TCP輻輳制御アルゴリズムについての簡単な説明

最近、TCP/IP プロトコルの学習に時間を費やしました。主な理由は、TCP/IP に関する私の理解が長い間 3 ウェイ ハンドシェイクと 4 ウェイ ブレークアップに限定されていたため、より深い理解を得たいと思ったからです。さらに、TCP/IP および Linux システム レベルの多くの設計をミドルウェア システム アーキテクチャで使用できます。たとえば、TCP 輻輳制御アルゴリズムは、応答時間に基づいてフローを制限するミドルウェアでも使用できます。さらに深いレベルでは、TCP/IP プロトコルなどの基礎知識や原理技術は長い時間をかけてテストされ、先人たちの知恵の結晶であり、多くのインスピレーションと助けをすべての人に提供することができます。

この記事には略語がいくつかあります。スペースの都合上、一つ一つ説明することは不可能です。意味が分からない場合は自分で調べて、積極的に知識を求める人になってください。

TCP プロトコルには、フロー制御とブロッキング制御という 2 つの重要な制御アルゴリズムがあります。

TCP プロトコルは、スライディング ウィンドウを通じてフロー制御を実行し、送信者の送信速度を制御して、受信者が受信して処理する時間を確保します。輻輳制御はネットワーク全体に作用します。過剰なパケットがネットワークに送信されるのを防ぎ、ネットワークの過負荷やネットワークの輻輳を回避します。

輻輳アルゴリズムでは、ステート マシンと 4 つのアルゴリズムを習得する必要があります。輻輳制御ステート マシンには、Open、Disorder、CWR、Recovery、Loss の 5 つの状態があります。 4 つのアルゴリズムは、スロー スタート、輻輳回避、輻輳発生アルゴリズム、高速回復です。

輻輳制御ステートマシン

TCP と同様に、輻輳制御アルゴリズムにもステート マシンがあります。送信者が ACK を受信すると、Linux TCP はステート マシンの状態を使用して、輻輳ウィンドウ cwnd のサイズを縮小するか、cwnd を変更せずに維持するか、または cwnd を増やし続けるかの次の動作を決定します。適切に処理されない場合、パケット損失やタイムアウトが発生する可能性があります。

1 オープン状態

オープン状態は、輻輳制御ステート マシンのデフォルト状態です。この状態では、ACK が到着すると、送信者は、輻輳ウィンドウ cwnd (輻輳ウィンドウ) がスロー スタートしきい値 ssthresh (スロー スタートしきい値) より小さいか大きいかに基づいて、スロー スタートまたは輻輳回避アルゴリズムに従って輻輳ウィンドウを調整します。

2 障害の状態

送信者が DACK (重複確認応答) または SACK (選択確認応答) を検出すると、ステート マシンは Disorder 状態に遷移します。この状態では、送信者はインフライト パケット保存の原則に従います。つまり、古いパケットがネットワークを離れた後にのみ新しいパケットが送信されます。つまり、送信者は古いパケットの ACK を受信した後にのみ新しいパケットを送信します。

3 CWRステータス

送信側が明示的な輻輳通知を受信すると、輻輳ウィンドウ cwnd をすぐに減らすのではなく、ウィンドウ サイズが半分になるまで、受信した 2 つの ACK ごとに 1 セグメントずつ減らします。 cwnd が減少し、ネットワーク内に再送パケットがない場合、この状態は CWR (輻輳ウィンドウ減少) 状態と呼ばれます。 CWR 状態は、回復状態または損失状態に変更できます。

4 回復状態

送信者が十分な数（3 つを推奨）の DACK（重複した確認応答）を受信すると、この状態になります。この状態では、輻輳ウィンドウ cnwd は、cwnd がスロー スタートしきい値 ssthresh と等しくなるまで、受信された 2 つの ACK ごとに 1 セグメントずつ削減されます。スロー スタートしきい値 ssthresh は、回復状態に入ったときの cwnd の半分のサイズです。 送信者は、リカバリ状態に入るときに送信されているすべてのデータ セグメントが正常に確認されるまでリカバリ状態のままになり、その後、オープン状態に戻ります。再送信タイムアウトにより、リカバリ状態が中断され、ロス状態に入る場合があります。

5 損失ステータス

RTO (再送信タイムアウト) が期限切れになると、送信者は Loss 状態になります。送信中のすべてのデータは失われたものとしてマークされ、輻輳ウィンドウ cwnd はセグメントに設定され、送信者はスロー スタート アルゴリズムを使用して輻輳ウィンドウ cwnd を再度増加します。

損失状態と回復状態の違いは、損失状態では、送信者がセグメントに設定した後に輻輳ウィンドウが増加するのに対し、回復状態では輻輳ウィンドウは減少することしかできないことです。 Loss 状態は他の状態によって中断されることはありません。したがって、送信者は、Loss の開始時に送信されていたすべてのデータが正常に確認された後にのみ、Open 状態に戻ることができます。

4つの主要なアルゴリズム

輻輳制御は、主に 1) スロースタート、2) 輻輳回避、3) 輻輳発生、4) 高速回復の 4 つのアルゴリズムで構成されます。これら 4 つのアルゴリズムは 1 日で開発されたわけではありません。開発には長い時間がかかり、現在も最適化が続けられています。

スロースタートアルゴリズム

