基于HTTP的动态自适应视频流的控制理论方法

05 Oct 2019 in 个人博客 on PAPER

SIGCOMM 2015的一篇论文，讲的是码率自适应算法R-MPC。

在互联网视频应用中，用户感知的体验质量(QoE)是至关重要，因为它会影响内容提供商和分发系统的收入。鉴于网络中很少提供优化此类措施的支持，瓶颈可能出现在分发系统的任何地方。因此，客户端中健壮的码率自适应算法对于确保良好的用户体验至关重要。先前的研究表明了最新的商业解决方案的关键局限性，并提出了一系列启发式解决方案。尽管提出了一些建议，但在以下方面仍然明显缺乏共识：(1)如何最好地设计这种客户端码率自适应逻辑(例如，使用估计带宽与缓冲区占用率)；(2)在不同的网络环境下特定类别的方法表现如何(例如，高吞吐量可变性)；(3)实际中，如何平衡不同的QoE目标(例如，启动延迟与缓冲)。为此，本文做出了三个关键的技术贡献。首先，为了给这个空间带来一些严谨性，我们开发了一种合理的控制理论模型来分析各种方法。其次，我们提出了一种新颖的模型预测控制算法，该算法可以有效结合吞吐量和缓冲区占用信息，从而优于传统方法。第三，实现了一个播放器实例，并使用真实的trace来验证我们的算法。

主要内容

每一个视频块都被编码为不同的码率，\(\mathcal{R}\)定义为不同的码率级别。播放器可以下载一个码率为\(R_{k} \in \mathcal{R}\)视频块\(k\), 令\(d_{k}\left(R_{k}\right)\)为码率\(R_{k}\)为视频块\(k\)的大小，令\(B(t) \in\left[0, B_{\max }\right]\)为时间\(t\)的缓冲区占用，\(C_{k}\)为吞吐量，定义为平均下载速率，\(q(\cdot): \mathcal{R} \rightarrow \mathbb{R}_{+}\)是一个非递减的函数，它将视频码率\(R_{k}\)映射到用户感知的视频质量\(q\left(R_{k}\right)\)，这里定义为恒等函数。将QoE定义为:
\(\begin{aligned} Q o E_{1}^{K}=& \sum_{k=1}^{K} q\left(R_{k}\right)-\lambda \sum_{k=1}^{K-1}\left|q\left(R_{k+1}\right)-q\left(R_{k}\right)\right| \\ &-\mu \sum_{k=1}^{K}\left(\frac{d_{k}\left(R_{k}\right)}{C_{k}}-B_{k}\right)_{+} \end{aligned}\)
其中:

平均视频质量：所有视频块的平均质量\(\frac{1}{K} \sum_{k=1}^{K} q\left(R_{k}\right)\)
平均质量变化幅度：这跟踪了从一个块到另一个块的质量变化的幅度\(\frac{1}{K-1} \sum_{k=1}^{K-1}\left|q\left(R_{k+1}\right)-q\left(R_{k}\right)\right|\)
缓冲时长：对于每个块，如果下载时间\(d_{k}\left(R_{k}\right) / C_{k}\)高于块下载开始时的播出缓冲区缓冲时长（即，\(R_{k}\)），则会发生缓冲事件。总的缓冲时长为: \(\sum_{k=1}^{K}\left(\frac{d_{k}\left(R_{k}\right)}{C_{k}}-B_{k}\right)_{+}\)
\(\lambda\)，\(\mu\)是分别与视频质量变化，缓冲时间相对应的非负加权参数。

算法1
//码率自适应的工作流程
initialize;
for k=1 to K do
\(\hat{C}_{\left[t_{k}, t_{k+N-1}\right]}=\operatorname{ThoughtputPredict}(C_{\left[t_{1}, t_{k-1}\right]})\);
\(R_{k}=f_{m p c}\left(R_{k-1}, B_{k}, \hat{C}_{\left[t_{k}, t_{k+N-1}\right]}\right)\);
Download chuck \(k\) with bitrate \(R_{k}\);
end for

在迭代\(k\)时，播放器吞吐量预测保持从块\(k\)到\(k + N-1\)的移动范围(N设置为2)，并执行以下三个关键步骤，如算法1所示。

预测：使用吞吐量预测器预测下N个块的吞吐量\(\hat{C}_{\left[t_{k}, t_{k+N-1}\right]}\)。这里使用最近5个块的观测吞吐量的谐波均值。
优化：这是MPC算法的核心，给定当前的缓冲区占用\(B_{k}\)，上一个选择的码率\(R_{k-1}\)，吞吐量预测\(\hat{C}_{\left[t_{k}, t_{k+N-1}\right]}\)，找到最优的码率选择\(R_{k}\)。\(R_{k}=f_{m p c}\left(R_{k-1}, B_{k}, \hat{C}_{\left[t_{k}, t_{k+N-1}\right]}\right)\)通过求解最大的\(QOE_{k}^{k + N-1}\)来实现。
应用：开始使用\(R_{k}\)下载块\(k\)，并向前移动预测窗口。

介绍

最近的许多研究都强调了用户感知的体验质量(QoE)在互联网视频应用中所起的关键作用，因为它最终会影响内容提供商的收入。具体来说，度量标准包括缓冲时长(播放器缓冲区没有要渲染的内容)，启动延迟(用户单击到开始渲染的时长)，平均播放码率以及码率抖动已成为关键因素。

由于复杂的互联网视频分发系统和网络瓶颈，播放器的码率自适应能力显著影响着用户体验的优化。如今，基于http的分发模型占据主导地位，视频通常以码率级别进行分块和编码。自适应视频播放器的目标是选择视频块的码率，以提供尽可能高的QoE。例如，最大化码率，同时最小化缓冲时长，并避免过多的码率抖动。

