基于軟件定義網(wǎng)絡的數(shù)據(jù)中心網(wǎng)絡負載均衡算法研究*

樊自甫，張 丹，李 書

(重慶郵電大學通信與信息工程學院，重慶 400065)

1 引言

傳統(tǒng)的數(shù)據(jù)中心采用專用的負載均衡設備實現(xiàn)網(wǎng)絡資源的有效利用，存在設備成本昂貴和可擴展性差等問題，而基于軟件定義網(wǎng)絡SDN(Software Defined Networking)[1,2]的集中化方式能夠簡化網(wǎng)絡管理，降低運營成本。對于負載均衡技術而言，軟件定義網(wǎng)絡提供了一種成本低廉、靈活性強的流量管理。SDN是一種新型的網(wǎng)絡架構，采用了集中式的控制平面和分布式的數(shù)據(jù)平面，兩個平面相互分離。隨著數(shù)據(jù)中心在全球范圍內開始得到廣泛的應用，數(shù)據(jù)中心流量也急劇增長，傳統(tǒng)數(shù)據(jù)中心網(wǎng)絡存在運行效率低、鏈路利用率低、易擁塞等問題，而下一代網(wǎng)絡技術(如SDN技術)的出現(xiàn)為數(shù)據(jù)中心網(wǎng)絡當前的問題提供了解決方案。然而，基于SDN 的數(shù)據(jù)中心網(wǎng)絡存在著鏈路負載分布不均勻的的問題，解決基于SDN的數(shù)據(jù)中心網(wǎng)絡負載均衡問題能有效地提高網(wǎng)絡資源利用率，降低設備管理復雜度。

目前根據(jù)對流的傳輸方式的不同，可以將基于SDN的負載均衡算法分為以下三種：

第一種是流分割后再傳輸方法。如文獻[3]提出的流分割策略，將控制器匹配到的大流進行分割后再進行傳輸。文獻[4]根據(jù)Fat-Tree拓撲的特征，將路徑分為上行和下行路徑，并根據(jù)下一跳鏈路負載情況選擇最佳路徑，并當檢測到大流時將其進行分割，再將其分配到路徑中。該類方案需要對大流進行分割，且重路由僅考慮了下一跳，可能導致網(wǎng)絡負載不均衡，甚至擁塞。

第二種是流聚合后再傳輸方法。針對當前數(shù)據(jù)中心網(wǎng)絡中主要是針對大流進行調度容易產(chǎn)生小流擁塞的問題，文獻[5]提出了MiceTrap方案，該方案將網(wǎng)絡中的小流聚合后，再根據(jù)計算的路徑權重對聚合后的流進行多路徑轉發(fā)。對流進行分割或聚合后再進行負載均衡，雖然能將負載分布得更為均勻，但沒有高效的方案解決包失序的問題。

第三種是流透明傳輸方法，也是當前負載均衡的主流方案。例如，文獻[6]提出了模糊綜合評估機制FSEM(Fuzzy Synthetic Evaluation Mechanism)實現(xiàn)路徑負載均衡。文獻[7]提出了基于數(shù)據(jù)中心網(wǎng)絡Fat-Tree拓撲的動態(tài)負載均衡DLB(Dynamic Load Balancing)算法，通過單跳貪婪策略為最大的流選擇最優(yōu)下一跳鏈路，該算法僅通過單跳貪婪策略為流量選路，難以避免算法的局限性，從而引發(fā)網(wǎng)絡擁塞。文獻[8]針對數(shù)據(jù)中心網(wǎng)絡的折疊式Clos網(wǎng)絡架構提出了選擇性隨機負載均衡SRL(Selective Randomized Load Balancing)和FlowFit兩個不同的實現(xiàn)方案。SRL是對隨機負載均衡的增強，類似于等價多路徑ECMP(Equal Cost MultiPath)的隨機路由[9]，但并不是隨機選擇一條路徑，而是隨機選擇兩條路徑并將最大的流分配到負載最低的路徑中。文獻[10]提出了負載均衡算法LABERIO，該方案采用最大最小剩余帶寬法為流量選擇最佳下一跳鏈路，將最高負載鏈路上的最大的流調度到負載最小的鏈路上。

