信息中心网络的内容流行度评估算法

张送柱，王兴伟，黄 敏

1(东北大学 计算机科学与工程学院，沈阳 110169) 2(东北大学 信息科学与工程学院，沈阳 110819)

1 引 言

近年来，信息中心网络(Information-Centric Networking,ICN)作为一股清流的革命网络范式被学术界率先推崇，究其历史，ICN的雏形可追溯到2001年，源于Gritter和Cheriton撰写的开创性文章[1]；而其概念的提出却源于2009年Jacobson发表在CoNEXT上的一篇会议论文[2].抛开通信模式的独特性，我们认为ICN最有价值的地方是其标新立异的网内缓存特征[3].然而网内缓存是指网内的路由器(内容路由器)具有缓存内容副本的能力，即一个内容能够存在于网内的多个路由器中，以供用户方便地使用.当然这里所指的网内缓存并非传统路由器中设置的buffer，也非内容分发网中的服务器.进一步地，ICN缓存技术有助于降低获取内容所需的网络时延、均衡整个网络的业务流量以及减少由于链路或者节点失效对内容获取(分发)带来的负面影响等[4].

ICN缓存技术[5]的研究范畴大致包括缓存资源分配、缓存放置、缓存替换和缓存协作等.首先，缓存资源分配着眼于对不同的路由器分配不同大小的缓存空间以及在内容分发前预分配哪些内容资源到哪些路由器；其次，缓存放置主要研究在众多路由器中哪里开辟缓存的问题；再次，缓存替换旨在选择怎样的替换算法进行缓存内容的更新.最后，缓存协作涉及到集中式存储和分布式存储(如同构协作、同构非协作、异构协作、异构非协作等).总结来看，这四种缓存机制分别回答了缓存多少、哪里能够缓存、缓存什么以及如何缓存的问题.

对ICN缓存技术中缓存替换策略的研究极为重要，因为缓存的具体内容决定了缓存的命中率也进一步决定了整个路由的效率和网络性能.据我们所知，大多数缓存替换策略都是基于访问频率或者访问时间制定的，因为缓存替换算法应尽可能的简单高效才能保证ICN的线速执行.几种常见的且具有代表性的缓存替换策略可归纳为：最近最少使用[6]、基于自适应模糊推理[7]和基于内容流行度预测[8].从性能上来看，很难讲清楚哪一种替换策略更有价值，唯一可以用于评判的标准恐怕只有应用场景.

虽然内容是ICN的第一实体，且能够以任何形式出现，但在实际的应用中，内容往往指的是视频流.例如思科视觉网络指数预测到2020年平均每年的全球移动数据流量能达到366.8EB，其中仅视频就能占到75%[9].更为重要的是大多数用户通常采用点播的形式观看部分视频，不再是整个完整的视频.这就需要路由器去缓存一些热点片段，进而最大程度地满足更多用户的需求.事实上，热点片段正是流行的内容片段，这说明基于流行度预测的替换策略才是当前甚至未来一段时间的主要潮流.尽管已经有一些ICN的缓存替换策略是基于流行度开展的，但是这些研究并没有给出如何评价内容的流行度、或者仅仅简单地使用访问次数来代表流行度.鉴于此，本文继续研究面向ICN缓存替换的流行度预测方案，并给出一种新型的内容流行度评估模型.

2 相关工作

针对ICN缓存替换策略的研究，比较成熟且较早的是其内置的最近最少使用策略[6]，它不仅适用于ICN，也同样适合于其他具有缓存能力的网络和系统.虽然这种策略很大程度上能够满足用户对热点内容的获取，但同样也存在时间局部性和空间局部性的限制，很难应对突发流量的情况.为此，文献[7]提出一种自适应模糊推理的策略来预测用户请求的分布.首先，基于神经模糊推理系统分析缓存的内容从而挑选出比较受欢迎的内容类型；然后，再次启用推理系统分析剩余的内容，以此类推将所有的内容进行分类.一旦内容到达路由节点，系统会自适应地判断该内容的类型以及过往的访问历史，进而决定是否缓存.文献[10]基于流量负载和用户偏好程度，根据网络环境实时调整内容的缓存位置，这使得缓存替换的利用率更高.文献[11]提出了一个基于贪心的上下游协作的缓存替换策略，其将流行的内容缓存在边缘节点，其余的内容缓存在中间核心节点.文献[12]提出了一个机会式的缓存替换策略，根据局部概率将频繁请求的内容缓存起来.虽然以上缓存替换策略能够大幅度提高缓存的命中率，然而执行效率变低，使用户不能及时获取所需的内容.

