(57)【要約】【課題】効率的な記憶領域の利用、ヒット率の向上を実現するキャッシュ装置、キャッシュデータ管理方法を提供する。【解決手段】ネットワーク接続されたキャッシュ装置におけるキャッシュ・リプレースメント処理において、削除保留ブロックに関するリストを保持して、キャッシュグループ内のキャッシュ装置ごとに各々削除保留されるデータ・ブロックが異なるように設定して、削除保留リストを適用したデータ管理を行なう。本構成によれば、キャッシュ装置単独のキャッシュ・リプレースメント管理に比べて効率的な記憶領域の利用が図れ、また、端末からのデータ要求に応じて複数のキャッシュ装置に記憶したデータ・ブロックを集めて送信することが可能となり、ネットワークトラフィックの軽減、キャッシュ装置のヒット率の向上が実現される。【選択図】　図４
2004038627.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置であり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルと、
前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する制御手段と、
を有することを特徴とするキャッシュ装置。
【請求項２】
前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、
前記制御手段は、共同管理するコンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持対象とする保留データ・ブロックの決定処理を、以下の処理、すなわち、
判定対象データ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍであるか否かを判定し、
Ｖ＝ｍである場合に、該データ・ブロックを保留データ・ブロックとして決定する処理、
を実行する構成であることを特徴とする請求項１に記載のキャッシュ装置。
【請求項３】
前記制御手段は、
記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループによる共同管理が可能か否かをキャッシュ装置間のメッセージ送受信により判定し、
共同管理可能であると判定した場合に、前記キャッシュグループ・テーブルを生成する構成であることを特徴とする請求項１に記載のキャッシュ装置。
【請求項４】
前記制御手段は、
記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、
前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロック中から、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロック以外のデータ・ブロックについては、削除の許容されるデータ・ブロック管理リストとしてのフリーブロックリストにより管理する構成であることを特徴とする請求項１に記載のキャッシュ装置。
【請求項５】
前記削除保留リストは、データ・ブロックの保存優先度に応じた複数のリストによって構成され、
前記制御手段は、
データ・ブロックの保存優先度を判定し、該判定結果に基づいて選択した削除保留リストに対して前記管理データ・ブロックに対応するエントリの設定を行なう構成であることを特徴とする請求項１に記載のキャッシュ装置。
【請求項６】
前記制御手段は、
端末からのデータ・ブロック取得要求が、前記キャッシュグループによる共同管理対象のコンテンツに含まれるデータ・ブロック取得要求である場合に、
取得要求対象のデータ・ブロックが前記キャッシュグループを構成するいずれのキャッシュ装置の保持対象データ・ブロックであるかを判定し、該判定結果に基づいてデータ・ブロックを自キャッシュ装置または、前記キャッシュグループを構成する他のキャッシュ装置から取得する処理を実行する構成であることを特徴とする請求項１に記載のキャッシュ装置。
【請求項７】
前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、
前記制御手段は、
取得要求対象のデータ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍを算出し、
算出したｍをグループ・メンバー番号として有するキャッシュ装置からデータ・ブロックの取得処理を実行する構成であることを特徴とする請求項６に記載のキャッシュ装置。
【請求項８】
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置におけるキャッシュデータ管理方法であり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定する保留データ・ブロック決定ステップと、
決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する管理ステップと、
を有することを特徴とするキャッシュデータ管理方法。
【請求項９】
前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、
前記保留データ・ブロック決定ステップは、
共同管理するコンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持対象とする保留データ・ブロックの決定処理を、以下の処理、すなわち、
判定対象データ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍであるか否かを判定し、
Ｖ＝ｍである場合に、該データ・ブロックを保留データ・ブロックとして決定する処理を実行することを特徴とする請求項８に記載のキャッシュデータ管理方法。
【請求項１０】
前記キャッシュデータ管理方法は、さらに、
記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループによる共同管理が可能か否かをキャッシュ装置間のメッセージ送受信により判定し、共同管理可能であると判定した場合に、前記キャッシュグループ・テーブルを生成する処理を実行することを特徴とする請求項８に記載のキャッシュデータ管理方法。
【請求項１１】
前記キャッシュデータ管理方法は、さらに、
記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロック中から、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロック以外のデータ・ブロックについては、削除の許容されるデータ・ブロック管理リストとしてのフリーブロックリストにより管理するステップを含むことを特徴とする請求項８に記載のキャッシュデータ管理方法。
【請求項１２】
前記削除保留リストは、データ・ブロックの保存優先度に応じた複数のリストによって構成され、
前記キャッシュデータ管理方法は、さらに、
データ・ブロックの保存優先度を判定し、該判定結果に基づいて選択した削除保留リストに対して前記管理データ・ブロックに対応するエントリの設定を行なうステップを含むことを特徴とする請求項８に記載のキャッシュデータ管理方法。
【請求項１３】
前記キャッシュデータ管理方法は、さらに、
端末からのデータ・ブロック取得要求が、前記キャッシュグループによる共同管理対象のコンテンツに含まれるデータ・ブロック取得要求である場合に、取得要求対象のデータ・ブロックが前記キャッシュグループを構成するいずれのキャッシュ装置の保持対象データ・ブロックであるかを判定し、該判定結果に基づいてデータ・ブロックを自キャッシュ装置または、前記キャッシュグループを構成する他のキャッシュ装置から取得するデータ・ブロック取得処理を実行するステップを含むことを特徴とする請求項８に記載のキャッシュデータ管理方法。
【請求項１４】
前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、
前記データ・ブロック取得処理は、
取得要求対象のデータ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍを算出し、
算出したｍをグループ・メンバー番号として有するキャッシュ装置からデータ・ブロックを取得する処理として実行することを特徴とする請求項１３に記載のキャッシュデータ管理方法。
【請求項１５】
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置におけるキャッシュデータ管理処理を実行するコンピュータ・プグラムであり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定する保留データ・ブロック決定ステップと、
決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する管理ステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キャッシュ装置、およびキャッシュデータ管理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、ネットワークを通じて送受信されるデータ・キャッシュ処理において、キャッシュ装置内のデータ格納領域の効率的利用、およびヒット率向上を実現したキャッシュ装置、およびキャッシュデータ管理方法、並びにコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
近年、インターネット等の通信ネットワークを介した画像、音声データ、各種プログラム等のデータ転送が盛んに行われている。ネットワークを通じてやりとりされるコンテンツの種類は、テキスト・静止画などから、動画・音声などのマルチメディアコンテンツへと移行が進み、コンテンツの大容量化、多種類化が著しく進んでいる。
【０００３】
また、近年は、ブロードバンドによる大容量コンテンツの配信が急速に広まり、これに応じて、ネットワークを介して流通するコンテンツ数が飛躍的に増加している。このようにコンテンツの種類が増加し、大容量コンテンツが増大すると、データ通信量の増大、すなわちネットワークのデータトラフィックの増大という問題が発生する。
【０００４】
ネットワークのデータトラフィックの増大という問題を解決する１つの手法にキャッシュシステムがある。キャッシュシステムは、例えばコンテンツ配信サイトからコンテンツ受信ユーザー側に至るネットワーク経路上にデータ蓄積手段としてのキャッシュを構成したシステムであり、ユーザー側から要求されたデータ（コンテンツ）がキャッシュに蓄積されている場合は、コンテンツ配信サイトから改めてデータ（コンテンツ）を送信することなく、データをキャッシュから取り出してユーザーに提供可能としたものである。
【０００５】
例えば、ユーザーがネットワークを介してコンテンツを取得し、ネットワーク上の一時的な記憶装置（キャッシュ）にコンテンツが格納された場合、キャッシュは一定の決まったルールでコンテンツ格納、削除処理を行なう。例えばキャッシュの記憶容量の越えない範囲で最新のコンテンツが入力される毎に、アクセスの頻度が古いコンテンツを書き換える処理を実行する。通常、このキャッシュにおけるコンテンツ管理ルールはコンテンツの配信側やユーザー側の直接的な管理とは無関係に実行される。
【０００６】
このように、インターネット・キャッシュのデータ領域管理において、データが満杯になると使われなくなったデータ領域を検出し、その領域をキャッシュから削除後に新しいデータで置き換える処理を行なう。これをキャッシュ・リプレースメント（Ｃａｃｈｅ　Ｒｅｐｌａｃｅｍｅｎｔ）と呼ぶ。
【０００７】
従来のインターネット・キャッシュのキャッシュ・リプレースメント（Ｃａｃｈｅ　Ｒｅｐｌａｃｅｍｅｎｔ）は、インターネット等のネットワークに複数のキャッシュが存在する場合であっても、各々の個別のキャッシュ装置内で独自なデータ管理を実行するのが一般的である。最も一般的なキャッシュ・リプレースメントの技法としては、ＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）によるデータ管理方法がある。
【０００８】
ＬＲＵは、最近使用されていないデータ・ブロックを、ＬＲＵリストの後ろに回し、最近使われたデータ・ブロックを、ＬＲＵリストの先頭に設定するという管理方法であり、新しいデータをキャッシュするために古いデータを削除したい場合には、ＬＲＵリストの後ろにあるブロックから削除することで、キャッシュ内に新たなデータ格納領域を形成する方法である。
【０００９】
図１を参照してＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）によるデータ管理方法について説明する。管理データとしては、利用頻度順にデータ・ブロックに対応するエントリを並べた（ａ）ＬＲＵリストと、キャッシュの空き領域ブロックを示す（ｂ）フリーブロックリストを有する。新たにキャッシュされたデータは、（ｂ）フリーブロックリストのエントリに示されるポインタによって特定されるメモリ領域としてのデータ格納ブロックに格納され、格納ブロックに対して設定されるブロック情報を格納したエントリが、（ａ）ＬＲＵリストの先頭エントリ１０１として設定される。
【００１０】
データの新規入力（キャッシュ）により、キャッシュのデータ格納領域が満杯になり、以前よりキャッシュされていたデータの中から、いずれかを削除する必要のあるときに、削除されるデータは、（ａ）ＬＲＵリストの末端にある最近使われていないデータ・ブロックと考えられるエントリ１０２に対応するデータ・ブロックであり、削除されたデータ・ブロックをポインタ情報として示すエントリが（ｂ）フリーブロックリストに設定されることで、所定のデータ格納ブロックが空き領域として設定される。
【００１１】
このようなキャッシュ用データ・ブロック管理の方法は、あくまで単独のキャッシュ装置に関する情報を元に処理されていた。また、近隣の複数のキャッシュ装置に対して要求元のキャッシュ装置の持っていないデータを要求するための手段としてＩＣＰ（Ｉｎｔｅｒｎｅｔ　Ｃａｃｈｅ　Ｐｒｏｔｏｃｏｌ　：　ＲＦＣ−２１８６，　ＲＦＣ−２１８７）が提案されているが、コンテンツファイルのリソース情報としてのＵＲＬ（Ｕｎｉｆｏｒｍ　Ｒｅｓｏｕｒｃｅ　Ｌｏｃａｔｏｒ）を指定したＵＲＬ単位でのデータ要求処理であることや、複数のキャッシュ間でどのデータを消去または残すべきかの細かい調整機能が無い。このため、たまたま各キャッシュ装置の事情で要求したものと同じデータが他のキャッシュ装置に残っているときに、そのデータをサーバーからダウンロードしてくる代わりに他のキャッシュ装置から持ってくるという処理をしていただけである。
【００１２】
【発明が解決しようとする課題】
本発明は、上述したキャッシュ管理の現状に鑑みてなされたものであり、ネットワークに複数のキャッシュが接続された構成において、効率的なデータ格納領域の利用を実現したキャッシュ装置、およびキャッシュデータ管理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００１３】
例えば、ネットワーク接続されたキャッシュにおけるデータ領域管理方法において、データの削除を一時保留する「削除保留リスト」を使って管理することや、キャッシュグループという概念を導入することで、ビデオコンテンツのような大きなサイズのコンテンツをキャッシュするときに好適なデータ管理方法を実現する。
【００１４】
キャッシュグループとは、ネットワークに接続したキャッシュ装置のいくつかを組にしたものであり、このグループ内の複数のディスク間で同じコンテンツデータが管理されているものとする。このときに、あるデータ単位ごとにブロック化して各々のブロック単位で削除保留リストを使って管理するときに、ディスク別に削除保留すべき部分が異なるように処理することにより、キャッシュ・リプレースメントによって、ある程度のデータ削除処理が進んだ段階においても、キャッシュグループ内の近隣のキャッシュディスクからデータを集めることによって、元のコンテンツデータを迅速に再生することができる。短いコンテンツデータであれば、コンテンツ別に削除保留にすべきものをディスク別に異なるように設定することで、同様の管理が可能である。
【００１５】
【課題を解決するための手段】
本発明の第１の側面は、
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置であり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルと、
前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する制御手段と、
を有することを特徴とするキャッシュ装置にある。
【００１６】
さらに、本発明のキャッシュ装置の一実施態様において、前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、前記制御手段は、共同管理するコンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持対象とする保留データ・ブロックの決定処理を、以下の処理、すなわち判定対象データ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍであるか否かを判定し、
Ｖ＝ｍである場合に、該データ・ブロックを保留データ・ブロックとして決定する処理、
を実行する構成であることを特徴とする。
【００１７】
さらに、本発明のキャッシュ装置の一実施態様において、前記制御手段は、記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループによる共同管理が可能か否かをキャッシュ装置間のメッセージ送受信により判定し、共同管理可能であると判定した場合に、前記キャッシュグループ・テーブルを生成する構成であることを特徴とする。
【００１８】
さらに、本発明のキャッシュ装置の一実施態様において、前記制御手段は、記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロック中から、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロック以外のデータ・ブロックについては、削除の許容されるデータ・ブロック管理リストとしてのフリーブロックリストにより管理する構成であることを特徴とする。
【００１９】
さらに、本発明のキャッシュ装置の一実施態様において、前記削除保留リストは、データ・ブロックの保存優先度に応じた複数のリストによって構成され、前記制御手段は、データ・ブロックの保存優先度を判定し、該判定結果に基づいて選択した削除保留リストに対して前記管理データ・ブロックに対応するエントリの設定を行なう構成であることを特徴とする。
【００２０】
さらに、本発明のキャッシュ装置の一実施態様において、前記制御手段は、端末からのデータ・ブロック取得要求が、前記キャッシュグループによる共同管理対象のコンテンツに含まれるデータ・ブロック取得要求である場合に、取得要求対象のデータ・ブロックが前記キャッシュグループを構成するいずれのキャッシュ装置の保持対象データ・ブロックであるかを判定し、該判定結果に基づいてデータ・ブロックを自キャッシュ装置または、前記キャッシュグループを構成する他のキャッシュ装置から取得する処理を実行する構成であることを特徴とする。
【００２１】
さらに、本発明のキャッシュ装置の一実施態様において、前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、前記制御手段は、取得要求対象のデータ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍを算出し、
算出したｍをグループ・メンバー番号として有するキャッシュ装置からデータ・ブロックの取得処理を実行する構成であることを特徴とする。
【００２２】
さらに、本発明の第２の側面は、
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置におけるキャッシュデータ管理方法であり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定する保留データ・ブロック決定ステップと、
決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する管理ステップと、
を有することを特徴とするキャッシュデータ管理方法にある。
【００２３】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、前記保留データ・ブロック決定ステップは、共同管理するコンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持対象とする保留データ・ブロックの決定処理を、以下の処理、すなわち、
判定対象データ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍであるか否かを判定し、
Ｖ＝ｍである場合に、該データ・ブロックを保留データ・ブロックとして決定する処理を実行することを特徴とする。
【００２４】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記キャッシュデータ管理方法は、さらに、記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループによる共同管理が可能か否かをキャッシュ装置間のメッセージ送受信により判定し、共同管理可能であると判定した場合に、前記キャッシュグループ・テーブルを生成する処理を実行することを特徴とする。
【００２５】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記キャッシュデータ管理方法は、さらに、記憶手段に格納したデータ・ブロックについての管理リストであるＬＲＵリストからの排除対象エントリに対応するデータ・ブロックについて、前記キャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロック中から、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定し、決定した保留データ・ブロック以外のデータ・ブロックについては、削除の許容されるデータ・ブロック管理リストとしてのフリーブロックリストにより管理するステップを含むことを特徴とする。
【００２６】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記削除保留リストは、データ・ブロックの保存優先度に応じた複数のリストによって構成され、前記キャッシュデータ管理方法は、さらに、データ・ブロックの保存優先度を判定し、該判定結果に基づいて選択した削除保留リストに対して前記管理データ・ブロックに対応するエントリの設定を行なうステップを含むことを特徴とする。
【００２７】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記キャッシュデータ管理方法は、さらに、端末からのデータ・ブロック取得要求が、前記キャッシュグループによる共同管理対象のコンテンツに含まれるデータ・ブロック取得要求である場合に、取得要求対象のデータ・ブロックが前記キャッシュグループを構成するいずれのキャッシュ装置の保持対象データ・ブロックであるかを判定し、該判定結果に基づいてデータ・ブロックを自キャッシュ装置または、前記キャッシュグループを構成する他のキャッシュ装置から取得するデータ・ブロック取得処理を実行するステップを含むことを特徴とする。
【００２８】
さらに、本発明のキャッシュデータ管理方法の一実施態様において、前記キャッシュグループ・テーブルは、キャッシュグループによって共同管理するコンテンツの識別子と、キャッシュグループを構成するキャッシュ装置数：Ｎと、各キャッシュ装置に対応して設定されるグループ・メンバー番号：ｍとを有し、前記データ・ブロック取得処理は、取得要求対象のデータ・ブロックが構成要素となるコンテンツの先頭データ・ブロックからのオフセット情報としてのブロックオフセット番号：Ｃに基づいて、
Ｃ　ｍｏｄ　Ｎを算出し、
Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
Ｖ＝ｍを算出し、
算出したｍをグループ・メンバー番号として有するキャッシュ装置からデータ・ブロックを取得する処理として実行することを特徴とする。
【００２９】
さらに、本発明の第３の側面は、
ネットワークを介して受信したデータをキャッシュデータとして格納し、端末からのデータ要求に応じてキャッシュデータを取得して端末に送信するキャッシュ装置におけるキャッシュデータ管理処理を実行するコンピュータ・プグラムであり、
自キャッシュ装置およびネットワークに接続された他のキャッシュ装置によって構成され、コンテンツの共同管理を実行するキャッシュグループに関するグループ設定情報を格納したキャッシュグループ・テーブルの格納情報に基づいて、コンテンツを構成する複数のデータ・ブロックから、自キャッシュ装置における記憶保持データとしての保留データ・ブロックを決定する保留データ・ブロック決定ステップと、
決定した保留データ・ブロックの対応情報からなるエントリによって構成される削除保留リストに従って保留データ・ブロックの管理を実行する管理ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００３０】
【作用】
本発明の構成によれば、ネットワーク接続されたキャッシュ装置におけるキャッシュ・リプレースメント処理において、削除保留ブロックに関するリストを保持して、キャッシュグループ内のキャッシュ装置ごとに各々削除保留されるデータ・ブロックが異なるようにデータ管理を行なう構成としたので、各キャッシュ装置が単独でキャッシュ・リプレースメントの管理をしている場合に比べて効率的な記憶領域の利用が図れ、また、端末からのデータ要求に応じて複数のキャッシュ装置に記憶したデータ・ブロックを集めて送信することが可能となり、ネットワークトラフィックの軽減、キャッシュ装置のヒット率の向上が実現される。
【００３１】
さらに、本発明の多段の削除保留リストを適用したキャッシュ装置構成によれば、保持重要度の高いデータが削除されずにキャッシュに残る可能性が高くなるため、さらに、キャッシュヒット率の向上を達成することが可能となる。
【００３２】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００３３】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【００３４】
【発明の実施の形態】
以下、本発明のキャッシュ装置、およびキャッシュデータ管理方法について、図面を参照して、詳細に説明する。
【００３５】
［キャッシュ装置および処理概要］
図２は、本発明のキャッシュ装置を適用可能なネットワークシステムの全体構成例を示す図である。この図２に示す構成は、一般的なインターネット・キャッシュ装置、サーバー装置、端末装置から成るシステムと同様である。本発明のキャッシュ装置は、従来のネットワークシステム構成での適用が可能であり、ネットワーク内の複数のキャッシュ装置でグループ設定を行ない、グループ内においてキャッシュデータの管理を実行する。
【００３６】
各キャッシュ装置１（２１１）〜キャッシュ装置４（２１４）は、お互いにネットワークで接続されていると共に、コンテンツサーバー２０１から配信されるデータ（コンテンツ）を一時的に保存する機能を持つ。キャッシュ装置２１１〜２１４のネットワーク下流側には、コンテンツを受信する複数の端末装置、例えばユーザーＰＣ、携帯通信端末等の各種端末を接続できる構成となっている。
【００３７】
キャッシュ装置１（２１１）には、コンテンツ受信端末としての端末２２１ａ〜ｃ・・、キャッシュ装置２（２１２）には、端末２３１ａ〜ｃ・・、キャッシュ装置３（２１３）には、端末２４１ａ〜ｂ・・、キャッシュ装置４（２１４）には、端末２５１ａ〜ｃ・・がそれぞれ接続される。
【００３８】
ある端末からコンテンツデータの取得要求があると、コンテンツサーバー２０１からデータを読み出すか、中間にあるキャッシュ装置からデータを読み出す。端末からのコンテンツ要求は、例えば、コンテンツファイルのリソース情報としてのＵＲＬ（Ｕｎｉｆｏｒｍ　Ｒｅｓｏｕｒｃｅ　Ｌｏｃａｔｏｒ）を指定したコンテンンツ取得要求メッセージの送信によって行なわれる。
【００３９】
キャッシュ装置に端末から取得要求のあったコンテンツのＵＲＬに対応するデータが保存されている場合は、このキャッシュ装置からデータを読み出す。キャッシュからのデータ読み出しにより、コンテンツサーバー２０１からキャッシュ装置間におけるデータ転送が省略可能となり、ネットワーク上のデータトラフィックが緩和される。
【００４０】
本発明の構成では、ネットワークで接続された複数のキャッシュ装置、例えば、図２に示すキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）を「キャッシュグループ」としてグループ化し、これら複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）間で、コンテンツの共同管理、すなわち複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）でのコンテンツの分散保持を実行する。以下、本発明におけるキャッシュ管理の構成、および方法について説明する。
【００４１】
図２のキャッシュグループに属する４つのキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）に、例えば図３に示すように、同じコンテンツデータがキャッシュされているとする。コンテンツは、データ・ブロック１〜７からなる。図３のように各キャッシュ装置１（２１１）〜キャッシュ装置４（２１４）で同じデータ・ブロック１〜７を保存しているものとする。これらのデータ・ブロック１〜７は、それぞれのキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）がそれぞれの接続端末からの要求に応じて、コンテンツサーバー２０１から受信し、一時記憶しているデータ、すなわちキャッシュデータである。
【００４２】
もし、従来と同様、個々のキャッシュ装置が単独で、キャッシュ・リプレースメント処理を実行すると、個々のキャッシュ装置は、新しく記憶手段に格納、すなわちキャッシュすべきデータを保存するために、端末からの取得要求頻度の低いデータ・ブロックを削除することになる。この削除したデータを再度提供する場合には、既にキャッシュ装置にデータが無いために、コンテンツサーバー２０１へデータを取りに行くことになる。
【００４３】
本発明のキャッシュ装置は、複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）で構成するキャッシュグループで、データを共同管理する。
【００４４】
本発明のキャッシュデータ管理方法では、同じコンテンツデータを持つ複数のキャッシュ装置を使ってキャッシュをグループ化してキャッシュするデータを管理する。本発明におけるキャッシュ装置のキャッシュ・リプレースメントは、キャッシュグループを構成する複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）を単位として実行する。
【００４５】
キャッシュグループを構成するキャッシュ装置ごとに削除されずに残っているデータが異なるデータとなるように制御されてデータ削除を実行する。従って、キャッシュ装置におけるデータ格納領域の効率的利用が可能となる。さらに、端末からのデータ要求に応答して、キャッシュグループの複数キャッシュ装置から各格納データを転送して端末に対する出力が可能となり、総合的にキャッシュ装置のヒット率を向上させることが可能となる。
【００４６】
具体例について、図を参照して説明する。図３のように、キャッシュグループを構成する複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）の各々が、同じコンテンツデータ・ブロック１〜７を格納していた場合、キャッシュグループを単位としたデータ管理により、キャッシュ装置ごとに削除されずに残っているデータが異なるデータとなるようにデータ削除、すなわちキャッシュ・リプレースメントを実行する。
【００４７】
このキャッシュグループを単位としたキャッシュ・リプレースメントの結果、図４に示すように、キャッシュ装置１（２１１）は、データ・ブロック１，５をキャッシュデータとして保持し、データ・ブロック２，３，４，６，７をフリーリスト（削除データ・ブロックに相当）に移動する。キャッシュ装置２（２１２）は、データ・ブロック２，６をキャッシュデータとして保持し、データ・ブロック１，３，４，５，７をフリーリストに移動する。キャッシュ装置３（２１３）は、データ・ブロック３，７をキャッシュデータとして保持し、データ・ブロック１，２，４，５，６をフリーリストに移動する。キャッシュ装置４（２１４）は、データ・ブロック４をキャッシュデータとして保持し、データ・ブロック１，２，３，５，６，７をフリーリストに移動する。
【００４８】
このように、キャッシュグループを構成する複数のキャッシュ装置１（２１１）〜キャッシュ装置４（２１４）全体としてキャッシュ・リプレースメントを行ない、コンテンツ共同管理を実行する。キャッシュグループ単位でのキャッシュ・リプレースメント処理の具体的処理態様について説明する。
【００４９】
あらかじめ決めた一定の時間間隔ごとに、各キャッシュ装置が独自に持っているＬＲＵリスト（図１参照）から、キャッシュ・リプレースメントによって近々に消去される可能性のある順にブロックをスキャンし、その消去予定のブロックに対応するコンテンツを持つキャッシュ装置が近隣にあるかどうかを問い合わせ、さらに、問い合わせ先のキャッシュ装置が消去予定のコンテンツを持っている場合には、相互にキャッシュグループを組めるか否かを確認する。
【００５０】
このような問い合わせに適用する送受信メッセージは、例えばネットワーク接続されたキャッシュ間のメッセージ送受信プロトコルとして定義されたＩＣＰ（Ｉｎｔｅｒｎｅｔ　Ｃａｃｈｅ　Ｐｒｏｔｏｃｏｌ）プロトコルが適用可能である。従来のＩＣＰの仕様中には、キャッシュグループに参加できるかどうかの確認機能についてまで規定されていないが、例えば、ＩＣＰ中のオペコードの１つとして定義されているＩＰ＿ＯＰ＿ＱＵＥＲＹメッセージ中のＯＰＴＩＯＮ　Ｆｌａｇを拡張して、キャッシュグループに参加できるかどうかの確認メッセージを送受信することが可能である。
【００５１】
ネットワーク接続されたキャッシュ間のメッセージ送受信プロトコルとして定義されたＩＣＰ（Ｉｎｔｅｒｎｅｔ　Ｃａｃｈｅ　Ｐｒｏｔｏｃｏｌ）プロトコルのフォーマットを図５（ａ）に、ＩＣＰ中のオペコードの１つとして定義されているＩＰ＿ＯＰ＿ＱＵＥＲＹメッセージフォーマットを図５（ｂ）に示す。ＩＣＰフォーマットは、図５（ａ）に示すように、オペコード、バージョン、メッセージ長、リクエストＮｏ．、オプション、オプションデータ、送信側ホストアドレス、ペイロードの各データフィールドを有する。
【００５２】
特定のコンテンツデータを持っているか、およびキャッシュグループに参加できるかを、近隣のキャッシュ装置に問い合わせる際には、コンテンツファイルのリソース情報としてのＵＲＬ（Ｕｎｉｆｏｒｍ　Ｒｅｓｏｕｒｃｅ　Ｌｏｃａｔｏｒ）を指定して、近隣キャッシュ装置に問い合わせメッセージを送信する。この問い合わせメッセージの１形態として、ＩＣＰ（Ｉｎｔｅｒｎｅｔ　Ｃａｃｈｅ　Ｐｒｏｔｏｃｏｌ）プロトコルのＯＰＴＩＯＮ　Ｆｌａｇの拡張を行ない、ＩＣＰ＿ＯＰ＿ＱＵＥＲＹで、コンテンツファイルのリソース情報としてのＵＲＬを指定するとともに、このコンテンツについてキャッシュグループのメンバーとして参加可能かの確認の意味を含むフラグ（例えば、０ｘ２０００００００（ＩＣＰ＿ＦＬＡＧ＿ＧＲＯＵＰ＿ＲＥＱ））を追加する。なお、この問い合わせメッセージは、この手法に限らず、他のフォーマット、プロトコルを使用することも可能である。
【００５３】
なお、このコンテンツ保持問い合わせは、問い合わせを行なうキャッシュ装置が、マルチキャスト（Ｍｕｌｔｉｃａｓｔ）を適用して、複数の近隣キャッシュ装置に一度に問い合わせることも可能である。
【００５４】
なお、本発明において、「近隣のキャッシュ装置」とは、ある１つのキャッシュ装置に対してキャッシュグループとして組む可能性のあるキャッシュ装置の候補であり、例えばデータ送受信処理を、あらかじめ定めた許容時間内に実行可能なキャッシュ装置として設定される。
【００５５】
「近隣のキャッシュ装置」の具体的な設定態様としては、例えば、キャッシュ装置の設定ファイルにキャッシュグループを組める可能性のある複数のキャッシュ装置を予め登録し、これらの登録キャッシュ装置にｐｉｎｇなどを使ってキャッシュ装置間のＲＴＴ（Ｒｏｕｎｄ　Ｔｒｉｐ　Ｔｉｍｅ）を測定し、ＲＴＴが許容時間範囲内にある複数のキャッシュ装置を「近隣のキャッシュ装置」として設定することが可能である。
【００５６】
キャッシュグループの設定を実行するキャッシュ装置は、「近隣のキャッシュ装置」に関するリストを保持する。リストは、対象となるキャッシュ装置に関するデータとして、ホスト名、ＩＰアドレス、ＩＣＰポート番号を保存したリストである。
【００５７】
キャッシュ装置リスト構成例を図６に示す。キャッシュ装置リストは、図６に示すように、近隣のキャッシュ装置として設定されたキャッシュ装置に関するデータとして、ホスト名、ＩＰアドレス、ＩＣＰポート番号を保存したリストである。
【００５８】
コンテンツ保持の有無および、グループ参加可否についての問い合わせを近隣のキャッシュ装置に対して実行しようとするキャッシュ装置は、例えば、ＩＣＰ＿ＯＰ＿ＱＵＥＲＹで、あるコンテンツデータに対応するＵＲＬを指定して問い合わせメッセージをブロードキャスト、マルチキャスト等により送信する。問い合わせを実行したキャッシュ装置は、問い合わせメッセージに対する答えを待つことになる。
【００５９】
しかし、応答を無限に待つことはできないし、マルチキャストで問い合わせした場合は、どれだけ返事が戻るか不明であるため、あらかじめ決めた一定時間の範囲内において、ヒット（ＨＩＴ）応答、すなわち問い合わせに係るＵＲＬに関連するコンテンツデータを持っているとの応答が何処からいくつ戻るかをカウントし内部のキャッシュグループ・テーブル（対象とするコンテンツデータの識別子（ＵＲＬ，コンテンツＩＤ等）、グループの構成メンバー数、グループＩＤ、キャッシュグループを構成するメンバーの（メンバー番号とＩＰアドレスリストの対データ））に記憶する。
【００６０】
応答メッセージは、問い合わせに係るＵＲＬに関連するコンテンツデータを持っているとの応答として、例えばＩＣＰメッセージのＩＣＰ＿ＯＰ＿ＨＩＴ、また、コンテンツデータを持っていない旨の応答として、ＩＣＰ＿ＯＰ＿ＭＩＳＳを用いた応答メッセージが適用可能である。
【００６１】
上述の問い合わせメッセージを受信したキャッシュ装置は、問い合わせを送信してきたキャッシュ装置とのキャッシュグループを構成するメンバーになることを承諾し、さらに、キャッシュグループ形成までの間、問い合わせのあったコンテンツに対応するデータ・ブロックを削除せずに保持できる能力を持つ場合に、ＨＩＴ応答を返す。
【００６２】
問い合わせメッセージを送信したキャッシュ装置と、ＨＩＴ応答を返した１以上のキャッシュ装置とによって、問い合わせメッセージの指定コンテンツに関するキャッシュグループを構成する。
【００６３】
問い合わせメッセージを送信し、応答メッセージを受信したキャッシュ装置が、１以上のＨＩＴ応答を受信してキャッシュグループを設定した場合は、キャッシュグループを構成するキャッシュ装置数（Ｎ），当該キャッシュ装置のキャッシュグループを構成するキャッシュ装置（メンバー）識別子としてのグループ・メンバー番号（ｍ）、キャッシュグループでの処理対象コンテンツデータ識別子（ＣＩＤ）などのグループ設定情報を、キャッシュグループを構成する各キャッシュ装置に伝える。
【００６４】
なお、キャッシュ装置（メンバー）識別子としてのグループ・メンバー番号（ｍ）は、キャッシュ装置のＩＰアドレスに対応して設定され、キャッシュグループを構成する全てのキャッシュ装置（メンバー）は、キャッシュグループを構成する他の全てのキャッシュ装置（メンバー）識別子としてのグループ・メンバー番号（ｍ）とＩＰアドレスの対応情報を取得する。
【００６５】
グループ設定情報の伝達には、上述の問い合わせメッセージと同様、ＩＣＰが適用可能である。例えば、ＩＣＰにおいて、情報通知のためのＩＣＰ＿ＯＰ＿ＮＯＴＩＦＹのようなオペコードを独自に追加し、ペイロード部分に図７のようなキャッシュ装置（メンバー）のグループ・メンバー番号と、ＩＰアドレスデータを格納してキャッシュグループを構成する各キャッシュ装置に送信し、通知することになる。なお、図７に示す例は、ＩＰアドレスとしてＩＰｖ４を適用した例である。
【００６６】
図７に示すように、ペイロード部には、キャッシュグループを構成する全て（Ｎ）のキャッシュ装置（メンバー）のグループ・メンバー番号（キャッシュ・メンバー＃１〜＃Ｎ）とＩＰアドレス情報が格納される。これらの情報を受領することにより、キャッシュグループを構成する全てのキャッシュ装置（メンバー）は、キャッシュグループを構成する他の全てのキャッシュ装置（メンバー）のグループ・メンバー番号とＩＰアドレスの対応を知ることができる。
【００６７】
グループ設定情報を伝達したキャッシュ装置、およびグループ設定情報を伝達された、キャッシュグループに属するキャッシュ装置は、図８に示すようなグループ設定情報を格納したキャッシュグループ・テーブルを自己の管理情報としてメモリに格納する。
【００６８】
キャッシュグループ・テーブルには、上述のグループ設定情報に基づいて取得される情報、すなわち、設定キャッシュグループにおいて共同管理するコンテンツの識別子、キャッシュグループの構成キャッシュ装置数［Ｎ］、キャッシュグループの識別子（ＩＤ）、およびキャッシュグループのメンバーリストとして、メンバー番号とＩＰアドレスの対応データとが格納される。
【００６９】
このようにして作成したキャッシュグループを構成する各キャッシュ装置は、単独のデータ（コンテンツ）管理ではなく、グループ全体でのコンテンツデータの管理を行なう。以下、キャッシュグループ内の各キャッシュ装置におけるコンテンツ管理方法について説明する。
【００７０】
キャッシュグループ内の各キャッシュ装置は、図９に示すように、利用頻度順にデータ・ブロックを並べた（ａ）ＬＲＵリストと、キャッシュの空き領域ブロックをポインタ情報として持つ（ｃ）フリーブロックリスト、さらに、（ｂ）削除保留リストを有する。
【００７１】
削除保留リストとは、ＬＲＵリストから排除、例えば削除対象ブロックとなったデータ・ブロックの内、一時的に削除保留状態に設定したデータ・ブロックを管理するリストである。ＬＲＵリストから排除するエントリに対応するデータ・ブロックを削除対象として、フリーブロックリストで管理するか、あるいは削除を保留すべきブロックとして、削除保留リストで管理するかの判定は、以下の処理手順によって行なう。
【００７２】
削除保留状態に設定するか否かの判定は、以下の処理手順について説明する。判定対象コンテンツの先頭からのブロックオフセット番号をＣ、キャッシュグループを構成するキャッシュ装置数をＮ、キャッシュグループにおける自己に設定されたグループ・メンバー番号をｍとしたときに、
（１）　Ｃ　ｍｏｄ　Ｎを算出する。
（２）　Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
（３）　Ｖ＝ｍであれば、削除保留状態に設定する。
Ｖ≠ｍであれば、削除保留状態に設定せず削除する。
【００７３】
上述の処理を、キャッシュグループを構成するキャッシュ装置の各々で実行することにより、先に図４を参照して説明したように、キャッシュ装置間で、重複の無いデータ・ブロックの格納構成が実現される。
【００７４】
すなわち、ｍ＝１であるキャッシュ装置１（２１１）は、データ・ブロック１，５を削除保留状態として保持し、削除保留リストの管理ブロックとし、データ・ブロック２，３，４，６，７を削除対象としてフリーリストで管理する。ｍ＝２であるキャッシュ装置２（２１２）は、データ・ブロック２，６を削除保留状態として保持し、削除保留リストの管理ブロックとし、データ・ブロック１，３，４，５，７をフリーリストで管理する。ｍ＝３であるキャッシュ装置３（２１３）は、データ・ブロック３，７を削除保留状態として保持し、削除保留リストの管理ブロックとし、データ・ブロック１，２，４，５，６をフリーリストで管理する。ｍ＝４であるキャッシュ装置４（２１４）は、データ・ブロック４を削除保留状態として保持し、削除保留リストの管理ブロックとし、データ・ブロック１，２，３，５，６，７をフリーリストで管理する構成が実現される。
【００７５】
上述の処理の詳細について、キャッシュグループ内の各キャッシュ装置の有するＬＲＵリスト、削除保留リスト、フリーブロックリストの内部構造を参照しながら説明する。
【００７６】
まず、ＬＲＵリストの構成について図１０を参照して説明する。図１０に示すように、各キャッシュ装置は、自己のキャッシュデータを格納する記憶手段としてのデータ格納領域３２０、およびデータ格納領域に格納したデータに対するリストとしてのＬＲＵリスト３１０を有する。
【００７７】
ＬＲＵリスト３１０は、各データ・ブロックに対応付けて生成される。ここでは、（ａ）〜（ｐ）のリストデータ（エントリ）が各データ・ブロックに対応付けられて保持されている。ＬＲＵリストの内部構造は、図１０に示すように、データ・ブロックヘのポインタ３１１、コンテンツ識別子３１２、ブロックオフセット３１３、ＬＲＵリストの前リストデータ（エントリ）のポインタ３１４、ＬＲＵリストの後続リストデータ（エントリ）のポインタ３１５を有する。
【００７８】
データ・ブロックヘのポインタ３１１は、各リストデータに対応する実コンテンツデータ・ブロックの、データ格納領域３２０における格納アドレスを示す。コンテンツ識別子３１２は、例えばＵＲＬ、または各データ・ブロックの識別データによって構成されるコンテンツＩＤである。ブロックオフセット３１３は、各コンテンツデータ・ブロックのコンテンツ先頭からのオフセットを示す。
【００７９】
オフセットは、例えばデータ格納領域におけるアドレス差分を用いることも可能であるが、ここでは、ある大きさごとにデータを区切ったブロックという単位で管理することにすると、先頭からのブロックオフセット番号Ｃの値が入る。（ａ）のリストに対して設定されるブロックオフセットは１、（ｂ）のリストに対して設定されるブロックオフセットは２となり、（ｐ）のリストに対して設定されるブロックオフセットは、コンテンツデータのブロックサイズがＮブロック分あるとすると、Ｎとなる。このようにブロックオフセットは、コンテンツ毎の、コンテンツ先頭からの位置識別データとしてのブロックオフセット番号Ｃとして設定される。
【００８０】
ＬＲＵリストの前リストデータ（エントリ）のポインタ３１４、ＬＲＵリスト後リストデータ（エントリ）のポインタ３１５は、それぞれ、リストの前後のエントリに対するポインタを示すデータである。従って、リスト先頭のリストデータ（ａ）の前リストデータのポインタはＮＵＬＬ、リスト最後尾のリストデータ（ｐ）の後リストデータのポインタもＮＵＬＬとして設定される。
【００８１】
ＬＲＵリスト中の各エントリが持つデータ・ブロックへのポインタに対応するコンテンツの識別子および先頭からのブロックオフセット番号：Ｃは、このエントリ中のデータを読むことで簡単に知ることが出来る。
【００８２】
次に、削除保留リストの構成について、図１１を参照して説明する。削除保留リストとは、前述したように、ＬＲＵリストで削除対象ブロックとなったデータ・ブロックの内、一時的に削除保留状態に設定したデータ・ブロックを管理するリストである。
【００８３】
図１１に示すように、キャッシュ装置の保有する削除保留リスト３３０は、削除保留状態に設定したデータ・データ・ブロックに対応付けて生成される。ここでは、（ａ）〜（ｐ）のリストデータ（エントリ）が削除保留状態に設定したデータ・データ・ブロックに対応付けられて保持されている。削除保留リストの内部構造は、図１１に示すように、データ・ブロックヘのポインタ３３１、コンテンツ識別子３３２、ブロックオフセット３３３、設定されたキャッシュグループのグループ識別子（ＧＰ）３３４、削除保留リストの前リストデータ（エントリ）のポインタ３３５、削除保留リストの後続リストデータ（エントリ）のポインタ３３６を有する。
【００８４】
キャッシュ装置の保有する削除保留リスト３３０の格納データは、先に説明したＬＲＵリストの格納データにグループ識別子（ＧＰ）３３４を付加した構成となる。グループ識別子（ＧＰ）３３４は、キャッシュグループ作成時に設定されるキャッシュグループを識別するグループＩＤである。キャッシュグループを設定したキャッシュ装置によって設定され、キャッシュグループを構成する他のキャッシュ装置は、キャッシュグループを設定したキャッシュ装置から送信されるグループ設定情報により通知され、キャッシュグループ・テーブル（図８参照）に記録されたＩＤである。
【００８５】
次に、フリーブロックリストの構成について、図１２を参照して説明する。フリーブロックリストとは、前述したように、ＬＲＵリストで削除対象ブロックとなったデータ・ブロックの内、削除保留状態に設定されずに削除対象となったデータ・ブロック、および削除保留状態に一旦、設定されたものの、その後、削除対象となったデータ・ブロックに対応する管理リストである。
【００８６】
図１２に示すように、キャッシュ装置の保有するフリーブロックリスト３５０は、データ格納領域３２０のデータ格納ブロック中、上書き、消去可能なデータ・ブロックへのポインタ３５１を持ち、フリーブロックリストの前リストデータ（エントリ）のポインタ３５２、フリーブロックリストの後続リストデータ（エントリ）のポインタ３５３を有する。
【００８７】
次に、キャッシュグループを構成する各キャッシュ装置において、新規入力データが発生し、データ・ブロックを削除保留リスト、あるいはフリーブロックリストの管理データに移行する際の処理手順について説明する。
【００８８】
まず、キャッシュ装置は、ＬＲＵリストから処理対象とするデータ・ブロックに対応するエントリ（リストデータ）を抽出し、抽出したＬＲＵリストのエントリからブロックオフセット番号：Ｃ（図１０：ブロックオフセット３１３）を読み出す。
【００８９】
次に、キャッシュ装置は、ブロックオフセット番号：Ｃの値に基づいて、上述した処理を実行する。すなわち、
（１）　Ｃ　ｍｏｄ　Ｎを算出する。
（２）　Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）、
として、
（３）Ｖ＝ｍであれば、削除保留状態に設定、すなわち、
対応するデータ・ブロックの管理リストデータを削除保留リストに移動する。このデータ・ブロックは、データ格納領域において消去されずに保持される。
（３’）一方、Ｖ≠ｍであれば、削除保留状態に設定しない。すなわち、
対応するデータ・ブロックの管理リストデータをフリーブロックリストに移動する。このデータ・ブロックは、データ格納領域において消去、上書き可能ブロックとして設定されることになる。
【００９０】
Ｖ＝ｍである場合は、設定したキャッシュグループにおいて、自装置がそのデータ・ブロックを保留すべきであると判定し、ＬＲＵリストからの削除予定エントリを削除保留リストに移動し、コンテンツデータ・ブロックを削除することなく、メモリに残し、削除保留リストでの管理を実行する。また、Ｖ≠ｍの場合は、設定したキャッシュグループにおいて、自装置がデータ・ブロックを保留する必要がない、すなわち、そのデータ・ブロックは、他のグループ・メンバーにおいて保持すべきデータ・ブロックであると判定し、ＬＲＵリストからの削除予定エントリをフリーブロックリストに移動して、対応データ・ブロックを削除可能状態とするものである。なお、削除されたデータ・ブロックは、キャッシュグループの他のメンバーが保持しており、これを取得して端末に送信可能となる。この処理については後述する。
【００９１】
リストに対するエントリの移動は、図９に示す処理となる。例えばキャッシュ装置１において、新規データ・ブロックの書き込み要求があると、（ｃ）フリーブロックリストの先頭エントリ２７１に設定されたデータ・ブロック・ポインタに対応するデータ格納領域のデータ記憶領域に新規データ・ブロックが書き込まれ、書き込まれたデータ・ブロックに関する情報は、図１０のＬＲＵリストの先頭エントリ２７２に移される。
【００９２】
その結果、もしＬＲＵリストの長さが許容リスト長を超えることになった場合は、ＬＲＵリストの末尾のエントリ２７３が、削除保留リストあるいは、フリーブロックリストに移動することになる。どちらに移動するかの判定は、前述の（１）〜（３）に示すＣ　ｍｏｄ　Ｎの算出、Ｖの値の判定に従う。
【００９３】
上述した判定処理の結果、ＬＲＵリストの末尾のエントリ２７３を削除保留リストに移動すると決定した場合は、ＬＲＵリストの末尾のエントリ２７３が削除保留リストの末尾のエントリ２７４として設定される。また、上述した判定処理の結果、フリーブロックリストに移動すると決定した場合は、ＬＲＵリストの末尾のエントリ２７３がフリーブロックリストの末尾のエントリ２７５として設定される。
【００９４】
また、削除保留リストに新たなエントリが加わり、削除保留リストが予め定められたリスト長を超えることとなった場合は、削除保留リストの先頭のエントリ２７６が、フリーブロックリストの末尾のエントリ２７５として設定される。
【００９５】
なお、フリーブロックリストに対応して確保すべきバッファ量が、予め定められており、これが、新規データの格納により不足することとなった場合は、ＬＲＵリストあるいは削除保留リストからのフリーブロックリストへの移動、すなわちデータ・ブロックの削除によるバッファ量確保処理が実行される。
【００９６】
フリーブロックリストへ移動されたエントリの指定するデータ・ブロック・ポインタの指定するメモリ領域は、新たな入力データの書き込みに適用され、データ・ブロックの内容が捨てられることになる。
【００９７】
［キャッシュグループ形成およびデータ管理処理］
次に、上述したキャッシュグループにおけるグループ形成、データ管理の手順について、フローチャートおよびシーケンス図を参照して説明する。
【００９８】
まず、キャッシュグループの生成処理、データ管理手順について、図１３および図１４を参照して説明する。
【００９９】
キャッシュグループは、自己のキャッシュ装置に格納したコンテンツのデータ・ブロックをＬＲＵリストから削除保留リストによる管理に移動して、グループでの共同管理を行なう場合に生成される。図１３のフローに従って、キャッシュグループの生成処理手順について説明する。
【０１００】
まず、ネットワーク接続されたキャッシュ装置は、事前準備処理として、キャッシュグループのメンバー候補の登録を行なう。これは、図１３におけるステップＳ１０１〜Ｓ１０４のステップである。
【０１０１】
ステップＳ１０１において、キャッシュグループを組む可能性のあるキャッシュ装置情報を登録する。これは、例えばオペレータが選択した１以上のキャッシュ装置のホスト名、ＩＰアドレス、ＩＣＰポート番号の登録情報である。
【０１０２】
次に、これらの登録情報から実際にキャッシュグループを設定可能なキャッシュ装置を判定する。これは、ステップＳ１０１において登録された各キャッシュ装置にｐｉｎｇなどを使ってキャッシュ装置間のＲＴＴ（Ｒｏｕｎｄ　ＴｒｉｐＴｉｍｅ）を測定し、ＲＴＴが許容時間範囲内にある複数のキャッシュ装置を選択するものであり、ステップＳ１０２のＲＴＴ測定処理、ステップＳ１０３の判定処理によって、あらかじめ定めた閾値以下のＲＴＴを持つキャッシュ装置をステップＳ１０４において、「近隣のキャッシュ装置」として設定する。
【０１０３】
キャッシュ装置は、「近隣のキャッシュ装置」として設定されたキャッシュ装置リストを保持する。リストは、先に図６を参照して説明したように、近隣のキャッシュ装置に関するホスト名、ＩＰアドレス、ＩＣＰポート番号を保存したリストである。
【０１０４】
図１３のステップＳ１０２〜Ｓ１０４のステップに対応するデータ通信シーケンスが図１４の［処理Ｐ］に相当する。図１４のシーケンス図においては、キャッシュ装置Ａが処理主体となるキャッシュ装置であり、キャッシュ装置Ｂ，Ｃ，Ｄが図１３のステップＳ１０１において登録されたキャッシュ装置に相当する。
【０１０５】
図１４の［処理Ｐ］がＲＴＴ測定処理に相当する。キャッシュ装置Ａは、キャッシュ装置Ｂ，Ｃ，Ｄに対して登録された各キャッシュ装置Ｂ，Ｃ，Ｄにｐｉｎｇなどを使ってキャッシュ装置間のＲＴＴ（Ｒｏｕｎｄ　Ｔｒｉｐ　Ｔｉｍｅ）を測定し、ＲＴＴが許容時間範囲内にある複数のキャッシュ装置を選択する。
【０１０６】
図１３のフローに戻り、説明を続ける。図６に示す近隣のキャッシュ装置リストが生成されると、キャッシュ装置は、ステップＳ１０５において、所定時間毎に、キャッシュ・リプレースメントにより、自己の保有するＬＲＵリストから削除すべきコンテンツデータ・ブロックが発生したか否かの判定を実行する。
【０１０７】
ＬＲＵリストから削除すべきデータ・ブロックがあると判定すると、ステップＳ１０６に進み、ＬＲＵリスト中の削除予定のエントリを抽出し、ステップＳ１０７において、そのエントリに対応するコンテンツがキャッシュグループ・テーブルに登録ずみのコンテンツであるかを判定する。
【０１０８】
キャッシュグループ・テーブルは、先に、図８を参照して説明したように、設定キャッシュグループにおいて共同管理するコンテンツの識別子、キャッシュグループの構成キャッシュ装置数［Ｎ］、キャッシュグループの識別子（ＩＤ）、およびキャッシュグループのメンバーリストとして、メンバー番号とＩＰアドレスの対応データとが格納されたテーブルであり、キャッシュグループ・テーブルに登録されたコンテンツは、設定されたキャッシュグループにおいて共同管理が実行されていることを示す。
【０１０９】
ステップＳ１０７において、ＬＲＵリストから削除予定のコンテンツがキャッシュグループ・テーブルに登録されている場合は、設定されたキャッシュグループにおいて共同管理が実行されているコンテンツであり、共同管理処理として、ステップＳ１１５以下の処理を実行することになる。この処理の詳細については、後段で説明する。
【０１１０】
ステップＳ１０７において、ＬＲＵリストから削除予定のコンテンツがキャッシュグループ・テーブルに登録されていない場合は、ステップＳ１０８以下において、ＬＲＵリストから削除予定のコンテンツに対応する新たなキャッシュグループを生成する。
【０１１１】
ステップＳ１０８では、先のステップＳ１０４で設定したＲＴＴが閾値以下の近隣キャッシュ装置リスト（図６参照）に設定された各キャッシュ装置に対して、ＬＲＵリストから削除予定のコンテンツに関するキャッシュグループを組むことが可能か否かの問い合わせメッセージを送信する。
【０１１２】
この問い合わせメッセージは、ＬＲＵリストから削除予定のエントリに対応するコンテンツ保持の有無および、グループ参加可否についての問い合わせメッセージである。図１４のシーケンス図では、［処理Ｑ］のＩＣＰ＿ＯＰ＿ＱＵＥＲＹがこの問い合わせメッセージに相当する。
【０１１３】
図１３のステップＳ１０９で、キャッシュ装置は、問い合わせメッセージに対する応答を待機し、ステップＳ１１０で応答が、グループ構成可（ＨＩＴ）であるか否かを判定し、ステップＳ１１１において、グループ構成可（ＨＩＴ）であるキャッシュ装置について、のデータをキャッシュグループ・テーブル（図８参照）に登録する。ステップＳ１１２では、全てのグループ・メンバー候補（図６の近隣キャッシュ装置リストに登録されたキャッシュ装置）に対する返事の確認が終了したかを判定して、キャッシュグループの仮設定を終える。
【０１１４】
図１４のシーケンス図では、［処理Ｑ］のＩＣＰ＿ＯＰ＿ＱＵＥＲＹ（問い合わせメッセージ）に対して、グループ構成可（ＨＩＴ）のキャッシュ装置Ｂ，Ｃが、ＩＣＰメッセージのＩＣＰ＿ＯＰ＿ＨＩＴをキャッシュ装置Ａに対する応答メッセージとして送信し、グループ構成不可（ＭＩＳＳ）のキャッシュ装置Ｄが、ＩＣＰメッセージのＩＣＰ＿ＯＰ＿ＭＩＳＳをキャッシュ装置Ａに対する応答メッセージとして送信している。この場合、キャッシュ装置Ａは、キャッシュ装置Ｂ，Ｃと、キャッシュグループを構成する。
【０１１５】
図１３の処理フローのステップＳ１１３では、キャッシュグループ設定可能な数のキャッシュ装置からのＨＩＴ応答が取得できたかを判定する。例えば１以上のキャッシュ装置からＨＩＴ応答が得られればキャッシュグループ設定可能と判定することができる。キャッシュグループ設定可能な数のキャッシュ装置のＨＩＴ応答がなかった場合は、ステップＳ１１８に進み、キャッシュグループは設定せずにＬＲＵリストからの削除エントリをフリーブロックリストに移動する。この場合は、当エントリに対応するコンテンツのキャッシュグループでの共同管理は実行されない。
【０１１６】
ステップＳ１１３で、キャッシュグループ設定可能な数のキャッシュ装置からのＨＩＴ応答が取得できたと判定された場合は、ステップＳ１１４において、ＨＩＴ応答を返したキャッシュ装置であり、キャッシュグループ・テーブル（図８参照）にキャッシュグループのメンバーとして登録されたキャッシュ装置に対してグループ設定情報を送信する。
【０１１７】
グループ設定情報は、キャッシュグループを構成するキャッシュ装置数（Ｎ），当該キャッシュ装置のキャッシュグループを構成するキャッシュ装置（メンバー）識別子としてのグループ・メンバー番号（ｍ）、キャッシュグループでの処理対象コンテンツデータ識別子などの情報である。グループ・メンバー番号（ｍ）は、キャッシュ装置のＩＰアドレスに対応して設定され、キャッシュグループを構成する全てのキャッシュ装置（メンバー）は、キャッシュグループを構成する他の全てのキャッシュ装置（メンバー）識別子としてのグループ・メンバー番号（ｍ）とＩＰアドレスの対応情報を取得する。
【０１１８】
図１４のシーケンス図において、［処理Ｒ］のＩＣＰ＿ＯＰ＿ＮＯＴＩＦＹが、グループ設定情報の送信に相当し、この送信データフォーマットは、例えば先に図７を参照して説明したフォーマットに従ったものとなる。グループ設定情報を伝達したキャッシュ装置、およびグループ設定情報を伝達された、キャッシュグループに属するキャッシュ装置は、図８に示すようなグループ設定情報格納したキャッシュグループ・テーブルを自己の管理情報としてメモリに格納する。
【０１１９】
次にステップＳ１１５以下が、設定されたキャッシュグループにおけるコンテンツの共同管理処理として実行されるＬＲＵリストからの移動処理である。
【０１２０】
キャッシュ装置は、ステップＳ１１５において、ＬＲＵリストからの削除予定エントリについて、ブロックオフセット番号：Ｃ、キャッシュグループを構成するキャッシュ装置数：Ｎ、キャッシュグループにおける自己に設定されたグループ・メンバー番号：ｍの各値に基づいて、
（１）　Ｃ　ｍｏｄ　Ｎを算出し、
（２）　Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
（３）Ｖ＝ｍであるか否かを判定する。
【０１２１】
Ｖ＝ｍである場合は、設定したキャッシュグループにおいて、自装置がコンテンツを保留すべきであると判定し、ステップＳ１１６において、ＬＲＵリストからの削除予定エントリを削除保留リストに移動する。すなわち、コンテンツデータ・ブロックを削除することなく、メモリに残し、削除保留リストでの管理を実行する。
【０１２２】
Ｖ＝ｍでない場合は、設定したキャッシュグループにおいて、自装置がコンテンツを保留する必要がない、すなわち、他のグループ・メンバーにおいて保持すべきデータ・ブロックであると判定し、ステップＳ１１８において、ＬＲＵリストからの削除予定エントリをフリーブロックリストに移動する。この場合は、対応データ・ブロックは、削除されることになる。削除された場合でも、キャッシュグループの他のメンバーが保持しており、これを取得して端末に送信可能となる。この処理については後述する。
【０１２３】
さらに、ステップＳ１１６におけるＬＲＵリストから削除保留リストに対するエントリ移動により、削除保留リストのリスト長が許容値を超えることとなったとき（Ｓ１１７でＹｅｓ）は、ステップＳ１１８において、削除保留リストのエントリをフリーブロックリストに移動する処理を実行する。
【０１２４】
次に、図１５乃至図１７を参照して、キャッシュグループによるコンテンツ管理を実行しているキャッシュ装置に、端末からのコンテンツ要求が発生した場合の処理について説明する。
【０１２５】
図１５のステップＳ２０１において、キャッシュ装置が端末からコンテンツ取得要求を受信すると、キャッシュ装置は、ステップＳ２０２において、要求コンテンツデータがキャッシュグループ・テーブル（図８参照）に登録されたコンテンツであるか否かを判定する。登録されていない場合は、グループ管理されていないコンテンツであり、通常の処理、すなわち自装置に格納されている場合は、コンテンツを取得して端末に送信し、自装置に格納されていない場合は、コンテンツをコンテンツサーバーから取得して端末に送信する。
【０１２６】
要求コンテンツデータがキャッシュグループ・テーブル（図８参照）に登録されたコンテンツである場合は、グループ管理されているコンテンツであり、ステップＳ２０３で、キャッシュグループ・テーブル（図８参照）からキャッシュグループの構成要素数Ｎと、自身のメンバー番号ｍ１を取得する。
【０１２７】
ステップＳ２０４において、端末からのコンテンツ取得要求中に含まれるコンテンツのオフセット情報に基づいて、ブロックオフセットを算出して、ブロックオフセット番号：Ｃを取得する。次に、ステップＳ２０５において、キャッシュグループを構成するキャッシュ装置数：Ｎ、キャッシュグループにおける自己に設定されたグループ・メンバー番号：ｍ１の各値に基づいて、
（１）　Ｃ　ｍｏｄ　Ｎを算出し、
（２）　Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、
Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、
（３）Ｖ＝ｍ１であるか否かを判定する。
【０１２８】
Ｖ＝ｍ１である場合は、要求されたコンテンツが自装置内に格納されていることになり、ステップＳ２０６に進み、ＬＲＵリストまたは削除保留リストのエントリに基づいて要求コンテンツ名、ブロックオフセット番号から自装置内のデータ格納領域情報を取得し、ステップＳ２０７において、データの読み出しを実行し、正常読み出し完了を確認（Ｓ２０８）し、ステップＳ２０９において、グループＩＤ（Ｇｐ）＝０であるか否かを判定する。
【０１２９】
グループＩＤ（Ｇｐ）＝０は、設定されたキャッシュグループのメンバー離脱が発生して、キャッシュグループの維持を行なわない際にキャッシュ装置が、キャッシュグループ・テーブルのグループＩＤ（Ｇｐ）を書き換えることにより設定される。グループＩＤ（Ｇｐ）が、０の場合は、キャッシュグループから離脱したメンバーが多くなってグループを構成できないことを示すエントリであるため、ステップＳ２１０において、エントリを削除保留リストではなくＬＲＵリストの先頭に移動させる。
【０１３０】
また、グループＩＤ（Ｇｐ）＝０でない場合は、ステップＳ２１１において、データ・ブロックがアクセスをされたことから、削除保留リストの先頭に該当のエントリを移す。
【０１３１】
さらに、ステップＳ２１２で、読み出しデータを要求端末に送信し、指定サイズデータの送信の完了を確認（Ｓ２１３）し、未終了である場合は、ステップＳ２１４において、ブロックオフセット番号：Ｃの更新処理（Ｃ＝Ｃ＋１）を実行して、ステップＳ２０５以下の処理を繰り返し実行して端末に対するコンテンツ送信を実行する。
【０１３２】
ステップＳ２０５において、キャッシュグループを構成するキャッシュ装置数：Ｎ、キャッシュグループにおける自己に設定されたグループ・メンバー番号：ｍ１の各値に基づく、Ｃ　ｍｏｄ　Ｎ算出、Ｖ＝ｍ１であるか否かの判定において、Ｖ＝ｍ１でない場合は、要求されたコンテンツが自装置内に格納されていないことになり、ステップＳ２１５に進み、算出したＶの値（ｍ２とする）に対応するグループ・メンバーをキャッシュグループ・テーブル（図８参照）から取得する。
【０１３３】
ステップＳ２１６において、算出したＶの値（ｍ２とする）に対応するグループ・メンバーのＩＰアドレスをキャッシュグループ・テーブル（図８参照）から取得する。ステップＳ２１７では、取得ＩＰアドレスが０．０．０．０か否かを判定する。ＩＰアドレスが０．０．０．０の場合は、キャッシュグループを離脱したメンバーのエントリを示す。この場合は、上流のキャッシュ装置またはコンテンツサーバーに要求をリダイレクトして発行（Ｓ２２１）する。
【０１３４】
ステップＳ２１７の判定において、取得ＩＰアドレスが０．０．０．０でない場合は、キャッシュグループのメンバーのエントリを示す。ステップＳ２１８に進み、コンテンツの読み出し要求（リダイレクト要求）をキャッシュグループのメンバー（ｍ２）に対応するＩＰアドレスに基づいて実行する。
【０１３５】
リダイレクト要求を受信したキャッシュ装置における処理について、図１６を参照して説明する。これは、キャッシュグループを構成するキャッシュ装置が、他のグループ・メンバーからのコンテンツ読み出し要求（リダイレクト要求）に応答する処理として実行される処理である。
【０１３６】
ステップＳ３０１において、コンテンツ読み出し要求（リダイレクト要求）を受信すると、ステップＳ３０２に進み、ＬＲＵリストまたは削除保留リストのエントリに基づいて要求コンテンツ名、ブロックオフセット番号から自装置内のデータ格納領域情報を取得し、ステップＳ３０３において、データの有無、エラー状態を判定し、消去されているかエラーである場合は、ステップＳ３０６において、コンテンツ読み出し要求（リダイレクト要求）を送信してきたキャッシュ装置に対してエラー提示コードを応答送信する。
【０１３７】
ステップＳ３０３において、データの有無、エラー状態を判定し、データが存在し、読み出し可能であると判定されると、ステップＳ３０４において、指定サイズのデータの読み出しを実行し、ステップＳ３０５で、読み出しデータを要求キャッシュ装置に、正常終了提示コードとともに送信する。
【０１３８】
図１５の処理フローに戻り、説明を続ける。ステップＳ２１９またはステップＳ２２２において、リダイレクト要求先からの応答を受信すると、ステップＳ２２０またはステップＳ２２３において、正常読み出しがなされたか否かを判定し、Ｙｅｓの場合は、ステップＳ２０９に進み、以下の処理、すなわち、リストエントリの移動、取得コンテンツの端末に対する送信等を実行する。なお、ステップＳ２０８、Ｓ２２０，Ｓ２２３において、データの正常読み出しに失敗した場合は、異常終了として処理を終了する。
【０１３９】
なお、異常終了として処理を終了する以前に、エラー応答受信後、リダイレクト先として上流のキャッシュ装置（サーバーへの経路途中にある、サーバーにより近いキャッシュ装置）がある場合は、上流の装置にリダイレクトし、無い場合は、直接コンテンツサーバーに要求をリダイレクトして、目的とするデータを得る処理を実行してもよい。
【０１４０】
上記処理における各キャッシュ装置間のデータ通信シーケンスの概要を、図１７を参照して説明する。なお、図１７において、左端から、
コンテンツ取得要求を送信する端末、
端末からのコンテンツ取得要求を受信するキャッシュ装置Ａ
キュッシュ装置Ａとキャッシュグループを構成するキャッシュ装置１
キュッシュ装置Ａとキャッシュグループを構成するキャッシュ装置２
キュッシュ装置Ａの上流キャシュ装置またはサーバー
である。
【０１４１】
［処理Ｓ］は、端末からの要求コンテンツデータを、キャッシュ装置Ａが、キャッシュグループ・メンバーとしてのキャッシュ装置１，２からそれぞれ取得して、端末に送信する処理シーケンスであり、ＵＲＬを指定したコンテンツ取得要求（ＨＴＴＰ　ＧＥＴ　（ＵＲＬ））を受信したキャッシュ装置が上述のＣ　ｍｏｄ　Ｎ算出、Ｖ＝ｍ１の算出に基づいて、コンテンツの対応データ・ブロックを保持していると予測されるキャッシュ装置１，２に対してコンテンツ取得要求（ＨＴＴＰ　ＧＥＴ　（ＵＲＬ）　Ｒａｎｇｅ：ｂｙｔｅｓ＝ａａ−ｂｂ）を送信し、コンテンツのデータ・ブロックを取得（ＨＴＴＰ２０６）し、キャッシュ装置Ａは、取得コンテンツを端末に送信（ＨＴＴＰ　ＯＫ）する処理シーケンスである。
【０１４２】
［処理Ｔ］は、端末からの要求コンテンツデータを、キャッシュ装置Ａが、キャッシュグループ・メンバーとしてのキャッシュ装置１，２からそれぞれ取得できなかった場合の処理シーケンスであり、ＵＲＬを指定したコンテンツ取得要求（ＨＴＴＰ　ＧＥＴ　（ＵＲＬ））を受信したキャッシュ装置が上述のＣ　ｍｏｄＮ算出、Ｖ＝ｍ１の算出に基づいて、コンテンツの対応データ・ブロックを保持していると予測されるキャッシュ装置１に対してコンテンツ取得要求（ＨＴＴＰ　ＧＥＴ　（ＵＲＬ）　Ｒａｎｇｅ：ｂｙｔｅｓ＝ａａ−ｂｂ）を送信し、コンテンツのデータ・ブロックが取得できない旨の応答（ＨＴＴＰ４０４（Ｎｏｔ　Ｆｏｕｎｄ）または、ＨＴＴＰ４１０（Ｇｏｎｅ））を受信する。
【０１４３】
さらに、キャッシュ装置Ａは、キュッシュ装置Ａの上流キャシュ装置またはサーバーに、コンテンツ取得要求（ＨＴＴＰ　ＧＥＴ　（ＵＲＬ）　Ｒａｎｇｅ：ｂｙｔｅｓ＝ａａ−ｂｂ）を送信し、コンテンツのデータ・ブロックを取得（ＨＴＴＰ２０６）し、キャッシュ装置Ａは、取得コンテンツを端末に送信（ＨＴＴＰＯＫ及び取得したコンテンツデータの送信）をする。
【０１４４】
なお、［処理Ｔ］のように、キャッシュグループの構成メンバーから予定のコンテンツが取得できなかった場合は、キャッシュグループの構成メンバーとして存続する意味がないので、グループ解消を行なう。この処理が［処理Ｕ］である。
【０１４５】
グループ解消処理は、キャッシュＡから、グループ解消通知（ＩＣＰ　ＯＰ　ＮＯＴＩＦＹ）を、グループを構成する各キャッシュ装置１，２に送信することによって行なわれる。キャッシュ装置Ａ，１，２はその後、キャッシュグループ・テーブルから対応するグループ情報を削除する。
【０１４６】
なお、上述した例では、ＨＴＴＰプロトコルを使ったリダイレクト手順を書いているが、ＦＴＰやＲＴＳＰなどの別のプロトコルであってもかまわない。また、キャッシュ装置間の通信プロトコルについても、ＩＣＰだけに限定する必要はなく、一般的に使われる装置間の通信手段を拡張することでも実現可能である。また、キャッシュ間通信プロトコルも、ＩＣＰだけには限らない。
【０１４７】
キャッシュグループを構成するグループ・メンバーｍ（ｍ＝１，２，．．．，Ｎ：　Ｎはグループ構成メンバー数）がキャッシュグループから離脱することになるケースを以下に説明する。
【０１４８】
キャッシュグループを組むと宣言したコンテンツに関連するデータ・ブロックの全体数をＡとしたときに、グループ・メンバーとして保持しておくべきデータ・ブロック（Ｖ＝ｍのデータ・ブロック）の総数Ｓは、Ａ　ｍｏｄ　Ｎが零の場合はＶ＝Ｎ，非零の場合はＶ＝（Ａ　ｍｏｄ　Ｎ）としてｍ≦ＶのときＳ＝（Ａ＋Ｎ−１）／Ｎ，ｍ＞ＶのときＳ＝Ａ／Ｎと計算される。
【０１４９】
このＳの分のデータ・ブロックを永久に保持できればよいが、記憶資源は有限であるため、キャッシュ・リプレースメントが進むとグループ・メンバーとして保持しておくべきデータ・ブロックであったとしても、削除保留リストから削除されてしまうケースもある。このようにグループ・メンバーとして保持しておくべきデータ・ブロックも削除保留リストからも削除されてしまうような場合において、グループ・メンバーとして保持すべきデータ・ブロックにもかかわらず削除してしまったデータ・ブロックの数をＤとするとき、グループ離脱に至る閾値Ｔ（％）として、グループ・メンバーとして保持すべきデータ・ブロックの残存率：（Ｓ−Ｄ）／Ｓ×１００（％）を算出し、
データ・ブロックの残存率と閾値Ｔとの関係が、
（Ｓ−Ｄ）／Ｓ×１００（％）＜Ｔ（０＜＝Ｔ＜１００）となった場合に、そのコンテンツに関しキャッシュグループを組んでいるキャッシュ・メンバーに対して、グループ離脱を宣言する構成が可能である。
【０１５０】
キャッシュグループからの離脱を検知したときは、自分のキャッシュグループ・テーブルから該当するコンテンツに対応するエントリを削除すると共に、図１７の［処理Ｕ］に示すように、これを知らせるフラグ（説明のための例として０ｘ１０００００００（ＩＣＰ＿ＦＬＡＧ＿ＧＲＯＵＰ＿ＤＥＳＥＲＴＥＤ））を立てたＩＣＰ＿ＯＰ＿ＮＯＴＩＦＹメッセージを、該当するコンテンツについてキャッシュグループを組んでいる全グループ・メンバーに送る。
【０１５１】
さらに、各キャッシュ装置にあるキャッシュグループ・テーブルから、通知されたキャッシュ装置がキャッシュグループから離脱したことがわかるように、対応する部分のＩＰアドレスを≡０．０．０．０≡のように書き換える。
【０１５２】
ただし、メンバー数などの他の情報は、離脱メンバーが無い場合とのアルゴリズムの互換を保つ目的もあり、そのままの情報として保持してもよい。もし、離脱グループ・メンバーが保持しているべきデータ・ブロックをアクセスしたい場合には、オリジナルデータを持っているサーバーまたは上流のキャッシュ装置にアクセスすることになる。
【０１５３】
キャッシュグループを構成するメンバー数が、離脱メンバーを除いた実質数で１となった場合、キャッシュグループを組めないことになるため、グループを完全に消去する意味で、残った１台のキャッシュ装置のキャッシュグループ・テーブルから該当するコンテンツに対応するエントリを削除し、削除保留リストの対応するコンテンツに属するデータ・ブロックの“Ｇｐ”の項目を初期化（ゼロクリア）する。
【０１５４】
［多段構成の削除保留リスト］
次に、キャッシュ装置においてデータ管理リストとして生成する削除保留リストを多段構成とした実施例について説明する。
【０１５５】
上述した実施例において、キャッシュ装置は、図９を参照して説明したように、ＬＲＵリストと、キャッシュの空き領域ブロックを示すフリーブロックリスト、さらに、ＬＲＵリストで削除対象ブロックとなったデータ・ブロックの内、一時的に削除保留状態に設定したデータ・ブロックを管理するリストとしての削除保留リストを有しており、各リストは、先頭エントリからシーケンシャルに並べられたエントリを有する構成であった。
【０１５６】
本実施例のキャッシュ装置は、図１８に示すように、複数の削除保留リストを有する。キャッシュ装置は、利用頻度順にエントリを並べた（ａ）ＬＲＵリスト、キャッシュグループを構成したコンテンツのデータ・ブロックに対応して設定したエントリを格納した複数の（ｂ１）（ｂ２）削除保留リスト、空きブロック領域をポインタ情報として有する（ｃ）フリーブロックリストを有する。
【０１５７】
複数の削除保留リスト（ｂ１）（ｂ２）は、コンテンツデータ・ブロックの削除保留優先度の高低に基づいて振り分けられてエントリが各リストに格納される。ここでは、２つの削除保留リスト（ｂ１）（ｂ２）のうち、（ｂ１）のリストに保存優先度の高いコンテンツに対応するエントリを格納し、（ｂ２）のリストに保存優先度の低いコンテンツに対応するエントリを格納する例を示す。本例では、２つの削除保留リストの設定例を示しているが、保存優先度順に３以上の削除保留リストを設定する構成としてもよい。
【０１５８】
なお、データ・ブロックの重要性に応じた保存優先度の判定の態様は、様々な態様が可能である。例えば、新規に届いたコンテンツに対応するデータ・ブロックほど重要とする設定、あるいは、コンテンツデータの先頭部分やシーンチェンジ部分以降の特定区間だけは重要度の高いデータ・ブロックとして設定するなどの構成がある。なお、コンテンツデータの先頭部分やシーンチェンジ部分の検出は、既存のソフトウェアによる処理が可能である。
【０１５９】
リストに対するエントリの移動について説明する。例えばキャッシュ装置において、新規データ・ブロックの書き込み要求があると、（ｃ）フリーブロックリストの先頭エントリ５０１に設定されたデータ・ブロック・ポインタに対応するデータ格納領域のデータ記憶領域に新規データ・ブロックが書き込まれ、書き込まれたデータ・ブロックに関する情報は、図１０のＬＲＵリストの先頭エントリ５０２に移される。
【０１６０】
その結果、もしＬＲＵリストの長さが許容リスト長を超えることになった場合は、ＬＲＵリストの末尾のエントリ５０３が、削除保留リスト（ｂ１）または（ｂ２）あるいは、フリーブロックリスト（ｃ）に移動することになる。削除保留リストかフリーブロックリストのどちらに移動するかの判定は、前述のＣ　ｍｏｄ　Ｎの算出、Ｖの値によるエントリに対応するコンテンツデータ・ブロックの残留、削除判定に基づくことになる。
【０１６１】
上述した判定処理の結果、エントリを削除保留リストに移動すると決定した場合は、保存の重要度に応じて、重要度の高いデータ・ブロックに対するエントリは、削除保留リスト（ｂ１）の末尾のエントリ５０４として設定し、重要度の低いデータ・ブロックに対するエントリは、削除保留リスト（ｂ２）の末尾のエントリ５０５として設定する。
【０１６２】
また、削除保留リスト（ｂ１）に新たなエントリが加わり、削除保留リスト（ｂ１）が予め定められたリスト長を超えることとなった場合は、削除保留リスト（ｂ１）の先頭のエントリ５１１が、削除保留リスト（ｂ２）の末尾のエントリ５０５として設定される。
【０１６３】
同様に、削除保留リスト（ｂ２）に新たなエントリが加わり、削除保留リスト（ｂ２）が予め定められたリスト長を超えることとなった場合は、削除保留リスト（ｂ２）の先頭のエントリ５１２が、フリーブロックリストの末尾のエントリ５２１として設定される。
【０１６４】
なお、フリーブロックリストに対応して確保すべきバッファ量が、予め定められており、これが、新規データの格納により不足することとなった場合は、ＬＲＵリストあるいは削除保留リスト（ｂ２）からのフリーブロックリストへの移動、すなわちデータ・ブロックの削除によるバッファ量確保処理が実行される。
【０１６５】
フリーブロックリストへ移動されたエントリの指定するデータ・ブロック・ポインタの指定するメモリ領域は、新たな入力データの書き込みに適用され、データ・ブロックの内容が捨てられることになる。
【０１６６】
多段構成とした場合の削除保留リストの構成について、図１９を参照して説明する。削除保留リストとは、前述したように、ＬＲＵリストで削除対象ブロックとなったデータ・ブロックの内、一時的に削除保留状態に設定したデータ・ブロックを管理するリストである。
【０１６７】
図１９は、図１８の削除保留リスト（ｂ１）または（ｂ２）のいずれかに対応する削除保留リストの構成を示している。図１９のように、キャッシュ装置の保有する削除保留リスト６３０は、削除保留状態に設定したデータ・データ・ブロックに対応付けて生成される。ここでは、（ａ）〜（ｐ）のリストデータ（エントリ）が削除保留状態に設定したデータ・データ・ブロックに対応付けられて保持されている。削除保留リストの内部構造は、図１９に示すように、データ・ブロックヘのポインタ６３１、コンテンツ識別子６３２、ブロックオフセット６３３、設定されたキャッシュグループのグループ識別子（ＧＰ）６３４、さらに、削除保留リストの重要度指数値（Ｐｒｉｏｒｉｔｙ）６３５、および削除保留リストの前リストデータ（エントリ）のポインタ６３６、削除保留リストの後続リストデータ（エントリ）のポインタ６３７を有する。多段構成の削除保留リスト６３０の格納データには、削除保留リストの重要度指数値（Ｐｒｉｏｒｉｔｙ）６３５が付加されることになる。
【０１６８】
次に、多段構成の削除保留リストを持キャッシュ装置におけるキャッシュグループの生成処理、データ管理手順について、図２０を参照して説明する。
【０１６９】
図２０において、ステップＳ５０１乃至ステップＳ５１５は、前述の図１３を参照して説明した処理フローのステップＳ１０１乃至ステップＳ１１５と同様の処理であるので、説明を省略する。
【０１７０】
図２０のステップＳ５１５において、ＬＲＵリストからの削除予定エントリについて、ブロックオフセット番号：Ｃ、キャッシュグループを構成するキャッシュ装置数：Ｎ、キャッシュグループにおける自己に設定されたグループ・メンバー番号：ｍの各値に基づいて、　Ｃ　ｍｏｄ　Ｎを算出し、さらに、　Ｃ　ｍｏｄ　Ｎ＝０の場合はＶ＝Ｎ、Ｃ　ｍｏｄ　Ｎ≠０の場合はＶ＝（Ｃ　ｍｏｄ　Ｎ）として、Ｖ＝ｍであるか否かを判定した結果、Ｖ≠ｍである場合は、ステップＳ５２３に進みそのデータ・ブロックをフリーリストで管理する。Ｖ＝ｍである場合は、そのデータ・ブロックを削除保留として、自装置で管理することになる。
【０１７１】
この場合、ステップＳ５１６において、削除保留対象データ・ブロックの保持優先度の判定を実行する。この保持優先度判定は、キャッシュ装置において予め定められた基準、例えば、前述したように、新規に届いたコンテンツに対応するデータ・ブロックを重要、あるいは、コンテンツデータの先頭部分やシーンチェンジ部分以降の特定区間を重要とした設定情報に基づいて判定する。
【０１７２】
保存優先度の高いデータ・ブロックであると判定した場合は、ステップＳ５１７に進み、保存優先度の高い削除保留リスト（図１８の（ｂ１））にエントリを移動する。保存優先度の低いデータ・ブロックであると判定した場合は、ステップＳ５２０に進み、保存優先度の低い削除保留リスト（図１８の（ｂ２））にエントリを移動する。
【０１７３】
さらに、ステップＳ５１８において、保存優先度の高い削除保留リストから保存優先度の低い削除保留リストにエントリ移動が必要であるか否かを判定し、必要があると判定されると、ステップＳ５１９において、保存優先度の高い削除保留リストから保存優先度の低い削除保留リストにエントリを移動する。
【０１７４】
ステップＳ５２１において、保存優先度の低い削除保留リストからフリーブロックリストにエントリ移動が必要であるか否かを判定し、必要があると判定されると、ステップＳ５２２において、保存優先度の低い削除保留リストからフリーブロックリストにエントリを移動する。
【０１７５】
以上の処理に従って、多段構成を持つ削除保留リストを適用したデータ管理が実行される。
【０１７６】
［キャッシュ装置の構成］
次に、上述の実施例において説明したキャッシュ装置のハード構成例について説明する。
【０１７７】
図２１に、制御手段としてＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）を備えたキャッシュ装置例を示す。なお、図２１に示す構成例は１つの例であり、キャッシュ装置は、ここに示す構成以外のハードウェアを持つことも可能である。
【０１７８】
図２１に示す構成について説明する。ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）７０１は、各種実行プログラム、ＯＳ（Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍ）を実行するプロセッサである。ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ−Ｍｅｍｏｒｙ）７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納する。ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）７０３は、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用される。また、近隣キャッシュ装置リスト、キャッシュグループ・テーブルの格納領域として使用される。
【０１７９】
ＣＰＵ７０１，ＲＯＭ７０２，ＲＡＭ７０３はＣＰＵバス７１１によってデータ転送可能に接続され、バスブリッジ７０４を介してＩ／Ｏバス７１２に接続される。Ｉ／Ｏバス７１２には、ディスクインタフェース７０５、ネットワークインタフェース７０７，７０８が接続される。
【０１８０】
ディスクインタフェース７０５は、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ　Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ　ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、磁気ディスク等のディスク７０６に対するインタフェースであり、ディスク７０６には、キャッシュデータガ格納され、ＣＰＵ７０１の制御の下に必要データが取得、格納される。
【０１８１】
ネットワークインタフェース７０７は、外部ネットワークインタフェースであり、ネットワーク接続されたサーバー、他のキャッシュ装置とのデータ送受信用のインタフェースである。ネットワークインタフェース７０８は、内部ネットワークインタフェースであり、ネットワーク接続された端末とのデータ送受信用のインタフェースである。
【０１８２】
なお、明細書中において説明した各処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが専用のハードウェアに組み込まれているコンピュータ、又は各種のプログラムをインストールすることで各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、フレキシブルディスクやＣＤ−ＲＯＭ等のプログラム読み取り可能な記録媒体にプログラムを格納して提供してもよいし、インターネットなどの通信網を介してプログラムをダウンロードしてもよい。
【０１８３】
具体的には、プログラムは記録媒体としてのハードディスクやＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ　Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ　ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１８４】
また、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１８５】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【０１８６】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０１８７】
【発明の効果】
以上、説明してきたように、本発明の構成によれば、ネットワーク接続されたキャッシュ装置におけるキャッシュ・リプレースメント処理において、削除保留ブロックに関するリストを保持して、キャッシュグループ内のキャッシュ装置ごとに各々削除保留されるデータ・ブロックが異なるようにデータ管理を行なう構成としたので、各キャッシュ装置が単独でキャッシュ・リプレースメントの管理をしている場合に比べて効率的な記憶領域の利用が図れ、また、端末からのデータ要求に応じて複数のキャッシュ装置に記憶したデータ・ブロックを集めて送信することが可能となり、ネットワークトラフィックの軽減、キャッシュ装置のヒット率の向上が実現される。
【０１８８】
さらに、本発明の多段の削除保留リストを適用したキャッシュ装置構成によれば、保持重要度の高いデータが削除されずにキャッシュに残る可能性が高くなるため、さらに、キャッシュヒット率の向上を達成することが可能となる。
【図面の簡単な説明】
【図１】従来のＬＲＵリストおよびフリーブロックリストによるキャッシュデータの管理構成について説明する図である。
【図２】本発明のキャッシュ装置が適用可能なネットワーク構成について説明する図である。
【図３】本発明のキャッシュ装置におけるデータ管理構成について説明する図である。
【図４】本発明のキャッシュ装置におけるデータ管理構成について説明する図である。
【図５】本発明のキャッシュ装置間における送受信メッセージのフォーマット例について説明する図である。
【図６】本発明のキャッシュ装置における近隣キャッシュ装置リストの構成データについて説明する図である。
【図７】本発明のキャッシュ装置間における送受信メッセージとしてのグループ設定情報メッセージのフォーマット例について説明する図である。
【図８】本発明のキャッシュ装置において格納するキャッシュグループ・テーブルのデータ例について説明する図である。
【図９】本発明のキャッシュ装置においてデータ管理に利用するリストについて説明する図である。
【図１０】本発明のキャッシュ装置においてデータ管理に利用するＬＲＵリストについて説明する図である。
【図１１】本発明のキャッシュ装置においてデータ管理に利用する削除保留リストについて説明する図である。
【図１２】本発明のキャッシュ装置においてデータ管理に利用するフリーブロックリストについて説明する図である。
【図１３】本発明のキャッシュ装置におけるグループ形成、データ管理処理について説明するフロー図である。
【図１４】本発明のキャッシュ装置におけるグループ形成、データ管理処理に際して送受信されるメッセージについて説明するシーケンス図である。
【図１５】本発明のキャッシュ装置におけるデータ取得送信処理について説明するフロー図である。
【図１６】本発明のキャッシュ装置におけるリダイレクト処理によるデータ取得送信処理について説明するフロー図である。
【図１７】本発明のキャッシュ装置におけるデータ取得送信処理に際して送受信されるメッセージについて説明するシーケンス図である。
【図１８】本発明のキャッシュ装置において多段構成の削除保留リストを持つ構成を説明する図である。
【図１９】本発明のキャッシュ装置における多段構成の削除保留リスト構成について説明する図である。
【図２０】本発明の多段構成の削除保留リストを持つキャッシュ装置におけるグループ形成、データ管理処理について説明するフロー図である。
【図２１】本発明のキャッシュ装置におけるハード構成例を示す図である。
【符号の説明】
２０１　コンテンツサーバー
２０２　ネットワーク
２１０　キャッシュグループ
２１１，２１２，２１３，２１４　キャッシュ装置
２２１，２３１，２５１　端末
３１０　ＬＲＵリスト
３２０　データ格納領域
３３０　削除保留リスト
３５０　フリーブロックリスト
６３０　削除保留リスト
７０１　ＣＰＵ
７０２　ＲＯＭ
７０３　ＲＡＭ
７０４　バスブリッジ
７０５　ディスクインタフェース
７０６　ディスク
７０７　ネットワークインタフェース
７０８　ネットワークインタフェース
７１１　ＣＰＵバス
７１２　Ｉ／Ｏバス
【図１】
2004038627.tif 000003
【図２】
2004038627.tif 000004
【図３】
2004038627.tif 000005
【図４】
2004038627.tif 000006
【図５】
2004038627.tif 000007
【図６】
2004038627.tif 000008
【図７】
2004038627.tif 000009
【図８】
2004038627.tif 000010
【図９】
2004038627.tif 000011
【図１０】
2004038627.tif 000012
【図１１】
2004038627.tif 000013
【図１２】
2004038627.tif 000014
【図１３】
2004038627.tif 000015
【図１４】
2004038627.tif 000016
【図１５】
2004038627.tif 000017
【図１６】
2004038627.tif 000018
【図１７】
2004038627.tif 000019
【図１８】
2004038627.tif 000020
【図１９】
2004038627.tif 000021
【図２０】
2004038627.tif 000022
【図２１】
2004038627.tif 000023