面向海量流媒体信道资源分配快速Nash议价算法
刘扬 , 魏蔚     
河南工业大学 信息科学与工程学院, 郑州 450001
摘要:在大规模在线流媒体分发系统中,服务端需处理来自全球各区域的海量用户请求。现有混合云架构不能很好地满足日益增加的动态流媒体内容分发要求,需结合私有数据中心、云和内容分发网络3类平台,充分挖掘各平台的优势以降低费用并提高服务质量。针对基于3种平台的混合云,该文给出了多资源分配问题的描述,将其转化为Nash议价问题,从几何角度获取问题的高效求解算法,并基于实际商用环境中海量流媒体采样数据进行了模拟实验。实验结果表明:相比传统的混合云架构,该算法可显著提升服务质量,在动态和静态内容混合情况下可降低平均约40%的费用,可在包括大量动态流媒体内容场景中进行快速有效的资源分配。
关键词流媒体    云计算    混合云    资源调度    Nash议价    
Fast Nash bargaining algorithm for resource scheduling problems with a large number of media streaming channels
LIU Yang, WEI Wei     
College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China
Abstract: The servers in large media streaming systems need to handle a large number of requests from all around the world. However, due to the increasing dynamic media content and because existing cloud-based architectures cannot provide enough benefits, the service provider needs to utilize a hybrid architecture composed of a content delivery network with private and cloud data centers to provide sufficient quality of service while reducing costs. This paper describes a general resource scheduling problem for this scenario for a hybrid cloud, which is then transformed into a Nash bargaining problem. A fast Nash bargaining algorithm is given based on a geometrical perspective of the problem. Tests show that the algorithm improves the quality of service and reduces expenses by about 40% compared with a traditional hybrid architecture, so it can effectively handle large amounts of dynamic media content.
Key words: streaming media     cloud computing     hybrid cloud     resource scheduling     Nash bargaining    

大规模在线流媒体分发系统(如Netflix和YouTube)面临来自全球各区域高度动态的用户请求,利用云计算平台可满足快速增长的资源需求,降低费用并提升用户体验。系统在全球各云数据中心中,为各流媒体信道分配计算、存储和网络资源,将单个用户请求分发到较近数据中心,以保证服务质量。因此需在异质资源和多种不同计费模式下,以尽量低的代价满足服务质量要求。

基于云平台的流媒体内容分发已有较多的研究工作,由于内容分发网络(content delivery network, CDN)较高的性价比,现有成熟平台仍使用CDN发送静态内容。如在Netflix系统架构中,云只负责用户管理和源文件处理,分发主要依赖CDN。但随着流媒体业务的发展,仅依赖CDN无法满足多样业务层需求,如在动态产生视频内容的场景中,需对每个请求做独立计算,基于CDN方式无法有效承载并处理这种情况,云计算数据中心可应对并发挥更大的作用。在现有动态和静态内容混合存在情况下,一种可行方式即结合私有数据中心、云和CDN 3个平台,充分挖掘各平台优势,进一步降低费用并提高服务质量。研究这类混合云中面向海量流媒体信道的资源分配问题,有助于构建满足多种业务需求的流媒体系统。

已有工作探讨了基于云平台流媒体内容分发的若干问题。文[1]分析了混合云中面向视频点播服务的资源配置问题,限制平均延时以保证服务质量,利用Lyapunov优化方法获得长程统计平均最优。文[2]研究了面向流处理服务的资源部署问题,考虑经由中间节点响应客户请求的情况,采用集合覆盖等方法从多角度规约问题获取最优解。类似的,文[3-4]也集中于缓解资源不足问题并保证足够的服务质量,但未考虑跨多平台多种计费模式。文[5]尝试解决多种计费模式下的费用优化问题,从各云中心预定最小量资源,根据不同时间槽内动态变化的用户需求,实时调整以保证服务质量。文[6]设计主动、被动、智能等流媒体内容迁移策略,高效迁移私有服务器至云中。上述算法均利用分布式云架构满足流媒体分发要求,但未充分考虑海量流媒体分发时性能问题,影响算法实用性。

在基于云的内容分发方向上,文[7]考虑利用空闲带宽分发容迟数据,采用任务调度与资源整合相结合的思路,延时调度以充分复用带宽资源并减少分发时间。文[8]的MetaCDN架构将用户内容分发到多个存储云中,最大化表征服务质量的效用函数。文[9]提出基于Lyapunov优化理论的通用优化框架,在保证服务质量的前提下最小化资源使用费用。文[10]研究了存储云中的内容存放问题和存储云间的分发网络构建问题,提出了多种启发式算法。文[11]设计了一种结合树形和网状拓扑的新型分发架构,采用网络编码方法提高分发效率,保证服务质量的同时大幅降低骨干网流量。文[12]提出基于用户行为特征的资源分配策略,通过统计用户工作习惯与任务完成时间的变化规律,建立用户行为特征信息表,实现动态调整资源的分配策略。文[13]建立云环境中用户效用的描述模型,量化用户对任务执行时间和费用等指标的满意程度,基于线性规划理论得到面向用户效用的任务调度优化模型。除高度相关的云计算方向研究工作,点对点网络的相关工作也研究类似的资源调度问题[14]

为满足动态视频分发场景的资源需求[15-16],需采用私有数据中心、云和CDN混合平台分发流媒体内容,因此针对这类平台中结合通用计费模型的多资源分配问题,本文提出可处理海量流媒体信息的快速议价算法,包括: 1) 给出了混合平台中的多资源分配问题通用形式,将其转化为Nash议价问题,并证明等价性;2) 从几何角度找到议价问题的高效算法并验证效果;3) 通过来自YouTube实际商用环境的海量数据进行了模拟实验[17]。实验结果表明:相比传统的分布式云架构,该算法可明显降低费用,有效地优化资源配置并提升服务质量。

1 模型

在系统模型中,共有J个数据中心,由来自私有、公有云和内容分发网络的数据中心组成, 数量分别为JdJpJc,数据中心序号用j表示。需要区分3种不同数据中心时,分别用jdjpjc表示。每数据中心资源限制是带宽限制Bj、处理能力限制Cj和存储限制Sj。对于公有云和内容分发网络中心,资源限制BjpBjcCjpCjcSjpSjc一般为很大的值,表示资源不受限的情况;对于私有云数据中心,根据基础设施容量设置对应的上限值。各种数据中心里,带宽、计算和存储资源的计费函数分别为gBjd(·)、gCjd(·)和gSjd(·),这些函数为具有通用性的凹函数,保证算法可适用于各类已有计费模式。对于公有云数据中心,根据选取的资源组合方式设置计价函数;对于内容分发网络数据中心,由于一般只按流量收取费用,根据流量单价设置gBjc函数;对于私有云数据中心,由于计算和存储在建立数据中心时一次性购买,一般不另收取费用,计算和存储计费函数gCjd(·)和gSjd(·)可折合能源使用费用设为较小的值,私有云带宽计费函数gBjd(·)可根据基础设施价格折合成单价。

全球各地的用户连接这些数据中心,获取多个流媒体信道的内容。为保证服务质量,尽量连接到较近的数据中心。一般按地理位置划分多个子区域,用户和数据中心分别位于各子区域中,若用户向同一个子区域内数据中心发送请求,由于网络距离较近,会获得较高的服务质量,这种情况下分发产生的流量视为本地流量,跨区域分发的流量则视为跨区域流量。本地流量占全局流量越高,一般说明整体的服务质量越高,系统整体结构如图 1所示。

图 1 系统结构示意图

设系统提供I个流媒体信道的播放服务,并根据历史信息预测请求数和资源需求,流媒体信道需求表示为采样间隔Tr内平均请求数;经过调度间隔Ts,重新调整新的资源分配方案。这里有${T_{\rm{s}}} \gg {T_{\rm{r}}} $,例如需求表示为每10 s(Tr=10 s)的平均请求数,每隔1 h调整一次调度方案(Ts=3 600s)。在一次调度中,设第i个流媒体信道对应资源文件的总播放时间为Li,一般为固定值;因用户播放可能中途退出,实际播放时间可能小于Li,设所有用户对该信道播放时间满足分布Di,对应累计概率分布函数为CDFi(·)。则对采样间隔t, 第i个流媒体信道的平均请求数为ri(t),则采样间隔t中累计的所有正在服务中的播放请求数为ci(t),为之前所有间隔到达且在当前间隔内仍在服务中的请求的和:

