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

朱國暉，劉茹文，楊 瑛

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

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

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

文獻(xiàn)[9]提出了一種主從模式的高可用動(dòng)態(tài)部署算法，通過在鄰域內(nèi)選取從控制器來接管失控交換機(jī)，保證了故障恢復(fù)時(shí)延較短。文獻(xiàn)[2]提出了一種帶內(nèi)通信場景下平面式的多控制器容錯(cuò)架構(gòu)，單控制器控制單個(gè)自治域，在可接受的時(shí)間內(nèi)完成控制器故障的快速恢復(fù)。文獻(xiàn)[10]提出了一種SDN控制器節(jié)點(diǎn)故障恢復(fù)的部署策略，采用熵權(quán)多目標(biāo)決策方法，對(duì)控制器進(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ī)制的備份控制器部署方法即多個(gè)網(wǎng)絡(luò)域共享一定數(shù)目的備份控制器，考慮了備份控制器的數(shù)目和備份控制器的放置能夠合理地利用網(wǎng)絡(luò)資源，但是會(huì)導(dǎo)致部分控制器超載現(xiàn)象。

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

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

本文主要工作如下：

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

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

1 模型建立

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

圖1 一個(gè)簡單的多控制器架構(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ī)的個(gè)數(shù)；E代表網(wǎng)絡(luò)中的鏈路集合；將網(wǎng)絡(luò)劃分成q個(gè)子網(wǎng)絡(luò)域，每個(gè)子網(wǎng)域內(nèi)包含任意p(1≤p≤n)個(gè)交換機(jī)，整個(gè)網(wǎng)絡(luò)包含1個(gè)主控制器和q個(gè)子控制器組成，C表示控制器集合C=(c1,c2,…,cm)，整個(gè)網(wǎng)絡(luò)有m=||C個(gè)控制器；任意兩個(gè)子域間互不重疊，并且每個(gè)交換機(jī)只屬于某個(gè)子網(wǎng)絡(luò)域。

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

步驟2根據(jù)Packet-In消息速率大小對(duì)失控交換機(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)化算法對(duì)備份控制器進(jìn)行動(dòng)態(tài)調(diào)整，其中包括：

（1）初始化

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

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

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

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

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

（4）終止迭代

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

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

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

2.1 備份控制器挑選算法

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

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

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

因此為確保正常的子控制器在接管失控交換機(jī)時(shí)不出現(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.主控制器集中獲取每個(gè)子控制器的剩余負(fù)載大小

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

3.2.2 仿真驗(yàn)證

為了驗(yàn)證該算法的合理性，本文采用了不同規(guī)模的網(wǎng)絡(luò)對(duì)算法性能進(jìn)行驗(yàn)證，實(shí)驗(yàn)過程中采用了5個(gè)不同規(guī)模的網(wǎng)絡(luò)拓?fù)洌總€(gè)拓?fù)涞牟町愋泽w現(xiàn)在失控交換機(jī)的數(shù)量不一樣，其中網(wǎng)絡(luò)拓?fù)湫畔⑷绫?所示。實(shí)驗(yàn)中采用cbench工具對(duì)控制器的負(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í)驗(yàn)過程中為了保證實(shí)驗(yàn)結(jié)果的正確性，本文在每一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下進(jìn)行10次實(shí)驗(yàn)，并取10次實(shí)驗(yàn)的平均值作為實(shí)驗(yàn)結(jié)果。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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