SDN架構(gòu)下的鏈路分離路徑算法的研究

池亞平 高 聰 陳 穎 范曉紅

1(北京電子科技學(xué)院通信工程系 北京 100070)2(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)3(中國(guó)科學(xué)院信息工程研究所網(wǎng)絡(luò)測(cè)評(píng)技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京 100093)

0 引 言

近些年，隨著互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，互聯(lián)網(wǎng)用戶數(shù)量呈現(xiàn)巨大的增長(zhǎng)。人們對(duì)互聯(lián)網(wǎng)的需求越來越多，對(duì)網(wǎng)絡(luò)的質(zhì)量要求也日益增高，所以人們要求網(wǎng)絡(luò)的傳輸能夠更加可靠。傳統(tǒng)網(wǎng)絡(luò)具有非常分散的控制機(jī)制，特定的路由協(xié)議和算法在每個(gè)獨(dú)立的節(jié)點(diǎn)上運(yùn)行。在現(xiàn)如今網(wǎng)絡(luò)設(shè)備多種多樣的現(xiàn)實(shí)網(wǎng)絡(luò)中，這種分布式網(wǎng)絡(luò)架構(gòu)，使得網(wǎng)絡(luò)管理和監(jiān)控成為一項(xiàng)艱巨的任務(wù)。SDN的出現(xiàn)給復(fù)雜的網(wǎng)絡(luò)管理者們帶來了曙光。SDN擺脫了硬件對(duì)于網(wǎng)絡(luò)的限制，使網(wǎng)絡(luò)可編程化，通過軟件可以對(duì)網(wǎng)絡(luò)進(jìn)行管理和修改。

SDN是一個(gè)具有三層架構(gòu)的新型網(wǎng)絡(luò)架構(gòu)(如圖1所示)，包括數(shù)據(jù)層、控制層、應(yīng)用層。其中控制層是SDN的一個(gè)核心層，在控制層實(shí)現(xiàn)路徑的計(jì)算。在SDN架構(gòu)中，控制層與數(shù)據(jù)層分離，對(duì)網(wǎng)絡(luò)的控制集中在可編程控制器中。數(shù)據(jù)層與控制層分離的靈活架構(gòu)，使QoS傳輸和流量工程可以集中式處理網(wǎng)絡(luò)的拓?fù)湫畔?，網(wǎng)絡(luò)可以高效地運(yùn)行。傳統(tǒng)網(wǎng)絡(luò)的體系結(jié)構(gòu)是過于靜態(tài)、不夠靈活，無法獲得網(wǎng)絡(luò)全局拓?fù)湫畔?。SDN中網(wǎng)絡(luò)設(shè)備的流量可以由軟件集中動(dòng)態(tài)控制，可以確保網(wǎng)絡(luò)資源的優(yōu)化分配，避免擁塞。SDN的一個(gè)重要的特點(diǎn)是可以獲取到網(wǎng)絡(luò)拓?fù)涞娜中畔ⅲ琒DN的出現(xiàn)使得流量工程有了更進(jìn)一步的發(fā)展。該網(wǎng)絡(luò)架構(gòu)通過使用新型網(wǎng)絡(luò)協(xié)議(如OpenFlow[1])降低傳統(tǒng)網(wǎng)絡(luò)設(shè)備獲取網(wǎng)絡(luò)資源信息的通信開銷，降低對(duì)網(wǎng)絡(luò)資源的占用。SDN另一個(gè)重要的特點(diǎn)是能夠靈活地控制網(wǎng)絡(luò)流量，使用不同的路由算法來改變網(wǎng)絡(luò)的傳輸路徑。路由算法僅運(yùn)行在控制器中，SDN通過對(duì)路由設(shè)備的集中控制，提供更加精確的路徑，獲得更小的延遲、更加高質(zhì)量的路徑。

圖1 SDN架構(gòu)圖

