(57)【要約】【課題】到着過程及びサービス時間分布の平均及び分散を入力としてキュー遅延の確率分布を算出することを目的とする。【解決手段】キュー遅延を算出するキュー遅延算出装置は、キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出する系内数推定手段と、算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するキュー遅延分布算出手段とを有する。【選択図】図１
2015019159.tif 000002
【特許請求の範囲】
【請求項１】
キュー遅延を算出するキュー遅延算出装置であって、
キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出する系内数推定手段と、
算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するキュー遅延分布算出手段と、
を有するキュー遅延算出装置。
【請求項２】
前記系内数推定手段は、定常状態における系内数分布を更に算出する、請求項１に記載のキュー遅延算出装置。
【請求項３】
前記系内数推定手段は、時刻tにおける系内数の近似値xの確率密度関数f(x,t)：
【数１４】
2015019159.tif 000016
ただし、(α,β)=(λK_a+μK_s,λ-μ)、
(λ,K_a,μ,K_s)はそれぞれ平均到着率、到着間隔の変動係数、平均サービス率、サービス時間の変動係数、
Λ-1は系内数が0となる時間間隔の平均、R(t)は時刻tにおける系内数0の確率、
*、*xはそれぞれ(x,t)及びxに関する畳み込み、δ(・)、H(・),はそれぞれDiracのデルタ関数、Heavisideのステップ関数、
を用いて、系内数分布を算出する、請求項１又は２に記載のキュー遅延算出装置。
【請求項４】
前記キュー遅延分布算出手段は、時刻tにおける系内数kの確率密度P(k,t)：
【数１５】
2015019159.tif 000017
を算出し、系内の処理時間がy以下である確率：
【数１６】
2015019159.tif 000018
を、系内数kに関する漸近展開により近似的に陽な表現を求め、キュー遅延Wtの確率密度関数P(Wt≦y)：
【数１７】
2015019159.tif 000019
を算出する、請求項３に記載のキュー遅延算出装置。
【請求項５】
通信機器に到達するパケットを観測することにより、到着時間の２次までのモーメント観測値である平均及び分散を同定し、当該通信機器の通過時間を観測することにより、サービス時間のN次までのモーメント観測値を同定する入力情報同定手段を更に有する、請求項１乃至４のうちいずれか１項に記載のキュー遅延算出装置。
【請求項６】
キュー遅延を算出するキュー遅延算出装置におけるキュー遅延算出方法であって、
前記キュー遅延算出装置の系内数推定手段が、キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出するステップと、
前記キュー遅延算出装置のキュー遅延分布算出手段が、算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するステップと、
を有するキュー遅延算出方法。
【請求項７】
キュー遅延を算出するキュー遅延算出装置として、コンピュータを機能させるためのプログラムであって、当該コンピュータを
キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出する系内数推定手段、及び
算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するキュー遅延分布算出手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、待ち行列シミュレーションに関する技術であり、待ち行列モデルによる待ち行列遅延のシミュレーションを行うキュー遅延算出装置、キュー遅延算出方法及びプログラムに関する。
【背景技術】
【０００２】
一般的な待ち行列モデルは、キューへの到着を表す到着過程と、サービスに必要なサービス時間と、サービスの数によって表される。
【０００３】
到着過程もサービス時間も共にマルコフ的でない場合、非マルコフモデルと呼ばれる。非マルコフモデルに対する近似法は複数存在するが、それらの近似法の中でも、普遍性を持ち、システム性能尺度が結果的に容易に得られるものとして拡散近似法が知られている。拡散近似とは、非マルコフ待ち行列システムにおけるシステム性能評価尺度を得るために、系内客数過程あるいは仮待ち時間過程を拡散方程式で記述する定式化である。これにより、キュー遅延の近似値を容易に算出することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】E. Gelenbe, "Probabilistic models of computer systems, Part II, Diffusion approximations, waiting times and batch arrivals," Acta Informatica, vol. 12, pp.285-303, 1979.
【非特許文献２】高橋敬隆：「拡散近似法（非マルコフモデル近似式導出法）」，電子情報通信学会知識ベース，2010.http://www.ieice-hbkb.org/files/05/05gun_01hen_03.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００５】
到着過程やサービス時間の一方または双方が所定のよく知られた分布に従う待ち行列モデル、例えばM/D/1モデルにおいては、系内数分布の理論値が帰納的にではあるが陽に算出可能である。しかし、到着過程とサービス時間分布の双方とも一般の確率分布に従うGI/GI/1モデルにおいては、陽に系内数分布を算出することが困難である。前記の拡散近似はよく知られる手法であり、その適用により数値的に近似解の構成も可能である。しかしながら、GI/GI/1モデルの場合には、拡散近似の陽な解が知られていないため、拡散近似モデルの妥当性や、数値計算における誤差、定常解への収束可否やモデルに課されるべき条件が不明である。
【０００６】
また、系内数の分布が得られても、それに基づき直接キュー遅延を算出することができない。
【０００７】
本発明は、上記の問題に鑑み、待ち行列モデルGI/GI/1におけるキュー遅延分布の近似値を算出することを目的とする。具体的には、本発明は、待ち行列モデルGI/GI/1において、容易に入手可能な到着過程及びサービス時間分布の平均及び分散を入力としてキュー遅延の確率分布を算出することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一形態に係るキュー遅延算出装置は、
キュー遅延を算出するキュー遅延算出装置であって、
キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出する系内数推定手段と、
算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するキュー遅延分布算出手段と、
を有することを特徴とする。
【０００９】
本発明の一形態に係るキュー遅延算出方法は、
キュー遅延を算出するキュー遅延算出装置におけるキュー遅延算出方法であって、
前記キュー遅延算出装置の系内数推定手段が、キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出するステップと、
前記キュー遅延算出装置のキュー遅延分布算出手段が、算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するステップと、
を有することを特徴とする。
【００１０】
本発明の一形態に係るプログラムは、
キュー遅延を算出するキュー遅延算出装置として、コンピュータを機能させるためのプログラムであって、当該コンピュータを
キューへの到着時間の２次までのモーメント観測値を入力として、拡散近似の陽な解を算出することにより、系内数分布を算出する系内数推定手段、及び
算出された系内数分布と、キューのサービス時間のN次（N≧2）までのモーメント観測値とを入力として、キュー遅延分布を算出するキュー遅延分布算出手段、
として機能させることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、到着過程及びサービス時間分布の平均及び分散を入力としてキュー遅延の確率分布を算出することが可能になる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施例に係るキュー遅延算出装置の構成図
【図２】本発明の実施例に係るキュー遅延算出装置の入力情報同定手段の例を示す図
【図３】本発明の実施例に係るキュー遅延算出方法のフローチャート
【図４】M/D/1系内数理論値と本発明の実施例に係るキュー遅延算出装置における推定結果との比較を示す図
【発明を実施するための形態】
【００１３】
以下、本発明の実施例について詳細に説明する。
【００１４】
本発明の実施例では、ネットワークのボトルネックリンクにおけるキュー遅延の確率分布近似値を、到着間隔については2次まで、サービス時間についてはN次まで（N≧2）のモーメント観測値を入力として出力するキュー遅延算出装置について説明する。
【００１５】
本発明の実施例に係るキュー遅延算出装置は、拡散近似の陽な解を算出して用いることにより、待ち行列モデルGI/GI/1において、容易に入手可能な到着過程及び待ち時間分布の平均及び分散を入力として、各時刻もしくは定常状態における系内数分布を出力する。次に、算出した系内数分布に基づき、キュー遅延の分布を算出する。ここではサービス時間のN次（N≧2）までのモーメント観測値を利用し、漸近展開を活用して当該時刻における到着パケットの待ち時間の分布を算出する。
【００１６】
図１に、本発明の実施例に係るキュー遅延算出装置の構成図を示す。キュー遅延算出装置は、系内数推定手段１０１と、キュー遅延分布算出手段１０２とを有する。また、以下に説明する通り、キュー遅延算出装置は、到着間隔の測定値及びサービス時間の測定値から、到着間隔の平均及び分散とサービス時間のN次までのモーメント観測値とを同定する入力情報同定手段１０３を更に有してもよい。
【００１７】
まず、入力情報同定手段１０３は、観測されたネットワーク情報から、到着間隔の平均及び分散とサービス時間のN次までのモーメント観測値とを同定し、系内数推定手段１０１への入力情報とする。例えば、図２に示すように、入力情報同定手段１０３は、ボトルネックリンクのルータの前後にて、パケットキャプチャデータから到着パケットの時間間隔を抽出し、その平均値及び標準偏差を算出する。サービス時間については、当該ルータの前後で時刻同期したパケットキャプチャ装置にてキャプチャを行い、ルータ通過時間を計測する。各パケットp_i(i=1,2,...,M)のルータ通過時間をそれぞれt_i(i=1,2,...,M)とすると、そのk次モーメント観測値μ_k(k=1,2,...,N)は以下の様に得ることができる。
【００１８】
μ_k=E[t_ik]
ただし、系内数推定手段１０１への入力情報は、別の装置で計測されてもよい。例えばサーバにおけるバッチ処理のような場合には、サーバ端末におけるログを活用してこれらの値を取得することも考えられる。
【００１９】
系内数分布算出手段１０１への入力としては、到着間隔及びサービス時間の2次までのモーメント観測値とする。系内数分布算出手段１０１は、下記に示す拡散近似の陽な解（２）と前記入力に基づき、所望の時刻tもしくは定常状態における系内数分布を算出、出力する。系内数推定手段１０１の出力は、キュー遅延分布算出手段１０２への入力とする。
【００２０】
系内数分布算出手段１０１が系内数分布の算出に利用する基本反射壁境界条件を採用したGI/GI/1の拡散近似は以下の様に表現される。
【００２１】
【数１】
2015019159.tif 000003
ここで方程式の係数は
(α,β)=(λK_a+μK_s,λ-μ)
により与えられ（非特許文献１参照）、前記入力された到着間隔及びサービス時間の2次までのモーメント観測値から算出するものとする。(λ,K_a,μ,K_s)はそれぞれ平均到着率、到着間隔の変動係数（標準偏差を平均で除した値）、平均サービス率、サービス時間の変動係数である。独立変数(x,t)はそれぞれ系内数の近似値と時刻、未知変数f(x,t)は時刻tにおける系内数の確率密度関数、Λ-1は系内数が0となる時間間隔の平均、R(t)は時刻tにおける系内数0の確率を示す。
【００２２】
上記（１）は、モデルとしては与えられているものの、その陽な解は現在まで知られていなかった（非特許文献２参照）。そこで、系内数分布算出手段１０１ではまず、上記の陽な解を与え、これを用いることにより、系内数の分布及びキュー遅延分布の簡易な算出を実現する。具体的には、上記の陽な解は以下の様に求めることができる。 
【００２３】
【数２】
2015019159.tif 000004
*、*xはそれぞれ(x,t)及びxに関する畳み込み、δ(・)、H(・),はそれぞれDiracのデルタ関数、Heavisideのステップ関数である。解の表現（2）を得る具体的な証明は省略する。
【００２４】
定常状態における系内数分布を算出するためには、上記（２）においてt→∞として得られる以下の関数を適用する。
【００２５】
【数３】
2015019159.tif 000005
次に再度図1を使用して、キュー遅延分布算出手段１０２につき記載する。キュー遅延分布算出手段１０２は、系内数推定手段１０１で算出された系内数分布とサービス時間分布のN次（N≧2）までのモーメントを入力として、キュー遅延分布を算出し、出力する。ここでNは、後述するように所望の推定精度要件に応じて設定する。ここでは、観測されているサービス時間分布のモーメント次数に応じ、分布関数に対する標本数に関する漸近展開の適用により、近似的にキュー遅延Wtの分布を算出・出力する。
【００２６】
【数４】
2015019159.tif 000006
ここでP(Wt≦y)はキュー遅延yの分布関数、P(k,t)は時刻tにおける系内数kの確率密度であり、前記（２）により得たf(x,t)を用いて以下の通り算出する.
【００２７】
【数５】
2015019159.tif 000007
また、
【００２８】
【数６】
2015019159.tif 000008
は当該系内kパケットの全処理時間がy以下である確率を表す。当該確率は未知であるが、系内数kに関して漸近的に正規分布に従うことから、系内数kに関する漸近展開により近似的に陽な表現を求めることができる。以上により、式（３）を用いてキュー遅延分布算出手段１０２の出力が算出される。これがキュー遅延算出装置の最終出力である。
【００２９】
次に、図３を参照して、本発明の実施例に係るキュー遅延算出方法のフローチャートについて説明する。
【００３０】
まずステップＳ１０１において、入力情報同定手段１０３が入力情報を同定する。入力情報同定手段１０３は、入力情報として、観測されたネットワーク情報から到着間隔の平均及び分散と、サービス時間分布のN次までのモーメント観測値とをそれぞれ同定する。到着間隔の平均及び分散は例えば、所定の時間区間に到達するパケットの個数の観測により同定可能である。サービス時間分布についてはルータ前後での測定により各パケットの通過時間を観測することにより得られる。前述のように、入力情報同定手段１０３自体は別の装置に存在してもよく、ここでは規定しない。またモデル（１）においては、R(t)及びΛを所与とする必要がある。これらについても事前に所与する。
【００３１】
次にステップＳ１０２において、系内数分布算出手段１０１が系内数分布を推定する。系内数分布算出手段１０１は、モデル（１）に入力情報同定手段１０３からの入力情報を代入することにより、所望の時刻における系内数分布を算出し、出力する。
【００３２】
次にステップＳ１０３において、キュー遅延分布算出手段１０２は、前記算出された系内数分布に基づき、キュー遅延分布を算出し、出力する。ここで系に到着したパケットが、その前に到着したパケットの処理が終了してから享受する待ち時間は同一のサービス時間分布に従う。このため、ある時刻に系に到着したパケットが経験する待ち時間は、当該時刻における系内のパケットの独立同分布に従う確率変数の和である。キュー遅延分布算出手段１０２はまず、系内数k(k=0,1,2,...)である確率P(k,t)を系内数分布算出手段１０１の出力である確率密度関数f(x,t)を用いて以下の様に算出する（式（３）再掲）。
【００３３】
【数７】
2015019159.tif 000009
次に式（３）を用いて、時刻tにおける待ち時間Wtがx以下である確率P(Wt≦y)を以下の様に算出する。
【００３４】
【数８】
2015019159.tif 000010
ここで
【００３５】
【数９】
2015019159.tif 000011
は、当該系内の全処理時間がy以下である確率を表す。この確率について、系内数kが大きい場合には、中心極限定理により当該分布は系内数に関し漸近的に平均、標準偏差がそれぞれ(k/μ,kσ_s)の正規分布のそれに従うことが知られている。ここでσ_sはサービス時間の標準偏差である。また更に精度を高める手段としてEdgeworth展開が知られている。Edgeworth展開では、サービス時間分布のモーメントを高次まで入力するほど、推定誤差を標本数の負冪のオーダで抑制することができる。例として、ここでは２次のEdgeWorth展開により
【００３６】
【数１０】
2015019159.tif 000012
の表現を陽に与える手法を記載する。この場合、推定誤差はo(k-1.5)である。
【００３７】
まずサービス時間分布を正規化した確率変数Z及びそのk個の標本値{Zi}i=1kを考える。
【００３８】
Z=(X-μ)σs-1
これに2次のEdgeWorth展開を適用すると、そのk個の和の確率分布は以下の様に与えられる。
【００３９】
【数１１】
2015019159.tif 000013
ここでΦ(・)、φ(・)はそれぞれ標準正規分布の分布関数及び確率密度関数、Hi(・)(i=2,3,5)はi次Hermite多項式、(μ3,μ4)はサービス時間分布の3次及び4次のモーメントである。従って前記所望の確率は、近似的に以下の様に表現することができる。
【００４０】
【数１２】
2015019159.tif 000014
これが本装置の最終出力である。
【００４１】
なおHermite多項式は例えば5次までの場合以下の様に与えられている。
【００４２】
【数１３】
2015019159.tif 000015
＜本発明の実施例の効果＞
上記のように、一般的なGI/GI/1モデルを対象とする場合、従来技術では、確率密度関数を陽に表現する手段が存在しなかった。このため、コンピュータ上に待ち行列システムを実装して、シミュレーションを膨大な回数反復し、近似する手段しか存在しなかった。本発明の実施例では、各時刻における確率密度関数の近似値を陽に求めて用いることにより、各時刻における確率密度を、陽な表現で極めて容易に出力することが可能である。
【００４３】
本発明の実施例によれば、到着過程・サービス時間分布とも一般の確率分布に従うGI/GI/1モデルに従う待ち行列シミュレーションにおいて、平均到着率、到着間隔の変動係数、サービス時間のモーメントの入力により、各時刻における系内数分布及びキュー遅延分布を算出可能である。従って、ネットワーク上の簡易な測定により、当該ネットワークのボトルネックリンクにおけるキュー遅延の推定・予測をするネットワークの品質制御技術に適用することができる。
【００４４】
本発明の実施例に係る手法はまた、任意時刻における系内数や遅延の分布を算出可能であることから、将来の分布変動や定常状態における分布の予測推定にも用いることができる。
【００４５】
以下では到着過程がポアソン過程、待ち時間が固定の場合（M/D/１）について本発明の実施例に係る装置を用いた場合のキュー遅延分布の例を示す。到着間隔の平均値1/λ、変動係数K_a、サービス時間の平均値1/μ、変動係数K_sは以下を用いる。
【００４６】
(1/λ,K_a,1/μ,K_s,μ3,μ4)=(2,1,1,0,0,0)
また分布の推定対象とする時刻はt=10、Λ=0.5、R(t)=1+exp(-t)でそれぞれ所与とする。この場合ρ=0.5である。
【００４７】
これを入力として、本発明の実施例により推定されるサービス時間分布は図４の様になり、ρ=0.5の場合におけるM/D/1の定常状態キュー遅延の確率密度関数理論値とほぼ同等の結果が得られることが確認できる。
【００４８】
本発明の実施例は、M/M/1モデル等を含み、単一サーバ且つ無限長のキューを有する待ち行列モデル（GI/GI/1モデル）に適用可能である。
【００４９】
説明の便宜上、本発明の実施例に係るキュー遅延算出装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係るキュー遅延算出装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係る方法は処理の流れを示すフローチャートを用いて説明しているが、本発明の実施例に係る方法は、実施例に示す順序と異なる順序で実施されてもよい。
【００５０】
以上、到着過程及びサービス時間分布の平均及び分散を入力としてキュー遅延の確率分布を算出するための手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００５１】
１０１  系内数推定手段
１０２  キュー遅延分布算出手段
１０３  入力情報同定手段
【図１】
2015019159.tif 000020
【図２】
2015019159.tif 000021
【図３】
2015019159.tif 000022
【図４】
2015019159.tif 000023