内容中心网络中基于分布式协作的缓存策略
胡骞, 武穆清, 刘红宝    
北京邮电大学 网络体系构建与融合北京市重点实验室, 北京 100876
摘要

提出了一种应用于内容中心网络的缓存策略, 对高热度内容进行分布式缓存, 允许缓存节点之间协作, 保证热度高的内容在缓存中生存更长的时间, 并在内容请求过程中利用跟踪节点实现缓存内容的定位, 允许内容请求用户从网络中参与协作的缓存节点获取被请求内容的不同部分, 达到分布式缓存协作的目的, 提高网络中缓存资源的利用率, 降低内容请求用户获取内容的时间.仿真结果表明, 该策略能有效减少网络的平均时延.

关键词: 内容中心网络     缓存     协作缓存     内容定位    
中图分类号:TP393 文献标志码:A 文章编号:1007-5321(2015)02-0098-06 DOI:10.13190/j.jbupt.2015.02.018
Distributed Cooperative Caching Strategy in Content-Centric Networking
HU Qian, WU Mu-qing, LIU Hong-bao    
Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract

A distributed cooperative caching strategy was proposed for content-centric networking, in which the popular contents can be cached and the distributed cooperation is allowed within the cache nodes to ensure a longer sojourn period of caching. By utilizing the tracker node, the location of cached contents can be found during the content request process. Moreover, the content requesters can acquire the contents from all cache nodes that participate in the cooperation to achieve the goal of distributed cooperative caching, so as to improve the utilization of cache resources in the network, and to reduce the average time of acquiring contents for the requesters. Simulation shows that the proposed strategy can reduce the average round trip time in the network effectively.

Key words: content-centric networking     cache     cooperative caching     content locating    

内容中心网络(CCN, content-centric networking)颠覆了传统TCP/IP网络以主机为中心的组网思想,将内容置于首要地位,并基于内容直接进行数据转发,在未来网络领域的研究中广受关注[1].

作为CCN的关键技术之一,缓存技术逐渐成为领域内的研究热点.虽然缓存技术在网络领域已经得到了广泛的应用[2],但与传统缓存技术相比,CCN的缓存具有普适性和透明性,并且具有更细的粒度[3].但是这也为缓存技术的研究带来问题和挑战,如何才能让内容业务充分地利用网络中的缓存资源,降低内容请求用户获取内容的所需时间,是CCN缓存研究中的重要问题.提出基于分布式协作的缓存策略,用于定位网络中的缓存内容,并允许内容请求用户从参与协作的任意缓存节点获取内容,使缓存资源得到充分利用.

1 内容中心网络中的缓存协作策略1.1 策略思想

根据内容中心网络的特性,内容请求用户在发起请求时并不关心内容来源,但是网络节点仍需要基于一定的规则对内容请求进行路由和转发,以避免在全网泛洪加重网络负载.尽管CCN网络节点的缓存能力在一定程度上缓解了网络压力,但只有从内容请求用户到内容服务器之间的节点能够将缓存的内容返回给内容请求用户,而其他节点中的缓存无法得到有效利用[4].

在CCN网络中,全网节点内嵌缓存的优势与缓存资源的不充分利用的矛盾,是缓存研究中亟待解决的问题.笔者提出的缓存协作策略就是为了解决这个问题.

图 1所示,假设用户请求的文件f1被划分为c1c2c3c4共4个块.网络中实线部分指示的是用户到内容服务器之间的默认路径.在缓存非协作的情况下,c1c2分别在节点AB命中,而c3c4由于缓存在路径外的节点CE中,因此不能被利用.提出的缓存协作策略,就是通过为文件设定一个跟踪节点(tracker),用来收集协作范围内其他节点的缓存状态信息,以扩大网络中缓存资源的可用性.另外,所有参与缓存协作的节点定义为对等节点(peer).假设图中节点A被选定为文件f1的tracker节点,其协作范围为两跳,那么当对c3c4的内容请求到达节点A时,节点A会将其转发给节点C,而不再继续沿着实线标识的路径转发.通过网络节点之间的缓存协作,可以使缓存中的内容得到充分地利用,减少网络中重复流量的传输,降低内容服务器的负载.

