The Packet Number Space Debate in Multipath QUICのメモ

「The Packet Number Space Debate in Multipath QUIC」というQUICマルチパスの拡張に関する論文です。

arxiv.org

Multipath QUICの現在のドラフトMultipath Extension for QUIC draft-lmbdhk-quic-multipath-00 上では、単一のパケット番号空間を選択するか、複数のパケット番号空間(=パス毎にパケット番号空間)を採用するかが選べるようになっています。

この論文では、ネットワークシミュレータのNS3を使って、それぞれの手法が性能に与える影響を調べています。

論文では、パスごとに1つのパケット番号空間を使用することで、Multipath QUIC接続が受信者のACK戦略に対してより耐性を持つことを示唆しています。 逆に、一つのパケット番号空間を使用すると、受信側のACKの送信の仕方による性能の影響が大きいことを示しています。

歴史的な経緯

Multipath QUICにはもともと3つの提案が存在していました。

現在では、この3つを統合した Multipath Extension for QUIC draft-lmbdhk-quic-multipath-00 で標準化が進められているようです。

この仕様のなかで、オプションとしてユーザーが選択できる項目があります。それは、パケット番号空間の使い方です。

パケット番号空間は、以下の2つのうちどちらか一つを使用することができます。

  • すべてのパスで共通するパケット番号空間を使用
  • 複数のパケット番号空間を使用(=1つのパス毎に一つのパケット番号空間)

まずは、一つのパケット番号空間を使う場合と複数のパケット番号空間を使う場合の技術的な違いを説明します。

Single Packet Number Space

この方法は、通常のQUICと同じパケット番号空間の使い方をします。

この場合、パケット番号NがあるパスAで送られたときに、パケット番号N+1は別のパスBで送られる可能性があります。

Figure 1aは、12個のパケットをラウンドロビンで2つのパスに振り分けて送った場合を説明しています。

f:id:neko--suki:20211213212030p:plain
Figure 1a (論文からの引用)

上のパスは偶数番号のパケットを、下のパスでは奇数番号のパケットを送っています。

パケットは通常のACKフレームでACKされます。そのため、パスの性能が違う場合(マルチパスの場合は違う場合が多い)、受信者はパケット番号順通りには受信しない可能性が高いです。

例えば先ほどの図で、下のパスが上のパスより速いとします。

クライアントは、上のパスからパケット番号0、2、下のパスからパケット番号1,3,5のパケットを受信したことをACKします。この時、ACKフレームには、[0-3], [5] の2つの範囲が入ったACKフレームを送信します。

それから、下のパスからパケット番号7の4つ目のパケットを受信したとします。これによって、ACKフレームには新しい範囲が作られます。つまり、[0-3], [5], [7] という範囲がACKフレームに含まれます。

1つのパケット番号空間を使う場合、受信者が送るACKフレームに含まれる範囲の数に以下のような懸念があります。

  • もし、パス間のレイテンシーが異なると、このACKの範囲の数がすぐには減らない可能性
  • 実装はACKフレームに含むことができる範囲の数を制限している可能性

このため、最終的に受信されていたとしても、遅れてACKされる、あるいはACKされないパケットが発生するかもしれません。 また、ACKフレームのACKディレイフィールドは、最大のパケット番号のものが含まれるので、RTT評価の精度が下がる可能性があります。

Multiple Packet Number Spaces

複数のパケット番号空間を使う場合、パス毎に一つのパケット番号空間が使われるため、それぞれのパスでは連続したパケット番号が使われることになります。

f:id:neko--suki:20211213213236p:plain
Figure 1b(論文からの引用)

また、ACKを返すときにはACK_MPフレームが使われます。

この方法では、パスの性能の違いによって範囲の数が巨大になることを防ぐことができます。

しかし、この方法にも欠点はあります。

まず、エンドホストは、パケット番号空間を識別するために長さが0ではないConnection IDの使用が必須になります。

次に、AEADの使い方が変わります。QUICはAEADのナンスの計算にパケット番号を使用しています。ナンス再利用してはいけないため、ナンスにパスの識別子を追加する必要があります。

詳細は、https://datatracker.ietf.org/doc/html/draft-lmbdhk-quic-multipath-00#section-7.2.1 に書かれています。

評価

評価にはNS3に含まれるネットワークシナリオを使用しています。

QUICの実装は2つのOSS実装を使用しています。

実装 一つのパケット番号空間 複数のパケット番号空間 CUBIC BBR
picoquic
PQUIC × ×

picoquicのロス検出やマルチパス固有の判断ロジックなどはパケット番号に関わらず同じようです。

両者の実装は、ACK(ACK_MP)フレームに含まれる追加のACKブロックを32個に制限しています。なので、ACK(ACK_MP)フレームは最大で33個に制限されます。

