基于内容迁移的ICN 缓存负载均衡机制

李 惟，孙 鹏，韩 锐

（1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190；2.中国科学院大学，北京 100049）

信息中心网络（ICN）是未来网络研究的主要方向。目前的互联网架构以主机为中心，依赖发送者驱动的端到端通信模式[1]。互联网技术和应用不断发展，互联网用户数量和多媒体应用流量成指数级增长，用户对网络的主要需求已经转变为对海量内容的访问。ICN 采用独立于位置的内容命名、请求-响应模型和网内缓存来实现有效和可靠的内容分发[2]，很好地应对这一转变。常见的ICN 网络架构有DONA[3]、NDN[4]、PURSUIT[5]、NetInf[6]。

网内缓存是ICN的重要内容，ICN 路由器通过配置额外的存储器来缓存途经内容，从而可以响应用户的请求，这大大降低了内容访问延迟和带宽利用。然而由于缓存节点的缓存空间有限，高效地利用缓存资源是提高缓存网络系统性能的主要研究方向。LCE（Leave Copy Everywhere）是许多ICN 网络架构的默认缓存策略，但内容返回时沿途所有缓存节点都会缓存该内容，这种激进的缓存方式会造成大量的缓存冗余、节点缓存替换频繁、缓存性能较低。LCD（Leave Copy Down）试图解决LCE的缓存冗余问题[7]，LCD 在命中节点的下游节点缓存该内容，潜在地考虑了内容的流行度，随着请求次数的增加被复制到用户边缘，但如果用户频繁请求流行度较高的内容，会出现缓存节点服务负载过重的性能瓶颈，网络局部陷入拥塞。文献[8]提出了基于节点中心性的缓存放置算法，内容被缓存在返回路径上中心性最大的节点上，但是这种机制会造成节点间负载分布的不均衡，内容缓存和响应集中在中心性大的节点上，而其他缓存节点的缓存资源没有得到充分利用。

针对上述缓存机制造成负载分布不均、从而大大降低了网络资源利用率的问题，文中提出了基于内容迁移的负载均衡机制。首先将节点负载区分为服务负载和缓存负载，针对两种情况，分别设计了负载的衡量方式以及负载均衡机制的触发条件，其次设计了迁移内容和迁移节点选择机制，实现高效的内容迁移，充分利用网络缓存资源实现负载均衡。

1 相关研究

文献[9]在传统网络负载均衡研究的基础上，从负载均衡决策指标、功能位置等分析了负载均衡在ICN 中的挑战。当负载均衡机制实现在网络全局控制器中时，主要分为基于请求的负载均衡和基于队列的负载均衡两种类型。基于请求的负载均衡试图将请求分配给最适合节点，如轮询调度算法[10]和Scheduling-based 算法[11-12]，基于队列的负载均衡试图将作业从一个队列迁移到另一个队列来平衡副本的作业队列，如启发式负载均衡[13]。两种类型都依赖于服务能力、副本占用率等指标作出决策。

当负载均衡机制实现在缓存节点中，文献[14]提出了一种基于蚁群分工启发的ICN 负载均衡机制，定期预测路由器和链路负载并设计了蚁后表、雄蚁和工蚁包，通过分工协作将部分待处理数据包迁移至轻载节点或链路。文献[15]针对现有缓存机制造成缓存负载分布不均的情况，将内容迁移与缓存策略结合，提出基于内容迁移的协作缓存机制，当缓存压力过大时选择合适的邻居节点进行缓存内容的转移，实现负载分担。文献[16]面向边缘节点的缓存冗余问题，提出一种基于内容迁移的路径内外协作缓存机制，该机制战略性放置一路径外缓存节点支持额外的缓存级别，用来缓存路径内缓存节点卸载的内容。

2 负载均衡机制

文中设计的负载均衡机制流程如图1 所示。

图1 负载均衡机制流程

负载均衡机制分为以下两个过程：

1）缓存节点周期性监控∆t时间内的负载状况，并根据邻居状态表判断节点是否重载。

