雷田穎林子薇何榮希劉家懌

SDN中多鏈路狀態(tài)路由算法?

雷田穎林子薇何榮希劉家懌

（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連116026）

針對(duì)軟件定義網(wǎng)絡(luò)（SDN）易于獲取鏈路狀態(tài)信息的特點(diǎn)，綜合考慮鏈路的時(shí)延和可用帶寬兩種因素的影響，提出一種多鏈路狀態(tài)路由算法（MLSR），并通過(guò)Mininet和Floodlight進(jìn)行仿真。仿真結(jié)果表明：與文獻(xiàn)中已有算法相比，ML?SR具有更低的傳輸時(shí)延和丟包率。

軟件定義網(wǎng)絡(luò)；鏈路狀態(tài)；路由；Floodlight；Mininet

Class NumberTP393

1引言

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）具有松耦合的控制平面與數(shù)據(jù)平面，支持集中化的網(wǎng)絡(luò)狀態(tài)控制，能實(shí)現(xiàn)底層網(wǎng)絡(luò)設(shè)施對(duì)上層應(yīng)用的透明［1～2］，與傳統(tǒng)網(wǎng)絡(luò)相比，具有靈活、開(kāi)放、簡(jiǎn)單等特點(diǎn)，已得到業(yè)界的廣泛認(rèn)可。SDN網(wǎng)絡(luò)架構(gòu)分為應(yīng)用層、控制層和數(shù)據(jù)層，層與層之間通過(guò)南、北向接口相應(yīng)的協(xié)議實(shí)現(xiàn)通信［3］。OpenFlow是目前最流行的南向接口協(xié)議，其最小數(shù)據(jù)交換單位為流。交換機(jī)根據(jù)控制器生成并統(tǒng)一下發(fā)的流表來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)流［4］。

如何設(shè)計(jì)和實(shí)現(xiàn)高效的路由策略是SDN中一個(gè)關(guān)鍵問(wèn)題，目前已有不少文獻(xiàn)［5～8］對(duì)此進(jìn)行討論。最小跳數(shù)路由［5］（Minimum Hop Routing，MHR）、輪詢(xún)路由［6］（Round-Robin Routing，RRR）、等價(jià)多徑路由［7］（Equal-Cost Multi-Path，ECMP）和基于鏈路關(guān)鍵動(dòng)態(tài)路由［8］（Dynamic Routing Algo?rithm based on Link Critical Degree，DraLCD）是目前控制器中使用較多的四種路由策略。MHR算法［5］總是選擇源和目的交換機(jī)之間跳數(shù)最少路徑，路徑一旦選擇則始終使用該路徑。當(dāng)兩個(gè)交換機(jī)節(jié)點(diǎn)之間存在多條可達(dá)路由時(shí)，可能導(dǎo)致剩余路徑空閑而產(chǎn)生資源浪費(fèi)。RRR［6］和隨機(jī)ECMP［7］算法雖然避免了資源浪費(fèi)的問(wèn)題，但是與MHR［5］一樣，均未能利用網(wǎng)絡(luò)的實(shí)時(shí)鏈路狀態(tài)信息。DraLCD算法［8］基于剩余鏈路帶寬來(lái)選路，有利于根據(jù)實(shí)時(shí)鏈路情況進(jìn)行路徑選擇，但是該算法在拓?fù)涔芾頃r(shí)獲取鏈路的帶寬信息，而在路由選擇時(shí)的實(shí)時(shí)數(shù)據(jù)可能會(huì)與已獲取的數(shù)據(jù)存在一定偏差。更重要的是，該算法沒(méi)有考慮鏈路的時(shí)延，僅利用局部信息選擇下一跳鏈路，并沒(méi)有充分利用SDN可以獲取全網(wǎng)信息的優(yōu)勢(shì)，從全局考慮來(lái)選擇最佳路由。實(shí)際上，網(wǎng)絡(luò)中各個(gè)鏈路的時(shí)延和帶寬是動(dòng)態(tài)變化的，而且各不相同，因此，很有必要綜合考慮時(shí)延及可用帶寬等鏈路狀態(tài)信息的影響，設(shè)計(jì)一種更高效的路由算法。

