基于内容中心性的概率缓存内容放置方法

李 黎1 柳寰宇1 鲁来凤2

1(陕西师范大学计算机科学学院 西安 710119)

2(陕西师范大学数学与信息科学学院 西安 710119)

摘 要 为减少信息中心网络的缓存冗余,改善缓存命中率和利用率,提出了一种基于内容中心性的概率缓存内容放置方法(content-centrality-based probabilistic caching content placement method, CCPCP).与传统网络中仅用来刻画网络拓扑结构的中心性指标不同,采用的内容中心性指标,不仅能刻画缓存节点的位置中心属性,而且能刻画信息内容本身属性.该方法中,沿途各缓存节点综合考虑内容中心性和内容获取时延自适应地计算各自缓存概率,即内容所在节点位置越居于中心,内容热度越高,内容获取时延节省越优的内容被缓存的概率就越高.仿真实验表明:与现有基于概率缓存内容放置方法相比较,CCPCP方法缓存内容副本数目较少,减少率可达到32%以上,CCPCP方法显著地减少了缓存冗余,降低了内容获取时延,提高了缓存命中率和缓存内容利用率.

关键词 信息中心网络;缓存内容放置;内容中心性;缓存冗余;缓存内容利用率

随着互联网的快速发展,网络中的流量呈爆炸式增长,用户对海量信息的获取逐渐成为核心需求.而传统网络的端到端通信模式已经无法很好地应对流量剧增所带来的巨大压力,因此,未来网络体系架构成为研究热点.其中,作为一种逐渐被认可的新型网络架构体系,以CCN(content-centric networking)/NDN(named data networking)[1],DONA(data-oriented network architecture)[2],NetInf(network of information)[3]等为典型代表的信息中心网络(information-centric networking, ICN)提倡以信息为中心的通信模式代替传统的以主机为中心的通信模式,能更好地适应互联网应用由发送者驱动的端对端通信模式向接受者驱动的海量内容获取模式的转变.

在ICN中,用户并不关心信息/内容所存放的位置(即where),而只关心信息/内容本身(即what)[4].因而,网络对内容进行统一标识,基于内容进行定位、路由和传输.同时,为了缓解当前网络流量的快速增长对网络带宽造成的严峻压力,ICN提倡网络中所有节点增加内置缓存功能以提高内容获取的效率和网络资源的利用率[5].

作为ICN中的关键技术之一,网内缓存(in-network caching)[6]被广泛研究,其核心思想是利用网络中节点的内置缓存功能,在具有缓存空间的路由器节点上缓存内容资源,以便用户发送的内容请求在路由时能直接访问到内容,而不需要每次从内容源(服务器)中获取内容.通过就近服务的方法,从而减轻服务器负载,降低网络流量,减少用户获取内容的时延[7].因此,合理高效的缓存内容放置方法对提高ICN的内容分发效率有着至关重要的影响.

在ICN中,最简单具有代表性的缓存放置方法是处处缓存(leave copy everywhere, LCE)方法[1],其主要思想是在内容对象返回路径中所经过的所有中间节点上缓存所有被请求的内容资源.不难看出,这种不加区分地缓存大量重复内容的方法会导致严重的缓存冗余,降低缓存空间利用率,难以发挥内容缓存的性能优势.为了减少缓存冗余,近年来,一些学者围绕节点在网络结构中的重要性,研究在核心节点上放置内容的缓存方法[8-10].这类缓存方法的依据是重要性大的节点具有更高的缓存访问概率,可以有效地减少缓存冗余,提高缓存资源的利用率.然而,这类方法仅考虑了节点的位置重要性,却未对内容进行区分,导致所有内容具有一样的缓存概率,从而影响缓存效率.另一些学者在考虑内容热度的同时更加关注用户获取内容的收益,研究在边缘节点上放置内容的缓存方法[11-14].这类缓存方法的依据是边缘节点更加接近用户,可以有效地降低用户获取内容所需的时延,缓解网络带宽压力.然而,这类方法趋向在边缘节点放置缓存内容,会增加不同内容在边缘缓存节点的竞争,从而降低缓存利用率.

针对上述问题,为减少缓存冗余,提高缓存利用率,降低内容获取时延,缓解网络带宽压力,本文提出了一种基于内容中心性的概率缓存内容放置方法(content-centrality-based probabilistic caching content placement method, CCPCP).本文主要贡献有3个方面:

1) 采用了内容中心性指标,该指标不仅能刻画内容缓存时的位置中心属性,而且也能刻画内容本身的属性;

2) 建立了最大化内容获取收益的整数线性规划模型,该模型兼顾了内容中心性和内容获取时延2方面的优化目标;

3) 提出了一种基于内容中心性的概率缓存内容放置方法CCPCP,该方法在缓存内容副本数目相同,甚至缓存内容副本数目更少的情况下,也能获得更优的缓存命中率、缓存内容利用率,有效地降低内容获取时延和内容缓存冗余.

1 相关工作

目前,在信息中心网络中,网内缓存机制已经受到许多研究者的关注.其中,根据缓存存放位置和请求用户与内容源路径的相对关系,可将现有研究大致分为2类:路径上缓存(on-path caching)和路径外缓存(off-path caching).本文主要关注路径上缓存研究,即考虑缓存内容存放在内容请求用户和内容源服务器的传递路径上.

