面向大规模实时视频流的Overlay路由决策算法

实时通信（Real-Time Communication, RTC）是一类为用户提供实时的音视频通信服务的互联网应用，包括视频会议、网络电话、互动直播、云游戏、远程控制等形式，应用场景涵盖办公、社交、娱乐等多个重要领域。实时性交互是RTC应用的核心特点，强调从发送者到接受者的端到端低时延。过高的时延会导致通信双方无法顺畅交互，严重损害用户的体验质量。因此，RTC应用对传输网络的服务质量（Quality of Service, QoS）提出了较高的需求。依据国际电信联盟对网络传输时延的建议，RTC应用的基本交互体验要求传输网络的端到端单向时延低于400ms，理想交互体验则要求端到端单向时延低于200ms [1]。

然而，公共互联网的设计哲学里将连通性和可扩展性置于比服务质量更高的优先级，导致互联网尽力而为（best-effort）的传输服务难以满足RTC应用的实时交互需求。例如，针对网络电话应用Skype的性能测量研究表明：在互联网通话中，端到端时延无法满足实时交互需求的通话占比超过15%；对于跨国的互联网通话，这一比例超过40% [2]。

为缓解互联网在服务质量上的局限性，实时传输网络（Real-Time Network, RTN）应运而生，成为实际支持RTC应用传输需求的关键基础设施。RTN是构建在公共互联网和私有骨干网之上的覆盖（Overlay）网络。Overlay网络是在底层（Underlay）网络上构建的逻辑网络，其能够在Overlay节点之间实现灵活的路由控制，因此能够绕避Underlay网络中的性能瓶颈以提升传输性能 [3-4]。如图1所示，RTN基于大规模部署的存在节点（Point of Presence, PoP）就近接入用户，并根据网络条件和传输目标实时计算动态Overlay路由，从而为RTC应用提供高服务质量且低带宽成本的实时传输服务。随着RTC业务的蓬勃发展，RTN作为其中的关键基础设施，其市场规模持续扩大并受到学术界的广泛关注。截至2023年，RTN的全球市场规模达到81亿美元且保持25.9%的增速 [5]，不仅涌现出Agora、Twilo、融云等专业RTN提供商，阿里巴巴等互联网服务提供商也积极部署RTN以支持实时通信业务 [6]。

RTN中的Overlay路由决策问题

作为一类广泛流行的RTC应用，视频直播（live video）是RTN中重要的传输对象 [6]。相较于文件下载等应用中的完整传输方式，视频直播采用流式传输，因此也被称为实时视频流（live streaming）。实时视频流对RTN的传输提出了三方面需求：

1. 一对多传输。由于同一直播频道内的不同观众可能被映射到不同的PoP上，每个实时视频流的传输目的PoP可能存在多个。

2. 低时延且高带宽。由于直播者和观众交互需求的增加，实时视频流要求低时延传输以提供流畅的交互体验。另外，由于视频质量的提升，实时视频流对传输的带宽也提出了更高的需求。

3. 大规模传输。由于视频直播应用的流行，RTN需要支持大规模实时视频流的并行传输。并且，RTN可能需要同时服务多家直播平台，进一步增加了对传输规模的需求。

针对这样的需求，我们将RTN中的Overlay路由决策问题建模为一个时延与带宽开销联合优化的Overlay多播树决策问题（ORLVD），如图2所示。在优化问题中，优化目标为最小化传输时延与传输带宽开销的加权和，约束条件包括网络带宽限制和流量守恒限制。基于ORLVD问题，RTN能够通过控制目标权重指定传输预算，并求解出在指定预算下具有最低总传输时延的Overlay路由。

基于分布式优化的Overlay路由决策算法

尽管ORLVD问题能够提供低时延、低带宽开销的Overlay多播树决策，但其NP难度导致现有的集中式优化算法难以应用。具体来说，面向大规模的实时视频流，集中式优化算法需要较长的求解时间计算最优解，从而导致Overlay路由决策难以快速响应传输需求的变化。因此，我们提出基于分布式优化的Overlay路由决策算法，使用各个PoP的计算资源并行优化求解以提升路由决策效率。该算法由两部分组成，分别为源PoP感知的问题分解策略和基于资源切分的分布式优化算法。

（1）源PoP感知的问题分解策略

