命名数据网络中基于局部请求相似性的协作缓存路由机制

葛国栋郭云飞 刘彩霞 兰巨龙

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

命名数据网络中基于局部请求相似性的协作缓存路由机制

葛国栋*郭云飞 刘彩霞 兰巨龙

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

该文针对命名数据网络(Named Data Networking, NDN)应答内容的高效缓存和利用问题，依据内容请求分布的局域相似特征，提出一种协作缓存路由机制。缓存决策时，将垂直请求路径上的冗余消除和水平局域范围内的内容放置进行有效结合。垂直方向上，提出基于最大内容活跃因子的路径缓存策略，确定沿途转发对应的最大热点请求区域；水平方向上，采用一致性Hash协同缓存思想，实现应答内容的局域定向存储。路由查找时，将局域节点缓存引入到路由转发决策中，依据内容活跃等级动态执行局域缓存查找，增大内容请求就近响应概率。该机制减小了内容请求时延和缓存冗余，提高了缓存命中率，以少量额外的代价换取了内容请求开销的大幅下降，仿真结果验证了其有效性。

互联网；命名数据网络(NDN)；内容路由；缓存策略；请求相似性

1 引言

随着互联网技术与应用的飞速发展，“宽带化”、“内容化”与“个性化”已成为网络发展的主旋律，人们对于数据内容的需求日益强烈，网络应用的主体逐步向内容请求和信息服务演进转移[1]。据Cisco VNI Mobile Forecast预测，到2014年互联网上所有内容相关的流量将占据超过97.5%的份额[2]，传统以主机为中心的网络体系结构难以满足当前网络信息服务的发展要求。为此，信息中心网络(Information-Centric Networking, ICN)[1]作为一种革命式(clean-slate)的未来互联网设计思路，让数据内容本身成为网络通信的主体单元，将网络通信模式从关注“在哪”转变为关注“是什么”，即用户和应用通信的目的和意向，成为未来Internet设计的重要模式。其中，命名数据网络(Named Data Networking, NDN)[3]作为典型的ICN体系结构范例，在中间层用命名数据取代IP，数据传输采用“发布-请求-响应”模式，直接以内容名字进行路由，实现点到多点高效的内容分发。

在NDN的设计中，采用网络内在普遍缓存(in-network caching)的方式，在兴趣包(interest packet)沿途转发路径(on-path)的所有节点上缓存应答内容。在路由转发中，当节点收到兴趣包，依据内容名字依次在内容存储器(Content Store，CS)，未决请求表(Pending Interest Table, PIT)和转发信息库(Forwarding Information Base, FIB)中进行匹配查询。应答数据包(data packet)携带请求内容，依据节点PIT表项记录，沿相同路径进行反向的逐跳传输。但是，由于NDN泛滥式的沿途全部缓存方式(Cache Everything Everywhere, CE2)，应答内容在沿途转发路径上所有节点都将进行存储，致使节点缓存内容趋于同质化，导致大量的缓存冗余。在路由查找中，只针对持久稳定的内容源建立了路由条目，并没有考虑局域节点的暂态缓存，致使传输路径以外(off-path)大量的就近缓存资源无法加以利用。

文献[4]对缓存资源利用的必要性和可行性进行了分析，指出在控制平面的路由决策中，必须结合节点暂态缓存；文献[5]对现有缓存方案进行了对比分析，指出缓存算法的设计缺乏对于内容请求分布特征的考虑；文献[6]指出，现有典型的缓存策略，包括随机缓存[7]，概率缓存[8]，最大介数缓存[9]等，在存储决策时，只设计了垂直请求路径上的内容放置和冗余消除，缺乏对于局域水平范围的考虑；文献[10]提出了一种综合使用节点介数和内容更替率的缓存策略，避免重要节点处于高频率的内容替换状态；文献[7]提出了一种基于势能的目标识别路由方法(CATT)，将节点缓存内容进行局部范围通告，实现缓存资源的可用性；文献[11]提出了一种基于Hash协同的域内缓存策略，边缘路由节点通过Hash运算，确定内容的存储位置和转发路径；以上方案存在的不足主要包括：(1)缓存算法的设计缺乏对于内容请求分布特征的考虑；(2)内容放置时，只设计了垂直请求路径上的冗余消除策略，缺乏与水平局域范围内缓存放置的有效结合；(3)路由查找缺乏对传输路径以外缓存资源的考虑，无法有效利用局域节点的缓存内容。

