TCP輻輳制御とGoogleのBBRアルゴリズムとは何か

[[428076]]

この記事はWeChatの公開アカウント「Backend Research Institute」から転載したもので、著者はDabaiskiです。この記事を転載する場合は、バックエンド研究所の公式アカウントまでご連絡ください。

1. 輻輳制御の簡単な歴史

Wikipedia の TCP/IP プロトコルスタックの説明をいくつか見てみましょう。説明がわかりやすくなるように、いくつか変更を加えました。

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

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

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

1988 年頃までは、TCP/IP には輻輳制御がありませんでした。しかし、ネットワークアクセスの規模が大きくなるにつれて、エンドツーエンドのウィンドウ制御だけでは要件を満たせなくなり、1986 年に大規模なネットワーク麻痺が発生しました。このとき、重要な人物として Van Jacobson の名前を挙げなければなりません。

流れを変えたこの人物は、インターネットの殿堂入りを果たしました。ヴァン・ジェイコブソンは、TCP/IP 輻輳制御を提案、設計、実装し、当時の最大の問題を解決しました。ヴァン・ジェイコブソンの Wikipedia プロフィールを簡単に見てみましょう (著者は一部を削除しています)。

Van Jacobson 氏は、現在のインターネット技術の基礎となっている TCP/IP プロトコルスタックの主な起草者であり、ネットワークパフォーマンスの改善と最適化における先駆的な業績でよく知られています。

2006 年 8 月、彼は PARC に研究者として参加し、隣接するゼロックスコンプレックスにある Packet Design で主任科学者として勤務しました。それ以前は、シスコシステムズの主任科学者であり、ローレンス・バークレー国立研究所のネットワーク研究グループのリーダーを務めていました。

Van Jacobson は、IP ネットワークのパフォーマンスと最適化の改善に尽力したことで知られています。1988 年から 1989 年にかけて、TCP/IP のフロー制御アルゴリズム (Jacobson アルゴリズム) を再設計しました。また、RFC 1144 (Van Jacobson TCP/IP ヘッダー圧縮プロトコル) の TCP/IP ヘッダー圧縮プロトコルを設計したことでも知られています。彼はまた、traceroute、pathchar、tcpdump など、広く使用されているネットワーク診断ツールの共同設計者でもあります。

ヴァン・ジェイコブソンは、2012 年 4 月にコンピュータの殿堂の第一期メンバーに選出されました。コンピュータの殿堂について: https://www.internethalloffame.org/inductees/van-jacobson

以下は、Van Jacobson コンピュータ殿堂のプロフィールです。

著者は、1988 年 11 月に Van Jacobson と Michael J. Karels が発表した、輻輳回避と制御に関する 25 ページの論文を発見しました。興味のある読者は以下を参照してください。

https://ee.lbl.gov/papers/congavoid.pdf

私たちがよく使う tracetoute や tcpdump も、偉大な Van-Jacobson の傑作です。インターネット時代の恩恵を受けている私たちは、インターネットの初期の発展に多大な貢献をした先駆者、革新者、改革者を賞賛し、尊敬せずにはいられません。

2. フロー制御と輻輳制御

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

2.1 フロー制御の概要

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

Wikipedia のフロー制御の説明:

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

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

翻訳する：

データ通信において、フロー制御とは、高速な送信者が低速な受信者に負担をかけないように、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 と重複確認によって判断できます。

帯域幅の使い方

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

混雑時の対応方法

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

3. 輻輳制御を理解する

TCP トランスポート層の輻輳制御アルゴリズムは単なるコンピュータネットワークの概念ではなく、制御理論の範疇にも属するという記事を見ました。この見方は理にかなっていると感じます。

TCP 輻輳制御アルゴリズムの目的は、公平な競争、ネットワーク帯域幅の完全な利用、ネットワーク遅延の削減、ユーザーエクスペリエンスの最適化と簡単にまとめることができます。ただし、現時点では、これらの目標を達成するには、必然的にトレードオフが伴います。

