趙文文, 孟相如, 康巧燕, 陽 勇

(1. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077;2. 中國(guó)人民解放軍第69235部隊(duì), 新疆 烏蘇 833000)

0 引 言

軟件定義網(wǎng)絡(luò)(software defined networking, SDN)因其控制平面和數(shù)據(jù)平面高度解耦的體系架構(gòu)和動(dòng)態(tài)可編程的功能特點(diǎn),正逐漸成為數(shù)字網(wǎng)絡(luò)發(fā)展的重要方向,對(duì)數(shù)據(jù)中心網(wǎng)絡(luò)、傳統(tǒng)運(yùn)營(yíng)商網(wǎng)絡(luò)的發(fā)展提供了重要思路和方向。其數(shù)控分離的架構(gòu)理念、靈活高效的組網(wǎng)方式為網(wǎng)絡(luò)的運(yùn)行、維護(hù)與管理(operation, administration, maintenance, OAM)提供了極大的便利,使網(wǎng)絡(luò)自動(dòng)化維護(hù)、動(dòng)態(tài)化適應(yīng)、智能化調(diào)整成為可能[1]。

按照控制器數(shù)量不同,SDN分為單控制器SDN和多控制器SDN,其中單控制器SDN部署方式簡(jiǎn)單、經(jīng)濟(jì),但由于全網(wǎng)僅依靠單個(gè)控制器進(jìn)行路由計(jì)算、流表下發(fā)、網(wǎng)絡(luò)管理等網(wǎng)絡(luò)控制操作,導(dǎo)致控制器容易成為網(wǎng)絡(luò)性能的瓶頸,對(duì)網(wǎng)絡(luò)的安全性也帶來不小挑戰(zhàn),容易出現(xiàn)“一點(diǎn)被毀,全網(wǎng)受損”的安全問題[2]。為此,研究人員提出了多控制器SDN,將整個(gè)SDN劃分為不同控制域,每個(gè)控制域分屬不同控制器,控制器之間通過東西向接口進(jìn)行協(xié)同交互,共同實(shí)現(xiàn)SDN的OAM功能。

在多控制器SDN中,控制器與控制器之間的通信接口為東西向接口,主要通過相關(guān)協(xié)議進(jìn)行網(wǎng)絡(luò)視圖更新、狀態(tài)同步、路由信息傳輸?shù)扔蜷g信息交互[3],同時(shí)進(jìn)行網(wǎng)絡(luò)區(qū)域隔離,防止廣播風(fēng)暴在全網(wǎng)范圍蔓延。在實(shí)際部署應(yīng)用中,很多場(chǎng)景都需要通過東西向接口來同步控制器之間的OAM信息,比如在運(yùn)營(yíng)商網(wǎng)絡(luò)中,接入網(wǎng)、回傳網(wǎng)、核心網(wǎng)三者功能差異巨大,需要指定不同控制器間的不同應(yīng)用相互協(xié)同運(yùn)行,以實(shí)現(xiàn)全網(wǎng)信息同步,此時(shí)就需要通過東西向接口完成控制器之間的通信。再比如在跨數(shù)據(jù)中心網(wǎng)絡(luò)中,各控制器之間也存在協(xié)同通信的類似需求[4]?？梢?東西向接口在多控制器SDN域間信息交互中發(fā)揮著紐帶作用,其域間時(shí)延、帶寬、可靠性等因素對(duì)整個(gè)SDN的性能具有巨大影響。

目前,關(guān)于SDN東西向接口的研究還處于起步探索階段,配套的行業(yè)標(biāo)準(zhǔn)尚未完全建立。文獻(xiàn)[5]針對(duì)SDN跨域服務(wù)中的資源管理問題,提出了一種跨域服務(wù)協(xié)商方案,并基于OpenDayLight開源控制器平臺(tái)設(shè)計(jì)和實(shí)現(xiàn)了相關(guān)原型系統(tǒng),為面向異構(gòu)多域的服務(wù)提供商提供有效和靈活的網(wǎng)絡(luò)資源管理服務(wù)提供了支持。文獻(xiàn)[6]著眼于異構(gòu)SDN控制器域間的信息流轉(zhuǎn)問題,設(shè)計(jì)了一種用于SDN移動(dòng)自組網(wǎng)的網(wǎng)絡(luò)協(xié)議,有效降低了通信開銷,為SDN移動(dòng)自組網(wǎng)絡(luò)拓展提供了標(biāo)準(zhǔn)支撐。文獻(xiàn)[7]提出并實(shí)現(xiàn)了一種分布式控制平面通信接口,以滿足多個(gè)分布式SDN控制器之間的同步和通告信息交換等服務(wù)要求,并在該結(jié)構(gòu)中實(shí)現(xiàn)了防火墻、負(fù)載均衡器等網(wǎng)絡(luò)功能服務(wù)。文獻(xiàn)[8]提出了一種具有全網(wǎng)狀連接的高性能東西橋,用于異構(gòu)網(wǎng)絡(luò)操作系統(tǒng)在企業(yè)、數(shù)據(jù)中心和域內(nèi)網(wǎng)絡(luò)中交換網(wǎng)絡(luò)視圖。文獻(xiàn)[9]提出了一種面向異構(gòu)分布式SDN的東西向接口協(xié)議——控制平面框架。在該框架中,控制器使用數(shù)據(jù)分發(fā)服務(wù),通過實(shí)時(shí)發(fā)布/訂閱范例來同步全網(wǎng)拓?fù)湟晥D。文獻(xiàn)[10]設(shè)計(jì)了一種包含異構(gòu)控制器管理模塊和域關(guān)系管理模塊的東西向接口通信框架,實(shí)現(xiàn)了控制器管理和網(wǎng)絡(luò)管理信息收集、更新等功能。在東西向接口商業(yè)化部署方面,華為公司面向東西向接口,提出了基于水平架構(gòu)的SDNi東西向接口[11],并依托OpenDayLight框架實(shí)現(xiàn)了SDN東西向接口之間的域間通信功能,以及傳輸包括QoS數(shù)據(jù)及其他拓展網(wǎng)絡(luò)信息在內(nèi)的各類網(wǎng)絡(luò)狀態(tài)信息。

