Research paper

Analysis of the Increase and Decreas, e Algorithms for Congestion Avoidance in Computer Networks

D a h - M i n g C H I U a n d Raj J A I N Digital Equipment Corporation, 550 King Street (LKG1-2 /,419), Littleton, MA 01460-1289, U.S.A.

1. I n t r o d u c t i o n

1.1. Background

Abstract. C o n g e s t i o n a v o i d a n c e m e c h a n i s m s allow a n e t w o r k to o p e r a t e in t h e o p t i m a l region o f low delay a n d h i g h t h r o u g h p u t , thereby, p r e v e n t i n g t h e n e t w o r k f r o m b e c o m i n g c o n g e s t e d . T h i s is d i f f e r e n t f r o m the t r a d i t i o n a l c o n g e s t i o n c o n t r o l m e c h a n i s m s t h a t allow t h e n e t w o r k to recover f r o m the c o n g e s t e d s t a t e o f h i g h delay a n d low t h r o u g h p u t . Both c o n - g e s t i o n a v o i d a n c e a n d c o n g e s t i o n c o n t r o l m e c h a n i s m s are basi- cally resource m a n a g e m e n t p r o b l e m s . T h e y c a n be f o r m u l a t e d as s y s t e m c o n t r o l p r o b l e m s in which t h e s y s t e m s e n s e s its state a n d feeds this back to its users w h o a d j u s t their controls.

T h e key c o m p o n e n t of a n y c o n g e s t i o n a v o i d a n c e s c h e m e is t h e a l g o r i t h m (or c o n t r o l f u n c t i o n ) u s e d b y the users to in- crease o r decrease their load ( w i n d o w o r rate). W e a b s t r a c t l y characterize a wide class o f s u c h i n c r e a s e / d e c r e a s e a l g o r i t h m s a n d c o m p a r e t h e m u s i n g several different p e r f o r m a n c e metrics. T h e y key metrics are efficiency, fairness, c o n v e r g e n c e time, a n d size of oscillations.

It is s h o w n t h a t a s i m p l e additive i n c r e a s e a n d multiplicative d e c r e a s e a l g o r i t h m satisfies t h e sufficient c o n d i t i o n s for c o n - v e r g e n c e to a n efficient a n d fair state regardless o f the s t a r t i n g s t a t e o f the network. T h i s is t h e a l g o r i t h m finally c h o s e n for i m p l e m e n t a t i o n in t h e c o n g e s t i o n a v o i d a n c e s c h e m e r e c o m - m e n d e d for Digital N e t w o r k i n g A r c h i t e c t u r e a n d OSI T r a n s - p o r t C l a s s 4 N e t w o r k s .

Keywords. C o m p u t e r N e t w o r k , N e t w o r k P e r f o r m a n c e , Re- s o u r c e M a n a g e m e n t , C o n g e s t i o n C o n t r o l , C o n g e s t i o n Avoi- d a n c e , Flow C o n t r o l , Fairness.

N o r t h - H o l l a n d C o m p u t e r N e t w o r k s a n d I S D N S y s t e m s 17 (1989) 1 - 1 4

Congestion in computer networks is becoming an important issue due to the increasing mismatch in link speeds caused by intermixing of old and new technology. Recent technological advances

D a h - M i n g C h i u received the B.Sc. de- gree w i t h first class h o n o u r s f r o m I m - perial College o f Science a n d T e c h n o l - ogy, L o n d o n U n i v e r s i t y , in 1975, a n d t h e M.S. a n d Ph.D. degrees f r o m H a r v a r d U n i v e r s i t y , C a m b r i d g e , MA, in 1976 a n d 1980 respectively.

F r o m 1979 to 1980, he was with A T & T Bell L a b o r a t o r i e s , where he worked o n a p p l y i n g q u e u i n g t h e o r y to n e t w o r k m o d e l i n g . Since 1980, he h a s b e e n w i t h Digital E q u i p m e n t C o r p o - ration, where he h a s worked o n per-

f o r m a n c e m o d e l i n g a n d a n a l y s i s of c o m p u t e r s y s t e m s a n d n e t w o r k s . C u r r e n t l y , he is a m e m b e r o f the D i s t r i b u t e d Sys- t e m s A r c h i t e c t u r e g r o u p , where he is working o n the n a m e service architecture a n d a n a l y z i n g v a r i o u s d i s t r i b u t e d algo- rithms. His research i n t e r e s t s include o p e r a t i o n s y s t e m s , dis- t r i b u t e d s y s t e m s , c o m p u t e r networks, p e r f o r m a n c e analysis, a n d o p t i m i z a t i o n theories.

Dr. C h i u is a m e m b e r o f the A C M a n d the IEEE.

Raj Jain received the B.E. degree f r o m A.P.S. University, Rewa, India, t h e M.E. degree f r o m I n d i a n I n s t i t u t e of Science, Bangalore, India, a n d the Ph.D. degree f r o m H a r v a r d U n i v e r - sity, C a m b r i d g e , M A , in 1972, 1974, a n d 1978, respectively.

H i s P h . D . d i s s e r t a t i o n , e n t i t l e d " C o n t r o l T h e o r e t i c F o r m u l a t i o n o f O p e r a t i n g S y s t e m s R e s o u r c e M a n a g e - m e n t Policies," was p u b l i s h e d by G a r - l a n d Publishing, Inc. o f N e w Y o r k in their " O u t s t a n d i n g D i s s e r t a t i o n s in

t h e C o m p u t e r Sciences" series. Since 1978, he h a s b e e n with Digital E q u i p m e n t C o r p o r a t i o n , where he h a s b e e n involved in p e r f o r m a n c e m o d e l i n g a n d a n a l y s i s o f a n u m b e r o f c o m p u t e r s y s t e m s a n d n e t w o r k s i n c l u d i n g V A X Clusters, D E C n e t , a n d E t h e r n e t . C u r r e n t l y , he is a C o n s u l t i n g E n g i n e e r in the Distrib- u t e d S y s t e m s A r c h i t e c t u r e a n d P e r f o r m a n c e G r o u p . He s p e n t t h e 1 9 8 3 - 1 9 8 4 a c a d e m i c y e a r o n a s a b b a t i c a l at the M a s - s a c h u s e t t s I n s t i t u t e of T e c h n o l o g y d o i n g research on t h e pei-- f o r m a n c e o f n e t w o r k s a n d local area s y s t e m s . F o r three y e a r s he a l s o t a u g h t a g r a d u a t e c o u r s e on c o m p u t e r s y s t e m s perfor- m a n c e t e c h n i q u e s at M I T a n d is writing a t e x t b o o k o n this subject, to be p u b l i s h e d by Wiley-Interscience.

Dr. J a i n is a m e m b e r o f t h e A s s o c i a t i o n for C o m p u t i n g M a c h i n e r y , a n d a s e n i o r m e m b e r o f IEEE.

0 1 6 9 - 7 5 5 2 / 8 9 / $ 3 . 5 0 © 1989, Elsevier Science P u b l i s h e r s B.V. ( N o r t h - H o l l a n d )

2 D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

Knee Cliff ; ',

Throu- ~ ghput

I

Load !

RoeSsP- j *

time , , "

I l l . -

Load Fig. 1. Network performance as a function of the load. Broken curves indicate performance with deterministic service and

interarrival times.

such as local area networks (LANs) and fiber optic LANs have resulted in a significant increase in the bandwidths of computer network links. However, these new technologies must coexist with the old low bandwidth media such as the twisted pair. This heterogeneity has resulted in a mis- match of arrival and service rates in the inter- mediate nodes in the network causing increased queuing and congestion.