輻輳制御アルゴリズムを理解する前に、核となる考え方を明確にする必要があります。学習には順序があり、誰もが独自の専門分野を持っています。これは非常に重要なコンセンサスの問題だと思います。A を踏みにじり、B を称賛するのは良い習慣ではありません。

実際のネットワーク環境は非常に複雑で、急速に変化します。これらすべてに対応できる輻輳制御アルゴリズムは存在しません。各アルゴリズムには、それぞれ固有の適用可能な分野があります。各アルゴリズムは、いくつかの重要なポイントの間でトレードオフを行います。両方を同時に実現することが不可能な場合、一部のアルゴリズムでは帯域幅の利用率を選択し、一部のアルゴリズムでは通信遅延を選択するなどです。

このコンセンサスの問題を明確にした後、私たちはさまざまな輻輳制御アルゴリズムに対する態度をより穏健にし、どれか1つが最良であるという考えに極端にならないようにする必要があります。数十年前のネットワーク状況は、現在とはまったく異なります。私たちは常に巨人の肩の上に立っており、それが科学と文明の進歩の原動力でもあります。

従来の輻輳制御アルゴリズムは、一夜にして作成されたものではありません。複雑なネットワーク環境と高いユーザー要件により、輻輳制御アルゴリズムの最適化と反復が促進されます。図に示すように、パケット損失戦略に基づく従来の輻輳制御アルゴリズムの反復バージョンをいくつか見てみましょう。

同時に、RTT 遅延戦略に基づいて制御される別のタイプのアルゴリズムもあります。ただし、このタイプのアルゴリズムは、パケット送信速度の点で十分に積極的ではない可能性があり、その競争力は他のアルゴリズムほど優れていません。そのため、ネットワーク帯域幅を共有する場合は不公平です。ただし、アルゴリズムのレート曲線は非常に滑らかです。当面、このタイプのアルゴリズムを紳士と見なしましょう。

より有名な Vegas アルゴリズムは、1995 年頃にアリゾナ大学の研究者 Larry Peterson 氏と Lawrence Burakov 氏によって提案されました。この新しい TCP 輻輳アルゴリズムは、ネバダ州最大の都市であるラスベガスにちなんで名付けられ、後に TCP Vegas アルゴリズムになりました。

RTT ベースの TCP Vegas アルゴリズムの詳細な紹介については、次のドキュメントを参照してください。

http://www.cs.cmu.edu/~srini/15-744/F02/readings/BP95.pdf

このドキュメントでは、Vegas アルゴリズムと New Reno を比較しています。直感的なグラフから、Vegas アルゴリズムの方が滑らかであるのに対し、New Reno は図に示すように大きな変動を除いてギザギザしていることがわかります。

実際にはもっと細かい分類もあるのですが、今日の焦点ではないので詳しくは触れません。現在の輻輳制御アルゴリズムは、依然としてパケットロスを基準としたものが主流です。

3.1 輻輳ウィンドウ cwnd

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

輻輳ウィンドウ (cwnd) は、TCP が ACK を受信する前にネットワークに送信できるデータの量を制限する TCP 状態変数です。

受信ウィンドウ (rwnd) は、宛先側が受信できるデータの量を通知する変数です。

これら 2 つの変数を組み合わせて使用すると、TCP 接続のデータフローを調整し、輻輳を最小限に抑え、ネットワークパフォーマンスを向上させることができます。

著者は 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 は直線的に増加し、前のプロセスを繰り返します。

4. 弱いネットワーク環境におけるAIMDの特性

ネットワークリンク内の接続数は動的かつ膨大であることは周知の事実です。各接続はブラックボックスネットワーク環境に直面しています。旅行中に地図を見てトラフィックがどこにあるかを知るのとは違います。良好なネットワーク環境を維持するために、各接続はいくつかの規則に準拠する必要があります。

