基于层次划分的CCN网络缓存存储策略

李俊，冯宗明,2，吴海博，智江,2



基于层次划分的CCN网络缓存存储策略

李俊1，冯宗明1,2，吴海博1，智江1,2

（1. 中国科学院计算机网络信息中心，北京 100190；2. 中国科学院大学，北京 100049）

针对如何提高内容中心网络网内缓存性能的问题，提出一种基于层次划分的轻量协作的缓存存储策略。该策略通过Interest分组、Data分组以及路由器本地PIT表三者的协作把内容划分为多种优先级层级，使不同内容缓存在沿途的不同路由器。实验证明该策略可以有效地减少访问跳数，提高平均缓存命中率，降低服务器负载。

内容中心网络；缓存存储策略；层次划分；协作存储

1 引言

CCN网络是一种在现有互联网络工作模式的基础上，以内容获取与分发为主要目标的新兴网络体系结构[1,2]。通过对网络中内容进行唯一命名，部署网内缓存，并采用名字路由机制，CCN网络可以快速准确地满足用户对内容的需求，同时减少网络流量、降低传播延迟以及提高传输效率。目前，网内缓存技术已成为CCN体系结构的重要组成部分，对于CCN网络的性能提升具有重要影响。CCN网络的缓存存储、缓存发现等一系列缓存可用性相关的研究得到越来越多人的关注。如何提高缓存利用效率是缓存研究的核心问题。目前，国内外已有一些关于缓存存储策略的研究[3~12]，然而这些方案都存在不同的局限性，有些方案仅仅利用本地缓存处理机制，没有利用CCN中Interest-Data这种pull传输机制的优势，有的方案旨在求取全局最优的缓存存储策略，但是这样需要大量的额外开销，并且网络状况是动态变化的，需要经常去计算，重复开销也大，这些方案并不能很好地适应CCN网络。

在综合分析CCN网络特性的基础上，提出一种基于层次划分的概率存储方案。其主要目标是高效利用缓存空间、减少网络延时以及降低服务器负载。通过对用户请求的内容进行层次划分，转发路径上的各路由器可以对不同层次的内容进行不同的缓存存储操作，从而实现高效存储。层次划分是动态的，根据不同请求路径沿途各缓存的容量、路径跳数产生不同的划分结果。本方案使热门的内容可以缓存在路径上的不同位置，而相对冷门的内容就只能缓存在靠近内容源的位置，这有利于热门内容的访问以及缓存空间的利用。实验结果表明所提的方案在多个方面都取得了性能的提升。

本文的主要贡献如下。

1) 提出了对内容进行层次划分的方法，并在实验中实现这种划分。

2) 结合层次划分，提出一种基于层次划分和概率存储的CCN网络缓存存储策略，同时对路径之上的缓存冗余进行处理。

3) 实验评价存储策略的性能，通过与现有的缓存策略对比，实验结果表明本文的方案对于网络性能的提升较为明显。

2 相关工作

CCN网络中，请求者向内容源发送Interest分组请求内容，内容源接收到Interest请求分组之后会产生相应的Data数据分组满足Interest请求。当Interest分组请求的内容在中间节点有缓存备份时，中间节点就会返回本地副本内容（Data数据分组）以满足此次的Interest请求。这就使在设计高效缓存策略时需要考虑如何设定缓存容量、怎样去放置内容副本等难题。理想情况下，在进行缓存存储的时候，总是希望热度高的内容更靠近用户，即最热门的内容缓存的位置距离请求者最近，而相对较冷门的内容由于缓存空间的限制只能相对地远离请求者缓存，即更靠近内容源。由于热度高的内容会经常被请求，所有大量的高热度Interest请求会被就近满足，从而使网络访问延时、访问跳数以及服务器负载都大大降低。

关于缓存存储的研究主要分为2个方面：路径之外(off-path)和路径之上(on-path)缓存存储策略。

目前现有的off-path缓存存储策略旨在达到全局最优，需要收集大量的信息，比如请求者位置及请求分布、缓存容量与位置等，这会产生大量的开销同时并不能保证取得很好效果[7,13]。在文献[3~6]中提出的几种缓存存储策略，都是需要事先收集信息，在此基础上在进行最优化求解，虽然使用的方法不同但是无一例外都需要大量的额外开销。同时，网络环境也会随时变化，热门的内容也不是一直热门，会被新的热门内容取代，所以在off-path缓存存储策略下，经常需要重新计算。

