基于动态流行度与请求代价的命名数据网络缓存策略

郭 晨,郑 烇,丁 尧,王 嵩

(中国科学技术大学 自动化系 未来网络实验室,合肥 230026)

0 概述

为从根本上解决传统IP网络传输效率低的问题,一类以信息为中心的新型网络体系——信息中心网络(Information-Centric Networking,ICN)被提出[1]。命名数据网络(Named Data Networking,NDN)[2]是ICN的主流网络架构之一[3],NDN网络泛在化的缓存能有效减少用户的等待时延,节约带宽资源,减轻服务器负载。NDN网络缓存策略主要分为2个方面:缓存决策与缓存替换。

为高效地进行缓存替换,有不少经典NDN缓存替换策略被提出:LRU对最近最少使用的缓存内容进行替换;LFU对使用频率少的内容进行替换[4];Age-based[5]替换策略则对请求代价小的内容进行替换;CCP[6]结合LRU与LFU的特点,实时计算内容的动态流行度,对动态流行度小的内容进行替换。虽然上述策略不同程度地提高了缓存效果,但都是基于单独因素进行缓存内容的替换,而综合考虑各方面的替换因素将能有效提升缓存性能。

缓存决策方面,NDN缓存的默认策略采用的是LCE(Leave Copy Everywhere),该算法在内容返回路径中的每一个节点都会缓存内容,从而产生大量冗余副本,导致网络缓存资源的利用率降低。针对LCE的缺点,RCOne[7]、Betw[8]、ProbCache[9]、LCD[10]、BetwRep[11]、PopBetw[12]等缓存决策策略相继被提出。RCOne算法在内容返回路径中随机地选择一个节点缓存内容,这种随机化的缓存决策易于实现,但并未考虑内容的热度等信息,对缓存性能的提升有限。Betw算法在内容返回时选择兴趣包请求路径上最重要的节点缓存,其他节点不再缓存。对于不同网络拓扑,该策略都取得了较高的网内节点缓存命中率,并减少了内容传输的平均跳数。然而在实际网络中,节点缓存量远小于内容总量,Betw算法会使重要节点负载过大及缓存替换频率过快,导致网络缓存性能降低。

本文综合考虑缓存内容的动态性、流行度和请求代价,提出动态流行度与请求代价结合的缓存替换算法DPCP。在该算法中,节点单独计算每个缓存内容的动态流行度与请求代价(Dynamic Popularity and Cost,DPC)加权值,并在缓存替换时选择动态流行度低、请求代价小的内容。在缓存决策策略方面,为合理选择节点放置缓存,本文提出结合内容的热度信息与节点的重要度信息的缓存决策策略DDP。根据缓存内容的DPC值对内容进行分类,并执行区分化的缓存决策策略,将DPC值大的内容放置在重要节点上,DPC值小的内容随机放置在某一个节点上,从而保证热点内容尽量缓存在相对重要的节点上,同时又避免重要节点处于高频率的内容替换状态,同时充分利用非重要节点的缓存资源,达到提升网络缓存性能的目的。

1 相关技术

缓存技术作为NDN网络的关键技术之一,是NDN网络的研究热点。针对现有缓存策略的优缺点,很多不同的缓存替换策略和缓存决策策略被提出[1]。

现有的NDN缓存替换策略主要有LRU与LFU[4]。LRU(Least Recently Used)主要思想是:当有新内容转发到节点且节点缓存空间已满时,将最久未使用的缓存内容替换掉。LRU主要考虑内容的动态性,认为最近转发的内容很有可能再次被请求。但是如果一个内容每隔一段时间都会被请求一次,LRU算法就会用最近的内容将它替换掉,即使最近的内容很少有人感兴趣。LFU(Least Frequently Used)的核心思想是:给每一个缓存内容进行计数,缓存命中时,计数值加1,缓存替换时将计数值最小的内容替换掉。LFU主要考虑内容的流行度,认为历史流行度高的内容被再次请求的概率大。但是如果请求的内容在动态变化时,LFU算法的性能将下降,原因是:当一个内容过去很流行,即使之后没有人再请求,它也会一直留在缓存中,直到最近的一些被命中次数更多的内容出现。Age-based[5]缓存替换策略给每个缓存内容设置生存时间(Time-to-Live,TTL),距离源服务器越远的缓存内容越能减少用户的请求跳数,TTL就越大,缓存替换时则根据TTL将过期数据替换掉。CCP[6]缓存替换策略结合了LRU与LFU的优势,周期性地统计内容的命中次数,实时计算内容的动态流行度,根据动态流行度进行缓存替换。Age-based替换策略主要考虑内容的请求代价,忽视了内容的动态流行度;CCP替换策略则与Age-based相反。这些典型缓存替换策略的主要问题是考虑因素比较单一,难以获得较好的缓存替换效果。

在缓存决策方面,NDN的默认缓存决策策略主要是LCE。LCE算法的主要思想是在内容返回过程中使每一个节点都缓存内容。该算法复杂度低、实现简单,但是会导致网络中出现大量冗余副本,降低缓存的多样性。

RCOne[7]缓存决策策略采用随机化的思想,在内容返回路径中随机选取一个节点缓存内容。在如图1所示的拓扑结构中,当用户Client A请求内容c1时,源服务器s1提供c1,c1在返回路径中随机选择v1、v2、v3中的某一个节点缓存下来。相比于LCE,RCOne虽然能一定程度上提升网络缓存多样性,但其在缓存放置时既没有考虑内容热度,也没有考虑节点信息,对网络缓存性能的提升有限。

图1 实例拓扑结构

文献[8]提出的Betw缓存决策策略,请求命中后将返回内容只缓存在路径最重要的节点上。由于在重要节点上同一个内容被请求的次数会更多,使得内容在节点上被缓存时间变长,缓存命中率变高,从而提升缓存性能。而节点重要程度是以节点介数作为度量。节点的介数是用来描述节点在网络中重要性的一个度量,源于复杂网络领域,其数学定义如下:

(1)

其中,V是网络拓扑结构所有节点的集合,s、t、v是拓扑结构中不相同的任意3个节点,CB(v)是节点v的节点介数,σs,t是节点s到节点v的所有最短路径数,σs,t(v)是其中经过节点v的最短路径数。节点的介数越大,它在网络中越重要。在图1所示的拓扑结构中,v2的节点介数最大,3个用户节点的请求都会经过v2,Betw策略将内容缓存在v2节点可以满足更多的请求。然而在实际网络中节点缓存大小与网络内容总量相比非常小,因此,重要节点到达的请求数量非常大,节点处于高频率的内容替换状态下,导致热点内容也会出现很快就被替换的情况。此时大量兴趣包到达重要节点后无法实现缓存命中,兴趣包也只能被转发到别的节点,直至内容源端。在图1所示的拓扑结构中,Betw策略会把所有的内容都缓存在v2节点,但v2节点的缓存空间大小有限,高频率的替换状态下导致网络缓存性能的降低。此外,v2之外的其他节点均未放置缓存,也造成了缓存资源的浪费。RCOne、Betw这些缓存决策策略的主要问题都在于没有综合利用内容和节点的特性。

关于NDN网络缓存的研究,多为单独研究缓存替换或者缓存决策。如果将两者有效结合,利用缓存替换策略计算出的节点缓存内容热度信息合理地进行缓存决策,将能有效提高缓存命中率,降低请求平均跳数。

2 本文算法

为提高缓存命中率、降低请求平均跳数,本文结合内容的动态性、流行度、请求代价三方面提出DPCP缓存替换算法,周期性地计算缓存表中每个内容的DPC值。DPC值越小,说明内容的动态流行度与请求代价越小,缓存替换时将DPC值小的内容替换出去。根据缓存内容的DPC值,本文将内容分为热点内容与非热点内容执行DDP缓存决策算法。DDP算法的核心思想是将热点内容放置在内容返回路径中最重要的节点上,非热点内容随机放置在某一节点,使热点内容长时间存储在重要节点上,以期在互联网低层ISP的典型拓扑中获得较好的缓存效果。

2.1 DPCP缓存替换算法

缓存替换算法需要考虑的内容相关因素及主要出发点如下:

1)动态性:适应内容请求的动态变化。

2)流行度:适应内容流行度的变化。

3)请求代价:距离源服务器越远的缓存内容越能减少用户的请求跳数。

DPCP算法分周期测量和计算内容的DPC值。内容在第i个计时周期的动态流行度(Dynamic Popularity,DP)为DP(i),则DPC(i)计算公式如下:

DPC(i)=Hopdata×DP(i)

(2)

其中,Hopdata是内容所在节点距离源服务器的跳数。距离源服务器越远的缓存内容能更大程度地降低经过缓存内容所在节点的用户请求跳数,从而使DPC值越高。动态流行度DP(i)的计算公式如下:

DP(i)=β×DP(i-1)+(1-β)×N(i)

(3)

其中,β是衰减因子,0<β<1,表示上一个周期的DP值在当前周期所占的比例,N(i)表示内容在第i周期被命中的次数,每个节点单独计算CS表中缓存内容的命中次数。结合式(2)、式(3),得出的DPC值递推计算公式如下:

DPC(i)=Hopdata×DP(i)=Hopdata×

(1-β)×(N(i)+β×N(i-1)+…)

(4)

距离当前周期越远的周期,内容的被命中次数在当前DPC值中占的比例越小,说明分周期计算缓存内容DPC值的思想能适应内容请求的动态变化。

为了实现DPCP缓存替换策略,本文在NDN网络原有CS、PIT、FIB表的基础上,增加一个DPC表。

以一个简单实例说明DPCP策略的缓存替换过程。假设β=0.4,已知缓存内容的历史动态流行度His_DP、当前周期命中次数Cache_Hit_Num、距离源服务器跳数Hopdata,可以计算出缓存内容的当前动态流行度Cur_DP、动态流行度与DPC值,如表1所示。

表1 DPC表

在缓存替换时,将DPC值最小的缓存内容替换出去。虽然反映内容/content/1.mpg流行度的DP值是最大的,但是由于它离源服务器的距离太近,不能很好地降低该内容的请求代价,导致其DPC值最小,因此最早地被替换。

2.2 DDP缓存决策算法

NDN网络中用户请求到的内容是由源服务器节点或者请求路由路径中某个节点的CS表提供[13]。为结合内容的热度信息与节点的重要度信息合理地进行缓存放置,本文将内容分为热点内容与非热点内容。由于源服务器提供的内容在请求路由路径中没有缓存副本,说明这个内容在路径中所有节点上的热度都不高,因此被划分为非热点内容。由节点CS缓存表提供的内容,根据DPC值进行划分。内容分类具体如下:

1)热点内容:节点CS表中DPC值位于前40%的内容。

2)非热点内容:源服务器提供的内容,节点CS表中DPC值位于后60%的内容。

兴趣包请求如果被某一个节点CS表中DPC值位于前40%的内容满足,那么返回的内容是热点内容;如果被源服务器或者某一个节点CS表中DPC值位于后60%的内容满足,则返回的内容是非热点内容。根据内容的分类,本文提出了区分化的缓存决策策略(DDP)。具体设计思想如下:

1)热点内容采用基于节点介数的Betw策略,缓存在内容返回路径中节点介数最大的节点上,以满足更多的请求。

2)非热点内容采用随机化的RCOne策略,随机缓存在内容返回路径中的某一个节点上,以降低节点介数大的节点的缓存替换频率,同时也充分利用其他节点的缓存资源。

DDP缓存决策算法的伪代码如下:

算法DDP

初始化(CB=0,hop=0,Bool hot=false)

兴趣包到达节点v:

get(hop,hot);

hop++;

if data in cache

hot=DPC.isHoted(data);//look up the DPC table

hop=random(0,hop);//RCOne

send(data);

else if node v is server and provide data

hot=false;

hop=random(0,hop);

send(data);

else

get(CB);

if CB(v)>CB

CB=CB(v)

end if

forward interest to the next hop

end if

数据包到达节点v:

get(CB,hop,hot);

hop--;

if hot==true

if CB(v)==CB

cache(data);

end if

else

if hop==0

cache(data);

end if

end if

forward data to the next hop;

兴趣包在请求的过程中,需要记录路由路径中所有节点的最大节点介数CB与跳数hop。兴趣包请求被满足时,判断内容是否为热点内容并生成一个1～hop的随机数。热点内容在内容返回的路径中,将路径中每个节点v的节点介数CB(v)与最大节点介数CB进行比较,2个值相同则将内容缓存在这个节点v上。非热点内容每转发1跳,随机数减1,当随机数减为0时,将内容缓存在这个节点上。

3 实验与结果分析

3.1 实验环境与参数配置

3.2 结果分析

图2是在6种缓存策略下节点的缓存容量不同时用户请求在全网的缓存命中率。这个命中率是在节点缓存确定后,一次实验中被网内节点缓存命中的请求占所有用户请求的比例。当缓存决策策略都采用LCE时,DPCP-LCE的全网缓存命中率与CCP-LCE不相上下,相比于LFU-LCE提升了22.9%。这是因为DPCP、CCP缓存替换策略能兼顾内容请求的动态性与历史内容的流行度,根据内容的动态流行度进行缓存替换。当缓存替换策略都采用DPCP缓存替换策略时,DPCP-DDP的全网缓存命中率高于DPCP-LCE、DPCP-Betw策略,相比于DPCP-Betw策略提升了9.2%。对比结果表明,DPCP-DDP缓存策略的全网缓存命中率明显高于其他5种策略。