接続の両端がデータパケットを制限なく送信すると、ネットワークリンクはすぐにボトルネックに達し、データ通信は完全に信頼できなくなります。したがって、安定した効率的なネットワーク環境を実現するには、多くの考慮が必要です。そこには、公平性と収束という 2 つの重要な概念が関係しています。

正直に言うと、TCP 輻輳制御の公平性と収束性を理解するためにインターネットで多くの情報を見つけましたが、まだ権威ある良い説明が得られていないため、いわゆる公平性と収束性を説明するには、いくつかの情報と私自身の理解を組み合わせることしかできません。

筆者は、公平性とはネットワークリンク内のすべての接続を指すと考えています。これらの共有リンクの接続は、開始時間と終了時間が異なります。実際の相互作用プロセスでは、各接続に帯域幅を占有する機会が平等にあります。さらに、帯域幅の制限により、2者間で通信されるデータの量は動的に調整され、ほぼ一定の値に収束します。つまり、鋸歯状またはより滑らかな変動曲線を示します。パケット損失に基づく輻輳制御アルゴリズムでは、AIMD線形乗法削減戦略が重要な制御役割を果たします。

次に、AIMD 機能に焦点を当ててみましょう。まず、AIMD プロセスを視覚的に確認するための典型的な画像を投稿しましょう。

Wikipedia の AIMD の定義を見てみましょう。

加法的増加/乗法的減少 (AIMD) アルゴリズムは、TCP 輻輳制御での使用で最もよく知られているフィードバック制御アルゴリズムです。

AIMD は、輻輳ウィンドウの線形増加と、輻輳が検出されたときの指数関数的な減少を組み合わせます。

AIMD 輻輳制御を使用する複数のフローは、最終的には収束して、共有リンクを均等に使用します。

関連する方式である乗法増加/乗法減少 (MIMD) および加法増加/加法減少 (AIAD) は安定に達しません。

簡単に訳すと、線形増加乗法減少アルゴリズムは、TCP 輻輳制御で広く使用されているフィードバック制御アルゴリズムです。AIMD は、輻輳ウィンドウの線形増加と輻輳中のウィンドウの乗法減少を組み合わせます。AIMD に基づく複数の接続は、理想的には最終的な収束に達し、同じ量のネットワーク帯域幅を共有します。関連する乗法増加と乗法減少 MIMD 戦略と増分増加と増分減少 AIAD は、安定性を保証することはできません。

MIMD や AIAD と比較すると、AIMD は、接続が輻輳回避フェーズに入るときに乗法加算戦略ではなく暫定線形加算戦略を使用するという点でより安全です。パケット損失が検出されると、乗法戦略は 1/2 に大幅に削減され、輻輳をより迅速に緩和する効果があります。逆に、パケット損失が検出されたときに AD の線形削減を使用すると、輻輳が長く続く可能性があります。全体的に、AIMD は比較的シンプルで実用的なフィードバック制御のエンジニアリングバージョンであり、エンジニアリングの収束性も備えているため、広く使用されています。

20年以上前を振り返ってみましょう。インターネットの初期の頃は、ほぼすべてのデバイスが有線ネットワークを介して接続され、通信していました。これは、輻輳制御が設計以来常に良い役割を果たしてきたという事実の重要な要因でもあります。有線接続はネットワークの安定性が優れているため、パケット損失をネットワーク輻輳の特徴と見なすのは正常です。

時代は進み、2010年以降、モバイルインターネットが盛んになり、使用されるモバイル端末の数は膨大になりました。ワイヤレスネットワークの導入により、ネットワーク環境はより複雑になり、不安定なパケット損失がより頻繁に発生しています。ただし、このときのパケット損失は、必ずしもネットワークの混雑が原因であるとは限りません。データパケット全体が複数のルーター、スイッチ、基地局などの基本的な通信機器を通過し、各リンクで異常が発生する可能性があるためです。

