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 (lambda) n = f((xi) n )n , where f is a strictly-decreasing continuous function and (xi) 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 ((lambda)* n , (xi)* n ) such that (xi)* n is the steady-state congestion associated with arrival rate (lambda)* n and (lambda)* n = f((xi)* n )n . Moreover, we show that, as n increases, the queue with the equilibrium arrival rate (lambda)* 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.