Discrete Mathematics & Theoretical Computer Science |

- 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.

Source: HAL:hal-01184037v1

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]

This page has been seen 218 times.

This article's PDF has been downloaded 238 times.