一种基于多服务器的DASH客户端优化算法

吴如亮,王子磊,奚宏生

(中国科学技术大学 自动化系,合肥 230027)

0 概述

近年来,一种称之为HAS(HTTP Adaptive Streaming)的流媒体传输标准出现,并且很快变成了流媒体传输的主要方式。据Cisco[1]估计,到2019年视频流量将占据互联网数据传输总流量的80%,网络运营商也试图寻找新的方式以更好地利用网络容量。2011年,MPEG结合3GPP开发出一套标准化的解决方案——基于HTTP的动态自适应流媒体(Dynamic Adaptive Streaming over HTTP,DASH)[2]。在DASH标准中,原视频被分割成2 s～10 s的视频分片并以不同的码率等级进行编码,生成的分片存储在服务器上,客户端则根据网络状况及自身状态动态调整请求的视频质量。随着业务规模的扩大,DASH服务模式开始从单服务器向多服务器转变。多服务器能够提供更大的带宽,传输路径更加多样化,服务质量也更加可靠。但是,由于服务器间的带宽差异,如何减少客户端视频码率的频繁波动,保证客户端体验质量(Quality of Experience,QoE),仍是一个挑战。

相关算法[3]已被提出用来解决单服务器场景下的质量波动问题。现有多服务器场景下DASH客户端方法主要是在最大化带宽利用率的前提下,提高客户端视频质量,但是往往忽视了视频质量频繁波动的问题。文献[4]为了优化多个服务器间的资源分配问题和提高客户端视频质量,提出了一种协同多尺度调度算法,该算法能够平衡服务器负载,优化整体视频质量。文献[5]针对多服务器场景下的公平、效率和稳定性问题,提出了一种新的协议Presto,提高了用户体验质量。上述优化方法均是在传统网络下进行,由于视频下载的间歇性,客户端对带宽的估计往往不准确。近年来,软件定义网络(Software-Defined Network,SDN)出现,由于其集中控制机制及其在网络资源调度和网络状态监测等方面的智能性和灵活性,在流媒体视频领域越来越受欢迎[6]。文献[7]提出了一种OpenFlow协助下的QoE优化框架,减少了客户端和SDN控制器间的频繁通信,能够有效分配网络资源,但因其请求模式是单服务器,并没有解决多服务器场景下的质量波动问题。

针对上述问题,本文提出一种多服务器场景下基于SDN的视频分片请求调度算法。该算法将多个分片组成一个视频块,并把这多个分片分配至多个服务器,利用这种以视频块为单位的调度策略实现同一视频块内视频分片的码率同步,减少视频质量的波动。同时,在客户端通过使用Q学习训练码率决策矩阵,当新的分片请求到达时,通过查询该矩阵找到当前状态下Q值最大的动作作为最优码率。

1 基于SDN的DASH系统框架

1.1 问题描述

动态自适应码率切换算法是当前DASH技术研究的一个热点。但是目前很多算法[4-5,8]是纯客户端驱动,即仅仅依赖客户端及其获悉的网络状态来动态调整视频比特率,可能由于带宽估计不准确导致客户端频繁切换视频比特率,影响客户端QoE。

在DASH多服务器场景下,客户端同时向多个服务器发起视频分片请求。但是由于客户端到各个服务器的带宽多样性,可能会出现分片失序到达的情况,此时若缓冲区耗尽,则视频播放会中断,从而引入不必要的时延。文献[9]为解决并行多服务器下视频块顺序下载的问题,提出一种概率分片调度方法,该方法根据时变带宽概率模型,估计在视频缓冲区耗尽之前视频分片成功下载的概率来优化视频传输。此外,由于多个服务器间服务带宽的差异性,往往会导致视频质量的频繁波动。文献[8]针对多个服务器服务能力的动态变化的情况,提出一种动态服务器选取策略来协助客户端选择服务能力最优的视频传输服务器,解决了传统DASH自适应策略仅选取视频码率的问题。这种方案在网络状况较好时每次都能请求最高的视频码率,但在网络环境较差的情况下,视频质量仍然会出现频繁波动的情况。