弱いネットワーク環境、特にモバイルインターネットでは、従来の AIMD ベースの輻輳制御戦略では、パケット損失によりネットワークスループットが大幅に低下し、ネットワーク帯域幅の利用率が大幅に低下する可能性があります。今回は、より積極的な制御戦略を採用し、より良い結果とユーザーエクスペリエンスを実現しました。

悪意のあるパケット損失の場合、AIMD ベースの輻輳制御は確かに速度制限と同等です。これは、AIMD が確かにいくぶん保守的で慎重であるためです。これは実際には理解しやすいです。

モバイルネットワーク環境では、端末が無線形式で近くの基地局とデータを交換していることは誰もが知っています。その後、データはコアネットワークに送信され、最終的に特定のサーバーが配置されている有線ネットワークに落ちます。ラストマイルエリアは高遅延シナリオに属し、有線ネットワークは低遅延および高帯域幅シナリオに属します。

海外では、従来の輻輳制御アルゴリズムを使用した場合の、弱いネットワーク環境での RTT の変化がネットワークスループットに与える影響を証明する関連実験が行われています。データと曲線は図に示されています。

実験的意義: RTT の増加は、CUBIC などの輻輳制御アルゴリズムのスロースタートフェーズに影響します。スロースタートフェーズでは、輻輳ウィンドウ cwnd が RTT サイクルごとに 2 倍になることがわかっています。ただし、RTT が大きいということは、送信者が非常に低いレートでデータを送信し、アイドル時間が長くなることを意味します。パケット送信の加速が大幅に低下するため、全体的なスループットが大幅に低下します。

実験者の元の発言を見てみましょう。

確認応答パケットが受信されるまでの遅延 (= レイテンシ) は、TCP 輻輳ウィンドウが増加する速度 (つまりスループット) に影響を与えます。

レイテンシが高い場合、送信側がアイドル状態（新しいパケットを送信しない状態）で過ごす時間が長くなり、スループットの増加速度が低下します。

5. BBRアルゴリズムの基本原理

BBR アルゴリズムは、アクティブなクローズドループフィードバックシステムです。簡単に言えば、帯域幅と RTT 遅延に基づいて、適切な送信速度と量を継続的かつ動的に探索および検索します。

BBR アルゴリズムに関する Wikipedia の説明と情報をご覧ください。

関連文献: https://queue.acm.org/detail.cfm?id=3022184

TCP BBR (ボトルネック帯域幅とラウンドトリップ伝播時間) は、Google によって設計され、2016 年にリリースされた輻輳アルゴリズムです。これまで、ほとんどの輻輳アルゴリズムは、パケット損失を信号として送信速度を低下させるものでしたが、BBR はモデルのアクティブ検出に基づいています。

このアルゴリズムは、ネットワークの最新の最大帯域幅と、その時点での送信パケットの往復時間を使用して、ネットワークの明示的なモデルを作成します。パケット送信の各累積確認応答または選択確認応答は、パケット送信から確認応答の返信までの期間中に転送されたデータの量を記録するサンプリングレートを生成するために使用されます。

このアルゴリズムでは、ネットワークインターフェイスコントローラが徐々にギガビット速度に到達するにつれて、パケット損失は輻輳を識別する際の主な決定要因とは見なされなくなり、モデルベースの輻輳制御アルゴリズムはスループットを高め、レイテンシを低くすることができ、BBR は CUBIC などの他の一般的な輻輳アルゴリズムの代わりに使用できると考えています。 Google はこのアルゴリズムを YouTube に適用し、YouTube ネットワークのスループットの世界平均が 4% 増加し、一部の国では 14% 以上増加しました。 BBR は後に Linux カーネルバージョン 4.9 に移植され、QUIC で使用できるようになりました。

5.1 パケットロスフィードバック戦略で起こりうる問題

パケット損失フィードバックは受動的なメカニズムです。根本的な原因は、これらの輻輳制御アルゴリズムがネットワークの輻輳を判断し、パケット損失の発生に基づいてウィンドウの縮小調整を行うことです。これにより、次のような問題が発生する可能性があります。

