JP4244940B2 - ネットワークの品質劣化箇所推定装置、品質劣化箇所推定方法及び品質劣化箇所推定プログラム - Google Patents

Description

本発明は、通信ネットワークシステムに関し、特に通信品質の劣化箇所を推定する品質劣化箇所推定装置等に関する。

従来、通信ネットワークにおいて、通信品質劣化時に、次のようにして、高速に通信品質劣化箇所を特定していた。すなわち、ネットワーク内に監視装置を多数配備し、配備した位置での通信品質を常に監視しておき、通信品質劣化時に、品質劣化の起こっている監視装置の位置に基づき、品質劣化している区間を推定していた。この方法では、品質劣化している位置の推定精度を高めるに、多数の監視装置が必要となるので、その配置コストが高いという問題がある。

特許文献１記載の品質劣化箇所推定方法では、ネットワーク利用者の通信フローの品質情報とネットワークトポロジとから、品質劣化したフローの経路を求め、複数の品質劣化したフローが共有する経路区間を特定し、品質劣化箇所として推定する。

例えば、図２４に示した、ルータ（又はパケットスイッチ）Ｒ１〜Ｒ６、端末Ｔ１〜Ｔ６が接続されたネットワークにおいて、利用者のフローＦ１及びフローＦ２が流れており、経路Ｒ１→Ｒ２において品質劣化が起こっているとする。この場合、フローＦ１及びＦ２が品質劣化する。従来の品質劣化箇所推定方法では、これらの品質劣化したフローＦ１、Ｆ２が共有している経路区間であるＲ１→Ｒ２を、品質劣化箇所として正しく推定する。

特開２００２−２７１３９２号公報「ＩＰ網における呼毎の音声品質管理方法」

しかし、この方法は、品質劣化したフローの経路が類似していて、多数の共有する経路区間がある場合に、それらを全て品質劣化箇所として推定してしまうので推定精度が悪い、及び、複数の品質劣化箇所がある場合に誤った区間を品質劣化箇所として推定してしまう、という問題がある。

例えば、図２５に示した、ルータ（又はパケットスイッチ）Ｒ１〜Ｒ６、端末Ｔ１〜Ｔ７が接続されたネットワークにおいて、利用者のフローＦ１及びフローＦ２が流れており、経路Ｒ１→Ｒ２において品質劣化が起こっているとする。この場合、フローＦ１及びＦ２が品質劣化するが、従来の品質劣化箇所推定方法では、これらの品質劣化したフローＦ１、Ｆ２が共有している全ての経路区間である、Ｒ１→Ｒ２、Ｒ２→Ｒ３、及び、Ｒ３→Ｒ４を品質劣化の疑いがある区間として示す。この示された内容は、実際の品質劣化区間より広く、推定精度が低い。

同じネットワーク構成での別な例として、図２６のようにフローＦ１〜Ｆ４が流れていたとし、経路Ｒ１→Ｒ２、及び経路Ｒ３→Ｒ４において品質劣化が発生していたとする。この場合、フローＦ１、Ｆ２、Ｆ３、Ｆ４の品質が劣化する。このとき、品質劣化したフローＦ１、Ｆ２、Ｆ３、Ｆ４の全てが共有している経路区間はない。また、２つ以上のフローが共有している経路区間は、Ｒ１→Ｒ２、Ｒ２→Ｒ３、及び、Ｒ３→Ｒ４である。従来の品質推定方法では、共有している経路を品質劣化区間と推定するため、「品質劣化の疑いのある区間はない」又は「Ｒ１→Ｒ２、Ｒ２→Ｒ３、及び、Ｒ３→Ｒ４が品質劣化の疑いのある区間である」という結果になる。しかし、実際に品質劣化が発生した区間は、経路Ｒ１→Ｒ２、及び経路Ｒ３→Ｒ４であるため、前者は誤った推定結果となり、後者は精度が悪い推定結果となる。

そこで、本発明の目的は、フロー品質情報に基づいて、品質劣化箇所を精度高く推定することにある。また、本発明の別な目的は、品質劣化箇所を高速に推定することにある。

本発明に係る第一の品質劣化箇所推定装置は、ネットワーク利用者が流しているフローの送信者アドレスと受信者アドレスと通信品質とから成るフロー品質情報を収集するフロー品質収集手段と、ネットワークの構成情報を集める経路情報収集手段と、前記フロー品質情報及びネットワークの構成情報から前記フローが経由するリンクを求め、品質の劣化の有無を判定し、それらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理手段と、前記テーブルにおいて、１つ以上フローの品質の劣化があった場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段と、を有する。

品質劣化箇所推定手段は、現在が通信中のフローが経由している全てのリンクについて、現在の通信品質劣化を起こし得る、あらゆる品質劣化したリンクの組み合わせのうち、最小のリンク数からなる組み合わせを品質劣化箇所として出力する。ネットワークの各リンクが品質劣化の原因となる確率が等しく、互いに独立である、という妥当な仮定の基において、この出力は、現在の通信品質劣化を起こしている最も発生確率が高い品質劣化箇所である。このため、フロー品質情報に基づいて、精度高く推定することを実現している。

本発明に係る第二の品質劣化箇所推定装置は、ネットワーク利用者が流しているフローの送信者アドレスと受信者アドレスと通信品質とから成るフロー品質情報を収集するフロー品質収集手段と、ネットワークの構成情報を集める経路情報収集手段と、前記フロー品質情報及びネットワークの構成情報から前記フローが経由するリンクを求め、品質の劣化の有無を判定し、それらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理手段と、ネットワークの各リンクについて過去の品質劣化原因となった確率を記憶しておくリンク品質劣化確率記憶手段と、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最も発生確率が高いと推定される部分集合を前記確率を用いて決定し、決定した部分集合を品質劣化箇所として出力することを特徴とする、品質劣化箇所推定手段と、を有する。

品質劣化箇所推定手段は、現在が通信中のフローが経由している全てのリンクについて、現在の通信品質劣化を起こし得る、あらゆる品質劣化したリンクの組み合わせのうち、過去の各リンクが品質劣化原因となった確率に基づいて、最も高い確率となる組み合わせを品質劣化箇所として出力する。ネットワークの各リンクが品質劣化の原因となる確率が互いに大きく異なる場合でも、フロー品質情報に基づいて、精度高く推定することが実現している。

