In queueing theory, a discipline within the mathematical theory of probability, a Jackson network (sometimes Jacksonian network) 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, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’
Jackson was inspired by the work of Burke and Reich, 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".
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).
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 and state-dependent. 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.
In an open network, jobs arrive from outside following a Poisson process with rate . Each arrival is independently routed to node j with probability and . Upon service completion at node i, a job may go to another node j with probability or leave the network with probability .
Hence we have the overall arrival rate to node i, , including both external arrivals and internal transitions:
Define , then we can solve .
All jobs leave each node also following Poisson process, and define as the service rate of node i when there are jobs at node i.
Let denote the number of jobs at node i at time t, and . Then the equilibrium distribution of , is determined by the following system of balance equations:
where denote the unit vector.
Suppose a vector of independent random variables with each having a probability mass function as
where . If i.e. is well defined, then the equilibrium distribution of the open Jackson network has the following product form:
for all .⟩
This theorem extends the one shown on Jackson's Theorem page by allowing state-dependent service rate of each node. It relates the distribution of by a vector of independent variable .
Suppose we have a three-node Jackson shown in the graph, the coefficients are:
Then by the theorem, we can calculate:
According to the definition of , we have:
Hence the probability that there is one job at each node is:
Since the service rate here does not depend on state, the s simply follow a geometric distribution.
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.
Under some mild conditions the queue-length process[clarification needed] of an open generalized Jackson network can be approximated by a reflected Brownian motion defined as , where is the drift of the process, is the covariance matrix, and is the reflection matrix. This is a two-order approximation obtained by relation between general Jackson network with homogeneous fluid network and reflected Brownian motion.
The parameters of the reflected Brownian process is specified as follows:
where the symbols are defined as:
|a J-vector specifying the arrival rates to each node.|
|a J-vector specifying the service rates of each node.|
|effective arrival of node.|
|variation of service time at node.|
|variation of inter-arrival time at node.|
|coefficients to specify correlation between nodes.|
||This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (June 2012)|
- 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.
- Kelly, F. P. (Jun 1976). "Networks of Queues". Advances in Applied Probability 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.
- 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.
- Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213.
- Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.
- Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.
- 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.
- 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.
- 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.
- 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.
- Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.