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. Similarly, points to the right of this line can be 3.1. Optimal Convergence to Efficiency reached by 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