Paper Info
Title
Distributed load balancing in heterogenous systems
Abstract
We consider the problem of distributed load balancing in heterogeneous parallel server systems, where the service rate achieved by a user at a server depends on both the user and the server. Such heterogeneity typically arises in wireless networks (e.g., servers may represent frequency bands, and the service rate of a user varies across bands). Users select servers in a distributed manner. They initially attach to an arbitrary server. However, at random instants of time, they may probe the load at a new server and migrate there to improve their service rate. We analyze the system dynamics under the natural Random Local Search (RLS) migration scheme, introduced in [5]. Under this scheme, when a user has the opportunity to switch servers, she does it only if this improves her service rate. The dynamics under RLS may be interpreted as those generated by strategic players updating their strategy in a load balancing game. We show that this game has pure Nash Equilibriums (NEs), and we analyze their efficiency. We further prove that when the user population grows large, pure NEs get closer to a Proportionally Fair (PF) allocation of users to servers, and we characterize the gap between equilibriums and this ideal allocation depending on user population. Under the RLS algorithm, the system converges to pure NEs: we study the time it takes for the system to reach the PF allocation within a certain margin.
Year
DOI
Venue
2014
10.1109/CISS.2014.6814133
CISS
Keywords
DocType
Volume
parallel processing,load balancing game,proportionally fair allocation,heterogeneous parallel server systems,heterogeneous systems,natural random local search migration scheme,nash equilibriums,rls algorithm,queueing theory,resource allocation,wireless networks,rls migration scheme,search problems,game theory,system dynamics,service rate,distributed load balancing,resource management,servers,games,computer and information science,sociology,statistics
Journal
abs/1403.4075
Citations 
PageRank 
References 
3
0.40
7
Authors
2
Name
Order
Citations
PageRank
Se-Young Yun1518.52
Alexandre Proutiere255840.94