命名数据网络中基于内容请求相关性的协作缓存算法

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



命名数据网络中基于内容请求相关性的协作缓存算法

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

①(国家数字交换系统工程技术研究中心 郑州 450002)②(解放军理工大学 南京 210007)

针对命名数据网络(Named Data Networking, NDN)存储空间的有效利用和应答内容的高效缓存问题，该文采用“差异化缓存”的方式，提出一种依据内容请求序列相关性的协作缓存算法。在内容请求中，预先发送对于后续相关数据单元的并行预测请求，增大内容请求的就近响应概率；缓存决策时，提出联合空间存储位置与缓存驻留时间的2维差异化缓存策略。根据内容活跃度的变化趋势，空间维度上逐跳推进内容存储位置，时间维度上动态调整内容缓存时间，以渐进式的方式将真正流行的请求内容推送至网络边缘存储。该算法减小了内容请求时延和缓存冗余，提高了缓存命中率，仿真结果验证了其有效性。

互联网；命名数据网络(NDN)；协作缓存；请求相关性；内容路由

1 引言

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

在NDN的设计中，采用网络内在普遍缓存(in-network caching)的方式，在兴趣包(interest packet)沿途转发路径(on-path)的所有节点上缓存应答内容。在路由转发中，当节点收到兴趣包，依据内容名字依次在内容存储器(Content Store, CS)，未决请求表(Pending Interest Table, PIT)和转发信息库(Forwarding Information Base, FIB)中进行匹配查询。应答数据包(data packet)携带请求内容，依据节点PIT表项的记录，沿相同路径进行反向的逐跳传输。

文献[3]指出，对于NDN网络，合理的内容放置和缓存决策，是有效发挥网络性能的关键因素。但由于NDN泛滥式的沿途全部缓存方式(Cache Everything Everywhere, CE2)，致使节点缓存内容趋于同质化，导致大量的缓存冗余。而且，在缓存决策时，缺乏对于内容本身差异化特征的考虑，无法实现内容的优化存储。为此，为了有效发挥内容普遍缓存的优势，高效缓存算法的设计就成为NDN需要解决的关键问题。

2 问题分析

文献[4]提出了一种随机单点缓存策略(RCOne)，在沿途路径上随机选择单个节点进行内容存储，减小缓存冗余。但该方案没有考虑不同请求内容流行程度的差异性；文献[5]提出只在缓存命中节点的直接下一跳存储应答内容(LCD)，避免内容的重复缓存；文献[6]提出了基于节点介数的缓存方案(betw)，通过在沿途传输路径介数最大的节点上缓存内容，以提高后续利用率。但该方案将导致少数重要节点上的缓存频繁替换；文献[7]设计了基于概率的缓存方式(probabilistic cache)，依据节点距离数据源的距离和路径的剩余存储能力，计算节点对应的缓存概率；文献[8]提出了缓存年龄的思想(age)，依据内容流行等级和存储节点的位置来计算缓存年龄。但是该算法中假设内容流行度是已知的静态参量，无法体现内容请求的动态变化特性，而且该参数难以预先获取；文献[9]提出了一种基于内容流行等级的协作缓存策略(WAVE)，依据内容的请求次数，以指数增长方式逐步增加沿途缓存的数据个数。但是该方案并没有考虑内容请求序列的相关性，而且只实现了空间存储位置上的差异化缓存；文献[10]对现有缓存方案进行了对比分析，指出缓存算法的设计缺乏对于内容请求分布特征的考虑，并给出下一步的研究方向。

以上方案存在的不足之处主要体现在：(1)在差异化缓存设计时，对于不同内容的存储位置和缓存驻留时间缺乏综合考虑和有效结合；(2)缓存决策没有结合内容请求序列的分布特征。缓存算法设计时，多数基于独立请求模式(Independent Reference Model, IRM)进行研究[10]，内容请求概率由流行度分布函数预先给定，无法体现请求分布的动态变化和相关性特征[10, 11]。针对上述不足，在NDN中本文提出了一种基于内容请求相关性的协作缓存算法(Collaborative Caching Algorithm based on Request Correlation, CCARC)。CCARC根据内容请求序列间的相关性特征，主动发送对于关联数据单元的并行预测请求；在缓存决策时，从差异化缓存思想出发，根据内容活跃度的变化趋势，逐步推进内容存储位置，以渐进式的方式将流行资源推送至网络边缘节点存储。

3 基于内容请求相关性的协作缓存算法

