【課題】コストを抑えながら、ネットワークの品質を改善するための対処に有効な劣化パスを効率的かつ適切に検出する。
【解決手段】劣化パス検出装置１は、測定端末Ｔに近い方から、測定ネットワーク全体を小さな木構造のトポロジに分解する。そして、分解した木構造のトポロジ内において、測定端末Ｔ間で測定を実施して劣化パスを検出するとともに、この木構造トポロジにおけるルートノードと測定端末Ｔとの間の劣化値が最大となる測定端末Ｔを抽出する。劣化パス検出装置１は、分解した木構造である各部分木のルートノードに接続されている１階層上のノードをルートノードとした新たな部分木を対象範囲とし、劣化値が最大となる測定端末Ｔ間で測定を実施して劣化パスを検出し、劣化値が最大となる測定端末Ｔを抽出することを繰り返す。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、劣化パス検出システム、劣化パス検出方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
特許文献１には、各ノード装置がネットワークシステムから取得した情報に基づいて所属先のクラスタを自律的に決定することによって、各ノード装置が複数のクラスタのうちいずれか１つのクラスタに所属するクラスタ化を行い、実際の品質測定については各クラスタ内の代表ノード間でのみフルメッシュの測定を行う品質測定方法が記載されている。この品質測定方法では、クラスタに所属する他のノードがネットワーク品質の測定結果を必要とする場合、代表ノードの測定結果を用いることによって全体の測定数を抑えることができ、また、ネットワークにかかる負荷を抑制することができる。その結果、ユビキタス時代に急激に増加すると予測される多ノード大規模分散ネットワーク環境下において、スケーラビリティを保ったままで効率的な品質測定を自動的に実施することが可能となり、ネットワーク管理や利用可能アプリケーションの把握、障害検知に有用である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−０７４２０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述した従来技術では、全体の測定数を抑えているものの、その測定方式から、ネットワークの全ての代表ノードに測定装置が必要となり、設置コストがかかってしまう。また、代表ノード以外に劣化要因が存在した場合、劣化パスは抽出できない。また、複数の劣化パスが抽出された場合は、対処に有効な劣化パスが適切に保守者等へ通知されない可能性もある。
【０００５】
本発明は、このような事情を考慮してなされたもので、その目的は、コストを抑えながら、ネットワークの品質を改善するための対処に有効な劣化パスを効率的かつ適切に検出することができる劣化パス検出システム、劣化パス検出方法及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決すべくなされたもので、劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、前記劣化パス検出装置は、前記ネットワークを前記測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築部と、前記部分木ネットワーク構築部によって分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する測定指示実行部と、前記測定指示実行部による指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析部（測定端末選定／劣化値分析部）とを備え、前記測定指示実行部は、前記木構造のトポロジにおいて前記選定分析部が特定した前記測定端末間による通信品質の測定を指示する、ことを特徴とする劣化パス検出システムである。
【０００７】
また、本発明は、劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、前記劣化パス検出装置は、測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとし、前記測定端末をリーフノードとする木構造の部分木ネットワークを前記ネットワークから抽出する部分木ネットワーク構築部と、前記部分木ネットワーク構築部により抽出された前記部分木ネットワーク内の前記測定端末間による通信品質の測定を指示する測定指示実行部と、前記測定指示実行部による指示に応じて得られた前記測定端末間の通信品質の測定劣化値に基づいてさらに測定対象の前記測定端末を選択し、前記測定指示実行部に選択した前記測定端末間の通信品質の測定を指示し、測定によって得られた前記測定端末間の測定劣化値に基づいて前記部分木ネットワーク内の劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる前記測定端末を特定する選定分析部（測定端末選定／劣化値分析部）とを備え、前記部分木ネットワーク構築部は、前記ルートノードが最も下の階層である場合は前記ルートノードに接続される前記測定端末全てをリーフノードとし、前記ルートノードが最も下の階層ではない場合は、前記選定分析部によって選択された前記測定端末をリーフノードとした部分木ネットワークを抽出する、ことを特徴とする劣化パス検出システムである。
【０００８】
また、本発明は、劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、前記測定端末は、前記劣化パス検出装置からの指示を受け、他の前記測定端末との間で通信品質を測定する手段を備え、前記劣化パス検出装置は、測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとし、前記測定端末をリーフノードとする木構造の部分木ネットワークを前記ネットワークから抽出する部分木ネットワーク構築部と、前記部分木ネットワーク構築部により抽出された前記部分木ネットワークにおける測定端末のペアを選択し、選択した前記測定端末のペア間における通信品質の測定を指示する測定指示実行部と、前記測定指示実行部による指示に対応して前記選択した前記ペア間の通信品質の測定結果を取得して劣化値を算出する劣化値取得部（測定結果受信／劣化値算出部）と、前記劣化値取得部が取得した前記測定端末間の測定劣化値に基づいて劣化パスの検出のために測定が必要な測定端末のペアを選択し、前記選択した測定端末のペア間の通信品質の測定を行なうよう前記測定指示実行部に指示し、前記劣化値取得部が取得した前記測定端末のペア間の測定劣化値によって前記部分木ネットワーク内のリンクの劣化値を取得して劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる前記測定端末を特定する選定分析部（測定端末選定／劣化値分析部）とを備え、前記部分木ネットワーク構築部は、前記ルートノードが最も下の階層である場合は前記ルートノードに接続される前記測定端末全てをリーフノードとし、前記ルートノードが最も下の階層ではない場合は、前記選定分析部によって選択された前記測定端末をリーフノードとした部分木ネットワークを抽出する、ことを特徴とする劣化パス検出システムである。
【０００９】
また、本発明は、上述した劣化パス検出システムであって、前記選定分析部は、前記劣化値取得部が取得した前記測定端末間の測定劣化値に基づいて劣化パスの検出のために測定が必要な測定端末を選択し、前記選択した測定端末間の通信品質の測定を行なうよう前記測定指示実行部に指示し、前記劣化値取得部が取得した前記測定端末間の測定劣化値によって前記部分木ネットワーク内のリンクの劣化値を取得して劣化パスを検出し、劣化パスが検出された場合は、劣化パス内の各リンクの劣化値を補正した後、前記部分木ネットワーク内のリンクの劣化値に基づいてルートノードとの間の劣化値が最大となる測定端末を特定する、ことを特徴とする。
【００１０】
本発明は、劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムに用いられる劣化パス検出方法であって、前記劣化パス検出装置において、部分木ネットワーク構築部が、複数のノードをリンクにより接続してなるネットワークから測定端末が接続されている層の前記ノードを選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する最下層部分木ネットワーク構築過程と、測定指示実行部が、前記初期部分木ネットワーク構築過程において分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する最下層指示実行過程と、選定分析部（測定端末選定／劣化値分析部）が、前記指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析過程と、前記部分木ネットワーク構築部が、現在のルートノードより一階層上位のノードを新たなルートノードとして選択し、前記ネットワークを選択した新たなノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築過程と、前記測定指示実行部が、前記部分木ネットワーク構築過程において分解された木構造のトポロジにおいて、前記選定分析過程によって特定された前記測定端末間による測定を指示する指示実行過程とを有し、前記ネットワーク内の全てのノードについて処理を終了するまで前記選定分析過程からの処理を繰り返し実行する、ことを特徴とする劣化パス検出方法である。
【００１１】
また、本発明は、劣化パス検出装置として用いられるコンピュータに、複数のノードをリンクにより接続してなるネットワークを、測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築ステップと、前記部分木ネットワーク構築ステップにおいて分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する測定指示実行ステップと、前記測定指示実行ステップにおける指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析ステップとを実行させ、前記測定指示実行ステップにおいては、前記木構造のトポロジにおいて前記選定分析ステップにおいて特定された前記測定端末間による通信品質の測定を指示する処理を実行させる、ことを特徴とするコンピュータプログラムである。
【発明の効果】
【００１２】
本発明によれば、すでに測定パスの測定結果を利用し、演算で求めることによって、フルメッシュにより通信品質を測定することなく全ノードを対象とした効率的な品質測定を実現することができる。これにより、ネットワークに負荷を最小限に抑えながら劣化パスを検出することが可能であるため、大規模ネットワークへの応用が容易である。加えて、劣化パス検出の際に必要となる測定機器は、ネットワーク外部のみに配置すればよく、各区間の品質算出のためにネットワーク内部に測定機器を設置する必要がない。よって、設置コストを抑えることが可能である。
本発明によれば、すでに検出された劣化パス内の劣化値を演算補正しながら測定処理を実施しているため、他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスの検出を抑えながら、網内の劣化パスを検出することが可能であり、また、この検出された劣化パスのほとんどは独立しているため、劣化パス検出時の無駄な切り分け作業を抑えることができ、早期の故障回復が可能である。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態による劣化パス検出システムの全体構成図である。
【図２】同実施形態による劣化パス検出装置の構成を示す機能ブロック図である。
【図３】同実施形態による劣化パス検出装置が処理に使用するデータのデータ構造を示す図である。
【図４】同実施形態による劣化パス検出装置における劣化パス検出処理全体の処理フローを示す図である。
【図５】同実施形態による劣化パス検出装置における部分木データ構築処理の処理フローを示す図である。
【図６】同実施形態による劣化パス検出装置における部分木内測定処理の処理フローを示す図である。
【図７】同実施形態による劣化パス検出装置における測定劣化パス処理の処理フローを示す図である。
【図８】同実施形態による劣化パス検出装置におけるリンク劣化値算出処理の処理フローを示す図である。
【図９】同実施形態による劣化パス検出装置における劣化区間候補抽出処理の処理フローを示す図である。
【図１０】同実施形態による劣化パス検出装置における折り返し劣化分析処理の処理フローを示す図である。
【図１１】同実施形態による劣化パス検出装置における折り返し劣化分析処理の処理フローを示す図である。
【図１２】同実施形態による劣化パス検出装置における最大劣化区間抽出処理の処理フローを示す図である。
【図１３】同実施形態による劣化パス検出装置における部分木データ再構築処理の処理フローを示す図である。
【図１４】同実施形態による部分木データ構築処理を説明するための図である。
【図１５】同実施形態による測定劣化パス処理を説明するための図である。
【図１６】同実施形態による測定劣化パス処理を説明するための図である。
【図１７】同実施形態によるリンク劣化値算出処理を説明するための図である。
【図１８】同実施形態によるリンク劣化値算出処理を説明するための図である。
【図１９】同実施形態による劣化区間候補抽出処理を説明するための図である。
【図２０】同実施形態による劣化区間候補抽出処理を説明するための図である。
【図２１】同実施形態による折り返し劣化分析処理を説明するための図である。
【図２２】同実施形態による折り返し劣化分析処理を説明するための図である。
【図２３】同実施形態による最大劣化区間抽出処理を説明するための図である。
【図２４】同実施形態による部分木データ再構築処理を説明するための図である。
【図２５】同実施形態による部分木データ再構築処理を説明するための図である。
【図２６】同実施形態による部分木データ再構築処理を説明するための図である。
【図２７】同実施形態による部分木データ再構築処理を説明するための図である。
【図２８】同実施形態による部分木データ再構築処理を説明するための図である。
【図２９】同実施形態による部分木データ再構築処理を説明するための図である。
【図３０】同実施形態による部分木データ再構築処理を説明するための図である。
【図３１】同実施形態による部分木データ再構築処理を説明するための図である。
【図３２】同実施形態による部分木データ再構築処理を説明するための図である。
【図３３】同実施形態による部分木データ再構築処理を説明するための図である。
【図３４】同実施形態による部分木データ再構築処理を説明するための図である。
【図３５】同実施形態による部分木データ再構築処理を説明するための図である。
【図３６】同実施形態による部分木データ再構築処理を説明するための図である。
【図３７】同実施形態による部分木データ再構築処理を説明するための図である。
【図３８】同実施形態による部分木データ再構築処理を説明するための図である。
【図３９】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４０】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４１】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４２】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４３】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４４】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４５】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４６】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４７】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４８】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図４９】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５０】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５１】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５２】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５３】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５４】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５５】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５６】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５７】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５８】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図５９】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６０】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６１】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６２】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６３】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６４】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６５】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６６】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６７】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６８】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図６９】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図７０】同実施形態による劣化パス検出装置の分析例を説明するための図である。
【図７１】同実施形態による劣化パス検出装置により分析可能な測定対象ネットワークの例を示す図である。
【図７２】図７１の測定対象ネットワークを部分木に分割した例を示す図である。
【図７３】図７２に示す部分木ネットワークにおける劣化パスを示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら本発明の実施形態を詳細に説明する。
【００１５】
[１． 構成]
図１は、本発明の一実施形態による劣化パス検出システムの全体構成を示す図である。
同図に示すように、複数のルータＲから構成される測定対象ネットワーク内の劣化パスを検出する劣化パス検出システムは、ネットワークトポロジ情報記憶装置２を備えた劣化パス検出装置１と、測定対象ネットワークを構成するルータＲに接続される測定端末Ｔとからなり、全ての測定端末Ｔと劣化パス検出装置１とは通信ネットワークにより接続されている。
同図において、測定対象ネットワークは、ツリー構造のネットワーク構成となっているが、部分木に分割が可能なネットワークであれば測定ネットワークの構造は問わない。
【００１６】
本実施形態では、測定端末Ｔ及び測定対象ネットワーク内のルータＲ等の中継装置を「ノード」とし、測定端末Ｔ−ルータＲ間、および、ルータＲ−ルータＲ間の区間を「リンク」とする。
そして、木構造のトポロジにおいて、測定端末Ｔが設置される層を測定端末層とし、測定対象ネットワークにおいて、測定端末Ｔに近いルータＲ（ノード）から順に第一階層、第二階層、・・・、第Ｎ階層とグルーピングする。以下の説明において、「第ｉ階層に含まれるノード」（ｉは、一、二、…、Ｎ）などと記載されている場合、第ｉ階層に含まれる全てのノードを指し、例えば、「第二階層に含まれるノード」と記載されている場合、図１に示すトポロジにおいては、第二階層内の２つのノード（ルータＲ）を指す。
階層の数字が小さいほう、つまり、端末層に近い階層を低い階層、階層の数字が多いほうを高い階層とし、あるノードと接続されている１つ低い階層のノードを子ノード、あるノードと接続されている１つ高い階層のノードを親ノードとする。
【００１７】
ネットワークトポロジ情報記憶装置２は、ネットワークトポロジ情報を記憶する。ネットワークトポロジ情報とは、測定対象ネットワークを構成するエレメント（ノード及びリンク）と、各測定端末Ｔとの接続関係を特定する情報である。各エレメント及び各測定端末Ｔは一意の識別情報を持つ。ネットワークトポロジ情報には、各エレメントの識別情報、各ノードが測定端末ＴであるかルータＲであるかの種別、各ノードの通信アドレスの情報も含まれる。本実施形態では、ノードの識別情報をノードＩＤとし、ノードＩＤがｘのノードをノードＮ［ｘ］と記載する。特に、ノードＩＤがｘの測定端末Ｔを測定端末Ｔ［ｘ］とも記載する。また、図面中には測定端末Ｔ、ルータＲのノードＩＤを［］内に記載する。
【００１８】
劣化パス検出装置１は、ネットワークトポロジ情報記憶装置２に記憶されているネットワークトポロジ情報と、測定端末の識別情報とに基づいて測定端末Ｔ間の経路を特定することができる。劣化パス検出装置１は、測定端末Ｔに対して通信品質の測定（以下、通信品質の測定を単に「測定」とも記載する。）を指示し、その測定指示に応じて測定端末Ｔが送受信した通信パケットの伝送情報を受信する。劣化パス検出装置１は、測定端末Ｔ間の通信パケットの伝送情報送受信のタイムスタンプから、２地点間のＩＰ（Internet Protocol）品質を算出する。ここではＩＰ品質は、遅延やパケットロスを示す。
【００１９】
測定端末Ｔは、一般の通信端末と同様に、測定端末同士でアクティブな通信が可能な装置である。測定端末Ｔは、劣化パス検出装置１から通信品質の測定指示により、他の測定端末Ｔの間での通信を実施し、通信パケットの伝送情報を劣化パス検出装置１に送信する。測定端末Ｔは、通信パケットを送受信した際の時刻を取得する。なお、各測定端末Ｔによる通信品質の測定時には時刻同期が行われているものとする。
【００２０】
本実施形態の劣化パス検出装置１は、測定対象ネットワークを構成する機器間において、劣化と判定されるパスを検出するため、以下の処理を行なう。
（１）測定端末Ｔに近い方から、測定ネットワーク全体を小さな木構造のトポロジに分解する。
（２）分解した木構造のトポロジ内において、測定端末Ｔ間で測定を実施して劣化パスを検出するとともに、この木構造トポロジにおけるルートノードと測定端末Ｔとの間の劣化値が最大となる測定端末Ｔを抽出する。
（３）分解した木構造である各部分木のルートノードに接続されている１階層上のノードをルートノードとした新たな部分木を対象範囲とし、（２）において抽出した測定端末Ｔ間で測定を実施して劣化パスを検出し、劣化値が最大となる測定端末Ｔを抽出する。
（４）（３）の処理を繰り返し、トポロジ全体の劣化パスを検出する。
【００２１】
上記処理は、以下の特徴を有する。
（ａ）各エレメントの劣化の和によって、End-Endで劣化となるパスの検出が可能である。
（ｂ）他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスの検出を少なく抑えることにより、対処すべき劣化パスを効率的に認識することが可能である。
（ｃ）複数の独立した劣化パスが同時に存在したとしても、１度の測定対象ネットワーク全体に対する測定において、False Negativeパス（劣化パスとなるパスが未検出となる状態）が存在しない。
【００２２】
図２は、劣化パス検出装置１の構成を示す機能ブロック図である。
同図において、劣化パス検出装置１は、部分木ネットワーク構築部１１、測定指示実行部１２、測定結果受信／劣化値算出部１３、測定端末選定／劣化値分析部１４、記憶部１５、及び、出力部１６を備えて構成される。なお、ネットワークトポロジ情報記憶装置２は、劣化パス検出装置１内に備えられてもよく、劣化パス検出装置１と接続される外部の装置により実現してもよい。
【００２３】
部分木ネットワーク構築部１１は、劣化パス検出のための測定対象となる、部分木ネットワークを抽出する。測定指示実行部１２は、部分木ネットワーク構築部１１が抽出した部分木ネットワーク内の測定端末Ｔに対して測定指示を送信する。また、測定端末選定／劣化値分析部１４から受信した情報に基づき、測定端末Ｔに対し測定指示を送信する。測定結果受信／劣化値算出部１３は、測定端末Ｔから通信パケットの伝送情報を受信し、受信情報から２台の測定端末Ｔ間の測定劣化値（遅延／ロス）の算出を行う。測定端末選定／劣化値分析部１４は、測定結果受信／劣化値算出部１３による測定結果に応じて、分析に必要な測定端末Ｔの選定を行うとともに、測定結果から劣化パスの検出や、ルートノード−リーフノード間の劣化値が最大となる測定端末Ｔの特定を行なう。なお、ルートノードとは、部分木ネットワークにおいて最も高い階層のノードであり、リーフノードとは、部分木ネットワークにおける測定端末層のノード（測定端末Ｔ）である。記憶部１５は、劣化パス検出処理に用いられるデータを記憶する。出力部１６は、検出された劣化パスを画面に表示する。あるいは、出力部１６は、検出された劣化パスを印刷したり、コンピュータ読み取り可能な記録媒体に書き込んだり、あるいは、ネットワークを介して接続される他のコンピュータに送信してもよい。
【００２４】
劣化パス検出装置１内の各部による処理概要を説明する。
【００２５】
（ステップＳ１）：部分木ネットワーク構築部１１は、第一階層に含まれるノードをルートノードとし、このノードに直接接続される測定端末Ｔをリーフノードとする部分木ネットワークを測定範囲として抽出する。
【００２６】
(ステップＳ２）：測定端末選定／劣化値分析部１４は、各測定範囲である部分木ネットワークの測定端末Ｔに対し、網羅率１００％となるように測定端末Ｔのペアを選択し、測定指示実行部１２は、各ペア間での測定を実施するよう測定端末Ｔに指示を送信する。網羅率１００％とは、部分木ネットワークに含まれる測定端末Ｔ全てが、選択されたペアの中に１回のみ使用されている状態である。ただし、測定端末Ｔが奇数台のときは、１台のみが２回使用される。
【００２７】
（ステップＳ３）：測定端末Ｔは、ペアとして指示された測定端末Ｔとの間で測定のための通信を行い、パケットの送受信を行なう。各測定端末Ｔは、送受信したパケットの情報（送信先、送信元、シーケンス番号など）、および、パケットを送受信した時刻を記録する。測定終了後、測定端末Ｔは、送受信パケット情報、パケットの送受信時刻、及び、自測定端末Ｔを特定するノード識別情報を含む測定結果情報を劣化パス検出装置１に送信する。
【００２８】
（ステップＳ４）：測定結果受信／劣化値算出部１３は、測定端末Ｔから受信した測定結果情報を受信し、この受信した測定結果情報から、ある単位時間における各測定端末Ｔ間の測定劣化値（遅延時間／パケットロス率）を計算する。
【００２９】
（ステップＳ５）：測定端末選定／劣化値分析部１４は、各パスの測定劣化値に応じて、分析に必要な測定端末Ｔを選定し、測定指示実行部１２は選定した測定端末Ｔへ測定を指示する。測定結果受信／劣化値検出部１３は、測定結果を受信して、測定端末選定／劣化値分析部１４は劣化値の算出を行い、各測定範囲（部分木ネットワーク）内における劣化パスを検出し、ルートノード−リーフノード間の劣化値が最大となる測定端末Ｔを抽出する。
【００３０】
（ステップＳ６）：部分木ネットワーク構築部１１は、第二階層に含まれるノードをルートノードとし、ステップＳ５で抽出した測定端末Ｔをリーフノードとする新たな測定範囲（部分木ネットワーク）を抽出する。
【００３１】
（ステップＳ７）：ステップＳ６において抽出した部分木ネットワークについてステップＳ２〜Ｓ４と同様の処理を行い、第二階層のノードをルートノードとする測定範囲（部分木ネットワーク）内における劣化パスを検出し、ルートノード−リーフノード間の劣化値が最大となる測定端末Ｔを抽出する。
【００３２】
（ステップＳ８）：以降、同様に各階層に含まれるノードをルートノードとし、抽出した測定端末Ｔをリーフノードとする測定範囲（部分木ネットワーク）を抽出し、各測定範囲（部分木ネットワーク）内の劣化パス検出、および最大劣化値となる測定端末Ｔの抽出の処理を、最上位階層のノードがルートノードとなるまで繰り返す。劣化パス検出装置１の出力部１６は、検出した劣化パスを分析結果として出力する。
【００３３】
他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスの検出を抑える効果を得るために、ステップＳ５の処理を詳細化すると、以下のステップＳ５’のようになる。
【００３４】
（ステップＳ５’）：測定端末選定／劣化値分析部１４は、各パスの測定劣化値に応じて、分析に必要な測定端末Ｔを選定し、測定指示実行部１２は選定した測定端末Ｔへ測定を指示する。測定結果受信／劣化値算出部１３は、測定結果を受信して、劣化値の算出を行い、測定端末選定／劣化値分析部１４は、算出結果から各測定範囲（部分木ネットワーク）内に劣化パスが存在するかどうかを分析する。
劣化パスが検出された場合、測定端末選定／劣化値分析部１４は、劣化パス内の各リンクの劣化値を「０」に補正した後、部分木内の各リンクの劣化値に基づいて、ルートノード−リーフノード間の劣化値が最大となる測定端末Ｔを抽出する。
【００３５】
劣化パス内の各リンクの劣化値をそのまま使用した場合、劣化箇所が含まれているパスは全て劣化パスとして検出されてしまうことになり、対処すべき範囲の絞り込みが困難となる。そこで、劣化パスを検出した場合、劣化パス内の各リンクの劣化値を「０」によって補正する処理を行い、その劣化箇所を含んだパスについては、計算上、その劣化パスが解消された状態での劣化値とすることにより、他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスの検出を抑える効果を得る事が可能となる。
尚、劣化パスが検出されなかった場合、補正処理は行われず、測定結果そのものから得られる各リンクの劣化値に基づいて、ルートノード−リーフノード間の劣化値が最大となる測定端末Ｔを抽出する事となる。
【００３６】
[２． 劣化パス検出装置の処理]
続いて、フローチャートを用いて劣化パス検出装置１の処理フローを説明し、さらにこの処理フローの処理を具体的な例を挙げて説明する。
【００３７】
［２．１ データ構成］
まず、劣化パス検出装置１が処理に用いるデータについて説明する。
図３は、劣化パス検出装置１の記憶部１５に記憶されるデータのデータ構造を示す図である。同図に示すデータ構造は、通信品質（ＩＰ品質）の各劣化値や劣化補正値として、１種類の品質情報（例えば、遅延）のみを扱う場合のものである。
【００３８】
ノード情報は、各ノードに対応しており、各ノード情報には、対応するノード（自ノード）に関する情報が格納され、自ノードに関する情報として子ノードに対応したノード情報も格納される。測定対象ネットワークは木構造（又は木構造に分割可能）であるため、１つのノード情報には、１以上の子ノードのノード情報が格納されることになる。また、自ノードに関する情報として、１以上の子ノードペア情報も格納される。
【００３９】
同図において、ノード情報は、ノードＩＤ、リンク劣化値、子ノードペアリスト、子ノードリスト、部分木構成ノード、リンク合計劣化値、及び、リンク劣化補正値のデータからなる。
ノードＩＤは、各ノード情報が対応しているノード（自ノード）を一意に識別可能な識別子である。
リンク劣化値は、自ノードと、自ノードの親ノードとの間のリンク劣化値を示す。
子ノードペアリストは、自ノードをルートとする部分木において、測定時にペアとした子ノードを示す子ノードペア情報が格納されるリスト情報である。子ノードペア情報は、ペアとなった２つの子ノードのノードＩＤと、その２つの子ノードそれぞれに付随する測定端末Ｔ間の劣化値を示すパス劣化値とのデータからなる。
子ノードリストは、自ノードに接続されている子ノードのノード情報が格納されるリスト情報である。
部分木構成ノードは、自ノードと測定端末Ｔとの間のリンク劣化値の和が最大となる経路に属する子ノードを示す。ここでは、子ノードのノードＩＤが設定される。
リンク合計劣化値は、部分木構成ノードをたどってできる、自ノードから測定端末Ｔまでの経路上のノードに設定されているリンク劣化値の合計値を示す。
リンク劣化補正値は、劣化と判定されたパスに属する自ノードと親ノード間のリンク劣化値を示す。
【００４０】
本実施形態では、１種類の品質情報だけを対象としたデータ構造を例に説明を記載するが、複数種類（遅延とロス）の品質情報を扱うようにしてもよい。複数種類（遅延とロス）の品質情報を扱う場合、それぞれの情報を格納する領域を用意するか、種類毎に図３に示すデータを利用しても良い。なお、本データ構造は一例であり、他のデータ構造を用いて処理を実施してもよい。
【００４１】
図面においてノード情報の設定例を示す際、１行目はノードＩＤ、２行目はリンク劣化値、３行目は子ノードペアリスト、４行目は子ノードリスト、５行目は部分木構成ノード、６行目はリンク合計劣化値、７行目はリンク劣化補正値の設定値を示す。また、図面において子ノードペア情報の設定例を示す際、１行目及び２行目はノードＩＤ、３行目はパス劣化値を示す。また、ノード情報内において、子ノードリストペアリストは、子ノードペア情報が設定されているペアの子ノードの識別情報を記載して示し、子ノードリストは、ノード情報が設定されている子ノードの識別情報を記載して示す。
【００４２】
また、ノードの部分木構成ノードを辿っていくことによって得られる測定端末Ｔを「ノードに付随する測定端末Ｔ」と記載する。あるノードに付随する測定端末Ｔを特定する場合、まず、そのノードのノード情報を読み出し、読み出したノード情報から部分木構成ノードを読み出す。そして、部分木構成ノードにノードＩＤが設定されていれば、その設定されているノードＩＤにより特定されるノード情報を読み出す処理を、部分木構成ノードが設定されていないノード情報に至るまで繰り返す。部分木構成ノードが設定されていないノード情報に設定されているノードＩＤで特定されるノード、つまり、部分木構成ノードがないノード情報に対応するノードが付随する測定端末Ｔである。また、このとき読み出されたノード情報は、あるノードから付随する測定端末Ｔに至るパスに存在するノードのノード情報である。
以下に示す処理の説明においては、ノードに付随する測定端末Ｔを特定する手順、及び、ノードから付随する測定端末Ｔに至るパスに存在するノードのノード情報を取得する手順は上記により行なうものとし、省略して記載する。
【００４３】
［２．２ 処理手順］
［２．２．１ 劣化パス検出全体処理］
図４は、劣化パス検出装置１における劣化パス検出全体の処理フローを示す図である。
劣化パス検出装置１は、所定の時間毎周期的に、指定された時間になった場合に、あるいは、外部から分析指示が入力された場合に、劣化パス検出処理を起動する。まず、劣化パス検出装置１は、ネットワークトポロジ情報記憶装置２に記憶されているネットワークトポロジ情報を参照し、第一階層〜第Ｎ階層を順に処理対象の層として選択すると、ステップＳ２０以降の処理を順に行なう（ステップＳ１０）。さらに、ステップＳ１０において選択された処理対象の層の全てのノードが選択されるまで、ステップＳ３０〜Ｓ８０までの処理を行なう（ステップＳ２０）。
なお、劣化パス検出装置１の部分木ネットワーク構築部１１は、ネットワークトポロジ情報を参照し、測定端末Ｔに接続されているルータＲを第一階層のノードとして選択し、第一階層のルータＲに接続されている未選択のルータＲを第二階層のノードとして選択することを、全てのルータＲが選択されるまで繰り返すことによって、第Ｎ階層までのルータＲをノードとして選択することができる。なお、各ルータＲが属している階層の情報を予めネットワークトポロジ情報に設定してもよい。
【００４４】
劣化パス検出装置１は、処理対象の層でまだ選択していないノードを１つ選択し（ステップＳ３０）、図５に示す部分木データ構築処理によって、木構造のネットワークである測定対象ネットワークを、ステップＳ３０において選択したノードをルートノードとした部分木に分割し（ステップＳ４０）、図６に示す部分木内測定処理によって、ステップＳ４０において分割した部分木内で測定を行う（ステップＳ５０）。劣化パス検出装置１は、ステップＳ５０の測定結果に基づき、図９に示す劣化区間候補抽出処理によって、ルートノード−リーフノード間の劣化値が最大となる可能性が高い区間を抽出する（ステップＳ６０）。抽出した区間と他の区間を結ぶパスが劣化パスとなるかを判定するため、図１０及び図１１に示す折り返し劣化分析処理によって、部分木内における劣化パスの有無の分析を行なう（ステップＳ７０）。そして、図１２に示す最大劣化区間抽出処理により、抽出済みの区間が部分木内におけるルートノードとリーフノード間における最大の劣化値の区間であるかを分析し、真にノードとリーフノード間の劣化値が最大となる区間を抽出する（ステップＳ８０）。
劣化パス検出装置１の出力部１６は、上記処理の終了後、検出された劣化パスを出力する（ステップＳ９０）。
以下に、ステップＳ４０〜ステップＳ８０までの各処理の詳細を説明する。ステップＳ４０〜ステップＳ８０の各処理の入力パラメータはステップＳ３０において選択されたノードである。なお、ステップＳ３０において選択されたノード（ルータＲ）を「選択ノード」と記載する。
【００４５】
［２．２．２ 部分木データ構築処理］
［２．２．２．１ 処理フロー］
図５は、劣化パス検出装置１の部分木ネットワーク構築部１１による部分木データ構築処理の処理フローを示す図であり、図４のステップＳ４０の詳細な処理を示している。なお、部分木の構築方法、部分木データの構造については、一例であり、これに限定するものではない。
【００４６】
まず、劣化パス検出装置１の部分木ネットワーク構築部１１は、選択ノードのノード情報を記憶部１５に新規に生成して書き込み、この生成したノード情報のノードＩＤに、選択ノードのノードＩＤを書き込む（ステップＳ１０１）。続いて、部分木ネットワーク構築部１１は、ネットワークトポロジ情報記憶装置２に記憶されているネットワークトポロジ情報を参照し、選択ノードの全ての子ノードのノードＩＤを抽出する（ステップＳ１０２）。
【００４７】
部分木ネットワーク構築部１１は、抽出した子ノードのノードＩＤが設定されているノード情報がまだ記憶部１５に登録されていないと判断した場合（ステップＳ１０３：ＮＯ）、記憶部１５にステップＳ１０２において抽出した子ノードのノード情報を新規に生成して書き込み、この生成した各ノード情報に、対応する子ノードのノードＩＤを書き込む（ステップＳ１０４）。さらに、部分木ネットワーク構築部１１は、ステップＳ１０１において生成した選択ノードのノード情報内の子ノードリストに、ステップＳ１０４において生成した子ノードのノード情報を書き込む（ステップＳ１０５）。
【００４８】
一方、ステップＳ１０２において抽出した子ノードのノードＩＤが設定されているノード情報がすでに記憶部１５に登録されていると判断した場合（ステップＳ１０３：ＹＥＳ）、部分木ネットワーク構築部１１は、記憶部１５から子ノードのノードＩＤが設定されているノード情報を抽出し、ステップＳ１０１において生成した選択ノードのノード情報内の子ノードリストに、抽出した子ノードのノード情報を書き込む（ステップＳ１０５）。
【００４９】
［２．２．２．２ 具体例による処理の説明］
例えば、第二階層に１台のノードがあり、その子ノードとして第一階層にノードＮ［１］とノードＮ［２］があり、ノードＮ［１］には測定端末層のノードＮ［３］からノードＮ［５］の３台の測定端末Ｔが、ノードＮ［２］には測定端末層のノードＮ［６］からノードＮ［８］の３台の測定端末Ｔが接続されているネットワークを想定する。
図４に示す全体のアルゴリズムは、第一階層に含まれるノードから順に処理を行うため、この場合、ステップＳ３０において最初に選択されるノードは、ノードＮ［１］もしくはノードＮ［２］のどちらかとなる。どちらの場合も部分木データ構築処理は同じであるため、ノードＮ［１］が選択された場合についについて説明する。
【００５０】
（１）ノードＮ［１］が選択されたため、ノードＮ［１］に対応して、ノードＩＤ「１」が設定されたノード情報を生成し、記憶部１５に登録する（ステップＳ１０１）。
【００５１】
（２）ノードＮ［１］に接続される子ノードは、ノードＮ［３］〜ノードＮ［５］としての測定端末Ｔであり、これらの子ノードに対するノード情報は未生成であるため、ノードＮ［３］〜ノードＮ［５］のノード情報を生成し、記憶部１５に登録する（ステップＳ１０２〜Ｓ１０４）。
これにより、ノードＩＤ「３」が設定されたノード情報、ノードＩＤ「４」が設定されたノード情報、及び、ノードＩＤ「５」が設定されたノード情報が生成される。
【００５２】
（３）選択ノードであるノードＮ［１］と、子ノードであるノードＮ［３］〜ノードＮ［５］とを関連づけるため、選択ノードのノード情報に、（２）で生成した全ての子ノードのノード情報を子ノードリストとして書き込む（ステップＳ１０５）。
【００５３】
他の第一階層に含まれるノードが選択ノードとなった場合も、上記と同様な処理を行う。ただし、第二階層以上のノードが選択ノードとなった場合、選択ノードのノード情報を生成するまでは同様であるが（ステップＳ１０１）、その子ノードのノード情報は既に生成済みである（ステップＳ１０２、Ｓ１０３：ＮＯ）。そのため、選択ノードのノード情報に子ノードリストとして、その生成済みの子ノードのノード情報のリストを追加する処理（ステップＳ１０５）を行う。
【００５４】
［２．２．３ 部分木内測定処理］
［２．２．３．１ 処理フロー］
図６は、劣化パス検出装置１における部分木内測定処理の処理フローを示す図であり、図４のステップＳ５０の詳細な処理を示している。本処理フローでは、部分木内における測定端末Ｔの選択方法と、選択した測定端末Ｔ間の測定によって得られる測定劣化値に基づく処理が含まれる。
【００５５】
部分木内における最初の測定端末Ｔの選択方法は、以下の理由により、網羅率１００％となるように選択している。
（ａ）網内の全てのエレメントを最低１回は通過するように測定しないと、劣化パスの検出漏れに繋がる可能性がある。
（ｂ）最初の測定において、網羅率１００％を超えるパスの測定をすると、劣化パス検出に不必要なパスとなる可能性があり、網に対して不必要に負荷を与えることになる。
つまり、まず網羅率１００％での測定を行い、その測定結果を踏まえた測定を行うことで、必要最小限の測定となるようにしている。
【００５６】
劣化パス検出装置１の測定端末選定／劣化分析部１４は、選択ノードのノード情報に設定されている子ノードリストにより示される子ノードの中で、未選択の子ノードを選択し、全ての子ノードについて選択を終了するまで以下のステップＳ２０２〜Ｓ２１６の処理が行われる（ステップＳ２０１）。
【００５７】
まず、測定端末選定／劣化分析部１４は、選択ノードが第一階層に含まれるか判断する（ステップＳ２０２）。第一階層に含まれる場合（ステップＳ２０２：ＹＥＳ）、測定指示実行部１２は、未選択の子ノードが２つ以上であれば（ステップＳ２０６：２つ以上）、未選択の子ノードの中からランダムに２つの子ノードを選択し（ステップＳ２０８）、未選択の子ノード数が１つであれば（ステップＳ２０６：１つ）、未選択の子ノードと、選択済みの子ノードからランダムに１つを選択する（ステップＳ２０７）。
【００５８】
一方、選択ノードが第一階層に含まれない場合（ステップＳ２０２：ＮＯ）、測定端末選定／劣化分析部１４は、未選択の子ノードが２つ以上であれば（ステップＳ２０３：２つ以上）、未選択の子ノードの中から、リンク合計劣化値最も大きい２つの子ノードを選択し（ステップＳ２０５）、未選択の子ノード数が１つであれば（ステップＳ２０３：１つ）、未選択の子ノードと、リンク合計劣化値が最小の選択済みの子ノードを選択する（ステップＳ２０４）。リンク合計劣化値は、選択ノードのノード情報に子ノードリストとして設定されている子ノードのノード情報から読み出す。
【００５９】
ステップＳ２０８、または、ステップＳ２０５に続いて、測定端末選定／劣化分析部１４は、子ノードペア情報を生成して記憶部１５に書き込むと、生成した子ノードペア情報に、選択した２つの子ノードのノードＩＤを書き込む（ステップＳ２０９）。測定端末選定／劣化分析部１４は、選択ノードのノード情報に、子ノードペアリストとしてステップＳ２０９において生成した子ノードペア情報を追加する（ステップＳ２１０）。測定端末選定／劣化分析部１４が、選択した子ノードペアの２つの子ノードそれぞれに付随する測定端末Ｔを特定し、そのアドレス情報を読み出すと（ステップＳ２１１）、測定指示実行部１２は、読み出したアドレスを用いて特定した測定端末Ｔに対して測定指示を出力する（ステップＳ２１２）。測定指示には、ペアとなる相手先の測定端末Ｔのアドレス情報が含まれる。
【００６０】
劣化パス検出装置１からの測定指示を受信した測定端末Ｔは、相手先となるペアの測定端末Ｔに対して品質測定用のパケットを送信し、その結果得られた通信パケットの伝送情報を劣化パス検出装置１に返送する。劣化パス検出装置１の測定結果受信／劣化値算出部１３は、測定指示を出力した測定端末Ｔから通信パケットの伝送情報を測定結果として受信すると（ステップＳ２１３）、測定結果により示される通信パケットのタイムスタンプ及びシーケンス番号に基づいて測定劣化値を得る。ここでは、遅延を得るものとする。測定端末選定／劣化値分析部１４は、算出した測定劣化値を補正した後、ステップＳ２１０において追加した子ノードペア情報のパス劣化値に補正後の劣化値を書き込む（ステップＳ２１４）。測定劣化値の補正とは、測定パス内に含まれるノードのノード情報に設定されているリンク劣化補正値の合計を減算する処理である。
【００６１】
測定端末選定／劣化値分析部１４は、パス劣化値が「０」であった場合（ステップＳ２１５：ＹＥＳ）、選択した子ノードペアのノードＩＤが設定されているノード情報内のリンク劣化値に「０」を書き込む（ステップＳ２１６）。
【００６２】
上記のステップＳ２１６までの処理を、選択ノードの全ての子ノードについて終了すると、測定端末選定／劣化値分析部１４は、ステップＳ２１４においてパス劣化値を書き込んだ子ノードペア情報を参照し、上記において測定を行なった子ノードペアのうち、パス劣化値が劣化パスと検出するための所定の閾値を超えている子ノードペアを抽出する（ステップＳ２１７）。測定端末選定／劣化値分析部１４は、ステップＳ２１７において抽出された子ノードペアがなかった場合（ステップＳ２１８：ＮＯ）、処理を終了し、呼び出し元に戻る。ステップＳ２１７において抽出された子ノードペアがあった場合（ステップＳ２１８：ＹＥＳ）、抽出した子ノードペアに付随する測定端末Ｔ間のパスを劣化パスとして検出し（ステップＳ２１９）、抽出した子ノードペアを入力として図７に示す測定劣化パス処理を実行する（ステップＳ２２０）。
【００６３】
［２．２．３．２ 具体例による処理の説明］
上述した処理フローに従い、網羅率１００％の測定による部分木データに対する部分木内測定処理の内容を説明する。
【００６４】
（１）測定端末選定／劣化分析部１４は、選択ノードの子ノードから２つずつのペアを作成し、ペア毎の子ノードペア情報を生成する（ステップＳ２０１〜Ｓ２０９）。
ここでは、網羅率１００％の測定を実施したいので、子ノードのペアは重複を最小限となるようにペアリングする。そして、ペアとした子ノードそれぞれに対し、子ノードペア情報を生成する。例えば、選択ノードがノードＮ［１］であり、その子ノードのうちノードＮ［２］とノードＮ［３］を子ノードペアとしたときの子ノードペア情報には、ノードＩＤ「２」、「３」が設定される。
【００６５】
（２）続いて、測定端末選定／劣化分析部１４は、（１）において生成した子ノードペア情報を選択ノードに関連付ける（ステップＳ２１０）。
例えば、選択ノードがノードＮ［１］、ノードＮ［１］の子ノードがノードＮ［２］、ノードＮ［３］、ノードＮ［１０］、ノードＮ［１１］であるとする。この場合、選択ノードのノード情報には、ノードＩＤ「１」、子ノードリスト「２、３、１０、１１」が設定されている。そして、ノードＮ［２］及びノードＮ［３］のペアと、ノードＮ［１０］及びノードＮ［１１］のペアが生成された場合、選択ノードのノード情報には、子ノードペアリストとして、ノードＩＤ「２」、「３」が設定された子ノードペア情報、ノードＩＤ「１０」、「１１」が設定された子ノードペア情報が設定される。
【００６６】
（３）測定指示実行部１２は、生成した子ノードのペアそれぞれに付随する測定端末Ｔ間で測定を実施し、測定結果受信／劣化値算出部１３は、測定端末Ｔから受信した測定結果に基づいて測定劣化値を算出する。測定端末選定／劣化値分析部１４は、測定劣化値から測定パス内に含まれるノードのノード情報に設定されているリンク劣化補正値を減算し、減算結果を子ノードペア情報のパス劣化値に設定する（ステップＳ２１１〜Ｓ２１５）。
例えば、図１４のように、選択ノードがノードＮ［１］、ノードＮ［１］の子ノードペアがノードＮ［２］及びノードＮ［３］、ノードＮ［２］に付随する測定端末Ｔが、子ノードであるノードＮ［４］に接続されたノードＮ［６］、ノードＮ［３］に付随する測定端末Ｔが、子ノードであるノードＮ［５］に接続されたノードＮ［７］であるとする。同図に示す関係にある測定端末Ｔ間、つまり、ノードＮ［６］−ノードＮ［７］間において品質測定を実施し、測定劣化値が「４０」だったとする。
このとき、この測定パス内の各ノードに対するノード情報全てにリンク劣化補正値が設定されていなければ、ノードＩＤ「２」、「３」が設定されている子ノードペア情報のパス劣化値には、測定劣化値「４０」がそのまま設定される。
【００６７】
一方、この測定パス内のノードに対するノード情報にリンク劣化補正値が設定されている場合、そのリンク劣化補正値の合計値を測定劣化値から減算し、減算結果を子ノードペア情報のパス劣化値に設定する。
例えば、ノードＮ［４］に対応したノード情報にリンク劣化補正値「１０」、ノードＮ［７］に対応したノード情報にリンク劣化補正値「２０」が設定されていたとすると、その合計値である「３０」を測定劣化値「４０」から減算し、減算結果「１０」をノードＩＤ「２」、「３」が設定されている子ノードペア情報のパス劣化値に書き込む。
【００６８】
（４）測定端末選定／劣化値分析部１４は、子ノードペア情報のパス劣化値に設定された値が「０」の場合、子ノードペア情報に設定されている２つのノードＩＤに対するノード情報内のリンク劣化値に「０」を書き込む（ステップＳ２１５〜Ｓ２１６）。
例えば、ノードＩＤ「２」、「３」の子ノードペア情報のパス劣化値に「０」が設定されたとする。ノードＩＤ「２」が設定されているノードＮ［２］のノード情報、及び、ノードＩＤ「３」が設定されているノードＮ［３］のノード情報のリンク劣化値にも「０」を設定する。
【００６９】
（５）子ノードペア全てに対して測定を実施し、パス劣化値の設定が完了したら、測定端末選定／劣化値分析部１４は、劣化閾値を超えるパス劣化値が設定された子ノードペア情報を抽出する。抽出できた場合、その抽出された子ノードペア情報により特定される各ノードに付随する測定端末Ｔ間のパスを劣化パスとして検出するとともに、抽出された子ノードペア情報を測定劣化パス処理に渡す（ステップＳ２１７〜Ｓ２２０）。
【００７０】
［２．２．４ 測定劣化パス処理］
［２．２．４．１ 処理フロー］
図７は、劣化パス検出装置１における測定劣化パス処理の処理フローを示す図である。
測定劣化パス処理には、部分木内における測定端末Ｔの選択方法と、選択した測定端末Ｔ間の測定によって得られる測定劣化値に基づく処理が含まれる。
【００７１】
同図に示す測定劣化パス処理は、網羅率１００％での測定によって得られた測定劣化値と測定パス内のノードに対応したノード情報内のリンク劣化補正値とから得られるパス劣化値が劣化閾値を超えた劣化パスが検出された際の処理である。
他の処理においても共通して言えることであるが、パス劣化値、および、劣化パス内の各リンクの劣化値を「０」と置くことにより、他のパスが検出済みの劣化パスの一部と重複することによって劣化パスとして検出されてしまう（他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスとなる）状態を抑制している。
また、ルートノードとリーフノード間の劣化値が２番目に高い区間が、他の部分木における最大劣化区間と接続されることによって、劣化パスとなる可能性があることから、部分木を再構築することによって、そのようなパスの検出を可能としている。
【００７２】
同図において、劣化パス検出装置１の測定端末選定／劣化値分析部１４は、図６のステップＳ２１９において劣化パスとして検出された子ノードペアの子ノードペア情報全てが選択されるまで、以下のステップＳ３０２〜Ｓ３１１までの処理を行なう（ステップＳ３０１）。
【００７３】
まず、測定端末選定／劣化値分析部１４は、図６のステップＳ２１９において劣化パスとして検出された子ノードペアの子ノードペア情報のうち、ステップＳ３０１において選択した子ノードペア情報以外の未選択の子ノードペア情報の数が１つであるか、２つ以上であるかを判断する（ステップＳ３０２）。２つ以上であると判断した場合（ステップＳ３０２：２つ以上）、測定端末選定／劣化値分析部１４は、未選択の子ノードペア情報からランダムに２つの子ノードペア情報を選択し（ステップＳ３０３）、１つであると判断した場合（ステップＳ３０２：１つ）、選択ノードのノード情報に設定されている子ノードペアリストに設定されている子ノードペア情報の中から１つをランダムに選択するとともに、未選択の子ノードペア情報を選択する（ステップＳ３０４）。
【００７４】
測定端末選定／劣化値分析部１４は、ステップＳ３０３またはＳ３０４において選択した子ノードペア情報（本処理フローの説明では、「選択子ノードペア情報」と記載）により示される子ノードについて、図８に示すリンク劣化値算出処理を実行し、各子ノードと選択ノードとの間のリンク劣化値を算出する（ステップＳ３０５）。続いて、測定端末選定／劣化値分析部１４は、選択ノードが第一階層のノードであるか否かを判断する（ステップＳ３０６）。
【００７５】
選択ノードが第一階層のノードである場合（ステップＳ３０６：ＹＥＳ）、選択子ノードペア情報のパス劣化値に「０」を書き込む（ステップＳ３０７）。さらに、測定端末選定／劣化値分析部１４は、この選択子ノードペア情報により示される子ノードのノード情報に対し、現在設定されているリンク劣化値をリンク劣化補正値に設定した後、リンク劣化値に「０」を設定する（ステップＳ３０８）。
【００７６】
一方、選択ノードが第一階層のノードではない場合（ステップＳ３０６：ＮＯ）、測定端末選定／劣化値分析部１４は、ステップＳ３０３またはＳ３０４において未選択の中から選択された選択子ノードペア情報から子ノードのノードＩＤを抽出し（ステップＳ３０９）、この抽出したノードＩＤの子ノードに対して図１３に示す部分木再構築処理を行なう（ステップＳ３１０）。部分木再構築処理では、劣化パス内のルートノードとリーフノード間の劣化値に次いで２番目に高い区間が部分木の構成要素となるように、部分木を再構築する。測定端末選定／劣化値分析部１４は、部分木再構築処理が終了すると、再構築処理後の各子ノードに付随する測定端末Ｔ間とのパスの中に含まれるノードのノード情報からリンク劣化値を読み出してその和を算出し、算出結果のリンク劣化値を子ノードペア情報のパス劣化値に設定する（ステップＳ３１１）。
【００７７】
［２．２．４．２ 具体例による処理の説明］
上述した処理フローに従い、網羅率１００％の測定によって、劣化パスが検出された際の部分木データに対する処理を記載する。
例えば、図１４に示す部分木において、選択ノードであるノードＮ［１］の子ノードペアであるノードＮ［２］、ノードＮ［３］それぞれに付随する測定端末Ｔ、すなわち、ノードＮ［６］−ノードＮ［７］間で品質測定を実施した結果、パス劣化値が「７０」であり、劣化閾値を超えた場合を考える。この場合、ノードＩＤ「２」、「３」が設定された子ノードペア情報のパス劣化値には「７０」が設定される。
【００７８】
（１）劣化パスとなった子ノードペア情報を２つずつのペアとして、選択ノードと各子ノード間のリンクの劣化値を算出する（ステップＳ３０１〜Ｓ３０５）。
子ノードペア情報のペアリング方法は、抽出された子ノードペア情報が偶数個の場合と奇数個の場合で異なる。抽出された子ノードペア情報が偶数個の場合は、抽出された子ノードペア情報のみからペアリングを行う。奇数個の場合は、抽出された子ノードペア情報のみからペアリングを行なっていき、最後の１つの子ノードペア情報は、他の子ノードペア情報から１つを選択してペアリングする。また、後述するリンク劣化値算出処理によって、抽出した子ノードペア情報により示される子ノードと選択ノード間のリンク劣化値を算出する。
【００７９】
（２）選択ノードが第一階層に含まれる場合は、その測定に利用した子ノードペア情報のパス劣化値を「０」に変更し、算出した選択ノードと各子ノード間のリンク劣化値を、各子ノードのノード情報のリンク劣化補正値に設定し、リンク劣化値には「０」を設定する（ステップＳ３０６〜Ｓ３０８）。
例えば、選択ノードが第一階層のノードＮ［１０］であり、ノードＮ［１０］にはノードＮ［１１］、ノードＮ［１２］としての２台の測定端末Ｔが接続され、ノードＮ［１１］−ノードＮ［１２］間の劣化値が「７０」であったとする。部分木ネットワーク構築部１１は、ノードＩＤ「１１」、「１２」の子ノードペア情報に現在設定されているパス劣化値「７０」を「０」に書き換える。
また、ステップＳ３０５のリンク劣化値算出処理において、ノードＮ［１０］−ノードＮ［１１］間の劣化値は「４０」、ノードＮ［１０］−ノードＮ［１２］間の劣化値は「３０」であったとする。測定端末選定／劣化分析部１４は、ノードＩＤ「１１」のノード情報内にリンク劣化値「０」、及び、リンク劣化補正値「４０」を書き込み、ノードＩＤ「１２」のノード情報内には、リンク劣化値「０」、及び、リンク劣化補正値「３０」を書き込む。
【００８０】
（３）選択ノードが第一階層以外の場合、ステップＳ３１０における部分木データ再構築処理（詳細は後述）により、各子ノードに付随する測定端末Ｔが、劣化パス検出時に測定端末Ｔと異なるものに変わっている可能性がある（ステップＳ３０９〜Ｓ３１１）。
次に実施する劣化区間候補抽出処理を実施するためには、選択ノードの子ノードペア情報全てに対して、部分木構成と整合が取れたパス劣化値が付与されている必要がある。そのため、部分木データ再構築処理後の子ノードペア情報に設定されている２つのノードに付随する測定端末Ｔ間のパス内に属する各ノードのノード情報に設定されているリンク劣化値の和を算出し、算出結果をパス劣化値に設定する。
【００８１】
図１５（ａ）は、図１４の部分木における各リンクのリンク劣化値を示し、図１５（ｂ）は、部分木内のノードのノード情報を示す図である。選択ノードＮ［１］の子ノードペアであるノードＮ［２］、ノードＮ［３］それぞれに付随する測定端末Ｔ、すなわち、ノードＮ［６］−ノードＮ［７］間で測定を行った結果、劣化パスとして検出され、ステップＳ３０６のリンク劣化値算出処理によって、選択ノードと各子ノード間のリンク劣化値が算出された状態を示したものである。選択ノードと各子ノード間のリンク劣化値は、ノードＮ［１］−ノードＮ［２］間が「１０」、ノードＮ［１］−ノードＮ［３］間が「０」である。
このとき、部分木データ再構築（ステップＳ３１０）処理を実施した結果、図１６（ａ）に示すようにノードＮ［２］に付随する測定端末ＴがノードＮ［１０］に、ノードＮ［３］に付随する測定端末ＴがノードＮ［１１］に変更され、また、劣化パス内の各ノードのノード情報がそれぞれ変更されたとする。
【００８２】
図１６（ｂ）に示すように、ノードＮ［２］のノード情報においては、リンク劣化値が「１０」から「０」に、リンク合計劣化値が「３０」から「１０」に、リンク劣化補正値が「ＮＵＬＬ」から「１０」に更新され、ノードＮ［３］のノード情報においては、リンク劣化値が「０」から「０」に、部分木構成ノードが「５」から「９」に、リンク合計劣化値が「３０」から「２０」に、リンク劣化補正値が「ＮＵＬＬ」から「０」に更新されている。
また、ノードＮ［４］のノード情報においては、リンク劣化値が「０」から「０」に、部分木構成ノードが「６」から「１０」に、リンク合計劣化値が「３０」から「１０」に、リンク劣化補正値が「ＮＵＬＬ」から「０」に更新され、ノードＮ［５］のノード情報においては、リンク劣化値が「２０」から「０」に、部分木構成ノードが「７」から「８」に、リンク合計劣化値が「１０」から「１０」に、リンク劣化補正値が「ＮＵＬＬ」から「２０」に更新されている。
また、ノードＮ［６］のノード情報においては、リンク劣化値が「３０」から「０」に、リンク劣化補正値が「ＮＵＬＬ」から「３０」に更新され、ノードＮ［７］のノード情報においては、リンク劣化値が「１０」から「０」に、リンク劣化補正値が「ＮＵＬＬ」から「１０」に更新されている。
【００８３】
これはつまり、部分木データ再構築処理によってノードＮ［２］ノードＮ［３］にそれぞれ付随する測定端末Ｔ間のパスが変更になったことを意味する。
よって、部分木ネットワーク構築部１１は、ノードＮ［２］−ノードＮ［３］のペアを示す子ノードペア情報のパス劣化値として、各ノード（ノードＮ［２］、ノードＮ［３］、ノードＮ［４］、ノードＮ［９］、ノードＮ［１０］、ノードＮ［１１］）のリンク劣化値（０，０，０，１０，１０，１０）の和である「３０」を設定する。すなわち、ノードＩＤ「２」、「３」の子ノードペア情報にパス劣化値「３０」が設定される。
これまでの処理により、ノードＮ［２］−ノードＮ［３］のペアを示す子ノードペア情報のパス劣化値は、ステップＳ２１４において「７０」が設定され、ステップＳ３１１において「３０」に変更される。
【００８４】
［２．２．５ リンク劣化値算出処理］
［２．２．５．１ 処理フロー］
図８は、劣化パス検出装置１におけるリンク劣化値算出処理の処理フローを示す図である。
リンク劣化値算出処理では、部分木のルートノードである選択ノードと、選択ノードの４つの子ノード間それぞれのリンクの劣化値を算出する。
【００８５】
同図において、測定端末選定／劣化値分析部１４は、選択されている２つの子ノードペア情報それぞれに設定されているノードＩＤを読み出し、読み出したノードＩＤにより特定されるノード情報の全てにリンク劣化値が設定されているか否かを判断する（ステップＳ４０１）。全てのノード情報にリンク劣化値が設定されていると判断した場合（ステップＳ４０１：ＹＥＳ）、そのまま処理を終了する。特定されたノード情報の中にリンク劣化値が設定されていないものがあると判断した場合（ステップＳ４０１：ＮＯ）、測定端末選定／劣化値分析部１４は、２つの子ノードペア情報の両方に同一のノードＩＤが設定されているか否かを判断する（ステップＳ４０２）。
【００８６】
２つの子ノードペア情報の両方に同一のノードＩＤが設定されていると判断した場合（ステップＳ４０２：ＹＥＳ）、測定端末選定／劣化値分析部１４は、一方の子ノードペア情報のみに設定されているノードＩＤを抽出する（ステップＳ４０３）。このとき、２つのノードＩＤが抽出される。測定端末選定／劣化値分析部１４は、抽出した２つのノードＩＤにより特定されるノードに付随する測定端末Ｔを特定し、測定指示実行部１２は、ネットワークトポロジ情報から特定した測定端末Ｔのアドレス情報を読み出すと、特定した測定端末Ｔに対して、相手先の測定端末Ｔのアドレス情報を設定した測定指示を出力する。劣化パス検出装置１からの測定指示を受信した測定端末Ｔは、相手先となるペアの測定端末Ｔに対して品質測定用のパケットを送信し、その結果得られた通信パケットの伝送情報を劣化パス検出装置１に返送する。劣化パス検出装置１の測定結果受信／劣化値算出部１３は、測定指示を出力した測定端末Ｔから通信パケットの伝送情報を測定結果として受信し、測定劣化値を得る（ステップＳ４０４）。
【００８７】
一方、２つの子ノードペア情報の両方に同一のノードＩＤが設定されていないと判断した場合（ステップＳ４０２：ＮＯ）、測定端末選定／劣化値分析部１４は、２つの子ノードペア情報の一方に設定されているノードＩＤの中からランダムにノードＩＤを抽出すると（ステップＳ４０５）、この抽出したノードＩＤにより特定されるノードに付随する測定端末Ｔを特定する（ステップＳ４０６）。この特定した測定端末Ｔを端末Ａとする。さらに、測定端末選定／劣化値分析部１４は、他方の子ノードペア情報に設定されている２つのノードＩＤを抽出すると、この抽出した２つのノードＩＤにより特定されるノードそれぞれに付随する測定端末Ｔを特定する（ステップＳ４０７）。この特定した測定端末Ｔをそれぞれ端末Ｂ，端末Ｃとする。
測定指示実行部１２は、ネットワークトポロジ情報から特定した端末Ａ，Ｂ，Ｃのアドレス情報を読み出すと、端末Ａ及び端末Ｂに対して、端末Ａ−端末Ｂ間の測定指示を出力するとともに、端末Ａ及び端末Ｃに対して、端末Ａ−端末Ｃ間の測定指示を出力する。劣化パス検出装置１からの測定指示を受信した端末Ａ，Ｂ，Ｃは、相手先となるペアの測定端末Ｔに対して品質測定用のパケットを送信し、その結果得られた通信パケットの伝送情報を劣化パス検出装置１に返送する。劣化パス検出装置１の測定結果受信／劣化値算出部１３は、受信した通信パケットの伝送情報から、端末Ａ−端末Ｂ間、端末Ａ−端末Ｃ間の測定劣化値を得ると、この算出した測定劣化値を補正した後の端末間劣化値を得る（ステップＳ４０８）。
【００８８】
測定端末選定／劣化値分析部１４は、ステップＳ４０４において得られた測定劣化値、または、ステップＳ４０８において得られた補正処理後の端末間劣化値から、選択ノードと各測定端末Ｔの劣化値を算出する（ステップＳ４０９）。さらに、測定端末選定／劣化値分析部１４は、子ノードペア情報内のノードＩＤにより特定される各子ノードと、親ノードである選択ノードとの間の劣化値を算出し、子ノードのノードＩＤにより特定されるノード情報内に算出したリンク劣化値を書き込む（ステップＳ４１０）。
【００８９】
［２．２．５．２ 具体例による処理の説明］
図８に示すリンク劣化値算出処理によって、選択ノードと選択ノードの子ノード間の劣化値を算出するための測定、および算出方法について説明する。
【００９０】
（１）リンク劣化値算出処理に対する入力は、２つの子ノードペア情報である。これらに属するノードのノード情報全てにリンク劣化値が設定されていれば、新たに算出する必要がないので、本処理はスキップする（ステップＳ４０１）。
【００９１】
（２）リンク劣化値を算出する場合、選択された子ノードペア情報に属するノードの状態によって、以下の２つが考えられる。
（状態１）図１７（ａ）に示すように、選択ノードＮ［１］の一方の子ノードペアがノードＮ［２］−ノードＮ［３］であり、もう一方の子ノードペアがノードＮ［３］−ノードＮ［４］であるとする。ノードＮ［２］、［３］、［４］はそれぞれ、ノードＮ［１０］、［１１］、［１２］の測定端末Ｔに接続されている。
（状態２）図１８（ａ）に示すように、選択ノードＮ［１］の一方の子ノードペアがノードＮ［２］−ノードＮ［３］であり、もう一方の子ノードペアがノードＮ［４］−ノードＮ［５］であるとする。この場合、２つの子ノードペア情報に重複するノードが存在しない。
【００９２】
（２−１）：図１７（ａ）に示す状態１の場合、２つの子ノードペア情報に重複するノードはノードＮ［３］であるため、図１７（ｂ）に示すように、一方の子ノードペアにのみ属しているノードＮ［２］及びノードＮ［４］を抽出し、抽出したノードに付随する測定端末Ｔ、すなわち、ノードＮ［１０］−ノードＮ［１２］間で測定を実施し、測定劣化値を算出する（ステップＳ４０２〜Ｓ４０４）。
【００９３】
（２−２）：図１８（ａ）に示す状態２の場合、一方の子ノードペア（ノードＮ［２］−ノードＮ［３］）からランダムにノードを抽出（例えばノードＮ［２］）し、そのノードに付随する測定端末Ｔを端末Ａ（ノードＮ［１０］）として抽出する（ステップＳ４０５〜Ｓ４０６）。
次に、他の子ノードペア（ノードＮ［４］、ノードＮ［５］）それぞれに付随する測定端末Ｔを端末Ｂ（ノードＮ［１２］）、端末Ｃ（ノードＮ［１３］）として抽出する。そして、図１８（ｂ）に示すように、端末Ａ−端末Ｂ、端末Ａ−端末Ｃ間で測定を実施し、測定劣化値を算出する（ステップＳ４０７、Ｓ４０８）。
【００９４】
（３）測定端末選定／劣化値分析部１４は、ここでの測定によって得られた測定劣化値、ここでの測定パス内の各ノードのリンク劣化値／リンク劣化補正値、２つの子ノードペア情報に設定されているパス劣化値から、選択ノードと子ノードペア情報内の各ノードとの間の劣化値を算出し、算出結果を各子ノードのノード情報内のリンク劣化値に設定する（ステップＳ４０９、Ｓ４１０）。
選択ノードと子ノードペア情報内の各ノードとの間の劣化値算出手順の詳細を以下に示す。なお、算出方法は２つの子ノードペア情報に重複するノードの存在有無によって大きな違いはなく、方程式数が異なるだけなので、重複ノードがない場合にのみ記載する。
【００９５】
（手順１）測定パス内に属するリンク劣化補正値を測定劣化値から減算する。
ノードＮ［１０］（端末Ａ）−ノードＮ［１２］（端末Ｂ）間の測定劣化値が「６０」であり、ノードＮ［１０］のノード情報には、リンク劣化値「０」、リンク劣化補正値「３０」が設定され、ノードＮ［１２］のノード情報には、リンク劣化値「２０」、リンク劣化補正値「０」が設定されている状態であったとする。
【００９６】
このとき、ノードＮ［１０］−ノードＮ［１２］間の劣化値は「１０」（＝６０（測定劣化値）−３０（ノードＮ［１０］のリンク劣化補正値）−２０（ノードＮ［１２］のリンク劣化値）となる。これは、ノードＮ［２］−ノードＮ［４］間の劣化値を意味している。
また、ノードＮ［１０］（端末Ａ）−ノードＮ［１３］（端末Ｃ）間のパスについても同様の処理を行い、ノードＮ［２］−ノードＮ［５］間の劣化値を算出する。ここでは、算出結果が「２０」であったとする。
【００９７】
図１８（ｃ）に示すように、ノードＮ［１］−ノードＮ［２］間の劣化値を「Ｌ１」、ノードＮ［１］−ノードＮ［３］間の劣化値を「Ｌ２」、ノードＮ［１］−ノードＮ［４］間の劣化値を「Ｌ３」、ノードＮ［１］−ノードＮ［５］間の劣化値を「Ｌ４」とすると、上記の計算により、以下が成り立つことを意味する。
【００９８】
Ｌ１＋Ｌ３＝１０ …ノードＮ［２］−ノードＮ［４］間の劣化値（式１）
Ｌ１＋Ｌ４＝２０ …ノードＮ［２］−ノードＮ［５］間の劣化値（式２）
【００９９】
（手順２）２つの子ノードペア情報内のパス劣化値から、ノードペアそれぞれに付随する測定端末Ｔ間のパス内に属するノードのリンク劣化値を減算する。
ノードＮ［２］とノードＮ［３］の子ノードペア情報にリンク劣化値「３０」が設定されており、ノードＮ［１０］のノード情報にリンク劣化値「０」、リンク劣化補正値「３０」が設定され、ノードＮ［１１］のノード情報にリンク劣化値「１０」、リンク劣化補正値「ＮＵＬＬ」が設定されていたとする。
このとき、３０（ノードＮ［２］とノードＮ［３］の子ノードペア情報に設定されているパス劣化値）−０（ノードＮ［１０］のパス劣化値）−１０（ノードＮ［１１］のパス劣化値）＝「２０」は、ノードＮ［２］−ノードＮ［３］間の劣化値を意味する。
同様にしてノードＮ［４］−ノードＮ［５］間の劣化値を算出し、算出結果が「１０」であったとする。このとき、以下が成立する。
【０１００】
Ｌ１＋Ｌ２＝２０ …ノードＮ［２］−ノードＮ［３］間の劣化値（式３）
Ｌ３＋Ｌ４＝１０ …ノードＮ［４］−ノードＮ［５］間の劣化値（式４）
【０１０１】
得られた４つの（式１）〜（式４）からなる方程式を解くことで、以下を得る。
【０１０２】
Ｌ１＝１０、Ｌ２＝１０、Ｌ３＝０、Ｌ４＝１０
【０１０３】
得られた結果を各ノードのリンク劣化値に設定する。つまり、ノードＮ［２］のノード情報にリンク劣化値「１０（Ｌ１）」を、ノードＮ［３］のノード情報にリンク劣化値「１０（Ｌ２）」を、ノードＮ［４］のノード情報にリンク劣化値に「０（Ｌ３）」を、ノードＮ［５］のリンク劣化値に「１０（Ｌ４）」を書き込む。
【０１０４】
［２．２．６ 劣化区間候補抽出処理］
［２．２．６．１ 処理フロー］
図９は、劣化パス検出装置１における劣化区間候補抽出処理の処理フローを示す図である。
劣化区間候補抽出処理では、網羅率１００％による測定パスの中から、パス劣化値が最大となる２つのパスを抽出し、その中から選択ノードと測定端末Ｔ間の劣化値が最大となる区間を抽出する処理である。ただし、網羅率１００％の測定によって劣化パスとして検出済みのパスのパス劣化値は、検出時に「０」に補正処理されていることから、劣化と判定されていない範囲でパス劣化値が最も大きい２つのパスが対象となる。
パス劣化値が最大となる２つのパスを抽出する理由としては、そのパス内に選択ノードと測定端末Ｔ間の劣化値が最大となる区間が含まれている可能性が最も高いことから、そこから分析を始めているためである。劣化区間候補を抽出する過程において劣化パスが検出された場合、前述の測定劣化パス処置のフローチャートの説明と同様に、パス劣化値やリンク劣化値の「０」への補正処理、および部分木の再構築処理を実施する。
【０１０５】
同図において、まず、測定端末選定／劣化値分析部１４は、選択ノードのノード情報に設定されている全ての子ノードペア情報のパス劣化値を読み出し、読み出したパス劣化値の最大値が「０」であるか否かを判断する（ステップＳ５０１）。最大値が「０」である場合（ステップＳ５０１：ＹＥＳ）、測定端末選定／劣化値分析部１４は、選択ノードの全ての子ノードの中から、リンク劣化値が設定されている子ノード情報を特定し、この特定した子ノード情報に設定されているノードＩＤからランダムに１つを選択すると（ステップＳ５０２）、この選択した子ノードのノードＩＤを選択ノードのノード情報の部分木構成ノードに設定し、処理を終了する（ステップＳ５１３）。
【０１０６】
ステップＳ５０１において最大値が「０」ではないと判断した場合（ステップＳ５０１：ＮＯ）、測定端末選定／劣化値分析部１４は、選択ノードのノード情報に設定されている全ての子ノードペア情報の中から、パス劣化値が最も大きい２つの子ノードペア情報を選択する（ステップＳ５０３）。測定端末選定／劣化値分析部１４は、選択した子ノードペア情報について、図８に示すリンク劣化値算出処理を行い、選択した子ノードペア情報に設定されているノードＩＤにより特定される子ノードと、選択ノードとの間のリンク劣化値を算出する（ステップＳ５０４）。
【０１０７】
測定端末選定／劣化値分析部１４は、ステップＳ５０３において選択した子ノードペア情報に設定されているノードＩＤを読み出し、読み出したノードＩＤにより特定される子ノードに付随する測定端末Ｔを特定すると、この特定した測定端末Ｔ全ての組み合わせのパスについて劣化値を算出する（ステップＳ５０５）。選択ノードからある子ノードに付随する測定端末Ｔまでのパスの劣化値は、当該子ノードのノード情報に設定されているリンク劣化値と、リンク合計劣化値との和となる。従って、選択ノードのノード情報に設定されている各子ノードのノード情報から、選択ノードと各ノードに付随する測定端末Ｔとのパスの劣化値が算出できる。測定端末Ｔの組み合わせに応じて、その算出した選択ノード−測定端末Ｔ間のパスの劣化値を加算し、測定端末Ｔ全ての組み合わせのパスについての劣化値を算出することができる。測定端末選定／劣化値分析部１４は、ステップＳ５０５において算出した劣化値の中に、劣化閾値を超えるものがあるか否かを判断する（ステップＳ５０６）。
【０１０８】
劣化閾値を超えるものがないと判断した場合（ステップＳ５０６：ＮＯ）、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードを選択する（ステップＳ５１２）。具体的には、選択ノードのノード情報内に設定されている子ノードリストから子ノードのノード情報を読み出し、この子ノードのノード情報の中から、リンク劣化値とリンク合計劣化値の和が最大のノード情報を選択する。部分木ネットワーク構築部１１は、ステップＳ５１２において選択した子ノードのノード情報内のノードＩＤを選択ノードのノード情報の部分木構成ノードに設定し、処理を終了すると呼び出し元に戻る（ステップＳ５１３）。
【０１０９】
ステップＳ５０６において劣化閾値を超えるものがあると判断した場合（ステップＳ５０６：ＹＥＳ）、測定端末選定／劣化値分析部１４は、その劣化閾値を超えた測定端末Ｔ間のパスを劣化パスとして検出し（ステップＳ５０７）、検出した劣化パスに属する選択ノードの子ノード、つまり、ステップＳ５０５においてこの測定端末Ｔを付随する測定端末Ｔとして特定した子ノードを抽出する（ステップＳ５０８）。
【０１１０】
測定端末選定／劣化値分析部１４は、選択ノードが第一階層のノードであると判断した場合（ステップＳ５０８−１：ＹＥＳ）、抽出した子ノードのノード情報に現在設定されているリンク劣化値をリンク劣化補正値に設定した後、リンク劣化値に「０」を設定する（ステップＳ５１４）。測定端末選定／劣化値分析部１４は、選択ノードのノード情報に対応付けられている子ノードペア情報から、ステップＳ５０８において抽出した子ノードのノードＩＤが設定されている子ノードペア情報を抽出し、抽出した子ノードペア情報の現在のパス劣化値を、ステップＳ５１４において選択ノードのノード情報に設定したリンク補正値を減算した値に更新する（ステップＳ５１５）。その後、選択ノードについて、再帰的に劣化区間候補抽出処理を実行する（ステップＳ５１６）。
【０１１１】
一方、測定端末選定／劣化値分析部１４は、選択ノードが第一階層のノードではないと判断した場合（ステップＳ５０８−１：ＮＯ）、ステップＳ５０８において抽出した子ノードを入力とし、後述する図１３に示す部分木データ再構築処理を行なう（ステップＳ５０９）。部分木再構築処理では、ルートノードとリーフノード間の劣化値が、劣化パスに次いで２番目に高い区間が部分木の構成要素となるように、部分木を再構築する。測定端末選定／劣化値分析部１４は、選択ノードのノード情報に対応付けられている子ノードペア情報の中から、ステップＳ５０８において抽出した子ノードのノードＩＤが含まれる子ノードペア情報を選択する（ステップＳ５１０）。測定端末選定／劣化値分析部１４は、ステップＳ５０９の再構築処理後の各ノードに付随する測定端末Ｔ間のパスに含まれるノードのリンク劣化値の和を算出し、算出結果を子ノードペア情報のパス劣化値に設定する（ステップＳ５１１）。その後、選択ノードについて、再帰的に劣化区間候補抽出処理を実行する（ステップＳ５１６）。
【０１１２】
［２．２．６．２ 具体例による処理の説明］
（１）選択ノードに設定されている子ノードペア情報内のパス劣化値の中から最も大きい値の２つの子ノードペア情報を抽出する（ステップＳ５０３）。
抽出した子ノードペア情報を利用して構成できる測定端末Ｔ間のパスの一部が、既に他のパスで劣化と判定されたパスの一部と重複する場合、重複箇所の劣化値は補正済みである。そのため、パス劣化値が最大となるパスに含まれる選択ノード−測定端末Ｔ間の区間が最も劣化パスの一部になる可能性が高いことから、そのような子ノードペア情報を抽出する。
【０１１３】
（２）（１）において抽出した２つの子ノードペア情報から、そこに含まれる選択ノードの子ノードを４つ特定し、この特定した４つの各ノードと選択ノードと間の劣化値をそれぞれ算出する。そしてこの算出した劣化値から、４つの子ノードに付随する測定端末Ｔ間が劣化パスとなるか否かを判定する（ステップＳ５０４〜Ｓ５０６）。
図１９に示すように、図１８と同様の部分木の場合、測定端末Ｔ［１０］−測定端末Ｔ［１１］間、及び、測定端末Ｔ［１２］−測定端末Ｔ［１３］間は、網羅率１００％の測定により測定実施済みであり、測定端末Ｔ［１０］と測定端末Ｔ［１２］間、及び、測定端末Ｔ［１０］と測定端末Ｔ［１３］間はリンク劣化値算出処理により測定実施済みである。これにより、部分木内の各ノード間の劣化値がわかることから、測定していない測定端末［１１］−測定端末［１２］間、および、測定端末［１１］−測定端末［１３］間の劣化値を計算で求めることが出来る。つまり、測定端末Ｔ［１１］−測定端末Ｔ［１２］間の劣化値は、ノードＮ［１０］、［２］、［４］、［１２］のノード情報に設定されているリンク劣化値の合計であり、測定端末Ｔ［１１］−測定端末Ｔ［１３］間の劣化値は、ノードＮ［１０］、［２］、［５］、［１３］のノード情報に設定されているリンク劣化値の合計であり、
ステップＳ５０５においては、その未測定の測定端末間の劣化値を算出することで、４つのノードＮ［１０］、［１１］、［１２］、［１３］間の全てにおいて劣化パスとなるかどうか判定を行う。
【０１１４】
（３）どの測定端末Ｔ間の劣化値も、劣化閾値を超えない（劣化パスではない）場合、選択ノードと測定端末Ｔ間の劣化値が最大となる区間を抽出し、その区間に属する選択ノードの子ノードを選択ノードのノード情報の部分木構成ノードとして登録する（ステップＳ５１２、Ｓ５１３）。
図１９において、ノードＮ［１］−測定端末［１１］間の劣化値（ノードＮ［３］の劣化値とノードＮ［３］のリンク合計劣化値の和）が、他の３つの区間より大きい場合、選択ノードＮ［１］の子ノードであるノードＮ［３］を、選択ノードＮ［１］のノード情報の部分木構成ノードとして登録する。
【０１１５】
（４）４つの測定端末Ｔ間の全てにおいて劣化パスとなるかどうか判定を行い、劣化パスが検出できた場合、測定劣化パス処理のときと同様に、部分木データ再構築処理を実施し、抽出済みの子ノードペア情報内のパス劣化値を更新する（ステップＳ５０７〜Ｓ５１１、Ｓ５１４、Ｓ５１５）。
【０１１６】
（５）パス劣化値更新後、再度劣化区間候補抽出処理を実施する（ステップＳ５１６）。
劣化パスが検出されると、各子ノードペア情報のパス劣化値は変更される場合がある。図２０は、パス劣化値が変更される例を示す図である。図２０（ａ）に示す部分木において、測定端末Ｔ［Ａ］−測定端末Ｔ［Ａ’］間のパス劣化値が６０、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間のパス劣化値が５０、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間のパス劣化値が４０、測定端末Ｔ［Ｎ］−測定端末Ｔ［Ｎ’］間のパス劣化値が３０であったとする。この場合、図２０（ｂ）に示すように、劣化区間候補処理対象パスは、ノードＮ［Ａ］−ノードＮ［Ａ’］間のパスと、ノードＮ［Ｂ］−ノードＮ［Ｂ’］間のパスとなる。そして、選択ノード−ノードＮ［Ａ］、ノードＮ［Ａ’］、ノードＮ［Ｂ］、ノードＮ［Ｂ’］それぞれとの間のパス劣化値が、「４０」、「２０」、「４０」、「１０」であり、ノードＮ［Ａ］−ノードＮ［Ｂ］間が劣化パスとして検出されたとする。
【０１１７】
このとき、選択ノード−測定端末Ｔ［Ａ］間、および選択ノード−測定端末Ｔ［Ｂ］間は、劣化パスとして検出済みであり、リンク劣化値は「０」に補正される。よって、図２０（ｃ）に示すように、測定端末Ｔ［Ａ］−測定端末Ｔ［Ａ’］間のパス劣化値は、選択ノード−ノードＮ［Ａ］間のパス劣化値「４０」を減算した「２０」、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間のパス劣化値は、選択ノード−ノードＮ［Ｂ］間のパス劣化値「４０」を減算した「１０」となる。
各部分木において見つけたいものは、選択ノードと測定端末Ｔ間の劣化値が最大となる区間であり、図２０に示す場合、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間や、測定端末Ｔ［Ｎ］−測定端末Ｔ［Ｎ’］間の方が、劣化値が最大となる区間が含まれている可能性が高くなる。そのため、再度劣化区間候補抽出処理を実施している。
【０１１８】
［２．２．７ 折り返し劣化分析処理］
［２．２．７．１ 処理フロー］
図１０及び図１１は、劣化パス検出装置１における折り返し劣化分析処理の処理フローを示す図であり、図４のステップＳ７０の詳細な処理を示している。
折り返し劣化分析処理では、劣化区間候補内の測定端末Ｔと、劣化区間候補の抽出に利用した２つのパス以外のパス内における測定端末Ｔ間の折り返しパスとが劣化パスとして検出されるかどうか分析する。
そこで、劣化区間候補の劣化値と、他のパスのパス劣化値とを比較することによって、可能性のある箇所だけ測定を実施し、劣化パスの有無の分析を行っている。劣化パスが検出された場合は、前述のとおり、パス劣化値やリンク劣化値の補正処理、および、部分木の再構築処理を実施する。
【０１１９】
図１０において、測定端末選定／劣化値分析部１４は、選択ノードのノード情報に設定されている部分木構成ノードからノードＩＤを読み出し、読み出したノードＩＤにより特定される子ノードのノード情報に設定されているリンク劣化値とリンク合計劣化値の和を算出する（ステップＳ６０１）。測定端末選定／劣化値分析部１４は、選択ノードのノード情報の子ノードペアリストに設定されている子ノードペア情報の中から、リンク劣化値が設定されている子ノードのノードＩＤが設定されておらず、かつ、各子ノードペア情報に設定されているパス劣化値とステップＳ６０１において算出した和との合計が劣化閾値を超える子ノードペア情報を抽出する（ステップＳ６０２）。ステップＳ６０２において抽出できた子ノードペア情報がない場合（ステップＳ６０２：ＮＯ）、処理を終了する。
【０１２０】
ステップＳ６０２において抽出できた子ノードペア情報がある場合、測定端末選定／劣化値分析部１４は、抽出した子ノードペア情報に設定されているパス劣化値が大きい順に選択し、以下の処理を行なう（ステップＳ６０４）。以下、本処理フローの説明ではこのステップＳ６０４で選択した子ノードペア情報を選択子ノードペア情報と記載する。
【０１２１】
測定端末選定／劣化値分析部１４は、選択子ノードペア情報に設定されている２つの子ノードのノードＩＤのうち１つをランダムに選択し、選択したノードＩＤの子ノードに付随する測定端末Ｔを特定する（ステップＳ６０５）。本処理フローの説明では、特定した測定端末Ｔを「測定端末Ｔ１」、特定されなかったほうの測定端末Ｔを「測定端末Ｔ１’」と記載する。続いて、測定端末選定／劣化値分析部１４は、選択ノードのノード情報の部分木構成ノードに設定されているノードＩＤを読み出し、このノードＩＤにより特定される子ノードに付随する測定端末Ｔ（本処理フローの説明では、「測定端末Ｔ２」と記載）を特定する（ステップＳ６０６）。
【０１２２】
測定指示実行部１２は、ステップＳ６０５おいて特定された測定端末Ｔ１と、ステップＳ６０６において特定された測定端末Ｔ２との間で測定を行なう。測定指示実行部１２は、ネットワークトポロジ情報から測定端末Ｔ１及びＴ２のアドレス情報を読み出すと、測定端末Ｔ１及びＴ２に対して測定指示を出力する。劣化パス検出装置１の測定結果受信／劣化値算出部１３は、測定端末Ｔ１及びＴ２から通信パケットの伝送情報を測定結果として受信し、測定劣化値を得る（ステップＳ６０７）。
【０１２３】
測定端末選定／劣化値分析部１４は、ステップＳ６０７において得られた測定劣化値に基づいて、選択ノード−測定端末Ｔ１間と、選択ノード−測定端末Ｔ１’間の劣化値をそれぞれ算出する（ステップＳ６０８）。
選択ノード−測定端末Ｔ２間の劣化値は、選択ノードから測定端末Ｔ２に至る経路上のノードのノード情報に設定されている劣化値を合計することによって算出することができる。よって、ステップＳ６０７の測定劣化値から選択ノード−測定端末Ｔ２間の劣化値を減算することによって、選択ノード−測定端末Ｔ１間の劣化値が算出できる。
また、測定端末Ｔ１−測定端末Ｔ１’間の劣化値は、選択した子ノードペア情報のパス劣化値から取得することができる。つまり、測定端末Ｔ１−測定端末Ｔ１’間のパス劣化値から、算出した選択ノード−測定端末Ｔ１間の劣化値を減算することで選択ノード−測定端末Ｔ１’間の劣化値が算出できる。
【０１２４】
測定端末選定／劣化値分析部１４は、ステップＳ６０８において算出された劣化値に基づいて、選択ノードと、選択子ノードペア情報に設定されている各子ノードとの間の劣化値を算出し、選択子ノードペア情報により示される子ノードのノード情報に、ステップＳ６０８において算出されたリンク劣化値を設定する（ステップＳ６０９）。
選択ノードと測定端末Ｔ１が付随している子ノードとの間の劣化値は、ステップＳ６０８において算出した選択ノード−測定端末Ｔ１間の劣化値から、測定端末Ｔ１が付随している子ノードのノード情報に設定されているリンク合計劣化値を減算して得られる。
同様に、選択ノードと測定端末Ｔ１’が付随している子ノードとの間の劣化値は、ステップＳ６０８において算出した選択ノード−測定端末Ｔ１’間の劣化値から、測定端末Ｔ１’が付随している子ノードのノード情報に設定されているリンク合計劣化値を減算して得られる。
【０１２５】
続いて測定端末選定／劣化値分析部１４は、選択ノードの部分木構成ノードに付随する測定端末Ｔから、選択子ノードペア情報により示される子ノードそれぞれに付随する全ての測定端末Ｔの組み合わせについて、測定端末Ｔ間の劣化値を算出する（ステップＳ６１０）。
図１１において測定端末選定／劣化値分析部１４は、ステップＳ６１０において算出した劣化値の中に劣化閾値を超えるものが存在するか否かを判断する（ステップＳ６１１）。劣化閾値を超える算出結果が存在しない場合（ステップＳ６１１：ＮＯ）、ステップＳ６０４に戻り、次にパス劣化値が大きい子ノードペア情報を選択して処理を行う。
【０１２６】
一方、劣化閾値を超える算出結果が存在した場合（ステップＳ６１１：ＹＥＳ）、測定端末選定／劣化値分析部１４は、該当パスを劣化パスとして検出し（ステップＳ６１２）、この劣化パスとして検出したパスに属する選択ノードの子ノードを抽出する（ステップＳ６１３）。
【０１２７】
選択ノードが第一階層のノードであると判断した場合（ステップＳ６１４：ＹＥＳ）、測定端末選定／劣化値分析部１４は、抽出した子ノードのノード情報に現在設定されているリンク劣化値をリンク劣化補正値に設定した後、リンク劣化値に「０」を設定する（ステップＳ６１８）。測定端末選定／劣化値分析部１４は、選択ノードのノード情報にノードペアリストとして設定されている子ノードペア情報から、ステップＳ６１３において抽出した子ノードのノードＩＤが設定されている子ノードペア情報を抽出し、抽出した子ノードペア情報の現在のパス劣化値を、ステップＳ６１８において設定したリンク補正値を減算した値に更新する（ステップＳ６１９）。その後、選択ノードについて、劣化区間候補抽出処理を実行した後（ステップＳ６２０）、折り返し劣化分析処理を行なう（ステップＳ６２１）。
【０１２８】
選択ノードが第一階層のノードではないと判断した場合（ステップＳ６１４：ＮＯ）、部分木ネットワーク構築部１１は、抽出した子ノードについて部分木データ再構築処理を行なう（ステップＳ６１５）。そして、測定端末選定／劣化値分析部１４は、選択ノードの子ノードペア情報から、ステップＳ６１３において抽出した子ノードが含まれる子ノードペア情報を抽出すると（ステップＳ６１６）、再構築処理後の各子ノードに付随する測定端末Ｔ間のパスに含まれるノードのリンク劣化値の和を算出し、算出結果を子ノードペア情報のパス劣化値に設定する（ステップＳ６１７）。その後、選択ノードについて、劣化区間候補抽出処理を実行した後（ステップＳ６２０）、折り返し劣化分析処理を行なう（ステップＳ６２１）。
【０１２９】
［２．２．７．２ 具体例による処理の説明］
折り返し劣化分析処理では、部分木内測定や劣化区間候補抽出処理において検出できなかった、部分木内での折り返し劣化パスの検出を行う。
【０１３０】
（１）劣化区間候補抽出処理によって抽出された選択ノードと測定端末Ｔとの間のパスと、他の選択ノードと測定端末Ｔとの間のパスを結ぶことで、劣化パスが検出できるか分析する（ステップＳ６０１、Ｓ６０２）。
これを行うために、抽出された選択ノードと測定端末Ｔとの間の劣化値と、リンク劣化値が設定されていないノードが属する子ノードペア情報のパス劣化値の和を算出し、算出結果が劣化閾値を超えるノードペアがあるかについて分析を行う。
既にリンク劣化値が設定されている選択ノードと測定端末Ｔとの間の区間同士を結ぶ、測定端末Ｔ間のパスは、既に劣化パスとなるかどうかの判定が実施済みであるため、リンク劣化値が設定されているノードが属するノードペアを除外している。
また、抽出された選択ノードと測定端末Ｔ間のパスと子ノードペア情報のパス劣化値の和が劣化閾値を超えない場合、そのノードペアに付随する測定端末Ｔと抽出された劣化区間候補の測定端末Ｔ間の劣化値は、劣化閾値を超えることはないので、除外している。
【０１３１】
図２１に示す部分木の場合、劣化区間候補は、パス劣化値が「４０」の選択ノード−測定端末Ｔ［Ａ］間の区間であり、測定端末Ｔ［Ａ］−測定端末Ｔ［Ａ’］間のパス劣化値が「６０」、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間のパス劣化値が「４０」、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間のパス劣化値が「２０」、測定端末Ｔ［Ｎ］−測定端末Ｔ［Ｎ’］間のパス劣化値が「１０」であったとする。
【０１３２】
劣化閾値を「７０」としたとき、劣化区間候補の劣化値「４０」とパス劣化値の和が劣化閾値を超えるのは測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間となる。
測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間を考えた場合、その劣化値の分布としては、一方の選択ノード−測定端末Ｔ間の劣化値が「３０」以上である状態Ｂ１や、両方の選択ノード−測定端末Ｔ間の劣化値が「３０」未満である状態Ｂ２が考えられる。
測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間の劣化値の分布が状態Ｂ１のとき、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ’］間のパスが劣化閾値以上となり、劣化パスとなる可能性がある。従って、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間については分析対象となる。
【０１３３】
一方、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間のパスは、選択ノード−測定端末Ｔ間の劣化値が最大となる状態Ｃを考えたとしても、劣化区間候補と結ぶパスが劣化閾値を超えることはないので、分析対象から除外している。測定端末Ｔ［Ｎ］−測定端末Ｔ［Ｎ’］も同様に分析対象から除外している。
【０１３４】
（２）劣化区間候補の劣化値とパス劣化値の和が劣化閾値を超えるパスが抽出できた場合、劣化区間候補の測定端末Ｔと抽出したパスに属する一方の測定端末Ｔ間で測定を行い、抽出パスの選択ノード−測定端末Ｔ間の劣化値を算出する。また、算出結果から抽出パス内の選択ノードとその子ノード間の劣化値（子ノードのリンク劣化値）を算出し、子ノードのノード情報に設定する（ステップＳ６０５〜Ｓ６０９）。
【０１３５】
図２２は、図２１における分析対象を模式的に表した図である。同図に示すように、劣化区間候補抽出処理に利用したパス、すなわち、測定端末Ｔ［Ａ］−測定端末Ｔ［Ａ’］間は、そのパス内の各リンクの劣化値（リンク劣化値）が既知である。また、第一階層における処理により、ノードＮ［４］−測定端末Ｔ［Ｂ］間やノードＮ［５］−測定端末Ｔ［Ｂ’］間のリンク劣化値も既知である。
そこで、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ］’間で測定を行うことにより、ノードＮ［１］−ノードＮ［５］間の劣化値を算出し、ノードＮ［５］のリンク劣化値にその算出結果を設定する。
また、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間は部分木内測定において測定を実施しており、パス劣化値が既知であることから、ノードＮ［１］−ノードＮ［５］間の劣化値が算出できれば、ノードＮ［１］−ノードＮ［４］間の劣化値も算出されるため、その算出結果をノードＮ［４］のリンク劣化値に設定する。
【０１３６】
（３）以上の計算から、ノードＮ［１］（選択ノード）−ノードＮ［Ｂ］（測定端末Ｔ［Ｂ］）間、及び、ノードＮ［１］−ノードＮ［Ｂ’］（測定端末Ｔ［Ｂ］）間の各劣化値が算出できるため、図２１に示す状態Ｂ１または状態Ｂ２のいずれに該当するかを判定できる。状態Ｂ１の場合、劣化閾値を超える測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ’］間のパスを劣化パスとして検出する。また、劣化区間候補抽出処理と同様に、部分木データ再構築処理を実施し、抽出済みの子ノードペア情報内のパス劣化値を更新する（ステップＳ６１０〜Ｓ６１９）。
【０１３７】
（４）劣化区間候補抽出処理における説明と同様に、他のパス内の選択ノード−測定端末Ｔ間の劣化値が最大となる場合があるので、再度、劣化区間候補抽出処理を実施する（ステップＳ６２０）。
【０１３８】
［２．２．８ 最大劣化区間抽出処理］
［２．２．８．１ 処理フロー］
図１２は、劣化パス検出装置１における最大劣化区間抽出処理の処理フローを示す図である。
最大劣化区間抽出処理では、部分木において、選択ノードと測定端末Ｔ間の劣化値が最大となる区間を決定する。ここまでの処理において、部分木内に存在する劣化パスは全て検出済みであり、また、検出された劣化パスに含まれるリンクの劣化値は「０」に補正済みであるため、部分木内の選択ノードと測定端末Ｔ間の劣化値が最大となる区間が、真の最大劣化区間となる。最大劣化区間の決定は、劣化区間候補の劣化値と他のパスのパス劣化値を比較し、劣化区間候補より大きい劣化値となりうるパスが存在する場合に限り測定によって分析を行い、真の最大劣化区間を抽出する。
【０１３９】
まず、測定端末選定／劣化値分析部１４は、選択ノードのノード情報に設定されている部分木構成ノードから子ノードのノードＩＤを読み出し、読み出したノードＩＤにより特定される子ノードのノード情報からリンク劣化値を読み出すと、この読み出したリンク劣化値と、選択ノードのノード情報から読み出したリンク合計劣化値との和を算出し、これを基準劣化値とする（ステップＳ７０１）。測定端末選定／劣化値分析部１４は、選択ノードのノード情報に対応づけられている子ノードペア情報の中から、リンク劣化値が設定されている子ノードのノードＩＤが設定されておらず、かつ、各子ノードペア情報に設定さている劣化値とステップＳ７０１において算出した基準劣化値を超える子ノードペア情報を抽出する（ステップＳ７０２）。ステップＳ７０２において抽出できた子ノードペア情報がない場合（ステップＳ７０２：ＮＯ）、選択ノードのノード情報に、合計劣化値として基準劣化値を設定する（ステップＳ７１４）。
【０１４０】
ステップＳ７０２において抽出できた子ノードペア情報がある場合、抽出した子ノードペア情報に設定されているパス劣化値が大きい順に選択し、以下の処理を行なう（ステップＳ７０４）。以下、本処理フローの説明ではこのステップＳ７０４で選択した子ノードペア情報を選択子ノードペア情報と記載する。
【０１４１】
測定端末選定／劣化値分析部１４は、選択子ノードペア情報に設定されている２つの子ノードのノードＩＤのうち１つをランダムに選択し、選択したノードＩＤの子ノードに付随する測定端末Ｔを特定する（ステップＳ７０５）。本処理フローの説明では、特定した測定端末Ｔを「測定端末Ｔ１」、特定されなかったほうの測定端末Ｔを「測定端末Ｔ１’」と記載する。続いて、測定端末選定／劣化値分析部１４は、選択ノードのノード情報の部分木構成ノードに設定されているノードＩＤを読み出し、このノードＩＤにより特定される子ノードに付随する測定端末Ｔ（本処理フローの説明では、「測定端末Ｔ２」と記載）を特定する（ステップＳ７０６）。
【０１４２】
測定指示実行部１２は、ステップＳ７０５において特定された測定端末Ｔ１と、ステップＳ７０６において特定された測定端末Ｔ２との間の測定を行なう。測定指示実行部１２は、これらの測定端末Ｔ１及びＴ２に対して測定指示を出力し、測定結果受信／劣化値算出部１３は、測定指示を出力した測定端末Ｔ１及びＴ２から受信した測定結果から測定劣化値を得る（ステップＳ７０７）。
【０１４３】
測定端末選定／劣化値分析部１４は、ステップＳ７０７において得られた測定劣化値に基づいて、選択ノードと−測定端末Ｔ１間と、選択ノード−測定端末Ｔ１’間の劣化値（以下、比較劣化値）をそれぞれ算出する（ステップＳ７０８）。これは、図１０のステップＳ６０８と同様の処理により算出することができる。
さらに、測定端末選定／劣化値分析部１４は、ステップＳ７０８において算出された劣化値に基づいて、選択ノードと、選択子ノードペア情報に設定されている各子ノードとの間の劣化値を算出し、選択子ノードペア情報により示される子ノードのノード情報に、ステップＳ７０８において算出されたリンク劣化値を設定する（ステップＳ７０９）。これは、図１０のステップＳ６０９と同様の処理により算出することができる。
【０１４４】
続いて測定端末選定／劣化値分析部１４は、基準劣化値を超える比較劣化値が存在するか否かを判断する（ステップＳ７１０）。基準劣化値を超える比較劣化値が存在すると判断した場合（ステップＳ７１０：ＹＥＳ）、測定端末選定／劣化値分析部１４は、基準劣化値を超えるパスに属する選択ノードの子ノードを、選択ノードのノード情報に部分木構成ノードとして設定した後、最大劣化区間抽出処理を行い（ステップＳ７１１）、処理を終了して呼び出し元に戻る。
【０１４５】
一方、基準劣化値を超える比較劣化値が存在しないと判断した場合（ステップＳ７１０：ＮＯ）、ステップＳ７０４に戻り、ステップＳ７０２において抽出した子ノードペア情報から次にパス劣化値が大きい子ノードペア情報を選択して処理を行い、ステップＳ７０２において抽出した子ノードペア情報について全て処理を行なうと、選択ノードのノード情報に、合計劣化値として基準劣化値を設定する（ステップＳ７１４）。測定端末選定／劣化値分析部１４は、処理を終了して呼び出し元に戻る。
【０１４６】
［２．２．８．２ 具体例による処理の説明］
最大劣化区間抽出処理では、部分木内の選択ノード−測定端末Ｔ間の劣化値が最大となる区間を決定する。
【０１４７】
（１）まず、劣化区間候補抽出処理によって抽出された選択ノードと測定端末Ｔ間の劣化値を超える劣化値を持つ、選択ノード−測定端末Ｔ間が存在するかどうか分析を行う（ステップＳ７０１、Ｓ７０２）。
これを行うために、抽出された選択ノードと測定端末Ｔ間の劣化値を超えるパス劣化値と、リンク劣化値が設定されていないノードとが設定されている子ノードペア情報のノードペアについて分析を行う。
既にリンク劣化値が設定されている選択ノードと測定端末Ｔ間の区間は、劣化区間候補抽出処理時に比較済みであるので、分析対象から除外している。
また、子ノードペア情報のパス劣化値が、抽出された選択ノードと測定端末Ｔ間の劣化値を超えない場合、そのノードペアに付随する測定端末Ｔと選択ノード間の劣化値は、抽出済みの劣化区間候補の劣化値を超えることはないので、除外している。
【０１４８】
図２３に示す部分木の場合、劣化区間候補は、パス劣化値が「２０」の選択ノード−測定端末Ｔ［Ａ］間の区間であり、測定端末Ｔ［Ａ］−測定端末Ｔ［Ａ’］間のパス劣化値が「３５」、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間のパス劣化値が「３０」、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間のパス劣化値が「１５」、測定端末Ｔ［Ｎ］−測定端末Ｔ［Ｎ’］間のパス劣化値が「１０」である。
このとき劣化区間候補の劣化値「２０」を超えるパス劣化値を持つパスは測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間となる。
【０１４９】
測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間を考えた場合、その劣化値の分布としては、選択ノードと一方の測定端末Ｔ（測定端末Ｔ［Ｂ’］）との間の劣化値が「２０」を超える状態Ｂ１や、選択ノードと両方の測定端末Ｔとの間の劣化値が「２０」未満である状態Ｂ２が考えられる。
測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間の劣化値の分布が状態Ｂ１の場合、選択ノード−測定端末Ｔ［Ｂ’］間のパスが劣化区間候補の劣化値を超えることなり、部分木内における選択ノード−測定端末Ｔ間の劣化値が最大となる可能性があるので、測定端末Ｔ［Ｂ］−測定端末Ｔ［Ｂ’］間については分析対象となる。
一方、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｃ’］間のパスは、選択ノード−測定端末Ｔ間の劣化値が最大となる状態Ｃを考えたとしても、選択ノード−測定端末Ｔ間の劣化値が劣化区間候補の劣化値を超えることはないので、分析対象から除外している。
【０１５０】
（２）劣化区間候補の劣化値を超えるパスが抽出できた場合、劣化区間候補の測定端末Ｔと抽出したパスに属する一方の測定端末Ｔ間で測定を行い、抽出パスの選択ノード−測定端末Ｔ間の劣化値を算出する。また、算出結果から抽出パス内の選択ノードとその子ノード間の劣化値（子ノードのリンク劣化値）を算出し、子ノードのノード情報に設定する（ステップＳ７０５〜Ｓ７０９）。
図２３の例の場合、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ］間、あるいは、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ’］間のいずれかで測定を行なう。なお、選択ノードの子ノードのリンク劣化値の算出方法は、折り返し劣化パス分析と同様である。
【０１５１】
（３）以上の計算から、抽出されたパスにおける選択ノード−測定端末Ｔ間の劣化値をそれぞれ算出し、図２３に示す状態Ｂ１または状態Ｂ２のいずれであるかを判定する（ステップＳ７１０）。
判定結果として状態Ｂ１に該当した場合、劣化区間候補を超える劣化値を持つ選択ノード−測定端末Ｔ［Ｂ’］間を新たな劣化区間候補とし、新たな劣化区間候補内の選択ノードの子ノードを、選択ノードの部分木構成ノードに登録する（ステップS７１１）。
また、新たな劣化区間候補と基準とし、部分木内における最大劣化区間抽出処理を実施する（ステップS７１２）。これにより、部分木内において真に劣化値が最大となる選択ノード−測定端末Ｔ間を見つける。
【０１５２】
（４）ステップＳ７１０による判定により、劣化区間候補以外に、真に劣化値が最大となる選択ノード−測定端末Ｔ間が存在しなかった場合、選択ノードのノード情報に設定されている部分木構成ノードのリンク劣化値と、リンク合計劣化値との和を、各ノード情報のリンク合計劣化値に設定する（ステップＳ７１４）。
これにより、リンク合計劣化値が設定されているノードは、そのノードから測定端末Ｔ間の劣化値が最大となる区間の抽出が完了していることを意味し、またその区間の劣化値（その区間に属するノードのリンク劣化値の合計値）がわかることとなる。
【０１５３】
［２．２．９ 部分木データ再構築処理］
［２．２．９．１ 処理フロー］
図１３は、劣化パス検出装置１による部分木データ再構築処理の処理フローを示す図である。部分木データ再構築処理では、劣化パスが検出された際、ルートノードとリーフノード間の劣化値が２番目に高い区間が、部分木の構成要素となるように、部分木を再構築する。
ルートノードとリーフノード間の劣化値が２番目に高い区間が、他の部分木における最大劣化区間と接続されることによって、劣化パスとなる可能性があり、そのようなパスの検出漏れ（False Negativeパスの存在）が無い様にするために本処理を行っている。
【０１５４】
図１３において、部分木ネットワーク構築部１１は、各抽出ノードから、当該抽出ノードそれぞれに付随する測定端末Ｔに至るまでのパスに属するノードのノード情報を読み出す（ステップＳ８０１）。測定端末選定／劣化値分析部１４は、ステップＳ８０１において特定した測定端末Ｔのノード情報に対し、現在設定されているリンク劣化値をリンク劣化補正値に設定した後、リンク劣化値に「０」を設定する（ステップＳ８０２）。
【０１５５】
部分木ネットワーク構築部１１は、特定した測定端末Ｔの親ノードのノード情報に設定されている子ノードペア情報を読み出し、読み出した子ノードペア情報の現在のパス劣化値を、ステップＳ８０２において測定端末Ｔのノード情報に設定したリンク補正値を減算した値に更新する（ステップＳ８０３）。
【０１５６】
部分木ネットワーク構築部１１は、ステップＳ８０１において読み出したノード情報に対応するノードについて、第一階層から順に処理対象の層として選択し、ステップＳ８０５以降の処理を行う。
部分木ネットワーク構築部１１は、処理対象の層に含まれるノードのうち、本処理フローにおいて未選択のノードについて以下のステップＳ８０６以降の処理を行う。
【０１５７】
部分木ネットワーク構築部１１は、処理対象の層に含まれる未選択のノードを選択し（ステップＳ８０６）、この選択したノードのノード情報に対し、現在設定されているリンク劣化値をリンク劣化補正値に設定した後、リンク劣化値に「０」を設定する（ステップＳ８０７）。
【０１５８】
選択ノードが第一階層である場合（ステップＳ８０８：ＮＯ）、部分木ネットワーク構築部１１は、ステップＳ８０６において選択した選択ノードについて劣化区間候補抽出処理を行ない（ステップＳ８１０）、最大劣化区間抽出処理を行なう（ステップＳ８１１）。
一方、ステップＳ８０６において選択した選択ノードが第二階層以上である場合（ステップＳ８０８：ＹＥＳ）、部分木ネットワーク構築部１１は、この選択ノードのノード情報に設定されている部分木構成ノードからノードＩＤを読み出し、読み出したノードＩＤが設定されている子ノードペア情報を特定する。部分木ネットワーク構築部１１は、特定した子ノードペア情報に設定されている２つのノードのノードＩＤから、各ノードに付随する測定端末Ｔを特定し、この特定した測定端末Ｔ間のパス内に属するノードのノード情報からリンク劣化値を読み出す。部分木ネットワーク構築部１１は、この読み出したリンク劣化値の合計値を、特定した子ノードペア情報のパス劣化値として設定する（ステップＳ８０９）。その後、ステップＳ８０６において選択した選択ノードについて劣化区間候補抽出処理を行ない（ステップＳ８１０）、最大劣化区間抽出処理を行なう（ステップＳ８１１）。
【０１５９】
［２．２．９．２ 具体例による処理の説明］
部分木データ再構築処理は、選択ノードが第二階層以上に属する部分木において劣化パスが検出された際、劣化パス内の選択ノードの子ノードから、それぞれの子ノードに付随する測定端末Ｔ間の部分木データを再構築する。
【０１６０】
図２４は、部分木データ再構築処理の対象となる測定対象ネットワークの一部を示す。
同図において、ノードＮ［１］が選択ノードであり、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｉ］間のパスＰ１）が劣化パスとして検出された状態とする。また、点線で示した区間（例えばノードＮ［４］−測定端末Ｔ［Ａ］）は、各階層における処理において最大劣化区間として抽出された区間を示している。つまり、選択ノードがノードＮ［２］のときは、ノードＮ［２］−測定端末Ｔ［Ａ］間が最大劣化区間となったことを示している。
【０１６１】
図２５（ａ）に示すように、図２４に示したノードＮ［１］の子ノードとして、ノードＮ［２］やノードＮ［３］等が存在し、ノードＮ［１］−ノードＮ［２］間の劣化値（ノードＮ［２］のリンク劣化値）が「１０」、ノードＮ［１］−ノードＮ［３］間の劣化値（ノードＮ［３］のリンク劣化値）が「０」であったとする。このときのノードＮ［１］、ノードＮ［２］、ノードＮ［３］のノード情報を図２５（ｂ）に示す。
【０１６２】
また、図２６（ａ）に示すように、図２４に示したノードＮ［４］における子ノードペアとしては、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ］や、測定端末Ｔ［Ｃ］−測定端末Ｔ［Ｄ］等が存在し、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｂ］間のパス劣化値は「３０」、ノードＮ［４］−測定端末Ｔ［Ａ］間の劣化値（ノードＮ［Ａ］のリンク劣化値）が「２０」、ノードＮ［４］−測定端末Ｔ［Ｂ］間の劣化値（ノードＮ［Ｂ］のリンク劣化値）が「１０」、ノードＮ［４］−測定端末Ｔ［Ｃ］間の劣化値（ノードＮ［Ｃ］のリンク劣化値）が「１５」、ノードＮ［４］−測定端末Ｔ［Ｄ］間の劣化値（ノードＮ［Ｄ］のリンク劣化値）が「１０」、それ以外のパス劣化値は「０」であったとする。このときのノードＮ［４］、ノードＮ［Ａ］、ノードＮ［Ｂ］、ノードＮ［Ｃ］、ノードＮ［Ｄ］のノード情報、及び、ノードＮ［Ａ］とノードＮ［Ｂ］、ノードＮ［Ｃ］とノードＮ［Ｄ］の子ノードペア情報を図２６（ｂ）に示す。
【０１６３】
また、図２７（ａ）に示すように、図２４に示したノードＮ［５］における子ノードペアとしては、測定端末Ｔ［Ｅ］や測定端末Ｔ［Ｆ］等が存在し、そのパス劣化値は「３０」、ノードＮ［５］−測定端末Ｔ［Ｅ］間の劣化値（ノードＮ［Ｅ］のリンク劣化値）が「１０」、ノードＮ［５］−測定端末Ｔ［Ｆ］間の劣化値（ノードＮ［Ｆ］のリンク劣化値）が「２０」、それ以外のパス劣化値は「０」であったとする。このときのノードＮ［５］、ノードＮ［Ｅ］、ノードＮ［Ｆ］のノード情報、及び、ノードＮ［Ｅ］とノードＮ［Ｆ］の子ノードペア情報を図２７（ｂ）に示す。
【０１６４】
また、図２８（ａ）に示すように、図２４に示したノードＮ［６］における子ノードペアとしては、測定端末Ｔ［Ｇ］や測定端末Ｔ［Ｈ］等が存在し、そのパス劣化値は「１０」、ノードＮ［６］−測定端末Ｔ［Ｇ］間の劣化値（ノードＮ［Ｇ］のリンク劣化値）が「０」、ノードＮ［６］−測定端末Ｔ［Ｈ］間の劣化値（ノードＮ［Ｈ］のリンク劣化値）が「１０」、それ以外のパス劣化値は「０」であったとする。このときのノードＮ［６］、ノードＮ［Ｇ］、ノードＮ［Ｈ］のノード情報、及び、ノードＮ［Ｇ］とノードＮ［Ｈ］の子ノードペア情報を図２８（ｂ）に示す。
【０１６５】
また、図２９（ａ）に示すように、図２４に示したノードＮ［２］には、ノードＮ［４］、ノードＮ［５］、ノードＮ［６］の３つのノードが接続し、ノードＮ［２］−ノードＮ［４］間の劣化値（ノードＮ［４］のリンク劣化値）が「２０」、ノードＮ［２］−ノードＮ［５］間の劣化値（ノードＮ［５］のリンク劣化値）が「０」、ノードＮ［２］−ノードＮ［６］間の劣化値（ノードＮ［６］のリンク劣化値）が「５」であったとする。このときのノードＮ［２］、ノードＮ［４］、ノードＮ［５］、ノードＮ［６］のノード情報、及び、ノードＮ［４］とノードＮ［５］、ノードＮ［５］とノードＮ［６］の子ノードペア情報を図２９（ｂ）に示す。
【０１６６】
また、図３０に示すように、ノードＮ［３］と測定端末Ｔ［Ｉ］間の最大劣化区間の劣化値は「２０」であったとする。
【０１６７】
つまり、測定端末Ｔ［Ａ］−測定端末Ｔ［Ｉ］間のパスの劣化値は、ノードＮ［Ａ］−ノードＮ［４］間の劣化値「２０」、ノードＮ［４］−ノードＮ［２］間の劣化値「２０」、ノードＮ［２］−ノードＮ［１］間の劣化値「１０」、ノードＮ［１］−ノードＮ［３］間の劣化値「０」、ノードＮ［３］−測定端末Ｔ［Ｉ］間の劣化値「２０」の和「７０」として表され、劣化閾値「７０」以上であることから、劣化パスとなっている。
図２４〜図３０を利用して、以降の説明を記載する。
【０１６８】
（１）部分木データ再構築処理の入力情報としては、劣化パス内に含まれる選択ノードの子ノードである。上図においては、ノードＮ［２］とノードＮ［３］が該当し、この２つのノードがフローチャートにおける「抽出ノード２つ」を示している。
以降の処理は、抽出ノード２つに対して処理を実施するが、同じ処理を行うので、抽出ノードＮ［２］に対する処理のみ記載する。
【０１６９】
（２）抽出ノードから、抽出ノードに付随する測定端末Ｔまでのパス内に属するノードを抽出する（ステップＳ８０１）。
図３１に示すように、抽出ノードＮ［２］から抽出ノードＮ［２］に付随する測定端末Ｔまでのノードは、ノードＮ［２］からノード情報内の部分木構成ノードをたどることで得られ、それはノードＮ［４］およびノードＮ［Ａ］である。つまり、抽出ノードＮ［２］に対しては、本処理によって「ノードＮ［２］／ノードＮ［４］／ノードＮ［Ａ］」の３つが抽出されることになる。同様の処理は、抽出ノードＮ［３］に対しても行われる。
【０１７０】
（３）（２）において抽出したノードのうち測定端末Ｔのノード情報において、リンク劣化値をリンク劣化補正値に設定し、リンク劣化値に「０」を設定する。また、この測定端末Ｔの親ノードのノード情報に設定されている、各測定端末Ｔが属する子ノードペア情報においてパス劣化値を、リンク劣化補正値を減算した値に更新する（ステップＳ８０２、Ｓ８０３）。
図３２に示すように、測定端末Ｔのノード（ノードＮ［Ａ］）のノード情報において、リンク劣化値をリンク劣化補正値に設定し、リンク劣化値に「０」を設定する。また、ノードＮ［Ａ］の親ノードであるノードＮ［４］のノード情報に設定されている子ノードペア情報から、ノードＴ［Ａ］が属する子ノードペア情報を特定し、この子ノードペア情報において、現在設定されているパス劣化値からリンク劣化補正値を減算し、減算結果をパス劣化値に設定する。
このような補正処理を行うことによって、この区間が他のパスの一部となったときに、劣化値が加算されて、劣化パスとして検出されることを抑制している。
なお、本処理はノードＮ［Ｉ］についても同様に実施される。
【０１７１】
（４）第一階層から順に、上位階層に向けて以降の処理を実施する。つまり、ノードＮ［２］−ノードＮ［Ａ］間の第一階層のノードであるノードＮ［４］、および、ノードＮ［３］−ノードＮ［Ｉ］の間の第一階層に含まれるノードが処理対象となる（ステップＳ８０４〜Ｓ８０６）。
【０１７２】
（５）図３３に示すように、（４）において選択されたノード（ノードＮ［４］）のノード情報において、リンク劣化補正値にリンク劣化値を設定し、リンク劣化値に「０」を設定する（ステップＳ８０７）。
測定端末Ｔにおける処理と同様の理由で、リンク劣化値およびリンク劣化補正値を変更している。
【０１７３】
（６）選択されたノード（ノードＮ［４］）は第一階層のノードであることから、ノードＮ［４］において劣化区間候補抽出処理、及び、最大劣化区間抽出処理を実施し、ノードＮ［４］をルートノードとする部分木における最大劣化区間を変更する（ステップＳ８０８、Ｓ８１０、Ｓ８１１）。
劣化区間候補抽出では、パス劣化値が最も大きい２つのパスを抽出し、その中からルートノードとリーフノード間の劣化値が最大となる区間を候補として抽出する処理を行うことになる。
これまでの処理によって、図３４に示すように、ノードＮ［Ａ］のリンク劣化値、およびノードＮ［Ａ］−ノードＮ［Ｂ］間のパス劣化値が変更されており、その状態で劣化区間候補抽出が実施されることになる。
本例では、ノードＮ［Ａ］−測定端末Ｔ［Ｂ］間およびノードＮ［Ｃ］−測定端末Ｔ［Ｄ］間のパス以外のパスのパス劣化値は「０」としているので、再度実施される劣化区間候補抽出処理においては、ノードＮ［Ａ］−測定端末Ｔ［Ｂ］間およびノードＮ［Ｃ］−測定端末Ｔ［Ｄ］間のパスが抽出され、最も劣化値の大きいノードＮ［４］−測定端末Ｔ［Ｃ］間の区間が劣化区間候補として抽出されることになる。
もし、パス劣化値が「２０」のパスが存在していれば、そのパスとノードＮ［Ｃ］−測定端末Ｔ［Ｄ］間のパスが抽出され、その中から劣化区間候補が抽出されるという動作をする。
ノードＮ［４］をルートノードとする部分木において、ノードＮ［４］で折り返すパスが劣化となるかどうかの分析処理は既に実施済みであることから、折り返し劣化分析処理は実施せず、最大劣化区間抽出処理を実施することとなる。
以上の処理により、図３５に示すように、ノードＮ［４］における部分木構成ノードがノードＮ［Ｃ］に変更になるとともに、リンク合計劣化値「１５」に変更となる。
これで第一階層に属するノードＮ［４］における部分木データ再構築処理は終了となる。
【０１７４】
（７）次に第二階層に属するノード（ノードＮ［２］）を対象として、部分木データ再構築処理を実施する。まず、図３６に示すように第一階層のノードと同様に、リンク劣化補正値にリンク劣化値を設定し、リンク劣化値に「０」を設定する（ステップＳ８０６、Ｓ８０７）。
なお、本処理以降の処理は、第二階層以上のノードにおいて共通の処理となる。
【０１７５】
（８）（７）において選択したノード（ノードＮ［２］）は第二階層以上のノードであることから、ノード情報部分木構成ノードに設定されているノードＩＤが含まれる子ノードペア情報を特定し、その特定した子ノードペア情報に設定されている２つのノードに付随する測定端末Ｔ間のパスに属するノードのリンク劣化値の合計値をパス劣化値に設定する（ステップＳ８０８、Ｓ８０９）。
まず、ノードＮ［２］の部分木構成ノードはノードＮ［４］であることから、図３７に示すように、ノードＮ［４］が含まれる子ノードペア情報を抽出し、ノード情報内の部分木構成ノードをそれぞれ辿り、付随する測定端末Ｔを特定する。
本例では、ノードＮ［４］が属する子ノードペア情報には、ノードＮ［５］が設定されていることから、ノードＮ［４］およびノードＮ［５］に付随する測定端末Ｔを抽出する。
ここで、ノードＮ［５］の情報はなにも変更されていないので、ノードＮ［５］に付随する測定端末ＴはノードＮ［Ｆ］であるが、ノードＮ［４］に付随する測定端末Ｔは上記（６）の処理によって図３５に示すようにノードＮ［Ａ］からノードＮ［Ｃ］に変更となっている。つまり、ノードＮ［４］とノードＮ［５］それぞれに付随する測定端末Ｔ間のパス劣化値が異なっていることを意味する。
そこで、測定端末Ｔ間のパス内に属するノードのリンク劣化値の合計を算出し、それをパス劣化値として設定する。
本例では、ノードＮ［Ｃ］−ノードＮ［Ｆ］間のパス内にあるノードのノード情報は、図３８に示すようになっている。パス内にある各ノード、つまり、ノードＮ［Ｃ］、ノードＮ［４］、ノードＮ［２］、ノードＮ［５］、ノードＮ［Ｆ］のノード情報に設定されているリンク劣化値の合計「１５＋０＋０＋０＋２０」を算出し、その算出結果「３５」をノードＮ［４］及びノードＮ［５］の子ノードペア情報にパス劣化値として設定する。
【０１７６】
（９）上記までの処理によって、ノードＮ［２］における各子ノードペア情報のパス劣化値を補正後、上記（６）と同様に、ノードＮ［２］をルートノードとして劣化区間候補抽出処理および最大劣化区間抽出処理を実施する。これにより、劣化として検出されたパスの各リンクの劣化値を「０」と置いたときの、ノードＮ［２］から測定端末Ｔ間の劣化値が最大となる区間を再抽出しなおす（ステップＳ８１０、Ｓ８１１）。
本例では、入力のノード（抽出ノード２つ）は第二階層のノードなので、部分木データ再構築処理が完了となるが、より上位階層のノードが抽出ノードとして入力された場合は、各ノードにおいて上記（７）〜（９）の処理を繰り返し実施する。
【０１７７】
［３． 処理例］
ここでは、具体的な測定対象ネットワークの例を用いて、劣化パス検出装置１の一連の動作を説明する。
【０１７８】
図３９は、測定対象ネットワークを示す図であり、○で示した箇所がルータＲ、□で示した箇所が測定端末Ｔを意味している。また、ルータＲや測定端末Ｔに振られている数字（１〜２６）は、各ノードのＩＤを示している。また、ルータＲ間やルータＲ−測定端末Ｔ間を結んでいる線は、リンクを表している。
破線で示しているリンク（例えば、ノードＮ［１］−ノードＮ［２］間のリンク）や、ノード（例えば、ノードＮ［４］）は劣化箇所を示しており、各劣化箇所に振られた数値は、該当箇所の劣化値（例えば、遅延時間）を示している。
【０１７９】
第一階層に含まれるノードは、ノードＮ［２］、［３］、［４］、［５］であり、第二階層に含まれるノードはノードＮ［１］である。ノードＮ［２］には測定端末Ｔ［６］〜［１０］が接続され、ノードＮ［３］には測定端末Ｔ［１１］〜［１６］が接続され、ノードＮ［４］には測定端末Ｔ［１７］〜［２０］が接続され、ノードＮ［５］には測定端末Ｔ［２１］〜［２６］が接続されている。
【０１８０】
以下に、図３９の測定対象ネットワークを例に、劣化パス検出装置１による劣化パス検出方法について、上述したフローチャートに従って説明を記載する。なお、ここでは劣化閾値は「７０」とする。
【０１８１】
（１） 第一階層から順に上位階層に向かって処理を行う。最初に、第一階層が選択される（ステップＳ１０）。
【０１８２】
（２） まず、第一階層に含まれるノードである「ノードＮ［２］」を選択する（ステップＳ２０、Ｓ３０）。図４０〜図４４に、この選択されたノードＮ［２］の部分木に対する処理を説明するための図を示す。
選択ノードがノードＮ［２］の部分木に対する処理は、本アルゴリズムの最も基本となる処理であり、部分木内で劣化パスが検出されない例を示している。
【０１８３】
（２．１） 選択ノードである「ノードＮ［２］」に対して部分木データ構築処理を実施する（ステップＳ４０）。つまり、ここでの処理対象は図４０（ａ）に示す範囲である。
【０１８４】
（２．１．１） まず、選択ノードに対するノード情報を生成する（ステップＳ１０１）。これにより、図４１（ａ）に示すように、ノードＩＤ「２」が設定されたノード情報が生成される。
【０１８５】
（２．１．２） 続いて、トポロジ情報から、選択ノードであるノードＮ［２］の子ノードを抽出する。本例では、図４０（ａ）に示すように、ノードＮ［２］の子ノードは、ノードＮ［６］からノードＮ［１０］である（ステップＳ１０２）。抽出した子ノードのノード情報は未生成であることから、各子ノードのノード情報を生成する（ステップＳ１０３、Ｓ１０４）。図４１（ｂ）に生成した子ノードのノード情報を示す。
【０１８６】
（２．１．２） 選択ノードの子ノードリストに、生成した子ノードのノード情報を追加する（ステップＳ１０５）。図４１（ｃ）に、子ノードリスト追加後の選択ノードのノード情報を示す。
【０１８７】
（２．２） 選択ノードである「ノードＮ［２］」に対して部分木内測定処理を実施する（ステップＳ５０）。
【０１８８】
（２．２．１） 選択ノードの子ノードであるノードＮ［６］からノードＮ［１０］の中で未選択のノードに対して処理を行う（ステップＳ２０１）。
【０１８９】
（２．２．２） 選択ノードは第一階層に属しており、未選択の子ノードは２つ以上存在することから、ランダムに子ノードを２つ選択する。ここではノードＮ［６］とノードＮ［７］を選択したこととする（ステップＳ２０２、Ｓ２０６、Ｓ２０８）。
図４２（ａ）に示すように、子ノードペア情報を生成し、選択した子ノードのノードＩＤを設定する（ステップＳ２０９）。
【０１９０】
（２．２．３） 図４２（ｂ）に示すように、生成した子ノードペア情報を選択ノードのノード情報に追加する（ステップＳ２１０）。
【０１９１】
（２．２．４） 選択した２つの子ノード（ノードＮ［６］とノードＮ［７］）それぞれに付随する、２つの測定端末Ｔを特定する（ステップＳ２１１）。図４１（ｂ）に示すようにノードＮ［６］やノードＮ［７］のノード情報には部分木構成ノード情報が設定されていない、つまり測定端末Ｔであることを意味していることから、２つの子ノードに付随する測定端末Ｔは、ノードＮ［６］およびノードＮ［７］となる。
劣化パス検出装置１は、特定した測定端末Ｔに測定指示を出し、測定結果を受信する。また受信情報から特定した測定端末Ｔ間の測定劣化値を算出し、補正処理後、子ノードペア情報のパス劣化値に算出結果を設定する（ステップＳ２１２〜Ｓ２１４）。
補正処理とは、測定パス内の各ノードのノード情報内にあるリンク劣化補正値を、測定劣化値から減算する処理を示しているが、ノードＮ［６］−ノードＮ［７］を結ぶパス（ノードＮ［６］−ノードＮ［２］−ノードＮ［７］）内のノード情報にリンク劣化補正値は設定されていないことから、補正処理は行われず、測定劣化値がそのままパス劣化値として子ノードペア情報内に格納される。
本例では、測定劣化値は「１０」であることから、図４２（ｂ）に示すように、そのままパス劣化値に設定される。
【０１９２】
（２．２．５） 同様にして、ノードＮ［８］とノードＮ［９］の子ノードペア情報の生成、選択ノードのノード情報への子ノードペア情報の追加、ノードＮ［８］とノードＮ［９］間の測定、子ノードペア情報のパス劣化値への測定劣化値の設定を行なう（ステップＳ２０２、Ｓ２０６、Ｓ２０８〜Ｓ２１１）。図４２（ｃ）は、生成された子ノードペア情報と、子ノードペア情報が追加されたノード情報を示す図である。
ノードＮ［８］とノードＮ［９］間のパス劣化値は「０」であることから、図４２（ｄ）に示すように、ノードＮ［８］及びノードＮ［９］のノード情報のリンク劣化値に「０」を設定する（ステップＳ２１６）。
【０１９３】
（２．２．６） まだ未選択のノードはノードＮ［１０］だけであるので、選択済みのノードとペアリングする。ここでは、ノードＮ［９］を選択し、ペアリングする。そして、他のペアと同様に、ノードＮ［９］とノードＮ［１０］の子ノードペア情報の生成、選択ノードのノード情報への子ノードペア情報の追加、ノードＮ［９］とノードＮ［１０］間の測定、子ノードペア情報のパス劣化値への測定劣化値の設定を行なう（ステップＳ２０２、Ｓ２０6、Ｓ２０７、Ｓ２０９〜Ｓ２１１）。図４２（ｅ）は、生成された子ノードペア情報と、子ノードペア情報が追加されたノード情報を示す図である。
【０１９４】
（２．３） 続いて、選択ノードである「ノードＮ［２］」に対して劣化区間候補抽出処理を実施する（ステップＳ６０）。
選択ノードＮ［２］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する（ステップＳ５０１、Ｓ５０３）。
選択ノードＮ［２］の子ノードペア情報は図４２（ｂ）、（ｃ）、（ｅ）に示す通りなので、パス劣化値「２０」が設定されているノードＮ［９］及びノードＮ［１０］の子ノードペア情報と、パス劣化値「１０」が設定されているノードＮ［６］及びノードＮ［７］の子ノードペア情報が抽出される。
【０１９５】
（２．３．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
抽出された子ノードペア情報に設定されている子ノード（ノードＮ［６］、ノードＮ［７］、ノードＮ［９］、ノードＮ［１０］）のノード情報の全てにリンク劣化値の値が設定されておらず、また、両方の子ノードペア情報に属するノードＩＤが存在しない（ステップＳ４０１、Ｓ４０２）。
【０１９６】
（２．３．２） 一方の子ノードペア情報からランダムにノードＩＤを抽出し、そのノードに付随する測定端末Ｔを特定し、これを測定端末Ｔ（Ａ）と呼ぶ（ステップＳ４０５、Ｓ４０６）。
ここでは、ノードＮ［６］を選択したこととする。また、ノードＮ［６］は測定端末Ｔなので、ノードＮ［６］が測定端末Ｔ（Ａ）となる。他方の子ノードペア情報に属するノード（ノードＮ［９］およびノードＮ［１０］）それぞれに付随する測定端末Ｔを特定し、これを測定端末Ｔ（Ｂ）、測定端末Ｔ（Ｃ）と呼ぶ（ステップＳ４０７）。ノードＮ［９］およびノードＮ［１０］は測定端末Ｔなので、ノードＮ［９］を測定端末Ｔ（Ｂ）、ノードＮ［１０］を測定端末Ｔ（Ｃ）とする。
【０１９７】
（２．３．３） 測定端末Ｔ（Ａ）（ノードＮ［６］）と測定端末Ｔ（Ｂ）（ノードＮ［９］）間、及び測定端末Ｔ（Ａ）（ノードＮ［６］）と測定端末Ｔ（Ｃ）（ノードＮ［１０］）間で測定を実施し、測定端末間劣化値を得る。
測定端末Ｔ（Ａ）（ノードＮ［６］）と測定端末Ｔ（Ｂ）（ノードＮ［９］）間の測定端末間劣化値は「０」、測定端末Ｔ（Ａ）（ノードＮ［６］）と測定端末Ｔ（Ｃ）（ノードＮ［１０］）間の測定端末間劣化値は「２０」となる。
ここまでの処理によって、図４３（ａ）に示す４つのパスの劣化値を得たことになる。
【０１９８】
（２．３．４） 続いて、リンク劣化値算出処理において記載した方程式を解くことによって、選択ノードと各測定端末Ｔ間の劣化値を算出する。また、各選択ノードと測定端末Ｔ間のノードのリンク劣化値／リンク劣化補正値を利用して、選択ノードと選択ノードの子ノード間の劣化値を算出し、各子ノードのノード情報内のリンク劣化値に算出結果を設定する（ステップＳ４０９、Ｓ４１０）。ここでは、選択ノードの子ノードが測定端末Ｔであることから、方程式の解が選択ノードとその子ノード間の劣化値となる。
【０１９９】
ノードＮ［２］とノードＮ［６］の劣化値を「Ｌ２６」、ノードＮ［２］とノードＮ［７］の劣化値を「Ｌ２７」、ノードＮ［２］とノードＮ［９］の劣化値を「Ｌ２９」、ノードＮ［２］とノードＮ［１０］の劣化値を「Ｌ２１０」と置くと、下記のような方程式および解を得る。
【０２００】
Ｌ２６+Ｌ２７=１０，Ｌ２６+Ｌ２９=０，Ｌ２６+Ｌ２１０= ２０，Ｌ２９+Ｌ２１０=２０
∴ Ｌ２６=０，Ｌ２７=１０，Ｌ２９=０，Ｌ２１０=２０
【０２０１】
上記のようにして得られた結果を各子ノードのノード情報内のリンク劣化値に設定する。図４３（ｂ）は、リンク劣化値を設定した後の子ノードのノード情報を示す図である。
ここまでで、リンク劣化値算出処理は終了し、劣化区間候補抽出処理に戻る。
【０２０２】
（２．３．５） 続いて、抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する（ステップＳ５０５）。
【０２０３】
ノードＮ［６］−ノードＮ［７］間の劣化値：１０
ノードＮ［６］−ノードＮ［９］間の劣化値：０
ノードＮ［６］−ノードＮ［１０］間の劣化値：２０
ノードＮ［７］−ノードＮ［９］間の劣化値：１０（Ｌ２７+Ｌ２９=１０）
ノードＮ［７］−ノードＮ［１０］間の劣化値：３０（Ｌ２７+Ｌ２１０=３０）
ノードＮ［９］−ノードＮ［１０］間の劣化値：２０
【０２０４】
（２．３．６） 算出した測定端末間の劣化値に、劣化閾値「７０」を超えるパスは存在しないことから、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードを抽出し、選択ノードの部分木構成ノードに登録する（ステップＳ５０６、Ｓ５１２、Ｓ５１３）。
リンク合計劣化値は、任意のノードから測定端末Ｔまでの劣化値の合計を意味していることから、測定端末Ｔのノードにおいてはこの値は存在しない。つまり、リンク劣化値が最大となる子ノード（測定端末Ｔ）が抽出対象であり、それはノードＮ［１０］となる。図４４（ａ）に示すように、ノードＮ［１０］を選択ノードＮ［２］のノード情報における部分木構成ノードに登録する。
【０２０５】
（２．４） 選択ノードである「ノードＮ［２］」に対して折り返し劣化分析処理を実施する（ステップＳ７０）。
【０２０６】
（２．４．１） 選択ノードに登録されている部分木構成ノードのリンク劣化値とリンク合計劣化値の和を算出する（ステップＳ６０１）。
これは、部分木内における選択ノード（ノードＮ［２］）と測定端末Ｔ間の劣化値が最大となる可能性が高い劣化区間候補の劣化値を算出していることを意味する。ここでは、図４４（ａ）に示すように、ノードＮ［２］の部分木構成ノードに登録されているノードは、ノードＮ［１０］であり、図４３（ｂ）に示すように、ノードＮ［１０］のリンク劣化値とリンク合計劣化値の和は「２０」である。
【０２０７】
（２．４．２） 選択ノードの子ノードペア情報の中から、リンク劣化値が設定されている子ノードが属しておらず、かつパス劣化値と算出結果の和が劣化閾値を超える子ノードペアを抽出する（ステップＳ６０２）。
この時点で、選択ノード（ノードＮ［２］）の子ノードであるノードＮ［６］〜ノードＮ［１０］のノード情報は、ノードＮ［６］、［７］、［９］、［１０］については図４３（ｂ）、ノードＮ［８］については図４２（ｄ）のように設定されており、全ての子ノード情報にリンク劣化値が設定済みとなっている。また、選択ノードの子ノードペア情報は、図４２（ｂ）、（ｃ）、（ｅ）のようになっている。
つまり、子ノードペア情報に設定されているノード（ノードＮ［６］からノードＮ［１０］）のノード情報には、リンク劣化値が設定されていないノードが存在せず、パス劣化値と算出結果の和が劣化閾値を超える子ノードペアが存在しない（ステップＳ６０３：ＮＯ）。
以上により、折り返し劣化分析はこれで終了となる。
【０２０８】
（２．５） 続いて、選択ノードである「ノードＮ［２］」に対して最大劣化区間抽出処理を実施する（ステップＳ８０）。
折り返し劣化分析と同様に、選択ノードに登録されている部分木構成ノードのリンク劣化値とリンク合計劣化値の和を算出する（ステップＳ７０１）。先の折り返し劣化分析で、各ノード情報等の変更がないので、リンク劣化値とリンク合計劣化値の和は「２０」であり、これを基準劣化値とする。また、リンク劣化値が設定されていない選択ノードの子ノードは存在しない。よって、図４４（ｂ）に示すように、選択ノードのリンク合計劣化値に基準劣化値「２０」を設定する（ステップＳ７０２、Ｓ７０３、Ｓ７１４）。
【０２０９】
以上により、選択ノード（ノードＮ［２］）をルートノードとする部分木における分析が完了となる。図４０（ｂ）は、分析完了後の部分木を示す。同図において劣化値が最大となるパスに属する子ノード及びリンク、ならびに、その劣化値を示している。このように、選択ノードと測定端末Ｔ間の劣化値が最大となるパスに属する選択ノードの子ノード（ノードＮ［１０］）が決定される。
【０２１０】
（３） 次に、第一階層に含まれるノードである「ノードＮ［３］」を選択する（ステップＳ３０）。図４５〜図４９に、この選択されたノードＮ［３］に関する処理を説明するための図を示す。
選択ノードがノードＮ［３］の部分木の処理は、劣化区間候補抽出処理対象となる２つのパス以外に、選択ノード−測定端末Ｔ間の劣化値が最大となる区間が含まれている例を示している。
【０２１１】
（３．１） 選択ノードである「ノードＮ［３］」に対して部分木データ構築処理を実施する（ステップＳ４０）。つまり、ここでの処理対象は図４５（ａ）に示す範囲である。
ノードＮ［２］において実施した部分木データ構築処理と同様にして、選択ノードに対するノード情報、選択ノードの子ノード（ノードＮ［１１］からノードＮ［１６］）に対するノード情報を生成し、選択ノードの子ノードリストに生成した子ノードのノード情報を追加する。図４６（ａ）に生成した選択ノードのノード情報と、各ノード情報に追加した子ノードのノード情報を示す。
【０２１２】
（３．２） 選択ノードである「ノードＮ［３］」に対して部分木内測定処理を実施する（ステップＳ５０）。
ノードＮ［２］における部分木内測定処理と同様に、子ノードペアを生成し、選択ノードに子ノードペア情報を追加する。また、各ペア内のノードそれぞれに付随する測定端末Ｔ間で測定を実施し、パス劣化値を算出する。ここでは、ノードＮ［１１］−ノードＮ［１２］、ノードＮ［１３］−ノードＮ［１４］、ノードＮ［１５］−ノードＮ［１６］をそれぞれペアとする。また、各ペアにおけるパス劣化値は、ノードＮ［１１］−ノードＮ［１２］間では「３０（=１５+１５）」、ノードＮ［１３］−ノードＮ［１４］間では「２５（=１０+１５）」、ノードＮ［１５］−ノードＮ［１６］間では「２０（=０+２０）」となる。
以上から、図４６（ｂ）に示すように子ノードペア情報が生成され、選択ノードのノード情報の子ノードペアリストが追加になる。
劣化閾値を超えるパス劣化値は存在しないので、本処理はこれで終了となる。
【０２１３】
（３．３） 続いて、選択ノードである「ノードＮ［３］」に対して劣化区間候補抽出処理を実施する（ステップＳ６０）。
選択ノードＮ［３］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。ここでは、選択ノードＮ［３］の子ノードペア情報は図４６（ｂ）に示す通りのため、パス劣化値「３０」が設定されているノードＮ［１１］及びノードＮ［１２］の子ノードペア情報と、パス劣化値「２５」が設定されているノードＮ［１３］及びノードＮ［１４］の子ノードペア情報が抽出されることになる。
【０２１４】
（３．３．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
選択ノードがノードＮ［２］であるときに実施したリンク劣化値算出処理と同様にして、ノードＮ［３］−ノードＮ［１１］間、ノードＮ［３］−ノードＮ［１２］間、ノードＮ［３］−ノードＮ［１３］間、ノードＮ［３］−ノードＮ［１４］間の各劣化値を算出し、各子ノード情報のリンク劣化値に設定する。算出結果は以下のようになる。
【０２１５】
ノードＮ［３］−ノードＮ［１１］間の劣化値：１５
ノードＮ［３］−ノードＮ［１２］間の劣化値：１５
ノードＮ［３］−ノードＮ［１３］間の劣化値：１０
ノードＮ［３］−ノードＮ［１４］間の劣化値：１５
【０２１６】
よって、ノードＮ［１１］からノードＮ［１４］のノード情報は図４７（ａ）に示すようになる。
【０２１７】
次に、抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する。算出結果は以下のようになる。
【０２１８】
ノードＮ［１１］−ノードＮ［１２］間の劣化値：３０
ノードＮ［１１］−ノードＮ［１３］間の劣化値：２５
ノードＮ［１１］−ノードＮ［１４］間の劣化値：３０
ノードＮ［１２］−ノードＮ［１３］間の劣化値：２５
ノードＮ［１２］−ノードＮ［１４］間の劣化値：３０
ノードＮ［１３］−ノードＮ［１４］間の劣化値：２５
【０２１９】
上記により得られた測定端末間の劣化値の中に、劣化閾値「７０」を超えるパスは存在しないことから、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードであるノードを、選択ノードの部分木構成ノードに登録する。
ここでは、３区間の劣化値が最大であるので、ランダムに選択し、ノードＮ［１１］を選択することとする。
以上により、図４８（ａ）に示すように、ノードＮ［１１］を選択ノードＮ［３］のノード情報における部分木構成ノードに登録する。
【０２２０】
（３．４） 選択ノードである「ノードＮ［３］」に対して折り返し劣化分析処理を実施する（ステップＳ７０）。
図４８（ａ）に示すように、選択ノードの部分木構成ノードに登録されているノードはノードＮ［１１］であり、図４７（ａ）に示すように、ノードＮ［１１］のノード情報に登録されているリンク劣化値とリンク合計劣化値の和は「１５」である。また、選択ノードに登録されている子ノードのノード情報の中で、ノードＮ［１５］とノードＮ［１６］のノード情報については図４６（ａ）に示す設定内容のままであり、リンク劣化値に値が設定されていない。
選択ノードにおいて、ノードＮ［１５］とノードＮ［１６］はペアであり、子ノードペア情報は図４６（ｂ）に示すようになっている。
この子ノードペア情報に設定されているパス劣化値は「２０」であり、部分木構成ノード（ノードＮ［１１］）のリンク劣化値とリンク合計劣化値の和は「１５」であることから、２つの劣化値の和は「３５（=２０+１５）」であり、劣化閾値「７０」を超えない。
つまり、選択ノード（ノードＮ［３］）をルートノードとする部分木内において、選択ノードで折り返す通信パスが劣化パスにはなりえないことを意味している。
以上により、折り返し劣化分析はこれで終了となる。
【０２２１】
（３．５） 続いて、選択ノードである「ノードＮ［３］」に対して最大劣化区間抽出処理を実施する（ステップＳ８０）。
【０２２２】
（３．５.１） 部分木構成ノード（ノードＮ［１１］）を基準とした比較処理を実施する。
図４７（ａ）に示す部分木構成ノード（ノードＮ［１１］）のリンク劣化値「１５」とリンク合計劣化値「ＮＵＬＬ」の和が基準劣化値であり、その値は「１５」である。また、図４６（ｂ）に示す選択ノードの子ノードペア情報の中に、図４６（ａ）に示すようにリンク劣化値が設定されてないノード（ノードＮ［１５］、ノードＮ［１６］）が属する子ノードペア情報が存在し、図４６（ｂ）に示す子ノードペア情報からそのパス劣化値は「２０」であり、基準劣化値を超える（ステップＳ７０３：ＹＥＳ）。
これは、パス劣化値は小さいが、選択ノードと各子ノードに付随する測定端末Ｔ間の劣化値が、劣化区間候補抽出処理によって抽出した選択ノードと測定端末Ｔ間の劣化値を超える可能性があることを意味している。
【０２２３】
ノードＮ［１５］とノードＮ［１６］間のパス劣化値は「２０」であることから、図４９に示す状態（ａ）もしくは状態（ｂ）のような場合が考えられる。
状態（ａ）の時は、選択ノードと子ノード間の劣化値は、劣化区間候補の劣化値「１５」を超えないため、選択ノードと子ノード間の劣化値が最大となる子ノードはノードＮ［１１］であると言える。一方、状態（ｂ）の時は、劣化区間候補の劣化値「１５」を超え、選択ノードと子ノード間の劣化値が最大となる子ノードはノードＮ［１５］となる。
そこでステップＳ７０４以降では、基準劣化値を超えるパス劣化値が設定されたパスが、このどちらの状態となるのか分析している。
【０２２４】
そこで、抽出された子ノードペア情報（ノードＮ［１５］とノードＮ［１６］が属する子ノードペア情報）に属するノードをランダムに選択する。ここでは、ノードＮ［１５］を選択することとする。また、選択したノードに付随する測定端末Ｔを特定する。ここではノードＮ［１５］が測定端末Ｔなので、ノードＮ［１５］が特定対象の測定端末Ｔとなる（ステップＳ７０５）。
【０２２５】
選択ノードに登録されている部分木構成ノードに付随する測定端末Ｔを特定する（ステップＳ７０６）。
部分木構成ノードはノードＮ［１１］であり、また、ノードＮ［１１］は測定端末Ｔなので、特定対象の測定端末ＴはノードＮ［１１］である。
【０２２６】
特定した測定端末Ｔ間で測定を実施し、測定劣化値を算出するとともに、選択ノードと各測定端末Ｔ間の劣化値（比較劣化値）を算出する（ステップＳ７０７、Ｓ７０８）。
ノードＮ［１１］とノードＮ［１５］間で測定した際の劣化値は「１５」となる。ここで、ノードＮ［３］とノードＮ［１１］間の劣化値を「Ｌ３１１」、ノードＮ［３］とノードＮ［１５］間の劣化値を「Ｌ３１５」、ノードＮ［３］とノードＮ［１６］間の劣化値を「Ｌ３１６」とおくと、以下が成り立つ。
【０２２７】
Ｌ３１１+Ｌ３１５=１５，Ｌ３１５+Ｌ３１６=２０，Ｌ３１１=１５
∴ Ｌ３１５=０，Ｌ３１６=２０
【０２２８】
ここでの処理対象部分木は、選択ノードが第一階層のノードであり、選択ノードの子ノードは測定端末Ｔのノードであるため、上記の計算結果が選択ノードと子ノード間の劣化値となる。そのため、図４７（ｂ）に示すように、計算結果を各子ノード（ノードＮ［１５］とノードＮ［１６］）のリンク劣化値に設定する（ステップＳ７０９）。
【０２２９】
また、基準劣化値は「１５」であり、比較劣化値はノードＮ［３］−ノードＮ［１５］間の劣化値「０」およびノードＮ［３］−ノードＮ［１６］間の劣化値「２０」であることから、基準劣化値を超える比較劣化値が存在することになる（ステップＳ７１０：ＹＥＳ）。
図４８（ｂ）に示すように、基準劣化値を超えるパス（ノードＮ［３］−ノードＮ［１６］間のパス）に属する選択ノードの子ノードであるノードＮ［１６］を、選択ノードの部分木構成ノードに登録する（ステップＳ７１１）。
選択ノードにおける部分木構成ノードの変更が生じたため、新たな部分木構成ノードを利用して、再度、最大劣化区間抽出処理を実施する（ステップＳ７１２）。
【０２３０】
（３.５．２） 最大劣化区間抽出処理において、部分木構成ノード（ノードＮ［１６］）を基準とした比較処理を実施する。
図４７（ｂ）に示すノードＮ［１６］の部分木構成ノードのリンク劣化値「２０」とリンク合計劣化値「ＮＵＬＬ」の和が基準劣化値であり、その値は「２０」である。また、先の処理により、選択ノード（ノードＮ［３］）の子ノードにリンク劣化値が設定されていないノードは存在しなくなった。そのため、図４８（ｃ）に示すように、選択ノードのリンク合計劣化値に基準劣化値「２０」を設定する。
【０２３１】
以上により、選択ノード（ノードＮ［３］）をルートノードとする部分木における分析が完了となる。図４５（ｂ）は、分析完了後の部分木を示す。同図において、劣化値が最大となるパスに属する子ノード及びリンク、ならびに、その劣化値を示している。このように、選択ノードと測定端末Ｔ間の劣化値が最大となるパスに属する選択ノードの子ノード（ノードＮ［１６］）が決定される。
【０２３２】
（４） 次に、第一階層に含まれるノードである「ノードＮ［４］」を選択する（ステップＳ３０）。図５０〜図５３に、この選択されたノードＮ［４］に関する処理を説明するための図を示す。
選択ノードがノードＮ［４］の部分木の処理は、部分木内測定によって劣化パスが検出される例を示している。
【０２３３】
（４．１） 選択ノードである「ノードＮ［４］」に対して部分木データ構築処理を実施する（ステップＳ４０）。つまり、ここでの処理対象は図５０（ａ）に示す範囲である。
ノードＮ［２］において実施した部分木データ構築処理と同様にして、選択ノードに対するノード情報、選択ノードの子ノード（ノードＮ［１７］からノードＮ［２０］）に対するノード情報を生成し、選択ノードの子ノードリストに生成した子ノードのノード情報を追加する。図５１（ａ）に生成した選択ノードのノード情報と、各ノード情報に追加した子ノードのノード情報を示す。
【０２３４】
（４．２） 選択ノードである「ノードＮ［４］」に対して部分木内測定処理を実施する（ステップＳ５０）。
ノードＮ［２］における部分木内測定処理と同様に、子ノードペアを生成し、選択ノードに子ノードペア情報を追加する。また、各ペア内のノードそれぞれに付随する測定端末Ｔ間で測定を実施し、パス劣化値を算出する。ここでは、ノードＮ［１７］−ノードＮ［１８］、ノードＮ［１９］−ノードＮ［２０］をそれぞれペアとする。また、各ペアにおけるパス劣化値は、ノードＮ［１７］−ノードＮ［１８］間では「７０（=３０+２０+２０）」、ノードＮ［１９］−ノードＮ［２０］間では「２５（=２０+５）」となる。
以上から、図５１（ｂ）に示すように子ノードペア情報が生成され、選択ノードのノード情報の子ノードペアリストが追加になる。
劣化閾値は「７０」であり、ノードＮ［１７］−ノードＮ［１８］間のパス劣化値が「７０」であることから、このパスを劣化パスとして検出する（ステップＳ２１７〜Ｓ２１９）。
【０２３５】
（４．２．１） 劣化パスとして抽出された子ノードペア情報を利用して、測定劣化パス処理を実施する（ステップＳ２２０）。
部分木内測定において劣化パスとして抽出された子ノードペア情報は１つだけであるため、選択ノードの子ノードペア情報から、抽出子ノードペア情報以外の子ノードペア情報をランダムに選択する。ここでは、ノードＮ［１９］とノードＮ［２０］の子ノードペア情報を選択する（ステップＳ３０２、Ｓ３０４）。
つまり、次のリンク劣化値算出処理対象２つの子ノードペア情報は、図５１（ｂ）に示す２つとなる。
【０２３６】
（４．２．１．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
選択ノードがノードＮ［２］であるときに実施したリンク劣化値算出処理と同様にして、ノードＮ［４］−ノードＮ［１７］間、ノードＮ［４］−ノードＮ［１８］間、ノードＮ［４］−ノードＮ［１９］間、ノードＮ［４］−ノードＮ［２０］間の各劣化値を算出し、各子ノード情報のリンク劣化値に設定する。算出結果は以下のようになる。
【０２３７】
ノードＮ［４］−ノードＮ［１７］間の劣化値：４０
ノードＮ［４］−ノードＮ［１８］間の劣化値：３０
ノードＮ［４］−ノードＮ［１９］間の劣化値：１０
ノードＮ［４］−ノードＮ［２０］間の劣化値：１５
【０２３８】
よって、ノードＮ［１７］からノードＮ［２０］のノード情報は図５２（ａ）に示すようになる。
【０２３９】
選択ノード（ノードＮ［４］）は第一階層のノードであることから、図５２（ｂ）に示すように劣化パスとして抽出された子ノードペア情報のパス劣化値に「０」を設定し、この子ノードペア情報に属するノード（ノードＮ［１７］およびノードＮ［１８］）それぞれのノード情報に対し、リンク劣化補正値にリンク劣化値を設定し、リンク劣化値に「０」を設定する（ステップＳ３０７、Ｓ３０８）。
【０２４０】
（４．３） 選択ノードである「ノードＮ［４］」に対して劣化区間候補抽出処理を実施する（ステップＳ６０）。
選択ノードＮ［４］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。ここでは、選択ノードＮ［４］の子ノードペア情報は２つしかないため、パス劣化値「０」が設定されているノードＮ［１７］及びノードＮ［１８］の子ノードペア情報（図５２（ｂ））と、パス劣化値「２５」が設定されているノードＮ［１９］及びノードＮ［２０］の子ノードペア情報（図５１（ｂ））が抽出されることになる。
【０２４１】
（４．３．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
抽出された２つの子ノードペア情報に属するノードのノード情報は、ノードＮ［１７］及びノードＮ［１８］については、図５２（ｂ）に示すように、ノードＮ［１９］及びノードＮ［２０］については、図５２（ａ）に示すようになっている。既に、全てのノードのリンク劣化値は算出済みであるため、新たな処理をせずに、リンク劣化値算出処理は終了となる（ステップＳ４０１：ＹＥＳ）。
【０２４２】
次に、抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する。算出結果は以下のようになる。
【０２４３】
ノードＮ［１７］−ノードＮ［１８］間の劣化値：０
ノードＮ［１７］−ノードＮ［１９］間の劣化値：１０
ノードＮ［１７］−ノードＮ［２０］間の劣化値：１５
ノードＮ［１８］−ノードＮ［１９］間の劣化値：１０
ノードＮ［１８］−ノードＮ［２０］間の劣化値：１５
ノードＮ［１９］−ノードＮ［２０］間の劣化値：２５
【０２４４】
上記により得られた測定端末間の劣化値の中に、劣化閾値「７０」を超えるパスは存在しないことから、図５３（ａ）に示すように、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードであるノードＮ［２０］を、選択ノードの部分木構成ノードに登録する。
【０２４５】
（４．４） 選択ノードである「ノードＮ［４］」に対して折り返し劣化分析処理を実施する（ステップＳ７０）。
図５３（ａ）に示すように、選択ノードの部分木構成ノードに登録されているノードはノードＮ［２０］であり、図５２（ａ）に示すように、ノードＮ［２０］のリンク劣化値とリンク合計劣化値の和は「１５」である。また、図５２（ａ）及び図５２（ｂ）に示すように、選択ノード（ノードＮ［４］）に登録されている子ノードＮ［１７］〜［２０］のノード情報には、リンク劣化値が設定されていないノードは存在しない。
よって、折り返し劣化分析はこれで終了となる。
【０２４６】
（４．５） 選択ノードである「ノードＮ［４］」に対して最大劣化区間抽出処理を実施する（ステップＳ８０）。
図５２（ａ）に示すノードＮ［２０］の部分木構成ノード（ノードＮ［２０］）のリンク劣化値「１５」とリンク合計劣化値「ＮＵＬＬ］の和が基準劣化値であり、その値は「１５」である。また、選択ノード（ノードＮ［４］）に登録されている子ノードの中で、リンク劣化値が設定されていないノードは存在しないことから、図５３（ｂ）に示すように、基準劣化値「１５」を選択ノードのリンク合計劣化値に設定する。
【０２４７】
以上により、選択ノード（ノードＮ［４］）をルートノードとする部分木における分析が完了となる。図５０（ｂ）は、分析完了後の部分木を示す。同図において、劣化値が最大となるパスに属する子ノード及びリンク、ならびに、その劣化値を示している。このように、選択ノードと測定端末Ｔ間の劣化値が最大となるパスに属する選択ノードの子ノード（ノードＮ［２０］）が決定される。
【０２４８】
（５） 次に、第一階層に含まれるノードである「ノードＮ［５］」を選択する（ステップＳ３０）。図５４〜図５９に、この選択されたノードＮ［５］に関する処理を説明するための図を示す。
選択ノードがノードＮ［５］の部分木の処理は、劣化区間候補抽出処理を行う範囲内には劣化パスは検出されないが、劣化区間候補と他のパスの選択ノード−測定端末Ｔ間を結ぶ区間とを結ぶようなパスが劣化パスとなる例を示している。
【０２４９】
（５．１） 選択ノードである「ノードＮ［５］」に対して部分木データ構築処理を実施する（ステップＳ４０）。つまり、ここでの処理対象は図５４（ａ）に示す範囲である。
ノードＮ［２］において実施した部分木データ構築処理と同様にして、選択ノードに対するノード情報、選択ノードの子ノード（ノードＮ［２１］からノードＮ［２６］）に対するノード情報を生成し、選択ノードの子ノードリストに生成した子ノードのノード情報を追加する。図５５（ａ）に生成した選択ノードのノード情報と、各ノード情報に追加した子ノードのノード情報を示す。
【０２５０】
（５．２） 選択ノードである「ノードＮ［５］」に対して部分木内測定処理を実施する（ステップＳ５０）。
ノードＮ［２］における部分木内測定処理と同様に、子ノードペアを生成し、選択ノードのノード情報のノードペアリストに子ノードペア情報を追加する。また、各ペア内のノードそれぞれに付随する測定端末Ｔ間で測定を実施し、パス劣化値を算出する。ここでは、ノードＮ［２１］−ノードＮ［２２］、ノードＮ［２３］−ノードＮ［２４］、ノードＮ［２５］−ノードＮ［２６］をそれぞれペアとする。各ペアにおけるパス劣化値は、ノードＮ［２１］−ノードＮ［２２］間では「５０（=３０+２０）」、ノードＮ［２３］−ノードＮ［２４］間では「６０（=３０+３０）」、ノードＮ［２５］−ノードＮ［２６］間では「４０（=０+４０）」となる。
以上から、図５５（ｂ）に示すように子ノードペア情報が生成され、選択ノードのノード情報の子ノードペアリストが追加になる。
劣化閾値を超えるパス劣化値は存在しないので、本処理はこれで終了となる。
【０２５１】
（５．３） 選択ノードである「ノードＮ［５］」に対して劣化区間候補抽出処理を実施する（ステップＳ６０）。
選択ノードＮ［５］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。ここでは、選択ノードＮ［５］の子ノードペア情報は、図５５（ｂ）に示す通りのため、パス劣化値「５０」が設定されているノードＮ［２１］及びノードＮ［２２］の子ノードペア情報とパス劣化値「６０」が設定されているノードＮ［２３］及びノードＮ［２４］の子ノードペア情報が抽出されることになる。
【０２５２】
（５．３.１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
選択ノードがノードＮ［２］であるときに実施したリンク劣化値算出処理と同様にして、ノードＮ［５］−ノードＮ［２１］間、ノードＮ［５］−ノードＮ［２２］間、ノードＮ［５］−ノードＮ［２３］間、ノードＮ［５］−ノードＮ［２４］間の各劣化値を算出し、各子ノード情報のリンク劣化値に設定する。算出結果は以下のようになる。
【０２５３】
ノードＮ［５］−ノードＮ［２１］間の劣化値：３０
ノードＮ［５］−ノードＮ［２２］間の劣化値：２０
ノードＮ［５］−ノードＮ［２３］間の劣化値：３０
ノードＮ［５］−ノードＮ［２４］間の劣化値：３０
【０２５４】
よって、ノードＮ［２１］からノードＮ［２４］のノード情報は図５６（ａ）に示すようになる。
【０２５５】
次に、抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する。算出結果は以下のようになる。
【０２５６】
ノードＮ［２１］−ノードＮ［２２］間の劣化値：５０
ノードＮ［２１］−ノードＮ［２３］間の劣化値：６０
ノードＮ［２１］−ノードＮ［２４］間の劣化値：６０
ノードＮ［２２］−ノードＮ［２３］間の劣化値：５０
ノードＮ［２２］−ノードＮ［２４］間の劣化値：５０
ノードＮ［２３］−ノードＮ［２４］間の劣化値：６０
【０２５７】
上記により得られた測定端末間の劣化値の中に、劣化閾値「７０」を超えるパスは存在しないことから、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードであるノードを、選択ノードの部分木構成ノードに登録する。
ここでは、３区間の劣化値が最大であるので、ランダムに選択し、ノードＮ［２１］を選択することとする。
以上により、ノードＮ［２１］を選択ノードＮ［５］のノード情報における部分木構成ノードに登録する。
【０２５８】
（５．４） 選択ノードである「ノードＮ［５］」に対して折り返し劣化分析処理を実施する（ステップＳ７０）。
選択ノードの部分木構成ノードに登録されているノードはノードＮ［２１］であり、図５６（ａ）に示すように、ノードＮ［２１］のノード情報に登録されているリンク劣化値とリンク合計劣化値の和は「３０」である。また、図５６（ａ）に示すように、選択ノードに登録されている子ノードのノード情報の中で、ノードＮ［２５］とノードＮ［２６］のノード情報についてはリンク劣化値に値が設定されていない。
選択ノードにおいて、ノードＮ［２５］とノードＮ［２６］はペアであり、子ノードペア情報は図５５（ｂ）に示すようになっている。
この子ノードペア情報に設定されているパス劣化値は「４０」であり、部分木構成ノード（ノードＮ［２１］）のリンク劣化値とリンク合計劣化値の和は「３０」であることから、２つの劣化値の和は「７０（=３０+４０）」であり、劣化閾値「７０」以上となる（ステップＳ６０３：ＹＥＳ）。
つまり、部分木構成ノード（ノードＮ［２１］）に付随する測定端末Ｔと、抽出された子ノードペアのいずれかに付随する測定端末Ｔ間が劣化パスとなる可能性があることを意味している。
【０２５９】
ノードＮ［２５］とノードＮ［２６］間のパス劣化値は「４０」であることから、図５７に示す状態（ａ）もしくは状態（ｂ）のような場合が考えられる。
状態（ａ）の時は、選択ノードとノードＮ［２５］もしくは選択ノードとノードＮ［２６］間の劣化値と、ノードＮ［２１］のリンク劣化値とリンク合計劣化値の和が「７０」未満となる。状態（ｂ）のときは、選択ノードとノードＮ［２５］もしくは選択ノードとノードＮ［２６］間のいずれか一方と、ノードＮ［２１］のリンク劣化値とリンク合計劣化値の和が「７０」以上となる。
そこでステップＳ６０４以降では、劣化区間候補と他のパス内の選択ノード−測定端末Ｔ区間を結ぶことで、劣化パスとなるかどうか分析している。
【０２６０】
抽出された子ノードペア情報（ノードＮ［２５］とノードＮ［２６］が属する子ノードペア情報）に属するノードをランダムに選択する。ここでは、ノードＮ［２５］を選択することとする。また、選択したノードに付随する測定端末Ｔを特定する。ここではノードＮ［２５］が測定端末Ｔなので、ノードＮ［２５］が特定対象の測定端末Ｔとなる（ステップＳ６０５）。
【０２６１】
選択ノードに登録されている部分木構成ノードに付随する測定端末Ｔを特定する（ステップＳ６０６）。
部分木構成ノードはノードＮ［２１］であり、また、ノードＮ［２１］は測定端末Ｔなので、特定対象の測定端末ＴはノードＮ［２１］である。
【０２６２】
特定した測定端末Ｔ間で測定を実施し、測定劣化値を算出するとともに、選択ノードと各測定端末Ｔ間の劣化値を算出する（ステップＳ６０７、Ｓ６０８）。
ノードＮ［２１］とノードＮ［２５］間で測定した際の劣化値は「３０」となる。ここで、ノードＮ［５］とノードＮ［２１］間の劣化値を「Ｌ５２１」、ノードＮ［５］とノードＮ［２５］間の劣化値を「Ｌ５２５」、ノードＮ［５］とノードＮ［２６］間の劣化値を「Ｌ５２６」とおくと、以下が成り立つ。
【０２６３】
Ｌ５２１+Ｌ５２５=３０，Ｌ５２５+Ｌ５２６=４０，Ｌ５２１=３０
∴ Ｌ５２５=０，Ｌ５２６=４０
【０２６４】
ノードＮ［２５］およびノードＮ［２６］は、測定端末Ｔノードであることから、上記の計算結果が選択ノードと子ノード間の劣化値となる。そのため、図５６（ｂ）に示すように、計算結果を各子ノード（ノードＮ［２５］とノードＮ［２６］）のノード情報のリンク劣化値に設定する（ステップＳ６０９）。
【０２６５】
各測定端末Ｔ（ノードＮ［２１］、ノードＮ［２５］、ノードＮ［２６］）間の劣化値は以下のようになる（ステップＳ６１０）。
【０２６６】
ノードＮ［２１］−ノードＮ［２５］間の劣化値：３０
ノードＮ［２１］−ノードＮ［２６］間の劣化値：７０
ノードＮ［２５］−ノードＮ［２６］間の劣化値：４０
【０２６７】
このとき、劣化閾値「７０」以上のパスが存在しているので、これを劣化パスとして検出する（ステップＳ６１１、Ｓ６１２）。劣化パスに属する選択ノードの子ノードは、ノードＮ［２１］とノードＮ［２６］である（ステップＳ６１３）。また、選択ノードは第一階層に属していることから、図５６（ｃ）に示すように、抽出した子ノード（ノードＮ［２１］とノードＮ［２６］）のリンク劣化補正値にリンク劣化値を設定し、リンク劣化値に「０」を設定する（ステップＳ６１４、Ｓ６１８）。
【０２６８】
また、抽出した子ノード（ノードＮ［２１］とノードＮ［２６］）が属するそれぞれの子ノードペア情報のパス劣化値から、子ノードのリンク劣化補正値を減算し、減算結果をそれぞれのパス劣化値に設定する（ステップＳ６１９）。
ノードＮ［２１］およびノードＮ［２６］が属する子ノードペア情報は図５５（ｂ）に示すようになっている。よって、図５６（ｄ）に示すように、それぞれの子ノードペア情報のパス劣化値から、属するノードのリンク劣化補正値を減算する。
【０２６９】
以上の処理により、劣化区間候補抽出処理によって抽出された部分木構成ノードに付随する測定端末Ｔと選択ノード間の劣化値は「０」に補正されたことになる。つまり、この時点で選択ノードに登録されている部分木構成ノードは、選択ノード（ノードＮ［５］）をルートノードとする部分木内において、選択ノードと測定端末Ｔ間の劣化値が最大となる区間内の子ノードではない可能性がある。
そのため、再度、劣化区間候補抽出処理を実施すると共に、抽出された区間が劣化パスを構成するかどうか分析を行う（ステップＳ６２０、Ｓ６２１）。
【０２７０】
ここまでの処理によって、各ノード情報や子ノードペア情報は図５８に示すようになっている。
【０２７１】
（５.４．１） 選択ノードである「ノードＮ［５］」に対して劣化区間候補抽出処理を実施する（ステップＳ６２０）。
図５８に示すように、選択ノードＮ［５］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、同様にして、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。ここでは、パス劣化値「２０」が設定されているノードＮ［２１］及びノードＮ［２２］の子ノードペア情報と、パス劣化値「６０」が設定されているノードＮ［２３］及びノードＮ［２４］の子ノードペア情報を抽出する。
【０２７２】
（５.４．１．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
抽出された子ノードペア情報に属するノード（ノードＮ［２１］からノードＮ［２４］）全てにおいて、リンク劣化値が設定済みであることから、本処理は終了となる。
【０２７３】
抽出済みの子ノードペアに属する子ノードのリンク劣化値、およびリンク合計劣化値より、各子ノードに付随する測定端末Ｔ間の劣化値は、以下のようになる。
【０２７４】
ノードＮ［２１］−ノードＮ［２２］間の劣化値：２０
ノードＮ［２１］−ノードＮ［２３］間の劣化値：３０
ノードＮ［２１］−ノードＮ［２４］間の劣化値：３０
ノードＮ［２２］−ノードＮ［２３］間の劣化値：５０
ノードＮ［２２］−ノードＮ［２４］間の劣化値：５０
ノードＮ［２３］−ノードＮ［２４］間の劣化値：６０
【０２７５】
上記により得られた測定端末間の劣化値の中に、劣化閾値「７０」を超えるパスは存在しないことから、選択ノードの子ノードの中で、リンク劣化値とリンク合計劣化値の和が最大の子ノードであるノードを、選択ノードの部分木構成ノードに登録する。
ここでは、２区間の劣化値が最大であるので、ランダムに選択し、ノードＮ［２３］を選択することとする。
以上により、図５９（ａ）に示すように、ノードＮ［２３］を選択ノードＮ［５］のノード情報における部分木構成ノードに登録する。
【０２７６】
（５.４．２） 選択ノードである「ノードＮ［５］」に対して折り返し劣化分析処理を実施する（ステップＳ６２１）。
選択ノードの部分木構成ノードに登録されているノードはノードＮ［２３］であり、図５８に示すように、ノードＮ［２３］のノード情報に設定されているリンク劣化値とリンク合計劣化値の和は「３０」である。また、選択ノードのノード情報に子ノードリストとして設定されている子ノードのノード情報は図５８に示すようになっており、リンク劣化値が設定されていないノード情報は存在しない。
よって、ノードＮ［５］をルートノードとする部分木内においては、劣化パスはこれ以上存在しない。
【０２７７】
（５．５） 選択ノードである「ノードＮ［５］」に対して最大劣化区間抽出処理を実施する（ステップＳ８０）。
図５８に示すように、部分木構成ノード（ノードＮ［２３］）のリンク劣化値「３０」とリンク合計劣化値「ＮＵＬＬ」の和が基準劣化値であり、その値は「３０」である。
選択ノード（ノードＮ［５］）に登録されている子ノードの中で、リンク劣化値が設定されていないノードは存在しないことから、図５９（ｂ）に示すように、基準劣化値「３０」を選択ノードのノード情報のリンク合計劣化値に設定する。
【０２７８】
以上により、選択ノード（ノードＮ［５］）をルートノードとする部分木における分析が完了となる。図５４（ｂ）は、分析完了後の部分木を示す。同図において、劣化値が最大となるパスに属する子ノード及びリンク、ならびに、その劣化値を示している。このように、選択ノードと測定端末Ｔ間の劣化値が最大となるパスに属する選択ノードの子ノード（ノードＮ［２３］）が決定される。
【０２７９】
以上により、第一階層に属するノードＮ［２］からノードＮ［５］までの処理が終了となり、第二階層のノードに対する処理に移行する。
【０２８０】
（６） 第二階層に含まれるノードである「ノードＮ［１］」を選択する（ステップＳ３０）。図６０〜図６９に、この選択されたノードＮ［１］に関する処理を説明するための図を示す。
第二階層以上のノードが選択ノードのときの処理対象となる部分木は、選択ノードと選択ノードの子ノードを接続する部分木、および第一階層に属する各子ノード（ノードＮ［２］からノードＮ［５］）と測定端末Ｔ間の劣化値が最大となる区間（各子ノードの部分木構成ノードをたどることで得られる測定端末Ｔまでの区間）から構成される。
本例では、図６０に示す部分木が処理対象となる範囲である。
【０２８１】
図６０において、第一階層のノードと測定端末Ｔ間のリンクに記載されている数値は、第一階層の各部分木における処理において算出済みの既知の劣化値である。
また、ノードＮ［１］とノードＮ［２］間の数値は、ノードＮ［１］とノードＮ［２］間のリンクに含まれる未知の劣化値である。
ノードＮ［１］とノードＮ［４］間の括弧付きの数値は、ノードＮ［４］に劣化値「２０」があるため、計算上、ノードＮ［１］とノードＮ［４］間の劣化値として現れる、現時点では未知の劣化値である。
【０２８２】
選択ノードがノードＮ［１］の部分木の処理は、部分木内測定では劣化パスが検出されないが、劣化区間候補抽出処理で劣化パスが検出され、それに伴い部分木データ再構築処理が行われる例を示している。
【０２８３】
（６．１） 選択ノードである「ノードＮ［１］」に対して部分木データ構築処理を実施する（ステップＳ４０）。
（６．１．１） まず、選択ノードに対するノード情報を生成する（ステップＳ１０１）。これにより、図６１（ａ）に示すように、ノードＩＤ「１」が設定されたノード情報が生成される。
（６．１．２） 続いて、トポロジ情報から、選択ノードの子ノードを抽出する。本例では、ノードＮ［２］の子ノードは、ノードＮ［２］からノードＮ［５］である（ステップＳ１０２）。
抽出した子ノードのノード情報は生成済みであることから、図６１（ｂ）に示すようにノードＮ［２］からノードＮ［５］の子ノード情報を、生成したノードＮ［１］のノード情報の子ノードリストに追加する（ステップＳ１０３、Ｓ１０５）。ノードＮ［２］のノード情報は図４４（ｂ）に、ノードＮ［３］のノード情報は図４８（ｃ）に、ノードＮ［４］のノード情報は図５３（ｂ）に、ノードＮ［５］のノード情報は図５９（ｂ）に示すおとりである。
【０２８４】
（６．２） 選択ノードである「ノードＮ［１］」に対して部分木内測定処理を実施する（ステップＳ５０）。
【０２８５】
（６．２．１） 選択ノードの子ノードであるノードＮ［２］からノードＮ［５］の中で未選択のノードに対して処理を行う（ステップＳ２０１）。
【０２８６】
（６．２．２） 選択ノードは第二階層に属しており、未選択の子ノードは２つ以上存在することから、その中からリンク合計劣化値の最も大きい２つの子ノードを選択する（ステップＳ２０２、Ｓ２０３、Ｓ２０５）。
この時点で未選択の子ノードは、全ての子ノードであり、各子ノードのノード情報は、ノードＮ［２］について図４４（ｂ）に、ノードＮ［３］については図４８（ｃ）に、ノードＮ［４］については図５３（ｂ）に、ノードＮ［５］について図５９（ｂ）に示すようになっていることから、リンク合計劣化値の最も大きいノードＮ［５］と２番目にリンク合計劣化値の最も大きいノードＮ［３］をペアとする。２番目にリンク合計劣化値の最も大きいノードはノードＮ［２］とノードＮ［３］であるが、ここではランダムにノードＮ［３］を選択したものとする。
【０２８７】
（６．２．３） 図６２（ａ）に示すように、子ノードペア情報を生成し、選択した子ノードペアのノードＩＤを設定する。また、子ノードペア情報を選択ノードに追加する（ステップＳ２０９、Ｓ２１０）。
【０２８８】
選択した２つの子ノード（ノードＮ［３］とノードＮ［５］）それぞれに付随する２つの測定端末Ｔを特定する（ステップＳ２１１）。ノードＮ［３］のノード情報に登録されている部分木構成ノードはノードＮ［１６］であり、ノードＮ［１６］は測定端末Ｔノードであるので、ノードＮ［３］に付随する測定端末ＴはノードＮ［１６］となる。同様にして、ノードＮ［５］に付随する測定端末ＴはノードＮ［２３］である。
特定した２つの測定端末Ｔ（ノードＮ［１６］とノードＮ［２３］）間で測定を実施し、パス劣化値を算出する（ステップＳ２１２〜Ｓ２１４）。
本例では、パス劣化値は「５０」であることから、図６２（ｂ）に示すように、子ノードペア情報のパス劣化値に算出結果を設定する。
【０２８９】
同様にして、ノードＮ［２］とノードＮ［４］を子ノードペアとし、子ノードペア情報の生成、選択ノードへの子ノードペア情報の追加を行う。また、各子ノード（ノードＮ［２］とノードＮ［４］）それぞれに付随する測定端末Ｔ（ノードＮ［１０］とノードＮ［２０］）間で測定を実施し、算出したパス劣化値「６５」を子ノードペア情報に設定する（ステップＳ２０２、Ｓ２０３、Ｓ２０５、Ｓ２０９〜Ｓ２１４）。
以上の処理により、各情報は図６２（ｃ）に示すようになる。
パス劣化値は共に劣化閾値「７０」未満であることから、これで部分木内測定処理を終了する。
【０２９０】
（６．３） 選択ノードである「ノードＮ［１］」に対して劣化区間候補抽出処理を実施する（ステップＳ６０）。
選択ノードＮ［１］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する（ステップＳ５０１、Ｓ５０３）。本例では、図６２（ｂ）及び（ｃ）に示すように、ノードＮ［１］が持つ子ノードペア情報は２つしかないので、その２つが抽出されることになる。
【０２９１】
（６.３．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
ノードＮ［２］におけるリンク劣化値算出処理と同様にして、ノードＮ［１］とノードＮ［１］の子ノード（ノードＮ［２］からノードＮ［５］）それぞれに付随する測定端末Ｔ間の劣化値を算出する（ステップＳ４０１、Ｓ４０２、Ｓ４０５〜Ｓ４０９）。
ノードＮ［１］と各測定端末Ｔ間の劣化値は以下のようになる。
【０２９２】
ノードＮ［１］−ノードＮ［１０］（ノードＮ［２］に付随する測定端末Ｔ）間の劣化値：４０
ノードＮ［１］−ノードＮ［１６］（ノードＮ［３］に付随する測定端末Ｔ）間の劣化値：２０
ノードＮ［１］−ノードＮ［２０］（ノードＮ［３］に付随する測定端末Ｔ）間の劣化値：２５
ノードＮ［１］−ノードＮ［２３］（ノードＮ［４］に付随する測定端末Ｔ）間の劣化値：３０
【０２９３】
抽出した２つの子ノードペア情報内の各子ノードとその親ノード（選択ノード）間の劣化値を算出し、各子ノードのリンク劣化値に設定する（ステップＳ４１０）。
ここで、ノードＮ［１］の子ノード（ノードＮ［２］からノードＮ［５］）におけるリンク合計劣化値（各子ノードから付随する測定端末Ｔまでの合計劣化値）がわかっており、それぞれ以下のようになっている。
【０２９４】
ノードＮ［２］からノードＮ［２］に付随する測定端末Ｔ（ノードＮ［１０］）間の劣化値：２０
ノードＮ［３］からノードＮ［３］に付随する測定端末Ｔ（ノードＮ［１６］）間の劣化値：２０
ノードＮ［４］からノードＮ［４］に付随する測定端末Ｔ（ノードＮ［２０］）間の劣化値：１５
ノードＮ［５］からノードＮ［５］に付随する測定端末Ｔ（ノードＮ［２３］）間の劣化値：３０
【０２９５】
以上から、ノードＮ［１］と各子ノード（ノードＮ［２］からノードＮ［５］）間の劣化値は、以下のようになる。
ノードＮ［１］とノードＮ［２］間の劣化値：２０（＝（ノードＮ［１］とノードＮ［１０］間の劣化値）−（ノードＮ［２］とノードＮ［１０］間の劣化値）＝４０−２０）
ノードＮ［１］とノードＮ［３］間の劣化値：０（＝（ノードＮ［１］とノードＮ［１６］間の劣化値）−（ノードＮ［３］とノードＮ［１６］間の劣化値）＝２０−２０）
ノードＮ［１］とノードＮ［４］間の劣化値：１０（＝（ノードＮ［１］とノードＮ［２０］間の劣化値）−（ノードＮ［４］とノードＮ［２０］間の劣化値）＝２５−１５）
ノードＮ［１］とノードＮ［５］間の劣化値：０（＝（ノードＮ［１］とノードＮ［２３］間の劣化値）−（ノードＮ［５］とノードＮ［２３］間の劣化値）＝３０−３０）
【０２９６】
よって、ノードＮ［２］からノードＮ［５］のノード情報のリンク劣化値は図６３に示すようになる。
ここまでで、リンク劣化値算出処理は終了し、劣化区間候補抽出処理に戻る。
【０２９７】
続いて、抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する（ステップＳ５０５）。
【０２９８】
ノードＮ［１０］−ノードＮ［１６］間の劣化値：６０
ノードＮ［１０］−ノードＮ［２０］間の劣化値：６５
ノードＮ［１０］−ノードＮ［２３］間の劣化値：７０
ノードＮ［１６］−ノードＮ［２０］間の劣化値：４５
ノードＮ［１６］−ノードＮ［２３］間の劣化値：５０
ノードＮ［２０］−ノードＮ［２３］間の劣化値：５５
【０２９９】
ノードＮ［１０］−ノードＮ［２３］間の劣化値が「７０」であり、劣化閾値以上となるため、このパスを劣化パスとして検出すると共に、劣化パス内の選択ノードの子ノードを抽出する（ステップＳ５０６〜Ｓ５０８）。
ここで抽出されたノードは、ノードＮ［２］とノードＮ［５］となる。
また、選択ノード（ノードＮ［１］）は第二階層であることから、抽出した２つのノード（ノードＮ［２］とノードＮ［５］）を利用して、部分木データ再構築処理を実施する（ステップＳ５０８−１、Ｓ５０９）。
【０３００】
（６.３．２） 抽出したノード（ノードＮ［２］とノードＮ［５］）に対して、部分木データ再構築処理を実施する。
まず、各抽出ノードから抽出ノードそれぞれに付随する測定端末Ｔまでのパス内に属するノードを抽出する（ステップＳ８０１）。
ノードＮ［２］とそれに付随する測定端末Ｔ間のノードは、測定端末ＴのノードであるノードＮ［１０］のみである。また、ノードＮ［５］に対しては、ノードＮ［２３］のみである。つまり、S８０１においては、第一階層のノードＮ［２］とノードＮ［５］、測定端末ＴのノードＮ［１０］とノードＮ［２３］が抽出されることとなる。
本例では、抽出ノード（ノードＮ［２］、ノードＮ［５］）が第一階層のノードなので、ステップＳ８０１において新たに抽出されるノードは測定端末Ｔのノードのみであるが、抽出ノードが第二階層以上の場合、抽出ノードと測定端末Ｔのノードの間のノードも抽出されることとなる。
【０３０１】
次に、測定端末Ｔのノードにおいて、リンク劣化補正値にリンク劣化値をそのまま設定し、リンク劣化値を「０」に変更する（ステップＳ８０２）。
測定端末Ｔのノードは、ノードＮ［１０］とノードＮ［２３］であることから、この２つのノードのノード情報内のリンク劣化値とリンク劣化補正値を図６４（ａ）のように変更する。
【０３０２】
測定端末Ｔのノードの親ノードのノード情報に設定されている子ノードペア情報より、この測定端末Ｔのノードが属する子ノードペア情報を抽出し、パス劣化値から測定端末Ｔのノードのリンク劣化補正値を減算した値を、パス劣化値に設定する（ステップＳ８０３）。
【０３０３】
測定端末Ｔのノード（ノードＮ［１０］とノードＮ［２３］）が属する子ノードペア情報は図６４（ｂ）に示すとおりである。
ノードＮ［１０］のリンク劣化補正値は「２０」であり、ノードＮ［１０］が属する子ノードペア情報のパス劣化値は「２０」であることから、パス劣化値は「０（=２０−２０）」となる。
同様に、ノードＮ［２３］のリンク劣化補正値は「６０」であり、ノードＮ［２３］が属する子ノードペア情報のパス劣化値は「３０」であることから、パス劣化値は「３０（=６０−３０）」となる。
図６４（ｂ）の子ノードペア情報に新たに算出したパス劣化値を設定することにより、図６４（ｃ）に示すように更新される。
【０３０４】
次に、第一階層以上のノードに対して、下位層から順に処理を実施する（ステップＳ８０４、Ｓ８０５）。
第一階層に属するノードはノードＮ［２］とノードＮ［５］であることから、まずノードＮ［２］をランダムに選択する（ステップＳ８０６）。
【０３０５】
選択されたノードのノード情報における、リンク劣化補正値にリンク劣化値を設定し、リンク劣化値を「０」に変更する（ステップＳ８０７）。
本処理により、選択ノード（ノードＮ［２］）におけるノード情報は図６４（ｄ）に示すようになる。
選択ノード（ノードＮ［２］）は第一階層に属するノードであることから、補正処理後の状態において、劣化区間候補抽出処理および最大劣化区間抽出処理を実施する（ステップＳ８１０、Ｓ８１１）。
【０３０６】
（６．３.２．１） 選択ノードである「ノードＮ［２］」に対して劣化区間候補抽出処理を実施する（ステップＳ８１０）。
ここまでの部分木データ再構築処理によって、ノードＮ［２］をルートノードとする部分木の各情報は図６５（ａ）に示すようになっている。選択ノードＮ［２］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。ここでは、選択ノードＮ［２］の子ノードペア情報は図６５（ａ）に示す通りなので、パス劣化値「１０」の子ノードペア情報とパス劣化値「０」の子ノードペア情報が抽出されることになる。パス劣化値「１０」の子ノードペア情報は、ノードＮ［６］とノードＮ［７］のペアである。パス劣化値が「０」の子ノードペア情報は２つあるので、ランダムにノードＮ［８］とノードＮ［９］のペアを選択することとする。
【０３０７】
（６.３．２.１．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
抽出された２つの子ノードペア情報内のノードに対応したノード情報（ノードＮ［６］からノードＮ［９］）全てにリンク劣化値が既に設定済みなので、新たに算出処理はせずに、リンク劣化値算出処理は終了となる。
【０３０８】
ノードＮ［２］をルートノードとする部分木において、各測定端末Ｔ間の劣化値が劣化閾値を超えないので、図６５（ｂ）に示すように、選択ノード（ノードＮ［２］）と測定端末Ｔ間の劣化値が最大となるノードであるノードＮ［７］を部分木構成ノードとして、ノードＮ［２］のノード情報に設定する。
【０３０９】
（６．３.２．２） 選択ノードである「ノードＮ［２］」に対して最大劣化区間抽出処理を実施する（ステップＳ８１１）。
部分木構成ノード（ノードＮ［７］）のリンク劣化値とリンク合計劣化値の和が基準劣化値であり、その値は「１０」である。選択ノード（ノードＮ［２］）に登録されている子ノードの中で、リンク劣化値が設定されていないノードは存在しないことから、図６５（ｂ）に示すように、基準劣化値「１０」を選択ノードであるノードＮ［２］のリンク合計劣化値に設定する。
以上により、選択ノード（ノードＮ［２］）に対する処理が終了となる。
【０３１０】
次に、同じ第一階層に属するノードＮ［５］を選択ノードとし、処理を実施する（ステップＳ８０６）。
ノードＮ［２］における部分木データ再構築処理と同様に、選択ノード（ノードＮ［５］）におけるリンク劣化補正値に現在のリンク劣化値「０」を設定し、リンク劣化値に「０」を設定する。
選択ノード（ノードＮ［５］）は第一階層に属するノードであることから、補正処理後の状態において、劣化区間候補抽出処理および最大劣化区間抽出処理を実施する。
【０３１１】
（６．３.２．３） 選択ノードである「ノードＮ［５］」に対して劣化区間候補抽出処理を実施する（ステップＳ８１０）。
ここまでの部分木データ再構築処理によって、ノードＮ［５］をルートノードとする部分木の各情報は図６６（ａ）に示すようになっている。選択ノードＮ［５］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。従って、パス劣化値「２０」が設定されているノードＮ［２１］及びノードＮ［２２］の子ノードペア情報と、パス劣化値「３０」が設定されているノードＮ［２３］及びノードＮ［２４］の子ノードペア情報の２つが抽出される。
【０３１２】
（６.３．２.３．１） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
抽出された２つのノードペア内のノード情報（ノードＮ［２１］からノードＮ［２６］）全てにリンク劣化値が既に設定済みなので、新たに算出処理はせずに、リンク劣化値算出処理は終了となる。
【０３１３】
ノードＮ［５］をルートノードとする部分木において、各測定端末Ｔ間の劣化値が劣化閾値を超えないので、図６６（ｂ）に示すように、選択ノード（ノードＮ［５］）と測定端末Ｔ間の劣化値が最大となるノードであるノードＮ［２４］を部分木構成ノードとして、ノードＮ［５］のノード情報に設定する。
【０３１４】
（６．３．２．４） 選択ノードである「ノードＮ［５］」に対して最大劣化区間抽出処理を実施する（ステップＳ８１１）。
部分木構成ノード（ノードＮ［２４］）のリンク劣化値「３０」とリンク合計劣化値「ＮＵＬＬ」の和が基準劣化値であり、その値は「３０」である。選択ノード（ノードＮ［５］）に登録されている子ノードの中で、リンク劣化値が付与されていないノードは存在しないことから、図６６（ｂ）に示すように、基準劣化値「３０」を選択ノードであるノードＮ［５］に対応したノード情報のリンク合計劣化値に設定する。
以上により、選択ノード（ノードＮ［５］）に対する処理が終了となる。
また、以上で劣化区間候補抽出処理にから呼ばれた部分木データ再構築処理（ステップＳ５０９）は終了となる。
【０３１５】
部分木データ再構築処理が終了すると、選択ノードの子ノードペア情報から、抽出ノードが含まれる子ノードペア情報を抽出する（ステップＳ５１０）。
ステップＳ５０８の処理によって抽出されたノードは、ノードＮ［２］とノードＮ［５］であったことから、選択ノード（ノードＮ［１］）において、これらのノードが属する子ノードペア情報は図６７（ａ）に示すようになる。
【０３１６】
再構築処理後の各子ノードに付随する測定端末Ｔ間のパスに含まれるノードのリンク劣化値の和を算出し、算出結果を子ノードペア情報のパス劣化値に設定する（ステップＳ５１１）。
ノードＮ［２］から付随する測定端末Ｔまでは、ノードＮ［２］、ノードＮ［７］が属している。この２つのノード情報は、図６７（ｂ）に示すようになっている。
また、ノードＮ［４］付随する測定端末Ｔまでは、ノードＮ［４］、ノードＮ［２０］が属している。この２つのノード情報は、図６７（ｃ）に示すようになっている。
よって、図６７（ｄ）に示すように、ノードＮ［２］が属する子ノードペア情報のパス劣化値は、ノードＮ［２］のリンク劣化値「０」、ノードＮ［７］のリンク劣化値「１０」、ノードＮ［４］のリンク劣化値「１０」、ノードＮ［２０］のリンク劣化値「１５」、の和である「３５」となる。
【０３１７】
同様にして、ノードＮ［５］から付随する測定端末Ｔまでは、ノードＮ［５］、ノードＮ［２３］が属しており、また、ノードＮ［３］から付随する測定端末Ｔまでは、ノードＮ［３］、ノードＮ［１６］が属している。それぞれのノード情報は、図６７（ｅ）に示すようになっている。
よって、ノードＮ［５］が属する子ノードペア情報のパス劣化値は、図６７（ｆ）に示すように、ノードＮ［３］のリンク劣化値「０」、ノードＮ［１６］のリンク劣化値「２０」、ノードＮ［５］のリンク劣化値「０」、ノードＮ［２４］のリンク劣化値「３０」、の和である「５０」となる。
【０３１８】
以上までの処理により、選択ノード（ノードＮ［１］）の部分木における各情報は図６８に示すようになる。
【０３１９】
選択ノード（ノードＮ［１］）の子ノードペア情報のパス劣化値が変化したことから、再度、選択ノードにおいて劣化区間候補抽出処理を実施する（ステップＳ５１６）。
【０３２０】
（６．３．３） 選択ノードである「ノードＮ［１］」に対して劣化区間候補抽出処理を実施する（ステップＳ５１６）。
選択ノードＮ［１］の子ノードペア情報に設定されているパス劣化値の最大値は「０」ではないため、パス劣化値の最も大きい２つの子ノードペア情報を抽出する。
本例では、図６８に示すように、ノードＮ［１］が持つ子ノードペア情報は２つしかないので、その２つが抽出されることになる。
【０３２１】
（６．３．４） 抽出された２つの子ノードペア情報に基づいて、リンク劣化値算出処理を実施する。
既に、この２つの子ノードペア情報に属するノードのリンク劣化値は算出済みなので、特に何もせずに本処理は終了となる。
【０３２２】
抽出済みの子ノードペアに属するノードそれぞれに付随する測定端末Ｔ間の劣化値を算出する（ステップＳ５０５）。
【０３２３】
ノードＮ［７］−ノードＮ［１６］間の劣化値：３０
ノードＮ［７］−ノードＮ［２０］間の劣化値：３５
ノードＮ［７］−ノードＮ［２４］間の劣化値：４０
ノードＮ［１６］−ノードＮ［２０］間の劣化値：４５
ノードＮ［１６］−ノードＮ［２４］間の劣化値：５０
ノードＮ［２０］−ノードＮ［２４］間の劣化値：５５
【０３２４】
いずれの測定端末間の劣化値も劣化閾値「７０」未満であることから、リンク劣化値とリンク合計劣化値の和が最大の子ノードを抽出し、それを選択ノードの部分木構成ノードに設定する。
ここでは、ノードＮ［５］がリンク劣化値とリンク合計劣化値の和が最大であることから、図６９（ａ）に示すように、ノードＮ［５］を選択ノードの部分木構成ノードに設定する。
【０３２５】
（６．４） 選択ノードである「ノードＮ［１］」に対して折り返し劣化分析処理を実施する（ステップＳ７０）。
図６９（ａ）に示すように、選択ノードの部分木構成ノードに登録されているノードはノードＮ［５］であり、ノードＮ［５］のリンク劣化値とリンク合計劣化値の和は図６８のノードＮ［５］のノード情報に示すように「３０」である。
また、選択ノード（ノードＮ［１］）に登録されている子ノードであるノードＮ［２］、ノードＮ［３］、ノードＮ［４］、ノードＮ［５］のノード情報は図６８に示すようになっており、リンク劣化値が設定されていないノードは存在しない。
よって、折り返し劣化分析はこれで終了となる。
【０３２６】
（６．５） 選択ノードである「ノードＮ［１］」に対して最大劣化区間抽出処理を実施する（ステップＳ８０）。
上述のように、選択ノードの部分木構成ノードに登録されているノードはノードＮ［５］であり、ノードＮ［５］のリンク劣化値とリンク合計劣化値の和は「３０」であり、これが基準劣化値となる。選択ノード（ノードＮ［１］）に登録されている子ノードの中で、リンク劣化値が設定されていないノードは存在しないことから、図６９（ｂ）に示すように、ノードＮ［１］のノード情報のリンク合計劣化値に、基準劣化値「３０」を設定する。
【０３２７】
以上により、選択ノード（ノードＮ［１］）をルートノードとする部分木における分析が完了となる。
【０３２８】
また、全ての階層におけるノードに対する処理が完了したので、劣化パス検出装置１の出力部１６は、この処理の中で劣化パスとして検出したパスを出力する（ステップＳ９０）。これによって、劣化パス検出処理全てが完了となる。
【０３２９】
図７０は、劣化パス検出装置１の出力部１６の出力例を示す図である。
同図に示すように、ネットワークトポロジ情報から読み出したネットワークのトポロジを現すリンクに対して、検出した劣化パスの箇所を示している。同図においては、検出いした劣化パスとして、ノードＮ［１０］−ノードＮ［２］−ノードＮ［１］−ノードＮ［５］−ノードＮ［２３］のパス、ノードＮ［１７］−ノードＮ［４］−ノードＮ［１８］のパス、ノードＮ［２１］−ノードＮ［５］−ノードＮ［２６］のパスが示されている。
【０３３０】
［４． 部分木分割が可能なネットワークへの応用］
本実施の形態は、部分木ネットワーク自体ではなくとも、部分木分割可能なネットワークであれば適用可能である。
【０３３１】
図７１は、本実施形態による劣化パス検出装置が分析可能な測定対象ネットワークを示す図である。同図に示す測定対象ネットワークは、部分木分割が可能である。なお、部分木への分割方法は問わないが、図４のステップＳ１０の処理に示したように第一階層〜第Ｎ階層を順に選択していくことができる。
図７２は、図７１に示す測定対象ネットワークＮＷを部分木に分割した例を示す図である。図７１に示すネットワークは、何らかの方法によって、図７２に示す２つの部分木ネットワークＮＷ１及びＮＷ２に分割することができる。図７１及び図７２において、同じ符号を付したルータＲ１、Ｒ２は、同じノードを指している。そこで、図７２に示す分割した各部分木ネットワークＮＷ１及びＮＷ２それぞれにおいて劣化値が最大となるパスを、本実施形態のアルゴリズムによって見つける。
【０３３２】
図７３は、図７２に示す部分木ネットワークＮＷ１における劣化パスを示す図である。図７３において二重線により示すパスが、部分木ネットワークＮＷ１の劣化パス、つまり、劣化値が最大となる測定端末間のパスである。同様に、劣化パス検出装置１によって、部分木ネットワークＮＷ２の劣化パスが検出される。 このように、部分木に分割可能なネットワークであれば、木構造以外のネットワークにおいても本実施形態の劣化パス検出装置によれば劣化パスの検出が可能となる。
【０３３３】
［５． 効果］
本実施形態によれば、すでに測定パスの測定結果を利用して測定パス（測定端末）の重複度を最小限に抑えることによって、フルメッシュにより通信品質を測定することなく全ノードを対象とした効率的な品質測定を実現することができる。これにより、ネットワークに負荷を最小限に抑えながら劣化パスを検出することが可能であるため、大規模ネットワークへの応用が容易である。加えて、劣化パス検出の際に必要となる測定機器は、ネットワーク外部のみに配置すればよく、各区間の品質算出のためにネットワーク内部に測定機器を設置する必要がない。よって、設置コストを抑えることが可能である。
本実施形態によれば、すでに検出された劣化パス内の劣化値を演算補正しながら測定処理を実施しているため、他の劣化パス内の劣化が解消されると、劣化状態が解消されてしまうパスの検出を抑えながら、網内の劣化パスを検出することが可能であり、また、この検出された劣化パスのほとんどは独立しているため、劣化パス検出時の無駄な切り分け作業を抑えることができ、早期の故障回復が可能である。
【０３３４】
［６． その他］
なお、上述の劣化パス検出装置１は、内部にコンピュータシステムを有している。そして、劣化パス検出装置１の部分木ネットワーク構築部１１、測定指示実行部１２、測定結果受信／劣化値算出部１３、測定端末選定／劣化値分析部１４、及び、出力部１６の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
【０３３５】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【符号の説明】
【０３３６】
１…劣化パス検出装置
１１…部分木ネットワーク構築部
１２…測定指示実行部
１３…測定結果受信／劣化値算出部（劣化値取得部）
１４…測定端末選定／劣化値分析部（選定分析部）
１５…記憶部
１６…出力部
２…ネットワークトポロジ情報記憶装置
Ｒ…ルータ
Ｔ…測定端末
Ｎ…ノード

【特許請求の範囲】
【請求項１】
劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、
前記劣化パス検出装置は、
前記ネットワークを前記測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築部と、
前記部分木ネットワーク構築部によって分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する測定指示実行部と、
前記測定指示実行部による指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析部とを備え、
前記測定指示実行部は、前記木構造のトポロジにおいて前記選定分析部が特定した前記測定端末間による通信品質の測定を指示する、
ことを特徴とする劣化パス検出システム。
【請求項２】
劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、
前記劣化パス検出装置は、
測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとし、前記測定端末をリーフノードとする木構造の部分木ネットワークを前記ネットワークから抽出する部分木ネットワーク構築部と、
前記部分木ネットワーク構築部により抽出された前記部分木ネットワーク内の前記測定端末間による通信品質の測定を指示する測定指示実行部と、
前記測定指示実行部による指示に応じて得られた前記測定端末間の通信品質の測定劣化値に基づいてさらに測定対象の前記測定端末を選択し、前記測定指示実行部に選択した前記測定端末間の通信品質の測定を指示し、測定によって得られた前記測定端末間の測定劣化値に基づいて前記部分木ネットワーク内の劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる前記測定端末を特定する選定分析部とを備え、
前記部分木ネットワーク構築部は、前記ルートノードが最も下の階層である場合は前記ルートノードに接続される前記測定端末全てをリーフノードとし、前記ルートノードが最も下の階層ではない場合は、前記選定分析部によって選択された前記測定端末をリーフノードとした部分木ネットワークを抽出する、
ことを特徴とする劣化パス検出システム。
【請求項３】
劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムであって、
前記測定端末は、前記劣化パス検出装置からの指示を受け、他の前記測定端末との間で通信品質を測定する手段を備え、
前記劣化パス検出装置は、
測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとし、前記測定端末をリーフノードとする木構造の部分木ネットワークを前記ネットワークから抽出する部分木ネットワーク構築部と、
前記部分木ネットワーク構築部により抽出された前記部分木ネットワークにおける測定端末のペアを選択し、選択した前記測定端末のペア間における通信品質の測定を指示する測定指示実行部と、
前記測定指示実行部による指示に対応して前記選択した前記ペア間の通信品質の測定結果を取得して劣化値を算出する劣化値取得部と、
前記劣化値取得部が取得した前記測定端末間の測定劣化値に基づいて劣化パスの検出のために測定が必要な測定端末のペアを選択し、前記選択した測定端末のペア間の通信品質の測定を行なうよう前記測定指示実行部に指示し、前記劣化値取得部が取得した前記測定端末のペア間の測定劣化値によって前記部分木ネットワーク内のリンクの劣化値を取得して劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる前記測定端末を特定する選定分析部とを備え、
前記部分木ネットワーク構築部は、前記ルートノードが最も下の階層である場合は前記ルートノードに接続される前記測定端末全てをリーフノードとし、前記ルートノードが最も下の階層ではない場合は、前記選定分析部によって選択された前記測定端末をリーフノードとした部分木ネットワークを抽出する、
ことを特徴とする劣化パス検出システム。
【請求項４】
前記選定分析部は、前記劣化値取得部が取得した前記測定端末間の測定劣化値に基づいて劣化パスの検出のために測定が必要な測定端末を選択し、前記選択した測定端末間の通信品質の測定を行なうよう前記測定指示実行部に指示し、前記劣化値取得部が取得した前記測定端末間の測定劣化値によって前記部分木ネットワーク内のリンクの劣化値を取得して劣化パスを検出し、劣化パスが検出された場合は、劣化パス内の各リンクの劣化値を補正した後、前記部分木ネットワーク内のリンクの劣化値に基づいてルートノードとの間の劣化値が最大となる測定端末を特定する、
ことを特徴とする請求項３に記載の劣化パス検出システム。
【請求項５】
劣化パス検出装置と、複数のノードをリンクにより接続してなるネットワーク内の前記ノードに接続される測定端末とを備えた劣化パス検出システムに用いられる劣化パス検出方法であって、
前記劣化パス検出装置において、
部分木ネットワーク構築部が、複数のノードをリンクにより接続してなるネットワークから測定端末が接続されている層の前記ノードを選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する最下層部分木ネットワーク構築過程と、
測定指示実行部が、前記初期部分木ネットワーク構築過程において分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する最下層指示実行過程と、
選定分析部が、前記指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析過程と、
前記部分木ネットワーク構築部が、現在のルートノードより一階層上位のノードを新たなルートノードとして選択し、前記ネットワークを選択した新たなノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築過程と、
前記測定指示実行部が、前記部分木ネットワーク構築過程において分解された木構造のトポロジにおいて、前記選定分析過程によって特定された前記測定端末間による測定を指示する指示実行過程とを有し、
前記ネットワーク内の全てのノードについて処理を終了するまで前記選定分析過程からの処理を繰り返し実行する、
ことを特徴とする劣化パス検出方法。
【請求項６】
劣化パス検出装置として用いられるコンピュータに、
複数のノードをリンクにより接続してなるネットワークを、測定端末が接続されている階層の前記ノードから順に選択し、選択した前記ノードをルートノードとした木構造のトポロジに分解する部分木ネットワーク構築ステップと、
前記部分木ネットワーク構築ステップにおいて分解された前記木構造のトポロジにおいて、前記測定端末間による通信品質の測定を指示する測定指示実行ステップと、
前記測定指示実行ステップにおける指示に応じて得られた前記測定端末間の通信品質の劣化値に基づいて劣化パスを検出するとともに、前記ルートノードとの間の劣化値が最大となる測定端末を特定する選定分析ステップとを実行させ、
前記測定指示実行ステップにおいては、前記木構造のトポロジにおいて前記選定分析ステップにおいて特定された前記測定端末間による通信品質の測定を指示する処理を実行させる、
ことを特徴とするコンピュータプログラム。

【図１】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６】

【図１７】

【図１８】

【図１９】

【図２０】

【図２１】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７】

【図２８】

【図２９】

【図３０】

【図３１】

【図３２】

【図３３】

【図３４】

【図３５】

【図３６】

【図３７】

【図３８】

【図３９】

【図４０】

【図４１】

【図４２】

【図４３】

【図４４】

【図４５】

【図４６】

【図４７】

【図４８】

【図４９】

【図５０】

【図５１】

【図５２】

【図５３】

【図５４】

【図５５】

【図５６】

【図５７】

【図５８】

【図５９】

【図６０】

【図６１】

【図６２】

【図６３】

【図６４】

【図６５】

【図６６】

【図６７】

【図６８】

【図６９】

【図７０】

【図７１】

【図７２】

【図７３】

【公開番号】特開２０１１−１８８２８２（Ｐ２０１１−１８８２８２Ａ）
【公開日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願番号】特願２０１０−５１９０１（Ｐ２０１０−５１９０１）
【出願日】平成２２年３月９日（２０１０．３．９）
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【Ｆターム（参考）】