机器学习在ABR算法中的应用纵览

本文整理自LiveVideoStack线上分享第三季，第五期，由清华大学计算机系网络技术研究所博士生王莫为为大家介绍近些年ABR算法的发展，探讨基于机器学习的ABR算法的优劣势，并结合AiTrans比赛分析其在直播场景中的应用问题。

文/王莫为

整理/LiveVideoStack

大家好，我是来自清华大学计算机系的博士生王莫为，导师是崔勇教授，本次分享的主题是机器学习在ABR算法中的应用，机器学习在网络、系统和流媒体中都有各种各样的应用。

我们组自2016年就开始对机器学习如何与网络相结合做一些调研和综述，发现在2016年前后相关应用特别少，而且大多集中在拥塞控制和流量分类方面。AlphaGo之后就出现了许多深度学习包括深度强化学习方面的应用，应用包括路由、流媒体QoE优化和数据中心等。

去年八月份网络领域顶会SIGCOMM主会中五十篇论文中有三篇都是与机器学习相关的，Workshop和Posters and Demos加起来有二十多篇，其中NetAI workshop在SIGCOMM历史上首次人数破百，AI在系统、网络、流媒体传输各个方面都在不断深入，本次分享也将从ABR的角度来介绍它的发展。

1. 自适应码率（ABR）算法

本次分享的内容主要分为三个方面，首先会介绍ABR算法的一些背景和过去的一些传统算法，接下来会介绍机器学习驱动的ABR算法的发展和它潜在的一些问题，最后会简单介绍一下AITrans竞赛与直播场景下的ABR算法。

生活中各种各样的视频应用越来越多，包括视频点播、视频直播、短视频和在线教育，各大厂商也花费了很大力气去提高用户体验。

观看视频时，我们经常会遇到由于各种各样原因导致的视频卡顿或者码率不高导致画面不清晰的问题，这时大家一般都会在右下角通过选择视频清晰度来改善卡顿或者不清晰的问题，而目前很多厂商已经上线了自适应码率技术来提高用户的使用体验。

国内包括B站、爱奇艺都有相对应的技术上线，国外的YouTube、Twitch也有相关的技术应用。自适应码率一般来讲采用基于HTTP的DASH协议，基本运作流程是首先在CDN中存储已经按照不同码率编码好的视频块，客户端会不断向服务器请求某个码率下的视频块，每个视频块含有几秒钟的内容，服务器把视频传输给客户端，客户端会把视频块存在本地的缓冲区Buffer里。上图中紫色的块可以认为是视频块，持续时间是一秒，高度就是它的码率。在视频播放中，Buffer就会被实时消耗，如果此时你的下载速率与码率不匹配就会出现排空Buffer或者累计Buffer，当带宽远低于码率时会出现卡顿，于是各个播放器厂商都会考虑采用自适应码率来根据当前网络状况和Buffer长度来选择合适的码率去优化用户的体验质量（Quality of Experience），也就是QoE。QoE包括的指标一般有视频质量、卡顿和码率抖动等。

ABR的研究已经持续了很多年，但仍有一些挑战需要解决。假设现在有一个播放器已经播放了一段时间，视频的Throughput如上图所示，这时需要选择一个码率使得用户的QoE较高。有一种方式是对Throughput进行预测，然后根据Throughput的变化选择一个与它接近或者比它低一点的码率，但在移动设备或者无线场景下，网络变化难以预测，这给ABR决策带来了挑战。另一方面QoE指标之间是相互冲突的，视频质量越高视频块越大，所需的带宽越大，因此造成卡顿的概率越高，如果比较保守的选择低质量的视频块，虽然可以减少卡顿概率，但也会牺牲视频质量从而无法提高QoE。另一方面，ABR算法跟随Throughput变化的速度会影响视频切换的频率，如果想让码率变化尽可能的平滑就需要用提前准备好的Buffer去处理未来可能会遇见的Throughput的低谷。最后一点是码率决策具有一定的级联效应，先前的决策会对未来产生很大影响，换言之就是需要提前为某些Throughput的抖动变化预留一些Buffer，比如在某一时刻对Throughput的预测不是很好，选择了比较高的码率，如果网络发生抖动，在未来全部选择低码率也无法阻止这一次卡顿，所以这就需要ABR算法具有一定的前瞻性和预测性。

2. 机器学习驱动的ABR算法