为进行分布式优化，首先需要将大规模的全局问题分解为多个小规模的子问题，然后通过分别求解各个子问题获得全局问题的解。在ORLVD问题中，由于优化目标式为变量向量中各个元素的函数之和，可以将决策变量分解为多个子决策变量以实现对原问题的分解，然后对各个子问题进行分布式优化，再将其优化结果组合即可得到原问题的解。

显然，分解的结果会显著影响分布式优化的性能，因此需要仔细设计问题分解策略。一方面，不均匀的分解会导致各个子问题具有不同的复杂性，从而导致针对复杂子问题的分布式优化过程成为性能瓶颈，最终影响整体求解速度。另一方面，不合适的分解可能导致子问题间具有强耦合性，从而增加分布式优化的难度。在ORLVD问题中，决策变量之间存在着带宽耦合和流耦合两种正交的耦合关系：带宽耦合是指网络带宽限制让属于不同视频流的决策变量间存在跨视频流的耦合关系，而流耦合是指流量守恒限制让属于同一视频流的决策变量间存在跨Overlay链路的耦合关系。

因此，我们设计了源PoP感知的问题分解策略。该策略以视频流作为分解决策变量的最小粒度，即控制同一视频流的决策变量不会被分解到不同的子问题中。在视频流粒度上，我们根据源PoP对决策变量聚类以实现问题分解，即具有相同源PoP的视频流属于同一聚类。

这一分解策略能够有效缓解上述两个挑战。一方面，根据源PoP进行变量分解的分解方式能够实现负载均衡。由于PoP负载是Overlay网络在请求映射时的重要指标，被映射到各个PoP上的视频流数量基本保持均衡，因此该策略分解后的各个子问题具有相近的规模。另一方面，视频流粒度的分解避免了子问题间存在流耦合，同时源PoP感知的分解方式使所有视频流的路由都可以直接由其源PoP完成决策，减少了在分布式优化中所需的PoP间信息交换。

(2) 基于资源切分的分布式优化算法

在问题分解后，各个子问题间仍然存在带宽耦合。因此，无法直接通过独立优化各个子问题实现对原问题的优化，需要设计分布式优化算法处理耦合关系，即通过该算法对各个PoP的子问题优化进行协调，从而让子问题优化结果的组合即为原问题的最优解。

我们设计了基于资源切分（Resource Splitting，RS）的分布式优化算法，即通过资源切分消除子问题之间的带宽耦合，让解耦后的子问题可以独立地优化求解。资源切分是一种用于求解资源分配问题的算法 [8]，指的是预先将可分配的资源进行划分并分配给各个子问题，然后各个子问题再在预分配的资源之上进行独立的优化求解以进一步完成资源分配。在我们的Overlay路由决策问题中，需要将Overlay链路的带宽资源分配给多条流，对带宽资源的切分有两种可能的方式。第一种是链路维度，即将Overlay链路进行切分。第二种是带宽维度，即将每条Overlay链路的带宽资源进行切分。由于链路维度的资源切分会显著影响各个子问题中Overlay路由的决策空间，为尽可能地降低资源切分对决策最优性的影响，我们使用带宽维度的资源切分。因此，我们的分布式算法首先将每条Overlay链路的带宽资源切分为N份并分配给对应的N个子问题（N为PoP数量），然后各个子问题基于切分后的带宽资源进行优化求解，如图3所示。

基于分布式优化的Overlay路由决策流程如图4所示，图中红、蓝两色箭头分别表示两个实时视频流的Overlay多播树决策结果。在直播的过程中，可能出现直播频道的新增或结束以及观众加入或退出某一频道的场景，导致各个PoP的传输请求发生变化而需要重新计算Overlay路由。若使用集中式优化进行Overlay路由决策，新传输需求的最优Overlay路由需要等待周期性的集中式优化求解，且周期通常较长。基于我们提出的问题分解策略和资源切分算法，各个PoP可以在观测到传输请求发生变化后立刻进行独立的分布式优化以实现快速Overlay路由决策。并且，由于决策的视频流都以该PoP为源，可以基于源路由进行转发以保证决策的准确执行。

实验评估

我们以Facebook Live的测量数据集 [9]作为trace，基于Fastly CDN的PoP地理位置模拟Overlay网络，对Overlay路由决策算法的决策速度和决策质量进行了评估。实验结果表明，通过利用分布式优化，我们的Overlay路由决策算法具有更优的可扩展性。

