蚁群分工启发的ICN负载均衡机制*

任珂欣，王兴伟，马连博，黄 敏

1.东北大学 计算机科学与工程学院，沈阳 110169

2.东北大学 软件学院，沈阳 110169

3.东北大学 信息科学与工程学院，沈阳 110819

1 引言

随着网络不断发展，大量终端加入网络[1]，用户请求的数量与过去相比增长幅度巨大，这使得大量数据涌入网络，从而导致网络流量激增[2]。信息中心网络（information centric networking，ICN）能够提供网内缓存机制，这一定程度上减少了网络流量[3]，但信息中心网络中的内容数量庞大，而且网络中的路由器节点缓存能力有限[4]，因此大量内容仍然需要从网络的内容服务器中获取。缺乏有效的负载均衡机制会导致单一内容服务器负载过重，网络局部陷入拥塞，路由时延增加等一系列问题。由于以上原因，急需提供一种有效的面向ICN的负载均衡机制。

目前已经有一些对ICN拥塞控制机制的研究，但是这些研究没有考虑网络的整体负载。文献[5]提出了一种基于滑动窗口的ICN拥塞控制机制，当路由器检测到拥塞时沿兴趣包路径的反方向发送NAK（negative acknowledgement），并缩小滑动窗口，收到NAK的节点接口权重减小。文献[6]设计了一种缓存策略和一种路由策略控制网络流量，一方面通过提高缓存命中率缓解拥塞，另一方面当检测到某条链路拥塞时，兴趣包不选择拥塞链路对应的接口进行转发，而是重新选择转发接口。与文献[6]中的单路径路由策略不同，文献[7]设计了一种基于多路径的拥塞避免机制，在为请求节点设置工作路径的同时，为其分配一条备用路径，当工作路径发生拥塞时，请求节点选择备用路径转发。文献[8]采用慢开始和滑动窗口结合的方式实现拥塞控制机制。以上机制可以提供兴趣包路由过程中某段链路的拥塞控制，但没有考虑全局的负载是否均衡。此外，上述设计是在路由器检测到拥塞后触发负载均衡机制，但拥塞的发生可能会造成丢包等问题，这不仅会导致网络能耗增加，同时会提高时延，使得用户的服务体验质量降低。除了因为链路传输速率无法满足网络的输入负载外，路由器的处理速度无法满足网络请求速度也是网络瓶颈之一。基于以上原因，本文设计的负载均衡机制定期对路由器和链路在一段时间后的负载进行预测，并通过预测负载来判断是否需要执行负载均衡机制。

网络负载与路由过程息息相关[1]，因此本文设计路由机制用于解决网络负载不均衡的问题。由于基于仿生的网络具有很好的自组织性[9]，与预计算策略相比[10]，基于仿生的负载均衡更加灵活[11]。在众多仿生算法中选择基于蚁群算法设计路由策略，是因为ICN路由的思想与蚁群行为具有相似性[12]。首先，ICN关注内容本身而非内容位置[13]，蚂蚁关注食物本身而非食物位置；其次，在路由过程中，蚂蚁相当于兴趣包，兴趣请求节点相当于蚂蚁巢穴，内容相当于食物，蚁群寻找到食物源的最短路径即寻找到内容提供者的最短路径。本文设计的路由机制需要综合考虑路由路径长度和路由器及链路负载，返回由请求节点到内容源节点的最优路径。

自然界中的蚂蚁包括蚁后、雄蚁和工蚁。蚁后是具有生殖能力的雌性，负责繁育工蚁，但无法直接参与觅食行为；雄蚁的主要职责是与蚁后交配产生工蚁；在蚁群中，工蚁的数量最多，它们的主要职责包括采集食物，建造巢穴，哺育幼虫等。与天然蚂蚁对应，本文将蚂蚁分为3类。蚁后是一个表结构，其中包含局部范围节点的预测负载信息，根据蚁后表可以判断是否需要生成工蚁，并触发蚁群分工启发的路由器负载均衡机制或链路负载均衡机制；雄蚁是一种请求应答报文，通过雄蚁与当前节点的邻居节点通信，以获得生成本地蚁后表需要的内容并判断是否触发负载均衡机制，即通过雄蚁与蚁后的结合，判断是否需要生成工蚁；与自然工蚁采集食物的行为对应，负载均衡机制中的工蚁根据链路信息素浓度在负载均衡机制中迭代出到达内容服务器的最优路径。由于ICN具有网内缓存的能力，网络中的路由器节点既相当于食物源又相当于蚂蚁的巢穴。每一个节点都包含一个蚁后、若干雄蚁和若干工蚁，且工蚁的数量远多于雄蚁。这种设计与自然界中蚂蚁数量的分布也是一致的。

本文的主要贡献是提出了蚁群分工启发的ICN负载均衡机制（ant swarm cooperation inspired ICN load balance scheme，ASCLB）。首先设计了负载的衡量方法和预测方式，使用预测负载判断网络负载情况，可以避免拥塞发生；其次设计了不同种类的蚂蚁，并对它们在机制中的作用进行了说明，通过不同种类蚂蚁间的协作，可以实现全网负载均衡，而非以往设计中的单一接口拥塞控制；最后阐述了负载均衡机制的触发条件和执行过程，本文不仅考虑信道对数据传输的影响，而且还考虑了路由器的数据处理能力。

2 系统框架

本文设计的蚁群分工启发的ICN负载均衡机制系统框架如图1所示。

本文设计的蚁群分工启发的负载均衡机制定期预测节点的局部负载。负载均衡机制分为以下几个过程：

（1）预测当前节点在t+Δt时刻的负载，并将数值记录在蚁后表中。

Fig.1 System framework图1 系统框架

（2）节点向其相邻节点发送雄蚁请求报文，以获取局部预测负载情况，并根据邻居节点返回的雄蚁应答报文填写蚁后表。

（3）节点向其邻居节点发送包含当前节点负载预测值和预测负载平均值的雄蚁应答报文。通过蚁后表和雄蚁应答报文判断当前节点是否需要执行蚁群分工启发的负载均衡机制。

每个路由器节点都包含两种队列：存放未处理数据的消息队列和接口的缓冲区队列，由消息队列的长度可以判断路由器节点负载情况，由接口缓冲区队列长度可以判断链路负载情况。为简便起见，仅考虑消息队列中未处理的兴趣请求数目。负载均衡机制周期性地对网络中的路由器和链路的负载情况进行预测，防止网络中出现严重的拥塞甚至瘫痪。如果路由器的消息队列过长，则触发路由器负载均衡机制，如果转发接口的缓冲区队列过长，则触发链路负载均衡机制。

路由器负载均衡机制是将该路由器消息队列中部分亟待解决的包迁移至网络内负载较轻的路由器，在保留原有的路由器到内容服务器虚链路的前提下，为该路由器分配一条到内容服务器的最优路径，在这条路径上选择负载最轻的下游节点作为辅助节点，并将负载过重节点的部分待处理内容迁移至辅助路由器。链路负载均衡机制是通过执行蚁群算法，在保留原有的路由器到内容服务器虚链路的前提下为该路由器分配一条到内容服务器的最优路径，并将队列中的一部分包转移到新的转发接口的缓冲区队列。

本文设计的节点模型包括可以处理并转发请求的路由器节点以及包含永久内容副本的内容服务器。在逻辑上路由器节点知道与其直接相连的内容服务器节点，但它们之间实际上是一条由多段物理链路连接起来的虚链路。路由器节点除包含CS（content store）表、PIT（pending interest table）表和FIB（forwarding information base）表之外，还包括本文设计的蚁后表。蚁后表的作用是记录节点局部的负载情况，包含当前节点的邻居节点中重载节点和轻载节点的负载，通过这些记录可以计算出局部的平均负载。蚁后表的结构如表1所示。

网络路由器节点集由R表示，链路集由E表示。局部重载节点和局部轻载节点个数取决于路由器节点的邻居节点个数。蚁后表中最多包含两个局部重载节点和两个局部轻载节点，最少包含一个局部重载节点和一个局部轻载节点，节点属于集合R。t代表当前时刻；Δt代表一段时间间隔；表示路由器节点Ri在t+Δt时刻预测的负载值；同理；表示t+Δt时刻节点Ri局部负载的平均值。

3 蚁群分工启发的负载均衡机制

3.1 负载预测

为了防止拥塞发生，ASCLB定期对路由器和链路的负载进行预测。由于局部回归估计具有较高的渐近效率和较强的适应设计能力，且能有效地解决边界效应问题[14]，本文引入LR（local regression）算法对负载进行预测。以对路由器节点的负载预测为例，路由器节点在t+Δt时刻的负载情况可以根据以下公式计算。为了更精确地估计负载值，引入时间权重函数w(u)。其中u的定义如式（2）所示：

