(57)【特許請求の範囲】
【請求項１】
ＩＰネットワークに接続する複数のオーバーレイノードによって構成される論理網であるオーバーレイネットワークを形成する方法であって、
オーバーレイネットワークを構成するオーバーレイノードの内、予め定められた条件で選定された複数のスーパーノードは、各スーパーノード間で論理的な接続を行いスーパーノードネットワーク層を形成し、
上記条件に合わない各一般ノードは、上記スーパーノードのいずれか一つと論理的に接続して一般ノードネットワーク層を形成し、
該一般ノードネットワーク層と上記スーパーノードネットワーク層の２層を形成すると共に、
各スーパーノードは、予め記憶装置に記憶した自身の２次元の座標位置情報を読み出し、
自身を中心に２次元空間を角度θ＝π／３で空間を６つのセクタに分割し、
セクタｊ（ｊ＝１〜６）の空間に位置する他のスーパーノードから当該スーパーノードの２次元の座標位置情報を取得し、最も座標位置が近いスーパーノードを当該セクタｊにおける隣接スーパーノードとして特定し、特定した隣接スーパーノードと論理的に接続する
ことを特徴とするオーバーレイネットワーク形成方法。
【請求項２】
請求項１に記載のオーバーレイネットワーク形成方法であって、
上記一般ノードは、上記複数のスーパーノードの内、最短ＲＴＴを含む最良通信効率のスーパーノードを特定し、特定したスーパーノードと論理的に接続することを特徴とするオーバーレイネットワーク形成方法。
【請求項３】
請求項２に記載のオーバーレイネットワーク形成方法であって、
各スーパーノードは、一定周期毎あるいは新規スーパーノードの参加もしくは既存スーパーノードの離脱を含む事象の発生を契機に、セクタｊにおいて接続する隣接スーパーノードの更新を行うことを特徴とするオーバーレイネットワーク形成方法。
【請求項４】
請求項１から請求項３のいずれかに記載のオーバーレイネットワーク形成方法であって、
上記スーパーノードは、
送信元スーパーノードから転送されてきたパケットを着信先スーパーノードへ中継転送する際、
自身の隣接スーパーノードの内、座標空間上において、自身の座標ｕと着信先スーパーノードの座標ｙとを結ぶ線ｕ−ｙを挟む両側から１つずつ、自身の座標ｕと隣接スーパーノードの座標ｖｊとを結ぶ線ｕ−ｖｊと上記線ｕ−ｙとで形成される角度が最も小さい第１，第２の隣接スーパーノードを特定し、
特定した第１，第２の隣接スーパーノードのいずれかをランダムに次ホップノードとしてパケットを転送することを特徴とするオーバーレイネットワーク形成方法。
【請求項５】
請求項１から請求項４のいずれかに記載のオーバーレイネットワーク形成方法であって、
各一般ノードは、予め記憶装置に記憶した自身の２次元の座標位置情報を、論理的に接続したスーパーノードに通知すると共に、該スーパーノードの２次元の座標位置情報を取得して、自身の２次元の座標位置情報とを用いて、自身と該スーパーノード間の距離（第１の距離）を算出し、
論理的に接続したスーパーノードから、同じスーパーノードに接続した他の一般ノードの２次元の座標位置情報を取得して、取得した他の一般ノードの２次元の座標位置情報と当該スーパーノードの２次元の座標位置情報とを用いて、各他の一般ノードと当該スーパーノード間の距離（第２の距離）を算出し、
論理的に接続したスーパーノードから、同じスーパーノードに接続した他の一般ノードの２次元の座標位置情報を取得して、取得した他の一般ノードの２次元の座標位置情報と記憶装置に記憶した自身の２次元の座標位置情報とを用いて、各他の一般ノードとの距離（第３の距離）を算出し、
算出した第１の距離と第２の距離を加算し、加算した値と第３の距離とを比較して、
第１の距離と第２の距離を加算した値が、第３の距離より大きくなる他の一般ノードがあれば、該他の一般ノードと自身との間を論理的に接続してショートカットの経路を作成することを特徴とするオーバーレイネットワーク形成方法。
【請求項６】
請求項１から請求項５のいずれかに記載のオーバーレイネットワーク形成方法であって、
上記一般ノードは、別のスーパーノードに接続した一般ノードとパケット通信する際、自身が接続したスーパーノードにパケットを送出し、
パケットと受けたスーパーノードから通信先の一般ノードに接続しているスーパーノードまでスーパーノードネットワーク層を介してパケットを転送し、
通信先の一般ノードに接続しているスーパーノードは、当該通信先の一般ノードにパケットを送出する
ことを特徴とするオーバーレイネットワーク形成方法。
【請求項７】
ＩＰネットワーク上にオーバーレイネットワークを形成する複数のオーバーレイノードであって、
請求項１から請求項６のいずれかに記載のオーバーレイネットワーク形成方法におけるスーパーノードもしくは一般ノードのいずれかとして、上記スーパーノード層もしくは上記一般ノード層を形成する手段を具備したことを特徴とするオーバーレイノード。
【請求項８】
ＩＰネットワークに接続する複数のオーバーレイノードによって構成される論理網であるオーバーレイネットワークであって、
請求項７に記載のオーバーレイノードによって上記スーパーノード層と上記一般ノード層の２層から形成されることを特徴とするオーバーレイネットワーク。
【請求項９】
コンピュータに、請求項１から請求項６のいずれかに記載のオーバーレイネットワーク形成方法におけるスーパーノードもしくは一般ノードのいずれかとしての処理を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ネットワークにおけるエンド・ツー・エンドの通信品質を向上させる技術に係り、特にＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させるのに好適な技術に関するものである。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Ｖｏｉｃｅ  ｏｖｅｒ  ＩＰ）やストリーミングに代表されるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）に敏感な実時間アプリケーション等の収容も急速に発展している。
【０００３】
これに伴い、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００４】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
（２）インターネットは管理主体の異なる複数のＡＳ（Ａｕｔｏｎｏｍｏｕｓ  Ｓｙｓｔｅｍ）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００５】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えば非特許文献１に記載の、オーバーレイネットワークによるＱｏＳ管理技術が注目されている。
【０００６】
オーバーレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層に、目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００７】
このようなオーバーレイネットワークによるＱｏＳ管理の基本的な概念を図１に例示する。図１において、ｘからｙに向けて、ＩＰルータ２ａ→ＩＰルータ２ｄ→ＩＰルータ２ｅの経路でトラヒックが流れているとする。また、ＩＰルータ２ｄ，２ｅ間の経路が輻輳しており、その結果として、ｘ，ｙ間のＱｏＳが低下しているとする。
【０００８】
このとき、オーバーレイノード１ａ，１ｂ，１ｃで形成されるオーバーレイネットワーク１を用いて、ｘ→ＩＰルータ２ａ→オーバーレイノード１ａ→オーバーレイノード１ｂ→オーバーレイノード１ｃ→ＩＰルータ２ｅ→ｙの経路にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【０００９】
実際、非特許文献３，４，５では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。しかし、非特許文献３と非特許文献５の技術は、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっている。非特許文献４では迂回経路を提供する中継ノード候補数を制限した場合を評価しているが、こちらもオーバーレイネットワークのトポロジーをフルメッシュとしており、かつ全てのオーバーレイノード間の品質情報が必要である。つまり非特許文献３から非特許文献５の技術はオーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
【００１０】
すなわち、オーバーレイノードの総数が大きい場合には、フルメッシュでネットワークを構成することはスケーラビリティの観点から困難であるという問題がある。
【００１１】
【非特許文献１】Ｌ．Ｚｈｉ  ａｎｄ  Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔ−ｗｏｒｋｓ，”ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ  ２００４．
【非特許文献２】ＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェクト研究報告書，第１７部，２００２．
【非特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献４】Ｓ．Ｒｅｗａｓｋａｒ  ａｎｄ  Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ  ｔｈｅ  Ｓｃａｌａｂｉｌｉｔｙ  ｏｆ  Ｏｖｅｒｌａｙ  Ｒｏｕｔｉｎｇ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，”Ｐｒｏｃ．ＰＡＭ２００４．Ａｐｒｉｌ  ２００４．
【非特許文献５】Ｓ．Ｂａｎｅｒｊｅｅ，  Ｔ．Ｇ．Ｇｒｉｆｉｎ  ａｎｄ  Ｍ．Ｐｉａｓ，  “Ｔｈｅ  Ｉｎｔｅｒｄｏｍａｉｎ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ＰｌａｎｅｔＬａｂ  Ｎｏｄｅｓ，”  Ｐｒｏｃ．  ＰＡＭ２００４，Ａｐｒｉｌ  ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１２】
解決しようとする問題点は、従来の技術では、オーバーレイノードの総数が大きい場合には、フルメッシュでオーバーレイネットワークを構成することはスケーラビリティの観点から困難である点である。
【００１３】
本発明の目的は、これら従来技術の課題を解決し、スケーラブルなオーバーレイネットワークの形成を可能とすることである。
【課題を解決するための手段】
【００１４】
上記目的を達成するため、本発明では、インターネット等のＩＰネットワークに接続するいくつかのオーバーレイノードによって構築される論理網であるオーバーレイネットワークにおいて、それらオーバーレイノードの内、例えば、十分なリソース（帯域、ＣＰＵ等）があり、ネットワークへの参加・離脱を頻繁に行わないノードのいくつかをスーパーノードとし、スーパーノード間を論理的に接続してスーパーノードネットワーク層を形成し、その他のオーバーレイノードを一般ノードとして、各一般ノードは、例えば、自身からの距離（往復遅延時間ＲＴＴ：Ｒｏｕｎｄ−Ｔｒｉｐ−Ｔｉｍｅ等）が最も近いスーパーノードに所属させ、スーパーノードと一般ノード間を論理的に接続し、一般ノード群が存在する階層を一般ノードネットワーク層として形成し、オーバーレイネットワーク上に、スーパーノードネットワーク層と一般ノードネットワーク層の２階層を形成することを特徴とする。尚、各ノードを２次元の幾何学的な座標空間にマッピングし、すなわち、各ノードには２次元の座標位置を与え、各スーパーノードは、自身を中心に２次元空間を角度θ＝π／３で空間を６つのセクタに分割し、セクタｊ（ｊ＝１〜６）の空間に位置する他のスーパーノードの中から自身に最も距離が近いスーパーノードを隣接スーパーノードとして論理的に接続してスーパーノード層を形成する。
【発明の効果】
【００１５】
本発明によれば、全てのノード間でフルメッシュでネットワークを構成することなく、スケーラブルなオーバーレイネットワークを構成することが可能となり、ＱｏＳ向上を可能とするトラヒックエンジニアリングが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、ＩＰネットワーク上にオーバーレイネットワークを設けたネットワーク構成例を示すブロック図であり、図２は、図１におけるオーバーレイネットワーク上に本発明に係るスーパーノード層を形成したネットワーク構成例を示す説明図、図３は、図２におけるスーパーノード層での経路選択手順例を示す説明図、図４は、図２におけるスーパーノード層での経路制御手順例を示す説明図、図５は、本発明に係るスーパーノード層を形成するスーパーノードの構成例を示すブロック図、図６は、本発明に係る一般ノード層を形成する一般ノードの構成例を示すブロック図、図７は、図２におけるスーパーノード層での隣接スーパーノード更新手順の第１の例を示す説明図、図８は、図２におけるスーパーノード層での隣接スーパーノード更新手順の第２の例を示す説明図、図９は、本発明に係るオーバーレイネットワークの形成手順例を示すフローチャートである。
【００１７】
図１におけるオーバーレイノード１ａ，１ｂ，１ｃのそれぞれは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、図５におけるスーパーノード５０と図６における一般ノード６０に示される各処理手段を具備した構成となる。
【００１８】
例えば、図５におけるスーパーノード５０として機能する場合には、プログラムされたコンピュータ処理機能として、座標管理部５０ａ、隣接ノード決定部５０ｂ、パケット転送部５０ｃ、一般ノード管理部５０ｄによる処理を実行し、図６における一般ノード６０として機能する場合には、プログラムされたコンピュータ処理機能として、スーパーノード選択部６０ａ、座標保持部６０ｂ、ショートカット経路決定部６０ｃ、パケット転送部６０ｄによる処理を実行する。
【００１９】
図１に示すように、ＩＰルータ２ａ〜２ｅで構成されるＩＰネットワーク（図中「ＩＰ−ＮＷ」と記載）３において、ｘからｙに向けて、ＩＰルータ２ａ，２ｄ，２ｅの経路でトラヒックが流れている際、この経路上のＩＰルータ２ｄ，２ｅ間で輻輳が発生すると、その結果として、ｘ，ｙ間のＱｏＳが低下する。
【００２０】
このとき、オーバーレイノード（以下、単にノードとも記載する）１ａ，１ｂ，１ｃで形成されるオーバーレイネットワーク（図中「Ｏｖｅｒｌａｙ−ＮＷ」と記載）１を用いて、ｘ→ＩＰルータ２ａ→オーバーレイノードａ→オーバーレイノードｃ→ＩＰルータ２ｅ→ｙの経路でトラヒックを迂回させることで、上述の輻輳を回避することができる。
【００２１】
しかし、この際、オーバーレイノード１ａからオーバーレイノード１ｃへ直接転送した場合の遅延時間よりも、オーバーレイノード１ａから一旦オーバーレイノード１ｂへ転送し、オーバーレイノード１ｂからオーバーレイノード１ｃへ転送するという迂回経路を経由した方が遅延時間が小さい場合がある。例えばインターネットでのドメイン間ルーチングポリシーなどに起因する場合である。
【００２２】
この場合、オーバーレイノード１ａ，１ｂ，１ｃで形成されるオーバーレイネットワークを用いて、実線矢印で表される経路（オーバーレイノード１ａ→オーバーレイノード１ｂ→オーバーレイノード１ｃ）にトラヒックを迂回させることができれば、ＱｏＳを向上できる。
【００２３】
そこで、本実施例では、図２に例示するように、このようなオーバーレイネットワークにおいて、各オーバーレイノードのうち、予め定められた選定条件に基づき、いくつかのオーバーレイノードをスーパーノードとして選定し、各スーパーノードは、各スーパーノード間で論理的な接続を行いスーパーノードネットワーク層（図中および以下「スーパーノード層」と記載）２１を形成し、また、選定条件に合わないその他のオーバーレイノードを一般ノードとし、各一般ノードは、スーパーノードのいずれか一つと論理的に接続して一般ノードネットワーク層（図中および以下「一般ノード層」と記載）２２を形成し、オーバーレイネットワークをスーパーノード層２１と一般ノード層２２の２階層で形成する。
【００２４】
尚、ここでは、いずれのオーバーレイノードをスーパーノードとして選定するかを決定するための条件としては、例えば、十分なリソース（帯域や、ＣＰＵ性能等）があり、ネットワークへの参加・離脱を頻繁に行わないものをスーパーノードとして選定する条件とする。
【００２５】
そして、このようなスーパーノードの選定は、このネットワークの管理者が選定しても良いし、また、各オーバーレイノードがオーバーレイネットワークに接続する際に、自身がスーパーノードになるか否かを選択し、スーパーノードになるのであればその旨を既に接続している各オーバーレイノードに通知しても良い。
【００２６】
また、一般ノードは、複数のスーパーノードの内、自身からの最短ＲＴＴ（Ｒｏｕｎｄ−Ｔｒｉｐ−Ｔｉｍｅ；往復遅延時間）を含む最良通信効率となるスーパーノードを特定し、特定したスーパーノードと論理的に接続し、当該スーパーノードに所属させる。尚、最良通信効率となるスーパーノードの特定に、最短ＲＴＴの代わりに、片道遅延時間や、パケット損失率を距離にマッピングしたもの（パケット損失率が大きければ距離が大きくなるような関数を予め用意して算出する）、あるいは、後述の図６におけるスーパーノード選択部６０ａの処理動作により座標位置から求めた距離を用いても良い。
【００２７】
さらに、オーバーレイネットワークにおいて、各オーバーレイノードを２次元の幾何学的な座標空間にマッピングし、すなわち、各オーバーレイノードに２次元の座標位置を与え、各オーバーレイノードにおいて自身の２次元の座標位置を記憶し、特に、各スーパーノードは、記憶した自身の２次元の座標位置情報を読み出し、自身を中心に２次元空間を角度θ＝π／３で空間を６つのセクタに分割し、セクタｊ（ｊ＝１〜６）の空間に位置する他のスーパーノードから当該スーパーノードの２次元の座標位置情報を取得し、自身に最も座標位置が近いスーパーノードを当該セクタｊにおける隣接スーパーノードとして特定し、特定した隣接スーパーノードと論理的に接続する。
【００２８】
すなわち、図２に示すように、スーパーノード層２１において、各スーパーノードを中心に６つのセクタに区切る。このようにして構成される隣接ネットワークはＹａｏグラフと呼ばれ、幾何学空間上で最短のパスを持つスパニングツリー（枝分かれしていく木）を構成できることが知られている。
【００２９】
このようなスーパーノード層２１におけるノード間接続を行う際、各スーパーノードは，一定周期毎あるいは新規スーパーノードの参加や既存スーパーノードの離脱といった何らかの事象が発生した際に、その事象の発生を契機に、自身を中心とした各セクタｊにおける現在の隣接スーパーノードと、セクタｊ内の他のスーパーノードとの距離を比較し、もし、現在の隣接スーパーノードよりも近い距離に他のスーパーノードが存在すれば、その中で最も近いスーパーノードを、新たな隣接スーパーノードとして、更新していく。
【００３０】
また、各一般ノードは、予め記憶装置に記憶した自身の２次元の座標位置情報を、論理的に接続したスーパーノードに通知すると共に、このスーパーノードの２次元の座標位置情報を取得して、自身の２次元の座標位置情報とを用いて、自身と当該スーパーノード間の距離（第１の距離）を算出すると共に、論理的に接続したスーパーノードから、同じスーパーノードに接続した他の一般ノードの２次元の座標位置情報を取得して、取得した他の一般ノードの２次元の座標位置情報と当該スーパーノードの２次元の座標位置情報とを用いて、各他の一般ノードと当該スーパーノード間の距離（第２の距離）を算出し、さらに、論理的に接続したスーパーノードから、同じスーパーノードに接続した他の一般ノードの２次元の座標位置情報を取得して、取得した他の一般ノードの２次元の座標位置情報と自身の２次元の座標位置情報とを用いて、各他の一般ノードとの距離（第３の距離）を算出し、そして、算出した第１の距離と第２の距離を加算し、加算した値と第３の距離とを比較して、第１の距離と第２の距離を加算した値が、第３の距離より大きくなる他の一般ノードがあれば、この他の一般ノードと自身との間を論理的に接続してショートカットの経路を作成する。このように、一般ノード層２２において、あるスーパーノードｘに属する一般ノードｉ_ｘは、同じスーパーノードｘに属する他の一般ノードｊ_ｘとの距離ｄ（ｉ_ｘ，ｊ_ｘ）を測定し、その値と、ｄ（ｉ_ｘ，ｘ）（一般ノードｉ_ｘとスーパーノードｘの距離）にｄ（ｊ_ｘ，ｘ）（一般ノードｊ_ｘとスーパーノードｘの距離）を加えた値を比較し、もし、「ｄ（ｉ_ｘ，ｊ_ｘ）＜ｄ（ｉ_ｘ，ｘ）+ｄ（ｊ_ｘ，ｘ）」ならば、一般ノードｉ_ｘと一般ノードｊ_ｘの間を論理的に接続してショートカットの経路を作成する。
【００３１】
このような構成において、あるスーパーノードｘに属する一般ノードｘ_ｉが、別のスーパーノードｙに接続した一般ノードｙ_ｊとパケット通信する際、一般ノードｘ_ｉが、まずスーパーノードｘにパケットを送出し、パケットを受け取ったスーパーノードｘがスーパーノードｙまでスーパーノード層を介してパケットを転送し、スーパーノードｙは一般ノードｙ_ｊにパケットを送出する。
【００３２】
すなわち、図３に示すように、一般ノード（１）から一般ノード（４）にパケットを転送する際、経路は、Ａ−Ｄ−Ｆとなる。尚、ここでの経路Ｄについては、必ずしもスーパーノード（１）とスーパーノード（２）が直接論理的に接続されていなくても良く、間に何ホップかあっても良い。その際の中継技術については図４を用いて後述する。
【００３３】
上述のショートカット経路についても、図３に示すように、一般ノード（１）から一般ノード（２）へは経路Ｃのショートカット経路を通る。また、一般ノード（３）から一般ノード（４）への経路は、ショートカットよりもスーパーノード（２）経由の方が近いため、そういう経路（Ｅ−Ｆ）を通っている。
【００３４】
このようなスーパーノード層において、スーパーノードｘが送信元スーパーノード、スーパーノードｙが着信先スーパーノードであるとし、スーパーノードｘからスーパーノードｙへ転送されるパケットが今、図４に示すように、中継スーパーノードｕにあるとすると、この中継スーパーノードｕは、隣接スーパーノードｖ_１，ｖ_２，…のうち、座標空間上において、自身の座標ｕと着信先スーパーノードの座標ｙとを結ぶ線ｕ−ｙを挟む両側から１つずつ、角度ｖ_ｊ−ｕ−ｙが最小になる隣接スーパーノードｖ_ｊと、角度ｙ−ｕ−ｖ_ｋが最小となる隣接スーパーノードｖ_ｋを探索し、ランダムに、隣接スーパーノードｖ_ｊまたは隣接スーパーノードｖ_ｋのいずれかを次ホップノードとしてパケットを転送する。
【００３５】
以下、図５，図６を用いて、このようなスーパーノード層と一般ノード層の２層からなるオーバーレイネットワークを形成するスーパーノード５０と一般ノード６０の構成と処理動作について説明する。
【００３６】
図５に示すように、スーパーノード５０は、プログラムされたコンピュータ処理機能として、座標管理部５０ａ、隣接ノード決定部５０ｂ、パケット転送部５０ｃ、一般ノード管理部５０ｄを具備し、座標管理部５０ａは、自身の座標位置を図示していない記憶装置に保持するとともに、現在ネットワークに参加中の他のスーパーノードに座標位置を問い合わせてその情報を取得して保持しておき、かつ、各スーパーノードの座標情報を、隣接ノード決定部５０ｂに通知する。
【００３７】
通知を受けた隣接ノード決定部５０ｂは、自身を中心に２次元空間を角度θ＝π／３で空間を６つのセクタに分割し、セクタｊ（ｊ＝１〜６）の空間に位置する他のスーパーノードからそれぞれの座標情報を取得し、各座標情報から算出される距離を比較し、自身に最も近いスーパーノードを隣接スーパーノードとして選定し、論理的に接続する。
【００３８】
尚、隣接ノード決定部５０ｂは、隣接スーパーノードの選定を以下の手順で更新していく。すなわち、自身を中心とした各セクタｊにおける現在の隣接スーパーノードと、セクタｊ内の他のスーパーノードとの距離を比較し、もし、現在の隣接スーパーノードよりも近い距離に他のスーパーノードが存在すれば、その中で最も近いスーパーノードを、新たな隣接スーパーノードとして、更新していく。
【００３９】
この動作は、一定周期毎に行うか、何らかの事象を検知した毎（新規スーパーノードの参加、既存スーパーノードの離脱等）に行う。その様子を図７、８を用いて説明する。
【００４０】
図７は、新規スーパーノードが参加した場合の隣接スーパーノードの選定更新処理動作例を示しており、既にＮ１、Ｎ２、Ｎ３というスーパーノードが存在しているとし、Ｎ１、Ｎ２、Ｎ３が実線で示すように論理的に接続しているとする。
【００４１】
ここで、Ｎ１−Ｎ２間の論理リンクが切断され、同時にＬという新規スーパーノードが参加したケースを考える。この場合、各スーパーノードの隣接ノードテーブルは、図７のように更新される。
【００４２】
例えば、Ｎ１の隣接スーパーノードはＬとＮ３となる。尚、図７では、ｉｎとｏｕｔの両方を記載しているが、方向別にテーブルを持っていることを意味し、ｉｎ、ｏｕｔの両者とも、ＬとＮ３が新規に隣接スーパーノードとしてエントリされている。
【００４３】
図８は、既存スーパーノードＬが離脱した場合の隣接スーパーノードの選定更新処理動作例を示しており、この場合、図７に示す例とは逆にして、隣接ノードテーブルが更新されることになる。
【００４４】
図５のスーパーノード５０における一般ノード管理部５０ｄは、自身と論理的に接続され、配下に属する一般ノードのアドレスと座標位置を取得して記憶管理している。
【００４５】
図５のスーパーノード５０におけるパケット転送部５０ｃは、自身の配下の一般ノード、あるいは隣接するスーパーノードからパケットを受信したら、そのパケットの宛先を読み込み、自身の配下の他の一般ノード向けであれば、一般ノード管理部５０ｄで管理している自身の配下に属する一般ノードのアドレスと座標位置を参照して、当該ノードにパケットを送出し、他のスーパーノード向けのパケットであれば、以下の手順に従って、パケットを転送する。
【００４６】
スーパーノードｙへ転送されるパケットが、現在、自身のところ（スーパーノードｕとする）にあるとすると、スーパーノードｕは、隣接スーパーノードｖ_１，ｖ_２，…のうち、座標空間上において、自身の座標ｕと着信先スーパーノードの座標ｙとを結ぶ線ｕ−ｙを挟む両側から１つずつ、角度ｖ_ｊ−ｕ−ｙが最小になる隣接スーパーノードｖ_ｊと、角度ｙ−ｕ−ｖ_ｋが最小となる隣接スーパーノードｖ_ｋを探索し、ランダムに、隣接スーパーノードｖ_ｊまたは隣接スーパーノードｖ_ｋのいずれかを次ホップノードとしてパケットを転送する。
【００４７】
次に、一般ノードの動作について、図６を用いて説明する。一般ノード６０は、座標管理部６０ａにおいて、自身の座標位置を保持している。ネットワークへの参加時に、スーパーノード選択部６０ａは、例えば、各スーパーノードから各スーパーノードの座標位置を取得し、座標管理部６０ａで保持している自身の座標位置と比べて、最も距離の近いスーパーノードを探索し、それを自身の属するスーパーノードとして選択して、その旨を、選択したスーパーノードの一般ノード管理部５０ｄに通知する。
【００４８】
また、ショートカット経路決定部６０ｃでは、自身（一般ノードｉ_ｘ）が論理的に接続して配下として属するスーパーノードｘから、このスーパーノードｘの配下に属する他の一般ノードの座標位置を読み出し、自身（一般ノードｉ_ｘ）と他の一般ノードｊ_ｘとの第３の距離ｄ（ｉ_ｘ，ｊ_ｘ）を計算し、その値「ｄ（ｉ_ｘ，ｊ_ｘ）」と、自身（一般ノードｉ_ｘ）とスーパーノードｘとの第１の距離「ｄ（ｉ_ｘ，ｘ）」に他の一般ノードｊ_ｘとスーパーノードｘとの第２の距離「ｄ（ｊ_ｘ，ｘ）」を加えた値を比較し、もし、「ｄ（ｉ_ｘ、ｊ_ｘ）＜ｄ（ｉ_ｘ、ｘ）+ｄ（ｊ_ｘ、ｘ）」で、第１の距離と第２の距離を加算した値が第３の距離より大きくなるならば、自身（一般ノードｉ_ｘ）と一般ノードｊ_ｘの間を論理的に接続してショートカットの経路を作成する。
【００４９】
パケット転送部６０ｄでは、自身がパケットを送出する際に、宛先が同じスーパーノード配下か否かを調べ、もしそうならば、ショートカット経路決定部６０ｃに問い合わせて、ショートカット経路があるか否かを判定して、ショートカット経路があるならば直接宛先へパケットを送出し、ショートカット経路がなければ、自身が配下として属するスーパーノードへパケットを転送する。また、他スーパーノードに属する一般ノードへパケットを送出する場合にも、自身が配下として属するスーパーノードへパケットを転送する。
【００５０】
次に、図９を用いて、このようなスーパーノード層と一般ノード層からなるオーバーレイネットワークの形成手順について説明する。
【００５１】
まず、オーバーレイネットワークを構成する各オーバーレイノードから、スーパーノードの選定を行う（ステップＳ９０１）。ここでは、例えば、十分なリソース（帯域、ＣＰＵ等）があり、ネットワークへの参加・離脱を頻繁に行わないノードのいくつかをスーパーノードとして選定するが、このようなスーパーノードの選定は、このネットワークの管理者が選定しても良いし、各オーバーレイノードがネットワークに接続する際に、自身がスーパーノードになるか否かを選択し、スーパーノードになるのであればその旨を既に接続しているノードに通知しても良い。
【００５２】
次に、各ノードを２次元の幾何学的な座標空間にマッピングし、すなわち、各オーバーレイノードに２次元の座標位置を与えて保持させ、各スーパーノードは、自身を中心に２次元空間を角度θ＝π／３で空間を６つのセクタに分割し、セクタｊ（ｊ＝１〜６）の空間に位置する他のスーパーノードから当該スーパーノードの座標位置を取得し、各座標位置から自身との距離を算出し、自身に最も距離が近いスーパーノードを隣接スーパーノードとして特定して論理的に接続することで、スーパーノード層を形成する（ステップＳ９０２）。
【００５３】
そして、その他のオーバーレイノードは、一般ノードとして、例えば、自身とのＲＴＴが最短であるスーパーノードを自身からの距離が最も近いスーパーノードとして特定し、特定したスーパーノードに論理的に接続して、一般ノード層を形成する（ステップＳ９０３）。このようにして、オーバーレイネットワークをスーパーノード層と一般ノード層の２階層で形成とする。
【００５４】
以上、図１〜図９を用いて説明したように、本例では、オーバーレイネットワークをスーパーノード層と一般ノード層の２階層で形成する。このことにより、全てのノード間でフルメッシュでネットワークを構成することなく、スケーラブルなオーバーレイネットワークを構成することが可能となり、ＱｏＳ向上を可能とするトラヒックエンジニアリングが可能となる。
【００５５】
尚、本発明は、図１〜図９を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、スーパーノード５０における各処理部（座標管理部５０ａ、隣接ノード決定部５０ｂ、パケット転送部５０ｃ、一般ノード管理部５０ｄ）および一般ノード６０における各処理部（スーパーノード選択部６０ａ、座標保持部６０ｂ、ショートカット経路決定部６０ｃ、パケット転送部６０ｄ）は、ＣＰＵや記憶装置からなる、プログラムにより各機能の実行が可能なコンピュータで構成するものとしているが、各処理部の全てもしくは幾つかを、論理素子回路からなるハードウェア構成としても良い。
【００５６】
また、本例でのコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【００５７】
【図１】ＩＰネットワーク上にオーバーレイネットワークを設けたネットワーク構成例を示すブロック図である。
【図２】図１におけるオーバーレイネットワーク上に本発明に係るスーパーノード層を形成したネットワーク構成例を示す説明図である。
【図３】図２におけるスーパーノード層での経路選択手順例を示す説明図である。
【図４】図２におけるスーパーノード層での経路制御手順例を示す説明図である。
【図５】本発明に係るスーパーノード層を形成するスーパーノードの構成例を示すブロック図である。
【図６】本発明に係る一般ノード層を形成する一般ノードの構成例を示すブロック図である。
【図７】図２におけるスーパーノード層での隣接スーパーノード更新手順の第１の例を示す説明図である。
【図８】図２におけるスーパーノード層での隣接スーパーノード更新手順の第２の例を示す説明図である。
【図９】本発明に係るオーバーレイネットワークの形成手順例を示すフローチャートである。
【符号の説明】
【００５８】
１：オーバーレイネットワーク（Ｏｖｅｒｌａｙ−ＮＷ）、１ａ〜１ｃ：オーバーレイノード、２ａ〜２ｅ：ＩＰルータ、３：ＩＰネットワーク（ＩＰ−ＮＷ）、２１：スーパーノード層、２２：一般ノード層、５０：スーパーノード、５０ａ：座標管理部、５０ｂ：隣接ノード決定部、５０ｃ：パケット転送部、５０ｄ：一般ノード管理部、６０：一般ノード、６０ａ：スーパーノード選択部、６０ｂ：座標保持部、６０ｃ：ショートカット経路決定部、６０ｄ：パケット転送部。
【図１】
0004743640.tif 000002
【図２】
0004743640.tif 000003
【図３】
0004743640.tif 000004
【図４】
0004743640.tif 000005
【図５】
0004743640.tif 000006
【図６】
0004743640.tif 000007
【図７】
0004743640.tif 000008
【図８】
0004743640.tif 000009
【図９】
0004743640.tif 000010