Research paper summary

CallmeBOND

red.pdf

Home >Computer Science homework help >Research paper summary

RandomEarly DetectionGatewaysfor CongestionAvoidance

Sally Floyd andVanJacobson �

LawrenceBerkeley Laboratory Universityof California

[email protected] [email protected]

To appearin theAugust1993IEEE/ACM Transactionson Networking

Abstract

This paperpresentsRandomEarly Detection(RED) gate- ways for congestionavoidancein packet-switchednet- works. Thegateway detectsincipientcongestionby com- puting the averagequeuesize. The gateway could notify connectionsof congestioneitherby droppingpacketsar- riving at thegateway or by settinga bit in packet headers. Whenthe averagequeuesizeexceedsa presetthreshold, the gateway dropsor markseacharriving packet with a certainprobability, wherethe exact probability is a func- tion of theaveragequeuesize.

RED gatewayskeeptheaveragequeuesizelow while allowing occasionalburstsof packetsin thequeue.During congestion,theprobabilitythatthegateway notifiesa par- ticular connectionto reduceits window is roughlypropor- tional to thatconnection’s shareof thebandwidththrough thegateway. RED gatewaysaredesignedto accompany a transport-layercongestioncontrol protocol suchas TCP. The RED gateway hasno bias againstbursty traffic and avoids the global synchronizationof many connections decreasingtheir window at thesametime. Simulationsof a TCP/IP network are usedto illustrate the performance of RED gateways.

1 Intr oduction

In high-speednetworkswith connectionswith largedelay- bandwidthproducts,gateways are lik ely to be designed with correspondinglylarge maximumqueuesto accom- modatetransientcongestion.In the currentInternet,the TCPtransportprotocoldetectscongestiononly afterapacket hasbeendroppedatthegateway. However, it wouldclearly beundesirableto have largequeues(possiblyon theorder�

This work was supportedby the Director, Office of Energy Re- search,Scientific ComputingStaff, of the U.S. Departmentof Energy underContractNo. DE-AC03-76SF00098.

of a delay-bandwidthproduct)that werefull muchof the time; this would significantly increasethe averagedelay in the network. Therefore,with increasinglyhigh-speed networks,it is increasinglyimportantto have mechanisms thatkeepthroughputhigh but averagequeuesizeslow.

In the absenceof explicit feedbackfrom the gateway, there are a numberof mechanismsthat have beenpro- posedfor transport-layerprotocolsto maintainhighthrough- put andlow delayin thenetwork. Someof theseproposed mechanismsaredesignedto work with currentgateways [15, 23, 31, 33, 34], while other mechanismsare cou- pledwith gateway schedulingalgorithmsthatrequireper- connectionstatein thegateway [20, 22]. In theabsenceof explicit feedbackfrom thegateway, transport-layerproto- colscouldinfer congestionfrom theestimatedbottleneck servicetime, from changesin throughput,from changes in end-to-enddelay, aswell asfrom packet dropsor other methods.Nevertheless,the view of anindividual connec- tion is limited by the timescalesof the connection,the traffic patternof the connection,the lack of knowledge of the numberof congestedgateways,the possibilitiesof routing changes,aswell asby otherdifficulties in distin- guishingpropagationdelayfrom persistentqueueingde- lay.

The mosteffective detectionof congestioncanoccur in the gateway itself. The gateway can reliably distin- guishbetweenpropagationdelayandpersistentqueueing delay. Only the gateway hasa unified view of the queue- ing behavior over time; the perspective of individual con- nectionsis limited by the packet arrival patternsfor those connections.In addition,a gateway is sharedby many ac- tive connectionswith a wide rangeof roundtriptimes,tol- erancesof delay, throughputrequirements,etc.;decisions aboutthe durationandmagnitudeof transientcongestion to beallowedat thegateway arebestmadeby thegateway itself.

The methodof monitoring the averagequeuesize at

thegateway, andof notifying connectionsof incipientcon- gestion,is basedof the assumptionthat it will continue to be useful to have queuesat the gateway where traf- fic from a numberof connectionsis multiplexedtogether, with FIFO scheduling.Not only is FIFO schedulinguse- ful for sharingdelayamongconnections,reducingdelay for a particularconnectionduringits periodsof burstiness [4], but it scaleswell andis easyto implementefficiently. In an alternateapproach,somecongestioncontrol mech- anismsthat usevariantsof Fair Queueing[20] or hop-by- hop flow control schemes[22] proposethat the gateway schedulingalgorithmmake useof per-connectionstatefor every active connection. We would suggestinsteadthat per-connectiongateway mechanismsshouldbe usedonly in thosecircumstanceswheregateway schedulingmecha- nismswithout per-connectionmechanismsareclearly in- adequate.

The DECbit congestionavoidancescheme[18], de- scribedlater in this paper, is an early example of con- gestiondetectionat the gateway; DECbit gateways give explicit feedbackwhenthe averagequeuesizeexceedsa certain threshold. This paperproposesa different con- gestionavoidancemechanismat the gateway, RED (Ran- dom Early Detection)gateways,with somewhat different methodsfor detectingcongestionandfor choosingwhich connectionsto notify of this congestion.

While the principlesbehindRED gatewaysarefairly general,and RED gateways can be useful in controlling theaveragequeuesizeevenin a network wherethetrans- port protocol can not be trustedto be cooperative, RED gatewaysare intendedfor a network wherethe transport protocolrespondsto congestionindicationsfrom the net- work. Thegatewaycongestioncontrolmechanismin RED gatewayssimplifiesthecongestioncontroljob requiredof thetransportprotocol,andshouldbeapplicableto transport- layer congestioncontrol mechanismsother than the cur- rent versionof TCP, including protocolswith rate-based ratherthanwindow-basedflow control.

However, someaspectsof RED gatewaysarespecifi- cally targetedto TCP/IPnetworks. The RED gateway is designedfor a network wherea singlemarkedor dropped packet is sufficient to signal the presenceof congestion to the transport-layerprotocol. This is differentfrom the DECbit congestioncontrol scheme,wherethe transport- layer protocol computesthe fraction of arriving packets thathave thecongestionindicationbit set.

In addition,the emphasison avoiding the global syn- chronizationthatresultsfrom many connectionsreducing their windowsat thesametime is particularlyrelevantin a network with 4.3-TahoeBSD TCP [14], whereeachcon- nectiongoesthroughSlow-Start,reducingthe window to one,in responseto a droppedpacket. In the DECbit con- gestioncontrolscheme,for example,whereeachconnec- tion’s responseto congestionis lesssevere,it is alsoless

critical to avoid this globalsynchronization. RED gatewayscanbeusefulin gatewayswith a range

of packet-schedulingandpacket-droppingalgorithms.For example,RED congestioncontrol mechanismscould be implementedin gatewayswith droppreference,wherepack- etsaremarkedaseither“essential”or “optional”, and“op- tional” packetsaredroppedfirst whenthequeueexceedsa certainsize.Similarly, for a gateway with separatequeues for realtimeand non-realtimetraffic, for example,RED congestioncontrol mechanismscould be applied to the queuefor oneof thesetraffic classes.

TheRED congestioncontrolmechanismsmonitorthe averagequeuesizefor eachoutputqueue,and,usingran- domization,chooseconnectionsto notify of that conges- tion. Transientcongestionis accommodatedby a tem- poraryincreasein the queue.Longer-li ved congestionis reflectedby an increasein the computedaveragequeue size, and resultsin randomizedfeedbackto someof the connectionsto decreasetheir windows. The probability that a connectionis notified of congestionis proportional to that connection’s shareof the throughputthroughthe gateway.

Gatewaysthatdetectcongestionbeforethequeueover- flows are not limited to packet drops as the methodfor notifying connectionsof congestion.RED gatewayscan mark a packet by droppingit at the gateway or by setting a bit in thepacket header, dependingon thetransportpro- tocol. Whenthe averagequeuesizeexceedsa maximum threshold,the RED gateway marksevery packet that ar- rives at the gateway. If RED gateways mark packets by droppingthem, ratherthan by settinga bit in the packet header, when the averagequeuesize exceedsthe maxi- mum threshold,thenthe RED gateway controlsthe aver- agequeuesizeevenin theabsenceof a cooperatingtrans- port protocol.

Oneadvantageof a gateway congestioncontrolmech- anismthatworkswith currenttransportprotocols,andthat doesnot requirethat all gatewaysin the internetusethe samegateway congestioncontrol mechanism,is that it couldbe deployedgraduallyin the currentInternet.RED gateways are a simple mechanismfor congestionavoid- ancethatcouldbeimplementedgraduallyin currentTCP/IP networkswith no changesto transportprotocols.

Section2 discussesprevious researchon Early Ran- domDrop gatewaysandothercongestionavoidancegate- ways.Section3 outlinesdesignguidelinesfor RED gate- ways.Section4 presentstheRED gateway algorithm,and Section5 describessimple simulations. Section6 dis- cussesin detailthe parametersusedin calculatingthe av- eragequeuesize, and Section7 discussesthe algorithm usedin calculatingthepacket-markingprobability.

Section8 examinestheperformanceof REDgateways, including the robustnessof RED gateways for a range of traffic and for a rangeof parametervalues. Simula-

tions in Section9 demonstrate,amongother things, the RED gateway’s lack of bias againstbursty traffic. Sec- tion 10 describeshow RED gatewayscanbeusedto iden- tify thoseusersthatareusinga largefractionof theband- width througha congestedgateway. Section11 discusses methodsfor efficiently implementingREDgateways.Sec- tion 12 gives conclusionsand describesareasfor future work.

2 Previouswork on congestionavoid- ancegateways

2.1 Early Random Dr op gateways

SeveralresearchershavestudiedEarlyRandomDropgate- ways as a methodfor providing congestionavoidanceat thegateway.1

Hashem[11] discussessomeof the shortcomingsof RandomDrop2 and Drop Tail gateways, and briefly in- vestigatesEarly RandomDrop gateways. In the imple- mentationof Early RandomDrop gatewaysin [11], if the queuelength exceedsa certaindrop level, thenthe gate- way dropseachpacketarriving at thegatewaywith a fixed drop probability. This is discussedas a roughinitial im- plementation.Hashem[11] stressesthat in future imple- mentationsthe drop level andthe drop probabilityshould beadjusteddynamically, dependingon network traffic.

Hashem[11] pointsout that with Drop Tail gateways eachcongestionperiodintroducesglobalsynchronization in the network. When the queueoverflows, packets are often droppedfrom several connections,and thesecon- nectionsdecreasetheir windows at the sametime. This resultsin a lossof throughputat the gateway. The paper shows that Early RandomDrop gatewayshave a broader view of traffic distribution thando Drop Tail or Random Drop gateways and reduceglobal synchronization.The papersuggeststhat becauseof this broaderview of traf- fic distribution, Early RandomDrop gatewayshave a bet- ter chancethan Drop Tail gateways of targeting aggres- sive users.Theconclusionsin [11] arethatEarly Random Drop gatewaysdeserve furtherinvestigation.

For the versionof Early RandomDrop gatewaysused in the simulationsin [36], if the queueis morethanhalf

1Jacobson[14] proposedgatewaysto monitortheaveragequeuesize to detectincipientcongestion,andto randomlydrop packetswhencon- gestionis detected.Theseproposedgatewaysarea precursorto theEarly RandomDrop gateways that have beenstudiedby several authors[11] [36]. We refer to the gatewaysin this paperasRandomEarly Detection or RED gateways. RED gatewaysdiffer from the earlierEarly Random Drop gatewaysin several respects:the average queuesizeis measured; the gateway is not limited to droppingpackets; andthe packet-marking probabilityis a functionof theaveragequeuesize.

2With RandomDrop gateways,whena packet arrivesat thegateway andthe queueis full, the gateway randomlychoosesa packet from the gateway queueto drop.

full thenthegatewaydropseacharriving packetwith prob- ability 0.02. Zhang[36] shows that this versionof Early RandomDrop gatewayswasnot successfulin controlling misbehaving users.In thesesimulations,with both Ran- dom Drop and Early RandomDrop gateways, the mis- behaving usersreceived roughly 75% higher throughput thantheusersimplementingstandard4.3 BSD TCP.

