Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing Schemes: Theory to Algorithms

Abstract

We establish a unified analytical framework for load balancing systems, which allows us to construct a general class $Î $ of policies that are both throughput optimal and heavy-traffic delay optimal. This general class $Î $ includes as special cases popular policies such as join-shortest-queue and power-of-$d$, but not the join-idle-queue (JIQ) policy. In fact, we show that JIQ, which is not in $Î $, is actually not heavy-traffic delay optimal. Owing to the significant flexibility offered by class $Î $, we are able to design a new policy called join-below-threshold (JBT-d), which maintains the simplicity of pull-based policies such as JIQ, but updates its threshold dynamically. We prove that JBT-$d$ belongs to the class $Î $ when the threshold is picked appropriately and thus it is heavy-traffic delay optimal. Extensive simulations show that the new policy not only has a low complexity in message rates, but also achieves excellent delay performance, comparable to the optimal join-shortest-queue in various system settings.

42 pages, 34 figure, this is the technical report for a paper accepted by ACM Sigmetrics 2018