SDN多控制器部署及流量均衡研究*

陳俊彥，李 玥，梁楚欣，雷曉春

(1.桂林電子科技大學(xué)計算機(jī)與信息安全學(xué)院，廣西 桂林 541004;2.廣西云計算與大數(shù)據(jù)協(xié)同創(chuàng)新中心，廣西 桂林 541004)

1 引言

現(xiàn)有的網(wǎng)絡(luò)中，單個控制器已經(jīng)無法滿足網(wǎng)絡(luò)需求，控制器負(fù)載過高導(dǎo)致網(wǎng)絡(luò)性能下降。軟件定義網(wǎng)絡(luò)SDN(Software Define Network)可以很好地解決這些問題。軟件定義網(wǎng)絡(luò)(SDN)是一種新型的網(wǎng)絡(luò)架構(gòu)，其核心是將交換機(jī)網(wǎng)絡(luò)的控制平面和數(shù)據(jù)平面分離[1]，交換機(jī)只負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，控制功能由控制器來負(fù)責(zé)，此外，SDN還可利用控制平面的北向接口進(jìn)行編程，大幅提高了網(wǎng)絡(luò)的靈活性。本文在SDN架構(gòu)中，利用改進(jìn)的k-means++算法對網(wǎng)絡(luò)進(jìn)行劃分，相比k-means算法的劃分結(jié)果要更均衡，在成本相同的情況下負(fù)載差異度更低，從而得出多控制器部署的最佳方案；然后利用網(wǎng)絡(luò)流量均衡算法，對多條路徑轉(zhuǎn)發(fā)的情況采取流量均衡策略，使流量分配更均衡，從而大幅提高網(wǎng)絡(luò)的性能。

2 相關(guān)研究

針對多控制器的部署和網(wǎng)絡(luò)流量均衡問題，相關(guān)研究人員提出了許多解決方案。覃匡宇等[1]就受時延和容量限制的多控制器部署問題，提出在譜聚類的基礎(chǔ)上，為聚類算法增加均衡部署的目標(biāo)函數(shù)，并對多控制器部署算法引入懲罰函數(shù)來防止出現(xiàn)孤立點。Das等[2]基于Steiner樹的控制器間延遲模型，提出了一個多目標(biāo)整數(shù)線性規(guī)劃方法，以推導(dǎo)無故障時控制器優(yōu)化配置的同步代價場景，以及對單鏈路故障的恢復(fù)能力。Yang等[3]研究了單鏈路和多鏈路故障下的SDN控制器配置問題。張棟等[4]研究了分層分布式控制平面控制器配置問題，采用多級k路開關(guān)劃分算法對大系統(tǒng)進(jìn)行劃分，以擴(kuò)展網(wǎng)絡(luò)拓?fù)洹hen等[5]提出了一種新的社區(qū)檢測控制器部署方法，借助復(fù)雜網(wǎng)絡(luò)分析理論，將待部署控制器的網(wǎng)絡(luò)拓?fù)湟暈橐粋€由多個社區(qū)組成的網(wǎng)絡(luò)，然后在每個社區(qū)中選擇一個合適的位置放置控制器，避免了全局部署的復(fù)雜性。史文根等[6]提出了一種控制器的放置和調(diào)整策略，主要包括用于初始控制器配置的遺傳算法和平衡控制域算法，以及一種動態(tài)在線調(diào)整算法，即長期動態(tài)控制中的在線調(diào)整算法。魯垚光等[7]提出了一種基于鏈路偏好的隨機(jī)路由算法和2種流調(diào)度算法，實現(xiàn)了動態(tài)負(fù)載均衡和節(jié)能。Lu等[8]根據(jù)目標(biāo)將控制器配置問題分為延遲、可靠性、成本和多目標(biāo)4個方面，并分析了不同應(yīng)用場景下的具體算法。Wang等[9]利用帶內(nèi)環(huán)境，即所有交換機(jī)通過專用交換機(jī)連接到一個控制器的設(shè)計，設(shè)計了一個由負(fù)載收集器、負(fù)載平衡器和交換機(jī)遷移器組成的負(fù)載調(diào)整機(jī)制。Wang等[10]提出了一種同時考慮負(fù)載平衡、連通性和延遲的多控制器布局算法。

上述多控制器部署及網(wǎng)絡(luò)負(fù)載均衡方案均未考慮拓?fù)渲械木W(wǎng)絡(luò)帶寬及時延。因此，本文將鏈路帶寬和傳輸延遲作為網(wǎng)絡(luò)邊的權(quán)重，針對網(wǎng)絡(luò)對于控制器負(fù)載均衡的需求，利用負(fù)載差異度來表示控制器所管理交換機(jī)個數(shù)的差異程度，得出最優(yōu)的多控制器部署策略。

3 控制器部署模型

本文通過改進(jìn)的k-means++聚類算法對多控制器進(jìn)行劃分，所得到的控制器的部署位置是根據(jù)某些規(guī)則在交換機(jī)節(jié)點中選出的，所以將控制器和交換機(jī)之間的時延理想化為零，只考慮交換機(jī)之間的時延。

將SDN網(wǎng)絡(luò)建模為一個無向圖G=(V,E)，其中，V表示交換機(jī)集合，E表示交換機(jī)間鏈路的集合。聚類算法將網(wǎng)絡(luò)劃分為k類，每一類的交換機(jī)僅由一個控制器控制，即網(wǎng)絡(luò)中需要k個控制器。設(shè)定網(wǎng)絡(luò)中交換機(jī)的個數(shù)為M，控制器j所管理的交換機(jī)集合表示為CVj，每個控制器所能管理的交換機(jī)上限為n個[1]。

交換機(jī)集合表示如式(1)所示：

V={v1,v2,…,vM}

(1)

控制器的集合表示如式(2)所示：

C={c1,c2,…,ck}

(2)

控制器j所管理的交換機(jī)如式(3)所示：

CVj={vi|vi∈V,vi由控制器j管理,

1≤i≤M,1≤j≤k}

(3)

3.1 多控制器部署算法

k-means算法是一種經(jīng)典的無監(jiān)督聚類算法，其核心思想如下所示：首先隨機(jī)產(chǎn)生k個點作為網(wǎng)絡(luò)中k個類的聚類中心，計算圖中所有點到這k個聚類中心的距離，將這些點劃分到距離最近的一個聚類中心所屬的類中，完成第1次劃分。隨后在第1次劃分中所得的k個類中重新選擇聚類中心，再按第1次的方法重新計算并歸類，至結(jié)果不發(fā)生變化為止[3]。

k-means算法存在一些缺陷，首先，算法的k值需要預(yù)先設(shè)定，然后算法根據(jù)設(shè)定的值來進(jìn)行分類。但是，在實際的大型網(wǎng)絡(luò)中，網(wǎng)絡(luò)復(fù)雜，很難在初始時便確定聚類個數(shù)，所以預(yù)先設(shè)定k值容易導(dǎo)致設(shè)定錯誤，從而導(dǎo)致劃分結(jié)果并不是最優(yōu)結(jié)果。其次，k-means算法起初是隨機(jī)選擇聚類中心的，而這個初始的聚類中心則是后續(xù)計算的基礎(chǔ)，所以對結(jié)果的影響較大，容易造成初始得到的聚類中心不佳從而導(dǎo)致劃分結(jié)果不均衡。最后，聚類的劃分以迭代的方式進(jìn)行，若網(wǎng)絡(luò)較復(fù)雜，則需要多次計算，從而導(dǎo)致算法開銷加大[5]。

在網(wǎng)絡(luò)的實際劃分中，k值代表了將網(wǎng)絡(luò)劃分為k個類，而在SDN網(wǎng)絡(luò)中也可代表需要k個控制器。將交換機(jī)和控制器之間的時延問題抽象為點到聚類中心的距離問題，即抽象為圖的最短路徑的問題。

對于k-means算法中隨機(jī)選擇聚類中心而導(dǎo)致結(jié)果不一定最優(yōu)的問題，研究人員提出一種改進(jìn)算法k-means++。在聚類中心的選擇上，k-means++算法將距離較遠(yuǎn)的節(jié)點作為初始聚類中心，并且這個節(jié)點是從已有的點中選擇的。然后計算圖中其他點到此聚類中心的距離，距離越大則下次迭代時作為新的聚類中心的概率就越大，至聚類中心不再發(fā)生變化，則完成初始聚類中心的選擇。隨后對于網(wǎng)絡(luò)的劃分步驟與k-means算法的相同。

k-means++算法改良了k-means算法對于初始聚類中心選擇過于隨機(jī)的問題，通過多步計算得到初始聚類中心，提高了算法的準(zhǔn)確度。但是，k-means++算法并未考慮網(wǎng)絡(luò)中邊的權(quán)重，容易造成某條鏈路流量過高，負(fù)載過大，所以還要加入其它約束條件。

