name name IP [6] ICN Zipf 2 5 [7] 2 name 2 CCN 3 ICN Compact CCN 2. ICN ICN name NDN/CCN [], [2] CCN MTU name Interest Data CCN FIB PIT CS 3 CS

(1)

情報指向ネットワークルータにおける実装を考慮したキャッシュ置換方式

の提案と評価

大岡

睦

†

阿多信吾

††

村田正幸

†

大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5

††

大阪市立大学大学院工学研究科〒 558-8585 大阪府大阪市住吉区杉本 3-3-138

E-mail:

†{

a-ooka,murata

}

@ist.osaka-u.ac.jp,

††

ata@info.eng.osaka-cu.ac.jp

あらまし情報指向ネットワーク (ICN) におけるルータキャッシング技術の実現には，ルータハードウェア実装を考慮

した低オーバーヘッドかつ高キャッシュヒット率を達成可能なキャッシュ置換手法が必要不可欠である．しかし，既存

のキャッシング手法は極めて単純な手法を採用するか，キャッシュ性能向上のために実装不可能なオーバーヘッドを要

するものばかりである．本研究では CAR を参考にして以上の要件を満たすキャッシュ置換手法として Compact CAR

を提案し，単純な手法と同じ性能が 1/10 のキャッシュサイズで達成可能ば場合があることをシミュレーション評価に

よって示す．

キーワード新世代ネットワーク，情報指向ネットワーク (ICN)，コンテンツセントリックネットワーク (CCN)，キャッ

シング，キャッシュ置換方式

A Proposal and Evaluation of Cache Replacement Policy for the

Implementation of ICN Router

Atsushi OOKA

†

, Shingo ATA

††

, and Masayuki MURATA

†

Graduate School of Information Science and Technology, Osaka University

1-5 Yamadaoka, Suita, Osaka, 565-0871, Japan

††

Graduate School of Engineering, Osaka City University

3-3-138 Sugimoto, Sumiyoshi-ku, Osaka-shi, Osaka 558-8585, Japan

E-mail:

†{

a-ooka,murata

}

@ist.osaka-u.ac.jp,

††

ata@info.eng.osaka-cu.ac.jp

Abstract

Information-centric networking (ICN) requires an innovative cache replacement algorithm with performance far

superior to simple policies such as FIFO and computational and memory overheads that are low enough to run on ICN router’s

hardware. We focus on CAR as the suitable policy for an access pattern of workload on the router and propose the cache

replacement policy (called Compact CAR) that satisfies the requirements. We also evaluate our proposed approach and show

that the size of cache memory required to achieve a certain performance can be reduced to 1/10th of that of the simple policy.

Key words

Future Networks, Information-Centric Networking, Content-Centric Networking, Caching, Cache Replacement

Policy

1. はじめに

現在のインターネットが直面する課題を解決する将来インターネットとしてInformation-Centric Networking (ICN)が注目されている．現在のインターネットはトラフィック量の急増，携帯端末普及によるネットワーク接続機器数の爆発的増加，高度なアプリケーションのための品質・セキュリティ・頑強性の要請など，様々な問題に直面している．これらの問題を個々に解決するのではなく，ネットワークアーキテクチャから根本的な改革を図る試みとしてICNが注目されている．インターネットが端末間通信に焦点を当てて端末の在処に対してアドレスを割り振るのに対して，ICNでは，現在の利用形態に即して， IPアドレスの代わりにコンテンツごとにnameと呼ばれる識別子を割り当て，情報とユーザを結びつける．その有望性から，NDN/CCN [1]∼[3], PSIRP/PURSUIT [4], SAIL/NetInf [5]など，世界的に多数のプロジェクトが存在している．しかし，ICNは未だに開発初期段階にあり，課題は山積している．ICNはclean-slateなアーキテクチャであり，厳密なプロトコルとそれをサポートするデバイスは策定段階にある．従来のIPアドレスとは異なり，nameアドレスは位置を指定するも

(2)

のではないため，情報とその所在を結びつけるルーティングとフォワーディングが必要である．nameアドレスは中継ルータにおけるキャッシングを可能にするが，限られた資源でネットワーク負荷を大幅に軽減する方策も求められる．また，nameアドレスは可変長でIPアドレスよりも長く扱いづらいことが想定されるため，これをハードウェアで高速にサポートする方法についても研究されている[6]．ネットワーク内部のルータにおけるキャッシングはICNの有用な特徴であり，活発に研究が行われている．増大の一途を辿るネットワークトラフィックはZipf則に従うと言われ，多数のパケットが重複した情報を運ぶ冗長な通信が行われている．観測期間によっても値は異なるが，2回以上アクセスのあるコンテンツがトラフィック量に対して占める割合は5割を超えるという結果もある[7]．その潜在性からキャッシングに関する研究は多数行われており，ルータがどのコンテンツをキャッシュすべきか，また，ストレージが溢れた際にどのキャッシュを置換すべきかを決定する主に2つの観点からアルゴリズムが研究されている．本稿では，ルータにおけるキャッシング実装の問題を解決するために，実用的かつ高いキャッシュヒット率を達成可能なキャッシュ置換手法を提案する．ルータでは資源やパケットの処理時間が限られており，キャッシュ置換手法が要求する計算量・メモリオーバーヘッドはそれらの制約を満足させるものでなければならない．しかし，既存研究はキャッシュヒット率を犠牲にする極めて単純な手法を採用したものや，nameアドレスを活用したきめ細やかな統計情報を用いるために実用時間内の処理が不可能な手法を提案するものばかりである．また，過去の計算機領域におけるキャッシング置換手法の研究はプロセス処理特有のアクセスに特化されており，ネットワークに直接応用できるかは明らかではない．そこで，本研究ではルータにおける実現可能性と，ネットワークにおける高い性能の両立を可能とする手法を提案する．本稿の構成は以下のようになる．2章で，CCNについて述べ，キャッシングの研究の現状について概観する．3章で，本研究の背景としてキャッシュに関する知見をまとめ，ICNにおける実用的かつ効果的なキャッシュ置換手法とは何かを分析する．その分析に基いて，CARに基づく低オーバーヘッドかつ高ヒット率な提案手法として，Compact CARの設計について4章に詳述する．5章の評価結果から，提案手法によって単純な手法と比較して同一のキャッシュヒット率を達成するために10の1 以下のメモリ容量で済む場合があることを明らかにする．最後に，考察と結論をまとめる．

