tahoe

TCP快速重传与快速恢复原理分析

标签：tcp算法网络lessstructurenetwork

2012-02-0318:0719177人阅读评论(3)收藏举报

分类：

TCP/IP（83）

作者同类文章X

版权声明：本文为博主原创文章，转载请注明出处。

超时重传是TCP协议保证数据可靠性的一个重要机制，其原理是在发送一个数据以后就开

启一个计时器，

在一定时间内如果没有得到发送数据报的ACK报文，那么就重新发送数据，直到发送成功

为止。这是数据

包丢失的情况下给出的一种修补机制。一般来说，重传发生在超时之后，但是如果发送端接

收到3个以上

的重复ACK，就应该意识到，数据丢了，需要重新传递。这个机制不需要等到重传定时器

溢出，所以叫

做快速重传，而快速重传以后，因为走的不是慢启动而是拥塞避免算法，所以这又叫做快速

恢复算法。

快速重传和快速恢复旨在：快速恢复丢失的数据包。

没有快速重传和快速恢复，TCP将会使用定时器来要求传输暂停。在暂停这段时间内，没

有新的数据包

被发送。

快速重传和快速恢复算法是在4.3BSD中提出的，并在RFC2001和RFC2581中描述。

快速重传与快速恢复经历了几个阶段。

Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼近可用

信道容量，然后

慢慢接近均衡。Tahoe包括3个基本的拥塞控制算法：慢启动、拥塞避免、快速重传。

我们可以看到，Tahoe不存在快速恢复算法。这也是它的不足之处。

在收到3个重复ACK或者在超时的情况下，Tahoe置cwnd为1，然后进入慢启动阶段。

这一方面会引起网

络的激烈震荡，另一方面大大降低了网络的利用率。

也就是说，一旦发现掉包，那么cwnd就被打回原形。

没有快速恢复算法，在恢复丢失数据包期间，不能发送新的数据包，这段时间的吞吐量为0。

而实际上

如果利用这段时间来发送适量的新数据包，可以大大的提高丢包时的传输效率。这就是快速

恢复名称的

由来。

Reno与Tahoe相比，增加了快速恢复阶段，也就是说，完成快速重传后，进入了拥塞避免

阶段而不是慢

启动阶段。

RenopreventsthecommunicationpathfromgoingemptyafterFastRetransmit.

RenonderusadditionalincomingdupACKstoclocksubquentoutgoingpackets.

算法描述：

step1：

if(dupacks>=3){

ssthresh=max(2,cwnd/2);

cwnd=ssthresh+3*SMSS;

}

step2：重传丢失的分组

step3：此后每收到一个重复的ACK确认时，cwnd++

step4：当收到对新发送数据的ACK确认时，cwnd=ssthresh，这个ACK能够对

那些在

丢失的分组之后，第一个重复ACK之前发送的所有包进行确认。

在快速恢复阶段，每收到重复的ACK，则cwnd加1；收到非重复ACK时，置cwnd=ssthresh，

转入拥塞避免阶段；如果发生超时重传，则置ssthresh为当前cwnd的一半，cwnd=1，

重新进入

慢启动阶段。

Reno快速恢复阶段退出条件：收到非重复ACK。

o

Reno不能有效的处理多个分组从同一数据窗口丢失，于是有了NewReno。

NewReno修改了Reno的快速恢复算法，处理一个窗口中的多个报文段同时丢失时出现的

“部分确认”

（PartialACKs，它在快速恢复阶段到达并且确认新数据，但它只确认进入快速重传之前发

送的一部分

数据）。

在这种情况下，Reno会退出快速恢复状态，等待定时器溢出或者重复的确认ACK到达，

但是NewReno

并不退出快速恢复状态，而是：

step1：重传紧接着那个部分ACK之后的报文段，拥塞窗口等于其减去partial

ACK的部分。

step2：对于得到确认的新数据，cwnd++