其中，Δ(q)t是时间阈值，Δt越接近Δ(q)t，则估计值的参考价值越小，当Δt超过Δ(q)t时，则预测的结果不具有参考价值。

平方损失函数Q用来估计预测负载值与实际负载值之间的误差，因此平方损失函数Q值越小，估计值越准确。是路由器节点Ri在t时刻的负载值。

显然，当Q达到最小值时，有式（4）和式（5）：

由式（4）、式（5）解得α和β如式（6）、式（7）所示：

路由器节点Ri在t+Δt时刻的预测负载值如式（8）所示：

Table 1 Queen table structure表1 蚁后表结构

t+Δt时刻链路eij上的负载值计算方法与t+Δt时刻路由器节点的负载值计算方法相同，只需将替换成loadtij即可。

3.2 负载均衡策略触发条件

在使用局部回归算法计算出路由器节点Ri在t+Δt时刻的预测负载值后，节点以洪泛的方式向邻居节点发送雄蚁的请求报文，邻居节点在收到请求后，向节点Ri发送雄蚁应答报文。雄蚁的应答报文包括两个字段：节点编号和预测负载值。这个过程中，预测负载值字段是路由器节点Ri的邻居节点在t+Δt时刻的预测负载值。节点Ri收到应答报文后，根据报文内容选择局部负载最重的两个节点和负载最轻的两个节点，并以降序的方式填写在蚁后表里。结合蚁后表，根据式（9）可以计算出t+Δt时刻节点Ri的局部平均负载。

其中，N的数值取决于局部重载节点和轻载节点的个数，N∈[3,5]。

节点Ri向邻居节点广播雄蚁请求报文，在这个过程中收到的雄蚁应答报文中的预测负载值字段是路由器节点Ri的邻居节点在t+Δt时刻的局部平均负载。在收到其邻居节点发送的应答报文后，节点Ri可以判断自己是否为t+Δt时刻局部重载节点。

某节点触发负载均衡机制当且仅当其满足以下两个条件：

（1）该节点t+Δt时刻局部负载值最大的节点。

（2）该节点的局部预测负载平均值大于其邻居节点的局部预测负载平均值。

信道利用率并非越高越好，当信道利用率高于50%时，时延就要加倍。由于现在网络底层的信道复用技术多种多样，本文选择用链路对应的出口接口的缓冲区队列长度刻画信道负载。为了简单起见，假设所有接口的缓冲区队列长度相等。设置阈值a作为缓冲区的门槛值，阈值b为缓冲队列上限，则链路负载均衡机制的触发条件是接口的缓冲队列长度大于a×b。

3.3 负载均衡机制的路由策略

触发负载均衡机制后，路由器发送工蚁依据链路上的信息素浓度为当前节点增加一条到内容服务器的最优路径。由于路由路径上的路由器负载和链路负载都会影响路径性能，本文引入链路负载权重φ和节点负载权重ω，定义如式（10）和式（11）所示：

启发函数ηij(t)是节点Ri选择节点Rj作为下一跳节点的期望程度，对链路的选择不仅需要考虑链路长度，还需要考虑所选链路和路由器节点的负载，才能保证路径的效率和性能，其定义如式（12）所示：

其中，dij表示链路eij的长度。

链路上的信息量τij(t+Δt)的定义如式（13）所示：

其中，常量 ρ为挥发因子；Δτij(t)为信息量增量，其定义如式（14）所示：

其中，Q表示信息素强度。

通过链路信息量和启发函数可以计算出节点Ri选择节点Rj作为下一跳节点的概率，其定义如式（16）所示：

其中，allowedk是工蚁k允许选择的下一跳路由器节点的集合。

在为当前节点选择一条最优路径后，当前节点以先入先出原则，将消息队列中的一部分待处理包迁移至新的路径上负载最轻的节点。

4 实验分析

本文基于美国NSFNet拓扑进行仿真实现，并选取文献[15]所提机制AIRM（ACO-inspired ICN routing mechanismwithmobilitysupport）作为对比机制，NSFNet拓扑如图2所示。在Intel®CoreTMi5-4590 CPU@3.30 GHz，配置Windows7操作系统的个人电脑上，采用C++语言进行仿真实验。本文将不包含负载均衡机制的AIRM机制与加入ASCLB机制的AIRM路由机制进行对比。选取的评价指标包括：预测负载与实际负载的拟合程度、路由器负载标准差、链路负载标准差和内容服务器负载比例。在仿真实验中，0号节点和12号节点被设置为内容服务器，其余节点为路由器节点。参数设置为a=1 000，b=0.8，Δ(q)t=600 s。

