Additive increase/multiplicative decrease

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

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:

Transmission Control Protocol (TCP)
Scalable Transmission Control Protocol (STCP)
OSI Transport Class 4[1]
DCCP (in some modes)[2]
DECnet[1]

gollark: Why is there a mongodb log on there?

gollark: You could look at the end.

gollark: No, you just use `sudo -i` (open root shell) then run whatever commands.

gollark: Wait, no.

gollark: `journalctl -u unifi`

References

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.
Floyd. "4341: RFC Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control".

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[chui1989-1] 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".