トランスポート層 TCP輻輳制御（3.7）

Size: px

Start display at page:

Download "トランスポート層 TCP輻輳制御（3.7）"

もりよりたておか
4 years ago
Views:

情報指向ネットワークへの適正と実現可能性を有するに基づいた置換方式の提案と評価大岡睦, オムスーヨン, 阿多信吾, 村田正幸大阪大学大学院情報科学研究科大阪市立大学大学院工学研究科発表内容研究背景 ICN ルータにおけるキャッシング置換方式の課題提案手法 CUSH ( Usig Switchig Hash-tables) 評価ネットワークトラフィックに適した戦略

大量のコンテンツに対してルータのメモリ資源は有限ルータサーバ ame: /movie/olympic.mp マルチキャスト /movie/olympic.

1 情報指向ネットワークへの適正と実現可能性を有するに基づいた置換方式の提案と評価大岡睦, オムスーヨン, 阿多信吾, 村田正幸大阪大学大学院情報科学研究科大阪市立大学大学院工学研究科発表内容研究背景 ICN ルータにおけるキャッシング置換方式の課題提案手法 CUSH ( Usig Switchig Hash-tables) 評価ネットワークトラフィックに適した戦略ルータで実現可能な低コストの実装既存方式との性能比較実装コスト 0// 月 ICN 研究会情報指向ネットワーク (ICN) ICN におけるキャッシングの課題ホスト中心ではなくコンテンツ中心コンテンツ拡散型の利用形態を支援 Iterest 要求集約 Data マルチキャストネットワーク内キャッシング要求集約キャッシング Iterest Data 資源が限られた状況下でのキャッシング大量のコンテンツに対してルータのメモリ資源は有限ルータサーバ ame: /movie/olympic.mp マルチキャスト /movie/olympic.mp 置換方式人気のあるコンテンツのみを配置判断方式複数のルータでを分散 0// 月 ICN 研究会 0// 月 ICN 研究会置換方式の実現課題ネットワークトラフィックの特性 ICN ルータハードウェアにおける実現性 LFU や人気度を計測する方式は過剰なメモリ計算コストが必要でも高速アクセスが必須な環境では実現が困難例 : スタックの実装 ( 右図 ) スタック ew old 0 hit コンテンツの人気度に大きな偏りがある [] コンテンツ全体の約 90% が度しか要求されないワンタイマーコンテンツがトラフィックの 0% を占める既存の単純な方式はネットワークに不適人気のコンテンツ ew E D C B A old LFU 過去に人気だったコンテンツ E D C B A ネットワークトラフィックへの適正ワンタイマーアクセス (sca) への耐性チャンク単位アクセス (loop) への耐性 FIFO Radom などの単純な手法は耐性を持たない 0 大量ののシフトコピーが必要アクセス z y x E D 人気の無いコンテンツによって人気のコンテンツが溢れる x y z アクセス E D C B y 過去に人気だったコンテンツがを占領してしまう x x y 0// 月 ICN 研究会 []F. Guillemi, et al, Experimetal aalysis of cachig efficiecy for YouTube traffic i a ISP etwork, i Proceedigs of the th Iteratioal Teletraffic Cogress, September 0, pp. 9. 0// 月 ICN 研究会

2 研究の目的とアプローチ目的 ICN ルータにおける置換方式の実現ルータハードウェアでの実現可能な低コストネットワークトラフィックへの適正アプローチ LIRS/ [,] に注目 sca 耐性と loop 耐性を実現などの管理のための計算メモリコストが課題ルータにおいて実現可能な CUSH を提案評価 CUSH: CLOCK-pro Usig Switchig Hash-tables LIRS/ の長所を強化しネットワーク適性を実現によるへのオーバーヘッドを削減 []F. N. Megiddo, et al, ARC: a self-tuig, low overhead replacemet cache, i Proceedigs of the rd USENIX Coferece o File ad Storage T echologies, March 00, pp. -0. [] S. Basal ad D.S. Modha, CAR: Clock with adaptive replacemet, i Proceedigs of the rd USENIX Coferece o File ad Storage T echologies, pp.87 00, March 00. 0// 月 ICN 研究会 CLOCK の特徴各エントリに参照ビットを設定各エントリあたり bit だけのメモリオーバーヘッドヒット時には参照ビットをに変更するだけの計算オーバーヘッド時計の針のように円環バッファを巡回することでを近似参照ビットが 0 のエントリを優先的に削除参照ビットがのエントリは 0 にリセットして無視 0 ew old CLOCK // 月 ICN 研究会 0 ヒット時には参照ビットを設定するだけアクセスパターン sca による悪影響 LIRS/ の sca 耐性多量のワンタイムコンテンツへの要求でが溢れるコンテンツを hot ( 人気 ) と cold ( 不人気 ) の二種類に分類人気コンテンツ人気コンテンツ不人気なコンテンツ sca: 多量のワンタイムコンテンツへの要求列不人気なコンテンツ sca: 多量のワンタイムコンテンツへの要求列スタック : cold スタック : hot スタック : 人気のコンテンツがから溢れる人気のコンテンツは hot チャンクに昇格ワンタイムコンテンツを無視して人気コンテンツを保持できる 0 アクセスパターン loop による悪影響 LIRS/ の loop 耐性毎回溢れが起きるようなアクセスの繰り返し大容量コンテンツへのチャンク単位アクセスによって発生を活用して適切な数の hot チャンクのみを保持 loop 7 loop cold スタック : 単純なスタック戦略 : (ARC, CAR など ) 再アクセスされる前にから溢れる hot スタック : : を用いて hot に昇格し溢れそうになるとと cold を削除

