内容中心网络中基于内容迁移的协作缓存机制

罗 熹 安 莹 王建新 刘 耀



内容中心网络中基于内容迁移的协作缓存机制

罗 熹①③安 莹*②王建新①刘 耀④

①(中南大学信息科学与工程学院 长沙 410083)②(中南大学湘雅医学院 长沙 410013)③(湖南警察学院信息技术系 长沙 410138)④(湖南商学院计算机与信息工程学院 长沙 410205)

内容中心网络(CCN)是为了适应未来网络通信模式的转变，提供对可扩展和高效内容获取的原生支持而提出一种新型的网络体系架构，内容缓存机制是其研究的关键问题之一。现有机制在缓存节点的选择时往往过于集中，缓存负载分布严重不均，大大降低了网络资源利用率以及系统的缓存性能。该文提出一种基于缓存迁移的协作缓存机制，首先在缓存节点选择时考虑节点的中心性保证内容尽可能缓存在位置更重要的节点。同时，在缓存压力过大时，通过可用缓存空间大小、缓存替换率以及网络连接的稳定性等信息选择合适的邻居节点进行缓存内容的转移，充分利用邻居资源实现负载分担。仿真结果表明该机制能有效地改善缓存负载在节点上分布的均衡性，提高缓存命中率和缓存资源利用率并降低平均接入代价。

内容中心网络；协作缓存；负载均衡；内容迁移

1 引言

随着互联网技术和应用的不断发展，网络需求已经从最初的计算资源共享演变为主机到网络海量信息的访问，内容服务逐渐成为网络服务的主体。为了适应从发送方驱动的端到端通信向接收方驱动的内容获取方式的转变，近年来研究者们提出了以内容为中心的新型网络架构。作为其中的典型代表，内容中心网络(Content-Centric Networking, CCN)[3]成为了当前下一代网络架构研究的热点。为了缓解网络流量的快速增长对网络带宽造成的严峻压力，提高网络资源的利用率，CCN缓存机制的研究受到了学术界极大的重视。

当前CCN采用LCE(Leave Copy Everywhere)[4]作为默认的缓存策略，然而这种对经过的所有内容都进行缓存的策略容易造成过大的内容冗余，并降低内容的多样性。随后，大量学者提出了一系列的选择性缓存算法，依据一定的条件从网络中选择部分节点进行内容缓存，以求降低缓存冗余并达到较高的缓存命中率(即用户请求由中间节点缓存响应的概率)。如，Cho等人[5]提出了WAVE缓存机制，根据内容的流行度调整每个节点缓存的chunk数目，并由上游节点通过显式标记向下游节点给出需要缓存的chunk数目建议。文献[6]提出了内容年龄的概念，通过为位于网络边缘且流行度较高的内容设置较长的年龄，驱动流行内容向网络边缘的缓存，从而减少网络流量和内容获取延迟。基于内容流行度的策略试图将较流行的内容推向用户端以提高缓存命中率，然而由于缺乏对节点间联系的相关特征以及节点重要性的考虑，大大影响了这类策略的执行效果。其他类似的改进算法还包括文献[7-9]。

考虑到网络中节点位置的重要性，Chai等人[10]提出一种基于中心性的选择性缓存决策算法Betw。它将节点介数定义为经过该节点的所有最短路径的数量占网络中最短路径总数的比例，然后利用介数作为衡量标准，在兴趣包沿途中选择重要性更高的节点进行内容缓存，从而在获得较高缓存命中率的同时减少了内容的转发跳数。然而，该算法使得内容集中缓存在大介数节点上，而小介数节点的缓存资源则得不到充分利用。这种严重的分布不均导致部分节点缓存内容的更替过于频繁，必然造成缓存命中率的下降，极大地削弱了前期缓存为后续请求提供快速响应的积极作用。不少学者就此提出了一些改进方案，如文献[11]提出的ProbCache策略，它设计了一种基于加权概率的缓存决策算法，使内容返回路径中各节点缓存内容的概率反比于节点和请求者之间的距离。由于未考虑内容的流行度，不同内容对象在边缘节点处存在激烈的竞争，因而算法的性能受到一定的影响。此外，文献[12]则试图综合网络节点介数和内容替换率来选择内容的最佳缓存位置。但是从这些策略的实际效果来看，作用都非常有限。

针对上述问题，本文提出了一种基于内容迁移的协同缓存机制(Cooperative Caching Mechanism with Content Migration, CCMCM)。一方面根据节点的中心性，选取位于重要位置的网络节点进行内容缓存。另一方面，以高中心性节点为缓存中心，将其一跳邻居范围划定为一个缓存区域。在中心节点缓存压力较大时，合理地选择部分内容转移到邻居节点，利用整个区域的节点资源共同分担内容的缓存需求。这样既保证内容尽量缓存在重要节点附近，同时又充分利用了邻居节点的资源来均衡缓存负载的分布，有效地降低了缓存内容的替换率，提高了缓存命中率和网络资源的利用率。

2 CCMCM缓存机制

文献[10]指出节点重要性对于缓存决策具有重要的意义，因此我们采用自我中心网络(ego network)的介数中心性作为节点重要性的量化指标。然而为了缓解高中心性节点的缓存压力，提高内容缓存分布的均匀性，我们并非将全部的内容都缓存在高中心性节点上，而是选择高中心性节点为中心的一跳范围作为缓存区域，在高中心性节点缓存紧张时把部分内容转移到区域内的其他节点，充分利用整个区域的缓存能力实现负载分担，从而降低缓存替换频率，提高缓存命中的概率。下面详细描述CCMCM机制的工作原理。

首先，CCMCM机制中的每一个路由节点仍然维护着3个数据结构：前向转发表(Forwarding Information Base, FIB)、待定请求表(Pending Interest Table, PIT)以及内容存储器(Content Store, CS)。但是与CCN中的一般情况不同，我们将CS进一步划分为普通内容存储区(Common Content Store, CCS)和内容索引存储区(Content Index Store, CIS)两部分。CCS占整个节点缓存的绝大部分空间，用来缓存完整的内容分组。而CIS仅存储内容对象相关缓存位置信息的索引，用来记录内容的缓存节点及其相应的访问路径。

用户通过发送请求分组来请求所需的内容，每个节点会计算自己的自我中心网络介数值，同时在请求分组中记录其传播路径上的节点最大介数值。在某个节点发生缓存命中时，命中节点将从请求分组上获得的介数最大值写入到内容的数据分组中。在数据分组沿着反向路径传回用户端的过程中，沿途各节点会将自己的介数值与数据分组中记录的最大值作比较并做出相应的缓存决策。若二者相等表明当前节点即为该路径上介数中心性最高的节点，则该节点被选为缓存中心节点(Caching Center, CC)，而将其构成的自我中心网络称为内容缓存区域(Caching Area, CA)。当CC缓存空间充足时，数据分组直接缓存在其CCS内；若CC缓存占用率超过某个临界值时，则对本地CCS中的内容进行筛选，从中挑选部分内容转移到邻居节点上，同时在其CIS中建立该内容存储位置的索引信息。我们把这类需要转移出去的内容称为转存内容，将接收并缓存了某个转存内容的节点称为该内容的转存节点，而内容索引存储区中的索引信息则称之为转存内容索引。在转存内容索引中包含了转存内容的名称、转存节点名称以及相应的转发接口等信息。根据内容的名称，若在CIS中发现与某个请求分组匹配的转存内容索引条目，则CC可以将该请求分组通过转存内容索引中记录的转发接口发往转存节点来实现缓存命中。

2.1转存节点的选择

为了保证内容对象转移到其他节点后的可用性，在选择转存节点时主要考虑两方面的因素，其一是节点的缓存状态，即选择的转存节点是否具有足够的空间缓存转存内容以及能否提供较长的缓存时间；其二是转存节点与缓存中心节点网络连接的稳定性，即二者之间是否能保持较稳定的连接链路，以保证利用缓存中心节点记录的内容位置索引有较大概率实现缓存命中和内容返回。

