基于SDN的胖樹數據中心網絡多路徑負載均衡算法研究

付應輝 劉必果 束永安

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

基于SDN的胖樹數據中心網絡多路徑負載均衡算法研究

付應輝 劉必果 束永安

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

軟件定義網絡SDN(Software Defined Network)通過將網絡設備的控制層與數據層分離解耦，能夠實現網絡的集中控制和流量的靈活轉發，因此被廣泛應用于數據中心等相關領域。在數據中心網絡中，為了提高網絡的帶寬和吞吐量，多采用具有多路徑特性的層次型網絡拓撲結構，如胖樹拓撲結構。然而傳統路由算法對多路徑的支持非常有限，無法充分利用網絡剩余帶寬。重點研究基于SDN的胖樹數據中心網絡多路徑負載均衡算法。利用SDN網絡集中控制的特點，獲取多路徑實時狀態信息，計算各路徑當前可用帶寬，根據數據流的帶寬需求選擇最佳轉發路徑。實驗結果表明，該算法無論在降低網絡傳播時延還是在提高網絡吞吐量等方面都優于傳統路由算法，能夠實現胖樹數據中心網絡的多路徑負載均衡。

軟件定義網絡 SDN 胖樹 數據中心網絡 多路徑負載均衡

0 引 言

軟件定義網絡(SDN)[1]是當前熱門的新型網絡創新架構，其控制層與數據層的分離能夠提供全網信息的集中控制和統一部署，被廣泛應用于數據中心網絡以提高網絡帶寬利用率。數據中心網絡配套各種存儲系統、網絡互連設備，網絡規模龐大。為了實現各服務器之間的高效互聯，數據中心網絡多采用具有多路徑特性的胖樹拓撲結構[2-3]。

傳統的基于IP的等價多路徑路由(ECMP)協議根據數據包的源目的地址計算路由并轉發，雖然支持多路徑協議，但是沒有考慮流對帶寬的需求，也無法感知網絡負載狀態及數據流帶寬需求的變化。僅僅是從具有相同最小代價的路徑中選擇備選路徑，導致該算法有很大的局限性[4]。

目前針對數據中心網絡設計的多路徑解決方案主要有如下幾種：Al-Fares等[5]提出的全局最先匹配算法和模擬退火法；Heller等[6]提出的ElasticTree數據中心網絡能量管理方法，包括貪婪裝箱算法和拓撲感知的啟發式算法。

其中，全局最先匹配算法選擇網絡中第一條滿足流帶寬需求的路徑，算法簡單但是必須獲取所有鏈路信息，而且往往找到的路徑都不是全局最優路徑；模擬退火法使用概率性搜索方法確定全網最優路徑，能夠實現全局最優，但是收斂速度可能會很慢，不適應對響應速度要求很高的網絡；貪婪裝箱算法通過評估所有可用路徑然后選擇最左邊滿足需求的路徑，缺點是每次數據流到來時都要進行一次評估，系統開銷比較大；拓撲感知的啟發式算法基于胖樹拓撲結構的特性使用快速啟發式，要依賴于流劃分也沒有考慮到整個網絡的流量狀態。

在SDN集中控制機制下，實現數據中心系統狀態最優也有相關研究。如文獻[7]中通過在SDN控制器中建立流分布規則，減小控制器過載和延遲，以及控制規則表規模。文獻[8]通過動態分配權值減輕SDN交換機和普通交換機混合網絡中局部擁堵路徑，提高整個全網工作效率。

但是，這些方法缺少自適應性，沒有考慮網絡運行狀態，不能保證在全局最優的情況下，實現胖樹數據中心網絡全網多路徑負載均衡。

本文的目標是在SDN結構下，研究胖樹數據中心網絡中基于網絡運行狀態且支持多路徑的高效可行的多路徑負載均衡算法(F-MPLB)，以提高網絡帶寬和吞吐量，實現全網負載均衡。

F-MPLB算法的研究思路是利用SDN控制器收集全網狀態信息，然后計算節點可調用帶寬、鏈路剩余帶寬等信息。通過評估所有可選路徑找出最佳路由，最后由控制器制定路由轉發策略并下發到各交換機節點。算法主要研究以下幾個方面：

