Jackson's theorem (queueing theory): Difference between revisions

Revision as of 12:49, 20 July 2012

Latest revision as of 13:01, 20 July 2012

Line 1:

{{merge to|#REDIRECT[[Jackson network|July 2012}}]]

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]] '''Jackson's theorem''' is a theorem by [[James R. Jackson]].<ref name="jackson">{{cite journal|title=Jobshop-like Queueing Systems|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=10|number=1|month=Oct.|year=1963|pages=131–142|doi=10.1287/mnsc.1040.0268|jstor=2627213}}</ref> It was the first significant development in the theory of [[queueing theory|networks of queues]], and generalising and applying the ideas of the theorem to search for similar [[product form solution]]s in other networks has been the subject of much research,<ref>{{cite journal|title=Networks of Queues|authorlink=F. P. Kelly|first=F. P.|last=Kelly|journal=Advances in Applied Probability|volume=8|number=2|month=Jun.|year=1976|pages=416–432|jstor=1425912}}</ref> including ideas used in the development of the Internet.<ref>{{cite journal|title=Comments on "Jobshop-Like Queueing Systems": The Background|first=James R.|last=Jackson|journal=|[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|number=12|month=December|year=2004|pages=1796–1802|jstor=30046150}}</ref> The paper was re-printed in the journal [[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’<ref>{{cite journal|title=Jobshop-Like Queueing Systems|first=James R.|last=Jackson|journal=|[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|number=12|month=December|year=2004|pages=1796–1802|jstor=30046149}}</ref>

Jackson was inspired by the work of [[Burke's theorem|Burke]] and Reich,<ref>{{cite journal|title=Waiting Times When Queues are in Tandem|journal=[[Annals of Mathematical Statistics]]|volume=28|number=3|month=September|year=1957|first=Edgar|last=Reich|doi=10.1214/aoms/1177706889|jstor=2237237}}</ref> 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".<ref>{{cite journal|title=A Probabilistic Look at Networks of Quasi-Reversible Queues|journal=[[IEEE Transactions on Information Theory]]|volume=29|number=6|month=November|year=1983|first=Jean|last=Walrand|doi=10.1109/TIT.1983.1056762}}</ref>

An earlier [[product form solution]] was found by R. R. P. Jackson for tandem queues (a finite chain of queues where each customer must visit each queue in order) and cyclic networks (a loop of queues where each customer must visit each queue in order).<ref>{{cite journal|title=Book review: Queueing networks and product forms: a systems approach|first=R. R. P.|last=Jackson|doi=10.1093/imaman/6.4.382|year=1995|volume=6|number=4|pages=382–384|journal=IMA Journal of Management Mathematics}}</ref>

==Definition of a Jackson network==

{{Main|Jackson network}}

A network of ''m'' interconnected queues is known as a '''Jackson network'''<ref>{{cite jstor|3213702}}</ref> or '''Jacksonian network'''<ref>{{cite jstor|1426753}}</ref> if it meets the following conditions:

# the network is open and any external arrivals to node ''i'' form a [[Poisson process]],

# all service times are exponentially distributed and the service discipline at all queues is [[first-come, first-served]],

# a customer completing service at queue ''i'' will either move to some new queue ''j'' with probability <math>P_{ij}</math> or leave the system with probability <math>1-\sum_{j=1}^{m}P_{ij}</math>, which is non-zero for some subset of the queues,

# the [[utilization]] of all of the queues is less than one.

==Theorem==

In an open Jackson network of ''m'' [[M/M/1 model|M/M/1 queues]] where the [[utilization]] <math>\rho_i</math> is less than 1 at every queue, the equilibrium state probability distribution exists and for state <math>\scriptstyle{(k_1,k_2,\ldots,k_m)}</math> is given by the product of the individual queue equilibrium distributions

:<math>\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)].</math>

The result <math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i)</math> also holds for [[M/M/c model]] stations with ''c''_''i'' servers at the <math>i^\text{th}</math> station, with utilization requirement <math>\rho_i < c_i</math>.

==Generalized Jackson network==

A '''generalized Jackson network''' allows [[renewal process|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 solution|product form stationary distribution]], so approximations are sought.<ref>{{cite book|title=Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization|first1=Hong|last1=Chen|first2=David D.|last2=Yao|publisher=Springer|year=2001|isbn=0-387-95166-0}}</ref>

==See also==

*[[Gordon–Newell network]]

*[[BCMP network]]

*[[G-network]]

*[[Little's law]]

==Notes==

{{Reflist}}

{{Queueing theory}}

[[Category:Stochastic processes]]

[[Category:Probability theorems]]

[[Category:Queueing theory]]

[[nl:Jackson-netwerk]]