ppt

Advanced Network
Architecture
Research Group
高速バックボーンネットワークにおける
公平性を考慮した
階層化パケットスケジューリング方式
大阪大学大学院基礎工学研究科
情報数理系専攻博士前期課程
牧一之進
2001/6/22
ネットワークシステム研究会
発表内容






研究の背景
研究の目的
階層化パケットスケジューリング方式の
提案
評価モデル
シミュレーションによる評価
まとめと今後の課題
2001/6/22
ネットワークシステム研究会
研究の背景

インターネットのインフラ化
ユーザのアクセス帯域の増加

特定のユーザのみが大きな帯域を占有

公平なインターネットの構築
各ユーザフローを公平にサービス
2001/6/22
ネットワークシステム研究会
従来の研究

CSFQ (Core Stateless Fair Queueing)


エッジルータでレートを測定してパケットヘッダに書きこむ
コアルータでそのレートをもとに動的に廃棄確率を決定する
ヘッダの拡張が必要であり、すべてのエッジ
ルータを更新する必要がある。

DRR (Deficit Round Robin)

フロー毎にキューを設けてスケジューリング
コアルータでもすべてのフローに対してキュー
を設ける必要があるので実装が困難
2001/6/22
ネットワークシステム研究会
研究の目的

ヘッダの拡張がなくフロー毎の情報をもた
ないパケットスケジューリング方式の提案


基本的にDRRのようなper-flowのスケジューリ
ング
扱うべきフロー数にしたがってフローを集約
エッジからコアまで適用できてスケーラブル
2001/6/22
ネットワークシステム研究会
提案方式(Hierarchically Aggregated
Fair Queuing)の概要(1/3)
HAFQ
各キューに収容された
1 フロー数を推定する
Zombie
List
2 2
Hashing
4 3 2 1
Input
Zombie
List
2
4 1 4 1
○
3 3
Zombie
List
1
各フローのパケットを振り分ける
2001/6/22
ネットワークシステム研究会
Output
提案方式(Hierarchically Aggregated
Fair Queuing)の概要(2/3)
Flow Id counter
3
1
2
7
1
5
4
7
ゾンビリスト : {Flow Id, counter}を
1つの組とする
過去に到着したフロー
に関する履歴
すべてのフローの情報は必要ない
 そのキューに収容されたフロー数を推定する
 同一キュー内でより多くの帯域を使用している
フローを発見する
2001/6/22
ネットワークシステム研究会
提案方式(Hierarchically Aggregated
Fair Queuing)の概要(3/3)
HAFQ
Zombie
List
フロー数に比例した帯域を
動的に割り当てる
2 2 1
Hashing
4 3 2 1
Input
Zombie
List
4 1 4 1
2
3 3 1
Zombie
List
2001/6/22
ネットワークシステム研究会
2 4 3 1 2
○
Output
ゾンビリスト(リスト内にIDがあるとき)
パケットがルータに到着したときのゾンビリストの動作
 ゾンビリストをすべて検索する
少ないエントリ数で、できる限り多くのフローを
管理する
Flow Id counter
Flow Id counter
3
3
1
1
2
Count Up
2
2
7
8
1
1
5
5
Hit
4
4
7
7

ゾンビリスト内に到着して来たフローのIDがあれば、
そのゾンビのカウンタ値を1増やす
2001/6/22
ネットワークシステム研究会
ゾンビリスト(リスト内にIDが存在しないとき)
Flow Id counter
3
1
2
7
1
5
4
7
3
Miss Hit
Swap
(Prob : q)
No-Swap
(Prob : 1-q)
Flow Id counter
3
1
1
3
1
5
4
7
Flow Id counter
3
1
2
7
1
5
4
7
ゾンビリスト内に到着して来たフローのIDがなければ、
q の確率で置き換え、カウンタ値を1に初期化する。
1-q の確率で何もしない。
2001/6/22
ネットワークシステム研究会
SREDのフロー数推定アルゴリズム
SREDのフロー数推定方式
各フローのレートがほぼ一定であると仮定
比較の際、同じ 2
である確率:
p (ヒット率)
Flow Id
2
5
7
2のある確率: 1/N
N : フロー数
N = 1/p
レートにかたよりがある場合、うまくいかない
2001/6/22
ネットワークシステム研究会
提案方式のフロー数推定アルゴリズム(1/2)
l
N
avg
=
i =1
l N
(1)
i
N
N = l l
i =1
i
avg
l
: フローi のレート
l avg : 全フローの平均レート
N : フロー数
i
フロー数 = 全到着レート / 全フローの平均レート
レートにかたよりがある場合にもフロー数を正しく推定できる
Ri を全到着レートに占めるフローi のレートの割合として、
Ravg から推定フロー数を求める
推定フロー数 = 1
2001/6/22
R
avg
ネットワークシステム研究会
提案方式のフロー数推定アルゴリズム(2/2)
R
i
の計算は、ゾンビの内容が置き換えられるときに行う
このときのカウンタ値が、そのフローのレートに比例
問題点
 レートの高いフローが存在する場合、他のフローよりも
