面向缓存命中率的命名数据网络缓存优化策略

高全力，杨 昊,李雪花，赵 辉，金 帅，徐国梁

(1.西安工程大学 计算机科学学院，陕西 西安710048;山东如意毛纺服装集团股份有限公司，山东 济宁 272000；3.山东如意恒成产研新材料科技有限公司，山东 济宁 272000)

0 引 言

随着互联网用户及内容规模的日益增多，网络内的数据流量呈指数级增长。根据Cisco的VNI预测报告，2021年全球IP视频流量将占互联网总流量的82%，2022年IP流量达到4.8 ZiB[1]。急速增长的网络流量对于传统网络转发模式和转发链路带来了严峻考验。在此背景下，信息中心网络(information centric networking，ICN)受到广泛重视[2]。这种网络架构通信模式由端到端通信转向以海量信息获取为目标的通信。其中，NDN[3]完全以内容名字标识进行路由，充分体现了信息中心的特征，是最具前景的技术方案之一。区别于传统的TCP/IP网络，NDN网络直接对内容进行唯一命名标识，基于内容进行寻址传输，且网内路由节点具有数据缓存能力。内容请求者通过向网内发送带有标识用户想要获取内容名称的兴趣包，响应者通过发送相应的数据包沿着兴趣包路径响应请求。响应者可以是数据源服务器，也可以是网络已缓存该数据的路由节点。因此，合理的内容缓存策略是影响NDN网络内容分发效率的关键因素[4],也是当前的研究热点问题之一[5-6]。

缓存策略包括数据包经过路由节点时决定是否进行缓存的缓存决定策略，缓存空间满时应该替换掉哪些内容的缓存替换策略[7]。在缓存决定策略方面，代表性的有LCE(leave copy everywhere)[8]、LCD(leave copy down)[9]、Prob[10]等3种。LCE是NDN中默认的网内缓存策略，它将内容缓存在数据回传路径上的所有路由器节点上，提高了内容的分发和检索速度，但同时也带来了大量的网内冗余副本，缓存资源利用率较低[11]。LCD策略采用当请求在某节点命中时，返回的数据只在命中节点与靠近客户端的下游路由器节点缓存，避免了同一内容在路径所有节点的大量复制，并且只有内容被多次请求时，才会逐步缓存在离客户端较近的节点上。潜在地考虑了内容访问次数因素，但并未考虑下游各节点的缓存替换率，可能造成下游节点的替换率过高，导致缓存利用率较低。Prob策略采取每个沿途节点都以概率P缓存内容块。该方法可以认为是全局沿路缓存的一般化，当P=1时，即退化为LCE策略。在缓存替换策略方面，目前比较有代表性的替换策略有LRU(least recently used)[12]、LFU(least frequently used)[13]等。LRU采取最近最少使用策略。当节点缓存满而又需要缓存新内容时，该策略会将缓存内最近时间最少使用次数的内容块删除，即删除当前价值最小的内容。LRU只考虑了内容块访问时间单一因素，当流行内容块前期被大量访问，但最近很短时间内不访问，就会被替换出去，不能很好地反映内容块的未来使用价值。LFU利用最不经常使用策略，即删除当前缓存中命中次数最少的内容块。LFU策略只将历史访问次数这一种因素作为判断标准，当内容块前期被大量访问，而未来不再访问，根据价值函数值此内容块不会被替换，从而成为缓存垃圾，浪费了缓存空间。

鉴于上述策略的不足，韩奇辰等基于LCD策略提出了交替路由缓存策略，在内容块途径的节点交替地缓存内容块，但忽略了各个内容块的价值差异[14]。陈劼博等延伸了LCE策略，提出了一种基于节点介数的数据缓存策略，根据每个节点的介数中心性，将当前流行的内容缓存在较为重要的节点上，但未考虑到内容块可向下游分发的情况[15]。BERNARDINI等提出的MPC(most popular content)缓存决定策略，路由器缓存流行度超过固定阈值的内容块，其动态性欠佳[16]。李韬等提出一种基于流行度的缓存策略CCP(cache replacement policy based on content popularity),考虑了流行度因素，但对NDN原本架构修改较大，增加了新的表数据结构[17]。还有部分学者使用静态的流行度阈值，没有考虑流行度阈值随时间的动态变化，对缓存替换策略与决定策略之间的关系考虑亦欠佳。

针对上述问题，本文提出了动态优先权的缓存替换策略(dynamic priority replacement policy，DPRP)，将缓存内容块的访问频率特性、访问时间特性作为影响缓存价值的因素，随时间的推移动态计算出内容块的价值，将价值最小的内容替换，从而提高缓存命中率。缓存决定算法的重点是通过选择缓存节点的位置，结合缓存替换策略的过滤效应，使整个网络内都缓存价值较大的内容块，从而提升整个网络的分发效率。此外，本文还提出了高优先权缓存决定策略(high priority cache determines policy，HPCDP)：综合考虑请求路径上各节点缓存内容的价值以及替换情况，选择替换率高、缓存内容价值低的节点进行缓存，以此放大缓存替换策略的过滤效应，使网络中所有节点都尽量缓存价值大的内容块，进而提高命中率，降低请求平均路由跳数。