图 1 CCN网络的内容请求过程
1.2 缓存协作策略描述

通过缓存协作,可以使热度高的内容在缓存中生存更长的时间,并缩短内容请求用户获取内容的时间.与内容服务器相比,网络节点中被缓存的内容具有不稳定性,当缓存没有可用空间时,节点会根据缓存替换算法确定删除哪些被缓存的内容,直至能够容纳新到达的内容为止.此外,缓存的协作应该是有条件的,对于热度较低的文件,启动缓存协作可能并不会带来性能的提升,反而会消耗有限的缓存资源并引入额外的信令开销.下面将详述提出的缓存协作策略,以期解决上述问题.

1.2.1 节点的缓存状态空间

考虑到网络中产生内容的业务流特性各不相同, 并非所有内容都需要缓存协作, 例如热度很低的文件或具有隐私性的电子邮件等业务, 引入协作机制不但无法获得缓存性能的提升, 还会带来额外的网络开销.因此,仅允许一部分缓存的内容参与协作.

为了明确地将参与协作的缓存内容与本地缓存内容区分开来,下面对缓存内容的状态进行定义:假设节点缓存的状态空间为{sl, sc},sl代表本地状态,sc代表协作状态.

当新的内容块被缓存在一个节点中时,初始状态为本地状态sl,该内容块仅本地可见,不能满足其他节点收到的内容请求;满足一定的条件,可以从初始状态转化为协作状态.处于协作状态时,可以满足其他节点收到的内容请求.在替换策略上,节点对所有处于本地状态的内容块执行最近最少使用替换算法(LRU, least recently used),替换最近最少使用的内容块;而对于处于协作状态的内容块,则需先转化为本地状态,再执行LRU策略进行替换.

A.本地状态到协作状态的转化

前面已经提到,缓存协作会引入额外的网络流量.为了避免不必要的缓存协作给网络带来的较大开销,应当对本地状态向协作状态的转化作一定限制.可以通过两种机制实现本地状态sl向协作状态sc的转化.

1) 命中计数机制.对所有处于本地状态的内容块进行命中计数,在被替换之前,如果内容块的命中计数达到阈值θ,则将该内容块的状态转化为协作状态.其中,阈值可以根据缓存空间的大小进行设定.

2) 被动提升机制.当节点收到文件fi的协作请求时,允许将处于本地状态的所有内容块ci, j提升至协作缓存空间,以参与文件fi的缓存协作,其中,j∈[1, mi],mi表示文件fi被划分成的内容块数.

B.协作状态到本地状态的转化

为了保证协作机制的有效运行,处于协作状态的内容块默认不允许被替换,只有当收到取消协作请求时,才会将相应的内容块转化到本地状态.但是,考虑到链路或节点网络故障等问题可能会造成丢包,导致节点收不到取消协作的请求,使过期失效的缓存一直保持在协作状态造成缓存空间的浪费.通过为协作状态绑定冻结时间[5]来解决这个问题.具体描述如下:

刚进入协作状态sc的内容块被绑定冻结时间Tf,处于冻结时间内的内容块不允许发生状态转移,且每一次对冻结内容块的请求,会将冻结时间重置为Tf.当冻结时间内没有新的内容请求到达时,内容块将转化成本地状态.

由此可见,在提出的缓存协作策略中,内容从协作状态转移到本地状态的条件有两个,满足其一即可:1) 接收到tracker发出的取消协作请求;2) 在冻结时间内没有发生命中事件.

1.2.2 协作缓存网络的建立与维护

