JP2006246205A - オーバレイネットワーク対応ルーチング方法およびオーバレイノード - Google Patents

Abstract

【課題】インターネット規模のスケーラビリティを備え、かつ、ＱｏＳの実現が可能なオーバレイネットワーク対応ルーチング方法およびこのようなルーチングを行うオーバレイノードを提供する。
【解決手段】オーバレイノードごとに、隣接する少なくとも一つのオーバレイノードとの間のリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定し、受信したパスメッセージに該当するリンクについて測定された特性を示すＱｏＳ情報を付加したパス情報を蓄積し、受信したパスメッセージで示される利用者端末を起点とするパスの中から、対応するパス情報に含まれるＱｏＳ情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択し、選択されたパスのパス情報を含む新たなパスメッセージを隣接するオーバレイノードに中継する。
【選択図】 図１

Description

本発明は、オーバレイネットワーク対応ルーチング方法およびこのルーチング方法を適用したオーバレイノードに関し、特に、ルーチング対象のパスによって最終的に接続される利用者に提供されるサービス品質(ＱｏＳ：Quality of Service)を、パスを選択する際の基準の一つとして考慮するための技術に関する。
オーバレイネットワークは、ＩＰレイヤの上位に位置する論理的なネットワークであり、このオーバレイネットワークの考え方は、例えば、複数のインターネットサービスプロバイダにまたがる情報流通経路(パス)を設定し、また、管理するための仕組みとして利用されている。

一方、高速なアクセス回線の普及に伴い、利用者は、ＶｏＩＰや映像などのストリーミング配信のように、より、高いＱｏＳが要求されるサービスの提供を求めるようになってきている。
このため、オーバレイネットワークにおけるルーチングにおいても、ＱｏＳを考慮したパスの選択を実現する技術が求められている。

個々のインターネットサービスプロバイダ（ＩＳＰ）によって提供される自律的なネットワークシステム(Autonomous System以下、ＡＳと略称する)内部では、主として、ＯＳＰＦ（Open Shortest Path First）ルーチングが採用されている。
このＯＳＰＦルーチングでは、各ノードが、ＡＳ内に存在する全てのノードに自身の隣接ノードとこれらの隣接ノードに対応するコスト情報を伝えることにより、ＡＳにおける全てのノードに関するリンクの状態を収集し、それぞれのノードにおいて、自身を基点とする経路のコストを計算している(非特許文献１、３参照)。

ＯＳＰＦルーチングでは、各ノードにおいて、ＡＳの全体構成が把握されているので、例えば、コスト情報にＱｏＳにかかわる情報を含めることにより、ＱｏＳを考慮したルーチングを実現することができる。
一方、自律的なネットワークシステムをまたがるパスのルーチングのためのゲートウェイ外プロトコルとしては、ＢＧＰ(Border Gateway Protocol)が事実上の標準プロトコルとなっている(非特許文献２参照)。

このＢＧＰルーチングでは、最終目的地からパスメッセージを通信方向とは逆方向に伝播させ、そのパスメッセージが通過したノードを記録しながら経路を構成する手法を採用している。つまり、ＢＧＰルーチングを行うノード(以下、ＢＧＰノードと称する)は、使われた正確な経路の軌跡を保存し、この経路の軌跡に関する情報を隣接するノードに知らせている(非特許文献３参照)。

例えば、図６に示したように、互いに異なるＩＳＰによってサービスが提供されているＡＳ１〜ＡＳｎにそれぞれ備えられたＢＧＰノードＮ１〜Ｎｎは、それぞれが起動されたときなどに、後述するようなパスメッセージを隣接している全てのＢＧＰノードに配布する。
なお、図６においては、ＢＧＰノードＮ１についてのみ詳細構成を示したが、全てのＢＧＰノードＮ１〜Ｎｎの構成は当然ながら同等である。

ＢＧＰノードＮ１において、ユーザ管理部４１１は、自身をゲートウェイとして利用する利用者のＩＰアドレスの集合Ｐ（prefix1,prefix2,…）を保持するとともに、新たなユーザの起動などに応じて、上述した集合Ｐの更新などを行う。また、ＢＧＰノードＮ１において、ＴＣＰセッション管理部４１２は、予め、セッションの設定が可能なＢＧＰノード(隣接するＢＧＰノード)についてセッションの設定に必要な情報を保持している。この情報が、ＴＣＰ通信処理部４１３によるセッション設定処理に供される。

ＢＧＰノードＮ１に備えられたパス構成部４１４は、まず、上述した集合Ｐに含まれる各要素と自身のＩＰアドレス(Ｎ１)とを用いて、ＢＧＰノード１から各利用者(例えば、prefix1で示される利用者)までの経路を示すパス情報を作成し、このパス情報を含むパスメッセージ(prefix1、Ｎ１)を、ＴＣＰ通信処理部４１３を介して、このパスメッセージを隣接するＢＧＰノード(例えば、ＢＧＰノードＮ２)に配布する。また、上述したパス情報は、パス情報管理部４１６を介してパス情報データベース４１７に登録されて保持される。

一方、隣接するＢＧＰノード(例えば、ＢＧＰノードＮ１)からパスメッセージを受け取ったときに、ＢＧＰノードＮ２に備えられたパス構成部４１４は、パス情報データベース４１７に保持されたパス情報と自身のＩＰアドレス(Ｎ２)とに基づいて適切なパス情報を作成し、このパス情報を含むパスメッセージ(prefix1、Ｎ１、Ｎ２)を、ＴＣＰ通信処理部４１３を介して、隣接するＢＧＰノード(例えば、ＢＧＰノードＮ３)に配布する。このように、パスメッセージを中継する際に、パス選択部４１５は、同一のＩＰアドレスに向かうパスの中で最もホップ数が少なく、かつ、最も早くパス情報データベース４１７に登録されたパス情報を選択し、このパス情報をパス構成部４１４の処理に供する。また、このとき、パス選択部４１５により、このパスメッセージの契機となったパスメッセージの送信元であるＢＧＰノードＮ１を送信先から除外する制御がＴＣＰ通信処理部４１３に対して行われる。

このようにして順次にパスメッセージを伝播していき、上述した送信先の限定の過程において、パス選択部４１５により、パスメッセージの配布先がなくなったこと、あるいは、パスメッセージによって示される経路にループがあることが検出されたときに、パスメッセージの配布が終了される。
また、上述したパスメッセージの配布は、上述した集合Ｐに新たな利用者が追加された場合などにも行われる。

このように、ＢＧＰルーチングでは、隣接ノードに伝えられる情報は、正確な経路の軌跡に限られており、候補となるパスそれぞれにおいて期待できるＱｏＳにかかわらず、軌跡として残されたノードの数、すなわち、ホップ数に基づいてパスの選択が行われる。
その一方、上述したように、ＢＧＰルーチングでは、パスメッセージを伝播させていく過程において、隣接するノードに渡すパス情報の取捨選択を行うことにより、経路計算を分散して処理しているので、大規模なネットワークにおいても十分に適用可能である。
「ＯＳＰＦ」、John T. Moy, Adduson-Wesley(1998年２月) 「ＢＧＰ４」，John W. Stewart, Adduson-Wesley(1998年12月) 『コンピュータネットワーク第４版−５．６インターネットにおけるネットワーク層』、Ａ．Ｓ．タネンバウム著、日経ＢＰ社、２００３年１２月１５日初版発行 木村卓巳、内田真人、川原亮一、亀井聡、森達哉、能上慎也、阿部威郎、「オーバレイネットワークによるトラヒック制御の提案」、電子情報通信学会 情報ネットワーク研究会（２００４年７月） 木村卓巳、内田真人、川原亮一、亀井聡、森達哉、能上慎也、阿部威郎、「オーバレイネットワークによるトラヒック制御」、電子情報通信学会 ソサエティ大会（２００４年９月） 木村卓巳、内田真人、川原亮一、亀井聡、森達哉、能上慎也、阿部威郎、「オーバレイネットワークにおけるＱｏＳルーチング制御に関する考察」、電子情報通信学会 ソサエティ大会（２００４年９月） 熊谷和則、住田修一、阿部威郎、「非構造化オーバレイネットワークのための分散トポロジ制御法の検討」、電子情報通信学会 情報ネットワーク研究会（２００４年２月）

従来のＡＳ間ルーチングでは、個々のＡＳで適用されるルーチングプロトコルに大幅な自由度を与えつつインターネット規模での接続性を確保するとともに、ＡＳ間のピアリングポリシーを適用する際の容易性を保証するために、ＡＳ間ルーチングでは最小限度の情報であるホップ数を基準としており、ＱｏＳについては全く考慮されていなかった。
このため、上述したようなＡＳ間ルーチング技術では、ＡＳをまたがるパスのエンドツーエンドでは、ＶｏＩＰや映像のストリーミング配信などのサービスを提供するに足るＱｏＳを保証すること事実上できなかった。

