基于混合軟件定義網絡的路由保護算法

耿海軍,張 偉,尹 霞

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

0 概述

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

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

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

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

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

1 問題描述

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

上述問題可以描述為一個0-1整數線性規劃(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整數規劃模型。式(1)是本文的優化目標,使得部署SDN節點的數量最小,并且能夠實現保護網絡中所有可能出現的單鏈路故障的目的。

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

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

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

2 算法描述

2.1 SLFRPHSDN算法

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

算法1SLFRPHSDN算法

輸入G=(V,E)

輸出M

1.計算網絡中任意鏈路(j,k)∈E對應的SDN節點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的執行過程。圖2為一個包含8個節點和12條邊的簡單網絡拓撲結構,邊上標注的數值表示該邊的權值。

圖2 SLFRPHSDN算法執行過程

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

表2 算法執行完第一次循環鏈路對應的SDN節點

2.3 SLFRPHSDN算法的時間復雜度

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

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

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

3 實驗與結果分析

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

3.1 網絡拓撲

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

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

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

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

3.2 SDN節點的數量

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

表3 SDN節點的數量

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

3.3 故障保護率

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

表4 故障保護率

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

3.4 路徑拉伸度

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

表5 路徑拉伸度

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

4 結束語

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