step3：对于第一个或每一个PartialACK，重传定时器复位。且每次都重置cwnd

=原cwnd/2。

NewReno算法中有变量recover，其值为检测到丢包时的最大发送序列号。只有当recover

之前的数据

报都确认完后，才能推出快速恢复，进入拥塞避免阶段。

当超时时，将发送的最大序列号保存在recover变量中，结束快速恢复过程。

NewReno不支持SACK。

DuringFastRecovery,SACKmaintainsavariablecalledpipethatreprentsthe

estimatednumber

ofpacketsoutstandinginthepath.

Thenderonlyndsneworretransmitteddatawhentheestimatednumberofpackets

inthepath

iablepipeisincrementedbyonewhenthe

ndereither

crementedbyonewhenthe

nderreceives

adupACKpacketwithaSACKoptionreportingthenewdatahasbeenreceivedatthe

receiver.

Uofthepipevariabledecouplesthedecisionofwhentondapacketfromthe

decisionofwhich

packettond.

Thendermaintainsadatastructure,thescoreboard,thatremenbers

acknowledgementsfrom

enderisallowedtondapacket,itretransmitsthe

nextpacket

earenosuchpackets

andthe

receiver'sadvertidwindowissufficientlylarge,thenderndsanewpacket.

Whenaretransmittedpacketisitlfdropped,theSACKimplementationdetectsthedrop

witha

retransmittimeout,retransmittingthedroppedpacketandthenslow-starting.

ThenderexitsFastRecoverywhenarecoveryacknowledgementisreceived

acknowledging

alldatathatwasoutstandingwhenFastRecoverywantered.

step1:

FastRecoveryisinitiated,

pipe-1(forthepacketassumedtohavebeen

dropped).

pipe+1(forthepacketretransmitted)

cwnd=cwnd/2

step2:

Ifpipe<=cwnd，nderretransmitspacketsinferredtobe

missing.

Iftherearenosuchpackets,nderndsnewpackets.

step3:

whennderreceivesadupACK,pipe=pipe-1

whennderndsanew/retransmitanoldpacket,pipe=pipe

+1

step4:

ForpartialACKs：pipe=pipe-2

(onefororiginaldroppedpacket，oneforretransmittedpacket)

step5:

allpacketsoutstandingbeforeFastRecoverywereACKed,

exitFastRecovery.

当退出FastRecovery时，cwnd同样恢复成ssthresh，进入拥塞避

免。

与Reno不同的是：

（1）whentondpacket：由计算pipe变化决定，不再是计算cwnd变化。

（2）whichpackettond：由SACK携带信息决定，反应更迅速。

问题1：在一个窗口内重复丢包会造成影响吗？

答案：会。如果只丢一个包，那么收到非重复ACK时，就能确认完本窗口内所有的包。然

后进入拥塞

避免阶段。这就是Reno想达到的。

而如果丢失多个包，那么收到非重复ACK时，不能确认完本窗口内所有的包。但是，也会

退出快速恢复，

进入拥塞避免阶段。

这个时候可能会发生两种情况：

（1）多次进行快速重传和快速恢复。又发现丢包，再次进入快速重传和快速恢复。注意，

每次进入

快速重传和快速恢复时，ssthresh和cwnd都要减半。多次丢包最终会导致ssthresh指数

减小。

通过画cwnd(t)图可以发现，不仅这段时间吞吐量非常低，而且导致恢复完后拥塞避免的起

点非常低，从

而导致之后的吞吐量也很低。

（2）经过多次快速重传和快速恢复，接着发生传输超时。

那么，发生传输超时需要什么样的条件呢？

1)whentwopacketsaredroppedfromawindowofdata,theRenonderisforcedtowait

fora

retransmittimeoutwheneverthecongestionwindowislessthan10packetswhenFast

Recoveryisinitiated,andwheneverthecongestionwindowiswithintwopacketsofthe

