云环境视频直播中的服务器选择问题

刘志强，万剑雄，董秀曼

（内蒙古工业大学 信息工程学院，内蒙古 呼和浩特010080）

0 引 言

云计算环境可为实时流媒体直播提供平台，具有较强的适应性与可扩展性。云环境中的数据中心通常分布在一片较大的地理区域内。终端用户可从各个数据中心中获取实时流媒体数据，而不是直接从源服务器中获取数据，有效的避免网络拥塞与源服务器过载。

云计算是云服务提供商面对的一个核心问题。在传统基于Web的应用中已经存在一些服务器选择策略［1－4］，这些策略有很多都具有动态性，因为动态的服务器选择策略可以更合理地利用有限的资源，但这些基于Web的动态服务器选择策略无法直接移植到视频流媒体直播环境。

本文研究云环境中流媒体视频直播的服务器选择问题，给出多阶段服务器选择调度策略，有效保证服务质量，降低运营成本。

1 相关工作

目前，国内外针对基于云计算的视频直播问题已经有了一些研究成果。刘景使用虚拟化技术动态调配资源建立分发服务器的思想，提出一种基于云计算环境的视频直播设计方法，有效地节约了校园网主线路的大量带宽和物理计算资源，并在真实的校园网环境中进行了测试［5］。邓达等对对等节点引入评分，提出一种缓冲算法，利用CDN 边缘服务器缓解P2P节点的瞬时拥塞，较好地减少了节点的启动时延［6］。孙名松等利用基于蜂窝的负载均衡算法和主动聚簇算法，解决了单点故障隐患，改善了负载不均衡的问题，提高了服务器的利用率［7］。Wang Feng等提出一种基于云计算环境的视频直播系统，称为CALMS。文中给出了一种动态虚拟服务器租赁策略，可在满足视频服务可用性与视频播放质量的前提下，最小化资源租赁成本。CALMS系统可充分利用全球视频访问请求的时间与位置异质性，较为精确的预测用户请求数量，降低视频服务提供商的运营成本［8］。Raymond Sweha等提出了ngelCast原型系统，从云平台中租用一些称为angle的服务器，设计了一个构造最优多叉树的算法用以在angle服务器与用户节点之间传输实时视频数据。该系统部署在Emulab和PlaneLab平台，实验结果表明了AngelCast系统的有效性［9］。以上这些研究，大多关注如何降低云环境中部署视频服务的运营成本，而在终端用户的服务器选择方面的研究还不完善。在视频直播服务中，服务器选择策略对端到端延时有较大影响，是视频直播系统中的关键技术之一，对提高终端用户体验起着关键性的作用。因此，研究如何设计最优的服务器选择策略是视频直播系统中亟待解决的问题。

2 问题建模

一个典型基于云环境的实时流媒体直播系统如图1所示。因特网内容提供商 （Internet content providers，ICPs）将实时视频进行采集、编码、与压缩等处理，并将视频流媒体数据传输给核心服务器。核心服务器再通过云提供商的覆盖网络 （该覆盖网络既可以是专用线路，也可以是公共线路）将这些数据分发到各个地区的数据中心中。来自不同地区的终端用户向云提供商发起视频请求，并通过服务器选择 （server selection，RR）技术被重定向到某个边缘服务器中。

图1 实时流媒体视频直播系统结构

2.1 终端用户模型

为管理方便，云提供商通常将整个服务区域划分为一些相邻的地理子区域。划分的方法一般与ISP 网络的拓扑结构与人口的地域分布有着较为密切的关系。令R ＝｛1，2，…，r｝为子区域的集合，φi，i∈R 为子区域i内终端用户所占总体用户的比例。显然，有∑i∈Rφi ＝1。

S Agarwal等的研究［10］结果表明，对于某种特定的英特网在线应用，其终端用户的地理分布一般会遵循某种特定的规律。因此，这里假定在视频流媒体直播问题中，某个子区域内终端用户所占的比例服从某种稳态分布，即φi为一个定值，不随总终端用户的数量变化。φi 的确切数值可以通过统计以往实时流媒体视频直播的记录数据得到。

