We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Load Balancing in the Nondegenerate Slowdown Regime.
- Authors
Gupta, Varun; Walton, Neil
- Abstract
The exact study of control policies for queueing systems, such as prioritizing queues or load-balancing among servers, is often notoriously intractable. The usual path to study these questions is an asymptotic analysis where either the system load is increased to its capacity or the size of the queueing system is increased (called many servers regime) at the same time as its load is increased. In the paper "Load Balancing in the Nondegenerate Slowdown Regime," authors V. Gupta and N. Walton argue that the traditional asymptotic regimes are insufficient for studying the properties of the most classical load-balancing policy, join the shortest queue (JSQ), where arriving jobs join the server with the fewest number of jobs. By studying load-balancing policies in the novel nondegenerate slowdown asymptotic regime, the authors conclude that JSQ achieves performance close to the ideal centralized policy. Further, the work proposes a simpler load-balancing policy, called idle one first, which achieves the same performance as JSQ but at a much smaller communication overhead between the servers and the load balancer. 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. The online appendix is available at http://doi.org/10.1287/opre.2018.1768.
- Subjects
NON-degenerate perturbation theory; LOAD balancing (Computer networks); QUEUEING networks; APPROXIMATION theory; COMMUNICATION
- Publication
Operations Research, 2019, Vol 67, Issue 1, p281
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.2018.1768