基于可靠性與負(fù)載優(yōu)化的多控制器彈性部署算法

陸 , ,

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,鄭州 450002)

0 概述

隨著軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)[1]的引入,傳統(tǒng)網(wǎng)絡(luò)中邏輯集中式架構(gòu)開始朝著控制和數(shù)據(jù)平面分離的方向轉(zhuǎn)變,這種轉(zhuǎn)變能夠方便網(wǎng)絡(luò)的管理和維護(hù),因此,受到學(xué)界和工業(yè)界的廣泛關(guān)注。隨著SDN網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大,單個(gè)控制器已經(jīng)難以滿足現(xiàn)有的網(wǎng)絡(luò)需求。為提高網(wǎng)絡(luò)的可拓展性,避免單點(diǎn)失效,研究人員在集中式控制的基礎(chǔ)上提出將網(wǎng)絡(luò)劃分為多個(gè)域,通過部署多個(gè)控制器來實(shí)現(xiàn)邏輯上集中、物理上分布的SDN網(wǎng)絡(luò)[2]。多控制器的部署主要有3個(gè)關(guān)鍵:控制器的部署數(shù)量;控制器的部署位置;交換機(jī)與控制器間的映射關(guān)系,即哪些交換機(jī)由哪些控制器控制。一個(gè)網(wǎng)絡(luò)所需的控制器數(shù)量由實(shí)際場(chǎng)景所決定,因此,本文主要研究和分析控制器的部署位置和交換機(jī)與控制器間的映射關(guān)系。

在實(shí)際中,要實(shí)現(xiàn)控制器的合理部署,會(huì)面臨較多挑戰(zhàn)。控制層的失效概率要滿足特定的要求以保證網(wǎng)絡(luò)的可靠性。同時(shí),要利用控制器的負(fù)載優(yōu)化來保證負(fù)載的合理分配,并減少交換機(jī)到控制器的時(shí)延,以提高網(wǎng)絡(luò)性能。

目前,針對(duì)多控制器部署的研究主要分為兩類:

1)考慮時(shí)延、負(fù)載均衡等因素,通過多目標(biāo)優(yōu)化來求解控制器部署的位置。文獻(xiàn)[3]考慮控制報(bào)文的平均時(shí)延和最差時(shí)延后確定控制器的最佳部署位置。文獻(xiàn)[4]針對(duì)控制器的負(fù)載過大導(dǎo)致時(shí)延顯著增加的問題,提出在滿足控制器負(fù)載均衡的條件下,尋求平均時(shí)延最優(yōu)部署。文獻(xiàn)[5]考慮額外的目標(biāo),如控制器之間的負(fù)載平衡問題,以在不同目標(biāo)相互競(jìng)爭(zhēng)的情況下,在不同的位置選擇之間進(jìn)行權(quán)衡。文獻(xiàn)[6]利用譜分類算法,綜合考慮時(shí)延與容量限制下的多控制器負(fù)載均衡問題,然后提出KCBP(K Controllers Balanced Placement)算法,該算法是基于Normalized Cut的標(biāo)準(zhǔn)化分割方式。文獻(xiàn)[7]在K-means算法的基礎(chǔ)上提出優(yōu)化K-means算法,為避免初始值的選取對(duì)分區(qū)的影響,其使用一種逐步遞進(jìn)分區(qū)的方式。這類方案均以提高網(wǎng)絡(luò)通信質(zhì)量、設(shè)備利用率為目標(biāo),但是忽略了設(shè)備故障對(duì)網(wǎng)絡(luò)的影響。

2)考慮控制器的可靠部署。文獻(xiàn)[8]引入失效路徑百分比來評(píng)價(jià)SDN網(wǎng)絡(luò)的可靠性,并用數(shù)學(xué)方法證明可靠控制器部署(Reliable Controller Placement,RCP)是NP-Hard問題。文獻(xiàn)[9]建立Survivor模型,其考慮路徑連通性、控制器容量和快速恢復(fù)性3個(gè)指標(biāo)。文獻(xiàn)[10]通過分析表明,控制器位置選擇對(duì)SDN網(wǎng)絡(luò)可靠性有重要影響,同時(shí),過多的控制器會(huì)顯著增加運(yùn)營(yíng)成本。這類方案在考慮控制層的可靠性時(shí),沒有考慮數(shù)據(jù)轉(zhuǎn)發(fā)層對(duì)控制層可靠性的影響。由于轉(zhuǎn)發(fā)層和控制層實(shí)際上是復(fù)用同一個(gè)網(wǎng)絡(luò),因此當(dāng)數(shù)據(jù)流量超過鏈路帶寬時(shí),數(shù)據(jù)層的擁塞也會(huì)導(dǎo)致控制層的失效。同時(shí),這類方案僅通過考慮網(wǎng)絡(luò)可靠性指標(biāo)來進(jìn)行控制器部署,其對(duì)于交換機(jī)分配、網(wǎng)絡(luò)時(shí)延等因素缺乏考慮,容易導(dǎo)致控制器負(fù)載失衡。

