Load Balancing in the Nondegenerate Slowdown Regime

Varun Gupta () and Neil Walton ()
Additional contact information
Varun Gupta: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Neil Walton: Alan Turing Building, University of Manchester, Manchester M13 9PL, United Kingdom

Operations Research, 2019, vol. 67, issue 1, 281-294

Abstract: We analyze join-the-shortest-queue (JSQ) in a contemporary scaling regime known as the nondegenerate slowdown (NDS) regime. Join-the-shortest-queue is a classical load-balancing policy for queueing systems with multiple parallel servers. Parallel server queueing systems are regularly analyzed and dimensioned by diffusion approximations achieved in the Halfin–Whitt scaling regime. However, when jobs must be dispatched to a server upon arrival, we advocate the nondegenerate slowdown regime to compare different load-balancing rules. In this paper we identify novel diffusion approximation and timescale separation that provides insights into the performance of JSQ. We calculate the price of irrevocably dispatching jobs to servers and prove this to be within 15% (in the NDS regime) of the rules that may maneuver jobs between servers. We also compare our results for the JSQ policy with the NDS approximations of many modern load-balancing policies such as idle-queue-first and power-of-d-choices policies that act as low information proxies for the JSQ policy. Our analysis leads us to construct new rules that have identical performance to JSQ but require less communication overhead than power of two choices.

Keywords: nondegenerate slowdown; load balancing; join-the-shortest-queue; M/M/k (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1768 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:1:p:281-294

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().