一种基于势能的内容中心网络缓存决策策略

张建伟,王旭辉,蔡增玉

1(郑州轻工业大学 计算机与通信工程学院,郑州 450002)2(郑州轻工业大学 软件学院,郑州 450002)

1 引 言

随着互联网任务以及用户关注方向的转变[1,2],传统的IP网络已经不能满足时代的需求[3,4],迫切需要提出新的网络体系架构.鉴于此,国内外学者提出了许多不同的网络体系架构[5],其中一种以信息为中心的体系架构——信息中心网络(Information-Centric Network,ICN)由于其良好的特性得到了学者们的广泛认可[6],而内容中心网络(Content-Centric Network,CCN)作为ICN的一种典型架构,被认为是最有发展前景的未来网络体系架构[7].

与传统的IP网络相比,CCN网络最重要的特征就是不再依赖IP地址来确定内容在网络中的位置[8],而是以内容的名字作为其全网的唯一标识,并以内容名作为用户获取内容的索引[9].同时,CCN网络采用发布/订阅式的模式请求内容,使得内容的供需双方可以在时空上解耦合.此外,CCN路由器同时具有存储及路由转发内容的功能[10],所以CCN可以进行域内缓存.正是由于域内缓存的存在,使得用户的请求在到达内容源服务器之前就能够得到响应,这在减少用户平均请求时延的同时.大大减轻了内容源服务器的负载.

域内缓存作为CCN网络的重要组成部分[11],其性能的优劣直接影响着CCN网络的整体性能.而CCN网络总的缓存空间以及每一个路由器的缓存空间是有限度的[12],因此选择有效的域内缓存决策策略,将内容放置于合适的位置,在有限的空间中缓存更加多样化的内容,使网络资源得到更加合理的利用,可以增加缓存内容的多样性、提高缓存命中率.

为了充分发挥CCN网络的性能[13],域内缓存决策策略需要满足两方面的要求:1)将访问量(流行度)高的内容缓存到距离互联网用户较近(网络边缘)的路由器节点中,降低用户的请求时延,提升用户使用体验;2)提高整个网络缓存系统的缓存内容的多样性,降低网络缓存内容的冗余度,提升网络的缓存命中率.

目前,国内外学者致力于域内缓存性能的研究,已经有了创造性的研究成果[14,15].文献[16]提出的TERC(Techniques for En-Route Web Caching)策略是CCN默认的决策策略,其将用户请求的内容缓存至内容所经过的每一个节点中,其缺点是造成了大量的缓存内容冗余,同时因为CCN路由器的缓存空间有限,导致网络的缓存内容多样性不高,此外,TERC策略也没有考虑到内容访问量的问题.文献[17]提出的ProbC(Probabilistic Caching)策略将用户所请求的内容尽量的缓存到距离用户较近的节点中,进而降低用户的请求时延,但是该策略同样没有考虑到内容的访问量等因素,而是一味地将内容缓存至网络边缘的位置,加大了网络边缘位置的竞争.MPC(Most Popularity Caching)策略[18]的宗旨是将用户访问较多的内容尽可能多的备份在CCN网络中,但是MPC策略仅仅缓存用户访问量高的内容,导致网络内容的多样性不高.文献[19]所提出的CC-CCN(Cache Capacity-aware)策略将内容缓存至路径上剩余缓存空间最大的节点中,并没有考虑到内容的访问量,此外,没有将内容备份至网络边缘的位置.

在综合分析现有缓存决策策略的基础上,文中提出了一种基于势能的缓存决策策略PECDS.该策略引用物理学中“势能”的概念,分别赋予内容以及网络节点相应的势能,并将两者的势能进行匹配,实现内容的分级缓存,避免了CCN网络默认的TERC策略所造成的内容冗余问题.提高了整个CCN网络缓存内容的多样性.同时,PECDS策略能够更加合理的分配网络中的资源,提高网络资源的利用率.

本文的第二部分主要介绍本文所提出的PECDS方案;第三部分对PECDS方案进行实验仿真,并对其性能进行对比分析;第四部分为结束语.

2 基于势能的缓存决策策略(PECDS)

2.1 PECDS概述

一个内容中心网络CCN由1个内容源服务器、I个路由器节点和K个互联网用户组成.内容源服务器中存储有整个网络中的所有的内容备份,且永久不会删除.假设在内容源服务器中,每一个内容数据的大小都相同,每一个路由器节点具有相同大小的缓存空间.

在本文所提出的PECDS方案中,我们在Data包中加入了用来标记内容势能等级(如何划分内容的势能等级,请见2.4.1节)的字段PE_C.同时,根据路由器节点距离互联网用户的跳数为路由器节点分配势能(如何确定节点的势能,请见2.4.1节),互联网用户的势能最低,距离用户的跳数越多,路由器节点的势能越高,直至最终的内容源服务器.此外,为了统计互联网用户的请求信息,在距离互联网用户最近的第一跳路由器节点中添加了用户请求信息表(User Requests Information Table,URIT)(详情请见2.4.2节),URIT会根据其统计的用户请求信息以及路径上路由器的数量为用户所访问的内容划分势能等级,访问量多的内容其对应的势能等级越低.

如果互联网用户需要请求内容,就会发送一个Interest包,当此Interest包到达距离用户的第一跳路由器节点时,首先,位于该路由器节点的URIT会记录此Interest包所请求的内容名以及其访问次数;之后,该路由器节点会查询内容存储CS中是否存在此Interest包所请求的Data包.如果有,就会直接响应此Interest包的请求并删除此Interest包,如果没有,此Interest包将会被路由到该路径上的上游路由器节点或者最终的内容源服务器满足其请求.

2.2 PECDS工作原理

图1 PECDS工作原理Fig.1 Working principle of PECDS

下面以图1所示的通信链路阐述PECDS方案的工作原理.图1(Ⅰ)所示的是该条通信链路的初始状态.可以看出,在此条通信链路中,存在4个互联网用户U1、U2、U3、U4,3个路由器节点R1、R2、R3以及1个内容源服务器CRS.其中,每一个路由器节点拥有大小相同的缓存空间;用来统计用户请求信息的URIT存放于路由器节点R1中,且URIT中的CN、CPV以及CPE等3个字段均为空,而RN字段记录的是该条路径上路由器节点的个数;在内容源服务器中存有4个大小相同的内容C1、C2、C3、C4.

在图1(Ⅱ)中,用户U1请求内容C1,首先发送请求内容C1的Interest包,当Interest包到达R1时,位于其中的URIT会记录此Interest包所请求的内容名字以及其访问次数,由于R1中没有内容C1的缓存备份,所以此Interest包将会被转发.同时,该路径上的所有路由器节点中都没有此Interest包所请求内容的缓存备份,所以,最终由内容源服务器响应此Interest包的请求.

接下来,如图1中(Ⅲ)、(Ⅳ)、(Ⅴ)所示,用户U2请求内容C1和C2,用户U3请求内容C1、C2和C3,用户U4请求内容C1、C2、C3和C4.与图1(Ⅰ)所示的用户U1请求内容C1的情况类似,由于在沿途的路由器节点中都没有其所请求的内容备份.所以,用户U2、U3、U4所发出的Interest包都会被路由到最终的内容源服务器中满足其请求.但是,位于R1中的URIT会记录用户所请求内容的名字以及其被访问的次数.

经过上述过程,URIT的状态如图1(Ⅴ)所示,存储于内容源服务器中的内容C1、C2、C3、C4被遍历访问.假设内容C1的访问量已将达到了内容访问量阈值,接下来,便会根据URIT中的CPV字段对其中的条目进行排序,排名由高到低依次是C1、C2、C3、C4.根据2.4.1节所述,内容势能被划分为3个等级,且每一个等级中具有1个内容.同时,内容的势能等级被写入包含该内容的Data包的PE_C字段中.接下来,PECDS会根据PE_C字段将该Data包缓存至与之相匹配的路由器节点中(详情请见2.4.2节).

图1(Ⅵ)所示的是该条通信链路的最终状态.其中,C1、C2、C3分别被缓存到R1、R2、R3中,由于用户对内容C4的访问量最少,所以C4在任何路由器节点中都没有备份.同时,为了避免“缓存污染”,Data包中的PE_C字段、URIT中的CN、CPV以及CPE等字段被全部清空,即保证那些在近段时间访问量较多的内容能够在较短的时间内获得较低的势能而不被近段时间访问量较少的内容所影响.

