多種群粒子群的SDN控制器故障恢復(fù)算法

朱國暉，劉茹文，楊 瑛

西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710121

軟件定義網(wǎng)絡(luò)（software defined network，SDN）實(shí)現(xiàn)了控制平面與數(shù)據(jù)平面分離，采用了中心化的控制器對網(wǎng)絡(luò)進(jìn)行集中式管理[1]，相比于傳統(tǒng)網(wǎng)絡(luò)，有效地提高了網(wǎng)絡(luò)的靈活性。SDN在快速發(fā)展的同時也面臨著一些挑戰(zhàn)，如控制器的可擴(kuò)展性，SDN的故障恢復(fù)等[2]。其中SDN的故障恢復(fù)是不可忽視的問題，SDN網(wǎng)絡(luò)中的故障主要存在于數(shù)據(jù)平面和控制平面。在控制平面中，一旦控制器出現(xiàn)故障，若沒有其他正常工作的控制器來接管失控的交換機(jī)，則會影響整個故障控制器所管理的網(wǎng)絡(luò)域內(nèi)的信息傳輸。因此為了避免因單控制器故障而造成網(wǎng)絡(luò)性能下降的現(xiàn)象，在SDN網(wǎng)絡(luò)中大多都采用分布式的架構(gòu)[3-4]，在整個網(wǎng)絡(luò)中同時部署多個控制器，每個網(wǎng)絡(luò)域內(nèi)都有一個子控制器來管理域內(nèi)的所有交換機(jī)。當(dāng)某個子控制器發(fā)生故障時，該控制器下的失控交換機(jī)可以遷移到其他正常工作的子控制器上，從而保證網(wǎng)絡(luò)的正常運(yùn)行。那么在交換機(jī)遷移過程又如何在控制器不發(fā)生超載的情況下，最小化交換機(jī)到控制器之間的平均傳播時延成為了研究的熱點(diǎn)問題。

文獻(xiàn)[5]提出了基于控制時延可靠性的控制器部署策略以提升網(wǎng)絡(luò)的可靠性。文獻(xiàn)[6]針對大規(guī)模SDN網(wǎng)絡(luò)，采用改進(jìn)的標(biāo)簽傳播算法（LPA）將網(wǎng)絡(luò)劃分成多個子域，然后在子域中分別部署控制器。文獻(xiàn)[7]提出了一種蝙蝠算法進(jìn)行多控制器的部署，算法在迭代時不斷地優(yōu)化平均控制時延，限制控制器負(fù)載利用率保證了控制器間的負(fù)載均衡。文獻(xiàn)[8]提出了基于負(fù)載均衡的多控制器部署算法。以上文獻(xiàn)均是針對控制器部署問題展開研究，沒有考慮到控制器發(fā)生故障的情況。

文獻(xiàn)[9]提出了一種主從模式的高可用動態(tài)部署算法，通過在鄰域內(nèi)選取從控制器來接管失控交換機(jī)，保證了故障恢復(fù)時延較短。文獻(xiàn)[2]提出了一種帶內(nèi)通信場景下平面式的多控制器容錯架構(gòu)，單控制器控制單個自治域，在可接受的時間內(nèi)完成控制器故障的快速恢復(fù)。文獻(xiàn)[10]提出了一種SDN控制器節(jié)點(diǎn)故障恢復(fù)的部署策略，采用熵權(quán)多目標(biāo)決策方法，對控制器進(jìn)行故障恢復(fù)從而保證網(wǎng)絡(luò)的正常運(yùn)行。文獻(xiàn)[11]提出了一種啟發(fā)式控制器故障恢復(fù)算法，該算法在保證控制器不發(fā)生超載的情況下，控制備份控制器的激活數(shù)量，節(jié)省修復(fù)開銷。但是算法的執(zhí)行效率不高，不能很快地完成失控交換機(jī)的遷移過程。文獻(xiàn)[12]提出了一種基于控制網(wǎng)絡(luò)生存性的備份控制器放置方法，沒有考慮到備份控制器的數(shù)量和負(fù)載容量。文獻(xiàn)[13]提出了一種基于共享機(jī)制的備份控制器部署方法即多個網(wǎng)絡(luò)域共享一定數(shù)目的備份控制器，考慮了備份控制器的數(shù)目和備份控制器的放置能夠合理地利用網(wǎng)絡(luò)資源，但是會導(dǎo)致部分控制器超載現(xiàn)象。

