軟件定義網(wǎng)絡(luò)中基于時延和負(fù)載的多控制器部署策略研究

黃梅根 袁 雪 吳令令 孫培斯

(重慶郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 重慶 400065)

1 引言

SDN(Software Defined Network)起源于2006年斯坦福大學(xué)的Clean Slate研究課題[1]，是一種將數(shù)據(jù)轉(zhuǎn)發(fā)功能與控制邏輯解耦的新型網(wǎng)絡(luò)架構(gòu)，具有集中式控制、可編程性、開放性以及靈活的網(wǎng)絡(luò)管理等特點[2]。經(jīng)典SDN網(wǎng)絡(luò)架構(gòu)依賴擁有全局視圖的單一控制器，在中小型網(wǎng)絡(luò)中，可以勝任網(wǎng)絡(luò)的管理。但在大規(guī)模網(wǎng)絡(luò)環(huán)境中，隨著轉(zhuǎn)發(fā)設(shè)備和終端的增多，單一控制器有限的資源和處理能力難以及時處理大量流請求，因此依賴單一控制器的SDN網(wǎng)絡(luò)架構(gòu)存在可擴(kuò)展性問題。

為了解決這一問題，業(yè)界提出通過部署多個控制器來分擔(dān)網(wǎng)絡(luò)中的各種處理請求，以減少單個控制器的負(fù)載，從而提高整個控制平面的處理能力。對于一個給定的網(wǎng)絡(luò)拓?fù)?，部署多個控制器往往需要考慮3個方面：網(wǎng)絡(luò)中需要多少個控制器、這些控制器應(yīng)該放在哪里以及網(wǎng)絡(luò)中交換機(jī)的歸屬問題。

Heller等人[3]首次提出控制器放置問題(Controller Placement Problem， CPP)，并將控制器位置問題作為設(shè)施位置問題來解決，試圖最小化平均傳播延遲和最壞情況傳播延遲。他們表明，最優(yōu)安置的控制器延遲明顯優(yōu)于隨機(jī)安置的控制器，但該算法未考慮控制器負(fù)載；Zhang等人[4]以網(wǎng)絡(luò)可靠性、控制器的負(fù)載均衡和響應(yīng)時間為度量，使用自適應(yīng)細(xì)菌覓食優(yōu)化算法來解決控制器放置問題，但未考慮控制器時延問題；文獻(xiàn)[5，6]都考慮在控制器負(fù)載不超過其容量的情況下，用不同的算法最小化控制器到節(jié)點的延遲或者控制器到控制器的延遲，但這些算法僅考慮了傳播時延；文獻(xiàn)[7]主要考慮控制器負(fù)載，提出一種近似比為2的多控制器負(fù)載均衡算法；文獻(xiàn)[8，9]利用博弈論處理交換機(jī)遷移，通過重新分配交換機(jī)而不是添加或刪除控制器來實現(xiàn)控制器的負(fù)載平衡，以達(dá)到最大化整個網(wǎng)絡(luò)效用即最大化每個控制器的資源利用率，但并未考慮到時延問題；Wang等人[10]考慮端到端的傳播時延以及控制器排隊時延，提出聚簇網(wǎng)絡(luò)劃分算法來減少端到端的傳播時延，并放置多控制器來減少排隊時延，但未考慮控制器負(fù)載問題；文獻(xiàn)[11]嘗試使用改進(jìn)的NSGA-II(非支配排序遺傳算法)來解決最小化延遲和容量管理的問題，但僅考慮了傳播時延；文獻(xiàn)[12]使用修改后的ap聚類算法對網(wǎng)絡(luò)進(jìn)行分區(qū)，自動計算聚類數(shù)量并識別出最佳的控制器部署位置，但該算法僅考慮了控制器之間的傳播時延；文獻(xiàn)[13]提出多種優(yōu)化模型用于控制器部署及故障處理，但僅考慮了交換機(jī)到控制器的傳播時延。

綜上所述，大多數(shù)研究只考慮了傳播時延，然而網(wǎng)絡(luò)中除數(shù)據(jù)包發(fā)送和傳輸所需的時延外，每次交換機(jī)轉(zhuǎn)發(fā)都需要時間，且距離控制器的跳數(shù)越多，所需轉(zhuǎn)發(fā)時間就越多。此外，控制器和交換機(jī)所需的排隊時延又與網(wǎng)絡(luò)流量有一定的關(guān)系，網(wǎng)絡(luò)流量越大，排隊時延就越大?？梢娒恳环N時延都對CPP有一定的影響，因此為了更好地部署控制器，應(yīng)當(dāng)綜合考慮網(wǎng)絡(luò)中可能產(chǎn)生的各種時延。故本文考慮總時延和控制器負(fù)載均衡，引入譜聚類，并改造該算法中的K-means算法來保證連通性的同時加入離群點處理算法和負(fù)載均衡處理算法，將網(wǎng)絡(luò)劃分成一定數(shù)量的子網(wǎng)域，并在每個子網(wǎng)域中選取合適的位置部署控制器，達(dá)到降低網(wǎng)絡(luò)總時延和均衡控制器負(fù)載的目的。