為此，本文針對(duì)SDN設(shè)計(jì)并實(shí)現(xiàn)了一種根據(jù)網(wǎng)絡(luò)中多種實(shí)時(shí)鏈路狀態(tài)信息進(jìn)行路由選擇的多鏈路狀態(tài)路由算法（Multiple Link-state Routing，ML?SR），該算法通過(guò)改寫(xiě)Floodlight控制器［9］的源碼，利用SDN控制器可以掌控全網(wǎng)信息的優(yōu)勢(shì)，從全局考慮，綜合分析源交換機(jī)到目的交換機(jī)的每一條路徑所經(jīng)鏈路的平均時(shí)延和平均剩余帶寬等狀態(tài)信息，進(jìn)而選出一條綜合代價(jià)最小的最佳路徑。最后利用Mininet［10］對(duì)所設(shè)計(jì)算法進(jìn)行仿真評(píng)測(cè)，仿真結(jié)果驗(yàn)證了算法的有效性。

2 MLSR算法描述

SDN的系統(tǒng)架構(gòu)如圖1所示，主要分成數(shù)據(jù)轉(zhuǎn)發(fā)層和Floodlight控制層兩部分。其中，數(shù)據(jù)轉(zhuǎn)發(fā)層主要是由轉(zhuǎn)發(fā)設(shè)備和SFlow代理兩部分構(gòu)成；Floodlight控制器主要包括全網(wǎng)感知模塊、鏈路發(fā)現(xiàn)決策模塊、流表下發(fā)模塊和SFlow控制器。

圖1 系統(tǒng)架構(gòu)

在Floodlight控制器中，首先通過(guò)全網(wǎng)感知模塊獲得各設(shè)備的連接方式，進(jìn)而獲取全網(wǎng)拓?fù)浣Y(jié)構(gòu)。然后通過(guò)鏈路發(fā)現(xiàn)決策模塊實(shí)現(xiàn)MLSR算法，完成最佳路徑選擇。SFlow控制器通過(guò)Restlet框架和JSON數(shù)據(jù)以及正則表達(dá)式技術(shù)，為鏈路發(fā)現(xiàn)決策模塊提供鏈路選擇所需實(shí)時(shí)流量信息。最后流表下發(fā)模塊根據(jù)所獲取的最佳路徑，通知該路徑途經(jīng)交換機(jī)進(jìn)行流表更新。

MLSR算法通過(guò)鏈路發(fā)現(xiàn)決策模塊實(shí)現(xiàn)，可分成鏈路發(fā)現(xiàn)子模塊和鏈路選擇子模塊兩部分。

鏈路發(fā)現(xiàn)子模塊的主要工作過(guò)程為：

1）獲取全網(wǎng)節(jié)點(diǎn)的鄰接矩陣relations［total］［total］，其中total為全網(wǎng)交換機(jī)的個(gè)數(shù)。

2）分別獲取源和目的交換機(jī)節(jié)點(diǎn)的標(biāo)號(hào)src和dst。

3）初始化存放路徑的堆棧stack，將src放入stack。

4）調(diào)用findRoute（src，dst，relations，stack）方法獲取路徑。其中，findRoute方法的偽代碼為

鏈路發(fā)現(xiàn)子模塊完成上述步驟后可獲取源、目的交換機(jī)節(jié)點(diǎn)之間的所有路徑，并存放到路由集合R中。鏈路選擇子模塊通過(guò)Java的IO流技術(shù)從配置文件中獲取鏈路的時(shí)延和初始可用帶寬信息，然后從SFlow控制器獲取鏈路的實(shí)時(shí)流量信息，從而調(diào)用MLSR算法進(jìn)行最佳路徑選擇。

MLSR算法綜合考慮鏈路的時(shí)延和帶寬使用情況來(lái)選擇代價(jià)最小的路徑。將源、目的交換機(jī)中第i條路徑ri的代價(jià)定義為

