命名数据网络中基于数据请求节点的就近缓存算法

张 浪，韩 敏，郑 勇，吴婷婷，侯 睿

(中南民族大学 计算机科学学院，武汉 430074)

0 引 言

随着互联网信息量的飞速增长，目前以地址，如IP，为寻址方式的数据传输和交换方式在移动性、安全性、网络地址转换等方面出现一定制约，未来互联网的发展以及用户的需求必然以信息内容为核心而不是其所存在的地址，因此，信息中心网络(information-centric networking,ICN)[1-2]以数据信息为资源共享的特点，恰好适应了未来网络的发展趋势，目前已得到世界各国研究者的高度关注。在ICN中，命名数据网络(named data networking,NDN)[3]以其分布式的信息缓存方式、耦合路由等特点被认为是ICN中最有效的部署方案之一。

在NDN中，数据信息分布式存储或缓存在NDN所有节点中，数据请求节点(consumer)首先发出interest包去探寻所需信息，interest包中含有所需数据信息的名称，其每经过一个NDN路由器，依次在内容存储数据库(content store,CS)、待定兴趣表(pending interest table,PIT)和转发信息库(forwarding information base,FIB)中进行数据查找、端口登记、数据最长匹配查询并转发等处理。数据发布节点(publisher)收到interest包后，将对应数据信息封装成data包发送到NDN网络，data包沿interest所经历路径原路返回至数据请求节点，并在所经过的每一个NDN路由器中将此数据信息进行缓存。因此，合理优化管理NDN路由器中有限的缓存资源，能有效提高NDN网络数据存储、转发和路由性能。

1 研究现状

目前的IP网络数据传输大多基于C/S模式，数据传输的中间节点没有缓存功能，因此，请求时延和路由跳数较大，这是目前IP网络的弊端。而NDN采用沿途缓存方式(cache everything everywhere,CEE)有效提高了信息搜索和获取速度，提高了效率，但CEE会出现节点缓存趋于同质化，缓存内容可能出现大量重复从而导致信息冗余等问题；文献[4]提出只在数据信息命中节点的直接下一跳缓存应答数据包(leave copy down,LCD)，避免内容的重复缓存，但并没有考虑数据请求节点的影响，而且被替换出来的data包再次请求时只能转发到数据发布节点进行响应；文献[5]提出一种随机单点缓存方法(randomly copy one,RCOne)，即在沿途路径随机选择单个节点进行内容数据缓存，减少了信息冗余；文献[6]提出一种基于概率的缓存方法Procache(copy with probability)，依据节点距离数据源距离和路径的剩余缓存能力，计算节点对应的缓存概率，这是对零缓存和全缓存的一种折中算法，但RCOne和Procache均没有考虑请求内容的流行度问题；文献[7]提出一种根据请求内容的流行度以及存储节点的位置来计算缓存时间的缓存方法，但此流行度是静态的；文献[9]同样提出一种依据内容流行度以指数方式逐步增加沿途缓存的方案(WAVE)，但没有考虑缓存驻留时间，只是对LCD进行了有限改进；文献[8]提出一种基于节点介数的缓存方案，其原理是通过计算网络拓扑路径上介数最大的节点(最重要的节点)来进行数据缓存，这会造成了介数最大节点负载过重、频繁替换缓存、其他节点被闲置等问题。

可见，以上方案在考虑数据请求节点与数据发布节点的距离、请求内容的热度，以及动态改变数据包的缓存时间等问题上尚存在一定局限。鉴于此，本文提出一种基于数据请求节点的就近缓存算法(consumer-based proximity caching algorithm,CPCA)，该算法依据数据请求节点的不同，根据内容热度的变化趋势，将热度高的内容动态推进到数据请求节点周边，并且使热度高的内容能长时间缓存，同时将热度低的内容推到数据发布节点周边，有效提高了数据信息的首跳命中率，减少了请求时延和平均跳数。

2 CPCA算法原理

CPCA算法中规定数据从数据请求节点到数据发布节点的传输方向为上游方向，相反则为下游方向，同时本文称与数据请求节点直连的NDN路由器为请求路由器。根据算法需要，CPCA改进了NDN网络中data包的格式，如图1所示。

类型(Type)内容名字(Contentname)缓存标志位(CI)缓存时间(CT)剩余缓存时间(CRT)签名信息(Signature)数据(Data)

图1改进的data包格式
Fig.1 Improved data packet format

图1中，类型(Type)字段表明了该data包的业务类型；内容名字(content name)字段记录了该data包所承载的数据信息的名称；缓存标志位(caching index,CI)字段为缓存标志位，初始化为0，当其为1时，指示NDN路由器缓存该data包(实际上缓存的是data包中所承载的数据信息，为简单起见，本文简述为缓存data包)；缓存时间(caching time ,CT)字段记录的是该data包的缓存时间，单位为秒；缓存剩余时间(caching remain time,CRT)字段记录的是该data包的剩余缓存时间，当其为0时，该data包可被替换；签名信息(Signature)字段记录的是签名信息，如发布者ID等；Data字段为该data包承载的数据信息；此外将NDN路由器中CS的剩余存储空间大小记为(remain caching size,RCS)，data包的大小记为DS(data packet size)。