picoquicとPQUICでは、最も新しくACKされたパケット番号に近い範囲をACKするようにしているようです。(?)

実験では遅延と帯域を設定しています。実験用のパラメータは、WSPアルゴリズムという手法で、パラメータ空間を広くカバーするために95個のパラメータを選んで実行します。

実験では、50MBのファイルを単一のGETリクエストでダウンロードします。大きなファイルの転送なので、初期の受信バッファは2MBにしてパケットのスケジューラへの影響を制限しています。

クライアントは最初にハンドシェイクをし、終わったらすべてのパスをバリデーションします。( 3.1. Path Initiation)

転送時間は、クライアントによって最初のQUICパケットが送られてから、クライアントがCONNECTION_CLOSEを含む最後のフレームを受信するまで続きます。また、解析用に、クライアントサイドとサーバーサイドでQLOGを生成しています。

以下の3つの評価を行っています。

  • 同じ特徴を持った2つのパスがある状態
  • 2つのパスが異なる帯域と遅延を持った状態
  • 3つのパスで異なる帯域と遅延を持った状態

Homogeneous 2-Path Experiments

同じ特徴を持った2つのパスがある場合、つまり遅延と帯域が同じ場合、受信側でパケットの順番が入れ替わることはあまり多くないため、大きな性能差がないことが予想されます。

実験ではTable 1の範囲のパラメータを使用します。

f:id:neko--suki:20211214223449p:plain
Table 1

明示的に言及がない限りロスがないネットワークでバッファサイズが帯域遅延積の1.5倍を使用しています。それでも、ボトルネックルーターバッファオーバーフローによるロスは発生しています。

Figure 2aは、50MBのファイルの転送が終わるまでの時間を載せています。

f:id:neko--suki:20211214223845p:plain
Figure 2a (論文からの引用)

f:id:neko--suki:20211214224723p:plain
Figure 2b (論文からの引用)

f:id:neko--suki:20211214230307p:plain
FIgure 2c (論文からの引用)

Figure 2a から予想していた通り、一つのパケット番号空間と複数のパケット番号空間の大きな違いは見られません。

Figure 2b はクライアントが送信したACK/ACK_MPフレームに含まれる範囲の平均サイズをプロットしています。複数のパケット番号空間はパス内でのリオーダリングが起きないので単一の範囲を返すことが多いです。それでも、バッファオーバーフローによっておこるパケットロスによって、平均サイズが1より大きい場合がありました。

一つのパケット番号空間の場合、バッファオーバーフローによるロスがない場合でもACKフレームが多くの範囲を含む場合が発生しています。(Figure 2b のSPNSの線2本)

リオーダリングは、あるパスで他のパスよりも多くパケットを送ったときに、そのキューイングディレイによって発生します。その後、ACKフレームで複数の範囲を受信すると、サーバーは負荷が小さいパスで大量のパケットをバースト送信します。

picoquicにはこのような効果を押さえるペーシングが組み込まれています。

しかし、ACKフレームに含まれる範囲が多い現象は、受信側がACKフレームに含める範囲をより制限した場合に問題になります。

もし、リオーダリングが多くのパケットを含む場合、クライアントは受信しているパケットもACKしない可能性があります。

Figure 2b のオレンジのラインACKフレームに含まれる範囲の数を5個(デフォルトの1つ+追加のもの4つ) にした場合を表しています。平均のブロックサイズが5に近いことが分かります。また、Figure 2aを見ると、バッファオーバーフローしがちなcubicの場合に転送にかかる時間が長くなっています。

Figure 2cでは再送されたバイト量と送信するファイルサイズ(=50MB)との相対的なサイズを計測しています。特に、ACKブロックの数が制限されている場合、シングルパケット番号空間はより多くの再送が発生していることが分かります。(SPNS Cubic [4AB], SPNS BBR [4AB])

同質なネットワークパスの場合であっても、ACKの制限によってACKされないパケットが発生します。それにより不要な再送が発生し、送信レートが下がり、全体の性能が低下します。

BBR(SPNS BBR)は、CUBICと比べてパケットロスの影響が少ないので、性能への影響はCUBICよりは少ないです。

Heterogeneous 2-Path Experiments

両方のパスが同じという環境は現実的ではないため、パス毎に異なる遅延・帯域を設定で実験します。

ここでは、Table 2 のようなパラメータ空間を使用します。RTT/帯域ともに、合計の値は同じ値で、比率を設定しています。例えば、帯域のバランスが0.9で、RTTのバランスが0.1の場合、最初のパスは90Mbps/20ms、2つ目のパスは、10Mbps/180ms となります。

f:id:neko--suki:20211214231028p:plain
Table 2

