BOLA (INFOCOM ‘16) ABR算法阅读笔记

前言

BOLA（Buffer Occupancy based Lyapunov Algorithm）是一种经典的基于播放缓冲区的（Buffer-based）ABR（自适应码率）算法，并且其改进版本是如今dash.js开源播放器的默认ABR算法¹。

BOLA算法基于李雅普诺夫（Lyapunov）优化方法设计，将ABR算法视作效用最大化问题，其效用通过提高视频质量和减少卡顿时间来提升。鉴于其初版论文包含了大量理论推导和公式建模，没有相关背景的人可能不易读懂，故本文可以作为便于理解的参考资料。至于BOLA在dash.js中的代码实现，可参考：BOLA dash.js代码实现。

描述BOLA的论文有以下五篇，本文仅关注第一篇INFOCOM '16初版论文：

1. BOLA: Near-optimal bitrate adaptation for online videos (INFOCOM '16) ：BOLA的初版论文，对其建模和算法进行了详细描述，包含四种不同的版本（BOLA-BASIC、BOLA-FINITE、BOLA-O、BOLA-U），其中BOLA-O为2018年以前dash.js的默认BOLA算法。
2. BOLA: Near-Optimal Bitrate Adaptation for Online Videos (TON '20)：INFOCOM '16论文的期刊扩展版。
3. From theory to practice: improving bitrate adaptation in the DASH reference player (MMSys '18)：提出了BOLA的改进版本BOLA-E，引入占位符（placeholder）来解决缓冲区不足时的决策问题；将BOLA-E和基于吞吐量的（Rate-based）算法结合成为DYNAMIC，是如今dash.js的默认ABR算法¹；引入了FAST SWITCHING算法，将低码率的视频块替换为高码率视频块。
4. From Theory to Practice: Improving Bitrate Adaptation in the DASH Reference Player (TOMM '20)：MMSys '18论文的期刊扩展版。
5. Implementing BOLA-BASIC on Puffer: Lessons for the use of SSIM in ABR logic：在Puffer平台 (NSDI '20)上实现BOLA-BASIC的经验，将其衡量视频质量的效用函数替换为SSIM。

系列博文索引：

• DASH标准&ABR算法介绍
• dash.js的ABR逻辑
• ABR算法研究综述阅读笔记
• 经典ABR算法介绍：FESTIVE (CoNEXT '12) 论文阅读笔记
• 经典ABR算法介绍：BBA (SIGCOMM ’14) 设计与代码实现
• 经典ABR算法介绍：BOLA (INFOCOM '16) 核心算法逻辑
• 经典ABR算法介绍：BOLA (INFOCOM '16) dash.js代码实现
• 经典ABR算法介绍：Pensieve (SIGCOMM ‘17) 原理及训练指南

概述

BOLA的目标

BOLA的总体目标是最大化（平均）效用，其效用定义分为两部分：(1) 提高视频质量，(2) 减少卡顿时间

• 注意：BOLA的效用定义中并不包含减少视频质量的切换²，其在BOLA-O中针对此项进行单独优化，详见下文
• *BOLA的效用公式并不重要，其核心算法非常简单（见下文的BOLA-BASIC），所以这部分看不懂也可以略过

(1) 提高视频质量

在一个视频会话中，平均视频质量的效用为${\bar{v}}_N$，其效用公式为论文的式(4)，即：
v ˉ N ≜ E { ∑ k = 1 K N ∑ m = 1 M a m ( t k ) v m } E { T e n d } (4) \tag{4} \bar{v}_N\triangleq\frac{\mathbb{E}\{\sum_{k=1}^{K_N}\sum_{m=1}^{M}a_m(t_k)v_m\}}{\mathbb{E}\{T_{end}\}} vˉN​≜E{Tend​}E{∑k=1KN​​∑m=1M​am​(tk​)vm​}​(4)

其中：

• $N$：该会话中视频块总数量
• $M$：码率级别，注意1表示最高码率级别，$M$表示最低码率级别
• $v_m$：目标码率级别$m$的效用，下文给出定义，注意视频码率越高，视频块越大，效用越高（式(1)）
• $a_m(t_k)$：BOLA将视频会话划分为若干个时隙，则$a_m(t_k)$表示在第$k$个时隙内的播放器请求行为
  • 若播放器在该时隙内请求视频块，则$a_m(t_k)=1$，且该时隙时长等于该视频块的下载时间
  • 若播放器在该时隙内不请求视频块（仅播放），则$a_m(t_k)=0$，且该时隙时长为固定值$\Delta$
• $T_{end}$：该会话持续总时长（这个不重要）

这个公式的形式看起来复杂，但其含义非常简单：分母为整个会话的持续时间，分子表示整个会话中视频质量的效用之和（可以简单理解为视频块码率之和，但并不是），因此整个公式就是计算平均视频质量（效用）。

(2) 减少卡顿时间

在一个视频会话中，平均不卡顿（流畅播放）的效用为${\bar{s}}_N$，其效用公式为论文的式(5)，即：
s ˉ N ≜ N p E { T e n d } = E { ∑ k = 1 K N ∑ m = 1 M a m ( t k ) p } E { T e n d } (5) \tag{5} \bar{s}_N\triangleq\frac{Np}{\mathbb{E}\{T_{end}\}}=\frac{\mathbb{E}\{\sum_{k=1}^{K_N}\sum_{m=1}^{M}a_m(t_k)p\}}{\mathbb{E}\{T_{end}\}} sˉN​≜E{Tend​}Np​=E{Tend​}E{∑k=1KN​​∑m=1M​am​(tk​)p}​(5)

其中，$p$表示每个视频块的时长。因此，该公式表示的是视频播放总时长占会话总时长的比例，在完全没有任何卡顿发生的情况下，${\bar{s}}_N$最大为1。

• 注意：与MPC (SIGCOMM '15)不同，BOLA并没有对卡顿时间的计算进行建模，而是通过对视频块的总播放时间来表征不卡顿的总时间
• 式(4)和(5)的具体形式不重要，重要的是二者的差异，即分子中的$v_m$与$p$

效用最大化

BOLA效用最大化的目标即最大化下式，表示提升视频质量的同时减少卡顿时间：
$${\bar{v}}_N+\gamma {\bar{s}}_N$$

其中，$\gamma$为调整参数，类似于MPC的QoE公式中的卡顿项系数，不过取值有所不同。

BOLA的四个版本

BOLA总共有四个版本：

• BOLA-BASIC：基础版本，假设视频块数量N趋近于无穷大
• BOLA-FINITE：在BOLA-BASIC的基础上，考虑了有限视频长度的情形
• BOLA-O：在BOLA-FINITE的基础上，尽可能避免码率切换（Oscillations）
• BOLA-U：在BOLA-FINITE的基础上，尽可能保持效用（Utility）

注意，BOLA实际上不止是ABR算法，其还包括了视频请求控制（基于时隙）与放弃请求（BOLA-FINITE）的逻辑³。

BOLA-BASIC【关键】

BOLA-BASIC是最基本的BOLA版本，也体现了BOLA的核心算法，是其他三个版本的基础。

*简便起见，本文仅叙述BOLA的直观设计理念，略去其理论推导的部分。若对其基础理论有兴趣，可以参考原论文及其引用文献[17]：M. J. Neely, Stochastic network optimization with application to communication and queueing systems. Morgan & Claypool, 2010

核心算法

略去一些列理论分析与简化（§III.A），BOLA-BASIC基于李雅普诺夫方法，将最大化${\bar{v}}_N+\gamma {\bar{s}}_N$转为：

最大化${\sum }_{m=1}^M{a}_m(t_k)(v_m+\gamma p)$的同时最小化$Q(t_k)$，联合起来表征为式(9)：
max ⁡ ∑ m = 1 M a m ( t k ) ( V v m + V γ p − Q ( t k ) ) ∑ m = 1 M a m ( t k ) S m s . t . ∑ m = 1 M a m ( t k ) ≤ 1 , a m ( t k ) ∈ { 0 , 1 } (9) \tag{9} \max \quad\frac{\sum_{m=1}^{M}a_m(t_k)(Vv_m+V\gamma p-Q(t_k))}{\sum_{m=1}^{M}a_m(t_k)S_m} \\ s.t.\quad\sum_{m=1}^{M}a_m(t_k)\leq1,a_m(t_k)\in\{0,1\} max∑m=1M​am​(tk​)Sm​∑m=1M​am​(tk​)(Vvm​+Vγp−Q(tk​))​s.t.m=1∑M​am​(tk​)≤1,am​(tk​)∈{0,1}(9)

其中：

• $V$：调整参数（与最大buffer时长有关）
• $Q(t_k)$：$t_k$时刻（时隙$k$开始时）buffer中的视频块数量（表征缓冲时长）
• $S_m$：$m$级别码率对应的视频块大小

具体而言，式(9)有两个分支：

• 当buffer水平足够高时，即$Q(t_k)>V(v_m+\gamma p)$时，BOLA在该时隙中不请求视频块
  • 注意：BOLA会涉及视频块的请求控制⁴
• 否则，BOLA求解$(V{v}_m+V\gamma p-Q(t_k))/S_m$的最大值，为下一视频块选择码率
  • 此式为BOLA的核心ABR算法，包含两个参数$V$和$\gamma$

效用计算

BOLA认为每个码率对应的效用函数是一个收益递减（diminishing returns）的凹（concave）函数。
直观上来说，码率的提升带来的QoE提升并非线性，而是会收益递减。举例而言，2K相对于1080p的画质提升，很可能不如720p相对于480p的画质提升大。

因此，为了体现码率对于视频质量带来的非线性效用提升，BOLA选择对数函数（以e为底）作为码率的效用函数⁵，其形式为：

$$v_m=ln\frac{S_m}{S_M}$$

其中，$M$表示最低码率的级别，因此某档码率的效用为其码率与最低码率的比值的自然对数。

决策示例

当BOLA-BASIC的两个参数的取值为$\gamma =5.0/p$和$V=0.93$时，其每个码率级别对应的$(V{v}_m+V\gamma p-Q(t_k))/S_m$的数值随buffer大小（buffer内视频块数量）的变化如下图所示：

可以看出，每个码率在不同buffer下对应一条直线，而两条直线的交点对应的buffer大小，则表示切换码率的buffer阈值。因此BOLA-BASIC的决策函数类似于阶梯状，如下图所示：

作为对比，同为buffer-based方法的BBA (SIGCOMM '14)的决策函数完全是线性的：

参数设置

• $\gamma$：控制避免卡顿的权重，在BOLA文章中经常设置为$\gamma =5.0/p$
• $V$：给定buffer能容纳的视频块最大数量（表征最大buffer大小）$Q_{max}$，有$V=(Q_{max}-1)/(v_1+\gamma p)$
  • 注意：$v_1$表示最高码率级别的效用

如果需要指定一个阈值（类似于BBA的reservoir），使得当buffer低于该阈值时持续选择最低码率，则可以通过计算相应的$\gamma$和$V$实现。

BOLA-FINITE

BOLA-BASIC假设了一个无穷大的视频长度（视频块数量），但这对于真实视频而言显然是不成立的。因此，作者提出BOLA-FINITE作为对于较短视频的改进版本，其与BOLA-BASIC的差异在于以下两个方面：

• 动态调整$V$的取值，以避免buffer过多或者过少：$V^D=(Q_{max}^D-1)/(v_1+\gamma p)$
  • 其中，最大buffer大小$Q_{max}^D$也是动态的（*论文似乎没说怎么实现，不过在dash.js中，这个值会随着视频总时长和码率级别进行调整）
• 放弃下载：当所选码率过高而网络突然变差，无法在短时间内完成下载时，BOLA-FINITE会考虑放弃当前视频块下载并重新请求更低码率的视频块³

BOLA-O & BOLA-U

尽管BOLA-FINITE可以应用于较短的视频上，但鉴于BOLA所优化的效用仅包括视频质量和卡顿，并不包括质量切换，所以BOLA-FINITE可能会产生频繁的码率切换。为了减少码率切换，作者在BOLA-FINITE的基础上提出了两个版本：BOLA-O和BOLA-U。

对于BOLA-FINITE而言，码率切换由以下三方面原因触发：

1. 带宽变化：BOLA-FINITE为了适应网络变化，会调整码率决策，这种情况下引起的码率切换不必调整
2. 密集的buffer阈值：当buffer上限过低时，选择不同码率的对应的buffer阈值可能太过密集（如间隙小于1个视频块时长），则会导致buffer在多个阈值上剧烈变化（*BBA也有这种情况）
3. 离散码率的影响：码率级别不是连续的而是离散的，当网络带宽刚好处于两个码率之间，则BOLA-FINITE可能会在这两档码率间反复切换，因为平均buffer是会稳定在某个数值附近

在第3种情况下，依据用户的不同偏好，有两种不同的选择，对应两个BOLA的版本：

• BOLA-O（oscillations）：处理第2、3类切换，倾向于选择较低的码率以避免码率切换（需要将所选码率与吞吐量进行比较），但会牺牲部分效用
  • BOLA-O会比较码率和吞吐量，不过伪代码写了一堆if-else判断，具体逻辑就不展开分析了
  • BOLA-O选择低码率会导致buffer增长比较快，因此BOLA-O会通过延迟请求（等待buffer下降）来缓解这个问题
• BOLA-U（utility）：仅处理第2类切换（不处理第3类），倾向于选择较高的码率以最大化效用

具体机制可以结合论文和伪代码（图4）一起看。从理论和实验结果上来看，BOLA-O避免码率切换的效果更好，但BOLA-U的效用更高（也高于BOLA-FINITE）。

到了这里，关于BOLA (INFOCOM ‘16) ABR算法阅读笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！