基于網絡拓撲劃分的大規模SDN控制器部署

張元龍，廖曉群，張佳庚

(1.西安科技大學 信息網絡中心，陜西 西安 710054；2.西安交通大學 網絡信息中心，陜西 西安 710049)

0 引 言

軟件定義網絡(software defined network，SDN)體系架構通過網絡可編程和開放接口技術解耦合了網絡控制與轉發平面，使得新型網絡具備邏輯集中可編程控制能力[1]。然而，網絡部署規模的擴大帶來了網絡業務需求和轉發流量的快速增加，單一集中控制器無法對大規模流量請求進行實時處理以服務網絡業務需求。因此，分布式多控制器部署成為未來SDN大規模部署應用的關鍵方向[2,3]。

近年來，關于控制器部署問題的研究主要從全局網絡視角出發建立以通信時延、彈性、可靠性、能耗和負載均衡等為單/多目標的優化方案[1-3]。文獻[4]基于Pareto最優控制器部署框架，考慮了控制器與交換機之間和控制器彼此之間的時延和通信代價以及負載均衡等多種性能指標來實現最優控制。然而，此類方法應用在大規模復雜網絡中時存在全局部署過于復雜且會陷入局部次優解等問題。采用分而治之思想，學者提出基于網絡劃分技術的分布式多控制器部署方案，以達到簡化部署復雜度和保證部署性能的目的。文獻[5]提出一種I-K-means部署方案，以減小網絡質心節點及其關聯節點之間的最大傳播時延為目標來實現網絡分區和子域部署求解。文獻[6]則在K均值聚類基礎上提出啟發式控制器部署策略，通過劃分子域中控制節點和交換機節點之間傳播時延最小化為目標來實現多控制器部署。文獻[7]提出一種基于密度聚類劃分的控制器部署方法，通過參考子域交換機密度實現網絡劃分和局部部署。文獻[8,9]提出利用譜聚類(spectral clustering，SC)結合真實網絡拓撲結構特性來實現全局網絡的有效劃分，并基于劃分子域來實現控制器部署。文獻[10]在譜聚類基礎上結合矩陣攝動理論和特征間隙法，自主發現網絡穩定結構并確定最優網絡劃分，從而實現更合理的控制器部署。然而，這類標準聚類方法需要預先指定分類簇數或閾值，受限于初始化和人為因素影響，無法在大規模復雜網絡中提供穩定且合理的網絡劃分，網絡可靠性得不到保障。

考慮到網絡結構本身可作為控制器部署線索，本文提出了一種改進Louvain社區檢測[11]算法的控制器部署策略Modified-Louvain，包括兩個階段：第一是網絡社區的均衡劃分，為了使社區的緊密性最大化，基于節點距離相似度重定義鏈路權重，然后在Louvain社區檢測算法中引入社區容量約束因子，提出一種平衡負載的社區檢測算法，可獨立根據網絡拓撲結構來實現全局網絡的準確合理劃分。第二是啟發式部署控制器，針對每個劃分子網以控制器與交換機之間傳播時延最小化為目標來確定控制器的部署位置。總之，所提Modified-Louvain控制器部署方案通過識別大規模網絡中具有社區屬性的網絡結構，可獨立確定合理的分區。同時該算法引入尺度約束因子，平衡子網的大小規模，保證將整個網絡劃分為多個規模適中的子域，提供可靠控制器部署策略。

1 相關工作

多控制器部署方案[12-14]逐漸應用并實踐于大型SDN網絡。解決SDN面向大規模網絡部署的趨勢是通過分布式理念將多個控制器部署到不同的控制域內，形成一個物理上分布的控制平面，通過控制器間的通信協作最終形成邏輯上集中的控制平面來統一管理全網設備。考慮到多控制器管控的網絡場景，自然誕生出如何決策控制器數量和位置的問題，即控制器部署問題(controller placement problem，CPP)。具體來說，CPP需要解決以下兩個問題[15]：

(1)需要多少控制器？

(2)控制器應該部署在哪些位置？

