On AIMD algorithms with correlated losses

F. Guillemin, Ph. Robert, and B. Zwart


The behavior of connection transmitting packets into a network according to a general additive-increase multiplicative-decrease (AIMD) algorithm is investigated. It is assumed that loss of packets occurs in clumps. When a packet is lost, a certain number of subsequent packets are also lost (correlated losses). We analyze the congestion window size distribution and the throughput of the connection in the stationary regime when the occurrence of clumps becomes arbitrarily small. From a probabilistic point of view, it is shown that exponential integral random variables associated to compound Poisson processes play a key role. Analytically, to derive the explicit expression of the distributions involved, the natural framework of this study turns out to be the $q$-calculus. Different loss models are then compared using concave ordering. Quite surprisingly, it is shown that, for a fixed loss rate, the correlated loss model has a higher throughput than an uncorrelated model.

Presentation Slides

Based on the Papers:

V. Dumas, F. Guillemin, and Ph. Robert, "A Markovian analysis of AIMD algorithms"

F. Guillemin, Ph. Robert and B. Zwart, "AIMD algorithms and exponential functionals",
Submitted to The Annals of Applied Probability, April 2002