基于局部流行度的分布式协作缓存策略

房晓阳,季新生,刘彩霞,杜福德

(1.国家数字交换系统工程技术研究中心,郑州 450002; 2.65054部队,大连 116000)

0 概述

据Cisco预测,全球网络流量的年复合增长率将达到22%,而到2020年,视频流量占所有消费类互联网流量的比重将超过82%[1],内容获取已经成为互联网流量的主导因素。日益增长的对高效内容分发的需求促使基于命名数据对象(Named Data Objects,NDOs)的未来网络架构的研究,这些架构一般统称为信息中心网络(Information-Centric Network,ICN)[2]。ICN作为一种革命式的新型网络架构,其首要考虑对象是内容本身,而不是内容所处位置。在ICN中,网络节点具备缓存能力,用户请求内容时,缓存该内容的节点可以响应用户请求。自Information-Centric的概念提出以来,涌现了很多解决方案,其中,以命名数据网络(Named Data Network,NDN)[3]最为引人注目,其也是现在主流的ICN架构研究范例。

NDN为每个内容对象分配全局唯一的名字,在中间层用数据名取代IP进行路由[4]。当NDN路由器接收到兴趣包后,如果内容存储器(Content Store,CS)中有对应数据,则发送数据包响应请求。若CS中没有对应数据,则查询未决请求表(Pending Interest Table,PIT),如果发现匹配项,则在对应项中添加兴趣包进来的接口(Face)。如果PIT中没有匹配项,则依据转发信息库(Forwarding Information Base,FIB)向内容源方向转发请求,并在PIT中创建新条目。

对于NDN网络,发挥网内(In-Network)缓存优势的关键是在较小的开销下,提升缓存效能。而NDN中默认的缓存方式为处处缓存 (Leave Copy Everywhere,LCE)[5],即当对象返回时,沿途的所有节点都缓存对象,但这种方式容易造成缓存冗余,即相同的对象在多个节点同时存有副本,影响了缓存系统的多样性[6]。而且在路由转发时,无法感知路径外(off-path)邻近节点的缓存内容,导致缓存利用率低。这种无协作的缓存机制导致缓存冗余、频繁替换、效率不高。

针对上述问题,本文基于内容请求的局部特征,依据转发路径缓存收益及邻居缓存感知,提出一种分布式协作缓存机制(LPDCC)。在边缘路由器周期性地统计内容请求速率,并将结果随兴趣包转发,在请求路径上依据缓存收益的比较进行缓存决策。

1 研究现状

针对NDN网络LCE缓存方法的不足,为了提升缓存性能,减少冗余,目前研究人员已经提出了一些缓存策略,可以划分为4类,分别是随机缓存决策、基于拓扑的缓存决策、基于标签的缓存决策和基于流行度的缓存决策。

随机缓存决策中,节点以某一概率决定是否缓存通过的内容。文献[7]提出了Prob方法,节点按照固定概率p进行内容缓存。文献[8]提出了RCOne方法,在沿途路径上随机选择某一个节点进行缓存。文献[9]提出的HPC是一种逐步将内容推向消费者的缓存方法。随机缓存决策能够一定程度上降低缓存冗余,但是由于是一种随机性和盲目性的决策,缓存性能的提升有限。

基于拓扑的缓存决策依据节点的拓扑位置进行缓存。文献[10]为提高边缘节点缓存概率,提出了ProbCache方法,通过计算节点距离和缓存容量进行缓存决策。文献[11]提出的Betw方法,在转发路径上选择介数最高的节点缓存内容副本。基于拓扑的缓存决策提高了缓存针对性,但是没有考虑内容请求的分布特征。

基于标签的缓存决策为每个节点预先分配一些标签,节点只缓存满足标签条件的特定范围的内容。文献[12]为每个节点分配一个正整数,内容块的标号经过模运算后等于节点存储的整数,则进行缓存。文献[13]提出一种基于Hash的协作缓存机制,采取的方法是先对网络进行分簇,而后在每个簇中使用Hash算法进行缓存分配。这种缓存决策使得内容只在特定节点缓存,内容请求定向查找的路径较长,而且需要集中式的网络控制。

