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

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

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

1 引言

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

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

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

2 SDN方案設(shè)計

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

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

2.1 拓撲采集模塊

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

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

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

1）已用帶寬

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

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

2）時延

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

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

2）交換機B收到了交換機A發(fā)送過來的數(shù)據(jù)包，無法匹配對應流表項，從而Packet_in到控制器?？刂破鹘邮盏竭@個數(shù)據(jù)包之后，和當下時間相減，得到時間差T1。

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

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

5）交換機A到交換機B的鏈路時延dela.b為

2.3 路由計算模塊

將胖樹網(wǎng)絡(luò)拓撲抽象為有向圖G(N，V)，N表示網(wǎng)絡(luò)中節(jié)點的集合，V表示網(wǎng)絡(luò)中鏈路的集合。

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

因為路徑的剩余帶寬取決于路徑中鏈路的最小剩余帶寬，所以路徑li的剩余帶寬bwi為

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

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

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

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

圖2 路由算法流程圖

2.4 流表下發(fā)模塊

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

3 仿真實驗與分析

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

圖3 仿真實驗拓撲圖

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

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

圖4 鏈路平均利用率對比圖

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

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

4 結(jié)語

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