基于SDN的數據中心網絡路由算法研究

賴香武，彭大芹＊，黃德玲，劉艷林

（重慶郵電大學 通信與信息工程學院，重慶 400065）

基于SDN的數據中心網絡路由算法研究

賴香武，彭大芹＊，黃德玲，劉艷林

（重慶郵電大學 通信與信息工程學院，重慶 400065）

針對云計算、大數據等互聯網應用規模不斷擴大，新應用的發展對傳統網絡提出更高效集中的網絡管理需求、高效靈活的組網需求。文章對在軟件定義網絡架構下的數據中心網絡路由方面展開研究，提出基于流分類的軟件定義數據中心網絡路由算法，使用改進的路由算法，在Fat-Tree架構上建立流量模型并與傳統的ECMP算法進行性能分析和對比。結果表明，文章中提出的路由算法能夠在提高鏈路利用率的基礎上提高網絡吞吐量和降低分組端到端時延。

數據中心；SDN；Fat-Tree；路由算法

隨著云計算、大數據等互聯網應用的快速發展，數據中心內部的通信量正以指數級的速度增長，新型應用對數據中心網絡的帶寬需求不斷增加[1]。與傳統網絡相比，軟件定義網絡（Software Defined Network，SDN）通過集中控制取代了原來的路由協議自協商方式，極大地提升了網絡的管控效率和開放程度，能夠對整個數據中心網絡資源作出全局判斷[2]。文獻[4]發現，數據中心網絡中大部分的數據流量是由小流組成的。近90%的數據流大小不超過1MB，持續時間不超過10秒，而90%的數據流量都集中在大于100 MB的數據流中。文獻[5]提出了一種軟件定義數據中心網絡混合路由機制（Software-Defined Hybrid Routing，SHR）。SHR采取了一種折中的辦法，對數據流進行分類，對不同類型的流量采用不同的路由算法。該機制與傳統ECMP算法相比，雖然降低了數據流丟棄率，提高了網絡吞吐量，但沒有考慮鏈路利用率這方面的性能，給機制帶來一定的缺陷性。

考慮到數據中心網絡的流量特征以及現有路由方式的優缺點，本文提出一種路由策略，該策略從兩方面考慮，針對無法事先知道大小的新流使用改進的ECMP算法進行路由；而針對已經在網絡中轉發的大流則采用考慮路徑整體轉發能力的動態路由算法，當計算出來的路由與原有路由不同時對大流進行重路由。

1 基于流分類的路由機制設計（見圖1）

圖1 路由機制總體設計

圖1是該機制的總體設計圖。簡要描述如下：（1a）對于新到的數據流，由于不知道其大小，故使用改進的ECMP算法，以鏈路的剩余帶寬作為其選擇路徑的概率；每隔T2周期將交換機中已傳輸的數據流信息發送給控制器，對流進行分類。（1b）每隔T1周期將鏈路狀態的統計信息發送到控制器。（2）控制器2為新流和需要進行重路由的大流制定路由策略，最后以流表的形式下發到各個交換機中。

2 算法思想及實現流程

式中：Lin是第i條鏈路第n個統計周期T1內的負載，是該周期內端口發送的字節數，是同周期內端口接收的字節數。

則選擇第i條鏈路的概率為：

式中Bin是第i條鏈路的最大帶寬，l為總鏈路數。先計算出每條鏈路的負載Lin，然后計算出每條鏈路的剩余帶寬（Bin-Lin），將某條鏈路剩余帶寬占所有可選路徑剩余帶寬的比值Pi作為小流分配到該條鏈路的占比，控制器在第n個周期內收到的新流請求按照第n-1個周期計算出來的占比Pi為分配到相應的傳輸鏈路上。

（2）本文設定鏈路利用率大于75%時為擁塞鏈路[6]，當檢測到鏈路存在擁塞情況時，對鏈路中的大流采用路徑整體轉發能力的動態路由算法進行重路由。具體操作流程如圖2所示。

兩種路由策略具體算法描述如下：

算法1改進的ECMP算法。

輸入：新數據流f；

Fat-tree拓撲全網信息；

鏈路負載信息Lin；

輸出：新數據流的路徑Path

（1）獲取f的源主機和目的主機和連接二者的邊緣交換機。

（2）計算兩主機所在的Pod，確定f需要達到的最高層節點。

（3）根據最高層節點計算f的所有等價路徑Paths。

（4）根據Lin計算第i條鏈路的概率。

（5）獲取鏈路i的起點，確定路由的開始節點。

（6）路由到下一跳后繼續向上搜索適合的鏈路。

（7）搜索到最高節點后即可確定到目的主機的路由路徑。算法2大流重路由算法。

輸入：Fat-Tree拓撲全網信息；

鏈路統計信息；

擁塞鏈路L上的大流Flows；

輸出：Flows中大流的路徑Path

（1）For f in Flowsdo。

（2）計算f的所有等價路徑Paths。

（3）計算f當前所占的帶寬。

（4）獲取擁塞鏈路L的起點，確定重路由的開始節點。

（5）向上一層搜索最先適應的鏈路。

（6）若同層中無滿足條件的節點則向下層回溯。