首先我们引入节点缓存替换率的概念，记为Rep()，并将其定义为单位采样时间内节点缓存中被替换内容的大小与其缓存总容量的比值，以此作为节点缓存状态的衡量指标。Rep()的计算方法如式(1)所示。

其中，(M)表示节点中被替换的内容M的大小，为单位时间内节点缓存中替换的内容个数，()则是节点的缓存总容量。我们应尽可能将转存内容迁往内容替换率较低的节点，以避免其被过快地替换。

同时，我们将缓存中心节点与其任意邻居节点间链路连接的稳定性定义为采样周期内节点间链路的连接时间所占的比例，记为Stab()，计算公式为

其中t为链路的连接时长，T为采样时长。我们尽量选择与缓存中心节点连接稳定性更高的节点进行内容转移以提高被转移内容对象的可用性。

当需要进行缓存内容的转移时，缓存中心节点将分别计算其各个邻居节点的选择权重因子，然后从中选择权重值最大的节点作为内容的转存节点。

2.2转存内容的选择

为了通过恰当的内容迁移实现有效的邻域协同缓存，缓存中心节点首先检测并消除当前缓存区域内的冗余内容，然后根据内容的流行度来选择合适的转存内容。具体过程描述如下：

(1)节点根据流行度对CCS中缓存的所有内容按升序进行排序；

(2)若缓存中心节点与其邻居间存在冗余内容且冗余内容流行度低(排在缓存中心节点缓存内容队列的前50%)，则直接删除缓存中心节点上的冗余内容副本；反之，删除邻居节点上的冗余副本。若邻居节点间存在冗余，则选择删除缓存替换率较高的节点上的冗余副本；

2.3 转存内容索引的更新与替换

在CCMCM机制中，节点接收到的内容分组可能源自两种情况，一种是源自内容分发机制产生的正常内容传输，由其他节点转发而来的普通内容分组；另一种则来自缓存决策机制触发的内容转移存储行为。为了区分这两种不同来源的内容分组，我们在每个内容分组的头部增加了一个1 bit的转存标志位Ft。该标志位初值设为0，表示内容为普通内容分组。而该标志位被置为1时，表示该内容分组为转存分组。当节点缓存不足时，节点对普通内容分组均采用优先舍弃低流行度内容的方式进行替换。然而如果涉及到转存内容分组，则需考虑其对应的转存索引信息的更新或替换，我们分以下几种情况进行处理：

(1)由于转存节点N的移动或关机，其与缓存中心节点N的连接即将中断。

此时，N将其缓存中的所有转存内容向N进行主动通告，若N缓存空间充足，则直接取回转存内容；否则N比较转存内容与自身缓存内容的流行度，保留其中流行度较高的内容并删除对应的转存内容索引。

(2)由于转存节点N缓存不足，根据缓存替换算法某个流行度最低的转存内容M需被替换。

此时，N将向N发送包含M信息的缓存替换通告。若N缓存空间充足，则直接将M取回并将Ft复位，同时移除M对应的转存内容索引；若N缓存已满，则根据M的流行度执行相应的替换操作。

(3)缓存中心节点N的CIS空间不足。

此时，N根据流行度替换流行度最低的转存内容的索引，并通过转存节点将对应内容的F复位。

3 仿真实验及性能分析

3.1仿真环境与性能参数

为了证明CCMCM缓存机制在缓存性能上的优势，我们选择了处处缓存的LCE策略和基于介数的Betw策略作为CCMCM性能比较的对象，并利用ndnSIM[13]模拟器实现了以上3种策略的性能仿真。仿真实验中我们利用GT-ITM生成了一个由50个路由节点组成的随机网络拓扑。默认情况下，网络中内容对象总数为2000个，内容大小服从[0.1 MB, 1.9 MB]区间上的均匀分布，转存内容索引分组的大小均为1 kB。节点缓存初始为空，缓存大小均为10 MB，其中CIS占整个缓存空间大小的1%。用户请求的到达过程服从=10个/s的泊松分布，用户的访问模式服从参数=0.7的Zipf分布。同时，请求分组采用洪泛方式进行转发，缓存替换策略默认为LRU。在无特殊说明时，各实验参数均取默认值。本文采用的主要性能评估指标包括：

