# User:Ygh929/sandbox

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 ${\displaystyle P}$.

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

In an open network, jobs arrive from outside following a Poisson process with rate ${\displaystyle \alpha >0}$. Each arrival is independently routed to node j with probability ${\displaystyle p_{0j}\geq 0}$ and ${\displaystyle \sum _{j=1}^{J}p_{0j}=1}$. Upon service completion at node i, a job may go to another node j with probability ${\displaystyle p_{ij}}$ or leave the network with probability ${\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}$.

Hence we have the overall arrival rate to node i, ${\displaystyle \lambda _{i}}$, including both external arrivals and internal transitions:

${\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)}$

Define ${\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}$, then we can solve ${\displaystyle \lambda =(I-P')^{-1}a}$.

All jobs leave each node also following Poisson process, and define ${\displaystyle \mu _{i}(x_{i})}$ as the service rate of node i when there are ${\displaystyle x_{i}}$ jobs at node i.

Let ${\displaystyle X_{i}(t)}$ denote the number of jobs at node i at time t, and ${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$. Then the equilibrium distribution of ${\displaystyle \mathbf {X} }$, ${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$ is determined by the following system of balance equations:

${\displaystyle \pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)}$

where ${\displaystyle \mathbf {e} _{i}}$ denote the ${\displaystyle i^{th}}$ unit vector.

### Theorem

Suppose a vector of independent random variables ${\displaystyle (Y_{1},\ldots ,Y_{J})}$ with each ${\displaystyle Y_{i}}$ having a probability mass function as

${\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}}\quad (3)}$

, where ${\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}$. If ${\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }$ i.e. ${\displaystyle P(Y_{i}=0)=(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}})^{-1}}$ is well defined, then the equilibrium distribution of the open Jackson network has the following product form:

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).}$

for all ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$.⟩

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 ${\displaystyle \mathbf {X} }$ by a vector of independent variable ${\displaystyle \mathbf {Y} }$.

### Example

A three-node open Jackson network

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

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}}$ for all ${\displaystyle x_{i}>0}$

Then by the theorem, we can calculate:

${\displaystyle \lambda =(I-P')^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}$

According to the definition of ${\displaystyle \mathbf {Y} }$, we have:

${\displaystyle P(Y_{1}=0)=(1+\sum _{n=1}^{\infty }({\frac {2.5}{15}})^{n})^{-1}={\frac {5}{6}}}$
${\displaystyle P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {3.75}{12}})^{n})^{-1}={\frac {11}{16}}}$
${\displaystyle P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {1.25}{10}})^{n})^{-1}={\frac {7}{8}}}$

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

${\displaystyle \pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326}$

Since the service rate here doesn't depend on state, the ${\displaystyle Y_{i}'s}$ simply follows geometric distribution.

## Closed Jackson network

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, ${\displaystyle p_{0i}}$ and ${\displaystyle p_{j0}}$ are 0 for all i and j., and ${\displaystyle \sum _{j=1}^{J}p_{ij}=1}$ for each row. Let ${\displaystyle (\nu _{i})_{i=1}^{J}}$ be the solution to

${\displaystyle \nu _{i}=\sum _{j=1}^{J}\nu _{j}p_{ji}\qquad (5)}$

The solution is not unique so we need to add another equation. For example ${\displaystyle \sum _{i=1}^{J}\nu _{i}=\nu _{0}}$ for some constant ${\displaystyle \nu _{0}}$ or ${\displaystyle \nu _{j}=1}$for some ${\displaystyle j}$.

The equilibrium balance equations are given by:

${\displaystyle \pi (\mathbf {x} )\sum _{i=1}^{J}\mu _{i}(x_{i})(1-p_{ii})=\sum _{i=1}^{J}\sum _{j\neq i}\pi )\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.}$

for all ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$ such that ${\displaystyle |\mathbf {x} |:=\sum _{i=1}^{J}x_{i}=N}$. Similarly, define ${\displaystyle |\mathbf {X} |:=\sum _{i=1}^{J}X_{i}}$ and ${\displaystyle |\mathbf {Y} |:=\sum _{i=1}^{J}Y_{i}}$ where ${\displaystyle \mathbf {X} }$ and ${\displaystyle \mathbf {Y} }$ are defined before.

### Theorem

For all ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J},|\mathbf {x} |=N}$, we have:

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i})/P(|\mathbf {Y} |=N)}$

Where ${\displaystyle \mathbf {Y} }$ follow the distribution in ${\displaystyle (3)}$ with ${\displaystyle \lambda _{i}}$ is replaced by ${\displaystyle \nu _{i}}$.⟩

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

### Example

A three-node closed Jackson network

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

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0.5&0.5&0\\0.5&0.5&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}}$ for all ${\displaystyle x_{i}>0}$

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

Set ${\displaystyle \nu _{1}=1}$ and solve ${\displaystyle (I-P')\nu =0}$, we get:

${\displaystyle \nu ={\begin{bmatrix}1\\1.5\\0.5\end{bmatrix}}}$

Hence we can know the distribution of ${\displaystyle \mathbf {Y} }$:

${\displaystyle P(Y_{1}=0)=(1+\sum _{n=1}^{\infty }({\frac {1}{15}})^{n})^{-1}={\frac {14}{15}}}$
${\displaystyle P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {1.5}{12}})^{n})^{-1}={\frac {7}{8}}}$
${\displaystyle P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.5}{10}})^{n})^{-1}={\frac {19}{20}}}$

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