一方、例えば、ＢＧＰノード間でやり取りされるパスメッセージにＱｏＳに関する情報を付加することによってＢＧＰを単純に拡張する方法は、多数のＩＳＰがそれぞれに多種多様なサービスを利用者に提供している現実を考えれば到底実現できないと考えられる。なぜなら、上述したようなＢＧＰルーチングの拡張をＩＰレイヤにおいて実現するためには、全てのＡＳに備えら得たＢＧＰノードを一斉に上述したＱｏＳに関する拡張に対応させなければならないからである。

そこで、本出願人は、個々のＩＳＰによって管理されるＩＰレイヤの自律的なネットワークシステムの上位レイヤに位置するオーバレイネットワーク上でルーチングを行うことにより、多様なサービスの提供が可能なレベルのＱｏＳを実現する手法を確立すべく、オーバレイネットワークにおけるルーチング技術に必要な前提条件を整理し、得られた成果を発表している(非特許文献４、５、６参照)。また、本出願人は、複数のＡＳにまたがるエンドツーエンドにおいてＱｏＳを保証する技術を提供するために確立すべきもう一つの鍵となる要素技術として、オーバレイネットワークのトポロジ制御に関する技術を提案している(非特許文献７参照)。

非特許文献４、５、６における検討の結果として、第１に、多数の代替経路を確保するために、膨大な数のオーバレイノードがインターネット規模で分散して配置されることから、オーバレイネットワークにおけるルーチングでは、経路の管理や経路計算を分散して行う必要があることが示されている。また、第２に、個々のＩＳＰが管理運用しているＩＰネットワークにおけるＱｏＳに関する情報を、各ＡＳに属するノードからの報告などによって直接把握することは期待できないことから、オーバレイネットワークにおいて設定する個々の経路に関するＱｏＳをＩＰレイヤにおいて実現されている機能に依存することなく取得する必要があることが示されている。

本発明は、インターネット規模のスケーラビリティを備え、かつ、ＱｏＳの実現が可能なオーバレイネットワーク対応ルーチング方法およびこのようなルーチングを行うオーバレイノードを提供することを目的とする。

本発明にかかわる第１のオーバレイネットワーク対応ルーチング方法は、作成ステップと、送信ステップと、測定ステップと、蓄積ステップと、検索ステップと、選択ステップと、中継ステップとから構成され、選択ステップに、ＱｏＳ算出ステップを備えて構成される。
本発明にかかわる第１のオーバレイネットワーク対応ルーチング方法の原理は、以下の通りである。

ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成し、隣接するオーバレイノードとの間にピアセッションを設定するオーバレイノードで用いられるオーバレイネットワーク対応ルーチング方法において、作成ステップは、オーバレイネットワークを構成するオーバレイノードそれぞれの起動あるいはオーバレイノードに収容される利用者端末の起動あるいは追加に応じて、オーバレイノードに収容される利用者端末とオーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成する。送信ステップは、作成されたパスメッセージを隣接するオーバレイノードとの間に設定されたリンクを介して送信する。測定ステップは、オーバレイノードごとに、隣接する少なくとも一つのオーバレイノードとの間のリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する。蓄積ステップは、パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加するとともに、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報を付加することにより、パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成し、このパス情報を蓄積する。検索ステップは、パスメッセージの受信に応じて、それまでに蓄積したパス情報の中から、受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する。選択ステップは、検索されたパスメッセージそれぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する。中継ステップは、選択されたパスのパス情報を含む新たなパスメッセージを送信元のオーバレイノードを除く隣接するオーバレイノードに中継する。また、上述した選択ステップにおいて、ＱｏＳ算出ステップは、検索されたパス情報それぞれに含まれる情報と、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出する。

このように構成された第１のオーバレイネットワーク対応ルーチング方法の動作は、下記の通りである。
図１に、本発明にかかわるオーバレイネットワーク対応ルーチング方法の原理説明図を示す。
例えば、図１(ａ)に示すオーバレイノードＮ１の起動に応じて、作成ステップにより、このオーバレイノードＮ１に収容される利用者端末Ｐ₁₁、Ｐ₁₂、Ｐ₁₃それぞれについて、このオーバレイノードＮ１までの経路を示すノードリスト（Ｐ_1i，Ｎ１）（ｉ＝１〜３）を含むパスメッセージが作成される。このようにして作成されたパスメッセージは、送信ステップにおいて、隣接する別のオーバレイノード(例えば、オーバレイノードＮ２)に送信され、このパスメッセージの受信を契機として、転送先のオーバレイノード(例えば、オーバレイノードＮ２)では、パス情報の収集およびパスメッセージの中継が行われる。

ここで、各オーバレイノードでは、例えば、測定ステップを一定時間ごとに実行することにより、隣接するオーバレイノードとの間に設定されたリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳ情報が測定されており、この測定結果が、上述したパスメッセージの受信を契機とするパス情報の収集およびパスメッセージの中継に利用される。

まず、蓄積ステップでは、受信したパスメッセージに含まれるノードリスト(例えば、Ｐ₁₁、Ｎ１)に自身を示す情報(例えば、Ｎ２)を付加するとともに、このパスメッセージの送信元のオーバレイノード(例えば、オーバレイノードＮ１)との間のリンクについて測定されたＱｏＳ情報ＱｏＳ₁₂を付加することにより、利用者端末Ｐ₁₁からオーバレイノードＮ２までの経路に関するパス情報(例えば、Ｐ₁₁、Ｎ１、Ｎ２、ＱｏＳ₁₂)が形成され、このパス情報が例えばパス情報データベースに蓄積される。次に、検索ステップにより、それまでに蓄積されたパス情報の中から、受信したパスメッセージで示された利用者端末(例えば、利用者端末Ｐ₁₁)を経路の基点とするノードリストを含むものが検索され、これらのパス情報が選択ステップによる処理に供される。この選択ステップでは、ＱｏＳ算出ステップにより、検索されたパス情報に含まれるＱｏＳ情報に基づいて、例えば、期待できる遅延時間、期待できるパケット損失率および期待できる可用帯域がそれぞれ算出され、これらの算出結果に基づいて、これらのパスの中から最も高いＱｏＳの実現が期待できるパスが利用するパスとして選択される。このようにして選択されたパスのパス情報は、中継ステップにより、隣接するオーバレイノードに中継される。

例えば、図１(ａ)に示したオーバレイノードＮ４にオーバレイノードＮ２からのパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ２、ＱｏＳ₁₂)が到達したときに、既に、オーバレイノードＮ３からのパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ３、ＱｏＳ₁₃)が到達していれば、これらのパスメッセージに含まれたＱｏＳ情報に基づいて、より高いＱｏＳを実現可能なパスが選択され、このパスに対応するパス情報に基づいて編成されたパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ３、Ｎ４、ＱｏＳ₁₃、ＱｏＳ₃₄)が、中継ステップにより、隣接するオーバレイノードＮ５に中継される。

このようにして、各オーバレイノードにおいて測定されたＱｏＳ情報を含むパスメッセージを伝播させていくことにより、オーバレイネットワークを構成する各オーバレイノードにおいて、ＱｏＳを考慮したルーチングを実現することができる。
本発明にかかわる第２のオーバレイネットワーク対応ルーチング方法は、作成ステップと、送信ステップと、測定ステップと、ＱｏＳ算出ステップと、蓄積ステップと、検索ステップと、選択ステップと、中継ステップとから構成される。

本発明にかかわる第２のオーバレイネットワーク対応ルーチング方法の原理は、以下の通りである。
ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成し、隣接するオーバレイノードとの間にピアセッションを設定するオーバレイノードで用いられるオーバレイネットワーク対応ルーチング方法において、作成ステップは、オーバレイネットワークを構成するオーバレイノードそれぞれの起動あるいはオーバレイノードに収容される利用者端末の起動あるいは追加に応じて、オーバレイノードに収容される利用者端末とオーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成する。送信ステップは、作成されたパスメッセージを隣接するオーバレイノードとの間に設定されたリンクを介して送信する。測定ステップは、オーバレイノードごとに、隣接する少なくとも一つのオーバレイノードとの間のリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する。ＱｏＳ算出ステップは、パスメッセージの受信に応じて、受信したパスメッセージに含まれる情報と、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出する。蓄積ステップは、パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、ＱｏＳ算出ステップによって得られたＱｏＳ情報とからパス情報を形成し、このパス情報を蓄積する。検索ステップは、パスメッセージの受信に応じて、それまでに蓄積したパス情報の中から、受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する。選択ステップは、検索されたパス情報それぞれに含まれるＱｏＳ情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する。中継ステップは、選択されたパスのパス情報を含む新たなパスメッセージを送信元のオーバレイノードを除く隣接するオーバレイノードに中継する。

このように構成された第２のオーバレイネットワーク対応ルーチング方法の動作は、下記の通りである。
このルーチング方法では、パス情報を選択する段階において各パス情報に含まれるＱｏＳ情報からそのパスにおいて期待できるＱｏＳにかかわる特性を算出する代わりに、蓄積ステップでパス情報を形成するのに先立って、ＱｏＳ算出ステップを実行し、それぞれのパスにおいて期待できる遅延時間やパケット損失率および可用帯域を求めている。

