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)<∑x;(r) crease or decrease policy. In terms of increase/de- In terms of the policy parameters, this means that the parameter values should be o and 0 na,+(bi+1)Ex, ((>0 n and VEx, (2), nap +(bp-1)x, (1)<0 Vn and vEx, (n) >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