《待ち行列における希少事象の評価》

提供: ORWiki
2007年8月7日 (火) 03:21時点におけるKuwashima (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【まちぎょうれつにおけるきしょうじしょうのひょうか (rare event evalution of queueing systems) 】

 待ち行列理論は, 電話トラヒックの輻輳を解析することから始まったのであるが, ここで述べる「待ち行列における溢れ確率 (overflow probability) 近似」は, 近年普及してきたマルチメディア通信ネットワークの輻輳を解析する必要性から始まったと言える [5]. それでは従来の待ち行列と何が異なるか? 一つは, 従来良く用いられたポアソン入力や再生過程入力とは異なり, 強い相関を持つ入力トラヒックを対象にしたこと, もう一つは, 評価すべき溢れ確率がのオーダの極めて稀な確率事象を対象にしたことである. 以下, これらの課題から生まれた新たな入力モデルや解析手法について簡単に述べる.


流体近似モデル 待ち行列モデルとしてマルチメディア通信ネットワークで用いられる穴あきバケツモデル (bucket-with-hole model) の離散時間版を考える. 時刻入力率 (input rate) を, 出力率をとすると, 時刻での待ち行列長


     


で表される. ここで, をEの定常過程とすると, 定常状態における溢れ確率P


     


で与えられる. 但し, , である. 番目の客のサービス時間番目と番目の客の到着間隔の差と考えるならば, (2) は先着順サービスのG/G/1待ち行列における待ち時間分布の裾 (tail of waitingtime distribution)となる. これは, (1) で表される待ち行列モデルが特殊なモデルではなく, 従来から議論されている待ち行列モデルと基本的に変わらないことを意味している. 従来と大きく異なるところは, 入力として強い相関をもつマルコフ型入力過程長期依存型入力過程 (long-rangedependent input process)が議論されるようになったことである.


漸近解析 ところで, 溢れ確率の解析手法については, が閾値を越える事象が極めて稀な場合を考えているため, 大偏差理論 (large deviation theory)を用いた漸近解析 (asymptotic analysis)が注目を浴びるようになった. ここでは, 長期依存型入力を含む一般的な入力過程の場合の漸近解析を説明する [3].



が存在するように適当な増加数列を与える. 但し, . このとき, 大偏差理論のGärtner-Ellisの定理 [1] から, 任意のに対して



が成り立つ. 但し, . 更に



の不等式において, が十分大きいところではオーダの意味で



となる. ここで, である. これは, 大偏差理論における稀な事象が生起するときの基本的な性質である. つまり, (2)の右辺は負のドリフトを持つ確率過程が閾値にヒットする確率と解釈できるが, もしヒットするならば最も可能性の高い時点, ここでは, でヒットすることを意味する. これらの議論から溢れ確率に関して


     


が得られる. (3) は緩やかに変動する関数が存在して


     


であることを意味する. 具体的な入力過程で計算するならば, 短期依存型であるマルコフ型入力過程のときは, となり, 溢れ確率は指数的に減衰する. 一方, 長期依存型入力過程の多くはとなり, 溢れ確率が指数より緩やかに減衰する.


 入力の多重数とそれに比例して出力率, 閾値を増加させたときの溢れ確率 も同様な考え方で漸近解析が行なわれている [2]. 多重数の入力率は, 個の入力率を単純に足したものである. 結果だけを記述すると任意のに対して


     


となる. 但し, , である.


 本結果も,長期依存型入力に適用できる.

 以上, 離散時間の場合を議論してきたが, 連続時間のモデルに対しても同様な結果が得られる. なお,本内容については参考文献 [4] にも書かれている.



参考文献

[1] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Jones and Bartlett Publishers, 1993.

[2] N. G. Duffield, "Economies of Scale for Long-Range Dependent Traffic in Short Buffers," Telecommunication Systems, 7 (1997), 267-280.

[3] N. G. Duffield and N. O'Connell, "Large Deviations and Overflow Probabilities for the General Single-Server Queue, with Ppplications," Mathematical Proceedings of the Cambridge Philosophical Society, 118 (1995), 363-374.

[4] A. Ganesh, N. O'Connell and D. Wischik, Big Queues, Springer, 2004.

[5] 小林和朝, 「マルチメディア情報流に対する流体近似」, 『応用数理』, 9 (1999), 46-59.