ppt

転送データサイズの違いによる
TCPコネクション間の
不公平性に関する一検討
大阪大学大学院基礎工学研究科
博士前期課程1年徳田航一
E-mail : [email protected]
1
発表内容
•
•
•
•
•
•
研究の背景
転送データサイズの違いによる不公平性
hash-RED方式の提案
TCPスループット解析
シミュレーションによる提案方式の評価
まとめと今後の課題
2
研究の背景(1)
• TCP (Transmission Control Protocol)
– インターネットトラヒックの大部分を占める
– ACKパケットを用いた輻輳制御を行う
• さまざまな原因によってスループットの不
公平が生じる
3
研究の背景(2)
• 転送データサイズの違いによるスループッ
トの不公平
– 帯域や遅延などのネットワーク環境が同じで
も発生
• long-livedコネクション
– 転送データサイズの大きなコネクション
• short-livedコネクション
– 転送データサイズの小さなコネクション
4
研究の目的
• エンドホストの変更を行うことなく転送デー
タサイズの違いによる不公平を改善
– long-livedコネクションとshort-livedコネクショ
ンの判別をどのように行うのか
– short-livedコネクションの優先処理をどのよう
に行うのか
5
シミュレーションによる
不公平の確認
• ルータのバッファサイズ
– TCPのスループットを抑えないように大きく設
定する
• パケット廃棄
– 送信側ホストとルータ間に一定のリンクロスp
によって生じる
Sender host
500 [Mbps]
50 [msec]
リンクロス率：p
Receiver host
500 [Mbps]
50 [msec]
6
転送パケット数とスループット
の関係
Throughput [Kbps]
2500
2000
p=0.005
p=0.01
p=0.05
1500
1000
500
0
1
10
100
Data Size [packets]
1000
10000
7
不公平が生じる原因
• long-livedコネクション
– 転送中にウィンドウサイズが大きくなる
– fast retransmit アルゴリズムによりタイムアウ
トを回避することができる
• short-livedコネクション
– ウィンドウサイズが大きくなる前に転送終了
– fast retransmit アルゴリズムが機能しにくい
ため、タイムアウトになりやすい
8
hash-RED方式の提案
• パケット判別処理
– hashテーブルを用いる
• パケット優先処理
– RED (Random Early Detection) をベースに
した方式を用いる
• 二つの処理の組み合わせによって公平性
を改善する
9
パケット判別処理
• コネクションIDを基にハッシュ関数を計算
• 関数値によりテーブルのエントリの決定
• 閾値K以上であるとlong-livedコネクション
と判断
time stamp counter
パケット
ハッシュ関数
time stamp counter 10
パケット優先処理
• パケット廃棄率に差をつける
– short-livedコネクションからのパケット
• バッファ溢れが起きない限り廃棄しない
– long-livedコネクションからのパケット
• 高い確率で廃棄
• 全体の廃棄率が通常のREDによる廃棄率pと同じ
になるように設定
long-livedコネクションとshortlivedコネクションの閾値Kは？
11
閾値Kの決定方法
• Fairness index F(K)の定義
F ( K )  lim
L 
L
2
P
(
i
)

(

(
i
)


(
L
))

i 1
• P(i) : 転送パケット数が i パケットである確率
– Webトラヒック分布を示した文献[9]より求める。
[9] Paul Barford and Mark E. Crovella, “Generating Representative Web Workloads for
Network and Server,“in Proceedings of Performance ’98/ACM SIGMETRICS, June 1998.
• ρ(i) : i パケット転送したときのスループット
– 次に述べる解析により求める
12
TCPスループット解析(1)
• 文献 [5]
– パケット廃棄率一定
– 定常状態におけるTCPのスループット
• 文献 [6]
– 文献 [5]の解析にコネクション確立直後のス
ロースタートフェーズも含める。
[5] J. Padye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP Throughput: A Simple
Model and its Empirical Validation, “in Proceedings of ACM SIGCOMM’98, Sept. 1998.
[6] N. Cardwell, S. Savage, and T. Anderson, “Modeling TCP Latency,”
in Proceedings of IEEE INFOCOM’00, pp. 249-271, Mar. 2000
13
TCPスループット解析(2)
• hash-RED方式
– パケット廃棄率を転送中に変化させる
• 文献[5]と[6]を拡張
– パケット廃棄率がパケットごとに変化する場合
を想定
– コネクション確立直後のスロースタート及び輻
輳回避フェーズのより正確なモデル化
14
解析の数値例
700
Simulation
1200 Analysis of [6]
1000 Our analysis
Throughput [Kbps]
Throughput [Kbps]
1400
800
600
400
200
0
1
10
100
1000
10000
600
500
Simulation
Our analysis
400
300
200
100
0
1
10
100
1000
10000
Data Size [packets]
Data Size [packets]
廃棄率p=0.01の場合
0-20パケット目まで廃棄率0
21パケット目以降は廃棄率0.03
15
閾値Kの決定方法
• Fairness index F(K)の定義
F ( K )  lim
L 
L
2
P
(
i
)

(

(
i
)


(
L
))

i 1
• P(i) : 転送パケット数が i パケットである確率
– Webトラヒック分布を示した文献[1]より求める。
[１] Paul Barford and Mark E. Crovella, “Generating Representative Web Workloads for
Network and Server,“in Proceedings of Performance ’98/ACM SIGMETRICS, June 1998.
• ρ(i) : i パケット転送したときのスループット
– 次に述べる解析により求める
16
KとF(K)の関係
F(K)
• F(K)が最小になるように閾値Kを決定する
2.6e+009
2.4e+009
2.2e+009
2e+009
1.8e+009
1.6e+009
1.4e+009
1.2e+009
1e+009
8e+008
0
p=0.01
p=0.02
p=0.03
p=0.04
p=0.05
20
40
60
K [packets]
80
100
17
シミュレーションモデル
• 提案方式の評価は、以下のモデルを用い
る
• ルータAに提案方式を適用する
R1
S1
100 [Mbps]
5 [msec]
S100
BW [Mbps]
30 [msec]
Router A
300 [packets]
Router B
300 [packets]
100 [Mbps]
5 [msec]
R100
パケット判別処理の評価
転送データサイズ分布
long-lived
connection
short-lived
connection
Data size
Pareto
Avg=1000[KB]
Shape=1.13
Pareto
Avg=10[KB
]
Shape=1.13
Think
Time
Pareto
Avg=20[s]
Shape=1.5
Pareto
Avg=2[s]
Shape=1.85
Estimated ratio
of long-lived connections
• long-livedコネクションのホスト数とルータ
でlong-livedコネクションと判定される割合
の関係
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Actual ratio of long-lived connections
公平性の評価
• 転送ドキュメントサイズがWebドキュメント
分布に従った環境でのシミュレーション
ボトルネックリンクの利用率
Tail-drop
0.954
hash-RED 0.952
Throughput [Kbps]
40
35
30
Taildrop
hash-RED
25
20
15
10
5
1
10
100
Data Size [packets]
1000
まとめと今後の課題
• まとめ
– hash-RED方式の提案
– エンドホストの変更をすることなく、short-lived
コネクションの不公平性を改善
• 今後の課題
– 詳細な評価
– 提案方式の実装
21

Download Report