于明秋，周創(chuàng)明，王慧杰，杜瑞超

(空軍工程大學 防空反導學院，西安 710051)

基于改進引力搜索算法的交換機遷移策略

于明秋*，周創(chuàng)明，王慧杰，杜瑞超

(空軍工程大學 防空反導學院，西安 710051)

(*通信作者電子郵箱15511743667@163.com)

針對多控制器軟件定義網(wǎng)絡(luò)(SDN)中交換機遷移策略遷移代價衡量單一，不能適應(yīng)交換機流量的變化的情況，提出基于改進引力搜索算法的交換機遷移策略(IGS-SMS)。在決策階段，應(yīng)用基于模糊滿意度的多目標決策方法，優(yōu)化目標根據(jù)隸屬度大小競爭優(yōu)先權(quán)；在計算階段，通過改進引力搜索算法優(yōu)化優(yōu)先權(quán)高的目標函數(shù)。實驗結(jié)果表明，IGS-SMS在實現(xiàn)負載均衡的同時，能保證傳輸時延與交換機重分配的指標；在實驗中，當局部負載較重時，動態(tài)遷移算法(DSMA)和基于改進型拍賣交換機遷移機制(PASMM)不能緩解控制器過載，而IGS-SMS執(zhí)行后無控制器過載，且負載均衡度小于DSMA和PASMM。

軟件定義網(wǎng)絡(luò)；多控制器；交換機遷移策略；引力搜索算法；模糊滿意度

0 引言

軟件定義網(wǎng)絡(luò)(Software Define Network, SDN)[1]的標志性特點是將控制平面和數(shù)據(jù)平面解耦，實現(xiàn)集中化的網(wǎng)絡(luò)控制。分布式控制器架構(gòu)在破解控制器性能瓶頸,在解決單點失效的同時，也帶來了負載不均的問題。由于已提出的分布式控制器構(gòu)架，如HyperFlow[2]，其控制器與交換機之間是靜態(tài)的映射關(guān)系，不能適應(yīng)交換機請求流量的變化，容易造成控制器資源的失衡。

ElastiCon[3]是第一個彈性的分布式的控制器架構(gòu)。在該架構(gòu)中，控制器與交換機維持一種動態(tài)的映射關(guān)系，過載控制器下的交換機可以遷移到負載較輕的控制器下。ElastiCon為控制器設(shè)定一個指定的負載域，負載過大或過小時，執(zhí)行交換機遷移或刪除控制器的操作。交換機遷移的方式為控制器負載均衡研究提供了新的思路，其實現(xiàn)方法簡單，控制靈活可靠，已經(jīng)成為研究的熱點; 但ElastiCon提出的遷移策略并不完善，在該體制下，交換機只能遷移到鄰近的控制器。就近遷移是一種局部的調(diào)動，當網(wǎng)絡(luò)中某個區(qū)域負載較重時，該方法就失去了它的作用。

對比就近遷移策略(Lowest Utilization Migration Algorithm, LUMA)[4]將交換機遷移至剩余資源使用率最低的控制器來實現(xiàn)負載均衡，這種方法跳出了區(qū)域的限制，在整個網(wǎng)絡(luò)中尋找空閑資源; 但交換機與控制器之間的傳輸時延是受限制的，時延過大會引起數(shù)據(jù)延遲、控制一致性等問題，這就要求交換機與控制器之間的距離必須受到限制。另外，這種距離上不加限定的遷移策略還容易產(chǎn)生交換機的跨域通信問題。

針對負載均衡與傳輸時延兩方面因素，文獻[5]提出基于改進型拍賣的交換機遷移機制(Progressive Auction based Switches Migration Mechanism, PASMM)，將交換機的遷移問題優(yōu)化成為控制器剩余資源的拍賣問題。其中，傳輸距離作為交換機對控制器估價函數(shù)的參數(shù)，以此來影響交換機的選擇；文獻[6]提出基于免疫粒子群算法的動態(tài)交換機遷移策略(Dynamic Switches Migration Algorithm, DSMA)，將最小化負載均衡度和傳輸距離的加權(quán)和作為優(yōu)化目標，通過免疫粒子群算法求解。PASMM中傳輸距離與估價函數(shù)成反比，交換機近距離優(yōu)先選擇控制器，當局部負載較重時，算法收斂速度較慢。而DSMA優(yōu)化目標是負載均衡度與傳輸距離加權(quán)和，在負載較重時，不能保證控制器不過載。