SDN網(wǎng)絡(luò)的出現(xiàn)，使現(xiàn)有網(wǎng)絡(luò)有了集中控制的思想，對(duì)傳統(tǒng)網(wǎng)絡(luò)中的路由算法有了較大的影響。由于SDN的創(chuàng)新特性的出現(xiàn)，不得不對(duì)傳統(tǒng)的路由算法進(jìn)行重新研究。本文對(duì)多路徑算法進(jìn)行了改進(jìn)及應(yīng)用，多路徑算法對(duì)流量工程也具有很大幫助。流量工程用于優(yōu)化網(wǎng)絡(luò)流量的控制和監(jiān)控，有助于滿足特定的服務(wù)質(zhì)量并提供高效的網(wǎng)絡(luò)資源利用率。傳統(tǒng)的流量工程增加網(wǎng)絡(luò)的通信開銷，并且復(fù)雜的算法對(duì)有限的計(jì)算資源來說是一個(gè)巨大的挑戰(zhàn)，SDN的出現(xiàn)有效應(yīng)對(duì)了流量工程的這一挑戰(zhàn)。

多路徑路由算法能夠計(jì)算出網(wǎng)絡(luò)中多條可行路徑，可以應(yīng)用到流量工程中，啟用多路徑，便于分流，從而利用現(xiàn)有利用率比較低的路徑，有利于網(wǎng)絡(luò)流量在不同鏈路上進(jìn)行均衡。當(dāng)前在多路徑算法中，對(duì)于鏈路分離路徑算法的應(yīng)用研究很少。鏈路分離路徑可以增加數(shù)據(jù)的可靠傳遞，為尋路失敗提供彈性，縮減網(wǎng)絡(luò)的擁堵，有助于在網(wǎng)絡(luò)中提供高速率的數(shù)據(jù)傳輸和負(fù)載均衡。對(duì)于在QoS需求較高的網(wǎng)絡(luò)中，SDN具有較高的優(yōu)勢(shì)。通過為不同的流量提供多個(gè)鏈路分離路徑，從而有效地優(yōu)化網(wǎng)絡(luò)資源的利用，即實(shí)現(xiàn)接納控制、流量分類和負(fù)載均衡等，還能夠增強(qiáng)路徑的可靠性。對(duì)于流量感知網(wǎng)絡(luò)，解決接入控制和多路徑的失敗等問題需要耗費(fèi)很多時(shí)間，這些工作的耗時(shí)不僅體現(xiàn)在網(wǎng)絡(luò)的核心設(shè)備或路由器的接入時(shí)間，更體現(xiàn)在路徑的計(jì)算上。

SDN通過使用OpenFlow協(xié)議能夠細(xì)粒度地對(duì)流量進(jìn)行調(diào)控，使得網(wǎng)絡(luò)可以更加精確地對(duì)流量進(jìn)行控制?，F(xiàn)有的許多算法僅僅是增強(qiáng)鏈路的約束條件，或者是在SDN中應(yīng)用十分復(fù)雜的算法來取得更優(yōu)的鏈路。本文將SDN的靈活特性、細(xì)粒度控制特性與鏈路分離路徑相結(jié)合，利用二者的特點(diǎn)，為網(wǎng)絡(luò)提供多條可靠路徑，從而提高網(wǎng)絡(luò)的魯棒性，并且可以使用多分離路徑進(jìn)行負(fù)載均衡。由于使用了分離路徑算法，更能提高網(wǎng)絡(luò)的利用率。

1 研究現(xiàn)狀

