杰克逊排队网络

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

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

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

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

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

杰克逊排队网络的必要条件

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

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

定理

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

$\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服务站（stations）也成立，其中第$i$个节点的服务台（servers）数为$c_{i}$，利用率满足$\rho _{i}<c_{i}$。

定义

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

因此，节点$i$的总到达率$\lambda _{i}$是外部到达和内部转移的总和：${\displaystyle }$${\displaystyle }$

$$\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}$。）${\displaystyle }$

定义 $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{aligned}&\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)\end{aligned}}$

其中$\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)}}<\infty$即$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\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}}$

根据$\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}$各项服从简单的几何分布。

杰克逊网络的推广

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

布朗近似

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

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

$\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}$

其中符号的定义：

近似公式中符号的定义

符号	含义
$\alpha =(\alpha _{j})_{j=1}^{J}$	J维向量，每个节点的到达率
$\mu =(\mu )_{j=1}^{J}$	J维向量，每个节点的服务率
$P$	转移矩阵
$\lambda _{j}$	第j个节点的有效到达
$c_{j}$	第j个节点服务时间的变异系数
$c_{0,j}$	第j个节点服务台间转移到达时间的变异系数
$\delta _{ij}$	反映节点间关系的系数 它们是这样定义的：令$A(t)$为系统的到达过程，则在分布中有$A(t)-\alpha t{}\approx {\hat {A}}(t)$，其中${\hat {A}}(t)$是一个无漂移（driftless）的布朗过程，其协方差矩阵为$\Gamma ^{0}=(\Gamma _{ij}^{0})$，满足对所有的$i,j\in \{1,\dots ,J\}$都有$\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$。

参见

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