侯曉婷

(安徽廣播電視臺播控中心，安徽 合肥 230071)

基于SDN的動態(tài)負載均衡最優(yōu)路徑算法研究

侯曉婷

(安徽廣播電視臺播控中心，安徽 合肥230071)

在傳統(tǒng)網(wǎng)絡(luò)中，轉(zhuǎn)發(fā)路徑由各路由節(jié)點的動態(tài)協(xié)議決定，傳統(tǒng)路徑分配算法的全局性差、效率不高，對網(wǎng)絡(luò)負載平衡的考慮不夠，而且管理員難以確定業(yè)務(wù)報文所走路徑。利用SDN改變傳統(tǒng)網(wǎng)絡(luò)對數(shù)據(jù)流控制的方式，提出一種H-Dijkstra負載均衡最優(yōu)路徑算法。該算法在傳統(tǒng)Dijkstra算法的基礎(chǔ)上設(shè)定一個動態(tài)負載均衡閾值，當檢測到負載均衡參數(shù)超過此閾值，則觸發(fā)動態(tài)調(diào)度策略對路徑分配算法進行調(diào)整。通過反復(fù)實驗與傳統(tǒng)網(wǎng)絡(luò)對比分析，結(jié)果表明，本文算法不僅發(fā)揮了SDN在轉(zhuǎn)發(fā)與控制分離架構(gòu)上的速度優(yōu)勢，而且避免了網(wǎng)絡(luò)資源的浪費，提高了網(wǎng)絡(luò)性能。

SDN；負載均衡；Dijkstra；最優(yōu)路徑

0 引言

當前，SDN已成為全球網(wǎng)絡(luò)領(lǐng)域最熱門的研究方向。SDN作為一種數(shù)據(jù)控制分離、軟件可編程的新型網(wǎng)絡(luò)體系架構(gòu)，采用了集中式的控制平面和分布式的轉(zhuǎn)發(fā)平面，控制平面利用控制—轉(zhuǎn)發(fā)通信接口對轉(zhuǎn)發(fā)平面上的網(wǎng)絡(luò)設(shè)備進行集中式的控制，并提供靈活的可編程能力[1]。SDN可以解決傳統(tǒng)網(wǎng)絡(luò)中的以下問題：(1)傳統(tǒng)網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)路徑受各種網(wǎng)絡(luò)協(xié)議控制，而且管理員無法直接操控路徑轉(zhuǎn)發(fā)行為，使得業(yè)務(wù)部署和路徑轉(zhuǎn)發(fā)的效率不高[2]；(2)傳統(tǒng)網(wǎng)絡(luò)技術(shù)中網(wǎng)絡(luò)協(xié)議對轉(zhuǎn)發(fā)行為的影響是固有模式的，比如路由協(xié)議只能靠目的IP地址來進行轉(zhuǎn)發(fā)，且不同情況下的轉(zhuǎn)發(fā)只能對報文進行固定模式的修改，靈活度不高[3]。

相比傳統(tǒng)網(wǎng)絡(luò)，SDN最大的特點是改變了傳統(tǒng)網(wǎng)絡(luò)對數(shù)據(jù)流進行控制的方式。從設(shè)備可編程轉(zhuǎn)變?yōu)榫W(wǎng)絡(luò)可編程，SDN的網(wǎng)絡(luò)可編程性實現(xiàn)的是對整個網(wǎng)絡(luò)的編程而不僅僅是針對單個網(wǎng)絡(luò)節(jié)點。SDN控制器具有全局拓撲，可以計算任意節(jié)點間的路由，并控制轉(zhuǎn)發(fā)路徑[4]。本文利用SDN網(wǎng)絡(luò)的特點及優(yōu)勢，提出一種H-Dijkstra負載均衡最優(yōu)路徑算法，將其運用在SDN網(wǎng)絡(luò)，在提高了整個系統(tǒng)的穩(wěn)定性的同時，保證整體鏈路動態(tài)平衡，避免了局部擁塞，同時將路徑的選擇進行了最優(yōu)化。

1 SDN系統(tǒng)架構(gòu)

近來年，SDN技術(shù)迅猛發(fā)展，提出了至關(guān)重要的網(wǎng)絡(luò)分層耦合概念，包括轉(zhuǎn)發(fā)層、控制層和業(yè)務(wù)層，如圖1所示。數(shù)據(jù)轉(zhuǎn)發(fā)層即物理網(wǎng)絡(luò)設(shè)備、OpenFlow交換機?？刂茖蛹淳W(wǎng)絡(luò)操作系統(tǒng)，它是SDN的核心，包括鏈路發(fā)現(xiàn)、拓撲管理、轉(zhuǎn)發(fā)管理和配置管理等?？刂茖优c轉(zhuǎn)發(fā)層間以一種標準化的協(xié)議來通信，目前OpenFlow協(xié)議最為流行。應(yīng)用層可以開發(fā)各類應(yīng)用業(yè)務(wù)，用戶可以自由選擇網(wǎng)絡(luò)操作系統(tǒng)并開發(fā)自己的網(wǎng)絡(luò)管理軟件和應(yīng)用[5]?？刂茖优c應(yīng)用層之間有一個API模塊。API 模塊由網(wǎng)絡(luò)管理策略、路由選擇和流表下發(fā)組成，如圖2所示。

圖1 SDN網(wǎng)絡(luò)架構(gòu)圖

圖2 應(yīng)用接口模塊

網(wǎng)絡(luò)管理策略是API模塊的核心，負責在控制器上記錄功能模塊所產(chǎn)生的網(wǎng)絡(luò)策略。路由選擇是在掌握了全網(wǎng)拓撲信息的前提下，為用戶訪問選擇一個最優(yōu)路徑。流表下發(fā)是保證控制器產(chǎn)生的流表項成功地下發(fā)到轉(zhuǎn)發(fā)層。

為了提高處理網(wǎng)絡(luò)大數(shù)據(jù)的效率，降低服務(wù)器群的處理壓力，本文采用在SDN網(wǎng)絡(luò)架構(gòu)下對大數(shù)據(jù)的負載進行均衡處理，這種靈活的可編程架構(gòu)也非常適用于負載均衡服務(wù)，并對網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆窂竭M行最優(yōu)化。

2 H-Dijkstra算法介紹

傳統(tǒng)的Dijkstra算法是眾多實現(xiàn)最短路徑的算法中公認的好算法，且有名的OSPF協(xié)議是根據(jù)鏈路狀態(tài)數(shù)據(jù)庫計算出從本路由器到域內(nèi)其他所有路由器的最短路徑，其中SPF最短路徑優(yōu)先算法也是用的Dijkstra算法[6]。本文沿用傳統(tǒng)Dijkstra算法中的精髓思想，并在此算法過程中加入一個動態(tài)負載均衡閾值φ，避免局部承載負載過大而造成不必要的擁塞。通過綜合因素考慮，選擇真正的最優(yōu)路徑。圖3給出了整個H-Dijkstra算法的流程框圖。

圖3 H-Dijkstra算法流程圖

(1)SDN控制器遍歷所有主機，對整個網(wǎng)絡(luò)拓撲有個鏡像，確定每臺主機之間可能的路徑集合，預(yù)先計算出網(wǎng)絡(luò)中所有主機之間兩輛存在的所有路徑，每條路徑包括從源主機到目的主機之間所需要經(jīng)過的所有鏈路，根據(jù)這條路徑上所有鏈路當前可用帶寬/鏈路開銷/距離/費用等為每條路徑生成一個權(quán)重，用此來衡量此路徑的均衡程度。

(2)設(shè)D=(V,A,W)是一個非負權(quán)網(wǎng)絡(luò)，V=(v1,v2,…,vn)，則D中最短(vi,vj)∈A路徑滿足方程：

U1=0

(1)

Uj<φ(j=2,3,…,n)

(2)

Uj=min(Uk+Uj) (j=2,3,…,n)

(3)

如果D從定點v1到其余各頂點最短路徑長的排序為：

Ui1≤Ui2≤…≤Uin

(4)

當i1=1，即U1=0。

(5)

當k>j時，Uik≥Uij，且Wikij≥0，所以Uij≤Uik+Wikij，即：

(6)