关于ABR算法的研究工作一直都在进行。Rate-based的方法是一种经典的传统ABR算法，它首先对Throughput进行估计，之后选择与Throughput接近或略低的码率，可能还要配上些启发式算法来处理鲁棒性或者带宽探测的问题。2014年提出的BBA（buffer-based approach）算法基于buffer来进行码率决策，之所以选择buffer是因为Throughput抖动非常大，很难对其进行预测。BBA的基本策略是在Buffer比较小的时候认为卡顿概率比较高，选择相对低的码率，Buffer比较大的时候卡顿概率比较低，可以选择相对高的码率，处于二者之间时会以某种线性函数或者其他对应关系将buffer长度映射到中间的码率，来实现一种不依赖Throughput的解决方案。这个方案会出现Buffer比较小时相对保守，切换比较频繁的现象。还有一种同时基于throughput和buffer进行码率决策的方法MPC，全称是Model Predictive Control模型预测控制。其基本逻辑是先对客户端的播放逻辑进行简单建模，建模的目标是可以利用throughput和buffer来判断选择不同码率下未来可以得到的QoE，从而可以利用这个模型对未来进行规划。

到了2016年和2017年就开始出现了一些基于机器学习的ABR算法，其中CS2P主要解决MPC在Throughput预测不准的情况下会出现明显性能下降的问题，尤其是在Throughput进行快速抖动的情况下。CS2P利用隐马尔可夫模型进行带宽预测，可以认为是利用机器学习算法进行间接ABR决策的工作。

Pensieve是基于深度强化学习进行端到端码率决策的ABR算法。

2.1 CS2P

CS2P的全称是Cross-Session Stateful Prediction，基本逻辑是利用更好的Throughput预测来达到更好的码率选择，基本操作就是把Throughput预测拼到MPC方案上。作者观察到吞吐量具有某种状态转移特性，关键特征相似的会话吞吐量特性相似，例如上图中两条红线之间Throughput会呈现某种状态特性，然后它又对这些数据集中某一个时间段到另一个时间段的吞吐量转移进行了分析，发现其中确实具有明显的状态转移特性，这种特性可以考虑用隐马尔可夫模型去建模Throughput的变化。另一方面，作者发现如果把所有session的Throughput信息都拿去训练同一个模型，就会导致这个模型变得很差，表征能力不强或者学到相对平均的结果以至于不能反映每一个子类的特性。为了解决这个问题，可以考虑利用关键特征对会话进行聚类，之后再针对每个类别训练单独的隐马尔可夫模型。这个工作整体上就是通过Throughput的预测方式间接对码率进行决策。

2.2 Pensieve

2017年的Pensieve（Pensieve：AI带来的更流畅的高质量观看体验）是第一篇基于深度强化学习端到端进行码率决策的论文，这篇文章中提到之所以这样做是因为先前的工作总有一些固有的局限，因此考虑用端到端的方式去学习，减少人为干涉。ABR本身具有长期规划特性，这与深度强化学习本身十分适配，深度神经网络也可以处理多维输入状态来辅助决策。

强化学习的基本逻辑是靠Agent和Environment之间不断交互进行学习。具体的操作方式是，Agent会从Environment中不断地观测到状态state，基于state做出一些决策动作action传递给Environment，Environment会依据当前状态和决策转移到下一个状态，并且给Agent一个Reward反馈，Agent由此进行学习去最大化未来的累计Reward和。

ABR中的决策就是为未来每一个视频块选择一个合适的码率，输入信息包括当前带宽、历史选择码率和当前Buffer长度，除此之外可能还需要块大小、下载时间和剩余块数量等信息，由此Agent就可以每次决定一个动作后告诉环境。这里首先需要解决ABR算法与环境的交互的问题，强化学习需要不断地交互迭代才能实现很好的学习效果，这要求环境需要足够的快才能在有限的时间内完成学习过程。这里有两个选择，一个是ABR算法与真实环境进行交互，但真实环境交互次数远不足以支持Agent的训练，所以这里采用了一个块级别的仿真器来对客户端行为进行近似模拟，实现高加速比（十分钟模拟100小时播放）。有了仿真器和Agent交互之后就需要考虑Reward的设计，ABR算法的最终目标是要最大化的QoE和，每一步的Reward就应该是单步的QoE（质量、卡顿、切换的带权线性和），这个QoE 模型也是MPC所使用的。Pensieve的训练方案用的是A3C的快速异步算法，使用真实trace 或者人工合成的trace得到的效果都还不错。

2.3 机遇与挑战

Pensieve看上去似乎无懈可击，但仍存在一些问题。在ABR和流媒体优化中，QoE模型如何构建一直是一个悬而未决的问题，不同用户和业务需求中质量、卡顿和切换比例关系可能会有变化。而Pensieve一旦训练完成之后，比例关系就已经确定，不太能够适应新的业务需求，因此预测在未来可能会出现多目标强化学习来解决多目标QoE的要求。

