キャッシュシステム及びキャッシュ配置方法及びキャッシュ制御装置及びキャッシュ制御プログラム
【課題】 キャッシュ装置毎のコンテンツへの要求量を正確に予測する。
【解決手段】 本発明は、キャッシュ制御装置において、キャッシュ装置からコンテンツのアクセス履歴を受信し、キャッシュ装置毎の各コンテンツのアクセス数を集計し、集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングし、クラスタ毎に、属するキャッシュ装置のアクセス履歴を抽出して、時系列に並べた時系列データを生成し、時系列データについて、次の予測を行うまでの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定し、推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成してキャッシュ装置に送信することで、キャッシュ装置において、キャッシュ記憶手段の内容を書き換える。
【解決手段】 本発明は、キャッシュ制御装置において、キャッシュ装置からコンテンツのアクセス履歴を受信し、キャッシュ装置毎の各コンテンツのアクセス数を集計し、集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングし、クラスタ毎に、属するキャッシュ装置のアクセス履歴を抽出して、時系列に並べた時系列データを生成し、時系列データについて、次の予測を行うまでの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定し、推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成してキャッシュ装置に送信することで、キャッシュ装置において、キャッシュ記憶手段の内容を書き換える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュシステム及びキャッシュ配置方法及びキャッシュ制御装置及びキャッシュ制御プログラムに係り、特に、流通コンテンツの大容量・大規模化に伴うトラヒック削減を目的としたキャッシュを配置するためのキャッシュシステム及びキャッシュ配置方法及びキャッシュ制御装置及びキャッシュ制御プログラムに関する。
【背景技術】
【０００２】
流通コンテンツの大容量・大規模化に伴い、インターネットトラヒックは増加の一途を辿っている。そのため、トラヒック削減を目的として、キャッシュ技術が盛んに研究・開発されている。キャッシュ技術では、図７に示すように、キャッシュ装置３においてコンテンツを複製し、ユーザ４から要求があった場合、配信サーバ１に変わってデータを配信する。コンテンツ配信事業者にとってはサーバ負荷の低減、通信事業者にとってはトラヒック削減による設備コストの削減、ユーザにとってはレスポンス時間短縮によるQoE（Quality of Experience）の向上が利点である。
【０００３】
キャッシュ技術の性能向上に向け、コンテンツのアクセス履歴より、アクセスパターン解析やアクセス傾向予測をキャッシュ戦略に反映する技術が提案されている。この分野の従来技術は大きく２つに分類でき、コンテンツのアクセスパターンを利用したデータの事前配信技術と、コンテンツのアクセス傾向を利用したキャッシュの置き換え技術である。
アクセスパターンを利用した事前配信技術では、アクセス履歴を解析することにより、コンテンツのアクセスパターンを導き出す（例えば、特許文献１，２，３参照）。アクセスパターンとは、あるコンテンツがアクセスされた時に、その後に関連性の高い他のコンテンツがアクセスされやすいといったパターンである。アクセスパターンを利用することで、将来的にアクセスが予測されるコンテンツを、キャッシュ装置に事前配信しておくことで、ユーザへのレスポンス時間が向上する。
【０００４】
しかし、この技術は、人気コンテンツが定常状態にある場合は有効だが、短期的に人気コンテンツが変化する環境では、アクセスパターンを解析している間に人気コンテンツが変化してしまい、アクセスパターンの予測精度が低下する。特に、近年ネットワークにおいて支配的になっているビデオトラヒックにおいては、コンテンツのライフサイクルが短く、人気が短期的に急上昇・急下降する。さらに、予測精度が悪い場合は、アクセスされないコンテンツを事前配布することになり、無駄な容量と帯域を消費することになる。
【０００５】
コンテンツのアクセス傾向を利用したキャッシュの置き換え技術では、コンテンツアクセス数の時系列データから、将来的にコンテンツの人気度が上昇するか下降するかを予測し、キャッシュの置き換えに反映する。 この置き換え技術は、人気が増加するコンテンツに対しては優先的にキャッシュし、低下するコンテンツに対しては優先的に置き換えの対象とする。この技術では、コンテンツの人気度変動を早期に検出でき、短期的に人気コンテンツが変化する環境において特に有効である（例えば、特許文献４、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８-３９２９号公報
【特許文献２】特開２００７-１４８５５４号公報
【特許文献３】特開２００６-１３９３９８号公報
【特許文献４】特開２００３-２４２０２０号公報
【非特許文献】
【０００７】
【非特許文献１】土井等、"P2Pネットワークにおけるクエリトレンド変化を利用したキャッシング法"IEEE technical report 108 (123), 91-96, 2008-07-03.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
コンテンツのアクセス傾向を利用したキャッシュの置き換えの従来技術では、アクセス傾向を予測する際に、一定期間毎（タイムスロット毎）にコンテンツ毎のアクセス数をカウントし、現在のタイムスロットと一つ前のタイムスロットにおけるアクセス数の差分より人気の増減を判断している。そのため、直近アクセス数の変化量のみで人気を推定しており、短期的な人気度変動に過剰に反応し、全体の人気度傾向を把握できず、予測の精度が低下するといった課題がある。
【０００９】
また、従来技術はキャッシュ装置毎に予測を行っており、小規模なネットワーク事業者に設置されたキャッシュ装置だと、一定期間に十分な量のアクセス履歴が取得できないため、少ない統計データで予測を行うことになり、予測精度が低下する。これに対して、上位のサーバが複数のキャッシュ装置のアクセス履歴を収集することにより、十分な量の統計データを利用し、アクセス傾向を予測する手法が考えられる。しかし、この手法ではキャッシュ装置毎の人気コンテンツ傾向の違いが反映されない。キャッシュ装置毎の人気コンテンツ傾向の違いとは、あるキャッシュ装置では、人気があるコンテンツでも、他のキャッシュ装置では人気がないといった傾向の違いを指す。
【００１０】
本発明は、上記の点に鑑みなされたもので、上記の課題を解決し、コンテンツのアクセス傾向を利用したキャッシュの置き換え技術の高精度化が可能なキャッシュシステム及びキャッシュ配置方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の問題を解決するために、本発明（請求項１）は、配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムであって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有するキャッシュ制御装置を有し、
前記キャッシュ装置は、
アクセス履歴を格納するアクセス履歴記憶手段と、
前記ユーザ端末からのリクエストを受け付け、アクセス履歴を前記アクセス履歴記憶手段に格納し、所定の周期で該アクセス履歴を前記キャッシュ制御装置に送信する手段と、
コンテンツを格納するキャッシュ記憶手段と、
前記キャッシュ制御装置から取得した前記予測データに基づいて前記キャッシュ記憶手段の内容を書き換えるキャッシュ管理手段と、
を有する。
【００１２】
また、本発明（請求項２）は、請求項１の前記キャッシュ管理装置の前記予測データ生成手段において、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する。
【００１３】
また、本発明（請求項３）は、請求項１または2の前記キャッシュ管理装置の前記予測データ生成手段において、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む。
【００１４】
本発明（請求項４）は、配信サーバ、複数のキャッシュ装置、ユーザ端末、キャッシュ制御装置からなるキャッシュシステムにおけるキャッシュ配置方法であって、
前記キャッシュ装置は、前記ユーザ端末からのリクエストを受け付け、アクセス履歴をアクセス履歴記憶手段に格納し、所定の周期で前記キャッシュ制御装置に送信し、
前記キャッシュ制御装置は、
前記キャッシュ装置からコンテンツのアクセス履歴を受信し、履歴データ記憶手段に格納するアクセス履歴受信ステップと、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計ステップと、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリングステップと、
前記クラスタリングステップでクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出ステップと、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測ステップと、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成ステップと、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信ステップと、
を行い、
前記キャッシュ装置は、
前記キャッシュ制御装置から取得した前記予測データに基づいて、コンテンツを格納するキャッシュ記憶手段の内容を書き換える。
【００１５】
また、本発明（請求項５）は、請求項４の前記予測データ生成ステップにおいて、
前記アクセス傾向予測アルゴリズムのパラメータ調整をする。
【００１６】
また、本発明（請求項６）は、請求項４または５の前記予測データ生成ステップにおいて、
前記クラスタリングステップにおいて前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測ステップで算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する。
【００１７】
本発明（請求項７）は、配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムにおけるキャッシュ制御装置であって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、を有する。
【００１８】
また、本発明（請求項８）は、請求項７の前記予測データ生成手段において、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する。
【００１９】
また、本発明（請求項９）は、請求項７または８の前記予測データ生成手段において、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む。
【００２０】
本発明（請求項１０）は、請求項７乃至９のいずれか1項に記載のキャッシュ制御装置を構成する各手段としてコンピュータを機能させるためのキャッシュ制御プログラムである。
【発明の効果】
【００２１】
上記のように、本発明によれば、複数のキャッシュ装置を制御するキャッシュ制御装置において、キャッシュ装置毎にコンテンツのアクセス傾向を統計手法を用いて高精度に予測することにより、各キャッシュ装置におけるキャッシュヒット率が上昇する。それに伴い、ネットワークトラヒックの削減、配信サーバの負荷の削減、ユーザに対するレスポンス時間の短縮等の効果がある。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態におけるシステム全体の動作のフローチャートである。
【図３】本発明の一実施の形態におけるキャッシュ制御装置の構成図である。
【図４】本発明の一実施の形態におけるキャッシュ制御装置のフローチャートである。
【図５】本発明の一実施の形態におけるキャッシュ装置の構成図である。
【図６】本発明の一実施の形態におけるキャッシュ装置のフローチャートである。
【図７】従来のキャッシュ動作の概要を示す図である。
【発明を実施するための形態】
【００２３】
以下図面と共に、本発明の実施の形態を説明する。
【００２４】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００２５】
同図に示すシステムは、配信サーバ１０、キャッシュ制御装置２０、キャッシュ装置３０、ルータ４０、ユーザ端末５０から構成される。
【００２６】
キャッシュ制御装置２０は、十分に計算性能が確保されたマシンやIaaS (Infrastructure as a Service)等のクラウド基盤上に実装されることを前提とする。
【００２７】
各キャッシュ装置３０は、アクセス履歴をキャッシュ制御装置２０に定期的に送信する。アクセス履歴とは、リクエストされた時間、リクエストされたコンテンツの識別子、コンテンツサイズ等の情報を記憶したデータである。
【００２８】
図２は、本発明の一実施の形態におけるシステム全体の動作のフローチャートである。
【００２９】
ステップ１０１） キャッシュ装置３０は、保持していたアクセス履歴を定期的にキャッシュ制御装置１０に送信し（ステップ１０１）、キャッシュ制御装置２０では、キャッシュ装置３０からアクセス履歴を収集する（ステップ１０２）。キャッシュ制御装置２０は、収集した履歴データを利用し、コンテンツ毎のアクセス傾向を予測し（ステップ１０３）、その結果を各キャッシュ装置３０へ返信する（ステップ１０４）。キャッシュ装置３０は、キャッシュ制御装置２０から取得した、予測情報を元に、キャッシュ置き換え処理を行う（ステップ１０５）。
【００３０】
以下に、それぞれ装置の動作概要を説明する。
【００３１】
最初にキャッシュ制御装置１０について説明する。
【００３２】
図３は、本発明の一実施の形態におけるキャッシュ制御装置の構成図である。
【００３３】
キャッシュ制御装置２０は、履歴データ記憶DB（Data Base）２１，アクセス数集計部２２，クラスタリング部２３，時系列データ抽出部２４，アクセス傾向予測部２５，学習部２６，置き換え優先度作成部２７からなる。
【００３４】
履歴データ記憶部ＤＢ２１は、各キャッシュ装置３０から受信したアクセス履歴を格納する。アクセス履歴には、それぞれ各キャッシュ装置３０の識別子が付与されており、キャッシュ装置３０毎に格納するものとする。
【００３５】
アクセス数集計部２２は、履歴データ記憶ＤＢ２１からアクセス履歴を読み込み、各キャッシュ装置について、コンテンツ毎にアクセス数を集計し、クラスタリング部２３に出力する。
【００３６】
クラスタリング部２３は、集計されたアクセス数を取得してコンテンツのリクエスト傾向が似ているキャッシュ装置をクラスタリングする。リクエスト傾向を調べる方法は既存の方法を用いるものとする。
【００３７】
時系列データ抽出部２４は、クラスタリング部２３でクラスタリングされたグループに含まれるキャッシュ装置のアクセス履歴を履歴データ記憶ＤＢ２１から抽出し、これを時系列にソートして時系列データを生成する。
【００３８】
アクセス傾向予測部２５は、次の予測を開始するまでの人気コンテンツの人気度変化の傾向を、アクセス傾向予測アルゴリズムを用いて予測し、人気コンテンツの変化傾向データを出力する。
【００３９】
学習部２６は、アクセス傾向予測部２５が用いるアクセス傾向予測アルゴリズムのパラメータ調整を行う。
【００４０】
置き換え優先度作成部２７は、クラスタリング部２３から入力されるクラスタごとの各コンテンツのアクセス数及び、アクセス傾向予測部２５から入力される人気コンテンツの変化傾向データを用いて、置き換えスコアを計算する。置き換えスコアはスコアが小さいほど優先的にキャッシュ内容を置き換えるためのスコアである。生成された置き換えスコアを予測データとしてキャッシュ装置３０に送信する。
【００４１】
図４は、本発明の一実施の形態におけるキャッシュ制御装置の動作のフローチャートである。
【００４２】
各キャッシュ装置からアクセス履歴を受信すると（ステップ２０１）、収履歴データ記憶ＤＢ２１は、収集された情報を格納する（ステップ２０２）。
【００４３】
アクセス数集計部２２は、履歴データ記憶ＤＢ２１からアクセス情報を読み出し、キャッシュ装置毎に各コンテンツのアクセス数を集計する(ステップ２０３)。
【００４４】
次に、クラスタリング部２３では、キャッシュ装置３０毎に集計した各コンテンツのアクセス数を基に、コンテンツのリクエスト傾向の近いサーバ同士をクラスタリングする（ステップ２０４）。クラスタリングには、ウォード法、最短距離法、最長距離法、Ｋ平均法等の手法を用いる。これらの方法を利用しクラスタリングを行う際には、キャッシュ装置３０A，３０B間のコンテンツリクエスト傾向の非類似度を表す距離関数Dist(A, B)を定義する必要がある。実施例としては、人気度上位コンテンツの重複割合の逆数等があげられる。分類した各クラスタに対して、コンテンツCi毎のアクセス数Aiを集計する（ステップ２０５）。
【００４５】
時系列データ抽出部２４は、クラスタリング部２３によって分類したクラスタ単位で処理を行う。こうすることにより、類似した傾向を持つキャッシュ装置３０同士のログデータを共有することにより、精度が高い推定が可能であり、かつキャッシュ装置毎の傾向の違いにも対応が可能である。動作としては、まず、クラスタに属しているキャッシュ装置３０の過去のアクセス履歴を履歴データ記憶ＤＢ２１から抽出し、次にコンテンツ毎のアクセス数の時系列データをアクセス履歴から抽出する（ステップ２０６）。アクセス数の時系列データとは、あるタイムスロット毎に集計したアクセス数を時系列に並べたデータのことである。
【００４６】
アクセス傾向予測部２５は、時系列データ抽出部２４で抽出したアクセス数の時系列データより、次に予測を行うまでの期間のアクセスの人気度変化傾向Biを推定する（ステップ２０７）。アクセス傾向予測アルゴリズムには、ニューラルネットワーク、サポートベクターマシン、ベイズ推定等の機械学習技術を利用する。これらの手法は、株価予測等のデータの時系列変動予測によく利用されている。予測アルゴリズムに対しての、入出力データの一例として、下記のようなものが挙げられる。入力データとしては、コンテンツのアクセス数の時系列データを用いる。出力データとしては、人気度の変化傾向を示した値（上昇だったら"1"，下降だったら"０"）やアクセス数の変動率等が挙げられる。こうすることにより、従来の一つ前のタイムスロットの情報のみを利用した場合と比較して、高精度な予測が可能となる。
【００４７】
学習部２６は、履歴データ記憶DB２１から最新のアクセス履歴を読み出し（ステップ２０７）、学習データとして用いることにより、予測誤差が最小になるように、アクセス傾向予測アルゴリズムのパラメータの調整を行う（ステップ２０８）。この処理はオフラインで行われ、一定期間毎にパラメータを更新する。
【００４８】
置き換え優先度作成部２７は、クラスタリング部２３およびアクセス傾向予測部２５で算出した、コンテンツCiのアクセス数Aiと人気度変化傾向Biより、置き換えスコアS(Ci)を計算する（ステップ２０９，２１０）。置き換えスコアは低い程、優先的に置き換えられるものとする。人気が急上昇するコンテンツは優先的にキャッシュし、急降下するコンテンツは優先的に置き換える必要がある。以上を踏まえた置き換えスコア関数の実施例を以下に示す。
【００４９】
S(Ci)=α×Ai+β×Bi
各パラメータは、予めAiは[0:1]とBiは[0:1]の値を取るように正規化する。Biは"0"の場合は、人気度が1に近いほど急増、0に近いほど急減、0.5で変化なし、となる。A及びBは、それぞれの指標をスコアに反映させる際の強度を示すパラメータである。キャッシュするコンテンツの人気度の変化が緩やかな場合はαを大きくし、短期的に変化する場合はβを大きくする。計算が終了したら、結果をクラスタ中の各キャッシュ装置に送信する（ステップ２１１）。
【００５０】
次に、キャッシュ装置３０について説明する。
【００５１】
図５は、本発明の一実施の形態におけるキャッシュ装置の構成を示す。
【００５２】
キャッシュ装置３０は、キャッシュ管理部３１、キャッシュ記憶部３２、アクセス履歴記憶部３３からなる。
【００５３】
キャッシュ管理部３１は、ユーザからのリクエストを受け付け、キャッシュ記憶部３２にリクエストされたデータがある、または、キャッシュ記憶部３２に空き領域がある場合には、キャッシュ記憶部３２にデータ取得を指示する。アクセス傾向予測データに基づいて、キャッシュ内容を置き換えるかを判断し、その結果に基づいてキャッシュ記憶部３２のキャッシュ内容を置き換える。
【００５４】
キャッシュ記憶部３２は、コンテンツを記憶しておく領域である。キャッシュ管理部３１より、配信サーバ１０よりデータを取得する指示がある場合は、配信サーバ１０から該当コンテンツを取得し、装置に記憶した後、ユーザ端末５０へ転送する。また、ユーザへのデータ転送指示がある場合、該当コンテンツをユーザ端末５０へ配信する。コンテンツ置き換え指示がある場合、配信サーバ１０から該当コンテンツを取得し、キャッシュ内容の置き換えを行う。置き換え後は、該当コンテンツをユーザ端末５０へ転送する。
【００５５】
アクセス履歴記憶部３３は、キャッシュ管理部３１より送られてくるログを記憶し、一定時間毎にキャッシュ制御装置２０にログを送信する。
【００５６】
上記の構成のキャッシュ装置の動作を以下に示す。
【００５７】
図６は、本発明の一実施の形態におけるキャッシュ装置の動作のフローチャートである。
【００５８】
キャッシュ管理部３１は、キャッシュ装置３０全体を管理する部分である。ユーザからのリクエストを受信したら（ステップ３０１）、キャッシュ記憶部３２内にリクエストされたデータが記憶されているかどうかを判断する（ステップ３０２）。記憶されている場合は（ステップ３０２、Yes）、キャッシュ記憶部３２へリクエストされたコンテンツをユーザへ転送するよう指示する（ステップ３０３）。記憶されていない場合は（ステップ３０２、No）、キャッシュ制御装置２０が解析したアクセス傾向予測データを利用し、キャッシュ内容を置き換えるか判断する（ステップ３０４）。キャッシュ記憶部３２にリクエストされたデータを記憶するだけの領域が空いている場合は（ステップ３０４、Yes）、キャッシュ記憶部３２にデータを配信サーバ１０から取得するように指示する（ステップ３０５）。キャッシュ記憶部３２に空き領域がない場合は（ステップ３０４、No）、キャッシュ内で最も置き換えスコアが低いデータ（スコアをS1とする）を抽出し（ステップ３０６）、リクエストされたコンテンツのスコア（S2とする）と比較する（ステップ３０７）。S1＜S2の場合、キャッシュの内容を置き換え、S1≧S2場合は置き換えない。キャッシュ内容を置き換える場合は（ステップ３０７、Yes）、キャッシュ記憶部３２に置き換え処理を行うように指示を行う（ステップ３０８）。置き換えない場合は（ステップ３０７、No）、ユーザより受信したリクエストを配信サーバ１０へ転送する（ステップ３１１）。
【００５９】
なお、図３に示すキャッシュ制御装置及び図5に示すキャッシュ装置の各構成要素の動作（図４、図６）をプログラムとして構築し、キャッシュ制御装置及びキャッシュ装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６１】
１０ 配信サーバ
２０ キャッシュ制御装置
２１履歴データ記憶ＤＢ（データベース）
２２ アクセス数週軽侮
２３ クラスタリング部
２４ 時系列データ抽出部
２５ アクセス傾向予測部
２６ 学習部
２７ 置き換え優先度作成部
３０ キャッシュ装置
３１ キャッシュ管理部
３２ キャッシュ記憶部
３３ アクセス履歴記憶部
４０ ルータ
５０ ユーザ端末
【技術分野】
【０００１】
本発明は、キャッシュシステム及びキャッシュ配置方法及びキャッシュ制御装置及びキャッシュ制御プログラムに係り、特に、流通コンテンツの大容量・大規模化に伴うトラヒック削減を目的としたキャッシュを配置するためのキャッシュシステム及びキャッシュ配置方法及びキャッシュ制御装置及びキャッシュ制御プログラムに関する。
【背景技術】
【０００２】
流通コンテンツの大容量・大規模化に伴い、インターネットトラヒックは増加の一途を辿っている。そのため、トラヒック削減を目的として、キャッシュ技術が盛んに研究・開発されている。キャッシュ技術では、図７に示すように、キャッシュ装置３においてコンテンツを複製し、ユーザ４から要求があった場合、配信サーバ１に変わってデータを配信する。コンテンツ配信事業者にとってはサーバ負荷の低減、通信事業者にとってはトラヒック削減による設備コストの削減、ユーザにとってはレスポンス時間短縮によるQoE（Quality of Experience）の向上が利点である。
【０００３】
キャッシュ技術の性能向上に向け、コンテンツのアクセス履歴より、アクセスパターン解析やアクセス傾向予測をキャッシュ戦略に反映する技術が提案されている。この分野の従来技術は大きく２つに分類でき、コンテンツのアクセスパターンを利用したデータの事前配信技術と、コンテンツのアクセス傾向を利用したキャッシュの置き換え技術である。
アクセスパターンを利用した事前配信技術では、アクセス履歴を解析することにより、コンテンツのアクセスパターンを導き出す（例えば、特許文献１，２，３参照）。アクセスパターンとは、あるコンテンツがアクセスされた時に、その後に関連性の高い他のコンテンツがアクセスされやすいといったパターンである。アクセスパターンを利用することで、将来的にアクセスが予測されるコンテンツを、キャッシュ装置に事前配信しておくことで、ユーザへのレスポンス時間が向上する。
【０００４】
しかし、この技術は、人気コンテンツが定常状態にある場合は有効だが、短期的に人気コンテンツが変化する環境では、アクセスパターンを解析している間に人気コンテンツが変化してしまい、アクセスパターンの予測精度が低下する。特に、近年ネットワークにおいて支配的になっているビデオトラヒックにおいては、コンテンツのライフサイクルが短く、人気が短期的に急上昇・急下降する。さらに、予測精度が悪い場合は、アクセスされないコンテンツを事前配布することになり、無駄な容量と帯域を消費することになる。
【０００５】
コンテンツのアクセス傾向を利用したキャッシュの置き換え技術では、コンテンツアクセス数の時系列データから、将来的にコンテンツの人気度が上昇するか下降するかを予測し、キャッシュの置き換えに反映する。 この置き換え技術は、人気が増加するコンテンツに対しては優先的にキャッシュし、低下するコンテンツに対しては優先的に置き換えの対象とする。この技術では、コンテンツの人気度変動を早期に検出でき、短期的に人気コンテンツが変化する環境において特に有効である（例えば、特許文献４、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８-３９２９号公報
【特許文献２】特開２００７-１４８５５４号公報
【特許文献３】特開２００６-１３９３９８号公報
【特許文献４】特開２００３-２４２０２０号公報
【非特許文献】
【０００７】
【非特許文献１】土井等、"P2Pネットワークにおけるクエリトレンド変化を利用したキャッシング法"IEEE technical report 108 (123), 91-96, 2008-07-03.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
コンテンツのアクセス傾向を利用したキャッシュの置き換えの従来技術では、アクセス傾向を予測する際に、一定期間毎（タイムスロット毎）にコンテンツ毎のアクセス数をカウントし、現在のタイムスロットと一つ前のタイムスロットにおけるアクセス数の差分より人気の増減を判断している。そのため、直近アクセス数の変化量のみで人気を推定しており、短期的な人気度変動に過剰に反応し、全体の人気度傾向を把握できず、予測の精度が低下するといった課題がある。
【０００９】
また、従来技術はキャッシュ装置毎に予測を行っており、小規模なネットワーク事業者に設置されたキャッシュ装置だと、一定期間に十分な量のアクセス履歴が取得できないため、少ない統計データで予測を行うことになり、予測精度が低下する。これに対して、上位のサーバが複数のキャッシュ装置のアクセス履歴を収集することにより、十分な量の統計データを利用し、アクセス傾向を予測する手法が考えられる。しかし、この手法ではキャッシュ装置毎の人気コンテンツ傾向の違いが反映されない。キャッシュ装置毎の人気コンテンツ傾向の違いとは、あるキャッシュ装置では、人気があるコンテンツでも、他のキャッシュ装置では人気がないといった傾向の違いを指す。
【００１０】
本発明は、上記の点に鑑みなされたもので、上記の課題を解決し、コンテンツのアクセス傾向を利用したキャッシュの置き換え技術の高精度化が可能なキャッシュシステム及びキャッシュ配置方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の問題を解決するために、本発明（請求項１）は、配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムであって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有するキャッシュ制御装置を有し、
前記キャッシュ装置は、
アクセス履歴を格納するアクセス履歴記憶手段と、
前記ユーザ端末からのリクエストを受け付け、アクセス履歴を前記アクセス履歴記憶手段に格納し、所定の周期で該アクセス履歴を前記キャッシュ制御装置に送信する手段と、
コンテンツを格納するキャッシュ記憶手段と、
前記キャッシュ制御装置から取得した前記予測データに基づいて前記キャッシュ記憶手段の内容を書き換えるキャッシュ管理手段と、
を有する。
【００１２】
また、本発明（請求項２）は、請求項１の前記キャッシュ管理装置の前記予測データ生成手段において、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する。
【００１３】
また、本発明（請求項３）は、請求項１または2の前記キャッシュ管理装置の前記予測データ生成手段において、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む。
【００１４】
本発明（請求項４）は、配信サーバ、複数のキャッシュ装置、ユーザ端末、キャッシュ制御装置からなるキャッシュシステムにおけるキャッシュ配置方法であって、
前記キャッシュ装置は、前記ユーザ端末からのリクエストを受け付け、アクセス履歴をアクセス履歴記憶手段に格納し、所定の周期で前記キャッシュ制御装置に送信し、
前記キャッシュ制御装置は、
前記キャッシュ装置からコンテンツのアクセス履歴を受信し、履歴データ記憶手段に格納するアクセス履歴受信ステップと、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計ステップと、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリングステップと、
前記クラスタリングステップでクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出ステップと、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測ステップと、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成ステップと、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信ステップと、
を行い、
前記キャッシュ装置は、
前記キャッシュ制御装置から取得した前記予測データに基づいて、コンテンツを格納するキャッシュ記憶手段の内容を書き換える。
【００１５】
また、本発明（請求項５）は、請求項４の前記予測データ生成ステップにおいて、
前記アクセス傾向予測アルゴリズムのパラメータ調整をする。
【００１６】
また、本発明（請求項６）は、請求項４または５の前記予測データ生成ステップにおいて、
前記クラスタリングステップにおいて前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測ステップで算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する。
【００１７】
本発明（請求項７）は、配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムにおけるキャッシュ制御装置であって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、を有する。
【００１８】
また、本発明（請求項８）は、請求項７の前記予測データ生成手段において、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する。
【００１９】
また、本発明（請求項９）は、請求項７または８の前記予測データ生成手段において、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む。
【００２０】
本発明（請求項１０）は、請求項７乃至９のいずれか1項に記載のキャッシュ制御装置を構成する各手段としてコンピュータを機能させるためのキャッシュ制御プログラムである。
【発明の効果】
【００２１】
上記のように、本発明によれば、複数のキャッシュ装置を制御するキャッシュ制御装置において、キャッシュ装置毎にコンテンツのアクセス傾向を統計手法を用いて高精度に予測することにより、各キャッシュ装置におけるキャッシュヒット率が上昇する。それに伴い、ネットワークトラヒックの削減、配信サーバの負荷の削減、ユーザに対するレスポンス時間の短縮等の効果がある。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態におけるシステム全体の動作のフローチャートである。
【図３】本発明の一実施の形態におけるキャッシュ制御装置の構成図である。
【図４】本発明の一実施の形態におけるキャッシュ制御装置のフローチャートである。
【図５】本発明の一実施の形態におけるキャッシュ装置の構成図である。
【図６】本発明の一実施の形態におけるキャッシュ装置のフローチャートである。
【図７】従来のキャッシュ動作の概要を示す図である。
【発明を実施するための形態】
【００２３】
以下図面と共に、本発明の実施の形態を説明する。
【００２４】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００２５】
同図に示すシステムは、配信サーバ１０、キャッシュ制御装置２０、キャッシュ装置３０、ルータ４０、ユーザ端末５０から構成される。
【００２６】
キャッシュ制御装置２０は、十分に計算性能が確保されたマシンやIaaS (Infrastructure as a Service)等のクラウド基盤上に実装されることを前提とする。
【００２７】
各キャッシュ装置３０は、アクセス履歴をキャッシュ制御装置２０に定期的に送信する。アクセス履歴とは、リクエストされた時間、リクエストされたコンテンツの識別子、コンテンツサイズ等の情報を記憶したデータである。
【００２８】
図２は、本発明の一実施の形態におけるシステム全体の動作のフローチャートである。
【００２９】
ステップ１０１） キャッシュ装置３０は、保持していたアクセス履歴を定期的にキャッシュ制御装置１０に送信し（ステップ１０１）、キャッシュ制御装置２０では、キャッシュ装置３０からアクセス履歴を収集する（ステップ１０２）。キャッシュ制御装置２０は、収集した履歴データを利用し、コンテンツ毎のアクセス傾向を予測し（ステップ１０３）、その結果を各キャッシュ装置３０へ返信する（ステップ１０４）。キャッシュ装置３０は、キャッシュ制御装置２０から取得した、予測情報を元に、キャッシュ置き換え処理を行う（ステップ１０５）。
【００３０】
以下に、それぞれ装置の動作概要を説明する。
【００３１】
最初にキャッシュ制御装置１０について説明する。
【００３２】
図３は、本発明の一実施の形態におけるキャッシュ制御装置の構成図である。
【００３３】
キャッシュ制御装置２０は、履歴データ記憶DB（Data Base）２１，アクセス数集計部２２，クラスタリング部２３，時系列データ抽出部２４，アクセス傾向予測部２５，学習部２６，置き換え優先度作成部２７からなる。
【００３４】
履歴データ記憶部ＤＢ２１は、各キャッシュ装置３０から受信したアクセス履歴を格納する。アクセス履歴には、それぞれ各キャッシュ装置３０の識別子が付与されており、キャッシュ装置３０毎に格納するものとする。
【００３５】
アクセス数集計部２２は、履歴データ記憶ＤＢ２１からアクセス履歴を読み込み、各キャッシュ装置について、コンテンツ毎にアクセス数を集計し、クラスタリング部２３に出力する。
【００３６】
クラスタリング部２３は、集計されたアクセス数を取得してコンテンツのリクエスト傾向が似ているキャッシュ装置をクラスタリングする。リクエスト傾向を調べる方法は既存の方法を用いるものとする。
【００３７】
時系列データ抽出部２４は、クラスタリング部２３でクラスタリングされたグループに含まれるキャッシュ装置のアクセス履歴を履歴データ記憶ＤＢ２１から抽出し、これを時系列にソートして時系列データを生成する。
【００３８】
アクセス傾向予測部２５は、次の予測を開始するまでの人気コンテンツの人気度変化の傾向を、アクセス傾向予測アルゴリズムを用いて予測し、人気コンテンツの変化傾向データを出力する。
【００３９】
学習部２６は、アクセス傾向予測部２５が用いるアクセス傾向予測アルゴリズムのパラメータ調整を行う。
【００４０】
置き換え優先度作成部２７は、クラスタリング部２３から入力されるクラスタごとの各コンテンツのアクセス数及び、アクセス傾向予測部２５から入力される人気コンテンツの変化傾向データを用いて、置き換えスコアを計算する。置き換えスコアはスコアが小さいほど優先的にキャッシュ内容を置き換えるためのスコアである。生成された置き換えスコアを予測データとしてキャッシュ装置３０に送信する。
【００４１】
図４は、本発明の一実施の形態におけるキャッシュ制御装置の動作のフローチャートである。
【００４２】
各キャッシュ装置からアクセス履歴を受信すると（ステップ２０１）、収履歴データ記憶ＤＢ２１は、収集された情報を格納する（ステップ２０２）。
【００４３】
アクセス数集計部２２は、履歴データ記憶ＤＢ２１からアクセス情報を読み出し、キャッシュ装置毎に各コンテンツのアクセス数を集計する(ステップ２０３)。
【００４４】
次に、クラスタリング部２３では、キャッシュ装置３０毎に集計した各コンテンツのアクセス数を基に、コンテンツのリクエスト傾向の近いサーバ同士をクラスタリングする（ステップ２０４）。クラスタリングには、ウォード法、最短距離法、最長距離法、Ｋ平均法等の手法を用いる。これらの方法を利用しクラスタリングを行う際には、キャッシュ装置３０A，３０B間のコンテンツリクエスト傾向の非類似度を表す距離関数Dist(A, B)を定義する必要がある。実施例としては、人気度上位コンテンツの重複割合の逆数等があげられる。分類した各クラスタに対して、コンテンツCi毎のアクセス数Aiを集計する（ステップ２０５）。
【００４５】
時系列データ抽出部２４は、クラスタリング部２３によって分類したクラスタ単位で処理を行う。こうすることにより、類似した傾向を持つキャッシュ装置３０同士のログデータを共有することにより、精度が高い推定が可能であり、かつキャッシュ装置毎の傾向の違いにも対応が可能である。動作としては、まず、クラスタに属しているキャッシュ装置３０の過去のアクセス履歴を履歴データ記憶ＤＢ２１から抽出し、次にコンテンツ毎のアクセス数の時系列データをアクセス履歴から抽出する（ステップ２０６）。アクセス数の時系列データとは、あるタイムスロット毎に集計したアクセス数を時系列に並べたデータのことである。
【００４６】
アクセス傾向予測部２５は、時系列データ抽出部２４で抽出したアクセス数の時系列データより、次に予測を行うまでの期間のアクセスの人気度変化傾向Biを推定する（ステップ２０７）。アクセス傾向予測アルゴリズムには、ニューラルネットワーク、サポートベクターマシン、ベイズ推定等の機械学習技術を利用する。これらの手法は、株価予測等のデータの時系列変動予測によく利用されている。予測アルゴリズムに対しての、入出力データの一例として、下記のようなものが挙げられる。入力データとしては、コンテンツのアクセス数の時系列データを用いる。出力データとしては、人気度の変化傾向を示した値（上昇だったら"1"，下降だったら"０"）やアクセス数の変動率等が挙げられる。こうすることにより、従来の一つ前のタイムスロットの情報のみを利用した場合と比較して、高精度な予測が可能となる。
【００４７】
学習部２６は、履歴データ記憶DB２１から最新のアクセス履歴を読み出し（ステップ２０７）、学習データとして用いることにより、予測誤差が最小になるように、アクセス傾向予測アルゴリズムのパラメータの調整を行う（ステップ２０８）。この処理はオフラインで行われ、一定期間毎にパラメータを更新する。
【００４８】
置き換え優先度作成部２７は、クラスタリング部２３およびアクセス傾向予測部２５で算出した、コンテンツCiのアクセス数Aiと人気度変化傾向Biより、置き換えスコアS(Ci)を計算する（ステップ２０９，２１０）。置き換えスコアは低い程、優先的に置き換えられるものとする。人気が急上昇するコンテンツは優先的にキャッシュし、急降下するコンテンツは優先的に置き換える必要がある。以上を踏まえた置き換えスコア関数の実施例を以下に示す。
【００４９】
S(Ci)=α×Ai+β×Bi
各パラメータは、予めAiは[0:1]とBiは[0:1]の値を取るように正規化する。Biは"0"の場合は、人気度が1に近いほど急増、0に近いほど急減、0.5で変化なし、となる。A及びBは、それぞれの指標をスコアに反映させる際の強度を示すパラメータである。キャッシュするコンテンツの人気度の変化が緩やかな場合はαを大きくし、短期的に変化する場合はβを大きくする。計算が終了したら、結果をクラスタ中の各キャッシュ装置に送信する（ステップ２１１）。
【００５０】
次に、キャッシュ装置３０について説明する。
【００５１】
図５は、本発明の一実施の形態におけるキャッシュ装置の構成を示す。
【００５２】
キャッシュ装置３０は、キャッシュ管理部３１、キャッシュ記憶部３２、アクセス履歴記憶部３３からなる。
【００５３】
キャッシュ管理部３１は、ユーザからのリクエストを受け付け、キャッシュ記憶部３２にリクエストされたデータがある、または、キャッシュ記憶部３２に空き領域がある場合には、キャッシュ記憶部３２にデータ取得を指示する。アクセス傾向予測データに基づいて、キャッシュ内容を置き換えるかを判断し、その結果に基づいてキャッシュ記憶部３２のキャッシュ内容を置き換える。
【００５４】
キャッシュ記憶部３２は、コンテンツを記憶しておく領域である。キャッシュ管理部３１より、配信サーバ１０よりデータを取得する指示がある場合は、配信サーバ１０から該当コンテンツを取得し、装置に記憶した後、ユーザ端末５０へ転送する。また、ユーザへのデータ転送指示がある場合、該当コンテンツをユーザ端末５０へ配信する。コンテンツ置き換え指示がある場合、配信サーバ１０から該当コンテンツを取得し、キャッシュ内容の置き換えを行う。置き換え後は、該当コンテンツをユーザ端末５０へ転送する。
【００５５】
アクセス履歴記憶部３３は、キャッシュ管理部３１より送られてくるログを記憶し、一定時間毎にキャッシュ制御装置２０にログを送信する。
【００５６】
上記の構成のキャッシュ装置の動作を以下に示す。
【００５７】
図６は、本発明の一実施の形態におけるキャッシュ装置の動作のフローチャートである。
【００５８】
キャッシュ管理部３１は、キャッシュ装置３０全体を管理する部分である。ユーザからのリクエストを受信したら（ステップ３０１）、キャッシュ記憶部３２内にリクエストされたデータが記憶されているかどうかを判断する（ステップ３０２）。記憶されている場合は（ステップ３０２、Yes）、キャッシュ記憶部３２へリクエストされたコンテンツをユーザへ転送するよう指示する（ステップ３０３）。記憶されていない場合は（ステップ３０２、No）、キャッシュ制御装置２０が解析したアクセス傾向予測データを利用し、キャッシュ内容を置き換えるか判断する（ステップ３０４）。キャッシュ記憶部３２にリクエストされたデータを記憶するだけの領域が空いている場合は（ステップ３０４、Yes）、キャッシュ記憶部３２にデータを配信サーバ１０から取得するように指示する（ステップ３０５）。キャッシュ記憶部３２に空き領域がない場合は（ステップ３０４、No）、キャッシュ内で最も置き換えスコアが低いデータ（スコアをS1とする）を抽出し（ステップ３０６）、リクエストされたコンテンツのスコア（S2とする）と比較する（ステップ３０７）。S1＜S2の場合、キャッシュの内容を置き換え、S1≧S2場合は置き換えない。キャッシュ内容を置き換える場合は（ステップ３０７、Yes）、キャッシュ記憶部３２に置き換え処理を行うように指示を行う（ステップ３０８）。置き換えない場合は（ステップ３０７、No）、ユーザより受信したリクエストを配信サーバ１０へ転送する（ステップ３１１）。
【００５９】
なお、図３に示すキャッシュ制御装置及び図5に示すキャッシュ装置の各構成要素の動作（図４、図６）をプログラムとして構築し、キャッシュ制御装置及びキャッシュ装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６１】
１０ 配信サーバ
２０ キャッシュ制御装置
２１履歴データ記憶ＤＢ（データベース）
２２ アクセス数週軽侮
２３ クラスタリング部
２４ 時系列データ抽出部
２５ アクセス傾向予測部
２６ 学習部
２７ 置き換え優先度作成部
３０ キャッシュ装置
３１ キャッシュ管理部
３２ キャッシュ記憶部
３３ アクセス履歴記憶部
４０ ルータ
５０ ユーザ端末
【特許請求の範囲】
【請求項１】
配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムであって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有するキャッシュ制御装置を有し、
前記キャッシュ装置は、
アクセス履歴を格納するアクセス履歴記憶手段と、
前記ユーザ端末からのリクエストを受け付け、アクセス履歴を前記アクセス履歴記憶手段に格納し、所定の周期で該アクセス履歴を前記キャッシュ制御装置に送信する手段と、
コンテンツを格納するキャッシュ記憶手段と、
前記キャッシュ制御装置から取得した前記予測データに基づいて前記キャッシュ記憶手段の内容を書き換えるキャッシュ管理手段と、
を有する
ことを特徴とするキャッシュシステム。
【請求項２】
前記キャッシュ管理装置の前記予測データ生成手段は、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する
請求項１記載のキャッシュシステム。
【請求項３】
前記キャッシュ管理装置の前記予測データ生成手段は、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む
請求項１または２に記載のキャッシュシステム。
【請求項４】
配信サーバ、複数のキャッシュ装置、ユーザ端末、キャッシュ制御装置からなるキャッシュシステムにおけるキャッシュ配置方法であって、
前記キャッシュ装置は、前記ユーザ端末からのリクエストを受け付け、アクセス履歴をアクセス履歴記憶手段に格納し、所定の周期で前記キャッシュ制御装置に送信し、
前記キャッシュ制御装置は、
前記キャッシュ装置からコンテンツのアクセス履歴を受信し、履歴データ記憶手段に格納するアクセス履歴受信ステップと、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計ステップと、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリングステップと、
前記クラスタリングステップでクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出ステップと、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測ステップと、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成ステップと、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信ステップと、
を行い、
前記キャッシュ装置は、
前記キャッシュ制御装置から取得した前記予測データに基づいて、コンテンツを格納するキャッシュ記憶手段の内容を書き換える
ことを特徴とするキャッシュ配置方法。
【請求項５】
前記予測データ生成ステップにおいて、
前記アクセス傾向予測アルゴリズムのパラメータ調整をする
請求項４記載のキャッシュ配置方法。
【請求項６】
前記予測データ生成ステップにおいて、
前記クラスタリングステップにおいて前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測ステップで算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する
請求項４または５に記載のキャッシュ配置方法。
【請求項７】
配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムにおけるキャッシュ制御装置であって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気変化傾向を、任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有することを特徴とするキャッシュ制御装置。
【請求項８】
前記予測データ生成手段は、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する
請求項７記載のキャッシュ制御装置。
【請求項９】
前記予測データ生成手段は、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む
請求項７または８に記載のキャッシュ制御装置。
【請求項１０】
請求項７乃至９のいずれか1項に記載のキャッシュ制御装置を構成する各手段としてコンピュータを機能させるためのキャッシュ制御プログラム。
【請求項１】
配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムであって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有するキャッシュ制御装置を有し、
前記キャッシュ装置は、
アクセス履歴を格納するアクセス履歴記憶手段と、
前記ユーザ端末からのリクエストを受け付け、アクセス履歴を前記アクセス履歴記憶手段に格納し、所定の周期で該アクセス履歴を前記キャッシュ制御装置に送信する手段と、
コンテンツを格納するキャッシュ記憶手段と、
前記キャッシュ制御装置から取得した前記予測データに基づいて前記キャッシュ記憶手段の内容を書き換えるキャッシュ管理手段と、
を有する
ことを特徴とするキャッシュシステム。
【請求項２】
前記キャッシュ管理装置の前記予測データ生成手段は、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する
請求項１記載のキャッシュシステム。
【請求項３】
前記キャッシュ管理装置の前記予測データ生成手段は、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む
請求項１または２に記載のキャッシュシステム。
【請求項４】
配信サーバ、複数のキャッシュ装置、ユーザ端末、キャッシュ制御装置からなるキャッシュシステムにおけるキャッシュ配置方法であって、
前記キャッシュ装置は、前記ユーザ端末からのリクエストを受け付け、アクセス履歴をアクセス履歴記憶手段に格納し、所定の周期で前記キャッシュ制御装置に送信し、
前記キャッシュ制御装置は、
前記キャッシュ装置からコンテンツのアクセス履歴を受信し、履歴データ記憶手段に格納するアクセス履歴受信ステップと、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計ステップと、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリングステップと、
前記クラスタリングステップでクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出ステップと、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気度変化傾向を任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測ステップと、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成ステップと、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信ステップと、
を行い、
前記キャッシュ装置は、
前記キャッシュ制御装置から取得した前記予測データに基づいて、コンテンツを格納するキャッシュ記憶手段の内容を書き換える
ことを特徴とするキャッシュ配置方法。
【請求項５】
前記予測データ生成ステップにおいて、
前記アクセス傾向予測アルゴリズムのパラメータ調整をする
請求項４記載のキャッシュ配置方法。
【請求項６】
前記予測データ生成ステップにおいて、
前記クラスタリングステップにおいて前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測ステップで算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する
請求項４または５に記載のキャッシュ配置方法。
【請求項７】
配信サーバ、複数のキャッシュ装置及びユーザ端末からなるキャッシュシステムにおけるキャッシュ制御装置であって、
前記キャッシュ装置から受信したコンテンツのアクセス履歴を格納する履歴データ記憶手段と、
前記履歴データ記憶手段から前記アクセス履歴を読み出して、キャッシュ装置毎の各コンテンツのアクセス数を集計するアクセス数集計手段と、
集計されたアクセス数に基づいて、各コンテンツのリクエストの傾向の近いキャッシュ装置同士をクラスタリングするクラスタリング手段と、
前記クラスタリング手段でクラスタリングされたクラスタ毎に、該クラスタに属するキャッシュ装置のアクセス履歴を前記履歴データ記憶手段から抽出して、時系列に並べた時系列データを生成する時系列データ抽出手段と、
前記時系列データについて、次の予測を行うまでの人気コンテンツの人気変化傾向を、任意のアクセス傾向予測アルゴリズムを用いて推定するアクセス傾向予測手段と、
推定された前記人気コンテンツの変化傾向と、クラスタ毎のコンテンツのアクセス数に応じて予測データを生成する予測データ生成手段と、
前記予測データをクラスタ毎に該クラスタに含まれる前記キャッシュ装置に送信する予測データ送信手段と、
を有することを特徴とするキャッシュ制御装置。
【請求項８】
前記予測データ生成手段は、
前記アクセス傾向予測アルゴリズムのパラメータ調整を行う学習手段を更に有する
請求項７記載のキャッシュ制御装置。
【請求項９】
前記予測データ生成手段は、
前記クラスタリング手段において前記集計されたアクセス数が最も多いコンテンツ及びそのアクセス数と、前記アクセス傾向予測手段で算出した前記人気度変化傾向を用いて、値が低いほど優先的に置き換えられる置き換えスコアを算出し、該置き換えスコアに基づいて前記予測データを生成する手段を含む
請求項７または８に記載のキャッシュ制御装置。
【請求項１０】
請求項７乃至９のいずれか1項に記載のキャッシュ制御装置を構成する各手段としてコンピュータを機能させるためのキャッシュ制御プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−１４１８８５（Ｐ２０１２−１４１８８５Ａ）
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願番号】特願２０１１−６２３（Ｐ２０１１−６２３）
【出願日】平成２３年１月５日（２０１１．１．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願日】平成２３年１月５日（２０１１．１．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]