TheGateway CongestionControlSurvey [21] consid- ersthe versionsof Early RandomDrop describedabove. The survey cites the resultsin which the Early Random Drop gateway is unsuccessfulin controllingmisbehaving users[36]. As mentionedin [32], Early RandomDrop gateways are not expectedto solve all of the problems of unequalthroughputgiven connectionswith different roundtriptimesandmultiple congestedgateways.In [21], thegoalsof Early RandomDrop gatewaysfor congestion avoidanceare describedas “uniform, dynamictreatment of users(streams/flows), of low overhead,and of good scalingcharacteristicsin largeandloadednetworks”. It is left asanopenquestionwhetheror not thesegoalscanbe achieved.

2.2 Other approachesto gatewaymechanisms for congestionavoidance

Early descriptionsof IP SourceQuenchmessagessug- gestthat gateways could sendSourceQuenchmessages to sourcehosts before the buffer spaceat the gateway reachescapacity[26], andbeforepacketshaveto bedropped at the gateway. Oneproposal[27] suggeststhat the gate- way sendSourceQuenchmessageswhenthe queuesize exceedsacertainthreshold,andoutlinesapossiblemethod for flow control at the sourcehostsin responseto these messages.Theproposalalsosuggeststhatwhenthegate- way queuesizeapproachesthe maximumlevel the gate- way coulddiscardarriving packetsotherthanICMP pack- ets.

The DECbit congestionavoidancescheme,a binary feedbackschemefor congestionavoidance,is described in [29]. In theDECbitschemethegatewayusesacongestion- indicationbit in packet headersto provide feedbackabout congestionin the network. When a packet arrivesat the gateway, the gateway calculatesthe averagequeuelength for the last (busy + idle) periodplus the currentbusy pe- riod. (Thegateway is busywhenit is transmittingpackets, and idle otherwise.)Whenthe averagequeuelength ex- ceedsone,thenthegatewaysetsthecongestion-indication bit in thepacket headerof arriving packets.

The sourceuseswindow flow control,andupdatesits window onceevery two roundtriptimes.If at leasthalf of the packetsin the last window hadthe congestionindica- tion bit set, then the window is decreasedexponentially. Otherwise,thewindow is increasedlinearly.

ThereareseveralsignificantdifferencesbetweenDECbit

gatewaysand the RED gatewaysdescribedin this paper. Thefirst differenceconcernsthemethodof computingthe averagequeuesize. Becausethe DECbit schemechooses the last (busy + idle) cycle plus the currentbusy period for averagingthe queuesize, the queuesize can some- times be averagedover a fairly short period of time. In high-speednetworks with large buffers at the gateway, it would be desirableto explicitly control the time constant for thecomputedaveragequeuesize;this is donein RED gatewaysusingtime-basedexponentialdecay. In [29] the authorsreport that they rejectedthe idea of a weighted exponentialrunningaverageof the queuelengthbecause when the time interval was far from the roundtrip time, therewasbiasin the network. This problemof biasdoes not arisewith RED gatewaysbecauseRED gatewaysuse a randomizedalgorithmfor markingpackets,andassume that the sourcesusea differentalgorithm for responding to markedpackets.In a DECbit network, thesourcelooks at thefractionof packetsthathave beenmarkedin thelast roundtrip time. For a network with RED gateways, the sourceshouldreduceits window evenif thereis only one markedpacket.

A seconddifferencebetweenDECbit gateways and RED gatewaysconcernsthemethodfor choosingconnec- tions to notify of congestion.In the DECbit schemethere is no conceptualseparationbetweenthe algorithmto de- tectcongestionandthealgorithmto setthecongestionin- dicationbit. Whena packet arrivesat thegateway andthe computedaveragequeuesizeis too high, the congestion indicationbit is setin the headerof that packet. Because of this methodfor markingpackets,DECbit networkscan exhibit a biasagainstbursty traffic [seeSection9]; this is avoidedin RED gatewaysby usingrandomizationin the methodfor marking packets. For congestionavoidance gatewaysdesignedto work with TCP, an additionalmoti- vationfor usingrandomizationin themethodfor marking packetsis to avoid the global synchronizationthat results from many TCPconnectionsreducingtheir window at the sametime. This is lessof a concernin networks with the DECbit congestionavoidancescheme,whereeachsource decreasesits window fairly moderatelyin responseto con- gestion.

Anotherproposalfor adaptivewindow schemeswhere the sourcenodesincreaseor decreasetheir windows ac- cording to feedbackconcerningthe queuelengthsat the gatewaysis presentedin [25]. Eachgateway hasanupper thresholdUT indicatingcongestion,anda lowerthreshold LT indicatinglight loadconditions.Informationaboutthe queuesizesat the gateways is addedto eachpacket. A sourcenodeincreasesits window only if all the gateway queuelengthsin the patharebelow the lower thresholds. If the queuelength is above the upperthresholdfor any queuealong the path,then the sourcenodedecreasesits window. Onedisadvantageof this proposalis thatthenet-

work respondsto the instantaneousqueuelengths,not to the averagequeuelengths. We believe that this scheme would be vulnerableto traffic phaseeffectsandto biases againstbursty traffic, and would not accommodatetran- sientincreasesin the queuesize.

3 Designguidelines

This sectionsummarizessomeof the designgoals and guidelinesfor RED gateways.Themaingoalis to provide congestionavoidanceby controlling the averagequeue size. Additional goals include the avoidanceof global synchronizationandof a biasagainstburstytraffic andthe ability to maintainan upperboundon the averagequeue size even in the absenceof cooperationfrom transport- layerprotocols.

The first job of a congestionavoidancemechanismat the gateway is to detectincipient congestion.As defined in [18], a congestionavoidanceschememaintainsthenet- work in a region of low delayandhigh throughput.The averagequeuesizeshouldbe kept low, while fluctuations in the actualqueuesize shouldbe allowed to accommo- datebursty traffic and transientcongestion.Becausethe gateway canmonitor the sizeof the queueover time, the gateway is the appropriateagentto detectincipient con- gestion. Becausethe gateway hasa unified view of the varioussourcescontributing to this congestion,the gate- way is alsothe appropriateagentto decidewhich sources to notify of this congestion.

In anetwork with connectionswith arangeof roundtrip times, throughputrequirements,and delay sensitivities, thegateway is themostappropriateagentto determinethe sizeanddurationof short-livedburstsin queuesizeto be accommodatedby the gateway. The gateway cando this by controllingthetime constantsusedby thelow-passfil- ter for computingthe averagequeuesize.Thegoal of the gatewayis to detectincipientcongestionthathaspersisted for a “long time” (severalroundtriptimes).

The secondjob of a congestionavoidancegateway is to decidewhich connectionsto notify of congestionat the gateway. If congestionis detectedbefore the gate- way buffer is full, it is not necessaryfor the gateway to drop packetsto notify sourcesof congestion.In this pa- per, we saythat the gateway marksa packet, andnotifies thesourceto reducethewindow for thatconnection.This markingandnotificationcanconsistof droppinga packet, settinga bit in a packet header, or someothermethodun- derstoodby the transportprotocol. The currentfeedback mechanismin TCP/IPnetworksis for thegateway to drop packets,andthe simulationsof RED gatewaysin this pa- perusethis approach.

Onegoal is to avoid a biasagainstburstytraffic. Net- workscontainconnectionswith a rangeof burstiness,and

gatewayssuchas Drop Tail andRandomDrop gateways have a bias againstbursty traffic. With Drop Tail gate- ways, the more bursty the traffic from a particularcon- nection,the morelik ely it is that the gateway queuewill overflow whenpacketsfrom that connectionarrive at the gateway [7].

Anothergoal in decidingwhich connectionsto notify of congestionis to avoid the global synchronizationthat resultsfrom notifying all connectionsto reducetheir win- dows at the sametime. Global synchronizationhasbeen studiedin networkswith Drop Tail gateways[37], andre- sults in lossof throughputin the network. Synchroniza- tion as a generalnetwork phenomenahasbeenexplored in [8].

In orderto avoid problemssuchasbiasesagainstbursty traffic and global synchronization,congestionavoidance gateways can use distinct algorithmsfor congestionde- tection and for decidingwhich connectionsto notify of this congestion.TheRED gateway usesrandomizationin choosingwhicharriving packetsto mark;with thismethod, theprobabilityof markinga packet from a particularcon- nectionis roughly proportionalto that connection’s share of the bandwidththroughthe gateway. This methodcan beefficiently implementedwithoutmaintainingper-connection stateat thegateway.

One goal for a congestionavoidancegateway is the ability to control the averagequeuesize even in the ab- senceof cooperatingsources. This can be done if the gateway drops arriving packets when the averagequeue size exceedssomemaximumthreshold(ratherthan set- ting a bit in the packet header). This methodcould be usedto control the averagequeuesize even if mostcon- nectionslast less than a roundtrip time (as could occur with modified transportprotocolsin increasinglyhigh- speednetworks), and even if connectionsfail to reduce their throughputin responseto marked or droppedpack- ets.

4 The RED algorithm

This sectiondescribesthe algorithm for RED gateways. The RED gateway calculatesthe averagequeuesize,us- ing a low-passfilter with an exponentialweightedmov- ing average.The averagequeuesizeis comparedto two thresholds,a minimumthresholdand a maximumthresh- old. When the averagequeuesize is lessthan the min- imum threshold,no packets are marked. When the av- eragequeuesizeis greaterthanthe maximumthreshold, every arriving packet is marked. If marked packetsarein fact dropped,or if all sourcenodesare cooperative, this ensuresthat the averagequeuesizedoesnot significantly exceedthemaximumthreshold.

When the averagequeuesize is betweenthe mini-

mum and the maximumthreshold,eacharriving packet is marked with probability �� , where�� is a function of the averagequeuesize �� . Eachtime that a packet is marked, the probability that a packet is marked from a particularconnectionis roughly proportionalto that con- nection’s shareof thebandwidthat thegateway. Thegen- eralRED gateway algorithmis givenin Figure1.

for each packet arrival calculate the average queue size �� if � ��

calculate probability �� with probability �� :

mark the arriving packet else if � ��

mark the arriving packet

Figure1: Generalalgorithmfor RED gateways.

Thus the RED gateway hastwo separatealgorithms. Thealgorithmfor computingtheaveragequeuesizedeter- minesthe degreeof burstinessthat will be allowed in the gateway queue.The algorithmfor calculatingthe packet- markingprobability determineshow frequentlythe gate- way markspackets,giventhe currentlevel of congestion. Thegoalis for thegatewayto markpacketsatfairly evenly- spacedintervals, in order to avoid biasesand to avoid global synchronization,and to mark packets sufficiently frequentlyto controltheaveragequeuesize.

The detailedalgorithmfor the RED gateway is given in Figure 2. Section11 discussesefficient implementa- tionsof thesealgorithms.

The gateway’s calculationsof the averagequeuesize take into accounttheperiodwhenthequeueis empty(the idle period)by estimatingthe number� of smallpackets that could have beentransmittedby the gateway during the idle period. After the idle period the gateway com- putesthe averagequeuesizeas if � packetshadarrived to anemptyqueueduringthatperiod.

As �� variesfrom �� to � �� , thepacket-marking probability ��! varieslinearly from 0 to � ��#" :� !%$ � �� "#& �� (')�� *,+ & � ��-')�� */. The final packet-markingprobability �� increasesslowly asthe countincreasessincethelast markedpacket:� � $ ��! + &10 ')24365��798 ��! * As discussedin Section7, this ensuresthat the gateway doesnot wait too long beforemarkinga packet.

Thegatewaymarkseachpacketthatarrivesatthegate- way whenthe averagequeuesize �� exceeds�� .

One option for the RED gateway is to measurethe queuein bytesratherthan in packets. With this option,

Initialization:�� $;:2<365��7 $ ' 0 for each packet arrival

calculate new avg. queue size �� : if the queue is nonempty� � � $ &10 '>=@?A*B�� DCE=@?GF else� $;H & 7I� ��J@'KF 7I� � JL*� � � $ &10 '>=@?A*BMN��

if �� O�P�� Q�� increment 24365��7 calculate probability � � :��! $ � ��R" & �� (')�� *,+ & � �� ')�� *� � $ ��! + &10 ')2<365��798 ��! * with probability � � :