基于流行度的缓存决策依据用户访问特征,更多地缓存流行内容。文献[14]提出的WAVE机制,当内容请求次数增加时,按照指数速度增加被缓存的内容块数量。文献[15]提出的MPC机制,当内容请求率达到设定的门限,就将该内容标记为流行内容,如果节点中已经缓存了该内容,则向邻居节点发送建议缓存的消息,邻居节点根据自身状态决定是否缓存该流行内容,文献[16]提出了一种PRL缓存策略,网络节点根据本地内容请求的统计信息计算请求率,并结合跳数信息和替换率计算缓存收益,在传输路径中选出收益最大节点作为缓存节点,上游节点会记录缓存节点信息,并为后续内容请求执行重定向,这种方法会导致频繁的缓存信息同步,显著增加网络负载。文献[17]综合考虑了垂直请求路径和水平局域范围2维空间下的内容放置和冗余消除,基于最大内容活跃因子确定沿途转发路径对应的最大热点请求区域,但是会引入额外的查找时延。

从上述分析可以看出,基于流行度的缓存决策依据用户访问特征提高缓存内容的针对性,使得缓存内容更好地响应后续请求,得到了更多关注。但是现有方法无法避免请求聚合特性(即上游路由器接收到的请求是下游路由器请求聚合后的结果)[18]对内容流行度统计的影响,缺乏实时流行度感知,或者以全局流行度代替局部流行度,忽视了内容请求的差异性。

2 基于局部流行度的协作缓存机制

用无向图G=(V,E)表示任意网络拓扑,其中,V={v1,v2,…,vn}表示网络中的节点集合,节点vi的缓存容量为Ci,E表示链路集合。内容块对象分别表示为ok,k=1,2,…。ok所在源节点为Sk。ri,k为节点vi处,对内容块ok的请求速率。用hi,k表示从节点vi到Sk的跳数。详细的符号说明参见表1。

表1 符号说明

LPDCC是一种通过比较缓存收益进行决策的机制,主要思想如图1所示,用户发送Interest包,路由节点依据FIB进行转发,假设在节点v1命中(hit)缓存,然后系统按相反路径转发Data包,途中各节点将距节点v1的跳数与本节点内容流行度相乘,得到缓存收益,通过比较缓存收益进行决策。以节点v3为例,计算内容ok的缓存收益,r3,k=3,h3,1=2,那么缓存收益为:

Gain3,k=r3,k×h3,1

(1)

图1 内容请求示意图

2.1 流行度统计

由于内容数量很多,而且用户需求会动态变化,准确统计内容的全局流行度是很困难的,尤其是在大规模网络中。为此,提出一种局部流行度统计方法,每个节点根据自己服务范围的内容请求情况对内容流行度进行划分。由于不同区域的关注点不同,局部的流行度信息相比全局流行度,更能准确刻画用户需求。因为本文将周期性统计的内容请求速率作为本地的流行度,在本文中将不再区分这2个名词,而是在不同语境中采用不同的名词。

NDN协议对Interest包的处理过程中包含如下步骤,当在节点CS中没有发现匹配的数据,则查找PIT,如果在PIT中发现匹配项,那么把Interest包来源端口(Face)加入PIT表并丢弃,也就是请求聚合的Filter effect[19],这会导致内容流行度信息与实际情况差距较大,尤其是对于上游节点,所接收到的是合并后的内容请求信息,无法掌握真实的内容请求速率。在本文提出的LPDCC中,为了获得内容流行度信息,所有接入路由器周期性地统计每个内容对象的请求速率,并将结果随兴趣包一起转发。

图2给出了请求速率的转发示意图,路由节点中需要建立内容流行度表(Local Popularity Table,LPT)用于存储统计结果。图2显示了最近一次请求速率统计结果,r4,1=3表示在节点v4对内容o1的请求速率为3。这些结果随兴趣包向上游节点转发,上游节点接收后,记录内容ID、来源端口、流行度信息。这样可以在不增加网络负载的情况下获取本地内容流行度信息。在内容流行度表中之所以要区分端口是因为如果下游节点发送的流行度信息变化后,需要在对应接口记录中进行更新。如果在下个统计周期,r4,1=2,那么v2中(内容1,端口a)对应的流行度为2,v2中内容1总的流行度为4。

