Queuing Theory — Mathematics Knowledge System

Overview

Queuing theory studies the formation and dynamics of waiting lines (queues) in stochastic systems. The Kendall notation A/B/c denotes a queue with inter-arrival distribution A, service distribution B, and c servers. The fundamental M/M/1 queue (Poisson arrivals, exponential service, 1 server) yields explicit formulas for steady-state probabilities, mean queue length, and mean waiting time. Little's Law (L = lambda W) is a universal relationship between average number in system, arrival rate, and average time in system.

Intuition

Queuing theory quantifies the tradeoff between service capacity and waiting time. The key insight: at low utilization (rho = arrival rate / service rate close to 0), queues are short and waits are minimal. But as rho approaches 1, the queue length and waiting times blow up, diverging to infinity at rho = 1 (full utilization). This nonlinear sensitivity -- the queue is fine at 90% utilization but catastrophic at 100% -- is the fundamental lesson of M/M/1. Little's Law (L = lambda W) is a universal accounting identity: customers in the system equals arrival rate times average time spent.

Formal Definition

Definition

An M/M/1 queue has Poisson arrivals at rate lambda, exponential service at rate mu (with mu > lambda for stability), and a single server.

\rho = \frac{\lambda}{\mu} < 1 \quad \text{(stability condition)}

Traffic intensity / utilization

\pi_n = (1-\rho)\rho^n, \quad n = 0,1,2,\ldots

Stationary probabilities (M/M/1)

L = \frac{\rho}{1-\rho} = \frac{\lambda}{\mu-\lambda}

Mean number in system

W = \frac{L}{\lambda} = \frac{1}{\mu-\lambda}

Mean time in system (Little's Law)

L = \lambda W

Little's Law (universal)

Notation

Notation	Meaning
$\lambda$	Arrival rate (customers per unit time)
$\mu$	Service rate (customers served per unit time)
$\rho = \lambda/\mu$	Traffic intensity (utilization)
$L$	Mean number of customers in the system
$W$	Mean time a customer spends in the system

Theorems

Theorem 1: Little's Law

\text{For any stable queuing system, the mean number in the system } L \text{, the average arrival rate } \lambda \text{, and the mean time in system } W \text{ satisfy:} \quad L = \lambda W.

Theorem 2: M/M/1 Stationary Distribution

\text{The M/M/1 queue with traffic intensity } \rho = \lambda/\mu < 1 \text{ has unique stationary distribution } \pi_n = (1-\rho)\rho^n \text{ (geometric), with mean queue length } L = \rho/(1-\rho).

Theorem 3: Pollaczek-Khinchine Mean Value Formula (M/G/1)

\text{For an M/G/1 queue (Poisson arrivals, general service time B with mean } 1/\mu \text{ and second moment } \mathbb{E}[B^2]\text{):} \quad L = \rho + \frac{\rho^2 + \lambda^2 \mathbb{E}[B^2]}{2(1-\rho)}.

Worked Examples

1
Compute utilization: rho = lambda / mu = 3/5 = 0.6.
$\rho = \frac{3}{5} = 0.6$
2
Mean number in system: L = rho/(1-rho) = 0.6/0.4 = 1.5.
$L = \frac{\rho}{1-\rho} = \frac{0.6}{0.4} = 1.5 \text{ customers}$
3
Mean time in system by Little's Law: W = L/lambda = 1.5/3 = 0.5 hours.
$W = \frac{L}{\lambda} = \frac{1.5}{3} = 0.5 \text{ hours} = 30 \text{ minutes}$

✓ Answer

rho = 0.6, L = 1.5 customers, W = 30 minutes.

Practice Problems

Mediumapplication

A checkout counter has Poisson arrivals at rate 4 customers/minute and exponential service at rate 6 customers/minute. Find P(queue length >= 3).

Mediumfree response

Explain intuitively and mathematically why a bank queue with 10 tellers each serving at rate mu is better (shorter waits) than 10 separate single-server queues, even with the same total service rate.

Common Mistakes

Common Mistake

Doubling arrival rate doubles the mean queue length

Due to the L = rho/(1-rho) formula, increasing rho from 0.5 to 0.9 (nearly doubling load) increases L from 1 to 9, a 9-fold increase. The relationship is highly nonlinear near saturation.

Common Mistake

Little's Law requires Poisson arrivals or exponential service times

Little's Law L = lambda W holds for any stable queuing system regardless of the arrival or service distribution.

Quiz

Historical Background

Agner Krarup Erlang founded queuing theory in 1909 while working for the Copenhagen Telephone Company, developing formulas for telephone traffic and operator staffing. His Erlang B and Erlang C formulas are still widely used in telecommunications. The M/M/1 queue was analyzed systematically by Pollaczek in the 1930s. Little's Law was conjectured by P.M. Morse in 1958 and proved by John Little in 1961. The M/G/1 queue and the Pollaczek-Khinchine formula were developed in the 1930s-1950s.

1909
Erlang develops the first queuing formulas for telephone traffic
Agner Krarup Erlang
1930s
Pollaczek analyzes M/M/1 and M/G/1 queues systematically
Felix Pollaczek
1961
Little proves the law L = lambda W in full generality
John Little

Summary

Queuing systems are characterized by arrival process, service distribution, and number of servers; M/M/1 is the baseline tractable model.
M/M/1 stationary distribution: pi_n = (1-rho)rho^n; mean number in system L = rho/(1-rho); mean time W = 1/(mu-lambda).
Little's Law L = lambda W is a universal identity for stable queuing systems, independent of distributional assumptions.
The Pollaczek-Khinchine formula extends M/M/1 to M/G/1: mean queue length depends on the second moment of service time.

References

BookRoss, S. -- Introduction to Probability Models, Chapter 8
BookKleinrock, L. -- Queuing Systems, Volume 1
WebsiteWikipedia -- Queuing theory