一种面向邻近缓存的引导式内容路由机制*

杜传震，兰巨龙，田 铭

（国家数字交换系统工程技术研究中心 郑州 450002）

1 引言

随着互联网技术与应用的飞速发展以及互联网用户数量的快速增长，传统IP网络中的地址既表示节点位置信息又表示身份信息的方式混淆了位置和标识的功能界限，在支持内容分发业务方面的局限性越来越明显。针对该问题，近年来提出的一种将内容与主机在网络层分离的创新思想引起了广泛关注。以内容为中心的网络成为未来网络的一种重要模式和发展趋势。

命名数据网络（named data networking，NDN）是一个全新的网络架构，使用层次化的数据名字而不是IP地址进行数据传递，让数据本身成为互联网架构中的核心要素[1～3]。该架构采用“兴趣分组”的形式以通告的方式实现点到多点的内容获取和分发；“数据分组”沿着“兴趣分组”到达的反向路径传递给内容的请求者，实现了基于跳的流量平衡，并试图在路径节点上以“缓存”的形式驻留热度较高的服务内容，尽可能地以最短传输路径抵近请求用户。NDN路由与转发模型如图1所示。

图1 NDN路由与转发模型

命名数据网络直接基于名字的路由和转发方式，有效地解决了IP网络中地址空间耗尽、移动性与可扩展性差等问题。NDN路由器负责发布名字前缀公告，并通过路由协议在网络中传播，每个接收到公告的路由器建立自己的转发信息库（forwarding information base，FIB）。当有多个兴趣分组同时请求相同数据时，路由器只会转发收到的第一个兴趣分组，并将这些请求存储在未决兴趣表（pending interest table，PIT）中。当数据分组传回时，路由器会在PIT中找到与之匹配的条目，并根据条目中显示的接口列表，分别向这些接口转发数据分组。转发完成后，路由器会删除相应的PIT条目，并将数据分组存储在内容缓存（content store，CS）中。CS是路由器的缓冲存储器，使用某种缓冲替代策略。

命名数据网络采用针对内容的路由方式:节点兴趣分组直接面向内容源服务器进行转发，在转发过程中探知所经各节点是否缓存所请求的内容，以达到最短时间返回数据的目的。虽然相较于IP网络，命名数据网络的内容路由方式提高了返回数据分组的效率，但是这种路径缓存方式使不在路径上的邻近缓存内容无法被充分利用。如图2所示，用户周围的路由节点存储着相应的数据，但不能得到有效利用，这种现象导致访问数据路径过长。

图2 命名数据网络中内容获取过程

针对命名数据网络中内容路由节点的缓存利用率问题，相关研究已经取得了一定的进展和成果。Shanbhag S等人提出了一种服务路由方法SoCCeR （services over content-centric routing），将内容路由问题归结为服务选取问题，实现了对沿途节点缓存的充分利用，但仍未考虑对邻近节点缓存的内容[5]。参考文献[3]比较了exploitation（开发）和exploration（探测）两种不同的内容路由机制，并且提出了一种混合的路由方法，即对源服务器的内容建立路由，而对节点缓存的内容副本进行探测，但其出发点是减少路由条目数量和网络代价。参考文献[6]将基于势能的路由应用于内容网络，设计了缓存感知目标识别 （cache aware target identification,CATT）路由方法。然而，CATT路由方法在请求通过势能路由之前采用随机转发的方式，其路由性能取决于随机转发的初始值设置，可能会导致较长的路径时延。参考文献[7]提出了通过探测邻居节点缓存的内容，构建邻居缓存表的NCE路由策略，从而充分利用邻居节点资源。但考虑到NDN中的内容数量巨大，该探测方式存在实现上的困难，会导致内容请求的平均响应时间增加。参考文献[8]对节点副本通告的必要性和可行性进行了定性分析，虽提出利用布鲁姆滤波器进行路由表聚合，仍缺乏对路由机制的定量分析和具体实现方式。此外，上述研究都未考虑节点上缓存内容的根据热度的动态更新以及不同内容缓存之间的差异性。

本文借鉴参考文献[9]和参考文献[10]中对非结构化P2P网络中建立快捷链接的思想，提出一种面向邻近缓存的导向式便捷路由（fast content routing，FCR）机制，解决了命名数据网络中邻近缓存路由构建的问题。

2 便捷路由定义

内容源服务器路径为用户节点S发送兴趣分组到达内容源服务器D的最短路径，期间经过的节点集合为S={Na，Nb，…，Nm}，响应跳数为 H1。

定义 1 （便捷路由路径（fast content path，FCP））将用户节点S到存储所需内容的最近邻近缓存节点N（N埸S）的最短路径定义为用户S的便捷路由路径，期间转发节点集合为 SFCP={NA，NB，…，NM}，响应跳数为 H2，如图 3 所示。

图3 请求节点的便捷路由路径

定理 路由节点N作为到用户节点S最近的缓存节点，必然使得H2≤H1，否则内容源作为最近缓存与定义相矛盾。若用户 S存在 FCP，则SFCP∩S≠○/。

证明 用反证法。假设SFCP∩S≠○/，接入网络的路由节点为N0。由网络中内容源路径必然存在，则N0∈S且N0埸SFCP，则S的接入点N0与路由节点N不连通，则FCP不存在，与已知矛盾，故而假设不成立。

根据便捷路由路径与服务器路径至少具有一个相交点的原理，为了寻找构建 FCP，只需由 S={Na，Nb，…，Nm}获知其他近邻节点N对应内容C的存储内容且计算相应路由。

3 缓存通告及代价

节点周围的缓存分布情况主要可以由探测与主动通告两种方式获得。探测虽然可以针对具体内容进行精确定位，但是产生的流量是双向的，网络代价太高，难以大规模部署。相较于探测的方式，主动通告方式的流量是单向的。在合理控制通告范围的情况下，批量分发自身的缓存内容条目可以将网络代价降至最低。

设网络拓扑由G={V，E}表示，V是节点的集合，E为链路的集合，网络中节点个数为|V|。通告数据分组大小为B，节点平均连接度为m，命名数据网络节点的缓存根据内容热度不断发生变化，间隔为T。在网络G中时间T内至少产生|V|次缓存变化，需要通过N（N为不小于logm|V|的整数）次通告，才能将一次缓存内容更新发送至网络中所有节点。那么产生的流量代价为:

由于内容节点缓存更新时间最短的只有数秒，单位时间内的流量代价为C/T≥|V|2·B/T。

为了减少缓存内容通告代价，本文提出的引导式便捷路由通告机制的主要原理包含3个方面。

（1）设定面向邻近缓存内容的合理通告范围|V|

互联网存在小世界特性，距离相近的地区访问与缓存的内容具有相似性[11]。由于同一个集群节点对同一类内容感兴趣的概率很大，提出基于兴趣关联度的标准来构建节点兴趣集群。因此，在整个网络中通告节点缓存消息是繁琐而且没有必要的，将通告范围缩小在兴趣集群内可以提高通告内容利用率。基于此推论，本文提出一种引导式的便捷内容路由通告机制，克服洪泛法通告产生的巨大流量代价。

（2）选取热度较高的内容延长通告时间间隔T

NDN中的内容路由查找伴随着节点缓存的频繁更新，具有动态性与挥发性。节点内更替频繁的缓存条目对于捷径路由没有指导意义，可能会造成路由振荡，故本文提出只通告节点缓存中热度较高，即长期处于稳态的部分存储数据。由于节点内更替频繁的缓存信息不向外通告，使得通告时间间隔延长，也确保网络中的节点缓存内容的稳定性。

（3）设计独特的通告报文结构以减少通告报文的大小B

通告内容通常包含节点缓存中的副本信息的名字。本文拟借鉴布鲁姆过滤器的研究成果，提出一种光谱布鲁姆过滤器的高效数据结构，减少通告报文的大小。

4 引导式便捷内容路由机制

4.1 基本思想

本文提出的引导式邻近缓存通告机制首先依据节点缓存热度与需求的相似性，将网络节点划分为若干兴趣节点集群。集群节点只在内部通告热度较高的缓存内容，不属于同一集群的节点之间不进行缓存通告。便捷内容路由的构建大致分为3个步骤:集群构建、缓存通告以及便捷路由建立。便捷路由表构建完成后，节点若收到内容请求，按照内容缓存表、未决兴趣表、便捷路由表和转发信息表的顺序查表，执行相应的转发操作。

4.2 节点兴趣集群的构建

在NDN中，给定内容需求节点i与j，兴趣内容集合分 别 为 Cinterest（i）、Cinterest（j），则 它 们 共 同 的 兴 趣 集 合 为 PC=Cinterest（i）∩Cinterest（j）。若节点 i在过去的时间段 T 内对内容的需求次数为MC，i，那么节点i与节点j的兴趣关联系数（interest relevancy coefficient）则定义为:

MC，j与 MC，j分别表示节点 i、j对内容 C 在过去时间段T 内的需求次数。MC，j与 MC，j的值越接近，则对 θ（i，j）的影响越大，说明节点i、j两节点对内容C的兴趣关联度越大。反之，则关联度越小。由于 MC，j与 MC，j不排除为 0的可能性，正数d确保除数不为0。

4.2.1 核心节点的选取

节点兴趣集群的构建不是无序的，选取兴趣相关度最高的核心节点（leader node）构建兴趣集群，可以使得集群的收益提高。定义节点i的关联度ηi为该节点与其邻居节点 的 兴 趣 关 联 系 数 之 和θ（i，j），作 为 选 取核节点的标准。选取的核节点关联度越高，该集群收益越大。

在兴趣集群中，对兴趣节点进行统计比较，可以将节点的关联系数ηi作为该节点选取优先值。兴趣节点对邻近节点进行范围通告。为了减少核心节点选取导致的流量冗余，兴趣节点的ηi越大，则等待的时间越短。节点收到比自身优先值大的通告时，不再通告自身的ηi，而是将具备较大优先值的节点信息通告出去。

4.2.2 兴趣集群范围确定

为了体现邻近节点缓存的优势，提高便捷路由的效率，命名数据网络中的请求节点所在集群的范围设定不宜过大（即H2≤H1）。参考文献[7]对内容网络的范围通告进行了详细的研究，指出通告范围scope为2的网络集群平均时延仅仅比scope为1的网络集群减少3%。对于具备缓存能力的内容网络，绝大多数内容需求都可以在请求节点的邻近1～2的节点范围内得到满足（即3跳范围）。考虑到双向传输的时延叠加，在参考文献[7]的基础上，将本文的网络通告范围的上限设定为6跳，即scope=6，在后面章节通过仿真实验，对通告范围的最优值进行讨论。

4.2.3 兴趣集群构建算法

根据兴趣关联度的集群构建需要考虑缓存内容及其热度，只通告部分长期处于稳态的缓存数据。构建流程如下。

步骤1 内容缓存节点根据当前缓存表中的内容及其热度，计算该节点的兴趣关联度ηi，构造某种或某些内容的通告报文。

步骤2在等待T时间之后，将该节点的内容关联度通告给邻近节点，设定需要的通告范围scope和hop值并向所有接口进行转发。

步骤3 在时间T内，对节点接收到的报文进行比较，计算比较节点优先值，将具备较大优先值的信息通告出去。

步骤4 当前节点在收到内容通告报文后，将收到的ηi和自身的ηi进行比较，若收到的节点通告兴趣关联度较大，则节点更新集群的范围与构建，并将该通告节点设定为集群的核心节点，将scope减1，同时将该节点通告出去。否则，丢弃该通告报文。

步骤5 将集群范围内的具备最大ηi的节点设定为集群核心节点，它在集群内发送确认消息，完成集群的构建。

步骤6 当缓存节点的所有内容达到一定程度或经过时间间隔T后，重新进行内容通告。

4.3 引导式邻近缓存通告

4.3.1 通告报文设计

为了实现邻近缓存的内容通告，在网络中设计引导式缓存通告报文如图4所示。

图4 引导式缓存通告报文格式

其中，type字段用来表示报文的类型，cluster字段记录当前节点所在集群的编号。timestamp字段用来记录报文的发送时间，判别通告内容的最新版本。hop字段用来记录内容通告节点到当前节点的跳数，作为通告的路由代价，用于便捷路由计算的依据。URL与scope分别为需要通告的内容名字（NDN中的命名机制采用URL形式）和通告范围（跳数）。每通告1跳，hop字段加1，scope字段减1，直到为0。邻居节点根据scope字段是否为0来决定是否继续通告，如果为scope字段为0，则不再进行内容通告。

4.3.2 通告内容选取

为了避免缓存内频繁的内容更替造成通告消息膨胀，通告内容只选择缓存中相对稳定的 （也就是热度值较高的）部分内容进行通告。首先节点缓存按照所采用的缓存策略对内容进行排序，选择热度较高的前x%个副本条目进行通告。如节点内采用LRU（least recently used）策略，则把新近压入缓存队列的x%通告邻居节点，如图5所示。

图5 节点缓存的热度列表

过度频繁的更新可能会造成路由时内容条目缺失，如果当前通告的副本条目中有任意一个被节点删除，则触发新一次的缓存通告，将当前时刻排序在前x%的节点缓存信息发送给兴趣集群内所有节点。

4.3.3 引导式邻近缓存通告算法

完成节点集群建立后，节点都已划分在各个集群中。便捷路由构建可以分为两个阶段:引导式缓存通告构建阶段与内容传递阶段。便捷路由构建阶段主要进行内容的通告和便捷内容路由表（fast content table，FCT）的建立。首先，集群中的缓存节点进行通告之前的初始化操作:节点i设定自身所属的集群数值和通告内容时间戳TSnew以及通告范围scope，根据内容热度构造缓存内容前x%的缓存内容条目并向所有接口转发。设定邻居节点j在接受通告之前的通告结果为，其中，nameC为路由条目名字，face表示其通告接口。没有内容C的记录时，时间戳TSold=0。当节点j接收到来自节点i的通告后，执行以下步骤。

步骤1 节点j判断与节点i是否属于相同的集群；如果是，执行步骤2，否则丢弃该通告报文，执行步骤5。

步骤2 判断当前收到的内容通告报文是否为最新。若TSnew

步骤3 若TSnew≥TSold，该内容通告为最新条目。接收通告报文，并计算接收报文的hop值作为路由代价:hopnew←hop0+hop（i，j）。若 hopnew≥hop0，说明路由代价过高，丢弃报文，执行步骤 5；否则执行步骤 4。

步骤4 查询FCRT，更新URL对应表项信息，将hopnew填入转发信息表中的路由代价域，然后根据scope值的大小决定是否转发此内容通告给下一节点。

步骤5 通告结束。

便捷路由表构建完成后，节点收到内容请求即兴趣分组后，对比当前便捷路由代价与转发信息表中的服务器路径代价，若便捷路由代价较小则在便捷路由表中处理该条目并创建转发信息表，即按照内容缓存表、便捷路由表和转发信息表的顺序查表，执行相应的转发操作。兴趣分组在节点内的转发过程如图6所示。

图6 节点内兴趣分组转发过程

4.4 便捷内容路由算法

节点j在收到邻居i关于内容C的通告后，记录内容名字、到达接口和到达此缓存内容的代价，按如下步骤执行便捷内容路由算法。

步骤1 对比当前便捷路由的hop与转发信息表中到内容源服务器的代价，若便捷路由hop较小，则在便捷路由表中创建该条目；否则删除该路由内容条目对应的便捷路由。

步骤2 同一个内容存在多个便捷路由转发接口时，优先选择最小代价的接口作为下一跳。

由上述算法创建的便捷路由表格式见表1。

表1 便捷内容路由表

5 仿真实验与结果

5.1 实验设置

采用C++及MATLAB语言模拟NDN运行过程拓扑图并进行相关性能仿真。实验环境为4 GHz英特尔酷睿2双核处理器Windows 7操作系统的PC。根据命名数据网络特点构建路由节点，由GT-ITM拓扑生成工具生成一个路由节点数为30的平面随机网络拓扑，其中任意两个路由节点之间存在直接相连接路径的概率为0.3。从边缘节点中随机选取1个节点作为服务器节点为整个网络节点提供内容的发布与服务，其容量足够存储所有内容对象。剩下的节点作为普通的内容路由节点与用户直接相连，缓存容量为B（假定内容对象大小相同，则B表示节点可以缓存的内容个数）。为了便于分析，相邻节点之间的时延设为10 ms。

为方便测量，设定内容源服务器中内容对象数量N=2000个，假定URL路由条目大小相等[13]，设为 128 KB。内容对象的流行度服从Zipf-Mandelbrot分布，即第k个内容对象的流行度为 Pk=H-1（σ,q,N）/（q+k）σ。其中，σ为形状参数，q 为移动参数，取 σ=0.4，q=10，H（σ,q,N）为归一化系数。内容路由节点与用户主机直接相连，由用户发送兴趣分组（数据请求分组）至相关联的内容节点请求数据。在模拟用户发送数据分组时使其满足泊松到达特性[20]（λ=4个/s），并且在各个路由节点随机到达。仿真拓扑如图7所示，圆点表示路由器，线段表示链路，链路带宽为100 Mbit/s。

图7 仿真拓扑

为了有效地评估实验效果，在对便捷路由机制进行仿真的同时，对前人提出的几种方法进行仿真对比。首先是基本的NDN内容路由机制，不考虑节点邻近缓存，直接将请求分组转发到内容源服务器获取内容[6]，记为SCR（simple content routing）。其次为参考文献[7]提出的邻居缓存探测（NCE）策略。参考文献[14]提出的通告缓存副本的路由方式，记为ACC。这3种方法中邻近缓存节点内容缺失时，直接将请求分组转发给内容源。最后，对本文提出的基于节点兴趣集群的引导式便捷路由机制FCR进行仿真比较。

为了对引导式邻近便捷路由机制的性能进行验证，以用户请求平均时延和内容源服务器负载为性能指标进行对比。源服务器负载定义为仿真期间源服务器收到的请求分组个数。

5.2 最佳兴趣集群的构建

为了确定最佳的兴趣集群范围，指导缓存信息通告范围scope，针对上述网络拓扑，分别对不同范围的兴趣集群进行仿真。结果如图8所示，分别给出了scope不同值时的兴趣集群构建示意。实验表明，scope值越小，兴趣集群数量越多，集群内的成员越少。

5.3 最佳兴趣集群范围

图9给出了在上述兴趣集群构建图中不同通告范围对平均时延和通告代价的影响。结合上述对通告内容比例的仿真，取通告内容比例为60%。随着集群范围的增大，便捷路由的时延逐渐减小。引导式通告报文数量亦随集群范围的增大而增大。从图中发现，当兴趣集群范围超过6跳时，时延发生了回转现象，主要是因为通告范围过大，逐渐接近内容源路由路径长度，导致路径时延开始回升。综合考虑对性能与代价的影响，最佳集群范围为5跳。

5.4 内容缓存通告比例

取缓存容量B=60，总的请求数Nq=2000个。以内容通告比例x%为变量对捷径路由时延性能进行仿真，结果如图10所示。随着通告比例的增加，时延性能逐渐改善，然而当通告比例超过80%后，平均时延反而有所增加，这是因为缓存中的内容存在动态性，将部分频繁更替的内容通告出去，导致节点将请求转发到这些内容已经被删除的节点，造成缓存缺失，重新从其他节点获取内容使得时延增加。另外，随着通告范围的扩大，这种时延增加的现象愈加明显。

图8 不同范围节点兴趣集群的构建

图9 兴趣集群范围对时延与通告报文数的影响

图10 缓存内容通告比例对性能影响

5.5 用户请求平均时延

图11 用户请求平均时延

仿真过程中共产生2000个内容请求，记节点从内容请求发出到收到所请求的数据的时延为单个请求时延，则所有内容请求的平均时延仿真结果如图11所示。

由图11可以看出，基本的NDN内容路由方式，不考虑节点上内容副本的路由，时延最大。NCE和ACC方法都建立了到达邻居节点副本的路由表，但未考虑邻居节点上内容的热度差异和命中概率，内容缺失情况较为突出，需要从其他资源处重新获取，导致请求时延增加。相比之下，捷径路由考虑了缓存节点内容的更新删除，一旦通告的缓存内容被替换，则进行通告更新，提高了请求的命中概率，其请求的平均时延最小。

5.6 内容源服务器负载

取缓存容量B=60个，内容请求数Nq=2000个。以内容服务器收到的兴趣分组的个数作为其性能指标，则服务器负载性能的仿真结果如图12所示。

图12 内容源服务器负载

由图12可见，在总的内容请求数为2000的情况下，原始的NDN路由方式只将请求路由到确定的服务器，因而不会产生额外的请求分组，ACE和NCE都存在内容缺失导致重新请求的现象，会产生额外的请求分组。FCR会将通告内容的更新及时发布给兴趣集群内的邻居节点，所以不存在重路由现象。在服务器收到的请求分组数量上，SCR最多，因为其只能利用转发路径上的部分缓存的内容，而ACE、NCE和捷径路由利用了缓存节点的内容资源，有效地减少了内容服务器的负载。便捷路由相对于SCR，在服务器负载上减少了约30%。

6 结束语

命名数据网络中直接面向内容源服务器的路由方式提高了返回数据分组的效率，但不在发送路径上的邻近缓存内容无法充分利用。为解决此问题，提出基于兴趣集群的面向邻近缓存的引导式便捷路由机制FCR。依据互联网小世界特性，针对小区域内邻近节点兴趣相似度不同，设计引导式的缓存内容通告机制，最后设计独特的通告报文结构和合理的通告范围实现便捷路由机制。理论分析与实验结果表明，该方法减少了用户请求的平均时延，有效地降低了内容源服务器的负载。由于内容节点的频繁更新，这种便捷路由机制可能导致节点路由表项的膨胀，如何聚合压缩路由表中转发信息条目是下一步研究和探索的重点。

1 Muscariello L,Carofiglio G,Gallo M.Bandwidth and storage sharing performance in information centric networking.Proceedings of ACM SIGCOMM ICN Workshop,Toronto,ON,Canada,2011:26～31

2 Tsilopoulos C,Xylomenos G.Supporting diverse traffic types in information centric networks.Proceedings of ACM SIGCOMM ICN Workshop,Toronto,ON,Canada,2011:13～18

3 Zhang L X,Estrin D,Burke J,et al.Named data networking(NDN)project.http://named-data.net/techreports.html,2013

4 Shanbhag S,Schwan N,Rimac I,et al.SoCCeR:services over content-centric routing. Proceedings of ACM SIGCOMM Workshop on Information-Centric Networking,Toronto,Canada,2011:62～67

5 Chiocchetti R,Rossi D,Carofiglio G,et al.Exploit the known or explore the unknown?Hamlet-like doubts in ICN.Proceedings of ACM SIGCOMM ICN Workshop,Helsinki,Finland,2012:7～12

6 Eum S,Nakauchi K,Murata M,et al.CATT:potential based routing with content caching for ICN.Proceedings of ACM SIGCOMM Workshop on Information-Centric Networking,Helsinki,Finland,2012:49～54

7 叶润生，徐明伟.命名数据网络中的邻居缓存路由策略.计算机科学与探索,2012,6(7):593～601

8 Wang Y,Lee K,Venkataraman B,et al.Advertising cached contents in the control plane: necessity and feasibility.Proceedings of IEEE INFOCOM,NOMEN Workshop,Orlando,Florida,USA,2012:286～291

9 Sripanidkulchai K,Maggs B,Zhang H.Efficient content location using interest-based locality in peer-to-peer systems.Proceedings of IEEE INFOCOM,San Franciso,CA,USA,April 2003

10 Pireddo L,Nascimento M A.Taxonomy-based routing indices for peer-to-peer networks.Proceedings of the SIGIR Workshop on Peer-to-Peer Information Retrieval,the 27th Annual International ACM SIGIR Conference,Sheffield,UK,July 2004

11 Mcpherson M,Lovin L,Cook J.Birds of a feather:homophily in social networks.Annual Review of Sociology,2001,27(1):415～444

12 Zhang Y,Zhao J,Cao G H,et al.On interest locality in content-based routing for large-scale MANETs.Proceedings of IEEE 6th International Conference on Mobile Ad Hoc and Sensor Systems(MASS'09),Macao,China,2009

13 Berners-Lee T,Fielding R T,Masinter L.Uniform Resource Identifier(URI):Generic Syntax.RFC3986,2005