耿海軍,張 偉,尹 霞

(1.山西大學(xué) 軟件學(xué)院,太原 030006; 2.中國勞動(dòng)關(guān)系學(xué)院 計(jì)算機(jī)應(yīng)用教研室,北京 100048;3.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,北京 100084)

0 概述

近年來,互聯(lián)網(wǎng)得到了迅速的發(fā)展和廣泛的部署。然而,大量的新型應(yīng)用軟件和應(yīng)用場景層出不窮,這對(duì)互聯(lián)網(wǎng)提出了更加嚴(yán)格的要求和更高的挑戰(zhàn)。為了適應(yīng)軟件應(yīng)用發(fā)展的需求,斯坦福大學(xué)的研究人員提出了一種網(wǎng)絡(luò)體系結(jié)構(gòu),即軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)。該網(wǎng)絡(luò)體系架構(gòu)將控制平面和轉(zhuǎn)發(fā)平面的功能進(jìn)行了分離[1],控制平面主要關(guān)注如何根據(jù)優(yōu)化目標(biāo)制定最優(yōu)的路由決策,而轉(zhuǎn)發(fā)平面主要負(fù)責(zé)快速轉(zhuǎn)發(fā)數(shù)據(jù)包[2]。由于研究人員對(duì)SDN架構(gòu)的性能、健壯性等方面進(jìn)行了優(yōu)化,因此使得越來越多的互聯(lián)網(wǎng)服務(wù)提供商開始在他們的骨干網(wǎng)中部署SDN技術(shù)[3-6]。然而,由于經(jīng)濟(jì)和技術(shù)等方面的原因,短期內(nèi)不可能將目前骨干網(wǎng)中的所有傳統(tǒng)網(wǎng)絡(luò)設(shè)備替換為SDN節(jié)點(diǎn),因此骨干網(wǎng)將會(huì)長期處在傳統(tǒng)網(wǎng)絡(luò)設(shè)備和SDN節(jié)點(diǎn)共存的狀態(tài),稱該網(wǎng)絡(luò)為混合SDN網(wǎng)絡(luò)[7-8]?；旌蟂DN網(wǎng)絡(luò)主要由SDN控制器、SDN節(jié)點(diǎn)和傳統(tǒng)網(wǎng)絡(luò)設(shè)備構(gòu)成,SDN節(jié)點(diǎn)既可以運(yùn)行傳統(tǒng)的路由協(xié)議,也可以和SDN控制器交互信息,但是傳統(tǒng)網(wǎng)絡(luò)設(shè)備只能運(yùn)行傳統(tǒng)的路由協(xié)議[9]。

隨著互聯(lián)網(wǎng)的發(fā)展,其支持的應(yīng)用范圍呈現(xiàn)出了顯著的變化。最初,互聯(lián)網(wǎng)主要支持一些非實(shí)時(shí)應(yīng)用,如電子郵件、傳輸文件等。而如今大量的實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)[10-11]在互聯(lián)網(wǎng)上廣泛傳播,如IP語音(Voice over Internet Protocol,VoIP)、股票在線交易、遠(yuǎn)程手術(shù)、視頻監(jiān)控和即時(shí)通信等,這些新型應(yīng)用對(duì)路由可用性[12]提出了更高的要求。由此可見,路由可用性將直接影響用戶的財(cái)產(chǎn)安全甚至生命安全。

目前,提高域內(nèi)路由可用性的算法可以分為兩類,即被動(dòng)恢復(fù)算法和路由保護(hù)算法[13]。其中被動(dòng)恢復(fù)算法主要研究當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí)如何加快路由收斂速度,盡量縮短網(wǎng)絡(luò)中斷時(shí)間,但是當(dāng)網(wǎng)絡(luò)中的鏈路頻繁斷開時(shí),該算法可能導(dǎo)致路由不穩(wěn)定。路由保護(hù)算法則是根據(jù)相關(guān)規(guī)則事先計(jì)算備份路由,當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí),利用事先計(jì)算的備份路由轉(zhuǎn)發(fā)數(shù)據(jù)包,從而最大化減少報(bào)文丟失,縮短網(wǎng)絡(luò)服務(wù)中斷時(shí)間。相比較而言,路由保護(hù)算法更受學(xué)術(shù)界青睞[14]。

