Load Balancing in the Nondegenerate Slowdown Regime

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.