基于Ryu的SDN網絡動態路由算法實現*

傅妍芳，李敬偉，馬 靜，趙世峰，田鵬輝

(西安工業大學 計算機科學與工程學院，西安 710021)

傳統網絡中，不容易對各交換設備的集中管理和配置，需要分別對其進行手動配置；對虛擬網絡的管理應用不多，需要專門的虛擬網絡管理系統；傳統網絡設備控制與數據平面的耦合，很難做到全局的網絡拓撲的顯示來實現監控功能；不同的廠商提供的網絡設備都是閉源的，不同的設備需要不同的API來進行網絡應用開發，不利于網絡應用的創新.

SDN是對傳統網絡架構的重構[1]，從分布式網絡架構轉向集中式控制網絡架構，將傳統的各交換設備的控制層面[2]抽取出來，作為控制中樞來管理和控制各交換設備，與數據轉發層面分離[3]；其網絡配置也解決了傳統的分布式框架，采用集中式的管理方式，對SDN設備進行統一管理和靈活部署[4]，并且可以對全網的拓撲進行監控，實現全局鏈路的顯示，其控制層面可根據需要進行鏈路選擇，如采用動態路由的方法對鏈路進行路徑選擇[5].

基于此，為了底層網絡能更好的為上層業務和應用服務，使網絡資源做到靈活調度，文中擬應用SDN架構，把協議的實現從硬件層剝離出來，把硬件用統一的模型描述，模型之外的部分變成控制器和流表，通過控制器和流表來實現各種網絡協議.

1 SDN相關技術

作為SDN框架中的核心，SDN控制器獲得下層的全局網絡拓撲，做出控制報文的轉發決策，可以解決在傳統網絡中路由不可控的問題.當需要調整網絡行為時，不再需要修改網絡設備本身，而是調整SDN控制器內部的軟件.目前主流的SDN控制器采用的路由算法為Dijkstra算法，該算法只能計算出源節點和目的節點之間的最短路徑.

Ryu控制器就作為一種基于組件的軟件定義網絡框架，提供了定義好的API使開發者更易創建新的網絡管理和應用控制[6].Ryu支持不同的協議管理網絡設備，如：OpenFlow、Netconf、OF-config等，且支持OpenFlow1.0到OpenFlow1.5.

mininet是一些虛擬的終端節點、交換機、路由器連接而成的網絡仿真器，其基于Linux Container架構，采用輕量級的虛擬化技術，使得系統可以和真實網絡媲美[7].利用mininet創建支持自定義的網絡拓撲，縮短開發測試周期；支持OpenFlow、Open vSwitch等軟件定義的網絡組件[2，8]，在mininet上運行的代碼可以無縫移植到支持OpenFlow的硬件設備；支持系統級的還原測試、支持復雜拓撲、自定義拓撲等.文獻[9]對傳統網絡與SDN網絡架構做了闡述(如圖1所示)，SDN是把不同協議間的分布式系統集成到了網絡操作系統中，各路由算法成為了另一種形態——APP.

圖1 傳統網絡與新型SDN的架構變更

在Ryu控制器的架構中可以更加清晰的看到SDN的架構應用，整體結構如圖2所示.

圖2 Ryu控制器框架的層次結構

1.1 傳統路由技術

在OSI模型中，網絡數據傳輸主要在數據鏈路層和網絡層.數據鏈路層主要負責數據幀的傳輸，網絡層主要負責數據包在發送端和接收端的傳輸.路徑選擇、路由以及邏輯尋址也都是在網絡層中實現.選路問題存在于網絡的各個層之中，網絡層中的路由選擇和路由計算采用IP地址協議，其步驟如下：

① 當數據分組進入交換設備時，對分組的目的地址進行選路，確定下一跳的節點地址；

② 利用ARP確定下一跳節點物理地址；

③ 將數據分組封裝在物理幀中，利用底層物理網絡節點發送到下一跳節點.