在视频直播开始前，云提供商会在以往直播统计数据的基础上，对本次直播的终端用户总量N 进行一次粗略的估计。这种离线估计虽然在一定程度上能提供一些信息，但是这些信息往往都不精确，有时还会与真实数据产生较大误差。其原因在于影响终端用户数量的因素数量多且关系复杂，例如，英特网冲浪人数在一直增长，这种增长对于一次视频直播产生的影响难以建模；一次视频直播的观看用户可能与节目受欢迎的程度相关，但是节目的受欢迎程度又很难量化等等。为解决这个问题，云提供商可以利用另一个参数珡N 来对N 提供一个上界。珡N 的值可以简单的设为整个云计算环境可以支持的最大终端用户数量。

为简单起见，假设所有终端用户都是同质的，即所有用户所接受到视频流的码率都是一样的。这意味着总带宽消耗与终端用户总数成正比关系。

2.2 数据中心模型

云服务提供商通常在一个服务子区域建立一个或多个数据中心。令S＝｛1，2，…s｝为数据中心的集合。每个数据中心包含一些资源。在本文中考虑的主要资源是CPU 处理资源与网络带宽资源，因为这两种资源是影响实时流媒体传输性能的主要因素。假设在数据中心内部有一套负载均衡策略，可将终端用户请求均匀地分配给数据中心内的各个服务器。一般来说，由于各个地域的人口分布不均，因而各地数据中心所拥有的资源量也有较大差异。

为提高资源的利用效率，数据中心中的服务器一般都负责多种应用。例如，除了处理实时流媒体业务外，服务器还要处理一些基于Web的业务。在一个典型的云计算环境中，数据中心的负载可以通过服务器选择策略进行精确控制。对于数据中心i，令λi，i∈S为其CPU 的背景负载，即除了实时流媒体业务外所有其它业务所能占据的CPU 负载。令Bi为当前带宽所能支持的实时流媒体终端用户数。

在实时流媒体业务中，服务器的行为特性与处理Web业务的服务器行为特性有很大不同：在Web业务中，用户一般不会在系统中 “驻留”，即一旦用户接受服务器的服务（一般是较小的Web页面或者图片等其它多媒体文件）后，会立即从服务器的服务队列中被移除。相比之下，在实时流媒体业务中，只有终端用户关闭媒体播放器不再观看节目的时候，才能从服务器的服务队列中移除，否则，服务器必须连续地为其提供服务。在整个观看时间内，终端用户一直占据着服务器的资源。

在文献 ［11，12］中，作者验证了在基于Web业务的应用中，资源的消耗量与请求的速率基本呈线性关系。在实时流媒体业务中，也可有此结论。对于服务器群i，假设每个终端用户会占用ιi的CPU，则CPU 的使用率可表示为θiCPU＝λi＋xi·ιi，其中xi是当前正在被服务的实时流媒体终端用户的个数。进一步，可以假设服务器的响应时间gi为CPU 利用率的线性函数，即有gi＝ai·θiCPU＋bi，其中ai与bi都是常数。服务器响应时间对用户体验有较大影响。

2.3 服务器选择策略

服务器选择策略所起的作用相当于一个调度器，将终端用户的实时视频流媒体请求重定向到合适的数据中心中。一种好的服务器选择策略可以使云提供商获得更多经济利益，并与此同时保证终端用户的观看体验。

目前实现服务器选择策略的方法有多种，例如HTTP重定向、URL 重写、任播技术、以及DNS 重定向等。传统基于Web业务的服务器选择策略可分为两大类：非自适应服务器选择策略与自适应服务器选择策略。非自适应服务器选择策略实现较为容易，而自适应服务器选择策略实现相对复杂一些，需要考虑当前系统的状态，但是换来的是更强的健壮性与更高的资源利用率。但是，如前所述，已有的基于Web服务的动态服务器选择策略无法直接移植到实时流媒体视频直播业务中。因此，本文提出一种多阶段服务器选择策略来解决这一问题。

