基于节点介数和替换率的内容中心网络网内缓存策略

崔现东 刘 江 黄 韬 陈建亚 刘韵洁



基于节点介数和替换率的内容中心网络网内缓存策略

崔现东*①刘 江①黄 韬①陈建亚②刘韵洁①③

①(北京邮电大学泛网无线通信教育部重点实验室 北京 100876)②(北京邮电大学北京市网络体系构建与融合重点实验室 北京 100876)③(南京(中国)未来网络产业创新中心 南京 211100)

网内缓存技术是内容中心网络(CCN)的关键技术之一，CCN采用传统的ALWAYS缓存策略，会造成较大冗余。改进的Betw方案仅考虑了节点介数，容易造成高介数节点缓存更替频繁，内容可用性下降。为了解决这个问题，该文提出一种综合使用网络节点介数和节点缓存内容更替速率作为缓存决策度量的新型网内缓存策略BetwRep，通过权衡节点位置重要性和缓存内容时效性实现回传内容的最佳放置。最后，基于ndnSIM平台进行的网络仿真表明，该文提出的BetwRep缓存策略取得了比Betw方案和ALWAYS方案更低的源端请求负载和更少的平均跳数。

内容中心网络；网内缓存技术；BetwRep缓存策略；节点介数；缓存替换率

1 引言

基于以上方案存在的问题，本文提出了一种综合使用网络节点介数和节点缓存内容更替率作为缓存决策度量的新型网内缓存策略BetwRep。在返回内容判决路径上哪些节点需要缓存该内容时，既考虑节点的重要性，又要考虑节点缓存内容更替状况。该策略既有效保证了内容尽量缓存在相对重要的节点上，又能通过节点的内容替换率来调控内容的缓存，使重要节点避免处于高频率的内容替换状态而导致系统性能下降。

文章组织结构如下。第2节介绍CCN路径缓存模型以及相关技术；第3节重点阐述了本文提出的BetwRep缓存判决策略；第4节详细描述了仿真环境、方案和参数的配置，并对仿真结果进行分析；第5节是结束语。

2 CCN路径缓存模型和相关技术

2.1 系统模型

2.2 ALWAYS与Betw路径缓存策略分析

文献[10]提出的Betw缓存策略，请求命中后将返回内容只缓存在分发路径最重要的节点上。由于在重要节点上，同一个内容被请求的次数会更多，使得内容在节点被缓存时间变长，这在某种程度上减缓了节点的缓存更替压力。而节点重要程度以介数作为度量，介数是节点介数中心性的简称[12,13]，用来描述节点在网络中重要性的一个度量，源于复杂网络领域，其数学定义如下：

然而，网络中节点缓存大小与系统内容总量相比非常小[14]，因此，重要节点到达的请求和经过的内容量都极为庞大，最流行的内容也会出现很快就被替换的情况，此时大量的兴趣包到达重要节点后，无法实现缓存命中，兴趣包也只能被转发到别的节点，直至内容源端。

3 基于节点介数和缓存更替率的BetwRep缓存策略

3.1 BetwRep缓存策略核心思想

CCN网络中如果一个节点位于多个内容分发路径上，便会有更多的兴趣包和内容包经过，则在该节点上更容易发生内容请求缓存命中。文献[10]提出的内容缓存算法选择介数作为度量，将返回内容只缓存在路径最重要的节点上。由于在重要节点上，同一个内容被请求的次数会更多，使得内容在节点被缓存时间变长，这在某种程度上减缓了节点的缓存更替压力。

本文目标是设计能取得高收益的网内缓存策略，并验证系统在不同缓存策略下的网络缓存性能。Betw缓存策略用来判决请求内容在返回路径上如何缓存，但由于Betw策略选取缓存节点只考虑节点的重要性，而网络中节点缓存大小远小于系统内容总量[14]，大量的请求和内容到达重要节点，导致重要节点内容替换频繁，使得流行内容在节点中的缓存时间变短，最后致使网内缓存命中率下降。另一个方面，作为网络层的技术，CCN的节点内容缓存和数据转发要求达到线性处理速度，如果出现上述情况，节点处理包的压力将会陡增，给网络带来拥塞。