當一個網絡設備把數據包發給路由器時，路由器對收到的數據包進行解析，提取出目的地址，接下來路由器根據ARP協議確定下一跳的物理設備，路由器再把數據包轉發出去，可以將數據包轉發到最終的設備中.IP網絡的路由是先選擇路徑，然后通過網絡傳輸，每個設備只知道下一跳的地址，這樣依次進行轉發就可以到達目的地址.

1.2 SDN路由技術

與傳統網絡相比較，SDN網絡中，SDN控制器集中擁有全局視圖的網絡拓撲[8].控制器通過鏈路層發現協議，獲得網絡設備的基本信息(包括網絡拓撲和網絡資源，網絡資源包括節點連接關系，帶寬、跳數、時延、誤碼率等信息)，形成網絡拓撲視圖和資源視圖.基于網絡拓撲，結合Dijkstra算法，并對其優化，找出網絡中源節點到目的節點的最短路由.

傳統網絡中的路由只能實現基本的路由功能，不考慮整個網絡中的流量分布情況，很容易造成局部鏈路的路由阻塞.而SDN控制器可以根據網絡拓撲與網絡資源進行路由的調度，選出最佳路徑而不一定是最短路徑.

2 路由算法設計

2.1 靜態路由

靜態路由的鏈路選擇不是根據算法得到的，是網絡管理員根據鏈路的實際需求，對各個網絡設備進行手動配置得出，在規模比較小的網絡中，可以滿足應用，當網絡規模較大，網絡拓撲較復雜，且網絡變化較頻繁時，對網絡的配置就顯得不夠靈活，非常低效.在SDN控制器中，可以顯示他所控制和管理的域內全局的網絡視圖，而且Ryu控制器作為集中的控制層面，管理員只需在控制器中對各節點進行統一流表下發，使各OpenFlow交換設備根據流表項的規則進行數據轉發，完成靜態路由的功能.SDN網絡中的交換機不再解析任何協議，只做流表匹配和轉發，其控制方式采用集中式，所有協議解析都需在控制器內完成，流表下發也是統一從控制器下發.

在Ryu控制器中，將對各OpenFlow交換設備的MAC地址和輸入輸出端口進行規則定制，按照OpenFlow協議對各字段進行定義和封裝，通過Ryu流表下發函數對各OpenFlow交換設備進行流表下發，從而完成鏈路的整個靜態路由.

2.2 基于跳數的動態路由算法

基于SDN架構的靜態路由可以集中的對各支持OpenFlow的交換設備進行表項下發，對于鏈路的狀態也能做到更好的監測.但是，基于SDN的靜態路由配置也存在一些缺陷，例如：需要預先對網絡的狀態進行獲取，同時，對各交換設備的各個參數都要記錄到控制器中，且以上過程都需要人工參與記錄和流表項的規則制定，特別是當網絡拓撲發生變化時，還需要對流表項進行更新，以適應新拓撲可以正常通信.

如果以上過程完全由程序來實現，如：對鏈路的自動發現，對網絡狀態的自動感知，對鏈路的自動選擇，對各交換設備進行自動的流表下發，那么可以用動態的方式來完成以上過程.重點是對網絡中進行動態的路徑選擇，利用Dijkstra算法[10]完成.結合Ryu控制器中的鏈路發現，對控制層面的可編程性，完成對鏈路的自動選擇和對OpenFlow交換設備流表的自動下發[5].

Dijkstra采用貪心算法的原理，主要解決源節點到目的節點之間的最短路徑問題，它的主要特點是每次迭代找到的點，除了已經找到的點之外離源點最近的點.Dijkstra算法思想如下：

