DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Asymptotic analysis of a nonlinear AIMD algorithm

Y. Baryshnikov, E. Coffman, J. Feng, P. Momčilović


The Additive-Increase-Multiplicative Decrease (AIMD) algorithm is an effective technique for controlling competitive access to a shared resource. Let N be the number of users and let xi(t) be the amount of the resource in possession of the i-th user. The allocations xi(t) increase linearly until the aggregate demand Σi xi(t) exceeds a given nominal capacity, at which point a user is selected at a random time and its allocation reduced from xi(t) to xi(t)/γ, for some given parameter γ>1. In our new, generalized version of AIMD, the choice of users to have their allocations cut is determined by a selection rule whereby the probabilities of selection are proportional to xiα(t)/ Σj xjα, with α a parameter of the policy. Variations of parameters allows one to adjust fairness under AIMD (as measured for example by the variance of xi(t)) as well as to provide for differentiated service. The primary contribution here is an asymptotic, large-N analysis of the above nonlinear AIMD algorithm within a baseline mathematical model that leads to explicit formulas for the density function governing the allocations xi(t) in statistical equilibrium. The analysis yields explicit formulas for measures of fairness and several techniques for supplying differentiated service via AIMD.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional