損失ネットワーク

待ち行列理論において、ロスネットワークとは、通話がノード間のネットワークを迂回してルーティングされる電話ネットワークの確率モデルです。ノード間のリンク容量は有限であるため、到着した通話の中には、宛先への利用可能な経路が見つからないものもあります。これらの通話はネットワークから失われるため、ロスネットワークと呼ばれます。^[1]

損失ネットワークは、アーランによって最初に単一の電話リンクを対象に研究されました。^[2] フランク・ケリーは、1991年の論文「損失ネットワーク」^{[4] [5]で}フレデリック・W・ランチェスター賞^[3]を受賞し、損失ネットワークの挙動がヒステリシスを示す可能性があることを示しました。

モデル

固定ルーティング

1、2、…、Jとラベル付けされたJ個のリンクがあり、各リンクjにC _{j 個の}回線があるネットワークを考えます。R をネットワーク内のすべての可能なルート（通話が使用する可能性のあるリンクの組み合わせ）の集合とし、各ルートrについて、リンクjでルートrが使用する回線の数をA _jrと書きます（したがって、 AはJ x | R | 行列です）。Aのすべての要素が 0 または 1 で、各ルートrについて、そのルートの使用を必要とする通話がレートv _rのポアソン過程に従って到着する場合を考えます。通話が到着すると、必要なすべてのリンクに十分な容量が残っている場合、その通話は受け入れられ、パラメータ 1 で指数分布の時間だけネットワークを^占有します。

時刻tにおける経路r上の通話数をn _r ( t ) 、ベクトル ( n r ( t ) : r in R ) をn ₍ t )、C = ( C 1 , C 2 , ... _, C J ₎と書く_。このとき、連続時間マルコフ過程n ( t ) は唯一の定常分布に従う^[5]

${\displaystyle \pi (n)=G(C)^{-1}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}{\text{ }}n\in S(C)}$

どこ

${\displaystyle S(C)=\{n\in \mathbb {Z} _{+}^{R}:An\leq C\}}$

そして

${\displaystyle G(C)=\left(\sum _{n\in S(C)}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}\right).}$

この結果から、適切な状態を合計することで、異なるルートで到着する通話の損失確率を計算できます。

損失確率の計算

損失ネットワークにおける損失確率を計算するための一般的なアルゴリズムがある^[6]

1. アーラン固定小数点近似
2. スライス法
3. 3点スライス法

注記

1. ハリソン, ピーター G. ; パテル, ナレシュ M. (1992).通信ネットワークとコンピュータアーキテクチャのパフォーマンスモデリング. アディソン・ウェズレー. p. 417. ISBN 0201544199。
2. Zachary, S.; Ziedins, I. (2011). 「ロスネットワーク」.キューイングネットワーク. オペレーションズ・リサーチ＆マネジメントサイエンス国際シリーズ. 第154巻. p. 701. doi :10.1007/978-1-4419-6472-4_16. ISBN 978-1-4419-6471-7。
3. 「フレデリック・W・ランチェスター賞」informs. 2010年12月31日時点のオリジナルよりアーカイブ。2010年11月17日閲覧。
4. 「損失ネットワーク」フランク・ケリー. 2010年11月17日閲覧。
5. Kelly, FP (1991). 「損失ネットワーク」.応用確率論年報. 1 (3): 319. doi : 10.1214/aoap/1177005872 . JSTOR  2959742.
6. Jung, K.; Lu, Y.; Shah, D.; Sharma, M.; Squillante, MS (2008). 「確率的損失ネットワークの再考」 2008 ACM SIGMETRICS 国際会議「コンピュータシステムの測定とモデリング」の議事録 - SIGMETRICS '08 (PDF) . p. 407. doi :10.1145/1375457.1375503. ISBN 9781605580050。