基于SDN的胖樹數據中心網絡多路徑路由算法

彭大芹,,

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

0 概述

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

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

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

1 路由方案設計

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

圖1 路由方案總體框架

1.1 網絡狀態信息收集

本節由信息統計模塊完成,包括對網絡中鏈路帶寬和大流信息的統計收集。

1)鏈路帶寬信息

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

圖2 端口帶寬信息

2)大流信息

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

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

1.2 路由算法實現

1.2.1 核心思想

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

1)大流選路

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

(1)

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

(2)

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

(3)

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

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

2)小流選路

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

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

圖3 路由算法流程

1.2.2 算法實現

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

MLF算法的具體步驟如下:

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

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

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

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

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

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

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

2 實驗與結果分析

2.1 仿真環境設置

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

圖4 網絡拓撲場景

2.2 結果分析

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

(4)

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

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

圖5 平均鏈路利用率對比

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

圖6 網絡吞吐量對比

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

圖7 區分大小流對網絡吞吐量的影響

3 結束語

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

[1] 中國互聯網信息中心.第37次中國互聯網絡發展狀態統計報告[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] 蔡岳平,王昌平.軟件定義數據中心網絡混合路由機制[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網絡的快速流調度策略[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的網絡性能測量研究[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.