内容分发网络中基于相关内容吸引的缓存算法

张 成,杨东风,黄 协,张根耀

(延安大学a.数学与计算机科学学院;b.网络信息中心,陕西延安716000)

内容分发网络中基于相关内容吸引的缓存算法

张 成a,b,杨东风a,黄 协b,张根耀a

(延安大学a.数学与计算机科学学院;b.网络信息中心,陕西延安716000)

内容分发网络中基于内容名的缓存算法会导致路由表规模随网络增长而膨胀,将严重影响网络路由效率和性能。针对该问题,提出一种基于相关内容吸引的节点缓存算法。利用本地缓存算法,通过节点已缓存内容对其他内容的吸引作用吸引主要特征内容,排斥具有次要特征内容,将缓存中不同特征内容的数量差异进行放大,使缓存内容表现出明显稳定的内容特征。同时设计相关内容生存时间相互增强的缓存策略,以减少路由通告信息量,提高内容分发网络的路由能力。实验结果表明,该算法在有效解决路由问题的同时,能增强缓存内容稳定性,提高路由可信度。

内容分发网络;缓存算法;内容吸引;缓存因子;缓存冗余;路由

1 概述

内容分发网络(Content Delivery Network, CDN)是一种全新的网络体系结构[1],采用了基于内容名的路由方式对内容和位置进行解耦合,使用户能够直接访问内容本身而不需要关心其所在位置[2]。为了找到离用户最近的目标内容,网络节点需要向外通告缓存中的内容[3]。缓存内容难以进行内容名前缀聚合且产生大量路由更新消息是导致内容分发网络的路由可扩展性问题研究中亟待解决的主要问题[4]。

针对缓存内容难以聚合且更新频繁的问题,本文提出一种基于相关内容吸引的缓存算法(CA),通过具有相同特征的内容相互吸引,将缓存中不同特征内容的数量差异进行放大,使缓存内容表现出明显稳定的内容特征,从而在缓存资源有限的情况下提高缓存内容的内容名前缀聚合程度,方便通过内容特征抽象减少路由通告的信息量,同时通过相关内容的生存时间相互增强使缓存中具有主要内容特征的内容更不容易被丢弃,降低缓存内容的更新频率,避免造成过大的网络开销,以提高网络的路由扩展能力。

2 相关研究

现有网络体系结构以地址/位置为中心的设计模式与用户关心内容本身而非其所在位置的特点不符,从而带来流量集中化、链路重复传输等一系列影响内容分发效率的问题[5]。已有的解决方案,如内容分发网络[6]、P2P[7]等,都是在现有网络架构的基础上部署更加复杂的功能来实现,一方面带来新的固有问题,另一方面使网络体系结构更复杂,难以从根本上解决现网面临的难题[8]。内容分发网络采用流媒体服务器集群技术,提升系统支持的并发流,利用全局负载均衡技术将用户的访问指向离用户最近的缓存服务器,由流媒体服务器直接响应用户的请求[9]。与 IP网络相比,内容分发网络面临更严重的路由问题,其内容的更新频率要高得多。新内容的产生以及缓存内容的快速替换导致大量的更新消息使网络开销大量增加,影响路由性能。

LCE[10](Leaving Copies Everwhere)是目前内容分发网络研究中常用的缓存算法,路由路径上的所有节点都对内容文件进行缓存,LCE简单且易于部署,具有良好的缓存性能。然而,LCE算法会造成非常频繁的缓存更新和严重的缓存冗余,带来巨大网络开销[6];ProbCache算法减小了路径上的缓存冗余,提高了缓存资源的利用率,但是ProbCache没有考虑到内容之间的热门程度差异,不符合大量用户访问少量热门内容的特点,因此,在缓存资源管理方面还有很大的改进空间[11];TopDown算法根据内容热门度确定内容是否被缓存以及缓存位置,流行度高的内容被缓存在网络的“枢纽”位置,而流行度较低的内容则被缓存在离用户更近的位置。上述算法的共同问题是缓存中内容特征分布具有很强的随机性,表现为没有突出的主要内容特征以及稳定的特征分布[12],因而难以通过内容特征抽象减少向外通告的路由信息量,导致严重的路由可扩展性问题。在早期的研究中,研究者们试图将复杂网络拓扑映射到欧氏空间[13]中,但得到的实验结果非常不理想,路由成功率非常低。随着研究的进展,研究者们发现双曲空间由于具有负曲率,其空间增长服从指数分布,与复杂网络的拓扑增长特性类似,在双曲空间中构建的复杂网络模型能够天然地表现出幂律特性[14]。因此,本文根据真实网络的拓扑连接关系确定双曲空间中的坐标分布,从而使双曲空间中的坐标距离关系与真实网络的连接关系趋于一致。

3 相关内容吸引的缓存算法

3.1 算法描述

CA算法的基本原理如下:通过相关内容的相互吸引,使节点的主要内容特征更加突出一致,并排斥具有次要内容特征的内容在节点上的缓存,CA算法基于本地缓存,通过节点已缓存内容对其他内容的吸引作用影响目标内容的缓存。在缓存过程中,具有某一种特征的目标内容基于相关内容特点而更容易被节点缓存,新增缓存内容将增大其后到达该节点的相同特征目标内容被缓存的概率,形成良性循环。随着缓存的进行,节点的内容特征逐渐突出,形成主要内容特征。另一方面,其他特征内容在缓存中所占比例逐渐减小,吸引作用也越来越弱,继而其在缓存中所占比例进一步减小。通过这种方式,节点的主要内容特征逐渐增强,其他内容特征逐渐被削弱,形成节点的内容分布特征。如图1所示,随着各个节点自身特征内容的对相关内容吸引,形成了各个节点的突出内容特征。

图1 相关内容吸引效果

缓存中相关内容之间的相互吸引能使节点的主要内容特征更加稳定,这主要通过缓存内容丢弃策略体现出来。在已有的缓存算法中,决定缓存中的内容是否被替换和丢弃完全是由该内容被访问情况决定的,这种方式是造成缓存更新频繁的重要原因。缓存聚集通过缓存中相关内容的相互吸引,具有主要内容特征的内容更不容易被丢弃,由于具有主要内容特征的内容占据缓存内容的绝大多数,因此这种方式能够大幅降低缓存更新频率。同时,为了保证节点的缓存利用率,本文将缓存中相关内容之间的相互吸引通过相关内容生存时间相互增强的形式表现出来,并将生存时间作为缓存替换和丢弃的唯一衡量指标,保证足够的缓存更新。

图2是CA算法示意图,图中节点缓存中的内容分为主要特征内容和次要特征内容两部分,其占据缓存空间大小用矩形框的长度表示,通过内容吸引的过程和产生的效果,具有主要内容特征的内容占据了更大的缓存空间,使节点的主要内容特征更明显。由于缓存空间有限,若节点出现多个主要内容特征,将会导致每个主要内容特征由于吸引力不够导致节点内容特征度降低。为了避免出现多个主要内容特征,主要特征内容之间的生存时间相互增强,次要特征内容则被丢弃。例如增强路由聚合时,如果聚合后的内容名前缀没有覆盖大量该前缀下的内容名,将会使路径变长,影响路由性能。这是由于缓存空间有限,为了使内容特征抽象具有更高的可信度,节点需要集中资源大量存储某一特征的内容,避免出现多个主要内容特征。CA算法能够在不增强内容和位置耦合程度的条件下,达到现有的基于内容名的路由聚合效果,而且不需要全局的映射,不会引入任何信令开销,因此,不会提高网络的复杂度及增大内容请求时延。同时,由于缓存吸引是以单个节点为单位,因此还有助于降低域内节点的路由表规模,大幅减少路由通告的信息量,增强网络的路由能力。

图2 CA算法示意图

3.2 算法应用分析

CA算法并非一种具体的缓存算法,而是改进节点缓存的思路,可用于改进内容分发网络的节点分布,减轻网络路由压力,减少发布的路由信息。CA算法使具有相同内容名前缀的内容相互吸引,当相同前缀的内容吸引到一定程度时,节点就可以向外通告更短的内容名前缀,从而提高路由聚合。

由于网络节点的内容名是一个多层的结构,因此某一完整内容名将会有不同层次的内容名前缀,此时前缀聚合涉及到如何判定相关内容的问题。内容名前缀聚合是一个逐层聚合的过程,聚合过程是从底层到顶层逐步实现的,因此相关内容吸引基于与目标内容名具有相同的最小聚合前缀的内容,是最小公约集合。为了进一步提高路由聚合程度,缓存吸引算法同样是一个层次化的过程,如图3所示。其中,各节点分别进行最低一层的名字聚合,然后将聚合后的内容名前缀通告出去,接收到路由通告的节点根据相关内容吸引判断是否保存该条路由,通过这种对路由通告有选择地接收,形成图中所示的树状缓存聚集结构。

图3 层次化缓存吸引算法

由于缓存节点根据本地信息无法获取某一内容名前缀下的具体内容信息,因此无法判断是否已经完全缓存了该内容名前缀下的所有内容。若在缓存该前缀下的内容数量不足时进行内容名前缀聚合,则将会因为聚合后的内容名前缀对其所包含的内容覆盖太小而导致路径变长,影响路由性能。然而,根据内容访问的柏拉图定律[15]可知,网络中大量用户会访问少量热门内容,针对这一特点,本文规定节点只需要缓存了某一内容前缀下的所有热门内容,就可以向外通告该内容名前缀。采用这种方式不但能够有效地解决路由聚合判定的问题,还能降低对节点缓存空间的要求,因为热门内容仅占全部内容较小的比例。该方法采用具有某一特征的热门内容代替全部内容,可能会导致非热门内容访问出现绕路行为,但是由于其访问量较少,这种结果是可以被接受的。

为了进一步减少节点的路由表项和网络中的路由更新消息,节点可以只向外通告吸引度最高的内容名前缀,其他未经聚合或聚合程度太低的内容名前缀将不会被通告出去。如图2所示的CA算法过程,由于缓存吸引的作用,节点所缓存的内容多数将具有相同的内容名前缀,不具有相同前缀的内容也因生存时间造成次要内容的丢弃。

4 CA算法实现

在缓存内容吸引的基础上,本文设计了CA算法的详细步骤。该算法借鉴了ProbCache、TopDown等概率缓存算法的思路,采用了多种缓存因子共同用于缓存决策[6]。本文采用的缓存因子包括相关内容因子、内容流行度因子、路径因子、剩余缓存空间因子以及生存时间因子[16],各缓存因子的作用如表1所示。

表1 缓存因子说明

本文涉及到的其他参数含义如下:

为更好地利用缓存空间达到相关内容吸引的效果,CA算法采用了4种缓存因子用于缓存决策。

式(1)表示相关内容因子等于当前节点中与目标内容相关的已缓存内容的有效数量的归一化值。有效数量与每个相关内容的流行度有关,内容越热门,对目标内容的吸引力越强,因此,其有效数量越趋近于1。由于非热门内容的访问量少,对节点内容特征的影响相对较弱,因此,此处采用指数函数这一非线性函数进一步强化热门内容的吸引作用,弱化非热门内容的吸引作用[17]。式(1)中的分子表示目标内容的相关内容有效数量,分母表示缓存中所有内容的有效数量。

内容流行度因子表示为目标内容流行度与内容流行度的最大值的比值,为了使热门内容更容易被缓存,非热门内容更不容易被缓存,本文同样采用指数函数对其进行非线性处理[18],公式如式(2)所示。内容流行度(热度)可以用一段时间内,内容请求经过节点的次数表示。内容的流行度是由用户对内容的访问决定的,内容被访问频率越高,内容流行度越大。每个节点需要处理的用户请求不同,为了节点的缓存命中率,提升用户感受,节点更应该缓存经过本节点频次高的内容,而非全网统一评价出的具有更高流行度的内容,因此,这种方式是合理的。

由于经过节点的内容次数没有固定的上限,因此本文用如下的分段函数将其映射到某一固定的区间内,如式(3)所示。

