基于SDN的胖樹數(shù)據(jù)中心網(wǎng)絡多路徑路由算法

彭大芹,,

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

0 概述

近年來,大數(shù)據(jù)、云計算等互聯(lián)網(wǎng)應用發(fā)展迅速,這些新型應用使數(shù)據(jù)中心內部通信量加倍地增長,帶來的問題是數(shù)據(jù)中心網(wǎng)絡內部帶寬已經不能滿足流量的傳輸需求[1-2]。為解決該問題,新型數(shù)據(jù)中心網(wǎng)絡通常采用分層的多根網(wǎng)絡拓撲,如胖樹網(wǎng)絡拓撲。這種拓撲使網(wǎng)絡更容易擴展,同時也具有多路徑路由的特性[3-4]。針對數(shù)據(jù)中心網(wǎng)絡多路徑路由問題,比較經典的是基于哈希的ECMP算法,該算法在數(shù)量上將數(shù)據(jù)流均勻地哈希到多條等價路徑上[5]。ECMP能夠利用樹形網(wǎng)絡拓撲的冗余鏈路,實現(xiàn)數(shù)據(jù)的快速轉發(fā),但該算法沒有考慮鏈路實時傳輸狀態(tài)及網(wǎng)絡流量特征。文獻[6]研究發(fā)現(xiàn),數(shù)據(jù)中心網(wǎng)絡流量中90%的數(shù)據(jù)流持續(xù)時間不超過10 s,大小不超過100 KB,而大于100 KB的數(shù)據(jù)流占總流量大小的90%。因此,ECMP算法可能將多條大數(shù)據(jù)流散列到同一條鏈路上,造成網(wǎng)絡擁塞。

軟件定義網(wǎng)絡(Software Definod Network,SDN)是近年提出的一種新型網(wǎng)絡技術,其核心思想是將網(wǎng)絡的控制平面與數(shù)據(jù)平面分離,并實現(xiàn)可編程的集中控制。目前,國內外越來越多的研究者專注于利用SDN具有全網(wǎng)視圖的特性來解決新型數(shù)據(jù)中心網(wǎng)絡的多路徑路由問題,并提出很多改進的路由算法。文獻[7]提出一種動態(tài)分布式流調度(DDFS)機制,該機制綜合分析不同層次交換機的流量調度問題,在一定程度上能夠提高核心交換機的交換能力和網(wǎng)絡鏈路利用率。文獻[8]提出一種SHR路由機制,該機制使用控制器對網(wǎng)絡中的大流進行調度,而將小流的處理權交給交換機。仿真結果表明,該機制改善了吞吐量和流丟棄率等網(wǎng)絡性能,但鏈路利用率并不高。文獻[9]中Hedera對大流采用模擬退火算法進行路由,而對小數(shù)據(jù)流仍然使用ECMP算法進行選路。結果表明該策略僅在ECMP算法的基礎上將鏈路利用率提高了1%～5%,效果并不明顯。文獻[10]提出的PROBE算法利用類似路由追蹤的方式來實現(xiàn)流量細粒度控制。經驗證該方法具有一定可行性。

綜上所述,針對ECMP算法的缺點以及現(xiàn)有路由算法沒有綜合考慮鏈路實時傳輸狀態(tài)和流量特征的問題,本文提出一種基于鏈路實時狀態(tài)和流量特征的多路徑路由(MLF)算法,該算法根據(jù)數(shù)據(jù)中心網(wǎng)絡流量特征,將數(shù)據(jù)流分為大流和小流,并對不同大小的數(shù)據(jù)流使用不同的路由方式。

1 路由方案設計

路由方案的總體框架如圖1所示。其中,胖樹拓撲的數(shù)據(jù)中心網(wǎng)絡由支持OpenFlow協(xié)議的SDN交換機構建;同時,為了實現(xiàn)提出的MLF算法,本文在Floodlight控制器內設計了信息統(tǒng)計模塊、數(shù)據(jù)存儲模塊、路徑計算模塊和流表下發(fā)模塊,這些模塊是完成數(shù)據(jù)中心網(wǎng)絡流量路由的核心功能模塊。其中,信息統(tǒng)計模塊完成鏈路狀態(tài)信息和流信息的收集,主要包括實時鏈路帶寬信息和大流信息;數(shù)據(jù)存儲模塊負責存儲收集的鏈路帶寬信息和大流信息,并提供相關接口,便于控制器其他模塊訪問和修改;路徑計算模塊采用MLF算法為數(shù)據(jù)流計算路由策略;流表下發(fā)模塊將路徑計算模塊計算好的路由策略以流表的形式下發(fā)到路徑上的各個交換機中,完成數(shù)據(jù)流的轉發(fā)。

圖1 路由方案總體框架

1.1 網(wǎng)絡狀態(tài)信息收集

本節(jié)由信息統(tǒng)計模塊完成,包括對網(wǎng)絡中鏈路帶寬和大流信息的統(tǒng)計收集。

1)鏈路帶寬信息

Floodlight控制器提供了用于統(tǒng)計交換機各端口帶寬信息(即鏈路帶寬信息)的IstatisticsService接口,因此,信息統(tǒng)計模塊只需調用該接口即可。對于統(tǒng)計間隔,文獻[11]通過實驗發(fā)現(xiàn)1 s的統(tǒng)計間隔在平均鏈路利用率上要比5 s的統(tǒng)計間隔更高,本文沿用了這種思想,將鏈路帶寬信息的統(tǒng)計間隔設定為1 s。鑒于胖樹拓撲結構特點,信息統(tǒng)計模塊只需對匯聚層交換機的端口帶寬信息進行統(tǒng)計,具體為調用控制器中進程池(ThreadPool)模塊提供的線程,以周期為1 s獲取交換機各端口帶寬信息,包括發(fā)送和接收的總字節(jié)數(shù),并將信息發(fā)送給數(shù)據(jù)存儲模塊進行存儲。圖2為實驗測試過程中打印的由信息統(tǒng)計模塊統(tǒng)計的部分交換機端口帶寬信息,包括交換機DPID、端口id和端口傳輸帶寬等字段信息,由端口帶寬信息便可獲得鏈路帶寬信息。

圖2 端口帶寬信息

2)大流信息

根據(jù)數(shù)據(jù)中心網(wǎng)絡流量特征,本文將超過100 KB大小的數(shù)據(jù)流定義為大流。對于流信息統(tǒng)計,通常的做法是由控制器周期性地向邊緣層交換機發(fā)送flow_stats_request流統(tǒng)計請求消息,以此獲取數(shù)據(jù)流的精確統(tǒng)計信息。然而,過多的請求響應消息一方面會消耗大量的交換機資源和鏈路帶寬資源,造成網(wǎng)絡擁塞,另一方面也會增加控制器的處理時延,造成控制器負擔過重[12]。文獻[13]的研究發(fā)現(xiàn),生成數(shù)據(jù)包的服務器主機對應用程序的發(fā)包速率感知性更強,檢測大流較好的方式是在服務器主機進行。因此,本文使用服務器主機完成對大流信息的統(tǒng)計,當服務器主機發(fā)送緩沖區(qū)內同一五元組的數(shù)據(jù)包總大小超過100 KB時,該流便被標記為大流,然后將標識流的五元組和速率等信息通過交換機發(fā)送到控制器的信息統(tǒng)計模塊。

信息統(tǒng)計模塊收集到鏈路帶寬信息和大流信息后,將它們發(fā)送到數(shù)據(jù)存儲模塊以Java HashMap結構形式存儲在NoSQL內存數(shù)據(jù)庫中。對于鏈路帶寬信息,存儲區(qū)只保存最近統(tǒng)計間隔內的數(shù)據(jù),并進行周期性更新;對于大流信息,如果該流已經完成轉發(fā),則刪除在數(shù)據(jù)庫中的相關信息以釋放內存空間,否則繼續(xù)保留。