理論的には、すべての実行で帯域が同じなので、性能の比較が簡単に行えます。

Figure 3aから、ACKブロックの上限を32にして、cubicを検討した場合、picoquicの一つのパケット番号空間の結果(SPNS cubic)は、picoquicの複数のパケット番号空間(MPNS cubic)の場合とPQUIC(複数のパケット番号空間+Cubic)の場合に近い性能になっている。

f:id:neko--suki:20211218124237p:plain
Figure 3b(論文からの引用)

2つのパスが同じ場合と同様に、picoquicの一つのパケット番号空間の場合、複数の範囲を含むACKフレームが発生しています。しばしば上限に到達しているケースも見られます。

もし、ACKブロックの数をより制限すると、転送性能は低下し再送は増加します。

特に、単一のパケット番号空間でCUBICを使用している場合で、ACKブロックを4に制限している場合は70%のデータが再送される場合がある。その時にいくつかのデータは8回も再送されていました。

また、picoquic+BBRの場合、CUBICよりも悪い結果になっている場合があります。特に、シングルパケット番号空間のpicoquic with cubicで、ACKブロックが4つまでの時に、70%より多いデータが再送されており、いくつかのデータは8回も再送されていました。(Figure 2cより)

更に、picoquic BBR の組み合わせは、cubicより転送時間が長くなっていまます。

picoquicの実装者にこれを報告したところ2つの理由が見つかりました。

最初にBBRの性能の観点です。受信側のACKフレームのスケジューリングに関連しています。

特定の状況下では、ある範囲が常に遅いパスで送られています。それから、後の範囲が速いパスで先に到着します。これによって、RTTの評価とRACKベースのロス検出アルゴリズムに影響を与えました。

これは、両方のパスでのACK(_MP)を送るように修正されました。

(ここはよくわからなかった) また、最大の範囲が最初にACKされていること判明しました。もし大きなパケットのリオーダリングがあった場合、パケットは遅れて、あるいは、ACKされなくなります。その結果、不要な再送が発生しました。そのため、picoquicでは、ACKしたい範囲の最大数を把握した上で、最も低い範囲を最初に配置するヒューリスティックを搭載するようになりました。ここ以降の評価は、picoquicを修正したバージョンで評価しています。

Figure 4は再評価した結果を載せています。

f:id:neko--suki:20211214233714p:plain
Figure 4a (論文からの引用)

f:id:neko--suki:20211215211713p:plain
Figure 4b (論文からの引用)

f:id:neko--suki:20211218124923p:plain
Figure 4c (論文からの引用)

また、Figure5は、オリジナルと修正されたバージョンの転送時間の比率を載せています。(afterのほう早ければ、Time before fix / Time after fix > 1 となる)

f:id:neko--suki:20211215211126p:plain
Figure 5 (論文からの引用)

picoquic+BBRはかなりの改善がみられます(Figure 4aより)。BBRはパスの遅延にセンシティブなので、両方のパスで重複したACKを送ることでRTTの評価が安定します。

このACKの重複は複数のパケット番号空間のCUBICにも良い影響を与えます。

一方、範囲の選択方法を変えることの影響も見られます。

Figure 4bから見てわかるように、一つのパケット番号空間の場合、25%のACKフレームが上限に到達してしまいます。(Figure 3bは平均、Figure 4bは75%値であることに注意)

低い範囲を最初にACKすることは、いくつかのネットワークではよい結果につながりますが、他のネットワークでは悪い結果につながってしまいます。 もし、受信者がすべての情報を提供しなければ、送信側が最適ではない判断をし、再送するデータが増えてしまいます。

興味深いことに、picoquicの複数のパケット番号空間+CUBICの場合は再送(Figure 4c)と、ACK_MPフレームが複数の範囲を含む (4bより)現象が発生しています。しかし、PQUIC (CUBIC) では、picoquic(BBR)のように発生はしていません。(複数のパケット番号空間では本来起きにくいと言われた現象が来ている。)

これには2つの要素が関連しています。

最初に、CUBICの実装が異なる点です。picoquicは、評価したパスのRTTをもとにスロースタートフェーズを抜けるかを決めています。これにより、picoquicのCUBICはPQUICのものよりわずかにアグレッシブになるのかもしれません。

次に、Figure 6 から見られるように、PQUICの受信側のACK(_MP) の送信はpicoquicよりもアグレッシブです。

f:id:neko--suki:20211215212348p:plain
Figure 6 (論文からの引用)

PQUICの受信者は、2つの新しいパケットがあるパスから来たら、両方のパスにACK_MPフレームを送信しています。

