On Universal Scaling of Distributed Queues under Load Balancing

• DOI: 10.48550/arxiv.1912.11904
• Publication Date: 2019-01-01
• Authors: Xin Liu; Lei Ying
• Keywords: Probability (math.PR); FOS: Mathematics; 0101 mathematics; 01 natural sciences; Mathematics - Probability

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