内容中心网络边缘节点势能增强路由机制

蔡岳平,樊欣唯,邱 娅,谭 兵,晏 尧

1(重庆大学 通信工程学院,重庆 400030)2(国网重庆市电力公司 电力科学研究院,重庆 410014)

1 引 言

根据Cisco VNI的预测报告,2021年视频类应用产生的流量将约占网络总流量的82%[1].视频内容大量复制传播的需求,带来了内容分发网络(content delivery networking,CDN)[2]和对等网络(peer-to-peer,P2P)[3]的流行和商用.二者均提高了用户访问内容的速度,但CDN通过DNS重定向的方式将用户请求转发到网络边缘的服务器,其内容存放地点受限;P2P为每个内容生成一个跟踪器,交付有效性低.由于二者均无法摆脱基于IP地址的端到端转发模式,造成诸如DDoS攻击等安全事故频繁发生.因此,研究者们提出了一种全新的未来网络架构——信息中心网络(information centric networking,ICN),从根本上解决当前面向连接的互联网模式无法满足用户的流量需求的问题.ICN通过内容的名字而不是分配的IP地址进行标识,因此用户发出的请求只需关注内容本身,而不必关注内容存储的位置.典型的ICN架构有DONA[4]、PURSUIT[5]、CCN[6]、COMET[7]、PSIRP[8]等,其中CCN(content centric networking)被认为是最有前途的方案之一.

CCN架构采用了类似URL的命名的方式,提供端到内容的服务,并且支持扩展路由节点的功能,使得路由器不仅具有传统的转发功能,还具有一定存储的能力.该功能通过“存储换带宽”的方式降低数据包在网络中的传输时间,实现比CDN更加灵活的分布式缓存网.然而,在传统的CCN路由机制中,这种“分布式缓存”的优势并未得到很好的发挥,这是因为传统的路由机制只能实现兴趣包向发布者进行路由,而路径外的大量就近缓存无法感知利用,导致大量带宽资源的浪费.因此,需要设计出一种高效可靠的缓存感知的路由机制来充分发挥CCN的缓存优势.

对于CCN的缓存感知的机制,主要解决的问题可以归为两点:(1)如何发现缓存内容;(2)如何朝着最近的一个内容源转发兴趣包.

现有缓存感知路由机制可分为两类,一类是请求者主动发布报文探测缓存内容的位置:文献[9]提出一种邻居缓存探测的路由机制(neighbor cache explore routing,NCE),该方案利用分布式蚁群算法计算最短路径,可实现局部缓存的感知.但该方案并未明确指出探测的深度,当网络范围增大时可能造成探测的成本较大,对网络带宽造压力.另一类是由缓存节点向周围发布已经缓存的内容信息,请求者被动接收后进行综合判断再选出最优路径:文献[10-12]提出了一种基于势能的路由机制(cache aware target identification,CATT),该方案对于稳定的发布者节点构建永久势场(permanent potential field,PPF),采用类似于传统CCN的洪泛通知方式实现;对易变的缓存节点构建易变势场(volatile potential field,VPF),采用固定跳数的通告邻居节点内容的势能,兴趣包依据收到的最小势能确定下一跳的转发端口从而获取最近的内容.但该方案并未区分缓存节点和发布者节点的服务器性能,当网络中的多个内容节点势能叠加后,造成兴趣包并未受到最近的内容源的吸引,请求内容的时延大;同时CATT没有对缓存的内容进行区分,将节点内缓存的所有内容以相同跳数向周围节点进行通告,造成巨大的带宽开销.

由于CCN路由器的主要功能仍然是快速转发数据包,因此我们需要考虑路由器缓存功能的有限性.另外,在多数真实场景下,位于网络核心及中间的路由器不会产生内容请求,兴趣包均来自靠近网络边缘的用户,因此我们也需要考虑充分利用网络边缘的缓存,将兴趣包尽可能的吸引到就近的缓存节点,提高内容的响应速度.

本文提出了一种基于势能的边缘节点势能增强路由机制(edge node potential-enhanced routing,ENPER).该方案定义了网络中每个节点的势能,通过增强边缘缓存节点的势能,将兴趣包尽可能地吸引到边缘节点上命中;并配合使用边缘节点统计的兴趣包数量对不同流行度的内容进行区分通告,以满足用户的低请求时延需求和网络的低带宽开销.本文的贡献如下:

1)在文献[10-12]提出的势能概念基础上,针对CCN兴趣包来自网络边缘却无法在边缘节点快速响应的问题设计了模型,提出了一种边缘节点势能增强的路由机制.

2)提出了一种在边缘节点对内容的流行度进行预测并结合网络拓扑范围的大小,对缓存内容的势能值进行区分通告的机制.

2 边缘节点势能增强路由机制