以上研究对DASH多服务器场景下的分片失序到达、视频质量波动等问题做出了一定的改善,但是由于传统网络的限制,不能从全局角度对系统进行优化,同时,带宽大多是基于预测手段获取,往往存在偏差,制约了优化效果。

本文研究内容可以描述为:在SDN网络中,客户端同时发起多个视频分片请求,分片调度算法将多个请求分配至多个服务器,以减少客户端视频质量的波动,同时客户端采用Q学习算法决策视频码率,为用户提供更佳的QoE。

1.2 系统模型

OpenFlow[10]网络中的动态自适应视频播放系统模型如图1所示。整个系统由视频服务器、Web代理服务器、视频客户端、OpenFlow控制器及交换机组成。其中:视频服务器负责向视频客户端提供视频服务;Web代理服务器负责将用户的视频分片请求以及将请求下发给OpenFlow控制器;视频客户端是视频请求的发起者;OpenFlow控制器负责分片调度算法的决策,负责控制视频分片请求的下发;OpenFlow交换机负责根据流表完成数据的转发。

图1 DASH系统模型

本文的工作是设计视频分片请求调度算法和客户端码率决策算法。整个视频请求过程可以描述为:首先客户端向Web代理服务器发起视频请求,代理服务器将此请求转发至控制器,控制器根据收集的各个服务器带宽信息,执行分片调度算法,决策出需要请求的分片数及服务器数,并通过OpenFlow协议与交换机进行指令下发和信息收集;然后客户端根据Q学习算法决策出要请求的视频码率,根据控制器下发的指令开始向视频服务器发起视频传输请求。视频块请求分配示意图如图2所示。把多个视频分片组成一个视频块,每次对一块视频进行调度,下文将给出调度策略的具体描述。

图2 视频块请求分配示意图

2 视频分片调度策略

视频分片调度策略首先动态选择视频块的长度(分片个数)及所请求的服务器;然后采用视频分片请求调度算法将各个分片请求分配至多个服务器。

2.1 视频块长度及服务器选取算法

多服务器请求模式为:一个客户端同时向多个服务器发起多个视频分片的请求,服务器分配的请求分片数与服务器可用带宽成正比,这样确保了多个服务器完成下载的时间几乎是同步的。但是随着时间的变化,服务带宽也在变化,同一视频块内的各个分片可能无法以预定同步的时间完成下载。因此,设置了视频块长度的上限阈值Nmax。同时,将带宽最小的服务器分配一个分片,其他服务器按照此带宽成比例依次分配视频分片数。

假设存储客户端请求视频的服务器有S个,第i个服务器可用带宽为ci,降序排列使得c1≥c2≥…≥cS。令Sk表示请求第k块视频所用服务器数,显然Sk≤S。将第k块视频包含的分片数记为Nk。下面将详细描述视频块长度Nk及服务器个数Sk的选取过程。

算法1视频块长度及服务器选取算法

输入视频服务器个数S,各服务器可用带宽c={c1,c2,…,cS}

输出视频块长度Nk,服务器个数Sk

1.Initialize:

2.Sk←S

3.while TRUE do

4.nSk←1;

5.for i←1 to Sk-1 do

6.ni=⎣ci/cSk」;

7.end for

9.if Nk>Nmaxthen

10.Sk←Sk-1

11.else

12.return Nk,Sk;

13.end if

14.end while

对算法1的解释如下:

算法第1行～第2行:算法开始时获取各个服务器可用带宽集合{c1,c2,…,cS},并初始化本次请求所用服务器数目Sk为S。

算法第9行～第14行:判断分片总数Nk是否大于视频块长度的上限阈值Nmax。若Nk小于等于Nmax,返回视频块长度Nk和服务器个数Sk,程序结束;否则,若Nk大于Nmax,舍弃带宽最小的服务器,更新可用服务器数目Sk为Sk-1,程序跳转到第3行继续执行。