CCN/NDN早期采用了LCE策略[1],该策略采用沿途全部缓存而没有对缓存内容和缓存位置进行选择,虽然操作简单,但冗余度高且容易造成缓存资源浪费.针对这一问题,Laoutaris等人[15]提出了一种LCD(leave copy down)缓存方法.当内容请求在缓存中命中时,只在缓存命中节点的直接下游节点缓存该内容,使缓存内容逐步接近用户.同时,文献[15]还提出了一种MCD(move copy down)缓存方法.该方法与LCD相似,但不同之处在于,缓存命中节点在其直接下游节点缓存内容后会删除相应的内容,服务器命中除外,从而减少缓存冗余.文献[16]则提出一种Prob(copy with probability)缓存方法.缓存节点以固定的概率对途经的内容资源进行缓存决策,即以概率p缓存内容,以概率1-p不缓存内容.这3种方法主要通过控制内容缓存的数量来降低冗余度,但仍没有考虑到对缓存内容和缓存放置位置的选择,因此,缓存资源利用率较低.

Chai等人[9]提出了一种基于介数中心性(bet-weenness centrality)的缓存算法,利用节点的介数概念,只在内容传递路径中选定介数最大的节点上缓存内容.其主要思想是,相比于其他节点,介数大的节点具有更高的缓存命中概率,从而提高缓存资源的利用率.类似地,文献[10]提出了一种基于节点中心性度量的内容中心网络缓存机制,其核心思想是,利用度、紧密度和介数这3个节点中心性度量作为各个节点重要性的评价指标,并结合缓存空间空闲率对网络拓扑中的关键节点进行选取,在选中的节点上缓存内容资源.可以看出,这2种方法提倡仅在网络拓扑中的核心节点上放置内容,以有效地减少冗余,提高缓存命中次数.然而,这类方法忽略了不同内容的流行度,导致所有内容具有一样的缓存概率,从而影响缓存效率.

通过考虑路径缓存容量和缓存收益2方面因素,Psaras等人[11]提出了一种加权概率缓存机制(ProbCache),即节点根据一定的加权概率进行缓存决策.其中,加权概率与节点的路径缓存容量和缓存收益成正比,路径缓存容量越大,缓存收益越高的节点,其缓存内容的概率越大.文献[12]提出了一种最大增益缓存策略.该策略的目标是通过联合考虑内容流行度和跳数减少来计算缓存增益,从而减少带宽消耗.类似地,Wu等人[13]提出了一种基于最大化收益的概率缓存策略(max-benefit probabilistic caching, MBP),依据内容流行度和内容放置收益2个关键因素计算节点缓存内容的概率.内容流行度越高,内容放置收益越大,则内容在节点上的缓存概率越大.这3种方法通过考虑缓存收益,提倡在边缘节点上放置内容,可以有效地降低用户获取内容所需的时延、减少网络流量.然而,这类策略会增加不同内容在边缘缓存节点的竞争,从而降低缓存利用率.

借鉴相关研究工作,为降低缓存冗余,本文提出的CCPCP方法考虑了缓存内容和缓存放置位置的选择;与现有仅关注网络结构因素,忽略缓存内容属性的放置方法不同,CCPCP方法在缓存内容位置的选择中不仅考虑缓存节点的位置中心属性,而且考虑缓存内容热度属性;与现有仅考虑内容获取时延的单目标优化模型和方法相比,本文建立的最大化内容获取收益模型,兼顾缓存放置位置、缓存内容属性和内容获取时延多个优化目标.本文提出的CCPCP方法能显著地减少缓存冗余,提高缓存命中率和缓存内容利用率,降低内容获取时延.

2 问题建模

2.1 基本定义

我们将ICN系统建模成一个无向网络图G=(V,E).其中,V={v1,v2,…,vn}表示缓存节点集合,E={e1,e2,…,em}表示所有链路集合.记S={s1,s2,…,sp}表示内容源服务器节点集合,U={u1,u2,…,uq}表示用户集合.C={c1,c2,…,cR},其中ciC表示第i个内容块,C表示所有内容块的集合.假设内容由若干个内容块组成,每个内容块大小相同,且仅保存于一个内容源服务器中.假设所有缓存节点都具有一定的缓存空间(cache space),其缓存空间的容量记为CS.

相关符号定义如表1所示:

Table 1 Related Notations
表1 相关符号

NotationDefinitionnNumber of Cache NodesmNumber of LinkspNumber of ServersqNumber of UsersRNumber of Content ChunksvCache Node v, v∈VcContent Chunk c, c∈CuUser u, u∈UpcPopularity of Content Chunk cs(c)Original Server of Content Chunk c, s(c)∈SCS(v)Maximal Capacity of Cache Node v

2.2 内容中心性

在复杂网络理论中,中心性是一个核心的度量指标,它通常用来反映网络拓扑中节点的重要性,中心性度量值越大的节点,在网络拓扑中的重要度越大.其中,介数中心性度量可以反映节点对信息在网络内传输的重要性.一般地,具有更大介数中心性度量值的节点在网络中占有更重要的地位.

传统网络中主要采用主机间端到端的通信模式,网络中介数中心性表示网络中所有节点对之间通过该节点的最短路径的数目,可用来刻画一个节点处理的信息访问量.然而,ICN提倡以信息为中心的通信模式代替传统以主机为中心的通信模式.在ICN中,相对于信息内容物理或逻辑位置而言,用户更加关心的是信息内容本身的获取.因此,仅依靠刻画网络结构的中心性指标是不够的.为了刻画缓存节点在用户请求内容时的重要性,本文借鉴文献[17-18]中基于内容的中心性(content-based centrality, CBC)度量思想,通过扩展介数中心性指标,并结合内容自身属性,定义了内容中心性(content centrality, CC)指标,该指标不仅能刻画缓存节点的位置中心性,而且也能刻画信息内容本身的属性.