图2 请求速率转发示意图

2.2 缓存通告

由于内容对象数量多,而且已缓存内容有可能会被替换。如果将节点的缓存内容在全网或者较大范围内进行通告,将加剧网络负载。尤其是对于一些缓存收益较低的内容,由于缓存的驻留时间(Time To Live,TTL)短,缓存通告的信息容易失效,将导致请求重发,增加延迟。为此,需要选择相对稳定的缓存条目进行通告。

由于采用了基于缓存收益的决策方式,内容的缓存收益越大,在节点中的驻留概率越大,因此依据内容缓存收益的大小进行局域通告,增加内容可用性。按照节点CS中内容的缓存收益将其划分为3个等级:一是高收益内容,在进行通告时,优先保证可用性;二是一般收益内容;三是低收益内容,不进行通告,减小网络开销。对于不同等级的内容,通告范围的设置也不同。等级越低,TTL越小,可用性较低,应设置比较小的通告范围。可以将缓存收益在前10%的内容定义为第一等级,通告范围设为2跳;缓存收益在10%～ 30%的内容定义为第二等级,通告范围为1跳;其余内容可用性低,不进行邻域通告。

节点收到邻居节点的缓存内容通告后,建立邻居缓存信息表(Neighbor Content Table,NCT),如表2所示,其中跳数是指当前节点与内容提供节点之间的跳数。

表2 邻居缓存信息

当某项内容在NCT中存在多个条目时,则从中选择跳数最小的接口进行转发。由于依据NCT进行转发后,可能存在目的节点内容已经被替换的可能,在这种情况下,可以将请求通过NCT源节点进行再次转发。

2.3 路径缓存决策

为了比较缓存收益,需要流行度和跳数信息,而由于节点内容的流行度会由于子节点的缓存决策而变化,为了不增加请求应答的时间,在兴趣包转发过程中收集沿途节点信息。为此,在兴趣包中增加字段用于收集必要信息。增加的请求内容流行度字段用于2.1节阐述的流行度转发和更新;增加的沿途节点信息字段包含沿途节点ID、待替换内容ID、待替换内容收益、当前请求内容在沿途节点的流行度以及节点与内容源之间的跳数。兴趣包的报文格式如图3所示。

图3 兴趣包格式

在兴趣包中添加的字段用灰色表示,分别是请求内容流行度和沿途节点信息,其他字段和NDN中的兴趣包相同。沿途节点接收到兴趣包后首先依据内容流行度更新本节点CS表信息。沿途节点每转发一次就添加一项沿途节点信息,其中待替换内容是指节点CS中缓存收益最小的内容,收益是指待替换内容的缓存收益,流行度是指当前节点处被请求内容的流行度。跳数的初始值为1,每经过一次转发节点就加1。兴趣包转发过程见算法1。

算法1兴趣包转发算法(用户请求内容oj)

1.for (对于每个兴趣包上行请求的沿途节点)

2. 依据兴趣包中流行度更新rk,j(当前节点vk处内容oj的流行度)

3. if CS中不存在被请求内容then

4. 查询PIT

5. if存在记录

6. 在PIT中添加本次请求端口,停止转发

7. else

8. 更新兴趣包

9. 查询NC

10. if存在记录

11. 依据NCT转发

12. else

13. 依据FIB转发

14. end if

15. end if

16. else(CS中查找到被请求内容,将该内容提供节点记为g)

17. 执行缓存决策算法

18. 从请求端口转发数据包

19. 停止兴趣包转发

20. end if

21.end for

更新兴趣包是指:1)更新被请求内容的流行度;2)兴趣包沿途节点信息字段中已有条目的跳数加1;3)从当前节点CS中选出缓存收益最低的内容,标记为待替换内容,在兴趣包中添加其内容名、收益,跳数初始化为1。

