外文翻译--拥塞控制中的算法

1、.译文2 The Algorithm of Congestion Control1Tahoe TCP Modern TCP implementations contain a number of algorithms aimed at controlling network congestion while maintaining good user throughput. Early TCP implementations followed a go-back-n. model using cumulative positive acknowledgment and requiring a

2、retransmit timer expiration to re-send data lost during transport. These TCPs did little to minimize network congestion. The Tahoe TCP implementation added a number of new algorithms and refinements to earlier implementations. The new algorithms include Slow-Start, Congestion Avoidance, and Fast Ret

3、ransmit. The refinements include a modification to the round-trip time estimator used to set retransmission timeout values. All modifications have been described elsewhere.The Fast Retransmit algorithm is of special interest in this paper because it is modified subsequent versions of TCP. With Fast

4、Retransmit, after receiving a small number of duplicate acknowledgments for the same TCP segment (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 throug

5、hput.2Reno TCPThe Reno TCP implementation retained the enhancements incorporated into Tahoe, but modified the Fast Retransmit operation to include Fast Recovery. The new algorithm prevents the communication path (“pipe”) from going empty after Fast Retransmit, thereby avoiding the need to Slow-Start

6、 to refill it after a single packet loss. Fast Recovery operates by assuming each dup ACK received represents a single packet having left the pipe. Thus, during Fast Recovery the TCP sender is able to make intelligent estimates of the amount of outstanding data.In Reno, the sender's usable windo

7、w becomes other gateways that fail to monitor the average 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 received, according to the observ

8、ation 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 single packet, the sender effectively waits until half a window of dup ACKs have been received, and then sends a new packet for each ad

9、ditional dup ACK that is received. 3New-Reno TCP 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 time, we use New-Reno TCP to explore the fundamental limitations

10、 of TCP performance in the absence of SACK. The New-Reno TCP in this paper includes a small change to the Reno algorithm at the sender 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 Recove

11、ry when a partial ACK is received that acknowledges some 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 of the congestion window. In New-Reno, partial A

12、CKs do not take TCP out of Fast Recovery. Instead, partial ACKs received during Fast Recovery are treated as an indication that the packet immediately following the acknowledged packet in the sequence space has been lost, and should be retransmitted. Thus, when multiple packets are lost from a singl

13、e window of data, New-Reno can recover without a retransmission timeout, retransmitting one lost packet per round-trip time until all of the lost packets from that window have been retransmitted. New-Reno remains in Fast Recovery until all of the data outstanding when Fast Recovery was initiated has

14、 been acknowledged. 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 to a single incoming ACK, even if the sender's congestion

15、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 Fast Recovery, to more closely reproduce the behavior of Reno TCP during Fast Recovery. The “maxburst” parameter is really only needed for the

16、first window of packets that are sent after leaving Fast Recovery. If the sender had been prevented by the receiver's advertised window from sending packets during Fast Recovery, then, without “maxburst” , it is possible for the sender to send a large burst of packets upon exiting Fast Recovery.

17、 This applies to Reno and New-Reno TCP, and to a lesser extent, to SACK TCP. In Tahoe TCP the Slow-Start algorithm prevents bursts after recovering from a packet loss. The bursts of packets upon exiting Fast Recovery with New-Reno TCP are illustrated in Section 6 in the simulations with three and fo

18、ur packet drops. Bursts of packets upon exiting Fast Recovery with Reno TCP are illustrated in.4SACK TCP The SACK option follows the format in MMFR96. From MMFR96, the SACK option field contains a number of SACK blocks, where each SACK block reports a non-contiguous set of data that has been receive

19、d and queued. The first block in a SACK option is required to report the data receiver's most recently received segment, 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

20、the SACK option is used with the Timestamp option specified for TCP Extensions for High Performance, then the SACK option has room for only three SACK blocks MMFR96. If the SACK option were to be used with both the Timestamp option and with T/TCP (TCP Extensions for Transactions), the TCP option spa

21、ce would have room for only two SACK blocks.The 1990 “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, Jamshid Mahdavi, and Matt Mathis

22、. 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 increasing and decreasing the congestion window, The SACK TCP implementation in this paper, called “Sack1”in our simulator, is also

23、discussed in. and make minimal changes to the other congestion con-trol algorithms. Adding SACK to TCP does not change the basic underlying congestion control algorithms. The SACK TCP implementation preserves the properties of Tahoe and Reno TCP of being robust in the presence of out-of-order packet

24、s, and uses retransmit timeouts as the recovery method of last resort. The main difference between the SACK TCP implementation and the Reno TCP implementation is in the behavior when multiple packets are dropped from one window of data.拥塞控制中的算法1Tahoe TCP TCP Tahoe指的是1988年加入Van Jacobson提出的慢启动、拥塞避免和快速

25、重传算法之后的4.3BSD或类似的TCP实现版本。正如RFC793所要求的，Tahoe采用了递增式肯定重传策略和"go-back-n"模型(滑动窗口算法)。在慢启动阶段，拥塞窗口(cwnd)随着确认的到来以指数方式递增(这种以ACK来触发TRANSMIT的机制，被VJ称为"ACK clocking"，或"self-clocking")，直到到达阀值ssthresh(slow start threshold)；之后TCP进入拥塞避免阶段，cwnd每隔RTT以线性方式递增1个单位。如果连续收到3个重复确认，TCP不等重传定时器溢出，马上重

26、传丢失的报文段，这称为快速重传；之后TCP返回慢启动状态。早期的TCP实现算法是基于积极响应并通过重传来重发丢失的数据，当丢包时，TCP减小拥塞窗口，并重传被丢失的分组，然而在使用网络拥塞达到最小方面，这些算法的性能很差。TCP Tahoe 参考了早期的实现方法，并增加一些算法，包括慢启动：窗口大小以指数速度增加；拥塞避免：窗口的大小以一个线形速度增加；快速重传：从一个丢包的状态恢复而不需要等待重传定时器的超时。Tahoe 还包括对往返时间估计量的修改，这一参数的准确估计是非常重要的，因为它被用来设置重传超时定时器的基值，此外，Tahoe引入快速重传机制，即当接受者收到几个对同一TCP报文的相

27、同应答时，发送方就推断已经发生了丢包，而没有必要的等到重传定时器超时，并且重传相应的包，提高了信道的利用率。2Reno TCPTCP Reno在快速重传之后进入快速恢复(而不是TCP Tahoe采用的慢启动)。VJ给出的原因是，接收方发送重复确认不仅仅意味着有报文段丢失了，还意味着有(其它的)报文段离开了网络，到达了接收方的缓冲区(self-clocking)，也就是说，网络“管道”空出了新的位置，这样TCP可以继续发送新的报文段(当然cwnd应该减小一些)。另一个不进入慢启动的原因是，dup ACKs的到达已经使得发送方的确认“时钟”得到了同步。快速重传和快速恢复通常一起实现：1. 收到第3

28、个重复确认之后，令ssthresh = max(FlightSize/2，2*SMSS)；2. 重传丢失的报文段，并令cwnd = ssthresh +3；3. 对每个dupACK，cwnd += SMSS，此时，窗口大小允许的话发送一个报文段；4. 当确认了新数据的ACK到达时，令cwnd=ssthresh，即进入拥塞避免状态。TCP Reno在一个窗口中的多个报文段同时丢失的情况下会出现性能问题，因为此时引起TCP退出快速恢复的“确认了新数据的ACK”没有确认进入快速重传之前丢失的所有报文段。其它丢失的报文段会使得TCP不断执行快速重传和快速恢复，而cwnd和ssthresh亦会多次被减半

29、，大大降低了吞吐量。 Reno修改了Tahoe的快速重传为快速恢复(指由三个重复的应答判断有包丢失时，仅使窗口值减半)新的算法防止通信管道在快速重传之后变为空，因而避免了慢启动在单包丢失之重填。快速重传主要决定于收到的重复应答数目的初始门限值，一旦达到了门限值，发送方就重传一个数据包，同时使拥塞窗口减半，与Tahoe的慢启动不同，Reno的发送方用额外到达的应答来为后续包定时。发送方的可用窗口变为发送窗口与拥塞窗口的最小值，因而在快速恢复中，发送方根据收到的重复的应答来变动自己的窗口。相应地，每个重复应答表示有一些包已被移出网络，并且现在已经到达接收方。在进入快速恢复阶段并重发一个数据包后，对

30、应每一个额外重复地应答传出一个新包，当接受到新数据地应答时，发送方退出快速恢复阶段并设置Ndup为0。 Reno的理想情况是在一个窗口中单包丢失时，Reno 发送方在每一个往返时间中最多重传一个包，但是它在同一个窗口中出现多包丢失时可能出现的问题。3New Reno TCPTCP NewReno修改了TCP Reno的快速恢复算法，以处理一个窗口中的多个报文段同时丢失时出现的“部分确认”(partial ACKs，它在快速恢复阶段到达并且确认了新数据，但它只确认了进入快速重传之前发送的一部分数据)。在这种情况下，TCP Reno会退出快速恢复状态，等待重传定时器溢出或者dup ACKs的到达，但是TCP NewReno并不退出快速恢复