On Universal Scaling of Distributed Queues under Load Balancing

MaRDI QIDQ6331848zbMATH OpenFDO

Authors Lei Ying

Publication date 26 December 2019

Abstract: This paper considers the steady-state performance of load balancing algorithms in a many-server system with distributed queues. The system has $N$ servers, and each server maintains a local queue with buffer size $b-1,$ i.e. a server can hold at most one job in service and $b-1$ jobs in the queue. Jobs in the same queue are served according to the first-in-first-out (FIFO) order. The system is operated in a heavy-traffic regime such that the workload per server is $lambda=1-N^{-alpha}$ for $0.5leqalpha<1.$ We identify a set of algorithms such that the steady-state queues have the following universal scaling, where {em universal} means that it holds for any $alphain[0.5,1)$: (i) the number of of busy servers is $lambdaN-o(1);$ and (ii) the number of servers with two jobs (one in service and one in queue) is $O(N^{alpha}logN);$ and (iii) the number of servers with more than two jobs is $Oleft(frac1N^{r(1-alpha)-1}ight),$ where $r$ can be any positive integer independent of $N.$ The set of load balancing algorithms that satisfy the sufficient condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), and power-of-$d$-choices (Po$d$) with $dgeq{N}^{a}lphalo{g}^{2}N.$ We further argue that the waiting time of such an algorithm is near optimal order-wise.

This page was built for publication: On Universal Scaling of Distributed Queues under Load Balancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6331848)