命名数据网络中的二分缓存方案

张俊敏，金继欢，侯睿

（中南民族大学 计算机科学学院，武汉 430074）

近年来世界各国都在关注设计全新的未来互联网体系架构，其中主流研究方向之一就是信息中心网络，而命名数据网络（Named Data Networking，NDN）［1］作为信息中心网络（Information-Centric Network，ICN）［2-3］的经典项目具有重要研究意义.

NDN 中存在两种类型的包，兴趣包和数据包，兴趣包中包括内容请求者所请求的数据内容名称，内容发布者将相应数据内容封装成数据包并沿兴趣包传输的路径反向返回至内容请求者.NDN 路由器包含3 种数据结构，分别是内容存储 （Content Store，CS），待定兴趣表（Pending Interest Table，PIT）以及转发信息库（Forwarding Information Base，FIB）.其中CS 提供有限的数据存储功能，PIT 记录Interest包的请求接口信息，FIB 提供数据转发接口的信息.NDN路由器处理传输包的过程如图1所示.

图1 路由器处理传输包的过程Fig.1 The process of router processing transmission packet

NDN 默认的缓存方案为沿途缓存方案Cache Everything Everywhere，CEE）［4］.该方案会将数据内容缓存在所有经过的路由器中从而产生大量冗余副本，降低缓存空间利用率.且由于路由器缓存空间有限，缓存的数据内容多样性较差，内容请求者发送的请求在路由器中被响应的次数较少，大多数请求仍需从较远的内容生产者中获取响应，从而降低缓存命中率，增大数据内容的请求时延.

为了解决上述问题，本文提出了一种二分缓存方案（Binary Caching，BC）.该方案考虑了区分数据内容的热度以及将高热度数据内容缓存在靠近内容请求者周围对缓存性能的提升.将首次被请求的数据内容缓存在中心路由器中，若该数据内容再次被请求则缓存在内容请求者的邻接路由器中，若该数据内容许久未被请求则会被逐渐推向内容生产者.从而使得内容请求者周围路由器缓存更多热度高的数据内容，有效利用了缓存空间，增加了缓存命中率以及降低了数据内容的请求时延.

1 相关研究

数据内容缓存方案一直是NDN 网络研究的重点之一.近年来，许多研究人员都提出相关缓存方案来有效利用缓存空间，提升缓存性能.

文献［5］提出基于固定概率将数据包进行缓存的方案Prob，该方案实现方法简单，并且能减少路由器中的冗余数据内容，提升缓存空间利用率.但是基于概率缓存数据内容的方法存在较大的不确定性，无法有效区分不同数据内容之间的热度差异.文献［6］提出了基于节点介数与边缘流行度的方案（Betweenness and Edge Popularity，BEP），该方案通过构建边缘节点流行度表，将最流行的数据内容缓存在介数值最高的核心路由器上，非流行数据内容缓存在介数值不高的次要路由器上，增加了缓存空间的利用率.虽然该方案有效区分了不同数据内容的流行度差异性，但是介数值最高的路由器的位置并非最接近内容请求者，请求仍需经过多个路由器转发才能命中数据内容，增大了数据内容的请求时延.文献［7］提出基于内容流行度的以指数方式增加沿途经过缓存概率的方案WAVE，该方案能将流行度高的内容以指数级别的速度缓存到内容请求者四周，减少数据内容的请求时延，但WAVE 需要在上游路由器中创建数据块标记窗口（Chunk Marking Window，CMW）来记录数据内容被请求的次数，并且CMW 会随着数据内容被请求频率的增加而增大［8］，从而增加额外开销.文献［9］提出了基于数据请求节点的就近缓存方案（Consumer-based Proximity Caching Algorithm，CPCA），该方案根据内容热度变化趋势将高热度数据内容推进在内容请求者周围路由器中，并且延长其在路由器中的缓存时间，提高数据内容缓存命中率以及减少数据内容的请求时延.但CPCA 并未将数据内容进行过滤，使得缓存在靠近内容请求者的路由器中的高热度数据内容容易被低热度数据内容替换.文献［10］提出了一种基于缓存价值的缓存方案（Leave Cache Value，LCV），该方案通过统计内容流行度，兴趣源距离，内容大小及多样性3 个指标来建立缓存决策模型，通过层次判别矩阵来确定指标的权值，并且为了减少CS 已满时的计算压力通过缓存更新方法提前删除CS中缓存价值较低的数据内容.但建立内容流行度表，内容大小及多样性统计表，内容信息熵以及复杂的缓存价值计算会增加额外计算开销以及存储开销.并且通过缓存更新方法提前删除的只有少量数据内容，无法有效减小计算压力.

2 BC方案原理

BC 方案规定从内容生产者到内容请求者的传输方向为下游方向，相反则为上游方向.将兴趣包从内容请求者转发到内容生产者时经过的路径称为当前路径.

