Queueing Networks

A queueing network links several service stations so that customers leaving one station route to another; remarkably, many such networks have a product-form equilibrium that factorises across stations.

Definition

A queueing network is a collection of interconnected service stations through which customers move according to routing probabilities, and its analysis seeks the joint stationary distribution of the numbers at all stations, which under broad conditions factorises into a product of single-station terms.

Scope

This topic covers open and closed networks of queues, routing probabilities and traffic equations, Jackson's theorem on the product-form stationary distribution of open Markovian networks, the BCMP extension to multiple customer classes and service disciplines, the arrival theorem and mean-value analysis for closed networks, and quasi-reversibility as the structural reason for product form.

Core questions

• How do routing probabilities determine the effective arrival rate at each station?
• When does the joint stationary distribution factorise into a product over stations?
• How do closed networks with a fixed customer population differ from open ones?
• What structural property of stations guarantees product form?

Key theories

Jackson's product-form theorem

In an open network of exponential single-server queues with Markovian routing, the stationary distribution is the product of geometric distributions whose parameters come from the solution of the traffic equations, so the stations behave as if independent in equilibrium.

Quasi-reversibility and the BCMP theorem

Stations that are quasi-reversible compose into networks with product-form equilibria, and the BCMP theorem extends this to multiple customer classes and several service disciplines, greatly broadening the class of tractable networks.

Clinical relevance

Queueing networks model computer systems, communication and packet networks, flexible manufacturing, and supply chains, and the product-form theory and mean-value analysis provide efficient performance predictions of throughput, utilisation, and response time without simulating the full joint state space.

History

Jackson introduced open networks with product-form solutions in 1957, Gordon and Newell treated closed networks in 1967, the BCMP theorem of 1975 unified multiple classes and disciplines, and Kelly's 1979 monograph explained product form through reversibility, establishing the theory underlying computer-systems performance analysis.

Key figures

• James Jackson
• Frank Kelly
• Forest Baskett
• Mani Chandy

Seminal works

• kelly1979
• jackson1957

Frequently asked questions

What is a product-form network?

It is a queueing network whose equilibrium distribution factorises into a product of terms, one per station, so the stations appear statistically independent in steady state even though customers flow between them.

What is the difference between open and closed networks?

An open network has external arrivals and departures so the customer population fluctuates, while a closed network circulates a fixed number of customers among the stations with no entries or exits.