How Multiserver Queues Scale with Growing Congestion-Dependent Demand

Abstract

We investigate how performance scales in the standard M/M/n queue in the presence of growing congestion-dependent customer demand. We scale the queue by letting the potential (congestion-free) arrival rate be proportional to the number of servers, n, and letting n increase. We let the actual arrival rate with n servers be of the form λn=f(ξn)n, where f is a strictly-decreasing continuous function and ξn is a steady-state congestion measure. We consider several alternative congestion measures, such as the mean waiting time and the probability of delay. We show, under minor regularity conditions, that for each n there is a unique equilibrium pair (λ*n, ξ*n) such that ξ*n is the steady-state congestion associated with arrival rate λ*n and λ*n=f(ξ*n)n. Moreover, we show that, as n increases, the queue with the equilibrium arrival rate λ*n is brought into heavy traffic, but the three different heavy-traffic regimes for multiserver queues identified by Halfin and Whitt (1981) each can arise depending on the congestion measure used. In considerable generality, there is asymptotic service efficiency: the server utilization approaches one as n increases. Under the assumption of growing congestion-dependent demand, the service efficiency can be achieved even if there is significant uncertainty about the potential demand, because the actual arrival rate adjusts to the congestion.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 52 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.