${\displaystyle \pi (1,1,1)=(P(Y_{1}=1)\cdot P(Y_{2}=1)\cdot P(Y_{3}=1))/P(|\mathbf {Y} |=3)=\prod _{j=1}^{3}P(Y_{j}=1)/\sum _{|\mathbf {y} |=3}P(\mathbf {Y} =\mathbf {y} )\approx 0.07097}$

## Semi-open Jackson Network

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 ${\displaystyle \mu _{0}(n)=\alpha }$ if ${\displaystyle n>0}$ and ${\displaystyle \mu _{0}(0)=0}$. This captures the blocking of the external arrivals when the buffer is full.

Set ${\displaystyle \nu _{0}=1}$ and ${\displaystyle \nu _{i}=\lambda _{i}/\alpha }$, then they are solutions to the set of equations:

${\displaystyle \nu _{i}=\sum _{j=0}^{J}\nu _{j}p_{ji}\qquad }$

It is same as the one described in ${\displaystyle (5)}$ for a J+1 closed work.

### Theorem

The semiopen Jackson network with an overall buffer capacity of K, has the following distribution: For all ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$ such that ${\displaystyle |\mathbf {x} |\leq K}$,

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i})/P(|\mathbf {Y} |\leq K),}$

where ${\displaystyle Y_{i}}$ follows distribution in ${\displaystyle (3)}$.⟩

### Example

A semiopen three-node network

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

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}}$ for all ${\displaystyle x_{i}>0}$

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

When the systme is not full, the arrival rate is ${\displaystyle \lambda ={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}.}$

We can use node 0 to represent the out-side world, and its service rate is ${\displaystyle \mu _{0}(x_{0})=\alpha =5}$. Then we have a closed network with 4 jobs and coefficients:

${\displaystyle P_{close}={\begin{bmatrix}0&0.5&0.5&0\\0&0&0.5&0.5\\1&0&0&0\\1&0&0&0\end{bmatrix}},\quad \mu _{close}={\begin{bmatrix}\mu _{0}(x_{0})\\\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}5\\15\\12\\10\end{bmatrix}}}$ for all ${\displaystyle x_{i}>0}$

By setting ${\displaystyle \nu _{0}=1}$ and dividing ${\displaystyle \lambda }$ by ${\displaystyle \alpha }$, we can calculate ${\displaystyle \nu _{close}={\begin{bmatrix}1\\0.5\\0.75\\0.25\end{bmatrix}}}$

Then we have

${\displaystyle P(Y_{0}=0)=(1+\sum _{n=1}^{\infty }({\frac {1}{5}})^{n})^{-1}={\frac {4}{5}}}$
${\displaystyle P(Y_{1}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.5}{15}})^{n})^{-1}={\frac {29}{30}}}$
${\displaystyle P(Y_{2}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.75}{12}})^{n})^{-1}={\frac {15}{16}}}$
${\displaystyle P(Y_{3}=0)=(1+\sum _{n=1}^{\infty }({\frac {0.25}{10}})^{n})^{-1}={\frac {39}{40}}}$

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

${\displaystyle \pi (X_{1}=X_{2}=X_{3}=1)=\prod _{j=1}^{3}P(Y_{j}=1)/\sum _{|\mathbf {y} |\leq 4}P(\mathbf {Y} =\mathbf {y} )\approx 0.00329}$

## Generalized Jackson Network

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

Under some mild conditions the queue-length process ${\displaystyle Q(t)}$ of a open generalized Jackson network can be approximated by a reflected Brownian motion defined as ${\displaystyle RBM_{Q(0)}(\theta ,\Gamma ;R).}$, where ${\displaystyle \theta }$ is the drift of the process, ${\displaystyle \Gamma }$ is the covariance matrix, and ${\displaystyle R}$ 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:

${\displaystyle \theta =\alpha -(I-P')\mu }$
${\displaystyle \Gamma =(\Gamma _{kl})}$ with ${\displaystyle \Gamma _{kl}=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{kl}-p_{jl})+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{jl}-\delta _{jl})]+\alpha _{k}c_{0,k}^{2}\delta _{kl}}$
${\displaystyle R=I-P'}$

where the symbols are defined as:

Definitions of symbols in the approximation formula
symbol Meaning
${\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}}$ a J-vector specifying the arrival rates to each node.
${\displaystyle \mu =(\mu )_{j=1}^{J}}$ a J-vector specifying the service rates of each node.
${\displaystyle P}$ routing matrix.
${\displaystyle \lambda _{j}}$ effective arrival of ${\displaystyle j^{th}}$ node.
${\displaystyle c_{j}}$ variation of service time at ${\displaystyle j^{th}}$ node.
${\displaystyle c_{0,j}}$ variation of inter-arrival time at ${\displaystyle j^{th}}$ node.
${\displaystyle \delta _{ij}}$ coefficients to specify correlation between nodes.