基于粒子群优化的SDN负载均衡研究

曹欲晓，徐金宝

（南京工程学院 计算机工程学院，南京　211167）

基于粒子群优化的SDN负载均衡研究

曹欲晓，徐金宝

（南京工程学院 计算机工程学院，南京211167）

软件定义网络SDN的转发平面和控制平面分离，当有新的流进入网络时，交换机不能确定对该流的操作，需要封装Packet_In消息发送给控制器，由控制器决定对该流所进行的操作。基于SDN的这种特点，传统网络中的负载均衡算法已经不再适用于SDN网络。在分析SDN网络流转发机制的基础上，建立SDN负载均衡的数学模型，应用粒子群算法对负载均衡问题进行优化，并把优化算法运行于SDN的控制器中。在Mininet上的仿真实验表明，粒子群优化的SDN负载均衡算法可以有效地均衡网络负载，提高网络性能。

软件定义网络；负载均衡；粒子群算法；流表

江苏省自然科学基金青年基金（No.BK20150730）、南京工程学院校级科研基金（No.CKJC201506）

0　引言

自上世纪90年代开始，随着技术的发展和应用的促进，因特网已经逐渐成为当今社会的基础设施之一，在人类的生产生活中发挥着愈加重要的作用。特别是最近几年，由于云计算、物联网、大数据的逐步实用化，智能手机在全球的迅速普及，网络的规模和网络中的数据流量呈现爆炸式的增长［1］。传统的基于TCP/IP的因特网架构，控制平面和转发平面紧密耦合在一起，共存于网络设备中，这种模式已经难以适应未来网络的发展需求。具体原因体现在以下几个方面：首先管理人员难以应用一种统一的自动的模式对网络设备进行管理、配置和升级，只能对设备逐一进行手工管理，效率低且容易出错，如果核心网络中的设备配置出错，将会造成大面积的网络故障。其次网络中存在多家厂商的设备，这些厂商为了维护自身的利益，尽可能把设备做地封闭化，用户无法自行在设备中增加新协议，无法对设备的功能进行修改，因此也无法对网络进行新的部署和升级。为了解决上述问题，便于对网络进行灵活的规划和对设备进行方便的管理，软件定义网络（Software Defined Network，SDN）［2］的概念最近几年被提出来并且逐渐得到学术界和工业界的普遍重视。SDN的核心思想是控制平面和转发平面分离，控制平面的决策功能集中于逻辑上集中的控制器中，数据平面的转发功能则由交换机实现，交换机按照控制器下发的流表对流进行转发，控制器和交换机通过一个标准的接口进行通信。

SDN的概念提出以后，已经在真实网络中获得了越来越多的应用。2012年4月，Google在其数据中心的骨干网络中已经全面应用了OpenFlow［3］协议，建立了SDN领域著名的B4网络。随后，Facebook也在其数据中心应用了SDN的OpenFlow技术。随着SDN的大量应用，许多新的问题也随之出现，比如多租户管理、交换机迁移、网络安全、负载均衡等。传统的基于IP的网络负载均衡是通过负载均衡器实现的，负载均衡器可以专用硬件或软件的形式出现，技术已经比较成熟。传统网络中的负载均衡算法主要有随机算法、轮询算法、加权轮询算法、最少连接算法、最快响应时间算法等。但是在SDN网络中，数据中心面对来自整个Internet的大量用户访问请求，由于交换机和控制器分离，因此交换机如何把服务请求均匀的分配到各个服务器上是一个全新的问题。本文在分析SDN网络架构的基础上，针对SDN负载均衡的特点，建立SDN负载均衡的数学模型，确定负载均衡的优化目标，最后在控制器中应用粒子群算法对SDN的负载分配进行了优化。最后在Mininet仿真环境下，应用Ryu控制器对算法进行了仿真模拟，结果表明本文提出的方法较传统负载均衡算法的性能提高1倍以上，本文的方法是行之有效的。

1　软件定义网络

相较于目前以TCP/IP为基础的Internet来说，SDN是一种全新的网络架构，而不是运行于当前网络上的一种协议，也不是对当前网络的改良方案。SDN的核心思想是控制平面和转发平面的分离［4］。SDN的架构可以用图1来说明。

图1　SDN的架构