上述研究均是在SDN控制器部署位置確定的前提下,圍繞網(wǎng)絡(luò)東西向接口中的信息交互需求,進(jìn)行相關(guān)標(biāo)準(zhǔn)與協(xié)議設(shè)計(jì)。在SDN多控制器部署問題研究方面, SDN中控制器部署問題首次在文獻(xiàn)[12]中被正式提出,在指出SDN中控制器部署問題是“NP難”問題的同時(shí),Heller等[12]分別研究了平均和最大網(wǎng)絡(luò)域內(nèi)時(shí)延在不同控制器部署位置下產(chǎn)生的不同影響,但該研究未對(duì)域間時(shí)延和可靠性等因素進(jìn)行考慮。在Heller等[12]研究的基礎(chǔ)上,后續(xù)研究人員相繼對(duì)控制器部署問題中網(wǎng)絡(luò)未知流的安裝時(shí)間、多個(gè)控制器之間的負(fù)載均衡、控制網(wǎng)絡(luò)的可靠性等指標(biāo)因素進(jìn)行了大量研究。文獻(xiàn)[13-14]以負(fù)載均衡為關(guān)鍵指標(biāo),搭建了基于帕累托最優(yōu)的彈性控制器部署框架來進(jìn)行控制器部署。該框架在設(shè)計(jì)中雖然從控制器與底層交換節(jié)點(diǎn)兩個(gè)方面考慮了網(wǎng)絡(luò)時(shí)延對(duì)控制器部署位置和網(wǎng)絡(luò)性能的影響,但由于沒有將整個(gè)SDN劃分為相對(duì)獨(dú)立的網(wǎng)絡(luò)控制域,導(dǎo)致不能有效地進(jìn)行網(wǎng)絡(luò)狀態(tài)信息的域間隔離,增加了網(wǎng)絡(luò)廣播風(fēng)暴發(fā)生的可能。文獻(xiàn)[15]僅在控制器部署過程中,將域間時(shí)延作為網(wǎng)絡(luò)整體時(shí)延的內(nèi)部因素而有所提及,而對(duì)具體域間時(shí)延對(duì)控制器部署的影響未做專門分析,且沒有考慮可靠性問題。文獻(xiàn)[16]以SDN/legacy混合網(wǎng)絡(luò)為研究對(duì)象,以網(wǎng)絡(luò)可靠性、流建立時(shí)間和控制器負(fù)載均衡為目標(biāo),基于Steiner樹對(duì)控制器處理延遲和控制器間網(wǎng)絡(luò)狀態(tài)同步時(shí)延進(jìn)行了建模,提出了一種基于遺傳算法(genetic algorithm, GA)的啟發(fā)式算法來計(jì)算控制器部署問題的帕累托最優(yōu)解集。文獻(xiàn)[17]將控制器部署問題按照控制域劃分、控制器數(shù)量確定、控制器部署位置選擇和最少備份數(shù)量的確定計(jì)算4個(gè)階段進(jìn)行建模,提出了一種面向高可靠性需求的控制器部署方案,然而其僅考慮了控制器之間的時(shí)延,沒有綜合考慮控制器的可靠性和域間效能對(duì)SDN整體性能的影響。

除了控制器與控制器之間的時(shí)延、控制器可靠性等域間效能因素,控制器與交換機(jī)時(shí)延、控制路徑的可靠性與各控制器的負(fù)載均衡也是需要重點(diǎn)考慮的關(guān)鍵指標(biāo),更是控制器部署問題研究的重點(diǎn)和熱點(diǎn)方向。文獻(xiàn)[18]以平衡控制器之間的負(fù)載、降低網(wǎng)絡(luò)控制時(shí)延為目標(biāo),提出一種支持隨網(wǎng)絡(luò)情況動(dòng)態(tài)調(diào)整的控制器部署策略。文獻(xiàn)[19]在考慮網(wǎng)絡(luò)負(fù)載均衡和控制器與交換機(jī)間的傳播時(shí)延的情況下,提出一種基于效率區(qū)間的負(fù)載均衡優(yōu)化算法,以解決控制器部署問題。上述研究?jī)H僅考慮了控制器與底層交換節(jié)點(diǎn)之間的傳播時(shí)延,對(duì)控制網(wǎng)絡(luò)的其他性能因素沒有考慮。文獻(xiàn)[20]僅從最差網(wǎng)絡(luò)控制時(shí)延的角度,研究了不同控制器部署策略對(duì)控制器負(fù)載和對(duì)未知流的響應(yīng)時(shí)間的影響,而沒有考慮平均網(wǎng)絡(luò)時(shí)延和可靠性情況。文獻(xiàn)[21]提出可通過評(píng)價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)的效能和路徑質(zhì)量,將其作為控制器部署位置選擇的衡量指標(biāo),但未考慮網(wǎng)絡(luò)控制時(shí)延指標(biāo)。文獻(xiàn)[22-23]分別通過建立網(wǎng)絡(luò)的可靠性模型,提出了控制器可靠部署算法,但均未考慮控制器負(fù)載和網(wǎng)絡(luò)時(shí)延指標(biāo)。文獻(xiàn)[24]在假定底層網(wǎng)絡(luò)節(jié)點(diǎn)故障率已知的情況下,建立了一種具有一定故障恢復(fù)能力的控制器部署模型,卻對(duì)時(shí)延、負(fù)載等因素沒有考慮。