mark the arriving packet2<365��7 $S: else if � ��

mark the arriving packet2<365��7 $;: else 2<365��7 $ ' 0

when queue becomes emptyF 7I� � J $ 7I� � J Saved Variables:�� : average queue sizeF 7I� � J : start of the queue idle time2<365��7 : packets since last marked pkt. Fixed parameters:= ? : queue weight�� : minimum threshold for queue� �� : maximum threshold for queue� ��#" : maximum value for ��! Other:�� : current pkt-marking probabilityF : current queue size7I� � J : current timeH & 71* : a linear function of the time 7

Figure2: Detailedalgorithmfor RED gateways.

the averagequeuesizeaccuratelyreflectsthe averagede- lay at the gateway. When this option is used,the algo- rithm wouldbemodifiedto ensurethattheprobabilitythat a packet is marked is proportionalto the packet size in bytes:��! $ ��R" & �� T'>� � � �� *U+ & � �� '>� � � �� *� !V$ � !XWGY Z\[ ]<^/_a`cbd] +Le YgfR`ch(i#h�WGY Z\[ ]4^\_a`jb4]

�� $ � ! + &B0 'K2<365��7k8 � ! * In this casea largeFTPpacket is morelik ely to bemarked thanis a smallTELNET packet.

Sections6 and7 discussin detailthesettingof thevar- ious parametersfor RED gateways. Section6 discusses thecalculationof theaveragequeuesize.Thequeueweight= ? is determinedby the size and duration of bursts in queuesize that are allowed at the gateway. The mini- mumandmaximumthresholds� � �� and �� arede- terminedby the desiredaveragequeuesize. The average queuesizewhich makesthedesiredtradeoffs (suchasthe tradeoff betweenmaximizingthroughputandminimizing delay) dependson network characteristics,and is left as a questionfor further research.Section7 discussesthe calculationof the packet-markingprobability.

In this paperour primary interestis in the functional operationof the RED gateways. Specificquestionsabout the most efficient implementationof the RED algorithm arediscussedin Section11.

5 A simple simulation

This sectiondescribesour simulatorandpresentsa simple simulationwith REDgateways.Oursimulatoris a version of theREAL simulator[19] built on Columbia’sNestsim- ulationpackage[1], with extensive modificationsandbug fixes madeby Steven McCanneat LBL. In the simula- tor, FTPsourcesalwayshave a packet to sendandalways senda maximal-sized(1000-byte)packet as soonas the congestioncontrol window allows themto do so. A sink immediatelysendsanACK packet whenit receivesa data packet. ThegatewaysuseFIFO queueing.

Sourceand sink nodesimplementa congestioncon- trol algorithmequivalentto that in 4.3-TahoeBSD TCP.3

Briefly, therearetwo phasesto thewindow-adjustmental- gorithm. A thresholdis setinitially to half the receiver’s advertisedwindow. In the slow-start phase,the current window is doubledeachroundtriptime until the window reachesthethreshold.Thenthecongestion-avoidancephase is entered,andthecurrentwindow is increasedby roughly onepacket eachroundtriptime. The window is never al- lowed to increaseto more than the receiver’s advertised window, which this paperrefersto asthe“maximumwin- dow size”. In 4.3-TahoeBSD TCP, packet loss(a dropped packet) is treatedas a “congestionexperienced”signal. Thesourcereactsto a packet lossby settingthethreshold to half thecurrentwindow, decreasingthecurrentwindow to onepacket, andenteringthe slow-startphase.

3Our simulatordoesnot usethe4.3-TahoeTCPcodedirectly but we believe it is functionallyidentical.

Queue size (solid line) and average queue size (dashed line).lTimem

Q u

e u

0.0 0.2 0.4 0.6 0.8 1.0

o 10 3

0 max-thp min-thq

............ ............... .............. ............... .................. ................ ................. ................ .............. ................ ........

................

............... ............ ................ ........... .............. ................ .......... ................ .............. ....

..............

............... ......... ................. ............. .......... .................. ........... ......... ................

........... .......... ................. ........... ......... ............... ............. .......... ............ .............

.........

..........

................

........... ......... .......... ................ .......... .......... .......

..............

..........

...............

..........

.........

..........

.................

..........

....

.........

..........

.........

..........

.........

..........

.........

..................

................

..............

............

..........

................

......

................

...............

..........

........

...

............

..............

..........

.........

..........

...

......

....

......

....

......

....

.......

.........

..............

..........

......

...

......

...............

....

...

......

...

............... ..

.....

..........

...........

................

.............

...

............ .......

.............

........

..............

............ .........

..........

...............

.........

........

.......

.........

...............

...

..........

................. .

..................

...............

......

...............

........

...

..............

....

...

........

...........

............

...............

........... ..........

...

....

...

.........

.......

....

...

.....

.......

............ .

......

...

.....

...

......

.....

....

..........

.................

...

..............

......

...

....

...

....

...

....

...

...........

...............

........

....

...

....

.....

......

...

....

...

....

...

.........

....

...

.....

....

.....

....

..............

....

...

....

.........

.......... ..

....

...

....

...

....

...

.......

........... ............ ..

................

...

.. .

..........

...............

.............

......

...

.........

.....

.................

..........

................

.........

............

............... ............. ...........

................

.....

....

.........

......

....

......... ..............

....

...

........

...

..........

...............

...

......

...

.....

...

..........

................

.......... ...

....

...

....

...

....

......

...

.....

...

.......

.....

..........

.....

........... ................ .............

...

....

...

.....

........

.....

...

........

...

.......

.....

....

...

......

...

.....

...

....

...

.....

...............

...

.....

....

...

.........

....

...

...............

............. ........... . .. .. . ...........

....

...

........... .......

....

...

......

.........

....

........... ....

...

....

............ .......... ..

....

...

......

...........

............... ................ .

...

....

..........

...

.....

................

............ .......... .........

....

...

....

...

......

.........

...

......

...

........

...

......

...

....

...

....

...

....

.......

........

...........

.......

...

.....

...

.....

....

...

.....

....

......

....

......

.....

...

....

.....

....

.....

....

...

.....

....

...

.....

...

.........

...............

.....

..............

........

.........

.....

...

.....

...

............ .......... .

...

....

.....

.......

....

.....

....

...

....

........

............

..........

...

......

...

.........

.......

...

.....

......

......... .

.........

....

...

.....

...

....

...

....

........

....

...

....

...

......

....

.......

.....

....

...

.......

...

....

.......

....

.....

....

......

........

...

.....

...

......

...

....

...

.....

........

............

.............

.....

....

...

....

......

...

....

........

.....

....

...

.....

......

.......

.....

......

...

....

.....

...

......

...

........... .

.....

....

.....

...

............

......

............

...

..........

...

.........

.....

....

...

.........

....

...

........

.........

.......

.....

...

........... .

...

....

.......

......

.......... .......

....

...

......

...

.....

............. .........

.....

...

......

.....

....

...

....

........... ..........

....

..........

....

...

..........

...

....

........

...

....

...

.....

...

......

...

....

............

.....

...

.........

....

...

....

...

.....

...

.....

....

...

....

.........

.....

...

....

...

.......

...

......

...

....

...

......

....

.......

...

.....

....

...

....

...

.......

...

....

...

.......

.....

...

......... ..

.........

....

...

....

.....

....

........

...

........

...

......

...

.....

...

........

....

...

....

...

....

...

.....

....

...

....

...

......

.........

........... ..

...

...........

...

........

......

..........

............. ..

.....

......... ..........

...

......

...

........

....

...

....

...

..........

...

......

...

....

...

.....

....

...

....

.....

......

...

.....

....

......

...

.......

.....

...

....

...

....

...

......

.....

...

....

...

....

.....

......

.....

...

........

....

.........

....

...

......

...

......

...

....

...

......

...

....

...

....

...

....

...

.....

...

.........

...

....

...

....

...

....

.....

.......

...

....

...

.............

.......... .......... .............. ......

...

.......

.....

..............

. . ..

..............

......

.......

...............

...........

..........

....

............

...............

........... ....

...

....

...

..........

.....

....

.....

.......

....

...

....

...

.....

........

...

.....

...

........

...

..............

.....

....

...

......

...

..........

............ ..

...

....

...

.......

...

....

.......... .

....

...

.....

....

.........

....

...

....

...

....

...

....

...

....

...

.....

...

......

.....

......

...

....

...

....

...

....

...

.....

..........

...

.......

...

....

.....

...

.....

Timer

P a c k e t N

u m

b e r

(M o d 9

0 )

fo r

F o u r

C o n n e c ti o n s

0.0 0.2 0.4 0.6 0.8 1.0

1 0 0s

2 0 0s

3 0 0s

4 0 0s

Figure3: A simulationwith four FTPconnectionswith staggeredstarttimes.

Figure 3 shows a simple simulationwith RED gate- ways. The network is shown in Figure 4. The simula- tion containsfour FTPconnections,eachwith amaximum window roughly equal to the delay-bandwidthproduct, which rangesfrom 33 to 112 packets. The RED gateway parametersare set as follows: =@?�t : . : : u , �� vtw

packets, � ��xt 0 w packets, and �� " t 0 + w : . The buffer sizeis sufficiently large that packetsarenever droppedat thegatewaydueto buffer overflow; in this sim- ulationtheRED gateway controlstheaveragequeuesize, andtheactualqueuesizenever exceedsforty packets.

3 y

2 z 4{

SINK |

GATEWAY }1

5 ~ 6 �

