router_cachehit.eps

(1)

ワーク誘導型キャッシュ発見方式の融合

柳生智彦 _{(NEC / 電通大), 藤井厚太朗 (電通大)} 情報指向ネットワーク技術時限研究会 2015/4/7

研究背景

▌増加するトラフィックモバイルデータトラヒック総量は_{5年間で10倍に} [1] ▌WEBやビデオなどコンテンツ流通が大半現在，コンテンツ流通はトラヒックの約半分で毎年_69%増加

[1] Cisco Visual Networking Index：全世界のモバイルデータトラフィックの予測、 2013 ～ 2018 年アップデート, 2014 White paper , 2014

• Content Oriented Network の研究

- トラヒックの大半がコンテンツ流通であることに着目 - 効率的なコンテンツ配信を実現する新しいNWを提案

(2)

Page 3 © NEC Corporation 2015 NEC Group Internal Use Only

Content Oriented Network (CON)の研究

CON

インターネット

DNSサーバ f1 f1 f1 サーバサーバユーザはコンテンツを取得する場所を指定しないインターネット CON 転送先の判断 IPアドレスを用いるコンテンツ名を用いるルータのコンテンツキャッシュなしありコンテンツ取得場所ユーザが指定する NW内で決定する現在のインターネットと_CONの比較

CONの研究課題（の一部）

▌ルータがキャッシュを持つ_{CONで効率的なコンテンツ配信を実現す} るには次のことが重要になる ▌・どのコンテンツを，どのルータでキャッシュするか ⇛キャッシュ方式最適化問題を解くことで、キャッシュの最適配置を行う研究等人気度は常に変化し、新たなコンテンツが生成される→事前計算は困難 ▌・どのようにキャッシュしたルータへ誘導するか ⇛キャッシュ発見方式（ルーティング）明示的なキャッシュへのルーティングはスケーラビリティの点で困難

(3)

従来のキャッシュ方式

Transparent En-Route Cache (TERC)方式 • CONで用いられる基本的なキャッシュ方式 • ルータは通過するコンテンツをキャッシュ

• キャッシュ交換はLeast Recently Used (LRU) 規律で行う TERC方式の問題点 • キャッシュの交換回数が多くルータ負荷が高い • コンテンツ人気度を考慮しておらず，キャッシュヒット率が低い

キャッシュ発見方式

_Breadcrumbs

Breadcrumbs方式（BC方式）の概要 -コンテンツ転送時に TERC方式でキャッシュし， BC情報を記憶する - BC情報は5つの属性で構成されるコンテンツ転送先を辿ってできる軌跡を_{BC Trail}と呼ぶ ① _f1 ② _null ③ _B ④ _ta ⑤ _null ①_② f1_A ③ _D ④ _tb ⑤ _null サーバサーバサーバサーバ A C B D ユーザユーザユーザ ユーザ1 BC Trail BC有 BC有キャッシュ有 ① ① ① ① コンテンツコンテンツコンテンツコンテンツ ID ② コンテンツ転送元 ③ ③ ③ ③ コンテンツコンテンツコンテンツコンテンツ転送先転送先転送先転送先 ④ コンテンツ通過時間 ⑤ クエリの通過時間 ① _f1 ② _B ③ _null ④ _td ⑤ _null

(4)

Breadcrumbsによるクエリ誘導

BCによるクエリ誘導のシナリオ ① ルータ_{A，Bのキャッシュが上} 書きされなくなる ② ユーザ２のクエリは_BC情報により_{A→B→Dと転送される} ③ デフォルト経路上以外の_Dでキャッシュヒットユーザユーザユーザ ユーザ2 ① _f1 ② _null ③ _B ④ _ta ⑤ _null ①_② f1_A ③ _D ④ _tb ⑤ _null サーバサーバサーバサーバ A C B D BC Trail BC有 BC有キャッシュ有コンテンツ転送先を辿ってできる軌跡を_{BC Trail}と呼ぶ BC情報を利用することでデフォルト経路以外のキャッシュも利用できるようになる ① _f1 ② _B ③ _null ④ _td ⑤ _null

Breadcrumbsの無効化

