Economies-of-scale in resource sharing systems: tutorial and partial review of the QED heavy-traffic regime

Abstract

Multi-server queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the Quality-and-Efficiency Driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and only provide sketches or references for more advanced settings related to e.g. load balancing, overdispersion, parameter uncertainty, general service requirements and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not aimed to be exhaustive.

References in corpus (6)

• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic
• On Lerch's transcendent and the Gaussian random walk
• High order steady-state diffusion approximation of the Erlang-C system
• Heavy-tailed queues in the Halfin-Whitt regime
• Optimal Admission Control for Many-Server Systems with QED-Driven Revenues
• Robust heavy-traffic approximations for service systems facing overdispersed demand

Cited by in corpus (4)

• Scalable load balancing in networked systems: A survey of recent advances
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Tail Asymptotics and Scaling of Extrema
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Sensitivity on the Heavy-traffic Parameter
• Large deviations analysis for the $M/H_2/n+M$ queue in the Halfin-Whitt regime