本文在負載均衡和傳輸時延的基礎(chǔ)上，進一步考慮交換機遷移過程產(chǎn)生的網(wǎng)絡(luò)代價，提出基于改進引力搜索算法的交換遷移策略(Switch Migration Strategy based on Improved Gravitation Search, IGS-SMS)。在該遷移策略中，用模糊滿意度為三種優(yōu)化目標設(shè)定權(quán)重，根據(jù)權(quán)重大小選擇優(yōu)先優(yōu)化的目標，通過改進引力搜索算法快速求解。

1 問題建模

在本文的網(wǎng)絡(luò)實例中，采用帶內(nèi)模式的co-located部署方案，也就是控制器與交換機節(jié)點部署在同一位置，且控制信息與數(shù)據(jù)信息采用相同的信道[7]。網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖1所示。在圖1網(wǎng)絡(luò)中有30個節(jié)點，每個節(jié)點位置有一臺交換機。5個控制器分別部署在節(jié)點4、11、14、23、26處。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig. 1 Network topological structure

設(shè)在SDN中有M個控制器C={c1,c2,…,cM}，控制器的容量CA={a1,a2,…,aM}。交換機的數(shù)量為N，表示為S={s1,s2,…,sN}。交換機分布矩陣X=(xij)M×N，式中：

控制器資源使用率閾值為TH={th1,th2,…,thM}，當控制器資源使用率超過閾值時，控制器過載，觸發(fā)交換機遷移機制。

定義1 目標負載，定義為各控制器資源使用率中的最大值。

定義2 平均傳輸時延，用交換機到控制器的平均最小傳輸跳數(shù)衡量。

為直觀說明，以交換機到控制器的最小傳輸跳數(shù)衡量傳輸時延。其中l(wèi)(ci,sj)為交換機sj到控制器ci的最小跳數(shù)。f2越小則說明平均傳輸時延越小。

定義3 交換機遷移數(shù)，用于衡量交換機遷移過程的代價，表示為f3，指某時刻交換機分布矩陣的列與原交換機分布矩陣對應(yīng)列不相同的數(shù)量。

優(yōu)化模型為：

minf1,f2,f3

(1)

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

(2)

(3)

式(1)是模型的目標函數(shù)，f1,f2,f3均為越小越優(yōu)型目標，屬于多目標優(yōu)化問題；式(2)和式(3)是約束條件，保證每個交換機只隸屬于一個控制器。

2 基于模糊滿意度的多目標決策

模型中f1、f2、f3沒有統(tǒng)一的量綱，且三者之間存在制約，因此應(yīng)用基于模糊滿意度的多目標決策方法[8]。首先根據(jù)隸屬度函數(shù)求f1、f2、f3的隸屬度，進行歸一化處理。優(yōu)化目標是使交換機遷移過程中產(chǎn)生的網(wǎng)絡(luò)代價整體最小，因此隸屬度函數(shù)選擇遞增型函數(shù)，隸屬度越大，說明產(chǎn)生的網(wǎng)絡(luò)代價越大。為描述f1、f2、f3之間的制約關(guān)系，把各目標函數(shù)隸屬度的最大值最小化作為優(yōu)化準則，從而將該多目標問題轉(zhuǎn)化為單目標問題。設(shè)f1、f2、f3的隸屬度值為u1、u2、u3，目標函數(shù)轉(zhuǎn)換為：

(4)

式(4)表明，函數(shù)隸屬度越大，越能獲得優(yōu)化的優(yōu)先權(quán)，即算法的每次迭代過程都為減小最大的網(wǎng)絡(luò)代價。

f2、f3的隸屬度函數(shù)可用圖2表示的遞增連續(xù)函數(shù)表示。

圖2 f2、 f3隸屬度函數(shù)Fig. 2 f2、 f3membership function

其數(shù)學表達式為：

定義閾值v、f1的隸屬度函數(shù)如圖3所示。

其數(shù)學表達式：

