内容中心网络中一种改进型缓存机制

曲 桦,王伟萍,赵季红,2

(1.西安交通大学电子与信息工程学院,西安710049;2.西安邮电大学通信与信息工程学院,西安710061)

内容中心网络中一种改进型缓存机制

曲 桦1,王伟萍1,赵季红1,2

(1.西安交通大学电子与信息工程学院,西安710049;2.西安邮电大学通信与信息工程学院,西安710061)

内容中心网络(CCN)作为一种主要的未来网络架构,以命名的内容作为网内的主要元素之一,在网络研究中受到广泛关注。针对已有的CCN缓存方案内容副本替换严重的问题,提出一种内容热门度与节点中介中心度约束的缓存机制PopBetw。在基于节点中心度的基础上,从内容本身的属性热门度出发,避免非热门内容的不必要缓存,降低每个节点的缓存负荷,提高网络缓存性能。仿真结果表明,通过评估缓存大小和内容热门度对缓存性能的影响,PopBetw缓存策略可取得比LCE,LCPro和EgoBetw方案更高的缓存命中率和更小的路径延展度,明显降低网内缓存替换数量,有效减少网内节点中介中心性较大节点群的缓存替换数,达到整体性能最优化。

内容中心网络;缓存;内容热门度;中介中心度;缓存替换;缓存冗余

1 概述

目前因特网大多用于对内容的访问。尽管当初基于IP的因特网设计是为了达到端到端的通信,但是终端用户感兴趣的仅仅是内容本身而非源端位置。新的信息中心网络(Information-centric Network, ICN)架构［1］一经提出,便引起了越来越多的研究人员的兴趣,例如内容中心网络(Content-centric Network, CCN)［2-3］。CCN主张重新设计网络体系结构,从根本上解决高效内容分发面临的问题。针对用户关注内容本身而非其所在位置这一特点,内容和位置进行解耦合,并采用内容名对内容进行内容标识和路

由,使用户可以直接访问内容本身,不再需要通过位置间接进行访问。这一特点增强了内容缓存的灵活性,使得内容流量分布更加均匀。

在CCN场景下,所请求内容会依据相应的缓存决策机制［4］被缓存在返回路径沿途的某些节点中,以便为后续请求服务。缓存的主要作用在于降低用户访问时延,特别是减少跨网络的数据传输,使得用户不必总是从源服务器获取内容,而是从就近的缓存处获得服务,同时分布式的缓存起到负载均衡的作用。但是,相对于系统庞大的内容总量,网络中节点缓存资源是稀缺的。并且内容数目的增长远大于硬件存储空间的增长。因此网内缓存决策成为CCN研究中的核心问题之一。

网内缓存决策技术源于Web缓存、CDN和P2P系统,主要包括LCE(Leaving Copies Everywhere)［5］,Rdm (Random Caching Strategy),LCPro(Leaving Copies with Probability)等。LCE机制易于实现但缓存替换频繁、性能较差,后两者通过选择性缓存以减少不必要的内容替换,优于LCE,但随机性较大,内容缓存点的动态性会产生更多的网络开销。文献［6］基于自我网络中的中介中心度的概念,提出了ICN场景下一种新颖的缓存方案——EgoBetw,当内容数据包沿原路径返回时,仅在中介中心度值最大的节点缓存。一个节点若位于大量内容分发路径之间(在拓扑中起到交通枢纽、关键桥梁的作用),则该节点将缓存较多内容,本地缓存将为更多的其他到来的用户请求提供服务。EgoBetw在一定程度上降低了网内缓存替换率,并且将较热门的内容逐渐吸引到离用户较近的缓存节点上,缓存性能明显得以改善。但是同时导致中介值较大的节点处的缓存替换率较高。网内缓存容量有限,只能满足用户的部分请求,即较流行的内容,大部分较不流行的内容请求需到达服务器获取内容。当这些内容在服务器命中后经过返回路径上的重要节点(中介中心度较高的节点)缓存后,节点的缓存替换率变高,部分内容副本在缓存内的实际存活时间(节点缓存副本和副本被替换的时间差)变小,导致重要节点的缓存替换率较高、负荷严重、效率不高。

