基于蚁群优化的数据中心网络负载均衡算法

朱国晖，史思潮，翟鹏宇

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

在互联网发展初期，主要通过传统的负载均衡技术改善网络流量拥塞问题。当网络中的用户产生了流量，负载均衡设备根据流量的目的IP，通过服务器将流量分配到相应的链路中去。随着大数据等技术飞速发展，网络的规模也越来越大，尤其在数据中心网络中，需要提供的业务也越来越多，因此会产生大量的流量。传统的负载均衡技术不能满足网络中多业务对流量的需求，从而会引发网络拥塞问题。并且传统的数据中心网络拓扑简单，很难解决链路拥塞问题，从而导致网络传输速率较低。因此，研究人员提出了胖树[1](Fat-Tree)、BCube[2]等多种网络拓扑结构，可以为网络提供更多的链路，便于实现数据中心网络的负载均衡。

在数据中心网络中，使用最为广泛的是等价多路径[3](Equal Cost Multi Path, ECMP)算法，由于其为静态路由算法，不能适应网络流量的实时变化，因此当网络的流量急剧增加会使网络产生拥塞现象。随着网络中业务种类的不同，产生的流量大小也不同。为了可以更好地调度网络中的流量，充分利用网络资源，将数据中心网络中的流量按照大小划分为大象流和老鼠流[4-5]。传统的ECMP算法会将网络中的大象流调度到同一路径中，使得链路产生拥塞现象，导致网络负载不均衡现象。文献[6]中提出了Hedera策略，可以随着网络中实时变化的动态流量而调整策略，将占用链路容量的10%作为大象流，通过全局优先匹配流量调度(Global First Fit, GFF)算法在网络中搜索，将得到的第一条满足大象流分配的路径作为大象流路由。随着网络中流量不断扩大，大象流可调度的路径将会不断减少。因此，Hedera策略不能保证所有数据流都能合理的调度，易使得网络产生拥塞现象，并且导致网络资源不能充分的利用。文献[7]提出一种差异化调度算法，将网络中的流量划分为老鼠流和大象流，并且分别提出不同的算法进行调度。大象流通过封锁岛路径设置算法，老鼠流则使用多路径算法，通过分配合理的加权值将老鼠流分配到多路径中，并且随着网络流量变化动态地调整策略。文献[8]中提出粒子群优化算法，主要针对网络中的大象流进行调度。在网络中设定一个阈值，当负载超过设定的阈值时，通过调度优化的粒子群算法重新路由网络中的大象流，避免链路产生拥塞现象。文献[9]同样设定阈值，当网络中的负载超过设定的阈值，大象流负载均衡机制通过将大象流划分为多个老鼠流，并且在选择下一跳交换机时，将负载最小作为选择条件。最终将大象流分配到其他路径中，避免产生拥塞现象。文献[10]针对大象流易导致拥塞问题，对可调度的路径进行加权值计算，将大象流合理地分配到多条路径中，从而实现网络负载均衡。文献[11]以最小化最大链路利用率为目标，提出了基于蚁群算法的软件定义网络(Ant Colony Optimization-Software Defined Network，ACO-SDN)机制。通过建立整型线性规划(Integral Linear Programing，ILP)模型，将拥堵的链路通过调度蚁群算法重新路由，实现负载均衡的效果。但是，该蚁群算法收敛速度变慢，对网络整体性能都有影响。

针对ECMP算法调度大象流易产生链路拥塞导致网络负载不均衡现象，在Fat-Tree拓扑结构下，拟提出基于蚁群优化的动态链路负载均衡(Dynamic Load Balancing based on Ant Colony Optimization，DLB-ACO)算法。该算法首先计算一个周期内的链路负载方差，降低瞬时负载极值对负载均衡度的影响，避免资源的浪费。其次，对蚁群算法的路径选择概率引入混沌策略和分段调节挥发因子，增强算法的全局搜索能力，可以较大概率地计算出全局最优路径，实现网络的负载均衡。最后，通过与ECMP算法和GFF算法对比，验证所提DLB-ACO算法的有效性。