4 {

45Mbps � 100Mbps �

2ms �

FTP SOURCES

1ms � 4ms

� 8ms �

5ms �

Figure4: Simulationnetwork.

For thechartsin Figure3, thex-axisshows thetime in seconds.The bottomchartshows the packetsfrom nodes 1-4. Eachof the four main rows shows the packetsfrom oneof thefour connections;thebottomrow shows node1 packets,andthetop row shows node4 packets.Thereis a mark for eachdatapacket asit arrivesat the gateway and asit departsfrom the gateway; at this time scale,the two marksareoftenindistinguishable.They-axisis a function of thepacket sequencenumber;for packetnumber� from node � , the y-axis shows � h��R�(� : C & ��' 0 * 0 : : . Thus, eachvertical‘line’ represents90 consecutively-numbered packetsfrom oneconnectionarriving atthegateway. Each ‘X’ shows a packet droppedby thegateway, andeach‘X’ is followed by a mark showing the retransmittedpacket. Node1 startssendingpacketsat time 0, node2 startsaf- ter 0.2seconds,node3 startsafter0.4seconds,andnode4 startsafter0.6 seconds.

Thetopchartof Figure3 showstheinstantaneousqueue size F andthecalculatedaveragequeuesize � � � . Thedot- tedlinesshow �� and �� , theminimumandmax- imum thresholdsfor theaveragequeuesize.Notethatthe calculatedaveragequeuesize �� changesfairly slowly comparedto F . The bottom row of X’ s on the bottom chartshows againthetime of eachdroppedpacket.

This simulationshows the successof the RED gate- way in controlling the averagequeuesizeat the gateway

in responseto a dynamicallychangingload. As the num- berof connectionsincreases,thefrequency with whichthe gateway dropspacketsalsoincreases.Thereis no global synchronization.The higher throughputfor the connec- tions with shorterroundtrip times is due to the bias of TCP’s window increasealgorithmin favor of connections with shorterroundtriptimes(asdiscussedin [6, 7]). For the simulationin Figure 3 the averagelink utilization is 76%. For the following secondof the simulation,when all four sourcesare active, the averagelink utilization is 82%. (This is not shown in Figure3.)

(‘triangle’ for RED, ‘square’ for Drop Tail)�Throughput (%)� A

ve ra

g e Q

u e u e�

0.4 0.6 0.8 1.0

0� 20 4 0

6 0

8 0

1 0 0�

Figure5: ComparingDrop Tail andRED gateways.

3 �

4 �

SINK �

GATEWAY �

5 � 6 �

4 �

45Mbps �

100Mbps

FTP SOURCES

20ms �

1ms

Figure6: Simulationnetwork.

BecauseRED gatewayscancontroltheaveragequeue sizewhile accommodatingtransientcongestion,REDgate- waysarewell-suitedto provide high throughputandlow average delayin high-speednetworks with TCP connec- tions that have largewindows. TheRED gateway canac- commodatetheshortburstin thequeuerequiredby TCP’s slow-start phase;thus RED gateways control the aver- age queuesize while still allowing TCP connectionsto smoothlyopentheir windows. Figure5 shows the results of simulationsof the network in Figure6 with two TCP connections,eachwith a maximumwindow of 240 pack- ets, roughly equalto the delay-bandwidthproduct. The two connectionsarestartedat slightly differenttimes.The simulationscomparetheperformanceof Drop Tail andof RED gateways.

In Figure5 the x-axis shows the total throughputasa

fractionof the maximumpossiblethroughputon the con- gestedlink. The y-axis shows the averagequeuesize in packets(asseenby arriving packets).Five 5-secondsim- ulations were run for eachof 11 setsof parametersfor DropTail gateways,andfor 11 setsof parametersfor RED gateways;eachmarkin Figure5 shows the resultsof one of thesefive-secondsimulations. The simulationswith Drop Tail gatewayswererun with the buffer sizeranging from 15 to 140 packets; as the buffer size is increased, the throughputandtheaveragequeuesizeincreasecorre- spondingly. In order to avoid phaseeffects in the simu- lationswith Drop Tail gateways,the sourcenodetakesa randomtime drawn from theuniform distribution on [0, t] secondsto prepareanFTPpacket for transmission,where7 is thebottleneckservicetime of 0.17ms. [7].

Thesimulationswith RED gatewayswereall run with a buffer size of 100 packets, with �� ranging from 3 to 50 packets. For the RED gateways, � �� is set to �G�� , with =@?�t : . : : u and �� " t 0 + w : . The dashedlinesshow theaveragedelay(asafunctionof through- put) approximatedby 0 .��L�a+ &10 '��* for the simulations with RED gateways,and approximatedby : . 0 + &B0 '��*B� for the simulationswith Drop Tail gateways. For this simple network with TCP connectionswith large win- dows, the network power (the ratio of throughputto de- lay) is higher with RED gateways than with Drop Tail gateways. Thereare several reasonsfor this difference. With Drop Tail gateways with a small maximumqueue, the queuedropspackets while the TCP connectionis in the slow-startphaseof rapidly increasingits window, re- ducing throughput. On the other hand, with Drop Tail gatewayswith a large maximumqueuethe averagedelay is unacceptablylarge. In addition,Drop Tail gatewaysare morelik ely to drop packetsfrom both connectionsat the sametime, resultingin global synchronizationanda fur- therlossof throughput.

Later in the paper, we discusssimulationresultsfrom networks with a morediverserangeof connections.The RED gateway is not specificallydesignedfor a network dominatedby bulk data transfer; this is simply an easy way to simulateincreasingly-heavy congestionat a gate- way.

6 Calculating the averagequeuelength

The RED gateway usesa low-passfilter to calculatethe averagequeuesize. Thus,the short-termincreasesin the queuesizethat resultfrom burstytraffic or from transient congestiondo not result in a significant increasein the averagequeuesize.

Thelow-passfilter is anexponentialweightedmoving average(EWMA):�� $ &10 ')= ? *B�� DCE= ? Fa. (1)

The weight =@? determinesthe time constantof the low-passfilter. The following sectionsdiscussupperand lower boundsfor setting =@? . The calculationof the aver- agequeuesizecanbeimplementedparticularlyefficiently when=@? is a (negative)powerof two, asshown in Section 11.

6.1 An upper bound for �� If = ? is too large, then the averagingprocedurewill not filter out transientcongestionat thegateway.

Assumethatthequeueis initially empty, with anaver- agequeuesizeof zero,andthenthequeueincreasesfrom 0 to � packetsover � packetarrivals.After the � th packet arrivesat thegateway, theaveragequeuesize �� is

�� t � ¡ ¢k£ ��= ? &B0 ')= ? * ��¤ ¡

t = ? &10 '>= ? * � � ¡ ¢k£ � & 00 '>=@? * ¡

t �¥C 0 C &10 '>= ? * �#¦ £ ' 0=@? . (2) This derivationusesthefollowing identity [9, p. 65]:� ¡ ¢k£ � �

¡ t �OC & §X¨ ')�)' 0 *a� �#¦ £&10 '>��*1© .

0.001

0.002

0.003

0.004

0.005

w_q

100

ave_L

0.001

0.002

0.003

0.004

0.005

w_q

100

ave_L

Figure7: � � � � asa functionof =@? and � . Figure 7 shows the averagequeuesize �� for a

rangeof valuesfor = ? and � . The � -axis shows = ? from 0.001to 0.005,and the ª -axis shows � from 10 to 100. For example,for = ? t : . : : 0 , aftera queueincreasefrom 0 to 100 packets, the averagequeuesize �� £I«U« is 4.88 packets.

Givena minimumthreshold� � �� , andgiventhatwe wish to allow burstsof � packetsarriving at the gateway,

then=@? shouldbechosento satisfythefollowing equation for � � � �� :

�¥C 0 C &B0 ')=¬?d* �#¦ £ ' 0= ? �� #. (3) Given �� Qt w , and �t w : , for example,it is neces- saryto choose=@?N� : . : :g®au . 6.2 A lower bound for �� REDgatewaysaredesignedto keepthecalculatedaverage queuesize �� below a certainthreshold.However, this serveslittle purposeif the calculatedaverage�� is not a reasonablereflectionof the currentaveragequeuesize.If=@? is settoo low, then � � � respondstoo slowly to changes in theactualqueuesize.In this case,thegatewayis unable to detectthe initial stagesof congestion.

Assumethat the queuechangesfrom empty to one packet, andthat, aspacketsarrive anddepartat the same rate,thequeueremainsat onepacket. Furtherassumethat initially the averagequeuesize was zero. In this caseit takes ' 0 +6¯j° &B0 ')= ? * packet arrivals(with the queuesize remainingat one)until theaveragequeuesize �� reachs: . ± �)t 0 ' 0 +gJ [35]. For = ? t : . : : 0 , this takes 1000 packet arrivals; for = ? t : . : :�u , this takes500 packet ar- rivals; for =@?�t : . : : � , this takes333 packet arrivals. In mostof our simulationswe use=@?@t : . : : u . 6.3 Setting ²´³,µ·¶¹¸ and ²�º�»G¶¹¸ The optimal valuesfor �� and � �� dependon the desiredaveragequeuesize. If the typical traffic is fairly bursty, then �� must be correspondinglylarge to al- low the link utilization to be maintainedat an acceptably high level. For the typical traffic in our simulations,for connectionswith reasonablylargedelay-bandwidthprod- ucts,a minimum thresholdof onepacket would resultin unacceptablylow link utilization. The discussionof the optimal averagequeuesize for a particulartraffic mix is left asa questionfor futureresearch.

The optimal valuefor �� dependsin part on the maximumaveragedelaythat canbe allowed by the gate- way.

The RED gateway functions most effectively when�� '¼�� is larger thanthe typical increasein the calculatedaveragequeuesize in one roundtrip time. A usefulrule-of-thumbis to set�� to atleasttwice � � �� . 7 Calculating the packet-marking pr ob-

ability

The initial packet-markingprobability � ! is calculatedas a linearfunctionof theaveragequeuesize.In this section

we comparetwo methodsfor calculatingthefinal packet- marking probability, and demonstratethe advantagesof the secondmethod. In the first method,when the aver- agequeuesizeis constantthe numberof arriving packets betweenmarked packetsis a geometricrandomvariable; in the secondmethodthe numberof arriving packetsbe- tweenmarkedpacketsis a uniform randomvariable.

Theinitial packet-markingprobabilityis computedas follows:� !%$ � �� "#& �� (')�� *,+ & � ��-')�� */. The parameter�� " gives the maximum value for the packet-markingprobability��! , achievedwhentheaverage queuesizereachesthemaximumthreshold.

Method 1: Geometricrandom variables. In Method 1, let eachpacket be marked with probability ��! . Let the intermarkingtime ½ bethenumberof packetsthatarrive, after a marked packet, until the next packet is marked. Becauseeachpacket is markedwith probability � ! ,¾D¿ 3gÀLÁ ½Ât´��Ã�t &10 ' � ! *1Ä ¤ £ � ! . Thus with Method 1, ½ is a geometricrandomvariable with parameter� ! , and Å�Á ½ÆÃ�t 0 + � ! .

With aconstantaveragequeuesize,thegoalis to mark packetsat fairly regularintervals.It is undesirableto have too many marked packets close together, and it is also undesirableto have too long an interval betweenmarked packets.Both of theseeventscanresultin globalsynchro- nization,with severalconnectionsreducingtheirwindows at thesametime, andbothof theseeventscanoccurwhen½ is a geometricrandomvariable. Ç

Method 2: Uniform random variables. A morede- sirablealternative is for ½ to be a uniform randomvari- able from È 1, 2, ..., 0 + ��!/É (assumingfor simplicity that0 + � ! is an integer). This is achievedif the markingprob- ability for eacharriving packet is � ! + &B0 'Ê2<365��7@8 � ! * , where2<365��7 is thenumberof unmarkedpacketsthathave arrived sincethe last marked packet. Call this Method2. In this case,¾D¿ 3gÀgÁ ½ÂtP��ÃËt � !0 ' & � ' 0 * � ! Ä ¤ ©Ì¡ ¢X« Í 0 ' � !0 '>� � ! Ît � !(Ï¹� Ð 0 ��>� 0 + � !/Ñ and ¾D¿ 3gÀLÁ ½Òt��Ã�t :¥Ï¹� Ð �¥Ó 0 + � ! . For Method2, Å�Á ½�Ã�t 0 + & u � ! *XC 0 + u . Ç

Figure8 showsanexperimentcomparingthetwo meth- ods for marking packets. The top line shows Method 1, where eachpacket is marked with probability � , for� t : . :�u . The bottomline shows Method2, whereeach packetis markedwith probability� + &10 CD� � * , for � t : . : 0 ,

(top row for Method 1, bottom row for Method 2) Packet NumberÔ0Õ 1000 2000 3000 4000 5000

..... .. . ... ..... .. . . . . ...... . . .. . .. . . .. . ... .. . . .... . .. .. . .... ... ... .. .. . .. . . .. . ... . . . ... . .. . . . . . . . .. .. . . ... . .. . .. . .. ... ... .. .... .. . . . .. . ... .. .. ... . .... . . .. . .. . ..... . ... . ...... . . ..... .. .. . .. .. . . .

... .... ... . . ...... .... . . ... .. . . .. . ........ . . .... ..... ......... ..... . .. ........ ..... . . ........ ..... .... . .. .... ..... .. . . .... ... ... . . ... ...... . .. ... .. .. . ..... .. . .... .. .. ...... . .... . .... . .. . .. .... .... .. .. . .....1:

2:Ö

Figure8: Randomly-markedpackets,comparingtwo packet-markingmethods.

and for � the numberof unmarked packets sincethe last markedpacket. Both methodsmarkedroughly100 out of the 5000 arriving packets. The � -axis shows the packet number. For eachmethod,thereis a dot for eachmarked packet. As expected,the marked packetsare more clus- teredwith Method1 thanwith Method2.

For thesimulationsin this paper, we set� �� " to 1/50. Whenthe averagequeuesizeis halfway between�� and � �� , the gateway drops,on the average,roughly one out of 50 (or one out of 0 +6�� " ) of the arriving packets. RED gateways perform best when the packet- markingprobability changesfairly slowly as the average queuesizechanges;thishelpsto discourageoscillationsin the averagequeuesizeandin the packet-markingproba- bility. Thereshouldnever bea reasonto set ��R" greater than0.1, for example.When � ��#"�t : . 0 , thenthe RED gateway markscloseto 1/5thof thearriving packetswhen theaveragequeuesizeis closeto themaximumthreshold (using Method 2 to calculatethe packet-markingproba- bility). If congestionis sufficiently heavy thattheaverage queuesizecannotbecontrolledby markingcloseto 1/5th of the arriving packets,thenafter the averagequeuesize exceedsthe maximumthreshold,the gateway will mark every arriving packet.

