社团感知的ICN缓存策略

蔡君，刘燕，罗建桢，余顺争，吴晓萍



社团感知的ICN缓存策略

蔡君1，刘燕1，罗建桢1，余顺争2，吴晓萍1

(1. 广东技术师范学院 电子与信息学院，广东 广州，510665；2. 中山大学 数据科学与计算机学院，广东 广州，510006)

为了使以信息为中心的网络缓存内容在空间和时间上分布更合理，提出一种社团感知的缓存策略(SCCNC)；以社团为单位，社团重要度高的节点缓存原始块，其他节点缓存编码块，在不增加缓存空间的条件下，提高缓存命中率和缓存多样性。研究结果表明：SCCNC策略与其他3种策略相比，能更好地提升包括缓存命中率和传输流量等缓存性能。

信息中心网络；缓存；节点社团重要度；网络编码

随着新应用的不断涌现，流量产生和传输的方式也将发生根本性变换，其中大部分流量来源于用户驱动的内容获取类应用，这使得当前基于端到端通信的TCP/IP网络架构遇到前所未有的挑战。为了适应用户和应用的需求，增强互联网架构的移动性、安全性和可扩展性，国内外研究者提出了一系列以信息或内容为中心的全新网络体系架构[1−4]，这些架构统称为以信息为中心的网络(information-centric networking，ICN)[5]。为缓解网络流量快速增长对网络带宽造成的巨大压力，ICN通过为全网节点增加缓存功能，让内容距离用户更近，减少网络流量。缓存策略决定了内容在网络中的时空分布，影响网络的流量行为。ICN中原始缓存策略是LCE(leave copy everywhere)，即网络中的每个节点都缓存收到的内容，这会造成极大的缓存冗余。为此，国内外研究学者提出了多种缓存机 制[6−12]。现有的缓存机制主要存在以下问题：在缓存位置上，大多从全局角度出发，而缓存的目的是为了满足局部用户的需求；在替换策略上，每个节点采用相同的替换策略，导致缓存内容同质化。近年来，不少研究者认为将网络编码引入ICN可以提升网络性 能[13−18]。然而，由于ICN的网内缓存机制，同一个编码块有可能会被转发路径上的多个节点缓存；相同或是线性相关的编码块有可能会响应给同一个用户，造成用户收到线性相关的编码块无法解码的情况。有研究表明[19]，Internet网络拓扑结构呈现社团特性，在同一社团中，节点社团重要度大的节点不仅易被社团内的节点访问，也易被社团外的节点访问。为此，本文作者提出社团感知的缓存与缓存替换策略(SCCNC)，以不同流行度的内容在网络中分布更合理。在SCCNC中，把原始内容块缓存在其经过的各社团内节点社团重要度最大的节点上，编码块缓存在节点社团重要度较低的节点上。同时，本文作者提出用编码代替移除的缓存替换策略，在不增加节点缓存空间的条件下，提升缓存内容多样性和缓存命中率。

1 SCCNC缓存策略

1.1 节点社团重要度定义

1.2 Interest包和Data包转发机制

在SCCNC中，Interest记录其转发路径上的每个社团中节点社团重要度的最大值，即{1max,2max, …,Imax}，其中Imax表示Interest转发路径上第个社团中节点重要度的最大值。当Data沿Interest转发路径返回用户时，中间节点通过对比自己的节点重要度I及Data携带的该社团的节点重要度最大值Imax，制定对应的缓存方案。本文作者设计了Interest合并机制，用于合并节点收到的多个Interest，目的是减少Interest包和Data包的通信开销。当节点N收到Interest时，将自己的节点重要度I与Interest中携带的当前社团的重要度最大值Imax进行对比，若I＞Imax，则令Imax=I。当Interest被转发到1个新的社团时，遇到的第1个节点N1(记为FirstNode)，记录下游社团的节点重要度最大值，即(i−1)max。这样Interest只需携带当前社团的节点重要度最大值，以减少Interest的通信开销。SCCNC示例如图1所示。由图1可知：当社团2中的节点21收到Interest(,1,4)时，用自己的节点社团重要度21替换Interest中节点社团重要度最大值4，然后将新的Interest即Interest(,1,21)转发给上游节点，同时新建1条PIT(pending interest table)条目记录Interest(,1,4)。

图1 SCCNC示例

表1所示为扩展的PIT表。

表1 扩展的PIT表

当节点N从接口收到Interest时，首先检查其PIT表。

Imax,(i−1)max>

其中：“ContentName”为内容名；“ClunkID”为内容块的名字；“Faces”为收到Interest的接口号；“Imax”为Interest转发路径上当前社团c的节点重要度的最大值；“(i−1)max”为Interest转发路径上当前社团c的下游社团(i−1)的节点重要度最大值，只有当前社团c中的FirstNode记录(i−1)max。若PIT中已有对应的表项，则将新到的Interest与其合并，同时丢弃该Interest；否则，新建1条PIT表项。Interest的转发过程如算法1所示。

算法1 Interest转发过程 Initialize Ii=0; foreach node Njreceiving Interest from face k do if cache hit then send Data Dp(Ii); else ifPIT exists then add face k into face list; ifnode Nj­ is the FirstNode then add Ii into I(i−1)max, let Iimax=0; else add Ii into Iimax; end if else ifIj＞Iithen let Ii=Ij; end if end if establish a new PIT entry for Interest, let Iimax=Ii, I(i−1)max=0; forward Interest to next hop; end if end for

在SCCNC中，Data包携带从Interest或PIT表中提取的节点社团重要度信息Imax，沿Interest转发路径返回用户。中间节点在收到Data包时，对比自己的节点社团重要度I和Data包携带的节点社团重要度最大值Imax，根据对比结果制定相应的缓存策略。Data包的转发过程的伪代码如算法2所示。

算法2 Data转发过程 When an Data (Iimax) arrived for each node Njdo cache Data according to Algorithm 3; check PIT table; foreach face k in face list of PIT table do ifIik≠0 then Iimax=max{Iimax, Iik}; else Iimax=I(i−1)max; end if send Data out of face k; end for end for

1.3 基于网络编码的缓存机制

以社团为单位，在同一社团内，根据Interest转发路径上各节点的社团重要度制定不同的缓存策略：重要度最高的节点缓存原始内容块，这是因为重要度高的节点更容易被其他节点访问；重要度低的节点缓存编码块，以节省缓存空间，提高缓存多样性。当节点N收到Data包，且Data包中携带的是内容的原始内容块时，将自己的节点重要度I与Data中携带的当前社团的重要度最大值Imax进行对比，若I=Imax，则将该内容块存储到本地缓存中；否则，查看本地缓存CS(content store)中是否有内容的内容块′，若存在，则对和′进行随机网络编码，生成新的编码块″，并用″替换′。将网络编码应用到缓存中，1个编码块包含多个内容块的信息，可以响应多个内容块的请求。该缓存机制实现了缓存在网络空间上的合理分布，减少了网络延迟，提高网络的传输效率。缓存机制的伪代码如算法3所示。

算法3 SCCNC缓存策略 When an Data (Iimax) arrived if Data is an original block then if Ij=Iimaxthen cache original block into ContentStore; else ifcache exist then encoded original block with other coded blocks in ContentStore; end if end if end if

1.4 基于网络编码的缓存替换策略

在SCCNC中，以社团为单位，同一社团内根据各节点的节点社团重要度不同，执行不同的缓存替换策略。节点社团重要度大的节点，流行度低的缓存内容被替换的概率大；而节点社团重要度小的节点，流行度高的缓存内容被替换的概率大，这样可以实现缓存在时间和空间上的合理分布。

当缓存替换发生时，假设内容是待移除的内容，若缓存的是个原始块，则对个原始块进行随机网络编码，生成1个编码块，缓存该编码块，移除个原始块。这样做的好处是可以释放−1个内容块的缓存空间，同时保留个内容块的信息，以响应后续 请求。

2 仿真实验与分析

1) 平均下载时间。平均下载时间是指平均每个用户从发送第1个Interest到该用户接收最后1个内容块所需的时间。

2) 缓存命中率。缓存命中率被定义为由缓存响应Interest的概率而不是内容服务器响应的概率，是衡量缓存性能的重要指标。缓存命中率越高，代表网络的缓存效率越高。

5) 传输流量。传输流量被定义为从第1个用户发送Interest 到最后1个用户收到最后1个内容块的整个过程中网络传输的Data包数据量。

(a) 平均下载时间随Zipf参数的变化；(b) 平均下载时间随用户请求数量的变化

图6所示为4种缓存方案的跳数减少率。由图6可知：SCCNC在跳数减少率方面比其他缓存方案具有更佳的性能表现。其原因是，SCCNC中各节点根据其节点重要度做出不同的缓存替换决策。在缓存耗尽时，利用编码代替移除的方法，释放缓存空间，同时保留多个内容块信息。由此可见，本文作者提出的基于节点社团重要度和网络编码的缓存替换策略使不同流行度的内容在时间和空间的分布更合理。

(a) 缓存命中率随Zipf参数的变化；(b) 缓存命中率随用户请求数量的变化

1—SCCNC；2—NC-CCN；3—CC；4—LCD。

(a) 传输流量随Zipf参数的变化；(b) 传输流量随用户请求数量的变化

1—SCCNC；2—NC-CCN；3—CC；4—LCD。

3 结论

1) 提出一种社团感知的ICN缓存策略(SCCNC)，具有不同节点社团重要度的节点采取不同的缓存决策和缓存替换策略，使缓存内容在时间和空间分布上更加合理。

2) 将网络编码引入缓存决策和缓存替换策略，在不增加缓存空间的情况下，提高缓存命中率和缓存多样性。

3) 在多种实验条件下对SCCNC策略进行仿真验证。与其他3种缓存策略相比，该策略能更好地提升包括缓存命中率和跳数减少率等在内的网络缓存 性能。

[1] AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. Second NetInf architecture description[EB/OL]. [2010−01−14]. http:// www.4ward-project.eu/

[2] VISALAK, LAGUTIN D, TARKOMA S. Lanes: an inter- domain data-oriented routing architecture[C]// Proceedings of the 2009 Workshop on Re-architecting the Internet. Rome, Italy: ACM, 2009: 55−60.

[3] JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]// Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies. Rome, Italy: ACM, 2009: 1−12.

[4] KOPONEN T, CHAWLA M, CHUN B G, et al. A data-oriented (and beyond) network architecture[C]// SIGCOMM Computer Communication Review. Kyoto, Japan: ACM, 2007: 181−192.

[5] AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. A survey of information-centric networking[J]. IEEE Communications Magazine, 2012, 50(7): 26−36.

[6] LI Zhe, SIMON G. Time-shifted tv in content centric networks: the case for cooperative in-network caching[C]// IEEE International Conference on Communications (ICC). Kyoto, Japan: IEEE, 2011: 1−6.

[7] SAINO L, PSARAS I, PAVLOU G. Hash-routing schemes for information centric networking[C]// Proceedings of the 3rd ACM SIGCOMM workshop on Information-Centric Networking. Hong Kong, China: ACM, 2013: 27−32

[8] WANG Sen, BI Jun, WU Jianping, et al. CPHR: in-network caching for information-centric networking with partitioning and hash-routing[J]. IEEE/ACM Transactions on Networking, 2016, 24(5): 2742−2755.

[9] PSARAS I, WEI K C, 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: ACM, 2012: 55−60.

[10] CHAI W K, HE D, PSARAS I, et al. Cache “less for more” in information-centric networks (extended version)[J]. Computer Communications, 2013, 36(7): 758−770.

[11] LIM S H, KO Y B, JUNG G H, et al. Inter-chunk popularity- based edge-first caching in content-centric networking[J]. IEEE Communications Letters, 2014, 18(8): 1331−1334.

[12] CHO K, LEE M, PARK K, et al. Wave: Popularity-based and collaborative in-network caching for content-oriented networks[C]// IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS).Orlando, FL, USA: IEEE, 2012: 316−321.

[13] WANG Jin, REN Jing, LU Kejie, et al. An optimal cache management framework for information-centric networks with network coding[C]// 2014 IFIP Networking Conference. Trondheim, Norway: IEEE, 2014: 1−9.

[14] WANG Jin, REN Jing, LU Kejie, et al. A minimum cost cache management framework for information centric networks with network coding[J]. Computer Networks, 2016, 110: 1−17.

[15] LLORCA J, TULINO A M, GUAN K, et al. Network-coded caching-aided multicast for efficient content delivery[C]// IEEE International Conference on Communications (ICC). Budapest, Hungary: IEEE, 2013: 3557−3562.

[16] ZHANG Guoqiang, XU Ziqu. Combing CCN with network coding: an architectural perspective[J]. Computer Networks, 2016, 94: 219−230.

[17] WU Qinghua, LI Zhenyu, XIE Gaogang. CodingCache: multipath-aware CCN cache with network coding[C]// Proceedings of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking. Hong Kong, China: ACM, 2013: 41−42.

[18] LIU Yan, YU Shunzheng. Network coding-based multisource content delivery in content centric networking[J]. Journal of Network and Computer Applications, 2016, 64: 167−175.

[19] ERIKSEN K A, SIMONSEN I, MASLOV S, et al. Modularity and extreme edges of the internet[J]. Physical Review Letters, 2003, 90(14): 148701−148704.

[20] CHAUHAN S, GIRVAN M, OTT E. Spectral properties of networks with community structure[J]. Physical Review E, 2009, 80(5): 056114−056123.

[21] WANG Yang, DI Zengru, FAN Ying. Identifying and characterizing nodes important to community structure using the spectrum of the graph[J]. PloS One, 2011, 6(11): e27418

[22] MEDINA A, LAKHINA A, MATTA I, et al. BRITE: an approach to universal topology generation[C]// Proceedings. Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Cincinnati, USA: IEEE, 2001: 346−353.

[23] MEDINA A, MATTA I, BYERS J. On the origin of power laws in Internet topologies[J]. ACM SIGCOMM Computer Communication Review, 2000, 30(2): 18−28.

[24] LAOUTARIS N, CHE Hao, STAVRAKAKIS I. The LCD interconnection of LRU caches and its analysis[J]. Performance Evaluation, 2006, 63(7): 609−634.

(编辑 伍锦花)

Social community-aware caching strategy in information-centric networking

CAI Jun1, LIU Yan1, LUO Jianzhen1, YU Shunzheng2, WU Xiaoping1

(1. School of Electronic and Information, Guangdong Polytechnic Normal University, Guangzhou 510665, China;2. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China)

In order to make content cached more reasonable in temporal and spatial distribution in information-centric networking(ICN), a social community-aware caching strategy (SCCNC) was proposed. For each community, original blocks were cached by nodes with more importance to community, and coded blocks were cached by other nodes. Thus, cache diversity and cache hit rate were enhanced without increasing cache capacity. The results show that the proposed scheme achieves better cache performance than other three schemes in terms of cache hit rate and traffic etc.

information centric networking; caching; node importance to community; network coding

10.11817/j.issn.1672-7207.2018.05.016

TN915.9

A

1672−7207(2018)05−1141−07

2017−05−19；

2017−06−29

国家自然科学基金资助项目(61571141)；国家自然科学基金-通用技术基础研究联合基金资助项目(U1636118)；广东省自然科学基金资助项目(2014A030313637)；广东省高校优秀青年教师基金资助项目(YQ2015105)；广东省应用型科技研发专项基金资助项目(2015B010131017) (Project(61571141) supported by the National Natural Science Foundation of China; Project(U1636118) supported by the National Natural Science Foundation of China−General Technical Fundamental Research Joint Foundation; Project(2014A030313637) supported by the Natural Science Foundation of Guangdong Province; Project(YQ2015105) supported by the Science Foundation for Excellent Young Teachers of Universities in Guangdong Province; Project(2015B010131017) supported by the Guangdong Provincial Application-oriented Technical Research and Development Special Fund)

刘燕，博士，讲师，从事未来网络研究；E-mail: liuyan_sysu@163.com