情報中心ネットワークのキャッシュポリシー

コンピューティングにおいて、キャッシュ アルゴリズム(キャッシュ置換アルゴリズムまたはキャッシュ置換ポリシーとも呼ばれる) は、コンピュータ プログラムまたはハードウェアで維持される構造がコンピュータに保存されている情報のキャッシュを管理するために従うことができる最適化された命令 (アルゴリズム)です。キャッシュがいっぱいになると、アルゴリズムは新しい項目のためのスペースを確保するためにどの項目を破棄するかを選択する必要があります。情報中心ネットワーク ICN のノードには固有のキャッシュ機能があるため、ICN はキャッシュの疎接続ネットワークと見なすことができ、キャッシュ ポリシーの独自の要件があります。プロキシ サーバーとは異なり、情報中心ネットワークでは、キャッシュはネットワーク レベルのソリューションです。したがって、キャッシュ状態は急速に変化し、要求の到着率は高くなります。さらに、キャッシュ サイズが小さいと、コンテンツの削除ポリシーにさまざまな種類の要件が課せられます。特に、情報中心ネットワークの削除ポリシーは高速で軽量である必要があります。さまざまな情報中心ネットワーク アーキテクチャとアプリケーション向けに、さまざまなキャッシュ複製および削除スキームが提案されています。

時間を考慮した Least Recently Used (TLRU) ^{[1] は、}キャッシュに格納されたコンテンツに有効な存続期間がある場合のために設計された LRU の変形です。このアルゴリズムは、情報中心ネットワーク (ICN)、コンテンツ配信ネットワーク(CDN)、一般的な分散ネットワークなどのネットワーク キャッシュ アプリケーションに適しています。TLRU では、TTU (Time to Use) という新しい用語が導入されています。TTU はコンテンツ/ページのタイム スタンプであり、コンテンツの局所性とコンテンツ発行者のアナウンスに基づいて、コンテンツの使用可能時間を規定します。この局所性に基づくタイム スタンプにより、TTU はネットワーク ストレージを規制するためのローカル管理者により多くの制御を提供します。TLRU アルゴリズムでは、コンテンツが到着すると、キャッシュ ノードはコンテンツ発行者によって割り当てられた TTU 値に基づいてローカル TTU 値を計算します。ローカル TTU 値は、ローカルで定義された関数を使用して計算されます。ローカル TTU 値が計算されると、キャッシュ ノードに格納されている全コンテンツのサブセットに対してコンテンツの置き換えが実行されます。 TLRU は、人気のないコンテンツや小規模なコンテンツが、新しいコンテンツに置き換えられることを保証します。

LFRU (Least Frequent Recently Used) ^[2]キャッシュ置換方式は、LFU 方式と LRU 方式の利点を組み合わせたものです。LFRU は、ICN、CDN、分散ネットワーク全般などの「ネットワーク内」キャッシュ アプリケーションに適しています。LFRU では、キャッシュは特権パーティションと非特権パーティションと呼ばれる 2 つのパーティションに分割されます。特権パーティションは、保護されたパーティションとして定義できます。コンテンツの人気が高い場合は、特権パーティションにプッシュされます。特権パーティションの置換は、次のように行われます。LFRU は、非特権パーティションからコンテンツを追い出し、特権パーティションから非特権パーティションにコンテンツをプッシュし、最後に新しいコンテンツを特権パーティションに挿入します。上記の手順では、特権パーティションに LRU が使用され、非特権パーティションには近似 LFU (ALFU) 方式が使用されるため、略語は LFRU です。基本的な考え方は、ALFU 方式を使用してローカルで人気のあるコンテンツをフィルターし、人気のあるコンテンツを特権パーティションの 1 つにプッシュすることです。