How Multiserver Queues Scale with Growing Congestion-Dependent Demand

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.