TCP congestion avoidance algorithm

The TCP uses a network congestion avoidance algorithm that includes various aspects of an additive-increase-multiplicative-decrease (AIMD) scheme, with other schemes such as slow-start in order to achieve congestion avoidance.

TCP Tahoe and Reno

Two such variations are those offered by TCP Tahoe and Reno. TCP specifies a maximum segment size (MSS).

To avoid congestion collapse, TCP uses a multi-faceted congestion control strategy. For each connection, TCP maintains a "congestion window", limiting the total number of unacknowledged packets that may be in transit end-to-end. This is somewhat analogous to TCP's sliding window used for flow control. TCP uses a mechanism ironically called "slow start" [cite journal |last=Jacobson |first=Van |year=1995 |title=Congestion Avoidance and Control |journal=ACM SIGCOMM Computer Communication Review |volume=25 |issue=1 |pages=157 - 187 |url=http://ee.lbl.gov/papers/congavoid.pdf] to increase the congestion window after a connection is initialised and after a timeout. It starts with a window of 2 MSS. Although the initial rate is low, the rate of increase is very rapid: for every packet ACKed, the congestion window increases by 1 MSS so that for every round trip time (RTT), the congestion window has doubled. When the congestion window exceeds a threshold "ssthresh" the algorithm enters a new state, called congestion avoidance. In some implementations (e.g. Linux), the initial ssthresh is large, and so the first slow start usually ends after a loss. However, ssthresh is updated at the end of each slow start, and will often affect subsequent slow starts triggered by timeouts.

Congestion Avoidance. As long as non-duplicate ACKs are received, the congestion window is additively increased by one MSS every round trip time. When a packet is lost, duplicate ACKs will be received. The behaviour of Tahoe and Reno differ in how they detect and react to packet loss:

* Tahoe: Loss is detected when a timeout expires before an ACK is received. Tahoe will then reduce congestion window to 1 MSS, and reset to slow-start state.
* Reno: If three duplicate ACKs are received (i.e., three ACKs acknowledging the same packet, which are not piggybacked on data, and do not change the receiver's advertised window), Reno will halve the congestion window, perform a "fast retransmit", and enter a phase called Fast Recovery. If an ACK times out, slow start is used as it is with Tahoe.

Fast Recovery. (Reno Only) In this state, TCP retransmits the missing packet that was signaled by 3 duplicate ACKs, and waits for an acknowledgment of the entire transmit window before returning to congestion avoidance. If there is no acknowledgment, TCP Reno experiences a timeout and enters the slow-start state.

Both algorithms reduce congestion window to 1 MSS on a timeout event.

TCP Vegas

Until the mid 1990s, all TCPs set timeouts and measured round-trip delays were based upon only the last transmitted packet in the transmit buffer. With TCP Vegas, timeouts were set and round-trip delays were measured for every packet in the transmit buffer. In addition, TCP Vegas uses additive increases and additive decreases in the congestion window.

TCP New Reno

[http://www.faqs.org/rfcs/rfc3782.html TCP New Reno] improves retransmission during the fast recovery phase of TCP Reno. During fast recovery, for every duplicate ACK that is returned to TCP New Reno, a new unsent packet from the end of the congestion window is sent, to keep the transmit window full. For every ACK that makes partial progress in the sequence space, the sender assumes that the ACK points to a new hole, and the next packet beyond the ACKed sequence number is sent.

Because the timeout timer is reset whenever there is progress in the transmit buffer, this allows New Reno to fill large holes, or multiple holes, in the sequence space - much like TCP SACK. Because New Reno can send new packets at the end of the congestion window during fast recovery, high throughput is maintained during the hole-filling process, even when there are multiple holes, of multiple packets each. When TCP enters fast recovery it records the highest outstanding unacknowledged packet sequence number. When this sequence number is acknowledged, TCP returns to the congestion avoidance state.

A problem occurs with New Reno when there are no packet losses but instead, packets are reordered by more than 3 packet sequence numbers. When this happens, New Reno mistakenly enters fast recovery, but when the reordered packet is delivered, ACK sequence-number progress occurs and from there until the end of fast recovery, every bit of sequence-number progress produces a duplicate and needless retransmission that is immediately ACKed.

New Reno performs as well as SACK at low packet error rates, and substantially outperforms Reno at high error rates.

TCP Hybla

[http://hybla.deis.unibo.it/ TCP Hybla] aims to eliminate penalization of TCP connections that incorporate a high-latency terrestrial or satellite radio link, due to their longer round trip times. It stems from an analytical evaluation of the congestion window dynamics, which suggests the necessary modifications to remove the performance dependence on RTT.

TCP BIC

Binary Increase Congestion control is an implementation of
TCP with an optimized congestion control algorithm for high speed networks with high latency (LFN: Long Fat Networks). BIC is used by default in Linux kernels 2.6.8 through 2.6.18.

TCP CUBIC

CUBIC is a less aggressive and more systematic derivative of BIC, in which the window is a cubic function of time since the last congestion event, with the inflection point set to the window prior to the event. CUBIC is used by default in Linux kernels since version 2.6.19.

References

Other TCP congestion avoidance algorithms

* Compound TCP
* Fast TCP
* H-TCP
* High Speed TCP
* [http://www.ece.rice.edu/networks/TCP-LP/ HSTCP-LP]
* TCP-Illinois
* [http://www.ece.rice.edu/networks/TCP-LP/ TCP-LP]
* TCP SACK
* [http://www.deneholme.net/tom/scalable/ Scalable TCP]
* [http://www.ntu.edu.sg/home/ascpfu/veno/ TCP Veno]
* Westwood
* Westwood+
* [http://www.isi.edu/isi-xcp/ XCP]
* [http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf YeAH-TCP]

TCP New Reno is the most commonly implemented algorithm, SACK support is very common and is an extension to Reno/New Reno. Most others are competing proposals which still need evaluation. Starting with 2.6.8 the Linux kernel switched the default implementation from reno to BIC. The default implementation was again changed to CUBIC in the 2.6.19 version.

When the per-flow product of bandwidth and latency increases, regardless of the queuing scheme, TCP becomes inefficient and prone to instability. This becomes increasingly important as the Internet evolves to incorporate very high-bandwidth optical links.

[http://www.medianet.kent.edu/itcp/main.html TCP Interactive (iTCP)] allows applications to subscribe to TCP events and respond accordingly enabling various functional extensions to TCP from outside TCP layer. Most TCP congestion schemes work internally. iTCP additionally enables advanced applications to directly participate in congestion control such as to control the source generation rate.

ee also

* Transmission Control Protocol#Development of TCP

* TCP CANIT