若当前路径中路由器数量为奇数则将最中心的路由器定义为中心路由器，否则为偶数时将最中间且靠近内容生产者的路由器定义为中心路由器，具体划分示例如图2所示.

图2 中心路由器定义方案Fig.2 Central router definition scheme

BC 方案在原有NDN 包格式基础上进行了拓展，如图3 所示，其中数据包新增缓存标志字段CachingTag，该字段内容用来指示路由器是否进行缓存；兴趣包新增兴趣包跳数字段InterestHop，该字段内容用来记录兴趣包经过跳数.

图3 拓展包格式Fig.3 Expansion package format

BC 方案主要思想为将热度高的数据内容缓存在内容请求者周围，将热度低的数据内容缓存在内容生产者周围.并且随着内容热度的动态变化将热度降低的数据内容逐渐推向内容生产者.

其具体实施过程如下所示：

1）当内容生产者接收到兴趣包，读取兴趣包的跳数字段值IH，为将数据包缓存在中心路由器中，按照如下公式设置数据包缓存标志字段内容，其中CT表示缓存标志字段值，TRC表示当前路径中路由器的数量，根据TRC的奇偶性设置CT：

设置完毕将其发往下游路由器.

2）当路由器接收到数据包，读取数据包的缓存标志字段值CT，并根据缓存标志值进行对应操作：

①CT大于2，表明该数据包并未到达指定缓存路由器，路由器将数据包CT减去1 后继续向下转发.

②CT等于2，表明该数据包到达指定缓存路由器，判断当前路由器CS剩余缓存容量能否满足该数据包进行缓存，如能满足则将该数据包缓存，缓存完毕将数据包CT设为1，设置完毕继续向下转发.若无法满足则通过LRU（Least Recently Used）［11］规则从CS 中替换出最近最久未使用的数据包lruData1，将lruData1的CT设置为0后发往上游路由器，而缓存的数据包CT设置为1 后继续向下游路由器转发.

③CT等于1，表明该数据包已在上游路由器中进行缓存，直接将该数据包向下转发.

④CT等于0，表明该数据包从下游路由器转发而来，判断当前路由器CS剩余缓存容量能否满足该数据包进行缓存，如能满足则将该数据包缓存.否则通过LRU 规则从CS 中替换出最近最久未使用的数据包lruData2，将lruData2的CT设置为0后发往继续向上游路由器转发.

3）当数据包在路由器中被命中，为将数据包缓存在内容请求者的邻接路由器中，读取对应兴趣包跳数字段值IH，并按照如下公式设置数据包缓存标志字段内容，其中CT表示缓存标志字段值：

设置完毕将其发往下游路由器.

给出内容生产者或者路由器使用BC 方案处理兴趣包以及数据包的伪代码.

Algorithm 1 Process Incoming Interest/*兴趣包处理算法*//*interest是到达节点的兴趣包*//*rdata是命中后响应的数据包*/Input： 到达节点的兴趣包interest Output： 响应的数据包rdata ih ← interest.getIH（） //获取兴趣包跳数IF Node=Producer THEN //节点为内容生产者IF ih%2=0 THEN //路径中路由器数量为偶数rdata.setCT （ih/2+1） //设置数据包缓存标志值ELSE //路径中路由器数量为奇数rdata.setCT （ih/2+2） //设置数据包缓存标志值END IF END IF IF Node=Router THEN //节点为路由器rdata.setCT（ih+1） //设置数据包缓存标志值END IF EXIT

Algorithm 2 Process Incoming Data/*数据包处理算法*//*data是到达节点的数据包*/Input： 到达节点的数据包data Output： 转发或缓存数据包data ct ← data.getCT（） //获取数据包缓存标志值IF ct＞2 THEN data.setCT （ct-1） //数据包缓存标志值减去1 sendData（data） //向下游发送数据包END IF IF ct=2 THEN IF CS能满足缓存 THEN cacheData（data） //缓存数据包ELSE通过LRU规则取出lruData1将lruData1的CT设置为0将lruData1发往上游路由器发送完毕在CS中删除lruData1 cacheData（data） //缓存数据包data.setCT （1） //设置数据包缓存标志值sendData（data） //向下游发送数据包END IF END IF IF ct=1 THEN sendData（data） //向下游发送数据包END IF IF ct=0 THEN IF CS能满足缓存THEN cacheData（data） //缓存数据包ELSE通过LRU规则取出lruData2将lruData2的CT设置为0将lruData2发往上游路由器发送完毕在CS中删除lruData2 cacheData（data） //缓存数据包END IF END IF EXIT

3 实验结果与分析

本次实验使用的是ndnSIM［12］仿真平台，选取CEE，Prob，CPCA 缓存方案同BC 进行比较，其中Prob缓存概率设置为0.5.实验拓扑参照AS-6461，该拓扑由176 个节点组成.在网络拓扑中心设置1 个内容生产者，在边缘随机设置20 个内容请求者.每个内容请求者发送兴趣包的过程都符合泊松分布，设置数据内容类型总量为5000，生成的请求数据内容符合Zipf-Mandelbrot分布［13］，其中Zipf参数α决定数据内容请求集中程度，α越大表示内容请求越集中，仿真时间设置为100 s，缓存替换规则使用LRU.为接近现实网络中数据缓存节点容量远小于数据内容类型总量的情况，将每个路由器节点缓存容量设置为50 KB，使得节点缓存容量与数据内容类型总量比例为0.01.具体各项模拟参数如表1所示

表1 实验参数Tab.1 Experimental parameters

为了验证本方案的优劣，本文选取缓存命中率［14］，平均请求时延［15］以及服务器负载三个指标来进行评判.

缓存命中率为数据包在路由器中被命中的数量与所有内容请求者发送的数据内容请求总量的比值，缓存命中率越高说明路由器缓存的数据内容种类更多，缓存空间利用率越高.

平均请求时延为内容请求者在发送兴趣包后等待数据包返回的平均时间，该指标反映了数据内容缓存位置的好坏，平均请求时延越小，说明离内容请求者越近的路由器能缓存越多热度高的数据内容.

服务器负载为内容生产者在单位时间内接收到请求并响应的数据包的数量，服务器负载越大表明内容生产者接收到的请求越多.同时服务器负载过高会导致处理请求能力过差，增加内容请求时延.

图4～6 为α=0.8 的情况下四种方案的缓存命中率，平均请求时延以及服务器负载的结果对比图.

图4 4种方案缓存命中率对比结果Fig.4 Comparison results of cache hit rate for four schemes

从图4 中可以看出到，BC 方案的缓存命中率均高于其余三种方案，这是因为NDN 默认的CEE方案会使得路径中所有路由器缓存相同的数据内容，降低缓存空间的利用率.而Prob 方案通过概率进行数据内容的缓存，不同路由器仍有概率缓存相同数据内容.CPCA 方案虽然减少了数据内容的冗余，但未对数据内容的热度进行过滤，使得路由器缓存更多热度低的数据内容.而BC 方案则在减少数据内容冗余的同时过滤掉低热度数据内容使得路径中路由器能缓存更多热度高的数据内容，更大的提升缓存命中率.

从图5 中我们可以看出，CPCA 和BC 两种方案的平均请求时延逐渐降低并且趋于平缓，同时BC相比CPCA 能取得更好的平均请求时延，这是因为随着路由器中数据内容逐渐饱和，CPCA 会使得靠近内容请求者的路由器中一些缓存的高热度的数据内容被低热度数据内容替换掉，而被替换的高热度数据内容仍需从较远的内容生产者重新请求，从而增加请求时延.而BC 方案则不允许低热度数据内容缓存在内容请求者周围，因此相较于CPCA 方案能获得更低的平均请求时延.

图5 4种方案平均请求时延对比结果Fig.5 Comparison results of average request delay for four schemes

从图6中我们可以看出，在运行初始阶段BC 方案的服务器负载高于CEE，Prob，CPCA三种方案.但随着运行时间的增加BC 方案中服务器负载逐渐低于其余三种方案并趋于平缓，这说明初始阶段由于路由器的缓存空间未被存储满，BC方案中大部分请求仍需发送至内容的生产者获得响应.而随着运行时间的增加，BC方案中路由器缓存更多热度高的数据内容，即使将低热度数据内容向上游转发会带来服务器负载的增加，但总体上服务器的负载量仍低于其余三种方案.

图6 4种方案服务器负载对比结果Fig.6 Comparison results of server load for four schemes

为了验证不同内容流行度集中程度对本文方案的影响，将α设置为0.5—1.4 进行实验，得到的三个指标结果如图7所示.

图7 数据内容请求集中程度对评价指标的影响Fig.7 Impact of data content request concentration on evaluation indicators

从图7中可以看出随着数据内容的请求集中程度越高，BC方案的缓存命中率仍然稳定高于其余三种方案，这是因为BC 方案将数据内容首次缓存在中心路由器中，并且随着数据内容的积累，中心路由器将热度高的数据内容继续推向内容请求者，而将热度低的数据内容逐渐推向内容生产者，更快的过滤掉请求次数少的数据内容，使路由器能缓存更多种类数据内容的同时减少冗余的数据内容.同样的从平均请求时延以及服务器负载两个指标的结果来看，BC方案除了能将热度最高的数据内容缓存在邻接路由器中，还能将热度较高的数据内容缓存在靠近内容请求者的路由器中.减少了邻接路由器频繁进行缓存替换的操作同时通过设置中心路由器分担了向上转发数据包造成的负载.

4 结束语

本文针对现有缓存算法的局限，提出一种二分缓存方案，过滤低热度数据内容，增加缓存的数据内容的多样性，减少数据冗余，降低平均请求时延.但本文提出的方案在数据内容热度过滤方面仍有提升空间，下一步将结合路由器缓存容量与周期性数据内容热度统计的方法将相应热度的数据内容更快的缓存在与内容请求者相应距离的路由器中.