2 SDN控制器放置模型

2.1 問題描述

SDN控制器的部署過程中，應(yīng)該盡量滿足以下幾個條件：(1)低成本。出于對成本的考慮，在滿足需求的情況下，控制器的數(shù)量應(yīng)該盡量少；(2)低時延。網(wǎng)絡(luò)時延是控制器部署中非常重要的一個性能度量，主要由傳播時延、處理時延、發(fā)送時延和排隊時延組成，在很大程度上影響網(wǎng)絡(luò)的性能。為了保證網(wǎng)絡(luò)的性能，應(yīng)該使網(wǎng)絡(luò)中的總時延不超過一個給定的閾值，并且總時延越低越好；(3)負(fù)載均衡。在SDN網(wǎng)絡(luò)中，控制器的負(fù)載均衡也是一個不可忽略的度量。控制器的負(fù)載越大，則其對于流的處理時間會越久，從而容易造成控制器處理效率低下，影響整個網(wǎng)絡(luò)的性能。因此，均衡各個控制器的負(fù)載，能夠有效提高整個網(wǎng)絡(luò)的服務(wù)質(zhì)量。

基于上述考慮，SDN控制器部署問題可以抽象地描述為：對于任一給定的網(wǎng)絡(luò)拓?fù)?，已知所需子網(wǎng)的個數(shù)、控制器的處理速率以及交換機(jī)的流請求速率，求解該網(wǎng)絡(luò)最佳的子網(wǎng)劃分方法以及每個子網(wǎng)中最優(yōu)部署控制器的位置，使整個網(wǎng)絡(luò)的總時延盡可能小，并且每個區(qū)域內(nèi)控制器的負(fù)載盡可能均衡。

2.2 系統(tǒng)模型

將SDN網(wǎng)絡(luò)建模為無向圖G=(V，E)，其中V表示網(wǎng)絡(luò)中交換機(jī)和控制器節(jié)點的集合，E表示連接交換機(jī)和控制器的鏈路，n表示V中節(jié)點的個數(shù)。假設(shè)在SDN網(wǎng)絡(luò)中需要放置k個控制器，則控制器的集合可表示為C={i|i=1，2，...，k}且控制器i管理的交換機(jī)集合表示為CVi。則在對SDN網(wǎng)絡(luò)進(jìn)行分區(qū)時，需要滿足

式(1)表示總子網(wǎng)需要覆蓋所有的網(wǎng)絡(luò)節(jié)點元素，式(2)表示每個子網(wǎng)中的交換機(jī)節(jié)點有且僅有1個控制器來對它進(jìn)行管理。

為進(jìn)一步闡述控制器放置問題，接下來將對研究部署時需考慮的度量進(jìn)行定義。

定義1 端到端時延。如圖1所示，從交換機(jī)1到控制器傳輸數(shù)據(jù)包的端到端時延主要由3個部分組成：數(shù)據(jù)包傳輸時延(TDi)、數(shù)據(jù)包傳播時延(PDi)和交換機(jī)處理時延(SPDi)。數(shù)據(jù)包傳輸延遲也稱發(fā)送時延，是指從開始發(fā)送數(shù)據(jù)幀到發(fā)送完畢所需要的全部時間，由TDi=PLi/BWi給出，其中PLi是鏈路i中數(shù)據(jù)包的長度，BWi為該鏈路的帶寬。數(shù)據(jù)包傳播時延是指數(shù)據(jù)包在鏈路上傳播所需要的時間，可由PDi=Li/TS計算而出，Li為鏈路i的距離， TS為鏈路上介質(zhì)的傳播速度。另外，交換機(jī)處理時延SPDi受交換機(jī)負(fù)載的影響。因此數(shù)據(jù)包從交換機(jī)Si到控制器Cn的端到端時延可表示為

圖1 SDN網(wǎng)絡(luò)中的端到端時延