相对而言，on-path缓存存储策略则主要研究怎样在转发路径上缓存特定的内容，即如何在沿途的路由器上缓存内容，以期达到较好性能。文献[1]中Jacobson等在阐述CCN网络思想时提出了LCE(leave copy everywhere)的策略，路由器缓存每个经过的内容，当缓存容量被占满时采用LRU替换策略进行替换。很显然，LCE策略需要大量的缓存替换操作同时缓存利用率也比较低。文献[8]中Arianfar等提出一种RAC(random autonomous caching)策略，让沿途的路由器概率缓存内容，并且路由器缓存的概率是一个常量。RAC并没有考虑到网内缓存容量、转发路径差异等情况，只是比较盲目地进行本地缓存操作。文献[9]中Psaras等提出ProbCache(probabilistic caching)策略，该策略利用内容转发路径上剩余的缓存容量与已取得的路径收益来计算沿途各路由器缓存该内容的概率。虽然ProbCache利用了路径的特征，考虑到缓存容量的限制，但是并没有对网内内容的热度差异进行考虑。

针对这些问题，提出一种基于层次划分的缓存存储策略，充分考虑转发路径长度，缓存容量空间与内容热度分布。

3 层次划分模型

本节首先介绍如何利用CCN网络中Interest- Data的传输特性去进行内容的层次划分，之后再介绍路径上的路由器如何根据层次划分的结果对经过的内容块进行缓存操作。

3.1 层次划分过程

层次划分过程是利用Interest-Data这种pull传输模式完成的。让Interest请求分组在去往内容源时，沿途记录请求者到内容源之间的路径信息，具体包括路径跳数与沿途各路由器缓存容量，之后对请求者所请求的内容进行优先级层次的划分。需要用到的参数如下。

CCN网络中所有的内容都被唯一命名[1],请求者consumer()发出带有某个内容名字的Interest请求分组请求对应的内容。网内各路由器利用自己的FIB转发表[14,15]把Interest请求分组转发给内容源producer()，内容源产生对应的Data数据分组沿Interest请求分组的反向路径传递给请求者。

先利用图1来说明层次划分的过程。

图1所示，请求者发送Interest请求分组向内容源请求相应内容。Interest分组沿途经过1、2、3节点，在Interest分组经过1时会告知节点1其=1，并把1节点的缓存容量1记录下来。同样地，Interest分组对后续节点做同样操作，待其到达内容源时，很容易求得此条路径上的缓存总容量c。网络中每个被请求内容的热度是不一样的，本文假设网内内容热度分布服从Zipf分布。如此，各内容都有与之对应的热度排名，这样就可以按如下方式把内容划分成个层次。

不难发现，转发路径上路由节点的个数就是划分的层次数。

3.2 层次划分必要性

在3.1节中详细地介绍了层次划分的方法，下面简单论证要进行层次划分的必要性，用以区别不同热度内容的优先级。

若网内内容满足Zipf分布，那么某个内容块被请求的概率为

3.3 缓存存储策略与去冗余功能

3.3.1 缓存存储策略

本节在介绍层次划分方案、层次划分的必要性之后，详细阐述利用层次划分结果对不同优先级的内容进行缓存存储操作。以图3为例进行叙述。

图3中中间路由节点数为3，根据3.1节所述方法，Interest分组到达内容源之后，已走过的跳数为即为4，因此内容会被分为3个层次。让最热门的内容即的内容，拥有最高的优先级可以在沿途所有的路由节点概率缓存，而最冷门的内容即的内容仅能在最靠近内容源的路由节点概率缓存，这样就会形成图3中的内容缓存情况。前面提到Interest分组沿途会把已经走过的节点数告知当前节点，由此路由器就可以知道自身存储哪些内容。例如的值为3，其可以缓存所有的内容。的值为2，其可以缓存第1层和第2层内容。的值为1，从而其仅可以缓存第1层的内容。可以发现的值越小，可以缓存的内容越少，而这些少量的内容正是网内热门的内容。

一般而言，Interest分组到达内容源走过的跳数为，因而把内容分为个层次。沿途的节点根据Interest经过时留下的值可以判断自身可缓存哪些层次的内容，具体如下。

利用层次划分方法，为不同热度的内容区别不同优先级，结合Interest分组的协作，让路由器可以识别内容的优先级，让高优先级的内容可以缓存在更靠近请求者的位置，达到了缓存存储策略的初衷，有效地提高了缓存效益。

3.3.2 去冗余功能

从图3发现，由于第1层次的内容是高优先级，按照上述概率缓存的方式有可能使节点1、2、3同时对同一个高热度内容进行了缓存操作。这样就造成内容副本的冗余，是对缓存空间的浪费。为了避免大量的冗余，应当降低内容副本在靠近内容源的节点3或2缓存的概率。因此，中间节点在缓存内容时依概率缓存，设定此概率为。乘积的前部分表示如果内容热度排名越高，则被缓存的概率越大，后半部分表示如果Data数据分组从源端走过的距离越小，则内容到达的当前位置越靠近内容源，被缓存的概率越小。这样就可以降低热门内容在靠近内容源被缓存的概率，从而避免了过多的冗余。对于第2热度层次的内容，缓存的概率为，因为第2层次的内容并不能被缓存在1，同理第3层次的内容缓存概率为。

