Microsoft PowerPoint ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint ppt"

えみひろなが
5 years ago
Views:

1 トランスポート層が提供する機能 CP その 2 山口英奈良先端科学技術大学院大学モデル : プロセス間の通信通信相手のプロセスの指定プロセス間の通信路の識別プロセス (process) はホストの中の処理単位で同時に複数存在することが仮定されている上位層へのインタフェースの提供 Connection oriented (virtual circuit) Connectionless (datagram) ネットワーク資源の競合と調停フロー制御 (flow control) 輻輳制御 (congestion control) 1 2 ネットワーク資源の競合と調停フロー制御 (flow control) 速度の違いを吸収配送順序の入れ替わりからの回復重複パケット廃棄ビット誤りからの回復通信するノード間でのデータ転送の最大効率追求輻輳制御 (congestion control) 輻輳を抑えつつ帯域を共有帯域の公平配分ネットワーク全体での共存共栄フロー制御 Stop-and-wait Go Back N Selective repeat さまざまな方式が存在ネットワーク側が速度等を申告するものホスト側で速度を推定しながら動くもの ARQ (Adaptive Repeat request) 3 4 Stop-and and-wait ARQ Go-back back-n N ARQ Sender t 1 t 4 t 5 フレーム 3 に対する再送タイマがタイムアウト!! t 1 t 2 t 3 Receiver t 1 : 伝送遅延 t 2 : フレーム伝送時間 t 3 : フレーム処理時間 t 4 : 伝送時間 t 5 : 処理時間情報ネットワーク論 I / 第 3 回 5 情報ネットワーク論 I / 第 3 回 6

2 CP におけるフロー制御の特徴 End to End ネットワーク全体でのグローバルな資源割り当てはしない各ホストが利用可能帯域を推定しながら動作 Available bandwidth estimation at individual hosts 経路上のルータはフロー制御に介入しないパケット廃棄のみを活用 Implicit signaling through packet drops End to end control in CP Data flow flow Scalable ホスト側のみで自律的に動く方式はネットワーク側での状態管理を必要としないためより大規模なネットワーク運用が可能 Autonomous less state management Scalable - timer & retransmission - packet interval handlings - on-the-fly packet control - buffering for retransmission 途中ルータでは他トラヒックの流入によりパケット廃棄が発生する可能性がある ( データもも ) - timer & duplicate - delayed ing - window size notification - buffering for reordering packets 7 8 CP から学ぶべき点非常に単純なアルゴリズムマクロな自己安定性 Macroscopic self-stabilization Greedy なノードの存在を仮定しないグローバルな制御システムの排除 Assume absence of greedy node Reject the idea of intermediate policing system データリンクを選ばずそこそこ動く特定の環境で最適な性能を発揮するわけではない Modest performance on almost all data-links 20 年以上にわたるチューニング CP におけるフロー制御利用帯域を調整 Sliding window パケット番号ではなくシーケンス番号で Window size パケット送出間隔を調整 clocking その他誤り検出 CP checksum パケット廃棄ー duplicate, timeout 9 10 Sliding window Sender Sent and acknowledged Nara Institute of Science and echnology 10 Window size 16 Sent but unacknowledged User data arrives Sequence number Packets in transit (on-the-fly packets, outstanding packets) 受信者側からの window size の広告古典的 CPでのフロー制御 rwnd: 広告ウィンドウ (advertisement window) 受信者が要求するパケットサイズあるいは受信可能なパケットサイズを通知し送信者が管理するスライディングウィンドウの大きさを制御通信路の状況を反映した値設定ができない可能性が高いボトルネックリンクの挙動に脆弱 Receiver Nara Insti 11 12