2.

3. 背

景

本章では，ネットワークトラフィックに適した低オーバーヘッドなキャッシング手法の設計思想を示す．計算機科学領域の知見から得られた課題について整理した後，これらの知見をネットワークに適用してネットワークトラフィック特有の問題を解決可能かつその特徴を活かすキャッシング手法を議論する． 3. 1 キャッシングの課題まず，キャッシュヒット率を悪化させる主要な4つのアクセス

パターン[20]として，scan, loop, correlated-reference,

frequently-shiftsについて説明する．scanは1度しかアクセスされないチャンクの連続的な読み込みである．一般的にはキャッシュサイズを超える数のユニークチャンクへのアクセスから構成され，LRU の性能を大きく悪化させる．特にnS> cのときにはチャンクされているページすべてが一度もキャッシュヒットしないチャンクによって置き換えられるキャッシュ汚染が発生する．loop は，キャッシュサイズを超える長さのscanの繰り返しである．科学計算の膨大な量のデータに対する繰り返し計算で見られるパターンで，すべてのチャンクの局所性・アクセス頻度が等しいため，基本的な戦略(LRU, LFU, ARCなど)でscanと同様のキャッシュ汚染が連続的に発生してしまう．correlated-reference は，あるチャンクに対するアクセスが短期間に集中するようなアクセスパターンである．これらのチャンクは集中アクセスが終わるとそれ以降全くアクセスされなくなるという特徴を持ち， LFUなどのアクセス頻度に基づく手法は，長期的なキャッシングが不要なチャンクに高い優先度を付与してしまい，キャッシュする価値のないチャンクが長期間キャッシュに留まるという問題が発生する．frequently-shiftsは，アクセスされるチャンク集合が頻繁に切り替わるアクセスパターンである．LIRSのように，チャンクの一部を優遇して長期的に保持する手法では，アクセス列の切り替わりの際に新しいアクセス列への対応が遅れてしまい，キャッシュヒット率が低下する．つぎに，キャッシュにおいて注目すべきオーバーヘッドについてまとめる．第一にデータ構造の維持管理のための計算量オーバーヘッドが挙げられる．キャッシュヒット/ミスに応じてデータ構造の整合性を保つためのオーバーヘッドで，LRUにおける MRU operationなど，キャッシュへのアクセスがある度に負荷の大きい処理が必要な手法は，高速環境下では実現できない．逆に，CLOCKやNRUは維持管理コストは制御ビットの変更だけで済む．第二に，置換ページを探索するための計算量オーバーヘッドが挙げられる．LFUやLRUは優先度キューを実装すれば，キューのtailを削除するだけでよい．NRUやCLOCK

はRビットがsetされたページ数が増えるほど探索回数が増える．第三に，制御用の情報を記憶するためのメモリオーバーヘッドがある．チャンクごとの置換の優先順位を決定するための情報を記憶するために必要で，LRU-stackのようにデータ構造だけで管理が可能な場合を除いて，基本的にはこのオーバーヘッドはキャッシュサイズに従って増大する．NRUやCLOCK のような単純な手法は1チャンクあたり1bitで済む．ARCや

(4)

LIRSなど，ghost cacheを持つ手法は，キャッシュサイズ以上のオーバーヘッドが必要となる．特に，LFUなどの統計情報を用いる手法は，維持管理コストも含めて実現が困難である． 3. 2 ICNにおけるキャッシング前節で議論した計算機領域のキャッシングに関する知見に基いて，ICNにおけるキャッシング手法を考察する．まずアクセスパターンに関して，計算機領域とネットワーク領域では3つの点で大きく異なる．1点目はアクセスの同時性で，計算機領域は単一プロセスのページアクセスを対象としたのに対して，ルータは多数のユーザからの要求を同時並列的に受け付ける．多数同時アクセスによって，scanやloopといったアクセスパターンは変則的になる．例えば，多数のユーザから独立したアクセスが行われた場合，互いに無関係なワンタイマーコンテンツ要求はscanを頻繁に生成しうる．また，要求されるコンテンツが激しく変動することで，frequently-shiftsが発生するだろう． 2点目に，コンテンツチャンクの粒度がキャッシュの動作に甚大な影響を与える．チャンクの粒度がコンテンツサイズと等しい場合，例えばWebページのような複数のコンテンツから構成されるコンテンツや，連続的にコンテンツを取得する必要があるVoIPやストリーミングサービスなどだけがscanやloop

を生成しうる．一方，チャンクの粒度が小さく，イーサネットフレームのMTUと等しい1.5KB程度を想定すると，単一のコンテンツへの要求によってscanやloopが発生しうる．例えば，100MBの動画コンテンツはルータのキャッシュに対して約 700k回のアクセスを発生させるだろう． 3点目はネットワーク中に複数のキャッシュが存在する点である．これは要求がルータによって応答される機会を増やすと同時に，問題のあるアクセスパターンによる悪影響が多数のルータに伝搬する可能性を示唆している．要求の満足される確率を維持しつつこの悪影響を低減するためには，適切な協調的キャッシング戦略が必要となる．例えば，10個のルータで別々のコンテンツを協調的にキャッシュすることとすれば，擬似的に10倍のサイズを持った1つのキャッシュストレージをネットワーク上に実現することができ，チャンク分割によって顕在化しやすくなったscanやloopの影響を軽減しうる．当然これを実現するためには適切なキャッシュ判断・配置アルゴリズムと，協調キャッシングをサポートするルーティングプロトコルが必要となる．本稿はルータの実装において必要なキャッシュ置換アルゴリズムに焦点を当てるため，詳細な議論は省略する．ルータにおけるキャッシングでは，以上のようなネットワークアクセスの特徴に適したアルゴリズムが必要である．特に

scanやfrequently-shiftsに強く，可能であればloopに強いこと

