17documents trouvés
Worst-case analysis of non-cooperative load balancing
O.BRUN, B.PRABHU
MRS
Manifestation avec acte : Workshop on Algorithmic Game Theory: Dynamics and Convergence in Distributed Systems, Bordeaux (France), 5 Juillet 2010, 5p. , N° 10425
Diffusable
122060Price of Anarchy in Non-Cooperative Load Balancing
U.AYESTA, O.BRUN, B.PRABHU
MRS
Manifestation avec acte : 29th Annual International Conference on Computer Communications (IEEE INFOCOM 2010), San Diego (USA), 15-19 Mars 2010, 6p. , N° 10052
Diffusable
120993Prix de l'Anarchie et Equilibrage de Charge Non-Coopératif
U.AYESTA, O.BRUN, B.PRABHU
MRS
Rapport LAAS N°10067, Février 2010
Diffusable
120440Dynamic Discrete Power Control in Cellular Networks
E.ALTMAN, K.E.AVRACHENKOV, I.MENACHE, G.MILLER, B.PRABHU, A.SHWARTZ
INRIA Sophia, MIT, IPI RAN, MRS, TECHNION
Revue Scientifique : IEEE Transactions on Automatic Control, Vol.54, N°10, pp. 2328-2340, Octobre 2009 , N° 09822
Diffusable
120217Price of Anarchy in Non-Cooperative Load Balancing
U.AYESTA, O.BRUN, B.PRABHU
MRS
Rapport LAAS N°09833, 11 Septembre 2009
Lien : http://hal.archives-ouvertes.fr/hal-00416123/fr/
Diffusable
120239Analysis of a Red Queue : A Singular Perturbation Approach
E.ALTMAN, K.E.AVRACHENKOV, B.PRABHU
INRIA Sophia, MRS
Ouvrage (auteur) : Traffic engineering, performance evaluation studies and tools for heterogeneous networks, River Publishers, N°978-87-92329-16-5, 4 Février 2009, pp.371-397 , N° 09827
Diffusable
120225Load balancing in processor sharing systems
E.ALTMAN, U.AYESTA, B.PRABHU
INRIA Sophia, MRS
Rapport LAAS N°08295, Juin 2008, 11p.
Lien : http://hal.archives-ouvertes.fr/hal-00286455/fr/
Diffusable
Plus d'informations
Abstract
In this paper, we investigate optimal load balancing strategies for a multi-class multi-server processor-sharing system with a Poisson input stream, heterogeneous service rates, and a server-dependent holding cost per unit time. Specifically, we study $(i)$ the centralized setting in which a dispatcher routes incoming jobs based on their service time requirements so as to minimize the weighted mean sojourn time in the system; and $(ii)$ the decentralized, distributed non-cooperative setting in which each job, aware of its service time, selects a server with the objective of minimizing its weighted mean sojourn time in the system. For the decentralized setting we show the existence of a potential function, which allows us to transform the non-cooperative game into a standard convex optimization problem. For the two aforementioned settings, we characterize the set of optimal routing policies and obtain a closed form expression for the load on each server under any such policy. Furthermore, we show the existence of an optimal policy that routes a job independently of its service time requirement. We also show that the set of servers used in the decentralized setting is a subset of set of servers used in the centralized setting. Finally, we compare the performance perceived by jobs in the two settings by studying the so-called Price of Anarchy (PoA), that is, the ratio between the decentralized and the optimal centralized solutions. When the holding cost per unit time is the same for all servers, it is known that the PoA is upper bounded by the number of servers in the system. Interestingly, we show that the PoA for our system can be unbounded. In particular this indicates that in our system, the performance of selfish routing can be extremely inefficient.
Mots-Clés / Keywords
M/G/1 processor; Sharing queues; Server farms; Load balancing; Potential game; Price of anarchy;