(57)【要約】【課題】スケーラブルに高品質・高信頼なオーバーレイネットワークを構成し、エンド・ツー・エンドの通信品質と信頼性を効率的に向上させる。【解決手段】オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定する際の手順として、予め、オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順（ステップＳ３０１）と、新規参加ノードの接続先となる既存ノードを、記憶装置に記憶したリスト情報を参照して決定する決定処理手順（ステップＳ３０２）とを含み、かつ、ステップ３０２における決定処理手順は、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を含む。【選択図】図３
2009260872.tif 000002
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御方法であって、
プログラムされたコンピュータの処理実行手順として、
予め、上記オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順と、
上記新規参加ノードの接続先となる既存ノードを、上記記憶装置に記憶したリスト情報を参照して決定する決定処理手順と
を含み、
かつ、上記決定処理手順は、上記リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を含む
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項２】
プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御方法であって、
プログラムされたコンピュータ処理手順として、
上記新規参加ノードが、上記オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードに対して、当該既存ノードの識別情報と当該既存ノードの接続先の数である次数とを問い合わせるメッセージと予め定められたホップ数を送信する送信手順と、
上記メッセージとホップ数を受信した既存ノードが、受信したメッセージとホップ数を、隣接する既存ノードに対して転送する転送手順と、
上記メッセージを受信した各既存ノードから上記新規参加ノードに対して、各既存ノードの識別情報と次数を返信する返信手順と、
上記転送手順と上記返信手順を、上記ホップ数以内の範囲の各既存ノードで繰り返す手順と、
上記新規参加ノードが、各既存ノードから受信した当該既存ノードの識別情報と次数とを対応付けて記述したリスト情報を生成して記憶装置に記憶する手順と、該記憶装置に記憶したリスト情報を参照して、自ノードの接続先となる既存ノードを決定する決定処理手順とを含み、
かつ、
上記決定処理手順は、上記リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を含む
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項３】
請求項２に記載のオーバーレイネットワークのトポロジー制御方法であって、
上記各既存ノードは、上記新規参加ノードに対して、上記識別情報と次数と共に、自装置の帯域使用率およびＣＰＵ使用率を含むリソース使用率を返信する手順を実行し、
上記新規参加ノードは、返信のあった既存ノードの内、上記リソース使用率が予め定められた閾値よりも良いものに対して、上記決定処理手順による接続先の決定処理を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項４】
請求項２に記載のオーバーレイネットワークのトポロジー制御方法であって、
上記既存ノードは、自身の識別情報と次数および帯域使用率とＣＰＵ使用率を含むリソース使用率をｉｎｄｅｘとして分散ハッシュテーブルに登録しておき、
上記新規参加ノードは、上記分散ハッシュテーブルを検索して予め定められた各々異なる複数の次数とリソース情報を持つ既存ノードを抽出し、抽出した各既存ノードに対して上記決定処理手順を実行して接続先の既存ノードを選択する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項５】
プログラムされたコンピュータ処理により、それぞれ複数のスーパーノードと各スーパーノードに接続される複数の一般ノードからなる複数のクラスタで構成されたオーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御方法であって、
プログラムされたコンピュータ処理手順として、
上記スーパーノードが、自身の属するクラスタ内で一般ノードとして存在している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを記憶装置に記憶する手順と、
新規参加ノードが、自身の属するクラスタ内のスーパーノードから、当該クラスタ内の各既存ノードの識別情報と次数を取得し、取得した次数と識別情報を用いて、自ノードの接続先となる既存ノードを決定する決定処理手順と
を含み、
かつ、上記決定処理手順は、上記リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を含む
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項６】
請求項５に記載のオーバーレイネットワークのトポロジー制御方法であって、
各スーパーノードは、自身の属するクラスタ内の各既存ノードの識別情報と数と共に、当該既存ノードの帯域使用率およびＣＰＵ使用率を含むリソース使用率を記憶装置に記憶し、
上記新規参加ノードは、自身の属するクラスタ内のスーパーノードから、当該クラスタ内の各既存ノードの識別情報および次数と共に上記リソース使用率を取得し、各既存ノードの内、取得したリソース使用率が予め定められた閾値よりも良いものに対して、上記決定処理手順による接続先の決定処理を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項７】
プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御方法であって、
プログラムされたコンピュータ処理を実行する管理サーバ装置が、
予め、上記オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順と、
上記新規参加ノードの接続先となる既存ノードを、上記記憶装置に記憶したリスト情報を参照して決定し当該新規参加ノードに通知する決定処理手順と
を実行すると共に、
上記決定処理手順として、上記リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項８】
プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御方法であって、
管理サーバ装置が、
予め、上記オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順と、
上記新規参加ノードからの要求に応じて、上記記憶装置に記憶したリスト情報を当該新規参加ノードに送信する送信処理手順とを実行し、
上記新規参加ノードが、上記管理サーバから受信したリスト情報を参照して、当該新規参加ノードの接続先となる既存ノードを決定する決定処理手順を実行すると共に、
上記新規参加ノードは、上記決定処理手順として、上記リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項９】
請求項１から請求項８のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
上記決定処理手順では、
全ての既存ノード数をｎ、既存ノードｊ（１＜ｊ≦ｎ）の次数をｋｊとし、かつ、次数の大きい順にｋ１＋ｋ２＋，・・・，＋ｋｎとし、
該次数ｋｊの既存ノードｊを、
確率Ｐ（ｋｊ）＝ｋｊ÷（ｋ１＋ｋ２＋，・・・，＋ｋｎ）で選択する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１０】
請求項９に記載のオーバーレイネットワークのトポロジー制御方法であって、
上記決定処理手順は、
０から１の間の乱数ｘを生成する手順と、
生成した乱数ｘを用いた｛（ｋ１＋ｋ２＋，・・・，＋ｋｊ−１）÷｛ｋ１＋ｋ２＋，・・・，＋ｋｎ）｝＜ｘ≦｛（ｋ１＋ｋ２＋，・・・，＋ｋｊ）÷｛ｋ１＋ｋ２＋，・・・，＋ｋｎ）｝の条件式から既存ノードｊを選択する手順と
を含むことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１１】
請求項１０に記載のオーバーレイネットワークのトポロジー制御方法であって、
上記決定処理手順では、
予め定められたそれぞれ異なるｍ（１＜ｍ≦ｎ）個の上記乱数ｘを用いて上記決定処理手順を繰り返し、ｍ個の既存ノードを選択する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１２】
請求項７から請求項１１のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
各既存ノードは、予め定められた周期Ｔ１毎に予め定められた確率で上記管理サーバに、自ノードの識別情報と次数を送信する手順を実行し、
上記管理サーバは、予め定められた周期Ｔ１毎に上記既存ノードから受信した当該既存ノードの識別情報と次数とを用いて上記記憶装置に記憶したリスト情報を更新する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１３】
請求項７から請求項１２のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
各既存ノードは、予め定められた周期Ｔ２毎に、自装置の帯域使用率およびＣＰＵ使用率を含むリソースに空きがあるか否かを判別する手順と、リソースに空きがあれば、上記管理サーバに、自ノードの識別情報と次数を送信する手順とを実行し、
上記管理サーバは、予め定められた周期Ｔ２毎に上記既存ノードから受信した当該既存ノードの識別情報と次数とを用いて上記記憶装置に記憶したリスト情報を更新する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１４】
請求項１２もしくは請求項１３のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
上記管理サーバは、
上記リストの更新毎に更新前のリスト情報も記憶装置に記憶しておき、
上記決定処理手順では、
上記記憶装置に記憶した複数のリスト情報からいずれかをランダムに選択し、選択したリスト情報を用いて上記新規参加ノードの接続先となる既存ノードの決定処理を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１５】
請求項２から請求項１４のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
上記新規参加ノードは、
上記決定処理手順で決定したｍ’個の既存ノードから、
自装置との間の遅延時間とパケット損失率およびスループットを含む品質メトリックが最も良いものから順にｍ個抽出し、該ｍ個の既存ノードを接続先として決定する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１６】
請求項２から請求項１４のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
上記新規参加ノードは、
上記決定処理手順で決定したｍ’個の既存ノードからランダムにｍ個抽出し、該ｍ個の既存ノードを接続先として決定する手順を実行する
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１７】
請求項１から請求項１６のいずれかに記載のオーバーレイネットワークのトポロジー制御方法であって、
プログラムされたコンピュータ処理手順として、
予め定められた周期毎、もしくは、予め定められたネットワークの状態変化を検出する毎に、予め定められた既存ノードに対して上記決定処理手順を実行し、当該既存ノードの接続先の変更を行う手順を含む
ことを特徴とするオーバーレイネットワークのトポロジー制御方法。
【請求項１８】
コンピュータに、請求項１から請求項１７のいずれかに記載のオーバーレイネットワークのトポロジー制御方法における各手順を実行させるためのプログラム。
【請求項１９】
プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定するオーバーレイネットワークのトポロジー制御システムであって、
プログラムされたコンピュータの処理実行手段として、
請求項１から請求項１７のいずれかに記載のオーバーレイネットワークのトポロジー制御方法における各手順を実行する手段を具備したことを特徴とするオーバーレイネットワークのトポロジー制御システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットにおけるエンド・ツー・エンド（ｅｎｄ  ｔｏ  ｅｎｄ）の通信品質および信頼性を向上させる技術に係り、特にＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質、信頼性を効率的に向上させるのに好適な技術に関するものである。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Ｖｏｉｃｅ  ｏｖｅｒ  ＩＰ）やストリーミングに代表されるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）に敏感な実時間アプリケーション等の収容も急速に発展している。
【０００３】
これに伴い、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。
【０００４】
しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００５】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００６】
（２）インターネットは管理主体の異なる複数のＡＳ（Ａｕｔｏｎｏｍｏｕｓ  Ｓｙｓｔｅｍ）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００７】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えば、非特許文献１に記載の、オーバーレイネットワークによるＱｏＳ管理技術が注目されている。
【０００８】
オーバーレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００９】
このようなオーバーレイネットワークによるＱｏＳ管理の基本的な概念を図８に例示する。図８に示すネットワーク（図中「ＩＰ−ＮＷ」と記載）８４において、ノード８１ａからノード８１ｃに向けて通信したい場合を考える。
【００１０】
このとき、ノード８１ａからノード８１ｃへ直接転送した場合（ノード８１ａ→ＩＰルータ８２ａ→ＩＰルータ８２ｄ→ＩＰルータ８２ｅ→ノード８１ｃ）の遅延時間よりも、ノード８１ａから一旦ノード８１ｂへ転送し、ノード８１ｂからノード８１ｃへ転送するという迂回経路（ノード８１ａ→ＩＰルータ８２ａ→ＩＰルータ８２ｂ→ＩＰルータ８２ｃ→ノード８１ｂ→ＩＰルータ８２ｃ→ＩＰルータ８２ｅ→ノード８１ｃ）を経由した方が、遅延時間が小さい場合がある（例えばインターネットでのドメイン間ルーチングポリシーなどに起因する）。
【００１１】
このとき、各ノード８１ａ，８１ｂ，８１ｃをオーバーレイノードとし、このオーバーレイノード８１ａ，８１ｂ，８１ｃで形成されるオーバーレイネットワーク８３を用いて、図８中の実線矢印で表される経路（オーバーレイノード８１ａ→オーバーレイノード８１ｂ→オーバーレイノード８１ｃ）にトラヒックを迂回させることができれば、ＱｏＳを向上できる。
【００１２】
実際、非特許文献３，４，５では、上記のような迂回経路が実績において多数存在していることを実測に基づいて示している。
【００１３】
しかし、非特許文献３と非特許文献５の結果は、オーバーレイネットワークのトポロジーをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
【００１４】
すなわち、オーバーレイノードの総数が大きい場合には、フルメッシュでネットワークを構成することはスケーラビリティの観点から困難であるという問題がある。
【００１５】
一方、フルメッシュとする代わりにオーバーレイネットワークにおけるトポロジーを決定・制御する技術として、ＩＰレイヤのトポロジーを考慮する技術がある。
【００１６】
これは、オーバーレイネットワーク上で仮に１ホップでノードが繋がっていたとしても、ＩＰレイヤで何ホップもしているようであると遅延時間が大きくなってしまい、高品質化の観点から望ましくないからである。
【００１７】
このような検討はあるものの、このように構成されたオーバーレイネットワーク上で、例えばあるノードが離脱した場合には接続性が維持できない可能性があり、高信頼性の観点も考慮してトポロジーを構成する必要がある。
【００１８】
【非特許文献１】Ｌ．Ｚｈｉ  ａｎｄ  Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔ−ｗｏｒｋｓ，”ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ  ２００４．
【非特許文献２】ＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェクト研究報告書，第１７部，２００２．
【非特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献４】Ｓ．Ｒｅｗａｓｋａｒ  ａｎｄ  Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ  ｔｈｅ  Ｓｃａｌａｂｉｌｉｔｙ  ｏｆ  ｏｖｅｒｌａｙ  Ｒｏｕｔｉｎｇ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，”Ｐｒｏｃ．ＰＡＭ  ２００４．Ａｐｒｉｌ  ２００４．
【非特許文献５】Ｓ．Ｂａｎｅｒｊｅｅ，Ｔ．Ｇ．Ｇｒｉｆｉｎ  ａｎｄ  Ｍ．Ｐｉａｓ，  “Ｔｈｅ  Ｉｎｔｅｒｄｏｍａｉｎ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ＰｌａｎｅｔＬａｂ  Ｎｏｄｅｓ，”  Ｐｒｏｃ．ＰＡＭ  ２００４，Ａｐｒｉｌ  ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１９】
解決しようとする問題点は、従来の例えばＩＰレイヤのトポロジーを考慮してオーバーレイネットワークのトポロジーを決定・制御する技術では、オーバーレイネットワーク上で或るノードが離脱した場合には接続性が維持できない可能性があり、高信頼性を維持することができない点である。
【００２０】
本発明の目的は、これら従来技術の課題を解決し、スケーラブルに高品質・高信頼なオーバーレイネットワークを構成し、エンド・ツー・エンドの通信品質と信頼性を効率的に向上させることである。
【課題を解決するための手段】
【００２１】
上記目的を達成するため、本発明では、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定する際、新規参加ノードが既存ノードに接続する基準を動的に制御することにより、その結果できあがったネットワークトポロジーがスケールフリー性という特性を有するものにすることによって、対障害性の高いネットワークにする。例えば、インターネットに接続するいくつかのオーバーレイノードによって構築される論理網であるオーバーレイネットワークにおいて、既に参加しているオーバーレイノードｊはｋｊ個のオーバーレイノードと接続している（次数ｋｊ）とし、オーバーレイネットワークへ新たに参加するノードは、次数ｋｊに対して定義する任意の確率分布関数Ｐ（ｋｊ）に応じた確率で接続先のノードを決定する。このように、新しいノードを追加するとき、既に存在するノードの次数ｋに比例して、接続させていくと、スケールフリーになることが知られている。本発明ではこの特性を利用しており、トポロジーに依存したネットワークの特性を接続時のノード選択アルゴリズムやパラメタによってコントロールすることができる。
【発明の効果】
【００２２】
本発明によれば、全てのノード間においてフルメッシュでネットワークを構成することなく、スケーラブルに耐障害性に優れ、かつ高品質なオーバーレイネットワークを構成することが可能となる。
【発明を実施するための最良の形態】
【００２３】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係るオーバーレイネットワークのトポロジー制御に用いる接続候補管理サーバの構成例を示すブロック図であり、図２は、本発明に係るトポロジー制御を行うオーバーレイネットワークの構成例を示す説明図である。
【００２４】
図２において、１は本発明に係るオーバーレイネットワークのトポロジー制御システムを構成する接続候補管理サーバ、２０ａ〜２０ｈは既存のオーバーレイノードであり特にオーバーレイネットワークにおけるスーパーノードネットワーク層を構成するスーパーノード、２１ａ〜２１ｋはオーバーレイネットワークにおける一般ノードを構成する既存ノード、２２はオーバーレイネットワークに新たに接続・参加する新規参加ノードである。
【００２５】
接続候補管理サーバ１、スーパーノード２０ａ〜２０ｈ、既存ノード２１ａ〜２１ｋ、新規参加ノード２２のそれぞれは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、ＣＲＴやＬＣＤ等の表示装置、キーボードやマウス等の入力装置、ＨＤＤ等の外部記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、本発明に係るオーバーレイネットワークのトポロジー制御を行う。
【００２６】
例えば、接続候補管理サーバ１は、プログラムされたコンピュータ処理を実行する手段として、図１に示すように、接続先決定部１ａ、次数管理部１ｂ、座標保持部１ｃの各処理部を有する。
【００２７】
以下、本発明に係るオーバーレイネットワークのトポロジー制御の基本的な考え方についてまず説明する。
【００２８】
本例では、新規参加ノード２２が既存ノード２１ａ〜２１ｋに接続する基準を動的に制御することにより、その結果できあがったネットワークトポロジーがスケールフリー性という特性を有するものにすることによって、対障害性の高いネットワークにしようとしている。
【００２９】
スケールフリーネットワークとは、ノードの次数（そのノードと隣接しているノード数）に関する分布（つまり次数ｋを持つノードの存在確率ｐ（ｋ））が、「ｋ＾｛−γ｝」のようなべき乗則に従うとき、スケールフリーと呼ぶ。
【００３０】
このようなネットワークは、例えば、参考文献１（「Ｒ．Ａｌｂｅｒｔ  ｅｔ  ａ１，“Ｅｒｒｏｒ  ａｎｄ  ａｔｔａｃｋ  ｔｏｌｅｒａｎｃｅ  ｏｆ  ｃｏｍｐｌｅｘ  ｎｅｔｗｏｒｋｓ，”  Ｎａｔｕｒｅ，ｖｏｌ．４０６，ｐｐ．３７８−３８２，２０００．」）に記載のあるように、ネットワーク障害に対する頑強性が高いことがあげられる。
【００３１】
スケールフリーなトポロジーを持つネットワークでは、全ノードのうちの何パーセントかがダウンしたとしても、代替経路の存在によってノード間の接続を維持でき、系全体の平均経路長（平均最短距離）はほとんど変化しない。
【００３２】
このような基本特性を利用して、本例では、例えばインターネットに接続するいくつかのオーバーレイノードによって構築される論理網であるオーバーレイネットワークにおいて、既に参加しているオーバーレイノードｊはｋｊ個のオーバーレイノードと接続しているとし、オーバーレイネットワークへ参加するノードは次数ｋｊに対して定義する任意の確率分布関数Ｐ（ｋｊ）に応じた確率で接続先のノードを決定する。
【００３３】
上述の参考文献１に記載されているように、新しいノード（２２）を追加するとき、既に存在するノード（２１ａ〜２１ｋ）の次数ｋに比例して、接続させていくと、スケールフリーになることが知られている。
【００３４】
このような特性を利用して本発明に係るオーバーレイネットワークのトポロジー制御を行う第１〜第１０の例を以下に説明する。
【００３５】
第１の例においては、上述の特性を利用して、トポロジーに依存したネットワークの特性を接続時のノード選択アルゴリズムやパラメタによってコントロールする。尚、ここでは新規参加ノードの参加時のみを対象に記載しているが、これを一定周期ごと、あるいはネットワークの状態に応じていくつかの既存ノードに対しても同様の手順により接続先を変更させてもよい。
【００３６】
また、第２の例においては、既に参加している各既存ノード２１ａ〜２１ｋは、一定周期毎に確率ｐで自身を接続候補リストとして立候補し、その旨を該ノードの次数とともに接続候補管理サーバ１に通知し、新規参加ノード２２の参加時には、この新規参加ノード２２が、接続候補管理サーバ１から接続候補リストを入手し、その中から、次数に応じた確率で、接続先ノードをｍ個選択する。
【００３７】
これは、第１の例では、全ノードの次数情報が必要となるが、ネットワーク規模が大きくなるとスケール性に問題が生じるため、全ノードではなく、そのうちの一部のみを候補とすることによりスケール性を担保している。
【００３８】
また、第３の例においては、例えば第２の例のように確率ｐでランダムに立候補する代わりに、既存ノード２１ａ〜２１ｋが、自身の帯域やＣＰＵ使用率といったリソースの状況に応じて、リソースに空きがあれば、接続候補として立候補する。こうすることにより、より安定的なノードヘ接続されやすくしている。
【００３９】
また、第４の例においては、接続候補リストを複数用意しておき、それぞれを複数の接続候補管理サーバ（１）で管理しておき、新規参加ノード２２は、参加時には、いずれかのリストをランダムに選択し、リスト決定後は第２の例と同様の手順に従って接続先ノードを決定する。こうすることにより、接続候補管理サーバ（１）に障害が発生した場合にも、他のサーバから情報を入手できるようにしている。
【００４０】
また、第５の例においては、新規参加ノード２２が、第１〜第４の例のいずれかにより接続先ノードをｍ’個選択し、そのｍ’個の中から、新規参加ノード２２との間の品質メトリック（遅延時間、パケット損失率、スループット）が最も良いものから順にｍ個拍出し、そのｍ個を接続先ノードとして決定する。こうすることにより、次数を考慮してスケールフリーなネットワーク（＝対障害性に優れるネットワーク）にしつつ、品質も考慮可能としている。
【００４１】
また、第６の例においては、第２の例のように接続候補管理サーバ１を集中管理サーバとして設置する代わりに、まずいずれかの既に参加している既存ノード２１ａ〜２１ｋに、次数の問い合わせメッセージを送出し、この問い合わせメッセージを受信した既存ノードは自身の隣接ノードに対して当該問い合わせメッセージを転送し、それを新規参加ノード２２から一定ホップ数以内の範囲で実施する。問い合わせメッセージを受信したノードは自身の次数を問い合わせ元の新規参加ノード２２に対して返信する。それを受け取った新規参加ノード２２は、返信のあったノード群から、次数に応じて接続先を決定する。
【００４２】
この第６の例は、上述の第２の例では、接続候補管理サーバ１が必要であったが、そのようなサーバによる集中管理をしないで、自律分散的に接続候補を探索させて、集中管理によるボトルネック回避やスケール性の限界を打破する。
【００４３】
また、第７の例では、第６の例において、各既存ノードが、次数に関する情報に加えてリソースに関する情報も新規参加ノード２２に伝え、新規参加ノード２２は返信のあったノード群から次数およびリソース状況に応じて接続先ノードをｍ’個選択し、そのｍ’個の中から、該新規参加ノードとの間の品質メトリック（遅延時間、パケット損失率、スループット）が最も良いものから順にｍ個抽出し、そのｍ個を接続先ノードとして決定する。
【００４４】
また、第８の例においては、Ｐ２Ｐに関連する技術として用いられている分散ハッシュテーブルを用いており、既存ノードが、自身の次数およびリソース情報をｉｎｄｅｘとして、分散ハッシュテーブルに登録しておき、新規参加ノード２２は、その分散ハッシュテーブルに対して、ある次数およびリソース情報を持つ既存ノードを検索し、これを複数の次数およびリソース情報に対して実施し、その結果得られたノード群の中から、接続先ノードをｍ’個選択し、そのｍ’個の中から、新規参加ノード２２との間の品質メトリック（遅延時間、パケット損失率、スループット）が最も良いものから順にｍ個抽出し、そのｍ個を接続先ノードとして決定する。
【００４５】
これは、上述の第６の例のように、フラッディングベースで次数情報を引き出す代わりに、分散ハッシュテーブルと呼ばれる技術を用いて効率的に次数情報を分散管理するものである。尚、このような分散ハッシュテーブルを含むＰ２Ｐ技術に関しては、例えば、上述の非特許文献２や、インターネット上で閲覧可能な参考文献２（「藤原洋，インターネット数理科学第１３回  〜Ｐ２Ｐテクノロジと今後の展望〜平成２００７年１月２５日  ，東京大学大学院数理科学研究科  情報理論９０１−３５講義資料  ｈｔｔｐ：／／ｗｗｗ．ｍｓ．ｕ−ｔｏｋｙｏ．ａｃ．ｊｐ／ｌｅｃｔｕｒｅ／２００６／９０１−３５／２００７−０１−２５．ｐｄｆ）や参考文献３（「砂原秀樹，油谷曉  Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ：本格的Ｐ２Ｐアプリケーション時代のための基礎知識とネットワーク運用技術  奈良先端科学技術大学院大学情報科学センタ、ｈｔｔｐ：／／ｗｗｗ．ｊｐｎｉｃ．ｎｅｔ／ｊａ／ｍａｔｅｒｉａｌｓ／ｉｗ／２００６／ｐｒｏｃｅｅｄｉｎｇｓ／Ｔ３−１．ｐｄｆ」等に記載されている。
【００４６】
また、第９の例では、それぞれ複数のスーパーノード（図２における２０ａ〜２０ｈ）と各スーパーノードに接続される複数の一般ノード（図２における２１ａ〜２１ｋ）からなる複数のクラスタで構成されたスーパーオーバーレイネットワークに新たにオーバーレイノードとして新規参加ノードを参加させる場合の接続先を決定するものである。尚、このようなスーパーノードおよびクラスタを含むＰ２Ｐ技術に関しては、上述の参考文献２，３や参考文献４（「Ｅｎｇ  Ｋｅｏｎｇ  Ｌｕａ  “Ｎｅｔｗｏｒｋ−ａｗａｒｅ  ＳｕｐｅｒＰｅｅｒｓ−Ｐｅｅｒｓ  Ｇｅｏｍｅｔｒｉｃ  Ｏｖｅｒｌａｙ  Ｎｅｔｗｏｒｋ，”  Ｐｒｏｃ．  ＩＥＥＥ  ＩＣＣＣＮ  ２００７  Ｐ２Ｐ  ａｎｄ  Ｇｒｉｄ  Ｎｅｔｗｏｒｋｉｎｇ  Ｔｒａｃｋ，Ｈａｗａｉｉ，ＵＳＡ，Ａｕｇｕｓｔ  １３−１６，  ２００７．」）等において記載されている。
【００４７】
すなわち、既存ノードを複数のクラスタに分割し、各クラスタにはいくつかのスーパーノードとそれ以外の多数の一般ノードの２種類が存在し、クラスタ間のスーパーノードはフルメッシュで接続されているとする。スーパーノードは自身の属するクラスタ内の一般ノードの次数およびリソース情報を把握しているとし、新規参加ノードは、いずれかのクラスタに所属させるが、その際に、該クラスタ内の一般ノードの次数およびリソース情報をスーパーノードから入手し、接続先ノードを次数を用いてｍ’個選択し、そのｍ’個の中から、該新規参加ノードとの間の品質メトリック（遅延時間、パケット損失率、スループット）が最も良いものから順にｍ個抽出し、そのｍ個を接続先ノードとして決定する。
【００４８】
また、第１０の例においては、新規参加ノード２２が参加する際に、次数に応じて接続先ノードを選択し、同時に次数に依らずにランダムに接続もさせる。これにより、スケールフリーネットワークにするだけでなく、あえてランダムネットワークにもすることができる。スケールフリーネットワークは、耐障害性に優れるが、ＤＤｏＳ（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄｅｎｉａｌ  ｏｆ  Ｄｒｖｉｃｅｓ  ａｔｔａｃｋ）のような攻撃に弱いことも指摘されている。一方、ランダムネットワークは耐障害性には劣るが攻撃には強いという面を持つ。したがって両者を併用することにより、耐障害性および攻撃にも強いネットワークとすることが可能となる。
【００４９】
以下、図２に示すオーバーレイネットワークにおける各既存ノード２１ａ〜２１ｋが、相互に論理的に接続されている状況で、当該オーバーレイネットワークに、新規参加ノード２２が参加する場合に、新規参加ノード２２が、図１に示す接続候補管理サーバ１に問い合わせて、各参加ノード２１ａ〜２１ｋから接続先ノードを決定する際の動作について説明する。
【００５０】
図１に示すように、接続候補管理サーバ１は、まず、新規参加ノード２２からの問い合わせを接続先決定部１ａで受信する。
【００５１】
この接続先決定部１ａは、次数管理部１ｂで記憶管理されている既存参加ノードｊの次数ｋｊを読み出し、読み出した次数ｋｊに比例した確率でｍ個の接続候補を選定して、接続候補リストを生成し、生成した接続先候補リストを、問い合わせ元の新規参加ノード２２に返信する。
【００５２】
接続先決定部１ａから接続候補リストを受けた新規参加ノード２２は、そのｍ個の接続先ノードヘ接続する。
【００５３】
一方、既存の各既存ノード２１ａ〜２１ｋは、一定周期毎に確率ｐで自身を接続候補リストとして立候補し、その旨を次数と共に、接続候補管理サーバ１内の次数管理部１ｂに通知する。
【００５４】
さらに、既存の各既存ノード２１ａ〜２１ｋは、一定周期毎に確率ｐ’で、接続候補管理サーバ１内の接続先決定部１ａに接続先変更の旨を通知し、それを受けた接続候補管理サーバ１内の接続先決定部１ａは、新規参加ノード時と同様に接続候補リストを返送し、既存ノードは接続先を変更する。
【００５５】
また、接続候補管理サーバ１内に座標保持部１ｃを用意しており、既存の各参加ノード２１ａ〜２１ｋは、一定周期毎に確率ｐで自身を接続候補リストとして立候補し、その先に、次数を次数管理部１ｂに通知すると同時に、白身の座標を座標保持部１ｃに通知する。
【００５６】
ここで座標とは、ノード間の品質に関する距離（ＲＴＴ（Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）やスループット等）を用いて、各ノードを座標空間上にマップさせることにより、ノードが座標位置を持っているとする。尚、このような座標位置の決定には、上述の参考文献４において記載された技術を用いることができる。
【００５７】
この際、接続候補管理サーバ１内の接続先決定部１ａは、次数情報を用いて、先ず、接続先ノードをｍ’個選択し、そのｍ’個の中から、座標位置を用いて当該新規参加ノードとの間の品質メトリック（遅延時間、パケット損失率、スループット）が最も良いものから順にｍ個抽出し、そのｍ個を接続先ノードとして決し、新規参加ノード２２に返送する。
【００５８】
このような手順を含むと共に他の手順による、本発明に係るオーバーレイネットワークのトポロジー制御処理動作を、図３〜図７を用いて説明する。
【００５９】
図３は、本発明に係るオーバーレイネットワークのトポロジー制御方法の手順例を示す第１のフローチャートであり、図４は、本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第２のフローチャート、図５は、本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第３のフローチャート、図６は、本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第４のフローチャート、図７は、本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第５のフローチャートである。
【００６０】
図３に示す例（Ｉ）では、プログラムされたコンピュータの処理実行手順として、予め、オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順（ステップＳ３０１）と、新規参加ノードの接続先となる既存ノードを、記憶装置に記憶したリスト情報を参照して決定する決定処理手順（ステップＳ３０２）とを含み、かつ、ステップ３０２における決定処理手順は、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を含む。
【００６１】
また、図４に示す例（ＩＩ）では、プログラムされたコンピュータ処理手順として、新規参加ノードが、オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードに対して、当該既存ノードの識別情報と当該既存ノードの接続先の数である次数とを問い合わせるメッセージと予め定められたホップ数を送信する送信手順（ステップＳ４０１）と、メッセージとホップ数を受信した既存ノードが、受信したメッセージとホップ数を、隣接する既存ノードに対して転送する転送手順（ステップＳ４０２）と、メッセージを受信した各既存ノードから新規参加ノードに対して、各既存ノードの識別情報と次数を返信する返信手順（ステップＳ４０３）と、この転送手順を、ホップ数以内の範囲の各既存ノードで繰り返す手順（ステップＳ４０４）と、新規参加ノードが、各既存ノードから受信した当該既存ノードの識別情報と次数とを対応付けて記述したリスト情報を生成して記憶装置に記憶する手順（ステップＳ４０５）と、この記憶装置に記憶したリスト情報を参照して、自ノードの接続先となる既存ノードを決定する決定処理手順（ステップＳ４０６）とを含み、かつ、ステップＳ４０６における決定処理手順は、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で新規参加ノードの接続先となる既存ノードを決定する手順を含む。
【００６２】
尚、例（ＩＩＩ）として、図４に示す例（ＩＩ）において、各既存ノードが、新規参加ノードに対して、識別情報と次数と共に、自装置の帯域使用率およびＣＰＵ使用率を含むリソース使用率を返信する手順を実行し、新規参加ノードが、返信のあった既存ノードの内、リソース使用率が予め定められた閾値よりも良いものに対して、決定処理手順による接続先の決定処理を実行することでも良い。
【００６３】
また、例（ＩＶ）として、図４に示す例（ＩＩ）において、既存ノードが、自身の識別情報と次数および帯域使用率とＣＰＵ使用率を含むリソース使用率をｉｎｄｅｘとして分散ハッシュテーブルに登録しておき、新規参加ノードが、分散ハッシュテーブルを検索して予め定められた各々異なる複数の次数とリソース情報を持つ既存ノードを抽出し、抽出した各既存ノードに対して上記決定処理手順を実行して接続先の既存ノードを選択することでも良い。
【００６４】
また、図５に示す例（Ｖ）では、プログラムされたコンピュータ処理手順として、スーパーノード（図２における２０ａ〜２０ｈ）が、自身の属するクラスタ内で一般ノード（図２における２１ａ〜２１ｋ）として存在している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを記憶装置に記憶する手順（ステップＳ５０１）と、新規参加ノードが、自身の属するクラスタ内のスーパーノードから、当該クラスタ内の各既存ノードの識別情報と次数を取得し、取得した次数と識別情報を用いて、自ノードの接続先となる既存ノードを決定する決定処理手順（ステップＳ５０２）とを含み、かつ、ステップＳ５０２における決定処理手順は、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で新規参加ノードの接続先となる既存ノードを決定する手順を含む。
【００６５】
尚、例（ＶＩ）として、図５に示す例（Ｖ）において、各スーパーノード（図２における２０ａ〜２０ｈ）が、自身の属するクラスタ内の各既存ノード（図２における２１ａ〜２１ｋ）の識別情報と数と共に、当該既存ノードの帯域使用率およびＣＰＵ使用率を含むリソース使用率を記憶装置に記憶し、新規参加ノードが、自身の属するクラスタ内のスーパーノードから、当該クラスタ内の各既存ノードの識別情報および次数と共にリソース使用率を取得し、各既存ノードの内、取得したリソース使用率が予め定められた閾値よりも良いものに対して、決定処理手順による接続先の決定処理を実行することでも良い。
【００６６】
また、図６に示す例（ＶＩＩ）では、プログラムされたコンピュータ処理を実行する管理サーバ装置が、予め、オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順（ステップＳ６０１）と、新規参加ノードの接続先となる既存ノードを、記憶装置に記憶したリスト情報を参照して決定し当該新規参加ノードに通知する決定処理手順（ステップＳ６０２）とを実行すると共に、このステップＳ６０２における決定処理手順として、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で新規参加ノードの接続先となる既存ノードを決定する手順を実行する。
【００６７】
また、図７に示す例（ＶＩＩＩ）では、プログラムされたコンピュータ処理により、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定する際、管理サーバ装置が、予め、オーバーレイネットワークに既にオーバーレイノードとして参加している各既存ノードの識別情報と当該既存ノードの接続先の数である次数とを対応付けて記述したリスト情報を記憶装置に記憶する記憶処理手順（ステップＳ７０１）と、新規参加ノードからの要求に応じて、記憶装置に記憶したリスト情報を当該新規参加ノードに送信する送信処理手順（ステップＳ７０２）とを実行し、新規参加ノードが、管理サーバから受信したリスト情報を参照して、当該新規参加ノードの接続先となる既存ノードを決定する決定処理手順（ステップＳ７０３）を実行すると共に、新規参加ノードは、ステップＳ７０３における決定処理手順として、リスト情報に記述された各既存ノードの次数に対して予め定義された確率分布関数に応じた確率で上記新規参加ノードの接続先となる既存ノードを決定する手順を実行する。
【００６８】
尚、例（ＩＸ）として、例（Ｉ）〜（ＶＩＩＩ）のいずれかの決定処理手順において、全ての既存ノード数をｎ、既存ノードｊ（１＜ｊ≦ｎ）の次数をｋｊとし、かつ、次数の大きい順にｋ１＋ｋ２＋，・・・，＋ｋｎとし、この次数ｋｊの既存ノードｊを、確率Ｐ（ｋｊ）＝ｋｊ÷（ｋ１＋ｋ２＋，・・・，＋ｋｎ）で選択することができる。
【００６９】
また、例（Ｘ）として、例（ＩＸ）における決定処理手順において、０から１の間の乱数ｘを生成する手順と、生成した乱数ｘを用いた｛（ｋ１＋ｋ２＋，・・・，＋ｋｊ−１）÷｛ｋ１＋ｋ２＋，・・・，＋ｋｎ）｝＜ｘ≦｛（ｋ１＋ｋ２＋，・・・，＋ｋｊ）÷｛ｋ１＋ｋ２＋，・・・，＋ｋｎ）｝の条件式から既存ノードｊを選択する手順とを含むことでも良い。
【００７０】
例えば、説明のための簡単な例として、既存ノードが３つあり、ノード１が次数５、ノード２が次数３、ノード３が次数２の場合、ノード１に関しては、確率＝５÷１０＝０．５、ノード２に関しては、確率＝（５＋３）÷１０＝０．８、ノード３に関しては、確率＝（５＋３＋２）÷１０＝１．０となり、乱数ｘ（０＜ｘ≦１）が０．５の場合には、上述の条件式から、ノード１のみが選択され、また、乱数ｘ（０＜ｘ≦１）が０．８の場合には、条件式から、ノード２のみが選択され、さらに、乱数ｘ（０＜ｘ≦１）が１．０の場合には、条件式から、ノード３のみが選択される。
【００７１】
また、例（ＸＩ）として、例（Ｘ）における決定処理手順において、予め定められたそれぞれ異なるｍ（１＜ｍ≦ｎ）個の乱数ｘを用いて当該決定処理手順を繰り返し、ｍ個の既存ノードを選択することでも良い。
【００７２】
また、例（ＸＩＩ）として、例（ＶＩＩ）〜（ＸＩ）のいずれかにおいて、各既存ノードが、予め定められた周期Ｔ１毎に予め定められた確率で管理サーバに、自ノードの識別情報と次数を送信する手順を実行し、管理サーバが、予め定められた周期Ｔ１毎に既存ノードから受信した当該既存ノードの識別情報と次数とを用いて記憶装置に記憶したリスト情報を更新する手順を実行することでも良い。
【００７３】
また、例（ＸＩＩＩ）として、例（ＶＩＩ）〜（ＸＩＩ）のいずれかにおいて、各既存ノードが、予め定められた周期Ｔ２毎に、自装置の帯域使用率およびＣＰＵ使用率を含むリソースに空きがあるか否かを判別する手順と、リソースに空きがあれば、管理サーバに、自ノードの識別情報と次数を送信する手順とを実行し、管理サーバが、予め定められた周期Ｔ２毎に既存ノードから受信した当該既存ノードの識別情報と次数とを用いて記憶装置に記憶したリスト情報を更新する手順を実行することでも良い。
【００７４】
また、例（ＸＩＶ）として、例（ＸＩＩ）もしくは例（ＸＩＩＩ）のいずれかにおいて、管理サーバが、リストの更新毎に更新前のリスト情報も記憶装置に記憶しておき、決定処理手順では、記憶装置に記憶した複数のリスト情報からいずれかをランダムに選択し、選択したリスト情報を用いて新規参加ノードの接続先となる既存ノードの決定処理を実行することでも良い。
【００７５】
また、例（ＸＶ）として、例（ＩＩ）〜例（ＸＩＶ）のいずれかにおいて、新規参加ノードが、決定処理手順で決定したｍ’個の既存ノードから、自装置との間の遅延時間とパケット損失率およびスループットを含む品質メトリックが最も良いものから順にｍ個抽出し、抽出したｍ個の既存ノードを接続先として決定する手順を実行することでも良い。
【００７６】
また、例（ＸＶＩ）として、例（ＩＩ）〜例（ＸＩＶ）のいずれかにおいて、新規参加ノードが、決定処理手順で決定したｍ’個の既存ノードからランダムにｍ個抽出し、該ｍ個の既存ノードを接続先として決定する手順を実行することでも良い。
【００７７】
また、例（ＸＶＩＩ）として、例（Ｉ）〜例（ＸＶＩ）のいずれかにおいて、予め定められた周期毎、もしくは、予め定められたネットワークの状態変化を検出する毎に、予め定められた既存ノードに対して決定処理手順を実行し、当該既存ノードの接続先の変更を行う手順を含むこととしても良い。
【００７８】
以上、図１〜図７を用いて説明したように、本例では、オーバーレイネットワークに新たにオーバーレイノードとして参加する新規参加ノードの接続先を決定する際、新規参加ノードが既存ノードに接続する基準を動的に制御することにより、その結果できあがったネットワークトポロジーがスケールフリー性という特性を有するものにすることによって、対障害性の高いネットワークとすることができる。例えば、インターネットに接続するいくつかのオーバーレイノードによって構築される論理網であるオーバーレイネットワークにおいて、既に参加しているオーバーレイノードｊはｋｊ個のオーバーレイノードと接続している（次数ｋｊ）とし、オーバーレイネットワークへ新たに参加するノードは、次数ｋｊに対して定義する任意の確率分布関数Ｐ（ｋｊ）に応じた確率で接続先のノードを決定する。このように、新しいノードを追加するとき、既に存在するノードの次数ｋに比例して、接続させていくと、スケールフリーになることが知られている。本発明ではこの特性を利用しており、トポロジーに依存したネットワークの特性を接続時のノード選択アルゴリズムやパラメタによってコントロールする。
【００７９】
このことにより、スケーラブルに高品質・高信頼なオーバーレイネットワークを構成でき、エンド・ツー・エンドの通信品質と信頼性を効率的に向上させることができる。
【００８０】
尚、本発明は、図１〜図７を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、図２に示すように、スーパーノード２０ａ〜２０ｈと既存ノード２１ａ〜２１ｋからなるスーパーオーバーレイネットワークを例として説明しているが、一般のオーバーレイネットワークにおいても適用することができる。
【００８１】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【００８２】
【図１】本発明に係るオーバーレイネットワークのトポロジー制御に用いる接続候補管理サーバの構成例を示すブロック図である。
【図２】本発明に係るトポロジー制御を行うオーバーレイネットワークの構成例を示す説明図である。
【図３】本発明に係るオーバーレイネットワークのトポロジー制御方法の手順例を示す第１のフローチャートである。
【図４】本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第２のフローチャートである。
【図５】本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第３のフローチャートである。
【図６】本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第４のフローチャートである。
【図７】本発明に係るオーバーレイネットワークのトポロジー制御方法の他の手順例を示す第５のフローチャートである。
【図８】従来のオーバーレイネットワークによるＱｏＳ管理の基本的な概念を示す説明図である。
【符号の説明】
【００８３】
１：接続候補管理サーバ、１ａ：接続先決定部、１ｂ：次数管理部、１ｃ：座標保持部、２０ａ〜２０ｈ：スーパーノード、２１ａ〜２１ｋ：既存ノード（一般ノード）、２２：新規参加ノード、８１ａ〜８１ｃ：スーパーノード、８２ａ〜８２ｅ：ＩＰルータ、８３：オーバーレイネットワーク、８４：ＩＰネットワーク。
【図１】
2009260872.tif 000003
【図２】
2009260872.tif 000004
【図３】
2009260872.tif 000005
【図４】
2009260872.tif 000006
【図５】
2009260872.tif 000007
【図６】
2009260872.tif 000008
【図７】
2009260872.tif 000009
【図８】
2009260872.tif 000010