内容中心性指标综合考虑了经过缓存节点的所有用户到内容的最短路径数目和内容本身的属性.本文中,用内容流行度来刻画内容属性,对内容进行区分.内容流行度是指用户对内容的请求概率,即内容被请求的概率越大,其流行度越高.CC指标可量化定义为

(1)

其中,pc表示内容块c的流行度,且满足表示内容块集合;σv(u,c)表示经过节点v的用户u请求内容块c的最短路径数目;σ(u,c)表示用户u请求内容块c的最短路径数目;U表示用户集合.CC(v,c)表示缓存节点v关于内容块c的内容中心性.CC(v,c)刻画了经过节点v的所有用户到内容的最短路径数目与所有用户到内容的最短路径数目之比与内容流行度的乘积.

通过一个简单示例对CC指标进行说明.如图1所示,假设用户u1u2u3分别对内容块c发送请求,内容块c存储在源服务器s(c)中.假设网络中内容请求根据最短路径进行转发.在图1中,用户u1到源服务器s(c)的最短路径只有1条,可表示为u1v1s(c),故u1请求内容块c的最短路径数目σ(u1,c)=1.同理,u2s(c)的最短路径只有1条,表示为u2v3v2v1s(c),u3s(c)的最短路径有2条,表示为u3v5v3v2v1s(c),u3v5v4v2v1s(c),故可得到σ(u2,c)=1,σ(u3,c)=2.因此,用户U={u1,u2,u3}请求内容块c时的总最短路径数目为4,即其中,经过缓存节点v1的最短路径有4条,经过缓存节点v2的最短路径有3条,依次类推,对于缓存节点v3v4v5,分别存在因此,从图1中可以看出,当用户请求内容块c时,缓存节点v1具有最大的位置中心性.然而,若根据传统的介数中心性定义计算,缓存节点v2具有最大的位置中心性.假设内容块c的流行度为0.2,根据式(1)可以计算得出缓存节点v1v2v3v4v5关于内容块c的内容中心性分别为CC(v1,c)=1/5,CC(v2,c)=3/20,CC(v3,c)=1/10,CC(v4,c)=1/20,CC(v5,c)=1/10.因此,缓存节点v1在用户请求内容块c时更加重要.

Fig. 1 Example illustration of CC metric
图1 CC指标的示例说明

2.3 内容获取时延

为了衡量缓存内容放置给网络中用户获取内容带来的时延减少,本文定义了内容获取时延节省(delay saving, ds)指标,ds指标刻画了用户从缓存节点获取内容时所需要的时延相比于从源服务器获取内容时所需要时延的减少量.为简化问题,本文采用节点跳数来量化时延,则ds指标可量化定义为

dsu,v,c=hops(c)(c,u)-hopv(c,u),

(2)

其中,hops(c)(c,u)表示用户u从源服务器s(c)获取内容块c时所需要的跳数;hopv(c,u)表示用户u从缓存节点v获取内容块c时所需要的跳数;dsu,v,c表示用户u从缓存节点v上获取内容块c的时延节省量.

2.4 模型建立

为兼顾内容中心性和内容获取时延2方面优化目标,我们的缓存内容放置问题可描述为:给定网络结构,在各缓存节点可利用缓存容量一定的前提下,如何合理地将内容存放到缓存节点上,即通过尽可能放置最少的缓存内容块数目以最大化内容获取收益.

针对我们的缓存内容放置问题,可构造整数线性规划的优化模型:

(3)

(4)

xv,c∈{0,1},

(5)

(6)

其中,λv,c表示内容块c在节点v上的平均请求速率;dsu,v,c表示用户u在节点v上获取内容块c的时延节省;CC(v,c)表示节点v关于内容块c的内容中心性;xv,c是一个0-1变量,表示节点v是否缓存内容块c,当xv,c=1时,则在节点v上缓存内容块c,当xv,c=0时,则在节点v上不缓存内容块cCS(v)表示节点v的最大缓存容量;pc表示内容块c的流行度;V表示缓存节点集合;C表示内容块集合.目标函数式(3)以最大化内容获取收益为目标,兼顾了内容中心性和内容获取时延2方面的优化目标;约束式(4)是对缓存节点上放置的内容进行容量限制.

根据式(3)~(6)可以看出,目标函数和约束条件均为线性,且变量xv,c的取值为0或1,因此,本文缓存内容放置问题属于0-1整数线性规划(integer linear programming, ILP)问题.

本文的缓存内容放置问题是NP完全问题.首先,该问题任意一个可能的解,都可以在多项式时间内判断其是否是可行解,因此该问题的判定问题是NP问题.其次,为证明该问题是NP完全问题,可以通过将该问题的ILP问题规约为3-CNF-SAT问题,以证明其是NP完全问题[19-20].

3 CCPCP方法

