一种基于节点中心性近似算法的ICN协作缓存策略

罗兰花，袁淑丹，何巧萍

(1.贺州学院人工智能学院，广西 贺州 542899; 2.贺州学院公共基础教学部，广西 贺州 542899)

0 引 言

根据Cisco VNI预测，全球数字化转型将对互联网需求产生深远影响，全球互联网用户急速增长，互联网总流量在2016—2021年间将增长大约2倍，即从2016年的年均1.2 ZB(96 EB/月)增长到2021年的3.3 ZB(278 EB/月)，视频总流量占比将从2016年的73%提高到82%[1]。网络应用需求逐渐向内容获取和信息服务演进，互联网中大量视频内容的获取将对内容提供商(Content Provider, CP)(如YouTube、Bit Torrent、Netflix、百度、网易等)在数据高效传输方面带来新的挑战。为了适应互联网应用模式的转变，从根本上解决网络可扩展性、移动性支持、面向内容的安全性、数据一致性和拥塞控制等问题，研究者们提出了以信息/内容为中心(Information Centric Networking, ICN)的网络体系架构。ICN的典型代表有Named Data Networking (NDN)[2]、Publish Subscribe Internet Routing Paradigm (PSIRP/PURSUIT)[3]、Data Oriented Network Architecture (DONA)[4]、Network of Information (NetInf)[5]、Scalable & Adaptive Internet Solutions (SAIL)[6]、Named Function Networking (NFN)[7-8]。

ICN的通信原理是基于内容(Content)或数据(Data)的接收端驱动的内容路由，以识别内容取代识别终端。因此，ICN在进行路由和数据包传送时不存在位置依赖，能有效解决移动性问题。ICN呈现出一系列的缓存新特征使得已有缓存技术不能完全移植到ICN。ICN默认的缓存机制采用LCE (Leave Copy Everywhere)[9]与LRU (Least Recently Used)结合的策略，即在返回路径的每个节点均缓存数据。该算法思想简单，易于实现，由于本质上没有采用协同缓存，会导致大量缓存冗余，降低了缓存内容多样性。正因如此，如何高效利用缓存资源，优化缓存性能成为ICN网络的研究热点之一。

针对上述存在的问题，本文提出将节点中心性近似度量和节点热度相结合的ICN协作缓存策略CMAA (Centrality Metric Approximation Algorithm)，将节点热度引入最短路径近似估计，提高了节点中心性的计算效率，从而减少网络延迟。CMAA算法具有较高的命中率，同时引入缓存利用率作为缓存影响因子，避免了节点处于高频替换状态，减少同质化现象产生，从而改善缓存系统性能。

1 相关工作

缓存机制是ICN的核心技术之一。其目的是通过网络中的路由器节点缓存数据资源，使数据请求在最近的缓存副本获取相应内容，提高数据传输效率，降低网络流通量以及缓解服务器的访问压力等，从而提高网络的性能。缓存机制设计对ICN的数据分发效率具有极其重要的影响，而缓存放置策略是缓存机制设计的核心，因此，设计一个好的缓存放置策略是提高ICN缓存性能的关键内容。

目前ICN缓存研究内容主要包括2个方面：1)缓存策略的设计与实现，包括缓存的资源分配、内容缓存方式、缓存放置策略、缓存置换算法、协作缓存、缓存对象可用性和可靠性；2)缓存系统模型的建立与分析，包括缓存网络拓扑模型、兴趣分组到达模型、对象流行度模型、外生请求到达模型、请求关联性模型、缓存系统状态模型、缓存系统稳态分析等[10]。

LCE是ICN默认的缓存策略。该方法要求数据分组返回路径的所有节点均无差别地缓存数据，因此，LCE存在缓存冗余大及缓存效率较低等问题。

LCD (Leave Copy Down)[11]的基本原理是将内容缓存在其所在节点的下一跳节点，该方法存在到达边缘节点速度慢、浪费节点空间和缓存内容冗余等缺陷。MCD (Move Copy Down)[6]将缓存内容缓存至命中节点的下游节点，该方案能有效减少缓存冗余，但存在当请求者来自不同的边缘网络时，会出现缓存节点摇摆现象，从而造成更大的网络开销。

Prob[9]以固定的概率缓存对象至数据返回路径的所有路由节点。文献[12]提出了Prob的改进方法ProbCache，该算法的基本原理是使用基于加权的概率缓存机制，即缓存对象的概率与请求节点的距离成反比。该方法将数据缓存到离用户更近的缓存节点，但考虑因素单一，未实现协作缓存，可能引起边缘节点竞争，以及较易出现同质化现象。RCOne[13]在数据分组返回路径上随机地选择一个节点缓存数据。对于一条跳数为n的路径来说，该策略近似以跳数的倒数作为概率保留缓存副本。该方法易于实现，缓存冗余度低，但是没有使用内容请求的分布等信息。

