TCP Rate-Halving
Abstract: As specified by RFC2581, Fast Recovery adjusts the congestion window (cwnd) by transmitting new data only during the second half of the recovery interval. The Rate-Halving algorithm adjusts the congestion window by spacing transmissions at the rate of one data segment per two segments acknowledged over the entire recovery period, thereby sustaining the self-clocking of TCP and avoiding a burst. Since it is largely independent of the details of the data retransmission strategy, the Rate-Halving algorithm can be used with several standard and experimental TCP implementations: NewReno, SACK, and ECN.
Introduction
All “Reno TCP” implementations include TCP Fast Retransmit and Fast Recovery algorithms [RFC2581]. Fast retransmit relies on three duplicate acknowledgements to trigger the retransmission of a single lost segment. Once the Fast Retransmit has occurred, TCP then waits for enough additional duplicate ACKs to arrive, indicating that half of the data in flight has left the network. Only when this has occurred will TCP send additional new data.
The consequence of this delay is that the entire new window of data is transmitted in one half of one Round Trip Time (RTT). This burst can cause repeated bursts in successive RTTs following the recovery, which can result in overall additional burstiness on the network.
Hoe [Hoe95] suggested that during Fast Recovery the TCP data sender space out retransmissions and new data on alternate acknowledgements across the entire recovery RTT. (Note that this eliminates the half RTT lull in sending which occurs in Reno TCP.)
The Rate-Halving algorithm implements Hoe’s idea. The algorithm may be implemented in NewReno, SACK, and ECN-style TCP implementations. Rate-Halving has a number of other useful properties as well. It results in a slightly lower final value for cwnd following recovery, which has been suggested by Floyd and others as the more correct value. The Rate-Halving algorithm provides proper adjustments to the congestion window in response to congestion signals such as a lost segment or an ECN-Echo bit [RFC2481]. These adjustments are largely independent of the strategy used to retransmit missing segments, allowing Rate-Halving to be extended for use in other TCP implementations or even non-TCP transport protocols.
Additional Information
- Draft specification of the algorithm.
- ns2 simulator module for Rate-Halving TCP.
- A brief description of the virtues of rate-halving tht includes data on Reno/NewReno with ECN vs. Rate-Halving with ECN and on SACK vs. Rate-Halving.
- An implementation for NetBSD 1.3.2
- Some preliminary simulator results are also available.
- The current algorithm for Rate Halving has evolved from an earlier version described in http://www.psc.edu/networking/papers/FACKnotes/current/. Bollinger, Hengartner, and Gross have published a technical report that evaluates the effectiveness of the earlier version of Rate Halving. Their report is called ‘The Effectiveness of End- to-End Congestion Control Mechanisms’, ETH Technical Report #313, 1999, Department Informatik ETH Zurich.
References
- [Hoe95] J. Hoe, Startup Dynamics of TCP’s Congestion Control and Avoidance Schemes. Master’s Thesis, MIT, 1995. URL “http://ana-www.lcs.mit.edu/anaweb/ps-papers/hoe-thesis.ps”
- [RFC2481] K. Ramakrishnan, and S. Floyd, “A Proposal to add Explicit Congestion Notification (ECN) to IP,” RFC2481, January 1999.
- [RFC2581] M. Allman, V. Paxson, and W. Stevens, “TCP Congestion Control,” RFC2581, April 1999.
Comments on the draft or algorithm are welcome! Please mail them to: M. Mathis, J. Mahdavi, J. Semke.