Asymptotic analysis of a nonlinear AIMD algorithm

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_i(t)$ be the amount of the resource in possession of the $i$-th user. The allocations $x_i(t)$ increase linearly until the aggregate demand $\sum_i x_i(t)$ exceeds a given nominal capacity, at which point a user is selected at a random time and its allocation reduced from $x_i(t)$ to $x_i(t)/ \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_i(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 $x_i(t)$ in statistical equilibrium. The analysis yields explicit formulas for measures of fairness and several techniques for supplying differentiated service via AIMD.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [25 references]

https://hal.inria.fr/hal-01184037
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 3:52:15 PM
Last modification on : Friday, December 18, 2020 - 6:46:05 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:34 AM

File

Publisher files allowed on an open archive

Identifiers

• HAL Id : hal-01184037, version 1

Citation

Y. Baryshnikov, E. Coffman, J. Feng, P. Momčilović. Asymptotic analysis of a nonlinear AIMD algorithm. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.27-38. ⟨hal-01184037⟩

Record views