假设在系统中有一个集中管理设施，用来实现服务器选择策略。这种集中管理设施可以对各个数据中心的负载进行实时监控，并跟踪系统的3个状态参数：λi、Bi与xi。服务器选择策略可表示为一个矩阵F＝ ｛fij｝，i∈S，j∈R，其中fij代表子区域j中分配到数据中心i的终端用户请求所占的百分比。

2.4 效用函数

云提供商的效用表达为服务每个终端用户所得到的利润的和。利润是收入与成本的差值。在本文中，假设收入π（dij），i∈S，j∈R是从数据中心到终端用户数据链路总延迟的严格递减函数。总延迟包含两部分，即服务器响应时间gi与平均网络延迟Dij。

以往的研究如文献 ［10］等，仅将数据中心到终端用户之间的总延迟作为问题约束，与收入无直接关系。本文所提出的模型将总延迟直接放入目标函数中，而且可以对不同地域的终端用户赋以不同的权值。这样建模的意义在于一次流媒体视频直播可能会表现出较强的地域特性。例如，一场足球实况转播的主要观众很可能都来自于交锋的两支足球队所属的城市，而其它距离该足球赛事较远区域的网民对其的关注度有限。ICP 可以将所有子区域进行区分，给出一些 “重要”区域 （这些区域中的网民对本次实时流媒体视频直播可能会更有兴趣），而这些来自于 “重要”区域的观众应该得到更好的用户体验。该问题可以利用本文中的模型进行有效处理：云服务提供商可设置一系列具有不同参数的效用函数πi，i∈R，使得不同地区的延迟对整个目标函数的贡献不同。

3 最优服务器选择策略与MPS算法

3.1 问题描述

首先，在表1中给出本文中所用的符号及其意义。

表1 本文中的符号与意义

当N 给定时，最优服务器选择问题可以归结为一个如式 （1）～式 （6）所示的优化问题。该优化问题的目标是找到一个最优策略F ＝｛fij｝，来最大化CDN 提供商的经济利益

其中，式 （2）用来计算总时延，条件式 （3）代表CPU 资源约束，条件式 （4）代表网络带宽约束，条件式 （5）代表所有的终端用户必须都被服务。

将目标函数展开，并将约束式 （3）与式 （4）合并，可以得到精化的优化问题，如式 （7）～式 （10）所示。令该问题表示为RRS（N，M），其中M＝｛mi｝，i∈s是资源约束，则RRS （N，M）的输出结果为最优服务器选择策略F＊＝｛｝，i∈S，j∈R

由式 （7）～式 （10）中的约束，可以推得云提供商可以服务的终端用户数量，即约束的式 （8）～式 （10）的交集不空。

命题1 （优化问题有可行解的条件）：服务器选择优化问题的可行解非空，当且仅当

证明：由已知条件易得

（1）充分条件：

将约束式 （8）的所有不等式相加，可以得到

（2）必要条件：

现在来证明如果∑i∈Smi≥1 时，必有关于约束式（8）～式 （10）的非零解存在。令

则有∑i∈Sni≤∑i∈Smi，该式意味着∑i∈Sni可以小于或等于1。

约束式 （8）与式 （9）组成了一个非齐次线性系统，其增广矩阵为

经过一些简单的变换，该矩阵可以变为

总能找到一组ni使得∑i∈Sni＝1≤∑i∈Smi，因此关于式 （9）与式 （14）的解存在。此外，由于增广矩阵不是满秩矩阵，因此至少存在如下非零解

3.2 问题求解

为对服务器选择优化问题进行求解，首先将所有的决策变量组织成向量形式

并将目标函数改写为标准二次型

其中