其中,n为目标内容被请求的次数;a,b为常数;threshold为内容访问次数的阈值。采用二次函数是为了让内容被缓存的概率随请求次数的增长非线性递增,当访问次数总体较少时,增长较缓慢,访问次数达到较高水平时,增长速率更快[19]。

路径因子计算公式如式(4)所示。

为了获取当前节点离用户的距离,需要在内容查找阶段记录路径长度。一种可行的方案是在请求数据包中增加cur_user_dis项,在内容数据包中增加cur_user_dis和path_length项。在内容查找阶段,每转发一次内容请求数据包,请求包中的cur_user_dis项加1;反之,在内容分发阶段,每转发一次,内容包中cur_user_dis项减1。目标节点接收到内容请求包时,将包中的cur_user_dis项复制到内容数据包中的cur_user_dis和path_length中。由于内容分发网络采用对称路由,内容查找和分发的路径相同,因此这种方式是合理的,但不适用于IP网络。

剩余缓存空间因子是为了使有限的缓存空间资源能够得到更加充分的利用,其计算公式如式(5)所示。

其中,Free_Cache_Space表示当前节点的剩余缓存空间可缓存内容的数量;Cache_Space表示总的缓存空间大小;D为常数,非线性处理的目的与上述3种因子相同。

节点对目标内容的缓存概率用上述4种缓存决策因子的加权和表示[20],公式如式(6)所示。

当Cache_Probability大于某一阈值时,内容被缓存。

生存时间因子用于在缓存中维持内容。当内容被缓存时,节点为其设置一个初始生存时间T0,随着时间的进行,生存时间减少,当生存时间减为0时,内容被丢弃。如果缓存中的某一内容在生存时间减为0之前被命中,则其生存时间重置为T0。同时,为了使节点具有更稳定的内容特征,本文规定相关内容的生存时间相互增强,某一内容的相关内容越多,其生存时间越长,越不容易被丢弃。

已缓存的相关内容对目标内容生存时间的增强可用式(7)表示。

其中,Mf表示主要内容特征(Main Feature,MF);E为常数。

当目标内容生存时间增强时,各相关内容的生存时间在当前基础值上增加T′,T′计算公式如下:

相对而言,那些不符合节点内容特征的内容即便被节点缓存,也更容易被丢弃。

4.1 缓存冗余避免

节点在通信的过程中通过对初始内容特征的逐步增强,最终形成稳定的内容特征,并由于其使相同特征内容吸引的特点,当临近的多个节点初始缓存的内容相同时,即存在缓存冗余[22],CA算法还会使初始的缓存冗余得到进一步增强,造成缓存资源的大量浪费。针对这一情况,本文提出路径冗余避免缓存冗余的可行策略。

路径冗余避免缓存冗余在内容数据包的包头中增加已缓存标识字段,用于标识该内容在路径上的缓存情况。当前节点根据这一字段判断目标内容是否被之前的节点缓存,如果已被缓存,则不缓存目标内容或提高缓存概率的阈值。

在内容数据包的包头中增加已缓存标识字段,用于标识该内容在路径上被缓存的次数。在一次路由过程中,内容每被缓存一次,该字段加1。路径上的节点在制定缓存策略时,根据已缓存标识字段的值确定缓存概率的阈值,内容在路径上被缓存的次数越多,缓存概率的阈值越大,这样可以有效避免在一条路径上的重复缓存。缓存概率阈值与被缓存次数的关系如下:

其中,CPT表示缓存概率的阈值;CPT0为初始阈值; Cache_Label表示缓存标识的值;p为内容每缓存一次的增幅。

4.2 算法实现步骤

CA算法的过程如下:

Step 1 当目标内容到达节点时,CA算法首先根据路径冗余避免缓存冗余策略判断是否有临近节点已缓存了相同的内容,以减少或避免缓存冗余。

Step 2 计算目标内容的缓存概率,并判断是否大于设定的阈值。若小于阈值,则不缓存目标内容,转Step 7;否则,转Step 3。

Step 3 缓存目标内容,并为其设置初始生存时间。

Step 4 判断目标内容是否具有主要内容特征,若具有,则转Step 5;否则,转Step 6。

