random early detection gateways for congestion avoi

RandomEarlyDetectionGatewaysforCongestionAvoidanceSallyFloydandVanJacobson∗LawrenceBerkeleyLaboratoryUniversityofCaliforniafloyd@@ppearintheAugust1993IEEE/ACMTransactionsonNetworkingAbstractThispaperpresentsRandomEarlyDetection(RED)ewaycouldnotifyconnectionsofcongestioneitherbydreaveragequeuesizeexceedsapresetthreshold,thegatewaydropsormarkseacharrivingpacketwithacertainprobability,ewayskeeptheavercongestion,theprobabilitythatthegatewaynotifiesaparticularconnectiontoreduceitswindowisroughlyproportionaltothatconnection’ewaysaredesigngatewayhasnobiasagainstburstytrafficandavoidstheglobalsyntionsofaTCP/IPnetworkareusedtoillustratetheperformanceofREDgateways.1IntroductionInhigh-speednetworkswithconnectionswithlargedelay-bandwidthproducts,gatewaysarelikelytobedesignedwithcourrentInternet,theTCPtransportprotr,itwouldclearlybeundesirabletohavelargequeues(possiblyontheorderofadelay-bandwidthproduct)thatwerefullmuchofthetime;thiswouldsignifiore,withincreasinglyhigh-speednetworks,itisincreasinglyimportabsenceofexplicitfeedbackfromthegateway,thereareanumberofmechanismsthathavebeenproposedfortransportheseproposedmechanismsaredesignedtoworkwithcurrentgateways[15,23,31,33,34],whileothermechanismsarecoupledwithgatewayschedulingalgorithmsthatrequireper-connectionstateinthegateway[20,22].Intheabsenceofexplicitfeedbackfromthegateway,transport-layerprotocolscouldinfercongestionfromtheestimatedbottleneckservicetime,fromchangesinthroughput,fromchangesin

1INTRODUCTION2end-to-enddelay,heless,theviewofanindividualconnectionislimitedbythetimescalesoftheconnection,thetrafficpatternoftheconnection,thelackofknowledgeofthenumberofcongestedgateways,thepossibilitiesofroutingchanges,aswellasbyotherdifficulewaycanreliaegatewayhasaunifiedviewofthequeueingbehaviorovertime;theperspectiveofindividualcotion,agatewayissharedbymanyactiveconnectionswithawiderangeofroundtriptimes,tolerancesofdelay,throughputrequirements,etc.;decisionsaboutthedurationandmagnitudeoftransienhodofmonitoringtheaveragequeuesizeatthegateway,andofnotifyingconnectionsofincip-ientcongestion,isbasedoftheassumptionthatitwillcontinuetobeusefultohavequeuesatthegatewaywheretrafficfromanumberofconnectionsismultiplexedtogether,yisFIFOschedulingusefulforsharingdelayamongconnections,reducingdelayforaparticularconnectionduringitsperiodsofburstiness[4],butitscaleswellandiseasytoimplementeffiternateapproach,somecongestioncontrolmechanismsthatusevariantsofFairQueueing[20]orhop-by-hopflowcontrolschemes[22]proposethatthegatewayschedulidsuggestinsteadthatper-connectiongatewaymechanismsshouldbeusedonlyinthosecircumstanceswheregatewayschedulibitcongestionavoidancescheme[18],describedlaterinthispaper,isanearlyexampleofcongestiondetectionatthegateway;DECbitgatewaysgiveperproposesadifferentcongestionavoidancemechanismatthegateway,RED(RandomEarlyDetection)gateways,withsomewhatdifferentmethodsfordetectingcheprinciplesbehindREDgatewaysarefairlygeneral,andREDgatewayscanbeusefulincon-trollingtheaveragequeuesizeeveninanetworkwherethetransportprotocolcannotbetrustedtobecooperative,REDgatewaysareintendedforanetworkwherethewaycongestioncontrolmechanisminREDgatewayssimplifiesthecongestioncontroljobrequiredofthetransportprotocol,andshouldbeapplicabletotransport-layerconges-tioncontrolmechanismsotherthanthecurrentversionofTCP,includingprotocolswithrate-basedratherthanwindow-basedflr,someaspectsofREDgatewaysarespecificallytargetedtoTCP/gate-wayisdesignedforanetworkwhereasinglemarkedordroppedpacketissufficdifferentfromtheDECbitcongestioncontrolscheme,wherethetransport-layerprotocolcomputesthetion,theemphasisonavoidingtheglobalsynchronizationthatresultsfrommanyconnectionsreducingtheirwindowsatthesametimeisparticularlyrelevantinanetworkwith4.3-TahoeBSDTCP[14],whereeachconnectiongoesthroughSlow-Start,reducingthewindowtoone,ECbitcongestioncontrolscheme,forexample,whereeachconnection’sresponsetocon-gestionislesssevere,ewayscanbeusefulingatmple,REDcongestioncontrolmechanismscouldbeimplementedingatewayswithdroppreference,wherepacketsaremarkedaseither“essential”or“optional”,and“optional”packetsaredroppedfirly,foragatewaywithseparatequeuesforrealtimeandnon-realtimetraffic,forexample,REDcongestioncontrolmechanismscouldbeappliedtothequeueforoneofthesetrafficclasses.

2PREVIOUSWORKONCONGESTIONAVOIDANCEGATEWAYS3TheREDcongestioncontrolmechanismsmonitortheaveragequeuesizeforeachoutputqueue,and,us-ingrandomization,-livedcongestionisreflectedbyanincreaseinthecomputedaveragequeuesize,andresultsinbabilitythataconnectionisnotifiedofcongestionisproportionaltothatconnection’ysthatdetectcongestionbeforethequeueoverflowsarenotlimewayscanmarkapacketbydroppingitatthegatewayorbysettingabitinthepacketheader,eaveragequeuesizeexceedsamaximumthreshold,atewaysmarkpacketsbydroppingthem,ratherthanbysettingabitinthepacketheader,whentheaveragequeuesizeexceedsthemaximumthreshold,thentheREDgatewaycontrolstheantageofagatewaycongestioncontrolmechanismthatworkswithcurrenttransportprotocols,andthatdoesnotrequirethatallgatewaysintheinternetusethesamegatewaycongestioncontrolmecha-nism,ewaysareasimplemechanismforcongestionavoidancethatcouldbeimplementedgraduallyincurrentTCP/n2discussespreviousresean4presentstheREDgatewayalgorithm,n6discussesindetailtheparametersusedincalculatingtheaveragequeuesize,andSection7disn8examinestheperformanceofREDgateways,includingtherobustnessofREDgatewaysforarangeoftraffitionsinSection9demonstrate,amongotherthings,theREDgateway’slackofbiasagainstburstytraffin10describeshowREDgatewayscanbeusedtoidentifythoseuserstn11discussesmethodsforeffin12givesconclusionsanddescribesareasforfuturework.2Previousworkoncongestionavoidancegateways2.1EarlyRandomDropgatewaysSeveralresearchershavestudiedEarlyRandomDropgatewaysasamethodforprovidingcongestionavoid-anceatthegateway.1Hashem[11]discussessomeoftheshortcomingsofRandomDrop2andDropTailgateways,andbrieflmplementationofEarlyRandomDropgatewaysin[11],ifthequeuelengthexceedsacertaindroplevel,thenthegatewaydropseachpacketarrivingatthegatewaywithafi[11]stressesthat

2PREVIOUSWORKONCONGESTIONAVOIDANCEGATEWAYS4infutureimplementationsthedroplevelandthedropprobabilityshouldbeadjusteddynamically,dependingonnetworktraffi[11]pointsoutthatwithDropTailgatewayseequeueoverflows,packetsareoftendroppedfromseveralconnections,ershowsthatEarlyRandomDropgatewayshaveabroaderviewoftrafficdistributiontersuggeststhatbecauseofthisbroaderviewoftrafficdistribution,EarlyRandomDropgatewaysclusionsin[11]versionofEarlyRandomDropgatewaysusedinthesimulationsin[36],ifthequeueismoreth[36]showsthatthisversionofEarlyesimulations,withbothRandomDropandEarlyRandomDropgateways,themisbehavingusersreceivedroughly75%ewayCongestionControlSurvey[21]veycitestheresultsinwhichtheEarlyRandomDropgatewayisunsuccessfulincontrollingmisbehavingusers[36].Asmentionedin[32],EarlyRandomDropgatewaysarenotexpectedtosolvealloftheproblemsofunequalthroughputgivencon[21],thegoalsofEarlyRandomDropgatewaysforcongestionavoidancearedescribedas“uniform,dynamictreatmentofusers(streams/flows),oflowoverhead,andofgoodscalingcharacteristicsinlargeandloadednetworks”.Itisleftasanopenquestionwhetherornotthesegoalscanbeachieved.2.2OtherapproachestogatewaymechanismsforcongestionavoidanceEarlydescriptionsofIPSourceQuenchmessagessuggestthatgatewayscouldsendSourceQuenchmes-sagestosourcehostsbeforethebufferspaceatthegatewayreachescapacity[26],posal[27]suggeststhatthegatewaysendSourceQuenchmessageswhenthequeuesizeexceedsacertainthreshold,andoutlinesapossiblemethodforflposalalsosuggeststhatwhenthegatewayqueuesizeapproachesthemaximubitcongestionavoidancescheme,abinaryfeedbackschemeforcongestionavoidance,isde-scribedin[29].IntheDECbitschemethegatewayusesacongestion-indicatioacketarrivesatthegateway,thegatewaycal-culatestheaveragequeuelengthforthelast(busy+idle)periodplusthecurrentbusyperiod.(Thegatewayisbusywhenitistransmittingpackets,andidleotherwise.)Whentheaveragequeuelengthexceedsone,thenthegatewayserceuseswindowflowcontrol,asthalfofthepacketsinthelastwindowhadthecongestionindicationbitset,ise,reseveralsignificantdifferfietheDECbitschemechoosesthelast(busy+idle)cycleplusthecurrentbusyperiodforaveragingthequeuesize,-speednetworkswithlargebuffersatthegateway,itwouldbedesirabletoexplicitlycontrolthetimeconstantforthecomputedaveragequeuesize;[29]theauthorsreportthattheyrejectedtheideaofaweightedexponentialrunningaverageofthequeuelengthbecausewhenthetimeintervalwasfarfromtheroundtriptime,oblemof

3DESIGNGUIDELINES5biasdoesnotarisewithREDgatewaysbecauseREDgatewaysusearandomizedalgorithmformarkingpackets,andassumetbitnetwork,thesourcelooktworkwithREDgateways,ddifferencebetweenDECbitgatewaysandREDgateECbitschemethereisnoconceptualseparationbetweenthealgorithmtacketarrivesatthegatewayandthecomputedaveragequeuesizeistoohigh,eofthismethodformarkingpackets,DECbitnetworkscanexhibitabiasagainstburstytraffic[seeSection9];thisisavoidgestionavoidancegatewaysdesignedtoworkwithTCP,anadditionalmotivationforusingrandomizationinthemethodformarkingpacketsistoavoidtheglobalsynchronizationthlessofaconcerninnetworkswiththeDECbitcongestionavoidancescheme,whereeacrproposalforadaptivewindowschemeswherethesourcenodesincreaseordecreasetheirwin-dowsaccordingtofeedbackconcerningthequeuelengthsatthegatewaysispresentedin[25].EachgatewayhasanupperthresholdUTindicatingcongestion,enodeincreasesitswindowonlueuelengthisabovetheupperthresholdforanyqueuealongthepath,advantageofthisproposalisthatthenetworkrespondstotheinstantaneousqueuelengths,evethatthisschemewouldbevulnerabletotrafficphaseeffectsandtobiasesagainstburstytraffic,andwouldnotaccommodatetransientincreasesinthequeuesize.3DesignguidelinesThissngoaonalgoalsincludetheavoidanceofglobalsynchronizationandofabiasagainstburstytrafficandtheabilitytomaintainanupperboundontheaveragequefirstjobofacongesfinedin[18],acongestionavoidanragequeuesizeshouldbekeptlow,whilefluctuationsintheactualqueuesizeshouldbeallowedtoaccommodateburstytraffiethegatewaycanmonitorthesizeofthequeueovertime,ethegatewayhasaunifiedviewofthevarioussourcescontributingtothiscongestion,thegatewayisalsoworkwithconnectionswitharangeofroundtriptimes,throughputrequirements,anddelaysensitivities,thegatewayisthemostappropriateagenttodeterminethesizeanddurewaycandothisbycontrollingthetimeconstantsusedbythelow-passfilofthegatewayistodetectincipientcongestionthathaspersistedfora“longtime”(severalroundtriptimes).Thesecondjobofacongestionavoidancegaestionisdetectedbeforethegatewaybufferisfull,itisnopaper,wesaythatthegatewaymarksapacket,

4THEREDALGORITHM6andnotifirkingandnotificationcanconsistofdroppingapacket,settingabitinapacketheader,rentfeedbackmechanisminTCP/IPnetworksisforthegatewaytodroppackets,listoavoidabiasagainstburstytraffikscontainconnectionswitharangeofbursti-ness,andgatewayssuchasDropTailandRandomDropgatewayshaveabiasagainstburstytraffiopTailgateways,themoreburstythetrafficfromaparticularconnection,themorelikelyitisthatthegatewayqueuewilloverflowwhenpacketsfromthatconnectionarriveatthegateway[7].Anothergoalindecidingwhichconnectionstonotifyofcongestionistoavoidtheglobalsynchroniza-tionthatresusynchro-nizationhasbeenstudiedinnetworkswithDropTailgateways[37],onizationasageneralnetworkphenomenahasbeenexploredin[8].Inordertoavoidproblemssuchasbiasesagainstburstytrafficandglobalsynchronization,congestionavoidancegatewayscanusedistinctalgorithmsforcongestiongatewayusesrandomizationinchoosingwhicharrivingpacketstomark;withthismethod,theprobabilityofmarkingapacketfromaparticularconnectionisroughlyproportionaltothatconnection’thodcanbeefficienlforacongestionavoidancegatewayistheabilitytnbedoneifthegatewaydropsarrivingpacketswhentheaveragequeuesizeexceedssomemaximumthreshold(ratherthansettingabitinthepacketheader).Thismethodcouldbeusedtocontroltheaveragequeuesizeevenifmostconnectionslastlessthanaroundtriptime(ascouldoccurwithmodifiedtransportprotocolsinincreasinglyhigh-speednetworks),andevenifconnectiogatewaycalculatestheaveragequeuesize,usingalow-passfiragequeuesizeiscomparedtotwothresholds,eaveragequeuesizeislessthantheminimumthreshold,eaveragequeuesizeisgreaterthanthemaximumthreshold,edpacketsareinfactdropped,orifallsourcenodesarecooperative,thisensuresthattheaveragequeuesizedoesnotsignifieaveragequeuesizeisbetweentheminimumandthemaximumthreshold,eacharrivingpacketismarkedwithprobabilitypa,methatapacketismarked,theprobabilitythatapacketismarkedfromaparticularconnectionisroughlyproportionaltothatconnection’orithmforcomputingtheaveragequeuesizedeorithmforcalculatingthepacket-markingprobabilitydetermineshowfrequentlythegatewaymarkspackets,lisforthegatewaytomarkpacketsatfairlyevenly-spacedintervals,inordertoavoidbiasesandtoavoidglobalsynchronization,andtomarkpacketssuffin11discusseseffieway’scalculationsoftheaveragequeuesizetakeintoaccounttheperiodwhenthequeueis

5ASIMPLESIMULATIONforeachpacketarrivalcalculatetheaveragequeuesizeavgifminth≤avg

5ASIMPLESIMULATIONInitialization:avg←0count←−1foreachpacketarrivalcalculatethenewaveragequeuesizeavg:ifthequeueisnonemptyavg←(1−wq)avg+wqqelsem←f(time−q8time←timeSavedVariables:avg:averagequeuesizeq

andsinknodesimplementacongestioncontrolalgorithmequivalenttothatin4.3-TahoeBSDTCP.3Briefly,holdissetinitiallytohalfthereceiver’low-startphase,thecurrentwiecongestion-avoidancephaseisentered,andowisneverallowedtoincreasetomorethanthereceiver’sadvertisedwindow,whichthispaperreferstoasthe“maximumwindowsize”.In4.3-TahoeBSDTCP,packetloss(adroppedpacket)istreatedasa“congestionexperienced”rcereactstoapacketlossbysettingthethresholdtohalfthecurrentwindow,decreasingthecurrentwindowtoonepacket,u-lationcontainsfourFTPconnections,eachwithamaximumwindowroughlyequaltothedelay-bandwidthproduct,gatewayparametersaresetasfollows:wq=0.002,minth=5packets,maxth=15packets,andmaxp=1/fersizeissufficientlylargethatpacketsareneverdroppedatthegatewayduetobufferoverflow;inthissimulationtheREDgatewaycontrolstheaveragequeuesize,chartsinFigure3,thefourmainrowsshowsthepacketsfromoneofthefourconnections;thebottomrowshowsnode1packets,samarkforeachdatapacketasitarrivesatthegatewayandasitdepartsfromthegateway;atthistimescale,-axisisafunctionofthepacketsequencenumber;forpacketnumbernfromnodei,they-axisshowsnmod90+(i−1),eachvertical‘line’represents90con‘X’showsapacketdroppedbythegateway,andeach‘X’1startssendingpacketsattime0,node2startsafter0.2seconds,node3startsafter0.4seconds,chartofFigure3shotedlinesshowminthandmaxth,atomrowofX’mulationshowsthesuccessoftheREDgatewayincontrollingtheaumberofconnectionsincreases,herthroughputfortheconnectionswithshorterroundtriptimesisduetothebiasofTCP’swindowincreasealgorithminfavorofconnectionswithshorterroundtriptimes(asdiscussedin[6,7]).ForthesimulationinFigure3theaveragelinkutilizationis76%.Forthefollowingsecondofthesimulation,whenallfoursourcesareactive,theaveragelinkutilizationis82%.(ThisisnotshowninFigure3.)BecauseREDgatewayscancontroltheaveragequeuesizewhileaccommodatingtransientcongestion,REDgatewaysarewell-suitedtoprovidehighthroughputandlowaveragegatewaycanaccommodatetheshortburstinthequeuerequiredbyTCP’sslow-startphase;thusREDgatewayscontroltheaveragequeu5showstheresultsofsimulationsofthenetworkinFigure6withtwoTCPconnections,eachwithamaximumwindowof240packets,re5thex-axisshowsthetotalthroug-axisshowstheaveragequeuesizeinpackets(asseenbyarrivingpackets).

5ASIMPLESIMULATION100Queue10300.00.20.40.60.81.0TimeQueue size (solid line) and average queue size (dashed line).400Packet

Number

(Mod

90)

for

Four

0.00.20.4Time0.60.81.0Figure3:5-secondsimulationswererunforeachof11setsofparametersforDropTailgateways,andfor11setsofparametersforREDgateways;eachmarkinFigure5showstheresultsofoneofthesefiulationswithDropTailgatewayswererunwiththebuffersizerangingfrom15to140packets;asthebuffersizeisincreased,rtoavoidphaseeffectsinthesimulationswithDropTailgateways,thesourcenodetakesarandom

5ASIMPLESIMULATION11FTP SOURCES38ms24ms45ms100Mbps11ms52msGATEWAY45Mbps6SINKFigure4:Simulationnetwork.0Average

Queue2.40.60.8Throughput (%)(‘triangle’ for RED, ‘square’ for Drop Tail)1.0Figure5: SOURCES341ms100Mbps5GATEWAY20ms45Mbps6SINKFigure6:awnfromtheuniformdistributionon[0,t]secondstoprepareanFTPpacketfortransmission,wheretisthebottleneckservicetimeof0.17ms.[7].ThesimulationswithREDgatewayswereallrunwithabuffersizeof100packets,REDgateways,maxthissetto3minth,withwq=0.002andmaxp=1/hedlinesshowtheaveragedelay(asafunctionofthroughput)approximatedby1.73/(1−x)for

6CALCULATINGTHEAVERAGEQUEUELENGTH12thesimulationswithREDgateways,andapproximatedby0.1/(1−x)ssimplenetworkwithTCPconnectionswithlargewindows,thenetworkpower(theratioofthroughputtodelay)opTailgatewayswithasmallmaximumqueue,thequeuedropspacketswhiletheTCPconnectionisintheslow-startphaseofrapidlyincreasingitswindow,therhand,withDropTailgtion,DropTailgatewaysaremorelikelytodroppacketsfrombothconnectionsatthesametime,nthepaper,wediscussgatewayisnotspecificallydesignedforanetworkdominatedbybulkdatatransfer;thisissimplyaneasywaytosimulateincreasingly-heavycongestionatagateway.6CalculatingtheaveragequeuelengthTheREDgatewayusesalow-passfi,theshort-termincreasesinthequeuesizethatresultfromburstytrafficorfromtransientcongestiondonotresultinasignifi-passfilterisanexponentialweightedmovingaverage(EWMA):avg←(1−wq)avg+wqq.(1)Theweightwqdeterminesthetimeconstantofthelow-passficulationoftheaveragequeuesizecanbeimplementedparticularlyefficientlywhenwqisa(negative)poweroftwo,asshowninSection11.6.1AnupperboundforwqIfwqistoolarge,thentheaveragingprocedurewillnotfithatthequeueisinitiallyempty,withanaveragequeuesizeofzero,heLthpacketarrivesatthegateway,theaveragequeuesizeavgLisavgL=i=1∑iwq(1−wq)L−iLi=1L=wq(1−wq)∑i(wqL1.(2)Thisderivationusesthefollowingidentity[9,p.65]:i=1∑ixLi=x+(Lx−L−1)xL+1

6CALCULATINGTHEAVERAGEQUEUELENGTH13200ave_L1510500.0010.0020.003w_q0.0040.0LFigure7:minimumthresholdminth,andgiventhatwewishtoallowburstsofLpacketsarrivingatthegateway,thenwqshouldbechosentosatisfythefollowingequationforavgL

7CALCULATINGTHEPACKET-MARKINGPROBABILITY147Calculatingthepacket-markingprobabilityTheinitialpacket-markingsectionwecomparetwomethodsforcalculatingthefinalpacket-markingprobability,firstmethod,whentheaveragequeuesizeisconstantthenumberofarrivingpacketsbetweenmarkedpacketsisageometricrandomvariable;inthesecondmethodthenumbtialpacket-markingprobabilityiscomputedasfollows:pb←maxp(avg−minth)/(maxth−minth).Thepar1:..................................................................................................................................................................2:....04000Packet Number(top row for Method 1, bottom row for Method 2)5000Figure8:Randomly-markedpackets,1:od1,intermarkingtimeXbethenumberofpacketsthatarrive,afteramarkedpacket,eeachpacketismarkedwithprobabilitypb,Prob[X=n]=(1−pb)n−thMethod1,Xisageometricrandomvariablewithparameterpb,andE[X]=1/onstantaveragequeuesize,desirabletohavetoomanymarkedpacketsclosetogether,antheseeventscanresultinglobalsynchronization,withseveralconnectionsreducingtheirwindowsatthesametime,2:esirablealternativeisforXtobeauniformrandomvariablefrom{1,2,...,1/pb}(assumingforsimplicitythat1/pbisaninteger).Thisisachievedifthemarkingprobabilityforeacharrivingpacketispb/(1−count·pb),wherecountisthcase,