(1) 節點可調用帶寬，根據節點轉發閾值上限及當前負載情況計算節點可調用帶寬，在節點發生擁塞前能夠提前更換轉發節點；

(2) 鏈路剩余帶寬，根據鏈路最大負載及當前已用帶寬計算鏈路剩余帶寬，防止鏈路擁塞；

(3) 路徑的選擇，根據節點可調用帶寬與鏈路剩余帶寬，評估節點對之間所有路徑，創建可選路徑集合，根據可選路徑的瓶頸帶寬選擇最佳轉發路徑。

1 系統結構

為了讓F-MPLB算法具有更強的可執行性，本文將網絡信息的收集、多路徑的分析與評估、路由策略的下發進行分離，分別使用信息收集模塊、路由模塊、控制器模塊等3部分實現，算法系統結構如圖1所示。

圖1 F-MPLB算法系統結構

1.1 信息收集模塊

信息收集模塊實時監控轉發層流量、節點狀態和鏈路狀態，獲取網絡流量需求及當前節點和鏈路負載狀態等信息，通過數據庫存儲到對應的數據表中供路由模塊使用。

1.2 路由模塊

路由模塊根據流、節點和鏈路相應的數據表中記錄的網絡流量、節點狀態和鏈路狀態等數據信息，將各信息計算模塊通過不同的獨立進程實現，分別負責流管理、節點管理和鏈路管理。然后基于網絡拓撲結構找出源目的節點對之間所有多路徑，對多路徑路由進行評估找出全網最佳路徑。路由的評估包括節點評估和鏈路評估兩部分。

(1) 節點評估

節點評估主要對節點的可調用帶寬進行評估。節點轉發能力有限，為了防止節點超載造成網絡癱瘓，一般都會設定節點轉發閾值上限來限定節點最大帶寬利用率。節點可調用帶寬通過節點最大帶寬與當前已用帶寬的差值計算得出。

路由模塊根據節點當前帶寬利用率，首先淘汰超過節點轉發閾值上限的節點以及包含這些節點的路徑，然后計算剩余節點的可調用帶寬，預測最佳轉發節點。

(2) 鏈路評估

胖樹數據中心網絡是層次型網絡拓撲結構，越靠近核心層的鏈路帶寬需求越高。為了避免鏈路擁塞，路由模塊通過設定合理的鏈路最大負載來限定鏈路最大可用帶寬。然后根據當前負載情況計算各鏈路剩余帶寬，淘汰那些剩余帶寬不足以滿足流量帶寬需求的鏈路。最后從剩下的鏈路中選擇最佳轉發鏈路。

1.3 控制器模塊

控制器模塊是SDN結構的核心。控制器主要完成以下任務：(1)從信息收集模塊獲取網絡流量、節點狀態和鏈路狀態等信息形成全局視圖，提供給路由模塊進行計算；(2)根據路由模塊計算得出的全局最佳路徑，形成路由轉發策略并生成流表下發到各個交換機節點。

F-MPLB算法的三個模塊構成如圖2所示。

圖2 F-MPLB算法模塊構成

各模塊進程相互獨立且按照一定的順序觸發。首先信息收集模塊收集信息寫在數據庫對應的數據表中；然后路由模塊評估算法從數據庫中讀取數據并根據全局視圖進行多路徑路由評估確定最佳轉發路徑；最后交給控制器模塊制定路由轉發策略。

2 路由模塊算法設計

2.1 網絡環境描述

胖樹拓撲結構具有邊緣層、匯聚層和核心層3層結構[9-10]。其中，匯聚層和邊緣層分為K個POD，每個POD包含K個交換機，其中K/2個在匯聚層，另外K/2個在邊緣層；每個交換機有K個端口，其中K/2個向下級聯，另外K/2個向上級聯；核心層共有(K/2)2個核心交換機，每個交換機K個端口分別連接到分屬于K個POD的匯聚層交換機向上的級聯口。整個網絡共有5K2/4個交換機、3K3/4條鏈路，可以容納K3/4個主機。本文構造一個K=8的簡單胖樹數據中心網絡，如圖3所示。