Step 5 增加目标内容及缓存中已有的主要特征内容的生存时间。目标内容生存时间增加量T和已有主要特征内容生存时间增加量T′的计算公式分别为:

Step 6 若缓存空间已满,则丢弃生存时间最小的内容。

Step 7 算法结束。

5 仿真分析

表2 仿真参数

对CA算法和经典的LCE算法能否达到使相同特征内容吸引的效果进行对比,其中,横坐标为缓存节点,纵坐标为内容数量(内容块),其结果如图4所示。可以看出,采用CA算法时,各节点的主要内容特征和次要内容特征对比明显,具有主要内容特征的内容数量远远大于其他特征的内容数量,使节点具有鲜明的内容特征,达到了预期的效果。而采用LCE算法时,由于针对各内容特征内容的请求是随机产生的,因此各节点缓存的每个特征的内容分布比较均匀,难以使某一类特征凸显出来。

图4 节点内容特征分布

对CA算法和LCE及ProbCache算法的缓存更新频率进行对比,结果如图5所示。可以看出,CA算法的缓存更新频率相比于另外2种算法明显降低,这是因为CA算法通过相关内容生存时间相互增强,使占据缓存绝大多数的主要特征内容更难被丢弃,从而增强了缓存内容的稳定性,也使其具有更高的路由可信度。

图5 缓存更新频率

对本文提出的2种缓存冗余避免策略进行对比验证,结果如图6所示。其中,CRA(Cache Redundancy Avoid)指缓存冗余避免;CRA1和CRA2分别指缓存冗余避免方案1及方案2。可以看出,当CA算法不采用缓存冗余避免策略时,其缓存冗余很高,仅次于LCE算法;而采用了本文提出的缓存冗余避免后,缓存冗余性能获得了极大的改善,符合预期效果。

图6 缓存冗余对比

6 结束语

针对内容分发网络不能解决缓存内容聚合的问题,本文提出一种基于相关内容吸引的缓存算法,将具有相同特征的相关内容相互吸引聚合在相同节点上,使缓存内容具有更突出、可信、稳定的内容特征,方便对缓存内容进行特征抽象,以减少路由通知信息量。该算法可以适用于多种应用场景。本文以增强内容名前缀聚合场景为例对其进行了简单的说明,下一步工作是研究如何将该算法应用于其他场景。

[1] Mellado A,Garcia M A,Zahariadis F,et al. Architectures for Future Media Internet[C]// Proceedings of the 2nd International Conference on User Centric Media.Palma de Mallorca,Spain:[s.n.],2012: 105-112.

[2] Pallis G,Vakali A.Insight andPerspectives for Content Delivery Networks[J].Communications of the ACM, 2006,49(1):101-106.

[3] Hei Xiaojun,Liang Chao,Liang Jian,et al.A Measurement Study of a Large-scale P2P IPTV System[J].IEEE Transactions on Multimedia,2007,9(8):1672-1687.

[4] 尹 浩,詹同宇,林 闯.多媒体网络:从内容分发网络到未来互联网[J].计算机学报,2012,35(6): 1120-1130.

[5] Feldmann A.InternetClean-slateDesign:Whatand Why?[J].ACM SIGCOMM ComputerCommunication Review,2007,37(3):59-64.

[6] Ahlgren B,Dannewitz C,Imbrenda C,et al.A Survey of Infor-mation-centric Networking[J].IEEE Communications Magazine,2012,50(7):26-36.

[7] Choi J,Han J,Cho E,et al.A Survey on Contentoriented Networking for Efficient Content Delivery[J].IEEE Communications Magazine,2011,49(3):121-127.

[8] Wang Y,Lee K,Venkataraman B,et al.Advertising Cached Contents in the Control Plane:Necessity and Feasibility[C]//Proceedings of INFOCOM WKSHPS. [S.l.]:IEEE Press,2012:286-291.

[9] Koponen T,Chawla M,Chun B G,et al.A Dataoriented (and Beyond)Network Architecture[J].Proceedings of ACM SIGCOMM Computer Communication Review, 2007,37(4):181-192.

