XLINK: QoE-Driven Multi-Path QUIC Transport in Large-scale Video Services の紹介と備忘録

SIGCOMM21で発表された「XLINK: QoE-Driven Multi-Path QUIC Transport in Large-scale Video Services」というMultipath QUIC を大規模な動画サービスに適用するための、設計、実装＋検証についての論文です。

著者のページで論文が公開されています。

www.hongqiangliu.com

論文へのリンク

また、以下のページでは、発表動画が視聴可能です。短くまとまっているので、動画発表を見ると理解しやすいかもしれないです。

https://dl.acm.org/doi/10.1145/3452296.3472893

論文では、マルチパスQUICをラージスケール（大規模な商用サービス）の動画サービスへの適用について書かれています。

従来提案されていたマルチパスQUICとは別のXLINKというマルチパスQUICを実装しています。

この実装では、QoEとコストの両立をゴールとしています。

XLINKでは、いくつかの動画フレームを含むストリームを構成するパケットを送り終えた時に、まだACKされていないパケットがあったら次のストリームを送る前に速いパスに再注入します。

また、最初の動画フレームの優先度を高くすることも可能です。これによって、最初の動画フレームを送り切ったときにまだACKされていない部分があったら再注入をします。

これらを無条件で適用すると冗長なトラフィックが発生する場合があります。不要な再注入は行わないためにクライアントから動画の残り時間に関するフィードバックを受け取ります。そしてクライアントにバッファされている動画の残り時間が短い場合に再注入を行います。

また、無線間の遅延を考慮して、以下の方法でパスの制御を行います。

  • プライマリパスを無線の種類で判断します。論文の例だと、5G SA > 5G NSA > Wi-Fi > LTE としています（国、地域で変わる可能性あり）。
  • どのパスから来たデータかによらず、ACKは最速のパスで返します。

以下は5章～7章の備忘録です。

5. QOE-DRIVEN SCHEDULING AND PATH MANAGEMENT

XLINKは以下の3つから構成されています。

  1. stream and video-frame priority-based
  2. packet re-injections, QoE feedback control
  3. QoE-aware path management.

5.1 Priority-based re-injection

Why re-injection?

f:id:neko--suki:20210909223950p:plain
Fig. 3

Fig. 3(a) では、どのようにマルチパスHoLブロッキングが起きるか説明しています。

pkt_send_q に含まれる1つのストリームを構成する7つのパケットのうち、1～4が速いパス、5～7が遅いパスで送信されたとします。 この場合、すべてのパケットがそろわないと動画チャンクとして扱うことができません。

もし、パケット6、7がロスしたとすると、遅いパスでロスリカバリーされるまでにRTO（retransmission timeout） と同じだけの時間がかかるため、その間処理がブロックされことになります。

再注入は、Fig. 3(b)に示すように、冗長な重複パケットを速いパスで送信します。

再注入するパケットを判断するために、送信側はACKされていないパケットのためのキューを用意します。

pkt_send_q に送信するパケットがなくなったら、送信側はACKされていない6と7のパケットを、遅いパスのロスリカバリーを待つことなしに速いパスに再注入します。これによって、受信側がブロックされなくなります。

Priority-based re-injection.

短い動画のトランスポートでは、動画プレイヤーは複数のストリームを同時にリクエストするかもしれません。それぞれのストリームが動画の一部のチャンクをダウンロードします。

f:id:neko--suki:20210909223021p:plain
Figure 4(a)

古典的な再注入は、ロスしたパケットをpkt_send_q の後ろに注入します。スケジューラーは遅いパスで送信したパケット4を、pkt_sendqの後ろ、つまりストリーム2の後ろに再注入します。

送信している動画はシーケンシャルなコンテンツのため、先に送信されているべきストリーム1のロスしたパケットがストリーム2の後で送信されることで、ストリーム2がストリーム1をブロックすることになります。

f:id:neko--suki:20210909223702p:plain
Fig. 4(b)

