基于缓存价值的命名数据网络缓存优化策略

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

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

0 引 言

随着互联网生态及网络技术的飞速发展，网络内的流量不断增长，根据思科的VNI预测报告，2022年全球用户数据流量将达到4.8 ZB[1]。快速增加的网络流量及对网络质量要求的不断提高，现存的TCP/IP以链接为中心的网络架构逐渐显现出一些弊端。建立链接的目的是传输信息，用户关心的是信息本身，而不关注信息的存储位置。在此思想及背景之下,信息中心网络(Information Centric Networking, ICN)[2-3]得到飞速发展。信息中心网络的思想一经提出，便有众多新型的网络架构被提出，大量科研机构投入研究，启动了一系列与此相关的科研项目。DONA[4]项目启动于2006年，项目架构设计考虑了路由器缓存、命名、命名解析、寻址等问题，虽然目前该项目已经结束，但其研究成果为后续各种项目提供了启发。PSIRP[5-6]项目启动于2008年，历时2年，倡导以信息为中心的发布-订阅网络模型作为未来网络架构，从而解决当前网络中由于是否信任信息发送者而产生的众多问题。NetInf[7]启动于2008年，通过数据类型定义数据名字，并给出了多种解析方式。命名数据网络(Named Data Network, NDN)[8-9]启动于2010年，是目前最有潜力的命名NDN。NDN中路由器具有缓存能力，可以缓存经过的数据包，以满足下次相同的请求。NDN中有2种包类型——兴趣包与数据包，请求方通过发送带有请求内容名的兴趣包请求数据，内容源服务器或缓存有该数据的中间路由器接收到该请求时，通过发送相应的数据包沿着兴趣包传输路径反向传输至用户，由于路由节点有缓存能力，可以响应部分请求，所以将数据包合理地缓存到网络内的路由器节点，能有效地提高网络的分发效率[10],所以命名数据网络中缓存策略是当前的研究热点之一[11-12]。

缓存策略包括缓存决定策略与缓存替换策略[13]。传统的缓存决定策略有LCE(Leave Copy Everywhere)[14]、LCD(Leave Copy Down)[13]、Prob(Copy with Probability)[14]、MCD(Move Copy Down)[13]等。LCE是NDN中默认的缓存决定策略，LCE将数据包缓存到经过的所有路由器节点，虽然充分利用了缓存空间，但各个路由节点存在大量相同的缓存内容块，冗余度较大。LCD策略采用标志位指导缓存，当一个节点发生缓存后，设置标志位使其下游节点不缓存，从而降低了缓存冗余度，当同一内容被大量请求时，此内容会逐渐缓存至边缘节点，虽然降低了边缘用户的请求代价，但可能造成边缘节点的缓存压力过大。Prob策略即概率缓存策略，每个路由器节点根据概率可能缓存数据包也可能不缓存此数据包，当P=1时，即退化为LCE策略，其随机性较大，缓存利用率较低。命名数据网络中传统的缓存替换策略主要有LRU[15](Least Recently Used)、LFU[16](Least Frequently Used)、Rand(Random)。LRU即最近最少使用策略，当需要缓存替换时，会将最近时间内具有最少使用次数的内容块删除，只考虑最近时间内访问次数这一单一因素，不能较好地反映内容块的价值。LFU即最不经常使用策略，即删除缓存中命中次数最少的内容块，同样也不能较好地反映内容块的价值。Rand策略即随机替换策略，当需要替换时随机选择一个对象移除，随机性较强，性能不稳定。

针对上述问题，韩奇辰等人[17]优化LCD缓存决定策略提出了交替路由缓存策略，在数据包路径上交替地缓存，提高了缓存利用率，但忽略了各个内容块的价值差异。陈劼博等人[18]优化了LCE策略，根据每个节点的重要性即介数中心性，将当前网络内较为流行的内容缓存到节点介数较大的路由节点上，但未考虑到可将内容块逐渐下发至下游节点。Bernardini等人[19]提出的MPC(Most Popular Content)策略，路由器节点缓存流行度超过固定值的内容块，实时性较差。朱轶等人[20]提出一种基于流行度的缓存策略，考虑了流行度因素，但使用静态的流行度阈值，其动态性考虑欠佳。

针对上述问题，本文提出一种动态缓存价值的缓存替换策略DCVRP(Dynamic Cache Value Replacement Policy)，缓存价值度量考虑了请求内容大小、请求所花费的跳数以及内容块被访问的时间特性，且其缓存价值随着时间动态变化，从而在缓存替换时保留价值较大内容块，进而提高网络内的缓存命中率。缓存决定策略主要是根据相应规则决定是否缓存当前经过的数据包，本文提出一种动态缓存价值的缓存决定策略DCVDP(Dynamic Cache Value Determines Policy),将兴趣包经过的所有节点的缓存情况作为参考因素，最终合理地选择数据包缓存的节点。

1 DCVDP缓存决定策略

由于被请求的数据包的大小不同，以及请求者距离内容服务器(Content Server, CS)的跳数不同，所以将被请求数据包大小及距离作为考量因素，计算此被请求内容块的初始价值。计算方式如下：

W0=Size·Hops

(1)

其中，Size是被请求数据包的大小，单位为MB, Hops为CS与内容请求者之间的路由跳数。当所请求的内容块越大，请求跳数越大，其初始价值就越大，越具有缓存价值，缓存所得的收益越大。

中间路由节点缓存的内容块价值随时间及请求次数的变化方式如下：

W=1/(W0·T/C)

(2)