8 Evaluation of RED gateways

In addition to the designgoals discussedin Section3, several generalgoals have beenoutlined for congestion avoidanceschemes[14, 16]. In this sectionwe describe how our goalshave beenmetby RED gateways.× Congestionavoidance. If the RED gateway in fact drops packets arriving at the gateway when the average queuesizereachesthemaximumthreshold,thentheRED gateway guaranteesthatthecalculatedaveragequeuesize doesnot exceedthemaximumthreshold.If theweight =@? for the EWMA procedurehasbeensetappropriately[see Section6.2], then the RED gateway in fact controlsthe actual averagequeuesize. If the RED gateway setsa bit in packetheaderswhentheaveragequeuesizeexceedsthe maximumthreshold,rather than dropping packets, then

theRED gateway relieson the cooperationof the sources to controltheaveragequeuesize.× Appr opriate time scales.After notifying a connec- tion of congestionby marking a packet, it takes at least a roundtriptime for the gateway to seea reductionin the arrival rate.In RED gatewaysthetime scalefor thedetec- tion of congestionroughlymatchesthetimescalerequired for connectionsto respondto congestion.RED gateways don’t notify connectionsto reducetheir windows asa re- sult of transientcongestionat thegateway.× No global synchronization. Therateat which RED gateways mark packets dependson the level of conges- tion. During low congestion,thegateway hasa low prob- ability of marking eacharriving packet, and as conges- tion increases,the probability of markingeachpacket in- creases.RED gatewaysavoid global synchronizationby markingpacketsat aslow a rateaspossible.× Simplicity. The RED gateway algorithm could be implementedwith moderateoverheadin currentnetworks, asdiscussedfurtherin Section11.× Maximizing global power4. The RED gateway ex- plicitly controlsthe averagequeuesize. Figure 5 shows thatfor simulationswith highlink utilization,globalpower is higher with RED gateways than with Drop Tail gate- ways. Future researchis neededto determinethe opti- mum averagequeuesizefor differentnetwork andtraffic conditions.× Fair ness.Onegoalfor acongestionavoidancemech- anismis fairness.This goalof fairnessis not well-defined, so we simply describethe performanceof the RED gate- way in this regard. The RED gateway doesnot discrim- inateagainstparticularconnectionsor classesof connec- tions. (This is in contrastto Drop Tail or RandomDrop gateways,asdescribedin [7]). For the RED gateway, the fractionof markedpacketsfor eachconnectionis roughly proportionalto that connection’s shareof the bandwidth. However, RED gateways do not attemptto ensurethat eachconnectionreceives the samefraction of the total throughput,anddonotexplicitly controlmisbehaving users. RED gatewaysprovide a mechanismto identify the level

4Poweris definedastheratio of throughputto delay.

of congestion,and RED gateways could also be usedto identify connectionsusinga largeshareof the total band- width. If desired,additionalmechanismscould be added to RED gatewaysto control the throughputof suchcon- nectionsduringperiodsof congestion.× Appr opriate for a wide range of envir onments. The randomizedmechanismfor marking packets is ap- propriatefor networks with connectionswith a rangeof roundtrip times and throughput,and for a large rangein the numberof active connectionsat one time. Changes in the load are detectedthroughchangesin the average queuesize,andtherateat which packetsaremarkedis ad- justedcorrespondingly. TheRED gateway’s performance is discussedfurtherin thefollowing section.

Even in a network whereRED gatewayssignalscon- gestionby droppingmarked packets,thereare many oc- casionsin a TCP/IPnetwork whena droppedpacket does not result in any decreasein load at the gateway. If the gateway dropsa datapacket for a TCP connection,this packet drop will be detectedby the source,possiblyaf- ter a retransmissiontimer expires.If thegateway dropsan ACK packetfor aTCPconnection,or apacketfrom anon- TCP connection,this packet drop could go unnoticedby the source.However, even for a congestednetwork with a traffic mix dominatedby short TCP connectionsor by non-TCPconnections,the RED gateway still controlsthe averagequeuesizeby droppingall arriving packetswhen theaveragequeuesizeexceedsa maximumthreshold.

8.1 Parameter sensitivity

This sectiondiscussesthe parametersensitivity of RED gateways. Unlike Drop Tail gateways, where the only free parameteris the buffer size,RED gatewayshave ad- ditional parametersthatdeterminetheupperboundon the averagequeuesize, the time interval over which the av- eragequeuesizeis computed,andthe maximumratefor marking packets. The congestionavoidancemechanism should have low parametersensitivity, and the parame- tersshouldbeapplicableto networkswith widely varying bandwidths.

TheRED gateway parameters=¬? , � �� , and �� arenecessaryso that the network designercanmake con- sciousdecisionsaboutthedesiredaveragequeuesize,and aboutthe sizeanddurationin queueburststo be allowed at the gateway. The parameter�� " canbe chosenfrom a fairly wide range,becauseit is only an upperboundon the actualmarkingprobability ��! . If congestionis suffi- ciently heavy that the gateway cannotcontrolthe average queuesize by marking at most a fraction � ��#" of the packets,thentheaveragequeuesizewill exceedthemax- imum threshold,andthe gateway will mark every packet until congestionis controlled.

We give a few rulesthatgive adequateperformanceof

theRED gateway undera wide rangeof traffic conditions andgateway parameters.

1: Ensureadequatecalculation of the averagequeue size: set =@?DØ : . : : 0 . Theaveragequeuesizeat thegate- wayis limited by � �� , aslongasthecalculatedaverage queuesize � � � is a fairly accuratereflectionof the actual averagequeuesize. The weight =@? shouldnot be settoo low, so that the calculatedaveragequeuelengthdoesnot delaytoo long in reflectingincreasesin the actualqueue length [See Section6]. Equation3 describesthe upper boundon = ? requiredto allow thequeueto accommodate burstsof � packetswithout markingpackets.

2: Set �� sufficiently high to maximize network power. The thresholds� � �� and �� shouldbe set sufficiently highto maximizenetwork power. As westated earlier, moreresearchis neededon determiningthe opti- mal averagequeuesize for various network conditions. Becausenetwork traffic is often bursty, the actualqueue sizecanalsobe quite bursty; if the averagequeuesizeis kepttoo low, thentheoutputlink will beunderutilized.

3: Mak e �� -')�� sufficiently lar geto avoid global synchronization. Make �� '� � � �� larger thanthe typical increasein the averagequeuesizeduring a roundtriptime, to avoid the global synchronizationthat resultswhenthegateway marksmany packetsat onetime. Onerule of thumbwould beto set �� to at leasttwice� � �� . If � ��Ù'T� � �� is too small,thenthecomputed averagequeuesize can regularly oscillateup to �� ; this behavior is similar to the oscillationsof the queueup to themaximumqueuesizewith Drop Tail gateways.

Queue size (solid line) and average queue size (dashed line).lTimem

Q u

e u

e f

o r

g a

te A

Ú 0.0 0.2 0.4 0.6 0.8 1.0

o 20 4

0 max-thp min-thq

Queue size (solid line) and average queue size (dashed line).lTimem

Q u

e u

e f

o r

g a

te B

Ú 0.0 0.2 0.4 0.6 0.8 1.0

o 20 4

max-thp min-thq

................ ...................... ...................... ........................ .................. ................... ..................... ...................... ......

...

..................... ...................... ......

................

............

....................

.....................

...........

.....................

........................

...

....................

...

..................

....

....................

................

...

.....

...

................ .......

......

....

...

....

............

........

.......

...

....

..................

....

.........

....

.........

......

....

......

...

....

.....

...

.......

........

......

...

..............

....

.....

...

....

...

.........

........

............. .....

...

.....

...

....

...

....

...................

...

....

..........................

....

.......

....

...

....

...

....

...

....

......

...................

.......

.........

...

....

.....

..............

....

...

.....

...

....

...

....

........................

.....

........

...

.....

...

....

...

......

.....

...

....

...

.......

....

...

....

...

........

...

....

...

.........

.......

.....

....

.....

....

......

...

........

.....

...

....

......

...

.....

.......

......

...

....

.....

...

.....

...

....

.....

...

.....

....

........

.....

......

...

....

...

....

...

....

...

....

...

......

....

...

....

...

....

...

.....

...

....

...

....

...

......

....

...

......

....

......

....

...

....

...

....

...

....

...

....

.....

....

...

........

....

...

....

...

....

......

....

...

.......

....

...

....

...

....

...

....

...

....

...

....

........

...

....

...

....

......

.....

....

...

....

...

....

...

....

...

........

....

...

....

.....

...

....

...

....

......

...

....

...

.....

...

....

...

....

...

....

...

....

.....

...

....

..........

....

...

......

....

.......

....

...

.....

....

...

....

...

....

...

....

...

......

....

...

....

...

....

...

....

...

.....

....

...

....

.....

.......

...

......

.......

........

.......

.....

....

...

....

...

....

........

....

...

.......

......

...

....

.....

........

...

....

...

....

...

....

...

.....

....

...

........

...

..........

....

.......

...

.....

......

....

...

....

.....

...

......

.......

...

.......

......

....

.....

...

....

..........

.........

...

.......

....

...

....

...

....

.....

......

....

........

...

....

...

.........

........

.....

......

...

....

...

.......

...

....

...

....

......

....

...

.....

...

....

...

....

...

....

...

......

....

...

.....

...

....

...

.....

....

...

....

...

....

...

........

...

....

......

...

.....

......

.......

....

...

....

...

....

...

....

...

......

...

.......

...

....

...

....

.....

....

...

.....

......

....

......

........

...

....

...

....

...

......

....

...

....

...

......

....

.....

....

...

....

...

.....

...

....

...

....

...

.....

...

....

...

........

....

...

........

...

....

...

.....

...

....

...

....

...

.....

...

......

...

....

...

.....

...

....

...

....

.....

....

...

....

......

...

....

........

....

...

.....

....

...

....

...

.....

...

....

.....

...

....

...

....

...

....

...

......

.......

...

.....

....

...

....

...

........

.....

...

....

..................

.............

....

...

.....

...

......

...

......

........

...

....

...

....

......

...

.....

....

...

....

...

......

....

...

....

...

....

...

.....

...

....

...

....

...

....

......

...

....

...

......

...

....

.....

...

......

...

....

...

......

....

.....

....

..........

......

...

....

...

.....

...

....

......

.....

....

...

....

......

....

.....

...

....

...

....

...

....

...

....

...

....

...

....

...

.....

....

.........

...

......

...

....

.....

....

.....

...

....

...

......

.......

...

....

...

....

...

....

......

...

....

...

....

...

....

...

....

...

.....

...

....

.....

...

.....

...

....

.....

...

....

...

......

....

.............

...............

....

...

....

...

....

...

....

...

....

...

....

...

................

...

....

...

....

...

.....

....

...

....

......

...

....

...

....

...

.....

....

...

..........

....

...

......

....

...

......

....

...

....

......

...

....

...

....

...

.......

........

...

.....

...

....

...

....

...

....

...

......

...

....

...

....

........

...

....

...

....

...

......

...

....

...

....

...

....

...

......

....

...

....

...

....

...

....

...

.....

...

....

...

....

...

....

...

........

....

.......

.....

....

...

....

...

....

...

....

...

....

...

......

...

......

...

....

...

....

...

....

...

......

..........

...

.....

........

...

........

...

....

...

....

......

...

......

........

...

.....

....

...

........

...

....

...

....

...

....

...

....

......

...

......

...

....

...

....

...

....

...

......

...

....

...

....

........

...

.......

...

....

...

....

...

.....

...

....

......

...

....

...

....

........

...

....

...

....

........

...

.................

.......

...

....

...

....

.....

...

.....

...

.................

...

.....

....

..............

.........

................

..........

.......

...

.....

......

...

....

...

....

.......

...

....

...

....

.....

........ ..

.....

...

....

..........

...

........

...

.....

........ ..

......

...

.....

...

.....

.. .

........

...

....

...... .....

........

.........

.....

........... ......

......

....

.. ..

.......

. ....... .

.....

......

........

...

........

. ...

........

.. .. .. . ...

. . . . . . . . ...

. . ...

. .. . . . .

. .... . . ..... .

. .

.. .... .

. . .... . ........ ........ ........ ........ ........ ......... .....

........ ........ ....

. .

....

.. ..

TimeÛ

P ac

ke t N

um be

r f or

E ac

h C

on ne

ct io

0.0 0.2 0.4 0.6 0.8 1.0

0Ý

10 0Ý

20 0Ý

30 0Ý

Figure 9: A RED gateway simulationwith heavy congestion,two-way traffic, and many short FTP and TELNET connections.

3 Þ 1 ß 2 à

4 á

GATEWAY â

1 ß

4 á

GATEWAY â

1 ß

4 á

A ã

5 ä 6 å 7 æ 8 ç

45Mbps è

100Mbps é100Mbpsé

2ms ê1ms

é 5ms ë 2msê

1ms é 5ms ë

0.5ms ì

3ms í

0.5ms ì

Figure10: A network with many shortconnections.

To investigatethe performanceof RED gatewaysin a rangeof traffic conditions,this sectiondiscussesa simula- tion with two-way traffic, wherethereis heavy congestion resultingfrom many FTPandTELNET connections,each with a small window andlimited datato send.The RED gateway parametersarethe sameasin the simplesimula- tion in Figure3, but thenetwork traffic is quitedifferent.

Figure9 showsthesimulation,whichusesthenetwork in Figure10. Roughlyhalf of the41 connectionsgo from one of the left-handnodes1-4 to one of the right-hand nodes5-8; the otherconnectionsgo in the oppositedirec- tion. The roundtrip times for the connectionsvary by a factor of 4 to 1. Most of the connectionsare FTP con- nections,but therearea few TELNET connections.(One of the reasonsto keepthe averagequeuesizesmall is to ensurelow averagedelayfor the TELNET connections.) Unlike the previous simulations,in this simulationall of the connectionshave a maximumwindow of either 8 or 16 packets. The total numberof packetsfor a connection rangesfrom 20 to 400packets.Thestartingtimesandthe total numberof packetsfor eachconnectionwerechosen ratherarbitrarily; we arenot claiming to representrealis- tic traffic models. The intentionis simply to show RED gatewaysin a rangeof environments.

Becauseof the effects of ack-compressionwith two- way traffic, the packetsarriving at the gateway from each connectionare somewhat bursty. When ack-packets are ‘compressed’in a queue,the ack packets arrive at the sourcenodein a burst. In response,the sourcesendsa burstof datapackets[38].

The top chart in Figure 9 shows the queuefor gate- way A, andthenext chartshows thequeuefor gateway B. For eachchart,each‘X’ indicatesa packet droppedat that gateway. The bottom chart shows the packets for each connectionarriving and departingfrom gateway A (and headingtowardsgatewayB). For eachconnection,thereis a mark for eachpacket arriving anddepartingfrom gate- way A, thoughat this time scalethe two marksareindis- tinguishable.Unlike thechartin Figures3, in Figure9 the

packetsfor the differentconnectionsare displayedover- lapped,rather than displayedon separaterows. The x- axisshows time, andthe y-axis shows the packet number for thatconnection,whereeachconnectionstartsatpacket number0. For example,theleftmost‘strand’showsacon- nectionthat startsat time 0, and that sends220 packets in all. Each‘X’ shows a packet droppedby one of the two gateways. The queueis measuredin packets rather in bytes;shortpacketsarejust aslik ely to be droppedas are longer packets. The bottom line of the bottom chart shows againan‘X’ for eachpacket droppedby oneof the two gateways.

BecauseFigure 9 shows many overlappingconnec- tions, it is not possibleto tracethe behavior of eachof the connections.As Figure9 shows, the RED gateway is effectivein controllingtheaveragequeuesize.Whencon- gestionis low at one of the gateways,the averagequeue size and the rate of marking packets is also low at that gateway. As congestionincreasesat the gateway, the av- eragequeuesizeandthe rateof markingpacketsboth in- crease.Becausethis simulationconsistsof heavy conges- tion causedby many connections,eachwith a smallmax- imum window, the RED gateways have to drop a fairly large numberof packets in order to control congestion. Theaveragelink utilization over theone-secondperiodis 61% for the congestedlink in onedirection,and59% for theotherdirection.As thefigureshows, thereareperiods at the beginning and the end of the simulationwhen the arrival rateat thegatewaysis low.

Note that the traffic in Figures3 and 9 in quite var- ied, andin eachcasethe RED gateway adjustsits rateof markingpacketsto maintainanacceptableaveragequeue size. For the simulationsin Figure 9 with many short connections,thereare occasionalperiodsof heavy con- gestion,and a higher rate of packet drops is neededto control congestion. In contrast,with the simulationsin Figure 3 with a small numberof connectionswith large maximumwindows,thecongestioncanbecontrolledwith a small numberof droppedpackets. For the simulations in Figure 9, the burstinessof the queueis dominatedby short-termburstinessas packet burstsarrive at the gate- way from individual connections.For the simulationsin Figure3, the burstinessof the queueis dominatedby the window increase/decreasecycles of the individual con- nections.Note that the RED gateway parametersareun- changedin thesetwo simulations.

Theperformanceof aslightly differentversionof RED gatewayswith connectionswith differentroundtriptimes and with connectionswith multiple congestedgateways hasbeenanalyzedandexploredelsewhere[5].

9 Bursty traffic

This sectionshows thatunlike Drop Tail or RandomDrop gateways,RED gatewaysdo not havea biasagainstbursty traffic.5 Bursty traffic at the gateway can result from an FTP connectionwith a long delay-bandwidthproductbut a smallwindow; a window of traffic will besent,andthen therewill be a delayuntil the ack packetsreturnandan- otherwindow of datacanbe sent.Variable-bit-ratevideo traffic and someforms of interactive traffic areother ex- amplesof burstytraffic seenby thegateway.

In this sectionwe useFTP connectionswith infinite data,small windows, andsmall roundtriptimesto model the less-bursty traffic, and we useFTP connectionswith smallerwindows andlongerroundtriptimesto modelthe more-burstytraffic.

We considersimulationsof the network in Figure11. Node5 packetshave a roundtriptime thatis six timesthat of the other packets. Connections1-4 have a maximum window of 12 packets, while connection5 has a maxi- mum window of 8 packets. Becausenode5 hasa large roundtriptime anda small window, node5 packetsoften arrive at the gateway in a loosecluster. By this, we mean that consideringonly node 5 packets, there is one long interarrival time, andmany smallerinterarrival times.

1 î

SINK ï

GATEWAY ð

FTP SOURCES

2 3 4

6 ñ 7 ò

d5,6

d 6,7

= 2ms

45Mbps

100Mbps

d(1,2,3,4),6 = 1ms

= 16ms

45Mbps

Figure 11: A simulationnetwork with five FTP connec- tions.

Figures12 through14 show theresultsof simulations of thenetwork in Figure11 with DropTail, RandomDrop, andRED gatewaysrespectively. The simulationsin Fig- ures12 and13 wererun with thebuffer sizerangingfrom 8 packets to 22 packets. The simulationsin Figure 14 wererun many timeswith a minimum thresholdranging from 3 to 14 packets,anda buffer sizerangingfrom 12 to 56 packets.

5By bursty traffic we mean traffic from a connectionwhere the amountof datatransmittedin one roundtriptime is small comparedto thedelay-bandwidthproduct,but wheremultiple packetsfrom thatcon- nectionarrive at thegateway in a shortperiodof time.

++ +

+ ++

+ +

+++ +

+ + ++ +

+ +

++ +

+ ++

+ +++

+ +

+ + +

+ +

+ + ++ + +

+ +

++ +

+++++++++

Buffer Sizeó

N o

d e

5 T

h ro

u g

h p

u t

(% )

8 õ

10ö 12÷ 14ø 16ù 18õ 20ö 22÷0ú

1û

. .

. . .

. . . . .

Buffer SizeÿAv er

ag e

Q ue

