外文翻譯--擁塞控制中的算法

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提出的慢啟動(dòng)、擁塞避免和快速重傳算法之后的4.3BSD或類似的TCP實(shí)現(xiàn)版本。正如RFC793所要求的，Tahoe采用了遞增式肯定重傳策略和"go-back-n"模型(滑動(dòng)窗口算法)。在慢啟動(dòng)階段，擁塞窗口(cwnd)隨著確認(rèn)的到來以指數(shù)方式遞增(這種以ACK來觸發(fā)TRANSMIT的機(jī)制，被VJ稱為"ACK clocking"

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

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

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

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

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

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

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

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

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

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

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

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