一种命名数据网络的缓存策略

秦鲁法，徐雅斌

(网络文化与数字传播北京市重点实验室，北京100101) (北京信息科技大学 计算机学院，北京100101)

1 引 言

传统的互联网体系结构面向的主要需求是分布在各地的主机之间的数据传输，但当今互联网面向的主要需求是信息获取，用户每天大量获取的内容包括:社交网络分享的最新信息，电商提供的琳琅满目的商品，视频网站发布的吸引眼球的短视频、影视剧等.前者的应用模式可以形象的称之为“推数据”，后者的应用模式可形象的比喻为“拉内容”.由此可见，当今的互联网服务方式与最初的互联网应用需求和设计目标已大相径庭，IP地址紧张已经不是突出的问题，而网络带宽不足、服务质量不高、安全问题频出则成为当下的主要矛盾.

为了从根本上解决这些问题，一种以内容为中心的网络体系结构- ICN(Information-Centric Networking)脱颖而出，该类网络体系结构的主流实现代表就是命名数据网络(Named Data Networking，NDN[1]).NDN的关键特性之一在于，内容请求并非一定需要到内容提供结点去获取，完全可以通过命中沿途路由结点缓存中之前缓存的请求内容而得到快速响应.这种缓存策略对于提升NDN的传输效率至关重要.

目前，NDN默认的缓存策略是LCE(Leave Copy Everywhere)[2]策略，即在数据返回给请求者时，在沿途各个节点上都要进行缓存.但是这种对内容不加区分的缓存策略，导致NDN的缓存替换率较高，并且存在大量的缓存内容冗余，最终导致缓存内容的利用率低下.因此，有部分研究人员对此开展研究，并提出了一些行之有效的方法.

目前，针对NDN的改进缓存策略主要有两类:协作式缓存策略和非协作式缓存策略.协作式缓存策略指的是节点间通过不断交换节点自身的缓存信息做出缓存决定.它从全局角度出发，相互协作，因此可以很好地利用网络资源，减少网络内部信息冗余.但是方法比较复杂，效率低下，而且大幅增加了NDN的网络信息传输量，因而实现效果不够理想;而非协作式缓存策略，只依据节点自身信息独立地做出缓存决定，因此非协作式缓存策略相对简单、效率高，不需要控制平面对内容的请求做出决策，但缺乏全局性考虑，优化效果有限[3].

有关协作式缓存策略的代表文献及采用的方法如下:文献[4]提出了一种根据节点位置重要性、兴趣源距离以及内容时效性计算缓存节点位置的协作式缓存机制.文献[5]通过在节点之间交换内容流行度分布，然后权衡节点位置，将数据缓存在最有利于客户端的节点上.文献[6]通过内容实时流行度、节点紧密度，并通过构建节点之间的直接影响力定义综合属性指标，实现了更加均匀的内容分布.文献[7]提出了一种基于区域划分和哈希环的协作式缓存策略.

有关非协作式缓存策略的代表文献及采用的方法如下:文献[8]提出了LCD(Leave Copy Down)策略，该策略在缓存命中时，将数据缓存在下游节点，使流行数据逐渐靠近用户.文献[9]提出了基于节点介数和缓存替换率的缓存策略，该种策略将数据缓存在内容替换率低并且比较关键的节点上.文献[10]提出了一种节点主观视角下结合内容流行度和节点对不同内容类型偏好的缓存策略.文献[11]提出了一种基于区域划分的思想，在网络边缘采用基于热度的确定性缓存策略，在网络核心采用基于缓存收益和内容热度的概率性缓存策略.文献[12]提出了一种综合考虑内容动态流行度、缓存代价以及最近请求的时间，进而设计内容价值函数的缓存替换方案.文献[13]提出了一种综合考虑内容热度和缓存放置收益的方法，内容热度越高、放置收益越大的内容被缓存的概率越高.

经过综合分析，本文倾向于非协作式缓存策略.提出了一种基于缓存价值的缓存策略(Leave Cache Value，LCV).除了将内容流行度、兴趣源距离作为缓存决策的指标外，还将内容大小及多样性也作为优化缓存空间的指标，这些因素综合到一起充分体现了缓存的价值.由此，可以通过构建的缓存价值决策模型实现内容缓存.

本文的突出贡献如下:

1)本文首次提出将缓存价值作为缓存内容置换策略的考量指标，以尽可能的提高缓存的命中率，进而提高NDN中节点缓存内容的复用程度;

2)设计了NDN节点的缓存自维护策略，运用统计学规律，定期将缓存价值较小的内容从内容存储区(Content Store，CS)中删除，为后续到来的数据预留必要的缓存空间，以减少内容置换的时间.

2 缓存策略相关因素

2.1 内容流行度

分析发现，当网络中有大量用户请求数据时，实际上只有少数内容会被绝大多数用户频繁访问，大部分内容很少被访问.即，网络流量符合Zipf定律，20%的内容被80%的请求访问，其余80%的内容只被20%的请求访问.因此，在节点上缓存流行度大的内容可以极大的提高缓存的利用效率.

