算法系列：大规模视频直播中的关键算法

本文为媒矿工厂翻译的技术文章

原标题：The Algorithm Series: Live Event Scaling

原作者：Tim Siglin

原文链接：https://www.streamingmedia.com/Articles/Editorial/Featured-Articles/The-Algorithm-Series-Live-Event-Scaling-143705.aspx

翻译整理：卢冰聪

伴随着2020年大部分的体育赛事、音乐会、节日活动和其他聚集性活动的停滞，面向2021年我们会发现对支持大型活动的流媒体传输的潜在需求是巨大的。业界各公司将怎样分发实时流事件来满足这些潜在的史无前例的需求呢？最近发布在 Algorithm Series的文章深入研究了调整大规模实时视频事件交付的数学和工作流决策算法。

01

PART

单播分发

许多直播流解决方案聚焦于单播，单播分发在视频流服务器和用户流媒体播放器终端（即网络中的客户端）之间有一个单独的链接。

HTTP流将一个流分解成了一系列的片段(segment)或块(chunk)，代价是直播流引入了额外的15~30s延迟。然而在HTTP流分发出现之前，大部分单播分发建立在RTP和相关衍生协议（如Adobe的RTMP）的基础上。基于RTP的实时流的一大优点是他们可以以非常低的延时被传输，缺点就是可扩展性差。对每个需要收到一个直播流的用户终端来说，一个服务器必须建立一个直接的分发链接（被称作state）才能进行交付。这意味着将要耗费非常昂贵的服务器的成本和需要大容量带宽，而以上条件通常只能在主要的互联网对等交汇点数据中心里才能满足。

02

PART

P2P分发

1990s末和2000s初的研究聚焦于通过HTTP分发或对等辅助(peer-assisted)分发来扩展单播直播流。

P2P（Peer to peer）使用客户端之间的链接，这些链接要么和服务器是协调合作的，要么完全独立于服务器。但是一旦初始化的内容被发送至几个客户端对，这些链接只需要非常少的服务器。有趣的是，独立于服务器的P2P方法本身并非源于流式传输，而是紧密的联系于被用于协调高级的可下载的媒体内容的未授权文件共享的分散式P2P BitTorrent 服务器。

然而随之而来的对文件分享网站的打击，使得P2P的受欢迎程度有所下降。但这种peer-assisted交付的效率和成本有效性（需要的服务器比较少，中央数据中心对带宽吞吐量的需求也有限）引起了专研视频的网络架构师的关注。

但是P2P没有解决可扩展规模的全部问题。一个原因不是所有的peer都被平等建立，这是由不同的网络拓扑结构引起的。在一篇2014年被发表在Wiley's International Journal ofCommunication Systems的论文《Using Topology Information forQuality-Aware Peer-to-Peer Multilayer Video Streaming》中，Ghent大学信息技术学院的一个研究团队探究了优化网络拓扑来改善流媒体质量的问题。以下是引言的节选：“本文介绍了通过P2P框架传输视频（多层）的一个模型，该模型包含了网络信息。视频流服务商的一个重要指标是终端用户感知到的内容质量。这里的优化研究聚焦于最大化能收到高质量视频的用户数。”

这篇文章从流媒体服务商的角度研究了该优化问题，其中流媒体服务商可以方便的获取网络拓扑信息。为了进行基础测试比较，提出了一种精确地优化方法。同时提出了一种使用实际网络规模的启发式算法。

鉴于该文章关注的是服务提高商比如CDNs和ISPs，作者做出了一个假设：服务提供商会在“网络中精心选择的位置”安装这些对等节点，并且这些对等节点之间有充足的网络容量来实现互联，以达到最佳的实时流媒体传输性能。

在这种方法中，peer的选择对于保持流媒体内容高质量吞吐是至关重要的，但是作者也建议四种节点类型是必要的

• 注入节点(injectors)，帮助最初的视频流进入网络；
• 追踪节点(tracking node)，当peers开始下载进程时协调这些peers；
• 对等节点(peering node)，接收内容并将其传播到其他peers和目的地（用户终端）；
• 转发节点(forwarding node)，是服务提供商网络的关键拓扑结构的一部分。

早期的peer-assisted 分发方式的一个问题是，当高带宽peer可用时节点会有贪婪问题。这种方法允许一些幸运的对等点更快地下载内容，但是这意味着其他对等点必须寻找带宽较低的peers。尽管非法共享优质文件（包括戏剧电影和高级的桌面应用程序）似乎不是什么大不了的事，但是实时流媒体传输中出现这种贪婪问题就潜在意味着并非所有的peers都可以收到同等的高质量视频流。