隸屬度函數(shù)分為3部分，分別對應(yīng)控制器負載的3種狀況。當有控制器過載時，u1=1，目標負載的優(yōu)化有絕對的優(yōu)先權(quán)，即最低指標要保證無控制器過載；當無控制器過載且目標函數(shù)超過閾值時，f1的隸屬度函數(shù)變?yōu)閱握{(diào)遞增，與f2、f3競爭優(yōu)化的優(yōu)先權(quán)；當目標負載低于閾值時，u1=0，目標負載不再參與競爭，可以認為f1=v是負載均衡的最高指標。

圖3 f1隸屬度函數(shù)Fig. 3 f1membership function

3 模型求解

3.1 引力搜索算法

(5)

其中：Maj(t)和Mpi(t)分別為粒子Xj和粒子Xi的慣性質(zhì)量；ε是一個很小的常量，防止分母為零；Rij(t)是粒子Xj和粒子Xi的歐氏距離；G(t)是在t時刻的引力常數(shù)：

(6)

其中：G0取值為100，α等于20，T是系統(tǒng)迭代次數(shù)。在GSA中，為了增強隨機特性，設(shè)randj是范圍在[0,1]內(nèi)的隨機數(shù)，則粒子Xi在第d維受到的合力為：

(7)

其中Mi(t)是粒子Xi的慣性質(zhì)量。對于每一次的迭代過程，粒子根據(jù)以下公式更新它的速度和位置：

(8)

其中randi是[0,1]內(nèi)的隨機數(shù)。慣性質(zhì)量根據(jù)適應(yīng)度值的大小計算，在GSA中，使用式(9)更新粒子的慣性質(zhì)量：

(9)

其中fiti(t)為t時刻粒子Xi的適應(yīng)度。對于求最小值問題，best(t)和worst(t)定義如下：

3.2 群體反向?qū)W習機制

引力搜索算法中初始狀態(tài)隨機生成，這導致了算法的尋優(yōu)效率不夠穩(wěn)定。本文引入群體反向?qū)W習機制[10-11]，優(yōu)化粒子的初始分布，提高算法效率。

3.3 算法過程

算法步驟：

1)隨機初始化映射關(guān)系矩陣并應(yīng)用反向?qū)W習原理進行優(yōu)化，將粒子的速度置零，設(shè)定循環(huán)次數(shù)Iteration；

2)計算粒子適應(yīng)度，選出最小的適應(yīng)度值Fbest和對應(yīng)的映射關(guān)系粒子Lbest；

3)更新引力系數(shù)G(t)、best(t)、worst(t)和粒子慣性質(zhì)量Mi(t)；

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

5)在約束條件下，對映射關(guān)系矩陣標準化，用Lbest代替負載均衡度較差的粒子；

6)返回2)，直到達到設(shè)定的迭代次數(shù)；

7)算法結(jié)束，完成一次求解，記錄結(jié)果；

8)重復執(zhí)行算法h次，從中選取使負載均衡度最優(yōu)的映射關(guān)系粒子作為最終的結(jié)果。

4 實驗仿真

實驗中，采用圖1的拓撲結(jié)構(gòu)，初始映射關(guān)系粒子為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)，將交換機就近分配給控制器。假設(shè)各控制器的容量相等，值設(shè)為1；資源利用率閾值按編號順序依次為0.9,0.85,0.85,0.9,0.95；交換機瞬時流量隨機生成。實驗以Matlab R2012a為平臺，分兩個部分進行。

實驗一 驗證IGS-SMS的性能，研究v在遷移策略中起到的作用。實驗中，控制器平均資源占用率為68.18%。比較v取不同值時，負載均衡度、平均傳輸時延與交換機遷移數(shù)的變化，如圖4～6。

圖4中，v取值在0.6～0.9時，負載均衡度無明顯變化，因為目標負載與網(wǎng)絡(luò)中總負載量和負載分布有關(guān)，在控制器平均資源使用率達68.87%時，目標負載容易超過閾值，獲得優(yōu)先權(quán)；當v=1時，負載均衡度迅速增大，這是因為v=1表示只要無控制器過載，目標負載就不會成為優(yōu)化的目標，此時負載均衡度得不到較好的保證。圖5、圖6中，隨著v的取值增大，平均傳輸時延與交換機遷移數(shù)整體有下降趨勢。因為增大v的取值，目標負載超過閾值的幾率降低，優(yōu)先權(quán)集中于平均傳輸時延與交換機遷移數(shù)?？梢缘贸鼋Y(jié)論：v取值在控制器平均資源使用率到1之間，具體數(shù)值應(yīng)根據(jù)交換機請求流量和網(wǎng)絡(luò)性能需求設(shè)定。

圖4 v對負載均衡度的影響Fig. 4 Influence of v on load balancing degree

圖5 v對平均傳輸時延的影響Fig. 5 Influence of v on average transmission delay

圖6 v對交換機遷移數(shù)的影響Fig. 6 Influence of v on the number of switch migration

從實驗一可以看出：v可以有效描述負載均衡、傳輸時延以及交換機遷移重分配3種代價之間的制約關(guān)系；v并不直接決定目標負載權(quán)重的相對大小，v值決定的是目標負載在什么樣范圍內(nèi)更有競爭力。當目標負載大于v時，競爭力強，可以防止出現(xiàn)單個控制器負載較重的情況；當目標負載小于v時，將優(yōu)先權(quán)轉(zhuǎn)讓，兼顧傳輸時延與交換機重分配的指標。

