基于副本通告的内容中心网络快捷路由机制

刘 涛，程东年，田 铭

(国家数字交换系统工程技术研究中心，郑州 4 50002)

基于副本通告的内容中心网络快捷路由机制

刘 涛，程东年，田 铭

(国家数字交换系统工程技术研究中心，郑州 4 50002)

内容中心网络是一种新的网络体系结构，采用以名字为标识的内容路由。然而，基本的内容中心网络路由机制仅对服务器的内容建立路由表项，缺少到达节点上缓存的内容副本路由，导致节点缓存资源利用率低，产生较大的内容访问时延。针对该问题，通过将节点缓存的副本向其他节点进行通告，提出一种快捷路由机制，使得节点能够感知邻居节点的内容副本，从而选择最优内容源以获取内容。仿真结果表明，相比不考虑节点副本路由的机制，快捷路由机制可明显减少用户请求的平均时延，在节点缓存容量为60个内容对象时，减少了43%的服务器负载。

内容中心网络；快捷路由；内容活跃度；命名数据网络；马尔可夫链；副本

1 概述

网络音视频等多媒体业务的发展，使得互联网的功能从端到端的主机通信变成了内容的分发，用户更关注于内容而不是内容的存储位置。为此，研究人员提出以内容为中心的网络体系，即内容中心网络(Content Centric Network, CCN)[1]，其核心思想是通过对内容的直接命名和基于内容名字的路由来进行内容的获取和分发。CCN通常是扁平的拓扑结构，类似于现有的IP网络。在CCN中，节点除了传统的路由和转发功能之外，还具备内容缓存能力。与基于IP地址的路由方式相比，CCN基于名字进行路由，不需要知道内容的位置或主机。

CCN的网络实体能够缓存临时的内容(即内容副本)，以备将来访问，副本缓存时间从数分钟到数天不等，并且受内容流行度、缓存策略以及请求转发策略所影响。为了利用这些副本资源，理想的内容路由方式是设计一种路由和转发机制，对所有临时的内容副本都能够进行寻址，以使得用户请求能够被转发到“最优”(例如，最近的)的可用副本。然而，这种理想的方式在CCN中存在实现上的困难，原因如下：

(1)网络规模。CCN设计适应多种应用需求，不仅在小规模的有限网络区域，也在整个网络范围内对内容副本进行寻址和路由，这将导致极大的控制开销。

(2)时间因素。存储在网络节点上的副本不停地加入和删除，存在高度的动态性和时变性，对这些副本进行路由更新导致极大的信令开销[2]。

针对节点副本路由问题，文献[3]的研究只考虑对内容源服务器的内容进行通告，内容请求在向源服务器转发的过程中检查各个节点上是否存在所请求的内容，这种路径缓存“检查”的方式使得不在路径上的内容副本无法被利用。文献[4]将以服务为中心的网络体系和以内容为中心的网络体系结合在一起，提出了一种服务路由方法SoCCeR，旨在解决服务选取问题，但是仍然缺少对节点副本内容的路由机制。文献[2]比较了2种不同的内容路由机制：exploitation和exploration，并且提出一种混合的路由方法，即对源服务器的内容原本建立路由表，而对节点缓存的内容副本进行探测，但其主要目标是减少路由条目数量。文献[5]提出一种邻居缓存路由策略NCE，通过探测邻居节点缓存的内容，构建邻居缓存表，从而利用邻居节点提供服务。由于CCN网络中的内容数量巨大，上述探测的方式存在实现上的困难，而且导致内容请求的响应时间增加。文献[6]将基于势能的路由应用于CCN，设计缓存感知目标识别路由方法CATT，然而，CATT方法在请求通过势能路由之前采用随机转发的方式，限制了其应用。文献[7]对节点副本通告的必要性和可行性进行了定性分析，除了通过布鲁姆滤波器进行路由表聚合外，缺乏对缓存特性的定量分析和具体的实现。此外，上述研究都未考虑节点上缓存网络的动态性和不同内容副本的差异性。

对节点副本进行路由的难点在于CCN缓存节点上内容的动态性和挥发性，路由到的缓存节点并不一定包含所请求的内容。因此，最大限度地减少这种不确定性成为本文研究的出发点。借鉴文献[8-9]对非结构化P2P网络中建立快捷链接的思想，提出一种基于副本通告的快捷路由(Short-cut Routing, SCR)机制，解决CCN节点上副本的路由构建问题。快捷路由机制对LRU(Least Recently Used)[10]缓存策略下节点上副本的有效性进行评估，节点有选择地通告，并限定通告范围，减少了副本路由导致的缓存缺失。与已有研究相比，快捷路由考虑了不同节点上内容命中率的差异性，以此实现转发。