图4为兴趣包转发过程示意图,用户请求内容oj,在节点v7处首先更新流行度表,假设v7没有缓存该内容,且PIT中也没有对应记录。那么v7从CS中选出缓存收益最低的内容,假设是oq(缓存收益为4),将对应信息写入兴趣包,然后继续转发。后续的转发处理过程类似,经过v7时,将兴趣包中v7的跳数信息加1。这样,当兴趣包到达内容提供节点时,就能够获取沿途节点的待替换内容信息,以及各节点距内容提供节点的跳数。当兴趣包到达内容提供节点后,在该节点执行缓存决策过程,见算法2。然后将决策结果随数据包转发,沿途节点接收到数据包后依据相应决策结果决定是否缓存该内容,并更新本地流行度。在内容提供节点处的缓存决策算法中,vi表示用户接入节点,g表示内容提供节点。

算法2缓存决策算法

1.rj=0

2.for vk∈Path(vi,g)

3. rk,j= rk,j-rj

4. if rk,j×hk,g-Gain>0

5. Caching Decision = TRUE

6. rj= rj+rk,j

7. else

8. Caching Decision = FALSE

9. end if

10.end for

图4 兴趣包转发过程示意图

以图4中的情况为例,在节点v1处执行缓存决策算法,rj初始化为0。首先判断是否在v7处缓存,由于r7,j=3,h7,g=2,Gainq=4,那么在v7处,内容oj的收益比待替换内容oq要大,所以在v7缓存内容oj。这时,rj更新为3,在判断v3的缓存决策时,由于v3的子节点v7将会缓存内容oj,后续在v7处对内容oj的请求将由v7应答,不会转发给v3,因此v3处内容oj的流行度要减去r7,j(即当前rj的值)。因此,r3,j=4,h3,g=1,Gainp=5,经过计算决定不在节点v3处缓存内容oj。通过算法2得到缓存结果后,将该结果随数据包下发。可以看出,按照算法2进行缓存决策,当子节点决定缓存当前请求内容时,可以及时更新父节点流行度,对缓存收益的评价更加合理,能够优化缓存位置。

3 仿真与性能分析

3.1 仿真环境与参数设置

本文通过ndnSIM进行仿真,这是一种基于NS3的NDN仿真工具,已经实现了所有的NDN的基本协议操作,并且支持用户自定义缓存和转发策略。使用NS3提供的GT-ITM生成50个节点的随机网络拓扑,并随机选择3个节点作为内容源服务器,其余节点作为接入节点。网络中共有10 000个大小相同的内容,内容大小设置为相同,每个内容划分为100个内容块,每个内容块的大小设为10 kB。每个节点的缓存容量设为相同,节点间链路带宽设置为100 Mb/s。节点的内生请求达到率符合参数为λ的泊松过程,内容请求概率符合参数为α的Zipf分布。在初始状态,节点缓存为空,没有存储任何内容副本。

3.2 性能分析

从平均请求延迟、缓存命中率、跳数减少率和业务开销4个方面,将本文提出的LPDCC与LCE[5]、ProbCache[10]、PRL[16]进行对比分析。

1)平均请求延迟

请求延迟是指从请求内容到收到数据包之间的时间延迟,网络中所有内容请求延迟的平均值定义为平均请求延迟ξ(t):

(2)

其中,Q指网络中所有内容请求,ωr(t)指单次内容请求的延迟。

如图5所示,在节点缓存容量为200 MB,λ为每移动30个的情况下,Zipf参数分别为α=1.0和α=1.2时的平均延迟。从系统初始状态开始,按照顺序进行了200 s的仿真,每隔2 s统计一次平均延迟。由于在初始状态下,网络节点中没有缓存任何内容,所有请求都被转发到内容源服务器,平均延迟较大。随着系统运行,网络节点缓存内容逐渐增加,用户可以就近获得所需内容,平均延迟变小,随后达到稳定状态。由于LCE采取泛滥式缓存,节点内容频繁更替,且无法利用路径外缓存,平均延迟最大。ProbCache没有考虑内容流行度的差异,不能确保高流行度内容的缓存驻留概率。对于PRL,由于没有考虑Filter effect的影响,导致延迟增加。而LPDCC依据内容的缓存收益合理确定缓存节点,选择驻留概率高的内容进行通告,提升缓存利用率,从而显著降低平均延迟。

图5 平均请求延迟对比

2)缓存命中率

缓存命中率ψ(t)定义为用户请求被节点缓存应答的比率:

(3)

其中,δr(t)为0表示在内容源获得响应,为1表示在路由节点命中缓存。缓存命中率越高,用户就近获取内容的可能性越大,源服务器和网络负载越小,也就表明系统的缓存性能更好。

图6给出在节点缓存容量为200 MB,α=1.2时,请求到达率分别为λ=20和λ=30情况下的缓存命中率。由于LCE的处处缓存,链路上存储了大量相同的内容,缓存多样性不足,导致缓存命中率很低。ProbCache没有利用路径外缓存,也会造成很多内容请求被转发到内容源服务器。PRL采取盲目式的缓存通告,增加了缓存缺少概率。LPDCC通过节点协作,保证了节点间缓存内容的差异性,增加了缓存命中率。

图6 缓存命中率对比

3)跳数减少率

(4)

图7给出了跳数减少率随α的变化趋势。当α较小时,内容流行度不集中,能够在节点缓存空间常驻的内容少,内容替换频繁,后续请求较难通过节点缓存满足,缩短内容获取路径的效果不明显,跳数减少率低。随着α的变大,内容请求更加集中,热点内容驻留概率大,由于LPDCC能够充分利用内容流行度的局域性特征,性能优于其他方案。

图7 跳数减少率随α的变化

图8给出了跳数减少率随节点缓存容量的变化趋势。当节点缓存空间很小时,能够缓存的内容很少,大部分内容请求需要转发到内容源服务器,跳数减少率都比较低。从图8可以看出,随着节点缓存空间的增加,可以在中间节点上缓存更多内容,4种方案的跳数减少率都在增加。LPDCC与其他3种方案相比,性能提升比较稳定。这是因为LPDCC依据缓存收益,提高缓存可用性,从而能够更快地相应内容请求,减少路由跳数。

图8 跳数减少率随缓存容量的变化

4)业务开销

与LCE相比,ProbCache、PRL和LPDCC为了提高缓存利用率都引入了显式协作开销。主要包含以下几部分:通告开销,节点存储开销,内容请求开销。

通告开销(CA):在构建NCT表过程中,选择相对稳定的缓存条目进行通告,引入了缓存状态通告开销。单次缓存通告的开销为通告报文大小(bit)与传输跳数(hop)的乘积。以fA表示通告频率,SA1表示首跳通告报文大小,d1为对应跳数。邻居节点收到SA1后,将报文中的通告范围减去1,并删掉通告范围为0的条目,获得下一跳通告报文SA2,d2为对应SA2的跳数。按上述方式类推,到最大通告范围m跳后,报文中的内容清空,通告结束。

(5)

节点存储开销(CC):由于节点需要额外存储流行度表(LPT)和邻居缓存信息表(NCT),增加了存储开销。LPT表需要记录内容名、端口、流行度信息,而NCT表需要记录内容名、端口、跳数信息。因此,节点存储开销是表中记录各项信息所占空间的大小(bit)。分别用lc、lf、lp、lh表示内容名、端口、流行度、跳数信息的长度,n1和n2分别表示流行度表和邻居缓存信息表的存储数量。

(6)

内容请求开销(CR):定义为内容请求和应答过程中产生的开销,即兴趣包和数据包的大小(bit)与传输距离(hop)的乘积。分别用Si和Sd表示兴趣包和数据包的大小,dr为第r次请求应答的传输距离。

(7)

表3为4种缓存机制的开销对比。统计时间为5 s,λ=30,α=1.2。LCE只是简单地进行处处缓存,没有通告开销和节点存储开销。但是LCE无法利用路径外缓存,并且路径缓存的替换率高,内容请求开销最大。ProbCache只需要收集沿途节点的缓存空间信息,通告开销和节点存储开销都较小,但和LCE一样,无法利用路径外缓存。PRL策略采取了一种盲目的节点通告方式,通告开销大,却不能保证通告的有效性,导致内容请求开销仍然较大。LPDCC 只通告驻留概率大的缓存内容,并且利用兴趣包转发过程进行流行度更新,引入了少量通告开销。由于需要在节点中维护LPT和NCT表,节点存储开销较大。但从内容请求开销的比较中,可以看出LPDCC能够增加内容请求的就近应答率,使得开销明显下降。

表3 业务开销对比

4 结束语

为有效利用NDN节点的缓存空间,提高网络服务性能,本文提出一种基于局部流行度的分布式协作缓存机制(LPDCC)。结合内容流行度的局域性,合理评价缓存收益,优化路径缓存,通过局部缓存通告,提高节点缓存利用率。仿真结果表明,LPDCC能够获得较高的缓存命中率,实现内容请求的就近应答。下一步工作重点为设计面向不同服务的缓存策略,并将LPDCC扩展到移动无线网络中。

[1] Cisco. Visual networking index:forecast and methodology,2015-2020[EB/OL].[2016-08-11].http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/complete-white-paper-c11-481360.pdf.

[2] TROSSEN D,SARELA M,SOLLINS K.Arguments for an information-centric internetworking architecture[J].ACM SIGCOMM Computer Communications Review,2010,40(2):26-33.

[3] ZHANG Lixia,AFANASYEV A,BURKE J,et al.Named data networking[J].ACM SIGCOMM Computer Communication Review,2014,44(3):66-73.

[4] IOANNOU A,WEBER S.A survey of caching policies and forwarding mechanisms in information-centric networking[J].IEEE Communications Surveys & Tutorials,2016,18(4):2847-2886.

[5] WANG Wei,SUN Yi,GUO Yang,et al.CRCache:exploiting the correlation between content popularity and network topology information for ICN caching[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2014:3191-3196.

[6] 张国强,李 杨,林 涛,等.信息中心网络中的内置缓存技术研究[J].软件学报,2014,25(1):154-175.

[7] LAOUTARIS N,SYNTILA S,STAVRAKAKIS I.Meta algorithms for hierarchical web caches[C]//Proceedings of Performance,Computing,and Communica-tions.USA:IEEE Press,2004:445-452.

[8] EUM S,NAKAUCHI K,MURATA M,et al.CATT:potential based routing with content caching for ICN[C]//Proceedings of ACM Proceedings of the ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:49-54.

[9] WANG Yu,XU Mingwei,FENG Zhen.Hop-based pro-babilistic caching for information-centric networks[C]//Proceedings of IEEE Global Communications Conference.Washington D.C.,USA:IEEE Press,2013:2102-2107.

[10] PSARAS I,CHAI W K,PAVLOU G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:55-60.

[11] CHAI W K,HE Diliang,PSARAS I,et al.Cache “less for more” in information-centric networks[J].Computer Communications,2013,36(7):758-770.

[12] LI Zhe,SIMON G.Time-shifted TV in content centric networks:the case for cooperative in-network caching[C]//Proceedings of ICC’11.Washington D.C.,USA:IEEE Press,2011:1-6.

[13] SOURLAS V,PSARAS I,SAINO L,et al.Efficient hash-routing and domain clustering techniques for information-centric networks[J].Computer Networks,2016,103:67-83.

[14] CHO K,LEE M,PARK K,et al.Wave:popularity-based and collaborative in-network caching for content-oriented networks[C]//Proceedings of IEEE Computer Com-munications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

[15] BERNARDINI C,SILVERSTON T,FESTOR O.MPC:IEEE Popularity-based caching strategy for content centric networks[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2013:3619-3623.

[16] HU Xiaoyan,GONG Jian,CHENG Guang,et al.Enhancing in-network caching by coupling cache placement,replacement and location[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2015:5672-5678.

[17] 葛国栋,郭云飞,刘彩霞等.命名数据网络中基于局部请求相似性的协作缓存路由机制[J].电子与信息学报,2015,37(2):435-442.

[18] JIA Zixiao,ZHANG Peng,HUANG Jiwei,et al.Modeling hierarchical caches in content-centric networks[C]//Proceedings of IEEE International Conference on Computer Communications and Networks.Washington D.C.,USA:IEEE Press,2013:1-7.

[19] FENG Bohao,ZHOU Huachun,ZHANG Hongke,et al.A popularity-based cache consistency mechanism for information-centric networking[C]//Proceedings of Global Communications Conference.Washington D.C.,USA:IEEE Press,2016:1-6.