BCの無効化シナリオ ① ルータ_{A，B，Dのキャッシュが} 上書きされなくなる ② ユーザ２のクエリは_BC情報により_{A→B→Dと転送される} ③ _{BCTrailの末端までキャッシュ} が存在しないのでクエリを送り返す ④ 送り返された場合，_BC情報を無効化するユーザユーザユーザ ユーザ2 ① _f1 ② _null ③ _B ④ _ta ⑤ _null ①_② f1_A ③ _D ④ _tb ⑤ _null サーバサーバサーバサーバ A C B D BC Trail BC有 BC有キャッシュ有コンテンツ転送先を辿ってできる軌跡を_{BC Trail}と呼ぶ BCTrail上のルータにキャッシュが存在しない場合，無駄な誘導となるため無効化する ① _f1 ② _B ③ _null ④ _td ⑤ _null

(5)

Breadcrumbsの課題

キャッシュの交換回数が多くルータ負荷が高い

キャッシュの交換回数が多い場合、

BC情報無効化回数

も増える

• クエリホップ数が増え，コンテンツ発見の時間が長くなる

本研究の目的

目的目的目的目的 • 従来手法よりキャッシュヒット率を向上させる • ルータのキャッシュ交換回数の削減 • 迅速なコンテンツ発見の実現提案方式提案方式提案方式提案方式

１．_{Popularity Based Cache （POP）方式} （_{12月NS研究会にて発表）}

人気度推定に基づくキャッシュ方式２．_BC-POP方式 POP方式とBC方式を組み合わせた方式前提 • コンテンツの数や人気度は未知 • 集中制御サーバは無い

(6)

Popularity Based Cache（POP）方式概要

高人気コンテンツユーザ付近でキャッシュされるキャッシュがサーバへのクエリ転送を減らすユーザ付近ではキャッシュされないクエリが集まる場所でキャッシュされる人気度推定に基づくキャッシュ選択方式・クエリをサーバ方向へ転送・ルータはクエリ受信時にコンテンツ_{IDの履歴を記憶} ・クエリ受信回数の多いコンテンツをキャッシュする低人気コンテンツ

POP方式に必要な記憶領域

クエリ履歴キャッシュルータリスト（_CRL）制限なしキャッシュするルータ_{IPアドレス} 100個コンテンツ_ID コンテンツキャッシュ 2個コンテンツルータクエリコンテンツ応答 CRLを用いてクエリ転送時にキャッシュ要と判断したルータにコンテンツを転送し，キャッシュする

(7)

POP方式ルータ動作例

ｎ：ルータのキャッシュ可能数コンテンツ_ID ・_{CRL要素と自身のルータIDを} 比較し一致する場合キャッシュ・キャッシュ交換は要求頻度の低いものが対象・_{CRL要素が登録されている場合} 優先して転送する

シミュレーション条件

サーバ_(500台) 全ルータに_1台配置管理コンテンツ数 _(20個) ルータ _(500台) キャッシュ_(2個) クエリ保持履歴_(100個) コンテンツ _(10000個) 人気度_{(zipf則 α＝0.7)} サイズ _{(125 kB)} ユーザ全ルータに配置総リクエスト数 _(100000回) クエリサイズ _{(125 B)} リンク数 _(2000本) 帯域 _(1Gbps) Waxman Model Waxman ModelWaxman Model Waxman Model

(8)

POP方式のキャッシュ位置の考察

TERC方式キャッシュ位置：経路上キャッシュ交換：多い POP方式キャッシュ位置：クエリの集まる場所キャッシュ交換：少ないサーバサーバ *人気度10位のコンテンツ

(9)

POP方式の課題

▌サーバ数が少ない場合、キャッシュヒット率が大きく減少 POP方式は、サーバ付近の人気度の偏りを利用して、多様なキャッシュを保持する方式。サーバが少なくなると、人気度の高いコンテンツばかりがキャッシュされるようになる 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0 100 200 300 400 500 600 キャッシュヒット率キャッシュヒット率キャッシュヒット率キャッシュヒット率サーバ台数サーバ台数サーバ台数サーバ台数 TERC BC POP

BC-POP方式

