基于改进引力搜索算法的交换机迁移策略

于明秋，周创明，王慧杰，杜瑞超

(空军工程大学 防空反导学院，西安 710051)

基于改进引力搜索算法的交换机迁移策略

于明秋*，周创明，王慧杰，杜瑞超

(空军工程大学 防空反导学院，西安 710051)

(*通信作者电子邮箱15511743667@163.com)

针对多控制器软件定义网络(SDN)中交换机迁移策略迁移代价衡量单一，不能适应交换机流量的变化的情况，提出基于改进引力搜索算法的交换机迁移策略(IGS-SMS)。在决策阶段，应用基于模糊满意度的多目标决策方法，优化目标根据隶属度大小竞争优先权；在计算阶段，通过改进引力搜索算法优化优先权高的目标函数。实验结果表明，IGS-SMS在实现负载均衡的同时，能保证传输时延与交换机重分配的指标；在实验中，当局部负载较重时，动态迁移算法(DSMA)和基于改进型拍卖交换机迁移机制(PASMM)不能缓解控制器过载，而IGS-SMS执行后无控制器过载，且负载均衡度小于DSMA和PASMM。

软件定义网络；多控制器；交换机迁移策略；引力搜索算法；模糊满意度

0 引言

软件定义网络(Software Define Network, SDN)[1]的标志性特点是将控制平面和数据平面解耦，实现集中化的网络控制。分布式控制器架构在破解控制器性能瓶颈,在解决单点失效的同时，也带来了负载不均的问题。由于已提出的分布式控制器构架，如HyperFlow[2]，其控制器与交换机之间是静态的映射关系，不能适应交换机请求流量的变化，容易造成控制器资源的失衡。

ElastiCon[3]是第一个弹性的分布式的控制器架构。在该架构中，控制器与交换机维持一种动态的映射关系，过载控制器下的交换机可以迁移到负载较轻的控制器下。ElastiCon为控制器设定一个指定的负载域，负载过大或过小时，执行交换机迁移或删除控制器的操作。交换机迁移的方式为控制器负载均衡研究提供了新的思路，其实现方法简单，控制灵活可靠，已经成为研究的热点; 但ElastiCon提出的迁移策略并不完善，在该体制下，交换机只能迁移到邻近的控制器。就近迁移是一种局部的调动，当网络中某个区域负载较重时，该方法就失去了它的作用。

对比就近迁移策略(Lowest Utilization Migration Algorithm, LUMA)[4]将交换机迁移至剩余资源使用率最低的控制器来实现负载均衡，这种方法跳出了区域的限制，在整个网络中寻找空闲资源; 但交换机与控制器之间的传输时延是受限制的，时延过大会引起数据延迟、控制一致性等问题，这就要求交换机与控制器之间的距离必须受到限制。另外，这种距离上不加限定的迁移策略还容易产生交换机的跨域通信问题。

针对负载均衡与传输时延两方面因素，文献[5]提出基于改进型拍卖的交换机迁移机制(Progressive Auction based Switches Migration Mechanism, PASMM)，将交换机的迁移问题优化成为控制器剩余资源的拍卖问题。其中，传输距离作为交换机对控制器估价函数的参数，以此来影响交换机的选择；文献[6]提出基于免疫粒子群算法的动态交换机迁移策略(Dynamic Switches Migration Algorithm, DSMA)，将最小化负载均衡度和传输距离的加权和作为优化目标，通过免疫粒子群算法求解。PASMM中传输距离与估价函数成反比，交换机近距离优先选择控制器，当局部负载较重时，算法收敛速度较慢。而DSMA优化目标是负载均衡度与传输距离加权和，在负载较重时，不能保证控制器不过载。

本文在负载均衡和传输时延的基础上，进一步考虑交换机迁移过程产生的网络代价，提出基于改进引力搜索算法的交换迁移策略(Switch Migration Strategy based on Improved Gravitation Search, IGS-SMS)。在该迁移策略中，用模糊满意度为三种优化目标设定权重，根据权重大小选择优先优化的目标，通过改进引力搜索算法快速求解。

1 问题建模

在本文的网络实例中，采用带内模式的co-located部署方案，也就是控制器与交换机节点部署在同一位置，且控制信息与数据信息采用相同的信道[7]。网络拓扑结构如图1所示。在图1网络中有30个节点，每个节点位置有一台交换机。5个控制器分别部署在节点4、11、14、23、26处。

图1 网络拓扑结构Fig. 1 Network topological structure

设在SDN中有M个控制器C={c1,c2,…,cM}，控制器的容量CA={a1,a2,…,aM}。交换机的数量为N，表示为S={s1,s2,…,sN}。交换机分布矩阵X=(xij)M×N，式中：