针对上述问题,考虑到CCN中固定时间段内不同内容的访问频次即热门度存在差异,本文将内容热门度与节点中介中心度相结合,提出一种PopBetw缓存机制,在请求内容沿原路径返回时,由最大节点中介中心度值预判断出缓存节点后,再由内容本身的热门度约束进行缓存判决,避免非流行内容的不必要缓存,增大较流行内容的缓存存活时间,实现全网内较佳的缓存性能。

2 PopBetw缓存机制

2.1 设计思想

在多数CCN网络中缓存判决策略中,每个节点对所有到达内容做相同处理,未考虑不同内容的热门程度不一这一重要特性。PopBetw缓存机制将内容热门度与节点中介度相结合,在节点中介度作为缓存约束条件的同时,考虑仅缓存热门内容,通过缓存更少内容提高网内缓存,减少冗余。

在如图1所示的拓扑中,t为0时,缓存节点V1至V6的缓存表均为空。当用户B向服务器S请求内容bi时,S向用户B返回的内容分发路径为V1→V3→V5,由于该条路径上节点V1的中介中心度最大,所以假如内容仅在V1节点处缓存,V3,V5节点不缓存,随后当A,B,C,D中某几个用户请求相同内容时,即可在节点V1命中。但是,网内内容繁多,一旦用户B请求的内容在缓存未命中,即服务器命中,节点V1均需缓存这些内容,导致节点V1缓存次数增多,有限的缓存容量引起替换次数增多,大量的缓存副本在缓存中的存活时间减小,命中率急剧减少。在上述例子中,当用户B向服务器S请求内容bi,服务器返回内容时,假如将节点中介中心度和内容热门度结合作为缓存的约束条件,即预判断节点V1的中介中心度最大,再次判断内容bi为热门内容时,节点V1缓存该内容,反之不缓存。这种方法使得高热门度的内容副本在节点V1处存在的概率变大,相对冷门内容副本在节点V1处存在的概率变小,从而避免了非流行内容无用的缓存操作,节省了路由器节点的缓存资源,节点V1缓存次数减少,缓存副本在缓存中的存活时间增大,命中率提高。

图1 缓存决策实例

2.2 内容热门度

PopBetw缓存策略在保留CCN中CS,FIB和PIT表的基础上,增加了数据结构:内容热门度表(Popularity Table,PT),每一个表项由内容bi的内容名和其热门度值fi组成。如果一个内容越热门,它的热门度值越大。

由于内容热门度值具有随时间变化的特性,因

此只能根据其过去的流行情况进行估计。PopBetw缓存策略中,将每个节点输入的请求流分段,每段成为一个统计周期,每个统计周期包括M个请求,在这M个请求周期中记录统计出各文件的访问频次。定义热门度值是对内容bi在某一统计周期内的请求次数估计值,采取类似文献［7］的估计方法来计算在第t+1个统计周期内内容bi的热门度值:

其中,Fbi为上一统计周期内内容bi的访问频次;δ为衰减系数。

2.3 节点中介中心度

考虑到实际网络是动态变化并且全局拓扑信息未必容易获得,最初的节点中介中心度是一种集中式计算,为实现节点中介中心度的分布式计算,文献［6］采用自我网络的中介中心度来近似计算CCN中各节点的中介中心度值。尽管自我网络的中介中心度仅仅反映节点在自我网络中的重要性,但是它和真实网络中该节点的中介中心度存在强的相关性。

设某一自我网络为图G,邻接矩阵为A,1为元素均为1的矩阵,则A2［1-A］i,j表示节点i和节点j之间访问跳数为2的路径数,A2［1-A］中所有元素倒数之和即该自我网络中心节点的中介中心度CB［8］,即也表征了该节点在全网内的重要程度。

2.4 算法描述

PopBetw缓存策略是基于单个兴趣包请求的,本节将结合节点收到兴趣包、内容包的处理伪代码对PopBetw缓存策略进行描述。

Pseudo-code I节点收到兴趣包伪代码如下:

若用户i向服务器j发送内容bi的兴趣包,经过的节点依次做出如下处理:

热门度更新:若计数器count未达到请求周期M,该统计周期内内容bi的访问频次Fbi加1;否则,请求数已达到统计周期,根据在本周期内非零的F值对所有内容对应的热门度值按定义公式更新,即更新内容热门度表PT。

