Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T08:10:48.207Z Has data issue: false hasContentIssue false

Universality of load balancing schemes on the diffusion scale

Published online by Cambridge University Press:  09 December 2016

Debankur Mukherjee*
Affiliation:
Eindhoven University of Technology
Sem C. Borst*
Affiliation:
Eindhoven University of Technology and Nokia Bell Labs
Johan S. H. van Leeuwaarden*
Affiliation:
Eindhoven University of Technology
Philip A. Whiting*
Affiliation:
Macquarie University
*
* Postal address: Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, Netherlands.
* Postal address: Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, Netherlands.
* Postal address: Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, Netherlands.
*** Postal address: Department of Engineering, Macquarie University, North Ryde, NSW 2109, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2016