在数据中心网络中，ECMP算法调度大象流会导致链路产生拥塞现象，使得网络负载不均衡。因此，所提DLB-ACO算法通过在SDN控制器中部署相关模块功能实现数据中心负载均衡，总体实现的框架如图1所示，其由控制器与Fat-tree网络拓扑两个部分组成。

图1 DLB-ACO总体框架

由图1可以看出，SDN控制器包括流量监控、大象流检测、负载均衡度计算、DLB-ACO调度路径计算和流量管理等5个模块。Fat-tree网络主要由主机和交换机组成，在数据中心网络对于大象流的整体调度的具体步骤如下。

步骤1流量监控模块主要功能是监控整个数据中心网络的数据流，并将数据流信息传递给大象流检测模块。

步骤2大象流检测模块主要检测是否有大象流，如果有，将信息传递给负载均衡度计算模块。

步骤3负载均衡度计算模块主要计算网络链路的带宽方差，判断整个网络的负载均衡度，当网络中大象流超过设定的阈值，就调度DLB-ACO算法模块。

步骤4DLB-ACO算法模块主要为大象流的调度重新计算转发路径，并将计算出的转发路径下发给流量管理模块。

步骤5流量管理模块把计算出的转发路径下发到数据中心网络中的流表项中，并由其完成大象流的重路由。

介绍针对大象流易导致数据中心网络拥塞现象提出的DLB-ACO算法实现整体过程，描述针对负载方差易受短时间内链路已用带宽极值的影响，并进行部分改进。最后，详述蚁群优化算法过程。

2.1 大象流流量调度机制

所提DLB-ACO算法首先设定阈值，以链路的负载方差作为网络的负载均衡度。当链路的负载方差大于设定的阈值时，触发网络中的负载均衡算法，控制器根据当前的网络情况通过优化的蚁群算法对大象流进行调度，从而计算出最佳路径，最终实现网络的负载均衡。DLB-ACO负载均衡算法的流程如图2所示。

图2 DLB-ACO负载均衡算法流程

由图2可以看出，DLB-ACO算法包括以下5个具体实现步骤。

步骤1当网络中的主机产生流量，并发送到数据中心网络中时，网络首先会调用ECMP静态路由算法对流量进行调度。物理层中的交换机会周期性地收集链路中的数据流信息，并传递给控制器。

步骤2控制器中sflow收集器会处理收集来的信息，并根据数据流的大小分类。将超过链路容量的10%划分为大象流，并且计算链路利用率。

步骤3控制器判断计算出大象流经过的链路利用率是否大于阈值60%[11]。如果大于该阈值，转到步骤4，否则转到步骤1。

步骤4根据链路的实时信息，控制器调用改进的蚁群算法重新路由大象流。将计算出的流表项转发给交换机。

步骤5交换机根据流表项重新路由大象流。之后，转到步骤2。

2.2 网络负载均衡度改进

在所提DLB-ACO算法中，控制器可以获取到全网络的链路信息，并且计算出网络的负载均衡度。通过计算全局链路已用带宽方差[12]作为网络的负载均衡度。t时刻的网络链路负载方差表达式为

(1)

在目前网络中，链路已用带宽随时间波动较大，易造成网络资源浪费。为降低此影响，在链路负载方差中引入平滑机制，某一时刻的链路负载不均衡状态会触发不必要的负载均衡算法。因此，需要忽略网络中某一时刻链路负载的极值。

通过计算一段时间内链路使用带宽变化情况，可以降低网络中某时刻产生的极值影响，使得计算出的方差值更加接近数据中心网络实际的波动情况。一个周期内网络链路负载方差计算的表达式为

(2)

式中：P表示周期时间；
T表示当前时刻。