在算法設(shè)計(jì)與選擇上,常用的算法有貪心算法、隨機(jī)部署(random deployment,RD)算法、聚類算法和啟發(fā)式算法。其中,文獻(xiàn)[12,17,19]提出用貪心算法進(jìn)行控制器部署問題求解,即選擇在當(dāng)前看來時(shí)延最小和負(fù)載最為均衡的位置進(jìn)行控制器部署,得到某種意義上的局部較優(yōu)解空間,由于該算法缺乏對(duì)解空間的全局考慮,導(dǎo)致策略的全局尋優(yōu)性能不佳。文獻(xiàn)[22-25]均提出了RD算法,即從底層交換節(jié)點(diǎn)中依照特定規(guī)則“隨機(jī)地”選取特定節(jié)點(diǎn),在滿足控制器的額定負(fù)載限制的情況下,實(shí)現(xiàn)控制器部署。該算法計(jì)算量較小,但受考慮因素所限,其在網(wǎng)絡(luò)整體性能上表現(xiàn)較差。常用的聚類算法有K-Center聚類算法、K-Means聚類算法、譜聚類算法等,其中文獻(xiàn)[26-27]將K-Means聚類算法引入控制器部署問題,但是囿于聚類算法局限,僅能依據(jù)距離因素進(jìn)行控制器部署位置探索,而沒有考慮負(fù)載、可靠性等其他因素。文獻(xiàn)[28]提出了一種改進(jìn)譜聚類算法進(jìn)行控制器均衡部署的策略,從節(jié)點(diǎn)連接度角度對(duì)域內(nèi)時(shí)延和可靠性進(jìn)行優(yōu)化。在控制器部署問題研究中,啟發(fā)式算法因具備直觀的計(jì)算思路和較高的計(jì)算效率而被廣泛應(yīng)用。目前,常用的啟發(fā)式算法有模擬退火算法[13-14]、GA[15-16,18,29]算法、細(xì)菌覓食算法[20]、粒子群算法[30-31]等。文獻(xiàn)[32-33]通過分析對(duì)比發(fā)現(xiàn),文獻(xiàn)[34]提出的麻雀搜索算法(sparrow search algorithm, SSA)相比其他啟發(fā)式優(yōu)化算法具備更好的尋優(yōu)能力,本文通過構(gòu)建相應(yīng)模型,將SSA引入控制器部署問題求解,并借鑒文獻(xiàn)[35]的反向?qū)W習(xí)(opposite learning, OL)策略對(duì)標(biāo)準(zhǔn)SSA進(jìn)行優(yōu)化,提出了具有較強(qiáng)全局尋優(yōu)能力的兩階段控制器均衡部署策略。

1 問題描述與模型構(gòu)建

對(duì)于底層交換網(wǎng)絡(luò)G(S,E),其定義如下所示:

(1)

式中:S為節(jié)點(diǎn)集合;sn表示第n個(gè)交換機(jī)節(jié)點(diǎn),E為網(wǎng)絡(luò)G的鏈路集,且eij表示第i個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)和第j個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈路;Gcut表示對(duì)網(wǎng)絡(luò)G進(jìn)行的控制域劃分,k表示劃分的控制域的數(shù)量,即控制器數(shù)量。C為控制器集合,控制域Gj的控制器用cj表示。在進(jìn)行控制域劃分時(shí),為兼顧SDN域間和域內(nèi)性能,考慮的因素分別有:網(wǎng)絡(luò)總平均控制時(shí)延、控制網(wǎng)絡(luò)總體可靠性度量、控制器的負(fù)載均衡情況和網(wǎng)絡(luò)評(píng)價(jià)模型。

1.1 網(wǎng)絡(luò)總平均控制時(shí)延

網(wǎng)絡(luò)總平均控制時(shí)延包括域內(nèi)時(shí)延和域間時(shí)延,其中域內(nèi)時(shí)延指控制器與其控制域內(nèi)交換機(jī)之間的時(shí)延,主要是指從交換機(jī)發(fā)送PACKET-IN報(bào)文到交換機(jī)收到相應(yīng)流表所經(jīng)歷的時(shí)間。域間時(shí)延是指控制器與控制器之間的時(shí)延,如前所述,域間時(shí)延對(duì)網(wǎng)絡(luò)全局視圖更新、網(wǎng)絡(luò)可擴(kuò)展性、網(wǎng)絡(luò)拓?fù)渫降染哂兄匾饬x。因此,定義網(wǎng)絡(luò)平均控制時(shí)延如下所示:

(2)

1.2 控制網(wǎng)絡(luò)可靠性

SDN通過OpenFlow等南北向接口協(xié)議,在控制器和交換機(jī)之間維護(hù)專門網(wǎng)絡(luò),用于控制信息傳輸,形成SDN控制網(wǎng)絡(luò),可以說SDN控制網(wǎng)絡(luò)就是由控制節(jié)點(diǎn)和控制路徑組成的網(wǎng)絡(luò)。本文分別用SDN控制器的可靠性和SDN控制路徑的可靠性度量整個(gè)SDN控制網(wǎng)絡(luò)的可靠性。

控制節(jié)點(diǎn)的可靠性用復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的平均聚集系數(shù)來表示?？刂乒?jié)點(diǎn)的平均聚集系數(shù)是指該節(jié)點(diǎn)的相鄰節(jié)點(diǎn)之間仍存在直連路徑的概率,該參數(shù)用來描述SDN控制網(wǎng)絡(luò)中各節(jié)點(diǎn)的局部聚集特性。平均聚集系數(shù)越大,說明當(dāng)某條控制鏈路出現(xiàn)故障時(shí),該節(jié)點(diǎn)可選擇的恢復(fù)路徑也較多,即該節(jié)點(diǎn)的可靠性越高。

定義 2控制節(jié)點(diǎn)Cj的聚集系數(shù)(CLj)。其中,假設(shè)節(jié)點(diǎn)j的kj個(gè)鄰居節(jié)點(diǎn)之間存在Ej條邊,其定義如下:

(3)

SDN中各交換機(jī)節(jié)點(diǎn)因個(gè)體差異而具有不同的故障概率,導(dǎo)致各控制域的故障概率隨著控制器部署位置選擇的不同而不同,并最終對(duì)整個(gè)控制網(wǎng)絡(luò)的可靠性產(chǎn)生影響。本文在網(wǎng)絡(luò)各節(jié)點(diǎn)發(fā)生故障的概率已定的情況下,分別定義控制域和控制網(wǎng)絡(luò)可靠性。

定義 3控制域可靠性(RGj),表示控制域Gj中信息到達(dá)率的可靠性度量,定義為

(4)

式中:Rij表示控制域Gj中,節(jié)點(diǎn)si到控制器cj的控制路徑的信息可達(dá)率,即控制路徑的可靠性;Rk表示節(jié)點(diǎn)sk到控制器cj的路徑可達(dá)率;Pij表示交換機(jī)節(jié)點(diǎn)si到控制器cj的控制路徑。

定義 4控制網(wǎng)絡(luò)可靠度(Rtotal)。SDN可劃分為多個(gè)控制域,本文在控制節(jié)點(diǎn)聚集系數(shù)和控制域可靠性的基礎(chǔ)上,將各控制域可靠度之和與控制節(jié)點(diǎn)聚集系數(shù)之和定義為控制網(wǎng)絡(luò)可靠度,作為全網(wǎng)的可靠性度量,其定義如下所示:

(5)

1.3 負(fù)載均衡度

本文參考文獻(xiàn)[15]的分析結(jié)果,用控制器處理cj流經(jīng)的未知數(shù)據(jù)流數(shù)量RNj作為其負(fù)載的度量?？刂破髫?fù)載均衡度(balance-loading, BL)表示SDN中所有控制器的整體負(fù)載均衡度,BL值越小,說明各控制器的負(fù)載越趨于均衡,如下所示:

(6)

式中:τ、ξ為權(quán)重參數(shù)。BL1和BL2的定義分別如式(7)和式(8)所示,其中RNmean表示控制器負(fù)載的均值。為使BL值能較為全面地反映各控制器的負(fù)載均衡度,本文用BL1和BL2兩個(gè)參數(shù),從負(fù)載差額和方差兩個(gè)角度對(duì)控制器負(fù)載均衡度進(jìn)行度量。

(7)

(8)

(9)

定義 5控制器cj的負(fù)載率(ηj)。控制器的負(fù)載率是RNj與其額定負(fù)載Ωj的比例,其定義如式(10)所示。其中,ηthr為負(fù)載率的閾值,該值是判斷當(dāng)前控制域是否合理并進(jìn)行重新劃分的界限標(biāo)準(zhǔn)。ηj決定控制器是否對(duì)PACKET_IN報(bào)文進(jìn)行排隊(duì)處理。

(10)

1.4 控制器部署模型

1.4.1 控制器域間效能評(píng)價(jià)指標(biāo)與模型

(11)

QCT+QCL+QBL=1

(12)

0≤QCT,QCL,QBL≤1

(13)

控制器評(píng)價(jià)模型,就是在底層交換節(jié)點(diǎn)中,尋找合適的控制器部署位置,使得MCE值達(dá)到最大。為此,建立控制器域間效能評(píng)價(jià)模型為如下帶約束的優(yōu)化評(píng)價(jià)模型:

(14)

(15)

1.4.2 控制網(wǎng)絡(luò)評(píng)價(jià)參考模型

在控制器評(píng)價(jià)模型的基礎(chǔ)上,本文用MDRB來衡量所提控制器部署策略對(duì)控制網(wǎng)絡(luò)的整體控制性能,其值與網(wǎng)絡(luò)總平均時(shí)延Ttotal和控制器負(fù)載均衡度BL成反比,與控制網(wǎng)絡(luò)可靠度Rtotal成正比,表達(dá)式如式(16)所示。其中,網(wǎng)絡(luò)總平均時(shí)延Ttotal是域間效能與域內(nèi)時(shí)延的比例之和。域間效能與域內(nèi)時(shí)延參數(shù)的選擇,在不同應(yīng)用場(chǎng)景下隨網(wǎng)絡(luò)結(jié)構(gòu)、規(guī)模、承載業(yè)務(wù)的不同而不相同。比如,在兩個(gè)典型的SDN應(yīng)用場(chǎng)景——軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)和軟件定義廣域網(wǎng)絡(luò)中,前者由于網(wǎng)絡(luò)規(guī)模比較集中,控制域之間與控制域內(nèi)的網(wǎng)絡(luò)時(shí)延基本接近,其參數(shù)選擇可以分別取α=β=0.5;而后者由于網(wǎng)絡(luò)分布范圍較廣,各控制域之間域間平均控制時(shí)延對(duì)網(wǎng)絡(luò)性能具有較大影響,此時(shí)可適當(dāng)增加域間平均控制時(shí)延在總平均時(shí)延中的比重,降低域內(nèi)時(shí)延的比重,如取α=0.7,β=0.3,以平衡域間時(shí)延在控制器部署中的參考比重,提升控制網(wǎng)絡(luò)的域間效能。

(16)

式中:σ、υ、ω,QT、QB、QR分別是各指標(biāo)因素的比例和量綱平衡系數(shù)。

