基于蚁群算法的SDN负载均衡的技术研究

钟原

(中国电建集团 成都勘测设计研究院有限公司, 成都 610072)

0 引言

近年来，随着电子商务、物联网、云计算等技术地不断推进，互联网用户规模与数据流量呈几何增长，以IP网络为核心的传统网络体系架构不再适应现今的用户需求，暴露出的网络问题越来越多，特别是网络的负载均衡问题。传统IP网络发展出现了瓶颈，在部分技术研发也出现了僵局[1]。在这样的发展形式下，有必要设计出一种新型网络架构来解决传统IP网络的弊端，加快推进网络创新的步伐。软件定义联网(Software Defined Networking,SDN)[2]作为一种创新型网络体系架构，它实现了网络控制层与数据层的解耦，提高了网络管理的扩展性和灵活性，增强了网络整体智能性。因此，面对网络的负载均衡问题，利用SDN网络的技术优势可以迎刃而解。

负载均衡算法是解决网络负载均衡的主要方法。经典的负载均衡算法有轮询算法、最少连接算法、随机算法等。随机算法[3]的网络中，负载资源被任意划分到各个用户终端上，利用随机数算法新建资源服务器，完成用户终端资源的有序分发。轮询算法[4]在网络负载均衡设备中设计了一张循环链路表和一个负载均衡器，循环链路表中记录了全部网络节点的路由等信息。当负载均衡器接收到用户请求时，会把该请求依次轮流传送给各个网络节点，不断循环。该算法的设计思路较为简单，容易理解，但由于每个网络节点都有同等概率获得该请求，所以对每个节点都会产生同等的网络压力，这样会给整个网络系统带来较大性能。最少连接数算法[5]会对用户新的连接请求进行动态分配，通过负载均衡设备显示的当前活跃的用户连接数来评估网络节点的负载情况，当一个请求被接入时，节点连接数增加；当请求中止或超时，节点连接数减小。

因此，为了需求SDN网络中更加可靠的负载均衡算法，本文创新性地把蚁群算法加入SDN网络进行研究，通过SDN控制器掌控全网中链路和节点负载情况。运行在SDN控制器中的蚁群算法可以准确计算出负载最小的通信链路，从而完成网络通信链路的负载均衡，实现网络资源的有效配置，本质上根除了网络资源利用率不高、吞吐量小等不足，为后续SDN网络负载均衡技术研究提供理论依据。

1 相关原理介绍

1.1 蚁群算法基本原理

平面中存在n个地点(1，2，3，…，n)，如果把m只蚂蚁随机置于这n个地点中，设dij(i，j=1，2，3，…，n)为地点i和地点j之间的距离；为t时刻在地点i和地点j链路上余留的资源量。设t=0时，每条链路上存在的资源量相等，(c为常数)。蚂蚁k(k=1，2，…，m)在移动过程中，根据每条链路上的资源量挑选其还未经过的地点，同时在完成地点间的访问后，重新计算全部链路上余留的资源量。下一个访问地点的主要变量为：为t时刻在地点i和地点j之间剩余的资源量；为蚂蚁由地点i移动到地点j的期望值；Pij(t)为t时刻蚂蚁k地点i转到目标地点j的可能性。通常取。则Pij(t)的计算如式(1)。

(1)

在公式(1)中：allowedk为{1,2,…,n}-tabuk，对应t时刻蚂蚁k未访问的地点。与自然界蚁群觅食方式不同，蚁群算法中的蚂蚁是具有一定的记忆功能的群体。本文用tabuk(k=1,2,…,m)来保存蚂蚁当前己经访问过的地点。

另外，经过n个周期后，蚂蚁实现了一次链路选择，在进行下一次链路选择之后，需要把蚂蚁经过的链路剩余资源量补充到τij(t)集合中。此时的资源量变化情况如式(2)。

τij(t+n)=ρ·τij(t)+Δτij

(2)

其中

(3)

2.2 SDN基本架构及其负载均衡原理

是基于OpenFlow协议[6]的SDN网络基本架构模型示意图，如图1所示。

图1 SDN网络基本架构模型示意图

SDN体系结构包括数据平面，控制平面和应用平面。数据平面由网络转发设备组成，相应的路由决策被转移至控制平面，SDN交换机仅仅负责完成IP(Internet Protocl，互联网协议)分组流转发的任务。控制平面是整个控制器架构模块的核心，它通过南北向接口分别与数据平面和应用平面进行交互[7]。应用平面有许多功能性的模块组成，这些模块通过北向应用可编程接口(Application Programming Interface，API)管理控制平面，指导数据平面的分组流的转发与决策。

负载均衡技术就是一种把外来传输压力尽可能地平均分配到多个转发设备中的方法，使每个设备所承受的负载都能达到相对平衡状态，实现资源的最优化分配，可以大幅度缩短任务响应时间，增大系统对业务处理的吞吐量。一般而言，负载均衡实质是通过对每个用户所占有的资源进行动态分析，最终规划出对全部用户业务分配的公平方案。

针对不同的网络架构和网络环境，负载均衡技术实现算法也各不相同。从算法实现方式角度进行划分，负载均衡技术包含硬件负载均衡技术与软件负载均衡技术；从算法的网络流量管理角度进行划分，负载均衡技术包含静态负载均衡技术和动态负载均衡技术。

3 基于蚁群算法SDN负载均衡的实现

3.1 蚁群算法的实现过程