綜上所述，當前的負載均衡方案主要是直接將最高負載鏈路上的最大流調度到最低負載鏈路，并沒有考慮整條鏈路的負載情況，可能由于瓶頸鏈路而造成局部擁塞。同時，直接對鏈路上的最大流進行調度，不僅可選路徑少，甚至可能由于頻繁調度大流，導致網(wǎng)絡性能下降。針對上述算法存在的一些不足，本文提出了一種基于SDN的負載均衡算法，該算法對容易引起網(wǎng)絡擁塞的大流進行調度，將高負載鏈路的流調度到低負載鏈路，以降低最大鏈路負載，并使整個網(wǎng)絡的鏈路負載盡量均衡。

2 負載均衡算法設計

2.1 算法思路

數(shù)據(jù)中心網(wǎng)絡的流量具有局部性和動態(tài)性、分布不均勻、明顯的大小流等特征，本文充分利用SDN 網(wǎng)絡架構的集中式控制優(yōu)勢，提出一種基于SDN的數(shù)據(jù)中心網(wǎng)絡負載均衡算法。具體的算法流程如圖1所示。

Figure 1 Flow chart of load balancing scheduling圖1 負載均衡調度流程圖

首先，控制器通過鏈路層發(fā)現(xiàn)協(xié)議LLDP(Link Layer Discovery Protocol)獲取并更新全局網(wǎng)絡拓撲。然后，控制器向OpenFlow交換機發(fā)送OFPT_STATS_REQUEST消息，以獲取所需的鏈路統(tǒng)計信息和流的統(tǒng)計信息。根據(jù)獲取的鏈路統(tǒng)計信息，控制器進一步為網(wǎng)絡中的路徑設置一個權重，選擇權重最小的路徑對流進行傳輸。其次，為了衡量網(wǎng)絡負載均衡程度，進一步設置一個負載均衡度。最后，根據(jù)調度的流的大小和路徑當前負載狀況，選取合適的大流進行調度。若該鏈路上存在多條滿足條件的大流，則優(yōu)先調度更大的流。當流調度和負載均衡完成后，對路徑的權值進行更新。

2.2 負載均衡算法實現(xiàn)

2.2.1 算法模型

網(wǎng)絡描述：給定SDN網(wǎng)絡拓撲加權圖G=(V,E)，其中V={v1,v2,…,vn}為網(wǎng)絡鏈路中的非空節(jié)點集，E={e1,e2,…,en}為各節(jié)點之間的鏈路集。數(shù)據(jù)包從源節(jié)點S傳輸?shù)侥康慕Y點D的路徑記為P，且路徑P由m條鏈路構成，記為P={l1,l2,…,lm}。網(wǎng)絡中共有n條鏈路，拓撲中每條鏈路的負載分別為{L1,L2,…,Ln}。

(1)

LMax=max{L1,L2,…,Ln}

(2)

LFi=1-Li

(3)

式(1)定義負載為當前已占用的鏈路帶寬百分比。其中，Li表示鏈路i的負載，Bi表示鏈路i的已占用帶寬，Ci表示鏈路i的最大可用帶寬。由式(2)可知網(wǎng)絡中的最大鏈路負載為LMax，而鏈路的空閑負載可用式(3)表示。由式(3)可看出第i條鏈路的空閑負載為LFi。

2.2.2 算法流程

(1)路徑選擇。

為了均衡鏈路負載和網(wǎng)絡流量，避免流量在某條鏈路過度集中和鏈路擁塞的產(chǎn)生，首先需要將路徑的空閑帶寬作為路徑權重的考慮因素。同時，為了使整個網(wǎng)絡鏈路負載和流量分布更均勻，可將路徑中所有鏈路負載的標準差作為路徑權重另一個考慮因素。本文目標是最小化最大鏈路負載。

