内容中心网络中基于内容流行度和节点属性的协作缓存策略

霍跃华，刘银龙

(1.中国矿业大学(北京) 现代教育技术中心，北京 100083；2.中国科学院 信息工程研究所，北京 100093)

内容中心网络(content-centric networking)是一种新兴的以信息/内容为中心的新型网络架构，将传统的主机中心模型转为更加灵活的数据中心模型，属于“革命式”的未来互联网体系架构，能够从根本上解决IP网络在可扩展性和内容分发有效性方面存在的问题，这种新的网络架构现在已经成为了未来互联网的研究热点。

随着网络流量的飞速增加，网络中的链路带宽受到了严峻压力，针对此问题，CCN网络架构利用了泛在化的缓存技术来缓解网络压力。然而，此种缓存机制提高了内容分发获取能力，但同时也产生较多的缓存冗余，从而降低了网络资源利用率和缓存能效。在CCN网络中，全网节点内嵌缓存的优势与缓存资源充分利用的矛盾，是缓存研究中亟待解决的问题。

传统的LCE(leave copies everywhere)，LCD(leave copy down)，ProbCache等缓存机制，虽然算法简单易行，但会使得网络中内容冗余度较高而且节点命中率较低[1-2]。为了改善网内缓存性能，目前的缓存算法主要是基于内容流行度[3-4]和基于复杂网络计算的节点属性[5-7](介数、度数、中心度等)等指标。

文献[3]提出了一种隐式协作缓存策略，该策略对内容分块流行度进行分级并根据缓存节点位置进行决策。该策略将内容流行度的计算单位提升到内容分块的级别，将流行度变得更加细粒度，从而提高了内容在网内缓存中的命中率，降低了用户的内容获取时延，用户的服务质量得到了提升。文献[8]提出了一种缓存策略，将内容流行度和节点中心度进行匹配，综合做出缓存决策，内容在沿路径传输时进行缓存选择，提高了沿路径节点的缓存利用率，降低了缓存冗余。

但是这些算法存在两个问题：1) 无法提前获取某一内容的流行度，而且同一内容在不同区域、不同时间段内的流行度也不完全相同的；2) 已有缓存算法往往将流行度高的内容缓存在介数、度数、中心度等属性高的节点，容易导致这些节点的内容不断被替换，而且内容在网络中的分布不均匀。文献[9]提出了一种基于阈值的缓存策略，该策略将内容相对均匀的分布在网络中，但是该方法没有考虑节点的差异性，而且也没有考虑内容流行度的局部、实时性特点。此外，现有的缓存算法没有考虑到用户在地理位置上的分布，不能实现内容在网络中根据用户分布的密集程度差异化分配。

基于上述考虑，本文提出了一种基于内容流行度和节点属性的协作缓存策略，该策略一方面根据内容的实时流行度将内容均匀分布，使实时流行度高的内容优先缓存在更重要的节点上，降低缓存冗余，提高缓存中内容多样性；另一方面从多个方面综合考虑节点差异性，使得内容分布更加均匀，避免内容更替过于频繁；同时，增大用户密集区域的缓存密度，提高缓存命中率和用户体验。

1 CCN缓存工作机制

下面介绍CCN的缓存工作机制。文中采用的网络拓扑由消费者节点、路由节点和内容服务器组成。路由节点又分为边缘路由节点和一般路由节点，基本功能为名解析和路由转发。此外，边缘路由节点与该区域内的多个消费者节点连接，负责收集并转发区域内消费者节点发起的内容请求，还能够实现本文提出缓存策略中所需的功能，如缓存、用户兴趣及流行度的计算等。为了简便起见，如无特殊说明，下文中的路由器指的均是边缘路由节点。