目前，粒子群優(yōu)化算法可以解決備份控制器的部署問題，但在解決這個問題時，容易陷入局部最優(yōu)，算法的復(fù)雜度高，使得故障恢復(fù)時間較長。為了更好地部署備份控制器，本文把機(jī)械臂路徑規(guī)劃中的多種群粒子群算法應(yīng)用在SDN控制器故障恢復(fù)的場景中。多種群粒子群算法是一種具有預(yù)選擇與交互機(jī)制的精英種群引導(dǎo)的算法[14]。

多種群粒子群算法將每個備份控制器當(dāng)作粒子，經(jīng)過迭代演化得到備份控制器的最優(yōu)位置，使得備份控制器與待遷移交換機(jī)的平均傳播時延最短。

本文主要工作如下：

（1）在多控制器網(wǎng)絡(luò)環(huán)境下，若一個子網(wǎng)絡(luò)域內(nèi)的控制器發(fā)生故障，首先采用備份控制器的挑選算法，從其他正常的子控制器中挑選出能夠容納失控交換機(jī)負(fù)載的備份控制器集合。

（2）提出了一種基于多種群粒子群的備份控制器調(diào)整算法，通過設(shè)置不同的子種群數(shù)，觀察對備份控制器部署的影響，并選出了該算法的最優(yōu)參數(shù)，為證明多種群蟻群算法在求解備份控制最優(yōu)位置時，能夠很快跳出最優(yōu)解，使得故障恢復(fù)時間較短，并將該算法與其他故障恢復(fù)算法進(jìn)行對比實(shí)驗。

1 模型建立

本文以一個簡單的多控制器構(gòu)架圖為示例進(jìn)行分析說明，如圖1所示主控制器控制整個SDN網(wǎng)絡(luò)域，同時作為控制器1、2、3的通信橋梁，掌握整個網(wǎng)絡(luò)域中的動態(tài)信息?？刂破?、2、3分別掌管自己所管轄的網(wǎng)絡(luò)域。假設(shè)控制器1出現(xiàn)了故障，則需要將該控制器所管理的網(wǎng)絡(luò)域內(nèi)的失控交換機(jī)重新托管給其他正常工作的控制器管理。

圖1 一個簡單的多控制器架構(gòu)圖Fig.1 Simple multi-controller architecture of SDN

將SDN網(wǎng)絡(luò)構(gòu)建成一張無向圖G=(V,E)，其中V代表網(wǎng)絡(luò)中交換機(jī)的集合V=(v1,v2,…,vn),n=|V|表示交換機(jī)的個數(shù)；E代表網(wǎng)絡(luò)中的鏈路集合；將網(wǎng)絡(luò)劃分成q個子網(wǎng)絡(luò)域，每個子網(wǎng)域內(nèi)包含任意p(1≤p≤n)個交換機(jī)，整個網(wǎng)絡(luò)包含1個主控制器和q個子控制器組成，C表示控制器集合C=(c1,c2,…,cm)，整個網(wǎng)絡(luò)有m=||C個控制器；任意兩個子域間互不重疊，并且每個交換機(jī)只屬于某個子網(wǎng)絡(luò)域。

定義1（交換機(jī)與控制器的連接矩陣X）X=[xi,j]n×n表示控制器與交換機(jī)之間的映射關(guān)系，如公式（1）所示：

