基于改進遺傳算法的SDN多控制器負載均衡機制研究

收稿日期：2022-02-18；修回日期：2022-04-02" 基金項目：國家自然科學基金資助項目（61802281，61702366，61972456）；天津市自然科學基金資助項目（19JCYBJC15800）；專用集成電路與系統國家重點實驗室（復旦大學）開放課題（2021KF014）

作者簡介：徐愛鑫（1997-），女，河北唐山人，碩士研究生，主要研究方向為軟件定義網絡、負載均衡；孫士民（1983-），男（通信作者），山東臨沂人，副教授，博士，主要研究方向為軟件定義網絡、網絡空間安全、QoS優化算法（sunshimin@tiangong.edu.cn）；汪曉凡（1996-），女，河北邯鄲人，碩士研究生，主要研究方向為區塊鏈、共識算法；徐國威（1998-），男，江蘇宿遷人，碩士研究生，主要研究方向為區塊鏈技術、低延時網絡；王美玉（1998-），女，山西呂梁人，碩士研究生，主要研究方向為區塊鏈技術、低延時網絡.

摘 要：

為解決軟件定義網絡中多控制器負載失衡問題，提出了一種基于非合作博弈降載的主控制器重選模型。首先，利用動態閾值來判別過載控制器；其次，采用基于優先權的遷移交換機決策機制；最后，構建以控制器集群的負載均衡度、平均總時延和交換機遷移成本作為效用函數的優化模型，采用改進的遺傳算法求解，加入相似算子提高尋求全局最優解的速度及準確度。實驗結果表明，該機制有效地均衡了控制平面的負載并優化了網絡性能。

關鍵詞：軟件定義網絡； 非合作博弈； 負載均衡； 交換機遷移； 遺傳算法； 算子

中圖分類號：TP393"" 文獻標志碼：A"" 文章編號：1001-3695（2022）09-017-2671-06

doi： 10.19734/j.issn.1001-3695.2022.02.0070

SDN multi-controller load balancing mechanism based on improved genetic algorithm

Xu Aixin1，2， Sun Shimin1，2， Wang Xiaofan1，2， Xu Guowei1，2， Wang Meiyu1，2

（1.School of Software，Tiangong University， Tianjin 300387， China; 2.Tianjin Key Laboratory of Autonomous Intelligent Technology amp; System， Tianjin 300387， China）

Abstract：This paper proposed the non-cooperative game theory-based of load-reduction master controller reselection model in software defined networking to address the multi-controller load imbalance problem，called GTMCR. Firstly，it utilized the overload dynamic thresholds approach （ODT） to discriminate the overload controller. Next，the migration of switches followed a priority decision switching strategy （PDSS）. Finally，the constructed optimization model took the load balancing degree of controller clusters，average total delay and switch migration cost as utility functions. To prevent the global optimal solution from slipping into the local optimum，the solution value of optimal deployment used the genetic algorithm for improved multi-objective optimization （GAIMO） with the addition of a similarity operator to boost the algorithm’s convergence speed and the accuracy of the global optimal solution. The experimental results show that this mechanism effectively balances the control plane load while achieving the goal of optimizing network performance.

Key words：software defined networking （SDN）; non-cooperative game; load balancing; switch migration; genetic algorithm; operator

0 引言

軟件定義網絡［1］是一種新型的互聯網體系架構，不僅實現了控制層與數據層的分離，還通過控制器的集中控制來實現對網絡靈活便捷的配置和管理。但是，由于網絡規模和流量規模的動態變化，控制器可能會發生負載失衡，從而導致網絡無法正常運行，過載控制器還可能因此遭受惡意流量的網絡攻擊，影響網絡的正常通信，這給穩定高效的網絡服務帶來了新的挑戰。所以，研究多控制器間的負載均衡具有重要意義。

目前，多控制器部署大多通過靜態部署方式來完成［2，3］。在實際通信環境中，網絡流量是動態變化的。因此，設計動態的控制器與交換機映射機制，以縮短控制器響應時間并更好地利用控制器資源，對提高SDN控制平面的可擴展性和可靠性具有重要作用。劉毅等人［4］針對SDN動態流量變化所引起的控制器負載不均衡問題，提出了一種僅以最小遷移代價為目標的階段式動態負載均衡策略，未考慮其他優化目標。Huang等人［5］提出了基于聚類的遺傳算法與合作集群（CGA-CC）來解決動態控制器部署問題，采用針對所有控制器上的請求分配概率的調度算法來平衡調度性能和可擴展性之間的權衡，沒有在指標權重分配上進行細致描述，其算法實現的負載均衡程度有限。Adekoya等人［6］采用動態映射交換機遷移決策算法（improved switch migration decision algorithm，ISMDA），通過遷移模型來對遷移交換機的流量容量限制選擇最優的控制器部署方案，但需要進一步實驗來驗證算法的可行性和有效性。

