内容中心网络中基于用户偏好的协作缓存策略

熊 炼，李朋明,，陈 翔，朱红梅

(1.重庆邮电大学 通信工程应用研究所，重庆 400065； 2.移动通信技术重庆市重点实验室(重庆邮电大学)，重庆 400065)(*通信作者电子邮箱2205603330@qq.com)

0 引言

在网络规模高速增长和多样化应用需求不断涌现的今天，网络角色定位已经发生了巨大变化。Cisco全球云指数报告[1]预测，2021年全球IP流量将达到20.6 ZB，其中内容类流量占80%以上。这不但带给网络带宽巨大压力，也表明用户主要需求已变为对海量内容的获取，以“主机到主机”通信为核心的传统架构难以满足未来网络发展需求。为此，研究者们提出以内容为中心的网络架构——内容中心网络(Content-Centric Network, CCN)[2]。CCN架构核心特征之一是网络内建存储，即通过有存储功能的节点将缓存的内容资源高效地共享给更多潜在用户，减少相似数据在网络中的大量重复传输，缓解网络带宽压力。

网络设备的线速转发要求制约着节点缓存容量大小，面对网络中持续产生的海量内容，在相对有限的存储空间下，研究缓存策略、提高缓存系统性能是CCN研究的热点之一。

现有研究为提升缓存系统性能，均从“内容”与“节点”两个角度出发来设计缓存策略。“内容”即缓存的内容，用控制内容冗余[2-5]增加缓存内容多样性，以及考虑内容重要度[6-7]，在有限的空间里缓存更需要的内容。“节点”即缓存节点的选择，仅部分重要节点缓存便能起到较好效果[8]。节点重要性有拓扑和需求上的重要性，用拓扑上边缘节点缓存[9-10]，可以降低用户获取时延；用中心节点缓存[11-13]，可以提高内容分发效率。需求上的重要性即实际需求中某节点的重要度，如考虑以节点处的缓存能耗与收益为节点重要度指标[14]。现有研究考虑内容重要性时忽略了用户对不同内容的偏好，更没有充分结合不同位置节点缓存的独有优势。

为进一步提高缓存内容“质量”，实现内容最佳放置，本文提出一种基于用户偏好的协作缓存策略(Cooperative Caching strategy based on User Preference，CCUP)，结合用户对内容类型的喜好与内容流行度选择性缓存本地偏好内容，通过节点间协作将本地偏好内容与其中全局活跃的内容缓存在最佳位置，达到最佳用户体验、缓存系统性能。

1 相关工作

LCE(Leave Copy Everywhere)[2]是CCN默认缓存机制，要求网络节点缓存所有经过的内容，处处缓存使网络中存在大量冗余副本，缓存空间填满后的频繁替换也会增加缓存处理开销。针对内容冗余问题，LCD(Leave Copy Down)[3]策略仅在命中节点的下一跳复制缓存，在控制冗余的同时将内容逐步推向网络边缘。而用户在边缘节点就近获取内容的同时，上游节点不可避免地会存在冗余副本，随着时间增长冗余会持续增加，未能实现最佳冗余控制。

文献[4]提出ProbCache缓存策略，途径节点以加权概率缓存内容，越靠近边缘缓存概率越大，以概率缓存控制冗余，并利用边缘存储优势。文献[5]提出基于相关概率的协作缓存策略，通过节点间协作以本地缓存状态影响下一跳节点缓存概率大小，以削弱概率缓存的盲目性，进一步控制冗余。

文献[6]提出基于内容流行度的概率缓存策略，以内容请求频率和潜在热度为流行度指标，增大流行内容缓存概率，以提高缓存内容“质量”。结合内容缓存位置，文献[7]将高“质量”内容缓存在中心重要节点，提出基于流行度和生存时间的缓存方案，以流行度决定内容是否向请求经过路径的中间节点缓存，以及内容的生存时间。

文献[8]验证了内容缓存节点的重要性，并提出Betw(cache “less for more”)缓存策略，仅高介数节点缓存内容，利用了中心节点存储便于内容快速分发的特点。而文献[9]则考虑仅边缘节点缓存内容，便于用户就近快速获取内容。文献[10]提出基于边缘优先的缓存协作策略,利用边缘存储优势，结合缓存处理开销的优化;在兴趣包转发阶段边缘节点优先进行缓存决策，方便用户就近获取内容，并减小后续节点不必要的缓存决策开销。文献[8-10]均证明了选择缓存节点的重要性。