3 clocking data Bottle neck でのパケット間隔が保存 CP における輻輳制御 CP tahoe Fair-share model: 帯域の公平分配 End to end Window size の増減 Additive increase Multiplicative decrease 自己安定的であることが知られている (Jain, et.al) Data flow 生成 flow ( 間隔 ) の受信間隔 ( ボトルネック速度 ) に合わせてパケットを送信平衡状態を考えると自己同期 (self clocking) を達成する 13 Window size 増加戦略の切り替えパケット廃棄で輻輳が起きたことを知る Detect congestion through packet drops 14 制御パラメータの追加 CP tahoe 送信側管理のパラメータ cwnd 輻輳ウインドウ congestion window, 初期値 1 ssthresh モード切替閾値 threshold, 初期値大 tcprecvthresh 高速再送を行う重複数, 多くの実装で3 Window size の増やし方 Slow start threshold (ssthresh) を基準として congestion window (cwnd) の増やし方を変えるアルゴリズムの概要 On receiving an : If (cwnd < ssthresh) { /* */ 毎にパケットを2 個送出 cwnd += 1; else { /* congestion avoidance */ 毎にパケットを1 個送出 cwnd 個送出後 1 個追加 cwnd += 1 / cwnd; Window size の増やし方 Window size の減らし方 Slow startの時 Exponential increase( 指数的増加 ) 倍々で送信パケットが増えていく Congestion avoidance の時 Additive increase( 加算的増加 ) 一個づつ増える congestion avoidance 最大スループットを越えてしまうとパケット廃棄の発生 Buffer overrun のためにパケットが取りこぼされる Packet dropの発生パケット廃棄が発生すると Duplicate が戻されるは戻ってくるのだから重度の輻輳ではないだろう ( 予想 ) 再送しても大丈夫だろうなぁタイムアウトしてしまう Retransmission ime Out (RO) も戻れない程ネットワークは混み合っているだろう ( 予想 ) しばらく待った方が良さそうだなぁ 17 18

4 Window size の減らし方 ( アルゴリズムの概要 ) On detecting packet drop: If ( 重複数 == tcprecvthresh ) { パケットを再送 /* fast retransmit */ ssthresh = cwnd / 2; cwnd = 1; /* から再開 */ If (timeout) { パケットを再送 timeout *= 2; /* 指数的バックオフ */ cwnd = 1; そうすると全体の動き方としては最大スループット ( 変動する可能性あり ) RO Calculation Err = M A A A+ gerr D D + h( Err -D) RO = A + 4D A: smoothed R D: smoothed mean deviation g: gain for the average (1/8) h: gain for the deviation (1/4) 簡単に言えば RO = { 平均的 R + 4 { 標準偏差 21 更に改善は続く CP reno ahoe の問題点 Fast retransmit( 高速再送 ) 後にするのはペナルティを与えすぎではないのかパケット廃棄直前の cwnd は安全 ( 現在の cwnd の ½) Fast recovery If ( 重複数 == tcprecvthresh) { パケットを再送 ; /* fast retransmit */ ssthresh = cwnd / 2 ; cwnd = cwnd/2 + tcprecvthresh; If ( 重複数 > cwnd/2 ) 重複毎に新しいパケットを一つ送信 ; If ( 再送パケットの ) cwnd = ssthresh ; 22 全体にペナルティが少ない更に改善は続く Selective Acknowledgement (S) の導入 Rate flow control への挑戦 CP vegas FRC - CP Friendly Rate Control (RFC4828) cwnd /2 最大スループット ( 変動する可能性あり ) Explicit Congestion Notification (ECN) Interaction with RED CP extensions for wireless links

5 CP enhancements 細かな実装の違いが存在 CP tahoe CP reno CP new reno S. 拡張には 2 種類ある特定の条件で最適な性能を発揮するための CP 拡張数多くの論文が書かれているが無視して良い幅広い条件でそれなりの性能を向上させるための拡張 IEF で標準化が検討されるベンダ独自の工夫が裏目にでることも多々発生まとめフロー制御 Stop-and-Wait Go back N CP におけるフロー制御 Sliding window CP における輻輳制御 Slow start Congestion avoidance Fast retransmit Fast recovery 25 26

ｽﾗｲﾄﾞﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし画像情報特論 (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 アプリケーション