Jump to content

Additive increase/multiplicative decrease

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 203.78.217.151 (talk) at 19:56, 22 April 2010. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The additive increase/multiplicative-decrease (AIMD) algorithm is a feedback control algorithm used in TCP Congestion Avoidance. AIMD combines linear growth of the congestion window with 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 may, for instance, increase the congestion window by 1 MSS (Maximum segment size) every RTT (Round Trip Time) until a loss is detected.

When loss is detected, the policy is changed to be one of multiplicative decrease, which may, for instance, 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 additive increase/decrease (AIAD), multiplicative increase/additive decrease (MIAD) and multiplicative increase/decrease (MIMD).

Mathematical Formula

Let w be the congestion window; for byte-oriented protocols (such as TCP) the window is relative to the sender's maximum segment size (MSS). Let a < 1 and b ≤ 1.

w ← a*w          decrease when loss is detected

w ← w + b       increase when the window has been fully ACK'ed, or

w ← w + w/b    increase by a fraction of MSS when an ACK arrives

Idea behind the formula

In a series of schemes, different proposals have been made in order to prevent congestion based on different definitions for a and b, aiming for a balance between responsiveness to congestion and utilisation of available capacity. For instance, considering the SCTP protocol, researchers suggested to make a = 0.125 while b = 0.01[citation needed]. Other times, researchers want a and b to be functions of w, that is, a(w) and b(w).

See also

Further reading

  • RFC 2581
  • Comer, Douglas E. (2006). Internetworking with TCP/IP (5E ed.). Prentice Hall: Upper Saddle River, NJ.
Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Additive_increase/multiplicative_decrease&oldid=357684220"