最近的许多研究都指出了设计这种适应逻辑的主要挑战，并且提出了一些解决这些挑战的提议。尽管出现了大量的算法，但是这些解决方案在多个方面似乎缺乏清晰性和共识。例如，有些人主张更好的吞吐量估计，而另一些人则建议改善组块调度。一些研究人员甚至反对基于速率的方法，该方法依赖于先前块下载的吞吐量，并提出了基于缓冲区占用的算法，该算法仅基于缓冲区占用来做出决策。

为了理解在不同的网络环境(例如低吞吐量与高吞吐量可变性)下不同类别算法(例如基于速率和基于缓冲区的算法)之间的权衡，我们首先将视频码率自适应建模为随机最优控制问题。我们定义了涉及视频码率自适应问题的关键动态变量和一个具体的优化目标。该模型使我们能够概述针对该问题的控制算法的更广阔的设计空间。我们发现了现有的仅依赖于基于纯速率或基于缓冲区方法中的缺陷，而结合了两种策略(rate-based and buffer-based)可能会解决这些缺点。

基于控制理论公式的见解，我们认为模型预测控制(MPC)是一类合适的算法，可以最佳地组合基于速率和基于缓冲区的反馈信号。宏观来看，MPC会尝试向前预测关键环境变量，并根据该预测解决精确的优化问题。MPC是众多现实世界控制问题中的首选技术。除了直观的表述之外，它还可以显式处理复杂的控制目标和约束，并具有一组众所周知的调整参数，例如预测范围。此外，MPC还具有其他定性优势，因为与高级控制方法相比，其开发时间要短得多，并且维护更容易，因为更改模型参数不需要完全重新设计。

在本文中，MPC方法需要预测接下来的几个数据块的预期吞吐量，并使用它来做出最佳码率决策，使得QoE最大化。的确，我们的仿真结果证实，如果我们可以运行最佳的MPC算法并且预测误差很小，那么MPC方案将优于传统的基于速率和基于缓冲区的策略。

但是，实际上，运行基于MPC的算法具有挑战性，因为它需要在每个时间步上解决非平凡(non-trivial)的离散优化问题。即使忽略计算开销，也存在实际困难，因为我们可能需要将此求解器与每个视频播放器捆绑在一起，或者要求用户下载并安装其他软件。为了应对这些挑战，我们开发了一种简单高效的FastMPC机制。从概念上讲，FastMPC本质上遵循表枚举方法，在此方法中，我们描述问题的状态空间，以最佳方式解决特定实例，并存储最佳控制决策以供将来在线使用。但是，如果简单粗暴地实现，此表的大小会导致显著的内存开销和视频播放器的启动延迟(例如，要加载的其他JavaScript)。幸运的是，我们表明，使用简单的值合并和压缩策略，就可以通过可管理的表大小实现接近最佳的性能。

我们已经在开源动态自适应流播放器dash.js中对FastMPC码率自适应算法进行了原型设计。我们选择的平台是基于HTML5规范的参考MPEG-DASH标准的开源项目，并得到业界的积极支持。我们算法的实现没有明显增加dash.js播放器的开销。我们还在演示页面中展示了基于FastMPC的播放器。

我们使用FCC, HSDPA以及合成的吞吐量trace来评估算法和原型实现。我们还通过基于仿真的敏感性分析实验的结果，来分析关键操作参数对不同类算法性能的影响。我们的主要发现是：

就QoE中位数而言，相比于目前最新的算法，我们提出的算法在FCC数据库上提升了15%，在HSDPA数据库上提升了10%。而且相比于dash.js原生的算法，也有巨大的提升(QoE中位数提升60%+)。
与其他算法相比，我们提出的FastMPC需要类似的CPU使用率，并且仅需要60kB的额外内存使用量。

本文主要做出以下贡献:

码率自适应问题的控制理论模型建模
包含现有的基于速率和基于缓冲区的策略的MPC方法的设计
一种实用且快速的基于表枚举的算法FastMPC
基于开源视频播放器dash.js的低开销实现
在不同参数和trace上对不同算法的评估

背景和相关工作

首先，我们先概述基于HTTP的自适应视频流的工作原理，然后再介绍当今最新解决方案的主要缺点。

互联网视频技术，例如Microsoft Smooth Streaming，苹果的HLS和Adobe的HDS都基于基于HTTP的自适应流。在DASH系统中，每个视频均由多个片段或“块”(相当于几秒钟的播放时间)组成，并且每个块均以多个离散的码率进行编码。来自不同码率流的块对齐，以便视频播放器可以根据需要在块边界处切换到不同的码率。与自定义流协议(例如实时消息协议RTMP)相比，此方法具有一些实用的优势。HTTP的使用使提供程序可以无缝绕过中间件。此外，它可以使用现有的商用CDN服务器，而无需自定义修改。最后，通过使服务器成为无状态服务器，可以使用多个服务器和CDN来实现更好的应用程序层弹性。

下图显示了自适应视频播放器的抽象模型。播放器在其决策逻辑中使用一些输入（例如，缓冲器占用或网络吞吐量的估计）来选择下一个要下载的块的码率。在做出此决定时，播放器必须考虑许多可能引起冲突的QoE注意事项：(1)最小化播放缓冲时长;(2)尽可能高的播放比特率;(3)最小化启动延迟，以使用户在等待视频加载时不会退出;(4)通过避免频繁或较大的码率跳跃来保持播放尽可能流畅。

AbstractmodelofDASHplayers

要了解为什么这些目标会造成冲突，让我们考虑两个极端的解决方案。最小化缓冲时长和启动延迟的简单解决方案是始终选择最低的码率，但这与提供高清晰度视频的目标相冲突。相反，选择最高可用码率可能会导致许多缓冲事件。类似地，如果同时最小化重缓冲时长和最大化平均码率的最佳选择是为每个块切换码率，则保持平滑播放的目标也可能会发生冲突。