1.2 路由算法實現(xiàn)

1.2.1 核心思想

基于鏈路實時狀態(tài)和流量特征的多路徑路由算法在設計時,重點對不同大小的數(shù)據(jù)流使用了不同的選路策略。其主要思想如下:

1)大流選路

為了提高大流吞吐量和避免鏈路擁塞,對于大流,根據(jù)最新統(tǒng)計的鏈路剩余帶寬計算出每條路徑的權重值,使用哈希算法對流的五元組進行哈希得到哈希值,哈希值對路徑權重值的總和取余,根據(jù)余數(shù)落在路徑權重值之間的位置決定使用哪條路徑進行路由。具體為:假設網(wǎng)絡中有n條小數(shù)據(jù)流,用F={f1,f2,…,fn}表示,對應每條數(shù)據(jù)流的請求帶寬設為vj,其中j∈{1,2,…,n}。根據(jù)k元胖樹拓撲結構特點,不同pod下的2臺服務器之間共有k條等價路徑,設為{p1,p2,…,pk},每條路徑有k條鏈路,并且各交換機之間的鏈路默認容量是一樣的。為避免鏈路擁塞,本文取鏈路容量的80%作為擁塞閾值,設為bth。令bmi表示第m條路徑第i條鏈路的已傳輸帶寬,其中i,m∈{1,2,…,k},該帶寬信息可直接從數(shù)據(jù)庫中讀取。這里需要說明的是,根據(jù)k元胖樹拓撲結構特點可知,不同Pod連接的每2個服務器之間總共有k條可用路徑,而每一條路徑總共有k條鏈路。因此,第m條路徑的可用帶寬為該路徑上k條鏈路中最小的鏈路可用帶寬,設為bm,表示為:

(1)

定義wm為第m條路徑的路徑權重,則wm的值即為第m條路徑的可用帶寬占所有路徑可用帶寬之和的比值,表示為:

(2)

其中,c為常數(shù),bm和bi分別代表第m條和第i條路徑的可用帶寬,δ函數(shù)用于判斷數(shù)據(jù)流的請求帶寬是否大于某條路徑的可用帶寬。如果大于,則取值為0,表示放棄該條路徑;如果小于,則將其加入到可用路徑中。δm和δi分別用于判斷第m條和第i條路徑的可用帶寬是否滿足數(shù)據(jù)流的請求帶寬。δ函數(shù)表示為:

(3)

其中,vj表示第j條數(shù)據(jù)流的請求帶寬。

假設最后得出新的可用路徑為k1條,由式(2)可知這k1條路徑的權重值之和為c。根據(jù)路徑權重值為這n條流選擇路由路徑,具體為:使用流的五元組信息作為哈希算法的輸入,將得出的哈希值對c進行取余,取余后的值范圍是{0,1,…,c-1},判斷求得的余數(shù)落在{0～w1,w1～w2,w2～w3,…,wk1-1～wk1}范圍內的位置,選擇對應的路徑;假設落在w1～w2范圍內時,則選擇w2所在的路徑作為路由路徑,以此類推。

2)小流選路

根據(jù)小流數(shù)目多、對時延敏感等特點,同時也為了使小流能夠快速轉發(fā),本文降低了對小流處理的復雜性,對小流一律采用基于路徑可用剩余帶寬最大的原則進行選路,即選用式(1)中bm最大的路徑。

路由算法流程如圖3所示。

圖3 路由算法流程

1.2.2 算法實現(xiàn)

路由算法實現(xiàn)部分由路徑計算模塊完成。控制器默認使用的路由算法為常見的最短路徑算法——Dijkstra算法,其主要思想是將網(wǎng)絡拓撲圖轉化為帶權有向圖G=(V,E),其中,V為網(wǎng)絡節(jié)點集合,E為連接節(jié)點與節(jié)點之間邊的集合。將頂點V劃分為2個集合,第1集合是已求出到源節(jié)點的最短路徑的目的節(jié)點的集合S,第3集合是其他沒有確定最短路徑的目的節(jié)點的集合U,然后依照鏈路權重值將集合U中的頂點逐漸依次添加到集合S中。針對數(shù)據(jù)中心網(wǎng)絡流量大而密集的特點,該算法容易造成鏈路擁塞,也不能解決負載均衡問題。

