一種基于SDN的數(shù)據(jù)中心負(fù)載均衡路由算法*

徐新羽 戴新發(fā) 夏 靜 李文鋮

（武漢數(shù)字工程研究所 武漢 430205）

1 引言

隨著云計(jì)算［1］和大數(shù)據(jù)的發(fā)展，數(shù)據(jù)中心的流量模型發(fā)生了巨大變化，東西向流量取代了南北向流量，占據(jù)了主導(dǎo)地位，比例可達(dá)70%以上。東西向流量的爆發(fā)意味著數(shù)據(jù)中心內(nèi)大部分的流量都將發(fā)生在服務(wù)器之間，從而導(dǎo)致傳統(tǒng)數(shù)據(jù)中心內(nèi)部的通信帶寬已經(jīng)無法滿足流量的傳輸需求［2～3］。因此，具有分層的多根網(wǎng)絡(luò)拓?fù)涞呐謽洌?～5］結(jié)構(gòu)逐漸成為主流，其具有很好的擴(kuò)展性，并能夠?yàn)閷俨煌琍OD的服務(wù)器提供多條等價(jià)路徑，進(jìn)而提供高帶寬和高容錯(cuò)性。

ECMP［6］（Equal Cost Multi-Path）算法是一種經(jīng)典的多路徑路由算法，其基于靜態(tài)哈希進(jìn)行路徑選擇，在一定程度上利用了胖樹拓?fù)浣Y(jié)構(gòu)帶來的等價(jià)路徑，實(shí)現(xiàn)了數(shù)據(jù)的快速轉(zhuǎn)發(fā)。然而，ECMP沒有考慮鏈路的實(shí)時(shí)傳輸狀態(tài)，以隨機(jī)的哈希方式選擇路徑，有可能導(dǎo)致?lián)砣DN［7～8］是一種新型的網(wǎng)絡(luò)架構(gòu)，其核心是將控制平面從傳統(tǒng)網(wǎng)絡(luò)的單個(gè)設(shè)備中剝離，集中到中央控制器上；數(shù)據(jù)平面由支持南向接口協(xié)議的轉(zhuǎn)發(fā)設(shè)備完成。其具有三大特征：1）網(wǎng)絡(luò)可編程；2）轉(zhuǎn)發(fā)與控制分離；3）集中式控制。因此，SDN能夠獲取數(shù)據(jù)中心的全局網(wǎng)絡(luò)信息，包括可用路徑以及它們的剩余帶寬和時(shí)延等，并據(jù)此統(tǒng)一為轉(zhuǎn)發(fā)設(shè)備制訂轉(zhuǎn)發(fā)策略，因而基于SDN的路由算法可以很好解決網(wǎng)絡(luò)負(fù)載均衡的問題。

綜上所述，要實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡，必須考慮鏈路的實(shí)時(shí)狀態(tài)。據(jù)此，本文提出了一種基于SDN的數(shù)據(jù)中心負(fù)載均衡路由算法，該算法依據(jù)SDN控制器獲取的全局網(wǎng)絡(luò)信息對(duì)進(jìn)入交換機(jī)的流量進(jìn)行集中控制，為其選擇最優(yōu)的傳輸路徑。

2 SDN方案設(shè)計(jì)

SDN方案由作為控制平面的控制器和和作為轉(zhuǎn)發(fā)平面的OpenFlow［9］交換機(jī)組成，交換機(jī)的拓?fù)浣Y(jié)構(gòu)采用胖樹拓?fù)浣Y(jié)構(gòu)。其中，在控制器中設(shè)計(jì)以下四個(gè)模塊：拓?fù)洳杉K，信息監(jiān)視模塊，路由計(jì)算模塊和流表下發(fā)模塊。拓?fù)洳杉K可以采集交換機(jī)各個(gè)端口的連接信息，并將其存儲(chǔ)起來；信息監(jiān)視模塊用來監(jiān)視網(wǎng)絡(luò)鏈路的已用帶寬和時(shí)延，并記錄下來；路由計(jì)算模塊依據(jù)網(wǎng)絡(luò)的拓?fù)湫畔⒑透鱾€(gè)鏈路的已用帶寬和時(shí)延計(jì)算出數(shù)據(jù)流轉(zhuǎn)發(fā)路徑；流表下發(fā)模塊根據(jù)路由計(jì)算模塊得出的路徑，向交換機(jī)下發(fā)流表，控制交換機(jī)中數(shù)據(jù)的轉(zhuǎn)發(fā)。

圖1 控制器模塊關(guān)系圖