我们分别以1k至40k规模的实时视频流传输需求作为实验负载，以ORLVD问题作为Overlay路由决策问题，Overlay路由决策算法包括传统的集中式优化算法、最新研究的（SOTA）集中式优化算法 [8]、分布式优化算法、启发式算法、直接路径传输。其中，启发式算法为最短路径树（SPT）算法；分布优化方案包括两类，均基于本文提出的源PoP感知的问题分解策略进行原问题的分解，但使用的分布式优化算法分别为本文提出的基于资源切分（RS）的分布式优化算法和现有的分布式优化算法ADMM；直接路径传输指使用源PoP和目的PoP间的Overlay链路作为决策结果。实验中所用的优化求解器为Gurobi。

图5和6分别展示了不同Overlay路由决策算法的决策所需时长和决策质量。由于不同决策算法的决策时间具有明显的差别，决策所需时长使用对数尺度绘制。决策质量指Overlay路由决策问题中由传输时延和传输带宽开销共同构成的优化目标，因此数值越低代表决策质量越高。我们将决策质量进行归一化处理，即以集中式优化算法的结果作为最优决策，将所有决策算法的决策质量数值除以最优决策的决策质量数值。

对比最新研究的集中式优化算法，我们提出的Overlay路由决策算法将决策所需时间降低38%至89%，且决策质量的损失在4%以内。并且，对比传统的分布式优化算法ADMM，我们提出的分布式优化算法实现的决策质量接近，但将决策时延降低54%至77%，这是由于ADMM需要多轮迭代优化，且每一轮中各个子问题的优化无法并行，而我们提出的分布式优化算法通过资源切分能够独立且并行地求解。

总结与展望

针对RTN的传输需求，我们将Overlay路由决策问题建模为时延与带宽开销联合优化的Overlay多播树决策问题，并设计了基于分布式优化的Overlay路由决策算法以增强可扩展性。我们的工作让RTN在面对大规模实时视频流时也能快速进行高质量的Overlay路由决策，从而提升传输性能并降低传输开销。

参考文献

[1] ITU-T. Recommendation g. 114: one-way transmission time[S/OL]. Series G: Transmission Systems and Media, Digital Systems and Networks, 2003.

https://www.itu.int/rec/T-REC-G.114-200305-I/en.

[2] Jiang J, Das R, Ananthanarayanan G, et al. Via: Improving internet telephony call quality using predictive relay selection[C/OL]//SIGCOMM ’16: Proceedings of the 2016 ACM SIGCOMM Conference. New York, NY, USA: Association for Computing Machinery, 2016: 286–299.

https://doi.org/10.1145/2934872.2934907.

[3] Andersen D, Balakrishnan H, Kaashoek F, et al. Resilient overlay networks[C/OL]//SOSP ’01: Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles. New York, NY, USA: Association for Computing Machinery, 2001: 131–145.

https://doi.org/10.1145/502034.502048.

[4] Nygren E, Sitaraman R K, Sun J. The akamai network: A platform for high-performance internet applications[J/OL]. SIGOPS Oper. Syst. Rev., 2010, 44(3): 2–19.

https://doi.org/10.1145/1842733.1842736.

[5]艾瑞咨询. 2023 年全球互联网通信云行业研究报告[EB/OL]. 2023.

https://report.iresearch.cn/report/202303/4144.shtml.

[6] Li J, Li Z, Lu R, et al. Livenet: A low-latency video transport network for large-scale live streaming[C/OL]//SIGCOMM ’22: Proceedings of the ACM SIGCOMM 2022 Conference. New York, NY, USA: Association for Computing Machinery, 2022: 812–825.

https://doi.org/10.1145/3544216.3544236.

[7] Li R, Wang H, Xu C, et al. Distributed Routing Controller for Large-scale Live Video Streams in Real-Time Networks [C]//GLOBECOM ’22: IEEE Global Communications Conference, 2022.

[8] Narayanan D, Kazhamiaka F, Abuzaid F, et al. Solving large-scale granular resource allocation problems efficiently with pop[C/OL]//SOSP ’21: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. New York, NY, USA: Association for Computing Machinery, 2021: 521–537.

https://doi.org/10.1145/3477132.3483588.

[9] Baccour E, Erbad A, Bilal K, et al. Facebookvideolive18: A live video streaming dataset for streams metadata and online viewers locations[C/OL]//2020 IEEE International Conference on Informatics, IoT, and Enabling Technologies (ICIoT). 2020: 476-483. DOI:10.1109/ICIoT48696.2020.9089607.