Simple and Explicit Bounds for Multiserver Queues with 1 1 − ρ Scaling

Yuan Li () and David A. Goldberg ()
Additional contact information
Yuan Li: Amazon, Bellevue, Washington 98004
David A. Goldberg: Cornell Operations Research and Information Engineering, Ithaca, New York 14853

Mathematics of Operations Research, 2025, vol. 50, issue 2, 813-837

Abstract: We consider the first-come-first-serve (FCFS) G I / G I / n queue and prove the first simple and explicit bounds that scale as 1 1 − ρ under only the assumption that interarrival times have finite second moment, and service times have finite 2 + ϵ moment for some ϵ > 0 . Here, ρ denotes the corresponding traffic intensity. Conceptually, our results can be viewed as a multiserver analogue of Kingman’s bound. Our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay. The strength of our bounds (e.g., in the form of tail decay rate) is a function of how many moments of the service distribution are assumed finite. Our bounds scale gracefully, even when the number of servers grows large and the traffic intensity converges to unity simultaneously, as in the Halfin-Whitt scaling regime. Some of our bounds scale better than 1 1 − ρ in certain asymptotic regimes. In these same asymptotic regimes, we also prove bounds for the tail of the steady-state number in service. Our main proofs proceed by explicitly analyzing the bounding process that arises in the stochastic comparison bounds of Gamarnik and Goldberg for multiserver queues. Along the way, we derive several novel results for suprema of random walks and pooled renewal processes, which may be of independent interest. We also prove several additional bounds using drift arguments (which have much smaller prefactors) and point out a conjecture that would imply further related bounds and generalizations. We also show that when all moments of the service distribution are finite and satisfy a mild growth rate assumption, our bounds can be strengthened to yield explicit tail estimates decaying as O ( exp ( − x α ) ) , with α ∈ ( 0 , 1 ) , depending on the growth rate of these moments.

Keywords: 60K25; many-server queues; stochastic comparison; Kingman’s bound; renewal process; Halfin-Whitt (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0131 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:813-837

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().