SDN使網(wǎng)絡(luò)軟件化、扁平化。在SDN中，關(guān)于路由算法的研究有很多。一方面，有些研究人員使用簡(jiǎn)單的路由算法，如最短路徑優(yōu)先算法和帶寬最寬的路徑算法來優(yōu)化SDN網(wǎng)絡(luò)中的路由問題。文獻(xiàn)[2]使用帶寬最寬的路徑來查找數(shù)據(jù)中心的交換機(jī)和服務(wù)器之間路徑，帶寬最寬的路徑搜索算法會(huì)對(duì)帶寬資源造成過度的浪費(fèi)，過度消耗網(wǎng)絡(luò)帶寬還能造成網(wǎng)絡(luò)擁堵。文獻(xiàn)[3]在Floodlight控制器中使用廣度優(yōu)先搜索算法代替了最短路徑優(yōu)先算法。在這些文獻(xiàn)中，研究人員沒有使用SDN的特性來對(duì)算法進(jìn)行優(yōu)化。另一方面，SDN中大部分的路由算法的研究主要集中在復(fù)雜的路由算法上，這些算法的主要目標(biāo)就是滿足服務(wù)需求的QoS約束，約束越多算法越復(fù)雜。文獻(xiàn)[4-5]使用復(fù)雜的算法來優(yōu)化多媒體和視頻流量通信，從而提高網(wǎng)絡(luò)服務(wù)的通信質(zhì)量。同樣的，文獻(xiàn)[6]使用多約束最短路徑來增強(qiáng)視頻流的服務(wù)。SDN架構(gòu)下的流量調(diào)度算法是當(dāng)下研究的熱點(diǎn)，文獻(xiàn)[7-8]在混合SDN架構(gòu)下對(duì)網(wǎng)絡(luò)進(jìn)行建模，研究使用貪婪策略對(duì)SDN交換機(jī)進(jìn)行增量部署，計(jì)算出混合SDN網(wǎng)絡(luò)中合理的SDN交換機(jī)配置數(shù)量比例。文獻(xiàn)[9]研究了在SDN網(wǎng)絡(luò)中，快速計(jì)算出帶寬受限的路徑。在傳統(tǒng)的算法中，最小跳數(shù)算法MHA(Minimum-hopalgorithm)是使用比較廣泛的算法，它可以在滿足帶寬需求的路徑中選擇鏈路跳數(shù)最少的一個(gè)路徑。該算法維護(hù)每條鏈路上的可用帶寬信息，只有那些有足夠資源且滿足用戶需求的路由才會(huì)被考慮進(jìn)路由中。MHA法非常簡(jiǎn)單，但是很快就會(huì)造成網(wǎng)絡(luò)的瓶頸鏈路，導(dǎo)致資源利用率低下。文獻(xiàn)[9]中提及的最短最寬路徑SWP(Shortest Widest Path)和最寬最短路徑WSP(Widest Shortest Path)算法都是MHA的增強(qiáng)的算法。其中WSP算法在最短可行路徑集合中，選擇具有最高可用帶寬的路徑即最寬路徑，在負(fù)載均衡和資源消耗兩個(gè)沖突的需求之間權(quán)衡。

上述算法最終都是考慮一條路徑作為最佳傳輸路徑，多路徑算法在流量工程領(lǐng)域有很多優(yōu)勢(shì)。等價(jià)路由ECMP[10](Equal Cost Multipath Routing)就是多路徑算法一個(gè)很好的應(yīng)用，可以同時(shí)使用多條路徑進(jìn)行傳輸，增加了網(wǎng)絡(luò)的傳輸帶寬。Yen算法和MPS算法是都是多路徑算法，屬于K最短路徑算法，可找出前K條最短路徑。其中Yen算法在流量工程中有應(yīng)用。以上的多路徑算法在是尋找到多條發(fā)生重疊的路徑，如果在公共鏈路上出現(xiàn)了故障，對(duì)兩點(diǎn)之間的連通性有很大影響。文獻(xiàn)[11]提出了最大K條不相交路徑算法來實(shí)現(xiàn)路由。該算法未找到最短的一對(duì)不相交路徑，并且沒有使用SDN能夠細(xì)粒度控制流量的特性來改進(jìn)算法。

