通信径路決定システムと方法およびプログラム
【課題】オーバーレイネットワークにおける測定コストを削減しつつ、通信品質の改善を図る。
【解決手段】オーバーレイネットワークを構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【解決手段】オーバーレイネットワークを構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等のＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）ネットワークにおけるエンド・ツー・エンドの通信品質を向上させる技術に係り、特にＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させるのに好適な技術に関するものである。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Ｖｏｉｃｅ ｏｖｅｒ ＩＰ）やストリーミングに代表されるＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）に敏感な実時間アプリケーション等の収容も急速に発展している。
【０００３】
これに伴い・エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００４】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００５】
（２）インターネットは管理主体の異なる複数のＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００６】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えば非特許文献１に記載の、オーバーレイネットワークによるＱｏＳ管理技術が注目されている。
【０００７】
オーバーレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００８】
このような、オーバーレイネットワークによるＱｏＳ管理の基本的な概念を図１に例示する。図１において、１ａ〜１ｃはオーバーレイネットワーク１を構成するノード（オーバーレイノード）であり、２ａ〜２ｅはＩＰネットワーク２を構成するＩＰルータであり、ｘからｙに向けて、破線矢印で表わされる経路にトラヒックが流れているとする。また、この経路上には輻輳しているＩＰルータが存在しており、その結果として、ｘ，ｙ間のＱｏＳが低下しているとする。
【０００９】
このとき、オーバーレイノード１ａ，１ｂ，１ｃで形成されるオーバーレイネットワーク１を用いて、実線矢印で表される経路（ｘ→オーバーレイノード１ａ→オーバーレイノード１ｂ→オーバーレイノード１ｃ→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【００１０】
実際、非特許文献３，４，５では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。しかし、非特許文献３と非特許文献５の結果は、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
【００１１】
すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間の品質測定情報を用いて通信経路の計算を行うことは現実的には不可能であるという問題がある。
【００１２】
このような問題を回避するため、非特許文献４では、迂回経路を提供する中継ノード候補数を制限した場合を評価している。しかし、中継ノード候補は単にランダムに選択しているにすぎず、中継ノード候補の選択方法までは検討していなかった。
【００１３】
一方、特許文献１において、本発明者らは、中継ノード候補を計測データに基づいて一定数以下に適切に制限することにより、全ノードを中継候補として経路探索を行った最適な場合とほぼ同等のＱｏＳ向上を図れることを示している。
【００１４】
しかしながら、この技術では、全てのノードペアに対する経路について、全ノードペアの直通の品質を用いて、直通路と迂回路の通信品質を比較することにより適切な経路を決定していた。
【００１５】
つまり、中継路探索においては全経路探索は行っていない（中継ノード候補を一定数に制限している）ものの、各ノードペアでの通信品質は依然として測定する必要があり、測定負荷自体は低減できていないという問題があった。
【００１６】
【特許文献１】特開２００８−０５３７９４号公報
【非特許文献１】Ｌ．Ｚｈｉ ａｎｄ Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ ｒｏｕｔｉｎｇ ｉｎ ｏｖｅｒｌａｙ ｎｅｔ−ｗｏｒｋｓ，” ＩＥＥＥ Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ Ｃｏｍｍｕｎ．ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ ２００４．
【非特許文献２】ＷＩＤＥ プロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジヱクト研究報告書，第１７部，２００２．
【非特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献４】Ｓ．Ｒｅｗａｓｋａｒ ａｎｄ Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ ｔｈｅ Ｓｃａｌａｂｉｌｉｔｙ ｏｆ Ｏｖｅｒｌａｙ Ｒｏｕｔｉｎｇ Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，” Ｐｒｏｃ．；ＰＡＭ２００４，Ａｐｒｉｌ ２００４．
【非特許文献５】Ｓ．Ｂａｎｅｒｊｅｅ， Ｔ．Ｇ．Ｇｒｉｆｉｎ ａｎｄ Ｍ．Ｐｉａｓ，“Ｔｈｅ Ｉｎｔｅｒｄｏｍａｉｎ Ｃｏｎｎｅｃｔｉｖｉｔｙ ｏｆ ＰｌａｎｅｔＬａｂ Ｎｏｄｅｓ，” Ｐｒｏｃ．ＰＡＭ ２００４，Ａｐｒｉｌ ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１７】
解決しようとする問題点は、従来の技術では、全てのノードペアに対する経路について、全ノードペアの直通の品質を測定する必要がある点である。
【００１８】
本発明の目的は、これら従来技術の課題を解決し、各ノードペアでの通信品質の測定に係る負荷を低減することで、オーバーレイネットワークにおけるエンド・ツー・エンドの通信品質を効率的に向上させることである。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、本発明では、オーバーレイネットワークを構成するノード（オーバーレイノード）を、ごく一部の少数の上位ノードと、それ以外の大多数の一般ノードの２階層に分け、少数の上位ノード間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。（１）具体的には、まず、オーバーレイネットワークを構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、Ｍ個のノードを上位ノードとして選択し、残りのＮ−Ｍ個を一般ノードとする。次に、各上位ノード間ではフルメッシュで通信品質（例えば、遅延時間や帯域あるいはパケット損失率など）を測定して最適な経路を決定し、一般ノードと当該一般ノードが接続された各上位ノード間では、各接続毎の通信品質を測定して最適な経路を決定することで、それぞれの経路選択においても、直通の経路を含めて最適な経路を決定する。そして、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。このように、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質コスト削減を可能としている。
【発明の効果】
【００２０】
本発明によれば、オーバーレイノードをさらに上位ノードと一般ノードに分け、一般ノードと一般ノード間はオーバーレイネットワークにおいて論理的に接続されていないとすることで、一般ノード間の品質測定結果を不要とすることができ、大多数の一般ノード間の品質コスト削減が可能となり、オーバーレイネットワークにおける測定コストを削減しつつ、通信品質の改善を図ることが可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図２は、本発明に係る通信経路選択システムを具備したオーバーレイネットワークの構成例を示すブロック図であり、図３は、図２におけるオーバーレイノードの本発明に係る構成例を示すブロック、図４は、図２における管理サーバ２０の本発明に係る構成例を示すブロック図である。
【００２２】
図２におけるオーバーレイネットワークでは、オーバーレイノードを、Ｍ個の上位ノード２１〜２５（ここではＭ＝５個）とそれ以外の一般ノード２６ａ〜２６ｄに分け、上位ノード２１〜２５間ではフルメッシュで論理的に接続し、一般ノード２６ａ〜２６ｄは各上位ノード２１〜２５と論理的に接続しているとする。
【００２３】
尚、ここで、論理的に接続されているとは、その接続先ノードのＩＰアドレスを知っており、通信可能な状態にある。
【００２４】
上位ノード２１〜２５と一般ノード２６ａ〜２６ｄおよび管理サーバ２０のそれぞれは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置を含むコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００２５】
すなわち、上位ノード２１〜２５と一般ノード２６ａ〜２６ｄを含むオーバーレイノードは、図３のオーバーレイノード３１として示すように、プログラムされたコンピュータ処理を実行する機能として、通信品質測定部３１ａと通信品質取得部３１ｂ、中継ノード決定部３１ｃ、中継候補選択部３１ｄ、上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈを具備し、管理サーバ２０は、図４に示すように、プログラムされたコンピュータ処理を実行する機能として、中継ノード状態管理部２０ａと中継ノード候補決定部２０ｂ、上位ノード決定部２０ｃ、上位ノード管理部２０ｄを具備している。
【００２６】
このような構成において、本例では、図１で示したオーバーレイネットワーク１を構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、図２に示すように、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【００２７】
以下、本発明に係る第１〜第７の技術について説明する。
【００２８】
まず、第１の技術について説明する。例えば、オーバーレイネットワーク１を構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、Ｍ個のノードを上位ノードとして選択し、残りのＮ−Ｍ個を一般ノードとする。図２の例では、５個の上位ノード２１〜２５と多数の一般ノード２６ａ〜２６ｄに分けられている。
【００２９】
各上位ノード間ではフルメッシュで通信品質を測定して最適な経路を決定し、また、一般ノードと当該一般ノードが接続された各上位ノード間では、各接続毎の通信品質を測定して最適な経路を決定することで、それぞれの経路選択においても、直通の経路を含めて最適な経路を決定する。
【００３０】
そして、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。
【００３１】
より詳細には、オーバーレイネットワーク１を構成する各ノード（オーバーレイノード２１〜２５，２６ａ〜２６ｄ）間の通信経路を、プログラムされたコンピュータ処理により決定するために、プログラムされたコンピュータ処理を実行する手段として、上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈを設けており、まず、上位ノード間通信品質取得部３１ｅにより、オーバーレイネットワーク１を構成する全てのＮ個のノード２１〜２５，２６ａ〜２６ｄから予め選択されたＭ個の上位ノード２１〜２５間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して図示していない記憶装置に記憶する。
【００３２】
次に、上位ノード間最適経路算出部３１ｆにより、上位ノード間最適経路算出部３１ｆが測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する。
【００３３】
さらに、一般・上位ノード間通信品質取得部３１ｇにより、上位ノード２１〜２５以外の残りのＮ−Ｍ個の一般ノード２６ａ〜２６ｄのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する。
【００３４】
そして、一般ノード間最適経路算出部３１ｈにより、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報および一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する。
【００３５】
このように、本例では、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質測定に要するコストを削減することが可能となる。
【００３６】
次に、第２，第３の技術について説明する。この第２，第３の技術は、通信品質に関するものであり、第２の技術においては、通信品質としてノード間の遅延時間を用い、ノード間のメトリックを遅延時間とし、上位ノード２１〜２５間はフルメッシュで接続されているとして、例えば上位ノード２１から上位ノード２４への経路は、上位ノード間最適経路算出部３１ｆにおいて、遅延をメトリックとして、ダイクストラ法で最短経路を探索しておきそれを最適な経路として決定する。
【００３７】
また、例えば一般ノード２６ａから上位ノード２４への最適経路は、一般ノード２６ａと全ての上位ノード２１〜２５が接続されているとし、また上位ノード２１〜２５間はフルメッシュで接続されているとし、一般ノード間最適経路算出部３１ｈにおいて、そのトポロジ上でダイクストラ法により最短経路を探索しておき、それを最適経路とする。
【００３８】
そして、例えば一般ノード２６ａから他の一般ノード２６ｄへの最適経路は、一般ノード２６ａと全ての上位ノード２１〜２５および全ての上位ノード２１〜２５と一般ノード２６ｄが接続されているとしたトポロジ上で最短経路を探索し、それを最適経路とする。
【００３９】
また、第３の技術では、上述の第２の技術のように遅延を品質とする代わりに、ノード間の利用可能帯域を品質として用い、品質の逆数をノード間のメトリックとして、あるいは、ノード間のパケット損失率またはパケット損失数を通信品質メトリックとしてダイクストラ法により最短経路を探索して最適経路とすることで、様々な品質メトリックに対応可能とする。
【００４０】
次に、第４の技術について説明する。この第４の技術では、上述の第１〜第３の技術のように、一般ノードから全ての上位ノードとの間を接続する代わりに、一般ノードから最も近い上位ノードのみ接続するものである。
【００４１】
すなわち、一般ノード間最適経路算出部３１ｈは、一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、各一般ノード毎に当該一般ノードに最適な通信品質で接続された上位ノードを１つ特定して記憶装置に記憶し、特定して記憶装置に記憶した特定情報を用いて、発信元の一般ノードに最適な通信品質で接続された発信側上位ノードと着信先の一般ノードに最適な通信品質で接続された着信側上位ノードを特定し、特定した発信側上位ノードと着信側上位ノード間の最適な通信品質の経路を、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報を用いて特定する。
【００４２】
次に、第５〜第７の技術について説明する。この第５〜第７の技術は、Ｍ個の上位ノードを選択する技術に関するものである。
【００４３】
第５の技術では、まず、オーバーレイネットワークによる経路制御開始から予め定めた時間までの間、一定周期毎に各オーバーレイノード（２１〜２５，２６ａ〜２６ｄ）間でフルメッシュで通信品質を測定し、Ｍ個のノードをランダムに中継ノード候補として選択する。
【００４４】
次に、ノードｉからノードｊへの経路を決定する際、ノードｉから中継ノード候補群に属するノードｋまでの通信品質をｄ（ｉ，ｋ）、ノードｋからノードｊまでの通信品質をｄ（ｋ，ｊ）とし、トータルな通信品質「ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を最小にする中継候補としてのノードｋ＊を探索し、ノードｉからノードｊの直通の通信品質ｄ（ｉ，ｊ）とトータルな通信品質「ｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）」を比較し、後者（トータルな通信品質）が小さければ、当該ノードｋ＊を中継ノードとして迂回経路を構築する。
【００４５】
このような処理を、各ノードペアについて実行し、ノードｋが中継ノードとして選択された回数をカウントし、次周期の中継ノード候補をＭ個選択する際には、過去に中継ノードとして選択された回数に応じた確率で選択する。
【００４６】
そして、このような処理を予め定めた時間までの間、繰り返し実行し、予め定めた時間経週後は、それまでに中継ノードとして選択された回数の多いもの上位Ｍ個を上位ノードとして選択する。
【００４７】
尚、このような上位ノードの選択技術には、上述の特許文献１に記載の技術を部分的に用いている。つまり、最初のうちは、全ノードペアの品質測定を実施し、特許文献１に記載の技術を用いて、良い中継路を提供できるＭ個のノードを推定する処理を、予め定めた時間まで実施し、その結果、中継ノードとして貢献した回数の多いものを上位ノードとして用いる。
【００４８】
第６の技術では、上述の第５の技術のように各ノード間においてフルメッシュで品質測定する代わりに、まずＮ個のノードからランダムにＭ個を選択し、それらを上位ノードとし、それら以外を一般ノードとして、上述の第１の技術のように、上位ノード間フルメッシュで品質測定し、また一般ノードと上位ノード間も品質測定をする。
【００４９】
そして、また、Ｎ個のノードの中からＭ’個（Ｍ’＞Ｍ）を中継ノード候補として選択する。ここで、上位ノードｉから上位ノードｊ、あるいは一般ノードｉから上位ノードｊ、あるいは上位ノードｉから一般ノードｊへの直通の通信品質をｄ（ｉ，ｊ）とし、Ｍ’個の中継ノード候補ｋを中継としたときの通信品質（ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ））を最小にするノードｋ＊を中継ノード候補とし、通信品質ｄ（ｉ，ｊ）と通信品質ｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）を比較して後者の通信品質の方がよければ、ノードｋ＊の得点をカウントアップし、この処理を直通の品質が測定されている全ノードペアに対して実行し、次周期には、その得点（カウントアップ結果）に応じてＭ’個の中継ノード候補を選択すると共に、Ｍ’個の中継ノード候補の特に上位Ｍ個を上位ノードとして選択し、これを繰り返すことにより現時点での上位ノードＭ個を決定する。あるいは、第１，第２の技術を用いて、ダイクストラ法により各ノードペアの最短経路を決定し、その結果ノードｋ＊が中継ノードとして選択された回数をカウントアップし、次周期には、当該回数に応じてＭ個の上位ノードを選択しても良い。
【００５０】
上述の第５の技術では、最初のうちはフルメッシュ測定を許容していたのに対し、本第６の技術では、最初からフルメッシュ測定は実施しないで、直通の品質が測定できている上位ノードと上位ノード間、および一般ノードと上位ノード間、上位ノードと一般ノード間のみを用いて、これらペアの直通路の品質と、Ｍ個の上位ノード群の中から最も品質の良い迂回路を提供する中継ノードを探索して、それを用いたときの迂回路の品質を比較し、後者の方が良い品質を提供できる場合には、そのときの中継ノードに得点を与え、これを繰り返し実施して、次周期にＭ個の上位ノードを選択する際には、過去の得点の高いものを高い確率で選択するようにする。
【００５１】
得点としては、時点ｎにおいてノードｋが中継ノードとして選択された回数をＣ’（ｎ，ｋ）として、時点ｎ＋１での得点Ｃ（ｎ＋１，ｋ）を「Ｃ（ｎ＋１，ｋ）＝（１−α）Ｃ（ｎ，ｋ）＋αＣ’（ｎ，ｋ）」により更新する。ここで、αは予め定める平滑化パラメータで、初期値Ｃ（０，ｋ）＝０とする。
【００５２】
この得点Ｃ（ｎ，ｋ）を用いて、時点ｎにおいてノードｋを上位ノードとして確率ｐ（ｎ，ｋ）で選択する。ここで「ｐ（ｎ，ｋ）＝Ｃ（ｎ，ｋ）／ΣＣ（ｎ，ｊ）」、あるいは、「ｐ（ｎ，ｋ）＝ｅｘｐ｛Ｃ（ｎ，ｋ）−１｝／Σｅｘｐ｛Ｃ（ｎ，ｊ）−１｝」、などが確率ｐ（ｎ，ｋ）の候補となる。
【００５３】
第７の技術では、ある時点においては各ノード間の通信品質をフルメッシュで測定し、ノードｉとノードｊ以外の各ノードを中継候補に用いてノードｉからノードｊへの最適な通信経路を探索し、これを全てのノードペアについて実施し、その結果、最適な中継ノードとして選択された回数が多い順にＭ個を、それ以降の上位ノードとして決定する。
【００５４】
以下、＜第１の実施例＞として、上述の第６の技術により上位ノードを選択し、上述の第２の技術によりノード間の経路を決定する場合について、図２〜図４を用いて説明する。尚、一定周期毎に以下の動作を実施するとし、ｎ番目の周期を時点ｎと呼ぶ。
【００５５】
図３における通信品質測定部３１ａは、測定周期τ毎に自身（仮にオーバーレイノードｉとする）と他の上位ノードｊとの間の遅延時間ｄ（ｉ，ｊ）を測定し、図示していない記憶装置に記憶する。このように遅延時間測定を実施したら、その旨を中継候補選択部３１ｄに通知する。
【００５６】
中継候補選択部３１ｄは、図４における管理サーバ２０の中継ノード候補決定部２０ｂから、時点ｎでのＭ’個の中継ノード候補を読み出す。同時に、中継候補選択部３１ｄは、通信品質取得部３１ｂに対して、各中継ノード候補ｋ（ｋ＝１〜Ｍ’）から当該中継ノード候補ｋと上述の上位ノードｊ間の遅延時間測定結果「ｄ（ｋ，ｊ）」を取得するように指示する。
【００５７】
通信品質取得部３１ｂは、中継候補選択部３１ｄからの指示に応じて、各中継ノード候補ｋから、当該中継ノード候補ｋと上位ノードｊ間の遅延時間測定結果「ｄ（ｋ，ｊ）」を取得し、中継ノード決定部３１ｃにそれを通知する。
【００５８】
以上の手順を、Ｍ’個の全ての中継ノード候補に対して実施する。
【００５９】
中継ノード決定部３１ｃは、自ノードｉから中継ノード候補ｋまでの遅延時間ｄ（ｉ，ｋ）を通信品質測定部３１ａから取得し、取得した遅延時間ｄ（ｉ，ｋ）と、通信品質取得部３１ｂから通知された中継ノード候補ｋと着信先の上位ノードｊの間の遅延時間ｄ（ｋ，ｊ）とを用いて、「ｄ（ｉ，ｊ）＞ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を満たす中継ノード候補ｋがＭ’個の候補の中に存在するか否かを調べる。
【００６０】
存在しない場合は、自ノードｉから着信先の上位ノードｊの直通路を、最適な通信経路として決定し、存在する場合は、右辺（「ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」）を最小にする中継ノード候補のノードｋ＊を特定し、このノードｋ＊を中継ノードとして選択し、その旨を管理サーバ２０内の中継ノード状態管理部２０ａへ通知する。
【００６１】
以上の手順を全ての上位ノードｊに対して実施する。
【００６２】
管理サーバ２０内の中継ノード状態管理部２０ａは、中継ノード決定部３１ｃからノードｋ＊が中継ノードとして選択された旨の通知を受けると、当該ノードｋ＊が中継ノードとなった回数Ｃ’（ｎ，ｋ＊）を、「Ｃ’（ｎ，ｋ＊）←Ｃ’（ｎ，ｋ＊）＋１」としてカウントアップする。
【００６３】
以上を、ｎ番目の周期が終わるまで繰り返して、各ノードの中継ノードとなった回数を計数する。そして、ｎ＋１番目の測定周期になれば、全てのノードの得点Ｃ（ｎ＋１，ｋ）を「Ｃ（ｎ＋１，ｋ）＝（１−α）Ｃ（ｎ，ｋ）＋αＣ’（ｎ，ｋ）」により更新する。尚、ここで、αは予め定める平滑化パラメータで「０＜α＜１」であり、Ｃ（ｎ，ｋ）の初期値は「Ｃ（０，ｋ）＝１（全てのｋ）」とする。
【００６４】
管理サーバ２０内の中継ノード候補決定部２０ｂでは、時点ｎのノードｋの得点Ｃ（ｎ，ｋ）を用いて、時点ｎにおけるＭ’個の中継ノード候補を確率ｐ（ｎ，ｋ）で選択する。ここで、「ｐ（ｎ，ｋ）＝Ｃ（ｎ，ｋ）／ΣＣ（ｎ，ｊ）」、あるいは、「ｐ（ｎ，ｋ）＝ｅｘｐ｛Ｃ（ｎ，ｋ）−１｝／Σｅｘｐ｛Ｃ（ｎ，ｊ）−１｝」、などがｐ（ｎ，ｋ）の候補となる。
【００６５】
一方、管理サーバ２０内の上位ノード決定部２０ｃでは、確率ｐ（ｎ，ｋ）あるいは得点Ｃ（ｎ，ｋ）を用いて、Ｍ個の上位ノードを決定する。
【００６６】
例えば、確率ｐ（ｎ，ｋ）を用いる場合には、中継ノード候補を選択した場合と同様に、確率ｐ（ｎ，ｋ）でノードｋを上位ノードとして選択する。
【００６７】
また、得点Ｃ（ｎ，ｋ）を用いる場合には、得点の高い上位Ｍ個を上位ノードとして選択する。
【００６８】
尚、以上の上位ノードの選択技術については、中継候補の更新処理の周期よりも長い周期で実施しても良いし、ネットワークの状態に変化が検知されたときのみ、上述の手順で上位ノードを再決定しても良い。
【００６９】
上位ノード決定部２０ｃは、上位ノードとして決定したノードに対して、上位ノードとして決定した旨と、他のどのノードが上位ノードであるかを通知する。
【００７０】
上位ノードとして決定を受けた場合、当該上位ノードは、上位ノード間通信品質取得部３１ｅにより、他の上位ノードとの間の遅延時間を測定しておき、その結果を他の上位ノードと共有する。また、その結果を管理サーバ２０に通知する。この際、上位としての各ノードは、上位ノード間最適経路算出部３１ｆにより他の上位ノードヘの最短経路をダイクストラ法で計算しておき、それを他ノードヘのオーバレイ経路とする。
【００７１】
一方、一般ノードとしてのノードｘは、一般・上位ノード間通信品質取得部３１ｇにより、管理サーバ２０内の上位ノード管理部２０ｄから、どのノードが上位ノードであるかの情報と、上位ノード間の遅延時間情報を入手し、さらに、通信したい着信先ノードｙから、当該着信先ノードｙと上位ノード間の遅延時間を測定した結果を入手する。
【００７２】
そして、一般ノードｘは、これらの入手した情報を用いて、一般ノード間最適経路算出部３１ｈにより、上位ノードを用いた場合の自ノードｘから着信先ノードｙへの最短経路をダイクストラ法で計算し、それをオーバレイ経路とする。
【００７３】
次に、＜第２の実施例＞として上述の第５の技術に関して説明する。上述の＜第１の実施例＞のように、上位ノード間、上位ノードと一般ノード間のみで中継ノードの得点をカウントする代わりに、Ｍ個の上位ノードを決定する際に、オーバーレイネットワークによる経路制御開始から予め定めた時間までの間は、一定周期毎に各オーバーレイノード間でフルメッシュで通信品質を測定し、Ｍ個のノードをランダムに中継ノード候補として選択する。
【００７４】
ノードｉからノードｊへの経路を決定する際、ノードｉから該中継ノード候補群に属するノードｋまでの通信品質をｄ（ｉ，ｋ）、ノードｋからノードｊまでの品質をｄ（ｋ，ｊ）とし、ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）を最小にするノードｋ＊を探索し、ノードｉからノードｊの直通の品質ｄ（ｉ，ｊ）とｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）を比較し、後者が小さければ、ノードｋ＊を中継ノードとして迂回経路を構築し、これを各ノードペアについて実施し、ノードｋが中継ノードとして選択された回数をカウントし、次周期の中継ノード候補をＭ個選択する際には、過去に中継ノードとして選択された回数に応じた確率で選択する。
【００７５】
これを予め定めた時間までの間、実施する。予め定めた時間経過後は、それまでに中継ノードとして選択された回数の多いもの上位Ｍ個を上位ノードとして選択する。
【００７６】
次に、＜第３の実施例＞として上述の第７の技術について説明する。上述の＜第１の実施例＞および＜第２の実施例＞では、上位ノードを決定するために、中継ノード候補の選択を実施していたが、そうする代わりに、ここでは、ある時点においては各ノード間の通信品質をフルメッシュで測定し、ノードｉ，ｊ以外のノードを中継候補に用いてノードｉからノードｊへの最適な通信経路を探索し、これを全てのノードペアについて実施し、その結果、最適な中継ノードとして選択された回数に関する上位Ｍ個を、それ以降の上位ノードとして決定する。
【００７７】
次に、図５〜図８を用いて、本発明に係る通信経路決定方法について説明する。図５は、本発明に係る通信経路決定システムによる通信経路決定方法の第１の処理手順例を示すフローチャートであり、図６は、本発明に係る通信経路決定システムによる通信経路決定方法の第２の処理手順例を示すフローチャート、図７は、本発明に係る通信経路決定システムによる通信経路決定方法の第３の処理手順例を示すフローチャート、図８は、本発明に係る通信経路決定システムによる通信経路決定方法の第４の処理手順例を示すフローチャートである。
【００７８】
図５は、本例に係る一般ノード間の最適な通信経路を決定する際の処理手順例を示し、図６〜図８はＭ個の上位ノードを選択する際の処理手順例を示している。
【００７９】
図５に示すように、本例の通信経路決定システムにおいては、まず、図３の上位ノード間通信品質取得部３１ｅにより、オーバーレイネットワークを構成する全てのＮ個のノードから予め選択されたＭ個の上位間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する（ステップＳ５０１）。
【００８０】
次に、上位ノード間最適経路算出部３１ｆにより、上位ノード間最適経路算出部３１ｆが測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する（ステップＳ５０２）。
【００８１】
さらに、一般・上位ノード間通信品質取得部３１ｇにより、上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する（ステップＳ５０３）。
【００８２】
そして、一般ノード間最適経路算出部３１ｈにより、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報および一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する（ステップＳ５０４）。
【００８３】
また、図６に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、Ｎ個の各ノードからランダムにＭ個のノードを中継ノード候補として選択する（ステップＳ６０１）。
【００８４】
次に、起動から予め定められた時間Ｔが経過するまで（ステップＳ６０２）、一定周期毎に、下記のステップＳ６０３〜Ｓ６０８の処理を実行する。
【００８５】
ステップＳ６０３においては、Ｎ個の各ノード間のそれぞれの通信品質を、各ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶し、ステップＳ６０４においては、記憶装置に記憶したＮ個の各ノード間のそれぞれの通信品質を用いて、Ｍ個の中継ノード候補を中継した、中継ノード候補以外のＮ−Ｍ個の各ノードのペア間の通信品質を算出する。
【００８６】
ステップＳ６０５においては、ステップＳ６０４の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択し、ステップＳ６０６においては、ステップＳ６０５の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する。
【００８７】
さらに、次周期の中継ノード候補選択時に（ステップＳ６０７）、ステップＳ６０６の手順で記憶装置に記憶した回数に応じた確率でＭ個の中継ノード候補を選択する（ステップＳ６０８）。
【００８８】
そして、時間Ｔの経過後（ステップＳ６０２）、ステップＳ６０６の手順により記憶装置に記憶した選択回数が多い上位Ｍ個の中継ノードを上位ノードとして選択する（ステップＳ６０９）。
【００８９】
また、図７に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、Ｎ個の各ノードからランダムにＭ”個のノードを中継ノード候補として選択する（ステップＳ７０１）。
【００９０】
次に、選択したＭ”個の中継ノード候補からＭ個の上位ノードを選択し（ステップＳ７０２）、以下、予め定められた周期（時間ｔ間隔）で（ステップＳ７０３）、ステップＳ７０４〜Ｓ７１０の処理を実行する。
【００９１】
ステップＳ７０４においては、Ｍ個の各上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶し、ステップＳ７０５において、上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する。
【００９２】
ステップＳ７０６においては、記憶装置に記憶したＭ個の各上位ノード間のそれぞれの通信品質およびＮ−Ｍ個の一般ノードと上位ノード間の通信品質を用いて、Ｍ”個の各中継ノード候補を中継した、上位ノード同士からなる各ノードペア間の通信品質および上位ノードと一般ノードからなる各ノードペア間の通信品質を算出する。
【００９３】
ステップＳ７０７においては、ステップＳ７０６の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択し、ステップＳ７０８においては、ステップＳ７０７の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する。
【００９４】
さらに、次周期の上位ノードおよび中継ノード候補の選択時に（ステップＳ７０９）、ステップＳ７０８の手順で記憶装置に記憶した回数に応じた確率でＭ個の上位ノードと中継ノード候補およびＭ”−Ｍ個の中継ノード候補を選択する（ステップＳ７１０）。
【００９５】
そして、各ノードからの要求があれば（ステップＳ７０３）、当該時刻における、ステップＳ７１０の手順で選択したＭ個の上位ノードを、図５に示す各手順による通信経路決定手順用に出力する（ステップＳ７１１）。
【００９６】
また、図８に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、任意の時点での各ノード間の通信品質をフルメッシュで測定して記憶装置に記憶する（ステップＳ８０１）。
【００９７】
次に、記憶装置に記憶した各ノードそれぞれの通信品質を用いて、各ノードペア間の最適な通信経路を選択し（ステップＳ８０２）、最適な通信経路を構成する中継ノードとして選択された回数を各ノード毎に計数して記憶装置に記憶し（ステップＳ８０３）、そして、記憶装置に記憶した選択回数が多い上位Ｍ個のノードを上位ノードとして選択する（ステップＳ８０４）。
【００９８】
このようにしてＭ個の上位ノードを選択して実際の通信経路決定を行った際の、評価結果を、図９，１０に示す。図９は、本発明に係る通信経路決定システムの第１の実行結果例を示す説明図である。
【００９９】
尚、図９の例では、インターネット上での約２００台のオーバーレイノードのノード間で、測定されたノード間の遅延時間を用いた。
【０１００】
ある時点において、各ノードペアに対して、全経路探索を実施し、その結果最適な経路を特定し、それを全ノードペアについて実施した。その結果、最適な中継路を提供した上位２０個を上位ノードとして決定した。
【０１０１】
そして、その２０個の上位ノードのみを用いて、オーバレイの経路を決定した際の、各ノードペアの遅延時間の累積分布を図９に示す。
【０１０２】
図９において、凡例（ＴｙｐｅＡ）がそのときの結果である。比較として、ｏｐｔｉｍａｌとは、全経路探索をしたときの最適路であり、ｄｉｒｅｃｔとは迂回制御をしない直通路の遅延時間結果である。
【０１０３】
また、比較として、上位Ｍノードの選び方として、ＴｙｐｅＡと同様に全経路探索を行った後、経路として選ばれなかったノード間リンクは削除し、その結果残ったトポロジにおいて、次数（ノードの接続リンク数）の高いもの上位２０個を選んだ結果をＴｙｐｅＢとして表示している。
【０１０４】
また、図９におけるＴｙｐｅＣは、ノードのほかのノードヘの遅延時間の平均を計算して、その平均遅延時間が小さいものから２０個選択した際の結果である。
【０１０５】
図５に示す結果により、本例におけるＴｙｐｅＡでは、ｏｐｔｉｍａｌとほぼ同等の遅延の改善がみられることが確認できる。
【０１０６】
以上、図１〜図９を用いて説明したように、本例の通信経路決定システム・方法では、図１で示したオーバーレイネットワーク１を構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、図２に示すように、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【０１０７】
すなわち、オーバーレイネットワーク１を構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、ごく少数のＭ個のノードを上位ノードとして選択し、残りの大多数のＮ−Ｍ個を一般ノードとする。
【０１０８】
そして、ごく少数である各上位ノード間ではフルメッシュで通信品質を測定して最適な経路を決定するが、大多数の一般ノードは、自一般ノードが接続された各上位ノード間において、各接続毎の通信品質を測定して最適な経路を決定し、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。
【０１０９】
このように、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質測定に要するコストを削減することが可能となる。
【０１１０】
このことにより、オーバーレイネットワークにおける測定コストを削減しつつ、通信品質の改善を図ることが可能となる。
【０１１１】
尚、本発明は、図１〜図９を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、各ノードに、本発明に係る通信経路決定を行う機能（上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈ）を設けた構成として説明しているが、これらの各機能を管理サーバ２０側に設け、各一般ノードからの要求に応じて管理サーバ２０で通信経路を決定し、決定した結果を要求元の一般ノードに通知する構成とすることでも良い。
【０１１２】
また、図２に示した上位ノードを５個として例を示しているが、図９において説明したように、２０個とすることでも、また、その他の個数とすることでも良い。
【０１１３】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１１４】
【図１】オーバーレイネットワークによるＱｏＳ管理の基本的な概念を示す説明図である。
【図２】本発明に係る通信経路選択システムを具備したオーバーレイネットワークの構成例を示すブロック図である。
【図３】図２におけるオーバーレイノードの本発明に係る構成例を示すブロックである。
【図４】図２における管理サーバ２０の本発明に係る構成例を示すブロック図である。
【図５】本発明に係る通信経路決定システムによる通信経路決定方法の第１の処理手順例を示すフローチャートである。
【図６】本発明に係る通信経路決定システムによる通信経路決定方法の第２の処理手順例を示すフローチャートである。
【図７】本発明に係る通信経路決定システムによる通信経路決定方法の第３の処理手順例を示すフローチャートである。
【図８】本発明に係る通信経路決定システムによる通信経路決定方法の第４の処理手順例を示すフローチャートである。
【図９】本発明に係る通信経路決定システムの第１の実行結果例を示す説明図である。
【符号の説明】
【０１１５】
１：オーバーレイネットワーク、１ａ〜１ｃ：オーバーレイノード、２：ＩＰネットワーク、２ａ〜２ｅ：ＩＰルータ、２０：管理サーバ、２０ａ：中継ノード状態管理部、２０ｂ：中継ノード候補決定部、２０ｃ：上位ノード決定部、２０ｄ：上位ノード管理部、２１〜２５：上位ノード、２６ａ〜２６ｄ：一般ノード、３１：オーバーレイノード、３１ａ：通信品質測定部、３１ｂ：通信品質取得部、３１ｃ：中継ノード決定部、３１ｄ：中継候補選択部、３１ｅ：上位ノード間通信品質取得部、３１ｆ：上位ノード間最適経路算出部、３１ｇ：一般・上位ノード間通信品質取得部、３１ｈ：一般ノード間最適経路算出部。
【技術分野】
【０００１】
本発明は、インターネット等のＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）ネットワークにおけるエンド・ツー・エンドの通信品質を向上させる技術に係り、特にＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させるのに好適な技術に関するものである。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Ｖｏｉｃｅ ｏｖｅｒ ＩＰ）やストリーミングに代表されるＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）に敏感な実時間アプリケーション等の収容も急速に発展している。
【０００３】
これに伴い・エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００４】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００５】
（２）インターネットは管理主体の異なる複数のＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００６】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えば非特許文献１に記載の、オーバーレイネットワークによるＱｏＳ管理技術が注目されている。
【０００７】
オーバーレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００８】
このような、オーバーレイネットワークによるＱｏＳ管理の基本的な概念を図１に例示する。図１において、１ａ〜１ｃはオーバーレイネットワーク１を構成するノード（オーバーレイノード）であり、２ａ〜２ｅはＩＰネットワーク２を構成するＩＰルータであり、ｘからｙに向けて、破線矢印で表わされる経路にトラヒックが流れているとする。また、この経路上には輻輳しているＩＰルータが存在しており、その結果として、ｘ，ｙ間のＱｏＳが低下しているとする。
【０００９】
このとき、オーバーレイノード１ａ，１ｂ，１ｃで形成されるオーバーレイネットワーク１を用いて、実線矢印で表される経路（ｘ→オーバーレイノード１ａ→オーバーレイノード１ｂ→オーバーレイノード１ｃ→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【００１０】
実際、非特許文献３，４，５では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。しかし、非特許文献３と非特許文献５の結果は、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
【００１１】
すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間の品質測定情報を用いて通信経路の計算を行うことは現実的には不可能であるという問題がある。
【００１２】
このような問題を回避するため、非特許文献４では、迂回経路を提供する中継ノード候補数を制限した場合を評価している。しかし、中継ノード候補は単にランダムに選択しているにすぎず、中継ノード候補の選択方法までは検討していなかった。
【００１３】
一方、特許文献１において、本発明者らは、中継ノード候補を計測データに基づいて一定数以下に適切に制限することにより、全ノードを中継候補として経路探索を行った最適な場合とほぼ同等のＱｏＳ向上を図れることを示している。
【００１４】
しかしながら、この技術では、全てのノードペアに対する経路について、全ノードペアの直通の品質を用いて、直通路と迂回路の通信品質を比較することにより適切な経路を決定していた。
【００１５】
つまり、中継路探索においては全経路探索は行っていない（中継ノード候補を一定数に制限している）ものの、各ノードペアでの通信品質は依然として測定する必要があり、測定負荷自体は低減できていないという問題があった。
【００１６】
【特許文献１】特開２００８−０５３７９４号公報
【非特許文献１】Ｌ．Ｚｈｉ ａｎｄ Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ ｒｏｕｔｉｎｇ ｉｎ ｏｖｅｒｌａｙ ｎｅｔ−ｗｏｒｋｓ，” ＩＥＥＥ Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ Ｃｏｍｍｕｎ．ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ ２００４．
【非特許文献２】ＷＩＤＥ プロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジヱクト研究報告書，第１７部，２００２．
【非特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献４】Ｓ．Ｒｅｗａｓｋａｒ ａｎｄ Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ ｔｈｅ Ｓｃａｌａｂｉｌｉｔｙ ｏｆ Ｏｖｅｒｌａｙ Ｒｏｕｔｉｎｇ Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，” Ｐｒｏｃ．；ＰＡＭ２００４，Ａｐｒｉｌ ２００４．
【非特許文献５】Ｓ．Ｂａｎｅｒｊｅｅ， Ｔ．Ｇ．Ｇｒｉｆｉｎ ａｎｄ Ｍ．Ｐｉａｓ，“Ｔｈｅ Ｉｎｔｅｒｄｏｍａｉｎ Ｃｏｎｎｅｃｔｉｖｉｔｙ ｏｆ ＰｌａｎｅｔＬａｂ Ｎｏｄｅｓ，” Ｐｒｏｃ．ＰＡＭ ２００４，Ａｐｒｉｌ ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１７】
解決しようとする問題点は、従来の技術では、全てのノードペアに対する経路について、全ノードペアの直通の品質を測定する必要がある点である。
【００１８】
本発明の目的は、これら従来技術の課題を解決し、各ノードペアでの通信品質の測定に係る負荷を低減することで、オーバーレイネットワークにおけるエンド・ツー・エンドの通信品質を効率的に向上させることである。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、本発明では、オーバーレイネットワークを構成するノード（オーバーレイノード）を、ごく一部の少数の上位ノードと、それ以外の大多数の一般ノードの２階層に分け、少数の上位ノード間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。（１）具体的には、まず、オーバーレイネットワークを構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、Ｍ個のノードを上位ノードとして選択し、残りのＮ−Ｍ個を一般ノードとする。次に、各上位ノード間ではフルメッシュで通信品質（例えば、遅延時間や帯域あるいはパケット損失率など）を測定して最適な経路を決定し、一般ノードと当該一般ノードが接続された各上位ノード間では、各接続毎の通信品質を測定して最適な経路を決定することで、それぞれの経路選択においても、直通の経路を含めて最適な経路を決定する。そして、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。このように、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質コスト削減を可能としている。
【発明の効果】
【００２０】
本発明によれば、オーバーレイノードをさらに上位ノードと一般ノードに分け、一般ノードと一般ノード間はオーバーレイネットワークにおいて論理的に接続されていないとすることで、一般ノード間の品質測定結果を不要とすることができ、大多数の一般ノード間の品質コスト削減が可能となり、オーバーレイネットワークにおける測定コストを削減しつつ、通信品質の改善を図ることが可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図２は、本発明に係る通信経路選択システムを具備したオーバーレイネットワークの構成例を示すブロック図であり、図３は、図２におけるオーバーレイノードの本発明に係る構成例を示すブロック、図４は、図２における管理サーバ２０の本発明に係る構成例を示すブロック図である。
【００２２】
図２におけるオーバーレイネットワークでは、オーバーレイノードを、Ｍ個の上位ノード２１〜２５（ここではＭ＝５個）とそれ以外の一般ノード２６ａ〜２６ｄに分け、上位ノード２１〜２５間ではフルメッシュで論理的に接続し、一般ノード２６ａ〜２６ｄは各上位ノード２１〜２５と論理的に接続しているとする。
【００２３】
尚、ここで、論理的に接続されているとは、その接続先ノードのＩＰアドレスを知っており、通信可能な状態にある。
【００２４】
上位ノード２１〜２５と一般ノード２６ａ〜２６ｄおよび管理サーバ２０のそれぞれは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置を含むコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００２５】
すなわち、上位ノード２１〜２５と一般ノード２６ａ〜２６ｄを含むオーバーレイノードは、図３のオーバーレイノード３１として示すように、プログラムされたコンピュータ処理を実行する機能として、通信品質測定部３１ａと通信品質取得部３１ｂ、中継ノード決定部３１ｃ、中継候補選択部３１ｄ、上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈを具備し、管理サーバ２０は、図４に示すように、プログラムされたコンピュータ処理を実行する機能として、中継ノード状態管理部２０ａと中継ノード候補決定部２０ｂ、上位ノード決定部２０ｃ、上位ノード管理部２０ｄを具備している。
【００２６】
このような構成において、本例では、図１で示したオーバーレイネットワーク１を構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、図２に示すように、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【００２７】
以下、本発明に係る第１〜第７の技術について説明する。
【００２８】
まず、第１の技術について説明する。例えば、オーバーレイネットワーク１を構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、Ｍ個のノードを上位ノードとして選択し、残りのＮ−Ｍ個を一般ノードとする。図２の例では、５個の上位ノード２１〜２５と多数の一般ノード２６ａ〜２６ｄに分けられている。
【００２９】
各上位ノード間ではフルメッシュで通信品質を測定して最適な経路を決定し、また、一般ノードと当該一般ノードが接続された各上位ノード間では、各接続毎の通信品質を測定して最適な経路を決定することで、それぞれの経路選択においても、直通の経路を含めて最適な経路を決定する。
【００３０】
そして、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。
【００３１】
より詳細には、オーバーレイネットワーク１を構成する各ノード（オーバーレイノード２１〜２５，２６ａ〜２６ｄ）間の通信経路を、プログラムされたコンピュータ処理により決定するために、プログラムされたコンピュータ処理を実行する手段として、上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈを設けており、まず、上位ノード間通信品質取得部３１ｅにより、オーバーレイネットワーク１を構成する全てのＮ個のノード２１〜２５，２６ａ〜２６ｄから予め選択されたＭ個の上位ノード２１〜２５間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して図示していない記憶装置に記憶する。
【００３２】
次に、上位ノード間最適経路算出部３１ｆにより、上位ノード間最適経路算出部３１ｆが測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する。
【００３３】
さらに、一般・上位ノード間通信品質取得部３１ｇにより、上位ノード２１〜２５以外の残りのＮ−Ｍ個の一般ノード２６ａ〜２６ｄのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する。
【００３４】
そして、一般ノード間最適経路算出部３１ｈにより、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報および一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する。
【００３５】
このように、本例では、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質測定に要するコストを削減することが可能となる。
【００３６】
次に、第２，第３の技術について説明する。この第２，第３の技術は、通信品質に関するものであり、第２の技術においては、通信品質としてノード間の遅延時間を用い、ノード間のメトリックを遅延時間とし、上位ノード２１〜２５間はフルメッシュで接続されているとして、例えば上位ノード２１から上位ノード２４への経路は、上位ノード間最適経路算出部３１ｆにおいて、遅延をメトリックとして、ダイクストラ法で最短経路を探索しておきそれを最適な経路として決定する。
【００３７】
また、例えば一般ノード２６ａから上位ノード２４への最適経路は、一般ノード２６ａと全ての上位ノード２１〜２５が接続されているとし、また上位ノード２１〜２５間はフルメッシュで接続されているとし、一般ノード間最適経路算出部３１ｈにおいて、そのトポロジ上でダイクストラ法により最短経路を探索しておき、それを最適経路とする。
【００３８】
そして、例えば一般ノード２６ａから他の一般ノード２６ｄへの最適経路は、一般ノード２６ａと全ての上位ノード２１〜２５および全ての上位ノード２１〜２５と一般ノード２６ｄが接続されているとしたトポロジ上で最短経路を探索し、それを最適経路とする。
【００３９】
また、第３の技術では、上述の第２の技術のように遅延を品質とする代わりに、ノード間の利用可能帯域を品質として用い、品質の逆数をノード間のメトリックとして、あるいは、ノード間のパケット損失率またはパケット損失数を通信品質メトリックとしてダイクストラ法により最短経路を探索して最適経路とすることで、様々な品質メトリックに対応可能とする。
【００４０】
次に、第４の技術について説明する。この第４の技術では、上述の第１〜第３の技術のように、一般ノードから全ての上位ノードとの間を接続する代わりに、一般ノードから最も近い上位ノードのみ接続するものである。
【００４１】
すなわち、一般ノード間最適経路算出部３１ｈは、一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、各一般ノード毎に当該一般ノードに最適な通信品質で接続された上位ノードを１つ特定して記憶装置に記憶し、特定して記憶装置に記憶した特定情報を用いて、発信元の一般ノードに最適な通信品質で接続された発信側上位ノードと着信先の一般ノードに最適な通信品質で接続された着信側上位ノードを特定し、特定した発信側上位ノードと着信側上位ノード間の最適な通信品質の経路を、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報を用いて特定する。
【００４２】
次に、第５〜第７の技術について説明する。この第５〜第７の技術は、Ｍ個の上位ノードを選択する技術に関するものである。
【００４３】
第５の技術では、まず、オーバーレイネットワークによる経路制御開始から予め定めた時間までの間、一定周期毎に各オーバーレイノード（２１〜２５，２６ａ〜２６ｄ）間でフルメッシュで通信品質を測定し、Ｍ個のノードをランダムに中継ノード候補として選択する。
【００４４】
次に、ノードｉからノードｊへの経路を決定する際、ノードｉから中継ノード候補群に属するノードｋまでの通信品質をｄ（ｉ，ｋ）、ノードｋからノードｊまでの通信品質をｄ（ｋ，ｊ）とし、トータルな通信品質「ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を最小にする中継候補としてのノードｋ＊を探索し、ノードｉからノードｊの直通の通信品質ｄ（ｉ，ｊ）とトータルな通信品質「ｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）」を比較し、後者（トータルな通信品質）が小さければ、当該ノードｋ＊を中継ノードとして迂回経路を構築する。
【００４５】
このような処理を、各ノードペアについて実行し、ノードｋが中継ノードとして選択された回数をカウントし、次周期の中継ノード候補をＭ個選択する際には、過去に中継ノードとして選択された回数に応じた確率で選択する。
【００４６】
そして、このような処理を予め定めた時間までの間、繰り返し実行し、予め定めた時間経週後は、それまでに中継ノードとして選択された回数の多いもの上位Ｍ個を上位ノードとして選択する。
【００４７】
尚、このような上位ノードの選択技術には、上述の特許文献１に記載の技術を部分的に用いている。つまり、最初のうちは、全ノードペアの品質測定を実施し、特許文献１に記載の技術を用いて、良い中継路を提供できるＭ個のノードを推定する処理を、予め定めた時間まで実施し、その結果、中継ノードとして貢献した回数の多いものを上位ノードとして用いる。
【００４８】
第６の技術では、上述の第５の技術のように各ノード間においてフルメッシュで品質測定する代わりに、まずＮ個のノードからランダムにＭ個を選択し、それらを上位ノードとし、それら以外を一般ノードとして、上述の第１の技術のように、上位ノード間フルメッシュで品質測定し、また一般ノードと上位ノード間も品質測定をする。
【００４９】
そして、また、Ｎ個のノードの中からＭ’個（Ｍ’＞Ｍ）を中継ノード候補として選択する。ここで、上位ノードｉから上位ノードｊ、あるいは一般ノードｉから上位ノードｊ、あるいは上位ノードｉから一般ノードｊへの直通の通信品質をｄ（ｉ，ｊ）とし、Ｍ’個の中継ノード候補ｋを中継としたときの通信品質（ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ））を最小にするノードｋ＊を中継ノード候補とし、通信品質ｄ（ｉ，ｊ）と通信品質ｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）を比較して後者の通信品質の方がよければ、ノードｋ＊の得点をカウントアップし、この処理を直通の品質が測定されている全ノードペアに対して実行し、次周期には、その得点（カウントアップ結果）に応じてＭ’個の中継ノード候補を選択すると共に、Ｍ’個の中継ノード候補の特に上位Ｍ個を上位ノードとして選択し、これを繰り返すことにより現時点での上位ノードＭ個を決定する。あるいは、第１，第２の技術を用いて、ダイクストラ法により各ノードペアの最短経路を決定し、その結果ノードｋ＊が中継ノードとして選択された回数をカウントアップし、次周期には、当該回数に応じてＭ個の上位ノードを選択しても良い。
【００５０】
上述の第５の技術では、最初のうちはフルメッシュ測定を許容していたのに対し、本第６の技術では、最初からフルメッシュ測定は実施しないで、直通の品質が測定できている上位ノードと上位ノード間、および一般ノードと上位ノード間、上位ノードと一般ノード間のみを用いて、これらペアの直通路の品質と、Ｍ個の上位ノード群の中から最も品質の良い迂回路を提供する中継ノードを探索して、それを用いたときの迂回路の品質を比較し、後者の方が良い品質を提供できる場合には、そのときの中継ノードに得点を与え、これを繰り返し実施して、次周期にＭ個の上位ノードを選択する際には、過去の得点の高いものを高い確率で選択するようにする。
【００５１】
得点としては、時点ｎにおいてノードｋが中継ノードとして選択された回数をＣ’（ｎ，ｋ）として、時点ｎ＋１での得点Ｃ（ｎ＋１，ｋ）を「Ｃ（ｎ＋１，ｋ）＝（１−α）Ｃ（ｎ，ｋ）＋αＣ’（ｎ，ｋ）」により更新する。ここで、αは予め定める平滑化パラメータで、初期値Ｃ（０，ｋ）＝０とする。
【００５２】
この得点Ｃ（ｎ，ｋ）を用いて、時点ｎにおいてノードｋを上位ノードとして確率ｐ（ｎ，ｋ）で選択する。ここで「ｐ（ｎ，ｋ）＝Ｃ（ｎ，ｋ）／ΣＣ（ｎ，ｊ）」、あるいは、「ｐ（ｎ，ｋ）＝ｅｘｐ｛Ｃ（ｎ，ｋ）−１｝／Σｅｘｐ｛Ｃ（ｎ，ｊ）−１｝」、などが確率ｐ（ｎ，ｋ）の候補となる。
【００５３】
第７の技術では、ある時点においては各ノード間の通信品質をフルメッシュで測定し、ノードｉとノードｊ以外の各ノードを中継候補に用いてノードｉからノードｊへの最適な通信経路を探索し、これを全てのノードペアについて実施し、その結果、最適な中継ノードとして選択された回数が多い順にＭ個を、それ以降の上位ノードとして決定する。
【００５４】
以下、＜第１の実施例＞として、上述の第６の技術により上位ノードを選択し、上述の第２の技術によりノード間の経路を決定する場合について、図２〜図４を用いて説明する。尚、一定周期毎に以下の動作を実施するとし、ｎ番目の周期を時点ｎと呼ぶ。
【００５５】
図３における通信品質測定部３１ａは、測定周期τ毎に自身（仮にオーバーレイノードｉとする）と他の上位ノードｊとの間の遅延時間ｄ（ｉ，ｊ）を測定し、図示していない記憶装置に記憶する。このように遅延時間測定を実施したら、その旨を中継候補選択部３１ｄに通知する。
【００５６】
中継候補選択部３１ｄは、図４における管理サーバ２０の中継ノード候補決定部２０ｂから、時点ｎでのＭ’個の中継ノード候補を読み出す。同時に、中継候補選択部３１ｄは、通信品質取得部３１ｂに対して、各中継ノード候補ｋ（ｋ＝１〜Ｍ’）から当該中継ノード候補ｋと上述の上位ノードｊ間の遅延時間測定結果「ｄ（ｋ，ｊ）」を取得するように指示する。
【００５７】
通信品質取得部３１ｂは、中継候補選択部３１ｄからの指示に応じて、各中継ノード候補ｋから、当該中継ノード候補ｋと上位ノードｊ間の遅延時間測定結果「ｄ（ｋ，ｊ）」を取得し、中継ノード決定部３１ｃにそれを通知する。
【００５８】
以上の手順を、Ｍ’個の全ての中継ノード候補に対して実施する。
【００５９】
中継ノード決定部３１ｃは、自ノードｉから中継ノード候補ｋまでの遅延時間ｄ（ｉ，ｋ）を通信品質測定部３１ａから取得し、取得した遅延時間ｄ（ｉ，ｋ）と、通信品質取得部３１ｂから通知された中継ノード候補ｋと着信先の上位ノードｊの間の遅延時間ｄ（ｋ，ｊ）とを用いて、「ｄ（ｉ，ｊ）＞ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を満たす中継ノード候補ｋがＭ’個の候補の中に存在するか否かを調べる。
【００６０】
存在しない場合は、自ノードｉから着信先の上位ノードｊの直通路を、最適な通信経路として決定し、存在する場合は、右辺（「ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」）を最小にする中継ノード候補のノードｋ＊を特定し、このノードｋ＊を中継ノードとして選択し、その旨を管理サーバ２０内の中継ノード状態管理部２０ａへ通知する。
【００６１】
以上の手順を全ての上位ノードｊに対して実施する。
【００６２】
管理サーバ２０内の中継ノード状態管理部２０ａは、中継ノード決定部３１ｃからノードｋ＊が中継ノードとして選択された旨の通知を受けると、当該ノードｋ＊が中継ノードとなった回数Ｃ’（ｎ，ｋ＊）を、「Ｃ’（ｎ，ｋ＊）←Ｃ’（ｎ，ｋ＊）＋１」としてカウントアップする。
【００６３】
以上を、ｎ番目の周期が終わるまで繰り返して、各ノードの中継ノードとなった回数を計数する。そして、ｎ＋１番目の測定周期になれば、全てのノードの得点Ｃ（ｎ＋１，ｋ）を「Ｃ（ｎ＋１，ｋ）＝（１−α）Ｃ（ｎ，ｋ）＋αＣ’（ｎ，ｋ）」により更新する。尚、ここで、αは予め定める平滑化パラメータで「０＜α＜１」であり、Ｃ（ｎ，ｋ）の初期値は「Ｃ（０，ｋ）＝１（全てのｋ）」とする。
【００６４】
管理サーバ２０内の中継ノード候補決定部２０ｂでは、時点ｎのノードｋの得点Ｃ（ｎ，ｋ）を用いて、時点ｎにおけるＭ’個の中継ノード候補を確率ｐ（ｎ，ｋ）で選択する。ここで、「ｐ（ｎ，ｋ）＝Ｃ（ｎ，ｋ）／ΣＣ（ｎ，ｊ）」、あるいは、「ｐ（ｎ，ｋ）＝ｅｘｐ｛Ｃ（ｎ，ｋ）−１｝／Σｅｘｐ｛Ｃ（ｎ，ｊ）−１｝」、などがｐ（ｎ，ｋ）の候補となる。
【００６５】
一方、管理サーバ２０内の上位ノード決定部２０ｃでは、確率ｐ（ｎ，ｋ）あるいは得点Ｃ（ｎ，ｋ）を用いて、Ｍ個の上位ノードを決定する。
【００６６】
例えば、確率ｐ（ｎ，ｋ）を用いる場合には、中継ノード候補を選択した場合と同様に、確率ｐ（ｎ，ｋ）でノードｋを上位ノードとして選択する。
【００６７】
また、得点Ｃ（ｎ，ｋ）を用いる場合には、得点の高い上位Ｍ個を上位ノードとして選択する。
【００６８】
尚、以上の上位ノードの選択技術については、中継候補の更新処理の周期よりも長い周期で実施しても良いし、ネットワークの状態に変化が検知されたときのみ、上述の手順で上位ノードを再決定しても良い。
【００６９】
上位ノード決定部２０ｃは、上位ノードとして決定したノードに対して、上位ノードとして決定した旨と、他のどのノードが上位ノードであるかを通知する。
【００７０】
上位ノードとして決定を受けた場合、当該上位ノードは、上位ノード間通信品質取得部３１ｅにより、他の上位ノードとの間の遅延時間を測定しておき、その結果を他の上位ノードと共有する。また、その結果を管理サーバ２０に通知する。この際、上位としての各ノードは、上位ノード間最適経路算出部３１ｆにより他の上位ノードヘの最短経路をダイクストラ法で計算しておき、それを他ノードヘのオーバレイ経路とする。
【００７１】
一方、一般ノードとしてのノードｘは、一般・上位ノード間通信品質取得部３１ｇにより、管理サーバ２０内の上位ノード管理部２０ｄから、どのノードが上位ノードであるかの情報と、上位ノード間の遅延時間情報を入手し、さらに、通信したい着信先ノードｙから、当該着信先ノードｙと上位ノード間の遅延時間を測定した結果を入手する。
【００７２】
そして、一般ノードｘは、これらの入手した情報を用いて、一般ノード間最適経路算出部３１ｈにより、上位ノードを用いた場合の自ノードｘから着信先ノードｙへの最短経路をダイクストラ法で計算し、それをオーバレイ経路とする。
【００７３】
次に、＜第２の実施例＞として上述の第５の技術に関して説明する。上述の＜第１の実施例＞のように、上位ノード間、上位ノードと一般ノード間のみで中継ノードの得点をカウントする代わりに、Ｍ個の上位ノードを決定する際に、オーバーレイネットワークによる経路制御開始から予め定めた時間までの間は、一定周期毎に各オーバーレイノード間でフルメッシュで通信品質を測定し、Ｍ個のノードをランダムに中継ノード候補として選択する。
【００７４】
ノードｉからノードｊへの経路を決定する際、ノードｉから該中継ノード候補群に属するノードｋまでの通信品質をｄ（ｉ，ｋ）、ノードｋからノードｊまでの品質をｄ（ｋ，ｊ）とし、ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）を最小にするノードｋ＊を探索し、ノードｉからノードｊの直通の品質ｄ（ｉ，ｊ）とｄ（ｉ，ｋ＊）＋ｄ（ｋ＊，ｊ）を比較し、後者が小さければ、ノードｋ＊を中継ノードとして迂回経路を構築し、これを各ノードペアについて実施し、ノードｋが中継ノードとして選択された回数をカウントし、次周期の中継ノード候補をＭ個選択する際には、過去に中継ノードとして選択された回数に応じた確率で選択する。
【００７５】
これを予め定めた時間までの間、実施する。予め定めた時間経過後は、それまでに中継ノードとして選択された回数の多いもの上位Ｍ個を上位ノードとして選択する。
【００７６】
次に、＜第３の実施例＞として上述の第７の技術について説明する。上述の＜第１の実施例＞および＜第２の実施例＞では、上位ノードを決定するために、中継ノード候補の選択を実施していたが、そうする代わりに、ここでは、ある時点においては各ノード間の通信品質をフルメッシュで測定し、ノードｉ，ｊ以外のノードを中継候補に用いてノードｉからノードｊへの最適な通信経路を探索し、これを全てのノードペアについて実施し、その結果、最適な中継ノードとして選択された回数に関する上位Ｍ個を、それ以降の上位ノードとして決定する。
【００７７】
次に、図５〜図８を用いて、本発明に係る通信経路決定方法について説明する。図５は、本発明に係る通信経路決定システムによる通信経路決定方法の第１の処理手順例を示すフローチャートであり、図６は、本発明に係る通信経路決定システムによる通信経路決定方法の第２の処理手順例を示すフローチャート、図７は、本発明に係る通信経路決定システムによる通信経路決定方法の第３の処理手順例を示すフローチャート、図８は、本発明に係る通信経路決定システムによる通信経路決定方法の第４の処理手順例を示すフローチャートである。
【００７８】
図５は、本例に係る一般ノード間の最適な通信経路を決定する際の処理手順例を示し、図６〜図８はＭ個の上位ノードを選択する際の処理手順例を示している。
【００７９】
図５に示すように、本例の通信経路決定システムにおいては、まず、図３の上位ノード間通信品質取得部３１ｅにより、オーバーレイネットワークを構成する全てのＮ個のノードから予め選択されたＭ個の上位間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する（ステップＳ５０１）。
【００８０】
次に、上位ノード間最適経路算出部３１ｆにより、上位ノード間最適経路算出部３１ｆが測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する（ステップＳ５０２）。
【００８１】
さらに、一般・上位ノード間通信品質取得部３１ｇにより、上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する（ステップＳ５０３）。
【００８２】
そして、一般ノード間最適経路算出部３１ｈにより、上位ノード間最適経路算出部３１ｆが記憶装置に記憶した決定情報および一般・上位ノード間通信品質取得部３１ｇが記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する（ステップＳ５０４）。
【００８３】
また、図６に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、Ｎ個の各ノードからランダムにＭ個のノードを中継ノード候補として選択する（ステップＳ６０１）。
【００８４】
次に、起動から予め定められた時間Ｔが経過するまで（ステップＳ６０２）、一定周期毎に、下記のステップＳ６０３〜Ｓ６０８の処理を実行する。
【００８５】
ステップＳ６０３においては、Ｎ個の各ノード間のそれぞれの通信品質を、各ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶し、ステップＳ６０４においては、記憶装置に記憶したＮ個の各ノード間のそれぞれの通信品質を用いて、Ｍ個の中継ノード候補を中継した、中継ノード候補以外のＮ−Ｍ個の各ノードのペア間の通信品質を算出する。
【００８６】
ステップＳ６０５においては、ステップＳ６０４の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択し、ステップＳ６０６においては、ステップＳ６０５の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する。
【００８７】
さらに、次周期の中継ノード候補選択時に（ステップＳ６０７）、ステップＳ６０６の手順で記憶装置に記憶した回数に応じた確率でＭ個の中継ノード候補を選択する（ステップＳ６０８）。
【００８８】
そして、時間Ｔの経過後（ステップＳ６０２）、ステップＳ６０６の手順により記憶装置に記憶した選択回数が多い上位Ｍ個の中継ノードを上位ノードとして選択する（ステップＳ６０９）。
【００８９】
また、図７に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、Ｎ個の各ノードからランダムにＭ”個のノードを中継ノード候補として選択する（ステップＳ７０１）。
【００９０】
次に、選択したＭ”個の中継ノード候補からＭ個の上位ノードを選択し（ステップＳ７０２）、以下、予め定められた周期（時間ｔ間隔）で（ステップＳ７０３）、ステップＳ７０４〜Ｓ７１０の処理を実行する。
【００９１】
ステップＳ７０４においては、Ｍ個の各上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶し、ステップＳ７０５において、上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する。
【００９２】
ステップＳ７０６においては、記憶装置に記憶したＭ個の各上位ノード間のそれぞれの通信品質およびＮ−Ｍ個の一般ノードと上位ノード間の通信品質を用いて、Ｍ”個の各中継ノード候補を中継した、上位ノード同士からなる各ノードペア間の通信品質および上位ノードと一般ノードからなる各ノードペア間の通信品質を算出する。
【００９３】
ステップＳ７０７においては、ステップＳ７０６の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択し、ステップＳ７０８においては、ステップＳ７０７の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する。
【００９４】
さらに、次周期の上位ノードおよび中継ノード候補の選択時に（ステップＳ７０９）、ステップＳ７０８の手順で記憶装置に記憶した回数に応じた確率でＭ個の上位ノードと中継ノード候補およびＭ”−Ｍ個の中継ノード候補を選択する（ステップＳ７１０）。
【００９５】
そして、各ノードからの要求があれば（ステップＳ７０３）、当該時刻における、ステップＳ７１０の手順で選択したＭ個の上位ノードを、図５に示す各手順による通信経路決定手順用に出力する（ステップＳ７１１）。
【００９６】
また、図８に示すように、本例の通信経路決定システムにおいては、全てのオーバレイノード（Ｎ個）からＭ個の上位ノードを選択するために、まず、任意の時点での各ノード間の通信品質をフルメッシュで測定して記憶装置に記憶する（ステップＳ８０１）。
【００９７】
次に、記憶装置に記憶した各ノードそれぞれの通信品質を用いて、各ノードペア間の最適な通信経路を選択し（ステップＳ８０２）、最適な通信経路を構成する中継ノードとして選択された回数を各ノード毎に計数して記憶装置に記憶し（ステップＳ８０３）、そして、記憶装置に記憶した選択回数が多い上位Ｍ個のノードを上位ノードとして選択する（ステップＳ８０４）。
【００９８】
このようにしてＭ個の上位ノードを選択して実際の通信経路決定を行った際の、評価結果を、図９，１０に示す。図９は、本発明に係る通信経路決定システムの第１の実行結果例を示す説明図である。
【００９９】
尚、図９の例では、インターネット上での約２００台のオーバーレイノードのノード間で、測定されたノード間の遅延時間を用いた。
【０１００】
ある時点において、各ノードペアに対して、全経路探索を実施し、その結果最適な経路を特定し、それを全ノードペアについて実施した。その結果、最適な中継路を提供した上位２０個を上位ノードとして決定した。
【０１０１】
そして、その２０個の上位ノードのみを用いて、オーバレイの経路を決定した際の、各ノードペアの遅延時間の累積分布を図９に示す。
【０１０２】
図９において、凡例（ＴｙｐｅＡ）がそのときの結果である。比較として、ｏｐｔｉｍａｌとは、全経路探索をしたときの最適路であり、ｄｉｒｅｃｔとは迂回制御をしない直通路の遅延時間結果である。
【０１０３】
また、比較として、上位Ｍノードの選び方として、ＴｙｐｅＡと同様に全経路探索を行った後、経路として選ばれなかったノード間リンクは削除し、その結果残ったトポロジにおいて、次数（ノードの接続リンク数）の高いもの上位２０個を選んだ結果をＴｙｐｅＢとして表示している。
【０１０４】
また、図９におけるＴｙｐｅＣは、ノードのほかのノードヘの遅延時間の平均を計算して、その平均遅延時間が小さいものから２０個選択した際の結果である。
【０１０５】
図５に示す結果により、本例におけるＴｙｐｅＡでは、ｏｐｔｉｍａｌとほぼ同等の遅延の改善がみられることが確認できる。
【０１０６】
以上、図１〜図９を用いて説明したように、本例の通信経路決定システム・方法では、図１で示したオーバーレイネットワーク１を構成する各ノード（オーバーレイノード１ａ〜１ｃ）を、図２に示すように、ごく一部の少数の上位ノード２１〜２５と、それ以外の大多数の一般ノード２６ａ〜２６ｄの２階層に分け、少数の上位ノード２１〜２５間についてはフルメッシュでの通信品質を測定するが、大多数の一般ノード２６ａ〜２６ｄ間については、直通の通信品質を測定することなく、オーバーレイネットワークにおける高品質な通信経路を決定する。
【０１０７】
すなわち、オーバーレイネットワーク１を構成する各オーバーレイノードｉ（ｉ＝１〜Ｎ）の中から、ごく少数のＭ個のノードを上位ノードとして選択し、残りの大多数のＮ−Ｍ個を一般ノードとする。
【０１０８】
そして、ごく少数である各上位ノード間ではフルメッシュで通信品質を測定して最適な経路を決定するが、大多数の一般ノードは、自一般ノードが接続された各上位ノード間において、各接続毎の通信品質を測定して最適な経路を決定し、一般ノードｊと他の一般ノードｋへの経路は、ノードｊからノードｋへの直通路は使わず、ノードｊから当該ノードｊが接続された各上位ノード、および、この各上位ノードからノードｋまでの経路の内で最適な経路を決定する。
【０１０９】
このように、オーバーレイネットワークを構成するノード（オーバーレイノード）を、少数の上位ノードと大多数の一般ノードに分け、一般ノードと一般ノードとの間はオーバーレイネットワークにおいて論理的に接続されていないとして、当該一般ノード間の品質測定結果は不要とすることにより、大多数の一般ノード間の品質測定に要するコストを削減することが可能となる。
【０１１０】
このことにより、オーバーレイネットワークにおける測定コストを削減しつつ、通信品質の改善を図ることが可能となる。
【０１１１】
尚、本発明は、図１〜図９を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、各ノードに、本発明に係る通信経路決定を行う機能（上位ノード間通信品質取得部３１ｅ、上位ノード間最適経路算出部３１ｆ、一般・上位ノード間通信品質取得部３１ｇ、一般ノード間最適経路算出部３１ｈ）を設けた構成として説明しているが、これらの各機能を管理サーバ２０側に設け、各一般ノードからの要求に応じて管理サーバ２０で通信経路を決定し、決定した結果を要求元の一般ノードに通知する構成とすることでも良い。
【０１１２】
また、図２に示した上位ノードを５個として例を示しているが、図９において説明したように、２０個とすることでも、また、その他の個数とすることでも良い。
【０１１３】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１１４】
【図１】オーバーレイネットワークによるＱｏＳ管理の基本的な概念を示す説明図である。
【図２】本発明に係る通信経路選択システムを具備したオーバーレイネットワークの構成例を示すブロック図である。
【図３】図２におけるオーバーレイノードの本発明に係る構成例を示すブロックである。
【図４】図２における管理サーバ２０の本発明に係る構成例を示すブロック図である。
【図５】本発明に係る通信経路決定システムによる通信経路決定方法の第１の処理手順例を示すフローチャートである。
【図６】本発明に係る通信経路決定システムによる通信経路決定方法の第２の処理手順例を示すフローチャートである。
【図７】本発明に係る通信経路決定システムによる通信経路決定方法の第３の処理手順例を示すフローチャートである。
【図８】本発明に係る通信経路決定システムによる通信経路決定方法の第４の処理手順例を示すフローチャートである。
【図９】本発明に係る通信経路決定システムの第１の実行結果例を示す説明図である。
【符号の説明】
【０１１５】
１：オーバーレイネットワーク、１ａ〜１ｃ：オーバーレイノード、２：ＩＰネットワーク、２ａ〜２ｅ：ＩＰルータ、２０：管理サーバ、２０ａ：中継ノード状態管理部、２０ｂ：中継ノード候補決定部、２０ｃ：上位ノード決定部、２０ｄ：上位ノード管理部、２１〜２５：上位ノード、２６ａ〜２６ｄ：一般ノード、３１：オーバーレイノード、３１ａ：通信品質測定部、３１ｂ：通信品質取得部、３１ｃ：中継ノード決定部、３１ｄ：中継候補選択部、３１ｅ：上位ノード間通信品質取得部、３１ｆ：上位ノード間最適経路算出部、３１ｇ：一般・上位ノード間通信品質取得部、３１ｈ：一般ノード間最適経路算出部。
【特許請求の範囲】
【請求項１】
オーバーレイネットワークを構成するノード（オーバーレイノード）間の通信経路を、プログラムされたコンピュータ処理により決定する通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記オーバーレイネットワークを構成する全てのＮ個のノードから予め選択されたＭ個の上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手段と、
該第１の手段が測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する第２の手段と、
上記上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する第３の手段と、
上記第２の手段が記憶装置に記憶した決定情報および上記第３の手段が記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する第４の手段と
を有することを特徴とする通信経路決定システム。
【請求項２】
請求項１に記載の通信経路決定システムであって、
上記通信品質としてノード間の遅延時間を用い、
上記第２の手段は、該遅延時間をノード間のメトリックとしたダイクストラ法により各上位ノード間の最短経路を探索し、該最短経路を上記最適な通信品質の経路として決定する
ことを特徴とする通信経路決定システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の通信経路決定システムであって、
上記通信品質としてノード間の利用可能帯域を用い、
上記第２の手段は、該利用可能帯域の逆数をノード間のメトリックとしたダイクストラ法により各上位ノード間の最短経路を探索し、該最短経路を上記最適な通信品質の経路として決定する
ことを特徴とする通信経路決定システム。
【請求項４】
請求項１から請求項３のいずれかに記載の通信経路決定システムであって、
上記第４の手段は、
上記第３の手段が記憶装置に記憶した通信品質測定情報を用いて、各一般ノード毎に当該一般ノードに最適な通信品質で接続された上位ノードを１つ特定して記憶装置に記憶する手段と、
該手段で特定して記憶装置に記憶した特定情報を用いて、発信元の一般ノードに最適な通信品質で接続された発信側上位ノードと着信先の一般ノードに最適な通信品質で接続された着信側上位ノードを特定する手段と、
該手段で特定した発信側上位ノードと着信側上位ノード間の最適な通信品質の経路を、上記第２の手段が記憶装置に記憶した決定情報を用いて特定する手段と
を有することを特徴とする通信経路決定システム。
【請求項５】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
Ｎ個の各ノードからランダムにＭ個のノードを中継ノード候補として選択する第８の手段と、
起動から予め定められた時間Ｔが経過するまで、一定周期毎に、第１〜第４の手順の処理
（Ｎ個の各ノード間のそれぞれの通信品質を、各ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手順、
記憶装置に記憶したＮ個の各ノード間のそれぞれの通信品質を用いて、
Ｍ個の中継ノード候補を中継した、中継ノード候補以外のＮ−Ｍ個の各ノードのペア間の通信品質を算出する第２の手順、
該第２の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択する第３の手順、
該第３の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する第４の手順、
次周期の中継ノード候補選択時に、上記第４の手順で記憶装置に記憶した回数に応じた確率でＭ個の中継ノード候補を選択する第５の手順）
を繰り返し実行する第９の手段と
を具備し、
上記時間Ｔの経過後、上記第９の手段が第４の手順により記憶装置に記憶した選択回数が多い上位Ｍ個の中継ノードを上記上位ノードとして選択することを特徴とする
通信経路決定システム。
【請求項６】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
Ｎ個の各ノードからランダムにＭ”個のノードを中継ノード候補として選択する第８の手段と、
上記Ｍ”個の中継ノード候補からＭ個の上位ノードを選択する第９の手段と、
予め定められた周期で、第１〜第５の手順の処理（
Ｍ個の各上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手順、
上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する第２の手順、
記憶装置に記憶したＭ個の各上位ノード間のそれぞれの通信品質およびＮ−Ｍ個の一般ノードと上位ノード間の通信品質を用いて、Ｍ”個の各中継ノード候補を中継した、上位ノード同士からなる各ノードペア間の通信品質および上記上位ノードと上記一般ノードからなる各ノードペア間の通信品質を算出する第３の手順、
該第３の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択する第４の手順、
該第４の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する第５の手順、
次周期の上位ノードおよび中継ノード候補の選択時に、上記第５の手順で記憶装置に記憶した回数に応じた確率でＭ個の上位ノードと中継ノード候補およびＭ”−Ｍ個の中継ノード候補を選択する第６の手順）
を繰り返して実行する第１０の手段と
を具備し、
該第１０の手段が上記第６の手順で選択したＭ個の上位ノードを用いて上記第１〜第６の手段による各処理を実行することを特徴とする通信経路決定システム。
【請求項７】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
任意の時点での各ノード間の通信品質をフルメッシュで測定して記憶装置に記憶する第８の手段と、
記憶装置に記憶した各ノードそれぞれの通信品質を用いて、各ノードペア間の最適な通信経路を選択する第９の手段と、
最適な通信経路を構成する中継ノードとして選択された回数を各ノード毎に計数して記憶装置に記憶する第１０の手段と、
記憶装置に記憶した選択回数が多い上位Ｍ個のノードを上記上位ノードとして選択する第１１の手段と
を具備することを特徴とする通信経路決定システム。
【請求項８】
オーバーレイネットワークを構成するノード（オーバーレイノード）間の通信経路を、プログラムされたコンピュータ処理により決定する通信経路決定方法であって、
プログラムされたコンピュータ処理手順として、
請求項１から請求項４のいずれかに記載の通信経路決定システムにおける各手段により、
発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する手順と、
請求項５から請求項７のいずれかに記載の通信経路決定システムにおける各手段により、
Ｍ個の上位ノードを選択する手順と
を含むことを特徴とする通信経路決定方法。
【請求項９】
コンピュータを、請求項１から請求項７のいずれかに記載の通信経路決定システムにおける各手段として機能させるためのプログラム。
【請求項１】
オーバーレイネットワークを構成するノード（オーバーレイノード）間の通信経路を、プログラムされたコンピュータ処理により決定する通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記オーバーレイネットワークを構成する全てのＮ個のノードから予め選択されたＭ個の上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手段と、
該第１の手段が測定して記憶装置に記憶した各上位ノード間の通信品質を用いて、各上位ノード間の最適な通信品質の経路を決定して記憶装置に記憶する第２の手段と、
上記上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される各上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する第３の手段と、
上記第２の手段が記憶装置に記憶した決定情報および上記第３の手段が記憶装置に記憶した通信品質測定情報を用いて、発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する通信経路を特定する第４の手段と
を有することを特徴とする通信経路決定システム。
【請求項２】
請求項１に記載の通信経路決定システムであって、
上記通信品質としてノード間の遅延時間を用い、
上記第２の手段は、該遅延時間をノード間のメトリックとしたダイクストラ法により各上位ノード間の最短経路を探索し、該最短経路を上記最適な通信品質の経路として決定する
ことを特徴とする通信経路決定システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の通信経路決定システムであって、
上記通信品質としてノード間の利用可能帯域を用い、
上記第２の手段は、該利用可能帯域の逆数をノード間のメトリックとしたダイクストラ法により各上位ノード間の最短経路を探索し、該最短経路を上記最適な通信品質の経路として決定する
ことを特徴とする通信経路決定システム。
【請求項４】
請求項１から請求項３のいずれかに記載の通信経路決定システムであって、
上記第４の手段は、
上記第３の手段が記憶装置に記憶した通信品質測定情報を用いて、各一般ノード毎に当該一般ノードに最適な通信品質で接続された上位ノードを１つ特定して記憶装置に記憶する手段と、
該手段で特定して記憶装置に記憶した特定情報を用いて、発信元の一般ノードに最適な通信品質で接続された発信側上位ノードと着信先の一般ノードに最適な通信品質で接続された着信側上位ノードを特定する手段と、
該手段で特定した発信側上位ノードと着信側上位ノード間の最適な通信品質の経路を、上記第２の手段が記憶装置に記憶した決定情報を用いて特定する手段と
を有することを特徴とする通信経路決定システム。
【請求項５】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
Ｎ個の各ノードからランダムにＭ個のノードを中継ノード候補として選択する第８の手段と、
起動から予め定められた時間Ｔが経過するまで、一定周期毎に、第１〜第４の手順の処理
（Ｎ個の各ノード間のそれぞれの通信品質を、各ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手順、
記憶装置に記憶したＮ個の各ノード間のそれぞれの通信品質を用いて、
Ｍ個の中継ノード候補を中継した、中継ノード候補以外のＮ−Ｍ個の各ノードのペア間の通信品質を算出する第２の手順、
該第２の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択する第３の手順、
該第３の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する第４の手順、
次周期の中継ノード候補選択時に、上記第４の手順で記憶装置に記憶した回数に応じた確率でＭ個の中継ノード候補を選択する第５の手順）
を繰り返し実行する第９の手段と
を具備し、
上記時間Ｔの経過後、上記第９の手段が第４の手順により記憶装置に記憶した選択回数が多い上位Ｍ個の中継ノードを上記上位ノードとして選択することを特徴とする
通信経路決定システム。
【請求項６】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
Ｎ個の各ノードからランダムにＭ”個のノードを中継ノード候補として選択する第８の手段と、
上記Ｍ”個の中継ノード候補からＭ個の上位ノードを選択する第９の手段と、
予め定められた周期で、第１〜第５の手順の処理（
Ｍ個の各上位ノード間のそれぞれの通信品質を、各上位ノードがフルメッシュで接続されたものとして全て測定して記憶装置に記憶する第１の手順、
上位ノード以外の残りのＮ−Ｍ個の一般ノードのそれぞれと当該一般ノードに直接接続される上位ノード間のそれぞれの通信品質を測定して記憶装置に記憶する第２の手順、
記憶装置に記憶したＭ個の各上位ノード間のそれぞれの通信品質およびＮ−Ｍ個の一般ノードと上位ノード間の通信品質を用いて、Ｍ”個の各中継ノード候補を中継した、上位ノード同士からなる各ノードペア間の通信品質および上記上位ノードと上記一般ノードからなる各ノードペア間の通信品質を算出する第３の手順、
該第３の手順で算出した通信品質が、最も良く、かつ、当該ノードペア間の直通の通信品質よりも良ければ、当該中継ノード候補を中継ノードとして選択する第４の手順、
該第４の手順で中継ノードとして選択した回数を、各中継ノード毎に計数して記憶装置に記憶する第５の手順、
次周期の上位ノードおよび中継ノード候補の選択時に、上記第５の手順で記憶装置に記憶した回数に応じた確率でＭ個の上位ノードと中継ノード候補およびＭ”−Ｍ個の中継ノード候補を選択する第６の手順）
を繰り返して実行する第１０の手段と
を具備し、
該第１０の手段が上記第６の手順で選択したＭ個の上位ノードを用いて上記第１〜第６の手段による各処理を実行することを特徴とする通信経路決定システム。
【請求項７】
請求項１から請求項４のいずれかに記載の通信経路決定システムであって、
プログラムされたコンピュータ処理を実行する手段として、
上記Ｍ個の上位ノードを選択する第７の手段を有し、
該第７の手段は、
任意の時点での各ノード間の通信品質をフルメッシュで測定して記憶装置に記憶する第８の手段と、
記憶装置に記憶した各ノードそれぞれの通信品質を用いて、各ノードペア間の最適な通信経路を選択する第９の手段と、
最適な通信経路を構成する中継ノードとして選択された回数を各ノード毎に計数して記憶装置に記憶する第１０の手段と、
記憶装置に記憶した選択回数が多い上位Ｍ個のノードを上記上位ノードとして選択する第１１の手段と
を具備することを特徴とする通信経路決定システム。
【請求項８】
オーバーレイネットワークを構成するノード（オーバーレイノード）間の通信経路を、プログラムされたコンピュータ処理により決定する通信経路決定方法であって、
プログラムされたコンピュータ処理手順として、
請求項１から請求項４のいずれかに記載の通信経路決定システムにおける各手段により、
発信元の一般ノードと着信先の一般ノード間を上位ノードを経由して最適な通信品質で接続する手順と、
請求項５から請求項７のいずれかに記載の通信経路決定システムにおける各手段により、
Ｍ個の上位ノードを選択する手順と
を含むことを特徴とする通信経路決定方法。
【請求項９】
コンピュータを、請求項１から請求項７のいずれかに記載の通信経路決定システムにおける各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−４５７２５（Ｐ２０１０−４５７２５Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０９８７２（Ｐ２００８−２０９８７２）
【出願日】平成２０年８月１８日（２００８．８．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１８日（２００８．８．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]