Fig. 4(b)のように、XLINKでは送信側はストリーム1の最後のパケットを送信したら、即座に同じ優先度のストリームで送信されたパケットのうちACKされていないものをunacked_qから見つけます。 もしACKされていないパケットがあれば、次に送信するストリームより先に再注入します。これによってストリームのブロッキングを回避します。

First-video-frame acceleration

XLINKはさらに、ビデオフレームの優先順位に基づいた再注入によって、短い動画の配信に重要な最初のビデオフレームの配信を加速します。

例えば、マルチパス間で大きな遅延がある場合、遅いパスによって動画フレームがブロックされることで再生が遅くなる可能性があります。

f:id:neko--suki:20210912174933p:plain
Fig. 4(c)

Fig. 4(c) のパケット3のように、良い状態のパスの輻輳制御ウィンドウが一杯だった時に、悪い状態のパスに割り当てられてしまうことがあります。

この場合は、再注入されるパケットは同じストリームの他の動画フレームを待たないといけません。

XLINKは、動画フレームの優先度ベースの再注入も行います。APIを提供し、アプリケーションが最初の動画フレームの優先度を高く設定できようにしています。

これを有効にすると、XLINKは最初のフレームのパケットをすべて送信した後に、最初のビデオフレームのACKされていないパケットをチェックします（この場合はpkt 3）。

もしそのようなパケットがあれば、スケジューラーは同じストリームの他のフレームの送信していないパケットよりも先にACKされていないパケットを再注入します。

再注入されたものパケットは速いパスで送信され、オリジナルのパケットより速く到達します。

動画フレームの優先度ベースの再注入によって、遅いパスでの大きな遅延を回避し、動画の開始を大幅に改善できます。

5.2 QoE feedback and re-injection control

パケット再注入の問題は、多くの冗長なパケットを発生させることです。論文の著者のケースでは、直接再注入するとトラフィックが15%増加しました。

XLINKでは、クライアントのQoEフィードバックを活用して、ユーザーが知覚するQoEを確保しながらパケット再注入によるコストオーバーヘッドを制御します。

もしバッファのoccupancy level が高いなら次のリバッファリングまでの時間が長いので、再注入の緊急性は低いと判断します。 バッファのoccupancy levelが低いなら、次に起こりうるリバッファリングまでの時間が短いので再注入の緊急性は高いと判断します。

クライアントのバッファのoccupancy-levelを知ることが、ユーザーが知覚するQoEの情報になります。XLINKはbuffer occupancyの情報を得て、サーバー側での再注入の制御のためにサーバーに送ります。

buffer occupancyの情報には以下の4つが含まれています。

  • キャッシュされているバイト数 (cached_bytes)
  • キャッシュされているフレーム数 (cached_frames)
  • ビットレート (bps)
  • フレームレート (fps)

f:id:neko--suki:20210911112859p:plain
Figure 16

これらのシグナルが、Fig. 16のACK_MPフレームのQoE Control Signal フィールドで伝えられます。

5.2.2 Double thresholding control.

制御アルゴリズムは以下のプロパティを満たす必要があります。

  • 緊急で再注入が必要になった場合でも十分な応答性をもつ
  • 不必要な再注入を的確に防ぐ
  • 性能とコストのバランスを調整できる柔軟性が必要

論文ではdouble thresholding control というアルゴリズムを提案しています。

アルゴリズムのステップ1

QoEフィードバックから、クライアントのバッファに残っている動画再生時間Δtを推定します。

Δt = cached_frames / fps か cached_bytes / bps を使います。

もし動画が一定のビットレートでエンコードされていなくてフレームレートが高い場合、bpsでは大きな変動がある可能性があるので、Δtはcached_frames / fps を使います。フレームレートがとても低い場合、計算はcached_bytes とbpsで計算します。

基本的に、ビットレートとフレームレートの両方を見るべきだと主張されています。

また、現実のフィードバックの頻度はクライアントの動画プレイヤーによって決まります。もし十分な頻度でQoEのフィードバックがこない場合は予測値などを使う必要があります。

アルゴリズムのステップ2