控制器资源使用率阈值为TH={th1,th2,…,thM}，当控制器资源使用率超过阈值时，控制器过载，触发交换机迁移机制。

定义1 目标负载，定义为各控制器资源使用率中的最大值。

定义2 平均传输时延，用交换机到控制器的平均最小传输跳数衡量。

为直观说明，以交换机到控制器的最小传输跳数衡量传输时延。其中l(ci,sj)为交换机sj到控制器ci的最小跳数。f2越小则说明平均传输时延越小。

定义3 交换机迁移数，用于衡量交换机迁移过程的代价，表示为f3，指某时刻交换机分布矩阵的列与原交换机分布矩阵对应列不相同的数量。

优化模型为：

minf1,f2,f3

(1)

xij∈{0,1}； ∀i,j

(2)

(3)

式(1)是模型的目标函数，f1,f2,f3均为越小越优型目标，属于多目标优化问题；式(2)和式(3)是约束条件，保证每个交换机只隶属于一个控制器。

2 基于模糊满意度的多目标决策

模型中f1、f2、f3没有统一的量纲，且三者之间存在制约，因此应用基于模糊满意度的多目标决策方法[8]。首先根据隶属度函数求f1、f2、f3的隶属度，进行归一化处理。优化目标是使交换机迁移过程中产生的网络代价整体最小，因此隶属度函数选择递增型函数，隶属度越大，说明产生的网络代价越大。为描述f1、f2、f3之间的制约关系，把各目标函数隶属度的最大值最小化作为优化准则，从而将该多目标问题转化为单目标问题。设f1、f2、f3的隶属度值为u1、u2、u3，目标函数转换为：

(4)

式(4)表明，函数隶属度越大，越能获得优化的优先权，即算法的每次迭代过程都为减小最大的网络代价。

f2、f3的隶属度函数可用图2表示的递增连续函数表示。

图2 f2、 f3隶属度函数Fig. 2 f2、 f3membership function

其数学表达式为：

定义阈值v、f1的隶属度函数如图3所示。

其数学表达式：

隶属度函数分为3部分，分别对应控制器负载的3种状况。当有控制器过载时，u1=1，目标负载的优化有绝对的优先权，即最低指标要保证无控制器过载；当无控制器过载且目标函数超过阈值时，f1的隶属度函数变为单调递增，与f2、f3竞争优化的优先权；当目标负载低于阈值时，u1=0，目标负载不再参与竞争，可以认为f1=v是负载均衡的最高指标。

图3 f1隶属度函数Fig. 3 f1membership function

3 模型求解

3.1 引力搜索算法

(5)

其中：Maj(t)和Mpi(t)分别为粒子Xj和粒子Xi的惯性质量；ε是一个很小的常量，防止分母为零；Rij(t)是粒子Xj和粒子Xi的欧氏距离；G(t)是在t时刻的引力常数：

(6)

其中：G0取值为100，α等于20，T是系统迭代次数。在GSA中，为了增强随机特性，设randj是范围在[0,1]内的随机数，则粒子Xi在第d维受到的合力为：

(7)

其中Mi(t)是粒子Xi的惯性质量。对于每一次的迭代过程，粒子根据以下公式更新它的速度和位置：

(8)

其中randi是[0,1]内的随机数。惯性质量根据适应度值的大小计算，在GSA中，使用式(9)更新粒子的惯性质量：

(9)

其中fiti(t)为t时刻粒子Xi的适应度。对于求最小值问题，best(t)和worst(t)定义如下：

3.2 群体反向学习机制

引力搜索算法中初始状态随机生成，这导致了算法的寻优效率不够稳定。本文引入群体反向学习机制[10-11]，优化粒子的初始分布，提高算法效率。

3.3 算法过程

算法步骤：

1)随机初始化映射关系矩阵并应用反向学习原理进行优化，将粒子的速度置零，设定循环次数Iteration；

2)计算粒子适应度，选出最小的适应度值Fbest和对应的映射关系粒子Lbest；

3)更新引力系数G(t)、best(t)、worst(t)和粒子惯性质量Mi(t)；

4)计算合力、加速度、速度、更新粒子的位置；

5)在约束条件下，对映射关系矩阵标准化，用Lbest代替负载均衡度较差的粒子；

6)返回2)，直到达到设定的迭代次数；

7)算法结束，完成一次求解，记录结果；

8)重复执行算法h次，从中选取使负载均衡度最优的映射关系粒子作为最终的结果。

4 实验仿真