したがって、図１(ｂ)に示すように、オーバレイノードＮ４からオーバレイノードＮ５に転送されるパスメッセージには、例えば、オーバレイノードＮ１、Ｎ３間のＱｏＳにかかわるＱｏＳ情報ＱｏＳ₁₃とオーバレイノードＮ３、Ｎ４間のＱｏＳにかかわるＱｏＳ情報ＱｏＳ₃₄とから求められたＱｏＳ情報、すなわち、ノードリスト(Ｎ１，Ｎ３，Ｎ４)に対応するＱｏＳ情報を集約したＱｏＳ情報ＱｏＳ_1-3-4が含まれている。このようにして、集約されたＱｏＳ情報を含むパスメッセージを中継する構成とすることにより、各パスに対応して蓄積されるパス情報の情報量を低減するとともに、パスメッセージによって伝送される情報量を大幅に低減することが可能である。

本発明にかかわる第１のオーバレイノードは、作成手段と、測定手段と、形成手段と、パス情報データベースと、検索手段と、選択手段と、中継手段とから構成され、選択手段にＱｏＳ算出手段を備える。
本発明にかかわる第１のオーバレイノードの原理は、以下の通りである。
ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成するオーバレイノードであって、隣接するオーバレイノードとの間に設定したピアセッションを介して情報のやり取りを行うピア間通信手段を有し、少なくとも一つの利用者端末を収容するオーバレイノードにおいて、作成手段は、オーバレイノードの起動あるいはオーバレイノードに収容される利用者端末の起動あるいは追加に応じて、利用者端末とオーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成し、ピア間通信手段を介して隣接するオーバレイノードに送出する。測定手段は、ピア間通信手段によって設定された各リンクについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する。形成手段は、パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とから、パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成する。パス情報データベースは、形成されたパス情報を順次に蓄積する。検索手段は、パスメッセージの受信に応じて、それまでにパス情報データベースに蓄積されたパス情報の中から、受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する。選択手段は、検索されたパス情報それぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する。中継手段は、ピア間通信手段を介して、選択されたパスのパス情報を含む新たなパスメッセージを送信元のオーバレイノードを除く隣接するオーバレイノードに中継する。また、上述した選択手段において、ＱｏＳ算出手段は、検索されたパス情報それぞれに含まれる情報と、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出する。

このように構成された第１のオーバレイノードの動作は、下記の通りである。
例えば、図１(ａ)に示すオーバレイノードＮ１の起動に応じて、このオーバレイノードＮ１に備えられた作成手段により、このオーバレイノードＮ１に収容されている利用者端末Ｐ₁₁、Ｐ₁₂、Ｐ₁₃それぞれについて、このオーバレイノードＮ１までの経路を示すノードリスト（Ｐ_1i，Ｎ１）（ｉ＝１〜３）を含むパスメッセージが作成される。このようにして作成されたパスメッセージは、ピア間通信手段の機能を利用して、隣接する別のオーバレイノード(例えば、オーバレイノードＮ２)に送信され、このパスメッセージの受信を契機として、転送先のオーバレイノード(例えば、オーバレイノードＮ２)では、パス情報の収集およびパスメッセージの中継が行われる。

ここで、各オーバレイノードでは、例えば、一定時間ごとに、測定手段により、隣接するオーバレイノードとの間に設定された各リンクについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳ情報が測定されており、この測定結果が、上述したパスメッセージの受信を契機とするパス情報の収集およびパスメッセージの中継に利用される。
まず、形成手段は、受信したパスメッセージに含まれるノードリスト(例えば、Ｐ₁₁、Ｎ１)に自身を示す情報(例えば、Ｎ２)を付加して得られたノードリストと、このパスメッセージの送信元のオーバレイノード(例えば、オーバレイノードＮ１)との間のリンクについて測定されたＱｏＳ情報ＱｏＳ₁₂とから、利用者端末Ｐ₁₁からオーバレイノードＮ２までの経路に関するパス情報(例えば、Ｐ₁₁、Ｎ１、Ｎ２、ＱｏＳ₁₂)を形成して、パス情報データベースに蓄積する。このようにしてパス情報が蓄積されたパス情報データベースから、検索手段により、受信したパスメッセージで示された利用者端末(例えば、利用者端末Ｐ₁₁)を経路の基点とするノードリストを含むものが検索され、これらのパス情報が選択手段による処理に供される。この選択手段に備えられたＱｏＳ算出手段により、検索されたパス情報に含まれるＱｏＳ情報に基づいて、例えば、期待できる遅延時間、期待できるパケット損失率および期待できる可用帯域がそれぞれ算出され、これらの算出結果に基づいて、これらのパスの中から最も高いＱｏＳの実現が期待できるパスが利用するパスとして選択される。このようにして選択されたパスのパス情報を含むパスメッセージが、中継手段により、この中継処理の契機となったパスメッセージの送信元(例えば、オーバレイノードＮ１)を除く隣接するオーバレイノードに中継される。

例えば、図１(ａ)に示したオーバレイノードＮ４にオーバレイノードＮ２からのパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ２、ＱｏＳ₁₂)が到達したときに、既に、オーバレイノードＮ３からのパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ３、ＱｏＳ₁₃)が到達していれば、これらのパスメッセージに含まれたＱｏＳ情報に基づいて、より高いＱｏＳを実現可能なパスが選択され、このパスに対応するパス情報に基づいて編成されたパスメッセージ(Ｐ₁₁、Ｎ１、Ｎ３、Ｎ４、ＱｏＳ₁₃、ＱｏＳ₃₄)が、中継ステップにより、隣接するオーバレイノードＮ５に中継される。

このようにして、各オーバレイノードに備えられた測定手段によって測定されたＱｏＳ情報を含むパスメッセージを伝播させていくことにより、各オーバレイノードがＩＰレイヤにおいてＱｏＳ情報を収集する機能を備えているか否かにかかわらず、オーバレイネットワークを構成する各オーバレイノードにおいて、ＱｏＳを考慮したルーチングを実現することができる。

本発明にかかわる第２のオーバレイノードは、上述した第１のオーバレイノードに備えられた測定手段にＱｏＳ情報保持手段を備えて構成される。
本発明にかかわる第２のオーバレイノードの原理は、以下の通りである。
上述した第１のオーバレイノードに備えられた測定手段において、ＱｏＳ情報保持手段は、ピア間通信手段によって設定されるピアセッションのうち、ＩＰレイヤにおいて確定されたＱｏＳ情報が得られたリンクに対応して、上述した確定したＱｏＳ情報を保持し、リンクに対応する測定によって得られたＱｏＳ情報として出力する。

このように構成された第２のオーバレイノードの動作は、下記の通りである。
例えば、図１(ａ)に示したオーバレイノードＮ２において、例えば、ＤｉｆｆＳｅｒｖなどのＩＰレイヤで提供される技術によってオーバレイノードＮ１との間のリンクについて確定したＱｏＳ情報が得られている場合に、ＱｏＳ情報保持手段は、ＩＰレイヤにおいて得られた確定したＱｏＳ情報を受け取って保持する。そして、このＱｏＳ情報が、上述したリンクについての測定結果として、形成手段によるパス情報の形成処理に供される。

つまり、オーバレイネットワークにおいて設定されるリンクについての測定は省略され、測定手段によって測定される特性値を含むＱｏＳ情報の代わりに、ＩＰレイヤの機能によって得られたＱｏＳ情報が該当するリンクに関するＱｏＳ情報として利用される。
本発明にかかわる第３のオーバレイノードは、上述した第１のオーバレイノードに備えられた作成手段に、利用者情報保持手段と、結合手段とを備えて構成される。

本発明にかかわる第３のオーバレイノードの原理は、以下の通りである。
上述した第１のオーバレイノードに備えられた作成手段において、利用者情報保持手段は、収容している利用者端末それぞれに対応するＱｏＳ情報を保持する。結合手段は、起点となる利用者端末と自身とを示す情報を含むノードリストと、利用者端末に対応して利用者情報保持手段に保持されたＱｏＳ情報とを結合してパスメッセージを作成する。

このように構成された第３のオーバレイノードの動作は、下記の通りである。
例えば、図１(ａ)に示したオーバレイノードＮ１に備えられた利用者情報保持手段には、利用者端末Ｐ₁₁、Ｐ₁₂、Ｐ₁₃に対応して、これらの利用者端末までの経路について得られているＱｏＳ情報ＱｏＳ_p1i(ｉ＝１〜３)が保持されている。そして、例えば、利用者端末Ｐ₁₃の起動を契機として、パスメッセージを作成する際に、結合手段により、この利用者端末Ｐ₁₃とオーバレイノードＮ１とを示す情報を含んだノードリストと上述したＱｏＳ情報ＱｏＳ_p13とが結合されて、パスメッセージが形成される。

