TCP快速恢復算法NewReno修正

本備忘錄的狀態
本文檔講述了一種Inte.net社區的Internet標準跟蹤協議，它需要進一步進行討論和建
議以得到改進。請參考最新版的“Internet正式協議標準”(STD1)來獲得本協議的標準化
程度和狀態。本備忘錄的發布不受任何限制。
版權聲明
Copyright(C)TheInternetSociety(2001).
摘要：
RFC2001[RFC2001]講述了以下四種相互作用的TCP擁塞控制算法：慢啟動，擁塞避免，
快速重傳，以及快速恢復。RFC2581[RFC2581]明確地允許對這些算法進行某些改動，包括
如下改動，使用TCP選擇確認（SACK）選項[MMFR96],以及在沒有SACK的情況下響應“部分
確認”(在檢測到數據丟失時，新數據的ACKs，而不是發送的所有數據的ACKs)。這篇文檔
描述了響應部分確認的一個特定算法，稱為NewReno。對部分確認的響應由JaneyHoe在
[Hoe95]中首次提出。


目錄
1.介紹 2
2.定義 2
3.NewReno中的快速重傳和快速恢復算法 2
4.重設重傳定時器 4
5.避免多次快速重傳 4
6.數據接收端的實現問題 5
8.總結 6
9.致謝 6
10.參考文獻 6
11.安全考慮 7
12.作者地址 7
13.完全版權說明 8

