ｽﾗｲﾄﾞﾀｲﾄﾙなし

Size: px

Start display at page:

Download "ｽﾗｲﾄﾞﾀｲﾄﾙなし"

あいりいいはた
5 years ago
Views:

1 画像情報特論 () Hybrid TCP 情報理工学専攻甲藤二郎

2 ネットワークシミュレーション & エミュレーション

3 ネットワークの研究アルゴリズム理論解析シミュレーションエミュレーション実装

4 シミュレータとエミュレータ (1) シミュレーションエミュレーションソフトウェア PC / 専用機ノード実機 NIC 1 5

5 シミュレータとエミュレータ () シミュレータエミュレータ URL ns- (ns) (nse) ns-3 OPNET Qualnet, GloMoSim Scenergie EXata PacketStorm Cloud

6 Ns- (1)

7 Ns- () ダウンロードサイト.9 以降 : 以前 : allinone をダウンロード展開 configure makeするのが楽 (Tcl/Tk, Otcl, TclCL, ns, nam)

8 Ns- (3) ns- Architecture ns- OTcl Simulation Objects (C++) TclCL Simulation Objects (Otcl) txt Simulation Scripts ns- shell executable command Simulation Trace File nam (animation) awk & gnuplot (graph)

9 Ns- (4) Simulation scripts (*.tcl) # パラメータの初期設定 # Simulatorオブジェクトの生成 set ns [ new Simulator ] # ネットワークトポロジの定義 # エージェントやアプリケーションの定義 # プロシージャの定義 (finish 等 ) proc finish () # イベント定義 $ns at 1.0 $ftp start # シミュレーション開始 $ns run set ns [new Simulator] set f [open out.tr w] $ns trace-all $f set n0 [$ns node] set n1 [$ns node] $ns duplex-link $n0 $n1 100Mb 1ms DropTail set udp0 [new Agent/UDP] $ns attach-agent $n0 $udp0 set cbr0 [new Application/Traffic/CBR] $cbr0 attach-agent $udp0

10 Ns- (5) Simulation Objects (C++/OTcl) C++ static class XXXTcpClass : public TclClass { public: XXXTcpClass() : TclClass("Agent/TCP/XXX") {} TclObject* create(int, const char*const*) { return (new XXXTcpAgent()); } } class_xxx; OTcl set tcp [new Agent/TCP/XXX] XXXTCPAgent Agent/TCP/XXX TclObject TclClass

11 Ns- (6) Simulation Objects (C++/OTcl) C++ class XXXTcpAgent : public TcpAgent { public: XXXTcpAgent(); virtual void recv(packet *pkt, Handler*); virtual void dupack_action(); virtual void timeout (int tno); virtual void opencwnd(); protected: int command(int argc, const char*const* argv); XXXTCPAgent method recv timeout command dupack_action opencwnd } double fr_amin_; double fr_amax_; double fr_prev_; variables fr_amin fr_amax fr_prev

12 Ns- (7) Simulation Objects (C++/OTcl) C++ OTcl XXXTcpAgent::XXXTcpAgent() { bind("fr_amin_", &fr_amin_); bind("fr_amax_", &fr_amax_); } XXXTCPAgent::command(int argc, const char*const* argv) { if (argc == 3) { } if ( strcmp(argv[1], target ) == 0 ) { } } return (NsObject::command(argc,argv)); XXXTCPAgent command fr_amin set tcp [new Agent/TCP/XXX] $tcp set fid_ 1 $tcp set fr_amin_ 0. $tcp set fr_amax_ 0.8 $tcp target [new Agent/Null] fr_amax bind Agent/TCP/XXX fr_amin_ fr_amax_

13 Ns- (8) Trace File (*.tr) enqueue dequeue receive drop cbr cbr r cbr r ack tcp tcp r cbr cbr d cbr cbr r cbr