圖3 胖樹數據中心網絡(K=8)

該網絡可以看作圖G=(H∪S;E)，其中，H與S是節點集合，H代表主機，S代表交換機，E是鏈路集合。交換機節點s∈S的帶寬用b(s)表示，鏈路e∈E的帶寬用b(e)表示。

設網絡中所有數據流組成集合F={f1,f2,…,fn}，流fi的運行帶寬用b(fi)表示。構造矩陣X=F×S，矩陣元素的值x(fi,s)∈(0,1)代表流fi是否流經交換機節點s。構造矩陣Y=F×E，矩陣元素的值y(fi,e)∈(0,1)代表流fi是否流經鏈路e。

2.2 節點評估算法

節點評估算法的目標是設定節點轉發閾值上限，路由模塊根據節點帶寬利用率，淘汰節點負載接近節點轉發閾值上限的節點，然后根據節點最大轉發帶寬及當前已用帶寬，計算各節點的可調用帶寬Ava(s)，選擇出最佳的轉發節點。

節點轉發閾值上限直接限定了節點最大轉發帶寬。考慮到網絡流量帶寬的不確定性，本文引用絕對中位差MAD[11]來衡量數據流穩定性。

根據MAD的定義，當前節點s的MAD值可表示為：

MAD=mediani(x(fi,s)×b(fi)-medianj(x(fj,s)×b(fj)))

(1)

節點轉發閾值上限定義為：

Thu(s)=1-α×MAD

(2)

其中，α∈R+，為自定義參數，通過調整α值可以調整節點轉發閾值上限。MAD值越小說明該節點上數據流越穩定，節點轉發閾值上限可以調大些；MAD值越大說明數據流越不穩定，需要調小節點轉發閾值上限避免數據流突發造成節點擁塞。

設wl(s)表示節點已用帶寬，則節點s的帶寬占用率為：

Pwl(s)=wl(s)/b(s)

(3)

節點帶寬占用率不能超過節點轉發閾值上限，即Pwl(s) ≤Thu(s)。

因此，節點s可調用帶寬為：

Ava(s)=Thu(s)×b(s)-wl(s)

(4)

2.3 鏈路評估算法

為了避免鏈路擁塞造成網絡癱瘓，鏈路評估算法會綜合考慮鏈路關鍵度及鏈路所處網絡層次等因素設定合理的鏈路最大負載，根據鏈路剩余帶寬選擇最佳轉發鏈路。

首先，我們將鏈路e的鏈路關鍵度ρ(e)定義為：

ρ(e)=AVE(e)/b(e)

(5)

其中，b(e)表示鏈路建設時帶寬；AVE(e)表示鏈路的平均期望負載，定義為網絡中所有流過鏈路e的流量帶寬之和與流數目的比值，則：

(6)

AVE(e)值越高說明數據流在選擇轉發路徑時更容易選中該鏈路，鏈路關鍵度越高，應該設置更高的鏈路最大負載。

胖樹數據中心網絡不同網絡層次需要的最大帶寬也不同，為此我們引入參數β∈R+，不同網絡層次設置不同的β值。鏈路最大負載定義為：

max=β×ρ(e)

(7)

則鏈路e的剩余帶寬c(e)為：

(8)

算法應該滿足如下限制：

(9)

(10)

式(9)表明了鏈路最大負載與鏈路可用帶寬的關系，即對鏈路需求的帶寬總和不超過鏈路的可用帶寬。式(10)表明流守恒限制，即流經任意中間節點v的流數目不會改變。

2.4 算法的實現代碼

本文在SDN環境中實現F-MPLB算法，通過SDN控制器獲取網絡中所有節點和鏈路狀態信息。當數據流需要重新選擇路徑或者一個新流產生時，根據流的源目的IP地址建立路徑集合數據庫；然后根據節點轉發閾值上限與鏈路最大負載的約束，排除節點超載或鏈路剩余帶寬不足的路徑；最后在剩下的可選路徑中根據節點可調用帶寬和鏈路剩余帶寬對多路徑進行評估，選擇瓶頸帶寬最大的路徑對數據流進行轉發。