图2 全网缓存命中率随节点缓存容量的变化

图3是在6种不同策略下请求的平均跳数随节点缓存容量大小的变化。平均跳数是一次实验中所有的用户请求被转发的平均跳数。与图3的全网缓存命中率结果不同,在缓存决策策略采用LCE的情况下,DPCP-LCE的平均跳数比CCP-LCE低8.9%,更低于LRU-LCE、LFU-LCE。与CCP缓存替换策略相比,DPCP缓存替换策略能兼顾动态流行度与请求代价,更有效地降低请求的平均跳数。当缓存替换策略都采用DPCP替换策略时,DPCP-DDP策略的平均跳数比DPCP-Betw策略低7.1%,更低于DPCP-LCE。对比结果表明,DPCP-DDP缓存策略的请求平均跳数是6种缓存策略中最低的。

图3 平均跳数随节点缓存容量的变化

4 结束语

合理利用缓存资源是NDN网络高效传输数据的关键。为实现高效的缓存替换,本文提出结合动态流行度与请求代价的DPCP缓存替换策略。该策略能将动态流行度小、请求代价小的内容替换出去,达到提高全网缓存命中率、降低请求平均跳数的目的。同时,针对如何合理放置缓存副本的问题,进一步提出DDP缓存决策算法。首先对内容进行分类,然后对热点内容与非热点内容采用不同的决策算法,既保证了热点内容尽量缓存在相对重要节点上,又能避免重要节点处于高频率的内容替换状态,同时也充分利用非重要节点的缓存资源,提高了网络缓存的多样性。实验结果表明,将两者结合的DPCP-DDP缓存策略能有效提高NDN缓存的整体性能。

现有的NDN缓存策略一般只考虑内容流行度,较少考虑不同区域或不同时间段内的内容请求特性。为此,下一步将设计邻域协作缓存策略,以提高全网缓存性能。

[1] 张国强,李 杨,林 涛,等.信息中心网络中的内置缓存技术研究[J].软件学报,2014,25(1):154-175.

[2] ZHANG L,ESTRIN D,BURKE J,et al.Named Data Networking (NDN) Project:NDN-0001[R].Palo Alto,USA:Xerox Palo Alto Research Center,2010.

[3] AHLGREN B,DANNEWITZ C,IMBRENDA C,et al.A Survey of Information-Centric Networking[J].IEEE Communications Magazine,2012,50(7):26-36.

[4] PODLIPNIG S,BÖSZÖRMENYI L.A Survey of Web Cache Replacement Strategies[J].ACM Computing Surveys,2003,35(4):374-398.

[5] MING Z,XU M,WANG D.Age-based Cooperative Caching in Information-Centric Networking[C]//Proceedings of International Conference on Computer Communication and Networks.Washington D.C.,USA:IEEE Press,2014:1-8.

[6] RAN J,LU N,ZHANG D,et al.On Performance of Cache Policies in Named Data Networking[C]//Proceedings of International Conference on Advanced Computer Science and Electronics Information.Washington D.C.,USA:IEEE Press,2013:668-671.

[7] EUM S,NAKAUCHI K,MURATA M,et al.CATT:Potential Based Routing with Content Caching for ICN[C]//Proceedings of the 2nd ICN Workshop on Information-Centric Networking.New York,USA:ACM Press,2012:49-54.

[8] CHAI W K,HE D,PSARAS I,et al.Cache “Less for More” in Information-Centric Networks[C]//Proceedings of Inter-national Conference on Research in Networking.Berlin,Germany:Springer,2012:27-40.

[9] 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.

[10] LAOUTARIS N,CHE H,STAVRAKAKIS I.The LCD Interconnection of LRU Caches and Its Analysis[J].Performance Evaluation,2006,63(7):609-634.

[11] 崔现东,刘 江,黄 韬,等.基于节点介数和替换率的内容中心网络网内缓存策略[J].电子与信息学报,2014,36(1):1-7.

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

[13] YI C,AFANASYEV A,WANG L,et al.Adaptive Forwarding in Named Data Networking[J].ACM SIGCOMM Computer Communication Review,2012,42(3):62-67.

[14] AFANASYEV A,MOISEENKO I,ZHANG L.ndnSIM:NDNSimulator for NS-3[D].Los Angeles,USA:University of California,Los Angeles,2012.

[15] MASTORAKIS S,AFANASYEV A,MOISEENKO I,et al.ndnSIM 2.0:A New Version of the NDN Simulator for NS-3:NDN-0028[R].Palo Alto,USA:Xerox Palo Alto Research Center,2015.