Traditional congestion control schemes help improve performance after congestion has oc- curred. Figure 1 shows general patterns of re- sponse time and throughput of a network as the network load increases. If the load is small, throughput generally keeps up with the load. As the load increases, throughput increases. After the load reaches the network capacity, throughput stops increasing. If the load is increased any fur- ther, the queues start building, potentially result- ing in packets being dropped. Throughput may suddenly drop when the load increases beyond this point and the network is said to be congested. The response-time curve follows a similar pattern. At first the response time increases little with load. When the queues start building up, the re- sponse time increases linearly until finally, as the

queues start overflowing, the response time in- creases drastically.

The point at which the packets start getting lost is called a cliff due to the fact that the throughput falls off rapidly after this point. We use the term knee to describe the point after which the increase in the throughput is small, but when a significant increase in the response time results.

A scheme that allows the network to operate at the knee is called a congestion avoidance scheme, as distinguished from a congestion control scheme that tries to keep the network operating in the zone to the left of the cliff. A properly designed congestion avoidance scheme will ensure that the users are encouraged to increase their traffic load as long as this does not significantly affect the response time, and are required to decrease them if that happens. Thus, the network load oscillates around the knee.

Both congestion avoidance and congestion con- trol mechanisms are dynamic resource manage- ment problems that can be formulated as system control problems in which the system senses its state and feeds this back to its users who adjust their controls. For the congestion problem, the state consists of the load on the network and the control is the number of packets put into the network by the users. Often a window mechanism is used in the transport layer protocols to limit the number of packets put into the network. An alter- native mechanism consists of setting a limit on the rate (packets per second or bits per second) that can be sent by a user. In either case, the control (window or rate) can be dynamically adjusted as the total load on the system changes. This control, which we call the increase/decrease algorithm, is at the heart of all congestion avoidance mecha- nisms.

We have investigated a number of congestion avoidance mechanisms, reported in a series of papers, and this paper is a part of that series [7,8,10,11]. The concept of congestion avoidance and several alternatives are described in [7]. We chose a particular alternative called the "binary feedback scheme" which is described in detail in [11]. This scheme is later extended in [10] to include a "selective feedback" mechanism in which the routers monitor different users and permit some users to increase load while requesting others to decrease load. All of our work on congestion avoidance is summarized in [8].

D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

T h i s p a p e r c o n c e n t r a t e s o n a detailed analysis o f the i n c r e a s e / d e c r e a s e algorithms. This analysis resulted in the selection o f the i n c r e a s e / d e c r e a s e a l g o r i t h m s used in the b i n a r y f e e d b a c k s c h e m e p r o p o s e d in [11] a n d [10]. H o w e v e r , the analysis p r e s e n t e d here is general a n d applies to m a n y o t h e r a p p l i c a t i o n s besides congestion avoidance.

Briefly, the b i n a r y f e e d b a c k s c h e m e f o r conges- tion a v o i d a n c e o p e r a t e s as follows. T h e resources in the n e t w o r k m o n i t o r their usage a n d d e t e r m i n e if t h e y are l o a d e d b e l o w o r a b o v e a n o p t i m a l l o a d level. D e p e n d i n g u p o n the l o a d level, the resource sends a b i n a r y f e e d b a c k (1 = overloaded, 0 = u n d e r l o a d e d ) to the users w h o then adjust their l o a d using a n i n c r e a s e / d e c r e a s e algorithm. This b i n a r y f e e d b a c k is sent b y setting a bit in the p a c k e t header. T h e use o f a bit in the p a c k e t h e a d e r as a f e e d b a c k m e c h a n i s m has b e e n incor- p o r a t e d into the O S I connectionless n e t w o r k i n g p r o t o c o l s t a n d a r d s [4]. T h e bit is called a " c o n g e s - tion experienced b i t " a n d is a p a r t o f a field called " q u a l i t y o f service" in the n e t w o r k layer header.

T h e a b s t r a c t m o d e l a s s u m e s t h a t all the users sharing the s a m e b o t t l e n e c k will receive the s a m e feedback. Based o n this feedback, the users try to a d j u s t their l o a d so t h a t the b o t t l e n e c k is effi- ciently used as well as equally shared b y all users. I n this a b s t r a c t e d context, we a s s u m e that the f e e d b a c k a n d c o n t r o l l o o p for all users is s y n c h r o - nous, t h a t is, all users receive the s a m e f e e d b a c k a n d react to it; the n e x t f e e d b a c k is t h e n gener- a t e d a f t e r all users h a v e reacted to the f e e d b a c k a n d so on. Also, we c o n c e n t r a t e o n o n e b o t t l e n e c k resource a n d the users t h a t share it. Because o f these abstractions, we are able to d e m o n s t r a t e s o m e o f the subtle b e h a v i o r o f this t y p e o f al- g o r i t h m . T h e results p r e s e n t e d here were verified b y detailed simulations o f real n e t w o r k s [7,10,11].

A t the o t h e r end o f the s p e c t r u m , we h a v e de- centralized d e c i s i o n - m a k i n g . I n this case the deci- sions are m a d e b y the users while the resources feed i n f o r m a t i o n regarding c u r r e n t resource usage. A l g o r i t h m s studied b y J a f f e [5] a n d later exten- sions b y G a f n i [2] a n d Mosely [9] are all g o o d e x a m p l e s o f this a p p r o a c h .

I n this p a p e r we a n a l y z e a class o f d e c e n t r a l - ized d e c i s i o n - m a k i n g a l g o r i t h m s t h a t are b a s e d o n a special f o r m o f feedback, n a m e l y the f e e d b a c k f r o m the resource is a b i n a r y signal. This b i n a r y signal indicates w h e t h e r the resource is c u r r e n t l y o v e r l o a d e d or underutilized. A very g o o d r e a s o n for considering a b i n a r y f o r m o f f e e d b a c k is the m o t i v a t i o n o f m a k i n g the c o n t r o l l e r / m a n a g e r o f the resource as simple a n d efficient as possible. T h e r e q u i r e m e n t o f a b i n a r y f e e d b a c k o f t e n mini- mizes the w o r k at the resource in g e n e r a t i n g the feedback.

1.3. Notations a n d Definitions

Figure 2 shows the a s s u m e d m o d e l o f the net- w o r k with n users sharing it. T h e c o n g e s t i o n state o f the s y s t e m is d e t e r m i n e d b y the n u m b e r o f p a c k e t s in the system. W e a s s u m e a discrete t i m e o p e r a t i o n with t i m e divided i n t o small slots. T h e s e slots basically r e p r e s e n t intervals at the b e g i n n i n g o f which the users set their l o a d level b a s e d o n the n e t w o r k f e e d b a c k received d u r i n g the p r e v i o u s interval. I f d u r i n g t i m e slot t, the i t h user's l o a d is x i ( t ), t h e n the total l o a d at the b o t t l e n e c k re- source would b e T . x , ( t ) , a n d the state o f the s y s t e m is d e n o t e d b y the n - d i m e n s i o n a l v e c t o r x ( t ) = { x l ( t ) , x 2 ( t ) . . . . . x n ( t ) } . Since we are o p - erating at o r n e a r the knee, all resource~ de- m a n d e d b y the users are g r a n t e d (this is n o t true at the cliff). Thus, x A t ) d e n o t e s the i t h u s e r ' s

1.2. P a s t W o r k

T h e a l g o r i t h m s studied here b e l o n g to a class o f d i s t r i b u t e d a l g o r i t h m s f o r m a n a g i n g d i s t r i b u t e d resources. A s p e c t r u m o f such d i s t r i b u t e d al- gorithrns h a v e b e e n studied in the literature. A t o n e e n d o f the s p e c t r u m , we h a v e centralized d e c i s i o n - m a k i n g . I n this p a r a d i g m , i n f o r m a t i o n ( a b o u t user d e m a n d s ) flows t o the resource m a n a g e r s , a n d the decision o f h o w to allocate the resource is m a d e a t the resource. T h e analysis b y S a n d e r s [12] is a g o o d e x a m p l e o f this a p p r o a c h .