圖1所示一個大型SDN網絡的控制器部署，可看出控制器所管轄的網絡子域范圍可能包括企業、學校、政府和數據中心等多種異構節點，為滿足某種特定的網絡性能指標需要合理決策控制器數量和部署位置。目前研究方向包括兩方面：性能優化和部署模型。從性能優化視角來看，主要依據的網絡性能指標包括傳播時延[15]、控制器容量[9]、節點故障[16]、部署代價[17]和能耗效率[18]等，其中控制器與交換機的傳播時延直接影響流表規則的轉發效率，因此被視作主要優化性能指標。而當多個性能指標同時考慮時，CPP通常定義為組合優化問題，這對于大型SDN網絡來說求解復雜度通常較高。從部署模型來看，聚類算法廣泛用于求解CPP，通過劃分類簇和確定類簇中心來完成控制器數量和位置的確定[5-10]。然而現有應用廣泛的聚類方法過于依賴初始化和人為隨機因素，因此無法提供合理且穩定的控制器部署方案。本文考慮到大規模SDN網絡對于控制器部署的高效穩定要求，提出基于網絡社區劃分機制的控制器部署策略，將高復雜的全局部署問題分解為多個低復雜的局部部署問題，進而采用啟發式機制來優化網絡性能指標。最后，該方法的網絡分區及部署性能在實際網絡拓撲上得到了驗證。

圖1 大型SDN網絡

2 控制器部署建模

對于一個SDN網絡，主要網絡元素構成包括控制器、交換機和鏈路。考慮到SDN網絡中交換機節點之間可上下行傳播流量，將SDN網絡建模為無向圖G=(V,E)， 其中V代表交換機節點，E代表連接兩個節點的物理鏈路。假定在SDN網絡中部署的控制器數量為K，定義集合={ci|i=1,2,…,K} 為控制器集。φ(c)(c∈) 表示將單個控制器與一組交換機連接起來的映射函數。那么整個網絡G將被K個控制器所管理并滿足

φ(ci)≠?, ?ci∈

(1)

φ(ci)∩φ(cj)=?, ?i≠j,ci,cj∈

(2)

(3)

上述公式表示每個子網絡必須包含至少一個節點，而且每個節點僅分配給一個子網絡且所有子網絡必須覆蓋整個網絡。

在大規模SDN網絡中，通信的及時性是影響網絡性能的一個重要因素。在本文工作中，網絡被劃分為多個子網，控制器和交換機之間的傳播時延將直接影響數據平面的數據包轉發效率，因此被用作關鍵性能指標。其中，平均時延和最大時延模型定義為

(4)

(5)

式(4)表示交換機和控制器間的平均時延；式(5)表示交換機和控制器間的最大時延。其中d(s,c) 表示兩點間的Dijkstra最短路徑距離，對應于交換機s到關聯控制器c的傳播時延，c∈φ(c) 表示控制器c將被部署至某一個交換機所在的位置。|φ(c)| 表示被控制器c所管理的交換機數目。

3 控制器部署策略

3.1 Modified-Louvain算法

假定SDN網絡拓撲G=(V,E)， 類似于式(1)～式(5)的目標，CPP的目的在于確定控制器數量和部署位置，以及確定控制器與交換機間的連接關系，從而確保某種網絡性能指標的優化。與此同時，還必須保證任何時候控制流量負載不能超過關聯控制器的負載容量上限[16]，定義為

(6)

式中：Load(c) 表示控制器c的最大負載容量，load(n) 表示控制交換機n所需的控制流量負載。因此，求解CPP的主要目標就是在式(6)的約束下來最小化每個控制域內控制器與交換機之間的傳播時延

(7)

(8)

s.t.constraints(6)

(9)

為了敘述的完整性，首先介紹標準Louvain算法。給定圖G(V,E)具有節點集V和邊集E，社區檢測將網絡劃分成不相交區域C={c1,c2,…,ck}， 使得V=c1∪c2…∪ck并且ci∩cj=?,i≠j。 每條邊e(u,v)∈E具有屬性權重w(u,v)。 模塊度Q用于量化劃分質量[11]

(10)

(11)

(12)

其中，節點間權重越大表示兩個節點的關聯越緊密，越有可能分布在同一社區。在網絡中，節點之間權重越大意味著鄰接關系更為緊密。以最大化網絡社區緊密性為目標，重新定義節點間邊權重函數

(13)

式中：d(u,v) 表示節點對 (u,v) 間的最短路徑長度，而dmax表示所有節點對間最長的最短路徑長度。