Δtを二つの閾値 T_{th1} 、 T_{th2} と比較します。

もし Δt < T_{th1} なら、クライアントにキャッシュされた動画プレイヤーが持つ残り時間がとても短いので、即座に再注入が必要と判断します。

もし T_{th2} < Δt なら、クライアントにキャッシュされた動画プレイヤーが持つ残り時間が十分に大きいので、コストを減らすために再注入は行わないと判断します。

この2つの閾値を組み合わせることで、性能とコストを両立させる柔軟性が提供できます。

アルゴリズムのステップ3

T_{th1} < Δt < T_{th2} なら、インフライト中のパケットの配信にかかる時間を再注入するかどうかの決定に使います。

Δt を インフライト中のパケットの推定の配信までにかかる時間 deliverTime_{max} と比較します。ここで deliverTime_{max} は以下のように求めます。

deliverTime_{max} = max_{𝑝 ∈P ∧ 𝑢𝑛𝑎𝑐𝑘𝑒𝑑_𝑞𝑝≠∅} {𝑅𝑇𝑇𝑝 + 𝛿𝑝 }

(補足: ACKされていないパケットがあるすべてのパスに対してRTT＋分散δを足したものから、最大値をとります）

もし Δt < deliverTime_{max} なら、一つのパスがとても遅いことになります。そこで他のパスに再注入することでパケットの配信を加速することができます。

もし Δt > deliverTime_{max} なら、インフライト中のパケットがΔtを使い切る前に到着すると判断し、再注入は行いません。

f:id:neko--suki:20210919001537p:plain
アルゴリズム

図にするとたぶんこんな感じなると思います。

例

アルゴリズムがどのように急速に変化する無線環境でHoLを克服するかの実例を確認します。

f:id:neko--suki:20210911121427p:plain
Fig. 6(a)

Fig. 6(a) は、実験に使う実データのパスの帯域の変動を表しています。Path1 は時間がたつと変動し、スループットが0になるタイミングもあります。

f:id:neko--suki:20210911121454p:plain
Fig. 6(b)

Fig. 6(b) はVanilla-MP （カスタムされていないマルチパスQUIC、従来提案されていた https://datatracker.ietf.org/doc/html/draft-deconinck-quic-multipath の実装）での結果を表しています。Path1の劣化に合わせて、マルチパスHoLブロッキングの影響でバッファレベルが低下していることが分かります。

f:id:neko--suki:20210911121520p:plain
Fig. 6(c)

Fig 6(c) は、再注入はしないがQoE による制御なしの場合の結果を表しています。バッファレベルは十分に保たれているものの、バッファレベルが高い時も再注入が行われて冗長なトラフィックが発生していることが分かります（4～6秒付近）。

f:id:neko--suki:20210911121532p:plain
Fig. 6(d)

Fig. 6(d) はQoEによる再注入の制御を行っています。この場合、バッファレベルが十分な場合には再注入が行われていないことが分かります。

Performance and cost tradeoffs.

より大きな T_{th1} は トラフィックオーバーヘッドの下限 C_{min} の増加させる代わりにテイルパフォーマンスを改善します。

一方で、 T_{th2}は、トラフィックオーバーヘッドの上限 C_{max} を制御します。

論文では、𝐶𝑚𝑖𝑛 >= 𝛽 ∗ 𝑃𝑟𝑜𝑏(Δ𝑡 < T_{𝑡ℎ1})、𝐶𝑚𝑎𝑥 <= 𝛽 ∗𝑃𝑟𝑜𝑏(Δ𝑡 < T_{th2} ) と記述しています。

βは、再注入をオンにした時のコストオーバーヘッドです。論文の動画アプリケーションの場合は15%と見積もっています。

Prob(Δt < T_{𝑡ℎ1}) は閾値よりバッファ時間が短い確率（＝再注入を行う確率）なので、そこにコストβをかけることでコストの下限が求められます。

同様に、𝑃𝑟𝑜𝑏(Δ𝑡 < T_{th2} ) は、再注入を行う可能性がある確率 (Δt < T_{𝑡ℎ1} とΔt < deliverTime_{max} で判断される両方）なので、そこにβをかけることでコストの上限を求めています。

f:id:neko--suki:20210912184649p:plain
Probの範囲

図で書くとこういう感じになると思います。

5.3 QoE-aware path management

複数の無線インターフェースはパス毎に遅延の値が変わります。ここではその値をどう使うかが述べられています。

Wireless-aware primary path selection.

例として、以下の優先順位でプライマリのパス選択を行っています。

5G SA > 5G NSA > Wi-Fi > LTE (この順番は、国や州などで変わる可能性がある）。

（LTEとコアネットワークを共有する5G NSAとは異なり、5G SAでは独立した新しいコアネットワークを採用しています。なので、5G SAは優先度が高い）

f:id:neko--suki:20210911123125p:plain
Fig. 7

Fig.7 では、いくつかのフレームサイズについて最初のフレームが到達するまでの時間を比較しています。計測は、5G SAテストベッドとエンタープライズWi-Fiで行っています。

この結果から見てわかるように、最初の動画フレームのプライマリパスの選択が、その配信時間に大きな影響を与えることが分かります。

Fastest-path Multi-path ACK.

MPTCPでは、ACKは送信したときと同じパスで返ってくると仮定していますが、XLINKではACK_MPをどのパスでも返せるようにしています。

f:id:neko--suki:20210911124049p:plain
Fig. 8

Fig. 8 では、RTTが最小の最速のパスでACK_MPを返す場合と、同一のパスでACKを返す場合を比較しています。

ここでは、エミュレータ上で、2つのパスに同じ帯域を設定し、速いパスと遅いパスのRTTの比を変更し4MBのファイルをロードした場合の時間を計測しています。

割合が大きくなるほど、最速のパスでACK_MPを返したほうが有利になっていくことが分かります。

その理由は、この実験にはCubicを使っているからです。CubicではACKが速いほど輻輳制御ウィンドウが速く増加し、その結果スループットが高くなります。

6 PROTOCOL AND IMPLEMENTATION

提案中の以下のドラフトをベースに実装されています。

datatracker.ietf.org

既存のQUICとの差分は、3つのフレームを追加するだけという点のみです。

以下の4つが設計のポイントになります。

(1) 異なるパスはCIDのシーケンス番号で識別されます。これによって、パケットロス検出とリカバリーが便利になります。それぞれのパスに対して異なるpacket number spaceを使います。

(2)ミドルボックスに防がれるリスクを阻止するために、QUICパケットヘッダーのフォーマットの変更は行いません。

(3) すべてのパスは一つの接続に属し、同じ暗号鍵を共有します。しかし、それぞれのパスが異なる AEADのnonceを得られる仕組みを取り込んでいます。

(4) PATH_STATUSとACK_MP拡張フレームによって、マルチパスの機能とQoEフィードバックメカニズムを実現します。

Multi-path initialization.

f:id:neko--suki:20210911230154p:plain
Fig. 9

まずは、通常のシングルパスと同様にQUICの接続を初期化します。この時に、クライアントは、enable_multipath トランスポートパラメータを送ります。サーバーがenable_multipath トランスポートパラメータで応答してくれば、サーバーがマルチパスをサポートしていることが分かります。もし対応していない場合はシングルパスにフォールバックします。

ここまでが、Fig. 9のPrimary Path Initialization で行われています。

マルチパス接続を確立するときに、クライアントはNEW_CONNECTION_IDフレームを使って新しいCIDをサーバーに渡します。そしてサーバーもNEW_CONNECTION_IDフレームを使って、少なくとも一つの未使用のクライアントに渡します。

path spoofingを回避するために、PATH_CHALLENGEとPACH_RESPONSE による Path Validation を行います。

パスが初期化されたら、ACKフレームの代わりにACK_MPフレームを使用します。

Frame extension.

PATH_STATUSフレームと、ACK_MPフレームを、マルチパスの機能とQoEフィードバックのために利用します。

PATH_STATUSフレームは、Abandon(0)、Standby(1)、Available(2) の3つをとります。

f:id:neko--suki:20210911233857p:plain
Fig. 16

ACK_MPフレームでは、パスインデックスフィールド（CIDシーケンス番号）を組み込むことで、各パスでのロスの検出とリカバリーを行います。

この論文での実装では、QoE_Cnotrol_Signalフィールドを取り込むことでクライアントとサーバー間のQoEフィードバックをサポートしています。一方でIETF に提案しているドラフトでは、QOE_CONTROL_SIGNAL を使用しています。これによって、ACKの頻度に影響されることなく独立にQoEフィードバックを送信できます。

Path Close

PATH_STATUS をAbandon にして送ります。

Packet Protection

(あまり詳しくないので自信ないです）

基本的な使い方は変わりませんが、パス毎にPacket Numberが異なるのでAEADのnonceの求め方が変わります。

nonceは、32ビットのConnection ID、2つの0のビット、62ビットのQUICのパケット番号から構成されます。

AEADの求め方は以下のサイトが分かりやすいと思います。

tex2e.github.io

Work with Load Balancers.

QUIC-LB の実装と一緒に動くことが可能です。

datatracker.ietf.org

Integration with android apps.

XLINKのクライアント（Cで書かれている）は、XQUICに実装されています（AlibabaのIETFのQUIC実装）。 そして、Taobaoというアンドロイドアプリに取り込まれています。

XLINKは、動画プレイヤーなどのアプリケーションに、キャッシュバイト、キャッシュされたフレーム、現在のビットレート、フレームレートなどの情報をQUICに渡すためのAPIを提供しています。

Deployment in CDN servers.

XLINKサーバーもCで書かれており、CDNのマルチプロセスアーキテクチャのサーバーにデプロイされています。

受信したパケットをQUICコネクションのコンテキストを持つ正しいプロセスに届けるために、CIDの予約バイトにエンコードされているプロセスIDにConsistent Hashing を使用している。

7 EVALUATION

リアルなユーザーの評価と、制御されたエミュレーション環境での評価を行っています。

Online evaluation:

Taobao アンドロイドアプリを使ったリアルなユーザーデータで評価しています。

クライアントの動画プレイヤーのバッファレベルの分布の変化と、いくつかの閾値に対する冗長なトラフィックコストの状況を見ています。

また、100Kの参加者による300万の動画再生のデータをもとにしたA/Bテスト(シングルパス vs XLINK) を14日間行い日毎の結果を比較しています。

Controlled evaluation:

再現性のある制御された環境化で、異なる手法を比較しています。

過酷なモビリティの環境で集めたネットワークのトレース上で、XLINKと他のマルチパスソリューションの性能を比較しています。

また、色々なサイズの動画をダウンロードした時の電力消費の比較も行っています。

輻輳制御はcubicを使っています。また、Vanilla-MP、MPTCP、XLINKはパス毎に輻輳制御を行っています。

7.1 Buffer-level and cost overhead vs. double thresholds.

QoEを制御するアルゴリズムの2つの閾値の選択について検討しています。

まず制御をオフにして、QoEフィードバックから動画の残り時間の分布を計測します。それから、(th(X), th(Y)) を選択します。

th(X)は X番目のパーセンタイル値をとっています。Xが90%なら、90％のデータで動画の残り時間がth(X) より多くなります。Xが大きいほど th(X)の値は小さくなります。

f:id:neko--suki:20210912121557p:plain
Fig. 10

Fig. 10はシングルパスに対する選んだ閾値でのクライアントのバッファレベルの改善をプロットしています。

ここから以下のことが言えます。

  • 再注入をオフにするとバッファレベルが大幅に低下するから再注入は必要です
  • QoE 制御を行わないと( (1,1)の時は T_{th1} の値が非常に大きくなるので、すべての場合で再注入が行われる）トラフィックコストは15%に達するため、QoE制御は必要です
  • オーバーヘッドコストの下限値は、β (1-X)で上限はβ(1-Y) 、ベータはおよそ15%←5.2.2 で予想した通り
  • (95, 80) のように、適切な閾値だと、小さいコストでよい性能を達成します。さらに閾値をあげた場合効果が薄れます。
  • (90, 80)と(90,60)、(60,50)と(60, 1)のように上限値が大きい場合にコストが大きくなっていません。これは配信時間を比較するロジックが有効だったことを意味します。

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

Table 2 では、キャッシュされている動画の残り時間が50ms以下のサンプルの減少率を載せています。ここから閾値として95を採用することが十分であることがわかります。

最もコスト効率が良い組み合わせは、(95, 80)で、コストのオーバーヘッドは2.1%でリバッファリングの確率を66%改善しています。

7.2 Large-scale A/B test

f:id:neko--suki:20210912123349p:plain
Fig. 11

Fig. 11は、2週間実施した動画のリクエスト完了時間のA/Bテストの結果です。Fig.11 では、メディアン、95%値、99%値の動画チャンクのリクエスト完了時間 (Request Completion Time RCT) が表されています。

XLINKは、メディアンと99%値で一貫してシングルパスの場合を上回っています。

メディアン、95th, 99thでそれぞれ2.3% ～ 8.9%、9.4% ～ 34%、19% ～ 50% の改善を観測しています。

ただし、14日目のメディアンのみ0.7%低下しています。

QoE metric #1: video rebuffer rate.

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

Table 3 は7日間の計測からクライアント側でのビデオリバッファレートの減少を載せています。ビデオリバッファレートは、リバッファの合計時間 / 動画の合計時間 で求められます。

これらから動画再生がスムーズになるよう改善され、ユーザーのQoEを向上させる効果があることが分かります。

QoE metric # 2: first-video-frame latency.

f:id:neko--suki:20210912124253p:plain
Fig. 12

Fig. 12ではFirst-video-frame accelerationをありにした場合と、なしにした場合の比較を行っています。シングルパスと比較したときの改善を表しています。

First-video-frame acceleration無しでは、動画のレイテンシーはシングルパスより悪くなります。99%値では14%遅くなっています。

逆に速いパスを選択した場合は32%改善しています。

7.3 Extreme mobility

過酷なモバイル環境を再現するために、LTEとWi-Fiのトレースを、地下鉄や高速鉄道で集めて、Mahimahiでトレースベースの評価を行っています。

f:id:neko--suki:20210912124837p:plain
Fig13

Fig. 13では、10個のトレースデータ上で、シングルパス、Vanilla-MP、MPTCP、QUIC Connection Migration とXLINKを比較しています。

ビデオチャンクのリクエスト完了時間のメディアン値と最大値がプロットされています。

ここから以下のことが観察できます

(1) Connection Migration無しのシングルパスは、すべてのトレースで性能が出ません。

(2) Connection MigrationはSPに比べて古いパスが劣化し時に新しいパスにマイグレーションするために改善します。しかし、過酷な環境では新しいパスも同様に即座に劣化するので、いくつかの場合ではSPよりも悪い結果になります。更に、Connection Migrationではcwndがリセットされるので輻輳制御がスロースタートになります。また、パスの劣化を検出するのはクライアントの責務なのでいくつかのラウンドトリップが必要になります。結果として、Connection Migrationは頻度が高いハンドオフに対しての応答性が十分ではなくなります。

(3) MPTCPとVanilla-MP はSPに対していくつかのケースでは改善を見せていますが、高速なリンク変動時に深刻なHoLブロッキングが発生し多くのケースで性能低下を招いています。

これらの結果とは対照的に、XLINKは一貫して他の手法よりもメディアンと最大値が小さくなります。XLINKは、高速に変化するリンクへのパケット配分を迅速に対応させることで、高速なリンクの変化や頻繁なハンドオフを克服できます。

7.4 Energy consumption

f:id:neko--suki:20210912125427p:plain
Fig. 14

以下の結果が観察できます。