2.2 视频分片请求调度算法

确定视频块长度Nk和服务器个数Sk后,下一步的目标是将Nk个视频分片合理分配至Sk个服务器,使得分片下载时间最短。

综上所述,以服务器分配矩阵A作为决策变量,视频分片请求的调度模型为:

Subject to:

aij∈{0,1},i=1,2,…,Nk,j=1,2,…,Sk

t(n)

上述优化问题是一个NP难问题,无法直接使用凸优化理论进行求解,本文在此给出了启发式算法。求解时,借助于贪心算法的思想,对矩阵A逐行求解,将分片从前往后依次分配给各个服务器,分配策略如算法2所示。

算法2视频分片请求调度算法

输入请求分片数Nk,服务器数Sk,各服务器可用带宽c={c1,c2,…,cSk}

输出服务器分配矩阵A

1.Initialize:

2.A←0

3.for i←1 to Nkdo

5.aij*=1;

6.end for

7.return A;

对算法2的解释如下:

算法开始时获取算法1 的输出结果,即视频块长度Nk、服务器数Sk,将其作为本算法的输入,同时将服务器可用带宽c={c1,c2,…,cSk}作为算法的输入。

算法第2行:初始化分片分配矩阵A=0,开始对Nk个视频分片进行分配。

算法第7行:当Nk个视频分片分配完成之后,返回分片分配矩阵A。

3 基于Q学习的客户端算法

当DASH客户端请求视频时,由于视频码率的多样性,往往需要一个客户端算法对视频码率进行决策。本文采用Q学习算法作为客户端码率决策算法[11-12]。

3.1 基于Q学习的决策

Q学习是强化学习[13]的一个分支,它需要解决如下问题:一个能够感知环境的自治智能体,根据当前的环境状态,通过学习选择一个最优动作,使得智能体获取的回报值最大。

基于Q学习,客户端码率选取过程为:根据环境状态(带宽、客户端缓冲区和视频码率等),采取某一动作(选择视频码率),使得回报值(QoE)最大。式(1)给出了智能体在状态s下,采取动作a获取回报值r时Q值的更新方式。其中,(s,a)是状态-动作对,α∈[0,1]是学习速率,表示新获取信息覆盖旧信息的程度,α越大保留之前训练的效果就越少;γ∈[0,1]是折扣因子,决定了对未来回报的重视程度。

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′,a′)]

(1)

基于学习到的Q值可选择要请求的码率。在DASH系统中,需要为每个动作a分配一个回报值r用来更新学习Q,其中,回报值r是通过回报函数来确定的,下面将给出回报函数的定义。

3.2 回报函数

客户端算法的优化目标是最大化QoE,因此,本文定义的回报函数是QoE的一种度量,主要包括3个方面[14]:1)视频质量等级;2)视频质量波动;3)缓冲区下溢。下面分别介绍这三方面对应的回报函数。

3.2.1 视频质量等级

文献[15]表明客观PSNR值和主观平均意见得分(MOS)之间存在类似线性的关系。因此,本文建立的视频质量等级对应的回报函数Rquality为一个线性函数,见式(2)。其中,视频有L个质量等级,QLi表示请求第i个分片的质量等级,且QLi

Rquality=-(QLL-QLi)

(2)

3.2.2 视频质量波动

在DASH系统中,由于带宽的波动,请求的视频质量等级会随之变化,导致视频质量发生波动,影响用户体验质量。本文建立了质量波动对应的回报函数Roscillation为波动值的线性函数,见式(3)。当无波动发生时,回报为0;当有波动时,波动越大回报越小。

Roscillation=-|QLi+1-QLi|

(3)

3.2.3 缓冲区下溢