が望ましい．したがって，ARCやCLOCK-Proが高キャッシュヒット率を達成できると考えられる．correlated-referenceが発生する傾向は弱いと考えられ，統計的情報を利用する手法は高い性能を発揮することができると予想される．ただし，LFUは loopやfrequtently-shiftsに弱いため不適だろう．性能だけではなく，アルゴリズムが低オーバーヘッドかつ高速である必要がある．キャッシュ性能の向上を目指して統計情報を活用するLFUなどの手法をルータで運用するのはメモリ・探索・データ構造管理すべてのオーバーヘッドの観点から困難である．ARCやLIRSを始めとして，多くのキャッシング手法はLRU相当のオーバーヘッドを目指して設計されているが， LRUはハードウェア実装においてはオーバーヘッドが大きすぎる．CLOCKは低オーバーヘッドなメモリ管理方式として実績がある点が注目されており[17], [18]，本稿でもデータ構造管理と探索コストが抑えられる手法としてCLOCKを採用する． NRUは探索コストが不要に大きくなる可能性があり，性能も CLOCKに劣る． CLOCKと同等の低オーバーヘッドかつネットワークトラフィックに適したアルゴリズムの候補としては，CLOCK-Proと

CARが挙げられる．CLOCK-Proはその長所であるloopへの耐性が限定的であるという問題があり，frequently-shiftsに強くな

い点からもCARより性能の面で劣ると考えられる．更に，1つ

のCLOCK上で独立して動作する針を3本持っており，CLOCK

と比較して針の動作回数が多くなる欠点もあり，候補から除外する．CARはloopに対処できないが，scan，frequently-shifts

に高い耐性を持っている．CARは可変長のCLOCKを採用している点，LRUが残っている点から，低オーバーヘッドとは言えないが，次章でその問題を解決する方法を提示する．

4. 提案方式の設計

本章では，提案方式Compact CARの具体的なデータ構造とアルゴリズムについて議論する．CARを低オーバーヘッドに改良することで，低オーバーヘッドかつ高ヒット率なキャッシュ置換手法を実現する． 4. 1 設計方針 CARはARCの実装コスト削減を図ったものだが，ルータでの実装には2つの課題が残っている．2.3節で述べたように， CARは性質の異なるアクセスに適応的に振る舞うために可変長のCLOCKを要するが，これに必要なコストはLRU-stackに匹敵する．可変長のCLOCKを実現するためには，針の位置のチャンクの削除と，針の直前(リストの先頭)へのページの挿入が必須である．針はキャッシュメモリ上の任意の場所を指す可能性があるため，メモリ上の任意箇所のチャンクの削除・メモリ上の任意箇所へのチャンクの挿入が必要となる．このLRU-stack と同等の実装コストは，ルータハードウェアに対しては不適である．そこで，本稿では2つのリスト長の総和が一定になることを利用して課題を解決した手法としてCompact CARを提案する．ARC/CARにおいては，T1, T2, B1, B2はリスト長がそれぞれ可変で，L1= T1∪ B1, L2= T2∪ B2のリスト長も可変である．しかし，T1∪ T2, B1∪ B2は必ず最大長がキャッシュサイズc以下に収まり，キャッシュが満杯の状況では常にcと等しくなる．したがって，T∗= T1∪ T2, B∗= B1∪ B2と表記すると，長さcの連続メモリ領域上にT∗とB∗をそれぞれ配置し，チャンクの挿入・削除処理を工夫すれば，固定メモリ領域上で低オーバーヘッドなCARを実現することができると考えられる．このようなチャンク挿入・削除処理を実現した方式として，

(5)

𝑎1 𝑎2 ⋯ 𝑎𝑖 ⋯ 𝑎𝑛 𝑏𝑐−𝑛 ⋯ 𝑏𝑗 reference-bit (R-bit) 𝑻𝟏( 𝑇1= 𝑛) 0 0 1 0 1 0 0 𝑎1 𝑎3 𝑎𝑖−1 𝑎𝑛 _𝑎 2 ⋯ ⋯ 𝑏1 ⋯ 𝑥1 ⋯ 𝑥𝑘 ⋯ 𝑥𝑚 𝑦𝑐−𝑚 ⋯ 𝑦𝑙 ⋯ 𝑦1 𝑻𝟐( 𝑇2= 𝑐 − 𝑛) 𝑩𝟏( 𝐵1= 𝑚) 𝑩𝟐( 𝐵2= 𝑐 − 𝑚) 𝑎𝑖 1 0 0 1 0 1 0 0 𝑏1 𝑏3 𝑏𝑗−1 𝑏𝑐−𝑛 _𝑏 2 ⋯ ⋯ 𝑏𝑗 1 𝑥1 𝑥3 𝑥𝑘−1 𝑥𝑚 _𝑥 2 ⋯ 𝑥𝑘 𝑦1 𝑦3 𝑦𝑙−1 𝑦𝑐−𝑚 𝑦2 ⋯ 𝑦𝑙

図 1 Compact CAR(境界ページ移動方式による ARC の改善案) の概略図 𝑎1 𝑎2 ⋯ 𝒂𝒊 ⋯ 𝒂𝒏 𝑏𝑐−𝑛 ⋯ 𝑏𝑗 𝑻𝟏( 𝑇1= 𝑛) 0 0 1 0 1 0 0 𝑎1 𝑎3 𝑎𝑖−1 𝒂𝒏 𝑎2 ⋯ ⋯ 𝑏1 ⋯ 𝑻𝟐( 𝑇2= 𝑐 − 𝑛) 𝒂𝒊 1 0 0 1 0 1 0 0 𝑏1 𝑏3 𝑏𝑗−1 𝑏𝑐−𝑛 𝑏2 ⋯ ⋯ 𝑏𝑗 1 𝑎1 ⋯ 𝒂𝒏 ⋯ 𝒂𝒊 𝑏𝑐−𝑛 ⋯ 𝑏𝑗 𝑻𝟏( 𝑇1= 𝑛 − 1) 0 0 1 0 1 0 0 𝑎1 𝑎3 𝑎𝑖−1 𝒂𝒏 𝑎𝑛−1 𝑎2 ⋯ ⋯ 𝑏1 ⋯ 𝑻𝟐( 𝑇2= 𝑐 − 𝑛 + 1) 1 0 0 1 0 0 0 1 𝑏1 𝑏3 𝑏𝑗−1 𝑏2 ⋯ ⋯ 𝑏𝑗 1 𝒂𝒊 +1 𝑎𝑛−1 図 2 境界ページの移動方法の概略図 (T1から T2へページ akを移動)

Algorithm 1Dual-bit/Compact CAR Replacement Algorithm

1: procedureCACHEREPLACEMENT(x) ▷ x is an accessed chunk.

2: if x∈ T∗then ▷ cache hit

3: x.R-bit← 1

4: return

5: else if x∈ B∗then ▷ ghost hit