キャッシュ手法である_{POP方式、キャッシュ発見手法であるBC方式} を組み合わせた_BCPOP方式クエリ転送時 • BC方式と同様に，BC情報を用いてクエリを誘導する • BC情報がないか，キャッシュヒットする場合のみクエリ履歴を更新コンテンツ応答転送時・_{CRL要素が有る場合のみBCを作成} コンテンツ応答転送時にキャッシュするルータの有無を把握できるので必要最低限の_BCを作成する BCPOP方式はキャッシュ生存時間が長いので_BCTrail 上に複数個キャッシュを作成する必要がない BC Trail クエリ履歴更新しないしないするするするするするしない BC作成 R1 R2 R3 R4 CRL：R3

(10)

性能評価

サーバ_(50台) 管理コンテンツ数 _(200個) ルータ _(500台) キャッシュ_(2個) クエリ保持履歴_(100個) コンテンツ _(10000個) 人気度_{(zipf則 α＝0.7)} サイズ _{(125 kB)} ユーザ全ルータに配置総リクエスト数 _(100000回) クエリサイズ _{(125 Byte)} リンク数 _(2000本) 帯域 _(1Gbps) Waxman Model Waxman ModelWaxman Model Waxman Model

主な評価結果

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Cache Hit Zipf Alpha BCPOP BC POP 人気度係数が変化した際にも BC-POP方式は高キャッシュヒット率を示した BC-POP方式 BC方式 POP方式キャッシュヒット率 28.3 20.2 19.9 キャッシュ交換回数 1076 519428 2727 クエリホップ数 6.47 13.87 6.05 コンテンツホップ数 6.1 6.22 6.05 ネットワーク負荷 76330GB 77923GB 75700GB クエリホップ数_54%軽減交換回数を_99.8%軽減キャッシュヒット率_{8.1ポイント向上} ・サーバ台数_{50台のときの評価結果} ・コンテンツ人気度分布を変化させた際のキャッシュヒット率横軸： 0.1 コンテンツが均等にアクセスされる 0.9 一部コンテンツにアクセスが集中する BC-POP方式とBC方式の比較

(11)

サーバ台数変化とキャッシュヒット率の関係

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0 50 100 150 200 250 300 350 400 450 500 CacheHit ServerNum BCPOP BC POP TERC BC-POP方式はすべてのサーバ台数で高キャッシュヒット率を示したサーバ_{1台から500台に変化させた場合}

キャッシュの多様性

BC-POP BC POP 全種類中 ₇₀₂ ₅₈₂ ₅₇₇ 上位_{1000コンテンツ中} ₃₀₉ ₁₈₁ ₂₄₆ シミュレーション終了時に、ネットワーク内のキャッシュに残っていたコンテンツの種類 BC-POP方式は、ネットワーク内に多様なコンテンツをキャッシュすることでキャッシュヒット率を向上キャッシュの発見には_{BCが効果を発揮}

(12)

リンクごとの転送パケット数

400000 600000 800000 1e+006 1.2e+006 1.4e+006 1.6e+006 1.8e+006 2e+006 2.2e+006 2.4e+006 0 50 100 150 200 Packet Link ID BCPOP BC POP

ルータごとのキャッシュヒット数

0 50 100 150 200 250 300 350 400 450 500 0 50 100 150 200 250 300 350 400 450 500

Router Cache Hit

Router Id

BCPOP POP BC

(13)

まとめ

▌

キャッシュ発見方式である

_{Breadcrumbsと人気度推定による}

キャッシュ方式

_{POPを組み合わせたBC-POP方式を提案}

BC方式に比べ、キャッシュヒット率を8.1ポイント向上。サーバ台数や人気度分布変化によらず高キャッシュヒット率を実現 BC方式に比べ、キャッシュ交換回数を99.8%減少でき，ルータ負荷を大きく削減 BC方式に比べ、クエリホップ数は54%減少し，迅速なキャッシュ発見を実現 ▌今後の課題キャッシュヒット数が少ないルータの効果的な活用方法の検討謝辞本研究の一部は，独立行政法人情報通信研究機構_{(NICT)の委託研究「新世代ネットワークを支え} るネットワーク仮想化基盤技術の研究開発」の成果です．