ジャクソンネットワーク

数学的確率論の一分野である待ち行列理論において、ジャクソンネットワーク（ジャクソンネットワークとも呼ばれる^{[1] ）は、ネットワークが}積形式解を持つため、均衡分布の計算が特に簡単な待ち行列ネットワークの一種である。これは待ち行列ネットワーク理論における最初の重要な発展であり、定理の考え方を一般化して他のネットワークで同様の積形式解を探すことに応用することは、インターネットの開発に使用された考え方を含め、多くの研究の対象となってきた^[2]。^{[3]ネットワークは、}ジェームズ・R・ジャクソンによって最初に特定され^{[4] [5]}、彼の論文は、雑誌「マネジメントサイエンス」の「経営科学の最初の50年間で最も影響力のある10のタイトル」に再掲載された。^[6]

ジャクソンはバークとライヒの研究に触発されたが^[7]、ジャン・ウォーランドは「積形式の結果は…ジャクソン自身が基礎論文で信じていたように、出力定理の直接的な結果ではない」と指摘している^{[8] 。}

以前の積形式解は、RRPジャクソンによってタンデムキュー（各顧客が順番に各キューを訪問しなければならない有限のキューチェーン）とサイクリックネットワーク（各顧客が順番に各キューを訪問しなければならないキューのループ）に対して発見されました。^[9]

Jackson ネットワークは多数のノードで構成され、各ノードはキューを表します。キューのサービス レートは、ノード依存 (ノードによってサービス レートが異なる) と状態依存 (キューの長さによってサービス レートが変わる) の両方になります。ジョブは、固定ルーティング マトリックスに従ってノード間を移動します。各ノードのすべてのジョブは単一の「クラス」に属し、ジョブは同じサービス時間配分と同じルーティング メカニズムに従います。したがって、ジョブの処理に優先順位はありません。各ノードのすべてのジョブは、先着順で処理されます。

有限個のジョブが閉じたネットワーク内を巡回するジャクソンネットワークも、ゴードン・ニューウェル定理によって記述される積形式解を持つ。^[10]

m個の相互接続されたキューのネットワークは、次の条件を満たす場合、 ジャクソンネットワーク^[11]またはジャクソンネットワーク^[12]と呼ばれます。

1. ネットワークが開いている場合、ノードiへの外部からの到着はポアソン過程を形成し、
2. すべてのサービス時間は指数分布しており、すべてのキューでのサービス規律は先着順です。
3. キューiでサービスを完了した顧客は、確率 で新しいキューjに移動する、または確率 でシステムを離れる。オープンネットワークの場合、この確率はキューのサブセットによってはゼロではない。${\displaystyle P_{ij}}$${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$
4. すべてのキューの使用率は 1 未満です。

ジャクソンネットワークのオープンネットワークでは、各キューの使用率が1未満であるm個の M/M/1キューがあり、均衡状態確率分布が存在し、状態は個々のキューの均衡分布の積で与えられる。 ${\displaystyle \rho_{i}}$${\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})].}$

この結果は、ステーションにc _iサーバーがあり、使用率要件が であるM/M/c モデルステーションにも当てはまります。 ${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$${\displaystyle i^{\text{th}}}$${\displaystyle \rho _{i}<c_{i}}$

オープン ネットワークでは、ジョブは外部からポアソン過程に従って到着し、その速度は です。到着したジョブはそれぞれ独立して、確率 および でノードjにルーティングされます。ノードiでサービスが完了すると、ジョブは確率 で別のノードjに移動するか、確率 でネットワークを離れます。 ${\displaystyle \alpha >0}$${\displaystyle p_{0j}\geq 0}$${\displaystyle \sum _{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}$

すべてのジョブもポアソン過程に従って各ノードから出発し、ノードiにジョブがある場合のノードiのサービス率として定義されます。 ${\displaystyle \mu _{i}(x_{i})}$${\displaystyle x_{i}}$

時刻tにおけるノードiのジョブ数を、 と表すものとします。の均衡分布は、次のバランス方程式のシステムによって決定されます。 ${\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} }$

グラフに示す 3 つのノードを持つ Jackson ネットワークがあるとします。係数は次のようになります。

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

したがって、各ノードに 1 つのジョブがある確率は次のようになります。

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

ここでのサービス率は状態に依存しないため、 は単純に幾何分布に従います。 ${\displaystyle Y_{i}}$

一般化されたジャクソンネットワークは、ポアソン過程である必要のない更新到着過程と、独立した同一分布の非指数サービス時間を可能にする。一般に、このネットワークは積形式の定常分布を持たないため、近似値が求められる。^[13]

ある穏やかな条件下では、開いた一般化ジャクソン ネットワークのキュー長さプロセス^{[明確化が必要]} は、と定義される反射ブラウン運動で近似できます。ここで、はプロセスのドリフト、は共分散行列、 は反射行列です。これは、均質流体ネットワークを持つ一般ジャクソン ネットワークと反射ブラウン運動の関係によって得られる 2 次近似です。 ${\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}}$

ここで、記号は次のように定義されます。

• ゴードン・ニューウェルネットワーク
• BCMPネットワーク
• Gネットワ​​ーク
• リトルの法則