内容缓存命中判断:若命中,返回内容,并将服务器命中标志HitInServer清零;否则,服务器命中标志HitInServer仍为1,更新CBmax(判断本节点中介中心度与兴趣包中的CBmax大小,若本节点中介中心度较大,更新CBmax),向下一跳转发兴趣包。

若内容bi从服务器j或缓存命中的节点到用户i沿原路径返回,关于缓存条件decision的判断,经过的节点依次分如下具体情况做出处理:

(1)若内容bi在服务器命中,即标志HitInServer为1,节点中介中心度CB(vn)等于CBmax,表明该节点为网络中中介中心性较大的节点,需要考虑内容热门度,即当该内容的热门度值大于阈值θ,则缓存该内容。

(2)若内容bi在缓存命中,即标志HitInServer为0,并且节点中介中心度CB(vn)等于CBmax,则缓存该内容。

3 性能评价

3.1仿真环境和性能评价指标

为了验证PopBetw算法是否能达到预期效果,本文从CCN网内多种内容放置方案中选择3种代表性策略LCE,LCPro,EgoBetw作为PopBetw性能比较对象,结合LRU缓存替换策略,在NS3网络仿真器中实现了简单的CCN仿真模型并对缓存性能进行评估。

由于真实的网络拓扑是不规则的并且遵循幂律度规则,本文采用文献［9］中的方法建立一个满足BA模型的无标度网络,总节点数为100。节点分为3类:服务器,中间节点和访问节点(连接用户终端并且在网内为第一跳的所有节点为访问节点)［10-11］。总的内容文件数M=1 000个,内容热门度模型为参数α=0.8的Zipf分布。内容请求由代表终端用户的66个访问节点发出,总数为330 0000个(50 000× 66个),每个访问节点的内容请求到达过程服从λ= 25的泊松过程。尽管CCN支持多径路由,本文仅从单径路由的前提下对缓存策略进行性能分析。

本文目标是过滤掉非流行内容,找到相对热门内容的最优缓存位置达到最大缓存性能,为更加准确地反映CCN性能,本文采取以下测量参数作为性能评价指标。

(1)缓存命中率(CHR):

其中,Q表示请求总数;q表示内容请求在内容路由器处命中个数。缓存命中率是一个典型的测量缓存性能的参数,缓存命中率越高,反映缓存响应用户请求的概率越高,服务器负载越低,缓存系统的效率越高。

再次，培训应该以日常工作为重点，不追求花哨和专业难度很大的内容。多关注那些在客户家经常用到的技术，把它们作为培训重点。例如，打扫卫生和做饭不掌握，净关注鲍鱼燕窝等高档食材的制作，就是没有把握住重点。

(2)路径延展度(PS)

其中,d为仿真中统计的29个访问节点发出的请求通过CCN获取内容的平均实际跳数;|P|为访问节点发出的请求从源服务器端获取所需的平均跳数。路径延展反映了负载水平,在某种程度上,它表示数据内容经过的链路数的减少程度［12-13］。

(3)不同节点群的平均缓存替换数和缓存命中数。在通常情况下,网内缓存容量有限,远远小于内容的大小,这就势必会产生大量的替换操作,进而消耗大量的计算资源。而对于一个缓存资源有限的路由器来说,这些消耗显然将会影响路由器的转发等其他任务的完成。另一方面,缓存替换发生越频繁,副本在节点的存活时间越短,副本命中的概率也越小,过高的缓存替换将严重影响网内的缓存性能。所以,如何减少CCN中的替换数量,也是一个值得注意的问题。

考虑到本文提出的PopBetw缓存机制涉及到节点的中介中心性,结合以上讨论将对3类节点群的平均缓存替换数和缓存命中数进行定量分析:所有具有缓存功能的路由器节点群,具有较大节点中介中心度的节点群和其余普通缓存节点群。

3.2 仿真结果

3.2.1 缓存大小对缓存性能的影响

本节首先研究缓存大小对系统性能的影响。图2显示出缓存性能随缓存大小变化而变化的情况,其中,缓存大小与内容总量之比从1%一直增加到6%。从图2(a)中可以看到,4种机制的缓存命中率会随着缓存容量大小的增加而增加,相比LCE, LCPro,EgoBetw机制性能明显提高,但在这个过程中,PopBetw策略都取得了比较稳定的性能提高,且好于LCE,LCPro,EgoBetw。图2(b)显示出路径延展随缓存容量的增加而减小的情况。缓存命中率提高,内容请求在内容路由器上获取到副本的概率增大,所需访问跳数减少,路径延展也相应减少。由于PopBetw采用内容热门度和节点中介中心性约束缓存条件,避免了缓存冗余,使得缓存节点尽量缓存热门内容。PopBetw的路径延展自始至终都比LCE, LCPro和EgoBetw要低。

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