比較典型的路由保護(hù)方案主要包括等價(jià)多路徑路由[15]、多配置路由[16]、Failure Carrying Packet[17]、LFA[18]和Not-Via[19]等。文獻(xiàn)[20]提出一種基于SDN的路由保護(hù)方案,其利用節(jié)點(diǎn)間的偏序關(guān)系為每個(gè)節(jié)點(diǎn)計(jì)算多個(gè)到達(dá)目的節(jié)點(diǎn)的下一跳,從而達(dá)到路由保護(hù)的目的。文獻(xiàn)[21]提出一種基于段路由的單節(jié)點(diǎn)故障路由保護(hù)算法,該算法為網(wǎng)絡(luò)中所有的節(jié)點(diǎn)對(duì)部署中轉(zhuǎn)節(jié)點(diǎn),從而提高路由可用性。

已有的路由保護(hù)算法多數(shù)針對(duì)單一網(wǎng)絡(luò)體系結(jié)構(gòu),上述方案都可以直接應(yīng)用在純SDN網(wǎng)絡(luò)體系結(jié)構(gòu)中,但是無法直接應(yīng)用于混合SDN網(wǎng)絡(luò)。為此,本文提出一種基于混合SDN的路由保護(hù)算法。通過在網(wǎng)絡(luò)中部署SDN節(jié)點(diǎn),為網(wǎng)絡(luò)中所有的鏈路計(jì)算一條保護(hù)路徑,從而使算法可以應(yīng)對(duì)網(wǎng)絡(luò)中可能出現(xiàn)的單鏈路故障情形。

1 問題描述

目前互聯(lián)網(wǎng)部署的域內(nèi)鏈路狀態(tài)路由協(xié)議為網(wǎng)絡(luò)中所有的源-目的對(duì)計(jì)算一條最短路徑。當(dāng)有報(bào)文在網(wǎng)絡(luò)中傳輸時(shí),路由器根據(jù)報(bào)文頭部字段中的目的地址將該報(bào)文正確地轉(zhuǎn)發(fā)到目的地址。當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí),受該故障影響的報(bào)文將會(huì)被丟棄,從而影響網(wǎng)絡(luò)性能,降低用戶體驗(yàn)滿意度,影響了互聯(lián)網(wǎng)服務(wù)提供商的聲譽(yù)。學(xué)術(shù)界和工業(yè)界普遍采用路由保護(hù)方案來解決由于故障造成的網(wǎng)絡(luò)性能下降問題。然而已有的路由保護(hù)方案都是基于單一網(wǎng)絡(luò)體系結(jié)構(gòu)展開研究,無法直接應(yīng)用在混合SDN網(wǎng)絡(luò)中。因此,可以將本文解決的問題具體表達(dá)為:給定網(wǎng)絡(luò)G=(V,E),其中,V為該拓?fù)渲泄?jié)點(diǎn)的集合,E為該拓?fù)渲羞叺募?。如何選擇一組節(jié)點(diǎn)M?V部署SDN技術(shù),從而使得該路由保護(hù)算法可以應(yīng)對(duì)網(wǎng)絡(luò)中所有可能出現(xiàn)的單鏈路故障情形。

上述問題可以描述為一個(gè)0-1整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)模型,即:

(1)

Subject to:

y(i,j,k)∈{0,1},i,j,k∈V

(2)

y(i,j,k)=0,i?SDN(j,k)

(3)

y(i,j,k)=1,i∈SDN(j,k)

(4)

(5)

x(i)∈{0,1},i∈V

(6)

(7)

(8)

f(i,j)∈{0,1},i,j∈V

(9)

f(i,j)=0, (i,j)?E

(10)

f(i,j)=1, (i,j)∈E

(11)

z((i,j),i,d)∈{0,1},i,j,d∈V

(12)

z((i,j),i,d)=0, (i,j)?sp(i,d)

(13)

z((i,j),i,d)=1, (i,j)∈sp(i,d)

(14)

(15)

y(i,j,k)≤x(i)

(16)

下文將闡述上述的0-1整數(shù)規(guī)劃模型。式(1)是本文的優(yōu)化目標(biāo),使得部署SDN節(jié)點(diǎn)的數(shù)量最小,并且能夠?qū)崿F(xiàn)保護(hù)網(wǎng)絡(luò)中所有可能出現(xiàn)的單鏈路故障的目的。

