耿海軍,張 偉,尹 霞

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

0 概述

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

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

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

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

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

1 問題描述

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

上述問題可以描述為一個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)化目標,使得部署SDN節(jié)點的數(shù)量最小,并且能夠?qū)崿F(xiàn)保護網(wǎng)絡(luò)中所有可能出現(xiàn)的單鏈路故障的目的。

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

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

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

2 算法描述

2.1 SLFRPHSDN算法

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

算法1SLFRPHSDN算法

輸入G=(V,E)

輸出M

1.計算網(wǎng)絡(luò)中任意鏈路(j,k)∈E對應的SDN節(jié)點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.計算故障保護率R(G,M)

14.End While

15.Return M

2.2 算法實例

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

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

表1 算法初始化后鏈路對應的SDN節(jié)點

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

2.3 SLFRPHSDN算法的時間復雜度

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

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

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

3 實驗與結(jié)果分析

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

3.1 網(wǎng)絡(luò)拓撲

為使實驗的結(jié)果更具有說服力,本文將算法運行在3種不同類型的網(wǎng)絡(luò)拓撲中,即真實網(wǎng)絡(luò)拓撲、測量網(wǎng)絡(luò)拓撲和利用模擬軟件生成的網(wǎng)絡(luò)拓撲。

1)真實網(wǎng)絡(luò)拓撲結(jié)構(gòu)[22-23]。在該類型的網(wǎng)絡(luò)拓撲中選擇了4個真實網(wǎng)絡(luò)拓撲,Abilene包括11個節(jié)點和14條邊,TORONTO包括25個節(jié)點和55條邊,NJLATA、USLD包括28個節(jié)點和45條邊。

2)Rocketfuel[24]測量的拓撲結(jié)構(gòu)。在該類型的網(wǎng)絡(luò)拓撲中選擇了4個測量拓撲結(jié)構(gòu)。AS1755包括87個節(jié)點和161條邊,AS1239包括315個節(jié)點和972條邊,AS3257包括161個節(jié)點和328條邊,AS3967包括79個節(jié)點和147條邊。

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

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

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

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

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

3.3 故障保護率

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

表4 故障保護率

由表4可知,在所有網(wǎng)絡(luò)拓撲結(jié)構(gòu)中,算法對應的故障保護率為100%。這是因為本文的算法可以為所有的鏈路找到SDN節(jié)點,從而達到保護鏈路的目的。

3.4 路徑拉伸度

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

表5 路徑拉伸度

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

4 結(jié)束語

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