Y. Baryshnikov ; E. Coffman ; J. Feng ; P. Momčilović - Asymptotic analysis of a nonlinear AIMD algorithm

dmtcs:3365 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3365
Asymptotic analysis of a nonlinear AIMD algorithmArticle

Authors: Y. Baryshnikov 1; E. Coffman 2; J. Feng 2; P. Momčilović 3

  • 1 Alcatel-Lucent Bell Labs
  • 2 Department of Electrical Engineering [New York]
  • 3 Department of Electrical Engineering and Computer Science

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.

Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: differentiated service,fair resource allocation,congestion avoidance algorithms,AIMD analysis,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

Consultation statistics

This page has been seen 188 times.
This article's PDF has been downloaded 216 times.