CCN的网络通信主要由两种包完成：兴趣包(interest packet)和数据包(data packet).CCN的网络通信主要由两种包完成：兴趣包(interest packet)和数据包(data packet)。为了获得内容，用户节点发送具有唯一内容名字的兴趣包，并且该兴趣包通过转发信息库(forwarding information base,FIB)中的信息以最长前缀匹配的方式传递给内容提供节点，其类似于当前的互联网中的路由表[10-11]。在转发兴趣包时，路由节点将一个条目添加到未决请求表(pending interest table,PIT)中，以记录该兴趣包到达的接口信息，从而为对应的数据包传输提供反向路径。在接收到数据包后，路由节点查找PIT中的相应条目，并将数据包转发到兴趣包的传入接口。转发数据后，路由节点将数据存储在名为内容存储器(content store,CS)中，即俗称的缓存。通过在网络中部署缓存，任何具有所请求数据的网络节点都可以提供数据包。与位置无关的数据检索能够有效的降低带宽消耗，从而避免了从原始内容提供者的重复数据请求。

如图1所示，节点R1发出内容请求，兴趣包沿路径到达内容提供者P，节点P将对应的数据包沿原路径发送给节点R1，若采用CCN默认的缓存策略，将在沿路径节点处缓存该内容。而后，节点R2发出对同一个内容的请求，兴趣包在转发到节点P1时，在节点的CS命中，节点P1直接将数据包发送给节点R2，而无需从内容提供者P处获取。

图1 网络模型Fig.1 Network model

2 CPA缓存策略

2.1 CPA策略概述

CCN网络由内容源服务器，缓存路由器以及用户组成。内容源服务器存储有网络中所有的内容数据；缓存路由器负责进行兴趣包及数据包的转发，内容缓存，以及缓存策略所需要的计算等能力；区域内的用户与缓存路由器相互连接，负责发起内容请求。

当兴趣包在内容源节点或缓存节点命中时，命中节点回传数据包，且在数据包中设置指针k，并赋值为初始缓存间隔值N.当数据包在回传过程中，每经过一个中间节点时，指针k-1，然后检测该节点是否为数据的请求节点，如果是，节点的请求被满足，流程结束；否则，判断k值是否为0.若k≠0，则将数据包转发至下一节点；如果k=0，则判断当前节点剩余缓存空间是否能容纳新数据。如果当前节点剩余缓存空间能容纳新数据，则在该节点缓存数据包；否则，计算该节点及其相邻节点的内容替换率、紧密度指标以及特征值向量，将数据包缓存在综合参数值最优的节点上，依次替换当前周期内流行度从低到高的内容。计算缓存替换率和实时流行度的综合属性值，若计算结果大于阈值，则将k设置为一个较小值，否则设为相对较大值，然后继续向下一个节点转发数据包。过程不断重复，在数据包到达请求节点时结束。图2给出了缓存策略的流程图。

图2 缓存策略流程图Fig.2 Flow chart of the caching strategy

2.2 缓存间隔计算方法

缓存间隔为缓存策略中的一项重要参数，用来决定缓存节点之间的跳数距离，下面给出缓存间隔的具体计算方法。

为了合理确定缓存间隔，一方面要增加网络中高流行度内容的副本数，以提高多数请求节点请求高流行度内容的服务质量；另一方面要减少大文件内容的副本数，以提高网络内容的多样性；第三，采用内容的实时流行度，综合考虑了内容在之前周期的请求数量和频率的影响，和当前周期内内容的实时热度。因此，缓存策略中采用的缓存间隔的计算方法为：

(1)

式中：s为内容大小(以chunk为单位)，即单个内容所包含的chunk数；a为比例系数；p为内容的实时流行度。为了计算内容的实时流行度，本文采用文献[12]提出的缓存流行度，计算方法为：

(2)

a=1+c×T.

(3)

式中：p[i]表示在周期i时内容的实时流行度；N[i]表示周期i内的内容缓存次数；a表示内容缓存次数的权重，其值大于1；且与每个周期的时长T的关系如公式所示；c为常数。该公式考虑了之前的缓存次数和当前周期的缓存次数，且当前周期的权重更高，时间越久，缓存次数的影响越小。此种计算方法较好地体现了内容的实时流行度。