事实上，ICN要想完全实际应用且兼容当前的IP网络，必然要重点解决当前盛行的互联网视频流业务，这同样会导致前两种缓存替换策略效果不佳.这种环境下，涌现了一些基于内容流行度预测的缓存策略.例如，文献[8]证明了通过内容流行度的预测能够极大地提高缓存的利用率.文献[13]提出基于软件定义网络(Software-Defined Networking，SDN)和深度学习(Deep Learning,DL)的流行度预测方法(SDN-DL)，它采用交换机的计算资源和配置资源，通过SDN构建一个集中式的深度学习网络.文献[14]提出一种具有节能水准的流行度预测算法(Energy-Efficient Prediction Algorithm，EPA)，用于平衡整个系统的流量，从而达到节能的效果.文献[15]将布隆过滤器和压缩感知技术结合，利用SDN的集中控制能力使缓存信息保持一致，提出一个缓存内容快速定位机制，有效地提高了缓存的利用率.文献[16]提出一种基于Q路由的方法来预测内容的流行度，通过对路径的不断增强学习，以达到更好的路由效果和更高的缓存命中率.虽然这些具体的流行度预测方案能够较大程度地提高缓存利用率和命中率，然而它们都是笼统的介绍流行度预测的依赖指标，却忽略了流行度的具体评价方式.鉴于此，本文将着重解决这一问题，即研究流行度的评估模型.

3 内容流行度建模

本节为内容流行度建模，首先进行流行度衰减和流行度上升建模.其中，流行度衰减启发于酒精挥发模型，流行度上升启发于物体吸热模型.特别地，鉴于内容的流行度是短暂的且具有时效性，故也对流行度的周期进行建模，即计算内容流行的时长.

3.1 流行度衰减建模

内容处于无人问津的状态时，其流行度通常会随着时间的推移而减弱，这就相当于一个醉酒的人，他身上的酒浓度会随着时间的推移而变淡，这是因为整个自然过程中，酒精发生了挥发.此外需要指出是，酒精挥发因子可类比成流行度衰减因子，且在整个过程中，衰减的快慢不等，即衰减因子应是一个变量.假设流行度的衰减因子为ρ，根据酒精挥发模型，它与内容的当前流行度T(t)成正比，则得到公式(1)如下：

(1)

其中，α为大于0的调解参数，通过求解微分方程(1)，可得到公式(2)如下：

T(t)=Ce-αt

(2)

假设初始时刻内容的流行度为T0，将公式(2)变形可得到公式(3)如下：

T(t)=T0e-αt

(3)

将公式(3)代入到公式(1)，显而易见ρ是一个变量.

3.2 流行度上升建模

内容处于频繁访问状态时，其流行度通常会出现上升趋势，这相当于一个物体内在地做吸热操作，其温度自然而然地要不断上升.物体的吸热过程如公式(4)所示：

Q=cmΔt

(4)

其中，Q为每一次加热物体吸收的热量，c是比热容，m是物体质量，Δt为两个连续时刻的温差变化.倘若把物体的吸热过程类比到内容被访问带来的流行度上升过程，那么可以有如下表述：Q为内容被连续访问后的即时流行度；m为内容的大小，通常情况下，内容越大其流行度越高，这是因为包含的切片越多其范围越大越笼统(例如，10分钟电影的流行度要高于该10分钟内某两分钟的流行度)；c能表达内容的类型，是内容类型参数，即不同的内容类型具有不同的参数值，且比较流行的内容类型应该有更高的对应参数值；Δt是连续的两个时刻.基于上述描述，可以将公式(4)改写成公式(5)如下：

Q(t)=cmt

(5)

假设从零时刻到t′时刻，内容处于无人访问状态，而从t′时刻后，内容处于频繁的访问状态，那么可以得到综合的内容流行度，如公式(6)所示：

(6)

其中，前半部分表示内容在自然状态下其流行度的变化情况，后半部分表示内容在频繁访问状态下其流行度的上升情况.

3.3 流行度周期建模

在实际的应用环境中，内容流行度的衰减情况和上升情况是不同的.如果内容长时间不被访问，其流行度会下降到零，并且这种情况是常见的；相反，内容流行度并不会一直呈现出上升趋势，而是在达到最高值的短暂时间后开始逐渐下降[17]，这说明内容的流行度具有时效性和短暂性，即时间周期性.举例讲，电影院新上映的电影，刚开始会随着观看次数的增多而变得非常流行，然而久而久之该电影下线之后，它的流行度就会瞬间衰减.因此，很有必要对流行度的周期进行分析，即公式(6)中t的建模.如上所述，流行度周期的产生源于流行度的上升，故流行度的周期建模必然要考虑流行度的上升速度；此外，流行度的周期其实就是个时间时效，它与当前的内容流行度T(t)紧密联系.鉴于此，流行度周期与流行度的上升速度和当前的流行度密切相关.

假设内容流行度的上升速度不能超过给定的值p，则得到关于两个连续时刻的边界方程如公式(7)所示：

(7)

将公式(6)的上升部分代入到公式(7)，可使t具体化如公式(8)所示：

(8)

综上所述，本节建立了三个流行度模型，其中第一个模型是指内容流行度会随着时间的推移而减弱，第二个模型是指内容流行度会随着访问次数的增多而上升，第三个模型是指内容流行度的持续不是长久的而是短暂的.

4 仿真结果

4.1 实验设置

本文提出的内容流行度评估算法用于ICN的缓存替换中，算法用C++编写，仿真环境基于NS3，硬件配置为Intel(R)Xeon e5-2680,2.39 GHz CPU,7.99 GB RAM.此外，本文选择文献[13](SDN-DL)和文献[14](EPA)作为对比基准，其中，缓存命中率、路由时延和网络能效作为三个评价指标.