ue (i

n pa

ck et

� 8 �

10 12� 14� 16 18 20 22�0� 5�

10 15

. .

. . .

. . . . . . . . . .

Buffer SizeÿA ve

ra ge

L in

k U

til iz

at io

� 8 �

10 12� 14� 16 18 20 22�0.80�

0. 90�

1. 00�

Figure12: Simulationswith Drop Tail gateways.

Each simulation was run for ten seconds,and each markrepresentsoneone-secondperiodof thatsimulation. For Figures12 and 13, the x-axis shows the buffer size, andthey-axisshows node5’s throughputasa percentage of the total throughputthroughthe gateway. In order to avoid traffic phaseeffects (effects causedby the precise timing of packet arrivals at the gateway), in the simula- tions with Drop Tail gatewaysthe sourcetakesa random timedrawn from theuniform distribution on [0, t] seconds to preparean FTP packet for transmission,where 7 is the bottleneckservicetime of 0.17 ms. [7]. In thesesimula- tionsour concernis to examinethegateway’s biasagainst burstytraffic.

For eachset of simulationsthere is a secondfigure showing the averagequeuesize (in packets) seenby ar- riving packetsat thebottleneckgateway, anda third figure showing theaveragelink utilizationon thecongestedlink.

+++++

++ +

+ +

++ +

+ +

++ +

+ +

+ ++ ++ +

+ +

+ + +

+ +

+++

++ +

+ +

+++++++

+++++++++

Buffer Sizeó

N o

d e

5 T

h ro

u g

h p

u t

(% )

8 õ

10ö 12÷ 14ø 16ù 18õ 20ö 22÷0ú

1û

ü 3

ý 4

. . .

. .

. . . .

. . . . . .

Buffer SizeÿAv er

ag e

Q ue

ue (i

n pa

ck et

� 8 �

10 12� 14� 16 18 20 22�0�

5�

10 15

. . . . .

. . . .

. . . . . .

Buffer SizeÿA ve

ra ge

L in

k U

til iz

at io

� 8 �

10 12� 14� 16 18 20 22�0.80�

0. 90�

1. 00�

Figure13: Simulationswith RandomDrop gateways.

BecauseRED gatewaysarequitedifferentfrom Drop Tail or RandomDrop gateways,the gatewayscannotbe com- paredsimply by comparingthe maximumqueuesize;the mostappropriatecomparisonis betweena Drop Tail gate- way and a RED gateway that maintainthe sameaverage queuesize.

With Drop Tail or RandomDrop gateways,the queue is morelik ely to overflow whenthe queuecontainssome packets from node5. In this case,with either Random Dropor DropTail gateways,node5 packetshaveadispro- portionateprobability of being dropped;the queuecon- tentswhenthe queueoverflows arenot representative of theaveragequeuecontents.

Figure 14 shows the result of simulationswith RED gateways. The x-axis shows � � �� andthe y-axis shows node5’s throughput.Thethroughputfor node5 is closeto themaximumpossiblethroughput,givennode5’sroundtrip

Minimum Threshold

N o d e 5

T h ro

u g h p u t (%

)

4 �

6 �

10� 12� 14�0�

1�

�

3�

�

. .

Minimum Threshold� A

ve ra

ge Q

ue ue

(i n

pa ck

et s)

� 4� 6� 8� 10 12� 14�0�

5� 10

. .

. . . . . .

. . . .

Minimum Threshold�

A ve

ra ge

L in

k U

til iz

at io

� 4� 6� 8� 10 12� 14�0.80�

0. 90�

1. 00�

Figure14: Simulationswith RED gateways

time andmaximumwindow. Theparametersfor theRED gateway areasfollows: =@?(t : . : :�u and �� " t 0 + w : . The maximumthresholdis twice the minimum threshold andthe buffer size,which rangesfrom 12 to 56 packets, is four timesthe minimumthreshold.

Figure15 shows that with the simulationswith Drop Tail or with RandomDrop gateways, node5 receives a disproportionateshareof the packet drops.Eachmark in Figure15 shows the resultsfrom a one-secondperiodof simulation. The boxes show the simulationswith Drop Tail gatewaysfrom Figure12, thetrianglesshow thesim- ulationswith RandomDrop gatewaysfrom Figure13,and the dots show the simulationswith RED gateways from Figure 14. For each one-secondperiod of simulation, the x-axis shows node 5’s throughput(as a percentage of the total throughput)and the y-axis shows node 5’s packet drops(as a percentageof the total packet drops).

(square for Drop Tail, triangle for Random Drop, dot for RED)�Node 5 Throughput (%)�

N od

e 5

D ro

ps (

% )�

0� 2� 4� 6� 8� 100�

10 20

30 40

... .

. .

...

. .

...

.....

. .

...

. .

....

......

. ....

.....

Figure15: Scatterplot, packet dropsvs. throughput

The numberof packets droppedin one one-secondsim- ulation periodrangesfrom zeroto 61; the chartexcludes thoseone-secondsimulationperiodswith lessthanthree droppedpackets.

Thedashedline in Figure15 shows thepositionwhere node 5’s shareof packet drops exactly equalsnode 5’s shareof the throughput. The cluster of dots is roughly centeredon the dashedline, indicatingthat for the RED gateways,node5’sshareof droppedpacketsreflectsnode5’s shareof the throughput.In contrast,for simulationswith RandomDrop (or with Drop Tail) gateways node 5 re- ceivesa small fraction of the throughputbut a large frac- tion of thepacket drops.This shows thebiasof Drop Tail andRandomDropgatewaysagainsttheburstytraffic from node5.

Our simulationswith an ISO TP4 network using the DECbit congestionavoidanceschemealso show a bias againstbursty traffic. With the DECbit congestionavoid- anceschemenode5 packetshaveadisproportionatechance of having their congestionindicationbits set.TheDECbit congestionavoidancescheme’s biasagainstbursty traffic would becorrectedby DECbit congestionavoidancewith selective feedback[28], which hasbeenproposedwith a fairnessgoal of dividing eachresourceequallyamongall of the userssharingit. This modificationusesa selective feedbackalgorithm at the gateway. The gateway deter- mineswhich usersareusingmorethantheir “f air share” of the bandwidth,andonly setsthe congestion-indication bit in packetsbelongingto thoseusers.We have not run simulationswith this algorithm.

10 Identifying misbehaving users

In this sectionwe show that RED gateways provide an efficient mechanismfor identifying connectionsthat use

a large shareof the bandwidthin times of congestion. BecauseRED gateways randomly choosepackets to be marked during congestion,RED gateways could easily identify whichconnectionshavereceivedasignificantfrac- tion of therecently-markedpackets.Whenthenumberof markedpacketsis sufficiently large,a connectionthathas receiveda largeshareof themarkedpacketsis alsolik ely to be a connectionthat hasreceived a large shareof the bandwidth.This informationcouldbeusedby higherpol- icy layersto restrict the bandwidthof thoseconnections duringcongestion.

The RED gateway notifiesconnectionsof congestion at the gateway by markingpackets. With RED gateways, when a packet is marked, the probability of marking a packet from a particular connectionis roughly propor- tional to that connection’s currentshareof the bandwidth throughthegateway. Notethatthis propertydoesnot hold for Drop-Tail gateways,asdemonstratedin Section9.

For the restof this section,we assumethat eachtime the gateway marksa packet, the probability that a packet from a particularconnectionis markedexactlyequalsthat connection’s fraction of the bandwidththroughthe gate- way. Assumethat connection� hasa fixed fraction � ¡ of the bandwidththroughthe gateway. Let

¡ ! Ä be the num- ber of the � most-recently-marked packetsthat are from connection� . From the assumptionsabove, the expected valuefor

¡ ! Ä is � � ¡ . Fromstandardstatisticalresultsgivenin theappendix, ¡ ! Ä is unlikely to be muchlarger thanits expectedvalue

for sufficiently large � :¾D¿ 3gÀ & ¡ ! Ä Ø�2 � ¡ � * �PJ ¤ © Ä "$# ¤ £&%(' " ') for 0 �x2 � 0 + � ¡ . The two lines in Figure16 show the upperboundon the probabilitythat a connectionreceives morethanC timesthe expectednumberof marked pack- ets,for * t uRÑ,® , andfor �Æt 0 : : ; the x-axisshows � ¡ .

Throughput (%)+

P ro

b a b il it y,

0.0 0.05- 0.10. 0.15. 0.20/ 0.25/ 0.3000. 0

0 .1

0 .2

0 .3

03 C=2

C=4

Figure16: Upperboundon probabilitythataconnection’s fraction of marked packets is more than C times the ex- pectednumber, given 0 : : total markedpackets.

The RED gateway could easily keep a list of the � mostrecently-marked packets. If someconnectionhasa large fraction of the marked packets,it is lik ely that the connectionalsohada large fraction of the averageband- width. If someTCP connectionis receiving a large frac- tion of the bandwidth,that connectioncould be a misbe- having hostthatis not following currentTCPprotocols,or simply a connectionwith either a shorterroundtrip time or a larger window than other active connections.In ei- ther case,if desired,the RED gateway could be modified to give lower priority to thoseconnectionsthat receive a large fraction of the bandwidthduring times of conges- tion.

11 Implementation

This sectionconsidersefficient implementationsof RED gateways. We show that the RED gateway algorithmcan be implementedefficiently, with only a small numberof addandshift instructionsfor eachpacket arrival. In addi- tion, theRED gateway algorithmis not tightly coupledto packet forwardingandits computationsdo not have to be madein the time-critical packet forwarding path. Much of the work of the RED gateway algorithm, suchas the computationof the averagequeuesizeandof the packet- marking probability � ! , could be performedin parallel with packetforwarding,or couldbecomputedby thegate- way asa lower-priority taskastime permits. This means thattheRED gateway algorithmneednot impair thegate- way’s ability to processpackets,andtheRED gateway al- gorithmcanbeadaptedto increasingly-high-speedoutput lines.

If theRED gateway’s methodof markingpacketsis to seta congestionindicationbit in thepacket header, rather than droppingthe arriving packet, then setting the con- gestionindicationbit itself addsoverheadto the gateway algorithm.However, becauseRED gatewaysaredesigned to mark as few packets as possible,the overheadof set- ting the congestionindication bit is kept to a minimum. This is unlike DECbit gateways, for example,which set the congestionindicationbit in every packet that arrives at the gateway when the averagequeuesize exceedsthe threshold.

For everypacketarrival atthegatewayqueue,theRED gateway calculatesthe averagequeuesize. This can be implementedasfollows:�� $ �� DC¼= ? & F 'K� � �#* As long as =@? is chosenas a (negative) power of two, this canbe implementedwith oneshift andtwo additions (givenscaledversionsof theparameters)[14].

BecausetheREDgatewaycomputestheaveragequeue sizeat packet arrivals, ratherthanat fixed time intervals,

thecalculationof theaveragequeuesizeis modifiedwhen a packet arrivesat the gateway to an emptyqueue.After the packet arrives at the gateway to an empty queuethe gateway calculates� , the numberof packets that might have beentransmittedby thegateway duringthetime that the line was free. The gateway calculatesthe average queuesizeasif � packetshadarrivedat thegateway with a queuesizeof zero.Thecalculationis asfollows:� $ & 7I� ��J¬')F 7I� ��JL*,+54�� $ &B0 '>=@?4* M �� Ñ where F 7I� � J is the start of the queueidle time, and 4 is a typical transmissiontime for a small packet. This entire calculationis an approximation,as it is basedon thenumberof packetsthatmighthave arrivedat thegate- way during a certainperiod of time. After the idle time687:9<;>=@?BA 7:9C;D=FE

hasbeencomputedto a roughlevel of accuracy, a table lookup could be usedto get the term6&GH?JILKMEONQP(RQSUTWV K P(R$SUT:X8YOZ

, which coulditself beanapprox- imationby a power of two.

Whena packet arrivesat the gateway andthe average queuesize []\_^ exceedsthethreshold; []` P8a , thearriving packet is marked. Thereis no recalculationof the packet- marking probability. However, when a packet arrives at the gateway and the averagequeuesize []\_^ is between the two thresholds

;>9<b P8a and ; []` P8a , the initial packet- markingprobability ced is calculatedasfollows:

c dgfihUj []\k^ ? hml for h jLn ; []`po; []` P8a ?q;>9Cb P8asr

htl n ; []`po ;u9<b P8a; []` P8a ?q;>9Cb P8asv The parameters

; []`po , ; []` P8a , and ;>9Cb P8a are fixed pa- rametersthat are determinedin advance. The valuesfor; []` P8a and ;u9<b P8a aredeterminedby the desiredbounds on the averagequeuesize,and might have limited flexi- bility. The fixed parameter

; []` o , however, could easily be setto a rangeof values.In particular,

; []` o could be chosenso that h j is a power of two. Thus,the calcula- tion of ced canbeaccomplishedwith oneshift andoneadd instruction.

In thealgorithmdescribedin Section4, when ;>9<b P8axw[]\k^zy ; []` P8a a new pseudo-randomnumber { is com-

putedfor eacharriving packet, where{|n}{@[ b�~k��;�� r G�� is from the uniform distribution on [0,1]. Theserandom numberscouldbegottenfrom a tableof randomnumbers storedin memoryor could be computedfairly efficiently on a 32-bit computer[3]. In the algorithm describedin Section4, the arriving packet is markedif

{�yqcedO� 6&GU?q��b�7�� ced E v 18

If c�d is approximatedby a negativepowerof two, thenthis canbeefficiently computed.

It is possibleto implementthe RED gateway algo- rithm to usea new randomnumberonly oncefor every markedpacket,insteadof usinga new randomnumberfor every packet that arrives at the gateway when

;>9<b P8aBw[]\_^�y ; []` P8a . As Section7 explains,whenthe average queuesizeis constantthe numberof packet arrivals after a marked packet until the next packet is marked is a uni- form randomvariablefrom � 1, 2, ..., � G �Oc d<�_� . Thus,if the averagequeuesizewasconstant,thenaftereachpacket is marked the gateway could simply choosea valuefor the uniform randomvariable {�n�{�[ b�~]��;q� � r GM� , and mark the

b -th arriving packet if

b�� {��ced . Becausethe av- eragequeuesizechangesover time, we recompute{��ced eachtime that c�d is recomputed.If ced is approximatedby a negative power of two, thenthis canbe computedusing a shift instructioninsteadof a divide instruction.

Figure 17 gives the pseudocodefor an efficient ver- sion of the RED gateway algorithm. This is just onesug- gestionfor an efficient versionof the RED gateway algo- rithm. Themostefficient way to implementthis algorithm depends,of course,on the gateway in question.

The memoryrequirementsof the RED gateway algo- rithm aremodest.Insteadof keepingstatefor eachactive connection,the RED gateway requiresa small numberof fixedandvariableparametersfor eachoutputline. This is not a burdenon gateway memory.

12 Further work and conclusions

RandomEarly Detectiongatewaysareaneffective mech- anismfor congestionavoidanceat the gateway, in coop- eration with network transportprotocols. If RED gate- ways drop packetswhenthe averagequeuesize exceeds themaximumthreshold,ratherthansimply settinga bit in packet headers,thenRED gatewayscontrolthecalculated averagequeuesize. This actionprovidesan upperbound on theaveragedelayat thegateway.

The probability that the RED gateway choosesa par- ticular connectionto notify during congestionis roughly proportionalto that connection’s shareof the bandwidth at thegateway. This approachavoidsa biasagainstbursty traffic atthegateway. For REDgateways,therateatwhich the gateway markspackets dependson the level of con- gestion,avoiding the global synchronizationthat results from many connectionsdecreasingtheir windows at the sametime. The RED gateway is a relatively simplegate- way algorithmthat could be implementedin currentnet- works or in high-speednetworks of the future. The RED gateway allows consciousdesigndecisionsto be made abouttheaveragequeuesizeandthemaximumqueuesize allowedat thegateway.

Initialization:[]\k^ f ��M��eb�7 f ?�G for each packet arrival:

calculate the new average queue size []\_^ : if the queue is nonempty[]\_^ f []\_^@� I K 68A�? [k\k^ E else using a table lookup:[]\_^ f 6�GU?qILK�EONQP(RQSUTWV K P(R$SUT:X8YOZ []\k^

if ;>9Cb P8a�w []\k^�y ; []` P8a increment

�M��eb�7ced f�h j � []\k^ ? h l if

�M��eb�7g ¡� and

if �M��eb�7 n � (choosing random number){ f {�[ b�~]��;q� � r GM�

else if ; []` P8a�w []\k^

mark the arriving packet�M��eb�7 f ?�G else

�M��eb�7 f ?�G when queue becomes emptyA 7:9<;D= f 7:9<;>= New variables:{ : a random number New fixed parameters:4 : typical transmission time

Figure17: Efficient algorithmfor RED gateways.

There are many areasfor further researchon RED gateways. The foremostopen questioninvolves deter- mining the optimum averagequeuesize for maximizing throughputandminimizingdelayfor variousnetwork con- figurations.Thisquestionis heavily dependentof thechar- acterizationof the network traffic aswell ason the phys- ical characteristicsof the network. Somework hasbeen donein thisareafor othercongestionavoidancealgorithms [23], but therearestill many openquestions.

Oneareafor further researchconcernstraffic dynam- ics with a mix of Drop Tail andRED gateways,aswould result from partial deployment of RED gateways in the currentinternet. Another areafor further researchcon- cernsthe behavior of the RED gateway machinerywith transportprotocols other than TCP, including open- or closed-looprate-basedprotocols.

As mentionedin Section10,thelist of packetsmarked by theREDgatewaycouldbeusedby thegatewayto iden- tify connectionsthat arereceiving a large fraction of the

bandwidththroughthe gateway. The gateway could use this informationto give suchconnectionslower priority at thegateway. We leave this asanareafor furtherresearch.

We do not specifyin this paperwhetherthequeuesize shouldbe measuredin bytesor in packets. For networks with a rangeof packet sizesat the congestedgateway the differencecanbesignificant.This includesnetworkswith two-way traffic wherethequeueat thecongestedgateway containslarge FTP packets,small TELNET packets,and small control packets. For a network wherethe time re- quired to transmita packet is proportionalto the size of the packet, and the gateway queueis measuredin bytes, the queuesize reflectsthe delay in secondsfor a packet arriving at thegateway.

The RED gateway is not constrainedto provide strict FIFO service.For example,we have experimentedwith a versionof RED gatewaysthatprovidespriority servicefor shortcontrolpackets,reducingproblemswith compressed ACKs.

By controllingtheaveragequeuesizebefore thegate- wayqueueoverflows,REDgatewayscouldbeparticularly usefulin networkswhereit is undesirableto droppackets at the gateway. This would be the case,for example,in runningTCPtransportprotocolsovercell-basednetworks suchasATM. Thereareseriousperformancepenaltiesfor cell-basednetworksif a largenumberof cellsaredropped at the gateway; in this caseit is possiblethat many of the cellssuccessfullytransmittedbelongto a packet in which somecell was droppedat a gateway [30]. By providing advancewarningof incipient congestion,RED gateways canbeusefulin avoiding unnecessarypacket or cell drops at thegateway.

Thesimulationsin thispaperusegatewayswherethere is oneoutputqueuefor eachoutputline, asin mostgate- ways in currentnetworks. RED gateways could also be usedin routerswith resourcemanagementwheredifferent classesof traffic aretreateddifferentlyandeachclasshas its own queue[6]. For example,in a routerwhereinter- active (TELNET) traffic andbulk data(FTP)traffic arein separateclasseswith separatequeues(in orderto give pri- ority to theinteractivetraffic), eachclasscouldhaveasep- arateRandomEarly Detectionqueue. The generalissue of resourcemanagementat gatewayswill beaddressedin futurepapers.

13 Acknowledgements

We thankAllyn Romanow for discussionson RED gate- ways in ATM networks, and we thank Vern Paxsonand the refereesfor helpful suggestions.This work could not have beendonewithout StevenMcCanne,who developed andmaintainedour simulator.

References

[1] Bacon,D,. Dupuy, A., Schwartz, J., and Yemimi, Y., “Nest: a Network Simulationand Prototyping Tool”, Proceedingsof Winter 1988 USENIXCon- ference, 1988,pp. 17-78.

[2] Bala, K., Cidon, I., and Sohraby, K., “Conges- tion Control for High SpeedPacket SwitchedNet- works”, INFOCOM ’90, pp. 520-526,1990.

[3] Carta,D., “Two FastImplementationsof the‘Mini- mal Standard’RandomNumberGenerator”,Com- municationsof the ACM, V.33 N.1, January1990, pp. 87-88.

[4] Clark, D.D., Shenker, S., andZhang,L., “Support- ing Real-Time Applicationsin an IntegratedSer- vices Packet Network: Architectureand Mecha- nism”, SIGCOMM ’92, August1992,p. 14-26.

[5] Floyd, S., Connectionswith Multiple Congested Gateways in Packet-Switched Networks Part 1: One-wayTraffic, ComputerCommunicationRe- view, V.21 N.5, October1991,pp. 30-47.

[6] Floyd, S., “Issuesin Flexible ResourceManage- ment for Datagram Networks”, Proceedingsof the 3rd Workshopon Very High SpeedNetworks, March,1992.

[7] Floyd, S., and Jacobson,V., On Traffic PhaseEf- fects in Packet-Switched Gateways, Internetwork- ing: ResearchandExperience,V.3 N.3, September 1992,p.115-156.

[8] Floyd, S., and Jacobson,V., The Synchronization of Periodic Routing Messages, to appearin SIG- COMM 93.

[9] Hansen,A Table of Seriesand Products, Prentice Hall, EnglewoodCliffs, NJ, 1975.

[10] Harvey, A., Forecasting, structural time series modelsand the Kalman filter, CambridgeUniver- sity Press,1989.

[11] Hashem,E., “Analysisof randomdropfor gateway congestioncontrol”, ReportLCSTR-465, Labora- tory for ComputerScience,MIT, Cambridge,MA, 1989,p.103.

[12] Hoeffding, W., Probability Inequalitiesfor Sumsof BoundedRandomVariables, AmericanStatistical AssociationJournal,Vol. 58, March 1963, p. 13- 30.

[13] Hofri, M., ProbabilisticAnalysis of Algorithms, Springer-Verlag,1987.

[14] Jacobson,V., CongestionAvoidanceand Control, Proceedingsof SIGCOMM ’88, August1988,pp. 314-329.

[15] Jain,R., “A Delay-BasedApproachfor Congestion Avoidancein InterconnectedHeterogeneousCom- puter Networks”, ComputerCommunicationRe- view, V.19 N.5, October1989,pp. 56-71.

[16] Jain, R., “CongestionControl in ComputerNet- works: Issuesand Trends”, IEEE Network, May 1990,pp. 24-30.

[17] Jain, R., “Myths About CongestionManagement in High-SpeedNetworks”, Internetworking: Re- searchand Experience,V.3 N.3, September1992, pp. 101-114.

[18] Jain, R., and Ramakrishnan,K.K., Congestion Avoidance in Computer Networks with a Con- nectionless Network Layer: Concepts, Goals, and Methodology, Proc.IEEE Comp.Networking Symp.,Washington,D.C., April 1988,pp.134-143.

[19] Keshav, S., “REAL: a Network Simulator”, Re- port 88/472, ComputerScienceDepartment,Uni- versityof Californiaat Berkeley, Berkeley, Califor- nia, 1988.

[20] Keshav, S., “A Control-TheoreticApproach to Flow Control”, Proceedingsof SIGCOMM ’91, September1991,p.3-16.

[21] Mankin, A. and Ramakrishnan,K. K., editors for the IETF PerformanceandCongestionControl Working Group,“Gateway congestioncontrol sur- vey”, RFC1254,August1991,p.21.

[22] Mishra,P., andKanakia,H,. “A Hop by Hop Rate- basedCongestionControl Scheme”,Proceedings of SIGCOMM ’92, August1992,p.112-123.

[23] Mitra, D. and Seery, J., Dynamic AdaptiveWin- dows for High SpeedData Networks: Theory and Simulations, Proceedingsof SIGCOMM ’90, September1990,p.30-40.

[24] Mitra, D. and Seery, J., Dynamic AdaptiveWin- dowsfor High SpeedData Networkswith Multiple Pathsand Propagation Delays, Proc.IEEE INFO- COM ’91, pp. 2B.1.1-2B.1.10.

[25] Pingali,S.,Tipper, D., andHammond,J.,“The Per- formanceof Adaptive Window Flow Controlsin a DynamicLoad Environment”,Proc.of IEEE Info- com’90, June1990,pp. 55-62.

[26] Postel, J., “Internet Control MessageProtocol”, RFC792,September1981.

[27] Prue,W., andPostel,J., “Somethinga Host Could Do with SourceQuench”,RFC1016,July 1987.

[28] Ramakrishnan,K.K., Chiu, D., andJain,R., “Con- gestionAvoidancein ComputerNetworks with a ConnectionlessNetwork Layer, Part IV: A Selec- tive Binary FeedbackSchemefor GeneralTopolo- gies”, DEC-TR-510,November, 1987.

[29] Ramakrishnan,K.K., and Jain, Raj, “A Binary FeedbackSchemefor CongestionAvoidance in ComputerNetworks”, ACM Transactionson Com- puterSystems,V. 8, N. 2, pp. 158-181,1990.

[30] Romanow, A., “Some PerformanceResults for TCPoverATM with Congestion”,to appearin Sec- ond IEEE Workshopon Architectureand Imple- mentationof High PerformanceCommunications Subsystems(HPCS93), Williamsburg, VA, Sept. 1-3, 1993.

[31] Sanghi,D., andAgrawala,A., “DTP: An Efficient TransportProtocol”, University of Maryland tech reportUMIA CS-TR-91-133,October1991.

[32] Shenker, S., “Commentson the IETF performance and congestioncontrol working group draft on gateway congestioncontrolpolicies”,unpublished, 1989.

[33] Wang, Z., and Crowcroft, J., “A New Congestion Control Scheme:Slow Start and Search(Tri-S)”, ComputerCommunicationReview, V.21 N.1, Jan- uary1991,pp. 32-43.

[34] Wang,Z., andCrowcroft, J., “Eliminating Periodic Packet Lossesin the 4.3-TahoeBSD TCP Conges- tion Control Algorithm”, ComputerCommunica- tion Review, V.22 N.2, April 1992,pp. 9-16.

[35] Young, P., Recursive Estimationand Time-Series Analysis,Springer-Verlag,1984,pp. 60-65.

[36] Zhang,L., “A New Architecturefor Packet Switch- ing Network Protocols”,MIT/LCS/TR-455,Labo- ratory for ComputerScience,MassachusettsInsti- tuteof Technology, August1989.

[37] Zhang,L., andClark, D., “Oscillating Behavior of Network Traffic: A CaseStudy Simulation”, In- ternetworking: Researchand Experience,Vol. 1, 1990,pp. 101-112.

[38] Zhang,L., Shenker, S., and Clark, D., “Observa- tionson theDynamicsof a CongestionControlAl- gorithm: The Effects of Two-Way Traffic”, SIG- COMM ’91, September1991,pp. 133-148.

A Appendix

In this sectionwe give thestatisticalresultusedin Section 10 on identifying misbehaving users.

Let «¬ , G w�®�w b , beindependentrandomvariables, let ¯ betheir sum,andlet °«±n²¯³� b . Theorem 1 (Hoeffding, 1963) [12, p.15] [13, p.104]: Let« j , « l ,..., «�´ be independent,and let � w « ¬ w G for all « ¬ . Thenfor � w 7 w GU?�µ�� °« � ,¶@· �5¸F� °« �Bµ�� °« � � 7<� (4)

w ¹»º½¼¼ � 7F¾À¿FÁ P º GU? ¼GU? ¼ ?q7F¾ j V ¿ V�PCÂ ´

w = V l ´ P(Ã vÄ Let « R8Å ¬ beanindicatorrandomvariablethatis 1 if the® th marked packet is from connection9 , and0 otherwise.

Then ¯ R(Å ´�n ´Æ¬¨ÇÈj « R8Å ¬ v FromTheorem1,¶@· �5¸F6 ¯ R(Å ´ � c R b � 7�b³E w = V l ´ P(Ã for

� w 7 w GU? c R . Thus¶@· �5¸F6 ¯ R8Å ´ �B� c R b³E w = V l ´ N$É¨V j X(Ã o ÃÊ for

G w � w G �Oc R .