命名数据移动自组织网络的官渡缓存策略

摘要

命名数据移动自组织网络的官渡缓存策略属于网络缓存领域。官渡策略的目标是尽可能减少内容在MANET移动节点上的缓存数量，减少节点的计算和维护开销，但同时仍能够维护NDN模式带来的快速响应时间，以适应NDM的存储和计算能力都有限的移动节点。核心思想是如果转发节点距离内容节点太远、且有存储空间，同时该数据可能再次被请求，而且在周围还没有被缓存，那么转发节点就缓存该数据，否则不予缓存。以此减少数据在网络中的冗余、减少对移动设备存储空间的占用，还将数据尽可能地放置在离用户较近的地方以减少对网络带宽的使用，提高响应速度。本发明大大减少移动节点的缓存空间的占用，不增加太多的网络流量，且提供很好的响应延迟。

说明书

技术领域

本发明属于网络缓存技术领域。

背景技术

移动自组织网络MANET(MobileAdhocNetwork)已被关注很长时间。但 MANET的应用和研究多停留在军事和应急环境下，而不是公众网络应用中。 这使MANET并没有真正普及起来。无线网络技术的发展使更多的公众移动 设备能够很容易地接入网络。调查表明现在互联网上越来越多的流量是由移 动设备贡献的。

各种数量巨大的移动设备可能在某个时间段内集中在某个区域内，如拥 挤的地铁、移动的旅行车厢、繁忙的机场等。如果有可用的MANET网络则 可为这些用户提供很多有吸引力的应用。例如，通过MANET，同一旅游车厢 中的人们可以一起观看其中某个移动设备上的视频，但不用支付任何流量费 用、不用进行任何带外交流、甚至完全不知道视频来自哪个设备、也无需任 何网络基础设施的支持。这些为MANET准备好了足够的技术支持和应用市 场。

NDN(NameddataNetworking)是近十几年来根据Internet应用发展的特点 提出来的一种新型的网络互联结构。NDN以内容的名字作为路由的索引，将 资源和其所在主机分离开。NDN在网络中缓存转发的数据。NDN将内容作为 寻址的实体，使内容可在任何地方存储，所以可能检索内容的副本。这不但 提高了响应时间，而且还缓解了网络失效带来的影响。

NDN对移动性有天生的支持优势。移动用户离开原来位置，只要重新申 请获取数据就可以、而且可能从新位置附近重新获得数据，而不需要和原来 的数据源保持连接及重新建立连接。NDN没有中心、没有层次的模式更适合 支持没有结构的MANET网络。NDN模式应用在MANET中的网络被称为命 名数据MANET网络(Named-dataMANET)，简称NDM。

在NDN基本模式中，内容转发路径上的所有节点都会缓存该内容。这被 称为沿路径缓存(on-pathcache)。虽然只在沿途节点上缓存内容已经减少了 缓存的数目以及单独发送缓存分发数据包的流量和管理开销。但MANET网 络移动节点的存储空间一般很有限，因而网络整体上可用的缓存空间也就很 有限。NDN沿路缓存的机制会给节点形成巨大负担。因而，需要设计合适的 缓存策略才能使NDM有实际应用的可能。

有很多针对有线网络的ICN/NDN网络的缓存算法研究工作，但是，专门 为NDM网络考虑移动环境的缓存算法很少。

NDM的缓存策略需要尽可能减少数据在网络中的冗余，将有限的缓存空 间缓存最应该缓存的内容，同时把内容缓存在最能提高网络性能的节点上。 此外，由于节点的处理能力有限，因此缓存策略还应该减少节点的缓存管理 开销，采用尽可能简单的方法。根据上述情况分析，本文给出一个缓存算法， 该算法将减少沿途路径上的缓存节点，使数据尽可能地分散，并缓存在离数 据源较远的位置。我们将该算法称为“官渡”算法，意取曹操在官渡之战部署上 的战略方针：不是分兵把守黄河南岸，而是集中兵力、扼守要隘、重点设防、 以逸待劳、最终实现以少胜多。算法意在用最有用的内容布置在最合适的节 点上阻击尽可能多的兴趣包。

对于使用缓存技术的网络，首先要解决的就是在什么地方缓存内容的问 题。NDN基本模式是在内容包途径节点上缓存内容。这样做的好处是可以捎 带缓存，以少的通信量达到大的可能缓存。问题是可能占用了过多的缓存空 间，尤其是NDM中移动节点缓存空间有限的情况下。IoannisPsaras等人为了 减少ICN网络中缓存的冗余，提出了进行全局优化的想法，他们在内容包经 过的节点上根据整条路径所能支持的缓存空间总和以及节点离用户的距离得 出的概率来进行缓存，使距离用户越近的节点缓存概率越大。但这种方法需 要知道路径的长度、每个节点在路径中的位置、路径上所有节点的总体缓存， 实现起来开销比较大，尤其是在拓扑变化较快的移动网络中，因而不适用于 NDM网络。

