Taxonomy of congestion control

Taxonomy of congestion control refers to grouping congestion control algorithms according to their characteristics.

Example classification

The following is one possible classification according to the following properties:
#The type and amount of feedback received from the network: Loss (L); delay (D); single-bit (S) or multi-bit (M) explicit signals
#Incremental deployability on the current Internet: Sender needs modification (S); receiver needs modification (R); routers/gateways need modification (G)
#The aspect of performance it aims to improve: high bandwidth-delay product networks (B); lossy links (L); fairness (F); advantage to short flows (S); variable-rate links (V); convergence speed (C)
#The fairness criterion it uses: max-min (M), proportional (P), "minimum potential delay" (D), Other (O)

Some well-known congestion avoidance mechanisms are classified by this scheme as follows:

Classification by network awareness

Congestion control algorithms can be [http://utopia.duth.gr/~emamatas/jie2007.pdf categorized using network awareness as a criterion] . The first category (”the box is black”) consists of a group of algorithms that consider the network as a black box, assuming no knowledge of its state, other than the binary feedback upon congestion. The second category (”the box is grey”) groups approaches that use measurements to estimate available bandwidth, level of contention or even the temporary characteristics of congestion. Due to the possibility of wrong estimations and measurements, the network is considered a grey box. The third category (”the box is green”) contains the bimodal congestion control, which calculates explicitly the fairshare, as well as the network-assisted control, where the network communicates its state to the transport layer; the box now is becoming green.

The Box is Black: Blind Congestion Control

The Additive Increase Multiplicative Decrease (AIMD) algorithm is used to implement TCP window adjustments; based on the analysis of Chiu and Jain the algorithm achieves stability and converges to fairness in situations where the demand (of competing flows) exceeds the channel’s bandwidth. The congestion control in the traditional TCP, is based on the basic idea of AIMD. In TCP-Tahoe, TCP-NewReno and TCP-Sack, the additive increase phase is adopted exactly as in AIMD, when the protocols are in the Congestion Avoidance phase. In case of a packet drop, instead of the multiplicative decrease a more conservative tactic is used in TCP-Tahoe. The congestion window resets and the protocol enters again the slow-start phase. On the other hand, in TCP-NewReno and TCP-Sack, when the sender receives 3 DACKs, a multiplicative decrease is used in both window and slow-start threshold. In such case, the protocols remain at the Congestion Avoidance phase. When the retransmission timeout expires,they enter the slow-start phase as in TCP-Tahoe.

*Highspeed-TCP -- Highspeed-TCP modifies the TCP response function in environments with large Delay-Bandwidth product and increase the congestion window more aggressively upon receiving an ACK and decreases the window more gently upon a loss event.
*BIC-TCP -- Binary Increase Congestion Control Protocol (BIC-TCP) uses a concave increase of the sources rate after each congestion event until the window is equal to that before the event, in order to maximise the time that the network is fully utilised. After that, it probes aggressively.
*CUBIC TCP -- 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.
*AIMD-FC -- A recent improvement of AIMD, Additive Increase Multiplicative Decrease with Fast Convergence (AIMD-FC) is not based on a new algorithm, but rather on an optimization of AIMD during the convergence procedure that enables the algorithm to converge faster and achieve higher efficiency.
*Binomial Mechanisms -- Binomial Mechanisms form a new class of nonlinear congestion control algorithms named Binomial Congestion Control Algorithms. These algorithms are called binomial because their control is based on the involvement of two additional algebraic terms with different exponents.
*SIMD Protocol -- SIMD is a TCP-friendly nonlinear congestion control algorithm that utilizes history information.
*GAIMD -- General AIMD Congestion Control (GAIMD) generalizes AIMD congestion control by parameterizing the additive increase value α and multiplicative decrease ratio β.

The Box is Grey: Measurement-based Congestion Control

Standard TCP relies on packet losses as an implicit congestion signal from overloaded links. However, packet loss is not a sufficient indication of congestion, in its own right, for a number of reasons:1) Packet loss can be caused by random bit corruption when bandwidth is still available.2) Acknowledgement-based loss detection at the sender side can be affected by the cross-traffic on the reverse path.3) Packet loss, as a binary feedback, cannot indicate the level of contention before the occurrence of congestion. Therefore, an efficient window adjustment tactic should reflect various network conditions, which cannot all be captured simply by packet drops. Several measurement-based transport protocols gather information on current network conditions.

