SDN中多鏈路狀態路由算法?

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

SDN中多鏈路狀態路由算法?

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

（大連海事大學信息科學技術學院大連116026）

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

軟件定義網絡；鏈路狀態；路由；Floodlight；Mininet

Class NumberTP393

1引言

軟件定義網絡（Software Defined Network，SDN）具有松耦合的控制平面與數據平面，支持集中化的網絡狀態控制，能實現底層網絡設施對上層應用的透明［1～2］，與傳統網絡相比，具有靈活、開放、簡單等特點，已得到業界的廣泛認可。SDN網絡架構分為應用層、控制層和數據層，層與層之間通過南、北向接口相應的協議實現通信［3］。OpenFlow是目前最流行的南向接口協議，其最小數據交換單位為流。交換機根據控制器生成并統一下發的流表來轉發數據流［4］。

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

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

2 MLSR算法描述

SDN的系統架構如圖1所示，主要分成數據轉發層和Floodlight控制層兩部分。其中，數據轉發層主要是由轉發設備和SFlow代理兩部分構成；Floodlight控制器主要包括全網感知模塊、鏈路發現決策模塊、流表下發模塊和SFlow控制器。

圖1 系統架構

在Floodlight控制器中，首先通過全網感知模塊獲得各設備的連接方式，進而獲取全網拓撲結構。然后通過鏈路發現決策模塊實現MLSR算法，完成最佳路徑選擇。SFlow控制器通過Restlet框架和JSON數據以及正則表達式技術，為鏈路發現決策模塊提供鏈路選擇所需實時流量信息。最后流表下發模塊根據所獲取的最佳路徑，通知該路徑途經交換機進行流表更新。

MLSR算法通過鏈路發現決策模塊實現，可分成鏈路發現子模塊和鏈路選擇子模塊兩部分。

鏈路發現子模塊的主要工作過程為：

1）獲取全網節點的鄰接矩陣relations［total］［total］，其中total為全網交換機的個數。

2）分別獲取源和目的交換機節點的標號src和dst。

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

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

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

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

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

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

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

圖2 MLSR算法流程圖

3仿真實驗及結果分析

本節將通過Floodlight遠程控制器［9］和Mininet網絡仿真工具［10］對MLSR算法進行仿真測試，并與MHR［5］、RRR［6］、ECMP［7］和DraLCD［8］四種算法進行對比。Mininet是由Stanford大學開發的虛擬化平臺，可以在PC機上測試SDN，或者對基于OpenFlow協議進行開發驗證，Mininet還提供了可編程的接口，通過編寫Python語言腳本，即可實現更為復雜的自定義的網絡拓撲結構［10］。

仿真網絡拓撲如圖3所示，鏈路初始狀態按表1設置。通過ping命令和Iperf技術，對上述5種算法的傳輸時延和丟包率進行仿真測試，仿真中α= 0.5。針對每種情況分別進行10次隨機實驗，然后對各次實驗結果取平均，所得結果如圖4和5所示。

表1 鏈路的初始狀態信息

圖3 仿真網絡拓撲圖

首先，通過ping命令在主機h1上向主機h4發送不同字節大小的數據流來測試不同算法的傳輸時延，仿真結果如圖4所示。

圖4 不同算法的傳輸時延比較

從圖4可以看出：隨著數據流大小的增大，各個算法的傳輸時延逐漸增大。其中MHR算法傳輸時延最大，MLSR算法最小，RRR、ECMP和DraLCD居中，而且DraLCD的傳輸時延低于其他兩種算法。另外，當數據流大小不超過30k字節時，RRR算法、ECMP算法和DraLCD算法的時延表現相當。而當數據流大于30k字節后，RRR和ECMP傳輸時延大幅度增加。這是由于此時傳輸路徑上開始出現擁塞鏈路，而RRR和ECMP沒有考慮網絡鏈路狀態，因此，會導致傳輸時延的快速增長。與之對應的是，DraLCD和MLSR考慮了鏈路狀態，可以根據實時情況選擇最佳路徑，因此傳輸時延增長趨勢平穩。另外，與其他四種算法相比，MLSR算法考慮的因素更為全面，因此傳輸時延始終最小。

其次，通過在主機h1上安裝Iperf的客戶端，在主機h4上安裝Iperf的服務器端，來測量兩主機之間不同算法的丟包率，仿真結果如圖5所示。

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

從圖5可以看出：數據發送速率在20Mbps以內時，各個算法的丟包率差別不大，但MLSR算法的丟包率更小。當數據發送速率大于20Mbps后，MHR算法的丟包率急劇增加，RRR算法和隨機ECMP算法的丟包率也明顯增加，DraLCD算法的丟包率有所增加，但是MLSR算法的丟包率變化不明顯，仍然低于其他四種算法。主要原因在于：MHR算法選擇的路徑始終為s1-s4，其帶寬與發送速率匹配程度嚴重失衡，導致鏈路負荷過重，所以隨著發送速率的增加，丟包率越來越大。而RRR算法和ECMP算法所選路徑也存在負荷不均衡問題，所以其丟包率也較大。由于MLSR算法實時根據網絡的負載情況動態調整路徑，可以最大限度地從當前網絡中選擇最優鏈路進行數據傳輸，因此，丟包率最小。

從以上實驗結果可以看出：當網絡鏈路負載較低時，五種路由算法表現相當，傳輸時延和丟包率均較低；但是，隨著負載的增加，網絡中逐漸出現擁塞，此時由于MLSR算法能根據鏈路的時延和帶寬狀態動態調整路徑的權值，有利于更合理地選擇路徑，因此具有更好的性能。

4結語

利用SDN易于獲取全網鏈路狀態信息的優點，綜合考慮鏈路的平均時延和平均剩余帶寬，提出一種多鏈路狀態路由算法（MLSR），并通過Mininet和Floodlight進行仿真評測。仿真結果表明：MLSR算法可以改善網絡的傳輸時延，具有更低的丟包率。但是MLSR算法只是選擇了影響數據傳輸的諸多因素中最重要的兩個因素，在下一步研究中可考慮其他因素的影響，例如交換機中流表的處理能力等，設計更有效的綜合路由策略。

［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］蔡岳平，王昌平.軟件定義數據中心網絡混合路由機制［J］.通信學報，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］張朝昆，崔勇，唐翯祎，等.軟件定義網絡（SDN）研究進展［J］.軟件學報，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技術［J］.軟件學報，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負載均衡的研究［D］.吉林：吉林大學碩士學位論文，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］楊洋，楊家海，秦董洪.一種新的數據中心多路徑路由方案研究［J］.中國科技論文在線，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日

國家自然科學基金項目（編號：61371091）；大連海事大學“十三五”重點科研項目（編號：3132016318）資助。

雷田穎，男，碩士研究生，研究方向：SDN與數據中心網絡的路由策略。林子薇，女，碩士研究生，研究方向：SDN與數據中心網絡的路由策略。何榮希，男，博士，教授，研究方向：通信網絡及其相關技術。劉家懌，男，研究方向：機器學習/數據分析。