瑞典KTH皇家理工学院的研究人员在论文《Server Guaranteed Cap: AnIncentive Mechanism for Maximizing Streaming Quality in Heterogeneous Overlays》中简略的陈述了贪婪问题，他们指出贪婪问题是由于P2P网络没有考虑网络拓扑结构，因此它的效率达不到他们本来该有的水平。这篇论文是Ghent大学几年前写的，在提及peers数据分享时使用了"selfish"而不是"greedy"这样的形容词。然而他们给出了一个更深层的结论：“我们的结果显示出，peers的自私行为导致在social welfare社会福利方面产生一个次优状态的均衡，因为自私的peers对于成群聚集和在这些群体之中交换数据更感兴趣”。

Social welfare概念是希望所有的peers节点的行为都有利于其他所有的peers节点，这在peers跨越几种不同的网络，包括无线、 Wi-Fi或者甚至是移动蜂窝网络时是很困难的。这需要通过例如服务器容量之类的激励措施来确保peers在高贡献度和低贡献度peers之间平等地共享数据。

他们的算法对于衡量peers之间的累计效用(aggregate utility)是相当简单的。

在KTH皇家理工学院的文章中给出了上述公式， pc是表示有贡献者(contributors)的播放概率，pnc表示没有贡献者(non-contributors)的播放概率。

至于对social welfare的影响，跨异构网络的自私节点会影响各种P2P系统。KTH皇家理工学院的文章认为：“由于peer聚集导致的性能下降不仅限于推送系统，而且是不协调的P2P传播算法所固有的。”