CPCA的主要思想是①当data包到达相应的请求路由器时或其CI字段值为1时，进入该路由器的CS进行缓存；②当请求路由器缓存容量达到上限，新到来的data包替换节点中已经缓存的data包，如果没有可替换状态的data包，则选择CRT值最小的data包进行替换，如果有可替换的data包，则依据LRU(least recently used)原则从可替换状态的data包中选择一个data包进行替换，将被替换出来的data包CI置为1，指示上游节点进行缓存，上游节点执行相同的替换算法，直到data包能够进入CS进行缓存；③当data包进入CS时，CRT字段的值更新为该data包的当前CRT字段的值加上CT后的值。

图2给出了CPCA算法的流程图。

图2 CPCA算法流程图Fig.2 Algorithm flow chart of CPCA

同时给出CPCA算法和缓存过程伪代码，如下所示。

Algorithm1CPCA

1 if 该节点是数据发布节点then

2 删除该data包

3 else if 该节点是对应请求节点或者该data包缓存标志位为1 then

4 缓存该data包

5 else

6 将该data包转发至下游节点

7 end if

Algorithm2Caching

1 symbol←true

2 while symbol is true do

3 if DS<=RCS then

4 把该data包插入到节点的CS中

5 CRT←CRT+CT

6 更新该data包的剩余缓存时间

7 symbol←false

8 else

9 if 没有可替换状态的data包then

10 选择一个剩余缓存时间最小的data包

11 else

12 用LRU原则从CS中选择一个data包

13 CI←1

14 将该data包向上游节点转发

15 symbol←true

16 end if

17 end if

18 end while

3 仿真与性能分析

为了验证CPCA算法的有效性，本文利用Matlab配合C++代码进行了模拟仿真实验。首先基于改进的Salama[10]算法用Matlab随机生成一个具有50个节点的NDN网络拓扑，如图3所示。不失一般性，本文假设该NDN网络中的数据信息有1 000个，每个信息内容大小设为1 MByte， NDN中间路由器缓存容量皆设为50 MByte，链路带宽为100 Mbit/s，在网络中设置了一个数据发布节点负责内容的存储和发布，在网络边缘设置有8个数据请求节点发出interest请求。Interest包的到达服从参数λ为10的泊松过程，请求概率服从Zipf分布[11]，仿真时间设为100 s，采样周期为1 s，仿真开始时所有NDN中间路由器无缓存，缓存替换采用LRU规则。

图3 实验拓扑图Fig.3 Experimental topology

将CPCA算法与目前NDN中采用的缓存方法、Procache和WAVE进行对比分析，评价指标采用缓存命中率(cache hit ratio，CHR)[12]、平均路由跳数(average route hop，ARH)[13]和平均请求时延(average request delay，ARD)[14]。CHR表示NDN网络中interest包在中间路由器被成功响应的概率；ARD表示节点发送interest包到接收到对应的data包所产生的平均时延；ARH表示成功获得响应的interest包所传输的平均距离，以路由跳数计算。设所有数据请求节点发出的interest包数量总和为m，数据发布节点响应数据包的总数为n，一个采样周期内共发出了j个interest请求，其中，第i个interest包得到响应的路由跳数为Xi，响应时延为Ti。3种评价指标计算公式如下

CHR=1-n/m

(1)

(2)

(3)

图4给出了4种方案CHR指标对比，从图4中可以看到，在运用CPCA的NDN中，数据请求节点的首跳命中率和缓存命中率皆高于其余3种方案。主要原因在于传统NDN采用沿途缓存方法(cache everything everywhere，CEE)，该方法是将原路返回的data包全部缓存在其经过的每一个NDN路由器上，因此，造成了大量的缓存冗余，且路由器中的缓存替换操作频繁，增加了其处理开销；Procache根据路由器节点与用户节点间的距离来计算节点的缓存概率，越靠近用户的节点其缓存概率就越高，因此，用户周围节点缓存替换频繁，而网络核心处节点的缓存空间利用不高；WAVE根据信息内容的请求频率以指数增长的方式增加沿途缓存信息内容的个数，但其指数式的增长方式使得用户周围节点频繁替换缓存内容，且节点间的交互报文也增加了网络负载。CPCA优先考虑在数据请求节点进行缓存，增大了首跳命中率和内容请求的就近响应率；通过动态设置data包的缓存时间，使热度越高的信息内容缓存时间越长，且被替换的data包没有被直接删除，而是向上一跳缓存，增大了缓存命中率，减小了数据发布节点的负载。

图4 4种方案的CHR比较Fig.4 CHR comparison of the four schemes

图5给出了4种方案的ARD指标对比，从图5中可以看到，在运行4种缓存算法的NDN网络中，ARD指标曲线走势皆逐渐减小，并趋于平缓，这是因为开始阶段是数据信息在NDN路由器中缓存积累的阶段，待一段时间后，NDN路由器中的数据信息量达到一定规模，便趋于稳定。同时可以看到，CPCA在整个过程中的ARD指标比其余3种方案皆具有优势，证明CPCA能够有效缩短interest包的搜索时间，提高数据信息对象的命中率。

