Analysis of the Increase and decrease Algorithms for Congestion Avoidance in Computer Networks Dah-Ming CHIU and Raj jAl 1. Introduction Digital Equipment Corporarion, 550 King Siree(LKGI-2/4A19 Littleton, MA O1460-1289, U.S.A 1. background Congestion in computer networks is becoming an important issue due to the increasing mismatch in link new technology, Recent technological advances that allow the network to recover from the congested state of high delay and low throughput. Both con gestion avoidance and congestion control mechanisms are basi ally resource management problems. They can be formulated algorithm(or control function) used by ease or decrease their load (window or rate). We abstractly aFro 979 to 1980. he was wi de class of such increase/decrease algorithms orked on applying queuing theory to and compare them using several different performance metrics. Thcy kcy metrics are cfficicncy, fairncao, convcrgence time, been with Digital Equipment Corpo- and size of oscillations. formance modeling and analysis of com It is shown that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for con- tems Archi to an efficient and fair state regardless of the starting rithms. His research interests include operation systems, dis- ation in the congestion avoidance scheme recom- and optimization theories. Digital Networking Architecture and OSI Trans- Dr Chiu is a member of the ACm and the IEEE ort Class 4 Networks Raj Jain received the B.E. degree eywords, Computer Network, Congestion ctor oL, Congestion AvO dance. flow Control fairness. cambridgeoma. in19⊥ His Ph D. dissertation their"Outstanding dissertations in systems and networks including VAX Clusters, DECnet, and rchitecture and perfe a sabbatical at the ma cal area systems. For North-Holland Computer Networks and ISDN Systems 17(1989)1-14 er of the Association for Computing Machinery. and a senior member of IEEE 0169-7552/89/S3.500 1989, Elsevier Science Publishers B V(North-Holland)
2 D,M Chiu R Jain/Congestion Aooidance in Computer Networks Cliff ueues start overflowing, the response time in- The point at which the packets start getting lost is called a cliff due to the fact that the throughput falls off rapidly after this point. We use the term knee to descnbe the point alter which the increase increase in the response time results a scheme that allows the network to operate at Load the knee is called as distinguished from a congestion control scheme that tries to keep the network operating in the zone to the left of the cliff. a properly designed congestion avoidance scheme will ensure that the users are encouraged to increase their traffic load as long as this does not significantly affect ul response time, and are rcquircd to dcercase them if that happens. Thus, the network load oscillates around the knee Both congestion avoidance and congestion con- Fig. 1. Network performance as a funetion of the load. Broken trol mechanisms are dynamic resource manage curves inuiuaie perfulInance will detcatiliMliy ct nterarnval times. ment problems that can be formulated as system control problems in which the system senses its state and feeds this back to its users who adjust their controls. For the congestion problem, the sucl as lucal auea networks(LANs) and fibcr statc consists of the load on the network and the optic LANs have resulted in a significant increase control is the number of packets put into the in the bandwidths of computer network links. network by the users. Often a window mechanism However, these new technologies must coexist with is used in the transport layer protocols to limit the the old low bandwidth media such as the twisted number of packets put into the network. An alter pair. This heterogeneity has resulted in a mis- native mechanism consists of setting a limit on the match of arrival and service rates in the inter ate(packets per second or bits per second)that mediate nodes in the network causing increased can be sent by a user. In either case, the control queuing and cor (window or rate)can be dynamically adjusted as Traditional congestion control schemes help the total load on the system changes. This control, improve performance after congestion has oc- which we call the increase/decrease algorithm, is rred. Figure 1 shows general patterns of re- at the heart of all congestion avoidance mecha sponse time and throughput of a network as the nism. network load increases. If the load is small, We have investigated a number of congestion throughput generally keeps up with the load. As avoidance mechanisms, reported in a series of the load increases, throughput increases. After the papers, and this paper is a part of that serie load reaches the network capacity, throughput [1,8 U, Il]. The concept of congestion avoidance stops increasing. If the load is increased any fur- and several alternatives are described in [7]. We ther, the queues start building, potentially result hose a particular alternative called the"binary ing in packets being dropped. Throughput ma feedback scheme"which is described in detail in suddenly drop when the lo creases heyond [11]. This scheme is later extended in (101 this point and the network is said to be congested. include a "selective feedback "mechanism in which The response-time curve follows a similar pattern. the routers monitor different users and permit At first the response time increases little with some users to increase load while requesting others load. When the queues start building up, the re- to decrease load. All of our work on congestion sponse time increases linearly until finally, as the avoidance is summarized in [8]
D.M. Chiu, R Jain/ Congestion Avoidance in Camputer Network This papel contenlaLes un a detailed analys At the other end of the spectrum, we have de of the increase/decrease algorithms. This analysis centralized decision-making. In this case the deci- resulted in the selection of the increase/decrease sions are made by the users while the resources algorithms used in the binary feedback scheme feed formation regi garding current resource usage. proposed in [1ll and [10]. However, the analysis Algorithms studied by Jaffe [5] and later exten presented here is general and applies to many sions by Gaini [2] and Mosely [91 are all good other applications besides congestion avoidance examples of this approach. Briefly, the binary feedback scheme for conges- In this paper we analyze a class of decentral- tion avoidance operates as follows. The resources ized decision-making algorithms that are based on in the network monitor their usage and determine a special form of feedback, namely the feedback if they are loaded below or above an optimal from the resource is a binary signal. This binary level Depending upon the load level, the resource signal indicates whether the resource is currentI sends a binary feedback (1-overloaded, 0 erloaded or underutilized. A very good reason nderloaded) to the users who then adjust their for considering a binary form of feedback is the using an increase/ decrease algorithm. Thi motivation of making the controller/ manager of binary feedback is sent by setting a bit in the the resource as simple and efficient as possible packet header. The use of a bit in the packet The requirement of a binary feedback often min header as a feedback mechanism has been incor- mizes the work at the resource in generating the porated into the OSI connectionless networking feedback protocol standards [4]. The bit is called a"conges- n experienced bit " and is a part of a field called 1.3. Notations and Definition The abstract model assumes that all the users Figure 2 shows the assumed model of the net sharing the same bottleneck will receive the same work with n users sharing it. The congestion state feedback, Based on this feedback, the users try to of the system is determined by the number of adJust their load so that the bottleneck is effi- packets in the system. We assume a discrete time iently used as well as equally shared by all users. operation with time divided into small slots.'These In this abstracted context. we assume that the slots basically represent intervals at the beginning feedback and control loop for all users is synchro- of which the users set their load level based on the nous, that is, all users receive the same feedback network feedback received during the previous and react to it: the next feedback is then gener ted after all users have reacted to the feedback x(1), then the total load at the bottleneck re and so on. Also, we concentrate on one bottleneck source would be Ex, (t),and the state of the resource and the users that share it. Because of system is denoted by the n-dimensional vector these abstractions, we are able to demonstrate x(0) some of the subtle behavior of this type of al erating at or near the knee, all resources de- gorith. The results piescuted licle wele verified Mandel by the users are granted (this is not true by detailed simulations of real networks [7, 10. 111. at the cliff). Thus, x, (()denotes the ith user s 1.2 Past Work User J he algorithms studied here belong to a class of distributed algorithms for managing distributed pectrum of such distributed al- User 2 Xxi> goni gorithms have been studied in the literature. At onc cnd of thc spcctrum, we havc centralized decision-making. In this paradigm, information (about user demands) flows to the resource managers, and the decision of how to allocate the User n resource is made at the resource. The analysis by Sanders [12] is a good example of this approach Fig 2. A control system model of a users sharing a network
D-M. Chi,R Jain/Congestion Acoidance in Computer Networks demands by adding a constant amount to their sources. During th previous demands. The decrease is also additive. ermines its load level and sends a binary feed (3)Additive Increase/ Multiplicative Decrease back y(u), which is interpreted by the users as x (+1 follows a,+x, (t) if y(a)=0=Increase, y()-{3 1→ Decrease load i, (r) if y(t)=1=Decrease. The users cooperate with the system and change The increase is by a constant amount but the (increase of decrease)their demands by an amount decrease is by (4)Multiplicative increase /additive decrease x,(t+1) The change u () represents ith users control. It 6 x, (1 if y(1)=0=Increase, is a function of the users previous demand and ap+x( if y(o)=1- Decrease In order to evaluate the effectiveness of these u1()=f(x,(t),y(t) (2) controls, we next define a set of criteria explicitly In other words in the next section x(+1)=x,(t)+f(x,(t),y(1) 1. 4. Criteria for Selecting Controls Notice that the users are not aware of other user individual demands and, thus, cannot make u, (4) utedness, and convergence. We define them for- a function of x, (t)./*i In general, the control mally as follows function /()can be any linear or nonlinear func- (1) Eficiency: The efficiency of a resource usage on. However, we will focus first on linear con- is defined by the closeness of the total load on the trols. ihe state equations (1)reduce to resource to its knee. If X denotes the desired x(r+1) load level at the knee, then the resource is operat- ing efficiently as long as the total allocation X(r) (a1+hx, (1) if y(n)=0=Increase 2x, (4)is close to Xgoal. Overload ( X(1)> xgoal) ap+bpx,(r if y(1)=1= Decrease nderlvau(X(I)0 and ap <O. All users increase their less than zero, so that x, (r) will never become negative
D.-M. Chiu, R. Jain/Congestion Aeoidance in Computer Networks class ought to have the equal sliaie uf tlie but- Responsiveness tleneck. Thus, a system in which x, (t)=x()vi,J sharing the same bottleneck is operating fairly. If all users do not get exactly equal allocations, the system is less fair and we need an index or a Goal Smoothness function that quantifies the fairness. One such Total load on Fairness: F(r) n(∑x2) the network This index has the following properties (a) The fairness is bounded between 0 and 1(or 0% and 100%). A totally fair allocation( with Fig 3. Responsiveness and smoothness all x, 's equal) has a fairness of I and a totally unfair allocation(with all resources (4)Convergence: Finally we require the contro given to only one user)has a fairness of 1/n scheme to converge. Convergence is generally which is 0 in the limit as n tends to oo measured by the speed with which(or time taken (b)The fairness is independent of scale, i.e., till) the system approaches the goal state from any (c)The fairness is a continuous function, Any of the feedback, the system does not generally slight change in allocation shows up in the converge to a single steady state. Rather, the sys- fairness tem reaches an"equilibrium"in which it oscillates (d )If only k of n users share the resource around the optimal state. The time taken to reach equally with the remaining n-k users not this"equilibrium" and the size of the oscillations receiving any resource, then the faimess jointly deteRmine tie convergene. Te Lille dv termines the responsiveness, and the size of the For other properties of this fairness function, see oscillations determine the smoothness of the con- [6] trol. Ideally we would like the time as well as ( Distributedness: The next requirement that oscillations to be small. Thus, the controls with we put on the control scheme is that it be distrib- smaller time and smaller amplitude of oscillations uted. A centralized scheme requires complete are called more responsive and more smooth, re- knowledge of the state of the system. For example, pectively, as shown in Fig. 3. we may want to know each individual users de- Imand or their sulll. Tlis inforMation nlay be 1,5 Outline uf this Puper available at the resourcc. However, conveying this information to each and every user causes consid In this paper, we develop a simple and intuitive erable overhea d, especially since a user may be methodology to explain when and why a control g several resources at the same time. We are converges. We address the following questions thus primarily interested in control schemes that What are all the possible solutions that converge to an be implemented in real networks and, there efficient and fair states? How do we compare those fore, we assume that the system does the mini- controls that converge? mum amount of feedback. It only tells whether it The paper is organized as follows In Section is underloaded or overloaded via the binary feed e will characterize the set of all linear controls back bits. Other information such as X and thc and, thus, identify the set of feasibl number of users sharing the resource are assumed ntrols. Then we narrow down the feasible set to to be unknown by the users. This restricts the set a subset that satisfies our distributedness criterion of feasible schemes. We therefore, describe the set These subset still includes controls that have un- of feasible schemes with and without this restric- acceptable magnitudes of oscillation or those that tion converge too slowly. Then in Section 3, we discuss
6 D.M. Chiu, R Jain/ Congestion Avoidance in Computer Networks how to find the subset of feasible distributed system to this point regardless of the starting controls that represent the optimal trade-off of position. responsiveness and smoothness, as we defined in An points below the efficiency line represent an convergenceIn Section 4, we discuss how the underloaded” system ideally the system results extend to nonlinear controls. And in the would ask users to increase their load. Consider last section we summarize the results and discuss for example, the point ro=(ro, x2o). The ad- some of the practical considerations(such as sim- ditive increase policy of increasing both users plicity, robustness, and scalability allocations by a, corresponds to moving along a 45 line. The multiplicative increase policy of increasing both users'allocations by a factor b, 2. Feasible linear Controls corresponds to moving along the line that con- nects the origin to the point. Similarly, all points 2.L. Vector Representation of the dynamics above the efficiency line represent an"overloaded system and additive decrease is represented by a In determining the set of feasible controls, it is 45 line, while multiplicative decrease is rep helpful to view the system state transitions as a resented by the line joining the point to the origin trajectory through an n-uinneusiunal vector space The failness at any uint(I, 2)is given by We describe this method using a 2-user case, which can be viewed in a 2-dimensional space. As shown in Fig 4 Fairness=1+x2) 2(x2+x2) location (x,(n), x,(n) can be represented as a point(Xr,x2)in a 2-dimensional space. In this Notice that multiplying both allocations by a fac- figure, the horizontal axis represents allocations or b does not change the faimess. That is, user 1, and the vertical axis represents allocations (bxi, bx2)has the same fairness as(x,, x2) for all to user 2. All allocations for which x,+x2=Xgoal values of b. Thus, all points on the line joining a arc cfficicnt allocations. This corresponds to the point to origin have the fairness. We, there ed“ efficiency line al fore, call a line passing through the origin a 'equi-fairness"line. The fairness decreases as the This corresponds to the straight line marked"fair- slope of the line either increases above or de ness lin lines intersect at th creases below the fairness line Xgoal/2, Xgpav/2) that is the optimal point. The Figure s shot goal of control schemes should be to bring the two-user system starting from point xo using additive increase/multiplicative decrease control cy. The point ro is below the efficiency line and so both users are asked to increase. They do Go additively by along at an angle of45° Fairness Fairness This brings them to x, which happens to be abot Lir the efficiency line. The users are asked to decrease U s and they do so multiplicatively. This corresponds ser to moving towards the n on the line joining Alloc I, and the origin. This brings them to point I2 Overload which happens to be below the efficiency line and the cycle repeats. Notice that x, has higher fair XO ness than xo. Thus, with every cycle, the fairness Optimal point increases slightly, and eventually, the system con- ficiency line Underload keeps oscillating around the goa imilar trajectories can be drawn for other con trol policies. Although not all control policies con- User1’ s Allocation xl verge. For example, Fig. 6 shows the trajectory for Fig 4. Vector representation of a two-user case. the additive increase/ additive decrease control
D -M. Chiu, R Jain /Congestion Avoidance in Computer Nenworks dimness Allo x Efficiency Line Fig 5, Additive Increase/ Multiplicative Decrease converges to the optimal point policy starting from the position xo. The system converge to efficienc not to fairness. The keeps moving back and forth along a 45 conditions for conver to efficiency and through ro. With such a policy, the system ness are derived algeb in the next sec The operating oscillating along Fairness Line User Line User 1's Allocation Fig. 6. Additive Increase/Additive Decrease does not converge
D.M. Chi R, Jain/ Congestion Avoidance in Computer Networks 2.2. Convergence to Efficiency wherc c-a/b In order to guarantee convergence to efficiency =F(x(r)+(1-F(x(t)) we need to first make sure that at each step the system react correctly to the feedback by moving in the right direction. That is, when the system asks the users to decrease we should ensure that The last expression in the e above equati the total load will not increase and when the increasing function of c. Thus, it is sufficient to system asks the users to increase, the total load ensure that c>0 to guarantee non-decrease of will not decrease This is the principle of negative faimess. Note that c=0=F(x(+1))=F(x(c), feedback. Algebraical e,the fairness stays the same. To ensurc conver y(1)=0→∑x,(1+1)>∑x,(r), gence to fairness, we require c>0 for either in- y(t)=1=∑x,(t+1)0 n and VEx, (2), nap +(bp-1)x, (1)0 and 0. (9) or, equine In(8), the fairness goes up during decrease and either goes up or stays the same during increase. Vn and VEx, (t) similarly, (9)ensures that fairness goes up during increase and either goes up or stays the same during dccrcasc. This is sufficient to ensure con 2. 3. Convergence to Fairness vergence to fairness. We do not need the fairness to go up during both increase and decrease Equations (8) and (9) basically state that a r Convergence to fairness is defined as moving and b, should not be of opposite signs. Similarly, towards the fairness index of one, i.e ap and bp should not be of opposite signs F(xr()→1ast→∞. To satisfy (8)or(9), it follows that all four The linear control policies affect the fairness as follows for otherwise x, (() can become negative. Also, since n, Ex, (4), and ap are all positive, from (3) F(x(+1)=Cx(+1)2 n(∑x(r+1) 4) know bp must be less than 1. So 0,bt≥0, ap≥0,0≤b<1 (10) (Σa+bx(t) nE(a+ bx(t)) where ar and b cannot be both zero, else it would imply zero increase; and a, and ap cannot (Ec+x, ()) be both zero, else it would imply c is always zero. nE(c+x, (o) 2.4. Distributedness Note that eatiefyi he system will oscillate about the The requirement of having no information efficiency point. about system state other than the feedback y(o) 二 further limits the set of feasible linear control explore how the oscillation size Since the faimess requirements (Equation(8)or 9))do not involve any system state, it alread policy in the next satisfies the distributedness criterion. The ef
D.M. Chiu, R. Jain/Congestion AVoidance in Computer Networks cd in(),IIow ever, require knowledge of 2x (t)and n at each user. In the absence of such knowledge, each user na1+(b1-1)Ex,(t)x,(t)v will make the left-hand side even more negative y(t)=1 (+1)0x,(r)≥0, For the case y=l, if all users truncate, then it ap+(bo-1)x,(r)x t)vi, a1>0,b1>1 nap+(b-1)∑x1(t)>0. 0,0≤bD max(a1+b*(),x,(o)) This leads to a violation of(14); thus a contradi x(t+1) ify(r)=0→ Increase So the linear controls with truncation leave us min(ap +bpx (t),x,(n)) (13) with a set of conditions weaker than (12)and ify(t)=1→ Decrease stronger than (10) then(10) can guarantee both convergence to ef a> iciency with the distributed requirements. There is one catch. however that is all users could uncate at the same time (thus stopping any 0≤aD<(1-bp)x,0≤bp<1.(16 progress). To prevent this possibility, let's consider the following conditions Notice that in the case that we do not have any knowledge to bound Xgoal or n, that simply corre- Xmin=0 and xn Nax ap+(bp-1) (14) Then the conditions on linear control with trunca- tion reduce to the same ones as those on the for some Xmin and Xmax satisfying strictly linear control. We have essentially proven Xmn≤X8)≤Xmx (15) the following propositions Here, Nmax is the upper bound on the number of sers that would share the resource. the claim is ements of distributed convergence to sfficiency and fairness that when(14)and (15) are satisfied, it is impossI- without truncation, the linear decrease policy should ble forΣx,(+1=∑x,(1) Let us suppose the contrary is true for the case be mullica linear increase policy y=0. This means that should always have an additive component, an optionally it may he triplication compor a1+b1x(1)<x,(t)v with the coefficient no less than one
D,M, Chiu R Jain/ Congestion Avoidance in Computer Network tion(as defined in Equation(13), the increase and the fairness line and the line passing through rh decrease policies can each hane both additive and have higher fairness than xH(see Fig. 7(e).If we multiplicative components, satisfying the constraint. locate the mirre ge of x- the point in Equations(16) and(15) (xH, xH)this point has the same fairness as rH and all points between the fairness line and the The vectorial representation in the next section line joining x h have higher fairness than rh should help illustrate these results further Thus, for convergence to fairness, it is sufficient that the next point be in the region bounded by the two lines joining origin to the points x and 2. 5. Vectorial Representation of Feasibility Condi Combining the effect of all the restrictions, the region for distributively converging to efficiency The constraint on the control imposed by the and fairness is given by the intersection of the efficiency and fairness convergence conditions are regions shown in Fig. 7(b), and (c), i.e., by the line depicted in Fig. 7 for the 2-user case. Let us first joining r to the origin as shown in Fig. 7(d) consider a point in the overloaded region. As Thus the only policies that would distnbutvely shown in Fig. 7(a). the users start at the point satisfy the fairness and efficiency convergence x=(xi, x 2), which is above the efficiency line. conditions are those that move the operating point The system asks the users to decrease. The line along this line. In other words, the decrease must line. All points on this line have the same Similarly, starting with a point rL ficiency as x". For convergence to efficiency it is in the underloaded region, the region for distribu- sufficient to ensure that the next decrease moves tively converging to efficiency and fairness is given into the shaded area by the region shown in Fig. 7(e) The requirement of linear controls and dis Equations(12) ,(1b), and(15)are basically the ibutedniess puts additional IesticLiuis. Linear algebaic staicinent uf these conditions. ontrols imply that the new state vector x(t+ 1)is a sum of two vectors corresponding to a and bx(o). In two dimensions, a vector is represented by a 45. line through x(r). This is shown in Fig. 3. Optimizing the Control Schemes 7(b) by the line marked b=1. All future states corresponding to b= l lie on this line. Points to Having established the feasible control region, the left of the line can be reached if and only if we the next step is to determine the optimal policy choose b>1. Similarly, points to the right of the a policy that takes the system to the goal quickly line can bc rcached if x 1. The second vecto In this section, therefore, we discuss the selectiull orresponding to b]( )is represented by the line f control parameters to minimize the time to irked a=0 in Fig. 7(b). If we choose a=0, the convergence and to minimize the oscillations state x(t+1)will lie on this line. Points to the left of this line can be reached by choosing a 0. Depending upon the values of a and b. the set of reachable states will lie in one of In this subsection, we deal exclusively with the e four regions formed by the two lines a=0 ar adeoff of verge to b=1. Only one of these four regions, the one the oscillation size, se. More figuratively. we also corresponding to a<o and b< 1, is completely refer to these two metrics as responsiecncss and below the equi-efficiency line. This region is shown smoothness, respectivel shaded in Fig. 7(b). If we choose parameter values The n state equations corresponding for n users corresponding to other regions, the next state can are ot be guaranteed to be always below the equi-ef ficiency line. x,(t+1)=a+bx,(x),i=1,2,,n