本文的重点是客户端的自适应解决方案(其他补充工作包括使用服务器端码率切换，修改TCP以避免突发以及网络内吞吐量管理和缓存)，原因有两个：(1)客户端提供立即可部署的解决方案；(2)客户端可快速发现性能问题并响应。

许多研究表明，所有的最新的播放器的QoE表现都不佳。为了缓和这些问题，业界提出了很多解决方案。从宏观来讲，这些解决方案可以大致分为两类：基于速率的算法和基于缓冲区的算法。采用基于速率的方法的视频播放器实质上会根据估计的可用吞吐量来选择最高的码率。但是，如先前的工作所示，HTTP上的吞吐量估算存在明显的偏差，这会导致传统的基于速率的方法出现问题。一些解决方案试图通过平滑吞吐量估计或选择更好的调度策略来解决这些偏差。另一方面，基于缓冲区的算法不使用吞吐量估算，而是使用缓冲区占用率作为反馈信号，并设计机制以将缓冲区占用率保持在所需水平，从而实质上丢弃任何可用的吞吐量信息。

尽管对该主题有广泛的兴趣，但是今天最关键的是对码率自适应算法的基本理解。每个上述解决方案都提供了在特定（和隐式）环境假设下的启发式方法。虽然孤立地看到的每种方法都表现出优于商业参与者的性能，但很少有系统地比较不同类别的算法如何相互叠加，或者这些技术组件中的哪些至关重要的，或者这些算法在不同网络环境下的鲁棒性怎么样(例如，吞吐量稳定性，缓冲区大小，比特率级别数)。此外，这些算法中的许多算法甚至都未能明确陈述其寻求优化的目标，从而使得进行有意义的比较变得更加困难。

控制理论模型

在本节中，我们将建立HTTP视频流化过程的数学模型，并形式化定义码率自适应问题。该模型为我们提供了一个比较和评估现有算法的框架，并为潜在的改进奠定了基础。

视频流化模型

我们把视频看成是一个连续视频块的集合，\(\mathcal{V}=\{1,2, \cdots, K\}\)，每一个块包含\(L\)秒的视频。每一个块都被编码为不同的码率，\(\mathcal{R}\)定义为不同的码率级别。播放器可以下载一个码率为\(R_{k} \in \mathcal{R}\)视频块\(k\), 令\(d_{k}\left(R_{k}\right)\)为码率\(R_{k}\)为视频块\(k\)的大小。在恒定码率(CBR)的情况下，\(d_{k}\left(R_{k}\right)=L \times R_{k}\)；在可变码率(VBR)的情况下, \(d_{k} \sim R_{k}\)的关系在不同块之间可能不一样。

码率越高，用户感知的视频质量就越好。定义\(q(\cdot): \mathcal{R} \rightarrow \mathbb{R}_{+}\)为一个非递减的函数，它将视频码率\(R_{k}\)映射到用户感知的视频质量\(q\left(R_{k}\right)\)。\(q(\cdot)\)可能会随着播放设备和播放内容而不同。如，在HDTV上，3Mbps和1Mbps可能会导致用户体验的显着差异，而3Mbps和1Mbps的视频质量可能在移动设备上相似；同样，与“静态”块相比，“动态”块的比特率提高将带来更多的QoE增益。

下载的视频块会被存储在播放器的缓冲区(playback buffer，包含已下载但未播放的视频)，令\(B(t) \in\left[0, B_{\max }\right]\)为时间\(t\)的缓冲区占用，即，留在缓冲区的视频时长。缓冲区大小\(B_{\max }\)取决于服务提供商的策略以及播放器上的存储限制。一般的播放器缓冲区可能包含几十秒的视频片段。

下图帮助说明了视频播放器的概念性操作。在时间\(t_{k}\)，视频播放器开始下载块\(k\)。当前视频块下载时长为\(d_{k}\left(R_{k}\right) / C_{k}\), 取决与块大小\(R_{k}\)和当前下载过程平均下载速度\(C_{k}\)。一旦块下载完成，播放器会等待\(\Delta t_{k}\), 然后在时间\(t_{k+1}\)开始下载视频块\(k+1\)。我们假设等待时间\(\Delta t_{k}\)很小，不会导致缓冲事件。如果我们用\(C_{t}\)表示在时间t的网络吞吐量，那么我们有：

\(t_{k+1}=t_{k}+\frac{d_{k}\left(R_{k}\right)}{C_{k}}+\Delta t_{k}\) (1)

\(C_{k}=\frac{1}{t_{k+1}-t_{k}-\Delta t_{k}} \int_{t_{k}}^{t_{k+1}-\Delta t_{k}} C_{t} d t\) (2)

缓冲区占用率\(B(t)\)随着块的下载和视频的播放而变化。具体而言，下载块\(k\)后，缓冲区占用量增加\(L\)秒，而随着用户观看视频而减少。令\(B_{k}=B\left(t_{k}\right)\)表示播放器开始下载块\(k\)时的缓冲区占用量。然后可以将缓冲区的动态变化公式化为：

\(B_{k+1}=\left(\left(B_{k}-\frac{d_{k}\left(R_{k}\right)}{C_{k}}\right)_{+}+L-\Delta t_{k}\right)_{+}\) (3)

在这里，符号\((x)_{+}=\max \{x, 0\}\)确保该项永远不会为负。请注意，如果\(B_{k}<d_{k}\left(R_{k}\right) / C_{k}\)，则当视频播放器仍在下载块\(k\)时，缓冲区变空，从而导致缓冲事件，如下图所示。

Illustrationofbufferdynamics

等待时间\(\Delta t_{k}\)的确定，也称为组块调度问题，在提高多人视频流的公平性方面同样是一个有趣且重要的问题。但是，在本文中，我们假设玩家只要下载了块\(k\)，便立即开始下载块\(k+1\)。一个例外是当缓冲区已满时，播放器等待缓冲区减小到允许添加块k的水平。即：