(3)通過上述步驟找到源主機到目的主機的最優(yōu)路徑，需要與系統(tǒng)設(shè)定的動態(tài)負載均衡閾值φ比較，當檢測到負載均衡參數(shù)σ(t)超過動態(tài)負載均衡閾值φ，則觸發(fā)并行動態(tài)調(diào)度策略對負載的路徑選擇進行動態(tài)調(diào)整，將超過部分的數(shù)據(jù)流調(diào)度到負載較小的節(jié)點上。其中負載均衡參數(shù)σ(t)用方差的形式表示：

(7)

UA(t)代表服務(wù)器平均負載量，Ui(t)代表服務(wù)器節(jié)點i在時間t時所承載的負載量。當σ(t)<φ時，全部的數(shù)據(jù)流選擇步驟(2)計算出的最優(yōu)路徑中進行傳輸；當σ(t)>φ時，動態(tài)調(diào)整最優(yōu)路徑。

本算法給系統(tǒng)設(shè)定一個平衡度，即動態(tài)負載均衡閾值φ，避免了多個數(shù)據(jù)流選擇同一條最優(yōu)路徑，通過實時計算，這條路徑并非一直都是最優(yōu)路徑，權(quán)重會隨著負載的增加而增加，如果不采取必要的措施，很有可能造成局部擁塞。本文在保證不超過負載均衡閾值φ的前提下，選擇最短路徑提高效率，一旦超過閾值φ，控制器將調(diào)整最短路徑的選擇，最終實現(xiàn)動態(tài)的負載均衡。

3 H-Dijkstra算法具體實現(xiàn)

根據(jù)上述理論分析，具體實施方案采用圖4所示的仿真測試結(jié)構(gòu)，SDN控制器會實時記錄服務(wù)器負載情況。

圖4 仿真測試結(jié)構(gòu)

圖5為一組由帶寬/鏈路開銷/距離/費用等所形成的帶權(quán)鄰接矩陣，用此權(quán)重來衡量每條路徑的均衡程度，作為選擇最優(yōu)路徑的依據(jù)。

圖5 各主機間權(quán)重矩陣圖

根據(jù)圖5矩陣畫出網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖如圖6所示。假設(shè)需要計算節(jié)點S5到節(jié)點S8的最優(yōu)路徑以及所經(jīng)過的各節(jié)點。通過測試計算出動態(tài)負載均衡閾值為120。

圖6 仿真網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖

(1)Floodlight控制器遍歷每臺主機，每臺主機遍歷整個網(wǎng)絡(luò)，可以得到從節(jié)點S5到節(jié)點S8的所有可能路徑：

D(S5-S2-S7-S8)=195

D(S5-S6-S7-S8)=260

D(S5-S6-S3-S8)=290

D(S5-S2-S3-S8)=180

……

(2)根據(jù)H-Dijkstra算法計算出最優(yōu)路徑為S5-S2-S3-S8，當數(shù)據(jù)流適中，沒有超過所設(shè)定的閾值120時，選擇S5-S2-S3-S8路徑進行數(shù)據(jù)流傳輸。一旦負載均衡參數(shù)σ(t)>φ，負載發(fā)生傾斜，控制器會觸發(fā)并運行動態(tài)調(diào)整策略，將后續(xù)數(shù)據(jù)流調(diào)度到S5-S2-S3-S7-S8，此時S5-S2-S3-S7-S8這條路徑作為當前的最優(yōu)路徑進行數(shù)據(jù)流的傳輸，以此類推，以實現(xiàn)整體動態(tài)平衡，避免局部擁塞。

4 實驗測試及分析

本文選用的仿真測試環(huán)境為Ubuntu14.04，在Linux系統(tǒng)下用Mininet搭建網(wǎng)絡(luò)拓撲圖，選用Floodlight控制器，實現(xiàn)最優(yōu)路徑的選擇，從而達到負載均衡的目的。通過性能檢測，驗證H-Dijkstra算法的可行性和高效性。

實驗測試同樣采用圖4所示的仿真測試結(jié)構(gòu)，具體方案采用圖6所示的仿真網(wǎng)絡(luò)拓撲結(jié)構(gòu)。本文選用負載均衡權(quán)重值對比分析H-Dijkstra算法與SPF算法的整體性能差異，通過速率對比分析該算法運用在SDN網(wǎng)絡(luò)架構(gòu)相比運用在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)的優(yōu)勢。