模塊度已被廣泛應用于評價社區檢測的質量[19]。然而，模塊度的優化本質上是一個NP-完全問題。一般用于優化模塊度最大化的策略包括4種：貪婪、模擬退火、極值和譜優化。貪婪優化采用不同的方法將頂點合并到社區中以獲得更高的模塊性，這通常會生成高質量的社區；模擬退火采用概率方法對模塊性進行全局優化；極值優化是一個啟發式搜索過程；譜優化利用特殊矩陣的特征值和特征向量進行模塊化優化。本文關注于貪婪搜索策略，即如何通過探索模塊度增益來評價網絡劃分質量的好壞，根據式(10)所定義的模塊度，模塊增益度定義為

(14)

算法1：Modified-Louvain算法

輸入：G(V,E,W)： 加權網絡；θ：控制器負載最大容量；φu：交換機u所需控制負載

輸出：C：平衡子網絡集合；Qbest：最優模塊度

whileTruedo

C←{{u}}, ?u∈V;

load(c)←∑u∈cφu,Ltotal←{∑c∈Cload(c)}

whileCchanges do // 階段1

foru∈Vandu∈cdo

load(c)=loadtemp(c);

end for

ifQ-Qbest≤0 then break;

end if

Qbest←Q;

C′←{c},?c∈C;

// 階段2：重構圖

V′←C′;

E′←{e(c,c′)}, ?e(u,v)∈E,u∈c,v∈c′;

wc,c′←∑wu,v, ?e(u,v)∈E,u∈c,v∈c′;

V←V′;E←E′.

end while

3.2 控制器位置選擇問題

圖2 網絡中控制器位置選擇

算法2：基于最小化平均時延的控制器位置選擇策略

輸入：拓撲劃分集C；

forc∈Cdo

Γ1←{};

foru∈cdo

lu←0; //定義從節點u到其它節點的時延總和

forv∈cdo

lu←lu+l(u,v);

end for

Γ←Γ∪{lu/|c|}

end for

end for

算法3：基于最小化最大時延的控制器位置選擇策略

輸入：拓撲劃分集C；

forc∈Cdo

Γ←{};

foru∈cdo

Γ2←{}

forv∈cdo

Γ2←Γ2∪{l(u,v)};

end for

end for

end for

3.3 復雜度分析

基于網絡劃分的控制器部署算法主要包括兩個步驟，分別是針對網絡拓撲的社區檢測(子網絡劃分)和每個子網絡中的控制器位置選擇過程。相比較于全局部署策略，基于網絡劃分機制的方案將全局部署分隔成單獨的兩個子過程，而且只需要考慮將控制器方案限定于小規模子網絡中，從而在一定程度上降低了問題的復雜性。對于一個具有N個節點的網絡拓撲，基于Louvain社區檢測算法的執行時間復雜度是O(NlogN)。 理想情況下可以得到m個平衡社區，也就是說每個社區包含相同數量的節點，表示為n=N/m。 而位置選擇過程的執行復雜度為O(m·n2)， 因此總體基于Louvain劃分的控制器部署時間復雜度為O((mn)log(mn))+O(m·n2)。 采用枚舉的載荷約束控制其部署算法執行復雜度是Ο(mNNm)。 總體而言，所提Modified Louvain可高效率地提供一個穩定且準確的控制器部署方案。

4 仿真實驗

在本節實驗中，為了評估Modified Louvain在SDN控制器部署問題中的性能，從SNDlib[20]中選擇3種不同尺度的大型骨干網拓撲，通過實驗來驗證算法在不同網絡規模中的部署性能。所有拓撲的屬性見表1，其中鏈路長度采用半正矢公式求解球面距離。為了評估基于Modified Louvain的CPP(簡寫為ML-CPP)部署方案的有效性，選取同樣屬于網絡劃分機制的基于譜聚類的控制器部署算法(簡寫為SC-CPP)[8-10]作為對比策略，這兩種算法均將CPP問題轉換為等價的網絡劃分問題，通過求解網絡劃分過程將全網拓撲劃分為多個子域，然后在每個子域中確定以優化某個網絡性能指標的控制器放置策略。在本節實驗中假定每個子域僅部署一個控制器，即最終網絡劃分所得的子域個數就是所需部署的控制器數量。

表1 網絡拓撲屬性