在式(2)～式(4)中,變量y(i,j,k)的取值為0或者1,如果y(i,j,k)=1,則節(jié)點(diǎn)i是鏈路(j,k)的SDN節(jié)點(diǎn),否則如果y(i,j,k)=0,則表示節(jié)點(diǎn)i不是鏈路(j,k)的SDN節(jié)點(diǎn)。如果節(jié)點(diǎn)i是鏈路(j,k)的SDN節(jié)點(diǎn),則當(dāng)鏈路(j,k)出現(xiàn)故障時(shí),節(jié)點(diǎn)j可以先將報(bào)文發(fā)送給節(jié)點(diǎn)i,然后節(jié)點(diǎn)i再將報(bào)文發(fā)送給節(jié)點(diǎn)k。式(5)說明,如果某個(gè)節(jié)點(diǎn)i是鏈路(j,k)的SDN節(jié)點(diǎn),則節(jié)點(diǎn)j到節(jié)點(diǎn)i的最短路徑一定不包含鏈路(j,k),并且節(jié)點(diǎn)i至少有一個(gè)鄰居節(jié)點(diǎn)到k的最短路徑一定不包含鏈路(j,k),式(5)同時(shí)也給出了計(jì)算網(wǎng)絡(luò)中所有鏈路SDN節(jié)點(diǎn)的方法。為了更好地理解式(5),本文通過實(shí)例來進(jìn)行解釋。圖1表示節(jié)點(diǎn)i是鏈路(j,k)中SDN節(jié)點(diǎn)的情況,圖中節(jié)點(diǎn)間的虛線表示這2個(gè)節(jié)點(diǎn)之間的最短路徑,實(shí)線表示這2個(gè)節(jié)點(diǎn)是鄰居節(jié)點(diǎn)。當(dāng)鏈路(j,k)出現(xiàn)故障時(shí),節(jié)點(diǎn)j可以先將報(bào)文發(fā)送給節(jié)點(diǎn)i,并且節(jié)點(diǎn)j到節(jié)點(diǎn)i的最短路徑不能包含鏈路(j,k),然后如果節(jié)點(diǎn)i到節(jié)點(diǎn)k的最短路徑不包含鏈路(j,k),則節(jié)點(diǎn)i通過最短路徑將報(bào)文轉(zhuǎn)發(fā)給節(jié)點(diǎn)k,否則如果節(jié)點(diǎn)i到節(jié)點(diǎn)k的最短路徑包含鏈路(j,k),則節(jié)點(diǎn)i將報(bào)文轉(zhuǎn)發(fā)給其鄰居節(jié)點(diǎn)x,并且需要保證節(jié)點(diǎn)x到節(jié)點(diǎn)k的最短路徑不包含鏈路(j,k)。

圖1 節(jié)點(diǎn)i為鏈路(j,k)中SDN節(jié)點(diǎn)的情況

在式(6)～式(8)中,變量x(i)的取值為0或者1,如果x(i)=1,則該節(jié)點(diǎn)是SDN節(jié)點(diǎn),否則如果x(i)=0,則該節(jié)點(diǎn)是傳統(tǒng)網(wǎng)絡(luò)設(shè)備。在式(9)～式(11)中,變量f(i,j)的取值為0或者1,如果f(i,j)=1,則表示鏈路(i,j)在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,否則如果f(i,j)=0,則表示鏈路(i,j)不在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中。在式(12)～式(14)中,變量z((i,j),i,d)的取值為0或者1,如果z((i,j),i,d)=1,則表示鏈路(i,j)在節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑上,否則如果z((i,j),i,d)=0,則表示鏈路(i,j)不在節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑上。式(15)說明,對(duì)于網(wǎng)絡(luò)中的任意一條鏈路,該鏈路對(duì)應(yīng)唯一一個(gè)SDN節(jié)點(diǎn)。式(16)說明,如果有一條鏈路選擇某個(gè)節(jié)點(diǎn)為其對(duì)應(yīng)的SDN節(jié)點(diǎn),則該節(jié)點(diǎn)必將被部署為SDN節(jié)點(diǎn)。

2 算法描述

2.1 SLFRPHSDN算法

