设计应用

内容分发网络预取技术综述

0 引言

    随着互联技术的发展,各类创新型应用如雨后春笋般涌现,以文件传输、视频会议等为代表业务显著提高了企业工作效率,网络视频直播、网上购物等热点业务使人们的生活变得丰富、便捷[1]。由于智能终端的不断普及,互联网已成为现代人来获取信息和信息分享的重要途径,Web及流媒体业务用量爆炸式增长,网络中服务器的负荷加重问题和网络流量拥塞问题日益严峻。

    大规模的用户请求导致服务器负荷加重,成为网络故障中的重要隐患,更有甚者它将会使服务器宕机,产生拒绝服务现象,严重影响用户体验质量。此外,大规模请求会造成网络拥塞,显著增加用户侧内容的获取时延, 严重网络拥塞将引发数据包的大量丢失,导致用户访问失败。为了解决上述问题,研究者们提出了内容分发网络(Content Deliver Network,CDN)。如图1所示,CDN是由分布在网络边缘节点服务器构成的一层智能虚拟网,主要原理是将内容副本缓存到靠近用户端的节点服务器上,并根据实时网络情况把原始服务器的用户请求重定向至距离用户就近状态最佳的节点服务器,使用户可以就近获取所需内容,从而有效地缓解由大量远程访问引起的骨干网流量拥塞[2]

zs1-t1.gif

    在CDN中,缓存技术[3]是保证用户请求加速的一项关键技术,但就CDN本身而言,节点处的内容缓存主要由用户驱动,即当有用户请求内容时,节点服务器里没有该内容,节点服务器向内容源服务器获取该请求内容,在发给用户的同时,将该内容保存在节点服务器中,为未来相同的请求提供服务。本质上,该技术所采用的是一种被动缓存方式。在网络终端不断普及的趋势下,这种被动式内容存储将无法满足互联网流量爆炸式增长的需求,典型地引发下述问题:(1)缓存具有滞后性,即服务器节点无法预测内容的流行趋势,内容缓存滞后于潜在的用户需求;(2)节点处缓存空间利用率低,尤其是在节点服务器处用户请求较少的情况下,由用户驱动的被动缓存将使服务器节点仅缓存有限的请求内容,致使节点处存在大量闲置缓存空间。为提升节点服务器上的缓存空间利用率以及提供更好的服务质量,众多研究者提出在CDN节点处引入预取技术[4]。CDN预取技术是对其缓存的补充,核心思想是由节点服务器预先主动从内容源服务器处获取部分内容,以期加速用户对于内容的获取。预取技术的引入,使得服务器节点可以先验地缓存部分内容,解决了因无法预测网络中内容流行趋势所导致的缓存滞后的问题;此外,通过引入预取技术,服务器节点可以预取部分流行度较高的内容,避免节点处大量缓存空间闲置,使有限的网络资源得到合理的利用。预取技术作为内容分发中的关键技术在国内外受到广泛关注,众多学者围绕内容流行度及用户需求等对预取进行了大量研究。

1 CDN预取分类

    根据预取时关注的对象不同,将CDN预取分为面向内容的预取和面向用户的预取。面向内容的预取依据网络中内容请求数量变化来进行预取,称之为基于流行度的预取。面向用户的预取进一步划分为三类预取方式:第一类主要通过对用户兴趣进行分析来决定预取的内容,称之为基于用户偏好的预取;第二类根据用户之间的社交关系来预测内容的传播趋势,并据此进行内容预取,将其定义为基于社交网络的预取;第三类旨在通过研究用户移动性对节点服务器上缓存内容流行度的影响来动态调整内容预取策略,称之为基于移动性的预取。

1.1 基于流行度的预取

    大量统计表明:内容的访问流行度分布符合zipf定律[5],即仅有近20%的内容对象被超过80%的用户访问,这一现象反映了在网络中不同内容被用户的访问分布情况。流行度被定义为统计时间段中内容对象被访问的次数或概率来表示,在研究中,基于流行度的预取利用上述现象对流行度较高的内容进行预取[6]。在CDN中,一方面,不允许存储新内容时,根据流行度来确定所需要删除的内容; 另一方面,根据流行度来选择所要预取的具体内容。基于流行度的预取是CDN中一种主流的内容预取技术,其关键在于内容流行度的确定,目前常采用统计学、控制理论的预测方法,有指数平滑预测、多项式回归预测及Savitzky-Golay滤波预测三种。

