高速バックボーンネットワークにおける公平性を考慮した階層化パケットスケジューリング方式

Size: px

Start display at page:

Download "高速バックボーンネットワークにおける公平性を考慮した階層化パケットスケジューリング方式"

れいなふしはら
4 years ago
Views:

1 Advanced Network Architecture Research Group 高速バックボーンネットワークにおける公平性を考慮した階層化パケットスケジューリング方式大阪大学大学院基礎工学研究科情報数理系専攻博士前期課程牧一之進

2 発表内容研究の背景研究の目的階層化パケットスケジューリング方式の提案評価モデルシミュレーションによる評価まとめと今後の課題

3 研究の背景インターネットのインフラ化ユーザのアクセス帯域の増加特定のユーザのみが大きな帯域を占有公平なインターネットの構築各ユーザフローを公平にサービス

4 従来の研究 CSFQ (Core Stateless Fair Queueing) エッジルータでレートを測定してパケットヘッダに書きこむコアルータでそのレートをもとに動的に廃棄確率を決定するヘッダの拡張が必要でありすべてのエッジルータを更新する必要がある DRR (Deficit Round Robin) フロー毎にキューを設けてスケジューリングコアルータでもすべてのフローに対してキューを設ける必要があるので実装が困難

5 研究の目的ヘッダの拡張がなくフロー毎の情報をもたないパケットスケジューリング方式の提案基本的にDRRのようなper-flowのスケジューリング扱うべきフロー数にしたがってフローを集約エッジからコアまで適用できてスケーラブル

6 提案方式 (Hierarchically Aggregated Fair Queuing) の概要 (/3) HAFQ Zombie List 各キューに収容されたフロー数を推定する 4 3 Input Hashing Zombie List 4 4 Output Zombie List 3 3 各フローのパケットを振り分ける

7 提案方式 (Hierarchically Aggregated Fair Queuing) の概要 (/3) ゾンビリスト : {Flow Id, counter} をつの組とする過去に到着したフローに関する履歴 Flow Id 5 7 counter すべてのフローの情報は必要ないそのキューに収容されたフロー数を推定する同一キュー内でより多くの帯域を使用しているフローを発見する

8 提案方式 (Hierarchically Aggregated Fair Queuing) の概要 (3/3) HAFQ Zombie List フロー数に比例した帯域を動的に割り当てる 4 3 Input Hashing Zombie List Output Zombie List 3 3

9 ゾンビリスト ( リスト内に ID があるとき ) パケットがルータに到着したときのゾンビリストの動作ゾンビリストをすべて検索する少ないエントリ数でできる限り多くのフローを管理する Flow Id counter Flow Id counter 3 Count Up Hit ゾンビリスト内に到着して来たフローのIDがあればそのゾンビのカウンタ値を増やす

10 3 Miss Hit ゾンビリスト ( リスト内に ID が存在しないとき ) Flow Id 5 7 counter Swap (Prob : q) No-Swap (Prob : -q) Flow Id Flow Id 5 7 counter 3 4 counter ゾンビリスト内に到着して来たフローのIDがなければ q の確率で置き換えカウンタ値をに初期化する -q の確率で何もしない

11 比較の際同じである確率 : p ( ヒット率 ) SRED のフロー数推定アルゴリズム SRED のフロー数推定方式各フローのレートがほぼ一定であると仮定 Flow Id 5 7 N = /p のある確率 : /N N : フロー数レートにかたよりがある場合うまくいかない

12 λ 提案方式のフロー数推定アルゴリズム (/) avg N = = N i= N λ i N λ λ i avg i= () λ i λ avg : フロー i のレート : 全フローの平均レート N : フロー数フロー数 = 全到着レート / 全フローの平均レートレートにかたよりがある場合にもフロー数を正しく推定できる Ri を全到着レートに占めるフロー i のレートの割合としてから推定フロー数を求める推定フロー数 = Ravg Ravg

13 提案方式のフロー数推定アルゴリズム (/) Ri の計算はゾンビの内容が置き換えられるときに行うこのときのカウンタ値がそのフローのレートに比例問題点レートの高いフローが存在する場合他のフローよりも多く平均到着割合に組み入れられる平均をとるさいに重みをつけるフロー数がエントリ数より少ない場合定常状態でカウンタ値が発散してしまうエントリ数を動的に減らし常にフロー数がエントリ数より大きくなるようにする

14 カウンタによる廃棄各キュー間の公平性は保たれるところが同一キュー内の公平性は保たれないゾンビのカウンタ値が大きければ大きいほどそのフローは他のフローよりも多くの帯域を使用 Flow Idcounter カウンタ値が大きいフローのパケットを優先的に廃棄

15 評価モデル ( シングルリンクモデル ) Sender Hosts S フロー数 : 64 本帯域 : 55 [Mbps] 伝播遅延時間 : [ms](bottleneck link) 0. [ms](access link) Bottleneck Link Receiver Hosts R Router Router S64 R64

16 推定フロー数の評価 Number of flows 秒毎にフロー数を倍にしていくキュー数をとしゾンビ数を 4 とする TCPのみ64 本 SRED HAFQ HAFQ(DROP) Number of flows TCP : 3 本 UDP(3.Mbps) : 3 本 SRED HAFQ HAFQ(DROP) Time(s) Time(s) SRED に比べて HAFQ は推定フロー数が実際の数に近い

17 各フローのスループットの評価各フローは同時に送信を開始する TCPのみ64 本 TCP : 3 本 UDP(3.Mbps) : 3 本 Throughput[Mbps] Throughput[Mbps] FIFO,TailDrop FIFO,TailDrop.5 HAFQ.5 HAFQ HAFQ(DROP) HAFQ(DROP) Flow Id Flow Id レートの高いフローが存在する場合 HAFQ(DROP) では高い公平性を実現

18 Fairness Index 0.8 フロー数を変化させた場合の評価 DRR: キュー数 64 としフロー数が 64 本を越えるときランダムにキューイング TCP のみ 0.6 FIFO,TailDrop 0.4 DRR HAFQ HAFQ(DROP) Number of flows Fairness Index 0.8 HAFQ: CRC6 でハッシングキュー数 64, ゾンビ数 4 TCP と UDP が混在 0.6 FIFO,TailDrop DRR 0.4 HAFQ HAFQ(DROP) Number of flows HAFQ: DRRと同等の性能 ( フロー数が少ないとき ) 従来手法に比べて高い公平性を実現 ( フロー数が多いとき )

19 まとめと今後の課題まとめエッジルータやコアルータの能力に応じてスケーラブルに実装可能なパケットスケジューリング方式の提案フロー毎の優れた公平性を実現今後の課題ルータを多段に配置した場合の影響既存のルータと共存できるのか?

公平なネットワーク利用を実現するスケーラブルなパケットスケジューリング方式

公平なネットワーク利用を実現するスケーラブルなパケットスケジューリング方式 Hierarchically Aggregated Fair Queuing (HAFQ) for Per-flow Fair Service in High-speed Networks 大阪大学大学院基礎工学研究科情報数理系専攻博士前期課程 2 年牧一之進 2018/8/28 信学会全国大会 1 発表内容研究の背景研究の目的