TCP/IPトランスポート層の輻輳制御アルゴリズムを理解する

この記事では、次の内容を学びます。

• 輻輳制御の概念とその背景
• フロー制御と輻輳制御の違いと関係
• 輻輳制御の主なプロセスの詳細な説明

皆さん、一生懸命勉強してオファーをもっと強力なものにしてください！

0x01. TCP/IP プロトコル スタックの簡単なレビュー

Wikipedia の TCP/IP の紹介をいくつか見てみましょう。説明がわかりやすくなるようにいくつか変更を加えました。

インターネット プロトコル スイートは、ネットワーク通信モデルであり、ネットワーク伝送プロトコルのファミリです。プロトコル スイートには、TCP (伝送制御プロトコル) と IP (インターネット プロトコル) という 2 つのコア プロトコルが含まれているため、TCP/IP プロトコル スイートと呼ばれることがよくあります。

TCP/IP プロトコルは、データをカプセル化し、アドレス指定し、送信し、ルーティングし、宛先で受信する基本的なプロセスを標準化します。通信プロセスを 4 つのレベルに抽象化し、プロトコル スタックの形式でさまざまな通信プロトコルを実装します。実際に使用される 4 層構造は、7 層の OSI モデルを簡略化したものです。

TCP/IP プロトコル スタックは、インターネットの世界のあらゆるものを接続するための基礎となる、簡略化された階層化モデルであることがわかります。7 層モデルと 4 層モデルの簡略化された図を見てみましょう。

TCP/IP プロトコル スタックは非常に大きく、スペースの制限により、この記事では詳細には説明しません。

0x02. フロー制御と輻輳制御

TCPは、コネクション指向で信頼性の高い全二重伝送プロトコルです。先人たちは、TCPを保護するために、次のような一連の複雑なアルゴリズムを含む多くの複雑なアルゴリズムを作成しました。   ハイアール兄弟 アルゴリズム: フロー制御と輻輳制御。これが今日の主役でもあります。

2.1 フロー制御の概要

フロー制御と輻輳制御は、中国語の文字通りの意味からは明確に区別できません。本質的に、これら 2 つのアルゴリズムには違いとつながりの両方があります。

Wikipedia のフロー制御の説明:

 In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver.

 It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node.

翻訳する：

データ通信において、フロー制御とは、高速な送信者が低速な受信者に負担をかけないように、2 つのノード間でデータが転送される速度を管理するプロセスです。

受信ノードが送信ノードからのデータに圧倒されないように、受信側が送信速度を制御するメカニズムを提供します。

フロー制御は、通信相手の間でデータ量を合意するためのメカニズムであることがわかります。具体的には、TCP プロトコルの ACK メカニズムとウィンドウ プロトコルの助けを借りて実現されます。

ウィンドウは固定ウィンドウと可変ウィンドウに分けられます。可変ウィンドウはスライディングウィンドウとも呼ばれます。簡単に言えば、通信側は受信側の受信状況に基づいて送信側に送信可能なデータ量を動的に伝え、送信側と受信側のデータ送受信能力のマッチングを実現します。

このプロセスは簡単にキャプチャできます。コンピュータで Wireshark を使用するか、サーバーで tcpdump を使用して確認できます。Dabai は、Wireshark を使用して、自分のコンピュータで次の行をキャプチャしました。

フロー制御プロセスを簡単に理解するために、2 つのホスト間の相互作用を使用します。

受信者の応答メッセージ ヘッダーの説明:

図中、RcvBuffer は受信領域の合計サイズ、バッファデータは現在占有されているデータ、空きバッファ領域は現在残っている領域です。rwnd は空きバッファ領域領域のバイト数です。

HostB は、現在の rwnd 値をメッセージ ヘッダーの受信ウィンドウ フィールドに入れて、使用可能なスペースの量を HostA に通知します。HostA は、rwnd 値の範囲内で未確認データの量を制御して、HostB の受信バッファ オーバーフローを回避します。

フロー制御は、ミクロレベルでのエンドツーエンドのデータ戦略であることがわかります。データ通信プロセス中、2つの当事者はリンク帯域幅を気にせず、通信当事者の受信バッファと送信バッファのスペースサイズのみを気にします。これは、レートフローマッチング戦略であると言えます。