为求解本文缓存内容放置问题,通过分析其优化模型,本文提出了基于内容中心性的概率缓存内容放置方法CCPCP.假定ICN是由具有缓存功能的路由器节点(缓存节点)、始终存储内容的服务器和发送内容请求的用户组成.在ICN中包括2种数据类型:兴趣包和数据包.兴趣包中包含用户所请求的内容对象的名字,数据包中包含用户所请求的内容对象.用户以发送兴趣包的方式从网络中获取所需的内容对象,收到该兴趣包且存储相应内容的服务节点(服务器或者具有缓存功能的路由器节点)按照相反的路径将数据包回传给用户.路由器节点可以通过缓存策略对所经过的内容对象进行缓存,同时通过查询和维护内容存储表(content store, CS)、待定兴趣表(pending interest table, PIT)、转发信息表(forwarding infor-mation base, FIB)这3种表从而实现路由和转发功能.内容对象以分块的形式进行缓存和传输,且所有内容块具有相同的大小.

3.1 基本思想

根据我们缓存内容放置问题的优化模型可知,最大化内容获取收益的目标主要有内容中心性和内容获取时延节省2方面因素的影响.因此,我们提出了基于内容中心性的概率缓存内容放置方法.该方法的基本思路是,在数据包返回过程中,沿途具有缓存功能的路由器节点依据一定的缓存概率对经过的内容对象进行缓存决策.缓存概率综合考虑了内容中心性和内容获取时延节省,与内容中心性和内容获取时延节省成正比.内容中心值越大,内容获取时延节省越大,则内容对象在该节点的缓存概率越大.

为了便于计算,我们需将内容中心性指标和内容获取时延指标标准化到0~1之间,归一化公式为

(7)

其中,norCC(v,c)表示相对内容中心性;CC(u,s(c))max表示用户u请求内容块c的最短路径上所经过的中间缓存节点的最大内容中心性值:

(8)

其中,nords(v,c)表示相对内容获取时延节省;d(u,s(c))表示用户u访问服务器s(c)所需要的跳数.

因此,根据内容中心性和内容获取时延的定义,缓存概率的计算为

(9)

其中,P(v,c)表示内容块c在缓存节点v上的缓存概率.

3.2 CCPCP方法过程描述

本节主要描述CCPCP方法的工作过程,主要包括兴趣包处理和数据包处理2方面:

1) 兴趣包处理.当用户想获取某个内容时,向网络中发送请求该内容的兴趣包.该兴趣包依据最短路径在网络中的路由器上进行转发,并记录用户请求内容的最短路径上所经过的中间缓存节点的最大内容中心性CCmax和到达内容请求响应节点所经过的跳数hop.当路由器(缓存节点)接收到该兴趣包,首先查找CS表中是否有相应的缓存内容.如果有,则直接将相应的内容数据返回给用户,并丢弃兴趣包;如果没有,则查找PIT表中是否有关于该内容的请求记录.如果有,则在原有的相应条目中添加该兴趣包的接入端口,并丢弃兴趣包;如果没有,则在PIT表中新增一条信息,并查找FIB表中记录的转发端口,将兴趣包转发至下一跳路由器节点,并更新相关记录信息CCmaxhop.直到转发至内容服务节点.

在兴趣包转发过程中,由全局控制器收集网络拓扑信息和用户的内容请求信息,并根据收集的相关信息计算出内容流行度、内容中心性指标和内容获取时延指标.

2) 数据包处理.当兴趣包在内容服务节点得到响应时,内容服务节点会返回一个包含相应请求内容的数据包.该数据包沿着与兴趣包的转发路径相反的路径进行回传,并根据兴趣包中记录的相关信息CCmaxhop来记录用户到达内容请求响应节点的最短路径上所经过的中间缓存节点的最大内容中心性CC(u,s(c))max和用户到内容源服务器的最短路径距离d(u,s(c)).其中,d(u,s(c))=dsu,w,c+hopw表示内容请求响应节点,dsu,w,c表示内容请求响应节点的内容获取时延节省,CC(u,s(c))max=CCmax.

当数据包转发至具有缓存空间的路由器节点,依据CCPCP方法的概率公式计算出该路由器节点对于数据包中相应的内容的缓存概率,并根据缓存概率决策是否缓存该数据包中的相应内容.如果路由器节点决定缓存该内容且缓存空间未满,则直接对该内容进行备份并转发至下一跳路由器节点;如果决定缓存该内容但缓存空间已满,则根据广泛使用的LRU(least recently used)缓存替换策略[21]进行替换缓存,即通过删除最近最少使用的内容为新内容提供缓存空间,并转发至下一跳路由器节点;如果不缓存该内容,则直接转发至下一跳路由器节点.直到用户接收到返回的数据包.

在数据包返回过程中,路由器节点可通过节点间相互协作来获取路径长度[20].对于距离的具体统计方法,已有研究工作进行详细介绍,因此,本文不将其作为研究重点.

3.3 CCPCP方法实现

以一个用户u请求内容块c为例,描述CCPCP方法中兴趣包和数据包的处理过程.算法1主要表示缓存节点对兴趣包处理的实现,算法2主要表示缓存节点对数据包处理的实现.

算法1. 兴趣包处理过程.

① 初始化CCmax=0; /*CCmax记录最短路径上所经过的中间缓存节点的最大内容中心性*/

hop=0; /*hop记录到达内容请求响应节点所经过的跳数*/

③ for用户u到内容源服务器s(c)的最短路径上的每一个缓存节点v

④ if在缓存节点v缓存命中

⑤ return内容数据;

⑥ else /*缓存节点v没有缓存命中*/

⑦ if CC(v,c)>CCmax

CCmax=CC(v,c); /*更新CCmax值*/

⑨ end if

hop=hop+1; /*更新hop值*/

