TCP Vegas New techniques for congestion detection and avoidance_百

TCPVegas:SeanW.O’MalleyDepartmentofComputerScienceUniversityofArizonaTucson,onAbstractVegasisanewimplementationofTCPthatachievesbe-tween40and70%betterthroughput,withone-fifthtoone-halfthelosses,apermotivatesanddescribesthethreekeytechniquesemployedbyVegas,andpresentstheresultsofacomprehensiveexperimentalperformancestudy—usingbothsimulationsandmeasure-mentsontheInternet—oftheVegasandRenoimplementa-tionsofTCP.1IntroductionFewwouldarguethatoneofTCP’sstrengthsliesinitsadaptiveretransmissionandcongestioncontrolmechanism,withJacobson’spaper[4]perattemptstogobeyondthisearlierwork;toprovidesomenewinsightsintocongestioncontrol,andtoproposemodifigibleresmeisatake-offofearlierimplementationsofTCPthatweredistributedinreleasesof4.3BSDUnixknownasTahoeandReno;weuseTaatVegasdoesnotinvolveanychangestotheTCPspecification;itismerelyanalternativeimpl,allthechangesareconfitourdiscussiontoReno,tethatintermsofthecongestion-relatedalgorithms,RenoisroughlyequivalenttotheBerkeleyNetworkRelease2(BNR2)implementationofTCP.

70605040KB30201000.5606001.0601201.52.02.53.01803.52404.04.55.05.5Time in seconds3003606.04206.54807.05407.58.08.59.09.560010.080400.5Sending

KB/S1.01.52.02.53.03.54.04.55.05.5Time in seconds6.06.57.07.58.08.59.09.510.0Figure1:environment,fically,thesimulatorsupportsmultiplehosts,eachrunningafullprotocolstack(TEST/TCP/IP/ETH),andseveralabstractlinkbehaviors(point-to-pointconnectionsandethernets).RouterscanbemodeledeitherasanetworknoderunningtheactualIPpro-tocolcode,,FIFO).The-kernel-basedsimulatorprovidesarealisticsettingforevaluatingprotocols—eachprotocolismodeledbytheactualCcodethatimplementsitratherthansomemoreabstractspecifisotrivialtomoveprotocolsbetweenthesimulatorandtherealworld,therebyprovid-ingacomprehensiveprotocoldesign,implementation,hemostimportantprotocolsavailableinthesimulatoriscalledTRAFFIC—itimplementsTCPInternettrafficbasedontcplib[1].TRAFFICstartsconnversationcanbeoftypeTELNET,FTP,NNTP,orSMTP,mple,FTPexpectsthefollowingparameters:numberofitemstotransmit,controlsegmentsize,heseparametersarebasedonprobabilitydistribu-tionsobtainedfromtraffiy,particularattentiontokeepingtheoverheadofthistracingfacilityaslowaspossible,fically,thefacilitywritestracedatatomemory,dumpsittoafileonlywhenthetestisover,andkeepstheamountofdataassociatedwitheachtraceentrysmall(8bytes).Wethtofthissectiondescribesonesuchtoolthatgraphicallyrepresenoloutputsmultiplegraphs,eachfocusingonaspecifieusegraphslikethisthroughoutthepaper,,allTCPtracegraphshavecertainfeaturesincom-mon,clednumbersinthisfigurearekeyedtothefollowingexplanations:2.2TraceFacilityEarlyinthiseffortibersonthetopofthegraphindicatewhenthekilobyte(KB)dsontopofthegraphindicatewhenthepe-riodiccoarse-grainedtimerfiesnotimplyaTCPtimeout,sontopofthegraphindicatethatacoarse-grainedtimeoutoccurred,causingasegmenttobe

