This is the user sandbox of Ygh929. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.
Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!
In queueing theory, Jackson network is a kind of networks where Jackson's theorem or its extensions can be applied. A Jackson network consists of J nodes. Each node can be considered as a M/M/1 queue and the service rate at eac node i can be both node-dependent and state-dependent. Jobs travel among the nodes following a routing matrix .
All jobs at each node belong to a single "class": All 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.
According to different specifications of the routing matrix, there are three different variations: the open, close and semi-open networks.
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:
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 .⟩
Proof
It suffices to verify equation is satisfied. By the product form and formula (3), we have:
Substituting these into the right side of we get:
Then use , we have:
Substituting the above into , we have:
This can be verified by . Hence both side of are equal.⟨
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 .
In some applications once a job leaves the network, a new job is immediately released into the network. This type of network can be viewed as having a fixed number of jobs in the network, with no job ever leaving the network and no external job entering the network. In this sense, the network is "closed". It is also referred to as Gordon-Newell network
In closed Jackson network, and are 0 for all i and j., and for each row. Let be the solution to
The solution is not unique so we need to add another equation. For example for some constant or for some .
The equilibrium balance equations are given by:
for all such that . Similarly, define and where and are defined before.
Semi-open net work has features of both open and closed networks: it follows the descriptions of the open model with the exception that the total number in the network is limited to a maximum of K jobs at any time.
It turns out that the semiopen model can be reduced to a closed network with K jobs and J+1 nodes. The additional node, indexed as node 0, represents the external world. Its service rate is defined as if and . This captures the blocking of the external arrivals when the buffer is full.
Set and , then they are solutions to the set of equations:
It is same as the one described in for a J+1 closed work.
In generalized Jackson network, arrival processes can be renewal process that is not Poisson, and i.i.d. service time that needs not follow exponential distribution. The stationary distribution of generalized Jackson network usually does not have an explicit analytical form.
Under some mild conditions the queue-length process of a 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:
with
where the symbols are defined as:
Definitions of symbols in the approximation formula
symbol
Meaning
a J-vector specifying the arrival rates to each node.
a J-vector specifying the service rates of each node.
routing matrix.
effective arrival of node.
variation of service time at node.
variation of inter-arrival time at node.
coefficients to specify correlation between nodes.
They are defined in this way: Let be the arrival process of the system, then in distribution, where is a driftless Brownian process with covariate matrix , with , for any
Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN0-387-95166-0.
Jackson, James R. (Oct. 1963). "Jobshop-like Queueing Systems". Management Science 10 (1): 131–142. DOI:10.1287/mnsc.1040.0268. JSTOR 2627213
William J. Gordon and Gordon F. Newell (1967) Closed queueing systems with exponential servers in Operations Research 15 (2), 254–65
Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics 6 (4): 382–384.