杰克逊排队网络

在排队论中（运筹学的一支），**杰克逊排队网络**（，亦作）是一类排队网络模型，其均衡分布计算形式简单且网络具有积形式解。该模型已被推广，其定理的思想也被运用于寻找其他网络中类似的积形式解。互联网发展中的一些思想亦源于该排队网络。这一网络模型首先由提出。2004年，杰克逊的文章重载于《》，该刊将其誉为“管理科学头50年中最具影响力的十篇论文”之一。

杰克逊受到了和赖克（）工作的启发。但吉恩·华尔兰德（）指出“积形式解的结果……从柏克定理推过去不是很直接，并没有杰克逊本人在他那篇奠基性文章中所认为的那么直接”。

在串联排队（有限数量的队列，顾客按先后顺序去每个队列等候）和环形排队网络（串联成环的若干队列，顾客按先后顺序去每个队列等候）中，更早就发现了一个积形式解。

杰克逊网络包括一定数量的节点，每个节点表示一个队列，队列的服务率既可以是状态无关的（不同的节点有不同的服务率），也可以是状态相关的（服务率的变化与队长相关）。任务（）按照一个固定的路由矩阵（）在节点间转移。每个节点处的任务都属于单一的“类”（），任务都服从相同都服务时间分布和路由机制。因此，并没有引入任务服务的优先级：每个节点处的所有工作都以先到先得（）方式进行。

有限任务、闭合网络的杰克逊网络也有积形式解，该结论由Gordon–Newell定理阐明。

## 杰克逊排队网络的必要条件
m个相连队列组成的网络被称作杰克逊网络，若它满足下述条件： 

# 若网络是开放的，任意往节点i的外部到达都是一个泊松过程，
# 服务时间呈指数分布，排队规则为先到先得（），
# 队列i处的顾客服务结束后，以概率P_{ij}转移到新的队列j或以概率1-\sum_{j=1}^{m}P_{ij}离开队列；对于开放网络来说，离开概率对所有队列的某个子集是非零的，
# 所有队列的利用率都小于1。

## 定理

m为M/M/1模型的开放杰克逊网络，其中利用率（）\rho_i对每个队列都小于1，平衡状态概率分布存在，且对状态\scriptstyle{(k_1,k_2,\ldots,k_m)}，平衡状态（）概率分布由每个队列的平衡分布之积给出：

:\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i) = \prod_{i=1}^{m} [\rho_i^{k_i} (1-\rho_i)].

结果\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i)对M/M/c服务站（）也成立，其中第i个节点的服务台（）数为c_i，利用率满足\rho_i 。

## 定义
在一个开放网络中，顾客自系统外部以泊松流方式到达，到达率为\alpha>0。每个往节点*j*的到达是相互独立的，有概率 p_{0j}\ge0且满足\sum_{j=1}^J p_{0j}=1。当节点i处的服务完成时，顾客会以概率p_{ij}进入另一节点或者以p_{i0}=1-\sum_{j=1}^J p_{ij}的概率离开网络。

因此，节点i的总到达率\lambda_i是外部到达和内部转移的总和：

:\lambda_i =\alpha p_{0i} + \sum_{j=1}^J \lambda_j p_{ji}, i=1,\ldots,J.\qquad (1)

（因为每个节点的利用率均小于1，且我们观察的是均衡分布，即长时间运行的平均行为，任务从j转移到i速率的界不超过j到达率的一部分，我们由此忽略上式中的服务率\mu_j。）

定义 a=(\alpha p_{0i})_{i=1}^J，我们就可以解出\lambda=(I-P^T)^{-1}a。

所有任务在后续泊松过程中会离开其节点，节点i处有 x_i 个任务，定义其服务率为\mu_i(x_i)。

令X_i(t)表示节点i在时间t的任务数，\mathbf{X}=(X_i)_{i=1}^J。\mathbf{X}的均衡分布，\pi(\mathbf{x})=P(\mathbf{X}=\mathbf{x})由如下系统平衡方程给出：

:
\begin{align}
& \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\ne i}\pi(\mathbf{x}+\mathbf{e}_i-\mathbf{e}_j)\mu_i(x_i+1)p_{ij}.\qquad (2)
\end{align}


其中\mathbf{e}_i表示第i个单位向量.。

### 定理
设独立随机向量 (Y_1,\ldots,Y_J)，每个 Y_i都有概率质量函数：

: P(Y_i=n)=p(Y_i=0)\cdot \frac{\lambda_i^n}{M_i(n)}, \quad (3)

其中 M_i(n)=\prod_{j=1}^n \mu_i(j) 。当 \sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)} 即P(Y_i=0)=\left(1+\sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)}\right)^{-1}是良定义的，开放杰克逊网络的平衡分布有如下的积形式：

: \pi(\mathbf{x})=\prod _{i=1}^J P(Y_i=x_i).

对所有的\mathbf{x}\in \mathcal{Z}_{+}^J 。

### 例

设图中有一三节点的杰克逊网络，系数分别是：

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

:
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} 
\text{ for all }x_i>0

通过定理，可以计算：

: \lambda=(I-P^T)^{-1}a=\begin{bmatrix}
1 & 0 & 0\\
-0.5 & 1 & 0 \\
-0.5 & 0 & 1\end{bmatrix}^{-1}\begin{bmatrix}
0.5\times5\\
0.5\times5\\
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}


根据\mathbf{Y}的定义，有：

: P(Y_1=0)=\left(\sum_{n=0}^\infty \left(\frac{2.5}{15}\right)^n\right)^{-1}=\frac{5}{6} 
: P(Y_2=0)=\left(\sum_{n=0}^\infty \left(\frac{3.75}{12}\right)^n\right)^{-1}=\frac{11}{16} 
: P(Y_3=0)=\left(\sum_{n=0}^\infty \left(\frac{1.25}{10}\right)^n\right)^{-1}=\frac{7}{8} 

因此，每个节点处有一个服务的概率是：

: \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

由于这里的服务率是状态无关的， Y_i各项服从简单的几何分布。

## 杰克逊网络的推广
**推广的杰克逊网络**允许不一定是一个泊松过程，也允许服务时间是独立且同种的非指数分布。一般地，网络不一定要有，因此需要找近似解

### 布朗近似
在一些平和的条件下，开放的推广杰克逊网络的队长过程Q(t)可以用近似，定义为RBM_{Q(0)}(\theta,\Gamma;R)，其中\theta是过程的漂移（），\Gamma是协方差矩阵，R是反射矩阵。这一二阶近似是从均质流体（）的推广杰克逊网络和反射布朗运动间的关系得到的。

反射布朗过程的参数如下所述：

: \theta= \alpha -(I-P^T)\mu 
: \Gamma=(\Gamma_{kl}) 有 \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} 
: R=I-P^T 

其中符号的定义：

## 参见

* Gordon–Newell网络
* BCMP网络
* G-网络
* Little法则

## 参考文献