MLF算法的具體步驟如下:

步驟1路由計算模塊調用processPacketInMessage()方法對Packet-In數(shù)據(jù)包進行解析,解析出數(shù)據(jù)包的IP五元組信息,然后根據(jù)防火墻模塊的轉發(fā)規(guī)則表判斷源目的主機是否可以通信,如果不可以則丟棄;否則繼續(xù)步驟2。

步驟2檢查數(shù)據(jù)包是否為廣播包,如果是則調用doFlood()方法進行廣播處理;否則繼續(xù)步驟3。

步驟3判斷數(shù)據(jù)包的源目的主機是否屬于同一網(wǎng)段,即為同一邊緣層交換機下的2臺主機,如果是則直接進行二層轉發(fā);否則繼續(xù)步驟4。

步驟4讀取數(shù)據(jù)庫中的統(tǒng)計信息判斷該流是否為大流,如果是則繼續(xù)步驟5;否則選擇可用剩余帶寬最大的路徑進行轉發(fā)并跳轉到步驟7。

步驟5根據(jù)流的請求速率篩選出源目的主機之間的所有可用路徑,調用caculateRouteWeight()方法計算每條路徑的路徑權重值。

步驟6調用hash()方法對流的五元組進行哈希運算,將得到的哈希值對權重值之和取余,根據(jù)余值和權重值范圍選擇路由路徑。

步驟7調用pushRoute()方法將路由策略推送到該路徑上的所有交換機上。

2 實驗與結果分析

2.1 仿真環(huán)境設置

采用Mininet[14]網(wǎng)絡仿真器和Floodlight控制器搭建實驗仿真平臺。Mininet是一款強大的網(wǎng)絡仿真工具,利用它可以構建包括交換機、鏈路和主機在內的數(shù)據(jù)中心網(wǎng)絡,同時還支持使用OpenFlow協(xié)議與Floodlight控制器相連接。受條件限制,本文只構建了4個Pod來模擬胖樹拓撲的數(shù)據(jù)中心網(wǎng)絡場景,如圖4所示,包括20臺OpenFlow交換機與16臺服務器。網(wǎng)絡中所有節(jié)點之間的鏈路均設置為全雙工鏈路,并將鏈路帶寬設定為1 Gb/s。使用Iperf[15]工具產生模擬的數(shù)據(jù)中心網(wǎng)絡流量,令主機H1～H8同時向主機H9～H16發(fā)送數(shù)據(jù)流量。根據(jù)數(shù)據(jù)中心網(wǎng)絡的流量特征,假設發(fā)送的流量中90%的流大小為0 KB～100 KB,10%的流大小大于100 KB,且所有的數(shù)據(jù)流都服從均勻分布[16]。

圖4 網(wǎng)絡拓撲場景

2.2 結果分析

本文選取平均鏈路利用率、網(wǎng)絡吞吐量作為性能評價指標,與ECMP算法和SHR機制進行對比,驗證MLF算法的性能優(yōu)勢。此外,還在MLF算法的基礎上對比區(qū)分大小流的選路策略對網(wǎng)絡吞吐量的影響。平均鏈路利用率為網(wǎng)絡拓撲中所有鏈路的平均值,用η(t)表示,用式(4)表示為:

(4)

其中,由上文可知,bmi(t)表示第m條路徑第i條鏈路在t時刻的已傳輸帶寬,可通過信息統(tǒng)計模塊得出,N為鏈路的總條數(shù),BMAX表示鏈路的默認帶寬。對于網(wǎng)絡吞吐量,Iperf可以直接測量出端到端的吞吐量,進而可以計算出整個網(wǎng)絡的吞吐量。