在通信的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間尋找多條分離路徑，可以將多條路徑互相當(dāng)做主備路徑，在一條路徑失效時(shí)，將流量切換到其他路徑上，以提高網(wǎng)絡(luò)的可靠性，還有利于網(wǎng)絡(luò)流量工程、負(fù)載均衡和擁塞避免的發(fā)生。關(guān)于分離路徑算法，RF(Remove-Find)方法是在一對(duì)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立兩條鏈路分離路徑的一種簡(jiǎn)單方法。這種方法簡(jiǎn)單但是有以下缺點(diǎn)：1) 在網(wǎng)絡(luò)中刪除源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的鏈路，會(huì)導(dǎo)致剩余網(wǎng)絡(luò)拓?fù)鋱D不連通，從而導(dǎo)致求解不出更多的路徑。2) 即使求出第二條路徑，第二條路徑過長(zhǎng)，或者僅僅是問題的可行解而不是最優(yōu)解。Suurballe提出通過路徑增益方法，并使用最短路徑方法構(gòu)建以總長(zhǎng)度最小為目標(biāo)，尋找出兩條節(jié)點(diǎn)分離路徑。之后Suurballe和Tarjan對(duì)算法進(jìn)行了改進(jìn)。Bhandari通過在原始的Dijkstra算法基礎(chǔ)上，提出在有向圖中求取路徑的鏈路分離路徑算法。以上提到的多數(shù)算法都是對(duì)原有算法的條件進(jìn)行改進(jìn)和增強(qiáng)，沒有利用到SDN能夠細(xì)粒度控制流量的新特性。為了獲得更好的路由性能，文獻(xiàn)[12-13]已經(jīng)開始嘗試?yán)肧DN架構(gòu)的優(yōu)勢(shì)，但是沒有考慮到分離路徑算法的優(yōu)勢(shì)。

本文借鑒了Bhandari算法的優(yōu)勢(shì)，將其與SDN相結(jié)合，利用了SDN的靈活特性，為網(wǎng)絡(luò)傳輸提供多個(gè)路徑，增加數(shù)據(jù)的可靠傳遞，為尋路失敗提供彈性，縮減網(wǎng)絡(luò)的擁堵，有助于在新型網(wǎng)絡(luò)中提供高速率的數(shù)據(jù)傳輸和負(fù)載均衡。

2 OpenFlow

OpenFlow協(xié)議可以實(shí)現(xiàn)SDN，基于OpenFlow使得網(wǎng)絡(luò)可編程，從而進(jìn)一步推出了SDN的概念。OpenFlow支持基于流量的路由決策，OpenFlow交換機(jī)根據(jù)控制器發(fā)出的指令區(qū)分流量進(jìn)行處理，一個(gè)流可以被廣泛地定義為具有相似特征的一系列分組?？刂破骺梢愿鶕?jù)圖2中的9個(gè)二層網(wǎng)絡(luò)到四層網(wǎng)絡(luò)之間的分組報(bào)文頭字段以及該分組到達(dá)接口的標(biāo)識(shí)符來定義一個(gè)網(wǎng)絡(luò)流量。這種控制選項(xiàng)可以實(shí)現(xiàn)高精度控制的動(dòng)態(tài)多路徑路由，顯著增加網(wǎng)絡(luò)容量。

圖2 OpenFlow報(bào)頭字段

使用OpenFlow接口的統(tǒng)計(jì)特性來計(jì)算的最佳路徑，可以使用基于OpenFlow協(xié)議的OpenMT[14]和OpenNetMon[15]等高效的開源軟件提取路由算法所需要的信息。其中OpenMT是一種用于OpenFlow網(wǎng)絡(luò)的流量矩陣估計(jì)系統(tǒng)，OpenMT使用OpenFlow交換機(jī)中提供的內(nèi)置功能，既降低了開銷，又準(zhǔn)確地測(cè)量了流量矩陣。OpenMT使用從OpenFlow控制器中學(xué)到的路由來智能地獲取流量統(tǒng)計(jì)信息。OpenNetMon也是一種開源的軟件，用于監(jiān)控OpenFlow網(wǎng)絡(luò)中的每個(gè)流量指標(biāo)，特別是吞吐量、延遲和數(shù)據(jù)包丟失。在OpenFlow提供接口來實(shí)現(xiàn)細(xì)粒度的流量工程的情況下，OpenNetMon提供必要的監(jiān)視來確定是否實(shí)際滿足端到端QoS參數(shù)，并為TE方法提供輸入來計(jì)算適當(dāng)?shù)穆窂健?/p>