在传统的CCN路由机制中,发布者产生一个新内容,将通过洪泛的方式向全网节点进行通告,兴趣包基于转发信息表(Forwarding information base,FIB)查找一条到达发布者的最佳路径.因此对于每个路由器,FIB中只包含到达内容发布者节点的下一跳端口,却没有包含到达就近缓存节点的下一跳端口.由于无法感知网络中存在的大量缓存资源,传统的CCN路由机制的平均请求内容的时延较大.本文在Suyong Eum等学者提出的势能概念基础上,设计了一种缓存可感知的边缘节点势能增强路由机制.在该模型下,发布者或缓存节点被当作负点电荷,兴趣包即带正电的试探电荷,将沿着梯度下降最快、势能最小的方向转发.本节将对ENPER的设计进行详细介绍.

图1 ENPER的转发过程

2.1 ENPER势能模型的建立

图1展示了兴趣包经过缓存节点时的转发过程.当兴趣包到达某个节点时,将首先根据CCN的路由特点查询内容存储表(content store,CS),如果匹配到相关条目则(1)直接返回数据包;如果没有匹配内容则查询待定兴趣表(pending interest table,PIT);(2)如果在PIT中查询到之前已有其他兴趣包请求过该内容,则将当前请求端口添加到PIT条目中,等待数据包返回;如果PIT中也没相应匹配项,则先在PIT中添加请求条目,然后;(3)兴趣包将会查找FIB中具有最小的势能值的端口,如果匹配则向势能值最小的端口转发;(4)如果此时具有最小势能值的内容被替换或者删除,则选择具有次小值的端口转发;(5)当网络中没有该请求的内容或该内容正被发布者洪泛通知,导致FIB中没有条目,兴趣包将被丢弃.发布者服务器收到兴趣包后,发送相应数据包并沿原路返回.数据包每经过一跳;(6)先检查PIT,如果PIT中存在多个端口则复制数据包发送给多个请求者;(7)然后将数据包存储在CS中,并重新建立自治域内的节点势场.

2.1.1 发布者节点的势能

由于发布者服务器为内容产生的源头,具有较大的输出速率、较高的处理性能和长时间的存储能力,因此设置为长期稳定的负点电荷,形成自治域内的全网势场.除非内容发生变化,该全网势场一旦建立将一直保持稳定状态.兴趣包处于网络中任意节点ni受到发布者np产生的吸引力为:

(1)

其中,Qnp为发布者生产内容的质量,大小与服务器处理速度、吞吐量等因素有关.公式(1)中的负号保证兴趣包朝着势能最低点进行路由.距离d可以为跳数、时延、链路带宽等.d(ni,np)定义为网络中的任意节点ni到发布者服务器np之间的最小跳数.随着跳数的增加,兴趣包位于发布者节点越远,受到的势能吸引力越小,即|φn|越小.

2.1.2 缓存节点的势能

虽然CCN网络中的路由转发节点具有缓存能力,但与发布者进行比较,路由器的主要功能为线速转发数据包,其缓存容量和处理性能远不及专为本域提供内容的发布者服务器.尤其是当缓存用尽时会根据CCN的替换算法删除一部份已经存储的内容,造成后续的兴趣包在无法命中.根据该特性,设置α为缓存节点nc的内容质量比例系数:

(2)

由于当前互联网的内容的请求符合幂律分布特征(Zipf或Mandelbrot-Zipf分布)[4],即80%的请求只与20%的内容有关.例如,当网络中内容的总数为N=1000,Zipf=1.0时,前129项内容的请求累计概率已达到80%,其他Zipf分布指数与累计概率到达80%时的内容个数关系如表1所示.根据以上分析,为了让缓存节点能尽可能的存储请求量大的内容,同时又考虑到路由节点的性能和成本,我们设置α为0.1到0.3之间的常数.

表1 Zipf分布指数与请求累计达80%时内容个数的关系

2.1.3 混合叠加的势能

由于数据包在返回中会存储在途经节点,因此当网络中同时存在多个缓存内容和多个发布者产生的内容时,总势场会以线性叠加的方式呈现,如公式(3)所示.

通过公式(3)可以推断出当存在多个缓存内容时,如图2(a)所示,靠近发布者的势能通过相互叠加的方式会比靠近边缘的副本节点的势能更大.然而在多数实际场景中,兴趣包来自靠近边缘网络的用户,位于网络核心及中间的路由器不会产生请求.如果从边缘出发的兴趣包受到了网络核心的吸引并向发布者服务器转发,将错过更靠近边缘的缓存内容,造成用户请求时延的增加.所以如图2(b)右所示,我们考虑加强网络边缘缓存的势能值.原因有两点:

(3)

图2 缓存节点的势能叠加

1)将来自边缘的兴趣包可直接在边缘节点上命中,可减少请求时延;

