ALCOMFT-TR-01-179

Vincent Dumas, Fabrice Guillemin and Philippe Robert
A Markovian analysis of AIMD algorithms
INRIA. Work packages 2 and 4. October 2001.

Abstract: The Additive-Increase Multiplicative-Decrease (AIMD) schemes designed to control congestion in communication networks are investigated from a probabilistic point of view. Functional limit theorems for a general class of Markov processes that describe these algorithms are obtained. The asymptotic behavior of the corresponding invariant measures is described in terms of the limiting Markov processes. For some special important cases, including TCP congestion avoidance, an important ARMA property is proved. As a consequence, the explicit expression of the related invariant probabilities is derived. The transient behavior of these algorithms is also analyzed.

Postscript file: ALCOMFT-TR-01-179.ps.gz (159 kb).