2 快捷路由原理

在CCN中，数据在内容源到请求用户的路径上沿途缓存，使得副本分布在多个节点。由于网络中的内容对象数量巨大，并且内容分布动态变化，如果将节点缓存的所有内容向网络进行洪泛通告，就会导致路由表膨胀，带来非常大的网络开销。与之相比，快捷路由将缓存与路由紧密地结合在一起，只将节点上部分驻留时间较长的内容进行通告。

研究表明，互联网存在小世界特性，并且距离相近的地区，用户访问具有相似性[11]。因此，快捷路由机制对内容的通告限于邻居节点，从而减少通信开销，即在局部构建了小跳数环境。

根据以上描述，快捷路由的基本思想可以概括为：

(1)副本选择性通告。缓存节点将自己缓存的比较活跃的内容副本向其邻居进行通告，使得在节点上缓存的内容可以被周边节点所“感知”，从而使得副本的覆盖范围扩大。另一方面，限定副本通告的范围，即只向特定跳数之内的节点通告。

(2)选取最优内容源。节点在收到副本通告之后，建立内容的“局部地图”，即到达副本的快捷表项(short-cut entry)，使得节点知晓内容的“存储位置”，从而选择最优的存储节点获取内容。

3 副本通告

对于任意的CCN节点a，假定节点a缓存了内容i，a向其n跳内的所有邻居节点发送通告消息，通告消息包含内容名字、活跃度等，图1(a)和图1(b)分别是1跳和2跳内容通告示意图，其中，灰色节点a是发送通告消息的节点；斜纹节点是灰色节点a的1跳或2跳邻居节点；白色节点为灰色节点a 2跳之外的节点；无箭头线条表示节点之间的链路；带箭头线条表示通告消息传输链路。

图1 内容通告示意图

在内容副本信息通告中，需要考虑不同内容副本的差异性。内容副本在缓存中是动态变化的，由于用户对内容的请求服从幂律分布，大部分请求访问的是部分热点内容。在特定的时间段内，不同内容副本在缓存中驻留的时间是不同的。

3.1 通告内容选取

缓存节点选取哪些副本向邻居通告是快捷路由的一个重要问题，直观的理解是根据副本在缓存中的持续时间长短来决定选取哪些副本，然而持续时间不容易获取。根据缓存的特性，内容访问的活跃程度或频繁程度决定了缓存时间的长短，并与具体的缓存策略相关，现有路由器缓存算法大多采用LRU策略。本节对LRU缓存策略下的通告内容选取问题进行分析。

对于任意的单个缓存节点a，M为总的内容对象个数，N为节点a的缓存容量，即节点a可以缓存的内容对象个数为N。图2为LRU缓存策略下CCN单个节点的缓存模型，Ci表示第i个内容对象，i=1,2,…,M，l=1,2,…,N表示内容对象在缓存中的位置。在LRU策略下，新加入的内容放置在位置N，而位置1的内容被淘汰出缓存。在通告副本的选取上，一个简单的策略是选择缓存位置最高的部分内容，然而，LRU策略没有考虑内容被访问的频率，因此，缓存位置并不能反映内容的“热度”。相比之下，缓存节点上内容的命中概率能够更精确地表示从此节点获取内容的概率。因此，通过对LRU缓存模型的分析，获取内容的命中概率，来指导通告内容的选取。

图2 CCN节点缓存模型

对于节点a上任意的内容i，以内容i在缓存中的位置为马尔可夫链的状态(内容i不在缓存中的状态为0)，建立马尔可夫链模型，对缓存特性进行分析。假定λ为内容i的请求速率，µ为使得内容i的缓存位置降低的其他内容的请求速率，r为内容i移出内容缓存器的速率，内容请求到达服从泊松过程，则内容i的状态转移如图3所示。

图3 CCN节点缓存马尔可夫链模型

根据马尔可夫链定义，此链为齐次马尔可夫链，其状态转移矩阵为：

根据状态转移矩阵Q，计算出平稳分布矢量π=(π0, π1,…,πN)如下：

平稳分布π反映了节点a上内容i在各个缓存位置驻留的概率，特别地，π0表示内容不在缓存中的概率，即内容i的缓存缺失概率，对应地，内容i的命中概率为hi, a= 1-π0。

在式(2)中，λ为内容i的请求速率，µ为使得内容i的缓存位置降低的其他内容的请求速率。文献[12]分析证明，假定节点上所有内容的请求只有一小部分请求的内容位于缓存中，则µ可以近似为节点上除内容i外其他所有内容的请求速率。本文利用上述近似得到λ和µ的值，进而获得节点上各个内容副本的命中概率hi, a，以此指导通告内容的选取。