定義4 總時延?？倳r延分為兩個部分：(1)子網(wǎng)總時延；(2)網(wǎng)絡(luò)平均總時延。當(dāng)網(wǎng)絡(luò)中有新的數(shù)據(jù)包進(jìn)入交換機(jī)，交換機(jī)沒有對應(yīng)的流表時，交換機(jī)會向?qū)?yīng)的控制器發(fā)送Packet-in請求消息?？刂破魇盏皆撓⒑螅瑢ζ渥龀鱿鄳?yīng)的決策和處理后，向交換機(jī)下發(fā)所需流表。這一過程所花費的時延，可由式(8)和式(9)表示

式(12)為需要優(yōu)化的目標(biāo)函數(shù)，α為權(quán)重因子。式(13)為α的取值范圍。式(14)表示任一控制器的負(fù)載不能超過其處理能力，即不能過載。

3 控制器部署算法

3.1 算法分析

控制器部署問題是一個帶約束的多目標(biāo)組合問題，因此本文考慮使用譜聚類算法來求解該問題。對于給定的網(wǎng)絡(luò)拓?fù)鋱DG=(V，E)，目標(biāo)是將其切成k個互相沒有聯(lián)系的子圖，每個子圖點的集合為A1，A2， ···，Ak，其中Ai ∩Aj=?且A1∪A2∪...∪Ak=V。

譜聚類中使用的是標(biāo)準(zhǔn)的K-means算法，但標(biāo)準(zhǔn)K-means算法的分類目標(biāo)是為了使內(nèi)部的距離變小，沒有考慮到類中節(jié)點的數(shù)量，這樣很容易造成局部最優(yōu)。除此之外，標(biāo)準(zhǔn)的K-means算法并不能直接應(yīng)用于網(wǎng)絡(luò)拓?fù)浞謪^(qū)，原因如下：首先，隨機(jī)選擇初始中心并不能保證每個分區(qū)的質(zhì)心與其關(guān)聯(lián)節(jié)點之間的最大延遲；其次，標(biāo)準(zhǔn)K-means算法是基于歐氏距離將節(jié)點分配到一個集群中的，然而由于初始中心是隨機(jī)選擇的，所以可能不存在物理鏈路，因此在實際網(wǎng)絡(luò)中使用歐氏距離并不總是可行的。

為了實現(xiàn)控制器的均衡部署，使用改造的Kmeans算法，實現(xiàn)均衡的譜聚類，在保證總時延較低的情況下，達(dá)到均衡各個控制器間的負(fù)載的目的。

3.2 MCPA算法實現(xiàn)

本文改造標(biāo)準(zhǔn)的K-means算法，首先用Dijkstra算法取代歐氏距離來求解出各相連節(jié)點的端到端距離，保證網(wǎng)絡(luò)的連通性；其次，在初步完成分區(qū)之后，加入離群點檢測算法，若發(fā)現(xiàn)孤立節(jié)點，則采取鄰近法進(jìn)行再分配以確保所有的交換機(jī)節(jié)點都分配到了相應(yīng)的控制器；最后加入負(fù)載均衡處理，保證子網(wǎng)總時延較低的情況下，控制器不過載。

如表1所示，該算法分為3個階段：(1)數(shù)據(jù)降維處理階段(步驟(1)—步驟(8))；(2)網(wǎng)絡(luò)劃分階段(步驟(9)—(19))；(3)子網(wǎng)調(diào)整階段(步驟(20)—步驟(33))。在網(wǎng)絡(luò)劃分階段，首先計算各個點到初始選取質(zhì)心的端到端距離，然后根據(jù)距離將節(jié)點分配給相應(yīng)的質(zhì)心后以時延總和最小為條件找出真正的質(zhì)心(步驟(16)—(19))。當(dāng)初步完成分區(qū)后，進(jìn)入子網(wǎng)調(diào)整階段，先進(jìn)行離群點檢測，若存在未分配到的節(jié)點，則使用重分配算法以就近原則對該節(jié)點進(jìn)行分配(步驟(24))。在保證所有節(jié)點都劃分到對應(yīng)的區(qū)域后，選擇負(fù)載最大的子網(wǎng)，找出邊緣區(qū)域的交換機(jī)節(jié)點作為擬移動節(jié)點(步驟(32))，以距離和F為指標(biāo)不斷調(diào)整擬移動交換機(jī)的分配，直至BLP-1接近一個極小的值(步驟(30)—步驟(33))，最終產(chǎn)生k個負(fù)載均衡的子網(wǎng)。

表1 基于時延和負(fù)載的多控制器部署算法

4 仿真實驗