定義3（交換機(jī)與控制器之間的直線距離d(vi,cj)）在SDN網(wǎng)絡(luò)中，計算兩個節(jié)點(diǎn)的距離需要考慮到地面弧度[15]。假設(shè)地球為一個半徑為r的球體，節(jié)點(diǎn)vi、cj的經(jīng)度分別為αi、αj，節(jié)點(diǎn)vi、cj的緯度分別為βj、βj。且規(guī)定計算經(jīng)度時，東經(jīng)為正，西經(jīng)為負(fù)；計算緯度時，南緯90°為正緯度值，北緯90°為負(fù)緯度值[17]，交換機(jī)與控制器之間的直線距離d(vi,cj)如公式（3）所示：

定義4（交換機(jī)與控制器之間的平均傳播時延Lavg）在SDN網(wǎng)絡(luò)中，交換機(jī)與控制器的物理距離是影響傳播時延的主要因素，實(shí)驗過程中假設(shè)每個交換機(jī)到控制器之間的傳輸速度v都一樣，因此平均傳播時延Lavg可以用所有交換機(jī)vi∈S到相應(yīng)控制器cj∈C最短傳輸時間的平均值來表示，如公式（4）、（5）所示：

其中，t(vi,cj)表示任意兩個節(jié)點(diǎn)間（交換機(jī)與控制器）最短傳輸時間。

定義5（每個控制器剩余負(fù)載Rj）本文不考慮控制器之間的差異性，所有控制器都有相同的負(fù)載容量、處理能力等。由于控制器負(fù)載可近似由Packet-In消息的計算開銷組成，所以上述控制器使用的負(fù)載均用當(dāng)前Packet-In消息到達(dá)速率來表示[2]。本文通過主控制器集中計算當(dāng)前每個控制器剩余負(fù)載，其計算公式如式（6）所示：

目標(biāo)函數(shù)如式（7）所示，最小化交換機(jī)與控制器之間的平均傳播時延Lavg。約束條件（8）表示交換機(jī)遷移后的連接矩陣，k表示交換機(jī)的個數(shù)；約束條件（9）保證控制器的剩余負(fù)載大于等于0；約束條件（10）保證網(wǎng)絡(luò)中的交換機(jī)在任何情況下只分配給一個主控制器；約束條件（12）保證了恢復(fù)過程中所有的備份控制器都屬于原有的主控制器。其中yi表示控制器ci為備份控制器時值為1，否則為0。

2 算法設(shè)計

算法的總體流程圖如圖2所示，算法步驟如下：

圖2 算法的總體流程圖Fig.2 Overall flow chart of algorithm

步驟1首先挑選出能夠容納失控交換機(jī)負(fù)載的備份控制器集合。

步驟2根據(jù)Packet-In消息速率大小對失控交換機(jī)集合進(jìn)行降序排列，優(yōu)先為Packet-In消息速率較大的交換機(jī)進(jìn)行遷移（原因是交換機(jī)產(chǎn)生的Packet-In消息速率越大，說明其與控制器間的數(shù)據(jù)交互越頻繁，應(yīng)當(dāng)優(yōu)先處理）。

步驟3采用多種群粒子群優(yōu)化算法對備份控制器進(jìn)行動態(tài)調(diào)整，其中包括：

（1）初始化

設(shè)置失控交換機(jī)受備份控制器控制的數(shù)量為0，經(jīng)過實(shí)驗分析設(shè)置子種群的數(shù)量為3，種群大小Number=100，實(shí)驗的測試次數(shù)為100次，最終迭代次數(shù)為10 000次。學(xué)習(xí)因子c1、c2代表了粒子向自身極值和全局極值推進(jìn)的加速權(quán)值，通常把c1、c2設(shè)置為2.0，代表對兩個方向的同等重視，粒子的速度決定移動的方向和距離，一般設(shè)置粒子的最大飛行速度vmax為1.7[14]。

（2）局部最優(yōu)

