NDMANET 中基于内容优先级的缓存策略研究

高子轩，郑 烇，2

（1.中国科学技术大学自动化系未来网络实验室，合肥 230026；2.中国科学技术大学先进技术研究院，合肥 230088）

0 概述

随着移动互联网的快速发展，现有的网络体系在可扩展性、移动性和安全性等方面逐渐出现性能瓶颈。为了适应互联网的需求变化，一种新的网络体系架构——信息中心网络（Information Centric Networks，ICN）［1］应运而生，而命名数据网络（Named Data Networks，NDN）［2］作为ICN 架构的一种具体网络实现，受到研究人员的广泛关注。在NDN 中，用户通过内容名称去获取内容，而无需关心内容从何而来，同时，在返回内容的过程中会在沿路根据缓存策略进行缓存。

近年来，考虑到NDN 的优越性能，研究人员开始将NDN 和移动自组织网络（Mobile Ad hoc Networks，MANET）相结合并进行分析［3-5］。传统的MANET 基于TCP/IP 协议进行通信，但是由于MANET 中节点移动而引起了网络拓扑动态变化，导致其难以建立稳定的端到端链路，这不仅使得网络较难实现高效的数据传输，同时也阻碍了MANET 的实际应用。由于MANET 中多数通信是“以内容为中心”的信息共享，而不关心数据承载在哪个终端以及某个数据是由哪个终端产生，因此NDN 适用于MANET［6-8］，其比“以主机为中心”的IP 路由协议更有利于数据传输。

命名数据无线移动自组织网络（NDMANET）的研究起步较晚，许多问题亟待解决。其中，缓存策略是NDN 中的一个关键技术［9-11］，由于MANET 中节点的移动性、网络的动态性以及网络所呈现出的分布式特性，使得现有NDN 中的缓存机制可能不再适用于NDMANET。因此，如何在节点空间资源有限、网络节点自由移动的MANET 中有效保证数据的可用性，提高更高优先级内容的命中率，加快请求的响应速度，降低数据冗余，是NDMANET 数据缓存机制研究中的关键问题。

不同于有线环境下可以扩展较大的缓存容量，无线环境下移动节点的缓存容量大小受限，因此，对缓存替换策略的研究显得尤为重要。目前，缓存替换策略主要包括先进先出（FIFO）、最近最少使用（LRU）［12］和最少经常使用（LFU）［13］。这些策略多数是从现有网络中演变而来，通常存在两点缺陷，一方面，它们没有考虑内容本身的特性，例如内容优先级、内容的访问频率等，另一方面，未考虑MANET应用场景下节点自由移动时重要节点脱离网络时引发重要内容不可用的问题。因此，上述策略并不适用于NDMANET 这种新型网络架构。

本文分析NDN 的特性，根据内容本身所传达的信息，如内容优先级、内容访问频率等指标，提出一种基于内容优先级的缓存替换策略PFC。通过向数据包添加新的TLV 字段“priority”，设计决策函数实现缓存内容的替换，以在保证平均缓存命中率的同时提高重要内容的缓存命中率和可用性。

1 相关工作

缓存机制包括缓存放置策略、缓存替换策略和缓存一致性维护策略等。缓存替换策略在缓存已满而需要缓存新对象时，决定如何替换出缓存中的一些旧对象，从而为新对象腾出空间。在NDMANET中，有限的缓存空间使缓存替换策略更具挑战性。NDMANET 的缓存研究包括MANET 和NDN 2 个方面。

在MANET 的相关缓存研究中，学者们提出了各种缓存技术。文献［14］提出一种SQUIRREL 缓存软件，该软件可以集成到Internet的节点中，允许区域内的多个节点共享其缓存。文献［15］提出CachePath、CacheData 和HybridCache 3 种缓存方案，CachePath存储数据的位置和路径信息，CacheData 通过存储数据而非路径来节省时间，HybridCache 是一种混合方案。上述MANET 缓存策略均基于TCP/IP 网络，需要存储与内容对应的IP 地址，因此，并不适用于NDN 网络。