首先，對比分析ML-CPP和SC-CPP兩種網絡劃分策略的負載均衡性能，即控制器所管轄的交換機數量的平衡指數。本實驗假設所有控制器具有統一的容量負載能力，而且每個交換機所需要的控制流量負載也都相同。因此，令φu=1， 同時對3個網絡拓撲設定控制器容量分別為θ={8,10,11}， 即每個子網絡中所能容納的交換機數量不能超過控制器負載容量。另外定義量化的負載均衡性能指標

(15)

式中：K表示劃分分區個數，N表示網絡中總的節點數，Ni表示第i個分區中節點數，λ越小，其負載均衡性能越好。

圖3所示ML-CPP和SC-CPP兩種方案分別執行100次實驗后的平均λ對比情況，其中對于Nobel-EU、Janos-US-CA和Germany50這3種網絡拓撲，ML-CPP所獲得的網絡分區數分別是 {6,6,7}。 從圖中所知，基于Modified-Louvain的網絡劃分機制可以保證網絡化分結果的穩定性，同時生成具有更低負載均衡指數的劃分結果，在3種網絡拓撲上均表現出比譜聚類(SC)更穩定且更好的性能。由于譜聚類受限于隨機因素的影響，為降低實驗結果的隨機性，每次獨立實驗重復進行了100次。接下來，針對這些結果將統計不同控制器部署方案下的平均傳播時延和最大傳播時延的累計分布曲線(cumulative distribution function，CDF)。

圖3 基于不同控制器部署策略的網絡負載均衡性能指標

圖4展示了在Nobel-EU網絡拓撲上基于ML-CPP和SC-CPP兩種網絡劃分策略的控制器部署性能。從圖中可以看出ML-CPP可以提供穩定且最優的平均時延和最大時延，而SC-CPP由于受限于人為參數和隨機初始化因素的影響，所產生的控制器部署性能差異較大，平均時延和最大時延抖動范圍分別是[2.52 ms,2.73 ms]和[5.94 ms,6.98 ms]，這些變化范圍均大于對應基于ML-CPP的平均時延和最大時延。

圖4 Nobel-EU網絡上控制器部署方案的時延性能對比

圖5展示了在Janos-US-CA網絡拓撲上基于ML-CPP和SC-CPP兩種網絡劃分策略的控制器部署性能。從圖5(a)可看出基于ML-CPP的平均時延(2.81 ms)持續小于基于SC-CPP所得到的平均時延范圍[3.34 ms,4.18 ms]。另外，對比最大時延性能，從圖5(b)中可以發現ML-CPP仍然確保了穩定的最大時延(8.76 ms)，而基于SC-CPP的最大時延變化范圍為[6.84 ms,21.12 ms]，雖然存在56%的基于SC-CPP的最大時延小于ML-CPP，但是仍有44%的基于SC-CPP的部署方案產生的最大時延遠高于8.76 ms。

圖5 Janos-US-CA網絡上控制器部署方案的時延性能對比

圖6展示了在Germany50網絡拓撲上基于ML-CPP和基于SC-CPP兩種網絡劃分策略的控制器部署性能。從圖6(a)和圖6(b)可以看出基于ML-CPP的控制器部署方案所產生的平均時延和最大時延均小于基于SC-CPP的控制器部署性能結果，而且ML-CPP可確保穩定的控制器部署性能，從而提供更加可靠的控制器部署方案。

圖6 Germany50網絡上控制器部署方案的時延性能對比

5 結束語

為了在大規模SDN網絡環境下設計高效穩定的控制器部署方案，并降低全局SDN網絡控制器部署的復雜性，本文基于社區檢測的網絡劃分機制來簡化大規模SDN網絡的控制器部署復雜度，結合控制器負載容量約束條件，提出一種改進的均衡負載網絡社區劃分方法(Modified-Louvain)用于準確識別控制器所管轄的子網絡，并以最小化平均時延和最大時延為目標啟發式求解控制器的最優部署位置。所提控制器部署方案在復雜網絡分析理論的支持下，考慮了網絡社區結構屬性可以作為控制器配置的線索，通過啟發式求解可提供快速準確的控制器部署方案，進而可為SDN控制平面管理提供性能保障。仿真結果表明，所提方法可有效處理大規模SDN網絡下的控制器部署問題，在均衡控制器負載的同時保證控制器與交換機之間傳播時延的最小化目標，能夠提供可靠部署策略。