Journal of Internet Engineering, Vol 1, No 2 (2007)

Font Size:  Small  Medium  Large

A Theory of Load Adjustments and its Implications for Congestion Control

Sergey Gorinsky, Manfred Georg, Maxim Podlesny, Christoph Jechlitschek


Multiplicative Increase (MI), Additive Increase (AI), and Multiplicative
Decrease (MD) are linear adjustments used extensively in networking.
However, their properties are not fully understood. We analyze responsiveness
(time for the total load to reach the target load), smoothness
(maximal size of the total load oscillations after reaching the target load), fairing
speed (speed of convergence to equal individual loads) and scalabilities of MAIMD
algorithms, which generalize AIMD algorithms via optional inclusion of MI. We
prove that an MAIMD can provide faster asymptotic fairing than a less smooth
AIMD. Furthermore, we discover that loads under a specific MAIMD converge
from any initial state to the same periodic pattern, called a canonical cycle. While
imperfectly correlated with smoothness, the canonical cycle reliably predicts the
asymptotic fairing speed. We also show that AIMD algorithms offer the best
trade-off between smoothness and responsiveness. Then, we introduce
smoothness-responsiveness diagrams to investigate MAIMD scalabilities. Finally,
we discuss implications of the theory for the practice of congestion control.

Full Text: PDF

Last Update: 23 May 2013

Copyright @ 2006-10 Klidarithmos Press. All rights reserved