在NDN 的相关缓存研究中，多数使用LRU、FIFO、LFU 和Random 策略作为缓存替换策略。为了提高NDN 的性能，研究人员也为其设计了很多缓存算法。文献［11］提供了有关信息中心网络中缓存机制的调查结果，其分析不同的参数（如缓存时间、内容本身、内容相关性以及缓存中的生存期）对ICN缓存性能的影响。文献［16］提出一种ICN 的缓存替换策略，其将内容的流行度视为替换指标，此外，还考虑网络中的全局流行度。但是，该策略不适用于NDMANET，一方面，对于NDMANET 而言，全局内容流行度并不现实，而且还会对CS 管理造成更多的负担；另一方面，该策略会延长缓存检索时间。文献［17］提出一种基于流行度的细粒度缓存替换策略FGPC，但是，FGPC 仅使用请求频率来决定内容的替换。文献［18］提出一种基于层次流行度的缓存替换策略，其将内容流行度分为5 个层次，每个数据包都属于一个流行度级别，当缓存已满时，将替换缓存中流行度最低的数据包。但是，该策略也导致一个问题，一些重要内容不一定是流行内容，仅通过流行度去决定缓存替换，对于一些特定内容将不合适。文献［19］提出一种通用缓存替换策略，节点可以通过各项指标，包括请求频率、节点距离、节点可达性等，综合决定替换内容，但是，该策略中的内容度量系统CMS 的权重系数是根据节点和网络中心的距离来确定的，对于MANET 这种去中心化的网络而言显然不合理。文献［20］将节点的位置加入到缓存替换决策中，但是，其决策函数考虑的因素较多，计算复杂度较高，从而提高了替换时的计算代价与响应时间。

从已有文献可以看出，MANET 缓存研究是基于IP 网络的，不适用于NDMANET 网络，针对NDN 的缓存替换策略也不适合NDMANET，原因是它们没有考虑节点的移动性、网络的去中心化等NDMANET 的特性。此外，多数缓存策略并未考虑内容本身的优先级。因此，本文从内容的优先级出发，同时兼顾内容的请求频率，提出一种缓存替换策略PFC。

一扇窗子立刻打开，拿着枪的黑脸孔的人竟跳进来，踏了金枝的左腿一下。那个黑人向棚顶望了望，他熟悉地爬向棚顶去，王婆也跟着走来，她多日不见金枝而没说一句话，宛如她什么也看不见似的。一直爬上棚顶去。金枝和母亲什么也不晓得，只是爬上去。直到黄昏恶消息仍没传来，他们和爬虫样才从棚顶爬下。王婆说：“哈尔滨一定比乡下好，你再去就在那里不要回来，村子里日本子越来越恶，他们捉大肚女人，破开肚子去破‘红枪会’（义勇军的一种），活显显的小孩从肚皮流出来。为这事，李青山把两个日本子的脑袋割下挂到树上。“

2 基于内容优先级的缓存替换策略

有效的缓存替换策略可以提高缓存命中率，从而提升内容分发性能。但是，现有研究一方面未考虑NDMANET 不同于传统NDN 网络的3 个特点：1）分布式控制，没有中心节点；2）节点的自由移动导致网络拓扑变化以及某些节点可能会“掉线”的情况；3）节点的资源有限。另一方面，现有缓存策略仅考虑内容的流行度而忽略了内容本身的优先级，这会导致重要内容的可用性降低，一旦重要节点离开网络，可能出现请求无响应的情况。

2.1 NDN 缓存机制

NDN 的通信模型由消费者驱动，消费者发送兴趣包（Interest Packet）请求相应的数据包（Data Packet）。节点在收到兴趣包后，其内容缓存CS（Content Store）中如果有匹配的内容，则会返回数据包；否则，节点先查询未决兴趣表PIT，查看是否有记录，若无记录，兴趣包将根据转发信息表FIB 在网络中进一步转发。在接收到数据包后，节点首先检查相关请求是否在PIT 中，如果对该数据的请求仍然没有得到响应，则将数据进一步转发到网络中的下游，否则将丢弃该数据。同时，节点根据适当的缓存决策方案将数据存储在CS 中，如果CS 达到其最大容量，则根据缓存替换策略进行内容替换。NDN 的通信流程如图1 所示。

图1 NDN 通信流程Fig.1 NDN communication procedure

2.2 内容的可用性与优先级

在NDMANET 中，内容的可用性指在网络中一部分节点出现故障后，网络整体是否还能响应消费者的请求。在一些实际的NDMANET 应用场景，如军事活动、救援行动中，由于环境的复杂性，可能经常发生节点脱离网络的情况。如果该节点缓存了重要内容，可能会导致重要内容不可用。因此，对于NDMANET 而言，节点可用性的重要程度不低于命中率、响应延时等指标。

常用的保证可用性的方法是在多处保留内容副本，对于NDN 架构而言，其每个节点所带有的缓存能力可以很好地解决该问题，但是，这些是建立在缓存容量足够大的情况下。在移动场景中，大缓存意味着低移动性，为保证节点的移动性，高可用性需要与缓存替换策略相结合。因为难以提高所有内容的可用性，所以本文的目标是提高重要内容的可用性。根据节点内容对可用性的不同需求，本文对内容优先级进行划分，即一个内容很重要，在网络中需要很高的可用性，则其优先级相应很高。

在本文模型中，通过对数据包添加新的TLV 字段“priority”来区分内容的优先级，priority 值越大，内容优先级就越高。

2.3 缓存替换策略

缓存替换决策函数所含的参数如下：

2）节点的请求频率。本文期望在引入内容优先级后对全局平均命中率并不会产生太大影响，因为NDN 缓存的本质就是为后续请求提供内容副本从而提高网络性能，包括请求的响应时间、吞吐量和网络负载等，如果仅考虑优先级，则会对全局性能造成影响，一些较为流行的内容可能因为没有被标记为重要内容而被替换，因此，本文引入节点的请求频率，请求频率度量内容在当前节点的CS 中被请求的次数，在某种程度上可以反映一个内容是否流行，如果是流行内容，其请求频率会相对较大。

3）内容大小。考虑到移动自组织网络节点缓存容量的限制，本文将内容大小也作为一个衡量指标。

根据以上分析，对于每一个到达CS 的内容k而言，都需要计算一个如式（1）所示的函数：

其中，P(k)表示内容k的优先级，F(k)表示内容k在当前CS 中的请求频率，S(k)表示内容k的大小，cf是F(k)的标准化系数，cs是S(k)的标准化系数。

从式（1）可以看出，R(k)随着F(k)线性增长，即当有很多节点对同一个内容k发起请求时，R(k)可能会变得很大，但是如果在接下来一段时间内没有节点请求内容k，k也会一直被缓存在CS 中，因为没有较大的R(j)来替换它。为了解决这一问题，本文在替换策略中考虑内容的生成周期，每次新内容到达后CS 会检测缓存中是否有内容过期，如果有，则删除该内容，以腾出缓存空间。

基于内容优先级的缓存替换策略PFC 的伪代码如算法1 所示，其步骤为：当一个内容k到达CS 时，先检查该内容是否已经在缓存中，如果已经在缓存中，则更新R(k)的值；否则，检测缓存空间是否已满，若缓存未满，则缓存该内容，如果缓存已满，则计算R(k)值，并与CS 其他内容的R值进行比较，淘汰R值最小的内容，最后，清空过期的内容。

算法1基于内容优先级的缓存替换策略PFC

3 实验结果与分析

本文选取比较常用的缓存策略LRU 和FIFO 作为对照组，通过模拟仿真来分析基于内容优先级的缓存替换策略的缓存性能。

3.1 实验环境

使用ndnSIM 仿真平台进行实验，网状拓扑共包含50 个节点，每个节点既是内容生产者（Producer）也是内容消费者（Consumer），实验参数设置如表1 所示。不同生产者产生的内容有不同的优先级标记，为了方便分析，本文将内容分为重要内容和普通内容2 种，其中，10%是重要内容，其余是普通内容，所有的内容流行度服从Zipf-mandelbrot 分布，消费者节点对内容的请求服从泊松分布，请求速率为10 req/s。此外，为了模拟移动网络的情景，在仿真进行到5 min 时，通过改变节点的通断关系来改变网络拓扑。

表1 实验环境的参数设置Table 1 Parameters setting of experimental environment

3.2 结果分析

缓存命中率是到达缓存节点时命中的请求数与到达缓存节点的请求总数之比。图2 所示为不同缓存替换策略下缓存命中率与缓存大小的关系，从图2可以看出，随着缓存容量的增加，各策略的内容命中率都提高，原因是缓存容量增加，可以缓存的内容副本数也随之增加，导致内容的命中率提高。

图2 平均缓存命中率随缓存容量的变化情况Fig.2 The change of average cache hit rate with cache capacity

图3 所示为重要内容命中率随缓存容量的变化情况，从图3 可以看出，各策略的重要内容命中率也随缓存容量的增大而提升，且本文内容优先级缓存策略对于重要内容的缓存命中率有显著提高，特别是在缓存容量较小时，缓存命中率较其他2 种策略而言提升幅度更大。这是因为缓存大小有限时，内容优先级缓存策略优先保留内容优先级较高的内容，即淘汰相对不重要的内容。随着缓存容量的增加，可以缓存更多的内容副本，内容优先级缓存策略对于重要内容的缓存命中率仍然高于其他缓存替换策略。

图3 重要内容缓存命中率随缓存容量的变化情况Fig.3 The change of important content cache hit rate with cache capacity

图4 所示为重要内容缓存占比随缓存容量的变化情况，从图4 可以看出，在缓存容量较小时，重要内容在缓存中占比最高，此时缓存的都是较为重要且请求较多的内容，随着缓存容量的增加，重要内容缓存占比开始减小。图4 中开始阶段本文策略的重要内容缓存占比达到1 是因为缓存较小，而重要内容的数量大于缓存容量，因此本文策略将重要内容全部缓存从而替换不重要的内容。其他策略的重要内容缓存占比基本保持不变，即它们并不区分重要内容与普通内容。

图4 重要内容缓存占比随缓存容量的变化情况Fig.4 The change of important content cache proportion with cache capacity

图5 所示为平均响应跳数随缓存容量的变化情况，从图5 可以看出，缓存可以降低请求的平均响应跳数，随着缓存容量的增加，响应跳数减少，内容请求者可以更快地获取内容，原因是随着用户的不断请求，其感兴趣的内容被缓存在离用户近的节点，响应跳数随之降低。

图5 平均响应跳数随缓存容量的变化情况Fig.5 The change of average response hops with cache capacity

为了验证本文缓存策略PFC 在提高内容可用性方面的性能，设计一个简单的包含10 个节点的小型拓扑，网络中有2 个节点产生重要内容，在仿真进行到3 min 时分别不断开、断开1 个和2 个重要节点与网络的连接，然后计算10 s 后的内容命中率，以反映重要内容的可用性。实验结果如图6 所示，其中，100%-topo 表示2 个节点都不断开，50%-topo 表示1 个节点断开，0%-topo 表示2 个节点均断开。从图6可以看出，在没有节点断开时，3 种缓存策略的命中率相差不多，随着重要节点的断开，命中率下降，这是因为内容生产者节点断开连接后，用户需要去向其他潜在内容拥有者请求，原有路由可能请求不到内容，造成命中率下降。但是，本文策略命中率下降幅度比较缓慢，这是因为该策略优先缓存重要内容，在整个网络中重要内容副本更多，所以更容易命中。

图6 缓存命中率随拓扑结构的变化情况Fig.6 The change of cache hit rate with topology

4 结束语

本文提出一种基于内容优先级的缓存替换策略。根据节点内容对可用性的不同需求划分内容优先级，将优先级作为缓存替换的参考因子进行缓存替换决策。实验结果表明，该策略能够提高NDMANET 网络的缓存命中率，缩短响应时间，提升网络的抗毁性。本文的内容优先级划分方式较简单，今后将通过更精确的方法，如根据生产者节点之间的博弈以及一些经济指标来决定缓存内容的优先级，从而使本文策略更具可靠性。