转发兴趣包至下一跳缓存节点;

end if

end for

算法2. 数据包处理过程.

① 从兴趣包中记录相关信息CCmaxhop

CC(u,s(c))max=CCmax; /*记录最短路径上所经过的中间缓存节点的最大内容中心性*/

d(u,s(c))=dsu,w,c+hop; /*记录用户u到内容源服务器s(c)的最短路径距离*/

④ for内容源服务器s(c)或缓存命中节点到用户u的最短路径上的每一个缓存节点v

P(v,c)=pc×[dsu,v,c/d(u,s(c))]×[CC(v,c)/CC(u,s(c))max]; /*依据式(9)计算缓存概率*/

⑥ 以概率P(v,c)决策是否缓存内容块c

⑦ if缓存该内容

⑧ if缓存空间未满

⑨ 在缓存节点v上缓存内容块c

⑩ else /*缓存空间已满*/

依据LRU缓存替换策略进行缓存;

end if

end if

转发数据包至下一跳缓存节点;

end for

4 仿真实验与分析

4.1 仿真设置

为了验证CCPCP方法的有效性,本文选取了具有代表性的处处缓存方法LCE[1]、随机概率缓存方法Prob(p=0.3,p=0.5,p=0.7)[16]、基于最大化缓存收益的概率缓存方法MBP[13]和我们的CCPCP方法进行对比.其中,对比仿真实验中缓存替换策略均采用LRU策略[21].

仿真实验中选取了具有代表性的Zachary空手道俱乐部网络和基于BA模型生成的网络来进行仿真分析,其中,Zachary网络是一个包含34个节点和78条边的“基准”社会网络,而包含100个节点的BA网络是典型的无标度网络.在网络中设置1个内容源服务器节点.假设每个路由器节点具有相同的缓存容量,且连接有相同数量的用户.用户的请求过程服从泊松分布,用户的请求模式服从Zipf分布.仿真实验的主要参数设置如表2所示:

Table 2 Experiment Parameters
表2 实验参数

ParameterValueRequest Rate∕(req·s-1)200Number of Content500-4000Default Number of Content1000Zipf Parameter α0.6-1.3Default Zipf Parameter α1.0Cache Capacity10-50Default Cache Capacity30Number of Users100

4.2 评价指标

为评估CCPCP方法性能,本文采用了缓存命中率和跳数减少率2个典型的评价指标,新定义了缓存内容利用率这个评价指标.

1) 缓存命中率

缓存命中率(cache hit ratio, CHR),刻画缓存方法减轻服务器负载的能力.缓存命中率越高,服务器负载的压力越小,缓存系统的效率就越高.其定义为由缓存节点而不是源服务器节点响应用户请求的概率:

CHR=h/r,

(10)

其中,h表示在缓存节点得到响应的内容请求次数,r表示用户发送的所有内容请求总数.

2) 跳数减少率

跳数减少率(hop reduction ratio, HRR),刻画了内容请求用户获取请求内容的时延节省量.跳数减少率越高,用户获取内容所需的时延越少,缓存系统的响应速度就越快.其定义为

(11)

其中,d表示内容请求在缓存节点或源服务器节点得到响应所需的访问跳数,D表示所有内容请求只在源服务器节点得到响应所需的访问跳数.假设r表示用户发送的所有内容请求总数,表示用户从缓存节点或资源服务器获取r个请求内容的跳数总和,表示用户只能从资源服务器获取r个请求内容的跳数总和.

3) 缓存内容利用率

为刻画有限缓存空间下缓存内容资源被利用程度,本文提出了缓存内容利用率(caching content utilization ratio, CCUR)指标.该指标表明缓存内容副本数目越少,缓存内容命中率越大,则缓存内容利用率就越大.该指标也反映了缓存内容副本的共享度,缓存内容利用率越大,缓存内容副本的共享度就越高,缓存系统的效率也就越高.CCUR指标定义为

(12)

其中,hc表示内容块c请求命中次数,rc表示内容块c的所有请求总数,N表示缓存的内容副本总数.

4.3 实验结果

本节主要分析内容数量、Zipf分布参数以及节点缓存容量3个关键参数对不同缓存内容放置方法性能影响.

为了观察某个参数对缓存性能的影响,本节各组实验中只有单方面参数的取值发生变化,而其他参数保持不变,其取值如表2所示.此外,为比较CCPCP方法与其他缓存方法的性能,本文实验是在确保CCPCP方法的缓存内容副本数目不超过对比方法的缓存内容副本数目的前提下进行的.

1) 内容数量影响分析

在该组实验中,比较LCE,Prob0.3(p=0.3),Prob0.5(p=0.5),Prob0.7(p=0.7),MBP,CCPCP方法作用下,随着网络中内容数量的增加,缓存命中率、跳数减少率和缓存内容利用率3方面指标的变化情况,并比较了不同内容数量取值时,各缓存方法的缓存内容副本数目.

从图2和图3中可以看出,不论对于Zachary网络,还是对于BA网络,随着网络中内容数量的增加,各缓存方法的缓存命中率和跳数减少率整体都呈现出下降趋势.这是由于随着网络中用户请求内容数量的增加,需要缓存的内容块增多,而节点的缓存空间有限,在缓存节点中命中内容请求的概率减小,从而导致缓存性能减弱.可以看出,与Prob方法相比,MBP方法虽然在缓存命中率方面效果稍差但在跳数减少率方面有一定的优势,这是由于MBP方法考虑了内容热度和内容获取时延节省收益,以便用户更快地获取内容.但是,即使缓存性能随着内容数量的增加而减弱,CCPCP方法的缓存命中率和跳数减少率仍一直高于其他缓存方法.