接下来,如图2所示,用户U1发出两个Interest包分别请求内容C1与C4,当请求内容C1的Interest包到达缓存路由器R1时,位于R1中的URIT会记录此Interest包所请求内容的名字以及访问次数,然后R1会查询其自身的内容存储CS,发现在CS中存在C1的备份,就会从R1直接将包含内容C1的Data包发送给用户U1并舍弃请求C1的Interest包.与此同时,当请求C4的Interest包到达R1时,位于R1中的URIT同样会记录其所请求的内容名以及访问次数,如前所述,在节点R1、R2、R3中都没有C4的缓存备份,所以,请求C4的Interest包将会被路由到最终的内容源服务器中满足其请求.

通过图1以及图2所示的例子,我们可以了解到,内容所

图2 请求C1与C4Fig.2 Requests for C1 and C4

处的路由器节点的势能与其内容势能相对应,势能等级低(访问量多)的内容被缓存备份到势能低(接近互联网用户)的路由器节点中.同时,仅仅位于距离互联网用户最近的路由器节点的URIT会记录用户请求的内容名以及其访问次数,并根据内容的访问量以及在互联网用户与内容源服务器之间的路由器的数量划分内容的势能等级,进而决定内容的缓存位置.在提高整个网络缓存效率的同时避免了不必要的网络开销.

2.3 算法描述

为了更进一步的理解PECDS缓存决策策略的实现过程,下面给出初始化(表1),节点Interest包(表2)以及Data包(表3)处理过程的伪代码.

表1 初始化过程伪代码
Table 1 Pseudo-code of initialization

Pseudo-code Ⅰinitialization PE_C = NULL PE_C=NULL CPE=NULL CPV=NULL CN=NULL RN is the number of router set PE_R(The potential energy of router)according to RNend

表2 Interest包处理过程伪代码
Table 2 Pseudo-code of Interest package

Pseudo-code Ⅱfor each Interest User send Interest URIT record the information of Interest,such as CN,CPV if Data in cache send Data & delete Interest else if Interest in PIT PIT records port else PIT records Interest(name,port) transmit Interest according to FIB send Data end ifend for

2.4 PECDS特性描述

上文详述了PECDS的工作原理,下文将介绍内容势能等级与节点势能的判断方法、URIT表,并通过例子阐述如何利用URIT表对内容进行分级缓存.

2.4.1 势能等级判断

在物理学中,若将地面视为0势能面,则一个物体的重力势能主要取决于其本身的重量m、距离地面的垂直高度h以及当地的重力加速度g.同时,根据距离地面的垂直高度,可将平面划分为势能等级不同的势能面.

表3 Data包处理过程伪代码
Table 3 Pseudo-code of Data package

Pseudo-code Ⅲfor(CPV >= T) set CPE according to RN & CPV PE_C=CPE for(each router) if PE_C==PE_R cache Data PE_C=NULL CPE=NULL CPV=NULL CN=NULL end if end forend for

在本文所提出的PECDS方案中,引用“势能”的概念,为内容及网络拓扑中的节点赋予势能.下面以图3所示的通信链路为例,分别介绍内容势能等级与节点势能的判断方法.

1)内容势能等级

内容势能等级主要取决于内容访问量以及互联网用户与内容源服务器之间路由器节点的数目等两方面的因素.假设位于路由器R1的URIT中共有X个内容,并且已经按照其访问量的高低排序.在互联网用户与内容源服务器之间存在Y个路由器,则可将URIT中的X个内容的势能划分为Y个等级,其中,有Z个内容的势能等级相同.Z可由公式(1)得出:

Z=[X/Y]

(1)

2)节点势能

在本文所提出的PECDS方案中,我们将网络拓扑中所有用户节点所构成的用户层视为“0势能面”,则每一个“路由器平面”由所有距离0势能面“垂直高度”相同的路由器节点所构成.这里的“垂直高度”指的是路由器节点距离用户节点的跳数.

