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

В теории массового обслуживания , дисциплине математической теории вероятностей , сеть Джексона (иногда сеть Джексона ^[1] ) представляет собой класс сетей массового обслуживания, в которых равновесное распределение особенно просто вычислить, поскольку сеть имеет решение в виде продукта . Это было первое значительное развитие в теории сетей очередей , и обобщение и применение идей теоремы для поиска аналогичных решений в форме продукта в других сетях было предметом многих исследований ^[2], включая идеи, использованные в развитие Интернета. ^[3]Сети были впервые идентифицированы Джеймсом Р. Джексоном ^{[4] [5],} и его статья была перепечатана в журнале Management Science 's «Десять наиболее влиятельных титулов в области управленческих наук за первые пятьдесят лет». ^[6]

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

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

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

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

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

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

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

Теорема [ править ]

В открытой сети Джексона из m очередей M / M / 1, где коэффициент использования меньше 1 в каждой очереди, существует распределение вероятностей состояния равновесия, и для состояния оно задается как произведение равновесных распределений отдельных очередей.${\ displaystyle \ rho _ {я}}$${\ displaystyle \ scriptstyle {(k_ {1}, k_ {2}, \ ldots, k_ {m})}}$

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

Результат также относится к модельным станциям M / M / c с серверами c _i на станции с требованиями к загрузке .${\ displaystyle \ pi (k_ {1}, k_ {2}, \ ldots, k_ {m}) = \ prod _ {i = 1} ^ {m} \ pi _ {i} (k_ {i})}$${\ displaystyle i ^ {\ text {th}}}$${\ Displaystyle \ rho _ {я} <c_ {я}}$

Определение [ править ]

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

Следовательно , мы имеем общую скорость прибытия к узлу I , , в том числе как внешних , так и внутренних вступлений переходов:${\ displaystyle \ lambda _ {i}}$

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

(Поскольку использование в каждом узле меньше 1, и мы смотрим на равновесное распределение, то есть на поведение долгосрочного среднего значения, скорость перехода заданий с j на i ограничена долей скорости поступления в j и мы игнорируем стоимость услуги, указанную выше.)${\ displaystyle \ mu _ {j}}$

Определите , тогда мы сможем решить .${\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}$${\displaystyle \lambda =(I-P^{T})^{-1}a}$

Все задания оставьте каждый узел также следующий процесс Пуассона, а также определить , как скорость обслуживания узла я , когда есть рабочие места на узле я .${\displaystyle \mu _{i}(x_{i})}$${\displaystyle x_{i}}$

Позвольте обозначить количество работ в узле i в момент времени t , и . Тогда равновесное распределение по , определяется следующей системой уравнений баланса:${\displaystyle X_{i}(t)}$${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$${\displaystyle \mathbf {X} }$${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$

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

где обозначим единичный вектор .${\displaystyle \mathbf {e} _{i}}$${\displaystyle i^{\text{th}}}$

Теорема [ править ]

Предположим, что вектор независимых случайных величин, каждая из которых имеет функцию массы вероятности как${\displaystyle (Y_{1},\ldots ,Y_{J})}$${\displaystyle Y_{i}}$

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

где . Если ie правильно определено, то равновесное распределение открытой сети Джексона имеет следующую форму продукта:${\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}$${\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }$${\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}}$

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

для всех .⟩${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$

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

Пример [ править ]

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

${\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}}{\text{ for all }}x_{i}>0}$

Тогда по теореме можно вычислить:

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

Согласно определению , мы имеем:${\displaystyle \mathbf {Y} }$

${\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

${\displaystyle P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}}$

${\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}}$

Следовательно, вероятность того, что на каждом узле есть одно задание, равна:

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

Поскольку скорость обслуживания здесь не зависит от состояния, s просто следуют геометрическому распределению .${\displaystyle Y_{i}}$

Обобщенная сеть Джексона [ править ]

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

Броуновское приближение [ править ]

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

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

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

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

${\displaystyle R=I-P^{T}}$

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

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

символ	Имея в виду
${\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}}$	J -векторный с указанием скорости прибытия для каждого узла.
${\displaystyle \mu =(\mu )_{j=1}^{J}}$	J -векторный с указанием скорости обслуживания каждого узла.
${\displaystyle P}$	матрица маршрутизации.
${\displaystyle \lambda _{j}}$	эффективное прибытие узла.${\displaystyle j^{\text{th}}}$
${\displaystyle c_{j}}$	изменение времени обслуживания на узле.${\displaystyle j^{\text{th}}}$
${\displaystyle c_{0,j}}$	изменение времени между прибытиями в узле.${\displaystyle j^{\text{th}}}$
${\displaystyle \delta _{ij}}$	коэффициенты для определения корреляции между узлами. Они определены следующим образом: пусть будет процесс прихода системы, затем в распределение, где - броуновский процесс без смещения с ковариатной матрицей , с , для любого${\displaystyle A(t)}$${\displaystyle A(t)-\alpha t{}\approx {\hat {A}}(t)}$${\displaystyle {\hat {A}}(t)}$${\displaystyle \Gamma ^{0}=(\Gamma _{ij}^{0})}$${\displaystyle \Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}}$${\displaystyle i,j\in \{1,\dots ,J\}}$

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июнь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

См. Также [ править ]

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

Ссылки [ править ]