本文提出一種改進(jìn)的k-means++算法對多控制器進(jìn)行劃分，該算法將鏈路帶寬和傳輸延遲作為網(wǎng)絡(luò)邊的權(quán)重，即點與點之間的距離。交換機(jī)不同，所擁有的帶寬也不同。而交換機(jī)在圖中所連接的交換機(jī)個數(shù)不同，傳輸延遲也不同。本文按節(jié)點的度來衡量，度越大，則所連接的點越多，即所連的交換機(jī)越多，傳輸延遲越大，邊的權(quán)重如式(4)所示:

α*bw+β*delay

(4)

其中,bw為鏈路帶寬，delay為傳輸延遲，α與β是2個因素的權(quán)值。同時，針對網(wǎng)絡(luò)對于控制器負(fù)載均衡的需求，本文用負(fù)載差異度來表示控制器所管理交換機(jī)個數(shù)的差異程度。計算方法如式(5)所示：

(5)

3.2 網(wǎng)絡(luò)流量均衡算法

本文提出一種基于存儲桶權(quán)重的多路徑網(wǎng)絡(luò)流量均衡算法。首先通過深度優(yōu)先搜索算法得出網(wǎng)絡(luò)中存在的所有路徑，然后根據(jù)路徑成本實施流量均衡策略。本文在計算路徑成本時，參考了OSPF(Open Shortest Path First)協(xié)議中對接口成本的計算方法。成本與帶寬成反比。首先計算單條路徑的成本，然后累加求和得出多條路徑的成本，最后計算每條路徑的存儲桶權(quán)重。在OpenFlow協(xié)議中，存儲桶權(quán)重越高，優(yōu)先級越高，即優(yōu)先選擇存儲桶權(quán)重高的路徑。

單條路徑的成本sw的計算公式如式(6)所示：

sw=1/bw(Mbps)

(6)

設(shè)有m條路徑，則其總成本SW的計算公式如式(7)所示：

(7)

單條路徑的存儲桶權(quán)重(cw)的計算公式如式(8)所示：

(8)

由以上公式可得，路徑成本越低，所得存儲桶權(quán)重越高，在OpenFlow協(xié)議中，存儲桶權(quán)重越高，優(yōu)先級越高。在流量均衡策略中，優(yōu)先選擇優(yōu)先級高的路徑。

4 實驗與分析

4.1 多控制器部署

本文將SDN多控制器和交換機(jī)之間的關(guān)系抽象為無向連通圖，將控制器和交換機(jī)之間最小時延的問題建模為節(jié)點之間最短路徑的問題。所選用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1和圖2所示。

Figure 1 Biznet topology圖1 Biznet拓?fù)?/p>

Figure 2 Claranet topology圖2 Claranet拓?fù)?/p>

k-means算法和本文提出的算法對2個網(wǎng)絡(luò)拓?fù)涞膭澐纸Y(jié)果圖如圖3～圖6所示。

Figure 3 Partition result of Biznet by k-means(k=4)圖3 k-means對Biznet劃分結(jié)果(k=4)

Figure 4 Partition result of Biznet by the proposed algorithm(k=4)圖4 本文算法對Biznet劃分結(jié)果(k=4)

Figure 5 Partition result of Claranet by the proposed algorithm (k=3)圖5 本文算法對Claranet劃分結(jié)果(k=3)

Figure 6 Partition result of Claranet by k-means(k=4)圖6 k-means對Claranet劃分結(jié)果(k=4)

Figure 7 Comparison of Biznet network load difference圖7 Biznet網(wǎng)絡(luò)負(fù)載差異度對比

Figure 8 Comparison of Claranet network load difference圖8 Claranet網(wǎng)絡(luò)負(fù)載差異度對比

根據(jù)算法劃分結(jié)果和負(fù)載差異度的計算公式，得出每個結(jié)果的負(fù)載差異度，將2種算法進(jìn)行比較得出最優(yōu)的多控制器部署策略。

?帕諾斯·艾烈珀洛斯:《基提翁的芝諾和莊子的德性與幸福》，彭榮譯，《商丘師范學(xué)院學(xué)報》2015年第1期。

實驗所得網(wǎng)絡(luò)負(fù)載差異度如圖7和圖8所示。

對于聚類中心k值的選取，本文采用負(fù)載均衡度作為基本衡量指標(biāo)，綜合部署成本、實際流量等情況選取最佳k值。