如同本小节开头所述,一个物体的势能由其本身的重量m、当地的重力加速度g以及其距离地面的垂直高度h所决定.在图3所示的链路中,假设每一个路由器节点具有相同大小的缓存空间,并且每一段链路的材质都相同,那么每一个路由器节点的势能仅仅取决于其距离用户节点的“垂直高度”,路由器节点的势能将随着距离用户节点跳数的增加而递增.如前所述,用户节点的势能为0,则R1的势能为1,R2的势能为2,依次类推,RY的势能为Y,最终的源服务器CRS的势能为Y+1.

图3 势能等级判断Fig.3 Judgment of the level for Potential energy

2.4.2 URIT表

URIT仅仅位于每一个距离用户第一跳位置的路由器节点中,而不会在其它的路由器节点中生成,以节省路由器节点的缓存空间.URIT的形式如图1所示,其包含内容名(Content Name,CN)、内容访问量(Content Page View,CPV)以及内容势能(Content Potential Energy,CPE)和路由器数量(Router Number,RN)等4个字段.其中,内容名CN是内容的全网唯一标识;内容访问量CPV字段所记录的是一段时间内用户对内容的访问量,这里的“一段时间”可以是一星期,可以是一天或者更短,并会根据用户对内容的访问量进行调整,同时,整个URIT会根据内容访问量CPV字段进行排序;路由器节点数量RN字段所记录的是该条路径上用户节点与内容源服务器之间路由器节点的数量.

内容势能CPE字段是URIT中最重要的字段,其与路由器数量RN字段共同决定着内容被缓存备份的位置.下面以图4为例说明如何利用URIT表实现内容的分级缓存.

图4 分级缓存内容Fig.4 Content is hierarchically cached

从图4(Ⅰ)中可以看到,在内容源服务器中存储了8个内容,但是用户仅仅对其中的C1、C2、C3、C4、C5等5个内容进行了访问,并且对每一个内容的访问量都不一样,假设C1的访问量已经达到了内容访问量阈值.同时,该条路径上存在2个路由器节点R1、R2,根据公式(1),每一个路由器节点中会缓存备份2个内容.所以,根据URIT中的CPV字段对其中的内容进行排序,同时,根据RN划分URIT中内容的势能等级,并将内容的势能等级写入到包含此内容的Data包的PE_C字段中.接下来,PECDS将Data包缓存至与其PE_C匹配的路由器节点中,则通信链路的最终状态如图4(Ⅱ)所示.其中,C1、C4被备份到R1中,C5、C2被备份到R2中,而C3不会被备份到任何路由器节点中.同时,为了避免“缓存污染”,Data包中的PE_C字段、URIT中的CN、CPV与CPE等字段将被清空.

3 仿真分析

为了验证文中所提出的PECDS方案的性能,本文在CCNSim仿真平台实现了对TERC、ProbC以及PECDS三种策略的仿真,并通过缓存命中率(Cache Hit Ratio,CHR)、缓存内容多样性(Cache Content Diversity,CCD)以及平均请求跳数(Average Request Hops,ARH)三个性能参数对上述三种策略进行了对比和分析.

3.1 仿真环境与参数配置

仿真拓扑采用如图5所示的网络拓扑结构,其中共有12个路由器节点,每一个路由器节点都同时具有缓存以及路由转发内容的能力,并且每一个路由器节点拥有相同大小的缓存空间;每一个客户端(用户)都连接于一个路由器节点;内容源服务器CRS位于该网络的中心,其中存有所有内容的备份,且永久不会被删除.仿真中主要用到的参数及其含义如表4所示.

图5 拓扑结构Fig.5 Topology

假设内容源服务器CRS中共有10000个内容,每一个内容的大小都同为1MB,并且一个内容由1个chunk组成,即N=10000,S=1;路由器节点的缓存空间C的取值如图6所示;策略ProbC的沿路缓存概率为0.7,即p=0.7;网络中所有内容的流行度,即内容被访问的概率遵循参数α=1的Zipf分布(二八定律)[20];路由器节点的缓存替换策略选择LRU策略;内容访问阈值T是PECDS策略的专属参数,其值需要根据Zipf分布(二八定律)以及网络中的内容总数进行设定,所以在这里设定内容访问量阈值T=400.