WAVE也选择在应答路径上的某些节点来缓存数据，缓存与否由上游节 点根据请求数的情况决定。该算法总体看起来数据会分布在路径上，但其实 数据更多地缓存在数据源周围，即距离用户越近的节点缓存越少。这种策略 对于类似于树形的拓扑结构会比较适合，因为边缘节点接入的终端用户较少， 中间节点会为更多的边缘节点服务，因此这样做可以提高缓存的利用率。但 对于网络拓扑不规则的移动网络来说，则容易造成数据缓存集中在数据源周 围，而距离需要的用户较远。

YuguangZeng等人提出了一个简单的使用间隔缓存的策略减少NDN网 络中缓存的冗余量。该算法在返回的内容包中加入记录内容包在转发过程中 的转发间隔数。每转发一次该值减1，当值为0时节点缓存该内容，并重置该 值继续转发。该算法非常容易实现、开销很小，值得借鉴。

除了缓存位置，哪些内容应该缓存是需要考虑的另外一个问题。数据的 流行度是一个经常被考虑的因素。流行度通常通过对该数据的请求计数来预 测。但各种策略对请求计数的处理是不一样的。比如，让节点定期从其子树 收集请求计数，对于计数小于阈值的内容则不予缓存(该算法针对ISP(Internet ServiceProvider)内部范围网络，要求各个节点维护树形的拓扑结构)。WAVE 则用文件请求计数的指数函数作为推荐下游节点缓存的文件子块数。让节点 只缓存请求计数超过阈值的数据，以避免缓存只会被请求一次的数据。

用复杂计算换取ISP外部流量的减少。不过该算法真正实现起来限制比 较大，而且只适合于ISP内部，不适合计算能力比较弱、网络拓扑不规则且 变化较快的NDM网络。WAVE以文件为单位进行计数，然后按照文件分片 缓存。这在NDN网络中不具普遍性，而且最终形成的数据分布还是比较集中， 冗余度也比较高。但其采用指数增长来分化流行和不流行内容的缓存密度是 值得借鉴的。]还考虑对兴趣包到来的接口进行计数，如果这个数值超过设定 阈值也进行缓存，理由是更多网络部分需要该内容。这是个非常有意义且容 易实现的做法。不过移动网络因为是广播网络，因而不存在多个接口的问题。

缓存策略的实现通常需要节点之间协同交流有关信息。信息交换的方式 一般分为两种。一是在请求包或者内容包中增加新的消息字段捎带。另一种 是发送单独的协同数据包捎带方式增加的通信量非常少，缺点是与基本转发 策略交织在一起，需要更改基本协议。如果基本协议已经普及则存在实施困 难。而采用单独的数据包会增加网络流量，比如要阶段性地交换缓存的概要。 因此，此类算法通常需要采取一些措施减少流量，如使用BloomFilter减小概 要的规模。同样由于会增加网络流量，所以需要协同的方案大都针对自治域 范围内。这样一来便于实现，二来对于内部流量，ISP也可以接受。这些算法 通常可以减少域内到域外的流量，因而ISP有支持它们的动机。

发明内容

官渡策略的目标是尽可能减少内容在MANET移动节点上的缓存数量， 减少节点的计算和维护开销，但同时仍能够维护NDN模式带来的快速响应时 间，以适应NDM的存储和计算能力都有限的移动节点。官渡策略的核心思想 是如果转发节点距离内容节点太远、且有存储空间，同时该数据可能再次被 请求，而且在周围还没有被缓存，那么转发节点就缓存该数据，否则不予缓 存。以此减少数据在网络中的冗余、减少对移动设备存储空间的占用，同时 还能够将数据尽可能地放置在离用户较近的地方以减少对网络带宽的使用， 提高响应速度。

按照官渡策略的目标，首先要选择缓存数据的节点。为减少缓存的维护 开销以及与NDN模式保持一致，缓存节点在数据转发节点中选择。当数据转 发到某中间节点时，该节点在转发数据的同时根据情况决定自己是否缓存该 数据。

命名数据移动自组织网络的官渡缓存策略，其特征在于：

选择缓存数据的节点；缓存节点在数据转发节点中选择；当数据转发到 某中间节点时，该节点在转发数据的同时根据情况决定自己是否缓存该数据； 转发节点在决定缓存数据时要考量自己的空闲存储空间是否足够；只有当缓 存所需数据量与节点的空闲存储空间的比值小于1/10，才能缓存该数据；

在内容包中增加一个跳数字段；该跳数字段在内容包每次被转发时加一； 规定网络能够容纳的节点数的开方为网络半径，在这里取网络半径的一半为 设定距离，超过设定距离，则认为该节点距离源节点较远，能考虑缓存该数 据；

在内容包中增加一个缓存间隔字段；应答节点在内容包中设置缓存间隔 字段为初始值，初始值为网络半径的1/8；内容包每次被转发时缓存间隔字段 递减1；如果内容被缓存则缓存间隔字段重新设置为初始值；

具体原理解释如下：

由于NDM中移动设备的存储空间有限，每个节点既是中间转发设备又是 终端设备。因此，转发节点在决定缓存数据时要考量自己的空闲存储空间是 否足够。只有当缓存所需数据量与节点的空闲存储空间的比值小于特定阈值、 不影响节点自身应用的运行时，才能缓存该数据。通常，将此阈值设置为系 统可用空闲空间的1/10。

转发节点距离内容节点的距离通过内容包所经过的跳数进行判断。为此， 我们在内容包中增加一个跳数字段。该跳数字段在内容包每次被转发时加一。 规定网络能够容纳的节点数的开方为网络半径，在这里取网络半径的一半为 设定距离，即若网络中节点数为64，则此阈值取4。超过设定距离，则认为 该节点距离源节点较远。

为降低数据缓存的冗余度，若附近节点已经缓存该数据，则中间节点不 再缓存。因此节点需要知道其他节点的缓存情况。为此，在内容包中增加一 个缓存间隔字段。应答节点在内容包中设置缓存间隔字段为初始值，初始值 为网络半径的1/8。即若网络中节点数为64，则存间隔字段数取1。内容包每 次被转发时缓存间隔字段递减1。如果内容被缓存则缓存间隔字段重新设置为 初始值。

由于缓存空间有限，所以应该缓存最可能被其他节点再次需要的内容。 关于数据的流行度考量，最直接的缓存策略是选择那些流行度高的内容进行 缓存。要实现该策略，一个做法是节点记录对每个内容收到的兴趣包的个数， 然后选择个数较高的内容缓存。但该做法需要为每个内容维护一个记录，开 销非常大。因为NDM网络中的名字空间非常大，这会导致流行度表非常大， 而且查表和维护开销比较大。

为此，为减少移动节点的时间和空间开销，我们将流行度的考虑放入到 缓存替换上。节点会在剩余存储空间小于一定阈值时执行缓存替换算法。我 们采用最简单通用的LRU算法，替换出最近最少被使用的内容。这样缓存中 会剩下最近被请求的内容，也就是比较流行的内容。这样节点会缓存第一次 收到的内容，这样做也会将那些不够流行的内容在缓存中暂时留存一段时间， 而不至于在缓存时就考虑流行度，而根本得不到缓存。同样在缓存替换时没 有采用各种关于流行度的计数和计算，也是考虑实现上的低时间和空间开销。

官渡缓存策略的具体过程如图8所示。首先，收到数据包的中间节点判 断自己与数据源节点的距离。在与数据包的发送节点的距离(数据包的跳数) 小于设定距离时不缓存数据，节点只要修改数据包中的缓存间隔数。如果缓 存间隔数达到0，则设置为初始值；如果没达到0，则减少1即可。同时增加 数据包的跳数，然后转发数据包。

当距离大于设定距离时，有可能要缓存。此时要综合考虑缓存间隔数和 节点的存储空间情况。当间隔数大于0时，表明周围有较近的节点缓存了该 数据，所以，该节点直接递减间隔数，递增数据包跳数，转发数据包。如果 缓存间隔数为0，则节点应该考虑缓存该数据。但如果“没有空间标志”为1， 表明节点没有可用的存储空间，则此时节点放弃缓存该数据，继续递减缓存 间隔数至-1，递增数据包跳数，将数据包转发出去。否则，若节点有存储空间， 则缓存该数据，将缓存间隔数设置为初始值，递增数据包跳数，转发数据包。

当节点收到的数据包的缓存间隔数为-1时，表明上一个节点应该缓存该 数据，但因为空间问题没有缓存。所以，节点应该缓存该数据。节点将缓存 间隔数恢复为初始值，递增数据包跳数，将数据包转发出去，然后缓存该数 据。如果该节点的“没有空间标志”为1，表明节点也没有可用的存储空间， 则执行LRU缓存替换算法，为此数据替换出空间。

当节点的空闲空间小于制定阈值时，“没有空间标志”将被设置为0，否 则为1。

本发明通过实验可以得出官渡算法可以大大减少移动节点的缓存空间的 占用，而且并不增加太多的网络流量，而且同时能够提供一个很好的响应延 迟。

附图说明

图1为节点缓存空间占用对比。

图2是总体节点缓存空间占用对比图。

图3为网络数据流量对比图(只统计内容包，不包括请求包)。

图4是总体网络流量对比图。

图5是数据包应答延迟的比较。

图6是总体应答时间的比较。

图7是成功率，即发送出请求包后，请求节点成功收到应答数据包的比 率。

图8本发明流程示意图。

具体实施方式

为了评估算法的效果，我们在ndnSIM环境下进行了模拟评估。NdnSIM 是网络模拟器NS-3的一个模块扩充，它实现了NDN通信模型。模拟在 Ubuntu-12.4systemwithlibboostofversion1.48.

4.SimulationandEvaluation

表1模拟环境的参数设置。在1000m*1000m的空间内模拟802.11g无线 Adhoc网络，网络的数据模式为ErpOfdmRate54Mbps。网络中节点数为64， 初始位置随机分配。节点采用随机移动方式，最大移动速度为30m/s，最大驻 留时间为4s。整个实验测试100s。

通信采取ndnSIM的服务者-消费者模型，随机选取10％的节点作为服务 节点，随机选取50％节点作为消费者发送请求。用户发送的兴趣报文满足泊 松到达特性，平均每秒发送2000个兴趣包。消费者的请求数据内容符合zipf 分布。每个内容包的大小设置为512B。每个节点的缓存空间上限设置为60000 个内容包，即提供30M大小的缓存。CS表的缓存替换策略采用LRU(Least RecentlyUsed)策略。

本文从以下四个方面对缓存策略进行评估，分别是节点缓存空间占用、 网络流量、以及数据包应答时延、请求得到内容的成功率。对比策略为基于 NDN的数据转发全缓存策略、以及间隔缓存策略，分别记作NDN和Interval。 Interval和官渡策略的缓存节点间隔数均设置为1，即每隔一个节点考虑对数 据进行缓存，缓存空间上限设置为全部缓存。官渡策略的距离阈值设置为3。 官渡算法每个节点的缓存空间上限设置为其他两种算法的1/10，即6000个内 容包，3M。

图1为节点缓存空间占用对比。从图上可以看出官渡策略占用空间是最 低的。Interval居中，NDN算法最多。这和算法的行为完全一致。因为NDN 在所有经过节点缓存数据，而Interval因为间隔缓存空间有所减少，官渡在离 数据源较远的地方进行间隔缓存，因而进一步减少缓存空间的占用。

图2是总体节点缓存空间占用对比图。从图中可以看出，官渡算法的空 间占用大约在NDN算法的1％，而Interval算法则大约在18％左右。

图3为网络数据流量对比图(只统计内容包，不包括请求包)。由于NDN 在网络中缓存的内容最多，因此可以用较短的路径应答请求者，所以，网络 中产生的总体流量最少。但从图中可以看出，尽管官渡缓存的更少，但是， 所产生的数据流量和Interval算法比较接近。

图4是总体网络流量对比图。从中可以看出官渡算法的流量甚至比 Interval算法还略少一些，但是非常接近。

图5是数据包应答延迟的比较。数据包应答延迟这里定义为请求数据包 发出后，直到成功收到应答的数据包所发花费的时间。从图上可以看出因为 NDN缓存在全部节点上缓存了数据，因而可以用较少的延迟应答请求。但是， 尽管官渡用了更少的缓存空间，从图中可以看出其延迟与Interval非常接近。

图6是总体应答时间的比较。可以看出官渡算法的应答时间和Interval算 法非常接近。

图7是成功率，即发送出请求包后，请求节点成功收到应答数据包的比 率。可以看出官渡算法和Interval算法的成功率比较接近。反而是Ndn全缓存 算法的最低。这是因为在NDN中虽然转发路径上的每个节点都缓存了数据， 但是每个节点缓存的内容比较相近，如果一个节点没有兴趣包要求的内容， 其他节点响应的可能性也比较小。也就是说，虽然很多节点缓存了内容，但 是整个网络的缓存空间利用率较低，大部分节点缓存了相同的内容。由于内 容量的巨大，致使缓存空间不够，导致有些内容不能被缓存，而对这部分内 容的请求，会被网络转发至较远节点甚至是源节点才能得到应答。由于长距 离转发导致丢包的升高，从而降低了成功率。反而是官渡和interval因为把数 据分散在节点上，节点缓存的内容不尽相同，反而可以更好地响应请求。