綜合考慮目前的控制器部署方案［7］是通過實施多控制器之間的交換機遷移從而實現負載均衡的目標。面臨的主要問題為：從控制器的角度來看，如何判定過載狀態以及遷移哪臺交換機實現主從控制器重映射達到控制平面的負載均衡；從交換機的角度來看，考慮映射到哪臺目標控制器來實現負載均衡以及如何設計動態的控制器和交換機的映射目標。

1 相關工作

近年來，對于多控制器中判定過載控制器的研究，Lan等人［8］提出一種預先定義負載權重的動態自適應的負載均衡策略，設定控制器的權重系數，大幅度減小了通信的流開銷，但在控制器響應時間方面表現不佳。Mokhtar等人［9］提出了多閾值負載均衡切換遷移方案，引入傳輸負載信息的指示器，通過漸進動態調整閾值來實現控制器之間的持續負載均衡，指示器會增加負載均衡的計算成本且實時性較差。

待遷移交換機的選擇大多采用隨機原則，傳統的方式未考慮遷入域的負載容易導致二次過載。因此，Xiao等人［10］提出了一種用于SDN控制平面的交換機遷移決策方案（DMSSM），提出了遷移效益模型來解決遷移決策問題，形成遷出域交換機集合，通過負載均衡率和傳輸時延衡量遷出的交換機，但是未考慮到遷移時的總時延。Sahoo等人［11］設計了最小化控制器間負載差異為目標的負載均衡算法來選取待遷移交換機，但是未考慮到控制器的負載容量，負載容量小的控制器在遷移后導致過載，因此可能會觸發錯誤的交換機遷移。Zhong等人［12］提出了一種基于預測的SDN負載均衡雙重交換機遷移方案，該方案將過去的流量負載作為歷史數據來預測未來的流量負載，并減少了交換機遷移的頻率，但預測流量需要一定的時間進行預測處理，無疑增加了計算成本。

對于待遷移交換機部署目標控制器的問題，Yuan等人［13］提出了一種基于控制器分配方案的遺傳算法（GAPA）來解決控制器的配置問題，該方法在降低SDN交換機與控制器之間的平均傳播時延方面具有良好的性能，并能實現控制器之間更好的平衡，針對平均傳播延遲尋找最優值從而獲得分配結果，但其交叉和變異的遺傳算子采用的是傳統固定值的方式，從而使得錯失最優部署方案，在尋優方面的效果不佳。Mohanty等人［14］提出了一種有效的基于遺傳算法的控制器布局求解方法（proposed GA），使傳播延遲和優化成本最小化，以找到成本最小的控制器的最優位置，但算法的收斂速度慢，從而導致部署時間太長以及映射策略并不高效。Ibrahim等人［15］提出了遺傳算法（GA）來確定控制器部署的最佳位置和數量，以最小化時延為優化目標，最大限度地減少迭代次數，并確保控制器之間的負載平衡，但算法中的選擇算子使得出的策略并不是十分合理。

針對多目標優化選取目標控制器考慮負載均衡方案對網絡性能帶來的影響，Schütz等人［16］提出了控制器部署的全面數學形式化，根據傳播延遲和控制器的能力確定了交換機與控制器的映射分配關系，同時保持控制器之間的平衡負載分布，但是其只針對平均傳播延遲尋找最優值從而獲得分配結果，發送以及處理時延還未考慮進去。Ibrahim等人［17］提出了一種貪婪隨機搜索（GRS）算法用來解決節點與控制器的動態分配問題，通過控制器的位置、數量的分配達到最大的資源利用率以實現負載平衡，使用這樣的策略要求控制器的位置正確，以提高網絡的可靠性和成本效益，但除了資源利用率外未考慮到其他因素。Zhong等人［18］提出了評估預測的收益（APOP）方案，這是一種基于過載狀態預測和收益評估的多控制器控制平面的負載均衡策略，但它只考慮了負載均衡程度，沒有考慮優化通信延遲等其他網絡性能因素。

就目前的文獻調查情況，為盡可能地減少計算成本和響應延遲，本文對過載控制器選取遵循動態閾值方法。選擇待遷移交換機綜合考慮了流量變化、負載容量和遷移距離，采用基于優先權的方式進行選取。對目標控制器的選取采用改進的遺傳算法，通過引入相似算子加快收斂速度的同時，調整選擇、交叉和變異算子確保達到最佳部署策略。結合待遷移交換機與主控制器的重新選取，考慮遷移前后對網絡性能的影響，設計的優化目標綜合考慮以下指標：控制器上的負載是均勻的，盡可能提升控制器的資源利用率，減少控制平面與數據平面通信的總時延，并盡可能降低交換機遷移的成本。通過以上的交換機遷移方式進行控制平面負載的分配，進而為多控制器負載均衡策略的研究提供解決方案和建模思路。

2 分析與建模

2.1 SDN分布式網絡模型

