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)<0. lust try to satisfy the negative feedback condition Since ai, bI, and all x,s are positive, the above y itself. This means a stronger condition to inequality is possible only if b -1 is negative and guarantee convergence to efficienc If so, substituting Xmax which is more than Ex, (1) y(t)=0→x,(t+1)>x,(t)v will make the left-hand side even more negative y(t)=1 (+1)<x;(1)v (11) +(b1-1)xmnx<0 Which translates into This violates (14) thus a contradiction with our a1+(b1-1)x()>0x,(r)≥0, For the case y=l, if all users truncate, then it ap+(bo-1)x,(r)<0x,(t)≥0 This implies further constraining equation(10)to nap+ box (r)>x t)vi, a1>0,b1>1 nap+(b-1)∑x1(t)>0. 0,0≤bD<1 Since bp is less than 1, the second term in the We shall demonstrate these constrains graphically left-hand side of the above equation is negative later, using the vector representations. -1 implies 2x, (t) is greater than Xya, hence Tlete is, lowever, a simple variation for us w Xmin Substituting Nmax in place of n, and Xmin in make the conditions in(12) less restrictive for place of Ex, (t), shoul d maintain the parameters b, and ap. If each user i truncates its must have control whenever the conditions in (11)would otherwise be violated, as below Nmax ap+(bp-1)Xin> 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