(57)【特許請求の範囲】
【請求項１】
IP(Internet  Protocol)ネットワークに接続するいくつかのオーバレイノードによって構築される論理網であるオーバレイネットワークを構成し、該オーバレイノードのうち、コンテンツキャッシュ機能を有するノードであるキャッシュオーバレイノード、全てのコンテンツを保持するノードであるオリジナルノード及び管理サーバからなるシステムにおけるオーバレイネットワークを用いたコンテンツ配信方法であって、
前記管理サーバは、
配信要求ユーザ装置からコンテンツmの要求を取得すると、キャッシュオーバレイノードと該ノードが保持するコンテンツを対応付けて保持するコンテンツ保持リスト記憶手段を参照して、オリジナルノード及びキャッシュオーバレイノードの中から、該コンテンツを保持するノードを探索し、その中でユーザとのホップ数（中継ルータ数）が最も小さいノードを、オーバレイノードの位置情報を管理するオーバレイノード位置記憶手段を参照してコンテンツ配信元ノードとして選択し、前記オーバレイノードに通知するノード選択ステップを行い、
前記オーバレイノードは、
前記コンテンツ配信元ノードと前記配信要求ユーザの間の経路を決定する経路決定ステップと、
決定された経路に従ってコンテンツを配信するコンテンツ配信ステップと、
コンテンツ配信経路上に、キャッシュオーバレイノードが存在すれば、そこに該コンテンツをキャッシュするコンテンツキャッシュステップと、
を行い、
前記オーバレイノードにおける前記経路決定ステップにおいて、
予め、オーバレイネットワークのどのオーバレイノード間に論理リンクが張られているかを示すトポロジが決められているとき、
前記オーバレイノード間に張られたオーバレイリンクの遅延時間、パケット損失率、利用可能帯域のいずれか、またはその組み合わせからなるメトリックを一定周期毎に測定して前記管理サーバに通知すると共に、他のオーバレイノードまたは該管理サーバから取得したメトリックをトポロジ記憶手段に格納し、
前記オーバレイノードiとjの間におけるt番目の測定周期の該メトリックをｑt(Li,j)とし、前記コンテンツ配信元ノードを発信元オーバレイノードs、配信要求ユーザに最も近いオーバレイノードを着信先オーバレイノードdとし、該ノードsかつ該ノードd両方と論理的につながっているノードの集合を前記トポロジ記憶手段から読み出し、該ノード集合をVs,dとし、該ノードsと該ノードdの間に論理リンクが存在する場合は、
【数５６】
0005506640.tif 000038
該ノードsと該ノードdの間に論理リンクが存在しない場合は、
【数５７】
0005506640.tif 000039
とし、
【数５８】
0005506640.tif 000040
を中継ノード集合とし、
前記オーバレイノードsと前記オーバレイノードd間においてn番目のコンテンツ配信フローが発生したら、
【数５９】
0005506640.tif 000041
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質、
【数６０】
0005506640.tif 000042
は、直近のメトリック観測値ｑtを用いて計算される値）
により決定される確率に基づいて、中継ノード集合の中から中継ノードkを選択し、
前記コンテンツ配信元ノードsは前記中継ノードkへ一旦パケットを転送し、
前記中継ノードkにおいてパケットを着信先のオーバレイノードdに転送する
ことを特徴とするオーバレイネットワークを用いたコンテンツ配信方法。
【請求項２】
前記直近のメトリック観測値ｑtが利用可能帯域であれば、前記
【数６１】
0005506640.tif 000043
は、
【数６２】
0005506640.tif 000044
であり、前記ｑtが遅延時間であれば、
【数６３】
0005506640.tif 000045
であり、前記ｑtがパケット損失率であれば、
【数６４】
0005506640.tif 000046
である
請求項1記載のオーバレイネットワークを用いたコンテンツ配信方法。
【請求項３】
前記経路決定ステップにおいて、
あるコンテンツに関して、コンテンツを保持するノードが複数存在する場合には、
前記コンテンツ保持ノードｓと配信要求ユーザの最近傍ノードｄの間のメトリック
【数６５】
0005506640.tif 000047
（但し、qtは直近のメトリック観測値）
を該メトリックを最適にする中継ノードkを選択したときの値として計算し、
コンテンツ保持ノード集合をVdとし、その中からコンテンツ配信元ノードsを
【数６６】
0005506640.tif 000048
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質)
により求められた確率で選択する
請求項１記載のオーバレイネットワークを用いたコンテンツ配信方法。
【請求項４】
前記直近のメトリック観測値ｑtが利用可能帯域であれば、前記
【数６７】
0005506640.tif 000049
を最大にする中継ノードｋを選択し、
前記ｑtが遅延時間であれば、
【数６８】
0005506640.tif 000050
を最小にする中継ノードkを選択し、
前記ｑtがパケット損失率であれば、
【数６９】
0005506640.tif 000051
を最小にする中継ノードkを選択する
請求項３記載のオーバレイネットワークを用いたコンテンツ配信方法。
【請求項５】
前記コンテンツキャッシュステップにおいて、
予め人気度の高い上位コンテンツをキャッシュオーバレイノードに配置しておく、
請求項１に記載のオーバレイネットワークを用いたコンテンツ配信方法。
【請求項６】
IPネットワークに接続するいくつかのオーバレイノードによって構築される論理網であるオーバレイネットワークを構成し、オーバレイノードのうち、コンテンツキャッシュ機能を有するノードをキャッシュオーバレイノード、全てのコンテンツを保持するノードであるオリジナルノード及び管理サーバからなるオーバレイネットワークを用いたコンテンツ配信システムであって、
前記管理サーバは、
キャッシュオーバレイノードと該ノードが保持するコンテンツを対応付けて保持するコンテンツ保持リスト記憶手段と、
オーバレイノードの位置情報管理するオーバレイノード位置記憶手段と、
配信要求ユーザ装置からコンテンツmの要求を取得すると、前記コンテンツ保持リスト記憶手段を参照して、該コンテンツを保持するノードを探索するノード探索手段と、
前記ノード探索手段で探索されたノードの中でユーザとのホップ数（中継ルータ数）が最も小さいノードを、前記オーバレイノード位置記憶手段を参照してコンテンツ配信元ノードとして選択し、前記オーバレイノードに通知するノード選択手段と、
を有し、
前記オーバレイノードは、
前記コンテンツ配信元ノードと前記配信要求ユーザ装置の間の経路を決定する経路決定手段と、
決定された経路に従ってコンテンツを配信するコンテンツ配信手段と、
コンテンツ配信経路上に、キャッシュオーバレイノードが存在すれば、そこに該コンテンツをキャッシュするコンテンツキャッシュ手段と、
を有し、
前記オーバレイノードは、
予め、オーバレイネットワークのどのオーバレイノード間に論理リンクが張られているかを示すトポロジを格納したトポロジ記憶手段と、
前記オーバレイノード間に張られたオーバレイリンクの遅延時間、パケット損失率、利用可能帯域のいずれか、またはその組み合わせからなるメトリックを一定周期毎に測定して前記管理サーバに通知すると共に、他のオーバレイノードまたは該管理サーバから取得したメトリックをトポロジ記憶手段に格納するトポロジ形成管理手段と、を有し、
前記経路決定手段は、
前記トポロジ記憶手段からオーバレイノードiとjの間におけるt番目の測定周期の該メトリックｑt(Li,j)とノードの集合を読み出し、コンテンツ配信元ノードを発信元オーバレイノードs、配信要求ユーザに最も近いオーバレイノードを着信先オーバレイノードdとし、該ノードsかつ該ノードd両方と論理的につながっているノードの集合をVs,dとし、該ノードsと該ノードdの間に論理リンクが存在する場合は、
【数７０】
0005506640.tif 000052
該ノードsと該ノードdの間に論理リンクが存在しない場合は、
【数７１】
0005506640.tif 000053
とし、
【数７２】
0005506640.tif 000054
を中継ノード集合とし、
前記オーバレイノードsと前記オーバレイノードd間においてn番目のコンテンツ配信フローが発生したら、
【数７３】
0005506640.tif 000055
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質、
【数７４】
0005506640.tif 000056
は、直近のメトリック観測値ｑtを用いて計算される値）
により決定される確率に基づいて、中継ノード集合の中から中継ノードkを選択する手段を含む、
ことを特徴とするオーバレイネットワークを用いたコンテンツ配信システム。
【請求項７】
前記オーバレイノードの前記経路決定手段は、
あるコンテンツに関して、コンテンツ保持ノードが複数存在する場合には、
前記コンテンツ保持ノードｓと配信要求ユーザの最近傍ノードｄの間のメトリック
【数７５】
0005506640.tif 000057
を該メトリックを最適にする中継ノードkを選択したときの値として計算し、
コンテンツ保持ノード集合をVdとし，その中からコンテンツ配信元ノードsを
【数７６】
0005506640.tif 000058
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質)
により求められた確率で選択する手段を含む
請求項６記載のオーバレイネットワークを用いたコンテンツ配信システム。
【請求項８】
前記コンテンツキャッシュ手段は、
予め人気度の高い上位コンテンツをキャッシュオーバレイノードに配置しておく、
請求項６に記載のオーバレイネットワークを用いたコンテンツ配信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットにおけるコンテンツ配信時のエンドエンド通信品質の向上とネットワークへの負荷を軽減させるコンテンツ配信方法及びシステムに係り、特にIＰネットワーク上に論理的に形成されたオーバレイネットワークを用いて、エンド・ツー・エンドの通信品質を効率的に向上させてネットワークの負荷を軽減させるコンテンツ配信方法及びシステムに関する。
【背景技術】
【０００２】
IPネットワークを代表するインターネットは、多様なアプリケーションの収容を可能とすべく発展・普及してきており、その一方で、QoS（Quality of Service）に対する要求も高まってきている。
【０００３】
これに伴い、エンド・ツー・エンドでの輻輳を回避し、品質を向上するための技術（「エンド・ツー・エンドQoS管理技術」）をインターネット上で実現することが重要な課題となっている。しかしながら、このような技術を実現する上では、以下に示す問題点がある。
【０００４】
（１）インターネットは既に社会的インフラ化しており、既存のネットワーク構造を大きく変更するような、ネットワークレイヤでの新たな機能拡張は困難である。
【０００５】
（２）インターネットは管理主体の異なる複数のAS（Autonomous System）によって形成されており、全てのASに対して一斉に新たな機能を拡張することは困難である。
【０００６】
こうした中、下位のネットワークレイヤを変更することなくエンド・ツー・エンドQoSの向上を可能とする有力な技術として、例えば非特許文献１に記載の、オーバレイネットワークによるQoS管理技術が注目されている。オーバレイネットワークとは、例えば非特許文献２においても記載のように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【０００７】
このようなオーバレイネットワークによるQoS管理の基本的な概念を図１２に例示する。図１２において、ｘからｙに向けて、破線矢印で表わされる経路にトラヒックが流れているとする。また、この経路上には輻輳しているIPルータが存在しており、その結果として、ｘ，ｙ間のQoSが低下しているとする。このとき、オーバレイノードａ，ｂ，ｃで形成されるオーバレイネットワークを用いて、実線矢印で表される経路（ｘ→オーバレイノードa→オーバレイノードb→オーバレイノードc→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。実際、非特許文献３，４，５等では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。このように、輻輳を回避してエンドエンド品質を改善することが期待される。
【０００８】
また、一方で、非特許文献６のように，コンテンツをネットワーク内部にキャッシュすることで、冗長なトラヒック転送を削減するというアプローチが存在する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】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.
【非特許文献５】平岡，長谷川，村田，``遅延および帯域情報を用いたオーバレイルーティングの有効性評価,'' 信学技報CQ2007-18, 2007年7月．
【非特許文献６】N. Kamiyama, T. Mori, R. Kawahara, S. Harada, and H. Hasegawa,"ISP-Operated CDN," Global Internet Symposium, Apr. 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来のオーバレイネットワークによるQoS管理（非特許文献１〜５）では、例えば複数のユーザから同一コンテンツへの配信要求があったとしても、配信元サーバから各々のユーザへ同じコンテンツからのパケットが転送されるため、冗長なパケット転送となり、輻輳を助長する可能性があるという問題があった。
【００１１】
また、コンテンツをネットワーク内部にキャッシュすることで、冗長なトラヒック転送を削減するという方法（非特許文献６）では、コンテンツ配信元サーバから要求ユーザまでの配信経路までを制御することはできないため、例えば特定のエリアから特定のサーバへ要求が集中すると、ネットワーク内で輻輳が発生し，エンドエンド品質が劣化する可能性がある、という問題があった。
【００１２】
本発明は、上記の点に鑑みなされたもので、IＰネットワーク上に論理的に形成されたオーバレイネットワークを用いて、エンド・ツー・エンドの通信品質を効率的に向上させてネットワークの負荷を軽減することを可能にするコンテンツ配信方法およびコンテンツ配信システムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するため、本発明（請求項１）は、IPネットワークに接続するいくつかのオーバレイノードによって構築される論理網であるオーバレイネットワークを構成し、該オーバレイノードのうち、コンテンツキャッシュ機能を有するノードであるキャッシュオーバレイノード、全てのコンテンツを保持するノードであるオリジナルノード及び管理サーバからなるシステムにおけるオーバレイネットワークを用いたコンテンツ配信方法であって、
前記管理サーバは、
配信要求ユーザ装置からコンテンツmの要求を取得すると、キャッシュオーバレイノードと該ノードが保持するコンテンツを対応付けて保持するコンテンツ保持リスト記憶手段を参照して、オリジナルノード及びキャッシュオーバレイノードの中から、該コンテンツを保持するノードを探索し、その中でユーザとのホップ数（中継ルータ数）が最も小さいノードを、オーバレイノードの位置情報を管理するオーバレイノード位置記憶手段を参照してコンテンツ配信元ノードとして選択し、前記オーバレイノードに通知するノード選択ステップを行い、
前記オーバレイノードは、
前記コンテンツ配信元ノードと前記配信要求ユーザの間の経路を決定する経路決定ステップと、
決定された経路に従ってコンテンツを配信するコンテンツ配信ステップと、
コンテンツ配信経路上に、キャッシュオーバレイノードが存在すれば、そこに該コンテンツをキャッシュするコンテンツキャッシュステップと、
を行い、
前記オーバレイノードにおける前記経路決定ステップにおいて、
予め、オーバレイネットワークのどのオーバレイノード間に論理リンクが張られているかを示すトポロジが決められているとき、
前記オーバレイノード間に張られたオーバレイリンクの遅延時間、パケット損失率、利用可能帯域のいずれか、またはその組み合わせからなるメトリックを一定周期毎に測定して前記管理サーバに通知すると共に、他のオーバレイノードまたは該管理サーバから取得したメトリックをトポロジ記憶手段に格納し、
前記オーバレイノードiとjの間におけるt番目の測定周期の該メトリックをｑt(Li,j)とし、前記コンテンツ配信元ノードを発信元オーバレイノードs、配信要求ユーザに最も近いオーバレイノードを着信先オーバレイノードdとし、該ノードsかつ該ノードd両方と論理的につながっているノードの集合を前記トポロジ記憶手段から読み出し、該ノード集合をVs,dとし、該ノードsと該ノードdの間に論理リンクが存在する場合は、
【数７７】
0005506640.tif 000002
該ノードsと該ノードdの間に論理リンクが存在しない場合は、
【数７８】
0005506640.tif 000003
とし、
【数７９】
0005506640.tif 000004
を中継ノード集合とし、
前記オーバレイノードsと前記オーバレイノードd間においてn番目のコンテンツ配信フローが発生したら、
【数８０】
0005506640.tif 000005
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質、
【数８１】
0005506640.tif 000006
は、直近のメトリック観測値ｑtを用いて計算される値）
により決定される確率に基づいて、中継ノード集合の中から中継ノードkを選択し、
前記コンテンツ配信元ノードsは前記中継ノードkへ一旦パケットを転送し、
前記中継ノードkにおいてパケットを着信先のオーバレイノードdに転送する。
【００２０】
また、本発明（請求項２）は、請求項１において、前記直近のメトリック観測値ｑtが利用可能帯域であれば、前記
【数８２】
0005506640.tif 000007
は、
【００２１】
【数６】
0005506640.tif 000008
は、
【００２２】
【数８３】
0005506640.tif 000009
であり、前記ｑtが遅延時間であれば、
【００２３】
【数８４】
0005506640.tif 000010
であり、前記ｑtがパケット損失率であれば、
【００２４】
【数８５】
0005506640.tif 000011
である。
【００２５】
また、本発明（請求項３）は、請求項１の前記経路決定ステップにおいて、
あるコンテンツに関して、コンテンツを保持するノードが複数存在する場合には、
前記コンテンツ保持ノードｓと配信要求ユーザの最近傍ノードｄの間のメトリック
【００２６】
【数８６】
0005506640.tif 000012
（但し、qtは直近のメトリック観測値）
を該メトリックを最適にする中継ノードkを選択したときの値として計算し、
コンテンツ保持ノード集合をVdとし、その中からコンテンツ配信元ノードsを
【００２７】
【数８７】
0005506640.tif 000013
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質)
により求められた確率で選択する。
【００２８】
また、本発明（請求項４）は、請求項３において、前記直近のメトリック観測値ｑtが利用可能帯域であれば、前記
【００２９】
【数８８】
0005506640.tif 000014
を最大にする中継ノードｋを選択し、
前記ｑtが遅延時間であれば、
【００３０】
【数８９】
0005506640.tif 000015
を最小にする中継ノードkを選択し、
前記ｑtがパケット損失率であれば、
【００３１】
【数９０】
0005506640.tif 000016
を最小にする中継ノードkを選択する。
【００３２】
また、本発明（請求項５）は、請求項１の前記コンテンツキャッシュステップにおいて、
予め人気度の高い上位コンテンツをキャッシュオーバレイノードに配置しておく。
【００３３】
また、本発明（請求項６）は、IPネットワークに接続するいくつかのオーバレイノードによって構築される論理網であるオーバレイネットワークを構成し、オーバレイノードのうち、コンテンツキャッシュ機能を有するノードをキャッシュオーバレイノード、全てのコンテンツを保持するノードであるオリジナルノード及び管理サーバからなるオーバレイネットワークを用いたコンテンツ配信システムであって、
前記管理サーバは、
キャッシュオーバレイノードと該ノードが保持するコンテンツを対応付けて保持するコンテンツ保持リスト記憶手段と、
オーバレイノードの位置情報管理するオーバレイノード位置記憶手段と、
配信要求ユーザ装置からコンテンツmの要求を取得すると、前記コンテンツ保持リスト記憶手段を参照して、該コンテンツを保持するノードを探索するノード探索手段と、
前記ノード探索手段で探索されたノードの中でユーザとのホップ数（中継ルータ数）が最も小さいノードを、前記オーバレイノード位置記憶手段を参照してコンテンツ配信元ノードとして選択し、前記オーバレイノードに通知するノード選択手段と、
を有し、
前記オーバレイノードは、
前記コンテンツ配信元ノードと前記配信要求ユーザ装置の間の経路を決定する経路決定手段と、
決定された経路に従ってコンテンツを配信するコンテンツ配信手段と、
コンテンツ配信経路上に、キャッシュオーバレイノードが存在すれば、そこに該コンテンツをキャッシュするコンテンツキャッシュ手段と、
を有し、
前記オーバレイノードは、
予め、オーバレイネットワークのどのオーバレイノード間に論理リンクが張られているかを示すトポロジを格納したトポロジ記憶手段と、
前記オーバレイノード間に張られたオーバレイリンクの遅延時間、パケット損失率、利用可能帯域のいずれか、またはその組み合わせからなるメトリックを一定周期毎に測定して前記管理サーバに通知すると共に、他のオーバレイノードまたは該管理サーバから取得したメトリックをトポロジ記憶手段に格納するトポロジ形成管理手段と、を有し、
前記経路決定手段は、
前記トポロジ記憶手段からオーバレイノードiとjの間におけるt番目の測定周期の該メトリックｑt(Li,j)とノードの集合を読み出し、コンテンツ配信元ノードを発信元オーバレイノードs、配信要求ユーザに最も近いオーバレイノードを着信先オーバレイノードdとし、該ノードsかつ該ノードd両方と論理的につながっているノードの集合をVs,dとし、該ノードsと該ノードdの間に論理リンクが存在する場合は、
【数９１】
0005506640.tif 000017
該ノードsと該ノードdの間に論理リンクが存在しない場合は、
【数９２】
0005506640.tif 000018
とし、
【数９３】
0005506640.tif 000019
を中継ノード集合とし、
前記オーバレイノードsと前記オーバレイノードd間においてn番目のコンテンツ配信フローが発生したら、
【数９４】
0005506640.tif 000020
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質、
【数９５】
0005506640.tif 000021
は、直近のメトリック観測値ｑtを用いて計算される値）
により決定される確率に基づいて、中継ノード集合の中から中継ノードkを選択する手段を含む。
【００４０】
また、本発明（請求項７）は、請求項６の前記オーバレイノードの前記経路決定手段は、
あるコンテンツに関して、コンテンツ保持ノードが複数存在する場合には、
前記コンテンツ保持ノードｓと配信要求ユーザの最近傍ノードｄの間のメトリック
【００４１】
【数９６】
0005506640.tif 000022
を該メトリックを最適にする中継ノードkを選択したときの値として計算し、
コンテンツ保持ノード集合をVdとし，その中からコンテンツ配信元ノードsを
【００４２】
【数９７】
0005506640.tif 000023
（但し、nはフロー番号、βは予め定める定数であり遅延時間およびパケット損失率の場合は0＜β＜１、利用可能帯域の場合はβ＞１であり、kは選択された中継ノード、qt(Ls,k）はノードｓと中継ノードk間のt番目の測定周期の品質、qt(Lk,d）は中継ノードkとノードd間のt番目の測定周期の品質)
により求められた確率で選択する手段を含む。
【００４３】
また、本発明（請求項８）は、請求項６の前記コンテンツキャッシュ手段は、
予め人気度の高い上位コンテンツをキャッシュオーバレイノードに配置しておく。
【発明の効果】
【００４４】
上記にように、本発明によれば、ネットワーク内でコンテンツをキャッシュすることで冗長なトラヒックを削減しつつ、オーバレイネットワークで経路を制御することでエンド・ツー・エンドでの通信品質を向上させることができる。
【図面の簡単な説明】
【００４５】
【図１】本発明の第１の実施の形態におけるシステム構成図である。
【図２】本発明の第１の実施の形態における管理サーバの構成図である。
【図３】本発明の第１の実施の形態におけるオーバレイノードの構成図である。
【図４】本発明の第１の実施の形態におけるエンドホストの構成図である。
【図５】本発明の第１の実施の形態におけるパケット中継処理のフローチャートである。
【図６】本発明の有効性を確認するのに用いたネットワークである。
【図７】本発明のAllegianceネットワークトポロジでの評価結果である。
【図８】本発明のAt Homeネットワークトポロジでの評価結果である。
【図９】本発明のCable&Wirelessトポロジでの評価結果である。
【図１０】本発明のCIASネットワークトポロジでの評価結果である。
【図１１】本発明のSavvisネットワークトポロジでの評価結果である。
【図１２】オーバレイネットワークによる経路制御の概念を説明するための図である。
【発明を実施するための形態】
【００４６】
以下図面と共に、本発明の実施の形態を説明する。
【００４７】
［第１の実施の形態］
本発明におけるシステムは、図１に示すように、オーバレイネットワークと物理ネットワーク（IPネットワーク）の構成を持ち、オーバレイネットワークは、オーバレイノード（このうちいくつかはキャッシュオーバレイノード）２、配信要求をするエンドホスト３、管理サーバ１、により構成される。管理サーバ１の構成図を図２に、オーバレイノード２の構成図を図３に、エンドホスト３の構成図を図４に示す。
【００４８】
本実施の形態では、あるコンテンツに関して、コンテンツを保持しているオーバレイノード（コンテンツ保持ノード）が複数存在する場合、配信要求ユーザとのホップ数が最小のノードを配信元ノードとして選択する例を説明する。
【００４９】
図２に示す管理サーバ１は、トラヒック品質情報管理部１１、コンテンツ保持リスト管理部１２、オーバレイノード位置管理部１３から構成される。
【００５０】
トラヒック品質情報管理部１１では、一定周期毎にオーバレイノード間で測定された品質を管理している。オーバレイノードiとjの間におけるt番目の測定周期の品質をｑt(Li,j)として記憶手段（図示せず）に格納し管理している。品質メトリックは、遅延時間、パケット損失率、利用可能帯域のいずれか、またはその組み合わせで定義される。
【００５１】
また、管理サーバ１内のコンテンツ保持リスト管理部１２では、どのキャッシュオーバレイノードがどのコンテンツを保有しているかを対応付けて記憶手段（図示せず）に格納し、管理している。エンドホスト３からのコンテンツ配信要求があった際には、記憶手段（図示せず）から該当するコンテンツを保持するキャッシュオーバレイノードがどれかを探し、コンテンツを保持するキャッシュオーバレイノードが複数存在する場合には、オーバレイノード位置管理部１３に問い合わせて、そのエンドホスト３に最も近いオーバレイノードを調べる。
【００５２】
具体的には、例えば、予めオーバレイノード位置管理部１３の記憶手段（図示せず）にIPアドレスをエリアにマッピングする情報を格納しておき、エンドホスト３のIPアドレスから該当するエリアを調べ、そのエリアに属するオーバレイノードを調べる。次に、該当するコンテンツを保持するキャッシュオーバレイノード２のうち、その最近傍オーバレイノードからみて最も近い（ルータホップ数が最も少ない）キャッシュオーバレイノードを選択する。その結果、つまり、配信要求エンドホスト３のアドレスを、エンドホスト３からみて最近傍オーバレイノード（ｄ）と、キャッシュオーバレイノード（ｓ）に通知する。
【００５３】
オーバレイノード２は、図３に示すように、トポロジ形成管理部２１、経路計算部２２、パケット転送部２３、コンテンツキャッシュ部２４から構成される。
【００５４】
トポロジ形成管理部２１では、オーバレイノードの接続関係を記憶手段（図示せず）に格納している。トポロジの決定は、ネットワーク管理者が集中的に決定してもよいし、オーバレイノード間で自律的にメッセージを交換して接続するか否かを決定してもよい。また、トポロジ形成管理部２１では、一定周期毎に隣接ノードと間の品質を測定しておき、その結果を管理サーバ１に通知する。管理サーバ１からは、自身の隣接ノード間以外のオーバレイノード間の品質を受け取り、当該トポロジ形成管理部２１内の記憶手段（図示せず）に格納する。
【００５５】
経路計算部２２では、エンドホスト３からコンテンツ配信の要求を受信したら（つまり自身がコンテンツ配信元ノードsとして指名されたら）、トポロジ形成管理部２１内の記憶手段（図示せず）を参照して、配信要求のあったエンドホスト３の最近傍に位置する着信先ノードdまでの経路を決定する。
【００５６】
図５は、本発明の第１の実施の形態におけるパケット中継処理のフローチャートである。
【００５７】
以下に具体的に説明する。
【００５８】
まず、経路計算部２２は、トポロジ形成管理部２１の記憶手段（図示せず）から、ノードｓかつノードd両方と論理的につながっているノードの集合を読み出し、それをVs,dとする。また、sとdの間に論理リンクが存在する場合は
【００５９】
【数２２】
0005506640.tif 000024
ノードｓとノードｄの間に論理リンクが存在しない場合は、
【００６０】
【数２３】
0005506640.tif 000025
とし、
【００６１】
【数９８】
0005506640.tif 000026
を中継ノード集合とする。
【００６２】
次に、ノードｓ−ｄ間でのコンテンツ配信フロー（n番目のフローだったとする）に対して、以下で決定される確率（ステップ１０２）で、中継ノード集合の中から，中継ノードkを選択する（ステップ１０３）。
【００６３】
【数２５】
0005506640.tif 000027
なお、ここで、
【００６４】
【数９９】
0005506640.tif 000028
は、直近のメトリック観測値ｑtを用いて計算される値であり、ｑtが利用可能領域であれば、
【００６５】
【数１００】
0005506640.tif 000029
であり、ｑtがパケット損失率であれば、
【００６６】
【数１０１】
0005506640.tif 000030
とする。中継ノードとして選択されたノードkをパケット転送部２３に通知する（ステップ１０４）。
【００６７】
【数２９】
0005506640.tif 000031
とする。中継ノードとして選択されたノードkをパケット転送部２３に通知する（ステップ１０４）。
【００６８】
パケット転送部２３では、配信要求元のコンテンツをコンテンツキャッシュ部２４から読み出し、コンテンツ配信フローを生成する。具体的には、コンテンツ配信フローのパケットの宛先アドレスとして配信要求のあったエンドホスト３のアドレスに設定する。またそのパケットをカプセル化し、カプセル化した後のパケットヘッダの宛先アドレスとして、経路計算部２２で指定されたノードkのアドレスを設定して、ノードkへ向けてパケットを転送する（ステップ１０５）。
【００６９】
一方、当該オーバレイノード２が中継ノードとして動作する場合、つまり、他のコンテンツ配信元ノード（オーバレイノード）からカプセル化されたパケットが転送されてきた場合には（ステップ１０６）、カプセルをはずした中にあるパケットの宛先アドレスを読み出し、その宛先（＝配信要求してきたエンドホスト）へ向けてパケットを転送する（ステップ１０７）。その際、そのパケットを記憶手段（図示せず）に蓄積していき、コンテンツ復元のためのパケットが全て到着したら、コンテンツを復元し、コンテンツキャッシュ部２４に該コンテンツをキャッシュする（ステップ１０８）。また、その旨を、管理サーバ１へ通知する。
【００７０】
次に、エンドホスト３について図４に基づいて説明する。
【００７１】
エンドホスト３は、コンテンツ要求部３１とコンテンツ受信部３２から構成される。
【００７２】
コンテンツ要求部３１は、サービスを受ける際、すなわちあるコンテンツの受信を要求する際に、管理サーバ１へコンテンツ配信を要求し、コンテンツ受信部３２が、管理サーバ１からのコンテンツ配信元となるキャッシュオーバレイノードsならびに、最近傍に位置するオーバレイノードdの通知を受ける。その情報を、オーバレイノードsに通知し、sからのコンテンツ配信フローのパケットを受信する。
【００７３】
［第２の実施の形態］
第１の実施の形態では、あるコンテンツに関して、コンテンツ保持ノードが複数存在する場合、配信要求ユーザとのホップ数が最小のノードを配信元ノードとして選択していたが、本実施の形態では、コンテンツ保持ノードと配信要求ユーザの最近傍ノードの間のメトリックをそのメトリックを最適にする中継ノードを選択したときの値として計算し、コンテンツ保持ノード集合の中からコンテンツ配信元ノードを選択する。
【００７４】
なお、本実施の形態においても、管理サーバ、オーバレイノード、エンドホストの構成は第1の実施の形態と同様である。
【００７５】
以下では、予めどのオーバレイノード間に論理リンクが張られているか等のトポロジが決められているものとする。また、以下に示すメトリックとは、オーバレイノード間に張られたオーバレイリンクの遅延時間、パケット損失率、利用可能帯域のいずれか、または、その組み合わせを指す。当該メトリックは一定周期毎に測定され、オーバレイノード２内のトポロジ形成管理部２１内の記憶手段（図示せず）に格納されているものとする。
【００７６】
まず、オーバレイノード２の経路計算部２２は、コンテンツ保持ノードsと配信要求ユーザの最近傍ノードdの間のｔ番目のメトリック
【００７７】
【数１０２】
0005506640.tif 000032
をそのメトリックを最適にする中継ノードkを選択したときの値として計算する。ｑtが利用可能帯域であれば、
【００７８】
【数１０３】
0005506640.tif 000033
を最大にする中継ノードkを選択し、ｑtが遅延時間であれば、
【００７９】
【数１０４】
0005506640.tif 000034
を最小にするkを選択し、ｑtがパケット損失率であれば
【００８０】
【数１０５】
0005506640.tif 000035
を最小にするkを選択する。
【００８１】
次に、コンテンツ保持ノード集合をVdとし、その中からコンテンツ配信元ノードsを以下の確率で選択する。
【００８２】
【数３４】
0005506640.tif 000036
その他の処理については第1の実施の形態と同様であるので、その説明を省略する。
【００８３】
［第３の実施の形態］
第１の実施の形態では、コンテンツを配信経路上のノードにキャッシュしたが、本実施の形態では、予め人気度の高い上位コンテンツをキャッシュオーバレイノード２に配置する。その上で、前述の第１または第２の実施の形態の手順によりコンテンツを配信する。
【００８４】
その他の構成及び処理については第1の実施の形態と同様であるので、その説明を省略する。
【００８５】
上記のように本発明によれば、 IＰネットワーク上に論理的に形成されたオーバレイネットワークを用いて、エンド・ツー・エンドの通信品質を効率的に向上させてネットワークの負荷を軽減することを可能にするコンテンツ配信方法およびコンテンツ配信システムを提供することが可能となる。
【００８６】
図６に示す５つのネットワークにおいて、本発明を動作させるシミュレーションを行った結果を示す。なお、同図における（ｘ，ｙ）は、（ノード数，リンク数）を表す。また、これらのネットワークトポロジは、「http://www.caida.org/tools/visualization/mapnet/Data/」より入手可能である。コンテンツを１０００種類用意し、全てのコンテンツを持つオリジナルサーバをネットワーク上のノード（ルータ）に１つ配置する。また、ネットワーク上の各ノードにオーバレイノードが一つ配置されているとする。コンテンツはTCPで転送されている場合を想定する。
【００８７】
このときの第１の実施の形態を適用したときの結果を図７に示す。なお、この結果は図６の５つのトポロジのうち、AT(Allegiance Telecom)の場合の結果である。図７（ａ）のグラフは、ネットワークへの負荷（コンテンツ配信要求呼数に相当）を変えたときの、個々のコンテンツ配信フローのフロー毎のスループットを集計し、その5パーセンタイルをプロットした結果となる。この図で、"Proposed"は本発明を適用した場合、"NoControl"とは、第１の実施の形態の経路制御を実施しなかった場合、"Selfish"は第１の実施の形態の経路制御の代わりに、そのときのスループットが最大となる経路を各ノードペアが自律分散的に選択した場合、"NoCache"はオリジナルサーバからのみ配信した場合、である。これより本発明"Proposed"が最もスループットがよいことが分かる。
【００８８】
また、図７（ｂ）のグラフは、リンク当りの負荷の平均をプロットしている。この値が小さいほど、ネットワークへの負荷が低減化できていることになる。これより、ネットワークの負荷は提案方式が小さくできていることがわかる。なお、"NoControl"は負荷が一番低いのは、"NoControl"では最小ホップの経路を常に選択するため、ネットワークへの負荷という観点からは負荷を最小とすることになる。但し、特定のリンクへ負荷が集中する可能性があるため、その結果、図８上段のようにスループットが低下してしまう。
【００８９】
図８から図１１に、他のネットワークでの評価結果も示す。これより、いずれのネットワークでも、本発明"Proposed"が最もスループットがよいことが分かる。
【００９０】
また別の評価として、UDP的にストリーム配信した場合についても評価した。このときの各トポロジでの品質劣化度（目標遅延時間内にコンテンツ内の各パケットを転送できなった割合[%]）は以下の表のようになる。これより、ほとんどの場合、提案では品質劣化度を小さくできていることがわかる。
【００９１】
【表１】
0005506640.tif 000037
上記の図２、図３、図４に示す管理サーバ１、オーバレイノード２、エンドホスト３の各動作をプログラムとして構築し、管理サーバ、オーバレイノード、エンドホストとして利用されるコンピュータにインストールして実行させる、またはネットワークを介して流通させることが可能である。
【００９２】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９３】
１  管理サーバ
２  オーバレイノード
３  配信要求エンドホスト
１１  トラヒック品質情報管理部
１２  コンテンツ保持リスト管理部
１３  オーバレイノード位置管理部
２１  トポロジ形成管理部
２２  経路計算部
２３  パケット転送部
２４  コンテンツキャッシュ部
３１  コンテンツ要求部
３２  コンテンツ受信部
【図１】
0005506640.tif 000059
【図２】
0005506640.tif 000060
【図３】
0005506640.tif 000061
【図４】
0005506640.tif 000062
【図５】
0005506640.tif 000063
【図６】
0005506640.tif 000064
【図７】
0005506640.tif 000065
【図８】
0005506640.tif 000066
【図９】
0005506640.tif 000067
【図１０】
0005506640.tif 000068
【図１１】
0005506640.tif 000069
【図１２】
0005506640.tif 000070