Fig. 2 The impact of number of content on cache hit ratio
图2 内容数量对缓存命中率的影响

Fig. 3 The impact of number of content on hop reduction ratio
图3 内容数量对跳数减少率的影响

从图4可以看出,随着内容数量的增加,CCPCP方法的缓存内容利用率一直明显高于其他缓存方法,尤其是MBP方法和LCE方法.这是因为CCPCP方法考虑到了缓存节点在网络结构中的位置重要性,居于中心的缓存节点具有更高的缓存访问概率.而MBP方法仅关注用户获取内容时延最大化收益目标,倾向于在边缘节点上放置内容,从而降低缓存内容利用率.LCE方法则主张处处缓存,存在大量缓存冗余,导致缓存利用率低.此外,对于不同内容数量取值下,缓存内容利用率呈现折线状态这一现象,是因为在不同的内容数量取值下,缓存内容的命中率和缓存的内容副本数目也有所不同,如图5所示.其中,从图5(b)可以看出,与其他缓存方法相比,CCPCP方法中部署的缓存内容副本数目较少,减少率不低于32%.当内容数量取值为3 500时,CCPCP方法缓存内容副本数目的减少率最大可达到34.7%.缓存内容副本数目减少率量化为,对比缓存方法中部署缓存内容副本数目与CCPCP方法中部署缓存内容副本数目的差值与对比缓存方法中部署缓存内容副本数目的比值.其中图5(b)中最大的减少率是内容数量取值为3 500时,(690-450)/690的近似值.

Fig. 4 The impact of number of content on caching content utilization ratio
图4 内容数量对缓存内容利用率的影响

Fig. 5 The number of content replicas with different number of content
图5 不同内容数量所对应的缓存内容副本数目

2) Zipf分布参数影响分析

现有研究表明用户对内容请求模式服从Zipf分布[22],Zipf分布的参数α越大,表明用户对内容请求的偏好越集中.在该组实验中,通过改变参数α的取值,来研究不同的用户请求偏好对缓存性能的影响.图6~8分别展示了在不同缓存方法作用下,Zipf参数变化对缓存命中率、跳数减少率和缓存内容利用率的影响.图9展示了不同Zipf参数取值下,各缓存方法的缓存内容副本数目.

从图6和图7可以看出,Zachary网络和BA网络,随着参数α取值的增加,各缓存方法的缓存命中率和跳数减少率都逐渐增大.这是由于随着偏度参数的增大,用户对内容请求的偏好变得更集中,高流行度的内容具有更大的请求概率,导致受欢迎的内容和不受欢迎的内容之间的差距越来越大.因此,缓存具有更高流行度的内容可以获得更多的缓存收益,从而提高缓存性能.如图6~8中图(b)所示,对于BA网络,当参数α=0.6,0.7,0.8时,CCPCP方法和Prob0.7(p=0.7)方法在缓存命中率和跳数减少率方面具有近乎相同的效果.但是,CCPCP方法的缓存内容利用率却明显优于Prob0.7方法.这是因为在相同的实验场景下,CCPCP方法放置了更少的缓存内容副本,达到了Prob0.7方法近似相同甚至更好的缓存效果.其中,与其他缓存方法相比如图9所示,CCPCP方法缓存内容副本数目的减少率不低于36%,尤其当α=0.8时,减少率可达到39.6%.

Fig. 6 The impact of Zipf parameter on cache hit ratio
图6 Zipf分布参数对缓存命中率的影响

Fig. 7 The impact of Zipf parameter on hop reduction ratio
图7 Zipf分布参数对跳数减少率的影响

Fig. 8 The impact of Zipf parameter on caching content utilization ratio
图8 Zipf分布参数对缓存内容利用率的影响

Fig. 9 The number of content replicas with different Zipf parameter
图9 不同Zipf分布参数所对应的缓存内容副本数目

Fig. 10 The impact of cache capacity on cache hit ratio
图10 节点缓存容量对缓存命中率的影响

同时,从图8中可以看出,CCPCP方法的缓存内容利用率一直高于其他缓存方法.此外,从图6~8中可以看出,与CCPCP方法和MBP方法相比,Prob方法和LCE方法的性能提升速度较慢,尤其是在跳数减少率方面.究其原因是Prob方法和LCE方法没有考虑内容的受欢迎程度.

3) 节点缓存容量影响分析

本组实验中,通过改变节点缓存容量的大小,研究变化节点缓存容量在不同缓存方法作用下,对缓存命中率、跳数减少率和缓存内容利用率的影响,并比较了不同缓存容量取值时,各缓存方法的缓存内容副本数目.

从图10~12可以看出,随着节点缓存容量的增加,各缓存方法的缓存命中率和跳数减少率都有所提高.这是由于随着节点缓存容量的增大,网络中缓存内容副本逐渐增多,在缓存节点中命中内容请求概率增大,从而改善了整体缓存性能.但是,如图13所示,随着节点缓存容量的增加,各缓存方法的缓存内容利用率整体上呈现下降趋势,其原因是网络中缓存的内容副本数量随着缓存容量的增加而增长.总体来说,与其他方法相比,在缓存内容副本数目较少的情况下,CCPCP方法一直表现出更优的性能.

Fig. 11 The impact of cache capacity on hop reduction ratio
图11 节点缓存容量对跳数减少率的影响

Fig. 12 The impact of cache capacity on caching content utilization ratio
图12 节点缓存容量对缓存内容利用率的影响

Fig. 13 The number of content replicas with different cache capacity
图13 不同节点缓存容量所对应的缓存内容副本数目

根据实验结果可以看出,随着内容数量、Zipf分布参数和节点缓存容量的改变,CCPCP方法在缓存命中率、跳数减少率和缓存内容利用率这3方面评价指标都优于其对比的基于概率的缓存方法和LCE缓存方法.这是因为CCPCP方法综合考虑了内容中心性和内容访问时延2方面的关键因素,从而在相同的缓存内容副本数量甚至更少的缓存内容副本数量的情况下,能够改善缓存内容的命中率,提高缓存资源的利用率,降低用户访问内容所需的时延.

4.4 性能分析讨论

CCPCP方法的一个核心内容是缓存概率的计算.从式(9)中可以看出,主要包括内容中心性、内容获取时延和内容流行度3个因素.其中,内容中心性的计算复杂度较大,因为网络中的内容是繁多且不断增长的.对此,可以采用优化的内容中心性计算方法[17]以及使用具有高性能的全局控制器获取网络拓扑信息并进行相关计算.此外,当网络拓扑、内容存放位置以及内容流行度稳定时,内容中心性指标值不会发生变化.此时,内容中心性指标计算所带来的时延影响较小.

5 结束语

为提高面向内容的网络系统的网内缓存效率,本文提出了一种基于内容中心性的概率缓存内容放置方法CCPCP.在CCPCP方法中,本文扩展了内容中心性指标,该指标不仅能刻画缓存节点的位置中心属性,而且能刻画信息内容本身的属性.本文提出的CCPCP方法兼顾了内容中心性和内容获取时延2方面的优化目标,能够将内容合理地放置到缓存节点中,以提高缓存资源的利用率,减少缓存冗余,降低内容获取时延.仿真实验表明,CCPCP方法通过合理部署相同数目的甚至较少的缓存内容资源,在缓存命中率、跳数减少率和缓存内容利用率等评价指标上都优于对比的基于概率的缓存方法.

现阶段,本文CCPCP方法仅适用于中小规模网络.为了扩大CCPCP方法适用范围,在下一步工作中可考虑结合软件定义网络(software-defined networking, SDN)的架构,利用其控制层的特征来感知网络的动态拓扑信息,并对内容中心性指标的计算方法进行优化改进,以降低其计算复杂度.

考虑到实际网络结构是动态的,而且内容流行度也是变化的,未来我们将进一步优化我们的模型和方法,探索移动社交网络环境中缓存内容资源的优化部署问题.

参考文献

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