缓存的协作需要在节点之间发送信令包以传递缓存状态信息,如果网络中传输的所有内容均采用协作策略,不仅会引入额外的信令开销,还会消耗有限的缓存资源.除了在单一节点内区分本地状态和协作状态以外,还有必要对参与协作的文件作进一步限定,只允许热度较高的文件利用缓存协作策略.由于内容中心网络分布式的特点,网络中的节点无法直接预测被请求内容的热度.采用前面介绍过的命中计数作为热度的判断依据.当命中计数达到阈值θ时,触发协作策略.

另外,为使内容中心网络能够支持缓存协作,修改CCN节点的数据结构,增添缓存协作转发信息表(CC-FIB, cache cooperating forward information base),以辅助完成协作功能,如图 2所示.

图 2 改进的网络节点模型

与转发信息表(FIB, forward information base)类似,CC-FIB表提供对内容请求的路由功能.当内容请求到达一个CCN节点时,首先检查缓存单元(CS, content store),如果CS命中,则直接沿内容请求的到达路径返回缓存内容.如果CS中没有请求的内容,则查找未决请求表(PIT, pending interest table),如果有PIT中有相同的内容前缀,则在PIT相应条目中增加内容请求的到达接口,并放弃转发.当CS与PIT均不匹配时,优先查询CC-FIB表,以确认是否能通过缓存节点之间的协作获取内容.只有CC-FIB无法匹配时,才按传统内容中心网络的方案,基于FIB进行转发.如果FIB中仍然没有匹配条目,CCN节点会丢弃内容请求包.为了实现缓存节点之间的协作,定义协作信令包,包格式如图 3所示.

图 3 协作信令包的格式

其中,协作指令的取值为1、2、3、4,分别对应以下4种功能:

1) 协作请求.协作请求指令由tracker节点泛洪发出,用于向协作范围内的节点发起协作请求.当一个节点接收到协作请求时,如果本地节点的缓存满足条件,会将相应的内容块转换到协作状态,并回应一个携带协作确认指令的信令包,用于协作确认.

2) 协作确认.协作确认指令由peer节点发出,按照协作请求的反转路由返回给tracker,用于确认参与缓存协作.

3) 协作取消.协作取消指令由tracker节点泛洪发出,用于向协作范围内的节点发起协作取消,收到协作取消指令的节点,如果正在参与协作,则将相应的缓存内容块转换回本地状态.

4) 协作退出.协作退出指令由参与协作的节点发出,按协作请求的反转路由返回给tracker,收到协作退出指令的节点,会删除CC-FIB中的相应条目.

内容名采用类似URL的方式.例如:/f1/c1.其中,f1是文件名,c1f1文件中被分割的一个内容块,假定内容块的大小不超过网络中的最大传输单元,那么各CCN节点的缓存即以内容块为单位[1].考虑到内容块之间的相关性[6],对单一内容块进行协作没有实际意义.协作是以文件为单位的,在发送协作请求和协作取消两个指令时,内容名应为文件名,即“f1”;而携带协作确认和协作退出指令的信令包,内容名应为内容块名,即“f1/c*”,星号表示内容块的序号.

下面结合具体实例来讨论协作缓存网络的建立,仍以图 1所示拓扑为例.当节点A中缓存的内容块c1被请求次数达到阈值θ时,节点A首先检查本地CC-FIB表中是否已经存在f1的tracker条目,如果存在,不作处理.如果不存在,则节点A发送协作请求指令(携带f1字段),搜索文件f1的其他内容块.协作请求包在限定的范围r内(例如r=2) 泛洪.收到该协作请求的所有节点,记录协作请求包的到达端口,并更新至CC-FIB表(“f1/tracker”,face).如果收到该协作请求包的节点缓存了文件f1的一个或多个内容块,则将这些内容块的状态转化为协作状态并按原路径返回协作确认指令.协作确认包同样会更新沿途节点的CC-FIB表.例如图中的节点CE,均会返回协作确认包.由于节点E与tracker之间还有节点C(路径A-C-E),故返回的协作确认指令会在节点C添加CC-FIB表项:(f1/c3,face).

