JP4548792B2 - オーバーレイネットワークの通信経路制御方法および通信経路制御システムとプログラム - Google Patents

Description

本発明は、インターネットにおけるエンド・ツー・エンドの通信品質を向上させる技術に係り、特にＩＰネットワーク上に論理的に形成されたオーバーレイネットワークを用いた通信経路で、エンド・ツー・エンドの通信品質を効率的に向上させるのに好適な技術に関するものである。

ＩＰネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、ＶｏＩＰ（Voice overＩＰ）やストリーミングに代表されるＱｏＳ（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. WIDEプロジェクト，"オーバーレイネットワークによる統合分散環境，"WIDEプロジヱクト研究報告書，第１７部，２００２． 亀井，川原，"エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，"信学ソ大，ＢＳ−５−３，２００４． 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.

一方、本発明者らは（「特願２００５−１９７０６０号」において）、中継ノード候補を計測データに基づいて適切に制限することにより、全ノードを中継候補として経路探索を行った最適な場合とほぼ同等のＱｏＳ向上を図れることを示している。

この技術では、全てのノードペアに対する経路について、全ノードを中継ノード候補とした場合の最適な経路を計算しておき、各ノードが最適な経路を提供する中継ノードとして選択される「頻度」を計算しておき、その「頻度」の高い上位Ｍ個のノードを抽出しておき、以上の準備の下、以降の経路計算時には、このＭ個の中継候補ノードのみを用いていた。

この技術では、一旦、全経路探索を行う必要があったのに対し、さらに、本発明者らは（「川原、亀井、内田、阿部、“迂回経路候補数に制限がある場合のＱｏＳオーバーレイ経路選択アルゴリズムとその評価、”信学技報 ＩＮ２００５−１９５，ｐｐ．２３１−２３６，（２００６年３月）」において）、常に中継ノード候補数を一定数以下に抑えておき、実際の中継ノードの選択行為を通じて高品質な経路を提供可能な中継ノードを学習し、そのようなノードを高確率で選択することにより、最適な場合とほぼ同等のＱｏＳ向上を図る技術を提案している。

しかしながら、この技術では、各中継ノードが最適な経路を提供できる頻度が一定で変化のない場合を仮定しており、ネットワーク条件が変化して、最適な中継ノードである頻度の順位が変わるような場合には対応できないという問題点があった。

例えば、あるノードは、これまでは、自ノードの設置されるネットワークが回線帯域が不十分なため品質が良くなく、最適なノードである頻度が非常に小さかったが、ある時点で当該ネットワークが設備増設をして品質が向上した場合を想定する。

このような場合、上述した２つの技術では、これまでのネットワーク状況から高品質な上位Ｍ個のノードを決めて、そこから中継ノードを選択するため、新規に高品質になったノードを適切に選択できない、という問題が生じる。

また、逆に、それまで上位Ｍ個の中継ノード候補にランクされていたノードの周囲のネットワーク条件が変化して品質が劣化したときにも、当該ノードを中継候補として選択してしまうという問題が生じる。

従来技術の問題点は、オーバーレイネットワークにおけるネットワーク条件の変化に適切に追従して、そのときのネットワーク条件に応じた高品質な経路を提供可能な中継ノードを適切に選択することができない点である。

本発明の目的は、これら従来技術の課題を解決し、オーバーレイネットワークにおけるエンド・ツー・エンドの通信品質を効率的に向上させることである。

上記目的を達成するため、本発明は、オーバーレイネットワークにおける通信経路制御を行う際、ネットワーク条件の変化に適切に追従して、そのときのネットワーク条件に応じた高品質な経路を提供可能な中継ノードを適切に選択できるように各ノードの選択確率を補正できる仕組みを持たせることを特徴とする。すなわち、ＩＰネットワークに接続するＮ個のオーバーレイノードによって構成される論理網であるオーバーレイネットワークにおいて、発信元ノードから着信先ノードヘの通信経路を決定する際、オーバーレイネットワークに属する各ノードｉ（ｉ＝１〜Ｎ）は、自ノードを発信元ノードとし他ノードｊ（ｉを除く全て）を着信先ノードｊとして、発信元ノードｉと着信先ノードｊの間の通信品質を測定しておき、その一方でＮ個のノードの中からＭ個のノードを中継ノードの候補として選択し、中継候補ノードｋから着信先ノードｊの間の通信品質測定結果を中継候補ノードから取得し、自ノードｉと着信先ノードｊの間の通信品質と、自ノードｉから中継候補ノードｋを経由して着信先ノードｊに到達するときの通信品質を比較し、前者の方が良い品質を与える場合には中継ノードは用いずに着信先ノードｊへ直接転送する経路を自ノードｉから着信先ノードｊへの通信経路として決定し、また、後者が良い品質を与える場合には、その中でも最も高品質を提供するノードｋ＊を中継ノードとし、通信経路を自ノードｉ→中継ノードｋ＊→着信先ノードｊと決定すると共に、次回の中継ノード候補選択時には、過去に中継ノードとして選択された頻度に応じて中継ノード候補をＭ’個選択し、残りのＭ−Ｍ’個は、当該頻度には依存せずに等確率で中継ノード候補を選択し、さらに、ネットワーク条件の変動を監視し、その変動が検知された際には各ノードの選択確率をその状況に応じて変化させることを特徴とする。

本発明によれば、ネットワーク条件の変動に追従して、オーバーレイネットワークにおける通信経路計算に伴うコストを削減しつつ、通信品質の改善を図ることが可能となる。

以下、図を用いて本発明を実施するための最良の形態例を説明する。図２は、本発明に係る通信経路制御システムを具備したオーバーレイネットワークの構成例を示すブロック図であって、当該オーバーレイネットワークには、図示したオーバーレイノード２１〜２５（以下、単に、「ノード２１〜２５」という）を含む複数のノードと管理サーバ２０が設けられている。

ノード２１〜２５等の各ノードおよび管理サーバ２０は、ＣＰＵ（Central Processing Unit）や主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、本発明に係る各処理部の機能を実行する。