第1節(jié)分析了本文需要解決的關(guān)鍵問題,并且形式化地描述了該問題。從上文的描述可以看出,該問題中所有變量的取值均為0和1,因此需要解決的問題是一個(gè)0-1整數(shù)規(guī)劃。因?yàn)?-1整數(shù)規(guī)劃已經(jīng)被證明是一個(gè)NP問題,所以不可能在有限的時(shí)間內(nèi)獲得最優(yōu)解。在實(shí)際網(wǎng)絡(luò)中,網(wǎng)絡(luò)拓?fù)浯笮〉淖兓秶^大,從十幾個(gè)節(jié)點(diǎn)到上百個(gè)節(jié)點(diǎn)不等。在較小的網(wǎng)絡(luò)中,可以使用已有的工具如CPLEX獲得最優(yōu)解,但是在較大的網(wǎng)絡(luò)中,CPLEX將無法計(jì)算出最優(yōu)解。因此,本文提出一種通用的解決方案SLFRPHSDN,該方案適用于各種類型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

算法1SLFRPHSDN算法

輸入G=(V,E)

輸出M

1.計(jì)算網(wǎng)絡(luò)中任意鏈路(j,k)∈E對(duì)應(yīng)的SDN節(jié)點(diǎn)SDN(j,k)

3.M=Φ

4.While R(G,M)<1 and M≠V do

6.M←M∪m

7.For (j,k)∈E

8.If m∈SDN(j,k) then

9.清空SDN(j,k)

10.End If

11.End For

13.計(jì)算故障保護(hù)率R(G,M)

14.End While

15.Return M

2.2 算法實(shí)例

下文通過一個(gè)例子來詳細(xì)解釋算法SLFRPHSDN的執(zhí)行過程。圖2為一個(gè)包含8個(gè)節(jié)點(diǎn)和12條邊的簡單網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),邊上標(biāo)注的數(shù)值表示該邊的權(quán)值。

圖2 SLFRPHSDN算法執(zhí)行過程

表1 算法初始化后鏈路對(duì)應(yīng)的SDN節(jié)點(diǎn)

表2 算法執(zhí)行完第一次循環(huán)鏈路對(duì)應(yīng)的SDN節(jié)點(diǎn)

2.3 SLFRPHSDN算法的時(shí)間復(fù)雜度

上文詳細(xì)介紹了SLFRPHSDN的執(zhí)行過程,本節(jié)將從理論上分析該算法的時(shí)間復(fù)雜度。

定理1算法SLFRPHSDN的時(shí)間復(fù)雜度為O(|E||V-2|+|V|(|V|lg|V|+E))。

證明算法SLFRPHSDN的第1行對(duì)應(yīng)的時(shí)間復(fù)雜度為O(|E||V-2|+|V|(|V|lg|V|+E)),這是因?yàn)樵撔行枰獮榫W(wǎng)絡(luò)中的所有鏈路計(jì)算可能出現(xiàn)的SDN節(jié)點(diǎn),每一條鏈路對(duì)應(yīng)的SDN節(jié)點(diǎn)的數(shù)量最大為|V-2|。判斷某個(gè)節(jié)點(diǎn)是否為鏈路的SDN節(jié)點(diǎn)需要計(jì)算節(jié)點(diǎn)對(duì)之間的最短路徑,該部分的時(shí)間復(fù)雜度為O(|V|(|V|lg|V|+E))。算法第4行到第14行的功能是為所有的鏈路選擇最終的SDN節(jié)點(diǎn),時(shí)間復(fù)雜度為O(|E||V-2|)。綜上所述,算法SLFRPHSDN的時(shí)間復(fù)雜度為O(|E||V-2|+|V|(|V|lg|V|+E))。

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

本節(jié)將利用模擬實(shí)驗(yàn)來驗(yàn)證算法的性能,并對(duì)實(shí)驗(yàn)的結(jié)果做出合理的說明。本文利用C+ +語言實(shí)現(xiàn)算法,編譯器為CodeBlocks。該算法運(yùn)行的平臺(tái)為一臺(tái)PC機(jī),Intel(R) Core(TM) i7-7700 CPU@3.6 GHz處理器,16 GB內(nèi)存,64位Windows10操作系統(tǒng)。算法的評(píng)價(jià)指標(biāo)主要有SDN節(jié)點(diǎn)的數(shù)量、故障保護(hù)率和路徑拉伸度。部署SDN節(jié)點(diǎn)需要一定的開銷,如果只需要升級(jí)部分SDN節(jié)點(diǎn)就可以達(dá)到目的,則網(wǎng)絡(luò)開銷就越小,反之網(wǎng)絡(luò)負(fù)擔(dān)越大。如果故障保護(hù)率越接近100%,則該算法應(yīng)對(duì)網(wǎng)絡(luò)故障的能力越強(qiáng),反之應(yīng)對(duì)網(wǎng)絡(luò)故障的能力較弱。如果路徑拉伸度越接近于1,則該算法不會(huì)給網(wǎng)絡(luò)增加較大的時(shí)延,否則該算法將會(huì)大大增加網(wǎng)絡(luò)延遲,影響網(wǎng)絡(luò)傳輸性能。本文首先詳細(xì)介紹實(shí)驗(yàn)采用的網(wǎng)絡(luò)拓?fù)?然后給出實(shí)驗(yàn)結(jié)果,并對(duì)結(jié)果給出詳細(xì)的說明。

