「idle」がアイドルではない場合：Linuxカーネルの最適化がQUICバグになった経緯

RFC 9438で標準化されたCUBICは、Linuxのデフォルトの輻輳制御アルゴリズムであり、その結果、パブリックインターネット上のほとんどのTCPおよびQUIC接続が、利用可能な帯域幅を探索し、損失を検出した際にバックオフし、その後回復する方法を管理します。Cloudflareでは、オープンソースのQUIC実装である quicheは、CUBICをデフォルトの輻輳コントローラーとして使用しています。つまり、このコードは、当社が提供するトラフィックの大部分のクリティカルパスにあります。

この記事では、CUBICの輻輳ウィンドウ（cwnd）が最小値で永続的にピン留めされ、輻輳が崩壊するイベントから回復できないというバグについてお話します。

話は、RFC 9438 §4.2-12に記載されているアプリ制限の除外に沿ったLinuxカーネルの変更から始まります。CUBICは、QUICの実装に移植された際に予期しない動作が表面化した、TCPの実際の問題に対する修正です。開発者に明らかになりました。末尾は、理想的な（ほぼ）1行の修正でサイクルを断ち切りました。

CUBICのロジックを簡潔に

核心的な問題に入る前に、輻輳制御アルゴリズム（CCA）について簡単におさらいしておきたいと思います。

CCAが回す中心的なボタンは、輻輳ウィンドウ（cwnd）です。これは、送信者が一度に送信できる（送信済みだが未確認の）バイト数の上限を示します。cwndが大きいほど、送信者はラウンドトリップでより多くのデータをプッシュできます。小さいcwndがそれをスロットルします。CUBICを含めた損失ベースのCCAは、究極的にはネットワークが健全に見える時にcwndをどのように成長させ、不健全な場合は縮小するかを決定するためのポリシーなのです。

基本的に、CCAはネットワークの「利用可能な帯域幅」を推測することで、データ転送を最大化することを目的としています。 1Gbpsのサブスクリプションの支払いをして、そのほんの一部しか使いたくはないからです。CUBICが属する損失ベースのアルゴリズムのファミリーは、（1）パケットロスがない場合は、送信レートを高める（つまり、帯域幅利用率を高める）という基本的な前提で動作します。 (2) 損失がある場合、損失ベースのアルゴリズムは、ネットワークの容量を超えていると想定するため、送信者はバックバックする必要があります（つまり、帯域幅使用率の低減など）です。

このロジックは、ここ数年にわたって再考されたいくつかの前提に基づいて構築されています。しかし、その説明はまた別の機会に持ちたいと思います。

症状：61%が失敗するテスト

当社の調査は、イングレスプロキシ統合テストパイプラインでの予期せぬ障害の報告から始まりました。この不安定な動作は、CUBICの接続初期に大幅な損失が発生するシナリオで評価されたテストで現れました。

輻輳崩壊後の復旧はとてつもない体制ですが、まさに輻輳コントローラーが対処すべき体制といえます。ほとんどの輻輳制御テストは、アルゴリズムの定常状態と成長段階で行われます。接続が切断された後、最小cwndで起こることを調査することは、はるかに少ないことになります。ステート空間のこの角のバグは、スループットダッシュボードでは見えず、静的レビューでは検出できません。CCAを意図的に起動して、後退するかどうかを監視することで初めて表面化します。これは、まさにこのテストが行ったのです。

シミュレートされたテストセットアップには、以下の詳細が含まれます：

ローカル（localhost）でQuiche HTTP/3クライアントとサーバーが実行
RTT = 10ミリ秒（設定で設定）
HTTP/3でダウンロードした10MBファイル
CUBICの輻輳制御を使用する
最初の2秒の間に30%のランダムなパケットロスが発生
2秒後には損失が完全に停止
このテストではダウンロードが完了するまでのタイムアウトは10秒と余裕があるため、4〜5秒で完了することが予想されます。

予想される動作は単純です。CUBICは、損失フェーズ中にいくつかのヒットを受け、輻輳ウィンドウを減らし、損失が停止したら、着実に増加し、タイムアウト内にダウンロードを完了します。しかし、複数の100回の実行で、テストの約60%が、余裕のある10秒のタイムアウト以内にダウンロードを完了できていないことが確認されました。

異常：損失ゼロの999状態遷移

私たちは quicheのqlog出力にパケットロスイベントを組み込み、輻輳コントローラー内で何が起こっているかを理解するための視覚化を構築しました。

^{失敗したテストの接続概要。T=2s後には、パケット損失が完全に停止しますが、cwndは最低フロアでピン留めされたままで、輻輳の状態は回復と輻輳回避の間でおよそ14ミリ秒ごとに変動します。}