Fig.2 NSFNet topology图2 NSFNet拓扑

4.1 预测负载与实际负载的拟合程度

对路由器负载和链路负载都需要使用改进的LR算法进行预测。由于对路由器负载和链路负载预测值与实际值的拟合程度基本相同，本文以路由器预测负载与实际路由器负载数据拟合程度为例进行分析。路由器预测负载与实际路由器负载数据拟合程度如图3所示。因为LR算法采用历史信息进行预测，所以随预测次数的增加，预测值会逐渐贴近实际值。网络负载平均值是网络中除内容服务器外，路由器节点负载的平均值。实验结果显示，在第46次预测后，预测负载平均值收敛到实际负载平均值。仿真实验中，在预测负载平均值收敛到实际负载平均值后，执行蚁群分工启发的负载均衡机制。

Fig.3 Fitting degree of predict load and actual load图3 预测负载与实际负载的拟合程度

4.2 路由器负载标准差

路由器负载标准差可以反映网络中路由器的负载是否均衡。在第一次采集路由器负载数据时，没有运行ASCLB。由图4可以看出，执行ASCLB机制的网络中路由器负载标准差稳定在30左右。因为ASCLB中节点无法获取全网路由器的负载情况，所以无法将路由器负载标准差降低至0，但仅获取局部负载信息相对获取全局信息的开销和时延更小。在节点触发路由器负载均衡机制后，迁移的请求数量为预测负载和局部平均预测负载的差。在路由器负载标准差基本稳定后，仍存在轻微波动，主要是因为路由器接收到的兴趣请求数量不是定值。AIRM的路由器负载标准差逐渐升高是由部分重载路由器造成的，曲线形状的变化与路由器接收到的请求数量有关。

Fig.4 Standard deviation of routers'load图4 路由器负载标准差

4.3 链路负载标准差

图5的横坐标是网络中链路负载实际值的采集次数，在第一次采集时未运行负载均衡机制。由图5中可以看出，运行ASCLB后，链路负载标准差明显降低。这种现象的原因是通过运行负载均衡机制，路由方式由单路径路由转变为多路径路由，同时，一些距离较长的路径作为迁移路径，承担了一部分负载。迁移的请求数量为在第七次数据采集中，AIRM机制的链路负载标准差增加幅度明显，主要是因为1号路由器负载增加幅度大，从而使局部链路负载加重引起的。

Fig.5 Standard deviation of links'load图5 链路负载标准差

4.4 内容服务器负载

内容服务器负载的定义是：单个内容服务器响应的兴趣请求数量与全网向内容服务器发送的兴趣请求数量比值。由图6可见，AIRM机制中0号服务器负载较重。运行ASCLB后，一部分向0号服务器发送请求的路由器将部分请求迁移至连接12号服务器的链路上。一方面均衡了链路负载，另一方面也使内容服务器负载更加均衡。内容服务器的负载比率与兴趣请求分布有关，但可以看出包含ASCLB的AIRM机制中内容服务器负载更加均衡。

5 结束语

Fig.6 Repositories'load percentage图6 内容服务器负载比例

尽管ICN的设计思想在一定程度上可以缓解负载问题，但由于网络中内容数量庞大，用户请求次数激增，高清视频等应用的兴起，针对ICN负载均衡机制的研究迫在眉睫。本文受蚁群分工协作行为的启发，设计了包含路由器负载均衡和链路负载均衡的ICN负载均衡机制。首先，采用改进的局部回归算法对路由器负载和链路负载进行估计。然后，节点间通过发送和接收雄蚁报文获取局部范围内的负载情况，并根据雄蚁报文返回的信息完善蚁后表。根据路由器负载均衡机制和链路负载均衡机制的触发条件判断某个路由器节点或某条链路的接口是否需要调用ASCLB机制均衡负载。触发负载均衡机制的节点或接口发送工蚁迭代一条区别于当前路由路径的最优路径，并将一部分负载迁移至轻载的下游节点，以实现负载均衡。实验结果表明，包含ASCLB的ICN路由机制能够有效地实现路由器和链路负载均衡，同时平衡多内容服务器负载。在此基础上，考虑如何将负载均衡机制与节能机制相结合，在网络重载时考虑负载均衡，在网络轻载时考虑节能是今后的研究方向。