1.介紹
對[RFC2581]（在1990年的BSDReno發行版中首次實現，在[FF96]稱之為Reno算法）
中描述的TCP快速恢復算法的典型實現，TCP數據發送端在發生一個超時重傳時僅僅重傳一
個數據包，或者當三個重復確認到達時觸發快速重傳算法。單單一個超時重傳可能導致許多
數據包的重傳，但是每次Reno快速重傳算法的啟用僅僅導致一個數據包的重傳。
因此，當多個數據包從一個數據窗口中丟失并且觸發快速重傳和快速恢復算法時，問題
就會產生。在這種情況下，如果SACK選項可用，TCP發送端在快速恢復期間就有足夠的信
息來決定重傳哪個數據包，不重傳哪個數據包。這篇文檔僅對不能使用TCP選擇確認（SACK）
選項的TCP連接適用。
在沒有SACK的情況下，TCP發送端在快速恢復期間只能得到很少的信息來作出重傳決
定。從三個重復確認中，發送端推斷出一個數據包丟失了，并且重傳那個聲明了數據包。在
這之后，數據發送端可能接收到另外的重復確認，因為在發送端進入快速重傳時，數據端確
認已經發送的附加數據包。
在多個數據包從一個數據窗口中丟失這種情況下，當發送端從對重傳的數據包（就是第
一次進入快速重傳時重傳的數據包）的一個確認時，它獲得第一條可用新信息。如果只有一
個數據包丟失了，對這個重傳的數據包的確認將確認所有進入快速重傳（在沒有重新排序的
情況下）之前發送的數據包。但是，當有多個數據包丟失時，對此重傳數據包的確認將僅確
認一些而不是所有在快速重傳之前發送的數據包。我們稱這個包是一個部分確認。
和許多其它的建議一起，[Hoe95]建議在快速恢復期間TCP數據發送端通過推斷聲明的
數據包已經丟失和重傳那個數據包的方式響應一個部分確認。這篇文檔描述了對RenoTCP
里的快速恢復算法的一個修正，RenoTCP包括了快速恢復期間對接收到的部分確認的一個
響應。我們稱這處修正過的快速恢復算法為NewReno，因為它與基礎的Reno算法有一些細
小但是很重要的不同。這篇文檔沒有討論[Hoe95]和[Hoe96]中的其它建議，比如在慢啟動期
間ssthresh參數的一個變化，及在快速恢復期間為每兩個重復確認發送一個新數據包的建
議。這篇文檔里的NewReno方案也使用了文獻[LM97]中的NewReno的討論。
我們沒有說對于不能使用SACK的TCP，這里描述的快速恢復的NewReno方案是響
應部分確認的一個可選修正。根據我們在NS模擬器上的NewReno修正經驗，我們相信這個
修正在很多地方都改善了快速重傳和快速恢復的性能，我們僅僅是為了IETF團體的利益而
將它文檔化。我們鼓勵使用對快速恢復的這一修正，并且我們還鼓勵反饋關于此修正或相關
修正的操作經驗。
2.定義
這篇文檔假設讀者熟悉[RFC2581]中定義的術語：最大段尺寸(MSS),擁塞窗口(cwnd),
和傳送尺寸（FlightSize）。傳送尺寸在[RFC2581]中是如下定義的：
傳送尺寸：已經發送但還沒有確認的數據量。
3.NewReno中的快速重傳和快速恢復算法
標準的快速重傳和快速恢復算法實現在[RFC2581]給出。這些算法的NewReno修正在下
面給出。NewReno修正[RFC2581]里的實現的不同僅在于步驟1中的變量“recover”的引入，
以及步驟5中對一個部分或新的確認的響應。修正定義了一個“快速恢復過程”，它在接收
到三個重復ACK時開始，并在一個超時重傳發生或一個確認所有在快速恢復過程開始后發送
的數據的ACK到達時結束。
1.當收到第三個重復ACK并且發送端還沒有處于快速恢復過程時，設置ssthresh不大
于下面等式1中給出的值。（這是[RFC2581]中的等式3）。
ssthresh=max(FlightSize/2,2*MSS)(1)
用變量“recover”記錄傳送的最大序列號。
2.重傳丟失的段并設置cwnd為ssthresh乘以3*MSS。這將人為地按已經離開網絡的報
文段數目（3）和接收端緩沖數據量來擴充擁塞窗口。
3.對每個接收到的額外的重復ACK，將cwnd增大SMSS字節。這將人為地擴充擁塞窗口
以反映已經離開網絡的附加數據段。
4.發送一個數據段，如果cwnd和接收端的通知窗口的值允許的話。
5.當一個確認新數據的ACK到達時，此ACK可能是由步驟2中的重傳引發的確認，或者
是由稍后的一次重傳引起的。
如果這個ACK確認了直到并包含“recover”的數據，那么這個ACK確認了所有在丟
失段的原始傳送和第三個重復ACK接收之間的段。設置cwnd為（1）
min(ssthresh,FlightSize+MSS)；或者(2)ssthresh,這里的ssthresh是步驟1中設置的值；
這稱為“deflating”窗口。（我們注意到步驟1中“FlightSize”指的是當進入快速恢復時
步驟1中發送的數據量，步驟5中的“FlightSize”指的是當退出快速恢復時發送的數據量。）
如果選擇了另一個選項，實現應該采取措施避免可能的數據爆發，萬一向網絡中發送的數據
量遠小于新擁塞窗口允許的量[HTH98]的話。退出快速恢復過程。
如果這個ACK不確認所有并包含到“recover”的數據的話，就產生一個部分ACK。在
此種情況下，重傳第一個沒有確認的數據段。按確認的新數據量來減小擁塞窗口，然后加回
一個MSS并發送一個新數據段，如果cwnd的新值允許的話。這個“部分窗口縮減”試圖確
定這一點，當快速恢復最終結束時，大約ssthresh數量的數據還在向網絡中傳送。不要退
出快速恢復過程（也就是說，如果任何重復ACK隨后到達，執行上面的步驟3和4）。
對在快速恢復期間第一個到達的部分ACK，也要重設重傳定時器。
注意到在步驟5中，擁塞窗口在一個部分確認收到時減小。擁塞窗口在部分確認收到時
可能已經大幅膨脹。另外，根據丟失數據包的類型，部分確認可能確認將近一個窗口的數據。
在這種情況下，如果擁塞窗口沒有減小，數據端可能能夠緊接著發送將近一個窗口的數據。
上面描述的對部分確認的簡單響應可能有許多變形。首先，一個問題是部分確認之后何
時重設定時器。這在下面的第4節進一步討論。
一個相關的問題是在每一個部分確認之后，重傳多少數據包。上面描述的算法在每個部
分確認之后重傳一個數據包。這是最保守的選擇，因為這種辦法最沒有可能導致一個沒有必
要重傳的數據包。有效地慢啟動也是一個變形，它能從丟失了許多數據包的窗口中更快地恢
復過來，但是要求從丟失了N個數據包[Hoe96]的恢復必須少于N來回時間。對部分確認采
用這種稍微激烈一點的響應的話，在每個重傳之后重設重傳定時器就會很有利。因為我們還
沒有在我們的模擬器上試驗這種變形，我們在這篇文檔中不會進一步對此進行討論。
第三個問題是避免由接收端已經到的數據包的重傳引起的多次快速重傳。這在下面的第
5節中討論。避免多次快速重傳在對部分確認采用更激烈的響應的情況下特別重要，因為在
這種情況下，發送端更可能重傳接收端已經接收的數據包。
最后，我們考察一下沒有SACK選項的情況，數據發送端在沒有足夠信息的情況下工作。
一個發送端可能花很長時間仔細考慮在這種情況哪個快速恢復的變形對這種環境是最優的。
因為從丟失了多個數據包的一個窗口中恢復的問題特別重要，所以最好的選擇是使用SACK
選項。
4.重設重傳定時器
第3節的算法僅在第一個部分ACK之后重設重傳定時器。在這種情況下，如果很多數據
包從一個窗口中丟失了，TCP數據發送端的重傳定時器最終將超時，接著TCP數據發送端將
調用慢啟動。（這在[F98]在12頁中被例證。）我們稱此為NewReno的Impatient變形。
相反地，[FF96]中的NewReno模擬例證了上面描述的算法，不同的是重傳定時器在每個
部分確認之后都要重設。我們稱此為Slow-but-Steady變形。在這種情況下，對于一個丟失
了大量數據包的窗口來說，TCP數據發送端每個來回時間至少發送一個數據包。（這種行為
在[FF96]中的NewRenoTCP模擬和[F98]的11頁中被例證。）
對于超時重傳值（RTO）一般不大于往返時間（RTT）的TCP實現來說，Impatient變形
即使在只有少量數據包丟失的情況下也會導致一個超時重傳。對于超時重傳值（RTO）一般
遠大于往返時間(RTT)的TCP實現來說，Slow-but-Steady變形當多個數據包從一個窗口中
丟失時能夠長時間維持快速恢復。這些變形沒有一個是最優的；一個更優的算法可能是某個
從多個數據包丟失中迅速恢復，并且在重設重傳定時器時與Slow-but-Steady進行混合的算
法。然而我們注意到，在沒有SACK選項的情況下，對潛在性能有個限制。
5.避免多次快速重傳
在沒有SACK選項時，一個重復確認沒有攜帶任何有關信息，這種信息是用來確定TCP
數據接收端觸發重復確認的一個或多個數據包的。TCP數據發送端不能把區分重復確認是由
數據包丟失或延時引起的，還是由發送端重傳了一個TCP接收端已經接收到的數據包引起
的。由于這個原因，一個窗口的多個數據段丟失某些時候能導致不必要的多次重傳（以及擁
塞窗口的多次縮減）[Flo94]。
在Reno或NewRenoTCP中使用了快速重傳和快速恢復算法的話，由多次快速重傳引起
的性能問題就相對小一些（和TahoeTCP的潛在問題相比，它沒有實現快速恢復）。然而，
Reno或NewRenoTCP也會發生不必要的快速重傳，特別是如果快速恢復期間發生了一個重
傳超時的話。（這在［F98］第6頁中作為Reno的例證，第8頁中作為NewReno的例證。）有
NewReno的話，數據發送端一直處于快速恢復，直到發生一個超時重傳，或者快速重傳時發
送的所有數據都已得到確認。因此有了NewReno，多次快速重傳的問題只有在一個超時重傳
后才發生。
接下來對第3節中算法的修正消除了多次快速重傳的問題。（這個修正在[F98]中稱為
“bugfix”，在第7和第9頁中說明。）這個修正使用了一個新變量“send_high”，它的初始
值是最初發送的序列號。每次超時重傳之后，到目前為止發送的最大序列號記錄到
“send_high”變量中。
如果在一個超時重傳之后，TCP數據發送端重傳了三個連續的數據包，而這此數據包數
據接收端已經接收到了，這樣的話TCP數據發送端就將接收到三個重復確認，這此確認并沒
有確認“send_high”號數據包。在這種情況下，重復確認并不能表明又發生了擁塞。它們
只是表明發送端沒有必要地重傳了至少三個數據包。
我們注意到如果如果TCP數據發送端接收到三個重復確認，而這些重復確認并沒有確認
“send_high”號數據包，這樣發送端就不知道這此重復確認是否是由一個新數據包的丟失
引起的。對一個實現了這節描述的用來避免多次快速重傳的bugfix的TCP而言，發送端在
這些情況下并不會由重復確認推斷出一個數據包丟失了。和往常一樣，重傳定時器在這種情
況又成了推斷數據包丟失的支持機制。
為避免多次快速重傳而對快速重傳作的修正用下面的步驟1A代了第3節中的步驟1。
另外，此修正增加了下面的步驟6：
1A.當接收到第三個重復ACK并且發送端還沒有進入快速恢復過程時，檢查并且看看這
些重復ACK有沒有確認“send_high”號數據包。如果有,設置ssthresh的值不大于等式1
中給出的值,在變量"recover"中記錄發送的最大序列號,然后轉到步驟2.如果重復ACK沒
有確認"send_high"號數據包,就什么也不做。也就是不要進入快速重傳和快速恢復過程,
不要改變ssthresh值,不要轉到步驟2以重傳"丟失的"數據段,并且不要在下一個重復ACK
到之前不要執行步驟3。
步驟2-5和第三節的步驟一樣。
6.一個超時重傳之后,在變量"send_high"中記錄發送的最大序列號,并退出快速恢復
過程,如果可以的話。
上面的1A步驟中檢查重復ACK是否確認"send_high"以后的數據包,這是對此算法的
careful變形。另一個可能的改變會是簡單地要求三個重復確認在開始另一個快速重傳之前
確認"send_high"號數據包。我們稱之為對快速重傳的lesscareful變形。
在兩種個別情況下,TCP發送端能接收到確認"send_high"號數據包的重復確認,但對
大于"send_high"號的數據包不確認。一種情況是數據發送端發送了四個序列號大于
"send_high"的數據包,第一個數據包丟失在網絡中,接下來的三個數據包觸發了三個重復
確認,這些確認確認了"send_high"號數據包。第二種情況是發送端不必要地重傳了三個序
列號小于"send_high"的數據包,并且這三個數據包觸發了三個確認了"send_high"號數
據包的重復確認。在沒有SACK選項的情況下,TCP發送端不能區分這兩種情況。
對快速重傳的Careful變形而言,數據發送端在第一種情況下必須等待一個超時重傳,
但在第二種情況下不會產生不必要的快速重傳。對快速重傳的lessCareful變形而言,數據
發送端會按第一種情況的需要快速重傳,并且在第二種情況下會不必要地快速重傳。NS模擬
器已經實現了NewReno的LessCareful變形,Sun的Solaris7上的TCP實現實現了Careful
變形.這篇文檔推薦上面的1A步驟給出的Careful變形。
6.數據接收端的實現問題
[RFC2001]闡述說“次序混亂的數據段應該迅速確認，以觸發快速重傳算法?！盢eal
Cardwell已經指出，一些數據接收端在發送一個部分確認時不迅速發送一個確認，而是首
先等待它們的延遲確認定時器超時[C98]。正如[C98]指出的，這嚴重限制了來自NewReno的
效益，因為它延遲了數據發送端部分確認的接收。我們的建議是，數據接收端為一個次序混
亂的數據段迅速發送一個確認，即使當次序混亂的段在緩沖區中時也一樣。
7.模擬
有NewReno的模擬在NS模擬器上用用效性測試"tcl/test/test-all-newreno"來例
證。命令“../../nstest-suite-newreno.tclreno”顯示了RenoTCP的一個模擬，例證
了數據發送端缺乏對一個部分確認的響應。相反地，命令“../../nstest-suite-newreno.tcl
newreno_B”顯示了這篇文檔描述的使用NewReno算法的相同情境的模擬。
測試“../../nstest-suite-newreno.tclnewreno1_B0”和“../../ns
test-suite-newreno.tclnewreno1_B”分別顯示了NewReno的Slow-but-Steady變形和
Impatient變形。
8.總結
我們的建議是TCP實現包括第3節給的快速恢復算法的NewReno修正，以及第5節給的
用來避免多次快速重傳的修正。第3節給的NewReno修正即使對支持SACK選項的TCP實現
也是很重要的，因為SACK選項只有當兩個TCP結點都支持SACK選項時才能使用。第3節給
的NewReno修正實現了NewReno的Impatient而不是Slow-but-Steady修正。
盡管這篇文檔提到了許多NewReno算法的可能的變化，但是我們沒有對所有這些可能的
變化進行探討，所以不能提出和其中一些有關的建議。我們相信，任何兩個NewReno變形之
間的不同比Reno和NewReno之間的不同要小。也就是說，重要的是實現NewReno而不是Reno，
對一個沒有SACK的TCP調用來說，具體NewReno的哪個變形被實現并不重要。
9.致謝
感謝AnilAgarwal,MarkAllman,VernPaxson,KacheongPoon,和BernieVolz關于
這篇文檔的細致的反饋。
10.參考文獻
[C98]NealCardwell,"delayedACKsforretransmittedpackets:
ouch!".November1998.Emailtothetcpimplmailing
list,Message-ID"Pine.LNX.4.02A.9811021421340.26785-
100000@sake.cs.washington.edu",archivedat
"http://tcp-impl.lerc.nasa.gov/tcp-impl".
[F98]SallyFloyd.RevisionstoRFC2001.Presentationto
theTCPIMPLWorkingGroup,August1998.URLs
"ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.ps"and
"ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.pdf".
[FF96]KevinFallandSallyFloyd.Simulation-based
ComparisonsofTahoe,RenoandSACKTCP.Computer
CommunicationReview,July1996.URL
"ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z".

