(57)【特許請求の範囲】
【請求項１】
複数のノードを含むネットワークの各ノード間の遅延を記述するメトリックツリーを作成するネットワーク遅延推定装置であって、
既知のメトリックツリーから、互いの距離が最も長い一対のノードを一巡目測定対象ノードとして選択し、任意のノードと前記一巡目測定対象ノードとの距離の測定を行う一巡目測定対象ノード選択部と、
前記一巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードとの距離が最も短いと推定されるノードを二巡目測定対象ノードとして選択し、前記任意のノードと前記二巡目測定対象ノードとの距離の測定を行う二巡目測定対象ノード選択部と、
前記二巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードを含むネットワークのメトリックツリーを作成する最適ツリー処理部と、
を有するネットワーク遅延推定装置。
【請求項２】
前記二巡目測定対象ノード選択部は、
前記一巡目測定対象ノード間を結ぶ経路との距離が最も短い位置のノードを、前記任意のノードとの距離が最も短いノードと推定する、
請求項１記載のネットワーク遅延推定装置。
【請求項３】
前記一巡目測定対象ノードと、この一巡目測定対象ノードに基づいて選択された前記二巡目測定対象ノードとに基づいて、前記既知のメトリックツリーに前記任意のノードを追加した候補ツリーを作成する候補ツリー作成部、を更に有し、
前記最適ツリー処理部は、
前記候補ツリーのうち、前記任意のノードと前記一巡目測定対象ノードおよび前記二巡目測定対象ノードとの間の各距離の、測定値に対する誤差が少ない候補ツリーを、前記任意のノードを含むネットワークのメトリックツリーとする、
請求項２記載のネットワーク遅延推定装置。
【請求項４】
前記二巡目測定対象ノード選択部は、
前記一巡目測定対象ノード間を結ぶ経路が複数存在するとき、前記任意のノードとの距離が最も短い経路上のノードを優先して、複数のノードを前記任意のノードとの距離が最も短いノードと推定し、
前記最適ツリー処理部は、
前記誤差が最も少ない候補ツリーを、前記任意のノードを含むネットワークのメトリックツリーとする、
請求項３記載のネットワーク遅延推定装置。
【請求項５】
前記最適ツリー処理部が作成したメトリックツリーを、以降の処理における前記既知のネットワークツリーとして格納する最適ツリーデータベース、を更に有する、
請求項１記載のネットワーク遅延推定装置。
【請求項６】
前記一巡目測定対象ノード選択部は、
前記互いの距離が最も長い一対のノードに加えて、対となる前記ノード間を結ぶ経路からの距離が最も長いノードおよびその次に長いノードを、前記一巡目測定対象ノードとして更に選択する、
請求項１記載のネットワーク遅延推定装置。
【請求項７】
前記一巡目測定対象ノード選択部、前記二巡目測定対象ノード選択部、および前記最適ツリー処理部は、
前記任意のノードが前記ネットワークに追加されることを条件として、それぞれ動作を開始する、
請求項１記載のネットワーク遅延推定装置。
【請求項８】
複数のノードを含むネットワークの各ノード間の遅延を記述するメトリックツリーを作成するネットワーク遅延推定方法であって、
既知のメトリックツリーから、互いの距離が最も長い一対のノードを一巡目測定対象ノードとして選択し、任意のノードと前記一巡目測定対象ノードとの距離の測定を行うステップと、
前記一巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードとの距離が最も短いと推定されるノードを二巡目測定対象ノードとして選択し、前記任意のノードと前記二巡目測定対象ノードとの距離の測定を行うステップと、
前記二巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードを含むネットワークのメトリックツリーを作成するステップと、
を有するネットワーク遅延推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの各ノード間の遅延を記述するメトリックツリーを作成するネットワーク遅延推定装置およびネットワーク遅延推定方法に関する。
【背景技術】
【０００２】
インターネット通信は、特定のタスクを目的として連携する多数のノードに分散化し、それらのノード間の相互依存の度合いは高くなりつつある。また、ピアツーピア通信、グリッドコンピューティング、クラスターコンピューティング、およびＡＬＭ（アプリケーション層マルチキャスティング）等は、多数のノードによる連携や通信を頼みとする新しい技術である。これらの技術を利用するアプリケーションは、相互依存的なタスクを正確に実行するために、ネットワークの各ノード間の遅延を記述するメトリックツリー（metric tree）を構築しておく必要がある。メトリックツリーを構築しておくことにより、任意のノード間の遅延を即時に推定することができるからである。
【０００３】
ところが、測定の対象となるノードの数がＮである場合、総当り的にフルメッシュで遅延測定を行うと、その測定回数はＮ×Ｎ−１となる。したがって、測定対象となるノードが多い場合には、メトリックツリーの構築のために、長い処理時間、高い演算能力、および大きい記憶容量が必要となる。このように負担が大きいと、例えば、アプリケーションによっては、メトリックツリーの構築が完了したときには、そのメトリックツリーが必要とされたタイミングが過ぎてしまっているといった事態が発生し得る。
【０００４】
そこで、ネットワークに新たにノードが追加される毎に、その加入ノードと、既知のメトリックツリーのノードとの間の遅延測定を行い、その測定結果をメトリックツリーに追加していく技術が、例えば非特許文献１に記載されている。この技術によれば、フルメッシュでの遅延測定を行うことなく、メトリックツリーを構築することができる。
【０００５】
ところが、非特許文献１記載の技術では、測定が行われなかった他のノードとの間の遅延は、低い精度でしか推定することができない。
【０００６】
そこで、加入ノードに最も近い（距離が短い）と推定される２つのノードを測定対象と選択する技術が、例えば、特許文献１に記載されている。この技術によれば、測定が行われなかった他のノードとの間の遅延を、より高い精度で推定することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許出願公開第２００８／０３０４４２１号明細書
【非特許文献】
【０００８】
【非特許文献１】Peter Buneman, “A Note on the Metric Properties of Trees”, Journal of combinatorial theory(B) 17, February 1974, p.48-50,
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１記載の技術では、加入ノードに近い２つのノードの推定が誤っていた場合、加入ノードと測定が行われなかった他のノードとの間の遅延は、低い精度でしか推定することができない。すなわち、特許文献１記載の技術は、メトリックツリーの精度の向上のために、加入ノードに近い２つのノードを特定する必要がある。このために、特許文献１記載の技術は、結局多数のノードの遅延測定を行うことになり、メトリックツリーが構築されるまでに時間が掛かるという課題がある。
【００１０】
本発明の目的は、メトリックツリーを高精度にかつ短時間で作成することができるネットワーク遅延推定装置およびネットワーク遅延推定方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明の一態様に係るネットワーク遅延推定装置は、複数のノードを含むネットワークの各ノード間の遅延を記述するメトリックツリーを作成するネットワーク遅延推定装置であって、既知のメトリックツリーから、互いの距離が長い一対または複数対のノードを一巡目測定対象ノードとして選択し、任意のノードと各一巡目測定対象ノードとの距離の測定を行う一巡目測定対象ノード選択部と、前記一巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードとの距離が短いと推定されるノードを二巡目測定対象ノードとして選択し、前記任意のノードと各二巡目測定対象ノードとの距離の測定を行う二巡目測定対象ノード選択部と、前記二巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードを含むネットワークのメトリックツリーを作成する最適ツリー処理部とを有する。
【００１２】
本発明の一態様に係るネットワーク遅延推定方法は、複数のノードを含むネットワークの各ノード間の遅延を記述するメトリックツリーを作成するネットワーク遅延推定方法であって、既知のメトリックツリーから、互いの距離が長い一対または複数対のノードを一巡目測定対象ノードとして選択し、任意のノードと各一巡目測定対象ノードとの距離の測定を行うステップと、前記一巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードとの距離が短いと推定されるノードを二巡目測定対象ノードとして選択し、前記任意のノードと各二巡目測定対象ノードとの距離の測定を行うステップと、前記二巡目測定対象ノードとの前記距離および前記既知のメトリックツリーに基づいて、前記任意のノードを含むネットワークのメトリックツリーを作成するステップとを有する。
【発明の効果】
【００１３】
本発明によれば、どのノードが任意のノードに近いのかを高精度に推定することができるので、メトリックツリーを高精度にかつ短時間で作成することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態におけるネットワークシステムの構成の一例を示すシステム構成図
【図２】本実施の形態に係るネットワーク遅延推定装置が保持する現在の最適ツリーの内容の一例を示す図
【図３】本実施の形態における一巡目の測定対象ノード選択の概要を説明するための図
【図４】本実施の形態における二巡目の測定対象ノード選択の概要を説明するための図
【図５】本実施の形態に係るネットワーク遅延推定装置の構成の一例を示すブロック図
【図６】本実施の形態におけるメトリックデータの構成の一例を示す図
【図７】本実施の形態における候補ツリーデータの構成の一例を示す図
【図８】本実施の形態における最適ツリーデータの構成の一例を示す図
【図９】本実施の形態に係るネットワーク遅延推定装置の全体動作を示すフローチャート
【図１０】本実施の形態におけるネットワークメッセージの構成の一例を示す図
【図１１】本実施の形態におけるネットワークメトリックの測定結果の構成の一例を示す図
【図１２】本実施の形態における一巡目測定対象ノードを選択する処理の詳細を示すフローチャート
【図１３】本実施の形態における第１の一巡目測定対象ノードを設定する処理の詳細を示すフローチャート
【図１４】本実施の形態における最良ノードを決定する処理の詳細を示すフローチャート
【図１５】本実施の形態における二巡目測定対象ノードを選択する処理の詳細を示すフローチャート
【図１６】本実施の形態における候補ツリーのセットを作成する処理の詳細を示すフローチャート
【図１７】本実施の形態における仮想ノードを追加する処理の詳細を示すフローチャート
【図１８】本実施の形態における二巡目測定対象ノードを抽出する処理の詳細を示すフローチャート
【図１９】本実施の形態における新しい最適ツリーを作成する処理の詳細を示すフローチャート
【図２０】本実施の形態における累積誤差を算出する処理の詳細を示すフローチャート
【発明を実施するための形態】
【００１５】
以下、本発明の一実施の形態について、図面を参照して詳細に説明する。
【００１６】
まず、本実施の形態の説明に先立って、本実施の形態における主な用語の定義について説明する。
「ツリー」とは、ノードとノード間を結ぶエッジとにより構成されるネットワークの構造である。
「メトリックツリー」とは、ノードと、ノード間の通信の遅延を示す重み付きエッジとにより構成される、ネットワークの各ノード間の遅延を記述する無方向の仮想的なツリーである。
「ネットワークメトリック」とは、２つのノード間の遅延の大きさを示すネットワークの特性値であり、２つのノード間のエッジの値の合計値である。
「実ノード」とは、メトリックツリーを構成するノードのうち、ネットワーク内に実際に存在する物理的なノードである。 
「仮想ノード」とは、メトリックツリーを構成するノードのうち、ネットワーク内に実際に存在しない仮想的なノードであって、後述の実ノードのペア間のネットワークメトリックを作成するために使用されるノードである。
「候補ツリー」とは、加入ノードがネットワークに追加される際に、ツリーの構築メカニズムの一部として作成される一時的なメトリックツリーであり、測定対象ノードを選択するために使用されるツリーである。
「最適ツリー」とは、候補ツリーの中から最良のツリーとして選択される、加入ノードを含むネットワークのメトリックツリーであり、その後の遅延推定に用いられるツリーである。
「新たな実ノード」とは、メトリックツリーに最後に追加された実ノード（このノードは、通常、加入ノードを指す）である。
「新たな仮想ノード」とは、メトリックツリーに最後に追加された仮想ノードである。
「現在の最適ツリー」とは、過去に生成された最適ツリーのうち最後のものである。
「加入ノード」とは、現在の最適ツリーには存在しない、ネットワークへの加入を要求したノードである。
「測定対象ノード」とは、現在の最適ツリーの実ノードのうち、加入ノードとの間の遅延が実際に測定される実ノードである。
「一巡目測定対象ノード」とは、現在の最適ツリーにおける各実ノードの位置に単に基づいて選択された測定対象ノードである。
「第１の一巡目測定対象ノード」とは、一巡目の遅延測定において、最初に選択される一巡目測定対象ノードのペアである。
「第２の一巡目測定対象ノード」とは、一巡目の遅延測定において、第１の一巡目測定対象ノードが選択された後に、第１の一巡目測定対象ノード以外の実ノードの中から選択される一巡目測定対象ノードのペアである。
「二巡目測定対象ノード」とは、一巡目の遅延測定の後に、現在の最適ツリーにおける各実ノードの位置だけでなく、加入ノードと一巡目測定対象ノードとの間の遅延測定結果に基づいて選択された、測定対象ノードである。
【００１７】
(実施の形態)
図１は、本発明の一実施の形態に係るネットワーク遅延推定装置が管理対象とするネットワークシステムの構成図の一例である。
【００１８】
図１に示すように、ネットワークシステム１００は、例えば、ノードＡ〜ノードＧ１０２〜１１４を有している。これらのノードは、ネットワーク１１６にそれぞれ接続されている物理的なノードである。なお、図示しないが、ネットワーク１１６には、他にも物理的なノードが存在し得る。ここでは、説明の簡便化のため、各ノードと他の全てのノードとの間に経路が存在しているものとするが、これに限定されない。ネットワーク遅延推定装置は、いずれかのノードに備えられていても良いし、ネットワーク１１６に接続された図示しない装置に備えられていても良い。
【００１９】
本実施の形態では、過去に取得されたメトリックツリーが、現在の最適ツリーとして既にネットワーク遅延推定装置に保持されているものとする。
【００２０】
図２は、ネットワーク遅延推定装置が保持する現在の最適ツリーの内容の一例を示す図である。
【００２１】
図２に示すように、現在の最適ツリー２００は、図１のネットワークシステム１００の現在の論理的な構造を推定したものである。現在の最適ツリー２００は、例えば、実ノードＡ〜Ｇ２０２〜２１４と、仮想ノード２１６〜２２４と、これらの実ノードおよび仮想ノードを結ぶ重み付きエッジ２２６〜２４６とにより構成される。
【００２２】
実ノードＡ〜Ｇ２０２〜２１４は、図１のノードＡ〜ノードＧに対応する要素である。仮想ノード２１６〜２２４は、実ノード間の遅延に基づいて挿入された仮想的な要素である。重み付きエッジ２２６〜２４６は、実ノードおよび仮想ノードを結び、それぞれ遅延値を持つ要素である。現在の最適ツリー２００の任意の２つの実ノード間における遅延は、その実ノードの間の全てのエッジの遅延値を合計する事によって、高い精度で推定することが可能となっている。また、実ノードＡ〜Ｇ２０２〜２１４は、現在の最適ツリー２００の端部にそれぞれ位置するものとする。
【００２３】
新たな加入ノードが追加された後のネットワークのメトリックツリーは、加入ノードと他の全てのノードとの間の遅延を測定すれば、最も高精度に得ることができるが、上述の通り、これには膨大な処理時間と処理負荷を伴う。ところが、一部の実ノードを選択して遅延測定を行う場合は、上述の通り、どの実ノードを測定対象ノードとして選択するかが問題となる。
【００２４】
そこで、本実施の形態に係るネットワーク遅延推定装置（以下、単に「ネットワーク遅延推定装置」という）は、下記の通り、入念に実ノードを選択し、選択した実ノード（測定対象ノード）のみについて遅延測定を行う。これにより、ネットワーク遅延推定装置は、少ない処理時間と処理負荷で、高精度な最適ツリーを構築することを可能にする。
【００２５】
ここで、ネットワーク遅延推定装置による最適ツリーの構築の仕方の概要について説明する。最適ツリーの構築とは、つまり、加入ノードを接続する仮想ノードを決定し、加入ノードと仮想ノードとの間の遅延を決定し、決定結果を現在の最適ツリーに反映させることである。
【００２６】
ネットワーク遅延推定装置は、大まかには、一巡目の測定対象ノード選択、一巡目の遅延測定、二巡目の測定対象ノード選択、二巡目の遅延測定、および接続ノードの決定を、この順序で行う。
【００２７】
図３は、一巡目の測定対象ノード選択の概要を説明するための図である。
【００２８】
図３（Ａ）に示すようなメトリックツリー２００ａが、現在の最適ツリーである場合を想定する。この場合、図３（Ｂ）に示すように、ネットワーク遅延推定装置は、最も長い経路である経路２４１ａの両端に位置する第１のノード２５１ａおよび第２のノード２５２ａを、第１の一巡目測定対象ノードのペアとして選択する。更に、ネットワーク遅延推定装置は、図３（Ｃ）に示すように、経路２４１ａからの距離が最も長い第３のノード２５３ａと、経路２４１ａからの距離が次に長い第４のノード２５４ａとを、それぞれ選択する。そして、ネットワーク遅延推定装置は、選択した第３のノード２５３ａおよび第４のノード２５４ａを、第２の一巡目測定対象ノードとする。
【００２９】
そして、ネットワーク遅延推定装置は、加入ノードと各一巡目測定対象ノード２５１ａ〜２５４ａとの間の遅延測定を行う。そして、ネットワーク遅延推定装置は、測定結果に基づいて、二巡目測定対象ノードの選択を行う。
【００３０】
図４は、二巡目の測定対象ノード選択の概要を説明するための図である。
【００３１】
まず、ネットワーク遅延推定装置は、図４（Ａ）に示すように、上記測定結果に基づき、加入ノード２６１ａとの距離２６２ａが最も近くなる位置に、仮想接続ノード２６３ａを設定する。この仮想接続ノード２６３ａは、既存の仮想ノードであっても良いし、適当な仮想ノードが存在しない場合には、新たに作成された仮想ノードであっても良い。
【００３２】
そして、ネットワーク遅延推定装置は、図４（Ｂ）に示すように、仮想接続ノード２６３ａ毎に、その仮想接続ノード２６３ａに隣接する２つの実ノード２６４ａを、二巡目測定対象ノードとして選択する。
【００３３】
そして、ネットワーク遅延推定装置は、加入ノード２６１ａと各二巡目測定対象ノード２６４ａとの間の遅延測定を行う。そして、ネットワーク遅延推定装置は、測定結果に基づいて、二巡目測定対象ノード２６４ａの中から、加入ノード２６１ａとの間の遅延が最も少ない二巡目測定対象ノード２６４ａを、加入ノード２６１ａの計測対象ノードとして選択する。
【００３４】
加入ノードに近いノードをより高精度に推定するためには、できるだけ遠くのノードとの間で行われた遅延測定結果が用いられる事が望ましい。このため、ネットワーク遅延推定装置は、上述のように、最も長い経路の両端のノードを、第１の一巡目測定対象ノードに選択し、更に、この経路から遠くに位置するノードを、第２の一巡目測定対象ノードに選択する。このような処理により、ネットワーク遅延推定装置は、加入ノードに近いノードを高精度に推定することができるので、高精度にかつ短時間で、最適ツリーを構築することができる。
【００３５】
次に、ネットワーク遅延推定装置の構成について説明する。
【００３６】
図５は、ネットワーク遅延推定装置の構成の一例を示すブロック図である。
【００３７】
図５において、ネットワーク遅延推定装置３０２は、イベント検出部３０４、一巡目測定対象ノード選択部３０６、メトリック処理部３０８、二巡目測定対象ノード選択部３１０、候補ツリー作成部３１２、最適ツリー処理部３１４、配信ツリー構築部３１６、候補ツリーデータベース（ＤＢ）３１８、メトリックデータベース（ＤＢ）３２０、および最適ツリーデータベース（ＤＢ）３２２を有する。
【００３８】
イベント検出部３０４は、ネットワーク遅延推定装置３０２の動作を開始させるネットワークイベントの発生を検出する。このネットワークイベントとは、加入ノードからネットワーク加入時に送信されるもので、加入ノードのネットワークＩＤ（identifier）を含むメッセージの受信である（３２４）。イベント検出部３０４は、メッセージを受信すると、そのメッセージに含まれているネットワークＩＤを、一巡目測定対象ノード選択部３０６へ渡す（３２６）。
【００３９】
一巡目測定対象ノード選択部３０６は、最適ツリーデータベース３２２に格納された現在の最適ツリーから、事前の評価に基づいて、互いの距離がより長い実ノードのペアを優先して、一巡目測定対象ノードとして選択する。また、一巡目測定対象ノード選択部３０６は、選択していない他の全てのノード（以下「非選択ノード」という）の、上述の実ノードのペアからの距離を評価し、距離が長い非選択ノードを探索する。そして、一巡目測定対象ノード選択部３０６は、探索された非選択ノードについても、一巡目測定対象ノードとして選択する（３２８）。
【００４０】
具体的には、一巡目測定対象ノード選択部３０６は、全ノードのうち所定の割合のノード（例えば、８分の１。ここでは、４つの実ノードとする。）が一巡目測定対象ノードとして選択される等、所定の終了条件が満たされるまで、この選択を繰り返す。終了条件は、ユーザの優先事項（精度または測定時間）に基づいて設定されてもよい。終了条件を、より高い割合のノード選択とすればするほど、新たに作成される最適ツリーの精度は向上するが、最適ツリーが作成されるまでに要する処理負荷は高くなり、処理時間は長くなる。
【００４１】
また、一巡目測定対象ノード選択部３０６は、終了条件が満たされると（例えば４つの実ノードが一巡目測定対象ノードとして選択されると）、メトリック処理部３０８に対して、一巡目のメトリック収集の開始を指示する（３３０）。一巡目のメトリック収集とは、加入ノードと各一巡目測定対象ノードとの間のネットワークメトリックの測定を行い、測定結果を収集することである。
【００４２】
メトリック処理部３０８は、他の機能部からの指示に従って、ネットワーク１１６から必要なネットワークメトリックを取得し、メトリックデータベース３２０に格納する。
【００４３】
具体的には、メトリック処理部３０８は、一巡目測定対象ノード選択部３０６からの指示を受けたときは、各一巡目測定対象ノードとの間の遅延測定を要求するネットワークメッセージを、加入ノードへ送信する（３３２）。そして、メトリック処理部３０８は、加入ノードから返信されてきた一巡目の遅延測定結果を（３３４）、メトリックデータとしてメトリックデータベース３２０へ格納する（３３６）。
【００４４】
また、メトリック処理部３０８は、後述の二巡目測定対象ノード選択部３１０からの指示を受けたときは、各一巡目測定対象ノードとの間の遅延測定を要求するネットワークメッセージを、加入ノードへ送信する（３３２）。そして、メトリック処理部３０８は、加入ノードから返信されてきた二巡目の遅延測定結果のデータを、メトリックデータとしてメトリックデータベース３２０へ格納する（３３６）。
【００４５】
図６は、メトリックデータベース３２０が格納するメトリックデータの構成の一例を示す図である。
【００４６】
図６に示すように、メトリックデータ１８００は、発側ノードＩＤ１８０８、着側ノードＩＤ１８１０、および遅延１８１２を、対応付けて記述する。発側ノードＩＤ１８０８には、加入ノードのネットワークＩＤが記述される。着側ノードＩＤ１８１０には、測定対象ノードのネットワークＩＤが記述される。遅延１８１２には、発側ノードＩＤ１８０８が示すノード（加入ノード）から着側ノードＩＤ１８１０が示すノード（測定対象ノード）への送信の遅延が、その組み合わせ毎に記述される。
【００４７】
二巡目測定対象ノード選択部３１０は、メトリックデータベース３２０に新たな一巡目の遅延測定結果の全てが格納される毎に、候補ツリー作成部３１２に対し、一巡目の遅延測定結果を渡して、候補ツリーの作成を指示する（３３８、３４０）。候補ツリーは、加入ノードを、推定される接続位置で現在の最適ツリーに追加した、一時的なメトリックツリーである。そして、二巡目測定対象ノード選択部３１０は、候補ツリー作成部３１２によって候補ツリーデータベース３１８に格納された、全ての候補ツリーの遅延実測値との誤差を評価して、遅延実測値との誤差が少ない候補ツリーを探索する（３４４）。
【００４８】
そして、二巡目測定対象ノード選択部３１０は、評価結果に従って、最良から最悪まで候補ツリーの順位付けを行い、より最良のものから順に、候補ツリー毎に巡目測定対象ノードの抽出を行う。
【００４９】
二巡目測定対象ノード選択部３１０は、全ノードのうち所定の割合のノード（例えば、８分の３）が二巡目測定対象ノードとして選択される等、所定の終了条件が満たされるまで、この抽出を繰り返す。そして、二巡目測定対象ノード選択部３１０は、終了条件が満たされると、抽出した二巡目測定対象ノードのリストを、メトリック処理部３０８へ渡す（３４６）。この結果、上述の通り、二巡目の遅延測定結果のデータが、メトリックデータベース３２０へ格納されることになる（３３６）。
【００５０】
候補ツリー作成部３１２は、他の機能部からの指示に従って、候補ツリーを作成し、作成した候補ツリーのデータ（以下「候補ツリーデータ」という）を、候補ツリーデータベース３１８に格納する（３４２）。
【００５１】
具体的には、候補ツリー作成部３１２は、二巡目測定対象ノード選択部３１０からの指示を受けたとき、一巡目測定対象ノードのペア毎に、ペアを結ぶ経路に対する加入ノードの相対位置を算出する。そして、候補ツリー作成部３１２は、経路との距離が最も短くなる位置で加入ノードを現在の最適ツリーに接続した場合のツリーを、候補ツリーとして作成する。
【００５２】
また、候補ツリー作成部３１２は、最適ツリー処理部３１４からの指示を受けたとき、一巡目測定対象ノードの全てのペアおよび二巡目測定対象ノードの全てのペア間におけるネットワークメトリックに基づいて、再び候補ツリーを作成する。
【００５３】
候補ツリーデータベース３１８は、候補ツリー作成部３１２の処理を受けて、候補ツリーデータを格納する。
【００５４】
図７は、候補ツリーデータベース３１８が格納する候補ツリーデータの構成の一例を示す図である。
【００５５】
図７に示すように、候補ツリーデータ１７００は、候補ツリーの各ノードの、ツリーＩＤ１７０８、ノードＩＤ１７１０、および種別１７１２を対応付けて記述する。また、候補ツリーデータ１７００は、候補ツリーの各エッジに関する、ツリーＩＤ１７２０、発側ノード１７２２、着側ノード１７２４、および距離１７２６を対応付けて記述する。ノードの種別１７１２には、ノードが実ノードと仮想ノードのいずれであるかを示す情報が記述される。また、エッジの距離１７２６には、発側ノード１７２２が示すノードと着側ノード１７２４が示すノードとの間の距離が記述される。
【００５６】
候補ツリーデータベース３１８に格納された候補ツリーデータは、二巡目測定対象ノード選択部３１０によって、二巡目測定対象ノードを選択する際に使用される。
【００５７】
最適ツリー処理部３１４は、メトリックデータベース３２０に新たな一巡目の遅延測定結果および二巡目の遅延測定結果の全てが格納される毎に、候補ツリー作成部３１２に対し、候補ツリーの作成を指示する（３４８、３５０）。この結果、上述の通り、二巡目測定対象ノードに基づいて作成された候補ツリーが、候補ツリーデータベース３１８へ格納されることになる（３４２）。そして、最適ツリー処理部３１４は、加入ノードと各測定対象ノードとの間の遅延測定結果（ネットワークメトリック）に基づいて、全ての候補ツリーを評価し（３５２）、最良の候補ツリーを、最適ツリーに決定する。そして、最適ツリー処理部３１４は、決定した最適ツリーのデータ（以下「最適ツリーデータ」という）を、最適ツリーデータベース３２２に格納する（３５４）。
【００５８】
図８は、最適ツリーデータベース３２２が格納する最適ツリーデータの構成の一例を示す図である。
【００５９】
図８に示すように、最適ツリーデータ１９００は、最適ツリーの各ノードの、ノードＩＤ１９０８および種別１９１０を対応付けて記述する。また、最適ツリーデータ１９００は、候補ツリーの各エッジに関する、発側ノード１９１８、着側ノード１９２０、および距離１９２２を対応付けて記述する。ノードの種別１９１０には、ノードが実ノードと仮想ノードのいずれであるかを示す情報が記述される。また、エッジの距離１９２２には、発側ノード１９１８が示すノードと着側ノード１９２０が示すノードとの間の距離が記述される。
【００６０】
配信ツリー構築部３１６は、例えば、オペレータ操作等による任意の区間の遅延の問い合わせを受けて、問い合わせのあった区間の遅延を、最適ツリーデータベース３２２の最適ツリーデータから取得する。
【００６１】
また、ネットワーク遅延推定装置３０２は、図示しないが、例えば、ＣＰＵ（central processing unit）、制御プログラムを格納したＲＯＭ（read only memory）等の記憶媒体、ＲＡＭ（random access memory）等の作業用メモリ、および通信回路等を有する。この場合、上記した各部の機能は、ＣＰＵが制御プログラムを実行することにより実現される。
【００６２】
このようなネットワーク遅延推定装置３０２は、加入ノードとの遅延測定の対象を、一巡目測定対象ノードおよび二巡目測定対象ノードのみに絞って、最適ツリーの構築を行うことができる。
【００６３】
次に、ネットワーク遅延推定装置３０２の動作について説明する。
【００６４】
図９は、ネットワーク遅延推定装置３０２の全体動作を示すフローチャートである。
【００６５】
まず、イベント検出部３０４において、メトリックツリー構築を伴うネットワークイベントが検出される（加入ノードからネットワークメッセージを受信）（Ｓ４０２）。すると、一巡目測定対象ノード選択部３０６は、現在の最適ツリーＯから、一巡目測定対象ノードＳＴ１を選択する（Ｓ４０４）。この一巡目測定対象ノードＳＴ１を選択する処理の詳細については、後述する。一巡目測定対象ノードＳＴ１が選択されると、メトリック処理部３０８は、加入ノードに対し、一巡目測定対象ノードＳＴ１のネットワークＩＤのリストを含むネットワークメッセージを送信する。これにより、メトリック処理部３０８は、加入ノードに対し、各一巡目測定対象ノードＳＴ１との間のネットワークメトリック（遅延）の測定を要求する（Ｓ４０６）。
【００６６】
図１０は、ネットワークメッセージの構成の一例を示す図である。
【００６７】
図１０に示すように、ネットワークメッセージ１５００は、ノード数１５０２と、ネットワークＩＤのリスト１５０４とを記述している。ネットワークＩＤのリスト１５０４は、選択された全ての一巡目測定対象ノードＳＴ１のネットワークＩＤのリストである。ノード数１５０２は、ネットワークＩＤのリスト１５０４が対応するノード数、つまり、リスト１５０４に記述されたネットワークＩＤの個数である。
【００６８】
図１１は、ネットワークメトリックの測定結果の構成の一例を示す図である。
【００６９】
図１１に示すように、測定結果１６００は、ノード数１６０２と、ネットワークＩＤ１６０４とそのノードについての結果１６０６とのペアとを記述している。ネットワークＩＤ１６０４は、ネットワークメッセージ１５００でリストアップされていたネットワークＩＤに対応している。
【００７０】
そして、メトリック処理部３０８により一巡目の全ての測定結果は、メトリックデータベース３２０へ格納される。そして、二巡目測定対象ノード選択部３１０は、一巡目測定対象ノードＳＴ１と現在の最適ツリーＯとを使用して、二巡目測定対象ノードＳＴ２を選択する（Ｓ４０８）。この二巡目測定対象ノードＳＴ２を選択する処理の詳細については、後述する。二巡目測定対象ノードＳＴ２のリストが得られると、メトリック処理部３０８は、二巡目測定対象ノードＳＴ２のネットワークＩＤのリストを含むネットワークメッセージを、加入ノードへ送信する。これにより、メトリック処理部３０８は、加入ノードに対して、各二巡目測定対象ノードＳＴ２との間のネットワークメトリック（遅延）の測定を要求する（Ｓ４１０）。
【００７１】
そして、メトリック処理部３０８は、二巡目の全ての測定結果をメトリックデータベース３２０に格納する。すると、最適ツリー処理部３１４は、一巡目測定対象ノードＳＴ１および二巡目測定対象ノードＳＴ２と現在の最適ツリーＯとを使用して、新たな最適ツリーＯ'を作成する（Ｓ４１２）。最適ツリーＯ'は、加入ノードを含む新たな最適ツリーである。この新たな最適ツリーＯ’を作成する処理の詳細については、後述する。そして、作成された最適ツリーＯ'が最適ツリーデータベース３２２に格納されると、配信ツリー構築部３１６は、コンテンツ配信のためのツリーを作成するために、適宜、最適ツリーＯ'を使用する（Ｓ４１４）。
【００７２】
以下、図９の各処理の詳細について説明する。
【００７３】
図１２は、図９のステップＳ４０４の、一巡目測定対象ノードを選択する処理の詳細を示すフローチャートである。
【００７４】
一巡目測定対象ノード選択部３０６は、現在の最適ツリーＯにおいて、最も距離が長い実ノードのペアを、第１の一巡目測定対象ノードＳＴ１として選択する（Ｓ５０２）。そして、一巡目測定対象ノード選択部３０６は、残っている非選択ノードＳＵを評価して、最良のノード（第１の一巡目測定対象ノードＳＴ１のペアを結ぶ経路からの距離が長いノード）ＮＢを決定する（Ｓ５０４）。これらの、第１の一巡目測定対象ノードＳＴ１を選択する処理の詳細、および、最良ノードＮＢを決定する処理の詳細については、後述する。非選択ノードとは、現在の最適ツリーＯにおける全ての実ノードＳＮから、一巡目測定対象ノードＳＴ１を除いた残りの実ノードである。
【００７５】
そして、一巡目測定対象ノード選択部３０６は、決定した最良のノードＮＢを、第２の一巡目測定対象ノードＳＴ１として選択して一巡目測定対象ノードＳＴ１のセットに追加する（Ｓ５０６）。一巡目測定対象ノード選択部３０６は、一巡目測定対象ノードＳＴ１の数が所要数に到達するまで、ステップＳ５０４、Ｓ５０６の処理を繰り返す（Ｓ５０８）。本実施の形態では、所定数は４であるため（図３（Ａ）参照）、ステップＳ５０２で第１の一巡目測定対象ノードのペアが選択され、ステップＳ５０４で第２の一巡目測定対象ノードのペアが選択されることになる。
【００７６】
図１３は、図１２のステップＳ５０２の、第１の一巡目測定対象ノードを設定する処理の詳細を示すフローチャートである。
【００７７】
一巡目測定対象ノード選択部３０６は、まず、現在の最適ツリーＯにおける全ての実ノードを、実ノードＳＮに設定する（Ｓ６０２）。そして、一巡目測定対象ノード選択部３０６は、ノード間の距離を比較するためのパラメータとして用いる最大距離Ｄｍａｘを、ゼロに初期化し（Ｓ６０４）、実ノードＳＮの全てのペアＳＮＮのセットを作成する（Ｓ６０６）。ペアＳＮＮは、実ノードＳＮと別の実ノードＳＮとの組み合わせ（ＳＮ＊ＳＮ＝｛（ａ，ｂ）｝である。未処理のペアＳＮＮが残っている間は、以下のステップＳ６１０〜Ｓ６１６の処理を繰り返す（Ｓ６０８）。
【００７８】
まず、一巡目測定対象ノード選択部３０６は、ペアＳＮＮを１つ選択し（Ｓ６１０）、選択中のペアＳＮＮのノードＡとノードＢとの間の距離Ｄを、現在の最適ツリーＯに基づいて算出する（Ｓ６１２）。そして、一巡目測定対象ノード選択部３０６は、算出した距離Ｄが最大距離Ｄｍａｘよりも大きい場合（Ｓ６１４：ＹＥＳ）、この距離Ｄを最大距離Ｄｍａｘとして記憶し、選択中のペアＳＮＮを現在の最良ノードとして記憶する（Ｓ６１６）。そして、一巡目測定対象ノード選択部３０６は、全てのペアＳＮＮについて調べた後、その時点の最良ノードを、第１の一巡目測定対象ノードＳＴ１に設定する（Ｓ６１８）。
【００７９】
図１４は、図１２のステップＳ５０４の、最良ノードを決定する処理の詳細を示すフローチャートである。
【００８０】
一巡目測定対象ノード選択部３０６は、まず、その時点の一巡目測定対象ノードＳＴ１を、初期の選択ノードＳＳとする（Ｓ７０２）。すなわち、選択ノードＳＳのセットの初期状態は、第１の一巡目測定対象ノードＳＴ１のみから成る。また、一巡目測定対象ノード選択部３０６は、ネットワークを形成するネットワークノードＳＶを、空に初期化する（Ｓ７０４）。そして、一巡目測定対象ノード選択部３０６は、次に、選択ノードＳＳのセットから任意のノードＮ０を１つ取り出し（Ｓ７０６）、未処理のノードが残っている間は、以下のステップＳ７１０、Ｓ７１２の処理を繰り返す（Ｓ７０８）。一巡目測定対象ノード選択部３０６は、選択ノードＳＳの残りである他のノードＮを１つ取り出す（Ｓ７１０）。そして、一巡目測定対象ノード選択部３０６は、現在の最適ツリーＯにおけるノードＮ０とノードＮとの間の経路を算出し、経路上の全てのノードを、ネットワークノードＳＶのセットに追加する（Ｓ７１２）。
【００８１】
そして、全ての選択ノードＳＳが処理されたら、一巡目測定対象ノード選択部３０６は、ネットワークノードＳＶのセットを使用して、非選択ノードＳＵの評価を開始する。まず、一巡目測定対象ノード選択部３０６は、実ノードＳＮのセットから全ての一巡目測定対象ノードＳＴ１を除外した残りのノードを、非選択ノードＳＵとする（Ｓ７１４）。そして、一巡目測定対象ノード選択部３０６は、未処理の非選択ノードＳＵが残っている間は、以下のステップＳ７１８〜７２２の処理を繰り返す（Ｓ７１６）。
【００８２】
一巡目測定対象ノード選択部３０６は、非選択ノードＳＵから任意のノードＮを１つ取り出し（Ｓ７１８）、現在の最適ツリーＯにおいて、ノードＮからの横型探索を、ネットワークノードＳＶのいずれかに到達するまで実行する（Ｓ７２０）。そして、一巡目測定対象ノード選択部３０６は、ノードＮと出くわしたネットワークノードＳＶのとの間の距離を、そのノードＮの指標値ｖ（Ｎ）と定義する（Ｓ７２２）。そして、一巡目測定対象ノード選択部３０６は、全てのノードＮのうち、指標値ｖ（Ｎ）が最大となるノードを、最良ノードＮＢに設定する（Ｓ７２４）。すなわち、一巡目測定対象ノード選択部３０６は、ネットワークノードＳＶのとの距離が最大となるノードであり、第１の一巡目測定対象ノードＳＴ１のペアを結ぶ経路との距離が最も長くなるノードを、最良ノードＮＢに設定する。
【００８３】
図１５は、図９のステップＳ４０８の、二巡目測定対象ノードを選択する処理の詳細を示すフローチャートである。
【００８４】
二巡目測定対象ノード選択部３１０は、まず、一巡目測定対象ノードＳＴ１を、測定対象ノードＳＴとする（Ｓ８０２）。すなわち、測定対象ノードＳＴのセットの初期状態は、第１の一巡目測定対象ノードＳＴ１のみから成る。そして、二巡目測定対象ノード選択部３１０は、候補ツリー作成部３１２を用いて、候補ツリーＳＣのセットを作成する（Ｓ８０４）。この候補ツリーＳＣのセットを作成する処理の詳細については、後述する。候補ツリーＳＣは、最適ツリーＯにおいて、測定対象ノードＳＴ（ここでは一巡目測定対象ノードＳＴ１）のペアを接続したときの、メトリックツリーである。また、候補ツリーＳＣのセットとは、全てのペアについての候補ツリーＳＣのセットある。そして、二巡目測定対象ノード選択部３１０は、候補ツリーデータベース３１８から候補ツリーＳＣのセットを取り出し、各候補ツリーＳＣを以下のように評価する。
【００８５】
まず、二巡目測定対象ノード選択部３１０は、評価ツリーＳＣ’を空に初期化する（Ｓ８０６）。そして、二巡目測定対象ノード選択部３１０は、未処理の候補ノードＳＣが残っている間は、以下のステップＳ８１０〜Ｓ８１４の処理を繰り返す（Ｓ８０８）。
【００８６】
まず、二巡目測定対象ノード選択部３１０は、候補ツリーＳＣのセットから任意の候補ツリーＴを１つ取り出す（Ｓ８１０）。そして、二巡目測定対象ノード選択部３１０は、候補ツリーＴにおける、新たな実ノード（加入ノード）と新たな仮想ノード（加入ノードの接続位置）との間の距離Ｄを求める（Ｓ８１２）。そして、二巡目測定対象ノード選択部３１０は、候補ツリーＴを評価ツリーＳＣ’のセットに追加し、求めた距離Ｄを、その候補ツリーＴの指標値ｖ（Ｔ）と定義する（Ｓ８１４）。そして、全ての評価候補ツリーＳＣを評価すると、二巡目測定対象ノード選択部３１０は、評価ツリーＳＣ’を指標値ｖ（Ｔ）の昇順にソートする（Ｓ８１６）。そして、二巡目測定対象ノード選択部３１０は、ソートされた順序に従って、評価ツリーＳＣ’のセットから、二巡目測定対象ノードＳＴ２を抽出する（Ｓ８１８）。この二巡目測定対象ノードＳＴ２を抽出する処理の詳細については、後述する。
【００８７】
図１６は、図１５のステップＳ８０４の、候補ツリーのセットを作成する処理の詳細を示すフローチャートである。
【００８８】
候補ツリー作成部３１２は、まず、測定対象ノードＳＴの中から、全ての可能なペアＳＴＴを作成し（Ｓ９０２）、２つのノードの両方が同一となっているペアをペアＳＴＴから除外する（Ｓ９０４）。そして、候補ツリー作成部３１２は、未処理のペアＳＴＴが残っている間は、以下のステップＳ９０８〜Ｓ９２２の処理を繰り返す（Ｓ９０６）。
【００８９】
まず、候補ツリー作成部３１２は、ペアＳＴＴを１つ選択し（Ｓ９０８）、現在の最適ツリーＯにおいて、選択中のペアＳＴＴのノードＡおよびノードＢのうち、ノードＡから、追加される仮想ノードまでの距離ＤＶを算出する（Ｓ９１０）。距離ＤＶは、つまり、候補ツリー作成部３１２は、加入ノードの接続位置として、当該ペアＳＴＴの間の経路上に追加される、仮想ノードの位置を示す値である。候補ツリー作成部３１２は、例えば、当該ＳＴＴの間の遅延（現在の最適ツリーＯからの推定値）とノードＡと加入ノードとの間の遅延（測定値）とを加算し、この加算値からノードＢ加入ノードとの間の遅延（測定値）を差し引く。そして、候補ツリー作成部３１２は、その差し引いた結果を２で割ることにより、距離ＤＶを算出する。
【００９０】
そして、候補ツリー作成部３１２は、現在の最適ツリーＯの複製ツリーＯ’を作成し（Ｓ９１２）、新たな仮想ノードＶを、距離ＤＶの位置で複製ツリーＯ’に追加する（Ｓ９１４）。この仮想ノードＶを追加する処理の詳細については、後述する。そして、候補ツリー作成部３１２は、加入ノードに相当する新たな実ノードＪを作成して複製ツリーＯ’に追加し（Ｓ９１６）、仮想ノードＶと実ノードＪとの間の距離を算出する（Ｓ９１８）。そして、候補ツリー作成部３１２は、算出した距離のエッジで、実ノードＪを仮想ノードＶに接続し（Ｓ９２０）、候補ツリーデータベース３１８に、候補ツリーＳＣとして、複製ツリーＯ’を追加する（Ｓ９２２）。
【００９１】
図１７は、図１６のステップＳ９１４の、仮想ノードを追加する処理の詳細を示すフローチャートである。
【００９２】
候補ツリー作成部３１２は、まず、現在のノードＣをノードＡに初期化し（Ｓ１００２）、現在の距離Ｄをゼロに初期化する（Ｓ１００４）。現在のノードＣとは、仮想ノードの位置の近傍であるか否かの判断対象となっている、複製ツリーＯ’上の仮想ノードを示す。そして、候補ツリー作成部３１２は、現在の距離Ｄが仮想ノードの位置を示す上述の距離ＤＶ未満である間は（Ｓ１００６：ＹＥＳ）、以下のステップＳ１００８〜Ｓ１０１２の処理を繰り返す。
【００９３】
まず、候補ツリー作成部３１２は、ノードＡとノードＢとの間の経路にある、現在のノードＣの直後の仮想ノードを直後ノードＣ２とする（Ｓ１００８）。そして、候補ツリー作成部３１２は、距離Ｄを、現在のノードＣと直後ノードＣ２との間の距離だけ増加させ（Ｓ１０１０）、その後、直後ノードＣ２を現在のノードＣに設定する（Ｓ１０１２）。
【００９４】
そして、現在の距離Ｄが上述の距離ＤＶ以上になると（Ｓ１００６：ＮＯ）、候補ツリー作成部３１２は、まず、ノードＡとノードＢとの間の経路にある、現在のノードＣの直前の仮想ノードを直前ノードＣ０とする（Ｓ１０１４）。そして、候補ツリー作成部３１２は、現在のノードＣと直前ノードＣ０との間の距離を距離Ｅとし（Ｓ１０１６）、現在のノードＣと直前ノードＣ０との間のエッジを除去する（Ｓ１０１８）。そして、候補ツリー作成部３１２は、新たな仮想ノードＶを作成して複製ツリーＯ’に追加する（Ｓ１０２０）。そして、候補ツリー作成部３１２は、仮想ノードＶを、現在の距離Ｄと上述の距離ＤＶとの差に相当するエッジで、現在のノードＣに接続する（Ｓ１０２２）。そして、候補ツリー作成部３１２は、距離Ｅと、仮想ノードＶと現在のノードＣとの間の距離との差に相当するエッジで、直前ノードＣ０に接続する（Ｓ１０２４）。
【００９５】
図１８は、図１５のステップＳ８１８の、二巡目測定対象ノードを抽出する処理の詳細を示すフローチャートである。
【００９６】
二巡目測定対象ノード選択部３１０は、まず、二巡目測定対象ノードＳＴ２を空に初期化する（Ｓ１１０２）。そして、二巡目測定対象ノード選択部３１０は、未処理の評価ツリーＳＣ'が残っている間は、以下のステップＳ１１０６〜Ｓ１１１４の処理を繰り返す（Ｓ１１０４）。
【００９７】
まず、二巡目測定対象ノード選択部３１０は、未処理の評価ツリーＳＣ'から、上述の指標値ｖ（Ｔ）のソートの順序に従って、候補ツリーＴを１つ取り出す（Ｓ１１０６）。そして、二巡目測定対象ノード選択部３１０は、取り出した候補ツリーＴにおいて、新たな実ノード（加入ノード）に最も近い２つの実ノードを、ノードＤおよびノードＥを決定する（Ｓ１１０８）。そして、二巡目測定対象ノード選択部３１０は、ノードＤが、一巡目測定対象ノードＳＴ１のセットおよび二巡目測定対象ノードＳＴ２のセットに含まれているか否かを判定する。二巡目測定対象ノード選択部３１０は、ノードＤがいずれにも含まれていなければ、ノードＤを、二巡目測定対象ノードＳＴ２のセットに追加する（Ｓ１１１０）。同様に、二巡目測定対象ノード選択部３１０は、ノードＥが、一巡目測定対象ノードＳＴ１のセットおよび二巡目測定対象ノードＳＴ２のセットに含まれているか否かを判定する。二巡目測定対象ノード選択部３１０は、ノードＥがいずれにも含まれていなければ、ノードＥを、二巡目測定対象ノードＳＴ２のセットに、最後の位置で追加する（Ｓ１１１２）。
【００９８】
そして、二巡目測定対象ノード選択部３１０は、二巡目測定対象ノードＳＴ２の数が所定値に到達し、十分となるまで、ステップＳ１１０６〜Ｓ１１１２の処理を繰り返す（Ｓ１１１４）。
【００９９】
図１９は、図９のステップＳ４１２の、新しい最適ツリーを作成する処理の詳細を示すフローチャートである。
【０１００】
二巡目測定対象ノード選択部３１０は、まず、一巡目測定対象ノードＳＴ１および二巡目測定対象ノードＳＴ２の両方を、現在の測定対象ノードＳＴに設定する（Ｓ１２０２）。そして、二巡目測定対象ノード選択部３１０は、候補ツリー作成部３１２を用いて、現在の測定対象ノードＳＴおよび現在の最適ツリーＯに基づいて候補ツリーＳＣを作成し（Ｓ１２０４）、評価ツリーＳＣ’を空に初期化する（Ｓ１２０６）。そして、二巡目測定対象ノード選択部３１０は、未処理の候補ノードＳＣが残っている間は、以下のステップＳ１２１０〜Ｓ１２１４の処理を繰り返す（Ｓ１２０８）。
【０１０１】
まず、二巡目測定対象ノード選択部３１０は、候補ツリーＳＣのセットから任意の候補ツリーＴを１つ取り出す（Ｓ１２１０）。そして、二巡目測定対象ノード選択部３１０は、一巡目測定対象ノードＳＴ１を使用して、その時点の累積誤差Ｅを算出し、新たな実ノードに対する候補ツリーＴの相対誤差に設定する（Ｓ１２１２）。この累積誤差Ｅを算出する処理の詳細については、後述する。そして、二巡目測定対象ノード選択部３１０は、候補ツリーＴを評価ツリーＳＣ’のセットに追加し、求めた累積誤差Ｅを、その候補ツリーＴの指標値ｖ（Ｔ）と定義する（Ｓ１２１４）。
【０１０２】
そして、全ての候補ツリーＳＣが処理されると、最適ツリー処理部３１４は、全ての候補ツリーＳＣのうち、指標値ｖ（Ｔ）が最小となる候補ツリーＳＣを、新たな最適ツリーＯ’に決定する（Ｓ１２１６）。なお、指標値ｖ（Ｔ）が最小となる候補ツリーＳＣとは、つまり、相対誤差が最小となる候補ツリーＳＣのことである。
【０１０３】
図２０は、図１９のステップＳ１２１２の、累積誤差を算出する処理の詳細を示すフローチャートである。
【０１０４】
二巡目測定対象ノード選択部３１０は、まず、累積誤差Ｅをゼロに初期化し（Ｓ１３０２）、測定対象ノードＳＴを、選択ノードＳＳとする（Ｓ１３０４）。そして、二巡目測定対象ノード選択部３１０は、未処理の選択ノードＳＳが残っている間は、以下のステップＳ１３０８〜Ｓ１３１６の処理を繰り返す。
【０１０５】
まず、二巡目測定対象ノード選択部３１０は、選択ノードＳＳのセットから任意のノードＮを１つ取り出し（Ｓ１３０８）、候補ツリーＴにおいて、ノードＮと新たな実ノード（加入ノード）との間との距離Ｄを算出する（Ｓ１３１０）。そして、二巡目測定対象ノード選択部３１０は、ノードＮと新たな実ノード（加入ノード）との間の実際の遅延測定値（ネットワークメトリック）Ｍを、メトリックデータベース３２０から取得する（Ｓ１３１２）。そして、二巡目測定対象ノード選択部３１０は、距離Ｄと遅延測定値Ｍとの差の絶対値を遅延測定値Ｍで割った値を、相対誤差Ｒとして算出する（Ｓ１３１４）し、累積誤差Ｅを、算出した相対誤差Ｒだけ増加させる（Ｓ１３１６）。
【０１０６】
上記により、ネットワーク遅延推定装置３０２は、一巡目測定対象ノードＳＴ１および二巡目測定対象ノードＳＴ２を選択し、これらと現在の最適ツリーＯとに基づいて、加入ノードを追加した新たな最適ツリーＯ’を作成することができる。
【０１０７】
以上のように、本実施の形態に係るネットワーク遅延推定装置３０２は、測定対象の入念なノードサンプリングを行う。すなわち、ネットワーク遅延推定装置３０２は、加入ノードからの距離測定となる実ノードを、一巡目測定対象ノードおよび二巡目測定対象ノードとして選択する。一巡目測定対象ノードは、現在の最適ツリーにおいて最も経路が長い、つまり最も外側に位置する実ノードのペアを含む。二巡目測定対象ノードは、一巡目測定対象ノードのペアを結ぶ経路において、加入ノードからの距離が近い実ノードである。これにより、ネットワーク遅延推定装置３０２は、加入ノードに近いノードを高精度に推定することができる。
【０１０８】
また、ネットワーク遅延推定装置３０２は、一巡目測定対象ノードおよび二巡目測定対象ノードのみに絞って遅延測定を行い、現在の最適ツリーに測定結果を追加する形で、新たな最適ツリーを作成する。これにより、ネットワーク遅延推定装置３０２は、精度の高い新たな最適ツリー（メトリックツリー）を、短時間で作成することができる。
【０１０９】
例えば、端末中継型マルチポイント通信の配送木の計算の前工程として、このようなメトリックツリーの作成を行えば、より少ない待ち時間で、配送木の計算に必要な情報を得ることができ、結果として、通信を短時間で開始することができる。また、ネットワーク遅延推定装置３０２は、この処理を繰り返すことにより、ネットワーク全体について、遅延実測値との誤差が少ないメトリックツリーを構成することが可能となる。
【０１１０】
なお、本実施の形態のネットワーク遅延推定装置３０２は、一巡目測定対象ノードの追加を２段階で行うことにより計測誤差の削減を図ったが、１段階の追加に止めても良いし、３段階の追加を行なってもよい。例えば、ネットワーク遅延推定装置３０２は、３段階目では、上述の第１の一巡目測定対象ノードおよび第２の一巡目測定対象ノードのそれぞれからの距離が最も離れている実ノードを選定し、追加してもよい。
【産業上の利用可能性】
【０１１１】
本発明に係るネットワーク遅延推定装置およびネットワーク遅延推定方法は、メトリックツリーを高精度にかつ短時間で作成することができるネットワーク遅延推定装置およびネットワーク遅延推定方法として有用である。すなわち、本発明は、ネットワークメトリックの取得を必要とする各種用途に適する。
【符号の説明】
【０１１２】
１００  ネットワークシステム
１０２〜１１４  ノード
１１６  ネットワーク
２００  最適ツリー
２０２〜２１４  実ノード
２１６〜２２４  仮想ノード
２２６〜２４６  重み付きエッジ
３０２  ネットワーク遅延推定装置
３０４  イベント検出部
３０６  一巡目測定対象ノード選択部
３０８  メトリック処理部
３１０  二巡目測定対象ノード選択部
３１２  候補ツリー作成部
３１４  最適ツリー処理部
３１６  配信ツリー構築部
３１８  候補ツリーデータベース
３２０  メトリックデータベース
３２２  最適ツリーデータベース
【図１】
0005473827.tif 000002
【図２】
0005473827.tif 000003
【図３】
0005473827.tif 000004
【図４】
0005473827.tif 000005
【図５】
0005473827.tif 000006
【図６】
0005473827.tif 000007
【図７】
0005473827.tif 000008
【図８】
0005473827.tif 000009
【図９】
0005473827.tif 000010
【図１０】
0005473827.tif 000011
【図１１】
0005473827.tif 000012
【図１２】
0005473827.tif 000013
【図１３】
0005473827.tif 000014
【図１４】
0005473827.tif 000015
【図１５】
0005473827.tif 000016
【図１６】
0005473827.tif 000017
【図１７】
0005473827.tif 000018
【図１８】
0005473827.tif 000019
【図１９】
0005473827.tif 000020
【図２０】
0005473827.tif 000021