$ {c_i}\left( t \right) = \sum\limits_{x = 1}^{{L_i}} {{r_i}\left( {t - x} \right)\left( {1 - {\rm{CD}}{{\rm{F}}_i}\left( x \right)} \right)} . $ (1)

则计算调度间隔ts内目标资源需求,一种常见方法是应按请求峰值量计算,峰值${\hat c_i}\left( {{t_{\rm{s}}}} \right) $

$ {{\hat c}_i}\left( {{t_{\rm{s}}}} \right) = \max \left( {{c_i}\left( t \right)\left| {t \in {t_{\rm{s}}}} \right.} \right). $ (2)

设第i个流媒体信道的CPU消耗均值为E(DiC),带宽消耗均值为E(DiB),可得信道i总带宽资源消耗RiB(ts)=E(DiB)${\hat c_i}\left( {{t_{\rm{s}}}} \right) $,计算资源消耗为RiC(ts)=E(DiC)${\hat c_i}\left( {{t_{\rm{s}}}} \right) $,存储资源消耗为RiS,单次调度中可简写为RiBRiCRiS;调度结果表示为Pij,其中Pij=1表示数据中心j参与分发第i个流媒体信道流量,否则为0。可由多个数据中心提供第i个流媒体信道数据,调度前预先设置一些热门信道的复制数Ni, 对任意i$ \sum\limits_{j = 1}^J {P_i^j} = {N_i}$。对于单次调度,首要的调度目标是降低总资源费用:

$ {\rm{cos}}{{\rm{t}}_{{\rm{total}}}} = \sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {P_i^j{\rm{cost}}_i^j} } . $ (3)

其中,costij表示每信道在每区域中的资源费用:

$ {\rm{cost}}_i^j = g_j^{\rm{B}}\left( {R_i^{\rm{B}}} \right) + g_j^{\rm{C}}\left( {R_i^{\rm{C}}} \right) + g_j^{\rm{S}}\left( {R_i^{\rm{S}}} \right). $ (4)

另一个目标是尽量提高整体的服务质量,服务质量用局域性量化表示,局域性越高表示更多的请求被网络延时较低的近处的数据中心响应:

$ {\rm{locality}} = \frac{{{\rm{traffi}}{{\rm{c}}_{{\rm{local}}}}}}{{{\rm{traffi}}{{\rm{c}}_{{\rm{total}}}}}}. $ (5)

其中:trafficlocal表示本地满足的流量,traffictotal=$\sum\limits_{i = 1}^I {R_i^{\rm{B}}} $表示全局所有流量。使用lij表示是否为本地流量,lij=1表示第i个流媒体信道若由数据中心j提供服务,视为本地流量,否则为0。可由历史信息进行估算并预先设置,比如第i个流媒体信道的用户需求主要来自数据中心j所属区域,对应流量主要在本地传输可视为本地流量。则trafficlocal可重新表示如下:

$ {\rm{traffi}}{{\rm{c}}_{{\rm{local}}}} = \sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {l_i^jP_i^jR_i^{\rm{B}}} } . $ (6)

其中:RiB表示第i个流媒体信道的带宽需求,lijRiB表示若信道i分配给数据中心j会产生的本地流量,$\sum\limits_{j = 1}^J {l_i^jP_i^jR_i^{\rm{B}}} $表示在最终的分配结果中第i个流媒体信道所产生的总的本地流量。因而式(6) 表示分配结果中所有流媒体信道到所有数据中心所产生的本地流量。上述目标在某些情况下存在冲突,如由最便宜但距离较远的数据中心响应请求,可降低费用但会影响服务质量。采用加权线性组合将多个目标变换为单个目标,其中每个目标都归一化到[0,1]区间,如式(7) 所示,参数α即为多目标组合为单目标的权重参数,一般设置为1。实际使用中可根据对服务质量和费用的偏好设置,若偏向于提供更好的服务质量,可设置α为大于1的一个参数;若偏向于牺牲服务质量以降低费用,可设置α为介于0和1之间的一个小数。

