損失ネットワーク

待ち行列理論では、ロスネットワークは、通話がノード間のネットワークを迂回する電話ネットワークの確率モデルです。ノード間のリンクには容量が限られているため、到着した通話の中には、宛先までのルートが見つからないものもあります。これらの通話はネットワークから失われるため、ロスネットワークと呼ばれます。^[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 で指数分布した時間の長さにわたってネットワークを占有します。通話を受け入れるのに十分な容量が個々のリンクにない場合、通話はネットワークから拒否されます (失われます)。^[5]

時刻tにおけるルートr上の通話数をn _r ( t ) 、ベクトル ( n _r ( t ) : r in R ) をn ( t ) 、C = ( C ₁ , C ₂ , ... , 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点スライス法