ノード２１〜２５等の各ノードは、それぞれ、他のノードと論理的に接続している。つまり、オーバーレイネットワークに存在する他のノードのＩＰアドレスを知っており、通信可能な状態にある。

また、管理サーバ２０は、ノード２１〜２５を含む各ノードのいずれかを、中継ノード候補として管理する機能を有する。

このような構成において、本例では、オーバーレイネットワークにおける通信経路制御を行う際、ネットワーク条件の変化に適切に追従して、そのときのネットワーク条件に応じた高品質な経路を提供可能な中継ノードを適切に選択できるようにノード２１〜２５を含む各ノードの選択確率を補正できる仕組み（第１〜第５の技術）を持たせる。

第１の技術は、オーバーレイネットワークを構成するノード間の通信品質の測定および中継ノードを用いて迂回するか否の決定を行うものであり、この第１の技術として本例では、当該オーバーレイネットワークに属するあるノードから着信先ノードヘの通信経路を決定する際、各ノードｉ（ｉ＝１〜Ｎ）は、自ノードを発信元ノードとし、他ノードｊ（ｉを除く全て）を着信先ノードｊとして、発信元ノードｉと着信先ノードｊの間の通信品質を測定しておき、その一方でＮ個のノードの中からＭ個のノードを中継ノードの候補として選択し、中継候補ノードｋから着信先ノードｊの間の通信品質測定結果を中継候補ノードから取得し、自ノードｉと着信先ノードｊの間の通信品質と、自ノードｉから中継候補ノードｋを経由して着信先ノードｊに到達するときの通信品質を比較し、前者の方が良い品質を与える場合には中継ノードは用いずに着信先ノードｊへ直接転送する経路を自ノードｉから着信先ノードｊへの通信経路として決定し、また、後者が良い品質を与える場合には、その中でも最も高品質を提供するノードｋ＊を中継ノードとし、通信経路を自ノードｉ→中継ノードｋ＊→着信先ノードｊと決定すると共に、次回の中継ノード候補選択時には、過去に中継ノードとして選択された頻度に応じて中継ノード候補をＭ’個選択し、残りのＭ−Ｍ’個は、当該頻度には依存せずに等確率で中継ノード候補を選択し、さらに、ネットワーク条件の変動を監視し、その変動が検知された際には各ノードの選択確率をその状況に応じて変化させる。

尚、過去に中継ノードとして選択された頻度に応じて中継ノード候補を選択する技術部分は、前述の「川原、亀井、内田、阿部、“迂回経路候補数に制限がある場合のＱｏＳオーバーレイ経路選択アルゴリズムとその評価、”信学技報 ＩＮ２００５−１９５，ｐｐ．２３１−２３６，（２００６年３月）」に記載の技術である。

本例では、それに加え、頻度には依存しないで等確率で選択する機能を追加している。こうすることにより、過去の状況に依存しないでノードを選択し、例えば、過去には低品質だったが、現在は新規に高品質となったノードも、ある一定の確率で選択でき、一旦選択されれば、選択確率が徐々に大きくなり、そのときのネットワークの状況に応じた選択が可能になる。

次に、第２の技術を説明する。この第２の技術は、中継候補ノードの選択を行うものであり、本例においては、管理サーバ２０が存在しており、この管理サーバ２０を用いた中継候補サーバの選択技術について説明する。

この管理サーバ２０は、オーバーレイネットワーク内における中継ノード候補の情報を管理する。管理サーバ２０は、図示しているノード２１〜２５を含む各ノードのｎ番目の測定周期（時点ｎ）での得点Ｃ（ｎ，ｋ）を管理している。

時点ｎにおいて、発信元ノードｉは、着信先ノードｊへの経路を決定する際、管理サーバ２０から各ノードｋ（ｋ＝１〜Ｎ）の得点Ｃ（ｎ，ｋ）を読み出し、確率ｐ_ｋ＝Ｃ（ｎ，ｋ）／Σ_ｋＣ（ｎ，ｋ）でノードｋ（ｋはｉ以外）を中継候補ノードとして選択し、これをＭ−Ｍ’個の中継候補ノードが決定するまで繰り返す。

また、残りのノード群の中から、中継候補ノードを等確率で選択し、これをＭ’個選択するまで繰り返す。そして、発信元ノードｉは着信先ノードｊへの経路を、上述のようにして決定する。

その際、ノードｋ＊が中継ノードとして決定されたら、当該ノードｋ＊は管理サーバ２０に、その旨を通知する。同様の手順は全ての発信元ノードと着信先ノードのペアについて実施される。

そして、管理サーバ２０は、各ノードから自身が中継ノードとして決定された旨を受信し、各ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントする。その値を用いて、次の時点ｎ＋１における各ノードｋの得点をＣ（ｎ＋１，ｋ）＝ｍａｘ｛Ｃ_ｌｏｗ，（１−１／ｔ’）Ｃ（ｎ，ｋ）＋１／ｔ’Ｃ’（ｎ，ｋ）｝により更新する。

なお、ここで、Ｃ_ｌｏｗは予め定める得点の下限値、１／ｔ’は平滑化パラメータであり、予め定めるパラメータβ（＞０）とｃ（＞１）を用いてｔ’＝ｍｉｎ｛ｎ＋β，ｃ｝で与えられ、Ｃ（ｎ，ｋ）の初期値はＣ（０，ｋ）＝１（全てのｋ）とする。

ここで、ノードの得点Ｃ（ｎ，ｋ）は、ノードｋが高品質な経路を提供すると増加していき、そうでないと減少するように更新している。従って、この得点に比例して中継ノード候補を選択することにより、高品質な経路を提供した中継ノードが次回の中継ノード候補選択時に選ばれやすくなるようにしている。

また、得点に下限値Ｃ_ｌｏｗを設けることにより、過度に得点が小さくならないようにすることにより、現在得点が下位のノードが、将来、ネットワーク条件が変化して上位ノードになったときに、得点が回復できるようにしている。