$ {\rm{revenue}} = \alpha \cdot {\rm{locality}} - \frac{{{\rm{cos}}{{\rm{t}}_{{\rm{total}}}}}}{{{\rm{cos}}{{\rm{t}}_{{\rm{max}}}}}}. $ (7)

在当前系统模型下,目标即最大化上述收益:

$ \max \left( {\alpha \frac{{\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {l_i^jP_i^jR_i^{\rm{B}}} } }}{{\sum\limits_{i = 1}^I {R_i^{\rm{B}}} }} - \frac{{\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {P_i^j\left( {g_j^{\rm{B}}\left( {R_i^{\rm{B}}} \right) + g_j^{\rm{C}}\left( {R_i^{\rm{C}}} \right) + g_j^{\rm{S}}\left( {R_i^{\rm{S}}} \right)} \right)} } }}{{{\rm{cos}}{{\rm{t}}_{{\rm{max}}}}}}} \right),\;\;\;{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\;\;\;\left\{ \begin{array}{l} \sum\limits_{i = 1}^I {R_i^{\rm{B}}P_i^j} \le {B_j},\;\;\;\;\forall j;\\ \sum\limits_{i = 1}^I {R_i^{\rm{C}}P_i^j} \le {C_j},\;\;\;\;\forall j;\\ \sum\limits_{i = 1}^I {R_i^{\rm{S}}P_i^j} \le {S_j},\;\;\;\;\forall j;\\ \sum\limits_{j = 1}^I {P_i^j} = {N_i},\;\;\;\;\forall i;\\ P_i^j \le 1,\;\;\;\;\;\;\;\;\;\;\;\forall i,j. \end{array} \right. $ (8)

在式(8) 约束中,前3项分别为每数据中心带宽、计算和存储3种资源的限制,包括私有数据中心内3种资源的上限,租用的CDN数据中心内3种资源的配额限制。对于云数据中心,可设置限制为一个较大的值。由于包含通用的代价函数,上述公式是一个典型的多维广义分配问题,即使近似算法也是APX-hard[18]。在I较大的情况下,传统思路会采用Lagrange松弛近似,将原问题分解为多个0~1背包问题,但是仍然会导致较高的计算复杂度。针对具体问题的特点,拟采用Nash议价算法进行求解,Nash议价算法主要用于解决多个博弈者分配多个物品场景中的问题,且分配目标使得博弈者整体的利益最大化,而当前问题是如何将多个流媒体信道分配到多个数据中心最大化整体的收益,2个问题具有很类似的结构,Nash议价算法有希望帮助获得高效算法。

2 算法 2.1 问题定义

在博弈论中,假定博弈双方是理性的,在每个个体追求自身收益最大化的前提下,研究他们的行为选择。计算机研究领域已有利用博弈论解决相关问题的先例[19-20]。Nash议价解是研究合作博弈场景论的一种数学模型,它解决的是2个或多个博弈个体总体效用最大化的问题,以在个体之间公平有效地分配收益。在问题场景中,有多个博弈者和多个物品,每个博弈者都希望得到部分物品,每个博弈者的效用是其对物品的期望的函数,求解目标即所有博弈者效用积最大化。设在给定解中,博弈者j对所有分配到的物品的效用为Ujdj为其改变现有分配方式失去的效用,则Gj=Ujdj为博弈者j的净效用,则Nash议价解即最大化净效用积为

$ \max \left( {\prod\limits_{j = 1}^J {{G_j}} } \right). $ (9)

为使用Nash议价算法,需将原问题做一些变换。首先引入记号uij:

$ u_i^j = \alpha \frac{{l_i^jR_i^{\rm{B}}}}{{\sum\limits_{i = 1}^I {R_i^{\rm{B}}} }} - \frac{{g_j^{\rm{B}}\left( {R_i^{\rm{B}}} \right) + g_j^{\rm{C}}\left( {R_i^{\rm{C}}} \right) + g_j^{\rm{S}}\left( {R_i^{\rm{S}}} \right)}}{{{\rm{cos}}{{\rm{t}}_{\max }}}}. $ (10)

则式(6) 中求解目标可简化为

$ \max \left( {\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {u_i^jP_i^j} } } \right). $ (11)

则有:

$ \begin{array}{*{20}{c}} {\max \left( {\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^J {u_i^jP_i^j} } } \right) \Leftrightarrow \max \left( {\sum\limits_{i = 1}^I {\lg \left( {\exp \left( {\sum\limits_{j = 1}^J {u_i^jP_i^j} } \right)} \right)} } \right) \Leftrightarrow }\\ {\max \left( {\exp \left( {\sum\limits_{i = 1}^I {\lg \left( {\exp \left( {\sum\limits_{j = 1}^J {u_i^jP_i^j} } \right)} \right)} } \right)} \right) \Leftrightarrow }\\ {\max \left( {\prod\limits_{i = 1}^I {\left( {\exp \left( {\sum\limits_{j = 1}^J {u_i^jP_i^j} } \right)} \right)} } \right).} \end{array} $

