命名数据网络中基于熵的概率缓存替换策略

高全力，李庆敏，高 岭，王西汉，胡发丽

(1.西安工程大学 计算机科学学院，陕西 西安 710048；2.西安工程大学 新型网络智能信息服务国家地方联合工程中心，陕西 西安 710048)

0 引 言

目前，互联网仍以TCP/IP协议栈为基础模型，在数据交换时是以找到数据所在的设备为前提映射到设备中；对在网络中可能进行多次传播的竞争性重复数据，需要分别建立连接来完成。这种方式过度依赖中心服务器的计算能力以及带宽资源，会造成传输拥塞和网络瘫痪的问题。为解决TCP/IP结构存在的问题，信息中心化(ICN)作为新一代互联网被提出。ICN的网络范式和架构不同于基于TCP/IP的网络。目前，ICN得到广泛研究和推广，而命名数据网络(NDN)是ICN的方案之一。NDN改进的是地址命名系统和路由器缓存功能。这种设计使得客户端能快速获取请求的内容，有效地减少网络带宽浪费，减轻源服务器端的响应负担，从而提高网络的顺畅度[1]。

NDN利用内容存储提供缓存功能，而其缓存机制受替换策略严格控制，因此高效的替换策略是NDN发展的决定性因素之一。为了提高替换的效率，许多学者进行了有关NDN缓存替换策略的研究：最近最少使用算法(LRU)[2]对最近最少使用的缓存内容进行替换；最少使用算法(LFU)[3]经对比后替换使用频率低的内容；先进先出算法(FIFO)替换最先缓存的内容；文献[4]提出淘汰请求代价小的内容；文献[5]则提出淘汰动态流行度小的内容。但是，LRU、LFU、FIFO等算法只考虑单一因素，无法区分内容的请求频率是高还是低，存在流行内容被非流行内容驱逐的问题。

一些研究提出了综合计算内容流行度的缓存替换算法：BERNARDINI等提出由不同用户提供的数据包应该进行区分[6]；FAN等提出利用影响整体缓存增益的因素将内容对象从内容文件细化到内容块，并实现了对内容块的存放和替换[7]；文献[8]提出了一种基于深度学习的替换策略。但是以上算法的计算量较大，而NDN路由器的缓存容量低，计算资源有限，使得实际工作时造成大量网络资源的浪费。

本文面向NDN网络的缓存替换策略展开研究，结合在软件定义网络(SDN)中根据多属性值作决策，从而降低网络时延的情况[9]，并综合考虑了数据包大小、内容流行度和请求代价，提出一种基于熵的概率缓存替换策略(EPR)。在该策略中，路由节点统计所有缓存数据包的大小、内容流行度和请求代价字段的值并进行熵权重值的计算，然后在需要缓存替换时选择熵权重值最小的数据包进行替换。该策略不仅计算量小且综合考虑了多项影响因素。实验结果显示，相较于NDN网络中现有的替换策略，EPR策略在平均缓存命中率和平均请求时延方面有较大的改善。

1 数据结构及替换策略

1.1 NDN节点组成与数据结构

在当前的NDN网络体系架构中，包括客户端(client)、源服务器(origin server)和路由器(router)等3个模块，其传输内容主要包括兴趣包(interest packet)和数据包(data packet)等2类。客户端请求数据时，首先向网络中发送兴趣包[10]。在请求的发送过程中，如果遇到某个节点中恰有可以满足请求的数据，就会响应一个数据包，将响应的数据返回客户端;否则,将转发到源服务器请求数据。数据包会沿着对应兴趣包的传递路径返回作为反馈[10]。客户端获取内容的过程分为2个步骤，如图1所示。

命名数据网络的网内路由节点有3个重要的数据结构：内容存储库(content store，CS),提供内容的存储；未决兴趣表(pending interest table，PIT),存储经由这个节点转发出去的兴趣包的名称和与这些请求相关的接口信息；转发信息表(forwarding information base，FIB)，记录了节点间的转发规则[11]。

图 1 NDN客户端请求处理流程Fig.1 NDN client request processing flow

1.2 缓存替换策略

由于NDN中间路由器节点缓存容量通常较小，计算资源有限，很容易达到缓存极限。当一个新的内容需要缓存时，就会面临缓存替换。因此，如何选择合适的数据包与CS表中原有数据包进行替换，以提高缓存空间的效率，对于缓存替换策略的有效性就显得尤为重要。