实验中，采用图1的拓扑结构，初始映射关系粒子为X0=(1,1,1,1,1,2,3,3,1,2,2,2,3,3,3,2,2,2,3,3,5,4,4,4,5,5,4,4,5,5)，将交换机就近分配给控制器。假设各控制器的容量相等，值设为1；资源利用率阈值按编号顺序依次为0.9,0.85,0.85,0.9,0.95；交换机瞬时流量随机生成。实验以Matlab R2012a为平台，分两个部分进行。

实验一 验证IGS-SMS的性能，研究v在迁移策略中起到的作用。实验中，控制器平均资源占用率为68.18%。比较v取不同值时，负载均衡度、平均传输时延与交换机迁移数的变化，如图4～6。

图4中，v取值在0.6～0.9时，负载均衡度无明显变化，因为目标负载与网络中总负载量和负载分布有关，在控制器平均资源使用率达68.87%时，目标负载容易超过阈值，获得优先权；当v=1时，负载均衡度迅速增大，这是因为v=1表示只要无控制器过载，目标负载就不会成为优化的目标，此时负载均衡度得不到较好的保证。图5、图6中，随着v的取值增大，平均传输时延与交换机迁移数整体有下降趋势。因为增大v的取值，目标负载超过阈值的几率降低，优先权集中于平均传输时延与交换机迁移数。可以得出结论：v取值在控制器平均资源使用率到1之间，具体数值应根据交换机请求流量和网络性能需求设定。

图4 v对负载均衡度的影响Fig. 4 Influence of v on load balancing degree

图5 v对平均传输时延的影响Fig. 5 Influence of v on average transmission delay

图6 v对交换机迁移数的影响Fig. 6 Influence of v on the number of switch migration

从实验一可以看出：v可以有效描述负载均衡、传输时延以及交换机迁移重分配3种代价之间的制约关系；v并不直接决定目标负载权重的相对大小，v值决定的是目标负载在什么样范围内更有竞争力。当目标负载大于v时，竞争力强，可以防止出现单个控制器负载较重的情况；当目标负载小于v时，将优先权转让，兼顾传输时延与交换机重分配的指标。

实验二 比较IGS-SMS、PASMM与DSMA的负载均衡效果。首先采用实验一中交换机请求流量分布，为保证较好的负载均衡效果，IGS-SMS算法中阈值v设为0.7。实验结果如图7。

图7 负载均衡比较(一)Fig. 7 Comparison of load balancing (No.1)

计算交换机迁移执行后的负载均衡度：ρ(InitialState)=0.066 2，ρ(PASMM)=0.028 8，ρ(DSMA)=0.044 2，ρ(IGS-SMS)=0.010 4；在该实例中，初始状态，控制器3过载。交换机迁移策略执行后，3种算法均能缓解过载状况。其中， IGS-SMS最优，PASMM和DSMA较差。

然后增大交换机请求流量，再次进行实验，结果如图8。

图8 负载均衡比较(二)Fig. 8 Comparison of load balancing (No.2)

此时，控制器平均资源使用率为81.66%，负载集中于控制器2和控制器3。初始状态下，控制器2和控制器3过载。IGS-SMS执行后无控制器过载，而采用PASMM和DSMA没有缓解控制器过载。计算负载均衡度：ρ(InitialState)=0.177 7，ρ(PASMM)=0.315 8，ρ(DSMA)=0.044 6，ρ(IGS-SMS)=0.002 7。可以看出IGS-SMS的负载均衡度最优，DSMA较差， PASMM执行后的负载均衡度相对于初始状态反而有所增大。对于DSMA算法，固定的权值无法反映不同网络的需求，实验采用文献[6]中设定的1∶1的权值，在网络局部负载较重时不能突出负载均衡的主要地位。在PASMM中，交换机对控制器的选择受距离影响较大，当网络局部负载较重时，算法收敛速度慢，实验中算法迭代10 000次仍然得不到合格的结果，这就陷入了与就近迁移策略相同的困境。

5 结语

本文提出了一种基于改进引力搜索算法的交换机迁移策略。采用基于模糊满意度的多目标决策方法，权衡负载均衡、传输时延和交换机重分配3个方面的代价，应用改进引力搜索算法进行求解。实验结果表明，提出的交换机迁移策略可以有效缓解控制器过载，实现较好的负载均衡效果。另外，阈值v可以根据负载状况及网络需求自适应选取，避免了人工操作的复杂性；而改进的引力搜索算法降低了算法随机性的影响，提高了求解的可靠性。但本文没有涉及交换机请求流量过大或过小，需要添加或减少控制器的情况，需要在以后的工作中进一步研究。

References)

[1] MCKEOWN N. Software-defined networking[EB/OL].[2016-06-20]. http://yuba.stanford.edu/～nickm/talks/infocom_brazil_2009_v1-1.pdf.

[2] TOOTOOCIAN A, GANJALI Y. HyperFlow: a distributed control plane for OpenFlow[C]// Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking. Berkeley, CA: USENIX Association, 2010:3.