本文的仿真是基于真实的YouTube数据集[18]，该数据集包括60万条兴趣请求、26条内容(80%的内容小于12M)、1563个服务器、89个网段和2377个用户.然而该数据集没有展示具体的网络拓扑，为此我们引入Deltacom网络拓扑(如图1所示，包括97节点和124条边)，并将该数据集的数据特征均匀地分布在Deltacom网络拓扑中.

特别地，本文涉及的四个重要参数，即α、c、m和p的设置如表1所示.其中，α为随机设置成定量100；c为集中测试的YouTube视频流类型，随机设置成定量2000；为了兼容当前IP网络的包级别的传输，m设置成定量1500B；p设置为变量，是要看不同流行度上升速度对流行度周期的影响，继而观测网络的性能.

图1 2010年Deltacom网络拓扑

表1 仿真参数设置

Table 1 Parameter settings

参数设 置α100c2000m1500Bp1%,5%,8%,10%,15%

4.2 缓存命中率测试

缓存命中率能直观地反映出缓存策略的好坏，缓存命中率高说明流行度评估准确，且路由器总能实时缓存流行度高的内容.缓存命中率chr定义如公式(9)所示：

(9)

其中，分子是路由器(不包括服务器源)缓存命中的次数，分母是总的请求次数.三种算法在不同p值下的缓存命中率对比结果如图2所示.

图2 三种算法的缓存命中率

通过图2可以看出，本文提出的流行度评估算法能够促进更高的缓存命中率，SDN-DL次之，EPA再次之，这是因为本文有一套完整的流行度评估模型，包括衰减模型、上升模型和周期模型.尤其对流行度周期模型的建模，能够很好地预测热点内容的生存周期，从而根据需求实时地调整缓存的内容，进一步提高缓存的命中率.此外，还可以看出随着p值的增大缓存命中率也会随之变高，然而当p达到一定的值(8%)后缓存命中率增加缓慢，这说明内容的缓存周期并不是越长越好，至于设置多长最佳，这与缓存的大小、兴趣请求的特征以及内容的地理位置分布密切相关，对此本文不做详细的讨论.

4.3 路由时延测试

路由时延用来评定缓存策略对整个ICN内容的获取过程是否有改进效果，它的定义如公式(10)所示：

Δmt=tend-tstart

(10)

其中，后者是兴趣请求发出的时刻，前者是用户获取内容的时刻.三种算法在不同p值下的路由时延对比结果如图3所示.

图3 三种算法的路由时延

通过图3可以看出，本文算法在路由时延方面具有明显优势，尤其在p=15%时，仅仅用了大约18ms就完成内容的获取，这说明本文的流行度评估算法将绝大多数热点内容在路由器上进行了缓存，以此满足了大多数后续相同的兴趣请求.正因如此，便省去了多余的兴趣请求路径和内容分发路径，自然地也节省了路由时延.然而SDN-DL和EPA没有很好地关注热点内容的缓存和预测，导致后续一段时间内相同的兴趣请求不能被中间的路由器满足，从而加大了路由时延.

4.4 网络能效测试

网络能效是指节能的效果，测试这个指标是因为绿色节能是ICT的主要话题之一，它的定义如公式(11)所示：

(11)

其中，Eused是采用流行度预测后网络消耗的能量，Enused是未采用流行度预测时网络消耗的能量，它们的计算可参考文献[19].三种算法在不同p值下的网络能效对比结果如图4所示.

图4 三种算法的网络能效

通过图4可以看出，本文算法的加入对网络能耗的节约有最好的效果，EPA和SDN-DL分别次之.特别地，当p=15%时，本文算法的节能效果能达到41%.事实上，由于基于牛顿冷却定律评估流行度而带来的缓存替换效果明显，一方面某些路由器不必再专门消耗能量去重新启动，另一方面大多数链路也不必再进一步地转发多余的兴趣请求以及浪费带宽去分发多余的流量，这样一来一往就卸载了路由器的操作能耗和链路传输流量所需的能耗.

5 结 语

在视频流分发业务盛行的当下，ICN有限的缓存空间对热点内容的把持显得尤为重要.本文提出了一种评估内容的流行度的新型方法，从而有效地执行缓存替换，将流行度高的热点内容缓存在ICN路由器中.针对内容流行度，建立了三种不同的模型，即流行度衰减模型、流行度上升模型和流行度周期模型：第一个模型是指内容流行度会随着时间的推移而减弱，第二个模型是指内容流行度会随着访问次数的增多而上升，第三个模型是指内容流行度的持续是短暂的不是长久的.采用YouTube数据集和Deltacom网络拓扑实施仿真，实验结果表明本文提出的流行度评估算法是可行的且有效的.然而，本文也存在一些缺憾，如没有给出内容缓存周期的理论分析.从理论上讲，它与缓存的大小、兴趣请求的特征以及内容的地理位置分布密切相关.这是一个较为复杂的数学问题，对此，我们将开展后续的研究工作.