1 DPRP

针对传统的缓存替换策略(LRU,LFU)只考虑单一因素，无法很好地体现缓存内容块的价值，容易造成缓存利用率低的问题，提出的DPRP算法核心思想为随着时间的变化，已缓存内容块的DPR值是随时间动态变化的，能较好地反映当前节点缓存内容的价值，从而通过替换提升此节点的命中率。 DPR值越大说明此内容块流行度低，未来被访问到的概率也不大，缓存替换时将此内容替换。

本文拓扑模型表示为无向图G=(V,E),集合V={v1,v2，…,vn}表示n个节点,集合E={e1,e2,…,em}表示m条边，集合Fi={f1,r2…,fk}表示节点vi中缓存的内容，集合S={s1,s2,…,sp}表示内容源服务器的集合。

当节点vi缓存空间满需要替换时，DPRP通过式(1)计算vi每个内容块fi的DPR值(记为DPRi)，即

(1)

式中：Ti为内容块fi最后一次命中的时刻距现在的时间间隔；Hi为该内容块从放入缓存到现在的命中次数。从DPR值可以看出，当某些内容块不访问后，其DPR值会随着时间增加逐步增大，直到被替换出去。DPRP不仅考虑了内容块的已命中次数，且动态地考虑了其命中的时间特性；DPR值随着时间变化，通过DPR值不仅侧面反映了内容块历史的价值，也反映了内容块未来的价值。

2 HPCDP

NDN中数据包的传播路径是沿着请求此数据包的路径发送给请求者的，所以要从请求路径上的节点中选择合适的节点对内容进行缓存，以满足后续其他请求。针对传统的缓存决定策略，例如LCE、LCD、Prob，独立于缓存替换策略进行缓存决定，容易造成网内缓存冗余度过大，即缓存空间不能缓存尽可能多的不同内容块，从而造成缓存命中率低、请求平均跳数高的问题，提出了HPCDP。结合上述DPRP过滤效应，网络内各节点缓存的内容在未来时间内应具有较高的命中率，即DPR平均值应该较小，所以不应该在这些节点进行缓存。若某节点内容的DPR平均值较大，说明此节点替换率较高，即此节点缓存内容块的命中率不高,所以选择此节点进行缓存，以期望通过替换此节点缓存内容块的方式提高此节点的缓存命中率，进而提高此节点缓存利用率。当某一请求被响应，在响应数据回传的路径上，选择的内容块缓存节点vi应是回传路径上所通过的所有节点中DPR平均值最大的那个节点。第i个节点的DPR平均值DPRVi可表示为

(2)

式中：k表示节点vi当前时刻的缓存大小。

缓存节点的DPRVi值SaveNodeDPRV(简记为SDPRV)满足

SDPRV=max(DPRV1,DPRV2,…,DPRVn)

(3)

即缓存节点的平均DRP值为回传路径上n个节点中最大的。

为实现上述算法，需要在兴趣包中添加MaxDPR与SaveNode字段，其中MaxDPR字段用于记录兴趣包经过节点中平均DPR的最大值，SaveNode用于记录MaxDPR节点对应的节点ID。在数据包中添加SavedNode字段，其值为相应的兴趣包中SaveNode中的值，用于指示哪个中间节点应当缓存此数据包。消息格式如图1所示。

图 1 信息格式Fig.1 Message format

图2为节点接收到数据包时HPCDP策略的处理流程，图3为接收到数据包时HPCDP算法的处理流程图。

图 2 接收到数据包时算法处理流程Fig.2 Algorithm processing flow chart as data packet received

图 3 接收到兴趣包时算法处理流程Fig.3 Algorithm processing flow chart as interest packet received

从流程图2、3可以看出：当数据请求在内容源服务器满足时，数据会缓存在请求路径的某一个节点上；当数据请求在中间节点的缓存命中时，若此下游节点的平均DPR值较大，则数据会在此节点的更靠近用户的下游节点缓存，当前节点缓存的数据包会删除。从而降低了缓存冗余率，提高缓存命中率，降低请求平均跳数。

3 实验结果与分析

NDNSim[18]是开源网络模拟器NS3中实现NDN架构的一个模块。使用NDNSim version 2.8作为仿真工具，通过对NDNSim代码的修改实现本文的策略,测试本文策略的性能。网络拓扑采用Rocketfuel[19]项目测量到的真实网络拓扑ET(ebone topology)，以最大限度模拟真实网络情况。该拓扑包含163个节点，300条链路，如图4所示。

图 4 实验网络拓扑Fig.4 Experimental retwork topology

图4中圆点表示节点，边表示节点之间的链路。网络中内容总块数N为2.4×105种不同的内容，大小均为50 kiB；内容流行度服从Zipf[20]分布，Zipf参数范围为0.7～1.5,链路带宽为1 Gibit/s。网络中有4个内容源服务器，每个内容源服务器存储4×104个不同的内容，根据最短路径路由算法建立转发表。随机选择12个节点为用户接入节点，用户请求速率服从参数λ=100 次/s的泊松分布。网络中节点缓存C与内容总量N之比控制在0.300%～0.025%之间，符合缓存容量远小于网络中内容总数的实际情况。统计仿真时长为800 s，以消除偶然性误差，最大限度模拟真实情况。