(4)

由式(4)可計算出路徑權重，其中WPath表示路徑權重，LFi表示鏈路i上的空閑負載。由式(4)可知，路徑權重WPath是路徑空閑負載的標準差和平均值比值。路徑平均空閑負載越大，路徑權重WPath越小，表明該路徑平均可用帶寬越大，傳輸性能越好。標準差越小，路徑權重WPath越小，表明該路徑負載離散程度小，越不易引發(fā)局部鏈路擁塞，該條路徑傳輸性能越好。

在數(shù)據(jù)傳輸過程中還需要進一步考慮路徑跳數(shù)，因此需要對路徑的選擇進行一定的約束。當控制器為流計算路徑時，首先檢測源主機與目的主機是否與同一邊緣層交換機相連。若連接到相同的邊緣層交換機，則將路徑跳數(shù)限制為一跳。若連接的是不同的邊緣層交換機，則優(yōu)先將流轉發(fā)到跳數(shù)較少的路徑中，即拓撲中的多條最短等價路徑。當所有等價路徑中鏈路負載已超過鏈路負載門限值時，再將流傳輸?shù)狡溆嗵鴶?shù)較多的等價路徑中。對于跳數(shù)的限定有效保證了流的傳輸時延。路徑選擇算法如算法1所示。

算法1路徑選擇算法

Input：Network topology,information of link state,information of flow state。

Output：the Path。

1 forFr← the rate of flow do

2 ifFr>δ

3elephant_flow←the flow is recorded as a stream;

4 forelephant_flow

5Path←Calculate all paths between the source and destination host;

6 for all Path

7LFi←Idle load in a link;

8m←Number of links in a path;

11WPath=σ/mean;

12hop←hop in a path;

13 if connected to the same edge switch

14 hop←1;

15 else if

16Path_List←the path hop in ascending order;

17 forli←Path_List

18 ifli<ε

19Path_Select←the least number of hops and small weight;

20 else if

21Path_Delete←Remove congestion link;

22Path_List←the least number of hops and small weight;

23 end for

24 end if

25 end for

26 end for

27 end if

28 end for

(2)負載均衡調度。

當處于流量高峰期時，由于大量突發(fā)性大流的存在，網(wǎng)絡的某些鏈路可能會處于高負載狀態(tài)，導致鏈路負載不均勻。因此，設定一個負載均衡度ρ用于判定當前鏈路負載是否均勻、網(wǎng)絡中是否存在高負載鏈路。

整個網(wǎng)絡的鏈路平均負載Lavg為：

(5)

全網(wǎng)負載均衡度ρ的定義如下：

ρ=Lavg/LMax

(6)

則網(wǎng)絡中某條鏈路的負載均衡度ρ′為：

ρ′=Lavg/Li

(7)

由式(6)可以看出，ρ是鏈路負載的平均值與最大鏈路負載的比值。ρ越接近1，表明網(wǎng)絡中負載越均勻，ρ越接近0，表明網(wǎng)絡中負載差異非常大，需要對最大鏈路負載進行調整。本文設定了一個負載均衡度閾值θ用于判斷鏈路的負載均衡程度，并決定是否需要對流進行調度。當負載均衡度閾值過大時，容易導致對流的頻繁調度，若負載均衡度閾值太小，則容易導致網(wǎng)絡負載不均衡。針對閾值θ的取值，通過測量不同θ與網(wǎng)絡吞吐量的關系選取了最佳θ值。

(3)調度流選取。

OpenFlow控制器可以向交換機發(fā)送查詢請求消息，從交換機獲取網(wǎng)絡流量和鏈路等相關的統(tǒng)計信息，如收發(fā)字節(jié)數(shù)、收發(fā)數(shù)據(jù)包、統(tǒng)計時間周期等。因此，可以通過周期性監(jiān)測交換機傳輸流的總字節(jié)數(shù)和統(tǒng)計周期來對大小流進行判定。流的大小可用式(8)求出。