14 Ns- (9) Awk / Perl スクリプトを用いたトレースファイルの整形 Gnuplot などに合わせた出力 *.tr Awk / Perl Gnuplot / Excel グラフ

15 結果の例 Ns- (10)

16 電子情報通信学会ネットワークシステム研究会アーカイブ s.html 009/8: ns- ( サマースクール ) 009/8: OPNET ( サマースクール ) 009/1: Qualnet ( チュートリアル ) その他 ns- チュートリアルなどで検索をかければ情報多数 ns-3の情報はまだ少ないチャンス

17 TCP Variants

18 TCP-Reno (loss-driven) cwnd ロスロスロス a=1 バッファ b=0.5 0 BDP increase: cwnd = cwnd + 1/cwnd decrease: cwnd = cwnd / n AIMD: additive increase multiplicative decrease

19 TCP-Vegas (delay-driven) cwnd バッファバッファ内滞留パケット α BDP n 0 e.g. α=1, β=3 diff = cwnd RTT min cwnd RTT RTT min バッファ内滞留パケット数 increase: cwnd = cwnd + 1 cwnd cwnd 1 diff < α otherwise diff > β decrease: cwnd = cwnd *0.75

20 10 年前の TCP の課題有線ネットワークの高速化ウィンドウの増加が追い付かない ( 非効率性 ) 無線ネットワークの普及無線エラーとバッファオーバーフローを区別できない TCP-Reno (NewReno, SACK) の支配 Reno は Vegas を排除する ( 非親和性 )

21 000 年代の TCP Variants Loss-driven (AIMD) TCP-Reno / NewReno / SACK High-Speed TCP (IETF RFC 3649, Dec 003) Scalable TCP (PFLDnet 003) BIC-TCP / CUBIC-TCP (IEEE INFOCOM 004, PFLDnet 005)... Linux H-TCP (PFLDnet 004) TCP-Westwood (ACM MOBICOM 001) Delay-driven (RTT Observation) TCP-Vegas (IEEE JSAC, Oct 1995) FAST-TCP (INFOCOM 004) Hybrid Gentle High-Speed TCP (PfHSN 003) TCP-Africa (IEEE INFOCOM 005) Compound TCP (PFLDnet 006)... Windows Adaptive Reno (PFLDnet 006) YeAH-TCP (PFLDnet 007) TCP-Fusion (PFLDnet 007)

22 Loss-driven TCPs aggressive adaptive a Variants Increase / Update Decrease TCP-Reno HighSpeed TCP (HS-TCP) w a( w) = b( w) p( w) b( w) e.g. 70 (10Gbps, 100ms) Scalable TCP (STCP) 0.01 (per every ACK) BIC-TCP CUBIC-TCP additive increase ( fast) binary search ( slow) max probing ( fast) w = ( t 3 W max ) Wmax H-TCP α ( 1 β ){ ( t TH )} TCP-Westwood (TCPW) 1 b log( w) log( Wlow ) b( w) = ( bhigh 0.5) log( W ) log( W ) high low e.g. 0.1 (10Gbps, 100ms) β RTT RTT RE * RTT BE * RTT min max min min B( k + 1) B( k) for B( k) / PS / PS otherwise ( congested) > ( not congested)