Pensieve在泛化方面有两种场景，一个是In-distribution，假设Pensieve应用的网络状态场景是可采样的，这样我们就可以对目标场景有一定认识，但之前的一些实验表明如果把流量分布的数量增加并且将对应的数据集混合在一起训练，分布的数量越多会导致Pensieve性能下降的约大。这使得在某些具体的数据集上训练Pensieve，混合训练和单独训练的pensieve agent之间的QoE差距会达到50%，这是不太能接受的程度。第二个场景是Out-of-distribution，在没有训练过的场景上pensieve很大程度会fail。

在视频源泛化方面，由于视频内容不同，编码得出的块的大小抖动幅度也不一样，如果在训练时没有考虑到多种视频源特性的话会导致一定程度上的性能下降，所以在这里可能会需要一些在线学习或者Meta-learning的方案去实现在线学习。

第三个问题在于仿真器与真实网络环境是否匹配的问题，这其中最大的问题在于仿真器是一个数值仿真，在网络状态部分采用的是直接读取Throughput trace去看某一时间段平均Throughput 大概是多少，这时Throughput trace是没有与传输层进行交互的，所以这里没法体现不同决策对传输层所带来的影响，这种情况下仿真器所得到的结果就会潜在得与真实网络环境存在偏差，同时也没办法模拟多用户带宽竞争的问题。还有个问题在于现在使用Throughput trace往往反应的都是当时的吞吐量而非带宽容量，而实际上的带宽大小很难采集，这之间的差异也会对这个问题产生影响。

在Pensieve paper中提到可以使用mahimahi仿真器作为传输层的仿真模拟，mahimahi很多时候也被用在TCP的拥塞控制场景里，它能够模拟中间瓶颈链路的Buffer变化情况，从而反映带宽和RTT的变化。但其本身加速比非常低，如果联合Throughput trace一起训练会拉低整个训练效率，因此这个方案存在一些效率问题。最近也有学者在考虑应用层ABR和传输层TCP拥塞控制的联合优化，斯坦福大学的puffer就是这方面的工作，大家可以关注一下。虽然有了Pensieve 提供的数据集、QoE模型和仿真器，但在网络或者流媒体领域去真的推进这件事情的话还需要一个公认的仿真系统或者开放的数据集。

3. AITrans竞赛与直播场景下的ABR算法

团队在去年9-12月份举办了一个直播流媒体的比赛AITrans，在其中构建了一套系统和平台，包括仿真器和数据，希望能为大家提供一些这方面的帮助，这个比赛后来拓展为ACM MM Grand Challenge。其主要任务是希望大家帮助我们去优化直播场景下的ABR决策，其中DASH以视频块为传输单位，延迟大，所以改为与公司合作，做了一个帧级别基于Push的直播流媒体传输系统。同时直播内容实时产生，ABR算法可利用信息减少，因为是直播对低延迟、高清、低卡顿、少切换的多目标QoE有更多的要求，这都导致了这个场景和原先点播场景有一些区别。为了解决低延迟的问题我们在ABR的基础上又添加了时延控制机制，也就是快慢播和跳帧，以此来对时延进行控制，最后在搭建的低时延直播传输仿真平台L3VTP进行测试。

在比赛的过程中可以发现选手们在直播场景下更多的还是在使用BBA、MPC、Pensieve算法的变种，比如有多阈值BBA，MPC + Oboe [SIGCOMM’18]和在Pensieve基础上加上直播信息作为输入，并修改训练算法和神经网络结构的变种等。

而一些选手包括冠军队都采用了一些方案来提高ABR的性能，一是网络状态分类，二是在直播场景下对源端信息进行帧大小和间隔的预测（机器学习或传统方法）。由于快慢播和跳帧机制的存在，采用强化学习的方案中还额外面对Reward对齐的问题。在点播中每个下载的块都会去播放，从而可以在下载时直接对块的QoE进行计算，而在直播中时延控制机制会导致下载的块也可能不会被播放，或者是以不同的速率播放，这都会影响最终的QoE，所以在最后计算reward的时候要和当时的决策对应才能使算法能够更好的运行。这其中得到的教训是不要过度依赖仿真器，团队在初赛时使用仿真器而决赛时使用真实系统，这两个之间还是存在某些实现上的差异，以至于某些在仿真器环境下比较好的算法在真实环境下出现了一些问题。