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

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

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

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

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

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

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

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

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

1 基于流分類的路由機(jī)制設(shè)計(jì)（見(jiàn)圖1）

圖1 路由機(jī)制總體設(shè)計(jì)

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

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

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

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

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

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

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

算法1改進(jìn)的ECMP算法。

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

Fat-tree拓?fù)淙W(wǎng)信息；

鏈路負(fù)載信息Lin；

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

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

（2）計(jì)算兩主機(jī)所在的Pod，確定f需要達(dá)到的最高層節(jié)點(diǎn)。

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

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

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

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

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

輸入：Fat-Tree拓?fù)淙W(wǎng)信息；

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

擁塞鏈路L上的大流Flows；

輸出：Flows中大流的路徑Path

（1）For f in Flowsdo。

（2）計(jì)算f的所有等價(jià)路徑Paths。

（3）計(jì)算f當(dāng)前所占的帶寬。

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

（5）向上一層搜索最先適應(yīng)的鏈路。

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

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

圖2 處理流程

3 實(shí)驗(yàn)仿真與結(jié)果分析

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

3.1 實(shí)驗(yàn)環(huán)境搭建

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

3.2 性能分析

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

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

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

4 結(jié)語(yǔ)

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

圖4 分組時(shí)延仿真對(duì)比

圖5 鏈路利用率仿真對(duì)比

[1]中國(guó)互聯(lián)網(wǎng)信息中心.第37次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顟B(tài)統(tǒng)計(jì)報(bào)告[R].北京：中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心，2016.

[2]黃韜，劉江，魏亮，等.軟件定義網(wǎng)絡(luò)核心原理與應(yīng)用實(shí)踐[J].通信學(xué)報(bào)，2015（3）：288.

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

[4]蔡岳平，王昌平.軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)混合路由機(jī)制[J].通信學(xué)報(bào)，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— ），男，江西吉水，碩士研究生；研究方向：未來(lái)網(wǎng)絡(luò)，SDN。

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