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

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

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

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

$Q_{n}=\max\{Q_{n-1}+U_{n},0\},\qquad U_{n}=X_{n}-C,\,$　　　　　$(1)\,$

で表される. ここで, $\{X_{n}\}\,$をE$(X_{n})<C\,$の定常過程とすると, 定常状態における溢れ確率P$(Q>x)\,$は

${\mbox{P}}(Q>x)={\mbox{P}}\left(\sup _{n\geq 0}\{A_{n}\}>x\right)\,$　　　　　$(2)\,$

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

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

$\psi (\theta )\equiv \lim _{n\rightarrow \infty }v(n)^{-1}\log {\mbox{E}}[\mathrm {e} ^{\theta A_{n}v(n)/a(n)}],\;\;\;\;g(y)\equiv \lim _{n\rightarrow \infty }{\frac {v(a^{-1}(n/y))}{h(n)}}\,$

が存在するように適当な増加数列$\{v(n)\},\{a(n)\},\{h(n)\}\,$を与える. 但し, $a^{-1}(z)\,$ $\equiv \sup\{n:a(n)\leq z\}\,$. このとき, 大偏差理論のGärtner-Ellisの定理 [1] から, 任意の$y>0\,$に対して

$\lim _{n\rightarrow \infty }v(n)^{-1}\log {\mbox{P}}(A_{n}/a(n)>y)=-\psi ^{*}(y)\,$

が成り立つ. 但し, $\textstyle \psi ^{*}(y)\equiv \sup _{\theta }\{\theta y-\psi (\theta )\}\,$. 更に

$\sup _{n\geq 0}{\mbox{P}}(A_{n}>x)\leq {\mbox{P}}(\sup _{n\geq 0}\{A_{n}\}>x)\leq \sum _{n}{\mbox{P}}(A_{n}>x)\,$

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

$\sup _{n\geq 0}{\mbox{P}}(A_{n}>x)\approx \sum _{n}{\mbox{P}}(A_{n}>x)\approx {\mbox{P}}(A_{a^{-1}(x/y^{*})}>x)\,$

となる. ここで, $\textstyle y^{*}=\arg \inf _{y>0}g(y)\psi ^{*}(y)\,$である. これは, 大偏差理論における稀な事象が生起するときの基本的な性質である. つまり, (2)の右辺は負のドリフトを持つ確率過程$\{A_{n}\}\,$が閾値$x\,$にヒットする確率と解釈できるが, もしヒットするならば最も可能性の高い時点$n\,$, ここでは$a^{-1}(x/y^{*})\,$, でヒットすることを意味する. これらの議論から溢れ確率に関して

$\lim _{x\rightarrow \infty }h(x)^{-1}\log {\mbox{P}}(Q>x)=-g(y^{*})\psi ^{*}(y^{*})\,$　　　　　$(3)\,$

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

${\mbox{P}}(Q>x)=B(x)\mathrm {e} ^{-\kappa h(x)},\qquad \kappa =g(y^{*})\psi ^{*}(y^{*}),\,$　　　　　$(4)\,$

であることを意味する. 具体的な入力過程で計算するならば, 短期依存型であるマルコフ型入力過程のときは, $h(x)=x\,$となり, 溢れ確率は指数的に減衰する. 一方, 長期依存型入力過程の多くは$h(x)=x^{\beta },\beta \in (0,1)\,$となり, 溢れ確率が指数より緩やかに減衰する.

　入力の多重数$L\,$とそれに比例して出力率, 閾値を増加させたときの溢れ確率 ${\mbox{P}}(Q^{L}>Ly)\,$も同様な考え方で漸近解析が行なわれている [2]. 多重数$L\,$の入力率は, $L\,$個の入力率$X_{n}^{(l)},l=1,\cdots ,L\,$を単純に足したものである. 結果だけを記述すると任意の$y>0\,$に対して

$\lim _{L\rightarrow \infty }L^{-1}\log {\mbox{P}}(Q^{L}>Ly)=-\inf _{n>0}\psi _{n}^{*}(y)\,$　　　　　$(5)\,$

となる. 但し, $\textstyle \psi _{n}(\theta )=\lim _{L\rightarrow \infty }L^{-1}\log {\mbox{E}}[\mathrm {e} ^{\theta A_{n}^{L}}]\,$, $\textstyle \psi _{n}^{*}(y)\equiv \sup _{\theta }\{\theta y-\psi _{n}(\theta )\}\,$である.

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

　以上, 離散時間の場合を議論してきたが, 連続時間のモデルに対しても同様な結果が得られる. なお，本内容については参考文献 [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.