如果tracker节点在协作冻结时间内没有收到任何对该文件的内容请求,则tracker节点会在协作范围内广播协作取消指令,取消对该文件的协作.

另外一种情况就是,对于各peer节点,虽然没有收到tracker节点发送的协作取消指令,但是本地缓存中处于协作状态的缓存条目在协作冻结时间内并没有收到任何内容请求.在这种情况下,peer节点会主动向tracker节点发送协作退出指令,退出该文件的协作,以释放资源.这种设置是必要的,因为内容中心网络并不关心内容的来源,当一个内容块存在于多个参与协作的peer节点时,会造成缓存资源的浪费,这种机制可以及时释放有限的缓存资源.如图 1中的节点CE,如果缓存了相同的内容块c2,且所有的内容请求来自节点A的转发,那么节点E将内容块c2设为协作状态将失去意义,因为所有的请求都会在节点C得到满足.

1.2.3 协作缓存的通信过程

在完成一个文件的协作缓存网络建立过程之后,后续对该文件的内容请求就可以利用这个网络内所有节点的缓存资源.具体的通信过程,根据协作缓存网络中第一个收到内容请求的节点是tracker节点还是非tracker节点,分两种情况讨论.

假设图 1中文件f1的协作缓存网络已经建立,tracker节点为A.节点CE参与了文件f1的缓存协作.

当一个请求到达节点A时,由于A是tracker节点,CC-FIB中记录了所有peer信息,所以直接查询CC-FIB,按接口转发即可.如果CC-FIB中无法匹配,则继续查询FIB表,按传统CCN的方式进行转发.当一个请求到达非tracker节点,例如节点E时,假定请求的是内容块c2,查询节点E缓存未命中,继续查询CC-FIB表,CC-FIB表中虽然没有精确匹配的内容块转发信息,但可以查找到f1的tracker为节点A,故节点E会将请求逐跳转发到节点A.节点A收到请求以后会查询CC-FIB,再将内容请求转发到缓存了相应内容的节点.在本例中,被转发的请求会按E-C-A路径转发,但节点C的缓存能够满足c2的内容请求,故内容块会直接从节点C返回.

图 4 基于CCN的缓存协作网络

在实际运行中,不同文件的tracker节点可以不同,参与协作的节点也可以不同,等效于对不同的文件形成了不同的缓存协作网络,这一点与作为覆盖网络的典型代表——对等网络(P2P, peer to peer)网络相似.但是两者本质上是两种完全不同的组网技术. P2P网络覆盖于IP网络之上,是将不同的终端、服务器等设备作为peer节点形成的应用层网络;而尽管沿用了tracker和peer的名称,实际上CCN网络中的缓存协作是利用内嵌缓存的网络节点完成组网,考虑到网络本身以内容为中心的特性,这样的协作机制在内容分发中具有更高的效率.

2 仿真实验与结果分析

为验证缓存协作策略的性能,利用Python语言搭建了内容中心网络的仿真平台,对提出的策略进行仿真,并与CCN网络默认的非协作策略作对比分析,缓存替换策略均采用LRU策略.

仿真采用ER(Erdös-Rényi)随机拓扑图,网络节点数量为100个,均具备缓存能力,且缓存大小S=100.定义与用户(内容请求用户)直连的节点为接入节点,与服务器直连的节点为内容服务器节点.为不失一般性,假设接入节点可以汇聚多个用户,而内容服务器节点只与一个内容服务器相连.从所有网络节点中,随机选择20个接入节点,5个内容服务器节点,其余节点为普通缓存节点.用户数量设定为200个,均匀分布连接到20个接入节点,对文件的请求服从泊松分布,而对文件中不同内容块的请求为恒定速率.为了更好地体现协作缓存机制的作用,设定两个仿真场景:

1) 场景1,接入节点20个,内容服务器节点5个;

2) 场景2,接入节点20个,内容服务器节点3个.