K=(Mt+T-Mt)/T

(8)

其中，Mt是交換機在t時刻接收到的流字節(jié)數(shù)，Mt+T是交換機在t+T時刻接收到的流字節(jié)數(shù)，T為控制器監(jiān)測統(tǒng)計周期。針對流的大小設定一個閾值δ用以區(qū)分大小流。當一條流的大小超過該閾值時，則記錄該流的匹配域并判定該流為大流；否則，判定該流為小流。針對大流閾值的選取，當前并沒有一個明確的規(guī)定。學者們主要是針對不同的網(wǎng)絡與流量狀況，定義不同的大流閾值，一般均是將占用1%～10%鏈路帶寬的流設定為大流，因此本文將占用5%鏈路帶寬的流設為大流。

設一條路徑正在傳輸一條大小為Fr的大流fe，由于路徑的負載逐漸增至最大，導致負載均衡度小于閾值θ，因此需要將路徑POri上的流調度到其它路徑中以均衡全網(wǎng)負載。經(jīng)過路徑權重計算與比較后，最終為大流fe選擇了另一條傳輸路徑PNew。路徑POri中負載最高的鏈路為lOri，負載大小記為LOri，路徑PNew中負載最高的鏈路為lNew，負載大小記為LNew。當對大流fe進行調度時，新路徑PNew的空閑帶寬首先需要滿足其帶寬需求，同時為避免調度大流可能造成的鏈路擁塞，進一步限定了每條鏈路的最高負載，設定了一個鏈路最高負載門限ε，鏈路負載門限設定為鏈路帶寬的80%。在對大流fe調度之前，有必要對流的需求帶寬和鏈路空閑帶寬進行計算，以確定大流fe調度到路徑PNew后是否會導致造成鏈路擁塞或負載過高。因此，調度的流的大小應小于路徑PNew中的最大可用帶寬。即:

(Fr+LNewCNew)/CNew<ε

(9)

其中，CNew表示鏈路lNew的最大帶寬。

則可得Fr需滿足條件：

Fr<εCNew-LNewCNew

(10)

當大流fe調度后，F(xiàn)r還需使新路徑PNew滿足條件：ρ′≥θ，以避免頻繁的流調度，即：

(11)

進一步可將Fr限定條件表示為：

Fr≤CNewLavg/θ-LNewCNew

(12)

考慮本文拓撲狀況，每條鏈路帶寬均為C，F(xiàn)r的范圍最終可化簡為：

(13)

若該鏈路上存在多條滿足調度條件的大流，則優(yōu)先調度最大的流。大流選取算法如算法2所示。

算法2大流選取算法

Input：Network topology,information of link state,information of flow state。

Output：Information of large flow。

1 forLi← the link load do

3Lmax=max{L1,L2,…,Lm};

4ρ=Larg/Lmax;

5 ifρ<θ

6 ifLmax=max{L1,L2,…,Lm}

7Fr←rate of flow in a link;

8 ifFr>σ

9elephant_flow←The flow is recorded as a stream;

10 forelephant_flow

11 ifFr≤(Larg/θ-LNew)*C&&Fr<(ε-LNew)*C

12flow_select←the information of flow;

13 end if

14 end for

15 end if

16 end if

17 end if

18 end for

3 仿真和性能分析

3.1 仿真環(huán)境