[10] Choi J,Han J,Cho E.et al.A Survey on Contentoriented Networking for Efficient Content Delivery[J].IEEE Communications Magazine,2011,49(3):121-127.

[11] Rajahalme J,Särelä M,Visala K,et al.On Name-based Inter-domain Routing[J].Computer Networks,2011,55 (4):975-986.

[12] Jacobson V,SmettersD K,ThorntonJD,etal. Networking Named Content[J].Communications of the ACM,2012,55(1):117-124.

[13] Boguna M,Krioukov D,Claffy K C.Navigability of Complex Networks[J].Nature Physics,2008,5(1): 74-80.

[14] Yuan H,Crowley P.PerformanceMeasurementof Name-centric ContentDistribution Methods[C]// Proceeding of ANCS'11.[S.l.]:IEEE Press,2011: 223-224.

[15] Boguná M,Papadopoulos F,Krioukov D.Sustaining the Internet with Hyperbolic Mapping[J].Nature Communications,2010,(1).

[16] Fricker C,Robert P,Roberts J,et al.Impact of Traffic Mix onCachingPerformanceinaContent-centric Network[C]//Proceedings of INFOCOM WKSHPS 2012.[S.l.]:IEEE Press,2012:310-315.

[17] Lee U,Rimac I,Hilt V.Greening the Internet with Content-centric Networking[C]//Proceedings of the 1st International Conference on Energy-efficient Computing and Networking.[S.l.]:ACM Press,2010:179-182.

[18] Zhang Lixia,Estrin D,Burke J,et al.Named Data Networking(NDN)Project[Z].2010.

[19] 张 威.毕 军.吴建平.互联网域间路由可扩展性[J].软件学报,2011,22(1):84-100.

[20] Arianfar S,Nikander P,Ott J.On Content-centric Router Design and Implications[C]//Proceedings of the Rearchitecting the Internet Workshop.[S.l.]:ACM Press, 2010:5.

[21] Dhamdhere A,Dovrolis C.Ten Years in the Evolution of the Internet Ecosystem[C]//Proceedings of the 8th ACM SIGCOMM Conference on Internet measurement. [S.l.]:ACM Press,2008:183-196.

[22] Hwang H,Ata S,Murata M.The Impact of FQDN Database Updates on Name-based Routing Architecture [C]//Proceedings of NOMS WKSPS.[S.l.]:IEEE Press,2010:16-21.

编辑 金胡考

Cache Algorithm Based on Related Content Attracting in Content Delivery Network

ZHANG Chenga,b,YANG Dong-fenga,HUANG Xieb,ZHANG Gen-yaoa
(a.College of Mathematics&Computer Science;b.Network&Information Center, Yan'an University,Yan'an 716000,China)

The existing content cache algorithm of Content Delivery Network(CDN)leads to the expansion of routing table with the network increasing,which will impair the routing efficiency and network performance.Therefore,based on related contents attracting,a related contents attracting algorithm is proposed.With the effect of attracting similar contents cached in other near nodes,for the purpose of apparently stable featured contents of nodes cached,the algorithm attracts major characteristic contents,rejects secondary feature contents,and enlarges the difference of different characteristic content.It also gathers the related contents on the same nodes via the mutual attraction with same contents feature,which facilitates the cache contents feature abstraction.Meanwhile,the strategy of lifetime increasement between contents with main feature is designed to deduce the routing advertisement and improve the routing scalability.Experimental results show that the proposed algorithm can reduce the update frequency of cache content,and improve the routing reliability.

Content Delivery Network(CDN);cache algorithm;contents attracting;cache factor;cache redundancy; routing

1000-3428(2014)09-0117-07

A

TN911.22

10.3969/j.issn.1000-3428.2014.09.024

国家自然科学基金资助项目(61379026);陕西省工业攻关计划基金资助项目(2013K06-39)。

张 成(1971-),男,副教授、博士,主研方向:内容分发网络,社交网络,网络安全,服务计算;杨东风,副教授;黄 协,工程师;张根耀,教授。

2013-10-28

2014-03-07E-mail:zc@yau.edu.cn