(57)【要約】【課題】  一部のオーバーレイノード間で部分的に測定された品質情報を利用して計算することによって計算量の大幅な削減を可能とすること。【解決手段】  代表ノード間の時刻ｔにおける通信品質ｑ（ｔ，ｃｉ，１，ｃｊ，１）を測定する手段、ノードｃｉ，ｋからノードｃｊ，１へ至る通信の時刻ｔにおける最適経路を、ｑ（ｔ，ｃｉ，１，ｃｖ，１）＋ｑ（ｔ，ｃｖ，１，ｃｊ，１）が、最小となるｖの値ｖ’を求め、ｑ（ｔ，ｃｉ，１，ｃｊ，１）とｑ（ｔ，ｃｉ，１，ｃｖ’，１）＋ｑ（ｔ，ｃｖ’，１，ｃｊ，１）を比較し、前者が小さい場合は通信経路をｃｉ，ｋ→ｃｊ，ｌ）とし、後者が小さい場合は通信経路をｃｉ，ｋ→ｃｖ’，１→ｃｊ，ｌとする。なお、ｑ（ｔ，ｃｉ，ｋ，ｃｊ，ｌ）或いはｑ（ｔ，ｃｉ，１，ｃｊ，１）が閾値よりも小さい場合には通信経路をｃｉ，ｋ→ｃｊ，ｌとし、大きい場合には上記手順により通信経路を計算してもよい。【選択図】      図２
2006245874.tif 000002
【特許請求の範囲】
【請求項１】
ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークに属する任意の二つのノード間の通信経路を、当該ネットワークにおける部分測定を利用して計算するための通信経路計算システムであって、
前記オーバーレイネットワークに属する全てのノードをｍ個のクラスタＣ１，Ｃ２，・・・，Ｃｍに分類し、クラスタＣｉに属するノードをｃｉ，１,ｃｉ，２,・・・、,ｃｉ，ｎｉとし、各クラスタＣｉに予め唯一の代表ノードｃｉ，１（ｉ＝１，２，・・・，ｍ）を設定しておき、前記オーバーレイネットワークに属する二つのノードａ，ｂについて、時刻ｔにおいてａからｂへデフォルトの経路で通信する際の通信品質をｑ（ｔ，ａ，ｂ）と記し、その経路をａ→ｂと記すとき、下記の各手段を具備することを特徴とする通信経路計算システム。
（Ａ）代表ノード間の時刻ｔにおける通信品質ｑ（ｔ，ｃｉ，１，ｃｊ，１）を測定する手段（ｉ，ｊ＝１，２，・・・，ｍ、ｉ≠ｊ）、
（Ｂ）ｃｉ，ｋからｃｊ，ｌへ至る通信の時刻ｔにおける最適経路を、ｑ（ｔ，ｃｉ，１，ｃｖ，１）＋ｑ（ｔ，ｃｖ，１，ｃｊ，１）が、最小となるｖの値ｖ’を求め（ｖ’＝１，２，・・・，ｍ、ｖ’≠ｉ，ｊ）、ｑ（ｔ，ｃｉ，１，ｃｊ，１）とｑ（ｔ，ｃｉ，１，ｃｖ’，１）＋ｑ（ｔ，ｃｖ’，１，ｃｊ，１）を比較し、前者の方が小さい場合は通信経路をｃｉ，ｋ→ｃｊ，ｌとし、後者の方が小さい場合は通信経路をｃｉ，ｋ→ｃｖ’，１→ｃｊ，ｌとして計算する手段（ｋ＝１，２，・・・，ｎｉ，ｌ＝１，２，・・・，ｎｊ）
【請求項２】
請求項１記載の通信経路計算システムにおいて、さらに、
ｑ（ｔ，ｃｉ，ｋ，ｃｊ，ｌ）或いはｑ（ｔ，ｃｉ，１，ｃｊ，１）と予め定められた閾値を比較する手段を有し、ｑ（ｔ，ｃｉ，ｋ，ｃｊ，ｌ）或いはｑ（ｔ，ｃｉ，１，ｃｊ，１）が、前記予め定められた閾値よりも小さい場合に通信経路をｃｉ，ｋ→ｃｊ，ｌとするとともに、予め定められた閾値よりも大きい場合に前記（Ａ）および（Ｂ）における各手段の処理を行うようにしたことを特徴とする通信経路計算システム。
【請求項３】
ＩＰネットワーク上に論理的に形成されたオーバーレイネットワークに属する任意の二つのノード間の通信経路を、当該ネットワークにおける部分測定を利用して計算するための通信経路計算方法であって、
前記オーバーレイネットワークに属する全てのノードをｍ個のクラスタＣ１，Ｃ２，・・・，Ｃｍに分類し、クラスタＣｉに属するノードをｃｉ，１,ｃｉ，２,・・・、,ｃｉ，ｎｉとし、各クラスタＣｉに予め唯一の代表ノードｃｉ，１（ｉ＝１，２，・・・，ｍ）を設定しておき、前記オーバーレイネットワークに属する二つのノードａ，ｂについて、時刻ｔにおいてａからｂへデフォルトの経路で通信する際の通信品質をｑ（ｔ，ａ，ｂ）と記し、その経路をａ→ｂと記すとき、下記の各ステップを具備することを特徴とする通信経路計算方法。
（Ｃ）代表ノード間の時刻ｔにおける通信品質ｑ（ｔ，ｃｉ，１，ｃｊ，１）を測定するステップ（ｉ，ｊ＝１，２，・・・，ｍ、ｉ≠ｊ）、
（Ｄ）ｃｉ，ｋからｃｊ，ｌへ至る通信の時刻ｔにおける最適経路を、ｑ（ｔ，ｃｉ，１，ｃｖ，１）＋ｑ（ｔ，ｃｖ，１，ｃｊ，１）が、最小となるｖの値ｖ’を求め（ｖ’＝１，２，・・・，ｍ、ｖ’≠ｉ，ｊ）、ｑ（ｔ，ｃｉ，１，ｃｊ，１）とｑ（ｔ，ｃｉ，１，ｃｖ’，１）＋ｑ（ｔ，ｃｖ’，１，ｃｊ，１）を比較し、前者の方が小さい場合は通信経路をｃｉ，ｋ→ｃｊ，ｌとし、後者の方が小さい場合は通信経路をｃｉ，ｋ→ｃｖ’，１→ｃｊ，ｌとして計算するステップ（ｋ＝１，２，・・・，ｎｉ，ｌ＝１，２，・・・，ｎｊ）
【請求項４】
請求項３記載の通信経路計算方法において、さらに、
ｑ（ｔ，ｃｉ，ｋ，ｃｊ，ｌ）或いはｑ（ｔ，ｃｉ，１，ｃｊ，１）が、予め定められた閾値よりも小さい場合に通信経路をｃｉ，ｋ→ｃｊ，ｌとするとともに、予め定められた閾値よりも大きい場合に前記（Ｃ）および（Ｄ）における各ステップの処理を順次行うようにしたことを特徴とする通信経路計算方法。
【請求項５】
請求項３または４記載の通信経路計算方法において、
前記通信品質ｑ（ｔ，ａ，ｂ）を、ノードａ，ｂ間の時刻ｔにおける遅延時間ｄ（ｔ，ａ，ｂ）を用いて通信品質ｑ（ｔ，ａ，ｂ）＝ｄ（ｔ，ａ，ｂ）とすることを特徴とする通信経路計算方法。
【請求項６】
請求項３または４記載の通信経路計算方法において、
前記通信品質として、ノードａ，ｂ間の時刻ｔにおける遅延時間ｄ（ｔ，ａ，ｂ）の所定時間における最小値，平均値，あるいは最大値のいずれかを用いたことを特徴とする通信経路計算方法。
【請求項７】
請求項３または４記載の通信経路計算方法において、
前記通信品質ｑ（ｔ，ａ，ｂ）を、ノードａ，ｂ間の時刻ｔにおけるパケット損失率ｐ（ｔ，ａ，ｂ）を用いて通信品質ｑ（ｔ，ａ，ｂ）＝−log(1−ｐ（ｔ，ａ，ｂ））とすることを特徴とする通信経路計算方法。
【請求項８】
請求項３または４記載の通信経路計算方法において、
前記通信品質として、ノードａ，ｂ間の時刻ｔにおけるパケット損失率ｐ（ｔ，ａ，ｂ）の所定時間における最小値，平均値，あるいは最大値のいずれかを用いたことを特徴とする通信経路計算方法。
【請求項９】
請求項３から８のいずれかに記載の通信経路計算方法における各ステップの処理をコンピュータに実行させるための通信経路計算用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰネットワークにおけるエンド・ツー・エンドの通信品質を向上させることが可能な通信経路計算システムおよび通信経路計算方法ならびにそのためのプログラムに関するものである。
【背景技術】
【０００２】
インターネットは多様なアプリケーションの収容を可能とすべく発展・普及してきており、昨今では、VoIP（Voice over IP）やストリーミングに代表されるQoS（Quality of Service）に敏感な実時間アプリケーション等の収容も急速に進展している。
【０００３】
これに伴い、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術 --- エンド・ツー・エンドQoS管理技術 --- をインターネット上で実現することが重要な課題となっている。
【０００４】
しかしながら、このような技術を実現する上では、以下に示す問題点がある。
（Ａ）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００５】
（Ｂ）インターネットは管理主体の異なる複数のAS（Autonomous System）によって形成されており、全てのASに対して一斉に新たな機能拡張することは困難である。
【０００６】
こうした中，下位のネットワークレイヤを変更することなくエンド・ツー・エンドQoSの向上を可能とする有力な技術として、オーバーレイネットワークによるQoS管理技術が注目されている（非特許文献１参照）
【０００７】
オーバーレイネットワークとは、既存のリンクを用いて、その上位層における目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである（非特許文献２参照）。
【０００８】
オーバーレイネットワークによるQoS管理の基本的な概念を図５に例示する。
図５において、ｘからｙに向けて、点線の矢印で表されるＩＰルータＲ１，Ｒ２，Ｒ３を介する経路にトラヒックが流れているとする。また、この経路上には輻輳しているＩＰルータが存在しており、その結果としてｘ，ｙ間のQoSが低下しているとする。
【０００９】
このとき、オーバーレイノードａ，ｂ，ｃで形成されるオーバーレイネットワーク（Ｏｖｅｒｌａｙ ＮＷ）を用いて、実線の矢印で表される経路（ｘ→オーバーレイノードａ→オーバーレイノードｂ→オーバーレイノードｃ→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【００１０】
実際、非特許文献３、非特許文献４、非特許文献５では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。
【００１１】
【非特許文献１】L.Zhi and P.Mohapatra, “QRON: QoS-aware routing in overlay networks,”IEEE J.Select.Areas Commun., vol.22, pp.29-40, January 2004.
【非特許文献２】WIDEプロジェクト,“オーバーレイネットワークによる統合分散環境” WIDEプロジェクト研究報告書, 第17部, 2002.
【非特許文献３】亀井, 川原“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性” 信学ソ大, BS-5-3, 2004.
【非特許文献４】S.Rewaskar and J.Kaur,“Testing the Scalability of Overlay Routing Infrastructures, ” Proc. PAM 2004, April 2004.
【非特許文献５】S.Banerjee, T.G.Griffin and M.Pias,“The Interdomain Connectivity of PlanetLab Nodes”, Proc. PAM 2004, April 2004.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、これらの結果はオーバーレイネットワークのトポロジをフルメッシュとし、全てのオーバーレイノード間で測定した品質情報を利用して理想的な通信経路計算を行った場合の評価となっており、オーバーレイノードの総数が増加した場合のスケーラビリティの低下については考慮されていない。
【００１３】
すなわち、オーバーレイノードの総数が大きい場合には、全てのオーバーレイノード間において品質情報の測定を行った上で通信経路の計算を行う事は計算量が膨大になり現実的には不可能であるという問題がある。
【００１４】
本発明の目的は、上記の問題点を鑑み、全てのオーバーレイノード間における品質情報の測定を行うのではなく、一部のオーバーレイノード間で部分的に測定された品質情報を利用して計算することによって計算量の大幅な削減を可能とした通信経路計算システムおよび方法ならびにそのためのプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
上記目的を達成するため、本発明では、予めクラスタ化されたオーバーレイネットワークおいて、各クラスタの代表ノード間で測定された品質情報のみを用いて通信経路を計算する。このことにより、オーバーレイノードの総数が大きい場合においても、計算量が削減され、ＩＰネットワークにおけるエンド・ツー・エンドの通信品質を向上し得る通信経路の計算が可能となる。
【００１６】
より詳細には、通信経路を計算するために、本発明では次の各手段を具備する。
【００１７】
（ａ）代表ノード間の時刻ｔにおける通信品質ｑ（ｔ，ｃｉ，１，ｃｊ，１）を測定する手段（ｉ，ｊ＝１，２，・・・，ｍ、ｉ≠ｊ）
【００１８】
（ｂ）ノードｃｉ，ｋからノードｃｊ，１へ至る通信の時刻ｔにおける最適経路を、次の手順で計算する手段（ｋ＝１，２，・・・，ｎｉ，ｌ＝１，２，・・・，ｎｊ）
＜Step １＞：ｑ（ｔ，ｃｉ，１，ｃｖ，１）＋ｑ（ｔ，ｃｖ，１，ｃｊ，１）が、最小となるｖの値ｖ’を求める（ｖ’＝１，２，・・・，ｍ、ｖ’≠ｉ，ｊ）。
＜Step ２＞：ｑ（ｔ，ｃｉ，１，ｃｊ，１）とｑ（ｔ，ｃｉ，１，ｃｖ’，１）＋ｑ（ｔ，ｃｖ’，１，ｃｊ，１）を比較し、前者が小さい場合は通信経路をｃｉ，ｋ→ｃｊ，ｌとし、後者が小さい場合は通信経路をｃｉ，ｋ→ｃｖ’，１→ｃｊ，ｌとする。
【００１９】
なお、ｑ（ｔ，ｃｉ，ｋ，ｃｊ，ｌ）或いはｑ（ｔ，ｃｉ，１，ｃｊ，１）が、予め定められた閾値よりも小さい場合には通信経路をｃｉ，ｋ→ｃｊ，ｌとし、大きい場合には上記＜Step １＞と上記＜Step ２＞の手順により通信経路を計算してもよい。
【発明の効果】
【００２０】
以上のように、本発明によれば、全てのオーバーレイノード間で品質情報を測定することなく、一部のオーバーレイノード間で部分的に測定された品質情報のみを利用することによって通信経路計算を行うことができる。また、計算された通信経路を用いることによって、QoSの向上させることができるため、本発明による通信経路計算は有用である。
【発明を実施するための最良の形態】
【００２１】
以下、図を用いて本発明を実施するための最良の形態例を説明する。
【００２２】
図１は、本発明の実施形態を説明する説明図、図２は、本発明に係わる通信経路計算システムの構成例を示すブロック図、図３は、本発明に係わる通信経路計算システムの手順例を示すフローチャートである。
【００２３】
なお、オーバーレイネットワークに属する全てのノードは、予めｍ個のクラスタに分類されているとし、このクラスタをＣ１，Ｃ２，・・・Ｃｍと書き、クラスタＣｉに属するノードをｃｉ，１，ｃｉ，２，・・・，ｃｉ，ｎｉと書く（ｉ＝１，２，・・・，ｍ）。したがって、オーバーレイネットワークに属するノードの総数をｎとすると、ｎ＝ｎ１＋ｎ２＋・・・・＋ｎｍとなる。
【００２４】
また、各クラスタＣｉには予め唯一の代表ノードが設定されているとし、それを一般性を失うことなくｃｉ，１とする（ｉ＝１，２，・・・，ｍ）。さらに、通信経路を計算する際に参照する通信品質ｑの基準は予め設定されているとする。
【００２５】
通信品質ｑの基準としては、例えば、ノードａ，ｂ間の時刻ｔにおける遅延時間ｄ（ｔ，ａ，ｂ）を用いたり、または遅延時間ｄ（ｔ，ａ，ｂ）の代わりに該遅延時間ｄ（ｔ，ａ，ｂ）の所定時間内における最小値，平均値，あるいは最大値などの統計値のいすれかを用いるようにしてもよい。
【００２６】
さらに、通信品質ｑの基準としては、例えば、ノードａ，ｂ間の時刻ｔにおけるパケット損失率ｐ（ｔ，ａ，ｂ）を用い、通信品質ｑ（ｔ，ａ，ｂ）＝−log(1−ｐ（ｔ，ａ，ｂ））を用いたり、または、上記式においてパケット損失率ｐ（ｔ，ａ，ｂ）の代わりに所定時間内におけるパケット損失率ｐ（ｔ，ａ，ｂ）の最小値，平均値，あるいは最大値などの統計値のいずれかを用いるようにしてもよい。
【００２７】
時刻ｔにおいて、ノードｃａ，ｘからノードｃｂ，ｙへの通信要求が発生した場合（ステップＳ１）の動作について説明する。
【００２８】
このとき、通信経路計算部１は、情報蓄積部２に蓄積されている代表ノード間の通信品質情報を用いて経路の計算を行う（ステップＳ２）。
【００２９】
なお、通信経路計算部１は、全てのオーバーレイノードに配備されていてもよいし、一部のオーバーレイノード（例えば、代表オーバーレイノード）のみに配備されていてもよいし、或いは、オーバーレイノードではない別のノード（例えば、外部サーバ）等に配備されていてもよい。
【００３０】
一方、通信品質測定部３においては、通信要求の発生の有無に関わらず、全ての代表ノードの対地の組み合わせについて、予め定められた単位時間毎に、代表ノード間の通信品質の測定を実施されており（ステップＳ３）、その測定結果は情報蓄積部２に集中的、或いは分散的に蓄積されている（ステップＳ４）。
【００３１】
蓄積されている情報は、例えば、通信品質ｑ（ｔ，ｃ１，ｎｉ，ｃ１，ｎｊ）である（ｉ，ｊ＝１，２，・・・，ｍ，ｉ≠ｊ）。
【００３２】
また、通信経路計算部１における経路計算手順（ステップＳ２）の詳細は以下の通りである。
【００３３】
＜ステップＳ２−１＞:ｑ（ｔ，ｃａ，１，ｃｖ，１）＋ｑ（ｔ，ｃｖ，１，ｃｂ，１）が最小となるｖの値ｖ’を求める。
【００３４】
＜ステップＳ２−２＞：ｑ（ｔ，ｃａ，１，ｃｂ，１）とｑ（ｔ，ｃａ，１，ｃｖ’，１）＋ｑ（ｔ，ｃｖ’、１、ｃｂ，１）を比較し、前者が小さい場合は通信経路をｃａ，ｘ→ｃｂ，ｙとし、後者が小さい場合は通信経路をｃａ，ｘ→ｃｖ’，１→ｃｂ，ｙとする。
【００３５】
ただし、ｑ（ｔ，ｃａ，ｘ，ｃｃ，ｙ）或いはｑ（ｔ，ｃａ，１，ｃｂ，１）を別途測定した上で、その値が予め定められた閾値よりも小さい場合には通信経路をｃａ，ｘ→ｃｂ，ｙとし、大きい場合には上記＜ステップＳ２−１＞および＜ステップＳ２−２＞の手順で通信経路を計算してもよい。
【００３６】
なお、通信経路計算部１、情報蓄積部２、通信品質測定部３における上記の各処理は、コンピュータプログラム化されてＣＤ−ＲＯＭ，ＦＤ，ＤＶＤなどの記録媒体やインターネットなどのネットワークを介して流通させることができる。
【００３７】
利用者は、これらの記録媒体やネットワークを介して入手したプログラムをコンピュータにインストールしてＣＰＵで実行することにより通信経路計算部１、情報蓄積部２、通信品質測定部３における上記の各処理を実現できる。
【００３８】
本発明の効果を見るために、実際のインターネット上において測定したデータを用いて、上記の手順を実行した場合の評価結果を示す。
【００３９】
評価に利用したデータは、国内で適当に地理的に離れた１８箇所のＩＳＰに利用者として契約した端末において、各対地での遅延測定（ping）を、１時間毎に毎秒１パケットで３分間（１８０パケット）実施したものである。分析対象としたのは、一日分のデータの内、対地毎のｔ時間目における端末ｘ，ｙ間の３分間の測定の中での最大遅延時間である。
【００４０】
本評価では、地理的に近いノードをまとめて４つのクラスタ（クラスタ：Ｃ１，Ｃ２，Ｃ３，Ｃ４に分類し（クラスタに含まれるノード数はそれぞれ、４，４，４，６とした）、各々のクラスタについて１つずつ代表ノードを適切に計算した上で（代表ノード：ｃ１，１，ｃ２，１，ｃ３，１，ｃ４，１（本評価では、適切な代表ノードを試行錯誤的に選択した））、代表ノード間で測定された品質情報のみを用いて通信経路計算を行った。
【００４１】
図４は、上記の方法で通信経路計算した場合の最大遅延時間の累積分布（line１）、ｃａ，１→ｃｂ，１の最大遅延時間が２００ｍｓを超えた場合のみに上記の方法を適用した場合の最大遅延時間の累積分布（line２）、本発明による通信経路を計算せずにデフォルトの経路を利用した場合の最大遅延時間の累積分布（line３）を示している。
【００４２】
本図より、end-to-endの最大遅延時間がある閾値（ここでは２００ｍｓ）を超えた場合に、本発明の方法で通信経路を計算することによって、QoSの向上が図れることが分かる。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施形態を説明するための図である。
【図２】本発明に係わる通信経路計算システムの構成例を示すブロック図である。
【図３】本発明に係わる通信経路計算システムの手順例を示すフローチャートである。
【図４】本発明の方法で通信経路計算した場合の最大遅延時間の累積分布（line１）、ｃａ，１→ｃｂ，１の最大遅延時間が２００ｍｓを超えた場合のみに上記の方法を適用した場合の最大遅延時間の累積分布（line２）、本発明による通信経路を計算せずにデフォルトの経路を利用した場合の最大遅延時間の累積分布（line３）を示す図である。
【図５】オーバーレイネットワークによるQoS管理の基本的な概念を例示する図である。
【符号の説明】
【００４４】
１：通信経路計算部
２：情報蓄積部
３：通信品質測定部
ｃａ，１、Ｃｂ、１，Ｃｖ１，１，ＣＶ２，１：代表ノード
ｃａ，２，・・・，ｃａ，ｘ，・・・，ｃａ，ｎａ，ｃｂ，２，・・・，ｃｂ，ｙ，・・・ｃｂ，ｎｂ，ｃｖ１，２，ｃｖ１，３，・・・，ｃｖ１，ｎｖ１，ｃｖ２，２，ｃｖ２，３，・・・，ｃｖ２，ｎｖ２：ノード
ａ，ｂ，ｃ：オーバオレイノード
Ｒ１〜Ｒ５：ＩＰルータ
Ｃａ，Ｃｂ，Ｃｖ１，Ｃｖ２：クラスタ
【図１】
2006245874.tif 000003
【図２】
2006245874.tif 000004
【図３】
2006245874.tif 000005
【図４】
2006245874.tif 000006
【図５】
2006245874.tif 000007