TCP Timeout and Retransmission miyu

今日のお話 TCPのタイムアウトと再転送 RTTとRTO スロースタート、輻輳回避、高速転送、高速リカバリ ICMPエラー 再パケット化

introduction TCPは信頼できるトランスポート層を提供する 信頼性を提供するには？ 一方のエンドがデータを受け取ったら他方のエンドに確認応答をだす データ・セグメントも確認応答も途中で失われてしまったら？ タイムアウトを設定し、タイムアウトが切れるまでにデータが確認応答されなければ、そのデータを再転送

TCPの４つのタイマー 再転送タイマー 持続タイマー　→22章 キープアライブタイマー　→23章 2MSLタイマー　→18章6節

シンプルなタイムアウトと再転送の例 % telnet srv4 discard Trying 140.252.13.34… Connecte to srv4. Hello,world\n And hi \n Connection closed by foreign host. ←通常の状態でこの行を送信 ←この行を送信する前にケーブルをはずす ←９分後に出力

3 0.006441 ( 0.0016) bsdi.1029 > svr4.discard: . ack 1 win 4096 1 0.0 bsdi.1029 > svr4.discard: S 1747921409:1747921409(0) win 4096 <mss 1024>　　　　　　　　　　　　　　　　　　　　　　通常のコネクション 2 0.004811 ( 0.0048) svr4.discard > bsdi.1029: S3416685569　:3416685569(0) ack 1747921410 win 4096 <mss 1024> 3 0.006441 ( 0.0016) bsdi.1029 > svr4.discard: . ack 1 win 4096 4 6.102290 ( 6.0958) bsdi.1029 > svr4.discard: P 1:15(14) ack 1 win 4096 　　　　　　　　　　　　　　　　　　　　　　hello worldの転送・ACK 5 6.259410 ( 0.1571) svr4.discard > bsdi.1029: . ack 15 win 4096 6 24.480158 (18.2207) bsdi.1029 > svr4.discard: P 15:23(8) ack 1 win 4096　　　　　　　　　　　　　　　　　　　　　　　and hiが送られる 7 25.493733 ( 1.0136) bsdi.1029 > svr4.discard: P 15:23(8) ack 1 win 4096 … 19 566.488478 (64.0015) bsdi.1029 > svr4.discard: R 23:23(0) ack 1 win 4096 1,2,3行目…通常のTCPコネクション確立 4行目…hello worldの転送 5行目…確認応答 6行目…and hiが送られてる

7行目→18行目 セグメントの12回にわたる再転送 時間間隔 1,3,6,12,24,48,64 指数バックオフ

往復時間(RTT)の測定 タイムアウトと再転送の基本はコネクションにおけるRTTの測定！ 経路の変化やネットワークの変化によって変化するから 適当なシーケンス番号を持つバイトの送信からその確認応答が返されるまでの往復時間を測定

往復時間の測定 R←αR+(1-α)M RTO=Rβ(RFC 793 再転送タイムアウト値) α…平滑化係数(推奨値 0.9) M…測定されたRTTの値 R…ロー･パス・フィルタを用いて平滑化されたRTT評価値 RTO=Rβ(RFC 793　再転送タイムアウト値) β…遅延分散係数（推奨値 2）

問題点 不必要な再転送により生じるRTTの変動に対応できない 必要なことは、平滑化されたRTT評価値に加えRTT測定値の分散を監視すること ネットワークに負荷がかかっていると、不必要な再転送は無駄すぎ 必要なことは、平滑化されたRTT評価値に加えRTT測定値の分散を監視すること 平均値と分散値をベースにRTOを計算すれば、単に平均値の定数倍として計算するよりも往復時間の変動に対応することが可能

RTTの測定値Mに適用する計算式 Err=M-A A←A+gErr D←D+h(|Err|-D) RTO=A+4D A←平滑化されたRTT Err←実際の測定値と現行RTTの差分 g←平均1/8 h←偏差の係数(0.25) 係数が大きくなるとRTTが変化したときRTOはより速く増加する

このACKは最初の転送のもの？２番目のもの？ Karnのアルゴリズム パケットが再転送されたとき パケットが転送され、タイムアウトが発生 ↓ 　RTOが増大し、長いRTOでパケットが再転送 確認応答が到着 このACKは最初の転送のもの？２番目のもの？ タイムアウトと再転送が発生したとき、 再転送されたデータの確認応答が戻ってきても RTT評価値を更新することはできない

例

往復時間の測定 500ミリ秒のTCPタイマー・ルーチンが起動するごとにカウンタを増加させる 送信から550mmsecで確認応答が到着するセグメントは？ 1周期RTT（500ミリ秒）or2周期RTT（1000ミリ秒） 周期カウンタとセグメントのデータの初期シーケンス番号が記録される シーケンス番号を含むACKがくるとタイマーはOFF

往復時間の測定 0.03 0.53 1.03 1.53 2.03 2.53 3.03 0.00 1.061 1.063 1.871 1.872 2.887 1.061sec 3周期 0.808sec 1周期 1.015sec 2周期