OpenFlow協(xié)議為數(shù)據(jù)層和控制層之間提供網(wǎng)絡(luò)連接，為控制層提供全局的網(wǎng)絡(luò)視圖。當(dāng)網(wǎng)絡(luò)連接發(fā)生任何變化時(shí)，OpenFlow交換機(jī)會(huì)向控制層發(fā)送一個(gè)端口狀態(tài)消息來更新這個(gè)變化。另外，OpenFlow交換機(jī)有各個(gè)端口、各個(gè)流和各個(gè)隊(duì)列的流量計(jì)數(shù)器。這些計(jì)數(shù)器使用兩種類型的消息來維護(hù)控制器數(shù)據(jù)庫(kù)的網(wǎng)絡(luò)狀態(tài)。流量越大，消息越頻繁。Read-State消息由控制器發(fā)送，用于手機(jī)交換機(jī)統(tǒng)計(jì)信息。消息包含每個(gè)交換機(jī)的流量持續(xù)時(shí)間和字節(jié)數(shù)，從而識(shí)別每個(gè)鏈路的網(wǎng)路吞吐量。

算法的實(shí)現(xiàn)需要從OpenFlow協(xié)議中提取出有效的QoS信息來進(jìn)行計(jì)算。此外，還可以根據(jù)OpenFlow報(bào)頭的不同識(shí)別流量的類型、源端口和目的端口等有效信息。

3 算法介紹

SDN控制層的一個(gè)主要功能是路徑的計(jì)算，對(duì)于求解分離路徑來說，就是找出從源點(diǎn)到目的節(jié)點(diǎn)之間一組鏈路利用率低的鏈路。在給定的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間計(jì)算出一對(duì)分離路徑，將第一可用路徑視為主路徑，第二可用路徑視為恢復(fù)路徑，其他可用路徑進(jìn)行負(fù)載均衡。在主要路徑故障發(fā)生時(shí)，將路徑上的流量迅速切換至備用路徑，這種方法可以有效地提高網(wǎng)絡(luò)的可靠性和QoS保障。多路徑算法能夠更好地提供網(wǎng)絡(luò)生存能力和恢復(fù)能力，非常有利于流量工程、負(fù)載均衡和擁塞避免等情況。

3.1 網(wǎng)絡(luò)模型及假設(shè)

有關(guān)算法的實(shí)現(xiàn)，從關(guān)鍵的假設(shè)開始介紹，然后建立模型解決分離路徑問題。假設(shè)網(wǎng)絡(luò)的初始狀態(tài)是具有非負(fù)性QoS鏈路權(quán)重的網(wǎng)絡(luò)，其中QoS權(quán)重可以使用加性的，也可以是凸性或凹性的。加性約束有時(shí)延、抖動(dòng)等；凸性或凹性的約束有如帶寬、策略標(biāo)志等。使用修改后的Dijkstra算法之后，網(wǎng)絡(luò)中的鏈路將被置為相反方向或者QoS將被賦予負(fù)值。如圖3所示，邊AC在執(zhí)行完一次算法之后將被置于反向，并將權(quán)QoS權(quán)重值設(shè)置為負(fù)值。

圖3 修改的Dijkstra算法演示拓?fù)?/p>

將網(wǎng)絡(luò)抽象為加權(quán)無向圖，記為G(V,E)。網(wǎng)絡(luò)中的路由設(shè)備和通信鏈路分別用圖3中的節(jié)點(diǎn)和邊表示。V表示節(jié)點(diǎn)的集合，E表示G(V,E)中邊的集合。(u，v)表示從節(jié)點(diǎn)u到節(jié)點(diǎn)v的一條邊。G中每條邊(u，v)都具有特定的帶寬。

用s和t分別代表通信的源和目的節(jié)點(diǎn)，P為從s到t的一條路徑，用E(P)={(u,v)|(u,v)∈P}代表路徑P上的邊的集合，給出如下定義：