${G_j} = \exp \left( {\sum\limits_{i = 1}^I {u_i^jP_i^j} } \right) $,原问题表示为式(9) 的形式,其中uij即为物品i对用户j的净效用。

2.2 问题求解

由于限制条件,问题仍表现为一个高复杂度的非确定性多项式困难问题[21], Nash议价问题的经典近似算法需要多次迭代,在海量物品场景下复杂度仍然很高。受相关工作启发[22],尝试将问题转换到几何空间获取高效算法。每个博弈者和每个物品都可以视为空间中的点,物品到博弈者的效用可表示为点之间的距离dij,效用越高则距离越近,则dij可归一化并表示为$d_i^j = {\left( {\sum\limits_{j' = 1}^J {1/u_i^{j'}} } \right)^{-1}}/u_i^j $,且有$\sum\limits_{j = 1}^J {d_i^j} = 1, \forall i $。则Nash议价解中的均衡状态可类比为达到平衡状态的天平,通过模拟寻找天平的平衡态找到原问题的均衡点,如图 2所示,2个博弈者在分配6个物品时找到了均衡点。如式(12) 所示,φij表示物品i在天平上产生的力矩,则最后的均衡点上,每个博弈者的物品力矩和相等。在得到均衡解后,将天平左边的物品分配给博弈者1,将天平右边的物品分配给博弈者2,得到Nash议价解:

图 2 几何空间中天平均衡态示意图

$ \varphi _i^j = u_i^jd_i^j = {\left( {\sum\limits_{j' = 1}^J {1/u_i^{j'}} } \right)^{ - 1}}. $ (12)