3.3.3 算法描述

前文详细地对基于层次划分的CCN网络缓存策略进行了描述，现在对整个缓存策略的实现进行介绍。图4中给出了整个算法的实现过程。Interest分组沿途记录各节点的缓存容量并告知各节点值，Data分组沿着Interest反向路径回来时携带自身所属的内容层次，路由器接收到Data数据分组之后，会查看自己的值，通过对比决定是否对当前的Data数据分组进行缓存存储操作。

请求者 1) 设定初始值为0；2) 发出Interest请求分组携带 内容源 1) 获取Interest请求分组当前的值，对内容进行层次划分得到；2) 产生Data分组携带对应的 中间节点 1) IF Interest 请求分组到达；2) 获取的值，记录在PIT条目中；3) Interest分组的值加1并转发请求分组；4) ElSE IF Data请求分组到达5) 获取其层次信息并查看对应PIT条目中的；6) 对比PIT中记录的值与当前的内容层次7) IF 8) 概率缓存Data数据分组

3.4 缓存存储策略的轻量级协作

从上述的介绍可以看出本文提出的缓存存储策略是一种轻量级协作的策略。首先通过Interest请求分组记录沿途的跳数信息与缓存信息，并让路由器的PIT表记录Interest请求分组走过的路径跳数，最后Interest请求分组到达内容源之后，把记录的总跳数以及沿途缓存总容量告知给内容源。内容源产生对应的Data数据分组并赋予其优先级，Data数据分组经过路由器时与本地PIT表进行优先级匹配以决定后续是否进行相应的缓存存储操作。通过Interest请求分组，路由器本地PIT表以及Data数据分组三者的轻量级协作，便可以完成整个缓存存储策略，并不需要引入复杂的功能与大量的计算开销。

4 性能评价

4.1 实验环境与性能指标

4.1.1 实验环境

实验在ndnSIM平台[16]上进行仿真。ndnSIM平台基于NS-3[17]，将CCN网络的功能设计成一个独立的协议栈，用户可以方便地配置到节点之上，实现CCN网络功能部署。为了验证本缓存方案的性能，本文方案记为HDBC，将HDBC与现有的其他缓存方案进行了性能对比。在本文中呈现与3个方案的对比结果——LCE[1]、RAC[8]、ProbCache[9]。为了保证公平性，对于所有的缓存方案，都采用LRU替换策略。

实验采用图5所示的5层完全二叉树的拓扑结构，指定树的根节点为内容源，而所有的叶子节点都是请求者。同时指定请求内容服从Zipf分布。在实验中，通过对以下2个参数值的改变来观察性能变化趋势。

4.1.2 性能指标

本文将用以下3个性能指标去衡量缓存策略的优劣。

1) 跳数降低率，可以反映出缓存方案节省的带宽，其值如下

2) 缓存平均命中率，反映出缓存内容的利用效率，同时也反映出缓存替换操作的多少，其值为

3) 负载降低率，反映缓存的部署对内容源负载降低效果，其值为

4.2 实验结果与分析

5 结束语

内容中心网络是一种以内容为中心的新兴网络体系结构，其突出特点之一就是通过网内缓存技术，快速地响应用户对网络中内容的请求，同时减少服务器负载、冗余流量。在缓存内容时，总是希望热度更高的内容在靠近用户处缓存，使最热门的内容缓存在离请求者最近的地方，这样接下来对热门内容的访问收益会大幅提高，而较冷门的内容由于缓存空间有限只能远离请求者缓存，即更靠近内容源。因而本文提出了一种基于层次划分的CCN网络缓存存储策略，把网内内容划分为不同优先级，让转发路径上的路由器去存储不同优先级的内容，尽可能地保证更热门的内容缓存在距离请求者更近的位置，同时对路径之上的缓存冗余进行了处理。通过实验与现有的on-path缓存方案的对比，表明本文所阐述的方案各项性能指标较其他方案都有大幅度的提高。接下来需要继续开展的工作是把方案应用到真实网络环境，可以进一步利用中国科技网的海云创新实验环境[18]进行实验。

[1] ACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]//The 5th International Conference on Emerging Networking Experiments and Technologies. ACM, c2009: 1-12.

[2] AHLGREN B, et al. A survey of information-centric networking[J]. Communications Magazine,2012, 50 (7) :26-36.