本発明に係る第三の品質劣化箇所推定装置は、本発明に係る第一の品質劣化箇所推定装置において、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合から、品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する、品質劣化箇所推定手段を有する。

品質劣化箇所推定手段は、現在が通信中のフローが経由している全てのリンクから、品質良好なフローが経由するリンクを除外した後で、本発明に係る第一の品質劣化箇所推定装置の品質劣化箇所推定手段と同じ方法によって、品質劣化箇所を推定している。品質良好なフローが経由するリンクを除外することにより、品質劣化の可能性のあるリンクの組み合わせ数を減らすことができ、推定精度を高めることを実現すると共に、品質劣化箇所の推定の高速化を実現している。

本発明に係る第四の品質劣化箇所推定装置は、本発明に係る第二の品質劣化箇所推定装置において、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、過去の品質劣化原因となった確率から最も発生確率が高いと推定される部分集合を、品質劣化箇所として出力する、品質劣化箇所推定手段を有する。

品質劣化箇所推定手段は、現在が通信中のフローが経由している全てのリンクから、品質良好なフローが経由するリンクを除外した後で、本発明に係る第二の品質劣化箇所推定装置の品質劣化箇所推定手段と同じ方法によって、品質劣化箇所を推定している。品質良好なフローが経由するリンクを除外することにより、品質劣化の可能性のあるリンクの組み合わせ数を減らすことができ、推定精度を高めることを実現すると共に、品質劣化古書の推定の高速化を実現している。

本発明に係る第五の品質劣化箇所推定装置は、ネットワーク利用者及び試験フローの送信者アドレスと受信者アドレスと通信品質とから成るフロー品質情報を収集し、かつ、ネットワーク端末に試験フローの発生と停止を指示するフロー品質収集手段と、ネットワークの構成情報を集める経路情報収集手段と、前記フロー品質情報及びネットワークの構成情報から前記フローが経由するリンクを求め、品質の劣化の有無を判定し、それらをテーブル形式で管理しておくと共に、ネットワーク利用者のフローの経路に依存して試験フローを流す経路を決定するフロー品質／経由リンクテーブル管理手段と、１つ以上フローの品質の劣化を検知した場合、質劣化を起こした任意のフローの集合が経由するリンクの集合から、品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段とを有する。

フロー品質収集手段が端末に指示して試験フローを発生させているため、品質劣化箇所推定手段は、試験フローを含む、現在通信中のフローが経由している全てのリンクから、品質良好なフローが経由するリンクを除外した後で、本発明に係る第一の品質劣化箇所推定装置の品質劣化箇所推定手段と同じ方法によって、品質劣化箇所を推定している。試験フローの経路は、ネットワーク利用者のフローの経路に依存して、推定精度を高めるよう決定されるため、推定精度を高めることができる。また、推定精度を高めるために必要なフローが、既にネットワーク利用者によって流されている場合には、そのフローを流さないため、試験フローによるネットワーク利用量を減らすことができる。

本発明に係る第六の品質劣化箇所推定装置は、本発明に係る第五の品質劣化箇所推定装置おいて、利用者フローの経路に依存して、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように試験フローを流す経路を決定するフロー品質／経由リンクテーブル管理手段を有する。

試験フローの経路は、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように試験フローを流す経路を決定されるため、利用者フローが流れる経路上の任意の１箇所のリンクが品質劣化を起こした場合に、その位置を正しく推定することができ、品質劣化箇所の推定精度の向上を実現している。

本発明に係る品質劣化箇所推定方法は、本発明に係る品質劣化箇所推定装置の各手段の動作を手順として捉えたものである。本発明に係る品質劣化箇所推定プログラムは、本発明に係る品質劣化箇所推定方法の各手順をコンピュータに実行させるためのものである。

また、本発明は次のように構成してもよい。

（１）．ネットワーク利用者が流しているフローの送信者アドレスと受信者アドレスと通信品質から成るフロー品質情報、及び、ネットワークの構成情報を集め、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求め、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する、ことを特徴とする品質劣化箇所推定方法。

（２）．ネットワーク利用者が流しているフローの送信者アドレスと受信者アドレスと通信品質から成るフロー品質情報、及び、ネットワークの構成情報を集め、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求め、ネットワークの各リンクについて過去の品質劣化原因となった確率を記憶しておき、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最も発生確率が高いと推定される部分集合を前記確率を用いて決定し、 決定した部分集合を品質劣化箇所として出力する、ことを特徴とする品質劣化箇所推定方法。

（３）．上記（１）に記載の品質劣化箇所推定方法において、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合から、品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する、ことを特徴とする品質劣化箇所推定方法。

（４）．上記（２）に記載の品質劣化箇所推定方法において、１つ以上フローの品質の劣化を検知した場合、品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、過去の品質劣化原因となった確率から最も発生確率が高いと推定される部分集合を、品質劣化箇所として出力する、ことを特徴とする品質劣化箇所推定方法。

（５）．ネットワーク利用者が流しているフローの経路に依存した経路で試験フローを同時に流しておき、利用者フローと試験フローの両方のフローの送信者アドレスと受信者アドレスと通信品質から成るフロー品質情報、及び、ネットワークの構成情報を集め、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求め、１つ以上フローの品質の劣化を検知した場合、質劣化を起こした任意のフローの集合が経由するリンクの集合から、品質良好なフローが経由するリンクを除外し、除外後の集合の部分集合の中で、品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する、ことを特徴とする品質劣化箇所推定方法。

（６）．上記（５）に記載の品質劣化箇所推定方法において、利用者フローの経路に依存して、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように試験フローを流す、ことを特徴とする、品質劣化箇所推定方法。

本発明によれば、現在が通信中のフローが経由している全てのリンクについて、現在の通信品質劣化を起こし得る、あらゆる品質劣化したリンクの組み合わせのうち、最小のリンク数からなる組み合わせを品質劣化箇所として、又は、過去の各リンクが品質劣化原因となった確率に基づいて、最も高い確率となる組み合わせを品質劣化箇所として出力することにより、フロー品質情報に基づいて精度高く品質劣化箇所を推定できる。

