Universality of load balancing schemes on diffusion scale

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

Research output: Book/ReportReportAcademic

5 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 \leq d \leq 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
Number of pages17
Publication statusPublished - 2015

Publication series

Volume1510.02657 [math.PR]


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

Cite this