このようにして形成されたパスメッセージを伝播させることにより、起点となる利用者端末とこれを収容するオーバレイノードとの間のＱｏＳとオーバレイネットワーク内のパスにかかわるＱｏＳとを合わせて考慮して、適切なルーチングを行うことができる。
本発明にかかわる第４のオーバレイノードは、作成手段と、測定手段と、ＱｏＳ算出手段と、形成手段と、パス情報データベースと、検索手段と、選択手段と、中継手段とから構成される。

本発明にかかわる第４のオーバレイノードの原理は、以下の通りである。
ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成するオーバレイノードであって、隣接するオーバレイノードとの間に設定したピアセッションを介して情報のやり取りを行うピア間通信手段を有し、少なくとも一つの利用者端末を収容するオーバレイノードにおいて、作成手段は、オーバレイノードの起動あるいはオーバレイノードに収容される利用者端末の起動あるいは追加に応じて、利用者端末とオーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成し、ピア間通信手段を介して隣接するオーバレイノードに送出する。測定手段は、ピア間通信手段によって設定された各リンクについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する。ＱｏＳ算出手段は、パスメッセージの受信に応じて、このパスメッセージに含まれる情報と、パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出する。形成手段は、パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、ＱｏＳ算出手段によって算出されたＱｏＳ情報とから、パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成する。パス情報データベースは、形成されたパス情報を順次に蓄積する。検索手段は、パスメッセージの受信に応じて、それまでにパス情報データベースに蓄積されたパス情報の中から、受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する。選択手段は、検索されたパス情報それぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する。中継手段は、ピア間通信手段を介して、選択されたパスのパス情報を含む新たなパスメッセージを送信元のオーバレイノードを除く隣接するオーバレイノードに中継する。

このように構成された第４のオーバレイノードの動作は、下記の通りである。
このルーチング方法では、パス情報を選択する段階において各パス情報に含まれるＱｏＳ情報からそのパスにおいて期待できるＱｏＳにかかわる特性を算出する代わりに、形成手段でパス情報を形成するのに先立って、ＱｏＳ算出手段により、受信したパスメッセージに示されたパスにおいて期待できる遅延時間やパケット損失率および可用帯域を求めている。

したがって、図１(ｂ)に示すように、オーバレイノードＮ４からオーバレイノードＮ５に転送されるパスメッセージには、例えば、オーバレイノードＮ１、Ｎ３間のＱｏＳにかかわるＱｏＳ情報ＱｏＳ₁₃とオーバレイノードＮ３、Ｎ４間のＱｏＳにかかわるＱｏＳ情報ＱｏＳ₃₄とから求められたＱｏＳ情報、すなわち、ノードリスト(Ｎ１，Ｎ３，Ｎ４)に対応するＱｏＳ情報を集約したＱｏＳ情報ＱｏＳ_1-3-4が含まれている。このようにして、集約されたＱｏＳ情報を含むパスメッセージを中継する構成とすることにより、各パスに対応して蓄積されるパス情報の情報量を低減するとともに、パスメッセージによって伝送される情報量を大幅に低減することが可能である。

本発明にかかわる第５のオーバレイノードは、上述した第４のオーバレイノードに備えられた測定手段に、ＱｏＳ情報保持手段を備えて構成される。
本発明にかかわる第５のオーバレイノードの原理は、以下の通りである。
上述した第４のオーバレイノードに備えられた測定手段において、ＱｏＳ情報保持手段は、ピア間通信手段によって設定されるリンクのうち、ＩＰレイヤにおいて確定したＱｏＳ情報が得られたリンクに対応して、上述した確定したＱｏＳ情報を保持し、リンクに対応する測定によって得られたＱｏＳ情報として出力する。

このように構成された第５のオーバレイノードの動作は、下記の通りである。
例えば、図１(ａ)に示したオーバレイノードＮ２に、例えば、ＤｉｆｆＳｅｒｖなどのＩＰレイヤで提供される技術によってオーバレイノードＮ１との間のリンクについて確定したＱｏＳ情報が得られている場合に、ＱｏＳ情報保持手段は、ＩＰレイヤにおいて得られた確定したＱｏＳ情報を受け取って保持する。そして、このＱｏＳ情報が、上述したリンクについての測定結果として、形成手段によるパス情報の形成処理に供される。

つまり、オーバレイネットワークにおいて設定されるリンクについての測定は省略され、測定手段によって測定される特性値を含むＱｏＳ情報の代わりに、ＩＰレイヤの機能によって得られたＱｏＳ情報が該当するリンクに関するＱｏＳ情報として利用される。
本発明にかかわる第６のオーバレイノードは、上述した第４のオーバレイノードに備えられた作成手段に、利用者情報保持手段と、結合手段とを備えて構成される。

本発明にかかわる第６のオーバレイノードの原理は、以下の通りである。
上述した第４のオーバレイノードに備えられた作成手段において、利用者情報保持手段は、収容している利用者端末それぞれに対応するＱｏＳ情報を保持する。結合手段は、起点となる利用者端末と自身とを示す情報を含むノードリストと、利用者端末に対応して利用者情報保持手段に保持されたＱｏＳ情報とを結合してパスメッセージを作成する。

このように構成された第６のオーバレイノードの動作は、下記の通りである。
例えば、図１(ａ)に示したオーバレイノードＮ１に備えられた利用者情報保持手段には、利用者端末Ｐ₁₁、Ｐ₁₂、Ｐ₁₃に対応して、これらの利用者端末までの経路について得られているＱｏＳ情報ＱｏＳ_p1i(ｉ＝１〜３)が保持されている。そして、例えば、利用者端末Ｐ₁₃の起動を契機として、パスメッセージを作成する際に、結合手段により、この利用者端末Ｐ₁₃とオーバレイノードとを示す情報を含んだノードリストと上述したＱｏＳ情報ＱｏＳ_p13とが結合されて、パスメッセージが形成される。

このようにして形成されたパスメッセージを伝播させることにより、起点となる利用者端末とこれを収容するオーバレイノードとの間のＱｏＳとオーバレイネットワーク内のパスにかかわるＱｏＳとを合わせて考慮して、適切なルーチングを行うことができる。

本発明にかかわる第１のオーバレイノードからオーバレイネットワークを構成し、本発明にかかわる第１のオーバレイネットワーク対応ルーチング方法を適用することにより、ＩＰレイヤの機能に全く依存することなく、ＱｏＳを考慮したルーチングをインターネット規模のスケールにおいて実現することが可能である。
また、本発明にかかわる第４のオーバレイノードからオーバレイネットワークを構成し、本発明にかかわる第２のオーバレイネットワーク対応ルーチング方法を適用することにより、各オーバレイノードにパス情報を集積するために伝播されるパスメッセージの情報量を大幅に低減することができるので、オーバレイネットワークの負荷を軽減し、サービス品質の向上を図ることができる。

更に、本発明にかかわる第２または第５のオーバレイノードからオーバレイネットワークを構成することにより、例えば、ＤｉｆｆＳｅｒｖのようなＩＰレイヤの機能によって確定したＱｏＳ情報が得られている一部のリンクについての測定処理を省略することができるので、オーバレイネットワークのトラヒックに占める測定のためのトラヒックの割合を低減し、オーバレイネットワークにかかる負荷を抑制することができる。

また、本発明にかかわる第３または第６のオーバレイノードからオーバレイネットワークを構成することにより、オーバレイネットワークにおいて設定されるパスに関するＱｏＳに加えて、起点となる利用者端末とこれを収容するオーバレイノードとの間のＱｏＳをも考慮したルーチングを実現することができるので、エンドツーエンドで保証すべきＱｏＳを考慮して適切なパスを選択することが可能となる。

これにより、複数のＩＳＰにまたがってＱｏＳを考慮した適切なパスを設定することができるので、このパスによって最終的に接続される利用者間のエンドツーエンドの通信について、ＶｏＩＰや映像ストリーミング配信などのサービス提供に必要なＱｏＳを保証することが可能となる。

以下、図面に基づいて、本発明の実施形態について詳細に説明する。
（第１の実施形態）
図２に、本発明にかかわるオーバレイノードの第１の実施形態を示す。
なお、図２に示す構成要素のうち、図６に示した各部と同等のものについては、図６に示した符号を付して示し、その説明を省略する。

図２に示すオーバレイノードは、ｎ個のオーバレイノードからなるオーバレイネットワークのｉ番目(ｉ＝１〜ｎ)のノードであり、また、このオーバレイノードは、ｍｉ個の利用者端末Ｔ_i1〜Ｔ_imi(図示せず)を収容している。
図２に示したオーバレイノードにおいて、ピアセッション管理部２１２は、ピア間通信処理部２１１によって隣接するオーバレイノードとの間に設定されるリンクに関する情報を管理する。図２に示したセッション情報保持部２１３には、予め、オーバレイネットワークにおいて、オーバレイノードに隣接する別のオーバレイノードに関する情報が保持されており、この情報が、ピアセッション管理部２１２を介してピア間通信処理部２１１に渡され、リンクの設定処理に用いられる。