为此，结合内容请求的局域分布特征，在NDN中提出了一种协作缓存路由机制(Collaborative Caching and Routing Scheme, CCRS)。通过构建局域的内容请求相似性社区，在垂直和水平2维空间下，联合进行冗余消除和缓存策略设计。路由转发时，将节点缓存因素引入到路由决策中，动态执行局域缓存查找，增大缓存命中率和就近响应概率。

2 协作缓存路由机制(CCRS)

CCRS从内容请求的局域相似性特征出发，首先构建了基于内容活跃因子的请求相似性社区(Content Similarity Community, CSC)。进而，依据CSC对内容对象的整体需求程度，将应答内容存储在沿途转发路径活跃度最高的热点请求CSC内，增大缓存内容驻留概率；在CSC内，采用一致性Hash协同缓存策略，定向缓存应答内容，减小相同内容的重复冗余存储。在内容请求时，CCRS不仅可以利用沿途转发路径节点上的缓存内容，通过执行局域缓存查找，对于所属CSC内的局域缓存资源也可加以利用。

2.1 内容请求相似性社区构建

2.1.1 内容活跃因子定义 内容请求在时间维度上具有动态可变特征[12]，即内容的流行程度在不同的时间段内会表现出不同程度的差异性。为了体现内容请求的动态变化特征，减小“冷门”资源的偶然访问对于请求分布造成的影响，兼顾内容对象历史请求的“热度”和当前时刻的“新颖度”，提出了内容活跃因子ρC(t,v)。

定义1 内容活跃因子ρC(t,v)。ρC(t,v)是内容活跃程度的度量指标，用于表征在特定时刻t，缓存节点v上，内容对象C被请求的活跃程度。

以时间间隔T对节点v上内容对象C的访问次数进行统计，请求速率的统计时间窗口宽度为WKT, k为滑动窗口的宽度，T为统计间隔时间，[nT, t], [(n-1)T, nT],…,[(n-k)T, (n-k+1)T]表示时间间隔序列，Sn, Sn-1,…,Sn-k为T中C的请求次数，λn,λn-1,…,λn-k为对应的请求频率。对于节点v，内容对象C在时刻t，对应的内容活跃因子ρC(t,v)为

其中，αi,i=n-1, … ,n-k , 0＜αi＜1，为历史请求频率的权值，表征了前k个时间序列对于当前时刻内容活跃程度的影响，反映了ρC(t,v)与历史请求“热度”的关联关系。αn表征了ρC(t,v)受当前时刻请求频度的影响程度，反映了内容对象访问的“新颖度”，图1给出了ρC(t,v)的具体图示。

2.1.2 内容相似性度量 内容请求分布在空间上具有很大程度的局域相似性[13]，处于局部区域的用户更倾向于关注和请求相同的内容和信息。为此，提出NDN网络内容请求相似性社区CSC，用于描述具有相似性内容请求的节点集合。

图1 内容活跃因子ρC(t,v)

定义2 内容请求相似性系数(Similarity Coefficient, SC): SC用于表示节点间内容请求的相似性程度。

以时间间隔T对节点v上内容请求进行统计分析，Ct(v)={c1,c2,…,cm}为内容请求条目列表，ρt(v)={ρC1(t,v),ρC2(t,v),…,ρCm(t,v )}为对应的内容活跃因子集合。时刻t，节点i与j之间的SC为

其中，∀ i, j, 0≤SC≤1, SC(i,j)=SC(j,i )。Ct(i)∩Ct(j)表示节点i, j之间内容请求的相同部分，Ct(i)∪Ct(j)表示内容请求对象的总和，ρC(t,i), ρC(t,j)分别为对应的内容活跃因子。节点间请求的内容条目越相似，对应的内容活跃因子越高，相应的SC取值越大。

定义3 相似性聚合度θ：用于表征CSC内节点间SC的聚合程度。即：对于CSC内任意相邻节点i, j，满足SC(i,j)≥θ。θ取值越大，对应CSC的内容请求相似性程度越高。

定义4 社区内容活跃度(Community Content Activity, CCA)：用于表示在整个CSC内，特定内容被请求的频度。社区内容活跃度CCA为

CCA(c)是特定内容c在CSC中所有请求节点上的局部活跃因子之和，衡量了整个社区对于该内容的整体需求程度，体现了请求内容在CSC内的全局活跃程度。