通過實驗分析可得，本文提出的算法對Claranet拓?fù)溥M(jìn)行聚類時，由于算法在選擇初始聚類中心點時進(jìn)行了改進(jìn)，所以負(fù)載差異度較k-means的小。在劃分為3、4個類時，即k=3、k=4時，k-means和本文算法的負(fù)載均衡度均為下降趨勢，但在劃分類增多時，其負(fù)載均衡度反而會上升，但本文算法的負(fù)載均衡度始終比k-means的要小。由實驗結(jié)果可知，對于Claranet拓?fù)涞膭澐郑疚乃惴▽⑵鋭澐譃?個類和4個類時的負(fù)載均衡度相似，k值代表網(wǎng)絡(luò)中控制器的個數(shù)，k=3比k=4要減少一個控制器，即成本更低。

4.2 網(wǎng)絡(luò)流量均衡

本文采用Mininet對上述Biznet網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真實驗。控制器采用ryu控制器，主機(jī)為h1和h2。

實驗假設(shè)主機(jī)h1為客戶端，h2為服務(wù)端。觀察拓?fù)淇傻胔1和h2傳送數(shù)據(jù)的線路有2條，分別為h1-S12-S10-h2(路徑1)和h1-S12-S11-S10-h2(路徑2)。反之同理。故本次仿真實驗選擇S10來觀察數(shù)據(jù)傳送情況，以分析網(wǎng)絡(luò)中流量均衡情況。

首先令客戶端h1向h2發(fā)送5個數(shù)據(jù)包。h1傳送的數(shù)據(jù)包如圖9所示，h2接收的數(shù)據(jù)包如圖10所示。

Figure 9 Data packets transfered by h1圖9 h1傳送數(shù)據(jù)包

Figure 10 Data packets received by h2圖10 h2接收數(shù)據(jù)包

查看交換機(jī)S12端口的流表信息(如圖11所示)和組表信息(如圖12所示)，分析數(shù)據(jù)傳送是否成功。

Figure 11 S12 flow table content of switch圖11 交換機(jī)S12流表內(nèi)容

Figure 12 S12 group table content of switch
圖12 交換機(jī)S12組表內(nèi)容

Figure 13 S12 port data of switch 圖13 交換機(jī)S12端口數(shù)據(jù)

由圖11和圖12的交換機(jī)S12端口的流表和組表數(shù)據(jù)可知，控制器下發(fā)了2個流給交換機(jī)來實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，其中的group值與組表中的group值相同，表明流操作是由ID為96196854的組進(jìn)行的，且數(shù)據(jù)傳送成功。

同時通過組表信息可得端口1的存儲桶權(quán)重為7，端口2的存儲桶權(quán)重為3，2個端口存儲桶權(quán)重比值為7/3≈2.33。由圖13的交換機(jī)S12端口數(shù)據(jù)可知，端口1發(fā)送數(shù)據(jù)包(tx pkts)個數(shù)為2 062 375，端口3發(fā)送數(shù)據(jù)包(tx pkts)個數(shù)為966 178，比值為2062375/966178≈2.13。

綜上所述，在網(wǎng)絡(luò)流量均衡的策略下，網(wǎng)絡(luò)根據(jù)存儲桶權(quán)重進(jìn)行分配，可以使數(shù)據(jù)包均衡地在網(wǎng)絡(luò)上進(jìn)行傳送，從而不會出現(xiàn)某一條路徑流量過大、負(fù)載過高導(dǎo)致網(wǎng)絡(luò)性能下降的情況。

5 結(jié)束語

本文通過改進(jìn)的k-means++聚類算法將網(wǎng)絡(luò)劃分為多類，將鏈路帶寬和傳輸延遲作為無向圖邊的權(quán)重引入聚類算法，得出劃分結(jié)果后，再通過負(fù)載差異度的計算分析和控制器成本的綜合考量，得出最優(yōu)的多控制器部署方案。隨后通過網(wǎng)絡(luò)流量均衡算法，使數(shù)據(jù)包在有多條路徑可選擇的情況下合理選擇傳送路徑，使網(wǎng)絡(luò)中各個路徑的負(fù)載均衡，避免因大量數(shù)據(jù)包涌入同一端口而導(dǎo)致網(wǎng)絡(luò)性能下降等問題。

未來可以在流量均衡策略中增加多個約束條件，而不是只根據(jù)存儲桶權(quán)重來決定優(yōu)先級。