表4 主要参数及其含义
Table 4 Main parameters and their meanings

参数含义N(个)内容源服务器中内容项的总数S(MB)每一个chunk的大小C(MB)路由器节点缓存空间的大小pProbC沿路缓存概率αZipf的参数T内容访问量阈值RS路由器节点缓存替换策略

3.2 仿真结果分析

在仿真的过程中,我们按照图6所示对路由器节点的Cache Space进行设置,考虑在Cache Space不同的情况下TERC、ProbC以及PECDS三种策略的缓存命中率CRH、缓存内容多样性CCD与平均请求条数ARH的仿真对比.如图6(a)所示,随着路由器节点Cache Space的增加,TERC、ProbC以及PECDS三种策略的缓存命中率CHR都有所提高,同时,我们也看到,在Cache Space为2000MB的情况下,PECDS的CHR相比于TERC及ProbC分别提高了44.1%和21.1%.如图6(b)所示,随着路由器节点缓存空间的扩大,三种策略在缓存内容多样性CCD方面都有所改善,但是,相比于TERC及ProbC,PECDS的CCD明显要更具有优越性,譬如,在Cache Space为2000MB时,PECDS的CCD为0.198,相比于TERC与ProbC分别增加了53.5%和23%.图6(c)所示的是三种策略的平均请求跳数ARH随Cache Space的变化,从图(c)中我们可以发现,随着Cache Space的增加,三种策略的ARH都呈现下降趋势,这说明三种策略都在一定程度上减少了用户的平均请求时延,但是,当Cache Space为2000MB时,PECDS的ARH相比于TERC与ProbC,分别减少了0.41跳和0.23跳,说明PECDS将更多的内容缓存至路由器节点中,有效减轻了内容源服务器CRS的负载压力.

图6 仿真结果Fig.6 Results of simulation

接下来对仿真结果作一下简要分析.如本文第1部分所述,TERC,即LCE策略,是内容中心网络CCN默认的缓存决策策略,其将用户请求的内容缓存至沿途上的每一个路由器中.这就使得沿途上所有的路由器节点所缓存的内容都一样,造成整个网络的缓存内容多样性不高,进而导致缓存命中率低下,用户的大多数请求在最终的内容源服务器中才能得到响应,导致用户的请求跳数偏大.

ProbC策略中,沿途上的每一个路由器会以不同的概率缓存用户所请求的内容,并且缓存概率与其距离用户的距离成反比,即距离用户越近,其缓存概率越大,使得沿途上的路由器节点可以缓存不同的内容.相比于LCE策略,ProbC在一定程度上提高了缓存内容的多样性,进而提高了缓存命中率,降低了用户的平均请求跳数.

本文所提出的PECDS策略引入“势能”这一物理学中的概念,为网络中的内容以及节点赋予势能,同时根据网络状况设置了内容的访问阈值.当内容的访问量达到该阈值,就匹配内容以及路由器的势能,有针对性的对内容进行缓存.相比于LCE策略以及ProbC策略,提高了缓存内容的多样性,同时提高了缓存命中率,降低了用户的请求跳数.

4 结束语

域内缓存是CCN网络最重要的特性,而缓存决策作为域内缓存的重要组成部分,其性能的优劣直接影响着CCN网络域内缓存的性能.CCN默认的缓存决策策略——TERC会造成大量的缓存冗余,并且请求时延长、命中率低.本文将物理学中的“势能”概念引入到网络拓扑结构中,提出了基于势能的缓存决策策略,即PECDS方案.PECDS方案分别为网络拓扑中的内容以及节点赋予势能,并按照一定的匹配原则匹配两者之间的势能,实现了内容的分级缓存.最后通过仿真结果表明,相比于TERC策略以及ProbC策略,PECDS在一定程度上提高了缓存命中率,降低了缓存内容的冗余度,减少了用户的平均请求时延,有效的减轻了内容源服务器的负载压力.

接下来,进一步优化势能的匹配机制以及研究与PECDS策略相匹配的缓存替换策略,并将两者结合应用到实际的网络拓扑中,逐步调优以期达到最优的性能,将是我们的重点研究内容.