命名数据网中基于流行度的网内缓存替换策略

刘期烈，秦庆伟，夏远鹏，李 云

LIU Qilie,QIN Qingwei,XIAYuanpeng,LI Yun

重庆邮电大学 移动通信重点实验室，重庆 400065

Chongqing Key Lab of Mobile Communications Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

1 引言

数据命名网络是信息中心网的一种典型架构，与传统的IP网络架构相比，最根本的区别是不再依赖IP地址，将传统的以主机为中心的模型转变为以数据内容为中心的模型[1]。所有的数据内容被全网统一唯一命名，并且基于内容进行定位寻址、转发路由。路由器具备和数据服务器同样的存储转发功能，用户除了在原始服务器请求内容外，可以在网内路由器节点的缓存内命中内容，极大减轻了服务器端的负载压力。

命名数据网络缓存要解决的主要有三个问题：（1）数据返回客户端，经过路由器节点需要存哪个数据；（2）在返回路径上需要缓存在哪个节点；（3）当确定在某个节点要缓存返回的数据，而该节点缓存空间饱和时，需要替换掉节点内哪个数据[2-4]。由于内容中心网对内容的请求处理速度必须是线性处理速度，所以在节点替换内容时，任何复杂度高于O(1)的策略都不能满足网络性能的要求[5]。鉴于此，很多研究工作集中在上文提到的（1）（2）问题上，对于问题（3），目前缓存替换策略仍然采用最近最少使用算法LRU（Least Recently Used）和最近最少频率算法LFU（Least Frequently Used），也有研究工作采用更为简单的先进先出FIFO（First In First Out），随机选择替换算法RND。

LRU策略是把最近最少使用的内容替换掉，LFU策略是把缓存中使用频率最少的内容替换掉，FIFO策略是把缓存中最先存进的内容替换掉，以上三种策略都存在只考虑了单一的影响因素[6-8]。由文献[8]可知LRU策略与FIFO策略不能真实反映内容的流行度。LFU按照每个缓存数据块被访问的频率的高低进行排序，由于其静态特性，即如果某数据块在过去一段时间内被大量请求，使该数据具有较大的请求频率，在最近时间该数据块的请求频率急剧下降，但由于前面的高频率请求使该数据获得了较大的权重，因此该数据即使当前请求频率很低也不能及时地将其替换，从而长期占用内存空间，使当前具有高流行度或高请求代价的数据不能被缓存。LRU策略维护一个缓存项队列，队列中的数据块按照每项的最后被访问时间排序。当缓存空间已满时，将删除最后一次被访问时间距离现在最久的项，在有些情况下可能会出现LRU将一个用户访问次数多的数据块从缓存空间中替换出来，而插入一个用户访问次数低的数据块，引起缓存污染的问题。Wang等基于GreedyDual-Size策略[9]提出一种改进型的Hetero[10]策略，该策略将节点获取数据块需要经过的跳数作为花费代价，每次替换时将代价最小的数据替换。Chen等[11]根据NDN的特点，提出LUV-Path策略，该策略将数据的权重设为本节点与服务器源端之间的距离，距离服务器较远的数据块具有相对较大的权重值，权重值较小的数据更易被节点剔除。以上策略虽然考虑了数据请求的代价，能够在一定程度上降低用户请求数据时的代价，但这些策略都没有考虑数据的流行度，这些策略不能够准确反映数据当前的流行度情况。

路由器的缓存空间和服务器相比，空间极小，网络内节点随着客户端请求次数的增加和时间推移，节点缓存空间很快就会出现饱和状态，从上游节点或服务器返回的数据，若要缓存在该节点将会面临替换掉谁的问题。如何提高网内节点的缓存空间利用率，减小数据的冗余度，将变得非常重要。

基于以上问题，本文提出了一种根据数据请求频率与最近请求时间间隔来确定数据块流行度的Po-Rep（Popularity-Replacement）缓存替换策略。该策略每次根据数据的最近请求时间差来判断数据的新鲜度，根据请求频率来判断内容在本地的热度，通过以上参量计算出节点存储空间CS（Cache Stored）中所有数据块的流行度，数据的新鲜度越高同时热度越高表明流行度越高。Po-Rep策略根据数据此时的流行度情况，有新数据到达并进行存储时，替换掉流行度最低的数据，使数据的存储更合理。仿真结果表明，该替换策略能够有效提高兴趣包在网内节点的命中率并减小用户请求数据的时延与路由跳数。