パケット損失は輻輳を意味する

現実には、ネットワーク環境は非常に複雑で、誤ったパケット損失が発生する可能性があります。多くのアルゴリズムは、輻輳パケット損失と誤ったパケット損失を区別できません。そのため、一部のネットワークシナリオでは、特定の誤ったパケット損失を前提として、帯域幅を十分に活用できません。

バッファブロート

ネットワーク接続におけるルーター、スイッチ、コアネットワークデバイスなどには、ネットワークの変動を平滑化するためのバッファがあります。これらのバッファは、輸液チューブの拡張部分のようなもので、データの流れをよりスムーズにします。ただし、ロスベース戦略は、最初にネットワークにデータをあふれさせるようなものです。このとき、すべてのバッファが考慮されます。バッファがいっぱいになると、RTTの増加やパケット損失などの問題が発生する可能性があります。これは、含めるべきではない一部の容量に相当しますが、この戦略はバッファを含めた予測に基づいているため、ディープバッファネットワークではいくつかの問題が発生します。

ネットワーク負荷は高いがパケット損失はない

ネットワークの負荷がすでに非常に高いと仮定すると、パケット損失イベントが発生しない限り、アルゴリズムは積極的にウィンドウを縮小して送信速度を下げることはありません。この場合、ネットワーク帯域幅は十分に活用されていますが、同時に、パケット損失イベントが発生していないため、送信者は依然としてウィンドウを追加しており、これは強力なネットワーク帯域幅の攻撃を示し、ネットワーク負荷圧力を高めます。

高負荷パケット損失

高負荷でパケット損失のない状況では、アルゴリズムはウィンドウを追加し続けます。これにより、パケット損失がすぐに発生する可能性があることを予測できます。パケット損失が発生すると、ウィンドウは乗算的に減少します。高速送信速度の急激な低下により、ネットワーク全体に瞬間的なジッタが発生し、全体的な状況は大きな鋸歯状の変動になります。

低負荷、高遅延、パケット損失

一部の弱いネットワーク環境では、RTT が増加し、輻輳に起因しないパケット損失も発生します。このとき、パケット損失フィードバックに基づく輻輳アルゴリズムのウィンドウは比較的小さくなり、帯域幅の使用率は非常に低くなり、スループットが大幅に低下します。ただし、実際にはネットワーク負荷は高くないため、弱いネットワーク環境では効果はあまり理想的ではありません。

5.2 TCP BBRアルゴリズムの基本原理

損失ベースのアルゴリズムに関するいくつかの問題について言及しました。TCP BBR アルゴリズムはアクティブなメカニズムです。簡単に言えば、BBR アルゴリズムはパケット損失の判断に基づかなくなり、輻輳ウィンドウを維持するために AIMD 線形乗算削減戦略を使用しなくなりました。代わりに、最大帯域幅と最小遅延をそれぞれサンプリングして推定し、その 2 つの積を送信ウィンドウとして使用します。さらに、BBR はデータ送信速度を制限するために Pacing Rate を導入し、cwnd と組み合わせて使用して影響を軽減します。

5.2.1 いくつかの用語

インド

BDP は Bandwidth-Delay Product の略称で、帯域幅遅延積と訳すことができます。帯域幅の単位は bps (ビット/秒) で、遅延の単位は s です。したがって、BDP の単位はビットです。したがって、BDP は一定期間内のリンクのデータ量を測定する指標であることがわかります。これは、水道管を満たす問題として理解できます。帯域幅は、立方メートル/秒単位の水の流量であり、遅延は、秒単位の充填時間です。この 2 つの積から、現在水道管に貯まっている水の量を知ることができます。これは、BBR アルゴリズムの重要な指標です。Tao Hui の記事の画像と、いくつかのネットワークシナリオでの BDP 計算を見てみましょう。

長飛ネットワーク