首先從每個子種群中挑選出n個粒子組成精英種群，讓子種群和精英種群分別進(jìn)行演化。在其子種群的演化過程中計算出每個粒子的適應(yīng)度函數(shù)值，并得到子種群的個體最優(yōu)值，然后把3個個體最優(yōu)值進(jìn)行比較，并輸出一個局部最優(yōu)值。在精英種群演化過程中，不斷用子種群最優(yōu)的粒子去替換精英種群中表現(xiàn)劣于子種群表現(xiàn)最優(yōu)的粒子，更新精英種群，并形成新的精英種群，最后輸出精英種群的個體最優(yōu)值。

（3）全局最優(yōu)

將子種群中的局部最優(yōu)值和精英種群中的個體最優(yōu)值進(jìn)行對比分析，得到全局最優(yōu)值，那么此時全局最優(yōu)值就是備份控制器與待遷移交換機(jī)的最優(yōu)匹配對。

（4）終止迭代

判斷所有待遷移的交換機(jī)是否完成分配。

多種群粒子群優(yōu)化算法中的適應(yīng)度函數(shù)如公式（13）所示，在演化過程中粒子的更新速度如（14）、（15）所示：

公式（13）中f(yi)表示備份控制器的總數(shù)。公式（14）、（15）中vk表示k時刻粒子的速度，r1、r2為隨機(jī)序列，且r1∈[0,1,]r2∈[0,1]，ak表示k時刻粒子的位置，ωk表示慣性權(quán)重，k=0,1,…,100。

2.1 備份控制器挑選算法

在一個子網(wǎng)絡(luò)域中，當(dāng)控制器出現(xiàn)故障時，其管理域內(nèi)的交換機(jī)需要遷移到其他正常的子控制器上，以保證網(wǎng)絡(luò)的正常運(yùn)行。而在遷移的過程中，需要確保正常的子控制器在接管失控交換機(jī)時不出現(xiàn)負(fù)載震蕩現(xiàn)象。

如圖3所示，失控的交換機(jī)負(fù)載為3個單位，從圖中可以看出，控制器2有足夠的剩余負(fù)載可供選擇，如果控制器1和控制器3去接管失控交換機(jī)將會出現(xiàn)剩余負(fù)載不足的情況，給網(wǎng)絡(luò)系統(tǒng)帶來負(fù)載震蕩現(xiàn)象。

圖3 控制器之間的負(fù)載分配Fig.3 Load distribution between controllers

因此為確保正常的子控制器在接管失控交換機(jī)時不出現(xiàn)負(fù)載震蕩現(xiàn)象，需滿足待遷移交換機(jī)的總負(fù)載小于正常的子控制器的剩余負(fù)載，即公式（16）表示。

算法1的具體步驟如下：

算法1備份控制器挑選算法

輸入：失控交換機(jī)集合Vuc，從控制器集合Cslave輸出：備份控制器集合Cbp

1.|Vuc|=n1,n1∈(0,n);|Cslave|=m1//初始化從控制器數(shù)目和失控交換機(jī)的數(shù)目

2.主控制器集中獲取每個子控制器的剩余負(fù)載大小

4.挑選出能夠滿足條件的備份控制器。

5.output：Cbp//備份控制器集合Cbp

2.2 基于多種群粒子群的備份控制器調(diào)整算法

在算法1的基礎(chǔ)上提出了基于多種群粒子群的備份控制器調(diào)整算法。該算法將備份控制器抽象為粒子，然后算法一直循環(huán)迭代演化，直到跳出局部最優(yōu)找到全局最優(yōu)解即使得失控交換機(jī)與備份控制器之間的平均傳播時延最小。具體過程如算法2所示。

算法2基于多種群粒子群的備份控制器調(diào)整算法

輸入：備份控制器集合Cbp，失控交換機(jī)集合Vuc

輸出：失控交換機(jī)與備份控制器的匹配對集合A1

3 實(shí)驗分析

3.1 實(shí)驗環(huán)境

