Asymptotic analysis of a nonlinear AIMD algorithm

• Published in: Discrete mathematics and theoretical computer science 2005-01, Vol.DMTCS Proceedings vol. AD,... (Proceedings), p.27-38
• Main Authors: Baryshnikov, Y., Coffman, E., Feng, J., Momčilović, P.
• Format: Article
• Language: English
• Subjects: [info.info-cg] computer science [cs]/computational geometry [cs.cg]; [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]; [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]; [info.info-hc] computer science [cs]/human-computer interaction [cs.hc]; [math.math-co] mathematics [math]/combinatorics [math.co]; aimd analysis; Combinatorics; Computational Geometry; Computer Science; congestion avoidance algorithms; Data Structures and Algorithms; differentiated service; Discrete Mathematics; fair resource allocation; Human-Computer Interaction; Mathematics
• ISSN: 1365-8050; 1462-7264; 1365-8050
• DOI: 10.46298/dmtcs.3365

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.