图1 ALWAYS, Betw和BetwRep缓存策略实例

3.2 BetwRep缓存策略的实现

4 仿真分析

为验证本文提出的BetwRep缓存策略对于CCN网络性能的提升，本文通过ndnSIM[15,16]仿真器实现了对Betw, ALWAYS和BetwRep 3种缓存策略的仿真，并对它们的性能进行了定量的比较和分析，仿真结果验证了BetwRep缓存策略的有效性。

4.1仿真环境和参数配置

表1节点兴趣包伪代码

Pseudocode I 兴趣包处理伪代码:Initialize (serialsB(v)=[0,,0],Re(v)=[0,,0]))Initialize (serials Betw(v)=[0,,0],Repl(v)=[0,,0])for each (vkfrom i to j )If data in cache || entry in PIT Get B(v),Re(v)Calculate Betw(v), Repl(v)Calculate vk= arg max{M(v)}B=B(vk)If data in cachethen send(data)else create () discard interest_packetelse Get B(vk), Re(vk)B(v)k=B(vk),Re(v)k=Re(vk)forward request to the next hop towards jPseudocode II 数据包处理伪代码:Record Betw from corresponding content requestfor each (vkfrom j to i )Get B(vk), if B== B(vk) &&0==Dthen cache(data)else if !=NULLin face = send(data)elseforward data packet to the next hop toward

请求转发方式选择洪泛模式，节点缓存替换策略选择LRU。根据CCN的通信机制，节点具有兴趣包的聚合特性，返回内容沿着组播树分发，因此仿真网络选择树状拓扑结构，本文选取一个深度为7，总节点数为17的随机树状拓扑。

4.2 仿真结果分析

图2 网络缓存性能与节点缓存大小关系图

图3 网络即时缓存性能图

5 结束语

为了解决内容中心网络中返回内容在请求路径上如何选择缓存节点的问题，本文将节点的内容缓存替换率和节点介数作为参数构造出一个新的度量，以此提出了一个新的BetwRep缓存策略。该策略避免了ALWAYS策略带来的大量缓存冗余，同时克服了Betw缓存策略中节点选取只考虑节点的重要性而导致重要节点内容替换频繁，流行内容在节点中缓存时间变短的缺点。通过对3种方案两个性能指标平均跳数和内容源端命中率的对比发现，本文提出的BetwRep缓存策略，性能比Betw策略有了5%的提高，相比ALWAYS策略性能提高更加显著。在后续工作中，我们将在本文基础上通过引入内容的流行度，设计出基于概率的缓存策略。

[1] Jacobson V, Smetters D K, Thornton J D,.. Networking named content[C]. Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies, Rome, December 1-4, 2009: 1-12.

[2] Yi C, Afanasyev A, Wang L,.. Adaptive forwarding in named data networking[J]., 2012, 42(3): 62-67.

[3] Kideok Cho, Lee Mun-young, Park Kun-woo,.. WAVE: popularity-based and collaborative in-network caching for content-oriented networks[C].IEEE Conference on Computer Communications (INFOCOM WKSHPS), Workshops, Orlando, March 25-30, 2012: 316-321.

[4] Dan A and Towsley D. An approximate analysis of the lru and fifo buffer replacement schemes[C].Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Boulder, May 22-25, 1990: 143-152.

[5] Leet Dong-hee, Choit Jong-moo, Kim Jong-hun..On the existence of a spectrum of policies that subsumes the Least Rrecently Used (LRU) and Least Frequently Used (LFU) policies[C]. Proceedings of the 1999 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Atlanta, May 1-4, 1999: 134-143.

[6] Jelenkovic P, Radovanovic A, and Squillante M S. Critical sizing of lru caches with dependent requests[J].y, 2006, 43(4): 1013-1027.

[7] Lee Breslau, Pei Cao, Li Fan.. Web caching and Zipf-like distributions: evidence and implications[C]. Proceedings of INFOCOM’99, Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, NewYork, March 21-25, 1999: 126-134.

[8] 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, April 15-17, 2004:445-452.

[9] Chai Wei-koong, He Di-liang, Ioannis P,Cache “Less for More” in information-centric networks[C]. Proceedings of the 11th International IFIP TC 6 Conference on Networking, Prague, May 21-25, 2012: 27-40.

[10] Chai Wei-koong, He Di-liang, Ioannis P,Cache “Less for More” in information-centric networks (extended version)[J]., 2013, 36(7): 758-770.

[11] Ghodsi A, Koponen T, Raghavan B,Information- centric networking: seeing the forest for the trees[C]. Proceedings of the 10th ACM Workshop on Hot Topics in Networks, Cambridge, Massachusetts, November 14-15, 2011: 1-6.

[12] Goh K, Oh E, Kahng B,.. Betweenness centrality correlation in social networks[J]., 2003, 67(1): 1-4.

[13] Izquierdo L R and Hanneman R A. Introduction to the formal analysis of social networks using mathematics[OL]. http://www.luis.izquierdo.name, 2006.

[14] Rossi D and Rossini G. Caching performance of content centric networks under multi-path routing (and more)[R]. Technical Report, Telecom ParisTech, 2011.

[15] Afanasyev A, Moiseenko I, and Zhang L. ndnSIM: NDN simulator for NS-3[R]. Technical Report, NDN-0005, NDN Project (July 2012).

[16] University of California, Los Angeles. NS-3 based Named Data Networking (NDN) simulator[OL]. http://ndnsim. net/, 2012.

[17] Tsinghua University, P. R. China. ndn-consumer-zipf- mandelbrot[OL]. http://ndnsim.net/doxygen/ ndn- consumer-zipf-mandelbrot_8cc_source.html, 2012.

崔现东： 男，1980年生，博士生，研究方向为未来网络关键技术、内容中心网络.

刘 江： 男，1983年生，讲师，研究方向为网络虚拟化、内容中心网络.

黄 韬： 男，1980年生，副教授，研究方向为路由与交换、内容中心网络.

陈建亚： 男，1951年生，教授，研究方向为下一代网络、路由与交换.

刘韵洁： 男，1943年生，中国工程院院士，博士生导师，主要研究领域为未来网络、网络融合等.

A Novel In-network Caching Scheme Based on Betweenness and Replacement Rate in Content Centric Networking

Cui Xian-dong①Liu Jiang①Huang Tao①Chen Jian-ya②Liu Yun-jie①③

①(,,,100876,)②(,,100876,)③(,211100,)

In-network caching is one of the key aspects of Content Centric Networking (CCN), which is widely concerned recently. However, the ALWAYS caching scheme (caching everywhere on the delivery path) in CCN produces a great of redundancy, while the Betw scheme leads to that the node has the more frequent replacement with the larger betweenness centrality, which will decrease the availability of the content. In this paper, a novel in-network caching scheme named BetwRep is proposed based on a metric including the betweenness centrality and the replacement rate of one node to address the problem-where to cache along the delivery path. Simulation experiment based on ndnSIM demonstrates that the BetwRep caching scheme achieves the lower loading in the source server and less average hops than that of Betw scheme and ALWAYS scheme.

Content Centric Networking (CCN); In-network caching; BetwRep caching scheme; Betweenness centrality; Replacement rate

TP393

A

1009-5896(2014)01-0001-07

10.3724/SP.J.1146.2013.00503

2013-04-16收到，2013-07-29改回

国家973计划项目(2012CB315801, 2011CB302901)和中央高校基本科研业务费专项资金(2013RC0113)资助课题

崔现东 cuixdbupt@gmail.com