其中，di和bi表示ri所經(jīng)過(guò)鏈路平均時(shí)延和平均可用帶寬，其值由式（2）和（3）決定；α為小于1的常量，表示di和bi所占權(quán)重，α越大則di在ci中起的作用越大。

其中，dij表示ri中第j段鏈路lij的時(shí)延，而bij表示lij的可用帶寬；tij表示lij的初始帶寬；uij表示lij的已用帶寬，N表示路徑中的鏈路條數(shù)。

MLSR算法流程圖如圖2所示。當(dāng)新的數(shù)據(jù)流被發(fā)送到控制器后，路由引擎會(huì)首先觸發(fā)路徑發(fā)現(xiàn)模塊，通過(guò)該模塊獲取源和目的交換機(jī)之間的所有路徑并存放到路由集合中。然后通過(guò)路徑選擇模塊根據(jù)網(wǎng)絡(luò)的鏈路狀態(tài)信息從路由集合中進(jìn)行最佳路徑的選擇。路徑選擇模塊由式（2）和式（3）計(jì)算出di和bi，然后再由式（1）計(jì)算出路徑發(fā)現(xiàn)模塊中獲得的所有路徑的代價(jià)ci，最后獲得其中最小的代價(jià)MinCost，進(jìn)而利用MinCost獲取最佳路徑，并將此路徑告知給流表下發(fā)模塊。

圖2 MLSR算法流程圖

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

本節(jié)將通過(guò)Floodlight遠(yuǎn)程控制器［9］和Mininet網(wǎng)絡(luò)仿真工具［10］對(duì)MLSR算法進(jìn)行仿真測(cè)試，并與MHR［5］、RRR［6］、ECMP［7］和DraLCD［8］四種算法進(jìn)行對(duì)比。Mininet是由Stanford大學(xué)開(kāi)發(fā)的虛擬化平臺(tái)，可以在PC機(jī)上測(cè)試SDN，或者對(duì)基于OpenFlow協(xié)議進(jìn)行開(kāi)發(fā)驗(yàn)證，Mininet還提供了可編程的接口，通過(guò)編寫(xiě)Python語(yǔ)言腳本，即可實(shí)現(xiàn)更為復(fù)雜的自定義的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［10］。

仿真網(wǎng)絡(luò)拓?fù)淙鐖D3所示，鏈路初始狀態(tài)按表1設(shè)置。通過(guò)ping命令和Iperf技術(shù)，對(duì)上述5種算法的傳輸時(shí)延和丟包率進(jìn)行仿真測(cè)試，仿真中α= 0.5。針對(duì)每種情況分別進(jìn)行10次隨機(jī)實(shí)驗(yàn)，然后對(duì)各次實(shí)驗(yàn)結(jié)果取平均，所得結(jié)果如圖4和5所示。

表1 鏈路的初始狀態(tài)信息

圖3 仿真網(wǎng)絡(luò)拓?fù)鋱D

首先，通過(guò)ping命令在主機(jī)h1上向主機(jī)h4發(fā)送不同字節(jié)大小的數(shù)據(jù)流來(lái)測(cè)試不同算法的傳輸時(shí)延，仿真結(jié)果如圖4所示。

圖4 不同算法的傳輸時(shí)延比較

從圖4可以看出：隨著數(shù)據(jù)流大小的增大，各個(gè)算法的傳輸時(shí)延逐漸增大。其中MHR算法傳輸時(shí)延最大，MLSR算法最小，RRR、ECMP和DraLCD居中，而且DraLCD的傳輸時(shí)延低于其他兩種算法。另外，當(dāng)數(shù)據(jù)流大小不超過(guò)30k字節(jié)時(shí)，RRR算法、ECMP算法和DraLCD算法的時(shí)延表現(xiàn)相當(dāng)。而當(dāng)數(shù)據(jù)流大于30k字節(jié)后，RRR和ECMP傳輸時(shí)延大幅度增加。這是由于此時(shí)傳輸路徑上開(kāi)始出現(xiàn)擁塞鏈路，而RRR和ECMP沒(méi)有考慮網(wǎng)絡(luò)鏈路狀態(tài)，因此，會(huì)導(dǎo)致傳輸時(shí)延的快速增長(zhǎng)。與之對(duì)應(yīng)的是，DraLCD和MLSR考慮了鏈路狀態(tài)，可以根據(jù)實(shí)時(shí)情況選擇最佳路徑，因此傳輸時(shí)延增長(zhǎng)趨勢(shì)平穩(wěn)。另外，與其他四種算法相比，MLSR算法考慮的因素更為全面，因此傳輸時(shí)延始終最小。