本文通过在节点内部周期性的统计不同内容的请求次数，并结合上一时刻内容的流行度，计算当前时刻不同内容的流行度.在t时刻，内容流行度pr(t)的计算方法如下：

pr(t)=α*pr(t-1)+(1-α)*hr(t)

(1)

hr(t)=Nr(t)/Nq(t)

(2)

其中，hr(t)表示在当前节点中某个内容在当前周期内的命中率，Nr(t)表示在当前节点中当前周期内被请求的次数，Nq(t)表示在当前节点中当前周期内路由节点收到的总请求数.α是衰减因子，表示上一时刻流行度在当前周期所占的比例.

上述递推公式，不仅考虑了上一时刻的热度对当前热度的影响，更加突出了最新的网络流量的热度.

2.2 兴趣源距离

在NDN中，当用户请求数据时，会发送兴趣(Interest)包.兴趣包在离用户越近的节点命中，数据请求时延就会越低.

因此，本文采用从缓存节点获取数据所需的跳数与从数据源获取数据所需的跳数的差值进行考量.跳数信息可以通过兴趣包和数据包中的HopCount字段获取.兴趣源距离越大，节省的跳数越多.也就说明，请求命中的节点离用户越近.内容c在节点i上的兴趣源距离b(i，c)的计算方法为:

b(i，c)=hs(i，c)-hc(i，c)

(3)

其中，hs(i，c)表示请求者从数据源处获取数据需要的跳数，hc(i，c)表示从节点i获取数据需要的跳数.

然而，在不同路径之间，兴趣源距离可比性较弱.在兴趣源距离相同的条件下，数据请求者距离数据源越远，相对收益越小.因此，本文利用相对兴趣源距离作为缓存决策的一项指标.相对兴趣源距离r(i，c)为:

r(i，c)=b(i，c)/hs(i，c)

(4)

2.3 内容大小及多样性

在NDN中，每个节点CS的容量总是有限的.一般来说，在充分考虑以上两个因素以外，CS中存储的内容越多、形式越丰富，后续数据请求被满足的概率也越大.

对于内容的大小可以直接获取.而对于内容的多样性，一般来说，CS中缓存的内容越丰富，内容名称就越多样，信息量就越多.因此，可以通过计算CS中缓存内容名称的信息熵来判断CS中存储内容的多样性.信息熵的计算可采用公式(5)进行计算.

(5)

其中，n指的是NDN节点中不同内容的数量，也即不同内容名称的个数;p(xi)表示节点内每个内容名称的长度占所有内容名称长度的比例.

当需要缓存较大的数据时，节点需要将较多数据删除，以腾出必要的缓存空间，此时节点缓存内容名称的信息熵就会减小;当节点缓存了多个小的数据时，节点缓存内容名称的信息熵就会增大.为了量化信息熵的变化情况，本文定义了信息熵增益的概念，计算方法如公式(6).

ΔE=E1(X)-E2(X)

(6)

其中E1(X)表示缓存某个内容后节点的信息熵，E2(X)表示缓存某个内容前节点的信息熵.

3 缓存决策模型

本文提出的缓存策略综合考虑内容大小、内容流行度、相对兴趣源距离以及内容多样性计算缓存价值，通过缓存价值进行缓存决策和缓存的定时更新.

在t时刻，在节点i的内容存储区中，内容c的缓存价值V(t，i，c)为：

(7)

其中，S是指内容c所占空间的大小，Vi指节点i总缓存空间大小.随着内容c的不断增加，缓存价值将会迅速减小.α，β，γ分别为内容流行度pr(t)，相对兴趣源距离r(i，c)和信息熵增益ΔE的权重，并且α+β+γ=1.

各属性的权重确定是个难题.仅凭主观经验确定缺少科学性与准确性;通过实验测定是一种可选的方法，但是需要有足够的数据支撑，而且取决于特定的实验环境和网络拓扑图，具有一定的局限性;层次分析法(AHP) 是由专业人员通过重要性对比来确定属性的相对权重，是一种可取的方法，而且具有广泛的适用性.为此本文选择层次分析法(AHP)确定每个属性的权重.

首先根据不同属性之间的重要程度，得出层次判别矩阵如表1所示，通过一致性检验得到各个属性权重如表2所示.

表1 层次判别矩阵Table 1 Hierarchical discriminant matrix

表2 权重值Table 2 Weight Values

4 缓存更新策略

当节点CS已满时，每个内容请求都要通过计算缓存价值才能删除数据.当内容请求较多时，会造成节点的计算压力较大.为此，笔者通过运用统计学规律，设计了如下缓存定时更新策略，提前删除缓存价值较小的内容.

设内容存储区中每一个缓存内容的缓存价值分别为x1，x2，…，xn，则缓存价值的平均值为:

μ=(x1+x2+，…，+xn)/n

(8)

残差为:

gi=xi-μ

(9)

标准差为:

(10)