針對(duì)上述方案存在的不足,本文在譜聚類思想的基礎(chǔ)上,對(duì)控制路徑時(shí)延、控制路徑可靠性和控制器負(fù)載均衡3個(gè)指標(biāo)進(jìn)行描述,提出一種基于可靠性和負(fù)載優(yōu)化的多控制器彈性部署(Multi-Controllers Elastic Placement,MCEP)算法。首先,利用節(jié)點(diǎn)間的相似關(guān)系將網(wǎng)絡(luò)拓?fù)浔硎緸橄嗨凭仃?并將多控制器部署問題轉(zhuǎn)化為相似矩陣的行向量分類問題;然后,采用基于模擬退火的改進(jìn)k-medoids算法對(duì)行向量進(jìn)行分類,以實(shí)現(xiàn)多控制器彈性部署;最后,通過實(shí)驗(yàn)驗(yàn)證該算法的可行性。

1 問題重述與建模

1.1 問題重述

在SDN中,控制器部署位置和交換機(jī)與控制器之間的映射關(guān)系會(huì)對(duì)整個(gè)控制網(wǎng)絡(luò)的可靠性和性能造成影響。圖1所示為在由6個(gè)節(jié)點(diǎn)和2個(gè)控制器組成的SDN網(wǎng)絡(luò)中,3種不同的控制器部署方式對(duì)控制網(wǎng)絡(luò)的影響。其中,實(shí)線表示物理鏈路,虛線表示控制鏈路。

圖1 控制器部署方式對(duì)網(wǎng)絡(luò)性能的影響

圖1(a)、圖1(c)表示相同的控制器部署位置、不同的交換機(jī)與控制器映射關(guān)系對(duì)控制器負(fù)載的影響。從中可以看出,在控制器處理容量相同的情況下,圖1(a)的控制器負(fù)載更均衡。圖1(b)、圖1(c)表示網(wǎng)絡(luò)分區(qū)相同、控制器部署位置不同對(duì)網(wǎng)絡(luò)可靠性的影響。從中可以看出,假如B節(jié)點(diǎn)與C節(jié)點(diǎn)之間的物理鏈路發(fā)生故障,則圖1(c)中有一條控制路徑會(huì)失效,圖1(b)中有2條控制路徑會(huì)失效,即圖1(c)的控制網(wǎng)絡(luò)比圖1(b)更可靠。

基于上述分析,本文所要研究的問題總結(jié)如下:

1)在給定網(wǎng)絡(luò)拓?fù)浜涂刂破鲾?shù)量的情況下,確定控制器的部署位置。

2)確定網(wǎng)絡(luò)中交換機(jī)與控制器間的映射關(guān)系。

1.2 問題建模

將物理網(wǎng)絡(luò)表示為一個(gè)無向圖G(V,E,B)。其中,V是圖中節(jié)點(diǎn)(交換機(jī))的集合,V=(v1,v2,…,vn),|V|表示節(jié)點(diǎn)個(gè)數(shù),E是邊eij的集合,eij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間直連鏈路的長(zhǎng)度,非直連鏈路eij取值為0,B表示直連鏈路eij的帶寬。對(duì)于SDN控制層,控制器的控制路徑可以視為物理網(wǎng)絡(luò)上的覆蓋網(wǎng)絡(luò),如圖1所示。

為解決多控制器部署問題,本文定義如下指標(biāo)。

定義1(控制路徑失效概率(Control Path Failure Probability,CPFP)) 路徑失效可分為2種情況:

2)由于控制路徑實(shí)際上是與物理轉(zhuǎn)發(fā)層使用同一個(gè)網(wǎng)絡(luò),因此轉(zhuǎn)發(fā)層數(shù)據(jù)流量過大會(huì)導(dǎo)致一些鏈路的擁塞,也會(huì)影響控制鏈路的可靠性。假設(shè)直連鏈路eij帶寬為bij,流量為fij,當(dāng)流量處于帶寬允許的范圍內(nèi)時(shí),不會(huì)導(dǎo)致鏈路擁塞,而當(dāng)流量超過一定的閾值時(shí),流量越大,鏈路擁塞程度越高。當(dāng)流量大于帶寬時(shí),則認(rèn)為該鏈路不可用,即擁塞的概率為1。因此,鏈路擁塞的概率可表示為:

其中,δ表示閾值。

綜合考慮物理失效與鏈路擁塞,直連鏈路eij可用概率APij表示為:

?i,j∈n,APij=APji

(4)

式(3)、式(4)表示鏈路可用概率與方向無關(guān)。對(duì)于一條控制路徑Pst,其可用的概率取決于路徑上各條直連鏈路的狀態(tài)。因此,控制路徑失效概率可表示為:

本文采用控制路徑平均失效概率(Control Path Average Failure Probability,CPAFP)對(duì)網(wǎng)絡(luò)的整體可靠性進(jìn)行評(píng)估,其表示為:

定義2(控制路徑時(shí)延(Control Path Delay,CPD))在SDN網(wǎng)絡(luò)中,當(dāng)新流到達(dá)交換機(jī)時(shí),由交換機(jī)交付給控制器處理,該過程會(huì)產(chǎn)生時(shí)延,且時(shí)延對(duì)于SDN網(wǎng)絡(luò)的性能有較大影響。通常情況下,時(shí)延可以分為4個(gè)方面:傳播時(shí)延,處理時(shí)延,排隊(duì)時(shí)延,發(fā)送時(shí)延。對(duì)于廣域網(wǎng)而言,傳播時(shí)延大于其他3種時(shí)延。本文主要進(jìn)行廣域網(wǎng)的SDN研究,因此,使用傳播時(shí)延近似表示網(wǎng)絡(luò)時(shí)延。

控制路徑平均時(shí)延(Control Path Average Delay,CPAD)是所有控制路徑時(shí)延的平均值,可表示為:

定義3(控制器負(fù)載標(biāo)準(zhǔn)差(Controller Load Standard Deviation,CLSD)) 控制器輕載會(huì)導(dǎo)致控制器性能浪費(fèi),而控制器過載時(shí),由于控制器處理性能跟不上流請(qǐng)求速度,從而導(dǎo)致時(shí)延大幅增加,網(wǎng)絡(luò)性能下降。因此,在多控制器位置部署中,需要考慮控制器之間的負(fù)載均衡。

本文將SDN中控制器的負(fù)載視為控制器因管理交換機(jī)而擔(dān)負(fù)的計(jì)算負(fù)載。為論述方便,本文將一個(gè)控制器的負(fù)載視為該控制器所管理的交換機(jī)數(shù)目。控制器負(fù)載差異表示為各控制器實(shí)際管理交換機(jī)數(shù)量的差異,可通過各控制器所管理交換機(jī)數(shù)量的標(biāo)準(zhǔn)差來表示:

基于以上3個(gè)指標(biāo)的定義,低時(shí)延與高可靠的多控制器均衡部署問題即為找到一個(gè)合適的方法,使CPAFP、CPAD、CLSD3個(gè)指標(biāo)均達(dá)到最小。可表示為:

min[CPAFP,CPAD,CLSD]

(10)

s.t.CPFPij

(11)

CPDij

(12)

|SCj|

(13)

式(11)表示控制鏈路失效概率不能高于P,式(12)表示控制鏈路的最差時(shí)延不能高于D,式(13)表示單個(gè)控制器所管理交換機(jī)的個(gè)數(shù)不能多于N。

多控制器均衡部署問題是一個(gè)帶約束的多目標(biāo)優(yōu)化問題,其難以在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解。因此,本文采用譜聚類思想來求解。為實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的合理劃分,在對(duì)圖上的節(jié)點(diǎn)進(jìn)行聚類時(shí),原則上將距離較近的節(jié)點(diǎn)聚為一類。而根據(jù)本文的需求,可以用2個(gè)節(jié)點(diǎn)之間的通信時(shí)延和可靠性來定義節(jié)點(diǎn)距離。此處,本文引入節(jié)點(diǎn)相似度來計(jì)算節(jié)點(diǎn)間的相似程度。

