1、<p>　　譯文2 The Algorithm of Congestion Control</p><p>　　1．Tahoe TCP </p><p>　　Modern TCP implementations contain a number of algorithms aimed at controlling network congestion while maintai

2、ning good user throughput. Early TCP implementations followed a go-back-n. model using cumulative positive acknowledgment and requiring a retransmit timer expiration to re-send data lost during transport. These TCPs did

3、little to minimize network congestion. </p><p>　　The Tahoe TCP implementation added a number of new algorithms and refinements to earlier implementations. The new algorithms include Slow-Start, Congestion Av

4、oidance, and Fast Retransmit. The refinements include a modification to the round-trip time estimator used to set retransmission timeout values. All modifications have been described elsewhere.</p><p>　　The

5、Fast Retransmit algorithm is of special interest in this paper because it is modified subsequent versions of TCP. With Fast Retransmit, after receiving a small number of duplicate acknowledgments for the same TCP segment

6、 (dup ACKs), the data sender infers that a packet has been lost and retransmits the packet without waiting for a retransmission timer to expire, leading to higher channel utilization and connection throughput.</p>

7、<p>　　2．Reno TCP</p><p>　　The Reno TCP implementation retained the enhancements incorporated into Tahoe, but modified the Fast Retransmit operation to include Fast Recovery. The new algorithm prevents

8、the communication path (“pipe”) from going empty after Fast Retransmit, thereby avoiding the need to Slow-Start to refill it after a single packet loss. Fast Recovery operates by assuming each dup ACK received represents

9、 a single packet having left the pipe. Thus, during Fast Recovery the TCP sender is able to make intellig</p><p>　　In Reno, the sender's usable window becomes other gateways that fail to monitor the aver

10、age queue size) until the number of dup ACKs reaches tcprexmtthresh, and thereafter tracks the number of duplicate ACKs. Thus, during Fast Recovery the sender “inflate” its window by the number of dup ACKs it has receive

11、d, according to the observation that each dup ACK indicates some packet has been removed from the network and is now cached at the receiver. After entering Fast Recovery and retransmitting a s</p><p>　　3．New

12、-Reno TCP </p><p>　　We include New-Reno TCP in this paper to show how a simple change to TCP makes it possible to avoid some of the performance problems of Reno TCP without the addition of SACK. At the same

13、time, we use New-Reno TCP to explore the fundamental limitations of TCP performance in the absence of SACK. </p><p>　　The New-Reno TCP in this paper includes a small change to the Reno algorithm at the sende

14、r that eliminates Reno's wait for a retransmit timer when multiple packets are lost from a window. The change concerns the sender's behavior during Fast Recovery when a partial ACK is received that acknowledges s

15、ome but not all of the packets that were out-standing at the start of that Fast Recovery period. In Reno, partial ACKs take TCP out of Fast Recovery by “deflating” the usable window back to the size </p><p>

16、　　The implementations of New-Reno and SACK TCP in our simulator also use a “maxburst” parameter. In our SACK TCP implementation, the “maxburst” parameter limits to four the number of packets that can be sent in response

17、to a single incoming ACK, even if the sender's congestion window would allow more packets to be sent. In New-Reno, the “maxburst” parameter is set to four packets outside of Fast Recovery, and to two packets during F

18、ast Recovery, to more closely reproduce the behavior of Reno TCP d</p><p>　　4．SACK TCP </p><p>　　The SACK option follows the format in [MMFR96]. From [MMFR96], the SACK option field contains a n

19、umber of SACK blocks, where each SACK block reports a non-contiguous set of data that has been received and queued. The first block in a SACK option is required to report the data receiver's most recently received se

20、gment, and the additional SACK blocks repeat the most recently reported SACK blocks [MMFR96]. In these simulations each SACK option is assumed to have room for three SACK blocks. When the</p><p>　　The 1990 “

21、Sack” TCP implementation on our previous simulator is from Steven McCanne and Sally Floyd, and does not conform to the formats in [MMFR96]. The new “Sack1”implementation contains major contributions from Kevin Fall, Jams

22、hid Mahdavi, and Matt Mathis. </p><p>　　The congestion control algorithms implemented in our SACK TCP are a conservative extension of Reno's congestion control, in that they use the same algorithms for