図１に本発明に係る第一実施形態のネットワーク構成図を示す。ネットワークには、ルータ（又はスイッチ）Ｒ１〜Ｒ６が配置され、端末Ｔ１〜Ｔ１２及び品質劣化箇所推定サーバＳ１が接続されている。

図２に、本発明に係る第一実施形態における品質劣化箇所推定サーバＳ１の内部構成図を示す。品質劣化箇所推定サーバＳ１は、フロー品質情報収集部１１、経路情報収集部１２、フロー品質／経由リンクテーブル管理部１３、テーブル記憶部１４、品質劣化箇所推定部１５、表示部１６から構成される。品質劣化箇所推定サーバＳ１は、端末Ｔ１〜Ｔ１２からフロー毎の品質情報を集め、ルータ又はスイッチから得た経路情報を基に、品質劣化箇所を推定し、推定結果を表示部１６に出力する。

以下に、各構成要素の動作を説明する。

フロー品質情報収集部１１は、次のように動作する。端末が通信開始すると、フロー品質情報収集部１１は端末からそのことが通知される。また通信開始以降は、端末から定期的に、端末の現在の通信品質情報（すなわち送信端末のアドレス、受信端末のアドレス、通信品質情報等の情報の組）を受け取る。端末が通信終了すると、通信終了の通知を受け取る。ここで、通信品質情報とは、例えば、パケットロス率、パケットロスのバースト性、受信レート、遅延、遅延ジッタ等の通信品質に関わる情報である。

経路情報収集部１２は、次のように動作する。経路情報収集部１２は、ルータ（又はスイッチ）Ｒ１〜Ｒ６から、ルーティングに関する情報を収集する。これは、ＳＭＴＰ（Simple Network Management Protocol）等を使って行うことが可能である。ルーティングに関する情報があれば、送受信端末のアドレス情報から、当該送受信端末間の通信がどの経路で行われるかを決定することができる。具体的には、ルータから収集する場合は、ルーティングテーブル及びＡＲＰテーブルの構成情報である。スイッチから収集する場合は、フォワーディングデーターベース及びスパニングツリーの構成情報である。なお、この情報は、ルータ（又はスイッチ）Ｒ１〜Ｒ６から収集せず、ネットワーク管理者が与えることも可能である。

フロー品質／経由リンクテーブル管理部１３は、次のように動作する。フロー品質／経由リンクテーブル管理部１３は、フロー品質情報収集部１１から得たフロー品質情報と、経路情報収集部１２からのルーティングに関する情報とに基づいて、現在通信が行われているフローについて、送受信端末のアドレスと、それらが現在経由しているリンク集合と、そのフローの現在の通信品質の良否を示す品質フラグとから成るフロー品質／経由リンクテーブルとを維持する。

ここでリンクとは、ルータ（又はスイッチ）間、ルータ（又はスイッチ）と端末との間の有向リンクとする。例えば、図１に示した、ネットワーク構成図の場合、図３に示すＬ１０，Ｌ１１，Ｌ２０，Ｌ２１，・・・，Ｌ２２０，Ｌ２２１の有向リンクである。

品質フラグは、フロー品質情報の通信品質情報に含まれる情報（パケットロス率、パケットロスのバースト性、受信レート、遅延、遅延ジッタ等）から品質指標を求め、それが、予め与えられた劣化閾値を超えるか否かで判定し、劣化閾値以上であれば（劣化している）フラグは「１」とする。また、品質指標が、予め与えられた良好閾値以下であれば、フラグは「０」とする。いずれでもなければ、品質フラグは不定（以下“「Ｎ／Ａ」”で表す。）とする。品質指標の例としては、単純に通信品質情報のうちの１つ（例えば、パケットロス率）を用いてもよいし、ＶｏＩＰのフローであれば、パケットロス率、遅延ジッタなどから、ＩＴＵ−Ｔ勧告のＧ．１０７のＥ−Ｍｏｄｅｌに従ってＲ値を求め、それを品質指標として用いてもよい。

例えば、図１に示したネットワーク構成図において、図４に示すようにフローＦ１〜Ｆ５が流れていたとし、フローＦ１〜Ｆ５の現在のフロー品質情報が図５に示す内容であったとする。品質指標としてパケットロス率を用い、劣化閾値が１％であった場合、フロー品質／経由リンクテーブルは、図６に示す内容となる。

図７に、フロー品質／経由リンクテーブル管理部１３の動作をフローチャートで示す。フロー品質情報収集部１１からフロー品質情報を受け取った場合（ＦＣ１００１）、もし、それが通信終了を示すものであれば（ＦＣ１００２）、該当フローをフロー品質／経由リンクテーブルから除去する（Ｆ１００３）。そうでなく（ＦＣ１００４）、通信開始を示すものであれば（ＦＣ１００５）、現在のルーティングに関する情報を経路情報収集部１２から得て、フロー品質情報の（送信端末のアドレス、受信端末のアドレス）の情報から経由リンクを決定し（ＦＣ１００６）、フロー品質情報の通信品質情報から品質フラグを決定し、フロー品質／経由リンクテーブルへ登録する（ＦＣ１００７）。通信開始を示すものでない場合（ＦＣ１００８）、それは今登録されているフローの最新の通信品質を通知するものであるので、フロー品質情報の通信品質情報から品質フラグを決定し、フロー品質／経由リンクテーブルの通信フラグを更新する（ＦＣ１００９）。経路情報収集部１２から経路情報を受信した場合（ＦＣ１０１０）、経路情報に変更があれば（ＦＣ１０１１）、現在のフロー品質／経由リンクテーブルに登録されている全フローについて、テーブルの（送信端末のアドレス、受信端末のアドレス）の情報と、現在のルーティングに関する情報（変更後のもの）とを基に経由リンクを決定し、フロー品質／経由リンクテーブルを更新する（ＦＣ１０１２）。

テーブル記憶部１４は、次のように動作する。テーブル記憶部１４は、フロー品質／経由リンクテーブルを記憶している。

品質劣化箇所推定部１５は、次のように動作する。品質劣化箇所推定部１５は、定期的にテーブル記憶部１４からフロー品質／経由リンクテーブルを読み出し、品質フラグが「１」のフローがある場合に、最小リンク数推定法を用いて品質劣化箇所を推定し、その結果を表示部１６へ出力する。