2秒（2000ミリ秒）を超えると、パケットの損失は完全に停止します。しかし、実行中のバイト数は横ばいのままであり、これはCUBICアルゴリズムのコアロジックに矛盾します。損失がなければ、より多くのガスを供給してスロットルを増加させます（私たちの世界では、より多くのバイト数を増やします）。ここで、疑問が生じます。ネットワークがパケットをドロップしなくなったのであれば、なぜ輻輳ウィンドウは拡大できないのでしょうか？

この領域にズームインすると、CUBICは急速な変動に達し、プロットに示されているように、輻輳回避状態（運用体制フェーズ）と復旧状態（パケット損失の復旧状態）の間で999の遷移が起き、 6.7秒で完了しましたこれは、~14msごとに1回の遷移が行われており、接続のRTT（10ms）に疑わしいほど近い値です。この期間全体を通して、cwndは最小フロアの2700バイト、つまり2つのフルサイズパケットでロックされます。

明らかに何かがCUBICのロジックの何かが、接続の状態を誤って解釈しています。重要なヒントは、往復時間（~14ms）がRTTと一致していることです。回復/回避の反転をトリガーするものは、接続のACKクロックによるロックステップで、ラウンドトリップごとに一度発生します。クライアントからの各往復のACKがサーバーの次の送信をトリガーする、セルフクロックアルゴリズム。これはダウンロード（サーバーからクライアントへ）であるため、問題のACKはクライアントからサーバーに移動し、CUBICのステートマシンはサーバー側で実行されます。それらのACKが到達するたびに、bytes_in_flightがゼロになり、サーバーは次の2つのパケットバーストを送信しますバグのトリガーとなるものです。

この動作がCUBIC固有のものであることを確認するため、損失ベースのファミリーの別のメンバーですが、異なる増加率を持つRenoでも同じテストを実行しました。結果は確信的なものでした：パス率は100%で、損失フェーズ後にRenoはきれいに回復し、これがCUBIC関連のバグであることを明らかにしました。

^{Renoは、T=2sで損失フェーズが終了した後正常に回復し、約5sでダウンロードを完了します。}

根本原因を追跡する

ロスベースアルゴリズムには、ガスとブレーキという2つのペダルがあり、加速方法が異なります。CUBICには追加の機能があります。ここでは、bytes_in_flight == 0に焦点を当てます。

アイドル中TCP CUBIC（Linux、2017年）

バグを理解するには、まず最適化から来たものを理解する必要があります。2017年、LinuxカーネルのCUBIC実装に問題が見つかりました。コミットメッセージは次のように説明します：

エポックは最初と損失が発生した時にのみ更新/リセットされます。now - epoch_startのデルタ"t"は、アプリのアイドル後に任意に大きくなることができ、bic_targetも同様です。結果的に、曲線（ca->cntの逆）は非常に大きくなり、最終的にca->cntは遅延が生じ、2につながる
これは、slow_start_after_idleが無効になっている場合に特に顕著で、アイドル状態の数秒後に危険なcwndインフレーション（1.5倍のRTT）が発生します。

epochは、CUBICが成長曲線を定着させるために使用する参照タイムスタンプです。W_cubic(delta_t)は、delta_t = now - epoch_startによってパラメータ化され、epochはCUBICが成長関数を再起動するたびにリセットされます。特に損失イベントが発生してcwndが減少した後です。リセットの間、delta_tは経過時間と共に単調に増加します。

アプリケーションがしばらくの間アイドル状態（送信を停止）になり、その後再開すると、CUBIC成長関数 W_cubic(delta_t) は、下図に示すように、delta_t を now - epoch_start として計算します。アイドル中にエポックが更新されなかったので、delta_tは巨大で、巨大なターゲットウィンドウを生成し、CUBICはすぐにcwndを不当な値まで膨らませようとします。

Jana Iyengarの最初の修正は、アプリケーションが送信を再開した時に`epoch_start`をリセットすることでした。しかし、ニール・カードウェル氏は、そのアプローチの欠陥を指摘しました。

...CUBICアルゴリズムに曲線の再計算を依頼して、cwndが現在の場所から再び急上昇し始めるようにします（CUBICは喪失直後に行うように）。理想的には、Cwndの成長曲線は同じ形になり、アイドル期間だけ分だけ後で移動するだけです。

Eric Dumazet、Yuchung Cheng、Neal Cardwell氏が考案した高性能ソリューションは、リセットするのではなく、アイドル期間によってエポックを前進させるものでした。これにより、CUBICの成長曲線の形が保たれ、代わりにスライディングが行われるため、アルゴリズムが先に作業を別の場所に到達させることができます。

