Universality of load balancing schemes on the diffusion scale

D. Mukherjee, S.C. Borst, J.S.H. van Leeuwaarden, Phil Whiting

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)
3 Downloads (Pure)


We consider a system of N parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among d randomly selected servers otherwise (1≤d≤N). This load balancing scheme subsumes the so-called Join-the-Idle Queue (JIQ) policy (d=1) and the celebrated Join-the-Shortest Queue (JSQ) policy (d=N) as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin-Whitt heavy-traffic regime, and establish that it does not depend on the value of d, implying that assigning tasks to idle servers is sufficient for diffusion level optimality.
Original languageEnglish
Pages (from-to)1111-1124
Number of pages14
JournalJournal of Applied Probability
Issue number4
Publication statusPublished - Dec 2016


Dive into the research topics of 'Universality of load balancing schemes on the diffusion scale'. Together they form a unique fingerprint.

Cite this