2 基于流行度预测的替换策略Po-Rep

2.1 Po-Rep策略基本思想

在NDN网络中，每个节点都具有缓存空间CS，其功能除了进行路由之外，与服务器一样可以满足客户端Interest包的请求，但是节点的CS空间有限，随着请求次数的积累，CS很快被存满，面临的最大的问题就是后续的内容根据缓存策略需要存储在该节点时，必须进行替换，选择替换掉CS中相应数据后，现有的数据仍然能够满足后续的用户请求。只有流行度高的内容才能满足更多用户的请求，降低服务器端的负载压力，增加用户在网内节点的命中率，减少用户的路由跳数。基于内容流行度的替换策略Po-Rep，利用内容在节点中被请求的次数和被请求的时间间隔，计算出流行度，对内容要进行缓存替换时，替换掉价值最低的内容。

由于在NDN中内容的流行度仅仅依靠在服务器端被请求的次数已经不能准确测定内容在整个网络内的流行度，如何实时准确预测出数据块在网络内的流行度，使每个节点中缓存的数据能够最大限度地满足用户的后续请求，对于提升NDN的整体性能非常重要。流行度高的内容说明在当前时间段和未来一段时间都是被用户大量请求的内容，具有被继续缓存在节点CS的潜在价值，而流行度低的内容在当前阶段没有满足用户的大量请求，占用了CS中存储空间，导致用户请求需要经过更多的跳数路由到服务器，当CS中流行度低的内容被替换掉后，价值更高的数据被缓存在离用户端更近的节点中，用户的请求可以更多地在网内节点命中，使网内节点内容始终保持价值最大化。

2.2 流行度计算

在整个网络中，数据内容流行度分布仍然符合Zipf分布，即二八分布，20%的内容满足整个网络的80%请求量，剩下的80%内容满足用户20%的请求量[12]。概率为：

其中，p(n)表示排序为n的内容出现的频率，排序按照内容出现频率的高低，从高到低的次序排列。

其中，r(i,s,N)表示在总数为N个内容中排序为i的内容被请求的概率，s是幂率系数，s越大，表示流行度高的内容越集中[13]。

而每个路由器节点的内容数量有限，单个节点内数据流行度不再符合数量级较大的Zipf分布，需要找出更恰当的参量来计算数据在节点中的流行度，既保证在节点中的数据保持最大价值，又可以保证整个网络的性能，提高用户请求在网内路由器节点的命中率。LRU策略把最近访问时刻作为数据流行度的参考量，距离最近一次被访问的时间越短，代表下一次被访问的概率越高，但是对于周期性操作的数据，容易出现被替换后再次请求时，已经被替换出去的现象；LFU策略把访问频率作为流行度参考量，被访问的次数越多，代表越多用户对该数据有需求，但是容易出现某个数据在某一段时间热度较高，短时间被请求的次数很多，长时间未被请求却仍然保持高频率值，而其他最近流行度高的内容被替换掉，使节点内的数据整体价值降低。

请求包在节点命中，与请求包在服务器源端命中相比，降低了路由跳数，节省了带宽，综合考虑节点内容被访问的次数，最近访问的时刻，准确预测节点中内容的流行度。用Ti表示节点中内容i所处的当前时刻，Ti_recent表示内容i最近一次被访问的时刻，Ti_first表示内容i在节点CS中第一次被访问的时刻。则此刻距离最近一次被访问时间间隔为：

Tinterval-max表示所有数据中Ti_interval对应的最大时间间隔，进行归一化处理：

而数据i平均的访问间隔可以表示为：

Mi表示在Ti_interval被请求的次数，Taverage-max表示所有数据中Ti_average对应的最大值，进行归一化处理：

内容i的流行度P(i)可以表示为：

Ti_interval越小，说明数据距离最近一次被访问的时间间隔越短，新鲜度较高，被访问的概率越大；Ti_average越小，说明数据在很短时间内被访问的次数越多，表示该数据处于高热度时期，被更多的用户需求。P(i)越大，表示内容i新鲜度越高的同时，热度也较高，可以很好地满足后续用户的请求。