次に、第３の技術について説明する。この第３の技術は、上述の第１の技術と同様に、各ノード間の通信品質の測定および中継ノードを用いて迂回するか否かの決定を行うものであり、本例では、自ノードｉと着信先ノードｊの間の通信品質として、前述の「川原、亀井、内田、阿部、“迂回経路候補数に制限がある場合のＱｏＳオーバーレイ経路選択アルゴリズムとその評価、”信学技報 ＩＮ２００５−１９５，ｐｐ．２３１−２３６，（２００６年３月）」に記載の遅延時間ｄ（ｉ，ｊ）を用い、自ノードｉから着信先ノードｊへの経路を決定するときにＭ個の中継候補ノードのいずれかを用いて迂回するか否かを決定する技術について説明する。

この場合、自ノードｉから中継候補ノードｋの遅延時間ｄ（ｉ，ｋ）と中継候補ノードｋと着信先ノードｊの間の遅延時間ｄ（ｋ，ｊ）を用いて、ｄ（ｉ，ｊ）＞ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）を満たすｋが存在するか否かを調べ、存在しない場合は、ノードｉからノードｊの直通を通信経路として決定し、存在する場合は、右辺を最小にするｋを中継ノードｋ＊とし、通信経路を自ノードｉ→中継ノードｋ＊→着信先ノードｊと決定する。

次に、第４の技術、第５の技術について説明する。これら第４，第５の技術は、上述の第１の技術におけるネットワーク条件の変動状況に応じて中継ノード候補の選択確率を変化させるものであり、本例では、中継ノード選択の際に用いるノードの得点を変更する技術を例として説明する。

第４の技術では、管理サーバ２０は、各ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントしておき、その合計値Σ_ｋＣ’（ｎ，ｋ）を計算し、それをノードペア総数Ｎ（Ｎ−１）で割ったものを、迂回経路の方が品質が良い頻度Ｆ（ｎ）とし、すなわち、Ｆ（ｎ）＝Σ_ｋＣ’（ｎ，ｋ）／｛Ｎ（Ｎ−１）｝とし、現在の時点ｎが「ｎ＞Ｔ」であればそのＴ期間前までの移動平均を意味するＦ_Ｔ（ｎ）を「Ｆ_Ｔ（ｎ）＝Σ_{ｘ＝１〜Ｔ}Ｆ（ｎ−ｘ）／Ｔ」により計算し、さらに、「Ｆ（ｎ）／Ｆ_Ｔ（ｎ）」が予め定めたしきい値よりも小さい場合には、各ノードの得点Ｃ（ｎ，ｋ）を再初期化してＣ（０，ｋ）（ｋ＝１〜Ｎ）、時点ｎ＝０とする。

これは、ネットワーク条件が変化せずに定常状態にあるときには、迂回の方がよい頻度Ｆ（ｎ）は大きく変化せずほぼ一定の値をとると考えられるが、ネットワークの条件が変化すると、もはや今の中継ノード選択では適切な迂回路を見つけることができなくなり、その結果、Ｆ（ｎ）の値が小さくなると考えられる。

そこで、Ｆ（ｎ）の挙動を監視して、Ｆ（ｎ）の値に変化が生じたと判断したら、各ノードの得点を再初期化して学習しなおすことにより、新たな状況に追従が可能となる。

第５の技術では、各ノードｉは、自ノードｉから着信先ノードｊへの遅延ｄ（ｉ，ｊ）を測定しておき、現時点ｎの自ノードから他の全てのノードヘの平均遅延時間ｄ_ａｖｇ（ｎ）＝Σ_ｊｄ（ｉ，ｊ）／（Ｎ−１）を計算する。

一方、時点ｎ−１におけるその指数重み付け移動平均ｄ_ａｖｇ_ｓ（ｎ−１）を「ｄ_ａｖｇ_ｓ（ｎ−１）＝（１−α）ｄ_ａｖｇ_ｓ（ｎ−２）＋αｄ_ａｖｇ（ｎ−１）」により計算する。ここでαは予め定める平滑化パラメータであり、０＜α＜１である。

もし、「ｄ_ａｖｇ（ｎ）＜ｄ_ａｖｇ_ｓ（ｎ−１）−ｔｈ_ｄ」となったら、その旨を、管理サーバ２０に通知する。ここで、ｔｈ_ｄはしきい値であり、予め定めるか、あるいは遅延の測定結果の履歴「ｄ_ａｖｇ_ｓ（ｎ−２），ｄ_ａｖｇ_ｓ（ｎ−３），ｄ_ａｖｇ（ｎ−４），…」から下位ｙパーセント値を求めておき、その値とｄ_ａｖｇ_ｓ（ｎ−１）の差をｔｈ_ｄに設定する。

遅延の変化の旨をノードｉから受信した管理サーバ２０は、自サーバで管理しているノードｋ（ｋ＝１〜Ｎ）の得点Ｃ（ｎ，ｋ）に関して、上位Ｘノード内にノードｉがエントリされているかどうか調べ、もしエントリされていなければ、ノードiの得点Ｃ（ｎ、ｉ）をＣ（ｎ、ｉ）←Ｃ（ｎ、ｉ）＋Ｃ_ａｄｄにより増加させる。ここで、Ｃ_ａｄｄは予め定める得点増加量である。

こうすることにより、現在は下位にランクされているノードの品質（遅延時間）が変化して向上した場合には、そのノードの得点をアップすることにより、当該ノードを適切に上位にランクインさせることが可能となる。

以下、このようにして、第１の技術もしくは第３の技術のいずれかにより、ノード間の通信品質を測定し、それを用いて迂回するか否かを決定する機能、第２の技術により中継候補ノードを選択する機能、第４の技術もしくは第５の技術のいずれかにより、中継ノード選択の際に用いるノードの得点を変更する機能を実行するための各手段について図３と図４を用いて説明する。

図３は、図２におけるオーバーレイノードの構成例を示すブロック図であり、図４は、図２における管理サーバの構成例を示すブロック図である。

図２における各ノード２１〜２５は、以下のようにして、他ノードとの通信経路を一定周期毎に更新する。ここでは、図３におけるノード２１に着目して説明をすすめる。しかし、他のノード２２〜２５も各々が独立に同様の振る舞いをする。

