一种命名数据网络的视频全域协作缓存算法

胡亚萍,王子磊

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

0 概述

目前网络中视频流量呈迅速增长趋势,传统网络已难以满足用户对视频的需求。命名数据网络[1](Named Data Networking,NDN)是一种以内容为中心的未来网络架构,在NDN中,每个节点具有一定的缓存功能,缓存该视频节点可以满足用户的视频需求。缓存可以显著降低用户访问时延,减小跨网间传输流量,减轻服务器负载[2]。然而,相对互联网的海量视频内容,节点内缓存容量有限。因此,如何制定缓存决定策略是NDN研究的关键问题之一。

NDN运行时默认采用全缓存(Leave Cache Everywhere,LCE)策略,该策略操作简单,易于实现,但是其并未考虑与其他节点间的缓存协作,容易造成网络中大量缓存内容冗余。文献[3]提出一种概率型缓存方案ProbCache,综合考虑节点缓存能力、待缓存节点到客户端的距离等因素,从而确定内容缓存概率。此外,文献[4]也做了相关研究。但是,上述方案都只进行了请求路径上的协作缓存,并未实现更大规模(如自治域)的协作,冗余下降有限。针对NDN路径缓存协作的局限性,研究者考虑将软件定义网络(Software Defined Networking,SDN)[5]和NDN进行结合[6-7],引入集中式控制器进行全域协作,从而提升缓存性能。为了实现视频域内协作缓存,文献[8]构建一种混合整数规划模型,将内容简单分组后使用优化器进行求解,但该模型限制了求解规模。文献[9]构建一种全局协作缓存模型并提出OPT-GA求解算法,OPT-GA算法对请求内容按流行度排序,分别使用遗传算法进行求解,导致热门内容大量冗余,中等热度内容没有缓存,该算法未能充分利用缓存空间。

针对以上方案的不足,本文首先建立一种全域协作缓存模型,针对求解模型难度较大的特点,给出一种灰狼非法位置更正算法并引入sigmoid函数,然后在灰狼优化(Grey Wolf Optimization,GWO)算法的基础上进行改进,得到二进制灰狼优化算法IBGWO,最后综合IBGWO算法和贪心算法,提出用于模型求解的预留协作缓存算法RCC。

1 视频缓存模型

本文将一个自治域看成一个协作缓存整体,每个缓存周期开始时执行视频协作缓存算法,确定各个缓存节点应该缓存的视频,然后缓存内容进行周期性更新。考虑到节点缓存空间有限,此处只考虑缓存目标周期内请求的热门视频。本文的优化目标是优化给定周期内给定热门集的用户请求视频时延。

1.1 问题模型

1.2 数学模型

根据上述已知条件和变量假设,以最小化用户请求热门视频时延(用跳数表示)为目标,给出目标函数及相关约束:

(1)

Subject to:

(2)

(3)

(4)

(5)

∀m,v∈V,∀n∈N

(6)

上述模型问题是一个整数规划且属于NP-hard[12]的问题,其随着节点数和视频数的增加,计算复杂度显著增加。1.3节将提出一种新的预留协作缓存算法,用以较快求得该问题的近似最优解。

1.3 求解算法

考虑到少数视频具有很高的流行度,因此,每个节点尽可能选择本节点请求量较高的视频进行缓存,从而减小请求跳数。但是,各个节点均独立缓存,容易造成整体缓存冗余,因此,还需留一部分空间用于协作缓存,以增加缓存视频的种类数,从而满足视频的覆盖性要求。由于本地缓存的具体缓存空间大小难以控制,因此可优先满足视频覆盖性要求,然后在各个节点剩余缓存空间贪心地缓存本节点尚未缓存的请求频率高的视频。这样既满足了本地缓存热门视频的需求,又实现了选中视频集域内全覆盖的目标。此外,将缓存空间分为2个部分,还能避免由全部空间用于全域协作缓存所带来的高计算复杂度问题。具体求解步骤如下:

1)解决视频覆盖问题,思路是使视频满足覆盖性要求,每个视频只缓存一份,请求只能从缓存该视频的唯一节点处获得。此时,原问题转化为:

(7)

Subject to:

(8)

(9)

(10)

显然,该问题还是一个NP-hard问题,目前较少有很好的求解策略,只能通过启发式算法来求解。

GWO算法[13]是一种基于灰狼群体捕食所设计的启发式算法,具有原理简单、全局搜索能力强等特点,在函数优化方面已被证明其收敛速度和求解精度均优于粒子群优化算法[14]。

GWO算法的基本思想是效仿灰狼捕食过程,其对候选解进行分级,将当前适应度值最佳、第二、第三的解分别记为α、β、δ,其余的候选解记为ω,猎物的位置即为问题的最优解。捕食(优化)过程中,ω依据α、β、δ更新自己的位置。具体的更新过程如图1所示。

图1 GWO算法位置更新示意图

在搜索空间先随机产生一群灰狼,进化过程中,由α、β、δ狼估计猎物(全局最优解)的位置,其他狼分别计算自己与α、β、δ狼的距离,以此来估计自身与猎物的距离,然后逐渐向猎物靠近、包围,最终将猎物成功捕获。

该算法数学描述为:

Dα=|C1·Xα(t)-X(t)|

(11)

Dβ=|C2·Xβ(t)-X(t)|

(12)

Dδ=|C3·Xδ(t)-X(t)|

(13)

(14)

(15)

(16)

(17)

式(11)～式(16)计算ω狼距离α、β、δ的距离,式(17)判断ω狼向猎物移动的方向。其中,t为当前迭代次数,X(t)为灰狼当前位置,X(t+1)为灰狼下一次迭代位置,C=2r1,A=2ar2-a,a随迭代次数在[2,0]间线性递减,r1、r2为[0,1]间的随机值。

2)使用GWO算法求解视频覆盖问题。每种缓存方案X对应一只灰狼,灰狼位置的变化对应缓存方案的更新。然而,要使用GWO算法进行求解,首先需要解决以下2个问题:

(1) GWO算法对应的位置更新函数(式(17))为连续函数,更新的位置可能是搜索空间中的任何一处,而本文求解的X中每个元素X(v,n)是一个非0即1的值,其是离散二进制的。

(2)GWO算法适用于求解无约束的优化问题,而本文适应度函数受式(8)～式(10)约束。

针对问题(1),本文使用sigmoid函数将灰狼位置由连续空间转化到离散空间,且只在0和1间转换。具体表示为:

(18)

(19)

其中,r为[0,1]间的随机值,式(18)每次更新X中的一个元素值。

针对问题(2),灰狼在迭代更新位置时,如果位置不符合式(8)～式(10)的约束,则定义为非法位置,需要将位置调整到合法的搜索空间。式(8)表示X矩阵每一列的列和均为1,对应于灰狼每个列向量n的元素和为1;式(9)表示X矩阵每一行的行和均小于缓存容量,对应于灰狼的每个行向量v的元素和小于缓存容量;式(10)可以直接由式(18)保证。上述约束转化为灰狼位置约束,即对于每只灰狼,其位置的每一行的和不能大于c,每一列的和必须等于1,否则为非法位置。

在灰狼位置更新过程中,采用如下算法对位置进行检测与更正。

算法位置检测与更正

1)计算X每一行的行和与每一列的列和;

2)初始化列j=1;

3)处理第j列;

4)如果j=|N|+1,即处理完所有列,转到步骤14);如果第j列列和大于1,转到步骤5);如果第j列列和等于1,转到步骤12);如果第j列列和等于0,转到步骤13);

5)初始化行i=1,初始化记录行和合法的行号的集合Set为空集;

6)处理第i行;

7)如果i=|V|+1,即处理完该列所有行,跳到步骤9);否则判断该行元素X(i,j)为否为1,为1则跳到步骤8),为0则更新行号i=i+1,跳到步骤6);

8)如果该行行和不合法即该节点缓存视频数超过缓存容量,更新X(i,j)为0并更新该行的行和;否则用集合Set记录该行行号,更新i=i+1,跳到步骤6);

9)如果集合Set不为空,从Set中随机选择一个元素l,保持X(l,j)为1,将Set中所有其他元素u对应的X(u,j)中的元素变为0,并更新u行行和;

10)如果集合Set为空,选择行和最小的行l(如果有多个,随机选一个),更新X(l,j)为1,并更新l行行和;

11)更新j=j+1,跳到步骤3);

12)遍历行选择X(i,j)为1的行i,如果该行行和合法,则更新j=j+1,跳到步骤3);否则更新X(i,j)为0并更新该行行和;

13)选取行和小于缓存容量的行的集合,从集合中随机挑选一个行号l使得X(l,j)为1,并更新该行行和,更新j=j+1,跳到步骤3);

14)输出X,结束算法。

该算法总体思想是对每个缓存矩阵X,以列为单位进行遍历,即遍历每个视频,其域内缓存的数量只有3种情况:超过一份(执行步骤5)～步骤11)),正好一份(执行步骤12)～步骤13)),尚未缓存(执行步骤13))。当缓存超过一份时,选择一个节点进行缓存,其余节点均不缓存(步骤8)～步骤10));当正好缓存一份时,如果缓存该视频的节点未超过缓存容量,则不作处理,否则从缓存节点移除该视频,随机选取一个还剩有缓存空间的节点进行缓存(步骤13));当尚未缓存视频时,直接执行步骤13)。

上述2个问题都解决后,将使用IBGWO算法求解视频覆盖问题。首先初始化k只灰狼,每次选取适应度最佳(式(7)最小)的3只狼,记为Xα、Xβ、Xδ,其他狼依据这3只狼的位置更新自己的位置信息,位置更新过程中使用位置检测与更正算法对非法位置进行更正,逐次迭代,当达到最大迭代次数时,结束算法。IBGWO算法处理步骤如下:

1)使用只包含0、1元素的随机矩阵初始化k只灰狼的初始位置Xi,i=1,2,…,k;

2)初始化参数a、A和C,初始化迭代次数iter=1;

3)将式(7)作为适应度函数,分别计算每只灰狼的适应度值,将适应度值最小、第二小、第三小的灰狼分别记为Xα、Xβ、Xδ,并记录Xα的适应度值;

4)进行第iter次迭代;

5)对每只灰狼Xi使用式(18)更新位置信息,更新后使用位置检测与更正算法更正不合法的位置信息;

6)更新a、A和C;

7)重新计算每只灰狼的适应度值,更新Xα、Xβ、Xδ,并记录Xα的适应度值;

8)迭代次数加1,如果达到最大迭代次数,跳到步骤9);否则跳到步骤4);

9)输出Xα及对应的适应度值,结束算法。

至此,视频覆盖问题已经解决,将它与贪心算法进行结合,得出求解原模型的RCC算法。总体思路是先求解视频覆盖问题,得到缓存矩阵X,随后针对每个节点剩余的缓存空间,贪心缓存本节点覆盖问题中未缓存的热门请求视频,直至用完缓存空间。结合两者,得到最终的视频缓存矩阵X。RCC算法具体步骤为:

1)使用IBGWO算法求解全局缓存问题,得到全域协作缓存矩阵X;

2)初始化路由器节点集合R=V;

3)如果R不为空,则从R中选择一个路由器节点v,并从R中去除节点v;否则跳到步骤10);

5)将节点v上请求的视频按请求频率的降序进行排列;

6)初始化排序后的视频编号i=1;

7)如果还剩余缓存空间,则执行步骤8);否则跳到步骤3);

8)如果X中未缓存编号i对应的视频,则缓存,并更新X以及剩余的缓存空间c*=c*-1;

9)更新视频编号i=i+1,跳到步骤7);

10)使用X利用式(6)得到矩阵Z,并计算式(1)的值;

11)输出缓存矩阵X和对应的式(1)的值。

2 性能评价

2.1 仿真环境与评价指标

本文采用文献[8]中所用的随机网络拓扑,该域共包含15个路由器,请求的视频集为10 000个服从参数为0.8的Zipf分布视频块,每块大小为15 MB,约等于YouTube视频平均大小[15]。终端用户发出视频请求,请求服从λ=50个/s的泊松分布,总请求数为1 000 000。如果请求视频域内尚未缓存,则从域外服务器获取,域外响应跳数取网络平均响应跳数,本文取12跳[16]。采用文献[11]中所述的基于SDN的路由方式,即缓存视频全域可见,可直接将请求路由到最近的缓存节点或网关节点。

为评价缓存策略的效果,本文采用缓存命中率和平均请求跳数2个评价指标。缓存命中率即域内服务的请求数与总请求数之比,其值越高,则有越多的请求在域内直接命中,可以节省域外流量,同时减小服务端负载,该值是一个重要的缓存性能指标;平均请求跳数即视频从服务节点到客户端经历的总跳数与所有请求数之比,该值反映客户端平均响应时延,对于视频类请求而言,较大的响应时延将严重影响用户体验。

2.2 仿真结果

2.2.1 缓存性能对比

将RCC算法与NDN典型缓存策略LCE和ProbCache以及文献[5]中使用的用遗传算法实现全局缓存的方案(OPT-GA)作对比。RCC中热门视频数设为域内最大缓存容量数的0.9倍。RCC和OPT-GA仿真过程中基本不发生替换,LCE和ProbCache采用LRU替换策略。现有研究普遍认为缓存容量、内容总量和Zipf参数α对缓存性能影响很大,故本文着重验证缓存容量和内容总量的比值与视频流行度α对缓存性能的影响。

1)缓存大小对缓存性能的影响

选取视频流行度参数α=0.8。缓存大小对缓存性能的影响如图2所示。

图2 缓存大小对缓存性能的影响

由图2(a)可以看出,随着域内节点缓存容量的增大,LCE算法、ProbCache算法、OPT-GA算法和RCC算法域内缓存命中率均有所提高,其中,RCC算法和OPT-GA算法整体比LCE算法和ProCache算法缓存命中率高,原因是前面2种算法实现了更大范围的缓存,网络中缓存冗余降低,缓存视频种类数增多,导致缓存命中率增加。RCC算法比OPT-GA算法命中率高,原因是OPT-GA算法是按请求度由高到低对每个视频分别使用遗传算法进行求解,导致一些热门影片缓存过多,一些中等热度视频没有空间缓存,从而命中率低于RCC算法。由图2(b)可以看出,平均请求跳数随着缓存容量的增大而减小。缓存命中率越高,更多的请求在域内被命中,相对域外,所需接入跳数显著减小。而随着缓存空间的增大,RCC算法平均跳数有所减小,一方面因为局部缓存热门视频增多,更多请求直接在接入路由器节点命中,域内跳数减小;另一方面因为域内协作缓存视频种类多,路由到域外的请求少,导致平均请求跳数减小。

2)视频流行度α对缓存性能的影响

考虑到一般缓存空间占总的缓存容量的5%左右,本文选定缓存容量与内容总量的比值为6%。视频流行度α对缓存性能的影响如图3所示。

图3 视频流行度对缓存性能的影响

由图3(a)可以看出,4种缓存方案的缓存命中率随着视频流行度α的变化情况是,α从0.8变化至2.0时,缓存命中率均有非常大的提升,当α较小时,RCC算法优势明显,此时RCC算法大幅度地增加了域内缓存视频的种类数。当α为1.7时,4种算法缓存命中率都接近100%,原因是此时流行视频很集中,缓存策略性能相差不大。图3(b)也呈现类似的结果,α较小时,RCC算法优势较大,因为缓存视频种类多,域外请求数相对另外3种算法少,导致平均请求跳数少。

2.2.2 计算性能对比

为了验证RCC算法的效率,选用CVX激活gurobi优化器对本文模型进行求解,gurobi能以较快的速度求解混合整数规划问题,是目前最好的优化器之一。在相同条件下,将RCC算法与CVX分别从内存消耗、求解时间和解的质量三方面作对比,结果如表1～表3所示。

