\documentstyle[IEEEtran]{article} \begin{document} \tolerance 10000 \title{An Interval Approach to Congestion Control in Computer Networks} \author{Scott Starks} \pagestyle{myheadings} \markright{APIC'95, El Paso, Extended Abstracts, A Supplement to the international journal of {\rm Reliable Computing}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \maketitle \begin{abstract} It is important to dynamically tune communication network parameters in order to improve the performance of the network and to prevent congestion. All parameters can be tuned, including the size of a packet, the retransmission timeout (i.e., the amount of time to wait for an acknowledgment), etc. Tuning is usually done by applying some predefined linear transformation to the current values of these parameters: e.g., add a constant, subtract a constant or multiply the current value by a constant. If we fix the parameters of these transformations once and forever, we still have some congestion problems. As an attempt to avoid this difficulty, Van Jacobson proposed to use nonlinear transformations (namely, a specific family of fractionally linear ones). His simulation results showed that this new tuning algorithm really worked well. However, the resulting behavior is still sometimes highly unstable. In \cite{Narasimhamurthy 1992,1994}, a linear congestion control with adaptive coefficients has been proposed. This tuning method turned out to perform much better that the non-adaptive non-linear one. In this paper, we use interval approach to explain why linear methods perform better than non-linear ones. \end{abstract} \auffil{The author is with Department of Electrical Engineering, The University of Texas at El Paso, El Paso, TX 79968.} \section{Introduction} \subsection{Why do we need to tune?} It is important to dynamically tune communication network parameters in order to improve the performance of the network and to prevent congestion \cite{Kleinrock 1978}. Congestion can occur for every network that has routers and/or gateways that connect several smaller networks because the resources of these routers are limited and therefore they form a bottleneck for the overall network. A typical example of such a network is the Internet (the same problems occur, however, for every Wide Area Network ({\it WAN})). Namely, the observations show the following pattern: the number of messages varies from time to time and inevitably a moment comes when it exceeds the capacity of a router's or gateway's queue. Then some messages are simply dropped from the network. So the computer that sent the dropped message waits for the message acknowledgment ({\it ack}) for some time ({\it retransmission timeout}), and when this time expires and there is no ack, it sends the same message again. As a result the same messages can go through the network several times. Therefore the number of the messages that are still in the network increases rapidly: because new messages come and the old messages are retransmitted again and again. As a result the queues become longer, more and more messages are dropped and we are on the edge of congestion collapse. Congestion problems can become more serious in the case of a {\it distributed file system (DFS)}, i.e., when we try to access files remotely. The reason why it is more difficult for a network to deal with distributed file system is evident: in addition to the usual messages it now has to move files, and those files can be long, so the total number of messages in the network increases. Some network protocols take care of that problem and so adding a distributed file system in the majority of cases does not worsen the congestion problems; an example of such a protocol is the Transmission Control Protocol (TCP) \cite{Jacobson 1988}. However, the most widely used distributed file system is the Network File System (NFS), and the majority of its implementations use another protocol: the User Datagram Protocol (UDP). The reason why the designers preferred UDP is that UDP up to now has been better in performance (faster, etc) than TCP. The users still use NFS over UDP because they have practically no choice: NFS over TCP is not yet widely available; and even if it was, its performance is still worse \cite{Macklem 1991}. NFS in general, and NFS over UDP in particular, works fine with Local Area Networks (LAN). In principle it is possible to use NFS with WANs as well. However, the researchers are extremely cautious about that. Experiments with the existing implementations show that as the number of users increases the behavior of the network deteriorates \cite{Kent 1987, Nowicki 1989}. So they conclude that NFS over UDP might lead to congestion collapse if it were widely used (see, e.g., a footnote on p. 321 of \cite{Jacobson 1988}). In view of all that we really have to dynamically change the parameters of the services that use the network in order to avoid or overcome congestion. So whenever we encounter congestion (or by some means know that we are close to it) we change (``tune'') the parameters. So the problem is: how to tune so that congestion is avoided? \subsection{What to tune?} We want to enumerate the retransmission parameters of the network. Some of the network protocols allow the user to change these parameters, in some of them the user has no access to them, and the method of changing (tuning) them must be incorporated into the implementation of this protocol by the designer of that implementation. Let's enumerate the main parameters and briefly explain what they mean: \begin{itemize} \item {\it Window size} (usually denoted by $W$). A window size is the maximum number of packets that a user is allowed to send before getting an acknowledgment: for example, if $W=10$ then after sending 10 packets he must wait until some ack comes before he can send the 11th packet. Some protocols do not have such a limitation (e.g., UDP). The protocols for which $W$ is defined are called {\it window-based} protocols. An example of such a protocol is TCP. The user never has any control over the window size, it is determined by the implementation. \item {\it Interpacket interval} (usually denoted by $I$). It is the time interval between packets. This parameter corresponds to a congestion-avoiding method that is an alternative to limiting the window size: namely, after the user sends a packet he cannot send the next one until after some time $I$ elapses. \item {\it Retransmission Timeout} or {\it timeout} for short (it is usually denoted by $\tau_{out}$). A timeout is the amount of time during which the node waits for an acknowledgment. If the ack does not come after $\tau_{out}$ seconds then the node sends the same packet once again. In TCP, this parameter is controlled by the implementation, so the only way to change it is to incorporate the changes into the implementation. In UDP the user can choose their own $\tau_{out}$. \item {\it Packet size} (usually denoted by $P$). It is the size of the packet. There can actually be several packet sizes for the different stages of the communication process. First the information is read or written in quanta that are called the {\it application-level packet size}. Then depending on the transport protocol these quanta are combined (or subdivided, if necessary) into packets of some other packet size. And, finally, before the signals go into the real physical network they must again be subdivided into packets whose size is not bigger than the maximum physical packet size. The user can control the application-level packet size (for example, NFS packet size), all other packet sizes are bounded by the protocol(s) and the physical network used. \end{itemize} \subsection{How are these parameters tuned now?} Before we present the formulas let's choose the notations. The new (current) value of a network parameter is usually marked by a subscript $c$ (c stands for current) and the previous value by $p$ (p stands for previous). For example, the current value of the window size is denoted by $W_c$ and the previous value by $W_p$. The window size is usually changed as follows \cite{Jacobson 1988,Ramakrishnan Jain 1990}: if the network becomes congested (we can tell it by the fact that one of the packets is lost) then we must decrease the window size. If, vice versa, no congestion signal appears, that possibly means that there is some additional room in the network, so we can increase $W$ a little bit. For decrease the new value $W_c$ equals to $dW_p$ (this formula is called {\it multiplicative decrease}). Here $d$ is a positive constant that is smaller than 1. In \cite{Jacobson 1988} $d=0.5$ is proposed, but the authors of \cite{Ramakrishnan Jain 1990} claim that $d=0.875$ is better. Another possibility is {\it additive decrease} $W_c=W_p-d$, where $d$ is some positive constant, but experimentally it proves to be worse \cite{Ramakrishnan Jain 1990}. For increase usually an additive algorithm is used: $W_c=W_p+c$. The changes in the interpacket interval are usually also described by linear formulas: for increase $I_c=dI_p$ with $d>1$, and for decrease $I_c=I_p-d$. However, these algorithms sometimes lead to bad oscillations \cite{Kline 1987,Prue Postel 1987,Jacobson 1988}. Therefore in \cite{Jacobson 1988} a different update algorithm is proposed for decrease: $I_c=\alpha I_p /(\alpha+I_p)$, where $\alpha$ is some positive constant. According to his experimental data, this algorithm appears to perform well. Tuning the timeout usually requires more complicated algorithms that take into consideration not only the previous value of the timeout and whether there is a congestion or not, but also the whole history of packet transmissions. Namely, these algorithms are based on the values of round-trip times $t_i$ for all the previous packets, i.e., the times from the moment when the packet was sent to the moment when an acknowledgment was received by the sender. From these data we can estimate an average $a=(\sum t_i)/n$ and a mean square deviation $\sigma=(\sum (t_i-a)^2/(n-1))^{1/2}$. Then the timeout so that practically all known round trip times $t_i$ are smaller than $\tau_{out}$. Following the standard statistical rules, we set $\tau_{out}=a+k\sigma$, where $k=2..4$. In \cite{Jacobson 1988} $k=2$ is recommended for TCP; the experiments of \cite{Macklem 1991} show that for UDP $k=4$ is a better choice. Proposed methods of tuning the packet size are just the same as for windows: for example, for NFS read and write sizes Nowicki \cite{Nowicki 1989} proposed to use multiplicative decrease and additive increase. \subsection{Non-linear and adaptive linear tuning} As we have seen, the choice of the tuning procedure can be crucial. Right now the main tuning procedures are linear ones, in which the new value $x_c$ of the tuned parameter $x$ is a linear function of the previous value: $x_c=ax_p+b$ for some constants $a$ and $b$. These linear tuning procedures work more or less fine. The first attempt to try a non-linear procedure (fractionally linear, by Jacobson) immediately lead to the radical performance improvement. In \cite{Narasimhamurthy 1992,1994}, the intelligent control methodology was used to transform the experience of expert system administrators into a linear congestion control with adaptive coefficients. This control turned out to perform much better that the proposed non-linear one. This is an empirical result. We did not compare our adaptive linear control with arbitrary non-linear ones. So, before we recommend to use the adaptive linear congestion control, it would be nice to analyze this problem theoretically, and either prove that linear control is better, or find a non-linear control that is better than the linear one. This is the problem that we deal with in the present paper. \subsection{Why is this problem difficult to solve?} These problems are difficult to solve because the network is a very complicated system. There is no known way to estimate its performance under different tuning rules other than performing a time-consuming simulation of the whole network. Therefore we cannot really compare a lot of different tuning functions, and even so if we experimentally choose one of them, it will still be possible that we missed the best tuning algorithm. \section{Main Idea} Our main idea is to use {\it intervals} instead of numbers. \begin{itemize} \item We will first explain this idea on the example of an interpacket interval. If we fix the interval $I$, this means that whenever we send a packet at some moment of time $t_0$, then and the next packet appears during an interval $[t_0,t_0+I]$, then we do not send this packet. In essence, the number that is called an interpacket interval is actually a characteristics of the actual {\it interval}: in this example, an interval $[0,I]$. \item Similarly, a timeout $\tau_{out}$ is a characteristic of the time {\it interval} during which we wait for the ack. \item The window size $W$ means that the actual number of unacknowledged messages initiated by this node can be any number from the interval $[0,W]$. \item etc. \end{itemize} What did we gain by rephrasing the numerical characteristics in terms of intervals? At first glance, we only made the description more complicated: \begin{itemize} \item instead of a single number, we must now describe the interval, i.e., two numbers (its endpoints); \item the tuning transformation $f$, that was previously described as a function from numbers to numbers, must now be described as a function from intervals to intervals (i.e., as two functions of two real variables). \end{itemize} However, we did gain something: namely, now, we can apply reasonable invariance demands to describe the tuning function $f$ from intervals to intervals (similar invariance demands are used, for a different purpose, in \cite{Wu}). The first invariance condition is {\it scale-invariance}. We want to design a function $f$ that transforms the initial interval ${\bf a}=[a^-,a^+]$ into the tuned one $f({\bf a})$. In order to describe the physical quantity $a^\pm$ (e.g., time) in numerical terms, we must fix a unit. It is natural to demand that the transformation $f$ must not depend on what exactly units we have chosen: be it a nanosecond, a millisecond, or something else. If, instead of the original unit (e.g., sec.), we use a new unit that is $\lambda$ times smaller (e.g., millisec.), then the numerical values will increase $\lambda$ times, and instead of ${\bf a}=[a^-,a^+]$, we will have $$\lambda\cdot{\bf a}=[\lambda \cdot a^-,\lambda\cdot a^+].$$ So: \begin{itemize} \item If we use the original unit, then the initial interval domain is described as ${\bf a}=[a^-,a^+]$. If we apply the function $f$ to this interval, we get $f({\bf a})$. \item If we use a unit that is $\lambda$ times smaller than the original one, then the same initial interval will be described by new numerical values: $\lambda\cdot {\bf a}=[\lambda\cdot a^-,\lambda\cdot a^+]$. If we apply the same transformation to these new values, we get the interval $f(\lambda\cdot {\bf a})$. \end{itemize} We want these two intervals to coincide: \begin{itemize}\item the interval $f({\bf a})$ in the old units, and \item the interval $f(\lambda\cdot {\bf a})$ in the new units. \end{itemize} To compare these intervals, we must express both intervals to one and the same unit. For example, if we transform $f({\bf a})$ to new units, we will get $\lambda \cdot f({\bf a})$. This new interval must coincide with $f(\lambda\cdot {\bf a})$: $$f(\lambda\cdot{\bf a})=\lambda\cdot f({\bf a}).\eqno{(1)}$$ A similar condition can be formulated if formalize the idea that the transformation $f$ should not depend on the choice of the starting point for time (i.e., if we choose a new starting point that is $\tau$ time units before the original one, then the numerical expression for the interval would change from $[t_0,t_0+I]$ to $[t_0+\tau,t_0+\tau+I]$). This invariance can be expressed as: $$f({\bf a}+a)=f({\bf a})+a.\eqno{(2)}$$ Now, we are ready for the formal definition: \section{Definition and the Main Results} \noindent{\bf Definition.} \begin{itemize} \item We say that a function $f$ from intervals to intervals is {\it scale-invariant} if it satisfies condition (1) for every interval $\bf a$ and for every positive real number $\lambda>0$. \item We say that a function $f$ from intervals to intervals is {\it translation-invariant} if it satisfies condition (2) for every interval $\bf a$ and for every real number $a$. \end{itemize} \noindent{\bf THEOREM.} \cite{Wu} {\it Every translation-invariant and scale-invariant function from intervals to intervals has the form $$f([a^-,a^+])=$$ $$[{a^-+a^+\over 2}+{a^+-a^-\over 2}\cdot b^-, {a^-+a^+\over 2}+{a^+-a^-\over 2}\cdot b^+]$$ for some real numbers $b^\pm$.} \smallskip According to this result, the endpoints of the transformed interval linearly depend on the endpoints of the initial interval. In other words, {\it reasonable invariance demands lead to linear tuning formulas.} This result explains why linear tuning formulas turned out to be empirically the best. \begin{thebibliography}{99} \bibitem{Jacobson 1988} Van Jacobson, ``Congestion avoidance and control'', {\it Proceedings of the SIGCOMM 88 Symposium on Communication Architectures and Protocols}, Stanford CA, 1988, pp. 314--329. \bibitem{Kent 1987} C. A. Kent and J. C. Mogul, ``Fragmentation considered harmful'', In: {\it Proceedings of the SIGCOMM 87 Workshop on Frontiers in Communications Technology}, Stowe, VT, August 1987, pp. 390--401. \bibitem{Kleinrock 1978} L. Kleinrock, ``On flow control in computer networks'', In: {\it Proceedings of the International Conference on Communications}, June 1978, pp. 27.2.1--27.2.5. \bibitem{Kline 1987} C. Kline, ``Supercomputers on the Internet: a case study'', In: {\it Proceedings of the SIGCOMM 87 Workshop on Frontiers in Communications Technology}, Stowe, VT, August 1987. \bibitem{Macklem 1991} R. Macklem, ``Lessons learned tuning the 4.3BSD Reno implementation of the NFS protocol'', {\it Proceedings of the USENIX Winter Conference}, Dallas, TX, 1991, pp. 53--64. \bibitem{Narasimhamurthy 1992} P. Narasimhamurthy, {\bf Application of intelligent control to congestion in computer networks}, Master Thesis, Department of Electrical Engineering, University of Texas at El Paso, December 1992. \bibitem{Nowicki 1989} B. Nowicki, ``Transport issues in the network file system'', {\it Computer Communication Review}, March 1989, pp. 16--20. \bibitem{Prue Postel 1987} W. Prue and J. Postel, {\bf Something a host could do with source quench.} ARPANET Working group request for comment, DDN Network Information Center, SRI International, Menlo Park, CA, July 1987, RFC--1016. \bibitem{Ramakrishnan Jain 1990} K. K. Ramakrishnan and R. Jain, ``A binary feedback scheme for congestion avoidance in computer networks'', {\it ACM Transaction on Computer Systems}, 1990, Vol. 8, No. 2, pp. 158--181. \bibitem{1994}S. Starks, V. Kreinovich, and \\ P. Narasimhamurthy, ``How to avoid congestion in computer networks'', In: L. Hall, H. Ying, R. Langari, and J. Yen (eds.), {\it NAFIPS/IFIS/NASA'94, Proceedings of the First International Joint Conference of The North American Fuzzy Information Processing Society Biannual Conference, The Industrial Fuzzy Control and Intelligent Systems Conference, and The NASA Joint Technology Workshop on Neural Networks and Fuzzy Logic, San Antonio, December 18--21, 1994}, IEEE, Piscataway, NJ, pp. 466--469. \bibitem{Wu}K. C. Wu, ``Interval methods in mobile robot control'', {\it These Proceedings}, 1994. \end{thebibliography} \end{document}