網絡模型G=（V，E），節點和鏈路的集合分別為V、E。網絡中的n臺控制器和m臺交換機分別表示為C={C1，C2，…，Cn}和S={S1，S2，…，Sm}。以映射矩陣式（1）來表示網絡節點之間的鏈路情況。按照控制器的管控范圍劃分成若干子域，其子域包括控制器及其管控的交換機。在多控制器架構下，依據交換機訪問權限不同，OpenFlow 1.3協議定義了三種不同角色功能的控制器，分別是等價控制器、主控制器和從控制器。其中，主控制器和等效控制器負責管理和控制交換機，但是從控制器只能讀取交換機狀態而不能對交換機進行管理。

C1 C2 … Cn

S1S2Sm

a11 a12 … a1n

a21 a22 … a2n

" am1 am2 … amn（1）

其中：aij=1控制器Cj是交換機Si的主控制器

0控制器Cj是交換機Si的從控制器或等價控制器

2.2 基于非合作博弈的純策略納什均衡模型

非合作博弈是在利益相互影響的局勢中如何決策使自己的收益最大，即策略選擇問題。對于如何決策目標控制器的部署策略使效用函數值最大的問題，本文對SDN構建非合作博弈模型。博弈模型可用三元組表示為Game={Q，P，U}，博弈的三要素如下：

a）參與者Q。除過載控制器之外，未過載的從控制器作為參與者。式（2）中Cr表示過載控制器集合。

Q={Ct，t∈（1，2，…，r－1，r+1，…，n）}（2）

b）策略集合P。純策略是指選擇某個策略的概率為0或1，即參與者只使用策略集合中的一條策略。過載控制器Cr將控制子域下的交換機Si（i∈（1，m））遷移至目標控制器Ck。博弈將在控制器集合Q之間進行，在選定博弈對手Ct后，每個參與者具有兩個純策略，可用式（3）表示。

Pk={Ck accept Sj，Ck reject Sj}（3）

c）效用函數U。所有參與者在某一組特定策略組合下的效用。它包含集成控制器的負載均衡度、交換機與控制器之間的總時延和交換機的遷移成本。

定義1 基于控制器負載均衡度的效用函數。在與控制器通信的交互報文中，來自于各交換機的數據報文占主導，如Packet_In報文。因此，本文采用控制器處理的Packet_In報文數量來計算控制器負載。Rj為控制器Cj單位時間內最大Packet_In數據報文處理量，ri為交換機Si單位時間內產生的Packet_In數據報文的數量，M為待遷移交換機的個數，則可用式（4）來計算控制器的負載。

Lcj=∑Mi=1ri×aijRj（4）

控制器的平均負載程度可用式（5）來表示。

Lc=∑nj=1Lcin（5）

為反映SDN控制平面的負載均衡分布情況，采用控制器集群負載均衡度u1來衡量，通過標準差得到控制器間的負載差異度，如式（6）所示。

u1=∑nj=∞（Lc1－Lc）2n（6）

定義2 基于交換機與控制器之間平均時延的效用函數。交換機與控制器之間的時延決定了決策下發的實時性，關系到網絡的整體性能。數據報文在交換機與控制器之間的時延主要包括傳播時延和網絡擁塞時的排隊時延。采用交換機到控制器的平均總時延來作為衡量標準，如式（7）所示。

u2=∑mj=1 ∑nj=1 Tm×ai m（7）

其中：Tij為交換機Si到控制器Cj的總時延。

定義3 基于交換機遷移平均成本的效用函數。在交換機遷移過程中，實現交換機的控制權轉移要經過復雜的角色轉換過程。當確定了待遷移的交換機時，控制器在域內將Flow_Mod等規則安裝到遷移交換機，開銷PI如式（8）所示。

Pj=∑mi=1 ∑nj=1aj·Ij·τ（8）

其中：τ表示流表安裝數據包（包括Flow_Mod消息數據包等）的平均大小；lij為交換機Si到目標控制器Cj的最短可達節點間鏈路長度。

交換機遷移的通信成本來自于部署流策略產生的代價，它主要受通信需要遷移的消息數目及大小所影響，包括遷移交換機與遷入、遷出控制器之間的通信成本PC，如式（9）所示。

PC=∑mi=1 ∑nj=1［（a0ij·lj）+（aij·lj）］·ε（9）

其中：ε表示交換機平均通信消息數據包大小（包括Packet_In數據包等）；a0ij和aij分別表示遷移前后待遷移交換機Si與目標控制器Cj之間的映射關系。

當遷移交換機向目標控制器發送流請求時生成遷移請求成本PM，如式（10）所示。

PM=∑mi－1 ∑nj=1ai·li·ζ（10）

其中：ζ為交換機Si進行遷移請求消息數據包（包括Role-Request消息數據包等）的平均大小。

交換機遷移數可表示為

λ=12∑ni=1 ∑ni=1（aaa－a4）2（11）

本文綜合考慮了遷移規則流表安裝成本PI、通信成本PC和遷移請求成本PM。式（12）表示平均遷移成本u3。

u3=（PS+PC+PM）/λ（12）

若將上述u1、u2、u3作為目標函數，則可以將尋找最優控制器—交換機映射矩陣關系問題轉換成多目標優化模型。優化模型式（13）是尋找最優解使得ui值最小，即控制器間負載差異、交換機與控制器的總時延和交換機的遷移成本均最小化。

min（ui）" i=1，2，3（13）

s.t." aij∈{0，1}" i，j，i=1，2，…，m; j=1，2，…，n

∑nj=1aij=1" i，i=1，2，3，…，n

∑mi=1riaij≤Rj" j，j=1，2，3，…，m

在該模型中，為了減少集群中交換機頻繁交換的額外開支，只要當前控制器還沒有出現過載的情況，就不會進行重映射操作。每臺控制器在不超負載的情況下盡可能處理更多的數據包，因為這對于控制器來說，在增大了自身的吞吐量的同時，也減少其余控制器負載的增加，符合納什均衡博弈中每個參與者的策略是對其他參與人策略的最優反應的原則。所以，該博弈存在純策略納什均衡。

對此，本文采用Pi表示參與者的某一特定的策略，P-i代表除參與者以外其余參與者策略的組合，具體表示為P－i=（P1，…，Pi－1，Pi+1，…，Pn）。因此，P=（Pi，P－i）表示所有參與者某一特定的策略組合。當博弈趨于穩定時，達到的納什均衡狀態用P*i表示。對于n個參與者的博弈，在其余參與者策略都不變的條件下，對任意一個參與者i，其策略都是對其余參與者策略組合的最優策略，可以表示為P*i∈argminPi∈Pui（Pi，P*－i），即效用函數值均有不等式ui（P*i，P*－i）≤ui（Pi，P*－i）成立。

3 控制器負載均衡模型

針對負載失衡的控制平面，本章首先通過判定過載控制器ODT方法，進而利用PDSS策略選擇過載控制器管控下的交換機進行遷移，遷移至GAIMO算法部署目標控制器下，最終通過一個基于非合作博弈降載的主控制器重選模型（game theory-based of load-reduction master controller reselection，GTMCR）對控制器集群中過載控制器進行降載處理，從而使控制平面負載均衡。其算法思想如圖1所示。

3.1 過載控制器判定策略ODT

對于過載控制器的判定，本文設計了過載控制器的動態閾值判定機制（overload dynamic thresholds，ODT），閾值LT根據整體控制平面的負載狀況動態調整，定義如式（14）所示。

