Abstract:Bounding the steady-state queue length of a multiserver queue is a central challenge in queueing theory. Even for the classical $GI/GI/n$ queue with homogeneous servers, obtaining a simple, accurate bound that holds across all parameters is highly non-trivial. A recent breakthrough by Li and Goldberg (2025) establishes the first universal bound of order $O(1/(1-\rho))$, holding for every load $\rho<1$ and server count $n$ -- an order known to be tight in many regimes, including classical heavy-traffic, Halfin-Whitt, and Non-Degenerate Slowdown. However, their bounds carry astronomically large constants and rely on an intricate proof; they conjecture that a far simpler bound holds.
We introduce a leave-one-out coupling technique that yields a new universal $O(1/(1-\rho))$ bound for the $GI/GI/n$ queue, with a simple and transparent proof. Moreover, for light-tailed service times, the leading constant in our bound is orders of magnitude smaller than that in prior work. For instance, we bound the $M/GI/n$ queue's mean queue length by simply $1/(1-\rho)$ for New-Better-than-Used-in-Expectation service times, with similarly clean bounds for gamma, phase-type, and bounded service times.
Finally, our techniques extend to $GI/GI/n$ queues with fully heterogeneous service-time distributions, a setting not addressed by prior universal bounds.
From: Yige Hong [view email]
[v1]
Mon, 13 Oct 2025 05:13:23 UTC (393 KB)
[v2]
Sun, 5 Apr 2026 16:43:16 UTC (304 KB)
[v3]
Sat, 22 Aug 2026 02:36:03 UTC (211 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。