综上所述，使用该方法可以得到每个内容的缓存间隔，根据内容的流行度和内容大小针对性的设置缓存间隔，使内容分布更加均匀。在命中节点返回数据包时，将计算好的缓存间隔携带在数据包内，用于在传输过程中指导缓存操作。

2.3 节点综合属性计算方法

当节点的缓存空间不能容纳数据包时，该节点将会计算与其相邻所有邻居节点的多项指标，做出综合判断，从而选择出最佳的缓存位置。这些指标包括缓存替换率、紧密度以及特征向量，下面介绍各项指标的定义以及作用。

1) 缓存替换率指标

定义节点替换率的计算公式为：

(4)

式中：fi是缓存空间中被替换的内容，i∈[1,m]；S(fi)是每个内容的文件大小，以chunk为单位。C(v)表示节点v的缓存空间能够容纳的chunk数。

2) 紧密度指标

Cc为某个节点的紧密度指标，表示某个节点在网络中与其它节点实现连接的难易程度，其值的计算公式为：

(5)

式中：dij表示该节点到达其它节点的跳数距离。该指标反映了某个节点对网络中的其他节点造成的间接影响力，体现了网络结构的紧密程度。

3) 特征向量指标

Ce为某个节点的特征向量指标，表示该节点通过与其它度数较高的邻居节点相连接所获得的积极影响力。Ce不仅体现了网络的相对中心点，还体现了节点的长期影响力。与紧密度指标作为对比，该指标表示某个节点对网络中其它节点造成的直接影响力。如果与一个度数很大的节点相邻，则该节点会获得更高的影响力。

节点i的特征向量指标定义为：

(6)

式中：aij为某个节点的邻居节点度数矩阵A中的元素，且特征值为λ；e=(e1,e2,…,en)为与λ对应的特征向量。

为了将前面几种属性结合考虑，定义了节点的综合属性指标，具体公式为：

(7)

式中：M(v)表示节点v的综合属性；Cc(v)表示节点v的紧密度指标；Ce(v)表示节点的特征向量指标；R(v)表示节点v的缓存替换率指标；α表示比例系数。

3 仿真分析

为了验证所提缓存策略的性能，本文采用ndnSIM平台进行仿真验证[13]。在仿真中添加了报文结构，编写了缓存策略代码，根据不同的标记作相应的收发处理。主要从缓存命中率、平均跳数和平均时延三方面对缓存策略的性能进行分析。

3.1 拓扑环境及仿真参数

如图3所示，仿照文献[14]中提供的随机网络拓扑类型，采用了NDN项目组官方提供的NDN Testbed拓扑[15]，包含了33个节点和174条链路。在网络中部署1个内容源服务器，并在拓扑中随机选取1个节点与内容源服务器直接连接。在拓扑中随机选取25个节点作为边缘路由节点，每个路由节点处的用户内容请求到达服从泊松过程，且到达率为10个/秒，其余节点作为中间路由节点。仿真中采用的其他主要参数如表1所示。

图3 仿真拓扑Fig.3 Simulation topology

参数数值链路带宽/Mbps10链路时延/ms10内容源服务器1内容数量1000请求到达频率/Hz10仿真时间/s100

我们将本文所提的基于内容流行度和节点属性的协作缓存方法(cooperative caching strategy based on content popularity and node attributes,CPA)与文献[16]中对比的两种算法进行对比：1) 一种概率式缓存算法(ProbCache)，以相同的概率在沿途所有节点进行缓存，在文中缓存概率取0.3；2) 一种概率式缓存算法(UniCache)，在沿途的路由器中只保存一个副本，即以的概率沿路径缓存内容。

3.2 仿真性能指标

本文采用以下性能评价指标评估所提缓存策略性能。

1) 缓存命中率，表示节点发起的请求在服务器之外的网内缓存命中的比率，体现了缓存算法对降低服务器负载起到的作用效果，缓存命中率越高，算法的效果越好。

2) 平均跳数，表示网络中的节点获取到内容所需的平均跳数，通过与对比算法的平均跳数做对比，能够体现缓存算法对减少网络开销所起到的作用，平均跳数越小，算法的效果越好。