2.3 改进的蚁群优化算法

2.3.1 选择策略

混沌现象是一种随机的现象，与大自然生物、物理及地理都有一定的联系，并且被广泛地应用在计算机技术的加密和图像处理中。为了增加路径选择的多样性，在选择下一节点的概率中引入混沌现象，可以使得选择下一节点的路径数增加。

Logistic映射产生混沌序列[13]的计算表达式为

Xi+1=μXi(1-Xi)

(3)

i∈{1,2…,n},μ∈(0,4],Xi∈(0,1)

式中，μ表示控制参数。

蚁群算法融合混沌策略之后的转移概率为蚂蚁从i到j之间的选择路径概率，其表达式为

(4)

式中：Xij表示节点i到节点j产生的混沌变量；
τij(t)表示t时刻节点i与节点j路径上的信息素；
τiu(t)表示t时刻节点i与节点u路径上的信息素；
ηiu(t)表示节点i到节点u的启发式因子；
ηij(t)为节点i到节点j的启发式因子，表示信息素τ的重要程度；
β为启发式η的相对重要程度；
Sk为蚂蚁k在t时刻可以选择的下一节点集合。

信息素更新的表达式为

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(5)

(6)

信息素初始化表达式为

(7)

2.3.2 分段调节信息素挥发因子

考虑蚁群算法在后期阶段容易陷入局部最优解，并且收敛速度也会随之降低。其中，挥发因子ρ对收敛速度和搜索能力都会产生一定的影响。ρ过大，会降低算法的收敛速度；
ρ过小，会降低全局搜索能力，得到的路径不一定是全局最优路径。因此，所提算法将挥发因子引入分段调节，在不降低收敛速度的同时，提高算法的全局搜索能力，可以较大概率地得到全局最优解，其调节的表达式为

(8)

式中：M表示最大迭代次数；
N表示算法当前执行的迭代次数。将算法分为前期、中期、后期和末期等4个阶段，每个阶段对信息素挥发因子都有对应的取值。

在经典的蚁群算法上做出改进，通过在路径选择概率中引入混沌策略，增加可能选择路径的数量，可以较大概率上得到全局最优解。同时，对挥发因子进行分段调节，增加蚁群算法的全局搜索能力和收敛速度。具体步骤如下。

步骤1将算法中所有参数初始化，蚂蚁的总数为m，最大的迭代次数为M，数据中心的链路总数初始化为L。

步骤2根据式(7)初始化链路的信息素浓度。

步骤3当为第k只蚂蚁时，根据式(4)选择选择下一跳节点(交换机)。

步骤4如果没有达到目的节点，继续重复步骤3，直达目的节点。

步骤5根据迭代的次数选择式(8)、式(6)和式(5)更新链路上的信息素。

步骤6当k≠m时，重复执行步骤3，直到k=m。

针对蚁群算法在后期存在收敛速度较低的问题，对蚁群算法做出了改进。通过分段调节挥发因子使得算法具有较强的全局搜索能力的同时还可以有较高的收敛速度，并且对路径选择概率引入混沌策略，增加路径选择的数目，可以更大概率上获得全局最优路径。

为验证所提的DLB-ACO算法的性能，在Mininet仿真平台搭建的Fat-Tree数据中心网路拓扑中，与其他两种算法比较，分别将最大链路利用率、吞吐量和网络时延作为最终的性能评价指标。

3.1 实验设置

3.1.1 网络拓扑结构

在Mininet[14]仿真平台上，搭建k=4的网络架构，SDN下的Fat-tree拓扑图如图3所示，每个链路的容量均为100 Mbit·s-1。

图3 SDN下的Fat-tree拓扑图

3.1.2 参数设置

蚁群参数设置对蚁群算法影响较大，通过文献[11]研究和综合多次试验结果进行设置，迭代次数设置为75，流量统计周期为1 s，大流监控周期为5 s，负载监控周期为5 s。两节点之间为11跳，其他主要参数值如表1所示。

