router_cachehit.eps

Size: px

Start display at page:

Download "router_cachehit.eps"

さいぞうなかきむら
5 years ago
Views:

1 人気度推定を用いたキャッシュ方式とネットワーク誘導型キャッシュ発見方式の融合柳生智彦 (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

2 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 方式の問題点キャッシュの交換回数が多くルータ負荷が高いコンテンツ人気度を考慮しておらず, キャッシュヒット率が低い

3 従来のキャッシュ方式 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

4 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

5 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 の履歴を記憶クエリ受信回数の多いコンテンツをキャッシュする高人気コンテンツユーザ付近でキャッシュされるキャッシュがへのクエリ転送を減らす低人気コンテンツユーザ付近ではキャッシュされないクエリが集まる場所でキャッシュされる

6 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

Group Internal Use Only シミュレーション条件自作したシミュレータを用いて評価を行ったルータ (500 台 ) キャッシュ (2 個

(100000 回 ) クエリサイズ (125 B) コンテンツ (10000 個 ) 人気度 (zipf 則 α=0.

7 POP 方式ルータ動作例 CRL 要素と自身のルータ ID を比較し一致する場合キャッシュキャッシュ交換は要求頻度の低いものが対象 CRL 要素が登録されている場合優先して転送するコンテンツ ID n: ルータのキャッシュ可能数 Page 13 NEC Corporation 2015 NEC Group Internal Use Only シミュレーション条件自作したシミュレータを用いて評価を行ったルータ (500 台 ) キャッシュ (2 個 ) クエリ保持履歴 (100 個 ) (500 台 ) 全ルータに 1 台配置管理コンテンツ数 (20 個 ) ユーザ全ルータに配置総リクエスト数 ( 回 ) クエリサイズ (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.

8 人気度係数とキャッシュヒット率の関係 zipf 則 : MAX: 上位 1000 コンテンツのアクセス確率合計値 ( 理論上の最大ヒット率 ) MAX POP TERC 0.5 Cache Hit 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

9 POP 方式の課題数が少ない場合キャッシュヒット率が大きく減少 POP 方式は付近の人気度の偏りを利用して多様なキャッシュを保持する方式が少なくなると人気度の高いコンテンツばかりがキャッシュされるようになるキャッシュヒット率 TERC BC POP 台数 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.

10 性能評価ルータ (500 台 ) キャッシュ (2 個 ) クエリ保持履歴 (100 個 ) (50 台 ) 管理コンテンツ数 (200 個 ) ユーザ全ルータに配置総リクエスト数 ( 回 ) クエリサイズ (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 方式キャッシュヒット率キャッシュ交換回数クエリホップ数コンテンツホップ数ネットワーク負荷 76330GB 77923GB 75700GB BC-POP 方式と BC 方式の比較キャッシュヒット率 8.1ポイント向上交換回数を99.8% 軽減クエリホップ数 54% 軽減コンテンツ人気度分布を変化させた際のキャッシュヒット率 BCPOP BC POP Cache Hit Zipf Alpha 横軸 : 0.1 コンテンツが均等にアクセスされる 0.9 一部コンテンツにアクセスが集中する人気度係数が変化した際にも BC-POP 方式は高キャッシュヒット率を示した Page 20 NEC Corporation 2015 NEC Group Internal Use Only

11 台数変化とキャッシュヒット率の関係 1 台から 500 台に変化させた場合 BCPOP BC POP TERC 0.25 CacheHit ServerNum BC-POP 方式はすべての台数で高キャッシュヒット率を示した Page 21 NEC Corporation 2015 NEC Group Internal Use Only キャッシュの多様性シミュレーション終了時にネットワーク内のキャッシュに残っていたコンテンツの種類 BC-POP BC POP 全種類中上位 1000 コンテンツ中 BC-POP 方式はネットワーク内に多様なコンテンツをキャッシュすることでキャッシュヒット率を向上キャッシュの発見には BC が効果を発揮 Page 22 NEC Corporation 2015 NEC Group Internal Use Only

12 リンクごとの転送パケット数 2.4e e+006 2e+006 BCPOP BC POP 1.8e+006 Packet 1.6e e e+006 1e Link ID Page 23 NEC Corporation 2015 NEC Group Internal Use Only ルータごとのキャッシュヒット数 BCPOP POP BC Router Cache Hit Router Id Page 24 NEC Corporation 2015 NEC Group Internal Use Only

13 まとめキャッシュ発見方式である Breadcrumbs と人気度推定によるキャッシュ方式 POP を組み合わせた BC-POP 方式を提案 BC 方式に比べキャッシュヒット率を 8.1 ポイント向上台数や人気度分布変化によらず高キャッシュヒット率を実現 BC 方式に比べキャッシュ交換回数を 99.8% 減少でき, ルータ負荷を大きく削減 BC 方式に比べクエリホップ数は 54% 減少し, 迅速なキャッシュ発見を実現今後の課題キャッシュヒット数が少ないルータの効果的な活用方法の検討謝辞本研究の一部は, 独立行政法人情報通信研究機構 (NICT) の委託研究新世代ネットワークを支えるネットワーク仮想化基盤技術の研究開発の成果です. Page 25 NEC Corporation 2015 NEC Group Internal Use Only

2014 年電子情報通信学会総合大会ネットワークシステム B DNS ラウンドロビンと OpenFlow スイッチを用いた省電力法 Electric Power Reduc8on by DNS round- robin with OpenFlow switches 池田賢斗, 後藤滋樹

2014 年電子情報通信学会総合大会ネットワークシステム B DNS ラウンドロビンと OpenFlow スイッチを用いた省電力法 Electric Power Reduc8on by DNS round- robin with OpenFlow switches 池田賢斗, 後藤滋樹ネットワークシステム B- 6-164 DNS ラウンドロビンと OpenFlow スイッチを用いた省電力法 Electric Power Reduc8on by DNS round- robin with OpenFlow switches 池田賢斗, 後藤滋樹早稲田大学基幹理工学研究科情報理工学専攻 1 研究の背景 n インターネットトラフィックが増大世界の IP トラフィックは 2012