























This paper studies a class of load balancing algorithms for many-server ($N$ servers) systems assuming finite buffer with size $b-1$ (i.e. a server can have at most one job in service and $b-1$ jobs in queue). We focus on steady-state performance of load balancing algorithms in the heavy traffic regime such that the load of system is $λ= 1 - N^{-α}$ for $0<α<0.5,$ which we call sub-Halfin-Whitt regime ($α=0.5$ is the so-called the Halfin-Whitt regime). We establish a sufficient condition under which the probability that an incoming job is routed to an idle server is one asymptotically. The class of load balancing algorithms that satisfy the condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), join-the-idle-queue (JIQ), and power-of-$d$-choices (Po$d$) with $d=N^α\log N$. The proof of the main result is based on the framework of Stein's method. A key contribution is to use a simple generator approximation based on state space collapse.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。