3 のデータ構造と課題数を超える長さの loop に対処できないのオーバーヘッドが大きいで用の ame を保持する必要がある数が多いほど CLOCK リストが肥大化し巡回のための計算コストが大きくなる (ame) /A.mpg/s /A.mpg/s /B.mpg/s /B.mpg/s 7 log[bit] 改変 CLOCK リスト HAND hot HAND cold HAND test つの制御参照ビットビットを各 hot/cold 識別ビットエントリに割当 test フラグルータハードウェアでの実装を考慮した LIRS/ の近似アルゴリズムの特徴を引き継ぎ sca 耐性を実現 loop 耐性を低オーバーヘッドに拡張可能ののオーバーヘッドを削減用のエントリと用のエントリを分離用のエントリは衝突ありのハッシュテーブルとして保持過去にアクセスがあったか否かを bit で管理 loop 耐性のために数を増やしても巡回コストが増大しない用エントリ用エントリ用エントリ CUSH + (H(ame)) (H(ame)) 用エントリ CUSH のデータ構造のオーバーヘッド削減 (ame) (ame) Circular buffer hads (ame) (ame) Circular buffer hads log[bit] log [bit] log[bit] log [bit] hads ハッシュテーブル (H(ame)) ハッシュテーブル (H(ame)) 交互に利用削除用のエントリを無くしの負荷を削減ハッシュテーブル hads (H(ame)) ハッシュテーブル (H(ame)) 交互に削除 k k [bit] [bit] [bit] [bit] CLOCK リストのオーバーヘッド削減 (ame) hads log[bit] k (ame) log [bit] Circular buffer hads 交互に削除用のエントリを無くしハッシュテーブルハッシュテーブル削除用の針 (HAND test ) も削除できるため巡回のための計算コストを大幅に削減 (H(ame)) (H(ame)) ハッシュテーブルを用いたの実装コンテンツ名のハッシュ値 H ame と対応するアドレスにを保持 loop の繰り返しが検出できればよいので bit の情報で十分検索計算オーバーヘッドが小さく拡張性が高いつのハッシュテーブルを交互に利用削除に登録されてすぐにから削除されることを防ぐ人気コンテンツを hot チャンクに分類しやすくなる k ハッシュテーブル (H(ame)) (H(ame)) 交互に利用削除ハッシュテーブル 7 [bit] [bit] [bit] [bit]

8 9 評価評価環境ネットワークへの適性の評価トポロジー : 単一ノードトポロジーシミュレーションを用いたヒット率評価比較方式最適手法 : OPT ハードウェアでの実現可能性の評価単純な方式 : FIFO CLOCK 空間計算量 sca 耐性を持つ方式 : Compact CAR と管理のための追加ビット数を評価計算量提案方式と元となった方式 : CUSH,

4 8 9 評価評価環境ネットワークへの適性の評価トポロジー : 単一ノードトポロジーシミュレーションを用いたヒット率評価比較方式最適手法 : OPT ハードウェアでの実現可能性の評価単純な方式 : FIFO CLOCK 空間計算量 sca 耐性を持つ方式 : Compact CAR と管理のための追加ビット数を評価計算量提案方式と元となった方式 : CUSH, は衝突有りハッシュテーブルで実装針の平均回転数に基いて評価トレースデータ Zipf 則に従って人工的に生成したトレース阪大キャンパスの YouTube へのアクセスに基づくトレースの設定 : コンテンツ単位とチャンク単位チャンク単位ではコンテンツをチャンクサイズで分割 00 Byte KB 0 KB の通り 0// 月 ICN 研究会 0// 月 ICN 研究会 0 人工的なトレース ( コンテンツ単位 ) の場合人工的なトレース ( チャンク単位 ) の場合 CUSH は単純な方式と比較して倍程度の効率 CUSH がと同等の性能を達成サイズが小さい状況でも loop を可能単純な方式はサイズが大きくなるまでヒット率が 0 人工トレース (α =.0): コンテンツ単位の評価結果 ( 左 : 単純な方式との比較右 : との比較 ) 0// 月 ICN 研究会人工トレース (α =.): チャンク単位の評価結果 ( 左 : 単純な方式との比較右 : との比較 ) 0// 月 ICN 研究会単一ノードの評価結果 : 実トレースデータの場合置換方式の空間計算量の評価人工トレースとほぼ同じ結果 CUSH は人気度の頻繁な移り変わりに対応できるようにアルゴリズムに工夫を加えているためよりヒット率が高いサイズの場合のメモリオーバーヘッドを評価 CUSH は k 個のを有すると仮定各用途ごとの置換方式の空間計算量置換方式の管理の管理用の DLL O( log ) - - CLOCK O() - - O() O() O( log ) CUSH O() O(k ) - CLOCK と同等の管理コスト用のへのコストを削除実トレース : コンテンツ単位実トレース : チャンク単位 0// 月 ICN 研究会 0// 月 ICN 研究会

