Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 · Networks of Queues

Tandem Queues and Burke's Theorem

Chain M/M/1 queues in series and see why each behaves independently: Burke's theorem says the departures of a stable M/M/1 queue are Poisson.

Customers rarely visit just one server. A patient registers, sees a nurse, then a doctor. A packet crosses several routers. A burger goes through the grill, the assembly station and the till. The simplest network is a tandem line: customers pass through queue 1, then queue 2, and so on.

At first glance this looks hard: the output of queue 1 becomes the input of queue 2, and that output is shaped by the congestion of queue 1. Yet for exponential servers a beautiful theorem makes the analysis almost trivial.

Burke's theorem

Consider a stable M/M/1 queue with arrival rate λ and service rate μ > λ, in steady state. Burke's theorem states:

  1. The departure process is a Poisson process with rate λ (not μ).
  2. The number in the system at time t is independent of the departures before t.

The first part is surprising. The departures are bunched when the server is busy and absent when it is idle, yet statistically they look exactly like the arrivals. Intuitively, in the long run every customer who enters must leave, so the rate is λ; the theorem says the pattern of times is also Poisson.

The full proof uses time reversal: a stationary birth-death chain looks the same run backwards, so the reversed process has arrivals at rate λ in the same way, and these reversed arrivals are the original departures.

Tandem line consequences

Put two M/M/1 queues in series: arrivals λ to server 1 (rate μ_1), departures go straight to server 2 (rate μ_2). By Burke, queue 2 sees a Poisson stream of rate λ. Moreover, the number in queue 1 at a given time is independent of queue 2's past input, so in steady state:

Text
P(N1 = n1, N2 = n2) = (1 - ρ1) ρ1^n1 · (1 - ρ2) ρ2^n2

with ρ_i = λ / μ_i. The joint distribution is the product of two M/M/1 distributions. So each stage can be analyzed alone.

For a line of m stations:

Text
L = Σ ρ_i / (1 - ρ_i),    W = L / λ = Σ 1/(μ_i - λ)
Python Mean time in a tandem line

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the slowest stage (μ = 4, the highest utilization) dominates both the mean number and the mean time. Improving that bottleneck gives the biggest gain.

What Burke does not say

Burke's theorem describes the departure stream of one stable M/M/1 queue in steady state. Be careful:

  • If service at stage 1 is not exponential, departures are generally not Poisson, and the product form fails.
  • Waiting times of the same customer at the two stages are not independent: a customer who waits long at queue 1 and has a long service tends to arrive at queue 2 as part of a bunch. Only the queue lengths at a fixed time are independent.
  • In a tandem line with blocking (finite buffer between stages) the product form also breaks.
Python Departures of an M/M/1 queue have rate lambda (simulation)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The departure rate comes out near λ = 2, not μ = 3, and the squared coefficient of variation of the gaps is close to 1, as for a Poisson stream.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A stable M/M/1 queue has arrival rate 4 and service rate 6. What is the departure rate in steady state?

    Everything that enters eventually leaves, so the long-run departure rate equals the arrival rate, 4. Burke adds that the stream is Poisson.
  2. 2. In a two-station M/M/1 tandem line, the joint distribution of (N1, N2) is

    By Burke's theorem, N1 and N2 are independent with geometric (M/M/1) distributions.
  3. 3. Which stage of a tandem line dominates the mean time?

    The term 1/(μ_i - λ) is largest for the smallest service rate.
  4. 4. Burke's theorem can fail if

    The theorem relies on exponential service (reversibility). Non-exponential service gives non-Poisson departures.

Summary

  • Burke: departures from a stable M/M/1 queue form a Poisson process with the arrival rate.
  • Tandem M/M/1 queues are independent in steady state; the joint distribution is a product.
  • W = Σ 1/(μ_i - λ); the bottleneck dominates.
  • The result needs exponential service and infinite buffers.

Next: Jackson Networks