1.1.1 指数平滑预测

    指数平滑预测是指采用指数平滑法(Exponential Smoothing,ES)对内容流行度进行预测,由于每个内容在其生命周期的早期和后期的流行度存在很强的相关性,指数平滑法已被广泛地应用于预测内容未来的请求数量[7]。指数平滑法是在移动平均法[8]基础上发展起来的一种时间序列分析预测法,既可以同全期平均法一样无遗漏地对历史数据加以利用,又可以同加权移动平均法一样为近期数据赋予更大权重的热点。指数平滑法兼容了全期平均和移动平均的优点,在不舍弃历史数据的情况下,仅给予逐渐减弱的影响程度,即随着数据的远离,赋予逐渐收敛为零的权数;并且指数平滑法对不同时间访问量赋予的权值具有伸缩性,可以通过赋予不同平滑指数来更改权值的变化速度。

    文献[9]提出一次指数平滑(Single Exponential Smoothing,SES)和二次指数平滑(Second Exponential Smoothing,DES)来预测各个阶段的内容流行度,作者从YouTube以天为观察单位提取每个内容流行度从上传到观测时间结束的真实轨迹,在每个观测单位分别采用SES和DES来根据观测时间前的流行度从而预测当前时间的流行度。

    指数平滑预测法的优点是仅需少量数据资料,便可预测出短期的内容流行度值。但由于指数平滑法对近期数据所赋予的权重高,而对远期数据的参考性弱,无法对远期流行度进行预测,只能做短期的预测。

1.1.2 多项式回归预测

    在实际工作中,人们经常采用多项式回归模型来解释自变量与因变量的相关关系[10]。多项式回归预测通过多项式回归法拟合内容流行度随时间变化的曲线,得到因变量内容流行度与自变量时间的变化函数,这一模型可以表示为,流行度等于时间的各次项与对应回归系数的乘积之和。在拟合过程中,主要是通过增加时间变量的高次项推导出逼近真实的时间函数,推导时主要是找到各次项的合适系数。

    文献[11]研究提出属于同一类别的内容具有相同的流行度随时间变化的曲线相似,多项式回归预测可以得到某一类内容流行度随时间变化的规律,因此该规律可以用于该类内容流行度的长期和短期预测。

1.1.3 Savitzky-Golay滤波预测

    Savitzky-Golay滤波预测通过Savitzky-Golay滤波器平滑观测流行度随时间的变化曲线,以便最好地保留流行度采样曲线的特征。文献[12]利用Savitzky-Golay滤波预测得到流行度时间模型,可表示为围绕时间观测窗口中心k的n次多项式,该模型能够使得预测值和实际值的累积平方误差值最小。

1.2 基于用户偏好的预取

    前面基于流行度的预取技术是利用流行度变化反映内容的访问趋势,这种趋势相对于个体用户偏好而言存在明显的差异,造成边缘节点预取的部分内容被闲置。为了解决上述问题,有学者提出了基于用户偏好的预取,并且相关研究统计证明了用户偏好在一定时间内是保持稳定的,这一特性为基于用户偏好的预取的可行性提供了有力的保证。

    在对从未访问过的新内容做预取时,基于流行度的预取由于缺乏历史数据作为分析基础,无法做出正确的预测,但基于用户偏好预取则可以根据用户兴趣内容标签集合并结合用户请求预判用户偏好,指导预取的执行。基于用户偏好的预取一般分为两个阶段,第一个阶段是获取用户偏好;第二个阶段是根据用户偏好制定预取策略。

    文献[13]采用文档主题生成模型(Latent Dirichlet Allocation,LDA)[14]获取内容的潜在主题,并用对称Jensen-Shannon散度[15]衡量内容主题与用户兴趣主题之间的相似性,节点将预取相似性较高的内容以供用户未来请求。

    文献[16]通过预测函数对用户为评分内容进行预测,将评分较高的一部分内容预取到边缘节点。在该文献中,作者首先将用户偏好向量定义为用户对不同内容属性的偏好度,偏好度表示用户访问的全部内容属性叠加后该属性所占的权重;然后通过余弦相似性得到群体用户的偏好相似度;最后根据用户评分相似性和偏好相似性带入对内容评分预测函数中得到内容的评分,并预取评分较高的内容。