由图1可知，从上到下，SDN一共由三层组成：应用层、控制层和数据层。应用层是用户编写的应用软件，可以通过开放的API和控制层进行信令的交互，从而实现对网络的管理和研究。控制层是把原来的路由器、交换机、防火墙等传统网络设备中的网络管理、路由规划等管理功能抽取出来集中在一起而形成的一个控制软件。控制层的核心是控制器。数据层由大量称为交换机的网络设备组成，SDN中的交换机不同于传统网络中的交换机，其不但具有第二层的交换功能，还具有第三层的路由等其它功能，能完成第2-4层的数据转发任务，再者SDN交换机本身不具备数据转发决策功能，只能根据控制器下发的流表工作。

SDN的控制层和数据层之间的接口称为 “南向接口”，目前OpenFlow协议已经成为事实上的南向接口标准。控制层通过OpenFlow协议向数据层下发转发策略。应用层和控制层之间的接口称为“北向接口”，由于应用层各种应用变化较多，目前尚没有形成统一且标准的北向接口，但主流的控制器都以REST API的方式对应用层提供北向接口。

2　粒子群优化的SDN负载均衡

2.1问题描述

相对于网络技术的发展，服务器CPU的处理速度和内存访问速度的增长要落后于网络带宽和网络访问量的增长，这就使得服务器的负载能力成为了网络的瓶颈。另外关键的网络应用也要求服务器必须随时能提供可靠的服务，因此对于SDN来说，负载均衡是一个必须面对和解决的问题。所谓负载均衡就是按照某种策略尽可能地把来自外部的访问平均分配到服务器集群中的每台服务器上，使每台服务器的负载均匀稳定且网络中没有拥塞。

在SDN网络中，当有流进入网络后，交换机对流进行解析并和流表进行匹配，如果匹配成功，则按照流表中的操作项对流执行相应的操作 （转发或丢弃）；如果匹配失败，交换机把流封装成Packet-In消息送给控制器，由控制器决定流的去向并生成新的流表下发给交换机，交换机根据新的流表对流进行处理［5-6］。可见当有新流进入SDN网络时，控制器需要根据服务器的负载情况、链路的占用率等多种因素决定流的转发路径，并在交换机没有发送Packet-In消息期间，定时检查整个网络的运行状况，并对转发策略做出实时调整。

2.2粒子群算法

粒子群优化 （Particle Swarm Optimization，PSO）算法［7］由Eberhart和Kennedy提出，是一种受鸟群觅食行为启发而发现的群体智能算法。粒子群算法中，每个粒子的位置对应问题的一个解，每个粒子既不断飞向自身的最优位置又追寻整个群体中最优粒子的位置，在解空间中不断飞行，通过多次迭代求得问题的最优解。

设群体规模为Q，粒子在D维空间中飞行，则每个粒子的速度和位置更新可用式（1）和式（2）表示：

式（1）中，w称为惯性因子，用来平衡个体最优和全局最优，c1称为个体学习因子，用来表示粒子对自身最优位置的跟踪，c2称为全局学习因子，用来表示粒子对群体中最优粒子的跟踪，r1和r2是区间［0，1］上的随机数，PB称为粒子的个体最优值，GB称为粒子群的最优值。

2.3粒子群优化的SDN负载均衡

应用粒子群算法求解优化问题时，首先要确定粒子的编码方案，其次要根据优化目标设计相应的适应值函数。本文以SDN网络通信链路的数目作为粒子的维数，以链路的带宽使用率作为粒子在每一维上的坐标，带宽使用率可以通过专用软件监控得到，带宽使用率的数值范围从0到100。假设SDN中共有K条链路，如果要使SDN网络的负载达到最为均衡的状态，则所有链路的带宽使用率应该最为接近，故可构造适应值函数如式（3）所示。

其中：

函数f1表示所有链路负载差值平方的和，f1的值越小则链路之间负载的差值越小，SDN网络的负载均衡程度越好。f2表示所有链路的负载和整个网络的平均负载差值平方的和，显然f2的值越小，每条链路的负载越接近整个网络的平均值，SDN的负载均衡程度越好。α和β分别是f1和f2的系数，表示f1或f2对适应值的贡献程度，α和β的值可调，但要满足（α+β=1）的条件。

下面给出应用粒子群算法优化SDN负载均衡的步骤。

①设置算法初始参数：确定种群规模Q、惯性因子w、学习因子c1和c2值。

②初始化每个粒子的位置和速度。位置矢量由式（6）给出，速度矢量由式（7）给出。

Loadj是第j条链路的带宽使用率，rand（）是随机函数，VMin是速度的最小值，VMax是速度的最大值。

③利用式（3）-（5）计算每个粒子的适应值，求出每个粒子的个体极值和整个种群的全局极值。

④由式（1）计算粒子的速度，由式（2）更新粒子的位置。

⑤求出最优粒子的适应值函数值和位置。