為評估本文提出的控制器部署算法，采用Internet2 OS3E網(wǎng)絡(luò)和ChinaNet網(wǎng)絡(luò)進(jìn)行仿真實驗。這兩種網(wǎng)絡(luò)廣泛使用于評估控制器部署問題，也是所選取對比算法之一中基于聚類的網(wǎng)絡(luò)劃分算法(Clustering-based Network Partition Algorithm，CNPA)[10]用于驗證的網(wǎng)絡(luò)拓?fù)??？紤]到真實網(wǎng)絡(luò)拓?fù)涞倪B通性，采用Haversine公式計算拓?fù)渲泄?jié)點之間的距離，并使用Dijkstra算法來計算節(jié)點到節(jié)點的最短路徑距離。設(shè)置控制器服務(wù)速率為1 kpps，以保證一個請求可以在1 ms內(nèi)處理完成，并規(guī)定每個交換機(jī)的流請求獨立且最大為0.1 kpps[10]。分別與K-means、譜聚類(Spectral Clustering)和CNPA在平均總時延、最大端到端時延以及控制器負(fù)載方面進(jìn)行比較。

實驗1 驗證在不同的網(wǎng)絡(luò)拓?fù)渲?，MCPA，Spectral Clustering， CNPA和K-means在最大端到端時延上的差異，實驗結(jié)果如圖2(a)和圖3(a)所示。MCPA和CNPA在端到端時延的差值并不大，說明提出的算法在最大端到端時延性能接近CNPA。而Spectral Clustering較高的原因可能是聚類的時候采用的傳統(tǒng)的K-means算法，選取的質(zhì)心并不一定是最優(yōu)的，因而導(dǎo)致端到端時延增大。

實驗2 驗證在不同的網(wǎng)絡(luò)拓?fù)渲校琈CPA，Spectral Clustering， CNPA和K-means在平均總時延上的差異，實驗結(jié)果如圖2(b)和圖3(b)所示。隨著控制器的增加，平均總時延都在下降，但K-means算法始終高于其他3種算法。分析其原因可知，Kmeans每次選擇節(jié)點加入的時候，會以最小距離為條件改變控制器的位置，這一做法雖減小了傳播時延，但忽略了控制器的負(fù)載情況，在大規(guī)模網(wǎng)絡(luò)中部署少量控制器時，容易出現(xiàn)局部控制器負(fù)載過大，導(dǎo)致排隊時延增加。CNPA總體高于MCPA算法和Spectral Clustering可能也是因為沒有考慮控制器負(fù)載，增加了排隊時延，導(dǎo)致總時延增大。

實驗3 驗證在不同的網(wǎng)絡(luò)拓?fù)渲?，MCPA，Spectral Clustering， CNPA和K-means在控制器負(fù)載上的差異，實驗結(jié)果如圖2(c)和圖3(c)所示。在圖2(c)中，MCPA算法下的控制器負(fù)載參數(shù)始終接近1.0，且最小的時候達(dá)到了1.05，最大值為1.3，優(yōu)于其他3種算法。分析原因是：K-means是以減少傳播時延為目標(biāo)的，未考慮到控制器的負(fù)載情況，導(dǎo)致控制器的負(fù)載增大。在圖3(c)中，控制器數(shù)量達(dá)到5后，隨著控制器的增加，CNPA的負(fù)載參數(shù)逐漸遞增，分析原因可能是該算法雖改進(jìn)了K-means算法，保證了連通性，但并沒有考慮控制器負(fù)載。負(fù)載參數(shù)最小的是MCPA算法和Spectral Clustering，且MCPA算法更低一些。這是因為譜聚類算法雖然采用了RatioCut來劃分網(wǎng)絡(luò)，具有了一定的均衡作用，但其采用的還是傳統(tǒng)的K-means算法進(jìn)行最后的聚類，因此不及經(jīng)過改造K-means后的MCPA算法。

圖2 OS3E網(wǎng)絡(luò)中的性能指標(biāo)

圖3 ChinaNet 網(wǎng)絡(luò)中的性能指標(biāo)

5 結(jié)束語

本文提出一種基于子網(wǎng)劃分的多控制器部署方法。該算法改造譜聚類算法，添加離群點分配算法和負(fù)載均衡處理算法，保證了網(wǎng)域內(nèi)各設(shè)備間的連通性，實現(xiàn)了時延和負(fù)載限制下控制器的均衡部署。通過在真實網(wǎng)絡(luò)拓?fù)渖线M(jìn)行仿真實驗，與標(biāo)準(zhǔn)的譜聚類等算法進(jìn)行對比，結(jié)果表明本文提出的控制器部署算法能夠有效地對網(wǎng)絡(luò)進(jìn)行劃分，使網(wǎng)絡(luò)中控制器和交換機(jī)之間保持較小的網(wǎng)絡(luò)總時延以及使各個控制器的負(fù)載保持均衡。未來將進(jìn)一步完善MCPA，使其能夠達(dá)到更好的效果。