《待ち行列ネットワーク(ジャクソン型とその応用)》

【まちぎょうれつねっとわーく (じゃくそんがた) (Jackson network) 】

ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から，計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され，平衡方程式の解である定常確率分布が積形式として陽に表される基本的なモデルとして重要なものとなっている．

この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり，１つのノードのサービスを終えた客が，その客の履歴によらず， 経路選択確率と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち，$M\,$個のノード$1,2,\ldots ,M\,$からなり，ノード$i\,$のサービス率はそのノードにいる客数$n\,$の関数で，$C_{i}\,$と表すことができる．例えば，ノード$i\,$のサーバー数が，$C_{i}\,$，サービス時間分布がサービス率，$mu_{(}i)\,$の\指数分布ならば，$C_{i}(n)=\min(n,c_{i})\mu _{i}\,$である．ノード$i\,$のサービスを終えた客は経路選択確率$r_{ij}\,$でノード$j\,$に移動する．

この網は，外部からの客の到着を仮定する開放型と，外部からの到着はなく，常に一定数$N\,$の客が網内を移動する閉鎖型に大別される．開放型の場合，外部からの到着過程は到着率$\lambda \,$のポアソン過程とする．外部から到着した客は確率$r_{0i}\,$でノード$i\,$に進み，ノード$i\,$のサービスが終了した客は確率$r_{i0}\,$で網から退去する．少なくとも一つの$i\,$について，構文解析に失敗 (構文エラー): {\displaystyle r_{i0}\>0, } とならなければならない．閉鎖型の場合はすべての$i\,$について，$\textstyle \sum _{j=1}^{M}p_{ij}=1\,$ とする． 経路選択確率$r_{ij}\,$ からなる正方行列を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\, } とする．開放型の場合，状態構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\, } があるため，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\, } は$M+1\,$次となり，閉鎖型の場合$M\,$次となる． 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\, } をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の混合型 については，発展した型であるBCMP型やケリー型などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある有限呼源(もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（\cite{B-B-02+jack}参照）．

定常状態確率　この待ち行列網の状態を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (n_1, n_2, \ldots, n_M)\, } で表す. ここで 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n_i\, } はノード 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } にいる客の数である. 定常状態確率を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_{(n_1, n_2, \ldots, n_M)}\, } とすれば, これは次のような積形式になる.

$p_{(n_{1},n_{2},\ldots ,n_{M})}=G^{-1}\prod _{i=1}^{M}\prod _{n=1}^{n_{i}}{\frac {\alpha _{i}}{C_{i}(n)}}\,$

ここで 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n_i=0\, } のときは上記の積は1とみなす. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } は正規化定数であり, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i\, } 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (i=1, 2, \ldots, M)\, } はトラヒック方程式と呼ばれるつぎの方程式の解である.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i = p_{0i}\lambda + \sum_{i=1}^M \alpha_j p_{ji}, \quad i=1, 2, \ldots, M, \qquad \, } 　開放型

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i = \sum_{i=1}^M \alpha_j p_{ji}, \quad i=1, 2, \ldots, M, \qquad \, } 　閉鎖型

これらの式は, 各ノード毎に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i\, } を到着率とみなし, これが退去率に等しいとして得られる1次の連立方程式と解釈できる. 開放型の場合, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i\, } は一人の客がネットワークに到着してから退去するまでにノード 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } を訪問する平均回数に構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda\, } を乗じたものとなっている. 閉鎖型の場合, トラヒック方程式は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P\, } の定常状態確率を求める方程式と同一であり, さらに例えば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1=1\, } という条件をおけば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_i\, } はノード1に到着してからまた再びノード1に戻ってくるまでにノード 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } を訪問する平均回数という意味をもつ.

