ch2(TCP拥塞控制)_737201421.ppt

第二章TCP拥塞控制,江勇jiangy,Outline,WindowFlowControlAnalysisofTCPCongestionControlTahoe,Reno,NewReno,Sack,VegasBeyondTCPCongestionControl,Outline,WindowFlowControlAnalysisofTCPCongestionControlTahoe,Reno,NewReno,Sack,VegasBeyondTCPCongestionControl,Problem,FlowcontrolmakesurethatthereceivercanreceiveasfastasyousendCongestioncontrolmakesurethatthenetworkdeliversthepacketstothereceiver,Windowflowcontrol,LostpacketdetectedbyACKApproximatelyWpacketstransmittedperRTTHigherwindowhigherthroughputSelf-clocking,time,time,Source,Destination,EarlyTCP,Pre-1988Go-back-NARQDetectslossfromtimeoutRetransmitsfromlostpacketonwardFlowcontrol:self-clocking,Sourcerate,LimitthenumberofpacketsinthenetworktowindowWSourcerate=bpsIfWtoosmallthenratecapacityIfWtoobigthenratecapacity=congestion,WhydoYouCareAboutCongestionControl?,OtherwiseyougettocongestioncollapseHowmightthishappen?Assumenetworkiscongested(arouterdropspackets)YoulearnthereceiverdidntgetthepacketeitherbyACK,NACK,orTimeoutWhatdoyoudo?retransmitpacketStillreceiverdidntgetthepacketRetransmitagain.andsoonAndnowassumethateveryoneisdoingthesame!,WhydoYouCareAboutCongestionControl?,NetworkwillbecomemoreandmorecongestedAndthiswithduplicatepacketsratherthannewpackets!October1986,InternethaditsfirstcongestioncollapseLinkLBLtoUCBerkeley400yards,3hops,32Kbpsthroughputdroppedto40bpsfactorof1000drop!1988,VanJacobsonproposedTCPflowcontrol,Solutions?,Increasebuffersize.Whynot?SlowdownIfyouknowthatyourpacketsarenotdeliveredbecausenetworkcongestion,slowdownQuestions:Howdoyoudetectnetworkcongestion?Byhowmuchdoyouslowdown?,Outline,WindowFlowControlAnalysisofTCPCongestionControlTahoe,Reno,NewReno,Sack,VegasBeyondTCPCongestionControl,WhatsReallyHappening?,KneepointafterwhichThroughputincreasesveryslowDelayincreasesfastCliffpointafterwhichThroughputstartstodecreaseveryfasttozero(congestioncollapse)DelayapproachesinfinityNote(inanM/M/1queue)Delay=1/(1utilization),Load,Load,Throughput,Delay,knee,cliff,congestioncollapse,packetloss,CongestionControlvs.CongestionAvoidance,CongestioncontrolgoalStayleftofcliffCongestionavoidancegoalStayleftofknee,Load,Throughput,knee,cliff,congestioncollapse,Goals,OperatenearthekneepointRemaininequilibriumHowtomaintainequilibrium?Dontputapacketintonetworkuntilanotherpacketleaves.Howdoyoudoit?UseACK:sendanewpacketonlyafteryoureceiveanACK.Why?Maintainnumberofpacketsinnetwork“constant”,HowDoYouDoIt?,Detectwhennetworkapproaches/reacheskneepointStaythereQuestionsHowdoyougetthere?Whatifyouovershoot(i.e.,gooverkneepoint)?Possiblesolution:IncreasewindowsizeuntilyounoticecongestionDecreasewindowsizeifnetworkcongested,DetectingCongestion,ExplicitnetworksignalSendpacketbacktosource(e.g.ICMPSourceQuench)ControltrafficcongestioncollapseSetbitinheader(e.g.DECDNA/OSILayer4CJ89,ECN)CanbesubvertedbyselfishreceiverSEW01Unlessoneveryrouter,stillneedend-to-endsignalCouldberobust,ifdeployed,DetectingCongestion,ImplicitnetworksignalLoss(e.g.TCPTahoe,Reno,NewReno,SACK)+relativelyrobust,-noavoidanceDelay(e.g.TCPVegas)+avoidance,-difficulttomakerobustEasilydeployableRobustenough?Wireless?,EfficientAllocation,TooslowFailtotakeadvantageofavailablebandwidthunderloadToofastOvershootkneeoverload,highdelay,lossEveryonesdoingitMayallunder/overshootlargeoscillationsOptimal:xi=XgoalEfficiency=1-distancefromefficiencyline,User1:x1,User2:x2,Efficiencyline,2userexample,overload,underload,FairAllocation,MaxminfairnessFlowswhichsharethesamebottleneckgetthesameamountofbandwidthAssumesnoknowledgeofprioritiesFairness=1-distancefromfairnessline,User1:x1,User2:x2,2userexample,2gettingtoomuch,1gettingtoomuch,fairnessline,ControlSystemModelCJ89,Simple,yetpowerfulmodel,User1,User2,Usern,x1,x2,xn,y,PossibleChoices,Multiplicativeincrease,additivedecreaseaI=0,bI1,aD0,bI=1,aD1,aD=0,00,bI=1,aD=0,0ssthreshtheneachtimeasegmentisacknowledgedincrementcwndby1/cwnd(cwnd+=1/cwnd).Socwndisincreasedbyoneonlyifallsegmentshavebeenacknowlegded.Congestionavoidanceandslowstartareindependentalgorithmswithdifferentobjectives.Inpracticetheyareimplementedtogether.,SlowStart/CongestionAvoidanceExample,Assumethatssthresh=8,Roundtriptimes,Cwnd(insegments),ssthresh,PuttingEverythingTogether:TCPPseudocode,Initially:cwnd=1;ssthresh=infinite;Newackreceived:if(cwndssthresh)/*SlowStart*/cwnd=cwnd+1;else/*CongestionAvoidance*/cwnd=cwnd+1/cwnd;Timeout:/*Multiplicativedecrease*/ssthresh=cwnd/2;cwnd=1;,while(nextunack+win)transmitnextpacket;wherewin=min(cwnd,flow_win);,unack,next,win,seq#,PacketLoss,PacketlossdetectedbyRetransmissiontimeouts(RTOtimer)DuplicateACKs(atleast3),1,2,3,4,5,6,1,2,Packets,Acknowledgements,7,FastRetransmit,Immediatelyretransmitsafter3dupACKswithoutwaitingfortimeout(fastretransmit)Adjustsssthreshssthreshmax(flightsize/2,2)flightsize:Theamountofdatathathasbeensentbutnotyetacknowledged.EnterSlowStart(cwnd=1)Assumption:lossindicatescongestion(bufferoverflow)Thefastretransmitalgorithmfirstappearedinthe4.3BSDTahoerelease,anditwasfollowedbyslowstart.,Summary:Tahoe,BasicideasGentlyprobenetworkforsparecapacityDrasticallyreducerateoncongestionWindowing:self-clockingOtherfunctions:roundtriptimeestimation,errorrecovery,TCPReno(Jacobson1990),Slowstart,congestionavoidance,fastretransmitAddition:fastrecoveryMostwidelyusedversionofTCPtoday,ss,time,window,ca,ss:slowstartca:congestionavoidance,Fastrecovery,Motivation:preventpipefromemptyingafterfastretransmitIdea:eachdupACKrepresentsapackethavingleftthepipe,thatis,thereisstilldataflowingbetweenthetwoends.EnterFR/FRafter3dupACKsSetssthreshmax(flightsize/2,2)RetransmitlostpacketSetcwndssthresh+3*MSS(windowinflation)EachtimeanotherduplicateACKarrives,cwnd+=MSS.Transmitapacket,ifallowedbythenewvalueofcwnd.Onnon-dupACK(1RTTlater),setcwndssthresh(windowdeflation)EnterCA,Example:FR/FR,FastretransmitRetransmiton3dupACKsFastrecoveryInflatewindowwhilerepairinglosstofillpipeThefastrecoveryalgorithmappearedinthe4.3BSDRenorelease.,1,2,time,S,time,D,3,4,5,6,8,7,Summary:Reno,BasicideasFastrecoveryavoidsslowstartdupACKs:fastretransmit+fastrecoveryTimeout:fastretransmit+slowstartAtsteadystate,cwndoscillatesaroundtheoptimalwindowsize.,Variant:NewReno(Fall&Floyd1996),Motivation:multiplelosseswithinawindowPartialACKacknowledgessomebutnotallpacketsoutstandingatstartofFRPartialACKtakesRenooutofFR,deflateswindowSendermayhavetowaitfortimeoutbeforeproceedingIdea:partialACKindicateslostpacketsStaysinFR/FRandretransmitsimmediatelyRetransmits1lostpacketperRTTuntilalllostpacketsfromthatwindowareretransmittedEliminatestimeout,Example:NewReno,On3dupACKs,receiverhaspackets2,4,6,8,cwnd=8,retransmitspkt1,enterFR/FRNextdupACKincrementcwndto9AfteraRTT,ACKarrivesforpkts1&2,exitFR/FR,cwnd=5,8unackedpktsNomoreACK,sendermustwaitfortimeout,1,2,time,S,time,D,3,4,5,6,8,7,0,9,Variant:SACK(Mathis,Mahdavi,Floyd,Romanow96),Motivation:Reno&NewRenoretransmitatmost1lostpacketperRTTPipecanbeemptiedduringFR/FRwithmultiplelossesIdea:SACKprovidesbetterestimateofpacketsinpipeSACKTCPoptiondescribesreceivedpacketsOn3dupACKs:retransmits,halveswindow,entersFRUpdatespipe=packetsinpipeIncrementwhenlostornewpacketssentDecrementwhendupACKreceivedTransmitsa(lostornew)packetwhenpipekcodedblockscanrecoveroriginalkblocksfromanykofthenblocksn-kblocksofoverheadtradebandwidthforlosscanrecoverfromlossintimeindependentoflinkRTTusefulforlinksthathavelongRTT(e.g.satellite)payn-koverheadwhetherlossornotneedtoadaptn,kdependingoncurrentchannelconditions,Hybrid,IndirectTCPBB95SplitTCPconnectionintotwopartsregularTCPfromfixedhost(FH)tobasestationmodifiedTCPfrombasestationtomobilehost(MH)basestationfails?wiredpathfasterthanwirelesspath?,Hybrid,TCPSnoopBSK95BasestationsnoopsTCPpackets,infersflowcachedatapacketsgoingtowirelesssideIfdupacksfromwirelessside,suppressackandretransmitfromcachesoftstatewhataboutnon-TCPprotocols?whatifwirelessnotlasthop?,Conclusion,Transportprotocolmodificationsnotdeploy