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

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

1 引言

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

2 相關研究

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

上述多控制器部署及網絡負載均衡方案均未考慮拓撲中的網絡帶寬及時延。因此，本文將鏈路帶寬和傳輸延遲作為網絡邊的權重，針對網絡對于控制器負載均衡的需求，利用負載差異度來表示控制器所管理交換機個數的差異程度，得出最優(yōu)的多控制器部署策略。

3 控制器部署模型

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

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

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

V={v1,v2,…,vM}

(1)

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

C={c1,c2,…,ck}

(2)

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

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

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

(3)

3.1 多控制器部署算法

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

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

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

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

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

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

α*bw+β*delay

(4)

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

(5)

3.2 網絡流量均衡算法

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

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

sw=1/bw(Mbps)

(6)

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

(7)

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

(8)

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

4 實驗與分析

4.1 多控制器部署

本文將SDN多控制器和交換機之間的關系抽象為無向連通圖，將控制器和交換機之間最小時延的問題建模為節(jié)點之間最短路徑的問題。所選用的網絡拓撲結構如圖1和圖2所示。

Figure 1 Biznet topology圖1 Biznet拓撲

Figure 2 Claranet topology圖2 Claranet拓撲

k-means算法和本文提出的算法對2個網絡拓撲的劃分結果圖如圖3～圖6所示。

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

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

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

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

Figure 7 Comparison of Biznet network load difference圖7 Biznet網絡負載差異度對比

Figure 8 Comparison of Claranet network load difference圖8 Claranet網絡負載差異度對比

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

?帕諾斯·艾烈珀洛斯:《基提翁的芝諾和莊子的德性與幸?！罚順s譯，《商丘師范學院學報》2015年第1期。

實驗所得網絡負載差異度如圖7和圖8所示。

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

通過實驗分析可得，本文提出的算法對Claranet拓撲進行聚類時，由于算法在選擇初始聚類中心點時進行了改進，所以負載差異度較k-means的小。在劃分為3、4個類時，即k=3、k=4時，k-means和本文算法的負載均衡度均為下降趨勢，但在劃分類增多時，其負載均衡度反而會上升，但本文算法的負載均衡度始終比k-means的要小。由實驗結果可知，對于Claranet拓撲的劃分，本文算法將其劃分為3個類和4個類時的負載均衡度相似，k值代表網絡中控制器的個數，k=3比k=4要減少一個控制器，即成本更低。

4.2 網絡流量均衡

本文采用Mininet對上述Biznet網絡拓撲進行仿真實驗?？刂破鞑捎胷yu控制器，主機為h1和h2。

實驗假設主機h1為客戶端，h2為服務端。觀察拓撲可得h1和h2傳送數據的線路有2條，分別為h1-S12-S10-h2(路徑1)和h1-S12-S11-S10-h2(路徑2)。反之同理。故本次仿真實驗選擇S10來觀察數據傳送情況，以分析網絡中流量均衡情況。

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

Figure 9 Data packets transfered by h1圖9 h1傳送數據包

Figure 10 Data packets received by h2圖10 h2接收數據包

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

Figure 11 S12 flow table content of switch圖11 交換機S12流表內容

Figure 12 S12 group table content of switch
圖12 交換機S12組表內容

Figure 13 S12 port data of switch 圖13 交換機S12端口數據

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

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

綜上所述，在網絡流量均衡的策略下，網絡根據存儲桶權重進行分配，可以使數據包均衡地在網絡上進行傳送，從而不會出現某一條路徑流量過大、負載過高導致網絡性能下降的情況。

5 結束語

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

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