2.1.3 局域相似性社区计算 为了计算和确定CSC结构和对应的节点集合，在NDN中，设计了CSC相似性通告报文(Similarity Advertisement Packet, SAP)，具体报文格式如图2所示。其中，Type字段表示报文类型，Nonce字段为随机数，Time Stamp用来记录报文发送时间。Node Identifier为缓存节点标识，Ct(v)=(c1,c2,…,cm), ρt(v)={ρC1(t,v),ρC2(t, v),…,(t,v )}分别为内容请求条目列表和内容活跃因子集合。

图2 CSC内容请求相似性通告报文(SAP)

以θ作为CSC的相似性聚合指标，构造内容请求相似性社区。节点向其邻居节点发送SAP报文，依据SAP消息携带的Ct(v)和ρt(v)的大小，计算对应SC取值。当SC(i,j)≥θ，在节点间添加相似性属性连接关系sij=1，否则sij=0。如果SC(i,j)≥θ，节点将接收到的SAP报文继续下行转发。否则，直接丢弃，终止报文发送。最终，节点将接收到所有具有连续相似性属性关系节点的SAP报文，确定所属CSC对应的节点集合Vθ。CSC构建算法的具体步骤如下，其中，CGT为局部缓存指引表项，用于确定目标缓存节点的下一跳转发接口。

(1)计算内容请求条目列表Ct(v)={c1,c2,…,cm}和活跃因子集合ρt(v)={ρC1(t,v),ρC2(t,v),…,ρCm(t,v )}；

(2)在SAP报文中添加节点对应的Ct(v)和ρt(v )信息，向其邻居节点发送SAP相似性通告，进行内容请求信息的局部交互；

(3)当邻居节点接收到SAP报文后，提取Ct(v)和ρt(v)属性内容，计算节点间对应的SC取值，并记录节点标识和对应的到达接口，用于建立局部CGT；

(4)依据θ与SC取值大小关系，确定相似性属性连接关系。当SC(i,j)≥θ时，sij=1，否则，sij=0；

(5)若SC≥θ，上游节点将其接收的SAP报文继续向下游节点转发通告；

(6)若SC＜θ，上游节点直接丢弃接收到的SAP报文，终止SAP转发通告；

(7)节点依据接收到的SAP报文，确定所属CSC的节点集合Vθ，计算CSC对应的CGT；

(8)依据各节点局部的Ct(v)和ρt(v)属性内容，确定CSC对应的内容请求条目列表C(CSC)，计算对应的全局内容活跃度集合CCA(CSC)。

2.2 基于CSC的缓存策略

垂直方向上，依据CSC对内容的整体需求程度，将请求内容存储在沿途转发路径活跃度(CCA)最高的热点请求CSC内，使内容请求尽可能在本地CSC内得到就近应答；水平方向上，在CSC内，采用一致性Hash协同的缓存思想，定向缓存应答内容，增大CSC局域缓存资源的多样性。

2.2.1 路径缓存策略 路径缓存策略需要确定应答内容存储的目标CSC社区，减小垂直方向上内容的重复冗余存储。在兴趣包和数据包中添加CCA字段，用于记录和匹配兴趣包沿途CSC对应的活度信息。

(1)内容请求过程：内容请求者vc发送内容请求，节点接收到兴趣包后，如果CS已经缓存了该内容，则直接进行响应。若CS和PIT中没有对应的请求内容和接口信息，则判断是否要执行CSC局域缓存查找(依据2.3.1节)。若条件成立，在CSC内执行局域缓存查找。否则，在兴趣包中添加CSC对应的内容活跃度CCA(c)，依据FIB表项信息进行下一跳路由转发。通过兴趣包逐跳的上行传输，依次记录和添加沿途CSC对应的CCA(c)。每当兴趣包转发到下一个CSC时，所属节点将相邻CSC对应的CCA(c)取值大小进行比较，将CCA(c)更新为已有社区中的最大值。最终，当兴趣包到达内容提供者vp后，CCA(c)记录的就是内容c沿途最大热点请求区域对应的内容活跃度maxCCA(c)。

(2)数据应答过程：当vp发送数据包进行反向应答时，将上行兴趣包中携带的maxCCA(c)添加到数据包的CCA(c)选项中，并依次比对反向传输路径节点对应的活跃度信息，匹配目标CSC。进而，在该CSC内执行局域缓存操作，将内容c存储在对应的CSC目标节点上，实现请求内容的热点区域缓存。

2.2.2 Hash协同缓存策略 当数据包到达目标CSC后，同时执行以下两种操作：(1)正常的数据转发。节点依据PIT表项，向请求者发送应答内容；(2)局域定向缓存。节点执行一致性Hash运算，计算该内容的目标缓存节点nc：

其中，输入为内容对象名字，目标空间为所属CSC的节点集合Vθ，输出为nc。在数据包中添加nc的节点标识，构造缓存数据报文(Caching Data Packet, CDP)，其格式与数据包消息类似，只是将CCA字段替换为目标缓存节点标识。然后，节点依据缓存指引表项CGT，确定下一跳转发接口，将CDP报文发送到nc。nc接收到CDP报文后，提取数据内容并在CS中进行存储。在CSC中，对于同一请求内容，只存储在目标缓存节点上，避免相同内容的重复冗余存储，增大CSC缓存内容的多样性。

2.3 缓存查找和路由转发

2.3.1 局域缓存查找 当CS和PIT表项中没有对应的请求内容和接口信息时，节点需要确定是否执行CSC内的局域缓存查找。如果对于沿途传输的所有CSC都执行局域的缓存资源查找操作，将会引入多个额外的查找时延。对于CSC来说，CCA描述了CSC对于请求内容的整体需求程度。对于特定的请求内容，如果该内容不处于对应的内容请求条目列表中，说明CSC对于该内容请求的频度很小，需求程度很低。那么，依据路径缓存策略，此内容在该CSC内存储的概率将很小，如果执行缓存查找，将存在很大程度的内容缺失。为此，定义局域缓存查找区间CQ(CSC)，节点只对CSC对应的流行资源进行局域缓存查找，减小额外引入的查找时延。为前m项流行内容，m取值由式(5)确定：

其中，δ(0≤δ≤1)为累积活跃阈值，表示前m项内容请求的累加概率。例如，当δ=0.8时，即表示对于前m项内容的请求概率占据了全部内容请求的80%。当内容对象总数为2000, Zipf指数α取值1.0和1.2时，累加请求概率为0.8包含的内容对象，即m取值分别为390项和99项。

2.3.2 动态路由转发 当节点接收到兴趣包后，首先查找CS中是否已存储了该请求内容c，若匹配成功，直接发送数据包进行响应。否则，查找PIT表项，若已包含该内容的请求条目，直接添加到达接口信息；否则，在PIT中增加该内容对应的请求条目，然后查看请求内容是否位于局域缓存查找区间CQ(CSC): (1)如果c∈CQ(CSC)，执行一致性Hash运算，确定目标缓存节点nc，依据CSC的缓存指引表项，进行局域缓存资源查找。若nc含有该请求内容，则直接命中，进行局部应答。否则，依据FIB表项，进行内容请求的前向转发；(2)如果c∉CQ(CSC)，无需执行局域缓存查找，直接依据FIB表项，进行内容请求的下一跳转发。表1给出了CCRS的整体流程，包括内容请求和数据应答两个部分。

表1 基于局域请求相似性的协作缓存路由机制

3 仿真与性能分析

3.1 仿真环境与参数设置

采用ndnSIM[14]进行仿真与性能分析，该工具对于NDN的基本数据单元结构和路由转发流程均已实现，并提供了开放源码和运行实例。在GT-ITM下采用Locality模型生成50个路由节点的平面随机网络拓扑。网络中内容对象总数N为10000个，大小设为10 kByte。节点缓存容量一致，CS设为100，链路带宽100 Mbps。在网络中设置2个内容服务器，负责内容对象的存储和发布，各服务器随机存储5000个内容，并在网络边缘节点中随机选取2个节点与内容服务器直接相连。其余节点均作为用户接入节点，发布内容请求，内容请求到达服从λ=50个/s的泊松过程[9]，请求概率服从Zipf分布[8]，第i个内容的请求概率为：。依据文献[15]的构造方法模拟内容请求分布的局域相似特征，首先依据节点度的大小，构造不同中心节点内容请求的差异化分布，其余节点的请求分布依据路由跳数与就近的中心节点保持一致，并依据与中心节点的距离进行局部的差异化调整。仿真时间设为200 s，统计间隔δ=0.8，初始节点缓存状态为空，缓存替换策略采用最近最少使用策略LRU。

3.2 性能分析

将CCRS与NDN[3], Betw[9]和Hash-Mu[11]进行对比分析，性能评价指标包括：平均请求时延(Average Request Delay, ARD)，缓存命中率(Cache Hit Ratio, CHR)，局部响应率(Local Response Ratio, LRR)和额外开销对比。

3.2.1 平均请求时延 平均请求时延ARD：节点发送请求兴趣包到接收到应答数据包之间的平均延迟。图3给出了α=1.2, θ=0.7时，4种方案的ARD对比，采样间隔T=2 s。仿真初始阶段，由于网络中所有节点存储状态为空，发送的兴趣包请求都需要转发至内容源服务器进行响应，ARD较大。但随着请求内容的不断存储，缓存内容的响应概率逐渐增加，ARD随之减小。

NDN采用泛滥式的CE2存储方式，将会引起高频率的缓存替换更新，导致内容缺失概率增大，对应的ARD最大；Betw通过在介数最大的重要节点上缓存内容，提高内容副本的后续利用率，但该方案仅仅考虑了垂直请求路径上的缓存放置，且对于传输路径以外的局部缓存资源无法进行感知利用；Hash-Mu虽然消除了域内相同内容的冗余缓存，但是基于Hash计算目标缓存节点，无法实现应答内容的优化存储；CCRS在应答内容存储时，综合考虑垂直和水平方向上的冗余消除，将CSC整体需求程度最大的活跃内容定向存储在对应的目标缓存节点上。内容请求时，实现了沿途所属CSC内就近缓存资源的有效利用，减小了内容请求时延，ARD是各方案中最小的。

3.2.2 缓存命中率 缓存命中率CHR：网络中节点缓存内容响应兴趣包请求的概率。图4给出了α=1.2, θ=0.7和α=1.5, θ=0.8时，各方案的CHR对比。随着α取值增加，内容请求的集中性和局域性不断加强，流行缓存资源的驻留概率和命中率不断增大，各方案对应的CHR都得到了相应的提高。对于NDN和Betw，在应答内容存储时，没有考虑不同请求内容流行等级的差异性，而且对于沿途附近存在的内容副本无法加以利用，CHR明显小于CCRS方案。对于Hash-Mu，域内所有节点整体协作，实现应答内容的协同缓存，虽然无法实现内容的优化存储，但提升了域内缓存内容的命中率；在CCRS中，将节点有限的存储空间用于缓存CSC整体需求程度最高的活跃请求内容，增大了缓存内容的驻留概率和利用率。同时，通过局域缓存查找，充分利用了沿途所属CSC内的局部缓存资源，CHR分别达到了0.481和0.622。

3.2.3 局部响应率 局部响应率LRR：内容请求在首跳发送节点和第1跳转发节点上响应的概率。LRR反映了内容请求在局部范围内的就近响应率。图5给出了在α=1.2, θ=0.7时，各方案的LRR对比。CCRS将应答内容存储在沿途请求活跃程度最大的热点CSC中，增加了缓存内容在本地的驻留概率和命中率，首跳节点缓存命中率达到了0.210。当首跳节点缓存缺失时，通过执行所属CSC缓存资源的局域查找，一跳转发节点的缓存命中率为0.161，明显大于其他方案，LRR达到了0.371，是4种方案中最大的。对于Hash-Mu，虽然其增大了域内缓存内容命中率CHR，但是由于其随机化的选择内容存储位置，对于LRR提升并不明显，只达到0.102和0.096。

3.2.4 代价开销对比 相比NDN, Betw和Hash-Mu, CCRS为了实现应答内容的合理放置和有效利用，引入了额外的开销来换取内容请求性能的提升。其中，额外开销主要包括：相似性通告和节点存储开销，下面进行定量分析。

(1)相似性通告开销(CA)：在CSC建立时，相似性通告报文(SAP)交互引入的开销，定义为SAP与其传输距离(路由跳数)的乘积，大小取决于报文长度、通告频率和路由传输跳数，代价单位取bit·hop。单位时间内相似性通告开销CA为

图3 平均请求时延ARD对比

图4 缓存命中率CHR对比图

图5 局部响应率LRR对比

其中，fSAP为SAP通告频率，SSAP为报文长度，d1为首跳邻居通告跳数。当邻居节点接收到SAP后，计算SC取值，如果SC≥θ，节点将SAP继续进行转发通告，d2为第2跳路由传输跳数。否则，直接丢弃，终止报文发送。

(2)节点存储开销(CC)：在CCRS中，节点需要记录内容请求条目列表Ct(v)和对应的内容活跃因子集合ρt(v)。当节点交互SAP报文后，需要存储局域缓存指引表项CGT和对应的缓存查找区间CQ(CSC)。额外CC大小取决于所存储的内容名字、接口和活跃因子的数量和长度，代价单位为bit。

其中，Lc, Lρ, Lf和Li分别为内容名字、活跃因子、接口和节点标识的长度，l, m, n为对应的存储数量。

(3)内容请求开销(CR)：定义为内容请求过程中，兴趣包(interest packet)和数据包(data packet)分别与其传输距离的乘积之和，大小主要取决于内容请求过程传输的路由跳数，代价单位取bit·hop。

其中，SInt, SDat分别表示内容请求和数据应答报文长度，d为对应的路由传输跳数。

表2给出了α=1.2，各方案的代价开销对比。其中，CCRS的SAP通告间隔设为2 s。在NDN和Betw中，没有相应的局域缓存内容发现机制，不会产生额外的报文通告开销CA和存储开销CC。但是，在内容请求时，由于无法利用局域就近的缓存资源，对应的CR最大。Hash-Mu提升了域内节点缓存内容的命中率，但是，基于Hash随机计算存储位置的方式，无法实现应答内容的优化存储；在CCRS中，将局域缓存因素引入到路由决策中，动态执行局域缓存查找和应答内容定向存储，相比其他方案，虽然引入了额外的CA和CC，但有效地减小了内容请求开销CR。CCRS通过小量额外CA, CC的付出，增大了内容请求的局部响应率LRR，换取了CR的大幅下降。表3给出在α=1.5，各方案代价开销对比。

表2 代价开销对比(α=1.2)

表3 代价开销对比(α=1.5)

3.3 适应性讨论

图6分别给出了在相似性聚合度θ取值为0.6, 0.7和0.8下，ARD随Zipf指数α的变化趋势。当α取值较小时，内容请求不能有效集中，在α取值为0.2和0.4时，最大流行内容对应的请求概率仅为0.0005和0.0024，节点间内容请求相似性较低，无法形成局域的CSC社区。随着α取值增大，内容请求的集中性和局域性不断加强，在聚合度θ=0.6时，首先形成CSC社区，内容请求局域响应概率增大，ARD显著下降。但是，随着α进一步增大，少数流行资源包含的内容对象已无显著变化，加之CSC的局域性，ARD下降趋势逐渐减缓。在不同的θ取值下，CCRS可以有效降低ARD, θ取值越大，CSC内容请求相似性程度越高，对应的ARD越小。

图7给出了在α=1.2, θ=0.7时，ARD随节点缓存容量变化的趋势。随着节点缓存容量的不断增加，更多的请求内容可以被存储在中间节点上，提高了缓存命中率CHR，各方案对应的ARD不断减小。当节点缓存空间较小时，CCRS依据CSC内容请求的流行等级，将节点有限的存储空间用于缓存CSC整体需求程度最高的活跃请求内容，减小相同内容副本的重复存储。CCRS可以有效利用节点有限的缓存空间，对于缓存容量的变化具有良好的适应性。

4 结束语

内容的普遍缓存是NDN的核心特征，而合理的内容放置和缓存查找是其性能有效发挥的保证。本文依据内容请求的局域分布特征，在NDN中提出了一种协作缓存路由机制。CCRS综合考虑了垂直请求路径和水平局域范围2维空间下的内容放置和冗余消除，基于最大内容活跃因子确定沿途转发路径对应的最大热点请求区域，采用一致性Hash协同缓存思想，实现应答内容CSC内的局域定向缓存，仿真结果和对比分析显示其有效性。后续研究工作包括：(1)如何将CCRS扩展到移动ICN环境中，设计相应的内容存储和查找机制；(2)在不同网络和仿真参数条件下，对于CCRS性能和开销进行进一步分析验证。

图6 ARD随Zipf指数α的变化趋势

图7 ARD随缓存容量的变化趋势

[1] Xylomenos G, Ververidis C, Siris V, et al.. A survey of information-centric networking research[J]. IEEE Communications Surveys & Tutorials, 2014, 16(2): 1024-1049.

[2] Cisco. Cisco Visual Networking Index (VNI): forecast and methodology, 2011-2016[OL]. http://www.cisco.com, 2012.

[3] Jacobson V, Smetters D K, Thornton J D, et al.. Networking named content[J]. Communications of the ACM, 2012, 55(1): 117-124.

[4] Wang Y G, Lee K, Venkataraman B, et al.. Advertising cached contents in the control plane: necessity and feasibility[C]. IEEE Conference on Computer Communications Workshops, Orlando, USA, 2012: 286-291.

[5] Zhang G Q, Li Y, and Lin T. Caching in information centric networking: a survey[J]. Computer Networks, 2013, 57(16): 3128-3141.

[6] Wang J M, Zhang J, and Bensaou B. Intra-AS cooperative caching for content-centric networks[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 61-66.

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

[8] Psaras I, Chai W K, and Pavlou G. Probabilistic in-network caching for information-centric networks[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Helsinki, Finland, 2012: 55-60.

[9] Chai W K, He D, Psaras I, et al.. Cache “less for more” ininformation-centric networks[C]. Proceedings of IFIP Networking, Prague, Czech, 2012: 27-40.

[10] 崔现东, 刘江, 黄韬, 等. 基于节点介数和替换率的内容中心网络网内缓存策略[J]. 电子与信息学报, 2014, 36(1): 1-7. Cui Xian-dong, Liu Jiang, Huang Tao, et al.. A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J]. Journal of Electronics & Information Technology, 2014, 36(1): 1-7.

[11] Saino L, Psaras I, and Pavlou G. Hash-routing schemes for information centric networking[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 27-32.

[12] Wang J M and Bensaou B. Progressive Caching in CCN[C]. IEEE GLOBECOM, Anaheim, USA, 2012: 2727-2732.

[13] 刘外喜, 余顺争, 蔡君, 等. ICN 中的一种协作缓存机制[J].软件学报, 2013, 24(8): 1947-1962. Liu Wai-xi, Yu Shun-zheng, Cai Jun, et al.. Scheme for cooperative caching in ICN[J]. Journal of Software, 2013, 24(8): 1947-1962.

[14] NS-3 based Named Data Networking (NDN) simulator[OL]. http://ndnsim.net, 2013.

[15] Zhang Y, Zhao J, Cao G H, et al.. On interest locality in content-based routing for large-scale MANETs[C]. IEEE 6th International Conference on Mobile Ad hoc and Sensor system, Macau, China, 2009: 178-187.

葛国栋： 男，1985年生，博士生，研究方向为新型网络体系结构设计、内容中心网络.

郭云飞： 男，1963年生，硕士，教授，博士生导师，研究方向为新型网络体系结构设计、移动互联网.

刘彩霞： 女，1974年生，博士，副教授，硕士生导师，研究方向为内容中心网络、移动互联网.

兰巨龙： 男，1962年生，博士，教授, 博士生导师，研究方向为可重构柔性网络和高性能路由.

Collaborative Caching and Routing Scheme Based on Local Request Similarity in Named Data Networking

Ge Guo-dong Guo Yun-fei Liu Cai-xia Lan Ju-long
(National Digital Switching System Engineering & Technological R &D Center, Zhengzhou 450002, China)

How to efficiently cache and take advantage of largely distributed copies poses challenges to the retrieval process of Named Data Networking (NDN). On the basis of similarity in local request, a collaborative caching and routing scheme is proposed. In the scheme, redundancy elimination in vertical requesting path and collaborative cache in horizontal local scope are effectively combined on the caching decision-making. In the vertical direction, the similar community which has the highest active value along the content delivery path is calculated based on the path caching strategy. In the horizontal direction, consistent Hash-caching is implemented to fulfill the oriented cache for the requested data in the vicinity. When a retrieve is requested, the proposed scheme dynamically performs the local lookup according to the content popularity by introduction of the local cache factor into the routing process. The simulation results show that the scheme can decrease the request latency, reduce the cache redundancy, and achieve higher cache hit ratio by comparison with existing methods.

Internet; Named Date Networking (NDN); Content-based routing; Caching strategy; Request similarity

TP393

A

1009-5896(2015)02-0435-08

10.11999/JEIT140246

2014-02-26收到，2014-05-30改回

国家973计划项目(2012CB315901)，国家自然科学基金(61372121)和国家863计划项目(2011AA01A103)资助课题

*通信作者：葛国栋 ggd@mail.ndsc.com.cn