基于軟件定義網(wǎng)絡(luò)的多路徑路由選擇算法

魏波

（鄭州工業(yè)應(yīng)用技術(shù)學(xué)院信息工程學(xué)院,河南鄭州451100）

樹(shù)形結(jié)構(gòu)的以太網(wǎng)交換機(jī)構(gòu)成了傳統(tǒng)的分層結(jié)構(gòu)網(wǎng)絡(luò),是一種靜態(tài)體系結(jié)構(gòu).這種網(wǎng)絡(luò)雖然在一定程度上可以滿足數(shù)據(jù)交換以及信息傳遞的需求,但是在面對(duì)日益增大的網(wǎng)絡(luò)規(guī)模和人們對(duì)高效便捷生活的需求時(shí),其網(wǎng)絡(luò)架構(gòu)的可擴(kuò)展性不足、網(wǎng)絡(luò)的動(dòng)態(tài)計(jì)算性能弱以及可管理性差等缺點(diǎn)便暴露出來(lái),增加了網(wǎng)絡(luò)優(yōu)化的難度及網(wǎng)絡(luò)管理人員的工作量[1].2006 年斯坦福大學(xué)的研究團(tuán)隊(duì)提出了軟件定義網(wǎng)絡(luò)（SDN）的概念,SDN 是一種新型的網(wǎng)絡(luò)體系結(jié)構(gòu),為了實(shí)現(xiàn)網(wǎng)絡(luò)控制器邏輯層面的集中,采用轉(zhuǎn)發(fā)層面分離的路由決策,通過(guò)解耦控制層與數(shù)據(jù)傳輸層,實(shí)現(xiàn)控制器決定路由選擇,進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)控制的集中化,從而得到簡(jiǎn)單方便的網(wǎng)絡(luò)管理,在減少企業(yè)運(yùn)營(yíng)成本的同時(shí),使得路由技術(shù)更加靈活精確[2].本文在傳統(tǒng)路由選擇算法的基礎(chǔ)上,提出基于軟件定義網(wǎng)絡(luò)的多路徑路由選擇算法,通過(guò)定義權(quán)重變量,對(duì)控制器進(jìn)行多方面均衡考慮,最終實(shí)現(xiàn)多路徑路由選擇.

1 SDN 簡(jiǎn)介及分析

1.1 SDN 概念及架構(gòu)

傳統(tǒng)的網(wǎng)絡(luò)是一種靜態(tài)、封閉的體系結(jié)構(gòu),系統(tǒng)的更新發(fā)展嚴(yán)重依賴于廠商硬件設(shè)備的更新,導(dǎo)致了維護(hù)費(fèi)用高、網(wǎng)絡(luò)刷新速度慢等問(wèn)題[3].SDN 是一種新型網(wǎng)絡(luò),以O(shè)penFlow 為基礎(chǔ),具有靈活的網(wǎng)絡(luò)可編程性,能夠?qū)崿F(xiàn)應(yīng)用與創(chuàng)新網(wǎng)絡(luò)協(xié)議之間的融合,具體講只要滿足可編程化、集中式軟件管理以及分開(kāi)管理的控制轉(zhuǎn)發(fā)層就屬于軟件定義網(wǎng)絡(luò)[4].而在廣義上也在不斷對(duì)SDN 的定義進(jìn)行擴(kuò)充,涉及到軟件驅(qū)動(dòng)、軟件定義安全等深層次的概念[5].

