NDLI: Distributed Proportional Fair Load Balancing in Heterogenous Systems

Content Provider	ACM Digital Library
Author	Proutiere, Alexandre Yun, Se-Young
Abstract	We consider the problem of distributed load balancing in heterogenous 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). We assume that each server equally shares in time its capacity among users allocated to it. Users initially attach to an arbitrary server, but at random instants of time, they probe the load at a new server and migrate there if this improves their service rate. The dynamics under this distributed load balancing scheme, referred to as Random Local Search (RLS), may be interpreted as those generated by strategic players updating their strategy in a load balancing game. In closed systems, where the user population is fixed, we show that this game has pure Nash Equilibriums (NEs), and that these equilibriums get close to a Proportionally Fair (PF) allocation of users to servers when the user population grows large. We provide an anytime upper bound of the gap between the allocation under RLS and the PF allocation. In open systems, where users randomly enter the system and leave upon service completion, we establish that the RLS algorithm stabilizes the system whenever this it at all possible under centralized load balancing schemes, i.e., it is throughput-optimal. The proof of this result relies on a novel Lyapounov analysis that captures the dynamics due to both users' migration and their arrivals and departures. To our knowledge, the RLS algorithm constitutes the first fully distributed and throughput-optimal load balancing scheme in heterogenous parallel server systems. We extend our analysis to various scenarios, e.g. to cases where users can be simultaneously served by several servers. Finally we illustrate through numerical experiments the efficiency of the RLS algorithm.
Starting Page	17
Ending Page	30
Page Count	14
File Format	PDF
ISSN	01635999
DOI	10.1145/2796314.2745861
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	43
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Distributed scheduling Stability Load balancing Game theory
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed Proportional Fair Load Balancing in Heterogenous Systems

Temporal load balancing for distributed backup scheduling

Load balancing in homogeneous broadcast distributed systems

Optimal load balancing and scheduling in a distributed computer system

Load balancing in distributed systems:a summary

Load distribution and balancing support in a workstation-based distributed system

The effect of local scheduling in load balancing designs

Insensitive load balancing

Towards Cooling Internet-Scale Distributed Networks on the Cheap

Distributed Proportional Fair Load Balancing in Heterogenous Systems

Similar Documents

Distributed Proportional Fair Load Balancing in Heterogenous Systems

Temporal load balancing for distributed backup scheduling

Load balancing in homogeneous broadcast distributed systems

Optimal load balancing and scheduling in a distributed computer system

Load balancing in distributed systems:a summary

Load distribution and balancing support in a workstation-based distributed system

The effect of local scheduling in load balancing designs

Insensitive load balancing

Towards Cooling Internet-Scale Distributed Networks on the Cheap

Distributed Proportional Fair Load Balancing in Heterogenous Systems