(1)缓存命中率：被定义为用户请求由缓存而非原始内容服务器响应的概率。

(2)缓存负载分布：通过统计节点的累积缓存内容数量(即各节点被选中为缓存节点的次数)来分析各缓存机制对缓存负载分布均衡性的影响。

3.2仿真实验结果

3.2.1缓存命中率 本小节首先研究采用不同缓存策略时系统缓存命中率随网络参数变化的情况。由图1(a)可见，随着节点缓存容量的增加，3种机制的缓存命中率都呈现增长的趋势。这是由于节点缓存空间增加使得内容分组的缓存时间延长，从而提高了缓存命中率。其中，CCMCM充分利用邻居节点缓存资源进行有效地转移存储，缓解了高中心性节点的缓存压力，从而获得了三者中最高的缓存命中率。在节点缓存不变时，内容数量的增加使得缓存资源更加稀缺。因此如图1(b)所示，3种机制的缓存命中率均随内容数量的增加明显下降，但CCMCM的缓存命中率始终优于其他二者。图1(c)反映了Zipf参数不同时各缓存机制的缓存命中率情况。由于Zipf参数越大表明用户对内容的偏好越集中于高流行度的内容，而3种机制的缓存放置策略以及基于LRU的缓存替换策略均倾向于保证高流行度内容在网络中的缓存时间。因此，缓存命中率随着用户偏好倾向性的增强逐渐增加。其中，CCMCM的缓存命中率相比其他两种机制依然有着明显的优势。

3.2.2缓存负载分布 本小节考察3种缓存决策机制下缓存负载的分布情况。为了突显出采用不同缓存机制时在网络节点累积缓存的内容数量上的差异，这里将内容数量增加到10000个，请求到达速率提高到100 个/s，在100 s的仿真时间内对节点的累积缓存内容数量进行统计。由图2可以看出，采用LCE时各节点上的累积缓存内容数量明显超过其他两种机制，这正是该机制导致大量缓存冗余的表现。同时，缓存负载在节点上的分布存在着不均衡的现象。Betw机制下缓存负载分布的不均衡现象更为突出，这是由于Betw总是选择路径上介数最大的节点进行内容缓存，因此导致了大量内容集中缓存在高介数节点上。反观CCMCM机制，通过适时地向周围的邻居节点进行缓存内容的转移，使得缓存负载分布更均衡，提高了节点资源的利用率。

图1 不同网络参数对缓存命中率的影响

图2 3种缓存机制下缓存负载在节点上的分布情况

4 结束语

缓存节点的合理选择是CCN网内缓存技术研究的关键问题。为了实现网络中节点资源的均衡有效利用，提升系统的缓存性能，本文提出了一种分布式的协同缓存机制——CCMCM。该机制在考虑缓存节点位置重要性的同时，通过适时地向邻居节点实现合理的缓存内容迁移，来提高缓存负载在节点上分布的均衡性。仿真结果表明CCMCM有效地优化了网络缓存的整体利用率，并对缓存命中率、平均接入代价等缓存性能指标具有明显的改进。在后续的工作中，我们将验证CCMCM在实际网络环境下的性能并实现算法的优化。同时，还将进一步研究如何将本文的缓存机制扩展到移动网络环境。

[1] Koponen T, Chawla M, Chun B G,.. A data-oriented (and beyond) network architecture[J]., 2007, 37(4): 181-192.

[2] Ahlgren B, Dannewitz C, Imbrenda C,. A survey of information-centric networking[J]., 2012, 50(7): 26-36.

[3] Jacobson V, Smetters D K, Thornton J D,.. Networking named content[J]., 2012, 55(1): 117-124.

[4] Laoutaris N, Syntila S, and Stavrakakis I. Meta algorithms for hierarchical web caches[C]. Proceedings of the IEEE International Performance Computing and Communications Conference (IEEE IPCCC), Phoenix, 2004: 445-452.