図８に、品質劣化箇所推定部１５の動作をフローチャートで示す。ここで、最小リンク数推定法を説明する。まず、フロー品質／経由リンクテーブルの経由リンクの列について、「１」が立っているフローの集合を、そのリンク列に属するフロー集合と呼ぶ。例えば、図６のフロー品質／経由リンクテーブルの場合、経由リンクＬ２０の列に属するフロー集合は、｛Ｆ１，Ｆ２，Ｆ３｝である。さらに、複数の経由リンクの列のそれぞれに属するフロー集合の和集合も同様に、それらのリンク列の集合に属するフロー集合と呼ぶ、例えば、図６のフロー品質／経由リンクテーブルの場合、リンク列の集合｛Ｌ１０，Ｌ３０，Ｌ８０｝に属するフロー集合は、｛Ｆ２，Ｆ３，Ｆ４，Ｆ５｝である。

ここで、最小リンク数推定法について具体的に説明する。まず、フロー品質／経由リンクテーブルを読み込み（ステップ１０１）、それらの中から品質フラグが「１」のフローのみを抽出する（ステップ１０２）。続いて、経由リンク列の集合に属するフロー集合が、ステップ１０２で抽出されたフローと同一になる、経由リンク列の集合のうち、最小の要素数からなるものを選ぶ（ステップ１０３）。続いて、ステップ１０３で得られた経由リンク集合（複数あってもよい）を結果として出力する（ステップ１０４）。

例えば、図６のフロー品質／経由リンクテーブルについて、最小リンク数推定法を実行する場合を説明する。このテーブルは全ての行の品質フラグが「１」であるので、ステップ１０２では全フロー｛Ｆ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５｝が抽出される。次に、ステップ１０３を実行すると、経由リンク列の集合に属するフロー集合が｛Ｆ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５｝となるようなフロー集合は、｛Ｌ２０，Ｌ８０｝，｛Ｌ３０，Ｌ１５０，Ｌ１７１｝，・・・，等があるが、最小の要素数を持つものは、｛Ｌ２０，Ｌ８０｝だけ（要素数２）である。ステップ１０４において、｛Ｌ２０，Ｌ８０｝が最小リンク数推定法の結果として出力される。なお、ステップ１０３は、最小被覆問題のアルゴリズムを用いて解くことが可能である。

本実施形態の効果は、各リンクがフローの品質劣化起こす確率が同程度で、互いに独立である場合に、品質劣化箇所を精度高く推定することができることにある。その理由は、次の通りである。フロー品質／経由リンクテーブルにおいて、ある経由リンクが品質劣化を起こした場合、その経由リンクの列に「１」の立っているフローが品質劣化を起こすと考えられる。このため、経由リンクの集合に属するフローは、経由リンクの集合が同時に品質劣化を起こした時に、品質劣化を起こすフローの集合と言える。このため、最小リンク数推定法は、現在の品質劣化の状況を引き起こすような品質劣化したリンク集合の全ての集合の中で、最も少ない要素数（リンク数）を持つものである。各リンクが品質劣化の原因となる確率が同程度、例えば確率p（０≦p≦１）で互いに独立である場合には、ｋ個のリンクが同時にフローの品質劣化を起こす確率はｐ＾ｋ（ｐのｋ乗）となり、ｋが大きいほど確率は小さくなる。すなわち、現在の品質劣化の状況を引き起こすような品質劣化原因の全パターンのうち、最も発生確率が高いパターンを見つけるのが、最小リンク数推定法である。この意味で、各リンクがフローの品質劣化起こす確率が同程度で、互いに独立である場合に、品質劣化箇所を最適に推定していると言える。

本発明に係る第二実施形態は、本発明に係る第一実施形態に対して、品質劣化箇所推定サーバＳ１の内部構成及び品質劣化箇所推定部の動作のみが異なるため、異なる点のみ説明する。

図９に、第二実施形態の品質劣化箇所推定サーバＳ１の内部構成図を示す。本実施形態の品質劣化箇所推定サーバＳ１は、第一実施形態に対して、リンク品質劣化確率記憶部１７が追加され、リンク品質劣化確率記憶部１７と品質劣化箇所推定部１５とで情報をやりとりする点のみが異なる。リンク品質劣化確率記憶部１７は、ネットワーク内の各リンクについて（ここで、リンクとは、第一実施形態で説明した有向リンクである。）、過去に通信品質の劣化発生時に、その原因となった確率を記憶しており、図１０のような品質劣化原因確率テーブルを記憶している。

以下、第一実施形態と動作が異なる品質劣化箇所推定部１５の動作のみを説明する。第一実施形態との違いは、品質劣化箇所推定部１５が、リンク品質劣化確率記憶部１７からの情報を基に、最小リンク推定法ではなく、最大確率推定法を用いて、品質劣化箇所を推定することにある。

品質劣化箇所推定部１５は、次のように動作する。品質劣化箇所推定部１５は、定期的にテーブル記憶部１４からフロー品質／経由リンクテーブルを読み出し、その中で品質フラグ「１」のフローがある場合に、最大確率推定法を用いて品質劣化箇所を推定し、その結果を表示部１６へ出力する。図１１に、品質劣化箇所推定部１５の動作をフローチャートで示す。

ここで、最大確率推定法について説明する。まず、フロー品質／経由リンクテーブルの経由リンクの列について、「１」が立っているフローの集合を、そのリンク列に属するフロー集合と呼ぶ。例えば、図６のフロー品質／経由リンクテーブルの場合、経由リンクＬ２０の列に属するフロー集合は、｛Ｆ１，Ｆ２，Ｆ３｝である。更に、複数の経由リンクの列のそれぞれに属するフロー集合の和集合も同様に、それらのリンク列の集合に属するフロー集合と呼ぶ、例えば、図６のフロー品質／経由リンクテーブルの場合、リンク列の集合｛Ｌ１０，Ｌ３０，Ｌ８０｝に属するフロー集合は、｛Ｆ２，Ｆ３，Ｆ４，Ｆ５｝である。また、リンク列の集合の推定発生確率とは、リンク品質劣化確率記憶部１７に記憶されている、各リンクの品質劣化原因となった確率を掛け合わせたものである。