[3] WANG Y G, et al. Advertising cached contents in the control plane: necessity and feasibility[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2012 IEEE Conference on. c2012: 286-291.

[4] SANG S, BI J, WU J P. Collaborative caching based on hash-routing for information-centric networking[J]. ACM Sigcomm Computer Communication Review, 2013, 43(4): 535-536.

[5] SAIL. NetInf Content Delivery and Operations[R]. SAIL Project, SAIL Project Deliverable D-3.2, 2011.

[6] SOURLAS V, FLEGKAS P, PASCHOS G S, et al. Storage planning and replica assignment in content-centric publish/subscribe networks[J]. Computer Networks, 2011, 55(18): 4021-4032.

[7] REN J, QI W, et al. MAGIC: a distributed max-gain in-network caching strategy in information-centric networks[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2014 IEEE Conference on. c2014: 470-475.

[8] ARIANFAR S, NIKANDER P, OTT J. On content-centric router design and implications[C]//Proc of ReARCH Workshop. New York, NY, USA, c2010: 1-6.

[9] PSARAS I, CHAI W K, PAVLOU G. Probabilistic in-network caching for information-centric networks[C]//Proc of ICN Workshop on Information Centric Networking. New York, NY, USA, c2012: 55-60.

[10] MING Z X, XU M W, WANG D. Age-based cooperative caching in information-centric networks[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2012 IEEE Conference on. c2012: 268-273.

[11] CHAI W K, HE D, PSARAS I, et al. Cache less for more in information-centric networks[C]//Networking 2012, Ser Lecture Notes in Computer Science. c2012: 27–40.

[12] EUM S,et al. CATT: potential based routing with content caching for ICN[C]//The Second Edition of the ICN Workshop on Information-centric Networking. c2012.

[13] WANG Y, LEE K, VENKATARAMAN B, et al. Advertising cached contents in the control plane: Necessity and feasibility[C]//Proc. of IEEE INFOCOM WKSHPS. c2012: 286-291.

[14] HOQUE A K M, AMIN S O, ALYYAN A, et al. Nlsr: named-data link state routing protocol[C]//The 3rd ACM SIGCOMM Workshop on Information-centric Networking. ACM, c2013: 15-20.

[15] WANG L, HOQUE A K M, YI C, et al. OSPFN: An OSPF Based Routing Protocol for Named Data Networking[R].University of Memphis and University of Arizona, 2012.

[16] ALEXANDER A, MOISEENKO I, ZHANG L X. ndnSIM: NDN simulator for NS-3 Named Data Networking (NDN) Project[R]. 2012.

[17] HENDERSON T R, et al. ns-3 project goals[C]//The 2006 Workshop on ns-2: the IP Network Simulator. ACM, c2006.

[18] SCIE project [EB/OL]. http://scie.ac.cn/view/scie.jsp.

Hierarchical division-based cache storage strategy in content-centric networking

LI Jun1, FENG Zong-ming1, 2, WU Hai-bo1, ZHI Jiang1, 2

(1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

For the issue of improving the performance of in-network cache in content-centric networking, a hierarchical division-based lightweight collaboration cache storage strategy was proposed. According to the strategy, content was grouped into different hierarchies by the cooperation of Interest package, Data package and the local PIT of routers, so that the contents could be cached in different nodes along the delivery path. The performance of the scheme was evaluated by comparing with the well-known schemes through simulation. Experimental results indicate that the scheme has good performance in reducing access hops, increasing the average cache hit ratio and reducing the server load.

content-centric network, cache strategy, hierarchical division, collaborative caching

TP393

A

10.11959/j.issn.1000-436x.2016005

2015-01-10；

2015-04-30

中国科学院计算机网络信息中心“135”规划重点培育方向专项基金资助项目（No.CNIC_PY_1401）；国家重点基础研究发展计划（“973”计划）基金资助项目（No.2012CB315803）；中国科学院知识创新工程青年人才领域基金资助项目（No.CNIC_QN_1303, No.CNIC_QN_1508）；中国科学院计算机网络信息中心主任基金资助项目（No.CNIC_ZR_201204）

Five Top Priorities of“One-Three-Five”Strategic Planning, CNIC (No.CNIC_PY-1401), The National Basic Research Program of China (973 Program) (No.2012CB315803), Knowledge Innovation Program, CAS (No.CNIC_QN_1303, No.CNIC_QN_1508); Director Fund, CNIC (No.CNIC_ZR_201204)

李俊（1968-），男，安徽桐城人，博士，中国科学院计算机网络信息中心研究员、博士生导师，主要研究方向为下一代互联网、网络安全等。

冯宗明（1989-），男，安徽马鞍山人，中国科学院大学硕士生，主要研究方向为下一代互联网关键技术。

吴海博（1981-），男，山东泰安人，博士，中国科学院计算机网络信息中心助理研究员，主要研究方向为下一代互联网缓存技术。

智江（1983-），男，山西太原人，中国科学院大学博士生，主要研究方向为下一代互联网关键技术。