Asymptotic analysis of a nonlinear AIMD algorithmReport as inadecuate

Asymptotic analysis of a nonlinear AIMD algorithm - Download this document for free, or read online. Document in PDF available to download.

1 Alcatel-Lucent Bell Labs 2 Columbia - Department of Electrical Engineering 3 EECS - Department of Electrical Engineering and Computer Science

Abstract : 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 $x it$ be the amount of the resource in possession of the $i$-th user. The allocations $x it$ increase linearly until the aggregate demand $\sum i x it$ exceeds a given nominal capacity, at which point a user is selected at a random time and its allocation reduced from $x it$ to $x it- \gamma$ , for some given parameter $\gamma >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 $x i^{\alpha} t- \sum j x j^{\alpha}$, with $\alpha$ a parameter of the policy. Variations of parameters allows one to adjust fairness under AIMD as measured for example by the variance of $x it$ 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 $x it$ in statistical equilibrium. The analysis yields explicit formulas for measures of fairness and several techniques for supplying differentiated service via AIMD.

Keywords : differentiated service fair resource allocation congestion avoidance algorithms AIMD analysis

Author: Y. Baryshnikov - E. Coffman - J. Feng - P. Momčilović -



Related documents