为进一步选择缓存节点，文献[11]考虑通过选择缓存位置减少请求跳数，提出了基于介数的最佳缓存位置选择方法，有效减少了请求所需时间；文献[12]考虑提高内容分发效率，提出一种基于内容流行度和节点级别匹配的概率缓存策略，让内容按流行度有序地缓存在中心重要节点；文献[13]则提出一种基于节点中心性度量的缓存机制，由软件定义网络(Software Defined Network, SDN)控制器根据节点中心性度量指标，选择中心度高的节点并向其下发缓存指令，但增加了算法复杂度和对拓扑变化的敏感性。

现有方案均在考虑如何进一步提高缓存内容的“质量”或发挥重要节点的缓存优势，却没有利用不同位置节点的缓存优势，也忽略了用户对不同类型内容的偏好因素，未能充分发挥缓存系统性能。

2 CCUP策略

2.1 CCUP基本原理

CCUP考虑用户偏好进一步提高缓存内容“质量”，对于需要缓存的本地偏好内容，通过节点协作优先将其中全局活跃内容放置在中心重要节点；普通本地偏好内容则根据偏好度级别、与节点距离用户跳数的多少匹配缓存，偏好度越高存储距离用户越近。如图1所示，若A域用户对C1、C2、C3三种类型内容喜好C1>C2>C3，流行度相等的内容h、q、s分别属于以上三类内容，本地偏好度h>q>s，则本地偏好度高的内容h潜在需求更大，缓存优先级应该满足：h>q>s。

图1 分析示例拓扑Fig. 1 Example topology for analysis

对于本地偏好度高的内容h，若非全局活跃则偏好度越高缓存位置应该距A区越近，便于用户获取；若内容全局活跃度高，则缓存在中心节点V5更有利于内容分发。对全局活跃内容的放置以传统方案用节点拓扑的介数、紧密度等为指标，难以将内容准确地放置在最佳节点V5，因此本文以节点处内容实际需求为重要中心节点的选择指标。

本地偏好度指标内容喜好度和流行度定义如下。

定义1 内容喜好度。接入节点统计的用户对此类内容的需求占比(用户接入的第一跳节点为接入节点，接入节点对用户需求最敏感)，表示用户对不同类型内容的需求程度。CM类内容的用户喜好度PM为：

PM=count_M/count_All

(1)

其中:count_M为此类内容请求数;count_All为请求总数。

定义2 内容流行度。一个统计周期T内，节点j中i内容的流行度表示节点j处收到对i内容请求的频率，计算式为：

Lij=count_Ti/count_Tall

(2)

其中:count_Ti为取样时段内i内容的请求次数;count_Tall为统计时段本地收到请求数。但仅考虑一个周期，会将前段时间流行此时已不流行内容，误判为流行内容，不能充分利用各时段内容表现出的流行趋势。所以选择内容流行度CLij如式(3)：

(3)

其中，η1+η2+η3=1，即综合考虑三个周期，仿真中周期权重η1、η2和η3值为0.6、0.3、0.1。内容偏好度Hi为：

Hi=PM·CLij

(4)

考虑本地偏好度高的重要内容中的全局活跃内容的快速分发，进一步提高缓存系统性能，本文将全局活跃内容缓存在中心重要节点。内容活跃度定义如下。

定义3 内容活跃度。中心节点统计的网络中内容i的活跃程度(网络中心节点服务的用户更多，对内容活跃度更敏感)。j节点处i内容的活跃度ADij计算式为：

(5)

其中，DV为内容请求经过节点集合。将更多用户需要的全局活跃内容缓存在重要的中心节点,更利于内容的分发。

2.2 CCUP策略实现

CCUP策略的实现需要在原兴趣包、数据包结构基础上扩展，扩展字段如图2灰色部分。扩展的兴趣包中:Interest Total Hops字段值ITH为请求所经过跳数；Local Importance Level字段值LIL为内容偏好级别；Activity Degree字段值AD为内容全局活跃度；Activity Hop字段用于记录高需求节点的跳数。数据包中:Data Total Hops字段值DTH为数据包历经跳数;Execution Cache Hops字段值ECH为执行缓存跳数。

图2 包结构扩展Fig. 2 Extension of packet structure

假设请求者到缓存内容i的节点Vn有n跳，路径上各节点均未缓存内容i，此时请求者发出对i的请求。在兴趣包转发过程中，请求首先到达接入节点V1，V1查询表1，计算内容偏好度Hi与内容级别Wi。Wi计算式如下：

Wi=Ri/U

(6)

其中:Ri为重要度排名;U为内容总数。Wi若小于ΔW(0<ΔW<1)，将Wi写入兴趣包Local Importance Level字段；否则，不修改LIL值(初始值为空)。然后，Interest Total Hops字段值ITHi加1后转发(初始值为0)，即每个转发节点累加，以记录请求经过的节点数。

表1 内容信息统计表Tab. 1 StatisticalTable of content information

内容命中前沿途节点j判断ITHi值不为0，则匹配LIL值确认是否为本地偏好度高的重要内容。字段值非空，则计算ADij,若大于兴趣包Activity Degree字段ADi值,则修改ADi=ADij，并将ITHi值赋予兴趣包Activity Hop字段值AHi;否则不对兴趣包作任何修改，最后将ITHi值加1后转发。

若节点Vn的CS(Content Store)中存在请求的内容，节点将数据包历经跳数值DTHi与缓存执行跳数值ECHi写入数据包Data Total Hops字段和Execution Cache Hops字段，然后返回数据包。其中DTHi=ITHi-1，求取ECHi时首先节点计算内容全局活跃度归一化值NADi：

NADi=(ADi-ADmin)/(ADmax-ADmin)

(7)

其中，ADmin和ADmax分别为表1中可查的最大与最小活跃度值。然后,分两种情况求取ECHi：

1)若NADi≥ΔAD，则认为内容i为全局活跃内容，则将内容i缓存在其活跃度最高的节点，即将兴趣包中AHi值赋予ECHi。

2)若NADi<ΔAD，即内容为非活跃内容，则读取LIL字段值与ITHi，计算层级匹配值CHi，CHi=Round(Wi·ITHi)，即内容偏好级别与经过跳数的积向近取整，然后将CHi值赋予ECHi。

以上为兴趣包转发和缓存决策的过程，在数据包返回阶段，沿途节点只需简单地识别DTHi值是否等于ITHi值，两值相等则执行缓存操作，两值不相等则不执行缓存操作。然后，将DTHi值减1后转发下一跳。直到数据返回给用户，完成整个请求过程。结合上面介绍，CCUP策略伪码如下。

算法1 兴趣包转发处理过程。

1)

收到兴趣包

2)

if (CS命中)

3)

执行算法2

4)

else 读取ITHi

5)

if (THi=0)

6)

计算Wi

//式(6)

7)

if (Wi≤ΔW)

8)

Wi值写入LIL字段

9)

else 执行步骤18)

10)

else 查看LIL值

11)

if (LIL=Null)

12)

执行步骤18)

13)

else 计算ADij

//式(5)

15)

if (ADij>ADi)

16)

修改AD、AH值

17)

else

18)

ITHi++

19)

转发下一节点

算法2 缓存决策过程。

1)

读取兴趣包中ADi、AHi、ITHi

2)

计算NADi

3)

if (NADi≥ΔAD)

4)

ECHi=AHi

5)

执行步骤8)

6)

else

7)

ECHi=CHi

8)

DTHi=ITHi-1

9)

返回数据包

算法3 数据包处理过程。

1)

收到数据包

2)

读取DTHi和ITHi

3)

if (DTHi=ECHi)

4)

if (CS is full)

5)

执行近期最少使用(Least Recently Used, LRU)替换策

略并缓存

6)

else

7)

缓存数据

8)

else

9)

DTHi=DTHi-1

10)

转发数据包

算法1中,步骤6)与步骤7)结合用户喜好完成了对缓存内容的筛选，实现选择性缓存高“质量”内容的目的;步骤11)选择需要中心节点计算内容活跃度的请求，由步骤15)判断并记录下重要中心节点的跳数。既释放了路径中节点跟踪每个内容活跃度的计算压力，还可以由每个区域内容偏好度的变化及时发现潜在全局活跃内容。对需要缓存的内容，由算法2进行的差异化缓存决策，确定执行缓存操作的跳数。算法2中：步骤4)是将跟踪发现的全局活跃内容缓存在重要中心节点，快速高效地分发给更多潜在需求用户；步骤7)是将非全局活跃度内容按偏好等级与节点距离用户跳数层级匹配缓存，便于用户快速就近获取区域偏好内容。数据包返回时节点处理过程见算法3，仅当前数据包历经跳数DTHi与缓存执行跳数ECHi匹配时才执行缓存操作(算法3中步骤3))，否则直接转发数据包。通过上述机制，CCUP在控制冗余并提高缓存资源“质量”的同时，满足了用户对区域偏好内容的就近获取、更多区域用户偏好活跃内容的快速分发。

