Queues with Many Servers: The Virtual Waiting-Time Process in the QED Regime

We consider a first-come first-served multiserver queue in the Quality- and Efficiency-Driven (QED) regime. In this regime, which was first formalized by Halfin and Whitt, the number of servers N is not small, servers' utilization is (Efficiency-Driven) while waiting time is (Quality-Driven). This is equivalent to having the number of servers N being approximately equal to , where R is the offered load and β is a positive constant.

For the G/D_K/N queue in the QED regime, we analyze the virtual waiting time V_N(t), as N increases indefinitely. Assuming that the service-time distribution has a finite support (hence the D_K in G/D_K/N), it is shown that, in the limit, the scaled virtual waiting time is representable as a supremum over a random weighted tree (S denotes a service time). Informally, it is then argued that, for large N,

here is the averaging of over S, and the process is zero-mean Gaussian that summarizes all relevant information about arrivals and service times ( arises as a limit of an infinite-server (G/D_K/∞) process, appropriately scaled). The results are obtained by using both combinatorial and probabilistic arguments. Possible applications of our approximations include fast simulation of queues and estimation/prediction of customer waiting times in the QED regime.