軟件定義網絡中基于時延和負載的多控制器部署策略研究

黃梅根 袁 雪 吳令令 孫培斯

(重慶郵電大學計算機科學與技術學院 重慶 400065)

1 引言

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

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

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

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

2 SDN控制器放置模型

2.1 問題描述

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

基于上述考慮，SDN控制器部署問題可以抽象地描述為：對于任一給定的網絡拓撲，已知所需子網的個數、控制器的處理速率以及交換機的流請求速率，求解該網絡最佳的子網劃分方法以及每個子網中最優部署控制器的位置，使整個網絡的總時延盡可能小，并且每個區域內控制器的負載盡可能均衡。

2.2 系統模型

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

式(1)表示總子網需要覆蓋所有的網絡節點元素，式(2)表示每個子網中的交換機節點有且僅有1個控制器來對它進行管理。

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

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

圖1 SDN網絡中的端到端時延

定義4 總時延。總時延分為兩個部分：(1)子網總時延；(2)網絡平均總時延。當網絡中有新的數據包進入交換機，交換機沒有對應的流表時，交換機會向對應的控制器發送Packet-in請求消息。控制器收到該消息后，對其做出相應的決策和處理后，向交換機下發所需流表。這一過程所花費的時延，可由式(8)和式(9)表示

式(12)為需要優化的目標函數，α為權重因子。式(13)為α的取值范圍。式(14)表示任一控制器的負載不能超過其處理能力，即不能過載。

3 控制器部署算法

3.1 算法分析

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

譜聚類中使用的是標準的K-means算法，但標準K-means算法的分類目標是為了使內部的距離變小，沒有考慮到類中節點的數量，這樣很容易造成局部最優。除此之外，標準的K-means算法并不能直接應用于網絡拓撲分區，原因如下：首先，隨機選擇初始中心并不能保證每個分區的質心與其關聯節點之間的最大延遲；其次，標準K-means算法是基于歐氏距離將節點分配到一個集群中的，然而由于初始中心是隨機選擇的，所以可能不存在物理鏈路，因此在實際網絡中使用歐氏距離并不總是可行的。

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

3.2 MCPA算法實現

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

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

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

4 仿真實驗

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

實驗1 驗證在不同的網絡拓撲中，MCPA，Spectral Clustering， CNPA和K-means在最大端到端時延上的差異，實驗結果如圖2(a)和圖3(a)所示。MCPA和CNPA在端到端時延的差值并不大，說明提出的算法在最大端到端時延性能接近CNPA。而Spectral Clustering較高的原因可能是聚類的時候采用的傳統的K-means算法，選取的質心并不一定是最優的，因而導致端到端時延增大。

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

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

圖2 OS3E網絡中的性能指標

圖3 ChinaNet 網絡中的性能指標

5 結束語

本文提出一種基于子網劃分的多控制器部署方法。該算法改造譜聚類算法，添加離群點分配算法和負載均衡處理算法，保證了網域內各設備間的連通性，實現了時延和負載限制下控制器的均衡部署。通過在真實網絡拓撲上進行仿真實驗，與標準的譜聚類等算法進行對比，結果表明本文提出的控制器部署算法能夠有效地對網絡進行劃分，使網絡中控制器和交換機之間保持較小的網絡總時延以及使各個控制器的負載保持均衡。未來將進一步完善MCPA，使其能夠達到更好的效果。