erticallinesrunningthewholeheightofthegraphindicatewhenasegmentthatiseventuallyre-transmittedwasoriginallysent,thatseveralconsecutivesegmentsareretransmittedintheexample.4565040KB3.51.01.52.02.5Time in seconds3.03.5Figure2:tiontothiscommoninformation,eachgraphde-pictsmorespecifitomgraphinFig-ure1isthesimplest—itshowstheaveragesendingrate,graphinFigure1ismorecomplicated—itgivesthesizeofthedif-ferentwindowsTCPusesforfl3showstheseinmoredetail,againkeyedbythefollowingexplanations:edduringslow-start,andmarksthepoineminimumofthesender’sbuffersizeandreceiver’edforcongestioncontrol,nlinegivestheactualnumberofbytesintransitatanygiventime,phsjustdescribedareobtainedfromtracingin-formationsavedbytheprotocol,andare,thus,availulatoritselfalsoreportscertaininfor-mation,suchastherate,inKB/s,uter,thetracesalsosave

Host1aHost1bHost2aEthernetRouter1200 KBytes/sec50ms delayRouter2EthernetHost2bHost3aHost3bFigure5:NetworkConfi,thenVegasretransmitsthesegmentwithouthavingtowaitfor(3)cases,lossesareeithersogreatorthewindowsosmallthatthesenderwillneverreceivethreeduplicateACKs,andtherefore, ACK for packet 10 (packets 11 and 12 are in transit)Send packet 13 (which is lost)Rcvd ACK for packet 11Send packet 14one

RTTTimeRcvd ACK for packet 12Send packet 15 (which is also lost)Should have gotten ACK for packet 13Rcvd dup ACK for packet 12 (due to packet 14)Vegas checks timestamp of packet 13 and decides to retransmit it(Reno would need to wait for the 3rd duplicate ACK)Rcvd ACK for packets 13 and 14Since it is 1st or 2nd ACK after retransmission,Vegas checks timestamp of packet 15 and decides to retransmit it(Reno would need to wait for 3 new duplicate ACKS)Whenanon-duplicateACKisreceived,ifitisthefirstorsecondoneafteraretransmission,Vegasagaincheckstoseeift,llcatchanyothersegmentthatmayhavebeenlos

RTTFigure4:mple,ifRenoreceivespacket2butpacket3isdropped,itwillsendaduplicateACKforpacket2whenpacket4arrives,againwhenpacket5arrives,esenderseesthethirdduplicateACKforpacket2(theonesentbecausethereceiverhadgottenpacket6)xtendsReno’,ACKarrives,VegasreadstheclockagainanddoestheRTTcalcuhenusesthismoreaccurateRTTestimatetodecidetore-transmitinthefollowingtwosituations(asimpleexampleisgiveninFigure4):Inotherwords,VegastreatlcontainsReno’scoarse-grathatthecongestionwindowshouldonlybere-ducedduetolossesthathappenedatthecurrentsendingrate,andnotduetolossesthathappenedatanearlier,,itispossibletodecreasethecongestrast,Vegasonlydecreasesthecongestionwindosesthathappenedbeforethelastwindowdecreasedonotimplythatthenetworkiscongestedforthecurrentcongestionwindowsize,andtherefore,angeisneededbecauseVegasdetectslossesmuchsoonerthanReno.3.2CongestionAvoidanceMechanismTCPReno’scongestiondetectionandcontrolmechanismomechanismtodetecttheincipientWhenaduplicateACKisreceived,Vegascheckstoseeifthedifferencebetweenthecurrenttimeandthetimestamprecordedfortherelevantsegmentisgreater

7KB30201000.51101.01.52.02.53.03.54.04.55.05.5Time in seconds2206.03306.54407.05507.56608.07708.58809.09.599010.8.5Sending

KB/S1.01.52.02.53.03.54.04.55.05.5Time in seconds6.06.57.07.58.08.59.09.510.010Queue

size

in