本文采用的實(shí)驗環(huán)境為Intel?Core? i5-4570 CPU@3.20 GHz，16.00 GB內(nèi)存，操作系統(tǒng)Windows10版本（64位），算法均在MATLAB2018a軟件上進(jìn)行仿真實(shí)驗。實(shí)驗的控制器采用OpenDaylight，用到的虛擬機(jī)Mininet在軟件Ubuntu16.04上進(jìn)行操作，并使用cbench工具測試控制器的負(fù)載能力。

3.2 實(shí)驗結(jié)果

3.2.1 多種群粒子群算法在不同子種群個數(shù)下的結(jié)果分析

首先，對多種群粒子群算法在不同參數(shù)下進(jìn)行仿真，仿真結(jié)果如表1，表示在不同子種群個數(shù)下的演化結(jié)果。

表1 在不同子種群個數(shù)下的適應(yīng)度比較Table 1 Comparison of fitness values in different subpopulations ms

由表1知道，只有子種群的個數(shù)為3時，求出的適應(yīng)度函數(shù)值最小即備份控制器與待遷移交換機(jī)之間的平均傳播時延最小。算法在迭代次數(shù)為10 000次時，適應(yīng)度函數(shù)值趨于穩(wěn)定。

3.2.2 仿真驗證

為了驗證該算法的合理性，本文采用了不同規(guī)模的網(wǎng)絡(luò)對算法性能進(jìn)行驗證，實(shí)驗過程中采用了5個不同規(guī)模的網(wǎng)絡(luò)拓?fù)?，每個拓?fù)涞牟町愋泽w現(xiàn)在失控交換機(jī)的數(shù)量不一樣，其中網(wǎng)絡(luò)拓?fù)湫畔⑷绫?所示。實(shí)驗中采用cbench工具對控制器的負(fù)載容量進(jìn)行了測試，結(jié)果顯示本文中控制器的容量限制為5 000條packet_in消息范圍內(nèi)，交換機(jī)的負(fù)載保持在100條/s到200條/s的信息。

表2 網(wǎng)絡(luò)拓?fù)湫畔able 2 Network topology information

實(shí)驗過程中為了保證實(shí)驗結(jié)果的正確性，本文在每一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下進(jìn)行10次實(shí)驗，并取10次實(shí)驗的平均值作為實(shí)驗結(jié)果。

將本文提出的算法（CFRS）與BCS[11]和SBC[13]算法進(jìn)行對比。BCS是備份控制器選擇算法，在滿足負(fù)載約束的前提下找到最少數(shù)量的備份控制器集合，節(jié)約了控制器的激活開銷；SBC是一種基于共享機(jī)制的控制器故障恢復(fù)算法，多個網(wǎng)絡(luò)域共享一定數(shù)目的備份控制器。本文綜合考慮了控制器負(fù)載容量和平均傳播時延，在滿足控制器容量的前提下，動態(tài)調(diào)整備份控制器的位置以達(dá)到全局最優(yōu)。本文分別從故障恢復(fù)時延和控制器的負(fù)載利用率兩個方面驗證CFRS算法的有效性。

（1）故障恢復(fù)時延

圖4為不同算法的故障恢復(fù)時間對比圖，橫坐標(biāo)表示每一個網(wǎng)絡(luò)拓?fù)渲惺Э亟粨Q機(jī)的個數(shù)，縱坐標(biāo)表示每個網(wǎng)絡(luò)拓?fù)湓?0次實(shí)驗中取得的平均恢復(fù)時間。隨著失控交換機(jī)數(shù)量的增加，故障恢復(fù)時間也隨之而增加。本文提出的CFRS算法明顯縮短了故障恢復(fù)時間。相比于BCS和SBC算法，該算法在故障恢復(fù)時延上最大減小了35%，平均減小了26%，其原因在于多種群粒子群算法根據(jù)目標(biāo)函數(shù)對備份控制器的位置進(jìn)行不斷的優(yōu)化，采用了預(yù)選和交互的機(jī)制讓算法很快跳出局部最優(yōu)達(dá)到全局最優(yōu)，節(jié)約了搜索時間，算法效率高；而且遷移后的控制鏈路平均時延較低，因此故障恢復(fù)時間較短。SBC采用的粒子群算法解決備份控制的數(shù)量與位置問題，在交換機(jī)遷移的過程中容易陷入局部最優(yōu)，導(dǎo)致故障恢復(fù)時間比較長。BCS雖然考慮了減少控制器和交換機(jī)之間的時延，但算法的執(zhí)行效率比較低。