為了測試與驗證提出的負載均衡算法的性能，本文采用了Mininet[11]和Ryu[12]控制器作為網(wǎng)絡仿真平臺。實驗主機中采用VMware Workstation作為虛擬機軟件，并安裝兩個Ubuntu 14.04.4 LTS系統(tǒng)。其中，一個系統(tǒng)安裝Mininet，用于模擬OpenFlow網(wǎng)絡環(huán)境和拓撲結構；另一個系統(tǒng)安裝Ryu控制器，并通過指令與Mininet相連，對OpenFlow網(wǎng)絡進行集中式控制。同時，Ryu控制器向上層提供了可編程接口，因此可以使用Python語言實現(xiàn)負載均衡功能。本文模擬數(shù)據(jù)中心網(wǎng)絡拓撲架構，使用Mininet構建了一個4元Fat-Tree拓撲，如圖2所示，共包括20臺OpenFlow交換機和16臺主機，并將網(wǎng)絡中鏈路的帶寬設置為10 Mbps，鏈路均為全雙工鏈路。使用Iperf軟件生成不同速率、大小的數(shù)據(jù)流，仿真網(wǎng)絡環(huán)境流量，并對算法進行性能測試與比較。實驗仿真參數(shù)設置如表1所示。

Table 1 Experimental simulation environment表1 仿真環(huán)境

Figure 2 Four-element Fat-Tree network topology圖2 4元Fat-Tree網(wǎng)絡拓撲結構

3.2 性能分析

在Mininet構建的網(wǎng)絡拓撲環(huán)境下，首先選取合適的負載均衡度閾值，再對本文提出的數(shù)據(jù)中心負載均衡算法DCLB(Load Balancing in Data Center)的性能進行對比與分析，使用平均傳輸時延、鏈路帶寬利用率和負載分布三個性能指標與ECMP、LABERIO算法進行對比。使用Iperf使網(wǎng)絡中的主機互相隨機發(fā)送數(shù)據(jù)包，并將流量速率從2 Mbps逐漸提升到8 Mbps，測量不同負載狀況下，DCLB算法與ECMP、LABERIO算法的平均時延對比，如圖3所示。由圖3可見，三種算法的平均時延均隨著發(fā)包速率的提升而逐漸增加。整體上來看，DCLB算法和LABERIO算法時延更為穩(wěn)定。當發(fā)包速率小于3 Mbps時，網(wǎng)絡中鏈路負載較輕，三種路由算法都能較為穩(wěn)定地傳輸網(wǎng)絡中的數(shù)據(jù)包，平均時延總體也較為穩(wěn)定。

Figure 3 Average delay圖3 平均時延

通過調整Iperf發(fā)包速率，測量了滿負載情況下，核心層交換機與匯聚層交換機之間鏈路的帶寬利用率，如圖4所示。其中，橫坐標表示核心交換機與匯聚層交換機之間的鏈路。由圖4可以看出，ECMP算法的平均鏈路利用率為61.7%，LABERIO算法的平均鏈路利用率為67.2%，DCLB算法的平均鏈路利用率為72.4%，DCLB算法和LABERIO算法的鏈路利用率均優(yōu)于ECMP算法。ECMP算法是隨機選擇路徑，多條大流在同一條鏈路中碰撞，導致Pod內部產(chǎn)生熱點路徑，因此核心交換機與匯聚層交換機鏈路的帶寬利用率較低。而LABERIO算法是基于單跳貪婪策略，且僅在鏈路負載超過門限閾值時實現(xiàn)對流的調度，不能主動均衡鏈路負載，因此在網(wǎng)絡負載較高的情況下，鏈路利用率較低。

Figure 4 Link utilization圖4 鏈路利用率

通過統(tǒng)計控制器中監(jiān)控模塊輸出的交換機狀態(tài)信息，可以獲得網(wǎng)絡中所有核心交換機接收到的字節(jié)數(shù)，用以表征核心交換機之間的負載分布。圖5是拓撲中核心交換機的負載分布。由圖5可以看出，采用DCLB和LABERIO算法時，核心交換機之間的負載分布得更為均勻。在ECMP算法下，核心交換機的負載范圍為[2008,3107] Mbit，平均負載為2 505 Mbit，方差為461.4。在LABERIO算法下，核心交換機的負載范圍為[2503,3014] Mbit，平均負載為2 718 Mbit，方差為254.5。在DCLB算法下，核心交換機的負載范圍為[2638,3006] Mbit，平均負載為2 837 Mbit，方差為157.9。通過方差的比較，可以發(fā)現(xiàn)DCLB算法的負載分布得更加均勻。

