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

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

(空軍工程大學 防空反導學院，西安 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