缓冲区下溢导致视频播放中断是影响QoE的第3个方面,因此,缓冲区下溢也成为回报函数的一个组成部分。当客户端缓冲区耗尽时,视频播放中断,重缓冲事件发生。定义回报函数时,本文考虑根据缓冲区长度大小,将缓冲区下溢对应的回报函数分段定义。当缓冲区长度Bi低于缓冲区总长度Bmax的10%时,给予-100的惩罚;否则,将回报函数定义为一个线性函数,见式(4)。

(4)

3.2.4 总回报函数

最终的回报函数可以归结为以上三者的线性叠加之和,见式(5),其中C1、C2、C3为权重因子。

R=C1Rquality+C2Roscillation+C3Rbuffer

(5)

3.3 环境状态

在构建环境状态时,结合回报函数的定义,本文采用视频质量等级和缓冲区长度作为环境状态。此外,因为带宽也是码率选择中的一个重要因素,所以将带宽也加入到环境状态中。表1给出了环境状态的定义。

表1 环境状态定义

Q学习的算法描述详见算法3,算法维护一个状态空间和行动集构成的矩阵S×A来存储Q值,下面对整个算法进行详细描述。

算法3基于Q学习的客户端码率选择算法

1.Initialize:

2.Q←0

3.for each episode//video start play

4.s←randSelectState();

5.for each step of episode//request segment

6.a=selectAction(s);//use ε-greedy

7.calculate R by formula (5)

8.calculate Q by formula (1)

9.s←s′

10.end for

11.end for//video end

12.return Q;

对算法3的解释如下:

首先将Q值矩阵初始化为全0元素矩阵,episode为智能体学习的次数,算法第3行开始对智能体进行训练,第4行是从所有码率中随机选择一个码率作为初始状态。

算法第5行～第10行:每一次的码率请求对应一步,对于每一次的码率请求,智能体使用ε-greedy方法选择一个码率作为下一时刻要请求的视频码率,根据式(5)计算该码率对应的回报值R,根据式(1)更新Q值矩阵,同时,将当前的状态s进行更新,然后进行下一步的循环过程。

当设定的episode循环结束之后,Q学习过程结束。将最终训练得到的Q值矩阵作为客户端的码率决策依据。当客户端请求到来时,根据客户端不同的状态,查询Q值矩阵找到当前状态下效用值最大的动作为最优码率。

4 仿真与分析

4.1 仿真参数说明与设定

仿真实验不考虑链路的连接关系,使用的拓扑包含4个服务器,各个服务器的带宽数据基于中国科学技术大学校园网络内某一服务器的真实网络带宽情况。选取1个客户端发起DASH视频请求。视频选择开源视频源“Big Buck Bunny”,该视频由2 s长的视频分片组成,并且每一个视频分片被编码成7个质量等级:300,400,600,800,1 200,1 500,1 800,单位为Kb/s。客户端播放器的缓冲区上限阈值设置为30 s(15个分片)。通过调整实验参数进行多次实验,获得一组比较好的设置参数。本文最终回报函数中参数C1、C2、C3均设置为1。式(1)中的α设置为0.1,γ设置为0.5。

实验的流程共分为3个阶段:训练学习获取码率决策矩阵,即Q值矩阵,根据分片调度算法获取分片分配矩阵A,根据环境状态及Q值矩阵选择码率并按分配矩阵A中分配方式发起视频请求。

1)客户端学习算法

本算法是在Ubuntu14.04系统下通过编写python脚本实现的,主要是调用python下的工具包numpy,同时在实验中episode设置为200 000,step设置为100 000,数值较大,运算时间较长,而python脚本执行速度较快。因此,本文选择使用python执行Q学习算法。

2)分片调度算法

本算法是DASH流媒体视频传输系统中的重要一步。在实验中,采用真实的服务器带宽进行实验,另外,由于Matlab具有强大的矩阵处理能力,因此本文选择在Matlab上执行分片调度算法。在执行分片调度算法的过程中,通过改变服务器带宽进行多次实验,观察客户端质量变化及缓冲区变化情况。