いわゆるスロースタートとは、TCP 接続が確立された直後に、ネットワーク チャネルの秩序を直接乱さないように、ネットワークの負荷能力をテストするために速度を少しずつ上げることを意味します。

スロースタートアルゴリズム:

1) 接続が確立されると、輻輳ウィンドウ cwnd サイズが 1 に初期化され、MSS サイズのデータ​​が送信可能であることを示します。

2) ACK が受信されるたびに、cwnd のサイズが 1 ずつ増加し、線形に増加します。

3) 往復遅延時間 RTT (ラウンドトリップ時間) が経過するたびに、cwnd のサイズは直接 2 倍になり、2 倍になり、指数関数的に増加します。

4) 上限値である ssthresh (スロー スタートしきい値) もあります。cwnd >= ssthresh の場合、「輻輳回避アルゴリズム」が開始されます (このアルゴリズムについては後で説明します)

混雑回避

前述のように、輻輳ウィンドウ サイズ cwnd がスロー スタートしきい値 ssthresh 以上になると、輻輳回避アルゴリズムが開始されます。アルゴリズムは次のとおりです。

1) ACK を受信すると、cwnd = cwnd + 1 / cwnd になります。2) 往復遅延時間 RTT が経過するたびに、cwnd のサイズが 1 つ増加します。

スロー スタートしきい値を超えると、輻輳回避アルゴリズムによって、ウィンドウが急速に拡大してウィンドウ輻輳が発生するのを防ぎ、代わりにウィンドウをネットワークに最適な値までゆっくりと増加させることができます。

混雑のアルゴリズム

一般的に、TCP 輻輳制御では、ネットワーク パケット損失はネットワーク輻輳によって発生するとデフォルトで想定されるため、一般的な TCP 輻輳制御アルゴリズムでは、パケット損失をネットワークが輻輳状態になったことを示す信号として使用します。パケット損失を判定する方法は 2 つあります。1 つは再送信タイムアウト (RTO) が経過したとき、もう 1 つは 3 つの繰り返し確認応答 (ACK) が受信されたときです。

タイムアウト再送信は、データの信頼性を確保するための TCP プロトコルの重要なメカニズムです。その原理は、データを送信した後にタイマーを開始することです。送信したデータグラムに対して一定時間内に ACK メッセージが受信されない場合は、データが正常に送信されるまで再送信されます。

ただし、送信者が重複した ACK を 3 つ以上受信した場合、TCP はデータが失われたと認識し、再送信が必要になります。このメカニズムは、再送タイマーがタイムアウトするまで待つ必要がないため、高速再送と呼ばれます。高速再送後は、スロースタートアルゴリズムは使用されず、輻輳回避アルゴリズムが使用されるため、高速回復アルゴリズムとも呼ばれます。

RTO [再送信タイムアウト] がタイムアウトすると、TCP はデータ パケットを再送信します。 TCP はこの状況が非常に悪いと考えており、強く反応しています。

• パケット損失のため、スロー スタートしきい値 ssthresh は現在の cwnd の半分、つまり ssthresh = cwnd / 2 に設定されます。
• cwndは1にリセットされます
• スロースタートプロセスの開始

最も初期の TCP Tahoe アルゴリズムでは上記の処理方法が使用されていましたが、パケットが失われるとすべてを再開する必要があったため、cwnd は 1 にリセットされ、ネットワーク データの安定した送信にはつながりませんでした。

したがって、TCP Reno アルゴリズムが最適化されます。重複した ACK が 3 つ受信されると、TCP は再送信前に RTO がタイムアウトするまで待つのではなく、高速再送信アルゴリズムを開始します。

• cwnd のサイズは現在のサイズの半分に縮小されます。
• ssthreshは縮小されたcwndサイズに設定されます
• 次に、高速回復アルゴリズム「Fast Recovery」を入力します。

高速回復アルゴリズム

TCP Tahoe は初期のアルゴリズムであるため、Reno アルゴリズムとは異なり、高速回復アルゴリズムはありません。高速回復に入る前に、cwnd と ssthresh は元の cwnd の半分に変更されています。高速回復アルゴリズムのロジックは次のとおりです。

• cwnd = cwnd + 3 * MSS。3 * MSS を追加する理由は、3 つの重複した ACK が受信されるためです。
• DACK で指定されたパケットを再送信します。
• さらに多くの DACK が受信されると、cwnd サイズは 1 つ増加します。
• 再送信されたパケットが成功したことを示す新しい ACK が受信された場合、高速回復アルゴリズムは終了します。 cwnd を ssthresh に設定し、輻輳回避アルゴリズムに入ります。

図に示すように、5 番目のパケットが失われているため、受信側は 3 つの重複した ACK、つまり ACK5 を受信します。したがって、ssthresh をその時点の cwnd の半分、つまり 6/2 = 3 に設定し、cwnd を 3 + 3 = 6 に設定します。次に、5 番目のパケットを再送信します。新しい ACK、つまり ACK11 が受信されると、高速回復フェーズが終了し、cwnd が現在の ssthresh、つまり 3 にリセットされ、輻輳回避アルゴリズム フェーズに入ります。

追記

この記事では、TCP 輻輳制御のいくつかのメカニズムについて簡単に説明します。ただし、これらの輻輳制御にはまだ多くの欠陥があり、最適化の余地があります。業界では、Google の BBR など、新しい輻輳制御アルゴリズムも絶えず導入されています。これらについては今後も議論を続けていきますので、ご注目ください。