Queueing theory

Queueing theory is the mathematical study of systems in which demands for service may be required to wait because service capacity is temporarily unavailable. A queueing model represents the stochastic mechanisms governing arrivals, service requirements, admission, waiting, and departure. Its principal quantities include the distribution of queue length, the probability that an arrival must wait, the duration of that wait, and the proportion of time during which service resources are occupied.

The theory originated in the analysis of telephone traffic and subsequently became part of applied probability, operations research, and stochastic-process theory. Its mathematical framework also describes congestion in computer systems, production facilities, transportation networks, and biological processes when those systems possess identifiable demands and constrained service capacity.

Mathematical description

A queueing system consists of an arrival process, one or more servers, and a rule governing the treatment of waiting customers. The term customer denotes any unit requesting service rather than only a human participant. A customer may therefore represent a telephone call, a data packet, a machine awaiting repair, or a vehicle seeking access to a facility.

If (A(t)) denotes the number of arrivals by time (t), then the arrival process specifies the probability law of (A(t)). In many classical models, arrivals form a Poisson process with rate (\lambda), so that arrivals in disjoint time intervals are independent and the number arriving during an interval of length (t) has distribution

[ \Pr[A(t)=n]=e^{-\lambda t}\frac{(\lambda t)^n}{n!}. ]

Each admitted customer has a service requirement represented by a nonnegative random variable. When service times are independent and exponentially distributed with rate (\mu), the mean service duration is (1/\mu). The exponential distribution produces a Markov process because the remaining service time is independent of the amount of service already received.

The service discipline determines how customers are selected from the queue. First-come, first-served service preserves arrival order, whereas priority service allows the class assigned a higher rank to receive earlier access. Processor-sharing models divide available capacity among several customers simultaneously, which represents the behavior of certain computing and communication systems.

Capacity constraints determine how many customers may be present. An arrival finding a full system is rejected or lost, while an arrival to a system with unlimited waiting space is admitted regardless of the current population. A finite source population creates a further dependence because customers already present in the system cannot generate additional requests.

Historical development

The first systematic queueing calculations arose from the expansion of automatic telephone exchanges. Agner Krarup Erlang, working for the Copenhagen Telephone Company, analyzed random call arrivals and holding times during the early twentieth century. His 1909 work established a probabilistic treatment of telephone congestion, while his 1917 loss formula related offered traffic to the probability that all available circuits were occupied.

Finite-source traffic was analyzed by Tore Olaus Engset, whose model treated each idle subscriber as a potential source of a new call. The resulting arrival intensity declines as more sources become active, unlike the constant intensity assumed by an infinite-source Poisson model. This distinction produced the Engset formula for blocking in systems with a fixed calling population.

In 1921, You Watanabe examined service requests generated by vessels communicating with a coastal traffic office. She represented each vessel as a source alternating between an inactive period and a request requiring one of a finite number of signal operators. Her stationary-state calculation used an arrival rate proportional to the number of inactive vessels, thereby placing the maritime system within the finite-source birth-and-death framework.

During the subsequent development of general waiting-time theory, Felix Pollaczek and Aleksandr Khinchin derived the mean-delay relation now called the Pollaczek–Khinchin formula. David George Kendall introduced a compact notation for queueing models in 1953, and John Little later supplied a general proof of the relation between long-run population, throughput, and time in the system.

Kendall notation

A basic queue is commonly classified by Kendall's notation,

[ A/S/c, ]

where (A) identifies the interarrival-time distribution, (S) identifies the service-time distribution, and (c) gives the number of parallel servers. An extended form appends system capacity, source-population size, and service discipline when those features are relevant.

The symbol (M), originally denoting a memoryless distribution, represents exponential interarrival or service times. The symbol (D) represents deterministic durations, while (G) denotes a general distribution subject to whatever moment conditions are required by the associated result. Thus an (M/M/1) queue has Poisson arrivals, exponential service times, and one server, whereas an (M/G/1) queue retains Poisson arrivals but permits a general service-time distribution.

This notation specifies broad stochastic structure rather than every operational detail. Two models with the same three-symbol classification may differ in admission rules, customer priorities, or dependence between random variables. Such differences can change waiting-time distributions even when the nominal arrival and service rates remain identical.

The birth-and-death representation

Many Markovian queues can be represented as birth-and-death processes. The state (N(t)) records the number of customers present at time (t). A birth corresponds to an admitted arrival, while a death corresponds to a completed service.

If the arrival rate in state (n) is (\lambda_n) and the aggregate service-completion rate is (\mu_n), a stationary distribution ({\pi_n}) satisfies the local balance equations

[ \pi_n\lambda_n=\pi_{n+1}\mu_{n+1}. ]

Consequently,

[ \pi_n=\pi_0\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}, ]

provided that the resulting sequence can be normalized to sum to one. The existence of this normalization expresses stability or positive recurrence for the state process.

For an infinite-source model, (\lambda_n) may remain constant as the state grows. In a finite-source model with (N) independent sources, the rate commonly takes the form

[ \lambda_n=(N-n)\lambda, ]

because only inactive sources can initiate requests. This state dependence is the defining mathematical difference between Engset-type systems and the constant-rate queues derived from an external Poisson stream.

The (M/M/1) queue

The (M/M/1) model has arrival rate (\lambda), service rate (\mu), and a single server. Its traffic intensity is