定義4(節(jié)點(diǎn)相似度) 相似度表示2個(gè)節(jié)點(diǎn)相似的程度,相似程度越高,表示2個(gè)節(jié)點(diǎn)歸為一類的可能性越大。對(duì)應(yīng)于本文的路徑可靠性與時(shí)延,任意2個(gè)節(jié)點(diǎn)之間的時(shí)延越小,通信可靠性越大,其相似程度也越大。因此,首先定義包含可靠性和時(shí)延的節(jié)點(diǎn)相似度。因?yàn)镃PEP是取值為(0,1)的概率值,而CPD是一個(gè)具體的數(shù)值,為方便兩者的比較,對(duì)CPD做歸一化處理:

其中,maxCPD表示網(wǎng)絡(luò)中鏈路的最長(zhǎng)時(shí)延,minCPD表示網(wǎng)絡(luò)中鏈路的最短時(shí)延。

當(dāng)2個(gè)節(jié)點(diǎn)之間的鏈路可靠性低于可容忍的可用概率P或時(shí)延超過可容忍的最大時(shí)延D時(shí),將這2個(gè)節(jié)點(diǎn)的相似度設(shè)為0。因此,2個(gè)節(jié)點(diǎn)之間相似度wij表示為:

(15)

其中,α表示時(shí)延與可靠性之間的權(quán)值,當(dāng)0≤α<0.5時(shí),聚類更偏向于可靠性,當(dāng)0.5≤α≤1時(shí),聚類原則上偏向于時(shí)延。由各節(jié)點(diǎn)相似度可以得到表示整個(gè)網(wǎng)絡(luò)拓?fù)涞南嗨贫染仃嘩。

對(duì)于一個(gè)網(wǎng)絡(luò)拓?fù)銰,將其切割為2個(gè)子圖A、B,定義A和B之間的切割為:

由切割的定義可得,若將網(wǎng)絡(luò)拓?fù)淝懈顬閗個(gè)子圖,則最小割可以表示為:

圖2 最小割與比率割的網(wǎng)絡(luò)分區(qū)結(jié)果對(duì)比

基于負(fù)載均衡的考慮,本文采用比率割(RatioCut)作為圖劃分的原則。RatioCut不僅考慮最小化切割Cut,而且考慮最大化每個(gè)子圖節(jié)點(diǎn)的個(gè)數(shù)。RatioCut表示為:

其中,|Ai|表示區(qū)域Ai的節(jié)點(diǎn)個(gè)數(shù)。當(dāng)子圖劃分不均勻時(shí),如某個(gè)區(qū)域只包含很少的節(jié)點(diǎn),則該子圖的|Ai|會(huì)很小,導(dǎo)致總的RatioCut值很大。而整個(gè)圖中的節(jié)點(diǎn)數(shù)是一個(gè)固定值,即|A1|+|A2|+…+|Ak|=|V|,由均值不等式可知,當(dāng)各區(qū)域節(jié)點(diǎn)個(gè)數(shù)趨向均勻時(shí),RatioCut最小。因此,式(18)的求解可以轉(zhuǎn)化為求RatioCut的最小值,即:

argminRatioCut(A1,A2,…,Ak)

(19)

由于W是相似度矩陣,根據(jù)譜理論可知,度矩陣D表示為:

D=diag(d1,d2,…,dk)

(20)

L=D-W

(21)

對(duì)于任意n維向量f=[f1,f2,…,fn],有:

為對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類,需要為每個(gè)節(jié)點(diǎn)賦予一個(gè)向量來指示該節(jié)點(diǎn)的類別。引入指示向量Hn×k=[h1,h2,…,hk]。對(duì)于任意一個(gè)n維向量hi,定義其元素hij為:

式(24)是將網(wǎng)絡(luò)拓?fù)淝蟹殖?個(gè)子圖的結(jié)果,因此,對(duì)于k個(gè)子圖切分的RatioCut,可表示為:

Tr(H′LH)

(25)

因此,求解RatioCut最小值問題就轉(zhuǎn)化為求解矩陣H′LH跡的問題,即:

argmin Tr(H′LH)

s.t.H′H=Ik

