Queueing Theory: The M/M/1 Queue and Little's Law

Core Idea

Queueing theory models systems where customers arrive, wait and are served. In the M/M/1 queue, arrivals form a Poisson process with rate λ, service times are independent exponential random variables with rate μ, and there is a single server. The number in the system is then a birth-death continuous-time Markov chain. When the traffic intensity ρ = λ/μ is less than 1, the queue has stationary distribution πₙ = (1 - ρ)ρⁿ, with mean number in system L = ρ/(1 - ρ) and mean time in system W = 1/(μ - λ). Little's law, L = λW, links averages in very general queueing systems.

How It's Best Learned

Draw the state diagram 0, 1, 2, ... with arrows at rate λ to the right and rate μ to the left, and solve the balance equations across each cut between neighboring states. Tabulate L for ρ = 0.5, 0.8, 0.9 and 0.95 to see the sharp growth as ρ approaches 1. Then justify Little's law with the picture of total waiting time as an area under the number-in-system curve, and apply it to compute waiting times from queue lengths.

Common Misconceptions

• A server that is busy 90% of the time has a little spare capacity, so queues stay short. (In an M/M/1 queue with ρ = 0.9, the mean number in system is 0.9/0.1 = 9, and it grows without bound as ρ → 1.)
• A queue is stable as long as λ ≤ μ. (With λ = μ the M/M/1 queue has no stationary distribution; stability requires λ < μ.)
• Little's law holds only for M/M/1 queues. (L = λW holds for a broad class of stable systems, whatever the arrival and service distributions or the queue discipline.)

Explainer

Queues appear in call centers, computer networks, hospitals and checkout lines. The simplest model that captures their main effects is the M/M/1 queue. In Kendall's notation, the first M means Markovian (Poisson) arrivals, the second M means Markovian (exponential) service times, and 1 is the number of servers.

Let N(t) be the number of customers present, including the one in service. Because exponential times are memoryless, N(t) is a continuous-time Markov chain. From state n it moves up to n + 1 at rate λ (an arrival) and, if n ≥ 1, down to n - 1 at rate μ (a departure). This is a birth-death process.

For a stationary distribution π, the flow across the cut between states n and n + 1 must balance: λπₙ = μπₙ₊₁. Writing ρ = λ/μ, this gives πₙ = ρⁿπ₀. The probabilities must sum to 1, which is possible only if ρ < 1, and then π₀ = 1 - ρ. So

πₙ = (1 - ρ)ρⁿ, n = 0, 1, 2, ...,

a geometric distribution. The server is idle a fraction 1 - ρ of the time, which is why ρ is called the utilization.

The mean number in the system is L = ρ/(1 - ρ). This formula explains a lot of everyday frustration. At ρ = 0.5, L = 1. At ρ = 0.8, L = 4. At ρ = 0.9, L = 9, and at ρ = 0.95, L = 19. Raising utilization from 90% to 95% roughly doubles the queue. On average the server keeps up, so this congestion comes from random fluctuations in arrivals and service.

Little's law connects queue lengths to waiting times. If customers arrive at long-run rate λ and each spends an average time W in the system, then the long-run average number present is L = λW. The idea is to add up total customer-time in two ways: as the area under N(t), or as the sum of individual stays. The law holds for a wide class of stable systems. For the M/M/1 queue it gives W = L/λ = 1/(μ - λ). With λ = 8 and μ = 10 per hour, W = 30 minutes, of which 6 minutes on average is service and 24 minutes is waiting in line.

The same method extends to multiple servers (M/M/c), finite waiting rooms and networks of queues. In heavy traffic, when ρ is close to 1, a suitably rescaled queue-length process is approximated by reflected Brownian motion.