Premium
A decentralized adaptive algorithm for fair allocation of a shared resource
Author(s) -
Bhaya Amit,
Kaszkurewicz Eugenius
Publication year - 2015
Publication title -
international journal of adaptive control and signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.73
H-Index - 66
eISSN - 1099-1115
pISSN - 0890-6327
DOI - 10.1002/acs.2655
Subject(s) - computer science , multiplicative function , network congestion , variable (mathematics) , resource allocation , mathematical optimization , distributed computing , algorithm , mathematics , computer network , mathematical analysis , network packet
Summary This paper views the classical Chiu–Jain algorithm, originally proposed for congestion control of network links, as a decentralized algorithm for the fair allocation of a total of c units of a shared resource among n users. A new analysis is given of the general case of additive increase and multiplicative decrease (AIMD) dynamics, from the perspective of virtual equilibria and variable structure systems, leading to a better understanding of the Chiu–Jain algorithm, which is one example of AIMD dynamics. It is shown that the variable structure discrete dynamical system that describes the evolution of the share of each individual, starting from an arbitrary initial allocation, always attains a neighbourhood of the fair share ( c / n ) for each user, under the assumption that the latter is known. Subsequently, a new adaptive version of the algorithm, called adaptive AIMD, is described, with the same property of converging to the fair share, without assuming that it is known. Simulations that show the behaviour and advantages of the proposed adaptive AIMD adaptive algorithm are given. Copyright © 2015 John Wiley & Sons, Ltd.