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

侯曉婷

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

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

侯曉婷

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

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

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

0 引言

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

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

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

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

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

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

網(wǎng)絡(luò)管理策略是API模塊的核心，負(fù)責(zé)在控制器上記錄功能模塊所產(chǎn)生的網(wǎng)絡(luò)策略。路由選擇是在掌握了全網(wǎng)拓?fù)湫畔⒌那疤嵯拢瑸橛脩粼L問(wèn)選擇一個(gè)最優(yōu)路徑。流表下發(fā)是保證控制器產(chǎn)生的流表項(xiàng)成功地下發(fā)到轉(zhuǎn)發(fā)層。

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

2 H-Dijkstra算法介紹

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

圖3 H-Dijkstra算法流程圖

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

(2)設(shè)D=(V,A,W)是一個(gè)非負(fù)權(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從定點(diǎn)v1到其余各頂點(diǎn)最短路徑長(zhǎng)的排序?yàn)椋?/p>

Ui1≤Ui2≤…≤Uin

(4)

當(dāng)i1=1，即U1=0。

(5)

當(dāng)k>j時(shí)，Uik≥Uij，且Wikij≥0，所以Uij≤Uik+Wikij，即：

(6)

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

(7)

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

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

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

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

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

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

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

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

圖6 仿真網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

(1)Floodlight控制器遍歷每臺(tái)主機(jī)，每臺(tái)主機(jī)遍歷整個(gè)網(wǎng)絡(luò)，可以得到從節(jié)點(diǎn)S5到節(jié)點(diǎn)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算法計(jì)算出最優(yōu)路徑為S5-S2-S3-S8，當(dāng)數(shù)據(jù)流適中，沒(méi)有超過(guò)所設(shè)定的閾值120時(shí)，選擇S5-S2-S3-S8路徑進(jìn)行數(shù)據(jù)流傳輸。一旦負(fù)載均衡參數(shù)σ(t)>φ，負(fù)載發(fā)生傾斜，控制器會(huì)觸發(fā)并運(yùn)行動(dòng)態(tài)調(diào)整策略，將后續(xù)數(shù)據(jù)流調(diào)度到S5-S2-S3-S7-S8，此時(shí)S5-S2-S3-S7-S8這條路徑作為當(dāng)前的最優(yōu)路徑進(jìn)行數(shù)據(jù)流的傳輸，以此類推，以實(shí)現(xiàn)整體動(dòng)態(tài)平衡，避免局部擁塞。

4 實(shí)驗(yàn)測(cè)試及分析

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

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

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

圖7 負(fù)載均衡對(duì)比圖

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

圖8 速率對(duì)比圖

5 結(jié)論

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

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

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

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

[4] 魏凱. 基于蟻群算法SDN負(fù)載均衡的研究[D]. 長(zhǎng)春：吉林大學(xué),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中基于負(fù)載均衡的最優(yōu)路徑分配算法研究[J].計(jì)算機(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的動(dòng)態(tài)負(fù)載均衡最優(yōu)路徑算法研究J.微型機(jī)與應(yīng)用，2017,36(24)：65-68.

2017-06-27)

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