Additive increase/multiplicative decrease

The additive increase/multiplicative-decrease (AIMD) algorithm is a feedback control algorithm used in TCP Congestion Avoidance. Basically, AIMD represents a linear growth of the congestion window, combined to an exponential reduction when a congestion takes place.

The approach taken is to increase the transmission rate (window size), probing for usable bandwidth, until loss occurs. The policy of additive increase basically says to increase the congestion window by 1 MSS (Maximum segment size) every RTT until a loss is detected.

When loss is detected, the policy is changed to be one of multiplicative decrease which is to cut the congestion window in half after loss.

The result is a saw tooth behavior that represents the probe for bandwidth.

A loss event is generally described to be either a timeout or the event of receiving 3 duplicate ACKs. Also related to TCP congestion control is the slow start mechanism.

Other policies or algorithms for fairness in congestion control are AIAD, MIAD and MIMD.

Mathematical Formula

w ← w - aw when loss is detected

w ← w + b/w when an ACK arrives

Idea behind the formula

In a series of schemes, different proposals has been made in order to prevent congestion based on different numbers for a and b. For instance, considering the SCTP protocol, researchers suggested to make a = 0.125 while b = .01. Other times, researchers wants a and b to be functions of w which would result in creating a(w) and b(w).

Up until Vegas and FAST came about, the use of increasing the Round Trip Time (RTT) is used as a measure of congestion rather than looking at packet losses. This would define the congestion window size to be a function of the measured RTT. Typically, these modifications can only lead to improvements in special cases like networks with high bandwidth and low loss rates.