Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.23918 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912927307530240 |
|---|---|
| author | Liu, Xin Ying, Lei |
| author_facet | Liu, Xin Ying, Lei |
| contents | We study the steady-state delay performance of load balancing in large-scale systems with heterogeneous servers in the heavy-traffic regimes. The system consists of $N$ servers, each with a local buffer of size $b-1$, serving jobs in the first-in-first-out (FIFO) order. Jobs arrive according to a Poisson process with rate $λN$, where $λ= 1 - N^{-α}$ for any $α\in (0,1)$. Service times are assumed to be exponentially distributed with fully heterogeneous rates, where the service rate of each server can differ and may scale with the system size $N$. We study a queue length aware and service rate aware load balancing policy, Join-the-Fastest-Shortest-Queue (JFSQ), and demonstrate that it achieves asymptotic zero waiting time and probability under the heavy traffic regimes, including both the Sub-Halfin-Whitt ($α\in (0,0.5)$) and Super-Halfin-Whitt ($α\in [0.5,1)$) regimes. The performance bounds of waiting time and probability explicitly capture the convergence rate w.r.t. the system size $N$ and show the negative effect of server heterogeneity. Our analysis builds on the general framework of Stein's method with iterative state-space peeling, where we design a sequence of Lyapunov functions to analyze the high-dimensional heterogeneous system without assuming exchangeability and monotonicity. Our analysis shows that JFSQ efficiently utilizes servers with higher capacities, and the steady-state system can be coupled with a single-server queue via Stein's method. To the best of our knowledge, this is the first work to establish delay performance bounds of a load-balancing system with size $N$ and fully heterogeneous servers in heavy traffic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Zero-Waiting Load Balancing with Heterogeneous Servers in Heavy Traffic Liu, Xin Ying, Lei Probability We study the steady-state delay performance of load balancing in large-scale systems with heterogeneous servers in the heavy-traffic regimes. The system consists of $N$ servers, each with a local buffer of size $b-1$, serving jobs in the first-in-first-out (FIFO) order. Jobs arrive according to a Poisson process with rate $λN$, where $λ= 1 - N^{-α}$ for any $α\in (0,1)$. Service times are assumed to be exponentially distributed with fully heterogeneous rates, where the service rate of each server can differ and may scale with the system size $N$. We study a queue length aware and service rate aware load balancing policy, Join-the-Fastest-Shortest-Queue (JFSQ), and demonstrate that it achieves asymptotic zero waiting time and probability under the heavy traffic regimes, including both the Sub-Halfin-Whitt ($α\in (0,0.5)$) and Super-Halfin-Whitt ($α\in [0.5,1)$) regimes. The performance bounds of waiting time and probability explicitly capture the convergence rate w.r.t. the system size $N$ and show the negative effect of server heterogeneity. Our analysis builds on the general framework of Stein's method with iterative state-space peeling, where we design a sequence of Lyapunov functions to analyze the high-dimensional heterogeneous system without assuming exchangeability and monotonicity. Our analysis shows that JFSQ efficiently utilizes servers with higher capacities, and the steady-state system can be coupled with a single-server queue via Stein's method. To the best of our knowledge, this is the first work to establish delay performance bounds of a load-balancing system with size $N$ and fully heterogeneous servers in heavy traffic. |
| title | Zero-Waiting Load Balancing with Heterogeneous Servers in Heavy Traffic |
| topic | Probability |
| url | https://arxiv.org/abs/2509.23918 |