⑥重复步骤③-⑤，直至达到规定的迭代次数。

迭代结束后，处于最优位置的粒子的位置矢量就是控制器对新流的均衡分配方案。

3　仿真结果及分析

为了验证本文提出的基于粒子群的SDN负载均衡算法的性能，利用Mininet［8］软件进行了仿真测试。仿真环境为Ubuntu12.04操作系统，仿真软件Mininet2.2.0，控制器是Ryu。首先应用Mininet生成图2所示SDN网络，再使用iperf软件生成TCP流和UDP流模拟对网络的访问。在相同的网络环境下，分别运行负载均衡的随机算法、轮询算法、本文提出的粒子群优化算法各100次，取其平均值作为测试的结果列于表1中。由表1可见，粒子群优化的SDN负载均衡算法无论在延时还是在丢包率上，性能都较随机算法和轮询算法有明显提高。

图2　测试网络拓扑

表1　三种负载均衡算法的性能比较

4　结语

SDN网络是一种全新的网络架构，设计思想是把数据流的转发动作和做出这种动作的逻辑决策分离，这样人们就可以在控制器上进行新协议的部署以及网络功能的优化，极大地增强了网络的灵活性，是未来网络发展的方向。由于SDN网络和传统网络的运行机制不同，这就导致了SDN网络的负载均衡也不同于传统网络。在SDN网络中，当有新流进入网络时，交换机的流表中尚没有针对该流的流表项，因此需要控制器做出对该流的转发决策，这时控制器根据实时反馈的链路负载情况，应用粒子群算法计算出负载均衡最佳的一条链路分配给新进入网络的流。通过用Mininet软件仿真证明，本文提出的粒子群优化的SDN负载均衡算法较传统算法有着更好的表现，在真实网络中是完全可行的。

［1］左青云，陈鸣，赵广松，等.基于OpenFlow的SDN技术研究［J］.软件学报，2013，24（5）：1078-1097.

［2］McKeown N.Software-Defined Networking.In：Proc.of the INFOCOM Key Note.2009.http：//infocom2009.ieee-infocom.org/technical-Program.htm

［3］Mckeown N，Anderson T，Balakrishnan H，Parulkar G，Peterson L，Rexford J，Shenker S，Turner J.OpenFlow：Enabling Innovation in Campus networks.ACM SIGCOMM Computer Communication Review，2008，38（2）：69？74.［doi：10.1145/1355734.1355746］

［4］Open Networking Foundation.SDN Architecture Overview，Version 1.0.2013.

［5］Software-Defined Networking Research Group（SDNRG）.2013.http：//irtf.org/sdnrg

［6］Tootoonchian A，Ganjali Y.HyperFlow：A Distributed Control Plane for OpenFlow.In：Proc.of the 2010 Internet Network Management Workshop/Workshop on Research on Enterprise Networking（INM/WREN）.San Jose：USENIX Association，2010.http：//dl.acm.org/citation.cfm？id=1863136

［7］Kennedy，J，Eberhart R C.A Discrete Binary Version of the Particle Swarm Slgorithm［C］.The 1997 Conference on System，Cybernetics and Informatics.Piscataway，NJ USA：IEEE Press，1997：4104-4109.

［8］Mininet Team.Mininet：An Instant Virtual Network on Your Laptop［EB/OL］.（2016）［2016］.http：//www.mininet.org/.

Software Defined Network；Load Balance；Particle Swarm Optimization Algorithm；Flow Table

Research on SDN Load Balance Based on Particle Swarm Optimization

CAO Yu-xiao，，XU Jin-bao
（School of Computer Engineering，Nanjing Institute of Technology，Nanjing 211167）

Software Defined Network’s（SDN）controller platform and data platform are separated，when new data flow comes to SDN，switch can't decide to how to deal with the flow，then Packet_In message is sent to controller and controller decides which action can be added to the new coming flow.Based on the feature of SDN，traditional load balance algorithm is not suitable to SDN.After the mechanism of flow transmutation of SDN is analyzed，the mathematic model of SDN load balance is built.Then particle swarm optimization algorithm is used to solve SDN load balance problem and the algorithm is built in SDN controller.The emulation on Mininet platform proves that PSO load balance algorithm can equal load of SDN and increase performance of network effectively.

1007-1423（2016）29-0018-04

10.3969/j.issn.1007-1423.2016.29.004

曹欲晓（1971-），男，硕士，讲师，研究方向为智能算法、软件定义网络徐金宝（1970-），男，硕士，副教授，研究方向为数据挖掘、智能算法

2016-07-21

2016-09-15