SDN 架構(gòu)作為一種新型的網(wǎng)絡(luò)架構(gòu),設(shè)計(jì)理念主要分為3 層：基礎(chǔ)設(shè)施層、控制層和應(yīng)用層.簡(jiǎn)化的網(wǎng)絡(luò)設(shè)備構(gòu)成了基礎(chǔ)設(shè)施層即數(shù)據(jù)平面；SDN 控制軟件構(gòu)成了控制層可以自動(dòng)對(duì)網(wǎng)絡(luò)狀態(tài)進(jìn)行反應(yīng),保證上層控制邏輯的準(zhǔn)確性；應(yīng)用層則由應(yīng)用APP 構(gòu)成[6].SDN 架構(gòu)體系通過(guò)將數(shù)據(jù)轉(zhuǎn)發(fā)層和控制層分離,改變了以往控制層和數(shù)據(jù)層集中的特點(diǎn),實(shí)現(xiàn)了網(wǎng)絡(luò)編程的集中控制,進(jìn)而使得網(wǎng)絡(luò)配置變得更加簡(jiǎn)單和精確[7].SDN 體系架構(gòu)如圖1 所示.

圖1 SDN 架構(gòu)Fig.1 SDN network architecture

1.2 SDN 關(guān)鍵技術(shù)

SDN 關(guān)鍵技術(shù)主要涉及OpenFlow 協(xié)議、工作機(jī)制以及控制層關(guān)鍵技術(shù)[8].SDN 是一種新型的網(wǎng)絡(luò)架構(gòu),本身不具有技術(shù)實(shí)現(xiàn)功能.OpenFlow 是網(wǎng)絡(luò)標(biāo)準(zhǔn)協(xié)議,是一種技術(shù),由ONF 標(biāo)準(zhǔn)化組織進(jìn)行維護(hù)和宣傳,主要負(fù)責(zé)實(shí)現(xiàn)控制器和交換機(jī)之間的數(shù)據(jù)交流以及交換機(jī)操作,運(yùn)行在傳輸控制協(xié)議或安全傳輸協(xié)議連接之上,通過(guò)定義控制器對(duì)交換機(jī)的管理方式以及消息格式和類型來(lái)實(shí)現(xiàn)交換機(jī)轉(zhuǎn)發(fā)層的功能.SDN 的工作機(jī)制主要有流量統(tǒng)計(jì)機(jī)制、數(shù)據(jù)流處理機(jī)制以及網(wǎng)絡(luò)拓?fù)鋵W(xué)習(xí)機(jī)制,通過(guò)不同的機(jī)制實(shí)現(xiàn)網(wǎng)絡(luò)資源的合理配置,進(jìn)而為網(wǎng)絡(luò)帶寬優(yōu)化提供數(shù)據(jù)支撐,實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)質(zhì)量的提升.SDN 的控制層技術(shù)主要由兩部分組成：（1）SDN 控制器及北向接口技術(shù).控制器作為軟件定義網(wǎng)絡(luò)的計(jì)算單位,提供對(duì)路由進(jìn)行計(jì)算以及對(duì)網(wǎng)絡(luò)交換設(shè)備進(jìn)行管理、網(wǎng)絡(luò)狀態(tài)監(jiān)測(cè)來(lái)實(shí)現(xiàn)其功能；南向接口技術(shù)實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)設(shè)備的標(biāo)準(zhǔn)化對(duì)接,北向接口技術(shù)在提供標(biāo)準(zhǔn)化管理接口的同時(shí)提供了可擴(kuò)展服務(wù)接口,對(duì)資源進(jìn)行統(tǒng)一調(diào)度進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)系統(tǒng)的靈活性、開(kāi)放性和便利性.（2）網(wǎng)絡(luò)虛擬化及多控制器架構(gòu).網(wǎng)絡(luò)虛擬化作為云計(jì)算和數(shù)據(jù)中心技術(shù)焦點(diǎn),滿足了流量隔離、多租戶以及網(wǎng)絡(luò)自由控制進(jìn)而實(shí)現(xiàn)多用戶數(shù)據(jù)共享等需求；多控制器架構(gòu)可以減少控制器與交換機(jī)之間的通信延時(shí),減輕單個(gè)控制器的負(fù)載,進(jìn)而提高網(wǎng)絡(luò)服務(wù)質(zhì)量[9].