(26)

由Rayleigh-Ritz定理[11]可知,若L為實(shí)對(duì)稱矩陣,其特征值λ1≤λ2≤…≤λn,且其對(duì)應(yīng)的特征向量v1,v2,…,vn正交,則:

min Tr(H′LH)=λ1+λ2+…+λk

(27)

其中,最小值對(duì)應(yīng)的矩陣H=[v1,v2,…,vk]。

由于H中向量的取值受到限制條件的影響,其取值是離散的,因此該問題的求解是NP-Hard。為求解該最小值,可將其進(jìn)行松弛。將hij的取值放寬到實(shí)數(shù)范圍[6],則最小實(shí)數(shù)解出現(xiàn)在矩陣L的前k個(gè)最小特征值對(duì)應(yīng)的特征向量組成的矩陣H中。此時(shí),H矩陣由n個(gè)k維行向量組成,其分別表示n個(gè)節(jié)點(diǎn)的k維坐標(biāo),每個(gè)節(jié)點(diǎn)的k維坐標(biāo)分別代表該節(jié)點(diǎn)的k維屬性,越相似的節(jié)點(diǎn),其k維屬性越相近。

在獲得H矩陣后,譜聚類通常采用K-means算法對(duì)k維坐標(biāo)系中的n個(gè)點(diǎn)進(jìn)行分類。由前述推論可知,譜聚類的實(shí)質(zhì)是一個(gè)降維過程,其將n×n維矩陣的分類問題轉(zhuǎn)化為n×k維矩陣的分類問題,通常k<

2 算法描述與分析

2.1 算法描述

針對(duì)現(xiàn)有多控制器部署方案中存在控制路徑可靠性差和控制器負(fù)載不均衡的問題,本文提出一種基于可靠性和負(fù)載優(yōu)化的多控制器彈性部署算法MCEP。MCEP算法基于改進(jìn)的RatioCut算法,并使用模擬退火的k-medoids算法對(duì)其聚類過程進(jìn)行優(yōu)化。MCEP算法的主要改進(jìn)體現(xiàn)在:

1)采用k-medoids代替RatioCut中原有的K-means聚類,將中心點(diǎn)的選取限制在當(dāng)前聚類所包含的數(shù)據(jù)點(diǎn)集合中,防止孤立點(diǎn)對(duì)聚類的影響。

2)初始聚類后,增加一個(gè)模擬退火的調(diào)整步驟,避免陷入局部最優(yōu)。

對(duì)由矩陣Hn×k表示的n個(gè)節(jié)點(diǎn)進(jìn)行分類,任意選取k個(gè)節(jié)點(diǎn),按照k-medoids算法迭代,直至穩(wěn)定,記錄穩(wěn)定狀態(tài)時(shí)的分類結(jié)果并更新最優(yōu)結(jié)果,用式(28)計(jì)算此時(shí)目標(biāo)函數(shù)obj。然后將類中某個(gè)節(jié)點(diǎn)歸入其鄰居節(jié)點(diǎn)的類別,按照k-medoids算法迭代,直至能夠穩(wěn)定計(jì)算目標(biāo)函數(shù)obj,若調(diào)整后,新obj的值減小,則保留調(diào)整之后的結(jié)果作為新的分類,并更新最優(yōu)結(jié)果;若調(diào)整后obj的值增加,則以一定的概率值接受新結(jié)果。同時(shí),按照退火速率降低該概率值。在連續(xù)多次退火后,結(jié)束調(diào)整,以最優(yōu)結(jié)果作為最后的分類結(jié)果,輸出。

MCEP算法具體描述如下:

算法1MCEP算法

輸入控制器個(gè)數(shù)k,權(quán)重值α,鏈路流量矩陣F,離開溫度Tmin,初始溫度Torg,降溫速度r

輸出控制器位置bestVc,交換機(jī)與控制器之間的映射關(guān)系bestSC

1.for each i,j∈V do

2.CPFPst←式(5),CPDij←式(7)

3.end for

4.W←式(16),D←式(20),L=D-W

5.[H]=eigs(L,k),

6.tempVc←initKCenter(H,k),T=Torg

7.調(diào)用k-medoids,得tempVc,tempSC

8.bestVc←Vc←tempVc,bestSC←SC←tempSC

9.while(T>Tmin)