圖5分別采用ECMP、SHR和MLF進行路由的平均鏈路利用率仿真對比。仿真結果表明,由于ECMP在路由時沒有將網(wǎng)絡的實時鏈路狀態(tài)和數(shù)據(jù)流的大小考慮在內,僅在數(shù)量上將數(shù)據(jù)流均勻分配到各條等價路徑上,導致鏈路帶寬分配不均勻,增加了鏈路擁塞的可能性,因此它的平均鏈路利用率要低于MLF和SHR。此外,從圖5可以看出,開始時MLF和SHR的平均鏈路利用率相差不大,但30 s以后,MLF要明顯高于SHR。這是因為SHR中是按鏈路默認帶寬比為小流進行選路,沒有考慮流量傳輸后路徑上的實時負載情況,這容易造成某條路徑上的流量負載過重,導致網(wǎng)絡擁塞而降低網(wǎng)絡鏈路利用率。而MLF算法對大流和小流的選路都考慮了鏈路的實時負載,因而性能要優(yōu)于SHR。

圖5 平均鏈路利用率對比

圖6為網(wǎng)絡吞吐量的性能對比。從圖6可以看出,當發(fā)包速率低于500 Mb/s,由于MLF和SHR中交換機和控制器之間需要頻繁發(fā)送用于統(tǒng)計鏈路狀態(tài)的請求回復信息,而這需要占據(jù)一定的傳輸帶寬,因此,它們的網(wǎng)絡吞吐量要比ECMP略低。當發(fā)包速率超過500 Mb/s時,ECMP的吞吐量要比MLF和SHR低得多,這是由于ECMP靜態(tài)的散列方式可能將多條大流映射到同一路徑上,導致網(wǎng)絡擁塞,造成數(shù)據(jù)流的丟棄,從而影響整個網(wǎng)絡的吞吐量,而MLF和SHR根據(jù)網(wǎng)絡負載的動態(tài)變化對流進行選路,在一定程度上提高了網(wǎng)絡的吞吐量;此外,MLF的吞吐量要比SHR高,這是因為SHR是通過控制器周期性地發(fā)送流統(tǒng)計消息完成對大流的區(qū)分,增加了控制器與交換機的通信開銷,而MLF是由服務器主機將大流信息上報至控制器,減少了這部分開銷。

圖6 網(wǎng)絡吞吐量對比

為了研究將數(shù)據(jù)流區(qū)分大小進行選路對網(wǎng)絡吞吐量的影響,本文在MLF算法上進行了分析比較。具體為不區(qū)分大小流與區(qū)分大小流,不區(qū)分大小流的做法是將所有的數(shù)據(jù)流按照MLF算法中小流的處理方式進行選路,得出的性能對比如圖7所示。從圖7中可以看出,開始時兩者的性能曲線非常相似,當發(fā)包速率超過550 Mb/s時,不區(qū)分大小流的網(wǎng)絡出現(xiàn)擁塞,鏈路不能得到有效利用,吞吐量要明顯低于區(qū)分大小流的選路策略,這是因為不區(qū)分大小流的方式可能將很多條大流放在單一路徑上傳輸,造成網(wǎng)絡阻塞而影響網(wǎng)絡吞吐量。因此,與不區(qū)分大小流相比,區(qū)分大小流的選路策略能更好地改善網(wǎng)絡性能。

圖7 區(qū)分大小流對網(wǎng)絡吞吐量的影響

3 結束語