図３におけるノード（図中「オーバーレイノード」と記載）２１は、上述の第２の技術により、中継候補ノードを選択し、第３の技術により、ノード間の通信品質を測定し、それを用いて迂回するか否かを決定するための機能として、通信品質測定部２１ａ、通信品質取得部２１ｂ、中継ノード決定部２１ｃ、中継候補選択部２１ｄ、迂回経路設定部２１ｅを具備し、それに対応するため、図４における管理サーバ２０は、中継ノード選択回数管理部２０ａとノード得点更新・管理部２０ｂを具備している。

図３において、通信品質測定部２１ａは、測定周期τ毎に自身（ノード２１）と他のノードｊ（ｊ＝２２〜２５）との間の遅延時間ｄ（１，ｊ）を測定する。同様に、ノードｉ（ｉ＝２２〜２５）も他ノードｊ（ｊ＝ｉを除くｊ＝２１〜２５のいずれか）との遅延時間ｄ（ｉ，ｊ）を測定している。そして、この遅延時間測定を実施したら、その旨を中継候補選択部２１ｄに通知する。

中継候補選択部２１ｄは、図４の管理サーバ２０のノード得点更新・管理部２０ｂから、各ノードｋのｎ番目の測定周期（以下、時点ｎと呼ぶ）での得点Ｃ（ｎ，ｋ）をダウンロードし、それを用いて、確率ｐ_ｋ＝Ｃ（ｎ，ｋ）／Σ_ｋＣ（ｎ，ｋ）でノードｋ（ｋはｉ以外）を中継候補ノードとして選択し、これをＭ−Ｍ’個の中継候補ノードを選択するまで繰り返す。

また、残りのノード群の中から、中継候補ノードを等確率で選択し、これをＭ’個選択するまで繰り返す。このようにして選択した合計Ｍ個の中継候補ノードを、中継ノード決定部２１ｃに通知する。

通知を受けた中継ノード決定部２１ｃは、通信品質取得部２１ｂに対して、当該中継候補ノードｋから、ノードｋとノードｊの遅延時間測定結果ｄ（ｋ，ｊ）を取得するように指示する。

指示を受けた通信品質取得部２１ｂは、当該中継候補ノードｋの通信品質測定部２１aからノードｋとノードｊの遅延時間測定結果ｄ（ｋ，ｊ）を取得し、中継ノード決定部２１ｃにそれを通知する。以上の手順を、全ての中継候補ノードに対して実施する。

中継ノード決定部２１ｃは、自ノード１から中継候補ノードｋの遅延時間ｄ（１，ｋ）を通信品質測定部２１ａから取得し、それと、通信品質取得部２１ｂから通知された中継候補ノードｋと着信先ノードｊの間の遅延時問ｄ（ｋ，ｊ）を用いて、「ｄ（２１，ｊ）＞ｄ（２１，ｋ）＋ｄ（ｋ，ｊ）」を満たすｋがＭ個の候補の中に存在するか否かを調べ、存在しない場合は、自ノード２１からノードｊの直通路を通信経路として決定し、また、存在する場合は、右辺を最小にするｋを中継ノードｋ＊として決定する。

このようにして決定した後、当該ノードｋ＊の迂回経路設定部２１ｅに対して、通信経路を、「自ノード２１→中継ノードｋ＊→着信先ノードｊ」と設定するように要求する。以上の手順を全ての着信先ノードｊ（ｊ＝２２〜２５）に対して実施する。

中継ノードｋ＊の迂回経路設定部２１ｅは、「ノード２１→中継ノードｋ＊→着信先ノードｊ」の経路を設定し、その後、自身が中継ノードとして選択された旨を管理サーバ２０の中継ノード選択回数管理部２０ａに通知する。

図４における管理サーバ２０の中継ノード選択回数管理部２０ａは、中継ノードｋ＊からの通知を受けると、ノードｋ＊が中継ノードとなった回数Ｃ’（ｎ，ｋ）を、「Ｃ’（ｎ，ｋ）←Ｃ’（ｎ，ｋ）＋１」とカウントアップする。

以上を、ｎ番目の測定周期が終わるまで繰り返して、各ノードの中継ノードとなった回数を数える。その結果をノード得点更新・管理部２０ｂに通知する。

ノード得点更新・管理部２０ｂでは、ｎ＋１番目の測定周期になると、全てのノードの得点Ｃ（ｎ＋１，ｋ）を「Ｃ（ｎ＋１，ｋ）＝ｍａｘ｛Ｃ_ｌｏｗ，（１−１／ｔ’）Ｃ（ｎ，ｋ）＋１／ｔ’Ｃ’（ｎ，ｋ）｝」により更新する。

上述したように、ここで、Ｃ_ｌｏｗは予め定める得点の下限値、１／ｔ’は平滑化パラメータであり、予め定めるパラメータβ（＞０）とｃ（＞１）を用いて「ｔ’＝ｍｉｎ｛ｎ＋β，ｃ｝」で与えられ、Ｃ（ｎ，ｋ）の初期値は「Ｃ（０，ｋ）＝１（全てのｋ）」とする。

さらに、ノード得点更新・管理部２０ｂは、各ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントしておき、その合計値Σ_ｋＣ’（ｎ，ｋ）を計算し、それをノードペア総数Ｎ（Ｎ−１）で割ったものを迂回経路の方が品質が良い頻度Ｆ（ｎ）＝Σ_ｋＣ’（ｎ，ｋ）／｛Ｎ（Ｎ−１）｝とし、現在の時点ｎがｎ＞Ｔであれば、そのＴ期間前までの移動平均を意味するＦ_Ｔ（ｎ）を「Ｆ_Ｔ（ｎ）＝Σ_{ｘ＝１〜Ｔ}Ｆ（ｎ−ｘ）／Ｔ」により計算し、「Ｆ（ｎ）／Ｆ_Ｔ（ｎ）」が予め定めたしきい値よりも小さい場合には、各ノードの得点Ｃ（ｎ，ｋ）を再初期化して「Ｃ（０，ｋ）」（ｋ＝１〜Ｎ）、「時点ｎ＝０」とする。