1.3 軟件定義網(wǎng)絡(luò)路由管理技術(shù)

由于傳統(tǒng)的網(wǎng)絡(luò)是一種靜態(tài)、封閉的體系結(jié)構(gòu), 因此路由的選擇只考慮了數(shù)據(jù)包的交換和網(wǎng)絡(luò)拓?fù)?但是這種方法收斂速度慢、程序復(fù)雜,不能靈活適應(yīng)數(shù)據(jù)的變化[10].SDN 路由管理技術(shù),根據(jù)流量實(shí)時(shí)性和安全性需求提出一種多路徑路由優(yōu)化模型,進(jìn)而減少網(wǎng)絡(luò)擁塞實(shí)現(xiàn)多路徑優(yōu)化機(jī)制,路由選擇方案主要有基于SDN 的多徑路由選擇、基于SDN 的通用路由選擇以及基于SDN 的分段路由選擇[11].

2 路由選擇策略

路由規(guī)則管理主要有數(shù)據(jù)層面的路由規(guī)則放置以及更新和控制層面的數(shù)據(jù)傳遞.SDN 路由選擇策略主要是利用中間節(jié)點(diǎn)以及節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈路, 在網(wǎng)絡(luò)體系結(jié)構(gòu)中選擇一條最優(yōu)的目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間的路徑,進(jìn)而提高數(shù)據(jù)傳輸效率和負(fù)載均衡[12].常用的基于SDN 的路由選擇策略主要有基于負(fù)載均衡、基于交換等級(jí)、基于權(quán)重的路由選擇算法.SDN 路由選擇算法分類如圖2 所示.

圖2 SDN 路由選擇算法分類Fig.2 Classification of SDN routing algorithms

2.1 基于SDN 的路由選擇

基于Qos 指標(biāo)的路由選擇算法,通過(guò)感知Qos 指標(biāo)為不同優(yōu)先級(jí)用戶和應(yīng)用進(jìn)行分流和路徑選擇,對(duì)最大化鏈路的剩余寬帶進(jìn)行建模得到目標(biāo)函數(shù)進(jìn)而實(shí)現(xiàn)最優(yōu)路徑選擇,Qos 指標(biāo)主要包括網(wǎng)絡(luò)吞吐量、誤碼率和傳輸時(shí)延等.基于負(fù)載均衡的路由選擇算法則是通過(guò)目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間路徑,找到空閑鏈路然后將網(wǎng)絡(luò)數(shù)據(jù)分配到上面,進(jìn)而實(shí)現(xiàn)鏈路的優(yōu)化,提高網(wǎng)絡(luò)利用效率,實(shí)現(xiàn)負(fù)載均衡.基于權(quán)重的路由選擇算法將路由和調(diào)度結(jié)合起來(lái),以時(shí)延和鏈路帶寬作為選擇權(quán)重參數(shù),建立模型將路由選擇轉(zhuǎn)化為求解最優(yōu)化問(wèn)題,降低系統(tǒng)復(fù)雜的同時(shí)減少流量延遲.

2.2 路徑選擇機(jī)制

網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)的優(yōu)化受多方面因素制約,為了使得節(jié)點(diǎn)配合網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)傳輸,保障數(shù)據(jù)交換以及通信的實(shí)時(shí)性和有效性,進(jìn)而滿足不同服務(wù)對(duì)系統(tǒng)的需求,需要對(duì)路徑選擇機(jī)制參數(shù)、性能和安全進(jìn)行綜合考慮,從而保證路徑選擇的最優(yōu)化,進(jìn)而實(shí)現(xiàn)數(shù)據(jù)交換時(shí)鏈路能夠滿足需求.路徑選擇機(jī)制主要由3個(gè)方面構(gòu)成：

