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

出典: ORWiki

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

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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E5%B8%8C%E5%B0%91%E4%BA%8B%E8%B1%A1%E3%81%AE%E8%A9%95%E4%BE%A1%E3%80%8B" より作成