10.隨機(jī)選擇一個(gè)節(jié)點(diǎn),將其歸入鄰居節(jié)點(diǎn)類別;調(diào)用k-medoids,得tempVc,tempSC

11.Δ=obj(tempSC)-obj(SC)

12.if (Δ≤0) SC←tempSC

13.if (obj(SC)

14.bestSC←SC,bestVc←Vc

15.end if

16.else

17.SC←以exp(-Δ/T)的概率將tempSC賦值

18.end if T=T*r

19.end while

20.return bestSC,bestVc

在MCEP算法中:第1行～第5行,得到矩陣L的特征值和特征向量,并從中選取k個(gè)最小特征值對(duì)應(yīng)的特征向量組成矩陣H;第6行～第8行,使用傳統(tǒng)的k-medoids算法對(duì)表示節(jié)點(diǎn)的k維行向量進(jìn)行第一次分類;第9行～第19行表示基于模擬退火對(duì)分類結(jié)果進(jìn)行調(diào)整;第20行輸出最優(yōu)的分類結(jié)果。

2.2 算法復(fù)雜度分析

MCEP算法首先利用Johnson算法[12]計(jì)算任意2點(diǎn)之間的最短路徑,然后通過式(5)和式(7)得到相應(yīng)的CPFP和CPD,其時(shí)間復(fù)雜度為O(V2lgV+VE)。計(jì)算矩陣W、D、L的時(shí)間復(fù)雜度為O(V),計(jì)算特征向量組成的矩陣H,其時(shí)間復(fù)雜度為O(V3),k-medoids算法的時(shí)間復(fù)雜度為O(V2kt),其中,t為k-medoids算法的迭代次數(shù),因?yàn)樵诿看文M退火的步驟中都需調(diào)用k-medoids進(jìn)行分類,所以其調(diào)整時(shí)間為O(V2ktlogr(Tmin/Torg))。因此,MCEP算法總的時(shí)間復(fù)雜度為O(V3+V2logrT)。

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

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

為評(píng)估MCEP算法的有效性和可行性,本文以實(shí)際網(wǎng)絡(luò)拓?fù)銸S3E[13]作為仿真進(jìn)行分析。OS3E拓?fù)浣Y(jié)構(gòu)如圖3所示,其由34個(gè)節(jié)點(diǎn)、42條邊組成。仿真中控制器部署方法使用Matlab模擬實(shí)現(xiàn),實(shí)驗(yàn)機(jī)配置為Intel Core i5 2.4 GHz,8 GB RAM。

圖3 OS3E網(wǎng)絡(luò)拓?fù)?/p>

通常鏈路流量處于動(dòng)態(tài)范圍內(nèi),且每條鏈路的帶寬也并不相同。為使實(shí)驗(yàn)易于實(shí)現(xiàn),在不影響結(jié)果的前提下,假定每條物理鏈路的帶寬bij=50 Mb/s。所有鏈路有相同的流強(qiáng)度,且流量f服從強(qiáng)度為20 Mb/s的泊松分布[14]。鏈路物理失效的概率取決于鏈路材料和外部環(huán)境,在本實(shí)驗(yàn)中,假設(shè)所有的鏈路具有相同的物理失效概率,每100 km失效概率為0.01[15]。

3.2 算法性能分析

實(shí)驗(yàn)1驗(yàn)證在不同參數(shù)設(shè)置下MCEP算法的控制器部署和分區(qū)情況。對(duì)MCEP算法進(jìn)行不同參數(shù)仿真,網(wǎng)絡(luò)劃分和控制器部署結(jié)果如圖4所示。其中,相同的符號(hào)表示處于同一個(gè)子域,黑色實(shí)心符號(hào)表示控制器部署位置。圖4(a)、圖4(b)表示將網(wǎng)絡(luò)分為2個(gè)區(qū)域時(shí),α值不同對(duì)網(wǎng)絡(luò)分區(qū)的影響。其中,α=1表示只考慮鏈路可靠性指標(biāo),此時(shí)長(zhǎng)度較長(zhǎng)的鏈路更有可能被切斷。從圖4(a)、圖4(b)可以看出,盡管時(shí)延和可靠性都與鏈路的長(zhǎng)度相關(guān),但是鏈路失效的概率與鏈路長(zhǎng)度成指數(shù)關(guān)系,而時(shí)延與鏈路長(zhǎng)度成線性關(guān)系。因此,可靠性對(duì)鏈路長(zhǎng)度更敏感。圖4(c)、圖4(d)的參數(shù)分別為k=3,α=0.5和k=4,α=0.5,其分別將網(wǎng)絡(luò)劃分成3個(gè)和4個(gè)區(qū)域,且劃分出的子網(wǎng)大小較均勻。這表明可以通過改變MCEP的參數(shù)來調(diào)整SDN網(wǎng)絡(luò)的可靠性和負(fù)載均衡之間的權(quán)衡關(guān)系。

圖4 不同參數(shù)時(shí)MCEP算法的部署情況

實(shí)驗(yàn)2將MCEP算法與KCBP算法[6]、優(yōu)化的K-means算法[7]在可靠性、時(shí)延與負(fù)載均衡3個(gè)指標(biāo)上進(jìn)行對(duì)比。實(shí)驗(yàn)中MCEP算法的權(quán)重α默認(rèn)取0.5。圖5所示為3種算法的控制路徑可靠性對(duì)比結(jié)果,從中可以看出,隨著控制器個(gè)數(shù)的增加,3種算法的可靠性均有所提高,原因是控制器數(shù)量增加,可以使每個(gè)子域更緊密,從而使可靠性得到提升。但在控制器數(shù)量相同時(shí),MCEP算法的可靠性明顯大于其他2個(gè)算法,與另外2個(gè)算法相比,MCEP算法的可靠性平均提升了17%。

圖5 3種算法控制路徑可靠性對(duì)比結(jié)果

圖6所示為3種算法的平均時(shí)延情況,從中可以看出,隨著控制器數(shù)量的增加,3種算法的控制路徑平均時(shí)延均有所下降。其中,MCEP和KCBP算法在數(shù)值和下降趨勢(shì)上都很接近,而優(yōu)化K-means算法在時(shí)延指標(biāo)上相對(duì)較差。這是由于優(yōu)化K-means算法僅考慮負(fù)載均衡,沒有考慮其他因素的約束,而MCEP和KCBP算法將時(shí)延作為控制器部署的一個(gè)參考因素。

圖6 3種算法控制器平均時(shí)延對(duì)比結(jié)果

圖7所示為3種算法的控制器負(fù)載標(biāo)準(zhǔn)差對(duì)比情況,從中可以看出,當(dāng)控制器個(gè)數(shù)較少時(shí),與優(yōu)化K-means算法相比,MCEP算法的負(fù)載均衡性相對(duì)較差,但隨著控制器個(gè)數(shù)的增加,MCEP算法負(fù)載均衡性可以得到顯著優(yōu)化。這是由于MCEP算法在部署控制器時(shí),會(huì)同時(shí)考慮負(fù)載均衡、時(shí)延和可靠性3個(gè)指標(biāo)。如圖3所示,OS3E拓?fù)涔?jié)點(diǎn)分布不均勻,東北區(qū)域節(jié)點(diǎn)較密集。當(dāng)控制器數(shù)量較少時(shí),MCEP算法會(huì)將東北區(qū)域置于一個(gè)控制器之下,這樣雖然導(dǎo)致負(fù)載不均衡,但是可以保證低時(shí)延和高可靠性。而隨著控制器數(shù)量的增加,MCEP算法通過在密集區(qū)域部署多個(gè)控制器,可以在不降低時(shí)延和可靠性的基礎(chǔ)上,明顯減少各控制器的負(fù)載差異。

圖7 3種算法控制器負(fù)載標(biāo)準(zhǔn)差對(duì)比結(jié)果

4 結(jié)束語

為提高控制路徑的可靠性并優(yōu)化控制器負(fù)載,本文提出控制路徑可用概率、控制路徑平均時(shí)延和控制器負(fù)載標(biāo)準(zhǔn)差3個(gè)度量指標(biāo),在此基礎(chǔ)上,設(shè)計(jì)一種基于可靠性和負(fù)載優(yōu)化的多控制器彈性部署算法MCEP。仿真結(jié)果表明,相比KCBP和優(yōu)化K-means算法,MCEP算法能夠在保證低時(shí)延和負(fù)載均衡的基礎(chǔ)上,使控制路徑的平均可靠性提高17%。今后將進(jìn)一步研究如何利用譜聚類算法來提高本文多控制器部署算法的魯棒性。