2)边缘缓存节点集中收集相同兴趣包的请求,将增加请求概率较大的内容的驻留时间,提升目标缓存内容的可用性,进而增加缓存命中率.

图3 网络的拓扑和缓存节点的势场图

根据以上分析,为了保证兴趣包可以受到边缘缓存势能的吸引朝着最近的缓存进行路由,我们提出了缓存节点的势能参数Wni,在考虑节点负载的情况下,提高边缘缓存的势能值:

(4)

2.2 缓存节点内容通告机制

当势场模型建立之后,如果缺少通告机制将势能的值通告到其它节点,那么基于势能路由机制与传统的CCN路由机制无异,即兴趣包将在转发路径上随机命中,错过临近的缓存节点.因此我们需要添加通告机制实现势能的吸引.但如果将所有缓存内容向全网进行通告,不仅仅会造成网络的大量开销,当缓存内容根据不同算法被替换时,也需要向周围节点发布NACK通告,删除相应的FIB条目,这也将占用大量的带宽资源.因此我们需要一种简单高效的流行度判断机制和一种适应网络拓扑的通告范围机制来实现基于势能的路由.

在文献[14]中,作者根据内容请求呈幂律分布特点将内容划分成三类:流行、普通、冷门,据此对缓存内容进行区分通告,但是该方案成立的前提是已知所有内容的请求的次数和整体流行度,在真实的网络情况下是无法实现的.另外,兴趣包的请求个数还具有“收敛性”,当一个节点收到大量相同的兴趣包时,会记录下游请求端口并添加在PIT中,然后仅向上游发出一个兴趣包,因此类似于文献[15]提出的统计上游节点,或统计域内的所有节点收到兴趣包的个数的方式也是不可取的.根据以上分析,内容的流行度值只能在边缘节点进行统计和计算.本文提出的边缘加强的势能方案,在考虑节点负载的情况下,可将具有相同请求的兴趣包尽可能地吸引到一个边缘缓存节点,得到更加精确的内容流行度.

CCN网络的内容流行度根据内容的请求次数进行计算,假设一个k内容在请求节点ni上某个时间段T内收到的兴趣包请求次数为fni,k,那么该内容的流行度定义为:

(5)

PT+1(k)=σPT(k)+(1-σ)PT-1(k)

(6)

当第一次请求k内容时,边缘节点收集下游的请求总次数,并在向上游发送一个兴趣包的同时通知上游节点k内容的流行度.当内容返回并建立势场后,边缘节点将在周期T的时间段继续统计,并向上游缓存节点通知内容流行度的变化,保持上游流行度的实时性,保证对同一内容通知范围的统一.

由上小节可知,当预测的流行度越大,代表请求的次数越多,缓存内容的稳定性越高,对其进行大范围的通告可提高内容的可用性.通告节点的最大范围n跳的设置需要依赖特定的网络拓扑结构和大小,且需要满足如下要求[14]:(1)通告范围限制在域内;(2)通告产生的控制流量应限定在一定程度内;(3)n的选择小于缓存节点到发布者之间的跳数.

表2 缓存通告范围