定義1假設(shè)路徑P1和路徑P2是網(wǎng)絡(luò)G(V,E)中的兩條路徑，若E(P1)∩E(P2)=φ，則P1和P2為鏈路分離路徑。

從OpenFlow統(tǒng)計(jì)的信息中提取出網(wǎng)絡(luò)中各鏈路的QoS信息，QoS信息可以從上文中介紹的開源軟件中提取，該軟件使用上文中所述的細(xì)粒度OpenFlow統(tǒng)計(jì)量。在多路徑算法運(yùn)行之前，先對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行處理。首先對(duì)QoS信息做處理，由于QoS權(quán)重可以是加性的也可是凸性或凹性的，對(duì)于凸性和凹性信息(如帶寬和策略標(biāo)志)使用OpenFlow統(tǒng)計(jì)的流量類型和數(shù)據(jù)，根據(jù)不同種類的流量給出QoS值。如果是對(duì)帶寬需求較高的流量請(qǐng)求，我們可以將剩余帶寬值較低的鏈路進(jìn)行刪除，保留合理的鏈路。對(duì)于加性QoS參數(shù)，例如延時(shí)和抖動(dòng)，根據(jù)網(wǎng)絡(luò)的特征來尋找更加合理的路徑，而不是一味地尋求最短路徑，容易造成網(wǎng)絡(luò)擁堵，并產(chǎn)生資源的浪費(fèi)。本文給出鏈路QoS信息的參考值，假設(shè)buv是流量的最低需求的帶寬，duv表示鏈路延遲，puv表示丟包率，對(duì)低于有效帶寬buv的鏈路進(jìn)行刪除，用Cuv來表示在(u,v)邊上消耗的費(fèi)用，將QoSuv定義為：

QoSuv=aduv+βpuv?(u,v)∈E

3.2 改進(jìn)的Dijkstra

Dijkstra算法適用于QoS路由，并在實(shí)際中網(wǎng)絡(luò)中，具有可擴(kuò)展性的優(yōu)勢(shì)，它被互聯(lián)網(wǎng)路由的逐跳協(xié)議所使用。大型網(wǎng)絡(luò)和SDN控制網(wǎng)絡(luò)是可擴(kuò)展的，使用改進(jìn)的Dijkstra算法有助于減少源到目的路由的最壞計(jì)算時(shí)間。Dijkstra算法用一種貪婪的方法來計(jì)算源、目的地對(duì)之間或從源到任何其他目的地之間的最短路徑。

對(duì)于傳統(tǒng)的Dijkstra算法，不能直接應(yīng)用到權(quán)值為負(fù)的拓?fù)渲?。Bhandari改進(jìn)的算法之中，路徑中存在負(fù)的邊，必須保證已經(jīng)標(biāo)記的節(jié)點(diǎn)再次被評(píng)估，這就意味著任何已經(jīng)被評(píng)估的節(jié)點(diǎn)在下一次計(jì)算中也要被再次評(píng)估。這對(duì)存在負(fù)弧的網(wǎng)絡(luò)拓?fù)錁?gòu)造鏈路分離路徑特別有效。

當(dāng)拓?fù)浯嬖跈?quán)值為負(fù)的邊時(shí)候，原始Dijkstra算法會(huì)失效，如圖3所示。利用原始Dijkstra算法，求得的路徑為P1=ABZ，權(quán)重大小為13，此路徑并非最短路徑，利用改進(jìn)的Dijkstra算法之后，可以得到最短路徑為P2=ADECBZ，權(quán)重大小為12，P2權(quán)重小于P1，是權(quán)重最小的鏈路。

3.3 鏈路分離路徑算法

使用OpenFlow協(xié)議從網(wǎng)絡(luò)中獲取QoS信息作為算法的輸入。最后輸出需要的k條分離路徑。鏈路分離路徑算法的偽代碼如下：

Input:(Graph G(V, E), QoS and Request R(s,d,k))

Output: kMDP

1 Run(MDA_Path_Pi);

2 E(Pir) <-E(Pi)

教師也可以根據(jù)學(xué)生回答問題的情況進(jìn)行追問，追問的問題可以是學(xué)生以往的典型錯(cuò)誤，可以是問題的進(jìn)一步拓展，也可以是知識(shí)之間的聯(lián)系和運(yùn)用。在不斷的設(shè)問和追問中，師生和生生不斷產(chǎn)生思維碰撞。

3 K<-1,2,…,k;

4 Update Path;

5 while(negative_BMDA_Path_(Pi)=true) do

6 G<-G′;

7 Run(MDA_Path_Pi);

8 If (MDA_Path_Pi over) do

9 return kMDP;

10 else if(E(Pir)∩E(Pi)=?) do

11 E(Pir)<-E(Pi)

12 Update Path;

13 else

14 E(Pir)<-{E(Pi)-E(Pir)∩E(Pi)}

15 Update Path;

16 end if

17 then if(Path < k) do

18 go to step 5;

19 else

20 Return kMDP;

21 end if

22 end if

在上述偽代碼中，當(dāng)?shù)谝淮螌ふ衣窂綍r(shí)，在沒有負(fù)邊的情況下，算法第1行是按照最短路徑算法來尋路的。第5～6行改變了原始的拓?fù)鋱D，第7行在改變后的拓?fù)渲袑ふ倚碌淖疃搪窂健５?～15行是將計(jì)算出的最短路徑所在的邊重新組合成最短路徑。

3.4 算例分析

圖4是使其運(yùn)行改進(jìn)后的Dijkstra算法演示。由于第一次運(yùn)行，拓?fù)渲袥]有負(fù)邊緣的存在，嚴(yán)格按照Dijkstra算法來運(yùn)行，計(jì)算出路徑為P1=ABCZ。之后改變路徑的方向?yàn)榉聪?，將成本大小改變?yōu)樨?fù)值，此時(shí)已經(jīng)計(jì)算出的路徑的鏈路成本改為-QoS，再次運(yùn)行改進(jìn)的Dijkstra算法，得到路徑P2=ADCEZ。如果得到的路徑與已知路徑發(fā)生重疊，則刪除兩條鏈路的并集，剩余的鏈路組成分離路徑。在計(jì)算出P2之后再次修改拓?fù)洌瑢蓷l路徑的方向取反，鏈路成本改為負(fù)值，得到圖4中帶有負(fù)權(quán)值的網(wǎng)絡(luò)拓?fù)?。在新的拓?fù)渲惺褂酶倪M(jìn)的Dijkstra算法找到從A到Z的最短路徑P3=AFECBHZ，再刪除與之前求得的鏈路的并集，得到三條鏈路分離路徑。重復(fù)上述步驟直到路徑計(jì)算結(jié)束或已達(dá)到路徑數(shù)量請(qǐng)求。

圖4 相交路徑算法演示

算法的主要流程就是在修改后的拓?fù)渖锨蟪鲎疃搪窂?，將?jì)算出的最短路徑和此前的最短分離路徑作比較，刪除重疊的邊，將剩余的邊組合成最短的鏈路分離路徑。上述例子中路徑P3=AFECBHZ遍歷P2、P3的EC和BC兩條邊，刪除EC和BC之后我們會(huì)得到三條鏈路分離的路徑(AFEZ,ADCZ,ABHZ)，權(quán)重的總和為15，即三條鏈路權(quán)重之和。

如果FE權(quán)值變?yōu)?，在第二次轉(zhuǎn)變后的拓?fù)渲凶疃搪窂絇3=AFDBHZ，三條分離路徑即變成ABCZ、ADCEZ和AFDBHZ，他們的總長(zhǎng)度為3+4+10=17。

4 仿 真

分別使用擁有20個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)和40個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的拓?fù)?，?duì)于n個(gè)點(diǎn)之間我們建立n(n-1)條邊的完全拓?fù)?，并在拓?fù)渲星蠼獠煌瑪?shù)量的路徑個(gè)數(shù)，并統(tǒng)計(jì)算法的執(zhí)行時(shí)間。如圖5所示，算法在較短時(shí)間內(nèi)可以求得所需要的路徑數(shù)量。

圖5 求解路徑的平均計(jì)時(shí)間

仿真網(wǎng)絡(luò)采用具有14個(gè)節(jié)點(diǎn)21條鏈路的NSFNET骨干網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)仿真。如圖6所示，使用延遲作為實(shí)驗(yàn)仿真的QoS值，對(duì)每個(gè)滿足帶寬需求的鏈路上設(shè)置不同的延時(shí)。在圖中使用1節(jié)點(diǎn)為源節(jié)點(diǎn)，13節(jié)點(diǎn)為目的節(jié)點(diǎn)，使用SDN控制器獲取分離鏈路。設(shè)置各個(gè)鏈路帶寬1 Gbit/s，鏈路帶寬滿足網(wǎng)絡(luò)鏈路的傳輸質(zhì)量需求。當(dāng)鏈路數(shù)量為1時(shí)，算法就是最短路徑算法，所以求得的路徑數(shù)目k須大于1，才能體現(xiàn)算法的特點(diǎn)，所以我們?nèi)=2為例，實(shí)現(xiàn)仿真。

圖6 NSFNET網(wǎng)絡(luò)

使用Mininet[16]模擬骨干網(wǎng)絡(luò)，使用Pox控制器進(jìn)行控制。建立數(shù)據(jù)平面的方法有三種：1) Hop-by-Hop方式，即交換機(jī)之間的數(shù)據(jù)面直接進(jìn)行物理連接的方式。2) 覆蓋方式，即采用IP通道的等技術(shù)構(gòu)建用于數(shù)面的覆蓋網(wǎng)絡(luò)。3) 混合方式，即上述兩種方式的組合稱為混合方式。本文采用Hop-by-Hop方式組建數(shù)據(jù)平面，其優(yōu)點(diǎn)是OpenFlow交換機(jī)的數(shù)據(jù)平面直接互相連接，與其他覆蓋方式相比，具有能夠高速處理，判斷何處出現(xiàn)故障時(shí)的考慮因素較少等優(yōu)點(diǎn)。

利用網(wǎng)絡(luò)中的延遲作為仿真的參考QoS，求出合適路徑，計(jì)算出QoS最低的兩條分離路徑。在每條鏈路上取不同的延時(shí)參數(shù)，分別計(jì)算路徑作對(duì)比。其中：MHA算法得到的延時(shí)較高；使用Yen算法得到兩個(gè)鏈路的平均延時(shí)較高，求出的路徑條數(shù)較多；Dijkstra算法得到最優(yōu)路徑；Path1和Path2是使用本文的算法求出的兩條分離路徑。由此可見，本文的算法比Yen算法更加有優(yōu)勢(shì)，在延時(shí)相對(duì)接近的情況下，本文的算法能夠得到鏈路分離路徑，而Yen算法得到的是一組發(fā)生重疊的路徑。

如圖7所示，多路徑分離算法也可以取得良好的通信鏈路，但是路徑分離算法使用到了更多的鏈路，計(jì)算出兩條分離路徑，可以提供更好的負(fù)載均衡，大大提高了鏈路的魯棒性。

圖7 不同算法之間延遲的比較

5 結(jié) 語

鏈路分離路徑算法可以計(jì)算出多條沒有共用鏈路的路徑，將其與SDN的靈活性和細(xì)粒度控制特性相結(jié)合，可以為不同服務(wù)質(zhì)量的流量請(qǐng)求提供不同的路徑，也可以為同一類型的服務(wù)提供多條路徑以供選擇。根據(jù)網(wǎng)絡(luò)的擁擠程度調(diào)整路徑的使用，提供網(wǎng)絡(luò)傳輸質(zhì)量的同時(shí)，還能夠提高網(wǎng)絡(luò)利用率。鏈路分離路徑能夠提高網(wǎng)絡(luò)的可靠性，為尋路失敗提供韌性，縮減網(wǎng)絡(luò)的擁堵，在網(wǎng)絡(luò)中為高速率的數(shù)據(jù)傳輸提供很大的幫助，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡。