ABSTRACT The Power of Explicit Congestion Notification

AleksandarKuzmanovic

DepartmentofComputerScience

NorthwesternUniversityakuzma@cs.northwestern.edu

ABSTRACT

DespitethefactthatExplicitCongestionNotification(ECN)demon-stratedaclearpotentialtosubstantiallyimprovenetworkperfor-mance,recentnetworkmeasurementsrevealanextremelypoorus-ageofthisoptionintoday’sInternet.Inthispaper,weanalyzetherootsofthisphenomenonanddevelopasetofnovelincentivestoencouragenetworkproviders,end-hosts,andwebserverstoapplyECN.

Initially,weexamineafundamentaldrawbackofthecurrentECNspecification,anddemonstratethattheabsenceofECNindica-tionsinTCPcontrolpacketscandramaticallyhindersystemper-formance.WhilesecurityreasonsprimarilypreventtheusageofECNbitsinTCPSYNpackets,weshowthatapplyingECNtoTCPSYNACKpacketscansignificantlyimprovesystemperformancewithoutintroducinganynovelsecurityorstabilityside-effects.OurnetworkexperimentsonaclusterofwebserversshowadramaticperformanceimprovementovertheexistingECNspecification:throughputincreasesbymorethan40%,whiletheaveragewebresponse-timesimultaneouslydecreasesbynearlyanorderofmag-nitude.

Inlightoftheabovefinding,usinglarge-scalesimulations,mod-eling,andnetworkexperiments,were-investigatetherelevanceofECN,andprovideasetofpracticalrecommendationsandinsights:(i)ECNsystematicallyimprovestheperformanceofallinvesti-gatedAQMschemes;contrarytocommonbelief,thisparticularlyholdsforRED.(ii)TheimpactofECNishighestforweb-onlytrafficmixessuchthatevenagenericAQMalgorithmwithECNsupportoutperformsallnon-ECN-enabledAQMschemesthatweinvestigated.(iii)Primarilyduetomoderatequeuinglevels,thesu-periorityofECNoverotherAQMmechanismslargelyholdsforhigh-speedbackbonerouters,eveninmoregeneraltrafficscenar-ios.(iv)End-hoststhatapplyECNcanexercisetheaboveper-formancebenefitsinstantly,withoutwaitingfortheentireInternetcommunitytosupporttheoption.

CategoriesandSubjectDescriptors

C.2.2[ComputerCommunicationNetworks]:NetworkProto-cols

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.

SIGCOMM’05,August21–26,2005,Philadelphia,Pennsylvania,USA.Copyright2005ACM1-59593-009-4/05/0008...$5.00.

GeneralTerms

Algorithms,Measurement,Performance,Experimentation

Keywords

Explicitcongestionnotification,Congestioncontrol,Activequeuemanagement

1.INTRODUCTION

Formorethanadecade,thenetworkingresearchcommunityhasinvestedenormouseffortsinthedevelopmentofActiveQueueManagement(AQM)algorithmsfortheInternet,withthegoalbe-ingtoallownetworkoperatorstosimultaneouslyachievehighthroughputandlowaveragedelay.Thekeyideaistodetectcon-gestioninitsearlystagesandsignalthisinformationtotheend-points,beforetherouterqueueoverflows.Insuchscenarios,AQMalgorithmsarenotforcedtodroppacketsinordertoimplicitlyno-tifyendpointsaboutthecongestion;instead,theycanmarkpacketsandsendexplicitcongestionnotificationstotheendpoints.Suchexplicitindicationsenablemuchsmootherend-pointcontrol[12],whichinturnsignificantlyimprovessystemperformance[12,23].Similareffortsarebeingundertakentomakebothroutersandend-pointsintheInternetECN-capable[30,31].

Despitetheaboveefforts,recentnetworkmeasurementsrevealanextremelypoorusageofECN.Forexample,experimentsonover84,000webserversintheInternetindicatethatintheyear2000,only1.1%oftheserverswereECN-capable[28],whilethisfractionincreasedtoonly2.1%in2004[27].Moreinterestingly,measurementsfrom[27]revealthatinexperimentswithECN-enabledservers,notasinglepacketwasmarkedbyintermediaterouters.ThisindirectlyindicatesthatthepercentageofroutersthatapplyECN-enabledAQMisprobablyevensmallerthantheabovepercentageofECN-enabledwebservers.

Thecausesoftheabovephenomenonarediverse.Ononehand,deployinganychangeinalargescalesystemsuchastheInternetisanon-trivialengineeringtask.OneofthereasonsforthesmallfractionofECN-enabledendpointsistheexistenceof“broken”firewallsandload-balancersinthecurrentInternet,whichincor-rectlysendaresetinresponsetoaTCPSYNpacketthatusesECNflagsintheTCPheader.Whilethisproblemhasbeenaddressed[14]andthedefecthasbeengraduallyremoved,thisinitialstresssignificantlyreducedtheECNdeploymentratebecauseendpointswerereluctanttoapplyit.

Ontheotherhand,thereasonsforthesmallusageofAQMandECNintheInternetroutersaremoreserious.DespitenumeroustheoreticalandempiricalindicationsthatAQMcanindeedsimul-taneouslyimprovenetworkthroughoutandboundqueuingdelay,questions,doubts,andcounter-opinionsarestillbeingexpressed:

(i)WhyshouldIdroppacketswhenmybuffersarenotfull[26]?;(ii)staticAQMparameterscannothandledynamicnetworktraf-fic[26];(iii)settingAQMparametersistedious,particularlyforwebtraffic[10];(iv)ECNcanimproveperformanceofsomeAQMschemes,butnotothers[23];etc.Althoughsomeoftheaboveissuesareaddressedhereandelsewhere[15],networkprovidersapparentlyarewaitingforamoreuniformandstrongersignalfromtheresearchcommunitybeforeapplyinganychange.

Inthispaper,wedevelopasetofnovelincentivesfornetworkendpoints,bothweb-clientsandservers,toapplyECN;inaddition,wedevelopnovelincentivesfornetworkproviderstoapplyECN-enabledAQMschemes.WeshowthatECNisnotanobstacleforAQMdeployment,assuggestedin[24];moreover,thekeyhypoth-esisofourworkisthatECNshouldbeusedasthedrivingforceforAQMdeployment.

InSection2,weprovidethenecessarybackgroundonECN.Next,inSection3,wepointoutafundamentaldrawbackofthecurrentECNspecificationwhichdropsTCPcontrolpacketsinmo-mentsofcongestion;wearguethatmarkingTCPSYNACKpack-etsatcongestedrouterscansignificantlyimprovethesystemper-formancewithoutinducinganynovelsecurityorstabilitychal-lenges.Section4evaluatestheimpactofthisinnovationontheperformanceofseveralAQMschemesinaweb-browsingenviron-ment.InSection5,wedevelopasimplequeuingmodeltoexplaintheobservedsystembehavior.Section6evaluatesECN’sincre-mentaldeployability,whileSection7presentsasetofexperimentsconductedonaclusterofwebservers.WediscussrelatedworkinSection8.Finally,inSection9,weconclude.

2.BACKGROUND

ExplicitCongestionNotificationisinherentlycoupledwiththeideaofActiveQueueManagement.TheprimarygoalofAQMalgorithms,whichwediscussinmoredetailbelow,istoallownet-workoperatorssimultaneouslytoachievehighthroughputandlowaveragedelaybydetectingincipientcongestion.Thisisachievedbysendingappropriateindicationstotheendpointsbeforethequeueoverflows.However,themethodofinformingsourcesofconges-tionisnotlimitedtodroppingpackets,asisthecasewithnon-AQM-enabledFIFOqueues.Instead,AQM-enabledrouterscanmarkpacketsduringcongestionbysettingtheECNbitinthepack-ets’header,asoriginallyproposedfortheDECbitscheme[32].TheactualnumberandchoiceofpacketsthataremarkedduringcongestiondependsonaparticularAQMpolicy.Therecommen-dationsforTCP’sresponsetoECNareinitiallyproposedin[12],andadditionallyrefinedin[30,31].

2.1NegotiatingECNcapabilities

BeforeanyECN-enableddataexchangecantakeplacebetweentwoendpoints,theyfirsthavetosuccessfullynegotiatetheuseofECN.ECNnegotiationhappensduringtheTCPconnectionsetupphase.TheECN-relatedbitsare(i)ECN-Capable(ECT)and(ii)CongestionExperienced(ECN/CE)bitsintheIPheader,and(iii)ECN-EchobitintheTCPheader.1WeillustratethenegotiationprocedureinFigure1usinganHTTPfiledownloadexample,whichweextensivelyexploitlaterinthepaper.TheclientfirstsetstheECN-EchobitintheTCPheaderofaTCPSYNpacketandsendsthispackettothereceiver.ForaSYNpacket,theECN-Echobitisdefinednotasareturnindicationofcongestion,butinsteadasanindicationthatthesendingTCPisECN-capable[13].Uponreceiv-

theserver,typicallypiggybackingsomedata(aHTTPrequestinourscenario)withtheacknowledgement.However,iftheSYNACKpacketdoesnotreturn(eitherbecausetheTCPSYNpacketislostontheforwardpath,ortheSYNACKpacketislostonthereversepath)beforethetimerexpires,theclientdoublestheretrans-missiontimeoutvalueandre-sendstheTCPSYNpacket.OnceaSYNACKpacketisreceivedattheclientside,theconnectionisassumedtobesuccessfully“admitted”intothesystem.

Considerfirstanon-AQM-basedFIFOqueueattherouter.Thekeyproblemisthatapacketlossaloneisanextremelyunreli-ableindicationthattheflowshouldnotbe“admitted”intothenet-work.TCPflowsaregreedyandtendtoutilizeallpossibleavail-ablebandwidth.Thus,evenasmallnumberof“admitted”greedyTCPflowscancreateanenvironmentwithahighpacketlossprob-ability.Yet,thisdoesnotmeanthatanotherTCPflowcannotbeadmittedintothesystem.Moreover,TCP’sadditive-increasemultiplicative-decrease(AIMD)mechanismenablesallflowstoutilizetheirproportionalfairshareofbandwidthoncetheyarepresentinthesystem.However,intheabsenceofanyexplicitnoti-ficationfromthenetwork,aTCPendpointhasnootheroptionbuttowaitfortheretransmissiontimertoexpire,andtothenre-sendtheTCPSYNpacket.

TheaboveproblemisevenmoreseriouswhenthecongestedrouterappliesanAQMalgorithm,aswedemonstratelaterinthepaper.ThisisbecauseAQMschemesemploymechanismsthatdroppacketsbeforethequeuesizereachesthequeuelimit.Whilesuchmechanismscanhaveremarkableimpactandcansignificantlyimprovesystemthroughputbycontrollingbehaviorofalreadyad-mittedflows[8,16,19,21],theycanproducedevastatingeffectsinscenarioswhereflowsdynamicallyarriveanddepartfromthesystematahighrate.ThishappensbecausethepercentageofthetrafficthatismadeupofSYNACKpacketsfromtheservertotheclientscanbequitehigh.Notsurprisingly,ithasbeenexperi-mentallyshownthatforlinkscarryingonlywebtraffic,AQM(e.g.,RED)providesnoclearadvantageoverdrop-tailFIFOforend-userresponsetimes[10].

Unfortunately,theproblemisnotmitigatedbyECNbecauseECNisnotusedinIPheadersofTCPSYNorSYNACKpack-ets.Therefore,inmomentsofcongestion,anECN-enabledrouterdropsTCPSYNandSYNACKpacketsbecausetheECNoptionisnotyetnegotiatedbetweentheendpoints.Surprisingly,wedemon-stratelaterinthepaperthatthecorrespondingperformancedegra-dationcanbeevenworsewhentheAQMschemeisECN-enabled.Below,weexplorepossibilitiesofapplyingECNbitsintheIPheadersofTCPcontrolpackets.

3.2MarkingTCPControlPackets

TheTCP“admissioncontrol”problemcanpotentiallybeallevi-atedbyallowingendpointstosettheECTbitintheIPheadersofTCPSYNorSYNACKpackets.ThatwouldenableECN-basedAQMschemesatrouterstomarkTCPcontrolpackets.However,suchanapproachraisesseveralconcernsthatwediscussbelow.ThereareseveralreasonswhytheECTfieldshouldnotbesetinTCPSYNpackets.First,asindicatedin[13],therearenoguaran-teesthattheotherendpoint(webserverinourscenario)isECN-capable,orthatitwouldbeabletounderstandandreactiftheECN/CEbitsweresetbyacongestedrouter.Second,theECTfieldinTCPSYNpacketsmaybemisusedbymaliciousclientstoimprovethewell-knownTCPSYNattack,wherethegoalistocongestthewebserver’slistenqueuebysendingalargenumberofTCPSYNpackets.BysettingtheECTbitinTCPSYNpacket’sheaders,amaliciousclientwouldbeabletoeasilyinjectalargenumberofTCPSYNpacketsthroughapotentiallycongestedECN-

enabledrouter.Luckily,intypicalclient-serverscenarios(e.g.,webtrafficexamplefromFigure1),congestionismuchmorelikelytohappeninthedirectionoftheservertotheclients.Thus,settingECTbitsinTCPSYNpacketsisnotjustifiedfromtheperformancepointofview.

TherearejustasmanyreasonstosettheECTfieldsinSYNACKpackets.ReferagaintoFigure1.First,whenthewebserverreceivesaTCPSYNpacketwiththeECN-Echobitset,itindicatesthattheclientisECN-capable.Hence,iftheserverisalsoECN-capable,therearenoobstaclestoimmediatelyapplyingECN,andsettingtheECTbitintheSYNACKpacket.Second,settingtheECTbitinSYNACKpacketsdoesnotraisenovelsecurityvul-nerabilities.Forexample,provokingwebserversorhoststosendSYNACKpacketstothirdpartiesinordertoperforma”SYNACKflood”attackwouldbegreatlyinefficient.Thisisbecausethethirdpartieswouldimmediatelydropsuchpackets,sincetheywouldknowthattheydidn’tgeneratetheTCPSYNpacketsinthefirstplace.Moreover,suchattackswouldhavethesamesignaturesastheexistingTCPSYNattacks.Also,provokingwebserversorhoststoreplywithSYNACKpacketsinordertocongestacertainlinkwouldalsobehighlyinefficientbecauseSYNACKpacketsaresmallinsize.Suchattackswouldbeseveralordersofmagni-tudeweakerthantheexistingICMPecho-replyDoSattacks.Fi-nally,becausethecongestionislikelytohappenintheserver-to-clientdirection,settingtheECTbitinSYNACKpacketscanhaveatremendousimpactonperformance,asweindeeddemonstratebelow.

3.2.1Reactingets

toECNSignalsinTCPControlPack-TheTCPsendershouldimmediatelysendanHTTPrequestuponreceivingaSYNACKpacket,despitethestateoftheECN/CEbit.Asdiscussedabove,thefundamentalreasonisthattheexistenceofacongestionnotificationisnotavalidindicationthattheflowshouldnotbe“admitted”intothesystem;thatisonlyanecessitywhenpacketlossesareusedtoconveythenetworkstate.Below,wearguethatsuchbehaviordoesnotintroduceanythreattosystemstability.

Therearethreereasonswhytheabovebehaviorwillnotcauseacongestioncollapse.First,ifthenetworkisindeedcongested,thefirstdatapacketwillre-experiencecongestionattherouter,whichwillsettheECN/CEbitinthefirstTCPDATApacket.ThiswillforcethewebclienttosettheECN-EchobitinthecorrespondingTCPACKpacket,whichwillfurthercausethewebservertoini-tiallywaitforatimeoutof3secondsbeforere-sendingthepacket,2andevenlongerifthecongestionpersists.Thus,theexponentialbackoffmechanism,whichisnecessarytoprotectnetworkstabil-ity,isstillinplace.Second,AQMalgorithmsareabletocontrolextremelylargeflowaggregates(e.g.,[19]).Third,wedemonstrateinSection7thateveninanextremelyheavilycongestedscenariocausedbyshort-livedflows,theaboveapproachonlyimprovestheperformancewithoutcausinganystabilitysideeffects.

Finally,todistinguishtheexistingECNspecificationfromtheadditionproposedhere,wenametheaboveschemeECN+.Insum-mary,whilethecurrent+ECNspecificationenablesrouterstomarkdatapackets,ECN,whenenabledatservers,extendsthisfeaturetoTCPSYNACKpackets.Weevaluatebothschemesbelow.

4.

THEIMPACTOFECN+ONAQMPER-FORMANCE

4.1AQMAlgorithms

WhileECN+isagenericextensiontoECNthatshouldimprovetheperformanceofallECN-enabledAQMschemes,wenecessar-ilylimitourperformanceevaluationtoasubsetofAQMschemes.Inparticular,weevaluatetheimpactofECN+onRandomEarlyDetection(RED)[15],RandomExponentialMarking(REM)[8],andProportionalIntegrator(PI)[19].

REDusesaweighted-averagequeuesizeasameasureofconges-tion,andthedrop(mark)ratedependsonminimumandmaximumthresholdparameters(denotedasminthandmaxth,respectively),asfollows:whentheweightedaverageissmallerthanminth,nopacketsaremarkedordropped.Whentheaveragequeuelengthisbetweenminthandmaxth,theprobabilityofmarkingordroppingpacketsvarieslinearlybetween0andamaximumdropprobability(typicallysetto0.1).Iftheaveragequeuelengthexceedsmaxth,allpacketsaremarkedordropped.Reference[15]definesfurtherrefinementsofthescheme.

OfparticularimportanceisthewayREDbehaveswhentheav-eragequeuelengthexceedsmaxth.TheoriginalREDpaper[16]recommendsmarkingthesepacketswhenECNisenabled,whileRFC3168[31]recommendsdroppingpacketsinthesescenarios,eveniftheyareECN-enabled.Thelatterrule,whichweanalyzeinmoredetailbelow,ismotivatedbyaneedtomoreefficientlydealwithnon-responsiveflowsthatignorecongestionindications.Interestingly,wediscoverthatbothoftheaboveimplementationsarerepresentedintoday’sInternet.Forexample,Linuxmachines,whichweuseinourtestbedexperimentsinSection7,mark,byde-fault,allpacketswhentheaveragequeuelengthexceedsmaxth.SomeothervendorsfollowtheRFC3168recommendationmoreclosely,atleastaccordingtothepubliclyavailablespecificationsoftheirequipment.3Becausetheissueofmarkingvs.droppingpack-etsbeyondmaxthimpactsthesystemperformanceinanon-trivialmanner,weevaluatebothversionsbelow.

REMandPIapplycontroltheoreticprincipleswhendecidingwhichpacketstodropormark.Bothschemesmeasurethedif-ferencebetweenthetargetedandmeasuredqueuelengths,andin-creaseordecreasethemarkingordroppingprobabilityaccordingtoaparticularcontrolfunction(seereferences[8,19]fordetails).Theparametersusedtosetthecontrolalgorithm’stargetedobjec-tivearequeuereference(qref)inPI’scase,andtargetqueuelength(b∗)inREM’s.

4.2ExperimentalMethodology

Next,weconductalargenumberoflarge-scalens-2simulations.Weadoptthemodeldevelopedin[11],andcombineitwiththeem-piricalfile-sizedistributionreportedin[33].Inthismodel,clientsinitiatesessionsfromrandomlychosenwebsiteswithseveralwebpagesdownloadedfromeachwebsite.Eachwebpagecontainsseveralobjects,eachofwhichrequiresaTCPconnectionforde-livery.WeexploretheeffectsofpersistentHTTPconnectionsinSection7.Theinter-pagetimedistributionisPareto,whilewegen-eratewebfilesizesbyfittingtheempirically-measuredheavy-taileddistributionreportedin[23,33].Whilethemajorityoftheflowsareveryshort,suchthatthemeanfilesizeis7.2kBytes,Gbytesfilesizeswillalsobegeneratedsuchthatthetop15%ofobjectsizesap-proximatelyaccountsfor80%ofthebytessentbyservers[33].Ac-cordingto[23],thecombinationofheavy-taileduser“thinktimes”

100 90)% 80( yti 70libab 60orp 50 evit 40Uncongested networkalum 30RED, no ECN, 90loadRED, with ECN, 90loaduC 20RED, with ECN+, 90loadRED, no ECN, 105load 10RED, with ECN, 105load 0RED, with ECN+, 105load 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2Response Time (sec)

Figure2:REDperformance

allpacketswhentheaveragequeuelengthexceedsmaxth.

ThekeyinsightsfromFigure2arethefollowing.First,notethatECN+indeedsignificantlyimprovestheperformanceofRED.ThisisbecausetheSYNACKpacketsaremarkedintheECN+case,andnotdropped,asintheECNcase.Thus,anumberofunnec-essarytimeoutsareavoided,andtheperformanceimprovementsareevidentinthefigure,bothfor90%and105%loads.How-ever,becauseallpackets,includingSYNACKs,aredroppedwhentheRED’saveragequeuelengthexceedsmaxth,thissignificantlyworsenstheRED’sresponse-timeprofile.

RFC3168motivatesthisrulewithaneedtomoreefficientlydealwithnon-responsiveflowsthatareignoringcongestionindica-tions.However,droppingallpacketsbeyondmaxthcannotprotectagainstnon-responsiveflows.Instead,itcanactuallyaidapoten-tiallymalicioususer.Thisisbecausetheproposedruledegradesallflowsthatsharethebottleneck,notjustthenon-responsiveones.Moresophisticatedmechanisms,suchastheoneproposedin[25],areneededtofirstdetectnon-responsiveflows,andthendroppack-etsexclusivelyfromtheseflows.

100 90)% 80( yti 70libab 60orp 50 evit 40Uncongested networkalum 30RED*, no ECN, 90loadRED*, with ECN, 90loaduC 20RED*, with ECN+, 90loadRED*, no ECN, 105load 10RED*, with ECN, 105load 0RED*, with ECN+, 105load 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2Response Time (sec)

Figure3:RED∗performance

Figure3depictstheperformanceofRED∗inthesamesimula-tionscenariosasabove.ThemoststunningresultiscertainlythehugedegradationofresponsetimesinscenarioswithECN(whenTCPdatapacketsareECN-capable,butSYNACKsarenot).Forexample,for90%load,thefigureshowsthatapproximatelyonly30%oftheflowshaveresponsetimeslessthan0.5sec.Thisisa

significantdegradationfromthescenarioinwhichECNisnotused,wherenearly75%flowshaveresponsetimeslessthan0.5sec.Thisisduetothe“TCPadmissionproblem”discussedabove;wepro-videadditionalinsightsbelow.

TheonlydifferencebetweentheREDandRED∗schemesisthewayinwhichpacketsaretreatedwhentheaveragequeuelengthexceedsmaxth:theyaredroppedbyRED,andmarkedbyRED∗.BecausedatapacketsaremarkedbyRED∗,TCP’send-pointcon-trolbecomeslessresponsive[12],andRED∗’soperatingpoint(av-eragequeuinglength)movesclosertotheupperthresholdmaxth.WhilethiscanincreasethethroughputofECN-enableddatapack-ets,itcanhaveadevastatingeffectonnon-ECN-enabledSYNACKpacketsthatarebeingfrequentlygeneratedbywebserversinre-sponsetoclient’sTCPSYNpackets.BecauseSYNACKpack-etsarenowmuchmorefrequentlydropped,thetimeoutpenaltyisinvokedmoreoften,andthedegradationbecomeshuge.ECN+solvesthisproblembecausewebserversinthisscenariosendECN-enabledSYNACKpacketsthataremarkedbythecongestedrouter.Thus,ECN+avoidstheabovedegradation,andFigure3showsthatitsignificantlyimprovessystemperformancewhencomparedtothescenariowithoutECN.+Moreover,inthe90%loadscenario,RED∗’sprofilewithECNcomesveryclosetotheidealizedun-congestedprofile.

4.3.2REMandPI

100 90)% 80( yti 70libab 60orp 50 evit 40Uncongested networkalum 30REM, no ECN, 90loadREM, with ECN, 90loaduC 20REM, with ECN+, 90loadREM, no ECN, 105load 10REM, with ECN, 105load 0REM, with ECN+, 105load 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2Response Time (sec)

Figure4:REMperformance

Figures4and5showtheimpactofECN+onREMandPI,inrepeatedscenariosfromabove.ThekeyinsightfromFigure4isverylowperformanceofREMwithoutECNsupport.How-ever,notethatECNalonecansignificantly+improveREM’sper-formance,whiletheadditionofECNhasvariableimpact.Inthe90%loadscenario,ECN+onlymarginallyimprovesREM’sperformancewithECN,whichindicatesthatREM’smarkingisquiteconservativeinlightlycongestedscenarios.Weanalyzesuchscenariosinmoredepthinthefollowingsection.However,inthe105%loadscenario,thebenefitsofECN+becomemorepro-nounced,andtheappropriatedelaycharacteristicremainsalmostthesameaswhenthecongestionisnotaspersistent.Generally,whenthelevelofcongestionincreases,thebenefitsofECN+aremorepronounced.Thisresultsystematicallyholdsforallschemesexploredinthispaper.ThekeyreasonforthisisthatdroppingSYNACKpacketsonpersistentlycongestedlinkscansignificantlyde-gradesystemperformance;therefore,ensuringthatthosepacketsaremarkedpreventstheabovedegradation.

Figure5depictstheCDFresponse-timeprofileswithPI.While

100 90)% 80( yti 70libab 60orp 50 evit 40Uncongested networkalum 30PI, no ECN, 90loadPI, with ECN, 90loaduC 20PI, with ECN+, 90loadPI, no ECN, 105load 10PI, with ECN, 105load 0PI, with ECN+, 105load 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2Response Time (sec)

Figure5:PIperformance

ECNdoesimprovetheperformance,notethattheimpactofECN+isevenmoreprofound.Moreover,forbothlevelsofcongestion,theclients’responsetimesareveryclosetotheuncongestedscenario.BecausewetreatPIinmoredetailinthefollowingsection,wenowturnourdiscussiontoanotherimportantissue,theimpactofECN+onthroughputatthecongestedrouter.

4.4Throughput

TheprimaryobjectiveofECN+istoaddressTCP’s“admis-sioncontrol”problem,wherethelossofTCPcontrolpacketscanseverelyimpactthesystemperformance+inhighlydynamicenvi-ronments.WhiletheimpactofECNonend-to-enddelayisin-deedsignificantinthepresenceofallAQMschemes,wedemon-stratebelowthattheimpactonthroughputcanalsobesurprisinglyhigh.

Table1summarizesthethroughputresultsforECN+andECNforallAQMschemes.TheimprovementsofECN+overECNaremoremoderateforPI,RED,andREM,wheretheyvaryfrom1%to5%.Thisissomewhatexpected,becauseECN+impactsmostlyshort-livedflowsthatinturncannotimpactthroughputcon-siderably.Nevertheless,itisimportanttonotethattheimpactonthroughputissystematicallypositive,whichmeansthatECN+doesnotimprovetheend-to-endresponse-timecharacteristicbydegradingthroughput.Instead,ECN+exploitsopportunitiesthusfarunexploitedbyAQMschemes.

However,intheRED∗scenario,theimpactofECN+onthrough-putbecomesquitesubstantial,andrangesfrom6%,inthelightcongestionscenario,to20%inthepersistentone.Thekeyrea-sonsforthroughputdegradationintheRED∗/ECNscenarioarethesameasfortheresponse-timedegradation.Insummary,becauseTCPdatapacketsaremarkedbeyondmaxth,theRED∗’soperat-ingpointmovesclosertomaxth,whichfurthercausesasignificantdegradationforshortflowsasSYNACKpacketsareoftendropped.Unfortunately,thesamehappenstolargerflowsthatareforcedtowaitalongtimebeforebeing“admitted”intothenetwork,whichcausessignificantthroughputdegradation.

4.5ComparingDifferentSchemes

Whiletherelationshipamongdifferentschemesisbeyondthescopeofthispaper(seereferences[20,23,24]formorerigorouscomparisonsofvariousAQMschemes,aswellasFIFO),wedoitbecausetheimpactofECN+,whilesystematicallypositive,isnon-uniformfortheevaluatedAQMschemes.Duetospacecon-straints,wedonotshowtheresponse-timecomparisonsfordiffer-

entAQMschemeswithECN+inaseparatefigure.Insummary,whilePIhasthebestperformance,thedifferencebetweenPIandotherschemesissignificantlyreducedinthepresenceofECN+.Also,RED∗’sprofileisalmostidenticaltoREM’s,whileRED*outperformsRED.ThisisbecauseECN+improvesRED∗’sper-formancethemost.

5.UNDERSTANDINGECN+5.1DecouplingECN+fromAQM

ECN+isinherentlycoupledwithAQM.However,whiletheper-formanceofAQMschemeswithandwithoutECNhasbeenex-plored,andwhiletheimpactofECN+onAQMperformanceisevidentlypositive,thequestionis:canECN+bedecoupledfromAQM-specificmechanisms?Inotherwords,ourgoalistoisolatetheimpactofECN+fromsophisticatedmechanismsthatdefinethewaypacketsaredroppedormarkedatthequeue.Reasonsforcon-ductingsuchevaluationsarethefollowing:(i)toemphasizetheimportanceofECN+,(ii)tounderstandtheimpactofnon-ECN-relatedAQMmechanismsonend-to-endperformance,and(iii)tocomparetheimpactsofthetwoinvariousscenarios.

TodecoupleECN+fromspecificAQMdropping/markingmech-anismsweproceedasfollows.Weexploreasimplethreshold-basedAQMalgorithm,whichisdefinedasfollows:whenthetem-poralqueuelengthissmallerthanagivenqueuethreshold,nopacketsaremarked;wheneverthequeuelengthexceedsthethresh-old,allpacketsaremarked.ThisschemeintentionallylacksallfundamentalAQMmechanisms:first,itdoesnotusetheaveragedqueuelengthasanindicationofcongestion,whichisneededtopro-tectfromprematurelysendingcongestionindicationstotheend-points[16];second,ithasasharp“step”markingfunction;there-fore,itlacksanyrandomizationpropertiesandispronetopossi-bleflow-synchronizationeffectsthatcancausesignificantthrough-putdegradations[16];finally,thethresholdschemelackssophisti-catedcontrol-theoreticmechanisms(e.g.,theonesproposedin[8,19]).However,theschemeusesECN+,whichinitializessmoothECN-basedendpointcontroldefinedin[12],andenablesmarkingofSYNACKpackets.Thus,thesystem’sperformancedependssolelyuponthesetwomechanisms.

Toisolate“classical”AQMmechanismsfromECN+,wecom-paretheaboveschemeagainstdroppingPI.DroppingPIpossesesallthefeaturesthattheaboveschemelacks,yetPIinthisscenariolacksthesupportofECN+.ItisimportanttounderstandthatweneithersuggestthatPIshouldnotuseECN+northatoneshouldapplythethresholdscheme.Ourgoalistoevaluatetheimpactofthetwomechanisms.Whilenecessarilynotcomprehensive,theex-perimentsandanalysisbelowprovidevaluableinsightsthatareofpracticalimportance.

5.2WebTrafficMixes

5.2.1LightlyCongestedLinks

AQMalgorithmsaredesignedtocontroldelayandthroughputinpersistentlycongestedscenariosbymarking/droppingpacketsinanefforttostabilizethequeuelengthatatargetedlevel.However,inlightlycongestedscenarios,bothclassicalrandomizationmech-anismsandsophisticatedcontroltheoreticmechanismsmaybeoflimitedimportance.ThisisbecausethetemporalqueuelengthmayonlyoccasionallyexceedtheleveltargetedbyAQM.Thus,tryingtostabilizethequeuelengthinsuchscenariosmaybelessrelevant,becausethequeuingoscillationsarelargelyindependentoftheac-tualAQMmechanisms.Onthecontrary,theuseofECN+(i.e.,

AQMschemeRED/ECNTable1:NormalizedThroughput(%)

RED∗/ECN+REM/ECN

PI/ECN+90%load84.91

95.02

76.62

4

TCPAccording35%flowsto16kBytes,havetomeasurementstheandadvertisedfrom[27],approximately20%oftherestofwindow45%toparameter64kBytes.

setto8kBytes,79.2978.28

86.56

99.73

99.76

thebounddeterminedbyWmax.Thus,becausetheinitialwindowsizeistwopackets[6],andbecauseTCP’sslow-startmechanismdoublesthewindowsizeeachround-trip-time,theflowarrivesintothesysteminnburstsofsizeXs={2,...,2n−1,Rs},whereRs=smod(2n−1).Onthecontrary,largerflowswillnecessar-ilyhitthelimitimposedbythereceiver.Denotebylthe(“large”)filesizeinthisscenario;thefilearrivesintothequeueinburstsofsizeXl={1,2,...,Wmax,...,Wmax,Rl},wheretheac-tualnumberofburstsandtheremainderfactorRlarefunctionsoflandWmax.Finally,bymappingthefile-sizedistributionusingtheabovefile-to-burstsizetransformations,andbyusingthethree-modaldistributionforWmax[27],wecancomputetheburst-sizedistributionXforanygivenflow-sizedistribution.

WejustifythechoiceoftheM[X]/M/1modelasfollows.First,thearrivalprocessisPoissonbecausethisrealisticallymodelshigh-aggregationregimesinwhichburstsfrommanyflowsarriveatthequeue.Thesameargumentjustifiestheassumptionofuncorre-latedburstsizes:burstsproducedbyverylongflowsarelimitedbytheWmaxparameter,andcorrelationamongsuchburstsdimin-ishesduetolargenumbersofotherburststhatoriginatefrommanydifferentsources.Second,themodelassumesthePoissonservicerate.Whiletheservicerate(packets/sec)isclearlydeterministicinpractice,thePoissonassumptionsignificantlysimplifiesouranal-ysishereandatthesametimeonlymoderatelyoverestimatesthequeuelength[17].Finally,wedonotmodeltheimpactofotherbottlenecksthatcanexistonanend-to-endpath.Anydistortionofpacketburstsonsecondarybottleneckswouldnecessarilyleadtoevenshorterqueuelengthsthanmodeledhere.

Denotebyρtheloadonthelink,andbyE(X)andE(X2)thefirstandsecondmomentsoftheburstsize.Then,itcouldbeshownthattheexpectedqueuelength,E(Q),canbeexpressedas

E(Q)=

ρ

2E(X)

.

(1)

Thederivationisgivenin[22].

50

)sM[X]/M/1 model

tk45Simulation

p( 40htg35nel30 eu25euq20 eg15ar10evA500

10203040506070

Length of TCP flows (pkts)

Figure7:Theaveragequeuelengthasafunctionoftheflowlengthforρ=0.8

Figure7showstheexpectedqueuelengthasafunctionoftheflowsize,forafixedload,andinascenariowhereallgeneratedflowsareofthesamesize.Whilenotrepresentativeofanactualscenario,ourgoalhereistoillustrateagoodmatchbetweenthe

modelandsimulations.Thenon-monotonicrelationshipbetweentheaveragequeuelengthandtheTCPflowlengtharisesbecausetheaveragequeuelengthpeakswhentheprobabilityoflargeburstsishighestandnotwhentheaverageburstishighest.Ourresultsherelineupwellwiththeonesreportedin[7],whichareobtainedusingtheM/G/1queuingmodel.

ThekeyinsightfromFigure7isaparticularlymoderatelevelofqueuingwithrespecttothequeuingdelaytypicallytargetedbyAQMschemes[15],despitearelativelyhighutilizationlevel.ThisimpliesalimitedimpactofAQMmechanismsthataimtostabi-lizethequeuelengthatthetargetedlevel;anAQMalgorithmcanachievethisgoalinapersistentlycongestedscenariobysendingmorefrequentcongestionindications,yet,anAQMcannotincreasethequeuelengthinmomentsoftrafficstarvation.Indeed,themeanqueuingdelayinlightlycongestedscenariosmayoftenbebelowtheleveltargetedbyAQMschemes(e.g.,5ms,asproposedin[15]).Forexample,Figure7indicatesthatatypicalweb-browsingaggregate(e.g.,themeanflow-sizeequals7.22packets[33])wouldhaveonlyamoderate(5packets)averagequeuelength.

Whilequiteinsightful,Figure7doesnotcorrespondtoareal-isticflow-sizedistribution.Inaddition,Equation(1)computestheaveragequeuelength,whichcanbequitemisleadinginthecaseofnon-standardqueuingdistributions.Below,weuseourmodelinordertoevaluatetheimpactofarealisticflow-sizedistribution,andalsotonumericallycomputethecorrespondingqueue-sizedis-tribution.

WenumericallysolvethesystemoflinearequationsdefinedbythematrixofM[X]/M/1transitionprobabilities(see[22]forde-tails)asfollows.Westartfromthefile-sizedistributionusedintheprevioussection,whichisinitiallyobtainedfromrepresenta-tiveweb-basednetworkmeasurements[23,33].Next,usingthefile-to-bursttransformationsdevelopedabove,weobtaintheappro-priateburst-sizedistribution,whichenablesustosolvethesystemofM[X]/M/1equationsandobtainthequeuesizedistribution.Fi-nally,wecomputetheprobabilityofthequeuelengthexceedingtheleveltypicallytargetedbyAQMalgorithms,andpresenttheresultsinFigure8.

0.90.8HTTP Traffic, Model, C=100MbpsModel, C=155Mbps0.7

Simulation, C=100MbpsModel, C=622Mbps))C0.6Simulation, C=155Mbps*Simulation, C=622Mbps

sm0.55(>0.4Q(P0.30.20.100.75

0.80.850.90.951

Utilization

Figure8:Probabilitythatthequeuedelayexceeds5msasafunctionofthelinkload(web-trafficscenario)

WedenotethelinkcapacitybyC.Figure8depictsbothmodel-ingandsimulationresultsfortheprobabilitythatthequeuelengthexceedsthe5ms∗Clevel.Figure8depictsthisprobabilityasafunctionofthelinkutilizationρ,andforthelinkcapacitiesof100Mbps,155Mbps,and622Mbps.Inaddition,weperformsim-ulationsonaFIFOqueueforthreedifferentrandomseeds.Figure8showsagoodmatchbetweenmodelingandsimulations,withthedifferencethatinthisscenariothemodelbehavesasanupperboundforthesimulationresults.

ThekeypointfromFigure8isthattheprobabilitythatthequeuelengthexceedsthe5ms∗Cthresholdisindeedverysmall,which,

basedontheabovediscussion,indicatesasimilarimpactofnon-ECN-basedAQMmechanisms.Asexpected,thisimpactincreasesforhigherutilizationlevels,anddecreasesforhigherlink-speeds.Forexample,Figure8showsthatforC=622Mbpsandρ=0.95,theprobabilitythatthequeuelengthexceedsthe5ms∗Cthresholdissmallerthan10%,indicatingthatthecorrespondingcongestionepochsareindeedveryshort.Nevertheless,AQMmechanismsarestillneededtocontroldelayduringtheseepochs,becauseasimpleFIFOqueuelacksanysuchcapabilities[23].However,asindicatedinFigure6,ECN-originatedmechanisms,andmuchlesssophis-ticatedAQMcontrolmechanisms,areresponsibleforend-to-endperformance.Moreover,theuseofECN+isofparticularimpor-tancehere,becauseitpreventsunnecessaryperformancedegrada-tions(e.g.,droppingSYNACKpackets)duringshort-livedconges-tionperiods.

5.2.3PersistentlyCongestedLinks

Here,weincreasetheloadto105%.Thismeansthatthepopula-tionofwebclientsinthisscenarioincreasessuchthattheywouldgeneratealoadof105Mbpsona1Gbpslink.Therefore,thiscre-atesapersistently-congestedenvironmentfora100Mbpslink.WeshowthattheimpactofECN+onwebresponsetimesincreasesinsuchscenarios,whilethetwoschemes(threshold-basedandPI)haveapproximatelythesamethroughput.Below,weexplaintheoriginsofsuchabehavior.

Ourresults(notshownduetospaceconstraints,seereference[22]formoredetails)revealthatthethreshold-basedschemewithECN+outperformsPIwithoutECNbyevenalargermarginthanintheabovelightly-congestedscenario.Thisisbecausemarking,insteadofdroppingpacketsinthisscenariohasanevenlargerim-pactonend-to-endperformance.ThisisparticularlytrueforSYNACKpackets,whicharemarkedinthecaseofECN+.However,amoreinterestingresultistheimpactofbothschemesonnormal-izedthroughput.Itis99.89%inthePIcase,whileitis97.37%fortheECN+-enabledthresholdscheme.WhilePI’scontrolmech-anismsareindeeddevelopedfor,andobviouslyperformwellin,persistently-congestedscenarios,thesurprisingresultisthehighthroughputachievedbythethreshold-basedscheme.Thisisdespitethefactthatitlacksbothgenericanti-randomizationmechanismsaswellasmoreadvancedcontrolmechanisms.Below,weexplainthisphenomenoninmoredetail.

Thekeyreasonsforthehighthroughputachievedbythethreshold-basedschemewithECN+arethefollowing.First,whiledroppingallpacketswhentheinstantaneousqueuelengthexceedsagiventhresholdcanhavedevastatingeffectsonTCP’sperformance,thisisnotnecessarilythecasewhenECNissupported.Thisisbe-causeECN-enabledTCPendpointsreacttotheeventofmultiplemarkedpacketswithinanRTTthesameasifasinglepacketwasdropped[30].Thus,theimpactonthroughputisnotdramatic.Sec-ond,eventhoughshortflowscarryonly20%ofthebytesinourscenario,thefactthatSYNACKpacketsarenotdroppedhaspos-itiveimpactonthroughput.However,thekeyreasonforthegoodperformanceofthisgenericschemeisanobviouslackofsynchro-nizationamonglonger-livedflows.

SynchronizationofTCPflowswasoneofthemotivationsforRED[16].ThemaingoalofREDisavoidingthesynchroniza-tionofmanyTCPflowsthatdecreasetheirwindowatthesametime,andthusdegradethesystemthroughput.Thekeyreasonsfortheabsenceofsynchronizationinourscenario,despitethelackofrandomizationmechanisms,arethefollowing.First,whilewedogeneratelongflowsinoursimulation(accordingtothefilesizedis-tributionreportedin[23,33]),theseflowsareoffinitesize.Thus,theyaredownloadedinfinitetime,whichcansometimesnotbe

longenoughtoallowsynchronization.Second,thefactthatTCPflowsarelimitedbyWmaxadditionallydecreasestheprobabil-itythatsynchronizationwillarise.Next,heterogeneousround-triptimesmayalsoweakentheseeffects.Finally,inlargeaggregationregimes,non-synchronizedgreedyshort-RTTTCPflowsareabletoquicklyfillin“gaps”inducedbypossiblysynchronizedTCPsub-aggregates.

5.3GeneralTrafficMixes

Sofar,bothmodelingandsimulationresultsarebasedonthetracefrom[23,33],whichaccuratelyrepresentsweb-trafficscenar-ios.Here,weextendouranalysistogeneraltrafficmixes,whicharenotlimitedtoonlywebtraffic.

Wemakeabriefsurveyofrecentlyreportedmeasurementsofgeneralflow-sizedistributions,andfindtwosuchrepresentatives.ThefirstisreportedbyGarettoetal.in[17];thedistributionisobtainedfrommeasurementstakenonanaccesslinkofacampusnetwork;theseconddistributionisreportedbyCamposetal.in[9];itisobtainedfrommeasurementsonanOC-48linkbetweenIndianapolisandCleveland,andthetraceispubliclyavailableathttp://pma.nlanr.net/Traces/long/ipls1.html.Whilebothdistribu-tionshave“heavier”tailsthantheaboveweb-baseddistribution,suchthatthepercentageofbytesthatbelongtolong-livedflowsbe-comeslarger,onlythesecondtrace(fromtheOC-48link)revealssomewhatdifferenttrendsfortheimpactofECN+andnon-ECN-basedAQMmechanismsthanreportedabove.Below,wepresentthoseresults,bothforlightlyandpersistentlycongestedscenarios.

5.3.1LightlyCongestedLinks

Here,werepeatthesimulationsforthelightlycongestedsce-nariobyusingthefile-sizedistributionobtainedfromtheaboveOC-48trace.Itisimportanttounderstandthatwedonotsimplyplugthetraceintooursimulator.Instead,weusethefile-sizedis-tributionwhichcorrespondstothistrace,andgenerateinter-arrivaltimesinsimulationstoachieve90%loadona100Mbpslink.

Theresponse-timeprofiles(notshownduetospaceconstraints)forthetwoAQMschemesaresimilartothatofFigure6,whichconfirmsthedominantimpactofECN+onwebresponse-timeper-formance.Thisisbecausethemajorityofflowsintheexperimentarestillshort-lived,eventhoughlongflowscarryapproximately90%ofthebytesinthisscenario.Hence,aheavierflow-size-distributiontailhasnoimpactonwebresponse-timeperformance.Onthecontrary,duetolackofanyrandomizationoranyothercon-trolmechanisms,thethroughputofthethreshold-basedAQMstartstolagbehindPI’smorerapidly:itis76.81%inthethreshold-basedAQMcase,and80.92%forPI.

0.90.8HTTP + longer-size Traffic, C=100MbpsC=155Mbps0.7

Simulation, C=100MbpsC=622Mbps

))C0.6Simulation, C=155Mbps*Simulation, C=622Mbps

sm0.55(>0.4Q(P0.30.20.100.75

0.80.850.90.951

Utilization

Figure9:Probabilitythatthequeuedelayexceeds5msasafunctionofthelinkload(generaltrafficscenario)

Tofurtherunderstandtheabovebehavior,were-applyourmod-elingprocedureandobtainthequeue-sizedistributionthatcorre-

spondstotheabovegeneralfile-sizedistribution.Figure9depictstheprobabilitythatthequeuelengthexceedsthe5ms∗CthresholdtypicallyusedinAQMalgorithms.They-axisinFigure9indi-rectlymeasuresthe“relevance”ofnon-ECN-basedAQMmecha-nisms(PI’sinthisscenario).WhencomparedtoFigure8,Figure9indicateslongerqueuinglengths,particularlyforthe100Mbpsand155Mbpsscenarios.Forexample,for90%loadona100Mbpslink(exactlyourscenariohere),theprobabilitythatthequeuelengthex-ceedsthetargetedAQMthresholdislargerthan0.5.Thisindicatesmorepersistentcongestionlevels,whichinvokePI’scontrolmech-anisms.

Onthecontrary,threshold-basedAQM,despiteECN+support,lacksbasiccontrolmechanisms,andexperiencesmoderatethrough-putdegradations.Whileitiswellknownthatnon-ECN-basedAQMcontrolmechanismsarerequiredtoachievehighthroughputinper-sistentlycongestedenvironmentsdominatedbylong-livedtrafficflows,ourresultsindicatethatsuchmechanismsarerequiredevenformoremoderatecongestionlevels.However,asthelinkspeedincreases,Figure9showsthatdespitehighutilizationlevels,thequeuinglengthsarenotaspersistent.Forexample,forC=622Mbpsand95%utilization,thequeuinglengthsarelight,whilefor90%theyarealmostnon-existentdespiteheavierfile-size-distribution+tail.Thus,ourpreviousanalysisindicatesthatthegenericECNschemewouldworkwellinsuchscenarios.

5.3.2PersistentlyCongestedLinks

Finally,were-createthepersistentlycongestedscenariowith105%loadona100Mbpslink,withthesameflow-sizedistribu-tionasabove.Theresponse-timeprofile(notshowndue+tospaceconstraints)againconfirmsthedominantimpactofECNonend-to-endperformance.However,thethreshold-basedschemedoesnotkeeppacewithPIinthroughput:threshold-basedAQMhasanormalizedthroughputof88.43%,whereasPIachieves96.48%.Asdiscussedabove,alargerpercentageoflong-livedflowsin-creasestheprobabilityofflow-synchronization,whichinturncausesthroughputdegradation.

6.INCREMENTALDEPLOYABILITY

Inthissection,wetreattheproblemofincrementallydeploy-ingECNintheInternet.GiventhatitisimpossibletoforcetheentireInternetcommunitytosimultaneouslyapplyECN,theques-tionishowECN-andnon-ECN-enabledtrafficstreamsaffecteachotherwhentheyaremultiplexed.Tothebestofourknowledge,thisissuehasnotyetbeenexplored.ThekeyproblemwithaddinganynewfunctionalityintheInternetistofulfillthetwofollow-ing,oftencontradictory,requirements:(i)tobe“friendly”totheendpointsthatdonotapplytheinnovation;andconcurrently(ii)achieveperformanceimprovements,whicharenecessarytopro-videareasonableincentiveforendpointstoapplytheinnovationinthefirstplace.Whileitiswell-knownthatECNachievesthefirstfeature,weshowbelowthatECN+(implementedatservers)successfullyaddsthesecond.

Tobecomeeffective,ECNneedstobeappliedatclients,servers,andthebottleneckrouterinbetween.Below,weassumeECNsup-portatthecongestionrouterandECN+supportatservers,andwecontrolthepercentageofECNflowsattherouterbychangingthenumberofECN-enabledclients.ThesameproportionofECNflowsinthesystem(andthesameeffectsasreportedbelow)couldbeachievedbyassumingECNsupportatclientsandthecongestedrouter,andthenvaryingthepercentageofECN+-enabledservers.Figure10depictstheresponse-timeprofilesfordifferentlevelsofECNdeployabilityintheweb-basedsimulationscenariowithserverandclientpools.Wesetallthemachinesintheserver-pool

10090)%80( yti70libab60orp50 evit40Uncongested networkalum30RED* no ECN, P(ECN) = 5%RED* with ECN+, P(ECN) = 5%uC20RED* no ECN, P(ECN) = 50%RED* with ECN+, P(ECN) = 50%10RED* no ECN, P(ECN) = 95%0RED* with ECN+, P(ECN) = 95%00.20.40.60.811.21.41.61.82Response Time (ms)

Figure10:Incrementaldeployability,98%load

tosupportECN+andinitiallyonly5%oftheclientssupportECN.Figure10showsthateventhesmallpercentageofECN-enabledclientsmanagetosignificantlyimprovetheirresponsetimes.Thisisofparticularimportancebecauseitprovidesareasonableincen-tiveforclientstoapplyECN;bydoingso,theycanachievesig-nificantperformanceimprovementsinstantly,withoutwaitingforotherclientstosupporttheoption.

Next,weincreasethepercentageofECN-enabledclientsto50%.Figure10showsthatECN-enabledclientsstillachievenearlyidealperformance.Atthesametime,theperformanceofnon-ECN-enabledclientsslightlydegradeswhencomparedtothepreviousscenario.ThisdegradationoccursbecausealargerpercentageofECN-enabledflowsbetterutilizetheavailablebandwidthinthisscenarioandkeeptheaveragequeuinglengthclosertoRED’smaxthparameter;thiscausesalargernumberofSYNACKpack-etsbelongingtonon-ECN-enabledflowstobemorefrequentlydroppedattherouter.However,Figure10indicatesthatthedegra-dationisnotsignificant.Thus,whiletheperformanceimprove-mentsareinstantfortheclientsthatapplyECN,thedegradationofnon-ECN-enabledclientsisgradual,whichisadesirablepropertythatwediscussinmoredetailbelow.

Finally,weincreasethepercentageofECN-enabledclientsto95%.Theresponse-timeprofileofsuchclientsisslightlydegradedwhencomparedtothepreviousscenario;thisisbecausethesys-temthroughputincreasesinscenarioswithhighECNdeployment,aswediscussindetailinthefollowingsection.Inaddition,thedegradationofthesmallnumber(5%)ofnon-ECN-enabledflowsisnowmorepronounced.Thisisbecausesuchflowsexperiencethe“TCPadmissioncontrol”problem(explainedindetailinSec-tion3.1)whichtheycansolvebyapplyingECN.

7.TESTBEDEXPERIMENTS

Here,weperformasetoftestbedexperimentswiththegoalofverifyingtheabovefindingsinarealsystem.Thetestbedcon-sistsofaclusterofIntelPentiumIV2.0GHzmachinesrunningLinux2.4.18-14,with512MBSDRAM,anda30GBATA-66diskdrive.OneofthemachinesisconfiguredasarouterandrunsNist-net[2],anIP-layernetworkemulationpackage.Theroutersepa-ratestheremainingmachinesintoclientandserverpools.WeuseNistnettovarytheRTTbetweenclientsandserversintherangefrom10to150msinordertoemulateawide-areanetworken-vironment.Inaddition,welimitthebandwidthbetweenthetwopoolsto100Mbps,whichrepresentsanuncongestedscenario,and10Mbps,whichrepresentsacongestedscenario,asweexplainin

detailbelow.ThissetupenablesustoexperimentwithaversionofREDimplementedattherouter.AsexplainedinSection4.1,thisversion,which∗is“hardwired”totheLinuxkernelandthatwede-notebyRED,marksallECN-enabledpacketswhentheaveragequeuelengthexceedsthemaxthparameter.WesetallofRED∗’sparametersaccordingtotherecommendationfrom[15],wherethereference-targetedqueuingdelayissetto5ms.

Forourexperimentalworkload,weutilizetheTPC-W[5]bench-marktorepresentane-commerceworkloadcharacterizinganon-linebookstoresitethatservesdynamicwebcontent;hence,itre-quiresaccesstoadatabaseserver.Thus,theserverpoolinoursce-narioconsistsofaweb-serverandadatabasetier.Atthewebtier,weuseaclusterofApachewebservers[4]anddynamiccontentcodedusingPHPscripts[3]attheapplicationlayer.Accesstothe4GBdatabasetierisprovidedbyaMySQLserver[1].Thework-loadforTPC-WisgeneratedbyaclientemulatorwhichgeneratestherequestsspecifiedinTPC-W.

Attheclientpool,theclientemulatoropenspersistentHTTPconnectionstothewebserversandsendsasequenceofrequestsforthedynamiccontent.Themeantimebetweentheopeningsoftwosuccessiveconnections,togetherwiththenumberofclients,definestherequestarrivalrateattheweb-servertier.However,sinceeachrequestfordynamiccontentcanconsistofseveralem-beddedqueries,accesstothedatabaseservermaybecomethesys-tembottleneck.Becauseweareinterestedinisolatingandexplor-ingnetwork-basedeffects,weproceedasfollows.

Initially,welimitthenetworkcapacitybetweentheclientandserverpoolsto100Mbps.Next,wesetthenumberofclientsandthemeantimebetweentheirarrivalssuchthattheresultingaveragenetworkthroughput,inthedirectionofserverstoclients,becomes15Mbps.Atthesametime,weverifythatthisrequestratedoesnotcreateabottleneckatthedatabaseserver.Finally,welimittheratebetweenthetwopoolsto10+Mbps,whichenablesustoexploretheimpactofRED∗andECNonend-to-endperformance.

10090)%(80 ytili70babo60rp e50vita40lum30muUncongested networkC20RED*, no ECN10RED*, with ECN0RED*, with ECN+00.20.40.60.811.21.41.61.82Response time (sec)

Figure11:TestbedExperiments:CDFProfiles

Figure11depictstheuser-experiencedresponse-timeprofilesindifferentscenarios.Thecurvelabeled“uncongestednetwork”de-pictstheresponse∗timesforthe100Mbpsscenario.Thecurvela-beled“RED,noECN”depicts∗theresponsetimeprofileinthe10Mbpsscenario,inwhichREDisappliedbuttheendpointsdonotsupportECN.Thethirdcurve,labeled”RED∗,withECN,”showstheresponse-timeprofileinthe10MbpsscenariowhereweconfigurebothclientandservermachineswithECN.Finally,wepatchallwebserversfromtheclusterwithECN+,andlabelthecorrespondingcurve“RED∗,withECN+.”WhileFigure11shows

aclearimprovementofECNoverthenon-ECNscenario,andECN+overtheECNscenario,theimpactonthroughputisevenmoredra-matic:thenormalizedthroughputis44%inthescenariowithoutECN;56%intheECNscenario,andasmuchas99%intheECN+scenario.Below,weexplainindetailthekeyreasonsforsuchsig-nificantperformancedifferences.

1.babor0.1p .mmu0.01c .melpm0.001Uncongested networkoRED*, no ECNC0.0001RED*, with ECN+RED*, with ECN0.010.11101001000Response time (sec)

Figure12:TestbedExperiments:CCDFProfiles

Figure12depictsthecomplementarycumulativedistributionfunction(CCDF),1−Pr[X≤x],ofresponsetimesfortheabovefourscenarios.Thesmallerthetailofthedistributionis,thesmallerthemeanresponsetime,andthebettertheperformanceofapar-ticularscheme.Certainly,theuncongestedscenarioshowssuperiorperformance.Onthecontrary,RED∗withoutECNhastheheaviesttail,whichindicatesthatalargenumberofwebresponsesexperi-encemultiplesuccessivetimeoutssuchthatthemeanresponsetimebecomes26sec.Atthesametime,becausemostoftheflowsspendtimeinlongexponentialbackoffs,theyareunabletosuccessfullyutilizetheavailablebandwidth;therefore,thenormalizedthrough-putisaslowas44%.Next,thepresenceofECNinTCPdatapack-etsimprovesboththemeanresponsetime,whichnowbecomes4.5sec,andthethroughput,whichincreasesto56%.However,thekeypointfromthefigureisthelargeperformanceimprovementofECN+overECN.IntheECN+scenario,thepresenceofECNinbothdataandSYNACKpacketsreducesthemeanresponsetimetoapproximately500ms,whilethenormalizedthroughputbecomesashighas99%.Mostimportant,Figure12indicatesthatECN+doesnotachieveperformanceimprovementsbysacrificingsystemstability.Onthecontrary,TCPendpointcontrolstillappliesex-ponentialbackoff,andsomeflowsnecessarilyexperiencemultipletimeoutsduetoextremelyheavycongestion,asshowninFigure12.However,despitethesecircumstances,ECN+avoidsalargenumberofunnecessarytimeouts;whencomparedtotheexistingECNspecification,ECN+shiftsthesystemclosertoanidealop-eratingpoint:web-serversmanagetosuccessfullyserveapproxi-mately50%morerequests,thenetworkthroughputimprovesbymorethan40%,andtheaverageclient-experiencedresponsetimeimprovesbynearlyanorderofmagnitude.

8.DISCUSSIONANDRELATEDWORK

ECN+extendstheexistingECNspecificationbyenablingmark-ing,insteadofdropping,server-generatedTCPcontrolpackets.Inthissection,wediscusswhetheritispossibletoachievethesameperformancesimplybygivingpriority+toTCPcontrolpacketsatrouters.WealsocomparetheECNapproachwithAQMalgo-rithmsthatgivepreferentialtreatmenttoshortflows.

Thefirstquestioniswhetheritispossibletoachievesimilaref-fectssimplybygivingprioritytoTCPcontrolpacketsatrouters.GivingprioritytoTCPSYNpacketsiscertainlynotanacceptableoption,becauseitopensthedoortoTCPSYNfloodattacks.On

thecontrary,givingprioritytoSYNACKpacketsatrouterswouldcertainlynothavethesameimpactonperformance.WhiletheuseofECNincontrolpacketscertainlyisimportant,thisfunctionalityaloneisnotsufficienttoachievedesirableperformancewithoutanAQMalgorithmattherouter,theuseofECNintheTCPdataplane,andtheECN-enabledend-pointcongestioncontrol.Inthispaper,weshowedthatallofthesemechanismsareessentialtoachieveimprovedperformance.

Next,becauseECN+achievesthelargestperformanceimprove-mentsinweb-basedscenarios,whereshortflowsaredominant,wecomparetheECN+approachwithAQMschemesandarchitec-turesthatgivepreferentialtreatmenttoshortflows.GuoandMatta[18]usedifferentmarking/droppingfunctionsattheroutersandapacketclassifieratthenetworkedgetodistinguishbetweenlong-andshort-livedTCPflows.WhileimplementingsuchclassifiersintheInternetisindeedachallengingtask,weneverthelessnotethatECN+isorthogonaltotheabovesolution,andthetwocouldbeusedtogether.

Similarly,Leetal.[24]proposeanAQMschemewhichgivesastrictprioritytoshortflows,whileitappliescongestioncontrolonlytolongflows.Theschemedistinguishesshortfromlongflowsbytrackingthenumberofpacketsthathavebeenseenrecentlyfromeachflowattherouter.Thereareseveraldrawbacksofsuchanapproach.First,givingastrictprioritytoshortflowsinvokesafun-damentalvulnerabilitytomaliciousclientsthatcanchoptheirfilesintosmallpiecesinordertoimproveperformanceorperformaDoSattack.Second,thisapproachalsocreatesthepossibilityofstabil-ityproblemsinenvironmentsthatconsistofonlyshortflows(e.g.,theabovedynamicwebcontentexperiment).Ifallflowsaregivenpriorityduringcongestion,highpacketlossratiosaregenerated,causingend-to-enddelaycharacteristictodegrade.

Finally,whilewedemonstratedthatECN+doesnothaveanyoftheabovedrawbacks,wenotethatitalsoimpactsamuchmoregeneralsetofscenariosandproblems.First,itaddressesagenericweaknessofTCP’sconnection-setupmechanisminwhichthelossofasinglecontrolpacketgenerateslongexponentialbackoffs.Whilethisiscertainlyofparticularimportanceinenvironmentsdominatedbyshort-livedflows,italsoimpactsthefairnessamonglong-livedflows(notshowninthepaper),becausenewlyarrivingflowscanenter+thesystemwithoutwaitinglonginitialtimeouts.Second,ECNisagenericadditiontoECNfunctionality;itsim-pactisnotlimitedtoanyparticularAQMscheme-itsystematicallyimprovesallECN-enabledAQMalgorithms.

9.CONCLUSIONS

Thispaperre-investigatedtheimportanceofECNinlightofre-centmeasurementsthatrevealanextremelypoorusageofthisop-tionintoday’sInternet.WediscoveredafundamentaldrawbackofthecurrentECNspecification,andshowedthattheuseofECNin-dicationsinTCPcontrolpacketscanaddressaninherentweaknessofTCP’shandshakemechanism.Alossofasinglecontrolpacketcandramaticallydegradesystemperformance,primarilyduetothehighlyskeweddistributionofInternetflow-sizes.WhiletheuseofECNbitsinTCPSYNpacketscanpotentiallyreinforceawell-knownservervulnerabilitytoDoSattackslaunchedbymaliciousclients,weshowedthatnosuchobstacleexistsfortheuseofECNbitsinserver-generatedcontrolpackets.Moreover,wearguedthatsuchanapproach(i)ismoreimportant,becausethecongestionismuchmorelikelytoariseinthedirectionfromtheservertotheclient;(ii)doesnotinduceachallengeforsystemstability,becauseTCP’sexponential-backoffmechanismsareused;and(iii)iseasytodeploy,becauseitrequiresminimalchangestoserversonly.Inordertodeploytheaboveinnovationatservers,andmoreim-

portantly,toinitiateahigh-scaledeploymentofECNintheInter-net,wearguedthatitisnecessarytoprovideasetofnovelincen-tivesthataddressparticularneedsofnetworkprovidersandend-points.Onacasestudyoftheweb,weproducedasetofsuchincentivesandshowedthat(i)web-serversthatapplytheabovein-novationcanserveapproximately50%morerequests,whiletheaverageresponsetimesexperiencedbytheirclientsimprovesbynearlyanorderofmagnitude;(ii)ECNsystematicallyimprovestheperformanceofallinvestigatedAQMschemes(RED,REM,andPI);(iii)webclientsthatapplyECNcanexperiencetheaboveperformancebenefitsinstantly,independentoftheactualnumberandrateatwhichothersadopttheoption.

InanattempttofullyunderstandtheimportanceofECN,en-richedwiththeaboveinnovation,westudiedtheECNfunctional-ityinisolationfromtraditionalrandomizationandcontrol-theory-basedAQMmechanisms.Ourfindingsareasfollows.(i)Forweb-onlytrafficmixes,ECNdominantlyimpactswebresponse-timesduetothelargenumberofshort-livedflows,suchthatevenagenericAQMschemewithECNsupportoutperformsnon-ECN-enabledAQMalgorithms;hence,applyingECNinsuchenviron-mentsisamoreimportantfactorthanwhichAQMalgorithmisapplied;(ii)forgeneraltrafficmixes,thesuperiorityofECNoverotherAQMmechanismslargelyholdsforhigh-speedbackbonerouters;thisisbecausesuchtrafficmixesgiverisetoonlymoderatequeuinglengthsinhigh-speedenvironments,despitepossiblyhighutilizationlevels;(iii)forgeneraltrafficmixesatthenetworkedge,randomizationandcontrol-theoreticmechanismsareessentialtoachievehighthroughput;whilethisisawell-establishedresultforpersistently-congestedscenarios,weshowedthatthesameholdsforless-persistentcongestionlevels.

Acknowledgments

TheauthorisgratefultoSupranamayaRanjan(RiceUniversity)forhishelpwiththetestbedexperiments,andMicheleGaretto(RiceUniversity)fordiscussionsaboutthequeuingmodel.Theauthoralsothankstheanonymousreviewersaswellashisshepherd,BruceDavie(CISCO),whosecommentshelpedimprovethispaper.10.[1]MySQLREFERENCES

DatabaseServer.http://www.mysql.com.[2]NISTNET:NetworkEmulationPackage.

http://snad.ncsl.nist.gov/itg/nistnet/.

[3]PHPScriptingLanguage.http://www.php.net.

[4]TheApacheSoftwareFoundation.http://www.apache.org.[5]TPC-W:TransactionProcessingCouncil.

http://www.tpc.org.

[6]M.Allman,S.Floyd,andC.Partridge.IncreasingTCP’s

initialwindow,1998.InternetRFC2414.

[7]G.Appenzeller,I.Keslassy,andN.McKeown.Sizingrouter

buffers.InProceedingsofACMSIGCOMM’04,Portland,Oregon,Sept.2004.

[8]S.Athuraliya,V.Li,S.Low,andQ.Yin.REM:Activequeue

management.IEEENetwork,15(3):48–53,May2001.

[9]F.Campos,F.Smith,andK.Jeffay.GeneratingrealisticTCP

workloads.Technicalreport,2004.

[10]M.Christiansen,K.Jeffay,D.Ott,andF.Smith.Tuning

REDforwebtraffic.IEEE/ACMTransactionsonNetworking,9(3):249–264,2001.

[11]A.Feldmann,A.Gilbert,P.Huang,andW.Willinger.

DynamicsofIPtraffic:Astudyoftheroleofvariabilityandtheimpactofcontrol.InProceedingsofACMSIGCOMM’99,Vancouver,BritishColumbia,Sept.1999.

[12]S.Floyd.TCPandexplicitcongestionnotification.ACM

ComputerComm.Review,24(5):10–23,1994.[13]S.Floyd.ImplementingECNinTCP,1998.

http://www.icir.org/floyd/ECN-TCP.txt.

[14]S.Floyd.InappropriateTCPresetsconsideredharmful,Aug.

2002.InternetRFC3360.

[15]S.Floyd,R.Gummadi,andS.Shenker.AdaptiveRED:An

algorithmforincreasingtherobustnessofRED’sactivequeuemanegement.Technicalreport,Aug.2001.

[16]S.FloydandV.Jacobson.Randomearlydetectiongateways

forcongestionavoidance.IEEE/ACMTransactionsonNetworking,1(4):397–413,1993.

[17]M.GarettoandD.Towsley.Modeling,simulationand

measurementsofqueuingdelayunderlong-tailInternettraffic.InProceedingsofACMSIGMETRICS’03,SanDiego,CA,June2003.

[18]L.GuoandI.Matta.Thewarbetweenmiceandelephants.In

ProceedingsofIEEEICNP’01,Riverside,CA,Nov.2001.[19]C.Hollot,V.Misra,W.Gong,andD.Towsley.Ondesigning

improvedcontrollersforAQMrouterssupportingTCPflows.InProceedingsofIEEEINFOCOM’01,Anchorage,Alaska,June2001.

[20]D.Katabi,M.Handley,andC.Rohrs.Congestioncontrolfor

highbandwidth-delayproductnetworks.InProceedingsofACMSIGCOMM’02,Pittsburgh,PA,Aug.2002.[21]S.KunniyurandR.Srikant.Analysisanddesignofan

adaptivevirtualqueue(AQM)algorithmforactivequeuemanegement.IEEE/ACMTransactionsonNetworking,12(2):286–299,2004.

[22]A.Kuzmanovic.Thepowerofexplicitcongestion

notification(extendedversion).NorthwesternUniversityTechnicalReport,May2005.

[23]L.Le,J.Aikat,K.Jeffay,andF.Smith.Theeffectsofactive

queuemanagementonwebperformance.InProceedingsofACMSIGCOMM’03,Karlsruhe,Germany,Aug.2003.[24]L.Le,J.Aikat,K.Jeffay,andF.Smith.Differential

congestionnotification:Tamingtheelephants.In

ProceedingsofIEEEICNP’04,Berlin,Germany,Oct.2004.[25]R.Mahajan,S.Floyd,andD.Wetherall.Controlling

high-bandwidthflowsatthecongestedrouter.InProceedingsofIEEEICNP’01,Riverside,CA,Nov.2001.

[26]M.May,J.Bolot,C.Diot,andB.Lyles.Reasonsnotto

deployRED.InProc.ofIWQoS’99,London,UK,1999.[27]A.Medina,J.Padhye,andS.Floyd.Measuringthe

evoluationoftransportprotocolsintheInternet.Technicalreport,2004.

[28]J.PadhyeandS.Floyd.IdentifyingtheTCPbehaviorofweb

servers.InProceedingsofACMSIGCOMM’01,SanDiego,CA,Aug.2001.

[29]V.PaxsonandM.Allman.ComputingTCP’sretransmission

timer,Nov.2000.InternetRFC2988.

[30]K.RamakrishnanandS.Floyd.Aproposaltoaddexplicit

congestionnotificationtoIP,Jan.1999.InternetRFC2481.[31]K.RamakrishnanandS.Floyd.Theadditionofexplicit

congestionnotificationtoIP,Sept.2001.InternetRFC3168.[32]K.RamakrishnanandR.Jain.Abinaryfeedbackschemefor

congestionavoidanceincomputernetworks.ACMTransactionsonComp.Sys.,8(2):158–181,May1990.[33]F.Smith,F.Campos,K.Jeffay,andD.Ott.WhatTCP/IP

protocolheaderscantellusabouttheweb.InProceedingsofACMSIGMETRICS’01,Cambridge,MA,June2001.