Сеть Джексона

В теории массового обслуживания — дисциплине математической теории вероятностей — сеть Джексона (иногда джексоновская сеть). ) — это класс сети массового обслуживания, где равновесное распределение особенно просто вычислить, поскольку сеть имеет решение в форме продукта . Это было первое значительное достижение в теории сетей очередей , а обобщение и применение идей теоремы для поиска аналогичных решений в форме продукта в других сетях стало предметом многочисленных исследований. включая идеи, использованные при развитии Интернета. Сети были впервые идентифицированы Джеймсом Р. Джексоном. и его статья была перепечатана в журнале Management Science « Десять самых влиятельных названий наук об управлении за первые пятьдесят лет».

Джексон был вдохновлен работами Берка и Райха. хотя Жан Вальранд отмечает, что «результаты в форме произведения… [являются] гораздо менее непосредственным результатом теоремы о выходе, чем, по-видимому, полагал сам Джексон в своей фундаментальной статье».

Более раннее решение в форме продукта было найдено RRP Jackson для тандемных очередей (конечная цепочка очередей, в которой каждый клиент должен посещать каждую очередь по порядку) и циклических сетей (цикл очередей, в котором каждый клиент должен посещать каждую очередь по порядку).

Сеть Джексона состоит из нескольких узлов, где каждый узел представляет собой очередь, в которой скорость обслуживания может зависеть как от узла (разные узлы имеют разные скорости обслуживания), так и от состояния (скорость обслуживания меняется в зависимости от длины очереди). Задания перемещаются между узлами по фиксированной матрице маршрутизации. Все задания на каждом узле принадлежат одному «классу», и задания имеют одинаковое распределение времени обслуживания и один и тот же механизм маршрутизации. Следовательно, при обслуживании заданий не существует понятия приоритета: все задания на каждом узле обслуживаются в порядке очереди .

Сети Джексона, в которых конечная совокупность рабочих мест перемещается по замкнутой сети, также имеют решение в форме продукта, описываемое теоремой Гордона-Ньюэлла .

Необходимые условия для сети Джексона

Сеть из m взаимосвязанных очередей называется сетью Джексона. или джексоновская сеть если он соответствует следующим условиям:

1. если сеть открыта, любые внешние поступления в узел i образуют процесс Пуассона ,
2. Все времена обслуживания распределены экспоненциально, а дисциплина обслуживания во всех очередях осуществляется в порядке очереди .
3. клиент, завершающий обслуживание в очереди i, перейдет в какую-то новую очередь j либо с вероятностью $P_{ij}$ или покинуть систему с вероятностью $1-\sum _{j=1}^{m}P_{ij}$, которое для открытой сети не равно нулю для некоторого подмножества очередей,
4. использование . всех очередей меньше единицы

Теорема

В открытой сети Джексона с 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 с серверами c _i на $i^{\text{th}}$ станция, с требованием утилизации $\rho _{i}<c_{i}$.

Определение

В открытой сети рабочие места поступают извне в соответствии с процессом Пуассона со скоростью $\alpha >0$. Каждое поступление независимо направляется в узел j с вероятностью $p_{0j}\geq 0$ и $\sum _{j=1}^{J}p_{0j}=1$. После завершения обслуживания в узле i задание может перейти в другой узел j с вероятностью $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$.

Все задания покидают каждый узел также в соответствии с процессом Пуассона и определяют $\mu _{i}(x_{i})$ как скорость обслуживания узла i, когда есть $x_{i}$ рабочие места в узле 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^{\text{th}}$ единичный вектор .

Теорема

Предположим, что вектор независимых случайных величин $(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}$.⟩

показывать

Доказательство

It suffices to verify equation $(2)$ is satisfied. By the product form and formula (3), we have:

$\pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]$

Substituting these into the right side of $(2)$ we get:

$\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i}p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j}).\qquad (4)$

Then use $(1)$, we have:

$\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}]\mu _{j}(x_{j})=\sum _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j}}{\lambda _{j}}}]\mu _{j}(x_{j}).$

Substituting the above into $(4)$, we have:

$\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}$

This can be verified by $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$. Hence both side of $(2)$ are equal.⟨

Эта теорема расширяет теорему, показанную выше, допуская зависимость скорости обслуживания каждого узла от состояния. Это касается распределения $\mathbf {X}$ вектором независимой переменной $\mathbf {Y}$.

Пример

Открытая сеть Джексона с тремя узлами

Предположим, у нас есть сеть Джексона с тремя узлами, показанная на графике, коэффициенты:

$\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}$s просто следует геометрическому распределению .

Обобщенная сеть Джексона

Обобщенная сеть Джексона допускает процессы прибытия обновлений , которые не обязательно должны быть процессами Пуассона, и независимые, одинаково распределенные неэкспоненциальные времена обслуживания. В общем, эта сеть не имеет стационарного распределения по форме продукта , поэтому ищутся приближения.

Броуновское приближение

В некоторых мягких условиях процесс длины очереди $Q(t)$ открытой обобщенной сети Джексона может быть аппроксимирована отраженным броуновским движением, определяемым как $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$, где $\theta$ это дрейф процесса, $\Gamma$ - ковариационная матрица, а $R$ – матрица отражения. Это аппроксимация двух порядков, полученная на основе связи между общей сетью Джексона с однородной сетью жидкости и отраженным броуновским движением.

Параметры отраженного броуновского процесса задаются следующим образом:

$\theta =\alpha -(I-P^{T})\mu$

$\Gamma =(\Gamma _{k\ell }){\text{ with }}\Gamma _{k\ell }=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }$

$R=I-P^{T}$

где символы определены как:

Определения символов в формуле аппроксимации

символ	Значение
$\alpha =(\alpha _{j})_{j=1}^{J}$	J -вектор , определяющий скорость поступления в каждый узел.
$\mu =(\mu )_{j=1}^{J}$	J -вектор , задающий скорость обслуживания каждого узла.
$P$	матрица маршрутизации.
$\lambda _{j}$	эффективное прибытие $j^{\text{th}}$ узел.
$c_{j}$	изменение времени обслуживания в $j^{\text{th}}$ узел.
$c_{0,j}$	изменение времени прибытия в $j^{\text{th}}$ узел.
$\delta _{ij}$	коэффициенты для определения корреляции между узлами. показывать They are defined in this way: Let $A(t)$ be the arrival process of the system, then $A(t)-\alpha t{}\approx {\hat {A}}(t)$ in distribution, where ${\hat {A}}(t)$ is a driftless Brownian process with covariate matrix $\Gamma ^{0}=(\Gamma _{ij}^{0})$, with $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$, for any $i,j\in \{1,\dots ,J\}$

См. также

• Сеть Гордона – Ньюэлла
• Сеть BCMP
• G-сеть
• Закон Литтла