命题2 （存在全局最大解）：当服务器选择问题可行解集合非空时，存在全局最优解，且任意局部最优解就是全局最优解。

证明：命题2的第一部分是显然的，因为约束集是凸集，且目标函数是连续函数。由Weierstrass定理，易得在可行解集内目标函数必然可以取到最大值。第二部分可如下证明。当n≥2时，矩阵A 所有n 阶主子式都为0。又由于a＜0，因而所有1阶主子式都小于等于0。因此，矩阵A为半负定矩阵。服务器选择问题为一个凸优化问题，Karush－Kuhn－Tucker条件为局部最优的充分必要条件，同时也是全局最优的充分必要条件。

服务器选择问题可以进行线性化处理，划归为一个线性规划问题进行求解，步骤如下：

（1）构建拉格朗日函数

其中，μi，ηij 与γj是拉格朗日乘子。运用Karush－Kuhn－Tucker定理，最优策略F 应是下式的解

（2）为约束式 （8）增加松弛变量xi，i＝｛1，…，s｝。

（3）令

其中

为符号函数。当且仅当zij＝0时，该问题的解才与原服务器选择问题的解相同，因此，可以得到如式 （22）～式 （30）所示的线性规划问题

Subject to

（4）求解式 （22）～式 （30）所示的线性规划问题，得到最优解。

3.3 MPS调度算法

算法1：MPS调度算法

（1）Function MPS （M，P）

（2）Initialize K＝ ｛ki｝，i＝1，2，…，n

（4）return ERROR；／＊current resources cannot support up to pnclients＊／

（5）for（i＝1；i＜n；i＋＋）

（6）ki＝RRS （pi＋1－pi，M）

（7）V＝Resource＿Consumption （ki，pi＋1－pi）

（8）M＝M－V

（9）end for

（10）return K；

一个较好的调度算法必须满足如下两个属性：①对于所有可能的N ，算法必须输出可行的服务器选择策略。“可行”的含义是每个数据中心的负载不能超过该数据中心所拥有的资源总量。②服务器选择策略应当输出最优的或近似最优的策略。非常明显，这两个属性的关注点不同。例如，如果采用非自适应的服务器选择策略，假设有N2＞N1，则一个在N＝N1时的最优策略在N＝N2时很可能是不可行策略。相反，一个在N＝N2时的最优策略很可能是N＝N1时的可行策略，但是却与最优策略有较大差距。因此，设计服务器选择调度策略的最大挑战，在于如何在这两个属性之间取得合理的权衡取舍。

本文使用如下方法来解决以上问题。首先，通过3 个参数NL、NH、来估计并描述终端用户的数量。其中有NL≤NH≤。区间 ［NL，NH］是 “正常”区间，即以前各次类似视频流媒体直播的终端用户总数都在该区间范围内。是 “最差”情形，是ICP所给出的用户总数上界的估计。其次，将区间 ［NL，］分割为n－1个阶段：P1＝［p1，p2），P2＝［p2，p3），…，Pn－1＝［pn－1，pn］，pi＜pi＋1，p1＝NL且pn＝，最后，利用MPS算法来计算得到阶段Pi的服务器选择调度策略ki。在阶段Pi，对每个新到的终端用户请求使用策略ki。

MPS算法 （算法1）将M 与P 作为输入参数。M ＝｛m1，m2，…，ms｝为资源约束，可以通过实时监测各个数据中心的资源使用状况得到。P＝｛p1，p2，…，pn｝是阶段的边界参数。最简单的一种阶段划分方法是两阶段划分，且令p1＝NL，p2＝NH，p3＝珡N。后文的数值分析部分显示，即使这种最简单的服务器选择策略也能显著的提高系统的收益。

MPS算法中使用了两个子函数。RRS（N，M）前面提到过，用来计算在资源约束M 下的最优策略。Resource＿Consumption（k，p）计算在路由请求调度策略k与终端用户请求数量p的情况下所消耗的资源。在下一小节中，将通过一个例子分析来说明多阶段服务器选择调度策略的有效性。

