《待ち行列ネットワーク(BCMP型とその応用)》
【まちぎょうれつねっとわーく (びーしーえむぴーがた) (BCMP network) 】
待ち行列ネットワーク (queueing network) において, ネットワーク全体の定常分布が各ノードの状態の周辺分布の積として表されるとき, このようなネットワークは一般に積形式解 (product form solution) を持つといわれる. 最初に研究された一連の積形式ネットワークは, ジャクソンネットワーク (Jackson network) と呼ばれている. ジャクソンネットワークは, 定常分布の表現が簡単であるので広く応用されてきたが, 経路をあらかじめ選択できない, 指数サービスに限定される, などモデルの制約が強い. これに対して, ジャクソンネットワークを拡張して, 客に客のクラスを設け, かつより一般的なサービス機構にしても積形式解をもつことが, Baskettら [1] やKelly [2] の研究によって明らかにされた. ここでは, 前者をBCMPネットワーク (BCMP network) [3], 後者をケリーネットワーク (Kelly network) と呼ぶ.
BCMPネットワーク BCMPネットワークは, 次のように定義される.
- ネットワークは$M$個のノードから成り, 客は$C$個のクラスのいずれかに属する. この他に外部を表すノード$0$があるとする.
- 外部から到着した客は, 確率$r_{0, (i, c)}$でノード$i$に行き, クラス$c$の客となる. ノード$i$のクラス$c$の客は, サービス終了後確率$r_{(i, c), (j, d)}$でノード$j$のクラス$d$の客となり, 確率$r_{(i, c), 0}$でネットワークから退去する.
- 客は外部から率$\lambda$のポアソン過程に従って到着する. (到着率は, ネットワーク内の人数, または経路選択行列で構成されるマルコフ連鎖の部分連鎖の人数に依存してもよい. )
- 各ノードのサービス規律は先着順, プロセッサ・シェアリング, 無限サーバ, 後着順割込継続型のいずれかにしたがう. 各クラスの客のサービス要求量の分布は, 先着順の場合はクラス共通の指数分布のみであるが, その他の場合はクラスに依存してもよく, 任意の分布が許される.
$r_{0, (i, c)}$, $r_{(i, c), (j, d)}$, $r_{(i, c), 0}$などで表される確率による経路選択はネットワークの状態とは独立であると仮定されるので, このような経路選択をマルコフ的経路選択ともいう. マルコフ的経路選択では, すべてのノード, クラスのペア $(i, c)$ に対して正の経路選択確率をたどって外部から到達でき, また正の経路選択確率をたどって外部に出られるならば開放型 (open network), すべてのノード, クラスのペアに対して$r_{0, (i, c)}=0$, $r_{(i, c), 0}=0$であれば閉鎖型 (closed network) である.
積形式定常状態確率 いま, ノード$i$への客の到着をトラヒック方程式 (traffic equation)
\lambda_{(i, c)} = \lambda r_{0, (i, c)} + \sum_{j=1}^M \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$の状態 {\mbox{\boldmath $x_i$}} を, 位置$k$の客のクラス$c_k$とその客の残余サービス要求量 (サービス要求量の分布が相型分布の場合は客のいる相番号)$\phi_k$を用いて, ${\mbox{\boldmath $x_i$}} = (c_1, \phi_1, c_2, \phi_2, \cdots, c_m, \phi_m)$ と表現する. ノード$i$の状態が ${\mbox{\boldmath $x_i$}}$ であるときこのノードに客が到着すると, 客は確率 $\gamma(m+1, k)$ で位置$k$を選択し, このとき位置 $l>k$ にいた客は位置$l+1$に移る. また, 状態 ${\mbox{\boldmath $x_i$}}$において位置$k$の客が退去すると, 位置 $l>k$ にいた客は位置 $l-1$ に移る. さらに, ノード$i$の状態が ${\mbox{\boldmath $x_i$}}$ であるとき, このノードの総サービス率は $\varphi(m)$ で与えられ, 総サービス率は位置$k$の客に $\gamma(m, k)$ の割合で配分される. すなわち, 位置$k$の客のサービス率は $\varphi(m) \gamma(m, k)$ となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する. また, 対称型サービスでは, 客がノードに到着してから退去するまでの平均応答時間が, その客のサービス要求量に比例することが知られている.
BCMPやケリーネットワークの特徴は, 局所平衡 (local balance) 方程式を満たすことにある. これによって, 積形式解が直接導かれ, また積形式解が大域平衡 (global balance) 方程式を満足すること (定常分布であること)も容易に証明できる. また, サービス時間分布が一般の場合は, 対称型サービス規律はサービス位置を区別した最も詳細な局所平衡方程式が成り立つための必要十分条件となる. 対称型サービス規律はこの局所平衡方式から自然に導かれたと考えられる.
対称型サービス規律では, 各ノードの状態確率がサービス時間分布の形とは無関係に, その平均値のみによって定まる. この性質は不感性 (insensitivity)と呼ばれている. また, 局所平衡が成り立つネットワークは不感性をもつこともわかる. 不感性をもつ代表的なシステムの例としては, 呼がポアソン過程に従って発生する回線交換網 (circuit switching network) が挙げられ, 呼損率は保留時間の分布形に関係なく平均値によってのみ定まる.
ネットワークが積形式解をもつ証明の別法として, 元の確率過程の時間を逆転した逆過程 (reversed process) を用いる方法が提案されている [2], [4]. 関連した方法に準可逆性(quasi-reversibility) という性質を使う証明がある. この場合には, 各ノードが準可逆性を持つことを示し, 準可逆性を持つノードをマルコフ的経路選択で結合すると積形式ネットワークとなることを利用する. この方法は, 積形式を持つネットワークを構成するためにも有効な方法である.
参考文献
[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] 橋田温, 「最近のネットワーク手法」, 『オペレーションズ・リサーチ』, 26 (1981), 205-212.
[4] J. Walrand, An Introduction to Queueing Networks, Prentice-Hall, 1988.