router50.51.01.52.02.53.03.54.04.55.05.5Time in seconds6.06.57.07.58.08.59.09.510.0Figure6:TCPRenowithNoOtherTraffic(Throughput:105KB/s).stagesofcongestion—beforelossesoccur—reactive,ratherthanproactive,ult,RenoneedstocreatelossestofinbeseeninFigure6,whichshowsthetraceofaRenoconnectionsending1MBofdataoverthenetworkconfigurationseeninFigure5,withnoothertraffi,case,reseveralpreviouslyproposedapproachesforproactivecongestiondetectionbasedonacommonunder-standingofthenetworkchangesasitapproachescongestion(anexcellentdevelopmentisgivenin[7]).ngeistheincreasedqueuesizeintheintermediatenodesoftheconnection,dCrowcroft’sDUALalgorithm[11]gestionwindownormallyincreasesasinReno,buteverytworound-tripdelaysthealgorithmcheckstoseeifthecurre,’sCARD(CongestionAvoidanceusingRound-tripDelay)approach[7]isbasedonananalyticisionastowhetherornottochangethdowisadjustedonceeverytworound-tripdelaysbasedontheproduct(WindowSize-WindowSize)(RTT-RTT)asfollows:iftheresultispositive,decreasethewindowsizebyone-eighth;iftheresultisnegativeorzero,atthewindowchangesduringeveryadjustment,thatis,rchangeseenasthenetworkapproachescon-gestionisthefldCrowcroft’sTri-Sscheme[10]TT,theyincreasethewindowsizebyonesegmentandcomparethethriffer-enceislessthanone-halfthethroughputachievedwhenonlyonesegmentwasintransit—aswasthecaseatthebeginningoftheconnection—-Scalculatesthethro’approachismostsimilartoTri-S,r,itdiffersfromTri-Sinthatitcalculatesthroughputsdifferently,andinsteadoflookingforachangeinthethroughputslope,itcompares

7KB30201000.51.01101.52202.03302.54403.03.54.0Time in seconds5506604.57705.08805.59906.06.57.8.5Sending

KB/S1.01101.52202.03302.54403.03.54.0Time in seconds5506604.57705.08805.59906.06.57.0280240CAM

KB/S20.51.01.52.02.53.03.54.0Time in seconds4.55.05.56.06.57.010Queue

size

in

router50.51.01.52.02.53.03.54.0Time in seconds4.55.05.56.06.57.0Figure7:TCPVegaswithNoOtherTraffic(Throughput:169KB/s).pleideathatVegasexploitsisthatthenumberofbytesintransitisdirectlyproportionaltotheexpectedthroughput,andtherefore,asthewindowsizeincreases—causingthebytesintransittoincrease—sesthisideatomeasureandcontroltheamountofextradatathisconnectionhasintransit,wherebyextradatawemeandatathatwouldnothavebeensentiftheband-widthuselofVegasistomaintainthe“right”sly,ifaconnectionissendingtoomuchextradata,viously,ifaconnectionissendingtoolittleextradata,itcannotrespondr’congestionavoidanceactionsarebasedonchangesintheestimatedamountofextradatainthenetwork,’,defineagivenconnection’tice,VegassetsBaseRTTtotheminimumofallmea-suredroundtriptimes;itiscommonlytheRTTofthefirstsegmentsentbytheconnection,beforetherouterqueuesincreaseduetotraffisumethatwearenotoverflowingtheconnection,thentheexpectedthroughputisgivenby:Expected=WindowSize/BaseRTTwhereWindowSizeisthesizeofthecurrentcongestionwin-dow,whichweassumeforthepurposeofthisdiscussion,tobeequaltothenumberofbytesintransit.

Second,donebyrecordingthesendingtimeforadistin-guishedsegment,recordinghowmanybytesaretransmittedbetweenthetimethatsegmentissentanditsacknowledge-mentisreceived,computingtheRTTforthedistinguishedsegmentwhenitsacknowledgementarrives,,VegascomparesActualtoExpected,f=atDiffispositiveorzerobydefinition,sinceActuafinetwothresholds,,roughlycorrespondingtohavingtoolittleandtoomuchextradatainthenetwork,ff,VegasincreasesthecongestionwindowlinearlyduringthenextRTT,andwhenDiff,eavesthecongestionDiff<.windowunchangedwhenIntuitively,thefartherawaytheactualthroughputgetsfromtheexpectedthroughput,themorecongestionthereisinthenetwork,therhand,whentheactualthroughputrategetstooclosetotheexpectedthroughput,ethealgorithm,asjustpresented,comparesthedifferencebetweentheactualandexpectedthroughputratestotheandthresholds,thesetwothresholdsaredefinedintermsofKB/r,itisperhapsmoreaccuratetothinkimple,onaconnectionwithaBaseRTTof100msandasegmentsizeof1KB,ifKB/sandKB/s,thenwecanthinkofassayingthattheconnectionneedstobeoccupyingatleastthreeextrabuffersinthenetwork,ermsofbuffersInpractice,linearin-crease/decreasemode—asopposedtotheslow-startmodedescribedbelow—nbeinterpretedasanattempttouseatleasttwo,7showsthebehaviorofTCPVegaswhenthereisnoothertrafficpresent;sonenewtypeofgraphinthisfigure,thethirdone,whichdepictsthecongestion