（1）網(wǎng)絡(luò)性能參數(shù).主要包括吞吐量和丟包率,吞吐量的數(shù)學(xué)定義為單位時(shí)間內(nèi)在網(wǎng)絡(luò)鏈路（i,j）上通過(guò)的數(shù)據(jù)量Tij即為此鏈路的吞吐量,單位時(shí)間為秒.丟包率則為數(shù)據(jù)傳輸過(guò)程中由于內(nèi)在或外在因素的影響造成的數(shù)據(jù)損失,丟包率的范圍為[0,1].

（2）網(wǎng)絡(luò)安全參數(shù).為了保證數(shù)據(jù)傳輸?shù)陌踩?需要考慮網(wǎng)絡(luò)體系架構(gòu)的可靠性,而可靠性主要通過(guò)Switch 轉(zhuǎn)換次數(shù)、路徑通過(guò)次數(shù)來(lái)決定.

（3）路徑的評(píng)價(jià)與選擇.在對(duì)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)進(jìn)行路徑選擇時(shí),需要考慮系統(tǒng)的多個(gè)約束條件并對(duì)鏈路進(jìn)行評(píng)價(jià),因此需要建立多路徑路由問(wèn)題優(yōu)化模型,進(jìn)而對(duì)優(yōu)化問(wèn)題進(jìn)行求解,得到路徑選擇機(jī)制.

3 基于SDN 的多路徑路由選擇算法

3.1 基于多路徑路由選擇模型

基于SDN 的多路徑路由選擇,應(yīng)通過(guò)對(duì)節(jié)點(diǎn)流量進(jìn)行描述,同時(shí)需要考慮鏈路容量對(duì)網(wǎng)絡(luò)吞吐量的限制以及節(jié)點(diǎn)容量有限,進(jìn)而選擇最優(yōu)路徑.節(jié)點(diǎn)流量的數(shù)學(xué)定義為：源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)路徑上任一節(jié)點(diǎn)（s,d）,流出該節(jié)點(diǎn)和流入該節(jié)點(diǎn)的數(shù)據(jù)量相等,即

式（1）中：s 為源節(jié)點(diǎn),d 為路徑節(jié)點(diǎn),u、v 為節(jié)點(diǎn)集合,E 為節(jié)點(diǎn)間的連接,D 為源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的所需流量的集.則代表經(jīng)過(guò)鏈路（u、v）從源節(jié)點(diǎn)s 達(dá)到目的節(jié)點(diǎn)d 的流量.鏈路容量是多路徑選擇的另一個(gè)重要因素,在鏈路（u、v）上鏈路容量能夠承受通過(guò)的最大值數(shù)學(xué)公式表示為

式（2）中：Cuv為鏈路容量能夠承受的最大值.

3.2 基于SDN 的多路徑路由選擇算法

在已知網(wǎng)絡(luò)架構(gòu)模型上建立基于SDN 的多路徑路由選擇算法,通過(guò)對(duì)傳統(tǒng)路由優(yōu)化算法進(jìn)行梳理和優(yōu)化,進(jìn)而實(shí)現(xiàn)多路徑路由選擇,算法流程如圖3 所示.具體算法步驟為：

（1）對(duì)整個(gè)網(wǎng)絡(luò)架構(gòu),計(jì)算源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)路徑上任一節(jié)點(diǎn)（s,d）可能產(chǎn)生的路徑,以及每一條路徑的流量,同時(shí)需要考慮流出該節(jié)點(diǎn)和流入該節(jié)點(diǎn)的數(shù)據(jù)量相等即鏈路容量對(duì)網(wǎng)絡(luò)的限制,保存所有數(shù)據(jù),路徑數(shù)量和路徑上的流量在約束條件下取最大值；

（2）逐個(gè)的對(duì)每條路徑上的所有節(jié)點(diǎn)進(jìn)行驗(yàn)證,以檢驗(yàn)是否在流表容量范圍內(nèi),只有當(dāng)一條鏈路上的所有節(jié)點(diǎn)都滿足條件時(shí)（目標(biāo)節(jié)點(diǎn)和源節(jié)點(diǎn)不在驗(yàn)證范圍）,才說(shuō)明此鏈路具有路由選擇性；

（3）通過(guò)步驟（2）選擇到滿足所有限制條件合適的路徑,并對(duì)不符合條件的路徑進(jìn)行重新規(guī)劃計(jì)算看是否可以規(guī)劃到其他路徑,如果經(jīng)過(guò)規(guī)劃仍不能滿足系統(tǒng)的所有條件,則說(shuō)明該路徑是不可行的,最終得到路由選擇的多條路徑目標(biāo)值.

圖3 基于SDN 多路徑路由選擇算法流程Fig.3 Multi-path routing algorithm flow based on SDN

3.3 仿真實(shí)驗(yàn)

為了測(cè)試算法的有效性需要通過(guò)模擬環(huán)境來(lái)實(shí)現(xiàn),實(shí)驗(yàn)采用的硬件環(huán)境為：主計(jì)算機(jī)16 G 內(nèi)存,CPU 3.2 G 內(nèi)存.利用Mininet 網(wǎng)絡(luò)仿真器為仿真平臺(tái)創(chuàng)建虛擬拓?fù)渚W(wǎng)絡(luò)模型,Mininet 可以方便地創(chuàng)建一個(gè)支持SDN 的網(wǎng)絡(luò),同時(shí)設(shè)置實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：20 個(gè)源節(jié)點(diǎn),2 000 個(gè)節(jié)點(diǎn),鏈路容量根據(jù)實(shí)驗(yàn)環(huán)境進(jìn)行設(shè)置,實(shí)驗(yàn)參數(shù)見(jiàn)表1.

表1 實(shí)驗(yàn)參數(shù)配置Tab.1 Experimental parameter configuration

為了驗(yàn)證本文算法的有效性, 將基于SDN 的多路徑路由選擇算法和最優(yōu)解Optimal 算法以及SPR算法在不同緩存容量下運(yùn)行速度進(jìn)行比較,具體見(jiàn)表2.

表2 不同緩存容量（S）下算法的運(yùn)行速度Tab.2 Algorithm speed under different cache sizes

由表2 可知,在不同緩存容量下,基于SDN 的多路徑路由選擇算法的運(yùn)行速度明顯優(yōu)于其他算法,運(yùn)行時(shí)間雖然包含了仿真器本身的運(yùn)行開(kāi)銷(xiāo),但算法仍具有優(yōu)勢(shì),同時(shí)解決了多路徑路由選擇策略以及網(wǎng)絡(luò)鏈路的擁堵,節(jié)省了運(yùn)行時(shí)間,從而能夠保證整體網(wǎng)絡(luò)架構(gòu)的總體時(shí)延在可接受范圍內(nèi).

4 小結(jié)

本文針對(duì)SDN 網(wǎng)絡(luò)架構(gòu)分別從定義、關(guān)鍵技術(shù)以及路徑選擇機(jī)制進(jìn)行了分析,同時(shí)介紹了SDN 路由選擇算法分類.由于控制器可以對(duì)全局信息進(jìn)行分析,進(jìn)而能夠?yàn)槎嗦窂铰酚蛇x擇作出判斷,因此對(duì)SDN 中關(guān)鍵技術(shù)控制器進(jìn)行了著重介紹.在建立多路徑路由選擇模型的基礎(chǔ)上提出了基于SDN 的多路徑路由選擇算法,并通過(guò)實(shí)驗(yàn)仿真驗(yàn)證了算法的運(yùn)行速度和有效性,具有一定的應(yīng)用價(jià)值.如何對(duì)網(wǎng)絡(luò)中的延遲情況進(jìn)行優(yōu)化,并且在減少丟包率的同時(shí)提高網(wǎng)絡(luò)運(yùn)行效率及準(zhǔn)確性是下一步研究的重點(diǎn).