表1 蚁群算法主要参数值

通过以上参数设置，将所提算法与ECMP算法和GFF算法相比较。

3.2 链路利用率、延时和吞吐量分析

为了验证ECMP算法、GFF算法与所提DLB-ACO算法的性能，设定在交错通信模式下Staggered(0,0.3)，将第一个数据中心基本物理设计单元(Point of Delivery,Pod)中的主机作为数据源产生数据流并发送，使得链路中有较高的负载，达到可以检测算法的性能。

3.2.1 平均吞吐量

吞吐量可以清楚地反映出算法对网络实时的影响情况，表示在单位时间内网络可以传输的数据量，并且还能反映出网络状态的优劣情况。ECMP算法、GFF算法和DLB-ACO这3种算法在不同流量负载下的吞吐量对比情况如图4所示。

图4 不同流量负载下的平均吞吐量

由图4可以看出，ECMP算法和GFF算法的吞吐量分别在负载80 Mbit·s-1、85 Mbit·s-1时达到最大值，之后呈下降趋势。通过不同的负载情况对比3种算法，可以看出所提的DLB-ACO算法吞吐量一直高于其他两种算法。

3.2.2 平均时延

算法的性能影响网络状态和数据流的传输时间，计算数据流的平均传输时延可以有效地反映出算法对网络系统的影响。ECMP算法、GFF算法和DLB-ACO等3种算法在不同流量负载下的平均传输时延情况如图5所示。

图5 不同流量负载下的平均时延

由图5可以看出，ECMP算法、GFF算法及所提DLB-ACO算法的平均延迟时间：在负载30 Mbit·s-1之前，3种算法的延迟基本相差不大；
在负载60 Mbit·s-1后，GFF算法和DLB-ACO算法与ECMP算法相差较大，GFF算法相对于DLB-ACO算法平均延迟时间逐渐变大；
当负载到达最高100 Mbit·s-1时，DLB-ACO算法相较于ECMP算法和GFF算法分别降低了延迟时间的38%和22%。

3.2.3 最大链路利用率

链路利用率可以反映出链路的使用情况，不同负载下ECMP算法、GFF算法和DLB-ACO这3种算法链路利用率如图6所示。

图6 不同负载下的链路利用率

由图6可以看出，DLB-ACO算法的性能最好，因为当网络中的信息有变化时，该算法会对网络链路信息实时更改。当有链路的负载均衡度超过阈值时，则启动DLB-ACO算法，对检测出的大象流重路由，避免了网络的拥塞机率。ECMP算法不能根据网络的当前信息及时作出调整，因此链路拥塞的机率和最大链路利用率会变大。GFF算法是根据大象流达到的先后顺序进行重路由，有一定的局限性。因此，所提DLB-ACO算法最大链路利用率最高。

针对数据中心网络中传统路由算法调度大象流容易造成网络负载不均衡现象，提出了基于蚁群优化的动态负载均衡DLB-ACO算法。所提算法首先计算出一个周期内的链路负载方差，降低瞬时负载极值对负载均衡度的影响，然后对蚁群算法的路径选择概率引入混沌策略，增强蚁群算法的全局搜索能力。同时，分段调节挥发因子，增强算法的收敛速度，并且可以较大概率地计算出全局最优路径，实现网络的负载均衡。最后，为了验证所提DLB-ACO算法的有效性，将其与ECMP算法和GFF算法对比。在网络负载为90 Mbit·s-1时，所提算法的平均吞吐量明显高于其他两种算法。当负载最高时，DLB-ACO算法与ECMP算法和GFF算法相比，时延分别降低了38%和22%。实验结果表明，ECMP和GFF算法整体性能低于所提DLB-ACO算法，所提算法对网络整体性能有所改进，分别在平均吞吐量和时延和最大链路利用率有所改善。