7KB30201000.51.01101.52202.02.53303.03.54404.04.5Time in seconds5505.06605.56.07706.58807.07.59908.08.5280240CAM

KB/S20.51.01.52.02.53.03.54.04.5Time in seconds5.05.56.06.57.07.58.08.5280240TRAFFIC

KB/S20.51.01.52.02.53.03.54.04.5Time in seconds5.05.56.06.57.07.58.08.5Figure9:TCPVegaswithtcplib-GeneratedBackgroundTraffiorkbandwidthincreases,awaytofindaconnection’sthisend,weincorpo-ratedourcongestiondetectionmechanismintoslow-startwithonlyminormodifiletodetectandavoidcongestionduringslow-start,een,thecon-gestionwindowstaysfieactualratefallsbelowtheexpectedratebyacertainamount—wecallthisthethreshold—Vegaschangesfromslow-startmodetolinearincrease/aviorofthemodifisonthatweneedtomeasuretheactualratewithafixedcongestionwindowisthatw,wecanonlysendasmuchdataasisacknowledgedintheACK.(Duringslow-start,RenosendstwosegmentsforeachACKreceived.)Insummary,webelievethataddingcongestiondetectiontoslow-startisimportant,ffersabeginning,slow-start,,earen’tenoughbuffersinthebottleneckrouter,Vegas’slow-startwithcongestiondetectouseratecontrolduringslow-start,usingaratedefiristoslowdownaswereachthebandwidthavailabletotheconnection(Vegashasenoughinformationtofigurethisout).4SimulationResultsThissectionreportstheresul-thoughwehavealsomeasuredVegasandRenoontheac-tualInternet—seeSection5—thesimulatorallowsustobettercontroltheexperiment,andinparticular,givesustheopportunitytoseewhetheroatalltheexperimentsusedinthissectionareonthenetworkconfigurationshowninFigure5.

Reno/Vegas60/109ThroughputRatios30/22RetransmitRatios1.43/0.081.02/1.131.5/1866/119Vegas/Vegas1.23/1.200.01/0.01Table1:One-on-One(300KBand1MB)hput(KB/s)ThroughputRatioRetransmissions(KB)RetransmitRatioCoarseTimeoutsVegas-1,389.401.5327.100.490.904.2BackgroundTrafficWenextmeasuredtheperformanceofadistinguishedTCPconnectionwhenthenetworkisloadedwithtraffi,theprotocolTRAFFICisrunningbetweenHost1aandHost1binFigure5,setofexperiments,thetcplibtraffi2givestheresultsforRenoandtwoversionsofand,andVegas-2,4Vegas—Vegas-1,bersshownareaveragesfrom57runs,obtainedbyusingdiffer-entseedsfortcplib,andbyusing10,leshowsthethroughputrateforeachofthedistin-guishedconnectionsusingthethreeprotocols,alongwiththeirratiotoReno’givesthenum-berofkilobytesretransmitted,theratioofretransmitstoReno’s,mple,Vegas-1,3had53%betterthroughputthanReno,withonly49%tethatthereislittledifferencebetweenVegas-1,3andVegas-2,imulationstellustheexpectedimprovementofVegasoverReno:morethan50%improvementonthrough-put,ultsfromtheone-on-oneexperimentsindicatethatthegainsofVegasarenotmadeattheexpenseofReno;thisbeliefisfurthersup-portedbythefactthatthebackgroundtraffic’sthroughputincreasesby20%whenRenoiscompetingforresourceswithVegas,ranthesetestswiththebackgroundtraffioughputandthekilo-bytesretransmittedbythe1MBytetransfersdidn’tchangeComparingthbecausethelargetransferwasabletorunbyitselfduringmostofthetest.

