xlink解读

XLINK: QoE-Driven Multi-Path QUIC Transport in Large-scale Video Services

Introduction

2 observation:

• 短视频的卡顿和初始延迟严重影响用户体验
• 用户想要观看更细节更逼真的视频，带来高质量高码率的需求

multi-path: Wi-Fi, LTE, 5G ...

目前的多路径传输研究：MPTCP in RFC 6824 (OS-level support),

multi-path QUIC (user-space protocol)，目前更多针对于web and bulk data transfer，还没有针对video的设计。直接应用到video的话性能反而降低。

原因：multi-path head-of-line (MP-HoL) blocking issue caused by fast varying and heterogeneous paths. 传输会被slow path拖累，导致fast path的包要等待。

solution: sophisticated packet scheduling algorithms (路径调度、包优先级调度)、transmit duplicate packets to decouple multipaths (发送冗余包，但这会带宽超过15%的网络流量)。

本文工作：

• 通过客户端QoE的反馈来控制packet re-injection’s aggressiveness策略（比如某个包重新注入另一条快路径传输）。
• XLINK carefully determines the sending order based on the urgency of the streams. 决定包(parket)的传输队列次序，比如着急的重传包优先发送。 包：正常包和重传包
• video-frame priority-based re-injection，视频帧的发送顺序。这里更多指首帧应该优先发送，降低初始卡顿。 帧：正常帧和首帧
• wireless-aware primary path selection (Primary path is the path used to start a connection.) 。不同于MPTCP每次以同一路径传输ACK包，XLINK可以灵活地选择multi-path ACKs (ACK_MPs)的传输路径。

结果：

在淘宝app上超过100K的用户进行A/B测试，进行超过3-million次的视频播放，跟单路径QUIC对比。超过99%样例视频请求时间降低19-50%；...99%...首帧延时降低32%；在只增加2.1%带宽流量的前提下，卡顿率降低23-67%。

作者强调：利用上层的QoE来指导底层传输层的控制策略 (cross-layer network designs)，达到pioneers innovations on a closer collaboration between video and wireless。

EXPERIENCE WITH VANILLA MULTI-PATH QUIC

对比：传统的多路径 vanilla-MP (MPQUIC) [1], single-path QUIC (SP)

1. Wi-Fi的带宽变化很大，使得CWND无法及时反映链路状况，造成slow path拥堵；
2. 不同路径的delay：The median path delay of LTE was 2.7 times and 5.5 times that of Wi-Fi and 5G SA, respectively.
3. The rebuffer rate of vanilla-MP was worse than that of SP. 传统多路径算法的表现反而更差。

XLINK DESIGN OVERVIEW

XLINK的整体架构如图1所示， 具有以下几个特点：

1. 用户态部署：XLINK工作在用户态，集成在App当中并在UDP之上实现了数据的可靠传输与拥塞控制。它伴随应用快速部署与迭代，即插即用。XLINK的手机端的应用可以做到以周为单位更新，XLINK服务端的应用和算法更新可做到天或小时为粒度。由于XLINK实现在用户态协议栈中，与app集成在一起，因此XLINK可以直接针对不同的应用做定制化优化。

2. 高性能：XLINK利用视频应用的QoE反馈作为调度器的控制信号，QoE信号可以包含多种与用户体验相关的参数，通过这个QoE反馈控制调度器， XLINK成功克服了MP-HoL所带来的性能和成本问题， 使多路径技术在大规模视频应用中的使用变得可行。XLINK进行多路径调度时， 并不需要对于路径的带宽和时延作精确的估计， 而是采取了数据包重注入(Reinjection)的自适应补偿方法， 让数据包自适应的在多条路径上实现均衡。此外， XLINK通过对于用户QoE的理解，可以进一步优化用户体验。比如，XLINK可以针对短视频的首帧进行特殊优化，降低用户的首帧下载时间，从而提升用户的秒开率。

3. 低成本：XLINK的调度算法不仅可以克服MP-HoL所带来的性能问题， 而且几乎不增加额外的数据量，QoE的反馈帮助XLINK调节重注入的力度， 达到最优的性能与成本之间的平衡， 所以码率很高的视频应用也可以放心的大规模使用多路径传输而不用担心其流量成本问题。

4. 轻量化：XLINK完全基于C语言开发（在XQUIC用户态协议栈中实现），XQUIC总体的包大小只有300+KB，非常适合各种移动终端的使用。

在客户端捕获QoE信号（缓存帧数和帧率），然后利用ACK_MP extension frame返回给服务器。

XLINK implements priority-based re-injection at two levels: transport (QUIC stream) level and application (video frame) level.

包：重传包的优先级>普通包；帧：首帧处于最高优先级。

本文实现基于[2]（该团队之前的另一篇文章）。

QOE-DRIVEN SCHEDULING AND PATH MANAGEMENT