下面研究不同缓存机制下缓存替换数和缓存命中数之间的关系。图3是节点缓存大小和内容总量之比取定后,LCE,LCPro,EgoBetw和PopBetw 4种缓存策略下3种不同缓存节点群的平均缓存替换数和命中数的比较。类似文献［6］,设节点缓存大小和内容总量之比为0.1,节点群1～节点群3分别表示具有缓存功能的所有节点,具有较大节点中介中心度的节点群和其余普通缓存节点群。

如图3所示,对于节点群1,LCE机制下的平均

缓存替换数最大且平均缓存命中数最小,故综合性能最差,而PopBetw机制下的平均缓存替换数最小而缓存命中数最高,综合性能明显提高;对于节点群2,4种缓存机制下的缓存替换数量差异较大, LCE和LCPro机制在缓存命中数方面优于EgoBetw,而PopBetw策略下的节点群2的替换数远比另外3种少,并且命中数达最高;对于节点群3,节点中介中心性较小,4种策略下的缓存替换次数均较小,与节点群2不同的是,EgoBetw性能远胜过LCE和LCPro机制,同时EgoBetw以低替换率达到了最好的命中效果。与节点群3相比,节点群2往往处在网内的枢纽位置,每个节点收到来自下游节点聚合的内容请求数量较多,大量的内容缓存在这些节点的概率增大,图中显示节点群2的替换次数远远高于节点群3。

图3显示了PopBetw缓存方案通过判断内容的流行度过滤掉相对较冷门的内容,有效地减少了网内节点中介中心性较大的节点群的缓存替换数,改善了节点群2的缓存水平,达到了整体性能最优化的目的。

图3 不同缓存节点群的缓存命中数和平均缓存替换数

3.2.2 内容热门度对缓存性能的影响

由于用户对内容的兴趣随时间会发生变化从而影响内容热门度,本节进一步研究变化的内容热门度对缓存性能的影响。

首先考虑内容的热门度有范围这一情况,即一些内容在某些节点属于热门类,在另外一些节点处为非热门内容。仿真中所有访问节点分为3类,分别产生3类不同内容请求(体现用户对内容的不同程度的喜好),当缓存大小与内容总量之比为1%时统计4种缓存机制的缓存性能并与内容请求为一类的情况下的结果对比,如表1所示。相对于内容请求为一类的情况,4种缓存机制达到的缓存性能稍差,但是与其他3种方案对比,PopBetw缓存方案依然有明显的性能改善。

表1 内容请求不同分类情况下的缓存性能对比

然后分析当内容热门度在变化速率不同时4种缓存机制的性能变化,假设缓存大小与内容总量之比为3%。如图4所示,横轴表示在一个时间周期里变化的热门内容数与内容总数的比值。图4表明随着变化的内容热门度,LCE和LCPro30%性能所受影响不大,EgoBetw和PopBetw性能稍微变差。实验显示当内容热门度变化越缓和,EgoBetw性能越易达到最优。

图4 热门内容变化率对缓存性能的影响

4 结束语

为了使CCN的全网缓存发挥潜在的优势,本文将内容本身的属性——流行度和节点中介中心性相结合,提出并实现了一种新的内容缓存策略

PopBetw。该策略通过节点中介中心性大小判定选择较优目标缓存位置,通过内容热门度缓存热门内容,避免非热门内容的不必要缓存,有效利用缓存资源,避免了大量缓存冗余。仿真结果表明,考虑到缓存大小和内容热门度变化的因素,PopBetw在缓存性能(包括缓存命中率、路径延展度)方面优于EgoBetw,相比LCE,LCPro策略性能提高更显著;另外相比较LCE,LCPro,EgoBetw 3种策略,PopBetw有效地减少了网内节点中介中心性较大的节点群的缓存替换数,达到了整体性能最优化。下一步将对内容热门度对算法的影响进行更深入的研究。

