Comments
Description
Transcript
講義資料
情報ネットワーク学基礎論 TCPによるネットワークの高速化技術 長谷川 剛 (ごう) 大阪大学大学院情報科学研究科 [email protected] http://www.ane.cmc.osaka-u.ac.jp/ hasegawa/ TCP (Transmission Control Protocol) RFC793により規定 } } } RFC 793 - Transmission Control Protocol トランスポート層プロトコル 7. アプリケーション層 (Application Layer) 6. プレゼンテーション層 (Presentation Layer) SNMP, DNS, SMTP, FTP, TELNET, HTTP, NTP, .. NETBIOS 5. セッション層 (Session Layer) 4. トランスポート層 (Transport Layer) 3. ネットワーク層 (Network Layer) 2. データリンク層 (Datalink Layer) 1. 物理層 (Physical Layer) 2 TCP, UDP, … IP, ICMP, … ARP, RARP, … Ethernet, Token Ring, X.25, FDDI, ATM,WDM, … TCPのシェア } インターネットトラヒック全体の大部分を占め る } フロー数で75-80％、パケット・バイト数だと90％以 上 } } HTTPの割合が大きい (over TCP) } } } 3 ほとんどTCPトラヒック (蓄積型)ビデオストリーミング } } Webトラヒック P2P系 } } HTTP, FTP, SMTP, … 多くがTCPトラヒック ライブ配信にも使われる TCPの性能を知ることは重要 TCPによるデータ転送速度 } スループット } } データ転送遅延時間 } } } } B [Mbytes] のデータを転送したところ、C [秒]かかった Bの大きさにかかわらず、Aは変化しないのか？ } } データ転送を行った結果、平均 A [Mbps] Aは、Bの大きさによって大きく変動する 当然、ネットワーク環境によっても変動 どんなネットワークで、Aはどうなるのか？ TCPの動きを理解しないと、その性能を正しく見極めら れない } 4 問題が発生した時に、原因を突きとめられない TCPの主要な動作 コネクション開設 } } 3-way handshake データ転送 } } } 輻輳制御アルゴリズム パケット廃棄の検出、再送アルゴリズム コネクション切断 } } 5 開設と同様の手順 3-way Handshake TCPが用いるコネクション確立方法 } } } １往復半で完了、データ転送開始 終了時も同様 送信側 コネクション確立 受信側 送信側 コネクション切断 受信側 SYN SYN+ACK ACK（+データ） コネクション確立、 データ転送開始 FIN FIN+ACK ACK コネクション切断終了 6 送信側 3-way Handshake とデータ転送 } } SYN 転送データサイズに よっては、ほとんどの 時間をHandshakeに 使う場合がある } Webドキュメント…平均 サイズは10KB程度＝6 パケット程度 転送初期は速度が非常 に低い（後述） } 多くのデータを転送すれ ばするほど、速度が上 がってくる SYN+ACK ACK（+データ） 送信側 受信側 データ転送 SYN SYN+ACK ACK（+データ） データ転送 FIN FIN FIN+ACK ACK 7 受信側 FIN+ACK ACK データ転送 } 受信側は、データパケットに対してACK（確認）パ ケットを返送する } 確実な転送の実現 送信側 受信側 Data 1:1000 ACK 1001 Data 1001:2000 Data 2001:3000 ACK 2001 ACK 3001 8 パケットの種類 データパケット } } 転送するデータを格納 } サイズは任意（下位層のネットワークに依存） } シーケンス番号が、バイトカウントで付けられる ACKパケット } } データを受け取ったことを確認するために返送する } } サイズは通常40バイト (オプション無の場合) } 9 次に受信すべきシーケンス番号 (受信完了したシーケンス番 号+1) が書かれる TCPヘッダ＋IPヘッダ Cumulative (累積的) ACK } ACKパケットには、シーケンス番号の何番までのデータをすべて受 信したかが書かれている } } 何番を受け取ったか、ではないことに注意 } } 確実な転送のため ACKパケットが落ちた時に、どれが受信出来ていないのかわからなくな るのを防止 最後のACKが最新の情報を持っている } 途中でACKパケットが落ちても、次のACKが届けばよい Data Data Data Data Data Data 1 2 3 4 5 6 Data 3 （再送） ACK 1 ACK 2 ACK 2 ACK 2 ACK 2 ACK 6 10 輻輳制御 } } TCPが持つもっとも重要な機能 輻輳とは？ } ネットワークの混雑 } } } } 「遅い」「重たい」 ネットワーク内に注入されるパケットが多すぎて、ルータ、リ ンクが処理し切れない エンドホスト処理に時間がかかっている場合もある ネットワークが輻輳するとどうなるのか？ } パケット転送に時間がかかる } } } 11 ルータのバッファリング遅延など パケットがネットワーク内で失われる バッファ れ、リンク切断 フロー制御+エラー回復制御=TCP輻輳制御 } では、どうすればいいのか？ } ネットワークに送出するデータ量を減らすこと で、ネットワーク輻輳を回避する } } ネットワーク内でパケットが失われたことを発 見し、そのパケットを送りなおす } } エラー回復制御 TCPはその両方を複合的に行う } 12 フロー制御 輻輳制御 データ転送速度の制御 } Window-based control （ウィンドウ型フロー制 御） } } 13 受信側からの確認を得ずに送信することができるデータ 量を制限（ウィンドウサイズ）する ウィンドウサイズ＝ネットワーク内に流し込むデータ量 ウィンドウ型輻輳制御 } ウィンドウサイズが 1パ ケットの場合 送信側 ウィンドウサイズが 5パ ケットの場合 送信側 受信側 Data 1 ACK 1 Data 2 ACK 2 14 } Data Data Data Data Data ACKを待たずに データパケットを 5つ送れる 1 2 3 4 5 Data 6 Data 7 Data 8 Data 9 Data 10 受信側 ACK ACK ACK ACK ACK 1 2 3 4 5 ACK 6 ACK 7 ACK 8 ACK 9 ACK 10 データ転送速度が5倍 ウィンドウサイズと転送速度 } 転送レート ウィンドウサイズ／往復遅延時間 （RTT) } ウィンドウサイズ５ パケットサイズ1KB RTT100msecの場合 } 15 転送レート 5 1KB／100msec ＝400 Kbps 送信側 Data Data Data Data Data 1 2 3 4 5 Data 6 Data 7 Data 8 Data 9 Data 10 受信側 ACK ACK ACK ACK ACK 1 2 3 4 5 ACK 6 ACK 7 ACK 8 ACK 9 ACK 10 TCPのウィンドウサイズ } 固定でいいのか？ } } } } } ネットワークの輻輳状態に応じて、ウィンドウ サイズを変動させる } } ウィンドウサイズ＝ネットワーク内に流し込むデータ 量 空いているネットワークでは大きく 混んでいるネットワークでは小さく ネットワークの状態は常に変化する ネットワークに送出するデータ量を調節 動的なウィンドウサイズの調節 } 16 TCPの輻輳制御のキーポイント TCPのウィンドウサイズと帯域遅延積 } では、ウィンドウサイズはいくらにすればいいの か？ } 帯域遅延積に等しければ理想的 } TCPコネクションが利用可能な帯域と、端末間の伝播遅延時間 の積 １Mbps、10msec Data Data Data Data Data Data Data ACK 1Mbps 17 ACK ACK ACK ACK ACK ACK 20msec = 20 Kbit 分のデータがリンク上に乗る TCPのウィンドウサイズと帯域遅延積 (2) } ウィンドウサイズが小さいと、ネットワーク帯域が 無駄になる Data Data ACK } ACK ウィンドウサイズが大きいと、乗り切れないデータ がネットワーク内（のどこか）で廃棄される Data Data Data Data Data Data Data Data Data ACK 18 ACK ACK ACK ACK ACK ACK 帯域遅延積の大きさ } } 帯域のケタ数 RTTのケタ数の変化 帯域1Mbps 、RTT 20msec } } 帯域1Gbps 、RTT 200msec } } 20 Kbits 200Mbits ネットワークによって、数ケタの違いがある } 19 近年のネットワークでは特に（ギガビットイーサから無 線ネットワークまで幅広い） 帯域遅延積の推定 } 送信側端末で帯域遅延積がわかるのか？ } 遅延時間はある程度わかる } TCPはRTT (Round Trip Time)は計測している ¨ } 利用可能な帯域がわからない } } 20 データパケットを送信してから、対応するACKが帰ってくるまでの 時間 輻輳状況によって変化 ATM ABRサービスクラス等で考えられたRate-based control では、ネットワーク側から教えてもらうのが前提 受信側バッファサイズとウィンドウサイズ } 信側端末が用意しているバッファサイズも考慮する 必要がある } } ネットワークに余裕があっても、受信側で ため れてしまう 現在のインターネット＋端末設定では、バッファサ イズ設定がスループットを制限している場合が多い } } } 21 ネットワーク帯域を使いきれていない Socketインタフェースで調整可能 Windows環境でもパラメータ調整可能 TCPの2つのウィンドウ } 輻輳ウィンドウ (Congestion Window: cwnd) } } } 広告ウィンドウ (Advertised Window: awnd) } } } 送信側が持つ 輻輳状況に応じて増減 受信側が持つバッファの空き容量 ACKパケットに書き込んで送信側へ返送することで、送信側端末 へ通知 送信側端末は2つのウィンドウの小さいほうを利用して データ転送を行う 22 輻輳ウィンドウ } 最初は小さい値からスタートして、徐々に大きくし ていく } } ACKパケットを受け取るたびに増加させる パケットが廃棄されれば、ウィンドウサイズを小さ くする } 23 パケット廃棄の発生を、ネットワークが輻輳しているも のと判断する 2つのフェーズ } スロースタートフェーズ } } } } } データ転送開始直後、タイムアウト後 帯域遅延積をすばやく推定する 最初は1 [packet] からスタート ACKを受け取るたびに cwnd = cwnd + 1 [packet] つまり、ラウンドトリップ時間ごとに2倍になる } } 1, 2, 4, 8, 16,… 輻輳回避フェーズ } } } } データ転送中盤以降（安定状態） 帯域遅延積の推定値を修正しながらデータ転送 ACKを受け取るたびに cwnd = cwnd + 1/cwnd [packet] つまり、ラウンドトリップ時間ごとにほぼ1ずつ大きくなる } 24 5, 6, 7, 8, … フェーズの移動 } スロースタートフェーズから輻輳回避フェーズへ } } cwnd が ssthreth (slow start threshold)に達すれば移 動 ssthreshはパケット廃棄検出時に更新 } } その時の輻輳ウィンドウサイズの1/2に設定 輻輳回避フェーズからスロースタートフェーズへ } } 25 タイムアウトが発生したり、長いアイドル時間の後に移 動 ウィンドウサイズは1にリセット ウィンドウサイズの変化 Window Size Congestion Avoidance Phase ssthreth Slow Start Phase Time 26 TCPバッファ (ソケットバッファ) } 送信バッファ } } 受信バッファ } } 送信側アプリケーションがTCPへデータを渡す際に格 納する領域 受信側TCPがアプリケーションにデータを渡す前に格 納する領域 大きさがTCP性能に影響を与える } } バッファサイズを超えるウィンドウサイズを設定し ないため そのため、小さすぎると、スループットが上がらない } 27 ウィンドウサイズに上限を与えてしまう TCPバッファ (2) } } } デフォルトは32KB∼64KBぐらい 通常、カーネルパラメータで変更可能 ネットワーク帯域を十分活用するためには } } 帯域1Mbps 、RTT 20msec } } 200Mbitsなので、デフォルトでは足りない 大きく設定しすぎると、コネクション数が増えると足り なくなる } } 20 Kbitsなので、デフォルトで十分 帯域1Gbps 、RTT 200msec } } ネットワークの帯域遅延積よりも大きい必要がある 特に繁忙サーバでは深刻な問題 適応的、かつ動的なバッファサイズ設定が必要になるか もしれない } 28 既に実装されているOSも存在（linuxなど） パケット廃棄の検出 } ネットワーク内でのパケット廃棄 } } バッファ れ等 送信側端末には直接わからない } } } ネットワーク側から「落ちた」と教えてもらえるわけではない データパケットが落ちたのか、帰りのACKパケットが落ちたの かもわからない パケット廃棄の検出方法 } } 29 タイムアウトによる検出 重複ACKによる検出 タイムアウトによる検出 } } } } データパケットが受信側に届けば、 受信側はACKパケットを送信側へ 返送する ACKパケットが一定時間内に返っ てこなければ、データパケットは 受信側に届かなかったと判断し、 そのパケットを再送する 一定時間・・・再送タイムアウト 時間 (RTO: Retransmission TimeOut) 3以降を全て送信し直し （GoBack-N） } 送信側 Data 1 Data 2 Data 3 Data 4 Data 5 Data 6 ACK 1 ACK 2 ACK 2 Data 3 （再送） Data 4 Data 5 Data 6 ひどい輻輳と判断するため 再送タイムアウト時間 30 受信側 再送タイムアウト時間 } ＲＴＴが1秒のコネクションと10msecのコネクション で、同じだけ待っても意味がない } } } 各転送パケットのRTTを計測し、その大きさをベースに RTOを決定 計算アルゴリズム } } } } } } RTTの長さに応じた設定が必要 Err(n) = RTT(n) ‒ A(n-1) A(n) = (1-g)・A(n-1) + g・RTT(n) D(n) = D(n-1) + h・{¦Err(n)¦ - D(n-1)} RTO(n) = A(n) + k・D(n) A(n) ・・・ RTTの平均値 (Smoothed RTT) D(n) ・・・ RTTの変動部分 （分散）に相当 31 タイマ粒度 } 計算される値をそのまま使うわけではない } 少なくとも、OSのタイマ粒度以上の細かい値は設定でき ない } } } カーネルは一般的に、OSが提供可能なものより粗い粒度 のタイマを使っている } 32 通常のデフォルトは10ms, 1ms程度 OSのタイマ粒度は小さくできるが、負荷が高くなる カーネルのオーバヘッド削減のため 重複ACKによる検出 } Cumulative ACKを利用 } } } } 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …と送信 1, 2, 3, 4, 6, 7, 8, 9, 10, …と受信 1, 2, 3, 4, 4, 4, 4, 4, 4, …とACK 4のACKを3つ受信すると、5が失われた、と判断し、再 送する } } 33 タイムアウトより早く検出できる Fast Retransmit （高速再送） パケットロスを検出したら } そのパケットを再送する } タイムアウトなら Go-Back-Nで落ちたパケット以降を全 て再送 } } 重複ACKならSelectiveに落ちたパケットだけを再送 } } たくさんパケットが落ちているはずだから １、２個のパケット廃棄だから さらに、TCPはパケットロス＝輻輳と思う } } } 34 ネットワークの輻輳を解消する必要 自分自身が、転送レートを下げる つまり、ウィンドウサイズを小さくする ウィンドウサイズの減少 } タイムアウトの時 ひどい輻輳なので、ウィンドウサイズを1パケットに する } 転送開始時と同じ ウィンドウサイズ } ssthrethを落ちる前の パケットロス発生 ウィンドウサイズの半分 タイムアウト発生 W にする } つまり、スロースタート フェーズが始まる 再送後の } ssthresh = (W/2) 1 35 再送タイムアウト時間（RTO) 時間 ウィンドウサイズの減少 (2) } Fast Retansmitの時 } } } 軽度の輻輳なので、ウィンドウサイズを半分にする ssthrethを落ちる前のウィンドウサイズの半分にする （ウィンドウサイズと同じ値） つまり、輻輳回避フェーズが始まる ウィンドウサイズ パケットロス発生 重複ACK検出 W 再送後の ssthresh = (W/2) 36 時間 ウィンドウサイズの変化 [packets] Congestion window ssthresh 0 37 時間 ssthreshの意味 } パケット廃棄の発生 } } 38 ウィンドウサイズが帯域遅延積を超えるときに発生 パケット廃棄が発生するときのウィンドウサイズは、ほ ぼそのコネクションが使える帯域遅延積に等しい 高速TCP 39 LFNsにおけるTCPの問題点 } 高遅延(Long)、高帯域(Fat)ネットワーク (Network) } } インターネットの大規模化、ネットワーク技術の進歩 帯域遅延積が巨大化 } Ex) 10Gbps, 100msec で125MB } } } 83333パケットに相当(パケットサイズ：1500B) 速いだけ、遠いだけならそれほど問題ではない この帯域遅延積を使い切るには、 } } 送受信端末に巨大なバッファが必要 輻輳ウィンドウサイズの増減アルゴリズムがよくない } } 40 1パケット／RTTの増加 パケット廃棄時に半分に減少 LFNsにおけるTCPの問題点(2) 従来のTCP(Reno)で、10Gbps, 100msecのネットワー クを使い切るには、 } 2 x 10-10 以下のパケット廃棄率が必要 } } } } 41 現在の光ファイバ技術でも不可能 リンクレイヤでのエラー回復制御で可能になるかもしれない パケット廃棄が発生すると、スループットが回復するまでに 40000 RTTs(1時間以上)必要 現実的には10Gbpsは達成不可能 輻輳ウィンドウサイズ } 125MB (83333pkts) 40000RTT (1時間以上) 時間 根本的な原因と解決策 } ネットワークの輻輳状態を知るための指標が、パケット 廃棄の発生の有無のみ } Loss-based手法 } } } (そのため、)ウィンドウサイズの増減のパラメータが固 定 } } パケット廃棄発生＝ネットワークは輻輳している パケット廃棄なし＝ネットワークは輻輳していない どれぐらい空いている、というのが分からないため 解決策 } } 42 TCPコネクションの並列利用 LFNsに対応する輻輳制御方式の利用 解決策：Parallelizing TCP Connections } 1つのデータ転送に、複数のTCPコネクションを並列利用 する } アプリケーションのみで書けるため、実装が容易 } } } GridFTPなどで既に導入されている ネットワークがボトルネックでなければ、比較的容易にスルー プットを向上可能 問題点 } コネクション数の決定 } } } } } 1本のコネクションでの転送データサイズの決定 ネットワーク状況の動的な変化に対する追随性 オーバヘッドの増加 } 43 多すぎるとスループットは低下する ネットワーク環境が決まれば、コネクション数にはそれほど敏感では ないが、ネットワーク環境そのもの変化には敏感 端末において多くのTCPコネクションの管理が必要 解決策：TCP modifications for LFNs } 高速・高遅延ネットワークに対応するための輻輳 制御方式 } 新たな指標の導入 } Loss-basedの拡張 ¨ } Delay-based ¨ } } } } スループット値、過去のパケットロス時の状態など 帯域に関わる情報 動的なパラメータ設定 新たな制御アルゴリズム } } 44 パケットのラウンドトリップ時間（RTT）を利用 Loss-basedとdelay-basedの組み合わせ その他の手法 ¨ } cwnd値そのものを指標に用いる AIMDからMIMD、あるいは別の方式へ まったく別の手法の導入 HighSpeed TCP (HSTCP) } } Loss-basedの拡張 指標として、輻輳ウィンドウサイズそのものを利用 } } 輻輳ウィンドウサイズが大きい＝より高速なネットワークである ウィンドウサイズの上げ幅(通常1pkt/RTT)をより大きく、 下げ幅(半減)をより小さく Window Size HighSpeed TCP TCP Reno 45 Time S. Floyd, “HighSpeed TCP for large congestion windows,” Request for Comments (RFC)3649, Dec. 2 FAST TCP } RTT値に基づいたウィンドウサイズの増減 } ウィンドウサイズは収束値にexponentialに近づく } } 定期的なパケット廃棄は発生しない 欠点 } } αの設定方法 ボトルネックリンクのキュー長 } } 46 コネクション数に比例して増大する バッファ れを防ぐには、αをコネクション数に応じて変化させる必 要がある 欠点 } Loss-basedの改善 } } 既存TCP Renoコネクションと共存すると、TCP Renoコネク ションのスループットを圧迫 Delay-based } 想定しているネットワークの輻輳 } } } まず、キューイング遅延の発生にともない、エンド間遅延が大きく なる その後、パケット廃棄が発生 Loss-basedとの共存環境 } ネットワーク輻輳の初期段階において、 ¨ ¨ } 47 Delay-basedはウィンドウサイズを小さくする Loss-basedはウィンドウサイズを大きくし続ける Loss-basedが帯域を占有する Loss-basedとdelay-basedの組み合わせ } Compound TCP など } } 自身のウィンドウサイズとは別に、Loss-based（e.g. Reno）相当のウィンドウサイズ値を保持 RTTの大きさに応じて動きを変化させる } RTT 最小値の場合：Renoより早くウィンドウサイズを増加さ せる ¨ } RTTが増加し始めた場合：ウィンドウサイズの増加をとめる ¨ } Renoを圧迫しない Renoに追いつかれた場合： Renoのウィンドウサイズを採用 ¨ 48 LFNsの大きな帯域遅延積をすばやく利用 Renoに負けない 48 TCPフローの多重化とルータバッファサイズ (1) } 従来：250∼500msecルール } 輻輳ウィンドウサイズ (の合計値) } 同期して動作するTCP Renoフローを前提 バッファサイズが帯域遅延積分ないと、バッファ ンク利用率低下が発生 } 49 帯域遅延積+バッファサイズ 同 期 ： Ta i l - D r o p バ ッフ ァ Synchronization が原因 } れ時にリ 時間 れによるGlobal 通過するTCPフローが同時にパケット廃棄を起こし、同時 にウィンドウサイズを小さくする TCPフローの多重化とルータバッファサイズ (2) } } 通過するTCPフローが同期しないのであれば、バッファサイズは もっと小さくて良いのではないか } G. Appenzeller, I. Keslassy, and N. McKeown, Sizing router buffers, in Proceedings of ACM SIGCOMM, pp. 281‒292, Sept. 2004. } 同期しない … いわゆる統計多重化効果が得られる 同期しないための条件 } } } } 良影響 } } } 通過するコネクション数(多ければよい) フローのRTTのバラツキ、ランダム性 …? RTTのバラツキが小さくなる(バッファが小さいため) ルータの低コスト化 悪影響 } 50 パケット廃棄率の増加 その他の方式 } TCP Westwood } Used bandwidthを指標にする } } 帯域値 RTTを、ウィンドウサイズの制御に用いる } } } 競合トラヒックが減って、使える帯域が増加する場合に、追随速度が鈍い BIC TCP / CUBIC TCP } } } } タイムアウト時のssthreshの設定 ウィンドウサイズの増減アルゴリズムそのものに導入 問題点 } } ACKパケットの到着間隔から判断 Linuxのデフォルト (CUBIC) パケット廃棄が発生したときの輻輳ウィンドウサイズを記憶し、次サイ クルの制御に利用 ルータバッファが十分にあることを暗に前提としている Hamilton TCP(HTCP)、TCP-Fusion、… 51 帯域情報の指標としての利用 } エンド端末間のネットワークパスの帯域情報 } } } } 物理帯域(キャパシティ) 利用可能帯域 RTTなどよりも、輻輳制御に直結 帯域計測アルゴリズム・ツール } 豊富に存在するが、根本的な欠点を持つ } } } 帯域情報を輻輳制御に使うためには } } 52 計測に別途パケットが必要 計測のために多くのパケットを、高い転送速度で送出する 帯域情報をローコストかつ高い頻度で取得 帯域情報を基にした新たな輻輳制御方式の導入 TCP/IPの処理のオーバヘッド } 今のレベルのマシンだと } デフォルトのOSの設定だと、数百Mbps程度しか出ない } } OSの設定、メモリ処理等を最適化すると数Gbpsぐらい 出る、という結果もある } } 53 OSによって性能にかなりの違いがある 10GbEのインタフェースカードでの結果 ただし、CPU利用率は100%となり、本来の仕事(アプリケー ション処理)に支障が出る TOE (TCP Offload Engine) } TCP以下の処理をハードウェアで行う } } 製品が既に発売されている } } } } 上位OSはアプリケーションの処理に集中 3∼4つのメーカ 1GbEだとオンチップ化されている 10GbE対応のカードも存在 ただ、TCPの動きは怪しいものが多い 54 54 TOE (TCP Offload Engine) (2) } ハードウェアタイプ } } ASICベース PE（プロトコルエンジン）ベース } } IXPなどのネットワークプロセッサを使った実装もありうる 実装タイプ } 並列型 } } パイプライン型 } 55 複数のエンジンでパケットを並列処理 パイプライン処理によって高速化 55