また、図３のノード２１は、通信品質測定部２１ａにおいて、自ノード２１から着信先ノードｊへの遅延ｄ（２１，ｊ）を測定しておき、現時点ｎの自ノードから他の全てのノードヘの平均遅延時間ｄ_ａｖｇ（ｎ）＝Σ_ｊｄ（２１，ｊ）／（Ｎ−１）を計算する。

一方、時点ｎ−１におけるその指数重み付け移動平均ｄ_ａｖｇ_ｓ（ｎ−１）を「ｄ_ａｖｇ_ｓ（ｎ−１）＝（１−α）ｄ_ａｖｇ_ｓ（ｎ−２）＋αｄ_ａｖｇ（ｎ−１）」により計算する。尚、上述のように、ここでαは予め定める平滑化パラメータであり、０＜α＜１である。

もし、「ｄ_ａｖｇ（ｎ）＜ｄ_ａｖｇ_ｓ（ｎ−１）−ｔｈ_ｄ」となったら、その旨を管理サーバ２０内のノード得点更新・管理部２０ｂに通知する。尚、上述のように、ｔｈ_ｄはしきい値であり、予め定めるか、あるいは遅延の測定結果の履歴ｄ_ａｖｇ_ｓ（ｎ−２），ｄ_ａｖｇ_ｓ（ｎ−３），ｄ_ａｖｇ（ｎ−４），…から下位ｙパーセント値を求めておき、その値とｄ_ａｖｇ_ｓ（ｎ−１）の差をｔｈ_ｄに設定する。

遅延の変化の旨をノード２１から受信した管理サーバ２０内のノード得点更新・管理部２０ｂは、ノード得点更新・管理部２０ｂで管理しているノードｋ（ｋ＝１〜Ｎ）の得点Ｃ（ｎ，ｋ）に関して、上位Ｘノード内にノード２１がエントリされているかどうか調べ、もしエントリされていなければ、ノード２１の得点Ｃ（ｎ、ｉ）を「Ｃ（ｎ、ｉ）←Ｃ（ｎ、ｉ）＋Ｃ_ａｄｄ」により増加させる。尚、ここで、Ｃ_ａｄｄは上述のように予め定める得点増加量である。

次に、図５〜図９を用いて、本発明に係るオーバーレイネットワークにおける通信経路制御方法について説明する。図５は、図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第１の処理動作例を示すフローチャートであり、図６は、第２の処理動作例を示すシーケンス図、図７は、第３の処理動作例を示すフローチャート、図８は、第４の処理動作例を示すフローチャート、図９は、第５の処理動作例を示すシーケンス図である。

図５に示す例は、上述の第１の技術に相当し、ＩＰネットワークに接続するＮ個のオーバーレイノードによって構成される論理網であるオーバーレイネットワークにおいて、発信元ノードから着信先ノードヘの通信経路をネットワークの状況に応じて制御する通信経路制御手順であって、オーバーレイネットワークに属する各ノードｉ（ｉ＝１〜Ｎ）は、自ノードを発信元ノードとし他ノードｊ（ｉを除く全て）を着信先ノードｊとして、発信元ノードｉと着信先ノードｊの間の通信品質を測定し（ステップＳ５０１）、Ｎ個のノードの中からＭ個のノードを中継ノードの候補として選択し、選択した中継候補ノードｋから、中継候補ノードｋと着信先ノードｊの間の通信品質測定結果を取得し、自ノードｉから当該中継候補ノードｋを経由して着信先ノードｊに到達するときの通信品質を算出する（ステップＳ５０２）。

算出した通信品質と測定した通信品質とを比較し、測定した通信品質が良ければ自ノードｉから着信先ノードｊへの直通の通信経路を決定し、算出した通信品質が良ければ、最も高品質を提供するノードｋ＊を中継した着信先ノードｊへの通信経路を決定し（ステップＳ５０３）、当該ノードｋ＊を決定した頻度を記憶装置に記憶する（ステップＳ５０４）。

そして、次回の中継ノード候補選択時には（ステップＳ５０５）、記憶した頻度に応じた確率で（つまり，該頻度が高い順に選ばれやすくなる）Ｍ’個の中継ノード候補を選択し、残りのＭ−Ｍ’個は、頻度には依存せずに等確率で中継ノード候補を選択し（ステップＳ５０６）、さらに、Ｍ−Ｍ’個の中継ノード候補が設置されたネットワーク条件の変動を監視し（ステップＳ５０７）、変動を検知した際には（ステップＳ５０８）、当該中継ノード候補の選択確率をその状況に応じて変化させる（ステップＳ５０９）。

図６に示す例は、上述の第２の技術に相当し、中継ノードとして決定された各ノードｋは、オーバーレイネットワーク内に設置され中継ノード候補の情報を管理する管理サーバに、発信元ノードｉと着信先ノードｊとのペアの通信経路として自ノードｋが中継ノードとして決定されたことを示す情報を通知する（ステップＳ６０１）。

各ノードｋからの情報を受信した管理サーバは、当該ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントし、このカウント値を用いて、次の時点ｎ＋１における各ノードｋの得点を、式「Ｃ（ｎ＋１，ｋ）＝ｍａｘ｛Ｃ_ｌｏｗ，（１−１／ｔ’）Ｃ（ｎ，ｋ）＋１／ｔ’Ｃ’（ｎ，ｋ）｝」（「Ｃ_ｌｏｗ」は予め定める得点の下限値、「１／ｔ’」は平滑化パラメータであり、予め定めるパラメータβ（＞０）とｃ（＞１）を用いて「ｔ’＝ｍｉｎ｛ｎ＋β，ｃ｝」で与えられ、Ｃ（ｎ，ｋ）の初期値はＣ（０，ｋ）＝１（全てのｋ）とする）により更新する（ステップＳ６０２）。

