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

情報指向ネットワークルータにおける実装を考慮したキャッシュ置換方式
の提案と評価
大岡
睦†
阿多
信吾††
村田
正幸†
† 大阪大学 大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5
†† 大阪市立大学 大学院工学研究科〒 558-8585 大阪府大阪市住吉区杉本 3-3-138
E-mail: †{a-ooka,murata}@ist.osaka-u.ac.jp, ††[email protected]
あらまし 情報指向ネットワーク (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, ††[email protected]
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. は じ め に
トが端末間通信に焦点を当てて端末の在処に対してアドレス
を割り振るのに対して，ICN では，現在の利用形態に即して，
現在のインターネットが直面する課題を解決する将来イン
IP アドレスの代わりにコンテンツごとに name と呼ばれる識
ターネットとして Information-Centric Networking (ICN) が注目
別子を割り当て，情報とユーザを結びつける．その有望性か
されている．現在のインターネットはトラフィック量の急増，
ら，NDN/CCN [1]∼[3], PSIRP/PURSUIT [4], SAIL/NetInf [5] な
携帯端末普及によるネットワーク接続機器数の爆発的増加，高
ど，世界的に多数のプロジェクトが存在している．
度なアプリケーションのための品質・セキュリティ・頑強性の
しかし，ICN は未だに開発初期段階にあり，課題は山積して
要請など，様々な問題に直面している．これらの問題を個々に
いる．ICN は clean-slate なアーキテクチャであり，厳密なプロ
解決するのではなく，ネットワークアーキテクチャから根本的
トコルとそれをサポートするデバイスは策定段階にある．従来
な改革を図る試みとして ICN が注目されている．インターネッ
の IP アドレスとは異なり，name アドレスは位置を指定するも
—1—
のではないため，情報とその所在を結びつけるルーティングと
の細部はプロジェクトごとに異なるが，本稿は NDN/CCN [1], [2]
フォワーディングが必要である．name アドレスは中継ルータ
に基づく．CCN ではコンテンツごとに自然言語で書かれた覚え
におけるキャッシングを可能にするが，限られた資源でネット
やすいユニークな識別子が割り当てられる．MTU を超えるよ
ワーク負荷を大幅に軽減する方策も求められる．また，name ア
うなデータサイズのコンテンツはチャンクに分割され，個々の
ドレスは可変長で IP アドレスよりも長く扱いづらいことが想
チャンクごとに name が割り当てられる．要求者は Interest パ
定されるため，これをハードウェアで高速にサポートする方法
ケットと Data パケットの交換を反復してコンテンツの取得を
についても研究されている [6]．
実現する．また，CCN ルータは FIB，PIT，CS の 3 つのスト
ネットワーク内部のルータにおけるキャッシングは ICN の有
レージを持ち，マルチキャスト，ループフリー，キャッシング
用な特徴であり，活発に研究が行われている．増大の一途を辿
などの特徴を実現する．特に CS は Data パケットのキャッシュ
るネットワークトラフィックは Zipf 則に従うと言われ，多数の
として機能する．Data の自己同一性は name に保証されている
パケットが重複した情報を運ぶ冗長な通信が行われている．観
ため，キャッシュされた Data はその所在や要求時刻に関わらず
測期間によっても値は異なるが，2 回以上アクセスのあるコン
再利用できる．
テンツがトラフィック量に対して占める割合は 5 割を超えると
2. 2 キャッシュ判断方式
いう結果もある [7]．その潜在性からキャッシングに関する研究
ICN の初期設計では全ルータで通過したすべてのコンテン
は多数行われており，ルータがどのコンテンツをキャッシュす
ツをキャッシュする方式 CE 2 (Cache Everything Everywhere) が
べきか，また，ストレージが溢れた際にどのキャッシュを置換
考えられてきた [1], [2], [4], [5]．CE 2 は人気度の偏りが大きい
すべきかを決定する主に 2 つの観点からアルゴリズムが研究さ
ネットワークにおいて要求者から遠いルータの資源が十分に活
れている．
用できないことが指摘されている [8]．ルータごとに一定の確
本稿では，ルータにおけるキャッシング実装の問題を解決する
率 d でキャッシングを行うキャッシュ判断方式 [9] は，単純な方
ために，実用的かつ高いキャッシュヒット率を達成可能なキャッ
式でコンテンツ取得時間を半減できるが，キャッシュ資源の無
シュ置換手法を提案する．ルータでは資源やパケットの処理時
駄が発生する． [10] では，経路上のルータからランダムに 1 つ
間が限られており，キャッシュ置換手法が要求する計算量・メ
選んで確実にキャッシュする方式と，媒介中心性を用いること
モリオーバーヘッドはそれらの制約を満足させるものでなけれ
で効果的なルータを選択してキャッシュする方式を提案・比較
ばならない．しかし，既存研究はキャッシュヒット率を犠牲に
し，少数のルータによるキャッシュ性能向上の可能性を示して
する極めて単純な手法を採用したものや，name アドレスを活
いる． [11] では様々な観点から総合的にキャッシュ性能を評価
用したきめ細やかな統計情報を用いるために実用時間内の処理
しており，Leave Copy Down (LCD) と呼ばれる，キャッシュミ
が不可能な手法を提案するものばかりである．また，過去の計
スの度に高々1 ホップしかキャッシュが下流に伝搬しない低コ
算機領域におけるキャッシング置換手法の研究はプロセス処理
ストな方式でも CE 2 などとの差が僅少であると述べている．
特有のアクセスに特化されており，ネットワークに直接応用で
多くのキャッシュ判断方式が存在する一方で [12]，人気度情報
きるかは明らかではない．そこで，本研究ではルータにおける
を用いた最適な配置にキャッシングを行う手法も考えられてい
実現可能性と，ネットワークにおける高い性能の両立を可能と
る [13]．一般的に最適方式は非現実的だが，実現可能性のある
する手法を提案する．
低オーバーヘッドな方式の性能の妥当性を理解するために重要
本稿の構成は以下のようになる．2 章で，CCN について述
べ，キャッシングの研究の現状について概観する．3 章で，本研
究の背景としてキャッシュに関する知見をまとめ，ICN におけ
である．
2. 3 キャッシュ置換方式
ルータハードウェアにおける実現可能性に着目して，アプリ
る実用的かつ効果的なキャッシュ置換手法とは何かを分析する．
ケーションレベルではなくハードウェアレベルで実装可能な手
その分析に基いて，CAR に基づく低オーバーヘッドかつ高ヒッ
法に焦点を当てる．
ト率な提案手法として，Compact CAR の設計について 4 章に
低オーバーヘッドで性能も低い単純な手法としては，Random
詳述する．5 章の評価結果から，提案手法によって単純な手法
や First-In, First Out (FIFO)，Not Recently Used (NRU) などがあ
と比較して同一のキャッシュヒット率を達成するために 10 の 1
る．Random は，すべてのチャンクを一様の確率で削除する手
以下のメモリ容量で済む場合があることを明らかにする．最後
法である．First-In, First Out (FIFO) は現行の IP ルータのバッ
に，考察と結論をまとめる．
ファでも採用されているデータ構造で，最初にキャッシュされ
2. 関 連 研 究
たチャンクが最初に置換される．Not Recently Used (NRU) は使
用されたチャンクに参照ビット (以下 R ビット) を立て，R ビッ
本章では，キャッシングの既存研究を概観する．最初に CCN
トが 0 のチャンクを優先的に置換する方式である．いずれも性
におけるキャッシングの実現方法を要約し，続いてルータにお
能は一般的に LRU に劣るが，状況によっては LRU と同等以上
けるキャッシュ判断方式と，計算機領域におけるキャッシュ置
の性能を発揮しうる [11]．
換方式についてまとめる．
ハードウェア実装の観点からは高オーバーヘッドだが，性能
2. 1 ICN
向上を目指した代表的な手法には Least Recently Used (LRU)，
ICN では name を用いた新しい通信方式を提供する．通信方式
Adaptive Replacement Cache (ARC) [14]，Low Inter-reference Re—2—
cency Set (LIRS) [15]，Least Frequently Used (LFU) が挙げられ
る．最も代表的な方法である LRU は，参照の局所性を備えた
アクセスに強いが，ネットワークアクセスは局所性が低く，更
である．
3. 背
景
に低オーバーヘッドな実装が困難なため，望ましくない．多数
本章では，ネットワークトラフィックに適した低オーバーヘッ
の ICN のキャッシングの関連研究で Random と並んで採用され
ドなキャッシング手法の設計思想を示す．計算機科学領域の知
ているが，LRU はルータハードウェアでの実現が困難であるこ
見から得られた課題について整理した後，これらの知見をネッ
とが指摘されている [11], [16]．
トワークに適用してネットワークトラフィック特有の問題を解
ARC は LRU と LFU の長所を兼ね揃えており，LRU よりも
決可能かつその特徴を活かすキャッシング手法を議論する．
キャッシュヒット率が高い．ARC は 2 つの LRU リスト L1 と
3. 1 キャッシングの課題
L2 を保持し，それぞれ 1 回だけアクセスされたチャンク，2 回
まず，キャッシュヒット率を悪化させる主要な 4 つのアクセス
以上アクセスされたチャンクを保持する．Ln (n = 1, 2) は上部
パターン [20] として，scan, loop, correlated-reference, frequently-
(Tn ) と下部 (Bn ) に分けられ，recent なものが Tn ，古いものは
shifts について説明する．scan は 1 度しかアクセスされないチャ
Bn に含まれる．Bn は ghost cache という，実際のキャッシュ
ンクの連続的な読み込みである．一般的にはキャッシュサイズを
データは保持せずに履歴情報だけを保持する方式を取る．アク
超える数のユニークチャンクへのアクセスから構成され，LRU
セスの局所性の変化や多様性に対応するため，|T1 ∪ T2 | <
=cか
の性能を大きく悪化させる．特に nS > c のときにはチャンク
つ |L1 ∪ L2 | = |T1 ∪ B1 ∪ T2 ∪ B2 | <
= 2c となるように適応的
にそれぞれのリスト長の調整を行う．複数の LRU リストで実
されているページすべてが一度もキャッシュヒットしないチャ
装されるため，LRU と同等の処理オーバーヘッドで済む．
は，キャッシュサイズを超える長さの scan の繰り返しである．
ンクによって置き換えられるキャッシュ汚染が発生する．loop
LIRS はメモリオーバーヘッドは極めて大きいが LRU と同等
科学計算の膨大な量のデータに対する繰り返し計算で見られる
の複雑性で loop(3.1 節で後述) への耐性を実現している．LFU
パターンで，すべてのチャンクの局所性・アクセス頻度が等し
はチャンクの参照回数に基いてチャンクを置換する．いずれも
いため，基本的な戦略 (LRU, LFU, ARC など) で scan と同様の
LRU 以上のオーバーヘッドが必要であり，ルータレベルでの実
キャッシュ汚染が連続的に発生してしまう．correlated-reference
現は困難である．
は，あるチャンクに対するアクセスが短期間に集中するような
高い性能を維持したままオーバーヘッドを妥当な大きさに抑
アクセスパターンである．これらのチャンクは集中アクセスが
えるために開発された LRU の近似手法として CLOCK が有名
終わるとそれ以降全くアクセスされなくなるという特徴を持ち，
である．CLOCK は前回置換したチャンクの次のアドレスから
LFU などのアクセス頻度に基づく手法は，長期的なキャッシン
R = 0 のページの探索を開始する．探索中に見つかった R = 1
グが不要なチャンクに高い優先度を付与してしまい，キャッシュ
のチャンクは R ビットを 0 にリセットして無視する仕組みによ
する価値のないチャンクが長期間キャッシュに留まるという問
り，最近利用されたチャンクを優先的に保持できる．LRU に匹
題が発生する．frequently-shifts は，アクセスされるチャンク集
敵する性能を発揮でき，1 チャンクあたり 1 ビットだけのメモ
合が頻繁に切り替わるアクセスパターンである．LIRS のよう
リオーバーヘッド，および高々数回の探索コストで実現が可能
に，チャンクの一部を優遇して長期的に保持する手法では，ア
である．
クセス列の切り替わりの際に新しいアクセス列への対応が遅れ
ARC に CLOCK を適用したキャッシング手法として，Clock
てしまい，キャッシュヒット率が低下する．
with Adaptive Replacement (CAR) [17] に本稿では注目する．リ
つぎに，キャッシュにおいて注目すべきオーバーヘッドについ
スト T1 と T2 を CLOCK に変更することで計算量オーバーヘッ
てまとめる．第一にデータ構造の維持管理のための計算量オー
ドを削減しつつ，ARC に匹敵した性能を発揮できる．しかし，
バーヘッドが挙げられる．キャッシュヒット/ミスに応じてデー
B1 と B2 は LRU のままであり，また，T1 と T2 は可変長の
タ構造の整合性を保つためのオーバーヘッドで，LRU における
CLOCK として実装されているので，キャッシュミス時にはキャッ
MRU operation など，キャッシュへのアクセスがある度に負荷
シュリストの任意位置への挿入や削除が必要で，MRU operation
の大きい処理が必要な手法は，高速環境下では実現できない．
と同等の計算量オーバーヘッドが発生する．
逆に，CLOCK や NRU は維持管理コストは制御ビットの変更
CLOCK を適応した高性能な近似手法として，LIRS の近似手
だけで済む．第二に，置換ページを探索するための計算量オー
法 CLOCK-Pro [18] が挙げられ，追加したビットと針のために
バーヘッドが挙げられる．LFU や LRU は優先度キューを実装
CLOCK よりメモリ・計算量オーバーヘッドは大きいが，LRU
すれば，キューの tail を削除するだけでよい．NRU や CLOCK
などと比較すると十分に実現可能な範囲である．しかし，loop
は R ビットが set されたページ数が増えるほど探索回数が増え
への耐性は LIRS に劣る．
る．第三に，制御用の情報を記憶するためのメモリオーバー
ICN における特徴を活かした手法として，チャンクの人気
ヘッドがある．チャンクごとの置換の優先順位を決定するため
度に応じたキャッシングを行う手法も存在する [13], [19]．LRU
の情報を記憶するために必要で，LRU-stack のようにデータ構
や LFU と比較して優れた性能を示すものの，チャンク単位で
造だけで管理が可能な場合を除いて，基本的にはこのオーバー
の人気度の計測と管理が必要であるため，メモリ・計算量オー
ヘッドはキャッシュサイズに従って増大する．NRU や CLOCK
バーヘッド共に高く，ルータハードウェアにおける実装は困難
のような単純な手法は 1 チャンクあたり 1bit で済む．ARC や
—3—
LIRS など，ghost cache を持つ手法は，キャッシュサイズ以上の
報を活用する LFU などの手法をルータで運用するのはメモリ・
オーバーヘッドが必要となる．特に，LFU などの統計情報を用
探索・データ構造管理すべてのオーバーヘッドの観点から困難
いる手法は，維持管理コストも含めて実現が困難である．
である．ARC や LIRS を始めとして，多くのキャッシング手法
3. 2 ICN におけるキャッシング
は LRU 相当のオーバーヘッドを目指して設計されているが，
前節で議論した計算機領域のキャッシングに関する知見に基
LRU はハードウェア実装においてはオーバーヘッドが大きす
いて，ICN におけるキャッシング手法を考察する．
まずアクセスパターンに関して，計算機領域とネットワーク
ぎる．CLOCK は低オーバーヘッドなメモリ管理方式として実
績がある点が注目されており [17], [18]，本稿でもデータ構造管
領域では 3 つの点で大きく異なる．1 点目はアクセスの同時性
理と探索コストが抑えられる手法として CLOCK を採用する．
で，計算機領域は単一プロセスのページアクセスを対象とした
NRU は探索コストが不要に大きくなる可能性があり，性能も
のに対して，ルータは多数のユーザからの要求を同時並列的に
CLOCK に劣る．
受け付ける．多数同時アクセスによって，scan や loop といっ
CLOCK と同等の低オーバーヘッドかつネットワークトラ
たアクセスパターンは変則的になる．例えば，多数のユーザか
フィックに適したアルゴリズムの候補としては，CLOCK-Pro と
ら独立したアクセスが行われた場合，互いに無関係なワンタイ
CAR が挙げられる．CLOCK-Pro はその長所である loop への耐
マーコンテンツ要求は scan を頻繁に生成しうる．また，要求さ
性が限定的であるという問題があり，frequently-shifts に強くな
れるコンテンツが激しく変動することで，frequently-shifts が発
い点からも CAR より性能の面で劣ると考えられる．更に，1 つ
生するだろう．
の CLOCK 上で独立して動作する針を 3 本持っており，CLOCK
2 点目に，コンテンツチャンクの粒度がキャッシュの動作に
と比較して針の動作回数が多くなる欠点もあり，候補から除外
甚大な影響を与える．チャンクの粒度がコンテンツサイズと等
する．CAR は loop に対処できないが，scan，frequently-shifts
しい場合，例えば Web ページのような複数のコンテンツから
に高い耐性を持っている．CAR は可変長の CLOCK を採用し
構成されるコンテンツや，連続的にコンテンツを取得する必要
ている点，LRU が残っている点から，低オーバーヘッドとは言
がある VoIP やストリーミングサービスなどだけが scan や loop
えないが，次章でその問題を解決する方法を提示する．
を生成しうる．一方，チャンクの粒度が小さく，イーサネット
フレームの MTU と等しい 1.5KB 程度を想定すると，単一の
4. 提案方式の設計
コンテンツへの要求によって scan や loop が発生しうる．例え
本章では，提案方式 Compact CAR の具体的なデータ構造と
ば，100MB の動画コンテンツはルータのキャッシュに対して約
アルゴリズムについて議論する．CAR を低オーバーヘッドに改
700k 回のアクセスを発生させるだろう．
良することで，低オーバーヘッドかつ高ヒット率なキャッシュ
3 点目はネットワーク中に複数のキャッシュが存在する点で
置換手法を実現する．
ある．これは要求がルータによって応答される機会を増やすと
4. 1 設 計 方 針
同時に，問題のあるアクセスパターンによる悪影響が多数の
CAR は ARC の実装コスト削減を図ったものだが，ルータで
ルータに伝搬する可能性を示唆している．要求の満足される確
の実装には 2 つの課題が残っている．2.3 節で述べたように，
率を維持しつつこの悪影響を低減するためには，適切な協調的
CAR は性質の異なるアクセスに適応的に振る舞うために可変
キャッシング戦略が必要となる．例えば，10 個のルータで別々
長の CLOCK を要するが，これに必要なコストは LRU-stack に
のコンテンツを協調的にキャッシュすることとすれば，擬似的
匹敵する．可変長の CLOCK を実現するためには，針の位置の
に 10 倍のサイズを持った 1 つのキャッシュストレージをネット
チャンクの削除と，針の直前 (リストの先頭) へのページの挿入
ワーク上に実現することができ，チャンク分割によって顕在化
が必須である．針はキャッシュメモリ上の任意の場所を指す可能
しやすくなった scan や loop の影響を軽減しうる．当然これを
性があるため，メモリ上の任意箇所のチャンクの削除・メモリ上
実現するためには適切なキャッシュ判断・配置アルゴリズムと，
の任意箇所へのチャンクの挿入が必要となる．この LRU-stack
協調キャッシングをサポートするルーティングプロトコルが必
と同等の実装コストは，ルータハードウェアに対しては不適で
要となる．本稿はルータの実装において必要なキャッシュ置換
ある．
アルゴリズムに焦点を当てるため，詳細な議論は省略する．
そこで，本稿では 2 つのリスト長の総和が一定になること
ルータにおけるキャッシングでは，以上のようなネットワー
を利用して課題を解決した手法として Compact CAR を提案す
クアクセスの特徴に適したアルゴリズムが必要である．特に
る．ARC/CAR においては，T1 , T2 , B1 , B2 はリスト長がそれぞ
scan や frequently-shifts に強く，可能であれば loop に強いこと
れ可変で，L1 = T1 ∪ B1 , L2 = T2 ∪ B2 のリスト長も可変であ
が望ましい．したがって，ARC や CLOCK-Pro が高キャッシュ
る．しかし，T1 ∪ T2 , B1 ∪ B2 は必ず最大長がキャッシュサイ
ヒット率を達成できると考えられる．correlated-reference が発
ズ c 以下に収まり，キャッシュが満杯の状況では常に c と等し
生する傾向は弱いと考えられ，統計的情報を利用する手法は高
くなる．したがって，T∗ = T1 ∪ T2 , B∗ = B1 ∪ B2 と表記する
い性能を発揮することができると予想される．ただし，LFU は
と，長さ c の連続メモリ領域上に T∗ と B∗ をそれぞれ配置し，
loop や frequtently-shifts に弱いため不適だろう．
チャンクの挿入・削除処理を工夫すれば，固定メモリ領域上で
性能だけではなく，アルゴリズムが低オーバーヘッドかつ高
速である必要がある．キャッシュ性能の向上を目指して統計情
低オーバーヘッドな CAR を実現することができると考えられ
る．このようなチャンク挿入・削除処理を実現した方式として，
—4—
𝑻𝟐 ( 𝑇2 = 𝑐 − 𝑛)
𝑻𝟏 ( 𝑇1 = 𝑛)
⋯ 𝑎𝑛 𝑏𝑐−𝑛 ⋯ 𝑏𝑗
𝑎1 𝑎2 ⋯ 𝑎𝑖
0
1
𝑎2
0
1
𝑦2
𝑥3
𝑥𝑘 𝑥𝑘−1
𝑏𝑗 𝑏𝑗−1
0
0
𝑦𝑐−𝑚 𝑦1
𝑥2
1
𝑦3
⋯
1
𝑥𝑚 𝑥1
0
𝑏3
⋯
𝑎𝑖 𝑎𝑖−1
0
𝑏2
1
⋯
⋯
⋯
⋯
𝑎3
𝑏𝑐−𝑛 𝑏1
0
⋯ 𝑦1
0
1
𝑎1
𝑎𝑛
0
Algorithm 3 ReplaceBtm() for Compact CAR
𝑩𝟐 ( 𝐵2 = 𝑐 − 𝑚)
𝑩𝟏 ( 𝐵1 = 𝑚)
𝑥1 ⋯ 𝑥𝑘 ⋯ 𝑥𝑚 𝑦𝑐−𝑚 ⋯ 𝑦𝑙
⋯ 𝑏1
𝑦𝑙 𝑦𝑙−1
Algorithm 4 ReplaceTop() for Compact CAR
0
reference-bit (R-bit)
図 1 Compact CAR(境界ページ移動方式による ARC の改善案) の概
略図
𝑻𝟐 ( 𝑇2 = 𝑐 − 𝑛)
𝑻𝟏 ( 𝑇1 = 𝑛)
𝑎1 𝑎2 ⋯ 𝒂𝒊 ⋯ 𝒂𝒏 𝑏𝑐−𝑛 ⋯ 𝑏𝑗
𝑻𝟐 ( 𝑇2 = 𝑐 − 𝑛 + 1)
𝑻𝟏 ( 𝑇1 = 𝑛 − 1)
⋯ 𝑏1
𝑎1 ⋯ 𝒂𝒏 ⋯ 𝑎𝑛−1 𝒂𝒊 𝑏𝑐−𝑛 ⋯ 𝑏𝑗
⋯ 𝑏1
+1
1
0
0
𝒂𝒏 𝑎1
0
0
𝑏3
1
0
1
𝑏2
0
0
0
𝑎3
1
𝒂𝒊
𝑏1
𝑏2
0
1
𝑏𝑗 𝑏𝑗−1
1
0
0
𝑏3
1
𝒂𝒏 𝑎𝑖−1
1
0
0
0
𝑎2
1
𝑏𝑗 𝑏𝑗−1
1
0
𝑎𝑛−1 𝑎1
⋯
⋯
0
0
𝑏𝑐−𝑛 𝑏1
⋯
⋯
𝒂𝒊 𝑎𝑖−1
1
0
⋯
⋯
𝑎3
⋯
⋯
0
1
𝑎2
1: procedure R EPLACE B TM(i)
2:
Swap(Bi [HandBi ], Bi .EdgeChunk)
3:
Discard Bi .EdgeChunk
4:
Rotate HandBi
5:
▷ an address next to the edge of Bi is ensured to be free.
6: end procedure
0
1: function R EPLACE T OP(i)
2:
while Ti [HandTi ].R-bit= 1 do
3:
Ti [HandTi ].R-bit← 0
4:
if i=1 then
5:
Swap(Ti [HandTi ], Ti .EdgeChunk)
6:
▷ Shift the boundary between T1 and 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
図 2 境界ページの移動方法の概略図 (T1 から T2 へページ ak を移動)
Algorithm 1 Dual-bit/Compact CAR Replacement Algorithm
1: procedure C ACHE R EPLACEMENT(x)
2:
if x ∈ T∗ then
3:
x.R-bit← 1
4:
return
5:
else if x ∈ B∗ then
6:
i←2
if x ∈ B1 then
7:
8:
9:
10:
11:
|B2 |
);
|B1 |
▷ x is an accessed chunk.
▷ cache hit
れぞれメモリ上の連続な位置に配置する．T1 は領域の一端，T2
はもう一端からそれぞれ逆方向に針が進む CLOCK として動作
する．B1 と B2 も，R ビットが不要なだけで同様である．それ
ぞれが独立した CLOCK として動作するため，単純なページの
▷ ghost hit
▷ to cache x in T2
置換処理は通常の CLOCK と同様に低オーバーヘッドかつ高速
に実行できる．
p ← min(c, p + δ)
問題はリストの大きさが変化するような場合であるが，各
DiscardBtm(1,x)
else
|B |
δ ← max(1, |B1 | ); p ← max(0, p − δ)
リスト間の境界位置のページと交換することで LRU-stack に
δ ← max(1,
▷ x ∈ B2
2
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
見られるシフト処理を廃する．図 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，
Algorithm 2 DiscardBtm() for Compact CAR
1: procedure D ISCARD B TM(i, x)
2:
Swap(x, Bi .EdgeChunk)
3:
Discard x (at the edge of Bi )
4:
▷ an address next to the edge of Bi is ensured to be free.
5: end procedure
3，4 に示す．アルゴリズム 1 では，Compact CAR の全体の戦
略，つまり，必要なリストの空き領域を確保してから適切な位
置へキャッシュ情報を移動する方法を示している．まず，キャッ
シュヒットした場合は R ビットを 1 に設定して終了する (2–4
行目)．キャッシュミスした場合は，5–19 行目で B∗ の空き領域
Compact CAR を提案する．
4. 2 Compact CAR の概要
Compact CAR では，図 1 のように T1 と T2 ，B1 と B2 をそ
を確保する．ghost hit 時 (5–13 行目) には，パラメータ p の値
を調整して，ghost hit した領域を元に空き領域を決定する．パ
ラメータ p は ARC の有用な特徴の一つで，リスト T1 の目標
—5—
サイズとして定義され，p の値をヒット状況に応じて動的に変
化させることでアクセスパターンの変化に適切に対応でき，他
の方式のように静的なパラメータを事前に調整する必要がなく
なる．完全にキャッシュミスした場合 (14–19 行目) は，B∗ に空
きがなければ B1 または B2 の履歴情報を置換し，空き領域を
確保する．そうでなければ，パラメータ p に従って任意の空き
領域を取得する．実質的にはこの処理はリストの終端のアドレ
スを取得するだけで済む．つぎに，20–26 行目でキャッシュ置
換処理を行う．置換されたキャッシュの履歴情報を B∗ に確保
した領域に記憶しつつ，T∗ の空き領域 st を確保する．最後に，
図 3 阪大の動画アクセス回数の分布
27 行目で st にキャッシュを行う．
アルゴリズム 2，3，4 は，それぞれ空き領域を確保するため
の処理である．HandTi はリスト Ti の針の位置を示しており，
された入力列の 2 種類を用い，コンテンツ単位とチャンク単位
Ti [HandTi ] はその針が指し示す領域を表す (Bi についても同
のアクセスそれぞれの場合についてキャッシュヒット率の評価
様)．どの関数でも最終的に空き領域はリストの境界上に確保さ
を行う．
れ，境界上に無いチャンク情報は必ずリスト端部のチャンク情
5. 2 シミュレーション設定
報 (アルゴリズム中の EdgeChunk) と交換される．この理由は，
5. 2. 1 アクセス列
例えば T∗ に空き領域がある場合に Ghost hit した場合など，確
シミュレーションに用いる入力列には，Zipf 分布に従うもの
保した空き領域が後続の処理で埋められないせいでリストの連
と，実トラフィックとして阪大のキャンパス内から外部の動画
続性が失われることを防ぐためである．端部チャンクは B1 と
サイトへのアクセス情報に基いて生成されたものの 2 種類を用
B2 の境界線に最も近い Bi のチャンクであり，CLOCK の針の
いる．以降，前者を AZipf(α) ，後者を AActual と呼称する．ネッ
位置とは無関係にリスト端部のチャンクを取得する．これは端
トワークコンテンツへのアクセスは一般的に Zipf 分布に従う
部チャンクであって境界チャンクではない点に注意する．なぜ
と言われており，提案手法の幅広い状況下における有効性を実
なら，キャッシュに空き容量がある場合，B1 と B2 の間には空
証するために AZipf(α) の α を変えてシミュレーションを行う．
き領域が存在し，端部チャンクはリストの境界とならないから
更に，実トラフィックに対する有効性を実証するために，それ
である．
に近い AActual を用いてキャッシュヒット率を評価する．
DiscardBtm 関数 (アルゴリズム 2) はリスト Bi 中のチャン
Zipf 則 と は ，コ ン テ ン ツ の 人 気 順 位 r の 関 数 f (r) =
ク x の履歴情報を削除する処理で，Ghost hit 時に実行される．
cα /rα (c, α は定数) によってその順位のコンテンツのアクセ
ReplaceBtm 関数 (アルゴリズム 3) はリスト Bi の針が指し示す
ス回数が近似できることを指す． [21] の人気度分布に関する
履歴情報を削除する処理で，キャッシュミス時に B∗ が満杯な
議論によれば，α は 0.5 から 1.2 までの値を取るため，今回は
らば実行される．ReplaceTop 関数 (アルゴリズム 4) はリスト
α = 0.6, 0.8, 1.0, 1.2 の 4 通りの場合についてシミュレーション
Ti の針が指し示すチャンクを削除する処理で，T∗ が満杯の場
を行った．アクセス数は後述の AActual と同様に 107 個程度に
合に空き領域を確保するために実行される．置換対象が T1 中
設定した．
のチャンクの場合，R ビットが 1 のページは図 2 で示した方法
実トレースデータは，YouTube, nicovideo, dailymotion の 3 つ
で T2 に移動される．置換されたチャンクは履歴情報として対
の動画サイトに対する，2013 年 7 月 26 日から 2015 年 2 月 26 日
応する履歴リストに記憶されるが，この記憶先はその履歴リス
までのアクセスに基づく．ユニークコンテンツ数は 2,428,880 個，
トの端部チャンクに隣接する領域のアドレスであり，事前の処
2 回以上アクセスのあるコンテンツ数はその約半数の 918,545
理によって必ず空き領域となっている．B∗ に空き領域が存在
個である．この約 1 年半の間の全体のアクセス数は 13,004,868
した場合は当然リスト端部の隣接アドレスも空いているはずで
アクセスである．アクセス分布は図 3 のようになっており，Zipf
あり，B∗ が満杯の場合は DiscardBtm または ReplaceBtm 関数
分布に近い形で，人気が高いコンテンツへの集中が多いことが
の実行時にリスト B1 と B2 の境界上に空き領域が確保されて
確認できる．実際，最もアクセスされたコンテンツのアクセス
いるため，どちらのリストから見てもリスト端部に隣接する領
数は 149,820 回である．
域は解放済みとなっている．
5. シミュレーション評価
5. 1 概
要
これらのアクセス列はコンテンツ単位でのアクセスだが，そ
こからチャンク単位での入力列も生成した．具体的には，アク
セス日時と動画情報を利用し，動画の長さと対応画質の情報
から動画サイズを決定して，予め決定したサイズのチャンクが
Compact CAR の性能を単純な手法と比較して，十分に高い
再生時間を等分割した時間間隔で要求されるようなアクセス
性能を発揮できることを示す．評価にはコンテンツのアクセス
列を想定する．チャンクサイズ L は 1500B・1.5KB・60KB を
頻度が Zipf 分布に従うように人工的に生成した入力列と，阪大
対象とする．また，動画長 1 分あたりの通信量は，簡単な事
キャンパス内部から外部動画サイトへのアクセスに基いて生成
前調査の結果，表 1 の規則に従って動画ごとのチャンク数を決
—6—
場合の評価結果の一例として，α = 1.0 の場合を図 8，9，10 に
表 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
CAR に匹敵する性能を示している．Compact CAR は LRU 順序
の不整合による性能の劣化が予想されたが，最大でも 0.5% 以
定した．AZipf(α) に関しては，観測された動画の再生時間と画
下の差しか見られなかった．これらの CAR 系の手法は一様に
質の分布に従って，コンテンツごとに再生時間と画質を決定
高い性能を示しており，良い場合には同一のキャッシュヒット
した．しかし，チャンク単位のアクセスは膨大な量となってシ
率を達成するために CLOCK や FIFO の 1/10 以下で済む．OPT
ミュレーションの実行が困難であるため，107 個程度の長さに
との差についても，ほぼすべての場合で 10% 以下に抑えられ
収まるように一部分のみを対象としてチャンク単位のアクセ
ている．α が大きいほどキャッシュヒット率が高く，紙面の制
ス列を切り出した．AActual については，キャッシュの効果を
限上記載していないがチャンク単位のキャッシングでも同じ傾
考慮してアクセスの集中する時間帯を対象とし，2013 年 7 月
向が見られる．チャンク単位でのキャッシュでは，チャンクサ
29 日のトラフィックについて，チャンクサイズ 1.5KB に関し
イズが小さいほどコンテンツが多数のチャンクに分割される影
ては 12:01 から 12:10 まで (約 9 分間)，15KB の場合に関して
響が大きく，キャッシュヒット率が大幅に低下する．
は 13:02 から 14:08 まで (約 66 分間)，60KB の場合に関しては
前日の 19:57 から 14:45 まで (約 19 時間) を対象とした．以降，
5. 3. 2 実トラフィック AActual に基づく評価
次に，実トラフィックに基づくトラフィックの評価結果を示
コンテンツ単位のアクセス列と区別するために，コンテンツ単
す．単一ルータの場合の評価結果は，コンテンツ単位の結果を
C
位のアクセス列は AC
Zipf(α) と AActual ，チャンク単位のアクセ
図 11 に，パケット単位の結果を図 12，13，14 に示している．
=LKB
P =LKB
ス列は AP
Zipf(α) と AActual のように表記する．
AC
Actual の結果は，OPT を除く手法間で差が出ていない．特
5. 2. 2 対 象 方 式
に，CAR 系の手法が単純な手法より優れているものの差は小さ
評価対象とするキャッシング手法は提案手法の他に，OPT,
い．これは, トレースデータのアクセスの局所性の高さに起因
FIFO, CLOCK, CAR を用いる．OPT は最適手法であり，同一
すると考えられる。人気のコンテンツに対する要求間隔が短い
キャッシュサイズで実現可能なキャッシュヒット率の上限値が分
値に集中するために、単純な手法でも CAR に匹敵する性能を
かる．それ以外はルータハードウェア実装が実現可能な高速な
=1.5KB
示したと考えられる。実際に AP
では 104 付近でキャッ
Actual
方式のみを対象としている．FIFO と CLOCK は単純な手法で
シュヒット率が急上昇しており、チャンク分割によって要求間
あり，提案手法が単純な手法と比較してどれほど改善できてい
隔が引き伸ばされたものと考えられる。トレースデータは動画
るかの基準とする．CAR は提案手法の基とした既存手法であ
サイトへのアクセスのみを抽出しているため、多様なアプリ
り，提案手法が CAR よりも性能が悪くないことを示せるのが
ケーションへの要求を扱う現実のルータでは局所性は低くなり、
望ましい．
CAR と単純な手法の性能差は大きくなることが予想される。
5. 2. 3 環 境 設 定
=LKB
また，AP
Actual の結果では，CAR 系の手法が単純な手法に
ネットワークトポロジーは単一ノードの場合と単純なトポロ
大きく勝っている．チャンク単位でのアクセスでは同一チャン
ジーの場合の 2 通りを考える．単一ノードとは，コンテンツ
ク間のアクセス数が増加して局所性が低下した結果，FIFO や
供給元とユーザが単一のルータでつながっている場合であり，
CLOCK の性能が低下したと推測される．一方，CAR 系の手法
キャッシュ置換手法の純粋な性能を確認できる．単純なトポロ
=1.5KB
=15KB
は高いヒット率を示しており，特に AP
と AP
で
Actual
Actual
ジーとしては，10 個のルータがコンテンツ供給元とユーザを繋
=1.5KB
は OPT に近い性能を達成している．注意点として，AP
Actual
2
=60KB
から AP
にかけて，チャンクサイズが小さくなっている
Actual
ぐ直線上のトポロジーを想定し，キャッシュ判断方式には CE
を採用する．
評価指標にはキャッシュヒット率を採用する．これは，ユー
ザの要求全体 (ルータへのアクセス数全体ではない) に対するそ
にも関わらずキャッシュヒット率が低下する傾向が見られるが，
これはアクセスの集中度合いが時間帯によって大きく変化する
ためである．
のルータでのキャッシュヒット数の割合である．アクセス列の
5. 3. 3 複数ルータの場合の評価
長さを 107 程度に抑えているため，キャッシュサイズ C は 101
直線状トポロジーでの評価結果の一部として, AC
Zipf(α) の一
6
から 10 [Chunks] の 6 通りとする．コンテンツのサイズは考慮
=LKB
例を図 15 に, AP
Zipf(α) の評価結果の一部を図 17, 18 に示す。ま
せず，チャンク数に対するキャッシュヒット率を考える．
=15KB
た,AP
の結果を図 20 に示している。グラフの横軸は, 左
Actual
5. 3 評 価 結 果
端がネットワーク全体のキャッシュヒット率を示しており, 以降
5. 3. 1 人工的に生成したトラフィック AZipf(α) に基づく評価
は 1 番目から 10 番目まで要求者に近いルータから順番にアク
まず，Zipf 則に基づき人工的に生成したトラフィックの評価結
セス全体に対するヒット数の割合を示している。全体で 96 通
果を示す．図 4，5，6，7 は，単一ルータで，要求がコンテンツ単
りの試行を行ったが, そのすべてで記載されている結果とほぼ
位の場合の評価結果である．4 通りの α の値ごとに，AC
Zipf(0.6)
C
C
は図 4，AC
は図
5
，
A
は図
6
，
A
Zipf(0.8)
Zipf(1.0)
Zipf(1.2) は図 7
同じ傾向が見られた。結果としては,CLOCK や FIFO が 2 番目
に結果が示されている．また，チャンク単位で要求が行われた
て, 提案手法を含む CAR 系の手法は 2 番目以降のルータでも少
以降のルータではキャッシュヒット率がほぼ 0 であるのに対し
—7—
0.6
0.4
0.3
0.2
1
OPT
FIFO
CLOCK
CAR
Compact CAR
0.9
0.8
0.7
0.5
0.4
0.3
0.2
0.1
101
102
103
104
105
101
102
Cache size [Chunks]
103
104
105
104
105
0.1
101
102
103
101
102
103
104
105
0.6
0.5
0.5
0.4
0.3
0
106
101
102
103
104
105
106
Cache size [Chunks]
図7
AC
Zipf(1.2)
0.2
0
106
101
102
103
104
105
106
Cache size [Chunks]
=60KB
AP
Zipf(1.0)
図 10
0.7
OPT
FIFO
CLOCK
CAR
Compact CAR
0.6
0.5
Cache hit rate
0.7
0.6
105
0.3
=15KB
図 9 AP
Zipf(1.0)
OPT
FIFO
CLOCK
CAR
Compact CAR
104
OPT
FIFO
CLOCK
CAR
Compact CAR
0.4
Cache size [Chunks]
Cache hit rate
Cache hit rate
0.7
0.2
0.1
=1.5KB
図 8 AP
Zipf(1.0)
0.8
0.3
0.2
0.5
Cache size [Chunks]
0.9
0.4
図 6 AC
Zipf(1.0)
0.2
0
106
0.5
Cache size [Chunks]
0.1
103
OPT
FIFO
CLOCK
CAR
Compact CAR
0.6
0.3
0
Cache hit rate
0.1
102
0.4
106
OPT
FIFO
CLOCK
CAR
Compact CAR
0.3
Cache hit rate
Cache hit rate
0.4
OPT
FIFO
CLOCK
CAR
Compact CAR
101
0.5
図 5 AC
Zipf(0.8)
0.2
0
0.7
0.6
Cache size [Chunks]
図 4 AC
Zipf(0.6)
0.3
0.8
0.1
0
106
0.9
0.4
0.3
0.6
OPT
FIFO
CLOCK
CAR
Compact CAR
0.5
Cache hit rate
0
0.1
1
OPT
FIFO
CLOCK
CAR
Compact CAR
Cache hit rate
0.7
Cache hit rate
Cache hit rate
0.5
0.8
OPT
FIFO
CLOCK
CAR
Compact CAR
Cache hit rate
0.6
0.4
0.3
0.2
0.2
0.1
0.1
0
0
OPT
FIFO
CLOCK
CAR
Compact CAR
0.4
0.3
0.2
0.2
101
102
103
104
105
106
101
102
Cache size [Chunks]
AC
Actual
図 11
図 12
FIFO
CLOCK
CAR
RepelCAR
0.4
104
105
106
FIFO
CLOCK
CAR
RepelCAR
0.35
0.3
0.2
0.1
0.3
0.25
0.2
0.15
0.1
tot
al
1st
2n
d
3rd
4th
5th
6th
7th
8th
9th
0
10
th
tot
1
al st
2n
d
3rd 4th 5th 6th 7th 8th 9th 10
th
Node
図 15
# of Hits / # of total accesses
0.3
0.2
0.1
tot
al
1st
2n
d
3rd
4th
5th
6th
7th
8th
9th
10
th
FIFO
CLOCK
CAR
RepelCAR
0.2
AC
Actual
(C = 103 [Chunks])
105
0
106
101
102
=15KB
AP
Actual
FIFO
CLOCK
CAR
RepelCAR
0.25
0.2
0.15
0.1
0
103
104
105
106
Cache size [Chunks]
図 14
=60KB
AP
Actual
0.3
FIFO
CLOCK
CAR
RepelCAR
0.25
0.2
0.15
0.1
0.05
tot
1
al st
2n
d
3rd 4th 5th 6th 7th 8th 9th 10
th
0
tot
1
al st
Node
=60KB
AP
Zipf(1.0)
(c =
6. 考
2n 3rd 4th 5th 6th 7th 8th 9th 10
th
d
図 18
103 [Chunks])
=60KB
AP
Zipf(1.0)
(c = 104 [Chunks])
察
6. 1 単純な手法からの改善
0.15
CAR は単純な手法よりも性能が優れており，CAR の近似手
0.1
法である提案手法は CAR とほとんど同等の性能を示した．特
0.05
0
に，低オーバーヘッド化のために LRU の順序を崩した Compact
tot
1
al st
Node
図 19
図 13
0.3
図 17
103 [Chunks])
0.25
0.4
104
Node
=60KB
AP
Zipf(1.2)
(c =
FIFO
CLOCK
CAR
RepelCAR
0.5
# of Hits / # of total accesses
図 16
105 [Chunks])
0.6
0
103
Cache size [Chunks]
Node
AC
Zipf(0.8)
(c =
102
0.05
0.05
0
101
=1.5KB
AP
Actual
0.4
# of Hits / # of total accesses
# of Hits / # of total accesses
0.5
103
0.1
Cache size [Chunks]
# of Hits / # of total accesses
0
# of Hits / # of total accesses
0.1
2n
d
3rd 4th 5th 6th 7th 8th 9th 10
th
Node
図 20
=15KB
AP
Actual
(C = 103 [Chunks])
CAR でこのような結果が得られたのは理想的と言える．提案
手法を用いることで同一の性能を達成するために必要なキャッ
シュサイズを削減することができ，FIFO や CLOCK と比較し
てキャッシュ資源の利用効率を 10 倍程度に高めることができ
る．ほぼすべての場合で OPT との差は 10% 以下に抑えられて
量ながら全体のキャッシュヒット率向上に貢献している。
いるが，AZipf(α) の評価結果から分かるように，α の値が低い，
—8—
つまり人気度の偏りが低いほど OPT との差が大きい傾向があ
での実現は困難であり，同様に ICN の特徴を活かしてコンテン
る．現実のトラフィックは様々なアプリケーションの重畳効果
ツごとの統計を取る手法もオーバーヘッドが大きすぎる．本研
によって人気度の偏りが引き伸ばされていくことが想定される
究では，ネットワーク中を流れるコンテンツのほとんどは 1 度
ため，キャッシュ置換アルゴリズムの更なる改良には大きな価
しかアクセスされないコンテンツであることに注目し，ワンタ
値があるだろう．
イマーコンテンツを避ける有望な手法として CAR [17] に注目
しかし，OPT との差は依然として存在している．今回の評価
した．CAR の動作を CLOCK と同等なレベルに置き換え，更
結果から，アクセスの局所性の多様化が性能の悪化原因と予想
に固定メモリ領域で動作可能なキャッシング手法を提案するこ
されるため，それに対処可能なキャッシュ置換手法が期待され
とで，ワンタイマーコンテンツに耐性を持つ低オーバーヘッド
る．また，CAR は loop に弱い手法であるが，チャンク単位の
なキャッシュ置換手法の実現を目指した．
連続アクセスが直感的に loop を形成しやすいことから，loop
への対処が可能な手法について検討すべきと考えられる．
可変長の CLOCK をどのようにして低コストに実装するかが
主な実装課題だが，リスト長の相補性に注目して可変長の動
6. 2 ルータの実現可能性
作を無くし，管理・運用コストを最小限に抑える手法 Compact
ネットワークトラフィックをキャッシュする場合，キャッシュ
CAR を提案した．Compact CAR は連続したメモリ領域を明確
容量とアクセス速度の制約が課題となる．無差別にキャッシュ
に二分して，両端ごとに別々の CLOCK を割り当てることで，
を行う場合，ルータは自身が送信した全 Data パケットをキャッ
CLOCK ごとのメモリ領域の連続性を維持させる．キャッシュが
シュする．例えば，10Gbps のトラフィックを扱うラインカー
溢れた場合は境界線上のエントリを置換することで，領域端か
ドは 1 秒間で最大 1.25GB をキャッシュする必要がある．また，
ら境界線上までのキャッシュエントリ連続性を保持する．ただ
Data パケットサイズが 64B だと仮定すると，最大で約 20MSPS
し，メモリの境界線上のエントリの置換という LRU の特徴を
の処理速度が必要である．更に，複数のラインカードのトラ
無視した置換によって，性能が大きく変化する可能性があった．
フィックを収容するルータ単位では，ラインカード数に比例し
評価の結果，提案手法は CAR と同等の性能を示すという理
た性能を確保しなければならない．現実的には，Interest パケッ
想的な結果が確認され，単純な手法と比較して同一の性能を達
トの存在とキャッシュヒットの発生によってこの時間は数十%
成するために必要なキャッシュ容量が 1/10 で済む場合がある
程度延長されうると考えられるが，倍以上の改善のためには
ことが判明した．改善の余地は見られるものの，提案手法が低
キャッシュ判断方式の併用が必要だろう．
オーバーヘッドかつ高性能であることを示し，ICN ルータの実
提案するアルゴリズムは 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 キャッシン
グの多くはソフトウェアレベルでの動作を想定していてルータ
度（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,” Proceedings of the 7th International ICST Conference on Broadband
Communications,Networks, and Systems, pp.1–13, Oct. 2010.
[5] T. Levä, J. Gonç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, “Experimental analysis of caching efficiency for YouTube traffic in an ISP
network,” Proceedings of the 25th International Teletraffic Congress,
pp.1–9, Sept. 2013.
—9—
[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 Computer Communication Review, vol.43, no.4, pp.147–158, Aug. 2013.
[9] S. Arianfar, P. Nikander, and J. Ott, “On content-centric router design 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 Communications，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 Communications, vol.61, no.1, pp.48–57, May 2015.
[14] N. Megiddo and D.S. Modha, “ARC: a self-tuning, low overhead replacement 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 workloads: a novel replacement algorithm to improve buffer cache performance,” 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 improvement 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 International 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 performance 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,” Proceedings 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.
— 10 —