CCARC属于一种隐式的轻量级协作缓存算法，节点以分布式的方式独立地执行缓存决策，不会引入额外的交互报文的发送与通告，也避免了中心化决策实体的引入。同时，内容的流行程度根据实际请求次数来动态确定，不依赖预先的参数假设。CCARC主要思想包括两个方面：(1)基于内容请求相关性的并行预测请求；(2)缓存位置和驻留时间的2维差异化存储。

3.1 报文交互与参数定义

为了区分基于相关性预测发起的请求和应答数据，分别设计了相关兴趣包(Correlated Interest packet, CIP)和相关数据包(Correlated Data Packet, CDP)报文，其具体格式与NDN中的兴趣包和数据包相同，只是CIP和CDP用于标识节点基于请求相关性而发出的交互报文，用于执行下一相关数据单元(chunk)的预测请求。在数据包和CDP报文中，添加缓存指示(Cache Indication, CI)和内容活跃度(Content Activity, CA)字段。其中，CI用于缓存节点指示下游节点执行应答内容的存储，CA表示该内容对应的流行程度，用于存储位置和缓存时间(Caching Time, CT)的计算，图1给出了具体报文格式。

图1 (相关)兴趣和(相关)数据报文格式

图2 内容活跃度CA

3.2 算法执行流程

3.2.1缓存存储决策 节点依据接收到的报文格式和内容活跃度CA的变化趋势，动态地确定内容存储位置，计算、更新缓存时间。具体执行以下3种策略：

3.3 算法运行实例

图3给出了CCARC算法具体执行实例。假设内容包括7个chunk(1~7)，存储于内容源服务器(Original Content Server, OCS)。终端用户1~4为内容请求者，A, B, C, D均为内容路由器(Content Router, C-Router)，实线方框表示正常的数据缓存单元，虚线方框代表临时存储的数据单元。

(1)1发送对前5项数据块(1~5)的请求(图3(a))：由于沿途路径不存在对应的缓存资源，兴趣包请求需要路由至OCS进行响应。当OCS接收到内容请求后，发送数据包进行应答，并将缓存指示标志CI位置为1，指示下游路由器缓存该应答内容；当C-Router A接收到数据包后，查看CI标志和CA字段，计算缓存存储时间CT，将内容在其CS中进行存储，并重置CI为0，继续向下转发应答数据包。当B, C和D接收到数据包后，由于CI标志位为0，直接进行报文转发，无需进行数据缓存；

图3 CCARC算法执行过程

(2)2发送对前3项数据内容(1~3)的请求(图3(b1))：在首次请求中，由于1~5在路由器A处已经进行了缓存，节点A直接发送1~3对应的数据包进行应答，将CI置为1，指示下行路由器B缓存该应答内容。1~3将推送至节点B处进行存储；假设在该次请求中(图3(b2)),3对应的内容活跃度CA降低，那么对应的数据包中CI将设置为0，缓存位置将不会向下(节点B)推进，直接在节点A处依据当前CA重新计算缓存时间CT；

(3)3发送对前4项数据块(1~4)的请求(图3(c))：由于沿途缓存资源的存在，1~3对应的兴趣包将在B处得到响应，并在C处依次进行缓存。当节点B进行3的应答时，同时发送CIP报文，执行对于数据块4的相关性预测请求。当上游节点A接收到CIP后，发送CDP进行应答。当节点B接收到4的CDP应答报文后，提取内容并进行临时存储(虚线方框)。当C-Router B接收到用户发送的4请求兴趣包后，该内容将被节点正式缓存(实线方框)，并依据CA重新计算缓存时间CT。当5在节点B进行临时缓存后，由于用户没有发起对于该内容的请求，该内容短时间内将会被替换淘汰。

CCARC算法的整体流程示于表1，划分为内容请求和数据应答两个过程。

4 仿真与性能分析

4.1 仿真环境与参数设置

表1 CCARC算法的整体流程

4.2 性能分析

将CCARC与文献[2] NDN，文献[4]RCOne和文献[9] WAVE进行对比分析，评价指标包括：平均请求时延(Average Request Delay, ARD)，缓存命中率(Cache Hit Ratio, CHR)，平均路由跳数(Average Route Hop, ARH)。

由于NDN的CE2泛滥式缓存方式，节点的同质化缓存将会导致高频率的内容替换更新，降低了沿途缓存资源的响应率，对应的ARD最大；RCOne在沿途路径上以固定概率随机选择单个节点进行内容存储，但该方案没有考虑不同请求内容流行程度的差异性，固定的缓存概率无法实现内容的优化存储；WAVE依据内容的请求次数，以指数增长方式不断增加传输路径缓存数据个数。但是该方案并没有考虑内容请求分布的相关性特征。相比其他方案，CCARC对于不同请求内容，执行差异化缓存。依据内容活跃度的变化趋势，计算内容存储位置，动态调整内容缓存时间，增大了流行资源驻留概率和命中率。同时，依据内容请求序列的强相关性，主动发送对于关联内容的预测请求，有效减小内容请求时延(约37%)。

图4 平均请求时延ARD对比

图5 缓存命中率CHR对比

4.3 适应性讨论

5 结束语

内容的普遍缓存是NDN网络的核心特征，而合理的内容放置和缓存策略是其性能有效发挥的保证。本文针对现有缓存算法的不足，结合内容请求分布的相关性特征，从差异化缓存的思想出发，在NDN中提出了一种依据内容请求序列相关性的协作缓存算法。在内容请求过程中，节点主动发送对于下一个相关数据单元的预测请求，增大后续内容请求的就近应答；在缓存决策时，逐跳推进内容存储位置，动态调整缓存驻留时间，实现不同内容的差异化存储。后续研究工作包括：(1)如何将CCARC缓存算法扩展到多数据源和多路径模式下；(2)在不同网络和仿真参数条件下对于CCARC性能进一步分析验证。

图6 平均路由跳数ARH对比

图7 平均请求时延ARD随Zipf指数的变化趋势

图8 平均请求时延ARD随NoC的变化趋势

[1] Ahlgren B, Dannewitz C, Imbrenda C,.. A survey of information-centric networking[J]., 2012, 50(7): 26-36.

[2] Jacobson V, Smetters D K, Thornton J D,.. Networking named content[J]., 2012, 55(1): 117-124.

[3] Chiocchetti R, Perino D, Carofiglio G,.. INFORM: a dynamic Interest Forwarding Mechanism for Information Centric Networking[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 9-14.

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

[5] Laoutaris N, Syntila S, and Stavrakakis I. Meta algorithms for hierarchical web caches[C]. IEEE International Conference on Performance, Computing, and Commu- nications, Phoenix, USA, 2004: 445-452.

[6] Chai W K, He D, Psaras I,.. Cache “less for more” in information-centric networks[C]. Proceedings of IFIP 6 Networking Conference, Prague, Czech, 2012: 27-40.

[7] 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.

[8] Ming Z X, Xu M W, and Wang D. Age-Based cooperative caching in information-centric networks[C]. IEEE INFOCOM, Orlando, USA, 2012: 268-273.

[9] Cho K, Lee M, Park K,.. WAVE: popularity-based and collaborative in-network caching for content-oriented Networks[C], IEEE INFOCOM Workshop on Emerging Design Choices in Name-Oriented Networking, Orlando, USA, 2012: 316-321.

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

[11] 朱轶，糜正琨，王文鼐. 一种基于内容流行度的内容中心网络缓存概率置换策略[J]. 电子与信息学报, 2013, 35(6): 1305-1310.

Zhu Yi, Mi Zheng-kun, and Wang Wen-nai. A cache probability replacement policy based on content popularity in content centric networks[J].&, 2013, 35(6): 1305-1310.

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

[13] Chiocchetti R, Rossi D, Rossini G,.. Exploit the known or explore the unknown? Hamlet-like doubts in ICN[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Helsinki, Finland, 2012: 7-12.

[14] Guo S, Xie H Y, and Shi G. Collaborative forwarding and caching in content centric networks[C]. Proceedings of IFIP Networking, Prague, Czech Republic, 2012: 41-55.

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

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

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

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

Collaborative Caching Algorithm Based on Request Correlation in Named Data Networking

Ge Guo-dong①Guo Yun-fei①②Liu Cai-xia①Lan Ju-long①

①(&&,450002,)②(’,210007,)

How to efficiently utilize the finite storage space and cache content chunks in the content store poses challenges to the caching policy in Named Data Networking (NDN). Using the differentiated caching strategy, a collaborative caching algorithm is proposed based on the request correlation. In the scheme, the subsequent correlated content chunks are requested in advance to increase the hit ratio for content requesting. When making the caching decision, a two-dimensional differentiated caching policy combining the caching location and cache-resident time is proposed. According to the change of content activity, the caching location is pushed downstream hop by hop in the spatial dimension in order to spread popular contents to the network edge in a gradual manner, and the cache-resident time is adjusted dynamically in the time dimension. The simulation results show that the proposed algorithm can efficiently decrease the request latency, reduce the cache redundancy, and achieve higher cache hit ratio than other caching strategies.

Internet; Named Date Networking (NDN); Collaborative caching; Request correlation; Content-based routing

TP393

A

1009-5896(2014)12-2795-07

10.3724/SP.J.1146.2014.00114

葛国栋 ggd@mail.ndsc.com.cn

2014-01-20收到，2014-04-24改回

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