算法實現偽代碼如下：

begin

{ 輸入流f，源主機Hs，目的主機Hd；

if(Hs和Hd同屬一個邊緣交換機)

return path(Hs,Hd);

else

{ PATHS=getAllpath(Hs,Hd);

Deletepath();

for( int m=0;m

MINWIDTH=min( PATHS.minNodewidth, PATHS.minBandwidth );

end for;

for(int k=0;k< MINWIDTH.length;k++)

if( MINWIDTH[k].width ≥ b(f) )

path.width=max( path.width, MINWIDTH[k].width );

end for;

return path(Hs,Hd);

}end if;

輸出轉發路徑path(Hs,Hd)及其瓶頸帶寬path.width。

}

end

路徑評估由路徑上所有節點帶寬和鏈路帶寬的最小值決定路徑瓶頸帶寬，即路徑L瓶頸帶寬=min(節點1帶寬，節點2帶寬,…,節點m帶寬，鏈路1帶寬，鏈路2帶寬,…,鏈路n帶寬)。路徑選擇算法選擇瓶頸帶寬最大的路徑，即轉發路徑=max(路徑L1瓶頸帶寬，路徑L2瓶頸帶寬，…,路徑Lk瓶頸帶寬)，最終實現多路徑負載均衡。

3 實驗和算法評估

3.1 平臺介紹

本文使用Mininet+Floodlight實驗平臺模擬運行環境，F-MPLB算法各獨立模塊在Floodlight控制器上實現。Floodlight控制器周期性地調度監控事件獲取全網狀態信息，包括交換機狀態、鏈路負載情況以及數據流帶寬需求等信息。

Mininet版本為2.2.0，Floodlight控制器版本為Ubuntu 16.04-desktop-64位，硬件環境為ACER E1-571G，CPU為Intel Core(TM) i5，2.60 GHz，內存4 GB，硬盤500 GB。Mininet選擇嚴格胖樹拓撲結構[12]模擬數據中心網絡，取K=8模擬128個主機場景，網絡中葉節點交換機64個，核心交換機16個。

實驗中設定葉節點交換機帶寬為200 MB/s，核心交換機帶寬為1 GB/s，交換機轉發閾值上限缺省值為60%；鏈路帶寬為100 MB/s，核心層到匯聚層鏈路最大負載缺省值為70%，匯聚層到邊緣層鏈路最大負載缺省值為60%；算法將網絡中傳輸的流歸約到葉節點交換機，流直接在交換機端產生；數據流的源目的節點在葉節點交換機集合中隨機產生；大流帶寬大小服從[1 MB/s,10 MB/s]為區間的隨機分布，小流帶寬大小服從[1 KB/s,10 KB/s]為區間的隨機分布，流發生頻率服從指數分布。每次實驗流的數量相等，長短流按照設定配給比例產生，缺省情況下比例各為50%。

3.2 對比實驗

本文實驗選擇嚴格胖樹拓撲結構模擬數據中心網絡環境，數據流數量達到107數量級，對網絡的響應速度要求很高。如今已有的多路徑解決方案及SDN集中控制下的相關研究，在此類網絡中多使用傳統的ECMP算法及Hedera中提出的GFF算法，因此本文實驗主要與這兩種算法進行性能對比。

其中，ECMP在可供選擇的等價鏈路上平均分配流量，能夠有效提高網絡帶寬及吞吐量，但是不能夠根據鏈路狀態變化改變流量分配的比例；GFF算法在監測到大流時搜尋所有有效路徑，選擇最先找到的符合帶寬要求的鏈路進行轉發，沒有考慮網絡全局負載狀態。針對算法的這些差異，本文分別從節點過載次數、傳播時延、平均吞吐量等三方面進行比較。

(1) 節點過載次數比較

通過網絡運行過程中節點過載次數反映路徑的過載次數。如果節點過載次數過大，說明該算法不能根據多路徑當前負載狀態合理分配數據流轉發路徑，隨著流數量的增加最終會造成網絡擁塞。節點過載情況如圖4所示。

圖4 節點過載次數比較

從實驗結果可以看出，傳統的ECMP算法引起的節點過載次數最多；GFF算法能夠有效降低節點過載次數，但隨著網絡負載狀態的改變節點過載情況也開始出現；F-MPLB算法效果最好，能夠根據當前網絡負載狀態動態地調整轉發路徑，實現鏈路負載均衡避免節點過載情況的發生。但是，隨著數據流數量的不斷增加，網絡流量趨于飽和并最終超過系統處理閾值，各算法的節點過載次數趨于相同。所以F-MPLB算法在系統性能閾值之內能很好地避免節點過載，但超過系統閾值能夠引起的改變有限。

(2) 傳播時延比較

隨著數據流數量的增加，觀察算法對數據流傳播時延的影響，實驗結果如圖5所示。

圖5 傳播時延比較

實驗中不同算法選擇路徑的策略不同，導致了時延上的差異。實驗最開始傳播時延都有所上升是因為數據流第一個數據包到來時，交換機轉發流表為空，需要上報Floodlight控制器計算轉發路徑并下發流表。隨后傳播時延迅速回落。當數據流數量在0～104范圍內，多路徑鏈路狀態良好，3種算法傳播時延相當。當數據流數量超過104，ECMP算法傳播時延開始增加，網絡性能急劇下降；而GFF算法能保持時延只產生微小抖動，F-MPLB算法基本無抖動。當數據流數量到達106，網絡負載狀態超過系統處理閾值，傳播時延都有所增加，但總體上F-MPLB算法傳播時延最低，體現出一定的優越性。

(3) 平均吞吐量比較

網絡平均吞吐量實驗結果如圖6所示。

圖6 平均吞吐量比較

實驗結果反映出當網絡流量在0～102范圍內，網絡剩余帶寬充足，3種算法的平均吞吐量都穩定增長。但是當數據流數量超過102，網絡負載逐漸加重，傳統的ECMP算法不能很好地感知網絡負載狀態，吞吐量開始達到瓶頸值；而GFF算法和F-MPLB算法吞吐量依然能夠穩定提升。當數據流數量達到104，網絡負載趨于飽和，傳統的ECMP網絡吞吐量急劇下降；GFF算法吞吐量趨于穩定，能夠很好地處理網絡擁塞；而F-MPLB算法動態調整轉發路徑，不僅能處理網絡擁塞還能進一步提高網絡平均吞吐量。

3.3 實驗結論

從以上實驗結果可以看出，當網絡數據流數量較少、多路徑帶寬充足時，3種算法性能相當。但是隨著數據流數量的增加，網絡負載超出了系統處理能力閾值，傳統算法的有效性降低。而本文提出的F-MPLB算法能夠通過動態調整數據流轉發路徑，將流量引導至負載較低、質量較好的路徑上。實現多路徑負載均衡，能夠有效減少節點過載次數、降低傳播時延、提高網絡平均吞吐量。

4 結 語

本文基于SDN結構，針對胖樹數據中心網絡提出了多路徑負載均衡算法F-MPLB。該算法利用SDN集中控制器獲取全網網絡狀態信息，通過求解節點轉發閾值上限確定節點可調用帶寬、求解鏈路最大負載確定鏈路剩余帶寬，提供給路由模塊以選擇最佳轉發路徑，更好地利用多路徑有效帶寬達到鏈路負載均衡。經過Mininet+Floodlight仿真實驗，結果表明本文算法在系統閾值能力范圍內，在減少節點過載次數、縮減傳播時延、提升網絡吞吐量等方面的性能均優于傳統多路徑算法，能夠實現胖樹數據中心網絡多路徑負載均衡。

隨著研究的逐漸深入，發現還有許多工作值得后續的關注和跟進。

1) 評估模型擴展。本文算法以多路徑中交換機節點可調用帶寬及鏈路剩余帶寬兩個標準評估路徑最大傳輸能力，根據數據流帶寬需求尋找最佳轉發路徑。但是沒有考慮交換機節點轉發速率及鏈路的傳輸時延，隨著評估標準的增加，算法越來越復雜，需要增加控制器模塊復雜度。同時模塊部署時延、算法的準確度分析都需要跟進研究。