一個有向圖可以用G=(V,E)表示，V表示圖中所有點的集合，E表示圖中所有邊的集合.V中點可以分成兩組，一組用S表示，另一組用U表示.S中所包含的點是已經存在于已求最短路徑中的點，開始時，S中只包含源點，之后每求出一條最短路徑，就把其上的點加入S中，直到圖中的所有點都包含在S中，算法結束.U中包含的點是尚在已求最短上出現的點，根據最短路徑的長度，可以把U中的點依次加入到S中.在此過程中，必須保持源點到S中點的距離不大于源點到U中點的距離，另外，每個點都對應一個路徑長度，S中點所對應的路徑長度為該點到源點的最短路徑長度，U中點所對應的距離，是該點到源點且路徑只包含S中的點的路徑長度.

在Ryu控制器中，通過鏈路發現協議來獲取整個網絡拓撲中的節點，包括各交換設備本身以及其對應的出入端口信息，將其存儲到控制器中的MAC地址轉發表中記錄下來；根據動態路由算法，計算出源與目的主機之間經過的網絡節點，并選擇出源與目的之間的最短路徑；將計算得到的路徑經過的節點信息安裝到各個節點的流表中，從而完成Ryu控制器中對動態路由的實現[11].

2.3 提高網絡資源利用率的動態路由

在SDN網絡中，基于跳數而實現的最短路徑選擇，在實際使用中遠遠不夠，沒有考慮到鏈路的實際資源情況，例如：各個鏈路的帶寬、時延、丟包率等業務屬性.

在Ryu控制器內部，利用網絡特性和SDN控制器可以全局信息獲取以及整體決策各交換節點的特點，開發感知網絡資源的功能特性，獲取到各個鏈路的實際帶寬、時延、丟包率等屬性，根據這些屬性，將其設置為混合的權重機制，根據用戶需求，進行權重優先切換，也可根據算法，將獲取到的屬性根據實際情況進行擬合，生成一個多權重融合的算法，一是為了使動態路由計算更加實際可用，二是為了提高網絡資源的利用率.

3 最短路徑轉發實現

Ryu控制器與SDN交換機進行信息交換為：Hello握手信息，建立網絡連接，保持鏈接狀態；同時，Controller會向Switches發送狀態請求，包括支持的OpenFlow版本，支持的Features等信息.

通過bserve-links指令自動下發LLDP，開啟拓撲發現功能，Ryu控制器內部接收到鏈路發現事件后，觸發控制器的事件處理模塊進行交換設備、主機以及鏈路連接的信息獲取.SDN控制器與SDN交換機的具體通信過程見表1.

表1 SDN控制器與SDN交換機信息交換

Tab.1 Information exchange between the SDN controller and the SDN switch

消 息類 型描 述HelloController→SwitchTCP握手,控制器請求交換機版本號HelloSwitch→Controller交換機回復它支持的版本Feature RequestController→Switch控制器詢問可用端口SetConfigController→Switch控制器讓交換機發送超時消息Feature ReplySwitch→Controller交換機回復端口速度、支持的表和行動

默認情況下，SDN控制器會對交換機下發table-miss流表，當交換設備的信息進入Controller時，及觸發Packet-in事件供Ryu控制器進行處理.結合Dijkstra算法進行路徑選擇，其步驟如下：

① Ryu控制器獲取整個網絡的拓撲；

② 解析到網絡拓撲中所有的交換機和端口信息，存儲到鄰接矩陣的字典中；

③ handler事件處理器處理接收到的Packet-in事件，進行MAC地址學習和端口映射存儲；

④ 根據存儲在mac地址表中信息進行鏈路計算，執行Dijkstra路由算法并選擇出最短路徑；

⑤ 對計算到的路徑解析出其下一跳的交換機和出入端口信息；

⑥ 對各交換設備進行流表下發，使整個拓撲的所有數據平面按照計算結果進行數據包的正常轉發.

在上述過程中，動態路由Dijkstra只是基于跳數計算出了最短路徑，并沒有考慮到實際的鏈路狀態以及鏈路屬性等信息.對此，增加了對鏈路的感知功能，通過感知Ryu控制器來獲得鏈路的帶寬、延遲、丟包率等鏈路屬性，根據獲得的鏈路屬性來為其分配權重，將各種權重進行擬合，在路由算法中將權重加入到最短路徑選擇的鄰接矩陣中，從而用戶可以根據實際情況來切換權重，進而實現滿足用戶需求，同時又能提高網絡利用率的網絡路徑選擇.拓展的實現過程為：