RTT ラウンドトリップ時間が長く、帯域幅が大きいネットワークをロングファットネットワークまたはロングファットパイプと呼びます。このネットワークの帯域幅遅延積 (BDP) は非常に大きくなります。理論的には、このタイプのネットワークはスループットが大きく、研究の焦点にもなっています。

TCP ペーシングメカニズム

TCP ペーシングメカニズムは、輻輳制御中にデータパケットの送信をスムーズにし、データバーストを回避し、ネットワークジッタを削減するものとして簡単に理解できます。

5.2.2 帯域幅と遅延の測定

BBR アルゴリズムのいくつかのアイデアは、以前の遅延ベースの輻輳制御アルゴリズムにも登場しており、その中で最も有名なのは TCP WestWood アルゴリズムです。

TCP Westwood は New Reno の改良版です。損失を測定に使用する他の輻輳制御アルゴリズムとは異なり、確認パケットを測定することで適切な送信速度を決定し、それに応じて輻輳ウィンドウとスロースタートしきい値を調整します。スロースタートフェーズアルゴリズムをアジャイル検出に改良し、輻輳ウィンドウを継続的に検出してアジャイル検出へのエントリを制御する方法を設計し、リンクが可能な限り多くの帯域幅を使用できるようにします。

TCP WestWood アルゴリズムも、帯域幅と遅延の積に基づいて設計されています。ただし、帯域幅と遅延は、この 2 つの値が多少矛盾する極端な値であるため、同時に測定することはできません。最大帯域幅を測定するには、最大量のデータを送信する必要がありますが、このときの RTT は非常に大きくなる可能性があります。最小 RTT を測定する場合は、データ量が非常に少なく、最大帯域幅を取得できません。

TCP BBR アルゴリズムは、交互サンプリングを使用して 2 つの指標を測定し、一定期間内の最大帯域幅と最小遅延を推定値として取得します。この記事では、具体的な実装については詳しく説明しません。

5.2.3 送信レートとRTT曲線

前述のように、BBR アルゴリズムの核心は、BDP の最適な動作点を見つけることです。関連する論文には、複合曲線チャートが掲載されています。一緒に見てみましょう。

1. 曲線図の説明:

この図は2つの図で構成されています。現在は[データ送信速度対ネットワークデータ]と[RTT対ネットワークデータ]の関係を示しています。横軸はネットワークデータの量です。

上から下の 2 つの縦軸はそれぞれ RTT と送信速度であり、プロセス全体はアプリケーション制限段階、帯域幅制限段階、バッファ制限段階の 3 つの段階に分かれています。

2. 曲線プロセスの説明:

アプリ制限アプリケーション制限段階

この段階で、アプリケーションはデータの送信を開始します。現在、ネットワークは障害がなく、RTT は基本的に一定で小さいままです。送信速度は RTT に反比例するため、送信速度も直線的に増加します。この段階では、有効帯域幅が上限に達していないと単純に考えることができ、RTT は明らかな増加がなくほぼ固定されています。

帯域制限ステージ

送信速度が増加すると、ネットワーク内のデータパケットがリンクバッファを占有し始めます。このとき、RTT が増加し始め、送信速度は増加しなくなります。有効帯域幅にボトルネックが生じ始めますが、この時点ではリンク内のバッファ領域はいっぱいではありません。そのため、データは依然として増加しており、RTT も増加し始めます。

バッファ制限バッファ制限ステージ

リンクのバッファがいっぱいになると、パケット損失が発生し始めます。これは、検出された最大帯域幅でもあります。このノード BDP+BufferSize は、パケット損失制御戦略のアクションポイントでもあります。

3. いくつかの意見

インターネット上にはこの図について言及している資料がいくつかありますが、説明があまり明確ではありません。これらの資料と私自身の理解を組み合わせると、ネットワークリンクのキャッシュ領域が使用されていない場合、RTTは最小遅延MinRTTであり、ネットワークリンクバッファがいっぱいになると最大帯域幅MaxBW（リンク帯域幅+リンクキャッシュ）が現れると思います。ただし、このときのMaxBWとMinRTTは最適ではなく、比較的高いレベルにあります。一部のデータによると、2ln2のゲイン計算によると、この時点では3BDPです。プロセス全体を通して、MinRTTとMaxBWは同時に測定できないため、個別に検出されます。