クイッチするポート（2020年）

CUBICがquicheに初めて実装された時に、このアイドル期間の調整は移植されました。ただし、ユーザー空間で動作するQUICには、TCPのカーネルレベルのCA_EVENT_TX_STARTコールバックがありません。その代わりに、quicheの実装はon_packet_sent()内のアイドル状態をチェックします。

// cubic.rs — on_packet_sent() (simplified)
/// Updates the state when a packet is sent.
fn on_packet_sent(&mut self, bytes_in_flight: usize, now: Instant, ...) {
    // If the sending burst is restarting (i.e., bytes_in_flight was zero before this send),
    // adjust the congestion recovery start time to account for the gap in sending.
    if bytes_in_flight == 0 {
        let delta = now - self.last_sent_time;
        self.congestion_recovery_start_time += delta;
    }
    // Record the time of this send event.
    self.last_sent_time = now;
}

どこが問題点か：QUICの違い

quicheに移植された修正には、元のカーネル変更のバグが含まれていましたが、約1週間後にkernel cubicモジュールへのフォローアップ変更で修正されました。2つ目の修正のコミットメッセージは次のように説明しています：

tcp_cubic: epoch_startを将来に設定しないでください bictcp_cwnd_event()でのアイドル時間の追跡は不正確です。epoch_startは通常、送信時ではなくACK処理時に設定されるためです。
適切な修正を行うには、ステート変数を追加する必要がありますが、 CUBICのバグに気付く前にずっとそこにあることを考えると、この手間のかからないように見えます。
将来、epoch_startを設定しないようにしましょう。さもないと、 bictcp_update()がオーバーフローし、CUBICが再び cwndを急速に増加させてしまう可能性があります。

コミットメッセージに記載されているように、回復開始時刻はACK処理中に設定されており、送信時間に基づく調整の計算により、回復開始時刻を押し出すことができるのです。これは、テストで見られた回復と輻輳回避の遅れを説明しています。このトラップは、すべての着信ACKがbytes_in_flightがゼロになるまで一貫してトリガーされます。これは、実際には、Cwndが最小（2パケット）まで崩壊し、アプリケーションがACKが到着した瞬間に別の完全なウィンドウを送信する準備があることを意味します。この体制外では、bytes_in_flight == 0がすべての送信で保持される可能性は低いため、バグがトリガーされる可能性は低くなるのです。

接続開始時にもこうしたことが行われないのはなぜか？このバグは、接続がスロースタートを終了し、輻輳回避に切り替わった場合にのみトリガーされます。スロースタートを終了する前に、congestion_recovery_start_timeが設定されていないため、on_packet_sentのバグのあるブランチには進めるリカバリ境界がありません。スロースタート中、CUBICのcwndは、すべての損失ベースの CCA に共通する Reno スタイルの ack ベースのルールに従って増加します。つまり、接続が輻輳回避状態になったときにのみ、立方曲線とcongestion_recovery_start_timeに対する感度が考慮されるようになります。つまり、トラップには、回復境界を設定するための実際の損失イベント、輻輳回避が実行されていること、およびcwndが 2 パケットのフロアに縮退しているという 3 つのことが同時に必要です。

^{自己永続的な回復の罠。最小cwndでは、ACKサイクルごとにアイドル期間の調整をトリガーし、デルタを増大させます。}

最小cwnd（2パケット）では、接続のダイナミクスは「ゼロスパイラル」にシフトし、アイドル期間の最適化が自己実現的な予測をたどります。このトラップは継続的なループで動作します。

パケットの送信とACK: 送信者は2つのパケットウィンドウ全体を送信します。1つのRTT（～14ms）後に、両方のパケットがACKされるため、bytes_in_flightがゼロになります。
アイドル中の誤検出：次のバーストが送信されると、on_packet_sent()はbytes_in_flight == 0を見て、接続がアイドル状態であったと判断しますが、輻輳は制限されていました。
膨張したデルタ: 計算は now - last_sent_time を使用してアイドル期間を決定します。輻輳ウィンドウ（cwnd）が最小の時、last_sent_timeは前回のRTTサイクル開始のタイムスタンプです。したがって、結果のデルタは約14ミリ秒（接続のRTT＋追加のラウンドトリップエラー）です。このRTTサイズのデルタは、「アイドル」タイムとして誤って適用されます。接続がアイドル状態だった実際の時間（最後のACKが到着してから次のパケットが送信されるまでの処理ギャップ）は、事実上0です。真のギャップではなく完全なRTTを測定することで、デルタは大幅に膨らみ、回復開始時間を積極的に前倒しし、場合によっては未来にまでシフトさせます。
認識された復旧：復旧開始時刻は将来のことになるため、in_congestion_recovery()チェックはすべての着信ACKに対してtrueを返します。次のACKの処理が回復を出て、回復開始をlast_sent_timeよりも長い時刻に設定することで、輻輳コントローラーが次の送信をするときに、回復時間を遅らせる可能性が高くなります。
停止: CUBICは、回復期間中と認識されるパケットのcwndの増加をスキップするため、ウィンドウは2つのパケットでピン留めされたままとなり、次のACKでパイプが完全に消費されることを確認し、サイクルを再起動します。