2.1 拓?fù)洳杉K

在該模塊里，主要使用Ryu控制器［10］提供的get_switch（）方法和get_link（）方法。get_switch（）方法用來獲取網(wǎng)絡(luò)中的所有交換機(jī)，get_link（）方法用來采集網(wǎng)絡(luò)中交換機(jī)之間的鏈路信息。采集到交換機(jī)列表和鏈路鏈表后，再通過NetworkX［11］將這些信息記錄下來，供路由計(jì)算模塊調(diào)用。

2.2 信息監(jiān)視模塊

該模塊用來監(jiān)視鏈路的已用帶寬和時(shí)延。

1）已用帶寬

本文通過控制器每間隔10s主動(dòng)向交換機(jī)發(fā)送一個(gè)request_stats消息，從而使得交換機(jī)將端口信息返回給控制器，從返回信息中提取rx，tx和durt，rx表示接收到的字節(jié)數(shù)，tx表示發(fā)出的字節(jié)數(shù)，durt表示持續(xù)時(shí)間。假設(shè)，第一次統(tǒng)計(jì)到的數(shù)據(jù)為rx1，tx1，durt1；第二次統(tǒng)計(jì)的數(shù)據(jù)為rx2，tx2，durt2，則端口的速率sp為

鏈路的已用帶寬取決于連接鏈路兩端端口速率小的一方。假設(shè)，一端口的速率為sp1；另一端口的速率為sp2。則鏈路的已用帶寬bwu為

2）時(shí)延

假設(shè)要獲取交換機(jī)A和交換機(jī)B之間的時(shí)延，步驟如下：

1）控制器向交換機(jī)A下發(fā)一個(gè)Packet_out報(bào)文。報(bào)文的數(shù)據(jù)段攜帶了一個(gè)約定好了的協(xié)議報(bào)文，其報(bào)文的數(shù)據(jù)段攜帶了控制器下發(fā)報(bào)文時(shí)的時(shí)間戳。Packet_out報(bào)文的動(dòng)作指示交換機(jī)將其泛洪或者轉(zhuǎn)發(fā)到某端口。

2）交換機(jī)B收到了交換機(jī)A發(fā)送過來的數(shù)據(jù)包，無法匹配對(duì)應(yīng)流表項(xiàng)，從而Packet_in到控制器。控制器接收到這個(gè)數(shù)據(jù)包之后，和當(dāng)下時(shí)間相減，得到時(shí)間差T1。

3）控制器向交換機(jī)B發(fā)送一個(gè)類似的報(bào)文。然后控制器從交換機(jī)A收到Packet_in報(bào)文，記下時(shí)間差T2。

4）控制器向交換機(jī)A和交換機(jī)B分別發(fā)送帶有時(shí)間戳的echo_request。交換機(jī)收到之后即刻回復(fù)攜帶echo_request時(shí)間的echo_reply消息。所以控制可以通過echo_reply的時(shí)間戳減去echo_re?quest攜帶的時(shí)間，從而得到對(duì)應(yīng)交換機(jī)和控制器之間的RTT。這樣就可以得到控制器到A，B的RTT分別為Ta和Tb。

5）交換機(jī)A到交換機(jī)B的鏈路時(shí)延dela.b為

2.3 路由計(jì)算模塊

將胖樹網(wǎng)絡(luò)拓?fù)涑橄鬄橛邢驁DG(N，V)，N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，V表示網(wǎng)絡(luò)中鏈路的集合。

首先通過Dijkstra算法求得k個(gè)POD的胖樹拓?fù)涞膋條最短路徑，用li表示，i=(1...k)。假設(shè)li有n條鏈路，根據(jù)胖樹拓?fù)浣Y(jié)構(gòu)的特點(diǎn)可知，每條鏈路的容量是一樣的，設(shè)為bwa。通過信息監(jiān)視模塊可以獲取第i(i=1...k)條路徑的第j（j=1..n)條鏈路的的已用帶寬bwu-ij，則該鏈路的剩余帶寬bwij為

因?yàn)槁窂降氖Ｓ鄮捜Q于路徑中鏈路的最小剩余帶寬，所以路徑li的剩余帶寬bwi為

通過信息監(jiān)視模塊可以獲得第i(i=1...k)條路徑的第j（j=1..n)條鏈路的時(shí)延delij，因?yàn)槁窂降臅r(shí)延等于所有鏈路的時(shí)延總和，所以所以路徑li的的時(shí)延deli為

