ジャクソンネットワークとは何？わかりやすく解説 Weblio辞書

ジャクソンネットワーク

概要

各ノードはひとつまたは複数の窓口からなり，指数分布にしたがうサービス時間でサービスを行い，ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択にしたがって選ぶ待ち行列ネットワーク．客をクラスにより区別しない．外部からポアソン過程にしたがって客が到着する開放型と，常に一定数の客が網内を循環している閉鎖型に分けられる．ネットワーク状態の定常確率分布は積形式をもつ．基本的なモデルとして重要なものであり，広く応用されている．

詳説

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

　この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり, １つのノードのサービスを終えた客が，その客の履歴によらず，経路選択確率と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち， $M\,$ 個のノード $1, 2, \ldots, M\,$ からなり，ノード $i\,$ のサービス率はそのノードにいる客数 $n\,$ の関数で， $C_{i}\,(n)$ と表すことができる．例えば，ノード $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\,$ について， $r_{i0}\,>0$ とならなければならない．閉鎖型の場合はすべての $i\,$ について， $\textstyle \sum_{j=1}^Mp_{ij} =1\,$ とする．経路選択確率 $r_{ij}\,$ からなる正方行列を $P\,$ とする．開放型の場合，状態 $0\,$ があるため， $P\,$ は $M+1\,$ 次となり，閉鎖型の場合 $M\,$ 次となる． $P\,$ をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の混合型については，発展した型であるBCMP型やケリー型などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある有限呼源(もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．

積形式解

　この待ち行列網の状態を $(n_1, n_2, \ldots, n_M)\,$ で表す. ここで $n_i\,$ はノード $i\,$ にいる客の数である. 定常状態確率を $p_{(n_1, n_2, \ldots, n_M)}\,$ とすれば, これは次のような積形式になる.

$p_{(n_1, n_2, \ldots, n_M)}=G^{-1} \prod_{i=1}^M \, \frac{\alpha_i^{n_i}}{\prod_{n=1}^{n_i} C_i(n)}$

上記の積で $n_i=0\,$ となる項は1とする. $G\,$ は正規化定数であり, $\alpha_i\,$ $(i=1, 2, \ldots, M)\,$ はトラフィック方程式と呼ばれるつぎの方程式の解である.

$\alpha_i = p_{0i}\lambda + \sum_{i=1}^M \alpha_j p_{ji}, \quad i=1, 2, \ldots, M, \qquad \,$ 　開放型

$\alpha_i = \sum_{i=1}^M \alpha_j p_{ji}, \quad i=1, 2, \ldots, M, \qquad \,$ 　開放型

この方程式は，各ノード毎に到着率が退去率に等しいとして得られる 1次の連立方程式である．開放型の場合，解 $\alpha_i\,$ は一人の客が網に到着してから退去するまでにノード $i\,$ を訪問する平均回数にネットワークへの総到着率 $\lambda\,$ を乗じたものである．閉鎖型の場合は，トラヒック方程式は $P\,$ の定常確率を求める方程式と同一であり，さらに，例えば $\alpha_1=1\,$ とすれば， $\alpha_{i}\,$ はノード1に到着してからまた次にそこに到着するまでの間にノード $i\,$ を訪問する期待回数という意味をもつ．

定常分布が積形式となることから，開放型の場合，任意時点での，各ノードの列の長さは互いに独立になり，各ノードからの退去過程がポアソン過程になる．また，閉鎖型も含め，どんな部分ネットワークに対しても，部分ネットワーク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができる．長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，ノートンの定理が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを到着定理という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード $i\,$ に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．

正規化定数と性能評価量の計算

　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が $\textstyle \sum_{i=1}^M n_i=N\,$ を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，たたみ込み法や平均値解析法が知られている．[2]．たたみこみ法では, ノード $i\,$ に対し, $N+1\,$ 次元のベクトルを

$X_i=(X_i(0), X_i(1), \ldots, X_i(N)), \quad X_i(0)=1, X_i(n)= \frac {\alpha_i^{n}} {\Pi_{j=1}^n C_{i}(j)} \quad (n>0), \ n>0 \,$

とし， $G=(X_1*X_2*...*X_M){\mathbf 1}\,$ で与える． $*\,$ はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理とLittleの公式を応用し，平均列長などを系内客数 $N\,$ について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．

[3]X. Chao, M. Miyazawa and M. Pinedo, Queueing Networks; customers, signals and product form solutions, Wiley, 1999.

[4]E. Gelenbe, ``Product-form queueing networks with negative and positive customers, Journal of Applied Probability}, (1991), 656--663.

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

[6]T. Kawashima, ``A Property of two Palm measures in queueing networks and its applications,Journal of the Operations Research Society of Japan, (1982), 16--28.

[7]M. Miyazawa, P. Taylor, ``A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers, Advances in Applied Probability 29, (1997), 523--544.

[8] 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.

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

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

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

[12]H. Yamashita, M. Miyazawa,``Product form queueing networks with concurrent movements, . Advances in Applied Probability, 30 (1998), 1111--1129.