文献[14]提出基于介数中心性的CLFM (Cache “Less for More”)策略，该策略通过网络拓扑图计算转发路径上各节点的介数中心性值，选取介数中心性值最大的节点作为缓存节点。CLFM策略没有考虑到内容替换频率及同质化现象，可能导致部分缓存请求无法实现。

为了获取更好的缓存系统性能，合理利用节点中心性，协同缓存机制是行之有效的改进思路。通过协同机制的使用，其目的是让用户更快地获取到所需内容，同时减少同质化现象的产生，充分利用节点缓存空间。

2 节点中心性度量基本原理

对于复杂网络而言，节点中心性反映了节点的价值和所需的信息处理能力。中心性是复杂网络分析的核心内容之一，然而，根据节点中心性的定义，要准确计算中心性的工作量非常大，关键部分是计算最短路径长度。因此，选择快速有效的最短路径近似算法非常必要。本章将对节点中心性的3个度量及平均最短路径近似算法进行分析。

2.1 度中心性

针对网络连通图G(V,E)(|V|=n,|E|=m)，其中V={v1,v2,…,vn}表示G的顶点集合，E={e1,e2,…,em}表示G的边集合，图G的邻接矩阵Ann=(aij)n×n，当vi和vj有相连边时，则aij=1，否则，aij=0。

度中心性(Degree Centrality)是网络分析中最常用的刻画节点中心性(Centrality)的度量指标。度中心性通过统计直接相邻边数描述网络中心性，一个节点的度越大，则越趋于网络中心。其计算公式为：

(1)

其中，CD(vi)表示节点vi的度中心性。为消除网络规模对度中心性的影响，可通过除以最大可能的连接数n-1进行归一化处理，因此，度中心性的取值范围为CD(vi)∈[0,1]。

2.2 紧密中心性

紧密中心性(Closeness Centrality)用于描述网络中某一节点与其他节点之间的紧密程度。紧密中心性定义为从某一节点出发到其它所有节点的最短路径长度总和的倒数。其计算公式为：

(2)

其中，CC(vi)表示节点vi的紧密中心性，dG(vi,vj)表示G中节点vi到节点vj的最短路径长度。公式(2)仅适用于G为连通图的情况，而现实网络可能存在多个连通块，则会出现dG(vi,vj)=∞的情况，导致无法有效计算图G的紧密中心性。为此，本文使用指数函数对公式(2)做归一化处理，节点vi的紧密中心性计算表达式为：

(3)

2.3 介数中心性

介数中心性(Betweenness Centrality)描述一个节点出现在其他2个节点之间最短路径的概率，用于评价该节点在整个网络传播数据的重要性。节点的介数值越大则表示在该网络中的重要性越高。其计算公式为：

(4)

其中，CB(vi)表示节点vi的介数中心性，σs,t(vi)表示(s,t)节点之间经过vi的最短路径数，σs,t表示(s,t)节点之间所有最短路径数。

综上可知，上述3个中心性度量均能从一定的角度衡量节点的重要程度，但是不同的中心性度量均存在一些不足和局限性，使用不同的方法对相同的网络进行度量其结果不尽相同，为此，有研究者提出将3个中心性度量融合作为度量标准。文献[15]将度中心性、紧密中心性和介数中心性作为TOPSIS多属性决策模型的输入，该算法有效地解决了3个中心性度量各自存在的局限性。文献[16]中采用更为简单的方法，将3个节点中心性度量进行加权融合作为节点重要度的度量，能够有效折中3个中心性的差异，根据融合后的度量值作为缓存节点选择的标准。本文采用文献[16]简单加权叠加的方法，计算节点中心性的度量值作为评估标准。

2.4 最短路径近似算法

文献[16]提出的将3个节点中心性度量进行加权融合的方法确实能有效地折中3个中心性的差异，但其计算量仍然非常大，这是因为紧密中心性和介数中心性的计算均基于最短路径的识别和路径长度的计算。而精确计算最短路径工作量极大，为此，本文采用文献[17]提出的基于界标节点的最短路径近似估计，该方法能快速有效地估计出最短路径长度。

根据图论中最短路径长度的定义，最短路径长度估计可以分为跳数估计和物理距离估计2类，本文采用最短跳数估计作为最短路径长度。