ここで、最大確率推定法について具体的に説明する。まず、フロー品質／経由リンクテーブルを読み込み（ステップ２０１）、その中から品質フラグが「１」のフローのみを抽出する（ステップ２０２）。続いて、経由リンク列の集合に属するフロー集合が、ステップ２０２で抽出されたフローと同一になる、経由リンク列の集合のうち、推定発生確率が最大のものを選ぶ（ステップ２０３）。最後に、ステップ２０３で得られた経由リンク集合（複数あってもよい）を、結果として表示部１６へ出力する（ステップ２０４）。

例えば、図６のフロー品質／経由リンクテーブルについて、最大確率推定法を実行する場合を説明する。このテーブルは全ての行の品質フラグが「１」であるので、ステップ２０２では全フロー｛Ｆ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５｝が抽出される。次に、ステップ２０３の説明のため、図６のフロー品質／経由リンクテーブルに、リンク品質劣化確率記憶部１７に記憶されている、各リンクの品質劣化原因確率テーブルの内容を併記したものを、図１２に示す。

ステップ２０３を実行すると、経由リンク列の集合に属するフロー集合が｛Ｆ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５｝となるようなフロー集合は｛Ｌ２０，Ｌ８０｝，｛Ｌ３０，Ｌ１５０，Ｌ１７１｝，・・・，等があり、それぞれの推定発生確率は0.00001，0.0005，・・・，であり、最大の確率をもつものは｛Ｌ３０，Ｌ１５０，Ｌ１７１｝である。ステップ３において、｛Ｌ３０，Ｌ１５０，Ｌ１７１｝が最大確率推定法の結果として出力される。

本実施形態の効果は、各リンクがフローの品質劣化を起こす確率が互いに独立である場合に、品質劣化箇所を精度高く推定することができることにある。その理由は、次の通りである。フロー品質／経由リンクテーブルにおいて、ある経由リンクが品質劣化を起こした場合、その経由リンクの列に「１」の立っているフローが品質劣化を起こすと考えられる。このため、経由リンクの集合に属するフローは、経由リンクの集合が同時に品質劣化を起こした時に、品質劣化を起こすフローの集合と言える。最大確率推定法は、過去の品質劣化時に各リンクが品質劣化の原因となった確率に基づき、現在の品質劣化の状況を引き起こすような品質劣化したリンク集合の全ての集合の中で、最も発生確率が高いものを選び出している。

本発明に係る第三実施形態は、第一実施形態に対して、品質劣化箇所推定サーバＳ１における品質劣化箇所推定部１５の動作のみが異なる。そのため、その異なる点のみを説明する。

品質劣化箇所推定部１５は、次のように動作する。品質劣化箇所推定部１５は、定期的に、テーブル記憶部１４からフロー品質／経由リンクテーブルを読み出し、品質フラグ「１」のフローがある場合に、まず、品質非劣化リンクを除去し、その後に、最小リンク数推定法を用いて、品質劣化箇所を推定し、その結果を表示部１６へ出力する。図１３に、品質劣化箇所推定部１５の動作をフローチャートで示す。

品質非劣化リンクの除去とは、品質フラグ「０」のフローの行の経由リンク欄に「１」が立っているリンクを除去することである。例えば、図１４に示すような、第一実施形態の説明例に加え、Ｆ６，Ｆ７という新たなフロー（点線矢印で示されている）が流れている例を考える。このとき、Ｆ１〜Ｆ７の現在のフロー品質／経由リンクテーブルが、図１５に示す内容であったとする。Ｆ６，Ｆ７は品質が良好なフローであり（品質フラグが「０」）、このフローが経由するリンクであるＬ１２０，Ｌ１０，Ｌ２０，Ｌ３０，Ｌ１８１，Ｌ１５０，Ｌ１４１は品質劣化を起こしていないと考えられる。これらを除去したテーブルが、図１６に示したものである。これに対し、最小リンク推定法を用い、｛Ｌ８０，Ｌ１６１，１９１｝を推定結果として出力する。

本実施形態の第一の効果は、各リンクがフローの品質劣化起こす確率が互いに独立である場合に、品質劣化箇所の推定精度をより高めることができることにある。その理由は、以下の通りである。品質が良好なフローが経由するリンクは、品質劣化を起こしていないと考えられる。本実施形態では、最小リンク推定法を適用する前に、これらのリンクを推定対象から除いている。最小リンク数推定法では、現在の品質劣化の状況を引き起こすような品質劣化したリンク集合の全ての可能性のうち、最も発生確率が高いものを見つけるが、そもそも品質劣化を起こしていないリンクを除去しておけば、より推定精度を高めることができるからである。

本実施形態の第二の効果は、品質劣化箇所の推定速度を向上させることにある。その理由は、最小リンク数推定法は、推定対象のリンク数が増大すると、大幅に推定時間が増大するが、本発明に係る第三実施形態では、品質劣化を起こしていないと考えられるリンクを除去してから最小リンク数推定法を適用するため、推定対象のリンク数を減少させることができ、推定速度を向上させることができる。

本発明に係る第四実施形態は、本発明に係る第二実施形態の、品質劣化箇所推定サーバＳ１の、品質劣化箇所推定部１５の動作のみが異なる。そのため、異なる点のみ説明する。

品質劣化箇所推定部１５は、次のように動作する。品質劣化箇所推定部１５は、定期的にテーブル記憶部１４からフロー品質／経由リンクテーブルを読み出し、品質フラグ「１」のフローがある場合に、まず品質非劣化リンクを除去し、その後に最大確率推定法を用いて品質劣化箇所を推定し、その結果を表示部１６へ出力する。図１７に、品質劣化箇所推定部の動作をフローチャートで示す。

品質非劣化リンクの除去とは、品質フラグが「０」のフローの行の経由リンク欄に「１」が立っているリンクを除去することである。例えば、図１４に示すような、第二実施形態の説明例に加えＦ６，Ｆ７という新たなフロー（点線矢印で示されている）が流れている例を考える。このとき、Ｆ１〜Ｆ７の現在のフロー品質／経由リンクテーブルが図１５に示す内容であったとする。Ｆ６，Ｆ７は品質が良好なフローであり（品質フラグが０）、このフローが経由するリンクである、Ｌ１２０，Ｌ１０，Ｌ２０，Ｌ３０，Ｌ１８１，Ｌ１５０，Ｌ１４１は品質劣化を起こしていないと考えられる。これらを除去したテーブルが、図１６に示したものである。