根据以上分析，节点计算出各个缓存位置上内容副本的命中概率，并且设定阈值φ。对于任意的内容i，只有当其命中率hi, a＞φ时，才通告内容i，避免在缓存上存在时间很短的内容被通告出去。

3.2 副本通告范围设定

副本通告范围n的设定是另一个需要研究的问题。节点上缓存的内容副本不需要洪泛通告到整个网络，n越大，节点上的路由表项越多，导致快捷路由表膨胀，并且网络的控制流量开销太高。n的设定需要考虑代价与收益的权衡，然而，代价与收益的计算依赖于特定的网络拓扑结构，难以通过统一的方式进行分析。为此，快捷路由机制仅给出确定通告范围n的3个主要原则和可行的取值。

原则1 副本通告应限定在域内。其假定副本的覆盖范围主要是域内的用户。

原则2 副本通告产生的控制流量应限定在一定程度内。以网络中副本通告报文与数据报文(Data Packet)的数量之比ρ为指标，则ρ＜ρ0，其中，ρ0为预设的ρ的阈值。

原则3 根据副本通告建立的快捷路由表的平均条目数量应限定在一定上限内。为了减少重复，节点在根据副本通告构建快捷表时可以检查本地缓存，如果通告的内容在本地缓存并且其命中概率较高，则不建立此内容的快捷路由表项。

一个可行的方式是将n设定为缓存节点到内容服务器的距离(跳数)n0，其假定为各个节点到服务器的距离近似相等。当内容的请求节点到缓存节点的距离大于到服务器的距离时，请求被转发到服务器节点获取所需内容，因此，缓存节点的内容通告范围大于n0不会带来更大的收益。

为了实现内容副本信息的通告，在CCN中，设计针对快捷路由的副本通告报文，格式如图4所示。

图4 内容副本通告报文格式

类型字段表示报文的类型，随机数字段为随机数，时间戳字段用来记录报文的发送时间，跳数字段用来记录内容通告节点到当前节点的跳数。内容名字和范围分别为需要通告的内容的名字和通告范围。

内容通告报文可以一次通告多个内容副本，比如对相同缓存等级的所有内容名字只发送一个通告报文。为了对多个内容名字进行压缩，采用布鲁姆滤波器对名字列表进行压缩，并作为内容副本通告报文的内容名字域。节点收到副本通告报文后，建立快捷路由表。不失一般性，本文后续部分，仍以内容名字作为路由表项。

4 快捷路由表构建

节点在收到邻居关于内容的通告后，根据内容名字、到达接口和到达此邻居的跳数，创建如表1所示的快捷路由表(short-cut table)。

表1 快捷路由表

当同一个内容存在多个转发接口时，则选择跳数最小的接口转发兴趣包。由于快捷路由转发到的节点并不保证一定存在所需的内容，即存在内容缺失，因此建立类似于文献[7]中的回退机制，当请求的内容缺失时，可以回退到请求包的来源节点选择其他的接口转发。

5 工作流程

快捷路由可以分为以下阶段：快捷路由构建阶段和内容传递阶段。

快捷路由构建阶段主要进行内容的通告和快捷路由表的构建，其步骤如下：

Step1 内容缓存节点根据当前缓存表中的内容及其活跃度，构造某个或某些内容的内容通告报文，设定需要通告的范围并向所有接口进行转发。

Step2 当前节点在收到内容通告报文后，判断当前收到的内容通告报文是否已存在，即报文内容和随机数是否都相同，如果相同则丢弃该通告报文，否则执行Step3。

Step3 节点在收到内容通告报文后，更新范围值。节点检查快捷表，如果存在此报文中内容名字对应的表项，则更新表项信息，否则创建快捷路由条目，然后根据范围值的大小决定是否转发此内容通告。

Step4 当缓存节点的所有内容变化达到一定程度或经过时间间隔T后，重复Step1～Step3，重新进行内容通告，并且更新快捷路由表。

快捷路由表构建完成后，节点收到内容请求即兴趣包后，按照内容缓存表、快捷路由表和转发信息表的顺序查表，执行相应的转发操作。兴趣包在节点内的转发过程如图5所示，其中，C表示内容缓存表；P表示PIT表；S表示快捷路由表；F表示FIB表。

图5 节点内兴趣包转发过程

6 仿真实验与分析

本节对快捷路由在CCN中的性能进行仿真验证。实验使用GT-ITM工具产生网络拓扑，并使用VC++2008和Matlab2010工具进行仿真。

仿真参数描述如下：网络包含30节点，任意节点之间以0.3的概率相连。链路带宽为100 Mb/s。在边缘节点中，随机选取1个节点作为内容源服务器，负责内容原本的发布和服务，其容量足够存储所有内容对象，其余节点为普通的CCN路由节点，并且与用户直接相连，缓存容量为B(假定内容对象大小相同，则B表示节点可以缓存的内容个数)，缓存策略为LRU。网络中内容个数为N=2 000个，假定内容大小相等，设为128 KB。内容对象的流行度服从Zipf-Mandelbrot分布[13]，即第k个内容对象的流行度为Pk=H-1(σ, q, N)/(q+k)σ，其中，σ为形状参数，q为移动参数，取σ=0.4，q=10；H(σ, q, N)为归一化系数。

用户请求到达服从到达速率λ=4个/s的泊松过程，并且在各个路由节点随机到达；节点内容通告间隔为δ。仿真实验的硬件环境如下：处理器主频为双核2.37 GHz，2 GB内存，Windows7操作系统。

为了对快捷路由的性能进行验证，以用户请求平均时延和内容源服务器负载为性能指标进行对比。源服务器负载定义为单位时间内收到的请求包个数，在仿真中将单位时间取为仿真程序运行时间，因此，源服务器负载可以表示为仿真期间源服务器收到的请求包个数。

仿真的目标路由算法为：(1)基本的CCN路由[3]，不考虑节点副本的路由，记为BasicCCN；(2)邻居缓存探测策略NCE；(3)文献[7]提出的通告缓存副本的路由方式，记为ACC；(4)本文提出的快捷路由SCR，内容通告阈值φ=0.4，通告范围取节点到服务器的跳数。除了BasicCCN之外，假定其余4种方法中邻居缓存节点内容缺失时，直接将请求包转发到服务器获取内容。

6.1 用户请求平均时延

设置节点内容通告间隔为δ=4 s。在仿真过程中共产生2 000个内容请求，记节点从内容请求发出到收到所请求的数据的时延为单个请求时延，则所有内容请求的平均时延仿真结果如图6所示。

图6 用户请求平均时延

由图6可以看出，BasicCCN路由算法不考虑节点上内容副本的路由，导致时延最大。NCE和ACC都建立了到达邻居节点副本的路由表，但是不考虑邻居节点上内容的命中概率的差异性，请求被转发到的节点存在内容缺失的情况，导致这些请求的时延增加。相比之下，快捷路由考虑了缓存节点内容的命中概率，减少了缓存缺失导致重新获取内容的情况，所有请求的平均时延最小。与基本的CCN路由算法相比，在缓存容量从10增加到100时，当缓存容量为10时，相比BasicCCN，快捷路由减少了约9%的用户请求平均时延；当缓存容量为100时，可以得到，快捷路由比BasicCCN减少约17%的用户请求平均时延。

6.2 内容源服务器负载

取固定的缓存容量B=60、内容请求数Nq=2 000个、节点内容通告间隔为δ=4 s。以内容服务器收到的用户请求即兴趣包的个数作为其负载指标，则服务器负载性能的仿真结果如图7所示。

图7 内容源服务器负载

由图7可见，在总的内容请求数为2 0 00的情况下，BasicCCN只将请求路由到确定的服务器，因而不会产生额外的请求包，其他3种算法都会产生额外的请求包，这是因为考虑了缓存内容缺失导致重新产生请求包。在服务器收到的请求包数量上，BasicCCN最多，因为其只能利用转发路径上的部分缓存的内容，而ACE、NCE和快捷路由利用了缓存节点的副本资源，有效地减少了内容服务器的负载。快捷路由相对于BasicCCN，在服务器负载上减少了约43%。

6.3 内容通告比例对性能的影响

在快捷路由机制中，CCN网络中的缓存节点根据缓存内容的命中概率大小，将命中概率最高的比例为x(0＜x＜1)的内容向邻居节点进行通告，内容通告比例x的选取是一个需要考虑的问题。取缓存容量B=60，总的请求数Nq= 2 000个，节点内容通告间隔为δ=4 s。以内容通告比例x为变量对快捷路由时延性能进行仿真，结果如图8所示。

图8 内容通告比例对性能的影响

由图8可看出，随着内容通告比例x增加，用户请求平均时延减少。然而，当x＞0.8时，平均时延反而有所增加，这是因为缓存中的内容存在动态性，将部分命中概率低的内容通告出去，导致请求被转发到的节点内容已被淘汰，造成缓存缺失，重新从其他节点获取内容使得时延增加。

7 结束语