针对复杂网络连通图G(V,E)(|V|=n,|E|=m)，设π(s,t)={s,u1,u2,…,ur,t}表示节点s与t之间路由长度为r的路径，d(s,t)表示G中任意2个节点的最短路径长度，SP(s,t)表示节点s和t所有长度为d(s,t)的最短路径集合。在网络G中选取l个界标点(Landmark)LM={u1,u2,…,ul}，则任意节点v∈V到界标点的最短路径的集合可以表示为：

∅(v)={d(v,u1),d(v,u2),…,d(v,ul)}

定理1在G中任取3个节点s,u,t∈V，d(s,t)表示节点s和t的最短路径长度，根据三角不等式，则有：

d(s,t)≤d(s,u)+d(u,t)

d(s,t)≥|d(s,u)-d(u,t)|

推论1若存在路径π(s,t)∈SP(s,t)且u∈π(s,t)，则：

d(s,t)=d(s,u)+d(u,t)

推论2若存在路径π(s,t)∈SP(s,t)且s∈π(s,u)，或π(s,u)∈SP(s,u)且t∈π(s,u)，则：

d(s,t)=|d(s,u)-s(u,t)|

假定已经得到界标点LM={u1,u2,…,ul}与网络中所有节点的最短路径，根据三角不等式可得：

其中，si表示节点s与第i个界标点的距离。

3 基于中心性度量近似算法的缓存策略CMAA

3.1 CMAA工作原理

为了充分体现节点中心性和节点热度对缓存性能的影响，本文设计一种基于节点中心性近似算法的缓存策略，记为CMAA缓存策略。该策略根据节点的中心性近似度量、节点热度和缓存利用率计算转发路径上各节点的缓存优先级，基本过程为先将节点缓存优先级由高到低排序，然后按照缓存优先级选择若干节点作为缓存节点。本策略引入最短路径近似算法，降低了节点中心性度量的计算复杂度，同时将节点中心性、节点热度和节点缓存利用率三者结合计算得到节点的缓存优先级，避免了节点处于高频替换状态，减少同质化现象产生，同时获得较高的缓存命中率，提高了缓存系统性能。

CMAA缓存策略：假定兴趣包转发路径上共经过K个路由器节点，各节点的中心性度量总值为S(vi)，节点的缓存空间利用率为R(vi)，节点热度值为H(vi)，节点的缓存优先级为P(vi)，其计算公式为：

(5)

其中，路由器节点的中心性度量值S(vi)由度中心性、紧密中心性和介数中心性经过归一化处理后再按所占权重分别为α、β和γ构成，其计算公式为：

S(vi)=αCD(vi)+βCC(vi)+γCB(vi)

(6)

3.2 CMAA的算法实现

CMAA缓存策略首先获得全局网络拓扑G′、各路由器节点的缓存空间利用率为R(vi)和节点热度值为H(vi)，然后分别根据式(1)、式(3)和式(4)计算得到各路由器节点的CD(vi)、CC(vi)和CB(vi)，依据不同需求确定所占权重分别为α、β和γ，并根据式(6)计算得出兴趣包转发路径上各路由器节点的中心性度量总值S(vi)，再依据节点中心性值S(vi)、节点缓存空间利用率R(vi)和节点热度值H(vi)通过式(5)计算得到各路由器节点的优先级P(vi)，最后对路径上各路由器节点优先级排序，并按优先级高低选出k个节点作为缓存节点并进行内容缓存。

当缓存空间不足时，需要将缓存内容置换为新的内容，目前ICN中常用的缓存置换算法有LRU (Least Recently Used)和LFU (Least Frequently Used)。本文采用LFU算法，LFU基本原理是根据数据的访问频率将数据依次记录在缓存中，频率最高的数据保留在缓存的最顶端，反之，频率最低的数据放置于缓存最底端，当缓存空间不足时将最低端的数据替换为新内容。其实质是以“最近经常访问”的特性来预测数据将来被访问的可能性。

CMAA缓存策略的伪代码如算法1所示。

算法1CMAA缓存算法。

输入：全局网络拓扑结构G′；缓存空间利用率R={R(v1),R(v2),…,R(vn)}；节点热度值H={H(v1),H(v2),…,H(vn)}。

输出：缓存节点集CacheList()。

1) for (i=1;i≤n;i++)

2) for (j=1;j≤n;j++)

4) for (i=1;i≤n;i++) {

8)S(vi)←αCD(vi)+βCC(vi)+γCB(vi); //vi的中心性度量值 }

9) for (i=1;i≤n;i++)

11)P′(vj)←sort(P(vj)); //vi的缓存优先级排序

