### Abstract

We consider a system of $N$ parallel single-server queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. When a task arrives, the dispatcher assigns it to a server with the shortest queue among $d(N)$ randomly selected servers ($1 \leq d(N) \leq N$). This load balancing strategy is referred to as a JSQ($d(N)$) scheme, marking that it subsumes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial special case for $d(N) = N$. We construct a stochastic coupling to bound the difference in the queue length processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in the regime where $\lambda(N) / N \to \lambda 0$ as $N \to \infty$ with $d(N)/(\sqrt{N} \log (N))\to\infty$ corresponds to that for the JSQ policy. These results indicate that the optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively.

Original language | English |
---|---|

Number of pages | 36 |

Journal | arXiv |

Publication status | Published - 2 Dec 2016 |

### Bibliographical note

36 pages, 2 figures, companion paper of Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems (2016)### Keywords

- math.PR

## Fingerprint Dive into the research topics of 'Universality of Power-of-$d$ Load Balancing in Many-Server Systems'. Together they form a unique fingerprint.

## Cite this

Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H., & Whiting, P. A. (2016). Universality of Power-of-$d$ Load Balancing in Many-Server Systems.

*arXiv*.