D.-M.Chiu. R Jain/Congestion Avoidance in Computer Nerworks These n equations can be addcd to form a single This is in fact the form of the control we are state equation proposing for our congestion avoidance scheme ∑x(t+1)=na+b∑x,(t) [10,11] x(++1)=na+bx()where X=>x, 4. Nonlinear Controls Given initial state X(O), the time to reach Xgoal In this section, we exl certain nonlinear controls. In particular, we show n+(b-1) goal how they can be represented by the vector di- an+(b-1)X{0) agrams as in the case for linear controls. This b>0 log(b) ntuitive feeling about how nonlinear controls work. The detailed analy- X(0) sis of nonlinear controls is beyond the scope this paper. However, we will explain why we con After converging to X oal there will be a maximum sider such nonlinear mtrols uut suitable for pia tical purpose overshoot of Let us consider in general state transition equa- se=|an+(b-1)XgoalI- tions that are expressible as a power of the state: Notice that t. is a monotonically decreasing func- x, (t+1)=x, (()+a(x,(1) tion of a and b, while s. is a monotonically increasing function of a and b. Thus, any attempt to increase responsiveness(decrease te)also re- (1)=a(x, (t)) sults in decreased smoothness(increased s ),and here k can be any integer(positive, negative or VIce versa. zoro), and a is a normalization constant th defines the step size and sign. Note that k=0 3.2. Optimal Convergence to Fairness gives the additive policy and k=l gives the multi plicative policy Equation(7)shows that the per step improve- Now let us consider the two user vector repre- ment in fairness F(r(r-1))-F(())is a mono entation for these controls. In Fig. 8 we first onically increasing function of c=a/b. Thus, show the efficiency and fairness lines as before larger values of a and smaller values b give quick Consider the point x. Let g(k) be the slope of convergence to fairness u(t). Then we know o(0)is 45 and a(1)is the For the case of strict linear controls, this leads same as the slope for the initial state x(t). As k feasibility conditions required an=0. Thus, the to negative infinity, A(k)tends to oasktends elegantly simple conclusion. For decrease, tends to infinity, e(k)tends to.and fairness remains the same at every decrease step Since fairness requires that the slope of the new Ind the parameter bD has no effect on time to state x(t+1)be closer to 45. than that of the converge to a fair state. For increase, smaller bI initial state x(), we must have k< 1(negative k results in quicker convergence to fairness. Thu s fine) the optimal value of b, is its Iirimuin valuc-Unt Slopes for other three possibilites r, x,and (See Equation(12). )Choosing b,=l is equivalent x are shown in the figure and can be similarly to saying that additive increase gives us the quick- explained Considering all four possibilities we see est convergence to fa that the feasibility condition requires k< 1 for formally stated as: increase and k> 1 for decrease (with at least one inequality being strict), and appropriate values for tion 3. For both feasibility and optimal con- a so the sign and step size are correct. The ad e to fairness, the increase policy should be ditive increase and multiplicative decrease control and the decrease policy should be for example, clearly satisfies this general condi plication. tion