RTT評価値の初期化、更新 初期再転送タイムアウトの計算 初期SYNの転送のRTO RTO=A+4D (AとDは０秒と３秒に初期化) Ex)5.802秒後にタイムアウトが発生すると RTO=A+4D=0+4x3=12秒 指数バックオフが12に適用 次のタイムアウトは2の倍数→24秒 次は4の倍数→48秒

初期SYNが失われたときのtcpdump 1 0.0　slip1024>vangogh.discard:S35648001:35648001(0) win 4096 <mss 256> 2 5.802377 (5.8024) slip.1024 >vangogh.discard: S35648001:35648001(0) win 4096 <mss 256> 3 6.269395 (0.4670) vangogh.discard > slip.1024: S 1365512705:1365512705(0) ack 35648002 win 8192 <mss 512> 4 6.270796 (0.0014) slip. 1024 > vangogh.discard: . ack 1 win 4096

最初のデータセグメントのACKが到着すると3クロック周期がカウント、評価値を初期化 5.802秒後にタイムアウトが発生 RTO=A+4D=0+4x3=12秒 指数バックオフが12に適用 最初のタイムアウト 次のタイムアウトは2の倍数→24秒 次は4の倍数→48秒 再転送後、467ミリ秒でACKが到着　 AとDは更新されない 再転送の曖昧さに関するKarnのアルゴリズムが適用される 最初のデータセグメントのACKが到着すると3クロック周期がカウント、評価値を初期化 A=M+0.5=1.5+0.5=2 D=A/2=1 RTO=A+4D=2+4x1=6秒 2番目のACKが到着すると1クロック周期がカウントされ、評価値も更新 スロースタート

データセグメントの転送

セグメントの開始シーケンス番号と送信された時刻 再送が行われている

重複ACKの数をカウントし、３つ目をうけとるとセグメントが消失したと考え、シーケンス番号のセグメントだけを再転送 データ再転送しろ！ 重複ACKの数をカウントし、３つ目をうけとるとセグメントが消失したと考え、シーケンス番号のセグメントだけを再転送 →高速再転送アルゴリズム

輻輳回避アルゴリズム 中継ルーターの限界に達して破棄されたパケットの問題を解決 前提: パケットの消失を示すものは？ パケットが破損によって失われることは1%以下 パケットの消失は発信元とあて先のネットワーク上のどこかで輻輳が発生することを示す信号になる パケットの消失を示すものは？ タイムアウトの発生 重複ACKの受信

輻輳回避とスロースタート 本当は独立したもの 輻輳が発生するとスロースタートを再度利用する コネクションで管理される二つの変数を必要とする ネットワークに流すパケットの転送率を減らすため コネクションで管理される二つの変数を必要とする 輻輳ウィンドウ(cwnd) スロースタートの閾値(ssthresh)

２つのアルゴリズムの機能 コネクションの初期化 cwndは１セグメント、ssthreshは65535バイト TCPの出力ルーチンはcwndと受けての広告したウィンドウとの最小値を超えた送信は行わない 輻輳回避は送り手によるフロー制御形式、window advertismentは受けてによるフロー制御形式 輻輳が発生すると、現行ウィンドウサイズ1/2がssthreshにセーブされる 新しいデータが確認応答されるとcwndを増加 cwnd<=ssthreshの場合スロースタート、そうでなければ輻輳回避

スロースタートと輻輳回避のグラフ化 (輻輳がcwnd=32セグメントで起こったとき) ssthresh cwnd (セグメント) 往復時間

高速再転送と高速リカバリアルゴリズム 順番の違ったセグメントを受け取ったとき、直ちに確認応答（重複ACK）を生成する必要がある セグメントの順番が違って送られてきた、送られてくるべきシーケンス番号を教える セグメントの消失なのか？単にセグメントが入れ替わって送られてきただけなのか 入れ替わってるだけなら１，２個、消失なら多いはず いくつか送られてくるのを待たなければならない 再転送タイマーが切れるのを待たずに… 消失したと思われるセグメントの再転送 輻輳回避を行うがスロースタートは行わない

高速再転送と高速リカバリアルゴリズム 重複するACKが３つ以上返された後もスロースタートを行わない 2台のエンド間でのデータフローは継続してるからスロースタートに以降してフローを削減したくない！ 再転送を行う&&再転送の確認応答が届く前に新しいデータを含む３つのセグメントを送る

高速再転送と高速リカバリアルゴリズム 3番目の重複ACKが受け取られるとssthreshが現行のcwndの1/2に設定される 消失セグメントの再転送 cwndをssthreshにセグメントサイズの3倍を加えたものに設定 別の重複ACKが到着するたびにcwndをセグメントサイズ単位で増加させ、パケットを転送 新しいデータを確認応答するACKが到着したらcwndを上のssthreshに設定する 消失セグメントの再転送のACKであり、再転送から1往復時間が過ぎている。 パケットが消失したときに転送率を1/2に減らしているから輻輳回避になる

cwndとssthreshの値 セグメントが転送されるごとのcwndとssthreshの値 輻輳が発生していなかったら 輻輳ウィンドウは受けての広告したウィンドウを超過し、広告されたウィンドウがデータフローの制限となる 輻輳が発生していたら？