LT=ε"""" Lci≤ε

1n∑ni=1LciLcigt;ε（14）

其中：ε為判定過載門限值；LCi為控制器Cj的負載情況；Mi為0表示非過載狀態，反之處于過載狀態，觸發GTMCR進行負載均衡。控制器狀態標志位字段為

Mi=0" Lcj≤LTi1" Lcjgt;LTi（15）

3.2 遷移交換機選擇策略PDSS

為了盡快地使控制器降載，本文提出了一種基于優先權的交換機選擇策略（priority decision switching strategy，PDSS）。若在交換機變更主從控制器關系后有新的大量請求來，則要產生新的流表項向新的目的控制器發送更多的Packet_In請求，從而增加業務處理的負擔，所以流量變化小的擁有更高的優先遷移權。此外，負載大的交換機進行一次遷移就可完成負載下降，以防遷移的數量過大而增大遷移成本。另外，為了減少待遷移交換機與過載控制器之間的通信成本，距離目標控制器越近被遷移的優先權也越高。因此，優先遷移流量變化小、負載占比較高且與目標控制器之間距離較近的交換機。

式（16）表示Si在Cj上所占用的控制資源χij。

χij=λ（Si）Bij（Si）（16）

其中：Si加入Cj的事件數用λ（Si）表示；Bij（Si）代表Si的主控制器Cj的總事件數。

因此，式（17）定義Si遷移到Cr的優先權為Prir。它們之間的跳轉數目用dir表示，Si的流變化速率為Vi。

Prir=χirdirVi∑sk∈scrχkrdkrVk（17）

選取的遷移交換機Si為

Si=max{Prsj，Sj∈S}（18）

3.3 基于改進遺傳算法的控制器決策機制

遺傳算法（genetic algorithm，GA）［19］是一種啟發式的搜索算法，通常用來解決優化問題。它依靠概率性優化搜索，能夠自適應地修正和指導優化的搜索空間。本節提出面向改進多目標優化的遺傳算法GAIMO （genetic algorithm for improved multi-objective optimization），利用遺傳算法對網絡負載均衡問題進行全局搜索，然后在全局最優附近區域進一步局部尋優，最終找到網絡負載均衡最優解。

3.3.1 GAIMO算法

GAIMO算法在基礎的遺傳算法上加入了相似算子的概念，并采用兩種方式相結合的選擇算子以及自調節的交叉和變異概率。算法的過程包括個體編碼、種群初始化、個體評價、選擇、相似度判斷、交叉、變異操作以及種群迭代更替，具體設定如下：

整個網絡里的交換機和控制器用m×n維矩陣表示。采用隨機序列初始化使產生的個體具有一定的差異度，保證均勻性的同時提高種群的多樣性。個體適應度函數用于區分群體中個體好壞，適應度值越大表示控制器的性能越能得到充分的發揮。針對多目標優化問題采用離差標準化方法（min-max normalization），通過轉換函數對原始數據進行線性變換。適應度函數如式（19）所示。

fi（x）=uimax－uiuimax－uimin" uimin≤ui≤uimax，i=1，2，3（19）

其中：uimax和uimin為個體的最大值和最小值。對于多目標優化適應度函數式（20），采用的權重因子為w1 、w2 、w3。

F（x）=w1×f1（x）+w2×f2（x）+w3×f3（x）（20）

s.t. w1+w2+w3=1

選擇算子是為了在種群中選擇創造下一代的個體。本文的選擇算子采用5%精英策略，先選出最佳個體遺傳到下一代，為了保證親本的多樣性，再結合輪盤賭方法。式（21）表示個體xi被選擇的概率。

P（xi）=f（xi）∑Ni=1f（xi）（21）

由于近親交叉繁殖會增加不必要的迭代計算［20］，在傳統的遺傳算法基礎之上引入了相似算子，用海明距離GHij衡量兩個即將進行交叉個體的相似程度，海明距離是指相同長度的以a為基的兩個字串 i 和 j 中對應位不相同的數量。因此，先對交叉個體進行相似度評定，低于相似度閾值時，再給予交叉機會。這樣可以盡可能地減少迭代次數，實現保證解的準確度的同時從而加快收斂速度。

交叉為了讓后代能夠繼承上一代的優良基因，在固定概率P＇c的基礎上設定與進化代數相關的交叉概率，通過交叉概率來加快種群的收斂以便加速尋找優良種群所處的區域。由于Pc的取值過大容易使適應問題環境值高的基因串很快被破壞掉，所以Pc值隨遺傳代數的增加而逐漸遞減，這樣同時也解決了取值過小而使搜索速度緩慢的問題。增加交叉點會降低性能。因此，為保持多樣性，本文采用兩點交叉算子：

Pc=P′c×（1－iGen）" i≥Gen

P′cilt;Gen（22）

其中：Gen為最大迭代次數，當前迭代次數為i。

為保持種群遺傳多樣性，避免落入局部極大值陷阱，采用擇位變異和自適應變異概率Pm（式（23））。這種方法的優勢在于增加劣勢個體變異概率的同時，減小優秀個體的變異概率。因此，減小原有變異概率P′m，在優良種群周圍進行小步距大概率變異。這樣既避免了算法陷入局部極小又極大地降低再次產生無用的劣質解發生的概率，加快收斂速度。隨著進化過程的推進，概率逐漸減小趨于穩定。這避免了對算法后期的穩定性造成沖擊而導致算法收斂時間變長，提高了計算的效率。

Pm=P′m×1－fmax－f′fmax－farg" f≥fag

P′mflt;fag（23）

其中：f′、fmax和favg分別為當前、最大和平均適應度值。

經過不斷地種群更替，最終算法收斂到全局最優解。算法的程序流程如圖2所示。

本文提出的GAIMO算法是基于遺傳算法對交換機與控制器的映射關系進行尋優。首先確定算法執行所需要的輸入參數，然后對種群進行二進制編碼設計，對每一個個體進行初始化，并對初始種群中的每一個個體計算適應度函數值（第1、2行）。接下來開始進行遺傳算法的算子操作（第3～19行），先進行選擇算子操作，采用精英策略與輪盤賭選擇相結合的方式（第5～10行）。本文提出加入相似算子進行相似度條件判斷，若相似度低于相似度閾值，則進行自適應兩點交叉操作（第11～14行）。接下來進行自適應變異概率的遺傳操作（第15、16行）。形成新的種群（第17行）之后，對上述算子不斷地迭代進行種群更替，最后得到的最優個體就是對遍歷到待遷移交換機Si重選的主控制器（第18行）。

算法1 GAIMO算法

輸入：網絡參數，最大迭代次數Gen，種群大小N，交叉概率crossover_p和變異概率mutate_p。

輸出：負載均衡度、交換機與控制器之間的平均時延和交換機的遷移成本開銷；最優個體的適應度函數值；最優個體的交換機與控制器的映射矩陣。

1 pop=initialpop（N，chromlength，len，m）; //初始化種群

2 Functionvalue=objectiveFunction（Population）; /*適應度函數值計算*/

3 for i=1：Gen

4" fitvalue=cal_objective（pop，r，R，popsize，len，m）;

5" Newpop=selection（pop，fitvalue）; //選擇算子

6" if ilt;=0.05*N

7"" Elitist（Xi）=Max（pop）; //精英策略

8" else

9"" P（Xi）=f（Xi）/sum（f）; //比例選擇策略

10 end if

11 if GHijlt;0.8 //相似度判斷

12"" Pc=adapt_cross（crossover_p）; //自適應交叉概率

13"" newpop=crossover（newpop，Pc，len，m）; //交叉

14 end if

15 Pm=adapt_mutate（mutate_p）; //自適應變異概率

16 newpop=mutation（newpop，Pm，len，m）; //變異

17 pop=newpop; //種群更替產生新種群

18 ［bestindividual，bestfit］=best（pop，fitvalue）; //擇優

19 end for

3.4 基于非合作博弈降載的主控制器重選模型GTMCR

在GTMCR算法的執行過程中，首先遍歷所有控制器，對各個控制器的負載進行監測，通過動態負載閾值判定過載控制器，決策出需要遷移交換機的控制器集合，進而建立目標控制器的博弈域（第1～8行）。然后依據交換機的遷移優先權，選擇過載控制器管控下優先權最大的交換機進行遷移（第12～14行）。接下來重選待遷移交換機的主控制器，在控制器間的非合作博弈中，尋求目標控制器的純策略納什均衡狀態，通過上述的GAIMO算法得到所要遷移到的目標控制器，將遷移交換機的主從控制器進行角色轉換，實現過載控制器降載（第15～18行）。最終達到新的負載均衡，得到遷移后控制平面的負載均衡度（第21行）。最終根據遷移情況，構建新的SDN網絡拓撲。

算法2 GTMCR算法

輸入：網絡狀況參數，如交換機數量m與控制器數量n、控制器Cj的處理速率Rj、交換機Si的請求速率ri、控制器與交換機之間的時延T和距離D等相關參數。

輸出：網絡中過載控制器，控制器集群的負載均衡度，網絡中需要遷移的交換機。

1 for each Cj

2" LCi=LoadFunction（Cj）;//計算控制器負載

3" if LCjlt;LT return 0;/*決策是否為過載控制器，是否進行交換機遷移*/

4" else

5""" Mi=1; //過載控制器標志位

6""" C=ODT（LCj）;//決策過載控制器集合C

7" end if

8 end for

9 for Ci in C //遍歷過載控制器

10" S=traversal（Ci，Lij，Xij）; //控制器管控的交換機集合

11" for Si in S

12""" Prir=Pr（）;//計算Si遷移到Cr的優先權

13""" Si=max{Prsj，sj∈S};//優先權最大進行遷移

14""" Migrate（si）=PDSS（S）;//決策遷移交換機

15""" U=U_function（Ci）; //計算效用函數

16""" Game={C，P，U};//建立博弈模型

17""" Cr=GAIMO（Si）; //決策目標控制器

18""" Master（Si）=Cr; //主從控制器角色轉換

18"" end for

20 end for

21 LC=sum（LCj）/n; //遷移后負載均衡度的計算

4 仿真實驗

4.1 實驗環境設定

實驗環境配置為Intel i5處理器，內存4 GB，CPU 3.40 GHz，Windows 10操作系統，使用仿真工具MATLAB R2017b，控制器容量設定為10 MB，交換機與控制器間時延和鏈路距離依據實驗拓撲得出。實驗仿真參數值參照流量特征數值［21］，控制器單位時間的處理Packet_In流請求數據包為10 000個左右。實驗采用Internet topology zoo［22］ 中具有一定規模差異的網絡拓撲，具體網絡信息如表1所示。

4.2 實驗與結果分析

為了驗證本文提出的 GAIMO 算法的有效性與可行性，本節將GAIMO算法與現有解決控制器負載均衡問題的GAPA算法［13］、proposed GA算法［14］以及GA算法［15］在網絡負載均衡度、平均總時延、遷移成本的性能上進行對比。設置固定交叉概率為0.4，變異概率為0.04，迭代次數為200。對于適應度函數值進行歸一化，同時為了突出重要因素對于控制平面與數據平面的影響，選取的權值比重w1、w2、w3分別為0.5、0.3和0.2。

4.2.1 控制器負載均衡度對比

在實驗開始后，每個交換機發送數據報文到OS3E網絡部署的五臺控制器，整個網絡被劃分為五個子域。等待10 s后，所有控制器獲得狀態初始值。在此時，控制器的負載較為均衡，負載比為2∶4∶3∶2∶3（圖3）。隨后，增加交換機和控制間的交互報文量，使控制器負載逐步上升。從圖中可以看出控制器C2和C4超出閾值線，先后出現了過載現象，在第40 s時負載比達到了10∶13∶11∶14∶8，通過式（6）計算得到此時負載均衡度為2.135 4。因而，GTMCR機制觸發，進行交換機遷移。之后，控制器之間負載差明顯收斂。交換機遷移結果是：C2下的部分交換機遷移到C1，C4下的部分交換機遷移到C5，遷移之后的負載比為23∶23∶22∶22∶22，負載均衡度為0.489 9，使得控制平面負載達到了新的平衡。