為了綜合考慮路徑的剩余帶寬和時(shí)延，將路徑權(quán)重設(shè)置為剩余帶寬和時(shí)延的比值，則則路徑li的權(quán)重wi為

求得每條路徑的權(quán)值，選擇權(quán)值最大的一條路徑，作為流的傳輸路徑。當(dāng)存在多條路徑的權(quán)值相等且最大時(shí)，隨機(jī)選擇一條路徑作為流的傳輸路徑。

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

圖2 路由算法流程圖

2.4 流表下發(fā)模塊

在該模塊里，使用了ryu控制器提供的OFP?FlowMod類創(chuàng)建流表項(xiàng)信息，并使用datapath.send_msg（）方法，將流表項(xiàng)下發(fā)給相應(yīng)交換機(jī)。

3 仿真實(shí)驗(yàn)與分析

采用 Mininet［12］網(wǎng)絡(luò)仿真軟件和ryu 控制器搭建實(shí)驗(yàn)仿真平臺(tái)。實(shí)驗(yàn)拓?fù)洳捎煤袃蓚€(gè)POD的胖樹拓?fù)浣Y(jié)構(gòu)，如圖3所示，包含10臺(tái)OpenFlow交換機(jī)和8臺(tái)主機(jī)。網(wǎng)絡(luò)中的所有鏈路均設(shè)為全雙工鏈路，鏈路帶寬設(shè)為1Gb/s，并使用iperf工具產(chǎn)生模擬的數(shù)據(jù)中心流量，令主機(jī)h1-h4向主機(jī)h5-h8發(fā)送數(shù)據(jù)流。

圖3 仿真實(shí)驗(yàn)拓?fù)鋱D

因?yàn)楸疚牡哪繕?biāo)是使多路徑網(wǎng)絡(luò)拓?fù)鋵?shí)現(xiàn)負(fù)載均衡，所以選取網(wǎng)路的鏈路平均利用率作為評(píng)價(jià)指標(biāo)，但是只參考鏈路平均利率路不夠，還要考慮數(shù)據(jù)傳輸性能，因此再選取網(wǎng)絡(luò)吞吐量作為評(píng)價(jià)指標(biāo)。并與ECMP算進(jìn)行對(duì)比，驗(yàn)證本文算法的有效性和優(yōu)勢(shì)。

如圖4所示，0～10s之間，本文算法和ECMP算法的網(wǎng)絡(luò)鏈路平均利用率幾乎一樣，因?yàn)閷?shí)驗(yàn)開始，各條鏈路的實(shí)時(shí)狀態(tài)沒有差別，依據(jù)鏈路實(shí)時(shí)信息進(jìn)行選路的本文算法和隨機(jī)選路的ECMP算法沒有明顯差別。隨著時(shí)間的推移，網(wǎng)絡(luò)中的各條鏈路的狀態(tài)已經(jīng)不再一樣，時(shí)延和剩余帶寬都有了差別，所以依據(jù)鏈路實(shí)時(shí)狀態(tài)選擇最優(yōu)路徑的本文算法就比ECMP算法更加有效地利用了多路徑的鏈路資源，所以鏈路的平均利用率就比ECMP算法高。

圖4 鏈路平均利用率對(duì)比圖

如圖5所示，發(fā)包速率在0～500Mb/s之間，本文算法和ECMP算法的網(wǎng)絡(luò)吞吐量基本一樣。當(dāng)發(fā)包速率大于550Mb/s時(shí)，本文算法的網(wǎng)絡(luò)吞吐量明顯大于ECMP算法，這是因?yàn)榛陔S機(jī)選路的EC?MP算法沒有考慮鏈路的實(shí)時(shí)信息，可能將多條流hash到同一條路徑，使得網(wǎng)絡(luò)發(fā)生擁塞，從而降低了網(wǎng)絡(luò)的吞吐量。而依據(jù)鏈路信息進(jìn)行選路的本文算法會(huì)依據(jù)鏈路的實(shí)時(shí)狀態(tài)進(jìn)行選路，有效地避免擁塞，所以吞吐量要高于ECMP算法。

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

4 結(jié)語

本文設(shè)計(jì)了一種基于SDN的負(fù)載均衡路由算法，綜合考慮了鏈路的剩余帶寬和時(shí)延，重新設(shè)定路徑權(quán)值，并選擇權(quán)值最大的路徑進(jìn)行數(shù)據(jù)的傳輸。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的多路徑路由算法EC?MP相比，本文算法在鏈路平均利用率和網(wǎng)絡(luò)吞吐量等方面有一定的提高。