いろいろな性質　定常分布が積形式となることから, ジャクソンネットワークではいろいろ好ましい性質が成り立つことが証明されている. まず開放型の場合, 任意時点での各ノードの客の数は互いに独立になる. ただし, 閉鎖型の場合は可能な状態が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \sum_{i=1}^M n_i =N\, } を満たすものに限られるので, 客の数は独立とはならない. また, 閉鎖型も含め, 各ノードからの退去過程はポアソン過程になる. したがって, どんな部分ネットワークに対しても, 部分ネットワーク全体を1つのノードで置き換えて, 他の部分の定常分布が変わらないようにすることができる. すなわちノートンの定理が任意の部分ネットワークに対して成り立つ [8]. さらに, 1つのノードへの到着時点で, 到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する. これを到着定理という. ただし, ネットワークが閉鎖型の場合には, 任意時点の分布として (到着した客を除いたことに対応する) システム内客数が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N-1\, } のネットワークにおける定常分布を使う. さらに客の退去時点での分布も同様であり [4], この分布のもとで, ノード 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } に到着してから次にそこに戻るまでの平均周期は, ノードごとの平均訪問回数と平均待ち時間の積の総和で与えられる.

　正規化定数, スループット, 各ノードの平均客数などを求めることは, 開放型ネットワークの場合は容易である. 各ノードの客数が互いに独立になるためである. しかし, 閉鎖型の場合には, 可能な状態が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \sum_{i=1}^M n_i =N\, } を満たすものに限られるという制約のため, 工夫が必要である. 例えば, 正規化定数を計算する方法として, たたみ込み法や平均値解析法が知られている[2]. たたみ込み法では, ノード $i\,$ に対し, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N+1\, } 次元のベクトルを

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_i=(X_i(0), X_i(1), \ldots, X_i(N)), \quad X_i(0)=1, \quad X_i(n)=\prod_{j=1}^n \alpha_i/C_i(j), \ n>0 \, }

とし, これらのベクトルを客数の和が $N\,$ 以下の範囲でたたみこみ演算して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } を求める. 平均値解析法は到着定理とリトルの公式を応用し, 各ノードの平均客数, 1回あたりの平均滞在時間, スループットなどを, システム内客数 $N\,$ について 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\, } から繰り返し計算する方法である. 各ノードでの規律は, 平均待ち時間が到着時点での平均客数と平均サービス時間から求まるもの, 例えば先着順であること, が本質的である.

　待ち時間の分布については, 特殊なネットワークについてのみ考察されている. 開放型で, サーバー数が1のノード (規律は先着順) が直列に並んでいるネットワークもJackson型の一つであるが, このネットワークで一人の客の各ノードでの滞在時間は互いに独立であることがバークの定理として知られている [1],[6]. これを閉鎖型にした場合, すなわち最後のノードを退去した客は必ず最初のノードに戻る循環型のネットワークでも, 一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる [7]. これはどの客も他の客に追い越されることがない (overtake free) という性質が本質的であり, バークの定理はこの影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ. 特に最後のノードのサービス時間分布は任意でよい. その他, セントラルサーバモデルで規律がプロセッサーシェアリングである場合の研究もある [5].

　履歴により経路選択確率が変化する場合も含め, 客のクラスが複数の場合の混合型については, 発展型であるBCMP型, ケリー型などのネットワークで扱われる. また, 外部からの到着があるが, 系内に入ることができる客数に制限がある有限呼源 (もしくは損失型) の場合, 外部を一つのノードとみなすことにより, 閉鎖型に帰着できる [3].

---

参考文献

[1] P. J. Burke, "The Output Process of a Stationary M/M/s Queuing System, The Annals of Mathematical Statistics, 39 (1968), 1144-1152.

[2] K. M. Chandy and C. H. Sauer, "Computational Algorithms for Product Form Queueing Networks," Communications of the Association for Computing Machinery, 23 (1980), 573-583.

[3] J. R. Jackson, "Jobshop-like Queueing Systems," Management Science, 10 (1963), 131-142.

[4] T. Kawashima, "A Property of Two Palm Measures in Queueing Networks and Its Applications," Journal of the Operations Research Society of Japan, 25 (1982), 16-28.

[5] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," Advances in Applied Probability, 17 (1985), 163-185.

[6] E. Reich "Note on Queues in Tandem," The Annals of Mathematical Statistics, 34 (1963), 338-341.

[7] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," Journal of Applied Probability, 24 (1987), 511-521.

[8] J. Walrand, An Introduction to Queueing Networks, Prentice Hall, 1988.