图6给出了4种方案的ARH指标对比，从图6中可以看到，和图5相似，4种算法运行的NDN网络中，ARH指标皆逐渐降低，最后趋于平缓。主要原因在于NDN路由器的缓存逐渐趋于饱和，获取信息的路由跳数便有所减少。同样可以看到，CPCA算法在整个路由过程中，所经历的路由平均跳数较其余3种方案皆有明显的减少，主要取决于CPCA能够根据数据信息的请求频率，把热度较高的数据信息尽可能缓存于数据请求节点附近，且为了减小缓存冗余，相同数据信息不重复缓存，这样就在很大程度上减少数据请求的路由跳数。

图5 4种方案的ARD比较Fig.5 ARD comparison of the four schemes

图6 4种方案的ARH比较Fig.6 ARH comparison of the four schemes

图7给出了在NDN路由器配备100 M，150 M和200 M等不同容量缓存情况下，CPCA的ARH指标性能。从图7中看到，ARH随着缓存容量的增加而有所减少，证明缓存的增加能够有效增大interest包请求的命中率，减少平均路由跳数。

4 结 论

优化的内容缓存能有效提高NDN的数据信息搜索效率，发挥NDN网络的优势。本文针对现有缓存算法的局限，考虑到了首跳命中的重要性以及内容热度对缓存的影响，提出了基于数据请求节点的就近缓存算法。该算法重点在数据请求节点的上一跳NDN路由器中进行缓存，且把内容热度低的数据不断推送到内容源服务器数据发布节点周围，把热度高的数据拉到请求节点周围，仿真结果显示，所提算法有效提高NDN缓存命中率，降低数据获取时延。本文提出的方法在用户请求差异度较大时有良好的性能，但在用户请求差异度不大时，相邻节点间可能会存在一定的数据信息重复缓存，在今后的研究中将考虑相邻节点间的协作来进行缓存优化，进一步提升该算法的性能。

图7 不同缓存容量大小情况下的ARHFig.7 ARH in different cache capacity sizes

[1] ZHANG M,LUO H,ZHANG H.A survey of caching mechanisms in information-centric networking[J].IEEE Communications Surveys & Tutorials,2015,17(3):1473-1499.

[2] XYLOMENOS G, VERVERIDIS C N, SIRIS V A, et al. A survey of information-centric networking research[J]. IEEE Communications Surveys & Tutorials, 2014, 16(2): 1024-1049.

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

[4] BERNARDINI C, SILVERSTON T, FESTOR O. A comparison of caching strategies for content centric networking[C]// 2015 IEEE Global Communications Conference(GLOBECOM).San Diego,CA:IEEE,2015:1-6.

[5] EUM S, NAKAUCHI K, MURATA M, et al. CATT: potential based routing with content caching for ICN[C]// Proceedings of the second edition of the ICN workshop on Information-centric networking(ICN’12). New York, NY, USA: ACM, 2012: 49-54.

[6] PSARAS I, CHAI W K, AND PAVLOU G. Probabilistic in-network caching for information-centric networks[C]// Proceedings of the second edition of the ICN workshop on Information-centric networking(ICN’2). New York, NY, USA: ACM, 60.

[7] MING Z X, XU M W, AND WANG D. Age-Based cooperative caching in information-centric networks[C]// Computer Communications Workshops. Orlando, FL: IEEE, 2012: 1-8.

[8] CHAI W K, HE D, PSARAS I, et al.. Cache “less for more” in information-centric networks[C]// International Conference on Research in Networking. Berlin, Heidelberg: Springer, 2012: 27-40.

[9] CHO K, LEE M, PARK K, et al.. WAVE: popularity-based and collaborative in-network caching for content-oriented Networks[C]// 2012 Proceedings IEEE INFOCOM Workshops. Orlando, FL: IEEE, 2012: 316-321.

[10] SALAMA H F,REEVES D S,VINIOTIS Y. Evaluation of multicast routing algorithms for real-time communication on high-speed networks[J]. IEEE Journal on Selected Areas in Communications,1997,15(3):332-345.

[11] BACHER F, RAINER B, HELLWAGNER H. Towards controller-aided multimedia dissemination in named data networking[C]// 2015 IEEE International Conference on Multimedia & Expo Workshops(ICMEW). Turin: IEEE, 2015: 1-6.

[12] AOKI M, SHIGEYASU T. Effective content management technique based on cooperation cache among neighboring routers in content-centric networking[C]// 2017 31st International Conference on Advanced Information Networking and Applications Workshops(WAINA). Taipei: IEEE, 2017: 335-340.

[13] ZHANG Z, MA H, LIU L. Cache-aware named-data forwarding in internet of things[C]// 2015 IEEE Global Communications Conference (GLOBECOM). San Diego, CA: IEEE, 2015: 1-6.

[14] KIM D, KO Y B. On-demand anchor-based mobility support method for named data networking[C]// 2017 19th International Conference on Advanced Communication Technology(ICACT).Bongpyeong,South Korea:IEEE,2017:19-23.

(编辑：刘 勇)