最大接続数推定装置及び方法及びプログラム
【課題】 アプリケーション接続数の周期観測に基づき、観測周期毎の平均値からサービス時間の分布のパラメータを推定し、最大接続数の分布のα確率点(0<α<1) もしくはその近似値を算出する。
【解決手段】 周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定し、同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成し、M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0 <α< 1) 確率点推定を行う。また、同定結果に基づき、M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出し、α(0 <α< 1) 確率点推定を行う。さらに、推定されたサービス時間の分布に対し、観測値の適合度検定を行い、棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択する。
【解決手段】 周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定し、同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成し、M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0 <α< 1) 確率点推定を行う。また、同定結果に基づき、M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出し、α(0 <α< 1) 確率点推定を行う。さらに、推定されたサービス時間の分布に対し、観測値の適合度検定を行い、棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最大接続数推定装置及び方法及びプログラムに係り、特に、IPネットワーク上のアプリケーション接続数の周期観測に基づく接続数のモデル化により、観測周期毎の平均接続数からサービス時間の分布のパラメータ値を推定し、最大接続数の分布のα確率点(0<α<1) の近似値を算出するための最大接続数推定装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
一般にIP ネットワークの収容設計や帯域設計においては、対象とするフローのピーク値に基づき収容率や必要帯域の上限値を算出する。例えば、パケットフローの同時接続数に基づく効率的な収容設計手法が提案されている。しかしながら、これらの技術の実現に必要な入力値の一つであるパケットフローの同時接続数のピーク値が観測値として直接得られるとは限らない。商用網の運用においては瞬時値の常時観測ではなく、例えば周期観測による平均値のみを観測している場合があり、この場合には周期観測により得られた観測値からピーク値を推定する必要がある。
【０００３】
また、リンク使用帯域の平均・分散の推定方法について、周期観測により得られた複数の平均値に基づき、より細かい時間幅でのリンク使用帯域の分散を推定する技術が提案されている(例えば、特許文献１参照)。
【０００４】
当該技術で得られる分散値は２個のパラメータ（サンプル数）(m; n) に依存するが、固定したn に対しては得られる分散推定値がO(m) であり、またn = m の場合は時間粒度を細かくすると必要なサンプル数が無限大に発散するため、細かい時間粒度でのピーク値推定には不向きであると考えられる。確率過程のピーク値の分布の算出方法については、過去に多数の検討が存在する（例えば、非特許文献１）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３５４２０３０号
【非特許文献】
【０００６】
【非特許文献１】IAN F. Blake and William C. Lindsey, "Level-Crossing Problems for Random Processes", IEEE Transactions on Information Theory, 19 (1973), 295-315.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一般に、ＩＰネットワークの収容設計や帯域設計においては、対象とするアプリケーションの最大接続数に基づき、収容率や必要帯域の上限値を算出する。一方で、商用網の運用においては、瞬時値の常時観測ではなく、例えば、周期観測による平均値のみを観測している場合があり、この場合には、周期観測により得られた観測値から最大接続数を推定する必要がある。このための手法として、所与のサービス時間分布の仮定のもとで同時接続数の推移をM/G/∞モデルでモデル化し、最大接続数推定を行う手法があるが、有限時間区間内の最大接続数の分布は平均接続数とサービス時間分布に依存するため、正確な最大接続数推定にはサービス時間分布の推定が必要である。
【０００８】
本発明は、上記の点に鑑みなされたものであり、IP ネットワーク上のアプリケーション接続数の周期観測に基づき、観測周期毎の平均値からサービス時間の分布のパラメータを推定し、最大接続数の分布のα確率点(0<α<1) もしくはその近似値を算出する最大接続数推定装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明は、IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定装置であって、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定手段と、
前記パラメータ同定手段の同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化手段と、
前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0<α<1)確率点推定を行う最大値算出手段と、を有することを特徴とする。
【００１０】
また、前記モデル化手段は、
前記パラメータ同定手段の前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する累積分布算出手段を含み、α(０<α<１) 確率点推定を行う。
【００１１】
また、前記パラメータ同定手段で推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定手段と、
前記適合度検定手段で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択手段と、
を更に有する。
【００１２】
また、前記モデル選択手段は、
観測周期の各倍数上の平均接続数の２次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する手段を含む。
【発明の効果】
【００１３】
上記のように、従来は、M/G/∞の有限時間区間内の最大接続数の分布は平均接続数とサービス時間分布に依存するため、正確な最大接続数推定にはサービス時間分布の推定が必要になるという課題があったが、本発明によれば、ＩＰネットワーク上のアプリケーション接続数の周期観測に基づき、観測周期毎の平均値からサービス時間の分布のパラメータを推定することで、最大接続数の分布のα確率点（０＜α＜１）もしくはその近似値を算出することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】観測周期毎最大接続数と平均値のイメージである。
【図２】本発明の一実施の形態における推定装置の構成図である。
【図３】本発明の一実施の形態における推定装置の処理の流れを示す図である。
【図４】本発明の一実施例の２次キュムラント理論値と観測値である。
【図５】本発明の一実施例の式（１）右辺理論値と観測値（M/D/∞）である。
【図６】本発明の一実施例の式（１）の右辺理論値と観測値(M/M/∞)である。
【図７】本発明の一実施例の３次キュムラント理論値と観測値である。
【図８】本発明の一実施例の観測時間上最大接続数の経験累積分布である。
【発明を実施するための形態】
【００１５】
以下図面と共に、本発明の実施の形態を説明する。
【００１６】
最初に、凡例及び用語について説明する。
【００１７】
まず、以下に凡例を記載する。
【００１８】
・ T： 観測周期。
【００１９】
・ 1/λ，1/μ, ρ=λ/μ：それぞれM/G/∞モデルの平均到着時間間隔、平均サービス時間、平均接続数。
【００２０】
・ Xt: 時刻t における同時接続数。ここではM/G/∞の定常状態における値とする。
【００２１】
・周期T毎の平均接続数：以下ではATと表し、次式により定義する。
【００２２】
【数１】
最大接続数および周期毎の平均接続数のイメージを図１に示す。接続数自体は自然数に値をとるが、周期毎の平均接続数は観測周期内の同時接続数の平均であり実数値をとる。
【００２３】
・E[X], var[X]: それぞれ確率変数Xの平均、分散を表す。
【００２４】
・キュムラント母関数：確率密度関数fのラプラス変換（モーメント母関数）の対数：K(s) = log (M(s)),
【００２５】
【数２】
・キュムラント：キュムラント母関数のs=0におけるテーラー展開におけるn次の項の係数をn次キュムラントと定義する：
【００２６】
【数３】
確率変数Xに対して、そのn次中心化モーメントmn:=（E[(X-E[X])n]）との間で以下を満たす：
【００２７】
【数４】
2次のキュムラントは分散である。
・Anderson-Darling統計量：ある分布の経験分布{η1, η2, …,ηm}に対して、Anderson-Darling統計量を以下により定義する：
【００２８】
【数５】
F(・)は当該分布の累積分布関数。
【００２９】
図２は、本発明の一実施の形態における推定装置の構成を示す。
【００３０】
同図に示す推定装置は、パラメータ同定部１０、適合度検定部２０、モデル選択部３０、モデル化部４０、最大値算出部５０から構成される。
【００３１】
パラメータ同定部１０は、周期観測により得られた複数の平均接続数から到着率及びサービス時間分布のパラメータを推定する。
【００３２】
適合度検定部２０は、パラメータ同定部１０で推定されたサービス時間の分布に対し、観測値が選択された視聴時間分布に適合するかをチェックし、適合しないものは廃棄する。
【００３３】
モデル選択部３０は、適合度検定部２０で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択する。
【００３４】
モデル化部４０は、推定された視聴時間分布に従い、M/G/∞モデルによる待ち行列モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する。
【００３５】
最大値算出部５０は、M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα（０<α＜１）確率点推定を行う。
【００３６】
以下に上記の構成要素の動作を詳細に説明する。
【００３７】
＜パラメータ同定部１０＞
まず、接続数ρの推定値は、観測された平均接続数の標本平均として算出できる（特許文献１）。次にサービス時間の確率密度関数をf(x;θ1,θ2,・・・,θr)とする((θ1,θ2,・・・,θr)はパラメータ)。定常状態のM/G/∞ においては系内数Xt の分布は時間に依存せず平均ρのポアソン分布となる。またATはＴに関して漸近的に正規分布に従い、その平均はρ、時間幅T上の平均接続数のn次キュムラントkn (T) (n>=2)は、
【００３８】
【数６】
を満たす（例えば：文献１「IAN F. Blake and William C. Lindsey, "Level-Crossing Problems for Random Processes" IEEE Trans. Inform. Th. 19 (1973),295,315.」参照）。ここで、式（１）のg(x)は、サービス時間の累積分布を用いて以下により定義される：
【００３９】
【数７】
但し、G(・)はf(・)の累積確率分布を表す。
【００４０】
以下では、２つの条件を設定する。
【００４１】
［条件１］g(x)は急減少関数、即ち任意のm, n（>=1）に対して
【００４２】
【数８】
[条件２]任意のε>0に対して、
|(d/dT)fn(Tn,ε)-an| < ε
を満たすTn,εと、p≧rおよび実数上の区間In (n=2,3,…,p)が存在して、各n=2,3,…,pおよびan, bn∈In (n=2,3,…,p)に対し、(θ1,θ2,・・・,θr)に関する連立方程式
【００４３】
【数９】
が解を持つ。
本発明の技術は上の条件1, 2が満たされている前提のもとで成り立つ。
【００４４】
周期観測においては、観測時間にわたり上記モデルが適用可能であると考えると、自然数iについて各iTに対応するn次キュムラントの列
【００４５】
【数１０】
が得られる(Tは観測周期)。
【００４６】
例えば、いま、T毎の平均接続数の観測値ST :={ξ1,ξ2, …,ξm}が得られているとする。この時、観測周期2T毎の平均接続数
S2T :={(ξ1+ξ2)/2, (ξ3+ξ4)/2, ・・・ },
観測周期3T毎の平均接続数
S3T :={(ξ1+ξ2 +ξ3)/3, (ξ4+ξ5 +ξ6)/3, ・・・}, …
を構成する。ここで、式（１）よりgが条件１を満たせば、十分大きいTに対して式（１）右辺はTに関し線形となる。そこで、条件２を満たすp次までのキュムラントを算出し、各キュムラントの次数n (2≦n≦p)について、{T, 2T, 3T, …}を横軸に、キュムラントの値を縦軸にとり、傾きanと切片bnの値を算出し、これらがan, bn∈In (n=1,2,…,p)を満たしていれば、(θ1,θ2, …,θr)の推定値の算出が可能である。なお算出された傾きanと切片bnが、いずれかのn (2≦n≦p)についてan, bn∈Inを満たさない場合、当該分布の仮定は不適切と判断する。
平均接続数の観測値の収集方法としては、複数の手段が考えられる。例えば上記の例において、以下の様に標本数を小さくすることにより、観測周期Tの平均接続数の集合を複数作成することも可能である：
ST (1):={ξ1, ξ2, …, ξq1},
ST (2):={ ξq1+1, ξq1+2, …, ξq2}, …
ST (k+1):={ ξqk+1, ξqk+2, …, ξq(k+1)}, (q1≦q2≦…≦q(k+1)≦m).
これにより、観測周期Tに対して複数のキュムラント
{kn (1)(T), kn (2)(T), …, kn (k+1)(T)}n=1,2,…
を得ることができる。
【００４７】
観測周期2T, 3Tについても同様にして、線形回帰を行う対象の点の数を増やすことができる。本発明の実現形態として、これらの手段を採用することもできる。
【００４８】
＜適合度検定部２０＞
次に適合度検定の方法を述べる。以下では仮に有意水準5%の場合を述べる。本発明の適合度検定では、パラメータ推定されたサービス時間の分布から算出される平均接続数ATの分布に対して、ブートストラップ法によるAnderson-Darling検定を用いる。まず、ATを以下の意味において正規化した確率変数YTを考える：
YT = (AT - E[AT])/var(AT).
同様に、上記同様に観測値を正規化して得られる値を→ｙ = {y1,y2, …,ym}と表す。なお、「→y」はベクトルを示す。
【００４９】
まず、検定対象の帰無仮説を
『→ｙが、仮定したサービス時間分布から算出されるYTの分布に従う』
とし、→ｙからAnderson-Darling統計量T0を求める(T0の定義は凡例を参照)。
【００５０】
ここで、T0の算出にはYTの累積確率分布が必要である。条件１が満たされていれば、n(n>=3)次のキュムラントはTに関して漸近的にO(T1-n)のオーダとなるため、YTの確率密度関数fY(x;T)は、以下の様に漸近展開できる：
fY (x;T) = φ(x)[1+k3(T)/3! H3(x)
+ k4(T)/4! H4(x)
+ k5(T)/5! H5(x)
+k32(T)/72H6(x)
+k32(T)/6! H6(x)
+k3 (T)k4(T)/144H7(x)
+O(T6)], ・・・式（２）
ここで、φ(x)は標準正規分布の確率密度関数（φ(x)=exp(-x2)）/(2π)1/2）、Hi(x)はi次のエルミート多項式である：
H3(x)=x3-3x,
H4(x)=x4-6x2+3,
H5(x)=x5-10x3+15x,
H6(x)=x6-15x4+45x2-15,
H7(x)=x7-21x5+105x3-105x.
累積確率分布の漸近展開は次の様に表せる:
FY (x;T) = Φ(x) - φ(x)[k3(T)/3! H2(x)+ k4(T)/4! H2(x)
+ k5(T)/5! H4(x)
+k32(T)/72H5(x)
+k32(T)/6! H5(x)
+k3 (T)k4(T)/144H6(x)
+O(T6)],
ここでΦ(x)は標準正規分布の累積確率分布。これを用いてAnderson-Darling統計量T0を算出する。
【００５１】
次に、ブートストラップにより→yからのリサンプリングによる複製標本｛→yi*｝i=1Bを作成し、これに基づくパラメータ推定値に基づき平均接続数の累積確率分布FY* (x;T)を構成し、Anderson-Darling統計量｛Ti*｝i=1Bを算出・記録する。この過程をB回反復する。
【００５２】
ｐ:=#(Ti*>T0)/B
を推定p値とし、ｐ＜0.05であれば、帰無仮説を棄却、それ以外の場合棄却しない。なお、有意水準の値は任意に設定可能である。
【００５３】
＜モデル選択部３０＞
次にモデル選択の手法を述べる。一般的なモデル選択手法としては、AIC(赤池情報量基準), EIC(ブートストラップ情報量基準)などの情報量基準に基づく方法が存在する。これらはいずれも、比較対象の分布の経験分布に基づき、パラメータの最尤推定値に基づく対数尤度と、そのバイアス補正項の和として定義される量であり、その値をもって真の分布への近さとする。しかし本発明においては、比較対象はサービス時間の分布であるにも関わらず、得られる観測値は周期毎の平均接続数ATの経験分布である。ATの分布は漸近的に正規分布に従うため、上記式（２）の様に漸近展開により表現可能である。しかし、平均接続数の確率密度関数同士のとる値の差は、異なるサービス時間の分布から算出されたもの同士であっても小さく、従来手法が有効に機能しない。
【００５４】
そこで、サービス時間の分布同士ではなく、2次からn次までのキュムラントの値の組の間に距離を定義し、その大小を比較することにする。実際、n次までのキュムラントが一致していれば、ATの分布間の距離としても漸近的に（T-nのオーダで）近いことを示すことができる。
【００５５】
例えば、KX(s)：確率変数Xのキュムラント母関数とする。
【００５６】
【数１１】
また逆に、元の分布が近い場合にn次までのキュムラント同士がRn-1の点として近くなることは明らかである。
【００５７】
そこで本発明では、観測周期の各倍数上の平均接続数が従う分布のキュムラント理論値と、各々の観測値の差の平方の荷重和を比較し、モデルの近さを判定する。例えばいま、推定されたパラメータに基づく平均接続数の確率密度関数の一つを
【００５８】
【数１２】
とする。各
【００５９】
【数１３】
はパラメータ推定値である。f1に基づく観測周期の各倍数上の平均接続数のキュムラント理論値を
→k(1)(jT) := [k2(1)(jT), …,kn(1)(jT)] (j=1,2,…,N), ・・・式（３）
但し式（１）より
【００６０】
【数１４】
とする。ここでg1(x)は以下により定義される：
【００６１】
【数１５】
また（３）の各々に対応するキュムラント観測値を
【００６２】
【数１６】
とし、ｆ１と各観測時間幅における平均接続数の経験分布~(~観)0との距離を
【００６３】
【数１７】
により定める。但し(n-1)次元ベクトル→ａ，→ｂに対し、
【００６４】
【数１８】
とし、αjは時間に関する重み付けの正定数。
【００６５】
上記
【００６６】
【数１９】
が小さいサービス時間の確率密度関数ほど、真の分布に近いと考える。
【００６７】
なお上記によるモデル選択において、以下の手段によりバイアス補正を考慮することもできる。
【００６８】
まず、
【００６９】
【数２０】
とする。この量と、log d(f1,f0)との間のバイアスは以下の様に表すことができる：
【００７０】
【数２１】
ここで、Ef0[X]は確率変数Xについて、f0を確率測度として考えた場合の平均を表す。本発明ではブートストラップにより、以下の手順により上記バイアスを推定する：
（１）各時間幅Tj毎に、平均接続数の複製標本X*(Tj)を作成し、キュムラント観測値[k2*(Tj), …,kn*(Tj)]に基づきパラメータ推定値(θ1*, θ2*, ・・・, θn1*)を算出する。またこの時の平均接続数の確率密度関数を
f*1(x; θ1*, θ2*, ・・・, θn1*)
と表す。
【００７１】
（２）上記パラメータ推定値に基づき、
【００７２】
【数２２】
を算出する。
【００７３】
（３）手順（１）〜（２）をB回反復し、以下によりバイアス推定値を算出する：
【００７４】
【数２３】
以上により算出される量、
【００７５】
【数２４】
の値が（負の値であっても）小さいほど、f1は真の分布に近いと考える。
【００７６】
＜モデル化部４０＞
モデル化部４０は、最大接続数推定機能、アプリケーション接続数のモデル化機能、最大接続数と平均値の比率のモデル化機能を有する。
【００７７】
モデル化部４０の最大接続数推定機能は、推定されたサービス時間分布をもつM/G/∞モデルを構成し、任意の有限時間幅にわたるシミュレーションをm 回実施して最大接続数の経験分布η1，η2，...，ηm を得る。これにより、累積分布
【００７８】
【数２５】
を算出し、そのα確率点を算出する。
【００７９】
モデル化部４０のアプリケーション接続数のモデル化機能は、本方式では、アプリケーションの接続到着は互いに独立に到着するとの前提に立ち、平均到着間隔1/λのポアソン分布に従いモデル化する。またサービス時間は平均1/μの任意の確率変数とし、対象とするアプリケーション接続数を定常状態のM/G/∞としてモデル化する。
【００８０】
以下、時刻t における接続数をXt と表す。定常状態のM/G/∞については、時刻t で値n (∈N) をとる。定常状態確率P(Xt = n) について、
P(Xt = n) = ρn exp(-ρ)/n (ρ= λ/μ)
であることが知られている。
【００８１】
モデル化部の最大接続数と平均値の比率のモデル化機能は、上記のアプリケーション接続数のモデル化機能のアプリケーション接続数のモデルに基づき、アプリケーション接続数の最大接続数と平均値の比率 ATを以下の式でモデル化する：
【００８２】
【数２６】
＜最大値算出部５０＞
最大値算出部５０は、上記で求められたAT（アプリケーション接続数の最大接続数と平均値の比率）の分布を算出する。
【００８３】
本発明が提案する、AT の分布の算出方式では、前記M/G/∞モデルによるシミュレーションに基づき、AT の累積分布Pa ≡P(AT ≦ a) を算出する。AT の累積分布Paを基に、α 確率点におけるAT の値から最大接続数を算出する。
【００８４】
具体的な動作は次のとおりである。所与のρ= λ/μおよびサービス時間の分布の下にM/G/∞モデルのシミュレーションを行い、当該M/G/∞ モデルの系内数を算出し、各観測周期における(最大接続数)/(平均値) の経験累積分布Paを算出する。
【００８５】
さらに、上記観測周期における(最大接続数)/(平均値) の経験累積分布Paから、α確率点におけるATを算出する。
【００８６】
以下に、図３に沿って推定装置の一連の動作を説明する。
【００８７】
図３は、本発明の一実施の形態における推定装置の処理の流れを示す図である。
【００８８】
以下の処理の前提として、アプリケーション接続数の推移を所与の平均到着間隔1/λ， 平均サービス率μ のM/G/∞によりモデル化する。またサービス時間の推定候補として、パラメトリックなk個の確率密度関数、
f1(x;θ11, θ12, ・・・, θn1), f2(x;θ21, θ22, ・・・, θn2),…, fk(x;θk1, θk2, ・・・, θnk)
が与えられているものとする。
【００８９】
まず、パラメータ同定部１０の動作を示す。
【００９０】
周期観測により時間T毎の平均流量N個の観測値｛ξi｝N i=1が得られている（観測時間がNTである）ことを前提とする。パラメータ同定手段では、まず観測値
ST :=｛ξi｝N i=1
の標本平均によりρの推定値とする：
【００９１】
【数２７】
次に、観測周期2T毎の平均接続数
S2T :={(ξ1+ξ2)/2， (ξ3+ξ4)/2, … }、
観測周期3T毎の平均値接続数
S3T :={(ξ1+ξ2 +ξ3)/3， (ξ4+ξ5 +ξ6)/3， ・・・}， …
を構成し、それぞれのp次までのキュムラントを算出する。次数pの値は、推定対象の分布のパラメータ数と、このキュムラントの理論式に依存して決める。各次数のキュムラントについて十分大きい時間における線形回帰を行い、回帰直線の傾きおよび切片を算出し、パラメータ推定値を算出・出力する。
【００９２】
適合検定部２０は、パラメータ同定部１０において推定されたl個の分布それぞれに対して、観測値に基づき適合度検定を実施する。帰無仮説は「当該分布が有意水準5%で観測値に適合している。」であり、これに対する仮説検定を実施する。全ての分布について帰無仮説が棄却された場合は、観測値の不足と判定し、再度観測値の収集を行う。
【００９３】
適合度検定部２０では、標本数に基づき、まずAnderson-Darling統計量T*を算出する。次にブートストラップ法により推定p値を算出し、その値の多寡に応じて帰無仮説の棄却是非を各分布について判定し、結果を出力する。
【００９４】
モデル選択部３０は、適合度検定部２０において棄却されなかった確率密度関数、
fi1(x;θi11, θi12, ・・・, θni1), fi2(x;θi21, θi22, ・・・, θni2),…, fik'(x;θik'1, θik'2, ・・・, θni k') (k'≦k)
から、真の確率密度関数に最も近いと推定されるものを選出・出力する。
【００９５】
モデル化部４０では前記パラメータ同定部１０の出力に基づき、推定された平均接続数とサービス時間の分布に基づきM/G/∞モデルを構成する。このモデルにより、任意の有限時間にわたるシミュレーションをm回反復して 実施し、各回の最大接続数を蓄積する。
【００９６】
最大値算出部５０は、上記モデル化手段の出力であるm個の最大接続数の経験累積分布を算出し、そのα確率点の値を出力する。この値を最大接続数の推定値として出力する。
【実施例】
【００９７】
本実施例では、以下の設定による実施例を示す。あるアプリケーションの接続が平均到着間隔10分(1/λ =0.1), 平均利用時間120 分(1/μ=120)、従って平均接続数12(ρ = 12) に従うものとし、観測周期60 分(T = 60) で平均接続数を観測しているものとする。観測値として、666個の観測値が図４に示すように得られている(観測時間666時間) ものとする。またサービス時間の真の分布は固定であり、推定候補としては、ａ．固定、ｂ．指数分布（ともにパラメータは1個）を設定する。
【００９８】
まず、パラメータ同定部１０では、このデータの標本平均により、平均接続数の推定値(1/ρ)として11.99を算出する。次に、各分布仮定時のパラメータ推定を行う。
【００９９】
１．M/D/∞を仮定した場合：
式（１）の右辺の理論値は、T>1/μの時
T/2μ-1 /6μ2
である。この理論値と標本値のプロットを図５に示す。線形回帰により、μの推定値
μ=1/119.83
を得る。
【０１００】
２．M/M/∞を仮定した場合：
式（１）の右辺の理論値は、
【０１０１】
【数２８】
でありTが大きい時
【０１０２】
【数２９】
に漸近する。線形回帰によるμの推定値は、
μ=1/59.9
である(図６)。
【０１０３】
次に、適合度検定部２０の動作を説明する。
【０１０４】
パラメータ同定部１０にて推定された各分布に対しブートストラップによるAnderson-Darling検定を実施した結果、p値として以下の結果を得た：ａ．0.36, ｂ．0.09。従って、適合度検定では5%の有意水準でいずれの分布も棄却されなかった。
【０１０５】
次に、モデル選択部３０では個々の分布に対して、まずパラメータ推定値に基づきキュムラント推定値を算出する。
【０１０６】
図４、７にキュムラント理論値および観測値のプロットを示す。また3次までのキュムラントに関するd''の算出結果として、
M/D/∞：d'' = 1.54
M/M/∞：d'' = 2.79
を得た。従ってM/D/∞が選択される。
【０１０７】
モデル化部４０では、前記パラメータ同定１０の出力に基づき、平均接続数11.99、サービス時間固定（119.83）のM/G/∞モデルを構成する。このモデルにより666時間にわたるシミュレーションを200回(m = 200) 実施し、各回の最大接続数を蓄積する。
【０１０８】
最大値算出部５０は、数値例では、上記モデル化手段の出力である666個の最大接続数の経験累積分布を算出し、その確率点αを99%の値として最大接続数25を出力する。その結果を図８に示す(なお、実際の666時間にわたる最大接続数は21であり、上記推定値の範囲に入っている)。この値を最大接続数の推定値として出力する。これが当該推定装置の最終出力である。
【０１０９】
なお、図２に示す各構成要素の上記の実施の形態及び実施例の動作をプログラムとして構築し、最大接続数推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１０】
本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１１１】
１０ パラメータ同定部
２０ 適合度検定部
３０ モデル選択部
４０ モデル化部
５０ 最大値算出部
【技術分野】
【０００１】
本発明は、最大接続数推定装置及び方法及びプログラムに係り、特に、IPネットワーク上のアプリケーション接続数の周期観測に基づく接続数のモデル化により、観測周期毎の平均接続数からサービス時間の分布のパラメータ値を推定し、最大接続数の分布のα確率点(0<α<1) の近似値を算出するための最大接続数推定装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
一般にIP ネットワークの収容設計や帯域設計においては、対象とするフローのピーク値に基づき収容率や必要帯域の上限値を算出する。例えば、パケットフローの同時接続数に基づく効率的な収容設計手法が提案されている。しかしながら、これらの技術の実現に必要な入力値の一つであるパケットフローの同時接続数のピーク値が観測値として直接得られるとは限らない。商用網の運用においては瞬時値の常時観測ではなく、例えば周期観測による平均値のみを観測している場合があり、この場合には周期観測により得られた観測値からピーク値を推定する必要がある。
【０００３】
また、リンク使用帯域の平均・分散の推定方法について、周期観測により得られた複数の平均値に基づき、より細かい時間幅でのリンク使用帯域の分散を推定する技術が提案されている(例えば、特許文献１参照)。
【０００４】
当該技術で得られる分散値は２個のパラメータ（サンプル数）(m; n) に依存するが、固定したn に対しては得られる分散推定値がO(m) であり、またn = m の場合は時間粒度を細かくすると必要なサンプル数が無限大に発散するため、細かい時間粒度でのピーク値推定には不向きであると考えられる。確率過程のピーク値の分布の算出方法については、過去に多数の検討が存在する（例えば、非特許文献１）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３５４２０３０号
【非特許文献】
【０００６】
【非特許文献１】IAN F. Blake and William C. Lindsey, "Level-Crossing Problems for Random Processes", IEEE Transactions on Information Theory, 19 (1973), 295-315.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一般に、ＩＰネットワークの収容設計や帯域設計においては、対象とするアプリケーションの最大接続数に基づき、収容率や必要帯域の上限値を算出する。一方で、商用網の運用においては、瞬時値の常時観測ではなく、例えば、周期観測による平均値のみを観測している場合があり、この場合には、周期観測により得られた観測値から最大接続数を推定する必要がある。このための手法として、所与のサービス時間分布の仮定のもとで同時接続数の推移をM/G/∞モデルでモデル化し、最大接続数推定を行う手法があるが、有限時間区間内の最大接続数の分布は平均接続数とサービス時間分布に依存するため、正確な最大接続数推定にはサービス時間分布の推定が必要である。
【０００８】
本発明は、上記の点に鑑みなされたものであり、IP ネットワーク上のアプリケーション接続数の周期観測に基づき、観測周期毎の平均値からサービス時間の分布のパラメータを推定し、最大接続数の分布のα確率点(0<α<1) もしくはその近似値を算出する最大接続数推定装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明は、IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定装置であって、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定手段と、
前記パラメータ同定手段の同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化手段と、
前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0<α<1)確率点推定を行う最大値算出手段と、を有することを特徴とする。
【００１０】
また、前記モデル化手段は、
前記パラメータ同定手段の前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する累積分布算出手段を含み、α(０<α<１) 確率点推定を行う。
【００１１】
また、前記パラメータ同定手段で推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定手段と、
前記適合度検定手段で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択手段と、
を更に有する。
【００１２】
また、前記モデル選択手段は、
観測周期の各倍数上の平均接続数の２次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する手段を含む。
【発明の効果】
【００１３】
上記のように、従来は、M/G/∞の有限時間区間内の最大接続数の分布は平均接続数とサービス時間分布に依存するため、正確な最大接続数推定にはサービス時間分布の推定が必要になるという課題があったが、本発明によれば、ＩＰネットワーク上のアプリケーション接続数の周期観測に基づき、観測周期毎の平均値からサービス時間の分布のパラメータを推定することで、最大接続数の分布のα確率点（０＜α＜１）もしくはその近似値を算出することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】観測周期毎最大接続数と平均値のイメージである。
【図２】本発明の一実施の形態における推定装置の構成図である。
【図３】本発明の一実施の形態における推定装置の処理の流れを示す図である。
【図４】本発明の一実施例の２次キュムラント理論値と観測値である。
【図５】本発明の一実施例の式（１）右辺理論値と観測値（M/D/∞）である。
【図６】本発明の一実施例の式（１）の右辺理論値と観測値(M/M/∞)である。
【図７】本発明の一実施例の３次キュムラント理論値と観測値である。
【図８】本発明の一実施例の観測時間上最大接続数の経験累積分布である。
【発明を実施するための形態】
【００１５】
以下図面と共に、本発明の実施の形態を説明する。
【００１６】
最初に、凡例及び用語について説明する。
【００１７】
まず、以下に凡例を記載する。
【００１８】
・ T： 観測周期。
【００１９】
・ 1/λ，1/μ, ρ=λ/μ：それぞれM/G/∞モデルの平均到着時間間隔、平均サービス時間、平均接続数。
【００２０】
・ Xt: 時刻t における同時接続数。ここではM/G/∞の定常状態における値とする。
【００２１】
・周期T毎の平均接続数：以下ではATと表し、次式により定義する。
【００２２】
【数１】
最大接続数および周期毎の平均接続数のイメージを図１に示す。接続数自体は自然数に値をとるが、周期毎の平均接続数は観測周期内の同時接続数の平均であり実数値をとる。
【００２３】
・E[X], var[X]: それぞれ確率変数Xの平均、分散を表す。
【００２４】
・キュムラント母関数：確率密度関数fのラプラス変換（モーメント母関数）の対数：K(s) = log (M(s)),
【００２５】
【数２】
・キュムラント：キュムラント母関数のs=0におけるテーラー展開におけるn次の項の係数をn次キュムラントと定義する：
【００２６】
【数３】
確率変数Xに対して、そのn次中心化モーメントmn:=（E[(X-E[X])n]）との間で以下を満たす：
【００２７】
【数４】
2次のキュムラントは分散である。
・Anderson-Darling統計量：ある分布の経験分布{η1, η2, …,ηm}に対して、Anderson-Darling統計量を以下により定義する：
【００２８】
【数５】
F(・)は当該分布の累積分布関数。
【００２９】
図２は、本発明の一実施の形態における推定装置の構成を示す。
【００３０】
同図に示す推定装置は、パラメータ同定部１０、適合度検定部２０、モデル選択部３０、モデル化部４０、最大値算出部５０から構成される。
【００３１】
パラメータ同定部１０は、周期観測により得られた複数の平均接続数から到着率及びサービス時間分布のパラメータを推定する。
【００３２】
適合度検定部２０は、パラメータ同定部１０で推定されたサービス時間の分布に対し、観測値が選択された視聴時間分布に適合するかをチェックし、適合しないものは廃棄する。
【００３３】
モデル選択部３０は、適合度検定部２０で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択する。
【００３４】
モデル化部４０は、推定された視聴時間分布に従い、M/G/∞モデルによる待ち行列モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する。
【００３５】
最大値算出部５０は、M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα（０<α＜１）確率点推定を行う。
【００３６】
以下に上記の構成要素の動作を詳細に説明する。
【００３７】
＜パラメータ同定部１０＞
まず、接続数ρの推定値は、観測された平均接続数の標本平均として算出できる（特許文献１）。次にサービス時間の確率密度関数をf(x;θ1,θ2,・・・,θr)とする((θ1,θ2,・・・,θr)はパラメータ)。定常状態のM/G/∞ においては系内数Xt の分布は時間に依存せず平均ρのポアソン分布となる。またATはＴに関して漸近的に正規分布に従い、その平均はρ、時間幅T上の平均接続数のn次キュムラントkn (T) (n>=2)は、
【００３８】
【数６】
を満たす（例えば：文献１「IAN F. Blake and William C. Lindsey, "Level-Crossing Problems for Random Processes" IEEE Trans. Inform. Th. 19 (1973),295,315.」参照）。ここで、式（１）のg(x)は、サービス時間の累積分布を用いて以下により定義される：
【００３９】
【数７】
但し、G(・)はf(・)の累積確率分布を表す。
【００４０】
以下では、２つの条件を設定する。
【００４１】
［条件１］g(x)は急減少関数、即ち任意のm, n（>=1）に対して
【００４２】
【数８】
[条件２]任意のε>0に対して、
|(d/dT)fn(Tn,ε)-an| < ε
を満たすTn,εと、p≧rおよび実数上の区間In (n=2,3,…,p)が存在して、各n=2,3,…,pおよびan, bn∈In (n=2,3,…,p)に対し、(θ1,θ2,・・・,θr)に関する連立方程式
【００４３】
【数９】
が解を持つ。
本発明の技術は上の条件1, 2が満たされている前提のもとで成り立つ。
【００４４】
周期観測においては、観測時間にわたり上記モデルが適用可能であると考えると、自然数iについて各iTに対応するn次キュムラントの列
【００４５】
【数１０】
が得られる(Tは観測周期)。
【００４６】
例えば、いま、T毎の平均接続数の観測値ST :={ξ1,ξ2, …,ξm}が得られているとする。この時、観測周期2T毎の平均接続数
S2T :={(ξ1+ξ2)/2, (ξ3+ξ4)/2, ・・・ },
観測周期3T毎の平均接続数
S3T :={(ξ1+ξ2 +ξ3)/3, (ξ4+ξ5 +ξ6)/3, ・・・}, …
を構成する。ここで、式（１）よりgが条件１を満たせば、十分大きいTに対して式（１）右辺はTに関し線形となる。そこで、条件２を満たすp次までのキュムラントを算出し、各キュムラントの次数n (2≦n≦p)について、{T, 2T, 3T, …}を横軸に、キュムラントの値を縦軸にとり、傾きanと切片bnの値を算出し、これらがan, bn∈In (n=1,2,…,p)を満たしていれば、(θ1,θ2, …,θr)の推定値の算出が可能である。なお算出された傾きanと切片bnが、いずれかのn (2≦n≦p)についてan, bn∈Inを満たさない場合、当該分布の仮定は不適切と判断する。
平均接続数の観測値の収集方法としては、複数の手段が考えられる。例えば上記の例において、以下の様に標本数を小さくすることにより、観測周期Tの平均接続数の集合を複数作成することも可能である：
ST (1):={ξ1, ξ2, …, ξq1},
ST (2):={ ξq1+1, ξq1+2, …, ξq2}, …
ST (k+1):={ ξqk+1, ξqk+2, …, ξq(k+1)}, (q1≦q2≦…≦q(k+1)≦m).
これにより、観測周期Tに対して複数のキュムラント
{kn (1)(T), kn (2)(T), …, kn (k+1)(T)}n=1,2,…
を得ることができる。
【００４７】
観測周期2T, 3Tについても同様にして、線形回帰を行う対象の点の数を増やすことができる。本発明の実現形態として、これらの手段を採用することもできる。
【００４８】
＜適合度検定部２０＞
次に適合度検定の方法を述べる。以下では仮に有意水準5%の場合を述べる。本発明の適合度検定では、パラメータ推定されたサービス時間の分布から算出される平均接続数ATの分布に対して、ブートストラップ法によるAnderson-Darling検定を用いる。まず、ATを以下の意味において正規化した確率変数YTを考える：
YT = (AT - E[AT])/var(AT).
同様に、上記同様に観測値を正規化して得られる値を→ｙ = {y1,y2, …,ym}と表す。なお、「→y」はベクトルを示す。
【００４９】
まず、検定対象の帰無仮説を
『→ｙが、仮定したサービス時間分布から算出されるYTの分布に従う』
とし、→ｙからAnderson-Darling統計量T0を求める(T0の定義は凡例を参照)。
【００５０】
ここで、T0の算出にはYTの累積確率分布が必要である。条件１が満たされていれば、n(n>=3)次のキュムラントはTに関して漸近的にO(T1-n)のオーダとなるため、YTの確率密度関数fY(x;T)は、以下の様に漸近展開できる：
fY (x;T) = φ(x)[1+k3(T)/3! H3(x)
+ k4(T)/4! H4(x)
+ k5(T)/5! H5(x)
+k32(T)/72H6(x)
+k32(T)/6! H6(x)
+k3 (T)k4(T)/144H7(x)
+O(T6)], ・・・式（２）
ここで、φ(x)は標準正規分布の確率密度関数（φ(x)=exp(-x2)）/(2π)1/2）、Hi(x)はi次のエルミート多項式である：
H3(x)=x3-3x,
H4(x)=x4-6x2+3,
H5(x)=x5-10x3+15x,
H6(x)=x6-15x4+45x2-15,
H7(x)=x7-21x5+105x3-105x.
累積確率分布の漸近展開は次の様に表せる:
FY (x;T) = Φ(x) - φ(x)[k3(T)/3! H2(x)+ k4(T)/4! H2(x)
+ k5(T)/5! H4(x)
+k32(T)/72H5(x)
+k32(T)/6! H5(x)
+k3 (T)k4(T)/144H6(x)
+O(T6)],
ここでΦ(x)は標準正規分布の累積確率分布。これを用いてAnderson-Darling統計量T0を算出する。
【００５１】
次に、ブートストラップにより→yからのリサンプリングによる複製標本｛→yi*｝i=1Bを作成し、これに基づくパラメータ推定値に基づき平均接続数の累積確率分布FY* (x;T)を構成し、Anderson-Darling統計量｛Ti*｝i=1Bを算出・記録する。この過程をB回反復する。
【００５２】
ｐ:=#(Ti*>T0)/B
を推定p値とし、ｐ＜0.05であれば、帰無仮説を棄却、それ以外の場合棄却しない。なお、有意水準の値は任意に設定可能である。
【００５３】
＜モデル選択部３０＞
次にモデル選択の手法を述べる。一般的なモデル選択手法としては、AIC(赤池情報量基準), EIC(ブートストラップ情報量基準)などの情報量基準に基づく方法が存在する。これらはいずれも、比較対象の分布の経験分布に基づき、パラメータの最尤推定値に基づく対数尤度と、そのバイアス補正項の和として定義される量であり、その値をもって真の分布への近さとする。しかし本発明においては、比較対象はサービス時間の分布であるにも関わらず、得られる観測値は周期毎の平均接続数ATの経験分布である。ATの分布は漸近的に正規分布に従うため、上記式（２）の様に漸近展開により表現可能である。しかし、平均接続数の確率密度関数同士のとる値の差は、異なるサービス時間の分布から算出されたもの同士であっても小さく、従来手法が有効に機能しない。
【００５４】
そこで、サービス時間の分布同士ではなく、2次からn次までのキュムラントの値の組の間に距離を定義し、その大小を比較することにする。実際、n次までのキュムラントが一致していれば、ATの分布間の距離としても漸近的に（T-nのオーダで）近いことを示すことができる。
【００５５】
例えば、KX(s)：確率変数Xのキュムラント母関数とする。
【００５６】
【数１１】
また逆に、元の分布が近い場合にn次までのキュムラント同士がRn-1の点として近くなることは明らかである。
【００５７】
そこで本発明では、観測周期の各倍数上の平均接続数が従う分布のキュムラント理論値と、各々の観測値の差の平方の荷重和を比較し、モデルの近さを判定する。例えばいま、推定されたパラメータに基づく平均接続数の確率密度関数の一つを
【００５８】
【数１２】
とする。各
【００５９】
【数１３】
はパラメータ推定値である。f1に基づく観測周期の各倍数上の平均接続数のキュムラント理論値を
→k(1)(jT) := [k2(1)(jT), …,kn(1)(jT)] (j=1,2,…,N), ・・・式（３）
但し式（１）より
【００６０】
【数１４】
とする。ここでg1(x)は以下により定義される：
【００６１】
【数１５】
また（３）の各々に対応するキュムラント観測値を
【００６２】
【数１６】
とし、ｆ１と各観測時間幅における平均接続数の経験分布~(~観)0との距離を
【００６３】
【数１７】
により定める。但し(n-1)次元ベクトル→ａ，→ｂに対し、
【００６４】
【数１８】
とし、αjは時間に関する重み付けの正定数。
【００６５】
上記
【００６６】
【数１９】
が小さいサービス時間の確率密度関数ほど、真の分布に近いと考える。
【００６７】
なお上記によるモデル選択において、以下の手段によりバイアス補正を考慮することもできる。
【００６８】
まず、
【００６９】
【数２０】
とする。この量と、log d(f1,f0)との間のバイアスは以下の様に表すことができる：
【００７０】
【数２１】
ここで、Ef0[X]は確率変数Xについて、f0を確率測度として考えた場合の平均を表す。本発明ではブートストラップにより、以下の手順により上記バイアスを推定する：
（１）各時間幅Tj毎に、平均接続数の複製標本X*(Tj)を作成し、キュムラント観測値[k2*(Tj), …,kn*(Tj)]に基づきパラメータ推定値(θ1*, θ2*, ・・・, θn1*)を算出する。またこの時の平均接続数の確率密度関数を
f*1(x; θ1*, θ2*, ・・・, θn1*)
と表す。
【００７１】
（２）上記パラメータ推定値に基づき、
【００７２】
【数２２】
を算出する。
【００７３】
（３）手順（１）〜（２）をB回反復し、以下によりバイアス推定値を算出する：
【００７４】
【数２３】
以上により算出される量、
【００７５】
【数２４】
の値が（負の値であっても）小さいほど、f1は真の分布に近いと考える。
【００７６】
＜モデル化部４０＞
モデル化部４０は、最大接続数推定機能、アプリケーション接続数のモデル化機能、最大接続数と平均値の比率のモデル化機能を有する。
【００７７】
モデル化部４０の最大接続数推定機能は、推定されたサービス時間分布をもつM/G/∞モデルを構成し、任意の有限時間幅にわたるシミュレーションをm 回実施して最大接続数の経験分布η1，η2，...，ηm を得る。これにより、累積分布
【００７８】
【数２５】
を算出し、そのα確率点を算出する。
【００７９】
モデル化部４０のアプリケーション接続数のモデル化機能は、本方式では、アプリケーションの接続到着は互いに独立に到着するとの前提に立ち、平均到着間隔1/λのポアソン分布に従いモデル化する。またサービス時間は平均1/μの任意の確率変数とし、対象とするアプリケーション接続数を定常状態のM/G/∞としてモデル化する。
【００８０】
以下、時刻t における接続数をXt と表す。定常状態のM/G/∞については、時刻t で値n (∈N) をとる。定常状態確率P(Xt = n) について、
P(Xt = n) = ρn exp(-ρ)/n (ρ= λ/μ)
であることが知られている。
【００８１】
モデル化部の最大接続数と平均値の比率のモデル化機能は、上記のアプリケーション接続数のモデル化機能のアプリケーション接続数のモデルに基づき、アプリケーション接続数の最大接続数と平均値の比率 ATを以下の式でモデル化する：
【００８２】
【数２６】
＜最大値算出部５０＞
最大値算出部５０は、上記で求められたAT（アプリケーション接続数の最大接続数と平均値の比率）の分布を算出する。
【００８３】
本発明が提案する、AT の分布の算出方式では、前記M/G/∞モデルによるシミュレーションに基づき、AT の累積分布Pa ≡P(AT ≦ a) を算出する。AT の累積分布Paを基に、α 確率点におけるAT の値から最大接続数を算出する。
【００８４】
具体的な動作は次のとおりである。所与のρ= λ/μおよびサービス時間の分布の下にM/G/∞モデルのシミュレーションを行い、当該M/G/∞ モデルの系内数を算出し、各観測周期における(最大接続数)/(平均値) の経験累積分布Paを算出する。
【００８５】
さらに、上記観測周期における(最大接続数)/(平均値) の経験累積分布Paから、α確率点におけるATを算出する。
【００８６】
以下に、図３に沿って推定装置の一連の動作を説明する。
【００８７】
図３は、本発明の一実施の形態における推定装置の処理の流れを示す図である。
【００８８】
以下の処理の前提として、アプリケーション接続数の推移を所与の平均到着間隔1/λ， 平均サービス率μ のM/G/∞によりモデル化する。またサービス時間の推定候補として、パラメトリックなk個の確率密度関数、
f1(x;θ11, θ12, ・・・, θn1), f2(x;θ21, θ22, ・・・, θn2),…, fk(x;θk1, θk2, ・・・, θnk)
が与えられているものとする。
【００８９】
まず、パラメータ同定部１０の動作を示す。
【００９０】
周期観測により時間T毎の平均流量N個の観測値｛ξi｝N i=1が得られている（観測時間がNTである）ことを前提とする。パラメータ同定手段では、まず観測値
ST :=｛ξi｝N i=1
の標本平均によりρの推定値とする：
【００９１】
【数２７】
次に、観測周期2T毎の平均接続数
S2T :={(ξ1+ξ2)/2， (ξ3+ξ4)/2, … }、
観測周期3T毎の平均値接続数
S3T :={(ξ1+ξ2 +ξ3)/3， (ξ4+ξ5 +ξ6)/3， ・・・}， …
を構成し、それぞれのp次までのキュムラントを算出する。次数pの値は、推定対象の分布のパラメータ数と、このキュムラントの理論式に依存して決める。各次数のキュムラントについて十分大きい時間における線形回帰を行い、回帰直線の傾きおよび切片を算出し、パラメータ推定値を算出・出力する。
【００９２】
適合検定部２０は、パラメータ同定部１０において推定されたl個の分布それぞれに対して、観測値に基づき適合度検定を実施する。帰無仮説は「当該分布が有意水準5%で観測値に適合している。」であり、これに対する仮説検定を実施する。全ての分布について帰無仮説が棄却された場合は、観測値の不足と判定し、再度観測値の収集を行う。
【００９３】
適合度検定部２０では、標本数に基づき、まずAnderson-Darling統計量T*を算出する。次にブートストラップ法により推定p値を算出し、その値の多寡に応じて帰無仮説の棄却是非を各分布について判定し、結果を出力する。
【００９４】
モデル選択部３０は、適合度検定部２０において棄却されなかった確率密度関数、
fi1(x;θi11, θi12, ・・・, θni1), fi2(x;θi21, θi22, ・・・, θni2),…, fik'(x;θik'1, θik'2, ・・・, θni k') (k'≦k)
から、真の確率密度関数に最も近いと推定されるものを選出・出力する。
【００９５】
モデル化部４０では前記パラメータ同定部１０の出力に基づき、推定された平均接続数とサービス時間の分布に基づきM/G/∞モデルを構成する。このモデルにより、任意の有限時間にわたるシミュレーションをm回反復して 実施し、各回の最大接続数を蓄積する。
【００９６】
最大値算出部５０は、上記モデル化手段の出力であるm個の最大接続数の経験累積分布を算出し、そのα確率点の値を出力する。この値を最大接続数の推定値として出力する。
【実施例】
【００９７】
本実施例では、以下の設定による実施例を示す。あるアプリケーションの接続が平均到着間隔10分(1/λ =0.1), 平均利用時間120 分(1/μ=120)、従って平均接続数12(ρ = 12) に従うものとし、観測周期60 分(T = 60) で平均接続数を観測しているものとする。観測値として、666個の観測値が図４に示すように得られている(観測時間666時間) ものとする。またサービス時間の真の分布は固定であり、推定候補としては、ａ．固定、ｂ．指数分布（ともにパラメータは1個）を設定する。
【００９８】
まず、パラメータ同定部１０では、このデータの標本平均により、平均接続数の推定値(1/ρ)として11.99を算出する。次に、各分布仮定時のパラメータ推定を行う。
【００９９】
１．M/D/∞を仮定した場合：
式（１）の右辺の理論値は、T>1/μの時
T/2μ-1 /6μ2
である。この理論値と標本値のプロットを図５に示す。線形回帰により、μの推定値
μ=1/119.83
を得る。
【０１００】
２．M/M/∞を仮定した場合：
式（１）の右辺の理論値は、
【０１０１】
【数２８】
でありTが大きい時
【０１０２】
【数２９】
に漸近する。線形回帰によるμの推定値は、
μ=1/59.9
である(図６)。
【０１０３】
次に、適合度検定部２０の動作を説明する。
【０１０４】
パラメータ同定部１０にて推定された各分布に対しブートストラップによるAnderson-Darling検定を実施した結果、p値として以下の結果を得た：ａ．0.36, ｂ．0.09。従って、適合度検定では5%の有意水準でいずれの分布も棄却されなかった。
【０１０５】
次に、モデル選択部３０では個々の分布に対して、まずパラメータ推定値に基づきキュムラント推定値を算出する。
【０１０６】
図４、７にキュムラント理論値および観測値のプロットを示す。また3次までのキュムラントに関するd''の算出結果として、
M/D/∞：d'' = 1.54
M/M/∞：d'' = 2.79
を得た。従ってM/D/∞が選択される。
【０１０７】
モデル化部４０では、前記パラメータ同定１０の出力に基づき、平均接続数11.99、サービス時間固定（119.83）のM/G/∞モデルを構成する。このモデルにより666時間にわたるシミュレーションを200回(m = 200) 実施し、各回の最大接続数を蓄積する。
【０１０８】
最大値算出部５０は、数値例では、上記モデル化手段の出力である666個の最大接続数の経験累積分布を算出し、その確率点αを99%の値として最大接続数25を出力する。その結果を図８に示す(なお、実際の666時間にわたる最大接続数は21であり、上記推定値の範囲に入っている)。この値を最大接続数の推定値として出力する。これが当該推定装置の最終出力である。
【０１０９】
なお、図２に示す各構成要素の上記の実施の形態及び実施例の動作をプログラムとして構築し、最大接続数推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１０】
本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１１１】
１０ パラメータ同定部
２０ 適合度検定部
３０ モデル選択部
４０ モデル化部
５０ 最大値算出部
【特許請求の範囲】
【請求項１】
IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定装置であって、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定手段と、
前記パラメータ同定手段の同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化手段と、
前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0<α<1)確率点推定を行う最大値算出手段と、
を有することを特徴とする、最大接続数推定装置。
【請求項２】
前記モデル化手段は、
前記パラメータ同定手段の前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する累積分布算出手段を含み、α(0 <α< 1) 確率点推定を行う
請求項１記載の最大接続数推定装置。
【請求項３】
前記パラメータ同定手段で推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定手段と、
前記適合度検定手段で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択手段と、
を更に有する請求項１記載の最大接続数推定装置。
【請求項４】
前記モデル選択手段は、
観測周期の各倍数上の平均接続数の2次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する手段を含む
請求項３記載の最大接続数推定装置。
【請求項５】
IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定方法であって、
パラメータ同定手段が、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定ステップと、
モデル化手段が、前記パラメータ同定ステップの同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化ステップと、
最大値算出手段が、前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0 <α< 1) 確率点推定を行う最大値算出ステップと、
を行うことを特徴とする、最大接続数推定方法。
【請求項６】
前記モデル化ステップにおいて、
前記パラメータ同定ステップの前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出し、α(0 <α< 1) 確率点推定を行う
請求項５記載の最大接続数推定方法。
【請求項７】
適合度検定手段が、前記パラメータ同定ステップで推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定ステップと、
モデル選択手段が、前記適合度検定ステップで棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択ステップと、
を更に行う請求項５記載の最大接続数推定方法。
【請求項８】
前記モデル選択ステップにおいて、
観測周期の各倍数上の平均接続数の2次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する
請求項７記載の最大接続数推定方法。
【請求項９】
コンピュータを、
請求項１乃至４のいずれか１項に記載の最大接続数推定装置の各手段として機能させるための最大接続数推定プログラム。
【請求項１】
IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定装置であって、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定手段と、
前記パラメータ同定手段の同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化手段と、
前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0<α<1)確率点推定を行う最大値算出手段と、
を有することを特徴とする、最大接続数推定装置。
【請求項２】
前記モデル化手段は、
前記パラメータ同定手段の前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出する累積分布算出手段を含み、α(0 <α< 1) 確率点推定を行う
請求項１記載の最大接続数推定装置。
【請求項３】
前記パラメータ同定手段で推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定手段と、
前記適合度検定手段で棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択手段と、
を更に有する請求項１記載の最大接続数推定装置。
【請求項４】
前記モデル選択手段は、
観測周期の各倍数上の平均接続数の2次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する手段を含む
請求項３記載の最大接続数推定装置。
【請求項５】
IPネットワーク上において、所定の観測周期毎にアプリケーションの平均接続数を観測し、得られた複数の観測値から、任意の有限時間内のアプリケーション接続数最大値を推定する最大接続数推定方法であって、
パラメータ同定手段が、
周期観測により得られた複数の平均接続数から到着率およびサービス時間分布のパラメータを推定するパラメータ同定ステップと、
モデル化手段が、前記パラメータ同定ステップの同定結果に基づき、アプリケーション接続数をモデル化するM/G/∞のパラメータにより構成されたM/G/∞モデルを構成するモデル化ステップと、
最大値算出手段が、前記M/G/∞モデルにおける任意の有限時間内の最大接続数の累積分布を算出し、そのα(0 <α< 1) 確率点推定を行う最大値算出ステップと、
を行うことを特徴とする、最大接続数推定方法。
【請求項６】
前記モデル化ステップにおいて、
前記パラメータ同定ステップの前記同定結果に基づき、前記M/G/∞モデルを構成し、各観測周期内の最大接続数と平均接続数の比率の累積分布を算出し、α(0 <α< 1) 確率点推定を行う
請求項５記載の最大接続数推定方法。
【請求項７】
適合度検定手段が、前記パラメータ同定ステップで推定されたサービス時間の分布に対し、観測値の適合度検定を行う適合度検定ステップと、
モデル選択手段が、前記適合度検定ステップで棄却されなかった複数のパラメトリックなサービス時間の分布から、最も適切と思われる分布を選択するモデル選択ステップと、
を更に行う請求項５記載の最大接続数推定方法。
【請求項８】
前記モデル選択ステップにおいて、
観測周期の各倍数上の平均接続数の2次からｎ次のキュムラント理論値を算出し、各々の観測値との差の平方をとり、その荷重和の比較によりモデル選択を実現する
請求項７記載の最大接続数推定方法。
【請求項９】
コンピュータを、
請求項１乃至４のいずれか１項に記載の最大接続数推定装置の各手段として機能させるための最大接続数推定プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−２２２６６８（Ｐ２０１２−２２２６６８Ａ）
【公開日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願番号】特願２０１１−８７６８０（Ｐ２０１１−８７６８０）
【出願日】平成２３年４月１１日（２０１１．４．１１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願日】平成２３年４月１１日（２０１１．４．１１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]