(57)【特許請求の範囲】
【請求項１】
ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークにおける通信経路を求めるシステムであって、
予め上記オーバーレイネットワークに属する全てのノード間の通信品質データを取得して記憶装置に記憶するデータ取得手段と、
該データ取得手段で取得して記憶装置に記憶した通信品質データを用いて、予め、通信経路の算出に用いる中継ノードの候補を絞り込み特定する候補決定手段と、
上記オーバーレイネットワークに属する異なる任意の２つのノード間の通信経路を選択する際、該２つのノード間にある上記候補決定手段で特定した中継ノードのみを対象として、通信品質の高い通信経路を決定する経路計算手段とを有し、
上記データ取得手段は、
上記オーバーレイネットワークに属する総数ｎの各ノードｃｎ（ｎ＝１以上の整数）の集合Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝の内の異なる任意の二つのノードａ１，ｂ１（∈Ｃ）について、予め定められた期間Ｔに渡り時刻ｔ（＝１，２，…，Ｔ）毎にノードａ１からノードｂ１へデフォルトの経路で通信する際の通信品質Ｄ（＝｛ｑ（ｔ，ａ１，ｂ１）｜ｔ＝１，２，…，Ｔ，∀ａ１，ｂ１∈Ｃ｝）を取得して上記記憶装置に記憶し、
上記候補決定手段は、
上記オーバーレイネットワークに属する異なる任意の二つのノードａ２，ｂ２（∈Ｃ）と上記時刻ｔ＝１，２，・・・，Ｔについて、ノードａ２とノードｂ２間にある各中継ノード（ｖ）の内、通信品質「ｑ（ｔ，ａ２，ｖ）＋ｑ（ｔ，ｖ，ｂ２）」が最も良い中継ノードｖｔ,ａ２,ｂ２を上記集合Ｃの中から求め、
求めた各中継ノードｖｔ,ａ２,ｂ２（∈Ｃ）について、第１の通信品質「ｑ（ｔ，ａ２，ｂ２）」と第２の通信品質「ｑ（ｔ，ａ２，ｖｔ,ａ２,ｂ２）＋ｑ（ｔ，ｖｔ,ａ２,ｂ２，ｂ２）」とを比較して、第２の通信品質が第１の通信品質より良い中継ノードｃｉ（ｉ＝１以上ｎ未満の整数）を抽出し、
抽出した各中継ノードｃｉ毎の抽出回数ｆｉを求め、該抽出回数ｆｉが大きい順に予め定められたｋ個の中継ノードｃｉｋからなる集合Ｃ’＝｛ｃｉ１，ｃｉ２，…，ｃｉｋ｝（⊂Ｃ）を求め、
上記経路計算手段は、
上記オーバーレイネットワークに属する異なる任意の二つのノードａ３，ｂ３（∈Ｃ）について、通信要求された時刻ｔ’（＞Ｔ）において、ノードａ３とノードｂ３間にある上記集合Ｃ’に含まれる各中継ノード（ｖ’）の内、通信品質「ｑ（ｔ’，ａ３，ｖ’）＋ｑ（ｔ’，ｖ’，ｂ３）」が最も良い中継ノードｖ’ｔ’,ａ３,ｂ３を抽出し、
抽出した中継ノードｖ’ｔ’,ａ３,ｂ３（∈Ｃ’）について、第３の通信品質「ｑ（ｔ’，ａ３，ｂ３）」と第４の通信品質「ｑ（ｔ’，ａ３，ｖ’ｔ’,ａ３,ｂ３）＋ｑ（ｔ’，ｖ’ｔ’,ａ３,ｂ３，ｂ３）」とを比較して、第３の通信品質が第４の通信品質より良い場合は、通信経路をノードａ３→ノードｂ３とし、第４の通信品質が第３の通信品質より良い場合は、通信経路をノードａ３→中継ノードｖ’ｔ’,ａ３,ｂ３→ノードｂ３とする
ことを特徴とするオーバーレイネットワーク通信経路計算システム。
【請求項２】
請求項１に記載のオーバーレイネットワーク通信経路計算システムであって、
上記データ取得手段による各ノード間の通信品質データの取得と記憶装置への記憶、ならびに、上記候補決定手段による中継ノードの候補の絞り込みを、予め定められた期間Ｔ毎に繰り返して、上記候補決定手段で特定する中継ノードの候補を更新することを特徴とするオーバーレイネットワーク通信経路計算システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のオーバーレイネットワーク通信経路計算システムであって、
上記データ取得手段は、上記通信品質データとして、ノード間におけるパケット遅延時間の最小値、平均値、最大値のいずれかを取得することを特徴とするオーバーレイネットワーク通信経路計算システム。
【請求項４】
請求項１もしくは請求項２のいずれかに記載のオーバーレイネットワーク通信経路計算システムであって、
上記データ取得手段で取得する通信品質データとして、ノード間におけるパケット損失率の最小値、平均値、最大値のいずれかを取得することを特徴とするオーバーレイネットワーク通信経路計算システム。
【請求項５】
ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークにおける通信経路を、プログラムされたコンピュータによって求める方法であって、
プログラムされたコンピュータの処理手順として、
予め上記オーバーレイネットワークに属する全てのノード間の通信品質データを取得して記憶装置に記憶する第１の手順と、
該第１の手順で取得して記憶装置に記憶した通信品質データを用いて、予め、通信経路の算出に用いる中継ノードの候補を絞り込み特定する第２の手順と、
上記オーバーレイネットワークに属する異なる任意の２つのノード間の通信経路を選択する際、該２つのノード間にある上記第２の手順で特定した中継ノードのみを対象として、通信品質の高い通信経路を決定する第３の手順とを含み、
上記第１の手順は、
上記オーバーレイネットワークに属する総数ｎの各ノードｃｎ（ｎ＝１以上の整数）の集合Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝の内の異なる任意の二つのノードａ１，ｂ１（∈Ｃ）について、予め定められた期間Ｔに渡り時刻ｔ（＝１，２，…，Ｔ）毎にノードａ１からノードｂ１へデフォルトの経路で通信する際の通信品質Ｄ（＝｛ｑ（ｔ，ａ１，ｂ１）｜ｔ＝１，２，…，Ｔ，∀ａ１，ｂ１∈Ｃ｝）を取得して上記記憶装置に記憶する手順を含み、
上記第２の手順は、
上記オーバーレイネットワークに属する異なる任意の二つのノードａ２，ｂ２（∈Ｃ）と上記時刻ｔ＝１，２，・・・，Ｔについて、ノードａ２とノードｂ２間にある各中継ノード（ｖ）の内、通信品質「ｑ（ｔ，ａ２，ｖ）＋ｑ（ｔ，ｖ，ｂ２）」が最も良い中継ノードｖｔ,ａ２,ｂ２を上記集合Ｃの中から求める手順と、
求めた各中継ノードｖｔ,ａ２,ｂ２（∈Ｃ）について、第１の通信品質「ｑ（ｔ，ａ２，ｂ２）」と第２の通信品質「ｑ（ｔ，ａ２，ｖｔ,ａ２,ｂ２）＋ｑ（ｔ，ｖｔ,ａ２,ｂ２，ｂ２）」とを比較して、第２の通信品質が第１の通信品質より良い中継ノードｃｉ（ｉ＝１以上ｎ未満の整数）を抽出し、
抽出した各中継ノードｃｉ毎の抽出回数ｆｉを求め、抽出回数ｆｉが大きい順に予め定められたｋ個の中継ノードｃｉｋからなる集合Ｃ’＝｛ｃｉ１，ｃｉ２，…，ｃｉｋ｝（⊂Ｃ）を求める手順とをふくみ、
上記第３の手順は、
上記オーバーレイネットワークに属する異なる任意の二つのノードａ３，ｂ３（∈Ｃ）について、通信要求された時刻ｔ’（＞Ｔ）において、ノードａ３とノードｂ３間にある上記集合Ｃ’に含まれる各中継ノード（ｖ’）の内、通信品質「ｑ（ｔ’，ａ３，ｖ’）＋ｑ（ｔ’，ｖ’，ｂ３）」が最も良い中継ノードｖ’ｔ’,ａ３,ｂ３を抽出する手順と、
抽出した中継ノードｖ’ｔ’,ａ３,ｂ３（∈Ｃ’）について、第３の通信品質「ｑ（ｔ’，ａ３，ｂ３）」と第４の通信品質「ｑ（ｔ’，ａ３，ｖ’ｔ’,ａ３,ｂ３）＋ｑ（ｔ’，ｖ’ｔ’,ａ３,ｂ３，ｂ３）」とを比較して、第３の通信品質が第４の通信品質より良い場合は、通信経路をノードａ３→ノードｂ３とし、第４の通信品質が第３の通信品質より良い場合は、通信経路をノードａ３→中継ノードｖ’ｔ’,ａ３,ｂ３→ノードｂ３とする手順とを含む
ことを特徴とするオーバーレイネットワーク通信経路計算方法。
【請求項６】
請求項５に記載のオーバーレイネットワーク通信経路計算方法であって、
上記第１の手順での各ノード間の通信品質データの取得と記憶装置への記憶、ならびに、上記第２の手順での中継ノードの候補の絞り込みを、予め定められた期間Ｔ毎に繰り返して、上記第２の手順で特定する中継ノードの候補を更新することを特徴とするオーバーレイネットワーク通信経路計算方法。
【請求項７】
請求項５もしくは請求項６のいずれかに記載のオーバーレイネットワーク通信経路計算方法であって、
上記第１の手順では、上記通信品質データとして、ノード間におけるパケット遅延時間の最小値、平均値、最大値のいずれかを取得することを特徴とするオーバーレイネットワーク通信経路計算方法。
【請求項８】
請求項５もしくは請求項６のいずれかに記載のオーバーレイネットワーク通信経路計算方法であって、
上記第１の手順で取得する通信品質データとして、ノード間におけるパケット損失率の最小値、平均値、最大値のいずれかを取得することを特徴とするオーバーレイネットワーク通信経路計算方法。
【請求項９】
コンピュータに、請求項５から請求項８のいずれかに記載のオーバーレイネットワーク通信経路計算方法における第１の手順と第２の手順および第３の手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等のＩＰネットワークにおけるエンド・ツー・エンドの通信品質を向上させる技術に係り、特に、ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させるのに好適な技術に関するものである。
【背景技術】
【０００２】
ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Voice over IP）やストリーミングに代表されるＱｏＳ（Quality of Service）に敏感な実時間アプリケーション等の収容も急速に進展している。
【０００３】
これに伴い、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドＱｏＳ管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００４】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００５】
（２）インターネットは管理主体の異なる複数のＡＳ（Autonomous System）によって形成されており、全てのＡＳに対して一斉に新たな機能を拡張することは困難である。
【０００６】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術として、例えば非特許文献１に記載の、オーバーレイネットワークによるＱｏｓ管理技術が注目されている。
【０００７】
オーバーレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層における目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００８】
このようなオーバーレイネットワークによるＱｏＳ管理の基本的な概念を図６に例示する。
【０００９】
図６において、ｘからｙに向けて、破線矢印で表される経路にトラヒックが流れているとする。また、この経路上には輻輳しているＩＰルータ７２が存在しており、その結果としてｘ，ｙ間のＱｏＳが低下しているとする。
【００１０】
このとき、オーバーレイノード６１，６２，６３で形成されるオーバーレイネットワークを用いて、実線矢印で表される経路（ｘ→ＩＰルータ７１→オーバーレイノード６１→ＩＰルータ７１→ＩＰルータ７４→ＩＰルータ７５→オーバーレイノード６２→ＩＰルータ７５→ＩＰルータ７３→オーバーレイノード６３→ＩＰルータ７３→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【００１１】
実際、非特許文献３，４，５では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。
【００１２】
しかし、これらの結果はオーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティ（システムの拡張性）の低下については考慮されていない。
【００１３】
すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間において品質情報の測定を行った上で通信経路の計算を行うことは現実的には不可能であるという問題がある。
【００１４】
【非特許文献１】L.Zhi and P.Mohapatra,“QRON：QoS-aware routing in overlay net-works,” IEEE J.Select.Areas Commun., vol.22, pp.29-40, January 2004.
【非特許文献２】ＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェクト研究報告書，第１７部，２００２．
【非特許文献３】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献４】S.Rewaskar and J.Kaur, “Testing the Scalability of Overlay Routing Infrastructures,” Proc.PAM 2004, April 2004．
【非特許文献５】S.Banerjee, T.G.Grifin and M.Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
解決しようとする問題点は、従来の技術では、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合、現実的には通信経路の計算を行うことができない点である。
【００１６】
本発明の目的は、これら従来技術の課題を解決し、オーバーレイネットワークにおける通信経路を計算する際のスケーラビリティの向上を可能とすることである。
【課題を解決するための手段】
【００１７】
上記目的を達成するため、本発明では、ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いて通信経路を計算する際に、中継オーバーレイノードの候補を計測データに基づき予め決定しておくことを特徴とする。すなわち、予め、オーバーレイネットワークに属する全てのノード間の通信品質データを取得し、取得した通信品質データを用いて、異なる任意の２つのノード間の全ての経路の通信品質を算出し、迂回しない場合よりも通信品質が高くなる迂回経路において使用される中継ノードの中から、一定数の中継ノードを、通信品質が高い順に特定しておく。そして、例えば輻輳を回避するのに好適な通信経路を選択する際には、特定した一定数の中継ノードのみを用いて、通信経路を決定する。
【発明の効果】
【００１８】
本発明によれば、オーバーレイネットワークにおける通信経路を計算する際のスケーラビリティの向上を図ることが可能であると共に、通信品質の改善を図ることが可能である。
【発明を実施するための最良の形態】
【００１９】
以下、図を用いて本発明を実施するための最良の形態例を説明する。
【００２０】
図１は、本発明に係る通信経路計算システムを設けたオーバーレイネットワークの構成例を示すブロック図であり、図２は、本発明に係る通信経路計算システムの機能構成例を示すブロック図、図３は、本発明に係る通信経路計算システムのハードウェア構成例を示すブロック図、図４は、図２における各機能による本発明に係る通信経路計算方法に関する手順例を示すフローチャート、図５は、本発明に係る通信経路計算システムおよび方法の効果を示す説明図である。
【００２１】
図１に示すオーバーレイネットワークの構成は、図６で説明した従来のオーバーレイネットワークの構成と同様であり、ＩＰルータ１１〜１５からなるＩＰネットワーク（図中「ＩＰ−ＮＷ」と記載）１６に接続されたノード１〜３によりオーバーレイネットワーク４（図中「Ｏｖｅｒｌａｙ−ＮＷ」と記載）４を構成している。
【００２２】
図１においても、ｘからｙに向けて、破線矢印で表される経路にトラヒックが流れているとし、この経路上のＩＰルータ１２が輻輳し、その結果としてｘ，ｙ間のＱｏＳが低下しているとすると、オーバーレイノード１，２，３で形成されるオーバーレイネットワーク４を用いて、実線矢印で表される経路（ｘ→ＩＰルータ１１→オーバーレイノード１→ＩＰルータ１１→ＩＰルータ１４→ＩＰルータ１５→オーバーレイノード２→ＩＰルータ１５→ＩＰルータ１３→オーバーレイノード３→ＩＰルータ１３→ｙ）にトラヒックを迂回させることで、上記の輻輳を回避できる。
【００２３】
このようにオーバーレイネットワーク４経由で迂回経路を形成する際、本例では、予め、経由するノード、すなわち中継オーバーレイノードの候補を、各ノード間の通信品質を予め計測して収集しそのデータに基づき制限した上で、通信経路の計算を行う。
【００２４】
そのために、本例では、オーバーレイネットワークに属する全てのノード間の通信品質データを予め取得・収集する機能と、例えば、取得・収集した通信品質データを用いて通信品質が高い順に予め定められた数だけノードを絞り込むことでノード中継に用いるノード候補を制限する機能、および、絞り込んだ中継用ノードを経由する迂回経路と、デフォルトの経路（迂回しない経路）のそれぞれの通信品質を比較し、通信品質が優れている方の経路を採用する機能とを具備したコンピュータ装置を用いる。
【００２５】
尚、このコンピュータ装置の各機能は、オーバーレイネットワークに属する全てのノード（オーバーレイノード）に配備されていても良いし、あるいは、オーバーレイノードではない別のノード（例えば、外部サーバ）等に配備されていても良い。
【００２６】
コンピュータ装置のハードウェア構成は図３に示すものであり、図３において、３１はＣＲＴ（Cathode Ray Tube）やＬＣＤ(Liquid Crystal Display)等からなる表示装置、３２はキーボードやマウス等からなる入力装置、３３はＨＤＤ（Hard Disk Drive）等からなる外部記憶装置、３４はＣＰＵ（Central Processing Unit）３４ａや主メモリ３４ｂおよび入出力インタフェース３４ｃ等を具備してコンピュータ処理を行なう情報処理装置、３５は本発明に係わるプログラムやデータを記録したＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）もしくはＤＶＤ（Digital Video Disc/Digital Versatile Disc）等からなる光ディスク、３６は光ディスク３５に記録されたプログラムおよびデータを読み出すための駆動装置、３７はＬＡＮ（Local Area Network）カードやモデム等からなる通信装置である。
【００２７】
光ディスク３５に格納されたプログラムおよびデータを情報処理装置３４により駆動装置３６を介して外部記憶装置３３内にインストールした後、外部記憶装置３３から主メモリ３４ｂに読み込みＣＰＵ３４ａで処理することにより、情報処理装置３４内に図２に示す各機能からなる通信経路計算システムが構成される。
【００２８】
図２に示すように、本例の通信経路計算システムは、通信品質データ取得部（図中「中継オーバーレイノード候補決定用通信品質データ取得部」と記載）２１と、候補決定部（図中「中継オーバーレイノード候補決定部」と記載）２２、および、通信経路計算部２３を有している。
【００２９】
通信品質データ取得部２１は、オーバーレイネットワークに属する全てのノード間の通信品質データを取得して記憶装置に記憶し、候補決定部２２は、通信品質データ取得部２１で取得して記憶装置に記憶した通信品質データを用いて、各ノード間の全ての迂回経路および迂回しない経路の通信品質を算出し、迂回しない場合よりも通信品質が高くなる迂回経路を形成する中継ノードの中から、予め定められた数の中継ノードを通信品質の高い順に特定する。
【００３０】
そして、通信経路計算部２３は、オーバーレイネットワークに属する異なる任意の２つのノード間の通信経路を選択する際、当該ノード間にある候補決定部２２で特定した中継ノードを迂回した場合の通信品質を算出し、最も通信品質の高い中継ノードを特定すると共に、迂回しない場合の通信品質を算出し、この迂回しない場合の通信品質と特定した中継ノードを迂回した場合の通信品質とを比較し、通信品質の高い方を通信経路として決定する。
【００３１】
以下、このようなオーバーレイネットワークにおける通信経路計算システムに関してより詳細に説明する。尚、以下では、オーバーレイネットワークに属するノードの総数をｎとし、このオーバーレイノードの集合をＣ＝｛ｃ１，ｃ２，…，ｃｎ｝とする。
【００３２】
さらに、当該オーバーレイネットワークに属する異なる任意の二つのノードａ，ｂ（∈Ｃ）について、時刻ｔにおいてａからｂへデフォルトの経路で通信する際の通信品質をｑ（ｔ，ａ，ｂ）とし、その経路をａ→ｂとする。また、ここでの通信品質は、パケット遅延時間もしくはパケット損失率とする。
【００３３】
通信品質データ取得部２１は、予め定められた取得期間（Ｔ）において、中継オーバーレイノード候補決定用に、各ノード間の通信品質デークＤ＝｛ｑ（ｔ，ａ，ｂ）｜ｔ＝１，２，…，Ｔ，∀ａ，ｂ∈Ｃ｝を予め取得して記憶装置に記憶する。ただし、ｔ＝１，２，…，Ｔである。
【００３４】
候補決定部２２は、通信品質データ取得部２１が取得して記憶装置に記憶した中継オーバーレイノード候補決定用の各ノード間の通信品質データＤを用いて、中継オーバーレイノード候補を、次の手順で予め決定する。
【００３５】
手順１：オーバーレイネットワークに属する異なる任意の二つのノードａ，ｂ（∈Ｃ）とｔ＝１，２，・・・，Ｔについて、ノードａとノードｂ間にある各ノード（ｖ）の内、「ｑ（ｔ，ａ，ｖ）＋ｑ（ｔ，ｖ，ｂ）」が最小、すなわち最高品質となるノードｖをＣの中から求め、それをｖt,a,b（∈Ｃ）とする。
【００３６】
手順２：求めたｖt,a,bについて、「ｑ（ｔ，ａ，ｖ）」と「ｑ（ｔ，ａ，ｖt,a,b）＋ｑ（ｔ，ｖt,a,b，ｂ）」を比較して、前者が小さい場合（前者の品質が後者の品質より良い場合）はｖt,a,bの値（ｃ１，ｃ２，…，ｃｎ）をｃ０に変更し、後者が小さい場合はｖt,a,bの値（ｃ１，ｃ２，…，ｃｎ）を変更しない。
【００３７】
尚、当該ノードｖt,a,bの値をｃ０に変更することで、ノードａとノードｂ間を直接（ノードｖを中継して迂回することなく）接続することが最良であることを表す。
【００３８】
手順３：各ｖt,a,b（ｔ＝１，２，…，Ｔ，∀ａ，ｂ∈Ｃ）について、その値がｃｉ（ｉ＝０，１，２，…，ｎ）であるものの個数を求め、すなわち、各ノードｃｉが、Ｔ時間中に、最小（最高品質）として求められた回数を求め、それをｆｉとする。
【００３９】
手順４：予め定められた値ｋについて、ｆｉの値が大きいものの上位ｋ個を求め（ただし、ｆ０を除く）、そのときのｉをｉ１，ｉ２，…，ｉｋとする。
【００４０】
手順５：中継ノードの候補の集合をＣ’＝｛ｃｉ１，ｃｉ２，…，ｃｉｋ｝（⊂Ｃ）とする。
【００４１】
通信経路計算部２３は、このようにして、候補決定部２２が決定した中継オーバーレイノード候補のみを用いて、オーバーレイネットワークに属する異なる任意の二つのノードａ’，ｂ’（∈Ｃ）について、時刻ｔ’（＞Ｔ）におけるノードａ’からノードｂ’へ至る経路を次の手順で計算する
【００４２】
手順６：オーバーレイネットワークに属する異なる任意の二つのノードａ’，ｂ’（∈Ｃ）とｔ’＞Ｔについて、各時間ｔ’毎の各中継ノード間の通信品質（「ｑ（ｔ’，ａ’，ｖ’）＋ｑ（ｔ’，ｖ’，ｂ’）」）が最小となるノードｖ’を集合Ｃ’の中から求め、求めたノードを「ｖ't',a',b'（∈Ｃ’）」とする。
【００４３】
手順７：当該ノードａ’，ｂ’（∈Ｃ）とｔ’＞Ｔについて、迂回しない場合の通信品質「ｑ（ｔ’，ａ’，ｂ’）」と、求めた中継ノードｖ’を迂回した場合の通信品質「ｑ（ｔ’，ａ’，ｖ't',a',b'）＋ｑ（ｔ’，ｖ't',a',b'，ｂ’）」とを比較し、前者が小さい場合は通信経路を「ａ’→ｂ’」とし、後者が小さい場合は通信経路を「ａ’→ｖ't',a',b'→ｂ’」とする。
【００４４】
以上のようにして、オーバーレイネットワークにおける通信経路の計算を行う。尚、通信品質としてパケット遅延時間を用いた場合、通信品質ｑ（ｔ，ａ，ｂ）を、ノードａ，ｂ間の時刻ｔにおける遅延時間ｄ（ｔ，ａ，ｂ）を用いて「ｑ（ｔ，ａ，ｂ）＝ｄ（ｔ，ａ，ｂ）」とする。ただし、遅延時間として、最小、平均、最大などの適当な統計処理を施した遅延時間を用いる。
【００４５】
また、通信品質としてパケット損失率を用いた場合、通信品質ｑ（ｔ，ａ，ｂ）を、ノードａ，ｂ間の時刻ｔにおけるパケット損失率ｐ（ｔ，ａ，ｂ）を用いて「ｑ（ｔ，ａ，ｂ）＝−ｌｏｇ（１−ｐ（ｔ，ａ，ｂ））」とする。ただし、パケット損失率として、最小、平均、最大などの適当な統計処理を施したパケット損失率を用いる。
【００４６】
また、本例では、通信品質データ取得部２１による各ノード間の通信品質データの取得と記憶装置への記憶、ならびに、候補決定部２２による中継ノードの候補の絞り込みを、予め定められた期間Ｔ毎に繰り返して、候補決定部２２で特定する中継ノードの候補を更新し、通信経路計算部２３は、期間Ｔ毎に更新された中継ノード候補を用いて、通信経路の算出を行う。
【００４７】
以下、図４を用いて、このようなオーバーレイネットワーク通信経路計算システムの動作説明を行う。まず、オーバーレイネットワークにおける通信経路を計算する際に必要となる、中継オーバーレイノード候補の決定に関わる動作について説明する。
【００４８】
通信品質データ取得部２１は、予め定められた期間Ｔの間、中継オーバーレイノードの候補を決定する際に必要となる通信品質データを取得して記憶装置に格納する（ステップＳ１００）。取得した通信品質データの集合をＤ＝｛ｑ（ｔ，ａ，ｂ）｜ｔ＝１，２，…，Ｔ，∀ａ，ｂ∈Ｃ｝とする。
【００４９】
候補決定部２２は、通信品質データ取得部１において取得された通信品質データを記憶装置から読み出し、それを用いて、上述した手順１〜手順５の処理により、予め定められた数（ｋ）のノードを高品質な順で求め、中継オーバーレイノード候補として決定する（ステップＳ２００）。決定した中継オーバーレイノードの候補をＣ’＝｛ｃｉ１，ｃｉ２，…，ｃｉｋ｝（⊂Ｃ）とする。
【００５０】
次に、時刻ｔ’（＞Ｔ）において、ノードａ’からノードｂ’への通信要求が発生した場合（ステップＳ３００）における通信経路計算部２３の動作について説明する。
【００５１】
この場合、通信経路計算部２３は、候補決定部２２において決定された中継オーバーレイノード候補のみを対象にして、上記手順６〜手順７の処理により、経路の計算を行う（ステップＳ４００）。
【００５２】
そして、このようにして求めた通信経路を介してノードａ’とノードｂ’間の通信を実行する（ステップＳ５００）。
【００５３】
図５においては、実際のインターネット上において測定したデータを用いて、上記の手順を実行した場合の評価結果を示している。この図５において、評価に利用したデータは、国内で適当に地理的に離れた１８箇所のＩＳＰ（インターネット・サービス・プロバイダ）に利用者として契約したコンピュータ端末において、各対地での遅延測定（ｐｉｎｇによる）を、１時間毎に毎秒１パケットで３分間（合計１８０パケット）実施したものである。
【００５４】
また、分析対象としたのは、二日分のデータの内、対地毎のｔ時間目における端末ｘ，ｙ間の３分間の測定の中での最大パケット遅延時間である。尚、中継オーバーレイノードの候補は、一日目のデータを利用して決定した。また、中継オーバーレイノードの候補数ｋは４とした。
【００５５】
図５においては、上記の手順で通信経路計算した場合の最大遅延時間の累積分布（図５における実線）と、中継オーバーレイノードの制限をせずに通信経路計算した場合の最大遅延時間の累積分布（図５における破線）、および、デフォルトの通信経路を利用した場合の最大遅延時間の累積分布（図５における一点破線）を示している。
【００５６】
本図５から、本例のシステムおよび方法により、中継オーバーレイノードの制限を行う場合と、制限を行わない場合と同程度の通信品質の改善が見込めることが分かる。
【００５７】
以上、図１〜図５を用いて説明したように、本例のオーバーレイネットワーク通信経路計算システムおよび方法では、ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いて通信経路を計算する際に、中継オーバーレイノードの候補を計測データに基づき予め決定しておく。すなわち、予め、通信品質データ取得部（２１）が、オーバーレイネットワークに属する全てのノード間の通信品質データを取得して記憶装置に記憶し、候補決定部（２２）が、記憶装置から各通信品質データを読み出して、異なる任意の２つのノード間の全ての経路の通信品質を算出し、迂回しない場合よりも通信品質が高くなる迂回経路において使用される中継ノードの中から、一定数の中継ノードを、通信品質が高い順に特定しておく。そして、例えば輻輳を回避するのに好適な通信経路を選択する際には、通信経路計算部（２３）が、候補決定部（２２）が予め特定した一定数の中継ノードのみを用いて、通信経路を決定する。
【００５８】
より詳細には、通信品質データ取得部（２１）は、オーバーレイネットワークに属する総数ｎの各ノードｃｎ（ｎ＝１以上の整数）の集合Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝の内の異なる任意の二つのノードａ１，ｂ１（∈Ｃ）について、予め定められた期間Ｔに渡り時刻ｔ（＝１，２，…，Ｔ）毎にノードａ１からノードｂ１へデフォルトの経路で通信する際の通信品質Ｄ（＝｛ｑ（ｔ，ａ１，ｂ１）｜ｔ＝１，２，…，Ｔ，∀ａ１，ｂ１∈Ｃ｝）を取得して、全ノードｃｎの通信品質データとして記憶装置に記憶する。
【００５９】
候補決定部（２２）は、オーバーレイネットワークに属する異なる任意の二つのノードａ２，ｂ２（∈Ｃ）と時刻ｔ＝１，２，・・・，Ｔについて、ノードａ２とノードｂ２間にある各中継ノード（ｖ）の内、通信品質「ｑ（ｔ，ａ２，ｖ）＋ｑ（ｔ，ｖ，ｂ２）」が最も良い中継ノードｖt,ａ２,ｂ２を集合Ｃの中から求め、求めた中継ノードｖt,ａ２,ｂ２（∈Ｃ）について、第１の通信品質「ｑ（ｔ，ａ２，ｂ２）」と第２の通信品質「ｑ（ｔ，ａ２，ｖt,ａ２,ｂ２）＋ｑ（ｔ，ｖt,ａ２,ｂ２，ｂ２）」とを比較して、第２の通信品質が第１の通信品質より良い中継ノードｃｉ（ｉ＝１以上ｎ未満の整数）を抽出し、抽出した各中継ノードｃｉ毎の抽出回数ｆｉを求め、求めた抽出回数ｆｉが大きい順に予め定められたｋ個の中継ノードｃｉｋからなる集合Ｃ’＝｛ｃｉ１，ｃｉ２，…，ｃｉｋ｝（⊂Ｃ）を求める。
【００６０】
そして、通信経路計算部（２３）は、オーバーレイネットワークに属する異なる任意の二つのノードａ３，ｂ３（∈Ｃ）について、時刻ｔ’（＞Ｔ）において、ノードａ３とノードｂ３間にある集合Ｃ’に含まれる各中継ノード（ｖ’）の内、通信品質「ｑ（ｔ’，ａ３，ｖ’）＋ｑ（ｔ’，ｖ’，ｂ３）」が最も良い中継ノードｖ't',ａ３,ｂ３を抽出し、抽出した中継ノードｖ't',ａ３,ｂ３（∈Ｃ’）について、第３の通信品質「ｑ（ｔ’，ａ３，ｂ３）」と第４の通信品質「ｑ（ｔ’，ａ３，ｖ't',ａ３,ｂ３）＋ｑ（ｔ’，ｖ't',ａ３,ｂ３，ｂ３）」とを比較して、第３の通信品質が第４の通信品質より良い場合は、通信経路をノードａ３→ノードｂ３とし、第４の通信品質が第３の通信品質より良い場合は、通信経路をノードａ３→中継ノードｖ't',ａ３,ｂ３→ノードｂ３とする。
【００６１】
このように、本例では、従来の技術のように、オーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行うのではなく、予め、通信経路の計算の対象となる中継ノードを絞り込んでおき、実際の経路計算を行う際には、絞り込まれた中継ノード候補のみを対象とするので、オーバーレイノードの総数が増加した場合であっても、実用的な時間内に通信経路の計算を行うことができる。これにより、オーバーレイネットワークにおける通信経路を計算する際のスケーラビリティの向上を可能とすることができ、かつ、通信品質の改善が可能である。
【００６２】
尚、本発明は、図１〜図５を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、通信品質として、パケットの遅延時間、もしくは、パケット損失率を用いることを例示したが、例えば、スループットを通信品質として用いることでも良い。この場合、計測データが大きいほど通信品質が良いものとなる。
【００６３】
また、本発明は、図１に示したネットワーク構成に限定されるものではなく、図５の説明で掲げたインターネット等、より多くのＩＰルータからなる大規模なＩＰネットワーク、および、より多くのノードからなる大規模なオーバーレイネットワーク構成においても適用できる。
【００６４】
また、コンピュータ装置の構成に関しても図３の例に制限されるものではなく、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Flexible Disk）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【００６５】
【図１】本発明に係る通信経路計算システムを設けたオーバーレイネットワークの構成例を示すブロック図である。
【図２】本発明に係る通信経路計算システムの機能構成例を示すブロック図である。
【図３】本発明に係る通信経路計算システムのハードウェア構成例を示すブロック図である。
【図４】図２における各機能による本発明に係る通信経路計算方法に関する手順例を示すフローチャートである。
【図５】本発明に係る通信経路計算システムおよび方法の効果を示す説明図である。
【図６】従来のオーバーレイネットワークの構成例を示すブロック図である。
【符号の説明】
【００６６】
１〜３：オーバーレイノード、４：オーバーレイネットワーク（「Ｏｖｅｒｌａｙ−ＮＷ」）、１１〜１５：ＩＰルータ、１６：ＩＰネットワーク（「ＩＰ−ＮＷ」）、２１：通信品質データ取得部、２２：候補決定部、２３：通信経路計算部、３１：表示装置、３２：入力装置、３３：外部記憶装置、３４：情報処理装置、３４ａ：ＣＰＵ、３４ｂ：主メモリ、３４ｃ：入出力インタフェース、３５：光ディスク、３６：駆動装置、３７：通信装置、６１〜６３：オーバーレイノード、６４：オーバーレイネットワーク（「Ｏｖｅｒｌａｙ−ＮＷ」）、７１〜７５：ＩＰルータ、７６：ＩＰネットワーク（「ＩＰ−ＮＷ」）。
【図１】
0004437976.tif 000002
【図２】
0004437976.tif 000003
【図３】
0004437976.tif 000004
【図４】
0004437976.tif 000005
【図５】
0004437976.tif 000006
【図６】
0004437976.tif 000007