綜上所述,本文的目的就是通過對(duì)上述模型進(jìn)行計(jì)算,找到一個(gè)控制器部署策略,使得MDRB取得最優(yōu)值。因此,建立如下模型:

(17)

(18)

2 策略描述

針對(duì)上述模型,本文提出一種基于域間效能優(yōu)先的二階段均衡部署策略(two-stage balanced placement strategy, T-SBPS)。該策略分2個(gè)階段:階段1根據(jù)控制器域間效能評(píng)價(jià)模型,以最優(yōu)化控制器域間效能指標(biāo)為目標(biāo),應(yīng)用基于OL的SSA,尋求控制器的最優(yōu)部署位置。由于此階段還未進(jìn)行控制域劃分,不涉及負(fù)載均衡問題,故此時(shí)式(11)中QBL的值為0;階段2進(jìn)入控制域劃分階段,采用貪心策略,根據(jù)控制網(wǎng)絡(luò)評(píng)價(jià)模型,將所有交換節(jié)點(diǎn)部署到各控制器所在控制域,完成交換節(jié)點(diǎn)部署和控制域的劃分,并尋求控制網(wǎng)絡(luò)度量MDRB最大的最優(yōu)解決方案。

2.1 基于OL的SSA

2.1.1 SSA

SSA的總體思想是通過模擬麻雀覓食過程解決最優(yōu)化問題,是由薛建凱等最近提出的新型群體搜索算法。SSA中,將麻雀群體按固定比例分為領(lǐng)導(dǎo)者、追隨者和警戒者3種角色,每個(gè)角色的麻雀位置更新如圖1所示。

圖1 SSA中麻雀位置更新示意圖Fig.1 Sparrows’ position updating schematic diagram in SSA

其中,領(lǐng)導(dǎo)者和追隨者的角色可以相互轉(zhuǎn)化,但其在麻雀種群中所占比例保持不變。SSA的規(guī)則可描述如下:

(1) 領(lǐng)導(dǎo)者通常具有更高能量(更好的適應(yīng)度值),負(fù)責(zé)為所有麻雀種群在更大區(qū)域內(nèi)搜尋最佳“食物”,并向其他追隨者提供覓食方向。相比追隨者,領(lǐng)導(dǎo)者具有更大的覓食區(qū)域。領(lǐng)導(dǎo)者在每次覓食過后,按照式(19)所示更新自身位置:

(19)

(2) 追隨者 “監(jiān)視”領(lǐng)導(dǎo)者,并在領(lǐng)導(dǎo)者找到最佳食物后,爭(zhēng)奪該食物,或者在最佳食物附近覓食,其依照下式進(jìn)行位置更新:

(20)

(3) 警戒者負(fù)責(zé)搜尋過程的警戒,若發(fā)現(xiàn)捕食者,警戒者則向其他麻雀發(fā)出警戒。其他麻雀在收到警戒信息后,移動(dòng)到更加安全的區(qū)域覓食。SSA中,警戒者的初始位置隨機(jī)產(chǎn)生,在發(fā)現(xiàn)捕食者后,其位置更新依照下式進(jìn)行:

(21)

2.1.2 OLSSA

雖然標(biāo)準(zhǔn)SSA相較于其他群智能優(yōu)化算法具有較好的尋優(yōu)效果,但大量研究表明,傳統(tǒng)群智能優(yōu)化算法均存在在處理多模態(tài)優(yōu)化問題時(shí)易陷入局部最優(yōu)陷阱、迭代后期容易出現(xiàn)尋優(yōu)速度過慢等問題。同樣,標(biāo)準(zhǔn)SSA通常隨機(jī)生成初始種群,而后采用迭代方法逐步向全局最優(yōu)解逼近,若初始種群離全局最優(yōu)解很近,算法能很快達(dá)到全局最優(yōu)解。反之,若初始種群距離全局最優(yōu)解較遠(yuǎn),就極可能使算法陷入局部最優(yōu)陷阱,如圖2所示。

圖2 無反向種群的SSA尋優(yōu)過程Fig.2 Optimization searching process of SSA without reverse population

為克服上述不足,本文借鑒文獻(xiàn)[35]提出的OL思想,將OL機(jī)制引入標(biāo)準(zhǔn)SSA,形成OLSSA算法,通過在原始種群中加入式(22)定義反向個(gè)體:

(22)

OLSSA算法使種群從正、反兩個(gè)方向進(jìn)行全局最優(yōu)解搜尋,擴(kuò)大了種群搜索空間,增加了發(fā)現(xiàn)潛在最優(yōu)解的幾率,防止因初始種群距最優(yōu)解較遠(yuǎn)、算法易陷入局部最優(yōu)的問題,進(jìn)而提高了標(biāo)準(zhǔn)SSA的全局尋優(yōu)能力,如圖3所示。

圖3 加入反向種群的SSA尋優(yōu)過程Fig.3 Optimization searching process of SSA with reverse population

2.2 控制器部署策略

基于OLSSA,T-SBPS中的階段1首先進(jìn)行條件初始化:確定算法迭代次數(shù)、種群數(shù)量、解空間維數(shù)(控制器數(shù)量)、領(lǐng)導(dǎo)者及捕食者所占種群比例等參數(shù),隨機(jī)生成初始部署位置,得到原始種群。而后,通過OL機(jī)制、利用式(22)在原始種群中加入反向種群,與原始種群共同形成初始種群,并按固定比例劃分種群中的捕食者、追隨者和警戒者角色。而后,按照式(11)計(jì)算初始目標(biāo)值MCE,并對(duì)初始目標(biāo)值進(jìn)行排序,選擇出初始最優(yōu)目標(biāo)值。而后,由領(lǐng)導(dǎo)者搜尋最優(yōu)解,在搜尋過程中,按照式(11)計(jì)算目標(biāo)值,并按照式(19)更新位置;再由追隨者進(jìn)行搜尋,并依照式(20)判斷最優(yōu)解或更新搜索位置;警戒者在領(lǐng)導(dǎo)者和追隨者的搜索過程中進(jìn)行警戒,并依據(jù)式(21)更新搜索位置。追隨者在完成搜尋后,計(jì)算最終適應(yīng)度值并判斷是否滿足退出條件,若滿足則退出,否則繼續(xù)進(jìn)行下一輪搜索,如此迭代至最大迭代次數(shù),此時(shí)目標(biāo)值對(duì)應(yīng)的種群即為控制器所需部署的位置。階段1的控制器部署策略流程如圖4所示。