23、increasing and decreasing the congestion window, The SACK TCP implementation in this paper, called “Sack1”in our simulator, is also discussed in. and make minimal changes to the other congestion con-trol algorithms. Addi

24、ng SACK to TCP does not change the basic underlying congestion control algorithms. The SACK TCP implementation preserv</p><p><b>　　擁塞控制中的算法</b></p><p>　　1．Tahoe TCP</p><p&

25、gt;　　TCP Tahoe指的是1988年加入Van Jacobson提出的慢啟動、擁塞避免和快速重傳算法之后的4.3BSD或類似的TCP實現(xiàn)版本。正如RFC793所要求的，Tahoe采用了遞增式肯定重傳策略和"go-back-n"模型(滑動窗口算法)。在慢啟動階段，擁塞窗口(cwnd)隨著確認的到來以指數(shù)方式遞增(這種以ACK來觸發(fā)TRANSMIT的機制，被VJ稱為"ACK clocking"

26、，或"self-clocking")，直到到達閥值ssthresh(slow start threshold)；之后TCP進入擁塞避免階段，cwnd每隔RTT以線性方式遞增1個單位。如果連續(xù)收到3個重復確認，TCP不等重傳定時器溢出，馬上重傳丟失的報文段，這稱為快速重傳；之后TCP返回慢啟動狀態(tài)。早期的TCP實現(xiàn)算法是基于積極響應并通過重傳來重發(fā)丟失的數(shù)據(jù)，當丟包時，TCP減小擁塞窗口，并重傳被丟失的分組，然而在使用

27、網絡擁塞達到最小方面，這些算法的性能很差。TCP Tahoe 參考了早期的實現(xiàn)方法，并增加一些算法，包括慢啟動：窗口大小以指數(shù)速度增加；擁塞避免：窗口的大小以一個線形速度增加；快速重傳：從一</p><p>　　2．Reno TCP</p><p>　　TCP Reno在快速重傳之后進入快速恢復(而不是TCP Tahoe采用的慢啟動)。VJ給出的原因是，接收方發(fā)送重復確認不僅僅意味著有報文

28、段丟失了，還意味著有(其它的)報文段離開了網絡，到達了接收方的緩沖區(qū)(self-clocking)，也就是說，網絡“管道”空出了新的位置，這樣TCP可以繼續(xù)發(fā)送新的報文段(當然cwnd應該減小一些)。另一個不進入慢啟動的原因是，dup ACKs的到達已經使得發(fā)送方的確認“時鐘”得到了同步?？焖僦貍骱涂焖倩謴屯ǔＲ黄饘崿F(xiàn)：1. 收到第3個重復確認之后，令ssthresh = max(FlightSize/2，2*SMSS)；2. 重傳丟失

29、的報文段，并令cwnd = ssthresh +3；3. 對每個dupACK，cwnd += SMSS，此時，窗口大小允許的話發(fā)送一個報文段；4. 當確認了新數(shù)據(jù)的ACK到達時，令cwnd=ssthresh，即進入擁塞避免狀態(tài)。</p><p>　　TCP Reno在一個窗口中的多個報文段同時丟失的情況下會出現(xiàn)性能問題，因為此時引起TCP退出快速恢復的“確認了新數(shù)據(jù)的ACK”沒有確認進入快速重傳之前丟失的所有報文

30、段。其它丟失的報文段會使得TCP不斷執(zhí)行快速重傳和快速恢復，而cwnd和ssthresh亦會多次被減半，大大降低了吞吐量。 Reno修改了Tahoe的快速重傳為快速恢復(指由三個重復的應答判斷有包丟失時，僅使窗口值減半)新的算法防止通信管道在快速重傳之后變?yōu)榭?，因而避免了慢啟動在單包丟失之重填?？焖僦貍髦饕獩Q定于收到的重復應答數(shù)目的初始門限值，一旦達到了門限值，發(fā)送方就重傳一個數(shù)據(jù)包，同時使擁塞窗口減半，與Tahoe的慢啟動不同，Ren