[3] DIXIT A, HAO F, MUKHERJEE S, et al. Towards an elastic distributed SDN controller[C]// Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 7-12.

[4] YAO G, BI J, LI Y, et al. On the capacitated controller placement problem in software defined networks[J]. IEEE Communication Letters, 2014, 18(8): 1339-1342.

[5] 陈飞宇,汪斌强,王文博,等.基于改进型拍卖的软件定义网络交换机迁移机制[J]. 计算机应用,2015,35(8):2118-2123.(CHEN F Y, WANG B Q, WANG W B, et al. Progressive auction based switch migration mechanism in software defined network[J]. Journal of Computer Applications, 2015,35(8):2118-2123.)

[6] 陈飞宇,汪斌强,孟飞,等.一种软件定义网络中交换机动态迁移算法[J]. 计算机应用研究,2016,33(5):1446-1449. (CHEN F Y, WANG B Q, MENG F, et al. Dynamic switches migration algorithm in software defined networks[J]. Application Research of Computers, 2016, 33(5):1446-1449.)

[7] 姚龙.软件定义网络控制器容量及部署问题研究[D].合肥:中国科学技术大学,2015:37-38.(YAO L. Research on controller capacity and placement problem in software defined network[D]. Hefei: University of Science and Technology of China, 2015:37-38.)

[8] CHEN Y L. An interactive fuzzy-norm satisfying method for multi-objective reactive power sources planning[J]. IEEE Transactions on Power Systems, 2000, 15(3):1154-1160.

[9] RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm[J]. Information Sciences, 2009, 179(13): 2232-2248.

[10] TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence[C]// Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation, and International Conference on Intelligence Agent, Web Technologies and Internet Commerce. Piscataway, NJ: IEEE, 2005:695-701.

[11] AI-QUNAIEER F S, TIZHOOSH H R, RAHNAMAYAN S. Opposition based computing — a survey[C]// Proceedings of the 2010 International Joint Conference on Neural Networks. Piscataway, NJ: IEEE, 2010:1-7.

[12] 井福荣,郭肇禄,罗会兰,等.应用精英反向学习的引力搜索算法[J].计算机应用研究,2016,32(12):3638-3641.(JING F R, GUO Z L, LUO H L, et al. Improved gravitational search algorithm with elite opposition-based learning[J]. Application Research of Computers, 2016, 32(12):3638-3641.)

YU Mingqiu, born in 1992, M. S. candidate. His research interests include computer network, information security.

ZHOU Chuangming, born in 1967, Ph. D., associate professor. His research interests include database application, intelligent information processing.

WANG Huijie, born in 1992, M. S. candidate. His research interests include navigation guidance and control.

DU Ruichao, born in 1991, M. S. candidate. His research interests include embedded system, software reliability.

Switch migration strategy based on improved gravitation search algorithm

YU Mingqiu*, ZHOU Chuangming, WANG Huijie, DU Ruichao

(CollegeofAirandMissileDefense,AirForceEngineeringUniversity,Xi’anShaanxi710051,China)

In multi-controller Software Defined Network (SDN), since the existed switch migration strategies can not adapt to the change of switch traffic which only consider single migration factor, a Switch Migration Strategy based on Improved Gravitation Search Algorithm (IGS-SMS) was proposed. In the decision-making stage, the multi-objective decision based on fuzzy satisfaction was used to optimize the objectives by the competitive priority of membership. In the calculating phase, the objective function with the top priority was optimized by improved gravitational search algorithm. The simulation results show that the IGS-SMS achieves good load balancing of controllers while ensuring the index of transmission delay and switch redistribution. When local load was heavy in the experiment, Dynamic Switches Migration Algorithm (DSMA) and Progressive Auction based Switches Migration Mechanism (PASMM) couldn’t alleviate overload. By contrast, IGS-SMS could alleviate overload, and load balancing degree was lower than DSMA and PASMM.

Software Defined Network (SDN); multi-controller; switch migration strategy; Gravitation Search Algorithm (GSA); fuzzy satisfaction

2016-10-31;

2017-01-07。

于明秋(1992—)，男，河北沧州人，硕士研究生，主要研究方向：计算机网络、信息安全； 周创明(1967—)，男，湖南益阳人，副教授，博士，主要研究方向：数据库应用、智能信息处理； 王慧杰(1992—)，男，山西太原人，硕士研究生，主要研究方向：导航制导与控制； 杜瑞超(1991—)，男，黑龙江黑河人，硕士研究生，主要研究方向：嵌入式系统、软件可靠性。

1001-9081(2017)05-1317-04

10.11772/j.issn.1001-9081.2017.05.1317

TP393.0

A