Rate Adaptation to Video Streaming

A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service

0x00 引言

这篇Paper讨论是一个基于buffer的视频流传输的速率调整方案。视频在互联网流量占比越来越高，这个速率调整策略也是一个研究很多的问题。adaptive bit rate selection，即ABR，播放视频的bit rate根据目前的网络情况进行自适应的调整。Buffer-Based的方式基本思路是预先下载一部分视频到一个buffer中，buffer会有一个容量。下载视频的bit rate根据buffer占有的比例来进行调整，直观的思路是如果目前buffer占用比较高的时候，就可以选择下载bit rate更高的视频，buffer占用地的时候表面目前网络速度不理想，可以选择下载bit rate更低的视频。而这里提出的思路则是在这样的基本方式上面进行的一些优化。其基本的模型如下，buffer保存的视频会根据其以秒计的视频时长来计算，每次播放的时候为播放一个unit，client下载视频的时候以chunk的粒度下载。这个chunk为固定时间长度的一段视频，在paper中这个chunk的视频长度为4s。这样同样的视频，bit rate越大，这个chunk的bytes也越多。

之前这样的根据buffer占用调整bit rate为这样的一个模型：某时刻系统的capacity，即下载视频的速度表示为C(t)，其video rate表示为R(t)，其目标是实现一段时间内这个R不要超过C，有能尽量使用更大bit rate的视频。这里使用一个chunk传输的速度来估计一个时刻的capacity，C'(t)。这里估计下载什么样bit rate的视频的时候可能还要考虑到buffer的占用，这个adjustment factor表示为F(B(t))，即根据buffer占用加上一个调整的参数。通过这样的选择video rate表示为R(t) = F(B(t))C'(t)。如果目前的网络是足够的，可以选择R(t) = C'(t)这样bit rate的视频。
在一个时刻网络不够用的情况下，最好是在目前的chunks被播放完成之前，后面的chunk就被下载下来了。paper中先距离一个简单的例子，如果目前buffer里面只有一个chunk，这样就要去VR(t)/C(t) < B(t),这里使用VR(t)表示下载的chunk大小，in bytes(VR(t) = R(t) * V, 每个chunk为V秒长度)。B(t)即表示目前buffer里面的还能个播放的时间。即要求R(t) < (B(t)/V)*C(t)，这个有前面式子变换话速率的表示而来。又根据前面F(B(t))和R(t), C’(t)的关系，可以得出F(B(t)) < (B(t)/V)(C(t)/C'(t))，这个要求对于所有t都成立。这样如果C(t)/C’(t)由于网络速度变化大，造成这个比值很小的话，这样选择的F(-)只能选择很小的一个值，从而导致有C’(t)选择R(t)的时候作出选择很低bit rate的视频的决策。

0x01 基本思路

Paper这里就分析了根据前面的方法，由于网络的波动很容易造成选择的bit rate不合适。这里提出的最初始版本的方法将buffer占用分为了几个阶段：reservoir阶段考虑到chunk离散的，而且完整下载下来之后才能使用，最好buffer里面一直有一个chunk。即reservoir类似于一个起步阶段，这个阶段选择bit rate最小的视频；在这个阶段之后，是根据buffer占用选择不同bit rate的vedio，这个阶段称之为cushion阶段。达到一点的点之后，就是upper reservoir阶段，buffer占用在这个阶段的时候会选择bit rate最大的视频。考虑到下载一个chunk之后开始之后，不能中途改变其bit rate，如果网络速度的突然下降可能导致下载一个chunk的过程中这个buffer被耗尽。解决这个问题的方法是尽量保持buffer占用在r以上，所以根据f(B)选择bit rate的时候，定义f(B) 操作的一个safe area，当C(t)能满足一直大于R-min的时候，能保证在buffer占用大于r，基本保证V f(B)/Rmin ≤ (B − r)成立。

在这样的基本思路之上，在paper中描述的实际应用的环境中，buffer的大小为240s长的视频，reservoir设置为一个固定的比较长的长度，长90s。Bm的点设置为buffer占用为90% 的点，这样cushion在基本的算法上为126s。在cushion之间，Video Rate的选择根据buffer占用和video rate之间的一个映射，这里使用线性映射的方式，f(B)在这里是一个分段线性函数。这个映射称之为rate map，rate map是一个连续的函数，但是可续的bit rate是离散的几个值。算法表示如下，即在前面的几个区域划分的基础上，选择目前能选择的最大的bit rate。这样根据前一个video rate，目前的buffer占用，reservoir和cushion的大小选择下一个video rate的时候，B_i到B_i+1之间的距离可以用来缓解在不同的video rate之间的切换。前面的算法记为BBA-0，测试中显示这个算法能够实现更少的video rate切换，但是导致倾向于选择更低的video rate。

Input: 
	Rate-prev: The previously used video rate 
	Buf-now: The current buffer occupancy 
	r: The size of reservoir
	cu: The size of cushion
Output: 
	Rate-next : The next video rate
if Rate-prev = Rmax then 
	Rate+ = Rmax
else
	Rate+ = min{Ri : Ri > Rate-prev}

if Rateprev = Rmin then 
	Rate− = Rmin
else
	Rate− = max{Ri : Ri < Rate-prev}
if Buf-now ≤ r then 
	Rate-next = Rmin
else if Buf-now ≥ (r + cu) then 
	Rate-next = Rmax
else if f(Buf-now) ≥ Rate+ then
	Rate-next = max{Ri : Ri < f(Buf-now)};
else if f(Buf-now) ≤ Rate− then 
	Rate-next = min{Ri : Ri > f(Buf-now)};
else
	Rate-next = Rate-prev; 
return Rate-next;

目前很多视频使用的都是variable bitrate (VBR)编码的方式，这样的编码方式对于不同的视频场景会使用不同的bit rate来编码。这样的编码方式下，不同的chunk的大小差别会比较大。这里使用r[k]下载第k个chunk选择的video rate，使用c[k]表示下载这个chunk的时候的速度。选择video rate为r的视频的时候，第k个chunk的大小使用 Chunk[r][k]表示。每个chunk的视频长度还是V seconds。下载完成这样一个chunk需要的时长就是 Chunk[r][k]/c[k] seconds。假设c[k] = R-min, reservoir阶段的处理可以根据下载这个编码之后占用空间大的需要了比播放这个chunk更多的时间，和下载这个编码之后占用空间更小的chunk比播放这个chunk需要的少的时间加起来，来动态调整需要的reservoir。这里记这个每个计算多了的和少了的这个长度为X秒，paper中的数值设置为2倍buffer的大小。看起来类似于统计了一段时间内这个chunk的平均大小。另外的rate map的映射也不再是直接一个映射，而是需要通过chunk map来得到。Chunk轴表示的是对应video rate的平均chunk size。也就是说这里主要考虑到的是chunk大小，而不是BBA-1的rate。

前面的方法在启动阶段的策略都是从video rate最新的视频开始，随着buffer占用提升逐渐下载video rate更大的。这样的方式显得有点保守。这里参考了TCP中慢启动的一些做法，TCP在启动阶段使用比较激进的增长策略来尽快发送系统能够达到的发送速度。而这里提出的BBA-2的方法机遇这样的观察：buffer占用的变化，∆B = V − (ChunkSize/c[k])，即播放的和下载的之间的差值。对于当前适合video rate为R-i时，可以增加到R-{i+1}要求∆B ≥ V − (ChunkSize/R_{i+1})。在buffer为空的情况下，要求 V − (ChunkSize/(e*R_{i+1}))能被满足。在使用VBR方式编码的时候，设编码的max-to-average ratio为e，根据paper中的数据，这个e为2。这个意味着一般的chunk小于平均大小。BBA-2启动的时候选择video rate次高的，如果∆B增加超过了0.875V seconds，这样意味着这个视频下载的速度时播放的8倍。在启动阶段，BBA-2算法只在下载速度是播放的8倍以上时，才会继续增加video rate。在将要加满cushion阶段的buffer，BBA-2则会在2倍的时候增加video rate，而从启动阶段到cushion阶段的末尾，这个增加的阈值时线性变化的。在buffer占用减少或者是根据chunk map计算出video rate可以增加时候，这个根据∆B调整的方法的结果不会被使用。另外paper中还描述了一些实用性的优化：

Buffer-Based的方法在网络速度大于R-min的要求的时候，播放视频不会被卡顿。但是实际中可能有短时的网络问题。这里的方法是通过预留出一部分buffer，使得buffer的占用更高。来容忍一些temporary network outage。这个称之为outage protection。分配多少的buffer用于outage proaction，在BBA-1中的方法是在buffer增长且占用小于75%的时候，每下载一个增加400ms的时间。在BBA-2中是在startup阶段预留出一些时长视频的方式，
```
In the implementation of BBA-2, we only accumulate outage protection after the algorithm exits the startup phase and is using the chunk map algorithm. A typical amount of outage protection is 20–40 seconds at steady state and is bounded at 80 seconds. The downside of this approach is that the chunk map keeps moving, and can cause video rates to oscillate.
```
另外的一个优化是减少video rate的切换。前面的方法导致video rate切换的几个原因有：使用chunk map的方式使得没有buffer占用率到video rate的固定映射，而是buffer占用映射到一个chunk size上。加上使用VBA编码，即使buffer占用不变也可能导致每次请求不同的video rate。避免那些这样导致的video rate切换到另外一个，马上有切回来的情况，可以通过在一些情况下不去切换的方式，比如一个小chunk后面是一个大chunk时候，通过chunk map的方式得出可以增加rate时也不去增加。这个改进通过look ahead后面的一些chunks(buffer中同样chunks数量的chunks，or buffer空的时候look ahead下一个，or buffer满的时候look ahead后面60个)。这种策略只在chunk map得出增加video rate结论的时候使用，而减小video rate的情况下避免卡顿就不适用。

emmmm，不是很熟悉方向的总结。

0x02 评估

这里的具体性能可以参考[1].

参考

A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service, SIGCOMM ‘14.
A Control-Theoretic Approach for Dynamic Adaptive Video Streaming over HTTP, SIGCOMM ‘15.