3)客户端码率决策

客户端码率决策是实验的最后一步,决策过程是在Matlab上执行的。首先根据客户端当前环境状态,查询Q值矩阵中对应的状态行,找到该状态下效用值最大码率作为本次要请求的视频码率,然后根据分片分配矩阵A向服务器发起视频分片请求。客户端维护着请求的视频质量列表,作为客户端性能评估的依据。

在仿真实验过程中,具体的测试环境及软硬件配置信息如表2所示。

表2 实验配置

4.2 仿真结果分析

使用真实服务器带宽进行仿真实验时,考虑到真实服务器带宽和本文给定的视频码率不匹配问题,对真实数据进行了线性放大处理。在放大实际数据量的同时,保留了原始数据良好的周期性及波动性。本文实验拓扑结构如图3所示,设置了4个DASH服务器,选取1个客户端发起视频请求。

图3 实验拓扑

首先,本文运行客户端上的Q学习算法训练学习客户端码率选择过程,训练参数设置已在4.1节描述,最终得到训练的Q值,作为本文后续实验的码率选择依据;然后,客户端发起视频分片请求,运行控制器上的分片调度算法,算法决策出应该向哪几个服务器发起视频分片请求,接着,客户端根据控制器收集的带宽信息和客户端自身的状态信息,查询Q值矩阵中对应的状态行,找到该状态下效用值最大码率作为本次要请求的视频码率,开始视频传输服务。

实验将客户端QoE作为性能指标,分别测量了客户端平均视频质量等级、平均缓冲区大小和码率切换次数。此外,为了更好地反映本文策略的效果,仿真实验中加入了一组对照实验:协同多尺度调度算法[4],该算法也是针对DASH多服务器场景,能够平衡服务器负载,自适应各个服务器带宽,优化视频服务质量。实验将码率等级从低到高依次编号,从1开始,得到7个质量等级,实验结果如表3～表5所示。表中第1行给出了服务器带宽的放大倍数x,下面2行分别对应不同策略下的实验结果。

表3 平均质量等级对比

表4 不同策略平均缓冲区大小对比 s

表5 不同策略码率切换次数对比

实验结果表明,本文提出的分片调度算法能够在SDN控制器指导下有效改善客户端QoE。在不同的带宽放大倍数下,本文策略在平均视频质量、码率切换次数和平均缓冲区大小等方面均有所优化,其中分片调度算法保证了连续几个分片的码率一致性,使得码率切换频率明显降低。

另外,为了更直观地反映本文策略的实验效果,本文在服务器带宽倍数设置为4.90时,对客户端码率等级和缓冲区波动情况进行了图形化展示。图4对比了2种不同方案下的质量等级随时间波动情况。图5对比了2种不同方案下的客户端缓冲区的变化情况。

图4 质量等级波动图

图5 客户端缓冲区波动图

图4表明,在视频播放过程中,本文算法下视频质量波动次数明显减少,并且在波动幅度上相对于协同调度算法也略有减少,进而提高了用户体验质量。图5表明,协同多尺度调度算法下客户端缓冲区的波动更加剧烈,而本文算法下客户端缓冲区波动稍缓慢,这主要得益于本文中客户端Q学习算法将缓冲区状态引入了环境状态中,当缓冲区状态很低时,会给系统一个较大的惩罚。

5 结束语

本文提出了一种基于多服务器的DASH客户端优化算法,借助于SDN,实现了对服务器可用带宽的准确测量。通过将多个视频分片组成一个视频块,并对这个视频块中的码率进行统一化处理,一方面减少了客户端视频码率的频繁切换,另一方面提高了总体视频质量。同时,本文采用Q学习算法,通过自我学习训练Q值矩阵,为每一个视频块选择合适的码率,大幅提高了码率选择的效率。下一步将考虑客户端和服务器之间的路径规划问题,使客户端能够自动切换到网络状况较好的传输路径上。