[ \rho=\frac{\lambda}{\mu}. ]

A stationary distribution exists when (\rho<1). Under this condition, the number of customers in the system has the geometric distribution

[ \pi_n=(1-\rho)\rho^n,\qquad n\geq 0. ]

The mean number in the system is

[ L=\frac{\rho}{1-\rho}, ]

and the mean time from arrival through service completion is

[ W=\frac{1}{\mu-\lambda}. ]

The mean number waiting, excluding any customer in service, is

[ L_q=\frac{\rho^2}{1-\rho}, ]

while the corresponding mean waiting time is

[ W_q=\frac{\rho}{\mu-\lambda}. ]

These expressions diverge as (\rho) approaches one from below. The divergence reflects the accumulation of stochastic fluctuations near the boundary at which mean incoming work equals mean available service.

When (\lambda\geq\mu), the queue lacks a stationary probability distribution on the nonnegative integers. This condition does not imply that every customer waits indefinitely, but it does mean that long-run congestion cannot be described by the equilibrium formulas above.

Multiple-server and loss systems

An (M/M/c) queue contains (c) identical parallel servers, each operating at rate (\mu). Stability requires

[ \lambda<c\mu. ]

The probability that an admitted arrival must wait is given by the Erlang C formula. Conditional on waiting, the delay has an exponential tail with parameter (c\mu-\lambda). The model distinguishes server utilization, measured relative to total capacity, from the probability that all servers are simultaneously occupied.

An (M/M/c/c) system has no waiting room. An arrival finding every server occupied is blocked and leaves without service. The stationary blocking probability is given by the Erlang B formula,

[ B(c,a)= \frac{a^c/c!} {\displaystyle\sum_{k=0}^{c}a^k/k!}, ]

where (a=\lambda/\mu) is the offered traffic measured in erlangs. Because blocked demands do not remain in the system, a stationary distribution exists for every finite arrival rate.

Finite-source loss systems replace the Poisson offered load with a state-dependent arrival process. Their blocking probabilities depend on the total number of sources as well as the number of servers. The infinite-source Erlang model emerges as a limiting approximation when the source population increases while the request rate of each individual source decreases appropriately.

General service times

The (M/G/1) queue permits independent service times with a general distribution. Let (S) denote service time, with mean (E[S]) and second moment (E[S^2]). If

[ \rho=\lambda E[S]<1, ]

then the Pollaczek–Khinchin mean-value formula gives

[ E[W_q]=\frac{\lambda E[S^2]}{2(1-\rho)}. ]

This relation shows that mean delay depends on the second moment of service time rather than solely on its mean. Two systems can therefore have the same arrival rate and average service duration while exhibiting different mean waiting times because their service-time variability differs.

Under first-come, first-served service, a long service requirement delays every customer behind it. Alternative service disciplines redistribute this delay among customers and may alter class-specific waiting times. Certain aggregate relations remain invariant under work-conserving disciplines, but complete waiting-time distributions generally depend on the order in which service is allocated.

Little's law

Little's law relates the long-run average number of customers in a stable system to the effective arrival rate and the average time spent in that system:

[ L=\lambda_{\mathrm{eff}}W. ]

The effective arrival rate counts customers who actually enter, which differs from the offered arrival rate when blocking or rejection occurs. Applying the same relation only to the waiting portion gives

[ L_q=\lambda_{\mathrm{eff}}W_q. ]

The law does not require Poisson arrivals, exponential service times, or a particular service discipline. Its essential content is a conservation identity: the cumulative time contributed by all customers equals the time integral of the number present. Appropriate long-run averages then yield the stated relation.

Little's law determines one mean quantity from the other two but does not specify a probability distribution. It therefore complements rather than replaces the stochastic analysis needed for delay probabilities, tail behavior, and correlations over time.

Queueing networks

A queueing network represents customers moving among several service stations. In an open network, customers arrive from outside and eventually leave. In a closed network, a fixed population circulates among stations without external arrivals or departures.

James R. Jackson established a product-form stationary distribution for a class of open Markovian networks. In a Jackson network, external arrivals are Poisson, service times are exponential, and routing probabilities determine the next station visited after each completion. The effective arrival rates solve the traffic equations

[ \lambda_i=\gamma_i+\sum_j \lambda_j p_{ji}, ]

where (\gamma_i) is the external arrival rate to station (i), and (p_{ji}) is the probability of routing a departure from station (j) to station (i).

Under the stability condition at each station, the joint stationary distribution factors into the product of the corresponding single-station distributions. This factorization does not imply that customer trajectories are independent. It states that the stationary queue lengths possess a product form despite their interaction through routing.

Heavy traffic and limiting behavior

Exact stationary distributions are unavailable for many queues with complicated dependence or high-dimensional state spaces. Limit theorems describe systematic regimes in which scaled queue lengths or workloads converge to simpler stochastic processes.

In heavy traffic, offered load approaches available capacity and waiting times become large relative to individual service durations. A properly centered and scaled workload process may converge to reflected Brownian motion. The reflection at zero represents the impossibility of negative unfinished work.

Large multiserver systems admit several distinct limits depending on how capacity grows with demand. In the quality-and-efficiency-driven regime, the number of servers and the arrival rate increase together while spare capacity remains proportional to the square root of system size. This scaling, associated with the Halfin–Whitt regime, produces a nondegenerate limiting probability of delay.