2) 流動態預測與復雜分析。SDN數據流是可以預測的，預測模型通過在控制器端增加流信息統計模塊監控數據流的傳輸，根據流的歷史統計特性可以預測其未來行為。本文對數據流的分析僅局限于數據流的帶寬，沒有考慮流頻率及傳輸性質的不同。對于經常出現的流及突發產生的流應該采取不同的處理方式，但這樣也會增加模塊復雜度。

[1] Mckeown N,Anderson T,Balakrishnan H,et al.Open Flow:enabling innovation in campus networks[J].Acm Sigcomm Computer Communication Review,2008,38(2):69-74.

[2] Fei Y.Introduction to the development of data center network architecture[J].Network Security Technology & Application,2014,22(6):23-28.

[3] Sun Y,Cheng J,Shi K.Data Center Network Architecture[J].Zte Communications,2013,11(5):5-9.

[4] Chemeritskiy E,Smelansky R.On QoS management in SDN by multipath routing[C]//2014 First International Science and Technology Congerence(Modern Networking Technologies) (MoNeTeC).IEEE,2014:1-6.

[5] Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:Dynamic flow scheduling for data-center networks[C]//NSDI’10 Proceeding of the 7th USENIX conference on Networked systems design and implementation.Berkeley,CA,USA:USENIX Association,2010:19-19.