圖4 階段1的控制器部署策略流程Fig.4 Flowchart of the controller placement strategy of stage 1

在獲取控制器部署位置后,進(jìn)入階段2,即控制域劃分階段,本文運(yùn)用貪心策略進(jìn)行控制域劃分,對(duì)于每一個(gè)非控制器部署位置的交換機(jī)節(jié)點(diǎn),依據(jù)式(17)計(jì)算該節(jié)點(diǎn)到各控制器的目標(biāo)值MDRB,選擇MDRB值較大的控制器,并將當(dāng)前節(jié)點(diǎn)部署至該控制器的控制域中,如此反復(fù),直至所有節(jié)點(diǎn)完成部署。階段2的流程圖如圖5所示。

圖5 階段2控制器部署策略流程Fig.5 Flowchart of the controller placement strategy of stage 2

根據(jù)上述流程,2階段控制器均衡部署策略的偽代碼如下所示。其中,行(1)～行(2)進(jìn)行初始化,隨機(jī)生成原始種群,行(3)在初始種群中加入反向種群,形成算法的初始種群,行(5)～行(23)表示階段1的控制器部署位置選取過程,行(6)～行(7)分別進(jìn)行初始種群目標(biāo)值的計(jì)算并選取最優(yōu)目標(biāo)值,行(8)～行(10)、行(11)～行(13)、行(14)～行(16)分別表示領(lǐng)導(dǎo)者、追隨者、警戒者進(jìn)行搜尋(警戒)的過程,行(17)～行(20)表示對(duì)完成本輪搜尋并移位的種群計(jì)算新目標(biāo)值,而后比較、選擇當(dāng)前最優(yōu)目標(biāo)值對(duì)應(yīng)的種群。行(24)～行(30)表示在所得控制器部署位置的前提下,進(jìn)行階段2控制域劃分的過程。其中,行(25)～行(26)依次從交換機(jī)節(jié)點(diǎn)集合S中選取一個(gè)非控制器部署位置的交換節(jié)點(diǎn)s,行(27)～行(33)計(jì)算最大目標(biāo)值,返回對(duì)應(yīng)控制器序號(hào),并將s并入目標(biāo)最大的控制域,同時(shí)在S中移除s節(jié)點(diǎn),直至S為空。至此,全網(wǎng)控制域的劃分階段結(jié)束。

算法 1 T-SBPS策略流程輸入:G(S,E),控制器個(gè)數(shù)k,各額定負(fù)載等網(wǎng)絡(luò)基本參數(shù)。輸出:控制器部署位置集合C,控制域Gcut、MDRB值。(1) 初始化控制參數(shù):分別設(shè)置控制域Gcut,控制器數(shù)量K,種群個(gè)體大小POP_SIZE,最大進(jìn)化次數(shù)MaxInteration,領(lǐng)導(dǎo)者、追隨者、警戒者所占比例PF、PA、PL。 (2) controllers=randomInitialize(K,POP_SIZE);(3) oppositePoints=oppositeLearning(controllers); ∥生成反向種群(4) controllers=putInC(oppositePoints); ∥原始種群加入反向種群(5) while iteration

(10) end for(11) for j= PLNumber+1:POP_SIZE ∥追隨者執(zhí)行搜索(12) newControllers=FollowersSearch();(13) end for(14) for j=1:PANumberr ∥警戒者進(jìn)行警戒(15) newControllers=AlertersSearch();(16) end for(17) new MCE=getMCE(newControllers); ∥計(jì)算新的目標(biāo)值(18) GBestMCE=getBestMCE(GBestMCE, new MCE);∥比較并選擇(19) GBestControllers=getBestControllers(GBest-MCE,…(20) newControllers); ∥選擇最優(yōu)目標(biāo)值對(duì)應(yīng)的種群(21) iteration++;(22) end while(23) return GBestControllers; ∥階段1結(jié)束(24) while S≠ ∥階段2:控制域劃分(25) choose s from S ∥選取一個(gè)交換機(jī)節(jié)點(diǎn)(26) if s? GBestControllers ∥根據(jù)式(17)計(jì)算目標(biāo)值(27) temp MDRBs=calcMDRB(s, GBestControllers); (28) [best MDRB,bestIndex]=chooseBestMDRB(temp MDRBs);∥將s并入目標(biāo)最大的控制域(29) Gcut[ GBestControllers [bestIndex] ] <<-s; (30) S=S-s; ∥移除s節(jié)點(diǎn)(31) else ∥若s為控制器(32) continue;(33) end while ∥階段2結(jié)束(34) return GBestControllers、Gcut∥程序結(jié)束,返回控制器及控制域

3 實(shí)驗(yàn)仿真及結(jié)果分析

3.1 實(shí)驗(yàn)條件設(shè)置