（7）到達最高層節點后，若下行路徑鏈路空閑帶寬>f當前所占帶寬，則返回f的路徑；否則返回（6）。

圖2 處理流程

3 實驗仿真與結果分析

本文在Fat-Tree架構上對提出的軟件定義網絡架構下基于流分類的路由算法進行仿真實驗分析。與傳統的ECMP算法進行對比，展示改進的路由算法在網絡吞吐量、鏈路利用率和時延方面的性能優勢。

3.1 實驗環境搭建

使用Mininet網絡仿真器搭建基于四元Fat-Tree拓撲結構的軟件定義數據中心網絡，選取Floodlight作為仿真實驗所需控制器。參考已有對數據中心網絡內部流量的研究，本次實驗共仿真1萬個流，并且將T1和T2均設置為1s來收集鏈路狀態信息和流的統計信息。

3.2 性能分析

圖3是在Fat-Tree拓撲上分別采用ECMP和改進算法進行路由的網絡吞吐量仿真對比圖。仿真結果表明網絡吞吐量隨著數據流到達速率不斷增加而增加，當邊緣交換機的流到達速率達到2 500條/秒時，改進算法的網絡吞吐量比ECMP算法的網絡吞吐量高12.2%。這是由于ECMP在路徑分配前并沒有檢測負載情況，只能提供靜態的流量均衡。而本文提出的算法按照可行路徑上的負載情況選擇最優路徑，提高了吞吐量。

圖3 網絡吞吐量仿真對比

圖4的仿真結果表示，隨著網絡負載的增加，兩種路由方式的分組時延也隨之增加，ECMP算法的時延明顯要高，且隨著負載的增加，其時延的增長速度也要高些。圖5所示為在不同時刻下，兩種不同路由方式的網絡中所有鏈路的平均鏈路利用率，記錄了網絡中的平均鏈路利用率隨著時間的變化。從圖5中可以看出，本文提出的算法在平均鏈路利用率上要高于傳統的ECMP算法。當鏈路中的流陸續完成轉發時，鏈路的平均利用率呈下降趨勢。

4 結語

本文在軟件定義網絡架構下提出基于流分類的數據中心網絡路由算法，并在Fat-Tree架構上建立流量模型，與傳統的ECMP算法進行性能分析和對比，結果表明提出的路由算法能夠在提高鏈路利用率的基礎上提高網絡吞吐量和降低分組端到端時延。

圖4 分組時延仿真對比

圖5 鏈路利用率仿真對比

[1]中國互聯網信息中心.第37次中國互聯網絡發展狀態統計報告[R].北京：中國互聯網絡信息中心，2016.

[2]黃韜，劉江，魏亮，等.軟件定義網絡核心原理與應用實踐[J].通信學報，2015（3）：288.

[3]陳元謀，周麗娜.基于SDN的云計算數據中心網絡技術探討[J].電子世界，2015（18）：147-148.

[4]蔡岳平，王昌平.軟件定義數據中心網絡混合路由機制[J].通信學報，2016（4）：44-52.

[5]CHU C Y，XI K，LUO M，et al.Congestion-aware single link failure recovery in hybrid SDN networks[C].2015 IEEE Conference Computer Communications，2015：1086-1094.

[6]KANAGEVLU R，AUNG K M M.SDN Controlled Local Re-routing to Reduce Congestion in Cloud Data Center[C].2015 International Conference on Cloud Computing Research and Innovation，2015：80-88.

[7]ZAHAVI E，KESLASSY I，KOLODNY A.Distributed adaptive routing convergence to non-blocking dcn routing assignments[J]. Selected Areas in Communications，2014（1）：88-101.

[8]BHARTI S，PATTANAIK K K.Dynamic Distributed Flow Scheduling with Load Balancing for Data Center Networks [J].Procedia Computer Science，2013（19）：124-130.

[9]SHEN S H，HUANG L H，YANG D N，et al. Reliable multicast routing for software-defined networks[C].2015 IEEE Conference on Computer Communications，2015：181-189.

[10]DUAN J，WANG Z，WU C. Responsive multipath TCP in SDN-based datacenters[C]. IEEE International Conference on Communications，2015.

Research on routing algorithm of data center network based on SDN

Lai Xiangwu, Peng Daqin*, Huang Deling, Liu Yanlin
（Communication and Information Engineering College of Chongqing University of Posts and Telecommunications, Chongqing 400065, China）

With Internet application scale such as cloud computing, big data, expanding unceasingly, the development of new applications for traditional network makes a more efficient centralized network management requirements, highly efficient and flexible network requirements. This paper spread a study in the software-defined data center network routing aspect, putting forward software-defined data center network routing algorithm which based on traffic classification, proposing an improved routing algorithm, building the traffic model on the Fat-Tree architecture and comparing with the traditional ECMP algorithm. The results showed that the proposed routing algorithm can improve network throughput and reduce packet end-to-end delay on the basis of improving link utilization.

data center; SDN; Fat-Tree; routing algorithm

賴香武（1991— ），男，江西吉水，碩士研究生；研究方向：未來網絡，SDN。

＊通訊作者：彭大芹（1969— ），男，四川雅安，碩士，正高級工程師；研究方向：LTE，物聯網以及車聯網標準。