在圖4中，本文對GA、GAPA、proposed GA和GAIMO算法在控制器負載均衡適應度上的表現進行對比。縱坐標表示控制器負載均衡適應度函數值，反映控制器集群的負載均衡的情況。適應度數值越高，表示控制器負載均衡性能越好。為驗證四種算法對控制器集群負載的均衡效果，采用了基于OS3E的網絡拓撲，上述四種算法的適應度函數都有所提升，說明在負載失衡的情況下均能夠通過交換機遷移的方式在一定程度上實現負載均衡。GA和GAPA在200代的進化過程中容易出現大的波動，收斂性差，原因是交叉和變異概率固定不變難以收斂。proposed GA的負載均衡度的適應度值從0.813提升到0.915。相對而言，GAIMO收斂最快，負載均衡度的適應度值從0.813提升到0.95。可見，GAIMO算法能夠更有效地均衡控制平面負載。

為測試拓撲大小對算法性能的影響，本文采用的測試環境為五種不同網絡規模的拓撲結構。圖5中縱坐標為負載均衡度，值越小表明控制平面負載越均衡。在較小的OS3E網絡下，四種算法的負載均衡度差異較大。這是由于在較小的拓撲下，交換機節點較少，控制器間會因為管理交換機的數量不同而導致負載差異大，進而使負載均衡參數值偏大。隨著網絡規模的增大，GA和GAPA算法負載均衡度相近，均衡效果并不佳。相對而言，GAIMO算法隨拓撲的增大負載均衡效果更明顯，得到的負載均衡度始終比其他算法小，且變化趨勢較為平緩。由于GA、GAPA和proposed GA容易收斂到局部最優解，而GAIMO算法收斂到全局最優解，使得負載分配更加合理，網絡負載均衡度參數也越來越小。實驗結果也證明了 GA、GAPA和 proposed GA并不適用于小型網絡中，而GAIMO能夠在各種規模的網絡上保持較好的負載均衡性能。

4.2.2 交換機到控制器的平均總時延

為對比不同算法下交換機到控制器之間通信總時延的優化效果，實驗采用OS3E網絡測試時延適應度函數的優化效果。從圖6可以看出，proposed GA、GAPA 和GA算法中的最高適應度函數值最終只能收斂到0.85，均低于GAIMO算法，說明找到的映射方案并不是最佳的。GAIMO算法不僅收斂速度最快而且找到了最優解，更好地減少了遷移的總時延。在平均時延的控制上，GAIMO算法均優于其他算法且優化效果更加穩定，能夠較大幅度地縮短交換機到控制器之間的平均時延，更有效地減小通信開銷，保證網絡通信質量。

4.2.3 交換機的遷移成本

在交換機遷移過程中會產生大量的通信消息數據包，為實現控制器平面負載均衡的同時盡可能地減少遷移成本，實驗采用OS3E網絡測試不同算法下遷移成本的大小。測試結果如圖7所示。GA、proposed GA算法由于選擇策略過早收斂從而錯失了最優解，而GAPA算法一直都未收斂，原因是交叉和變異算子是固定值，無法根據迭代狀況作出相應的調整而難以收斂。GAIMO算法收斂速度更快，更容易找到最優解，目標函數值最終達到了0.9，是因為改進的算子結合迭代次數和適應度函數值的變化動態調整，達到更高效地找到全局最優解的目的。GAIMO算法的遷移策略效果最佳，能夠大幅度減少網絡中多臺交換機遷移的成本代價，證明了用交換機遷移方法提升網絡性能的有效性。

4.2.4 多目標性能優化

多目標優化適應度函數值反映控制器負載均衡的情況，適應度數值越高，控制器負載均衡的網絡性能越好。如圖8所示， GAIMO算法從20代開始，最優解的適應度值相比于其他算法更優且收斂速度最快。這是由于GAIMO算法采用相似算子，盡量避免下一代中出現近親繁殖，從而減少重復交叉和交叉無效的情況，減少了時間復雜度。GAIMO算法從50代開始穩定且找到最優部署。這是因為自適應的交叉概率考慮迭代次數以及變異概率考慮適應度函數值的偏好情況，突變的發生隨著遺傳代數和適應度函數值的增大而隨之減少。GAIMO算法最終的收斂值最大，說明GAIMO采用的精英策略防止了最優解丟失從而保證種群向優進化的趨勢并趨于穩定達到0.94。因此，GAIMO算法更能對激增的流量負載進行均衡的同時，提升控制平面的魯棒性。

5 結束語

本文構建了多目標優化模型GTMCR，對于判別過載控制器采用動態閾值ODT算法，遷移交換機的決策采用基于優先權的遷移策略PDSS算法，同時設置了相應的約束條件，采用改進的遺傳算法GAIMO獲得交換機遷移的最佳策略。實驗結果表明，GAIMO算法更加有效地提升收斂速度，能最快找到最優部署，合理地平衡控制器集群負載均衡度，提升了全局網絡性能。接下來，需要將重映射過程中控制器與交換機以及交換機間通信會出現丟包等容錯情況也考慮進來，如果當控制器負載嚴重過載或出現故障時，除了依靠交換機遷移，還需添加額外的控制器，進一步研究不同情況下的負載均衡。

參考文獻：