4 性能分析

4.1 仿真环境参数设置

在现实世界中，人口的地理分布是很不平均的。以此为依据，设定的终端用户分布见表2，其中子区域1，2，3的人口占据总人口的75%。

表2 终端用户分布

终端用户与各地数据中心的网络延迟见表3。当终端用户从本地数据中心获取视频直播流媒体数据时，网络延迟最小。但是，本地数据中心有可能没有足够的资源来支持本地所有的终端用户。这时，终端用户必须被重定向到其它 （远程）数据中心中。

假设云提供商可以提供基本的参数为：NL＝300，NH＝360，珡N ＝400。

4.2 结果与分析

在本小节中，将比较多阶段服务器选择策略与静态非自适应服务器选择策略的性能。

对于静态服务器选择策略，考虑如下情形：①策略S1，N＝360时的最优服务器选择策略。②策略S2，N＝400时的最优服务器选择策略。

对于多阶段服务器选择策略，考虑如下情形：①S3，二阶段服务器选择策略，其中P1＝ ［300，360），P2＝［360，400］。②S4，三阶段服务器选择策略，其中P1＝［300，330），P2＝ ［330，360），P3＝ ［360，400］。

注意在策略S3中，仅简单的将 “正常”工作负载作为第1阶段，而在策略S4中，将 “正常”工作负载平均划分为两个阶段P1与P2。

在图2与图3中，Optimal profit曲线为各个复杂度下最优策略所能得到的最大利润。图2中画出了3种静态服务器选择策略所得到的利润。可以看到，虽然在区间［300，360］中策略S1比S2所能得到的利润更多，但是当N 大于360时，策略S1为不可行策略，因此在图中以虚线画出了伪收益 （该收益实际上不能实现）。另一方面，虽然策略S2对于所有N∈ ［300，400］都是可行策略，但是当N 较小时，策略S2所得的利润与最高利润的差距较大。图3中可以看出多阶段服务器选择策略的优越性。策略S3与S4都是可行服务器选择策略。与策略S2相比，策略S3在区间 ［360，380］内所取得的收益有大幅提高，而策略S4在区间 ［300，370］内所得的利润几乎与静态最优策略所得到的最高利润相同。两种多阶段服务器选择策略S3与S4在当N 接近400 的时候，所得的利润都有所下降。但是，400实际上是一种 “极端”工作负载，这种情形在实际情况中出现的概率较低，因此，多阶段服务器选择策略在大多数情况下，比静态服务器选择策略所得到的利润要高。

图2 静态策略增益

图3 静态策略与多阶段策略收益

图4所描绘的是不同服务器选择策略所得的利润与最优利润之间差距的平均值。可以看出，二阶段服务器选择策略与三阶段服务器选择策略的性能都优于静态服务器选择策略。最左边的直方图是在整个用户到达区间 ［300，400］内3种策略与最优策略的目标函数差值，因此从整体来看，应用多阶段服务器选择策略相较于静态服务器选择策略可得到更高的利润回报。中间的直方图是用户 “正常”到达区间 ［300，360］。可以看出，在这个 “正常”工作负载区间中，多阶段服务器选择策略比静态服务器选择策略所得的利润要高的多。最右边的直方图是用户 “非正常”到达区间 ［360，400］，图中显示即使在 “非正常”工作负载区间内，多阶段服务器选择策略也比静态服务器选择策略所得的利润高。

图4 静态策略（当N＝100）、二阶段策略、以及三阶段策略所得的平均利润与最优策略所得利润的差距