其次，通過(guò)在主機(jī)h1上安裝Iperf的客戶(hù)端，在主機(jī)h4上安裝Iperf的服務(wù)器端，來(lái)測(cè)量?jī)芍鳈C(jī)之間不同算法的丟包率，仿真結(jié)果如圖5所示。

圖5 不同算法的丟包率比較

從圖5可以看出：數(shù)據(jù)發(fā)送速率在20Mbps以?xún)?nèi)時(shí)，各個(gè)算法的丟包率差別不大，但MLSR算法的丟包率更小。當(dāng)數(shù)據(jù)發(fā)送速率大于20Mbps后，MHR算法的丟包率急劇增加，RRR算法和隨機(jī)ECMP算法的丟包率也明顯增加，DraLCD算法的丟包率有所增加，但是MLSR算法的丟包率變化不明顯，仍然低于其他四種算法。主要原因在于：MHR算法選擇的路徑始終為s1-s4，其帶寬與發(fā)送速率匹配程度嚴(yán)重失衡，導(dǎo)致鏈路負(fù)荷過(guò)重，所以隨著發(fā)送速率的增加，丟包率越來(lái)越大。而RRR算法和ECMP算法所選路徑也存在負(fù)荷不均衡問(wèn)題，所以其丟包率也較大。由于MLSR算法實(shí)時(shí)根據(jù)網(wǎng)絡(luò)的負(fù)載情況動(dòng)態(tài)調(diào)整路徑，可以最大限度地從當(dāng)前網(wǎng)絡(luò)中選擇最優(yōu)鏈路進(jìn)行數(shù)據(jù)傳輸，因此，丟包率最小。

從以上實(shí)驗(yàn)結(jié)果可以看出：當(dāng)網(wǎng)絡(luò)鏈路負(fù)載較低時(shí)，五種路由算法表現(xiàn)相當(dāng)，傳輸時(shí)延和丟包率均較低；但是，隨著負(fù)載的增加，網(wǎng)絡(luò)中逐漸出現(xiàn)擁塞，此時(shí)由于MLSR算法能根據(jù)鏈路的時(shí)延和帶寬狀態(tài)動(dòng)態(tài)調(diào)整路徑的權(quán)值，有利于更合理地選擇路徑，因此具有更好的性能。

4結(jié)語(yǔ)

利用SDN易于獲取全網(wǎng)鏈路狀態(tài)信息的優(yōu)點(diǎn)，綜合考慮鏈路的平均時(shí)延和平均剩余帶寬，提出一種多鏈路狀態(tài)路由算法（MLSR），并通過(guò)Mininet和Floodlight進(jìn)行仿真評(píng)測(cè)。仿真結(jié)果表明：MLSR算法可以改善網(wǎng)絡(luò)的傳輸時(shí)延，具有更低的丟包率。但是MLSR算法只是選擇了影響數(shù)據(jù)傳輸?shù)闹T多因素中最重要的兩個(gè)因素，在下一步研究中可考慮其他因素的影響，例如交換機(jī)中流表的處理能力等，設(shè)計(jì)更有效的綜合路由策略。

［1］Nunes B A A，Mendonca M，Nguyen X N，et al.A survey of software-defined networking：Past，present，and future of programmable networks［J］.IEEE Communications Sur?veys&Tutorials，2014，16（3）：1617-1634.

［2］蔡岳平，王昌平.軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)混合路由機(jī)制［J］.通信學(xué)報(bào)，2016，37（4）：44-52.