2）重载的节点触发负载均衡机制，从缓存内容中选择迁移内容，从邻居状态表中选择迁移节点进行内容迁移。

2.1 负载监控和负载均衡机制触发

在该文负载均衡机制中，节点的负载被区分为服务负载和缓存负载。服务负载过重表示由于用户的请求不均衡，造成节点间服务请求的负载不均衡的情况，应当考虑利用网络内其他节点的服务能力，迁移相应内容均衡过重节点的服务请求。缓存负载表示由于缓存策略的缺陷，内容的放置集中在某些重要的节点上，发生频繁的缓存替换，应当考虑利用网络内其他节点的缓存资源，迁移相应内容充分利用网络资源提高网络性能。

服务负载和缓存负载对应的统计指标分别为缓存利用率和缓存替换率。首先引入缓存利用率，记为，将其定义为单位采样时间内节点v中命中内容的大小与总缓存容量大小的比值，作为服务负载的评价指标。缓存替换率记为，将其定义为单位采样时间内节点v替换内容大小与总缓存容量大小的比值，作为缓存负载的评价指标。

为每个缓存节点增添一张邻居状态表，邻居状态表的作用是记录缓存节点两跳半径内邻居节点的负载情况，通过这些记录可以计算局部的平均负载，邻居状态表的结构如表1 所示。

表1 邻居状态表结构

定义邻居节点集合为R={Ri,i=1,2,…n}，邻居节点周期性地向缓存节点报告负载情况，缓存节点会更新邻居状态表。根据邻居状态表计算局部的平均缓存利用率和缓存替换率。

采用阈值触发机制，当缓存节点的负载情况超过阈值时，触发相应的负载均衡机制。将服务负载阈值和缓存负载阈值分别设置为局部负载平均值UAaverage和RPaverage，对于缓存节点v，当UA(v)>UAaverage或RP(v)>RPaverage时，节点触发负载均衡机制，选择相应的缓存内容和邻居节点进行内容迁移。

2.2 迁移内容和迁移节点选择

为了实现有效的负载均衡，需要选择合适的内容进行迁移。根据两种重载的情况，选择迁移内容时需要考量内容的流行度。当服务负载过重时，缓存节点提供过多的请求服务，节点性能下降，应当选择流行的内容进行迁移，实现热门内容在邻域的扩散，均衡节点的服务请求；当缓存负载过重时，缓存节点内容替换频率极高，内容可用性下降，应当将流行内容保留在自己的缓存中，选择较冷门的内容迁移到邻居节点，充分利用缓存资源。

为了实现上述思想，对缓存内容采用二级LRU队列进行管理，兼顾缓存内容的请求频率和新近性，如图2 所示。

图2 二级LRU队

将缓存空间分成二段LRU，当新内容被缓存时，它被置于二级LRU的头部，命中内容被提升到一级LRU的头部，一级LRU 替换的内容被降级到二级LRU的头部，二级LRU 替换的内容被删除。当服务负载过重时，从一级LRU 头部位置选择迁移内容，而当缓存负载过重时，从二级LRU 尾部位置选择迁移内容。

当缓存节点服务负载过重时，内容迁移的主要目的是利用邻居节点的服务能力均衡节点的服务请求，分散网络局部拥塞的流量；当缓存负载过重时，内容迁移的主要目的之一是利用邻居节点的缓存内容来延长内容在网络中缓存的时间。为了选择合适的迁移节点，根据邻居状态表记录的信息设计迁移节点选择机制。

给定邻居节点集合R={Ri,i=1,2,…,n}，根据缓存替换率RP(i)是否为0，将R划分为RRP=0={Ri,i=0,…,m}和RRP>0={Ri,i=1,…,(n-m)} 两个集合。服务负载过重的情况下，若存在RRP=0，从RRP=0中选择缓存利用率最低的节点作为迁移节点，若不存在RRP=0，从RRP>0中选择缓存利用率最低的节点作为迁移节点；缓存负载过重的情况下，若存在RRP=0，从RRP=0中选择缓存利用率最低的节点作为缓存节点，若不存在RRP=0，从RRP>0中选择缓存替换率最低的节点作为迁移节点。具体过程如算法1所示。