本文在CCN内容路由基础上，针对其无法利用节点缓存的内容副本的缺陷，在分析常用的LRU缓存策略的基础上，提出一种基于副本通告的快捷路由机制，以解决内容中心网络中内容副本的路由问题。下一步工作是将快捷路由应用到实际网络环境中进一步验证其性能。

[1] Jacobson V, Mosk o M, Smetters D, et al. Content-centric Networking[EB/OL]. (2007-02-18). http://w ww.ietf.org/proceedings/65/slides/DTNRG-12.pdf.

[2] Chiocchetti R, Rossi D, Rossini G, et al. Exploit the Known or Explore the Unknown?[C]//Proceedings of the 2nd Edition of the ICN Workshop on Infor mation-centric Networking. Helsinki, Finland: ACM Press, 2012: 7-12.

[3] Zhang Lixia, Estrin D, Burke J, et al. Named Data Networking Project[R]. PARC, Tech. Rep.: ndn-0001, 2010.

[4] Shanbhag S, Schwan N, Rimac I, et al. SoCCeR: Services over Content-centric Routing[C]//Proceedings of ACM SIGCOMM Workshop o n Information-centric Networking. T oronto, Canada: ACM Press, 2011: 62-67.

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

[6] Eum S, Nakauchi K, Murata M, et al. CATT: Potential Based Routing with Content Caching for ICN[C]//Proceedings of ACM SIGCOMM Workshop on Information-centric Networking. Helsinki, Finland: ACM Press, 2012: 49-54.

[7] Wang Yaogong, Lee K. Adv ertising Cached Contents in the Control Plane: Necessity and Feasibility[C]//Proceedings of 2012 I EEE Conference o n Computer Comm unications Workshops. Orlando, USA: [s. n.], 2012: 1045-1053.

[8] Sripanidkulchai K, Maggs B. Efficient Content Location Using Interest-based Locality in Peer-to-Peer Systems[C]// Proceedings of I EEE INFOCOM’03. Sa n Fran cisco, USA: [s. n.], 2003: 364-372.

[9] Pireddo L, Nascimento M A. Taxonomy-based Routing Indices for Peer-to-Peer Networks[C]//Proceedings of Workshop o n Peer-to-Peer Inf ormation Retrieva l. S heffield, UK: [s. n.], 2004: 321-328.

[10] Seung W, Ki Y, Jo ng S. LRU Based Sm all Latency First Replacement(SLFR) Algorithm for the Proxy Cache[C]// Proceedings of IEEE International Conference on Web Intelligence. Daejon, South Korea: [s. n.], 2003: 499-502.

[11] Fonsecaf R, Almeida V, Crovella M. Lo cality in a Web of Stream[J]. Communications of the ACM, 2003, 48(1): 82-88.

[12] Psaras I, Cle gg R G, Landa R, et al. Modeling and Evaluation of CCN-caching Trees[C]//Proceedings of the 10th International IFIP TC 6 Conference on Networking. Heidelberg, Germany: Springer, 2011: 78-91.

[13] 蔡青松, 李子木, 胡建平. Internet上的流媒体特性及用户访问行为研究[J]. 北京航空航天大学学报, 2005, 31(1): 25-30.

编辑 陆燕菲

Short-cut Routing Mechanism in Content Centric Network Based on Replicas Notification

LIU Tao, CHENG Dong-nian, TIAN Ming

(National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)

Content Centric Network(CCN) is a novel paradigm for content distribution with name-based routing. However, the basic CCN routing mechanism only creates routing entries to server c ontents and lacks routing to cache contents on nodes, leading to low cache resource utilization and large content access latency. To solve this problem, a Short-cut Routing(SCR) is presented, based on the notification of cache content replicas, which enables nodes to perceive neighbor’s cache information and retrieve contents from the best routing content source. Simulation results show that the SCR significantly reduces the average delay compared to the basic routing m echanism which does not take into account routing to cache contents, gives the cache capacity of the 60 content objects, and SCR reduces the server load by 43%.

Content Centric Network(CCN); Short-cut Routing(SCR); content activeness; Named Data Network(NDN); Markov chain; replicas

10.3969/j.issn.1000-3428.2014.05.014

国家“973”计划基金资助项目(2012CB315901)；国家“863”计划基金资助项目(2011AA01A101, 2011AA01A103)；国家科技支撑计划基金资助项目(2011BAH19B01)。

刘 涛(1985－)，男，硕士研究生，主研方向：宽带信息网络，网络体系结构；程东年，教授；田 铭，博士研究生。

2013-03-22

2013-05-15E-mail：liutaota168@163.com

1000-3428(2014)05-0062-06

A

TP393