6: i← 2 ▷ to cache x in T2 7: if x∈ B1then 8: δ← max(1,|B2| |B1|); p← min(c, p + δ) 9: DiscardBtm(1,x) 10: else ▷ x∈ B2 11: δ← max(1,|B1| |B2|); p← max(0, p − δ) 12: DiscardBtm(2,x) 13: end if

14: else ▷ cache miss

15: i← 1 ▷ to cache x in T1

16: if Full(L1) & |B1| > 0 then ReplaceBtm(1)

17: else if Full(L) & |B2| > 0 then ReplaceBtm(2)

18: end if 19: end if

20: if Full(T∗) then

21: if|T1| >= max(p, 1) then st← ReplaceTop(1)

22: else st← ReplaceTop(2)

23: end if

24: else ▷ T_∗is not full. 25: st← a free address in Ti

26: end if

27: Ti[st]← x ▷ x is cached as a chunk in Ti.

28: end procedure

Algorithm 2DiscardBtm() for Compact CAR

1: procedureDISCARDBTM(i, x) 2: Swap(x, Bi.EdgeChunk)

3: Discard x (at the edge of Bi)

4: ▷ an address next to the edge of Biis ensured to be free.

5: end procedure

Compact CARを提案する．

4. 2 Compact CARの概要

Compact CARでは，図1のようにT1とT2，B1とB2をそ

Algorithm 3ReplaceBtm() for Compact CAR

1: procedureREPLACEBTM(i)

2: Swap(Bi[HandBi], Bi.EdgeChunk)

3: Discard Bi.EdgeChunk

4: Rotate HandBi

5: ▷ an address next to the edge of Biis ensured to be free.

6: end procedure

Algorithm 4ReplaceTop() for Compact CAR

1: functionREPLACETOP(i) 2: while Ti[HandTi].R-bit= 1 do

3: Ti[HandTi].R-bit← 0

4: ifi=1 then

5: Swap(Ti[HandTi], Ti.EdgeChunk)

6: ▷ Shift the boundary between T1and T2.

7: end if 8: Rotate HandTi

9: end while

10: se← an address next to the edge of Bi

11: Bi[se]← Ti[HandTi]

12: Swap(Ti[HandTi], Ti.EdgeChunk)

13: Discard Ti.EdgeChunk 14: Rotate HandTi 15: return Ti.EdgeAddr 16: end function れぞれメモリ上の連続な位置に配置する．T1は領域の一端，T2 はもう一端からそれぞれ逆方向に針が進むCLOCKとして動作する．B1とB2も，Rビットが不要なだけで同様である．それぞれが独立したCLOCKとして動作するため，単純なページの置換処理は通常のCLOCKと同様に低オーバーヘッドかつ高速に実行できる．問題はリストの大きさが変化するような場合であるが，各リスト間の境界位置のページと交換することでLRU-stackに見られるシフト処理を廃する．図2は，キャッシュがいっぱいの場合に，T1 = (a1, a2,· · · , an)からT2 = (b1, b2,· · · , bc−n) へ，ページakを移動する場合の例を示している．LRU-stack であれば，ここでakをT2 の針の位置に挿入するために， (bj+1,· · · , bc−n)のチャンクを左にシフトコピーしなければならない．その代わりに，Compact CARではakとanの位置を交換し，リストの境界を1チャンク分だけ移動する．結果として，交換後はT1 = (a1,· · · ak−1, an, ak+1· · · , an−1),および T2= (b1, b2,· · · , bc−n, ak)となり，T1内のチャンクをT2に移動することができる．このように，厳密なLRU順序を犠牲にするものの，単純なチャンクの交換でそれぞれのリストの大きさを変更することができる． 4. 3 アルゴリズム Compact CARの具体的なアルゴリズムはアルゴリズム1，2， 3，4に示す．アルゴリズム1では，Compact CARの全体の戦略，つまり，必要なリストの空き領域を確保してから適切な位置へキャッシュ情報を移動する方法を示している．まず，キャッシュヒットした場合はRビットを1に設定して終了する(2–4 行目)．キャッシュミスした場合は，5–19行目でB∗の空き領域を確保する．ghost hit時(5–13行目)には，パラメータpの値を調整して，ghost hitした領域を元に空き領域を決定する．パラメータpはARCの有用な特徴の一つで，リストT1の目標

(6)

サイズとして定義され，pの値をヒット状況に応じて動的に変化させることでアクセスパターンの変化に適切に対応でき，他の方式のように静的なパラメータを事前に調整する必要がなくなる．完全にキャッシュミスした場合(14–19行目)は，B∗に空きがなければB1またはB2の履歴情報を置換し，空き領域を確保する．そうでなければ，パラメータpに従って任意の空き領域を取得する．実質的にはこの処理はリストの終端のアドレスを取得するだけで済む．つぎに，20–26行目でキャッシュ置換処理を行う．置換されたキャッシュの履歴情報をB_∗に確保した領域に記憶しつつ，T_∗の空き領域stを確保する．最後に， 27行目でstにキャッシュを行う．アルゴリズム2，3，4は，それぞれ空き領域を確保するための処理である．HandTiはリストTiの針の位置を示しており， Ti[HandTi]はその針が指し示す領域を表す(Biについても同様)．どの関数でも最終的に空き領域はリストの境界上に確保され，境界上に無いチャンク情報は必ずリスト端部のチャンク情報(アルゴリズム中のEdgeChunk)と交換される．この理由は，例えばT∗に空き領域がある場合にGhost hitした場合など，確保した空き領域が後続の処理で埋められないせいでリストの連続性が失われることを防ぐためである．端部チャンクはB1と B2の境界線に最も近いBiのチャンクであり，CLOCKの針の位置とは無関係にリスト端部のチャンクを取得する．これは端部チャンクであって境界チャンクではない点に注意する．なぜなら，キャッシュに空き容量がある場合，B1とB2の間には空き領域が存在し，端部チャンクはリストの境界とならないからである． DiscardBtm関数(アルゴリズム2)はリストBi中のチャンクxの履歴情報を削除する処理で，Ghost hit時に実行される． ReplaceBtm関数(アルゴリズム3)はリストBiの針が指し示す履歴情報を削除する処理で，キャッシュミス時にB∗が満杯ならば実行される．ReplaceTop関数(アルゴリズム4)はリスト Tiの針が指し示すチャンクを削除する処理で，T∗が満杯の場合に空き領域を確保するために実行される．置換対象がT1中のチャンクの場合，Rビットが1のページは図2で示した方法でT2に移動される．置換されたチャンクは履歴情報として対応する履歴リストに記憶されるが，この記憶先はその履歴リストの端部チャンクに隣接する領域のアドレスであり，事前の処理によって必ず空き領域となっている．B∗に空き領域が存在した場合は当然リスト端部の隣接アドレスも空いているはずであり，B∗が満杯の場合はDiscardBtmまたはReplaceBtm関数の実行時にリストB1とB2の境界上に空き領域が確保されているため，どちらのリストから見てもリスト端部に隣接する領域は解放済みとなっている．