\(\Delta t_{k}=\left(\left(B_{k}-\frac{d_{k}\left(R_{k}\right)}{C_{k}}\right)_{+}+L-B_{\max }\right)_{+}\) (4)

最大化QoE问题

码率自适应的最终目标是提高用户的QoE。我们的目标是提供一个灵活的QoE模型，而不是一个固定的QoE概念，因为这是一个活跃的研究领域。尽管用户的特定QoE功能可能有所不同，但我们可以列举视频QoE的关键要素为：

平均视频质量：所有视频块的平均质量\(\frac{1}{K} \sum_{k=1}^{K} q\left(R_{k}\right)\)
平均质量变化幅度：这跟踪了从一个块到另一个块的质量变化的幅度\(\frac{1}{K-1} \sum_{k=1}^{K-1}\left|q\left(R_{k+1}\right)-q\left(R_{k}\right)\right|\)
缓冲时长：对于每个块，如果下载时间\(d_{k}\left(R_{k}\right) / C_{k}\)高于块下载开始时的播出缓冲区缓冲时长（即，\(R_{k}\)），则会发生缓冲事件。总的缓冲时长为: \(\sum_{k=1}^{K}\left(\frac{d_{k}\left(R_{k}\right)}{C_{k}}-B_{k}\right)_{+}\)
启动延迟\(T_{s}\),假设\(T_{s} \ll B_{\max }\)

由于用户可能对四个分量中的哪个分量更重要有不同的偏好，因此我们通过上述分量的加权和来定义视频段\(1\)到\(K\)的QoE:

\(\begin{aligned} Q o E_{1}^{K}=& \sum_{k=1}^{K} q\left(R_{k}\right)-\lambda \sum_{k=1}^{K-1}\left|q\left(R_{k+1}\right)-q\left(R_{k}\right)\right| \\ &-\mu \sum_{k=1}^{K}\left(\frac{d_{k}\left(R_{k}\right)}{C_{k}}-B_{k}\right)_{+}-\mu_{s} T_{s} \end{aligned}\) (5)

在这里，\(\lambda\)，\(\mu\)，\(\mu_{s}\)是分别与视频质量变化，缓冲时间和启动延迟相对应的非负加权参数。相对较小的\(\lambda\)表示用户并不特别关注视频质量变化；\(\lambda\)越大，将付出更多的精力来实现视频质量的平滑变化。相对于其他参数，较大的\(\mu\)表示用户非常担心缓冲。如果用户更喜欢低启动延迟，我们将使用较大的\(\mu_{s}\)。

总而言之，QoE的定义非常笼统，因为它允许我们在不同的影响因素上对不同的用户偏好进行建模。

\(\max _{R_{1}, \cdots, R_{K}, T_{s}} Q_{O} E_{1}^{K}\) (6)
\(\text {s.t.} \quad t_{k+1}=t_{k}+\frac{d_{k}\left(R_{k}\right)}{C_{k}}+\Delta t_{k}\) (7)
\(C_{k}=\frac{1}{t_{k+1}-t_{k}-\Delta t_{k}} \int_{t_{k}}^{t_{k+1}-\Delta t_{k}} C_{t} d t\) (8)
\(B_{k+1}=\left(\left(B_{k}-\frac{d_{k}\left(R_{k}\right)}{C_{k}}\right)_{+}+L-\Delta t_{k}\right)_{+}\) (9)
\(B_{1}=T_{s}, \quad B_{k} \in\left[0, B_{\max }\right]\) (10)
\(R_{k} \in \mathcal{R}, \quad \forall k=1, \cdots, K\) (11)

最大化QoE问题：QoE最大化码率自适应问题表示为\(Q O E_{-} M A X_{1}^{K}\)，在给定吞吐量trace\(\left\{C_{t}, t \in\left[t_{1}, t_{K+1}\right]\right\}\)作为输入的情况下，优化提供了以下内容作为输出：1)码率决策\(R_{1}, \cdots, R_{k}\)，以及2)启动时间\(T_{s}\)。

注意，假设问题\(Q O E_{-} M A X_{1}^{K}\)是在此优化时假设视频尚未开始播放的情况下制定的，因此启动延迟\(T_{s}\)是一个决策变量。但是，当下一个要下载的块为\(k_{0}\)且当前缓冲区占用为\(B_{k_{0}}\)时，也可以在视频播放期间的时间点\(k_{0}\)处实现此QoE最大化。在这种情况下，我们可以删除变量\(T_{s}\)并将相应的稳态问题表示为\(Q O E_{-} M A X_{-} S T E A D Y_{k_{0}}^{K}\)。

算法类别

本节中，我们将对问题\(Q O E_{-} M A X_{1}^{K}\)进行特征描述，并在此框架内描述现有的码率自适应算法，以了解它们之间的关系。

最大化QoE问题是有限随机最优控制问题。随机性的来源位于吞吐量\(C_{t}\)中。当播放器选择码率\(R_{k}\)时，只有过去的吞吐量\(\left\{C_{t}, t \leq t_{k}\right\}\)可用，而将来的值\(\left\{C_{t}, t>t_{k}\right\}\)未知。

但是，吞吐量预测器可用于获得定义为\(\left\{\hat{C}_{t}, t>t_{k}\right\}\)的预测。根据这预测和缓冲区占用信息(已知的)，码率控制器选择下一个块\(k\)的码率：

\(R_{k}=f\left(B_{k},\left\{\hat{C}_{t}, t>t_{k}\right\},\left\{R_{i}, i<k\right\}\right)\) (12)

有效的吞吐量预测器的设计本身就是一个有趣的研究方向。在本文中，我们仅关注码率自适应算法，并假设已将预测变量提供给我们，并根据预期的预测误差对其进行了表征。即，我们专注于\(f(\cdot)\)的设计以及预测误差对比较控制算法性能的影响。在以下各节中，我们将系统地评估在各种可变性条件下，如何使用最新的预测器执行不同算法。

现在，不同的自适应算法本质上采用不同的函数\(f(\cdot)\)。具体而言，文献中出现了两大类算法：基于速率的算法(RB)和基于缓冲区的算法(BB)。RB策略本质上仅根据吞吐量预测来选择码率：

\(R_{k}=f\left(\left\{\hat{C}_{t}, t>t_{k}\right\},\left\{R_{i}, i<k\right\}\right)\) (13)

例如，典型的RB策略是选择低于预测吞吐量的最大可能码率。
另一方面，BB策略提倡仅基于缓冲区占用进行决策，即:

\(R_{k}=f\left(B_{k},\left\{R_{i}, i<k\right\}\right)\) (14)

同时将吞吐量变化视为未建模的干扰。

但是请注意，如下图所示，这两种算法都在丢弃可能有用的信息。因此，原则上两者都不是最优的。理想情况下，我们要同时使用缓冲区占用率和吞吐量预测，从而考虑更宽的比特率自适应策略设计空间，如式（12）和下图所示的算法A3所示。

最优码率自适应的模型预测控制方法

在本节中，我们将介绍一种用于比特率自适应的模型预测控制(MPC)方法，并描述一种基于MPC的具体工作流，该工作流可以最佳地结合吞吐量预测和缓冲区占用率。我们还开发了一种Robust MPC方法，可以在高度可变的网络条件下更好地处理吞吐量预测中的错误。

why MPC

我们不能断言在所有可能的控制算法中MPC是必需的或最佳选择。我们的目标仅仅是争论MPC是码率适应问题的自然契机。

Strawman solutions:如前所述，码率自适应本质上是随机最优控制问题。在这方面，有两种众所周知的候选控制算法：(1)比例积分微分(PID)控制和(2)基于马尔可夫决策过程(MDP)的控制。尽管与MPC相比，PID在计算上更简单，但它只能起到稳定系统的作用，而不能明确优化我们的QoE目标。另外，PID控制被设计为在连续的时间和状态空间中工作，并且在像我们这样的高度离散的系统中使用它可能会导致性能下降或不稳定。另外，对于MDP，我们可以考虑将吞吐量和缓冲区状态转换公式化为马尔可夫过程，并使用标准算法(例如值迭代或策略迭代)找到最优控制策略。但是，这有一个很强的假设，即吞吐量动态遵循马尔可夫过程，目前尚不清楚这是否成立。我们认为MDP的潜在用途和吞吐量动态分析是未来的工作。

MPC案例: 理想地，如果完全了解视频\(\left[ t_{1},t_{K+1}\right]\)整个水平上的未来吞吐量，则可以通过解决整个视频\(QOE_{-}MAX_{1}^{K}\)的优化问题来一次计算出最佳比特率\(R_{1},\cdots,R_{K}\)和启动延迟\(T_{s}\)。在实践中，没有这样的完美信息，因此很难通过优化来找到这样的最优解。

尽管可能无法获取未来的信息，但有可能可以在不久的将来\(\left[ t_{k},t_{k+N}\right]\)上获得合理准确的吞吐量预测。研究表明，网络条件在短时间范围内相当稳定，通常在短时间内(几十秒)不会发生剧烈变化。基于此见解，我们可以使用此范围内的预测来优化QoE，应用第一个码率\(R_{k}\)，然后将范围向前移动到\(\left[ t_{k+1},t_{k+N+1}\right]\)。这种方案称为模型预测控制(MPC)或后退水平控制。MPC算法广泛应用于从工业控制到导航的不同领域。MPC的一般优势在于，MPC可以利用预测来在约束条件下在线优化动态系统中的复杂控制目标。

基本的MPC算法

算法1概述了MPC用于码率自适应的工作流程。在本文中，该算法本质上是通过向前看N步(即移动视界)来选择码率\(R_{k}\)，并通过吞吐量预测\(\left\{\hat{C}_{t}, t \in\left[t_{k}, t_{k+N}\right]\right\}\)或\(\hat{C}_{\left[t_{k}, t_{k+N}\right]}\)来解决特定的QoE最大化问题(这取决于播放器处于稳定还是启动阶段)。根据反馈信息获取第一个码率\(R_{k}\)，并在每个步骤\(k\)上迭代优化过程。

在迭代\(k\)时，播放器保持从块\(k\)到\(k + N-1\)的移动范围，并执行以下三个关键步骤，如算法1所示。

预测：使用某些吞吐量预测器预测下N个块的吞吐量\(\hat{C}_{\left[t_{k}, t_{k+N}\right]}\)。本文的目的不是设计一种预测机制，而是依靠现有方法。自然地，提高此预测的准确性将改善通过MPC实现的增益。也就是说，可以将MPC扩展为对错误具有鲁棒性，如下所述。
优化：这是MPC算法的核心，给定当前的缓冲区占用\(B_{k}\)，上一个选择的码率\(R_{k-1}\)，吞吐量预测\(\hat{C}_{\left[t_{k}, t_{k+N}\right]}\)，找到最优的码率选择\(R_{k}\)。在稳定状态下，\(R_{k}=f_{m p c}\left(R_{k-1}, B_{k}, \hat{C}_{\left[t_{k}, t_{k+N}\right]}\right)\)通过求解\(QOE_{-}MAX_{-}STEADY_{k}^{k + N-1}\)来实现。在启动阶段，它还优化了启动时间\(T_{s}\)为\(\left[R_{k}, T_{s}\right]=f_{m p c}^{s t}\left(R_{k-1}, B_{k}, \hat{C}_{\left[t_{k}, t_{k+N}\right]}\right)\)，通过求解\(QOE_{-}MAX_{k}^{k + N-1}\)来实现。如果我们忽略有关计算开销的实际细节，则可以简单地使用CPLEX等现成的求解器来解决这些离散的优化问题。实际上，我们无需在视频播放器中明确解决优化问题。
应用：开始使用\(R_{k}\)下载块\(k\)，并向前移动预测窗口。如果播放器处于启动阶段，请等待\(T_{s}\)之后再开始播放。

与我们下面讨论的基于缓冲区的（BB）和基于速率的（RB）相比，该工作流在质量上具有许多优势。首先，这种MPC算法合理地同时使用吞吐量预测和缓冲区信息。其次，与纯RB方法相比，MPC消除了每个步骤的预测误差，并且对预测误差更加鲁棒。具体来说，通过在移动的预测范围内优化多个块，一个特定块的较大预测误差将对性能产生较小的影响。第三，MPC直接优化了一个正式定义的QoE目标，而在RB和BB中，没有明确定义不同QoE因素之间的权衡，因此只能单独优化某一个因素。

Robust MPC

基本的MPC算法假定存在准确的吞吐量预测器。但是，在某些严峻的网络条件下，例如在蜂窝网络中或在互联网拥挤的黄金时间，这种精确的预测器可能不可用。例如，如果预测变量始终高估吞吐量，则可能会导致长时间的缓冲。为了抵消预测误差，我们开发了一种鲁Robust MPC算法。

假设实际吞吐量与点估计值\(C_{t}\)相比，可以在\(\left[\hat{C}_{t}^{-}, \hat{C}_{t}^{+}\right]\)范围内取任意值，那么Robust MPC实质上可以优化最坏情况的QoE。Robust MPC需要在\(t_{k}\)时刻解决以下优化问题以获得比特率\(R_{k}=f_{r o b u s t m p c}\left(R_{k-1}, B_{k}, \left[\hat{C}_{t}^{-}, \hat{C}_{t}^{+}\right]\right)\)：

\(\max _{R_{k}, \cdots, R_{k+N-1}} \min _{C_{t} \in[\hat{C}_{t}^{-}, \hat{C}_{t}^{+}]} Q o E_{k}^{k+N-1}\) (15)

\(\text { s.t. } \text { Constraints }(7) \text { to }(11)\) (16)

通常，解决这样的最大-最小鲁棒性优化问题可能是很复杂的。但是，在我们的特定情况下，我们可以证明最坏情况是在吞吐量处于其下界\(C_{t} = \hat{C}_{t}^{-}\)时发生的。因此，Robust MPC的实现是直接的。代替\(C_{t}\)，我们使用最低的\(C_{t}\)作为常规MPC QoE最大化问题的输入。形式化为:

定理1: Robust MPC控制器等效于以吞吐量下限为输入的常规MPC，即:
\(R_{k}=f_{r o b u s t m p c}\left(R_{k-1}, B_{k}, \left[\hat{C}_{t}^{-}, \hat{C}_{t}^{+}\right]\right)=f_{m p c}\left(R_{k-1}, B_{k}, \hat{C}_{t}^{-}\right)\)
证明：从概念上讲，QoE函数\(QoE\left(R，C\right)\)可以写为3个项的总和(g1：总视频质量，g2：总质量变化，g3：缓冲时间)，其中仅缓冲时间项取决于吞吐量C。从而,
\(\begin{aligned} & \max _{R} \min _{C \in[C^{-}, C^{+}]} \operatorname{Qo} E(R, C) \\ \equiv & \max _{R}\left(g_{1}(R)-\lambda \times g_{2}(R)-\max _{C \in[C^{-}, C^{+}]} \mu \times g_{3}(R, C)\right) \\ \equiv & \max _{R} \operatorname{Qo} E(R, C^{-}) \end{aligned}\)
由于吞吐量\(C\)的任何降低都将导致更长的缓冲时间，因此在\(C = C^{-}\)时可达到最小QoE。

潜在的不利影响之一是，假设吞吐量最低，Robust MPC比常规的MPC更保守。这里的保守程度自然取决于下限的松紧程度。在我们的实现中，我们将最大的错误预测错误应用于过去的几个块，并发现它在实践中效果很好。

在实际中使用MPC——FastMPC

基于速率和基于缓冲区的算法需要相对较小的计算，但MPC面临的挑战是我们需要在每个时间步上解决离散优化问题。这里有两个实际问题：

计算开销：首先，MPC的高计算开销对于低端移动设备尤其成问题，因为低端移动设备预计将成为未来的主要视频消费者。由于在播放器开始下载每个块之前调用了码率自适应决策逻辑，所以码率自适应逻辑中的过多延迟将对播放器的QoE产生负面影响。
部署：由于我们没有QoE最大化问题的封闭式或组合式解决方案，因此我们将需要使用求解器(例如CPLEX或Gurobi)。但是，视频播放器可能无法与此类求解器功能捆绑在一起。例如，许可问题可能会阻止分发此类软件，或者可能需要额外的插件或软件安装，这对部署过程造成了重大障碍。

从上面的讨论中可以明显看出，我们开发的解决方案应该是轻量级的和可组合的(即不在线解决LP或ILP)。因此，在本节中，我们将通过开发不需要视频播放器中任何显式求解器功能的快速，低开销的FastMPC设计来解决这两个关键的实际问题。

FastMPC的宏观想法

宏观来讲，FastMPC算法本质上遵循表枚举方法。在这里，我们离线执行枚举状态空间，并求解每个特定的实例。然后，在在线步骤中，我们仅使用映射到当前操作条件的这些存储的最佳控制决策。也就是说，该算法将简化为一个由最接近当前状态的键值索引的简单表查找，并且查找的输出是所选配置的最佳解决方案。