① 獲取拓撲信息之后進行鏈路感知；

② 獲取鏈路的帶寬、延遲、丟包率等屬性；

③ 對獲取的鏈路屬性進行權重賦值；

④ 與MAC地址表中的源、目的交換設備進行參數傳遞；

⑤ 將鏈路屬性參數作為Dijkstra的權重參數參與路徑選擇；

⑥ 根據最短路徑結果綁定所有輸入輸出端口；

⑦ 匹配路徑并為每個交換機下發流表.

4 實驗仿真

實驗采用All-in-one結構，將Ryu控制器、mininet安裝在同一臺虛擬主機里，其中Ryu負責對Openv Switch進行管理和控制，mininet負責對網絡的仿真，模擬出虛擬交換設備與虛擬主機.針對OpenFlow交換機加入動態路由功能，其網絡拓撲如圖3所示.

圖3 網絡拓撲測試圖

由圖3可知，從h1到h2可以經過兩條路徑，分別是：h1→s1→s2→s4→h2；h1→s1→s3→s4→h2.鏈路發現程序執行之后，學習設備的端口和經過的鏈路.執行程序之后，得到如圖4所示的詳細端口信息.

圖4 獲取到鏈路后的詳細信息

執行網絡鏈路感知程序，圖4中加入了h11、h22兩個虛擬主機，目的是為了在程序中對各鏈路完成對帶寬、延遲和丟包率等屬性的獲取.獲取到信息后，根據用戶需求對參數賦予權重，將其加入鏈路的動態路由算法，從而實現優化后的動態路由功能.

4.1 執行mininet網絡仿真環境

為了控制SDN交換機，OpenFlow交換機采用Open vSwitch，執行環境采用mininet.通過自定義網絡拓撲完成拓撲搭建，其中鏈路帶寬、延遲、丟包率由Linux TC內核流量控制工具來模擬.腳本如圖5所示.

圖5 mininet網絡拓撲仿真

由圖5可知，通過mininet拓撲自定義腳本生成四個虛擬交換機，四個虛擬主機.四個主機分別與四個虛擬交換機相連，同時在mininet腳本中引入流量控制工具，對各鏈路的參數進行指定：帶寬、丟包率以及延遲，以此來模擬實際網絡環境中的情況.

4.2 執行Ryu應用

基于OVS的mininet仿真環境與Ryu控制器連接之后，控制器會自動進行鏈路發現和MAC地址學習等功能，從而控制器中會有虛擬交換機的全局拓撲，自動對鏈路中各網絡節點進行獲取，計算出各節點的出入端口，執行動態路由選擇函數，計算出鄰接的交換機信息，和從源到目的基于跳數的所有路徑，而同時結合獲取到的網絡鏈路屬性，對權重較低的鏈路進行剪枝，得出優化后的最短路徑.SDN控制器對各交換機根據路由算法計算出的結果進行流表下發.

執行成功后，對h1到h4主機之間進行ping測試，然后對各交換機進行流表查看，結果如圖6所示.

圖6 各交換機的流表項查看結果

4.3 鏈路連通測試

通過OVS指令，對mininet仿真出的虛擬交換機進行流表查看，圖6中可以看到，數據從s1的1端口進入，2端口流出，從s2的1端口進入，2端口流出，從s4的1端口進入，3端口流出，此時的路徑為h1→s1→s2→s4→h2，而端口從交換機的流入流出情況為s1(1,2)→s2(1,2)→s4(1,3),驗證輸出結果如圖7所示.

圖7 路由學習后的鏈路驗證結果