2.1 平均时延

图 5所示为不同缓存大小情况下的平均往返时延.对于两种策略,随着缓存容量的增大,获取内容的平均往返时间均减小,但与非协作策略相比,协作策略进一步将平均往返时延减小5%左右.另外,由于内容服务器的减少,导致场景2的平均往返时延比场景1中的实验数据要大.

图 5 不同缓存大小情况下的平均往返时延

下面讨论不同内容热度分布的情况.根据Zipf分布特性可知,参数α会影响热度分布,α值越大,内容的热度分布越集中.基于场景1进行仿真,由图 6可知,随着α值的增大,两种策略的平均往返时间都在下降.这是因为LRU替换策略在一定程度上能够感知内容热度,使热度高的内容能够在缓存中生存更长的时间.而由Zipf的分布特性可知,α值越大,热度高的内容所占比例越大,缓存策略起的作用也越大.

图 6 不同α情况下的平均往返时延
2.2 网络负载

网络负载在本研究中定义为单位时间内网络中传输的比特数.考虑到在所有仿真实验中,内容请求用户的请求速率相同,因此较小的网络负载说明网络能够以更小的代价完成内容传输业务.

下面对不同缓存容量下两种策略的网络负载进行比较.由图 7可以看出,随着缓存容量的增大,两种策略的网络负载都会降低,这是因为更多的缓存资源使得内容请求用户能够以更大的概率从缓存中获取内容,而不必访问内容服务器,故而降低了网络负载.在相同的缓存大小情况下,协作策略能够进一步降低网络负载,这是因为协作机制的引入提高了网络中的缓存利用率.

图 7 不同缓存大小情况下的网络负载

图 8可知,当α值增大时,网络负载随之降低,这个结论与图 6是一致的.另外可以发现,协作策略在α值较低时,与非协作策略相比具有更大的性能增益,这是因为α值越低,不同内容之间的热度差异越不明显,根据LRU的替换算法,高热度的内容被替换的概率也会增大.而讨论的协作策略允许对参与协作的内容进行冻结保护,在一定时间内不允许被替换,最大限度地保证了高热度内容的命中率.

图 8 不同α情况下的网络负载
3 结束语

针对内容中心网络提出了一种基于分布式协作的缓存策略,建立网络中缓存节点的协作机制,有效减少网络重复流量,提高缓存利用率. 仿真结果表明,该策略在降低用户获取内容的平均时延,降低网络负载等方面取得了较好的性能.

参考文献
[1] Jacobson V, Smetters D K, Thornton J D, et al. Networ-king named content[C]//Proceedings of the 5th Conference on Emerging Networking Experiments and Technologies. New York: ACM, 2009: 1-12.
[2] 林荣恒, 章晖, 邹华. 面向SNS用户访问行为的Web缓存预测替换[J]. 北京邮电大学学报, 2012, 35(1): 111–114.
Lin Rongheng, Zhang Hui, Zou Hua. Web replacement policy based on user requests for SNS[J].Journal of Beijing University of Posts and Telecommunications, 2012, 35(1): 111–114.
[3] Zhang Guoqiang, Li Yang, Lin Tao. Caching in information centric networking: a survey[J].Computer Networks, 2013, 57(16): 3128–3141. doi: 10.1016/j.comnet.2013.07.007
[4] Draxler M, Karl H. Efficiency of On-Path and Off-Path Caching Strategies in Information Centric Networks[C]//GreenCom 2012, Besancon: IEEE, 2012: 581-587.
[5] Hu Qian, Wu Muqing, Wang Dongyang, et al. Lifetime-based greedy caching approach for content-centric networking[C]//ICT 2014, Portugal: IEEE, 2014: 426-430.
[6] Carofiglio G, Gallo M, Muscariello L. On the performance of bandwidth and storage sharing in information-centric networks[J].Computer Networks, 2013, 57(17): 3743–3758. doi: 10.1016/j.comnet.2013.08.018