What Is Queueing Analysis?

Queueing analysis is a branch of applied probability theory that models systems where customers or jobs arrive, wait for service, and depart, characterizing performance metrics such as mean waiting time, queue length, server utilization, and throughput as functions of the arrival and service processes. Rooted in the work of A.K. Erlang on telephone traffic engineering at the Danish telephone company in the early twentieth century, queueing analysis provides mathematically tractable frameworks for predicting and designing the behavior of systems ranging from computer networks and manufacturing lines to operating system schedulers and healthcare workflows. The field draws on probability theory, Markov processes, linear algebra, and optimization, and its results influence both the design of individual servers and the architecture of large-scale distributed infrastructures.

The Kendall notation A/S/c/K/N/D describes a queue by its arrival process A, service distribution S, number of servers c, capacity K, population size N, and service discipline D. The simplest tractable model, M/M/1, assumes Poisson arrivals, exponentially distributed service times, and a single server with infinite capacity. More general models such as M/G/1 (general service distribution) and G/G/c (general arrivals and service with c servers) require heavier analytical machinery and often yield only bounds or approximations. The central relation linking all queues is Little's Law, which states that the mean number of customers in any stable system equals the mean arrival rate multiplied by the mean time spent in the system, a result that holds regardless of arrival distribution, service distribution, or scheduling discipline.

Queueing Models and Performance Metrics

The M/M/1 queue yields closed-form expressions for queue length, waiting time, and server utilization as functions of the traffic intensity ρ = λ/μ, where λ is the arrival rate and μ is the service rate. As ρ approaches one from below, mean queue length and waiting time diverge, illustrating that utilization near 100% is incompatible with bounded delay. For the M/G/1 queue, the Pollaczek-Khinchine (P-K) formula extends this result to general service distributions, showing that variance in service time adds delay proportional to the coefficient of variation of the service time distribution. The arXiv introduction to queueing theory covers these foundational models and their derivations in accessible detail. The MIT lectures on queueing network models extend these results to networks of queues, where Jackson's theorem yields product-form stationary distributions when each node has Poisson arrivals and exponential service. Multi-server queues and closed networks require numerical methods or product-form approximations, with Jackson networks and BCMP networks providing exact product-form solutions for specific topologies.

Scheduling Disciplines

The order in which waiting customers are served profoundly affects individual delay even when it does not affect mean waiting time at a given utilization. First-come, first-served (FCFS) is fair but suboptimal in mean delay when service times vary widely. Shortest-job-first minimizes mean waiting time among all work-conserving disciplines but requires advance knowledge of service times. Shortest-remaining-processing-time (SRPT), which preemptively serves the job closest to completion, achieves provably optimal mean response time in the M/G/1 setting. The ACM SIGMETRICS new toolbox for scheduling theory introduced the SOAP framework, which unifies the analysis of a broad class of scheduling policies in the M/G/1 queue and yields delay distributions previously unknown for many policies. Processor sharing, in which all n customers in a system each receive 1/n of the server's capacity simultaneously, approximates time-sharing operating system schedulers and produces a mean response time that grows linearly with job size at any utilization.

Applications

Queueing analysis has applications across a wide range of systems and domains, including:

• Network router and switch buffer dimensioning for quality of service
• Cloud computing resource allocation and auto-scaling policies
• Operating system process and I/O scheduling
• Publish-subscribe message broker capacity planning and flow control
• Manufacturing line design and hospital patient flow optimization
• Call center staffing and service-level agreement evaluation