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

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

1 引言

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

2 相關(guān)研究

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

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

3 控制器部署模型

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

將SDN網(wǎng)絡(luò)建模為一個(gè)無(wú)向圖G=(V,E)，其中，V表示交換機(jī)集合，E表示交換機(jī)間鏈路的集合。聚類算法將網(wǎng)絡(luò)劃分為k類，每一類的交換機(jī)僅由一個(gè)控制器控制，即網(wǎng)絡(luò)中需要k個(gè)控制器。設(shè)定網(wǎng)絡(luò)中交換機(jī)的個(gè)數(shù)為M，控制器j所管理的交換機(jī)集合表示為CVj，每個(gè)控制器所能管理的交換機(jī)上限為n個(gè)[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)典的無(wú)監(jiān)督聚類算法，其核心思想如下所示：首先隨機(jī)產(chǎn)生k個(gè)點(diǎn)作為網(wǎng)絡(luò)中k個(gè)類的聚類中心，計(jì)算圖中所有點(diǎn)到這k個(gè)聚類中心的距離，將這些點(diǎn)劃分到距離最近的一個(gè)聚類中心所屬的類中，完成第1次劃分。隨后在第1次劃分中所得的k個(gè)類中重新選擇聚類中心，再按第1次的方法重新計(jì)算并歸類，至結(jié)果不發(fā)生變化為止[3]。

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

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

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

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

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

α*bw+β*delay

(4)

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

(5)

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

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

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

sw=1/bw(Mbps)

(6)

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

(7)

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

(8)

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

4 實(shí)驗(yàn)與分析

4.1 多控制器部署

本文將SDN多控制器和交換機(jī)之間的關(guān)系抽象為無(wú)向連通圖，將控制器和交換機(jī)之間最小時(shí)延的問(wèn)題建模為節(jié)點(diǎn)之間最短路徑的問(wèn)題。所選用的網(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算法和本文提出的算法對(duì)2個(gè)網(wǎng)絡(luò)拓?fù)涞膭澐纸Y(jié)果圖如圖3～圖6所示。

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

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

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

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

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

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

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

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

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

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

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

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

本文采用Mininet對(duì)上述Biznet網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真實(shí)驗(yàn)?？刂破鞑捎胷yu控制器，主機(jī)為h1和h2。

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

首先令客戶端h1向h2發(fā)送5個(gè)數(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個(gè)流給交換機(jī)來(lái)實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，其中的group值與組表中的group值相同，表明流操作是由ID為96196854的組進(jìn)行的，且數(shù)據(jù)傳送成功。

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

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

5 結(jié)束語(yǔ)

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

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