[Flo94]S.Floyd,TCPandSuclearcase/" target="_blank" >ccessiveFastRetransmits.
Technicalreport,October1994.URL
"ftp://ftp.ee.lbl.gov/papers/fastretrans.ps".
[Hen98]TomHenderson,Re:NewRenoandthe2001Revision.

September1998.Emailtothetcpimplmailinglist,
MessageID"Pine.BSI.3.95.980923224136.26134A-
100000@raptor.CS.Berkeley.EDU",archivedat
"http://tcp-impl.lerc.nasa.gov/tcp-impl".
[Hoe95]J.Hoe,StartupDynamicsofTCP'sCongestionControl
andAvoidanceSchemes.Master'sThesis,MIT,1995.URL
"http://ana-www.lcs.mit.edu/anaweb/ps-papers/hoe-
thesis.ps".
[Hoe96]J.Hoe,"ImprovingtheStart-upBehaviorofa
CongestionControlSchemeforTCP",InACMSIGCOMM,
August1996.URL
"http://www.acm.org/sigcomm/sigcomm96/program.html".
[HTH98]Hughes,A.,Touch,J.andJ.Heidemann,"IssuesinTCP
Slow-StartRestartAfterIdle",WorkinProgress,March
1998.
[LM97]DongLinandRobertMorris,"DynamicsofRandomEarly
Detection",SIGCOMM97,September1997.URL
"http://www.acm.org/sigcomm/sigcomm97/program.html".
[MMFR96]Mathis,M.,Mahdavi,J.,Floyd,S.andA.Romanow,"TCP
SelectiveAcknowledgementOptions",RFC2018,October
1996.
[NS]TheUCB/LBNL/VINTNetworkSimulator(NS).URL
"http://www-mash.cs.berkeley.edu/ns/".
[RFC2001]Stevens,W.,"TCPSlowStart,CongestionAvoidance,
FastRetransmit,andFastRecoveryAlgorithms",RFC
2001,January1997.
[RFC2581]Stevens,W.,Allman,M.andV.Paxson,"TCPCongestion
Control",RFC2581,April1999.
11.安全考慮
RFC2581討論了有關TCP擁塞控制的一般安全考慮。這篇文檔描述了一個特殊算法，它
符合RFC2581的擁塞控制要求，因此那些考慮也適用此算法。已知的還沒有其它關于這個特
殊算法的安全考慮。
12.作者地址
SallyFloyd
AT&TCenterforInternetResearchatICSI(ACIRI)
Phone:+1(510)642-4274x189
EMail:floyd@acm.org
URL:http://www.aciri.org/floyd/
TomHenderson
UniversityofCaliforniaatBerkeley
Phone:+1(510)642-8919
EMail:tomh@cs.berkeley.edu
URL:http://www.cs.berkeley.edu/~tomh/
13.完全版權說明
Copyright(C)TheInternetSociety(1999).AllRightsReserved.
Thisdocumentandtranslationsofitmaybecopiedandfurnishedto
others,andderivativeworksthatcommentonorotherwiseexplainit
orassistinitsimplementationmaybeprepared,copied,published
anddistributed,inwholeorinpart,withoutrestrictionofany
kind,providedthattheabovecopyrightnoticeandthisparagraphare
includedonallsuchcopiesandderivativeworks.However,this
documentitselfmaynotbemodifiedinanyway,suchasbyremoving
thecopyrightnoticeorreferencestotheInternetSocietyorother
Internetorganizations,exceptasneededforthepurposeof
developingInternetstandardsinwhichcasetheproceduresfor
copyrightsdefinedintheInternetStandardsprocessmustbe
followed,orasrequiredtotranslateitintolanguagesotherthan
English.
Thelimitedpermissionsgrantedaboveareperpetualandwillnotbe
revokedbytheInternetSocietyoritssuccessorsorassigns.
Thisdocumentandtheinformationcontainedhereinisprovidedonan
"ASIS"basisandTHEINTERNETSOCIETYANDTHEINTERNETENGINEERING
TASKFORCEDISCLAIMSALLWARRANTIES,EXPRESSORIMPLIED,INCLUDING
BUTNOTLIMITEDTOANYWARRANTYTHATTHEUSEOFTHEINFORMATION
HEREINWILLNOTINFRINGEANYRIGHTSORANYIMPLIEDWARRANTIESOF
MERCHANTABILITYORFITNESSFORAPARTICULARPURPOSE.