trafficover68Vegas(KB/s)Vegas85Table3:ThroughputofBackgroundTraffificantly—lessthan4%—butthistimethethroughputofthebackgroundtraffihole,theresultsweresimilar,exceptforwhenwechangedTCP’-on-onetestswithtraffi,RenodidbetterwhenrunningagainstVegasthanagainstitself,butthistime,itslossesincreasedbyonly6%(versus43%)intheReno/-waybackgroundtraffiavebeenreportsofchangeinTCP’sbehaviorwhenthebackgroundtrafficistwo-wayratherthanone-way[12].Thus,wemodifiedtheexperimentinSection4.2byaddingtcplibtraffioughputratiostayedthesame,butthelossratiowasmuchbetter:tthattherewasn’tmuchchangeisprobablyduetothefactthattcplibalreadycreatessome2-waytraffic—TELNETconnectionssendonebyteandgetoneormorebytesback,theexperi-mentsreportedsofar,sexperiment,’throughputandlossesstayedunchangedbetween50KBand20KB;fromthatpointon,asthebufferdecreased,’sthroughputinitiallyincreasedasthebuffersgotsmaller,okbackatFigure6,weseethatasRenoincreasesitscongestionwindow,itusesmoreanmitthecongestionwindowbyreducingthesizeofthesend-buffer,wemaypreventitfromoverrunningtherouter’imulationswith2,4,and16connectionssharingabottlenecklink,wherealltheconnectionseitherhadthesamepropa-gationdelay,orwhereofferentpropagationdelayswereused,imulationswhereusedtoobtainprelefairness,wechoseJain’sfairnessindex[8].Inthecaseof2and4connections,witheachconnec-tiontransfering8MB,RenowasslightlymorefairthanVegaswhenallconnectionshadthesamepropagationdelay,butVegaswasmorefairtxperimentswith16connections,witheachconnectiontransfering2MB,l,erenostabilityproblemsinthecaseof16connectionssharingthebottlenecklink,ghVegas’congestionavoidancemechanismscouldnotworkeffectivelyduetothelimitednumberofbuffers,Vegasonlyhadhalfthecoarse-grainedtimeoutsasRenoduetoVegas’improvedretransmitmechanism.5Intereitissimpletomoveaprotocolbetweenthesimulatorandthe“realworld”,thenumbersreporultsmustbeconsideredpreliminarybecausetheywerelimitedtotransfersbetweentheUniversityofAri-zona(UA)andtheNationalInstitutesofHealth(NIH).Theconnectionconsistsof17hops,andpassesthroughDenver,,Chicago,Cleveland,nconsistsofa

Throughput(KB/s)ThroughputRatioRetransmissions(KB)RetransmitRatioCoarseTimeoutsVegas-1,372.501.3724.500.510.80Throughput(KB/s)Retransmissions(KB)CoarseTimeouts1024KBReno72.501.0024.501.000.80Reno72.001.0010.501.000.20128KBReno53.101.004.001.000.20Table5:eventransfersfromUAtoNIH—Renosends1MB,512KB,and128KB,Vegas-1,3sends1MB,512KB,and128KB,andVegas-2,rteda45seconddelaybetweeneachtransferinaruntogivethenetworkachancetosettledown,arunstartedapproximatelyonceeveryhour,andweshuffl-pendingonthecongestionavoidancethresholds,itshowsbetween37%and42%improvementoverReno’sthrough-putwithonly51%to61%atVegasout-performedRenoon92%ofthetransfers,,ewewereconcernedthatVegas’throughputim-provementdependedonlargetransfersizes,5showstheeffectoftransfersizeonboththroughputandretransmissionsforRenoandVegas-1,,obssofthrough-put,weseeanincreasefrom37%to71%.Theresultsaresimilarforretransmissions,astherelativenumberofVegasretransmissionsgoesfrom51%ofReno’sto17%ofReno’,noticethatthenumberofkilobytesretransmittedbyRenostartstofldecreasedthetransfersizebyhalf,from1MBto512KB,weseeonlya42%furtherdecreasethetransfersizetoone-fourthitspreviousvalue,from512KBto128KB,thenumberofkilobytesretransmittedonlydecreasesby18%.ThisindicatesthatweareapproachingtheaveragenumberofkilobytesretransmittedduetoReno’eseresults,weconcludethattherearearound20KBsretransmittedduringslow-start,therhand,thenumberofkilobytesretransmidicatesthatVegaseliminatesnearlyalllossesduringslow-startduetoitsmodifiedslow-startwithcongestionavoidance.6DiscussionMostoftheexperimentsreportedintheprevioustwosec-tionsshowthebenefitsofrunningaVegasconnectionwhenmostofthetraffitionsshowthatifthereareenoughbuffersintherouters—meaningthatVegas’congestionavoidancemechanismscanfunctioneffectively—mple,simulationsrunningtcplibtrafficoverbothRenoandVegasshowthattheaverageresponsetimeinTELNETconnec-tionsisaround25%oadincreasesand/orthenumberofrouterbuffersdecreases,Vegas’scongestionavoidancemechanismsarenotaseffective,eavycongestion,VegasbehavesverysimilarlytoReno,sinceVegas“fallsback”toReno’ortantpointtokeepinmindisthatuptothepointthatcongestionisbadenoughforVegas’behaviortodegenerateintoReno,becauseVegaslimitsitsuseofrouterbuffersasspecifiedbythethresh-old,whereasRenoincreasesitswindowsizeuntiltherearelosses—whichmeansalltherouterbuffersarebeingused.