3.1 網(wǎng)絡(luò)拓?fù)?/h3>

為使實(shí)驗(yàn)的結(jié)果更具有說服力,本文將算法運(yùn)行在3種不同類型的網(wǎng)絡(luò)拓?fù)渲?即真實(shí)網(wǎng)絡(luò)拓?fù)洹y量網(wǎng)絡(luò)拓?fù)浜屠媚M軟件生成的網(wǎng)絡(luò)拓?fù)洹?/p>

1)真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[22-23]。在該類型的網(wǎng)絡(luò)拓?fù)渲羞x擇了4個(gè)真實(shí)網(wǎng)絡(luò)拓?fù)?Abilene包括11個(gè)節(jié)點(diǎn)和14條邊,TORONTO包括25個(gè)節(jié)點(diǎn)和55條邊,NJLATA、USLD包括28個(gè)節(jié)點(diǎn)和45條邊。

2)Rocketfuel[24]測量的拓?fù)浣Y(jié)構(gòu)。在該類型的網(wǎng)絡(luò)拓?fù)渲羞x擇了4個(gè)測量拓?fù)浣Y(jié)構(gòu)。AS1755包括87個(gè)節(jié)點(diǎn)和161條邊,AS1239包括315個(gè)節(jié)點(diǎn)和972條邊,AS3257包括161個(gè)節(jié)點(diǎn)和328條邊,AS3967包括79個(gè)節(jié)點(diǎn)和147條邊。

3)利用模擬軟件Brite生成的拓?fù)浣Y(jié)構(gòu)。Brite使用的模型為Waxman,拓?fù)渲泄?jié)點(diǎn)的數(shù)量在100和500之間,alpha的參數(shù)設(shè)置為0.15,beta的參數(shù)設(shè)置為0.2,網(wǎng)絡(luò)的平均度參數(shù)設(shè)置為2到4,網(wǎng)絡(luò)中節(jié)點(diǎn)的分布服從重尾分布,鏈路的帶寬參數(shù)設(shè)置為10到1 024,鏈路的代價(jià)和鏈路帶寬互為倒數(shù)。

3.2 SDN節(jié)點(diǎn)的數(shù)量

為了保護(hù)網(wǎng)絡(luò)中所有的鏈路,本文將網(wǎng)絡(luò)中部分傳統(tǒng)設(shè)備升級(jí)為SDN設(shè)備。但是升級(jí)SDN設(shè)備需要一定的經(jīng)濟(jì)開銷,因此如果升級(jí)的SDN節(jié)點(diǎn)數(shù)量越少,則帶來的經(jīng)濟(jì)開銷越小,否則,該方案很難在實(shí)際網(wǎng)絡(luò)中部署。因此,本節(jié)主要研究為保護(hù)網(wǎng)絡(luò)中所有的鏈路,不同網(wǎng)絡(luò)拓?fù)渲行枰渴餝DN節(jié)點(diǎn)的數(shù)量。表3說明了不同類型的網(wǎng)絡(luò)拓?fù)渲袑?duì)應(yīng)部署SDN節(jié)點(diǎn)的數(shù)量。在表3中,Brite(m,n)表示利用Brite軟件生成的拓?fù)浣Y(jié)構(gòu),節(jié)點(diǎn)數(shù)量為m,網(wǎng)絡(luò)平均度為n。

表3 SDN節(jié)點(diǎn)的數(shù)量

