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

【まちぎょうれつねっとわーく (びーしーえむぴーがた) (BCMP network) 】

　待ち行列ネットワーク (queueing network) において, ネットワーク全体の定常分布が各ノードの状態の周辺分布の積として表されるとき, このようなネットワークは一般に積形式解 (product form solution) を持つといわれる. 最初に研究された一連の積形式ネットワークは, ジャクソンネットワーク (Jackson network) と呼ばれている. ジャクソンネットワークは, 定常分布の表現が簡単であるので広く応用されてきたが, 経路をあらかじめ選択できない, 指数サービスに限定される, などモデルの制約が強い. これに対して, ジャクソンネットワークを拡張して, 客に客のクラスを設け, かつより一般的なサービス機構にしても積形式解をもつことが, Baskettら [1] やKelly [2] の研究によって明らかにされた. ここでは, 前者をBCMPネットワーク (BCMP network) [4], 後者をケリーネットワーク (Kelly network) と呼ぶ.

BCMPネットワーク BCMPネットワークは, 次のように定義される.

• ネットワークは$N\,$個のノードから成り, 客は$C\,$個のクラスのいずれかに属する. この他に外部を表すノード$0\,$があるとする.

• 外部から到着した客は, 確率$r_{0,(i,c)}\,$でノード$i\,$に行き, クラス$c\,$の客となる. ノード$i\,$のクラス$c\,$の客は, サービス終了後確率$r_{(i,c),(j,d)}\,$でノード$j\,$のクラス$d\,$の客となり, 確率$r_{(i,c),0}\,$でネットワークから退去する. これらの確率はネットワークの状態とは独立であるので、このような経路選択をマルコフ的という．マルコフ的経路選択では，すべてのクラスに対して$r_{0,(i,c)}\,>0$，$r_{(i,c),0}\,>0$とおけば開放型(open network)，$r_{0,(i,c)}\,=0$，$r_{(i,c),0}\,=0$とおけば閉鎖型(closed network)となる．

• 客は外部から率$\lambda$のポアソン過程に従って到着する．(到着率は，ネットワーク内の人数，または経路選択行列で構成されるマルコフ連鎖の部分連鎖の人数に依存してもよい．)

• 各ノードのサービス規律は先着順, プロセッサ・シェアリング, 無限サーバ, 後着順割込継続型のいずれかにしたがう. 各クラスの客のサービス要求量の分布は, 先着順の場合はクラス共通の指数分布のみであるが, その他の場合はクラスに依存してもよく, 任意の分布が許される.

いま, ノード$i\,$への客の到着をトラフィック方程式 (traffic equation)

$\lambda _{(i,c)}=\lambda r_{0,(i,c)}+\sum _{j=1}^{N}\sum _{d=1}^{C}\lambda _{(j,d)}r_{(j,d),(i,c)}\,$

の解$\lambda _{(i,c)}\,$に等しい率のポアソン到着としてノードの状態の周辺分布を求めると, BCPM型ネットワークの定常分布はこの周辺分布の積で表現できる.

ケリー型 BCMPネットワークとケリーネットワークの2つの研究は，ほぼ同時期に独立に行われたが，本質的には同種類のモデルである．しかしKellyの研究は，積形式解をもつネットワークの範囲がBCMP型のプロセッサ・シェアリング，無限サーバ，後着順割込継続型を含む，より一般的な対称型サービス規律(symmetric service discipline)に拡張されている点と，客のクラスを経路情報を含めた形で設定するれば客の経路を決定論的に定めることができることを明示した点で重要である．以下，対称型サービス規律について説明する．

対称型サービス　対称型サービス規律ではノード内の客の位置を区別し, ノード$i\,$に客が$m\,$人いるときのノード$i\,$の状態 ${\boldsymbol {x_{i}}}\,$ を, 位置$k\,$の客のクラス$c_{k}\,$とその客の残余サービス必要量 (サービス必要量の分布が相型分布(phase distribution)の場合は客のいる相番号))$\phi _{k}\,$を用いて，${\boldsymbol {x_{i}}}=(c_{1},\phi _{1},c_{2},\phi _{2},\cdots ,c_{m},\phi _{m})\,$と表現する． ノード$i\,$の状態が ${\boldsymbol {x_{i}}}\,$ であるときこのノードに客が到着すると, 客は確率 $\gamma (m+1,k)\,$ で位置$k\,$を選択し, このとき位置 $l>k\,$ にいた客は位置$l+1\,$に移る. また, 状態 ${\boldsymbol {x_{i}}}\,$において位置$k\,$の客が退去すると, 位置 $l>k\,$ にいた客は位置 $l-1\,$ に移る. さらに, ノード$i\,$の状態が ${\boldsymbol {x_{i}}}\,$ であるとき, このノードの総サービス率は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi(m)\, } で与えられ, 総サービス率は位置kの客に $\gamma (m,k)\,$ の割合で配分される. すなわち, 位置構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } の客のサービス率は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi(m) \gamma(m, k)\, } となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する.

平均応答時間 ケリーネットワークでは，客を種類に分け，種類ごとに客がサービスを受けるノードの列を前もって決めることができる．この経路選択は客の種類を適切に与えると通常のマルコフ的経路選択と等価であることが証明できる．このように客がサービスを受けるノードの列$i_{1},i_{2},\ldots ,i_{n}$が前もって与えられ，各ノードでのサービス必要量が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{1}, x_{2}, \ldots, x_{n}} である客が到着したという条件の下で，その客の到着から退去までの時間の条件付き期待値を平均ネットワーク応答時間と呼ぶ．対称型サービスでは，上記の客が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 番目のノードに到着してから退去するまでの平均応答時間が客のサービス必要量構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{k}} に比例し，平均ネットワーク応答時間は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{1}, x_{2}, \ldots, x_{n}} の線形和となることが知られている（[3]参照）．

不感性 対称型サービス規律では，各ノードの状態確率がサービス時間分布の形とは無関係に，その平均値のみによって定まる．この性質は不感性(insensitivity)と呼ばれている．また，局所平衡が成り立つネットワークは不感性であることもわかる． 不感性をもつ代表的なシステムの例としては，呼がポアソン過程に従って発生する回線交換網(circuit switching network)が挙げられ，呼損率は保留時間の分布形に関係なく平均値によってのみ定まる．

局所平衡 BCMPやケリーネットワークの特徴は，局所平衡(local balance)方程式を満たすことにある． これによって，積形式解が直接導かれ，また積形式解が大域平衡 (global balance)方程式を満足すること(定常分布であること)も容易に証明できる． また，サービス時間分布が一般の場合は，対称型サービス規律はサービス位置を区別した最も詳細な局所平衡方程式が成り立つための必要十分条件となる．対称型サービス規律はこの局所平衡方式から自然に導かれたと考えられる．

　

---

参考文献

[1] F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers," Journal of Association for Computing Machinery, 22 (1975), 248-260.

[2] F. P. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, 1979.

[3] M. Miyazawa, R. Schassberger and V. Schmidt, "On the structure of an insensitive generalized semi-Markov process with reallocation and with point-process input," Advances in Applied Probability (1995), 203-225.

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

[5] 橋田温, 「最近のネットワーク手法」, 『オペレーションズ・リサーチ』, 26 (1981), 205-212.