QUICをゆっくり解説(14)：輻輳制御

「フロー制御」の回で説明したように、輻輳制御とは途中のネットワークが溢れないようにするための仕組みです。QUICは、正確なRTT計測や、前回説明した簡潔なロス検知の機能を提供しています。このため輻輳制御としては、パケット欠落や遅延といったシグナルを使うアルゴリズムが利用可能です。RFC9002では、デフォルトの輻輳制御アルゴリズムとしてNewRenoを採用しています。

1990年に現れたRenoは、1995年に出されたアイディアに基づいて改良されNewRenoとなりました。2008年に提案されたCUBICや、2016年に現れたBBRに比べると、NewRenoは古い輻輳制御アルゴリズムです。QUICのデフォルトの輻輳制御に古いNewRenoが選ばれた理由は、QUICの標準化の初期にはCUBICのRFCは発行されておらず、またNewRenoは十分に高速で挙動が分かりやすく、標準化し易いからだそうです。今回は、RFC9002のNewRenoについて説明します。

輻輳ウインドウと状態遷移図

QUICの輻輳制御アルゴリズムは、「輻輳ウインドウ」を使って輻輳を制御します。輻輳ウインドウとは、ネットワークに送り出してもよいバイト数のことです。輻輳ウインドウから、すでに送り出したバイト数を引くと、今から送信してよいバイト数が求まります。

輻輳ウインドウの増減を管理するために、下記の図のように「スロースタート」、「輻輳回避」、「回復」の3つの状態が用意されています。この図を理解し易いように、「通信開始時」と後述する「継続的輻輳後」に分けて説明していきます。(RFC9002に掲載されている状態遷移図は、後者の場合を表現できていません。)

通信開始時

通信を開始したときは、輻輳制御はスロースタート状態(図中「開始」)から始まり、パケットが欠落すると回復状態へ遷移します。(後述のスロースタート閾値が無限大なので、輻輳ウインドウが閾値を越えることはないため、輻輳回避状態へ遷移することはありません。)

回復状態で送ったパケットに対して確認応答が返ってくると、輻輳回避状態へと遷移します。また、輻輳回避状態でパケットが欠落すると回復状態へ遷移します。このように、最初のスロースタートの後は、回復状態と輻輳回避状態を繰り返します。

次に、輻輳ウインドウの変化について説明します。各状態での輻輳ウインドウの変化は以下のとおりです。

• スロースタート：輻輳ウインドウが倍増していきます
• 輻輳回避：輻輳ウインドウが線形的に増加します
• 回復：この状態に入る際に輻輳ウインドウを半減し、確認応答が戻ってくるまでその輻輳ウインドウを維持します

通信を開始した直後の輻輳ウインドウの時間変化の例を以下に示します。輻輳ウインドウの初期値を「最大ペイロードサイズ」の2倍としています。最大ペイロードサイズは、QUICのペイロードサイズなので、UDPやIPヘッダの大きさは含みません。

前述のように、輻輳ウインドウは、スロースタートでは倍増し、輻輳回避では線形的に増加していきます。また、回復状態に入る際に輻輳ウインドウは半減します。

継続的輻輳後

「継続的輻輳」(persistent congestion)とは、一定期間の間に送信したパケットすべてが欠落した状況です。欠落は確認応答によって判断しますので、確認応答が戻って来ることが前提です。全く何も戻ってこなければ、コネクションがタイムアウトします。

確認応答の中身を検証した結果、ある期間の送信パケットが連続して欠落していれば継続的輻輳が起こったと判断します。この期間の長さは、RTTより算出しますが、詳細は割愛します。

継続的輻輳が起こったと判断した場合、輻輳ウインドウは最小の値(最大ペイロードサイズの2倍)に設定され、スロースタート状態へ遷移します。通信開始時と違って、スロースタート状態から輻輳回避状態へ移行する場合があります。その後、回復状態と輻輳回避状態を繰り返すところは同じです。

継続的輻輳が起こった後の輻輳ウインドウの時間変化の例を以下に示します。

スロースタートから輻輳回避へ移る点をスロースタート閾値と言います。スロースタート閾値の初期値は無限大です。パケットの欠落が起こって回復状態へ遷移する際に、スロースタート閾値は半減された輻輳ウインドウの値に設定されます。輻輳ウインドウが倍増していくスロースタート状態で欠落が起こったら、1つ前の値(半分の値)が安全であると言うことです。

輻輳ウインドウの実装

輻輳ウインドウ(congestion_window)をどのように実装するかイメージし易いように、以下では疑似コードを使って詳細を説明します。

前述のように、送信してよいバイト数は以下のようにして求めます。

• 送信してよいバイト数 = congestion_window – 送信したが確認応答が返って来てないパケットのバイト数の総和

初期化

通信の最初では、輻輳ウインドウが初期化され、スロースタート閾値(ssthresh)は無限大に設定されます。輻輳ウインドウの初期値としては、現在の最大ペイロードサイズ(max_datagram_size)の2倍か、10倍が推奨されています。

• congestion_window = 10 * max_datagram_size
• ssthresh = ∞

継続的輻輳の後では、輻輳ウインドウが現在の最大ペイロードサイズの2倍に設定されます。ssthreshは変化しません。

• congestion_window = 2 * max_datagram_size

輻輳ウインドウの増加

スロースタート状態と輻輳回避状態では、以下のように輻輳ウインドウが増えていきます。

• スロースタート：確認応答が返って来たパケットのバイト数を輻輳ウインドウに足します。たとえば、送信したすべてのパケットに確認応答が返って来たとすると、輻輳ウインドウは倍増します。
  • contestion_window += acked_packet.sent_bytes
• 輻輳回避：輻輳ウインドウ分のパケットすべてに対し、確認応答が戻って来た場合、(最大で)最大ペイロードサイズ分、輻輳ウインドウが増えます。確認応答が返って来たパケットごとでの輻輳ウインドウの増加は、以下の式で設定できます。
  • congestion_window += max_datagram_size * acked_packet.sent_bytes / congestion_window

スロースタートと輻輳回避を区別するには以下の条件を使います。

• スロースタート：輻輳ウインドウがスロースタート閾値より小さい
  • congestion_window < ssthresh
• 輻輳回避：輻輳ウインドウがスロースタート閾値以上
  • congestion_window >= ssthresh

回復

パケットの欠落が起こると、スロースタート閾値と輻輳ウインドウを現在の輻輳ウインドウの半分に設定します。

• congestion_window = congestion_window / 2
• ssthresh = congestion_window

そして、回復状態に入ります。回復状態では、回復状態中に送信したパケットに対して確認応答が戻って来た場合、輻輳回避状態へ遷移します。それ以外のパケットに対して確認応答が戻って来ても、パケットの欠落を検知しても、そのままの状態に留まります。