A decentralized adaptive algorithm for fair allocation of a shared resource‡. (22nd December 2015)

• Record Type: Journal Article
• Authors: Bhaya, Amit; Kaszkurewicz, Eugenius
• Other Names: Oliveira Tiago Roux guestEditor.; Fridman Leonid guestEditor.; Ortega Romeo guestEditor.
• Is Part Of: International journal of adaptive control and signal processing. Volume 30:Number 8/10(2016:Aug/Oct.)
• Page Start: 1449
• Page End: 1464
• Publication Date: 2015-12-22
• Subjects: resource allocation -- decentralized -- adaptive algorithm -- variable structure system -- AIMD algorithm -- congestion control; Adaptive control systems -- Periodicals; Adaptive signal processing -- Periodicals; 629.836
• DOI: 10.1002/acs.2655
• Languages: English
• ISSNs: 0890-6327

Abstract

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.