# 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 :
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.27-38, 2005, DMTCS Proceedings
Domaine :

Littérature citée [25 références]

https://hal.inria.fr/hal-01184037
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:15
Dernière modification le : mercredi 10 mai 2017 - 17:39:20
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:34

### Fichier

Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184037, version 1

### Citation

Y. Baryshnikov, E. Coffman, J. Feng, P. Momčilović. Asymptotic analysis of a nonlinear AIMD algorithm. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.27-38, 2005, DMTCS Proceedings. 〈hal-01184037〉

### Métriques

Consultations de la notice

## 141

Téléchargements de fichiers