発信元ノードｉは、時点ｎにおいて着信先ノードｊへの通信経路を決定する際（ステップＳ６０３）、管理サーバから各ノードｋの得点Ｃ（ｎ，ｋ）を読み出し（ステップＳ６０４）、確率ｐ_ｋ＝Ｃ（ｎ，ｋ）／Σ_ｋＣ（ｎ，ｋ）でノードｋ（ｋはｉ以外）を中継候補ノードとして選択する処理を、Ｍ−Ｍ’個の中継候補ノードが決定するまで繰り返し（ステップＳ６０５，Ｓ６０６）、さらに、残りのノード群の中から中継候補ノードを等確率で選択する処理を、Ｍ’個選択するまで繰り返す（ステップＳ６０７，Ｓ６０８）。

図７に示す例は、上述の第３の技術に相当し、発信元ノードｉは、自ノードｉから着信先ノードｊへの通信経路に、Ｍ個の中継候補ノードのいずれかを用いて迂回するか否かを決定する際、自ノードｉから中継候補ノードｋの遅延時間ｄ（ｉ，ｋ）と中継候補ノードｋと着信先ノードｊの間の遅延時間ｄ（ｋ，ｊ）を用いて、「ｄ（ｉ，ｊ）＞ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を満たすｋが存在するか否かを調べ（ステップＳ７０１）、存在しない場合は、自ノードｉから着信先ノードｊへの直通の通信経路を決定し（ステップＳ７０２）、存在する場合は、右辺を最小にするｋを中継ノードｋ＊として決定する（ステップＳ７０３）。

図８に示す例は、上述の第４の技術に相当し、管理サーバは、各ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントして、このカウント値の合計値Σ_ｋＣ’（ｎ，ｋ）を計算し（ステップＳ８０１）、計算した合計値Σ_ｋＣ’（ｎ，ｋ）をノードペア総数Ｎ（Ｎ−１）で割った値Ｆ（ｎ）（＝Σ_ｋＣ’（ｎ，ｋ）／｛Ｎ（Ｎ−１）｝）を、迂回経路の方が品質が良い頻度として求める（ステップＳ８０２）。

そして、現在の時点ｎがｎ＞Ｔであれば、Ｔ期間前までの移動平均を意味するＦ_Ｔ（ｎ）を「Ｆ_Ｔ（ｎ）＝Σ_{ｘ＝１〜Ｔ}Ｆ（ｎ−ｘ）／Ｔ」の式を用いて計算し（ステップＳ８０３）、「Ｆ（ｎ）／Ｆ_Ｔ（ｎ）」が予め定めたしきい値よりも小さければ（ステップＳ８０４）、各ノードの得点Ｃ（ｎ，ｋ）を再初期化してＣ（０，ｋ）（ｋ＝１〜Ｎ）、時点ｎ＝０とする（ステップＳ８０５）。

図９に示す例は、上述の第５の技術に相当し、各オーバーレイノードｉは、自ノードｉから着信先ノードｊへの遅延ｄ（ｉ，ｊ）を測定し（ステップＳ９０１）、現時点ｎの自ノードｉから他の全てのノードヘの平均遅延時間ｄａ「＝ｄ_ａｖｇ（ｎ）＝Σ_ｊｄ（ｉ，ｊ）／（Ｎ−１）」を計算する（ステップＳ９０２）。

また、時点ｎ−１における指数重み付け移動平均ｄ_ｎ−１（＝ｄ_ａｖｇ_ｓ（ｎ−１）を）「ｄ_ａｖｇ_ｓ（ｎ−１）＝（１−α）ｄ_ａｖｇ_ｓ（ｎ−２）＋αｄ_ａｖｇ（ｎ−１）、…αは予め定める平滑化パラメータであり、０＜α＜１」の式を用いて計算する（ステップＳ９０３）。

そして、「ｄ_ａｖｇ（ｎ）＜ｄ_ａｖｇ_ｓ（ｎ−１）−ｔｈ_ｄ、…ｔｈ_ｄはしきい値であり、予め定めるか、もしくは遅延の測定結果の履歴ｄ_ａｖｇ_ｓ（ｎ−２），ｄ_ａｖｇ_ｓ（ｎ−３），ｄ_ａｖｇ（ｎ−４），…から下位ｙパーセント値を求めておき、その値とｄ_ａｖｇ_ｓ（ｎ−１）の差をｔｈ_ｄに設定する」となれば（ステップＳ９０４）、遅延の変化を示す情報を管理サーバに通知する（ステップＳ９０５）。

管理サーバは、遅延の変化を示す情報をノードｉから受信すると（ステップＳ９０６）、自サーバで管理しているノードｋ（ｋ＝１〜Ｎ）の得点Ｃ（ｎ，ｋ）に関して上位Ｘノード内にノードｉがエントリされているかどうか調べ（ステップＳ９０７）、エントリされていなければ、ノードＩの得点Ｃ（ｎ、ｉ）を「Ｃ（ｎ、ｉ）←Ｃ（ｎ、ｉ）＋Ｃ_ａｄｄ、…Ｃ_ａｄｄは予め定める得点増加量である」の代入式を用いて増加させる（ステップＳ９０８）。

以下、図１０，１１により、上述の第１の技術を実行したときの評価結果を示す。本評価においては、国内で適当に地理的に離れた１８箇所のＩＳＰ（Internet Service Provider）に利用者として契約したコンピュータ端末において、各端末間において１時間毎に毎秒１パケットを３分間送出して遅延時間（３分間での最大遅延）を測定したデータを用いた（測定期間は４８時間）。

ｎ時間目（ｎ＝１，２，…４８）における端末ｉと端末ｊの間の遅延時間ｄ（ｎ，ｉ，ｊ）を用い、１８個の端末をオーバーレイノードとみなす。以上のデータを用いて、ｎ＝１〜２４時間目までは、実測データの通り、各ノード間の遅延を模擬し、ｎ＝２４時間目以降において、以下のネットワーク変動を模擬した。

