Congestion Control Algorithms in Linux

Algorithms with a Linux implementation in a pluggable congestion control module are indicated with the module name in brackets. Others do not currently have a Linux implementation.

Africa [africa]
A new delay sensitive congestion avoidance mode that allows for scalable, aggressive behavior in large underutilized links, yet falls back to the more conservative TCP Reno algorithm once links become well utilized and congestion is imminent.
TCP BIC [bic]
BIC is the abbreviation for Binary Increase Congestion control. BIC uses a unique window growth function. In case of packet loss, the window is reduced by a multiplicative factor. The window size just before and after the reduction is then used as parameters for a binary search for the new window size. BIC was used as standard algorithm in the Linux kernel.

This is from the implementation of BICTCP in Lison-Xu, Kahaled Harfoush, and Injong Rhee. Binary Increase Congestion Control for Fast, Long Distance Networks in InfoComm 2004.

Unless BIC is enabled and congestion window is large this behaves the same as the original Reno.

Compound TCP [compound]
Compound TCP (CTCP) is a Microsoft algorithm that is part of the Windows Vista and Window Server 2008 TCP stack. It is designed to aggressively adjust the sender’s congestion window to optimise TCP for connections with large bandwidth-delay products while trying not to harm fairness (as can occur with HSTCP).

The latest Linux implementation requires “research” justification to obtain. Our version is based on an older version implemented for the Linux 2.6.17 kernel which I have updated for the 2.6.27 kernel.

TCP CUBIC [cubic]
CUBIC is a less aggressive variant of BIC (meaning, it doesn’t steal as much throughput from competing TCP flows as does BIC).

This is from the implementation of CUBIC TCP in Injong Rhee, Lisong Xu. CUBIC: A New TCP-Friendly High-Speed TCP Variant in PFLDnet 2005.

Unless CUBIC is enabled and congestion window is large this behaves the same as the original Reno.

FAST TCP
The Implementation used by FastSoft. A Linux version is unavailable to us.
High Speed TCP [highspeed]
Sally Floyd’s High Speed TCP, described in RFC 3649. The main use is for connections with large bandwidth and large RTT (such as Gbit/s and 100 ms RTT).
High Speed TCP Low Priority (HSTCP-LP)
HSTCP-LP (High-Speed TCP Low Priority) is an advanced TCP version targeted towards fast long-distance networks (i.e., networks operating at 622 Mb/s, 2.5 Gb/s, or 10 Gb/s and spanning several countries or states). HSTCP-LP is a TCP-LP version with aggressive window increase policy.
H-TCP [htcp]
H-TCP was proposed by the Hamilton Institute for transmissions that recover more quickly after a congestion event. It is also designed for links with high bandwidth and RTT.
TCP Hybla [hybla]
TCP Hybla was proposed in order to transmit data efficiently over satellite links and “defend” the transmission against TCP flows from other origins.
TCP Illinois [illinois]
The algorithm is described in TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm for High-Speed Networks
TCP Low Priority [lp]
This is an approach to develop an algorithm that uses excess bandwidth for TCP flows. It can be used for low priority data transfers without “disturbing” other TCP transmissions (which probably don’t use TCP Low Priority).

The Linux implementation.

TCP Tahoe/Reno/New Reno [reno]
These are the classical models used for congestion control. They exhibit the typical slow start of transmissions. The throughput increases gradually until it stays stable. It is decreased as soon as the transfer encounters congestion, then the rate rises again slowly. The window is increased by adding fixed values. TCP Reno uses a multiplicative decrease algorithm for the reduction of window size. TCP Reno is the most widely deployed algorithm.

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.

Scalable TCP [scalable]
This is another algorithm for WAN links with high bandwidth and RTT. One of its design goals is a quick recovery of the window size after a congestion event. It achieves this goal by resetting the window to a higher value than standard TCP.
TCP Vegas [vegas]
TCP Vegas introduces the measurement of RTT for evaluating the link quality. It uses additive increases and additive decreases for the congestion window.

PDFs of the papers:
TCP Vegas: End to End Congestion Avoidance on a Global Internet
TCP Vegas: New Techniques for Congestion Detection and Avoidance

The Linux implementation differs:

  • We do not change the loss detection or recovery mechanisms of Linux in any way. Linux already recovers from losses quite well, using fine-grained timers, NewReno, and FACK.
  • To avoid the performance penalty imposed by increasing cwnd only every-other RTT during slow start, we increase during every RTT during slow start, just like Reno.
  • Largely to allow continuous cwnd growth during slow start, we use the rate at which ACKs come back as the “actual” rate, rather than the rate at which data is sent.
  • To speed convergence to the right rate, we set the cwnd to achieve the right (“actual”) rate when we exit slow start.
  • To filter out the noise caused by delayed ACKs, we use the minimum RTT sample observed during the last RTT to calculate the actual rate.
  • When the sender re-starts from idle, it waits until it has received ACKs for an entire flight of new data before making a cwnd adjustment decision. The original Vegas implementation assumed senders never went idle.
TCP Veno [veno]
This variant is optimised for wireless networks, since it was designed to handle random packet loss better. It tries to keep track of the transfer, and guesses if the quality decreases due to congestion or random packet errors.
TCP Westwood+ [westwood]
Westwood+ addresses both large bandwidth/RTT values and random packet loss together with dynamically changing network loads. It analyses the state of the transfer by looking at the acknowledgement packets. Westwood+ is a modification of the TCP Reno algorithm.
XCP
XCP is novel in separating the efficiency and fairness policies of congestion control, enabling routers to quickly make use of available bandwidth while conservatively managing the allocation of bandwidth to flows. XCP is built upon a new principle: carrying per-flow congestion state in packets. XCP packets carry a congestion header through which the sender requests a desired throughput. Routers make a fair per-flow bandwidth allocation without maintaining any per-flow state. Thus, the sender learns of the bottleneck router’s allocation in a single round trip.

This algorithm is currently experimental and not yet fully implemented or tested.

YeAH [yeah]
YeAH TCP is a delay-aware state-enabled congestion control algorithm. Through delay measures, when the network is sensed unloaded it will quickly exploit the available capacity, trying to keep the network buffer utilization always lower than a threshold. Moreover it is designed to be internal and RTT fair, Reno-friendly and resilient on lossy links.