TCP拥塞控制Tahoe-Reno-NewReno与SACK算法概述与比较

TCP拥塞控制：Tahoe、Reno、NewReno与SACK算法概述与比较刘娟2011.12.12拥塞的发生Sourcerate=bpsIfWtoosmallthenrate«capacityIfWtoobigthenratecapacity=congestionKnee–pointafterwhichThroughput增加非常缓慢Delay迅速增加Cliff–pointafterwhichThroughput迅速减少到0(congestioncollapse)Delay接近正无穷LoadLoadThroughputDelaykneecliffcongestioncollapsepacketlossRTTMSSWCongestionControlvs.CongestionAvoidanceCongestioncontrolgoalStayleftofcliffCongestionavoidancegoalStayleftofkneeLoadThroughputkneecliffcongestioncollapsePossibleChoices（AIMD算法）Additiveincrease,multiplicativedecreaseaI0,bI=1,aD=0,0bD1Howtostart?ImplicitcongestionsignalLossNeedtosendpacketstodetectcongestionMustreconcile（一致）withAIMDHowtomaintainequilibrium（均衡）?UseACK:sendanewpacketonlyafteryoureceiveanACK.Maintainnumberofpacketsinnetwork“constant”decreasetxbaincreasetxbatxiDDiIIi)()()1(TCPCongestionControlsTahoe(Jacobson1988)SlowStartCongestionAvoidanceFastRetransmitReno(Jacobson1990)FastRecoveryVegas(Brakmo&Peterson1994)NewCongestionAvoidanceRED(Floyd&Jacobson1993)Probabilisticmarking（随机标志）REM(Athuraliya&Low2000)Clearbuffer,matchrateTCPTahoe1988年加入VanJacobson提出的慢启动、拥塞避免和快速重传算法之后的4.3BSD或类似的TCP实现版本。只有拥塞控制的前三部分,没有快速恢复。正如RFC793所要求的，Tahoe采用了递增式肯定重传策略和go-back-n模型（滑动窗口算法）。在不清楚网络环境的情况下向网络传送数据，要求TCP缓慢地探测网络以确定可用带宽，以避免突然传送大量数据而使网络拥塞。为达此目的，在传送开始时，采用了慢启动机制，这个机制在修复了由重发定时器探测到的数据丢失之后也被采用。TCPTahoe在慢启动阶段，拥塞窗口(cwnd)随着确认的到来以指数方式递增(这种以ACK来触发TRANSMIT的机制，被VJ称为ACKclocking，或self-clocking)，直到到达阀值ssthresh；之后TCP进入拥塞避免阶段，cwnd每隔RTT以线性方式递增1个单位。如果连续收到3个重复确认，TCP不等重传定时器溢出，马上重传丢失的报文段，这称为快速重传；之后TCP返回慢启动状态。TCPTahoe(Jacobson1988)Howtoadjustwindowineachphase?Whentoswitchphase?sstimewindowcass:slowstartca:congestionavoidanceSlowStartExampleThecongestionwindowsizegrowsveryrapidlyTCPslowsdowntheincreaseofcwndwhencwnd=ssthreshcwnd=1cwnd=2cwnd=4cwnd=8CongestionAvoidanceSlowdown“SlowStart”Ifcwndssthreshtheneachtimeasegmentisacknowledgedincrementcwndby1/cwnd(cwnd+=1/cwnd).Socwndisincreasedbyoneonlyifallsegmentshavebeenacknowlegded.Congestionavoidanceandslowstartareindependentalgorithmswithdifferentobjectives.Inpracticetheyareimplementedtogether.SlowStart/CongestionAvoidanceExampleAssumethatssthresh=8cwnd=1cwnd=2cwnd=4cwnd=8cwnd=9cwnd=1002468101214t=0t=2t=4t=6RoundtriptimesCwnd(insegments)ssthreshPuttingEverythingTogether: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);unacknextwinseq#PacketLossPacketlossdetectedbyRetransmissiontimeouts(RTOtimer)DuplicateACKs(atleast3)123456123PacketsAcknowledgements3373FastRetransmitImmediatelyretransmitsafter3dupACKswithoutwaitingfortimeout(fastretransmit)Adjustsssthreshssthreshmax(flightsize/2,2*SMSS)flightsize:Theamountofdatathathasbeensentbutnotyetacknowledged.EnterSlowStart(cwnd=1)Assumption:lossindicatescongestion(bufferoverflow)Thefastretransmitalgorithmfirstappearedinthe4.3BSDTahoerelease,anditwasfollowedbyslowstart.Summary:TahoeBasicideasGentlyprobenetworkforsparecapacityDrasticallyreducerateoncongestionWindowing:self-clocking（）Otherfunctions:roundtriptimeestimation,errorrecoveryforeveryack{ifWssthreshthenW++(ss)elseW+=1/W(ca)}foreveryloss{ssthresh:=W/2W:=1}TCPTahoe注：无论慢启动阶段还是拥塞避免阶段，只要发送端发现拥塞，根据是没有按时接收到ACK或收到重复ACK就要将慢启动的门限ssthresh设置为出现拥塞时的发送窗口的一半，然后将拥塞窗口值cwnd重新设置为1。注：Tahoe引入快速重传机制，即当接受者收到几个对同一TCP报文的相同应答时，发送方就推断已经发生了丢包，而没有必要的等到重传定时器超时，并且重传相应的包，提高了信道的利用率。Tahoe算法存在着不足之处：在收到3个重复ACK或在超时的情况下，Tahoe置cwnd为1，然后进入慢启动阶段。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。TCPRenoTCPReno在TCPTahoe之后,加入了快速恢复,所以可以认为TCPReno是TCPTahoe的改进版。在快速重传之后进入快速恢复（而不是TCPTahoe采用的慢启动）。VJ给出的原因是，接收方发送重复确认不仅仅意味着有报文段丢失了，还意味着有（其它的）报文段离开了网络，到达了接收方的缓冲区（self-clocking），也就是说，网络“管道”空出了新的位置，这样TCP可以继续发送新的报文段（当然cwnd应该减小一些）。它有效地避免了当前网络拥塞状况不够严重时，采用“慢启动”算法容易造成发送窗口减小的幅度过大的问题，避免了在快速重传后通道为空的现象。TCPReno(Jacobson1990)Slowstart,congestionavoidance,fastretransmitAddition:fastrecoveryMostwidelyusedversionofTCPtodaysstimewindowcass:slowstartca:congestionavoidanceFastrecoveryMotivation:prevent`pipe’fromemptyingafterfastretransmitEnterFR/FRafter3dupACKsSetssthreshmax(flightsize/2,2*SMSS)RetransmitlostpacketSetcwndssthresh+3(windowinflation)EachtimeanotherduplicateACKarrives,cwnd+=MSS.Transmitapacket,ifallowedbythenewvalueofcwnd.Onnon-dupACK(1RTTlater),setcwndssthresh(windowdeflation)EnterCAExample:FR/FRFastretransmitRetransmiton3dupACKsFastrecoveryInflate(扩大)windowwhilerepairinglosstofillpipeThefastrecoveryalgorithmappearedinthe4.3BSDRenorelease.12timeStimeD345687100070099000111？ExitFR/FRRTT8Summary:RenoBasicideasFastrecoveryavoidsslowstartdupACKs:fastretransmit+fastrecoveryTimeout:fastretransmit+slowstart？？Atsteadystate,cwndoscillates（振荡）aroundtheoptimalwindowsize.slowstartretransmitcongestionavoidanceFR/FRdupACKstimeoutTCPReno但TCPReno算法仍有不足首先,源端在检测到拥塞后,要重传自数据包丢失到检测到丢失时发送的全部数据包(即Go-back-n算法),而这中间有些数据包是正确传到接收端,不必重传的.TCPReno在一个窗口中的多个报文段同时丢失的情况下会