U s e r 1

U s e r n

Y

r.xi > Xgoat (

N e t w o r k

Fig. 2. A control system model of n users sharing a network.

D. -M. Chit~ R. Jain / Congestion Avoidance in Computer Networks

d e m a n d as well as allocation of the system's re- sources. D u r i n g the interval, the system de- termines its load level and sends a binary feed- back y(t), which is interpreted by the users as follows:

y ( t ) = { ~ ~ I n c r e a s e l ° a d , Decrease load.

The users cooperate with the system and change (increase of decrease) their demands b y an a m o u n t ui(t ). Thus,

x i ( t + 1) = x i ( t ) + ui(t ). (1)

The change ui(t ) represents ith user's control. It is a function of the user's previous d e m a n d and the system feedback:

u , ( t ) = f ( x i ( t ) , y ( t ) ) . (2)

In other words,

x i ( t + 1) = x i ( t ) + f ( x i ( t ) , y ( t ) ) .

Notice that the users are not aware of other user's individual d e m a n d s and, thus, c a n n o t make ui(t) a function o f xj(t), j ~ i. In general, the control function f ( ) can be any linear or nonlinear func- tion. However, we will focus first on linear con- trois. The state equations (1) reduce to

x i ( t + 1)

= ( a l + b i x i ( t ) if y ( t ) = 0 ~ Increase,

a D + bDXi(t ) if y ( t ) = 1 ~ Decrease.

Here, a l, bi, aD, b D are constants. The following are some examples of the control functions:

(1) Multiplicative Increase/Multiplicative De- crease:

x i ( t + l ) = [ b l x ~ ( t ) if y ( t ) = 0 ~ Increase, [bDXi(t ) if y ( t ) = 1 ~ Decrease.

Here, b I > 1 and 0 < b D < 1. All users increase their d e m a n d s by multiplying their previous de- m a n d s by a constant factor. The decrease is also multiplicative.

(2) Additive Increase/Additive Decrease:

x i ( t + 1)

=[al+xi(t ) i f y ( t ) = 0 ~ Increase, [ a D + x i ( t ) if y ( t ) = 1 ~ Decrease.

Here, a i > 0 and a D < 0. All users increase their

demands b y adding a c o n s t a n t a m o u n t to their previous demands. The decrease is also a d d i t i v e )

(3) Additive Increase/ Multiplicative Decrease:

x i ( t + 1)

= ( a l + x i ( t ) i f y ( t ) = 0 ~ I n c r e a s e , b o x i ( t ) if y ( t ) = 1 ~ Decrease.

The increase is by a constant a m o u n t but the decrease is by a constant factor.

(4) Multiplicative Increase/Additive Decrease:

x i ( t + 1)

/ b~xi(t ) if y ( t ) = 0 ~ Increase, \ [ a o + x i ( t ) i f y ( t ) = l ~ D e c r e a s e .

In order to evaluate the effectiveness of these controls, we next define a set of criteria explicitly in the next section.

1.4. Criteria for Selecting Controls

The key criteria are: efficiency, fairness, distrib- utedness, and convergence. We define them for- mally as follows:

(1) Efficiency: The efficiency of a resource usage i s defined by the closeness o f the total load o n the resource to its knee. I f Xgo~ ~ denotes the desired load level at the knee, then the resource is operat- ing efficiently as long as the total allocation X ( t ) = F.xi(t ) is close to X~oar Overload ( X ( t ) > Xgoal) or underload ( X ( t ) < Xgoal) are b o t h undesirable and are considered inefficient. We consider b o t h as equally undesirable.

Notice, that efficiency relates only to the total allocations and thus two different allocations can b o t h be efficient as long as the total allocation is close to the goal. The distribution of the total allocation a m o n g individual users is measured b y the fairness criterion.

(2) Fairness: The fairness criterion has been widely studied in the literature. W h e n multiple users share multiple resources, the maxmin fair- ness criterion has been widely a d o p t e d [2,3,5,10]. Essentially, the set of users are partitioned into equivalent classes according to which resource is their p r i m a r y bottleneck. The maxmin criterion then asserts that the users in the same equivalent

i It is a s s u m e d t h a t t r u n c a t i o n is a p p l i e d w h e n a D + xi(t ) is l e s s t h a n z e r o , s o t h a t x i ( t ) w i l l n e v e r b e c o m e n e g a t i v e .

D. -M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

class o u g h t to h a v e the equal share o f the b o t - tleneck. Thus, a s y s t e m in which x i ( t ) = x j ( t ) V i, j sharing the s a m e b o t t l e n e c k is o p e r a t i n g fairly. I f all users d o n o t get exactly equal allocations, the s y s t e m is less fair a n d we need a n index or a f u n c t i o n t h a t quantifies the fairness. O n e such i n d e x is [6]:

F a i r n e s s : F ( x ) - ( E x ' ) 2 n(r ;i ) "

This index has the following properties: (a) T h e fairness is b o u n d e d b e t w e e n 0 a n d 1 (or

0% a n d 100%). A totally fair allocation (with all x i ' s equal) h a s a fairness o f 1 a n d a totally u n f a i r allocation (with all resources given to o n l y o n e user) h a s a fairness o f 1 / n which is 0 in the limit as n tends to oo.

(b) T h e fairness is i n d e p e n d e n t o f scale, i.e., unit o f m e a s u r e m e n t does n o t matter.

(c) T h e fairness is a c o n t i n u o u s function. A n y slight c h a n g e in allocation shows u p in the fairness.

(d) I f o n l y k o f n users share the resource equally with the r e m a i n i n g n - k users n o t receiving a n y resource, t h e n the fairness is k / n .

F o r o t h e r p r o p e r t i e s o f this fairness function, see

[61. (3) Distributedness: T h e next r e q u i r e m e n t t h a t

we p u t o n the c o n t r o l scheme is that it b e distrib- uted. A centralized s c h e m e requires c o m p l e t e k n o w l e d g e o f the state o f the system. F o r example, we m a y w a n t to k n o w e a c h individual u s e r ' s de- m a n d or their sum. This i n f o r m a t i o n m a y b e a v a i l a b l e at the resource. H o w e v e r , c o n v e y i n g this i n f o r m a t i o n to e a c h a n d every user causes consid- e r a b l e overhead, especially since a user m a y b e using several resources a t the s a m e time. W e are thus p r i m a r i l y interested in c o n t r o l schemes t h a t c a n b e i m p l e m e n t e d in real n e t w o r k s and, there- fore, we a s s u m e t h a t the s y s t e m does the m i n i - m u m a m o u n t o f feedback. I t o n l y tells w h e t h e r it is u n d e r l o a d e d o r o v e r l o a d e d via the b i n a r y feed- b a c k bits. O t h e r i n f o r m a t i o n such as Xsoal a n d the n u m b e r o f users sharing the resource are a s s u m e d to b e u n k n o w n b y the users. T h i s restricts the set o f feasible schemes. We, therefore, describe the set o f feasible schemes with a n d w i t h o u t this restric- tion.

G o a l

T o t a l load on

t h e n e t w o r k

~ e _ _ ~ C R e s p o n s i v e n e s s

~ o o t h n e s s

T i m e Fig. 3. Responsiveness and smoothness.

(4) Convergence: Finally we require the c o n t r o l scheme to converge. C o n v e r g e n c e is generally m e a s u r e d b y the speed with which (or t i m e t a k e n till) the s y s t e m a p p r o a c h e s the goal state f r o m a n y starting state. H o w e v e r , d u e t o the b i n a r y n a t u r e o f the feedback, the s y s t e m d o e s n o t generally converge to a single s t e a d y state. R a t h e r , the sys- t e m reaches a n " e q u i l i b r i u m " in which it oscillates a r o u n d the o p t i m a l state. T h e t i m e t a k e n to r e a c h this " e q u i l i b r i u m " a n d the size o f the oscillations j o i n t l y d e t e r m i n e the convergence. T h e t i m e de- termines the responsiveness, a n d the size o f the oscillations d e t e r m i n e the smoothness o f the c o n - trol. Ideally, we would like the t i m e as well as oscillations to b e small. Thus, the c o n t r o l s with smaller t i m e a n d smaller a m p l i t u d e o f oscillations are called m o r e responsive a n d m o r e s m o o t h , re- spectively, as s h o w n in Fig. 3.

1.5. Outline o f this P a p e r

I n this p a p e r , we d e v e l o p a s i m p l e a n d intuitive m e t h o d o l o g y to explain w h e n a n d w h y a c o n t r o l converges. W e a d d r e s s the following questions: W h a t are all the possible solutions that converge to efficient a n d f a i r states? H o w do we compare those controls that converge?

T h e p a p e r is o r g a n i z e d as follows. I n Section 2 we will characterize the set o f all linear c o n t r o l s t h a t c o n v e r g e and, thus, i d e n t i f y the set o f feasible controls. T h e n we n a r r o w d o w n the feasible set to a subset t h a t satisfies o u r d i s t r i b u t e d n e s s criterion. T h e s e subset still includes c o n t r o l s t h a t h a v e un- a c c e p t a b l e m a g n i t u d e s o f oscillation o r those t h a t c o n v e r g e t o o slowly. T h e n in Section 3, we discuss

6 D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

h o w to find the subset of feasible distributed controls that represent the optimal trade-off of responsiveness and smoothness, as we defined in convergence. In Section 4, we discuss how the results extend to nonlinear controls. A n d in the last section we summarize the results and discuss some o f the practical considerations (such as sim- plicity, robustness, and scalability).

2. Feasible Linear Controls

2.1. Vector Representation o f the Dynamics

In determining the set o f feasible controls, it is helpful to view the system state transitions as a trajectory through an n-dimensional vector space. We describe this m e t h o d using a 2-user case, which can be viewed in a 2-dimensional space.

As shown in Fig. 4, a n y 2-user resource al- location {Xl(t), x 2 ( t ) } Can be represented as a point ( x 1, x 2 ) in a 2-dimensional space. In this figure, the horizontal axis represents allocations to user 1, and the vertical axis represents allocations to user 2. All allocations for which x I + x 2 = Xgoa l are efficient allocations. This corresponds to the straight line m a r k e d " e f f i c i e n c y line". All al- locations for which x 1 = x 2 are fair allocations. This corresponds to the straight line m a r k e d " f a i r - ness line". T h e two lines intersect at the poin t ( X goal/2, Xgo~/2 ) that is the optimal point. T h e goal of control schemes should be to bring the

l Equi-

F a i r n e s s F a i r n e s s

U s e r ~ L m ~ L i n e

2's ~ ~ / /

Alloc- ] ~ / / O v e r l o a d

U s e r l ' s A l l o c a t i o n x t Fig. 4. Vector representation of a two-user case.

system to this p o i n t regardless o f the starting position.

All points below the efficiency line represent an " u n d e r l o a d e d " system an d ideally the system would ask users to increase their load. Consider, for example, the p o i n t x 0 = (xl0, x20 ). T h e ad- ditive increase policy o f increasing b o t h users' allocations b y a~ co rresp o n d s to m o v i n g along a 45 ° line. T h e multiplicative increase policy o f increasing b o t h users' allocations b y a f a c t o r b I c o r r e s p o n d s to moving along the line that con- nects the origin to the point. Similarly, all points above the efficiency line represent an " o v e r l o a d e d " system an d additive decrease is represented b y a 45 ° line, while multiplicative decrease is rep- resented b y the line j o i n i n g the p o i n t to the origin.

T h e fairness at a n y p o i n t ( x 1, x 2 ) is given b y

(Xl + x 2 ) 2 Fairness -

2 ( x 2 + x22) "

N o t i c e that multiplying b o t h allocations b y a fac- tor b does n o t change the fairness. T h a t is, ( b x 1, bx2) has the same fairness as ( x 1, x 2 ) fo r all values o f b. Thus, all points o n the line j o i n i n g a p o i n t to origin have the same fairness. We, there- fore, call a line passing t h ro u g h the origin a "equi-fairness" line. T h e fairness decreases as the slope o f the line either increases ab o v e o r de- creases below the fairness line.

Figure 5 shows a c o m p l e t e t raj ect o ry o f the two-user system starting f r o m p o i n t x 0 using an additive i n c r e a s e / m u l t i p l i c a t i v e decrease c o n t r o l policy. T h e p o i n t x 0 is below the efficiency line a n d so b o t h users are asked to increase. T h e y d o so additively b y moving along at an angle o f 45 o. This brings t h em to x~ which h a p p e n s to b e above the efficiency line. T h e users are asked to decrease an d they d o so multiplicatively. This c o r r e s p o n d s to moving towards the origin o n the line j o i n i n g x 1 and the origin. This brings t h em to p o i n t x 2, which h ap p en s to be below the efficiency line an d the cycle repeats. N o t i c e that x 2 has higher fair- ness t h an x 0. Thus, with every cycle, the fairness increases slightly, an d eventually, the system con- verges to the o p t i m al state in the sense t h at it keeps oscillating a r o u n d the goal.

Similar trajectories can b e d r a w n for o t h e r co n - trol policies. A l t h o u g h n o t all c o n t r o l policies con- verge. F o r example, Fig. 6 shows the t raj ect o ry for the additive i n c r e a s e / a d d i t i v e decrease co n t ro l

D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks 7

User 2's

Alloc- ation

x2

F a i r n e s s Line

x l /" /

/ / /

/,,;):,; ] l l l /

/ I / 1 I l l l /

I I l l I I I 1 ~

, ~5~' \ E f f i c i e n c y Line I i / / I i / / ~ /¢,

User l's Allocation xl Fig. 5. Additive Increase/Multiplicative Decrease converges to the optimal point.

ID-

policy starting from the position x 0. The system keeps moving back and forth along a 45 ° line through x 0. With such a policy, the system can

converge to efficiency, but not to fairness. The conditions for convergence to efficiency and fair- ness are derived algebraically in the next section.

U s e r 2's

Alloc- ation

x2

] The operating ] point keeps / oscillating along , .

\ / this line I ~ awness / Line

\ / / ,,"

~ N ~ l / / j fx0

/ j / j ~

/ ~ f f i c t e n e y Line

f

User l's Allocation x l Fig. 6. Additive Increase/Additive Decrease does not converge.

8 D.-M. Chiu, R. J a i n / Congestion Avoidance in Computer Networks

2.2. Convergence to Efficiency

I n o r d e r to g u a r a n t e e convergence to efficiency we need to first m a k e sure that at each step the s y s t e m react correctly to the f e e d b a c k b y m o v i n g in the right direction. T h a t is, when the s y s t e m asks the users to decrease, we should ensure that the total l o a d will not increase a n d when the s y s t e m asks the users to increase, the total load will not decrease This is the principle o f negative feedback, z Algebraically:

y ( t ) = O = ~,xi(t+ l ) > E x i ( t ) ,

y ( t ) = l = E x i ( t + l ) < X x i ( t ).

I n t e r m s o f the policy p a r a m e t e r s , this m e a n s t h a t the p a r a m e t e r values should b e

na I + (b I + 1 ) E x , ( t ) > 0 Vn a n d V ~ x i ( t ) ,

nap + ( b D - - l ) ~ x ~ ( t ) < 0 Vn a n d V E x , ( t ) ,

or, equivalently,

na I b ~ > l

F.xi(t)

na D b o < 1 E x i ( t ) Vn a n d VEx~(t). (3)

2.3. Convergence to Fairness

C o n v e r g e n c e to fairness is defined as m o v i n g t o w a r d s the fairness index o f one, i.e.,

F ( x ( t ) ) ~ 1 as t---, oo.

T h e linear c o n t r o l policies affect the fairness as follows:

( F . x i ( t + 1)) 2 F ( x ( t + 1)) = n ( Z x 2 ( t + 1)) (4)

= ( Z a + b x , ( t ) ) 2 (5)

n ~ , ( a + b x i ( t ) ) 2

(F.c + x i ( t ) ) z

where ¢ = a / b (6)

= F ( x ( t ) ) + (1 - F ( x ( t ) ) )

( z x 2 ( t ) )

X ] - - Y'~(C q- X i ( t ) ) 2 " (7)

T h e last expression in the a b o v e e q u a t i o n is an increasing function of c. Thus, it is sufficient to ensure that c >~ 0 to g u a r a n t e e n o n - d e c r e a s e o f fairness. N o t e that c - 0 ~ F ( x ( t + 1)) = F(x(t)), i.e., the fairness stays the same. T o ensure c o n v e r - gence to fairness, we require c > 0 for either in- crease or decrease policy. I n t e r m s o f i n c r e a s e / d e - crease p a r a m e t e r s , this implies

a l OD b--~ >~0 a n d ~ D > 0 (8)

o r

a l a D - - > 0 a n d >~0. (9)

I n (8), the fairness goes u p d u r i n g decrease a n d either goes u p or stays the s a m e d u r i n g increase. Similarly, (9) ensures t h a t fairness goes u p d u r i n g increase a n d either goes u p or stays the s a m e d u r i n g decrease. This is sufficient to ensure c o n - vergence to fairness. W e d o n o t n e e d the fairness to go u p d u r i n g b o t h increase a n d decrease.

E q u a t i o n s (8) a n d (9) basically state t h a t a~ a n d b I should not b e o f o p p o s i t e signs. Similarly, a D a n d b D should n o t b e o f o p p o s i t e signs.

T o satisfy (8) or (9), it follows t h a t all f o u r p a r a m e t e r s a l , b l , aD, a n d b D m u s t b e positive, for otherwise xi(t ) c a n b e c o m e negative. Also, since n, Exi(t), a n d a D are all positive, f r o m (3) we k n o w b D m u s t b e less t h a n 1. So

a l >/0, b I >~ 0, (10) a D > ~ 0 , 0 ~ < b D < l

where a~ a n d b~ c a n n o t b e b o t h zero, else it would i m p l y zero increase; a n d a~ a n d a D c a n n o t b e b o t h zero, else it would i m p l y c is always zero.

2.4. Distributedness

2 N o t e that satisfying the negative feedback condition alone only guarantees that the system will oscillate a b o u t the efficiency point, but says n o t h i n g about the size o f oscilla- tion. So this is strictly speaking weaker than the efficiency condition. We will, however, explore h o w the oscillation size c a n be minimized w h e n we talk a b o u t the optimality o f a policy in the next section.

T h e r e q u i r e m e n t o f h a v i n g n o i n f o r m a t i o n a b o u t s y s t e m state o t h e r t h a n the f e e d b a c k y ( t ) f u r t h e r limits the set o f feasible linear controls. Since the fairness r e q u i r e m e n t s ( E q u a t i o n (8) or (9)) d o n o t involve a n y s y s t e m state, it a l r e a d y satisfies the distributedness criterion. T h e ef-

D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks 9

f i c i e n c y c o n v e r g e n c e c o n d i t i o n s s t a t e d in (3), h o w - ever, r e q u i r e k n o w l e d g e o f Y.x~(t) a n d n at e a c h user. I n t h e a b s e n c e o f s u c h k n o w l e d g e , e a c h u s e r m u s t t r y t o satisfy t h e n e g a t i v e f e e d b a c k c o n d i t i o n b y itself. T h i s m e a n s a s t r o n g e r c o n d i t i o n t o g u a r a n t e e c o n v e r g e n c e t o efficiency:

y ( t ) = O ~ x i ( t + l ) > x i ( t ) V i ,

y ( t ) = l ~ x i ( t + l ) < x i ( t ) v i . (11)

W h i c h t r a n s l a t e s i n t o

a,+(b,-l)xi(t )>0 Vx,(t)>O, a D + ( b D - 1 ) x i ( t ) < 0 V x i ( t ) >/0.

T h i s implies f u r t h e r c o n s t r a i n i n g e q u a t i o n (10) t o b e

a i > O , b 1 > ~ l , (12)

a o = 0 , 0 ~ < b D < l .

W e shall d e m o n s t r a t e these c o n s t r a i n s g r a p h i c a l l y later, u s i n g t h e v e c t o r r e p r e s e n t a t i o n s .

T h e r e is, h o w e v e r , a s i m p l e v a r i a t i o n f o r us t o m a k e t h e c o n d i t i o n s in (12) less restrictive f o r p a r a m e t e r s b t a n d a o. I f e a c h u s e r i t r u n c a t e s its c o n t r o l w h e n e v e r the c o n d i t i o n s in (11) w o u l d o t h e r w i s e b e violated, as b e l o w

( m a x ( a , + b , x ~ t ) , x i ( t ) )

if y ( t ) = 0 I n c r e a s e , x i ( t + l ) = ) m J n ( a D + b D ~ ( t ) , x i ( t ) ) (13)

if y ( t ) = 1 D e c r e a s e ,

t h e n (10) c a n g u a r a n t e e b o t h c o n v e r g e n c e t o ef- f i c i e n c y with the d i s t r i b u t e d r e q u i r e m e n t s . T h e r e is o n e c a t c h , h o w e v e r , t h a t is all users c o u l d t r u n c a t e at the s a m e t i m e ( t h u s s t o p p i n g a n y progress). T o p r e v e n t this possibility, let's c o n s i d e r the f o l l o w i n g c o n d i t i o n s :

al + ( b l - 1 ) X m a x > O ,

Nmaxa D + ( b D - 1)Xmi n < 0 (14)

f o r s o m e Xmi . a n d Xma x s a t i s f y i n g

Xmin ~ /goal ~< Xmax- (15)

Here, Nma x is the u p p e r b o u n d o n the n u m b e r o f users t h a t w o u l d s h a r e t h e resource. T h e c l a i m is t h a t w h e n (14) a n d (15) a r e satisfied, it is i m p o s s i - ble f o r £ x i ( t + 1) = £ x , ( t ) .

L e t us s u p p o s e t h e c o n t r a r y is t r u e f o r the case y = 0. This m e a n s t h a t

a. + b , x i ( t ) < x i ( t ) Vi

w h i c h m e a n s

na I + ( b I - 1)Y.xi(t ) < 0.

Since a~, b 1, a n d all x / s are positive, t h e a b o v e i n e q u a l i t y is p o s s i b l e o n l y if b~ - 1 is n e g a t i v e a n d if so, s u b s t i t u t i n g Xm~ x w h i c h is m o r e t h a n Y.xi(t ) will m a k e the l e f t - h a n d side e v e n m o r e n e g a t i v e :

na I + ( b I - - l ) X m a x < 0 .

T h i s violates (14); t h u s a c o n t r a d i c t i o n w i t h o u r a s s u m p t i o n .

F o r the case y = 1, if all users t r u n c a t e , t h e n it m e a n s

na D+ b D X i ( t ) > x i ( t ) V i ,

t h u s

na o + ( b D - 1 ) ~ x i ( t ) > O.

Since b o is less t h a n 1, the s e c o n d t e r m in t h e l e f t - h a n d side o f t h e a b o v e e q u a t i o n is negative. y = 1 implies 52x~(t) is g r e a t e r t h a n Xgoa l, h e n c e Xmi .. S u b s t i t u t i n g Nma x i n p l a c e o f n, a n d S m i n in p l a c e o f Y.x,(t), s h o u l d m a i n t a i n t h e i n e q u a l i t y . T h a t is, w e m u s t h a v e

Nmaxa o + ( b o - l ) X m i n > 0.

T h i s leads t o a v i o l a t i o n o f (14); t h u s a c o n t r a d i c - tion.

So t h e l i n e a r c o n t r o l s w i t h t r u n c a t i o n leave us w i t h a set o f c o n d i t i o n s w e a k e r t h a n (12) a n d s t r o n g e r t h a n (10):

a l a l > 0 , b l > l -

gmax '

Xmi. 0 ~< a D < (1 -- b D ) Nmax, 0 ~< b D < 1. (16)

N o t i c e t h a t in t h e case t h a t w e d o n o t h a v e a n y k n o w l e d g e t o b o u n d Xgoa, o r n, t h a t s i m p l y c o r r e - s p o n d s t o Nr~x = oo, Xmi . -----0 a n d Xmax= oo. T h e n the c o n d i t i o n s o n l i n e a r c o n t r o l w i t h t r u n c a - t i o n r e d u c e t o the s a m e o n e s as t h o s e o n t h e strictly l i n e a r c o n t r o l . W e h a v e e s s e n t i a l l y p r o v e n the f o l l o w i n g p r o p o s i t i o n s :

Proposition 1. In order to satisfy the requirements of distributed convergence to efficiency and fairness without truncation, the linear decrease policy should be multiplicative, and the linear increase policy should always have an additive component, and optionally it may have a multiplicative component with the coefficient no less than one.

10 D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

Proposition 2. For the linear controls with trunca- tion (as defined m Equation (13)), the increase and decrease policies can each have both additive and multiplicative components, satisfying the constraints in Equations (16) and (15).

T h e vectorial r e p r e s e n t a t i o n in the next section should help illustrate these results further.

2.5. Vectorial Representation of Feasibility Condi- tions

T h e c o n s t r a i n t o n the c o n t r o l i m p o s e d b y the efficiency a n d fairness convergence conditions are depicted in Fig. 7 for the 2-user case. L e t us first consider a p o i n t in the o v e r l o a d e d region. As s h o w n in Fig. 7(a), the users s t a r t at the p o i n t x H = ( x H, x ~ ) , which is a b o v e the efficiency line. T h e system asks the users to decrease. T h e line x I + x 2 = x H + x H represents a n " e q u i - e f f i c i e n c y " line. All p o i n t s o n this line h a v e the s a m e ef- ficiency as x n. F o r convergence to efficiency it is sufficient to ensure t h a t the next decrease m o v e s into the shaded area.

T h e r e q u i r e m e n t o f linear controls a n d dis- tributedness puts a d d i t i o n a l restrictions. L i n e a r c o n t r o l s i m p l y t h a t the new state vector x ( t + 1) is a s u m o f two vectors c o r r e s p o n d i n g to a a n d bx(t). I n two dimensions, a v e c t o r is r e p r e s e n t e d b y a 45 ° line t h r o u g h x ( t ) . This is s h o w n in Fig. 7(b) b y the line m a r k e d b = 1. All future states c o r r e s p o n d i n g to b = 1 lie o n this line. Points to the left o f the line c a n b e r e a c h e d if a n d o n l y if we choose b > 1. Similarly, p o i n t s to the right o f the line c a n b e r e a c h e d if b < 1. T h e second v e c t o r c o r r e s p o n d i n g to b x ( t ) is r e p r e s e n t e d b y the line m a r k e d a = 0 in Fig. 7(b). I f we choose a = 0, the state x ( t + 1) will lie on this line. Points to the left o f this line c a n b e reached b y choosing a < 0. Similarly, p o i n t s to the fight o f this line c a n b e r e a c h e d b y a > 0. D e p e n d i n g u p o n the values o f a a n d b, the set o f r e a c h a b l e states will lie in o n e o f the f o u r regions f o r m e d b y the two lines a = 0 a n d b = 1. O n l y one o f these f o u r regions, the one c o r r e s p o n d i n g to a < 0 a n d b ~< 1, is c o m p l e t e l y below the equi-efficiency line. This region is s h o w n s h a d e d in Fig. 7(b). I f we choose p a r a m e t e r values c o r r e s p o n d i n g to o t h e r regions, the next state can n o t b e g u a r a n t e e d to be always below the equi-ef- ficiency line.

F o r fairness, we n o t e t h a t the p o i n t s b e t w e e n the fairness line a n d the line p a s s i n g t h r o u g h x rt h a v e higher fairness t h a n x H (see Fig. 7(c)). I f we locate the m i r r o r i m a g e o f x H - the p o i n t x r r = (2,xH x H ) - t h i s p o i n t has the s a m e fairness as x H, a n d all p o i n t s b e t w e e n the fairness line a n d the line j o i n i n g x w h a v e higher fairness t h a n x rr. Thus, for c o n v e r g e n c e to fairness, it is sufficient that the n e x t p o i n t b e in the region b o u n d e d b y the two lines j o i n i n g origin to the p o i n t s x n a n d X H'.

C o m b i n i n g the effect o f all the restrictions, the region for distributively converging to efficiency a n d fairness is given b y the intersection o f the regions s h o w n in Fig. 7(b), a n d (c), i.e., b y the line j o i n i n g x H to the origin as s h o w n in Fig. 7(d). T h u s the o n l y policies that w o u l d distributively satisfy the fairness a n d efficiency c o n v e r g e n c e conditions are those that m o v e the o p e r a t i n g p o i n t along this line. I n o t h e r words, the decrease m u s t b e multiplicative.

Similarly, starting with a p o i n t x L = ( x ~ , x2 e) in the u n d e r l o a d e d region, the region for distribu- tively converging to efficiency a n d fairness is given b y the region s h o w n in Fig. 7(e).

E q u a t i o n s (12), (16), a n d (15) are basically the algebraic s t a t e m e n t o f these conditions.

3. Optimizing the Control Schemes

H a v i n g established the feasible c o n t r o l region, the next step is to d e t e r m i n e the o p t i m a l policy - - a policy t h a t takes the s y s t e m to the goal quickly. I n this section, therefore, we discuss the selection o f control p a r a m e t e r s to m i n i m i z e the t i m e to convergence a n d to m i n i m i z e the oscillations.

3.1. Optimal Convergence to Efficiency

I n this subsection, we deal exclusively with the t r a d e o f f o f t i m e to converge to efficiency, te, with the oscillation size, s e. M o r e figuratively, we also refer to these two metrics as responsiveness a n d smoothness, respectively.

T h e n state e q u a t i o n s c o r r e s p o n d i n g for n users are

1)= i = 1 , 2 . . . . . n .

D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks 11

User 2's

Alloc- ation

x2

t x x . (a) Convergenceto a = I0 ~ b = l Efficiency | / 2¢ (b) Distributed

H j ~ " User [ / / / / Convergence

~ 2's Alloc-

/ ation x2

Equi-Efficiency Line

User l's Allocation xl User l's Allocation xt

l / (c) Convergence to l / (d) Distributed Fairness Convergence to

| [ Eff}ciency and / xH I . Fairness Line

User User 2's 2's

Alloc- Alloc- ation ation

x2 x 2

User l's Allocation xl User l's Allocation xl

User 2's

Alloc- ation

x2

(e) Increase

s /

/ J

User l's Allocation x l

Fig. 7. Vectorial representation of efficiency and fairness feasibility conditions.

12 D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

T h e s e n equations c a n b e a d d e d to f o r m a single state equation:

E x , ( t + 1) = na + b E x , ( t )

This is in fact the f o r m o f the c o n t r o l we are p r o p o s i n g for o u r congestion a v o i d a n c e schemes [10,11].

or,

X ( t + 1) = na + b X ( t ) where X = ~.x,.

G i v e n initial state X(0), the time to reach Xgoa I is

I an + (b - 1) Xgoa z

t e = l o g ( b ) , b > 0 ,

Xgoa, - X ( 0 ) , b = 0. an

A f t e r converging to Xgoa I there will b e a m a x i m u m o v e r s h o o t o f

se= lan + ( b - 1 ) g g o a , I.

N o t i c e that t e is a m o n o t o n i c a l l y decreasing func- tion o f a a n d b, while se is a m o n o t o n i c a l l y increasing f u n c t i o n o f a a n d b. Thus, a n y a t t e m p t to increase responsiveness (decrease te) also re- suits in decreased s m o o t h n e s s (increased s~), a n d vice versa.

3.2. Optimal Convergence to Fairness

E q u a t i o n (7) shows t h a t the p e r step i m p r o v e - m e n t in fairness F ( x ( t - 1)) - F ( x ( t ) ) is a m o n o - tonically increasing function o f c = a/b. Thus, larger values o f a a n d smaller values b give quicker convergence to fairness.

F o r the case o f strict linear controls, this leads to a n elegantly simple conclusion. F o r decrease, feasibility conditions required a D = 0. Thus, the fairness r e m a i n s the s a m e at every decrease step a n d the p a r a m e t e r b D has n o effect o n t i m e to c o n v e r g e to a fair state. F o r increase, smaller b I results in quicker convergence to fairness. Thus, the o p t i m a l value o f bl is its m i n i m u m v a l u e - - o n e . (See E q u a t i o n (12).) Choosing b~ = 1 is equivalent to saying t h a t additive increase gives us the quick- est convergence to fairness. This result c a n b e f o r m a l l y stated as:

Proposition 3. For both feasibifity and optimal con- vergence to fairness, the increase poficy should be additive and the decrease policy should be multi- pficative.

4. Nonlinear Controls

In this section, we explore the b e h a v i o u r o f certain n o n l i n e a r controls. I n particular, we show h o w they c a n b e r e p r e s e n t e d b y the v e c t o r di- a g r a m s as in the case for linear controls. This technique again gives a n intuitive feeling a b o u t h o w n o n l i n e a r controls work. T h e detailed analy- sis of n o n l i n e a r c o n t r o l s is b e y o n d the scope o f this p a p e r . H o w e v e r , we will explain why we con- sider such n o n l i n e a r controls n o t suitable for p r a c - tical purposes.

Let us consider in general state transition e q u a - tions that are expressible as a p o w e r o f the state:

x i ( t + 1) = x i ( t ) + a ( x i ( t ) ) k,

or, in t e r m s o f control,

u i ( t ) k

where k c a n b e a n y integer (positive, negative o r zero), a n d a is a n o r m a l i z a t i o n c o n s t a n t t h a t defines the step size a n d sign. N o t e t h a t k = 0 gives the additive policy a n d k = 1 gives the multi- plicative policy.

N o w let us consider the two user v e c t o r r e p r e - sentation for these controls. I n Fig. 8 we first show the efficiency a n d fairness lines as before. C o n s i d e r the p o i n t x L'. L e t O(k) b e the slope o f u(t). T h e n we k n o w 0(0) is 45 ° a n d 0(1) is the s a m e as the slope for the initial state x(t). A s k tends to infinity, O(k) tends to 0 ° a n d as k tends to negative infinity, O(k) tends to 90 o

Since fairness requires t h a t the slope o f the n e w state x ( t + 1) b e closer to 45 ° t h a n t h a t o f the initial state x ( t ) , we m u s t h a v e k ~< 1 (negative k is fine).

Slopes for o t h e r three possibilites x L, x ~, a n d x n ' are shown in the figure a n d can b e similarly explained. Considering all f o u r possibilities we see t h a t the feasibility condition requires k ~< 1 for increase a n d k >~ 1 for decrease (with at least o n e inequality b e i n g strict), a n d a p p r o p r i a t e values for a so the sign a n d step size are correct. T h e ad- ditive increase a n d multiplicative decrease control, for example, clearly satisfies this general condi- tion.

D.-M. Chiu, R. Jam / Congestion Avoidance in Computer Networks 13

x H

Us er l / ~ ~" .,sl ,"

All°c-I /T/'~N J

User l ' s Allocation xl

Fig. 8. Vectorial r e p r e s e n t a t i o n for n o n l i n e a r controls.

A nonlinear control could generally include m o r e c o m p o n e n t s with different slopes:

u i ( t ) = ~ c t k ( x k ( t ) ) k. k = --oo

T h e n the sum of the c o m p o n e n t s must have a slope satisfying the above condition.

A l t h o u g h nonlinear controls offer us far m o r e flexibility in trying to direct towards fairness, it also complicates the task of finding the right scaling factors, represented b y ag in the above equation. These p a r a m e t e r s usually must be cho- sen relative to system parameters, such as the capacity Xgoa I and m a x i m u m n u m b e r of users Nm~ ,. Being too sensitive to system parameters reduces the robustness of the control. F o r this reason we spent less effort in exploring nonlinear controls, W e will discuss the robustness question m o r e in the next section.

5. Practical Considerations

T h e p r o b l e m studied in this r e p o r t is a generic, b u t also highly abstracted problem. In o r d e r to a p p l y the results to solve the decentralized conges- tion control p r o b l e m in real networks, m a n y prac- tical issues must be taken into considerations. We briefly discuss some of them here.

O n e general principle in choosing an algorithm in a general architecture is to be i n d e p e n d e n t of

h ard w are a n d software scales or parameters as m u c h as possible. T h e reason being that in a co m p l ex system, scaling p a r a m e t e r s are n o t easily gathered in an a u t o m a t i c fashion and, thus, re- quire h u m a n help to configure. H a v i n g algorithms d e p e n d o n system scales would co m p l i cat e the configuration task an d m ak e the algorithm m o r e vulnerable to h u m a n error. While in this r e p o r t we have discussed optimizing the c o n t r o l scheme according to certain criteria, practical considera- tion m a y dictate that the c o n t r o l be chosen for the widest range o f values o f system parameters. As we indicated earlier, the n o n l i n ear controls t e n d to b e m o re sensitive to the system p a r a m e t e r s and, thus, are less likely to b e useful in practice.

A n o t h e r possible co n st rai n t is t h at the resource and thus the allocations must be integral. F o r example buffers an d windows are all m e a s u r e d in integers. Simple r o u n d i n g o f f to the nearest integer m a y cause violation o f the various convergence conditions.

Ease o f i m p l e m e n t a t i o n could also affect the choice of the controls. F o r example, the n u m b e r o f multiplications or e x p o n e n t i a t i o n s required to i m p l em en t a co n t ro l would i m p a c t o n the minimal h ard w are required.

5.1. Further Questions

T h e r e are m a n y fu rt h er questions w o r t h explor- ing in c o n j u n c t i o n to this problem. In particular, the following are i m p o r t a n t :

(1) How does delayed feedback affect the control? In practice there is invariably some delays b efo re the feedback arrives at the controller. As the d el ay lengthens, the feed b ack b e c o m e s less an d less use- ful, an d the p e r f o r m a n c e worsens. It would be valuable to have q u an t i t at i v e assessment o f h o w the p e r f o r m a n c e degrades.

(2) What is the marginal utility of increased bits of feedback? T h e b i n a r y feed b ack is the simplest. A d d i n g additional feedback signals m a y help to cut d o w n the oscillations. A f o r m a l analysis would allow an assessment o f the t r a d e o f f o f p erfo r- m an ce versus complexity.

(3) Is it worthwhile to guess the current number of users n? Users c o m e an d go d y n am i cal l y and the n u m b e r changes b y integral values. A se- q u en ce o f increase signals m a y indicate the reduc- tion in the n u m b e r o f users f r o m n to n - 1. If n were k n o w n or b o u n d e d , sources could p red i ct

14 D.-M. Chiu, R. Jain / Congestion Avoidance in Computer Networks

n - 1 a n d r e q u e s t t h a t level o f r e s o u r c e s r i g h t a w a y . A w r o n g g u e s s m a y m a k e t h e s y s t e m less s t a b l e . T h i s a l s o d e s e r v e s f u r t h e r s t u d y .

(4) W h a t i s t h e i m p a c t o f a s y n c h r o n o u s o p e r - a t i o n ? T h e a l g o r i t h m d e s c r i b e d in t h e p a p e r is i n t r i n s i c a l l y a s y n c h r o n o u s a l g o r i t h m . I n o t h e r w o r d s , it is a s s u m e d t h a t a l l u s e r s s t a r t f r o m a n i n i t i a l s t a t e a n d f o l l o w t h r o u g h c o m m o n p h a s e s o f c o m p u t a t i o n a n d f e e d b a c k . W h e n t h e f r e q u e n c y o f f e e d b a c k is d i f f e r e n t o r w h e n t h e t i m e d e l a y o f f e e d b a c k is d r a s t i c a l l y d i f f e r e n t , t h e n t h e c o n v e r - g e n c e p r o p e r t i e s c a n n o t b e g u a r a n t e e d . T h i s t o p i c is c u r r e n t l y u n d e r f u r t h e r s t u d y .

6. Summary of Results

C o n g e s t i o n a v o i d a n c e s c h e m e s a l l o w a n e t w o r k t o o p e r a t e i n t h e o p t i m a l r e g i o n o f l o w d e l a y a n d h i g h t h r o u g h p u t . T h i s is a c h i e v e d v i a t h e n e t w o r k m o n i t o r i n g its l o a d l e v e l a n d a s k i n g t h e u s e r s t o i n c r e a s e o r d e c r e a s e t h e l o a d a s a p p r o p r i a t e . I n t h i s p a p e r , w e e x a m i n e d t h e u s e r i n c r e a s e / d e - c r e a s e p o l i c i e s u n d e r t h e c o n s t r a i n t s t h a t t h e f e e d b a c k f r o m t h e s y s t e m is l i m i t e d t o a s i n g l e b i t , w h i c h t e l l s w h e t h e r t h e c u r r e n t l o a d is a b o v e o r b e l o w t h e g o a l .

W e f o r m u l a t e d a set o f c o n d i t i o n s t h a t a n y i n c r e a s e / d e c r e a s e p o l i c y s h o u l d s a t i s f y t o e n s u r e c o n v e r g e n c e t o e f f i c i e n t a n d f a i r s t a t e i n a d i s t r i b - u t e d m a n n e r . I n p a r t i c u l a r , w e s h o w e d t h a t t h e d e c r e a s e m u s t b e m u l t i p l i c a t i v e t o e n s u r e t h a t a t e v e r y s t e p t h e f a i r n e s s e i t h e r i n c r e a s e s o r s t a y s t h e s a m e a s t h a t t h e t h e c u r r e n t o p e r a t i n g p o i n t . W e d e r i v e d t h e s u f f i c i e n t c o n d i t i o n s a n a l y t i c a l l y a n d t h e n e x p l a i n e d t h e m u s i n g a v e c t o r r e p r e s e n t a t i o n .

O p t i m i z a t i o n c o n s i d e r a t i o n s r e q u i r e t h a t t h e c h a n g e in e f f i c i e n c y a n d f a i r n e s s b e m a x i m i z e d in e v e r y f e e d b a c k c y c l e . U s i n g t h e s e c o n s i d e r a t i o n s w e s h o w e d t h a t a d d i t i v e i n c r e a s e w i t h m u l t i p l i c a - t i v e d e c r e a s e is t h e o p t i m a l p o l i c y . T h i s is t h e p o l i c y f i n a l l y c h o s e n f o r i m p l e m e n t a t i o n i n t h e c o n g e s t i o n a v o i d a n c e s c h e m e r e c o m m e n d e d f o r D i g i t a l N e t w o r k i n g A r c h i t e c t u r e a n d O S I T r a n s - p o r t C l a s s 4 N e t w o r k s .

Acknowledgment

M a n y m e m b e r s o f t h e D i g i t a l ' s n e t w o r k i n g a r c h i t e c t u r e a n d i m p l e m e n t a t i o n g r o u p s c o n t r i b -

u t e d t o t h e c o n g e s t i o n a v o i d a n c e p r o j e c t . T h e a n a l y s i s i n t h e p a p e r b e n e f i t e d i n p a r t i c u l a r f r o m t h e s u p p o r t a n d i n p u t f r o m T o n y L a u c k , J o h n H a r p e r , a n d W i l l i a m H a w e .

References

[1] D.P. Bertsekas, Distributed Asynchronous Computation of Fixed Points, Mathematical Programming 27 (1983) 107-120.

[2] E. Gafni and D. Bertsekas, Dynamic Control of Session Input Rates in Communication Networks, in: Proc. M 1 L C O M "82, Boston, MA, MIT Technical Report LIDS-P-1228, 1982.

[3] H. Hayden, Voice Flow Control in Integrated Packet Networks, MIT, M.S. Thesis, MIT Technical Report LIDS-TH-1152, 1981.

[4] ISO 8073: Information Processing Systems - Open Sys- tems Interconnection - - Connection Oriented Transport Protocol Specification, International Organization for Standardization, Ref. no. ISO 8073-1986 (E)), 1986.

[5] J.M. Jaffe, Bottleneck Flow Control, I E E E Transactions on Communications 29 (7) (1981) 954-962.

[6] R. Jain, D.M. Chiu and W. Hawe. A Quantitative Mea- sure of Fairness and Discrimination for Resource Alloc- ation in Shared Systems, Technical Report, Digital Equipment Corporation, DEC-TR-301, 1984.

[7] R. Jain and K.K. Ramakrishnan, Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals and Methodology, in: Proc. Com- puter Networking Symposium, Washington, DC (1988) 134-143.

[8] R. Jain, K.K. Ramakrishnan and D.M. Chiu, Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Technical Report DEC-TR-506, Digital Equipment Corporation, 1987. Also in: C. Partridge, ed., Innovations in Internetworking (Artech House, Norwood, MA, 1988) 140-156.

[9] J. Mosely, Asynchronous Distributed Flow Control Algorithms, MIT, Ph.D. Thesis, MIT Technical Report LIDS-TH-1415, 1984.

[10] K.K. Ramakrishnan, D.M. Chiu and R. Jain, Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part IV-A Selective Binary Feedback Scheme for General Topologies, Technical Report DEC- TR-509, Digital Equipment Corporation, 1987.

[11] K.K. Ramakrishnan and R. Jain, A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer, in: Proc. A C M S I G C O M M ' 8 8 (1988).

[12] B.A. Sanders, An Incentive Compatible Flow Control Algorithm for Fair Rate Allocation in Computer/Com- munication Networks, 6th International Conference on Distributed Computing Systems, Cambridge, MA (1986).