［1]Koponen T,Chawla M,Chun B G,et al.A Data-oriented (and Beyond)Network Architecture［J］.ACM SIGCOMM Computer Communication Review,2007,37(4):181-192.

［2]闵二龙,陈 震,许宏峰,等.内容中心网络CCN研究进展探析［J］.信息网络安全,2012,(2):6-10.

［3]Jacobson V,Smetters D K,Thornton J D,et al.Networking Named Content［C］//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.New York,USA:ACM Press,2009:1-12.

［4]Cho K,Lee M,Park K,et al.WAVE:Popularity-based andCollaborativeIn-networkCachingforContentoriented Networks［C］//Proceedings of 2012 IEEE Conference on Computer Communications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

［5]Laoutaris N,Syntila S,Stavrakakis I.Meta Algorithms for Hierarchical Web Caches［C］//Proceedings of IEEE International Conference on Performance,Computing,and Communications.Washington D.C.,USA:IEEE Press, 2004:445-452.

［6]Chai W K,He D,Psaras I,et al.Cache“Less for More”in Information-centric Networks［C］//Proceedings of the 11thInternationalIFIPTC6Conferenceon Networking.Berlin,Germany:Springer,2012:27-40.

［7]Zhang Y,Zhao J,Cao G.Roadcast:A Popularity Aware ContentSharingSchemeinVANETs［J］.ACM SIGMOBILE Mobile Computing and Communications Review,2010,13(4):1-14.

［8]Everett M,Borgatti S P.Ego Network Betweenness［J］.Social Networks,2005,27(1):31-38.

［9]Barabasi A L,AlbertR.EmergenceofScalingin Random Networks［J］.Science,1999,286(5439): 509-512.

［10]Wang J M,Bensaou B.ProgressiveCaching in CCN［C］// Proceedings of 2012 IEEE Global Communications Conference.Washington D.C.,USA:IEEE,2012:2727-2732.

［11]Wang J M,Zhang J,Bensaou B.Intra-AS Cooperative Caching for Content-centric Networks［C］//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-centric Networking.New York,USA:ACM Press,2013:61-66.

［12]Rossi D,Rossini G.CachingPerformance of Content Centric Networks Under Multi-path Routing(and More)［Z］.2011.

［13]Rossi D,Rossini G.On sizing CCNContent Stores by Exploiting Topological Information［C］//Proceedings of INFOCOM Workshops.Washington D.C.,USA:IEEE Press,2012:280-285.

编辑 金胡考

An Improved Caching Mechanism for Content-centric Network

QU Hua1,WANG Weiping1,ZHAO Jihong1,2
(1.School of Electronic and Information Engineering,Xi’an Jiaotong University,Xi’an 710049,China;
2.School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

Content-centric Network(CCN)based on named data which is one of the vital elements in network,as a main architecture for the future Internet,attracts considerable attention from the research community recent years.A new caching scheme called PopBetw based on content popularity and node’s betweenness is proposed to solve the problem of heavy replacement of content copies brought by existing cache policies in CCN:combining content popularity which is one of content attributes with node’s betweenness avoids caching unpopular contents,reduces caching load in each node and improves in-network caching performance.Simulation experiment demonstrates that the proposed PopBetw caching strategy achieves larger cache hit rate and lower path stretch than that of LCE scheme,LCPro and EgoBetw scheme by evaluating the impact of cache size and content popularity on the caching performance,it also shows that PopBetw apparently lower the number of in-network cache replacement especially in nodes with relatively large value of betweenness to achieve better overall performance.

Content-centric Network(CCN);caching;content popularity;betweenness;cache replacement;cache redundancy

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

英文引用格式:Qu Hua,Wang Weiping,Zhao Jihong.An Improved Caching Mechanism for Content-centric Network［J］.Computer Eng-ineering,2015,41(3):41-46.

1000-3428(2015)03-0041-06

:A

:TP393

10.3969/j.issn.1000-3428.2015.03.008

国家自然科学基金资助项目(61371087);国家科技重大专项基金资助项目“新一代宽带无线移动通信网”(2013ZX03002010-003);国家“863”计划基金资助项目(2014AA01A706)。

曲 桦(1961-),男,教授、博士生导师,主研方向:移动互联网;王伟萍,硕士研究生;赵季红,教授。

2014-03-06

:2014-05-22E-mail:wwpwalker@163.com