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

陸 , ,

(國家數(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ò)的管理和維護,因此,受到學界和工業(yè)界的廣泛關(guān)注。隨著SDN網(wǎng)絡(luò)規(guī)模的不斷擴大,單個控制器已經(jīng)難以滿足現(xiàn)有的網(wǎng)絡(luò)需求。為提高網(wǎng)絡(luò)的可拓展性,避免單點失效,研究人員在集中式控制的基礎(chǔ)上提出將網(wǎng)絡(luò)劃分為多個域,通過部署多個控制器來實現(xiàn)邏輯上集中、物理上分布的SDN網(wǎng)絡(luò)[2]。多控制器的部署主要有3個關(guān)鍵:控制器的部署數(shù)量;控制器的部署位置;交換機與控制器間的映射關(guān)系,即哪些交換機由哪些控制器控制。一個網(wǎng)絡(luò)所需的控制器數(shù)量由實際場景所決定,因此,本文主要研究和分析控制器的部署位置和交換機與控制器間的映射關(guān)系。

在實際中,要實現(xiàn)控制器的合理部署,會面臨較多挑戰(zhàn)?？刂茖拥氖Ц怕室獫M足特定的要求以保證網(wǎng)絡(luò)的可靠性。同時,要利用控制器的負載優(yōu)化來保證負載的合理分配,并減少交換機到控制器的時延,以提高網(wǎng)絡(luò)性能。

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

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

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

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

1 問題重述與建模

1.1 問題重述

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

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

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

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

1)在給定網(wǎng)絡(luò)拓撲和控制器數(shù)量的情況下,確定控制器的部署位置。

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

1.2 問題建模

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

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

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

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

其中,δ表示閾值。

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

?i,j∈n,APij=APji

(4)

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

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

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

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

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

本文將SDN中控制器的負載視為控制器因管理交換機而擔負的計算負載。為論述方便,本文將一個控制器的負載視為該控制器所管理的交換機數(shù)目。控制器負載差異表示為各控制器實際管理交換機數(shù)量的差異,可通過各控制器所管理交換機數(shù)量的標準差來表示:

基于以上3個指標的定義,低時延與高可靠的多控制器均衡部署問題即為找到一個合適的方法,使CPAFP、CPAD、CLSD3個指標均達到最小?？杀硎緸?

min[CPAFP,CPAD,CLSD]

(10)

s.t.CPFPij

(11)

CPDij

(12)

|SCj|

(13)

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

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

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

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

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

(15)

其中,α表示時延與可靠性之間的權(quán)值,當0≤α<0.5時,聚類更偏向于可靠性,當0.5≤α≤1時,聚類原則上偏向于時延。由各節(jié)點相似度可以得到表示整個網(wǎng)絡(luò)拓撲的相似度矩陣W。

對于一個網(wǎng)絡(luò)拓撲G,將其切割為2個子圖A、B,定義A和B之間的切割為:

由切割的定義可得,若將網(wǎng)絡(luò)拓撲切割為k個子圖,則最小割可以表示為:

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

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

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

argminRatioCut(A1,A2,…,Ak)

(19)

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

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

(20)

L=D-W

(21)

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

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

式(24)是將網(wǎng)絡(luò)拓撲切分成2個子圖的結(jié)果,因此,對于k個子圖切分的RatioCut,可表示為:

Tr(H′LH)

(25)

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

argmin Tr(H′LH)

s.t.H′H=Ik

(26)

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

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

(27)

其中,最小值對應的矩陣H=[v1,v2,…,vk]。

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

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

2 算法描述與分析

2.1 算法描述

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

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

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

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

MCEP算法具體描述如下:

算法1MCEP算法

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

輸出控制器位置bestVc,交換機與控制器之間的映射關(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.隨機選擇一個節(jié)點,將其歸入鄰居節(jié)點類別;調(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個最小特征值對應的特征向量組成矩陣H;第6行～第8行,使用傳統(tǒng)的k-medoids算法對表示節(jié)點的k維行向量進行第一次分類;第9行～第19行表示基于模擬退火對分類結(jié)果進行調(diào)整;第20行輸出最優(yōu)的分類結(jié)果。

2.2 算法復雜度分析

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

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

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

圖3 OS3E網(wǎng)絡(luò)拓撲

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

3.2 算法性能分析

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

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

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

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

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

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

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

圖7 3種算法控制器負載標準差對比結(jié)果

4 結(jié)束語

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