(57)【要約】  品質劣化箇所推定装置（Ｓ１）は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、フロー・リンクテーブルに登録するフローとして、通過リンク数がネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定部（３）と、フローの通信品質の情報を収集するフロー品質情報収集部（１）と、ネットワークの経路情報を収集する経路情報収集部２と、通信品質の情報及び経路情報から、フロー・リンクテーブルを生成するフロー・リンクテーブル管理部（４）と、フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定部（８）とを有する。
2008108231.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が前記ネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えることを特徴とする品質劣化箇所推定方法。
【請求項２】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えることを特徴とする品質劣化箇所推定方法。
【請求項３】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えることを特徴とする品質劣化箇所推定方法。
【請求項４】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えることを特徴とする品質劣化箇所推定方法。
【請求項５】
請求項１記載の品質劣化箇所推定方法において、
前記フロー集合決定ステップは、
前記選択したフローを試験フローとするステップと、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示するステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項６】
請求項２記載の品質劣化箇所推定方法において、
前記フロー集合決定ステップは、
前記選択したフローを試験フローとするステップと、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示するステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項７】
請求項３記載の品質劣化箇所推定方法において、
前記フロー集合決定ステップは、
前記選択したフローを試験フローとするステップと、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示するステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項８】
請求項４記載の品質劣化箇所推定方法において、
前記フロー集合決定ステップは、
前記選択したフローを試験フローとするステップと、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示するステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項９】
請求項１記載の品質劣化箇所推定方法において、
前記推定ステップは、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去ステップと、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定ステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項１０】
請求項２記載の品質劣化箇所推定方法において、
前記推定ステップは、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去ステップと、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定ステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項１１】
請求項３記載の品質劣化箇所推定方法において、
前記推定ステップは、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去ステップと、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定ステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項１２】
請求項４記載の品質劣化箇所推定方法において、
前記推定ステップは、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去ステップと、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定ステップとを含むことを特徴とする品質劣化箇所推定方法。
【請求項１３】
請求項９記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１４】
請求項１０記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１５】
請求項１１記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１６】
請求項１２記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１７】
請求項９記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１８】
請求項１０記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項１９】
請求項１１記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項２０】
請求項１２記載の品質劣化箇所推定方法において、
前記品質劣化箇所推定ステップは、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定方法。
【請求項２１】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が前記ネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定手段と、
前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、
前記ネットワークの経路情報を収集する経路情報収集手段と、
前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えることを特徴とする品質劣化箇所推定装置。
【請求項２２】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択するフロー集合決定手段と、
前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、
前記ネットワークの経路情報を収集する経路情報収集手段と、
前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えることを特徴とする品質劣化箇所推定装置。
【請求項２３】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択するフロー集合決定手段と、
前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、
前記ネットワークの経路情報を収集する経路情報収集手段と、
前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えることを特徴とする品質劣化箇所推定装置。
【請求項２４】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを優先的に選択するフロー集合決定手段と、
前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、
前記ネットワークの経路情報を収集する経路情報収集手段と、
前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えることを特徴とする品質劣化箇所推定装置。
【請求項２５】
請求項２１記載の品質劣化箇所推定装置において、
前記フロー集合決定手段は、
前記選択したフローを試験フローとする手段と、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示する手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項２６】
請求項２２記載の品質劣化箇所推定装置において、
前記フロー集合決定手段は、
前記選択したフローを試験フローとする手段と、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示する手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項２７】
請求項２３記載の品質劣化箇所推定装置において、
前記フロー集合決定手段は、
前記選択したフローを試験フローとする手段と、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示する手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項２８】
請求項２４記載の品質劣化箇所推定装置において、
前記フロー集合決定手段は、
前記選択したフローを試験フローとする手段と、
前記試験フローを前記ネットワークに送出するよう前記ネットワーク上の端末に指示する手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項２９】
請求項２１記載の品質劣化箇所推定装置において、
前記推定手段は、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去手段と、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項３０】
請求項２２記載の品質劣化箇所推定装置において、
前記推定手段は、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去手段と、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項３１】
請求項２３記載の品質劣化箇所推定装置において、
前記推定手段は、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去手段と、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項３２】
請求項２４記載の品質劣化箇所推定装置において、
前記推定手段は、
前記フロー・リンクテーブルから、所定の劣化閾値より品質が悪い劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを除去した縮小フロー・リンクテーブルを生成する非劣化リンク除去手段と、
前記縮小フロー・リンクテーブルに基づいて品質劣化リンクを推定する品質劣化箇所推定手段とを含むことを特徴とする品質劣化箇所推定装置。
【請求項３３】
請求項２９記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３４】
請求項３０記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３５】
請求項３１記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３６】
請求項３２記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３７】
請求項２９記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３８】
請求項３０記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項３９】
請求項３１記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項４０】
請求項３２記載の品質劣化箇所推定装置において、
前記品質劣化箇所推定手段は、前記縮小フロー・リンクテーブルに登録された全ての劣化フローを包含するリンク集合のうち、最小のリンク数を持つ最小リンク集合を品質劣化リンクとすることを特徴とする品質劣化箇所推定装置。
【請求項４１】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が前記ネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを、ネットワーク上の品質劣化箇所推定装置として動作するコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【請求項４２】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを、ネットワーク上の品質劣化箇所推定装置として動作するコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【請求項４３】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを、ネットワーク上の品質劣化箇所推定装置として動作するコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【請求項４４】
ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを優先的に選択するフロー集合決定ステップと、
前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、
前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを、ネットワーク上の品質劣化箇所推定装置として動作するコンピュータに実行させることを特徴とする品質劣化箇所推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークシステムに係り、特に通信品質の劣化箇所を推定する品質劣化箇所推定方法、品質劣化箇所推定装置および品質劣化箇所推定プログラムに関するものである。
【背景技術】
【０００２】
通信ネットワークにおいて、通信品質劣化時に高速に通信品質劣化箇所を特定するには、ネットワーク内に監視装置を多数配備し、配備した位置での通信品質を常に監視しておき、通信品質劣化時に、品質劣化が起こっている監視装置の位置を基に、品質劣化している区間を推定していた（例えば、特開２００２−２７１３９２号公報参照）。この方式では、品質劣化している位置の推定精度を高めるには、多数の監視装置が必要となり、その配置コストが高いという問題がある。この問題に対処するため、ネットワークを通過する通信フローの品質情報とルーティング情報から品質劣化箇所を推定する方法が提案されている（例えば、特開２００６−２３８０５２号公報参照）。【０００３】
特開２００６−２３８０５２号公報に開示された品質劣化箇所推定方法について説明する。まず、各フローとそれらが通過するリンク（有向リンク）と品質とを対応付けたテーブル（以下、フロー・リンクテーブルと呼ぶ）を作成する。例えば図１５に示したルータ（あるいはパケットスイッチ）Ｒ１〜Ｒ６から成るネットークにおいて、フローＦ１〜Ｆ５が流れているとする。図１５のネットワークに対し、図１６に記すように各リンクに名前を付け、品質としてパケットロス率を使い、ルータＦ１〜Ｆ５のパケットロス率をそれぞれ３．０％、２．５％、３．５％、１．０％、０．５％とすると、フロー・リンクテーブルは図１７のようになる。ここで、各フローは１秒間に１００パケット流れるとし、パケットロス率は２秒毎のパケットロス数をもとに求めるとする。図１７中のビット「１」は、リンクにフローが流れることを示している。【０００４】
次に、品質劣化箇所推定方法では、非劣化リンク除去処理を行う。すなわち、あらかじめ定められたフロー品質の劣化閾値と非劣化閾値に基づいて、劣化閾値より品質の悪いフローを劣化フロー、非劣化閾値より品質の良いフローを非劣化フロー、それ以外のフローを中間品質フローとし、フロー・リンクテーブルから、中間品質フローの行と非劣化フローの行と非劣化フローが通過するリンクの列とを除いた縮小フロー・リンクテーブルを作成する。【０００５】
例えばパケットロス率２％を劣化閾値、１％を非劣化閾値とすると、図１７の例では、Ｆ１〜Ｆ３が劣化フロー、Ｆ５が非劣化フロー、Ｆ４が中間品質フローとなる。図１７に示したフロー・リンクテーブルから、図１８に示すように中間品質フローＦ４の行と非劣化フローＦ５の行と非劣化フローＦ５が通過するリンクＬ３０，Ｌ４５の列とを削除し、図１９に示すような縮小フロー・リンクテーブルを作成する。【０００６】
最後に、品質劣化箇所推定方法では、図１９の縮小フロー・リンクテーブルを基に品質劣化箇所を推定する。例えば、品質劣化フロー数に基づく推定法では、図１９の各リンクＬ１０，Ｌ２０，Ｌ５０，Ｌ４０を通過する劣化フロー数がそれぞれ１個、３個、１個、１個なので、この中で最も通過するフロー数が多いリンクＬ２０を品質劣化箇所として推定する。【０００７】
また、最小リンク数推定法では、図１９の各リンクＬ１０，Ｌ２０，Ｌ５０，Ｌ４０を通過するフロー集合を考え、最小の数のリンクで、図１９の全てのフローを包含するようなリンク集合を求め、それを劣化リンク集合とする。すなわち、図１９の例では、各リンクＬ１０，Ｌ２０，Ｌ５０，Ｌ４０を通過するフロー集合は、それぞれ｛Ｆ１｝，｛Ｆ１，Ｆ２，Ｆ３｝，｛Ｆ２｝，｛Ｆ３｝である。例えば３つのリンクから成るリンク集合｛Ｌ１０，Ｌ５０，Ｌ４０｝を通過するフロー和集合は｛Ｆ１，Ｆ２，Ｆ３｝となり、全てのフローを包含できる。これ以外にも、２つのリンクから成るリンク集合｛Ｌ１０，Ｌ２０｝や、１つのリンクから成るリンク集合｛Ｌ２０｝によっても全てのフローを包含できる。全てのフローを包含するようなリンク集合のうち、最小のリンク数をもつ｛Ｌ２０｝を最小リンク集合として推定する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特開２００６−２３８０５２号公報に開示された品質劣化箇所推定方法では、品質劣化箇所の推定に使用されるフローとして、ネットワークを流れる全てのフロー、あるいは全てのフローからランダムに選択されたフローが使用されていた。ネットワークを流れる全てのフローを品質劣化箇所の推定に使用する場合は、フロー・リンクテーブルの行数（フロー数）が非常に大きくなり、品質劣化箇所の推定に時間がかかるという問題点があった。また、全てのフローからランダムに選択されたフローを品質劣化箇所の推定に使用する場合は、品質劣化箇所の推定精度が悪いという問題点があった。【０００９】
本発明の目的は、品質劣化箇所の推定に要する時間を短縮し、品質劣化箇所の推定精度を向上させることにある。
【課題を解決するための手段】
【００１０】
本発明の品質劣化箇所推定方法は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が前記ネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定ステップと、前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えるものである。
また、本発明の品質劣化箇所推定方法は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択するフロー集合決定ステップと、前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えるものである。
また、本発明の品質劣化箇所推定方法は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択するフロー集合決定ステップと、前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えるものである。
また、本発明の品質劣化箇所推定方法は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを優先的に選択するフロー集合決定ステップと、前記ネットワークを流れるフローの通信品質及び前記ネットワークの経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成ステップと、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定ステップとを備えるものである。【００１１】
また、本発明の品質劣化箇所推定装置は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が前記ネットワークの全リンク数の１／２に近いフローを優先的に選択するフロー集合決定手段と、前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、前記ネットワークの経路情報を収集する経路情報収集手段と、前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えるものである。
また、本発明の品質劣化箇所推定装置は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択するフロー集合決定手段と、前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、前記ネットワークの経路情報を収集する経路情報収集手段と、前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えるものである。
また、本発明の品質劣化箇所推定装置は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択するフロー集合決定手段と、前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、前記ネットワークの経路情報を収集する経路情報収集手段と、前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えるものである。
また、本発明の品質劣化箇所推定装置は、ネットワークを流れるフローの通信品質とフローが通過するリンクとを対応付けたフロー・リンクテーブルを生成する前に、前記フロー・リンクテーブルに登録するフローとして、前記ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを優先的に選択するフロー集合決定手段と、前記ネットワークを流れるフローの通信品質の情報を収集するフロー品質情報収集手段と、前記ネットワークの経路情報を収集する経路情報収集手段と、前記収集された通信品質の情報及び経路情報から、前記フロー・リンクテーブルを生成するフロー・リンクテーブル生成手段と、前記フロー・リンクテーブルに基づいてネットワーク上の品質劣化箇所である品質劣化リンクを推定する推定手段とを備えるものである。
【発明の効果】
【００１２】
本発明によれば、フロー・リンクテーブルに登録するフローとして、通過リンク数がネットワークの全リンク数の１／２に近いフローを優先的に選択することにより、フロー・リンクテーブルの行数（フロー数）を少なくすることができるので、従来よりも品質劣化箇所の推定に要する時間を短縮することができ、またフロー・リンクテーブル上で縦のビット列が同一となるようなリンクを少なくすることができるので、品質劣化箇所の推定精度を向上させることができる。【００１３】
また、本発明によれば、フロー・リンクテーブルに登録するフローとして、通過リンク数が多いフローを優先的に選択することにより、フロー・リンクテーブルの行数（フロー数）を少なくすることができるので、従来よりも品質劣化箇所の推定に要する時間を短縮することができ、またフロー・リンクテーブル上で縦のビット列が同一となるようなリンクを少なくすることができるので、品質劣化箇所の推定精度を向上させることができる。【００１４】
また、本発明によれば、フロー・リンクテーブルに登録するフローとして、ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、２つのフロー間で通過リンクが異なる個数が、ネットワークの全リンク数の１／２に近いフローのペアを優先的に選択することにより、フロー・リンクテーブルの行数（フロー数）を少なくすることができるので、従来よりも品質劣化箇所の推定に要する時間を短縮することができ、またフロー・リンクテーブル上で縦のビット列が同一となるようなリンクを少なくすることができるので、品質劣化箇所の推定精度を向上させることができる。【００１５】
また、本発明によれば、フロー・リンクテーブルに登録するフローとして、ネットワーク上の任意の２つの端末間で送受し得る全てのフローの集合のうち、前記集合を構成する各フローのいずれか１つが通過するリンクの集合が大きくなるようにフローを選択することにより、フロー・リンクテーブルの行数（フロー数）を少なくすることができるので、従来よりも品質劣化箇所の推定に要する時間を短縮することができ、またフロー・リンクテーブル上で、フローが通過しないリンク数を少なくすることができるので、品質劣化箇所の推定精度を向上させることができる。【００１６】
また、本発明では、フロー・リンクテーブルに登録するフローとして選択したフローを試験フローとし、試験フローをネットワークに送出するようネットワーク上の端末に指示することにより、端末間に試験フローが流れるので、端末からはこの試験フローの通信品質情報が品質劣化箇所推定装置に送信される。この結果、フロー・リンクテーブルは、試験フローを含む、現在通信が行われているフローについて作成される。本発明では、品質劣化箇所推定のために、ネットワークユーザの通信とは別に流す試験フローの最適な集合を決定することができる。また、本発明によれば、試験フローの最適な集合を決定できることから、この試験フローを流す端末をネットワークに配置する際の最適な配置方法を決定することも可能である。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明の第１実施例に係るネットワークの構成例を示す図である。
【図２】図２は、本発明の第１実施例に係る品質劣化箇所推定装置の内部構成を示すブロック図である。
【図３】図３は、本発明の第１実施例に係る品質劣化箇所推定装置のフロー集合決定部の動作を示すフローチャートである。
【図４】図４は、本発明の第１実施例における全フロー・リンクテーブルの例を示す図である。
【図５】図５は、本発明の第１実施例に係る品質劣化箇所推定装置のフロー・リンクテーブル管理部の動作を示すフローチャートである。
【図６】図６は、本発明の第１実施例におけるフロー・リンクテーブルの例を示す図である。
【図７】図７は、本発明の第１実施例に係る品質劣化箇所推定装置の非劣化リンク除去部の動作を示すフローチャートである。
【図８】図８は、本発明の第１実施例における縮小フロー・リンクテーブルの例を示す図である。
【図９】図９は、本発明の第１実施例に係る品質劣化箇所推定装置の品質劣化箇所推定部の動作を示すフローチャートである。
【図１０】図１０は、本発明の第１実施例の効果を説明するためのフロー・リンクテーブルを示す図である。
【図１１】図１１は、本発明の第１実施例の効果を説明するための縮小フロー・リンクテーブルを示す図である。
【図１２】図１２は、本発明の第２実施例に係る品質劣化箇所推定装置のフロー集合決定部の動作を示すフローチャートである。
【図１３】図１３は、本発明の第３実施例に係る品質劣化箇所推定装置のフロー集合決定部の動作を示すフローチャートである。
【図１４】図１４は、本発明の第４実施例に係る品質劣化箇所推定装置のフロー集合決定部の動作を示すフローチャートである。
【図１５】図１５は、本発明に関連するネットワークの構成例とネットワークを流れるフローの例を示す図である。
【図１６】図１６は、図１５のネットワークのリンクを示す図である。
【図１７】図１７は、フロー・リンクテーブルの例を示す図である。
【図１８】図１８は、図１７のフロー・リンクテーブルから中間品質フローの行と非劣化フローの行と非劣化フローが経由するリンクの列とを削除する非劣化リンク除去処理を示す図である。
【図１９】図１９は、縮小フロー・リンクテーブルの例を示す図である。
【発明を実施するための最良の形態】
【００１８】
［第１実施例］
以下、本発明の第１実施例について図面を参照して説明する。図１は本発明の第１実施例に係るネットワークの構成例を示す図である。ネットワークには、ルータ（又はスイッチ）Ｒ１〜ＲＮが配置され、品質計測を行う試験端末Ａ１〜ＡＫ及び品質劣化箇所推定装置Ｓ１が接続されている。また、本実施例では、ルータＲ１〜ＲＮ間の通信リンクについては、同一のルータ間のリンクであっても方向が異なるものは別のリンクであるとして、各リンクにＬ１〜ＬＭの符号を付してある。【００１９】
試験端末Ａ１〜ＡＫは、通信品質を計測する機能と、計測した通信品質の情報を品質劣化箇所推定装置Ｓ１に通知する機能と、品質劣化箇所推定装置Ｓ１の指示に応じて試験フローを生成してネットワークに送出する機能とを備えている。【００２０】
図２に本発明の第１実施例に係る品質劣化箇所推定装置Ｓ１の内部構成を示す。品質劣化箇所推定装置Ｓ１は、フロー品質情報収集部１と、経路情報収集部２と、フロー集合決定部３と、フロー・リンクテーブル生成手段となるフロー・リンクテーブル管理部４と、フロー・リンクテーブル記憶部５と、非劣化リンク除去部６と、縮小フロー・リンクテーブル記憶部７と、品質劣化箇所推定部８と、表示部９とから構成されている。品質劣化箇所推定装置Ｓ１は、試験端末Ａ１〜ＡＫからフロー毎の品質情報を集めて、ルータＲ１〜ＲＮから得た経路情報を基に品質劣化箇所を推定し、推定結果を表示部９に出力する。【００２１】
以下に、品質劣化箇所推定装置Ｓ１の各構成要素の動作を説明する。まず、フロー品質情報収集部１は、試験端末Ａ１〜ＡＫが通信を開始すると、試験端末Ａ１〜ＡＫから通信開始の通知を受け取る。また、フロー品質情報収集部１は、通信開始以降は、試験端末Ａ１〜ＡＫから定期的に、現在の通信品質情報（例えばフローの送信元となる送信端末のアドレス、フローの宛先となる受信端末のアドレス、フロー品質情報、及びフローレート）を受け取る。ここで、フロー品質情報とは、例えばパケットロス率、遅延、遅延ジッタなどの通信品質に関わる情報である。フローレートとは、通信に使われたフローの１秒あたりのパケット数の情報である。フロー品質情報収集部１は、試験端末Ａ１〜ＡＫが通信を終了すると、試験端末Ａ１〜ＡＫから通信終了の通知を受け取る。【００２２】
次に、経路情報収集部２は、ルータ（又はスイッチ）Ｒ１〜ＲＮから、ルーティングに関する経路情報を収集する。この情報収集は、ＳＭＴＰ（Simple Network Management Protocol）等を使って行うことが可能である。経路情報があれば、送受信端末のアドレス情報から、当該送受信端末間の通信がどの経路で行われるかを決定することができる。ルータから収集する場合、経路情報は、具体的にはルーティングテーブル及びＡＲＰ（Address Resolution Protocol）テーブルの構成情報である。また、スイッチから収集する場合、経路情報は、具体的にはフォワーディングデーターベース及びスパニングツリーの構成情報である。なお、経路情報については、ルータ（又はスイッチ）Ｒ１〜ＲＮから収集せずに、ネットワーク管理者が与えることも可能である。【００２３】
次に、フロー集合決定部３は、試験端末Ａ１〜ＡＫがそれぞれ接続されたルータがどのルータであるかという情報を試験端末Ａ１〜ＡＫから取得し、この情報と経路情報収集部２が収集した経路情報に基づいて、どの端末間に試験フローを流すべきかを以下に述べるように決定して、決定した端末間で試験フローを流すように試験端末Ａ１〜ＡＫに対して指示する。図３はフロー集合決定部３の動作を示すフローチャートである。【００２４】
まず、フロー集合決定部３は、フローとフローが通過するリンクとフローの送信元となる送信端末のアドレスとフローの宛先となる受信端末のアドレスとを対応付けたフロー・リンクテーブルを、Ｋ個の試験端末Ａ１〜ＡＫのうちの任意の２つの端末間の全てのフローの組について生成する（図３ステップＳ１００）。このフロー・リンクテーブルを、全フロー・リンクテーブルＸとする。フローの送受信の向きを区別すると、Ｋ個の試験端末Ａ１〜ＡＫのうちの任意の２つの端末間のフローの組は、Ｋ×（Ｋ−１）通り存在し得る。したがって、Ｋ×（Ｋ−１）通りのフローについて全フロー・リンクテーブルＸを生成することになる。【００２５】
全フロー・リンクテーブルＸの１例を図４に示す。図４におけるＦ１はフローである。図４の例では、全て空欄になっているが、実際の全フロー・リンクテーブルＸでは、フローの行とこのフローが通過するリンクの列とが交差する欄にビット「１」が設定される。
全フロー・リンクテーブルＸは、試験端末Ａ１〜ＡＫから取得した、試験端末Ａ１〜ＡＫの接続先のルータを示す情報と、経路情報収集部２が収集した経路情報とを使うことによって生成することが可能である。フロー集合決定部３は、全フロー・リンクテーブルＸのＫ×（Ｋ−１）通りのフローの中から、品質計測のために流す試験フローの集合を以下の方法で決定する。【００２６】
本実施例では、フロー集合の決定方法として、第１のフロー集合決定方法を用いる。第１のフロー集合決定方法を用いる場合、フロー集合決定部３は、まず全リンク数Ｍの１／２の値をＨとする（ステップＳ１０１）。全リンク数Ｍが２で割り切れないときは、Ｍ／２の小数点以下を切り上げあるいは切り捨てて、Ｍ／２の整数値をＨとする。【００２７】
次に、フロー集合決定部３は、全フロー・リンクテーブルＸから、各フローの通過リンク数を求める（ステップＳ１０２）。通過リンク数を求めるには、全フロー・リンクテーブルＸの行毎にビット「１」が立っている数を求めればよい。フロー集合決定部３は、通過リンク数とＨとの差の絶対値が小さいフローから順に並ぶように全フロー・リンクテーブルＸの各行をソートする（ステップＳ１０３）。ただし、通過リンク数が同一のフロー、すなわち通過リンク数とＨとの差の絶対値が同一のフローが複数ある場合には、これらのフロー中のソートの順は問わないものとする。【００２８】
そして、フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの各フローから優先順位が高い順に、すなわち通過リンク数とＨとの差の絶対値が小さい方から順に、予め定められた個数Ｊのフローを試験フローの集合として決定する（ステップＳ１０４）。あるいは、フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの各フローのうち、通過リンク数とＨとの差の絶対値が予め定められた閾値以下であるフローを試験フローの集合として決定する（ステップＳ１０４）。【００２９】
最後に、フロー集合決定部３は、試験端末Ａ１〜ＡＫのうち、決定した試験フローの送信端末と受信端末に対して試験フローを流すように指示する（ステップＳ１０５）。【００３０】
次に、フロー・リンクテーブル管理部４は、フロー品質情報収集部１が取得した通信品質情報と、経路情報収集部２が収集した経路情報とに基づいて、現在通信が行われているフローについて、送信端末のアドレスと受信端末のアドレスと通過するリンクとフローの品質（例えばパケットロス率）とフローレートとを対応付けたフロー・リンクテーブルを生成し、このフロー・リンクテーブルをフロー・リンクテーブル記憶部５に記憶させる。
このフロー・リンクテーブルをフロー・リンクテーブルＹと呼ぶ。図５はフロー・リンクテーブル管理部４の動作を示すフローチャートである。【００３１】
フロー・リンクテーブル管理部４は、フロー品質情報収集部１から通信品質情報を受信し（図５ステップＳ２００）、経路情報収集部２から経路情報を受信すると（ステップＳ２０１）、通信品質情報から送信端末のアドレスと受信端末のアドレスとフロー品質とフローレートとを取得し（ステップＳ２０２）、送受信端末のアドレスと経路情報を基にフローの通過リンクを決定し（ステップＳ２０３）、フロー・リンクテーブルＹを生成して（ステップＳ２０４）、フロー・リンクテーブルＹをフロー・リンクテーブル記憶部５に登録する（ステップＳ２０５）。【００３２】
フロー・リンクテーブルＹの１例を図６に示す。全フロー・リンクテーブルＸの場合と同様に、フローの行とこのフローが通過するリンクの列とが交差する欄にはビット「１」が設定される。
前述のフロー集合決定部３の動作により、試験端末Ａ１〜ＡＫ間に試験フローが流れるので、試験端末Ａ１〜ＡＫからはこの試験フローの通信品質情報が品質劣化箇所推定装置Ｓ１に送信される。したがって、フロー・リンクテーブルＹは、試験フローを含む、現在通信が行われているフローについて作成されることになる。【００３３】
次に、非劣化リンク除去部６は、フロー・リンクテーブルＹに対して定期的に非劣化リンク除去処理を行って、縮小フロー・リンクテーブルＺを生成し、この縮小フロー・リンクテーブルＺを縮小フロー・リンクテーブル記憶部７に記憶させる。図７は非劣化リンク除去部６の動作を示すフローチャートである。【００３４】
まず、非劣化リンク除去部６は、フロー・リンクテーブル記憶部５から定期的にフロー・リンクテーブルＹを読み出し、あらかじめ定められた劣化閾値より品質が悪い劣化フローが存在するかどうか調べる（図７ステップＳ３００）。非劣化リンク除去部６は、劣化フローが存在する場合、フロー・リンクテーブルＹから、劣化フローを除く非劣化フローの行と非劣化フローが通過するリンクの列とを削除すると共に、送信端末のアドレスと受信端末のアドレスとフロー品質とフローレートとを削除して、縮小フロー・リンクテーブルＺを生成し（ステップＳ３０１）、縮小フロー・リンクテーブルＺを縮小フロー・リンクテーブル記憶部７に登録する（ステップＳ３０２）。縮小フロー・リンクテーブルＺの１例を図８に示す。【００３５】
図９は品質劣化箇所推定部８の動作を示すフローチャートである。品質劣化箇所推定部８は、縮小フロー・リンクテーブル記憶部７から縮小フロー・リンクテーブルＺを読み出し（ステップＳ４００）、品質劣化フロー数推定法あるいは最小リンク数推定法を用いて品質劣化箇所を推定し（ステップＳ４０１）、推定した品質劣化箇所を表示部９に表示させる（ステップＳ４０２）。【００３６】
図１９を用いて説明したように、品質劣化フロー数推定法は、縮小フロー・リンクテーブルＺに登録された各リンクのうち、通過する劣化フローの数が最も多いリンクを品質劣化箇所とする方法である。
一方、最小リンク数推定法は、縮小フロー・リンクテーブルＺに登録された全ての劣化フローを包含するリンク集合（リンクの組み合わせ）のうち、最小のリンク数を持つ最小リンク集合を品質劣化箇所とする方法である。【００３７】
こうして、品質劣化箇所推定装置Ｓ１では、品質劣化箇所として推定されたリンクが表示部９に表示される。【００３８】
次に、本実施例の効果について説明する。特開２００６−２３８０５２号公報に開示された品質劣化箇所推定方法では、フロー・リンクテーブルＹの各リンクの列に立っている縦のビット列について、同じビット列を持つ１つ以上のリンクがあると、それらのリンクはどれが品質劣化を起こしても、全てが品質劣化箇所の候補となってしまう。例えば、フロー・リンクテーブルＹが図１０のようであったとする。このフロー・リンクテーブルＹでリンクＬ２とＬ４は同じビット列を持っているため、どちらか一方が品質劣化を起こしても、図１１のような縮小フロー・リンクテーブルＺが生成される。このため、品質劣化箇所推定部８では、品質劣化フロー数に基づく推定法あるいは最小リンク数推定法のいずれを用いても、Ｌ２，Ｌ４の両方のリンクが品質劣化箇所と判定されてしまう。この結果、どちらか一方の品質劣化していないリンクは誤って品質劣化箇所と判定されることになり、推定精度が悪化することになる。【００３９】
これに対して、本実施例のフロー集合決定部３では、できるだけ少ないフロー数で、このような同じビット列を持つリンクの組が少なくなるような試験フローの集合を選択している。本実施例の第１のフロー集合決定方法では、全フロー・リンクテーブルＸの各行に立っているビット数（通過リンク数）が、全リンク数の１／２に近いフローを優先的に試験フローとして決定する。【００４０】
第１のフロー集合決定方法を用いる理由は、全フロー・リンクテーブルＸの２つの行（フロー）に着目したときに、各行に立つビットがランダムである場合には、１／２のビットが立っているような行が最も多く起こり得る上、着目した２行のビットが異なる位置の平均値が最大になるためである。このような現象が起こることは、全フロー・リンクテーブルＸの各列にビットが立つ確率をｐとすると、２つの行で同じ数だけビットが立つものについて、ビットが異なる確立はｐ×（１−ｐ）であり、この確率が最大となるのはｐ＝１／２であることから明らかである。【００４１】
こうして、本実施例のフロー集合決定部３において決定された試験フローの集合によれば、フロー・リンクテーブルＹの行数（フロー数）を少なくすることができるので、特開２００６−２３８０５２号公報に開示された品質劣化箇所推定方法に比べて品質劣化箇所の推定に要する時間を短縮することができ、またフロー・リンクテーブルＹ上で縦のビット列が同一となるようなリンクを少なくすることができるので、品質劣化箇所の推定精度を向上させることができる。【００４２】
［第２実施例］
次に、本発明の第２実施例について説明する。本実施例においても、ネットワーク及び品質劣化箇所推定装置Ｓ１の構成は第１実施例と同様であるので、図１、図２の符号を用いて説明する。
第１実施例との違いは、フロー集合決定部３においてフロー集合の決定方法として第２のフロー集合決定方法を用いる点である。以下、この第２のフロー集合決定方法について説明する。【００４３】
図１２は本実施例のフロー集合決定部３の動作を示すフローチャートである。まず、本実施例のフロー集合決定部３は、ステップＳ１００と同様に全フロー・リンクテーブルＸを生成し（ステップＳ５００）、ステップＳ１０１と同様に全リンク数Ｍの１／２の値をＨとし（ステップＳ５０１）、ステップＳ１０２と同様に全フロー・リンクテーブルＸから、各フローの通過リンク数を求める（ステップＳ５０２）。【００４４】
続いて、フロー集合決定部３は、通過リンク数が大きいフローから順に並ぶように全フロー・リンクテーブルＸの各行をソートする（ステップＳ５０３）。ただし、通過リンク数が同一のフローが複数ある場合には、これらのフロー中のソートの順は問わないものとする。【００４５】
そして、フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの各フローから優先順位が高い順に、すなわち通過リンク数が大きい方から順に、予め定められた個数Ｊのフローを試験フローの集合として決定する（ステップＳ５０４）。あるいは、フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの各フローのうち、通過リンク数が予め定められた閾値以上であるフローを試験フローの集合として決定する（ステップＳ５０４）。【００４６】
最後に、フロー集合決定部３は、試験端末Ａ１〜ＡＫのうち、決定した試験フローの送信端末と受信端末に対して試験フローを流すように指示する（ステップＳ５０５）。こうして、フロー集合決定部３の処理が終了する。
品質劣化箇所推定装置Ｓ１のその他の構成要素の動作は、第１実施例と同じである。【００４７】
本実施例のフロー集合決定部３における第２のフロー集合決定方法は、第１のフロー集合決定方法と同じ発想であるが、一般にネットワークトポロジを考えると、フローはネットワークの全リンク数Ｍの１／２より遙かに少ない数のリンク数しか通過できない可能性が高い。このため、全リンク数Ｍの１／２に近い数のリンクを通るということは、現実的にはできるだけ多くのリンクを通過するということと同義であるので、本実施例の第２のフロー集合決定方法によれば、第１のフロー集合決定方法と同等の効果を得ることができる。【００４８】
［第３実施例］
次に、本発明の第３実施例について説明する。本実施例においても、ネットワーク及び品質劣化箇所推定装置Ｓ１の構成は第１実施例と同様であるので、図１、図２の符号を用いて説明する。
第１実施例との違いは、フロー集合決定部３においてフロー集合の決定方法として第３のフロー集合決定方法を用いる点である。以下、この第３のフロー集合決定方法について説明する。【００４９】
図１３は本実施例のフロー集合決定部３の動作を示すフローチャートである。まず、本実施例のフロー集合決定部３は、ステップＳ１００と同様に全フロー・リンクテーブルＸを生成し（ステップＳ６００）、ステップＳ１０１と同様に全リンク数Ｍの１／２の値をＨとする（ステップＳ６０１）。続いて、フロー集合決定部３は、全フロー・リンクテーブルＸの全てのフロー（行）の集合をＵとし、集合Ｕの２つの要素間の距離を全ての要素の組み合わせについて求める（ステップＳ６０２）。【００５０】
集合Ｕの２つの要素間の距離としては、通過リンクを示すビット列間のハミング距離、すなわち２つの要素間で異なる通過リンクの個数を用いる。例えば全フロー・リンクテーブルＸにおいて、フローＦ１の通過リンクがＬ１，Ｌ３で、フローＦ２の通過リンクがＬ１であるとすれば、集合Ｕの２つの要素であるフローＦ１とＦ２の間で異なる通過リンクはＬ３である。したがって、フローＦ１とＦ２間の距離は１となる。なお、集合Ｕにおいて２つの要素のとり得る組み合わせは、全部でＫ×（Ｋ−１）×｛Ｋ×（Ｋ−１）−１｝通り存在する。以下、ステップＳ６０２で要素間距離を求めた要素の組をペアと呼ぶ。【００５１】
次に、フロー集合決定部３は、ステップＳ６０２で要素間距離を求めた全てのペアについて、要素間距離とＨとの差の絶対値を求め、要素間距離とＨとの差の絶対値が小さいペアから順に並ぶように全フロー・リンクテーブルＸの各行をソートする（ステップＳ６０３）。【００５２】
フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの先頭から優先順位が高い順に、すなわち要素間距離とＨとの差の絶対値が小さい方から順に、予め定められた個数Ｐのペアを選択する（ステップＳ６０４）。あるいは、フロー集合決定部３は、ソートした全フロー・リンクテーブルＸの各ペアのうち、要素間距離とＨとの差の絶対値が予め定められた閾値以下であるペアを選択する（ステップＳ６０４）。【００５３】
そして、フロー集合決定部３は、ステップＳ６０４で選択したペアの集合について、ペアの少なくとも一方に含まれる全てのフローを試験フローとして決定する（ステップＳ６０５）。最後に、フロー集合決定部３は、試験端末Ａ１〜ＡＫのうち、決定した試験フローの送信端末と受信端末に対して試験フローを流すように指示する（ステップＳ６０６）。こうして、フロー集合決定部３の処理が終了する。
品質劣化箇所推定装置Ｓ１のその他の構成要素の動作は、第１実施例と同じである。【００５４】
本実施例のフロー集合決定部３における第３のフロー集合決定方法によれば、以下のような効果がある。
全フロー・リンクテーブルＸの任意の２行に着目したとき、その通過リンクのビットが異なる個数がハミング距離に対応している。任意の２つのフローにおいて、同じリンクに立つビットの組は（０、０）、（０、１）、（１、０）、（１、１）の４通りしかなく、この２つのフローの品質の現れ方の組み合わせにより、全リンクが４通りに分類される。【００５５】
任意の２つのフローが（０、０）、（０、１）、（１、０）、（１、１）の４つのリンクを含むとき、この４つのリンクに関してのハミング距離は２である。これを全リンクに拡張すれば、ハミング距離が全リンクの数の１／２となっている場合に、最も均一に全リンクが４通りに識別されることとなる。ｋ本のフローがあったとき、ｋ本のフローで識別できるリンク数が最大となる（つまり、縦のビット列が同一となるようなリンクを少なくできる）のは、どのフローも均一に４通りの識別を行う場合であり、このようなフロー集合を使うことで、最も少ないフロー数で、品質劣化箇所の推定精度を最大化することができる。【００５６】
このように、本実施例では、互いのハミング距離が全リンク数の１／２に近付くようなフロー集合を集めており、少ないフロー数で品質劣化箇所推定精度が最大化されることが期待できる。【００５７】
［第４実施例］
次に、本発明の第４実施例について説明する。本実施例においても、ネットワーク及び品質劣化箇所推定装置Ｓ１の構成は第１実施例と同様であるので、図１、図２の符号を用いて説明する。
第１実施例との違いは、フロー集合決定部３においてフロー集合の決定方法として第４のフロー集合決定方法を用いる点である。以下、この第４のフロー集合決定方法について説明する。【００５８】
図１４は本実施例のフロー集合決定部３の動作を示すフローチャートである。まず、本実施例のフロー集合決定部３は、ステップＳ１００と同様に全フロー・リンクテーブルＸを生成し（ステップＳ７００）、全フロー・リンクテーブルＸの全てのフロー（行）の集合をＵとし、フロー集合Ｓを空集合とし、Ｔ＝０とする（ステップＳ７０１）。【００５９】
次に、フロー集合決定部３は、Ｔがあらかじめ決められた値Ｊ以上か、あるいはＵが空集合かどうかを調べ、いずれかの条件が成り立てば図１４の処理を終了し、そうでなければ、次のステップ（ステップＳ７０３）に進む（ステップＳ７０２）。フロー集合決定部３は、Ｓの要素であるフローのうち、フロー・リンクテーブルＸを用い、少なくとも１つのフローが通過しているリンクの総数Ｐを求める（ステップＳ７０３）。フロー集合決定部３は、Ｕの要素である各フローｒのそれぞれについて、Ｓにｒを加えたフロー集合Ｓ∩｛ｒ｝を求め、Ｓ∩｛ｒ｝の要素のフローのうち、少なくとも１つのフローが通過しているリンクの総数Ｐ’（ｒ）を求める（ステップＳ７０４）。【００６０】
フロー集合決定部３は、ステップＳ７０４で求めた各フローｒについてのＰ’（ｒ）と、ステップＳ７０３で求めたＰとの差Ｐ’（ｒ）−Ｐを求め、この差が大きいものから優先的にフローを選択し、Ｓに加える（ステップＳ７０５）。フロー集合決定部３は、ステップＳ７０５でＳに加えたフローをＵから除外し、加えたフローの本数をＴに加算し、ステップＳ７０２へ戻る（ステップＳ７０６）。ステップＳ７０５の処理を行う度に、Ｔは単調に増加し、Ｕの要素は単調に減少するため、いつか必ずステップＳ７０２の２つの条件のいずれかが成立し、フロー集合決定部３は動作を停止する。
品質劣化箇所推定装置Ｓ１のその他の構成要素の動作は、第１実施例と同じである。【００６１】
本実施例のフロー集合決定部３における第４のフロー集合決定方法によれば、以下のような効果がある。
全フロー・リンクテーブルの各列に着目したとき、どのフローも通過していないリンクにもし劣化が発生しても、どのフローも劣化とならず、品質劣化の発生自体が見逃されてしまい、品質劣化箇所の推定精度が悪化する。本実施例では、フロー集合の決定の際に、どのフローも通過していないリンクを少なくするようにフローを選択して追加している。このため、少ないフロー数で、品質劣化発生を見逃す可能性を最小化する事が期待され、品質劣化箇所推定精度を最大化することが期待できる。【００６２】
なお、第１実施例〜第４実施例における品質劣化箇所推定装置Ｓ１は、例えばＣＰＵ、記憶装置およびインタフェースを備えたコンピュータとこれらのハードウェア資源を制御するプログラムによって実現することができる。このようなコンピュータを動作させるための品質劣化箇所推定プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカードなどの記録媒体に記録された状態で提供される。ＣＰＵは、読み込んだプログラムを記憶装置に書き込み、このプログラムに従って第１実施例〜第４実施例で説明した処理を実行する。
【産業上の利用可能性】
【００６３】
本発明は、通信ネットワークシステムにおいて、通信品質の劣化箇所を推定する技術に適用することができる。
【図１】
2008108231.tif 000003
【図２】
2008108231.tif 000004
【図３】
2008108231.tif 000005
【図４】
2008108231.tif 000006
【図５】
2008108231.tif 000007
【図６】
2008108231.tif 000008
【図７】
2008108231.tif 000009
【図８】
2008108231.tif 000010
【図９】
2008108231.tif 000011
【図１０】
2008108231.tif 000012
【図１１】
2008108231.tif 000013
【図１２】
2008108231.tif 000014
【図１３】
2008108231.tif 000015
【図１４】
2008108231.tif 000016
【図１５】
2008108231.tif 000017
【図１６】
2008108231.tif 000018
【図１７】
2008108231.tif 000019
【図１８】
2008108231.tif 000020
【図１９】
2008108231.tif 000021
【国際調査報告】
2008108231.tif 000022
2008108231.tif 000023
2008108231.tif 000024
2008108231.tif 000025