表1 消耗内存对比 GB

表2 消耗时间对比 s

表3 域内平均请求跳数对比

由表1可以看出,本文策略只消耗少量内存资源,因为求解过程中,其只存储了少量的灰狼位置变量,而使用CVX优化器求解则非常消耗内存资源,特别是视频种类数较多时,CVX消耗内存显著增长。当缓存视频数为5 000时,CVX优化器消耗的内存为RCC算法的114倍。实验时缓存视频种类数达到6 000时,使用CVX优化器求解时计算机显示内存不足,而RCC算法仍只消耗少量内存,因此,RCC算法更适合求解大规模缓存问题,这也更符合现实情况。由表2可以看出,RCC算法求解时间始终小于CVX优化器,而且随着域内缓存视频种类数的增大,CVX优化器求解时间显著增长。表3显示两者的求解质量,从中可以看出,使用RCC算法求解与使用CVX优化器求解,性能相差6%左右,因此,RCC算法能以较少的时间和较少的内存求得近似最优解,规模越大,其优势越明显。

3 结束语

为解决传统视频分发启动时延迟较大等问题,本文针对NDN设计一种视频协作缓存算法RCC。综合使用贪心算法和改进的二进制灰狼算法,分别求解本地热门缓存问题和全域协作缓存问题。仿真结果表明,相较于缓存策略LCE算法、ProbCache算法和OPT-GA算法,该算法在缓存命中率和平均请求跳数方面均有明显提升。下一步将解决动态条件下用该视频放置策略时的视频请求调度和路由问题,即对于域内有多个缓存该视频的节点,如何实时选择合适的服务节点及相应的路由策略。

[1] ZHANG L,AFANASYEV A,BURKE J,et al.Named data networking[J].ACM SIGCOMM Computer Communication Review,2014,44(3):66-73.

[2] 曲 桦,王伟萍,赵季红.内容中心网络中一种改进型缓存机制[J].计算机工程,2015,41(3):41-46.

[3] PSARAS I,CHAI W K,PAVLOU G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the 2nd ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:55-60.

[4] CHO K,LEE M,PARK K,et al.Wave:popularity-based and collaborative in-network caching for content-oriented networks[C]//Proceedings of 2012 IEEE Conference on Computer Communications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

[5] MCKEOWN N.Software-defined networking[J].INFOCOM Keynote Talk,2009,17(2):30-32.

[6] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[7] SYRIVELIS D,PARISIS G,TROSSEN D,et al.Pursuing a software defined information-centric network[C]//Proceedings of 2012 European Workshop on Software Defined Networking.Washington D.C.,USA:IEEE Press,2012:103-108.

[8] KIM Y,YEOM I.Performance analysis of in-network caching for content-centric networking[J].Computer Networks,2013,57(13):2465-2482.

[9] 胡 骞.以内容为中心的网络中缓存技术的若干问题研究[D].北京:北京邮电大学,2015.

[10] LIU R,YIN H,CAI X,et al.Cooperative caching scheme for content oriented networking[J].IEEE Communications Letters,2013,17(4):781-784.

[11] AUBRY E,SILVERSTON T,CHRISMENT I.SRSC:SDN-based routing scheme for CCN[C]//Proceedings of the 1st IEEE Conference on Network Softwarization.Washington D.C.,USA:IEEE Press,2015:1-5.

[12] BAEV I,RAJARAMAN R,SWAMY C.Approximation algorithms for data placement problems[J].SIAM Journal on Computing,2008,38(4):1411-1429.

[13] MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.

[14] 龙 文,赵东泉,徐松金.求解约束优化问题的改进灰狼优化算法[J].计算机应用,2015,35(9):2590-2595.

[15] CHE X,IP B,LIN L.A survey of current YouTube video characteristics[J].IEEE Multimedia,2015,22(2):56-63.

[16] FEI A,PEI G,LIU R,et al.Measurements on delay and hop-count of the Internet[EB/OL].[2017-04-05].http://nrlweb.cs.ucla.edu/nrlweb/publication/download/281/garyglcm98.pdf.