交通管制は、現実の物流現場における2つの倉庫AとBのようなものです。AがBに商品を配送する場合、倉庫Bの残りのスペースのみを気にして自分の配送量を調整し、高速道路が混雑しているかどうかは気にしません。

2.2 輻輳制御の必要性

先ほど、ミクロレベルでのポイントツーポイントの交通制御について説明しましたが、次のような疑問が浮かびます。交通制御だけで十分なのでしょうか?答えはノーです。

また、ネットワーク リンクの輻輳を回避するには、マクロレベルの制御も必要です。そうしないと、エンドツーエンドのフロー制御アルゴリズムが最善であっても、パケット損失、無秩序、再送信などの問題に直面し、悪循環に陥ることになります。

多数の TCP 接続が多重化するネットワーク リンクの通信プロセスを、より高い視点から見てみましょう。

したがって、輻輳制御は各エンドツーエンド接続と密接に関係しています。これは、フロー制御と輻輳制御の深い関係です。各接続がスムーズであれば、複雑なネットワークリンク全体もかなりスムーズになります。

輻輳制御を始める前に、いくつかの問題について考えてみましょう。

• 混雑を感知する方法

TCP 接続の送信側が相手側にデータを送信する場合、現在のネットワーク状況に応じて送信速度を調整する必要があるため、認識機能が重要になります。

TCP 接続の送信者は通常、パケット損失に基づいて現在のネットワークが輻輳しているかどうかを判断します。パケット損失は、再送タイムアウト RTO と重複確認によって判断できます。

• 帯域幅の使い方

確かに、輻輳は大きな影響を及ぼしますが、低速でパケットを送信し続けるのは賢明ではありません。その結果、帯域幅の利用率が低下します。したがって、帯域幅を最大限に活用するには、データの送信速度が低すぎたり高すぎたりするのではなく、動的で安定した速度を維持して帯域幅の利用率を向上させる必要があります。これは、暗闇の中で障害物を避けるのと同じように、依然として比較的困難です。

• 混雑時の対応方法

輻輳が発生した場合、輻輳の悪化を防ぎ、接続トラフィックを回復するための一連の対策が必要です。これが輻輳制御アルゴリズムの本質です。

0x03. 輻輳制御を理解する

先ほど、輻輳制御の必要性と重要な問題について説明しました。次に、先人たちがどのように素晴らしい輻輳制御戦略を設計し、実装したかを見てみましょう。

3.1 輻輳ウィンドウ cwnd

フロー制御から、受信側がヘッダーで rwnd 受信ウィンドウ サイズを指定することがわかります。ネットワーク リンクは多重化されており、データ量を決定するには現在のリンク状況を考慮する必要があるため、送信側は受信側の rwnd 制限に従ってデータを送信することはできません。これは、言及したいもう 1 つの変数 cwnd です。著者は、rwnd と cwnd の英語の説明を見つけました。

 Congestion Window (cwnd) is a TCP state variable that limits the amount of data the TCP can send into the network before receiving an ACK.

 The Receiver Window (rwnd) is a variable that advertises the amount of data that the destination side can receive.

 Together, the two variables are used to regulate data flow in TCP connections, minimize congestion, and improve network performance.

著者は rfc5681 ドキュメントの cwnd の定義も確認しました。

この説明では、cwnd は送信者によって管理され、cwnd と rwnd は競合せず、送信者は図に示すように 2 つの変数 rwnd と cwnd を組み合わせてデータを送信する必要があることが指摘されています。

cwnd のサイズは、MSS 最大データ セグメントに直接関係します。MSS は TCP セグメント内のデータ フィールドの最大長です。つまり、MSS = TCP セグメント長 - TCP ヘッダー長です。

3.2 基本的な輻輳制御戦略

輻輳制御は動的なプロセスです。ネットワークの輻輳、パケット損失、RTT の増加を回避しながら、帯域幅の使用率を向上させ、できるだけ多くのデータを送信することを目的としています。このような高い要件は、単一の戦略では満たすことができません。したがって、TCP の輻輳制御戦略は、実際にはさまざまな段階と戦略を含む包括的なプロセスです。

注記：   TCPアルゴリズムの一部のバージョンでは高速回復フェーズが存在しない場合があります。

次の図は、4 つの戦略を含む一般的な輻輳制御を示しています。

図は、タイムアウト再送信 RTO が発生した場合のプロセスを示しています。

3.3 TCPアルゴリズムの一般的なバージョン

実際、TCP アルゴリズムには多くのバージョンがあり、各バージョンにはいくつかの違いがあります。以下は Wikipedia からの簡単な紹介です。

• アルゴリズムの命名規則

TCP+ アルゴリズムの名前は、1996 年に Kevin Fall と Sally Floyd によって発表された論文で初めて登場しました。

• TCP タホと TCP リノ

2 つのアルゴリズムは、タホ湖とリノ市にちなんでコード名が付けられています。2 つのアルゴリズムはほぼ同じです。パケット損失イベントの判断は、再送信タイムアウトと重複確認応答に基づいています。ただし、2 つのアルゴリズムは重複確認応答を異なる方法で処理します。タイムアウト再送信 RTO 状況では、両方のアルゴリズムが輻輳ウィンドウを 1 MSS に縮小してから、スロー スタート フェーズに入ります。

TCP Tahoe アルゴリズム: 重複する 3 つの確認応答 (つまり、同じ確認応答番号の 4 番目のセグメント確認応答) が受信され、そのセグメントが負荷セグメンテーションがなく受信ウィンドウに変更がないパケットに対応する場合、Tahoe アルゴリズムは高速再送信に入り、スロー スタートしきい値を現在の輻輳ウィンドウの半分に変更し、輻輳ウィンドウを 1 MSS に縮小して、スロー スタート フェーズに再び入ります。

TCP Reno アルゴリズム: 重複する確認応答が 3 つ受信された場合、Reno アルゴリズムは高速再送信に入り、輻輳ウィンドウを半分だけ減らしてスロー スタート フェーズをスキップし、スロー スタートしきい値を現在の新しい輻輳ウィンドウ値に設定し、高速回復と呼ばれる新しい設計フェーズに入ります。

• TCP ニューリノ

TCP New Reno は、TCP Reno の高速回復フェーズでの再送信用に改良されたアルゴリズムです。New Reno の動作効率は、低エラー率では選択的確認応答 (SACK) と同等であり、高エラー率でも Reno より優れています。

• TCP BIC と TCP CUBIC

TCP BIC は、高速かつ高遅延のネットワークにおける輻輳制御を最適化するように設計されています。輻輳ウィンドウ アルゴリズムは、バイナリ検索アルゴリズムを使用して、輻輳ウィンドウを長時間維持できる最大値を見つけようとします。Linux カーネルは、2.6.8 から 2.6.18 まで、このアルゴリズムをデフォルトの TCP 輻輳アルゴリズムとして使用します。

CUBIC は、BIC のより穏やかで体系的な分岐バージョンです。輻輳ウィンドウ アルゴリズムとして、2 進アルゴリズムではなく 3 次関数を使用し、輻輳ウィンドウの設定値として関数の変曲点を使用します。Linux カーネルは、2.6.19 以降、このアルゴリズムをデフォルトの TCP 輻輳アルゴリズムとして使用します。

• TCPPRR の

TCP PRR は、回復中に送信されるデータの精度を向上させるように設計されています。このアルゴリズムにより、回復後の輻輳ウィンドウ サイズがスロー スタートしきい値に可能な限り近くなることが保証されます。 Google が実施したテストでは、平均遅延を 3 ～ 10% 削減し、回復タイムアウトを 5% 削減できました。PRR アルゴリズムは、後に Linux カーネル バージョン 3.2 でデフォルトの輻輳アルゴリズムとして使用されます。

• TCP ブロック リバース

TCP BBR は、Google が設計し、2016 年にリリースされた輻輳制御アルゴリズムです。このアルゴリズムでは、ネットワーク インターフェイス コントローラが徐々にギガビット速度に移行するにつれて、パケット損失は輻輳識別の主な決定要因と見なされるべきではないと考えています。そのため、モデルベースの輻輳制御アルゴリズムは、より高いスループットとより低いレイテンシを実現できます。BBR は、他の一般的な輻輳制御アルゴリズムの代わりに使用できます。

