(57)【要約】【課題】元のフローサイズ分布をサンプルしたフローサイズデータより推定する際に、計算量を大幅に削減しつつも精度の良いフローサイズ分布の推定を実現する。【解決手段】フロー統計推定装置１０は、ネットワーク上のルータ・スイッチ等の計測装置１１、１２がパケットサンプリングを適用して計測したフローデータ（サンプルフローデータ１３、１４）を任意に指定が可能なインターバルで取得する。次に、フロー統計推定装置１０は、フロー計測装置１１、１２に設定されているサンプリングレートの値１５およびサンプルフローデータ１３、１４を元に、裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデル１６を用いて、サンプル前のフローサイズの分布を統計的に推定する。【選択図】図１
2008118588.tif 000002
【特許請求の範囲】
【請求項１】
サンプルフローデータに基づいてサンプル前のフローサイズの分布を統計的に推定するフロー統計推定装置におけるフロー統計推定方法であって、
前記フロー統計推定装置が、
ネットワーク上の計測装置がパケットサンプリングを適用して計測したフローデータを取得するデータ取得ステップと、
前記フロー計測装置に設定されているサンプリングレートの値および前記データ取得ステップで取得したサンプルフローデータを元に、裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデルを用いて、サンプル前のフローサイズの分布を統計的に推定する推定ステップと、
を有することを特徴とするフロー統計推定方法。
【請求項２】
請求項１に記載のフロー統計的推定方法において、
前記フロー統計推定装置が、前記推定ステップにおいて、１パケット以上サンプルされたサンプルフローデータである観測データに対して、ＥＭアルゴリズムを適用することによってサンプル前のフローサイズ分布のパラメタを推定することを特徴とするフロー統計推定方法。
【請求項３】
請求項１に記載のフロー統計的推定方法において、
前記フロー統計推定装置が、前記推定ステップにおいて、未観測データであるサンプルされなかったフローの数である非サンプルフロー数の情報を前記計測装置より取得し、最尤法を適用することによってサンプル前のフローサイズ分布のパラメタを推定することを特徴とするフロー統計推定方法。
【請求項４】
サンプルフローデータに基づいてサンプル前のフローサイズの分布を統計的に推定するフロー統計推定装置であって、
ネットワーク上の計測装置がパケットサンプリングを適用して計測したフローデータを取得するデータ取得手段と、
前記フロー計測装置に設定されているサンプリングレートの値および前記データ取得手段が取得したサンプルフローデータを元に、裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデルを用いて、サンプル前のフローサイズの分布を統計的に推定する推定手段と、
を有することを特徴とするフロー統計推定装置。
【請求項５】
請求項１ないし３のうちいずれか１項に記載のステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパケットサンプリングを適用して得られるサンプルフローデータより元のフロー統計を推定する技術に関する。
【背景技術】
【０００２】
ネットワーク運用管理において、ネットワーク上を流れるトラヒックがどのようなフローによって構成されるかを把握することは重要である。ここにフローとは、例えばＩＰパケットの場合は「発ＩＰアドレス、着ＩＰアドレス、発ポート番号、着ポート番号、プロトコル種別」のＩＰヘッダに記載される５つのレコードの組み合わせによって定義されるものであり、パケットヘッダ上のレコードおよびそれらのパケットヘッダに記録されたレコードに関連するパケットヘッダには直接記録されていないデータ（たとえばＩＰアドレスに対応するＡＳ番号など）を任意に組み合わせることによって様々なフローの定義が可能である。フロー毎のサイズを調べ、フローサイズの分布を得ることにより、どのような大きさのフローがどの程度ネットワークを流れているかなどの制御・管理に有用な情報を定量的に得ることができる。またフローサイズの分布を得ることにより、分布の変化を元にネットワークに生じた異常を検出することが可能となる。
【０００３】
近年のネットワーク回線の超高速化に伴い、回線上を流れるすべてのパケットデータからフロー統計を構成するのではなく、サンプリングによって得られる一部のパケットデータからフロー統計を構成する手法が実用に供している。ここでパケットサンプリングとは、時々刻々と到着するパケットに対して、確率的あるいはＮ個毎に１個のパケットを参照する等の決定的なルールに従ってサンプリングを行う技術である。フローを計測する際にパケットサンプリングを適用することにより、計測・データ蓄積に必要となる処理速度、メモリ量等のリソースを大幅に削減することができる。
【０００４】
以上のようにパケットサンプリング技術をフロー計測に適用することによって処理速度、保持データ量の観点でスケーラビリティを向上することができるが、サンプリングによって一部のパケットデータは観測されないため、サンプルしたフロー統計は元のフロー統計と異なる。このため、サンプル前のフローデータがどのようなものであったかはサンプルしたフローデータから統計的に推定する必要がある。
【０００５】
非特許先行文献１では分布モデルを仮定しないノンパラメトリックな方法によって、サンプルフロー統計から元のフロー分布を推定する手法を提案している。しかしながら同手法は推定に要する計算量が多大であるため、リアルタイムでサンプルフロー統計から元のフロー統計を推定するような用途には適用することができない問題がある。
【０００６】
【非特許文献１】Nick Duffield, Carsten Lund, Mikkel Thorup,“ Estimating Flow Distributions from Sampled Flow Statistics”, Proceedings the ACM SIGCOMM, pp.325-336, 2003
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は上記の課題を鑑みてなされたものであり、元のフローサイズ分布をサンプルしたフローサイズデータより推定する際に、計算量を大幅に削減しつつも精度の良いフローサイズ分布の推定を実現することが本発明の課題である。
【課題を解決するための手段】
【０００８】
本明細書において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。
【０００９】
上述の目的を達成するため、請求項１の発明は、サンプルフローデータに基づいてサンプル前のフローサイズの分布を統計的に推定するフロー統計推定装置におけるフロー統計推定方法であって、前記フロー統計推定装置が、ネットワーク上の計測装置がパケットサンプリングを適用して計測したフローデータを取得するデータ取得ステップと、前記フロー計測装置に設定されているサンプリングレートの値および前記データ取得ステップで取得したサンプルフローデータを元に、裾野を長く引く特徴を持ち、かつ１個以上のパラメタ数を有する分布モデルを用いて、サンプル前のフローサイズの分布を統計的に推定する推定ステップと、を有することを特徴とするフロー統計推定方法である。なお、フローのサイズ（フローサイズ）とはフロー毎のパケット数である。
【００１０】
以下、前記の分布モデルについて説明する。あるフローｊのサンプル前のパケット数をＸｊとする。すなわち、Ｘｊはフローｊのサンプル前のフローサイズである。このとき、離散変数Ｘｊのしたがう分布モデルをΘ＝｛θ１，θ２，…θｍ｝をパラメタとする確率関数によって表現する。すなわち、
【００１１】
【数１】
2008118588.tif 000003
とする。ここでΘは確率分布のパラメタの集合を表しており、ｍはパラメタの数であり、θ１，θ２，…θｍはパラメタの集合Θを構成するパラメタである。（１）式は、あるフローｊのフローサイズＸｊがある値ｘになる確率ｐが、Θをパラメタとする確率関数ｆ（ｘ；Θ）に等しいことを表した式である。
【００１２】
ここで分布モデルは、任意のモデルを選択することができるが、一般にフロー分布は裾野を長く引く分布にしたがうことが知られているので、そのような特徴を有する分布モデルを選択の候補とする。また、本発明はパラメトリックな方法によって元のフローを推定するものであり、１個以上のパラメタを有する分布モデルを使用するが、計算量を削減する観点から、パラメタの数は少ない方がよく、パラメタ数が１〜３程度の単純な分布モデルを選択の候補とするのが望ましい。上記二つの特徴を満たす分布モデルとして、例えば離散パレート分布、Ｙｕｌｅ−Ｓｉｍｏｎ分布、ワイブル分布、対数正規分布などを選択することができるが、本発明の適用範囲はこの限りではない。
【００１３】
請求項２の発明は、請求項１に記載のフロー統計的推定方法において、前記フロー統計推定装置が、前記推定ステップにおいて、１パケット以上サンプルされたサンプルフローデータである観測データに対して、ＥＭアルゴリズムを適用することによってサンプル前のフローサイズ分布のパラメタを推定することを特徴とするフロー統計推定方法である。
【００１４】
以下、前記のパラメタの推定方法（「第一の推定方法」という）について説明する。パケットをサンプリングレートｆ（０≦ｆ≦１）でランダムにサンプルした場合、あるフローの元のパケット数がＸｊ＝ｘである条件の元でそのフローについてサンプルされたパケット数がＹｊ＝ｙである確率は二項分布によって、
【００１５】
【数２】
2008118588.tif 000004
である。ここでＹｊはフローｊのサンプル後のフローサイズである。Ｐｒ（Ｙｊ＝ｙ｜Ｘｊ＝ｘ）は、あるフローｊのフローサイズＸｊがｘであった条件の元で、そのフローｊのサンプルフローサイズＹｊがｙとなる確率（条件付確率）である。ｑ（ｙ｜ｘ）は、Ｐｒ（Ｙｊ＝ｙ｜Ｘｊ＝ｘ）を簡単に記述するために導入した関数である。
【００１６】
このとき、あるフローｊについてサンプルされたパケット数がＹｊ＝ｙとなる確率は、（１）、（２）式を用いて
【００１７】
【数３】
2008118588.tif 000005
となる。ここでｒ（ｙ；Θ）は、Ｐｒ（Ｙｊ＝ｙ）を簡単に記述するために導入した関数である。Ｎは母集団に含まれるパケットの総数である。
【００１８】
ｉパケットサンプルされたフローの数ｎｉとしたとき、未観測のデータｎ０を含めた完全対数尤度ｌｏｇ ＬＣ（Θ）は、（３）式のｒ（ｙ）を用いて
【００１９】
【数４】
2008118588.tif 000006
となる。ここでｉはサンプルされたパケット数であり、ｎｉ（ｉ＝０，１，２，...）はｉ個のパケットがサンプルされたフローの数である。ＬＣ（Θ）は完全尤度である（Ｌ＝likelihood、Ｃ＝complete）。対数をとったものが完全対数尤度である。
【００２０】
以下ではＥＭアルゴリズムによってパラメタΘを求める手段について述べる。Θ＝Θ（０）をパラメタの初期推定値とする。このパラメタが与えられているとき、（４）式で定義される完全対数尤度の、観測データｎｉ（ｉ≧１）を得た下での条件付期待値
【００２１】
【数５】
2008118588.tif 000007
を計算する（Ｅ−ｓｔｅｐ）。つぎにＱ（Θ；Θ（０））を最大化するようなΘを数値計算によって求め、その値をΘ＝Θ（１）とする（Ｍ−ｓｔｅｐ）。以下同様にΘ（ｉ）（ｉ＝１，２，...）を繰り返し計算する。Θ（ｉ−１）とΘ（ｉ）の差が十分に小さくなったら、Θ（ｉ）をパラメタの推定値とする。
【００２２】
なお、（５）式において、Ｑ（Θ；Θ（０））は、右辺の式を簡単に記述するために導入した関数である。以下、（５）式の右辺のＥΘ（０）｛ｌｏｇ ＬＣ（Θ）｜ｎ１，ｎ２，...，ｎｍ｝について説明する。まず、一般的に述べると、Ｅ｛Ｘ｝はＸの期待値（expectation）であり、Ｅ｛Ｘ｜Ｙ｝はＹが与えられた元でのＸの期待値である。したがって、Ｅ｛ｌｏｇ ＬＣ（Θ）｜ｎ１，ｎ２，...，ｎｍ｝は、ｎ１，ｎ２，...，ｎｍ（観測データ）があたえられた元での対数尤度ｌｏｇ ＬＣ（Θ）の期待値である。ところで、ＥΘ（０）｛Ｘ（Θ）｝は、ΘをΘ＝Θ（０）としたときのＸ（Θ）の期待値である。結局、（５）式の右辺のＥΘ（０）｛ｌｏｇ ＬＣ（Θ）｜ｎ１，ｎ２，...，ｎｍ｝は、ΘをΘ＝Θ（０）としたとき、ｎ１，ｎ２，...，ｎｍ（観測データ）が与えられた条件の元での対数尤度ｌｏｇ ＬＣ（Θ）の期待値である。
【００２３】
ここで（５）式の条件付期待値は未観測データｎ０に関して線形の関数であるので、ｎ０の条件付期待値ｎ０（０）＝ＥΘ（０）（ｎ０｜ｎ１，ｎ２，...，ｎｍ）を（４）式のｎ０に代入することで得られる。ｎ０（０）は下式のオッズ比によって推定する。
【００２４】
【数６】
2008118588.tif 000008
請求項３の発明は、請求項１に記載のフロー統計的推定方法において、前記フロー統計推定装置が、前記推定ステップにおいて、未観測データであるサンプルされなかったフローの数である非サンプルフロー数の情報を前記計測装置より取得し、最尤法を適用することによってサンプル前のフローサイズ分布のパラメタを推定することを特徴とするフロー統計推定方法である。
【００２５】
以下、前記のパラメタの推定方法（「第二の推定方法」という）について説明する。第二の方法では、第一の方法において未観測であったデータｎ０、あるいはその推定値を別途なんらかの方法で取得できた場合、そのデータを用いて推定を行うことにより、推定精度の向上を図ることを狙いとする。具体的には、取得したｎ０を（４）式の完全対数尤度に代入し、（４）式を最大化するようなΘを数値計算によって求める。
【発明の効果】
【００２６】
本発明によれば、元のフローサイズ分布をサンプルしたフローサイズデータより推定する際に、計算量を大幅に短縮することが可能である。
【発明を実施するための最良の形態】
【００２７】
以下、図表を用いて本発明の実施例を説明する。またフローは発ＩＰアドレス、着ＩＰアドレス、発ポート番号、着ポート番号、プロトコル種別、の５つのキー（以下、フローキー）によって定義するが、本発明の適用範囲はこの限りではない。
【００２８】
図１は本発明の適用形態の一例を示す図である。１０はフロー統計推定装置、１１、１２はルータ・スイッチ等のフローを計測するフロー計測装置、１３、１４はそれぞれフロー計測装置１１、１２からフロー統計推定装置１０へ送信されるサンプルフローデータである。フロー計測装置１１、１２はそれを通過するパケットをサンプリングしてフローデータ（サンプルフローデータ）を作成する。フロー統計推定装置１０は、サンプルフローデータに基づいてサンプル前のフローサイズの分布を統計的に推定する装置である。フローサイズとはフロー毎のパケット数である。
【００２９】
フロー統計推定装置１０は単数あるいは複数のルータ・スイッチ等のフロー計測機能を有するフロー計測装置１１、１２がパケットサンプリングを適用して計測したフローデータ（サンプルフローデータ）を、任意の値に指定が可能なインターバルで取得する。ここでサンプルフローデータには少なくともフローキーと、各々のキーに対応する計測インターバル内での累積パケット数が含まれているものとする。フロー統計推定装置１０は前記のインターバルでサンプリングフローデータを取得する毎にフロー統計推定を行う。フロー統計推定装置１０は前記取得したサンプルフローデータ１３、１４、フロー計測装置１１、１２に設定されているサンプリングレートの値１５、および裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデル、例えば、離散パレート分布、Ｙｕｌｅ−Ｓｉｍｏｎ分布、ワイブル分布、対数正規分布から選択する分布モデル１６を入力とし、分布モデルに対するパラメタの推定値である推定パラメタ１７を出力として返す。
【００３０】
なお、後述する第二の方法では、フロー計測装置１１、１２でサンプルされなかったフロー数（非サンプルフロー数）の情報１８を追加の入力項目として利用する。このように第二の推定方法では非サンプルフロー数はフロー計測装置１１、１２等で計測した結果を用いて推定するが、後述する第一の推定方法では非サンプルフロー数も含めて推定する。
【００３１】
フロー統計推定装置１０は、ネットワーク上に設けられた複数のフロー計測装置からサンプルフローデータを取得し、ネットワーク全体のフロー統計推定を行うが、各フロー計測装置毎にフロー統計推定を行うようにしてもよい。
【００３２】
図２に、フロー統計推定装置１０の動作を示すフローチャートの例を示す。２１はデータ取得ステップであり、２２は推定ステップである。フロー統計推定装置１０は、データ取得ステップ２１において、ネットワーク上の計測装置１１、１２がパケットサンプリングを適用して計測したフローデータを任意に指定が可能なインターバルで取得する。次に、フロー統計推定装置１０は、推定ステップ２２において、フロー計測装置１１、１２に設定されているサンプリングレートの値１５およびデータ取得ステップ２１で取得したサンプルフローデータ１３、１４を元に、裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデル１６を用いて、サンプル前のフローサイズの分布を統計的に推定する。
【００３３】
分布モデルは１個以上のパラメタを有するものであればよいが、計算量を削減する観点から、パラメタ数は少ない方がよく、１〜３程度が望ましい。分布モデルとして、例えば離散パレート分布、Ｙｕｌｅ−Ｓｉｍｏｎ分布、ワイブル分布、対数正規分布等を使用することができる。なお、後述の例では離散パレート分布を使用している。
【００３４】
また、フロー統計推定装置１０は、データ取得ステップ２１において、前述のように裾野を長く引く特徴を持ち、かつ１個以上のパラメタを有する分布モデルを用いるが、このパラメタの推定方法として、以下に示す第一の推定方法または第二の推定方法を使用する。
【００３５】
第一の推定方法では、フロー統計推定装置１０は、推定ステップ２２において、１パケット以上サンプルされたサンプルフローデータである観測データに対して、ＥＭアルゴリズムを適用することによって、観測できない１パケットもサンプルされないフローの情報を含む、サンプル前のフローサイズ分布のパラメタを推定する。
【００３６】
第二の推定方法では、フロー統計推定装置１０は、推定ステップ２２において、未観測データであるサンプルされなかったフローの数である非サンプルフロー数の情報１８を計測装置１１、１２より取得し、最尤法を適用することによってサンプル前のフローサイズ分布のパラメタを推定する。
【００３７】
なお、分布モデル、第一の推定方法、第二の推定方法についての式を用いた説明は「課題を解決するための手段」に記載したとおりである。
【００３８】
以下、サンプル前のフローサイズ分布、およびサンプル後のフローデータの実例を示す。図３の実線（Original）はあるネットワークを５分間にわたって計測したトラヒックデータを用い、（サンプル前の）フローサイズの分布を累積分布の補分布として示したものである。図３の横軸はフローサイズ（Flow length）すなわちフローあたりに含まれるパケットの数である。縦軸は累積補分布（ＣＣＤ：complementary cumulative distribution）である。横軸および縦軸はどちらも対数表示である。
【００３９】
図４に示す表１は前記トラヒックデータに対して、サンプリングレートをｆ＝０．００１としたパケットサンプリングを適用したときのサンプルフローデータ（ｉ，ｎｉ）である。ここに、ｉはサンプルされたパケット数であり、ｎｉ（ｉ＝０，１，２，...）はｉパケットサンプルされたフローの数（ｉ個のパケットがサンプルされたフローの数）である。パケットサンプリングはよく用いられるランダムサンプリングを適用した。表１には、１個のパケットがサンプルされたフローの数が１３１７個であり、２個のパケットがサンプルされたフローの数が１２１個であり、３個のパケットがサンプルされたフローの数が３６個であり、…４０８個のパケットがサンプルされたフロー数が１個であることが示されている。表１は観測データを示す表であるから、ｉ＝０の場合、すなわち１パケットもサンプルされないフローの数についてのサンプルフローデータは記載されていない。第一の推定方法を用いる場合はフロー統計推定装置１０は表１のサンプルフローデータを取得するだけでよいが、第二の推定方法を用いる場合は別途、１パケットもサンプルされなかったフローの数である非サンプルフロー数の情報（ｉ＝０の場合のフロー数の情報）を取得する必要がある。
【００４０】
以下では分布モデルの選択において離散パレート分布を選択した例を説明するが、本発明の適用形態はこの例に限られるものではない。（１）式の確率関数を離散パレート分布によって
【００４１】
【数７】
2008118588.tif 000009
とモデル化する。パラメタは形状母数θ＞０である。ただしｘ＝１，２，...である。なお、（１）式はｍ個のパラメタを有するパラメタの集合Θ＝｛θ１，θ２，...θｍ｝で一般的に表した式であるが、（６）式は１個のパラメタΘ＝｛θ１｝の場合であり、これを簡単にθと記載している。
【００４２】
図３の破線（fitting）は実線で示したフローサイズ分布を離散パレート分布によってモデル化した結果を示す。このときパラメタθの最尤推定値はθ＝１．２４３であった。モデル分布は実際の分布を比較的良くフィッティングできていることがわかる。このパラメタの値を推定することが第一の推定方法、第二の推定方法の目標である。
【００４３】
第一の推定方法では、（６）式のｆ（ｘ；θ）を（５）式に代入する。また対数尤度の条件付期待値Ｑ（θ；θ（ｉ））を最大化するθ＝θ（ｉ＋１）はＱ（θ；θ（ｉ））のθに関する偏微分をｑ（θ）＝∂Ｑ（θ，θ（ｉ））／∂θとし、ｑ（θ）＝０をニュートン法によって解く。
【００４４】
この結果、パラメタの推定値θ＝１．０１７を得ることができた。なおＥＭアルゴリズムはθ（ｉ−１）とθ（ｉ）の差の絶対値が０.０００１より小さくなるまで繰り返した。
【００４５】
第二の推定方法では、第一の推定方法と同様に（６）式のｆ（ｘ；θ）を代入し、完全対数尤度ｌｏｇ ＬＣ（θ）を最大にするθを求めるのに、完全対数尤度のθに関する偏微分が０となるようなθをニュートン法によって解く事によって得る。また、ここではｎ０は計測装置が観測したものとして、真の値を代入した。この結果、パラメタの推定値をθ＝１.０７３として求めることができる。
【００４６】
以上の２つの方法によって算出したパラメタθを用い、推定フローサイズ分布を図１に示した元のフロー分布と合わせて描いた結果を図３の破線（第一の方法→method 1，第二の方法→method 2）に示す。いずれの方法も比較的精度よく分布を推定していることがわかる。また、第二の方法のほうがより元のパラメタの値θ＝１.２４３に近いことがわかる。
【００４７】
本実施例のフロー統計推定装置１０は、その動作、ステップ、機能を実現する手段を有しており、その手段はコンピュータとプログラムによって構成することができる。また、そのプログラムの一部または全部に換えてハードウェアを用いて構成してもよい。
【００４８】
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００４９】
【図１】本発明の適用形態の例を示す図である。
【図２】本発明のフロー統計推定装置の動作を示すフローチャートの例を示す。
【図３】本発明における推定の対象となるフロー分布、前記フロー分布の分布モデルによる近似、および本発明によって推定したフロー分布の例を示す図である。
【図４】本発明におけるサンプルフローデータの例を示す表（表１）である。
【符号の説明】
【００５０】
１０…フロー統計推定装置、１１，１２…フロー計測装置、１３，１４…サンプルフローデータ、１５…サンプリングレート、１６…分布モデル、１７…推定パラメタ、１８…非サンプルフロー数。
【図１】
2008118588.tif 000010
【図２】
2008118588.tif 000011
【図３】
2008118588.tif 000012
【図４】
2008118588.tif 000013