図２に示したＱｏＳ測定処理部２１４は、ピアセッション管理部２１２から測定すべきリンクに関する情報を受け取り、この情報で指定されたリンクについて遅延時間やパケット損失率および可用帯域などＱｏＳにかかわる特性値をピア間通信処理部２１１の機能を利用して測定し、測定結果からなるＱｏＳ情報をリンクに対応してＱｏＳ情報保持部２１５に格納する。

このＱｏＳ測定処理部２１４では、例えば、ピアセッション管理部２１２からの情報で指定されたリンクを介して、定期的にｐｉｎｇなどの制御パケットの授受を行い、この制御パケットの授受過程において得られる情報に基づいて上述した特性値を求めることにより、ＱｏＳ情報を得ることができる。
ここで、図２に示したオーバレイノードが、隣接するオーバレイノードのいずれかとの間のリンクについてＩＰレイヤの機能(例えば、ＤｉｆｆＳｅｒｖなど)によって確定したＱｏＳ情報の報告を受けることができる場合は、このＩＰレイヤから受け取ったＱｏＳ情報をセッション情報保持部２１３に該当する隣接ノードに対応して保持しておくことができる。また、このようにしてセッション情報保持部２１３に保持されたＱｏＳ情報は、ピアセッション管理部２１２を介してＱｏＳ情報保持部２１５に渡され、該当するリンクに対応して格納される。また、ピアセッション管理部２１２により、これらのリンク以外のリンクを選択的にＱｏＳの測定対象として指定することにより、ＩＰレイヤから受け取ったＱｏＳ情報をＱｏＳ情報保持部２１５に保持させたリンクについての測定処理を省略することができる。

また、図２に示したパス構成部２１６において、メッセージ作成部２２１は、ユーザ管理部４１１からの指示に応じて、指定された利用者端末Ｔ_ij(ｊ＝１〜ｍｉ)のＩＰアドレスＰ_ijを起点として示し、オーバレイノード自身のＩＰアドレスＮｉをパスの経由点として示すノードリストを含むパス情報を作成する。また、このメッセージ作成部２２１は、このようにして作成したパス情報をパス情報管理部４１６を介してパス情報データベース４１７に登録するとともに、このパス情報を含むパスメッセージを作成し、ピア間通信処理部２１１の機能を利用してオーバレイネットワークに送出する。

また、図２に示したパス構成部２１６において、中継制御部２２２は、ピア間通信処理部２１１に他のオーバレイノードからのパスメッセージが到達したときに、このパスメッセージの送信元に対応するリンクについてＱｏＳ情報保持部２１５に保持されたＱｏＳ情報を読み出し、このＱｏＳ情報を上述したパスメッセージとともにパス情報編集部２２３に渡す。

これに応じて、パス情報編集部２２３は、中継制御部２２２から受け取ったパスメッセージに含まれる情報に、自身のＩＰアドレスと上述したようにして得られたＱｏＳ情報と追加する編集処理を行い、得られたパス情報をパス情報管理部４１６に渡して、パスメッセージにおいて示された利用者端末から自身までのパスに対応するパス情報としてパス情報データベース４１７に登録させる。

また、図２に示したパス選択部２１７において、選択制御部２２４は、中継制御部２２２からの指示に応じて、指定された利用者端末Ｔ_ij(ｊ＝１〜ｋｉ)を起点とするパスに対応してパス情報データベース４１７に登録されているパス情報をパス情報管理部４１６の機能を利用して検索する。このようにして検索されたパス情報は、ＱｏＳ算出部２２５に渡され、該当するパスにおいて期待できるＱｏＳにかかわる特性の値が算出される。そして、得られた算出結果に基づいて、選択制御部２２４により、パス情報の一つが選択されて中継制御部２２２に返される。そして、中継制御部２２２により、このパス情報を含んだパスメッセージが生成され、ピア間通信処理部２１１を介して隣接するオーバレイノードに送出される。

また、図２に示したユーザ情報保持部２１８は、オーバレイノードが収容しているｋｉ個の利用者端末それぞれに対応して、これらの利用者端末それぞれのＩＰアドレスを含む利用者情報を保持しており、これらの利用者情報は、ＩＰレイヤから通知される制御情報とともに、ユーザ管理部４１１による各利用者端末の管理にかかわる処理に供される。
次に、図１(ａ)に示したように、オーバレイノードＮ１〜Ｎ５から構成されるオーバレイネットワークを例にとって、本発明にかかわるルーチング方法によるルーチング動作を説明する。

例えば、オーバレイノードＮｉ(ｉ＝１〜５)が起動されたときに、図２に示したユーザ管理部４１１は、このオーバレイノードＮｉに収容されるｍｉ個の利用者端末Ｔ_ij(ｊ＝１〜ｋｉ)それぞれを指定して、パス構成部２１６のメッセージ作成部２２１にパスメッセージの作成を依頼する。なお、このようなパスメッセージの作成は、利用者端末の起動や新たな利用者端末の追加などにも応じて実行される。

これに応じて、例えば、図１に示したオーバレイノードＮ１に収容されている利用者端末Ｔ₁₁〜Ｔ₁₃について、このオーバレイノードＮ１に備えられたメッセージ作成部２２１により、利用者端末Ｔ₁₁〜Ｔ₁₃のＩＰアドレスＰ₁₁、Ｐ₁₂、Ｐ₁₃とオーバレイノードＮ１のＩＰアドレスＮ１とを用いてパス情報（Ｐ_1j、Ｎ１）(ｊ＝１〜３)がそれぞれ作成される。このようにして得られたパス情報は、図２に示したパス情報管理部４１６を介してパス情報データベース４１７に登録されるとともに、それぞれに対応して作成されるパスメッセージに含められ、隣接するオーバレイノードＮ２、Ｎ３に送出される(図１参照)。

例えば、オーバレイノードＮ２に上述したパス情報（Ｐ_1j、Ｎ１）(ｊ＝１〜３)を含んだパスメッセージが到達すると、このパスメッセージは、ピア間通信処理部２１１を介してパス構成部２１６の中継制御部２２２に渡される。
このとき、中継制御部２２２により、上述したパスメッセージの送信元であるオーバレイノードＮ１との間のリンクＳ₁₂に対応するＱｏＳ情報ＱｏＳ₁₂がＱｏＳ情報保持部２１５から読み出され、上述したパス情報とともにパス情報編集部２２３に渡される。

パス情報編集部２２３は、中継制御部２２２から受け取ったパス情報に含まれるノードリスト（Ｐ_1j、Ｎ１）(ｊ＝１〜３)にオーバレイノードＮ２自身のＩＰアドレスＮ２を追加するとともに上述したＱｏＳ情報ＱｏＳ₁₂を付加して、利用者端末Ｔ_1jからオーバレイノードＮ２までのパスを示すノードリスト（Ｐ_1j、Ｎ１、Ｎ２）(ｊ＝１〜３)とＱｏＳ情報ＱｏＳ₁₂とからなるパス情報を形成する。

このようにして形成されたパス情報が、パス情報管理部４１６を介してパス情報データベース４１７に蓄積され、パス選択部２１７の処理に供される。
ここで、図１に示したオーバレイネットワークでは、オーバレイノードＮ２を経由してオーバレイノードＮ１に収容された利用者端末Ｔ_1jに到達するパスは上述したパスメッセージに対応して生成されたパス情報で示されるもののみである。したがって、中継制御部２２２からの指示に応じて、パス選択部２１７により、パス情報データベース４１７に蓄積されたパス情報の中から、ノードリスト（Ｐ_1j、Ｎ１、Ｎ２）(ｊ＝１〜３)とＱｏＳ情報ＱｏＳ₁₂とからなるパス情報が選択され、このパス情報に利用しているパスである旨を示すマークが付される。そして、このパス情報を含むパスメッセージが、中継制御部２２２によって生成され、ピア間通信処理部２１１により、隣接するオーバレイノードＮ４宛てに中継される。

同様にして、図１に示したオーバレイノードＮ３では、オーバレイノードｎ１から受け取ったパスメッセージに含まれるパス情報（Ｐ_1j、Ｎ１）(ｊ＝１〜３)に基づいて、利用者端末Ｔ_1jからオーバレイノードＮ３までのパスを示すノードリスト（Ｐ_1j、Ｎ１、Ｎ３）(ｊ＝１〜３)とリンクＳ₁₃に対応するＱｏＳ情報ＱｏＳ₁₃とからなるパス情報が形成される。そして、このパス情報が、パス情報データベース４１７に蓄積されるとともに、上述したオーバレイノードｎ２におけるパス選択処理と同様にして、利用しているパスとして選択され、パスメッセージに含められて隣接ずるオーバレイノードＮ４に中継される。

このようにして、図１に示したオーバレイノードＮ４に、異なる２つのパスに関するパス情報を含むパスメッセージが到達し、これらのパスメッセージの受信に応じて、それぞれの送信元との間のリンクＳ₂₄、Ｓ₃₄に対応してＱｏＳ情報保持部２１５に保持されたＱｏＳ情報ＱｏＳ₂₄、ＱｏＳ₃₄を用いて、それぞれのパスを経由してオーバレイノードＮ４に至るパスに関するパス情報が形成される。

つまり、図３(ａ)に示すように、オーバレイノードＮ２からのパスメッセージに対応して、ノードリスト（Ｐ_1j、Ｎ１、Ｎ２、Ｎ４）(ｊ＝１〜３)とＱｏＳ情報（ＱｏＳ₁₂、ＱｏＳ₂₄）とからなるパス情報が作成され、また、オーバレイノードＮ３からのパスメッセージに対応して、ノードリスト（Ｐ_1j、Ｎ１、Ｎ３、Ｎ４）(ｊ＝１〜３)とＱｏＳ情報（ＱｏＳ₁₃、ＱｏＳ₃₄）とからなるパス情報が作成される。そして、これらのパス情報が、パス情報データベース４１７に蓄積され、パス選択処理に供される。

上述したようにして、同一の利用者端末を起点としながら異なるパスを経由して到達した複数のパスメッセージがパス情報データベース４１７に蓄積されている場合（図３(ａ)参照）には、図２に示した選択制御部２２４により、これらのパス情報がパス情報データベース４１７から検索され、それぞれのパス情報に含まれるＱｏＳ情報がＱｏＳ算出部２２５の処理に供される。

ここで、パス情報に含まれるノードリストによって、パスに含まれるＬ個のリンクＳ₁〜Ｓ_Lが示されており、これらのリンクＳ₁〜Ｓ_Lについて、遅延時間τ_s1〜τ_sL、パケット損失率φ_s1〜φ_sL、可用帯域ｃ_s1〜ｃ_sLが得られれば、これらのリンクからなるパス全体の遅延時間τ、パケット損失率φおよび可用帯域ｃは、それぞれ、式(１)から式(３)のように表される。

したがって、ＱｏＳ算出部２２５により、これらの式(１)〜式(３)を用いて、上述した２つのパス情報で示されるパスにおいて期待できる遅延時間τ、パケット損失率φおよび可用帯域ｃを求めることにより、これらのパス情報で示されるパス全体に関するＱｏＳ情報を得ることができる。なお、上述した式(３)においては、可用帯域ｃ_S1〜ｃ_SLの最小値として、パス全体の可用帯域ｃを求めている。

このようにして得られたＱｏＳ情報によって、例えば、ノードリスト（Ｐ_1j、Ｎ１、Ｎ３、Ｎ４）(ｊ＝１〜３)で示されるパスの方がより高いＱｏＳが期待できることが示された場合に、選択制御部２２４により、該当するパスが選択され、これ応じて、パス情報データベース４１７に格納された該当するパス情報に利用しているパスである旨のマークが付される(図３(ａ)参照)。また、このようにして選択されたパス情報を含むパスメッセージが中継制御部２２２によって作成され、ピア間通信処理部２１１を介して、隣接するオーバレイノードＮ５に送出される。

ここで、選択制御部２２４は、例えば、複数のパスに対応して算出されたＱｏＳ情報に含まれる各特性値について、それぞれ適切な方法を用いた評価を行い、この評価結果に必要に応じて適切な重みを付けて総合評価値を求め、この総合評価値に基づいて一つのパスを選択することができる。また、複数のパスについて、同等の評価結果が得られたときに、選択制御部２２４は、パス情報データベース４１７に最も早く登録されたパス情報を選択することにより、単一のパスを確実に選択することができる。

このように、本発明のルーチング方法を適用したオーバレイノードでは、他のオーバレイノードから受け取ったパスメッセージを隣接する他のオーバレイノードに中継する際に、それまでに受け取ったパスメッセージに含まれているパス情報に基づいて、最も高いＱｏＳが期待できるパスを選択し、このパスに対応するパス情報を選択的に隣接するオーバレイノードに中継するパスメッセージに含めることができる。

このように、パスメッセージを伝播させる過程において、各パスにおいて期待できるＱｏＳに基づいてパスの取捨選択を行うことにより、インターネット規模のオーバレイネットワークにおいて、ＱｏＳを考慮したルーチングを実現することができる。
また、図２に示したＱｏＳ測定処理部２１４により、各オーバレイノードにおいて、隣接する全てのオーバレイノードとの間のリンクに関するＱｏＳを示す各特性値を測定すれば、ＩＰレイヤの機能に全く依存することなく、上述したパス情報の作成に必要なＱｏＳ情報を取得することができる。

このように、本発明のルーチング方法によれば、各自律システムに配置されたオーバレイノードにＩＰレイヤにおいてＱｏＳ情報を取得する機能が備えられているか否か、および、ＩＰレイヤにおいて取得されたＱｏＳ情報を上位レイヤに報告する機能があるか否かにかかわらず、ＱｏＳを考慮したルーチングを実現することができる。
一方、上述したように、オーバレイネットワークを構成する一部のリンクについてＩＰレイヤの機能によって確定したＱｏＳ情報が得られ、この確定したＱｏＳ情報をオーバレイノードに備えられたＱｏＳ情報保持部２１５に反映させることができれば、ＩＰレイヤで得られた確定したＱｏＳ情報を利用して、該当するリンクに関するＱｏＳ測定処理部２１４の処理を省略することができる。

つまり、該当するリンクについては、ＱｏＳ測定のために授受される制御パケットなどに関するトラヒックが発生しなくなるので、その分、オーバレイネットワーク全体として、ＱｏＳ測定のためのトラヒックを低減することが可能となる。
なお、ＩＰレイヤの機能によって得られるＱｏＳ情報をＱｏＳ測定処理部２１４の測定結果の代わりに利用する構成であるので、一部のリンクについてのみＩＰレイヤからＱｏＳ情報が取得できる場合や、ＩＰレイヤからＱｏＳ情報を取得できるオーバレイノードと取得できないオーバレイノードとが混在している場合にも全く問題なくルーチング処理を実現することができる。

このように、本発明では、各自律システムに配置されるオーバレイノードの構成に大幅な自由度を与えることができるので、多数のＩＳＰがひしめいている現状に極めてよくマッチしている。
（第２の実施形態）
更に、各オーバレイノードに収容される利用者端末とその収容先のオーバレイノードとの間のリンクに関するＱｏＳを考慮したルーチングを実現することもできる。

例えば、図１に示したユーザ情報保持部２１８は、ｉ番目のオーバレイノードに収容される各利用者端末Ｔ_i1〜Ｔ_imiのＩＰアドレスＰ_i1〜Ｐ_imiに加えて、これらの利用者端末Ｔ_i1〜Ｔ_imiとオーバレイノードとの間のリンクについて、例えば、各利用者が利用しているアクセス回線について保証されているＱｏＳを示すＱｏＳ情報ＱｏＳ_Tij(ｊ＝１〜ｍｉ)を保持している。また、図１に示したユーザ管理部４１１は、オーバレイノードの起動などに応じてパスメッセージの作成を依頼する際に、対象となる利用者端末を示すＩＰアドレスＰ_ijとともにこのＱｏＳ情報ＱｏＳ_Tijをメッセージ作成部２２１に渡し、パスメッセージの作成処理に供する。

これに応じて、メッセージ作成部２２１により、指定された利用者端末Ｔ_ijからｉ番目のオーバレイノードに至るパスを示すノードリスト(Ｐ_ij、Ｎｉ)と、この利用者端末Ｔ_ijとオーバレイノードとの間のリンクに対応するＱｏＳ情報ＱｏＳ_Tijとを含むパス情報が作成され、このパス情報が、パス情報管理部４１６を介してパス情報データベース４１７に蓄積される。また、メッセージ作成部２２１により、このパス情報を含むパスメッセージが作成され、ピア間通信処理部２１１によって隣接するオーバレイノードに送出される。

このようにして、各オーバレイノードと利用者端末との間のリンクに関するＱｏＳ情報を含むパスメッセージをオーバレイネットワークにおいて伝播させることにより、伝播経路上のオーバレイノードに備えられたパス情報データベース４１７(図２参照)に、オーバレイネットワークにおけるエンドツーエンドのパスに対応するＱｏＳ情報に加えて、利用者端末までのリンクに関するＱｏＳ情報をあわせて収集することができる。

したがって、例えば、図１(ａ)に示したオーバレイノードＮ１に収容された利用者端末Ｔ₁₁を起点とし、オーバレイノードＮ２、Ｎ３をそれぞれ経由する２つのパスを介してパスメッセージがオーバレイノードＮ４に到達すると、図３(ｂ)に示すように、利用者端末Ｔ₁₁に対応するＱｏＳ情報ＱｏＳ_T11を含むパス情報が、このオーバレイノードＮ４に備えられたパス情報データベース４１７(図２参照)に登録される。

