BCMPネットワーク

待ち行列理論（数学的確率論の一分野）において、BCMPネットワークは、積形均衡分布が存在する待ち行列ネットワークの一種である。このネットワークは、このネットワークを初めて記述した論文の著者であるバスケット、チャンディ、ムンツ、パラシオスにちなんで名付けられている。この定理は、ジャクソンネットワークの重要な拡張であり、特定のサービス規律の下で、事実上任意の顧客ルーティングとサービス時間分布を可能にする。^[1]

この論文はよく知られており、この定理は1990年にJ.マイケル・ハリソンとルース・J・ウィリアムズによって「過去20年間の待ち行列理論における重要な成果の1つ」と評されました。^[2]

意味

m 個の相互接続されたキューのネットワークは、各キューが次の 4 つのタイプのいずれかである場合、 BCMP ネットワークと呼ばれます。

1. FCFS規律では、すべての顧客が同じ負の指数分布を持つサービス時間分布を持ちます。サービス率は状態に依存する可能性があるため、キューの長さがjのときのサービス率を と書きます。${\displaystyle \scriptstyle {\mu_{j}}}$
2. プロセッサ共有キュー
3. 無限サーバーキュー
4. 事前再開機能付きLCFS （作業は失われません）

最後の3つのケースでは、サービス時間分布は有理 ラプラス変換を持つ必要がある。つまり、ラプラス変換は^{[3]の形式である必要がある。}

${\displaystyle L(s)={\frac {N(s)}{D(s)}}.}$

また、以下の条件を満たす必要があります。

1. ノードiへの外部到着（もしあれば）はポアソン過程を形成する。
2. キューiでサービスを完了した顧客は、 （固定の）確率で新しいキューjに移動する、または、キューのサブセットによってはゼロではない確率でシステムを離れます。${\displaystyle P_{ij}}$ ${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$

定理

m個のキューからなるBCMPネットワーク（オープン、クローズ、または混合）において、各キューがタイプ1、2、3、または4である場合、平衡状態確率は次のように与えられる。

${\displaystyle \pi (x_{1},x_{2},\ldots ,x_{m})=C\pi _{1}(x_{1})\pi _{2}(x_{2})\cdots \pi _{m}(x_{m}),}$

ここで、Cは平衡状態の確率の合計が1になるように選択された正規化定数であり、キューiの平衡分布を表します。 ${\displaystyle \scriptstyle {\pi _{i}(\cdot )}}$

証拠

定理の元々の証明は、独立したバランス方程式が満たされていることを確認することによって与えられました。

ピーター・G・ハリソンは逆の過程を考慮した別の証明^{[4]を提示した[5] 。}

参考文献

1. Baskett, F.; Chandy, K. Mani ; Muntz, RR; Palacios, FG (1975). 「異なる顧客層を持つ待ち行列の開回路網、閉回路網、混合ネットワーク」Journal of the ACM . 22 (2): 248– 260. doi : 10.1145/321879.321887 . S2CID  15204199.
2. Harrison, JM ; Williams, RJ (1990). 「多クラスブラウン運動サービスステーションの準可逆性について」.確率年報. 18 (3). 数理統計研究所: 1249–1268 . doi : 10.1214/aop/1176990745 . JSTOR  2244425.
3. Sinclair, Bart. 「BCMP定理」. Connexions . 2011年8月14日閲覧。
4. Harchol-Balter, M. (2012). 「タイムシェアリング（PS）サーバー（BCMP）を備えたネットワーク」.コンピュータシステムのパフォーマンスモデリングと設計. pp.  380– 394. doi :10.1017/CBO9781139226424.029. ISBN 9781139226424。
5. Harrison, PG (2004). 「逆過程、積形式、そして非積形式」.線形代数とその応用. 386 : 359–381 . doi : 10.1016/j.laa.2004.02.020 .