31、o的發(fā)送方用額外到達的應答來為后續(xù)包定時。發(fā)送方的可用窗口變?yōu)榘l(fā)送窗口與擁塞窗口的最小值，因而在快速恢復中，發(fā)送方根據(jù)收到的重復的應答來變動自己的窗口。相應地，每個重復應答表示有一些包已被移出網絡，并且現(xiàn)在已經到達接收方。在進入快速恢復階段并重發(fā)一個數(shù)據(jù)包后，對應每一個額外重復地應答傳出一個新包，當接受到新數(shù)據(jù)地應答時，發(fā)送方退出快速恢復階段并設置Ndup為0。</p><p>　　Reno的理想情況是在一個窗口

32、中單包丟失時，Reno 發(fā)送方在每一個往返時間中最多重傳一個包，但是它在同一個窗口中出現(xiàn)多包丟失時可能出現(xiàn)的問題。</p><p>　　3．New Reno TCP</p><p>　　TCP NewReno修改了TCP Reno的快速恢復算法，以處理一個窗口中的多個報文段同時丟失時出現(xiàn)的“部分確認”(partial ACKs，它在快速恢復階段到達并且確認了新數(shù)據(jù)，但它只確認了進入快速重傳

33、之前發(fā)送的一部分數(shù)據(jù))。在這種情況下，TCP Reno會退出快速恢復狀態(tài)，等待重傳定時器溢出或者dup ACKs的到達，但是TCP NewReno并不退出快速恢復狀態(tài)，而是 (1)重傳緊接著那個partial ACK之后的報文段，(2)cwnd-=partial ACK確認的新數(shù)據(jù)，cwnd+=SMSS，(3)對第一個(另一個建議是每一個)partial ACK，復位重傳定時器。</p><p>　　New Re

34、no 做了一個變化，即當多包丟棄時，去掉了Reno的等待重傳定時器，在快速恢復的階段，當發(fā)送端收到一個部分應答來表征一些包而不是所有包，在這個階段的起始時間沒有被成功傳送。在Reno中，部分包通過減少可用窗口至擁塞窗口大小以使TCP退出快速恢復。在New Reno 中，部分應答的包已經丟失，需要重傳。New Reno 的恢復不需要重傳超時，每個往返時間重傳一個包直到所有的數(shù)據(jù)包被傳完。New Reno 保持在快速恢復狀態(tài)，直到在快速恢復

35、階段初始化未被成功傳送的數(shù)據(jù)全被響應。</p><p>　　4．SACK TCP</p><p>　　前面這幾種算法，在單包丟棄時，效果是不錯的，但如果在同一個窗口下同一個數(shù)據(jù)窗口下，它們的性能都有比較大的局限性。后來出現(xiàn)了基于選擇應答(sack)的算法，它較好的解決了在同一個數(shù)據(jù)包丟失的問題，這種算法的基本原理是這樣的：SACK算法中，有一個稱作選擇域(option)的數(shù)據(jù)段：SACK的

36、選擇域的數(shù)據(jù)段，ACK中的SACK域包含一定數(shù)量的SACK塊，每一個SACK塊都記錄了信宿端接收或緩存的非連續(xù)分組。SACK塊的多少因應用和需要的不同而有所不同。與Reno相似，當發(fā)送端收到prexmtthresh個重復的ACK時，重發(fā)丟失的分組，并將擁塞窗口減半，進入快速恢復過程。期間，SACK維護了一個稱為“pipe”的變量用來估計出現(xiàn)在網絡中的分組數(shù)。當“pipe”小于擁塞窗口的大小時，發(fā)送端發(fā)送新的或需要重發(fā)的分組，并將變量“p

37、ipe”加一。當發(fā)送端接收了一個帶SACK選項的重復ACK，表明新分組已被接收端接收，pipe變量減一。Pipe變量的使用將何時發(fā)送與發(fā)送哪一個分組有效的解偶。當發(fā)送端被許可發(fā)送分組時，依次將發(fā)送丟失列表中記錄的分組。如果沒有這樣的分組，而接收端的通報窗口又足夠大，則發(fā)</p><p>　　當重傳分組本身被丟棄后，SACK用重傳超時來探測丟失，再次重傳后進入慢啟動過程，在確認了所有出現(xiàn)在進入快速恢復階段的分組后，