圖4 故障恢復(fù)時間Fig.4 Fault recovery time

（2）備份控制器的負(fù)載性能

由于在交換機(jī)的遷移過程中容易出現(xiàn)負(fù)載分配不均而造成控制器超載，所以本文給出了以下兩種性能指標(biāo)來驗證控制器的負(fù)載利用率。

指標(biāo)1為備份控制器需要接管的交換機(jī)負(fù)載占總失控交換機(jī)負(fù)載的比值，用字母w1表示；指標(biāo)2為備份控制器接管交換機(jī)負(fù)載占該控制器剩余負(fù)載的比值，用字母w2表示。

圖5給出了備份控制器需要接管的交換機(jī)的負(fù)載占總失控交換機(jī)負(fù)載的比值結(jié)果，實(shí)驗結(jié)果表明，本文所提的CFRS算法中，每個備份控制器所接管的失控交換機(jī)的個數(shù)基本一致。其原因是該算法不斷地更新每個子控制器的剩余負(fù)載，在每個子控制器不發(fā)生超載的情況下，實(shí)現(xiàn)了失控交換機(jī)負(fù)載的均衡分配。SCB算法沒有考慮到負(fù)載均衡從而導(dǎo)致每個備份控制器在分配失控交換機(jī)的個數(shù)存在明顯的差異，分布不均勻。

圖5 占總負(fù)載比值Fig.5 Ratio to total load

圖6給出了備份控制器接管交換機(jī)負(fù)載占該控制器剩余負(fù)載的比值結(jié)果，實(shí)驗結(jié)果表明，三種算法使用了相同數(shù)目的備份控制器完成了失控交換機(jī)的遷移。CFRS算法中的每個備份控制器都沒有出現(xiàn)負(fù)載震蕩現(xiàn)象，并充分利用了每個備份控制器的剩余負(fù)載，其原因是在算法1中保證了備份控制器的負(fù)載在合理范圍內(nèi)，同時在算法2中實(shí)時地更新子控制器的剩余負(fù)載。SBC算法采用了共享機(jī)制的控制器故障恢復(fù)方法，其備份控制器接管交換機(jī)負(fù)載占該控制器剩余負(fù)載的比值結(jié)果偏高，導(dǎo)致部分備份控制器超載。而BCS算法雖然考慮到了備份控制器的負(fù)載，但是并沒有對備份控制器的剩余負(fù)載進(jìn)行實(shí)時更新。

圖6 占剩余負(fù)載比值Fig.6 Ratio to remaining load

4 結(jié)束語

本文針對多控制器網(wǎng)絡(luò)環(huán)境下的單一控制器發(fā)生故障問題，提出了一種基于多種群粒子群的SDN網(wǎng)絡(luò)控制器故障恢復(fù)算法。實(shí)驗結(jié)果表明，與現(xiàn)有的控制器故障恢復(fù)算法相比，本文所提算法在恢復(fù)時間、控制器負(fù)載利用方面均有所提升。本文局限于多控制器網(wǎng)絡(luò)環(huán)境下的單一控制器發(fā)生故障的情況，沒有考慮到多個控制器同時發(fā)生故障的情況，因此下一步的工作是當(dāng)多個控制器發(fā)生故障時，繼續(xù)完善故障恢復(fù)機(jī)制，進(jìn)一步提高網(wǎng)絡(luò)的可靠性。