(57)【要約】【課題】階層型分散キャッシュシステムにおいて、ネットワーク全体のトータルコストを削減する。【解決手段】キャッシュ制御装置は、分散キャッシュシステムの外部から受信するリクエストの量を表すリクエスト情報、ＴＴＬ初期値、配信木ルートを表す配信木ルート情報に基づいて、キャッシュミスに起因して分散キャッシュシステム内で転送されるリクエストの伝搬量を推定するリクエスト伝搬推定部と、リクエスト伝搬推定部により推定されるリクエストの伝搬量に基づいて、リクエストに対応するデータを格納および配信するためのトータルコストを推定するコスト推定部と、コスト推定部により推定されるコストを小さくするようにＴＴＬ初期値を更新するＴＴＬ決定部を有する。【選択図】図４
2016048498.tif 000002
【特許請求の範囲】
【請求項１】
階層的に接続された複数のノードにそれぞれキャッシュメモリが設けられており、あるリクエストに対してキャッシュミスが発生したときにそのリクエストが予め決められている配信木ルートの上位側のノードへ転送される分散キャッシュシステムにおいて、前記キャッシュメモリにデータが格納される時間を表すＴＴＬ（Time-To-Live）初期値を決定するキャッシュ制御装置であって、
各ノードが前記分散キャッシュシステムの外部から受信するリクエストの量を表すリクエスト情報を前記複数のノードから収集する収集部と、
前記リクエスト情報、前記複数のノードに設定されているＴＴＬ初期値、前記配信木ルートを表す配信木ルート情報に基づいて、キャッシュミスに起因して前記分散キャッシュシステム内で転送されるリクエストの伝搬量を推定するリクエスト伝搬推定部と、
前記リクエスト伝搬推定部により推定されるリクエストの伝搬量、所定量のデータを格納するために要するコストを表すメモリコスト情報、所定量のデータを伝送するために要するコストを表す配信コスト情報に基づいて、前記リクエストに対応するデータを格納および配信するためのトータルコストを推定するコスト推定部と、
前記コスト推定部により推定されるコストを小さくするようにＴＴＬ初期値を更新するＴＴＬ決定部と、
を有するキャッシュ制御装置。
【請求項２】
第１のノードが前記分散キャッシュシステムの外部から第１のレートでリクエストを受信するときに、前記リクエスト伝搬推定部は、現在のＴＴＬ初期値および前記第１のレートに基づいて前記第１のノードにおけるキャッシュミス率を推定し、前記第１のレートおよび前記第１のノードにおけるキャッシュミス率に基づいて、前記第１のノードから前記第１のノードの上位に接続される第２のノードへ転送されるリクエストの伝搬レートを表す第２のレートを推定する
ことを特徴とする請求項１に記載のキャッシュ制御装置。
【請求項３】
前記リクエスト伝搬推定部は、現在のＴＴＬ初期値および前記第２のレートに基づいて前記第２のノードにおけるキャッシュミス率を推定し、前記第２のレートおよび前記第２のノードにおけるキャッシュミス率に基づいて、前記第２のノードから前記第２のノードの上位に接続される第３のノードへ転送されるリクエストの伝搬レートを表す第３のレートを推定する
ことを特徴とする請求項２に記載のキャッシュ制御装置。
【請求項４】
前記コスト推定部は、所定の範囲内の複数のＴＴＬ初期値に対してそれぞれトータルコスト値を計算し、
前記ＴＴＬ決定部は、前記コスト推定部により計算される複数のトータルコスト値のなかで最小のトータルコスト値に対応するＴＴＬ初期値を選択し、現在のＴＴＬ初期値を選択したＴＴＬ初期値に更新する
ことを特徴とする請求項１に記載のキャッシュ制御装置。
【請求項５】
前記ＴＴＬ決定部は、現在のＴＴＬ初期値に対するトータルコストの傾きに基づいて前記ＴＴＬ初期値を更新する
ことを特徴とする請求項１に記載のキャッシュ制御装置。
【請求項６】
前記ＴＴＬ決定部は、前記トータルコストの傾きが負であるときにＴＴＬ初期値を所定量だけ大きくし、前記トータルコストの傾きが正であるときにＴＴＬ初期値を所定量だけ小さくする
ことを特徴とする請求項５に記載のキャッシュ制御装置。
【請求項７】
階層的に接続された複数のノードにそれぞれキャッシュメモリが設けられており、あるリクエストに対してキャッシュミスが発生したときにそのリクエストが予め決められている配信木ルートの上位側のノードへ転送される分散キャッシュシステムにおいて、前記キャッシュメモリにデータが格納される時間を表すＴＴＬ（Time-To-Live）初期値を、コンピュータを用いて決定するキャッシュ制御方法であって、
各ノードが前記分散キャッシュシステムの外部から受信するリクエストの量を表すリクエスト情報を前記複数のノードから収集し、
前記リクエスト情報、前記複数のノードに設定されているＴＴＬ初期値、前記配信木ルートを表す配信木ルート情報に基づいて、キャッシュミスに起因して前記分散キャッシュシステム内で転送されるリクエストの伝搬量を推定し、
推定されるリクエストの伝搬量、所定量のデータを格納するために要するコストを表すメモリコスト情報、所定量のデータを伝送するために要するコストを表す配信コスト情報に基づいて、前記リクエストに対応するデータを格納および配信するためのトータルコストを推定し、
推定されるコストを小さくするようにＴＴＬ初期値を更新する
ことを特徴とするキャッシュ制御方法。
【請求項８】
各ノードにおいて、現在のＴＴＬ初期値および下位側のノードから通知されるリクエスト伝搬量の推定値に基づいて、上位側のノードへのリクエスト伝搬量および自ノードが前記リクエストに対応するデータを格納および配信するためのコストが推定され、
各ノードにおいて推定されたリクエスト伝搬量を表すノードリクエスト情報および推定されたコストを表すノードコスト情報が、前記配信木ルート情報に基づいて、それぞれ対応する上位側のノードへ通知され、
最上位に位置するノードにおいて、各ノードから通知されるノードリクエスト情報およびノードコスト情報に基づいて、ＴＴＬ初期値が更新される
ことを特徴とする請求項７に記載のキャッシュ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内の複数のノードに配置されたキャッシュメモリを制御する装置および方法に係わる。
【背景技術】
【０００２】
トラヒックを削減して効率的に配信するための技術の１つとしてネットワークキャッシュ（In-network Caching）システムが提案されている。ネットワークキャッシュシステムにおいては、コンテンツデータのコピーがネットワーク上の１または複数のキャッシュサーバに格納され、ユーザの近くに位置するキャッシュサーバからコンテンツが配信される。
【０００３】
このようなシステムでは、より多くのキャッシュサーバにコンテンツデータのコピーが格納されるほど、ネットワークで処理されるトラヒック量が削減され、トラヒック配信コスト（例えば、帯域使用量）が削減される。ただし、多くのキャッシュサーバにコンテンツデータのコピーが格納されると、例えば、各キャッシュサーバのメモリ容量を大きくする必要があるので、メモリ利用に伴うコストが増加する。このため、ネットワーク全体のコストを削減するためには、トラヒック配信コストおよびメモリ利用コストの双方を考慮する必要がある。
【０００４】
近年では、物理ネットワークリソースから仮想ネットワークを構築し、その仮想ネットワークを構成するノード及びリンクに対して必要なリソースを割り当てる技術（例えば、ＮＦＶ：Network Function Virtualization）が注目されている。さらに、ＮＦＶプラットフォーム上で実現されるアプリケーションの１つとして、各ノードにキャッシュ機能を付与することで、コンテンツのキャッシュ配置の制約を緩和するための技術（例えば、ＣＣＮ：Content Centric Networking）が知られている。ＣＣＮが適用される仮想ネットワークでは、コンテンツを配信するサーバが存在するノードをルートノードとして、階層的に複数のキャッシュノードが接続される配信木が自動的に構築される。
【０００５】
配信木上の各キャッシュノードは、ユーザから受信するリクエストに対応するコンテンツデータを格納しているか否かを判定する。そして、キャッシュノードは、リクエストに対応するコンテンツデータを格納しているときは、そのコンテンツデータをユーザに配信する。一方、リクエストに対応するコンテンツデータを格納していないときは、キャッシュノードは、配信木の上位側のノードへリクエストを転送する。そして、キャッシュノードは、上位側のノードから受信するコンテンツデータをユーザへ配信する。このとき、キャッシュノードは、上位側のノードから受信するコンテンツデータを自ノード内のキャッシュメモリに格納する。ただし、このような階層型の分散キャッシュシステムでは、どのキャッシュノードにどのコンテンツデータを格納するのかによって、トラヒック配信量およびキャッシュ利用効率は変化する。
【０００６】
他方、従来より、データの生存期間（ＴＴＬ：Time-To-Live）を利用してキャッシュノードにおいて無駄なデータを削除する技術が知られている。この場合、キャッシュノードは、ＴＴＬ期間内にリクエストを受信しないコンテンツを削除する。ここで、ＴＴＬが大きいときは、各キャッシュノードにコンテンツデータが格納されている確率が高いので、ユーザに近いキャッシュノードからデータが配信される。よって、ネットワーク内のトラヒックは削減されるが、各キャッシュノードにおいてメモリの利用量が増大する。一方、ＴＴＬが小さいときは、キャッシュミスが発生する確率が高くなる。キャッシュミスが発生すると、上位側のノードへリクエストを転送する処理が必要となり、また、コンテンツが配信されるルートが長くなるので、トラヒック配信コストが高くなる。
【０００７】
このように、ネットワーク内のトラヒック配信コストおよびメモリ利用コストは、ＴＴＬの値に対してトレードオフの関係を有する。
【０００８】
なお、キャッシュノードにおけるＴＴＬを決定する方法については、例えば、下記の特許文献１、２に記載されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００４−２９５８４５号公報
【特許文献２】特開２０１２−２１２２０８号公報（特許第５３４８１６７号）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述のように、トラヒック配信コストおよびメモリ利用コストを含むトータルコストを削減するためには、ＴＴＬの値を適切に決定する必要がある。ところが、階層型の分散キャッシュシステムでは、あるリクエストに対してキャッシュミスが発生した場合、上位側のノードへそのリクエストが転送される。このため、各キャッシュノードのコンテンツキャッシュの性能が上位ノードに影響を与え、ネットワーク全体のトータルコストに対するＴＴＬの寄与を特定することが困難である。すなわち、従来技術では、ネットワーク全体のトータルコストを計算して削減することは容易ではない。
【００１１】
本発明の１つの側面に係わる目的は、階層型分散キャッシュシステムにおいて、ネットワーク全体のトータルコストを削減することである。
【課題を解決するための手段】
【００１２】
本発明の１つの態様のキャッシュ制御装置は、階層的に接続された複数のノードにそれぞれキャッシュメモリが設けられており、あるリクエストに対してキャッシュミスが発生したときにそのリクエストが予め決められている配信木ルートの上位側のノードへ転送される分散キャッシュシステムにおいて、前記キャッシュメモリにデータが格納される時間を表すＴＴＬ（Time-To-Live）初期値を決定する。このキャッシュ制御装置は、各ノードが前記分散キャッシュシステムの外部から受信するリクエストの量を表すリクエスト情報を前記複数のノードから収集する収集部と、前記リクエスト情報、前記複数のノードに設定されているＴＴＬ初期値、前記配信木ルートを表す配信木ルート情報に基づいて、キャッシュミスに起因して前記分散キャッシュシステム内で転送されるリクエストの伝搬量を推定するリクエスト伝搬推定部と、前記リクエスト伝搬推定部により推定されるリクエストの伝搬量、所定量のデータを格納するために要するコストを表すメモリコスト情報、所定量のデータを伝送するために要するコストを表す配信コスト情報に基づいて、前記リクエストに対応するデータを格納および配信するためのトータルコストを推定するコスト推定部と、前記コスト推定部により推定されるコストを小さくするようにＴＴＬ初期値を更新するＴＴＬ決定部と、を有する。
【発明の効果】
【００１３】
上述の態様によれば、階層型分散キャッシュシステムにおいて、ネットワーク全体のトータルコストを削減することができる。
【図面の簡単な説明】
【００１４】
【図１】分散キャッシュシステムが動作するネットワークの一例を示す図である。
【図２】ノード装置の構成の一例を示す図である。
【図３】キャッシュ制御方法の実施例を示す図である。
【図４】キャッシュ制御装置の機能を示すブロック図である。
【図５】トータルコストについて説明する図である。
【図６】キャッシュ制御方法の処理を示すフローチャートである。
【図７】キャッシュ制御装置のハードウェア構成の一例を示す図である。
【図８】推定されるリクエスト伝搬の一例を示す図である。
【図９】配信コストについて説明する図である。
【図１０】リクエスト伝搬を推定する計算の実施例を示す図である。
【図１１】ＴＴＬ初期値とトータルコストの関係を示す図である。
【図１２】ＴＴＬ初期値を導出するシミュレーションのモデルを示す図である。
【図１３】掃引探索によるシミュレーション結果を示す。
【図１４】オンライン探索によるシミュレーション結果を示す。
【図１５】他の実施形態によりＴＴＬ初期値を決定する方法を説明する図である。
【図１６】他の実施形態によりＴＴＬ初期値を決定するシーケンスを示す。
【発明を実施するための形態】
【００１５】
図１は、分散キャッシュシステムが動作するネットワークの一例を示す。このネットワークは、図１（ａ）に示すように、複数のノードＮ１〜Ｎ６を含む。各ノードＮ１〜Ｎ６には、スイッチまたはルータ等のデータ通信装置が設けられている。以下の記載では、各ノードに設けられているデータ通信装置を「ノード装置」または単に「ノード」と呼ぶことがある。
【００１６】
各ノードは、物理リンクを介して１または複数の他のノードに接続されている。なお、図１（ａ）においてノード間を接続する線は、物理リンクを表している。例えば、ノードＮ３は、物理リンクを介してノードＮ２、Ｎ５、Ｎ６に接続されている。物理リンクは、例えば、光ファイバである。或いは、物理リンクは、無線リンクであってもよい。各ノードＮ１〜Ｎ６は、それぞれユーザを収容することができ、また、他のネットワークと接続することもできる。
【００１７】
ノード装置は、コンテンツの配信を要求するリクエストをユーザから受信すると、そのリクエストに対応するコンテンツデータをユーザに提供する。ここで、各ノードには、キャッシュメモリが設けられている。そして、ノード装置は、要求されたコンテンツが自ノードのキャッシュに格納されているときは（キャッシュヒット）、そのコンテンツデータをユーザに送信する。一方、要求されたコンテンツが自ノードのキャッシュに格納されていないときは（キャッシュミス）、ノード装置は、受信したリクエストを他のノードへ転送する。リクエストの転送先は、予め作成されている配信木に従う。
【００１８】
図１（ｂ）は、図１（ａ）に示す物理ネットワーク上に構成される分散キャッシュシステムの一例を示す。分散キャッシュシステムは、予め作成されている配信木を提供する仮想ネットワークによって実現される。配信木は、コンテンツが配信されるルートを指定する。なお、図１（ｂ）に示す例では、コンテンツデータの原本は、ノードＮ１に接続されているコンテンツサーバに格納されているものとする。この場合、ノードＮ１を「根ノード」と呼ぶことがある。
【００１９】
上記構成の分散キャッシュシステムにおいてキャッシュミスが発生したときは、受信リクエストは配信木の上位側のノードへ転送される。例えば、ノードＮ３においてキャッシュミスが発生したときは、受信リクエストはノードＮ３からノードＮ２へ転送される。ここで、このリクエストに対応するコンテンツデータがノードＮ２に格納されていれば、そのコンテンツデータがノードＮ２からノードＮ３へ配信される。そして、ノードＮ３からユーザへそのコンテンツデータが転送される。このとき、ノードＮ３のキャッシュには、このコンテンツデータのコピーが格納される。なお、上述のリクエストに対応するコンテンツデータがノードＮ２にも格納されていないときは、そのリクエストはさらにノードＮ２からノードＮ１へ転送される。
【００２０】
図２は、ノード装置の構成の一例を示す。ノード装置は、図２に示すように、通信ポートＰ、通信ポートＱ、キャッシュメモリ１１、リクエスト処理部１２、廃棄制御部１３、リクエストモニタ１４を有する。通信ポートＰは、分散キャッシュシステム内の他のノードに接続される。通信ポートＱは、分散キャッシュシステム外のネットワークに接続される。具体的には、通信ポートＱは、例えば、ユーザに接続される。
【００２１】
キャッシュメモリ１１は、コンテンツデータを格納することができる。図２に示す例では、キャッシュメモリ１１には、コンテンツＡ、Ｂ、．．．が格納されている。リクエスト処理部１２は、通信ポートＰまたは通信ポートＱを介して受信するコンテンツ配信リクエストを処理する。すなわち、受信したコンテンツ配信リクエストに対応するコンテンツデータがキャッシュメモリ１１に格納されているときは、リクエスト処理部１２は、そのコンテンツデータをリクエストの送信元へ配信する。一方、受信したコンテンツ配信リクエストに対応するコンテンツデータがキャッシュメモリ１１に格納されていないときは、リクエスト処理部１２は、配信木の上位側のノードへそのリクエストを転送する。
【００２２】
廃棄制御部１３は、ＴＴＬ（Time-To-Live）値に従って、キャッシュメモリ１１に格納されているコンテンツデータを廃棄する。ＴＴＬ初期値は、後述するキャッシュ制御装置１から与えられる。
【００２３】
図３は、キャッシュ制御方法の実施例を示す。キャッシュメモリに格納されているデータは、ＴＴＬ値によって管理される。すなわち、新たなデータがキャッシュメモリに格納されたときに、そのデータに対応するＴＴＬ値は、ＴＴＬ初期値に設定される。ＴＴＬ値は、時間経過に応じて一定のレートで減少する。そして、ＴＴＬ値がゼロになると、キャッシュメモリに格納されているデータは廃棄される。
【００２４】
図３（ａ）に示すポリシ１では、キャッシュがヒットしたときに、ＴＴＬ値は、ＴＴＬ初期値に更新される。この場合、キャッシュヒット率の推定値は、（１）式に示す関数ｆで表される。
【数１】
2016048498.tif 000003
λは、リクエストレートを表す。リクエストレートは、所定時間内に受信するリクエストの個数を表す。すなわち、ポリシ１では、リクエストレートλが高いほど、キャッシュヒット率が高くなる。また、ＴＴＬ初期値が大きいほど、キャッシュヒット率が高くなる。なお、リクエストレートλおよびＴＴＬ初期値は、この例では、コンテンツ毎に指定される。（１）式において、添え字ｃは、リクエストレートλおよびＴＴＬ初期値がコンテンツ毎に指定されることを表している。
【００２５】
図３（ｂ）に示すポリシ２では、キャッシュがヒットしても、ＴＴＬ値はＴＴＬ初期値に更新されない。この場合、キャッシュヒット率の推定値は、（２）式に示す関数ｆで表される。
【数２】
2016048498.tif 000004
なお、以下の記載では、廃棄制御部１３は、例えば、図３（ａ）に示すポリシ１でキャッシュメモリ１１を管理する。ただし、本発明は、この方法に限定されるものではない。すなわち、廃棄制御部１３は、図３（ｂ）に示すポリシ２でキャッシュメモリ１１を管理してもよい。
【００２６】
リクエストモニタ１４は、ノード装置が受信するリクエストの個数（即ち、受信リクエストレート）をモニタする。ただし、リクエストモニタ１４は、分散キャッシュシステムの外から受信するリクエストをカウントする。すなわち、リクエストモニタ１４は、分散キャッシュシステム内の他のノードから転送されてくるリクエストはカウントしない。例えば、図１（ｂ）に示すノードＮ３において、リクエストモニタ１４は、ユーザから受信するリクエストをカウントする。一方、ノードＮ２において、リクエストモニタ１４は、ノードＮ３から転送されてくるリクエストをカウントしない。なお、各ノードのリクエストモニタ１４は、コンテンツ毎にリクエストレートをモニタする。
【００２７】
実施形態に係る分散キャッシュシステムは、図１（ｂ）に示すように、キャッシュ制御装置１を有する。キャッシュ制御装置１は、この例では、根ノード（すなわち、ノードＮ１）に設けられているが、他のノードに設けられるようにしてもよい。そして、キャッシュ制御装置１は、コンテンツ毎に、各ノードに設定するキャッシュメモリのＴＴＬ初期値を決定する。この実施例では、各ノードに同じＴＴＬ初期値が設定される。
【００２８】
図４は、キャッシュ制御装置１の機能を示すブロック図である。キャッシュ制御装置１は、リクエスト情報収集部２、リクエスト伝搬推定部３、コスト推定部４、ＴＴＬ決定部５を有する。なお、キャッシュ制御装置１は、図示していない他の機能を有していてもよい。
【００２９】
リクエスト情報収集部２は、各ノードのリクエストモニタ１４により測定された受信リクエストレートを表すリクエスト情報を収集する。リクエスト情報収集部２は、例えば、定期的に、各ノードからリクエスト情報を収集する。
【００３０】
リクエスト伝搬推定部３は、リクエスト情報収集部２によって収集されるリクエスト情報、各ノードに設定されているＴＴＬ初期値、配信木ルート情報に基づいて、分散キャッシュシステム内で転送されるリクエストの伝搬量を推定する。配信木ルート情報は、上述したように、コンテンツが配信されるルートを指定する。また、配信木ルート情報は、例えば、ネットワーク管理者によって予め作成される。なお、リクエストは、あるノードにおいてキャッシュミスが発生したときに、他のノードへ転送される。すなわち、リクエスト伝搬推定部３は、キャッシュミスに起因して分散キャッシュシステム内で転送されるリクエストの伝搬量を推定する。
【００３１】
コスト推定部４は、リクエスト伝搬推定部３により推定されるリクエストの伝搬量、基準メモリコスト情報、基準配信コスト情報に基づいて、リクエストに対応するデータを格納および配信するためのトータルコストを推定する。基準メモリコスト情報は、所定量のデータを格納するために要するコストを表し、例えば、メモリデバイスの価格などに応じて予め決定される。基準メモリコストは、例えば「円／ビット」で表される。基準配信コスト情報は、所定量のデータを配信するために要するコストを表し、通信料金などに応じて予め決定される。基準配信コストは、例えば「円／ビット・ホップ数」で表される。
【００３２】
ＴＴＬ決定部５は、コスト推定部４により推定されるトータルコストを小さくするＴＴＬ初期値を決定する。すなわち、ＴＴＬ決定部５は、分散キャッシュシステム全体のコストが小さくなるように（好ましくは、最小化するように）ＴＴＬ初期値を決定する。
【００３３】
分散キャッシュシステムにおいてコンテンツデータを格納および配信するためのトータルコストは、メモリコストおよび配信コストの和で表される。ここで、ＴＴＬ初期値が大きいと、キャッシュメモリにデータが格納されている時間が長くなる。よって、ＴＴＬ初期値が大きいときは、メモリコストも大きくなる。一方、ＴＴＬ初期値が大きいと、各ノードのキャッシュメモリにデータが格納されている確率が高いので、ユーザに近いノードからデータが配信される確率が高い。よって、ＴＴＬ初期値が大きいときは、配信コストは小さくなる。したがって、トータルコストは、図５に示すように、ＴＴＬ初期値に対して最小値または極小値を有する。そこで、ＴＴＬ決定部５は、コンテンツデータを格納および配信するためのトータルコストが最小または極小に近づくように、ＴＴＬ初期値を決定する。なお、以下の記載では、「最小」は「極小」を含むものとする。
【００３４】
図６は、本発明の実施形態に係わるキャッシュ制御方法の処理を示すフローチャートである。このフローチャートの処理は、例えば、分散キャッシュシステムにおいて定期的に実行される。また、このフローチャートの処理は、例えば、コンテンツ毎に実行される。
【００３５】
Ｓ１において、各ノードのリクエストモニタ１４は、それぞれリクエストレートを測定する。このとき、リクエストモニタ１４は、分散キャッシュシステムの外部から受信するリクエストをカウントする。そして、リクエストレートの測定結果を表すリクエスト情報は、各ノードからキャッシュ制御装置１へそれぞれ送信される。
【００３６】
Ｓ２〜Ｓ５の処理は、キャッシュ制御装置１により実行される。即ち、Ｓ２において、リクエスト情報収集部２は、各ノードからリクエスト情報を収集する。Ｓ３において、リクエスト伝搬推定部３は、リクエスト情報、現在のＴＴＬ初期値、配信木ルート情報に基づいて、分散キャッシュシステム内で転送されるリクエストの伝搬量を推定する。Ｓ４において、コスト推定部４は、リクエストの伝搬量、基準メモリコスト情報、基準配信コスト情報に基づいて、リクエストに対応するデータを格納および配信するためのトータルコストを推定する。Ｓ５において、ＴＴＬ決定部５は、コスト推定部４により推定されるトータルコストを小さくするＴＴＬ初期値を決定する。
【００３７】
Ｓ６において、キャッシュ制御装置１は、Ｓ２〜Ｓ５において決定したＴＴＬ初期値を各ノードに設定する。そうすると、各ノードにおいて、廃棄制御部１３は、キャッシュ制御装置１により設定されるＴＴＬ初期値を利用してキャッシュメモリ１１を管理する。具体的には、新たなＴＴＬ初期値を利用して、図３（ａ）または図３（ｂ）に示すデータ廃棄処理が行われる。
【００３８】
図７は、キャッシュ制御装置１のハードウェア構成の一例を示す。キャッシュ制御装置１は、図７に示すコンピュータシステム１００を含む。コンピュータシステム１００は、ＣＰＵ１０１、メモリ１０２、記憶装置１０３、読み取り装置１０４、通信インタフェース１０６、および入出力装置１０７を備える。ＣＰＵ１０１、メモリ１０２、記憶装置１０３、読み取り装置１０４、通信インタフェース１０６、入出力装置１０７は、例えば、バス１０８を介して互いに接続されている。
【００３９】
ＣＰＵ１０１は、メモリ１０２を利用して、図６に示すフローチャートのＳ２〜Ｓ５の処理を記述したキャッシュ制御プログラムを実行する。これにより、図４に示すリクエスト情報収集部２、リクエスト伝搬推定部３、コスト推定部４、ＴＴＬ決定部５の機能が提供される。すなわち、上述したキャッシュ制御方法が実現される。メモリ１０２は、例えば半導体メモリであり、ＲＡＭ領域およびＲＯＭ領域を含んで構成される。記憶装置１０３は、例えばハードディスク装置であり、上述のキャッシュ制御プログラムを格納する。なお、記憶装置１０３は、フラッシュメモリ等の半導体メモリであってもよい。また、記憶装置１０３は、外部記憶装置であってもよい。
【００４０】
読み取り装置１０４は、ＣＰＵ１０１の指示に従って着脱可能記録媒体１０５にアクセスする。着脱可能記録媒体１０５は、例えば、半導体デバイス（ＵＳＢメモリ等）、磁気的作用により情報が入出力される媒体（磁気ディスク等）、光学的作用により情報が入出力される媒体（ＣＤ−ＲＯＭ、ＤＶＤ等）などにより実現される。通信インタフェース１０６は、ＣＰＵ１０１の指示に従ってネットワークを介してデータを送信および受信することができる。入出力装置１０７は、ユーザからの指示を受け付けるデバイス等を含む。
【００４１】
実施形態のキャッシュ制御プログラムは、例えば、下記の形態でコンピュータシステム１００に提供される。
（１）記憶装置１０３に予めインストールされている。
（２）着脱可能記録媒体１０５により提供される。
（３）プログラムサーバ１１０から提供される。
【００４２】
図８は、推定されるリクエスト伝搬の一例を示す。この実施例では、分散キャッシュシステムは、ノードＮ１〜Ｎ５を有する。ノードＮ１は、根ノードであり、コンテンツサーバに接続されている。ノードＮ１の下流にノードＮ２が接続されている。ノードＮ２の下流にノードＮ３およびノードＮ４が接続されている。ノードＮ４の下流にノードＮ５が接続されている。なお、この例では、説明を簡単にするために、各ノードにおける推定キャッシュヒット率が５０パーセントであるものとする。すなわち、各ノードにおける推定キャッシュミス率は、５０パーセントである。
【００４３】
上述の分散キャッシュシステムにおいて、ノードＮ４は、所定のモニタ期間内にノードＮ４に収容されているユーザから８個のリクエストを受信するものとする。この場合、ノードＮ４のリクエストモニタ１４により「受信リクエストレートｒ４＝８」が得られる。なお、図８において、「ｒｉ」は、ノードＮｉにおいて分散キャッシュシステムの外部から受信するリクエストの受信レートを表す。
【００４４】
ここで、ノードＮ４における推定キャッシュミス率は、５０パーセントである。すなわち、ノードＮ４において、８個の受信リクエストのうちの４個のリクエストについてキャッシュミスが発生すると推定される。よって、４個のリクエストがノードＮ４からノードＮ２へ転送されると推定される。すなわち「伝搬リクエストレートλ(2,4)＝４」が得られる。なお、図８において、「λ(x,i)」は、ノードＮｉにおいて受信されたリクエストのうち、ノードＮｘまで伝搬するリクエストの伝搬レートを表す。
【００４５】
ノードＮ２における推定キャッシュミス率も、５０パーセントである。すなわち、ノードＮ２において、ノードＮ４から受信する４個のリクエストのうちの２個のリクエストについてキャッシュミスが発生すると推定される。よって、ノードＮ４から受信する４個のリクエストのうちの２個のリクエストがノードＮ２からノードＮ１へ転送されると推定される。すなわち「伝搬リクエストレートλ(1,4)＝２」が得られる。
【００４６】
同様に、ノードＮ５における受信リクエストに対して以下の推定結果が得られる。４個のリクエストがノードＮ５からノードＮ３へ転送される（λ(3,5)＝４）。２個のリクエストがノードＮ５からノードＮ３を経由してノードＮ２へ転送される（λ(2,5)＝２）。そして、１個のリクエストがノードＮ５からノードＮ３、Ｎ２を経由してノードＮ１へ転送される（λ(1,5)＝１）。
【００４７】
上述の推定は、キャッシュ制御装置１のリクエスト伝搬推定部３により行われる。すなわち、リクエスト伝搬推定部３は、ノードＮ４、Ｎ５においてそれぞれ測定される受信リクエストレートを表すリクエスト情報に基づいて、各ノード間の伝搬リクエストレートを推定する。なお、リクエスト伝搬推定部３は、コンテンツ毎に、上述の推定を行う。
【００４８】
なお、上述の例では、各ノードのキャッシュヒット率は、固定的に与えられているが、実際には、キャッシュ制御装置１（たとえば、リクエスト伝搬推定部３）により推定される。すなわち、各ノードのキャッシュヒット率は、例えば、上述した（１）式により推定される。
【００４９】
例えば、ノードＮ３におけるキャッシュヒット率は、（１）式を利用して、ノードＮ３における推定リクエストレート「λ(3,5)」および現在のＴＴＬ初期値に基づいて算出される。また、ノードＮ２におけるキャッシュヒット率は、（１）式を利用して、推定リクエストレート「λ(2,4)＋λ(2,5)」および現在のＴＴＬ初期値に基づいて算出される。
【００５０】
このようにしてリクエスト伝搬推定部３により分散キャッシュシステム内のリクエストの伝搬が推定された後、コスト推定部４は、リクエスト伝搬推定部３による推定結果を利用してトータルメモリコストおよびトータル配信コストを推定する。トータルメモリコストは、各ノードにおけるメモリコストの和である。そして、各ノードにおけるメモリコストは、下式で表される。
メモリコスト＝Costsθcｆ
Costsは、上述した基準メモリコストを表し、分散キャッシュシステムに対して予め与えられる定数である。θcは、リクエストに対応するコンテンツのデータサイズを表す。ｆは、キャッシュヒット率を表し、例えば、上述した（１）式により推定される。なお、キャッシュヒット率は、目的データがメモリに格納されている確率を表す。すなわち、キャッシュヒット率は、目的データがメモリを使用している確率を表す。よって、この実施例では、メモリコストは、キャッシュヒット率に比例する。
【００５１】
Costsおよびθcは、既知である。また、キャッシュヒット率を推定する関数ｆは、推定リクエストレートおよび現在のＴＴＬ初期値に基づいて決まる。ＴＴＬ初期値は、キャッシュ制御装置１により決定されるので、既知である。よって、コスト推定部４は、各ノードにおける推定リクエストレートに基づいてメモリコストを推定できる。なお、推定リクエストレートは、受信レートおよび伝搬レートの和で表される。例えば、図８に示す例では、ノードＮ４のリクエストレートは「ｒ４」である。また、ノードＮ２のリクエストレートは、「λ(2,4)＋λ(2,5)」である。
【００５２】
図９は、配信コストについて説明する図である。なお、分散キャッシュシステムの構成は、図８および図９において同じである。また、図９に示す配信コストの推定は、図８に示すリクエスト伝搬についての推定結果を利用する。
【００５３】
トータル配信コストは、コンテンツデータが配信されるルート毎の配信コストの和である。ここで、図８に示す推定結果が得られている場合、コスト推定部４は、図９に示す７つの配信ルートについて配信コストを推定する。図９において、Ｄ(i)は、ノードＮｉにおいてキャッシュがヒットし、ノードＮｉからユーザにコンテンツデータが配信されるルートを表す。Ｄ(a,b,c,...,i)は、ノードＮａから配信されるコンテンツデータがノードＮｂ、Ｎｃ、．．．、Ｎｉを経由してユーザに転送される配信ルートを表す。
【００５４】
各配信ルートについての配信コストは、下式で表される。
配信コスト＝CostbＨ*Ｋ
Costbは、上述した基準配信コストを表し、分散キャッシュシステムに対して予め与えられる定数である。Ｈは、ルートのホップ数であり、配信木ルート情報により指定される。Ｋは、配信されるコンテンツデータの個数（または、配信回数）を表す。ここで、各ノードから配信されるコンテンツデータの個数は、各ノードにおけるキャッシュヒットの回数に相当する。よって、例えば、ノードＮ４は、４個のコンテンツデータをユーザに配信する。また、ノードＮ１からノードＮ２、Ｎ４を経由して２個のコンテンツデータがユーザに配信される。下記に、各配信ルートについてのホップ数Ｈおよび配信回数Ｋを示す。
Ｄ(4):Ｈ＝１、Ｋ＝４
Ｄ(2,4):Ｈ＝２、Ｋ＝２
Ｄ(1,2,4):Ｈ＝３、Ｋ＝２
Ｄ(5):Ｈ＝１、Ｋ＝４
Ｄ(2,5):Ｈ＝２、Ｋ＝２
Ｄ(2,3,5):Ｈ＝３、Ｋ＝１
Ｄ(1,2,3,5):Ｈ＝４、Ｋ＝１
【００５５】
CostbおよびＨは、既知である。Ｋは、受信リクエストレートおよび推定キャッシュヒット率から算出されるので、リクエスト伝搬推定部３による推定結果から得られる。すなわち、コスト推定部４は、リクエスト伝搬推定部３による推定結果に基づいて各配信ルートの配信コストを推定できる。
【００５６】
次に、図１０を参照しながら、リクエスト伝搬を推定する計算の実施例について説明する。リクエスト伝搬は、コンテンツ毎に行われる。このため、以下に示す計算式では、コンテンツ毎に計算が実行されることを表すために、添え字ｃを付することがある。
【００５７】
リクエストの伝搬は、下記の（３）式で表される。
【数３】
2016048498.tif 000005
（３）式において、伝搬リクエスト行列Λは、各ノードに伝搬されるリクエストレートを表す。伝搬確率行列Ｄは、各ノードにおいてリクエストが上位ノードへ転送される確率を表す。受信行列Ｒは、各ノードにおいて分散キャッシュシステムの外部から受信するリクエストの受信レートを表す。Ｍは、分散キャッシュシステム内のノードの個数を表す。Ｎは、分散キャッシュシステムの外部からリクエストを受信するノードの個数を表す。
【００５８】
ただし、（３）式では、繰返し演算により伝搬リクエスト行列Λが求められる。すなわち、（３）式において、変数ｓは、繰返し演算の実行回数を表す。そして、分散キャッシュシステムの最大ホップ数に達するまで変数ｓを１ずつインクリメントしながら上記計算を繰り返すことにより、伝搬リクエスト行列Λの各成分が算出される。以下では、図１０に示すモデルに基づいてリクエスト伝搬を推定する計算について説明する。なお、図１０に示すモデルは、図８に示す実施例の構成と実質的に同じである。
【００５９】
分散キャッシュシステムは、図１０に示すように、５個のノード１〜５を有する。すなわち、Ｍ＝５である。また、分散キャッシュシステムの外部からリクエストを受信するノードは、２個（ノード４、５）である。すなわち、Ｎ＝２である。よって、伝搬リクエスト行列Λおよび受信行列Ｒは、それぞれ５×２行列（５行×２列）で表される。また、分散キャッシュシステムの最大ホップ数は４である。なお、この実施例では、便宜上、あるノードからその同じノードまでのホップ数を「１」と規定する。よって、例えば、あるノードからその隣接ノードまでのホップ数は「２」である。
【００６０】
伝搬確率行列Ｄは、Ｍ×Ｍ行列で表される。すなわち、図１０に示す分散キャッシュシステムにおいては、伝搬確率行列Ｄは、５×５行列で表される。伝搬確率行列Ｄの各要素は、リクエストが上位ノードへ転送される確率を表す。すなわち、伝搬確率行列Ｄの各要素は、キャッシュミス率を表す。なお、「ｆ」がキャッシュヒット率を表すので、「１−ｆ」はキャッシュミス率を表す。ここで、伝搬確率行列Ｄの列はリクエストの転送元のノードに対応し、伝搬確率行列Ｄの行はリクエストの転送先のノードに対応する。例えば、伝搬確率行列Ｄの要素(1,2)は、ノード２においてキャッシュミスが発生してリクエストがノード１へ転送される確率を表す。同様に、伝搬確率行列Ｄの要素(2,3)は、ノード３においてキャッシュミスが発生してリクエストがノード２へ転送される確率を表す。伝搬確率行列Ｄの要素(4,3)は、ノード４においてキャッシュミスが発生してリクエストがノード２へ転送される確率を表す。伝搬確率行列Ｄの要素(5,3)は、ノード５においてキャッシュミスが発生してリクエストがノード３へ転送される確率を表す。なお、伝搬確率行列Ｄの他の要素は、ゼロである。
【００６１】
リクエスト伝搬推定部３は、上述したように、変数ｓをインクリメントしながら（３）式の計算を繰返し実行する。よって、リクエスト伝搬推定部３は、まず、ｓ＝１に対して（３）式の計算を実行する。このとき、伝搬リクエスト行列Λ[s=1]の各要素（即ち、各リクエストレートλ）は、ゼロであるものとする。また、ノード４、５における受信レートｒ4、ｒ5は、測定により得られている。よって、伝搬リクエスト行列Λ[s+1=2]において、λ(4,4)＝ｒ4およびλ(5,5)＝ｒ5が得られる。また、これらの計算結果に応じて、ノード４、５のキャッシュミス率が推定される。すなわち、リクエストレートλ(4,4)およびＴＴＬ初期値に基づいてノード４におけるキャッシュヒット率が推定され、リクエストレートλ(5,5)およびＴＴＬ初期値に基づいてノード５におけるキャッシュヒット率が推定される。キャッシュヒット率は、例えば、上述した（１）式で推定される。
【００６２】
リクエスト伝搬推定部３は、ｓ＝２に対して（３）式の計算を実行する。即ち、ノード４のリクエストレートλ(4,4)およびノード４のキャッシュミス率の積を計算することにより、ノード４からノード２へ向かうリクエストの伝搬レートλ(2,4)が算出される。同様に、ノード５のリクエストレートλ(5,5)およびノード５のキャッシュミス率の積を計算することにより、ノード５からノード３へ向かうリクエストの伝播レートλ(3,5)が算出される。さらに、これらの計算結果に応じてノード２、３のキャッシュミス率が推定される。すなわち、リクエストレートλ(2,4)およびＴＴＬ初期値に基づいてノード２におけるキャッシュヒット率が推定され、リクエストレートλ(3,5)およびＴＴＬ初期値に基づいてノード３におけるキャッシュヒット率が推定される。
【００６３】
リクエスト伝搬推定部３は、ｓ＝３に対して（３）式の計算を実行する。すなわち、ノード２のリクエストレートλ(2,4)およびノード２のキャッシュミス率の積を計算することにより、ノード４からノード２を経由してノード１へ向かうリクエストの伝播レートλ(1,4)が算出される。同様に、ノード３のリクエストレートλ(3,5)およびノード３のキャッシュミス率の積を計算することにより、ノード５からノード３を経由してノード２へ向かうリクエストの伝播レートλ(2,5)が算出される。
【００６４】
ただし、ノード２は、ノード４およびノード３の双方からリクエストを受信し得る。したがって、ノード２におけるキャッシュミス率は、ノード４から受信するリクエストの伝搬レートλ(2,4)、およびノード５からノード３を経由して受信するリクエストの伝搬レートλ(2,5)の和に基づいて算出される。よって、リクエスト伝搬推定部３は、リクエストレート「λ(2,4)＋λ(2,5)」およびＴＴＬ初期値に基づいてノード２におけるキャッシュヒット率を更新する。
【００６５】
リクエスト伝搬推定部３は、ｓ＝４に対して（３）式の計算を実行する。すなわち、リクエストレートλ(2,4)および更新されたノード２のキャッシュミス率に基づいて、ノード４からノード２を経由してノード１へ向かうリクエストの伝播レートλ(1,4)が算出される。また、リクエストレートλ(2,5)および更新されたノード２のキャッシュミス率に基づいて、ノード５からノード３およびノード２を経由してノード１へ向かうリクエストの伝播レートλ(1,5)が算出される。このようにして、７つのリクエストレートλが推定される。なお、伝搬リクエスト行列Λの他の要素はゼロである。
【００６６】
伝搬確率行列Ｄは、配信木ルート情報に基づいて作成される。たとえば、配信木ルート情報において、ノード２の上位側にノード１が設けられていることが定義されている。この場合、ノード２のキャッシュミス率は、伝搬確率行列Ｄにおいて、ノード１に対応する行（すなわち、第１行）およびノード２に対応する列（すなわち、第２列）により特定される要素として設定される。
【００６７】
次に、分散キャッシュシステムのトータルコストを推定する計算式について説明する。トータルコストは、上述したように、メモリコストおよび配信コストの和で表される。よって。コンテンツｃのトータルコストＪは、下式で表される。
【数４】
2016048498.tif 000006
Costs：基準メモリコスト[cost/bit]
Costb：基準配信コスト[cost/bit]
θc：コンテンツｃのデータサイズ[bit]
Ｈ：分散キャッシュシステムのホップ数行列
ｆ：キャッシュヒット率関数
λ(i,k)：ノードｋにおいて分散キャッシュシステムの外部から受信され、ノードｉへ伝搬されるリクエストの伝搬レート
【００６８】
伝搬リクエスト行列Λは、上述したように、リクエスト伝搬推定部３によって作成される。また、図１０に示す分散キャッシュシステムのホップ数行列Ｈは、下式により表される。
【数５】
2016048498.tif 000007
なお、ホップ数行列Ｈの列はリクエストの転送元のノードに対応し、ホップ数行列Ｈの行はリクエストの転送先のノードに対応する。
【００６９】
（４）式の右辺の第１項は、トータルメモリコストを表す。トータルメモリコストは、基準メモリコスト、データサイズ、総キャッシュヒット率の積で表される。総キャッシュヒット率は、各ノードにおけるキャッシュヒット率の和である。
【００７０】
（４）式の右辺の第２項は、配信コスト（又は、帯域コスト）を表す。配信コストは、配信ルート毎の配信コストの和に相当する。配信ルート毎の配信コストは、基準配信コスト、ホップ数、リクエストレート、キャッシュヒット率の積で表される。
【００７１】
（４）式の右辺の第３項は、根ノード（図１０に示す例では、ノード１）においてキャッシュミスが発生したときの配信コストを表す。なお、根ノードにおいてキャッシュミスが発生したときは、根ノードに設けられているキャッシュサーバは、コンテンツサーバからコンテンツデータを取得してユーザへ配信する。
【００７２】
次に、ＴＴＬ初期値を決定する方法の実施例を説明する。ＴＴＬ初期値は、コスト推定部４により推定されるトータルコストＪを小さくするように決定される。ここで、トータルコストＪは、メモリコストおよび配信コストの和である。また、上述したように、ＴＴＬ初期値が大きくなると、メモリコストは大きくなり、配信コストは小さくなる。したがって、トータルコストＪは、図１１に示すように、あるＴＴＬ初期値に対して最小値を有する。そこで、ＴＴＬ決定部５は、トータルコストＪが小さくなるＴＴＬ初期値（好ましくは、トータルコストＪが最小になるＴＴＬ初期値）を探索する。
【００７３】
ＴＴＬ決定部５は、掃引探索またはオンライン探索によりＴＴＬ初期値を決定する。掃引探索においては、上述した（４）式を利用して、所定の範囲に渡って「ＴＴＬ」を掃引しながらそれぞれトータルコストＪを計算する。例えば、ＴＴＬ＝１〜３００秒の範囲において１秒間隔でトータルコストＪが計算される。この場合、３００個の計算結果が得られる。そして、ＴＴＬ決定部５は、３００個の計算結果のなかで、トータルコストＪが最小となるＴＴＬ初期値を選択する。
【００７４】
このように、掃引探索においては、トータルコストＪを最小化するＴＴＬ初期値が特定される。このため、リクエストレートの変動が大きい場合には、掃引探索を利用して短い時間で好適なＴＴＬ初期値を特定することが好ましい。ただし、掃引探索は、後述するオンライン探索と比較して、ＴＴＬ決定部５の演算量が多くなる。
【００７５】
オンライン探索においては、ＴＴＬ初期値に対するトータルコストＪの傾き（即ち、微分）を利用してトータルコストＪが最小となるＴＴＬ初期値がサーチされる。すなわち、トータルコストＪの傾きが負であれば、トータルコストＪが最小となるＴＴＬ初期値は、現在のＴＴＬ初期値よりも大きいと判定される。この場合、ＴＴＬ決定部５は、ＴＴＬ初期値をΔｔ（例えば、１秒）だけ大きくする。一方、トータルコストＪの傾きが正であれば、トータルコストＪが最小となるＴＴＬ初期値は、現在のＴＴＬ初期値よりも小さいと判定される。この場合、ＴＴＬ決定部５は、ＴＴＬ初期値をΔｔだけ小さくする。なお、トータルコストＪの傾きがゼロまたは実質的にゼロであれば、現在のＴＴＬ初期値は、トータルコストＪを最小にするＴＴＬ初期値であると判定される。この場合、ＴＴＬ決定部５は、現在のＴＴＬ初期値を維持する。
【００７６】
ＴＴＬ決定部５によるオンライン検索の演算は、下式で表される。
【数６】
2016048498.tif 000008
「ａ」は、予め指定された時間Δｔを表し、例えば１秒である。
【００７７】
上述のようにして更新されたＴＴＬ初期値は、各ノードに設定される。したがって、ＴＴＬ決定部５がオンライン探索でＴＴＬ初期値を更新するときは、図６に示すフローチャートの処理を繰返し実行することにより、ＴＴＬ初期値が徐々に最適値に近づいていく。
【００７８】
なお、上述の記載では、コンテンツ毎にキャッシュメモリにＴＴＬ初期値が設定され、コンテンツ毎にそのＴＴＬ初期値が更新されるが、本発明はこの方式に限定されるものではない。例えば、本発明は、サービス（ビデオストリーミングサービス、ＷＥＢサービス等）毎にＴＴＬ初期値が設定される分散キャッシュシステムにも適用可能である。
【００７９】
サービス毎にＴＴＬ初期値が設定される分散キャッシュシステムにおけるオンライン探索の演算は、下式で表される。
【数７】
2016048498.tif 000009
Ｃsは、対象となるサービスに属するコンテンツの集合を表す。すなわち、サービス毎にＴＴＬ初期値を更新する場合、キャッシュ制御装置１は、対象となるサービスに属する各コンテンツについてトータルコストＪを推定し、各トータルコストＪの微分の和に基づいてＴＴＬ初期値を更新する。
【００８０】
このように、キャッシュ制御装置１は、分散キャッシュシステムの外部から流入するリクエストの量に基づいて、各ノードのキャッシュヒット率およびノード間のリクエスト伝搬率を推定する。また、キャッシュ制御装置１は、これらの推定結果を利用してコンテンツデータを格納および配信するためのトータルコストを小さくする（好ましくは、最小にする）ＴＴＬ初期値を決定する。そして、各ノードのキャッシュサーバは、キャッシュ制御装置１により決定されるＴＴＬ初期値に従って各コンテンツを管理する。よって、本発明の実施形態の構成および方法によれば、キャッシュミスに起因するリクエスト伝搬が発生する分散キャッシュシステムにおいても、トータルコストを小さくするＴＴＬ初期値を決定することができる。
【００８１】
＜シミュレーション＞
図１２は、ＴＴＬ初期値を導出するシミュレーションのモデルを示す。このシミュレーションの分散キャッシュシステムにおいては、図１２に示すように、第１レイヤに１台のキャッシュノード（根ノード）が設けられている。根ノードには、コンテンツデータを格納するコンテンツサーバが接続されている。また、根ノードの下位レイヤには、４台のキャッシュノードが接続されている。第２レイヤの各キャッシュノードには、それぞれ４台のキャッシュノードが接続されている。すなわち、第３レイヤには１６台のキャッシュノードが設けられている。第３レイヤの各キャッシュノードには、それぞれ４台のキャッシュノードが接続されている。すなわち、第４レイヤには６４台のキャッシュノードが設けられている。このように、このシミュレーションの分散キャッシュシステムは、８５台のキャッシュノードを有する。
【００８２】
ユーザからのリクエストは、第４レイヤのキャッシュノードにより受信される。リクエストの分布は、Zipf(1.2)分布に従う。基準メモリコストCostsは0.03であり、基準配信コストCostbは0.97である。コンテンツのデータサイズは１である。
【００８３】
図１３は、掃引探索によるシミュレーション結果を示す。ここでは、図３（ａ）に示すポリシ１および図３（ｂ）に示すポリシ２についてシミュレーションが行われている。また、この掃引探索では、３つのコンテンツ（Ｃ１〜Ｃ３）について、ＴＴＬ初期値＝１〜３００秒の範囲において１秒間隔でトータルコストＪが計算されている。そして、トータルコストＪが最小となるＴＴＬ初期値が選択される。
【００８４】
図１４は、オンライン探索によるシミュレーション結果を示す。オンライン探索においては、ＴＴＬ初期値＝１５０秒から探索が開始される。すなわち、このシミュレーションの開始時において、各キャッシュノードに対してＴＴＬ初期値＝１５０秒が設定されているものとする。そして、キャッシュ制御装置１は、まず、各キャッシュノードの受信リクエストレートを表すリクエスト情報を取得する。そして、キャッシュ制御装置１は、収集したリクエスト情報に基づいてトータルコストＪを計算し、さらにそのトータルコストＪの傾きを計算する。ここで、例えば、コンテンツＣ１についてのトータルコストＪの傾きは負である。この場合、キャッシュ制御装置１は、現在のＴＴＬ初期値に「Δｔ＝１」を加算し、各キャッシュノードにＴＴＬ初期値＝１５１秒を設定する。
【００８５】
続いて、キャッシュ制御装置１は、各キャッシュノードの受信リクエストレートを表すリクエスト情報を取得する。また、キャッシュ制御装置１は、収集したリクエスト情報に基づいてトータルコストＪを計算し、さらにそのトータルコストＪの傾きを計算する。そして、キャッシュ制御装置１は、トータルコストＪの傾きに基づいてＴＴＬ初期値を更新する。以降、キャッシュ制御装置１は、定期的に上記処理を実行する。
【００８６】
＜他の実施形態＞
上述の実施形態では、分散キャッシュシステムに対して設けられるキャッシュ制御装置１が最適なＴＴＬ初期値を決定する。しかし、本発明は、この構成に限定されるものではない。例えば、各ノードにおいて伝搬リクエストレートおよびコストが推定され、推定結果がそれぞれ上位ノードへ送信される構成であってもよい。この場合、最上位ノード（根ノード）においてＴＴＬ初期値が決定される。
【００８７】
図１５は、他の実施形態によりＴＴＬ初期値を決定する方法を説明する図である。この実施例では、分散キャッシュシステムは、ノード１〜６を有する。ノード１が根ノードである。ノード１の下位側にノード２、５が接続され、ノード２の下位側にノード３、４が接続され、ノード５の下位側にノード６が接続されている。ノード３、４、６が分散キャッシュシステムの外部からリクエストを受信する。
【００８８】
この場合、分散キャッシュシステムのエッジノードにおいて受信リクエストレートが測定される。すなわち、ノード３、４、６は、それぞれ分散キャッシュシステムの外部から受信するリクエストの量を測定する。
【００８９】
各ノード３、４、６は、現在のＴＴＬ初期値および測定したリクエストレートに基づいて、キャッシュミスに起因して上位ノードに転送されるリクエストの量および自ノードのコスト値を推定し、さらにそのコスト値の微分を計算する。コスト値は、メモリコストおよび配信コストを含む。例えば、ノード３は、ノード３からノード２へ転送されるリクエストの伝搬レートλ(2,3)およびノード３のコストＪ3を推定し、コストの微分ｄＪ3／ｄＴＴＬを計算する。そして、各ノード３、４、６は、推定結果および計算結果を上位ノードに通知する。
【００９０】
各ノード２、５は、現在のＴＴＬ初期値および下位ノードから通知された情報に基づいて、キャッシュミスに起因して上位ノードに転送するリクエストの量および自ノードのコスト値を推定し、さらにそのコスト値の微分を計算する。例えば、ノード２は、現在のＴＴＬ初期値およびノード３から通知される伝搬リクエストレートλ(2,3)に基づいて、ノード３からノード２を経由してノード１へ転送されるリクエストの伝搬レートλ(1,3)を推定する。また、ノード２は、現在のＴＴＬ初期値およびノード４から通知される伝搬リクエストレートλ(2,4)に基づいて、ノード４からノード２を経由してノード１へ転送されるリクエストの伝搬レートλ(1,4)を推定する。さらに、ノード２は、コストＪ2を推定し、コストの微分ｄＪ2／ｄＴＴＬを計算する。そして、各ノード２、５は、推定結果おおよび計算結果を上位ノードに通知する。また、各ノード２、５は、下位ノードから受信したコストの微分値を上位ノードへ転送する。
【００９１】
ノード１は、現在のＴＴＬ初期値およびノード２、５から通知された情報に基づいて、ノード１のコスト値を推定し、さらにそのコスト値の微分を計算する。そして、ノード１は、各ノード（ノード１を含む）において計算されたコスト値の微分の総和を計算する。すなわち、下記の計算が実行される。
【数８】
2016048498.tif 000010
さらに、ノード１は、その総和に基づいてＴＴＬ初期値を更新する。すなわち、下記の計算が実行される。
【数９】
2016048498.tif 000011
そして、ノード１は、更新したＴＴＬ初期値を各ノードに通知する。
【００９２】
図１６は、他の実施形態によりＴＴＬ初期値を決定するシーケンスを示す。他の実施形態では、指定された制御間隔でＴＴＬ初期値が更新される。制御間隔は、特に限定されるものではないが、例えば１０秒である。各エッジノードは、図１６に示すように、制御間隔でリクエストレートを測定し、リクエスト伝搬レートおよびコストなどを推定する。また、各ノードの推定結果は、配信木の上位ノードに向かって通知される。そして、根ノードは、全ノードの推定結果を収集し、それらの推定結果を利用してＴＴＬ初期値を更新する。更新されたＴＴＬ初期値は、配信木の上位ノードから下位ノードに向かって順番に設定されてゆく。
【符号の説明】
【００９３】
１  キャッシュ制御装置
２  リクエスト情報収集部
３  リクエスト伝搬推定部
４  コスト推定部
５  ＴＴＬ決定部
１１  キャッシュメモリ
１２  リクエスト処理部
１３  廃棄制御部
１４  リクエストモニタ
【図１】
2016048498.tif 000012
【図２】
2016048498.tif 000013
【図３】
2016048498.tif 000014
【図４】
2016048498.tif 000015
【図５】
2016048498.tif 000016
【図６】
2016048498.tif 000017
【図７】
2016048498.tif 000018
【図８】
2016048498.tif 000019
【図９】
2016048498.tif 000020
【図１０】
2016048498.tif 000021
【図１１】
2016048498.tif 000022
【図１２】
2016048498.tif 000023
【図１５】
2016048498.tif 000024
【図１６】
2016048498.tif 000025
【図１３】
2016048498.tif 000026
【図１４】
2016048498.tif 000027