(57)【要約】      （修正有）【課題】複数のキャッシュサーバの中からネットワークの全体の容量及び混雑状況を考慮して要求されたコンテンツを送信するキャッシュサーバを選択する装置、方法及び分散キャッシュシステムを提供する。【解決手段】クライアントからリクエストを受信し、複数のキャッシュサーバの中から、受信したリクエストに対応するデータを記憶する少なくとも一つのキャッシュサーバを特定し、該キャッシュサーバ毎に、装置から該キャッシュサーバまで到達可能な少なくとも一つのパスの中から所定の条件を満たす少なくとも一つのパスの束を、トポロジ情報に基づいて特定し、該キャッシュサーバ毎の特定した少なくとも一つの各パスの束のネットワークトラフィック容量を計算し、計算した各パスの束の容量に基づいて、該キャッシュサーバの中から、データをクライアントに送信するキャッシュサーバを選択する。【選択図】図６
2016046785.tif 000002
【特許請求の範囲】
【請求項１】
クライアント及び複数のキャッシュサーバに接続されるキャッシュサーバ選択装置であって、
前記複数のキャッシュサーバはネットワークを構築し、
前記ネットワークのトポロジ情報を記憶しており、
前記クライアントからリクエストを受信し、
前記複数のキャッシュサーバの中から、前記受信したリクエストに対応するデータを記憶する少なくとも一つのキャッシュサーバを特定し、
前記特定された少なくとも一つのキャッシュサーバ毎に、前記キャッシュサーバ選択装置から前記特定した少なくとも一つの各キャッシュサーバまで到達可能な全てのパスの中から所定の条件を満たす少なくとも一つのパスを、前記トポロジ情報に基づいて特定し、
前記特定した少なくとも一つのキャッシュサーバ毎の前記特定した少なくとも一つの各パスの容量を計算し、
前記計算したパスの容量に基づいて、前記特定した少なくとも一つのキャッシュサーバの中から、前記データをクライアントに送信するキャッシュサーバを選択することを特徴とするキャッシュサーバ選択装置。
【請求項２】
請求項１に記載のキャッシュサーバ選択装置であって、
前記所定の条件を満たす少なくとも一つのパスは、前記キャッシュサーバ選択装置と所定の関係にあるパスであることを特徴とするキャッシュサーバ選択装置。
【請求項３】
請求項２に記載のキャッシュサーバ選択装置であって、
前記キャッシュサーバ選択装置と所定の関係にあるパスは、前記キャッシュサーバ選択装置から前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスであることを特徴とするキャッシュサーバ選択装置。
【請求項４】
請求項３に記載のキャッシュサーバ選択装置であって、
前記キャッシュサーバ選択装置から前記特定した少なくとも一つの各キャッシュサーバまで到達可能な全てのパスの中から、前記キャッシュサーバ選択装置から前記特定した少なくとも一つの各キャッシュサーバまで最短の距離で到達する最短パスを特定し、
前記キャッシュサーバ選択装置から前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスは、前記キャッシュサーバ選択装置から前記特定された少なくとも一つのキャッシュサーバまで前記特定した最短パスの距離から所定範囲で到達するパスであることを特徴とするキャッシュサーバ選択装置。
【請求項５】
請求項１に記載のキャッシュサーバ選択装置であって、
前記複数のキャッシュサーバは、前記ネットワークのトポロジ情報を記憶しており、
前記トポロジ情報に基づいて、前記特定した所定の条件を満たすパス上の複数のノード、及び前記パスを構成するリンクを特定し、
前記複数のキャッシュサーバに前記トポロジ情報を更新させるために、前記特定した複数のノード及び前記特定したリンクに関する情報を含むサブグラフ情報を前記複数のキャッシュサーバに送信することを特徴とするキャッシュサーバ選択装置。
【請求項６】
クライアント及び複数のキャッシュサーバを備える分散キャッシュシステムであって、
前記複数のキャッシュサーバはネットワークを構築し、
前記複数のキャッシュサーバは、前記ネットワークのトポロジ情報を記憶しており、
前記クライアントからリクエストを受信したキャッシュサーバであるガーディアンは、
前記複数のキャッシュサーバの中から、前記受信したリクエストに対応するデータを記憶する少なくとも一つのキャッシュサーバを特定し、
前記特定された少なくとも一つのキャッシュサーバ毎に、前記ガーディアンから前記特定した少なくとも一つの各キャッシュサーバまで到達可能な全てのパスの中から所定の条件を満たす少なくとも一つのパスを、前記トポロジ情報に基づいて特定し、
前記特定した少なくとも一つのキャッシュサーバ毎の前記特定した少なくとも一つの各パスの容量を計算し、
前記計算した各パスの容量に基づいて、前記特定した少なくとも一つのキャッシュサーバの中から、前記データをクライアントに送信するキャッシュサーバを選択することを特徴とする分散キャッシュシステム。
【請求項７】
請求項６に記載の分散キャッシュシステムであって、
前記所定の条件を満たす少なくとも一つのパスは、前記ガーディアンと所定の関係にあるパスであることを特徴とする分散キャッシュシステム。
【請求項８】
請求項７に記載の分散キャッシュシステムであって、
前記ガーディアンと所定の関係にあるパスは、前記ガーディアンから前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスであることを特徴とする分散キャッシュシステム。
【請求項９】
請求項８に記載の分散キャッシュシステムであって、
前記ガーディアンは、前記ガーディアンから前記特定した少なくとも一つの各キャッシュサーバまで到達可能な少なくとも全てのパスの中から、前記ガーディアンから前記特定した少なくとも一つの各キャッシュサーバまで最短の距離で到達する最短パスを特定し、
前記ガーディアンから前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスは、前記ガーディアンから前記特定された少なくとも一つのキャッシュサーバまで前記特定した最短パスの距離から所定範囲で到達するパスであることを特徴とする分散キャッシュシステム。
【請求項１０】
請求項６に記載の分散キャッシュシステムであって、
前記ガーディアンは、
前記トポロジ情報に基づいて、前記特定した所定の条件を満たすパス上の複数のノード、及び前記パスを構成するリンクを特定し、
前記特定した複数のノード及び前記特定したリンクに関する情報を含むサブグラフ情報を前記複数のキャッシュサーバに送信し、
前記サブグラフ情報を受信したキャッシュサーバは、前記受信したサブグラフ情報に基づいて、前記トポロジ情報を更新することを特徴とする分散キャッシュシステム。
【請求項１１】
クライアント及び複数のキャッシュサーバに接続される装置における、データを前記クライアントに送信するキャッシュサーバを選択するキャッシュサーバ選択方法であって、
前記複数のキャッシュサーバはネットワークを構築し、
前記ネットワークのトポロジ情報を記憶しており、
前記方法は、
前記装置が、前記クライアントからリクエストを受信し、
前記装置が、前記複数のキャッシュサーバの中から、前記受信したリクエストに対応するデータを記憶する少なくとも一つのキャッシュサーバを特定し、
前記装置が、前記特定された少なくとも一つのキャッシュサーバ毎に、前記装置から前記特定した少なくとも一つの各キャッシュサーバまで到達可能な少なくとも全てのパスの中から所定の条件を満たす少なくとも一つのパスを、前記トポロジ情報に基づいて特定し、
前記装置が、前記特定した少なくとも一つのキャッシュサーバ毎の前記特定した少なくとも一つの各パスの容量を計算し、
前記装置が、前記計算した各パスの容量に基づいて、前記特定した少なくとも一つのキャッシュサーバの中から、前記データをクライアントに送信するキャッシュサーバを選択することを特徴とするキャッシュサーバ選択方法。
【請求項１２】
請求項１１に記載のキャッシュサーバ選択方法であって、
前記所定の条件を満たす少なくとも一つのパスは、前記装置と所定の関係にあるパスであることを特徴とするキャッシュサーバ選択方法。
【請求項１３】
請求項１２に記載のキャッシュサーバ選択方法であって、
前記装置と所定の関係にあるパスは、前記装置から前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスであることを特徴とするキャッシュサーバ選択方法。
【請求項１４】
請求項１３に記載のキャッシュサーバ選択方法であって、
前記装置が、前記装置から前記特定した少なくとも一つの各キャッシュサーバまで到達可能な全てのパスの中から、前記装置から前記特定した少なくとも一つの各キャッシュサーバまで最短の距離で到達する最短パスを特定し、
前記装置から前記特定された少なくとも一つのキャッシュサーバまで所定の距離で到達するパスは、前記装置から前記特定された少なくとも一つのキャッシュサーバまで前記特定した最短パスの距離から所定範囲で到達するパスであることを特徴とするキャッシュサーバ選択方法。
【請求項１５】
請求項１１に記載のキャッシュサーバ選択方法であって、
前記複数のキャッシュサーバは、前記ネットワークのトポロジ情報を記憶しており、
前記装置が、前記トポロジ情報に基づいて、前記特定した所定の条件を満たすパス上のノード、及び前記パスを構成するリンクを特定し、
前記複数のキャッシュサーバに前記トポロジ情報を更新させるために、前記特定した複数のノード及び前記特定したリンクに関する情報を含むサブグラフ情報を前記複数のキャッシュサーバに送信することを特徴とするキャッシュサーバ選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを保持する複数のキャッシュサーバの中からデータをクライアントに送信するキャッシュサーバを選択するキャッシュサーバ選択装置に関する。
【背景技術】
【０００２】
一般世帯及びモバイルにおける広帯域のインターネットの世界的な急増に伴って、広い帯域を要求するインターネットサービスの数も増加している。これによって、トラフィックが上昇する。
【０００３】
技術革新は、利用可能な帯域を増大させ、ネットワークインフラ機器によって引き起こされる遅延を減少させてきたが、トラフィックの要求は急激に増大している。特に、多くのユーザを持つネットワークキャリアでは、トラフィックの要求がネットワークの容量を超える可能性がある。ウェブ及びビデオなどのインターネットトラフィックはジップの法則に従うとの一般的に受け入れられている観測に基づけば、キャッシュシステムはトラフィックを効果的に低減させるメカニズムである。
【０００４】
キャッシュシステムは、データを提供するオリジンサーバの負荷及びキャッシュサーバとオリジンサーバとの間のネットワークの使用量を低減させると同時に、クライアントまでの送信時間を短縮する。容量の大きいデータの送信が要求されるサービス、例えば、高解像度のビデオストリーミングサービスを提供するために必要なストレージの容量と帯域はすでに高いので大規模なキャリアグレードのネットワークでは、リクエストの数及び要求されるストレージの容量と帯域がともに非常に高くなってしまうことが予想される。このようなシステムの堅牢性とスケーラビリティを高めるために、複数のキャッシュサーバを用いてストレージの容量と帯域を分散させることが望ましい。このようなキャッシュシステムとして、分散キャッシュシステムが知られている。
【０００５】
分散キャッシュシステムでは、要求されるコンテンツが複数のキャッシュサーバによって保持されることによって、コンテンツを要求したクライアントまでの平均距離を短くし、コンテンツの送信に利用可能なスループットを増大させる。このようなシステムでは、複数の分散キャッシュサーバからコンテンツを送信する一つのキャッシュサーバを選択することは、コンテンツの送信のための直接的に必要なリソース、及びコンテンツの送信に使用されるネットワークの利用可能なリソースに対する様々な影響に密接な関連性を有する。各キャッシュサーバのネットワークリソースやコンピューティングリソースの利用可能性の比較、又は、クライアントと各キャッシュサーバとの間のネットワークリソースのエンドツーエンドの距離（例えば、レイテンシ又はホップ数）の比較に基づいて、コンテンツを送信するキャッシュサーバが決定される。これらの評価尺度に基づく選択は、コンテンツのクライアントへの送信にかかる時間を短縮でき、キャッシュサーバのリソースの簡単な負荷分散を達成できる。
【０００６】
分散キャッシュシステムに関する技術として、米国特許第７８９０６５６号明細書（特許文献１）がある。特許文献１の公報には、「コンテンツを配信する複数の配信サーバと通信する複数の配信サーバ側ルータと、コンテンツを受信するクライアントと通信するクライアント側ルータとをそなえた伝送システムにおいて、複数の配信サーバのサーバ負荷状態と、複数の配信サーバ側ルータおよびクライアント側ルータ間における複数の配信経路についての各個別リンク負荷状態とを保持するデータベースと、データベースに保持されたサーバ負荷状態と各個別リンク負荷状態との総和に基づいて、複数の配信経路のうちの負荷状態が最小となる最小負荷状態配信経路を決定する経路制御部とをそなえて構成する。」と記載されている。
【０００７】
また、マルチパスルーティングに関する技術として米国特許第７５８３６７７号公報（特許文献２）がある。特許文献２の公報には、「概して、本発明はコンピュータネットワークを通る複数のパスの間のネットワークトラフィック負荷を動的に調整する技術を対象にする。この技術は、動的に計測されるパス帯域及び各フローの負荷に基づいて、異なるパスの間のネットワークパケットのフローを分散及び再分散する。フローの分散時に、フローに要求されるＱｏＳ（Ｑｕａｌｉｔｙ  Ｏｆ  Ｓｅｒｖｉｃｅ）の帯域が維持される。」と記載されている。
【０００８】
スループット容量に関してネットワーク全体の状況を把握し、ある地点間に流せる最大のフローを求めるためのマックスフロー処理と呼ばれる技術がある。マックスフロー処理では、通信ネットワークをフローネットワークとしてモデリングすることによって、ルーティングレイヤに利用可能なネットワーク全体のリソースがリンクの帯域を示す容量及び現在の使用量を示すフローとともに計算される。利用可能な種々のネットワークが完全に使用されていれば、ソースとサーバであるシンクとの間のマックスフローは利用可能な最大の帯域を示す。
【０００９】
マックスフロー処理に関する技術としてA New Approach to the Maximum-Flow Problem”（非特許文献１）がある。非特許文献１には、フローネットワークのマックスフローを分散環境において効率的に計算する方法が記載される。各キャッシュサーバのマックスフローが計算された場合、この評価尺度を用いて、利用可能な容量が最大であるパスのキャッシュサーバを選択することができ、これによって、非特許文献１に記載された技術はネットワークの混雑を最小限に抑えることができる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許第７８９０６５６号明細書
【特許文献２】米国特許第７５８３６７７号明細書
【非特許文献】
【００１１】
【非特許文献１】Andrew Goldberg and Robert Tarjan, “A New Approach to the Maximum-Flow Problem”, Journal of the ACM, Vol. 35, 1988
【非特許文献２】Rowstron, A. & Druschel, P. “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems”, IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001, 329-350
【非特許文献３】Dabek, F.; Cox, R.; Kaashoek, F. & Morris, R. “Vivaldi: a decentralized network coordinate system”, SIGCOMM Comput. Commun. Rev., ACM, 2004, 34, 15-26
【発明の概要】
【発明が解決しようとする課題】
【００１２】
特許文献１に記載された技術は、クライアント側ルータから複数のコンテンツサーバ側ルータまで（エンドツーエンド）の最短パスを計算し、計算結果に基づいてコンテンツの送信に用いる経路を決定する。エンドポイントとなるコンテンツサーバ側ルータはクライアント側ルータが過去に通信したルータに限定される。このため、特許文献１に記載された技術は、ネットワーク全体を考慮して、コンテンツの送信に用いる経路を選択できない。また、特許文献１に記載された技術は、予め収集した情報に基づいてコンテンツの送信に用いる経路を決定するので、急速にパスの構成が変化するネットワークに対応できない。
【００１３】
また、特許文献２に記載されたマルチパスルーティングは、第３レイヤ（ネットワーキングレイヤ）で実行される処理である。しかし、エンドポイントへの送信の最適ではない選択は、ルーティングレイヤでのトラフィックの選択肢が多様化されないため、トラフィックパスの混雑を引き起し得る。これは、分散システムでの選択処理中の全体のネットワークの使用の把握がないために起こる。
【００１４】
また、非特許文献１に記載された技術は、ネットワーク全体の状況を把握できる。しかし、計算中のメッセージングのオーバーヘッドが複雑になる。ノードの数が多くなると、分散キャッシュシステムではトラフィックが増加する。このため、マックスフローを計算するために必要な時間及びメッセージングのオーバーヘッドは高くなる。非特許文献１に記載された技術はノードの数が多い分散キャッシュシステムに対応できない。
【００１５】
本発明の目的は、ノードの数が多い分散キャッシュシステムであっても、ネットワーク全体の状況を考慮してコンテンツを送信するキャッシュサーバを選択するキャッシュサーバ選択装置を提供することである。
【課題を解決するための手段】
【００１６】
本発明の代表的な一例を示せば、クライアント及び複数のキャッシュサーバに接続されるキャッシュサーバ選択装置であって、前記複数のキャッシュサーバはネットワークを構築し、前記ネットワークのトポロジ情報を記憶しており、前記クライアントからリクエストを受信し、前記複数のキャッシュサーバの中から、前記受信したリクエストに対応するデータを記憶する少なくとも一つのキャッシュサーバを特定し、前記特定された少なくとも一つのキャッシュサーバ毎に、前記キャッシュサーバ選択装置から前記特定した少なくとも一つの各キャッシュサーバまで到達可能な全てのパスの中から所定の条件を満たす少なくとも一つのパスを、前記トポロジ情報に基づいて特定し、前記特定した少なくとも一つのキャッシュサーバ毎の前記特定した少なくとも一つの各パスの容量を計算し、前記計算した各パスの容量に基づいて、前記特定した少なくとも一つのキャッシュサーバの中から、前記データをクライアントに送信するキャッシュサーバを選択することを特徴とする。
【発明の効果】
【００１７】
本願において開示される発明のうち代表的なものによって得られる効果を簡潔に説明すれば、下記の通りである。すなわち、ノードの数が多い分散キャッシュシステムであっても、ネットワーク全体の状況を考慮してコンテンツを送信するキャッシュサーバを選択するキャッシュサーバ選択装置を提供できる。
【００１８】
上記した以外の課題、構成、及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１９】
【図１】実施例１の通信システムの構成の図である。
【図２】実施例１の通信システムの概略の説明図である。
【図３】実施例１のキャッシュサーバのハードウェア構成図である。
【図４】実施例１のガーディアンとなるキャッシュサーバによって実行される処理のフローチャートである。
【図５】実施例１のガーディアンによって実行される分散マックスフロー処理のフローチャートである。
【図６】実施例１のサブグラフ初期化処理のフローチャートである。
【図７】実施例１のサブグラフのデータ構造の説明図である。
【図８】実施例１のプッシュメッセージを受信した場合にガーディアンでないキャッシュサーバによって実行される処理のフローチャートである。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態を図面に従い説明する。
【実施例１】
【００２１】
実施例１について図１〜図８を用いて説明する。
【００２２】
複数の協働するキャッシュサーバを有する分散キャッシュシステムにおいて、リクエストを受信したキャッシュサーバとリクエストされたコンテンツを保持する複数のキャッシュサーバとの間のネットワークの容量が算出され、ネットワークの容量が最大であるキャッシュサーバがコンテンツを転送するキャッシュサーバとして選択される。
【００２３】
これによって、必要となる計算量を軽減しつつ、システムのスケーラビリティを制限せずに、アンダーレイネットワークのルーティングインフラの使用ネットワーク容量を最適化できる。
【００２４】
図１は、実施例１の通信システム１００の構成の説明図である。
【００２５】
通信システム１００は、キャリアネットワーク１０１及びコンテンツネットワーク１０２を有する。コンテンツネットワーク１０２は、キャリアネットワーク１０１と異なるネットワークである。キャリアネットワーク１０１は、コンテンツネットワーク１０２にネットワークリンク２０１を介して接続される。
【００２６】
キャリアネットワーク１０１のネットワークインフラは例えばルータ３４０Ａ及び３４０Ｍを含む。キャリアネットワーク１０１内には、クライアント３０１、及びキャッシュサーバ３６０Ａ〜３６０Ｎがある。コンテンツネットワーク１０２内にはコンテンツサーバ３２１がある。
【００２７】
クライアント３０１は、コンテンツサーバ３２１にコンテンツリクエストを送信する。コンテンツリクエストは、クライアント３０１に最も近いキャッシュサーバ３６０Ａを通る。キャッシュサーバ３６０Ａはキャッシュサーバ３６０Ａ〜３６０Ｎの協働ネットワークの一部であり、これらのキャッシュサーバ３６０Ａ〜３６０Ｎはデータを転送する場合にルータ３４０Ａ及び３４０Ｍを用いる。
【００２８】
キャッシュサーバ３６０Ａは、クライアント３０１によって送信されたコンテンツリクエストを受信した場合、受信したコンテンツリクエストに対応するコンテンツを保持する少なくとも一つのキャッシュサーバを特定する。キャッシュサーバ３６０Ａは、特定した少なくとも一つの各キャッシュサーバに到達可能なパスの中から所定の条件を満たす少なくとも一つパスを特定する。そして、キャッシュサーバ３６０Ａは、特定した各パスの容量を計算し、計算した各パスの容量に基づいて、要求されたコンテンツをクライアント３０１に転送するキャッシュサーバを選択する。例えば、キャッシュサーバ３６０Ａは、受信したコンテンツリクエストに対応するコンテンツを保持する複数のキャッシュサーバを特定し、その複数の特定したキャッシュサーバ毎に到達可能なパスを特定し、特定した複数のパス毎にパスの容量を計算し、その計算したパスの容量が最大であるパスを選択し、選択したパスが到達するキャッシュサーバを、コンテンツを転送するキャッシュサーバに選択する。そして、キャッシュサーバ３６０Ａは、選択したキャッシュサーバに選択したパスを介してコンテンツリクエストを送信する。キャッシュサーバ３６０Ａによって送信されたリクエストを受信したキャッシュサーバは、受信したリクエストに対応するコンテンツをクライアント３０１に送信する。この送信はキャッシュサーバ３６０Ａを通過してもよく、その際にキャッシュサーバ３６０Ａはこのコンテンツを保持してもよい。
【００２９】
キャッシュサーバ３６０Ａは、受信したコンテンツリクエストに対応するコンテンツを保持する少なくとも一つのキャッシュサーバを特定できない場合、すなわち、受信したコンテンツリクエストに対応するコンテンツを保持するキャッシュサーバが存在しない場合、受信したコンテンツリクエストをコンテンツサーバ３２１に送信する。コンテンツサーバ３２１は、このコンテンツリクエストを受信した場合、受信したコンテンツリクエストに対応するコンテンツをキャリアネットワーク１０１を介してクライアント３０１に送信する。この送信はキャッシュサーバ３６０Ａを通過してもよく、その際にキャッシュサーバ３６０Ａはこのコンテンツを保持してもよい。
【００３０】
図２は、実施例１の通信システム１００の概略の説明図である。
【００３１】
図１に示す通信システム１００は分散キャッシュシステム５００を有し、分散キャッシュシステム５００は、例えば、複数のキャッシュサーバ３６０Ａ〜３６０Ｄ、クライアント３０１、及びコンテンツサーバ３２１を有する。クライアント３０１は、あるコンテンツの送信をコンテンツサーバ３２１に要求するコンテンツリクエスト４０１を送信する。クライアント３０１に最も近いキャッシュサーバ３６０Ａは、コンテンツリクエスト４０１を受信する。このキャッシュサーバ３６０Ａをガーディアンという。
【００３２】
クライアント３０１はガーディアンをコンテンツリクエスト４０１を転送するプロキシのように用いてもよいし、クライアント３０１側に設定なしでコンテンツリクエスト４０１を転送する透過プロキシのようにガーディアンが用いられるようにネットワークが設定されてもよい。
【００３３】
分散キャッシュシステム５００のキャッシュサーバ３６０Ａ〜３６０Ｄのうちの少なくとも一つは、コンテンツリクエスト４０１で要求されたコンテンツを保持可能である。ガーディアンは、キャッシュサーバ３６０Ａ〜３６０Ｄが参加するオーバーレイネットワークのクエリ機能を用いて、コンテンツリクエスト４０１に対応するコンテンツを保持する全てのキャッシュサーバを特定する。コンテンツリクエスト４０１に対応するコンテンツを保持する全てのキャッシュサーバをデリゲイトという。
【００３４】
キャッシュサーバ３６０Ａ〜３６０Ｄのうちの少なくとも一つは、コンテンツの識別子のリストとコンテンツの識別子によって識別されるコンテンツを保持するデリゲイトの識別子のリストとが登録されたデリゲイトリストを保持する。あるコンテンツの識別子によって識別されるコンテンツリクエストのためのデリゲイトリストを保持するキャッシュサーバをホームという。
【００３５】
ガーディアンは、コンテンツリクエスト４０１を受信した場合、ホームキャッシュサーバを探すために、受信したコンテンツリクエスト４０１に含まれるコンテンツの識別子を含むデリゲイトクエリメッセージ４１１を隣接するキャッシュサーバに送信する。隣接するキャッシュサーバは、デリゲイトクエリメッセージ４１１を受信した場合、受信したデリゲイトクエリメッセージ４１１に含まれるコンテンツの識別子のためのデリゲイトリストを保持しているか否かを判定する。
【００３６】
隣接するキャッシュサーバは、このデリゲイトリストを保持していると判定された場合、デリゲイトリストを含むデリゲイトクエリレスポンス４１２を、受信したデリゲイトクエリメッセージ４１１の応答としてガーディアンに送信する。一方、隣接するキャッシュサーバは、デリゲイトリストを保持していないと判定された場合、受信したデリゲイトクエリメッセージ４１１を他の隣接するキャッシュサーバに送信する。デリゲイトリストを保持するキャッシュサーバの探索方法の詳細は、”Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems”（非特許文献２）に記載される。本出願には、非特許文献２に記載された内容が取り込まれる。
【００３７】
図２では、ホームはキャッシュサーバ３６０Ｃである。キャッシュサーバ３６０Ｃは、デリゲイトクエリメッセージ４１１を受信した場合、デリゲイトリストを含むデリゲイトクエリレスポンス４１２をガーディアンであるキャッシュサーバ３６０Ａに送信する。デリゲイトクエリレスポンス４１２に含まれるデリゲイトリストに、デリゲイトクエリメッセージ４１１に含まれるコンテンツの識別子に対応する複数のデリゲイトの識別子が登録されている場合、ガーディアンは、図４に示す仮想コーディネイトシステム８０３を用いて、ネットワーク距離が所定値以上である全てのデリゲイトを除外する。仮想コーディネイトシステム８０３は、キャッシュサーバ間のネットワーク距離の近似値を保持する。あるキャッシュサーバが他のキャッシュサーバと通信した場合にその仮想コーディネイトシステム８０３は更新される。例えばネットワーク距離はキャッシュサーバ間のレイテンシ又はホップ数に基づくものである。仮想コーディネイトシステムの詳細は、“Vivaldi: a decentralized network coordinate system”（非特許文献３）に記載される。本出願には、非特許文献３に記載された内容が取り込まれる。
【００３８】
ガーディアンは、図４に示すトポロジ情報８０５を使って、図５に示す各デリゲイトのサブグラフ８０６を計算する。各キャッシュサーバのトポロジ情報８０５は、ネットワーク管理者によって演繹的に設定されるか、トポロジディスカバリ機能及びネットワーク管理機能を用いて取得される。トポロジ情報８０５は、キャッシュサーバとルータとの間、又は異なるルータ間のリンク容量、リンク使用量を含む。異なる実施例では、他の情報（例えば、レイテンシ、又はパケットロス割合）がトポロジ情報８０５に含まれてもよい。
【００３９】
各サブグラフ８０６は、所定の条件を満たし、ある形態のコリドーを構築するガーディアンと各デリゲイトとの間のパス上のノードのみを含む。コリドーは、ガーディアンと各デリゲイトとの間のネットワーク距離に基づいて特定される。
【００４０】
そして、ガーディアンは、分散マックスフロー処理の計算量を低減させるためにサブグラフ８０６を用いて、各デリゲイトに対して分散マックスフロー処理を実行する。非特許文献１に分散マックスフローについて記載されているため、説明を省略する。本実施例では、ガーディアンと各デリゲイトとの間の全てのパスのうち所定の条件を満たすパスに対して分散マックスフロー処理が実行されることになる。これによって、分散マックスフロー処理の計算量及び分散マックスフロー処理の計算中に通信されるメッセージの数を減少させることができ、分散マックスフロー処理にかかる時間を短縮できる。したがって、ノードの数が多い分散キャッシュシステムに分散マックスフロー処理を適用することができ、ガーディアンは、ネットワーク全体の状況を考慮して、コンテンツを送信するキャッシュサーバを選択できる。
【００４１】
例えば、図２ではデリゲイトはキャッシュサーバ３６０Ｂ及び３６０Ｄである。ガーディアンとキャッシュサーバ３６０Ｂ及び３６０Ｄとの間では、分散マックスフロー処理の実行のために、分散マックスフローメッセージ４２１及び４２２が通信される。ガーディアンは、分散マックスフロー処理の結果に基づいて、容量が最大であるコリドーが到達するデリゲイトを、コンテンツをクライアント３０１に送信するキャッシュサーバとして選択する。図２では、コンテンツをクライアント３０１に送信するキャッシュサーバとしてキャッシュサーバ３６０Ｄが選択される。
【００４２】
そして、ガーディアンは、クライアント３０１によって送信されたコンテンツリクエスト４０１をメッセージ４３１としてキャッシュサーバ３６０Ｄに送信する。キャッシュサーバ３６０Ｄは、メッセージ４３１を受信した場合、メッセージ４３１に含まれるコンテンツの識別子に対応するコンテンツを含むレスポンス４３２をガーディアンに送信する。ガーディアンは、レスポンス４３２を受信した場合、受信したレスポンス４３２をレスポンス４０２としてクライアント３０１に送信する。この場合、ガーディアンは、受信したレスポンス４３２に含まれるコンテンツを記憶してもよい。
【００４３】
コンテンツリクエスト４０１に対応するコンテンツの識別子に対応するコンテンツを保持するキャッシュサーバが存在しない場合、ガーディアンは、コンテンツリクエスト４０１をコンテンツリクエスト４４１としてコンテンツサーバ３２１に直接送信する。ガーディアンは、コンテンツサーバ３２１によって送信されたコンテンツサーバレスポンス４４２を受信した場合、受信したコンテンツサーバレスポンス４４２をレスポンス４０２でクライアント３０１に送信する。この場合、ガーディアンは、受信したコンテンツサーバレスポンス４４２に含まれるコンテンツを記憶してもよい。
【００４４】
本実施例では、非特許文献２に記載されるように、キャッシュサーバは、アドレス機能、ディスカバリー機能、及びルーティング機能を提供する仮想的なピアツーピアオーバーレイネットワークの一部である。キャッシュサーバは、ピアツーピアのオーバーレイネットワークを用いて互いに通信でき、また、直接（例えばピアツーピアのオーバーレイネットワークを用いず）互いに通信できる。各キャッシュサーバは、アンダーレイネットワークのトポロジを把握する。アンダーレイネットワークのトポロジは、ネットワーク管理者による各キャッシュサーバの初期設定中に導入されてもよい。また、アンダーレイネットワークのトポロジは、ノード間のネットワークリンクの最大容量を含む。全てのキャッシュサーバは、非特許文献３に記載された仮想コーディネイトシステムを用いる。各キャッシュサーバは、隣接する他のノード及びネットワークの構成要素のリソース情報を取得できる。特に、リソース情報はノードに接続するリンクの使用量を含む。
【００４５】
ピアツーピアシステムでは、分散キャッシュシステムの各ノードがワークフロー、責任、及び通信の点で対等であり、このため、各ノードは「ピア」と呼ばれる。広く展開されるピアツーピアシステムにおいて、ハッシュ値を識別子として使用し、ピアツーピアネットワーク内のルーティングメカニズムを使用することによって、分散ハッシュテーブル（Distributed Hash Table、ＤＨＴ）の使用は他のノードの発見を可能にする。非特許文献２には、ピアが構築するルーティングインフラの上のオーバーレイネットワークが記載されている。このオーバーレイネットワークは、ピア及びピアに格納されたコンテンツの識別子として数学的なハッシュ値を用いて、効率的なコンテンツの発見、及び機能的なルーティングを提供できる。
【００４６】
非特許文献３に記載される仮想コーディネイトシステムでは、各ノードは、自身及び他のノードを仮想的なユークリッド空間座標系に配置し、直接通信した場合に計測されたネットワークレイテンシ及び受信した他のノードの座標に関する情報に基づいて、自分自身及び他のノードの座標を調整する。
【００４７】
図３は、実施例１のキャッシュサーバのハードウェア構成図である。
【００４８】
本実施例のキャッシュサーバは、中央演算ユニット（ＣＰＵ）１５０１、プライマリメモリ１５０２、ネットワークインタフェースコントローラ（ＮＩＣ）１５０４、及びセカンダリメモリ１５０５を有する。これらは通信バス１５０３を介して互いに接続される。キャッシュサーバに要求される最小の構成要素が図３に図示される。例えば他のネットワークインタフェースコントローラ等の他の構成は通信バス１５０３に接続されてもよい。
【００４９】
キャッシュサーバの動作中、キャッシュサーバの動作指示、及び実行時に必要な構成パラメータは、プライマリメモリ１５０２に記憶される。ＣＰＵ１５０１がプライマリメモリ１５０２に記憶されたプログラムを実行することによって、キャッシュサーバの動作が実現され、ＣＰＵ１５０１が通信バス１５０３に接続された全ての構成要素にアクセス可能となる。
【００５０】
セカンダリメモリ１５０５はデータのための記憶スペースを提供する。セカンダリメモリ１５０５は不揮発性のメモリであり、プライマリメモリ１５０２は揮発性のメモリである。ネットワークインタフェースコントローラ１５０４はキャッシュサーバ自身の外部のコンポーネントとの通信を実現する。
【００５１】
図１に示すキャッシュサーバ３６０Ａ〜３６０Ｎのハードウェア構成は、図３に示すキャッシュサーバのハードウェア構成と同じである。
【００５２】
図４は、実施例１のガーディアンとなるキャッシュサーバによって実行される処理のフローチャートである。
【００５３】
クライアントに最も近いキャッシュサーバは、ガーディアンとしてタスクを実行する。ガーディアンは、クライアントからコンテンツリクエストを受信する。
【００５４】
ガーディアンとなるキャッシュサーバは、コンテンツリクエストを受信した場合（１００１）、要求されるコンテンツの位置８０１を受信したコンテンツリクエストから抽出する。そして、ガーディアンは、要求されたコンテンツに対応するコンテンツの識別子のためのデリゲイトリストを仮想的なピアツーピアオーバーレイネットワークに要求する（１００２）。ガーディアンは、仮想的なピアツーピアオーバーレイネットワークからデリゲイトリスト８０２を受信する。デリゲイトリスト８０２は要求されたコンテンツを保持するキャッシュサーバの識別子を含む。要求されたコンテンツを保持するキャッシュサーバが存在しない場合、デリゲイトリスト８０２は他のキャッシュサーバのいかなる識別子も含まない。言い換えれば、デリゲイトリスト８０２は空のものであってもよい。ガーディアンは、コンテンツサーバ３２１の識別子をデリゲイトリスト８０２に追加してもよい。
【００５５】
もし、ガーディアンへの距離が遠いデリゲイトが要求されたコンテンツをクライアントに送信するように選択されたなら、送信されるコンテンツが多くのネットワークリンクを通り、多くのノード及びネットワークリンクが影響を受け、おそらく混雑を引き起こす。このため、ガーディアンからのネットワーク距離が所定値以上である全てのキャッシュサーバはデリゲイトリスト８０２から削除される。それらのキャッシュサーバに対して分散マックスフロー処理が実行されないようにするために、ガーディアンは、仮想コーディネイトシステム８０３の現在の状態及びデリゲイトリスト８０２を用いて、所定の距離関数を満たす（元の）デリゲイトリスト８０２に含まれているそれらキャッシュサーバ全てのデリゲイトの識別子を削除し（１００３）、減少デリゲイトリスト８０４を生成する。
【００５６】
ステップ１００３の処理では、キャッシュサーバは、仮想コーディネイトシステム８０３の各デリゲイトのネットワーク距離順にデリゲイトリスト８０２に含まれるデリゲイトの識別子をソートし、選択されたデリゲイトよりネットワーク距離が遠い全てのデリゲイトの識別子をデリゲイトリスト８０２から削除してもよい。
【００５７】
ある例では、ネットワーク距離が１０であるデリゲイトが選択されてもよい。他の例では、デリゲイトリスト８０２での位置がデリゲイトリスト８０２に含まれる全てのデリゲイトの数を３で除算した値に対応するデリゲイトが選択されてもよい。
【００５８】
キャッシュサーバは、減少デリゲイトリスト８０４から一つのデリゲイトを選択する（１００４）、選択されたデリゲイトに対して、トポロジ情報８０５を用いて分散マックスフロー処理を実行する（１００５）。もし、減少デリゲイトリスト８０４に分散マックスフロー処理１００５が実行されていないデリゲイトがあれば、このデリゲイトに分散マックスフロー処理が実行される（１００５）。もし、減少デリゲイトリスト８０４に含まれる全てのデリゲイトに分散マックスフロー処理が実行されたなら、キャッシュサーバは、ステップ１００６の処理を実行する。分散マックスフロー処理では、キャッシュサーバは、ガーディアンからステップ１００４の処理で選択されたデリゲイトまでのパスの容量を計算する。分散マックスフロー処理の詳細は、図５で説明する。
【００５９】
各デリゲイトに対する分散マックスフロー処理はマックスフロー値を返す。マックスフロー値は、ガーディアンからステップ１００４の処理で選択されたデリゲイトまでをつなぐ全てのパスの容量を示す値である。キャッシュサーバは、マックスフロー値をマックスフローリスト８０７に登録する。キャッシュサーバは、減少デリゲイトリスト８０４に含まれる全てのデリゲイトに分散マックスフロー処理を実行した後、マックスフローリスト８０７からデリゲイトを選択する（１００６）。ある例では、キャッシュサーバは、マックスフロー値が最大であるデリゲイトを最適なデリゲイトとして選択する。そして、キャッシュサーバは、ステップ１００２の処理で受信したコンテンツリクエストをステップ１００６の処理で選択されたデリゲイトに転送し（１００７）、処理を終了する。ステップ１００７の処理で転送されるコンテンツリクエストは、図２に示すメッセージ４３１に相当する。
【００６０】
デリゲイトは、ステップ１００７の処理で転送されたコンテンツリクエストを受信した場合、要求されたコンテンツを含むレスポンスをガーディアンに送信する。ガーディアンは、受信したレスポンスをクライアントに転送する。ガーディアンは、受信したレスポンスに含まれるコンテンツをセカンダリメモリ１５０５に記憶してもよい。この場合、ガーディアンは、仮想ピアツーピアオーバーレイネットワークのデリゲイトリストに、ガーディアンが記憶したコンテンツの識別子とガーディアンとなるキャッシュサーバの識別子との関係を追加するように更新する。
【００６１】
ある例では、もし、デリゲイトのセカンダリメモリ１５０５から要求されたコンテンツが削除されていた場合、デリゲイトによって送信されたレスポンスはエラーコードを含んでもよい。この場合、ガーディアンは、エラーコードを含むレスポンスを送信したデリゲイトを減少デリゲイトリスト８０４から削除した後、ステップ１００６の処理で他のデリゲイトを選択してもよい。
【００６２】
減少デリゲイトリスト８０４の全てのデリゲイトがエラーコードを含むレスポンスを送信した場合、ガーディアンは、コンテンツリクエストをコンテンツサーバ３２１に転送する。コンテンツサーバ３２１は、要求されたコンテンツを含むレスポンスをガーディアンを介してクライアント３０１に送信する。ガーディアンは、コンテンツサーバ３２１によって送信されたレスポンスを受信した場合、受信したレスポンスに含まれるコンテンツをセカンダリメモリ１５０５に記憶してもよい。また、ガーディアンは仮想ピアツーピアオーバーレイネットワークのデリゲイトリストを更新する必要がある。
【００６３】
次に、分散マックスフロー処理について図５及び図６を用いて説明する。図５は、実施例１のガーディアンによって実行される分散マックスフロー処理のフローチャートである。
【００６４】
まず、ガーディアンとなるキャッシュサーバは、サブグラフ８０６の送信のためのＵＵＩＤ（Ｕｎｉｖｅｒｓａｌ  Ｕｎｉｑｕｅ  Ｉｄｅｎｔｉｆｉｅｒ）を生成する（１１０１）。例えば、キャッシュサーバは、ＵＵＩＤ同士の重複を防止するために、ハッシュ関数を用いてＵＵＩＤを生成してもよい。ある例では、ハッシュ関数の入力は、ガーディアンのＩＰアドレス、及びガーディアンのＣＰＵ１５０１の識別子である。
【００６５】
そして、キャッシュサーバは、サブグラフ８０６を生成するサブグラフ初期化処理を実行する（１１０２）。サブグラフ初期化処理の詳細は図６で説明する。サブグラフ８０６のデータ構造の例の詳細は図７で説明する。
【００６６】
そして、キャッシュサーバは、分散マックスフロー処理の通常の初期化処理（１１０３）を実行し、分散マックスフロー処理を終了する。ステップ１１０３の処理では、キャッシュサーバは、ガーディアンからステップ１００４の処理で選択されたデリゲイトまでの限定サブグラフ８０６に含まれるパスの容量を計算する。容量が計算されるパスは限定サブグラフ８０６に含まれる。また、ステップ１１０３の処理では、キャッシュサーバは、限定サブグラフ８０６に含まれるキャッシュサーバに、プッシュメッセージに限定サブグラフ８０６を含めて送信する。パスの容量の計算処理の詳細は非特許文献１に記載される。
【００６７】
図６は、実施例１のサブグラフ初期化処理のフローチャートである。
【００６８】
まず、ガーディアンは、トポロジ情報８０５を無閉路のグラフ８０８に変換する。そして、ガーディアンは、グラフ８０８に基づいて、ガーディアンと選択されたデリゲイトとの間の最短のネットワーク距離８０９を計算する（１２０１）。ある例では、キャッシュサーバは、ダイクストラ法の最短経路優先アルゴリズムを用いて、最短パスを計算する。
【００６９】
そして、キャッシュサーバは、ステップ１２０１の処理で計算された最短パスのネットワーク距離８０９及び限定要素８１０を用いて、限定長を計算する（１２０２）。例えば、限定要素８１０は、キャッシュサーバのプライマリメモリ１５０２に記憶されている。ある例では、キャッシュサーバは、ネットワーク距離８０９に限定要素８１０を積算することによって限定長を計算する。他の例では、キャッシュサーバは、ネットワーク距離８０９に限定要素８１０を加算することによって限定長を計算してもよい。
【００７０】
そして、キャッシュサーバは、グラフ８０８のガーディアンからデリゲイトまでの全てのパスのうち、パスの長さが最短パスのネットワーク距離８０９以上であって、かつ、ステップ１２０２の処理で計算された限定長以下であるパスを特定する（１２０３）。キャッシュサーバは、ステップ１２０３の処理で特定されたパスをパスリスト８１１に登録する。パスリスト８１１はサブグラフを生成するために用いられる。
【００７１】
そして、キャッシュサーバは、パスリスト８１１を用いて、サブグラフ８０６を生成し（１２０４）、サブグラフ初期化処理を終了する。サブグラフ８０６は、グラフ８０８及びパスリスト８１１のノード及びエッジを含む。
【００７２】
図７は、実施例１のサブグラフ８０６のデータ構造の説明図である。サブグラフ８０６は、キャッシュサーバのプライマリメモリ１５０２に記憶され、他のキャッシュサーバにプッシュメッセージで送信される。
【００７３】
サブグラフ８０６のデータ構造は、ＵＵＩＤフィールド１４０１、エッジ数フィールド１４０２、及びエッジ１４０３Ａ〜１４０３Ｎのフィールドを含む。各エッジフィールド１４０３Ａ〜１４０３Ｎは、始点ノードフィールド１４０４及び終点ノードフィールド１４０５を含む。
【００７４】
ＵＵＩＤフィールド１４０１には、ステップ１１０１の処理で生成されたＵＵＩＤが登録される。ハッシュ値がＵＵＩＤに用いられる例では、ＵＵＩＤの容量が固定されている。これによって、ＵＵＩＤフィールド１４０１の値は簡単にデコードされる。エッジ数フィールド１４０２には、サブグラフ８０６のエッジ集合Ｅ”に含まれるエッジの数を示す値が登録される。ある例では、エッジ数フィールド１４０２の容量が固定されていてもよい。これによって、エッジ数フィールド１４０２に書き込まれるエッジ数は簡単にデコードされる。サブグラフ８０６に含まれるエッジ１４０３Ａ〜１４０３Ｎの数はエッジ数フィールド１４０２に登録された値が示す数と同じである。始点ノードフィールド１４０４には、エッジの始点となるキャッシュサーバやルータや他のネットワーク装置の識別子が登録される。終点ノードフィールド１４０５には、エッジの終点となるキャッシュサーバやルータや他のネットワーク装置の識別子が登録される。ある例では、始点ノード１４０４及び終点ノード１４０５に登録される識別子は、キャッシュサーバやルータや他のネットワーク装置のＩＰアドレスである。
【００７５】
次に、サブグラフ８０６を含むプッシュメッセージを受信した場合のガーディアンでないキャッシュサーバによって実行される処理について図８を用いて説明する。図８は、実施例１のプッシュメッセージを受信した場合にガーディアンでないキャッシュサーバによって実行される処理のフローチャートである。
【００７６】
まず、キャッシュサーバは、ガーディアンによって送信された新たなＵＵＩＤを含むプッシュメッセージを受信する（１３０１）。新たなＵＵＩＤは、キャッシュサーバが今まで受信したプッシュメッセージに含まれるＵＵＩＤと異なる。受信したプッシュメッセージに含まれるＵＵＩＤが新たなＵＵＩＤでない場合、そのプッシュメッセージを無視する。ある例では、キャッシュサーバは、受信したプッシュメッセージに含まれるＵＵＩＤが登録されたリストをセカンダリメモリ１５０５に記憶する。キャッシュサーバは、受信したプッシュメッセージに含まれるＵＵＩＤがリストにない場合、受信したプッシュメッセージに含まれるＵＵＩＤをそのリストに加える。
【００７７】
そして、キャッシュサーバは、受信したプッシュメッセージに含まれるサブグラフ８０６のデータ構造を構文解析する（１３０２）。そして、キャッシュサーバは、サブグラフ８０６を用いて、グラフ８０８を更新又は生成する（１３０３）。
【００７８】
ある例では、キャッシュサーバは、サブグラフ８０６を用いて、プライマリメモリ１５０２に記憶される一時的なグラフ８０８を生成する。また、キャッシュサーバは、各キャッシュサーバでわずかに異なる可能性があるトポロジ情報８０５と受信したプッシュメッセージに含まれるサブグラフ８０６との組み合わせを用いて、新たなグラフ８０８を生成し、トポロジ情報８０５を更新する。これによって、キャッシュサーバは、トポロジ情報８０５に含まれていなかったノードを追加でき、又は、更新されたグラフ８０８に含まれないノードを削除できる。
【００７９】
そして、キャッシュサーバは、分散マックスフロー処理の通常の初期化処理を実行し（１３０４）、プッシュメッセージ受信時の処理を終了する。ステップ１３０４の処理の詳細は非特許文献１に記載される。
【００８０】
本実施例では、ガーディアンが、ガーディアンとデリゲイトとの間の少なくとも一つのパスから所定の条件を満たす全てのパスを特定する。そして、ガーディアンは、それらのパスに対して分散マックスフロー処理を実行し、各デリゲイトまでのマックスフロー容量を計算する。これによって、分散マックスフロー処理が使用するノードの数が減少するので、マックスフローの計算中に通信されるメッセージの数を減少させることができる。したがって、本実施例は、ノードの数が多い分散キャッシュシステムであっても、ネットワーク全体の状況を考慮してコンテンツを送信するキャッシュサーバを選択するキャッシュサーバ選択装置を提供できる。
【００８１】
ガーディアンからのネットワーク距離が長いデリゲイトによってコンテンツが送信された場合、ネットワークの混雑が引き起こされる。このため、本実施例では、ガーディアンは、ガーディアンへの所定のネットワーク距離以下のデリゲイトのみに着目し、さらに、分散マックスフロー計算に基づいて所定の条件を満たすパスのみに着目する。これによって、不要なネットワークを混雑を引き起こすような不要な長いパスが計算中に考慮されないため、マックスフローの容量を計算するために通信されるメッセージの数を効率的に減少させることができる。
【００８２】
ある例では、ガーディアンと何らかの一つのデリゲイトとの間のパスを選択するための条件は、ガーディアンとデリゲイトとの間の最短パスの距離に関連してもよい。他の例では、考えられる他のパラメータを含んでもよい。これは、例えば、最短パスの長さに関連する条件に関連して、考慮されるパスの数を減少させるので、ガーディアンとデリゲイトとの間のマックスフローの容量の計算中に通信されるメッセージの数を効率的に減少させることができる。
【００８３】
また、本実施例では、ガーディアンとなるキャッシュサーバは、所定の条件を満たす各キャッシュサーバへの全てのパスのサブグラフ情報を複数のキャッシュサーバに送信する。複数のキャッシュサーバは、最新であるかもしれないし、各キャッシュサーバが把握していない情報を含んでいるかもしれない受信したサブグラフ情報に基づいてそれらのトポロジ情報を更新する。これによって、各キャッシュサーバが分散して自身のトポロジ情報を管理する場合であっても、このトポロジ情報は全体として正確なトポロジにまとまる。
【実施例２】
【００８４】
実施例１では、ガーディアンとなるキャッシュサーバは、図６に示すステップ１２０４の処理でサブグラフ８０６を含むプッシュメッセージを送信する。実施例２では、ガーディアンとなるキャッシュサーバは、ＴＴＬ（Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ）を含むプッシュメッセージを送信する。ガーディアンでないキャッシュサーバは、プッシュメッセージを受信した場合、図８に示すステップ１３０２及び１３０３の処理を実行せず、ステップ１３０４の処理を実行する。
【００８５】
本実施例によれば、ガーディアンは、図６に示すステップ１２０２の処理で計算された限定長をＴＴＬの値として用いる。キャッシュサーバは、プッシュメッセージを送信する場合、ＴＴＬの値を図７に示すエッジ数フィールド１４０２に書き込む。ガーディアンとなるキャッシュサーバによって送信されたプッシュメッセージはエッジフィールド１４０３Ａ〜１４０３Ｎを含まない。
【００８６】
ガーディアンでないキャッシュサーバは、プッシュメッセージを受信した場合、受信したプッシュメッセージに含まれるＴＴＬから所定値を減算する。例えば、この値は１である。ガーディアンでないキャッシュサーバは、再計算されたＴＴＬが０であれば、受信したプッシュメッセージを無視する。ガーディアンでないキャッシュサーバは、減算されたＴＴＬが０でなければ、非特許文献１に記載された分散マックスフロー処理を実行する。
【００８７】
本実施例では、ガーディアンから遠く、ＴＴＬが０となるノードは計算に考慮されないため、デリゲイトが選択された後の送信中に使用されないので、送信されたプッシュメッセージに限定サブグラフ８０６を含まずとも、ネットワークの混雑を防止できる。
【００８８】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることも可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【００８９】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、又は、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【００９０】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない、実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【符号の説明】
【００９１】
１００  通信システム
１０１  キャリアネットワーク
１０２  コンテンツネットワーク
２０１  ネットワークリンク
３０１  クライアント
３２１  コンテンツサーバ
３４０Ａ、３４０Ｍ  ルータ
３６０Ａ〜３６０Ｎ  キャッシュサーバ
【図１】
2016046785.tif 000003
【図２】
2016046785.tif 000004
【図３】
2016046785.tif 000005
【図４】
2016046785.tif 000006
【図５】
2016046785.tif 000007
【図６】
2016046785.tif 000008
【図７】
2016046785.tif 000009
【図８】
2016046785.tif 000010