5.2.4 BBRアルゴリズムの主なプロセス

BBR アルゴリズムは CUBIC アルゴリズムに似ており、StartUp、Drain、Probe_BW、Probe_RTT などのプロセスもいくつかあります。これらの状態の移行を見てみましょう。

スタートアップスロースタートフェーズ

BBR のスロースタートフェーズは CUBIC のスロースタートフェーズに似ており、どちらも検出ベースの加速です。違いは、BBR のスロースタートフェーズでは加速に 2ln2 のゲインを使用することです。プロセス中にパケット損失が発生しても、レートは低下しません。代わりに、返された確認パケットに基づいて帯域幅の増加が決定されます。帯域幅の増加が停止すると、スロースタートフェーズは停止し、次のフェーズが始まります。最大帯域幅を見つけるプロセスでは、2BDP の超過データが生成されることに注意してください。これについては、元の英語テキストの次の説明を参照してください。

12 桁に及ぶインターネットリンク帯域幅を処理するために、Startup は、配信速度が上昇している間、送信速度を 2 倍にする 2/ln2 のゲインを使用して、BtlBw のバイナリ検索を実装します。これにより、log2BDP RTT で BtlBw が検出されますが、その過程で最大 2BDP の過剰キューが作成されます。

排水段階

ドレインフェーズの目的は、スロースタートの終了時に余分な2BDPデータをクリアすることです。このフェーズでは、送信速度が低下し始めます。つまり、単位時間あたりに送信されるパケットの数は、未確認パケットの数が

ProbeBW帯域幅検出フェーズ

スロースタートとドレインの後、送信者は安定した状態に入り、データを送信します。ネットワーク帯域幅は RTT よりも頻繁に変化するため、ProbeBW ステージも BBR のメインステージです。検出期間中、パケット送信速度が増加します。データパケット ACK が影響を受けない場合は、増加し続けます。帯域幅が減少したことが検出されると、パケット送信速度も低下します。

ProbeRTT遅延検出フェーズ

前の 3 つのプロセスは、動作中に ProbeRTT ステージに入る場合があります。最小遅延が設定された時間内に更新されない場合、より小さい MinRTT を検出しようとして、データパケットの送信速度が低下し始めます。検出が完了すると、最新のデータを使用して、スロースタートステージに入るか、ProbeBW ステージに入るかが決定されます。

これら 4 つのプロセスの概略図を見てみましょう。

曲線の説明: この 2 つの座標は、10Mbps、40msRTT のネットワーク環境における CUBIC と BBR の比較プロセスを示しています。上図では、青は受信機、赤は CUBIC、緑は BBR を表しています。下図は、上図のプロセスに対応する RTT 変動を示しており、赤は CUBIC、緑は BBR を表しています。

5.3 TCP-BBRアルゴリズムの効果

一部の記事では、BBR には明確な特徴があると考え、輻輳制御アルゴリズムを BBR 以前と BBR 以後に分けています。BBR はまだ一定の影響力を持っていることがわかりますが、BBR アルゴリズムは万能薬ではありません。ただし、まずは Google が推進する BBR アルゴリズムのいくつかの適用効果、たとえばスループット、RTT、パケット損失率への影響などを見てみましょう。

図から、YouTube が BBR アルゴリズムを適用した後、スループットは全体的に約 4% 増加し、特に日本では 14% の増加に達したことがわかります。RTT はさらに大幅に減少し、平均 33% 減少し、IN (インド) では 50% を超えました。パケット損失率テストでは、BBR は CUBIC ほど敏感ではありません。パケット損失率が 5% に達したときにのみ、スループットが大幅に低下し始めました。