[2]Koponen T, Chawla M, Chun B G, et al. A data-oriented (and beyond) network architecture[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 181-192

[3]Dannewitz C, Kutscher D, Ohlman B, et al. Network of information (NetInf)—An information-centric networking architecture[J]. Computer Communications, 2013, 36(7): 721-735

[4]Kitsuwan N, Tahara H, Oki E. Heuristic approach to determining cache node locations in content-centric networks[J]. IEEE Access, 2018, 6: 1542-1549

[5]Ahlgren B, Dannewitz C, Imbrenda C, et al. A survey of information-centric networking[J]. IEEE Communications Magazine, 2012, 50(7): 26-36

[6]Zhang Guoqiang, Li Yang, Lin Tao, et al. Survey of in-network caching techniques in information-centric networks[J]. Journal of Software, 2014, 25(1): 154-175 (in Chinese)(张国强, 李杨, 林涛, 等. 信息中心网络中的内置缓存技术研究[J]. 软件学报, 2014, 25(1): 154-175)

[7]Chen Long, Tang Hongbo, Luo Xingguo, et al. Gain-aware caching scheme for information-centric networking[J]. Journal on Communications, 2016, 37(5): 130-142 (in Chinese)(陈龙, 汤红波, 罗兴国, 等. 基于收益感知的信息中心网络缓存机制[J]. 通信学报, 2016, 37(5): 130-142)

[8]Cai Jun, Liu Yan, Luo Jianzhen, et al. Social community-aware caching strategy in information-centric networking[J]. Journal of Central South University: Science and Technology, 2018, 49(5): 123-129 (in Chinese)(蔡君, 刘燕, 罗建桢, 等. 社团感知的ICN缓存策略[J]. 中南大学学报: 自然科学版, 2018, 49(5): 123-129)

[9]Chai W K, He Diliang, Psaras I, et al. Cache “less for more” in information-centric networks (extended version)[J]. Computer Communications, 2013, 36(7): 758-770

[10]Cai Yueping, Liu Jun, Fan Xinwei. Node centrality metric based caching mechanism in content-centric network[J]. Journal on Communications, 2017, 38(6): 10-18 (in Chinese)(蔡岳平, 刘军, 樊欣维. 基于节点中心性度量的内容中心网络缓存机制[J]. 通信学报, 2017, 38(6): 10-18)

[11]Psaras I,Chai W K, Pavlou G. Probabilistic in-network caching for information-centric networks[C] //Proc of the 2nd of the ICN Workshop on Information-Centric Networking. New York: ACM, 2012: 55-60

[12]Ren Jing, Qi Wen, Westphal C, et al.MAGIC: A distributed max-gain in-network caching strategy in information-centric networks[C] //Proc of the 2014 IEEE Conf on Computer Communications Workshops. Piscataway, NJ: IEEE, 2014: 470-475

[13]Wu Haibo, Li Jun, Zhi Jiang, et al.Design and evaluation of probabilistic caching in information-centric networking[J]. IEEE Access, 2018, 6: 32754-32768

[14]Zhi Jiang, Li Jun, Wu Haibo, et al. Edge-first-based cooperative caching strategy in information centric networking[J]. Journal on Communications, 2017, 38(3): 53-64 (in Chinese)(智江, 李俊, 吴海博, 等. 基于边缘优先的ICN缓存协作策略[J]. 通信学报, 2017, 38(3): 53-64)

[15]Laoutaris N, Syntila S, Stavrakakis I. Meta algorithms for hierarchical Web caches[C] //Proc of the 2004 IEEE Int Conf on Performance, Computing and Communication. Piscataway, NJ: IEEE, 2004: 445-452

[16]Laoutaris N, Che Hao, Stavrakakis I. The LCD interconnection of LRU caches and its analysis[J]. Performance Evaluation, 2006, 63(7): 609-634

[17]Khan J A, Westphal C, Ghamri-Doudane Y. A content-based centrality metric for collaborative caching in Information-centric fogs[C/OL] 2017: 1-6. [2020-00-00]. https://www.researchgate.net/publication/316662393_A_Content-based_Centrality_Metric_for_Collaborative_Caching_in_Information-Centric_Fogs

[18]Khan J A, Westphal C, Garcia-Luna-Aceves J J, et al. NICE: Network-oriented information-centric centrality for efficiency in cache management[C] //Proc of the 5th ACM Conf on Information-Centric Networking. New York: ACM, 2018: 31-42

[19]Chen Zhiping, Xu Zongben.Computer Mathematics: Computational Complexity Theory and Solution of NPC and NP-hard Problems[M]. Beijing: Science China Information Sciences, 2001 (in Chinese)(陈志平, 徐宗本. 计算机数学: 计算复杂性理论与NPC,NP难问题的求解[M]. 北京: 科学出版社, 2001)

[20]Wu Haibo, Li Jun, Zhi Jiang. Probability-based heuristic content placement method for ICN caching[J]. Journal on Communications, 2016, 37(5): 62-72 (in Chinese)(吴海博, 李俊, 智江. 基于概率的启发式ICN缓存内容放置方法[J]. 通信学报, 2016, 37(5): 62-72)

[21]Podlipnig S, Boszormenyi L. A survey of Web cache replacement strategies[J]. ACM Computing Surveys, 2003, 35(4): 374-398

[22]Breslau L, Cao Pei, Fan Li, et al. Web caching and Zipf-like distributions: Evidence and implications[C] //Proc of the 18th Annual Joint Conf of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 1999: 126-134

Probabilistic Caching Content Placement Method Based on Content-Centrality

Li Li1, Liu Huanyu1, and Lu Laifeng2

1(School of Computer Science and Technology, Shaanxi Normal University, Xian 710119)

2(School of Mathematics and Information Science, Shaanxi Normal University, Xian 710119)

Abstract A content-centrality-based probabilistic caching content placement method (CCPCP) is proposed to reduce cache redundancy as well as achieve better performance in terms of cache hits and utilization in information-centric networking (ICN). Different from those metrics that focus only on the centrality based on topology in the traditional network, the content centrality metric is developed in this paper. The content centrality metric not only describes the location centrality of cache nodes, but also describes the attribute of the content. In CCPCP method, each cache node individually makes a cache decision with a certain caching probability. In particular, each cache node adaptively calculates the caching probability by jointly considering the content centrality and the delay savings, which is proportional to the location centrality, the content popularity and the access delay savings. That is, the larger location centrality of cache node, the higher popularity of content, the more access delay savings, and the larger the caching probability of cache node caching the passing content. Simulation results show that CCPCP outperforms the state-of-art probabilistic methods in terms of cache hit ratio, caching content utilization ratio, access delay and cache redundancy under the less number of content replicas, even in the case that the reduction of number of content replicas is up to 32%.

Key words information-centric networking; caching content placement; content centrality; cache redundancy; caching content utilization

(lili@snnu.edu.cn)

中图法分类号 TP393

DOI:10.7544/issn1000-1239.2020.20190704

收稿日期2019-09-29;修回日期:2020-04-14

基金项目国家重点研发计划项目(2017YFB1402102);国家自然科学基金项目(61303092,61702317);陕西省自然科学基础研究计划项目(2020JM-290,2020JM-288);中央高校基本科研业务费专项资金(GK201903093,GK201903011)

This work was supported by the National Key Research and Development Program of China (2017YFB1402102), the National Natural Science Foundation of China (61303092, 61702317), the Shaanxi Province Natural Science Basic Research Foundation (2020JM-290, 2020JM-288), and the Fundamental Research Funds for the Central Universities (GK201903093, GK201903011).

通信作者鲁来凤(lulaifeng@snnu.edu.cn)

Li Li, born in 1979. PhD, associate professor, MSc supervisor. Her main research interests include network resource optimization and allocation, software-defined networking, information-centric networking, and network science and its applications.

Liu Huanyu, born in 1995. MSc. Her main research interests include information-centric networking, and network resource optimization and allocation.

Lu Laifeng, born in 1979. PhD, associate professor, MSc supervisor. Member of CCF. Her main research interests include wireless network, network security, and privacy protection.