根据拉依达准则(Pauta Criterion，PC)可知，数值分布在(μ-σ，μ+σ)中的概率为0.6827，数值分布在(μ-2σ，μ+2σ)中的概率为0.9544.由此可以看出，内容存储区中缓存价值绝大部分集中在(μ-2σ，μ+2σ)区间内，区间之外的数据仅占4.56%.因此，当内容存储区中剩余缓存容量不足或已满时，可以提前删除缓存价值小于μ-2σ的数据，从而为即将到来的数据提供必要的缓存空间.

5 实 验

5.1 实验环境与实验参数

本文所有实验均在网络仿真软件ndnSIM[14]中进行.实验环境如下:操作系统为Ubuntu16.04 LTS，内存为8GB，CPU型号为i5-8300H@2.3GHz，ndnSIM版本为2.6.实验采用如图1所示的树状拓扑结构.树的高度为4，共15个节点.根节点为源服务器，8个叶子节点为用户，其余6个节点为路由节点.

图1 实验拓扑图Fig.1 Experimental topology

网络中数据块总数为10000个chunk，不同内容的数据大小为1-10个chunk.实验时间为100s.其它实验参数见表3.

表3 实验参数Table 3 Experiment parameters

5.2 缓存命中率对比实验

缓存命中率是评价缓存策略好坏的一个重要指标.为此，本文将经典的LCE策略、改进的LCD策略以及本文提出的LCV策略的缓存命中率进行了对比，对比实验结果如图2所示.

图2 缓存命中率对比图Fig.2 Cache hit ratio comparison graph

从图2可以看出，本文提出的LCV策略的缓存命中率在3种策略中是最高的.在实验初始阶段，节点中缓存数据较少，因此3种策略的命中率均较低.但随着时间的推进，LCV策略相较于LCD策略缓存命中率平均提高了19.5%;LCV策略相较于LCE策略，缓存命中率平均提高了24.7%.

尽管用户对内容的请求模式是总体服从Zipf-Mandelbrot分布的[15]，但是服从Zipf 分布的情况不尽相同.Zipf参数(α)越小，用户请求内容的随机性越大;Zipf参数(α)越大，用户请求内容的集中性越高.不同的缓存策略对Zipf分布的参数，来研究请求模式对于缓存策略的影响.值得注意的是，因此，本文测试了Zipf 参数(α)在0.7到1.2的变化范围内，LCE策略、LCD策略和本文提出的LCV策略的缓存命中率.实验结果如图3所示.

图3 Zipf参数对命中率的影响Fig.3 Impact of Zipf-parameter on hit ratio

由图3可以看出，随着α的增大，热点内容越来越集中，3种策略的命中率都在增加.但是，本文提出的LCV策略的命中率比其他两种策略的命中率都高.在不同的Zipf(α)参数条件下，LCV策略相对于LCD策略命中率提升为3.6%-19.5%，相对于LCE策略命中率提升为10.3%-24.7%.

5.3 平均访问时延对比实验

访问时延与用户的上网体验直接相关.访问时延越低，用户上网体验越好.因此，本节测试了LCE策略、LCD策略以及本文提出的LCV策略的平均访问时延，实验结果如图4所示.

图4 平均访问时延对比图Fig.4 Average access delay comparison graph

从图4可以看出，随着网络请求的增多，3种策略的平均访问时延都在下降，但LCV策略平均访问时延最低.本文提出的LCV缓存策略比LCD策略平均访问延迟降低了4.3%，比LCE策略的平均访问时延降低了5.6%.

5.4 平均路由跳数对比实验

平均路由跳数指的是所有用户请求从发出到请求被满足所经过路由节点个数的均值.平均路由跳数越少，响应时间就会越短，进而说明缓存策略越好.为此，本文测试了LCE策略、LCD策略以及本文提出的LCV策略的平均路由跳数，实验结果如图5所示.

图5 平均路由跳数对比图Fig.5 Average route hops comparison graph

从图5可以看出，在实验开始阶段，由于节点中缓存数据较少，因此3种缓存策略的平均路由跳数差别较小.随着实验的进行，用户访问请求的增多，缓存策略逐渐发挥作用，因此平均路由跳数逐渐下降.而LCE策略由于没有进行任何优化，导致平均路由跳数下降的最慢.而本文所提出的LCV策略，由于倾向于将热点内容放置在距离用户较近的节点上，并且保证节点缓存内容的多样性，因此，LCV策略的平均路由跳数最少.相比较而言，LCV策略比LCD策略的平均路由跳数降低了4.4%，比LCE策略降低了5.2%.

6 结 语

为了提高NDN缓存的利用率，本文提出了一种基于缓存价值的非协作式缓存策略.路由节点可根据内容流行度、相对兴趣源距离、内容大小和多样性计算缓存价值，并依此进行缓存决策.由于在保证缓存内容的流行度和相对兴趣源距离以外，还充分考虑了节点缓存内容的大小、缓存内容的多样性，从而使得热点内容被优先缓存在缓存价值最大的节点，可以实现NDN缓存内容的有效复用.对比实验结果表明，本文所提出的LCV策略相较于传统的LCE策略和LCD策略，在缓存命中率、平均路由跳数和平均访问时延等方面均具有明显的优势.