QNA読解：5.1 GI/G/1待ち行列（５）

待ち行列ネットワークへの助走

上位エントリー：Word Whitt: The Queueing Network Analyzerの構成


「QNA読解：5.1 GI/G/1待ち行列（４）」の続きです。
今度はジョブの待ち時間Wの確率分布を近似的に導き出してしまおうとする試みです。これにはすでに私たちが持っている以下の情報を用います。

まずはP(W>0)から、P(W=0)を求めます。これは確率「密度」ではなく、確率です。次にW>0の場合についてDの分布からWの分布を求めます。そのDの分布はEDとc_D^2から推定します。（私にはEDとc_D^2だけから分布を推定するのは乱暴な気もするのですが・・・・）。まず基本はc_D^2=1に近い場合には、Dの分布は指数分布になる、という仮定です（この仮定の妥当性を調べる必要がありそうですね）。そしてc_D^2が1より大きければDの確率分布をバランスのとれた平均を持つ超指数分布で、1より小さければ２つの指数分布の畳み込み、または、アーラン分布で近似する、というものです。
論文に書いてある結論は、このようになっています。

ケース１：c_D^2>1.01の場合。Dの分布をバランスのとれた平均を持つ超指数分布で近似

その確率分布は

  • f_d(x)=p\gamma_1\exp(-\gamma_1x)+(1-p)\gamma_2\exp(-\gamma_2x)、 x{\ge}0・・・・(55)
  • ただし
    • p=\left[1+\sqrt{(c_D^2-1)/(c_D^2+1)}\right]/2・・・・(56-1)
    • \gamma_1=2p/ED・・・・(56-2)
    • \gamma_2=2(1-p)/ED・・・・(56-3)

です。(56-1)、(56-2)、(56-3)の導出方法は「バランスのとれた平均を持つ超指数分布」を参照下さい。なお、論文では変数xを用いていますが、Dは時間であるので、本来であれば変数tを使うべきだと私は思います。分布の形の例をグラフに示します。（ED=1）

ケース２：0.99{\le}c_D^2{\le}1.01の場合。Dの分布を平均EDを持つ指数分布で近似

ケース３：0.501{\le}c_D^2<0.99の場合。Dの分布をパラメータ\gamma_1と\gamma_2(\gamma_1>\gamma_2)を持つ２つの指数分布の畳み込みで近似

その確率分布は

  • f_D(x)=\left(\frac{\gamma_1\gamma_2}{\gamma_1-\gamma_2}\right)[\exp(-\gamma_2x)-\exp(-\gamma_1x)]、 x{\ge}0・・・・(57)
  • ただし
    • \gamma_2^{-1}=\frac{ED+\sqrt{2Var(D)-(ED)^2}}{2}・・・・(58-1)
    • \gamma_1^{-1}=ED-\gamma_2^{-1}・・・・(58-2)

です。この分布の裾野確率P(D>x)は

  • P(D>x)=[\gamma_1\exp(-\gamma_2x)-\gamma_2\exp(-\gamma_1x)]/(\gamma_1-\gamma_2)・・・・(59)

式(57)の分布が正規化されていること、その平均がEDになること、分散がVar(D)になることの確認は「２つの指数分布の畳込み」に示します。また、裾野確率が式(59)になることの確認もそこで示します。分布の形の例をグラフに示します。（ED=1）

なお、c^2=0.5になると\gamma_1=\gamma_2となってしまい、式(57)が計算不能になりますので、このグラフにはc^2=0.5を載せていません。c^2=0.5の場合には次のケース４で扱います。

ケース４：c_D^2<0.501の場合。Dの分布を平均ED、２乗変動係数c^2=0.5を持つ２次のアーラン分布で近似

その確率分布は

  • f_D(x)=\gamma^2x\exp(-{\gamma}x)、 x{\ge}0・・・・(60)
  • ただし
    • \gamma=2/ED・・・・(60-1)

です。この分布の裾野確率P(D>x)は

  • P(D>x)=\exp(-\gamma{x})(1+\gamma{x})、 x{\ge}0・・・・(61)

裾野確率が式(61)になることは以下のように確かめることが出来ます。

  • P(D>x)=\Bigint_x^{\infty}f_D(t)dt=\Bigint_x^{\infty}\gamma^2t\exp(-{\gamma}t)dt=\left[-\gamma{t}\exp(-{\gamma}t)\right]_x^{\infty}-\Bigint_x^{\infty}(-\gamma)\exp(-{\gamma}t)dt
    • =\gamma{x}\exp(-{\gamma}x)+\Bigint_x^{\infty}\gamma\exp(-{\gamma}t)dt=\gamma{x}\exp(-{\gamma}x)+\left[-\exp(-{\gamma}t)\right]_x^{\infty}
    • =\gamma{x}\exp(-{\gamma}x)+\exp(-{\gamma}x)=\exp(-{\gamma}x)(1+{\gamma}x)

分布の形の例をグラフに示します。（ED=1）


分布はEDとc_D^2の値を満たすように定める方針でしたが、論文に

これは一般ルールであって、以下のケース２と４ではあまり従っていない。

とありますように、ケース２と４ではc_D^2の値は近似分布から求めた値と異なっています。


「QNA読解：5.1 GI/G/1待ち行列（６）」に続きます。