NDN中默认使用的缓存替换策略是LRU。LRU主要思想是，当数据在最近一段时间内经常被访问，那么它在以后也会经常被访问，所以需要替换时优先淘汰不经常访问的数据。LFU的核心思想是，以次数作为参考，设置一个时间戳，替换时优先考虑时间戳内次数最少的数据内容。在FIFO缓存设计中，应该替换缓存时间记录最早的数据。Age-based策略是给每个缓存数据设置过期时间(TTL)。缓存数据的节点与源服务器的距离和用户的请求跳数相关，距离越远，请求跳数越小，TTL就越大，替换时淘汰TTL较小或归零的数据[1]。CCP策略则是周期性地统计内容的请求次数，实时计算动态流行度，最后淘汰流行度小的内容[1]。不过，这些替换策略使得用作决策的参数单一，替换后的效果不够理想。文献[6]提出由不同用户提供的数据包应该进行区分，不能用相同的方式处理这些数据包，发送的数据对网络有影响的用户所提供的数据包应该优先考虑。缓存替换策略结合一些社交感知信息可以提高网络缓存性能，但也增加了开销。文献[12-13]提出一种基于效用的替换策略(LVF)。该策略使用延迟、受欢迎程度和年龄等3个因素计算效用函数，以选择要从CS表中替换的条目。此策略使平均缓存命中率、平均请求时延等指标有较大改善。文献[13-14]提出最近使用频率(RUF)缓存替换策略，但错误地跟踪了内容流行度的变化，为旧数据分配了更大的权重。

2 EPR机制

在信息论中，Shannon的熵概念反映了一个事件、属性或样本所包含的平均信息量。熵中隐含的思想是，事件发生的可能性越小，它在发生时提供的信息就越多。熵可以作为客观的权重度量，并以此作出客观决策[15-17]。

考虑到现有缓存替换策略的问题，基于上述熵的特点，本文提出EPR缓存替换策略。EPR引入了多个属性以作替换决策，并且根据熵权理论客观地分配每个属性的权重。当需要替换数据包时，路由器会统计CS表中所有数据包携带的缓存内容大小、内容流行度、请求代价3个属性的信息，然后根据属性值和分配的属性权重计算每个数据包的权重，接着计算每个数据包的替换概率。最后，基于计算的替换概率从所有候选中按概率大小选择替换的数据包。

EPR缓存替换策略需要统计的参数以及参数选择的意义如下：

数据包大小：较大的数据包在一定时段内缓存的位置离客户端越近，客户端发出相同请求时能就近响应，减少网络中的带宽浪费。

内容流行度：适应内容流行度的变化。

请求代价：缓存节点距离源服务器的跳数[18]。

2.1 包格式拓展

为实现EPR缓存替换策略，在数据包原有结构的基础上，对其格式进行拓展，增加了DataSize、PopularityCount、DataJumpHop等3个字段，如表1所示。其中Datasize标识数据包的大小；PopularityCount标识数据包内容的请求次数，即内容流行度；DataJumpHops标识数据包缓存路由器节点距离源服务器的跳数，即请求代价。

表 1 拓展后的数据包格式Tab.1 Expanded data packet format

2.2 替换算法

在数据包返回给客户端阶段，沿途路由节点根据EPR策略在CS表达到上限时对CS表中的数据包进行属性熵权重的计算，然后删除概率最小的数据包，缓存新的数据包。同时，为了节约计算资源，快速响应客户端的请求，本策略将路由节点的一次计算结果，用于多次对新来的数据包进行缓存替换，次数为CS表存储大小的1/2，实现“一次计算，多次决策”。当替换到一定的次数，再对现存的所有数据包进行新属性熵权重计算。

计算属性权重的算法流程如下：

步骤1 统计CS表中各个表项的DataSize、PopularityCount、DataJumpHops等3个字段的数据，将结果记录在创建的二维数组X中，X由n个m维样本构成，则X可以表示为一个n×m的矩阵，即

式中：n为CS表的数据包数量；m为属性数量；xij为第i个数据包的第j列字段的值。

步骤2 为了消除量纲影响，解决数据的可比性，对数据进行归一化处理[16]，即

(1)

式中：maxxj,minxj为矩阵X中第j列字段的最大值和最小值；minxi为第i行数的最小值。

步骤3 计算第i行数据包的第j列字段所占比重，即计算每个数据包的提取字段的权重Pij[16]，

(2)

步骤4 计算第j列字段，即DataSize、PopularityCount、DataJumpHops字段的信息熵Ej，

(3)

步骤5 计算第j列字段的差异系数dj,

dj=1-Ej

(4)

步骤6 计算第j列字段的权重wj，

(5)

步骤7 设置vi作为对各个数据包的综合评价指标，即

(6)

步骤8 设置Pbi作为进行替换决策的数值依据，即

(7)

Pbi的值越小，表示其在该路由节点继续缓存的价值越小，因此可以选择该值最小一项对应的数据包进行替换。

2.3 包缓存替换流程

EPR缓存替换策略的包缓存和替换流程如图2所示。

图 2 内容缓存与替换阶段流程Fig.2 Content caching and replacement stage process