ｎ＝２４時間目において、得点Ｃ（ｎ，ｋ）が１位のノードと１８位のノードの遅延時間を入れ換え、２位のノードと１７位のノードも入れ替えた。つまり、上位ノードの遅延時間が仮想的に下位ノードの遅延時間に変化した場合（つまり、上位ノードの遅延時間が悪くなった場合）を模擬し、同様に下位ノードの遅延時間が上位ノードのそれに変化して遅延時問がよくなった場合を模擬した。

なお、中継ノード候補数Ｍ＝４，Ｍ’＝１とし、「β＝０．５」、「ｃ＝４」、「Ｃ_ｌｏｗ＝０．１」とした。

図１０には、このときのｎ時間目の遅延時間の時系列を示す。ここでは、ｎ時間目における、全ノードペアの遅延時間の９５パーセンタイルをプロットしている。図中learnedが本例を適用した場合の結果である。比較として、経路制御を行わなかった場合（つまりすべて直通路を選択した場合で、図中default）、中継ノード候補数を制限せずにＮ＝１８個の全ノードを中継候補として利用できる最適な場合（図中optimal）の結果も併せて示す。

これにより、本発明は、ネットワーク条件が変化したｎ＝２４時間目以降も全経路探索時（optimal）とほぼ同等の品質改善ができていることが分かる。

参考までに、本発明における１位、２位、３位、４位、１７位、１８位ノードの得点の推移を図１１に示す。これより、もともと下位であったノードの得点を適切に上昇させることができていることが確認できる。

以上、図２〜図１１を用いて説明したように、本例によれば、ネットワーク条件の変動に追従して、オーバーレイネットワークにおける通信経路計算に伴うコストを削減しつつ、通信品質の改善を図ることが可能となる。

尚、本発明は、図２〜図１１を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、オーバーレイノードや管理サーバのコンピュータ構成として、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Flexible Disk）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。

オーバーレイネットワークによる経路制御の概念を示す説明図である。 本発明に係る通信経路制御システムを具備したオーバーレイネットワークの構成例を示すブロック図である。 図２におけるオーバーレイノードの構成例を示すブロック図である。 図２における管理サーバの構成例を示すブロック図である。 図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第１の処理動作例を示すフローチャートである。 図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第２の処理動作例を示すシーケンス図である。 図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第３の処理動作例を示すフローチャートである。 図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第４の処理動作例を示すフローチャートである。 図２におけるオーバーレイノードと管理サーバからなる通信経路制御システムの本発明に係る第５の処理動作例を示すシーケンス図である。 本例の効果を示す説明図である。 本例を適用したときの得点の推移を示す説明図である。

符号の説明

１〜３：オーバーレイノード、４〜８：ＩＰルータ、１１：オーバーレイネットワーク、１２：ＩＰネットワーク、２０：管理サーバ、２０ａ：中継ノード選択回数管理部、２０ｂ：ノード得点更新・管理部、２１〜２５：オーバーレイノード、２１ａ：通信品質測定部、２１ｂ：通信品質取得部、２１ｃ：中継ノード決定部、２１ｄ：中継候補選択部、２１ｅ：迂回経路設定部。

Claims (7)

1. ＩＰネットワークに接続するＮ個のオーバーレイノードによって構成される論理網であるオーバーレイネットワークにおいて、発信元ノードから着信先ノードヘの通信経路をネットワークの状況に応じて制御する通信経路制御方法であって、
   上記オーバーレイネットワークに属する各ノードｉ（ｉ＝１〜Ｎ）は、自ノードを発信元ノードとし他ノードｊ（ｉを除く全て）を着信先ノードｊとして、発信元ノードｉと着信先ノードｊの間の通信品質を測定するステップと、
   Ｎ個のノードの中からＭ個のノードを中継ノードの候補として選択し、選択した中継候補ノードｋから、該中継候補ノードｋと着信先ノードｊの間の通信品質測定結果を取得し、自ノードｉから当該中継候補ノードｋを経由して着信先ノードｊに到達するときの通信品質を算出するステップと、
   該算出した通信品質と上記測定した通信品質とを比較し、測定した通信品質が良ければ自ノードｉから着信先ノードｊへの直通の通信経路を決定し、算出した通信品質が良ければ、最も高品質を提供するノードｋ＊を中継した着信先ノードｊへの通信経路を決定するステップと、
   当該ノードｋ＊を決定した頻度を記憶装置に記憶するステップと、
   次回の中継ノード候補選択時に、上記記憶した頻度が高い順にＭ’個の中継ノード候補を選択し、残りのＭ−Ｍ’個は、上記頻度には依存せずに等確率で中継ノード候補を選択するステップと、
   上記Ｍ−Ｍ’個の中継ノード候補が設置されたネットワーク条件の変動を監視し、変動を検知した際には当該中継ノード候補の上記選択確率をその状況に応じて変化させるステップと
   を有することを特徴とするオーバーレイネットワークの通信経路制御方法。
2. 請求項１に記載のオーバーレイネットワークの通信経路制御方法であって、
   上記中継ノードとして決定された各ノードｋが、オーバーレイネットワーク内に設置され中継ノード候補の情報を管理するサーバに、発信元ノードｉと着信先ノードｊとのペアの通信経路として自ノードｋが中継ノードとして決定されたことを示す情報を通知するステップを実行し、
   各ノードｋからの上記情報を受信したサーバが、当該ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントし、該カウント値を用いて、次の時点ｎ＋１における各ノードｋの得点を、式「Ｃ（ｎ＋１，ｋ）＝ｍａｘ｛Ｃ_ｌｏｗ，（１−１／ｔ’）Ｃ（ｎ，ｋ）＋１／ｔ’Ｃ’（ｎ，ｋ）｝」（「Ｃ_ｌｏｗ」は予め定める得点の下限値、「１／ｔ’」は平滑化パラメータであり、予め定めるパラメータβ（＞０）とｃ（＞１）を用いて「ｔ’＝ｍｉｎ｛ｎ＋β，ｃ｝」で与えられ、Ｃ（ｎ，ｋ）の初期値はＣ（０，ｋ）＝１（全てのｋ）とする）により更新するステップと、
   上記発信元ノードｉが、上記時点ｎにおいて着信先ノードｊへの通信経路を決定する際、上記サーバから各ノードｋの得点Ｃ（ｎ，ｋ）を読み出し、確率ｐ_ｋ＝Ｃ（ｎ，ｋ）／Σ_ｋＣ（ｎ，ｋ）でノードｋ（ｋはｉ以外）を中継候補ノードとして選択する処理を、Ｍ−Ｍ’個の中継候補ノードが決定するまで繰り返すステップと、
   残りのノード群の中から中継候補ノードを等確率で選択する処理を、Ｍ’個選択するまで繰り返すステップとを実行する
   ことを特徴とするオーバーレイネットワークの通信経路制御方法。
