Jackson's theorem (queueing theory)

In queueing theory, a discipline within the mathematical theory of probability Jackson's theorem is a theorem by James R. Jackson.^[1] It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product form solutions in other networks has been the subject of much research,^[2] including ideas used in the development of the Internet.^[3] The paper was printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’^[4]

Jackson was inspired by the work of Burke and Reich, though Walrand notes "product form results … [are] a much less immediate result of the output theorem than Jackson himself appeared to believe in his fundamental paper".^[5]

Definition of a Jackson network

A network of m interconnected queues is known as a Jackson network if it meets the following conditions:

1. the network is open and any external arrivals to node i form a Poisson process,
2. all service times are exponentially distributed and the service discipline at all queues is FCFS,
3. a customer completing service at queue i will either move to some new queue j with probability ${\displaystyle P_{ij}}$  or leave the system with probability ${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$ , which is non-zero for some subset of the queues,
4. the utilization of all of the queues is less than one.

Theorem

In an open Jackson network of m M/M/1 queues where the utilization ${\displaystyle \rho _{i}}$  is less than 1 at every queue, the equilibrium state probability distribution exists and for state ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$  is given by the product of the individual queue equilibrium distributions

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}$ 

The result ${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$  also holds for M/M/c model stations with c_i servers at the ${\displaystyle i^{th}}$  station, with utilization requirement ${\displaystyle \rho _{i}<c_{i}}$ .

Generalized Jackson network

A generalized Jackson network allows renewal arrival processes that need not be Poisson processes, and independent, identically distributed non-exponential service times. In general, this network does not have a product form stationary distribution, so approximations are sought.^[6]

See also

• Gordon–Newell network
• BCMP network
• G-network
• Little's law

Notes

1. Jobshop-like Queueing Systems James R. Jackson in Management Science, Vol. 10, No. 1 (Oct., 1963), pp. 131-142
2. Networks of Queues F. P. Kelly in Advances in Applied Probability, Vol. 8, No. 2 (Jun., 1976), pp. 416-432
3. Comments on "Jobshop-Like Queueing Systems": The Background James R. Jackson in Management Science, Vol. 50, No. 12, Ten Most Influential Titles of Management Sciences First Fifty Years (Dec., 2004), p. 1803
4. Jobshop-like Queueing Systems James R. Jackson in Management Science, Vol. 50, No. 12, Ten Most Influential Titles of Management Sciences First Fifty Years
5. Walrand, Jean (1983). "A Probabilistic Look at Networks of Quasi-Reversible Queues". IEEE Transactions on Information Theory. 29 (6). doi:10.1109/TIT.1983.1056762. {{cite journal}}: Unknown parameter |month= ignored (help)
6. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization by Hong Chen, David D. Yao Published by Springer, 2001 ISBN 0387951660, 9780387951669