在我们的设置中(下图)，状态空间由以下维度确定：(1)当前缓冲区级别，(2)先前选择的码率，以及(3)下N个块的预测吞吐量。因此，FastMPC将需要枚举每一个维度的可能情况，并以此在离线状态计算最优结果。

不幸的是，由于我们具有高维状态空间，因此直接使用这种想法将非常低效。例如，如果我们有100个可能的缓冲区级别值，10个可能的比特率，大小为5的向前预测范围以及1000个可能的吞吐量值，那么表中将有\(10^{18}\)行！这个庞大的状态空间有两个明显的后果。首先，将整个表显式存储在内存中可能不切实际。请注意，这不仅是假设的问题。如果我们需要在dash.js中实际实现此表查找，这将意味着非常高的内存占用量以及较大的启动延迟，因为需要将该表下载到播放器模块中。其次，离线计算最优结果将耗费大量时间，随着操作条件的变化，可能需要重新计算。

优化FastMPC的性能

接下来，我们提出两个关键的优化方法，以使表枚举方法易于处理。

通过合并进行压缩：首先，为了解决离线计算成本，对于缓冲区和吞吐量水平，我们可能不需要非常细粒度的值。因此，可以适当地将这些值粗化为聚集仓。而且，使用分箱，我们不需要显式存储行键，因为这些行键是直接从bin行索引中计算出来的。这里的挑战是平衡装箱的粒度和最佳实践的损失。在实践中，我们发现对缓冲区级别使用100 bins，对吞吐量预测使用100 bins效果很好，并且产生了接近最佳的性能。

表压缩：通过离线计算得到的决策表将具有重要的结构。具体来说，针对几种类似情况的最佳解决方案可能是相同的。因此，我们可以结合分箱策略来利用此结构，以使用游程编码来存储决策向量来探索简单的无损压缩策略。然后可以使用二进制搜索在线检索最佳决策。在实践中，我们看到压缩后该表占用的空间不足60 kB，其中缓冲区级别为100 bins，吞吐量预测为100 bins和5比特率级别。

实现

在本节中，我们描述dash.js框架中MPC方法的实现。我们的实现基于dash.js master分支(v1.2.0版本)，因为它是开发时的稳定版本。我们认为我们的实现可以很容易地适应将来的版本，因为我们需要的修改最少(JavaScript的约800行)。有关源代码和演示的更多信息，请访问我们的演示页面。

播放器的选择：过去许多的自适应码率播放器都是使用Adobe OSMF框架进行原型制作的，这似乎是很自然的选择。但是，我们与行业人员的对话显示，几乎所有内容提供商都在转向基于MPEG-DASH标准的基于HTML5的播放器，因此OSMF(基于Flash且市场份额不断下降)不太可能成为具有世界影响力的平台。选择了DASH播放器后，我们定性评估了DASH标准的几种实现方式。不幸的是，这些依赖于自定义客户端或利基视频播放器平台。考虑到这些考虑因素，我们选择dash.js框架，因为它是MPEG-DASH标准的参考开源实现，并且受到业界领先参与者的积极支持。我们相信我们的原型工作也将为这些标准化工作的发展提供信息。例如，任何控制算法的关键要求是知道每个视频块的大小(以字节为单位)，但是该标准并未规定清单必须报告块大小，这可能是当前规范的关键缺点。

dash.js概述：为了理解我们的实现和修改，我们从dash.js播放器的体系结构的简要背景开始。关键组件在下图中高亮显示。

从宏观来看，dash.js实现将高层次的视频流功能与低层次的特定DASH标准相关组件分开。由于我们对特定于标准的实现不特别感兴趣，因此我们将不修改这部分代码，只关注与自适应流相关的功能。

码率自适应和视频流逻辑的关键类和函数如下：

BufferController：此类提供了一些功能，可通过请求新片段并做出码率更改决策来管理播放器的缓冲区级别。具体来说，validate会定期调用，并调用AbrController类中的getPlaybackQualityfunction函数来找到最佳码率。它还维护一个bufferLevel来记录播放器当前的缓冲区占用情况，可用于确定码率。
AbrController：此类包含核心码率自适应逻辑。在最初的dash.js实现中，采用了基于规则的决策逻辑来找到码率。具体来说，DownloadRatioRule根据“下载比率”(最后一块的播放时间除以其下载时间)选择码率；另一方面，InsufficientBufferRule会根据缓冲区级别最近是否达到下限来选择码率，以避免重新缓存。为每个规则分配优先级以解决冲突并做出最终的码率决策。

修改和扩展：我们在dash.js中观察到两个有问题的实现细节。首先，代码会定期调用validate函数以检查缓冲区的状态，并在AbrController中调用函数以确定是否应更改当前码率。注意，这意味着码率决策并非总是在块边界处做出，这可能导致延迟执行码率决策，甚至重新下载先前的块。其次，dash.js并行下载多个块，即使理想情况下应优先考虑视频流中较早的块。

为了解决这些问题，我们通过对BufferController类进行两个关键更改来更改了dash.js代码中的码率决策和块下载过程：1)在每个块的开头都做出了码率决策，2)块下载是完全顺序的，即，不允许同时下载多个块。这允许一个基本的实现框架，该框架与我们的模型和其他建议的算法一致。

通过修改程序，我们通过用我们自己的实现替换了原始的基于规则的码率自适应逻辑，从而实现了不同的码率自适应算法(例如FastMPC，BB，RB)。FastMPC实现具有用于索引控制决策的静态表。我们还基于先前的工作实现了基于谐波均值的吞吐量预测方案，以及BufferController类中的其他日志记录功能，以记录播放器状态的完整日志，包括缓冲区级别，码率，缓冲时间，预测/实际吞吐量。

评估

在本节中，我们将真实的播放器和模拟实验相结合，将我们的方法与现有的基于速率和基于缓冲区的方法进行了比较。我们还将介绍FastMPC实现的CPU和内存开销方面的微基准。

