Universality of load balancing schemes on the diffusion scale

Debankur Mukherjee*, Sem C. Borst, Johan S H Van Leeuwaarden, Philip A. Whiting

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


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 policy (d=1) and the celebrated join-the-shortest queue 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 - 1 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