[5] Cho K, Lee M, Park K,.. WAVE: popularity-based and collaborative in-network caching for contentoriented networks[C]. Proceedings of the IEEE INFOCOM Workshop onNOMEN, Orlando, FL, 2012: 316-321.

[6] Ming Z, Xu M, and Wang D. Age-based cooperative caching in information-centric network[C]. Proceedings of the 23rd International Conference on Computer Communication and Networks (ICCCN), Shanghai, 2014: 1-8.

[7] 葛国栋, 郭云飞, 刘彩霞, 等. 命名数据网络中基于内容请求相关性的协作缓存算法[J]. 电子与信息学报, 2014, 36(12): 2795-2801.

Ge Guo-dong, Guo Yun-fei, Liu Cai-xia,.. Collaborative caching algorithm based on request correlation in named data networking[J].&, 2014, 36(12): 2795-2801.

[8] Wang L, Bayhan S, and Kangasharju J. Optimal chunking and partial caching in information-centric networks[J]., 2015, 61: 48-57.

[9] Qian H, Muqing W, Dongyang W,. Lifetime-based greedy caching approach for content-centric networking[C]. Proceedings of the 21st International Conference on Telecommunications (ICT), Lisbon,Portugal, 2014: 426-430.

[10] Chai W K, He D, Psaras I,.. Cache “less for more” in information-centric networks (extended version)[J]., 2013, 36(7): 758-770.

[11] 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, Helsinki, Finland, 2012: 55-60.

[12] 崔现东, 刘江, 黄韬, 等. 基于节点介数和替换率的内容中心网络网内缓存策略[J]. 电子与信息学报, 2014, 36(1): 1-7.

Cui Xian-dong, Liu Jiang, Huang Tao,.. A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].&, 2014, 36(1): 1-7.

[13] NS-3 based Named Data Networking (NDN) Simulator[OL]. http://ndnsim.net, 2013.6.

Cooperative Caching Mechanism with Content Migration in Content-centric Networking

Luo Xi①③An Ying②Wang Jian-xin①Liu Yao④

①(,,410083,)②(,,410013,)③(,,410138,)④(,,410205,)

Content-Centric Networking (CCN) is a new Internet architecture with native support for scalable and efficient content acquisition, which is proposed to accommodate the changes in future communication mode. Content caching is one of the key issues in CCN. In some existing work, the choice of caching nodes is over-focused on few special nodes, which results in an uneven distribution of cached contents. It greatly decreases the utilization of network resources and impairs the overall caching performance. In this paper, a Cooperative Caching Mechanism with Content Migration (CCMCM) is proposed. In this scheme, the centrality of node is considered in the selection of caching nodes to ensure that contents can be cached in the more important nodes as much as possible. When the cached contents are extensive, the caching node can transfer some contents to the appropriate neighbor according to the cache space available, the cache replacement rate and the connection stability between nodes. The aim is to fully utilize the resource of neighbor nodes and achieve effective load distribution. Simulation results show that the proposed scheme improves the load balance among caching nodes, increases the resource utilization and achieves high cache hit rate with low average access cost.

Content-Centric Networking (CCN); Cooperative caching; Load balance; Content migration

TP393

A

1009-5896(2015)11-2790-05

10.11999/JEIT150399

2015-04-08；改回日期：2015-07-08；

2015-08-27

安莹 anying@csu.edu.cn

国家自然科学基金(61402541, 61103204)

The National Natural Science Foundation of China (61402541, 61103204)

罗 熹： 女，1980年生，博士生，研究方向为新型网络体系结构设计、内容中心网络.

安 莹： 男，1980年生，讲师，在站博士后，研究方向为新型网络体系结构设计、内容中心网络、延迟容忍网络等.

王建新： 男，1969年生，教授，博士生导师，研究方向为网络优化理论、参数计算理论、生物信息学等.

刘 耀： 男，1976年生，讲师，博士，研究方向为延迟容忍网络、社会网络等.