これに対し、最大確率推定法を適用する。図１６のフロー品質／経由リンクテーブルに、リンク品質劣化確率記憶部１７に記憶されている、各リンクの品質劣化原因確率テーブルの内容を併記したものを、図１８に示す。

最大確率推定法のステップ１の実行後、ステップ２を実行すると、経由リンク列の集合に属するフロー集合が｛Ｆ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５｝となるようなフロー集合は、｛Ｌ８０，Ｌ１６１，Ｌ１９１｝，｛Ｌ１６１，Ｌ７１，１９１，Ｌ２０１｝，・・・，等があり、それぞれの推定発生確率は、0.0000001，0.000001，・・・，であり、最大の確率をもつものは、｛Ｌ１６１，Ｌ７１，１９１，Ｌ２０１｝である。ステップ３において、｛Ｌ１６１，Ｌ７１，１９１，Ｌ２０１｝が最大確率推定法の結果として出力される。

本実施形態の第一の効果は、各リンクがフローの品質劣化を起こす確率が互いに独立である場合に、品質劣化箇所の推定精度をより高めることができることにある。その理由は、以下の通りである。品質が良好なフローが経由するリンクは、品質劣化を起こしていないと考えられる。本実施形態では、最大確率推定法を適用する前に、これらのリンクを推定対象から除いている。最大確率推定法では、現在の品質劣化の状況を引き起こすような品質劣化したリンク集合の全ての可能性のうち、最も発生確率が高いものを見つけるが、そもそも品質劣化を起こしていないリンクを除去しておけば、より推定精度を高めることができるからである。

本実施形態の第二の効果は、品質劣化箇所の推定速度を向上させることにある。その理由は、最大確率推定法は、推定対象のリンク数が増大すると、大幅に推定時間が増大するが、本実施形態では、品質劣化を起こしていないと考えられるリンクを除去してから最大確率推定法を適用するため、推定対象のリンク数を減少させることができ、推定速度を向上させることができる。

本発明に係る第五実施形態は、第三実施形態と比べ、品質劣化箇所推定サーバＳ１の内部構成と、フロー品質／経由リンクテーブル管理部１３の動作のみが異なる。そのため、異なる点のみ説明する。

図１９に、第五実施形態における品質劣化箇所推定サーバＳ１の内部構成図を示す。本実施形態における品質劣化箇所推定サーバＳ１は、試験フロー制御部１８が追加され、フ試験フロー制御部１８とフロー品質／経由リンクテーブル管理部１３及び端末Ｔ１〜Ｔ１２との間で情報をやりとりする点のみが異なる。

端末は、利用者が発生するフロー以外に試験フロー制御部１８からの指示に従って、試験フローを発生させられるものとし、試験フローについても、利用者のフローと同様に、フロー品質を品質劣化箇所推定サーバＳ１のフロー品質情報収集部１１へ伝えるものとする。

以下に、本実施形態の品質劣化箇所推定サーバＳ１に追加された、試験フロー制御部１８と、動作に変更のあるフロー品質／経由リンクテーブル管理部１３との動作を説明する。その他の要素の動作は同じである。

試験フロー制御部１８は、次のように動作する。フロー品質／経由リンクテーブル管理部１３からの指示に従い、端末に指示して、試験フローの送信及び停止を指示する。

フロー品質／経由リンクテーブル管理部１３は、次のように動作する。第三実施形態と同様の方法で、フロー品質情報収集部１１から得たフロー品質情報と、経路情報収集部１２からのルーティングに関する情報とに基づいて、現在通信が行われているフロー（試験フローも含む）について、送受信端末のアドレスと、それらが現在経由しているリンク集合と、そのフローの現在の通信品質の良否を示す品質フラグとから成るフロー品質／経由リンクテーブルを維持する。更に、試験フローを流す経路集合を、現在の利用者フローの経路に依存して決定し、試験フロー制御部１８に指示して、その端末間で試験フローを発生させる。試験フロー経路集合は、利用者フローの品質劣化が発生した場合に、品質劣化箇所を精度高く決定できるような経路である。

利用者フローが経由しているリンクの１箇所が品質劣化を起こしたとき、そのリンクを、本実施形態の品質劣化箇所推定部１５（すなわち、第三実施形態の品質劣化箇所推定部１５と同じ動作をする）で正しく推定できないのは、次に示す、非劣化リンク除去付き最小リンク推定不確定条件が成り立っている場合である。

非劣化リンク除去付き最小リンク推定不確定条件について説明する。

（Ａ）任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態。

（Ｂ）利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態。

（Ａ）の場合には、その２箇所以上のリンクいずれかで品質劣化が発生した場合、どのリンクで発生したかを正しく推定できず、そのリンク全てを推定結果として示してしまう。（Ｂ）の場合にも、その２箇所以上のリンクいずれかで品質劣化が発生した場合、のリンクで発生したかを正しく推定できず、そのリンク全てを推定結果として示してしまう。

そこで、次のような方法で、（Ａ），（Ｂ）が起こらないように試験フローを流す経路を決定する。

試験フロー経路集合決定方法について説明する。

（ステップ１）：現在の試験フローの経路集合の全経路について、順に次を実行する。

もしその試験フローを除いた場合、推定不確定条件（Ａ），（Ｂ）が成立するか否かチェックする。もしいずれも成立しないならば、そのフロー試験フローの経路集合から除く。

（ステップ２）：現在の利用者のフローの全てについて、順に次を実行する。

そのフローについて、推定不確定条件（Ａ）が成立しているか否かチェックする。もし成立していれば、他のフローとリンクを共有していない２箇所以上のリンクの各リンクについて、試験フローを流すことができるか否かチェックし、流せるならば、そのフローの経路を試験フロー経路集合に加える。次に、推定不確定条件（Ｂ）をチェックし、もし成立していれば、共有している２箇所以上のリンクの各リンクについて、試験フローを流すことができるか否かチェックし、流せるならば、そのフローの経路を試験フロー経路集合に加える。

