AIMD
Encyclopedia
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. The related schemes of multiplicative-increase/multiplicative-decrease (MIMD) and additive-increase/additive-decrease (AIAD) do not converge.
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).
) during time slot t, a (
) be the additive increase factor, and b (
) be the multiplicative decrease factor.
In TCP, after slow start, the additive increase factor a is typically one MSS (maximum segment size
) per round-trip time, and the multiplicative decrease factor b is typically 1/2.
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
Congestion Avoidance
TCP congestion avoidance algorithm
Transmission Control Protocol uses a network congestion avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease scheme, with other schemes such as slow-start in order to achieve 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. 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
Explicit Congestion Notification
Explicit Congestion Notification is an extension to the Internet Protocol and to the Transmission Control Protocol and is defined in RFC 3168 . ECN allows end-to-end notification of network congestion without dropping packets. ECN is an optional feature that is only used when both endpoints...
(ECN).
Mathematical Formula
Let w(t) be the sending rate (e.g. the congestion windowCongestion window
In Transmission Control Protocol , the congestion window is one of the factors that determines the number of bytes that can be outstanding at any time. This is not to be confused with the TCP window size which is maintained by the receiver. This is a means of stopping the link between two places...
) during time slot t, a (
) be the additive increase factor, and b () be the multiplicative decrease factor.In TCP, after slow start, the additive increase factor a is typically one MSS (maximum segment size
Maximum segment size
The maximum segment size is a parameter of the TCP protocol that specifies the largest amount of data, specified in octets, that a computer or communications device can receive in a single TCP segment, and therefore in a single IP datagram. It does not count the TCP header or the IP header...
) 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 ProtocolTransmission Control ProtocolThe Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
(TCP) - Stream Control Transmission ProtocolStream Control Transmission ProtocolIn computer networking, the Stream Control Transmission Protocol is a Transport Layer protocol, serving in a similar role to the popular protocols Transmission Control Protocol and User Datagram Protocol...
(SCTP) - OSI Transport Class 4
- DCCP (in some modes)
- DECnetDECnetDECnet is a suite of network protocols created by Digital Equipment Corporation, originally released in 1975 in order to connect two PDP-11 minicomputers. It evolved into one of the first peer-to-peer network architectures, thus transforming DEC into a networking powerhouse in the 1980s...