人気度推定を用いたキャッシュ方式とネットワーク誘導型キャッシュ発見方式の融合 柳生智彦 (NEC / 電通大 ), 藤井厚太朗 ( 電通大 ) 情報指向ネットワーク技術時限研究会 2015/4/7 研究背景 増加するトラフィック モバイルデータトラヒック総量は 5 年間で 10 倍に [1] WEB やビデオなどコンテンツ流通が大半 現在, コンテンツ流通はトラヒックの約半分で毎年 69% 増加 増え続けるトラヒックへ対応 Content Oriented Network の研究 - トラヒックの大半がコンテンツ流通であることに着目 - 効率的なコンテンツ配信を実現する新しい NW を提案 [1] Cisco Visual Networking Index: 全世界のモバイルデータトラフィックの予測 2013 ~ 2018 年アップデート, 2014 White paper, 2014 Page 2 NEC Corporation 2015 NEC Group Internal Use Only
Content Oriented Network (CON) の研究 現在のインターネットと CON の比較 インターネット CON 転送先の判断 IPアドレスを用いる コンテンツ名を用いる ルータのコンテンツキャッシュ なし あり コンテンツ取得場所 ユーザが指定する NW 内で決定する インターネット DNS f1 CON f1 ユーザはコンテンツを取得する場所を指定しない f1 Page 3 NEC Corporation 2015 NEC Group Internal Use Only CON の研究課題 ( の一部 ) ルータがキャッシュを持つ CON で効率的なコンテンツ配信を実現するには次のことが重要になる どのコンテンツを, どのルータでキャッシュするか キャッシュ方式 最適化問題を解くことで キャッシュの最適配置を行う研究等 人気度は常に変化し 新たなコンテンツが生成される 事前計算は困難 どのようにキャッシュしたルータへ誘導するか キャッシュ発見方式 ( ルーティング ) 明示的なキャッシュへのルーティングはスケーラビリティの点で困難 Page 4 NEC Corporation 2015 NEC Group Internal Use Only
従来のキャッシュ方式 Transparent En-Route Cache (TERC) 方式 CON で用いられる基本的なキャッシュ方式 ルータは通過するコンテンツをキャッシュ キャッシュ交換は Least Recently Used (LRU) 規律で行う TERC 方式の問題点 キャッシュの交換回数が多くルータ負荷が高い コンテンツ人気度を考慮しておらず, キャッシュヒット率が低い Page 5 NEC Corporation 2015 NEC Group Internal Use Only キャッシュ発見方式 Breadcrumbs Breadcrumbs 方式 (BC 方式 ) の概要 - コンテンツ転送時に TERC 方式でキャッシュし, BC 情報を記憶する - BC 情報は5つの属性で構成される 1 コンテンツ ID 2 コンテンツ転送元 C 3 コンテンツ転送先 4 コンテンツ通過時間 5 クエリの通過時間 A 2 null 3 B 4 ta ユーザ 1 B D BC 有 BC 有キャッシュ有 2 A 3 D 4 tb BC Trail 2 B 3 null 4 td コンテンツ転送先を辿ってできる軌跡を BC Trail と呼ぶ Page 6 NEC Corporation 2015 NEC Group Internal Use Only
Breadcrumbs によるクエリ誘導 BC 情報を利用することでデフォルト経路以外のキャッシュも利用できるようになる BC によるクエリ誘導のシナリオ 1 ルータ A,B のキャッシュが上書きされなくなる 2 ユーザ 2 のクエリは BC 情報により A B D と転送される 3 デフォルト経路上以外の D でキャッシュヒット C ユーザ 2 A 2 null 3 B 4 ta B D BC 有 BC 有キャッシュ有 2 A 3 D 4 tb BC Trail 2 B 3 null 4 td コンテンツ転送先を辿ってできる軌跡を BC Trail と呼ぶ Page 7 NEC Corporation 2015 NEC Group Internal Use Only Breadcrumbs の無効化 BCTrail 上のルータにキャッシュが存在しない場合, 無駄な誘導となるため無効化する BC の無効化シナリオ 1 ルータ A,B,D のキャッシュが上書きされなくなる 2 ユーザ 2 のクエリは BC 情報により A B D と転送される 3 BCTrail の末端までキャッシュが存在しないのでクエリを送り返す 4 送り返された場合,BC 情報を無効化する C ユーザ 2 A 2 null 3 B 4 ta B D BC 有 BC 有キャッシュ有 2 A 3 D 4 tb BC Trail 2 B 3 null 4 td コンテンツ転送先を辿ってできる軌跡を BC Trail と呼ぶ Page 8 NEC Corporation 2015 NEC Group Internal Use Only
Breadcrumbs の課題 キャッシュの交換回数が多くルータ負荷が高い キャッシュの交換回数が多い場合 BC 情報無効化回数も増える クエリホップ数が増え, コンテンツ発見の時間が長くなる Page 9 NEC Corporation 2015 NEC Group Internal Use Only 本研究の目的 目的 従来手法よりキャッシュヒット率を向上させる ルータのキャッシュ交換回数の削減 迅速なコンテンツ発見の実現 提案方式 1.Popularity Based Cache (POP) 方式 (12 月 NS 研究会にて発表 ) 人気度推定に基づくキャッシュ方式 2.BC-POP 方式 POP 方式と BC 方式を組み合わせた方式 前提 コンテンツの数や人気度は未知 集中制御は無い Page 10 NEC Corporation 2015 NEC Group Internal Use Only
Popularity Based Cache(POP) 方式概要 人気度推定に基づくキャッシュ選択方式 クエリを方向へ転送 ルータはクエリ受信時にコンテンツ ID の履歴を記憶 クエリ受信回数の多いコンテンツをキャッシュする 高人気コンテンツ ユーザ付近でキャッシュされる キャッシュがへのクエリ転送を減らす 低人気コンテンツ ユーザ付近ではキャッシュされない クエリが集まる場所でキャッシュされる Page 11 NEC Corporation 2015 NEC Group Internal Use Only POP 方式に必要な記憶領域 コンテンツキャッシュ ルータ コンテンツ クエリ履歴 コンテンツ ID 2 個 100 個 コンテンツ応答 キャッシュルータリスト (CRL) クエリ キャッシュするルータ IP アドレス 制限なし CRL を用いてクエリ転送時にキャッシュ要と判断したルータにコンテンツを転送し, キャッシュする Page 12 NEC Corporation 2015 NEC Group Internal Use Only
POP 方式ルータ動作例 CRL 要素と自身のルータ ID を比較し一致する場合キャッシュ キャッシュ交換は要求頻度の低いものが対象 CRL 要素が登録されている場合優先して転送する コンテンツ ID n: ルータのキャッシュ可能数 Page 13 NEC Corporation 2015 NEC Group Internal Use Only シミュレーション条件 自作したシミュレータを用いて評価を行った ルータ (500 台 ) キャッシュ (2 個 ) クエリ保持履歴 (100 個 ) (500 台 ) 全ルータに 1 台配置管理コンテンツ数 (20 個 ) ユーザ全ルータに配置総リクエスト数 (100000 回 ) クエリサイズ (125 B) コンテンツ (10000 個 ) 人気度 (zipf 則 α=0.7) サイズ (125 kb) Waxman Model リンク数 (2000 本 ) 帯域 (1Gbps) Page 14 NEC Corporation 2015 NEC Group Internal Use Only
人気度係数とキャッシュヒット率の関係 zipf 則 : 0.7 0.6 MAX: 上位 1000 コンテンツのアクセス確率合計値 ( 理論上の最大ヒット率 ) MAX POP TERC 0.5 Cache Hit 0.4 0.3 0.2 0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Zipf Alpha POP 方式 : すべてのαで高キャッシュヒット率を示した α=0.1の時 : 付近にキャッシュされ TERCに比べ2.9 倍のヒット率 α=0.7の時 :POP 方式のキャッシュヒット率はTERCに比べて2.4 倍 MAXに対して71.7% のキャッシュヒット率 Page 15 NEC Corporation 2015 NEC Group Internal Use Only POP 方式のキャッシュ位置の考察 TERC 方式キャッシュ位置 : 経路上キャッシュ交換 : 多い POP 方式キャッシュ位置 : クエリの集まる場所キャッシュ交換 : 少ない * 人気度 10 位のコンテンツ Page 16 NEC Corporation 2015 NEC Group Internal Use Only
POP 方式の課題 数が少ない場合 キャッシュヒット率が大きく減少 POP 方式は 付近の人気度の偏りを利用して 多様なキャッシュを保持する方式 が少なくなると 人気度の高いコンテンツばかりがキャッシュされるようになる 0.35 0.3 0.25 キャッシュヒット率 0.2 0.15 0.1 TERC BC POP 0.05 0 0 100 200 300 400 500 600 台数 Page 17 NEC Corporation 2015 NEC Group Internal Use Only BC-POP 方式 キャッシュ手法である POP 方式 キャッシュ発見手法である BC 方式を組み合わせた BCPOP 方式 クエリ転送時 BC 方式と同様に,BC 情報を用いてクエリを誘導する BC 情報がないか, キャッシュヒットする場合のみクエリ履歴を更新 コンテンツ応答転送時 CRL 要素が有る場合のみ BC を作成 CRL:R3 BC Trail クエリ履歴更新 しない R1 BC 作成 する しない する する BCPOP 方式はキャッシュ生存時間が長いので BCTrail 上に複数個キャッシュを作成する必要がない R2 R3 R4 する する しない コンテンツ応答転送時にキャッシュするルータの有無を把握できるので必要最低限の BC を作成する Page 18 NEC Corporation 2015 NEC Group Internal Use Only
性能評価 ルータ (500 台 ) キャッシュ (2 個 ) クエリ保持履歴 (100 個 ) (50 台 ) 管理コンテンツ数 (200 個 ) ユーザ全ルータに配置総リクエスト数 (100000 回 ) クエリサイズ (125 Byte) コンテンツ (10000 個 ) 人気度 (zipf 則 α=0.7) サイズ (125 kb) Waxman Model リンク数 (2000 本 ) 帯域 (1Gbps) Page 19 NEC Corporation 2015 NEC Group Internal Use Only 主な評価結果 台数 50 台のときの評価結果 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 BC-POP 方式と BC 方式の比較 キャッシュヒット率 8.1ポイント向上交換回数を99.8% 軽減クエリホップ数 54% 軽減 コンテンツ人気度分布を変化させた際のキャッシュヒット率 0.5 0.45 0.4 BCPOP BC POP Cache Hit 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Zipf Alpha 横軸 : 0.1 コンテンツが均等にアクセスされる 0.9 一部コンテンツにアクセスが集中する 人気度係数が変化した際にも BC-POP 方式は高キャッシュヒット率を示した Page 20 NEC Corporation 2015 NEC Group Internal Use Only
台数変化とキャッシュヒット率の関係 1 台から 500 台に変化させた場合 0.35 0.3 BCPOP BC POP TERC 0.25 CacheHit 0.2 0.15 0.1 0.05 0 0 50 100 150 200 250 300 350 400 450 500 ServerNum BC-POP 方式はすべての台数で高キャッシュヒット率を示した Page 21 NEC Corporation 2015 NEC Group Internal Use Only キャッシュの多様性 シミュレーション終了時に ネットワーク内のキャッシュに残っていたコンテンツの種類 BC-POP BC POP 全種類中 702 582 577 上位 1000 コンテンツ中 309 181 246 BC-POP 方式は ネットワーク内に多様なコンテンツをキャッシュすることでキャッシュヒット率を向上キャッシュの発見には BC が効果を発揮 Page 22 NEC Corporation 2015 NEC Group Internal Use Only
リンクごとの転送パケット数 2.4e+006 2.2e+006 2e+006 BCPOP BC POP 1.8e+006 Packet 1.6e+006 1.4e+006 1.2e+006 1e+006 800000 600000 400000 0 50 100 150 200 Link ID Page 23 NEC Corporation 2015 NEC Group Internal Use Only ルータごとのキャッシュヒット数 500 450 400 BCPOP POP BC Router Cache Hit 350 300 250 200 150 100 50 0 0 50 100 150 200 250 300 350 400 450 500 Router Id Page 24 NEC Corporation 2015 NEC Group Internal Use Only
まとめ キャッシュ発見方式である Breadcrumbs と人気度推定によるキャッシュ方式 POP を組み合わせた BC-POP 方式を提案 BC 方式に比べ キャッシュヒット率を 8.1 ポイント向上 台数や人気度分布変化によらず高キャッシュヒット率を実現 BC 方式に比べ キャッシュ交換回数を 99.8% 減少でき, ルータ負荷を大きく削減 BC 方式に比べ クエリホップ数は 54% 減少し, 迅速なキャッシュ発見を実現 今後の課題 キャッシュヒット数が少ないルータの効果的な活用方法の検討 謝辞本研究の一部は, 独立行政法人情報通信研究機構 (NICT) の委託研究 新世代ネットワークを支えるネットワーク仮想化基盤技術の研究開発 の成果です. Page 25 NEC Corporation 2015 NEC Group Internal Use Only