CAI Yueping，WANG Cangping.Software defined data center network with hybrid routing［J］.Journal on Commu?nications，2016，37（4）：44-52.

［3］張朝昆，崔勇，唐翯祎，等.軟件定義網(wǎng)絡(luò)（SDN）研究進(jìn)展［J］.軟件學(xué)報(bào)，2015，26（1）：62-81.

ZHANG Chaokun，CUI Yong，TANG Heyi，et al. State-of-the-Art survey on software-defined networking（SDN）［J］.Journalof Software，2015，26（1）：62-81.

［4］左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術(shù)［J］.軟件學(xué)報(bào)，2013，24（5）：1078-1097.

ZUO Qingyun，CHEN Ming，ZHAO Guangsong，et al.Re?search on Open Flow-based SDN technologies［J］.Journal of Software，2013，24（5）：1078-1097.

［5］Cormen T H，Leiserson C E，Rivest R L，etal.Introduction to Algorithms.An introduction to element theory［M］.Ed?inburgh：Edinburgh University Press，2011：14-24.

［6］魏凱.基于蟻群算法SDN負(fù)載均衡的研究［D］.吉林：吉林大學(xué)碩士學(xué)位論文，2015：32-38.

WEI Kai.The Load Balancing Research of SDN Based on Ant Colony Algorithm［D］.Jilin：Jilin University，2015：32-38.

［7］Ho T V，Yves D，Oliver B，et al.Traffic engineering for multiple spanning tree protocol in large data centers［C］// Proceedings ofthe 2011 23rd International Teletraffic Con?gress（ITC），2011：23-30.

［8］楊洋，楊家海，秦董洪.一種新的數(shù)據(jù)中心多路徑路由方案研究［J］.中國(guó)科技論文在線，2015，8（16）：1688-1695.http：//www.paper.edu.cn/

YANG Yang，YANG Jiahai，QIN Donghong.A Novelmul?tipath routing scheme for Data Center Network［J］.Scien?cepaper Online，2015，8（16）：1688-1695.http：//www.pa?per.edu.cn/

［9］SONG Haoyu.Protocol-oblivious forwarding：Unleash the power of SDN through a future-proof forwarding plane［C］//Proceedings of the second ACM SIGCOMM work?shop on Hot topics in software defined networking.ACM，2013：127-132.

［10］De Oliveira R L S，Schweitzer C M，Shinoda A A，etal. Using mininetfor emulation and prototyping software-de?fined networks［C］//IEEE Colombian Conference on Com?munications and Computing（COLCOM），IEEE，2014：1-6.

Multiple Link-state Routing Algorithm in Software Defined Networks

LEI Tianying LIN Ziwei HE Rongxi LIU Jiayi
（College of Information Science and Technology，Dalian Maritime University，Dalian 116026）

Based on the feature that Software Defined Networks（SDN）that can easily obtain the link-state information，this paper proposes a Multiple Link-state Routing Algorithm（MLSR），with an integrated consideration of the influence of link delay and available bandwidth.And then the performance ofproposed algorithm is evaluated based on Mininetand Floodlight.The simula?tion results show that MLSR has lower transmission delay and packetloss rate than other existing algorithms presented in literature.

software defined network（SDN），link state，floodlight，mininet，routing

TP393

10.3969/j.issn.1672-9722.2017.08.026

2017年2月10日，

2017年3月24日

國(guó)家自然科學(xué)基金項(xiàng)目（編號(hào)：61371091）；大連海事大學(xué)“十三五”重點(diǎn)科研項(xiàng)目（編號(hào)：3132016318）資助。

雷田穎，男，碩士研究生，研究方向：SDN與數(shù)據(jù)中心網(wǎng)絡(luò)的路由策略。林子薇，女，碩士研究生，研究方向：SDN與數(shù)據(jù)中心網(wǎng)絡(luò)的路由策略。何榮希，男，博士，教授，研究方向：通信網(wǎng)絡(luò)及其相關(guān)技術(shù)。劉家懌，男，研究方向：機(jī)器學(xué)習(xí)/數(shù)據(jù)分析。