其中，T表示当前时刻与该内容块最后一次被请求时刻相减的时间差，C表示CS中此内容块的缓存命中次数。从表达式可以看到随着T增大，即内容块当前时刻与最后一次访问时刻的时间差越来越大，T/C的值将越来越大，其缓存价值将越来越小。

为了充分利用网内各路由节点的缓存空间，若数据包传输路径上存在缓存空间，则直接缓存该内容；若各个节点缓存空间都满，则缓存在平均缓存内容价值最小的路由节点上。各节点平均缓存内容价值计算方式如下：

(3)

其中，nj为节点j缓存内容的总块数。

为了实现上述算法，需要在兴趣包中添加Node字段、MinValue字段及Hops字段，数据包中添加Node字段。其中数据包与兴趣包中的Node字段用于标识缓存数据包的路由节点ID；兴趣包中的MinValue字段用于记录请求路径上节点的最小平均缓存内容价值；Hops字段用于记录跳数，兴趣包每经过一个路由器，Hops字段数值加1。消息格式如表1所示。

表1 消息格式

当中间路由节点接收到兴趣包时处理流程如图1所示。

如图1所示，当兴趣包在CS命中时，节点将兴趣包中的Node字段，写入数据包的Node字段以指示其下游缓存此数据包的节点。当节点接收到数据包时处理流程如图2所示。

2 DCVRP缓存替换策略

针对命名数据网络中LRU、LFU等缓存替换策略存在的无法较准确地在缓存满的情况下将价值小的内容替换出去，保留价值大的内容块，造成的缓存利用率低的问题，本文提出DCVRP缓存替换算法，缓存价值越大说明此内容块流行度越大，即价值越大，未来被访问到的概率越大。其基本思想是，随着时间的流逝，路由器CS中所缓存的内容块的价值是随时间流逝动态变化的，所以能比较准确地反映当前时间内容的价值，实时性较好。具体规则为当节点有要缓存的数据包但是缓存已满时，通过式(2)计算各内容块的缓存价值，然后将价值最小的缓存内容替换出去。从式(2)可以看出，内容块的缓存价值综合考虑了访问的次数、访问时间特性及访问者与请求者之间的路由跳数。

3 实验结果与分析

仿真实验使用NDNSim2.8[21-23]，通过编写脚本及修改代码，测试本文所提策略性能。网络拓扑采用Rocketfuel[24]项目提供的真实环境网络拓扑，此拓扑包含163个路由器、300条链路，如图3所示。其中圆点表示路由器，连线表示路由器之间的链接。网络中内容总块数n=160000，流行度服从Zipf[25-26]分布，Zipf参数设置为0.7～1.5。链路带宽为1 Gbit/s，网络中有4个内容源服务器，每个内容源服务器存储40000个不同的内容。随机选择12个节点为请求节点，用户请求速率服从参数λ=100 req/s的泊松分布[27]。网络中节点缓存C与内容总量之比控制在0.025%～0.3%之间，符合缓存容量远小于网络中内容总数的实际情况。统计时长为400 s，以消除偶然造成的误差，最大限度模拟真实情况。

3.1 实验指标

为了检验本文提出的缓存策略的性能，对比DCVDP+DCVRP、Prob+LRU、LCE+LRU、LCE+RAND的仿真结果。指标采用平均路由跳数(Average number of Route Hops, ARH)及缓存命中率(Cache Hit Ratio, CHR)。

平均路由跳数是指兴趣包被路由节点或内容源服务器满足的平均跳数，平均路由跳数越小，则说明响应越快。计算方法如下：

(4)

其中，hi表示请求数据包经过的路由跳数，Req为请求消息的集合，Q为网络内请求总数。

缓存命中率是指兴趣包在路由器节点被满足的数量占请求总数的比例，缓存命中率越高，意味着缓存策略效果越好。计算方法如下：

(5)

其中，Q表示请求总数，Req为请求消息的集合，hiti表示请求i是否在中间路由节点缓存命中。

3.2 结果分析

图4为Zipf参数对平均请求跳数影响的仿真结果，横轴为Zipf分布参数，纵轴为平均路由跳数。从实验结果可以看出，各缓存策略下，Zipf参数越大，平均请求跳数越小，对比于传统的缓存策略Prob+LRU、LCE+LRU、LCE+RAND，本文提出的策略有更小的平均请求跳数，说明了其可用性及有效性。

图5为Zipf分布参数对缓存命中率影响的仿真结果，横轴为Zipf分布参数，纵轴为缓存命中率。从仿真结果可以看出随着Zipf分布参数的增大，4种策略的缓存命中率不断增加，但本文提出的策略具有最优的性能，当Zipf分布参数为1.5时，本文提出策略的缓存命中率高达85%。对比LCE+LRU、LCE+RAND、Prob+LRU这3种策略，本文提出的DCVDP+DCVRP策略命中率最高，相对其他策略平均提高了6%，这说明本文提出的策略相比传统的缓存策略有更高的缓存命中率。

4 结束语

为了更有效地利用命名数据网络中路由节点的缓存空间，本文提出了基于缓存价值的缓存决定策略DCVDP，将内容块大小与请求跳数作为考量因素，且内容块价值随时间动态变化，从而更实时地反映内容块的价值。基于此提出了DCVRP缓存替换策略，当需要替换时将当前路由节点中价值最小的内容替换出去，从而提升整个网络内缓存的利用率。经过大量仿真实验，结果表明本文提出的策略相比于传统的策略能更好地提升缓存命中率及降低平均请求跳数。

下一步将考虑更多反映内容块价值的因素，更加准确地反映内容块的缓存价值，从而进一步提升整个网络的分发效率。