当数据包返回时，执行4个步骤：

步骤1 路由节点接收到源服务器或上游节点传递的数据包，首先查看CS表中是否有相同的内容：是，则丢弃数据包：否，则执行步骤2。

步骤2 查看PIT表中是否有相同条目：否，则丢弃数据包：是，则执行步骤3。

步骤3 转发数据包到PIT表项中记录的所有请求接口，并在PIT表中删除已满足的条目，判断CS表是否已达缓存上限：否，则缓存在该节点；是，则执行步骤4。

3 实验测试与结果分析

为了验证本文提出的EPR缓存替换策略在NDN网络中的实际部署效果和效率，在基于NS-3[19]的网络仿真平台ndnSIM[20-21]上对EPR机制进行模拟实验,选取NDN网络中的LRU、FIFO、LVF、RUF缓存替换策略作为参照对象。

3.1 仿真环境

3.1.1 实验平台相关参数

所有仿真作业均在本地计算机上进行。操作系统及版本为Ubuntu18.04，64-bit，CPU为Intel(R) Core(TM)i7-9700K CPU@ 3.60 GHz；实验平台为ndnSIM ，版本控制在2.7；实验分配内存为10 GiB，硬盘100 GiB，处理器数量为8个。

3.1.2 实验场景

本实验拓扑为8×8的Grid网络拓扑模型。此模型所有节点都能两两通信，具有高可靠性和高通信效率特点，如图3所示。图3中：蓝色代表源服务器，共24个；绿色代表客户端，共12个；红色代表中间路由节点，共28个。

图 3 8×8拓扑模型Fig.3 8×8 topology model

假设每个客户端请求的内容个数为20个，内容前缀名为“/prefix1”，后缀为随机数。所有路由节点的缓存空间容量相同，缓存伊始不包含任何内容，采用随处缓存LCE[22]缓存放置策略。每个源服务器响应发出的数据包大小不同，范围为0～2×106。其他设置：链路带宽为1 Mbis/s，时延为10 ms;实验测试时间为20 s，客户端请求频率为20 个/s。

3.2 性能评价指标

主要从平均缓存命中率和平均请求时延两方面，对比分析本方案的性能与LRU、FIFO、LVF、RUF策略。

1) 平均缓存命中率Hr是指在实验时间内中间路由节点命中的兴趣包数与各客户端发出的请求兴趣包的总数的比值，Hr能反映路由节点减少源服务器的工作量[1]。

(8)

式中：N表示客户端发送的请求兴趣包的总数；hi表示客户端请求兴趣包在路由节点Vi得到响应的次数[23]。

2) 平均请求时延。客户端发出请求兴趣包到接收响应数据包的时间，单位为ms。该值越大，用户得到反馈越慢，平均请求时延可以用来衡量用户体验好坏[1]。

3.3 实验结果分析

3.3.1 平均缓存命中率

图4显示了EPR策略和LRU、FIFO、LVF、RUF策略的平均缓存命中率，其统计时间为10 s。

图 4 平均缓存命中率随缓存量的变化Fig.4 Average cache hit rate with cache size

从图4可以看出，当路由节点的CS表逐渐增大缓存空间，5种替换策略的平均缓存命中率也随之缓慢提高。EPR缓存策略使用数据包大小、内容流行度、请求代价等3种属性作为替换的参考，避免了只考虑单一因素可能造成的流行内容被非流行内容频繁替换的现象，内容的缓存命中率平均提升了10%，对于比较的所有缓存替换策略，其表现最佳。

3.3.2 平均请求时延

图5显示了EPR策略和LRU、FIFO、LVF、RUF策略的平均请求时延，统计时长为10 s。

图 5 平均请求时延随缓存量的变化Fig.5 Average request latency with cache size

从图5可以看出，当缓存的容量逐渐增大时，5种缓存替换策略的平均请求时延逐渐下降。特别是缓存的容量越大，EPR策略的平均请求时延效果相比其他4种策略更好。原因是缓存的数据包越多，计算信息熵时提供的信息越多，做出的替换决策越准确，效果自然更优。EPR策略的平均请求时延比LRU策略降低了7.21%。

4 结 语

本文实现了基于熵的概率缓存替换(EPR)算法，并将其性能与NDN网络中LRU、FIFO、LVF、RUF替换策略进行比较。仿真结果表明：与其他4种替换策略相比，EPR替换策略实现了更高的平均缓存命中率和更低的平均请求时延；EPR替换策略的平均缓存命中率和平均请求时延效果取决于分配的内容存储的大小。通过改变CS容量大小，发现EPR替换策略在以上两方面优于其他4种替换策略，特别是平均请求时延这一指标优势明显。对于未来的研究，将在不同的网络拓扑模型中将EPR与其他4种替换策略进行对比。