如表2,本文根据网络的大小设置跳跃阈值实现针对不同流行度内容的缓存通告,其阈值为H1,H2,…,Hn(H1Hn时,向周围n跳范围内的节点进行通告;当Hm

3 仿真实验与结果分析

3.1 实验设置

本文采用了开源仿真平台ndnSim对上述路由机制进行实现,并与CATT[9]和仿真平台上主流的路由机制Best-Routing[15]进行对比.ndnSim是基于NS-3的仿真工具,在该平台上加入了NDN协议栈,可实现CCN网络的路由机制.实验的节点总数为30个,请求到达服从泊松分布.此外用户的请求分布根据Zipf的指数分布进行调整.Zipf指数代表请求内容的集中度,指数越大表示用户请求内容越相似,越小表示请求内容越分散.仿真时间为180s,其他参数如表3所示.

3.2 性能评价指标

为了客观反映不同路由机制的实际效果及不同参数对路由机制的影响,本文定义了以下的性能评价指标.

3.2.1 平均请求内容的时延

对单个内容的请求时延是指用户从开始发送兴趣包到接收数据包整个过程的时间,平均请求内容的时延是指在周期为T(此处设置为20s)的范围内,计算所有时延的平均值.平均请求内容的时延反应用户发从出请求到响应的平均时间,该值越小代表等待时间更短,用户体验更佳.

(7)

3.2.2 发布者服务器的负载减少率

表3 实验参数的设置

其中,S_counts表示发布者服务器的响应次数,R_counts表示用户的请求的总次数.服务器负载的减小率表示由于网络中分布的缓存的响应使得发布者的负载减小,该指标越高,说明网络中的缓存起到的效果越明显.

(8)

3.2.3 缓存通告报文开销

(9)

缓存通告开销定义单位时间内每个缓存通告的报文长度与传输距离的乘积,并对通知内容个数求和.开销的大小主要取决于报文的长度、报文的通告数量和跳数.该值越大,表示缓存通告的开销越大,占用的带宽越多.

3.3 仿真结果及分析

图4 平均请求内容的时延随仿真时间的变化

图4对各个路由机制的平均请求内容的时延进行对比.设置仿真条件为CATT的缓存通告为2跳,ENPER的最大通告范围为3跳,Zipf=1.从图4中可以看出,在仿真的初期,由于网络中所有路由节点均无存储,不同路由机制的兴趣包都必须到达发布者服务器以获取内容,初期的平均请求内容的时延相等且较大,随着网络中缓存的内容逐渐增加,获取内容的跳数减少,平均请求内容的时延逐渐降低,最后趋于平稳.对比分析,三种路由机制的平均请求内容的时延从大到小依次为Best-routing、CATT、ENPER.具体原因如下:Best-routing的FIB中只存在到发布者的最短路径,无法感知路径外的缓存节点的内容,因此大部分兴趣包需要穿过整个网络到达发布者服务器,占用的链路资源最多,平均请求时间最长;CATT由于采用了基于势能的缓存感知路由机制,与Best-routing相比可以让兴趣包朝着缓存节点进行路由,平均请求内容的时延下降;ENPER通过增加边缘节点的势能将兴趣包吸引到最近的缓存节点命中,跳数最少,占用的资源最少.

图5 平均请求内容的时延随Zipf的变化趋势

根据图4的仿真结果可以得到在仿真初期数据波动较大,为仿真预热时间.因此后续的对比将取100秒～180秒之间的稳定数据的平均值进行分析.由于在实际场景中,不同的网络环境下的Zipf的指数分布具有差异性,本文通过改变Zipf的分布参数(0.5～1.1)比较三种路由机制在平均请求内容的时延、发布者服务器负载减小率和缓存通告开销的差异.如图5,随着Zipf流行度分布指数的增加,三种请求时延不断减小,其原因是Zipf指数越小表示请求内容越离散,多样化的内容请求将导致有限的存储空间被高频率地替换,缓存利用率低;随着Zipf指数的增加,请求内容的局域性和集中性不断加强,CS储存的内容稳定,兴趣包得以在缓存节点中频繁命中,平均请求内容的时延不断减小.对比分析可以得出当Zipf=1时,ENPER的平均请求内容的时延相比Best-routing减少了约43%,与CATT相比减少了17%.

图6 发布者服务器负载减小率随Zipf的变化趋势

图6分析了Zipf流行度分布指数对发布者服务器负载的影响.发布者负载减小率越大表示兴趣包可以更多的在网络中的缓存节点上获得请求的内容.三者比较性能最优的是ENPER.在Zipf=1时,ENPER路由机制可以减少83%的发布者服务器的负载,其原因是通过改变节点的势能,兴趣包可以在边缘节点上获得请求内容,而无需到达发布者服务器.当Zipf指数增加,纵坐标对应的数值的增长速率放缓,其原因是我们采用的缓存机制为LRU,即当路由器缓存装满时,会将最近一段时间最少请求的内容淘汰.当请求逐渐集中,缓存容量大小又保持一定时,增长趋势放缓.

图7 缓存通告开销随Zipf的变化趋势

由于Best-routing不具备缓存通告能力,因此图7仅对ENPER和CATT的缓存通告开销随Zipf指数的变化进行分析.从图中可知ENPER的通告开销相比CATT更低,原因是CATT在周期时间内会将所有缓存节点的内容向周围节点以固定跳数的方式进行扩散,并且不区分请求次数很少、非流行的内容,这种盲目通告的方式会浪费带宽资源;而ENPER由于增加了边缘缓存节点的势能,兴趣包不仅仅可以受到缓存节点势能的吸引在边缘上快速命中,还由于边缘节点集中地收集兴趣包的个数,减少了上游节点存在的PIT过滤情况,能更好地统计出用户的请求分布.以外,ENPER按照流行度的预测值对缓存节点的通告范围进行区分设置,大量非流行的内容不会向周围节点发出通告报文,因此提升了缓存的内容的可用性,降低了通告的开销.

4 结束语

为了实现请求内容的就近应答,提高缓存资源的利用率,我们对内容中心网络的缓存节点和发布者节点构造了势能模型,并在此基础上提出了一种边缘节点势能增强的路由机制ENPER.通过改变靠近边缘的节点势能值,增加边缘缓存内容的吸引力,将兴趣包吸引到就近的节点上命中响应,减少了平均请求内容的时延和发布者服务器的负载;同时,还通过在边缘节点计算内容的预测流行度,对数量较少但流行度高的内容扩大范围通告,对数量较多但流行度低的内容减少或不发送通告,降低了通告报文对带宽的消耗.