基于SDN的數(shù)據(jù)中心網(wǎng)絡路由算法研究

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

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

基于SDN的數(shù)據(jù)中心網(wǎng)絡路由算法研究

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

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

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

數(shù)據(jù)中心；SDN；Fat-Tree；路由算法

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

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

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

圖1 路由機制總體設計

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

2 算法思想及實現(xiàn)流程

式中：Lin是第i條鏈路第n個統(tǒng)計周期T1內(nèi)的負載，是該周期內(nèi)端口發(fā)送的字節(jié)數(shù)，是同周期內(nèi)端口接收的字節(jié)數(shù)。

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

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

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

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

算法1改進的ECMP算法。

輸入：新數(shù)據(jù)流f；

Fat-tree拓撲全網(wǎng)信息；

鏈路負載信息Lin；

輸出：新數(shù)據(jù)流的路徑Path

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

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

（3）根據(jù)最高層節(jié)點計算f的所有等價路徑Paths。

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

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

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

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

輸入：Fat-Tree拓撲全網(wǎng)信息；

鏈路統(tǒng)計信息；

擁塞鏈路L上的大流Flows；

輸出：Flows中大流的路徑Path

（1）For f in Flowsdo。

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

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

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

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

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

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

圖2 處理流程

3 實驗仿真與結果分析

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

3.1 實驗環(huán)境搭建

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

3.2 性能分析

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

圖3 網(wǎng)絡吞吐量仿真對比

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

4 結語

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

圖4 分組時延仿真對比

圖5 鏈路利用率仿真對比

[1]中國互聯(lián)網(wǎng)信息中心.第37次中國互聯(lián)網(wǎng)絡發(fā)展狀態(tài)統(tǒng)計報告[R].北京：中國互聯(lián)網(wǎng)絡信息中心，2016.

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

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

[4]蔡岳平，王昌平.軟件定義數(shù)據(jù)中心網(wǎng)絡混合路由機制[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— ），男，江西吉水，碩士研究生；研究方向：未來網(wǎng)絡，SDN。

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