从图4中还可观测到，在用户 “正常”到达区间内，二阶段服务器选择策略可得利润比三阶段服务器选择策略可得利润多，而在用户 “非正常”到达区间内，二阶段服务器选择策略可得利润比三阶段服务器选择策略可得利润少。该现象可推广到更一般的结论：在多阶段服务器选择策略中，阶段数量越多，则在用户 “正常”到达区间内可得的利润越高，而在用户 “非正常”到达区间内可得的利润越少。导致该现象的主要原因，在于阶段数越多，则MPS算法会更看重在前期用户 “正常”到达区间，因此所得利润越高，但是相应的会预留更多的资源。而到了用户“非正常”到达区间，由于前期资源开销相对较多，会导致后期资源不足，因此所得利润减少。

5 结束语

本文主要关注在云环境实时流媒体视频直播中如何设计一个较好的服务器选择策略。实时流媒体视频直播具有一些自己独特的性质，而这些性质与传统基于Web服务的应用有较大差别，导致以往的服务器选择策略无法直接应用。为解决这一问题，本文建立了基于优化理论的服务器选择策略模型，并提出一种多阶段服务器选择算法。数值分析显示该方法在终端用户无法精确预测时也能显示出较好的性能。

［1］Patricia Takako Endo，Andre Vitor de Almeida Palhares，Nadilma Nunes Pereira，et al.Resource allocation for distributed cloud：Concepts and research challenges ［J］.IEEE Network，2011，25 （4）：42－46.

［2］Church K，Greenberg A，Hamilton J.On delivering embarrassingly distributed cloud services［EB／OL］.［2008－04－02］.http：／／conferences.sigcomm.org／hotnets／2008／papers／10.pdf.

［3］Chandra A，Nebulas AJW.Using distributed voluntary resources to build clouds［C］／／Proceedings of the Conference on Hot Topics in Cloud Computing，2009：1－9.

［4］Mohammad Hajjat，Shankaranarayanan PN，David Maltz，et al.Dynamic request splitting for interactive cloud applications［J］.IEEE Journal on Selected Areas in Communications，2013，31 （12）：2722－2737.

［5］LIU Jing.Design of campus network video broadcast on cloud computing ［J］.Journal of Computer Applications，2014，34（2）：572－575 （in Chinese）.［刘景.基于云计算环境的校园网网络视频直播设计 ［J］.计算机应用，2014，34 （2）：572－575.］

［6］DENG Da，LV Zhihui.Design and implementation of live streaming system based on CDN－P2P－hybrid mode ［J］.Journal of Computer Engineering and Design，2013，34 （1）：66－70 （in Chinese）.［邓达，吕智慧.基于CDN－P2P流媒体直播系统方案设计实现 ［J］.计算机工程与设计，2013，34 （1）：66－70.］

［7］SUN Mingsong，ZHAO Xiuna，SUN Xibei，et al.Design of campus network live video system based on cloud computing［J］.Journal of Harbin University of Science and Technology，2012，17 （1）：58－62 （in Chinese）.［孙名松，赵修娜，孙西贝，等.基于云计算的校园网视频直播系统设计 ［J］.哈尔滨理工大学学报，2012，17 （1）：58－62.］

［8］Wang F，Liu J，Chen M.CALMS：Cloud－assisted live media streaming for globalized demands with time／region diversities［C］／／Proceedings IEEE INFOCOM，2012：199－207.

［9］Raymond Sweha，Vatche Ishakian，Azer Bestavros.AngelCast：Cloud－based peer－assisted live streaming using optimized multi－tree construction ［C］／／Proceedings of the 3rd Multimedia Systems Conference，2011：15－22.

［10］Sahoo J，Mohapatra S，Lath R.Virtualization：A survey on concepts，taxonomy and associated security issues［C］／／2nd International Conference on Computer and Network Technology，2010：222－226.

［11］Samee Ullah Khan，Anthony A.Maciejewski and howard jay siegel robust CDN replica placement techniques ［C］／／23rd IEEE International Symposium on Parallel and Distributed Processing，2009：1－8.

［12］Rao Lei，Liu Xue，Xie Le，et al.Minimizing electricity cost：Optimization of distributed internet data centers in a multi－electricity－market environment ［C］／／Proceedings IEEE INFOCOM，2010：15－19.