(57)【要約】【課題】大規模ネットワークにおいて品質劣化箇所の高速推定を可能にする品質劣化箇所推定方法、装置およびシステムを提供する。【解決手段】通信ネットワーク（１００）における品質劣化箇所を推定する装置であって、複数の通信フローの通信品質情報と前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報とを含むフローリンクテーブル（３０３）を生成するフローリンクテーブル生成部（２０２）と、フローリンクテーブルに基づいて複数の通信フローを複数の通信フロー集合に分類するフロー分類部（２０４）と、複数の通信フロー集合のうち通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する品質劣化箇所推定部（２０５）と、を有する。【選択図】図４
2011041043.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークにおける品質劣化箇所を推定する装置であって、
複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、
前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、
前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する推定手段と、
を有することを特徴とする品質劣化箇所推定装置。
【請求項２】
前記フロー分類手段は、前記複数の通信フローの各々が経由する個別フローリンクの類似性に基づいて分類することを特徴とする請求項１に記載の品質劣化箇所推定装置。
【請求項３】
前記類似性は、通信フロー間の各々の個別フローリンクを示す情報を符号とした場合の符号間距離により決定されることを特徴とする請求項２に記載の品質劣化箇所推定装置。
【請求項４】
前記フロー分類手段は、前記複数の通信フロー間の最大符号間距離を有する通信フローペアのうち一方を基準フローとして選択し、前記基準フローとの符号間距離に応じて前記フローリンクテーブルを並び替えることを特徴とする請求項３に記載の品質劣化箇所推定装置。
【請求項５】
前記フロー分類手段は前記並び替えられたフローリンクテーブルを所定数の部分テーブルに分割し、前記推定手段は通信品質劣化を示す通信フローを含む部分テーブルごとに品質劣化箇所を推定することを特徴とする請求項４に記載の品質劣化箇所推定装置。
【請求項６】
前記類似性は、前記複数の通信フローの各々が経由する個別フローリンクの一致あるいは不一致の個数に基づいて決定されることを特徴とする請求項２−５のいずれか１項に記載の品質劣化箇所推定装置。
【請求項７】
前記フロー分類手段は、前記複数の通信フローの各々が経由する個別フローリンクの一致数が予め設定された閾値以上となる２以上の通信フローを選択することで通信フロー集合を抽出することを特徴とする請求項６に記載の品質劣化箇所推定装置。
【請求項８】
前記推定手段は複数の推定部からなり、前記複数の推定部が前記複数の通信フロー集合に関する品質劣化箇所を分散処理により推定することを特徴とする請求項１−７のいずれか１項に記載の品質劣化箇所推定装置。
【請求項９】
通信ネットワークにおける品質劣化箇所を推定する方法であって、
複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリングテーブル生成ステップと、
前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類ステップと、
前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する推定ステップと、
を有することを特徴とする品質劣化箇所推定方法。
【請求項１０】
前記フロー分類ステップは、前記複数の通信フローの各々が経由する個別フローリンクの類似性に基づいて前記複数の通信フローを複数の通信フロー集合に分類することを特徴とする請求項９に記載の品質劣化箇所推定方法。
【請求項１１】
前記類似性は、通信フロー間の各々の個別フローリンクを示す情報を符号とした場合の符号間距離により決定されることを特徴とする請求項１０に記載の品質劣化箇所推定方法。
【請求項１２】
前記フロー分類ステップは、前記複数の通信フロー間の最大符号間距離を有する通信フローペアのうち一方を基準フローとして選択し、前記基準フローとの符号間距離に応じて前記フローリンクテーブルを並び替えることを特徴とする請求項１１に記載の品質劣化箇所推定方法。
【請求項１３】
前記フロー分類ステップは、前記並び替えられたフローリンクテーブルを所定数の部分テーブルに分割し、前記推定ステップは通信品質劣化を示す通信フローを含む部分テーブルごとに品質劣化箇所を推定することを特徴とする請求項１２に記載の品質劣化箇所推定方法。
【請求項１４】
前記類似性は、前記複数の通信フローの各々が経由する個別フローリンクの一致あるいは不一致の個数に基づいて決定されることを特徴とする請求項１０−１３のいずれか１項に記載の品質劣化箇所推定方法。
【請求項１５】
前記フロー分類ステップは、前記複数の通信フローの各々が経由する個別フローリンクの一致数が予め設定された閾値以上となる２以上の通信フローを選択することで通信フロー集合を抽出することを特徴とする請求項１４に記載の品質劣化箇所推定方法。
【請求項１６】
前記推定ステップは、複数の推定ステップを並列実行することにより前記複数の通信フロー集合に関する品質劣化箇所を推定することを特徴とする請求項９−１５のいずれか１項に記載の品質劣化箇所推定方法。
【請求項１７】
通信ネットワーク中の品質劣化箇所の推定処理を行う品質劣化箇所推定システムであって、
前記通信ネットワークにおける通信フローの通信品質を測定する少なくとも１つの品質計測装置と、
前記品質計測装置から入力した複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、を有する管制装置と、
前記管制装置から受信した前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する少なくとも１つの推定装置と、
を前記通信ネットワーク上に配置したことを特徴とする品質劣化箇所推定システム。
【請求項１８】
前記フロー分類手段は、前記複数の通信フローの各々が経由する個別フローリンクの類似性に基づいて分類することを特徴とする請求項１７に記載の品質劣化箇所推定システム。
【請求項１９】
前記類似性は、通信フロー間の各々の個別フローリンクを示す情報を符号とした場合の符号間距離により決定されることを特徴とする請求項１８に記載の品質劣化箇所推定システム。
【請求項２０】
前記フロー分類手段は、前記複数の通信フロー間の最大符号間距離を有する通信フローペアのうち一方を基準フローとして選択し、前記基準フローとの符号間距離に応じて前記フローリンクテーブルを並び替えることを特徴とする請求項１９に記載の品質劣化箇所推定システム。
【請求項２１】
前記フロー分類手段は前記並び替えられたフローリンクテーブルを所定数の部分テーブルに分割し、前記推定装置は通信品質劣化を示す通信フローを含む部分テーブルごとに品質劣化箇所を推定することを特徴とする請求項２０に記載の品質劣化箇所推定システム。
【請求項２２】
前記類似性は、前記複数の通信フローの各々が経由する個別フローリンクの一致あるいは不一致の個数に基づいて決定されることを特徴とする請求項１８−２１のいずれか１項に記載の品質劣化箇所推定システム。
【請求項２３】
前記フロー分類手段は、前記複数の通信フローの各々が経由する個別フローリンクの一致数が予め設定された閾値以上となる２以上の通信フローを選択することで通信フロー集合を抽出することを特徴とする請求項２２に記載の品質劣化箇所推定システム。
【請求項２４】
複数の推定装置が前記複数の通信フロー集合に関する品質劣化箇所を分散処理により推定することを特徴とする請求項１７−２３のいずれか１項に記載の品質劣化箇所推定システム。
【請求項２５】
通信ネットワーク中の品質劣化箇所の推定処理を行う品質劣化箇所推定システムであって、
前記通信ネットワークにおける複数の通信フローの各々が経由する個別フローリンクを示す情報を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、を有する管制装置と、
通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する複数の推定装置と、
前記通信ネットワークにおける通信フローの通信品質を測定し、予め定められた推定装置へ測定された通信品質情報を送信する複数の品質計測装置と、
を前記通信ネットワーク上に配置したことを特徴とする品質劣化箇所推定システム。
【請求項２６】
通信ネットワークにおける品質劣化箇所を推定する装置としてコンピュータを機能させるためのプログラムであって、
複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリングテーブル生成機能と、
前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類機能と、
前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する推定機能と、
を前記コンピュータに実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワーク上で通信品質の劣化が発生した箇所を推定するための技術に関する。
【背景技術】
【０００２】
通信ネットワークにおける通信品質の劣化は、ユーザが享受するサービス品質の低下を招く。たとえば、通信ネットワークを介して音声通話や映像配信を行う通信アプリケーションは、リアルタイム性を必要とする。そのため、わずかな通信品質の劣化でも、音飛びやノイズが発生し、サービス品質が低下する。従って、通信品質の劣化箇所を速やかに特定することが重要である。以下、通信障害その他の原因により通信品質の劣化が発生した箇所を「品質劣化箇所」と記す。
【０００３】
特許文献１には，IP(Internet Protocol)網における音声品質管理方法が開示されている。この方法では、IP網が複数のゲートウェイを介して電話網に接続される。各ゲートウェイは、音声品質管理情報(たとえば遅延時間)を収集し、その音声品質管理情報が所定の閾値を越えた場合、品質劣化をOSS(Operation Support System)に通知する。OSSは、各ゲートウェイからの通知とネットワークトポロジーに基づいて、品質劣化が発生している経路を表示し、複数の品質劣化経路が重なっている場合、その重なり区間を品質劣化被疑区間として表示する。
【０００４】
特許文献２には、ネットワーク中の品質劣化箇所を高精度に推定するための方法が開示されている。この方法では、まずネットワークの利用者が流しているフローの送信者アドレス、受信者アドレスおよび通信品質を含むフロー情報が収集される。またネットワークの構成情報が収集される。続いて、上記フロー情報および構成情報に基づいて、当該フローが経由するリンクが求められ、当該フローの品質劣化の有無が判定される。１以上のフローにおいて品質劣化が発生している場合、複数の品質劣化フローに共通するリンクおよび／または単独の品質劣化フローのみに対応するリンクを組み合わせることで全ての品質劣化フローをカバーするリンク集合のうち、最も要素数の少ないリンク集合の要素であるリンクを品質劣化箇所として推定する。このような手法は「最小リンク数推定方式」と呼ばれる。
【０００５】
非特許文献１には、品質劣化箇所の推定処理を大規模なネットワークに適用するための方法が開示されている。この方法では、まず大規模なネットワークを複数の部分ネットワークに分割し、各部分ネットワークの内部に閉じるフローによる部分的な品質劣化箇所の推定を行う。続いて、複数の部分ネットワークを跨って通過するフローのうち、前記フローの経路が部分ネットワーク内部で推定された品質劣化箇所を通過するフローと、部分ネットワーク内部に閉じるフローを組み合わせて再度品質劣化箇所の推定を行う。この方法では、部分ネットワークでの推定を並列処理することができ、大規模なネットワークで品質劣化箇所の推定を行うことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−２７１３９２号公報
【特許文献２】特開２００６−２３８０５２号公報
【非特許文献】
【０００７】
【非特許文献１】電子情報通信学会技術研究報告書 IN-2005-105「フロー品質からのネットワーク品質劣化箇所推定の網分割による大規模化手法の提案と評価」
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、大規模ネットワークでは多数の通信が発生しているため、通信の品質情報量が膨大となり、またネットワークに含まれる経路の数も膨大となる。そのため、大規模ネットワークに上述の特許文献１または特許文献２の技術を適用すると、品質劣化箇所の推定に長い時間を要するという課題があった。
【０００９】
また、大規模ネットワークに上述の非特許文献１の技術を適用した場合には、予めネットワークを複数に分割する必要があるため、ネットワーク中を流れる通信の状況に応じて適宜に効果的な分割法を考え、実行する必要がある。そのため、ネットワークの分割法が適当でない場合のように分割されたネットワークを跨ぐ通信が多く発生すると、大規模なネットワークの全通信の経路情報と品質情報をもって品質劣化箇所の推定処理が行われ、推定に要する時間が長くなるという課題が発生する。
【００１０】
そこで、本発明の目的は、大規模ネットワークにおいて品質劣化箇所の高速推定を可能にする品質劣化箇所推定方法、装置およびシステムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明による品質劣化箇所推定装置は、通信ネットワークにおける品質劣化箇所を推定する装置であって、複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する推定手段と、を有することを特徴とする。
【００１２】
本発明による品質劣化箇所推定方法は、通信ネットワークにおける品質劣化箇所を推定する方法であって、複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリングテーブル生成ステップと、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類ステップと、前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する推定ステップと、を有することを特徴とする。
【００１３】
本発明による品質劣化箇所推定システムは、通信ネットワーク中の品質劣化箇所の推定処理を行う品質劣化箇所推定システムであって、前記通信ネットワークにおける通信フローの通信品質を測定する少なくとも１つの品質計測装置と、前記品質計測装置から入力した複数の通信フローの通信品質情報と、前記通信ネットワークにおける各通信フローが経由する個別フローリンクを示す情報と、を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、を有する管制装置と、前記管制装置から受信した前記複数の通信フロー集合のうち、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する少なくとも１つの推定装置と、を前記通信ネットワーク上に配置したことを特徴とする。
【００１４】
本発明による品質劣化箇所推定システムは、通信ネットワーク中の品質劣化箇所の推定処理を行う品質劣化箇所推定システムであって、前記通信ネットワークにおける複数の通信フローの各々が経由する個別フローリンクを示す情報を含むフローリンクテーブルを生成するフローリンクテーブル生成手段と、前記フローリンクテーブルに基づいて前記複数の通信フローを複数の通信フロー集合に分類するフロー分類手段と、を有する管制装置と、通信品質の劣化を示す通信フローを含む通信フロー集合の個別フローリンクを示す情報に基づいて品質劣化箇所を推定する複数の推定装置と、前記通信ネットワークにおける通信フローの通信品質を測定し、予め定められた推定装置へ測定された通信品質情報を送信する複数の品質計測装置と、を前記通信ネットワーク上に配置したことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、大規模ネットワークにおいて品質劣化箇所の高速推定が可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１実施形態に係る品質劣化箇所推定装置を有する通信ネットワークシステムの一例を示す模式図である。
【図２】図１に示す通信ネットワークシステムにおけるリンク関係の一例を示す模式図である。
【図３】図１に示す通信ネットワークシステムにおける通信フローの一例を示す模式図である。
【図４】本発明の第１実施形態に係る品質劣化箇所推定装置の機能的構成の概略を示すブロック図である。
【図５】（Ａ）は本発明の第１実施形態に係る品質劣化箇所推定方法の手順を示すフローチャートであり、（Ｂ）はその符号間距離ソート処理を示すフローチャートである。
【図６】本発明の第１実施形態に係る品質劣化箇所推定装置において生成される、通信ネットワーク上でフローの通過したリンクを示すフローリンクテーブルの一例を示す図である。
【図７】（Ａ）は図６に示すフローリンクテーブルで符号間距離を計算した符号間距離テーブルの一例を示す図であり、（Ｂ）は、（Ａ）の符号間距離テーブルを符号間距離でソートした後の符号間距離テーブルの一例を示す図である。
【図８】図６に示すフローリンクテーブルを符号間距離でソートした後のフローリンクテーブルの一例を示す図である。
【図９】（Ａ）、（Ｂ）および（Ｃ）は、図９に示すフローリンクテーブルを分割した後の第１部分テーブル、第２部分テーブルおよび第３部分テーブルのそれぞれの一例を示す図である。
【図１０】（Ａ）は、図９（Ａ）に示す第１部分テーブルに対して非劣化除去処理を行った後の部分テーブルの一例を示す図であり、（Ｂ）は、図９（Ｃ）に示す第３部分テーブルに対して非劣化除去処理を行った後の部分テーブルの一例を示す図である。
【図１１】本発明の第２実施形態に係る品質劣化箇所推定装置の機能的構成の概略を示すブロック図である。
【図１２】本発明の第３実施形態に係る品質劣化箇所推定システムの概略的構成図である。
【図１３】本発明の第４実施形態に係る品質劣化箇所推定システムの動作を説明するためのシステム構成図である。
【図１４】本発明の第５実施形態に係る品質劣化箇所推定装置の機能的構成の概略を示すブロック図である。
【図１５】図１４に示す品質劣化箇所推定装置の処理手順を示すフローチャートである。
【図１６】図１４に示すリンク距離テーブルの一例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明を実施するための形態について図面を参照して詳細に説明する。なお、本発明は、以下に述べる実施形態により限定されるものではない。
【００１８】
１．第１実施形態
１．１）通信ネットワークシステム
図１を用いて、本発明の第１実施形態に係る通信ネットワークシステムの概略構成について説明する。一例として、図１に示すように、通信ネットワーク100は、複数の端末T1-1〜T1-8、T2-1〜T2-8、T3-1〜T3-7、複数のルータR1-1〜R1-5、R2-1〜R2-7、R3-1〜R3-4、および品質劣化箇所推定装置Ｓ１が接続された構成を有するものとする。各端末は通信ネットワークを介して互いに通信可能である。なお、ルータの代わりにスイッチが用いられてもよい。以下、ルータあるいはスイッチを単に「ノード」と呼ぶ場合もある。
【００１９】
また、図２に示すように、あるノードと隣のノードとの間の区間を「リンク」と称し、ここでは双方向リンクの各方向が区別され、それぞれの方向のリンクにリンクIDが割り当てられているものとする。
【００２０】
図３は通信ネットワーク100における通信フローF1〜F11を示したものである。ここで、通信フローとは、送信元と送信先とで規定される通信のことであり、具体的には送信元および送信先のIPアドレス、送信元および送信先のPort番号およびプロトコルIDで規定される。たとえば、通信フローF1は送信端末T1-1から受信端末T2-8への通信であり、その経路は「T1-1 → R1-2 → R1-1 → R2-1 → R2-3 → R2-7 → T2-8」となる。同様に、通信フローF2〜F11は破線で示された経路の通信をそれぞれ示している。
【００２１】
品質劣化箇所推定装置S1は、通信端末間の複数の通信経路を示す経路情報と、通信端末間の通信フローの通信品質を計測して作成した計測情報とに基づき、通信ネットワーク中の品質劣化箇所を推定する機能を有する。品質劣化箇所推定装置S1の機能の詳細については後述する。
【００２２】
経路情報は、品質劣化推定装置S1により作成されてもよいし、通信ネットワーク中に別個に設けられた経路情報作成装置によって作成されてもよい。ただし、経路情報作成装置で作成された経路情報は品質劣化推定装置S1に送信される。あるいは、経路情報は、ネットワーク管理者によって直接、品質劣化推定装置S1に与えられてもよい。いずれの場合であっても、品質劣化箇所推定装置S1は、経路情報を取得することができる。
【００２３】
また、計測情報は、例えば端末が通信ネットワーク中を流れる通信フローの品質を計測することにより作成される。この場合、端末は、作成した計測情報を品質劣化推定装置S1に送信する。あるいは、通信ネットワーク中に品質計測装置を別途設けてフロー品質の計測情報が作成されてもよい。この場合も、品質計測装置は、作成した計測情報を品質劣化推定装置S1へ送信する。
【００２４】
品質計測装置を用いた計測手法には、ルータなどを計測点としミラーポートを用いて計測する手法、ルータなどに実装されているsFlowなどを利用する手法、また通信経路上の計測点にネットワークタップなどを導入し計測する手法などの複数の手法があり、いずれの手法を用いてもよい。 上述した計測情報は、フローレポート識別情報、送信元/送信先端末に関連する情報、計測に関連する情報、および計測された通信品質に関連する情報を含む。送信元/送信先端末に関連する情報とは、送信元/送信先端末のIPアドレス、MACアドレス、PORT番号などである。計測に関連する情報とは、計測地点でのパケットロス率、パケットロスのバースト性、受信レート、遅延ジッタ、伝送遅延時間、R値、品質フラグ(劣化，良好，不定)などである。なお、R値は、パケットロス率、遅延ジッタなどからITU-T勧告のG.107のE-Modelに従って求められる。
【００２５】
１．２）品質劣化箇所推定装置
図４に示すように、品質劣化箇所推定装置S1は、通信装置10、処理装置20、記憶装置30、および表示装置40を備えており、通信装置10を通して通信ネットワークに接続している。処理装置20は、入力部201，フローリンクテーブル作成部202、符号間距離ソート部203、フロー分類部204、品質劣化箇所推定部205、および品質劣化箇所通知部206のそれぞれの機能を実現する。記憶装置30はRAM(Random Access Memory)であり、半導体記憶装置、HDD(Hard Disk Drive)あるいはSSD(Solid State Drive)などのハードウエアから構成される。記憶装置30には、後述するように、経路情報301、計測情報302、フローリンクテーブル303、符号間距離テーブル304、部分テーブル305、および推定箇所情報306などの情報が格納される。表示装置40は、処理装置20からの指示により品質劣化箇所の情報などを表示する。
【００２６】
処理装置20は中央処理装置（CPU)等のプログラム制御プロセッサであり、コンピュータプログラム(品質劣化箇所推定プログラム)を実行することにより、品質劣化箇所推定処理を行う。例えば、品質劣化箇所推定プログラムは、コンピュータ読み取り可能な記録媒体に格納されており、処理装置20は、その記録媒体から品質劣化箇所推定プログラムを読み出し実行する。あるいは、品質劣化箇所推定プログラムは、ネットワークを介して提供されてもよい。
【００２７】
処理装置20は、次のような機能的構成を有する。入力部201は、通信装置10を介して経路情報301および各通信フローの品質劣化の有無などを示す計測情報302を受取り、これらの情報を記憶装置30に格納する。
【００２８】
フローリンクテーブル作成部202は、入力部201から計測情報および経路情報を受け取り、通信フローと当該通信フローが経由したリンクとの関係をマトリックスで通信フローの品質劣化の有無と共に示したフローリンクテーブル303を作成して記憶装置30に格納する。
【００２９】
符号間距離ソート部203は、記録装置30から読み出したフローリンクテーブル303から通信フロー間の符号間距離を計算して符号間距離テーブル304を生成し、さらに、符号間距離テーブル304をソートすることでソートされたフローリンクテーブルを記憶装置30に格納する。なお、通信フロー間の符号間距離は次のように求める。まず、全ての通信フロー（ここではF1〜F11）の経由リンク情報を符号化した個別フローリンク情報を作成する。個別フローリンク情報は、ネットワーク中の全リンクを一定の順序で配列し、１つの通信フローが経由するリンクを「１」、経由しないリンクを「０」としたときの０／１の列で定義することができる。たとえば、４つのリンクL1-L4からなるネットワークでリンクL1およびL3のみを経由する通信フローの個別フローリンク情報は、リンクL1,L2,L3,L4の順で配列した場合、「1010」と表すことができる。こうして、通信フロー間の符号間距離は、全ての通信フロー間で、個別フローリンク情報のたとえばハミング距離を計算することで求められる。
【００３０】
フロー分類部204は、ソートされたフローリンクテーブルを記憶装置30から読み出して、予め設定された部分テーブル数に基づき、フローリンクテーブルに並んでいる通信フローの順に分割することで複数の部分テーブル305を作成し記憶装置30に格納する。
【００３１】
品質劣化箇所推定部205は、フローリンクテーブルと部分テーブルを記憶装置30から読出して、前記計測情報が通信品質劣化を示す通信フローを含む部分テーブルを選択し、当該部分テーブルから後述するように品質劣化箇所を推定し、その推定箇所情報306を記憶装置30に格納する。
【００３２】
品質劣化箇所通知部206は、記憶装置30から推定箇所情報306を読み出し、その推定箇所情報を表示装置40に表示させる。この時の表示内容として、品質劣化箇所のアドレスなどをテキスト形式で表示してもよいし、品質劣化箇所の位置をネットワーク上でグラフィカルに表示してもよい。運用管理者は表示装置40に表示される情報を参照して、対策を講じることができる。
【００３３】
１．３）品質劣化箇所推定方法
次に、図５〜図１０を参照しながら、図４の品質劣化箇所推定装置で実行する品質劣化箇所推定処理について説明する。ここでは、図２に示したリンクIDを用い、リンクL2-3およびL3-8において品質劣化が発生していると仮定する。なお、計測情報は、端末T1-1〜T1-8、T2-1〜T2-8、T3-1〜T3-7の各々から品質劣化箇所推定装置S1へ送信される。以下、図５（Ａ）に示すフローチャートにおけるステップS401-S409、図５（Ｂ）に示すフローチャートのステップS403.1−S403.3に従って、適宜、図６〜図１０を参照しながら説明する。
【００３４】
(ステップS401)
ステップS401では、入力部201が計測情報および経路情報を取得し記憶装置30に格納する。また、入力部201は、受取った計測情報および経路情報をフローリンクテーブル作成部202に出力する。
【００３５】
(ステップS402)
ステップS402では、フローリンクテーブル作成部202が、入力部201から経路情報301および計測情報302を受け取り、それらに基づいてフローリンクテーブル303を作成する。具体的には、フローリンクテーブル作成部202は、品質の計測情報がある通信フローが経由したリンクIDを経路情報から求める。そして求めたリンクIDを通過リンクとして保持し、フローリンクテーブル303に格納する。フローリンクテーブル303では、各通信フローが通過するリンクIDに「1」が記入され、通過しなかったリンクIDには何も記入されないか、または「0」が記入され、さらに各通信フローの品質劣化の有無が記入される。図６にフローリンクテーブル303の一例を示す。たとえば、通信フローF1は、リンクID「L0-1，L1-1，L1-17，L2-3，L2-19，L2-27」を経由しているので、該当するリンクIDのフィールドに通過を示す「1」が書き込まれている。
【００３６】
(ステップS403：符号間距離ソート)
ステップS403では、符号間距離ソート部203が、フローリンクテーブル303を通信フロー間の符号間距離に基づきソートする。まず、符号間距離ソート部203は、フローリンクテーブル303を記録装置30から読み出し、全ての通信フロー間でフローリンクテーブル同士の符号間距離を計算し、その符号間距離を符号間距離テーブル304に保持する。上述した通信フローの符号の定義により、図６に示すフローリンクテーブルにおける各通信フローの個別フローリンク情報の０／１の列が当該通信フローの符号となる。ここでは、２つの通信フロー間の符号間距離がそれぞれ対応するリンクIDの０／１値の不一致個数として定義される。図７（Ａ）に、本実施形態において作成された符号間距離テーブルの一例を示す。
【００３７】
（ステップS403.1）
次に、符号間距離ソート部203は、この符号間距離テーブル304を用いて符号間距離が最大となる通信フローのペアを１つ選択する。図７（Ａ）に示した符号間距離テーブルの例では、符号間距離が最大となる通信フローのペアはF2-F7とF2-F8である。符号間距離が最大となるペアが複数存在する場合にはただ一つだけを選択する。ここでは、ペアの通信フローIDが小さい方を選択するというポリシーを適用し、F2-F7を選択するものとする。
【００３８】
（ステップS403.2）
次に、符号間距離ソート部203は、全ての通信フローF1-F11について、上記符号間距離が最大となる通信フローのペアのうち一方からの符号間距離を最優先キーとして、フローリンクテーブル内の通信フローの並びをソートする。なお、最優先キーで符号間距離が同じ通信フローが発生した場合には、選択された通信フローのペアのうち最優先キーとして選択しなかった方を第２優先キーとして、フローリンクテーブル内の通信フローの並びを逆順ソートする。例えば、通信フローIDが大きい方を最優先キーとして選択することとすると、ペアとしてF2-F7を選択していた場合にはF7との符号間距離が最優先キー、F2との符号間距離が第２優先キーとなる。図７（Ｂ）に、通信フローF7との符号間距離を最優先キーとし、通信フローF2との符号間距離を第２優先キーとしてソートした場合のソート後の符号間距離テーブルの一例を示す。
【００３９】
（ステップS403.3）
次に、符号間距離ソート部203は、ソート後の符号間距離テーブルに従って、図６に示すフローリンクテーブルをソートする。図８に示すソート後のフローリンクテーブルは、図７（Ｂ）に示した通信フローのソート順序を図６のフローリンクテーブルに反映した結果である。言い換えれば、図８に示すソート後のフローリンクテーブルは、符号間距離が最も離れた通信フローのペアF2とF7とを両端とし、その間に符号間距離に応じて他の通信フローを配置したものであり、ソート後のフローリンクテーブルにおける２つのフローの位置が近いか離れているかは経由リンクの類似性を反映している。
【００４０】
(ステップS404：フローリンクテーブル分割)
ステップS404では、フロー分類部204が通信フローを部分集合に分類する。まずフロー分類部204は、符号間距離ソート部203によりソートされたフローリンクテーブルを記憶装置30から読み出す。フロー分類部204は、全ての通信フローの集合を、複数の部分集合へ分類し、部分テーブルを記憶装置30に格納する。ここでは、ソート後のフローリンクテーブルに含まれるフローの本数と運用者が指定した部分テーブル数から、部分テーブル毎のフロー本数ができるだけ均等になるように重複無く部分テーブル毎のフローの本数を決定する。そして決定した本数分の通信フローをソート後のフローリンクテーブルに並んでいる順で各部分テーブルに割り当てる。例えば、フローリンクテーブルに含まれるフロー本数が１２本で、部分テーブル数が３の場合には、１番目の部分テーブルにフロー本数を４本、２番目の部分テーブルにフロー本数を４本、３番目の部分にフロー本数を４本と振り分ける。割り切れない場合には最初のテーブルから順にフローの本数を増やしていく。例えば、フロー本数が１３本で部分テーブル数が３の場合には、１番目の部分テーブルにフロー本数を５本、２番目の部分テーブルにフロー本数を４本、３番目の部分テーブルにフロー本数を４本と振り分ける。
【００４１】
図９（Ａ）〜（Ｃ）に、上述した手順を用いて図８のフローリンクテーブルを分割した後の部分テーブルの一例を示す。図９（Ａ）は、１番目の部分テーブルに通信フローF7,F8,F1,F4を振り分けて作成した部分テーブル１である。図９（Ｂ）は、２番目の部分テーブルに通信フローF5,F9,F11,F3を振り分けて作成した部分テーブル２である。図９（Ｃ）は、３番目の部分テーブルに通信フローF6,F10,F2を振り分けて作成した部分テーブル３である。なお、部分テーブル数は運用者が直接指定してもよいし、フローリンクテーブルに含まれる通信フローの本数を考慮してフロー分類部204が決定してもよい。
【００４２】
（ステップS405-S408：品質劣化箇所推定）
ステップS405-S408では、品質劣化箇所推定部205が記憶装置30のフローリンクテーブル303と部分テーブル305とを読み出し、それらを組み合わせることによって通信ネットワーク上の品質劣化箇所を推定する。
【００４３】
品質劣化箇所推定部205はフローリンクテーブル303を参照し、フロー品質が「劣化」である通信フローが存在するかどうかチェックする(ステップS405)。もし、劣化区間が一つも存在しない場合、すなわち、全ての通信フロー品質が「良好」もしくは「不定」である場合（ステップS405:No)、品質劣化箇所推定部205は品質劣化箇所が存在しないと判断し、推定処理を終了させる。
【００４４】
一方、一つ以上の通信フロー品質の劣化が存在する場合（ステップS405:Yes)、品質劣化箇所推定部205はフローリンクテーブル303を参照し、通信フロー品質が「劣化」であるフローが含まれる部分テーブルを検索し（ステップS406)、後述するように、「劣化」フローを含む部分テーブルを用いて品質劣化箇所の推定を行い、推定箇所情報306を記憶装置30に格納する（ステップS407)。他に「劣化」フローが含まれる部分テーブルが残っていれば（ステップS408：Yes）、ステップS407へ戻って、残った部分テーブルに対し同様に品質劣化箇所の推定を行っていく。
【００４５】
(ステップS409)
他に通信フロー品質が「劣化」であるフローが含まれる部分テーブルが残っていなければ（ステップS408：No）、ステップS409において、品質劣化箇所通知部206が記憶装置30から推定箇所情報306を読み出し、その推定箇所情報を表示装置40で表示させる。表示形式としては、品質劣化箇所のアドレスなどをテキスト形式で表示してもよいし、品質劣化箇所の位置をネットワーク表示上でグラフィカルに表示しても良い。運用管理者は表示装置40に表示される情報を参照して、対策を講じることができる。
【００４６】
１．４）品質劣化箇所推定の具体例
図を用いてさらに具体的に説明する。本実施形態では、上述したように、リンクID＝L2-3およびL3-8において品質劣化が発生している。したがって、これらのリンクL2-3およびL3-8を通過するフローF1,F2,F7,F8,F10の品質が「劣化」、これら以外のフローの品質が「良好」であると記憶装置30の計測情報302に記憶されている。
【００４７】
品質劣化箇所推定部205はフローリンクテーブル303を参照することでフロー品質が「劣化」であるフローを探す。ここではフローF1,F2,F7,F8,F10のフロー品質が「劣化」であるから、品質劣化箇所推定部205は、図９に示す部分テーブル１−３のうち、「劣化」フローF1,F2,F7,F8,F10が含まれる部分テーブル１および部分テーブル３を順次選択し、選択された部分テーブルに対して次のように品質劣化箇所推定を行う。
【００４８】
まず、図９（Ａ）に示す部分テーブル１からフロー品質が「良好」であるフロー（ここでは、F4）の通過するリンクL1-6およびL1-7を除去することで、図１０（Ａ）に示す非劣化除去後の部分テーブル１を得る。この非劣化除去後の部分テーブル１において、全ての品質劣化フローF7,F8およびF1をカバーするリンク集合としては、たとえば｛L2-2, L1-17｝、｛L2-3｝、｛L2-8, L2-19｝など多数存在するが、この中で最も要素数の少ないリンク集合は｛L2-3｝である。従って、その要素であるリンクL2-3を品質劣化箇所として推定する。
【００４９】
同様に、図９（Ｃ）に示す部分テーブル３からフロー品質が「良好」であるフロー（ここでは、F6）の通過するリンクL1-9,L1-13,L1-22,L1-27を除去することで、図１０（Ｂ）に示す非劣化除去後の部分テーブル３を得る。この非劣化除去後の部分テーブル３において、全ての品質劣化フローF10およびF2をカバーするリンク集合としては、たとえば｛L3-2, L1-17｝、｛L3-8｝、｛L3-22, L3-24｝など多数存在するが、この中で最も要素数の少ないリンク集合は｛L3-8｝である。従って、その要素であるリンクL3-8を品質劣化箇所として推定する。
【００５０】
このような手順により、品質劣化箇所推定部205は品質劣化箇所L2-3およびL3-8を推定箇所情報として記憶装置30に格納する。すなわち、当初仮定した品質劣化箇所リンクL2-3およびL3-8が正しく推定されていることが分かる。
【００５１】
１．５）効果
上述したように、本実施形態によれば、小規模な部分テーブルで品質劣化箇所の推定処理を行うことができるので推定処理にかかる計算量を減らすことができる。さらに、通信フロー間の符号間距離を考慮することにより、フローリンクテーブルを推定精度を維持したまま複数の部分テーブルに分割することができ、大規模な通信ネットワークにおける品質劣化箇所の推定処理を高速かつ高精度に行うことが可能となる。
【００５２】
２．第２実施形態
図１１を用いて、本発明の第２実施形態に係る品質劣化箇所推定装置の概略構成について説明する。本実施形態では、管制装置50、複数の推定装置60および全体的な制御を行う制御部70を有する。
【００５３】
管制装置50は、入力部201、フローリンクテーブル作成部202、符号間距離ソート部203およびフロー分類部204を機能的に備えており、これらは図４に示す第１実施形態の対応するブロックと同様である。複数の推定装置60の各々は、品質劣化箇所推定部205および品質劣化箇所通知部206を機能的に備えており、これらも図４に示す第１実施形態の対応するブロックと同様である。また、通信装置10、記憶装置30および表示装置40も図4に示す第１実施形態で説明した通りである。したがって、これらのブロックの構成および機能については図４と同一の参照番号を付して説明は省略する。
【００５４】
本実施形態では、複数の推定装置60を用意している点が第１実施形態と異なる。一つの品質劣化箇所推定装置内に複数実装されてもよいし、または推定装置を有する複数の品質劣化箇所推定装置を用意してもよい。いずれにしても、制御部70は、複数の推定装置60を用いて上述した品質劣化箇所推定処理を部分テーブル毎に実行する。その際、複数の推定装置60による並列処理が可能となるので、システム全体の処理能力を向上させることができる。また、一つの装置による処理であってもマルチコアなどのCPUを有することにより、装置内で推定処理を同時に実行することができシステム全体の処理能力を向上させることができる。
【００５５】
３．第３実施形態
図１１に示す品質劣化箇所推定装置における管制装置50および複数の推定装置60は、通信ネットワーク上に別個の装置として設けることもできる。図１２に本発明の第３実施形態による品質劣化箇所推定システムの一例を示す。
【００５６】
図１２に示すように、管制装置50、複数の推定装置60および品質劣化箇所推定制御装置80と、１以上の品質計測装置90とがそれぞれ通信ネットワーク100に接続され、図１１に示す品質劣化箇所推定装置と同様の機能を有する品質劣化箇所推定システムを構成する。ここでは、品質劣化箇所推定制御装置80が図１１の記憶装置30、表示装置40および制御部70と同等の機能を有するものとする。また、品質計測装置90はフロー品質情報を品質劣化箇所推定制御装置80へ送信する。
【００５７】
管制装置50および複数の推定装置60の動作は、通信ネットワーク100を通してデータの送受信を行う点を除けば、上述した第２実施形態と同様であるから説明は省略する。このようなシステム構成により、複数の推定装置60による並列処理が可能となるので、システム全体の処理能力を向上させることができる。
【００５８】
４．第４実施形態
本発明の第４実施形態による品質劣化箇所推定システムでは、図１２に示すシステム構成と基本的に同じであるが、品質劣化箇所推定制御装置80の記憶装置30には部分テーブル305が格納されていない。本実施形態によれば、管制装置50のフロー分類部204がフローの分類結果を品質計測装置90に通知し、品質計測装置90が予め決められた推定装置60へフロー計測情報を送信する。
【００５９】
具体的には、図１３に示すように、管制装置50のフロー分類部204がフローの分類結果を品質計測装置90に通知すると、品質計測装置90はフロー分類結果に基づいて推定に使用する推定装置を決定する。そして、品質計測装置90がフロー品質を計測すると、決定された推定装置にフロー品質情報を通知し、当該推定装置が品質劣化箇所の推定処理を行う。フロー分類部204から品質計測装置90に与える情報は、フロー分類結果だけではなく、推定装置のIDを直接通知してもよい。本実施形態によれば、一度フローの分類を決定すると品質計測装置から推定装置へ直接フロー品質情報を通知することが可能となるため、システム全体の処理能力を向上させることができる。
【００６０】
５．第５実施形態
本発明の第５実施形態による品質劣化箇所推定装置S1は、フロー分類部204が経由リンクの一致度を考慮した分類を行う点で第１実施形態と異なる。
【００６１】
図１４に示すように、本実施形態による品質劣化箇所推定装置S1は、図４に示す第１実施形態による品質劣化箇所推定装置と次のような構成上の相違点を有する。すなわち、処理装置２０には、図４の符号間距離ソート部203およびフロー分類部204の代わりに、共通リンク数計算部210およびフロー分類部211が設けられ、記憶装置３０には、図４の符号間距離テーブル304の代わりに、リンク距離テーブル310が設けられている。その他の構成は、第１実施形態と同じであるから、同一の参照番号を付して説明は省略する。
【００６２】
共通リンク数計算部210は、フローリンクテーブル作成部202で作成したフローリンクテーブル303に基づいて通信フロー間で共通の経由リンク数を計算し、通信フロー間の共通リンク数をマトリックスで示したリンク距離テーブル310を作成する。
【００６３】
図１５に示すように、本実施形態による品質劣化箇所推定装置S1は、図５（Ａ）に示す第１実施形態による品質劣化箇所推定方法と次のような相違点を有する。すなわち、図５（Ａ）の符号間距離ソートステップS403およびフローリングテーブル分割ステップS404の代わりに、共通リンク数カウントステップS500およびフローリングテーブル分割ステップS501が設けられている。ステップS500-S501、S404-S409以外のステップについては第１実施形態と同様であるから、以下、図1５におけるステップS500-S501、S404-S409についてのみ説明する。
【００６４】
(ステップS500) 
ステップS500では、フローリンクテーブル303をフロー間の経由リンクの一致数をカウントする。まず、共通リンク数計算部210は、フローリンクテーブル303を記録装置30から読み出す。そして共通リンク数計算部210は、フローリンクテーブル303を用いて、全ての通信フローペアの各々で共通のリンク数をカウントし、リンク距離テーブル310を生成する。図１６は通信フローF1〜F11間の共通リンク数を計算したリンク距離テーブルの一例を示している。
【００６５】
(ステップS501)
ステップS501では、フロー分類部211がフローを部分集合に分類する、まずフロー分類部211は、共通リンク数計算部210が生成したリンク距離テーブル310を記憶装置30から読み出す。フロー分類部210は、各通信フローについて共通リンク数が設定した閾値以上となる通信フローを集めて部分集合へ分類し、部分テーブル305を記憶装置30に格納する。例えば、閾値を”2”とすれば、図１６に示したリンク距離テーブル310に従って、通信フローF1,F7,F8が一つの部分テーブルに格納される。
【００６６】
(ステップS405-S409)
まず、ステップS405-S408では、品質劣化箇所推定部205が記憶装置30のフローリンクテーブル303と部分テーブル305とを読み出し、それらを組み合わせることによって通信ネットワーク上の品質劣化箇所を推定する。
【００６７】
品質劣化箇所推定部205はフローリンクテーブル303を参照し、フロー品質が「劣化」である通信フローが存在するかどうかチェックする(ステップS405)。もし、劣化区間が一つも存在しない場合、すなわち、全ての通信フロー品質が「良好」もしくは「不定」である場合（ステップS405:No)、品質劣化箇所推定部205は品質劣化箇所が存在しないと判断し、推定処理を終了させる。
【００６８】
一方、一つ以上の通信フロー品質の劣化が存在する場合（ステップS405:Yes)、品質劣化箇所推定部205はフローリンクテーブル303を参照し、通信フロー品質が「劣化」であるフローが含まれる部分テーブルを検索し（ステップS406)、「劣化」フローを含む部分テーブルを用いて品質劣化箇所の推定を行い、推定箇所情報306を記憶装置30に格納する（ステップS407)。他に「劣化」フローが含まれる部分テーブルが残っていれば（ステップS408：Yes）、ステップS407へ戻って、残った部分テーブルに対し同様に品質劣化箇所の推定を行っていく。
【００６９】
他に通信フロー品質が「劣化」であるフローが含まれる部分テーブルが残っていなければ（ステップS408：No）、ステップS409において、品質劣化箇所通知部206が記憶装置30から推定箇所情報306を読み出し、その推定箇所情報を表示装置40で表示させる。表示形式としては、品質劣化箇所のアドレスなどをテキスト形式で表示してもよいし、品質劣化箇所の位置をネットワーク表示上でグラフィカルに表示しても良い。運用管理者は表示装置40に表示される情報を参照して、対策を講じることができる。
【００７０】
本実施形態によれば、実際に経由した共通のリンクが多いフローを集めて推定処理を行うため、共通リンクがないフロー情報を部分集合から排除することができ、推定処理にかかる計算量を減らすことができる。
【産業上の利用可能性】
【００７１】
本発明は、通信ネットワーク上で通信障害の発生箇所または通信品質の劣化箇所を推定する装置に適用可能である。
【符号の説明】
【００７２】
Ｒ１−１〜５  ルータ
Ｒ２−１〜７  ルータ
Ｒ３−１〜４  ルータ
Ｔ１−１〜８  端末
Ｔ２−１〜８  端末
Ｔ３−１〜７  端末
Ｓ１  品質劣化箇所推定装置
１０  通信装置
２０  処理装置
３０  記憶装置
４０  表示装置
５０  管制装置
６０  推定装置
７０  制御部
８０  品質劣化箇所管理装置
１００  通信ネットワーク
２０１  入力部
２０２  フローリングテーブル作成部
２０３  符号間距離ソート部
２０４  フロー分類部
２０５  品質劣化箇所推定部
２０６  品質劣化箇所通知部
２１０  共通リンク崇敬三部
２１１  フロー分類部
３０１  経路情報
３０２  計測情報
３０３  フローリンクテーブル
３０４  符号間距離テーブル
３０５  部分テーブル
３０６  推定箇所情報
３１０  リンク距離テーブル
【図１】
2011041043.tif 000003
【図２】
2011041043.tif 000004
【図３】
2011041043.tif 000005
【図４】
2011041043.tif 000006
【図５】
2011041043.tif 000007
【図６】
2011041043.tif 000008
【図７】
2011041043.tif 000009
【図８】
2011041043.tif 000010
【図９】
2011041043.tif 000011
【図１０】
2011041043.tif 000012
【図１１】
2011041043.tif 000013
【図１２】
2011041043.tif 000014
【図１３】
2011041043.tif 000015
【図１４】
2011041043.tif 000016
【図１５】
2011041043.tif 000017
【図１６】
2011041043.tif 000018