本章要做的事：stream and video-frame priority-based packet re-injections, QoE feedback control, and QoE-aware path management.

re-injection例子

如图(a)，服务端通过两条路径发送packets。这时slow-path出现丢包，就会发生HoL (head-of-line)，导致整体性能下降。如果没有要发送的数据了，可以把未确认的6、7通过fast-path传输，decouple两条传输路径。

Priority-based re-injection.

在QUIC中，同一个connection可能对应多条stream（比如对应多个chunk）。当一条stream有未确认包时，可以优先送到另一条stream传输。 

如图(a)和(b)，当发送完stream1的所有包后，发现stream1的包4丢了，可以优先re-injdect到stream2进行传输。

这里path和stream的关系好像没有讲的很清楚，按我的理解，stream是比path更上层的传输队列，path是实际传输的链路。比如stream属于银行门口的两条队列，path属于快慢两个业务员。如果某个队列的人如果跟了慢业务员且迟迟未被确认，那么它的一个副本可以去另一个队列的前面排队等待被传输。

First-video-frame acceleration.

这里指首帧的包拥有最大的优先级，所以可以优先传输，降低首帧延时。如(c)的包3。

以上都属于逻辑设计方面的。

QoE feedback and re-injection control

本节提出一个决定是否进行re-injection的算法。当用户的buffer occupancy比较大时，不必进行重传。当较小时，则需要re-injection到fast path，避免引起卡顿。

这里的QoE signals包括：(1) the number of cached bytes (cached_bytes) (2) the number cached of frames (cached_frames) (3) the bitrate (bps), and (4) the framerate (fps). 

以上就是客户端的pipeline。TNET是淘宝的Android network SDK，收集QoE信息。XLINK周期性地请求QoE信息，然后封装在ACK_MP的QoE Control Signal字段发送给服务器。

作者设计了一个启发式算法判断是否要开启re-injection。 

首先，作者从source pipe和decoder统计两个缓存的时长。作者推荐当码率不均匀或帧率高时，使用cached_frames和fps。当帧率较低时，采用cached_frames和bps。

然后作者设计两个阈值。当缓存时长较大时，则不用re-injection，反之则要。

接着，作者计算各条path的in-flight (unack)的packet的传输时间$RTT_p+\delta_p$，$\delta$为误差参数。取值最大的传输时间，最后与$\Delta_t$比较决定是否需要重注入。

这里阈值的设置作者并没有详细地讨论，只说推荐依据客户端的缓存分布设置。

wireless-aware primary path selection To accommodate the upcoming 5G SA, we make XLINK’s primary path selection wireless-aware. For example,we can set the following order: 5G SA > 5G NSA > WiFi > LTE.

Fastest-path Multi-path ACK XLINK utilizes fastest-path Multi-path ACK.

PROTOCOL AND IMPLEMENTATION

Key design points:

• 不同路径被不同的sequence number of connection IDs (CIDs)标识。同时每条路径有separate packet number space。
• 保持QUIC的packet header formats不变。
• 所有同个连接的路径共享encryption key，同时每条路径有自己的a unique nonce in AEAD。
• 加入PATH_STATUS and ACK_MP extension frames。

建立连接 

每次建立连接，双方都要提供一个unused available CID。

We use the PATH_STATUS frame and ACK_MP frame to support multi-path functionality and QoE feedback.

The PATH_STATUS frame is used to help manage multi-paths, which informs the peer of the current status of a path, and the peer should send packets according to the preference expressed in these frames. Available values of PATH_STATUS are Abandon(0), Standby(1), and Available(2).

The ACK_MP frame allows for convenient loss detection and recovery on each path by incorporating a path index field (CID sequence number). In our experiments, it also supports QoE feedback between a client and a server by incorporating the QoE_Control_Signal field.

Path close. Both client and server can close a path, by sending PATH_STATUS frame which abandons the path with a corresponding Path Identifier.

Evaluation

评估主要从下载时间、卡顿、首帧时间展开。 

Q： 1. 图5的cached_bytes应该是解码前的bytes还是解码后的。为什么缓存时间的计算方式跟帧率有关。

这篇文章解决的问题还是比较受关注的，但算法部分相对比较简单，网络领域公司还是比较有优势呀~

[1] Quentin De Coninck and Olivier Bonaventure. Multipath quic: Design and evaluation. In Proceedings of the 13th international conference on emerging networking experiments and technologies, pages 160–166, 2017.

esign and evaluation. In Proceedings of the 13th international conference on emerging networking experiments and technologies, pages 160–166, 2017.

[2] Yanmei Liu, Yunfei Ma, Christian Huitema, Qing An, and Zhenyu Li. Multipath Extension for QUIC. Internet-Draft draft-liu-multipath-quic-02, Internet Engineering Task Force, December 2020. Work in Progress.