1.3 基于社交网络的预取

    据统计,网络中大量HTTP流量来自于在线社交网络(Online Social Network,OSN)中的带宽密集型媒体内容[17]。在线社交网络可以捕捉朋友之间的联系,且许多在线社交网络上可以获取用户的地理位置,这为基于社交网络的预取提供了实施条件。媒体提供商通常依靠CDN将其内容从内容源服务器分发到多个位置,基于社交关系的预取利用OSN上人们的社交关系了解内容地理传播方式,从而改善CDN用户访问体验。

    社交预取主要利用社交网络中的朋友关系信息、用户的交互行为,如提到、转发、评论等,来分析社交网络的朋友关系。通过引入朋友关系强弱程度的预取模型,主动将某用户访问内容分发给可能访问该内容的朋友附近的CDN节点,使其朋友下载内容时减少延迟。

    SASTRY N[18]等人构建了Buzztraq模型,该模型根据用户的朋友数量和朋友的位置信息,将用户发布的内容副本放置在更靠近较多用户朋友的位置,以满足未来请求。但该模型仅仅强调了捕捉潜在的下一个内容访问地址,并没有考虑服务器带宽和存储等复杂约束。

    KILANIOTI I[17]提出了利用OSN提取用户活动的动态预取策略,并且考虑到网络拓扑、服务器位置以及缓存容量的限制的情况,实验证明了结合OSN的预取模型能够改善CDN的性能。 

1.4 基于用户移动性的预取

    CDN中大多数预取方案针对的是固定网络,而据Cisco公司统计,在2016年,全球移动数据流量较2015年增长了63%,其中移动视频流量占移动数据流量总量的60%,并且移动数据流量和移动视频流量在未来几年内还将呈现持续增长趋势[19]。同样,CDN网络也将面临着大量移动用户接入的问题,文献[22]通过测量发现移动用户的缓存命中率远低于LRU缓存策略下的静态用户的缓存命中率。因此用户移动性是CDN缓存和预取策略的重要因素。

    由于个人的移动性存在一定的随机性,CDN节点下可以分为不同的用户群体,不同群体与CDN节点存在不同的关联程度,因此可以通过构建群体移动模型来优化CDN预取。文献[20]引入了PageRank的人群移动性内容传播(Crowd Mobility-based Content Propagation,CMCP)解决方案,通过关注不同用户群体移动用户的比例,预测未来的内容需求分配。

1.5 预取方法的比较

    以上根据预取时关注的对象不同,介绍了现有的预取方式,包括基于流行度的预取、基于用户偏好的预取、基于社交网络的预取和基于用户移动性的预取,表1给出了几种预取方式的对比。

zs1-b1.gif

    基于流行度的预取仅根据内容流行的趋势,一般采用统计学方法,实现相对简单。它不依赖于用户的特性,可以作为服务器端宏观地控制边缘节点预取。早期的IPTV也是采用该预取方式,将部分流行度高的内容预取到边缘节点上,从而提高用户的访问质量。但是基于流行度的预取技术缺乏对用户访问特性的研究,而且不同的用户群体之间也存在着明显的差异,比如在大学里学生一般大量地访问科技文献和技术视频,而小区家庭中一般倾向于少儿视频、体育赛事等一系列偏向于娱乐的业务需求。并且随着P2P与CDN的结合,边缘CDN节点越来越向用户端靠近,节点附近用户偏好对边缘节点的缓存影响也愈加显著,因此解决用户访问内容差异性问题成为了提高预取质量的重要所在。基于用户偏好的预取根据用户的历史访问记录构建用户画像,提取用户群体共同的内容偏好,预取时根据用户偏好对当前流行的内容和最新发布的内容进行预取。它给用户访问提供更精确服务的同时,采用数据挖掘方法又给节点带来了大量的运算开销。由于内容的传播很多的是由用户之间的推荐,并且大量的内容也在社交网络上发布。基于社交网络的预取,通过用户之间的社交关系,也可以提高用户的访问质量。基于用户移动性的预取主要应用于移动互联网中的内容预取,增加了用户对移动性对边缘节点内容需求的影响因素,以提高节点的服务质量。

2 评价标准

    为了对不同预取技术进行公平对比,学术界通常采用命中率[21]、准确率[22]、带宽成本[23]以及平均响应时延[24]评估预取技术对CDN系统性能的改善效果。

2.1 命中率

    CDN系统中希望将用户请求重新定向到离用户最近的边缘服务器上,以提高用户访问速度。在实际中,如果当服务器节点预先存储有用户请求内容时称之为命中;如果没有事先缓存称为未命中。命中率(Hit Rate,HR)体现了预取和缓存对用户访问加速的贡献,定义为:

    zs1-gs1.gif