3. 請求項１に記載のオーバーレイネットワークの通信経路制御方法であって、
   上記発信元ノードｉは、
   自ノードｉから着信先ノードｊへの通信経路に、上記Ｍ個の中継候補ノードのいずれかを用いて迂回するか否かを決定する際に、
   自ノードｉから中継候補ノードｋの遅延時間ｄ（ｉ，ｋ）と中継候補ノードｋと着信先ノードｊの間の遅延時間ｄ（ｋ，ｊ）を用いて、「ｄ（ｉ，ｊ）＞ｄ（ｉ，ｋ）＋ｄ（ｋ，ｊ）」を満たすｋが存在するか否かを調べるステップと、
   存在しない場合は、自ノードｉから着信先ノードｊへの直通の通信経路を決定し、存在する場合は、右辺を最小にするｋを中継ノードｋ＊として決定するステップと
   を有することを特徴とするオーバーレイネットワークの通信経路制御方法。
4. 請求項２に記載のオーバーレイネットワークの通信経路制御方法であって、
   上記管理サーバは、
   各ノードｋが時点ｎに中継ノードとなった回数Ｃ’（ｎ，ｋ）をカウントして、該カウント値の合計値Σ_ｋＣ’（ｎ，ｋ）を計算するステップと、
   計算した合計値Σ_ｋＣ’（ｎ，ｋ）をノードペア総数Ｎ（Ｎ−１）で割った値Ｆ（ｎ）（＝Σ_ｋＣ’（ｎ，ｋ）／｛Ｎ（Ｎ−１）｝）を、迂回経路の方が品質が良い頻度として求めるステップと、
   現在の時点ｎがｎ＞Ｔであれば、Ｔ期間前までの移動平均を意味するＦ_Ｔ（ｎ）を「Ｆ_Ｔ（ｎ）＝Σ_{ｘ＝１〜Ｔ}Ｆ（ｎ−ｘ）／Ｔ」の式を用いて計算し、「Ｆ（ｎ）／Ｆ_Ｔ（ｎ）」が予め定めたしきい値よりも小さければ、各ノードの得点Ｃ（ｎ，ｋ）を再初期化してＣ（０，ｋ）（ｋ＝１〜Ｎ）、時点ｎ＝０とするステップとを有する
   ことを特徴とするオーバーレイネットワークの通信経路制御方法。
5. 請求項２に記載のオーバーレイネットワークの通信経路制御方法であって、
   各オーバーレイノードｉは、
   自ノードｉから着信先ノードｊへの遅延ｄ（ｉ，ｊ）を測定するステップと、
   現時点ｎの自ノードｉから他の全てのノードヘの平均遅延時間ｄ_ａｖｇ（ｎ）＝Σ_ｊｄ（ｉ，ｊ）／（Ｎ−１）を計算するステップと、
   時点ｎ−１における指数重み付け移動平均ｄ_ａｖｇ_ｓ（ｎ−１）を「ｄ_ａｖｇ_ｓ（ｎ−１）＝（１−α）ｄ_ａｖｇ_ｓ（ｎ−２）＋αｄ_ａｖｇ（ｎ−１）、…αは予め定める平滑化パラメータであり、０＜α＜１」の式を用いて計算するステップと、
   「ｄ_ａｖｇ（ｎ）＜ｄ_ａｖｇ_ｓ（ｎ−１）−ｔｈ_ｄ、…ｔｈ_ｄはしきい値であり、予め定めるか、もしくは遅延の測定結果の履歴ｄ_ａｖｇ_ｓ（ｎ−２），ｄ_ａｖｇ_ｓ（ｎ−３），ｄ_ａｖｇ（ｎ−４），…から下位ｙパーセント値を求めておき、その値とｄ_ａｖｇ_ｓ（ｎ−１）の差をｔｈ_ｄに設定する」となれば、遅延の変化を示す情報を上記管理サーバに通知するステップとを有し、
   該管理サーバは、遅延の変化を示す情報をノードｉから受信すると、自サーバで管理しているノードｋ（ｋ＝１〜Ｎ）の得点Ｃ（ｎ，ｋ）に関して上位Ｘノード内にノードｉがエントリされているかどうか調べ、エントリされていなければ、ノードiの得点Ｃ（ｎ、ｉ）を「Ｃ（ｎ、ｉ）←Ｃ（ｎ、ｉ）＋Ｃ_ａｄｄ、…Ｃ_ａｄｄは予め定める得点増加量である」の代入式を用いて増加させるステップを有する
   ことを特徴とするオーバーレイネットワークの通信経路制御方法。
6. 請求項１もしくは請求項３のいずれかに記載のオーバーレイネットワークの通信経路制御方法における各ステップを実行してノード間の通信品質の測定および中継ノードを用いて迂回するか否かを決定する手段と、
   請求項２に記載のオーバーレイネットワークの通信経路制御方法における各ステップを実行して中継候補ノードの選択を行う手段と、
   請求項４もしくは請求項５のいずれかに記載のオーバーレイネットワークの通信経路制御方法における各ステップを実行して、中継ノード選択の際に用いるノードの得点を変更する手段と
   を具備することを特徴とするオーバーレイネットワークにおける通信経路制御システム。
7. コンピュータに、請求項１から請求項５のいずれかに記載のオーバーレイネットワークの通信経路制御方法における各ステップを実行させるためのプログラム。

Images