设置

我们从描述关键参数开始：(1)吞吐量变化trace；(2)视频特定参数；(3)各种自适应算法的配置；(4)定义本节中使用的标准化QoE指标。

输入参数

吞吐量trace：我们的目标是使用实际的网络可变性条件评估各种码率自适应方法。鉴于数十秒内无法进行大规模持续的吞吐量测量，因此，我们结合使用了现有数据集和合成模型。

宽带数据集(FCC):三者之中最稳定
移动网络数据集(HSDPA):三者之间变化最大
合成数据集

视频参数：我们使用DASH264 JavaScript参考客户端测试页中的“Envivio”视频，该视频长260s，由65个4s块组成。视频由H.264 / MPEG-4 AVC编解码器以以下码率级别编码：\(\mathcal{R} = \{350kbps，600kbps，1000kbps，2000kbps，3000kbps\}\)。这分别与YouTube视频码率水平240p，360p，480p，720p和1080p的要求一致。我们将缓冲区大小设置为\(B_{max} = 30s\)。我们假设\(q(\cdot)\)是一个恒等函数。作为默认的QoE功能，我们使用权重\(\lambda= 1，\mu = \mu_{s} = 3000\)，这意味着1秒的缓冲/启动时间会受到与将块的码率降低3000 kbps相同的损失。我们还进行了敏感性实验，以改变QoE权重。

算法和指标

自适应算法：在每个类别中确定最佳算法是困难的，因为它涉及到在无限维功能空间上的优化。为此，我们从先前的工作中为每类算法选择一种广泛采用的函数形式，并基于包含所有数据集中随机抽取的100条吞吐量trace数据的训练数据集，通过经验模拟对自由参数进行优化。我们评估以下算法：

RB: 选择小于一倍预测码率的最大可用码率
BB:
FastRPC: FastMPC：我们使用向前预测范围h = 5，并使用过去5个块的谐波均值进行吞吐量预测；我们将100个bin用于吞吐量预测，并将100个bin用于缓冲区级别。我们还在仿真中假定能够预先知道接下来5个块的吞吐量的精确MPC算法(表示为MPC-OPT)。
RobustMPC：我们假设吞吐量下限为\(\hat{C}_{t} = \hat{C}_{t} /\left(1 + err\right)\)，其中\(\hat{C}_{t}\)是使用过去5个块的谐波均值获得的，而预测误差err是过去5个块的最大绝对百分比误差。
dash.js:
FESTIVE: a rate-based algorithm

吞吐量预测器：请注意，RB，*-MPC和FESTIVE需要良好的吞吐量预测器。在不同情况下开发好的预测器超出了本文的范围。基于先前工作的见解，我们使用最后5个块的观测吞吐量的谐波均值，因为它对每个块估计中的异常值均具有鲁棒性。

normalize QoE metrics：我们定义标准化的QoE指标如下。对于给定的吞吐量轨迹\(\{C_{t}，t\in\left[t_{1}，t_{K + 1}\right]\}\)，最优的QoE(用QoE(OPT)表示)是可以通过对整个范围内的未来吞吐量有充分了解而实现的最大QoE。它可以通过解决问题\(QOE_{-}MAX_{1}^{K}\)来计算，并提供可实现QoE的理论上限。另一方面，实际的在线算法A基于当前的吞吐量预测\(\{\hat{C}_{t}，t> t_{k}\}\)来选择比特率\(R_{k}\)。我们将算法A的在线QoE表示为QoE(A)，并将算法A的规范化QoE定义为算法A：\(\operatorname{n-QoE}(A)=\frac{\operatorname{QoE}(A)}{\operatorname{QoE}(O P T)}\)。

真实的播放器评估

敏感性分析

对于敏感性分析，我们使用定制的仿真框架评估不同的算法。与以前一样，模拟将吞吐量trace作为输入，并对视频下载/回放过程和缓冲区进行动态建模。在\(t_{k}\)时，需要知道块\(k\)的码率，仿真调用嵌入了不同算法的码率控制器来获取\(R_{k}\)。使用此框架，我们研究了这些方法对关键因素的敏感性，这些因素包括：(1)预测误差，(2)QoE函数的选择，(3)播出缓冲区大小，(4)码率级别数和(5)启动延迟。

Throughputprediction:

Users’ QoE preferences:

Buffer size and startup delay:

birate level:

MPC配置和开销

结果总结

讨论

多播放器的影响

吞吐量预测 正如其他研究人员所观察到的那样，更好的吞吐量预测可以改善蜂窝网络中的视频性能。我们工作的一个关键限制是我们没有用于吞吐量预测的准确算法，并且文献令人惊讶地稀缺且过时。未来工作的两个有趣方向是在基于其他客户的测量结果的基础上使用众包方法，并更好地理解吞吐量的可预测性和稳定性。

结论

最近围绕基于HTTP(DASH)算法的动态自适应流设计的辩论引发了我们的论文。为了给这个空间带来一些严格的要求，我们开发了控制理论问题的表述，使我们能够系统地探索设计空间，并通过定义良好的QoE指标定量评估不同类别的解决方案。凭借与现有解决方案相比更广阔的设计空间可用的关键见解，我们设计并实施了一种模型预测控制方法，以最佳地组合缓冲区占用率和吞吐量预测，从而最大程度地提高用户的QoE。我们使用dash.js参考视频播放器演示了MPC的实际实现。我们使用真实的吞吐量trace进行跟踪驱动的仿真，证实了在广泛的工作条件下，与现有技术解决方案相比的优势，而对计算和内存的需求却可以忽略不计。在未来的工作中，我们计划合并更准确的吞吐量预测，并明确捕获多播放器互动。

基于HTTP的动态自适应视频流的控制理论方法

主要内容

介绍

背景和相关工作