5. シミュレーション評価

5. 1 概要 Compact CARの性能を単純な手法と比較して，十分に高い性能を発揮できることを示す．評価にはコンテンツのアクセス頻度がZipf分布に従うように人工的に生成した入力列と，阪大キャンパス内部から外部動画サイトへのアクセスに基いて生成図 3 阪大の動画アクセス回数の分布された入力列の2種類を用い，コンテンツ単位とチャンク単位のアクセスそれぞれの場合についてキャッシュヒット率の評価を行う． 5. 2 シミュレーション設定 5. 2. 1 アクセス列シミュレーションに用いる入力列には，Zipf分布に従うものと，実トラフィックとして阪大のキャンパス内から外部の動画サイトへのアクセス情報に基いて生成されたものの2種類を用いる．以降，前者をAZipf(α)，後者をAActualと呼称する．ネットワークコンテンツへのアクセスは一般的にZipf分布に従うと言われており，提案手法の幅広い状況下における有効性を実証するためにA_Zipf(α)のαを変えてシミュレーションを行う．更に，実トラフィックに対する有効性を実証するために，それに近いAActualを用いてキャッシュヒット率を評価する． Zipf 則とは，コンテンツの人気順位 r の関数 f (r) = cα_/rα (c, α は定数)によってその順位のコンテンツのアクセス回数が近似できることを指す．[21]の人気度分布に関する議論によれば，αは0.5から1.2までの値を取るため，今回は α = 0.6, 0.8, 1.0, 1.2の4通りの場合についてシミュレーションを行った．アクセス数は後述のAActualと同様に10 7_個程度に設定した．

実トレースデータは，YouTube, nicovideo, dailymotionの3つの動画サイトに対する，2013年7月26日から2015年2月26日までのアクセスに基づく．ユニークコンテンツ数は2,428,880個， 2回以上アクセスのあるコンテンツ数はその約半数の918,545 個である．この約1年半の間の全体のアクセス数は13,004,868 アクセスである．アクセス分布は図3のようになっており，Zipf 分布に近い形で，人気が高いコンテンツへの集中が多いことが確認できる．実際，最もアクセスされたコンテンツのアクセス数は149,820回である．これらのアクセス列はコンテンツ単位でのアクセスだが，そこからチャンク単位での入力列も生成した．具体的には，アクセス日時と動画情報を利用し，動画の長さと対応画質の情報から動画サイズを決定して，予め決定したサイズのチャンクが再生時間を等分割した時間間隔で要求されるようなアクセス列を想定する．チャンクサイズLは1500B・1.5KB・60KBを対象とする．また，動画長1分あたりの通信量は，簡単な事前調査の結果，表1の規則に従って動画ごとのチャンク数を決

(7)

表 1 動画の秒あたりパケット数 [pck/sec] チャンクサイズ 1.5KB 15KB 60KB SD(4.5[MB/min]) 50 5 1.25 HD(9.0[MB/min]) 100 10 2.50 定した．AZipf(α)に関しては，観測された動画の再生時間と画質の分布に従って，コンテンツごとに再生時間と画質を決定した．しかし，チャンク単位のアクセスは膨大な量となってシミュレーションの実行が困難であるため，107_{個程度の長さに} 収まるように一部分のみを対象としてチャンク単位のアクセス列を切り出した．AActualについては，キャッシュの効果を考慮してアクセスの集中する時間帯を対象とし，2013年7月 29日のトラフィックについて，チャンクサイズ1.5KBに関しては12:01から12:10まで(約9分間)，15KBの場合に関しては13:02から14:08まで(約66分間)，60KBの場合に関しては前日の19:57から14:45まで(約19時間)を対象とした．以降，コンテンツ単位のアクセス列と区別するために，コンテンツ単位のアクセス列はAC Zipf(α)とA C Actual，チャンク単位のアクセス列はAP =LKB Zipf(α) とA P =LKB Actual のように表記する． 5. 2. 2 対象方式評価対象とするキャッシング手法は提案手法の他に，OPT,

FIFO, CLOCK, CARを用いる．OPTは最適手法であり，同一

キャッシュサイズで実現可能なキャッシュヒット率の上限値が分かる．それ以外はルータハードウェア実装が実現可能な高速な方式のみを対象としている．FIFOとCLOCKは単純な手法であり，提案手法が単純な手法と比較してどれほど改善できているかの基準とする．CARは提案手法の基とした既存手法であり，提案手法がCARよりも性能が悪くないことを示せるのが望ましい． 5. 2. 3 環境設定ネットワークトポロジーは単一ノードの場合と単純なトポロジーの場合の2通りを考える．単一ノードとは，コンテンツ供給元とユーザが単一のルータでつながっている場合であり，キャッシュ置換手法の純粋な性能を確認できる．単純なトポロジーとしては，10個のルータがコンテンツ供給元とユーザを繋ぐ直線上のトポロジーを想定し，キャッシュ判断方式にはCE2 を採用する．評価指標にはキャッシュヒット率を採用する．これは，ユーザの要求全体(ルータへのアクセス数全体ではない)に対するそのルータでのキャッシュヒット数の割合である．アクセス列の長さを107程度に抑えているため，キャッシュサイズCは101 から106_[Chunks]_の 6通りとする．コンテンツのサイズは考慮せず，チャンク数に対するキャッシュヒット率を考える． 5. 3 評価結果 5. 3. 1 人工的に生成したトラフィックAZipf(α)に基づく評価まず，Zipf則に基づき人工的に生成したトラフィックの評価結果を示す．図4，5，6，7は，単一ルータで，要求がコンテンツ単位の場合の評価結果である．4通りのαの値ごとに，AC Zipf(0.6) は図4，ACZipf(0.8)は図5，A C Zipf(1.0)は図6，A C Zipf(1.2)は図7 に結果が示されている．また，チャンク単位で要求が行われた場合の評価結果の一例として，α = 1.0の場合を図8，9，10に示す．全体の傾向としては，最も注目すべき点として，提案手法が

