Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 38 · Networks of Queues

Jackson Networks and the Traffic Equations

Solve open networks of M/M/c queues with probabilistic routing: set up the traffic equations, check stability and use the product-form result to compute delays.

A Jackson network generalizes the tandem line. Customers can enter from outside at any node, move between nodes at random, loop back to nodes they visited, and leave. This models hospitals with referrals and re-visits, data centers with request fan-out, and manufacturing lines with rework.

The setup

An open Jackson network has m nodes. Each node i is an M/M/1 queue (or M/M/c) with service rate μ_i, FCFS. Customers arrive from outside to node i as a Poisson stream with rate γ_i. After finishing at node i, a customer goes to node j with probability P_ij, and leaves the network with probability 1 - Σ_j P_ij.

Because of feedback, the arrival stream into a node is not Poisson in general. Surprisingly, the steady-state analysis still works as if each node were an independent M/M/1 queue.

Traffic equations

Let λ_i be the total arrival rate into node i (outside plus internal). In steady state, flow in equals flow out at each node, so:

Text
λ_i = γ_i + Σ_j λ_j P_ji        for i = 1..m

In matrix form, λ = γ + Pᵀ λ, so (I - Pᵀ) λ = γ. Solve this linear system for λ. A unique non-negative solution exists whenever customers eventually leave (the routing matrix is substochastic and the network is "open").

Python Solve the traffic equations with numpy

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.

Check the answer by hand for node 1: λ_1 = 2 + 0.3 λ_3. The solver handles loops like 1 → 3 → 1 for you.

Jackson's theorem

If every node satisfies ρ_i = λ_i / μ_i < 1, the steady-state distribution of the vector (N_1, ..., N_m) is the product form:

Text
P(n_1, ..., n_m) = Π (1 - ρ_i) ρ_i^(n_i)

So the nodes behave like independent M/M/1 queues with arrival rates λ_i. Each node has L_i = ρ_i/(1 - ρ_i).

The mean number of customers in the whole network is L = Σ L_i. Little's Law applied to the whole network gives the mean time a customer spends in it:

Text
W = L / Σ γ_i

Only the external arrival rate belongs in the denominator.

Python Network delay and per-node numbers

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 last two lines agree: total time equals visits times time per visit at each node, summed over nodes.

Multi-server nodes

Jackson's theorem also holds when node i has c_i servers (M/M/c), with the same traffic equations. Each node's marginal is then the M/M/c distribution with arrival rate λ_i, and stability needs λ_i < c_i μ_i.

Jackson's product form needs exponential service, FCFS (or another symmetric rule), Poisson external arrivals, and infinite buffers. Finite buffers or non-exponential service break it. When that happens, networks are usually evaluated by approximations (decomposition) or simulation.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the traffic equations λ_i = γ_i + Σ_j λ_j P_ji, what does γ_i stand for?

    γ_i is the Poisson rate of arrivals from outside the network.
  2. 2. In Little's Law for the whole open network, which arrival rate do we use?

    A customer is counted once when it enters the network. Internal transfers would count the same customer several times.
  3. 3. What does Jackson's theorem say about the joint distribution of node counts?

    Each node behaves as if independent and M/M/1 with its total arrival rate λ_i.
  4. 4. A node with λ_i = 5 and μ_i = 5 makes the network

    Stability requires ρ_i < 1 at every node.

Summary

  • Open Jackson network: Poisson outside arrivals, exponential servers, random routing.
  • Traffic equations: (I - Pᵀ) λ = γ.
  • Product form: each node acts like an independent M/M/1 queue with rate λ_i.
  • W = (Σ L_i) / Σ γ_i, using only external arrivals.

Next: Closed Networks and Mean Value Analysis