BCMPネットワーク

提供:ORWiki
移動: 案内, 検索

【 びーしーえむぴーねっとわーく (BCMP (Baskett, Chandy, Muntz and Palacios) network) 】


概要

客数ベクトルの定常確率が積形式で与えられる待ち行列ネットワーク のひとつで, ジャクソン型を拡張してにクラスを設け, サービス規律をより一般的にしたもの. サービス時間分布は, 先着順の場合は指数分布のみであるが, プロセッサ・シェアリング, 無限サーバ, 後着順割込継続型の場合は, 任意の分布が許される. この結果は1975年にバスケット(F. Baskett)らによって発表されたが, その後この論文の著者4人のイニシャルをとって,BCMP型と呼ばれている.

詳説

 待ち行列ネットワーク (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}\, であるとき, このノードの総サービス率は \varphi(m)\, で与えられ, 総サービス率は位置kの客に \gamma(m, k)\, の割合で配分される. すなわち, 位置k\, の客のサービス率は \varphi(m) \gamma(m, k)\, となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する.


平均応答時間 ケリーネットワークでは,客を種類に分け,種類ごとに客がサービスを受けるノードの列を前もって決めることができる.この経路選択は客の種類を適切に与えると通常のマルコフ的経路選択と等価であることが証明できる.このように客がサービスを受けるノードの列i_{1}, i_{2}, \ldots, i_{n}が前もって与えられ,各ノードでのサービス必要量がx_{1}, x_{2}, \ldots, x_{n}である客が到着したという条件の下で,その客の到着から退去までの時間の条件付き期待値を平均ネットワーク応答時間と呼ぶ.対称型サービスでは,上記の客がk\, 番目のノードに到着してから退去するまでの平均応答時間が客のサービス必要量x_{k}に比例し,平均ネットワーク応答時間は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.

個人用ツール