本文的實(shí)驗(yàn)仿真主要依托Matlab進(jìn)行,模擬網(wǎng)絡(luò)由系統(tǒng)隨機(jī)生成,共包含80個(gè)交換節(jié)點(diǎn),604條網(wǎng)絡(luò)直連路徑,分布在距離為2 500 km的規(guī)則區(qū)域內(nèi)(如圖6(a)所示)。實(shí)驗(yàn)中,分別假設(shè)到達(dá)交換機(jī)的未知流數(shù)量、控制器額定負(fù)載、節(jié)點(diǎn)可靠度、網(wǎng)絡(luò)傳輸帶寬等參數(shù)如文獻(xiàn)[36]所示。

在SSA變量初始化方面,設(shè)定最大迭代次數(shù)Maxiteration=15,種群大小POP_SIZE=10,領(lǐng)導(dǎo)者所占比例PL=0.3,追隨者所占比例PF=0.7,警戒者所占比例PA=0.1。

3.2 仿真結(jié)果與分析

如前所述,在控制器部署問題解決中,常用的策略有貪心策略、RD策略、聚類策略和啟發(fā)式策略,本文為對(duì)比各算法性能,分別從上述4類策略中選取具有代表性的RD策略[22-25]、K-Means聚類部署策略[26-27]和GA部署策略[15-16]與T-SBPS進(jìn)行比較,對(duì)比不同部署策略對(duì)SDN性能的影響。其中,T-SBPS分為OLSSA-GRE和SSA-GRE,分別表示階段1采用OLSSA算法、階段2采用文獻(xiàn)[12]所提貪心策略和階段1采用SSA算法、階段2采用貪心策略進(jìn)行控制器部署和控制域劃分的操作。

圖6(b)～圖6(f)為當(dāng)控制器數(shù)量為4、式(11)中參數(shù)分別為QCT=0.7、QCL=0.3、QBL=0時(shí),通過不同策略對(duì)原始模擬網(wǎng)絡(luò)圖圖6(a)進(jìn)行控制器部署和控制域劃分的結(jié)果,劃分后圖中各控制域分別用不同顏色表示,控制器部署位置用相應(yīng)顏色的“★”表示,編號(hào)用紅色標(biāo)出。其中圖6(b)、圖6(c)均為T-SBPS進(jìn)行控制器部署的結(jié)果,不同的是圖6(b)在階段1采用OLSSA算法,圖6(c)采用了標(biāo)準(zhǔn)SSA算法。而圖6(d)、圖6(e)、圖6(f)分別為采用RD策略、GA部署策略、K-Means聚類部署策略所得效果?？梢钥闯?圖6(b)、圖6(c)由于采用T-SBPS在階段1以控制器間時(shí)延和控制器聚集系數(shù)為優(yōu)化目標(biāo),因此所得控制器部署位置較其他策略更為集中。同時(shí),由于沒有將域內(nèi)時(shí)延作為優(yōu)先考慮因素,因此采用T-SBPS進(jìn)行控制域劃分時(shí),域內(nèi)交換機(jī)地理分布遠(yuǎn)不如以域內(nèi)距離優(yōu)先的K-Means策略集中。

圖6 仿真網(wǎng)絡(luò)及部署效果Fig.6 Simulation network and placement results

圖7顯示了T-SBPS策略下階段1兩種策略的尋優(yōu)表現(xiàn),可以看出相較于SSA,OLSSA無論在尋優(yōu)速度還是最優(yōu)解的全局屬性表現(xiàn)上均優(yōu)于SSA,說明了在采用OL思想后,在標(biāo)準(zhǔn)SSA的原始種群中加入反向種群,確實(shí)進(jìn)一步增強(qiáng)了標(biāo)準(zhǔn)SSA的尋優(yōu)速度和尋優(yōu)能力,證明了OL策略對(duì)標(biāo)準(zhǔn)SSA的有效性。

不同部署策略的指標(biāo)對(duì)比如圖8～圖13所示,如前文所述,RD是在滿足負(fù)載率限制的情況下隨機(jī)選取控制器并隨機(jī)進(jìn)行交換機(jī)控制域劃分的部署策略。GA是在滿足負(fù)載率限制的情況下,采用GA對(duì)控制網(wǎng)絡(luò)評(píng)價(jià)模型進(jìn)行優(yōu)化得到的相應(yīng)的部署結(jié)果。K-Means聚類布署策略主要采用復(fù)雜網(wǎng)絡(luò)聚類的方法進(jìn)行控制器部署?？梢钥闯?SSA-GRE策略和OLSSA-GRE策略采用二階段的部署思路,既考慮了域間效能優(yōu)先,又在第2階段考慮了域內(nèi)時(shí)延、控制路徑可靠性和控制器負(fù)載的整體性能,因此T-SBPS策略,尤其是在階段1經(jīng)過OL策略優(yōu)化的OLSSA-GRE策略在域內(nèi)平均時(shí)延以外的控制器域間效能、域間時(shí)延、網(wǎng)絡(luò)整體可靠性負(fù)載均衡度和MDRB度量指標(biāo)上均具有一定優(yōu)勢(shì)。

不同策略所得部署方式對(duì)應(yīng)的SDN域間時(shí)延表現(xiàn)如圖8所示?？梢钥闯?除了在個(gè)別奇點(diǎn)處RD策略搜尋到比其他算法更優(yōu)的結(jié)果,采用T-SBPS策略的OLSSA-GRE策略和SSA-GRE策略經(jīng)過階段1專門進(jìn)行了域間平均時(shí)延優(yōu)化,因此所得方案的可靠度比不以控制器域間效能為考慮因素的RD、GA、K-Means部署策略分別低14.12%、15.3%和25.56%。

圖8 域間時(shí)延對(duì)比Fig.8 Comparison of inter-controllers delay