［1］Isong B，Molose R R S，Abu-Mahfouz A M，et al. Comprehensive review of SDN controller placement strategies ［J］. IEEE Access，2020，8： 170070-170092.

［2］Hamdan M，Hassan E，Abdelaziz A，et al. A comprehensive survey of load balancing techniques in software-defined network ［J］. Journal of Network and Computer Applications，2021，174： 102856.

［3］Alowa A，Fevens T，Khamayseh Y. Survival backup strategy for controller placement problem in software defined networking ［J］. Computer Communications，2022，185： 104-117.

［4］劉毅，李凱心，李國燕，等. 基于SDN的動態負載均衡策略 ［J］. 計算機應用研究，2020，37（10）： 3147-3152. （Liu Yi，Li Kaixin，Li Guoyan，et al. Dynamic load balancing strategy based on SDN ［J］. Application Research of Computers，2020，37（10）： 3147-3152.）

［5］Huang V，Chen Gang，Zhang Peng，et al. A scalable approach to SDN control plane management： high utilization comes with low latency ［J］. IEEE Trans on Network and Service Management，2020，17（2）： 682-695.

［6］Adekoya O，Aneiba A，Patwary M. An improved switch migration decision algorithm for SDN load balancing ［J］. IEEE Open Journal of the Communications Society，2020，1： 1602-1613.

［7］Shirmarz A，Ghaffari A. Taxonomy of controller placement problem （CPP） optimization in software defined network （SDN）： a survey ［J］. Journal of Ambient Intelligence and Humanized Computing，2021，12（12）： 10473-10498.

［8］Lan Wenjing，Li Fangmin，Liu Xinhua，et al. A dynamic load balancing mechanism for distributed controllers in software-defined networking ［C］// Proc of the 10th International Conference on Measuring Technology and Mechatronics Automation. Piscataway，NJ： IEEE Press，2018： 259-262.

［9］Mokhtar H，Di Xiaoqiang，Zhou Ying，et al. Multiple-level threshold load balancing in distributed SDN controllers ［J］. Computer Networks，2021，198： 108369.

［10］Xiao Han，Hu Bo，Zhou Lingye，et al. DMSSM： a decision-making scheme of switch migration for SDN control plane ［C］// Proc of the 7th IEEE International Conference on Computer Science and Network Technology. Piscataway，NJ： IEEE Press，2019： 348-352.

［11］Sahoo K S，Puthal D，Tiwary M，et al. ESMLB： efficient switch migration-based load balancing for multi-controller SDN in IoT ［J］. IEEE Internet of Things Journal，2020，7（7）： 5852-5860.

［12］Zhong Hong，Xu Jinshan，Cui Jie，et al. Prediction-based dual-weight switch migration scheme for SDN load balancing ［J］. Computer Networks，2022，205： 108749.

［13］Yuan Tingting，Huang Xiaohong，Ma Maode，et al. Balance-based SDN controller placement and assignment with minimum weight matching ［C］// Proc of IEEE International Conference on Communications. Piscataway，NJ： IEEE Press，2018： 1-6.

［14］Mohanty S，Priyadarshini P，Sahoo S，et al. Metaheuristic techniques for controller placement in software-defined networks ［C］// Proc of TENCON-IEEE Region 10 Conference. Piscataway，NJ： IEEE Press，2019： 897-902.

［15］Ibrahim A A Z，Hashim F，Sali A，et al. A modified genetic algorithm for controller placement problem in SDN distributed network ［C］// Proc of the 26th IEEE Asia-Pacific Conference on Communications. Piscataway，NJ： IEEE Press，2021： 83-88.

［16］Schütz G，Martins J A. A comprehensive approach for optimizing controller placement in software-defined networks ［J］. Computer Communications，2020，159： 198-205.

［17］Ibrahim A A Z，Hashim F，Noordin N K，et al. Heuristic resource allocation algorithm for controller placement in multi-control 5G based on SDN/NFV architecture ［J］. IEEE Access，2021，9： 2602-2617.

［18］Zhong Hong，Fan Jinpeng，Cui Jie，et al. Assessing profit of prediction for SDN controllers load balancing ［J］. Computer Networks，2021，191： 107991.

［19］Katoch S，Chauhan S S，Kumar V. A review on genetic algorithm： past，present，and future ［J］. Multimedia Tools and Applications，2021，80（5）： 8091-8126.

［20］Bao Lei，Zhang Linxuan，Sun Teng. Research on assembly line sche-duling based on small population adaptive genetic algorithm ［C］// Proc of the 6th International Conference on Intelligent Computing and Signal Processing. Piscataway，NJ： IEEE Press，2021： 166-170.

［21］Isyaku B，Zahid M S M，Kamat M B，et al. Software defined networking flow table management of openflow switches performance and security challenges： a survey ［J］. Future Internet，2020，12（9）： 147.

［22］Knight S，Nguyen H X，Falkner N，et al. The Internet topology zoo ［J］. IEEE Journal on Selected Areas in Communications，2011，29（9）： 1765-1775.