本文針對SDN架構下的胖樹數(shù)據(jù)中心網(wǎng)絡多路徑路由問題,提出一種基于鏈路實時狀態(tài)和流量特征的多路徑路由算法。該算法將數(shù)據(jù)流分為大流和小流,并對不同大小的數(shù)據(jù)流使用不同的路由方式。設計算法功能實現(xiàn)的總體框架,給出算法設計思想和算法實現(xiàn)步驟,最后在仿真平臺上對算法進行了驗證,結果表明,與ECMP算法和SHR路由機制相比,MLF算法能夠提高胖樹數(shù)據(jù)中心網(wǎng)絡的平均鏈路利用率和網(wǎng)絡吞吐量。另外,本文還驗證了區(qū)分大小流的路由策略比不區(qū)分大小流的路由策略具有更高的網(wǎng)絡吞吐量。MLF算法僅對k=4的胖樹網(wǎng)絡拓撲進行了驗證,而未考慮節(jié)點數(shù)更多的情況;此外,算法也未對其他方面的性能進行分析,如時延等,這是下一階段的主要工作。

[1] 中國互聯(lián)網(wǎng)信息中心.第37次中國互聯(lián)網(wǎng)絡發(fā)展狀態(tài)統(tǒng)計報告[EB/OL].[2016-01-31].http://www.cnnic.cn.

[2] GANG D,GONG Z,HONG W.Characteristics research on modern data center network[J].Journal of Computer Research & Development,2014,51(2):395-407.

[3] DALVANDI A,GURUSAMY M,CJUA K C.Application scheduling,placement,and routing for power efficiency in cloud data centers[J].IEEE Transactions on Parallel & Distributed Systems,2017,28(4):947-960.

[4] LEI Y C,WANG K,HSU Y H.Multipath routing in SDN-based data center networks[C]//Proceedings of European Conference on Networks and Communications.Washington D.C.,USA:IEEE Press,2015:365-369.

[5] HOPPS C E.Analysis of an equal-cost multipath algorithm[J].Journal of Allergy & Clinical Immunology,2000,109(1):265.

[6] BENSON T,AKELLA A,MALTZ D A.Network traffic characteristics of data centers in the wild[C]//Proceeding of ACM SIGCOMM Conference on Internet Measurement.New York,USA:ACM Press,2010:114-115.

[7] BHARTI S,PATTANAIK K K.Dynamic distributed flow scheduling with load balancing for data center networks[C]//Proceedings of the 4th International Conference on Ambient Systems,Networks and Tech-nologies.Washington D.C.,USA:IEEE Press,2013:124-130.

[8] 蔡岳平,王昌平.軟件定義數(shù)據(jù)中心網(wǎng)絡混合路由機制[J].通信學報,2016,37(4):44-52.

[9] Al-FARES M,RADHAKRISHNAN S,RAGHAVAN B,et al.Hedera:dynamic flow scheduling for data center networks[C]//Proceedings of USENIX Conference on Networked Systems Design and Implementation.[S.1.]:USENIX Association,2010:19-19.

[10] XI Kang,LIU Yulei,CHAO H J.Enabling flow-based routing control in data center networks using probe and ECMP[C]//Proceedings of Computer Communica-tions Workshops.Orlando,USA:IEEE Press,2011:608-613.

[11] CURTIS A R,MOGUL J C,TOURRILHES J,et al.DevoFlow:scaling flow management for high-performance networks[C]//Proceedings of ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications.Toronto,Canada:[s.n.],2011:254-265.

[12] 李 龍,付斌章,陳明宇,等.Nimble:一種適用于OpenFlow網(wǎng)絡的快速流調度策略[J].計算機學報,2015,38(5):1056-1068.

[13] CURTIS A R,KIM W,YALAGANDULA P.Mahout:low-overhead datacenter traffic management using end-host-based elephant detection[C]//Proceedings of IEEE INFOCOM’11.Washington D.C.,USA:IEEE Press,2011:1629-1637.

[14] TEAM M.Mininet:An instant virtual network on your laptop[EB/OL].[2016-10-21].http://www.mininet.org/.

[15] 張 白,宋安軍.基于Iperf的網(wǎng)絡性能測量研究[J].電腦知識與技術,2009,36(5):10227-10229.

[16] ZAHAVI E,KESLASSY I,Kolodny A.Distributed adaptive routing convergence to non-blocking DCN routing assignments[J].IEEE Journal on Selected Areas in Communications,2014,32(1):88-101.