内容中心网络中一种基于内容扩散的主动缓存机制

罗熹　安莹　牛碧诺

摘 要：借鉴分子扩散的思想，提出一种基于内容扩散的主动缓存机制（Content Diffusion Based Proactive Caching， CDBPC）.该机制引入缓存内容浓度的概念来描述不同内容在不同区域内的需求程度，然后根据节点间的缓存内容浓度关系来驱动内容副本在网络中的主动推进和迁移，并结合内容的流行度等因素实现了缓存内容的概率性放置，从而达到内容缓存的快速部署和推进，提高为用户提供就近响应概率的目的.仿真结果表明，该机制能有效地降低系统的平均接入代价并提高缓存命中率.

关键词：内容中心网络；扩散原理；主动缓存；内容流行度

中图分类号：TP393 文献标识码：A

Abstract：This paper borrowed the idea of molecular diffusion and proposed a proactive caching scheme based on content diffusion. In this mechanism， the conception of content concentration was introduced to analyze user demands for different contents in different network regions. In order to achieve fast content placement and increase the probability of providing responses to user requests by the nearer caching nodes， the content replicas were proactively pushed forward or migrated according to the content concentration difference between nodes. Furthermore， by synthetically considering the content popularity， a probabilistic content placement method was also implemented. The simulation results have shown that this scheme can effectively decrease the average access cost and improve the cache hit ratio.

Key words：Content-centric Networking（CCN）；diffusion theory；proactive caching；content popularity

近年来，随着P2P应用、发布订阅系统、普适计算以及海量流媒体等新型应用的不断发展，信息获取已经成为了当前网络服务的主体，传统的以主机为中心的通信模式逐渐演变为以信息为中心的新模式.网络通信方式的变化使得网络设计者们必须对当前的Internet体系架构做出重大调整，从而导致了以内容中心网络（Content-Centric Networking，CCN）[1]为代表的一系列新型网络的涌现.

在CCN中，内容位置的重要性被逐渐弱化，网络通过对内容进行统一命名，来实现基于内容名称的定位、路由和传输.同时，CCN要求每个具有存储能力的节点都能缓存经过的内容，从而为其他用户对同一内容的后续请求提供快速的响应.换而言之，CCN将透明化、泛在化的网络内置缓存作为其网络体系结构中固有的一部分，以此加快内容的分发速度并提高网络资源的利用率.因此，CCN中的内置缓存机制也就成为了目前该领域的研究热点，其中一个重要的问题是如何选择内容的缓存位置，并且研究者们已经就此开展了大量的研究工作.Psaras等人[2]提出了一种基于加权概率的缓存机制ProbCache，结合节点与请求者的距离和路径的剩余缓存空间来计算内容返回路径上各沿途节点缓存内容对象的概率，该概率与节点和内容请求者间的距离成反比，而与节点的可用资源成正比.该机制通过将内容以更高的概率缓存于距离请求者更近的节点，来保证内容副本快速地趋向网络边缘，从而提升系统的缓存性能.文献[3-4]采用了相似的基本思想，通过为流行度高的内容设置较长的缓存时间，保证流行内容的缓存命中，并加快内容获取的响应速度.文献[5]采用了差异化缓存的方式，提出了一种结合空间存储位置和缓存驻留时间的二维差异化缓存策略.该策略将一定时间间隔内内容被请求的次数定义为该内容的活跃度，然后根据内容活跃度的变化趋势来决定下行节点是否对内容进行缓存，在空间维度上实现内容缓存位置的逐跳推进.同时，通过赋予活跃度高的内容更长的缓存时间，进一步确保流行内容尽可能地缓存在靠近用户的网络边缘位置.刘外喜等人[6]提出了把内容的放置、发现、替换统一起来考虑的APDR机制，实现内容的有序缓存.APDR的主要思想是：Interest报文除了携带对内容的请求，还收集沿途各节点对该内容的潜在需求、空闲缓存等信息，使得Interest的汇聚点和目的地节点，可以据此计算出一个缓存方案，并把该方案附加在Data报文之上，通知返程途中的某些节点缓存该内容并设置指定的缓存时间.文献[7]根据用户的潜在需求和内容的流行规律，提出了一种选择性缓存机制SC.作者认为由于下游节点缓存的存在，节点上收到过某个内容的请求并作出响应的端口在未来一段时间内不会再次收到对该内容的请求.因此，对于某个内容而言，节点上未请求过该内容的端口数量越少，其对该内容的潜在需求就越低，那么节点缓存该内容的必要性也越小.在此基础上，该机制通过结合链路利用率以及节点的可用缓存空间等因素计算内容的缓存概率来实现内容的选择性缓存，以提升系统的缓存效率.Kyi等人[8]提出了一种基于一致性哈希算法的协作缓存决策机制，该机制将AS内的路由节点分成不同的组，通过组内路由节点间对内容缓存和请求转发的协同操作来提高缓存性能和资源利用率.在缓存决策时，各个路由节点主要考虑内容的流行度并利用一致性哈希避免内容的重复缓存.

CCN中内容缓存的重要目的之一是逐步地使内容副本接近请求用户，从而缩短内容的获取延迟.然而，对于整个网络范围而言，内容对象向网络边缘的复制往往是一个较为缓慢的过程[9].其主要原因是，现有的CCN缓存机制中，内容的缓存决策大多和内容的分发过程一样均由用户的兴趣（Interest）驱动，并采用路径内（on-path）缓存策略直接从Interest的反向路径上的中间节点中选择内容缓存位置.这导致了两方面的主要缺陷，其一，内容的携带者（原始内容服务器或中间缓存节点）只有在收到相应的Interest并在其缓存中发生命中后才会在响应内容的返回过程中触发内容缓存位置的决策，缺乏对内容副本进行主动推进的能力.这种过于被动的方式显然会延缓内容缓存在网络内的部署速度，很大程度上它将受到Interest转发策略的影响.其二，内容缓存位置的选择往往局限在原始内容服务器与请求用户节点的直接路径上，未充分地考虑路径外的节点状态及用户需求.文献[10]指出路径外（off-path）缓存策略在能耗等缓存性能上比路径内（on-path）缓存策略具有更大的优势.更重要的是，如果能根据节点未来的潜在需求，预先将内容复制到当前路径以外的其他网络区域，将能更进一步地加快内容查询和获取的速度，大大提升缓存系统的综合性能.

针对上述问题，本文提出一种基于扩散理论的主动缓存机制.该机制不仅能根据收到的用户请求沿着反向路径选择缓存内容的放置位置，同时还通过借鉴分子动理论中的扩散原理，根据节点分布密度以及与内容提供者和请求者间的距离来定义网络中不同区域的缓存内容浓度，然后将内容副本由高浓度区域主动扩散到低浓度区域，实现内容缓存节点的快速部署以及缓存位置的动态调整，从而有效提高系统的缓存性能.根据现有的相关研究工作，部分学者也试图通过引入物理场的概念来优化CCN中的缓存决策问题.如文献[11]中提出了一种基于势能的目标识别路由方法（Cache Aware Target iden Tification， CATT），该方法引入势场（potential field）的概念，将节点存储的内容副本沿势能由高到低的方向进行局部范围通告，从而提高缓存资源的可用性.文献[12]指出CCN中能够响应内容请求的节点可以分为持久稳定的原始内容服务器和动态可变的临时缓存节点两类，考虑到它们的差异化特征并结合数据场的思想，分别为其构建全局导向和局部吸引的势能辐射场，在路由查找过程中引导内容请求的转发，实现缓存内容整体利用率的提升.文献[13]则通过建立一个基于内容的拓扑势场，用于扩散网络缓存副本的内容通告，使网络后续产生的用户请求可以充分利用不在路径上的内容副本来选择最佳的内容响应位置.然而这些方法均从优化内容副本通告或用户请求转发的角度来改进内容的缓存性能和网络通信服务质量.与之不同的是，我们提出的方法是通过构建内容在网络中的区域缓存浓度，利用内容副本在不同浓度区域间的扩散实现内容缓存的主动放置和动态迁移，从而增加为潜在用户请求提供就近响应的可能.这种内容副本的主动推进方式将大大地缩短内容查找和响应的延迟并提高内容的缓存命中概率.

1 分子扩散的引入

扩散现象是指物质分子从高浓度区域向低浓度区域转移直到均匀分布的现象.根据分子动理论，分子扩散的本质是由于分子热运动而产生的质量迁移现象.从微观上说，它实际上是大量物质分子做无规则热运动时，分子之间发生相互碰撞的结果.由于不同空间区域的分子密度分布不均匀，分子发生碰撞的情况也不同.这种碰撞迫使密度大的区域的分子向密度小的区域转移，最后达到均匀的密度分布.

扩散定律描述了分子扩散导致的传质过程，这一定律由德国物理学家菲克（ A.Fick）于1855年在实验的基础上提出的，故又称为菲克（Fick）定律.Fick定律指出，在稳态扩散过程中，扩散通量J与浓度梯度成正比，即

式中：D为扩散系数，是描述扩散速度的重要物理量，它表示单位浓度梯度条件下，单位时间单位截面上通过的物质流量；φ为浓度；x代表位置；负号表示物质沿着浓度降低的方向扩散.式（1）的意思是，如果某个事物的空间分布是不均匀的，就会造成流动，而引起的物质流正比于该事物的梯度.其中，梯度是物质流动的驱动力.

受到上述分子扩散思想的启发，我们将内容对象看作溶质，将用户对该内容对象的需求视为溶剂，那么整个网络系统则为内容对象与用户需求混合而成的溶液.由于内容副本以及用户需求分布的不均匀性和动态性，因此该溶液不同区域的浓度也存在差异，内容原始服务器或缓存节点附近浓度较高，而内容请求节点附近浓度较低.对于内容的缓存决策而言，直觉上内容副本应尽量趋近用户需求较大的区域以提供快速高效的缓存和通信服务.于是，缓存内容的放置决策可以看作溶质分子（内容副本）在溶液中由高浓度区域向低浓度区域转移的扩散过程.

2 CDBPC缓存机制

2.1 内容扩散模型

2.2 CDBPC工作原理

CDBPC机制的基本思想是克服现有缓存机制中缓存决策过程完全依赖用户Interest驱动的被动性，通过借鉴分子扩散的原理以一种更主动的方式实现内容副本向用户端的快速推进.同时在内容副本的推进过程中综合缓存内容浓度和内容流行度实现概率性的缓存放置，从而加快对后续用户请求的响应速度，提高系统的整体缓存性能.CDBPC主要包括两个部分：内容副本的推进以及内容的缓存决策.在内容副本的推进过程中，我们设计了被动响应和主动扩散2种基本的推进模式.其中，被动响应模式发生在节点返回被请求的数据的响应过程中.即，仅当收到相应的用户请求并在缓存中发生命中时，作为数据应答，节点才会将内容副本沿着请求的反向传输路径返回请求用户.主动扩散模式的触发则与内容是否在该节点发生缓存命中无关，而是每隔一定的时间（本文称之为扩散周期Td），节点便通过计算并比较自身与邻居节点的缓存内容浓度，主动将内容副本沿着缓存内容浓度下降最快的路径方向逐跳地进行扩散.在内容副本的主动扩散或被动响应路径上，中间节点再以一定的概率来选择内容的缓存位置.CDBPC机制的工作流程描述如下.

2.2.2 内容的主动扩散

在CDBPC中，被动响应模式相对比较简单，它由发生缓存命中的Interest包触发，内容副本按照预先确定的Interest包的反向路径推进.而在主动扩散模式中，内容副本的扩散源自相邻节点间的缓存内容浓度差，按浓度由高到低的方向进行移动.与被动响应模式中推进的内容对象以及推进的路径均由相应的Interest确定不同，主动扩散模式需解决以下2个问题：①节点缓存中可能存在多个不同的内容对象，对所有的缓存内容均进行扩散容易造成过大的通信和存储开销.因此必须对进行扩散的内容对象进行合理的选择；②沿着节点的所有输出路径进行全方位的扩散也必然产生大量的冗余内容副本，导致网络资源的过度消耗.因此，节点还必须合理地选择内容副本的推进方向以实现内容的选择性扩散.下面针对上述问题给出具体的解决策略.

1）扩散内容的选择.为了使不同的内容对象均能获得一定的扩散机会，保证不同内容间的公平性以及网络中缓存内容的多样性，我们采用概率性选择的方式从节点的缓存中确定待扩散的内容.考虑到用户对流行度高的内容往往具有更高的请求概率，因此我们根据内容的流行度来调整不同内容的选中概率，使其与各自的流行度成正比.具体来说，假设节点N的缓存中包含l个内容对象，若将其中的第i个内容对象表示为cNi，其流行度表示为pcNi.那么，cNi被选中为扩散内容对象的概率DPi可以按公式（5）计算得到.

3.2 性能评估

仿真过程中，我们将CDBPC与在用户请求的被动响应路径上选择最大介数节点进行缓存的Betw[16]和利用势场主动进行局部内容通告的CATT进行比较.其中，CATT的内容通告范围设置为2跳.在缓存大小、内容数量和Zipf参数α等网络参数变化的情况下，分别对上述3种缓存机制的缓存命中率以及平均接入代价进行了定量分析和比较.

3.2.1 缓存大小的影响

图3为节点缓存对缓存性能影响的仿真结果图.由图3（a）可以看到，随着节点缓存空间的增大，内容分组在缓存中的驻留时间延长，因此3种机制的缓存命中率均逐渐提高.其中，由于CDBPC向用户端对内容分组实施主动扩散，同时在此过程中根据缓存内容浓度和内容流行度采用了逐跳递增的概率缓存，将内容的缓存副本快速有效地分布到请求用户节点附近，从而获得了3种机制中最高缓存命中率.而Betw中内容副本的推进完全依赖节点对用户请求的应答，且单纯地依据节点的介数中心性来实现缓存节点的选择，使得介数较高的节点由于缓存压力过大而导致缓存替换频繁，因此获得的缓存命中率最低.CATT利用势场实现了缓存内容的主动通告，有效地将用户请求导向匹配的内容缓存副本，一定程度上提高了系统的缓存命中率，因此在图中CATT的缓存命中率略高于Betw.

同样，随着节点缓存的增加，中间节点对内容的缓存能力增强，每个内容分组能获得更长时间的缓存服务.这意味着用户有更大的可能从距离较近的中间缓存节点实现快速的内容获取.因此，图3（b）中各机制的平均接入代价均随着节点缓存的增加而逐渐降低.其中，得益于CDBPC对内容副本的主动扩散，加快了缓存副本向用户边缘的推进，因此，CDBPC获得了3种机制中最小平均接入代价.以节点缓存为50 MB时的情况为例，Betw和CATT的平均接入代价达到了4.55跳和4.22跳，而CDBPC仅为4.02跳，与前两者相比，分别减少了近11.6%和4.7%.

3.2.2 内容数量的影响

内容数量对3种缓存机制影响的实验结果如图4所示.由于在节点缓存大小固定的情况下，内容数量的增加意味着可用缓存资源的相对紧张.因此，内容数量对缓存性能的影响实际上也是节点缓存大小与缓存性能之间关系的另一种体现.

从图4（a）中结果可以看到，随着内容数量的增多，节点缓存资源越发紧缺，3种机制的缓存命中率均出现进了明显下降的趋势.但是，CDBPC始终保持了3种机制中最高的缓存命中率.在内容数量增至10 000个时，CDBPC仍获得了21.6%的缓存命中率，优于CATT的19.5%和Betw的15.7%.而由图4（b）可知，3种缓存机制的平均接入代价则随着内容数量的增加逐渐增大.其中，CDBPC的平均接入代价明显低于其他2种缓存机制.同样以10 000个内容时的情况为例，CDBPC的平均接入代价仅为4.57跳，相比Betw和CATT分别减少了约10.9%和5%.这与3.2.1节中关于缓存大小对2种缓存性能指标的影响的分析结果是一致的.

3.2.3 Zipf参数α的影响

用户对内容的访问具有一定的偏好性，用户偏好对不同机制的缓存命中率的影响如图5所示.Zipf参数α越大，意味着用户的偏好越发地向流行度高的内容集中.由于3种缓存机制均采用了优先保证高流行度内容缓存时间的相关策略（如，基于LRU的缓存替换策略），因此，由图5（a）可见，它们的缓存命中率随着α值的增大均呈现上升的趋势.同时，还得益于在内容推进以及缓存决策中对内容流行度的考虑，CDBPC在采用不同的α值时均获得了明显高于其他2种缓存机制的缓存命中性能.在平均接入代价方面，从图5（b）中的结果可以发现，用户偏好性的增强导致了平均接入代价的下降.而CDBPC对内容副本更为主动的推进方式，使得用户可以更快地实现内容获取，从而获得了3种机制中相对最低的平均接入代价.

4 结 论

为了加快内容缓存副本在内容中心网络中的推进，进一步提高其为潜在用户请求提供就近响应的可能性，本文提出缓存内容浓度的概念，并借鉴分子的扩散原理设计了一种基于内容扩散的主动缓存机制CDBPC.该机制利用节点间的缓存内容浓度关系来驱动内容副本在网络中的主动推进和迁移，并结合内容的流行度等因素实现了内容的概率性缓存决策.仿真实验结果表明该机制能有效地提高系统的整体缓存性能.在今后的工作中，我们将对CDBPC在实际网络环境下的性能进行验证，同时进一步研究如何将其扩展到移动网络以及其他复杂的网络环境.

参考文献

[1] JACOBSON V，SMETTERS D K，THORNTON J D，et al. Networkingnamed content[J].Communications of the ACM， 2012， 55（1）：117-124.

[2] PSARAS I，CHAI W K，PAVLOU G.Probabilistic in-networkcaching for information-centric networks[C]// Proceedings of the Second Edition of the ICN Workshop on Information-centric Networking. New York： ACM， 2012： 55-60.

[3] MING Z，XU M，WANG D.Age-based cooperative caching in information-centric network[C]// Proceedings of the 23rd International Conference on Computer Communication and Networks （ICCCN）. Washington DC： IEEE Computer Society，2014：1-8.

[4] QIAN H，MUQING W，DONGYANG W，et al.Lifetime-based greedy caching approach for content-centric networking[C]// Proceedings of the 21st International Conference on Telecommunications （ICT）. Washington DC： IEEE Computer Society，2014：426-430.

[5] 葛国栋，郭云飞，刘彩霞，等.命名数据网络中基于内容请求相关性的协作缓存算法[J].电子与信息学报，2014，36（12）：2795-2801.

GE Guo-dong，GUO Yun-fei，LIU Cai-xia，et al.Collaborative caching algorithm based on request correlation in named data networking[J].Journal of Electronics & Information Technology，2014，36（12）：2795-2801.（In Chinese）

[6] 刘外喜，余顺争，蔡君，等.ICN中的一种协作缓存机制[J].软件学报，2013，24（8）：1947-1962.

LIU Wai-xi，YU Shun-zheng，CAI Jun，et al.Scheme for cooperative caching in ICN[J].Journal of Software， 2013， 24（8）：1947-1962.（In Chinese）

[7] 刘外喜，余顺争，胡晓，等.CCN中选择性缓存机制的研究[J]. 计算机学报，2014，37（2）：275-288.

LIU Wai-xi，YU Shun-zheng，HU Xiao，et al.Selective caching in content-centric networking[J].Chinese Journal of Computers，2014，37（2）：275-288.（In Chinese）

[8] KYI T，SAEED U，CHOONG S H.Consistent hashing based cooperative caching and forwarding in content centric network[C]//Proceedings of the 16th Asia-Pacific Network Operations and Management Symposium （APNOMS）. Washington DC： IEEE Computer Society，2014：1-4.

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

ZHANG Guo-qiang，LI Yang，LIN Tao，et al.Survey of in-network caching techniques in information-centric networks[J].Journal of Software，2014，25（1）：154-175.（In Chinese）

[10]DRAXLER M，KARL H.Efficiency of on-path and off-path caching strategies in information centric networks[C]// Proceedings of 2012 IEEE International Conference on Green Computing and Communications （GreenCom）. Washington DC：IEEE Computer Society，2012：581-587.

[11]EUM S，NAKAUCHI K，MURATA M，et al.CATT： potential based routing with content caching for ICN[J]. IEEE Communications Magazine，2012，50（12）：60-67.

[12]葛国栋，郭云飞，刘彩霞，等.内容中心网络中基于差异化缓存通告的混合路由机制[J].电子与信息学报，2015， 37（3）：700-707.

GE Guo-dong，GUO Yun-fei，LIU Cai-xia，et al.A hybrid routing scheme based on differentiated cache advertisement in content centric networking[J].Journal of Electronics & Information Technology，2015，37（3）：700-707.（In Chinese）

[13]陈璐，汤红波，郑林浩.内容中心网络基于拓扑势的请求者移动性支持机制[J].计算机工程与设计，2014，35（8）： 2685-2690.

CHEN Lu，TANG Hong-bo，ZHENG Lin-hao.Consumer mobility scheme in content centric networks based on topological potential[J].Computer Engineering and Design，2014，35（8）： 2685-2690.（In Chinese）

[14]KIM Y，YEOM I.Performance analysis of in-network caching for content-centric networking[J].Computer Networks，2013，57（13）：2465-2482.

[15]MASTORAKIS S，AFANASYEV A，MOISEENKO I，et al.ndnSIM 2.0： a new version of the NDN simulator for NS-3[R]. Los Angeles：University of California，2015.

[16]CHAI W K，HE D， PSARAS I，et al.Cache “Less for more” in information-centric networks[J].Computer Communications， 2013，36（7）：758-770.