Efficient load balancing in large-scale systems

D. Mukherjee, S. C. Borst, J. S H Van Leeuwaarden, P. A. Whiting

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

3 Citations (Scopus)


We consider a system of N identical parallel server pools and a single dispatcher where tasks arrive as a Poisson process. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution. The execution times are assumed to be exponentially distributed, and do not depend on the number of tasks contending for service. However, the experienced performance (e.g. in terms of received throughput or packet-level delay) does degrade with an increasing number of concurrent tasks at the same server pool. In order to optimize the performance, the dispatcher therefore aims to evenly distribute the tasks across the various server pools, using either a power-of-d or a threshold-based load balancing scheme. In the power-of-d scheme, an arriving task is assigned to the server pool with the minimum number of active tasks among d(N) randomly selected server pools (1 ≤ d(N) ≤ N). In the threshold-based scheme, an incoming task is dispatched to an arbitrary server pool with fewer than L active tasks, if there is any, to an arbitrary server pool with fewer than H > L tasks otherwise, or to a randomly selected server pool if all server pools have H or more tasks. This scheme can be implemented in a server-driven manner, with O(1) communication overhead per task, as opposed to O(d(N)) in the power-of-d scheme. We derive the fluid-level dynamics for the power-of-d scheme with d(N) → ∞ as N → ∞ and the threshold-based scheme, along with the associated fixed points. As it turns out, the fluid limit for the power-of-d scheme does not depend on the exact growth rate of d(N). We also characterize the diffusion-level behavior of the power-of-d scheme with d(N) ≥ √N log(N), and show that it coincides with that of the threshold-based scheme with suitably selected parameters L and H. In particular, the threshold-based scheme can achieve similar performance as the power-of-d scheme with d(N) ≥ √N log(N), and thus diffusion-level optimality, with only O(1) rather than O(N) communication overhead per task.

Original languageEnglish
Title of host publication2016 50th Annual Conference on Information Systems and Sciences, CISS 2016
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages6
ISBN (Electronic)9781467394574
Publication statusPublished - 26 Apr 2016
Event50th Annual Conference on Information Systems and Sciences, CISS 2016 - Princeton, United States
Duration: 16 Mar 201618 Mar 2016


Other50th Annual Conference on Information Systems and Sciences, CISS 2016
Country/TerritoryUnited States


Dive into the research topics of 'Efficient load balancing in large-scale systems'. Together they form a unique fingerprint.

Cite this