(57)【特許請求の範囲】
【請求項１】
IP（Internet  Protocol）ネットワークの通信品質状態を管理するフロー品質劣化特定装置であって、
前記ネットワーク上のフロー情報として、フロー毎のバイト数と持続時間を収集するフロー受信手段と、
受信した前記フロー情報を基にフローレートを計算するフローレート計算手段と、
前記フロー情報に基づいて、発信元エリアと着信先エリアを特定し、前記フローレートを基にエリア間フローレートを算出するエリア間フローレート管理手段と、
前記エリア間フローレートの時系列データを生成し、所定の基準に基づいて該エリア間フローレートの品質を判定し、該エリア間フローレートの品質低下が同期して発生しているエリアを検出するフロー品質劣化検出手段と、
前記エリア間フローレートと前記フロー品質劣化検出手段で検出された品質が劣化したエリア間フローレートの情報を基に、エリア間に共通のエリア間フロー品質の劣化が同期するエリアを抽出するレート低下ペア抽出手段と、
を有し、
前記フロー品質劣化検出手段は、
前記エリアのペア間の距離を計算し、該距離をクラスタリングし、該エリアのペアが同じクラスタに分類された場合、該エリアのペアをレートが低下した同期ペアとして抽出する手段を含む
ことを特徴とするフロー品質劣化特定装置。
【請求項２】
前記フロー受信手段は、
測定開始から予め定めた時間周期t0を経過するまでの期間において、
IPネットワーク内のノード（群）から受信するパケットに対し、N個の受信パケットから任意の1個のパケットを抽出し、抽出した該パケットヘッダの情報を基に該パケットが属するフロー(フローｉ)を検出し、検出された該フローｉについて、ユーザフロー管理テーブルへの登録の有無を確認し、
該フローｉの登録がない場合は、該フローｉについて、該パケットが最初に到着した時刻(T_first_i)と最後に到着した時刻(T_last_i)を現在の時刻とし、最後に到着したパケットのシーケンス番号(SN_last_i)を該パケットヘッダから読み出したシーケンス番号とし、最初に到着したパケットのシーケンス番号(SN_first_i)を{該シーケンス番号  −  該パケットサイズ}として設定し、前記ユーザフロー管理テーブルに該フローｉを登録し、
該フローｉが登録されている場合は、該フローｉについて、最後に到着した時刻を現在の時刻とし、最後に到着したパケットのシーケンス番号を該パケットヘッダから読み出したシーケンス番号として、前記ユーザフロー管理テーブルにおける該フローｉの登録情報を更新する、
ことを繰り返す手段を含み、
前記フローレート計算手段は、
前記時間周期t0経過時点において、
前記フローｉのパケットが最初に到着した時刻と最後に到着した時刻が同一であれば、該フローｉを前記ユーザフロー管理テーブルから削除し、
該フローｉの該パケットが最初に到着した時刻より最後に到着した時刻が後であれば、該フローｉのフローレートを計算し、前記ユーザフロー管理テーブルに登録された該フローｉのフローレートに設定する手段を含む
請求項１記載のフロー品質劣化特定装置。
【請求項３】
前記エリア間フローレート管理手段は、
前記エリア間フローレートを算出する際に、
エリア間のフローのレートの平均を用いる方法、
もしくは、
上位Xパーセンタイル(Xは任意に設定可能)に対応するエリア間のフローレートを選択する方法、
を用いる請求項１記載のフロー品質劣化特定装置。
【請求項４】
IP（Internet  Protocol）ネットワークの通信品質状態を管理するフロー品質劣化特定方法であって、
フロー受信手段が、前記ネットワーク上のフロー情報として、フロー毎のバイト数と持続時間を収集するフロー受信ステップと、
フローレート計算手段が、受信した前記フロー情報を基にフローレートを計算するフローレート計算ステップと、
エリア間フローレート管理手段が、前記フロー情報に基づいて、発信元エリアと着信先エリアを特定し、前記フローレートを基にエリア間フローレートを算出するエリア間フローレート管理ステップと、
フロー品質劣化検出手段が、前記エリア間フローレートの時系列データを生成し、所定の基準に基づいて該エリア間フローレートの品質を判定し、該エリア間フローレートの品質低下が同期して発生しているエリアを検出するフロー品質劣化検出ステップと、
レート低下ペア抽出手段が、前記エリア間フローレートと前記フロー品質劣化検出手段で検出された品質が劣化したエリア間フローレートの情報を基に、エリア間に共通のエリア間フロー品質の劣化が同期するエリアを抽出するレート低下ペア抽出ステップと、
を行い、
前記フロー品質劣化検出ステップにおいて、
前記エリアのペア間の距離を計算し、該距離をクラスタリングし、該エリアのペアが同じクラスタに分類された場合、該エリアのペアをレートが低下した同期ペアとして抽出することを特徴とするフロー品質劣化特定方法。
【請求項５】
前記フロー受信ステップにおいて、
測定開始から予め定めた時間周期t0を経過するまでの期間において、
IPネットワーク内のノード（群）から受信するパケットに対し、N個の受信パケットから任意の1個のパケットを抽出し、抽出した該パケットヘッダの情報を基に該パケットが属するフロー(フローｉ)を検出し、検出された該フローｉについて、ユーザフロー管理テーブルへの登録の有無を確認し、
該フローｉの登録がない場合は、該フローｉについて、該パケットが最初に到着した時刻(T_first_i)と最後に到着した時刻(T_last_i)を現在の時刻とし、最後に到着したパケットのシーケンス番号(SN_last_i)を該パケットヘッダから読み出したシーケンス番号とし、最初に到着したパケットのシーケンス番号(SN_first_i)を{該シーケンス番号  −  該パケットサイズ}として設定し、前記ユーザフロー管理テーブルに該フローｉを登録し、
該フローｉが登録されている場合は、該フローｉについて、最後に到着した時刻を現在の時刻とし、最後に到着したパケットのシーケンス番号を該パケットヘッダから読み出したシーケンス番号として、前記ユーザフロー管理テーブルにおける該フローｉの登録情報を更新する、
ことを繰り返し、
前記フローレート計算ステップにおいて、
前記時間周期t0経過時点において、
前記フローｉのパケットが最初に到着した時刻と最後に到着した時刻が同一であれば、該フローｉを前記ユーザフロー管理テーブルから削除し、
該フローｉの該パケットが最初に到着した時刻より最後に到着した時刻が後であれば、該フローｉのフローレートを計算し、前記ユーザフロー管理テーブルに登録された該フローｉのフローレートに設定する
請求項４記載のフロー品質劣化特定方法。
【請求項６】
前記エリア間フローレート管理ステップにおいて、
前記エリア間フローレートを算出する際に、
エリア間のフローのレートの平均を用いる方法、
もしくは、
上位Xパーセンタイル(Xは任意に設定可能)に対応するエリア間のフローレートを選択する方法、
を用いる請求項４記載のフロー品質劣化特定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フロー品質劣化特定装置及び方法に係り、特に、IPネットワークの通信品質状態を管理するため、劣化要因となる箇所を特定するフロー品質劣化特定装置及び方法に関する。
【背景技術】
【０００２】
IPネットワークが広く利用されてくるに伴って、IPネットワーク上での通信品質保証に対する要求が高まっている。現状のIPネットワーク管理においては、あるリンクが輻輳しているか否かは主にリンク使用率から判定している。しかし、リンク使用率とユーザの体感するファイル転送時間やスループット等の品質との関連が不明であるため、輻輳状態と判定する使用率を具体的に特定することが困難であった。
【０００３】
また、リンクを通過するフローのファイル転送時間やスループットを測定し、その平均等の統計値がある閾値以下になった場合を輻輳状態と判定する方法は、
１）ファイル転送時間やスループットといったユーザ品質測定は、当該リンク上を通過する全てのパケットをキャプチャしフローを組み上げて算出するか、もしくは当該リンクの前段か後段もしくは両方に試験パケット送受信機を設置して、試験パケットを送信することによって品質測定を能動的に行う必要があり、一般的にこれは困難である；
２）当該リンクがボトルネックでない場合であっても、当該リンクを通過するフローの、通過する前後のネットワークの状態によって平均スループットはネットワーク毎に異なり、ファイル転送時間やスループットに対する具体的な閾値の設定が困難である；
という問題があった。
【０００４】
一方、近年、フロー測定技術が広く利用されている。フローとは、{送信元IPアドレス、宛先IPアドレス、送信元ポート番号、宛先ポート番号、プロトコル}の５つ組を同じくするパケット群と定義するのが一般的である。フロー測定では、フロー毎のパケット数やバイト数、継続時間を情報として出力する。しかしながら、フローデータは主に交流トラヒック量を算出したり、特定の宛先へのトラヒックの集中を検知したり、あるいはヘビーユーザ特定、といった、トラヒックボリュームに関する情報を使うのが一般的である。
【０００５】
通常、スケール性を担保するために、パケットサンプリングを実施することによってフロー管理に必要とされる処理を軽減する（例えば、非特許文献１参照）。例えばN個に1個のパケットをサンプルし、サンプルされたパケットから元のフロー統計情報を推定する。
【０００６】
また、パケットサンプリングを用いてリンク帯域の占有率が高いフローを特定する方法が提案されている（例えば、非特許文献２参照）。
【０００７】
また、フローサイズが大きいフローの統計を精度よく得る方法が提案されている（例えば、非特許文献３参照）。
【０００８】
さらに、サンプルされたSYNパケット（TCPフラグの一つで、通信開始を意味する）の数を用いて、サンプルされていない全体のフロー発生数やフローサイズを推定する方法が提案されている（例えば、非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】IETF RFC 5474 A Framework for Packet Selection and Reporting http://datatracker.ietf.org/wg/psamp/.
【非特許文献２】T. Mori, T. Takine, J. Pan, R. Kawahara, M. Uchida, and S. Goto, ''Identifying heavy-hitter flows from sampled flow statistics,'' IEICE Trans. Commun., vol.E90-B, no.11, pp.3061-3072, Nov. 2007.
【非特許文献３】C. Estan and G. Varghese, "New Directions in Traffic Measurement and Accounting," ACM SIGCOMM2002, Aug. 2002.
【非特許文献４】N. Duffield, C. Lund, and M. Thorup, "Properties and Prediction of Flow Statistics from Sampled Packet Streams," ACM SIGCOMM Internet Measurement Conference 2002, Nov. 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、上記の非特許文献２、３の提案方法は、サイズの大きい、あるいは帯域の占有率が高いフローを特定し、それらフローを過剰に発生するユーザを迅速に切り分けることを目的としており、あるリンク上のフロー全体の通信品質を管理することを可能にするものではなかった。
【００１１】
また、非特許文献４の提案方法も元のフロー統計情報を推定するに留まっており、あるリンク上のフロー全体の通信品質を管理することを可能にするものではなかった。
【００１２】
本発明は、上記の点に鑑みなされたもので、フロー管理に要する処理を軽減しつつ、フロー情報を活用してフロー全体の品質を把握して、フローの品質劣化が生じていればそれを検出し、かつその劣化要因箇所の特定を可能するフロー品質劣化特定装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記の課題を解決するため、IPネットワークの通信品質状態を管理するフロー品質劣化特定装置であって、
前記ネットワーク上のフロー情報として、フロー毎のバイト数と持続時間を収集するフロー受信手段と、
受信した前記フロー情報を基にフローレートを計算するフローレート計算手段と、
前記フロー情報に基づいて、発信元エリアと着信先エリアを特定し、前記フローレートを基にエリア間フローレートを算出するエリア間フローレート管理手段と、
前記エリア間フローレートの時系列データを生成し、所定の基準に基づいて該エリア間フローレートの品質を判定し、該エリア間フローレートの品質低下が同期して発生しているエリアを検出するフロー品質劣化検出手段と、
前記エリア間フローレートと前記フロー品質劣化検出手段で検出された品質が劣化したエリア間フローレートの情報を基に、エリア間に共通のエリア間フロー品質の劣化が同期するエリアを抽出するレート低下ペア抽出手段と、を有し、
前記フロー品質劣化検出手段は、
前記エリアのペア間の距離を計算し、該距離をクラスタリングし、該エリアのペアが同じクラスタに分類された場合、該エリアのペアをレートが低下した同期ペアとして抽出する手段を含む。
【発明の効果】
【００１４】
以上説明したように、本発明によれば、フロー管理に要する処理を軽減しつつ、フロー情報を活用してフロー全体の品質を把握して、フローの品質劣化が生じていれば、それを検出し、かつ、その結果要因箇所のフロー品質劣化特定を可能とする。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１の実施の形態におけるシステム構成図である。
【図２】本発明の第１の実施の形態におけるフロー品質劣化特定装置の構成図である。
【図３】本発明の第１の実施の形態における動作のフローチャートである。
【図４】本発明の第１の実施の形態における測定されたフローレートの時系列の例である。
【図５】本発明の第１の実施の形態におけるＡＳ間に共通の経路上のリンク回線のリンク使用率である。
【図６】本発明の第２の実施の形態におけるフロー品質劣化特定装置の構成図である。
【図７】本発明の第２の実施の形態における動作のフローチャートである。
【図８】本発明の第２の実施の形態におけるユーザフロー管理テーブルの例である。
【発明を実施するための形態】
【００１６】
以下、図面と共に本発明の実施の形態を説明する。
【００１７】
［第１の実施の形態］
図１は、本発明の第１の実施の形態におけるシステム構成を示す。
【００１８】
同図に示すシステムは、ＩＰネットワーク１０１上の複数のノード１０とフロー品質劣化特定装置１００から構成され、フロー品質劣化特定装置１００がノード１０からフロー情報を収集する。
【００１９】
図２は、本発明の第１の実施の形態におけるフロー品質劣化特定装置の構成を示す。
【００２０】
同図に示すフロー劣化特定装置１００は、ネットワーク上のフロー情報を収集するフロー受信部１１０と、受信したフロー情報を基にフローレートを計算するフローレート計算部１２０と、フローレートを基にエリア間フローレートを算出するエリア間フローレート管理部１３０と、エリア間フローレートを基にエリア間のフロー品質の劣化を検出するフロー品質劣化検出部１４０と、エリア間フローレートと品質が劣化したエリア間フローレートの情報を基にエリア間フロー品質の劣化が同期するエリアを抽出するレート低下ペア抽出部１５０からなる。
【００２１】
図３は、本発明の第１の実施の形態における動作のフローチャートである。
【００２２】
上記の構成のフロー品質劣化特定装置１００では、一定周期t0毎に以下のステップを繰り返す。
【００２３】
ステップ１０１）  フロー受信部１１０は、IPネットワーク内のノード（群）において、フローi毎に転送バイト数B_iと持続時間T_iを測定した値をフロー情報として受信し、フローレート計算部１２０に出力する。
【００２４】
ステップ１０２）  フロレート計算部１２０は、受信したフロー情報を基に、フローレートR_iをR_i=B_i/T_iとして計算し、エリア間レート管理部１３０に出力する。
【００２５】
ステップ１０３）  エリア間フローレート管理部１３０は、フロー情報から、フローiの発信元エリアおよび着信先エリアを特定し、エリアA_iからA_jへ向かうフローのエリア間フローレートF(A_i,A_j)を算出し、フロー品質劣化検出部１４０とレート低下ペア抽出部１５０に出力する。
【００２６】
ステップ１０４）  フロー品質劣化検出部１４０は、各F(A_i,A_j)を基にすべてのエリアに対して、F(A_i,A_j)の時系列データを作成し、ある閾値を基準として当該エリア間フローレートの品質を判定し、エリア間フローレートの品質低下が同期して発生している全エリアを抽出してレート低下ペア抽出部１５０に出力する。
【００２７】
ステップ１０５）  レート低下ペア抽出部１５０は、エリア間フローレート管理部１３０とフロー品質劣化検出部１４０から受信した情報（エリア間フローレート、品質低下が同期して発生している全エリア）を基に、エリア間共通の経路上のボトルネックを特定する。
【００２８】
以下に詳細に説明する。
【００２９】
フロー情報受信部１１０は、IPネットワーク１０１内のノード（群）１０からフローを取得する。フローレート計算部１２０において、フローi毎に転送バイト数B_iと持続時間T_iを測定し、フローレートR_iをR_i=B_i/T_iとして計算する。一方、エリア間フローレート管理部１３０は、パケットの発信元IPアドレス等の情報から、フローiの発信元エリアおよび着信先エリアを特定し、エリアA_iからA_jへ向かうフローを調べ、それらエリア間フローレートF(A_i,A_j)（例えば、フローのレートの平均=ΣR_i/Nf(Nfは該当するエリア間フロー数)により算出する。これを一定周期t0毎に実施し、メモリ（図示せず）に格納する。フロー品質劣化検出部１４０は、F(A_i,A_j)の時系列データを作成し、メモリ（図示せず）に格納し、このエリア間フローレートがある閾値を下回ったら該エリア間で品質が劣化しているとしてメモリ（図示せず）に格納する。
【００３０】
上記の処理を各エリア間について実施し、品質劣化フロー抽出部１５０は、メモリ（図示せず）からエリア間フローレート及び閾値を下回ったエリアを読み出して、エリア間フローレート低下が同期している他のエリア間を抽出する。その後、レート低下が同期しているとして抽出された複数のエリア間について、それらエリア間に共通の経路上にボトルネックがあるとして特定する。
【００３１】
なお、本実施の形態では、TCP(Transmission Control Protocol)フローを対象とする。上記のように定義されたフローレートはTCPでのファイル転送速度を意味する。したがって、フローレートの低下はTCPの品質劣化を意味することとなる。また、TCPでは、ネットワークやサーバが輻輳すると、自律的に送信レートを減少させるため、レートの低下は、通信経路上のどこかで輻輳が発生していることを意味する。そのレートの低下が同期するということは、エリア間の共有の経路上にボトルネックがある可能性を意味することとなる。
【００３２】
なお、フロー品質劣化検出部１４０で劣化判定を行うための閾値の具体例としては、本発明の第４の方法にて後述するように、過去のデータを元に自動的に設定する、あるいは、例えばこのエリア間でのフローレート（TCPスループット）として担保すべき値を、SLA(service level agreement)などでNW利用者との間で予め決めた値に設定しておく。例えばスループットとして3Mbpsは担保するのであれば閾値を3Mbpsとする。
【００３３】
なお、品質劣化フロー抽出部１５０におけるボトルネックの判断の具体的には、第５または６の実施の形態で後述するが、レートが低下しているエリア間のペアを抽出し、仮にエリア間Xとエリア間Yのレートが同期していると判定されたとすると、エリア間Xの経路（IPでの経路パス）とエリア間Yの経路をそれぞれ調べ、両者に共通の経路区間をボトルネック箇所と判断する。
【００３４】
図４に、あるインターネット回線上で測定されたフローレートの時系列を示す。ここでは、エリア＝ASとして、AS間毎のフローレートの平均を15分周期で集計した結果である。これより、時系列上の11:00〜13:00と、17:00〜17:30の２か所においてフローレートの低下が観測される。また、その低下が個々の時系列で同期していることが確認できる。実際に、これらのAS間に共通の経路上のリンク回線のリンク使用率をみると（図５）、上記の２つの時間帯において、使用率が非常に高くなっていることが確認できる。このように、フローレートの挙動をみることで、品質劣化特定が可能となる。
【００３５】
なお、ここでは、エリア＝ASとしたが、他、エリア＝地域（東京、大阪など）、エリア＝サーバ、というように、いろいろな定義に合わせて集計することが可能である。たとえば、エリア＝サーバとして集計した結果、フローレートの低下の同期が検出されたら、そのサーバがボトルネックになっている、として品質劣化を特定することも可能である。
【００３６】
［第２の実施の形態］
図６は、本発明の第２の実施の形態におけるフロー品質劣化特定装置の構成を示す。
【００３７】
同図に示すフロー品質劣化特定装置１００Ｂは、フロー情報受信部１１０、ユーザフロー管理テーブル２１０、フローレート計算部１２０、エリア間フローレート管理部１３０、フロー品質劣化検出部１４０、品質劣化フロー抽出部１６０から構成される。
【００３８】
図７は、本発明の第２の実施の形態における動作のフローチャートであり、図８は、本発明の第２の実施の形態におけるユーザフロー管理テーブルの例を示す。
【００３９】
ステップ２０１）  フロー受信部１１０は、測定開始から予め定めた時間周期t0を経過するまでの期間において、IPネットワーク１０１内のノード（群）１０から受信するパケットに対し、N個の受信パケットから任意の1個のパケットを抽出し、抽出した該パケットヘッダの情報を基に該パケットが属するフロー(フローｉ)を検出する。
【００４０】
ステップ２０２）  検出された該フローｉについて、ユーザフロー管理テーブル２１０への登録の有無を確認する。当該フローｉの登録がない場合はステップ２０３に移行する。登録されている場合にはステップ２０４に移行する。
【００４１】
ステップ２０３）  フローｉの登録がない場合は、該フローｉについて、該パケットが最初に到着した時刻(T_first_i)と最後に到着した時刻(T_last_i)を現在の時刻とし、最後に到着したパケットのシーケンス番号(SN_last_i)を該パケットヘッダから読み出したシーケンス番号とし、最初に到着したパケットのシーケンス番号(SN_first_i)を{該シーケンス番号 - 該パケットサイズ}として設定し、ユーザフロー管理テーブル２１０に該フローｉを登録する。
【００４２】
ステップ２０４）  当該フローｉが登録されている場合は、該フローiについて、最後に到着した時刻を現在の時刻とし、最後に到着したパケットのシーケンス番号を該パケットヘッダから読み出したシーケンス番号として、ユーザフロー管理テーブル２１０における該フローｉの登録情報を更新する。
【００４３】
ステップ２０５）  所定の周期の時間ｔ０を経過するまで上記の処理を繰り返す。
【００４４】
ステップ２０６）  フローレート計算部１２０は、時間周期t0経過時点において、当該フローｉの該パケットが最初に到着した時刻と最後に到着した時刻が同一であるかを判定し、
同一であればステップ２０７に移行し、該フローｉの該パケットが最初に到着した時刻よ
り最後に到着した時刻が後であれば、ステップ２０８に移行する。
【００４５】
ステップ２０７）  当該フローｉをユーザフロー管理テーブル２１０から削除して、ステップ２０９に移行する。
【００４６】
ステップ２０８）  当該フローｉのフローレートを、
フローレートR_i=(SN_last_i - SN_first_i)/(T_last_i - T_first_i)
の式で計算し、ユーザフロー管理テーブル２１０に登録された該フローｉのフローレートに設定する。
【００４７】
以降の処理は、第１の実施の形態と同様である。
【００４８】
以下に詳細に説明する。
【００４９】
本実施の形態では、フローレートR_iを求める方法として、第１の実施の形態のように転送バイト数B_iを直接測る代わりに、フロー情報受信部１１０において、IPネットワーク１０１内のノード（群）１０からのN個の到着パケットに対し1個のパケットを抽出し、該パケットヘッダを読み込んでそのパケットがどのフローに属するかを調べ、該フローが、図８に示すような予め用意したユーザフロー管理テーブル２１０にエントリされているかを調べる。ユーザフロー管理テーブル２１０では、フロー毎に、
・フローiからのパケットが最初に到着した時刻T_first_i，
・パケットが最後に到着した時刻T_last_i，
・最初に到着したパケットのシーケンス番号SN_first_i，
・最後に到着したパケットのシーケンス番号SN_last_i
を記憶している。なお、当該ユーザフロー管理テーブル２１０は、当該装置内のメモリまたはハードディスク等の記憶媒体であるものとする。
【００５０】
受信したパケットが新規フローからのパケットであった場合はユーザフロー管理テーブル２１０にエントリされていないため、フロー情報受信部１１０は、ユーザフロー管理テーブル２１０にそのフローをエントリし、T_first_i（パケットが最初に到着した時刻），T_last_i（パケットが最後に到着した時刻）を現在の時刻に設定し、SN_last_iを該パケットヘッダから読み出したシーケンス番号に設定し、
SN_first_i←{該シーケンス番号 - 該パケットサイズ}
に設定する。
【００５１】
当該フローが既にエントリされているユーザフローiに該当する場合、該フローに対応するユーザフロー管理テーブル２１０のレコードにおいて、T_last_iを現在の時刻に更新し、SN_last_iを該パケットヘッダから読み出したシーケンス番号に更新する。
【００５２】
以上の手順を、測定を開始してから予め定めた時間周期t0経過するまで行い、時間周期t0経過時点において、もしT_last_i=T_first_iならばフローiは該ユーザフロー管理テーブル２１０のエントリから除外し、もしT_last_i>T_first_iならば、フローレート計算部１２０において、該ユーザフロー管理テーブル２１０にエントリされているフローiのフローレートR_iを
R_i=(SN_last_i  -  SN_first_i)/(T_last_i  -  T_first_i)
と計算する。
【００５３】
これは、パケットサンプリングにより得られた情報から個々のフローのフローレートを推定する手順である。なお、本手順は、発明者らの文献１「R. Kawahara, T. Mori, K. Ishibashi, N. Kamiyama, and H. Yoshino, ''Packet sampling TCP flow rate estimation and performance degradation detection method,'' IEICE Trans. Commun., Vol.E91-B, No.5, pp.1309-1319, May 2008.」において記載の通りである。
【００５４】
［第３の実施の形態］
第１の実施の形態におけるエリア間フローレート管理部１３０では、エリア間フローレートとして該エリア間のフローのレートの平均を用いていたが、本実施の形態では、上位Xパーセントタイルを用いる。
【００５５】
エリア間フローレート管理部１３０は、エリアA_iからA_jへ向かうフローのエリア間フローレートF(A_i,A_j)の算出にあたり、エリア間のフローのレートの平均を用いる方法もしくは、上位Xパーセンタイル(Xは任意に設定可能)に対応するエリア間のフローレートを選択する。
【００５６】
なお、エリア間フローのレートの平均は、
平均=ΣR_i/Nf (Nfは該当エリア間のフロー数)
とし、Xの値は、X=50パーセンタイル（つまり中央値）や、95パーセンタイル（レートの上側から5パーセントの値をみることで、当該Xパーセンタイルの値に該当するフローレートがエリア間フローレートとして選択されることになる。
【００５７】
これにより、スループットの高いエリア間で劣化が起きていないかをみるなどの任意の設定が可能である。
【００５８】
［第４の実施の形態］
本実施の形態では、フロー品質劣化検出部１４０の処理について説明する。
【００５９】
フロー品質劣化検出部１４０は、エリア間フローレートの時系列からレートの低下（品質劣化）を検出する方法として、t番目の測定周期におけるエリア間フローレートをF(A_i,A_j,t)とし、これを入力として平滑化フローレートS(A_i,A_j,t)を、次式により更新する。
【００６０】
S(A_i,A_j,t)←(1−α)S(A_i,A_j,t−1)+αF(A_i,A_j,t)
また、フローレートの分散V(A_i,A_j,t)を、次式により更新する。
【００６１】
V(A_i,A_j,t)←(1−β) V(A_i,A_j,t)+β{S(A_i,A_j,t)− F(A_i,A_j,t)}2
上記の平滑化フローレートS(A_i,A_j,t)とフローレートの分散V(A_i,A_j,t)から次式により閾値を算出する。
【００６２】
閾値←S(A_i,A_j,t-1)-γsqrt(V(A_i,A_j,t−1))
なお、γは品質劣化と判定する閾値を決めるパラメータであり、1以上の値に設定する。例えば、γ＝３と設定すれば、過去のフローレートのデータのうち、「平均−３標準偏差」と閾値とすることになり、これは正規分布を仮定した場合には、この閾値を下回ることは0.13％の確率でしか起きないまれな事象であり、これを超えたということは、品質の状態を過去に比べて変化して、低下していると判断することになる。
【００６３】
現在のフローレートF(A_i,A_j,t)が上記の閾値を下回った場合に、品質劣化として検出する。
【００６４】
なお、上記のα、βは予め定める平滑化パラメータであり、0から1の間の値に設定する。
【００６５】
以上を実施しておき、もし現在のフローレートF(A_i,A_j,t)が閾値
S(A_i,A_j,t−1)-γsqrt(V(A_i,A_j,t−1))
を下回ったら品質劣化として検出する。なお、α、β、γの決め方については、過去のある一定期間のフローデータを用いて、様々な（α、β、γ）のパラメータセットに対してフローレートの低下を検出し、一方で時系列を運用者が実際に目視により確認し、運用者の判断を正解としたときに、誤ってレート低下と判断される割合とレート低下を見逃す割合の両者を小さくできるパラメータセットを選定する。
【００６６】
なお、ここでは、時系列の平滑化レート（ベースライン）を計算する例として、上記のようなexponentially weighted moving average (EWMA)を用いた場合を示したが、他に、一般的なARIMAモデルや、Holt-winters法（文献２：「J. D. Brutlag, "Aberrant behavior detection in time series for network monitoring," 14th Systems administration conference (LISA2000), Dec. 2000.」）などを用いてもよい。
【００６７】
［第５の実施の形態］
本実施の形態では、フロー品質劣化検出部１４０においてフローレート低下が同期しているエリアを抽出する場合について説明する。
【００６８】
フロー品質劣化検出部１４０は、フローレート低下が同期しているエリア間を抽出する場合に、同期を検出するための測定期間長をNスロット（フローレートを計算する測定周期t0が１スロットに相当）、エリアペアiの時点nでのフローレートをy_n(i)とし、エリア間iにおいて、このNスロットの期間にフローレートの低下が検出されていた場合に、エリア間iとエリア間jのラグkにおける相互相関関数Rk(i,j)を次の式で計算する。
【００６９】
【数１】
0005528372.tif 000002
なお、μはエリア間ｉのフローレートの平均，Cは相互共分散関数を意味し、
k=−L, −(L-1), …, −1, 0, 1, …, (L−1), L（Lは調査するラグの範囲）
となる。
【００７０】
なお、L, th, Mは予め設定した値である。当該値の具体的な決め方の例は後述する。
【００７１】
レート低下ペア抽出部１５０は、R_k(i,j)に対して、R_k(i,j)＞th (thは予め定めた閾値)となった回数がM個以上であれば、ペア{i,j}はレートの低下が同期していると判定し、エリアのペアを抽出する。
【００７２】
［第６の実施の形態］
本実施の形態では、前述の第５の実施の形態のように、相互相関関数Rk(i,j)と閾値を比較してレート低下ペア{i,j}を抽出する代わりに、以下の手順でペアを抽出する。
【００７３】
フロー品質劣化検出部１４０が、フローレート低下が同期しているエリア間を抽出する場合に、予め定義した次の式によってペア{i,j}間の距離を算出する。但し、ペア{i,j}のR_k(i,j)をa(k)と記述するものとする。
【００７４】
D(R_k(i,j))=F(a(-L),a(-(L-1),…,a(-1),a(0),a(1),…, a(L-1),a(L))
そして、K-meansなどのクラスタリング手法を用いて、当該ペア{i,j}間の距離をクラスタリングする。クラスタリングの結果、ペア{i,j}が同じクラスタに分類された場合、レート低下ペア抽出部１５０で当該ペア{i,j}を、レート低下同期ペアとして抽出する方法をとることができる。
【００７５】
なお、距離の関数Fの例として、F=Σw(i)a(i)（w(i)は予め定める重み係数）を用いることが可能である。
【００７６】
上記の図２、図６に示すフロー品質劣化特性装置の各構成要素の動作をプログラムとして構築し、フロー品質劣化特定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００７８】
１０  ルータ
１００  フロー品質劣化特定装置
１０１  ＩＰネットワーク
１１０  フロー情報受信部
１２０  フローレート計算部
１３０  エリア間フローレート管理部
１４０  フロー品質劣化検出部
１５０  レート低下ペア抽出部
１６０  品質劣化フロー抽出部
２１０  ユーザフロー管理テーブル
【図１】
0005528372.tif 000003
【図２】
0005528372.tif 000004
【図３】
0005528372.tif 000005
【図４】
0005528372.tif 000006
【図５】
0005528372.tif 000007
【図６】
0005528372.tif 000008
【図７】
0005528372.tif 000009
【図８】
0005528372.tif 000010