データ転送中のcwndの値と送信シーケンス番号

ssthresh=1/2xcwnd wnd=ssthresh+重複ACKの数 xセグメントサイズ 再転送 ]重複ACK

ルートごとのメトリクス ルーティングテーブルエントリで管理 あて先のrouting table entryがdefault routeでない場合 平滑化されたRTT,平均偏差、スロースタートの閾値がエントリにセーブされる Routeコマンドで特定経路のメトリクスを設定

ICMPエラー 発信元抑制 ホスト到達不可orネットワーク到達不可 cwndはスロースタートに初期化 ssthreshは変更されず、ウィンドウは最後までor輻輳が発生するまでオープンされる ホスト到達不可orネットワーク到達不可 一時的なものとみなされ無視 コネクションを中断させることはない

1 0.0 slip.1035 > aix. echo: P 1:11(10) ack 1 2 0.212271 ( 0.2123) aix.echo > slip.1035: P 1:11(10) ack 11 3 0.310685 ( 0.0984) slip.1035 > aix.echo: . ack 11 SLIP link brought down here 4 174.758100 (174.4474) slip.1035 > aix.echo: P 11:24(13) ack 11 5 174.759017 ( 0.0009) sun > slip: icmp: host aix unreachable 6 177.150439 ( 2.3914) slip.1035 > aix.echo: P 11:24(13) ack 11 7 177.151271 ( 0.0008) sun > slip: icmp: host aix unreachable 8 182.150200 ( 4.9989) slip.1035 > aix.echo: P 11:24(13) ack 11 9 182.151189 ( 0.0010) sun > slip: icmp: host aix unreachable 10 192.149671 ( 9.9985) slip.1035 > aix.echo: P 11:24(13) ack 11 11 192.150608 ( 0.0009) sun > slip: icmp: host aix unreachable 12 212.148783 ( 19.9982) slip.1035 > aix.echo: P 11:24(13) ack 11 13 212.149786 ( 0.0010) sun > slip: icmp: host aix unreachable SLIP link brought up here 14 252.146774 ( 39.9970) slip.1035 > aix.echo: P 11:24(13) ack 11 15 252.439257 ( 0.2925) aix.echo > slip.1035: P 11:24(13) ack 24 16 252.505331 ( 0.0661) slip.1035 > aix.echo: . ack 24

17 261.977246 ( 9.4719) slip.1035 > aix.echo: P 24:38(14) ack 24 18 262.158758 ( 0.1815) aix.echo > slip.1035: P 24:38(14) ack 38 19 262.305086 ( 0.1463) slip.1035 > aix.echo: . ack 38 SLIP link brought down here 20 458.155330 (195.8502) slip.1035 > aix.echo: P 38:52(14) ack 38 21 458.156163 ( 0.0008) sun > slip: icmp: host aix unreachable 22 461.136904 (2.9807) slip.1035 > aix.echo: P 38:52(14) ack 38 23 461.137826 (0.0009) sun > slip: icmp: host aix unreachable 24 467.136461 (5.9986) slip.1035 > aix.echo: P 38:52(14) ack 38 25 467.137385 (0.0009) sun > slip: icmp: host aix unreachable 26 479.135811 ( 11.9984) slip.1035 > aix.echo: P 38:52(14) ack 38 27 479.136647 ( 0.0008) sun > slip: icmp: host aix unreachable 28 503.134816 ( 23.9982) slip.1035 > aix.echo: P 38:52(14) ack 38 29 503.135740 ( 0.0009) sun > slip: icmp: host aix unreachabie ……… 44 1000.219573 ( 64.0959) slip.1035 > aix.echo: P 38:52(14) ack 38 45 1000.220503 ( 0.0009) sun > slip: icmp: host aix unreachable 46 1064.201281 ( 63.9808) slip.1035 > aix.echo: R 52:52(0) ack 38 47 1064.202182 ( 0.0009) sun > slip: icmp: host aix unreachable

再パケット化 再パケット化で大きなセグメントを送信、パフォーマンスを向上 バイト数が増える 1 0.0 bsdi. 1032 > svr4.discard: P 1:13(12) ack 1 2 0.140489 ( 0.1405) svr4.discard > bsdi.1032: . ack 13 Ethernet cable disconnected here 　type”line number 2” 3 26.407696 (26.2672) bsdi.1032 > svr4.discard: P 13:27(14) ack 1 4 27.639390 ( 1.2317) bsdi.1032 > svr4.discard: P 13:27(14) ack 1 5 30.639453 ( 3.0001) bsdi.1032 > svr4.discard: P 13:27(14) ack 1 Type “and 3” 6 36.639653 ( 6.0002) bsdi.1032 > svr4.discard: P 13:33(20) ack 1 7 48.640131 (12.0005) bsdi.1032 > svr4.discard: P 13:33(20) ack 1 8 72.640768 (24.0006) bsdi.1032 > svr4.discard: P 13:33(20) ack 1 Ethernet cable reconnected here 9 72.719091 ( 0.0783) svr4.discard > bsdi.1032: . ack 33 バイト数が増える