CARに匹敵する性能を示している．Compact CARはLRU順序

の不整合による性能の劣化が予想されたが，最大でも0.5%以下の差しか見られなかった．これらのCAR系の手法は一様に高い性能を示しており，良い場合には同一のキャッシュヒット率を達成するためにCLOCKやFIFOの1/10以下で済む．OPT

との差についても，ほぼすべての場合で10%以下に抑えられている．αが大きいほどキャッシュヒット率が高く，紙面の制限上記載していないがチャンク単位のキャッシングでも同じ傾向が見られる．チャンク単位でのキャッシュでは，チャンクサイズが小さいほどコンテンツが多数のチャンクに分割される影響が大きく，キャッシュヒット率が大幅に低下する． 5. 3. 2 実トラフィックAActualに基づく評価次に，実トラフィックに基づくトラフィックの評価結果を示す．単一ルータの場合の評価結果は，コンテンツ単位の結果を図11に，パケット単位の結果を図12，13，14に示している． AC Actualの結果は，OPTを除く手法間で差が出ていない．特に，CAR系の手法が単純な手法より優れているものの差は小さい．これは,トレースデータのアクセスの局所性の高さに起因すると考えられる。人気のコンテンツに対する要求間隔が短い値に集中するために、単純な手法でもCARに匹敵する性能を示したと考えられる。実際にAP =1.5KB Actual では104付近でキャッシュヒット率が急上昇しており、チャンク分割によって要求間隔が引き伸ばされたものと考えられる。トレースデータは動画サイトへのアクセスのみを抽出しているため、多様なアプリケーションへの要求を扱う現実のルータでは局所性は低くなり、 CARと単純な手法の性能差は大きくなることが予想される。また，AP =LKB Actual の結果では，CAR系の手法が単純な手法に大きく勝っている．チャンク単位でのアクセスでは同一チャンク間のアクセス数が増加して局所性が低下した結果，FIFOや CLOCKの性能が低下したと推測される．一方，CAR系の手法は高いヒット率を示しており，特にAP =1.5KB Actual とAP =15KBActual ではOPTに近い性能を達成している．注意点として，AP =1.5KB Actual からAP =60KBActual にかけて，チャンクサイズが小さくなっているにも関わらずキャッシュヒット率が低下する傾向が見られるが，これはアクセスの集中度合いが時間帯によって大きく変化するためである． 5. 3. 3 複数ルータの場合の評価直線状トポロジーでの評価結果の一部として, ACZipf(α)の一例を図15に, AP =LKBZipf(α) の評価結果の一部を図17, 18に示す。また,AP =15KBActual の結果を図20に示している。グラフの横軸は,左端がネットワーク全体のキャッシュヒット率を示しており,以降は1番目から10番目まで要求者に近いルータから順番にアクセス全体に対するヒット数の割合を示している。全体で96通りの試行を行ったが,そのすべてで記載されている結果とほぼ同じ傾向が見られた。結果としては,CLOCKやFIFOが2番目以降のルータではキャッシュヒット率がほぼ0であるのに対して,提案手法を含むCAR系の手法は2番目以降のルータでも少

(8)

0 0.1 0.2 0.3 0.4 0.5 0.6 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 4 AC Zipf(0.6) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 5 AC Zipf(0.8) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 6 AC Zipf(1.0) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 7 AC Zipf(1.2) 0 0.1 0.2 0.3 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 8 AP =1.5KB Zipf(1.0) 0 0.1 0.2 0.3 0.4 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 9 AP =15KB Zipf(1.0) 0 0.1 0.2 0.3 0.4 0.5 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 10 AP =60KB Zipf(1.0) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 11 AC Actual 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 12 AP =1.5KB Actual 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 13 AP =15KB Actual 0 0.1 0.2 0.3 0.4 0.5 0.6 101 102 103 104 105 106

Cache hit rate

Cache size [Chunks] OPT FIFO CLOCK CAR Compact CAR 図 14 AP =60KB Actual 0 0.1 0.2 0.3 0.4 0.5 total 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th

# of Hits / # of total accesses

Node FIFO CLOCK CAR RepelCAR 図 15 AC Zipf(0.8) (c = 105_[Chunks]) 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 total 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th

Node FIFO CLOCK CAR RepelCAR 図 16 AP =60KB Zipf(1.2) (c = 103_[Chunks]) 0 0.05 0.1 0.15 0.2 0.25 0.3 total 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th

Node FIFO CLOCK CAR RepelCAR 図 19 AC Actual (C = 103_[Chunks]) 0 0.05 0.1 0.15 0.2 0.25 total 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th

Node FIFO CLOCK CAR RepelCAR 図 20 AP =15KB Actual (C = 103_[Chunks]) 量ながら全体のキャッシュヒット率向上に貢献している。

6. 考

察

6. 1 単純な手法からの改善 CARは単純な手法よりも性能が優れており，CARの近似手法である提案手法はCARとほとんど同等の性能を示した．特に，低オーバーヘッド化のためにLRUの順序を崩したCompact CARでこのような結果が得られたのは理想的と言える．提案手法を用いることで同一の性能を達成するために必要なキャッシュサイズを削減することができ，FIFOやCLOCKと比較してキャッシュ資源の利用効率を10倍程度に高めることができる．ほぼすべての場合でOPTとの差は10%以下に抑えられているが，A_Zipf(α)の評価結果から分かるように，αの値が低い，

(9)

