Additive increase/multiplicative decrease

The additive-increase/multiplicative-decrease (AIMD) algorithm is a feedback control algorithm best known for its use in TCP Congestion Avoidance. AIMD combines linear growth of the congestion window with an exponential reduction when a congestion takes place. Multiple flows using AIMD congestion control will eventually converge to use equal amounts of a contended link.[1] The related schemes of multiplicative-increase/multiplicative-decrease (MIMD) and additive-increase/additive-decrease (AIAD) do not converge.

Algorithm

The approach taken is to increase the transmission rate (window size), probing for usable bandwidth, until loss occurs. The policy of additive increase may, for instance, increase the congestion window by a fixed amount every round trip time. When congestion is detected, the transmitter decreases the transmission rate by a multiplicative factor; for example, cut the congestion window in half after loss. The result is a saw-tooth behavior that represents the probe for bandwidth.

AIMD requires a binary signal of congestion. Most frequently, packet loss serves as the signal; the multiplicative decrease is triggered when a timeout or acknowledgement message indicates a packet was lost. It is also possible for in-network mechanisms to mark congestion (without discarding packets) as in Explicit Congestion Notification (ECN).

Mathematical Formula

Let w(t) be the sending rate (e.g. the congestion window) during time slot t, a (a > 0) be the additive increase parameter, and b (0 < b < 1) be the multiplicative decrease factor.

w(t + 1) = \begin{cases} w(t) + a & \text{ if congestion is not detected} \\ w(t) \times b & \text{ if congestion is detected} \end{cases}

In TCP, after slow start, the additive increase parameter a is typically one MSS (maximum segment size) per round-trip time, and the multiplicative decrease factor b is typically 1/2.

Protocols

AIMD congestion avoidance is or was used in:

See also

References

  1. 1 2 3 Chiu, Dah-Ming; Raj Jain (1989). "Analysis of increase and decrease algorithms for congestion avoidance in computer networks". Computer Networks and ISDN systems 17: 1–14.
  2. ↑ Floyd. "4341: RFC Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control".
This article is issued from Wikipedia - version of the Sunday, March 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.