THE GOLD STANDARD OF QUEUEING THEORY
Find your route through this guide
Product form is powerful because a network that is coupled by routing can sometimes have a stationary distribution that factors into node-level terms. The factorisation is not magic and it is not a licence to pretend the queues are independent at every time. It comes from a balance structure that must survive the arrival process, service discipline, routing and stability conditions.
Quasi-reversibility is the useful local idea. A node can expose arrival and departure behaviour that allows it to be connected into a network while retaining a tractable stationary description, even when the node is not fully reversible in every internal detail.
This guide starts with a two-node open network, solves its traffic equations, calculates the stationary queue-length factors, changes the routing and service assumptions, and shows exactly where the convenient departure-process story stops.
- State the node model and service discipline before using a product form.
- Solve traffic equations before computing utilisation.
- Check every node has load below capacity.
- Distinguish stationary factorisation from pathwise independence.
- Rebuild the argument after blocking, priorities or non-Poisson inputs.
Five reading routes
Understand the local property · Chapters 1–3
Define reversibility, quasi-reversibility and partial balance without hiding the conditioning.
Build the network · Chapters 4–6
Solve traffic equations and calculate the product form for a two-node example.
Interpret departures · Chapters 7–8
Use Poisson-departure results only at the level justified by the node theorem.
Transfer and stress-test · Chapters 9–11
Change routing, service law and capacity, then inspect what survives.
Check limits and continue · Chapter 12
Use the final checklist, FAQs and verified specialist routes.
Chapter contents
Chapters 1–4
Chapters 5–8
Chapters 9–12
CHAPTER 1 OF 13
1. Begin with the question product form actually answers
A stationary distribution answers how likely the network is to occupy each state after transients have died away, assuming a stationary regime exists. Product form means this distribution can be written as a normalised product of simpler factors, often one factor per node. It does not say that the histories of the nodes are independent, nor that a downstream arrival never depends on an upstream completion.
The practical question is therefore narrow and valuable: can we compute long-run queue-length probabilities and related means without solving one enormous global balance system? The answer depends on local balance properties, network routing and stability. Start there rather than starting from a memorised formula.
- Name the stationary state vector.
- Name the node discipline and service law.
- Write exogenous arrival rates and routing probabilities.
- Check the network is open or closed.
- Separate stationary claims from transient claims.
CHAPTER 2 OF 13
2. Separate full reversibility from quasi-reversibility
A stationary Markov process is reversible when its time-reversed process has the same probabilistic law. Detailed balance is a familiar sufficient expression: flow between each pair of states balances in both directions. Queueing nodes often need a weaker property.
Quasi-reversibility controls how the node looks at its boundary. Roughly, the state at a fixed time has the independence relationships with past departures and future arrivals needed for network composition. The exact definition belongs to the chosen model; the safe operational rule is to cite the node theorem rather than infer quasi-reversibility from a smooth-looking output trace.
| Property | What it controls | What it does not guarantee |
|---|---|---|
| Reversibility | Whole stationary path under time reversal | Realistic service assumptions |
| Quasi-reversibility | Boundary flows and stationary node state | Full pathwise independence |
| Partial balance | Aggregated stationary flows | Pairwise detailed balance |
| Product form | Factorised stationary probabilities | Transient factorisation |
CHAPTER 3 OF 13
3. Use partial balance as the mechanism, not a slogan
Global balance says total stationary flow into each state equals total flow out. Detailed balance pairs every transition with its reverse. Partial balance groups transitions so that the grouped flows balance even when individual pairs do not. Many product-form proofs exploit this middle structure.
When reading a proof, identify the transition group: external arrivals, service completions, class changes or routing moves. If the proposed factor cancels terms only because a service rate or routing probability has a special form, that form is part of the contract. It must appear in the article’s limits.
Evidence check: point to the exact balance relation that makes the node factor work. A factorisation verified only by numerical coincidence is not a transferable theorem.
CHAPTER 4 OF 13
4. Solve traffic equations before touching queue formulas
Let v_i be the total effective arrival rate to node i. In an open Markovian network, v_i equals the exogenous arrival rate plus routed flow from every other node. These linear traffic equations count visits, not distinct customers: one customer may contribute several visits after feedback.
A solution with v_i at or above service capacity invalidates the usual stationary M/M/1 factor at that node. Traffic equations may still have an algebraic solution while the stochastic network is unstable, so flow conservation and stability are separate checks.
| Input | Symbol | Role |
|---|---|---|
| External arrivals | e_i | New customers entering node i |
| Routing probability | p_ji | Fraction leaving j and entering i |
| Effective rate | v_i | All visits to node i |
| Service capacity | μ_i | Maximum exponential completion rate |
| Load | ρ_i=v_i/μ_i | Stationary M/M/1 requires ρ_i<1 |
CHAPTER 5 OF 13
5. Worked example: a two-node open network with feedback
Customers enter node A at 4 per hour. After service at A, 60% go to B and 40% leave. After service at B, 25% return to A and 75% leave. The traffic equations are v_A = 4 + 0.25v_B and v_B = 0.60v_A.
Substitution gives v_A = 4 + 0.15v_A, so v_A = 4/0.85 = 4.7059 visits per hour. Then v_B = 2.8235 visits per hour. These are visit rates; the external customer rate remains 4 per hour.
With exponential service capacities μ_A=8 and μ_B=6 per hour, the loads are ρ_A=0.5882 and ρ_B=0.4706. Both are below one, so the open Jackson-network stationary calculation is admissible.
| Quantity | Node A | Node B |
|---|---|---|
| Effective arrival rate | 4.7059/h | 2.8235/h |
| Service capacity | 8/h | 6/h |
| Utilisation | 0.5882 | 0.4706 |
| Mean M/M/1 number ρ/(1−ρ) | 1.4286 | 0.8889 |
CHAPTER 6 OF 13
6. Build and check the stationary product
For this two-node M/M/1 Jackson network, the stationary probability of state (n_A,n_B) is (1−ρ_A)(1−ρ_B)ρ_A^{n_A}ρ_B^{n_B}. The mean total number in the two queues is therefore 1.4286+0.8889=2.3175.
Check normalisation one node at a time: each geometric series sums to one because its load is below one. Then check one or two global balance equations numerically. A correct formula should survive both the algebraic derivation and a direct substitution audit.
The product says the node counts are independent in the stationary distribution under this model. It does not say successive observations are independent, that routed arrivals are independent of upstream events at arbitrary epochs, or that the factorisation persists after a discipline change.
Changed-context check: if μ_B drops from 6 to 3 per hour, ρ_B becomes 0.9412 and its mean rises to 16. The algebra still normalises, but the approximation becomes operationally fragile and highly sensitive to small rate errors.
CHAPTER 7 OF 13
7. Connect Burke’s theorem to the wider node idea
For a stationary M/M/1 queue with Poisson input and load below one, Burke’s theorem gives a Poisson departure process with the same rate as the input, together with a specific independence statement. That result explains why a tandem of such nodes can remain analytically tractable.
Quasi-reversibility is broader: it identifies nodes that can participate in network product forms under stated conditions. The conclusion must be read at the theorem’s level. Observing an approximately exponential interdeparture histogram is not enough to prove the required independence, and superposing or filtering flows can alter what an observer sees.
| Claim | Safe when | Common overreach |
|---|---|---|
| Poisson departures | The node theorem’s stationary assumptions hold | Any busy queue has Poisson output |
| Same departure rate | Stable flow conservation applies | Finite-window counts match exactly |
| Node composition | Quasi-reversible boundary conditions hold | Internal path is fully reversible |
| Network product form | Every node and routing rule meet the network theorem | Any connected queues factorise |
CHAPTER 8 OF 13
8. Know what BCMP-type generalisations change
Product form is not limited to identical single-class FCFS exponential servers. BCMP networks admit several service-centre types and multiple classes under discipline-specific conditions. The point is not to memorise a list without context; it is to recognise that service-time insensitivity, class dependence and scheduling are coupled.
For example, processor sharing and infinite-server nodes can support broader service-time distributions than a standard FCFS node, while FCFS product-form conditions are more restrictive. If a real node mixes priorities, setup times, batch service or state-dependent routing, match it to a theorem or model it directly.
- Record customer classes and route changes.
- Record whether service requirements depend on class.
- Record the discipline at each node.
- Check whether service-time shape matters or only its mean.
- Do not transplant an insensitivity claim between node types.
CHAPTER 9 OF 13
9. Transfer check: change routing without changing external demand
Suppose the return probability from B to A rises from 0.25 to 0.50 while the A-to-B probability remains 0.60. Then v_A = 4 + 0.50v_B and v_B=0.60v_A, giving v_A=5.7143 and v_B=3.4286. The external demand is unchanged, yet repeat visits increase both loads.
With the original service capacities, ρ_A=0.7143 and ρ_B=0.5714. The mean node counts become 2.5 and 1.3333, for a total of 3.8333. The stationary product-form structure survives because only the routing probabilities changed within the same Jackson contract; the numerical performance does not.
| Scenario | v_A | v_B | Mean total number |
|---|---|---|---|
| Original feedback 0.25 | 4.7059 | 2.8235 | 2.3175 |
| Higher feedback 0.50 | 5.7143 | 3.4286 | 3.8333 |
CHAPTER 10 OF 13
10. Test the network with simulation and departure diagnostics
A discrete-event simulation can audit the stationary calculation before it is used for planning. Warm up the model, collect node counts at fixed observation times, compare marginal histograms with the predicted geometric laws, and compare joint frequencies with the product.
For departures, inspect counts over several interval lengths, interdeparture distributions and dependence with the node state. A single dispersion index near one is not decisive. Use multiple seeds, confidence intervals and deliberately changed routing to verify that the code responds in the direction the equations predict.
- Preserve random seeds and event definitions.
- Separate warm-up from measurement.
- Compare marginals and joint states.
- Check flows at every network boundary.
- Report uncertainty, not just fitted lines.
CHAPTER 11 OF 13
11. State the failure modes that break easy composition
Finite buffers create blocking and couple upstream service to downstream capacity. Priorities can change class-level balance. Nonstationary arrivals remove the stationary setting. Correlated service times, common shocks, fork–join synchronisation, simultaneous resource requirements and state-dependent routing can destroy the local boundary property.
Even when an approximate product form performs well, label it as an approximation and test the decisions it supports. Mean queue length may be robust while high quantiles, class delays or blocking probabilities are not. Product form is a structural shortcut, not an immunity certificate.
| Departure from the model | Likely consequence | Repair route |
|---|---|---|
| Finite buffers | Blocking dependence | Finite-state Markov or simulation model |
| Priority service | Class coupling | Discipline-specific network theorem |
| Time-varying demand | No stationary distribution | Transient or fluid model |
| Fork–join tasks | Synchronisation | Joint-state or bounds analysis |
| Common shocks | Correlated nodes | Shared-environment model |
CHAPTER 12 OF 12
12. Preserve the proof contract and the operational evidence
A reusable record contains the state definition, node types, service disciplines, class rules, external arrival processes, routing matrix, traffic-equation solution, stability margins, stationary factors, theorem citation, simulation settings and every excluded feature.
Keep departure claims beside their conditioning. If a result is used for staffing or capacity, also keep sensitivity runs for rates, feedback and service variation. A small algebraic product can support a strong decision only when the evidence trail remains larger than the formula.
- Traffic equations and solved visit rates.
- Load and stability margin for every node.
- Exact theorem and node conditions.
- Worked balance and normalisation checks.
- Simulation, sensitivity and transfer results.
Contents · Previous chapter · Return to the Queueing Theory root
Frequently asked questions
Does product form mean queues are independent in real time?
No. It can imply independence of node counts in the stationary distribution while the time paths remain coupled by routing.
Is every M/M/1 node quasi-reversible?
The standard stationary M/M/1 queue under its usual assumptions has the relevant reversibility properties, but a changed discipline, arrival process or conditioning can alter the claim.
Can Poisson-looking departures prove Burke’s theorem applies?
No. The theorem needs model assumptions and independence statements that a histogram alone cannot establish.
Continue through the verified ecosystem
Start from the Queueing Theory root. Then use the Gold Standard of Education parent and the How X Works hub to carry the same evidence-and-transfer habit into other subjects.
- Burke’s Theorem, Reversibility and Poisson Departures — the single-node result that motivates the network route
- Heavy-Traffic Limits, State-Space Collapse and Diffusion Approximations — the near-capacity approximation route
- Lindley Recursion, GI/G/1 Workloads and Stability — the workload recursion route beyond exponential service
Authoritative sources
- Jackson — Jobshop-Like Queueing Systems — primary product-form analysis for open networks of waiting lines
- Kelly — Networks of Quasi-Reversible Nodes — primary discussion of quasi-reversibility and composable nodes
- Kelly — Reversibility and Stochastic Networks — author-hosted book source for reversibility and queueing-network structure
The two-node network, changed-feedback calculation and diagnostic sequence are original teaching examples. The cited sources establish the structural results; they do not validate a specific operational network.