本文首先确定蚁群算法的各项参数：蚂蚁总个数M=8；则蚂蚁个体k的范围为1≤k≤8，k为正整数；蚁群参数α=1，β=2，资源量参数ρ=0.3，网络访问的下一节点集合为L，当前已选择的节点集合为U，默认初始节点属于集合U中。则基于蚁群算法的SDN网络的负载均衡实现流程图如图2所示。

图2 蚁群算法在SDN网络的负载均衡实现流程图

从以上算法实现流程图可以看出，算法运行首先就要进行参数初始化。蚂蚁k从起始节点开始寻路，根据计算，选择下一条链路及其对应节点，同时对集合L和U进行更新，直至蚂蚁k到达目的节点。当全部的M只蚂蚁都完成寻路之后，更新网络中链路资源量，根据算法终止条件判断算法是否结束。如果算法满足终止条件，则结束算法全部执行过程，获得满足负载均衡的最佳路由；否则算法循环执行，直到算法满足终止条件。

3.2 基于蚁群算法SDN负载均衡的实现

根据蚁群算法计算出的最优负载链路，SDN控制器把该链路的动作指令补充到相应流表项中，然后把流表项下发给SDN交换机。SDN交换机根据流表项的动作指令完成报文数据的转发。基于蚁群算法SDN负载均衡的方案如图3所示。

图3 基于蚁群算法的SDN负载均衡方案

在SDN网络中，蚁群算法的负载均衡实现步骤如下所示：

(1)对算法中全部参数初始化；

(2)蚂蚁k(1≤k≤M)根据网络链路中的资源量计算寻路概率，即挑选下一节点的SDN交换机；

(3)如果蚂蚁k没有移动到目的节点所在的SDN交换机，则转至步骤(2)，直至蚂蚁移动到目的节点的SDN交换机。即当k≠M时，k=k+1，并执行步骤(2)；

(4)蚂蚁k每访问过一个节点就会更新网络中链路资源量；

(5)计算每条链路上的平均资源量，当链路中平均资源量最大值vmax与平均资源量最小值vmin之间的差值大于10%则结束算法，并输出该条链路。如果不满足10%的结束条件，蚁群会继续进行寻路操作，直到符合算法的结束条件。

因此，基于蚁群算法的SDN负载均衡的伪代码如下所示：

begin

{输入流f，源主机Hs，目的主机Hd;

if(Hs和Hd同属一个边缘交换机)

return path(Hs,Hd);

else

{PATHS=getAllpath(Hs，Hd);

Deletepath();

for(int m = 0;m

MINWIDTH = min(PATHS.minNodewidth,PATHS.minBandwidth);

end for;

for(int k=0;k

if(MINWIDTH[k].width≥b(f))

path.width=max(path.width,MINWIDTH[k].width);

end for;

return path(Hs,Hd);

}end if;

输出转发路径path(Hs，Hd)及其瓶颈带宽path.width

}

end

4 实验仿真与结果分析

4.1 实验环境搭建

基于蚁群算法的SDN网络负载均衡测试需要搭建软件环境，本文采用Floodlight控制器[8]作为SDN控制器，然后使用Mininet工具创建包含9个SDN交换机与8个主机SDN网络，指定使用OpenvSwitch作为SDN交换机，如图4所示。

图4 基于蚁群算法的SDN网络负载均衡测试拓扑

4.2 实验仿真与结果

定义每条链路的带宽为4 M/s，同时使用iperf软件[9]产生数据流量，并产生带宽、延迟、丢包率等统计信息，设置α=1，β=2，ρ=0.3等蚁群算法参数。当测试的最优解与最差解的链路资源量之差大于10%时，则结束测试。为了避免算法测试过程中可能出现的误差，增强算法可信程度，本文选择以轮询算法来对比验证蚁群算法的效果，并进行3次对比实验，实验结果如表1-表3所示。

表1 蚁群算法和轮询算法第一次对比实验

表2 蚁群算法和轮询算法第二次对比实验

根据以上对比实验可知，本文使用的蚁群算法的保证了SDN网络链路的稳定性，没有出现过于明显的链路负载波动，每条链路上的时延和丢包率等参数指标均正常。但在轮询算法的负载测试中，表1中链路S1→S5、表2中链路S2→S5、表3中链路S1→S5均出现了明显的拥堵现象，时延与丢包率相比于蚁群算法较大。

表3 蚁群算法和轮询算法第三次对比实验

因此，在图4所示的网络拓扑中，本文提出的基于蚁群算法的SDN负载均衡解决方案可以很好地保证链路的负载处于正常水平，使得网络时延和丢包率都在正常值范围内，算法实现取得了令人满意的效果。

5 总结

本文是将蚁群算法应用于SDN负载均衡的技术研究中。文章阐述了蚁群算法的基本原理，说明了蚁群算法的数学模型，介绍了SDN基本架构和常规的网络负载均衡算法。类比自然界蚂蚁觅食过程，本文提出了一种基于蚁群算法的SDN负载均衡实现方案，通过蚂蚁对网络链路资源量的判断找到SDN网络中负载压力最小的路由。并根据Mininet软件构建了SDN模拟仿真环境，搭建了基于蚁群算法的SDN网络负载均衡测试拓扑，对比轮询算法进行时延和丢包率测试，得到了相关的实验数据。实验数据显示，在SDN网络中，基于蚁群算法的负载均衡要比传统的轮询算法等效果更加明显。因此，将蚁群算法运行在SDN网络中可以更好地实现网络链路的负载均衡。