(ここはよくわからなかった) また、picoquicは、最初に2つに制限しているが、ACK_FREQUENCYフレームをサポートしています。もしパケットのリオーダリングが発生したら、ピアに即座のACKを行わないように要求します。これにより、数ミリ秒の待ち時間が後続のACK(_MP) フレームとの間に発生します。しかし、その間にも、数十ものパケットがサーバーから届きます。ACK_MPフレームの最小サイズは、ACKフレームより大きいですが、picoquicの複数のパケット番号空間は、シングルパケット番号空間の場合よりも少ないACKに関連したバイトを送るようにしています。小さい範囲と、アウトオブオーダーによってトリガされたACKが少ないことがこの結果(PQUICは単一の範囲を含み、picoquicは多くの範囲を含む場合が多い)を説明しています。

Heterogeneous 3-Path Experiments

通常は2つのパスを考えるが、2以上のパスが同時に持たれる可能性もある。例えばデュアルスタック Wi-FiLTEなどが考えられます。

それらをカバーするために、Table3のようなパラメータ空間を検討しています。ここまでの実験とは異なり、帯域とRTTが重みをもつこととします。

f:id:neko--suki:20211215213508p:plain
Table 3

例えば、RTTの重みが、0.5, 0.25, 0.75 だと、100ms, 50ms, 150ms となります。(1.0が200ms)

3つのパスがある場合の実験もpicoquicは修正されたバージョンを使います。

f:id:neko--suki:20211215213712p:plain
Figure 7a (論文からの引用)

f:id:neko--suki:20211215213828p:plain
Figure 7b (論文からの引用)

f:id:neko--suki:20211215214115p:plain
Figure 7c (論文からの引用)

Figure 7b から、単一のパケット番号空間の場合、ACKフレームに含まれる範囲の上限が32では、受信側の情報を送信側に伝えられていないことが分かります。

実際、ほぼすべての実験で、30%のACKフレームが上限に到達していることが分かります。(Figure 7bは70%値。70%値で33の範囲を含んでいるので、残りの30%のパケットも同様に33の範囲を含む)

この情報の欠如が、不要な再送を発生させていることが、Figure 7cから分かります。また、その結果、複数のパケット番号空間と比べて性能が低下していることが分かります。

そのようなネットワークであっても、単一のACKフレームに含まれる範囲を増やすか減らすことで、複数のパケット番号空間と同じように動かせる可能性があります。

しかし、一つのパケット空間を使用する場合、複数のパケット番号空間を使う場合よりも受信側の実装に依存することになります。(つまり、ACKの上限によって性能が制限される。これは受信側の挙動である)

4 DISCUSSION AND NEXT STEPS

この論文では、パケット番号をbulk transferの影響を評価した。

このシナリオはすべてのユースケースをカバーしないが、bandwidth aggregationな結果を評価できる。最終的に、両方の設計がこれに対応しなければいけないことが分かる。

しかし、実験結果から、シングルパケット番号空間の場合、性能は受信側により依存する。

すでにhuetimaで議論されるように、一つのパケット番号空間と複数のパケット番号空間にはトレードオフがあります。

シングルパケット番号空間の場合、zerolength connectionIDが使え、かつ、プロトコルへの追加は少なく、ナンスの計算方法も変わりません。

一方で、複数のパケット番号空間は、現在のロス検出アルゴリズムをパス毎に維持でき、複雑なACKの生成(頻度も含む)無しで、受信側に依存しないパフォーマンスを維持できます。

マルチパスが含まれると、パケットスケジューリングやパス管理といった新たな対処が必要になるため、マルチパスプロトコル使用時には、これらのアルゴリズムに複雑さを加えない方が賢明かもしれません。

まとめ

現状のMultiplath QUICの提案では、パケット番号空間を一つにするか、パス毎に独立させるかの2つの方法が選択できます。

マルチパスのパス間の差異により、リオーダリングが発生したときに、受信側が送るACKにすべての範囲が含まれない可能性があります。特に受信側が一つのACKフレームに含むACKフレームの数を実装で制限している場合に影響が出やすくなります。(仕様上は、QUICパケットの上限まで入れられる)

送信側に適切に情報が伝わらないので、例えばロスなどの判断を誤る可能性があります。ACKが適切に送信側に伝わらないことで、余計な再送が発生し性能が低下します。

リオーダリングは複数のパケット番号空間よりも一つのパケット番号空間を使用している方が発生しやすいです。ただし、受信側の実装によっては、複数のパケット番号空間でも発生することがあります。(PQUIC cubicとpicoquic CUBICの比較)

また、受信側のACKの返し方の実装によって、発生の仕方も変わってきます(Figure 5より)。

論文の序章で書かれていますが、仕様上は選択できるものよりは統一されていた方が普及しやすいと考えられます。

これからの動向に注目ですね。