情報中心ネットワークにおけるポテンシャルに基づくルーティング方法およびそれを用いたネットワーク
【課題】情報中心ネットワークにおけるルーティング問題をポテンシャルに基づくルーティング方法を提供する。
【解決手段】ユーザの通信端末と、それを接続するネットワークと、そのネットワークの通信路の接続を切り換えるノードの複数と、そのノード間を接続する通信路の複数を備えるもので、そのノードは、ユーザーがネットワークを通じてダウンロードする情報を蓄積するネットワークを前提として、ノードを座標点とする離散空間にポテンシャル値を与えてポテンシャル面を形成し、このポテンシャル面の極小点または極大点を探索することでユーザーの望むコンテンツの所在を見出し、その探索履歴でユーザーから目標ノードまでの通信路を設定する。また、各ノードに与えるポテンシャル値は、コンテンツを有するノードからのネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては、予め決められた値に収束するものとする。
【解決手段】ユーザの通信端末と、それを接続するネットワークと、そのネットワークの通信路の接続を切り換えるノードの複数と、そのノード間を接続する通信路の複数を備えるもので、そのノードは、ユーザーがネットワークを通じてダウンロードする情報を蓄積するネットワークを前提として、ノードを座標点とする離散空間にポテンシャル値を与えてポテンシャル面を形成し、このポテンシャル面の極小点または極大点を探索することでユーザーの望むコンテンツの所在を見出し、その探索履歴でユーザーから目標ノードまでの通信路を設定する。また、各ノードに与えるポテンシャル値は、コンテンツを有するノードからのネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては、予め決められた値に収束するものとする。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、希望のデータの、名前や識別符号に基づいてルーティング（経路設定）される情報中心ネットワーク（ＩＣＮ：Information Centric Network）におけるポテンシャルに基づくルーティング方法およびそれを用いたネットワークに関している。
【背景技術】
【０００２】
ＩＣＮ（非特許文献１から３参照）においては、ユーザーのリクエスト（要求）は、ＩＰ（インターネットプロトコル）アドレスで表現された位置よりもむしろ求められるデータの名前に基づいて通信経路が設定される。この性質のため、動きつつあるデバイスにＩＰアドレスを割り当てるという問題、あるいは、増加しつつあるモバイルデバイスのＩＰアドレスを管理する問題は自然に解消されるので、モビリティ（機動性）問題やマルチホーミング問題（非特許文献４参照）として知られている問題とは無縁である。さらに、コンテンツ（一連の情報）をローカルにキャッシュ（蓄積）することでＩＣＮが低遅延のストレージ空間をサポートするので、ポピュラーコンテンツ（一般情報）の場合に起こる送り手側の隘路（ボトルネック）を引き起こさない。
【０００３】
上記の利点にもかかわらず、この有望な構成を進展させるためにいくつかの問題に注目する必要がある。その１つは、ネットワークに分散した複数のコンテンツから１つを賢く選択するか指定するかをどのように行うか、という問題である（この問題はＩＣＮにおけるルーティング問題として知られている）。
【０００４】
本発明では、上記のゴールを実現するために、ポテンシャルに基づくルーティング（ＰＢＲ：Potential Based Routing）というアイデアを採用する。これは、当初 Chalermark et al. （非特許文献５）によって導入されたもので、方向付けられた拡散法(directed diffusion method)と呼ばれたものである。ポテンシャルに基づくルーティングアルゴリズムは、注目するアプリケーションに対応したスカラー値をネットワーク要素ごとに割り当ててポテンシャル場を形成する。それから、クエリー（処理要求）やトラフィック（情報）が、ポテンシャル値を最小化する方向に転送される。
【０００５】
図１は、非特許文献１に基づく図であり、（ａ）はＰＢＲの場合で、ポテンシャル場を示す図である。谷があるものと想像されたい。ボールを落とすと、ボールはその場の底まで落ち続ける。同様に、その場の中から出たユーザーの要求は、自然にその場の底に導かれるが、その底は要求されたコンテンツの置き場所を示す。（ｂ）は、ＥＰＢＲ（Extended PBR）の場合で、この図に示すような有限の範囲に限られるポテンシャル場である場合には、ボールをランダムに転がし続ける。これは、コンテンツの置き場所を示す１つの穴に導かれるまで行う。
【０００６】
従来、ＩＣＮルーティングアルゴリズムは、２つのカテゴリーに分類されてきた。つまり、構造化されていないルーティングと構造化されたルーティングとであり、これはルーティング表を維持する際にシステマティックな構造があるかどうかによっている。
【０００７】
例えば、ＮＤＮ（Named Data Networking、非特許文献３）は前者に属し、集約コンテンツの識別子への特別な命名法を示唆しているが、その識別子は、ＩＰルーティングにおけるプレフィクス集約と同様なものである。ＩＰルーティングにおいては、コンテンツ識別子の集約によって拡張可能性問題の緩和するが、コンテンツ名の単一性を犠牲にしている。高い利便性のルーティングは、一般にネットワークの複数の識別子をもったコンテンツを利用して構築されているが、実現が難しい。
【０００８】
他方、ＤＯＮＡ（Data-Oriented Network Architecture、非特許文献２）は後者に属するが、エニーキャスト（anycast）に基づくルーティングを採用している。非特許文献２の著者達の主張では、彼らの方法は高い利便性を有し、これはユーザーに信頼性と低いレイテンシ（遅延時間）をもたらす。これは近くのコンテンツへのプロキシミティに基づくルーティングによるものである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】D. R. Cheriton and M. Gritter, TRIAD: a Scalable Deployable NAT-based Internet Architecture, “Distributed Systems Group, StanfordUniversity,” Technical Report, Jan 2000.
【非特許文献２】T. Koponen, A. Ermolinskiy, M. Chawla, K. H. Kim, I. Stoica, B. gon Chun, and S. Shenker, “A data-oriented (and beyond) network architecture,” in Proceedings of the 2007 conference on Applications,technologies, architectures, and protocols for computer communications (SIGCOMM'07), Kyoto, Japan, Aug 2007.
【非特許文献３】Named Data Networking. [Online]. Available:http://www.named-data.net/
【非特許文献４】J. Choi, J. Han, E. Cho, T. Kwon, and Y. Choi, “A Survey on content-oriented networking for efficient content delivery,” Communications Magazine, IEEE, vol. 49, pp. 121-127, 2011.
【非特許文献５】R. G. C. Intanagonwiwat and D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” in Proceedings of the sixth annual international conference on Mobile computing and networking, Boston, MA USA, Aug 2000.
【非特許文献６】S. Jin and L. Wang, “Content and service replication strategies in multi-hop wireless mesh networks,” in Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, Montreal, Canada, October 2005.
【非特許文献７】P. Radoslavov, R. Govindan, and D. Estrin, “Topology-Informed Internet Replica Placement,” in Proceedings of Sixth International Workshop on Web Caching and Content Distribution, Boston, USA, June 2001.
【非特許文献８】L. QIU, V. N. PADMANABHAN, AND G. M. VOELKER, “ON THE PLACEMENT OF WEB SERVER REPLICAS,” IN PROCEEDINGS OF IEEE INFOCOM, ANCHORAGE, USA, APRIL 2001.
【非特許文献９】S. ARIANFAR, P. NIKANDER, AND J. OTT, “ON CONTENT-CENTRIC ROUTER DESIGN AND IMPLICATIONS,” IN PROCEEDINGS OF ACM REARCH 2010, PHILADELPHIA, USA, NOVEMBER 2010.
【非特許文献１０】M. Pathan and R. Buyya, “A Taxonomy of CDNs (Content Delivery Networks).” R. Buyya, M. Pathan, and A. Vakali (Eds.), Springer-Verlag, Germany, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記の様に、ＩＣＮにおいては、動きつつあるデバイスにＩＰアドレスを割り当てるという問題、あるいは、増加しつつあるモバイルデバイスのＩＰアドレスを管理する問題は、自然に解消されるので、モビリティ（機動性）問題やマルチホーミング問題とは無縁である。さらに、ポピュラーコンテンツでは送り手側の隘路（ボトルネック）が起こり易い、という問題が起きない。しかし、上記の様に、ＩＣＮにおけるルーティング問題がある。本発明は、このＩＣＮにおけるルーティング問題を取り扱う１つのアイデアを提案するものである。
【課題を解決するための手段】
【００１１】
本発明は、概略、情報を伝送する複数の通信経路（以下では単に、経路）と、上記経路によって互いに接続された複数のノード（結節点）と、上記ノードのいずれかに上記経路によって接続された複数の通信端末とを備え、上記ノードは、受信した情報の少なくとも1部を蓄積（キャッシュ）し、またその受信した情報の演算処理を行い、その演算結果に基づいて送信する経路を選択して情報を送信するものであり、上記通信端末は接続された経路に対して、処理要求（クエリ）を送信し、あるいは情報（トラフィック）の送受信をするネットワークにおいて、ネットワークの使用者は、上記通信端末に、例えば、希望のコンテンツをダウンロードするためのクエリを入力し、上記通信端末に上記コンテンツを表示するか、上記通信端末から出力するもである。
【００１２】
同一のコンテンツを有するノードが複数の場合、上記ネットワークの各ノードのポテンシャル値は、上記コンテンツを有するノードのそれぞれからのポテンシャル値への寄与の線形和であるとする。これによって、同一のコンテンツを有するノードから、ユーザにとって最も好条件のノードを選択することができるようになる。
【００１３】
さらに詳しくは、本発明は、ポテンシャルに基づくルーティング方法であって、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、
該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、
該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を蓄積する機能を備えたネットワークシステムにおいて、
上記ノードを座標点とする離散空間にポテンシャル面を想定するために上記ノードの各々にポテンシャル値を与え、
このポテンシャル面の極小値または極大値を与える目標ノードを探索することによってユーザーの望むコンテンツの所在を探索し、上記探索履歴を用いて上記ユーザーから上記目標ノードに至る通信路を設定するものであり、
それぞれのノードに与えるポテンシャル値は、上記コンテンツを有するノードからの、該ネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては，予め決められた値に収束するものである。
【００１４】
上記測度としては色々なものを選択することができるが、例えば、上記測度はホッピング数であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小ホッピング数に比例する値である。
【００１５】
また、上記測度は、例えば信号遅延時間であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小信号遅延時間に比例する値である。
【００１６】
上記の極小値または極大値を与えるノードを探索するための方法は、
ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードを暫定探索ノードとし、上記暫定探索ノードにおいて、該ノードに上記通信路で接続されたノードのそれぞれが持つポテンシャル値を比較して、より目標ノードに近いポテンシャルを有するノードを新たな暫定探索ノードとして探索を順次繰り返すことによるものである。
【００１７】
上記暫定探索ノードについては、上記ユーザーが情報の入出力を行う通信端末が直接接続するノードを最初の暫定探索ノードとするものである。
【００１８】
また、上記暫定探索ノードについては、ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードをランダムにあるいは予め決められた順に探索し、その探索によって得られたノードを最初の暫定探索ノードとするものである。
【００１９】
上記ポテンシャル値は、コンテンツが長時間蓄積されるノードを中心とする第１種ポテンシャルによるポテンシャル値と、上記コンテンツの複写が短時間蓄積されるノードを中心とする第２種ポテンシャルの単数あるいは複数によるポテンシャル値の単数あるいは複数との和であって、第１種ポテンシャルは、第２種ポテンシャルよりも、広範囲の作用領域を有するものである。特別な場合として、第１種ポテンシャルは上記コンテンツを永続的に蓄積するノードからのもので、第２種ポテンシャルは上記コンテンツをネットワーク上での傍受により蓄積したノードによるポテンシャルである。
【００２０】
また、本発明は、ポテンシャルに基づくネットワークであって、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、
該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、
該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を記憶する機能を備えたものであるネットワークシステムであって、
上記のポテンシャルに基づくルーティング方法によって、通信経路を設定することを特徴とするものである。
【発明の効果】
【００２１】
本発明により、ネットワークに分散した複数のコンテンツから１つを賢く選択するか指定するかをどのように行うか、という問題、つまり、ＩＣＮにおけるルーティング問題、を解決することができる。これにより、ＩＣＮの利点である高い利便性に加えて、高い多様性を実現することができる。この多様性とは、ルーティングに多数の判断プロセスを提供するものである。例えば、誰かある者のコンテンツ要求は、それに合致するコンテンツに直接経路設定されるが、この際、コンテンツへの近さの他にコンテンツの質やネットワーク状況を考慮することができる。さらに、ＩＣＮの利点であるダイナミックな環境に対する高い適用性を得ることができる。このダイナミックな環境では、コンテンツはキャッシュに置かれたり取り除かれたりが任意に行われる。
【図面の簡単な説明】
【００２２】
【図１】図１は、非特許文献１に基づく図であり、（ａ）はＰＢＲの場合で、ポテンシャル場を示す図である。谷があるものと想像されたい。ボールを落とすと、ボールはその場の底まで落ち続ける。同様に、その場の中から出たユーザーの要求は、自然にその場の底に導かれるが、その底は要求されたコンテンツの置き場所を示す。（ｂ）は、ＥＰＢＲ（Extended PBR）の場合で、この図に示すような有限の範囲に限られるポテンシャル場である場合には、ボールをランダムに転がし続ける。これは、コンテンツの置き場所を示す１つの穴に導かれるまで行う。
【図２】現在のインターネット上のＣＡＴＴの最初の配備構成例を示す。このＣＡＴＴトポロジー５は、本発明のＩＣＮ構造でＰＢＲに基づくものである。ＣＡＴＴノードは、自律システム（ＡＳ：Autonomous System）の端点で展開され、コンテンツは、それがＡＳ間を伝送される途中でキャッシュされる。図中、エッジルータＥＲ（Edge router）１、バックボーンルータＢＲ（Backbone router）２、自律システムＡＳ（Autonomous system, e.g., ISP）３は、たとえばＩＳＰ（インターネットサービスプロバイダ）であり、ＣＡＴＮ４はＣＡＴＴノードである。これは、純ＣＡＴＴネットワーク上で動作する「白紙状態」のフェーズに移行する前の遷移フェーズにあるものである。この構成では、１つ以上のＣＡＴＴノード（ＣＡＴＮｓ：ｓは複数）が、自律システム（ＡＳ）のサイズに依存して、ＡＳのエッジ上にＡＳのサイズ順に展開されている。ＣＡＴＮｓをＩＳＰｓ（Internet Services Provider：インターネットサービスプロバイダ）間の情報のやり取りのキャッシング地点（蓄積地点）と考えれば、ＣＡＴＮ（ｓ）を備えたＩＳＰｓ低コストの方法を適用することができて、それは、コンテンつをエンドユーザの近くに配置し、そのコンテンツをダウンロードする際に広域回線網を用いないものである。
【図３】複数のノードで同じコンテンツと持つ場合について説明するための図である。この場合は、各ノードのポテンシャル値は、単に各キャッシュノードからの影響によるポテンシャル値の線形和であると考える。２つのノードｎp1とｎp2で１つのコンテンツ（同じコンテンツ）を持つとし、そのポテンシャル値はそれぞれ、−Ｑｎp1、−Ｑｎp2とする。ポテンシャル値は、隣のノードへ移っていくに従って抑制され、それぞれ図３の点線ａと２点鎖線ｂで示すようになる。実線ｃは両方のポテンシャル値の和を示す。この値は、各ノード、ｎ1、ｎ2、ｎ3、ｎ4、ｎ5、が、クライアントの要求にこたえて経路を設定するために用いる。上記例においては、クライアントの要求はノードｎ2上で行われるとする。その近隣のノードは、ｎ3とｎ1なので、ノードｎ2が計算するのは、自身の値と隣のポテンシャル値との差であり、それぞれ、−ψ2＋ψ1、と、−ψ2＋ψ3、である。後者は前者よりも大きいので、要求はノードｎ3に転送される。これと同様に、ノードｎ3上の要求はコンテンツを持ったノードｎp1へ転送される。
【図４】各ノードの記憶領域に残すテーブルの例を示す図である。この例では、ＦＴ（Forwarding Table:フォワーディング・テーブル)、ＰＴ（Pending Table:ペンディングのテーブル)の２つである。
【図５】コンテンツを保管するノードからのポテンシャル（（a）第１種ポテンシャル）と、その情報を傍受してキャッシュしたノードからのポテンシャル（(b)第２種ポテンシャル）との線形和のポテンシャル（(c)重畳ポテンシャル）について上記の探索を行う場合の例を示す。この例においては、第１種ポテンシャルは、時間的変化が無いものと仮定することができるので、作用範囲の広いポテンシャルを設けても、ポテンシャルの設定や除去に関わる情報資源的コストを低く抑えることができる。しかし、第２種ポテンシャルについては、キャッシュ内容が時々刻々変化するものと仮定することができ、この場合は、ポテンシャル場を入れ替える必要が出てくる。
【発明を実施するための最良の形態】
【００２３】
以下に、この発明の実施の形態を図面に基づいて詳細に説明する。また、以下では、極小点に向かって引力が生じるポテンシャル場を想定するが、極大点に向かって引力が生じるポテンシャル場を想定することは、符号を変えることで実現できるので、容易なことであるので、以下では、通常のポテンシャルの場合と同様に、極小点に向かって引力が生じるポテンシャル場を想定して説明する。
【実施例１】
【００２４】
本発明は、キャッシュ依存ターゲット識別（ＣＡＴＴ：Cache Aware Target idenTification）と呼ばれる分類に属するものである。ＣＡＴＴは２つの要件、すなわちルーティングおよびコンテンツのキャッシングを考慮して設計される。１つめの要件は、ネットワーク内に公表されるか貯えられるコンテンツの１つを見つけるか選択する方法である。ここで、各コンテンツは、上記ＤＯＮＡと同様に、１６進数を並べたフラット型でハッシュコードなどを並べた自己認証型である形式（standard flat and self-certifying scheme）で名称が付けられているものと仮定する。この形式では、認証が容易であり、一貫性がある。２つめの要件は、キャッシング形態と呼ぶもので、ネットワーク上の異なる部分に公表されたコンテンツをキャッシュする方法を取り扱う。
【００２５】
図２は、現在のインターネット上のＣＡＴＴの最初の配備構成例を示す。このＣＡＴＴトポロジー５は、本発明のＩＣＮ構造でＰＢＲに基づくものである。ＣＡＴＴノードは、自律システム（ＡＳ：Autonomous System）の端点で展開され、コンテンツは、それがＡＳ間を伝送される途中でキャッシュされる。図中、エッジルータＥＲ（Edge router）１、バックボーンルータＢＲ（Backbone router）２、自律システムＡＳ（Autonomous system, 例えば, ISP）３はたとえばＩＳＰ（インターネットサービスプロバイダ）であり、ＣＡＴＮ４はＣＡＴＴノードである。これは、純ＣＡＴＴネットワーク上で動作する「白紙状態」のフェーズに移行する前の遷移フェーズにあるものである。この構成では、１つ以上のＣＡＴＴノード（ＣＡＴＮｓ：ｓは複数）が、自律システム（ＡＳ）のサイズに依存して、ＡＳのエッジ上にＡＳのサイズ順に展開されている。ＣＡＴＮｓをＩＳＰｓ（Internet Services Provider：インターネットサービスプロバイダ）間の情報のやり取りのキャッシング地点（蓄積地点）と考えれば、ＣＡＴＮ（ｓ）を備えたＩＳＰｓ低コストの方法を適用することができて、それは、コンテンつをエンドユーザの近くに配置し、そのコンテンツをダウンロードする際に広域回線網を用いないものである。
【００２６】
配備構成は、かなり高度に、ＩＳＰルーティングポリシーに関係している。ＡＳの内のユーザはローカルのＣＡＴＮ（ｓ：ｓは複数）の位置を知っていると仮定すると、ネットワーク上にコンテンツを公開することができる。したがって、コンテンツに関わるどんな要請も、そのローカルのＣＡＴＮへ最初に転送され、その地点からコンテンツ分解（つまりルーティングに向けた）のプロセスが開始される。ユーザのリクエストを最初に受け取ったＣＡＴＮは、そのコンテンツがキャッシュにあるかどうかをチェックし、それが存在する場合は、要求に直接応答し、存在しない場合は、隣のＣＡＴＮのうちの１つへリクエストを転送する。このルーティングメカニズムについては、以下でポテンシャルに基づいたルーティング（ＰＢＲ）を導入する。
【００２７】
高い有用性を達成するために、多数の同一のコンテンツを利用するという意味で、本発明のルーティング解は上記ＤＯＮＡに似ている。有用性が最大の場合には、次のさらなる設計ゴールを達成することができる；
（イ） ルーティングに豊富な意志決定プロセスを供給する多様性。例えば、ユーザのコンテンツの要請は、コンテンツへの近さだけでなく、コンテンツの質またはネットワーク条件を考慮して、一致するコンテンツの方へ直接経路が向けられる。
（ロ） コンテンツが、いつ何時でも、キャッシュに置かれるか、取り除かれるかする環境への順応性。
（ハ） 十分に分散されたメカニズムに基づいた、単一故障に対する強健さ。
（ニ） ルーティング性能の低下を僅かなものに抑制して、ルーティングテーブルのサイズを緩和する拡張性。
【００２８】
ポテンシャルに基づいたルーティングアルゴリズムでは、関心のあるアプリケーションに対して、１つのスカラー値をネットワーク要素ごとに定義してポテンシャル場を形成する。その後、クエリまたはトラフィックは、ポテンシャル値を最小化する方向へ転送される。
【００２９】
さらに、ＩＣＮに起こりうるスケーラビリティ問題を緩和するために、ＰＢＲ様式を拡張する。
【００３０】
ルーティング解に加えて、コンテンツキャッシング（コンテンツの蓄積）問題を取り扱う。理論的には、このＩＣＮにおけるコンテンツキャッシング問題は、ＣＤＮ（Content Delivery Network）における代理サーバー配置と同様な最適化問題として定式化できる。これは、適正なスポットをネットワーク上に最適に選択することによって、最高のパフォーマンスが得られるという意味である。しかし、その最適化問題はＮＰ（Non-deterministic Polynomial）−完全であることが証明されており、発見的問題解決法だけが有効である（非特許文献６）。
【００３１】
これらのやり方では計算が複雑であることから、いくつかの別の直感的なやり方が、計算が比較的容易で十分な解を得られるものとして導入されている。例えば、トポロジー依存配置戦略（非特許文献７)では、ネットワークのトポロジカルな特徴に注目する。他の例は、ホットスポットアルゴリズム（非特許文献８)で、最大負荷を生じるユーザーの近くにそのコンテンツのレプリカを配置する。
【００３２】
以下では、２つの代替案を考慮する。つまり、ＩＣＮの在り得るキャッシング形態としては、トポロジー依存配置（ＴＰ：topology aware placement、非特許文献７)およびトラフィック依存配置（ＴＦ：traffic aware placement、非特許文献８)である。比較目的のために、ランダム配置（ＲＤ、非特許文献９）も考慮する。
【実施例２】
【００３３】
＜ケース１＞ １つのノードのみがコンテンツを持つ場合
上記の１つのノードはポテンシャル値として、−Ｑ、を持つものとする。絶対値｜Ｑ｜は、コンテンツの予測品質を表す。この品質とは、キャッシュノードの容量やトラフィック付加などである。例えば、高容量の外向きリンクを備えるキャッシュノードは高品質のコンテンツを提供するものと見なすことができる。さらに、ポテンシャル値はそのノードから離れるに従って増加する（たとえば、ホップカウント数に基づいて）。このように、ポテンシャル値は、ネットワークの各ノードで定義することができる。従って、コンテンツを見つけるためには、ユーザー要求のあるノードは、その要求をポテンシャル値が減少するように隣のノードに転送する。次に、このルーティングについて、詳しく説明する。
【００３４】
本発明の特徴の１つが、このポテンシャルに基づいたルーティング（ＰＢＲ）にある。この説明のため、まず、方向性の無いグラフとしてネットワークをモデル化する。ノードｎはそれぞれ、隣のノードＢ（ｎ）のセットを持っている。ネットワーク中のノードは、２つのグループ（すなわちキャッシュされたノードｎc、キャッシュされていないノードｎnc）に分けられる。ここで、キャッシュされたノードは、そのキャッシュにコンテンツをもつノードとして定義される。また、Ｔは、同一の内容（ｎ1c、ｎ2c、・・・、ｎTc）をもった、キャッシュされたノードの数を表わす。
【００３５】
最初に、１つのキャッシュされたノードだけ（Ｔ＝１）がネットワークにあると考える。そのとき、ノードｎのポテンシャル値ψnは数１で定義される。
【００３６】
【数１】
【００３７】
キャッシュされたノードのポテンシャル値ψncを−Ｑncとして定義する。絶対値｜Ｑnc｜は、そのコンテンツについて、キャッシュされたノードのキャパシティあるいはトラヒック負荷などで表され期待できる質を表わす。例えば、高キャパシティの出力リンクを持ったキャッシュされたノードは、高品質コンテンツを供給すると仮定することができる。また、ｄnc⇔nは、キャッシュされたノードｎcとノードｎの間の距離を表す。直観的に、コンテンツの質が、距離ｄnc⇔nの増加にしたがって低下すると推測される。距離としては、地理的な接近、ホップカウント、送信遅延、リンクコストなどのような様々な物理的な解釈がある。数１における負号は、ユーザのリクエストが、ポテンシャル場の、より低い部分に向かって下がり続けることを意味する。
【００３８】
上記の図１（ａ）におけるポテンシャル場は、ブロードキャストメカニズムを使用して、個々のキャッシュされたノードのアドバタイズ（経路広告）によって定義されるものとする。アドバタイズメッセージを受信するノードはそれぞれ、経路指定項目（ルーティングエントリー）を作るか、あるいは、入り口点（エントリーポイント）があればそれを更新する。あるノードにおけるルーティングテーブルのサイズはそのノードが受信するアドバタイズメッセージの数に比例するので、アドバタイズメッセージ用のブロードキャスト範囲を制限することでルーティングテーブルのサイズを抑制することができる。
【００３９】
上記のＰＢＲを次のように拡張し、拡張されたＰＢＲ（ＥＰＢＲ）とする。上記のように、図１（ｂ）は、６つのキャッシュされたノードがある場合の例を示す。また、そのノードの各々は、アドバタイズメッセージの移動を少数のホップ内に納めることが可能になる。このホップ数は、アドバタイズエリア（経路広告範囲）を決定するｍとして表わす。逆に言えば、アドバタイズされたエリアの外側のノードではルーティング情報を維持する必要はなく、それでルーティングテーブルのサイズが縮小される。このアプローチを用いると、どれほどルーティングテーブルのサイズを縮小することができるか、を次に示す。
【００４０】
ＥＰＢＲ構成では、ユーザリクエストは第１にランダムウォークを行ない、次に、そのリクエストは、ポテンシャル場に移るとすぐに、決定論的にルーティングされる。リクエストがポテンシャル場にあるノードｎに到達すると、コンテンツを持ったノードに到達するまで、それは隣接するノードｎ∈Ｂ（ｎ）に転送される。ここで、Ｂ（ｎ）は、ノードｎに隣接するノードの集合を表す。次のホップｂnextのための選択は、ノードｎとその隣のｂ∈Ｂ（ｎ）の間のポテンシャル差Ｆn→bによって決定される。
【００４１】
【数２】
【００４２】
数２に示すように、ユーザのノードｎに関するリクエストは、ポテンシャル差Ｆn→bが最大となるノードｎの隣のノードへ転送される。
【００４３】
どのノードにキャッシュするかというキャッシング形態は、パフォーマンスを最大化する上で重要な問題である。ＩＣＮにおけるキャッシュについてのコンテンツの配置問題は、最適な配置にすることで最大のパフォーマンスが得られるという意味で、ＣＤＮにおける代理配置の問題に類似している。ほとんどのＣＤＮプロバイダー（例えばアカマイ）は、その実装が単純である（非特許文献１０）ことから、非協力的プル型アルゴリズムを採用している。同じ理由で、本実施例においても、ＩＣＮに非協力的プル型アルゴリズムを使用することを想定している。
【００４４】
キャッシングのアルゴリズムの実装は以下のとおりである。第１に、ＩＣＮアーキテクチャーの１つの特性から受ける恩恵がある。それは、リクエストノードとレスポンスノードの間の経路上のＩＣＮノードは、それらのノードで交換されるコンテンツを知っていることにより生じるもので、これがために、中間ノードはより少ないオーバーヘッドでそのコンテンツをキャッシュできることになる。この場合は、経路上のノードからキャッシングポイントを選択することで、ネットワーク関連の手続きでなく、内部ルーター操作の一環としてのキャッシングを行うこともできる。
【００４５】
パス上のノードから１つのキャッシングポイントを選択するために、いくつかの直観的なアプローチを想定する。すなわちトポロジー依存配置（ＴＰ）、トラフィック依存配置（ＴＦ）およびランダム配置（ＲＤ）である。
【００４６】
トポロジー依存配置については、リンクを多く持ったノード（高位ノード）にコンテンツをキャッシュする。これは高位ノードが、他のノードへは、より少ない遅延時間で到達することができるためである。他方では、トラフィック依存配置の観点からは、真中にある高位ノードが選ばれる。また、ランダム配置の場合は、経路上のノードをランダムに選ぶ。
【実施例３】
【００４７】
複数のノードで同じコンテンツと持つ場合について説明する。この場合は、図３にその例を示す様に、各ノードのポテンシャル値は、単に各キャッシュノードからの影響によるポテンシャル値の線形和であると考える。２つのノードｎp1とｎp2で１つのコンテンツ（同じコンテンツ）を持つとし、そのポテンシャル値はそれぞれ、−Ｑｎp1、−Ｑｎp2とする。ポテンシャル値は、隣のノードへ移っていくに従って抑制され、それぞれ図３の点線ａと２点鎖線ｂで示すようになる。実線ｃは両方のポテンシャル値の和を示す。この値は、各ノード、ｎ1、ｎ2、ｎ3、ｎ4、ｎ5、が、クライアントの要求にこたえて経路を設定するために用いる。
【００４８】
上記例においては、クライアントの要求はノードｎ2上で行われるとする。その近隣のノードは、ｎ3とｎ1なので、ノードｎ2が計算するのは、自身の値と隣のポテンシャル値との差であり、それぞれ、−Ψ2＋Ψ1、と、−Ψ2＋Ψ3、である。後者は前者よりも大きいので、要求はノードｎ3に転送される。これと同様に、ノードｎ3上の要求はコンテンツを持ったノードｎp1へ転送される。
【００４９】
次に、複数のキャッシュされたノードがある場合を、より一般化した形式で扱う。それぞれのノードにおけるポテンシャル値は、個々のキャッシュされたノードを反映したポテンシャル値の線形和であると単純に考えることができる。
この場合、上記数１は、数３のように変形できる。
【００５０】
【数３】
【実施例４】
【００５１】
上記の図１（ａ）のポテンシャルの場合は、個々のキャッシュノードのブロードキャスト機能を用いたアドバタイズで定義される。アドバタイズメッセージを受け取った各ノードは、ルーティングエントリーを作るかそれをアップデートするかを要求する。この要求は、エントリーポイントの有無に依存する（ルーティング表の各エントリーポイントは、コンテンツの名前と隣のノード用のポテンシャル値とを含むものである）。
【００５２】
ここで、各ノードの記憶領域にはそれぞれ図４に示されるような２つのテーブルを設ける。これらは、ＦＴ（Forwarding Table:フォワーディング・テーブル)、ＰＴ（Pending Table:ペンディングのテーブル)である。
【００５３】
ＦＴには３カラムがあり、最初の２行のみ示すが、以降必要な分続く。第１列は、コンテンツ名またはＩＤを記入する。第２列は、それぞれそのポテンシャル値を入れる。最後の列にはフォワーディング・インターフェース、つまり、指定されたＩＤを備えた内容を見つけるために、リクエストを転送する隣接ノードを記入する。フォワーディング・インターフェースを決定するために、各ノードはそれぞれ、それ自身の値とその隣のポテンシャル値の間の各内容のポテンシャル差を計算し、最大のポテンシャル差がある隣接ノードを選択するようにする。
【００５４】
ノードにおけるルーティング表のサイズ（つまり行または列の数）は、そのノードの受け取る新しいアドバタイズメッセージの数に比例しているので、アドバタイズメッセージのブロードキャスト領域を制限することによってルーティング表のサイズを小さくすることができる。
【００５５】
上記の図１（ｂ）のポテンシャルの場合は、この例で６つのキャッシュノードがある場合の例で、アドバタイズメッセージが２〜３ホップ以内である場合を示す。この場合は、アドバタイズ領域外ではルーティング情報を持つ必要がないためルーティング表のサイズを小さくできる。
【００５６】
上記ＰＴは、希望のコンテンツを提供するノードに至る経路で、クエリ（要求メッセージ）が伝搬されたのと同じ経路を遡って、トラフィック（応答メッセージ）をユーザーに送るために使用する。言いかえれば、クエリ（要求メッセージ）は、一致する旨のレスポンスの場合に、中間ノードにユーザーまで逆に辿れる経路の記録を残すようにする。上記ＰＴの第２列には、注目するノードの、どのインターフェースへリクエストが入るかを記録する。したがって、あるノードが、あるリクエストＩＤを備えたレスポンスを受け取る場合、そのノードは、リクエストが入ってきたインターフェースへ、応答メッセージを逆向きに送出する。
【実施例５】
【００５７】
図５にコンテンツを保管するノードからのポテンシャル（（a）第１種ポテンシャル）と、その情報を傍受してキャッシュしたノードからのポテンシャル（(b)第２種ポテンシャル）との線形和のポテンシャル（(c)重畳ポテンシャル）について上記の探索を行う場合の例を示す。この例においては、第１種ポテンシャルは、時間的変化が無いものと仮定することができるので、作用範囲の広いポテンシャルを設けても、ポテンシャルの設定や除去に関わる情報資源的コストを低く抑えることができる。しかし、第２種ポテンシャルについては、キャッシュ内容が時々刻々変化するものと仮定することができ、この場合は、ポテンシャル場を入れ替える必要が出てくる。
【００５８】
ポテンシャル場を入れ替えることは、各ノードのポテンシャル値を書換えることであるので、第２種ポテンシャルの作用範囲がより広範囲になるにしたがって、その書換え分の情報量あるいは情報処理量が増大し情報資源的コストが増加することは明らかである。従って、第２種ポテンシャルの作用範囲は、なるべく狭いことが望ましい。しかし、上記の図１（ｂ）の説明の様に、第２種ポテンシャルの作用範囲がより小さい場合は、その分目的とするコンテンツの探索に時間を要する様になる。
【００５９】
従って、第２種ポテンシャルとしては、複数のノードを包含するが、第１種ポテンシャルよりも狭い作用範囲を持つことが望ましい。例えば、第１種ポテンシャルとして、所定の作用範囲を持ち、定義された距離について単調に増加または減少する関数を想定する。また、第２種ポテンシャルとしては、当初は、キャッシュノード近くのみに及ぶ作用範囲を持ち、時間の経過とともにその作用範囲を拡大し、所定の時間が経過した場合は、第１種ポテンシャルの作用範囲と同じになるように想定することも可能である。
【００６０】
第２種ポテンシャルを生成するキャッシュノードのコンテンツの変更が生じた場合には、そのコンテンツによるポテンシャル場を解消する必要がある。この際、複数のノードでのポテンシャル値を同時に改変することが理想であるが、それは通常困難であるので、何らかの手順に従ってそれぞれのノードで順に改変を進めることになる。この改変作業中もユーザーによるコンテンツ探索を許す場合には、この作業の間、コンテンツが消えた後に局所的な極小点（ポテンシャルや引力の極性が上記と逆の場合は、極大点）が発生すると、探索が必ずしも収束しなくなる、あるいは収束点に望みのコンテンツを見出せないなどの事が起こるので、この発生を避けることが臨まれる。このためには、第２種ポテンシャルのキャッシュノードでポテンシャル値を一旦解消するためには、例えば、コンテンツを消す前に、そのポテンシャルの作用する領域の最外殻にあるノードからそのキャッシュノードへ向かってポテンシャル値の解消を進めることで、この問題の発生を避けることができる。
【産業上の利用可能性】
【００６１】
本発明のポテンシャルに基づくルーティング方法を既存のネットワークに適用する場合を考えると、ＴＣＰ−ＩＰ（Transmission Control Protocol/Internet Protocol）に基づく通常のインターネットでは、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備えており、また、インターネットでは、通信路の接続を切り換えるルータ機能と情報を蓄えるキャッシュ機能を備えたサーバーが複数接続されている。このため、これを用いて、本発明のポテンシャルに基づくルーティング方法を適用できるようにすることは、容易である。
【００６２】
このためには、各ノードには、図４に示す表を用意し、コンテンツを有するノードからは、周りのノードに図１（ｂ）のポテンシャル面を形成するためのブロードキャストを行い、上記の表にデータを書き込む。
【００６３】
ユーザーが上記コンテンツを上記通信端末に表示しようとするときには、転送要求を、ランダムに選択したサーバー宛に、目的とするコンテンツのポテンシャル値を持ったサーバーの存在が確認できるまで（但し、決められた上限あり）送信する。そのポテンシャル値の極小点となるサーバーを見出す。この際、図４の表に必要なデータを埋めて残す。このサーバーにはユーザーの目的とするコンテンツがあるので、このコンテンツをユーザー宛に転送する。この際、図４（ｂ）に示す経路履歴が残されているので、この履歴を逆に辿るように各ノードを経由して上記通信端末まで送信する。
【符号の説明】
【００６４】
１ ＥＲ（エッジルータ）
２ ＢＲ（バックボーンルータ）
３ ＡＳ（自律システム）
４ ＣＡＴＮ
５ ＣＡＴＴトポロジー
【技術分野】
【０００１】
この発明は、希望のデータの、名前や識別符号に基づいてルーティング（経路設定）される情報中心ネットワーク（ＩＣＮ：Information Centric Network）におけるポテンシャルに基づくルーティング方法およびそれを用いたネットワークに関している。
【背景技術】
【０００２】
ＩＣＮ（非特許文献１から３参照）においては、ユーザーのリクエスト（要求）は、ＩＰ（インターネットプロトコル）アドレスで表現された位置よりもむしろ求められるデータの名前に基づいて通信経路が設定される。この性質のため、動きつつあるデバイスにＩＰアドレスを割り当てるという問題、あるいは、増加しつつあるモバイルデバイスのＩＰアドレスを管理する問題は自然に解消されるので、モビリティ（機動性）問題やマルチホーミング問題（非特許文献４参照）として知られている問題とは無縁である。さらに、コンテンツ（一連の情報）をローカルにキャッシュ（蓄積）することでＩＣＮが低遅延のストレージ空間をサポートするので、ポピュラーコンテンツ（一般情報）の場合に起こる送り手側の隘路（ボトルネック）を引き起こさない。
【０００３】
上記の利点にもかかわらず、この有望な構成を進展させるためにいくつかの問題に注目する必要がある。その１つは、ネットワークに分散した複数のコンテンツから１つを賢く選択するか指定するかをどのように行うか、という問題である（この問題はＩＣＮにおけるルーティング問題として知られている）。
【０００４】
本発明では、上記のゴールを実現するために、ポテンシャルに基づくルーティング（ＰＢＲ：Potential Based Routing）というアイデアを採用する。これは、当初 Chalermark et al. （非特許文献５）によって導入されたもので、方向付けられた拡散法(directed diffusion method)と呼ばれたものである。ポテンシャルに基づくルーティングアルゴリズムは、注目するアプリケーションに対応したスカラー値をネットワーク要素ごとに割り当ててポテンシャル場を形成する。それから、クエリー（処理要求）やトラフィック（情報）が、ポテンシャル値を最小化する方向に転送される。
【０００５】
図１は、非特許文献１に基づく図であり、（ａ）はＰＢＲの場合で、ポテンシャル場を示す図である。谷があるものと想像されたい。ボールを落とすと、ボールはその場の底まで落ち続ける。同様に、その場の中から出たユーザーの要求は、自然にその場の底に導かれるが、その底は要求されたコンテンツの置き場所を示す。（ｂ）は、ＥＰＢＲ（Extended PBR）の場合で、この図に示すような有限の範囲に限られるポテンシャル場である場合には、ボールをランダムに転がし続ける。これは、コンテンツの置き場所を示す１つの穴に導かれるまで行う。
【０００６】
従来、ＩＣＮルーティングアルゴリズムは、２つのカテゴリーに分類されてきた。つまり、構造化されていないルーティングと構造化されたルーティングとであり、これはルーティング表を維持する際にシステマティックな構造があるかどうかによっている。
【０００７】
例えば、ＮＤＮ（Named Data Networking、非特許文献３）は前者に属し、集約コンテンツの識別子への特別な命名法を示唆しているが、その識別子は、ＩＰルーティングにおけるプレフィクス集約と同様なものである。ＩＰルーティングにおいては、コンテンツ識別子の集約によって拡張可能性問題の緩和するが、コンテンツ名の単一性を犠牲にしている。高い利便性のルーティングは、一般にネットワークの複数の識別子をもったコンテンツを利用して構築されているが、実現が難しい。
【０００８】
他方、ＤＯＮＡ（Data-Oriented Network Architecture、非特許文献２）は後者に属するが、エニーキャスト（anycast）に基づくルーティングを採用している。非特許文献２の著者達の主張では、彼らの方法は高い利便性を有し、これはユーザーに信頼性と低いレイテンシ（遅延時間）をもたらす。これは近くのコンテンツへのプロキシミティに基づくルーティングによるものである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】D. R. Cheriton and M. Gritter, TRIAD: a Scalable Deployable NAT-based Internet Architecture, “Distributed Systems Group, StanfordUniversity,” Technical Report, Jan 2000.
【非特許文献２】T. Koponen, A. Ermolinskiy, M. Chawla, K. H. Kim, I. Stoica, B. gon Chun, and S. Shenker, “A data-oriented (and beyond) network architecture,” in Proceedings of the 2007 conference on Applications,technologies, architectures, and protocols for computer communications (SIGCOMM'07), Kyoto, Japan, Aug 2007.
【非特許文献３】Named Data Networking. [Online]. Available:http://www.named-data.net/
【非特許文献４】J. Choi, J. Han, E. Cho, T. Kwon, and Y. Choi, “A Survey on content-oriented networking for efficient content delivery,” Communications Magazine, IEEE, vol. 49, pp. 121-127, 2011.
【非特許文献５】R. G. C. Intanagonwiwat and D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” in Proceedings of the sixth annual international conference on Mobile computing and networking, Boston, MA USA, Aug 2000.
【非特許文献６】S. Jin and L. Wang, “Content and service replication strategies in multi-hop wireless mesh networks,” in Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, Montreal, Canada, October 2005.
【非特許文献７】P. Radoslavov, R. Govindan, and D. Estrin, “Topology-Informed Internet Replica Placement,” in Proceedings of Sixth International Workshop on Web Caching and Content Distribution, Boston, USA, June 2001.
【非特許文献８】L. QIU, V. N. PADMANABHAN, AND G. M. VOELKER, “ON THE PLACEMENT OF WEB SERVER REPLICAS,” IN PROCEEDINGS OF IEEE INFOCOM, ANCHORAGE, USA, APRIL 2001.
【非特許文献９】S. ARIANFAR, P. NIKANDER, AND J. OTT, “ON CONTENT-CENTRIC ROUTER DESIGN AND IMPLICATIONS,” IN PROCEEDINGS OF ACM REARCH 2010, PHILADELPHIA, USA, NOVEMBER 2010.
【非特許文献１０】M. Pathan and R. Buyya, “A Taxonomy of CDNs (Content Delivery Networks).” R. Buyya, M. Pathan, and A. Vakali (Eds.), Springer-Verlag, Germany, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記の様に、ＩＣＮにおいては、動きつつあるデバイスにＩＰアドレスを割り当てるという問題、あるいは、増加しつつあるモバイルデバイスのＩＰアドレスを管理する問題は、自然に解消されるので、モビリティ（機動性）問題やマルチホーミング問題とは無縁である。さらに、ポピュラーコンテンツでは送り手側の隘路（ボトルネック）が起こり易い、という問題が起きない。しかし、上記の様に、ＩＣＮにおけるルーティング問題がある。本発明は、このＩＣＮにおけるルーティング問題を取り扱う１つのアイデアを提案するものである。
【課題を解決するための手段】
【００１１】
本発明は、概略、情報を伝送する複数の通信経路（以下では単に、経路）と、上記経路によって互いに接続された複数のノード（結節点）と、上記ノードのいずれかに上記経路によって接続された複数の通信端末とを備え、上記ノードは、受信した情報の少なくとも1部を蓄積（キャッシュ）し、またその受信した情報の演算処理を行い、その演算結果に基づいて送信する経路を選択して情報を送信するものであり、上記通信端末は接続された経路に対して、処理要求（クエリ）を送信し、あるいは情報（トラフィック）の送受信をするネットワークにおいて、ネットワークの使用者は、上記通信端末に、例えば、希望のコンテンツをダウンロードするためのクエリを入力し、上記通信端末に上記コンテンツを表示するか、上記通信端末から出力するもである。
【００１２】
同一のコンテンツを有するノードが複数の場合、上記ネットワークの各ノードのポテンシャル値は、上記コンテンツを有するノードのそれぞれからのポテンシャル値への寄与の線形和であるとする。これによって、同一のコンテンツを有するノードから、ユーザにとって最も好条件のノードを選択することができるようになる。
【００１３】
さらに詳しくは、本発明は、ポテンシャルに基づくルーティング方法であって、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、
該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、
該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を蓄積する機能を備えたネットワークシステムにおいて、
上記ノードを座標点とする離散空間にポテンシャル面を想定するために上記ノードの各々にポテンシャル値を与え、
このポテンシャル面の極小値または極大値を与える目標ノードを探索することによってユーザーの望むコンテンツの所在を探索し、上記探索履歴を用いて上記ユーザーから上記目標ノードに至る通信路を設定するものであり、
それぞれのノードに与えるポテンシャル値は、上記コンテンツを有するノードからの、該ネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては，予め決められた値に収束するものである。
【００１４】
上記測度としては色々なものを選択することができるが、例えば、上記測度はホッピング数であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小ホッピング数に比例する値である。
【００１５】
また、上記測度は、例えば信号遅延時間であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小信号遅延時間に比例する値である。
【００１６】
上記の極小値または極大値を与えるノードを探索するための方法は、
ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードを暫定探索ノードとし、上記暫定探索ノードにおいて、該ノードに上記通信路で接続されたノードのそれぞれが持つポテンシャル値を比較して、より目標ノードに近いポテンシャルを有するノードを新たな暫定探索ノードとして探索を順次繰り返すことによるものである。
【００１７】
上記暫定探索ノードについては、上記ユーザーが情報の入出力を行う通信端末が直接接続するノードを最初の暫定探索ノードとするものである。
【００１８】
また、上記暫定探索ノードについては、ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードをランダムにあるいは予め決められた順に探索し、その探索によって得られたノードを最初の暫定探索ノードとするものである。
【００１９】
上記ポテンシャル値は、コンテンツが長時間蓄積されるノードを中心とする第１種ポテンシャルによるポテンシャル値と、上記コンテンツの複写が短時間蓄積されるノードを中心とする第２種ポテンシャルの単数あるいは複数によるポテンシャル値の単数あるいは複数との和であって、第１種ポテンシャルは、第２種ポテンシャルよりも、広範囲の作用領域を有するものである。特別な場合として、第１種ポテンシャルは上記コンテンツを永続的に蓄積するノードからのもので、第２種ポテンシャルは上記コンテンツをネットワーク上での傍受により蓄積したノードによるポテンシャルである。
【００２０】
また、本発明は、ポテンシャルに基づくネットワークであって、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、
該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、
該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を記憶する機能を備えたものであるネットワークシステムであって、
上記のポテンシャルに基づくルーティング方法によって、通信経路を設定することを特徴とするものである。
【発明の効果】
【００２１】
本発明により、ネットワークに分散した複数のコンテンツから１つを賢く選択するか指定するかをどのように行うか、という問題、つまり、ＩＣＮにおけるルーティング問題、を解決することができる。これにより、ＩＣＮの利点である高い利便性に加えて、高い多様性を実現することができる。この多様性とは、ルーティングに多数の判断プロセスを提供するものである。例えば、誰かある者のコンテンツ要求は、それに合致するコンテンツに直接経路設定されるが、この際、コンテンツへの近さの他にコンテンツの質やネットワーク状況を考慮することができる。さらに、ＩＣＮの利点であるダイナミックな環境に対する高い適用性を得ることができる。このダイナミックな環境では、コンテンツはキャッシュに置かれたり取り除かれたりが任意に行われる。
【図面の簡単な説明】
【００２２】
【図１】図１は、非特許文献１に基づく図であり、（ａ）はＰＢＲの場合で、ポテンシャル場を示す図である。谷があるものと想像されたい。ボールを落とすと、ボールはその場の底まで落ち続ける。同様に、その場の中から出たユーザーの要求は、自然にその場の底に導かれるが、その底は要求されたコンテンツの置き場所を示す。（ｂ）は、ＥＰＢＲ（Extended PBR）の場合で、この図に示すような有限の範囲に限られるポテンシャル場である場合には、ボールをランダムに転がし続ける。これは、コンテンツの置き場所を示す１つの穴に導かれるまで行う。
【図２】現在のインターネット上のＣＡＴＴの最初の配備構成例を示す。このＣＡＴＴトポロジー５は、本発明のＩＣＮ構造でＰＢＲに基づくものである。ＣＡＴＴノードは、自律システム（ＡＳ：Autonomous System）の端点で展開され、コンテンツは、それがＡＳ間を伝送される途中でキャッシュされる。図中、エッジルータＥＲ（Edge router）１、バックボーンルータＢＲ（Backbone router）２、自律システムＡＳ（Autonomous system, e.g., ISP）３は、たとえばＩＳＰ（インターネットサービスプロバイダ）であり、ＣＡＴＮ４はＣＡＴＴノードである。これは、純ＣＡＴＴネットワーク上で動作する「白紙状態」のフェーズに移行する前の遷移フェーズにあるものである。この構成では、１つ以上のＣＡＴＴノード（ＣＡＴＮｓ：ｓは複数）が、自律システム（ＡＳ）のサイズに依存して、ＡＳのエッジ上にＡＳのサイズ順に展開されている。ＣＡＴＮｓをＩＳＰｓ（Internet Services Provider：インターネットサービスプロバイダ）間の情報のやり取りのキャッシング地点（蓄積地点）と考えれば、ＣＡＴＮ（ｓ）を備えたＩＳＰｓ低コストの方法を適用することができて、それは、コンテンつをエンドユーザの近くに配置し、そのコンテンツをダウンロードする際に広域回線網を用いないものである。
【図３】複数のノードで同じコンテンツと持つ場合について説明するための図である。この場合は、各ノードのポテンシャル値は、単に各キャッシュノードからの影響によるポテンシャル値の線形和であると考える。２つのノードｎp1とｎp2で１つのコンテンツ（同じコンテンツ）を持つとし、そのポテンシャル値はそれぞれ、−Ｑｎp1、−Ｑｎp2とする。ポテンシャル値は、隣のノードへ移っていくに従って抑制され、それぞれ図３の点線ａと２点鎖線ｂで示すようになる。実線ｃは両方のポテンシャル値の和を示す。この値は、各ノード、ｎ1、ｎ2、ｎ3、ｎ4、ｎ5、が、クライアントの要求にこたえて経路を設定するために用いる。上記例においては、クライアントの要求はノードｎ2上で行われるとする。その近隣のノードは、ｎ3とｎ1なので、ノードｎ2が計算するのは、自身の値と隣のポテンシャル値との差であり、それぞれ、−ψ2＋ψ1、と、−ψ2＋ψ3、である。後者は前者よりも大きいので、要求はノードｎ3に転送される。これと同様に、ノードｎ3上の要求はコンテンツを持ったノードｎp1へ転送される。
【図４】各ノードの記憶領域に残すテーブルの例を示す図である。この例では、ＦＴ（Forwarding Table:フォワーディング・テーブル)、ＰＴ（Pending Table:ペンディングのテーブル)の２つである。
【図５】コンテンツを保管するノードからのポテンシャル（（a）第１種ポテンシャル）と、その情報を傍受してキャッシュしたノードからのポテンシャル（(b)第２種ポテンシャル）との線形和のポテンシャル（(c)重畳ポテンシャル）について上記の探索を行う場合の例を示す。この例においては、第１種ポテンシャルは、時間的変化が無いものと仮定することができるので、作用範囲の広いポテンシャルを設けても、ポテンシャルの設定や除去に関わる情報資源的コストを低く抑えることができる。しかし、第２種ポテンシャルについては、キャッシュ内容が時々刻々変化するものと仮定することができ、この場合は、ポテンシャル場を入れ替える必要が出てくる。
【発明を実施するための最良の形態】
【００２３】
以下に、この発明の実施の形態を図面に基づいて詳細に説明する。また、以下では、極小点に向かって引力が生じるポテンシャル場を想定するが、極大点に向かって引力が生じるポテンシャル場を想定することは、符号を変えることで実現できるので、容易なことであるので、以下では、通常のポテンシャルの場合と同様に、極小点に向かって引力が生じるポテンシャル場を想定して説明する。
【実施例１】
【００２４】
本発明は、キャッシュ依存ターゲット識別（ＣＡＴＴ：Cache Aware Target idenTification）と呼ばれる分類に属するものである。ＣＡＴＴは２つの要件、すなわちルーティングおよびコンテンツのキャッシングを考慮して設計される。１つめの要件は、ネットワーク内に公表されるか貯えられるコンテンツの１つを見つけるか選択する方法である。ここで、各コンテンツは、上記ＤＯＮＡと同様に、１６進数を並べたフラット型でハッシュコードなどを並べた自己認証型である形式（standard flat and self-certifying scheme）で名称が付けられているものと仮定する。この形式では、認証が容易であり、一貫性がある。２つめの要件は、キャッシング形態と呼ぶもので、ネットワーク上の異なる部分に公表されたコンテンツをキャッシュする方法を取り扱う。
【００２５】
図２は、現在のインターネット上のＣＡＴＴの最初の配備構成例を示す。このＣＡＴＴトポロジー５は、本発明のＩＣＮ構造でＰＢＲに基づくものである。ＣＡＴＴノードは、自律システム（ＡＳ：Autonomous System）の端点で展開され、コンテンツは、それがＡＳ間を伝送される途中でキャッシュされる。図中、エッジルータＥＲ（Edge router）１、バックボーンルータＢＲ（Backbone router）２、自律システムＡＳ（Autonomous system, 例えば, ISP）３はたとえばＩＳＰ（インターネットサービスプロバイダ）であり、ＣＡＴＮ４はＣＡＴＴノードである。これは、純ＣＡＴＴネットワーク上で動作する「白紙状態」のフェーズに移行する前の遷移フェーズにあるものである。この構成では、１つ以上のＣＡＴＴノード（ＣＡＴＮｓ：ｓは複数）が、自律システム（ＡＳ）のサイズに依存して、ＡＳのエッジ上にＡＳのサイズ順に展開されている。ＣＡＴＮｓをＩＳＰｓ（Internet Services Provider：インターネットサービスプロバイダ）間の情報のやり取りのキャッシング地点（蓄積地点）と考えれば、ＣＡＴＮ（ｓ）を備えたＩＳＰｓ低コストの方法を適用することができて、それは、コンテンつをエンドユーザの近くに配置し、そのコンテンツをダウンロードする際に広域回線網を用いないものである。
【００２６】
配備構成は、かなり高度に、ＩＳＰルーティングポリシーに関係している。ＡＳの内のユーザはローカルのＣＡＴＮ（ｓ：ｓは複数）の位置を知っていると仮定すると、ネットワーク上にコンテンツを公開することができる。したがって、コンテンツに関わるどんな要請も、そのローカルのＣＡＴＮへ最初に転送され、その地点からコンテンツ分解（つまりルーティングに向けた）のプロセスが開始される。ユーザのリクエストを最初に受け取ったＣＡＴＮは、そのコンテンツがキャッシュにあるかどうかをチェックし、それが存在する場合は、要求に直接応答し、存在しない場合は、隣のＣＡＴＮのうちの１つへリクエストを転送する。このルーティングメカニズムについては、以下でポテンシャルに基づいたルーティング（ＰＢＲ）を導入する。
【００２７】
高い有用性を達成するために、多数の同一のコンテンツを利用するという意味で、本発明のルーティング解は上記ＤＯＮＡに似ている。有用性が最大の場合には、次のさらなる設計ゴールを達成することができる；
（イ） ルーティングに豊富な意志決定プロセスを供給する多様性。例えば、ユーザのコンテンツの要請は、コンテンツへの近さだけでなく、コンテンツの質またはネットワーク条件を考慮して、一致するコンテンツの方へ直接経路が向けられる。
（ロ） コンテンツが、いつ何時でも、キャッシュに置かれるか、取り除かれるかする環境への順応性。
（ハ） 十分に分散されたメカニズムに基づいた、単一故障に対する強健さ。
（ニ） ルーティング性能の低下を僅かなものに抑制して、ルーティングテーブルのサイズを緩和する拡張性。
【００２８】
ポテンシャルに基づいたルーティングアルゴリズムでは、関心のあるアプリケーションに対して、１つのスカラー値をネットワーク要素ごとに定義してポテンシャル場を形成する。その後、クエリまたはトラフィックは、ポテンシャル値を最小化する方向へ転送される。
【００２９】
さらに、ＩＣＮに起こりうるスケーラビリティ問題を緩和するために、ＰＢＲ様式を拡張する。
【００３０】
ルーティング解に加えて、コンテンツキャッシング（コンテンツの蓄積）問題を取り扱う。理論的には、このＩＣＮにおけるコンテンツキャッシング問題は、ＣＤＮ（Content Delivery Network）における代理サーバー配置と同様な最適化問題として定式化できる。これは、適正なスポットをネットワーク上に最適に選択することによって、最高のパフォーマンスが得られるという意味である。しかし、その最適化問題はＮＰ（Non-deterministic Polynomial）−完全であることが証明されており、発見的問題解決法だけが有効である（非特許文献６）。
【００３１】
これらのやり方では計算が複雑であることから、いくつかの別の直感的なやり方が、計算が比較的容易で十分な解を得られるものとして導入されている。例えば、トポロジー依存配置戦略（非特許文献７)では、ネットワークのトポロジカルな特徴に注目する。他の例は、ホットスポットアルゴリズム（非特許文献８)で、最大負荷を生じるユーザーの近くにそのコンテンツのレプリカを配置する。
【００３２】
以下では、２つの代替案を考慮する。つまり、ＩＣＮの在り得るキャッシング形態としては、トポロジー依存配置（ＴＰ：topology aware placement、非特許文献７)およびトラフィック依存配置（ＴＦ：traffic aware placement、非特許文献８)である。比較目的のために、ランダム配置（ＲＤ、非特許文献９）も考慮する。
【実施例２】
【００３３】
＜ケース１＞ １つのノードのみがコンテンツを持つ場合
上記の１つのノードはポテンシャル値として、−Ｑ、を持つものとする。絶対値｜Ｑ｜は、コンテンツの予測品質を表す。この品質とは、キャッシュノードの容量やトラフィック付加などである。例えば、高容量の外向きリンクを備えるキャッシュノードは高品質のコンテンツを提供するものと見なすことができる。さらに、ポテンシャル値はそのノードから離れるに従って増加する（たとえば、ホップカウント数に基づいて）。このように、ポテンシャル値は、ネットワークの各ノードで定義することができる。従って、コンテンツを見つけるためには、ユーザー要求のあるノードは、その要求をポテンシャル値が減少するように隣のノードに転送する。次に、このルーティングについて、詳しく説明する。
【００３４】
本発明の特徴の１つが、このポテンシャルに基づいたルーティング（ＰＢＲ）にある。この説明のため、まず、方向性の無いグラフとしてネットワークをモデル化する。ノードｎはそれぞれ、隣のノードＢ（ｎ）のセットを持っている。ネットワーク中のノードは、２つのグループ（すなわちキャッシュされたノードｎc、キャッシュされていないノードｎnc）に分けられる。ここで、キャッシュされたノードは、そのキャッシュにコンテンツをもつノードとして定義される。また、Ｔは、同一の内容（ｎ1c、ｎ2c、・・・、ｎTc）をもった、キャッシュされたノードの数を表わす。
【００３５】
最初に、１つのキャッシュされたノードだけ（Ｔ＝１）がネットワークにあると考える。そのとき、ノードｎのポテンシャル値ψnは数１で定義される。
【００３６】
【数１】
【００３７】
キャッシュされたノードのポテンシャル値ψncを−Ｑncとして定義する。絶対値｜Ｑnc｜は、そのコンテンツについて、キャッシュされたノードのキャパシティあるいはトラヒック負荷などで表され期待できる質を表わす。例えば、高キャパシティの出力リンクを持ったキャッシュされたノードは、高品質コンテンツを供給すると仮定することができる。また、ｄnc⇔nは、キャッシュされたノードｎcとノードｎの間の距離を表す。直観的に、コンテンツの質が、距離ｄnc⇔nの増加にしたがって低下すると推測される。距離としては、地理的な接近、ホップカウント、送信遅延、リンクコストなどのような様々な物理的な解釈がある。数１における負号は、ユーザのリクエストが、ポテンシャル場の、より低い部分に向かって下がり続けることを意味する。
【００３８】
上記の図１（ａ）におけるポテンシャル場は、ブロードキャストメカニズムを使用して、個々のキャッシュされたノードのアドバタイズ（経路広告）によって定義されるものとする。アドバタイズメッセージを受信するノードはそれぞれ、経路指定項目（ルーティングエントリー）を作るか、あるいは、入り口点（エントリーポイント）があればそれを更新する。あるノードにおけるルーティングテーブルのサイズはそのノードが受信するアドバタイズメッセージの数に比例するので、アドバタイズメッセージ用のブロードキャスト範囲を制限することでルーティングテーブルのサイズを抑制することができる。
【００３９】
上記のＰＢＲを次のように拡張し、拡張されたＰＢＲ（ＥＰＢＲ）とする。上記のように、図１（ｂ）は、６つのキャッシュされたノードがある場合の例を示す。また、そのノードの各々は、アドバタイズメッセージの移動を少数のホップ内に納めることが可能になる。このホップ数は、アドバタイズエリア（経路広告範囲）を決定するｍとして表わす。逆に言えば、アドバタイズされたエリアの外側のノードではルーティング情報を維持する必要はなく、それでルーティングテーブルのサイズが縮小される。このアプローチを用いると、どれほどルーティングテーブルのサイズを縮小することができるか、を次に示す。
【００４０】
ＥＰＢＲ構成では、ユーザリクエストは第１にランダムウォークを行ない、次に、そのリクエストは、ポテンシャル場に移るとすぐに、決定論的にルーティングされる。リクエストがポテンシャル場にあるノードｎに到達すると、コンテンツを持ったノードに到達するまで、それは隣接するノードｎ∈Ｂ（ｎ）に転送される。ここで、Ｂ（ｎ）は、ノードｎに隣接するノードの集合を表す。次のホップｂnextのための選択は、ノードｎとその隣のｂ∈Ｂ（ｎ）の間のポテンシャル差Ｆn→bによって決定される。
【００４１】
【数２】
【００４２】
数２に示すように、ユーザのノードｎに関するリクエストは、ポテンシャル差Ｆn→bが最大となるノードｎの隣のノードへ転送される。
【００４３】
どのノードにキャッシュするかというキャッシング形態は、パフォーマンスを最大化する上で重要な問題である。ＩＣＮにおけるキャッシュについてのコンテンツの配置問題は、最適な配置にすることで最大のパフォーマンスが得られるという意味で、ＣＤＮにおける代理配置の問題に類似している。ほとんどのＣＤＮプロバイダー（例えばアカマイ）は、その実装が単純である（非特許文献１０）ことから、非協力的プル型アルゴリズムを採用している。同じ理由で、本実施例においても、ＩＣＮに非協力的プル型アルゴリズムを使用することを想定している。
【００４４】
キャッシングのアルゴリズムの実装は以下のとおりである。第１に、ＩＣＮアーキテクチャーの１つの特性から受ける恩恵がある。それは、リクエストノードとレスポンスノードの間の経路上のＩＣＮノードは、それらのノードで交換されるコンテンツを知っていることにより生じるもので、これがために、中間ノードはより少ないオーバーヘッドでそのコンテンツをキャッシュできることになる。この場合は、経路上のノードからキャッシングポイントを選択することで、ネットワーク関連の手続きでなく、内部ルーター操作の一環としてのキャッシングを行うこともできる。
【００４５】
パス上のノードから１つのキャッシングポイントを選択するために、いくつかの直観的なアプローチを想定する。すなわちトポロジー依存配置（ＴＰ）、トラフィック依存配置（ＴＦ）およびランダム配置（ＲＤ）である。
【００４６】
トポロジー依存配置については、リンクを多く持ったノード（高位ノード）にコンテンツをキャッシュする。これは高位ノードが、他のノードへは、より少ない遅延時間で到達することができるためである。他方では、トラフィック依存配置の観点からは、真中にある高位ノードが選ばれる。また、ランダム配置の場合は、経路上のノードをランダムに選ぶ。
【実施例３】
【００４７】
複数のノードで同じコンテンツと持つ場合について説明する。この場合は、図３にその例を示す様に、各ノードのポテンシャル値は、単に各キャッシュノードからの影響によるポテンシャル値の線形和であると考える。２つのノードｎp1とｎp2で１つのコンテンツ（同じコンテンツ）を持つとし、そのポテンシャル値はそれぞれ、−Ｑｎp1、−Ｑｎp2とする。ポテンシャル値は、隣のノードへ移っていくに従って抑制され、それぞれ図３の点線ａと２点鎖線ｂで示すようになる。実線ｃは両方のポテンシャル値の和を示す。この値は、各ノード、ｎ1、ｎ2、ｎ3、ｎ4、ｎ5、が、クライアントの要求にこたえて経路を設定するために用いる。
【００４８】
上記例においては、クライアントの要求はノードｎ2上で行われるとする。その近隣のノードは、ｎ3とｎ1なので、ノードｎ2が計算するのは、自身の値と隣のポテンシャル値との差であり、それぞれ、−Ψ2＋Ψ1、と、−Ψ2＋Ψ3、である。後者は前者よりも大きいので、要求はノードｎ3に転送される。これと同様に、ノードｎ3上の要求はコンテンツを持ったノードｎp1へ転送される。
【００４９】
次に、複数のキャッシュされたノードがある場合を、より一般化した形式で扱う。それぞれのノードにおけるポテンシャル値は、個々のキャッシュされたノードを反映したポテンシャル値の線形和であると単純に考えることができる。
この場合、上記数１は、数３のように変形できる。
【００５０】
【数３】
【実施例４】
【００５１】
上記の図１（ａ）のポテンシャルの場合は、個々のキャッシュノードのブロードキャスト機能を用いたアドバタイズで定義される。アドバタイズメッセージを受け取った各ノードは、ルーティングエントリーを作るかそれをアップデートするかを要求する。この要求は、エントリーポイントの有無に依存する（ルーティング表の各エントリーポイントは、コンテンツの名前と隣のノード用のポテンシャル値とを含むものである）。
【００５２】
ここで、各ノードの記憶領域にはそれぞれ図４に示されるような２つのテーブルを設ける。これらは、ＦＴ（Forwarding Table:フォワーディング・テーブル)、ＰＴ（Pending Table:ペンディングのテーブル)である。
【００５３】
ＦＴには３カラムがあり、最初の２行のみ示すが、以降必要な分続く。第１列は、コンテンツ名またはＩＤを記入する。第２列は、それぞれそのポテンシャル値を入れる。最後の列にはフォワーディング・インターフェース、つまり、指定されたＩＤを備えた内容を見つけるために、リクエストを転送する隣接ノードを記入する。フォワーディング・インターフェースを決定するために、各ノードはそれぞれ、それ自身の値とその隣のポテンシャル値の間の各内容のポテンシャル差を計算し、最大のポテンシャル差がある隣接ノードを選択するようにする。
【００５４】
ノードにおけるルーティング表のサイズ（つまり行または列の数）は、そのノードの受け取る新しいアドバタイズメッセージの数に比例しているので、アドバタイズメッセージのブロードキャスト領域を制限することによってルーティング表のサイズを小さくすることができる。
【００５５】
上記の図１（ｂ）のポテンシャルの場合は、この例で６つのキャッシュノードがある場合の例で、アドバタイズメッセージが２〜３ホップ以内である場合を示す。この場合は、アドバタイズ領域外ではルーティング情報を持つ必要がないためルーティング表のサイズを小さくできる。
【００５６】
上記ＰＴは、希望のコンテンツを提供するノードに至る経路で、クエリ（要求メッセージ）が伝搬されたのと同じ経路を遡って、トラフィック（応答メッセージ）をユーザーに送るために使用する。言いかえれば、クエリ（要求メッセージ）は、一致する旨のレスポンスの場合に、中間ノードにユーザーまで逆に辿れる経路の記録を残すようにする。上記ＰＴの第２列には、注目するノードの、どのインターフェースへリクエストが入るかを記録する。したがって、あるノードが、あるリクエストＩＤを備えたレスポンスを受け取る場合、そのノードは、リクエストが入ってきたインターフェースへ、応答メッセージを逆向きに送出する。
【実施例５】
【００５７】
図５にコンテンツを保管するノードからのポテンシャル（（a）第１種ポテンシャル）と、その情報を傍受してキャッシュしたノードからのポテンシャル（(b)第２種ポテンシャル）との線形和のポテンシャル（(c)重畳ポテンシャル）について上記の探索を行う場合の例を示す。この例においては、第１種ポテンシャルは、時間的変化が無いものと仮定することができるので、作用範囲の広いポテンシャルを設けても、ポテンシャルの設定や除去に関わる情報資源的コストを低く抑えることができる。しかし、第２種ポテンシャルについては、キャッシュ内容が時々刻々変化するものと仮定することができ、この場合は、ポテンシャル場を入れ替える必要が出てくる。
【００５８】
ポテンシャル場を入れ替えることは、各ノードのポテンシャル値を書換えることであるので、第２種ポテンシャルの作用範囲がより広範囲になるにしたがって、その書換え分の情報量あるいは情報処理量が増大し情報資源的コストが増加することは明らかである。従って、第２種ポテンシャルの作用範囲は、なるべく狭いことが望ましい。しかし、上記の図１（ｂ）の説明の様に、第２種ポテンシャルの作用範囲がより小さい場合は、その分目的とするコンテンツの探索に時間を要する様になる。
【００５９】
従って、第２種ポテンシャルとしては、複数のノードを包含するが、第１種ポテンシャルよりも狭い作用範囲を持つことが望ましい。例えば、第１種ポテンシャルとして、所定の作用範囲を持ち、定義された距離について単調に増加または減少する関数を想定する。また、第２種ポテンシャルとしては、当初は、キャッシュノード近くのみに及ぶ作用範囲を持ち、時間の経過とともにその作用範囲を拡大し、所定の時間が経過した場合は、第１種ポテンシャルの作用範囲と同じになるように想定することも可能である。
【００６０】
第２種ポテンシャルを生成するキャッシュノードのコンテンツの変更が生じた場合には、そのコンテンツによるポテンシャル場を解消する必要がある。この際、複数のノードでのポテンシャル値を同時に改変することが理想であるが、それは通常困難であるので、何らかの手順に従ってそれぞれのノードで順に改変を進めることになる。この改変作業中もユーザーによるコンテンツ探索を許す場合には、この作業の間、コンテンツが消えた後に局所的な極小点（ポテンシャルや引力の極性が上記と逆の場合は、極大点）が発生すると、探索が必ずしも収束しなくなる、あるいは収束点に望みのコンテンツを見出せないなどの事が起こるので、この発生を避けることが臨まれる。このためには、第２種ポテンシャルのキャッシュノードでポテンシャル値を一旦解消するためには、例えば、コンテンツを消す前に、そのポテンシャルの作用する領域の最外殻にあるノードからそのキャッシュノードへ向かってポテンシャル値の解消を進めることで、この問題の発生を避けることができる。
【産業上の利用可能性】
【００６１】
本発明のポテンシャルに基づくルーティング方法を既存のネットワークに適用する場合を考えると、ＴＣＰ−ＩＰ（Transmission Control Protocol/Internet Protocol）に基づく通常のインターネットでは、ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備えており、また、インターネットでは、通信路の接続を切り換えるルータ機能と情報を蓄えるキャッシュ機能を備えたサーバーが複数接続されている。このため、これを用いて、本発明のポテンシャルに基づくルーティング方法を適用できるようにすることは、容易である。
【００６２】
このためには、各ノードには、図４に示す表を用意し、コンテンツを有するノードからは、周りのノードに図１（ｂ）のポテンシャル面を形成するためのブロードキャストを行い、上記の表にデータを書き込む。
【００６３】
ユーザーが上記コンテンツを上記通信端末に表示しようとするときには、転送要求を、ランダムに選択したサーバー宛に、目的とするコンテンツのポテンシャル値を持ったサーバーの存在が確認できるまで（但し、決められた上限あり）送信する。そのポテンシャル値の極小点となるサーバーを見出す。この際、図４の表に必要なデータを埋めて残す。このサーバーにはユーザーの目的とするコンテンツがあるので、このコンテンツをユーザー宛に転送する。この際、図４（ｂ）に示す経路履歴が残されているので、この履歴を逆に辿るように各ノードを経由して上記通信端末まで送信する。
【符号の説明】
【００６４】
１ ＥＲ（エッジルータ）
２ ＢＲ（バックボーンルータ）
３ ＡＳ（自律システム）
４ ＣＡＴＮ
５ ＣＡＴＴトポロジー
【特許請求の範囲】
【請求項１】
ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を蓄積する機能を備えたネットワークシステムにおいて、
上記ノードを座標点とする離散空間にポテンシャル面を想定するために上記ノードの各々にポテンシャル値を与え、
このポテンシャル面の極小値または極大値を与える目標ノードを探索することによってユーザーの望むコンテンツの所在を探索し、上記探索履歴を用いて上記ユーザーから上記目標ノードに至る通信路を設定するものであり、
それぞれのノードに与えるポテンシャル値は、上記コンテンツを有するノードからの、該ネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては，予め決められた値に収束するものである、
ことを特徴とするポテンシャルに基づくルーティング方法。
【請求項２】
同一のコンテンツを有するノードが複数の場合、上記ネットワークの各ノードのポテンシャル値は、上記コンテンツを有するノードのそれぞれからのポテンシャル値への寄与の線形和であることを特徴とする請求項１に記載のポテンシャルに基づくルーティング方法。
【請求項３】
上記測度はホッピング数であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小ホッピング数に比例する値であることを特徴とする請求項１または２のどちらかに記載のポテンシャルに基づくルーティング方法。
【請求項４】
上記測度は信号遅延時間であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小信号遅延時間に比例する値であることを特徴とする請求項１または２のどちらかに記載のポテンシャルに基づくルーティング方法。
【請求項５】
上記の極小値または極大値を与えるノードを探索するための方法は、
ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードを暫定探索ノードとし、上記暫定探索ノードにおいて、該ノードに上記通信路で接続されたノードのそれぞれが持つポテンシャル値を比較して、より目標ノードに近いポテンシャルを有するノードを新たな暫定探索ノードとして探索を順次繰り返すことを特徴とする請求項１から４のいずれか１つに記載のポテンシャルに基づくルーティング方法。
【請求項６】
上記暫定探索ノードについては、上記ユーザーが情報の入出力を行う通信端末が直接接続するノードを最初の暫定探索ノードとすることを特徴とする請求項５に記載のポテンシャルに基づくルーティング方法。
【請求項７】
上記暫定探索ノードについては、ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードをランダムにあるいは予め決められた順に探索し、その探索によって得られたノードを最初の暫定探索ノードとすることを特徴とする請求項５に記載のポテンシャルに基づくルーティング方法。
【請求項８】
上記ポテンシャル値は、コンテンツが長時間蓄積されるノードを中心とする第１種ポテンシャルによるポテンシャル値と、上記コンテンツの複写が短時間蓄積されるノードを中心とする第２種ポテンシャルの単数あるいは複数によるポテンシャル値の単数あるいは複数との和であって、第１種ポテンシャルは、第２種ポテンシャルよりも、広範囲の作用領域を有するものであることを特徴とする請求項１から７のいずれか１つに記載のポテンシャルに基づくルーティング方法。
【請求項９】
ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、 該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を記憶する機能を備えたものであるネットワークシステムであって、
請求項１から８のいずれか１つのポテンシャルに基づくルーティング方法によって、通信経路を設定することを特徴とするポテンシャルに基づくネットワーク。
【請求項１】
ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を蓄積する機能を備えたネットワークシステムにおいて、
上記ノードを座標点とする離散空間にポテンシャル面を想定するために上記ノードの各々にポテンシャル値を与え、
このポテンシャル面の極小値または極大値を与える目標ノードを探索することによってユーザーの望むコンテンツの所在を探索し、上記探索履歴を用いて上記ユーザーから上記目標ノードに至る通信路を設定するものであり、
それぞれのノードに与えるポテンシャル値は、上記コンテンツを有するノードからの、該ネット上で定義された測度による距離に従って単調に減少または増加し、無限遠の距離においては，予め決められた値に収束するものである、
ことを特徴とするポテンシャルに基づくルーティング方法。
【請求項２】
同一のコンテンツを有するノードが複数の場合、上記ネットワークの各ノードのポテンシャル値は、上記コンテンツを有するノードのそれぞれからのポテンシャル値への寄与の線形和であることを特徴とする請求項１に記載のポテンシャルに基づくルーティング方法。
【請求項３】
上記測度はホッピング数であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小ホッピング数に比例する値であることを特徴とする請求項１または２のどちらかに記載のポテンシャルに基づくルーティング方法。
【請求項４】
上記測度は信号遅延時間であって、この測度によるノードＡとノードＢ間の距離は、ノードＡからノードＢに至るために必要な最小信号遅延時間に比例する値であることを特徴とする請求項１または２のどちらかに記載のポテンシャルに基づくルーティング方法。
【請求項５】
上記の極小値または極大値を与えるノードを探索するための方法は、
ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードを暫定探索ノードとし、上記暫定探索ノードにおいて、該ノードに上記通信路で接続されたノードのそれぞれが持つポテンシャル値を比較して、より目標ノードに近いポテンシャルを有するノードを新たな暫定探索ノードとして探索を順次繰り返すことを特徴とする請求項１から４のいずれか１つに記載のポテンシャルに基づくルーティング方法。
【請求項６】
上記暫定探索ノードについては、上記ユーザーが情報の入出力を行う通信端末が直接接続するノードを最初の暫定探索ノードとすることを特徴とする請求項５に記載のポテンシャルに基づくルーティング方法。
【請求項７】
上記暫定探索ノードについては、ユーザーの指定するコンテンツについて付与されたポテンシャル値を有するいずれかのノードをランダムにあるいは予め決められた順に探索し、その探索によって得られたノードを最初の暫定探索ノードとすることを特徴とする請求項５に記載のポテンシャルに基づくルーティング方法。
【請求項８】
上記ポテンシャル値は、コンテンツが長時間蓄積されるノードを中心とする第１種ポテンシャルによるポテンシャル値と、上記コンテンツの複写が短時間蓄積されるノードを中心とする第２種ポテンシャルの単数あるいは複数によるポテンシャル値の単数あるいは複数との和であって、第１種ポテンシャルは、第２種ポテンシャルよりも、広範囲の作用領域を有するものであることを特徴とする請求項１から７のいずれか１つに記載のポテンシャルに基づくルーティング方法。
【請求項９】
ユーザーが情報の入出力を行う通信端末と、該通信端末の接続するネットワークと、を備え、 該ネットワークは、該ネットワークにおける通信路の接続を切り換える機能を備えるノードの複数と、該ノードの複数を互いに接続する通信路の複数を備えるものであり、該ノードは、上記ユーザーが上記ネットワークを通じてダウンロードできる情報を記憶する機能を備えたものであるネットワークシステムであって、
請求項１から８のいずれか１つのポテンシャルに基づくルーティング方法によって、通信経路を設定することを特徴とするポテンシャルに基づくネットワーク。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１３−１０２３３０（Ｐ２０１３−１０２３３０Ａ）
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願番号】特願２０１１−２４４４５９（Ｐ２０１１−２４４４５９）
【出願日】平成２３年１１月８日（２０１１．１１．８）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願日】平成２３年１１月８日（２０１１．１１．８）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]