圖7為傳統(tǒng)SPF算法與H-Dijkstra算法的負載均衡對比圖，從圖6可知整個網(wǎng)絡(luò)架構(gòu)共有14條路徑。隨著業(yè)務(wù)請求量的增加，之前所選定的最優(yōu)路徑的權(quán)重會隨之增加，當?shù)竭_動態(tài)負載均衡閾值，H-Dijkstra算法會自動更改所選最優(yōu)路徑，而傳統(tǒng)的SPF算法會造成局部擁塞，最終導(dǎo)致業(yè)務(wù)傳輸速率降低，整個網(wǎng)絡(luò)性能下降。

圖7 負載均衡對比圖

圖8為H-Dijkstra算法在傳統(tǒng)網(wǎng)絡(luò)架構(gòu)與SDN網(wǎng)絡(luò)架構(gòu)的速率對比分析圖，由于采用了靈活的SDN網(wǎng)絡(luò)架構(gòu)，相比傳統(tǒng)網(wǎng)絡(luò)架構(gòu)，SDN能夠集中控制網(wǎng)絡(luò)，對整個網(wǎng)絡(luò)進行編程，方便計算任意端點間的路由，并下發(fā)流表，控制轉(zhuǎn)發(fā)路徑，這種網(wǎng)絡(luò)架構(gòu)方便了網(wǎng)絡(luò)管理，極大地提高了業(yè)務(wù)轉(zhuǎn)發(fā)速率。

圖8 速率對比圖

5 結(jié)論

本文針對經(jīng)典的Dijkstra算法進行研究并優(yōu)化，提出了H-Dijkstra算法，將其用于SDN網(wǎng)絡(luò)架構(gòu)中，此算法可作為內(nèi)部模塊作用于SDN控制器中。本文模擬實際應(yīng)用場景進行對比實驗，證明優(yōu)化算法能夠提高網(wǎng)絡(luò)數(shù)據(jù)速度，并簡化了網(wǎng)絡(luò)操作，具有重要的應(yīng)用價值。

[1] 王勇,匡玉雯.基于SDN的云中心動態(tài)負載均衡方法[J].桂林電子科技大學學報,2015,35(4):321-324.

[2] 匡玉雯,王勇,曾小寶. 基于SDN的一種云服務(wù)流量控制方法研究[J]. 微型機與應(yīng)用,2015,34(4):61-63.

[3] 徐秋伊. 基于SDN的路由映射算法的設(shè)計與實現(xiàn)[D].北京：北京郵電大學,2015.

[4] 魏凱. 基于蟻群算法SDN負載均衡的研究[D]. 長春：吉林大學,2015.

[5] JIANG J R,HUANG H W,LIAO J H,et al.Extending Dijkstra’s shortest path algorithm for software defined networking[C]. Network Operations & Management Symposium,2014,16th Asia-Pacific,2014:1-4.

[6] 王春枝,羅晨,陳宏偉. SDN中基于負載均衡的最優(yōu)路徑分配算法研究[J].計算機應(yīng)用研究,2016,33(8):2462-2466.

Dynamic optical path algorithm based on load balancing for SDN

Hou Xiaoting

(Broadcasting Center of Anhui TV Station,Hefei 230071,China)

In traditional network,the forwarding routes are decided by dynamic protocols on routers. The traditional routing algorithms are no-global optimal,low efficient,and usually ignore load balance issues. And system administrator are unaware of the actual path of each traffic flow. Taking the advantage of SDN’s capability to control data flow,this paper gives a H-Dijkstra load balance optimal routing algorithm. Our algorithm adds one dynamic load balance threshold to traditional Dijkstra algorithm. When load balance metric exceeds the threshold,dynamic adjustment to the algorithm’s parameters will be trigger. Compared with traditional network,experiment result shows that our algorithm,which is benefit from SDN’s architecture to separate forwarding plane with control plane,can avoid the waster of network bandwidth and improve network performance.

software defined network(SDN); load balance; Dijkstra; optimal path

TP301

A

10.19358/j.issn.1674-7720.2017.24.019

侯曉婷.基于SDN的動態(tài)負載均衡最優(yōu)路徑算法研究J.微型機與應(yīng)用，2017,36(24)：65-68.

2017-06-27)

侯曉婷(1968-)，女，本科，工程師，主要研究方向：通信網(wǎng)絡(luò)和網(wǎng)絡(luò)安全。