SelectiveACKs[5,6]havebeenproposedasawaytodecreasethenumberofunnecessarilyretransmittedpacketsandtopghtheselectiveACKmechanismisnotyetwelldefined,,itonlyrelatestoVegas’retransmissionmechanism;selectiveACKsbyth,thereislittlereasontobelievethatselectiveACKscansignificantlyimproveonVegasintermsofunnecessaryretransmissions,astherewereonly6K,selectiveACKshavethepotentialtoretransmitlostdatasooneronfuturenetworkswithlargedelay/dbeinterest-ingtosy,wenotethatse-lectiveACKsrequireachangetotheTCPstandard,whereastheVegasmodifi’stimatefortheBaseRTTistoosmall,thentheprotocol’sthroughputwillstaybelowtheavailablebandwidth;ifitistoolarge,r,weplantostudythismorecarefullyinthefuture.7ConclusionsWehaveintroducedseveraltechniquesforimprovingTCP,includinganewtimeoutmechanism,anovelapproachtocongestionavoidancethattriestocontrolthenumberofex-trabufferstheconnectionoccupiesinthenetwork,andamodifimentsonboththeInternetandusingasimulatorshowthatVegasachieves40to70%betterthroughput,withone-fifthtoone-halfasmanybytesbeingretransmitted,asrespects,,weneedtotestVegasunderawidersetofconditions,andinparticular,,webelievethatmoreattentionneedstobepaidtoavoidingcongestionduringslow-start,andaspointedoutinSection3.3,ledgementsThankstoLewBermanfromtheNationalLibraryofMedicinefnces[1]:ALibraryofTCPInternetworkTrafficalRe-portCS-SYS-91-495,ComputerScienceDepartment,USC,1991.[2]calreport,MIT,Sept.1990.[3]-kernel:ansactionsonSoftwareEngineering,17(1):64–76,Jan.1991.[4]eedingsoftheSIGCOMM’88Symposium,pages314–32,Aug.1988.[5]tforComments1072,Oct.1988.[6]on,,tforComments1323,May1992.[7]-BasedApproachforCoputerCommunicationRe-view,19(5):56–71,Oct.1989.[8]ofComputerSystemsPerformanceAnalysis:TechniquesforExperimentalDesign,Mea-surement,leyandSons,Inc.,NewYork,1991.[9]:calReport88/472,DepartmentofComputerScience,UCBerkeley,1988.[10]ngestionCon-trolScheme:SlowStartandSearch(Tri-S).ACMComputerCommunicationReview,21(1):32–43,Jan.1991.[11]puterCommunicationReview,22(2):9–16,Apr.1992.[12],r,ationsontheDynamicsofaCongestionControlAlgorithm:TheEffectsofTwo-WayTraffieedingsoftheSIGCOMM’91Symposium,pages133–147,Sept.1991.