您现在的位置是:首页 >其他 >BOLA (INFOCOM ‘16) ABR算法阅读笔记网站首页其他

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

Green Lv 2023-07-14 00:00:02
简介BOLA (INFOCOM ‘16) ABR算法阅读笔记

前言

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

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

描述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算法1;引入了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。

概述

BOLA的目标

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

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

(1) 提高视频质量

在一个视频会话中,平均视频质量的效用为 v ˉ N ar{v}_N 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) ag{4} ar{v}_N riangleqfrac{mathbb{E}{sum_{k=1}^{K_N}sum_{m=1}^{M}a_m(t_k)v_m}}{mathbb{E}{T_{end}}} vˉNE{Tend}E{k=1KNm=1Mam(tk)vm}(4)

其中:

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

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

(2) 减少卡顿时间

在一个视频会话中,平均不卡顿(流畅播放)的效用为 s ˉ N ar{s}_N 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) ag{5} ar{s}_N riangleqfrac{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ˉNE{Tend}Np=E{Tend}E{k=1KNm=1Mam(tk)p}(5)

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

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

效用最大化

BOLA效用最大化的目标即最大化下式,表示提升视频质量的同时减少卡顿时间:
v ˉ N + γ s ˉ N ar{v}_N+gamma ar{s}_N vˉN+γ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)的逻辑3

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基于李雅普诺夫方法,将最大化 v ˉ N + γ s ˉ N ar{v}_N+gamma ar{s}_N vˉN+γsˉN转为:

最大化 ∑ m = 1 M a m ( t k ) ( v m + γ p ) sum_{m=1}^{M}a_m(t_k)(v_m+gamma p) m=1Mam(tk)(vm+γp)的同时最小化 Q ( t k ) Q(t_k) Q(tk),联合起来表征为式(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) ag{9} max quadfrac{sum_{m=1}^{M}a_m(t_k)(Vv_m+Vgamma p-Q(t_k))}{sum_{m=1}^{M}a_m(t_k)S_m} \ s.t.quadsum_{m=1}^{M}a_m(t_k)leq1,a_m(t_k)in{0,1} maxm=1Mam(tk)Smm=1Mam(tk)(Vvm+pQ(tk))s.t.m=1Mam(tk)1,am(tk){0,1}(9)

其中:

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

具体而言,式(9)有两个分支:

  • 当buffer水平足够高时,即 Q ( t k ) > V ( v m + γ p ) Q(t_k)>V(v_m+gamma p) Q(tk)>V(vm+γp)时,BOLA在该时隙中不请求视频块
    • 注意:BOLA会涉及视频块的请求控制4
  • 否则,BOLA求解 ( V v m + V γ p − Q ( t k ) ) / S m (Vv_m+Vgamma p-Q(t_k))/S_m (Vvm+pQ(tk))/Sm的最大值,为下一视频块选择码率
    • 此式为BOLA的核心ABR算法,包含两个参数 V V V γ gamma γ

效用计算

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

因此,为了体现码率对于视频质量带来的非线性效用提升,BOLA选择对数函数(以e为底)作为码率的效用函数5,其形式为:

v m = l n S m S M v_m=ln frac{S_m}{S_M} vm=lnSMSm

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

决策示例

当BOLA-BASIC的两个参数的取值为 γ = 5.0 / p gamma = 5.0/p γ=5.0/p V = 0.93 V = 0.93 V=0.93时,其每个码率级别对应的 ( V v m + V γ p − Q ( t k ) ) / S m (Vv_m+Vgamma p-Q(t_k))/S_m (Vvm+pQ(tk))/Sm的数值随buffer大小(buffer内视频块数量)的变化如下图所示:
image.png
可以看出,每个码率在不同buffer下对应一条直线,而两条直线的交点对应的buffer大小,则表示切换码率的buffer阈值。因此BOLA-BASIC的决策函数类似于阶梯状,如下图所示:image.png
作为对比,同为buffer-based方法的BBA (SIGCOMM '14)的决策函数完全是线性的:
image.png

参数设置

  • γ gamma γ:控制避免卡顿的权重,在BOLA文章中经常设置为 γ = 5.0 / p gamma = 5.0/p γ=5.0/p
  • V V V:给定buffer能容纳的视频块最大数量(表征最大buffer大小) Q m a x Q_{max} Qmax,有 V = ( Q m a x − 1 ) / ( v 1 + γ p ) V=(Q_{max}-1)/(v_1+gamma p) V=(Qmax1)/(v1+γp)
    • 注意: v 1 v_1 v1表示最高码率级别的效用

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

BOLA-FINITE

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

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

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)。
image.png


  1. 参见:dash.js的ABR逻辑 ↩︎ ↩︎

  2. MPC (SIGCOMM '15)给出的经典QoE线性公式中,同时考虑了视频质量、卡顿时间和视频质量切换(以及启动时延) ↩︎

  3. dash.js中视频块的请求与放弃请求逻辑,可参见:dash.js (v4.1.0) 的请求&放弃请求逻辑,不过其实现可能与BOLA的论文描述存在一些差异 ↩︎ ↩︎

  4. 缓存的视频块数量不能超过一定的阈值,否则播放器会通过播放视频来消耗buffer,直到buffer低于阈值后再请求新的视频块,这也被称为视频流的ON-OFF行为。在dash.js中,对于10min以内的视频,这个阈值最大为30s,否则为60s ↩︎

  5. 学术界对于如何建模及衡量视频质量已有广泛的研究,常用的指标包括:PSNR、SSIM、VMAF、ITU-T P.1203等,可参见:DASH标准&ABR算法介绍 ↩︎

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。