5 ミス時の計算量の評価針の平均回転数に基いて計算量を評価針の回転数はにセットされた参照ビットの数に応じて増えるためヒット率を変えて評価最悪回転数は針が CLOCK リストを一周する場合なので自明ヒット時は参照ビットをにするだけなので自明 CLOCK と同等の計算量を達成数百回の回転を要すると比較して大幅な削減ミス時の針の平均回転数ヒット率 CLOCK CUSH Compact CAR まとめと今後の課題まとめ ICN ルータでの実装を考慮した置換方式を提案 sca 耐性と loop 耐性によってネットワークへの適正を実現のオーバーヘッドを削減して低コストに拡張可能なデータ構造とアルゴリズムを実現提案方式のネットワークトラフィックへの適正を評価 CUSH は元となったと同等の性能を達成単純な方式ではヒットできないアクセスパターンに対処可能今後の課題 CUSH のハードウェアアーキテクチャの考察配置判断方式と組み合わせた場合の性能評価 0// 月 ICN 研究会 0// 月 ICN 研究会 CUSH の特徴ネットワークへの適性 sca 耐性を実現しワンタイムアクセスに強い用ハッシュテーブルをつ交互に用いることで hot チャンクの検出性能も向上 loop 耐性を実現しチャンク単位アクセスに強い loop 耐性向上のための拡張コストが小さいエントリとエントリを分離しても loop 耐性を維持できるアルゴリズムを提案人気の頻繁な移り変わりに強い人気の頻繁な移り変わりに弱いからアルゴリズムを改善ルータでの実装オーバーヘッド CLOCK と同等のメモリ計算オーバーヘッド実装のためのオーバーヘッドを大幅削減 7 0// 月 ICN 研究会 0// 月 ICN 研究会 8 9 loop 耐性実現のための適切な削除 CUSH の loop 耐性 CUSH はとを分離したための削除を行う機構を引き継げない適切なタイミングでを削除しなければ hot チャンクが溢れてしまう LIRS ではスタックの順序によって管理では CLOCK リスト順序と test flag によって管理を活用して適切な数の hot チャンクのみを保持 loop ヒット数に応じてを削除することで動作を再現 hot チャンク数と同数のヒットがあった場合にを削除 cold スタック : hot スタック : : ヒット数が hot スタックサイズを超えた時点でを削除 0// 月 ICN 研究会

0 提案方式の位置づけと CLOCK のオーバーヘッドの比較チャンク単位のアクセスに対処可能 Performace ルータで実現可能ルータで実現不可能統計データに基づく手法 loopresitat CUSH(Proposal) LIRS ループ耐性が限定的人気度の移り変わりに弱い scaresitat Compact CAR CLOCK CAR (DLL) ARC LFU

6 0 提案方式の位置づけと CLOCK のオーバーヘッドの比較チャンク単位のアクセスに対処可能 Performace ルータで実現可能ルータで実現不可能統計データに基づく手法 loopresitat CUSH(Proposal) LIRS ループ耐性が限定的人気度の移り変わりに弱い scaresitat Compact CAR CLOCK CAR (DLL) ARC LFU (Couter) rececybased based CLOCKbased others 近似手法 simple FIFO 空間計算量 : O() O( log ) O( log ) Cost 計算量 : O() O() O(log ) CUSH の空間計算量オーバーヘッド処理速度の要件から SRAM ( 最大 0 Mbit) を利用既存研究で実現可能とされる 0 7 エントリを想定による検索機構へのオーバーヘッドを含めるとは SRAM の容量を超過 CUSH はを倍まで拡張しても SRAM の最大容量内に収容可能

Zipf [5] 2 5 [6] [7][11] ICN [12] LIRS/CLOCK-Pro [13], [14] CLOCK-Pro Using Switching Hash-table (CUSH) (3. )4. CUSH ICN 2. CPU [15] [17] LRU [1], [18

Zipf [5] 2 5 [6] [7][11] ICN [12] LIRS/CLOCK-Pro [13], [14] CLOCK-Pro Using Switching Hash-table (CUSH) (3. )4. CUSH ICN 2. CPU [15] [17] LRU [1], [18 CLOCK-Pro 565-871 1-5 558-8585 3-3-138 E-mail: {a-ooka,suyong,murata}@ist.osaka-u.ac.jp, ata@info.eng.osaka-cu.ac.jp (ICN) CLOCK-Pro ICN CLOCK-Pro Using Switching Hash-table (CUSH) (ICN) (CCN) A Proposal