朱國暉，劉茹文，楊 瑛

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

軟件定義網(wǎng)絡(luò)（software defined network，SDN）實現(xiàn)了控制平面與數(shù)據(jù)平面分離，采用了中心化的控制器對網(wǎng)絡(luò)進行集中式管理[1]，相比于傳統(tǒng)網(wǎng)絡(luò)，有效地提高了網(wǎng)絡(luò)的靈活性。SDN在快速發(fā)展的同時也面臨著一些挑戰(zhàn)，如控制器的可擴展性，SDN的故障恢復(fù)等[2]。其中SDN的故障恢復(fù)是不可忽視的問題，SDN網(wǎng)絡(luò)中的故障主要存在于數(shù)據(jù)平面和控制平面。在控制平面中，一旦控制器出現(xiàn)故障，若沒有其他正常工作的控制器來接管失控的交換機，則會影響整個故障控制器所管理的網(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)的所有交換機。當某個子控制器發(fā)生故障時，該控制器下的失控交換機可以遷移到其他正常工作的子控制器上，從而保證網(wǎng)絡(luò)的正常運行。那么在交換機遷移過程又如何在控制器不發(fā)生超載的情況下，最小化交換機到控制器之間的平均傳播時延成為了研究的熱點問題。

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

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

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

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

本文主要工作如下：

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

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

1 模型建立

本文以一個簡單的多控制器構(gòu)架圖為示例進行分析說明，如圖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)的失控交換機重新托管給其他正常工作的控制器管理。

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

（1）初始化

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

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

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

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

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

（4）終止迭代

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

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

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

2.1 備份控制器挑選算法

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

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

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

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

算法1的具體步驟如下：

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果

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

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

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

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

3.2.2 仿真驗證

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

表2 網(wǎng)絡(luò)拓撲信息Table 2 Network topology information

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

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

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

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

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

（2）備份控制器的負載性能

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

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

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

圖5 占總負載比值Fig.5 Ratio to total load

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

圖6 占剩余負載比值Fig.6 Ratio to remaining load

4 結(jié)束語

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