算法1：迁移节点选择

缓存替换率为0的邻居节点集合：RRP=0={Ri,i=0,…m}

缓存替换率大于0的邻居节点集合：RRP>0={Ri,i=1,…(n-m)}

迁移节点：j

3 性能分析

3.1 实验环境

为了验证负载均衡机制的缓存性能，基于Icarus缓存模拟器展开仿真实验。选择LCE、CL4M[8]和为两种缓存机制增加负载均衡机制的LCE_2、CL4M_2进行对比，对于LCE和CL4M 采用LRU 作为缓存替换策略。实验中的仿真拓扑选择GEANT（欧洲学术网络），其中节点度为1的节点被设置为客户端，结构如图3 所示。

图3 实验拓扑结构

实验参数设置如表2 所示。内容总数为3×105，正式测试开始前用3×105的请求进行环境预热，用于测试的请求数为6×105，用户请求到达服从泊松分布，请求速率为10 次/s。每个节点的缓存大小相同，缓存大小比率是网络缓存大小和内容总数的占比，其默认值为0.01，变化范围为[0.001，0.002，0.004，0.01]。内容请求服从Zipf 流行度分布，参数α默认值为0.6，变化范围为[0.2，0.4，0.6，0.8，1.0]。主要采用的性能评价指标为：1）缓存命中率：用户请求被缓存响应的概率。2）缓存负载分布：各节点被选中为缓存节点的次数[16]。

表2 参数设置

3.2 实验结果

3.2.1 缓存命中率

该小节首先研究4 种缓存机制下不同网络参数对缓存命中率的影响。由图4（a）所示，随着Zipf 参数的增加，各种缓存机制的缓存命中率也得到提高。更高的α表明用户对流行内容请求的偏向性更高，各机制下缓存放置策略和缓存替换策略均倾向于流行内容的缓存，内容热度差异越大，缓存的效果越明显。其中，增加负载均衡机制的LCE_2和CL4M_2 在不同Zipf 参数下的缓存命中率均高于对应的LCE和CL4M。由图4（b）可知，随着缓存容量的增加，缓存节点可以缓存更多的内容，各种缓存机制的缓存命中率随之增加。其中，由于提出的负载均衡机制通过内容迁移，有效地利用了邻居节点的缓存资源，提高了缓存资源的利用率，LCE_2和CL4M_在不同缓存大小比率下的缓存命中率均高于对应的LCE和CL4M。

图4 不同参数对缓存命中率的影响

3.2.2 缓存负载分布

该小节研究4 种缓存机制下缓存负载分布的情况，通过统计节点的累积缓存数量来分析负载均衡机制对负载分布均衡性的影响。在该文负载均衡机制中，缓存节点监控自身负载状况，如果高于节点邻域的平均情况，选择内容进行迁移。由图5（a）和图5（c）所示，LCE和CL4M 均存在负载分布不均衡的情况，CL4M选择传输路径上中心性最大的节点来缓存内容，负载分布不均衡的情况更为明显。如图5（b）和图5（d）所示，采用负载均衡机制后，LCE_2和CL4M_的负载分布更为均匀，并有效地利用了所有节点的缓存资源。

图5 不同机制下缓存负载分布

4 结论

针对现有ICN缓存机制会造成节点间负载分布不均衡的问题，提出了基于内容迁移的负载均衡机制。该机制对节点的服务负载和缓存负载进行监控，并维护节点邻居的负载状态，当负载过重时，根据缓存利用率、缓存替换率等信息选择适合的邻居节点进行内容迁移，充分利用缓存资源实现负载均衡。仿真结果显示，采用负载机制在缓存命中率、网络资源利用方面有良好的表现。在未来的工作中，将验证其在真实网络环境下的性能并优化相关算法、完善研究内容。