receiver's

advertidwindowwhenFastRecoveryisinitiated.

2)whenthreepacketsaredroppedfromawindowofdata,theRenonderisforcedto

waitfor

aretransmittimeoutwheneverthenumberofpacketsbetweenthefirstandthecond

dropped

packetsislessthan2+3W/4,forWthecongestionwindowjustbeforetheFast

Retransmit.

这种情况出现的概率极大，也就是说一个窗口出现3个丢包，有大概率出现超时。当丢包

时窗口大小

为15，有三个丢包，那么无论丢包的顺序如何，2次FR/FR之后，总会出现超时。

超时一般是因为未确认的数据包>可以使用的cwnd，不能发送新的数据，而网络中有没

有足够的

重复ACK来触发FR/FR。

问题2：为什么发生拥塞时，还增加cwnd？

答案：在检测到丢包时，窗口为cwnd。这时候网络中最多有cwnd个包（in_flight

每当收到

一个重复的ACK，则说明有数据包离开网络，达到接收端了。那么，此时网络中还可以再

容纳1个包。由

于发送端滑动窗口不能移动了，所以如果想保持in_flight，可以使cwnd++。

这样一来，可以提高吞吐量。而实际上，在fastrecovery期间发送的新数据包比起发生丢

包的cwnd来说，

已经是大大减少了。

性能分析

Tahoe没有快速恢复机制，在丢包后，它不仅重发了一些已经成功传输的数据，而且在恢

复期间吞吐量

也不高。

利用SACKoption携带的信息，我们能够提前知道哪些数据包丢失了。NewReno每个RTT

内只能恢复

一个丢失的数据包，所以如果丢失了N个数据包，那么FastRecovery就要持续N*RTT的

时间，当N比较

大时，这是一段相当长的时间。而SACK则没有这个限制，依靠SACKoption的信息，它

能够同时恢复

多个数据包，更加快速和平稳的恢复。

当发生同一窗口多个丢包时，SACK和NewReno最终都能够较为快速和平稳的恢复过来。

而Reno则经

常出现超时，然后再用慢启动来恢复，这个时候Reno的表现就如同Tahoe，会造成已接受

数据的重复

传送。Reno恢复期间会出现吞吐量低、恢复时间长、不必要重发数据、恢复结束后阈值过

低等一些问

题，严重的影响性能。

结论

经过上述分析我们可以看出：

ItisafundamentalconquenceoftheabnceofSACKthatthenderhastochoo

between

thefollowingstrategiestorecoverfromlostdata:

（1）retransmittingatmostonedroppedpacketperround-triptime

（2）retransmittingpacketsthatmighthavealreadybeensuccessfullydelivered.

RenoandNew-Renouthefirststrategy,andTahoeusthecond.

WithSACK,andercanavoidunnecessarydelaysandretransmissions,resultingin

improved

throughput.

SACK的不足

上面说了很多SACK的好话，现在来谈谈它的不足之处。

ForalargeBDPnetworkwherethenumberofpacketsareinflight,theprocesing

overheadof

SACKinformationattheendpointscanbequiteoverhelmingbecaueachSACKblock

invokes

arearchintothelargepacketbuffersofthenderforackedpacketsintheblock,and

every

recoveryofalosspacketcausthesamearchatthereceiver.

在BDP网络，这个问题尤其明显，会严重的消耗CPU而导致一系列问题。在一定程度上

来说，此时

的SACK就像DOS攻击一样，每次遍历都要消耗大量CPU，时间复杂度为O（n^2），n

为packetsin

flight的数量。

Thesystemoverloadcancauriousproblem:itcancaumultipletimeouts(aven

packet

retransmissionandreceptionsaredelayed)andalongperiodofzerothroughput.

当然，这是中等规模的BDP（100~1000）或大规模的BDP网络才需考虑的问题，对于一

般的BDP而

言不会出现太大的问题。