(57)【特許請求の範囲】
【請求項１】
複数の測定端末が中継装置を介してリンクにより接続してなるネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部と、
前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定する推定範囲決定部と、
前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定するテストパス決定部と、
前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信する測定指示実行部と、
前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出するパス劣化値算出部と、
前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定するリンク劣化値推定部と、
を備えることを特徴とする劣化値推定装置。
【請求項２】
前記ネットワークは木構造で構成され、
前記推定範囲決定部は、所定の前記中継装置をルートノードとした木構造のトポロジに前記ネットワークを分解し、分解した前記木構造のトポロジに含まれるリンクを前記推定範囲とすることを特徴とする請求項１に記載の劣化値推定装置。
【請求項３】
前記推定範囲決定部は、前記測定端末が接続されている階層の前記中継装置から順に選択し、選択した前記中継装置をルートノードとする前記推定範囲を決定し、
前記テストパス決定部は、前記ルートノードの階層が同一である全ての前記推定範囲のリンクの劣化値を前記リンク劣化値推定部が推定すると、当該階層より１つ高い階層の前記中継装置を前記ルートノードとする前記推定範囲のテストパスを決定し、
前記リンク劣化値推定部は、前記テストパス決定部が決定したテストパスに対応する前記推定範囲のリンクの劣化値を、当該推定範囲より低い階層にあるリンクの劣化値の推定値を用いて推定する
ことを特徴とする請求項２に記載の劣化値推定装置。
【請求項４】
複数の測定端末が中継装置を介してリンクにより接続してなるネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部を備えた劣化値推定装置に用いられる劣化値推定方法であって、
前記劣化値推定装置の推定範囲決定部が、前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定する過程と、
前記劣化値推定装置のテストパス決定部が、前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定する過程と、
前記劣化値推定装置の測定指示実行部が、前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信する過程と、
前記劣化値推定装置のパス劣化値算出部が、前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出する過程と、
前記劣化値推定装置のリンク劣化値推定部が、前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定する過程と、
を有することを特徴とする劣化値推定方法。
【請求項５】
複数の測定端末が中継装置を介してリンクにより接続ネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部を備えた劣化値推定装置として用いられるコンピュータに、
前記劣化値推定装置の推定範囲決定部が、前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定するステップと、
前記劣化値推定装置のテストパス決定部が、前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定するステップと、
前記劣化値推定装置の測定指示実行部が、前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信するステップと、
前記劣化値推定装置のパス劣化値算出部が、前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出するステップと、
前記劣化値推定装置のリンク劣化値推定部が、前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定するステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、劣化値推定装置、劣化値推定方法及びプログラムに関する。
【背景技術】
【０００２】
特許文献１には、複数の端末装置を含むネットワークシステムにおいて、端末装置が生成する受信品質劣化通知情報とネットワークシステムにおける経路情報に基づいて、通信品質劣化の原因となる区間を推定する技術が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−１７２６５５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、実際のネットワークでは、複数のノード（端末装置やルータ）間を接続するリンクを上りリンクと下りリンクで区別している全２重方式が多く採用されている。しかしながら、特許文献１に記載された技術では、上りリンクと下りリンクを区別せずに通信品質劣化の原因となる区間を推定しているため、上りリンクと下りリンクのいずれが劣化しているかを判断するのが困難である、という問題がある。また、仮に、通信品質の劣化を示す値である劣化値を１／２ずつ上りリンクと下りリンクに分配したとしても、上りリンクと下りリンクそれぞれの実際の劣化値に対する誤差が大きくなり、劣化値の推定精度が悪くなる。
【０００５】
本発明は上記の点に鑑みてなされたものであり、その目的は、上りリンクと下りリンクそれぞれの劣化値を算出することにより、劣化値の推定精度を向上させることができる劣化値推定装置、劣化値推定方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、複数の測定端末が中継装置を介してリンクにより接続してなるネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部と、前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定する推定範囲決定部と、前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定するテストパス決定部と、前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信する測定指示実行部と、前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出するパス劣化値算出部と、前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定するリンク劣化値推定部と、を備えることを特徴とする劣化値推定装置である。
【０００７】
この発明によれば、劣化値が最小であるテストパスが含むリンクの劣化値を、そのテストパスの劣化値に基づいて決定し、決定したリンクの劣化値を多元一次方程式に代入して、リンクの双方向それぞれの劣化値を推定している。これにより、リンクの上りと下りそれぞれの劣化値を精度良く推定することができる。また、最小限のテストパスで上りリンクと下りリンクそれぞれの劣化値を推定することができる。
【０００８】
また、本発明の一態様は、上記の劣化値推定装置において、前記ネットワークは木構造で構成され、前記推定範囲決定部は、所定の前記中継装置をルートノードとした木構造のトポロジに前記ネットワークを分解し、分解した前記木構造のトポロジに含まれるリンクを前記推定範囲とすることを特徴とする。
【０００９】
この発明によれば、木構造のネットワークを複数に分割してリンクの劣化値を推定する。これにより、ネットワーク全体だけではなく、任意の区間についての劣化値を推定することができる。
【００１０】
また、本発明の一態様は、上記の劣化値推定装置において、前記推定範囲決定部は、前記測定端末が接続されている階層の前記中継装置から順に選択し、選択した前記中継装置をルートノードとする前記推定範囲を決定し、前記テストパス決定部は、前記ルートノードの階層が同一である全ての前記推定範囲のリンクの劣化値を前記リンク劣化値推定部が推定すると、当該階層より１つ高い階層の前記中継装置を前記ルートノードとする前記推定範囲のテストパスを決定し、前記リンク劣化値推定部は、前記テストパス決定部が決定したテストパスに対応する前記推定範囲のリンクの劣化値を、当該推定範囲より低い階層にあるリンクの劣化値の推定値を用いて推定することを特徴とする。
【００１１】
この発明によれば、低い階層から順にリンクの劣化値を推定し、推定したリンクの劣化値を高い階層のリンクの劣化値を推定する際に用いる。これにより、テストパスの数を最小限に抑えて、効率良く劣化値を推定することができる。また、同階層にある推定範囲のリンクの劣化値を並行して推定すれば、全体の計算時間を短縮し、効率的に劣化値を推定することができる。
【００１２】
また、本発明の一態様は、複数の測定端末が中継装置を介してリンクにより接続してなるネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部を備えた劣化値推定装置に用いられる劣化値推定方法であって、前記劣化値推定装置の推定範囲決定部が、前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定する過程と、前記劣化値推定装置のテストパス決定部が、前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定する過程と、前記劣化値推定装置の測定指示実行部が、前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信する過程と、前記劣化値推定装置のパス劣化値算出部が、前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出する過程と、前記劣化値推定装置のリンク劣化値推定部が、前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定する過程と、を有することを特徴とする劣化値推定方法である。
【００１３】
また、本発明の一態様は、複数の測定端末が中継装置を介してリンクにより接続ネットワークにおける接続関係を特定するためのネットワークトポロジ情報を記憶する記憶部を備えた劣化値推定装置として用いられるコンピュータに、前記劣化値推定装置の推定範囲決定部が、前記記憶部により記憶されるネットワークトポロジ情報に基づいて、通信品質の劣化を示す値である劣化値を推定するリンクの範囲である推定範囲を決定するステップと、前記劣化値推定装置のテストパス決定部が、前記推定範囲決定部により決定された推定範囲内のリンクをテストパケットが双方向に通過するように、テストパケットの経路であるテストパスを複数決定するステップと、前記劣化値推定装置の測定指示実行部が、前記テストパス決定部により決定されたテストパスに基づいて、前記測定端末にテストパケットの伝送情報の測定指示を送信するステップと、前記劣化値推定装置のパス劣化値算出部が、前記測定指示実行部により送信された測定指示に応じて伝送された各テストパケットの伝送情報を前記測定端末から受信し、前記伝送情報に基づいて前記テストパスそれぞれの劣化値を算出するステップと、前記劣化値推定装置のリンク劣化値推定部が、前記劣化値が最小であるテストパスに含まれるリンクの劣化値を当該テストパスの劣化値に基づいて決定し、前記推定範囲に対応する全てのテストパスの劣化値を用いた多元一次方程式に当該決定したリンクの劣化値を代入して、前記推定範囲における全てのリンクの双方向それぞれの劣化値を推定するステップと、を実行させるためのプログラムである。
【発明の効果】
【００１４】
本発明によれば、劣化値が最小であるテストパスが含むリンクの劣化値を、そのテストパスの劣化値に基づいて決定し、決定したリンクの劣化値を多元一次方程式に代入して、リンクの双方向それぞれの劣化値を推定している。これにより、リンクの上りと下りそれぞれの劣化値を精度良く推定することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態による劣化値推定システムの全体構成を示すブロック図である。
【図２】本実施形態による劣化値推定装置の機能構成を示すブロック図である。
【図３】本実施形態による推定範囲決定処理等を説明するための略図である。
【図４】本実施形態によるテストパス決定処理の具体例を示す概略図である。
【図５】本実施形態による劣化値推定処理を説明するための概略図である。
【図６】本実施形態によるパス接続行列の具体例を示す概略図である。
【図７】本実施形態による劣化値近似後のパス接続行列の具体例を示す概略図である。
【図８】本実施形態によるリンクの劣化値推定処理の具体例を示す概略図である。
【図９】本実施形態によるリンク劣化値推定処理の手順を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照しながら本発明の実施形態について詳しく説明する。
図１は、本発明の一実施形態による劣化値推定システムの全体構成を示すブロック図である。
同図に示すように、複数のルータＲから構成される測定対象ネットワーク内のリンクの劣化値を推定する劣化値推定システムは、ネットワークトポロジ情報記憶装置２を備えた劣化値推定装置１と、測定対象ネットワークを構成するルータＲと、ルータＲに接続される測定端末Ｔとからなり、全ての測定端末Ｔと劣化値推定装置１とは通信ネットワークにより接続されている。劣化値は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）通信品質の劣化を示す値であり、遅延やパケットロス等を示す。ここで、劣化値の値が大きいほど劣化が大きいことを表し、劣化値の値が小さいほど劣化が小さいことを表す。
同図において、測定対象ネットワークは、木構造のネットワーク構成となっているが、部分木に分割が可能なネットワークであれば測定ネットワークの構造は問わない。
【００１７】
本実施形態では、測定端末Ｔ及び測定対象ネットワーク内のルータＲ等の中継装置を「ノード」とし、測定端末Ｔ−ルータＲ間、および、ルータＲ−ルータＲ間の区間を「リンク」とする。
そして、木構造のトポロジにおいて、測定端末Ｔが設置される層を測定端末層とし、測定対象ネットワークにおいて、測定端末Ｔに近いルータＲ（ノード）から順に第一階層、第二階層、・・・、第Ｎ階層とグルーピングする。以下の説明において、「第ｉ階層に含まれるノード」（ｉは、１，２，…，Ｎ）などと記載されている場合、第ｉ階層に含まれる全てのノードを指す。例えば、「第二階層に含まれるノード」と記載されている場合、図１に示すトポロジにおいては、第二階層内の２つのノードを指す。
階層の数字が小さいほう、つまり、測定端末層に近い階層を低い階層、階層の数字が多いほうを高い階層とし、あるノードと接続されている１つ低い階層のノードを当該ノードの子ノード、あるノードと接続されている１つ高い階層のノードを当該ノードの親ノードとする。また、低い階層から高い階層へ通信パケットが送信される方向を上り方向とし、高い階層から低い階層へ通信パケットが送信される方向を下り方向とする。
【００１８】
ネットワークトポロジ情報記憶装置２は、ネットワークトポロジ情報を記憶する。ネットワークトポロジ情報とは、測定対象ネットワークを構成するエレメント（ノード及びリンク）と、各測定端末Ｔとの接続関係を特定する情報である。各エレメントは一意の識別情報を持つ。ネットワークトポロジ情報には、各エレメントの識別情報、各ノードが測定端末ＴであるかルータＲであるかの種別、各ノードの通信アドレスの情報も含まれる。
【００１９】
劣化値推定装置１は、推定対象ネットワーク内のリンクの劣化値を推定する装置である。具体的には、劣化値推定装置１は、ネットワークトポロジ情報記憶装置２に記憶されているネットワークトポロジ情報に基づいて、テストパケットの伝送情報の測定指示を測定端末Ｔに送信する。テストパケットとは、劣化値を測定するための通信パケットである。そして、劣化値推定装置１は、測定指示に応じて伝送されたテストパケットの伝送情報を、テストパケットを受信した測定端末Ｔから受信する。伝送情報とは、テストパケットを送受信した時刻（タイムスタンプ）と、テストパケットを送受信した測定端末Ｔの識別情報と、テストパケットを特定するデータ（例えば、シーケンス番号）とを含むデータである。劣化値推定装置１は、伝送情報から各テストパスの劣化値を算出し、算出したテストパスの劣化値に基づいて、各リンクの上下方向それぞれの劣化値を推定する。
【００２０】
ルータＲは、ルータに限らず、スイッチ等のパケット伝送装置でもよい。測定端末Ｔは、一般の通信端末と同様に、測定端末Ｔ同士でアクティブな通信が可能な装置である。測定端末Ｔは、劣化値推定装置１からの測定指示に応じ、他の測定端末Ｔとの間でテストパケットの伝送を行い、テストパケットの伝送情報を劣化値推定装置１に送信する。なお、各測定端末Ｔによるテストパケット送受信時には時刻同期が行われているものとする。
【００２１】
図２は、本実施形態による劣化値推定装置１の機能構成を示すブロック図である。
劣化値推定装置１は、パス劣化値算出部１１と、リンク劣化値推定部１２と、推定範囲決定部１３と、テストパス決定部１４と、測定指示実行部１５とを含んで構成される。なお、ネットワークトポロジ情報記憶装置２は、劣化値推定装置１内に備えられてもよく、劣化値推定装置１と接続される外部の装置により実現してもよい。
【００２２】
推定範囲決定部１３は、ネットワークトポロジ情報記憶装置２が記憶するネットワークトポロジ情報に基づいて、劣化値を推定するリンクの範囲である推定範囲を決定する。本実施形態では、劣化値推定装置１は、木構造の測定対象ネットワークを部分木に分解し、低い階層にある部分木のリンクから順に劣化値を推定する。推定範囲は、分解した部分木に含まれるリンクである。推定範囲決定処理の詳細については後述する。
【００２３】
テストパス決定部１４は、推定範囲決定部１３が決定した推定範囲内のリンクをテストパケットが双方向（上下方向）に通過するように、テストパケットの経路であるテストパスを複数決定する。そして、テストパス決定部１４は、決定したテストパスのテストパス情報をネットワークトポロジ情報記憶装置２に記憶する。テストパス情報には、テストパスを構成するルータＲ、測定端末Ｔ及びリンクの識別情報と、経路（例えば、（測定端末Ｔ１）−（ルータＲ４）−（測定端末Ｔ２）等）が含まれる。測定指示実行部１５は、テストパス決定部１４が決定したテストパスに基づいて、各測定端末Ｔに測定指示を送信する。
【００２４】
パス劣化値算出部１１は、推定指示に応じて伝送されたテストパスの伝送情報を、テストパケットを受信した各測定端末Ｔから受信する。そして、パス劣化値算出部１１は、受信した伝送情報に基づいて、各テストパケットが通過したテストパスの劣化値をそれぞれ算出する。リンク劣化値推定部１２は、パス劣化値算出部１１が算出したテストパスの劣化値に基づいて、推定範囲内のリンクの上下方向それぞれの劣化値を推定する。劣化値推定処理の詳細については後述する。
【００２５】
図３は、本実施形態による推定範囲決定処理等を説明するための略図である。
ここで、図示する各ルータＲのそれぞれに対し、１〜８の数字を割り当て、ルータＲ１，Ｒ２，…，Ｒ８と記す。なお、各ルータＲ１，Ｒ２，…，Ｒ８に共通する事項については、１〜８の数字を省略し、単に「ルータＲ」又は「各ルータＲ」と記す。なお、図に示すルータＲは８台であるが、ルータＲ４とルータＲ５の間及びルータＲ２とルータＲ３の間にもルータＲは存在する。また、図示する各測定端末Ｔのそれぞれに対し、１〜１５の数字を割り当て、測定端末Ｔ１，Ｔ２，…，Ｔ１５と記す。各測定端末Ｔ１，Ｔ２，…，Ｔ１５に共通する事項については、１〜１５の数字を省略し、単に「測定端末Ｔ」又は「各測定端末Ｔ」と記す。
【００２６】
本図に示すように、推定範囲決定部１３は、木構造の測定対象ネットワークを、所定のノードをルートノードとした複数の部分木（木構造のトポロジ）に分解し、各部分木に含まれるリンクを推定範囲Ｓ１〜Ｓ８とする。そして、リンク劣化値推定部１２は、測定端末Ｔに近い階層にある推定範囲Ｓ１〜Ｓ５から順に、リンクの劣化値を推定する。
【００２７】
具体的には、推定範囲決定部１３は、まず、測定端末Ｔが接続されている第一階層のルータＲ４を選択し、選択したルータＲ４をルートノードとし測定端末Ｔ１，Ｔ２，Ｔ３をリーフノードとする部分木を生成する。そして、推定範囲決定部１３は、ルータＲ４（ルートノード）と測定端末Ｔ１，Ｔ２，Ｔ３（リーフノード）を接続するリンクを推定範囲Ｓ１とする。同様に、推定範囲決定部１３は、ルータＲ５，Ｒ６，Ｒ７，Ｒ８をルートノードとする部分木に含まれるリンクを推定範囲Ｓ２，Ｓ３，Ｓ４，Ｓ５とする。
【００２８】
次に、推定範囲決定部１３は、第一階層より１つ高い第二階層のノード（ルータＲ２，Ｒ３）をルートノードとする推定範囲Ｓ６，Ｓ７を決定する。最後に、推定範囲決定部１３は、第二階層より１つ高い第三階層のノード（ルータＲ１）をルートノードとする推定範囲Ｓ８を決定する。
【００２９】
テストパス決定部１４は、推定範囲内のリンクをテストパケットが双方向（上下方向）に通過するように複数のテストパスを決定する。具体的には、テストパス決定部１４は、推定範囲内の上りリンクと下りリンクの総数と同数のテストパスを決定する。例えば、テストパス決定部１４は、推定範囲Ｓ１において、測定端末Ｔ１から測定端末Ｔ２へテストパケットを送信するテストパスＰ１２と、測定端末Ｔ２から測定端末Ｔ１へテストパケットを送信するテストパスＰ２１と、測定端末Ｔ１から測定端末Ｔ３へテストパケットを送信するテストパスＰ１３と、測定端末Ｔ３から測定端末Ｔ１へテストパケットを送信するテストパスＰ３１と、測定端末Ｔ２から測定端末Ｔ３へテストパケットを送信するテストパスＰ２３と、測定端末Ｔ３から測定端末Ｔ２へテストパケットを送信するテストパスＰ３２と、を決定する。推定範囲Ｓ２，Ｓ３，Ｓ４，Ｓ５についても同様である。なお、本実施形態では、片方向通信によるテストパスを決定しているが、両方向通信による方法を用いてもよい。
【００３０】
リンク劣化値推定部１２は、テストパスＰ１２〜Ｐ３２の劣化値に基づいて、推定範囲Ｓ１内のリンクの上下方向それぞれの劣化値を推定する。推定範囲Ｓ２〜Ｓ５についても同様である。劣化値推定処理の詳細については後述する。
【００３１】
次に、テストパス決定部１４は、ルートノードの階層が第一階層である全ての推定範囲Ｓ１〜Ｓ５のリンクの劣化値をリンク劣化値推定部１２が推定すると、第一階層より１つ高い第二階層のノード（ルータＲ２，Ｒ３）をルートノードとする推定範囲Ｓ６，Ｓ７のテストパスを決定する。
【００３２】
図４は、本実施形態によるテストパス決定処理の具体例を示す概略図である。
テストパス決定部１４は、推定範囲Ｓ７において、各リンクをテストパケットが双方向に通過するように、テストパスを送受信する測定端末Ｔを決定する。図に示す例では、テストパス決定部１４は、ルータＲ６，ルータＲ７，ルータＲ８に接続された測定端末Ｔの中からそれぞれ任意の１台（測定端末Ｔ８，Ｔ１０，Ｔ１５）を選択する。推定範囲Ｓ６についても同様である。
【００３３】
リンク劣化値推定部１２は、推定範囲Ｓ７におけるテストパスの劣化値と、推定範囲Ｓ３，Ｓ４，Ｓ５のリンクの劣化値の推定値とに基づいて、推定範囲Ｓ７内のリンクの上下方向それぞれの劣化値を推定する。具体的には、リンク劣化値推定部１２は、推定範囲Ｓ７におけるテストパスの劣化値から、低い階層のリンクの劣化値を差し引く。例えば、リンク劣化値推定部１２は、測定端末Ｔ８から測定端末Ｔ１０へテストパケットを送信するテストパスＰ８１０の劣化値Ｐ８１０から、測定端末Ｔ８−ルータＲ６間の上りリンクの劣化値Ｕ８とルータＲ７−測定端末Ｔ１０間の下りリンクの劣化値Ｄ１０とを差し引く。同様に、リンク劣化値推定部１２は、推定範囲Ｓ７における他のテストパスから、低い階層のリンクの劣化値を差し引く。そして、リンク劣化値推定部１２は、低い階層のリンクの劣化値を差し引いた後のテストパスの劣化値に基づいて、推定範囲Ｓ７内のリンクの上下方向それぞれの劣化値を推定する。ここで、ルータＲ６−ルータＲ３間の上りリンクの劣化値をＵ６６とし、ルータＲ３−ルータＲ７間の下りリンクの劣化値をＤ７７とした場合、低い階層のリンクの劣化値を差し引いた後のテストパスの劣化値Ｐ’８１０（＝Ｐ８１０−Ｕ８−Ｄ１０）＝Ｕ６６＋Ｄ７７である。推定範囲Ｓ６についても同様である。劣化値推定処理の詳細については後述する。
【００３４】
続いて、テストパス決定部１４は、ルートノードの階層が第二階層である全ての推定範囲Ｓ６，Ｓ７のリンクの劣化値をリンク劣化値推定部１２が推定すると、第二階層より１つ高い第三階層のノード（ルータＲ１）をルートノードとする推定範囲Ｓ８のテストパスを決定する。リンク劣化値推定部１２は、推定範囲Ｓ８のテストパスの劣化値と、推定範囲Ｓ１〜Ｓ７のリンクの劣化値の推定値とに基づいて、推定範囲Ｓ８内のリンクの上下方向それぞれの劣化値を推定する。
【００３５】
このように、劣化値推定装置１は、木構造の測定対象ネットワークを複数の部分木（木構造のトポロジ）に分割し、低い階層から順にリンクの劣化値を推定し、低い階層におけるリンクの劣化値の推定値を用いて高い階層におけるリンクの劣化値を推定している。これにより、テストパスの数を最小限に抑えて、効率良く推定対象ネットワーク内のリンクの劣化値を推定することができる。また、並行して同階層にある推定範囲のリンクの劣化値を推定することにより、全体の計算時間を短縮することができる。
【００３６】
続いて、各推定範囲におけるリンクの劣化値推定処理について、図５から図８を用いて説明する。
図５は、本実施形態による劣化値推定処理を説明するための概略図である。
本図に例示する推定範囲Ｓ１は、ルータＲ１をルートノードとし、測定端末Ｔ１，Ｔ２，Ｔ３，Ｔ４をリーフノードとする。ここで、測定端末Ｔｉ（ｉ＝１，２，３，４）から測定端末Ｔｊ（ｊ＝１，２，３，４）へテストパケットが伝送されるテストパスＰｉｊの劣化値をＰｉｊとし、測定端末Ｔｉ−ルータＲ１間のリンクの上り方向の劣化値をＵｉとし、ルータＲ１−測定端末Ｔｊ間のリンクの下り方向の劣化値をＤｊとする。なお、Ｐｉｊ＝Ｕｉ＋Ｄｊ（ｉ≠ｊ）である。
【００３７】
テストパス決定部１４は、推定範囲Ｓ１内のリンクをテストパケットが双方向（上下方向）に通過するようにテストパスを決定する。まず、テストパス決定部１４は、任意の３台の測定端末Ｔ１，Ｔ２，Ｔ３について上下方向を考慮したフルメッシュでテストパスを決定する。具体的には、測定端末Ｔ１から測定端末Ｔ２へテストパケットを送信するテストパスＰ１２と、測定端末Ｔ２から測定端末Ｔ１へテストパケットを送信するテストパスＰ２１と、測定端末Ｔ１から測定端末Ｔ３へテストパケットを送信するテストパスＰ１３と、測定端末Ｔ３から測定端末Ｔ１へテストパケットを送信するテストパスＰ３１と、測定端末Ｔ２から測定端末Ｔ３へテストパケットを送信するテストパスＰ２３と、測定端末Ｔ３から測定端末Ｔ２へテストパケットを送信するテストパスＰ３２と、を決定する。次に、テストパス決定部１４は、４台目以降の測定端末Ｔ４については、測定端末Ｔ１，Ｔ２，Ｔ３のうちいずれかと双方向にテストパケットを送信するテストパスを決定する。具体的には、測定端末Ｔ３から測定端末Ｔ４へテストパケットを送信するテストパスＰ３４と、測定端末Ｔ４から測定端末Ｔ３へテストパケットを送信するテストパスＰ４３と、を決定する。
【００３８】
そして、テストパス決定部１４は、各測定端末Ｔ１，Ｔ２，Ｔ３，Ｔ４に測定指示を送信する。各測定端末Ｔ１，Ｔ２，Ｔ３，Ｔ４は、測定指示に従いテストパケットを送信する。そして、各測定端末Ｔ１，Ｔ２，Ｔ３，Ｔ４は、テストパケットを受信すると、伝送情報を生成し、生成した伝送情報を劣化値推定装置１のパス劣化値算出部１１に送信する。
【００３９】
パス劣化値算出部１１は、各測定端末Ｔ１，Ｔ２，Ｔ３，Ｔ４から伝送情報を受信すると、各テストパスの劣化値を算出する。図に示す例では、Ｐ１２＝６０であり、Ｐ２１＝６５であり、Ｐ１３＝１５であり、Ｐ３１＝８０であり、Ｐ２３＝１０であり、Ｐ３２＝７０であり、Ｐ３４＝６０であり、Ｐ４３＝３５である。
【００４０】
リンク劣化値推定部１２は、推定範囲Ｓ１のテストパスの劣化値Ｐ１２〜Ｐ４３を用いて、リンクの劣化値ｘ＝｛Ｕ１，Ｕ２，Ｕ３，Ｕ４，Ｄ１，Ｄ２，Ｄ３，Ｄ４｝を推定する。具体的には、次の多元一次方程式（１）により、リンクの劣化値ｘを算出する。
【００４１】
ｘ＝Ａ−１×Ｂ  …（１）
【００４２】
ここで、Ａ−１はパス接続行列Ａの逆行列である。また、Ｂはテストパスの劣化値のベクトルであり、Ｂ＝｛Ｐ１２，Ｐ２１，Ｐ１３，Ｐ３１，Ｐ２３，Ｐ３２，Ｐ３４，Ｐ４３｝＝｛６０，６５，１５，８０，１０，７０，６０，３５｝である。この多元一次方程式（１）は、テストパスの劣化値を用いた、リンクの劣化値を変数とする多元一次方程式である。
【００４３】
図６は、本実施形態によるパス接続行列Ａの具体例を示す概略図である。このパス接続行列Ａは、テストパスを行、リンクを列とし、テストパスとリンクの関係を示す行列である。リンク劣化値推定部１２は、テストパスが含むリンクを「１」、そうでない場合には「０」を、パス接続行列Ａの各要素に設定する。
【００４４】
ここで、図６に示すパス接続行列Ａの階数は７であり、変数であるリンクの劣化値の数８より少ない。このため、パス接続行列Ａの逆行列が存在せず、上述した多元一次方程式式（１）の解を求めることができない。よって、本実施形態によるリンク劣化値推定部１２は、劣化値が最小であるテストパスが含むリンクの劣化値を、このテストパスの劣化値で近似する。
【００４５】
具体的には、リンク劣化値推定部１２は、まず、劣化値が最小であるテストパスを抽出する。本例では、テストパスの最小劣化値はｍｉｎ（Ｐｉｊ）＝Ｐ２３＝１０である。そして、リンク劣化値推定部１２は、このテストパスＰ２３が含むリンクの劣化値であるＵ２とＤ３をＰ２３に基づいて決定する。具体的には、リンク劣化値推定部１２は、Ｕ２＝Ｄ３＝Ｐ２３（＝１０）／２＝５とする。
【００４６】
これは、測定範囲内のテストパス全てに劣化が含まれる確率が非常に低いことに基づいている。ここで、１リンクの劣化発生確率をＱとすると、１テストパスに劣化が発生している確率は１−（１−Ｑ）２＝２Ｑ−Ｑ２である。そして、仮に測定範囲内のテストパスが６本だった場合には、この推定範囲Ｓ内のリンク全てに劣化が発生している確率は（２Ｑ−Ｑ２）６となり、Ｑ＝０．１（１０％）とすると、約０．００５％である。よって、ｍｉｎ（Ｐｉｊ）≒０であることが言える。したがって、Ｕｉ＝Ｄｊ＝Ｐｉｊ／２とすることにより、誤差を最小限にすることができる。なお、本実施形態では、Ｕｉ＝Ｄｊ＝Ｐｉｊ／２としたが、例えばロス率等を考慮した場合にはＵｉ＝Ｄｊ＝０としてもよい。
【００４７】
図７は、本実施形態による劣化値近似後のパス接続行列Ａの具体例を示す概略図である。
リンク劣化値推定部１２は、劣化値を算出したＵ２又はＤ３いずれかの値を多元一次方程式に代入する。図７には、Ｕ２＝５とした場合の例を示す。具体的には、リンク劣化値推定部１２は、パス接続行列Ａの要素（Ｐ２３，Ｄ３）の値を「０」とする。そして、リンク劣化値推定部１２は、ベクトルＢにおけるＰ２３の値をＰ２３−Ｕ２＝１０−５＝５とする。これにより、パス接続行列Ａの階数が８となり、逆行列を算出することができる。
【００４８】
図８は、本実施形態によるリンクの劣化値推定処理の具体例を示す概略図である。
リンク劣化値推定部１２は、劣化値を近似した後のパス接続行列ＡとベクトルＢを用いて、上述した多元一次方程式（１）により、リンクの劣化値ｘ＝｛Ｕ１，Ｕ２，Ｕ３、Ｕ４，Ｄ１，Ｄ２，Ｄ３，Ｄ４｝＝｛１０，５，２０，３０，６０，５０，５，４０｝を算出する。
【００４９】
次に、図９を参照して、劣化値推定装置１によるリンク劣化値推定処理について説明する。図９は、本実施形態によるリンク劣化値推定処理の手順を示すフローチャートである。
まず、ステップＳ１において、推定範囲決定部１３が、推定範囲を決定する。そして、テストパス決定部１４が、推定範囲のテストパスを複数決定する。
次に、ステップＳ２において、測定指示実行部１５が、テストパス決定部１４が決定した各テストパスに基づいて、各測定端末Ｔに測定指示を送信する。具体的には、測定指示実行部１５は、各テストパスにおいて、テストパケットを送信する測定端末Ｔに対して、テストパケットを受信する測定端末Ｔ宛にテストパケットを送信する指示をするデータを送信する。そして、パス劣化値算出部１１が、推定指示に応じて各測定端末Ｔが送信したテストパケットの伝送情報を、テストパケットを受信した測定端末Ｔからそれぞれ受信する。
【００５０】
そして、ステップＳ３において、パス劣化値算出部１１は、各テストパケットの伝送情報に基づいて、各テストパスの劣化値Ｐｉｊを算出する。
次に、ステップＳ４において、リンク劣化値推定部１２は、各テストパスの劣化値を用いて、推定範囲におけるリンクの劣化値を変数とした多元一次方程式（１）を作成する。
【００５１】
続いて、ステップＳ５において、リンク劣化値推定部１２は、推定範囲におけるテストパスの最小劣化値ｍｉｎ（Ｐｉｊ）を抽出する。
次に、ステップＳ６において、リンク劣化値推定部１２は、ステップＳ５において抽出したテストパスが含むリンクの劣化値（Ｕｉ及びＤｊ）を、このテストパスの劣化値に基づいて近似する。具体的には、リンク劣化値推定部１２は、リンクの劣化値Ｕｉ＝Ｄｊ＝ｍｉｎ（Ｐｉｊ）／２とする。
【００５２】
そして、ステップＳ７において、リンク劣化値推定部１２は、ステップＳ６において近似したリンクの劣化値（Ｕｉ及びＤｊ）いずれかを、ステップＳ４において決定した多元一次方程式に代入して、各リンクの上下方向それぞれの劣化値を算出する。
最後に、ステップＳ８において、推定範囲決定部１３は、予め設定した推定対象範囲（例えば、推定対象ネットワーク全て）のリンクについて、劣化値を推定したか否かを判定する。全ての劣化値を推定した場合には処理を終了し、推定していない劣化値がある場合にはステップＳ１へ戻る。
【００５３】
このように、本実施形態によれば、最小劣化値を持つテストパスが含むリンクの劣化値をこの最小劣化値で近似し、多元一次方程式に代入して各リンクの上下方向それぞれの劣化値を算出している。これにより、最小限のテストパスで、推定対象ネットワーク内のリンクの双方向（上下方向）それぞれの劣化値を精度良く推定することができる。
また、大規模ネットワークに適用した場合、一度に全てのリンクを計算するのではなく、全体を複数に分割し並行して測定及び推定を行うことで効率的に劣化値を推定することができる。また、ネットワーク全体ではなく、任意の区間のみの劣化値を推定することができる。
【００５４】
また、図９に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、リンク劣化値推定処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００５５】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。  
【００５６】
以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上述のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。
例えば、本実施形態では、測定対象ネットワーク内におけるリンクの上下方向それぞれの劣化値を推定しているが、各劣化値から基準値を定め、この基準値より大きい劣化値を持つ区間（リンク）を劣化区間として判定するようにしてもよい。
【符号の説明】
【００５７】
１…劣化値推定装置  ２…ネットワークトポロジ情報記憶装置  １１…パス劣化値算出部  １２…リンク劣化値推定部  １３…推定範囲決定部  １４…テストパス決定部  １５…測定指示実行部  Ｒ…ルータ  Ｔ…測定端末
【図１】
0005439323.tif 000002
【図２】
0005439323.tif 000003
【図３】
0005439323.tif 000004
【図４】
0005439323.tif 000005
【図５】
0005439323.tif 000006
【図６】
0005439323.tif 000007
【図７】
0005439323.tif 000008
【図８】
0005439323.tif 000009
【図９】
0005439323.tif 000010