(57)【要約】【課題】ネットワーク全体でプロキシキャッシュの効率化を図ることは難しい。【解決手段】上位キャッシュサーバ２０のメトリックス累積部６５は、下位キャッシュサーバ２２において削除されるオブジェクトの参照回数の通知を受けて、キャッシュバッファ５２のメトリックス管理用エントリ５５の参照回数を累積加算する。評価部６６は、削除されるオブジェクトの累積参照回数にもとづいて、そのオブジェクトをキャッシュするかどうかを判断し、キャッシュ移動制御部６２はその判断結果にもとづいて、下位キャッシュサーバ２２からそのオブジェクトのデータを受信する。キャッシュ管理部６０は、受信されたオブジェクトのデータを新たなキャッシュオブジェクト５６としてキャッシュオブジェクト記憶部５８に格納し、キャッシュエントリ５４を新たに設けて管理する。【選択図】        図４
2004264956.tif 000002
【特許請求の範囲】
【請求項１】
階層的に構成されたキャッシュサーバのネットワークにおいて、下位階層の複数のキャッシュサーバにキャッシュされるオブジェクトのメトリックスを上位階層の少なくとも１つのキャッシュサーバにおいて累積評価し、下位階層のキャッシュサーバの１つにおいてキャッシュオブジェクトが削除されるとき、累積評価されたメトリックスに応じて、その削除されるキャッシュオブジェクトを下位階層のキャッシュサーバから上位階層のキャッシュサーバに転送してキャッシュするかどうかを決定することを特徴とするキャッシュ管理方法。
【請求項２】
下位階層のキャッシュサーバがキャッシュオブジェクトを削除するときに限り、上位階層のキャッシュサーバにおいてそのキャッシュオブジェクトのメトリックスが累積されることを特徴とする請求項１に記載のキャッシュ管理方法。
【請求項３】
上位階層のキャッシュサーバにおいては、累積評価されたメトリックスにもとづく置換ポリシーにしたがってキャッシュオブジェクトが管理されることを特徴とする請求項１または２に記載のキャッシュ管理方法。
【請求項４】
クライアントへ提供されるオブジェクトをキャッシュして保持するキャッシュ記憶部と、
所定のメトリックスにもとづく置換ポリシーにしたがってキャッシュオブジェクトの管理を行うキャッシュ管理部と、
前記置換ポリシーにしたがって削除されるキャッシュオブジェクトのメトリックスに限り、上位階層のキャッシュサーバに通知するメトリックス通知部と、
前記上位階層のキャッシュサーバから送信要求があった場合に、その削除されるキャッシュオブジェクトを前記上位階層のキャッシュサーバに移動させる移動制御部とを含むことを特徴とするキャッシュサーバ。
【請求項５】
クライアントへ提供されるオブジェクトをキャッシュして保持するキャッシュ記憶部と、
下位階層にある複数のキャッシュサーバから通知されるキャッシュオブジェクトのメトリックスを累積してオブジェクト毎にトータルメトリックスを算出するメトリックス累積部と、
前記トータルメトリックスにもとづく置換ポリシーにしたがって前記キャッシュ記憶部に保持されたキャッシュオブジェクトの管理を行うキャッシュ管理部と、
下位階層のキャッシュサーバから削除されるキャッシュオブジェクトの通知を受けた場合に、前記トータルメトリックスにもとづいてその削除されるキャッシュオブジェクトを保持するかどうかを決定する評価部と、
前記評価部がその削除されるキャッシュオブジェクトを保持すると決定した場合、下位階層にあるキャッシュサーバからその削除されるキャッシュオブジェクトを取得して、そのキャッシュオブジェクトを前記キャッシュ管理部に新たに管理させる移動制御部とを含むことを特徴とするキャッシュサーバ。
【請求項６】
前記メトリックス累積部は、下位階層のキャッシュサーバがそのキャッシュサーバの置換ポリシーにしたがってキャッシュオブジェクトを削除する際に、そのキャッシュオブジェクトのメトリックスの通知を受け、前記トータルメトリックスに累積することを特徴とする請求項５に記載のキャッシュサーバ。
【請求項７】
前記メトリックスは、キャッシュオブジェクトの参照回数であることを特徴とする請求項４または５に記載のキャッシュサーバ。
【請求項８】
下位階層にある複数のキャッシュサーバの各々からキャッシュオブジェクトの削除時に通知される当該キャッシュオブジェクトのメトリックスを累積してオブジェクト毎にトータルメトリックスを算出するステップと、
下位階層のキャッシュサーバから削除されるキャッシュオブジェクトの通知を受けて、前記トータルメトリックスにもとづいてその削除されるキャッシュオブジェクトを保持するかどうかを決定するステップと、
その削除されるキャッシュオブジェクトを保持すると決定した場合、下位階層にあるキャッシュサーバからその削除されるキャッシュオブジェクトを取得するステップと、
取得されたキャッシュオブジェクトを前記トータルメトリックスにもとづく置換ポリシーにしたがって管理するステップとをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はキャッシュ技術、とくにネットワークにおけるキャッシュ管理方法およびその方法を利用可能なキャッシュサーバに関する。
【０００２】
【従来の技術】
インターネットでＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）によるサービスを提供する際、サーバやルータの処理能力、通信回線の帯域幅などに制限があるため、プロキシキャッシュサーバをネットワーク上に設け、クライアントのＷｅｂオブジェクトに対するアクセス要求を代理するとともに、アクセスされたオブジェクトを一時的に保持して、処理性能を確保することが一般的に行われている。クライアントがサーバにアクセスしてオブジェクトを取得したとき、プロキシキャッシュサーバにそのオブジェクトのキャッシュデータが保持される。プロキシキャッシュサーバは、クライアントから再度同じオブジェクトに対する要求があったとき、サーバにアクセス要求を送る代わりに、そのキャッシュデータをクライアントに送信する。これによりサーバやルータにかかる負荷を軽減し、ネットワークトラフィックを削減して、ネットワークリソースの利用効率を向上させるとともに、サービスの応答時間の改善を図ることができる。
【０００３】
プロキシキャッシュの利用効率を高めるためには、オブジェクトをキャッシュするために十分な記憶容量をもった大規模記録装置が必要になる。ブロードバンドのネットワークが普及するにつれて、映像や音楽など容量の大きいコンテンツの利用が盛んになるため、プロキシサーバにおいて記録装置を増設するだけでは対応しきれず、プロキシキャッシュの効率的な運用がより一層求められる。
【０００４】
プロキシキャッシュの性能は、キャッシュのエントリの置換ポリシーに大きく左右される。新たなオブジェクトをキャッシュするためのメモリスペースを確保するためには、既にキャッシュされているオブジェクトを削除しなければならない。キャッシュオブジェクトのメトリックスを何らかの方法で評価して、どのキャッシュオブジェクトを削除するのが効率的であるかを決めるのが置換ポリシーである。プロキシキャッシュの効率化のために、最終アクセス時刻、アクセス頻度、オブジェクトサイズなどのメトリックスを用いた、さまざまな置換ポリシーが検討されている（たとえば、非特許文献１参照）。
【０００５】
【非特許文献１】
Ｇ．  Ｂａｒｉｓｈ  ａｎｄ  Ｋ．  Ｏｂｒａｃｚｋａ，  ”Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ  ｃａｃｈｉｎｇ：  Ｔｒｅｎｄｓ  ａｎｄ  ｔｅｃｈｎｉｑｕｅｓ，”  ＩＥＥＥ  Ｃｏｍｍｕｎ．  Ｍａｇ．，  ｖｏｌ．３８，  ｎｏ．５，  ｐｐ．１７８−１８４，  Ｍａｙ  ２０００．
【０００６】
【発明が解決しようとする課題】
これまで提案されているプロキシキャッシュの置換ポリシーは、１つのプロキシキャッシュサーバ内のローカルなプロキシキャッシュに対して作用するものであり、プロキシキャッシュサーバが自分のキャッシュオブジェクトにはもはや利用価値がないと判断した時点で、そのキャッシュオブジェクトは直ちにキャッシュメモリから削除される。しかしながら、キャッシュオブジェクトの利用価値は、本来はネットワーク全体において評価すべきものである。オブジェクトのアクセス時間を短縮し、ネットワークトラフィックを削減するためには、オブジェクトのキャッシュをネットワーク上に適切に分散させる必要があり、個々のプロキシキャッシュサーバ内のローカルな置換ポリシーだけに頼っていては、プロキシキャッシュの性能を十分に引き出すことはできない。
【０００７】
本発明はこうした状況に鑑みてなされたものであり、その目的は、キャッシュオブジェクトの利用効率を向上することのできるキャッシュ管理方法、およびその方法を利用可能なキャッシュサーバを提供することにある。
【０００８】
【課題を解決するための手段】
本発明のある態様はキャッシュ管理方法に関する。この方法は、階層的に構成されたキャッシュサーバのネットワークにおいて、下位階層の複数のキャッシュサーバにキャッシュされるオブジェクトのメトリックスを上位階層の少なくとも１つのキャッシュサーバにおいて累積評価し、下位階層のキャッシュサーバの１つにおいてキャッシュオブジェクトが削除されるとき、累積評価されたメトリックスに応じて、その削除されるキャッシュオブジェクトを下位階層のキャッシュサーバから上位階層のキャッシュサーバに転送してキャッシュするかどうかを決定する。ここで、サーバからクライアントに提供されるオブジェクトのネットワーク経路上で、クライアント側を下位、サーバ側を上位とし、ネットワーク経路上のキャッシュサーバの相対的な位置関係により、キャッシュサーバの階層の上下関係を定めることができる。
【０００９】
下位階層のキャッシュサーバがキャッシュオブジェクトを削除するときに限り、上位階層のキャッシュサーバにおいてそのキャッシュオブジェクトのメトリックスが累積されるようにしてもよい。これにより、下位階層のキャッシュサーバでオブジェクトが削除される前にメトリックスを上位階層のキャッシュサーバで累積することができる。また、メトリックスの累積を下位階層のキャッシュサーバで削除されるキャッシュに限ったことにより、下位階層のキャッシュサーバでキャッシュされている多数のオブジェクトについてメトリックスを累積することを避け、キャッシュサーバ間の通信量を最小限に抑えることができる。また、下位階層のキャッシュサーバでキャッシュオブジェクトが削除されるタイミングに限ってメトリックスを累積するため、メトリックスの累積漏れが起きたり、重複加算が起きるのを防ぐことができる。
【００１０】
上位階層のキャッシュサーバにおいては、累積評価されたメトリックスにもとづく置換ポリシーにしたがってキャッシュオブジェクトが管理されてもよい。累積されたメトリックスを用いることにより、上位階層のキャッシュサーバを経由してオブジェクトが提供される複数のクライアント全体で、オブジェクトに対するアクセス状況を考慮し、キャッシュの置換ポリシーを実現することができる。
【００１１】
本発明の別の態様はキャッシュサーバに関する。このキャッシュサーバは、階層的に構成されたキャッシュサーバのネットワークにおいて、相対的に見て下位階層にあるキャッシュサーバであり、クライアントへ提供されるオブジェクトをキャッシュして保持するキャッシュ記憶部と、所定のメトリックスにもとづく置換ポリシーにしたがってキャッシュオブジェクトの管理を行うキャッシュ管理部と、前記置換ポリシーにしたがって削除されるキャッシュオブジェクトのメトリックスに限り、上位階層のキャッシュサーバに通知するメトリックス通知部と、前記上位階層のキャッシュサーバから送信要求があった場合に、その削除されるキャッシュオブジェクトを前記上位階層のキャッシュサーバに移動させる移動制御部とを含む。
【００１２】
本発明のさらに別の態様もキャッシュサーバに関する。このキャッシュサーバは、階層的に構成されたキャッシュサーバのネットワークにおいて、相対的に見て上位階層にあるキャッシュサーバであり、クライアントへ提供されるオブジェクトをキャッシュして保持するキャッシュ記憶部と、下位階層にある複数のキャッシュサーバから通知されるキャッシュオブジェクトのメトリックスを累積してオブジェクト毎にトータルメトリックスを算出するメトリックス累積部と、前記トータルメトリックスにもとづく置換ポリシーにしたがって前記キャッシュ記憶部に保持されたキャッシュオブジェクトの管理を行うキャッシュ管理部と、下位階層のキャッシュサーバから削除されるキャッシュオブジェクトの通知を受けた場合に、前記トータルメトリックスにもとづいてその削除されるキャッシュオブジェクトを保持するかどうかを決定する評価部と、前記評価部がその削除されるキャッシュオブジェクトを保持すると決定した場合、下位階層にあるキャッシュサーバからその削除されるキャッシュオブジェクトを取得して、そのキャッシュオブジェクトを前記キャッシュ管理部に新たに管理させる移動制御部とを含む。
【００１３】
前記メトリックス累積部は、下位階層のキャッシュサーバがそのキャッシュサーバの置換ポリシーにしたがってキャッシュオブジェクトを削除する際に、そのキャッシュオブジェクトのメトリックスの通知を受け、前記トータルメトリックスに累積してもよい。
【００１４】
本発明のさらに別の態様はコンピュータプログラムに関する。このプログラムは、下位階層にある複数のキャッシュサーバの各々からキャッシュオブジェクトの削除時に通知される当該キャッシュオブジェクトのメトリックスを累積してオブジェクト毎にトータルメトリックスを算出するステップと、下位階層のキャッシュサーバから削除されるキャッシュオブジェクトの通知を受けて、前記トータルメトリックスにもとづいてその削除されるキャッシュオブジェクトを保持するかどうかを決定するステップと、その削除されるキャッシュオブジェクトを保持すると決定した場合、下位階層にあるキャッシュサーバからその削除されるキャッシュオブジェクトを取得するステップと、取得されたキャッシュオブジェクトを前記トータルメトリックスにもとづく置換ポリシーにしたがって管理するステップとをコンピュータに実行させる。
【００１５】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【００１６】
【発明の実施の形態】
図１は、実施の形態に係るキャッシュサーバを含むネットワーク全体の構成図である。クライアント１０ａ〜１０ｃ（以下、これらを総称するときはクライアント１０と呼ぶ）は、インターネット経由で、サーバ１４ａ、１４ｂ（以下、これらを総称するときはサーバ１４と呼ぶ）が提供するＷｅｂページや画像、オーディオなどのオブジェクトにアクセスする。
【００１７】
インターネットに配置された複数のキャッシュサーバ１２ａ〜１２ｅは、クライアント１０からサーバ１４へのオブジェクトのアクセス要求を代理するプロキシサーバとしての機能をもち、サーバ１４から取得したオブジェクトのデータを中継してクライアント１０へ提供するとともに、そのオブジェクトのデータを将来の使用に備えて一時的にキャッシュする。
【００１８】
これらのキャッシュサーバ１２ａ〜１２ｅは、サーバ１４ａ、１４ｂからクライアント１０ａ〜１０ｃに至るネットワークの経路上で階層構造を成し、クライアント１０ａ〜１０ｃがアクセスしたオブジェクト＃１〜＃４のデータをキャッシュする。たとえば、クライアント１０ａがサーバ１４ａにオブジェクト＃２のアクセス要求を送ると、まずクライアント１０ａに最も近い位置にあるキャッシュサーバ１２ｂがオブジェクト＃２のアクセス要求を代理し、そのキャッシュサーバ１２ｂから見て上位にあるキャッシュサーバ１２ａに対してオブジェクト＃２を要求する。すなわち、ここで下位のキャッシュサーバ１２ｂと上位のキャッシュサーバ１２ａは、クライアントとサーバの関係に立つ。
【００１９】
さらに、上位のキャッシュサーバ１２ａは、オブジェクト＃２のキャッシュがあれば、そのキャッシュデータを下位のキャッシュサーバ１２ｂに返信するが、そうでなければ、上位のキャッシュサーバ１２ａは、自身がクライアントとしてサーバ１４ａにオブジェクト＃２のアクセス要求を送ることになる。上位のキャッシュサーバ１２ａはサーバ１４ａからオブジェクト＃２のデータを受信し、キャッシュオブジェクト１６ａとしてキャッシュするとともに、下位のキャッシュサーバ１２ｂにそのデータを返信する。
【００２０】
下位のキャッシュサーバ１２ｂは、上位のキャッシュサーバ１２ａからオブジェクト＃２のデータを受信して、キャッシュオブジェクト１６ｂとしてキャッシュするとともに、そのデータをクライアント１０ａに返信する。
【００２１】
その後、別のクライアント１０ｃがサーバ１４ａに同じオブジェクト＃２のアクセス要求を送ると、このクライアント１０ｃに最も近い位置にある第１階層のキャッシュサーバ１２ｅがオブジェクト＃２のアクセス要求を代理し、１つ上の階層のキャッシュサーバ１２ｃに対してオブジェクト＃２を要求する。この第２階層のキャッシュサーバ１２ｃは、オブジェクト＃２のキャッシュがなければ、さらに１つ上の階層のキャッシュサーバ１２ａに対してオブジェクト＃２のアクセス要求を送る。この第３階層のキャッシュサーバ１２ａには、既にオブジェクト＃２のキャッシュオブジェクト１６ａがあるため、第２階層のキャッシュサーバ１２ｃにそのデータを返信する。第２階層のキャッシュサーバ１２ｃは、オブジェクト＃２のデータをキャッシュオブジェクト１６ｃとしてキャッシュするとともに、第１階層のキャッシュサーバ１２ｅにそのデータを返信する。第１階層のキャッシュサーバ１２ｅは、受信したオブジェクト＃２のデータをキャッシュオブジェクト１６ｅとしてキャッシュするとともに、そのデータをクライアント１０ｃに返信する。
【００２２】
このようにして第１階層のキャッシュサーバ１２ｅにキャッシュされたキャッシュオブジェクト１６ｅは、そのキャッシュサーバ１２ｅ内のキャッシュの置換ポリシーにしたがって管理され、他のオブジェクトを新しくキャッシュする際に置き換えられて削除されることがある。キャッシュサーバ１２ａ〜１２ｅはそれぞれ、これから述べるメトリックスにもとづく置換ポリシーにしたがって、キャッシュオブジェクトを管理する。
【００２３】
図２は、実施の形態に係るキャッシュサーバによるキャッシュオブジェクトのメトリックスの評価方法を説明する図である。同図の例では、クライアント１０ａ〜１０ｃのサーバ１４ａ、１４ｂに対するオブジェクトのアクセス要求は、それぞれ下位キャッシュサーバ２２ａ〜２２ｃにより代理され、さらに下位キャッシュサーバ２２ａ〜２２ｃから上位キャッシュサーバ２０にオブジェクトのアクセス要求がなされる。上位キャッシュサーバ２０はサーバ１４ａ、１４ｂからオブジェクトを受信してキャッシュするとともに、下位キャッシュサーバ２２ａ〜２２ｃに対してはサーバとして動作して、オブジェクトを下位キャッシュサーバ２２ａ〜２２ｃへ返信する。同図において、オブジェクト＃１〜＃４のキャッシュの右肩に付された数字は、各キャッシュオブジェクトのキャッシュサーバ２０、２２ａ〜２２ｃ内でのローカルな参照回数を示しており、キャッシュサーバ２０、２２ａ〜２２ｃはそれぞれ、この参照回数をメトリックスとして用いた置換ポリシーによりキャッシュオブジェクトを管理する。
【００２４】
２つの下位キャッシュサーバ２２ａ、２２ｂがそれぞれオブジェクト＃２のキャッシュオブジェクト１８ａ、１８ｂを格納しているが、オブジェクト＃２のキャッシュオブジェクト１８ａ、１８ｂの参照回数はいずれも４回であり、他のキャッシュオブジェクトの参照回数よりも少ない。しかし、ネットワーク全体で見た場合、オブジェクト＃２のキャッシュの参照回数は合計で８回であり、他のキャッシュオブジェクトの参照回数よりも多い。
【００２５】
ここで、２つの下位キャッシュサーバ２２ａ、２２ｂはそれぞれ、新たなオブジェクトをキャッシュするスペースを確保するために、参照回数の少ないキャッシュオブジェクト１８ａ、１８ｂを削除すると仮定する。上位キャッシュサーバ２０は、２つの下位キャッシュサーバ２２ａ、２２ｂのそれぞれからオブジェクト＃２のキャッシュオブジェクト１８ａ、１８ｂの参照回数の通知を受けて参照回数を累積し、合計で８回の参照回数であることをオブジェクト＃２のトータルメトリックスとして記憶する。
【００２６】
上位キャッシュサーバ２０は、オブジェクト＃２のキャッシュオブジェクト１９をこのトータルメトリックスにもとづいた置換ポリシーにしたがって管理するため、下位キャッシュサーバ２２ａ、２２ｂにおいてオブジェクト＃２のキャッシュオブジェクト１８ａ、１８ｂがローカルなメトリックスの評価によって削除されても、上位キャッシュサーバ２０において、オブジェクト＃２のキャッシュオブジェクト１９が保持される。もっとも、上位キャッシュサーバ２０において、他に参照回数の多いオブジェクトがあれば、オブジェクト＃２のキャッシュオブジェクト１９もやがては削除されることがある。このようにして、オブジェクト＃２のキャッシュの削除は下位階層から上位階層のキャッシュサーバに向けて徐々に行われることになり、ちょうどオブジェクト＃２のキャッシュの生成が上位階層から下位階層のキャッシュサーバに伝搬するのと対照を成す。
【００２７】
同様に、別のクライアント１０ｃを代理する下位キャッシュサーバ２２ｃにおいて、オブジェクト＃３のキャッシュオブジェクト１７ｃが置換ポリシーにしたがって削除されるときは、このキャッシュオブジェクト１７ｃの参照回数６回と、もう一つのクライアント１０ａを代理する下位キャッシュサーバ２２ａに格納されているオブジェクト＃３のキャッシュオブジェクト１７ａの参照回数５回とが、上位キャッシュサーバ２０において累積され、トータルメトリックスとして１１回の参照回数をもつものとして、上位キャッシュサーバ２０において管理される。
【００２８】
図３は、下位キャッシュサーバ２２の構成図であり、図４は、上位キャッシュサーバ２０の構成図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされたキャッシュ管理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２９】
図３を参照して、下位キャッシュサーバ２２の構成を説明する。下位キャッシュサーバ２２には、キャッシュバッファ３２が設けられ、キャッシュされるオブジェクトのエントリ３４（以下、単にキャッシュエントリ３４と呼ぶ）がリスト構造などで格納される。キャッシュエントリ３４にはオブジェクトのキャッシュデータ３６（以下、単にキャッシュオブジェクト３６と呼ぶ）へのポインタが含まれ、キャッシュオブジェクト３６そのものは大容量記憶装置であるキャッシュオブジェクト記憶部３８に記憶される。
【００３０】
キャッシュエントリ３４のデータ構造を図５に示す。キャッシュエントリ３４には、オブジェクトのサーバ１４における格納場所を示すＵＲＬ７０、下位キャッシュサーバ２２内での当該キャッシュの参照回数７２、キャッシュの最終アクセス時刻７４、キャッシュのアクセス頻度７６、キャッシュオブジェクトのサイズ７８、およびキャッシュオブジェクトへのポインタ８０が格納される。
【００３１】
図３に戻り、検索部３０は、クライアント１０から要求のあったオブジェクトについて、キャッシュバッファ３２のキャッシュエントリ３４のリスト構造を検索して、そのオブジェクトがキャッシュされているかどうかを調べる。オブジェクトの検索キーとして図５のＵＲＬ７０が用いられる。キャッシュにヒットした場合、検索部３０はヒットしたキャッシュエントリ３４のポインタ８０が指すキャッシュオブジェクト３６をキャッシュオブジェクト記憶部３８から取り出し、クライアント１０へ送信する。
【００３２】
キャッシュ管理部４０は、キャッシュバッファ３２に格納されたキャッシュエントリ３４毎に付与されたメトリックスを参照して、メトリックスにもとづいた置換ポリシーにしたがって、キャッシュバッファ３２に格納されたキャッシュエントリ３４の管理を行う。たとえば、メトリックスとして図５の参照回数７２を用い、参照回数７２の最も少ないキャッシュエントリ３４から先に追い出すＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）方式を置換ポリシーとして利用する。
【００３３】
キャッシュ管理部４０は、新たなオブジェクトをキャッシュするためのスペースがキャッシュオブジェクト記憶部３８に必要になったとき、メトリックスが最も小さいキャッシュエントリ３４を選んで、キャッシュオブジェクト記憶部３８から削除するキャッシュオブジェクト３６を決定する。キャッシュ管理部４０は、その削除するキャッシュオブジェクト３６のメトリックスをキャッシュバッファ３２から読み出して、メトリックス通知部４４に与える。
【００３４】
メトリックス通知部４４は、削除対象のキャッシュオブジェクト３６のメトリックスを上位キャッシュサーバ２０に通知する。キャッシュ移動制御部４２は、上位キャッシュサーバ２０から削除対象のキャッシュオブジェクト３６の送信要求を受けた場合に限り、キャッシュオブジェクト記憶部３８からそのキャッシュオブジェクト３６を読み出して、上位キャッシュサーバ２０へ転送する。
【００３５】
キャッシュ管理部４０は、キャッシュ移動制御部４２による削除対象のキャッシュオブジェクト３６の転送制御が終わったことを受け、キャッシュバッファ３２からそのキャッシュオブジェクト３６のキャッシュエントリ３４を削除するとともに、キャッシュオブジェクト３６をキャッシュオブジェクト記憶部３８から削除する。
【００３６】
図４を参照して、上位キャッシュサーバ２０の構成を説明する。検索部５０、キャッシュ管理部６０、キャッシュオブジェクト記憶部５８は、図３の下位キャッシュサーバ２２の検索部３０、キャッシュ管理部４０、キャッシュオブジェクト記憶部３８と同じ構成であるが、キャッシュバッファ５２に格納されるエントリに違いがある。
【００３７】
キャッシュバッファ５２には、キャッシュオブジェクト記憶部５８のキャッシュオブジェクト５６に対応して設けられたキャッシュエントリ５４以外に、メトリックス管理用エントリ５５がある。メトリックス管理用エントリ５５は、下位キャッシュサーバ２２がキャッシュするオブジェクトのメトリックスの累積計算のために利用されるものであり、キャッシュオブジェクト記憶部５８にはこれに対応するオブジェクトのキャッシュデータは格納されていない。
【００３８】
キャッシュエントリ５４は、図５で説明した下位キャッシュサーバ２２のキャッシュエントリ３４と同じデータ構造をもつが、参照回数７２には下位キャッシュサーバ２２から通知されるキャッシュオブジェクトの参照回数が累積加算され、トータルメトリックスとして利用される点が異なる。
【００３９】
メトリックス管理用エントリ５５のデータ構造を図６に示す。メトリックス管理用エントリ５５には、オブジェクトのＵＲＬ８２、累積参照回数８４、オブジェクトサイズ８６が格納される。このメトリックス管理用エントリ５５のＵＲＬ８２で特定されるオブジェクトが上位キャッシュサーバ２０においてもキャッシュされることとなった場合には、メトリックス管理用エントリ５５は図５で説明したキャッシュエントリ３４に置き換えられ、引き続いてキャッシュバッファ５２内でキャッシュエントリ３４として置換ポリシーにしたがった管理を受けることになる。
【００４０】
したがって、下位キャッシュサーバ２２においてキャッシュされているオブジェクトは、上位キャッシュサーバ２０のキャッシュバッファ５２内で、キャッシュエントリ５４として管理されているか、メトリックス管理用エントリ５５として管理されているか、あるいは、どちらにも該当しないかのいずれかである。また、キャッシュエントリ５４として管理された場合には、キャッシュオブジェクト記憶部５８にキャッシュオブジェクト５６がキャッシュされるが、メトリックス管理用エントリ５５として管理されている間は、キャッシュオブジェクト記憶部５８には対応するキャッシュデータが存在しない。
【００４１】
再び図４を参照し、検索部５０が下位キャッシュサーバ２２から要求されるオブジェクトを検索するときは、キャッシュバッファ５２内のキャッシュエントリ５４のみを検索して、ヒットした場合は、キャッシュオブジェクト記憶部５８から対応するキャッシュオブジェクト５６を取り出して下位キャッシュサーバ２２へ送信する。また、キャッシュ管理部６０は、キャッシュバッファ５２内のキャッシュエントリ５４のみをトータルメトリックスにもとづく置換ポリシーにしたがって管理する。
【００４２】
メトリックス累積部６５は、削除対象のオブジェクトのメトリックスの通知を下位キャッシュサーバ２２から受けると、そのオブジェクトがキャッシュされている場合は、キャッシュエントリ５４の参照回数７２に通知されたメトリックスを累積加算する。そのオブジェクトがキャッシュされていない場合は、メトリックス管理用エントリ５５の累積参照回数８４に通知されたメトリックスを累積加算する。
【００４３】
評価部６６は、下位キャッシュサーバ２２から削除対象のオブジェクトの通知を受けて、そのオブジェクトのＵＲＬを検索キーにして、キャッシュバッファ５２内のキャッシュエントリ５４またはメトリックス管理用エントリ５５を検索し、そのオブジェクトの累積参照回数を取得する。削除対象のオブジェクトがメトリックス管理用エントリ５５として存在する場合は、上位キャッシュサーバ２０にはそのオブジェクトのデータがキャッシュされていないため、その削除対象のオブジェクトの累積参照回数にもとづいて、新たなキャッシュエントリ５４としてキャッシュするかどうかを判断する。たとえば、他のキャッシュエントリ５４の参照回数よりも大きい累積参照回数をもつならば、その削除対象のオブジェクトを受理し、そうでないなら、受理しない。また、キャッシュオブジェクト記憶部５８に十分な空き容量がある場合は、累積参照回数を評価することなく、削除対象のオブジェクトを受理する。
【００４４】
評価部６６は判断結果をキャッシュ移動制御部６２に通知し、キャッシュ移動制御部６２は削除対象のオブジェクトを受理する場合には、下位キャッシュサーバ２２にそのオブジェクトの送信要求を送り、下位キャッシュサーバ２２からオブジェクトのデータを受信する。
【００４５】
キャッシュ移動制御部６２により受信されたオブジェクトのデータは、新たなキャッシュオブジェクト５６としてキャッシュオブジェクト記憶部５８に格納され、キャッシュ管理部６０はこのキャッシュオブジェクト５６に対するメトリックス管理用エントリ５５をキャッシュエントリ５４に置き換えてキャッシュバッファ５２内で、置換ポリシーにしたがって管理する。
【００４６】
図７から図９は、以上の構成の下位キャッシュサーバ２２および上位キャッシュサーバ２０によるキャッシュ管理手順を説明するフローチャートである。
【００４７】
図７において、下位キャッシュサーバ２２のキャッシュ管理部４０が、置換ポリシーにもとづいて削除されるキャッシュオブジェクト３６を決定する（Ｓ１０）。キャッシュ管理部４０は削除されるキャッシュオブジェクトを一時的にロックする（Ｓ１２）。メトリックス通知部４４は、削除されるキャッシュオブジェクト３６に対応するキャッシュエントリ３４のＵＲＬ７０とローカルなメトリックスである参照回数７２を上位キャッシュサーバ２０へ通知する（Ｓ１４）。この通知には、階層的に構成されたキャッシュサーバ間の通信に利用されるＩＣＰ（Ｉｎｔｅｒｎｅｔ  Ｃａｃｈｅ  Ｐｒｏｔｏｃｏｌ）を用い、下位キャッシュサーバ２２は、標準的なＩＣＰ＿ＱＵＥＲＹを拡張したＩＣＰ＿ＭＯＶＥ＿ＱＵＥＲＹメッセージにＵＲＬ７０と参照回数７２の情報を格納して上位キャッシュサーバ２０へ送信する（Ｓ１６）。
【００４８】
上位キャッシュサーバ２０のメトリックス累積部６５は、ＩＣＰ＿ＭＯＶＥ＿ＱＵＥＲＹメッセージを受信すると、ＩＣＰ＿ＭＯＶＥ＿ＱＵＥＲＹメッセージに含まれるＵＲＬ７０にもとづいてキャッシュバッファ５２内のキャッシュエントリ５４またはメトリックス管理用エントリ５５を検索し、キャッシュエントリ５４の参照回数７２またはメトリックス管理用エントリ５５の累積参照回数８４に下位キャッシュサーバ２２から通知されたローカルメトリックスである参照回数７２を累積加算する（Ｓ１８）。キャッシュバッファ５２に該当するエントリがない場合は、下位キャッシュサーバ２２から通知されたＵＲＬ７０と参照回数７２にもとづいて新たにメトリックス管理用エントリ５５が作成される。
【００４９】
評価部６６は、下位キャッシュサーバ２２から通知された削除対象のオブジェクトがキャッシュされていない場合、すなわちキャッシュバッファ５２内には削除対象のオブジェクトのエントリがメトリックス管理用エントリ５５として格納されているだけである場合、そのメトリックス管理用エントリ５５の累積参照回数８４にもとづいて、削除対象のオブジェクトを受理して新たにキャッシュするかどうかを判断する（Ｓ２０）。オブジェクトを受理する場合（Ｓ２０のＹ）の処理の流れを図８に示し、オブジェクトを受理しない場合（Ｓ２０のＮ）の処理の流れを図９に示す。
【００５０】
図８を参照して、下位キャッシュサーバ２２において削除されるオブジェクトを上位キャッシュサーバ２０が受理する場合の処理を説明する。上位キャッシュサーバ２０のキャッシュ移動制御部６２は、下位キャッシュサーバ２２に対して削除対象のオブジェクトの送信要求を行う（Ｓ２２）。この送信要求は、下位キャッシュサーバ２２から通知された削除対象のオブジェクトのＵＲＬ７０を用いたＨＴＴＰ（Ｈｙｐｅｒｔｅｘｔ  Ｔｒａｎｓｐｏｒｔ  Ｐｒｏｔｏｃｏｌ）リクエストによって行われる（Ｓ２４）。下位キャッシュサーバ２２のキャッシュ移動制御部４２は、削除されるキャッシュオブジェクト３６を上位キャッシュサーバ２０へ転送する（Ｓ２６）。この転送は、ＨＴＴＰリプライによって行われる（Ｓ２８）。下位キャッシュサーバ２２のキャッシュ管理部４０は、削除対象のキャッシュオブジェクト３６のロックを解除して、キャッシュオブジェクト記憶部３８からそのデータを削除し、対応するキャッシュエントリ３４をキャッシュバッファ３２から削除する（Ｓ３４）。
【００５１】
上位キャッシュサーバ２０のキャッシュ移動制御部６２は、ＨＴＴＰリプライにより転送されたオブジェクトのデータを受信する（Ｓ３０）。キャッシュ移動制御部６２は、受信したオブジェクトのデータを新たなキャッシュオブジェクト５６としてキャッシュオブジェクト記憶部５８に格納し、キャッシュ管理部６０は、そのオブジェクトに対応するメトリックス管理用エントリ５５を新たなキャッシュエントリ５４に変更してキャッシュバッファ５２内で管理する（Ｓ３２）。
【００５２】
図９を参照して、下位キャッシュサーバ２２において削除されるオブジェクトを上位キャッシュサーバ２０が受理しない場合の処理を説明する。上位キャッシュサーバ２０のキャッシュ移動制御部６２は、下位キャッシュサーバ２２へＩＣＰ＿ＭＯＶＥ＿ＮＧメッセージを送信して削除対象のオブジェクトを受理できないことを伝える（Ｓ３６）。下位キャッシュサーバ２２のキャッシュ管理部４０は、削除対象のキャッシュオブジェクト３６のロックを解除して、キャッシュオブジェクト記憶部３８からそのデータを削除し、対応するキャッシュエントリ３４をキャッシュバッファ３２から削除する（Ｓ３８）。
【００５３】
以上述べたように、本発明の実施の形態によれば、下位のプロキシキャッシュがローカルに評価するキャッシュのメトリックスを上位のプロキシキャッシュが統合して再評価するため、ネットワーク全体でキャッシュの利用頻度を考慮したキャッシュの置換ポリシーを実現することができる。それによって、キャッシュのヒット率を高め、またオブジェクトのアクセス時のレスポンス時間を改善することができる。
【００５４】
また、実施の形態によれば、比較的限定された地域のクライアントからの利用頻度が高いオブジェクトのキャッシュは、その地域のクライアントに近い下位のプロキシキャッシュにもたせ、ある程度広い地域のクライアントの集合から利用されるオブジェクトのキャッシュについては、上位のプロキシキャッシュに移動してもたせることができるため、キャッシュの適正な分散配置により、ネットワーク負荷を分散することができる。
【００５５】
また、下位のプロキシキャッシュが異なる管理ドメインに属していて、それらのプロキシキャッシュ間を連携することが政策的に困難な場合でも、管理ドメインをまたがって上位のプロキシキャッシュを設けることにより、上位階層でメトリックスの統合的な再評価をすることができるようになる。
【００５６】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【００５７】
上記の説明では、キャッシュオブジェクトの利用価値を表すメトリックスとして参照回数を用い、ＬＦＵ方式を置換ポリシーとして採用したが、当然に参照回数以外の他のメトリックスを用いても本発明を実施することができる。また参照回数に他のメトリックスを組み合わせて置換ポリシーを実現してもよい。たとえば、参照回数以外に最終アクセス時刻やアクセス頻度もメトリックスとして評価して、最後に参照されてからの経過時間が最も長いキャッシュエントリを優先的に削除したり、アクセス頻度によりキャッシュの寿命を考慮するようにしてもよい。また、オブジェクトサイズをもとにキャッシュを削除するかどうかを判断してもよい。たとえばオブジェクトサイズの大きいキャッシュについては、アクセス時間がかかるため、できるだけ削除しないようにしたり、逆に記憶スペースを節約するために優先的に削除するようにしてもよい。
【００５８】
また、下位のキャッシュサーバにおいては、参照回数を計数するのみで、置換ポリシーとしては、最終アクセス時刻をメトリックスとして用いたＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）方式を採用してもよい。この場合、下位のキャッシュサーバは、ＬＲＵ方式により置き換えられるキャッシュについて計数された参照回数を上位のキャッシュサーバに通知し、上位のキャッシュサーバは、累積された参照回数にもとづいた置換ポリシーでキャッシュを管理してもよい。このように、置換ポリシーは上位、下位のキャッシュサーバにおいて異なっていてもかまわない。
【００５９】
なお、上記の説明では、上位キャッシュサーバと下位キャッシュサーバに分けて構成と動作を説明したが、上位キャッシュサーバに対してさらに上位のキャッシュサーバがある場合は、上位キャッシュサーバはそのさらに上位のキャッシュサーバに対しては下位キャッシュサーバとして動作することになる。したがって、上位キャッシュサーバに下位キャッシュサーバの構成をもたせるようにして、相対的にいずれのキャッシュサーバの機能も実行できるようにしてもよい。
【００６０】
また、階層的に構成されたプロキシキャッシュのネットワークにおいて、下位キャッシュサーバは子プロキシキャッシュに、上位キャッシュサーバは親プロキシキャッシュに相当するのが通常の構成である。しかしながら、異なる親プロキシキャッシュに属する子プロキシキャッシュを下位キャッシュサーバとして、それらを統括する上位キャッシュサーバを設けてもかまわない。このように、プロキシキャッシュのネットワークにおける親子関係には限定されずに、上位、下位のキャッシュサーバを構成してもよい。
【００６１】
【発明の効果】
本発明によれば、ネットワーク上でキャッシュを効率よく管理することができる。
【図面の簡単な説明】
【図１】実施の形態に係るキャッシュサーバを含むネットワーク全体の構成図である。
【図２】実施の形態に係るキャッシュサーバによるキャッシュオブジェクトのメトリックスの評価方法を説明する図である。
【図３】図２の下位キャッシュサーバの構成図である。
【図４】図２の上位キャッシュサーバの構成図である。
【図５】図３のキャッシュエントリのデータ構造の説明図である。
【図６】図４のメトリックス管理用エントリのデータ構造の説明図である。
【図７】図２の下位キャッシュサーバおよび上位キャッシュサーバによるキャッシュ管理手順を説明するフローチャートである。
【図８】図２の下位キャッシュサーバにおいて削除されるオブジェクトを図２の上位キャッシュサーバが受理する場合の処理を説明するフローチャートである。
【図９】図２の下位キャッシュサーバにおいて削除されるオブジェクトを図２の上位キャッシュサーバが受理しない場合の処理を説明するフローチャートである。
【符号の説明】
１０  クライアント、  １２  キャッシュサーバ、  １４  サーバ、  ２０  上位キャッシュサーバ、  ２２  下位キャッシュサーバ、  ３０、５０  検索部、  ３２、５２  キャッシュバッファ、  ３４、５４  キャッシュエントリ、  ５５  メトリックス管理用エントリ、  ３６、５６  キャッシュオブジェクト、３８、５８  キャッシュオブジェクト記憶部、  ４０、６０  キャッシュ管理部、  ４２、６２  キャッシュ移動制御部、  ４４  メトリックス通知部、  ６５  メトリックス累積部、  ６６  評価部。
【図１】
2004264956.tif 000003
【図２】
2004264956.tif 000004
【図３】
2004264956.tif 000005
【図４】
2004264956.tif 000006
【図５】
2004264956.tif 000007
【図６】
2004264956.tif 000008
【図７】
2004264956.tif 000009
【図８】
2004264956.tif 000010
【図９】
2004264956.tif 000011