Google はこのアルゴリズムを YouTube に適用し、YouTube のネットワーク スループットの世界平均を 4% 向上させました。BBR は後に Linux カーネル バージョン 4.9 に移植されました。

3.4 輻輳制御プロセスの詳細な説明

スロースタート、輻輳回避、高速再送、高速回復の 4 つの代表的なプロセスについて説明します。

• スロースタート

スロー スタートとは、新しく開始されたネットワーク接続の送信速度が一度に増加するのではなく、一時的に増加することを意味します。具体的には、接続が最初に確立されると、送信者は輻輳ウィンドウ cwnd を m に初期化します。その後、送信者が 1 RTT 以内に ACK パケットを受信するたびに、cwnd は 1 ずつ直線的に増加します。各 RTT の後、cwnd=cwnd*2 は指数関数的に増加し、一定期間後に cwnd がスロー スタートしきい値 ssthresh に達するまで増加します。

その後、cwnd は指数関数的に増加しなくなり、輻輳回避フェーズに入ります (cwnd の増加の単位は MSS であることに注意してください)。 もちろん、スロー スタート フェーズでしきい値 ssthresh に達しておらず、パケット損失が発生した場合は、高速再送フェーズに入ります。 ネットワークの状態が良好で RTT 時間が短い場合、スロー スタート フェーズはすぐに比較的高い送信レートに達するため、スロー スタートを試行的な開始として理解する方が鮮明です。

• 混雑回避

スロースタートフェーズのcwndの値がssthreshに達すると、乱高下が止まり、パケットロスが発生するまでより合理的な線形フェーズに入ります。閾値ssthreshは、前回パケットロスが発生したときのcwnd値の半分です。そのため、これは前後を繋ぐ処理となります。

この送信中にパケット損失が発生した場合、ssthresh の値は調整されます。具体的な輻輳回避の増加プロセスは次のとおりです。送信者は、ACK パケットを受信するたびに cwnd=cwnd+1/cwnd を設定し、RTT ごとに cwnd を 1 ずつ増加します。

• タイムアウト再送信と高速再送信

信頼性の高いプロトコルとして、TCP はパケット損失という大きな問題に直面しています。パケット損失は再送信を必要とします。そのため、送信者は受信側から返された ACK に基づいてパケットが失われたかどうかを確認する必要があり、図に示すように、送信者はデータを送信した後にタイマーを開始します。

RTO は複雑なネットワーク環境に応じて動的に変化します。輻輳制御におけるタイムアウト再送信は cwnd を大幅に削減します。ネットワーク状態がそれほど悪くない場合、時折発生するネットワーク ジッタによってパケット損失やブロックが発生することはよくあります。そのため、スロー スタートがトリガーされると通信パフォーマンスが低下するため、高速再送信メカニズムが登場します。

いわゆる高速再送信とタイムアウト再送信を比較します。図に示すように、パフォーマンスの低下を最小限に抑えるために、再送信の待機時間が短縮され、スロースタートが可能な限り回避されます。

高速再送信とタイムアウト再送信の違いは、輻輳が発生したときの cwnd の値にあります。タイムアウト再送信は cwnd を初期値、つまりスロー スタート値に変更し、高速再送信は cwnd を半分にします。どちらも ssthresh を cwnd の半分に設定します。

両者の違いから、高速再送信の方がより積極的であり、リンクの送信パフォーマンスの確保に役立つことがわかります。ただし、いくつかの研究では、3 ACK メカニズムにも問題があることが示されています。この記事では、これについて詳しく説明しません。興味のある読者は、自分で調べてください。

高速再送信は、ネットワークの状態がそれほど悪くないという前提に基づいています。したがって、実際のネットワークがまだ比較的良好な場合、高速再送信は依然として非常に有用です。ネットワーク環境が非常に悪い場合、多くのアルゴリズムでは効率を保証することが困難です。

• 迅速な回復

高速再送後、高速回復フェーズが始まります。このとき、cwnd は前回輻輳が発生したときの cwnd の 1/2 です。その後、cwnd は直線的に増加し、前のプロセスを繰り返します。