從圖7可知，學習所有交換機MAC地址與端口后，需對源主機與目的主機進行ping測試，測試結果表明，Ryu控制器完成了所有交換機和端口信息以及鏈路信息的發現.根據Dijkstra算法計算出所經過的數據傳輸路徑，結合對鏈路屬性的獲取，在算法中增賦予鏈路權重，從而對不滿足需求鏈路進行剪枝，實現了動態路由的路徑計算，而ping測試也驗證了從源到目的主機之間的鏈路連通.

5 結 論

文中通過Ryu控制器、mininet網絡仿真工具對SDN網絡架構以及網絡動態路由進行研究，通過SDN控制器收集到整個網絡的拓撲和資源，形成拓撲視圖和資源視圖，實現了對OpenFlow交換機的管控功能.基于Ryu控制器分析和設計了靜態路由算法，通過控制器對各個交換設備進行統一靜態路由進行配置，分析了存在的缺陷；在SDN架構中引入基于跳數的動態路由方法，根據SDN全局獲取到的拓撲信息，將網絡節點以及交換設備的端口映射信息保存匯總，根據Dijkstra算法算出基于跳數的最短路徑；增加鏈路感知功能，獲取到網絡鏈路的帶寬、延遲、丟包率等屬性，將其加入動態路由算法，并通過mininet對網絡節點進行仿真.仿真結果表明，結合Ryu控制器內部應用來對Ryu控制器應用的開發可以實現動態路由選擇功能，并完成了自動的流表規則下發.SDN架構中應用層面對網絡協議等功能的設計方法具有可行性，并且SDN控制器能夠根據優化的路由算法實現對虛擬網絡設備進行集中的管理和自動化配置.

參考文獻：

[1] 張衛峰.深度解析SDN—— 利益、戰略、技術、實踐 [M].北京:電子工業出版社,2014.

ZHANG Weifeng.In-depth Analysis of SDN—Benefits,Strategy,Technology,Practice [M].Beijing:Electronic Industry Press,2014.(in Chinese)

[2] 左青云,陳鳴,趙廣松,等.基于OpenFlow的SDN技術研究[J].軟件學報,2013(5):1078.

ZUO Qingyun,CHEN Ming,ZHAO Guangsong.Research on SDN Technology Based on OpenFlow[J].Journal of Software,2013(5):1078.(in Chinese)

[3] 張順淼,鄒復民.軟件定義網絡研究綜述[J].計算機應用研究,2013,30(8):2246.

ZHANG Shunmiao,ZOU Fumin.A Review of Software Defined Network.Application Research of Computers[J].2013,30(8):2246.(in Chinese)

[4] 李朝輝.SDN路由算法設計與實現[D].北京：北京郵電大學,2016.

LI Chaohui.Design and Implement of SDN Routing Algorithm[D].Beijing:Beijing University of Post and Telecommunication,2016.(in Chinese)

[5] 李勇，劉學軍.基于OpenFlow的SDN網絡中路由機制研究[J].移動通信,2015(7):51.

LI Yong,LIU Xuejun.Research on Routing Mechanism in SDN Network Based on OpenFlow[J].Mobile Communication,2015(7):51.(in Chinese)

[6] RYU SDN Framework [EB/OL].[2017-10-05].http://osrg.github.io/ryu/.

[7] Mininet Team[EB/OL].[2018-01-01].http://Mininet.org/.

[8] A Linux Foundation Collaborative Project.Open vSwitch[EB/OL].[2018-01-01].http://www.openswitch.net /.

[9] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:Enabling Innovation in Campus Networks[J].Acm Sigcomm Computer Communication Review,2008,38(2):69.

[10] 王樹西,李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學,2014,41(6):217.

WANG Shuxi,LI Anyu.Multiple Adjacency Points and Multiple Shortest Paths in Dijkstra’s Algorithm[J].Computer Science,2014,41(6):217.

(in Chinese)

[11] YU Y S,KE C H.Genetic Algorithm Based Routing Method for Enhanced Video Delivery over Software Defined Networks[J].International Journal of Communication Systems,2018,31(1):e3391.