Figure 5 Load distribution圖5 負載分布

4 結束語

本文充分利用OpenFlow技術的全局網(wǎng)絡拓撲和集中式控制等特點，通過實時監(jiān)控和統(tǒng)計鏈路與流量的狀態(tài)信息，實現(xiàn)了動態(tài)的鏈路負載均衡，并通過仿真驗證了本文所提算法能有效提高網(wǎng)絡資源利用率，并均衡全網(wǎng)負載。本文的方案尚存在著不足,網(wǎng)絡環(huán)境僅考慮了單控制器和單域的情況，而在多控制器或混合網(wǎng)絡的情況下，如何保證本文提出的負載均衡方案的性能穩(wěn)定是下一步需要完善的地方。

[1] Zuo Qing-yun, Chen Ming, Zhao Guang-song,et al.Research on OpenFlow-based SDN technologies [J].Journal of Software,2013,24(5):1078-1097.(in Chinese)

[2] Nadeau T D,Gray K.SDN:Software defined networks[M]. Sebastopol:O'Reilly Media,Inc,2013.

[3] Braun W,Menth M.Load-dependent flow splitting for traffic engineering in resilient OpenFlow networks[C]∥Proc of 2015 International Conference and Workshops on Networked Systems(NetSys),2015:1-5.

[4] Craig A, Nandy B, Lambadaris I,et al.Load balancing for multicast traffic in SDN using real-time link cost modification[C]∥Proc of 2015 IEEE International Conference on Communications(ICC’15),2015:5789-5795.

[5] Trestian R, Muntean G M,Katrinis K.MiceTrap:Scalable traffic engineering of data center mice flows using OpenFlow[C]∥Proc of 2013 IFIP/IEEE International Symposium on Integrated Network Management(IM 2013),2013:904-907.

[6] Li J,Chang X,Ren Y,et al.An effective path load balancing mechanism based on SDN[C]∥Proc of 2014 IEEE 13th International Conference on Trust,Security and Privacy in Computing and Communications(TrustCom),2014:527-533.

[7] Li Y,Pan D.OpenFlow based load balancing for fat-tree networks with multipath support[C]∥Proc of the 12th IEEE International Conference on Communication(ICC’ 13),2013:1-5.

[8] Sehery W,Clancy T C.Load balancing in data center networks with folded-Clos architectures[C]∥Proc of 2015 1st IEEE Conference on Network Softwarization,2015:1-6.

[9] Xi K,Liu Y,Chao H J.Enabling flow-based routing control in data center networks using probe and ECMP[C]∥Proc of 2011 IEEE Conference on Computer Communications Workshops(INFOCOM WKSHPS),2011:608-613.

[10] Long H,Shen Y,Guo M,et al.LABERIO:Dynamic load-balanced routing in OpenFlow-enabled networks[C]∥Prco of 2013 IEEE 27th International Conference on Advanced Information Networking and Applications(AINA),2013:290-297.

[11] Lantz B,Heller B,Mckeown N.A network in a laptop:Rapid prototyping for software-defined networks[C]∥Proc of ACM Sigcomm Hotnets Workshop,2010:19.

[12] Stancu A L,Halunga S,Vulpe A,et al.A comparison between several software defined networking controllers[C]∥Proc of 2015 12th International Conference on Telecommunication in Modern Satellite,Cable and Broadcasting Services(TELSIKS),2015:223-226.

附中文參考文獻：

[1] 左青云,陳鳴,趙廣松.基于OpenFlow的SDN技術研究[J].軟件學報,2013,24(5):1078-1097.