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 journalArticle

12 Citations (Scopus)

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≤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
Volume53
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016

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

  • Cite this