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

侯曉婷

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

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

侯曉婷

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

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

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

0 引言

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

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

1 SDN系統(tǒng)架構

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

圖1 SDN網絡架構圖

圖2 應用接口模塊

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

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

2 H-Dijkstra算法介紹

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

圖3 H-Dijkstra算法流程圖

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

(2)設D=(V,A,W)是一個非負權網絡，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)設定的動態(tài)負載均衡閾值φ比較，當檢測到負載均衡參數(shù)σ(t)超過動態(tài)負載均衡閾值φ，則觸發(fā)并行動態(tài)調度策略對負載的路徑選擇進行動態(tài)調整，將超過部分的數(shù)據(jù)流調度到負載較小的節(jié)點上。其中負載均衡參數(shù)σ(t)用方差的形式表示：

(7)

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

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

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

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

圖4 仿真測試結構

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

圖5 各主機間權重矩陣圖

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

圖6 仿真網絡拓撲結構圖

(1)Floodlight控制器遍歷每臺主機，每臺主機遍歷整個網絡，可以得到從節(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ù)流適中，沒有超過所設定的閾值120時，選擇S5-S2-S3-S8路徑進行數(shù)據(jù)流傳輸。一旦負載均衡參數(shù)σ(t)>φ，負載發(fā)生傾斜，控制器會觸發(fā)并運行動態(tài)調整策略，將后續(xù)數(shù)據(jù)流調度到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搭建網絡拓撲圖，選用Floodlight控制器，實現(xiàn)最優(yōu)路徑的選擇，從而達到負載均衡的目的。通過性能檢測，驗證H-Dijkstra算法的可行性和高效性。

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

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

圖7 負載均衡對比圖

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

圖8 速率對比圖

5 結論

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

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

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

[3] 徐秋伊. 基于SDN的路由映射算法的設計與實現(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].計算機應用研究,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.微型機與應用，2017,36(24)：65-68.

2017-06-27)

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