其中SR表示命中的请求数,NR表示没有命中的请求数。

2.2 准确率

    命中率要求预取应该在用户访问之前缓存内容增加用户的体验质量,但是如果用户并没有访问,则预取会浪费网络资源和服务器存储资源。当预取规则没有准确地获取用户需求时,节点服务器会从源服务器下载必要的内容,导致服务器缓存资源浪费、带宽成本增加。准确率可以间接表示预取规则的有效性,定义为:

    zs1-gs2.gif

其中TP表示用户访问的预取内容数量,FP表示用户没有访问的预取内容数量。

2.3 带宽成本

    由于用户访问类型的多样性,为了提高命中率则需要频繁地进行预取操作,会造成边缘节点和内容服务器之间产生大量额外的带宽消耗和节点服务器过于频繁的缓存、删除操作,从而降低用户的体验质量。通常用带宽成本作为预取触发的约束条件,带宽成本可定义为:

    zs1-gs3.gif

其中,Pband表示包含有预取策略的CDN系统下满足用户需求所需的总带宽,Rband表示没有预取策略的原CDN系统下用户请求所需的总带宽。

2.4 平均响应时间

    CDN的主要目标是提高用户访问速度,平均响应时间的变化直接地反映了预取策略对CDN的优化程度,现实中预取往往在减少平均响应时间和带宽成本之间进行权衡。平均响应时间是CDN系统性能和用户体验质量的重要指标,定义为:

    zs1-gs4.gif

其中,M是用户请求的总数量,ti代表第i个请求开始时到连接结束时间。

3 未来研究方向

    CDN预取技术是提升用户体验的有效方式,但CDN网络本身仍有一些不足,信息时代的来临和市场需求都迫切需要将CDN与新型技术进行融合,主要有软件定义网络(Software Define Network,SDN)[25]、网络功能虚拟化(Network Function Virtualization,NFV)[26]技术以及深度学习技术,使其实现边缘智能和自适应组网等功能。未来对CDN预取技术研究将更加关注于CDN网络与新技术融合带来的挑战。

3.1 SDN/NFV技术与CDN网络融合

    目前,大多数的CDN网络是由各大厂家研制开发的专用型设备组成的,对多样性的业务支持的能力不足,且自建网络方式产生了资源独占的现象,阻碍着CDN行业的快速发展。融合SDN/NFV技术到CDN网络,利用NFV的软硬件解耦和功能抽象特点,以及利用SDN的设备控制与数据分离的特征,可以加强CDN的多业务智能化服务能力[27]

    在这种契机下,由差异化业务给CDN中内容预取带来的挑战:不同业务对应内容的格式、类型以及大小不尽相同;针对不同业务下相同类型的内容的用户需求也有所不同;不同业务的用户访问场景也存在差异。如何针对差异化业务预取合理的内容,满足不同业务下用户的需求,实现CDN预取的灵活性,是下一步CDN预取技术的关键所在。

3.2 深度学习与CDN网络融合

    目前视频提供商依赖于地理上分布的CDN网络,将视频内容尽可能靠近用户放置,以提高视频质量并避免服务器端的单点故障。视频流量爆炸式增长严重增加了CDN网络的负担,准确分析视频的特征并预取用户需求的视频内容,是减轻网络负担的重要途径。相对于自然语言的分析,对视频数据的分析更为困难。深度神经网络通过分层学习过程,能够有效地提取输入数据的高维度特征,显著提升计算机视觉、自然语言处理以及语音识别的精确度[28]

    深度神经网络给CDN中视频预取带来新的契机,例如卷积神经网络(Convolutional Neural Networks,CNN)[29]能够仿造生物的视知觉(Visual Perception)[30]机制,可以应用于预取机制中的视频分类和用户偏好挖掘。此外,递归神经网络(Recursive Neural Network,RNN)[31]能够对时间顺序的自然语言、语音识别等数据的变化进行建模,可用于预取时预测用户需求。深度学习可以为CDN预取中内容分类方法、用户兴趣挖掘等提供了更优的解决方法,随着流媒体内容的发展,对视频、音乐的预取将更加依赖于深度学习。