從表3可知,在真實(shí)網(wǎng)絡(luò)拓?fù)渲蠥bilene需要升級(jí)1/3左右的節(jié)點(diǎn),其余網(wǎng)絡(luò)拓?fù)鋬H僅需要升級(jí)1/8左右的節(jié)點(diǎn)。在測量拓?fù)渲?AS1755和AS3967需要升級(jí)1/7左右的節(jié)點(diǎn),AS3257需要升級(jí)1/16左右的節(jié)點(diǎn),而AS1239僅僅需要升級(jí)1/26的節(jié)點(diǎn)。在Brite生成的拓?fù)浣Y(jié)構(gòu)中,當(dāng)網(wǎng)絡(luò)的平均度為2時(shí),需要升級(jí)大約1/20～1/30左右的節(jié)點(diǎn),當(dāng)網(wǎng)絡(luò)的平均度為4時(shí),僅僅需要升級(jí)1/50～1/100左右的節(jié)點(diǎn)。從上面的實(shí)驗(yàn)結(jié)果可知,在稀疏圖中需要升級(jí)大量的SDN節(jié)點(diǎn),然而在稠密圖中僅僅需要升級(jí)少量的SDN節(jié)點(diǎn)。這是因?yàn)樵谙∈鑸D每條鏈路對(duì)應(yīng)的SDN節(jié)點(diǎn)數(shù)量較少,并且SDN節(jié)點(diǎn)重復(fù)的可能性較小。在稠密圖中,每條鏈路對(duì)應(yīng)的SDN節(jié)點(diǎn)數(shù)量較多,不同鏈路之間公共SDN節(jié)點(diǎn)較多。因此,在稀疏圖中,最終選擇的SDN數(shù)量較多,在稠密圖中,最終選擇的SDN數(shù)量較少。

3.3 故障保護(hù)率

本節(jié)利用故障保護(hù)率來衡量算法應(yīng)對(duì)故障的能力,故障保護(hù)率的數(shù)值越大,該算法應(yīng)對(duì)故障的能力越強(qiáng)。如果算法的故障保護(hù)率為100%,則表明該算法可以應(yīng)對(duì)網(wǎng)絡(luò)中所有可能出現(xiàn)的單鏈路故障情形。表4列出了算法在3種拓?fù)渲械墓收媳Ｗo(hù)率結(jié)果。

表4 故障保護(hù)率

由表4可知,在所有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,算法對(duì)應(yīng)的故障保護(hù)率為100%。這是因?yàn)楸疚牡乃惴梢詾樗械逆溌氛业絊DN節(jié)點(diǎn),從而達(dá)到保護(hù)鏈路的目的。

3.4 路徑拉伸度

本節(jié)利用路徑拉伸度來度量算法帶來的路徑開銷。在本文實(shí)驗(yàn)中,將路徑拉伸度定義為當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí),利用算法SLFRPHSDN計(jì)算出的路徑的代價(jià)和利用OSPF計(jì)算的最短路徑的代價(jià)的比值。表5列出了算法SLFRPHSDN在不同網(wǎng)絡(luò)拓?fù)渲袑?duì)應(yīng)的路徑拉伸度。

表5 路徑拉伸度

從表5可以看出,在實(shí)驗(yàn)的所有網(wǎng)絡(luò)拓?fù)渲?AS1239對(duì)應(yīng)的路徑拉伸度最大為1.267,其余網(wǎng)絡(luò)拓?fù)鋵?duì)應(yīng)的路徑拉伸度均小于該數(shù)值,因此該算法不會(huì)帶來較大的路徑開銷。尤其是在真實(shí)拓?fù)銩bilene中,算法對(duì)應(yīng)的路徑拉伸度僅為1.075,該數(shù)值和利用OSPF協(xié)議收斂后計(jì)算出的最短路徑的代價(jià)基本一致。

4 結(jié)束語

本文研究在傳統(tǒng)網(wǎng)絡(luò)中將傳統(tǒng)設(shè)備升級(jí)為SDN設(shè)備,從而使得路由保護(hù)算法可以應(yīng)對(duì)網(wǎng)絡(luò)中可能出現(xiàn)的單鏈路故障情形。通過將傳統(tǒng)網(wǎng)絡(luò)中部署SDN節(jié)點(diǎn)的問題描述為0-1整數(shù)規(guī)劃問題,并提出一種啟發(fā)式的算法SLFRPHSDN進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明,該算法只需在傳統(tǒng)網(wǎng)絡(luò)中將少部分節(jié)點(diǎn)升級(jí)為SDN節(jié)點(diǎn),故障保護(hù)率即可達(dá)到100%,并且不會(huì)帶來過多的路徑開銷。本文僅討論了混合SDN網(wǎng)絡(luò)中的單鏈路故障路由保護(hù)算法,下一步將針對(duì)多鏈路故障和單節(jié)點(diǎn)故障情形設(shè)計(jì)路由保護(hù)算法。