为优化social welfare，文章建议使用一个 SGC（server guaranteed cap）服务器推荐上限，其中包含两种类型的数据传递，P2P传播(一些新的内容会在peer之间根据某些转发算法传递，后面会对此进行探讨）和直接交付。

从在传统P2P peer-assisted方法中可能会丢失部分内容的节点直接向服务器发出的请求的方法，要求服务器计算某种级别的阈值概率（Tp）并保留一部分总交付容量（mt）作为直接传播的储备用量（mr）。当已知叠加层中的贡献者数量和储备用量mr时，服务器将SGC和播放概率的阈值按以下公式计算：

这个计算的目的是决定哪些peer有资格进行直接交付。这由那些布局概率(layout probability)小于等于阈值的对象决定。从数学的角度来说，就是那些的对象。

Ghent大学的文章考虑了一个KTH皇家理工学院没有考虑的概念：网络拓扑。实际上，Ghent大学的团队指出：“据我们所知，没有一个P2P（多层）视频流网络使用拓扑信息来优化网络负载。” 另外，“本文提出的策略是利用实际网络的拓扑信息来协调节点选择，从而形成一个经得起未来考验的健壮的框架来在互联网上分发（直播）视频流，从而最大化每个目的终端的最低接收视频质量”作者提出了一种协调引擎来应对peers之间的网络拓扑变化，但他们同时也承认了单点故障的可能性，这种故障时所有的peer-assised解决方案都试图避免的。

Ghent大学的文章指出了P2P的另一个问题：peers（比如那些同时观看相同视频流的peers）数量可能会不足。这意味着P2P优化在没有大量观看同一视频流的终端用户的情况下不能进行。尽管IP多播是一种理论上的选择，但作者指出，由于互联网的稀疏部署，IP多播对于可伸缩视频流服务不是可行的解决方案。

传统网络拓扑结构的一个改进就是转发节点，这对于注入节点和跟踪节点的正常工作至关重要的。这也与KTH皇家技术学院的论文的研究结果相吻合，因为转发是peer-assisted交付的基础。

为了获得更高的效率和鲁棒性，Ghent大学的论文提出了一种环形拓扑(ring topology)的数学算法，该环形拓扑使用了特定的R转发节点：“通过优化目标函数R，对等节点可以将视频层传输到似乎具有最高带宽连接的目的地，这在原则上与使目的地从那些具有最高带宽连接上选择（注入或对等）节点的进行下载完全相同。”然而，但是，它不允许完全无限制的传输，尤其是在高带宽节点之间，本文为注入节点和对等节点引入了一个约束条件“来防止在没有约束条件的情况下可能发生的节点间不必要的数据传输”。

读者可能还记得，在Algorithm Series有关内容交付的文章中，介绍了一种环形方法，其中内容存储和检索在顺时针环上达到平衡。然而，P2P的环形拓扑的类型与CDN决策不太相似，而与以太网问世之前用于早期局域网（LAN）的令牌环形拓扑更相似。P2P环形拓扑的好处是，环形上的每个可用节点仍可以用作传统P2P树形拓扑的根（请参见图1）。

图1 一个连接R个转发节点的环网，每个环形节点都充当树拓扑的根。

03

PART

HTTP Live Streaming （HLS）

毫无疑问苹果的HTTP Live Streaming（HLS）不需要特定于HLS的算法，因为它使用从HTTP服务器传送的小文件（称为块chunks或段segments）。但是近来低延迟HLS的出现导致了一种特定的算法，Roger Pantos在2020年4月30日发布的《HTTP Live Streaming 2nd Edition》规范中指出了这一点。Pantos已成为HLS设计和应用中不可或缺的一部分，自HLS在2009年问世以来的所有规范草案在业界通常称为“ Pantos spec”。

此最新版本将替换原来的RFC 8216，预期的标准中包括低延迟HLS。作为该rfc8216bis-07版本的一部分，Pantos在附录C中提供了一种算法，以涵盖通过CDN进行的低延迟传递。Pantos写道：“客户端应该支持通过CDN和其他HTTP缓存传递低延迟流。”他还提出：“正确实施PART-HOLD-BACK，即服务器建议的实时播放延迟，要求客户端首先获取合理的、最新版本的媒体播放列表。客户端可以采用多种方法来获取最新版本的媒体播放列表的。例如，一种算法是通过两个播放列表请求来获取当前播放列表的部分目标时间段之内的内容。

04

PART

回到RTP

正如文章开头所提到的，基于RTP的流媒体是流媒体最初20年的主流，但是在带宽和专用媒体服务器软件方面，规模化的交付成本高得令人望而却步，这阻碍了该行业与传统的无线广播公司竞争。这样一来，尽管CDN解决了这个问题（成本很高），但随着P2P和基于HTTP的分段交付的出现，RTP的使用逐渐减少。

然而，RTP仍然以WebRTC的形式存在，并且运行良好，它使用标准的Web浏览器来提供实时音频和视频通信，有些采用一对一的单播分发模式，而有些采用允许进行视频会议或视频聊天的超低延迟的双向方法。与经典RTP一样，以一对多或多对多的方式扩展WebRTC也需要大量服务器（在WebRTC中称为选择性转发单元，即SFU）来解决扩展问题。

使用基于云的服务器平台似乎是一种理想的方式，它可以动态地向上或向下扩展SFU，以在端点之间路由视频。但是，有关SFU优化（根据拓扑说明了不同的优化方法）的论文《Media Streams Allocation and Load Patterns for a WebRTC CloudArchitecture》的作者写道：“为了满足资源需求，需要为通信云平台中的所有会话提供足够的SFU单元”，无论它是基于云的还是本地SFU池。

在基于云的基础架构中，当使用来自同一SFU并发处理的数百个流的真实数据时，作者认定服务器负载可以轻松地等于每个SFU管理的流数量为前提（请参见图2）。从这一点出发，他们使用服务器负载为每个先前定义的云服务器类别（例如，特定CPU，RAM和SSD容量的EC2实例）对每个服务器的最大允许流进行基准测试，然后从每个服务器进行采样以验证基准。他们写道：“我们要解决的问题是，当同一个SFU同时处理数百个流时，成千上万个流如何影响通用媒体流处理应用程序的整体质量。”

图2 基于云的WebRTC基础架构的系统概述

使用一个针对真实世界WebRTC流量的自回归（或运行平均值）模型，作者使用涵盖滞后观测值（lag observation）的线性回归方程式来计算数据中心内的服务器负载（请参见图3）。

图3 数据中心总负载滞后图，为期1个月

在公式中，0.9974是参数斜率，而2.8282是截距。

基于回归斜率，作者提出了一种算法，以确保每个SFU服务于最少的流，从而提供更好的负载平衡（请参见图4）。他们还警告说：“算法倾向于寻找一个最佳点并在后续的过程中坚持下去，这实际上会适得其反。”他们写道：“即使我们能够预测到定义的数据中心的总负载，资源分配算法仍然会遇到问题，因为一旦将会话的第一流分配给其他服务器，该会话的其他所有流都将分配给同一台服务器。”

图4 提出的算法可确保每个SFU服务于最少数量的流，从而提供更好的负载平衡。

05

PART

结论

我们所涵盖的每一类实时流媒体事件规模扩展方案都有相当多的研究正在进行：传统RTP，P2P交付，HTTP低延迟交付和WebRTC。每个方案的共同目标就是减少网络流量，无论是通过优化服务器（RTP和WebRTC）、将流卸载到通用服务器（HTTP）或缩小整个服务器占用空间（P2P）。但是，在一个地理区域中，对于一种方法有效的方法，未必在另一个地理区域起作用。这可能是各种原因引起的，我在本期的“Stream of Thought”专栏中探讨了其中的一些原因（见第12页）。然而，在所有这些研究中，关键的因素是如何降低总体延迟，并且在过去的一年里，对于每种交付方法，降低延迟方面都取得了重大进展。

原文链接请点击左下角“阅读原文”。

最后附上同系列文章链接：

算法系列：视频播放器性能