異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システム
【課題】異常箇所を推定するためのメモリ量や演算負荷を抑制するための異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システムを提供する。
【解決手段】ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定装置。
【解決手段】ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システムに関する。
【背景技術】
【０００２】
近年、音声データや動画データのストリーミングなど、マルチメディアデータをリアルタイムに提供するサービスの増加に伴い、ネットワーク上で大量のデータが高速で通信されるようになってきている。また、リアルタイムの通信のために、ＲＴＰ（Ｒｅａｌ Ｔｉｍｅ Ｐｒｏｔｔｏｃｏｌ）やＲＴＣＰ（ＲＴＰ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ）のような通信プロトコルが使用されている。
【０００３】
しかし、上記のＲＴＰは、パケットロス対策や伝送時間保証などの行われないＵＤＰタイプのプロトコルである。このため、ＲＴＰは、少ない遅延でリアルタイムにデータを送信することに向いている反面、通信路上の障害の影響を受け、音声が途切れる、画像が乱れるなど、ユーザに対するサービス品質が低下しやすいという問題がある。
【０００４】
したがって、ＩＰネットワークにおいて動画像のストリーミングやテレビ会議のような品質が重視されるサービスを実施する上で、ユーザに対して提供する通信サービスの品質を管理し、品質劣化などの異常に対して異常箇所の特定と対策を行うことが重要になってきている。
【０００５】
この点に関し、ある事業者が管理している内部ネットワーク内のユーザと外部ネットワークに存在するサーバや端末との間のデータ通信において異常が検出され、異常の原因が外部ネットワークにある場合、外部ネットワークの情報無しには、ネットワークのどの位置で異常が起きたのか調べられないので、原因を推測し保全することが難しいという問題がある。
【０００６】
このように、内部ネットワークを含む複数のローカルネットワークに渡る通信が行われるとユーザに対する品質の保証が難しくなるので、異常を検出し、異常発生箇所を特定する仕組みが必要である。
【０００７】
そこで、ネットワーク上に観測点を設け、観測点を流れるトラフィックを観測することにより通信品質が劣化した異常フローを検出し、ネットワークのトポロジ情報やルーティング情報などを用いてネットワークの異常発生箇所を検出する方法が提案されている。
【０００８】
例えば、特許文献１および非特許文献１には、事前にネットワークのトポロジ情報を収集し、観測点で異常フローが検出された場合、異常フローおよび正常フローの情報に基づいて異常フローが経由するリンクを異常フローごとに整理した品質フロー／経由リンクテーブル（以下、フロー・リンク対応表）を生成し、最小リンク数推定方式と呼ばれる手法により異常リンクを推定する技術が開示されている。なお、本明細書では、ある端末間におけるネットワーク上のデータの流れを１つのフローとして扱う。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−２３８９５２号公報
【非特許文献】
【００１０】
【非特許文献１】小林正好他、「フロー品質情報からのネットワーク品質劣化箇所推定方式」、電子情報通信学会技術報告書、ＴＭ−２００４−１０７
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、特許文献１および非特許文献１に記載の最小リンク数推定方式は、集合被覆問題（ｓｅｔ ｃｏｎｖｅｒ問題）を解くことと等価である。このため、ネットワークの規模が大きくなると（リンク数および異常フロー数が多くなると）、サイズの大きなフロー・リンク対応表を生成して処理するので、計算時間が長くなるという問題がある。
【００１２】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、異常箇所を推定するためのメモリ量や演算負荷を抑制することが可能な、新規かつ改良された異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システムを提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある観点によれば、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定装置が提供される。
【００１４】
前記候補リンク収集部は、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクが１つでない場合、前記観測点に接続するリンクのうちで異常フローの通るリンクから到達可能な候補リンクを収集してもよい。
【００１５】
前記ネットワーク上には複数の観測ノードが複数の観測点に配置されており、前記フロー情報収集部は、前記複数の観測ノードから前記フロー情報を収集し、前記計数部、前記候補リンク収集部、および前記異常リンク推定部は、前記複数の観測点の各々に接続するリンクに関して処理を行ってもよい。
【００１６】
前記計数部は、前記異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、当該端末側のリンクの異常フロー重複度から、当該端末から出ている異常フローの重複度を減算してもよい。
【００１７】
前記ネットワークは、１の観測点から他の観測点を経由せずに到達可能な端末までのリンクを含む内部ネットワーク、および、前記１の観測点から前記他の観測点までのリンクを含む外部ネットワークからなり、前記ネットワークには、前記外部ネットワークを経由する外部フロー、および前記内部ネットワーク内で前記外部ネットワークを経由しない内部フローが流れ、前記計数部は、内部フローのうちで異常のある内部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記１の観測点に接続する当該端末側のリンクの内部異常フローの重複度から、当該端末から出ている内部異常フローの数を減算してもよい。
【００１８】
前記計数部は、外部フローのうちで異常のある外部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記正常フローが経由するリンクのうちで、
前記１の観測点に接続する前記外部異常フローの他側の端末側のリンク以外のリンクの異常フロー重複度から、共通する端末から出ている外部異常フローの数を減算してもよい。
【００１９】
前記計数部は、前記１の観測点および前記他の観測点を経由する外部正常フローが観測されている場合、前記１の観測点に接続する前記他の観測点側のリンクの異常フロー重複度から、前記１の観測点および前記他の観測点を経由する異常フローの数を減算してもよい。
【００２０】
前記異常リンク推定部は、前記候補リンク収集部により収集された前記候補リンク、および前記候補リンクを通過する異常フローおよび正常フローの対応表を作成し、前記対応表から、正常フローの通過する候補リンクを削除し、残った候補リンクの各々を通る異常フローの数に基づいて前記異常リンクを推定してもよい。
【００２１】
前記異常リンク推定部は、対応表に異常フローの通過数が最大の候補リンクが存在し、かつ、当該候補リンクの異常フローの通過数が、前記複数の観測点に接続する全リンクの異常フロー重複度のうちで２番目に大きな値以上である場合、当該候補リンクを前記異常リンクとして推定してもよい。
【００２２】
前記観測ノードは、前記ネットワークのゲートウェイ部分の観測点に配置されてもよい。
【００２３】
前記異常リンク推定装置は、２以上の観測点を通過する異常フローを収集する異常フロー収集部と、前記２以上の観測点の各々を通過する異常フローの総数を比較する異常フロー数比較部と、をさらに備え、候補リンク収集部は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外してもよい。
【００２４】
前記計数部は、前記観測点に接続する同一のリンクを通過する複数の異常フローは重複して計数しなくてもよい。
【００２５】
また、上記課題を解決するために、本発明の別の観点によれば、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するステップと、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数するステップと、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定するステップと、異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集するステップと、前記候補リンクから異常の発生している異常リンクを推定するステップと、を含む異常リンク推定方法が提供される。
【００２６】
また、上記課題を解決するために、本発明の別の観点によれば、コンピュータを、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、として機能させるためのプログラムが提供される。
【００２７】
また、上記課題を解決するために、本発明の別の観点によれば、ネットワーク上の観測点に配置された観測ノードと、前記観測ノードにおいて観測された端末間のフロー情報が提供される異常リンク推定装置と、からなる異常リンク推定システムであって、前記異常リンク推定装置は、前記観測ノードから前記ロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定システムが提供される。
【発明の効果】
【００２８】
以上説明したように本発明によれば、異常箇所を推定するためのメモリ量や演算負荷を抑制することが可能である。
【図面の簡単な説明】
【００２９】
【図１】本発明の第１の実施形態による異常リンク推定システムの構成を示した説明図である。
【図２】観測ノードの構成を示した機能ブロック図である。
【図３】ネットワークを流れる内部異常フローおよび外部異常フローの具体例を示した説明図である。
【図４】ネットワークを流れる内部正常フローおよび外部正常フローの具体例を示した説明図である。
【図５】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図６】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図７】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図８】本発明の第１の実施形態による異常リンク推定装置の構成を示した機能ブロック図である。
【図９】推定範囲絞り込み部の詳細な構成を示した説明図である。
【図１０】異常リンク推定装置の動作を示したフローチャートである。
【図１１】各リンクの内部異常フローの重複度を示した説明図である。
【図１２】各リンクの外部異常フローの重複度を示した説明図である。
【図１３】各リンクの内部異常フローの重複度の減算処理を示した説明図である。
【図１４】各リンクの外部異常フローの重複度の減算処理を示した説明図である。
【図１５】正常フローの観測点間リンクの外部異常フローの重複度の減算処理を示した説明図である。
【図１６】内部異常フローの重複度および外部異常フローの重複度の統合結果を示した説明図である。
【図１７】フロー・リンク対応表を示した説明図である。
【図１８】フロー・リンク対応表を示した説明図である。
【図１９】フロー・リンク対応表を示した説明図である。
【図２０】本発明の第２の実施形態による異常リンク推定システムの構成を示した説明図である。
【図２１】ネットワークを流れるフローの具体例を示した説明図である。
【図２２】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２３】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２４】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２５】本発明の第２の実施形態による異常リンク推定装置の構成を示した機能ブロック図である。
【図２６】推定範囲絞り込み部の詳細な構成を示した説明図である。
【図２７】異常リンク推定装置の動作を示したフローチャートである。
【図２８】各リンクの異常フローの重複度を示した説明図である。
【図２９】フロー・リンク対応表の具体例を示した説明図である。
【図３０】フロー・リンク対応表の具体例を示した説明図である。
【発明を実施するための形態】
【００３０】
以下に添付図面を参照しながら、本発明の実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００３１】
＜第１の実施形態＞
（異常リンク推定システムの構成）
図１は、本発明の第１の実施形態による異常リンク推定システム１の構成を示した説明図である。図１に示したように、本発明の第１の実施形態による異常リンク推定システム１は、端末Ｔ１〜Ｔ９、ルータ（あるいはスイッチ）Ｒ１〜Ｒ５、観測ノードＡ１〜Ａ３、および異常リンク推定装置１０を含む。端末Ｔ１〜Ｔ９、ルータＲ１〜Ｒ５、観測ノードＡ１〜Ａ３、および異常リンク推定装置１０は、リンクＬ１〜Ｌ１８により接続される。
【００３２】
なお、本明細書及び図面において、実質的に同一の機能構成を有する複数の構成要素を、同一のアルファベットの後に異なる符号を付して区別する場合もある。例えば、実質的に同一の機能構成を有する複数の構成を、必要に応じて観測ノードＡ１、Ａ２およびＡ３のように区別する。ただし、実質的に同一の機能構成を有する複数の構成要素の各々を特に区別する必要がない場合、同一アルファベットのみを付する。例えば、観測ノードＡ１、Ａ２およびＡ３を特に区別する必要が無い場合には、観測ノードＡと称する。
【００３３】
観測ノードＡは、ネットワーク上の観測点に配置されており、観測点を通過するトラフィックを観測し、観測により得られたフロー情報を異常リンク推定装置１０に送信する。この観測ノードＡは、ＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）やＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）のような小規模ネットワークのゲートウェイ部分に配置されてもよい。
【００３４】
ここで、ある観測ノードＡに着目した時に、当該観測ノードＡの観測点から他の観測点を経由せずに到達可能な端末までのリンクを内部ネットワークと称し、当該観測点から他の観測点までのリンク、および他の観測点を経由して到達可能な端末までのリンクを外部ネットワークと称する。本実施形態においては図１に示したように観測ノードＡ１の観測点に着目し、観測ノードＡ１の観測点から他の観測点を経由せずに到達可能な端末までのリンクＬ１〜Ｌ３、Ｌ１１〜Ｌ１５（およびルータＲ１〜Ｒ３）を内部ネットワークと称し、他のリンクを外部ネットワークと称する。
【００３５】
また、本実施形態においては、内部ネットワークのみを流れる端末間のデータフローを内部フローと称し、外部ネットワークを経由する端末間のデータフローを外部フローと称する。
【００３６】
異常リンク推定装置１０は、観測ノードＡ１〜Ａ３からフロー情報を収集し、収集したフロー情報に基づいてネットワーク上の異常リンクを推定する。詳細については後述するが、本実施形態による異常リンク推定装置１０は、推定範囲を絞り込んだ後に異常リンクを推定するので、異常リンクを推定するためのメモリ量や演算負荷を抑制することが可能である。
【００３７】
なお、図１においては異常リンク推定装置１０がルータＲ１に接続されている例を示しているが、異常リンク推定装置１０の配置位置はかかる例に限定されない。また、図１においては異常リンク推定装置１０を独立の構成として示しているが、異常リンク推定装置１０の機能は、観測ノードＡ、ルータＲ、または端末Ｔなどの他のノードに実装されてもよい。
【００３８】
（観測ノードの構成）
以上、図１を参照して本発明の第１の実施形態による異常リンク推定システム１の全体構成を説明した。続いて、図２〜図７を参照し、本発明の第１の実施形態による観測ノードＡの構成を説明する。
【００３９】
図２は、観測ノードＡの構成を示した機能ブロック図である。図２に示したように、観測ノードＡは、異常フロー検出部６２と、フロー情報記憶部６４と、フロー情報送信部６６と、を備える。
【００４０】
異常フロー検出部６２は、ネットワークを流れるフローを観測し、品質劣化した異常フローを検出する。例えば、異常フロー検出部６２は、フローのパケット損失率、送信遅延および遅延揺らぎなどの値を統計し、統計値が閾値を上回るか否かに応じて異常フローを検出してもよい。また、異常フロー検出部６２は、ＩＴＵ−Ｔ勧告のＧ．１０７に従ってＲ値と呼ばれる評価指標を用いて異常フローを検出してもよい。
【００４１】
フロー情報記憶部６４は、異常フロー検出部６２で任意の一定期間に観測された異常フローのフロー情報、および正常フローのフロー情報を記憶する。フロー情報は、端末などがネットワークを介してあるサービスを利用している時に通信する一連のトラフィックを識別することができればよい。例えば、フロー情報は、フロータイプ（異常フローｏｒ正常フロー）、送信元アドレス、送信先アドレス、プロトコルタイプ、送信元ポート番号、宛先ポート番号を含んでもよいし、さらに、入力インタフェースとサービスタイプを含んでもよい。
【００４２】
フロー情報送信部６６は、フロー情報記憶部６４に記憶されたフロー情報を異常リンク推定装置１０に送信する。なお、フロー情報送信部６６は、ネットワークを介してフロー情報を送信してもよいし、専用回線を介してフロー情報を送信してもよい。
【００４３】
ここで、図３〜図７を参照し、各観測ノードＡ１〜Ａ３から異常リンク推定装置１０に送信されるフロー情報の具体例を説明する。
【００４４】
図３は、ネットワークを流れる内部異常フローおよび外部異常フローの具体例を示した説明図である。図４は、ネットワークを流れる内部正常フローおよび外部正常フローの具体例を示した説明図である。図３および図４に示したように、ネットワークを内部異常フローＦ１およびＦ２、外部異常フローＦ４、Ｆ５およびＦ９、内部正常フローＦ３およびＦ６、外部正常フローＦ７およびＦ８が流れている場合、観測ノードＡ１〜Ａ３は、図５〜図７に示すフロー情報を異常リンク推定装置１０に送信する。
【００４５】
図５は、観測ノードＡ１が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図５に示したように、観測ノードＡ１は、観測点を通過するフローＦ１〜Ｆ９を観測し、フローＦ１〜Ｆ９の情報を異常リンク推定装置１０に送信する。なお、フロータイプ「１」は異常フローを示し、「０」は正常フローを示す。また、図５〜図７においては便宜上ＩＰアドレスとして端末の識別番号を示しているが、実際には、「１９２．１６８．０．８」のようなアドレスが記載される。また、各行がどのフローを表わすかを分かり易くするためにフロー番号の項目を設けているが、この項目は設けなくてもよい。
【００４６】
図６は、観測ノードＡ２が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図６に示したように、観測ノードＡ２は、観測点を通過するフローＦ４、Ｆ５およびＦ８を観測し、フローＦ４、Ｆ５およびＦ８の情報を異常リンク推定装置１０に送信する。
【００４７】
図７は、観測ノードＡ３が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図７に示したように、観測ノードＡ３は、観測点を通過するフローＦ７およびＦ９を観測し、フローＦ７およびＦ９の情報を異常リンク推定装置１０に送信する。
【００４８】
（異常リンク推定装置の構成）
以上、図２〜図７を参照して観測ノードの構成を説明した。続いて、図８および図９を参照し、本発明の第１の実施形態による異常リンク推定装置１０の構成を説明する。
【００４９】
図８は、本発明の第１の実施形態による異常リンク推定装置１０の構成を示した機能ブロック図である。図８に示したように、異常リンク推定装置１０は、フロー情報収集部１１０と、フロー情報記憶部１２０と、トポロジ／ルーティング情報収集部１３０と、トポロジ／ルーティング情報記憶部１４０と、絞り込み規則蓄積部１５０と、推定範囲絞り込み部１６０と、絞り込み情報記憶部１７０と、異常リンク推定部１８０と、出力部１９０と、を備える。
【００５０】
フロー情報収集部１１０は、各観測ノードＡ１〜Ａ３から送信されるフロー情報を収集する。
【００５１】
フロー情報記憶部１２０は、フロー情報収集部１１０により収集されたフロー情報を、送信元の観測ノードが区別できるような形態で一時的に記憶する。
【００５２】
トポロジ／ルーティング情報収集部１３０は、ネットワークからルーティングに関する情報やトポロジ情報を収集する。例えば、トポロジ／ルーティング情報収集部１３０は、ネットワークを流れるＢＧＰのようのルーティングプロトコルのパケットを収集してもよいし、ルータＲからＳＮＭＰ（Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ）などにより情報を収集してもよい。
【００５３】
トポロジ／ルーティング情報記憶部１４０は、トポロジ／ルーティング情報収集部１３０により収集されたルーティングに関する情報やトポロジ情報を一時的に記憶する。このトポロジ／ルーティング情報記憶部１４０は、送受信ＩＰアドレスから、２点間の通信時に経由するリンクや、あるルータに接続されているリンクからルーティングによって到達可能なリンクを検索する機能を有してもよい。
【００５４】
絞り込み規則蓄積部１５０は、推定範囲絞り込み部１６０による絞り込みのための規則を蓄積する。
【００５５】
推定範囲絞り込み部１６０は、フロー情報記憶部１２０に記憶されたフロー情報、およびトポロジ／ルーティング情報記憶部１４０に記憶された情報を参照し、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込む。この推定範囲絞り込み部１６０の詳細な構成は図９を参照して後述する。
【００５６】
絞り込み情報記憶部１７０は、推定範囲絞り込み部１６０により絞り込まれた候補リンクを記憶する。
【００５７】
異常リンク推定部１８０は、絞り込み情報記憶部１７０に記憶されている候補リンクと、フロー情報記憶部１２０に記憶されているフロー情報を用いて異常リンクを推定する。例えば、異常リンク推定部１８０は、絞り込み情報記憶部１７０に記憶されている候補リンクに限定して非特許文献１に記載のフロー・リンク対応表を生成し、フロー・リンク対応表から最小リンク数推定方式によって異常リンクを推定してもよい。
【００５８】
出力部１９０は、異常リンク推定部１８０により推定されたネットワーク上の異常リンクを出力する。
【００５９】
（推定範囲絞り込み部の構成）
ここで、図９を参照し、推定範囲絞り込み部１６０の詳細な構成を説明する。図９は、推定範囲絞り込み部１６０の詳細な構成を示した説明図である。図９に示したように、推定範囲絞り込み部１６０は、重複度計数部１６２、重複度最大リンク判定部１６６、および候補リンク収集部１６８を含む。また、重複度計数部１６２は、異常フロー重複度計数部１６３、正常リンク重複度減算部１６４、および観測点間リンク重複度減算部１６５を含む。これら推定範囲絞り込み部１６０の構成および異常リンク推定部１８０は、図１０に示すステップ１〜ステップ６を実行することにより異常リンクを推定する。
【００６０】
（ステップ１）
異常フロー重複度計数部１６３は、観測点に接続する各リンクを通過する内部異常フローの数（重複度）、および観測点に接続する各リンクを通過する外部異常フローの数（重複度）を計数する。
【００６１】
（ステップ２）
正常リンク重複度減算部１６４は、以下の２種類のいずれかの正常フローが存在する場合、ステップ１で得られた内部異常フローの重複度、および外部異常フローの重複度の減算を行う。
・異常フローと共通する端末から出ている内部正常フローが存在する場合
正常リンク重複度減算部１６４は、ステップ１で得られた共通の端末側のリンクの異常フロー重複度から、共通の端末から出ている異常フローの数を減算する。
・異常フローと共通する端末から出ている外部正常フローが存在する場合
正常リンク重複度減算部１６４は、異常フローの他方の端末の存在する内部ネットワーク側のリンク以外であって、外部正常フローが経由する全ての観測点における外部正常フローが経由するリンクのステップ１で得られた異常フロー重複度から、共通の端末から出ている異常フローの数を減算する。
【００６２】
（ステップ３）
外部異常フローと同一の観測点間を通過する外部正常フローが存在する場合、観測点間リンク重複度減算部１６５は、観測点間のリンクの重複度から、当該観測点間を経由する外部異常フローの数を減算する。
【００６３】
（ステップ４）
重複度計数部１６２は、ステップ２およびステップ３の減算が行われた内部異常フローの重複度、および外部異常フローの重複度を統合（合計）する。
【００６４】
（ステップ５）
重複度最大リンク判定部１６６は、各リンクの統合された異常フロー重複度のうちで、異常フロー重複度が最大であるリンクを判定する。候補リンク収集部１６８は、異常フロー重複度が最大であると判定されたリンクを経由する異常フローが通過する端末側の候補リンクを収集する。異常リンク推定部１８０は、候補リンク収集部１６８により収集された候補リンクからなるフロー・リンク対応表を生成し、２番目に大きな異常フロー重複度以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在する場合、当該候補リンクを異常リンクと推定する。その後、重複度計数部１６２は、フロー・リンク対応表から異常リンクとして推定した候補リンクを通る異常フローを削除し、重複度最大リンク判定部１６６により判定されたリンクの異常フロー重複度から異常フローの削除数を減算する。また、異常リンクとして推定した候補リンクを通る異常フローが経由するもう一方の観測点へ繋がるリンクの異常フロー重複度から、異常フローの通過数を減算する。
【００６５】
一方、２番目に大きな異常フロー重複度以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在しない場合、重複度計数部１６２は、このフロー・リンク対応表で最も多く異常フローが通るリンクの異常フロー通過数を重複度最大リンク判定部１６６により判定されたリンクの異常フロー重複度から減算する。
【００６６】
（ステップ６）
ステップ５の処理を、観測点に接続する全リンクの異常フロー重複度が０になるまで繰り返す。
【００６７】
（異常リンク推定装置の具体的な処理）
以上、図９および図１０を参照して異常リンクの推定方法の概要を説明した。続いて、図１１〜図１９を参照し、本実施形態による異常リンク推定装置１０の具体的な処理を説明する。なお、以下では、ネットワーク上を図３および図４に示したフローが流れている場合の異常リンク推定装置１０の処理を説明する。
【００６８】
まず、ステップ１として、異常フロー重複度計数部１６３は、フロー情報記憶部１２０に記憶されているフロー情報に基づき、観測点Ａ１に接続するリンクの内部異常フローの重複度を図１１に示すように計数する。例えば、リンクＬ３を通過する内部異常フローは図３に示したように内部異常フローＦ１およびＦ２の２つであるので、リンクＬ３の内部異常フローの重複度は図１１に示したように「２」と計数される。
【００６９】
同様に、異常フロー重複度計数部１６３は、フロー情報記憶部１２０に記憶されているフロー情報に基づき、観測点Ａ１に接続するリンクの外部異常フローの重複度を図１２に示すように計数する。例えば、リンクＬ４を通過する外部異常フローは図３に示したようにＦ９の１つであるので、リンクＬ４の外部異常フローの重複度は図１２に示したように「１」と計数される。
【００７０】
次に、正常リンク重複度減算部１６４は、ステップ２として、図４に示したように内部異常フローＦ２と共通の端末Ｔ３から出ている内部正常フローが存在する場合、共通の端末Ｔ３側のリンクＬ２の重複度「１」から異常フローの通過数である「１」を減算する。これにより、内部異常フローのリンクＬ２の重複度は図１３に示したように「０」となる。
【００７１】
また、正常リンク重複度減算部１６４は、図４に示したように外部異常フローＦ４と共通の端末Ｔ３から出ている外部正常フローＦ７が存在する場合、外部異常フローＦ４の他側の端末Ｔ９側のリンクＬ５を除くリンクＬ２の重複度「１」から、異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ２の重複度は図１４に示したように「０」となる。
【００７２】
同様に、外部正常フローＦ７は、外部異常フローＦ９と共通の端末Ｔ６から出ているので、正常リンク重複度減算部１６４は、外部異常フローＦ９の他側の端末Ｔ５側のリンクＬ３を除くリンクＬ４、Ｌ６およびＬ８の重複度「１」から、異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ４、Ｌ６およびＬ８の重複度は図１４に示したように「０」となる。
【００７３】
さらに、正常リンク重複度減算部１６４は、図４に示したように、外部異常フローＦ５と共通の端末Ｔ２から出ている内部正常フローＦ６が存在する場合、共通の端末Ｔ２側のリンクＬ１の重複度「１」から異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ１の重複度は図１４に示したように「０」となる。
【００７４】
続いて、観測点間リンク重複度減算部１６５は、ステップ３として、図４に示したように観測点Ａ１およびＡ２を経由する外部正常フローが観測されている場合、観測点Ａ１およびＡ２間のリンクＬ５およびＬ７の外部異常フローの重複度「２」から、同一の観測点Ａ１およびＡ２を経由する外部異常フロー数である「２」（Ｆ４およびＦ５の２つ）を減算する。これにより、外部異常フローのリンクＬ５およびＬ７の重複度は図１５に示したように「０」になる。
【００７５】
次に、重複度計数部１６２は、ステップ４として、図１３に示した各リンクの内部異常フローの重複度、および図１５に示した外部異常フローの重複度を統合（合計）する。これにより、図１６に示す統合結果が得られる。
【００７６】
その後、ステップ５へ移行する。すなわち、重複度最大リンク判定部１６６は、図１６に示したようにリンクＬ３が最大の重複度「３」を有するので、リンクＬ３を重複度が最大のリンクとして判定する。そして、候補リンク収集部１６８は、リンクＬ３を異常フローＦ１、Ｆ２およびＦ９が経由するので、これらのフローがＬ３を経由する端末までのリンクを候補リンクとして収集する。
【００７７】
さらに、異常リンク推定部１８０は、図１７に示したように、候補リンク収集部１６８により収集された候補リンクからなるフロー・リンク対応表を生成する。そして、異常リンク推定部１８０は、２番目に大きなＬ９の重複度「２」以上の数の異常フローの通る候補リンクＬ１５がフロー・リンク対応表に存在するので、Ｌ１５を異常リンクとして推定する。その後、重複度計数部１６２は、リンクＬ３の重複度を「３」から「０」とする。一方、異常フローＦ１、Ｆ２およびＦ９が通る他のリンクＬ１、Ｌ２、Ｌ４、Ｌ６およびＬ８の重複度は既にステップ２およびステップ３で「０」に減算されているので、ここでの重複度の減算は行われない。
【００７８】
仮に、図１８に示すフロー・リンク対応表が生成された場合、２番目に大きなＬ９の重複度「２」以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在しない。この場合、重複度計数部１６２は、フロー・リンク対応表で最も多く異常フローの通るリンクの異常フロー通過数「１」にリンクＬ３の重複度を更新する。
【００７９】
ここまでで１順目のステップ５が終了し、２順目のステップ５で、残りの全リンクから最も重複度の大きいリンクＬ９が選択され、同様の処理により、図１９に示したフロー・リンク表が生成され、リンクＬ１８が異常リンクとして推定され、Ｌ９の重複度が「０」に更新される。これにより、全ての観測点に接続するリンクの異常フロー重複度が「０」となる。
【００８０】
以上説明したように、本発明の第１の実施形態によれば、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することができる。したがって、本発明の第１の実施形態によれば、異常リンクを推定するためのメモリ量や演算負荷を抑制することが可能である。
【００８１】
＜２．第２の実施形態＞
続いて、本発明の第２の実施形態を説明する。
【００８２】
（異常リンク推定システムの構成）
図２０は、本発明の第２の実施形態による異常リンク推定システム２の構成を示した説明図である。図２０に示したように、本発明の第２の実施形態による異常リンク推定システム２は、端末Ｔ１〜Ｔ２２、ルータ（あるいはスイッチ）Ｒ１〜Ｒ１６、観測ノードＡ１〜Ａ３、および異常リンク推定装置２０を含む。端末Ｔ１〜Ｔ２２、ルータＲ１〜Ｒ１６、観測ノードＡ１〜Ａ３、および異常リンク推定装置２０は、リンクＬ１〜Ｌ４２により接続される。
【００８３】
観測ノードＡは、ネットワーク上の観測点に配置されており、観測点を通過するトラフィックを観測し、観測により得られたフロー情報を異常リンク推定装置２０に送信する。図２０に示したように、観測ノードＡ１、Ａ２およびＡ３は、例えばルータＲ３、Ｒ１０、Ｒ６の設置部分に配置される。この観測ノードＡの構成は第１の実施形態で説明した通りであるので、詳細な説明を省略する。
【００８４】
第２の実施形態による異常リンク推定装置２０は、観測ノードＡ１〜Ａ３からフロー情報を収集し、収集したフロー情報に基づいてネットワーク上の異常リンクを推定する。第２の実施形態による異常リンク推定装置２０は、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することが可能である。
【００８５】
ここで、図２１〜図２４を参照し、各観測ノードＡ１〜Ａ３から異常リンク推定装置２０に送信されるフロー情報の具体例を説明する。
【００８６】
図２１は、ネットワークを流れるフローの具体例を示した説明図である。図２１に示したように、ネットワークをフローＦ１〜Ｆ１１が流れる場合、観測ノードＡ１〜Ａ３は、図２２〜図２４に示すフロー情報を異常リンク推定装置２０に送信する。
【００８７】
図２２は、観測ノードＡ１が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２２に示したように、観測ノードＡ１は、観測点を通過するフローＦ３〜Ｆ６を観測し、フローＦ３〜Ｆ６の情報を異常リンク推定装置２０に送信する。
【００８８】
図２３は、観測ノードＡ２が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２３に示したように、観測ノードＡ２は、観測点を通過するフローＦ１、Ｆ１０およびＦ１１を観測し、フローＦ１、Ｆ１０およびＦ１１の情報を異常リンク推定装置２０に送信する。
【００８９】
図２４は、観測ノードＡ３が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２４に示したように、観測ノードＡ３は、観測点を通過するフローＦ２、Ｆ３およびＦ７〜Ｆ９を観測し、フローＦ２、Ｆ３およびＦ７〜Ｆ９の情報を異常リンク推定装置２０に送信する。
【００９０】
（異常リンク推定装置の構成）
図２５は、本発明の第２の実施形態による異常リンク推定装置２０の構成を示した機能ブロック図である。図２５に示したように、異常リンク推定装置２０は、フロー情報収集部２１０と、フロー情報記憶部２２０と、トポロジ／ルーティング情報収集部２３０と、トポロジ／ルーティング情報記憶部２４０と、絞り込み規則蓄積部２５０と、推定範囲絞り込み部２６０と、絞り込み情報記憶部２７０と、異常リンク推定部２８０と、出力部２９０と、を備える。
【００９１】
なお、フロー情報収集部２１０、フロー情報記憶部２２０、トポロジ／ルーティング情報収集部２３０、およびトポロジ／ルーティング情報記憶部２４０は、第１の実施形態によるフロー情報収集部１１０、フロー情報記憶部１２０、トポロジ／ルーティング情報収集部１３０、およびトポロジ／ルーティング情報記憶部１４０と実質的に同一であるので、詳細な説明を省略する。
【００９２】
絞り込み規則蓄積部２５０は、推定範囲絞り込み部２６０による絞り込みのための規則を蓄積する。
【００９３】
推定範囲絞り込み部２６０は、フロー情報記憶部２２０に記憶されたフロー情報、およびトポロジ／ルーティング情報記憶部４０に記憶された情報を参照し、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込む。この推定範囲絞り込み部２６０の詳細な構成は図２６を参照して後述する。
【００９４】
絞り込み情報記憶部２７０は、推定範囲絞り込み部２６０により絞り込まれた候補リンクを記憶する。
【００９５】
異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶されている候補リンクと、フロー情報記憶部２２０に記憶されているフロー情報を用いて異常リンクを推定する。例えば、異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶されている候補リンクに限定して非特許文献１に記載のフロー・リンク対応表を生成し、フロー・リンク対応表から最小リンク数推定方式によって異常リンクを推定してもよい。
【００９６】
出力部２９０は、異常リンク推定部２８０により推定されたネットワーク上の異常リンクを出力する。
【００９７】
（推定範囲絞り込み部の構成）
ここで、図２６を参照し、推定範囲絞り込み部２６０の詳細な構成を説明する。図２６は、推定範囲絞り込み部２６０の詳細な構成を示した説明図である。図２６に示したように、推定範囲絞り込み部２６０は、異常フロー重複度計数部２６２、重複度最大リンク判定部２６４、複数観測点通過異常フロー収集部２６６、異常フロー数比較部２６７および候補リンク収集部２６８を含む。このような推定範囲絞り込み部２６０および異常リンク推定部２８０は、図２７に示すＳ３１０〜Ｓ３６０を実行することにより異常リンクを推定する。
【００９８】
まず、異常フロー重複度計数部２６２が、各観測点に接続するリンクを経由する異常フローの数（重複度）を計数する（Ｓ３１０）。続いて、重複度最大リンク判定部２６４が、各観測点に接続するリンクのうちで、異常フローの重複度が最大であるリンクを判定する（Ｓ３２０）。
【００９９】
そして、候補リンク収集部２６８は、重複度最大リンク判定部２６４により判定される重複度が最大であるリンクが１つである場合、ルーティング情報を参照し、重複度最大リンク判定部２６４により判定されたリンクを経由して到達可能なリンクを候補リンクとして収集する（Ｓ３３０）。一方、候補リンク収集部２６８は、重複度最大リンク判定部２６４により判定される重複度が最大であるリンクが１つでない場合、異常フローの通るリンクから到達可能な端末または観測点までの全リンクを候補リンクとして収集する（Ｓ３３０）。候補リンク収集部２６８により収集された候補リンクは絞り込み情報記憶部２７０に記憶される。
【０１００】
その後、複数観測点間通過異常フロー収集部２６６が、フロー情報記憶部２２０に記憶されているフロー情報から、複数の観測点を通過する異常フローを収集する（Ｓ３４０）。
【０１０１】
続いて、異常フロー数比較部２６７が、Ｓ３４０において収集された異常フローが通過する２つの観測点において検出された異常フローの総数を比較し、候補リンク収集部２６８が、比較結果に応じて絞り込み情報記憶部２７０の候補リンクを追加または削除する（Ｓ３５０）。例えば、候補リンク収集部２６８は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外してもよい。
【０１０２】
そして、異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶された候補リンクからなるフロー・リンク対応表を生成し、このフロー・リンク対応表に対し最小リンク数推定方式を適用することにより異常リンクを推定する（Ｓ３６０）。
【０１０３】
（異常リンク推定装置の具体的な処理）
以上、図２６および図２７を参照して異常リンクの推定方法の概要を説明した。続いて、図２８〜図３０を参照し、本実施形態による異常リンク推定装置２０の具体的な処理を説明する。なお、以下では、ネットワーク上を図２１に示したフローが流れている場合の異常リンク推定装置２０の処理を説明する。
【０１０４】
まず、異常フロー重複度計数部２６２は、トポロジ／ルーティング情報記憶部２４０を参照し、観測ノードＡ１による観測点であるルータＲ３にリンクＬ３、Ｌ４、Ｌ１０、Ｌ１１、Ｌ１２およびＬ１３が接続されていることを認識する。そして、異常フロー重複度計数部２６２は、この観測点で観測された異常フローをフロー情報記憶部２２０から収集し、トポロジ／ルーティング情報記憶部２４０を参照して各異常フローが通るリンクを判定する。図２１に示した例では、異常フローＦ５がリンクＬ４およびＬ１３を通り、異常フローＦ６がリンクＬ１１およびＬ１３を通り、異常フローＦ２がリンクＬ３とＬ１２を通る。このため、異常フロー重複度計数部２６２は、図２８に示したように、リンクＬ３、Ｌ４、Ｌ１１およびＬ１２の重複度を「１」、リンクＬ１３の重複度を「２」と計数する（Ｓ３１０）。
【０１０５】
続いて、重複度最大リンク判定部２６４が、観測点であるルータＲ３に接続するリンクＬ３、Ｌ４、Ｌ１０、Ｌ１１、Ｌ１２およびＬ１３のうちで、異常フローの重複度が最大であるリンクがＬ１３であると判定する（Ｓ３２０）。
【０１０６】
このため、候補リンク収集部２６８は、ルータＲ３からルーティングによってリンクＬ１３を経由して到達可能な端末までの経路上の全リンク、すなわち、Ｌ７、Ｌ８およびＬ１３をトポロジ／ルーティング情報記憶部２４０から候補リンクとして収集する（Ｓ３３０）。
【０１０７】
同様に、観測ノードＡ２に関し、異常フロー重複度計数部２６２は、ルータＲ１０を経由する異常フローＦ１０およびＦ１１がリンクＬ２９およびＬ４２を通るので、図２８に示したようにリンクＬ２９およびＬ４２の重複度を「２」と計数する。よって、重複度最大リンク判定部２６４によりＬ２９およびＬ４２の双方が重複度の最大リンクとして判定されるので、候補リンク収集部２６８は、ルータＲ１０からリンクＬ２９またはＬ４２を経由してルーティングによって到達可能な端末または他の観測点までの全リンク、すなわち、リンクＬ２９〜Ｌ４２を候補リンクとして収集する。なお、異常フロー重複度計数部２６２は、同一ペアのリンクを通る異なる異常フローは重複して計数しなくてもよい。例えば、異常フローＦ１０およびＦ１１が通るリンクのペアはＬ２９とＬ４２で同一であるので、Ｌ２９およびＬ４２の重複度を「１」と計数してもよい。
【０１０８】
同様に、観測ノードＡ３に関し、異常フロー重複度計数部２６２は、ルータＲ６を経由する異常フローＦ２およびＦ３がリンクＬ１５およびＬ２７を通るので、図２８に示したようにリンクＬ１５およびＬ２７の重複度を「２」と計数する。よって、重複度最大リンク判定部２６４によりＬ１５およびＬ２７の双方が重複度の最大リンクとして判定されるので、候補リンク収集部２６８は、ルータＲ６からリンクＬ１５またはＬ２７を経由してルーティングによって到達可能な端末または他の観測点までの全リンク、すなわち、リンクＬ１５を経由して到達可能なリンクＬ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１２、およびＬ１４、リンクＬ２７を経由して到達可能なリンクＬ２３およびＬ２４を候補リンクとして収集する。
【０１０９】
続いて、複数観測点間通過異常フロー収集部２６６が、観測ノードＡ１による観測点Ｒ３および観測ノードＡ３による観測点Ｒ６を通過する異常フローＦ３を収集する（Ｓ３４０）。
【０１１０】
そして、異常フロー数比較部２６７が、Ｒ３において検出された異常フローの総数、およびＲ６において検出された異常フローの総数を比較する。ここで、Ｒ３において検出された異常フローの総数は「３」であり、Ｒ６において検出された異常フローの総数は「２」であるので、Ｒ６において検出された異常フローの総数の方が少ない。このため、候補リンク収集部２６８は、Ｒ６からＲ３への接続リンクＬ１５から到達可能な端末および他の観測点までのリンク、すなわち、Ｌ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１２、Ｌ１４およびＬ１５を候補リンクとして収集する。一方、候補リンク収集部２６８は、Ｌ１７およびＬ２７からルーティングにより到達可能な端末または他の観測点までのリンク、すなわち、既に収集されたリンクＬ２３、Ｌ２４およびＬ２７は、候補リンクから削除する（Ｓ３５０）。
【０１１１】
ここまでの処理により、絞り込み情報記憶部２７０には、候補リンクとしてリンクＬ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１３〜Ｌ１５、およびＬ２９〜Ｌ４２が記憶される。
【０１１２】
次に、異常リンク推定部２８０が、絞り込み情報記憶部２７０に記憶されている候補リンクを用い、図２９に示すフロー・リンク対応表を生成する。このフロー・リンク対応表において、列が各リンク、行が各異常フロー、各異常フローが通過するリンクを「１」、各異常フローが通過するリンクを「０」と示している。
【０１１３】
その後、異常リンク推定部２８０は、図２９に示したフロー・リンク対応表から、正常フローの通るリンク、およびどのフローも通らないリンクを削除し、図３０に示したフロー・リンク対応表を得る。異常リンク推定部２８０は、図３０に示したフロー・リンク対応表に対して最小リンク数推定方式を適用することにより、図３０で四角で囲って示したリンクＬ１３、Ｌ１５およびＬ４２を異常リンクとして推定することができる。
【０１１４】
以上説明したように、本発明の第２の実施形態によれば、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することができる。したがって、本発明の第２の実施形態によれば、異常リンクを推定するためのメモリ量、演算負荷およびコストなどを抑制することが可能である。
【０１１５】
＜３．補足＞
なお、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【０１１６】
例えば、本明細書の異常リンク推定装置１０または２０の処理における各ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はない。例えば、異常リンク推定装置１０または２０の処理における各ステップは、フローチャートとして記載した順序と異なる順序で処理されても、並列的に処理されてもよい。
【０１１７】
また、異常リンク推定装置１０または２０に内蔵されるＣＰＵ、ＲＯＭおよびＲＡＭなどのハードウェアを、上述した異常リンク推定装置１０または２０の各構成と同等の機能を発揮させるためのコンピュータプログラムも作成可能である。また、該コンピュータプログラムを記憶させた記憶媒体も提供される。
【符号の説明】
【０１１８】
１、２ 異常リンク推定システム
１０、２０ 異常リンク推定装置
６２ 異常フロー検出部
６４ フロー情報記憶部
６６ フロー情報送信部
１１０、２１０ フロー情報収集部
１２０、２２０ フロー情報記憶部
１３０、２３０ トポロジ／ルーティング情報収集部
１４０、２４０ トポロジ／ルーティング情報記憶部
１５０、２５０ 絞り込み規則蓄積部
１６０、２６０ 推定範囲絞り込み部
１６２ 重複度計数部
１６３、２６２ 異常フロー重複度計数部
１６４ 正常リンク重複度減算部
１６５ 観測点間リンク重複度減算部
１６６，２６４ 重複度最大リンク判定部
１６８、２６８ 候補リンク収集部
１７０、２７０ 絞り込み情報記憶部
１８０、２８０ 異常リンク推定部
１９０、２９０ 出力部
２６６ 複数観測点通過異常フロー収集部
２６７ 異常フロー数比較部
【技術分野】
【０００１】
本発明は、異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システムに関する。
【背景技術】
【０００２】
近年、音声データや動画データのストリーミングなど、マルチメディアデータをリアルタイムに提供するサービスの増加に伴い、ネットワーク上で大量のデータが高速で通信されるようになってきている。また、リアルタイムの通信のために、ＲＴＰ（Ｒｅａｌ Ｔｉｍｅ Ｐｒｏｔｔｏｃｏｌ）やＲＴＣＰ（ＲＴＰ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ）のような通信プロトコルが使用されている。
【０００３】
しかし、上記のＲＴＰは、パケットロス対策や伝送時間保証などの行われないＵＤＰタイプのプロトコルである。このため、ＲＴＰは、少ない遅延でリアルタイムにデータを送信することに向いている反面、通信路上の障害の影響を受け、音声が途切れる、画像が乱れるなど、ユーザに対するサービス品質が低下しやすいという問題がある。
【０００４】
したがって、ＩＰネットワークにおいて動画像のストリーミングやテレビ会議のような品質が重視されるサービスを実施する上で、ユーザに対して提供する通信サービスの品質を管理し、品質劣化などの異常に対して異常箇所の特定と対策を行うことが重要になってきている。
【０００５】
この点に関し、ある事業者が管理している内部ネットワーク内のユーザと外部ネットワークに存在するサーバや端末との間のデータ通信において異常が検出され、異常の原因が外部ネットワークにある場合、外部ネットワークの情報無しには、ネットワークのどの位置で異常が起きたのか調べられないので、原因を推測し保全することが難しいという問題がある。
【０００６】
このように、内部ネットワークを含む複数のローカルネットワークに渡る通信が行われるとユーザに対する品質の保証が難しくなるので、異常を検出し、異常発生箇所を特定する仕組みが必要である。
【０００７】
そこで、ネットワーク上に観測点を設け、観測点を流れるトラフィックを観測することにより通信品質が劣化した異常フローを検出し、ネットワークのトポロジ情報やルーティング情報などを用いてネットワークの異常発生箇所を検出する方法が提案されている。
【０００８】
例えば、特許文献１および非特許文献１には、事前にネットワークのトポロジ情報を収集し、観測点で異常フローが検出された場合、異常フローおよび正常フローの情報に基づいて異常フローが経由するリンクを異常フローごとに整理した品質フロー／経由リンクテーブル（以下、フロー・リンク対応表）を生成し、最小リンク数推定方式と呼ばれる手法により異常リンクを推定する技術が開示されている。なお、本明細書では、ある端末間におけるネットワーク上のデータの流れを１つのフローとして扱う。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−２３８９５２号公報
【非特許文献】
【００１０】
【非特許文献１】小林正好他、「フロー品質情報からのネットワーク品質劣化箇所推定方式」、電子情報通信学会技術報告書、ＴＭ−２００４−１０７
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、特許文献１および非特許文献１に記載の最小リンク数推定方式は、集合被覆問題（ｓｅｔ ｃｏｎｖｅｒ問題）を解くことと等価である。このため、ネットワークの規模が大きくなると（リンク数および異常フロー数が多くなると）、サイズの大きなフロー・リンク対応表を生成して処理するので、計算時間が長くなるという問題がある。
【００１２】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、異常箇所を推定するためのメモリ量や演算負荷を抑制することが可能な、新規かつ改良された異常リンク推定装置、異常リンク推定方法、プログラムおよび異常リンク推定システムを提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある観点によれば、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定装置が提供される。
【００１４】
前記候補リンク収集部は、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクが１つでない場合、前記観測点に接続するリンクのうちで異常フローの通るリンクから到達可能な候補リンクを収集してもよい。
【００１５】
前記ネットワーク上には複数の観測ノードが複数の観測点に配置されており、前記フロー情報収集部は、前記複数の観測ノードから前記フロー情報を収集し、前記計数部、前記候補リンク収集部、および前記異常リンク推定部は、前記複数の観測点の各々に接続するリンクに関して処理を行ってもよい。
【００１６】
前記計数部は、前記異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、当該端末側のリンクの異常フロー重複度から、当該端末から出ている異常フローの重複度を減算してもよい。
【００１７】
前記ネットワークは、１の観測点から他の観測点を経由せずに到達可能な端末までのリンクを含む内部ネットワーク、および、前記１の観測点から前記他の観測点までのリンクを含む外部ネットワークからなり、前記ネットワークには、前記外部ネットワークを経由する外部フロー、および前記内部ネットワーク内で前記外部ネットワークを経由しない内部フローが流れ、前記計数部は、内部フローのうちで異常のある内部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記１の観測点に接続する当該端末側のリンクの内部異常フローの重複度から、当該端末から出ている内部異常フローの数を減算してもよい。
【００１８】
前記計数部は、外部フローのうちで異常のある外部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記正常フローが経由するリンクのうちで、
前記１の観測点に接続する前記外部異常フローの他側の端末側のリンク以外のリンクの異常フロー重複度から、共通する端末から出ている外部異常フローの数を減算してもよい。
【００１９】
前記計数部は、前記１の観測点および前記他の観測点を経由する外部正常フローが観測されている場合、前記１の観測点に接続する前記他の観測点側のリンクの異常フロー重複度から、前記１の観測点および前記他の観測点を経由する異常フローの数を減算してもよい。
【００２０】
前記異常リンク推定部は、前記候補リンク収集部により収集された前記候補リンク、および前記候補リンクを通過する異常フローおよび正常フローの対応表を作成し、前記対応表から、正常フローの通過する候補リンクを削除し、残った候補リンクの各々を通る異常フローの数に基づいて前記異常リンクを推定してもよい。
【００２１】
前記異常リンク推定部は、対応表に異常フローの通過数が最大の候補リンクが存在し、かつ、当該候補リンクの異常フローの通過数が、前記複数の観測点に接続する全リンクの異常フロー重複度のうちで２番目に大きな値以上である場合、当該候補リンクを前記異常リンクとして推定してもよい。
【００２２】
前記観測ノードは、前記ネットワークのゲートウェイ部分の観測点に配置されてもよい。
【００２３】
前記異常リンク推定装置は、２以上の観測点を通過する異常フローを収集する異常フロー収集部と、前記２以上の観測点の各々を通過する異常フローの総数を比較する異常フロー数比較部と、をさらに備え、候補リンク収集部は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外してもよい。
【００２４】
前記計数部は、前記観測点に接続する同一のリンクを通過する複数の異常フローは重複して計数しなくてもよい。
【００２５】
また、上記課題を解決するために、本発明の別の観点によれば、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するステップと、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数するステップと、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定するステップと、異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集するステップと、前記候補リンクから異常の発生している異常リンクを推定するステップと、を含む異常リンク推定方法が提供される。
【００２６】
また、上記課題を解決するために、本発明の別の観点によれば、コンピュータを、ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、として機能させるためのプログラムが提供される。
【００２７】
また、上記課題を解決するために、本発明の別の観点によれば、ネットワーク上の観測点に配置された観測ノードと、前記観測ノードにおいて観測された端末間のフロー情報が提供される異常リンク推定装置と、からなる異常リンク推定システムであって、前記異常リンク推定装置は、前記観測ノードから前記ロー情報を収集するフロー情報収集部と、前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、を備える異常リンク推定システムが提供される。
【発明の効果】
【００２８】
以上説明したように本発明によれば、異常箇所を推定するためのメモリ量や演算負荷を抑制することが可能である。
【図面の簡単な説明】
【００２９】
【図１】本発明の第１の実施形態による異常リンク推定システムの構成を示した説明図である。
【図２】観測ノードの構成を示した機能ブロック図である。
【図３】ネットワークを流れる内部異常フローおよび外部異常フローの具体例を示した説明図である。
【図４】ネットワークを流れる内部正常フローおよび外部正常フローの具体例を示した説明図である。
【図５】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図６】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図７】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図８】本発明の第１の実施形態による異常リンク推定装置の構成を示した機能ブロック図である。
【図９】推定範囲絞り込み部の詳細な構成を示した説明図である。
【図１０】異常リンク推定装置の動作を示したフローチャートである。
【図１１】各リンクの内部異常フローの重複度を示した説明図である。
【図１２】各リンクの外部異常フローの重複度を示した説明図である。
【図１３】各リンクの内部異常フローの重複度の減算処理を示した説明図である。
【図１４】各リンクの外部異常フローの重複度の減算処理を示した説明図である。
【図１５】正常フローの観測点間リンクの外部異常フローの重複度の減算処理を示した説明図である。
【図１６】内部異常フローの重複度および外部異常フローの重複度の統合結果を示した説明図である。
【図１７】フロー・リンク対応表を示した説明図である。
【図１８】フロー・リンク対応表を示した説明図である。
【図１９】フロー・リンク対応表を示した説明図である。
【図２０】本発明の第２の実施形態による異常リンク推定システムの構成を示した説明図である。
【図２１】ネットワークを流れるフローの具体例を示した説明図である。
【図２２】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２３】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２４】観測ノードが異常リンク推定装置に送信するフロー情報を示した説明図である。
【図２５】本発明の第２の実施形態による異常リンク推定装置の構成を示した機能ブロック図である。
【図２６】推定範囲絞り込み部の詳細な構成を示した説明図である。
【図２７】異常リンク推定装置の動作を示したフローチャートである。
【図２８】各リンクの異常フローの重複度を示した説明図である。
【図２９】フロー・リンク対応表の具体例を示した説明図である。
【図３０】フロー・リンク対応表の具体例を示した説明図である。
【発明を実施するための形態】
【００３０】
以下に添付図面を参照しながら、本発明の実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００３１】
＜第１の実施形態＞
（異常リンク推定システムの構成）
図１は、本発明の第１の実施形態による異常リンク推定システム１の構成を示した説明図である。図１に示したように、本発明の第１の実施形態による異常リンク推定システム１は、端末Ｔ１〜Ｔ９、ルータ（あるいはスイッチ）Ｒ１〜Ｒ５、観測ノードＡ１〜Ａ３、および異常リンク推定装置１０を含む。端末Ｔ１〜Ｔ９、ルータＲ１〜Ｒ５、観測ノードＡ１〜Ａ３、および異常リンク推定装置１０は、リンクＬ１〜Ｌ１８により接続される。
【００３２】
なお、本明細書及び図面において、実質的に同一の機能構成を有する複数の構成要素を、同一のアルファベットの後に異なる符号を付して区別する場合もある。例えば、実質的に同一の機能構成を有する複数の構成を、必要に応じて観測ノードＡ１、Ａ２およびＡ３のように区別する。ただし、実質的に同一の機能構成を有する複数の構成要素の各々を特に区別する必要がない場合、同一アルファベットのみを付する。例えば、観測ノードＡ１、Ａ２およびＡ３を特に区別する必要が無い場合には、観測ノードＡと称する。
【００３３】
観測ノードＡは、ネットワーク上の観測点に配置されており、観測点を通過するトラフィックを観測し、観測により得られたフロー情報を異常リンク推定装置１０に送信する。この観測ノードＡは、ＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）やＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）のような小規模ネットワークのゲートウェイ部分に配置されてもよい。
【００３４】
ここで、ある観測ノードＡに着目した時に、当該観測ノードＡの観測点から他の観測点を経由せずに到達可能な端末までのリンクを内部ネットワークと称し、当該観測点から他の観測点までのリンク、および他の観測点を経由して到達可能な端末までのリンクを外部ネットワークと称する。本実施形態においては図１に示したように観測ノードＡ１の観測点に着目し、観測ノードＡ１の観測点から他の観測点を経由せずに到達可能な端末までのリンクＬ１〜Ｌ３、Ｌ１１〜Ｌ１５（およびルータＲ１〜Ｒ３）を内部ネットワークと称し、他のリンクを外部ネットワークと称する。
【００３５】
また、本実施形態においては、内部ネットワークのみを流れる端末間のデータフローを内部フローと称し、外部ネットワークを経由する端末間のデータフローを外部フローと称する。
【００３６】
異常リンク推定装置１０は、観測ノードＡ１〜Ａ３からフロー情報を収集し、収集したフロー情報に基づいてネットワーク上の異常リンクを推定する。詳細については後述するが、本実施形態による異常リンク推定装置１０は、推定範囲を絞り込んだ後に異常リンクを推定するので、異常リンクを推定するためのメモリ量や演算負荷を抑制することが可能である。
【００３７】
なお、図１においては異常リンク推定装置１０がルータＲ１に接続されている例を示しているが、異常リンク推定装置１０の配置位置はかかる例に限定されない。また、図１においては異常リンク推定装置１０を独立の構成として示しているが、異常リンク推定装置１０の機能は、観測ノードＡ、ルータＲ、または端末Ｔなどの他のノードに実装されてもよい。
【００３８】
（観測ノードの構成）
以上、図１を参照して本発明の第１の実施形態による異常リンク推定システム１の全体構成を説明した。続いて、図２〜図７を参照し、本発明の第１の実施形態による観測ノードＡの構成を説明する。
【００３９】
図２は、観測ノードＡの構成を示した機能ブロック図である。図２に示したように、観測ノードＡは、異常フロー検出部６２と、フロー情報記憶部６４と、フロー情報送信部６６と、を備える。
【００４０】
異常フロー検出部６２は、ネットワークを流れるフローを観測し、品質劣化した異常フローを検出する。例えば、異常フロー検出部６２は、フローのパケット損失率、送信遅延および遅延揺らぎなどの値を統計し、統計値が閾値を上回るか否かに応じて異常フローを検出してもよい。また、異常フロー検出部６２は、ＩＴＵ−Ｔ勧告のＧ．１０７に従ってＲ値と呼ばれる評価指標を用いて異常フローを検出してもよい。
【００４１】
フロー情報記憶部６４は、異常フロー検出部６２で任意の一定期間に観測された異常フローのフロー情報、および正常フローのフロー情報を記憶する。フロー情報は、端末などがネットワークを介してあるサービスを利用している時に通信する一連のトラフィックを識別することができればよい。例えば、フロー情報は、フロータイプ（異常フローｏｒ正常フロー）、送信元アドレス、送信先アドレス、プロトコルタイプ、送信元ポート番号、宛先ポート番号を含んでもよいし、さらに、入力インタフェースとサービスタイプを含んでもよい。
【００４２】
フロー情報送信部６６は、フロー情報記憶部６４に記憶されたフロー情報を異常リンク推定装置１０に送信する。なお、フロー情報送信部６６は、ネットワークを介してフロー情報を送信してもよいし、専用回線を介してフロー情報を送信してもよい。
【００４３】
ここで、図３〜図７を参照し、各観測ノードＡ１〜Ａ３から異常リンク推定装置１０に送信されるフロー情報の具体例を説明する。
【００４４】
図３は、ネットワークを流れる内部異常フローおよび外部異常フローの具体例を示した説明図である。図４は、ネットワークを流れる内部正常フローおよび外部正常フローの具体例を示した説明図である。図３および図４に示したように、ネットワークを内部異常フローＦ１およびＦ２、外部異常フローＦ４、Ｆ５およびＦ９、内部正常フローＦ３およびＦ６、外部正常フローＦ７およびＦ８が流れている場合、観測ノードＡ１〜Ａ３は、図５〜図７に示すフロー情報を異常リンク推定装置１０に送信する。
【００４５】
図５は、観測ノードＡ１が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図５に示したように、観測ノードＡ１は、観測点を通過するフローＦ１〜Ｆ９を観測し、フローＦ１〜Ｆ９の情報を異常リンク推定装置１０に送信する。なお、フロータイプ「１」は異常フローを示し、「０」は正常フローを示す。また、図５〜図７においては便宜上ＩＰアドレスとして端末の識別番号を示しているが、実際には、「１９２．１６８．０．８」のようなアドレスが記載される。また、各行がどのフローを表わすかを分かり易くするためにフロー番号の項目を設けているが、この項目は設けなくてもよい。
【００４６】
図６は、観測ノードＡ２が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図６に示したように、観測ノードＡ２は、観測点を通過するフローＦ４、Ｆ５およびＦ８を観測し、フローＦ４、Ｆ５およびＦ８の情報を異常リンク推定装置１０に送信する。
【００４７】
図７は、観測ノードＡ３が異常リンク推定装置１０に送信するフロー情報を示した説明図である。図７に示したように、観測ノードＡ３は、観測点を通過するフローＦ７およびＦ９を観測し、フローＦ７およびＦ９の情報を異常リンク推定装置１０に送信する。
【００４８】
（異常リンク推定装置の構成）
以上、図２〜図７を参照して観測ノードの構成を説明した。続いて、図８および図９を参照し、本発明の第１の実施形態による異常リンク推定装置１０の構成を説明する。
【００４９】
図８は、本発明の第１の実施形態による異常リンク推定装置１０の構成を示した機能ブロック図である。図８に示したように、異常リンク推定装置１０は、フロー情報収集部１１０と、フロー情報記憶部１２０と、トポロジ／ルーティング情報収集部１３０と、トポロジ／ルーティング情報記憶部１４０と、絞り込み規則蓄積部１５０と、推定範囲絞り込み部１６０と、絞り込み情報記憶部１７０と、異常リンク推定部１８０と、出力部１９０と、を備える。
【００５０】
フロー情報収集部１１０は、各観測ノードＡ１〜Ａ３から送信されるフロー情報を収集する。
【００５１】
フロー情報記憶部１２０は、フロー情報収集部１１０により収集されたフロー情報を、送信元の観測ノードが区別できるような形態で一時的に記憶する。
【００５２】
トポロジ／ルーティング情報収集部１３０は、ネットワークからルーティングに関する情報やトポロジ情報を収集する。例えば、トポロジ／ルーティング情報収集部１３０は、ネットワークを流れるＢＧＰのようのルーティングプロトコルのパケットを収集してもよいし、ルータＲからＳＮＭＰ（Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ）などにより情報を収集してもよい。
【００５３】
トポロジ／ルーティング情報記憶部１４０は、トポロジ／ルーティング情報収集部１３０により収集されたルーティングに関する情報やトポロジ情報を一時的に記憶する。このトポロジ／ルーティング情報記憶部１４０は、送受信ＩＰアドレスから、２点間の通信時に経由するリンクや、あるルータに接続されているリンクからルーティングによって到達可能なリンクを検索する機能を有してもよい。
【００５４】
絞り込み規則蓄積部１５０は、推定範囲絞り込み部１６０による絞り込みのための規則を蓄積する。
【００５５】
推定範囲絞り込み部１６０は、フロー情報記憶部１２０に記憶されたフロー情報、およびトポロジ／ルーティング情報記憶部１４０に記憶された情報を参照し、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込む。この推定範囲絞り込み部１６０の詳細な構成は図９を参照して後述する。
【００５６】
絞り込み情報記憶部１７０は、推定範囲絞り込み部１６０により絞り込まれた候補リンクを記憶する。
【００５７】
異常リンク推定部１８０は、絞り込み情報記憶部１７０に記憶されている候補リンクと、フロー情報記憶部１２０に記憶されているフロー情報を用いて異常リンクを推定する。例えば、異常リンク推定部１８０は、絞り込み情報記憶部１７０に記憶されている候補リンクに限定して非特許文献１に記載のフロー・リンク対応表を生成し、フロー・リンク対応表から最小リンク数推定方式によって異常リンクを推定してもよい。
【００５８】
出力部１９０は、異常リンク推定部１８０により推定されたネットワーク上の異常リンクを出力する。
【００５９】
（推定範囲絞り込み部の構成）
ここで、図９を参照し、推定範囲絞り込み部１６０の詳細な構成を説明する。図９は、推定範囲絞り込み部１６０の詳細な構成を示した説明図である。図９に示したように、推定範囲絞り込み部１６０は、重複度計数部１６２、重複度最大リンク判定部１６６、および候補リンク収集部１６８を含む。また、重複度計数部１６２は、異常フロー重複度計数部１６３、正常リンク重複度減算部１６４、および観測点間リンク重複度減算部１６５を含む。これら推定範囲絞り込み部１６０の構成および異常リンク推定部１８０は、図１０に示すステップ１〜ステップ６を実行することにより異常リンクを推定する。
【００６０】
（ステップ１）
異常フロー重複度計数部１６３は、観測点に接続する各リンクを通過する内部異常フローの数（重複度）、および観測点に接続する各リンクを通過する外部異常フローの数（重複度）を計数する。
【００６１】
（ステップ２）
正常リンク重複度減算部１６４は、以下の２種類のいずれかの正常フローが存在する場合、ステップ１で得られた内部異常フローの重複度、および外部異常フローの重複度の減算を行う。
・異常フローと共通する端末から出ている内部正常フローが存在する場合
正常リンク重複度減算部１６４は、ステップ１で得られた共通の端末側のリンクの異常フロー重複度から、共通の端末から出ている異常フローの数を減算する。
・異常フローと共通する端末から出ている外部正常フローが存在する場合
正常リンク重複度減算部１６４は、異常フローの他方の端末の存在する内部ネットワーク側のリンク以外であって、外部正常フローが経由する全ての観測点における外部正常フローが経由するリンクのステップ１で得られた異常フロー重複度から、共通の端末から出ている異常フローの数を減算する。
【００６２】
（ステップ３）
外部異常フローと同一の観測点間を通過する外部正常フローが存在する場合、観測点間リンク重複度減算部１６５は、観測点間のリンクの重複度から、当該観測点間を経由する外部異常フローの数を減算する。
【００６３】
（ステップ４）
重複度計数部１６２は、ステップ２およびステップ３の減算が行われた内部異常フローの重複度、および外部異常フローの重複度を統合（合計）する。
【００６４】
（ステップ５）
重複度最大リンク判定部１６６は、各リンクの統合された異常フロー重複度のうちで、異常フロー重複度が最大であるリンクを判定する。候補リンク収集部１６８は、異常フロー重複度が最大であると判定されたリンクを経由する異常フローが通過する端末側の候補リンクを収集する。異常リンク推定部１８０は、候補リンク収集部１６８により収集された候補リンクからなるフロー・リンク対応表を生成し、２番目に大きな異常フロー重複度以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在する場合、当該候補リンクを異常リンクと推定する。その後、重複度計数部１６２は、フロー・リンク対応表から異常リンクとして推定した候補リンクを通る異常フローを削除し、重複度最大リンク判定部１６６により判定されたリンクの異常フロー重複度から異常フローの削除数を減算する。また、異常リンクとして推定した候補リンクを通る異常フローが経由するもう一方の観測点へ繋がるリンクの異常フロー重複度から、異常フローの通過数を減算する。
【００６５】
一方、２番目に大きな異常フロー重複度以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在しない場合、重複度計数部１６２は、このフロー・リンク対応表で最も多く異常フローが通るリンクの異常フロー通過数を重複度最大リンク判定部１６６により判定されたリンクの異常フロー重複度から減算する。
【００６６】
（ステップ６）
ステップ５の処理を、観測点に接続する全リンクの異常フロー重複度が０になるまで繰り返す。
【００６７】
（異常リンク推定装置の具体的な処理）
以上、図９および図１０を参照して異常リンクの推定方法の概要を説明した。続いて、図１１〜図１９を参照し、本実施形態による異常リンク推定装置１０の具体的な処理を説明する。なお、以下では、ネットワーク上を図３および図４に示したフローが流れている場合の異常リンク推定装置１０の処理を説明する。
【００６８】
まず、ステップ１として、異常フロー重複度計数部１６３は、フロー情報記憶部１２０に記憶されているフロー情報に基づき、観測点Ａ１に接続するリンクの内部異常フローの重複度を図１１に示すように計数する。例えば、リンクＬ３を通過する内部異常フローは図３に示したように内部異常フローＦ１およびＦ２の２つであるので、リンクＬ３の内部異常フローの重複度は図１１に示したように「２」と計数される。
【００６９】
同様に、異常フロー重複度計数部１６３は、フロー情報記憶部１２０に記憶されているフロー情報に基づき、観測点Ａ１に接続するリンクの外部異常フローの重複度を図１２に示すように計数する。例えば、リンクＬ４を通過する外部異常フローは図３に示したようにＦ９の１つであるので、リンクＬ４の外部異常フローの重複度は図１２に示したように「１」と計数される。
【００７０】
次に、正常リンク重複度減算部１６４は、ステップ２として、図４に示したように内部異常フローＦ２と共通の端末Ｔ３から出ている内部正常フローが存在する場合、共通の端末Ｔ３側のリンクＬ２の重複度「１」から異常フローの通過数である「１」を減算する。これにより、内部異常フローのリンクＬ２の重複度は図１３に示したように「０」となる。
【００７１】
また、正常リンク重複度減算部１６４は、図４に示したように外部異常フローＦ４と共通の端末Ｔ３から出ている外部正常フローＦ７が存在する場合、外部異常フローＦ４の他側の端末Ｔ９側のリンクＬ５を除くリンクＬ２の重複度「１」から、異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ２の重複度は図１４に示したように「０」となる。
【００７２】
同様に、外部正常フローＦ７は、外部異常フローＦ９と共通の端末Ｔ６から出ているので、正常リンク重複度減算部１６４は、外部異常フローＦ９の他側の端末Ｔ５側のリンクＬ３を除くリンクＬ４、Ｌ６およびＬ８の重複度「１」から、異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ４、Ｌ６およびＬ８の重複度は図１４に示したように「０」となる。
【００７３】
さらに、正常リンク重複度減算部１６４は、図４に示したように、外部異常フローＦ５と共通の端末Ｔ２から出ている内部正常フローＦ６が存在する場合、共通の端末Ｔ２側のリンクＬ１の重複度「１」から異常フローの通過数である「１」を減算する。これにより、外部異常フローのリンクＬ１の重複度は図１４に示したように「０」となる。
【００７４】
続いて、観測点間リンク重複度減算部１６５は、ステップ３として、図４に示したように観測点Ａ１およびＡ２を経由する外部正常フローが観測されている場合、観測点Ａ１およびＡ２間のリンクＬ５およびＬ７の外部異常フローの重複度「２」から、同一の観測点Ａ１およびＡ２を経由する外部異常フロー数である「２」（Ｆ４およびＦ５の２つ）を減算する。これにより、外部異常フローのリンクＬ５およびＬ７の重複度は図１５に示したように「０」になる。
【００７５】
次に、重複度計数部１６２は、ステップ４として、図１３に示した各リンクの内部異常フローの重複度、および図１５に示した外部異常フローの重複度を統合（合計）する。これにより、図１６に示す統合結果が得られる。
【００７６】
その後、ステップ５へ移行する。すなわち、重複度最大リンク判定部１６６は、図１６に示したようにリンクＬ３が最大の重複度「３」を有するので、リンクＬ３を重複度が最大のリンクとして判定する。そして、候補リンク収集部１６８は、リンクＬ３を異常フローＦ１、Ｆ２およびＦ９が経由するので、これらのフローがＬ３を経由する端末までのリンクを候補リンクとして収集する。
【００７７】
さらに、異常リンク推定部１８０は、図１７に示したように、候補リンク収集部１６８により収集された候補リンクからなるフロー・リンク対応表を生成する。そして、異常リンク推定部１８０は、２番目に大きなＬ９の重複度「２」以上の数の異常フローの通る候補リンクＬ１５がフロー・リンク対応表に存在するので、Ｌ１５を異常リンクとして推定する。その後、重複度計数部１６２は、リンクＬ３の重複度を「３」から「０」とする。一方、異常フローＦ１、Ｆ２およびＦ９が通る他のリンクＬ１、Ｌ２、Ｌ４、Ｌ６およびＬ８の重複度は既にステップ２およびステップ３で「０」に減算されているので、ここでの重複度の減算は行われない。
【００７８】
仮に、図１８に示すフロー・リンク対応表が生成された場合、２番目に大きなＬ９の重複度「２」以上の数の異常フローの通る候補リンクがフロー・リンク対応表に存在しない。この場合、重複度計数部１６２は、フロー・リンク対応表で最も多く異常フローの通るリンクの異常フロー通過数「１」にリンクＬ３の重複度を更新する。
【００７９】
ここまでで１順目のステップ５が終了し、２順目のステップ５で、残りの全リンクから最も重複度の大きいリンクＬ９が選択され、同様の処理により、図１９に示したフロー・リンク表が生成され、リンクＬ１８が異常リンクとして推定され、Ｌ９の重複度が「０」に更新される。これにより、全ての観測点に接続するリンクの異常フロー重複度が「０」となる。
【００８０】
以上説明したように、本発明の第１の実施形態によれば、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することができる。したがって、本発明の第１の実施形態によれば、異常リンクを推定するためのメモリ量や演算負荷を抑制することが可能である。
【００８１】
＜２．第２の実施形態＞
続いて、本発明の第２の実施形態を説明する。
【００８２】
（異常リンク推定システムの構成）
図２０は、本発明の第２の実施形態による異常リンク推定システム２の構成を示した説明図である。図２０に示したように、本発明の第２の実施形態による異常リンク推定システム２は、端末Ｔ１〜Ｔ２２、ルータ（あるいはスイッチ）Ｒ１〜Ｒ１６、観測ノードＡ１〜Ａ３、および異常リンク推定装置２０を含む。端末Ｔ１〜Ｔ２２、ルータＲ１〜Ｒ１６、観測ノードＡ１〜Ａ３、および異常リンク推定装置２０は、リンクＬ１〜Ｌ４２により接続される。
【００８３】
観測ノードＡは、ネットワーク上の観測点に配置されており、観測点を通過するトラフィックを観測し、観測により得られたフロー情報を異常リンク推定装置２０に送信する。図２０に示したように、観測ノードＡ１、Ａ２およびＡ３は、例えばルータＲ３、Ｒ１０、Ｒ６の設置部分に配置される。この観測ノードＡの構成は第１の実施形態で説明した通りであるので、詳細な説明を省略する。
【００８４】
第２の実施形態による異常リンク推定装置２０は、観測ノードＡ１〜Ａ３からフロー情報を収集し、収集したフロー情報に基づいてネットワーク上の異常リンクを推定する。第２の実施形態による異常リンク推定装置２０は、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することが可能である。
【００８５】
ここで、図２１〜図２４を参照し、各観測ノードＡ１〜Ａ３から異常リンク推定装置２０に送信されるフロー情報の具体例を説明する。
【００８６】
図２１は、ネットワークを流れるフローの具体例を示した説明図である。図２１に示したように、ネットワークをフローＦ１〜Ｆ１１が流れる場合、観測ノードＡ１〜Ａ３は、図２２〜図２４に示すフロー情報を異常リンク推定装置２０に送信する。
【００８７】
図２２は、観測ノードＡ１が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２２に示したように、観測ノードＡ１は、観測点を通過するフローＦ３〜Ｆ６を観測し、フローＦ３〜Ｆ６の情報を異常リンク推定装置２０に送信する。
【００８８】
図２３は、観測ノードＡ２が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２３に示したように、観測ノードＡ２は、観測点を通過するフローＦ１、Ｆ１０およびＦ１１を観測し、フローＦ１、Ｆ１０およびＦ１１の情報を異常リンク推定装置２０に送信する。
【００８９】
図２４は、観測ノードＡ３が異常リンク推定装置２０に送信するフロー情報を示した説明図である。図２４に示したように、観測ノードＡ３は、観測点を通過するフローＦ２、Ｆ３およびＦ７〜Ｆ９を観測し、フローＦ２、Ｆ３およびＦ７〜Ｆ９の情報を異常リンク推定装置２０に送信する。
【００９０】
（異常リンク推定装置の構成）
図２５は、本発明の第２の実施形態による異常リンク推定装置２０の構成を示した機能ブロック図である。図２５に示したように、異常リンク推定装置２０は、フロー情報収集部２１０と、フロー情報記憶部２２０と、トポロジ／ルーティング情報収集部２３０と、トポロジ／ルーティング情報記憶部２４０と、絞り込み規則蓄積部２５０と、推定範囲絞り込み部２６０と、絞り込み情報記憶部２７０と、異常リンク推定部２８０と、出力部２９０と、を備える。
【００９１】
なお、フロー情報収集部２１０、フロー情報記憶部２２０、トポロジ／ルーティング情報収集部２３０、およびトポロジ／ルーティング情報記憶部２４０は、第１の実施形態によるフロー情報収集部１１０、フロー情報記憶部１２０、トポロジ／ルーティング情報収集部１３０、およびトポロジ／ルーティング情報記憶部１４０と実質的に同一であるので、詳細な説明を省略する。
【００９２】
絞り込み規則蓄積部２５０は、推定範囲絞り込み部２６０による絞り込みのための規則を蓄積する。
【００９３】
推定範囲絞り込み部２６０は、フロー情報記憶部２２０に記憶されたフロー情報、およびトポロジ／ルーティング情報記憶部４０に記憶された情報を参照し、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込む。この推定範囲絞り込み部２６０の詳細な構成は図２６を参照して後述する。
【００９４】
絞り込み情報記憶部２７０は、推定範囲絞り込み部２６０により絞り込まれた候補リンクを記憶する。
【００９５】
異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶されている候補リンクと、フロー情報記憶部２２０に記憶されているフロー情報を用いて異常リンクを推定する。例えば、異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶されている候補リンクに限定して非特許文献１に記載のフロー・リンク対応表を生成し、フロー・リンク対応表から最小リンク数推定方式によって異常リンクを推定してもよい。
【００９６】
出力部２９０は、異常リンク推定部２８０により推定されたネットワーク上の異常リンクを出力する。
【００９７】
（推定範囲絞り込み部の構成）
ここで、図２６を参照し、推定範囲絞り込み部２６０の詳細な構成を説明する。図２６は、推定範囲絞り込み部２６０の詳細な構成を示した説明図である。図２６に示したように、推定範囲絞り込み部２６０は、異常フロー重複度計数部２６２、重複度最大リンク判定部２６４、複数観測点通過異常フロー収集部２６６、異常フロー数比較部２６７および候補リンク収集部２６８を含む。このような推定範囲絞り込み部２６０および異常リンク推定部２８０は、図２７に示すＳ３１０〜Ｓ３６０を実行することにより異常リンクを推定する。
【００９８】
まず、異常フロー重複度計数部２６２が、各観測点に接続するリンクを経由する異常フローの数（重複度）を計数する（Ｓ３１０）。続いて、重複度最大リンク判定部２６４が、各観測点に接続するリンクのうちで、異常フローの重複度が最大であるリンクを判定する（Ｓ３２０）。
【００９９】
そして、候補リンク収集部２６８は、重複度最大リンク判定部２６４により判定される重複度が最大であるリンクが１つである場合、ルーティング情報を参照し、重複度最大リンク判定部２６４により判定されたリンクを経由して到達可能なリンクを候補リンクとして収集する（Ｓ３３０）。一方、候補リンク収集部２６８は、重複度最大リンク判定部２６４により判定される重複度が最大であるリンクが１つでない場合、異常フローの通るリンクから到達可能な端末または観測点までの全リンクを候補リンクとして収集する（Ｓ３３０）。候補リンク収集部２６８により収集された候補リンクは絞り込み情報記憶部２７０に記憶される。
【０１００】
その後、複数観測点間通過異常フロー収集部２６６が、フロー情報記憶部２２０に記憶されているフロー情報から、複数の観測点を通過する異常フローを収集する（Ｓ３４０）。
【０１０１】
続いて、異常フロー数比較部２６７が、Ｓ３４０において収集された異常フローが通過する２つの観測点において検出された異常フローの総数を比較し、候補リンク収集部２６８が、比較結果に応じて絞り込み情報記憶部２７０の候補リンクを追加または削除する（Ｓ３５０）。例えば、候補リンク収集部２６８は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外してもよい。
【０１０２】
そして、異常リンク推定部２８０は、絞り込み情報記憶部２７０に記憶された候補リンクからなるフロー・リンク対応表を生成し、このフロー・リンク対応表に対し最小リンク数推定方式を適用することにより異常リンクを推定する（Ｓ３６０）。
【０１０３】
（異常リンク推定装置の具体的な処理）
以上、図２６および図２７を参照して異常リンクの推定方法の概要を説明した。続いて、図２８〜図３０を参照し、本実施形態による異常リンク推定装置２０の具体的な処理を説明する。なお、以下では、ネットワーク上を図２１に示したフローが流れている場合の異常リンク推定装置２０の処理を説明する。
【０１０４】
まず、異常フロー重複度計数部２６２は、トポロジ／ルーティング情報記憶部２４０を参照し、観測ノードＡ１による観測点であるルータＲ３にリンクＬ３、Ｌ４、Ｌ１０、Ｌ１１、Ｌ１２およびＬ１３が接続されていることを認識する。そして、異常フロー重複度計数部２６２は、この観測点で観測された異常フローをフロー情報記憶部２２０から収集し、トポロジ／ルーティング情報記憶部２４０を参照して各異常フローが通るリンクを判定する。図２１に示した例では、異常フローＦ５がリンクＬ４およびＬ１３を通り、異常フローＦ６がリンクＬ１１およびＬ１３を通り、異常フローＦ２がリンクＬ３とＬ１２を通る。このため、異常フロー重複度計数部２６２は、図２８に示したように、リンクＬ３、Ｌ４、Ｌ１１およびＬ１２の重複度を「１」、リンクＬ１３の重複度を「２」と計数する（Ｓ３１０）。
【０１０５】
続いて、重複度最大リンク判定部２６４が、観測点であるルータＲ３に接続するリンクＬ３、Ｌ４、Ｌ１０、Ｌ１１、Ｌ１２およびＬ１３のうちで、異常フローの重複度が最大であるリンクがＬ１３であると判定する（Ｓ３２０）。
【０１０６】
このため、候補リンク収集部２６８は、ルータＲ３からルーティングによってリンクＬ１３を経由して到達可能な端末までの経路上の全リンク、すなわち、Ｌ７、Ｌ８およびＬ１３をトポロジ／ルーティング情報記憶部２４０から候補リンクとして収集する（Ｓ３３０）。
【０１０７】
同様に、観測ノードＡ２に関し、異常フロー重複度計数部２６２は、ルータＲ１０を経由する異常フローＦ１０およびＦ１１がリンクＬ２９およびＬ４２を通るので、図２８に示したようにリンクＬ２９およびＬ４２の重複度を「２」と計数する。よって、重複度最大リンク判定部２６４によりＬ２９およびＬ４２の双方が重複度の最大リンクとして判定されるので、候補リンク収集部２６８は、ルータＲ１０からリンクＬ２９またはＬ４２を経由してルーティングによって到達可能な端末または他の観測点までの全リンク、すなわち、リンクＬ２９〜Ｌ４２を候補リンクとして収集する。なお、異常フロー重複度計数部２６２は、同一ペアのリンクを通る異なる異常フローは重複して計数しなくてもよい。例えば、異常フローＦ１０およびＦ１１が通るリンクのペアはＬ２９とＬ４２で同一であるので、Ｌ２９およびＬ４２の重複度を「１」と計数してもよい。
【０１０８】
同様に、観測ノードＡ３に関し、異常フロー重複度計数部２６２は、ルータＲ６を経由する異常フローＦ２およびＦ３がリンクＬ１５およびＬ２７を通るので、図２８に示したようにリンクＬ１５およびＬ２７の重複度を「２」と計数する。よって、重複度最大リンク判定部２６４によりＬ１５およびＬ２７の双方が重複度の最大リンクとして判定されるので、候補リンク収集部２６８は、ルータＲ６からリンクＬ１５またはＬ２７を経由してルーティングによって到達可能な端末または他の観測点までの全リンク、すなわち、リンクＬ１５を経由して到達可能なリンクＬ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１２、およびＬ１４、リンクＬ２７を経由して到達可能なリンクＬ２３およびＬ２４を候補リンクとして収集する。
【０１０９】
続いて、複数観測点間通過異常フロー収集部２６６が、観測ノードＡ１による観測点Ｒ３および観測ノードＡ３による観測点Ｒ６を通過する異常フローＦ３を収集する（Ｓ３４０）。
【０１１０】
そして、異常フロー数比較部２６７が、Ｒ３において検出された異常フローの総数、およびＲ６において検出された異常フローの総数を比較する。ここで、Ｒ３において検出された異常フローの総数は「３」であり、Ｒ６において検出された異常フローの総数は「２」であるので、Ｒ６において検出された異常フローの総数の方が少ない。このため、候補リンク収集部２６８は、Ｒ６からＲ３への接続リンクＬ１５から到達可能な端末および他の観測点までのリンク、すなわち、Ｌ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１２、Ｌ１４およびＬ１５を候補リンクとして収集する。一方、候補リンク収集部２６８は、Ｌ１７およびＬ２７からルーティングにより到達可能な端末または他の観測点までのリンク、すなわち、既に収集されたリンクＬ２３、Ｌ２４およびＬ２７は、候補リンクから削除する（Ｓ３５０）。
【０１１１】
ここまでの処理により、絞り込み情報記憶部２７０には、候補リンクとしてリンクＬ１、Ｌ２、Ｌ７〜Ｌ９、Ｌ１３〜Ｌ１５、およびＬ２９〜Ｌ４２が記憶される。
【０１１２】
次に、異常リンク推定部２８０が、絞り込み情報記憶部２７０に記憶されている候補リンクを用い、図２９に示すフロー・リンク対応表を生成する。このフロー・リンク対応表において、列が各リンク、行が各異常フロー、各異常フローが通過するリンクを「１」、各異常フローが通過するリンクを「０」と示している。
【０１１３】
その後、異常リンク推定部２８０は、図２９に示したフロー・リンク対応表から、正常フローの通るリンク、およびどのフローも通らないリンクを削除し、図３０に示したフロー・リンク対応表を得る。異常リンク推定部２８０は、図３０に示したフロー・リンク対応表に対して最小リンク数推定方式を適用することにより、図３０で四角で囲って示したリンクＬ１３、Ｌ１５およびＬ４２を異常リンクとして推定することができる。
【０１１４】
以上説明したように、本発明の第２の実施形態によれば、異常リンクを推定するための対象範囲をとなる候補リンクを絞り込み、絞り込まれた候補リンクから例えばフロー・リンク表を用いて異常リンクを推定することができる。したがって、本発明の第２の実施形態によれば、異常リンクを推定するためのメモリ量、演算負荷およびコストなどを抑制することが可能である。
【０１１５】
＜３．補足＞
なお、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【０１１６】
例えば、本明細書の異常リンク推定装置１０または２０の処理における各ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はない。例えば、異常リンク推定装置１０または２０の処理における各ステップは、フローチャートとして記載した順序と異なる順序で処理されても、並列的に処理されてもよい。
【０１１７】
また、異常リンク推定装置１０または２０に内蔵されるＣＰＵ、ＲＯＭおよびＲＡＭなどのハードウェアを、上述した異常リンク推定装置１０または２０の各構成と同等の機能を発揮させるためのコンピュータプログラムも作成可能である。また、該コンピュータプログラムを記憶させた記憶媒体も提供される。
【符号の説明】
【０１１８】
１、２ 異常リンク推定システム
１０、２０ 異常リンク推定装置
６２ 異常フロー検出部
６４ フロー情報記憶部
６６ フロー情報送信部
１１０、２１０ フロー情報収集部
１２０、２２０ フロー情報記憶部
１３０、２３０ トポロジ／ルーティング情報収集部
１４０、２４０ トポロジ／ルーティング情報記憶部
１５０、２５０ 絞り込み規則蓄積部
１６０、２６０ 推定範囲絞り込み部
１６２ 重複度計数部
１６３、２６２ 異常フロー重複度計数部
１６４ 正常リンク重複度減算部
１６５ 観測点間リンク重複度減算部
１６６，２６４ 重複度最大リンク判定部
１６８、２６８ 候補リンク収集部
１７０、２７０ 絞り込み情報記憶部
１８０、２８０ 異常リンク推定部
１９０、２９０ 出力部
２６６ 複数観測点通過異常フロー収集部
２６７ 異常フロー数比較部
【特許請求の範囲】
【請求項１】
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
を備える、異常リンク推定装置。
【請求項２】
前記候補リンク収集部は、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクが１つでない場合、前記観測点に接続するリンクのうちで異常フローの通るリンクから到達可能な候補リンクを収集する、請求項１に記載の異常リンク推定装置。
【請求項３】
前記ネットワーク上には複数の観測ノードが複数の観測点に配置されており、
前記フロー情報収集部は、前記複数の観測ノードから前記フロー情報を収集し、
前記計数部、前記候補リンク収集部、および前記異常リンク推定部は、前記複数の観測点の各々に接続するリンクに関して処理を行う、請求項１に記載の異常リンク推定装置。
【請求項４】
前記計数部は、前記異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、当該端末側のリンクの異常フローの重複度から、当該端末から出ている異常フローの重複度を減算する、請求項３に記載の異常リンク推定装置。
【請求項５】
前記ネットワークは、１の観測点から他の観測点を経由せずに到達可能な端末までのリンクを含む内部ネットワーク、および、前記１の観測点から前記他の観測点までのリンクを含む外部ネットワークからなり、
前記ネットワークには、前記外部ネットワークを経由する外部フロー、および前記内部ネットワーク内で前記外部ネットワークを経由しない内部フローが流れ、
前記計数部は、内部フローのうちで異常のある内部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記１の観測点に接続する当該端末側のリンクの内部異常フローの重複度から、当該端末から出ている内部異常フローの数を減算する、請求項３に記載の異常リンク推定装置。
【請求項６】
前記計数部は、外部フローのうちで異常のある外部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記正常フローが経由するリンクのうちで、
前記１の観測点に接続する前記外部異常フローの他側の端末側のリンク以外のリンクの異常フロー重複度から、共通する端末から出ている外部異常フローの数を減算する、請求項５に記載の異常リンク推定装置。
【請求項７】
前記計数部は、前記１の観測点および前記他の観測点を経由する外部正常フローが観測されている場合、前記１の観測点に接続する前記他の観測点側のリンクの異常フロー重複度から、前記１の観測点および前記他の観測点を経由する異常フローの数を減算する、請求項６に記載の異常リンク推定装置。
【請求項８】
前記異常リンク推定部は、
前記候補リンク収集部により収集された前記候補リンク、および前記候補リンクを通過する異常フローおよび正常フローの対応表を作成し、
前記対応表から、正常フローの通過する候補リンクを削除し、
残った候補リンクの各々を通る異常フローの数に基づいて前記異常リンクを推定する、請求項７に記載の異常リンク推定装置。
【請求項９】
前記異常リンク推定部は、対応表に異常フローの通過数が最大の候補リンクが存在し、かつ、当該候補リンクの異常フローの通過数が、前記複数の観測点に接続する全リンクの異常フロー重複度のうちで２番目に大きな値以上である場合、当該候補リンクを前記異常リンクとして推定する、請求項８に記載の異常リンク推定装置。
【請求項１０】
前記観測ノードは、前記ネットワークのゲートウェイ部分の観測点に配置される、請求項３に記載の異常リンク推定装置。
【請求項１１】
前記異常リンク推定装置は、
２以上の観測点を通過する異常フローを収集する異常フロー収集部と、
前記２以上の観測点の各々を通過する異常フローの総数を比較する異常フロー数比較部と、
をさらに備え、
候補リンク収集部は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外する、請求項３に記載の異常リンク推定装置。
【請求項１２】
前記計数部は、前記観測点に接続する同一のリンクを通過する複数の異常フローは重複して計数しない、請求項１１に記載の異常リンク推定装置。
【請求項１３】
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するステップと、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数するステップと、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定するステップと、
異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集するステップと、
前記候補リンクから異常の発生している異常リンクを推定するステップと、
を含む、異常リンク推定方法。
【請求項１４】
コンピュータを、
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
として機能させるための、プログラム。
【請求項１５】
ネットワーク上の観測点に配置された観測ノードと、前記観測ノードにおいて観測された端末間のフロー情報が提供される異常リンク推定装置と、からなる異常リンク推定システムであって、
前記異常リンク推定装置は、
前記観測ノードから前記ロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
を備える、異常リンク推定システム。
【請求項１】
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
を備える、異常リンク推定装置。
【請求項２】
前記候補リンク収集部は、前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクが１つでない場合、前記観測点に接続するリンクのうちで異常フローの通るリンクから到達可能な候補リンクを収集する、請求項１に記載の異常リンク推定装置。
【請求項３】
前記ネットワーク上には複数の観測ノードが複数の観測点に配置されており、
前記フロー情報収集部は、前記複数の観測ノードから前記フロー情報を収集し、
前記計数部、前記候補リンク収集部、および前記異常リンク推定部は、前記複数の観測点の各々に接続するリンクに関して処理を行う、請求項１に記載の異常リンク推定装置。
【請求項４】
前記計数部は、前記異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、当該端末側のリンクの異常フローの重複度から、当該端末から出ている異常フローの重複度を減算する、請求項３に記載の異常リンク推定装置。
【請求項５】
前記ネットワークは、１の観測点から他の観測点を経由せずに到達可能な端末までのリンクを含む内部ネットワーク、および、前記１の観測点から前記他の観測点までのリンクを含む外部ネットワークからなり、
前記ネットワークには、前記外部ネットワークを経由する外部フロー、および前記内部ネットワーク内で前記外部ネットワークを経由しない内部フローが流れ、
前記計数部は、内部フローのうちで異常のある内部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記１の観測点に接続する当該端末側のリンクの内部異常フローの重複度から、当該端末から出ている内部異常フローの数を減算する、請求項３に記載の異常リンク推定装置。
【請求項６】
前記計数部は、外部フローのうちで異常のある外部異常フローと少なくとも一方の端末が共通する正常フローが観測されている場合、前記正常フローが経由するリンクのうちで、
前記１の観測点に接続する前記外部異常フローの他側の端末側のリンク以外のリンクの異常フロー重複度から、共通する端末から出ている外部異常フローの数を減算する、請求項５に記載の異常リンク推定装置。
【請求項７】
前記計数部は、前記１の観測点および前記他の観測点を経由する外部正常フローが観測されている場合、前記１の観測点に接続する前記他の観測点側のリンクの異常フロー重複度から、前記１の観測点および前記他の観測点を経由する異常フローの数を減算する、請求項６に記載の異常リンク推定装置。
【請求項８】
前記異常リンク推定部は、
前記候補リンク収集部により収集された前記候補リンク、および前記候補リンクを通過する異常フローおよび正常フローの対応表を作成し、
前記対応表から、正常フローの通過する候補リンクを削除し、
残った候補リンクの各々を通る異常フローの数に基づいて前記異常リンクを推定する、請求項７に記載の異常リンク推定装置。
【請求項９】
前記異常リンク推定部は、対応表に異常フローの通過数が最大の候補リンクが存在し、かつ、当該候補リンクの異常フローの通過数が、前記複数の観測点に接続する全リンクの異常フロー重複度のうちで２番目に大きな値以上である場合、当該候補リンクを前記異常リンクとして推定する、請求項８に記載の異常リンク推定装置。
【請求項１０】
前記観測ノードは、前記ネットワークのゲートウェイ部分の観測点に配置される、請求項３に記載の異常リンク推定装置。
【請求項１１】
前記異常リンク推定装置は、
２以上の観測点を通過する異常フローを収集する異常フロー収集部と、
前記２以上の観測点の各々を通過する異常フローの総数を比較する異常フロー数比較部と、
をさらに備え、
候補リンク収集部は、異常フローの総数が少ない方の観測点から異常フローの総数が多い方の観測点への接続リンクから到達可能なリンクを候補リンクとしてさらに収集し、異常フローの総数が少ない方の観測点から前記接続リンク以外のリンクを経由して到達可能なリンクを候補リンクから除外する、請求項３に記載の異常リンク推定装置。
【請求項１２】
前記計数部は、前記観測点に接続する同一のリンクを通過する複数の異常フローは重複して計数しない、請求項１１に記載の異常リンク推定装置。
【請求項１３】
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するステップと、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数するステップと、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定するステップと、
異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集するステップと、
前記候補リンクから異常の発生している異常リンクを推定するステップと、
を含む、異常リンク推定方法。
【請求項１４】
コンピュータを、
ネットワーク上の観測点に配置された観測ノードから端末間のフロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
として機能させるための、プログラム。
【請求項１５】
ネットワーク上の観測点に配置された観測ノードと、前記観測ノードにおいて観測された端末間のフロー情報が提供される異常リンク推定装置と、からなる異常リンク推定システムであって、
前記異常リンク推定装置は、
前記観測ノードから前記ロー情報を収集するフロー情報収集部と、
前記フロー情報に基づき、前記観測点に接続する各リンクを通過している異常フローの重複度を計数する計数部と、
前記観測点に接続するリンクのうちで異常フロー重複度が最大であるリンクを判定する判定部と、
前記判定部により異常フロー重複度が最大であると判定されたリンクを経由してルーティングにより到達可能な候補リンクを収集する候補リンク収集部と、
前記候補リンクから異常の発生している異常リンクを推定する異常リンク推定部と、
を備える、異常リンク推定システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【公開番号】特開２０１２−１８２７３９（Ｐ２０１２−１８２７３９Ａ）
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願番号】特願２０１１−４５５１８（Ｐ２０１１−４５５１８）
【出願日】平成２３年３月２日（２０１１．３．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／次世代ネットワーク（ＮＧＮ）基盤技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願日】平成２３年３月２日（２０１１．３．２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／次世代ネットワーク（ＮＧＮ）基盤技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
[ Back to top ]