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)<Sos) aIe both and are considered inefficient, We consider both Here, a1, b,, an, bn are constants. The following as equally undesirable are some exam ples of the control functions Notice, that efficiency relates only to the total (1)Multiplicative Increase/Multiplicative De- allocations and thus two different allocations can crease both be efficient as long as the total allocation is x, ((+U)s/b1 x,()if y(r)=0=Increase. close to the goal. The distribution of the total allocation among individual users is measured by (, (1)if y(r)=1=Decrease the fairness criterion (2) Fairness: The fairness criterion has been their demands by multiplying their previous de- widely studied in the litcrature. When multiplc mands by a constant factor. The decrease is also users share multiple resources, the maxmin fair- multiplicative ess criterion has been widely adopted [2, 3, 5, 10 Additive Increase /Additive Decrease Essentially, the set of users are partitioned into equivalent classes according to which resource is x(+1 their primary bottleneck. The maxmin criterion ar+x, (o if y(r)=0= Increase, hen asserts that the users in the same equivalent ap+x( if y(o=l= Decrease i It is assumed that truncation is applied when ap +x(o)is Here, a>0 and ap <O. All users increase their less than zero, so that x, (r) will never become negative