図２０に、フロー品質／経由リンクテーブル管理部１３の動作をフローチャートで示す。図７に示した第一実施形態のフロー品質情報収集部のフローチャートと異なる、点線部（ＦＣ２００１）についてのみ説明する。その他の動作は同じである。経路の変更、又は、フローの発生／停止の場合があると、ＦＣ２００２に達する。もし、試験フローの発生／停止の場合（ＦＣ２００３）何もしないが、それ以外の場合（ＦＣ２００４）、先に述べた試験フロー経路集合決定方法によって、試験フローの経路集合を決定し（ＦＣ２００５），経路集合に変化があれば（ＦＣ２００６）、試験フロー制御部１８に指示して、変化のあった経路について、試験フローを発生又は停止させる。

例えば、図１に示したネットワーク構成図において、図２１に示すようにフローＦ１〜Ｆ６が流れていたとし、全フローに劣化がない状態であると、フロー品質／経由リンクテーブルは、図２２に示す内容となる。この状態で、非劣化リンク除去付き最小リンク推定不確定条件の（Ｂ）が成立している、Ｌ１０で品質劣化が発生すると、｛Ｆ２，Ｆ６｝が品質劣化フローとなり、本実施形態の品質劣化箇所推定部１５（すなわち第三実施形態の品質劣化箇所推定部１５と同じ動作をする）での推定方法では、｛Ｌ１０｝と｛Ｌ１２０｝の両方を結果として出してしまい、正しく推定できない。同様に、劣化リンク除去付き最小リンク推定不確定条件の（Ａ）が成立している、Ｌ１５０で品質劣化が発生したとすると、本実施形態の品質劣化箇所推定部１５での推定方法では、｛Ｌ１５０｝，｛Ｌ１６０｝を結果として出してしまい、やはり正確な推定ができない。

この場合、フロー品質／経由リンクテーブル管理部１５が、試験フローを流す経路集合を決定すると、利用者フロー及び試験フローを含めたフロー品質／経由リンクテーブルは、図２３の内容になる。この場合、利用者フローが経由しているリンク集合｛Ｌ１０，Ｌ２０，Ｌ３０，Ｌ８０，Ｌ１２０，Ｌ１４０，Ｌ１５０，Ｌ１６０，Ｌ１７１，Ｌ１９１，Ｌ２０１，Ｌ２１０，Ｌ２２０，Ｌ１４１｝のいずれか１つのリンクで品質劣化が発生しても、正しく品質劣化箇所を推定することが可能である。このように、本実施形態により、品質劣化箇所の推定精度を高めることが可能となる。

本発明に用いられるネットワーク構成例を示すブロック図である。 本発明に係る第一実施形態の品質劣化箇所推定サーバの構成例を示すブロック図である。 本発明に用いられるネットワーク構成例のリンクを示すブロック図である。 本発明に係る第一実施形態のフロー例を示すブロック図である。 本発明に係る第一実施形態のフロー品質情報の一例を示す図表である。 本発明に係る第一実施形態のフロー品質／経由リンクテーブルの一例を示す図表である。 本発明に係る第一実施形態のフロー品質／経由リンクテーブル管理部の動作を示すフローチャートである。 本発明に係る第一実施形態の品質劣化箇所推定部の動作を示すフローチャートである。 本発明に係る第二実施形態の品質劣化箇所推定サーバの構成例を示すブロック図である。 本発明に係る第二実施形態の品質劣化原因確率テーブルの一例を示す図表である。 本発明に係る第二実施形態の品質劣化箇所推定部の動作を示すフローチャートである。 本発明に係る第二実施形態のフロー品質／経由リンクテーブルに、各経由リンクの品質劣化原因確率を併記した図表である。 本発明に係る第二実施形態の品質劣化箇所推定部の動作を示すフローチャートである。 本発明に係る第三実施形態のフロー例を示すブロック図である。 本発明に係る第三実施形態のフロー品質／経由リンクテーブルの一例を示す図表である。 本発明に係る第三実施形態の品質非劣化リンク除去後のフロー品質／経由リンクテーブルの一例を示す図表である。 本発明に係る第四実施形態の品質劣化箇所推定部の動作を示すフローチャートである。 本発明に係る第四実施形態の品質非劣化リンク除去後のフロー品質／経由リンクテーブルに、各経由リンクの品質劣化原因確率を併記した図表である。 本発明に係る第五実施形態の品質劣化箇所推定サーバの構成例を示すブロック図である。 本発明に係る第五実施形態のフロー品質／経由リンクテーブル管理部の動作を示すフローチャートである。 本発明に係る第五実施形態のフロー例を示すブロック図である。 本発明に係る第五実施形態のフロー品質／経由リンクテーブルの一例を示す図表である。 本発明に係る第五実施形態の試験フローが追加された後のフロー品質／経由リンクテーブルの一例を示す図表である。 従来の品質劣化箇所推定方法を示すブロック図である。 従来の品質劣化箇所推定方法の問題点１を説明するためのブロック図である。 従来の品質劣化箇所推定方法の問題点２を説明するためのブロック図である。

符号の説明

Ｒ１〜Ｒ６ ルータ又はスイッチ
Ｔ１〜Ｔ１２ 端末
Ｓ１ 品質劣化箇所推定サーバ
Ｆ１〜Ｆ６ 利用者フロー
ＴＦ１〜ＴＦ４ 試験フロー
１１ フロー品質情報収集部
１２ 経路情報収集部
１３ フロー品質／経由リンクテーブル管理部
１４ テーブル記憶部
１５ 品質劣化箇所推定部
１６ 表示部
１７ リンク品質劣化確率記憶部
１８ 試験フロー制御部

Claims (18)

1. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集するフロー品質情報収集手段と、
   前記ネットワークの構成情報を収集する経路情報収集手段と、
   前記フロー品質情報収集手段で収集されたフロー品質情報と前記経路情報収集手段で収集されたネットワークの構成情報とに基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理するフロー品質／経由リンクテーブル管理手段と、
   このフロー品質／経由リンクテーブル管理手段で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段と、
   を備えたことを特徴とする品質劣化箇所推定装置。
2. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集するフロー品質情報収集手段と、
   前記ネットワークの構成情報を収集する経路情報収集手段と、
   前記フロー品質情報収集手段で収集されたフロー品質情報と前記経路情報収集手段で収集されたネットワークの構成情報とに基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理するフロー品質／経由リンクテーブル管理手段と、
   前記ネットワークの各リンクについて、過去の品質劣化原因となった確率を記憶しておくリンク品質劣化確率記憶手段と、
   前記フロー品質／経由リンクテーブル管理手段で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する品質劣化箇所推定手段と、
   を備えたことを特徴とする品質劣化箇所推定装置。
3. 請求項１記載の品質劣化箇所推定装置において、前記品質劣化箇所推定手段に代えて、
   前記フロー品質／経由リンクテーブル管理手段で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段を備えた、
   ことを特徴とする品質劣化箇所推定装置。
4. 請求項２記載の品質劣化箇所推定装置において、前記品質劣化箇所推定手段に代えて、
   前記フロー品質／経由リンクテーブル管理手段で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する品質劣化箇所推定手段を備えた、
   ことを特徴とする品質劣化箇所推定装置。
5. ネットワークの利用者フロー及び試験フローを含むフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集し、かつ、前記ネットワークの端末に前記試験フローの発生及び停止を指示するフロー品質収集手段と、
   前記ネットワークの構成情報を収集する経路情報収集手段と、
   前記フロー品質収集手段で収集されたフロー品質情報と前記経路情報収集手段で収集されたネットワークの構成情報とに基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して前記試験フローを流す経路を決定するフロー品質／経由リンクテーブル管理手段と、
   このフロー品質／経由リンクテーブル管理手段で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段と、
   を備えたことを特徴とする品質劣化箇所推定装置。
6. 請求項５記載の品質劣化箇所推定装置おいて、前記フロー品質／経由リンクテーブル管理手段に代えて、
   前記フロー品質収集手段で収集されたフロー品質情報と前記経路情報収集手段で収集されたネットワークの構成情報とに基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように、前記試験フローを流す経路を決定するフロー品質／経由リンクテーブル管理手段を備えた、
   ことを特徴とする品質劣化箇所推定装置。
   
7. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集する第一の手順と、
   前記ネットワークの構成情報を収集する第二の手順と、
   前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理する第三の手順と、
   この第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順と、
   を含むことを特徴とする品質劣化箇所推定方法。
8. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集する第一の手順と、
   前記ネットワークの構成情報を収集する第二の手順と、
   前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理する第三の手順と、
   前記ネットワークの各リンクについて、過去の品質劣化原因となった確率を記憶しておく第四の手順と、
   前記第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する第五の手順と、
   を含むことを特徴とする品質劣化箇所推定方法。
9. 請求項７記載の品質劣化箇所推定方法において、前記第四の手順に代えて、
   前記三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順を含む、
   ことを特徴とする品質劣化箇所推定方法。
10. 請求項８記載の品質劣化箇所推定方法において、前記第五の手順に代えて、
    前記第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する第五の手順を含む、
    ことを特徴とする品質劣化箇所推定方法。
11. ネットワークの利用者フロー及び試験フローを含むフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集し、かつ、前記ネットワークの端末に前記試験フローの発生及び停止を指示する第一の手順と、
    前記ネットワークの構成情報を収集する第二の手順と、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して前記試験フローを流す経路を決定する第三の手順と、
    この第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順と、
    を含むことを特徴とする品質劣化箇所推定方法。
12. 請求項１１記載の品質劣化箇所推定方法おいて、前記第三の手順に代えて、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように、前記試験フローを流す経路を決定する第三の手順を含む、
    ことを特徴とする品質劣化箇所推定方法。
    
13. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集する第一の手順と、
    前記ネットワークの構成情報を収集する第二の手順と、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理する第三の手順と、
    この第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順と、
    をコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
14. ネットワークの利用者が流しているフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集する第一の手順と、
    前記ネットワークの構成情報を収集する第二の手順と、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理する第三の手順と、
    前記ネットワークの各リンクについて、過去の品質劣化原因となった確率を記憶しておく第四の手順と、
    前記第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する第五の手順と、
    をコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
15. 請求項１３記載の品質劣化箇所推定プログラムにおいて、前記第四の手順に代えて、
    前記三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順を、
    コンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
16. 請求項１４記載の品質劣化箇所推定プログラムにおいて、前記第五の手順に代えて、
    前記第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、その品質劣化を起こした任意のフローの集合が経由するリンクの集合から品質良好なフローが経由するリンクを除外し、除外後のリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、品質劣化の発生確率が最も高いと推定される部分集合を、前記リンク品質劣化確率記憶手段で記憶されている確率を用いて決定し、決定した部分集合を品質劣化箇所として出力する第五の手順を、
    コンピュータに実行させることを特徴とする品質劣化箇所推定方法。
17. ネットワークの利用者フロー及び試験フローを含むフローの送信者アドレス、受信者アドレス及び通信品質を含むフロー品質情報を収集し、かつ、前記ネットワークの端末に前記試験フローの発生及び停止を指示する第一の手順と、
    前記ネットワークの構成情報を収集する第二の手順と、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して前記試験フローを流す経路を決定する第三の手順と、
    この第三の手順で管理されている前記テーブルにおいて、１つ以上のフローに品質劣化があった場合、品質劣化を起こした任意のフローが経由するリンクの集合の部分集合のうち、その部分集合に含まれる各リンクを経由しているフロー集合を、その部分集合に含まれる全リンクについて和をとった集合が、全ての品質劣化したフローを含むような部分集合であって、かつ、最小の要素数をもつ部分集合を、品質劣化箇所として出力する第四の手順と、
    をコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
18. 請求項１７記載の品質劣化箇所推定プログラムおいて、前記第三の手順に代えて、
    前記第一及び第二の手順で収集されたフロー品質情報及びネットワークの構成情報に基づき、前記フローが経由するリンクを求め、かつ当該フローの品質劣化の有無を判定し、その結果をテーブルとして管理すると共に、前記利用者フローの経路に依存して、任意の利用者フローについて、その利用者フローが２箇所以上のリンクにおいて、他のフローとリンクを共有していない状態、及び、利用者フローを最低１つ含む任意の２つ以上のフローが、それらのフローのみで２箇所以上のリンクを共有している状態が発生しないように、前記試験フローを流す経路を決定する第三の手順を、
    コンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。

Images