User:Ygh929/sandbox

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Open Jackson network[edit]

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.

Theorem[edit]

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 .

Example[edit]

A three-node open Jackson network

Suppose we have a three-node Jackson shown in the graph, the coefficients are:


for all

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 doesn't depend on state, the simply follows geometric distribution.

Closed Jackson network[edit]

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.

Theorem[edit]

For all , we have:

Where follow the distribution in with is replaced by .⟩

This is an extension of Gordon-Newell theorem, where service rate can differ between states.

Example[edit]

A three-node closed Jackson network

We can modify the previous example a little to be a closed network with coefficients:

for all

Additionally, suppose there are totally 3 jobs in the network.

Set and solve , we get:

Hence we can know the distribution of :

This time, the probability that there is one job at each node is:

Semi-open Jackson Network[edit]

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.

Theorem[edit]

The semiopen Jackson network with an overall buffer capacity of K, has the following distribution: For all such that ,

where follows distribution in .⟩

Example[edit]

A semiopen three-node network

Suppose we have a semi-open network (consisting of nodes 1,2 and 3)with coefficients:


for all

and the number of jobs in the system is smaller than 4.

When the systme is not full, the arrival rate is

We can use node 0 to represent the out-side world, and its service rate is . Then we have a closed network with 4 jobs and coefficients:

for all

By setting and dividing by , we can calculate

Then we have

Then the probability that there is one job at each node is:

Generalized Jackson Network[edit]

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.

Approximation[edit]

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.

See also[edit]

References[edit]

  • Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-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.


Category:Stochastic processes Category:Probability theorems Category:Queueing theory