3) 平均时延，表示网络中的节点获取到内容所需的平均时延，通过与对比算法的平均时延做对比，能够体现缓存算法对提升用户体验所起到的效果，平均时延越小，算法的效果越好。

4) 平均缓存替换次数，表示在仿真时间内，每个节点发生缓存替换操作的平均次数。该指标反映了缓存策略对节点替换操作的时间和能量消耗的作用影响。

3.3 仿真结果分析

对不同缓存空间大小下的几种缓存策略的性能进行了对比分析。这里采用的参数设定为：流行度参数α设为0.93.缓存空间大小从30增到50，与内容总数相比占比从3%增加到5%.

1) 缓存空间对缓存命中率的影响

如图4所示，CPA策略的缓存命中率在几种算法中表现最好。当节点缓存空间增大时，CPA比另外两个缓存策略具有更高的缓存命中率，并且有着更高的增长率。CPA算法的缓存命中率在不同的缓存空间时比UniCache策略高4.3%～6.7%；比ProbCache策略高6.0%～6.7%.CPA策略对缓存命中率的提高有着较为明显的作用，提高了缓存内容的利用率，降低了网络开销。

图4 不同缓存空间下的缓存命中率对比Fig.4 Cache hit ratio under different cache space

2) 缓存空间对平均跳数的影响

如图5所示，CPA策略的平均跳数在几种策略中表现最好。当节点缓存空间增大时，CPA比另外两个缓存策略具有具有更低的平均跳数，并且降低速率也比其他策略要快。CPA算法的平均跳数在不同的缓存空间时比UniCache策略低0.1～0.2跳，平均降低了3.6%到6.2%；比ProbCache策略低0.18～0.35跳，平均降低了7.1%到10.1%.CPA策略对平均跳数的降低有着较为明显的作用，减少了网络开销，提高了获取内容的效率。

图5 不同缓存空间下的平均跳数Fig.5 Average hop count under different cache space

3) 缓存空间对平均时延的影响

如图6所示，CPA策略的平均时延同样在几种策略中表现最好。当节点缓存空间增大时，CPA比另外两个缓存策略具有更低的平均时延，并且降低速率也比其他策略要快。CPA策略的平均时延在不同的缓存空间时比UniCache策略低0.9～2.0 ms；比ProbCache策略低1.8～3.5 ms.CPA策略对平均时延的降低有着较为明显的作用，提升了网络性能和用户的服务质量。

图6 不同缓存空间下的平均时延Fig.6 Average delay under different cache space

4) 缓存空间对平均替换次数的影响

如图7所示，在替换次数方面，CPA策略也优于其他策略，整体的替换次数要少于其他策略，且替换次数随着缓存空间的升高而降低。CPA策略的平均缓存替换次数在不同的缓存空间时比UniCache策略低420～480次左右；比ProbCache策略低750～820次左右，大大减少了缓存替换次数，节省了节点的能量消耗。

图7 不同缓存空间下的平均替换次数Fig.7 Average cache replacement number under different cache space

随着缓存空间的增加，每个节点能够缓存的内容数量也随之增多，请求在网内缓存中的命中率也随之提高，而由于缓存策略充分考虑了内容的实时流行度，能够对节点的请求进行预测，并根据缓存节点的属性与能力综合判断缓存位置的选取，有效的均衡了内容分布，提高了缓存效率，降低了网络负载，缩短了用户获取内容的时延。

4 结束语

由于ICN网络中内容流行度的高低差异，现有的缓存策略会导致热门内容集中缓存在某些节点之上，而其他节点的缓存利用率低下，针对此种网络中缓存内容分布不均的问题，该文提出了一种基于内容流行度和节点属性的协作缓存策略，通过内容的实时流行度和多项节点属性对缓存内容及缓存位置进行选择，降低网络冗余，减少内容替换，实现更均匀的内容分布。该策略综合考虑了内容的实时流行度，节点的缓存替换率、紧密度以及特征向量等指标，选择最合适的位置缓存较为热门的内容。仿真结果表明，该策略在缓存命中率、平均跳数及时延以及缓存替换次数等方面均优于其他对比算法，有效的利用了有限的缓存空间资源。在未来的工作中，我们计划将更多的节点属性进行综合考虑和判断，以做出更优的缓存决策，达到更好的缓存性能。