つまり人気度の偏りが低いほどOPTとの差が大きい傾向がある．現実のトラフィックは様々なアプリケーションの重畳効果によって人気度の偏りが引き伸ばされていくことが想定されるため，キャッシュ置換アルゴリズムの更なる改良には大きな価値があるだろう．しかし，OPTとの差は依然として存在している．今回の評価結果から，アクセスの局所性の多様化が性能の悪化原因と予想されるため，それに対処可能なキャッシュ置換手法が期待される．また，CARはloopに弱い手法であるが，チャンク単位の連続アクセスが直感的にloopを形成しやすいことから，loop への対処が可能な手法について検討すべきと考えられる． 6. 2 ルータの実現可能性ネットワークトラフィックをキャッシュする場合，キャッシュ容量とアクセス速度の制約が課題となる．無差別にキャッシュを行う場合，ルータは自身が送信した全Dataパケットをキャッシュする．例えば，10Gbpsのトラフィックを扱うラインカードは1秒間で最大1.25GBをキャッシュする必要がある．また， Dataパケットサイズが64Bだと仮定すると，最大で約20MSPS の処理速度が必要である．更に，複数のラインカードのトラフィックを収容するルータ単位では，ラインカード数に比例した性能を確保しなければならない．現実的には，Interestパケットの存在とキャッシュヒットの発生によってこの時間は数十% 程度延長されうると考えられるが，倍以上の改善のためにはキャッシュ判断方式の併用が必要だろう．提案するアルゴリズムはCLOCKと同等の低オーバーヘッドを実現している．記憶容量のオーバーヘッドはエントリあたり 1bit以下であり，上述の20MSPSに合わせて2000万個のエントリをキャッシュするとした場合，キャッシュへのポインタとして24bitずつ保持するとしても，容量は63MB以下に抑えられ

る．高速だが集積化困難なSRAMでも2.3Gbit(8× 288Mbit)を確保可能であり，ラインカード4枚まではルータで集中管理できる．また，SRAMのアクセス時間が0.45nsとすると[22]，最悪時に数回程度針の回転が必要だとしても，ラインカード4枚程度であれば十分収容可能と推測される．しかし，キャッシュデータ自体はDRAMやSSDなどの低速なメモリに記憶しなければならない．その読み書きの高速性を保証するために，メモリの並列化や処理のパイプライン化，メモリ速度に応じた階層キャッシングなども考察する予定である．最終的には，FPGA を用いた実機評価を視野に，名前検索機構[6]などと組み合わせることを考慮しつつ，記憶装置を含むキャッシュアルゴリズムのハードウェア実装のための最適化を行い，キャッシュ機構およびルータ全体でのハードウェア実装コストおよび達成可能な性能を示すことで，ICNルータの実現可能性の実証に貢献したい．

7. 結

論

ICNにおいては実現可能なICNルータの設計が急務であるが，CSにおいて用いるキャッシング手法について，効果的で低コストな手法はまだ無い．従来研究されてきたWebキャッシングの多くはソフトウェアレベルでの動作を想定していてルータでの実現は困難であり，同様にICNの特徴を活かしてコンテンツごとの統計を取る手法もオーバーヘッドが大きすぎる．本研究では，ネットワーク中を流れるコンテンツのほとんどは1度しかアクセスされないコンテンツであることに注目し，ワンタイマーコンテンツを避ける有望な手法としてCAR [17]に注目した．CARの動作をCLOCKと同等なレベルに置き換え，更に固定メモリ領域で動作可能なキャッシング手法を提案することで，ワンタイマーコンテンツに耐性を持つ低オーバーヘッドなキャッシュ置換手法の実現を目指した．可変長のCLOCKをどのようにして低コストに実装するかが主な実装課題だが，リスト長の相補性に注目して可変長の動作を無くし，管理・運用コストを最小限に抑える手法Compact CARを提案した．Compact CARは連続したメモリ領域を明確に二分して，両端ごとに別々のCLOCKを割り当てることで， CLOCKごとのメモリ領域の連続性を維持させる．キャッシュが溢れた場合は境界線上のエントリを置換することで，領域端から境界線上までのキャッシュエントリ連続性を保持する．ただし，メモリの境界線上のエントリの置換というLRUの特徴を無視した置換によって，性能が大きく変化する可能性があった．評価の結果，提案手法はCARと同等の性能を示すという理想的な結果が確認され，単純な手法と比較して同一の性能を達成するために必要なキャッシュ容量が1/10で済む場合があることが判明した．改善の余地は見られるものの，提案手法が低オーバーヘッドかつ高性能であることを示し，ICNルータの実現可能性の実証に貢献した．今後は，ルータ間の協調を考慮に入れたキャッシングアルゴリズムの考案と，実機を用いたキャッシングアルゴリズムの実装および評価が研究課題となる．謝辞本研究成果の一部は総務省・戦略的情報通信研究開発推進制度（SCOPE）の支援による．文献

[1] V. Jacobson, D.K. Smetters, J.D. Thornton, M.F. Plass, N.H. Briggs, and R.L. Braynard, “Networking named content,” Proceedings of the ACM CoNEXT 2009, pp.1–12, Dec. 2009.

[2] L. Zhang, D. Estrin, J. Burke, V. Jacobson, J.D. Thornton, D.K. Smetters, B. Zhang, G. Tsudik, K. Claffy, D. Krioukov, D. Massey, C. Papadopoulos, T. Abdelzaher, L. Wang, P. Crowley, and E. Yeh, “Named data networking (NDN) project,” Oct. 2010.http: //named-data.net/techreport/TR001ndn-proj.pdf

[3] , “CCNx,” 2014.http://www.ccnx.org/

[4] N. Fotiou, P. Nikander, D. Trossen, and G.C. Polyzos, “Developing information networking further: From PSIRP to PURSUIT,” Pro-ceedings of the 7th International ICST Conference on Broadband Communications,Networks, and Systems, pp.1–13, Oct. 2010. [5] T. Lev¨a, J. Gonc¸alves, R.J. Ferreira, et al., “Description of project

wide scenarios and use cases,” Feb. 2011.http://www.sail-project. eu/wp-content/uploads/2011/02/SAIL D21 Project wide Scenarios and Use cases Public Final.pdf

[6] K.I. Atsushi Ooka, Shingo Ata and M. Murata, “High-speed design of conflict-less name lookup and efficient selective cache on CCN router,” IEICE Transactions on Communications, vol.E98-B, no.04, pp.607–620, April 2015.

[7] F. Guillemin, B. Kauffmann, S. Moteau, and A. Simonian, “Exper-imental analysis of caching efficiency for YouTube traffic in an ISP network,” Proceedings of the 25th International Teletraffic Congress, pp.1–9, Sept. 2013.

(10)