4 结论

    本文以预取关注对象为基础,对近年来CDN预取技术进行综述,总结归纳出基于流行度的预取、基于用户偏好的预取、基于社交网络的预取以及基于用户移动性的预取这四类预取方式。基于流行度的预取关注了网络中普遍的内容流行情况,本质上反映出内容的请求趋势,它是当前一种主流的预取方式。基于用户偏好的预取通过挖掘群体用户的偏好,使预取技术更加适应于用户的个性化需求,进一步提高了边缘节点中缓存内容的准确率。基于社交网络的预取根据用户之间的联系构建内容传播的模型,预测用户访问内容传播位置,提高边缘节点的缓存命中率。基于用户移动性的预取根据用户的移动性对节点内容需求的影响,动态地调整内容预取,提高了移动场景下节点服务器的缓存命中率。预取机制的主要目的是为了提高CDN网络的缓存命中率和准确率,但是也会带来一定的网络资源消耗,因此可以大规模实施的预取技术需要控制预取的带宽成本。CDN网络与新技术融合发展是满足信息时代需求的必然走向,本文分析了新型技术融合下预取技术面临的挑战,并给出了可能的研究方向。

参考文献

[1] “互联网+”时代企业办公自动化研究[J].信息技术与标准化,2015(8):66-69.

[2] 尹芹,华新海.基于融合CDN构建未来智能内容管道[J].电信科学,2015,31(4):33-37.

[3] HWANG K,SUH D Y.Reducing perceptible IPTV zapping delay using CDN cache server[C].2013 International Conference on ICT Convergence(ICTC),2013:738-739.

[4] PARMAR J,VERMA J.State-of-artsurvey of various web prefetching techniques[C].International Conference on Inventive Computation Technologies.IEEE,2016:1-7.

[5] 王道谊,周文安,刘元安.内容分发网络中内容流行度集中性的研究[J].计算机工程与应用,2011,47(6):102-104.

[6] 聂华,张敏,郭敬荣,等.基于内容流行度差异性的CDN-P2P融合分发网络缓存替换机制研究[J].通信学报,2015,36(s1):9-15.

[7] SZABO G,HUBERMAN B A.Predicting the popularity of online content[J].Communications of the ACM,2010,53(8):80-88.

[8] 李琦,陈玉新.移动平均法的滞后问题[J].统计与决策,2008(22):152-153.

[9] HASSINE N B,MARINCA D,MINET P,et al.Caching strategies based on popularity prediction in content delivery networks[C].2016 IEEE 12th International Conference on Wireless and Mobile Computing,Networking and Communi-cations(WiMob),New York,2016:1-8.

[10] 付凌晖,王惠文.多项式回归的建模方法比较研究[J].数理统计与管理,2004,23(1):48-52.

[11] HASSINE N B,MARINCA D,MINET P,et al.Popularity prediction in content delivery networks[C].2015 IEEE 26th Annual International Symposium on Personal,Indoor, and Mobile Radio Communications(PIMRC),Hong Kong,2015:2083-2088.

[12] HASSINE N B,MARINCA D,MINET P,et al.Expert-based on-line learning and prediction in content delivery networks[C].2016 International Wireless Communications and Mobile Computing Conference(IWCMC),Paphos,2016:182-187.

[13] Hu Wen,Huang Jiahui,Wang Zhi,et al.MUSA:Wi-Fi AP-assisted video prefetching via Tensor Learning[C].2017 IEEE/ACM 25th International Symposium on Quality of Service(IWQoS),Vilanova i la Geltru,2017:1-6.

[14] BLEI D M,NG A Y,JORDAN M I.Latent Dirichlet Allocation[J].Journal of Machine Learning Research,2003(3):993-1022.

[15] LIN J,LIN J H.Divergence measures based on the Shannon entropy[J].IEEE Transactions on Inform Theory,1991,37(1):145-151.

[16] 田瑞云.基于Hadoop的CDN-P2P系统中内容预测机制研究与实现[D].北京:北京邮电大学,2013.

[17] KILANIOTI I.Improving multimedia content delivery via augmentation with social information: the social prefetcher approach[J].IEEE Transactions on Multimedia,2015,17(9):1460-1470.

[18] SASTRY N,YONEKI E,CROWCROFT J.Buzztraq:predicting geographical access patterns of social cascades using social networks[C].Proceedings of the Second ACM Euvosys Workshop on Social Network Systems,2009:39-45.

[19] 唐红,韩健,段洁,等.基于内容流行度的移动CCN缓存策略研究[J].重庆邮电大学学报(自然科学版),2018,30(1):119-126.

文献[20]-[31]略





作者信息:

王舒平,张  毅,韦文闻,杨  硕,何  皇

(重庆邮电大学 通信与信息工程学院,重庆400065)

内容分发网络 服务质量 内容预取技术 资源利用率