Jackson network

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network (sometimes Jacksonian network[1]) is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. 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 networks were first identified by James R. Jackson[4][5] and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’[6]

Jackson was inspired by the work of Burke and Reich,[7] though Jean 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".[8]

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).[9]

A Jackson network consists of a number of nodes, where each node represents a queue in which the service rate can be both node-dependent (different nodes have different service rates) and state-dependent (service rates change depending on queue lengths). Jobs travel among the nodes following a fixed routing matrix. All jobs at each node belong to a single "class" and jobs follow the same service-time distribution and the same routing mechanism. Consequently, there is no notion of priority in serving the jobs: all jobs at each node are served on a first-come, first-served basis.

Jackson networks where a finite population of jobs travel around a closed network also have a product-form solution described by the Gordon–Newell theorem.[10]

  1. ^ Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR 1426753.
  2. ^ Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.
  3. ^ Jackson, James R. (December 2004). "Comments on "Jobshop-Like Queueing Systems": The Background". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046150.
  4. ^ Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213. A version from January 1963 is available at http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf Archived 2018-04-12 at the Wayback Machine
  5. ^ Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.
  6. ^ Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.
  7. ^ Reich, Edgar (September 1957). "Waiting Times When Queues are in Tandem". Annals of Mathematical Statistics. 28 (3): 768. doi:10.1214/aoms/1177706889. JSTOR 2237237.
  8. ^ Walrand, Jean (November 1983). "A Probabilistic Look at Networks of Quasi-Reversible Queues". IEEE Transactions on Information Theory. 29 (6): 825. doi:10.1109/TIT.1983.1056762.
  9. ^ Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics. 6 (4): 382–384. doi:10.1093/imaman/6.4.382.
  10. ^ Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.