Jackson's theorem (queueing theory)

This redirect is about James Jackson's theorem in queueing theory. For Dunham Jackson's inequality in analysis, see Jackson's inequality.

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]

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 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})].}$ 

Generalized Jackson network

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

See also

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

References

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. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization by Hong Chen, David D. Yao Published by Springer, 2001 ISBN 0387951660, 9780387951669