そして、このループは、スケジューラのジッタやACK処理のばらつきから生じる小さな逸脱の蓄積が何千回も繰り返され、in_congestion_recovery()の<=境界が次のパケットの送信時間より遅れて、サイクルが断たれるのです。

修正方法：アイドル状態を適切な瞬間から測定する

デススパイラルを修正するには、送信された最後のパケットではなく、bytes_in_flightが実際にゼロに移行した時点（ACKが処理された後）からアイドル期間を測定する必要があります。

コード変更

CUBICの状態にlast_ack_timeタイムスタンプを追加します。
ACKが到着したら、そのタイムスタンプを更新します。
アイドル当社のデルタ計算に使用

// cubic.rs — on_packet_sent()
fn on_packet_sent(&mut self, bytes_in_flight: usize, now: Instant, ...) {
    // Check if the connection was idle before this packet was sent.
    if bytes_in_flight == 0 {
        if let Some(recovery_start_time) = r.congestion_recovery_start_time {
            // Measure idle from the most recent activity: either the
            // last ACK (approximating when bif hit 0) or the last data
            // send, whichever is later. Using last_sent_time alone
            // would inflate the delta by a full RTT when cwnd is small
            // and bif transiently hits 0 between ACK and send.
            let idle_start = cmp::max(cubic.last_ack_time, cubic.last_sent_time);

            if let Some(idle_start) = idle_start {
                if idle_start < now {
                    let delta = now - idle_start;
                    r.congestion_recovery_start_time =
                        Some(recovery_start_time + delta);
                }
            }
        }
}

直近のACKからの実際のギャップを遅れてデルタが反映するようになり、リカバリー境界は送信時間を追い求めなくなります。

^{古いコード：境界はサイクルごとに1RTTを送り、常に次の送信、またはその前にランディングします。}

^{修正: 境界はほとんど移動しません。次の送信がその前に到達すると、cwndが成長します。}

完全にアイドル状態の接続の場合、last_ack_timeは遠く過去のものとなり、同じ式がアイドル期間全体を取得するため、元のepoch-shiftの動作は保持されます。

検証

修正を適用すると、QRフィッシングテストスイートの通過率が100%に戻りました。

^{修正後、cwndは予想されるCUBIC曲線に沿って成長し、ダウンロードは最大4～5秒で完了します。}

接続末尾での損失を心配することはありません。これは、ルーターに割り当てられたバッファを完全に活用するため、予想されることです。つまり、このテストケースでは、利用可能な帯域幅をフルに活用しています。

要点

「アイドル」は言葉にするよりも定義するのが難しいです。小さなウィンドウでの通常のパイプライン遅延は、単純なチェックではアイドル状態に見えるかもしれません。
最小Cwndダイナミクスは、ユニークなケースです。バグは高速では見えず、深刻な損失の発生後にトリガーされました。
動作の複雑さに比べ、修正は驚くほど小さいものでした。Qログのインストゥルメントと視覚化の分析で根本原因を突き止めた結果、わずか3行のコード変更が必要なソリューションになりました。調査中に述べたように、バグを見つけるための労力は膨大なものでしたが、修正自体は基本的に1行のロジックでした。

この記事で説明している修正は、Cloudflare/quiche、Cloudflareのオープンソース実装QUICとHTTP/3に貢献しています。当社のCCAへの取り組みは、ロスベースのアルゴリズムだけにとどまりません。quicheのモジュラー型輻輳制御設計を使用して、モデルベースのBBRv3実装の実験と調整を行っており、現在、QUICデプロイの割合が増加している環境で有効になっています。QUIC輻輳制御の実装とパフォーマンスについての最新情報は、今後の動きにご注目ください。

輻輳制御、トランスポートプロトコル、またはオープンソースネットワーキングコードへの貢献に興味がある方は、quiche リポジトリをご覧ください。当社では、このような問題を掘り下げることが好きな才能のあるエンジニアを常に募集しています。ぜひ、当社の求人情報をご覧ください。

Cloudflare ブログ