3 仿真实验及结果分析

3.1 实验设置

表2 仿真参数Tab. 2 Simulation parameters

3.2 性能评价指标

仿真对比LCE[2]、Prob(0.6)(Probabilistic caching with 0.6)[4]和Betw[8]策略，均采用LRU缓存替换策略,分别在CS容量、Zipf分布参数α和请求频率的变化下，从以下2个指标定量地比较和分析。

1)平均缓存命中率(Average Cache Hit, ACH):即网内缓存命中数interest_hit与用户请求总数的比值。

(8)

2)平均请求时延(Average Request Delay, ARD)：即用户请求时延delay的总和与请求总次数interest_all的比值。

(9)

其中:V为路由节点的集合;N为用户请求集合。平均缓存命中率越高，服务器负载越小。平均请求时延越小，用户请求需要的时间越短，体验感越好。

3.3 结果分析

3.3.1 节点缓存容量对性能的影响

本节研究分析不同节点缓存容量下四种缓存机制在缓存命中率和平均请求时延上的性能表现,结果如图3所示。从图3可以看出，随着节点缓存容量的增加，四种缓存机制的缓存命中率逐渐增大，平均请求时延均逐渐减小。这是因为随着缓存容量的增加，系统能够缓存更多的内容来满足用户需求，间接地增加了缓存内容的多样性。但不同策略对冗余控制的差异性使得CS增加量对系统性能的提升效果各不相同，当每节点均增加10 slot时，LCE、Prob(0.6)、Betw和CCUP四种策略的命中率分别能提高0.014、0.033、0.027、0.035个百分点。该结果进一步验证了提高控制缓存冗余和缓存内容“质量”以增加缓存内容多样性对提升系统性能的必要性。从图3对比可以看出，CCUP在两个评价指标上均优于其他缓存策略，具有较高的缓存性能与较好的用户体验。

3.3.2 Zipf分布参数对性能的影响

本节研究不同Zipf分布参数α对缓存系统性能的影响，比较随着Zipf参数α的变化四种缓存策略的性能表现，结果如图4所示。从图4可知，随着α增大，四种缓存机制在平均缓存命中率、平均请求时延这两个指标上的性能都越来越好。这是由于随着Zipf分布参数变大，请求越来越趋于集中，网内缓存资源利用率越来越高，请求时延也随之降低，但因网内冗余的客观存在与节点缓存容量的限制，使得整体性能增长率先大后小。如Betw策略仅高介数节点缓存，无法充分利用存储空间资源，随着请求趋于集中性能反而会降低。由图4分析可知，在这两个指标上CCUP均优于另三种策略，即相同Zipf分布参数下，CCUP具有更高的缓存资源利用率和更低的请求时延。

图3 缓存容量对性能的影响Fig. 3 Impact of caching capacity on performance

图4 Zipf分布参数对性能的影响Fig. 4 Impact of Zipf distribution parameter on performance

3.3.3 请求速率对性能的影响

本节研究分析不同请求速率下四种缓存机制在缓存命中率和平均请求时延上的性能表现,结果如图5所示。从图5(a)可以看出，随着用户请求速率的增加，四种缓存机制的缓存命中率的整体趋势均有小幅度提升。虽然用户请求速率增大时，单位时间内注入网络的分组数量增加，会小幅度提高缓存资源的利用率；但分组数的增多使得分组在排队系统中的排队时延增加，总体上如图5(b)所示，平均请求时延并没有太明显的改变。由图5可以看出，相比于另三种缓存策略，CCUP仍具有较高的缓存性能。

图5 请求速率对性能的影响Fig. 5 Impact of request rate on performance

4 结语

为进一步提高缓存系统性能，提升用户体验，本文提出一种基于用户偏好的协作缓存策略(CCUP)。该策略考虑用户偏好与内容流行度进一步提高缓存内容“质量”，发挥不同位置节点的独特缓存优势，选择最佳内容放置在最优位置。实验结果表明，CCUP在平均缓存命中率、平均请求时延方面较现有策略有显著优势。但由于内容流行度的被动统计存在一定滞后性，制约着缓存内容质量的进一步提高，下一步将考虑结合流行度的预测进行研究。