23 Delay-driven TCPs Variants Update Decrease TCP-Vegas + ) ( 1 ) ( ) ( 1 congestion early w stable w congestion no w w 0.75 FAST-TCP + + α γ γ w RTT RTT w w w min ) (1, min 0.5 (?) a b

24 Hybrid TCP cwnd ロスロスロスバッファ 0 BDP n RTT 増加なし : ロスモード親和性の改善 RTT 増加あり : 遅延モード効率性の改善

25 Hybrid TCPs a b simple adaptive Variants Increase Decrease Gentle HS-TCP HS-TCP / Reno HS-TCP TCP-Africa HS-TCP / Reno HS-TCP Compound TCP (CTCP) 0.15 cwnd / Reno 0.5 Adaptive Reno (ARENO) YeAH-TCP TCP-Fusion B /10Mbps / Reno STCP / Reno B * D PS min RTT RTT max min ( non congestion loss) ( congestion loss), 0.5 / Reno RTTmin max, 0.5 RTT

26 CUBIC-TCP

27 BIC-TCP (1) Binary Increase Congestion Control パケットロスが発生した cwnd 平衡点 L.Xu et al: Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks, IEEE INFOCOM 004.

28 BIC-TCP () Window Increase concave additive increase (linear increase) Wmax: 直前にパケット廃棄が起きた cwnd Smax: cwnd 増加の最大値 (e.g. 3) Smin: cwnd 増加の最小値 (e.g. 0.01) convex if (cwnd < Wmax ) Winc = (Wmax cwnd) / ; else Winc = (cwnd - Wmax) / ; if (Winc > Smax) Winc = Smax; elseif (Winc < Smin) Winc = Smin; binary search cwnd = cwnd + Winc / cwnd; L.Xu et al: Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks, IEEE INFOCOM 004.

29 BIC-TCP (3) Window Decrease Wmax=target cwnd を更新ロス 1 Wmax,new=0.9*cwnd ロス Wmax,new=cwnd if (cwnd < Wmax ) Wmax,new = cwnd * (-β) / ; else Wmax,new = cwnd; cwnd = cwnd * (1- β); β: 減少率 (e.g. 0.) *0.9: 新規参入フローに帯域を与える... Fast Convergence L.Xu et al: Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks, IEEE INFOCOM 004.

30 CUBIC-TCP (1) Cubic approximation of BIC-TCP S.Ha et al: CUBIC: A New TCP Friendly HighSpeed TCP Variant, ACM SIGOPS Review, 008.

31 CUBIC-TCP () Window Increase W(t) /* cubic function */ Winc = W(t+RTT) cwnd; cwnd = cwnd + Winc / cwnd; K Wmax*(1-β) 3 W ( t) = C *( t K) + Wmax W 3 maxβ Renoに等価 K = C β t W tcp ( t) = Wmax (1 β ) + 3 β RTT /* TCP mode */ if ( Wtcp > cwnd ) cwnd = Wtcp; Window Decrease は BIC と同じ β: 減少率 (e.g. 0.) C: 定数 (e.g. 0.4) S.Ha et al: CUBIC: A New TCP Friendly HighSpeed TCP Variant, ACM SIGOPS Review, 008.

32 CUBIC-TCP (3) CUBIC の挙動 S.Ha et al: CUBIC: A New TCP Friendly HighSpeed TCP Variant, ACM SIGOPS Review, 008.

33 CUBIC-TCP (4) CUBIC の長所安定性 (stability) 複数 CUBIC フローの公平性 (intra-protocol fairness) CUBIC の短所収束性 (responsiveness) バッファの占有遅延の増加 ( delay-driven) 他プロトコルとの不公平性 (inter-protocol unfairness Linux beats Windows! (vs. Compound TCP) K.Munir et al: Linux beats Windows! or the Worrying Evolution of TCP..., PFLDNet 007.

34 Hybrid TCP and its Performance Analysis

35 Hybrid TCP (1) 単独フロー packet loss clearing buffer (TCPW) cwnd last cwnd last RTT RTT min 1 vacant capacity Hybrid cwnd last / legacy (Reno) BDP n 二つのモードの適応的な切り替え (loss & delay): 1 RTT が増加するまでは一定レート (delay mode) : 効率性 RTT が増加し始めたら Reno として動作 (loss mode) : 親和性

36 Hybrid TCP () 競合フロー packet loss clearing buffer (TCPW) cwnd last cwnd last RTT RTT min 1 vacant capacity Hybrid 3 cwnd last / legacy (Reno) BDP/ n 二つのモードの適応的な切り替え (loss & delay): 1 cwnd の急激な増加 (delay... 効率性 ) cwnd のなだらかな減少 (delay... 輻輳回避 ) 3 RTT が増加し始めたら Reno として動作 (loss... 親和性 )

37 Min-Max Fair ( 理想解 ) 最も少ない帯域割当てを受けているユーザに最大の帯域割当てを行う動作をすべてのユーザに対して繰り返す ( 最小最大公平 ) ボトルネックリンク帯域 1 を割り当て 1 ボトルネックリンク公平に 1/3 割り当てボトルネックリンク残りの /3 割り当て 5 3 D.Bertsekas and R.Gallager: Data Networks, Prentice Hall.

38 理想解 : TCP の目標使用帯域セッション開始 Min-Max Fair 別のセッション開始時間 TCP Reno 使用帯域セッション開始 Min-Max Fair を探索し続ける別のセッション開始時間

39 TCP の理想挙動モデル (1) モデルの定義 Loss-driven (TCP-Reno) : cwnd += 1 ( RTT ラウンド毎 ) cwnd *= 1/ ( パケットロス時 ) Delay-driven : RTT が増加しないようにパイプを埋める ( リンクを使い切る ) Hybrid : RTT が増加しない場合は delay モードで動作 RTT が増加し始めたら loss モードで動作モード選択 : cwnd = max( cwnd loss, cwnd delay )

40 TCP の理想挙動モデル () パラメータの定義 w : パケットロスが発生するパケット数 W : ちょうどリンクを使い切るパケット数 ~ BDP p : パケットロス率 ( 乱暴な ) 仮定バッファオーバーフローによるパケットロスとランダムエラーによるパケットロスの影響を等価とみなす p = 8 3w (in case of TCP-Reno)

41 TCP の理想挙動モデル (3) TCP フレンドリのモデル cwnd TCP-Reno w w/ R w: パケットロスが起きる cwnd p: パケットロス率 RTT: ラウンドトリップ遅延 0 w/ RTT round n R: 等価なレートパケットロスが起きるまで送れるパケット数 (= 台形の面積 ) 1 w w + w 3w = 8 p = R = 8 3w PS RTT 3 p

42 TCP の理想挙動モデル (4) 単独フローの場合 sender bottleneck link receiver single TCP flow

43 TCP の理想挙動モデル (5) cwnd と RTT の挙動 cwnd w loss-driven delay-driven hybrid w ~ ロス率 W~ 帯域幅 w/ W 0 loss & hybrid delay w/ buffer BDP n cwnd loss w hybrid W delay w/ vacant capacity 0 W-w/ w/ buffer BDP n cwnd W w w/ 0 w/ delay & hybrid vacant capacity loss buffer BDP n RTT loss & hybrid delay RTT min 0 w/ n RTT loss & hybrid RTT min delay 0 W-w/ w/ n RTT min RTT 0 w/ loss, delay & hybrid n (i) W < w/ (ii) w/<w <w (iii) w <W バッファ大ロス率小 ( 常に loss-mode) バッファ小ロス率中 (delay loss) ロス率大常に空き帯域 ( 常に delay-mode)

44 TCP の理想挙動モデル (6) 定式化 TCP CA round (i) W < w/ (ii) w/ W < w (iii) w W Loss transmitted packets elapsed time 3 w w RTTmin + (3w 4wW ) 8 PS B 3 3 w w w RTTmin + ( w W) PS B 1 w RTT min Delay transmitted packets 1 w W 1 w W 1 w W elapsed time 1 w RTT min 1 w RTT min 1 w RTT min Hybrid transmitted packets 3 w w W + ( w W ) 1 w W elapsed time 1 1 w RTTmin + (3w 4wW ) 8 PS B 1 w RTT 1 + ( w W min ) PS B 1 w RTT min PS: Packet size, B: Link bandwidth

45 TCP の理想挙動モデル (7) 具体例の組込み ( 詳細略 ) Hybrids Window increase Window decrease Compound TCP 0.15*cwnd / ARENO B/10Mbps 1/~1 YeAH-TCP Scalable TCP (1.01) 1/, RTT min /RTT, 7/8 TCP-Fusion B*D min /(N*PS) RTT min /RTT D min : timer resolution, N: # of flows

46 TCP の理想挙動モデル (8) モデル評価とシミュレーション評価スループット delay & hybrid 1Gbps 1Gbps 100Mbps RTT=40ms buffer size = BDP (constant) Packet loss rate : variable loss-driven ロス率が大きい時 (w/<w) delay & hybrid のスループットは loss-driven よりもはるかに大きい ( 効率性の改善 ) ロス率 Compound と YeAH の特性が落ちるのはウィンドウ減少率が大きいため

47 TCP の理想挙動モデル (9) 競合フローの場合 loss-based TCP flow bottleneck link senders receivers loss-based or hybrid TCP flow

48 TCP の理想挙動モデル (10) cwnd の挙動 (RTT 省略 ) cwnd loss-driven hybrid total (loss + hybrid) w ~ ロス率 W~ 帯域幅 w W w/ 0 total loss & hybrid w/ buffer BDP n cwnd W w W/ w/ 0 total hybrid loss (W-w)/ w/ buffer BDP n cwnd W W/ w w/ 0 total hybrid loss w/ buffer BDP n (i) W < w (low PLR) (ii) w <W < *w (medium PLR) (iii) *w <W (high PLR) always buffered (loss mode) vacant buffered (delay loss) always vacant (delay mode) バッファ大ロス率小バッファ小ロス率中ロス率大常に空き帯域

49 TCP の理想挙動モデル (11) 定式化 TCP CA round (i) W < w (ii) w W < w (iii) w W Loss Hybrid (common) transmitted packets transmitted packets elapsed time 3 w w 1 w + ( W w) w RTTmin + w(3w W ) 4 PS B 3 3 w w w RTTmin + (w W) 4 PS B 1 3 w W w 8 1 w RTT min PS: Packet size, B: Link bandwidth

50 TCP の理想挙動モデル (1) モデル評価とシミュレーション評価スループット 1Gbps 1Gbps delay & hybrid 100Mbps RTT=40ms buffer size = BDP (constant) Packet loss rate : variable loss-driven ロス率が大きい時 (w<w) delay & hybrid のスループットは loss-driven よりもはるかに大きい ( 効率性の改善 ) ロス率ロス率が小さい時 (w>w) hybrid は loss と同様に振る舞う ( 親和性の改善 )

51 TCP の理想挙動モデル (13) Hybrid TCP の利点空き帯域が存在する時 ( パケットロス率が大きい時 ) スループット効率を大きく改善 (delay-drivenの利点) 空き帯域が存在しない時 ( バッファサイズが大きい時 ) レガシー TCPとの親和性を実現 (loss-drivenの利点) Hybrid TCP の弱点バッファサイズが大きい時 delay-driven の利点が出ない ( レガシー TCP はもう要らない?) さてどうしましょう

52 Hybrid TCP のまとめ

53 Hybrid TCP のまとめスループット効率と親和性の両立リアルタイムストリーミング大規模ファイルダウンロードへの適用無線環境でも有効? CUBIC-TCPやCompound-TCPとの親和性 CUBIC-TCP: Linux デフォルト Compound-TCP: Windows その他のメトリック RTT 公平性 Mice/Elephant 収束速度 etc ただしあくまでも有効なのは delay-driven

ｽﾗｲﾄﾞﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし画像情報特論 (3) -TCP/IP (2) TCP (Transport Control Protocol) UDP (User Datagram Protocol) 2004.04.30 情報ネットワーク専攻甲藤二郎 E-Mail: katto@waseda.jp TCP Transport Control Protocol インターネットの基礎プロトコルスタック端末 T アプリケーション

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし