DOI: 10.11817/j.issn.1672-7207.2018.05.016

社团感知的ICN缓存策略

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

(1. 广东技术师范学院 电子与信息学院，广东 广州，510665；

2. 中山大学 数据科学与计算机学院，广东 广州，510006)

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

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

中图分类号：TN915.9        文献标志码：A         文章编号：1672-7207(2018)05-1141-07

Social community-aware caching strategy in information-centric networking

CAI Jun¹, LIU Yan¹, LUO Jianzhen¹, YU Shunzheng², WU Xiaoping¹

(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)

Abstract: 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.

Key words: information centric networking; caching; node importance to community; network coding

随着新应用的不断涌现，流量产生和传输的方式也将发生根本性变换，其中大部分流量来源于用户驱动的内容获取类应用，这使得当前基于端到端通信的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  节点社团重要度定义

本文基于节点局部重要度即节点社团重要度确定ICN网络中内容的缓存位置。CHAUHAN等^[20]的研究表明，网络邻接矩阵的特征谱能清楚地反映网络中社团的数目，例如由c个社团组成的网络，则该网络的邻接矩阵将有c个特征值远大于其他特征值，这些特征值可以作为量化网络社团结构的重要指标。因而，网络社团强度定义为，其中λ₁，λ₂，…，λ_c表示邻接矩阵特征值中按降序排列的前c个特征值。当节点k离开网络时，整个网络的社团结构和邻接矩阵特征值都将随之变化，即。所以，节点k对网络社团特性的重要度为。利用摄动理论可得节点社团重要度的近似解^[21]P_k：

              (1)

其中：c为网络中社团数目，v_i表示以网络中的路由器为节点，路由器之间的物理链路为边构建的邻接矩阵的第i个特征向量，v_ik表示特征向量v_i中的第k个元素。P_k越大，节点k在其所属的社团中越重要，即社团内外的其他节点访问该节点将越容易。对于n个节点，c个社团的网络，有。为使测量参数的和为1，定义，满足。在应用I之前，需预先知道网络中社团数目c。本文作者利用网络的频谱特性直接确定网络社团数目。若c给定，则该方法无需对网络进行社团划分，避免了复杂的社团划分的计算量，可以直接描述节点对社团的重要度。由式(1)可知：要计算每个节点的社团重要度，只需求出表示网络节点连接关系的邻接矩阵的所有特征值和特征向量。而现实中的大部分网络为稀疏网络，利用Lanczos算法和QL算法，求稀疏对称矩阵的所有特征值和特征向量的时间复杂度为O(nm)，其中n和m分别表示网络的节点数和边数，计算量比较小，适合于实际应用。

1.2  Interest包和Data包转发机制

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

图1  SCCNC示例

Fig. 1  An example of SCCNC

表1所示为扩展的PIT表。

表1  扩展的PIT表

Table 1  Table of extended PIT

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

i_max, I_(i-1)max>

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

算法1  Interest转发过程

Initialize I_i=0;

for

each node N_j receiving Interest from face k do

if

cache hit then

send Data D_p(I_i);

else

if

PIT exists then

add face k into face list;

if

node N_j is the FirstNode then

add I_i into I_(i-1)max, let I_imax=0;

else

add I_i into I_imax;

end if

else

if

I_j＞I_i then

let I_i=I_j;

end if

end if

establish a new PIT entry for Interest, let I_imax=I_i, I_(i-1)max=0;

forward Interest to next hop;

end if

end for

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

算法2  Data转发过程

When an Data (I_imax) arrived

for

each node N_j do

cache Data according to Algorithm 3;

check PIT table;

for

each face k in face list of PIT table do

if

I_ik≠0 then

I_imax=max{I_imax, I_ik};

else

I_imax=I_(i-1)max;

end if

send Data out of face k;

end for

end for

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

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

算法3  SCCNC缓存策略

When an Data (I_imax) arrived

if  Data is an original block then

if 

I_j=I_imax then

cache original block into ContentStore;

else

if

cache exist then

encoded original block with other coded blocks in ContentStore;

end if

end if

end if

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

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

假设社团i的节点N_j的节点社团重要度为I_ij，社团i内的平均节点重要度为。当缓存耗尽时，首先利用最近最少使用(LRU)算法对缓存内容进行排序，构建缓存序列。第k个内容被移除的概率为

              (2)

式中：为归一化因子，为概率调节系数。满足如下条件：

              (3)

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

2  仿真实验与分析

仿真实验中的网络拓扑来自BRITE拓扑生成器^[22-23]，网络包含100节点，平均节点度为4，链路带宽为1 Gb/s。使用BRITE生成多种网络拓扑，进行多次仿真实验，得到相似的仿真结果。网络采用Dijkstra算法作为路由机制。将4 000个大小为1 Gb的内容随机存储在10个内容服务器上，每个内容被分成100个内容块，其中10个内容块为一代。采用代内随机线性网络编码，编解码过程只发生在属于同一代的内容块之间。内容流行度服从Zipf分布，其中[0.7, 1.0, 1.5, 2.0]。用户对内容的请求过程服从泊松分布。将SCCNC与以NC-CCN^[16]，CodingCache (CC)^[17]和Leave Copy Down (LCD)^[24]这3种机制的性能进行对比。

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

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

3) 服务器命中减少率，。若对内容块i的请求是由缓存响应的，则，否则。N(t)为在时间区间内用户收到的内容块总量。

4) 下载跳数减少率，。其中：为内容块i从缓存命中节点到请求者实际经历的跳数，为内容块i从内容服务器到请求者的跳数。若对内容块i的请求是由内容服务器响应的，则。

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

图2所示为4种缓存方案在不同参数下平均下载时间的对比。由图2可知：4种机制的平均下载时间随Zipf参数的增加而减少(见图2(a))。这是因为Zipf参数越大，用户的偏好越集中，用户发送的请求集中在一小部分内容上，使得这部分内容在网络中的缓存越来越多，越来越靠近用户。同理，用户的请求越多，网络中的缓存内容也就越多，所以，4种机制的平均下载时间随用户请求数量的增加而降低(见图2(b))。从图2还可以看出：SCCNC机制一直保持着明显优势，这种优势在较小的Zipf参数和较少的用户请求的情况下尤为明显。这是因为在SCCNC中，原始块缓存在节点社团重要度高的节点上，这些节点更容易被其他节点访问。

图3~5所示分别为4种缓存方案的缓冲命中率、服务器减少命中率和传输流量对比。在SCCNC中，节点社团重要度低的节点缓存编码块，1个编码块可以当做多个内容块，用来响应来自不同用户对不同内容块的请求。例如，编码块cb()能同时满足不同用户对A和B内容块的请求。因此，SCCNC能实现更高的缓存命中率(见图3)、更低的服务器负载减少率(见图4)以及更低的传输流量(见图5)。

图2  4种缓存方案平均下载时间对比

Fig. 2  Comparison of average download time for four different caching schemes

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

图3  4种缓存方案缓存命中率对比

Fig. 3  Comparison of cache hit ratios of four different schemes

图4 4种缓存方案服务器命中减少率对比

Fig. 4  Comparison of server hit reduction ratios of four different schemes

图5  4种缓存方案传输流量对比

Fig. 5  Comparison of traffic of four different schemes

图6 4种缓存方案跳数减少率对比

Fig. 6  Comparison of instantaneous hop reduction ratios of four different schemes

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.

(编辑  伍锦花)

收稿日期：2017-05-19；修回日期：2017-06-29

基金项目(Foundation item)：国家自然科学基金资助项目(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