*TCP Vegas -- Vegas estimates the queueing delay, and linearly increases or decreases the window so that a constant number of packets per flow are queued in the network. Vegas implements proportional fairness.
*FAST TCP -- FAST achieves the same equilibrium as Vegas, but uses proportional control instead of linear increase, and intentionally scales the gain down as the bandwidth increases with the aim of ensuring stability.
*TCP-Westwood -- In TCP-Westwood (TCPW), a loss causes the window to be reset to the sender's estimate of the bandwidth-delay product, which is the smallest measured RTT times the observed rate of receiving ACKs.
* TFRC -- TFRC is a TCP-Friendly, rate-based congestion control protocol, which intends to compete fairly for bandwidth with TCP flows.
*TCP-Real -- TCP-Real employs a receiver-oriented and measurement-based congestion control mechanism that improves TCP performance over heterogeneous (wired/wireless) networks and over asymmetric paths.
*TCP-Jersey -- TCP-Jersey is a new TCP scheme that focuses on the capability of the transport mechanism to distinguish the wireless from congestion packet losses.

The Box is Green

*Bimodal Mechanism -- Bimodal Congestion Avoidance and Control mechanism measures the fair-share of the total bandwidth that should be allocated for each flow, at any point, during the system’s execution.
*Signalling methods implemented by routers
**Random Early Detection -- Random Early Detection (RED) randomly drops packets in proportion to the router's queue size, triggering multiplicative decrease in some flows.
**Explicit Congestion Notification -- Explicit Congestion Notification (ECN) enables routers to probabilistically mark a bit in the IP header, rather than drop the packet, to inform end-hosts of pending congestion when the length of the queue exceeds a threshold.

*Network-Assisted Congestion Control
**VCP -- The variable-structure congestion control protocol (VCP) uses 2 ECN bits to explicitly feedback the network state of congestion. It includes an end host side algorithm as well.The following algorithms require custom fields to be added to the TCP packet structure.
** eXplicit Control Protocol (XCP) -- XCP routers signal explicit increase and decreases in the senders' congestion windows.
**MaxNet -- MaxNet uses a single header field, which carries the maximium congetsion level of any router on a flow's path. The rate is set as a function of this maximum congestion, resulting in max-min fairness.
**JetMax -- JetMax, like MaxNet, also responds only to the maximum congestion signal, but also carries other overhead fields

External links

* [http://utopia.duth.gr/~emamatas/jie2007.pdf Approaches to Congestion Control in Packet Networks]
* [http://www.ecse.rpi.edu/Homepages/shivkuma/research/cong-papers.html Papers in Congestion Control]
* [http://www.cs.arizona.edu/projects/protocols/ TCP Vegas Homepage]
* [http://www.icir.org/floyd/red.html Random Early Detection Homepage]
* [http://www.icir.org/floyd/ecn.html Explicit Congestion Notification Homepage]
* [http://www.ccs.neu.edu/home/ladrian/abstract/aimdfc.html AIMD-FC Homepage]
* [http://www.cs.ucla.edu/NRL/hpi/tcpw/ TCP-Westwood Homepage]
* [http://www.icir.org/floyd/hstcp.html Highspeed-TCP Homepage]
* [http://www.csc.ncsu.edu/faculty/rhee/export/bitcp/ BIC-TCP]
* [http://www.icir.org/tfrc/ TFRC Homepage]
* [http://netlab.caltech.edu/maxnet/ MaxNet Homepage]