圖9顯示了各算法的控制器域間效能指標(biāo)對(duì)比,可以看出,由于在階段1專門就控制器效能進(jìn)行了優(yōu)化,因此,與其他策略相比,采用SSA和OLSSA算法的T-SBPS在控制器域間效能上比其他策略更高。在T-SBPS內(nèi)部比較上,由于加入了反向種群,OLSSA-GRE較SSA-GRE具有更為廣泛的尋優(yōu)范圍,所得控制器域間效能也較標(biāo)準(zhǔn)SSA略高。

圖9 控制器域間效能對(duì)比Fig.9 Comparison of inter-domain performance of the controller

在域內(nèi)平均時(shí)延(見圖10)方面,可以看出,主要根據(jù)控制路徑距離作為評(píng)判標(biāo)準(zhǔn)的K-Means聚類布署策略在域內(nèi)平均時(shí)延表現(xiàn)上要明顯優(yōu)于沒有以域內(nèi)時(shí)延優(yōu)先的T-SBPS策略。 SSA-GRE策略和OLSSA-GRE策略由于在交換機(jī)控制域劃分階段均采用了貪心策略,所以兩者域內(nèi)平均時(shí)延大小較為相近,均差約為1%,而RD算法的域內(nèi)平均時(shí)延最大,比OLSSA-GRE策略高出近17.35%?？梢钥闯?T-SBPS策略在確保域間效能優(yōu)先的情況下,也能在一定程度上對(duì)域內(nèi)時(shí)延給予考慮,確保了SDN整體性能的平衡。

在可靠性指標(biāo)(見圖11)方面,本文用控制器聚類系數(shù)和控制網(wǎng)絡(luò)可靠度定義了保證域間可靠度優(yōu)先情況下的SDN控制網(wǎng)絡(luò)整體可靠性指標(biāo)。可以看出,T-SBPS的2階段部署策略在第1階段對(duì)控制器的域間可靠性進(jìn)行了尋優(yōu),導(dǎo)致其網(wǎng)絡(luò)整體可靠度均值較單純對(duì)域內(nèi)可靠度進(jìn)行考量的RD、GA和K-Means策略分別高出1.43%、0.9%和0.94%。而在T-SBPS內(nèi)部,得益于加入反向種群后算法較高的尋優(yōu)能力,在階段1采用OL策略的OLSSA-GRE策略較沒有采用OL策略的SSA-GRE策略所得部署方案具有更高的可靠性。

圖11 可靠性指標(biāo)對(duì)比Fig.11 Comparison of reliability

圖12顯示了不同策略所得部署方案在負(fù)載均衡指標(biāo)方面的表現(xiàn)?？梢钥闯?由于負(fù)載均衡度的定義包含了均方及方差取值,導(dǎo)致其相較于其他指標(biāo)波動(dòng)幅度更大、頻率更高。在指標(biāo)對(duì)比方面,在階段2采用貪心策略對(duì)包括控制器負(fù)載均衡在內(nèi)的各個(gè)指標(biāo)進(jìn)行了專門優(yōu)化,因此采用OLSSA-GRE和SSA-GRE的T-SBPS所得部署方式的各控制器負(fù)載更為均衡。

圖12 負(fù)載均衡度對(duì)比Fig.12 Comparison of load-balancing index

圖13為MDRB度量對(duì)比,在其他策略方面,主要為基于MDRB最優(yōu)值考慮的GA部署策略,由于缺乏對(duì)時(shí)延、可靠性和負(fù)載的針對(duì)性的全局考慮,導(dǎo)致其相較其他算法在各個(gè)指標(biāo)上較為平均。而在采用隨機(jī)部署的RD策略時(shí),由于在控制器選取和控制域劃分過程中只考慮控制器負(fù)載限制因素,因此其各指標(biāo)表現(xiàn)均不及其他策略。綜上,T-SBPS策略在各分項(xiàng)指標(biāo)上的優(yōu)勢(shì)最終在網(wǎng)絡(luò)整體衡量指標(biāo)MDRB上得以體現(xiàn):OLSSA-GRE策略所得度量值較RD、GA和K-Means策略所得度量值均值分別高28.95%、12.39%和7.68%,說明T-SBPS策略在進(jìn)行控制器部署的過程中,在優(yōu)先考慮域間時(shí)延的情況下,在網(wǎng)絡(luò)的時(shí)延、可靠性和負(fù)載均衡度上具備優(yōu)勢(shì)。

圖13 MDRB度量對(duì)比Fig.13 Comparison of MDRB performance

4 結(jié)束語

本文針對(duì)SDN中的多控制器部署問題,分析了東西向接口在SDN中的重要作用,研究了面向東西向接口的域間效能對(duì)控制器部署方案和網(wǎng)絡(luò)性能的影響,并基于控制器域間效能相關(guān)定義,建立了控制器域間效能和控制網(wǎng)絡(luò)評(píng)價(jià)參考模型,在運(yùn)用SSA對(duì)模型進(jìn)行最優(yōu)化求解后,區(qū)分問題的不同階段,形成了一種域間效能優(yōu)先的控制器部署策略T-SBPS。同時(shí),通過引入OL策略,對(duì)SSA進(jìn)行了優(yōu)化改進(jìn),進(jìn)一步擴(kuò)大了初始種群尋優(yōu)范圍,有效提升了算法尋優(yōu)性能。仿真結(jié)果表明,所提策略在確保域間效能優(yōu)先的情況下,有效降低了網(wǎng)絡(luò)時(shí)延,提高了控制網(wǎng)絡(luò)可靠性,為面向服務(wù)質(zhì)量的SDN應(yīng)用提供了可靠保障。下一步,將圍繞控制網(wǎng)絡(luò)評(píng)價(jià)參考模型中域間效能與域內(nèi)時(shí)延之間參數(shù)的選擇進(jìn)行研究,使網(wǎng)絡(luò)的整體性能指標(biāo)更加趨于平衡。