そして、ノードリスト（Ｐ₁₁、Ｎ１、Ｎ２、Ｎ４）とＱｏＳ情報（ＱｏＳ_T11、ＱｏＳ₁₂、ＱｏＳ₂₄）とからなるパス情報と、ノードリスト（Ｐ₁₁、Ｎ１、Ｎ３、Ｎ４）とＱｏＳ情報（ＱｏＳ_T11、ＱｏＳ₁₃、ＱｏＳ₃₄）とからなるパス情報とがパス情報データベース４１７から検索され、ＱｏＳ算出部２２５による特性値の算出処理に供される。
ここで、例えば、利用者端末においてサービスを提供するアプリケーションによって指定される制限条件(例えば、遅延時間１００ｍｓ、パケット損失率１０％)がある場合などには、選択制御部２２４は、この制限条件を考慮してＱｏＳ算出部２２５によって得られた算出結果を評価する必要がある。そして、一般に、個々の利用者端末とこれを収容するオーバレイノードまでのリンクは、オーバレイネットワーク内のリンクに比べて、期待できるＱｏＳが低い場合が少なくない。つまり、利用者端末とオーバレイノード間のリンクに関するＱｏＳ情報によっては、オーバレイネットワーク内のエンドツーエンドのパスに関するＱｏＳの評価が覆る可能性がある。

例えば、ノードリスト（Ｐ₁₁、Ｎ１、Ｎ２、Ｎ４）で示されるパスについて、オーバレイネットワークのエンドツーエンドのＱｏＳ情報として遅延時間τが５０ｍｓ、パケット損失率３％が得られ、一方、ノードリスト（Ｐ₁₁、Ｎ１、Ｎ３、Ｎ４）で示されるパスについて、同じく遅延時間τが１０ｍｓ、パケット損失率９％が得られている場合について説明する。

上述した２つのパスのＱｏＳ情報に、利用者端末Ｔ₁₁とオーバレイノードＮ１との間のＱｏＳ情報として遅延時間τが５ｍｓ、パケット損失率２％を加味した上で利用者端末Ｔ₁₁からオーバレイノードＮ４までのパスについての遅延時間およびパケット損失率を求めると、前者は、遅延時間が大きいものの制限条件の範囲内であり、かつ、パケット損失は制限条件を満たしているのに対して、後者は、遅延時間が小さいとはいえパケット損失が制限条件を明らかに満たしていないことが分かる。

このように、利用者端末とこれを収容するオーバレイノードとの間のＱｏＳおよびサービスの提供に必要なＱｏＳに関する制限条件が明らかな場合は、オーバレイネットワークにおけるエンドツーエンドのＱｏＳを汎用的な評価基準を用いて評価する代わりに、選択制御部２２４により、利用者端末までのパス全体のＱｏＳが制限条件を満たしているか否かに基づいて、そのパスを評価することができる。これにより、上述した例では、遅延時間の大きさにかかわらず、パケット損失率の小さいパス(つまり、オーバレイノードＮ２を経由するパス)が選択され、パス情報データベース４１７の該当するパス情報に利用しているパスである旨のマークがつけられる。

このように、各利用者端末Ｔ_ijからこれを収容するオーバレイノードまでの経路に関するＱｏＳ情報を利用することにより、利用者にサービスを提供するために必要な制限条件を満たす適切なパスを確実に選択することが可能となる。
（第３の実施形態）
図４に、本発明にかかわるオーバレイノードの第３の実施形態を示す。

なお、図４に示す構成要素のうち、図２に示した各部と同等のものについては、図２に示した符号を付して示し、その説明を省略する。
図４に示したパス構成部２１６は、図２に示した各部に加えてＱｏＳ算出部２２５を備え、パス情報編集部２２３によってパス情報を編集する過程において、該当するパス全体のＱｏＳをＱｏＳ算出部２２５の機能を利用して求め、このパス全体のＱｏＳを含むパス情報を、パス情報管理部４１６を介してパス情報データベース４１７に蓄積する。

例えば、パス情報編集部２２３は、中継制御部２２２から受け取ったパス情報にＱｏＳ情報が含まれている場合に、このＱｏＳ情報ＱｏＳ₀と中継制御部２２２から新たに受け取った送信元に対応するリンクＳ_aのＱｏＳ情報ＱｏＳ_aとをＱｏＳ算出部２２５に渡し、自ノードまでのパスに関するＱｏＳ情報ＱｏＳを算出する処理に供する。
ここで、ＱｏＳ情報ＱｏＳに含まれる遅延時間τ、パケット損失率φおよび可用帯域ｃは、ＱｏＳ情報ＱｏＳ₀に含まれる遅延時間τ₀、パケット損失率φ₀および可用帯域ｃ₀と、ＱｏＳ情報ＱｏＳ_aに含まれる遅延時間τ_a、パケット損失率φ_aおよび可用帯域ｃ_aとを用いて、式(４)〜式(６)のように表される。

τ＝τ₀＋τ_a ・・・（４）
φ＝１−(１−φ₀)×（１−φ_a） ・・・（５）
ｃ＝ｍｉｎ（ｃ₀、ｃ_a） ・・・（６）
パス情報編集部２２３は、ＱｏＳ算出部２２５によって上述した式(４)〜式(６)に基づいて算出されたＱｏＳ情報ＱｏＳを受け取り、このＱｏＳ情報ＱｏＳによって中継制御部２２２から受け取ったパス情報のＱｏＳ情報ＱｏＳ_baseを置き換えることにより、自身までの経路を示すノードリストとこのパス全体に関するＱｏＳを示すＱｏＳ情報ＱｏＳとから構成されるパス情報を、パス情報管理部４１６による登録処理に供することができる。

このようにしてパス情報データベース４１７に蓄積されるパス情報は、図５(ａ)に示すように、オーバレイネットワークにおいて該当するパスを構成する各リンクのＱｏＳ情報に基づいて算出されたパス全体のＱｏＳ情報を、それぞれのリンクに関するＱｏＳ情報を示したリストに代えて(図３(ａ)参照)含んでいる。
なお、図５(ａ)において、ノードリスト(Ｎ１、Ｎ２、Ｎ４)で示されるパスに対応するＱｏＳ情報を符号ＱｏＳ_1-2-4で示し、また、ノードリスト(Ｎ１、Ｎ３、Ｎ４)で示されるパスに対応するＱｏＳ情報を符号ＱｏＳ_1-3-4で示した。

したがって、図４に示したパス選択部２２６は、パス情報データベース４１７に利用者端末に対応して蓄積されたパス情報に含まれるＱｏＳ情報を相互に比較することにより、最も高いＱｏＳが期待できるパスを選択することができる。
また、このようにして、各オーバレイノードにおいて、パス情報を蓄積する段階でそのパス全体に関するＱｏＳ情報を求めておくことにより、パスメッセージのデータ長を大幅に低減することができる。なぜなら、図４に示したオーバレイノードによって伝播されるパスメッセージに含まれるＱｏＳ情報は、その伝播経路におけるホップ数にかかわらず、１つのリンクのＱｏＳ情報と同等の情報量に集約されているからである。

上述したようにして、オーバレイネットワークにおいて伝播されるパスメッセージの情報量を低減することは、インターネット規模のオーバレイネットワークにおいて設定されるパスのホップ数が非常に大きくなる場合があることを考えれば、極めて重要である。
また、図４に示したオーバレイノードに、上述した第２の実施形態の項において説明した技術を適用することも可能である。

この場合は、図５(ｂ)に示すように、自身を収容するオーバレイノードとの間について確定したＱｏＳが得られている利用者端末を起点とするパスについては、このパスの経路を示すノードリストともに、起点となる利用者端末から自ノードまでの全てのリンクに関するＱｏＳ情報から算出されたパス全体のＱｏＳ情報がパス情報データベース４１７に格納される。なお、図５(ｂ)において、利用者端末Ｔ₁₁を起点とし、ノードリスト(Ｎ１、Ｎ２、Ｎ４)で示されるパスに対応するＱｏＳ情報を符号ＱｏＳ_T11-1-2-4で示し、また、同じくノードリスト(Ｎ１、Ｎ３、Ｎ４)で示されるパスに対応するＱｏＳ情報を符号ＱｏＳ_T11-1-3-4で示した。

上述したように、本発明にかかわるオーバレイノードによって形成されたオーバレイネットワークにおいて本発明にかかわるルーチング方法を適用することにより、多種多様なインターネットサービスプロバイダがそれぞれ独自のサービスを展開しているインターネットシステムにおいて、ＱｏＳを考慮しつつ、各ＩＳＰに対応する自律システムをまたがる情報流通経路を設定することができる。

上述したように、本発明にかかわるルーチング方法およびオーバレイノードによれば、インターネット規模のスケーラビリティを確保しつつ、異なる自律システムに属する利用者端末を結ぶパスのエンドツーエンドでサービスの提供に必要なＱｏＳを保証することが可能となる。
これにより、自律システムの壁にかかわらず、利用者にＶｏＩＰや映像のストリーミング配信などの高度なサービスを提供する際のサービス品質を向上することができるので、このようなリアルタイム性の高いサービスを自律システムの障壁を超えて実現するための技術分野において極めて有用である。