对每个博弈者j,获取所有物品和博弈者j的距离,按升序排列得到列表listj, 其中第k个物品表示为listkj,其力矩为φkj。对每列表中每物品k′,按照先后顺序计算其累计力矩$\mathit{\Phi} _{k'}^j = \sum\limits_{k = 1} {\varphi _k^j} $和每个博弈者j的累计力矩阈值${\varphi ^j} = \frac{1}{J}\sum\limits_{i = 1}^I {\varphi _i^j} $。则对每个列表,找到物品m,其累计力矩ΦmjφjΦm-1j < φj,将列表listj中的物品1、物品2、…、物品m分配给博弈者j,算法还需处理约束及重复分配问题,如算法1所示。

算法1  Nash议价快速求解算法。

输入:信道总拷贝数量I和各信道资源需求,数据中心数量J和各中心的计价函数;

输出:分配方案

① For (j=1 to J)

② For (i=1 to I)

③ 计算距离dij, 力矩φij

④ End for

⑤ 计算用户j的累计力矩阈值φj

⑥ End for

⑦ For (j=1 to J)

⑧ 创建列表listj

⑨ 计算列表每个元素位置的累计力矩Φkj

⑩ 获取ΦmjφjΦm-1j < φj处的下标m

⑪ 对同个信道只考虑一份拷贝对应的物品,获取刚好满足约束物品下标m′;

⑫ 取m″=min(m, m′),将listj中下标1到m″的物品分配给博弈者j

⑬ End for

⑭ For (i=1 to I)

⑮ 若物品i被分配给超过1个博弈者,则分配给距离最小者;

⑯ 若物品未被分配给任何博弈者,则分配给未超过约束的距离最小的博弈者;

⑰ End for

首先迭代计算所有物品到所有博弈者的距离、力矩等基础信息(行①~⑥),再构建每个博弈者的候选物品列表,计算累计力矩并获得初始分配方案(行⑦~⑬), 最后分配方案中的一些特殊物品(行⑭~⑰)。该算法称为GBMS (geometrical bargaining algorithm for media streaming system)算法。各种计费函数都可事先表达为快速查询的数据结构,可保证计算复杂度为O(1),通过预先计算一些不变量,uijdijφij计算复杂度分别为O(1)、O(J)和O(1),则行①~⑥ 时间复杂度约为O(IJ2),通过采用快速排序算法,行⑦~⑬ 计算复杂度为O(JIlgI),通过采用插入排序,行⑭~⑯ 计算复杂度不会超过O(IJ)。因各j计算独立,采用并行度为J的算法,算法复杂度可低至O(I(J+lgI))。

3 实验

为验证算法在面向海量信道资源时的求解效果,使用YouTube的视频数据构建模拟环境[17],其中包含约160万个视频的信息,对一些热门视频设置多拷贝策略,对前10 000个热门视频设置3份拷贝,对应的设置I=1 600 000。图 3显示了数据中所有视频的观看次数的概率分布, 可看到大部分视频的播放次数都在1 000次及以下,仍有一些很热门的信道,信道数量多且资源消耗差异很大。

图 3 YouTube采样数据中每视频观看次数概率密度函数图

在模拟场景中,每信道的带宽需求在50 kB到1 000 kB间均匀分布,模拟从低到高各种清晰度的视频;每请求的CPU消耗符合均值为2 Mips、标准差为0.25 Mips的正态分布;根据上述带宽和CPU消息模型,设置需求的采样间隔为10 s,调度间隔为1 h;每采样间隔请求到达数量根据YouTube元数据的采样时间,每信道根据总数量基于Poisson分布生成;再根据式(1) 和(2),计算并设置调度间隔内带宽和计算需求RiBRiC,存储需求RiS按照YouTube元数据设置。随机选取全球161个主要城市作为数据中心所在地,即设置J=161。参考Amazon云,模拟场景使用的云中包括9个云计算数据中心,分别部署在实际Amazon数据中心对应位置,参考Amazon云官方收费标准[21]设置带宽、计算和存储资源计费函数gjB(·)、gjC(·)和gjS(·);场景中包含2个私有数据中心,分别部署在纽约和北京,每私有数据中心拥有100 TB存储能力、104 Mbps的带宽和105 Mips的计算能力,据此设置私有数据中心的资源上限BjCjSj;使用的内容分发网络包括150个接入点,随机分布在剩余的150个城市中,采用常用的按分发量计费方式,每GB流量计费0.085美元。为与传统架构对比,在场景中实现了纯云计算分发架构和纯内容分发网络架构。其中纯云中心分发采用文[1]和文[6]中提到的私有中心加云的分发架构,并考虑纯云计算分发架构在分发动态内容时产生的广告收益;纯内容分发网络架构模拟传统的私有数据中心结合内容分发网的分发架构。

首先比较了3种方法中未满足请求比例与动态内容比例的关系,取多个调度间隔内均值,如图 4所示。可以看到由于传统内容分发网络并不能有效地分发每请求变化的动态内容,在动态内容比例较高时导致很多请求无法满足。介于在动态内容场景下的明显差距,后面实验值只比较GBMS和纯云计算的分发方式。随后在不同参数设定下,比较了GBMS算法与纯云计算方式在费用上的差别,取多个调度间隔内均值,如图 5所示。可观察到GBMS始终存在费用优势,相比纯云计算方式,将费用平均降低40%左右;由于α的增加,提升了本地性的权重,使得更多的静态内容使用内容分发网络分发,相比纯云计算方式进一步降低了费用。

图 4 各方法未满足请求比例与动态内容比例关系图

图 5 不同参数设定GBMS与纯云计算方式费用比

为衡量不同算法在服务质量上的差别,本文比较了对应的请求的局域性。局域性定义为被本地服务器响应请求占所有请求的比例。因为服务质量和地理区域成反相关,距离越近服务质量越高,所以局域性可以作为服务质量的度量标准[3]。局域性越高,说明统计上这个方案达到的服务质量越好。图 6显示了GBMS方法和纯云计算方法的跨域流量比,取多个调度间隔内均值,可以看到相比纯云计算分发方式,GBMS可达到较高局域性,显著降低跨区域流量,在静态视频内容较多时可充分利用内容分发网络以提高服务质量。图 7显示了GBMS和纯云计算方式的费用和跨区域流量比随时间变化情况。其中动态视频比例为0.5且α=1,可见由于采用Poisson达到模型,两者的比例稳定在定值附近。接下来研究不同参数设定下GBMS算法在费用和跨区域流量上的变化趋势,取多个调度间隔内均值,如图 8图 9所示。在图 8中,费用随着动态内容的增加而升高,原因在于动态内容只能由费用较高的云数据中心提供服务;而随着α的增加,服务质量被赋予更高的权重,在较近但较贵的云数据中心与较远但便宜的分发网络数据中心间,还是会倾向选择前者,因而增加了整体费用。在图 9中,跨区域流量同样随着动态内容的比例而增加,原因在于动态内容只能由云数据中心提供服务,从而在某些情况下只能选择较远的云数据中心;随着α的增加,跨域流量反而有轻微下降,因为服务质量被赋予更高权重,从而部分降低了跨区域流量。实验结果可帮助选择不同的参数满足不同的要求。

图 6 GBMS费用与纯云计算方式跨区域流量比

图 7 GBMS费用与纯云计算方式费用和流量比

图 8 GBMS中不同参数下调度费用对比

图 9 GBMS中不同参数下跨域流量对比

4 结论

为满足动态和静态媒体混合内容的分发要求,在基于私有数据中心、云计算数据中心和CDN三类平台组成的混合云中,构建面向流媒体资源分配的Nash议价问题,通过将问题规约为几何空间的天平平衡问题,提出针对海量流媒体信道场景的快速Nash议价算法。实验结果表明:相比传统的混合云架构,该算法可显著提升服务质量,在动态和静态内容混合情况下平均可降低约40%的费用,可在包括大量动态流媒体内容的场景中进行快速有效的资源分配,可充分利用3个平台优势显著降低资源费用,降低跨区域流量以提供更高质量的服务。

参考文献
[1] QIU Xuanjia, LI Hongxing, WU Chuan, et al. Dynamic scaling of VoD services into hybrid clouds with cost minimization and QoS guarantee[C]//Proceedings of the IEEE International Conference on Packet Video Workshop. Piscataway, NJ, USA:IEEE, 2012:137-142. http://ieeexplore.ieee.org/document/6229726/
[2] YOU Kun, TANG Bin, QIAN Zhuzhong, et al. QoS-aware placement of stream processing service[J]. The Journal of Supercomputing, 2013, 64(3): 919–941. DOI:10.1007/s11227-010-0548-2
[3] WANG Feng, LIU Jiangchuan, CHEN Minghua. Calms:Cloud assisted live media streaming for globalized demands with time/region diversities[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:199-207.
[4] WU Yu, WU Chuan, LI Bo, et al. Cloudmedia:When cloud on demand meets video on demand[C]//Proceedings of the IEEE Conference on Distributed Computing Systems. Piscataway, NJ, USA:IEEE, 2011:268-277. https://pdfs.semanticscholar.org/86c4/3e228deb322a2ad9a43a1f686c9b58724723.pdf
[5] DENG Da, LU Zhihui, FANG Wei, et al. Cloud stream media:A cloud assistant global video on demand leasing scheme[C]//Proceedings of the IEEE Conference on Services Computing. Piscataway, NJ, USA:IEEE, 2013:486-493. http://ieeexplore.ieee.org/document/6649732/
[6] LI Haitao, ZHONG Lili, LIU Jiangchuan, et al. Cost effective partial migration of VoD services to content clouds[C]//Proceedings of the IEEE Conference on Cloud Computing. Piscataway, NJ, USA:IEEE, 2011:203-210. http://www.ijrter.com/papers/volume-2/issue-3/optimal-resources-provisioning-for-federated-cloud-load-handling-using-flow-fairness-scheme.pdf
[7] 黄永锋, 董永强, 张三峰, 等. 数据中心间空闲带宽感知的内容分发算法[J]. 通信学报, 2013, 34(7): 24–33. HUANG Yongfeng, DONG Yongqiang, ZHANG Sanfeng, et al. Leftover bandwidth-aware peer selection algorithm for inter-datacenter content distribution[J]. Journal on Communications, 2013, 34(7): 24–33. (in Chinese)
[8] Broberg J, Buyya R, Tari Z. Metacdn:Harnessing storage clouds for high performance content delivery[J]. Journal of Network and Computer Applications, 2009, 32(5): 1012–1022. DOI:10.1016/j.jnca.2009.03.004
[9] QIU Xuanjia, LI Hongxing, WU Chuan, et al. Cost-minimizing dynamic migration of content distribution services into hybrid clouds[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:2571-2575. http://i.cs.hku.hk/~hxli/paper/xuanjia-infocom12.pdf
[10] CHEN Fangfei, GUO Katherine, LIN John, et al. Intra-cloud lightning:Building CDNs in the cloud[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:433-441.
[11] 何智聪, 谷光昭, 王新, 等. 基于可重构路由器上缓存的流媒体协作分发策略[J]. 通信学报, 2012, 33(6): 82–90. HE Zhicong, GU Guangzhao, WANG Xin, et al. Novel cooperative caching strategies for video streaming distribution based on reconfiguration routers[J]. Journal on Communications, 2012, 33(6): 82–90. (in Chinese)
[12] 周景才, 张沪寅, 查文亮, 等. 云计算环境下基于用户行为特征的资源分配策略[J]. 计算机研究与发展, 2014, 51(5): 1108–1119. ZHOU Jingcai, ZHANG Huyin, CHA Wenliang, et al. User-aware resource provision policy for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(5): 1108–1119. DOI:10.7544/issn1000-1239.2014.20120918 (in Chinese)
[13] 唐卓, 朱敏, 杨黎, 等. 云环境中面向随机任务的用户效用优化模型[J]. 计算机研究与发展, 2014, 51(5): 1120–1128. TANG Zhuo, ZHU Min, YANG Li, et al. Random task-oriented user utility optimization model in the cloud environment[J]. Journal of Computer Research and Development, 2014, 51(5): 1120–1128. DOI:10.7544/issn1000-1239.2014.20121122 (in Chinese)
[14] TAN B, Massoulie L. Optimal content placement for peer-to-peer video-on-demand systems[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:694-702. https://arxiv.org/pdf/1004.4709.pdf
[15] Nicolas L S, Christoph N, Gilles S T. Cache policies for cloud-based systems:To keep or not to keep[C]//Proceedings of the IEEE Conference on Cloud Computing. Piscataway, NJ, USA:IEEE, 2014:1-8.
[16] HUANG Zixia, MEI Cao, LI Li Erran, et al. Cloudstream:Delivering high-quality streaming videos through a cloud-based svc proxy[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2011:201-205.
[17] Meeyoung C, Haewoon K, Pablo R, et al. I tube, you tube, everybody tubes:Analyzing the world's largest user generated content video system[C]//Proceedings of the ACM Sepecial Interest Group on Data Communication Conference on Internet Measurement. New York, NY, USA:ACM, 2007:1-14.
[18] Karlof J K. Integer Programming:Theory and Practice[M]. Boca Raton: CRC Press, 2005.
[19] 黄丽亚, 刘臣, 王锁萍. 改进的认知无线电频谱共享博弈模型[J]. 通信学报, 2010, 31(2): 136–140. HUANG Liya, LIU Chen, WANG Suoping. Improved spectrum sharing model in cognitive radios based on game theory[J]. Journal on Communications, 2010, 31(2): 136–140. (in Chinese)
[20] 饶翔, 张顺颐, 孙雁飞, 等. 基于预判与合作博弈的下一代网络资源优化分配方法[J]. 通信学报, 2009, 30(4): 60–65. RAO Xiang, ZHANG Shunyi, SUN Yanfei, et al. Next generation network resource allocation method based on cooperative game and decision-making in advance[J]. Journal on Communications, 2009, 30(4): 60–65. (in Chinese)
[21] Baron R, Durieu J, Haller H, et al. Finding a Nash equilibrium in spatial games is an NP-complete problem[J]. Economic Theory, 2004, 23(2): 445–454. DOI:10.1007/s00199-003-0376-1
[22] Wong K K L. A geometrical perspective for the bargaining problem[J]. Plos One, 2010, 5(4): 1–11.