3.1 实验指标

为了检验本文提出的缓存替换策略DPRP的性能，设定缓存决定策略全部采用LCE，对比LCE+LRU、LCE+FIFO、LCE+DPRP等策略的仿真结果。为了检验本文提出的缓存决定策略HPCDP的性能，设定缓存替换策略全部采用LRU,对比LCE+LRU、HPCDP+LRU、Prob+LRU的仿真结果。其中Prob策略的P设置为1时，Prob策略退化为LCE策略，即在内容经过的所有节点都缓存该内容；当P过小时，则缓存利用率较低，所以P取0.5，以增强仿真对比性。为了综合检验本文提出的DPRP策略与HPCDP策略的性能，对比HPCDP+DPRP、Prob+LRU、LCE+LRU、LCE+RAND等策略的仿真结果。其中性能指标主要采用平均路由跳数及缓存命中率。

平均路由跳数指的是用户的请求得到响应需要传输节点数目的平均值。平均跳数越小，用户获取内容的平均下载时间越小。令平均路由跳数为HRA，可表示为

(4)

式中：hi表示请求i在网络中经过的路由跳数；Req为请求消息的集合；Q为请求总数。

缓存命中率指的是路由器缓存响应的内容请求数占所有用户请求数的比例。缓存命中率越高，越能体现出缓存策略的高效性。令缓存命中率为NCR，可表示为

(5)

式中：请求i在中间路由节点缓存命中时，hti为1，否则，为0。

3.2 结果分析

图5为Zipf参数对缓存命中率的影响。从图5可以看出:随着Zipf参数的增加，6种策略的命中率不断增加，但HPCDP+DPRP策略具有最优的性能; 当Zipf参数为1.5时，本文提出策略的缓存命中率高达92%。当缓存替换策略采用DPRP时，对比LCE+LRU、LCE+FIFO、LCE+DPRP等3种策略，LCE+DPRP策略缓存命中率最高，比LCE+LRU、LCE+FIFO分别平均提高了11.7%、15.6%；当缓存决定策略采用HPCDP时，对比LCE+LRU、HPCDP+LRU、Prob+LRU等3种策略，HPCDP+LRU策略命中率最高，相对LCE+LRU、Prob+LRU分别平均提高了6.5%、5.2%。说明本文提出的缓存替换策略DPRP与缓存决定策略HPCDP都能较好的提高缓存命中率。

图 5 齐夫分布参数对缓存命中率的影响Fig.5 The effect of Zipf distribution parameters on cache hit rate

图6为Zipf参数对请求平均路由跳数的影响。从图6可以看出：随着Zipf参数的增大各策略的平均路由跳数不断减小，但HPCDP+DPRP策略具有最小的平均跳数。当缓存替换策略采用DPRP时，对比LCE+LRU、LCE+FIFO、LCE+DPRP等3种策略，LCE+DPRP策略的平均路由跳数最小，相对LCE+LRU、LCE+FIFO分别平均降低了7.9%、16.8%；当缓存决定策略采用HPCDP时，对比LCE+LRU、HPCDP+LRU、Prob+LRU等3种策略，HPCDP+LRU策略的平均路由跳数最小。说明本文提出的缓存替换策略DPRP与缓存决定策略HPCDP都能较好的降低平均路由跳数。

图 6 齐夫分布参数对平均路由跳数的影响Fig.6 The effect of Ziff distribution parameters on average routing hops

图7、8是Zipf参数为1的情况下，节点缓存容量对缓存命中率以及平均路由跳数的影响，其中缓存容量即节点可缓存的内容块的数量。从图7、8可以看出：在节点缓存容量较小的情况下，本文提出的策略相较于其他有更好的优势。说明在符合网络中缓存容量远小于内容总量的约束条件下，本文提出的策略依然有较好的性能。

图 7 缓存容量对缓存命中率的影响Fig.7 The effect of cache capacity on cache hit rate

图 8 缓存容量对平均路由跳数的影响Fig.8 The effectof buffer capacity on average routing hops

4 结束语

为了提高命名数据网络中缓存的命中率并降低请求平均路由跳数，本文提出了跟随时间变化的动态优先权缓存替换策略DPRP。DPR值不仅反映了内容块的历史价值,也反映了内容块的未来价值。根据此值进行替换后，能将缓存访问率较高的内容块留在缓存中，从而提高了缓存命中率。通过在数据传播路径上选择平均DPR值较大的节点缓存数据，可有效调整节点缓存内容，从而提高节点的缓存命中率，进而降低替换率。仿真实验表明，本文提出的策略能较好提高全网缓存命中率，降低请求平均路由跳数。

下一步的研究考虑将缓存决定策略与命名数据网络的路由机制结合，利用更多信息设计缓存决定策略，并且考虑根据数据流行度进行数据预取，进一步提高缓存命中率，提高网络分发效率。