本発明にかかわるルーチング方法の原理を説明する図である。 本発明にかかわるオーバレイネットワークシステムの第１の実施形態を示す図である。 パス情報の蓄積を説明する図である。 本発明にかかわるオーバレイノードの第３の実施形態を示す図である。 パス情報の蓄積を説明する図である。 ＢＧＰルーチングの説明図である。

符号の説明

２１１ ピア間通信処理部
２１２ ピアセッション管理部
２１３ セッション情報保持部
２１４ ＱｏＳ測定処理部
２１５ ＱｏＳ情報保持部
２１６、４１４ パス構成部
２１７、２２６、４１５ パス選択部
２１８ ユーザ情報保持部
２２１ メッセージ作成部
２２２ 中継制御部
２２３ パス情報編集部
２２４ 選択制御部
２２５ ＱｏＳ算出部
４１１ ユーザ管理部
４１２ ＴＣＰセッション管理部
４１３ ＴＣＰ通信処理部
４１６ パス情報管理部
４１７ パス情報データベース

Claims (8)

1. ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成し、隣接するオーバレイノードとの間にピアセッションを設定するオーバレイノードで用いられるオーバレイネットワーク対応ルーチング方法において、
   前記オーバレイネットワークを構成するオーバレイノードそれぞれの起動あるいは前記オーバレイノードに収容される利用者端末の起動あるいは追加に応じて、前記オーバレイノードに収容される利用者端末と前記オーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成する作成ステップと、
   前記作成されたパスメッセージを隣接するオーバレイノードとの間に設定されたリンクを介して送信する送信ステップと、
   前記オーバレイノードごとに、隣接する少なくとも一つのオーバレイノードとの間のリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する測定ステップと、
   前記パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加するとともに、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報を付加することにより、前記パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成し、このパス情報を蓄積する蓄積ステップと、
   前記パスメッセージの受信に応じて、それまでに蓄積したパス情報の中から、前記受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する検索ステップと、
   前記検索されたパスメッセージそれぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する選択ステップと、
   前記選択されたパスのパス情報を含む新たなパスメッセージを前記送信元のオーバレイノードを除く隣接するオーバレイノードに中継する中継ステップとを備え、
   前記選択ステップは、
   前記検索されたパス情報それぞれに含まれる情報と、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、前記パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出するＱｏＳ算出ステップを備えた
   ことを特徴とするオーバレイネットワーク対応ルーチング方法。
2. ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成し、隣接するオーバレイノードとの間にピアセッションを設定するオーバレイノードで用いられるオーバレイネットワーク対応ルーチング方法において、
   前記オーバレイネットワークを構成するオーバレイノードそれぞれの起動あるいは前記オーバレイノードに収容される利用者端末の起動あるいは追加に応じて、前記オーバレイノードに収容される利用者端末と前記オーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成する作成ステップと、
   前記作成されたパスメッセージを隣接するオーバレイノードとの間に設定されたリンクを介して送信する送信ステップと、
   前記オーバレイノードごとに、隣接する少なくとも一つのオーバレイノードとの間のリンクそれぞれについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する測定ステップと、
   前記パスメッセージの受信に応じて、受信したパスメッセージに含まれる情報と、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、前記パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出するＱｏＳ算出ステップと、
   前記パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、前記ＱｏＳ算出ステップによって得られたＱｏＳ情報とからパス情報を形成し、このパス情報を蓄積する蓄積ステップと、
   前記パスメッセージの受信に応じて、それまでに蓄積したパス情報の中から、前記受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する検索ステップと、
   前記検索されたパス情報それぞれに含まれるＱｏＳ情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する選択ステップと、
   前記選択されたパスのパス情報を含む新たなパスメッセージを前記送信元のオーバレイノードを除く隣接するオーバレイノードに中継する中継ステップと
   を備えたことを特徴とするオーバレイネットワーク対応ルーチング方法。
3. ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成するオーバレイノードであって、隣接するオーバレイノードとの間に設定したピアセッションを介して情報のやり取りを行うピア間通信手段を有し、少なくとも一つの利用者端末を収容するオーバレイノードにおいて、
   前記オーバレイノードの起動あるいは前記オーバレイノードに収容される利用者端末の起動あるいは追加に応じて、前記利用者端末と前記オーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成し、前記ピア間通信手段を介して隣接するオーバレイノードに送出する作成手段と、
   前記ピア間通信手段によって設定された各リンクについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する測定手段と、
   前記パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とから、前記パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成する形成手段と、
   形成されたパス情報を順次に蓄積するパス情報データベースと、
   前記パスメッセージの受信に応じて、それまでに前記パス情報データベースに蓄積されたパス情報の中から、前記受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する検索手段と、
   前記検索されたパス情報それぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する選択手段と、
   前記ピア間通信手段を介して、前記選択されたパスのパス情報を含む新たなパスメッセージを前記送信元のオーバレイノードを除く隣接するオーバレイノードに中継する中継手段とを備え、
   前記選択手段は、
   前記検索されたパス情報それぞれに含まれる情報と、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、前記パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出するＱｏＳ算出手段を備えた
   ことを特徴とするオーバレイノード。
4. 請求項３に記載のオーバレイノードにおいて、
   前記測定手段は、
   前記ピア間通信手段によって設定されるピアセッションのうち、ＩＰレイヤにおいて確定したＱｏＳ情報が得られたリンクに対応して、前記確定したＱｏＳ情報を保持し、前記リンクに対応する測定によって得られたＱｏＳ情報として出力するＱｏＳ情報保持手段を備えた
   ことを特徴とするオーバレイノード。
5. 請求項３に記載のオーバレイノードにおいて、
   前記作成手段は、
   前記収容している利用者端末それぞれに対応するＱｏＳ情報を保持する利用者情報保持手段と、
   前記起点となる利用者端末と自身とを示す情報を含むノードリストと、前記利用者端末に対応して前記利用者情報保持手段に保持されたＱｏＳ情報とを結合してパスメッセージを作成する結合手段とを備えた
   ことを特徴とするオーバレイノード。
6. ＩＰレイヤの上位レイヤに位置するオーバレイネットワークを構成するオーバレイノードであって、隣接するオーバレイノードとの間に設定したピアセッションを介して情報のやり取りを行うピア間通信手段を有し、少なくとも一つの利用者端末を収容するオーバレイノードにおいて、
   前記オーバレイノードの起動あるいは前記オーバレイノードに収容される利用者端末の起動あるいは追加に応じて、前記利用者端末と前記オーバレイノードとをパスの経由点として示すノードリストを含むパスメッセージを作成し、前記ピア間通信手段を介して隣接するオーバレイノードに送出する作成手段と、
   前記ピア間通信手段によって設定された各リンクについて、遅延時間、パケット損失率および可用帯域を含むＱｏＳにかかわる特性を測定する測定手段と、
   前記パスメッセージの受信に応じて、このパスメッセージに含まれる情報と、前記パスメッセージの送信元に対応するリンクについて測定された特性を示すＱｏＳ情報とに基づいて、前記パスメッセージで示された利用者端末から自身までの経路に関するＱｏＳ情報を算出するＱｏＳ算出手段と、
   前記パスメッセージの受信に応じて、受信したパスメッセージに含まれるノードリストに自身をパスの経由点として追加して得られるノードリストと、前記ＱｏＳ算出手段によって算出されたＱｏＳ情報とから、前記パスメッセージで示された利用者端末から自身までの経路に関するパス情報を形成する形成手段と、
   形成されたパス情報を順次に蓄積するパス情報データベースと、
   前記パスメッセージの受信に応じて、それまでに前記パス情報データベースに蓄積されたパス情報の中から、前記受信したパスメッセージに含まれるノードリストで示される利用者端末を含むものを検索する検索手段と、
   前記検索されたパス情報それぞれに含まれる情報に基づいて、最も高いＱｏＳの実現が期待できるパスを利用するパスとして選択する選択手段と、
   前記ピア間通信手段を介して、前記選択されたパスのパス情報を含む新たなパスメッセージを前記送信元のオーバレイノードを除く隣接するオーバレイノードに中継する中継手段と
   を備えたことを特徴とするオーバレイノード。
7. 請求項６に記載のオーバレイノードにおいて、
   前記測定手段は、
   前記ピア間通信手段によって設定されるリンクのうち、ＩＰレイヤにおいて確定したＱｏＳ情報が得られたリンクに対応して、前記確定したＱｏＳ情報を保持し、前記リンクに対応する測定によって得られたＱｏＳ情報として出力するＱｏＳ情報保持手段を備えた
   ことを特徴とするオーバレイノード。
8. 請求項６に記載のオーバレイノードにおいて、
   前記作成手段は、
   前記収容している利用者端末それぞれに対応するＱｏＳ情報を保持する利用者情報保持手段と、
   前記起点となる利用者端末と自身とを示す情報を含むノードリストと、前記利用者端末に対応して前記利用者情報保持手段に保持されたＱｏＳ情報とを結合してパスメッセージを作成する結合手段とを備えた
   ことを特徴とするオーバレイノード。
   
   

Images