[8] S.K. Fayazbakhsh, Y. Lin, A. Tootoonchian, A. Ghodsi, T. Koponen, B. Maggs, K.C. Ng, V. Sekar, and S. Shenker, “Less pain, most of the gain: Incrementally deployable ICN,” ACM SIGCOMM Com-puter Communication Review, vol.43, no.4, pp.147–158, Aug. 2013. [9] S. Arianfar, P. Nikander, and J. Ott, “On content-centric router de-sign and implications,” Proceedings of the ACM Re-Architecting the Internet Workshop, pp.1–6, Nov. 2010.

[10] W.K. Chai，D. He，I. Psaras, and G. Pavlou, “Cache “ less for more ” in information-centric networks,” Computer Communica-tions，vol.36，no.7，pp.758–770，2013．

[11] D. Rossi and G. Rossini, “Caching performance of content centric networks under multi-path routing (and more),” Technical report, Telecom ParisTech, July 2011.

[12] A. Ioannou and S. Weber, “A taxonomy of caching approaches in information-centric network architectures,” Technical report, School of Computer Science and Statistics, Trinity College Dublin, Jan. 2015.

[13] L. Wang, S. Bayhan, and J. Kangasharju, “Optimal chunking and partial caching in information-centric networks,” Computer Commu-nications, vol.61, no.1, pp.48–57, May 2015.

[14] N. Megiddo and D.S. Modha, “ARC: a self-tuning, low overhead re-placement cache,” Proceedings of the 2Nd USENIX Conference on File and Storage Technologies, pp.115–130, March 2003.

[15] S. Jiang and X. Zhang, “Making LRU friendly to weak locality work-loads: a novel replacement algorithm to improve buffer cache perfor-mance,” IEEE Transactions on Computers, vol.54, no.8, pp.939–952, Aug. 2005.

[16] S. Arianfar, P. Nikander, and J. Ott, “Packet-level caching for information-centric networking,” Technical report, Finnish ICT SHOK, June 2010.

[17] S. Bansal and D.S. Modha, “CAR: Clock with adaptive replacement,” Proceedings of the 3rd USENIX Conference on File and Storage Technologies, pp.187–200, March 2004.

[18] S. Jiang, F. Chen, and X. Zhang, “CLOCK-Pro: An effective im-provement of the CLOCK replacement,” Proceedings of the USENIX 2005, pp.323–336, April 2005.

[19] J. Ran, N. Lv, D. Zhang, Y. Ma, and Z. Xie, “On performance of cache policies in named data networking,” Proceedings of the Inter-national Conference on Advanced Computer Science and Electronics Information 2013, pp.668–671, July 2013.

[20] A. Jaleel, K.B. Theobald, S.C. Steely, Jr., and J. Emer, “High per-formance cache replacement using re-reference interval prediction (RRIP),” ACM SIGARCH Computer Architecture News, vol.38, no.3, pp.60–71, June 2010.

[21] C. Fricker, P. Robert, J. Roberts, and N. Sbihi, “Impact of traffic mix on caching performance in a content-centric network,” Proceed-ings of the IEEE Conference on Computer Communications 2012, pp.310–315, March 2012.

[22] D. Perino and M. Varvello, “A reality check for Content Centric Networking,” Proceedings of the ACM SIGCOMM workshop on Information-centric networking, pp.44–49, Aug. 2011.

name name IP [6] ICN Zipf 2 5 [7] 2 name 2 CCN 3 ICN Compact CCN 2. ICN ICN name NDN/CCN [], [2] CCN MTU name Interest Data CCN FIB PIT CS 3 CS

情報指向ネットワークルータにおける実装を考慮したキャッシュ置換方式

の提案と評価

大岡

睦

阿多 信吾

村田 正幸

†

大阪大学 大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5

††

大阪市立大学 大学院工学研究科〒 558-8585 大阪府大阪市住吉区杉本 3-3-138

E-mail:

†{

a-ooka,murata

}

@ist.osaka-u.ac.jp,

††

ata@info.eng.osaka-cu.ac.jp

あらまし 情報指向ネットワーク (ICN) におけるルータキャッシング技術の実現には，ルータハードウェア実装を考慮

した低オーバーヘッドかつ高キャッシュヒット率を達成可能なキャッシュ置換手法が必要不可欠である．しかし，既存

のキャッシング手法は極めて単純な手法を採用するか，キャッシュ性能向上のために実装不可能なオーバーヘッドを要

するものばかりである．本研究では CAR を参考にして以上の要件を満たすキャッシュ置換手法として Compact CAR

を提案し，単純な手法と同じ性能が 1/10 のキャッシュサイズで達成可能ば場合があることをシミュレーション評価に

よって示す．

キーワード 新世代ネットワーク，情報指向ネットワーク (ICN)，コンテンツセントリックネットワーク (CCN)，キャッ

シング，キャッシュ置換方式

A Proposal and Evaluation of Cache Replacement Policy for the

Implementation of ICN Router

Atsushi OOKA

, Shingo ATA

, and Masayuki MURATA

†

Graduate School of Information Science and Technology, Osaka University

1-5 Yamadaoka, Suita, Osaka, 565-0871, Japan

††

Graduate School of Engineering, Osaka City University

3-3-138 Sugimoto, Sumiyoshi-ku, Osaka-shi, Osaka 558-8585, Japan

E-mail:

†{

a-ooka,murata

}

@ist.osaka-u.ac.jp,

††

ata@info.eng.osaka-cu.ac.jp

Abstract

Information-centric networking (ICN) requires an innovative cache replacement algorithm with performance far

superior to simple policies such as FIFO and computational and memory overheads that are low enough to run on ICN router’s

hardware. We focus on CAR as the suitable policy for an access pattern of workload on the router and propose the cache

replacement policy (called Compact CAR) that satisfies the requirements. We also evaluate our proposed approach and show

that the size of cache memory required to achieve a certain performance can be reduced to 1/10th of that of the simple policy.

Key words

Future Networks, Information-Centric Networking, Content-Centric Networking, Caching, Cache Replacement

Policy

1.

は じ め に

2.

関 連 研 究

3.

背

景

4.

提案方式の設計

5.

シミュレーション評価

6.

考

察

7.

結

論

阿多信吾

村田正幸

大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5

大阪市立大学大学院工学研究科〒 558-8585 大阪府大阪市住吉区杉本 3-3-138

あらまし情報指向ネットワーク (ICN) におけるルータキャッシング技術の実現には，ルータハードウェア実装を考慮

キーワード新世代ネットワーク，情報指向ネットワーク (ICN)，コンテンツセントリックネットワーク (CCN)，キャッ

はじめに

関連研究