替换策略的步骤如图1中流程图所示。

步骤1数据到达节点，且根据缓存策略确定要缓存在该节点，检测节点的CS是否已满，若满则转步骤3。

步骤2直接缓存返回的数据。

图1 流程图

步骤3节点根据每个数据的Ti、Ti_recent、Ti_first、Mi计算出CS中每个数据的P(i)，进行比较得出P(i)最低的对应数据，进行删除。

步骤5数据存进节点后，对其Ti、Ti_recent、Ti_first、Mi分别进行初始化。

3 仿真

为验证本文提出的Po-Rep缓存替换策略对于NDN网络性能的提升，通过ndnSIM[14]仿真平台实现了对LRU、LFU、Po-Rep三种替换策略的仿真，并对其各自的性能进行了对比和分析，仿真结果验证了Po-Rep替换策略的有效性。

3.1 仿真环境和参数配置

本实验硬件环境为Intel®Core™i3-4170CPU@3.70 GHz，8GB内存。操作系统是Ubuntu 12.04。仿真环境ndnSIM是基于NS-3的仿真模块，该模块可以实现NDN的基本功能的仿真模拟，并且可以修改代码更换缓存和路由策略，仿真结果的数据导入Matlab软件进行处理。主要参数设置如下：数据块chunk总数N=5 000，所有的数据内容设为一个chunk大小，网络中整体内容请求服从Zipf分布，幂率指数s=0.8；节点请求到达服从泊松分布，λ=10个/s；为对比性能指标随节点容量变化，仿真时每个节点缓存容量取10，15，20，…，60个chunk。请求转发方式选择洪泛方式，命中数据在返回路径上采用的缓存决策策略为LCE（Leave Copy Everywhere）[15]；由于考虑到NDN网络中拓扑结构层次性不再明显，仿真时采用随机分布的50个节点和1个服务器源端。

3.2 仿真结果分析

主要考虑的关键指标为：节点存储空间划分的比例；请求平均跳数haverage(t)；内容源端命中率γ(t)（或网内节点命中率1-γ(t)），其中

hr(t)表示兴趣包r到命中节点经过的跳数，R是在t时间内总请求数。hitr(t)表示请求r在内容源端命中，若命中取1，其他取0。

图2显示了用户请求在网内节点的命中率，可以看到Po-Rep策略和LRU、LFU策略相比在网内节点命中率要高。这是因为LRU策略和LFU策略中，流行度较高的周期性操作数据被过早替换掉，在节点存储时间过久，但在过去时间段被请求频率很高，现在时间段流行度较低的数据不能被替换出去，导致节点中数据利用率偏低，用户端请求在网内扑空率较高，随着节点空间的增加，整个网络内的数据增加，在网内节点的命中率增加。而Po-Rep策略记录并计算出节点内每个数据的流行度，流行度高的内容被长时间保存在节点CS中，流行度低的内容很快被替换出去，保证用户请求可以快速在网内节点命中。通过对内容的区别缓存，大大提高了在网内节点的命中率。图3显示了用户发出的请求包经过的平均跳数随节点容量变化，通过对图3的分析可知，请求在网内节点命中率相比其他策略，Po-Rep策略在网内命中率更高，路由到网内节点要比路由到源端服务器跳数更少，对节点存储容量分配得越大，整个网内节点的存储空间相应增加，可以有更多的请求在网内节点命中，跳数进一步减少。

图2 网内节点的命中率随节点容量变化

图3 平均跳数随节点容量变化

图4是设定每个节点的CS大小为30 chunk，显示了兴趣包在网内节点的命中率随着zipf指数s的变化情况，在s较小的点，由于流行度高的内容分布比较广泛，流行度高的内容和流行度低的内容区别不够明显，所以在网内节点的缓存内容基本上是包括了所有分布区域的数据。LRU和LFU，在本来就对内容没有流行度准确预测的情况下，单个节点的空间利用率和整个网络网内节点的冗余度得不到改善，大量的请求仍然依赖源端服务器。随着s的增大，流行度高的内容分布范围集中，导致大量的请求集中在少量流行度高的内容上，所以在网内节点命中率逐步增加，对服务器的依赖只存在于对流行度低的内容请求时。而本文提出的Po-Rep策略在s较小时，仍然有一定优势。而随着s增大，优势愈加明显。同样在图5中，由对图4的分析可知随着s的增大，在网内节点命中率更高，这样平均跳数逐渐降低。

图2 网内节点的命中率随节点容量变化

图5 平均跳数随s变化

4 结束语

为了提高命名数据网络中网内节点存储空间的利用率，本文通过对内容的流行度预测后，根据流行度的不同对内容进行差异化缓存，提出了基于流行度预测的Po-Rep策略。通过仿真证明，在降低网内数据冗余度的同时，又增加了在网内节点的命中率，平均跳数也有显著降低。但是由于没有对缓存决策策略LCE进行改进，导致用户请求在网内节点中的命中率整体偏低，在后续工作中，将会在本文基础上，利用流行度预测，对当兴趣包命中的内容确定是否在返回路径节点缓存，缓存在哪个节点的问题进行研究，对现存的缓存放置策略中出现的高冗余度性问题提出改进方案，进一步提高整个网内节点缓存空间的利用率。

图1(a)示出了四模交叉谐振器的几何结构,其关于A-A′平面是对称的,因此可以应用奇偶模方法进行分析。对于奇模激励,其等效电路如图1(b)所示。

参考文献：

[1]Zhang L，Afanasyey A，Burke J，et al.Named data networking[J].ACM Sigcomm ComputerCommunication Review，2014，44（3）：66-73.

[2]Cheng Yunho，Cheng Yuanho，Chien Chaotseng.A case study of cache performance in ICN—various combinations of transmission behavior and cache replacement mechanism[C]//2015 17th International Conference on Advanced Communication Technology（ICACT），Seoul，July 1-3，2015：323-328.

[3]Li Jun，Feng Zongming，Wu Haibo，et al.Hierarchical division-based cache storage strategy in content-centric networking[J].Journal on Communications，2016，37（1）：35-41.

[4]蔡君，赵慧民，魏文国，等.一种信息中心网络内置缓存空间大小的设计策略[J].中山大学学报：自然科学版，2015，54（6）：72-76.

[5]Cui Xiandong，Liu Jiang，Huang Tao，et al.A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].Journal of Electronics&Information Technology，2014，36（1）：1-7.

[6]Psaras I，Clegg R G，Landa R，et al.Modeling and evaluation of CCN-caching trees[C]//Proceedings of the 10th International IFIP TC 6 Conference on Networking.Berlin：Springer，2011：78-91.

[7]Carofiglio G，Gallo M，Muscariello L，et al.Modeling data transfer in content-centric networking[C]//Proceedings of the 23rd InternationalTeletraffic Congress.Piscataway：IEEE，2011：111-118.

[8]CarofiglioG，GalloM，MuscarielloL.Bandwidthand storage sharing performance in information centric networking[C]//Proceedings of the 2011 ACM SIGCOMM Conference.New York：ACM，2011：1-6.

[9]Cao P，Irani S.Cost-aware WWW proxy caching algorithms[C]//Proceedings of the USENIX Symposium on Internet Technologies and Systems.Berkeley：USENIX Association，1997：193-206.

[10]Wang J M，Bensaou B.Improving content-centric networks performance with progressive，diversity-load driven caching[C]//Proceedings of the 2012 1st IEEE International Conference on Communications in China.Piscataway：IEEE，2012：85-90.

[11]Chen X，Fan Q，Yin H.Caching in information-centric networking：From a content delivery path perspective[C]//Proceedings of the 2013 9th International Conference on Innovations in Information Technology.Piscataway：IEEE，2013：48-53.

[12]Jiang Qiqi，Tan Chuanhoo，Phang Cheewei.Understanding Chinese online users and their visits to websites：Application of Zipf’s law[J].International Journal of Information Management，2013，33（5）：752-763.

[13]葛国栋，郭云飞，刘彩霞，等.命名数据网络中基于局部请求相似性的协作缓存路由机制[J].电子与信息学报，2015，37（2）：435-442.

[14]Alexander A，Ilya M，Zhang Lixia.ndnSIM：NDN simulator for NS-3，Technical Report NDN-005[R].NDN，May 2012.

[15]Bernardini C，Silverston T，Festor O.A comparison of caching strategies for content centric networking[C]//IEEE Global Communications Conference，2015：1-6.