12) for (j=1;j≤k;j++)

13)CacheList()←vj; //记录优先级高的前k个路由器节点

14)Return CacheList();

4 仿真实验

4.1 性能参数

本文实验考虑缓存系统3个关键性能指标：缓存命中率(Cache Hit Ratio, CHR)、平均接入代价(Average Access Cost, AAC)和平均请求时延(Average Request Delay, ARD)。其中，缓存命中率为某节点命中的请求数与其接收的请求数的比值；平均接入代价为用户请求到达内容节点的平均最短跳数；平均请求时延为用户发出请求到返回内容的平均时延。

4.2 实验环境及参数设置

实验环境。实验平台软件环境基于Ubuntu12.04操作系统，使用NDNSim[18]模拟器进行仿真实验，采用Matlab7.0作为数据分析工具；硬件环境为：CPU Intel(R) Core(TM) 3.40 GHz，内存6.00 GB，硬盘480 GB。

实验参数。随机生成节点和网络拓扑，节点数取值范围为[100,300]，其默认值为100；总内容数量为1000个，假定每个内容为单一数据块。用户的请求分布服从Zipf-Mandelbrot分布[19]，且用户的请求到达符合泊松分布。用户数量100个，节点缓存容量C指节点缓存内容的最大数量，C的取值范围为[10,100]，其默认值为10，取缓存节点数k为节点数的1%。

4.3 仿真结果分析

本文以LCE和CLFM作为对照实验，采用LFU缓存置换算法，中心性度量值S(vi)的计算式中的权重α、β和γ均取为1/3，即均衡看待各中心性值对网络中心性的影响，以检验CMAA缓存策略的有效性。

4.3.1 节点缓存容量的影响

为衡量节点缓存容量对实验的影响，考虑对缓存容量取不同值。当节点缓存容量取不同值时，LCE、CLFM和CMAA的缓存命中率如图1所示。由图1可以看出，3种策略的缓存命中率均随节点缓存容量的增加而增大。其中，CMAA的缓存命中率最高，比LCE提升约25.8%，比CLFM提升约7.2%。

图1 缓存容量对缓存命中率的影响

图2 缓存容量对平均接入代价的影响

平均接入代价随节点缓存容量的变化如图2所示。由图2可知，3种策略的平均接入代价均随节点容量的增加而减少，这是因为缓存容量的增加使得节点缓存内容多样性，增加就近获得内容的概率。

平均请求时延随节点缓存容量的变化如图3所示。由图3可知，3种策略的平均请求时延均随节点缓存容量的增加逐渐减少，这是因为缓存容量的增加提高了获取请求内容的概率。此外，CMAA平均请求时延略微高于LCE和CLFM，这是因为CMAA在计算节点缓存优先级时增加了计算量，从而增加了网络平均时延。

图3 缓存容量对平均请求时延的影响

4.3.2 用户请求数的影响

考虑用户请求数对实验的影响。当用户请求数取不同值时，LCE、CLFM和CMAA的缓存命中率如图4所示。由图4可知，3种策略的缓存命中率无明显变化。

图4 用户请求数对缓存命中率的影响

平均接入代价随用户请求数的变化如图5所示。由图5可知，3种策略的平均接入代价无明显变化。

图5 用户请求数对平均接入代价的影响

平均请求时延随用户请求数的变化如图6所示。由图6可知，3种策略的平均请求时延均随用户请求数目的增加而增大。

图6 用户请求数对平均请求时延的影响

通过实验可以看出，当节点缓存容量和用户请求数变化时，CMAA在缓存命中率、平均接入代价2个性能指标上均优于LCE和CLFM，平均请求时延略微高于LCE和CLFM。CMAA使用缓存利用率作为缓存影响因子，有效地利用了缓存空间。相对于缓存机制LCE和CLFM，CMAA具有更高的缓存性能，具有一定的实际意义。

5 结束语

本文提出了一种基于节点中心性近似算法的协作缓存策略CMAA。CMAA利用最短路径近似估计提高节点中心性的计算效率，将节点中心性近似度量加权融合值、节点热度和缓存利用率三者作为缓存影响因子，计算得出兴趣包转发路径各节点的缓存优先级。在计算量略微增加的前提下，在缓存命中率与平均请求跳数方面，该策略的性能均优于LCE和CLFM策略，在平均请求时延方面CMAA的时延也只是略长一些。下一步将在本文的研究基础上，结合ICN网络数据需求的多样性[20-21]，分析当前边缘缓存策略存在的关键问题，研究结合用户数据需求的边缘缓存策略[22]，进一步优化网络缓存性能。