(57)【特許請求の範囲】
【請求項１】
Ｎ個のアイテム（Ｉ［ｉ］）のリスト（Ｌ）を、前記リストのＣ個のアイテムのメモリキャッシュ（Ｍ）に格納することを管理するための方法であって、前記Ｎ個のアイテムが、ユーザによるそれらの最後の要求時間によって決まるランクｉに従って前記リスト中で順序付けられ、Ｃ、Ｎ、およびｉが厳密に正の整数である、方法において、アイテム（Ｉ［ｉ］）の要求を受け取ったとき、ｆが加速関数であるとすると、前記要求されたアイテムのポピュラリティ確率ｆ（ｉ）を計算することと、前記ポピュラリティ確率に従って、前記要求されたアイテムをより上位のランクｉ’に移動するかどうかを決定することとを行うことを特徴とする方法。
【請求項２】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが、０≦ｆ（ｉ）≦１のようであって、ランクｉに関して減少しており、そのポピュラリティ確率ｆ（ｉ）が決定された値よりも大きい場合、要求されたアイテム（Ｉ［ｉ］）がより上位のランクｉ’に移動されることを特徴とする、請求項１に記載の方法。
【請求項３】
要求されたアイテム（Ｉ［ｉ］）が、そのポピュラリティ確率ｆ（ｉ）が所定の値よりも大きい場合、リスト（Ｌ）の第１のランクに移動されることを特徴とする、請求項２に記載の方法。
【請求項４】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝ｅｘｐ（−λ＊（ｉ−１））のようであり、ここでλは正のパラメータであることを特徴とする、請求項２または３に記載の方法。
【請求項５】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝ｉ（−λ）のようであり、ここでλは正のパラメータであることを特徴とする、請求項２または３に記載の方法。
【請求項６】
ｉ＞Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝１のようであり、要求されたアイテム（Ｉ［ｉ］）が、リスト（Ｌ）の第１のランクに移動されることを特徴とする、請求項１から５のいずれか一項に記載の方法。
【請求項７】
Ｎ個のアイテムのリスト（Ｌ）のＣ個のアイテム（Ｉ［ｉ］）を格納するためのメモリキャッシュ（Ｍ）を備えたキャッシュシステムであって、前記キャッシュシステムが、ユーザからアイテム（Ｉ［ｉ］）の要求を受け取るための手段と、それらの最後の要求時間から決まるランクｉに従って前記リスト中でアイテム（Ｉ［ｉ］）を順序付けるための手段とを備え、Ｎ、Ｃ、およびｉが、厳密に正の整数であって、キャッシュシステムが、アイテム（Ｉ［ｉ］）の要求を受け取ったとき、ｆが加速関数であるとすると、前記アイテムのポピュラリティ確率ｆ（ｉ）を計算するための手段をさらに備え、順序付けのための手段が、前記要求されたアイテムを前記ポピュラリティ確率に従ってより上位のランクｉ’に移動するかどうかを決定するように構成された、キャッシュシステム。
【請求項８】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが０≦ｆ（ｉ）≦１であり、ランクｉに関して減少しており、順序付けのための手段が、要求されたアイテム（Ｉ［ｉ］）のポピュラリティ確率ｆ（ｉ）が所定の値よりも大きい場合、要求されたアイテム（Ｉ［ｉ］）をより上位のランクｉ’に移動させるように構成されることを特徴とする、請求項７に記載のキャッシュシステム。
【請求項９】
順序付けのための手段が、要求されたアイテム（Ｉ［ｉ］）のポピュラリティ確率ｆ（ｉ）が所定の値よりも大きい場合、要求されたアイテム（Ｉ［ｉ］）をリスト（Ｌ）の第１のランクに移動させるように構成されることを特徴とする、請求項８に記載のキャッシュシステム。
【請求項１０】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝ｅｘｐ（−λ＊（ｉ−１））のようであり、ここでλが正のパラメータであることを特徴とする、請求項８または９に記載のキャッシュシステム。
【請求項１１】
１≦ｉ≦Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝ｉ（−λ）のようであり、ここでλが正のパラメータであることを特徴とする、請求項８または９に記載のキャッシュシステム。
【請求項１２】
ｉ＞Ｃのランクｉについて、加速関数ｆが、ｆ（ｉ）＝１のようであり、順序付けのための手段が、要求されたアイテム（Ｉ［ｉ］）をリスト（Ｌ）の第１のランクに移動させるように構成されることを特徴とする、請求項７から１１のいずれか一項に記載のキャッシュシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎ個のアイテムのリストを、Ｃ個のアイテムを格納するためのメモリキャッシュを備えたキャッシュシステムなど、前記リストのＣ個のアイテムのメモリキャッシュに格納することを管理するための方法（ｐｒｏｃｅｓｓ）、およびこのような方法を実装するための手段に関する。
【背景技術】
【０００２】
本発明は特に、限られた数のアイテムを格納するために有限サイズのメモリキャッシュを備えたキャッシュシステムに適用され、前記メモリキャッシュの内容は、ユーザのアイテム要求および前記キャッシュシステムに適用される置換基準に従って、時間とともに変化する。
【０００３】
詳細には、置換基準は、例えばアイテムのアクセス頻度に依存するＬｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ（最長時間未使用：ＬＲＵ）置換基準とすることができ、最低のアクセス頻度のアイテムは、メモリキャッシュから取り除かれる一方で、最高のアクセス頻度のアイテムは、前記メモリキャッシュの第１のランクに配置されるようにする。
【０００４】
キャッシュシステムは、Ｍ．ＲＡＢＩＮＯＶＩＣＨおよびＯ．ＳＰＡＴＳＣＨＥＣＫによる論文「Ｗｅｂ  Ｃａｃｈｉｎｇ  ａｎｄ  Ｒｅｐｌｉｃａｔｉｏｎ」（Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ、第１版  ２００２、ＩＳＢＮ  ０−２０１−６１５７０−３）に説明されているように、例えばメモリコントローラ、またはウェブキャッシング領域など、主として異なる環境に配備される。またこのようなキャッシュシステムは、Ａ．ＶＡＫＡＬＩおよびＧ．ＰＡＬＬＩＳによる論文「Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋｓ：Ｓｔａｔｕｓ  ａｎｄ  Ｔｒｅｎｄｓ」（ＩＥＥＥ  Ｉｎｔｅｒｎｅｔ  Ｃｏｍｐｕｔｉｎｇ、２００３）およびＭ．ＰＡＴＨＡＮおよびＲ．ＢＵＹＹＡによる技術報告書「Ａ  Ｔａｘｏｎｏｍｙ  ａｎｄ  Ｓｕｒｖｅｙ  ｏｆ  Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋｓ」（ＧＲＩＤＳ−ＴＲ−２００７−４、Ｇｒｉｄ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ  Ｌａｂｏｒａｔｏｒｙ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｍｅｌｂｏｕｒｎｅ，Ａｕｓｔｒａｌｉａ）にさらに詳細に説明されているように、コンテンツ配信ネットワーク（ＣＤＮ）で現在使用されている。
【０００５】
実際に、こうした環境では、キャッシュシステムにより、頻繁にアクセスされるアイテムを要求者にとって閉じた（ｃｌｏｓｅｄ）場所に格納することによって、ストレージ機能をネットワークに分散することが可能になる。したがって、キャッシュシステムにより、トラフィック局在化（ｔｒａｆｆｉｃ  ｌｏｃａｌｉｚａｔｉｏｎ）を実施することが可能になり、これは、帯域幅需要が増大していること、および最も人気のあるアイテムの要求が重複することから非常に奨励されるものである。
【０００６】
例えば、一般的なウェブサーバを含むウェブネットワークにおいて、前記一般的なサーバよりも要求中のユーザにより近いプロキシサーバにウェブページを格納するために、したがってリンクおよび前記負担のかかり過ぎた一般的なサーバのトラフィック負荷の量を削減するために、ウェブキャッシュを使用することができる。このようなウェブキャッシュの使用はしたがって、インターネットサービスプロバイダ（ＩＳＰ）、企業ネットワーク、およびユーザに大きな利益をもたらす。
【０００７】
詳細には、インターネット利用の制御されない成長による帯域幅需要を制限するために、ローカルアプリケーション層のキャッシングをネットワークに拡大するいくつかのキャッシングソリューションが存在する。これは特に、Ｔｅｌｃｏ（Ｒ）ソサイエティによって開発されたコンテンツ配信ネットワークまたはトランスペアレントキャッシングソリューションの場合である。さらに、このようなシステムでは、コンテンツキャッシングにより、トラフィックおよびサーバ負荷を低減しながら、エンドユーザ応答時間を向上させ、したがってサービス可用性を増大させることができる。
【０００８】
トランスペアレントキャッシングソリューションは、キャリアネットワークに直接埋め込まれて、前記ネットワークのオペレータに、コンテンツキャッシングに関して、およびコンテンツ配信の加速に関して完全な制御を与えるためのネットワークストレージソリューションである。さらに、トランスペアレントキャッシングソリューションにより、異なるアプリケーションのコンテンツに対して単一の基礎的なキャッシングインフラストラクチャを使用できるようになる。ｈｔｔｐ：／／ｂｌｏｇ．ｓｔｒｅａｍｉｎｇｍｅｄｉａ．ｃｏｍ／ｔｈｅ＿ｂｕｓｉｎｅｓｓ＿ｏｆ＿ｏｎｌｉｎｅ＿ｖｉ／２０１０／１０／ａｎ−ｏｖｅｒｖｉｅｗ−ｏｆ−ｔｒａｎｓｐａｒｅｎｔ−ｃａｃｈｉｎｇ．ｈｔｍｌ＃ｍｏｒｅで入手できる論文「Ａｎ  Ｏｖｅｒｖｉｅｗ  Ｏｆ  Ｔｒａｎｓｐａｒｅｎｔ  Ｃａｃｈｉｎｇ  ａｎｄ  Ｉｔｓ  Ｒｏｌｅ  Ｉｎ  Ｔｈｅ  ＣＤＮ  Ｍａｒｋｅｔ」は、ＣＤＮネットワークにおけるトランスペアレントキャッシングソリューションの実施をさらに詳細に説明している。
【０００９】
さらに、ホストアドレスの代わりに名前をつけられたコンテンツに基づくコンテンツセントリックネットワーク（Ｃｏｎｔｅｎｔ  Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋ：ＣＣＮ）アーキテクチャが、現在開発中である。このようなアーキテクチャは、ルータに拡張メモリを備え付けることによってストレージ機能をネットワークに埋め込むことを可能にするという点で特に注目に値する。ＣＣＮアーキテクチャはさらに、例えばＡｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｃｉｅｎｃｅ  Ｆｕｎｄａｔｉｏｎ（米国国立科学財団：ＮＳＦ）のＮａｍｅｄ  Ｄａｔａ  Ｎｅｔｗｏｒｋｉｎｇプロジェクトを扱っているウェブサイトｈｔｔｐ：／／ｗｗｗ．ｎａｍｅｄ−ｄａｔａ．ｎｅｔ上で、論文「Ｎｅｔｗｏｒｋｉｎｇ  Ｎａｍｅｄ  Ｃｏｎｔｅｎｔ」（Ｖ．ＪＡＣＯＢＳＯＮ、Ｄ．Ｋ．ＳＭＥＴＴＥＲＳ、Ｊ．Ｂ．ＴＨＯＲＮＴＯＮ、Ｍ．Ｆ．ＰＬＡＳＳ，Ｎ．Ｈ．ＢＲＩＧＧＳ、Ｒ．Ｌ．ＢＲＡＹＮＡＲＤ、ＣｏＮＥＸＴ  ２００９、ローマ、２００９年１２月）、および「Ａ  Ｓｕｒｖｅｙ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ−Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋｉｎｇ」（Ｂ．ＡＨＬＧＲＥＮ、Ｃ．ＤＡＮＮＥＶＩＴＺ、Ｃ．ＩＭＢＲＥＮＤＡ、Ｄ．ＫＵＴＳＣＨＥＲ、Ｂ．ＯＨＬＭＡＮ、Ｄａｇｓｔｕｈｌ  Ｓｅｍｉｎａｒ  Ｐｒｏｃｅｅｄｉｎｇｓ、Ｄａｇｓｔｕｈｌ、Ｇｅｒｍａｎｙ、２０１１）に記載されている。
【００１０】
したがってコンテンツキャッシングソリューションは主として、特に異なるアプリケーションからコンテンツを格納するために配備されており、これはその管理を複雑にする。実際に、ストレージリソースがいくつかのアプリケーション間で共有されるので、前記リソースの動特性の管理（ｍａｎａｇｉｎｇ  ｄｙｎａｍｉｃｓ）は、各コンテンツのポピュラリティ変動（ｐｏｐｕｌａｒｉｔｙ  ｖａｒｉａｔｉｏｎｓ）を追跡するように構成されなければならず、前記ポピュラリティは、時間とともに大いに変動するだけでなく、アプリケーションごとにも大いに変動する。
【００１１】
これを行うために、最長時間未使用（ＬＲＵ）置換ポリシーがストレージリソースを管理するために最も一般的に使用される。その理由は、実装するのが比較的単純かつ容易であり、偏ったポピュラリティ分布、すなわちカタログは大きいが非常に人気のあるアイテムはほんのわずかであるというポピュラリティパターンを持つコンテンツのポピュラリティパターンの場合、よく知られている（ｎｏｔｏｒｉｏｕｓ）効率を有するからである。
【００１２】
例えば、論文「Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｔｏｒａｇｅ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ：Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｉｅｓ」（Ｐ．Ｋ．Ｃ．ＴＳＥ、ＩＳＢＮ  １０：１５９９０４２２５８／１−５９９０４−２２５−８、２００８）のＶ節に概要が示されているように、コンテンツキャッシングソリューションにおける置換ポリシーについて、多くの研究が行われてきた。
【００１３】
詳細には、これらの研究の多くは、特に、キャッシュ管理動特性を要求パターンおよび負荷に関する特定の仮定に条件づけるように、コンテンツリソースの予想される負荷に基づいてプリチューニング（ｐｒｅ−ｔｕｎｉｎｇ）を確立するために、ＬＲＵ型ポリシーを変更することに関するものである。しかしながら、このような変更は、多くの異なるアプリケーションからコンテンツを格納し、そのポピュラリティおよび負荷が時間とともに変動するキャッシュシステムの管理にあまり適合されていない。
【００１４】
ＬＲＵポリシーに基づく他の研究は、よりよい性能を生み出すが、一方ではより高い複雑度を生じる標準的ＬＲＵ置換ポリシーの変更に焦点を当てる。このような変更に基づくメカニズムの一例が、適応型置換キャッシュ（ＡＲＣ）と呼ばれ、論文「Ｏｕｔｐｅｒｆｏｒｍｉｎｇ  ＬＲＵ  ｗｉｔｈ  ａｎ  Ａｄａｐｔｉｖｅ  Ｒｅｐｌａｃｅｍｅｎｔ  Ｃａｃｈｅ  Ａｌｇｏｒｉｔｈｍ」（Ｎ．ＭＥＧＩＤＤＯ、Ｄ．Ｓ．ＭＯＤＨＡ、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ、Ｖｏｌｕｍｅ  ３７、５８−６５頁、２００４年４月）に詳細に記載されており、前記メカニズムは、作業負荷の最新性（ｒｅｃｅｎｃｙ）特性および頻度（ｆｒｅｑｕｅｎｃｙ）特性を継続的に監視し、活用することによって、時間にわたるポピュラリティ変動の問題を処理することを提案する。このようなメカニズムは、標準的ポリシーに基づくメカニズムよりも、要求パターンへのより高度な適応を実証し、作業負荷固有のプリチューニングの必要性をなくすことができる。
【００１５】
しかしながら、標準的ＬＲＵ置換ポリシーのアルゴリズムの複雑性は、Ｏ（１）であるのに対して、ＡＲＣメカニズムは、Ｃがメモリキャッシュのサイズであるとすると、Ｏ（Ｃ）の複雑性を有するアルゴリズムを使用する。さらに、要求トラフィックの効果的な監視は、低要求レートが存在する場合、達成するのが困難である。
【００１６】
ＬＲＵポリシーの変更に関する別の著作は、論文「Ｏｐｔｉｍａｌ  Ｐａｒｔｉｔｉｏｎｉｎｇ  ｏｆ  Ｃａｃｈｅ  Ｍｅｍｏｒｙ」（Ｈ．Ｓ．ＳＴＯＮＥ、Ｊ．ＴＵＲＥＫ、Ｊ．Ｌ．ＷＯＬＦ、ＩＥＥＥ  ｔｒａｎｓａｃｔｉｏｎｓ  ｏｆ  ｃｏｍｐｕｔｅｒ  １９９２、ｖｏｌｕｍｅ  ４１、ｉｓｓｕｅ  ９）に説明されるように、異なる要求によって特徴付けられるアイテムに対応するために、キャッシュ分割（ｃａｃｈｅ  ｐａｒｔｉｔｉｏｎｉｎｇ）を活用してサービス差別化を提供することを提案する。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Ｍ．ＲＡＢＩＮＯＶＩＣＨおよびＯ．ＳＰＡＴＳＣＨＥＣＫによる論文「Ｗｅｂ  Ｃａｃｈｉｎｇ  ａｎｄ  Ｒｅｐｌｉｃａｔｉｏｎ」、Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ、第１版  ２００２、ＩＳＢＮ  ０−２０１−６１５７０−３
【非特許文献２】Ａ．ＶＡＫＡＬＩおよびＧ．ＰＡＬＬＩＳによる論文「Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋｓ：Ｓｔａｔｕｓ  ａｎｄ  Ｔｒｅｎｄｓ」、ＩＥＥＥ  Ｉｎｔｅｒｎｅｔ  Ｃｏｍｐｕｔｉｎｇ、２００３
【非特許文献３】Ｍ．ＰＡＴＨＡＮおよびＲ．ＢＵＹＹＡによる技術報告書「Ａ  Ｔａｘｏｎｏｍｙ  ａｎｄ  Ｓｕｒｖｅｙ  ｏｆ  Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋｓ」、ＧＲＩＤＳ−ＴＲ−２００７−４、Ｇｒｉｄ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ  Ｌａｂｏｒａｔｏｒｙ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｍｅｌｂｏｕｒｎｅ，Ａｕｓｔｒａｌｉａ
【非特許文献４】「Ａｎ  Ｏｖｅｒｖｉｅｗ  Ｏｆ  Ｔｒａｎｓｐａｒｅｎｔ  Ｃａｃｈｉｎｇ  ａｎｄ  Ｉｔｓ  Ｒｏｌｅ  Ｉｎ  Ｔｈｅ  ＣＤＮ  Ｍａｒｋｅｔ」、ｈｔｔｐ：／／ｂｌｏｇ．ｓｔｒｅａｍｉｎｇｍｅｄｉａ．ｃｏｍ／ｔｈｅ＿ｂｕｓｉｎｅｓｓ＿ｏｆ＿ｏｎｌｉｎｅ＿ｖｉ／２０１０／１０／ａｎ−ｏｖｅｒｖｉｅｗ−ｏｆ−ｔｒａｎｓｐａｒｅｎｔ−ｃａｃｈｉｎｇ．ｈｔｍｌ＃ｍｏｒｅ
【非特許文献５】「Ｎｅｔｗｏｒｋｉｎｇ  Ｎａｍｅｄ  Ｃｏｎｔｅｎｔ」（Ｖ．ＪＡＣＯＢＳＯＮ、Ｄ．Ｋ．ＳＭＥＴＴＥＲＳ、Ｊ．Ｂ．ＴＨＯＲＮＴＯＮ、Ｍ．Ｆ．ＰＬＡＳＳ，Ｎ．Ｈ．ＢＲＩＧＧＳ、Ｒ．Ｌ．ＢＲＡＹＮＡＲＤ、ＣｏＮＥＸＴ  ２００９、ローマ、２００９年１２月）
【非特許文献６】「Ａ  Ｓｕｒｖｅｙ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ−Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋｉｎｇ」（Ｂ．ＡＨＬＧＲＥＮ、Ｃ．ＤＡＮＮＥＶＩＴＺ、Ｃ．ＩＭＢＲＥＮＤＡ、Ｄ．ＫＵＴＳＣＨＥＲ、Ｂ．ＯＨＬＭＡＮ、Ｄａｇｓｔｕｈｌ  Ｓｅｍｉｎａｒ  Ｐｒｏｃｅｅｄｉｎｇｓ、Ｄａｇｓｔｕｈｌ、Ｇｅｒｍａｎｙ、２０１１）
【非特許文献７】「Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｔｏｒａｇｅ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ：Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｉｅｓ」、Ｐ．Ｋ．Ｃ．ＴＳＥ、ＩＳＢＮ  １０：１５９９０４２２５８／１−５９９０４−２２５−８、２００８
【非特許文献８】「Ｏｕｔｐｅｒｆｏｒｍｉｎｇ  ＬＲＵ  ｗｉｔｈ  ａｎ  Ａｄａｐｔｉｖｅ  Ｒｅｐｌａｃｅｍｅｎｔ  Ｃａｃｈｅ  Ａｌｇｏｒｉｔｈｍ」、Ｎ．ＭＥＧＩＤＤＯ、Ｄ．Ｓ．ＭＯＤＨＡ、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ、Ｖｏｌｕｍｅ  ３７、５８−６５頁、２００４年４月
【非特許文献９】「Ｏｐｔｉｍａｌ  Ｐａｒｔｉｔｉｏｎｉｎｇ  ｏｆ  Ｃａｃｈｅ  Ｍｅｍｏｒｙ」、Ｈ．Ｓ．ＳＴＯＮＥ、Ｊ．ＴＵＲＥＫ、Ｊ．Ｌ．ＷＯＬＦ、ＩＥＥＥ  ｔｒａｎｓａｃｔｉｏｎｓ  ｏｆ  ｃｏｍｐｕｔｅｒ  １９９２、ｖｏｌｕｍｅ  ４１、ｉｓｓｕｅ  ９
【発明の概要】
【発明が解決しようとする課題】
【００１８】
本発明は、アイテムをキャッシュシステムのメモリキャッシュに格納することを管理するための方法を提案することによって、従来の技術を向上させることを目的とし、前記方法は、ＬＲＵ型ポリシーに基づいたキャッシュ動特性が定常状態、すなわち、最も人気のあるアイテムすべてがメモリキャッシュに格納される、したがってモバイル環境のように、時間とともに変化するポピュラリティパターンおよび／または低要求レートが存在しても格納される状態に迅速に収束することを可能にする。
【００１９】
実際に、定常状態への収束は、要求レートによって決まり、したがって前記レートが低いとき、経験値と最適ＬＲＵヒット確率すなわち定常状態のメモリキャッシュで人気のあるアイテムを見つける確率との間に有意の差が存在する可能性がある。
【課題を解決するための手段】
【００２０】
そのために、また第１の態様により、本発明は、Ｎ個のアイテムのリストを前記リストのＣ個のアイテムのメモリキャッシュに格納することを管理するための方法に関し、前記Ｎ個のアイテムは、ユーザＣによるそれらの最後の要求時間によって決まるランクｉに従って前記リスト中で順序付けられ、Ｃ、Ｎ、およびｉは厳密には正の正数であり、前記方法は、アイテムの要求を受け取ったとき、ｆが加速関数（ａｃｃｅｌｅｒａｔｉｏｎ  ｆｕｎｃｔｉｏｎ）であるとすると、前記要求されたアイテムのポピュラリティ確率ｆ（ｉ）を計算することと、前記ポピュラリティ確率に従って前記要求されたアイテムをより上位のランクｉに移動させるかどうかを決定することとを行う。
【００２１】
第２の態様によれば、本発明は、Ｎ個のアイテムのリストのＣ個のアイテムを格納するためのメモリキャッシュを備えたキャッシュシステムに関し、前記キャッシュシステムは、ユーザからアイテムの要求を受け取るための手段と、それらの最後の要求時間によって決まるランクｉに従って前記リスト中のアイテムを順序付けるための手段とを備え、Ｎ、Ｃ、およびｉは厳密には正の整数であり、さらにこのキャッシュシステムは、アイテムの要求を受け取ったとき、ｆが加速関数であるとすると、前記アイテムのポピュラリティ確率ｆ（ｉ）を計算するための手段と、前記ポピュラリティ確率に従って前記要求されたアイテムをより上位のランクｉに移動させるかどうかを決定するように構成された順序付けのための手段とを備える。
【００２２】
添付の図面を参照して行う次の説明において、本発明の他の態様および利点が明らかになるであろう。
【図面の簡単な説明】
【００２３】
【図１】本発明による方法の異なるステップを概略的に表す図である。
【図２】図１の方法によりリストのＮ個のアイテムを順序付けることを概略的に表す図である。
【発明を実施するための形態】
【００２４】
これらの図に関して、Ｎ個のアイテムＩ［ｉ］のリストＮを前記リストのＣ個のアイテムのメモリキャッシュＭに格納することを管理するための方法について、ＮおよびＣは厳密には正の整数であって、Ｃは前記メモリキャッシュのサイズに対応するとして、以下に説明し、例えばキャッシュシステムは、前記リストのＣ個のアイテムＩ［ｉ］を格納するためのメモリキャッシュＭと、このような方法を実施するための手段とを備える。
【００２５】
この方法は、リストＬのＮ個のアイテムＩ［ｉ］が、ユーザによるそれらの最後の要求時間によって決まるランクｉに従って前記リスト中で順序付けられることを定め、ｉは厳密には正の整数であり、Ｉ［１］は、例えばランク１のアイテムであって、最も最近に要求されたアイテムであり、Ｉ［ｉ］は、１≦ｉ≦Ｎであるランクｉのアイテムであり、Ｉ［Ｎ］は、ランクＮのアイテムであって、最も過去に（ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ）要求されたアイテムである。したがって、方法は、最長時間未使用タイプのポリシーに従う。
【００２６】
これを行うために、キャッシュシステムは、ユーザからアイテムＩ［ｉ］の要求を受け取るための手段と、前記定義されたランクｉに従って、１≦ｉ≦Ｃのランクｉを有するアイテムＩ［ｉ］のみがメモリキャッシュに格納されるように、リストＬ中でアイテムＩ［ｉ］を順序付けるための手段とを備える。
【００２７】
標準的なＬＲＵ置換ポリシーでは、アイテムの要求を受け取ったとき、要求されたアイテムＩ［ｉ］は、リストＬの第１のランクに自動的に移動される。さらに、要求されたアイテムＩ［ｉ］が、メモリキャッシュＭに最初に存在しなかった場合、すなわち前記アイテムのランクｉがＣよりも大きい場合、および前記メモリキャッシュがすでに一杯であった場合、メモリキャッシュＭの最も過去に要求されたアイテムＩ［Ｃ］が、前記メモリキャッシュから取り除かれる一方で、要求されたアイテムＩ［ｉ］は、前記メモリキャッシュの第１のランクに移動される。
【００２８】
しかしながら、このような従来のポリシーでは、メモリキャッシュＭは、すべての最も人気のあるアイテムＩ［ｉ］が、前記メモリキャッシュに格納される、その定常状態に到達するまでに長い遷移段階を経験し、前記遷移段階は、アイテム要求レートが低いとき、ますます長くなる。さらに、遷移段階が長くなればなるほど、メモリキャッシュＭのパフォーマンスの低下が大きくなる。
【００２９】
詳細には、シミュレーション結果により、ＬＲＵキャッシュ動特性の収束、したがってメモリキャッシュＭのパフォーマンスが、ポピュラリティ分布パターンの不完全な認識によって悪影響を受け、前記パターンは、特に経験から学んだポピュラリティ確率を反映することを確認することができた。例えば、アイテムＩ［ｉ］がメモリキャッシュＭで見つけられる確率を反映するヒット確率、または逆にアイテムＩ［ｉ］が前記メモリキャッシュで見つけられない確率を反映するミス確率が、ポピュラリティ確率である。
【００３０】
こうした欠点を克服するために、方法は、アイテムＩ［ｉ］の要求を受け取ったとき、ｆが加速関数であるとすると、前記要求されるアイテムのポピュラリティ確率ｆ（ｉ）を計算することと、前記ポピュラリティ確率に従って前記要求されるアイテムをより上位のランクｉに移動させるかどうかを決定することとを行う。
【００３１】
詳細には、加速関数ｆは、すべてのランクｉに対して、ポピュラリティ確率ｆ（ｉ）の値が、時間とともにその定常値に迅速に、特に、ＬＲＵ動特性を有する従来のキャッシュシステムのポピュラリティ確率よりも速く収束するように選択される。
【００３２】
したがって、この方法は、キャッシュシステムのキャッシュ動特性を加速させることを可能にするメカニズムを提案し、前記メカニズムは、アイテムＩ［ｉ］の局所的最新性（ｌｏｃａｌ  ｒｅｃｅｎｃｙ）尺度を利用して、前記アイテムをリストＬの前方に移動させる確率を決定する。
【００３３】
そのために、キャッシュシステムは、アイテムＩ［ｉ］の要求を受け取ったとき、前記アイテムの人気確率ｆ（ｉ）を計算するための手段を備え、順序付けのための手段は、前記人気確率に従って前記要求されるアイテムをより上位のランクｉに移動させるかどうかを決定するように構成される。
【００３４】
図１に関して、この方法は、キャッシュシステムがアイテムＩ［ｉ］の要求を受け取る第１のステップＡを含み、前記第１のシステムは、要求されたアイテムＩ［ｉ］のランクｉが検証されるステップＢをトリガし、この結果として、メモリキャッシュＭに前記アイテムが存在すること（ランクｉが１≦ｉ≦Ｃのようである場合）または前記メモリキャッシュに前記アイテムが存在しないこと（ランクｉがｉ＞Ｃのようである場合）を検証する。
【００３５】
したがって、この方法は、次のステップＫをトリガし、ランクｉに従って、ゆえにメモリキャッシュＭに要求されたアイテムＩ［ｉ］が存在するか、存在しないかに従って、キャッシュシステムの計算のための手段によって、ポピュラリティ確率ｆ（ｉ）が計算される。
【００３６】
詳細には、この方法は、１≦ｉ≦Ｃのランクｉについて、すなわち、要求されたアイテムＩ［ｉ］がメモリキャッシュＭに存在するとき、加速関数ｆは、０≦ｆ（ｉ）≦１のようであって、ランクｉに関して低下し、要求されたアイテムＩ［ｉ］は、そのポピュラリティ確率ｆ（ｉ）が所定の値よりも大きい場合、より上位のランクｉに移動されることを定める。
【００３７】
さらに、この方法は、要求されたアイテムＩ［ｉ］のポピュラリティ確率が所定の値よりも大きい場合、要求されたアイテムＩ［ｉ］は、リストＬの第１のランクに移動されることを定めることができる。
【００３８】
図１および２に関して、計算ステップＫの後に、この方法は、ステップＤを行い、キャッシュシステムの順序付けのための手段は、ポピュラリティ確率ｆ（ｉ）を所定の値と比較し、要求されたアイテムＩ［ｉ］をより上位のランクｉに移動させることを決定する、または決定しない。図２に表すように、ポピュラリティ確率ｆ（ｉ）が所定の値よりも大きいとき、この方法は、移動ステップＥをトリガし、キャッシュシステムの順序付けのための手段が、要求されたアイテムＩ［ｉ］（図２のアイテムＩ［４］）をリストＬの第１のランクに移動させる。
【００３９】
そうではなく、ポピュラリティ確率ｆ（ｉ）が所定の値よりも低い場合、この方法は、ステップＦをトリガし、キャッシュシステムの順序付けのための手段が、要求されたアイテムＩ［ｉ］をその最初のランクｉとする。
【００４０】
詳細には、１≦ｉ≦Ｃのランクｉについて、加速関数ｆは、次のようであることが可能である：
−  ｆ（ｉ）＝ｅｘｐ（−λ＊（ｉ−１））、または
−  ｆ（ｉ）＝ｉ（−λ）
ここでλは正のパラメータである。
【００４１】
さらに、この方法は、ｉ＞Ｃのランクｉについて、すなわち要求されたアイテムＩ［ｉ］がメモリキャッシュＭにないとき、加速関数ｆは、ｆ（ｉ）＝１であって、要求されるアイテムＩ［ｉ］は、リストＬの第１のランクに、すなわちメモリキャッシュＭに移動されることを定める。
【００４２】
図１および図２に関して、計算ステップＫの後、方法はステップＧを行い、順序付けのための手段が、メモリキャッシュＭが一杯であるかどうか、すなわち前記メモリキャッシュにすでにＣ個のアイテムＩ［１］−Ｉ［Ｃ］が存在するかどうかを検証する。メモリキャッシュＭが事実上一杯である場合、この方法はステップＨをトリガし、キャッシュシステムの順序付けのための手段が、メモリキャッシュＭの最長時間未使用のアイテムＩ［Ｃ］を前記メモリキャッシュから取り除き、したがって次のステップＩをトリガし、順序付けのための手段は、要求されたアイテムＩ［ｉ］をリストＬの第１のランクに、したがってメモリキャッシュＭに移動させる。
【００４３】
そうではなく、メモリキャッシュＭが一杯ではない場合、この方法は、ステップＧから、要求されたアイテムＩ［ｉ］をリストＬの第１のランクに移動させるステップＩに直接進むことを定める。
【００４４】
したがって、ステップＥ、Ｆ、Ｉのうちの１つの後、方法はステップＪで終了し、その後、キャッシュシステムの受け取るための手段が、別のアイテムＩ［ｉ］の別の要求を受け取ったとき、前記方法がステップＡで再開される。
【００４５】
したがって、この方法は、従来のＬＲＵポリシーよりも、格納されるアイテムの理想的なキャッシュ構成への収束時間を速くし、分散の低下をもたらし、したがって、コンテンツ要求パターンのポピュラリティ変化にキャッシュシステムをより速く、自動的に適合させることを可能にする。
【００４６】
さらに、この方法は、メモリキャッシュＭにより高いヒット確率をもたらし、したがって要求されるアイテムの配信時間をより短くし、そのため従来のキャッシュシステムよりも、同じストレージコストに対してよりよいパフォーマンスをユーザにもたらす。その上、この方法は、帯域幅削減を増大させる。
【００４７】
説明および図面は、本発明の原理を示すにすぎない。したがって、本明細書には明示的に記載または表示されていないが、本発明の原理を具体化し、本発明の趣旨および範囲の内に含まれる様々な仕組みを当業者は考案できるであろうことは理解されよう。さらに、本明細書に列挙するすべての例は、主として、発明者により当技術分野の促進にもたらされる本発明の原理および概念を理解する際に読者の助けとなるように、単に教育上の目的であることを明白に意図され、このような具体的に列挙した例および条件に限定しないものであると解釈されたい。さらに、本発明の原理、態様、および実施形態、ならびにその特定の例を列挙する本明細書中のあらゆる記載は、その均等物を含むものとする。
【図１】
0005998281.tif 000002
【図２】
0005998281.tif 000003