[1] 霍跃华,刘银龙.内容中心网络中安全问题研究综述[J].电讯技术,2016,56(2):224-232.

HUO Y H,LIU Y L.Survey on security issues in content-centric networking[J].Telecommunication Engineering,2016,56(2):224-232.

[2] IOANNOU A,WEBER S.A survey of caching policies and forwarding mechanisms in information-centric networking[J].IEEE Communications Surveys & Tutorials,2016,18(4): 2847-2886.

[3] 曾宇晶,靳明双,罗洪斌.基于内容分块流行度分级的信息中心网络缓存策略[J].电子学报,2016,44(2):358-364.

ZENG Y,JIN M,LUO H.LICA:A Segment-popularity based caching scheme in ICN[J].Acta Electronica Sinica,2016,44(2):358-364.

[4] 黄胜,刘四军,滕明埝,等.内容中心网络中一种基于内容等级及流行度的缓存策略[J].电子与信息学报,2017(6):1417-1423.

HUANG S,LIU S,TENG M,et al.Cache strategy based on content level and popularity in content centric networking[J].Journal of Electronics & Information Technology,2017(6):1417-1423.

[5] 霍跃华,刘银龙.内容中心网络中传输开销最小的协作缓存策略[J].太原理工大学学报,2017,48(1):116-121.

HUO Y H,LIU Y L.Collaborative caching strategy based on minimizing transmission cost in content-centric networking[J].Journal of Taiyuan University of Technology,2017,48(1):116-121.

[6] YAN H,GAO D,SU W,et al.Caching strategy based on hierarchical cluster for named data networking[J].IEEE Access,2017.

[7] KIM Y,KIM Y,BI J,et al.Differentiated forwarding and caching in named-data networking[J].Journal of Network and Computer Applications,2016,60:155-169.

[8] 芮兰兰,彭昊,黄豪球,等.基于内容流行度和节点中心度匹配的信息中心网络缓存策略[J].电子与信息学报,2016,38(2):325-331.

RUI L L,PENG H,HUANG H Q,et al.Popularity and centrality based selective caching scheme for information-centric networks[J].Journal of Electronics and Information Technology,2016,38(2):325-331.

[9] ZENG Y,HONG X.A caching strategy in mobile Ad Hoc named data network[C]∥Communications and Networking in China (CHINACOM),2011 6th International ICST Conference on.Harbin,2011:805-809.

[10] 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.2009:1-12.

[11] JACOBSON V,SMETTERS D K,THORNTON J D,et al.Networking named content[J].Communications of the ACM,2012,55(1):117-124.

[12] 李韬,李玉宏.一种基于内容热度的NDN缓存替换算法[J/OL].中国科技论文在线,2012.

LI T,LI Y H.A content popularity based cache replacement algorithm for NDN[J/OL].Sciencepaper Online,2012.

[13] MASTORAKIS S,AFANASYEV A,MOISEENKO I,et al.ndnSIM 2.0:a new version of the NDN simulator for NS-3[R].NDN,Technical ReportNDN-0028,2015.

[14] ZHANG G,LI Y,LIN T.Caching in information centric networking:a survey[J].Computer Networks,2013,57(16):3128-3141.doi:10.1016/j.comnet.2013.07.007.

[15] ZHANG L,ESTRIN D,BURKE J,et al.Named data networking (NDN) project[R].Relatório Técnico NDN-0001,Xerox Palo Alto Research Center-PARC,2010.

[16] CHO K,LEE M,PARK K,et al.WAVE:popularity-based and collaborative in-network caching for content-oriented networks[C]∥Computer Communications Workshops (INFOCOM WKSHPS).USA:Orlando,2012:316-321.