(57)【要約】【目的】通信ネットワークシステムにおける通信品質の劣化箇所を、フロー品質情報に基づいて精度高く迅速に推定することが可能な品質劣化箇所推定装置の実現すること。【構成】フロー品質収集部１１と、経路情報収集部１２と、フロー品質／経由リンクテーブル管理部１３と、劣化閾値と非劣化閾値とに基づいて、品質劣化フロー及び品質非劣化フローを決定し、通過する品質非劣化フロー数が非劣化フロー数閾値以上であるような非劣化リンクを除去する非劣化リンク除去部１５と、品質劣化を起こした任意のフローの集合が経由するリンク集合から非劣化リンクを除去したリンク集合の部分集合の中で最小の要素数をもつ部分集合を、品質劣化箇所として出力する品質劣化箇所推定部１７とを有する。【選択図】図３
2007094170.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする品質劣化箇所推定装置。
【請求項２】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする品質劣化箇所推定装置。
【請求項３】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フローレート閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする品質劣化箇所推定装置。
【請求項４】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする品質劣化箇所推定装置。
【請求項５】
前記品質劣化フロー／品質非劣化フロー決定手段は、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成るリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フロー数閾値を変えることを特徴とする請求項1 に記載の品質劣化箇所推定装置。
【請求項６】
前記請求項３に記載の品質劣化箇所推定装置において、
前記品質劣化フロー／品質非劣化フロー決定手段は、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成り、かつ、前記リンクを含まないリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フローレート閾値を変えることを特徴とする品質劣化箇所推定装置。
【請求項７】
前記請求項１に記載の品質劣化箇所推定装置において、
前記品質劣化フロー／品質非劣化フロー決定手段は、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過し、かつ、前記品質劣化フロー集合に含まれない１つ以上の品質劣化フローが通過するようなリンクの有無によって、前記非劣化フロー数閾値を変えることを特徴とする品質劣化箇所推定装置。
【請求項８】
前記請求項３に記載の品質劣化箇所推定装置において、
前記品質劣化フロー／品質非劣化フロー決定手段は、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過するリンクの有無によって、前記非劣化フローレート閾値を変えることを特徴とする品質劣化箇所推定装置。
【請求項９】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集工程と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定工程と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定工程と
を有することを特徴とする品質劣化箇所推定方法。
【請求項１０】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集工程と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定工程と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定工程と  を有することを特徴とする品質劣化箇所推定方法。
【請求項１１】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集工程と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定工程と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フローレート閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定工程と  を有することを特徴とする品質劣化箇所推定方法。
【請求項１２】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集工程と、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定工程と、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前  記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数（フローレート）閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定工程とを有することを特徴とする品質劣化箇所推定方法。
【請求項１３】
前記請求項９に記載の品質劣化箇所推定方法において、
前記品質劣化フロー／品質非劣化フロー決定工程では、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成るリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フロー数閾値を変えることを特徴とする品質劣化箇所推定方法。
【請求項１４】
前記請求項１１に記載の品質劣化箇所推定方法において、
前記品質劣化フロー／品質非劣化フロー決定工程では、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成り、かつ、前記リンクを含まないリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フローレート閾値を変えることを特徴とする品質劣化箇所推定方法。
【請求項１５】
前記請求項９に記載の品質劣化箇所推定方法において、
前記品質劣化フロー／品質非劣化フロー決定工程では、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過し、かつ、前記品質劣化フロー集合に含まれない１つ以上の品質劣化フローが通過するようなリンクの有無によって、前記非劣化フロー数閾値を変えることを特徴とする品質劣化箇所推定方法。
【請求項１６】
前記請求項１１に記載の品質劣化箇所推定方法において、
前記品質劣化フロー／品質非劣化フロー決定工程では、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過するリンクの有無によって、前記非劣化フローレート閾値を変えることを特徴とする品質劣化箇所推定方法。
【請求項１７】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集機能、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定機能、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定機能、
をコンピュータに実行させることを特徴とした品質劣化箇所推定プログラム。
【請求項１８】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集機能、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定機能、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定機能、  をコンピュータに実行させることを特徴とした品質劣化箇所推定プログラム。
【請求項１９】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集機能、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定機能、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フローレート閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定機能、
をコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【請求項２０】
ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集機能、
前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定機能、
前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数（フローレート）閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定機能、
をコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【請求項２１】
前記請求項１７に記載の品質劣化箇所推定プログラムにおいて、
前記品質劣化フロー／品質非劣化フロー決定機能では、前記コンピュータによる実行内容を、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成るリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フロー数閾値を変えるようにプログラム化したことを特徴とする品質劣化箇所推定プログラム。
【請求項２２】
前記請求項１９に記載の品質劣化箇所推定プログラムにおいて、
前記品質劣化フロー／品質非劣化フロー決定機能では、前記コンピュータによる実行内容を、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成り、かつ、前記リンクを含まないリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フローレート閾値を変えるようにプログラム化したことを特徴とする品質劣化箇所推定プログラム。
【請求項２３】
前記請求項１７に記載の品質劣化箇所推定プログラムにおいて、
前記品質劣化フロー／品質非劣化フロー決定機能では、前記コンピュータによる実行内容を、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過し、かつ、前記品質劣化フロー集合に含まれない１つ以上の品質劣化フローが通過するようなリンクの有無によって、前記非劣化フロー数閾値を変えるようにプログラム化したことを特徴とする品質劣化箇所推定プログラム。
【請求項２４】
前記請求項１９に記載の品質劣化箇所推定プログラムにおいて、
前記品質劣化フロー／品質非劣化フロー決定機能では、前記コンピュータによる実行内容を、ある品質非劣化フローが通過するリンクを通過する、品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過するリンクの有無によって、前記非劣化フローレート閾値を変えるようにプログラム化したことを特徴とする請求項１９に記載の品質劣化箇所推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークシステムにおける通信品質の劣化箇所を推定するための、品質劣化箇所推定装置、品質劣化箇所推定方法、及び品質劣化箇所推定プログラムに関する。
【背景技術】
【０００２】
通信ネットワークにおいて、通信品質劣化時に、高速に通信品質劣化箇所を特定するには、まずネットワーク内に監視装置を多数配備して当該配備位置での通信品質を常に監視する。そして、通信品質劣化時には、品質劣化の起こっている監視装置の位置情報に基づいて、品質劣化している区間を推定するという手法が採られている。
しかしながら、この方式では、品質劣化している位置の推定精度を高めるに多数の監視装置が必要となり、その配置コストが高いという問題がある。この問題に対処する手法として、従来より、ネットワークを通過する通信フローの品質情報とルーティング情報から品質劣化箇所を推定する方式が提案されている（特許文献１参照）。
最初に、この従来例の方式について説明する。【０００３】
まず、各フローとそれらが経由するリンク（有向リンク）および品質の対応表（フロー・リンク対応表）を作る。そして、例えば、図２８に示したルータ（或いはパケットスイッチ）Ｒ１〜Ｒ６を含むネットワークにフローＦ１〜Ｆ５が存在するものとする。
図２８のネットワークに対し、図２９に示すようにリンクに名前を付け、品質としてパケットロス率を使い、フローＦ１〜Ｆ５のパケットロス率を、３．０〔％〕、２．５〔％〕、３．５〔％〕、１．０〔％〕、０．５〔％〕とすると、フロー・リンク対応表は図３０のようになる。ここで、各フローは１秒間に１００パケット流れるものとし、パケットロス率は、２秒毎のパケットロス数をもとに求めるものとする。【０００４】
次に、非劣化リンク除去処理を行う。即ち、予め決められた、フロー品質の劣化閾値と非劣化閾値から、劣化閾値より品質の悪いフローを劣化フロー、非劣化閾値より品質の良いフローを非劣化フロー、それ以外のフローを中間品質フローとし、フロー・リンク対応表から、中間品質フローの行、および非劣化フローの行および非劣化フローが経由するリンクの列を除いた縮小フロー・リンク対応表を作成する。【０００５】
上記例では、例えば、パケットロス率２〔％〕を劣化閾値、１〔％〕を非劣化閾値とすると、劣化フローはＦ１〜Ｆ３、  非劣化フローはＦ５、中間フローはＦ４となる。次に、フロー・リンク対応表から、中間フローの行を削除し、非劣化フローの行および非劣化フローの行に１がある列を削除した縮小フロー・リンク対応表を作成する。
上記例での削除の様子を図３１に示し、縮小フロー・リンク対応表を図３２に示す。【０００６】
最後に、図３２に基づいて劣化箇所を推定する。例えば、品質劣化フロー数に基づく推定法では、図３２の各リンクＬ１０，Ｌ２０，Ｌ５０，Ｌ４０を経由する品質劣化したフロー数は、それぞれ１，３，１，１であり、この中で最も経由するフロー数が多いＬ２０を劣化箇所として推定する。或いは、次に述べる最小リンク数の推定によって劣化箇所を推定する。【０００７】
最小リンク数推定法では、図３２の各リンクを経由するフロー集合を考え、最小の数のリンクで、図３２の全てのフローを包含するようなリンク集合を求め、それを劣化リンク集合とする。
即ち、図３２の例では、各リンクＬ１０，Ｌ２０，Ｌ５０，Ｌ４０を経由するフロー集合は、それぞれ、｛Ｆ１｝、｛Ｆ１，Ｆ２，Ｆ３｝、｛Ｆ２｝、｛Ｆ３｝である。たとえば、３つのリンクから成るリンク集合｛Ｌ１０，Ｌ５０，Ｌ４０｝を経由するフロー和集合は｛Ｆ１，Ｆ２，Ｆ３｝となり、全てのフローを包含出来る。これ以外にも、２つのリンクから成るリンク集合｛Ｌ１０，Ｌ２０｝や、１つのリンクから成るリンク集合｛Ｌ２０｝によっても全てのフローを包含できる。全てのフローを包含するようなリンク集合のうち、最小のリンク数をもつ｛Ｌ２０｝を最小リンク集合として推定する。
【特許文献１】特開２００２−２７１３９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述した従来の品質劣化箇所の推定方式では、非劣化リンク除去によって、フロー・リンクテーブルのサイズを小さくする事により、推定にかかる時間を低減させている。また、品質が劣化していないリンクを除去することにより、品質が劣化していないリンクが推定結果に含まれないようにすることで推定精度を向上させている。
しかしながら、品質劣化をおこしたリンクを経由するフローが全て品質劣化を起こすとは限らず、たまたま品質劣化を起こしたリンクを通ったフローが非劣化閾値よりも品質が良いケースが起こり得る。【０００９】
例えば、パケットロス率を品質指標として用いた場合、劣化リンクを経由したにもかかわらず、たまたまパケットロスが起こらず、パケットロス率が非劣化閾値より低いフローが生じ得る。
このため、従来の品質劣化箇所の推定方式では、非劣化リンク除去によって真の品質劣化リンクが除去されてしまい、品質劣化箇所の見逃しや品質が劣化していないリンクを劣化していると判断する誤警告が生じる場合がある。或いは、最小リンク数推定で、劣化箇所が見つからないケースが生じる。【００１０】
例えば、前記の例で、真の品質劣化リンクがＬ２０で、その他のリンクの品質が劣化していないとする。真の品質劣化リンクがＬ２０を経由したにもかかわらず、ある計測時間のフローＦ４のパケットロス率が低く、パケットロス率が０．５〔％〕であったとすると、フロー・リンク対応表は図３３のようになる。非劣化リンク除去を行うと、縮小フロー・リンク対応表は図３４のようになる。【００１１】
そして、図３４の縮小フロー・リンク対応表に基づいて品質劣化箇所を推定すると、品質劣化フロー数に基づく推定法及び最小リンク数推定法のいずれも、Ｌ１０，Ｌ５０，Ｌ４０の３つのリンクを劣化リンクと推定し、真の品質劣化リンクがＬ２０が求まらない見逃しを生じ、劣化していないＬ１０，Ｌ５０，Ｌ４０の３つのリンクを劣化リンクと推定する誤警告が生じる。【００１２】
別の例としては、上記の例で、真の品質劣化リンクがＬ２０で、その他のリンクの品質が劣化していないとする。
真の品質劣化リンクがＬ２０を経由したにもかかわらず、ある計測時間のフローＦ３のパケットロス率が低くパケットロス率が０．５〔％〕であったとし、且つフローＦ４は劣化を起こしてパケットロス率３〔％〕であったとする。この場合のフロー・リンク対応表は図３５のようになる。【００１３】
ここで、非劣化リンク除去を行うと、縮小フロー・リンク対応表は図３６のようになる。品質劣化フロー数に基づく推定法ではＬ１０，Ｌ５０を劣化箇所と推定し、最小リンク数推定法では全ての劣化フローＦ１，Ｆ２，Ｆ４を包含するリンク集合が見つからず、推定に失敗する。【００１４】
本発明は、従来例の有する不都合を改善し、品質劣化箇所を、フロー品質情報に基づいて精度高く推定することが可能な品質劣化箇所推定装置、品質劣化箇所推定方法及び品質劣化箇所推定プログラムを実現することにある。同時に、品質劣化箇所を高速に推定することが可能な品質劣化箇所推定装置、品質劣化箇所推定方法、及び品質劣化箇所推定プログラムを実現することにある。
【課題を解決するための手段】
【００１５】
本発明にかかる品質劣化箇所推定装置は、ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする。【００１６】
このため、これによると、通過する品質非劣化フロー数が、劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、劣化リンク推定の精度を高める事が可能となる。【００１７】
又、本発明にかかる品質劣化箇所推定装置は、ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フロー数が、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする。【００１８】
このため、これによると、通過する品質非劣化フロー数が、劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、かかる点において劣化リンク推定の精度を高める事ができる。【００１９】
更に、本発明にかかる品質劣化箇所推定装置は、ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フローレート閾値以上であるようなリンクを除去したリンク集合の部分集合の中で、品質劣化フローの中の任意のフローが経由しているリンクを含む部分集合であって、且つ、最小の要素数を持つ部分集合を、品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする【００２０】
このため、これによると、通過する品質非劣化フローの合計レートが、劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、かかる点において劣化リンク推定の精度を高める事ができる。【００２１】
又、本発明にかかる品質劣化箇所推定装置は、ネットワークを流れるフローの品質情報とフローレート及び前記ネットワークの構成情報を集める情報収集手段と、前記情報収集手段が収集した前記フロー品質情報と前記ネットワーク構成情報から前記フローが経由するリンクを求め、予め決められた劣化閾値と非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローとを決定する品質劣化フロー／品質非劣化フロー決定手段と、前記品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レートが、前記劣化閾値と前記フローレートとに基づいて決められた非劣化フロー数（フローレート）閾値以上であるようなリンクを除去したリンク集合の中で、各リンクを経由する品質劣化フローが多い順に、予め決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定手段とを有することを特徴とする。【００２２】
このため、これによると、通過する品質非劣化フローの合計レートが、劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、かかる点において、劣化リンク推定の精度を高める事ができる。【００２３】
ここで、前述した品質劣化フロー／品質非劣化フロー決定手段を、ある品質非劣化フローが通過するリンクを通過する品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成るリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フロー数閾値を変えるように構成しても良い。【００２４】
これにより、リンクを通過する全ての品質劣化フローについて、他のリンクの集合であって、  その要素リンクのいずれかを通過しているようなリンク集合が選べるとき、その最小のリンク集合の要素数に依存して、非劣化フロー数閾値を変え、通過する品質非劣化フロー数が、劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、劣化リンク推定の精度を高める事が可能な品質劣化箇所推定装置を実現することができる。【００２５】
又、前述した品質劣化フロー／品質非劣化フロー決定手段を、ある品質非劣化フローが通過するリンクを通過する品質劣化フローの集合について、前記品質劣化フロー集合の中のいずれかのフローが通過するリンクから成り、かつ、前記リンクを含まないリンク集合であって、そのリンク集合のいずれかを通過する品質劣化フローからなるフロー集合が、前記品質劣化フロー集合を包含するようなリンク集合の中で、最小のリンクから成る集合の要素数に依存して、前記非劣化フローレート閾値を変えることを特徴とする。【００２６】
これにより、リンクを通過する全ての品質劣化フローについて、他のリンクの集合であって、その要素リンクのいずれかを通過しているようなリンク集合が選べるとき、その最小のリンク集合の要素数に依存して、非劣化フローレート閾値を変え、通過する品質非劣化フローの合計レートが、劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去することができ、劣化リンク推定の精度を高める事が可能な品質劣化箇所推定装置を実現することができる。【００２７】
更に、前述した品質劣化フロー／品質非劣化フロー決定手段を、ある品質非劣化フローが通過するリンクを通過する品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過し、かつ、前記品質劣化フロー集合に含まれない１つ以上の品質劣化フローが通過するようなリンクの有無によって、前記非劣化フロー数閾値を変えるように構成してもよい。【００２８】
これにより、品質劣化フロー集合の中の全てのフローが通過し、かつ、品質劣化フロー集合に含まれない１つ以上の品質劣化フローが通過するようなリンクの有無によって、閾値を変えることで、劣化リンク推定の精度をより高める事が可能な品質劣化箇所推定装置を実現することができる。【００２９】
又、前述した品質劣化フロー／品質非劣化フロー決定手段については、これを、ある品質非劣化フローが通過するリンクを通過する品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過するリンクの有無によって、前記非劣化フローレート閾値を変えるように構成してもよい。
これにより、ある品質非劣化フローが通過するリンクを通過する品質劣化フローの集合について、前記品質劣化フロー集合の中の全てのフローが通過するリンクの有無によって、閾値を変えることで、劣化リンク推定の精度をより高める事が可能な品質劣化箇所推定装置を実現することができる。【００３０】
更に、本発明に係る品質劣化箇所推定方法は、上記の本発明に係る品質劣化箇所推定装置の各手段の動作を手順として捕らえ、その動作順序の工程実行により、前述した目的達成の手法が組み込まれていることを特徴とする。また、本発明に係る品質劣化箇所推定プログラムは、本発明に係る品質劣化箇所推定方法の各手順をコンピュータに実行させるように構成して成るものである。
【発明の効果】
【００３１】
本発明は上述したように構成され機能するので、これによると、非劣化リンクを効率よく除去するようにしたので劣化リンク推定の精度を高める事ができ、これにより品質劣化箇所を高精度に推定することができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施形態を図に基づいて説明する。【００３３】
先ず、各実施形態の基本的構成について説明し、次いで、その実施形態を具体的に説明する。
図１乃至図３に示すように、符号１０は品質劣化箇所推定装置としての品質劣化箇所推定サーバを示す。実施形態１に係る品質劣化箇所推定サーバ１０は基本的構成として、ネットワークを流れるフロー品質情報とフローレートを収集するフロー品質収集手段としてのフロー品質収集部１１と、ネットワークの構成情報を集める経路情報収集手段としての経路情報収集部１２と、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求めると共にそれらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理手段としてのフロー品質／経由リンクテーブル管理部１３とを備えている。【００３４】
更に、実施形態１に係る品質劣化箇所推定サーバ１０は、前記管理テーブルにおいて１つ以上フローの品質の劣化があった場合に予め決められた劣化閾値及び非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローを決定すると共に、品質劣化フローが経由するリンク集合から，通過する品質非劣化フロー数が劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去する非劣化リンク除去手段としての非劣化リンク除去部１５と、品質劣化を起こした任意のフローの集合が経由するリンクから前記非劣化リンクを除去した集合の部分集合の中で，品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって且つ最小の要素数をもつ部分集合を，品質劣化箇所として出力する品質劣化箇所推定部１７と、この出力される品質劣化箇所にかかる情報を表示する表示部１８とを備えている。【００３５】
実施形態２に係る品質劣化箇所推定装置は基本的構成として、前述した実施形態１の場合と同様に、ネットワークを流れるフロー品質情報とフローレートとを収集するフロー品質収集部１１と、ネットワークの構成情報を集める経路情報収集部１２と、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求め，それらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理部１３とを備えている。【００３６】
更に、実施形態２に係る品質劣化箇所推定装置は、前記管理テーブルにおいて１つ以上フローの品質の劣化があった場合に予め決められた劣化閾値及び非劣化閾値に基づいて，品質劣化フロー，品質非劣化フローを決定すると共に，品質劣化フローが経由するリンク集合から，通過する品質非劣化フロー数が，劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去する非劣化リンク除去部１５と、品質劣化を起こした任意のフローの集合が経由するリンクから前記非劣化リンクを除去した集合の中で，各リンクを経由する品質劣化フローが多い順に予め決められた順位以上のリンクを品質劣化箇所として出力するように機能する品質劣化箇所推定部１７と、この出力される品質劣化箇所にかかる情報を表示する表示部１８とを備えている。
実施形態２では、前述した実施形態１とは品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の処理動作が異なる構成となっている。【００３７】
実施形態３に係る品質劣化箇所推定装置は基本的構成として、前述した実施形態１の場合と同様に、ネットワークを流れるフロー品質情報とフローレートを収集するフロー品質収集部１１と、ネットワークの構成情報を集める経路情報収集部１２と、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求めてそれらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理部１３とを備えている。【００３８】
更に、実施形態３に係る品質劣化箇所推定装置は、前記管理テーブルにおいて１つ以上フローの品質の劣化があった場合に予め決められた劣化閾値及び非劣化閾値に基づいて品質劣化フロー及び品質非劣化フローを決定し，品質劣化フローが経由するリンク集合から、通過する品質非劣化フローの合計レート数が劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去する非劣化リンク除去部１５と、品質劣化を起こした任意のフローの集合が経由するリンクから前記非劣化リンクを除去した集合の部分集合の中で，品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって且つ最小の要素数をもつ部分集合を，品質劣化箇所として出力する品質劣化箇所推定部１７と、この出力される品質劣化箇所にかかる情報を表示する表示部１８とを備えている。
実施形態３では、前述した実施形態１とは品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の処理動作が異なる構成となっている。【００３９】
実施形態４に係る品質劣化箇所推定装置は、前述した実施形態１の場合と同様に、ネットワークを流れるフロー品質情報とフローレートを収集するフロー品質収フロー品質収集部１１と、ネットワークの構成情報を集める経路情報収集部１２と、前記フロー品質情報とネットワークの構成情報から前記フローが経由するリンクを求めそれらをテーブル形式で管理しておくフロー品質／経由リンクテーブル管理部１３とを備えている。【００４０】
更に、実施形態４に係る品質劣化箇所推定装置は、前記管理テーブルにおいて１つ以上フローの品質の劣化があった場合に予め決められた劣化閾値及び非劣化閾値に基づいて品質劣化フローと品質非劣化フローとを決定し，品質劣化フローが経由するリンク集合から，通過する品質非劣化フローの合計レート数が劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去する非劣化リンク除去手段１５と、品質劣化を起こした任意のフローの集合が経由するリンクから前記非劣化リンクを除去した集合の中で，各リンクを経由する品質劣化フローが多い順にあらかじめ決められた順位以上のリンクを品質劣化箇所として出力する品質劣化箇所推定部１７と、この出力される品質劣化箇所にかかる情報を表示する表示部１８とを備えている。
実施形態４では、前述した実施形態１とは品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の処理動作が異なる構成となっている。【００４１】
また、実施形態１において、非劣化リンク除去１５が、リンクを通過する全ての品質劣化フローについて、他のリンクの集合であって、その要素リンクのいずれかを通過しているようなリンク集合が選べるとき、その最小のリンク集合の要素数に依存して非劣化フロー数閾値を変える構成としてもよいものである。この実施形態を実施形態５とする。また、実施形態３において、非劣化リンク除去１５が、リンクを通過する全ての品質劣化フローについて、他のリンクの集合であって、その要素リンクのいずれかを通過しているようなリンク集合が選べるとき、その最小のリンク集合の要素数に依存して非劣化フロー数閾値を変える構成としてもよいものである。この実施形態を実施形態６とする。【００４２】
上記実施形態１〜４にあって、品質劣化箇所推定装置では、通過する品質非劣化フロー数が，劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去することにより、十分高い確率で非劣化であるリンクを除去している。このため、劣化リンク推定の精度を高める事ができる。【００４３】
又、実施形態３、４にあって、品質劣化箇所推定装置では、通過する品質非劣化フローの合計レートが、劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去することにより，十分高い確率で非劣化であるリンクを除去している。このため、劣化リンク推定の精度を高める事ができる。【００４４】
更に、実施形態５に係る品質劣化箇所推定装置では、リンクを通過する全ての品質劣化フローについて，他のリンクの集合であって，その要素リンクのいずれかを通過しているようなリンク集合が選べるとき，その最小のリンク集合の要素数に依存して，非劣化フロー数閾値を変え，通過する品質非劣化フロー数が，劣化閾値とフローレートに基づいて決められた非劣化フロー数閾値以上であるような非劣化リンクを除去することにより，十分高い確率で非劣化であるリンクを除去している。このため、かかる観点において劣化リンク推定の精度を高める事ができる。【００４５】
実施形態６に係る品質劣化箇所推定装置では、リンクを通過する全ての品質劣化フローについて，他のリンクの集合であってその要素リンクのいずれかを通過しているようなリンク集合が選べるとき、その最小のリンク集合の要素数に依存して非劣化フローレート閾値を変え、通過する品質非劣化フローの合計レートが劣化閾値とフローレートに基づいて決められた非劣化フローレート閾値以上であるような非劣化リンクを除去することにより，十分高い確率で非劣化であるリンクを除去している。このため、かかる観点において劣化リンク推定の精度を高める事ができる。【００４６】
次に、各実施形態について具体的に説明する。【００４７】
（実施形態１）
図１に、本発明の実施形態１におけるネットワーク構成図を示す。このネットワークにはルータ（或いはスイッチ）Ｒ１〜Ｒ６及び品質劣化箇所推定サーバ１０が配置され、これらのルータＲ１〜Ｒ６には、図１に示すようにアドレスＴ１１〜Ｔ１ｎ……Ｔ６１〜Ｔ６ｎを有するこれらに属する端末が接続されている。前記ネットワークに含まれるルータＲ１−Ｒ６の相互間には、フローＦ１〜Ｆ５が形成されている。前記フローＦ１〜Ｆ５は、送信系と受信系との双方向のフローであるから、図２に示すように送信系と受信系とのフローＦ１〜Ｆ５にリンク名が付されている。すなわち、図１に示すフローＦ１については、送信系のフローにリンクＬ１０が付され、受信系のフローにリンクＬ１５が付されている。図１に示すフローＦ２については、送信系のフローにリンクＬ２０が付され、受信系のフローにリンクＬ２５が付されている。図１に示すフローＦ３については、送信系のフローにリンクＬ３０が付され、受信系のフローにリンクＬ３５が付されている。図１に示すフローＦ４については、送信系のフローにリンクＬ４０が付され、受信系のフローにリンクＬ４５が付されている。図１に示すフローＦ５については、送信系のフローにリンクＬ５０が付され、受信系のフローにリンクＬ５５が付されている。【００４８】
図１において、前記ルータＲ１〜Ｒ６に接続される前記端末は、アドレスＴ１１〜Ｔ１ｎ……Ｔ６１〜Ｔ６ｎをもつ送信端末或いは受信端末として機能する。以下の説明では、アドレスＴ１１〜Ｔ１ｎ……Ｔ６１〜Ｔ６ｎをもつ端末が送信端末して機能する場合には、送信端末ＴＳ１〜ＴＳ５として表記する。アドレスＴ１１〜Ｔ１ｎ……Ｔ６１〜Ｔ６ｎをもつ端末が受信端末して機能する場合には、受信端末ＴＲ１〜ＴＲ５として表記する。【００４９】
図２では、ルータＲ１〜Ｒ６相互間のリンクについてもにリンク名を付しているが、ルータＲ１〜Ｒ６と、アドレスＴ１１〜Ｔ１ｎ……Ｔ６１〜Ｔ６ｎをもつ端末との間に存在するリンクについては、リンク名を省略している。図１及び図２では、送信端末ＴＳ１〜ＴＳ５、受信端末ＴＲ１〜ＴＲ５は、単一のフローで結ばれた相手方の端末のみに対して送受信を行うように図示しているが、送信端末ＴＳ１〜ＴＳ５、受信端末ＴＲ１〜ＴＲ５は、複数のフローを通して相手方の端末に対して送受信を行うものである。【００５０】
また、図３に、実施形態１における品質劣化箇所推定サーバ１０の内部構成図を示す。図３において、品質劣化箇所推定サーバ１０は、前述したように、フロー品質収集手段としてのフロー品質収集部１１と、経路情報収集手段としての経路情報収集部１２と、フロー品質／経由リンクテーブル管理手段としてのフロー品質／経由リンクテーブル管理部１３とを備えている。【００５１】
更に、この品質劣化箇所推定サーバ１０は、所定の条件の基に非劣化リンクを除去する非劣化リンク除去手段としての非劣化リンク除去部１５と、前記非劣化リンクを除去した集合の部分集合の中で，品質劣化を起こした任意のフローが経由しているリンクを含む部分集合であって且つ最小の要素数をもつ部分集合を，品質劣化箇所として出力する品質劣化箇所推定部１７と、この出力される品質劣化箇所にかかる情報を表示する表示部１８とを備えている。【００５２】
これらは、実際には端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５からフロー毎の品質情報を集め、ルータ（或いはスイッチ）Ｒ１〜Ｒ６から得た経路情報を基に、品質劣化箇所を推定し、推定結果を表示部１８に出力する。【００５３】
実施形態１では、フロー品質情報収集部１１と経路情報収集部１２とにより情報収集手段１０１が構成され、フロー品質／経由リンクテーブル管理部１３，フロー品質／経由リンクテーブル記憶部１４，非劣化リンク除去部１５，及び縮小フロー品質／経由リンクテーブル記憶部１６により品質劣化フロー・品質費劣化フロー決定手段１０２が構成されている。また、品質劣化箇所推定部１７及び表示部１８により品質劣化箇所推定手段１０３が構成されている。【００５４】
次に、上記各構成要素の具体的な内容を説明する。【００５５】
（フロー品質情報収集部１１）
端末が通信開始すると、フロー品質情報収集部１１は、端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５から通信を開始する旨を通知され、通信開始以降、端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５から端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５の現在の通信品質情報、および、フローレートを受け取る。すなわち、送信端末ＴＳ１〜ＴＳ５のアドレス、受信端末ＴＲ１〜ＴＲ５のアドレス、フロー品質情報及びパケットレートからなる情報の組を受け取る。端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５が通信を終了すると、フロー品質情報収集部１１は、前記端末から通信終了の通知を受け取る。ここで、フロー品質情報とは、例えば、パケットロス率、遅延、遅延ジッタなどの通信品質に関わる情報である。パケットレートとは、通信に使われたフローの１秒あたりのパケット数の情報である。【００５６】
（経路情報収集部１２）
経路情報収集部１２は、ルータ( 或いはスイッチ) Ｒ１〜Ｒ６から、ルーティングに関する情報を収集する。前記情報の収集には、ＳＭＴＰ(Simple Network Management Protocol)等を使って行う事が可能である。経路情報収集部１２は、ルーティングに関する情報があれば、送受信端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５のアドレス情報から、該送受信端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５間の通信がどの経路で行われるかを決定する。具体的には、ルータから収集する場合には、ルーティングテーブルとＡＲＰテーブルを収集し、ルータ以外のスイッチから収集する場合には、フォワーディングデーターベースと、スパニングツリーの構成情報を収集する。なお、この情報は、経路情報収集部１２がルータ（或いはスイッチ）Ｒ１〜Ｒ６から収集することに代えて、ネットワーク管理者が経路情報収集部１２に与える事も可能である。【００５７】
（フロー品質／経由リンクテーブル管理部１３）
フロー品質／経由リンクテーブル管理部１３は、フロー品質情報収集部１１から得たフロー品質情報と、経路情報収集部１２からのルーティングに関する情報に基づいて、現在通信が行われているフローについて、送受信端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５のアドレス、それらが現在経由しているリンク集合と、そのフローの現在のフロー品質、フローレートの情報から成るフロー品質／経由リンクテーブルを維持する。【００５８】
ここで、リンクとは、ルータ（或いはスイッチ）Ｒ１〜Ｒ６間、ルータ（或いはスイッチ）Ｒ１〜Ｒ６と端末ＴＳ１〜ＴＳ５、ＴＲ１〜ＴＲ５間の有向リンクとする。例えば、図１に示した、ネットワーク構成図の場合、図２に示すような有向リンクである。【００５９】
図４に、フロー品質／経由リンクテーブル管理部１３の動作をフローチャートで示す。  図４において、フロー品質／経由リンクテーブル管理部１３がフロー品質情報収集部１１からフロー品質情報を受け取った場合（ステップＳ１０１）、もし、それが通信終了を示すものであれば（ステップＳ１０２）、該当フローをフロー品質／経由リンクテーブルから除去する（ステップＳ１０５）。そうでなく、通信開始を示すものであれば（ステップＳ１０３）、フロー品質／経由リンクテーブル管理部１３は、現在のルーティングに関する情報を経路情報収集部１２から得て、フロー品質情報の送信端末ＴＳ１〜ＴＳ５のアドレス及び受信端末ＴＲ１〜ＴＲ５のアドレスの情報から経由リンクを決定し（ステップＳ１０６）、フロー品質／経由リンクテーブルへ登録する（ステップＳ１０７）。通信開始を示すものでない場合、それは今登録されているフローの最新の通信品質を通知するものであるので、フロー品質／経由リンクテーブル管理部１３、フロー品質／経由リンクテーブルの通信品質情報を更新する（ステップＳ１０４）。【００６０】
経路情報収集部１２から経路情報を受信した場合（ステップＳ１０８）、フロー品質／経由リンクテーブル管理部１３は、経路情報に変更があれば（ステップＳ１０９）、現在のフロー品質／経由リンクテーブルに登録されている全フローについて、テーブルの送信端末ＴＳ１〜ＴＳ５のアドレス及び受信端末のアドレスの情報と、現在のルーティングに関する情報（変更後のもの）を基に経由リンクを決定し、フロー品質／経由リンクテーブルを更新する（ステップＳ２００）。【００６１】
（フロー品質／経由リンクテーブル記憶部１４）
フロー品質／経由リンクテーブル記憶部１４は、フロー品質／経由リンクテーブル管理部１３が管理するフロー品質／経由リンクにかかる情報を記憶している。【００６２】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部１４からフロー品質／経由リンクテーブルの情報を読み出し、予め決められた劣化閾値より品質が悪いフローの行を抽出する。非劣化リンク除去部１５は、前記劣化閾値より品質が悪いフローが存在する場合、次に述べる非劣化リンク判定法により非劣化リンク除去処理を行い、品質情報、フローレート情報を除いた、縮小フロー品質／経由テーブルを生成し、縮小フロー品質／経由テーブル記憶部１６に書き込む。【００６３】
（非劣化リンク判定法（１））
非劣化リンク除去部１５は、フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとし、非劣化フローの本数が、予め決められた非劣化フロー数閾値以上のリンクを非劣化リンクとして判定する。【００６４】
図５に非劣化リンク除去部１５の動作フローチャートを示す。非劣化リンク除去部１５は、フロー品質／経由リンクテーブル記憶部１４からフロー品質／経由リンクテーブルを読み込み（ステップＳ２０１）、品質劣化フローが存在するかどうかを判定する（ステップＳ２０２）。非劣化リンク除去部１５は、品質劣化フローが存在すると判定した場合、品質劣化フローを含む行を抽出し（ステップＳ２０３）、非劣化リンク判定法により、品質非劣化リンクを削除して（ステップＳ２０４）、残りから得られた縮小フロー品質／経由リンクテーブルを縮小フロー品質／経由リンクテーブル記憶部１６に書き込む。ステップＳ２０２において、非劣化リンク除去部１５は、品質劣化フローが存在しないと判定した場合、そのまま終了する。【００６５】
図６にフロー品質／経由リンクテーブルの一例をしめす。図６において、非劣化リンク判定法（１）を用い、パケットロス率２〔％〕を劣化閾値、パケットロス率０．６〔％〕を非劣化閾値、非劣化フロー数閾値を「２」とすると、図７の太枠で示す劣化フローが選ばれ、横方向の点線で示された非  劣化フローが２本以上経由するリンク（縦の点線で示したリンク）を除去し、図８のような縮小フロー品質／経由テーブルが得られる。【００６６】
（品質劣化箇所推定部１７）
品質劣化箇所推定部１７は、縮小フロー／経由テーブル記憶部１６から縮小フロー品質／経由テーブルを読み出し、品質劣化フロー数に基づく推定法、或いは、最小リンク数推定法を用いて、品質劣化箇所を推定し、表示部１８へ出力する。
品質劣化箇所推定部１７は、品質劣化フロー数に基づく推定法を用いる場合、縮小フロー／経由テーブルの各列に立っている１の数を数え、その数が大きいものから並べ、予め決められた順位までに含まれるリンクを劣化箇所と推定する。  例えば図８のような縮小フロー／経由テーブルの場合、リンクＬ２０、Ｌ４０、Ｌ５０に立っている１の数はそれぞれ、４，３，２であり、この中で２位までに含まれるリンクを劣化箇所として推定する場合、Ｌ２０，Ｌ４０が劣化箇所として推定される。１位までに含まれるリンクを劣化箇所として推定する場合Ｌ２０が劣化箇所として推定される。【００６７】
品質劣化箇所推定部１７が最小リンク数に基づく推定法を用いる場合、フロー品質／経由リンクテーブルの経由リンクの列について、１が立っているフローの集合を、そのリンク列に属するフロー集合とする。例えば、図８に示す縮小フロー品質／経由リンクテーブルの場合、経由リンクＬ２０の列に属するフロー集合は、｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１２｝である。さらに、複数の経由リンクの列のそれぞれに属するフロー集合の和集合も同様に、それらのリンク列の集合に属するフロー集合である。例えば、図８に示す縮小フロー品質／経由リンクテーブルの場合、リンク列の集合｛Ｌ４０，Ｌ５０｝に属するフロー集合は、｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１２｝となる。【００６８】
（最小リンク数推定法）
品質劣化箇所推定部１７は、最小リンク数に基づく推定法を用いる場合、リンク列の集合に属するフロー集合が、縮小フロー品質／経由リンクテーブルの全フローと同一になる経由リンク列の集合のうち、最小の要素数からなるものを選ぶ。例えば、図８に示す縮小フロー品質／経由リンクテーブルについて、最小リンク数推定法を実行する場合を説明する。【００６９】
経由リンク列の集合に属するフロー集合が縮小フロー品質／経由リンクテーブルの全フロー、すなわち、｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１２｝となるようなリンク集合は、｛Ｌ２０｝、｛Ｌ２０，Ｌ４０｝、｛Ｌ２０，Ｌ５０｝、｛Ｌ４０，Ｌ５０｝、｛Ｌ２０，Ｌ４０、Ｌ５０｝があるが、最小の要素数を持つものは、｛Ｌ２０｝だけ（要素数１)である。したがって、品質劣化箇所推定部１７は、Ｌ２０が劣化リンクとして推定する。なお、最小リンク数推定は、最小被覆問題のアルゴリズムを用いて解く事が可能である。【００７０】
実施形態１によれば、非劣化リンク除去において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。
例えば、図６のようなフロー品質／経由リンクテーブルにおいて、リンクＬ２０が真の劣化リンクとする。フローＦ１は、劣化リンクを経由したために、たまたまフロー品質が高かった（パケットロス率が低かった）フローである。【００７１】
又、提案方式と同じパケットロス率０．６〔％〕を非劣化閾値とし、従来法で非劣化リンク除去処理を行うと、フローＦ１がリンクＬ２０を経由することにより、除去されてしまい、推定精度が悪化する。更に、フローＦ１を含まないような非劣化閾値として０．４〔％〕未満の値を非劣化閾値として選ぶと、フローＦ５，Ｆ６，Ｆ７，Ｆ８，Ｆ１３〜Ｆ１６が非劣化となり、図１１のように縮小フロー品質／経由リンクテーブルのサイズが大きくなってしまい、推定時間が増大してしまう。【００７２】
これに対し、実施形態１では、非劣化リンク判定法１を用いて、複数の非劣化フローが経由するリンクのみを除去することで、たまたま品質が良いフローが存在することによって、劣化リンクが除外されてしまう確率を減らし、リンクＬ２０を除外することを防止しつつ、リンクＬ１０を除外している。実施形態１では、非劣化フロー数閾値を、劣化閾値に応じて変えることで、たまたま品質が良いフローが存在することによって、劣化リンクが除外されてしまう確率を制御することが出来る。【００７３】
（実施形態２）
次に、本発明の実施形態２を説明する。【００７４】
実施形態２は、実施形態１とは品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の処理動作が異なる構成となっている。このため、以下、この異なる部分について説明する。【００７５】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部１４からフロー品質／経由リンクテーブルを読み出し、予め決められた劣化閾値より品質が悪いフローの行を抽出する。非劣化リンク除去部１５は、前記閾値より品質が悪いフローが存在する場合、非劣化リンク判定法（２）により非劣化リンク除去処理を行い、品質情報及びフローレート情報を除いた縮小フロー品質／経由テーブルを生成し、縮小フロー品質／経由テーブル記憶部１６に書き込む。【００７６】
（非劣化リンク判定法（２））
非劣化リンク除去部１５は、非劣化リンク判定法（２）を用いる場合、フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとし、各非劣化フローについてフローレートを加えた値が計測間隔および劣化閾値に基づいて決められた非劣化フローレートの閾値以上のリンクを、非劣化リンクとして判定する。【００７７】
図６において、非劣化リンク除去部１５は、非劣化リンク判定法（２）を用いて、パケットロス率２〔％〕を劣化閾値、パケットロス率０．６〔％〕を非劣化閾値、非劣化フローレート閾値を６０パケット／秒として、図９の太枠で示す劣化フローを選定し、横方向の点線で示された非劣化フローの合計レートが６０パケット／秒以上であるリンク( 縦の点線で示したリンク) を除去し、図１０のような縮小フロー品質／経由テーブルを得る。【００７８】
実施形態２によれば、非劣化リンク除去において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。【００７９】
例えば、図６のようなフロー品質／経由リンクテーブルにおいて、リンクＬ２０が真の劣化リンクとする。フローＦ１は、劣化リンクを経由したために、たまたまフロー品質が高かった( パケットロス率が低かった) フローである。提案方式と同じパケットロス率０．６〔％〕を非劣化閾値とし、従来法の非劣化リンク除去処理を行うと、フローＦ１がリンクＬ２０を経由することにより、除去されてしまい、推定精度が悪化する。
また、フローＦ１を含まないような非劣化閾値として、０．４〔％〕未満の値を非劣化閾値として選定すると、フローＦ５，Ｆ６，Ｆ７，Ｆ８，Ｆ１３〜Ｆ１６が非劣化となり、図１１のように縮小フロー品質／経由リンクテーブルのサイズが大きくなってしまい、推定時間が増大してしまう。【００８０】
これに対し、実施形態２では、非劣化リンク判定法（２）を用い、非劣化フローの合計レートが非劣化フローレート閾値を超えるリンクのみを除去することで、たまたま品質が良いフローが存在することによって、劣化リンクが除外されてしまう確率を減らし、リンクＬ２０を除外することを防ぎつつ、リンクＬ１０、Ｌ４０を除外している。実施形態２では、非劣化フローレート閾値を劣化閾値に応じて変えることで、たまたま品質が良いフローが存在することによって、劣化リンクが除外されてしまう確率を制御することが出来る。【００８１】
（実施形態３）
次に、実施形態３を説明する。実施形態３は、前述した実施形態１における品質劣化箇所推定サーバ１０の非劣化リンク除去部１５について、その動作機能のみが異なる構成となっている。このため、この異なる点について説明する。【００８２】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部１４から、フロー品質／経由リンクテーブルを読み出し、予め決められた劣化閾値より品質が悪いフロー（劣化フロー）の行を抽出する。非劣化リンク除去部１５は、前記閾値より品質が悪いフローが存在する場合、非劣化リンク判定法（３）により決定される非劣化リンク集合Ｒをのぞき、品質情報、フローレート情報を除いた、縮小フロー品質／経由テーブルを生成し、これを縮小フロー品質／経由テーブル記憶部１６に書き込む。【００８３】
（非劣化リンク判定法（３））
非劣化リンク除去部１５は、非劣化リンク判定法（３）を用いる場合、劣化リンクが１本以上経由する全てのリンクについて、そのリンクを経由する劣化フロー集合を求める。以下では、あるリンクが包含する劣化フローというのは、そのリンクを経由する劣化フローを意味し、あるリンク集合が包含する劣化フローというのは、そのリンクのいずれか１つ以上を経由する劣化フローの集合を意味するものとする。【００８４】
図１２に、実施形態３における非劣化リンク判定法での動作のフローチャートを示す。フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとする。【００８５】
非劣化リンク除去部１５は、劣化フローが経由する全リンク集合をＬ０、Ｒを空集合とする（ステップＳ３０１）。Ｌ＝Ｌ０とする。非劣化リンク除去部１５は、前記Ｌが空集合なら、処理を終了する（ステップＳ３０２）。非劣化リンク除去部１５は、前記Ｌが空集合でない場合、前記Ｌから１つのリンクｖを選び、前記Ｌからリンクｖを除く（ステップＳ３０３）。Ｔは、前記全リンク集合Ｌ０から前記リンクｖ及び前記空集合Ｒの要素を除いたものとする。【００８６】
非劣化リンク除去部１５は、前記リンクｖが１本以上の非劣化フローを経由しているかどうかを判定し（ステップＳ３０４）、１本以上の非劣化フローを経由している場合、処理をステップＳ３０５へ移行させ、そうでなければ処理をステップＳ３０２へ戻す。
非劣化リンク除去部１５は、処理をステップＳ３０５に移行させた場合、前記リンクｖを包含する劣化フロー集合を求める。非劣化リンク除去部１５は、前記Ｔの部分集合によって、その劣化フロー集合を包含する部分集合のうち、最小の要素数をもつものの要素数Ｘを求める（ステップＳ３０５）。非劣化リンク除去部１５は、どのような部分集合でも、該劣化フロー集合が包含出来ない場合、要素数を無限大とする。【００８７】
非劣化リンク除去部１５は、ステップＳ３０５で求めた要素数Ｘに応じた非劣化フロー数閾値を、予め決められた対応表から決定する（ステップＳ３０６）。非劣化リンク除去部１５は、前記リンクｖを経由する非劣化フロー数が、ステップＳ３０６で求めた非劣化フロー数閾値以上の場合（ステップＳ３０７）、そのリンクｖを除去リンク集合Ｒへ追加する（ステップＳ３０８）。その後、非劣化リンク除去部１５は、処理をステップＳ３０２へ移行させる。
ステップＳ３０６で用いる最小要素数に応じた非劣化フロー数閾値の対応表は、最小要素数が増大するほど、非劣化フロー数閾値が増大するように決め、また、最小要素数が∞の時には、非劣化フロー数閾値は∞になるように決めておく。
以上の手順の終了時に、集合Ｒに含まれるリンクが除去される非劣化リンクである。【００８８】
次に、図６のフロー品質／経由リンクテーブルの例を用いて、非劣化リンク判定法（３）を用いた非劣化リンク除去部１５の動作を説明する。【００８９】
ここで、ステップＳ３０６での要素数と非劣化フローの閾値は図１３に示す値であったとする。また、パケットロス率２〔％〕を劣化閾値、パケットロス率０．６〔％〕を非劣化閾値とする。【００９０】
まず、図１４の太枠で示すものが劣化フローである。また、横方向の点線で記したフローが非劣化フローである。
ステップＳ３０１ではＬ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、ｔ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｒ＝｛  ｝となる。ステップＳ３０２において、ｖ＝Ｌ１０とすると、Ｌ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝となる。
ステップＳ３０４では、ｖを通過する非劣化フロー数は３である。ステップＳ３０５では、ｖが包含する劣化フロー集合は｛Ｆ３，Ｆ１１｝であり、Ｌ２０が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。
ステップＳ３０６で、図１３の最小要素数１に対応する非劣化フロー数閾値は１であるため、ステップＳ３０７で非劣化フロー数３がこの閾値１以上であることから、ステップＳ３０８で、Ｒ＝｛Ｌ１０｝となる。その後、ステップＳ３０２へ戻る。【００９１】
ステップＳ３０２で、ｖ＝Ｌ２０とし、Ｌ＝｛Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ４０，Ｌ５０｝となる。ステップＳ３０４では、ｖを通過する非劣化フロー数は１である。ステップＳ３０５では、ｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝であり、これを包含するＬの部分集合はないため、最小要素数Ｘは∞である。【００９２】
次に、ステップＳ３０５で、図１３の最小要素数∞に対応する非劣化フロー数閾値は∞であるため、ステップＳ３０７で非劣化フロー数３がこの閾値∞未満であることから、ステップＳ３０８で、Ｒ＝｛Ｌ１０｝のままとなる。そうして、ステップＳ３０２へ再び戻る。【００９３】
ステップＳ３０２でｖ＝Ｌ４０とし、Ｌ＝｛Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ５０｝となる。ステップＳ３０４では、ｖを通過する非劣化フロー数は２である。ステップＳ３０５では、ｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０｝であり、Ｔの部分集合である｛Ｌ２０｝が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。
ステップＳ３０６で、図１３の最小要素数１に対応する非劣化フロー数閾値は１であるため、ステップＳ３０７で非劣化フロー数２がこの閾値１を越えることから、ステップＳ３０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。再びステップＳ３０２へ戻る。【００９４】
ステップＳ３０２でｖ＝Ｌ４０とし、Ｌ＝｛  ｝、Ｔ＝｛Ｌ２０｝となる。ステップＳ３０４では、ｖを通過する非劣化フロー数は２である。ステップＳ３０５では、ｖが包含する劣化フロー集合は｛Ｆ２  ｝であり、Ｔの部分集合である｛Ｌ２０｝が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。
ステップＳ３０６で、図１３の最小要素数１に対応する非劣化フロー数閾値は１であるため、ステップＳ３０７で非劣化フロー数２がこの閾値１を越えることから、ステップＳ３０８で、Ｒ＝｛Ｌ１０，Ｌ４０，Ｌ５０｝となる。再びステップＳ３０２へ戻る。
ステップＳ３０２では、Ｌが空集合であるため停止する。
よって、図１４のようにＲ＝｛Ｌ１０，Ｌ４０，Ｌ５０｝を非劣化リンクとして除去し、図１５のような縮小フロー/ リンクテーブルを得ることができる。【００９５】
（品質劣化箇所推定部１７）
品質劣化箇所推定部１７は、縮小フロー品質／経由テーブル記憶部１６から縮小フロー品質／経由テーブルを読み出し、縮小フロー品質／経由テーブルに基づいて最小リンク数推定法を用いることで品質劣化箇所を推定する。【００９６】
実施形態３によれば、非劣化リンク除去において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。
各リンクの劣化確率を同一と考えると、出来るだけ小さい数のリンクの劣化によって、現在の劣化状況を説明する方が、現在の劣化状況が発生した条件下で、より高い確率での正しい説明であると言える。なぜなら、同時に複数のリンクが劣化する確率は、リンク数が増大するほど小さくなるからである。【００９７】
したがって、あるリンクを非劣化として除去する事によって、最小リンク数推定結果のリンク数が増大する場合、そのリンクを非劣化と判断した事が誤りである確率が高い。非劣化リンク判定法３のステップＳ３０６における最小要素数が１より大きくなればなるほど、そのリンクを除去した場合に、最小リンク数推定の結果得られる劣化リンクの数が増大する。【００９８】
また、最小要素数に対する非劣化フロー数閾値の対応表では、最小要素数が増大するほど、非劣化フロー数閾値が増大するように決めてある。
以上のことから、多数の非劣化フローが存在する場合、すなわち、高い確率で非劣化である場合にのみ、最小リンク数推定の結果得られる劣化リンクの数が増大するような非劣化リンク除去が行われる事になり、非劣化リンク除去を正しく行える確率が高くなる。【００９９】
（実施形態４）
実施形態４は、前述した実施形態１における品質劣化箇所推定サーバ１０の非劣化リンク除去部１５について、その動作のみが異なる構成となっている。このため、以下、異なる点のみ説明する。【０１００】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部１４から、フロー品質／経由リンクテーブルを読み出し、あらかじめ決められた劣化閾値より品質が悪いフロー（劣化フロー）の行を抽出する。非劣化リンク除去部１５は、前記閾値より品質が悪いフローが存在する場合、非劣化リンク判定法（４）により決定される非劣化リンク集合Ｒをのぞき、品質情報、フローレート情報を除いた、縮小フロー品質／経由テーブルを生成し、これを縮小フロー品質／経由リンクテーブル記憶部１６に書き込む。【０１０１】
（非劣化リンク判定法（４））
劣化リンクが１本以上経由する全てのリンクについて、そのリンクを経由する劣化フロー集合を求める。以下では、或るリンクが包含する劣化フローというのは、そのリンクを経由する劣化フローを意味し、或るリンク集合が包含する劣化フローというのは、そのリンクのいずれか１つ以上を経由する劣化フローの集合を意味するものとする。
フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとする。【０１０２】
図１６に、実施形態４による非劣化リンク判定法を用いた場合での動作のフローチャートを示す。
ステップＳ４０１で、劣化フローが経由する全リンク集合をＬ０とし、Ｒを空集合とする。又、Ｌ＝Ｌ０とする。
ステップＳ４０２で、Ｌが空集合なら終了。空集合でない場合、ステップＳ４０３で、Ｌから１つのリンクｖを選び、Ｌからｖを除く。ＴをＬ０からｖ及びＲの要素を除いたものとする。
ステップＳ４０４で、リンクｖを１本以上の非劣化フローが経由しているかどうかを判定し、経由している場合は、非劣化フローのレートの合計が非劣化フロー数閾値以上かどうかを判定し、レートの合計が非劣化フローレート閾値以上の場合、ステップＳ４０５へ。そうでなければステップＳ４０２へ戻る。【０１０３】
ステップＳ４０５で、ｖが包含する劣化フロー集合を求める。Ｔの部分集合によって、その劣化フロー集合を包含する部分集合のうち、最小の要素数をもつものの要素数Ｘを求める。どのような部分集合でも、該劣化フロー集合が包含出来ない場合、要素数は無限大とする。
ステップＳ４０６で、ステップＳ４０５で求めた要素数Ｘに応じた非劣化フローレート閾値を、予め決められた対応表から決定する。【０１０４】
ステップＳ４０７で、そのリンクを経由する非劣化フローの合計レートが、ステップＳ４０６で求めた非劣化フローレート閾値以上のリンクをステップＳ４０８で除去リンク集合Ｒへ追加する。その後、ステップＳ４０２へ戻る。
ステップＳ４０６で用いる、最小要素数に応じた非劣化フローレート閾値の対応表は、最小要素数が増大するほど、非劣化フローレート閾値が増大するように決め、また、最小要素数が∞の時には、非劣化フロー数閾値は∞になるように決めておく。
以上の手順の終了時に、集合Ｒに含まれるリンクが除去される非劣化リンクである。【０１０５】
図６のフロー品質／経由リンクテーブルの例を用いて、非劣化リンク判定法４を用いた非劣化リンク除去部１５の動作を説明する。ここで、ステップＳ４０６で用いる要素数と非劣化フローレートの閾値は図１７で示されるものとする。また、パケットロス率２％を劣化閾値、パケットロス率０．６％を非劣化閾値とする。
まず、図１８の太枠で示すものが劣化フローである。また、横方向の点線で記したフローが非劣化フローである。【０１０６】
ステップＳ４０１ではＬ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｒ＝｛  ｝となる。ステップＳ４０２において、ｖ＝Ｌ１０とし、Ｌ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝となる。【０１０７】
ステップＳ４０４では、リンクｖを通過する非劣化フローのレートの合計は６０パケット／秒である。ステップＳ４０５では、リンクｖが包含する劣化フロー集合は｛Ｆ３，Ｆ１１｝であり、Ｌ２０が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。
ステップＳ４０６で、図１７の最小要素数１に対応する非劣化フローレート閾値は６０である。非劣化フローの合計レート６０がこの閾値以上であることから、ステップＳ４０８で、Ｒ＝｛Ｌ１０｝となる。再びステップＳ４０２へ戻る。【０１０８】
ステップＳ４０２でｖ＝Ｌ２０とし、Ｌ＝｛Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ４０，Ｌ５０｝となる。ステップＳ４０４では、ｖを通過する非劣化フローの合計レートは２０パケット/ 秒である。ステップＳ４０５では、ｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝であり、これを包含するＬの部分集合はないため、最小要素数Ｘは∞である。
ステップＳ４０６で、図１７の最小要素数∞に対応する非劣化フローレート閾値は∞であるため、非劣化フローの合計レート２０パケット/ 秒がこの閾値∞未満であることから、ステップＳ４０８で、Ｒ＝｛Ｌ１０｝のままとなる。その後、ステップＳ４０２へ再び戻る。【０１０９】
ステップＳ４０２でｖ＝Ｌ４０とし、Ｌ＝｛Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ５０｝となる。ステップＳ４０４では、リンクｖを通過する非劣化フローの合計レート６０パケット/ 秒である。ステップＳ４０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０｝であり、Ｔの部分集合である｛Ｌ２０｝が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。ステップＳ４０６で、図１３の最小要素数１に対応する非劣化フローレート閾値は６０であるため、非劣化フローの合計レート６０パケット／秒が前記閾値以上である事から、ステップＳ４０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。その後、再びステップＳ４０２へ戻る。【０１１０】
ステップＳ４０２でｖ＝Ｌ５０とし、Ｌ＝｛  ｝、Ｔ＝｛Ｌ２０｝となる。ステップＳ４０４では、ｖを通過する非劣化フローの合計レートは１１０パケット／秒である。ステップＳ４０５では、ｖが包含する劣化フロー集合は｛Ｆ２｝であり、Ｔの部分集合である｛Ｌ２０｝が包含する劣化フロー集合｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝がこれを包含するため、最小要素数Ｘは１である。【０１１１】
ステップＳ４０６で、図１３の最小要素数１に対応する非劣化フローレート閾値は６０であるため、非劣化フローの合計レート４０パケット／秒がこの閾値未満であることから、ステップＳ４０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。再びステップＳ４０２へ戻る。  ステップＳ４０２では、Ｌが空集合であるため停止する。
よって、Ｒ＝｛Ｌ１０，Ｌ４０｝を非劣化リンクとして除去し、図１９のような縮小フロー／リンクテーブルを得る。【０１１２】
（品質劣化箇所推定部１７）
品質劣化箇所推定部１７は、縮小フロー品質／経由テーブル記憶部１６から縮小フロー品質／経由テーブルを読み出し、前記縮小フロー品質／経由テーブルに基づいて最小リンク数推定法を用いることで品質劣化箇所を推定する。【０１１３】
実施形態４によれば、非劣化リンク除去において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。
リンクの劣化確率を同一と考えると、出来るだけ小さい数のリンクの劣化によって、現在の劣化状況を説明する方が、現在の劣化状況が発生した条件下で、より高い確率での正しい説明であると言える。なぜなら、同時に複数のリンクが劣化する確率は、リンク数が増大するほど小さくなるからである。【０１１４】
よって、あるリンクを非劣化として除去する事によって、最小リンク数推定結果のリンク数が増大する場合には、そのリンクを非劣化と判断した事が誤りである確率が高い。非劣化リンク判定法４のステップＳ４０６における最小要素数が１より大きくなればなるほど、そのリンクを除去した場合に、最小リンク数推定の結果得られる劣化リンクの数が増大する。また、最小要素数に対する非劣化フローレート閾値の対応表では、最小要素数が増大するほど、非劣化フローレート閾値が増大するように決めてある。以上のことから、実施形態４では、非劣化フローの合計レートが高い場合、すなわち、高い確率で非劣化である場合にのみ、最小リンク数推定の結果得られる劣化リンクの数が増大するような非劣化リンク除去が行われる事になり、非劣化リンク除去を正しく行える確率が高くなる。【０１１５】
（実施形態５）
実施形態５では、品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の動作のみが前述した実施形態１における非劣化リンク除去部１５と異なるため、以下、異なる点のみ説明する。【０１１６】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部１４から、フロー品質／経由リンクテーブルを読み出し、予め決められた劣化閾値より品質が悪いフロー（劣化フロー）の行を抽出する。非劣化リンク除去部１５は、前記閾値より品質が悪いフローが存在する場合、非劣化リンク判定法（５）により決定される非劣化リンク集合Ｒを除去し、品質情報およびフローレート情報を除いた縮小フロー品質／経由テーブルを生成し、これを縮小フロー品質／経由リンクテーブル記憶部１６に書き込む。【０１１７】
（非劣化リンク判定法（５））
非劣化リンク除去部１５が用いる非劣化リンク判定法（５）では、劣化リンクが１本以上経由する全てのリンクについて、そのリンクを経由する劣化フロー集合を求める。ここで、或るリンクが包含する劣化フローというのはそのリンクを経由する劣化フローを意味し、或るリンク集合が包含する劣化フローというのはそのリンクのいずれか１つ以上を経由する劣化フローの集合を意味するものとする。又、フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとする。【０１１８】
図２０に、この実施形態５において、非劣化リンク除去部１５が実行する非劣化リンク判定法（５）での動作のフローチャートを示す。
ステップＳ５０１で、劣化フローが経由する全リンク集合をＬ０とし、Ｒを空集合とする。又、Ｌ＝Ｌ０とする。ステップＳ５０２で、全リンク集合Ｌが空集合なら、処理を終了させる。全リンク集合Ｌが空集合でない場合、ステップＳ５０３で、全リンク集合Ｌから１つのリンクｖを選び、全リンク集合Ｌからリンクｖを除く。Ｔは、全リンク集合Ｌ０からリンクｖ及び空集合Ｒの要素を除いたものとする。【０１１９】
ステップＳ５０４で、リンクｖを１本以上の非劣化フローが経由しているかどうかを判定し、１本以上の非劣化フローが経由している場合、ステップＳ５０５へ処理を移行させる。そうでなければ、処理をステップＳ５０２へ戻す。
ステップＳ５０５で、リンクｖが包含する劣化フロー集合を求める。Ｔに含まれるリンクであって、そのリンクのフロー集合の要素数が、前記フロー集合の要素数より１以上大きく、且つ、リンクｖが包含する劣化フロー集合を包含するようなリンクの有無を調べる。【０１２０】
ステップＳ５０６で、ステップＳ５０５で求めたリンクの有無に応じた非劣化フロー数閾値を、予め決められた対応表から決定する。ステップＳ５０７で、リンクｖを経由する非劣化フロー数が、ステップＳ５０６で求めた非劣化フロー数閾値以上のリンクをステップＳ５０８で除去リンク集合Ｒへ追加する。その後、ステップＳ５０２へ戻る。
ステップＳ５０６で用いる非劣化フロー数閾値の対応表は、ステップＳ５０５でリンクが無い場合の非劣化フロー数閾値は∞になるように決めておく。
以上の手順の終了時に、集合Ｒに含まれるリンクが除去される非劣化リンクである。【０１２１】
図６のフロー品質／経由リンクテーブルの例を用いて、非劣化リンク判定法（５）を用いた非劣化リンク除去部１５の動作を説明する。
ここで、ステップＳ５０６で用いる要素数と非劣化フローの閾値は図２１で示されるものとする。また、パケットロス率２〔％〕を劣化閾値、パケットロス率０．６〔％〕を非劣化閾値とする。
まず、図２２の太枠で示すものが劣化フローである。また、横方向の点線で記したフローが非劣化フローである。【０１２２】
ステップＳ５０１ではＬ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｒ＝｛  ｝となる。ステップＳ５０２において、ｖ＝Ｌ１０とし、Ｌ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝となる。【０１２３】
ステップＳ５０４では、リンクｖを通過する非劣化フロー数は３である。ステップＳ５０５では、リンクｖが包含する劣化フロー集合は｛Ｆ３，Ｆ１１｝であり、要素数は２である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ５０５の要件を満たすリンクは存在する。
ステップＳ５０６で、図２１のリンクがある場合に相当する非劣化フロー数閾値は１であるため、リンクｖを経由する非劣化フロー数３が非劣化フロー数閾値１以上であることから、ステップＳ５０８で、Ｒ＝｛Ｌ１０｝となる。再びステップＳ５０２へ戻る。【０１２４】
ステップＳ５０２でｖ＝Ｌ２０とし、Ｌ＝｛Ｌ４０，Ｌ５０｝、  Ｔ＝｛Ｌ４０，Ｌ５０｝となる。ステップＳ５０４では、リンクｖを通過する非劣化フロー数は１である。ステップＳ５０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝であり、このフロー集合を包含するリンクは、Ｔの中にはない。
ステップＳ５０６で、図２１のリンクが無い場合の非劣化フロー数閾値は∞であるため、非劣化フロー数３が非劣化フロー数閾値∞未満であることから、ステップＳ５０８で、Ｒ＝｛Ｌ１０｝のままとなる。その後、ステップＳ５０２へ再び戻る。【０１２５】
ステップＳ５０２で、リンクｖ＝Ｌ４０とし、Ｌ＝｛Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ５０｝となる。ステップＳ５０４では、リンクｖを通過する非劣化フロー数は２である。ステップＳ５０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０｝であり、要素数は３である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で、要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ５０５の条件を満たすリンクは存在する。
ステップＳ５０６で、図２１のリンクがある場合に対応する非劣化フロー数閾値は１であるため、リンクｖを経由する非劣化フロー数２が非劣化フロー数閾値１以上である事から、ステップＳ５０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。その後、再びステップＳ５０２へ戻る。【０１２６】
ステップＳ５０２で、リンクｖ＝Ｌ５０とし、Ｌ＝｛  ｝、Ｔ＝｛Ｌ２０｝となる。ステップＳ５０４では、リンクｖを通過する非劣化フロー数は２である。
ステップＳ５０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２｝であり、要素数は１である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で、要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ５０５の条件を満たすリンクは存在する。【０１２７】
ステップＳ５０６で、図２１のリンクがある場合に対応する非劣化フロー数閾値は１であるため、リンクｖを経由する非劣化フロー数２がこの閾値１以上である事から、ステップＳ５０８で、Ｒ＝｛Ｌ１０，Ｌ４０，Ｌ５０｝となる。その後、再びステップＳ５０２へ戻る。ステップＳ５０２では、全フロー集合Ｌが空集合であるため、処理が停止する。
よって、Ｒ＝｛Ｌ１０，Ｌ４０，Ｌ５０｝を非劣化リンクとして除去し、図２３のような縮小フロー／リンクテーブルを得る。【０１２８】
（品質劣化箇所推定部１７）
品質劣化箇所推定部１７は、縮小フロー品質／経由テーブル記憶部１６から縮小フロー品質／経由テーブルを読み出し、前記縮小フロー品質／経由テーブルに基づいて最小リンク数推定法を用いることで品質劣化箇所を推定する。【０１２９】
実施形態５によれば、非劣化リンク除去において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。
リンクの劣化確率を同一と考えると、出来るだけ小さい数のリンクの劣化によって、現在の劣化状況を説明する方が、現在の劣化状況が発生した条件下で、より高い確率での正しい説明であると言える。なぜなら、同時に複数のリンクが劣化する確率は、リンク数が増大するほど小さくなるからである。【０１３０】
よって、あるリンクを非劣化として除去する事によって、最小リンク数推定結果のリンク数が増大する場合には、そのリンクを非劣化と判断した事が誤りである確率が高い。ある品質費劣化フローが追加するリンクｖで、リンクｖが包含する劣化フロー集合を包含し、且つ、要素数が大きい劣化リンクがあれば、そのリンクを除去した場合に、最小リンク数推定の結果得られる劣化リンクの数は、同じか、あるいは、減少するものと期待することができる。非劣化リンク判定法（５）のステップＳ５０５〜ステップＳ５０７において、このようなリンクの有無を調べ、リンクがある場合のみ、非劣化リンク除去が行われるようにしている。このため、本実施形態を用いることによって、非劣化リンク除去が正しく行える確率が高くなる。【０１３１】
（実施形態６）
実施形態６は、前述した実施形態３における品質劣化箇所推定サーバ１０の非劣化リンク除去部１５の動作のみが、前述した実施形態３と異なる構成となっている。このため、以下、異なる点のみ説明する。【０１３２】
（非劣化リンク除去部１５）
非劣化リンク除去部１５は、定期的にフロー品質／経由リンクテーブル記憶部Ｓ１４から、フロー品質／経由リンクテーブルを読み出し、予め決められた劣化閾値より品質が悪いフロー（劣化フロー）の行を抽出する。それが存在する場合、更に、次に述べる非劣化リンク判定法（６）により決定される非劣化リンク集合Ｒをのぞき、品質情報及びフローレート情報を除いた縮小フロー品質／経由テーブルを生成し、これを縮小フロー品質／経由リンクテーブル記憶部Ｓ１６に書き込む。【０１３３】
（非劣化リンク判定法（６））
非劣化リンク除去部１５が用いる非劣化リンク判定法（６）では、劣化リンクが１本以上経由する全てのリンクについて、そのリンクを経由する劣化フロー集合を求める。ここで、或るリンクが包含する劣化フローというのは、そのリンクを経由する劣化フローを意味する、又は或るリンク集合が包含する劣化フローというのはそのリンクのいずれか１つ以上を経由する劣化フローの集合を意味するものとする。
更に、フローの品質情報が予め決められた非劣化閾値より良い品質のフローを非劣化フローとする。【０１３４】
図２４に、実施形態６において、非劣化リンク除去部１５が非劣化リンク判定法を用いた動作のフローチャートを示す。
ステップＳ６０１で、劣化フローが経由する全リンク集合をＬ０とし、Ｒを空集合とする。又、Ｌ＝Ｌ０とする。ステップＳ６０２で、全リンク集合Ｌが空集合なら、処理を終了させる。全リンク集合Ｌが空集合でない場合、ステップＳ６０３で、全リンク集合Ｌから１つのリンクｖを選び、全リンク集合Ｌからリンクｖを除く。Ｔは、全リンク集合Ｌ０からリンクｖ及び空集合Ｒの要素を除いたものとする。
ステップＳ６０４で、リンクｖを１本以上の非劣化フローが経由しているかどうかを判定し、１本以上の非劣化フローが経由している場合、ステップＳ６０５へ処理を移行させる。そうでなければ、ステップＳ６０２へ戻る。【０１３５】
ステップＳ６０５で、リンクｖが包含する劣化フロー集合を求める。Ｔに含まれるリンクであって、そのリンクのフロー集合の要素数が、前記フロー集合の要素数より１以上大きく、且つ、リンクｖが包含する劣化フロー集合を包含するようなリンクの有無を調べる。
ステップＳ６０６で、ステップＳ６０５で求めたリンクの有無に応じた非劣化フローレート閾値を、予め決められた対応表から決定する。【０１３６】
ステップＳ６０７で、リンクｖを経由する非劣化フロー数が、ステップＳ６０６で求めた非劣化フローレート閾値以上のリンクをステップＳ６０８で除去リンク集合Ｒへ追加する。その後、ステップＳ６０２へ戻る。
ステップＳ６０６で用いる非劣化フローレート閾値の対応表は、ステップＳ６０５でリンクが無い場合の非劣化フローレート閾値は∞になるように決めておく。
以上の手順の終了時に、集合Ｒに含まれるリンクが除去される非劣化リンクである。【０１３７】
図６のフロー品質／経由リンクテーブルの例を用いて、非劣化リンク判定法６を用いた非劣化リンク除去部１５の動作を説明する。
ここで、ステップＳ６０６で用いる要素数と非劣化フローレートの閾値は図２５で示されるものとする。また、パケットロス率２〔％〕を劣化閾値、パケットロス率０．６〔％〕を非劣化閾値とする。
まず、図２６の太枠で示すものが劣化フローである。また、横方向の点線で記したフローが非劣化フローである。【０１３８】
ステップＳ６０１では、Ｌ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ１０，Ｌ２０，Ｌ４０，Ｌ５０｝、Ｒ＝｛  ｝となる。ステップＳ５０２において、リンクｖ＝Ｌ１０とし、Ｌ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ４０，Ｌ５０｝となる。
ステップＳ６０４では、リンクｖを通過する非劣化フロー数は３である。ステップＳ６０５では、リンクｖが包含する劣化フロー集合は｛Ｆ３，Ｆ１１｝であり、要素数は２である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ６０５の要件をリンクは存在する。【０１３９】
ステップＳ６０６で、図２５のリンクがある場合に相当する非劣化フローレート閾値は６０であるため、リンクｖを経由する非劣化フローレート６０が非劣化フローレート閾値６０以上であることから、ステップＳ６０８で、Ｒ＝｛Ｌ１０｝となる。再びステップＳ６０２へ戻る。【０１４０】
ステップＳ６０２でｖ＝Ｌ２０とし、Ｌ＝｛Ｌ４０，Ｌ５０｝、  Ｔ＝｛Ｌ４０，Ｌ５０｝となる。ステップＳ６０４では、リンクｖを通過する非劣化フロー数は１である。ステップＳ６０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝であり、このフロー集合れを包含するリンクは、Ｔの中にはない。
ステップＳ６０６で、図２５において、リンクが無い場合の非劣化フローレート閾値は∞であるため、非劣化フローの合計レート２０がこの閾値∞未満であることから、ステップＳ６０８で、Ｒ＝｛Ｌ１０｝のままとなる。その後、ステップＳ６０２へ再び戻る。【０１４１】
ステップＳ６０２でｖ＝Ｌ４０とし、Ｌ＝｛Ｌ５０｝、Ｔ＝｛Ｌ２０，Ｌ５０｝となる。ステップＳ６０４では、リンクｖを通過する非劣化フロー数は２である。
ステップＳ６０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０｝であり、要素数は３である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で、要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ６０５の条件を満たすリンクは存在する。
ステップＳ６０６で、図２５のリンクがある場合に対応する非劣化フローレート閾値は６０であるため、リンクｖを経由する非劣化フローレートの合計レート１１０が非劣化フローレート閾値６０以上である事から、ステップＳ６０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。その後、再びステップＳ６０２へ戻る。【０１４２】
ステップＳ６０２でｖ＝Ｌ５０とし、Ｌ＝｛  ｝、Ｔ＝｛Ｌ２０｝となる。ステップＳ６０４では、リンクｖを通過する非劣化フロー数は２である。
ステップＳ６０５では、リンクｖが包含する劣化フロー集合は｛Ｆ２｝であり、要素数は１である。リンクＬ２０が包含する劣化フロー集合は｛Ｆ２，Ｆ３，Ｆ１０，Ｆ１１｝で、要素数は５で、リンクｖが包含する劣化フロー集合の要素数２よりも大きく、且つ、リンクｖが包含する劣化フロー集合を包含しているため、ステップＳ６０５の条件を満たすリンクは存在する。【０１４３】
ステップＳ６０６で、図２５のリンクがある場合に対応する非劣化フローレート閾値は６０であるため、リンクｖを経由する非劣化フローの合計レート４０が非劣化フローレート閾値６０未満である事から、ステップＳ６０８で、Ｒ＝｛Ｌ１０，Ｌ４０｝となる。その後、再びステップＳ６０２へ戻る。ステップＳ６０２では、全フロー集合Ｌが空集合であるため、処理を停止する。
よって、Ｒ＝｛Ｌ１０，Ｌ４０｝を非劣化リンクとして除去し、図２７のような縮小フロー/ リンクテーブルを得る。【０１４４】
（品質劣化箇所推定部１７）
品質劣化箇所推定部１７は、縮小フロー品質／経由テーブル記憶部１６から縮小フロー品質／経由テーブルを読み出し、前記縮小フロー品質／経由テーブルに基づいて最小リンク数推定法を用いることで品質劣化箇所を推定する。【０１４５】
実施形態６によれば、非劣化リンク除去部１５において、十分に高い確率で非劣化であるリンクのみを除去することが可能である。【０１４６】
リンクの劣化確率を同一と考えると、出来るだけ小さい数のリンクの劣化によって、現在の劣化状況を説明する方が、現在の劣化状況が発生した条件下で、より高い確率での正しい説明であると言える。なぜなら、同時に複数のリンクが劣化する確率は、リンク数が増大するほど小さくなるからである。【０１４７】
よって、或るリンクを非劣化として除去する事によって、最小リンク数推定結果のリンク数が増大する場合には、そのリンクを非劣化と判断した事が誤りである確率が高い。或る品質費劣化フローが追加するリンクｖで、ｖが包含する劣化フロー集合を包含し且つ要素数が大きい劣化リンクがあれば、そのリンクを除去した場合に、最小リンク数推定の結果得られる劣化リンクの数は、同じか或いは減少するものと期待することができる。
実施形態６では、非劣化リンク判定法６のステップＳ６０５〜ステップＳ６０７において、このようなリンクの有無を調べ、リンクがある場合のみ、非劣化リンク除去が行われるようにしている。このため、これを実施形態６に用いることによって、非劣化リンク除去が正しく行える確率が高くなる。【０１４８】
以上、本発明にかかる品質劣化箇所推定装置についてその具体例を説明する共に、その内容の実行工程を品質劣化箇所推定方法を含めて、動作説明の項で開示した。更に、上述した品質劣化箇所推定装置の内容を実行する工程にあっては、各構成手段が有する機能をプログラム化し、コンピュータに実行させるように構成してもよい。【０１４９】
このように、本発明によると、上述したように非劣化リンク除去を高精度で実行することができるので、通信ネットワークシステムにおける通信品質の劣化箇所を高い精度且つ高速に推定することができるという利点を備えた品質劣化箇所推定装置，品質劣化箇所推定方法，及び品質劣化箇所推定プログラムを提供することができる。
【産業上の利用可能性】
【０１５０】
以上のように、本発明によると、従来よりも精度高く且つ迅速に通信ネットワークにおける品質劣化箇所を推定することができるので、通信業界をはじめ、通信ネットワークを用いる産業上の広い分野で利用の可能性が高い。
【図面の簡単な説明】
【０１５１】
【図１】本発明の実施形態１におけるネットワーク構成とフローの例を示す説明図である。
【図２】図１における実施形態のネットワークにおけるリンク名を示す説明図である。
【図３】図１における実施形態の品質劣化箇所推定サーバの構成を示すブロック図である。
【図４】図１の実施形態１におけるフロー品質／経由テーブル管理部の動作を示すフローチャートである。
【図５】図１の実施形態１における非劣化リンク除去部の動作を示すフローチャートである。
【図６】フロー品質／経由テーブルの一例を示す図表である。
【図７】図１の実施形態１における非劣化リンク判定法（１）での非劣化リンク除去のプロセスを示す図表である。
【図８】図７の非劣化リンク判定法（１）の実行によって得た縮小フロー品質／経由テーブルを示す図表である。
【図９】本発明の実施形態２における非劣化リンク判定法（２）での非劣化リンク除去のプロセスを示す図表である。
【図１０】図９の非劣化リンク判定法（２）の実行によって得た縮小フロー品質／経由テーブルを示す図表である。
【図１１】従来の非劣化リンク判定法によって得た縮小フロー品質／経由テーブルを示す参考図表である。
【図１２】本発明の実施形態３における非劣化リンク除去部の動作を示すフローチャートである。
【図１３】本発明の実施形態３で包含するリンク数と非劣化フロー数閾値との対応を示す図表である。
【図１４】本発明の実施形態３における非劣化リンク判定法（３）での非劣化リンク除去のプロセスを示す図表である。
【図１５】図１４の非劣化リンク判定法（３）を実行することによって得た縮小フロー品質／経由テーブルを示す図表である。
【図１６】本発明の実施形態４における非劣化リンク除去部の動作を示すフローチャートである。
【図１７】本発明の実施形態４で包含するリンク数と非劣化フロー数閾値との対応を示す図表である。
【図１８】本発明の実施形態４における非劣化リンク判定法（４）での非劣化リンク除去のプロセスを示す図表である。
【図１９】図１８の非劣化リンク判定法（４）を実行することによって得た縮小フロー品質／経由テーブルを示す図表である。
【図２０】本発明の実施形態５における非劣化リンク除去部の動作を示すフローチャートである。
【図２１】本発明の実施形態５で包含するリンク数と非劣化フロー数閾値との対応を示す図表である。
【図２２】本発明の実施形態５における非劣化リンク判定法（５）での非劣化リンク除去のプロセスを示す図表である。
【図２３】図２２の非劣化リンク判定法（５）を実行することによって得た縮小フロー品質／経由テーブルを示す図表である。
【図２４】本発明の実施形態６における非劣化リンク除去部の動作を示すフローチャートである。
【図２５】本発明の実施形態６で包含するリンク数と非劣化フローレート閾値との対応を示す図表である。
【図２６】本発明の実施形態６における非劣化リンク判定法（６）での非劣化リンク除去のプロセスを示す図表である。
【図２７】図２６の非劣化リンク判定法（６）を実行することによって得た縮小フロー品質／経由テーブルを示す図表である。
【図２８】ネットワーク構成とフローの例を示す説明図である。
【図２９】図２８のネットワークにおけるリンク名を示す説明図である。
【図３０】図２８のネットワークにおけるフロー・リンク対応表の例である。
【図３１】従来例における非劣化リンク除去処理の例を示す図表である。
【図３２】従来例における縮小フロー・リンク対応表の例である。
【図３３】従来例での誤った非劣化リンク除去処理の例である。
【図３４】従来例での誤った縮小フロー・リンク対応表の例である。
【図３５】従来例での誤った非劣化リンク除去処理の他の例である。
【図３６】従来例での誤った縮小フロー・リンク対応表の他の例である。
【符号の説明】
【０１５２】
１０  品質劣化箇所推定サーバ（品質劣化箇所推定装置）
１１  フロー品質情報収集部（フロー品質情報収集手段）
１２  経路情報収集部（経路情報収集手段）
１３  フロー品質／経由リンクテーブル管理部（フロー品質／経由リンクテーブル管理手段）
１４  フロー品質／経由リンクテーブル記憶部（フロー品質／経由リンクテーブル記憶手段）
１５  非劣化リンク除去部（非劣化リンク除去手段）
１６  縮小フロー品質／経由リンクテーブル記憶部（縮小フロー品質／経由リンクテーブル記憶手段）
１７  品質劣化箇所推定部（品質劣化箇所推定手段）
１８  表示部（表示手段）
１０１  情報収集手段
１０２  縮小劣化フロー／品質非劣化フロー決定手段
１０３  品質劣化箇所推定手段
Ｒ１〜Ｒ６  ルータ（パケットスイッチ）
ＴＲ１〜ＴＲ５  受信端末
ＴＳ１〜ＴＳ５  送信端末
【図１】
2007094170.tif 000003
【図２】
2007094170.tif 000004
【図３】
2007094170.tif 000005
【図４】
2007094170.tif 000006
【図５】
2007094170.tif 000007
【図６】
2007094170.tif 000008
【図７】
2007094170.tif 000009
【図８】
2007094170.tif 000010
【図９】
2007094170.tif 000011
【図１０】
2007094170.tif 000012
【図１１】
2007094170.tif 000013
【図１２】
2007094170.tif 000014
【図１３】
2007094170.tif 000015
【図１４】
2007094170.tif 000016
【図１５】
2007094170.tif 000017
【図１６】
2007094170.tif 000018
【図１７】
2007094170.tif 000019
【図１８】
2007094170.tif 000020
【図１９】
2007094170.tif 000021
【図２０】
2007094170.tif 000022
【図２１】
2007094170.tif 000023
【図２２】
2007094170.tif 000024
【図２３】
2007094170.tif 000025
【図２４】
2007094170.tif 000026
【図２５】
2007094170.tif 000027
【図２６】
2007094170.tif 000028
【図２７】
2007094170.tif 000029
【図２８】
2007094170.tif 000030
【図２９】
2007094170.tif 000031
【図３０】
2007094170.tif 000032
【図３１】
2007094170.tif 000033
【図３２】
2007094170.tif 000034
【図３３】
2007094170.tif 000035
【図３４】
2007094170.tif 000036
【図３５】
2007094170.tif 000037
【図３６】
2007094170.tif 000038
【国際調査報告】
2007094170.tif 000039
2007094170.tif 000040
2007094170.tif 000041
2007094170.tif 000042