實驗二 比較IGS-SMS、PASMM與DSMA的負載均衡效果。首先采用實驗一中交換機請求流量分布，為保證較好的負載均衡效果，IGS-SMS算法中閾值v設(shè)為0.7。實驗結(jié)果如圖7。

圖7 負載均衡比較(一)Fig. 7 Comparison of load balancing (No.1)

計算交換機遷移執(zhí)行后的負載均衡度：ρ(InitialState)=0.066 2，ρ(PASMM)=0.028 8，ρ(DSMA)=0.044 2，ρ(IGS-SMS)=0.010 4；在該實例中，初始狀態(tài)，控制器3過載。交換機遷移策略執(zhí)行后，3種算法均能緩解過載狀況。其中， IGS-SMS最優(yōu)，PASMM和DSMA較差。

然后增大交換機請求流量，再次進行實驗，結(jié)果如圖8。

圖8 負載均衡比較(二)Fig. 8 Comparison of load balancing (No.2)

此時，控制器平均資源使用率為81.66%，負載集中于控制器2和控制器3。初始狀態(tài)下，控制器2和控制器3過載。IGS-SMS執(zhí)行后無控制器過載，而采用PASMM和DSMA沒有緩解控制器過載。計算負載均衡度：ρ(InitialState)=0.177 7，ρ(PASMM)=0.315 8，ρ(DSMA)=0.044 6，ρ(IGS-SMS)=0.002 7?？梢钥闯鯥GS-SMS的負載均衡度最優(yōu)，DSMA較差， PASMM執(zhí)行后的負載均衡度相對于初始狀態(tài)反而有所增大。對于DSMA算法，固定的權(quán)值無法反映不同網(wǎng)絡(luò)的需求，實驗采用文獻[6]中設(shè)定的1∶1的權(quán)值，在網(wǎng)絡(luò)局部負載較重時不能突出負載均衡的主要地位。在PASMM中，交換機對控制器的選擇受距離影響較大，當網(wǎng)絡(luò)局部負載較重時，算法收斂速度慢，實驗中算法迭代10 000次仍然得不到合格的結(jié)果，這就陷入了與就近遷移策略相同的困境。

5 結(jié)語

本文提出了一種基于改進引力搜索算法的交換機遷移策略。采用基于模糊滿意度的多目標決策方法，權(quán)衡負載均衡、傳輸時延和交換機重分配3個方面的代價，應(yīng)用改進引力搜索算法進行求解。實驗結(jié)果表明，提出的交換機遷移策略可以有效緩解控制器過載，實現(xiàn)較好的負載均衡效果。另外，閾值v可以根據(jù)負載狀況及網(wǎng)絡(luò)需求自適應(yīng)選取，避免了人工操作的復雜性；而改進的引力搜索算法降低了算法隨機性的影響，提高了求解的可靠性。但本文沒有涉及交換機請求流量過大或過小，需要添加或減少控制器的情況，需要在以后的工作中進一步研究。

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] 陳飛宇,汪斌強,王文博,等.基于改進型拍賣的軟件定義網(wǎng)絡(luò)交換機遷移機制[J]. 計算機應(yīng)用,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] 陳飛宇,汪斌強,孟飛,等.一種軟件定義網(wǎng)絡(luò)中交換機動態(tài)遷移算法[J]. 計算機應(yīng)用研究,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] 姚龍.軟件定義網(wǎng)絡(luò)控制器容量及部署問題研究[D].合肥:中國科學技術(shù)大學,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] 井福榮,郭肇祿,羅會蘭,等.應(yīng)用精英反向?qū)W習的引力搜索算法[J].計算機應(yīng)用研究,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—)，男，河北滄州人，碩士研究生，主要研究方向：計算機網(wǎng)絡(luò)、信息安全； 周創(chuàng)明(1967—)，男，湖南益陽人，副教授，博士，主要研究方向：數(shù)據(jù)庫應(yīng)用、智能信息處理； 王慧杰(1992—)，男，山西太原人，碩士研究生，主要研究方向：導航制導與控制； 杜瑞超(1991—)，男，黑龍江黑河人，碩士研究生，主要研究方向：嵌入式系統(tǒng)、軟件可靠性。

1001-9081(2017)05-1317-04

10.11772/j.issn.1001-9081.2017.05.1317

TP393.0

A