# Universality of load balancing schemes on diffusion scale

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

### Abstract

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 language English s.n. 17 Published - 2015

### Publication series

Name arXiv 1510.02657 [math.PR]

• ## Cite this

Mukherjee, D., Borst, S. C., Leeuwaarden, van, J. S. H., & Whiting, P. A. (2015). Universality of load balancing schemes on diffusion scale. (arXiv; Vol. 1510.02657 [math.PR]). s.n.