[6] Heller B,Seetharaman S,Mahadevan P,et al.ElasticTree: saving energy in data center networks[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2010:17-17.

[7] Wang R,Butnariu D,Rexford J,et al.OpenFlow-based server load balancing gone wild[C]//Proceedings of the 11th USENIX Conference on Hot Topics in Management of Internet,Cloud,and Enterprise Networks and Services.Boston,USA,2011:12-12.

[8] Guo Y,Wang Z,Yin X,et al.Traffic engineering in SDN/OSPF hybrid network[C]//Proceedings of the 22nd IEEE International Conference on Network Protocols(ICNP).North Carolina,USA,2014:563-568.

[9] Eric J,Deng P,Liu J,et al.Asimulation and emulation study of sdn-based multipath routing for fat-tree data center network[C]//WSC’14 Proceeding of the 2014 Winter Simulation Conference.Piscataway,NJ,USA:IEEE Press,2014:3072-3083.

[10] Zhou J,Malveeka T,Zhu M,et al.WCMP:Weighted cost multipathing for improve fairness in data centers[C]//EuroSys’14 Proceedings of the Ninth European Conference on Computer Systems.New York,NY,USA:ACM,2014,5.

[11] Wu C,Zhao Y,Wang Z,et al.The median absolute deviations and their applications to Shewhart control charts[J].Communications in Statistics-Simulation and Computation,2002,31(3):425-442.

[12] Al-Fares M,Loukessas A,Vahdat A,et al.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.

RESEARCHONSDN-BASEDMULTI-PATHLOADBALANCINGALGORITHMOFFAT-TREEDATACENTERNETWORK

Fu Yinghui Liu Biguo Shu Yongan

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

Software Defined Networking (SDN) is widely used in datacenters and other related fields to achieve centralized control of the network and flexible traffic forwarding by decoupling the control plane from the data plane. To improve the network bandwidth and throughput, datacenter network employ layering network topology structure with multi-path characteristics, such as Fat-tree. However, traditional routing algorithms have limited support for multi-path routing, they cannot make full use of the remaining bandwidth of the network. Therefore, this paper mainly studies the SDN based multi-path load balancing algorithm of Fat-tree datacenter network. By using the centralized control of SDN network, obtain multi-path real-time status information; calculate the available bandwidth of each path, and selects the best forwarding route according to the bandwidth requirement of the data stream. The experimental results show that the proposed algorithm is superior to traditional routing algorithms in not only reducing network propagation delay but improving network throughput, thus it is capable to achieve multi-path load balancing in Fat-tree datacenter networks.

Software defined network SDN Fat tree Datacenter network Multi-path load balancing

TP3

A

10.3969/j.issn.1000-386x.2017.09.030

2016-10-19。安徽省自然科學基金項目(1408085MF125)。付應輝，碩士生，主研領域：SDN。劉必果，碩士生。束永安，教授。