多く平均到着割合に組み入れられる
平均をとるさいに、重みをつける
 フロー数がエントリ数より少ない場合、定常状態で
カウンタ値が発散してしまう
エントリ数を動的に減らし、常にフロー数がエントリ数
より大きくなるようにする
2001/6/22
ネットワークシステム研究会
カウンタによる廃棄


各キュー間の公平性は保たれる
ところが同一キュー内の公平性は Flow Id counter
1
3
保たれない
2
2
ゾンビのカウンタ値が大きければ大きい
5
14
ほど、そのフローは他のフローよりも多く
7
2
の帯域を使用
カウンタ値が大きいフローのパケットを
優先的に廃棄
2001/6/22
ネットワークシステム研究会
評価モデル(シングルリンクモデル)
Sender Hosts
S1
フロー数: 64本
帯域 : 155 [Mbps]
伝播遅延時間 : 1 [ms](bottleneck link) Receiver Hosts
0.1 [ms](access link)
R1
Bottleneck Link
Router
Router
S64
2001/6/22
R64
ネットワークシステム研究会
推定フロー数の評価
Number of flows
Number of flows
●1秒毎にフロー数を2倍にしていく、キュー数を1とし、ゾンビ数を4とする
TCP : 32本
TCPのみ64本
UDP(3.2Mbps) : 32本
100 SRED
100 SRED
HAFQ
HAFQ
80 HAFQ(DROP)
80 HAFQ(DROP)
60
40
20
0
0
60
40
20
2
4
6
Time(s)
8
10
0
0
2
4
6
Time(s)
8
SREDに比べてHAFQは推定フロー数が実際の数に近い
2001/6/22
ネットワークシステム研究会
10
各フローのスループットの評価
3.5
3
2.5
2
FIFO,TailDrop
HAFQ
HAFQ(DROP)
1.5
Throughput[Mbps]
Throughput[Mbps]
●各フローは同時に送信を開始する
TCPのみ64本
TCP : 32本
UDP(3.2Mbps) : 32本
3.5
3
2.5
2
1.5
1
0
FIFO,TailDrop
HAFQ
HAFQ(DROP)
1
10 20 30 40 50 60 70
0 10 20 30 40 50 60 70
Flow Id
Flow Id
レートの高いフローが存在する場合、HAFQ(DROP)では高い公平性を実現
2001/6/22
ネットワークシステム研究会
フロー数を変化させた場合の評価
TCPのみ
1
0.8
Fairness Index
Fairness Index
DRR: キュー数64とし、フロー数が64本を
越えるとき、ランダムにキューイング
HAFQ: CRC16でハッシング
キュー数64,ゾンビ数4
TCPとUDPが混在
1
0.8
0.6
0.6
FIFO,TailDrop
FIFO,TailDrop
DRR
0.4 DRR
0.4
HAFQ
HAFQ
HAFQ(DROP)
HAFQ(DROP)
0.2
0.2
1
4
16
64
256 1024
4 8 16 32 64 128 256 1024
Number of flows
Number of flows
HAFQ: DRRと同等の性能(フロー数が少ないとき)
従来手法に比べて高い公平性を実現(フロー数が多いとき)
2001/6/22
ネットワークシステム研究会
まとめと今後の課題

まとめ
エッジルータやコアルータの能力に応じて
スケーラブルに実装可能なパケットスケジュー
リング方式の提案
 フロー毎の優れた公平性を実現


今後の課題


2001/6/22
ルータを多段に配置した場合の影響
既存のルータと共存できるのか?
ネットワークシステム研究会

Download Report