崔文巖　孟相如　楊歡歡　李紀真　陳天平　康巧燕（空軍工程大學信息與導航學院西安710077）（清華大學電子工程系北京100084）

?

QoS約束的鏈路故障多備份路徑恢復算法

崔文巖*①孟相如①楊歡歡①②李紀真①陳天平①康巧燕①①
①（空軍工程大學信息與導航學院西安710077）
②（清華大學電子工程系北京100084）

鏈路故障的恢復，不僅僅是選擇一條連通的備份路徑問題，還應考慮網(wǎng)絡業(yè)務故障恢復過程中的QoS需求。針對此問題，該文基于多備份路徑策略，構(gòu)建概率關聯(lián)故障模型和重路由流量丟棄量優(yōu)化目標。并基于該優(yōu)化目標，以業(yè)務的QoS需求為約束，建立故障恢復問題的數(shù)學模型，提出一種QoS約束的鏈路故障多備份路徑恢復算法。該算法構(gòu)建單條備份路徑時，以最大程度地減少重路由流量丟棄為目標，并采用改進的QoS約束的k最短路徑法進行拼接，且給與高優(yōu)先級鏈路更多的保護資源。此外還證明了算法的正確性并分析了時間空間復雜度。在NS2環(huán)境下的仿真結(jié)果表明，該算法顯著提升了鏈路故障恢復率和重路由流量QoS滿足率，且QoS約束條件越強，相較于其它算法優(yōu)勢越明顯。

鏈路故障恢復；多備份路徑；QoS；重路由

1　引言

隨著通信技術(shù)的快速發(fā)展，網(wǎng)絡鏈路帶寬得到不斷擴充。目前全球至少有來自20多個國家的53個運營商已經(jīng)部署或正在考慮部署400 GB/s的骨干網(wǎng)絡［1］。高速骨干網(wǎng)鏈路即使短暫的故障也會造成大量的數(shù)據(jù)包丟棄，嚴重影響通信質(zhì)量。根據(jù)對ISP的觀察，骨干網(wǎng)鏈路一年內(nèi)大約有30%的概率會出現(xiàn)故障［2］，表明鏈路故障是網(wǎng)絡中較為普遍的現(xiàn)象。因此，加快故障的恢復速度，降低故障造成的業(yè)務丟棄已成為當前研究亟待解決的問題。

網(wǎng)絡故障主要表現(xiàn)為鏈路故障，鏈路故障恢復策略可分為主動式和被動式兩種［3，4］。被動式策略在網(wǎng)絡故障后動態(tài)自適應地進行全網(wǎng)資源重分配，但路由重新收斂花費較多的時間而不可接受。因此目前故障快速恢復研究以主動式策略為主，通過提前對網(wǎng)絡進行資源規(guī)劃和預留，使得故障時能迅速切換，如基于多拓撲［5］和基于備份路徑的故障恢復技術(shù)。多拓撲技術(shù)需要配置多個拓撲子層，路由存儲消耗大；基于備份路徑的故障恢復技術(shù)提供端到端路徑重路由，在全局范圍內(nèi)進行流量分配，易于基于現(xiàn)有協(xié)議實現(xiàn)。因此，備份路徑技術(shù)是當前故障恢復領域研究的熱點［611］-。

故障恢復的本質(zhì)在于維持故障鏈路承載流量的傳輸，因此應從流量持續(xù)傳輸角度解決故障恢復問題。大部分故障恢復工作集中在如何選擇可靠備份路徑上，且一般利用單一備份路徑進行故障恢復。然而當流量超出備份路徑可用帶寬時，單一備份路徑無法滿足故障恢復的要求。受到這一啟發(fā)，文獻［8］將多路徑技術(shù)引入到故障恢復中，采用多條備份路徑共同承擔流量，減少了流量的丟棄。在此基礎上，文獻［9］提出一種結(jié)合故障恢復與流量工程的網(wǎng)絡結(jié)構(gòu)，在多路徑故障恢復基礎上進行流量工程優(yōu)化，其目的是進行負載均衡，且假設備份路徑可用帶寬滿足故障恢復需求。文獻［10］考慮了不同故障狀況，通過將重路由流量分配給有跳數(shù)限制的多條備份路徑，在網(wǎng)絡投入運行之前就設計好應對各種故障場景的最低容量備份網(wǎng)絡。文獻［11］提出一種跨層故障恢復模型，考慮了備份鏈路的可靠性，提升了故障恢復成功率。然而，上述故障恢復算法大都以最大化重路由為目標，未考慮恢復后的流量是否滿足用戶的需求。但是經(jīng)由備份路徑的重路由流量即使最終傳輸成功，由于時延超時、鏈路過載等原因，也無法滿足業(yè)務的服務質(zhì)量需求（Quality of Service，QoS），屬于無效流量。雖然文獻［12］提出了一種滿足QoS約束的自適應調(diào)整的多路徑路由，但未考慮故障恢復問題。因此，目前已提出的大部分鏈路故障恢復算法不能很好地確保業(yè)務的服務質(zhì)量。

為此，本文針對QoS約束下的鏈路故障恢復問題進行研究，即在網(wǎng)絡可用帶寬和業(yè)務時延需求約束下進行最大化重路由流量問題求解。首先基于多備份路徑策略建立概率關聯(lián)故障模型和重路由流量丟棄優(yōu)化目標，并構(gòu)建QoS約束的故障多備份路徑恢復問題的數(shù)學優(yōu)化模型。然后，設計QoS約束的鏈路故障多備份路徑恢復算法（Multiple backup Paths Recovery for link failure w ith QoS constrain algorithm，MPR-QoS）對此問題進行求解。MPR-QoS算法在構(gòu)建單條備份路徑時，利用改進的QoS約束的k最短路徑法進行拼接，并以最大化減少重路由流量丟棄為目標，且分配給高優(yōu)先級鏈路更多的保護資源。此外還證明了算法的正確性并對時間空間復雜度進行了分析。最后，在NS2仿真環(huán)境下從故障恢復率、重路由流量QoS滿足率、鏈路過載率和算法運行時間等方面驗證了本文算法的優(yōu)越性。

2　問題描述

2.1備份路徑策略

備份路徑策略是基于備份路徑故障恢復方法的關鍵問題［8］，對故障恢復效果有較大影響。雖然采用更多的備份路徑可以減少流量的丟棄，但是如果備份路徑數(shù)量過大會大大增加配置復雜度和存儲開銷，并且網(wǎng)絡對節(jié)點對之間可以設置的備份路徑數(shù)量有嚴格的限制，為此，本文設定每條鏈路最多擁有N條備份路徑。文獻［9］指出擁塞網(wǎng)絡的隊列時延隨跳數(shù)呈指數(shù)規(guī)律增加，且光網(wǎng)絡中的信號質(zhì)量隨著路徑跳數(shù)的增加而迅速下降，因此為支撐QoS需求，對備份路徑施加跳數(shù)限制是非常有必要的，文中限制備份路徑最大跳數(shù)為H。網(wǎng)絡拓撲利用有權(quán)無向圖G（V，E）表示，其中V和E分別表示路由器節(jié)點和鏈路集合。

2.2概率關聯(lián)故障模型

當前的鏈路故障恢復算法大多是針對獨立故障的，而事實上有時候鏈路故障并不是完全獨立的，比如當?shù)讓庸饫w鏈路故障時，由其承載的多條邏輯鏈路可能會同時失效，即鏈路故障之間存在概率關聯(lián)。共享風險鏈路組（Shared Risk Link Group，SRLG）模型［13］用來表示一組共享同一風險的鏈路集合，當SRLG中的一條鏈路失效時，該組中其它鏈路以1的概率出現(xiàn)失效。但實際上關聯(lián)故障并非100%絕對關聯(lián)，擁有關聯(lián)故障的兩條鏈路中的一條鏈路發(fā)生故障時，另一條鏈路只是以某一概率發(fā)生故障。為此，我們給出了概率共享風險鏈路組概念，在傳統(tǒng)的SRLG模型中加入故障關聯(lián)概率來表示擁有一定概率關聯(lián)的故障模型。

定義1概率共享風險鏈路組（Probabilistically Shared Risk Link G roup，PSRLG），設R為SRLG事件集合，當任意事件r R∈發(fā)生時，故障發(fā)生概率不為0的鏈路集合構(gòu)成事件r的PSRLG，如式（1）所示。

用rp表示事件r發(fā)生概率，鏈路和存在故障關聯(lián)時，各自發(fā)生故障的概率分別用和表示。

2.3優(yōu)化目標

式（4）中假設N條備份路徑均可用，根據(jù)前面分析，鏈路之間存在概率關聯(lián)故障，那么鏈路故障時也可能同時發(fā)生故障，如果發(fā)生故障，其上承載的重路由流量被丟棄。利用表示鏈路故障概率，并設鏈路故障時的故障概率為則考慮備份路徑可靠性時鏈路故障下的重路由流量丟棄量可用式（5）表示。

那么，網(wǎng)絡中所有鏈路因故障造成的重路由流量丟棄量之和可以表示為

本文算法的設計目標就是在業(yè)務QoS需求約束下，使得式（8）值最小，式（8）即為本文的優(yōu)化目標。

3　故障多備份路徑恢復問題的數(shù)學模型

本節(jié)以最小化重路由流量丟棄為目標，以業(yè)務QoS需求為約束，利用多備份路徑技術(shù)，對故障恢復問題進行混合整數(shù)線性規(guī)劃（M ixed Integer Linear Program，M ILP）建模。

（2）目標函數(shù)：

本文的目標函數(shù)是最小化全網(wǎng)范圍內(nèi)的重路由流量丟棄量。它包含兩部分，一是超出所有備份路徑重路由能力部分，二是因備份路徑自身故障而丟棄部分。

（3）約束條件：

（a）流守恒約束：

（b）容量約束：

式（11）為重路由流量約束，式（12）為鏈路帶寬容量約束。重路由流量約束表示鏈路的所有備份路徑重路由流量最大是其負載。鏈路帶寬容量約束表示每條鏈路承載的重路由流量不應超過其可用帶寬。其中表示鏈路故障時分配給鏈路的流量，其值可用式（13）表示。

feuv）由從節(jié)點i到u經(jīng)過不同跳數(shù)的所有備份路徑重路由流量之和構(gòu)成，如式（14）所示，式（13）與式（14）是等價關系。

（c）變量約束：

式（15）表示每條鏈路最多有N條備份路徑，每條備份路徑的時延最大為H跳。式（16）表示備份路徑預留帶寬非負。滿足整數(shù)約束條件式（17），因此本模型屬于非確定性多項式時間難問題（NP-hard）。

4　 MPR-QoS算法設計

鏈路故障恢復問題的M ILP模型是NP-hard問題，雖然可以利用單純形法等傳統(tǒng)線性規(guī)劃方法求解，但隨著問題規(guī)模的增加，計算時間復雜度較高，并不適用于大規(guī)模網(wǎng)絡故障恢復問題的求解。因此，本節(jié)設計MPR-QoS算法對QoS約束下的故障多備份路徑恢復問題進行求解。該算法由單條備份路徑拼接和備份路徑選擇兩個子算法構(gòu)成，其求解目標是在QoS約束下通過為網(wǎng)絡中每條鏈路選擇最多N條備份路徑，并合理分配資源使得全網(wǎng)重路由流量丟棄量最小。

4.1單條備份路徑拼接鏈路的備份路徑選擇是逐條進行的，單條備份路徑的選擇類似于計算最短路徑的k最短路徑算法，從節(jié)點開始，通過逐條添加鏈路來擴充備份路徑。假設鏈路已有1k-條備份路徑，額外添加一條備份路徑減少的流量丟棄量可用式（18）表示。

MPR-QoS算法在進行單條備份路徑拼接時，目的是要構(gòu)造一條使最大的。以鏈路的第k條備份路徑的拼接算法為例給出表1所示的單條備份路徑拼接算法。單條備份路徑拼接采用改進的k最短路徑法，使之保證每一條備份路徑存在可用的帶寬且滿足業(yè)務時延約束，選取最短備份路徑集合最大的最短備份路徑作為鏈路的第k條備份路徑。

表1　 M PR-QoS的單條備份路徑拼接算法（鏈路ije，第k條備份路徑拼接算法）

4.2備份路徑選擇由于承載較多流量負載的鏈路在故障時重路由流量較多，很可能因為網(wǎng)絡中沒有足夠多的帶寬資源而造成重路由流量的丟棄，而高故障概率鏈路更易發(fā)生故障，因此本文利用鏈路的流量負載與故障概率之積來確定其受保護優(yōu)先級，定義鏈路的優(yōu)先級如式（19）。

MPR-QoS算法在備份路徑選擇階段的算法是一種啟發(fā)式的多輪迭代算法，如表2所示。該算法首先按照承載流量負載大小和故障概率計算鏈路的優(yōu)先級LP，并根據(jù)LP值的大小依次為每一條鏈路構(gòu)造最多N條備份路徑，構(gòu)建每一條備份路徑的同時，更新鏈路的剩余重路由流量負載和網(wǎng)絡帶寬資源。

相比較已有的基于備份路徑的故障恢復算法［14，15］，MPR-QoS算法的優(yōu)勢在于，一是通過為每條鏈路確定優(yōu)先級，使得高優(yōu)先級鏈路獲得更多的保護資源，降低了全網(wǎng)范圍內(nèi)因故障造成的流量負載的丟棄；二是在每一輪迭代構(gòu)造單條備份路徑時，不僅考慮可用帶寬資源，還考慮備份路徑的時延，在業(yè)務QoS約束下，確保每一條新增的備份路徑均最大程度地減少重路由流量的丟棄。最終，MPR-QoS算法既滿足了業(yè)務QoS約束，又最大程度地保證了故障鏈路流量負載的重路由。

表2　M PR-QoS的備份路徑選擇算法

4.3MPR-QoS正確性證明

定理1在給定的網(wǎng)絡拓撲約束下，假設k最短路徑算法能生成k條最短路徑，那么MPR-QoS的單條備份路徑拼接算法能生成滿足可用帶寬和業(yè)務時延約束的備份路徑集合Ω（BPi，j）。

證明考察4.1節(jié)算法描述可知單條備份路徑拼接算法對k最短路徑算法的擴展主要在兩個方面：（1）在k條最短路徑構(gòu)建過程中增加跳數(shù)H限制，改變了k條最短路徑生成的判斷條件；（2）在k條最短路徑生成完畢后增加可用帶寬約束，保留滿足可用帶寬備份路徑至Ω（BPi，j）。k最短路徑算法可以通過構(gòu)建包含k個最短路徑的k最短路徑樹Tk，樹Tk的根節(jié)點為i，葉子節(jié)點為終節(jié)點j的k個備份。為此，單條備份路徑拼接算法基于k最短路徑樹Tk實現(xiàn)［16］。

下面采用數(shù)學歸納法證明。

當k=1時，生成樹Tk只包含1條最短路徑。如果該最短路徑構(gòu)建過程中H超時，得到Ω（BPi，j）為空；如果H時延滿足但不存在可用帶寬，同樣得到Ω（BPi，j）為空；如果2個條件均滿足，得到Ω（BPi，j）包含一個元素。命題成立。

假設當k=n時命題成立。即單條備份路徑拼接算法能生成滿足可用帶寬和時延約束的備份路徑集。

當k=n+1時，討論第n+1條備份路徑生成的情況，即利用已求得的p1，p2，…，pn求取pn+1。

我們利用偏離路徑概念構(gòu)建Tk。假設p=（m1，m2，…，）和q=（n1，n2，…，ns）分別為i到j的兩條路徑，如果有滿足以下約束的x，

單條備份路徑拼接算法相比基于最短偏離路徑的pn+1生成算法，主要改變發(fā)生在遍歷mt尋找至節(jié)點j最短路徑的過程，此過程加入了時延及帶寬約束。每一個節(jié)點mt至j的最短路徑可以采用Dijkstra算法求解，加入時延及帶寬約束后得到的節(jié)點mt至j的最短路徑集合是未加約束的子集，即縮小了偏離節(jié)點范圍，得到的mt至j的最短路徑可能是次最短路徑；由于k=n時命題成立，pn上從i到mt的路徑是滿足時延及帶寬約束的最短路徑，將i到mt與mt至j的最短路徑拼接即可得到pn+1的候選路徑；最后選取可用帶寬最大的路徑作為pn+1。

則當k=n+1時命題成立。

通過以上證明可知定理1得證。

MPR-QoS備份路徑選擇算法通過多輪迭代運算完成，主要嵌套單條備份路徑拼接算法實現(xiàn)，本質(zhì)上是迭代運算過程。因此，在單條備份路徑拼接算法可以正確執(zhí)行的情況下，備份路徑選擇算法可以正確執(zhí)行。另外，MPR-QoS算法基于k最短路徑算法實現(xiàn)，同樣可以保證產(chǎn)生的路徑是無環(huán)路的。

證畢

4.4MPR-QoS時間、空間復雜度分析

MPR-QoS算法的單條備份路徑拼接過程類似于k最短路徑算法，因此擁有同樣的計算復雜度O（E+V）lg（V）。由于網(wǎng)絡中共有E條鏈路，每條鏈路最多有N條備份路徑，則MPR-QoS算法的計算復雜度為O（E+V）lg（V）N E。

MPR-QoS算法采用4個1維向量存儲算法運行產(chǎn)生的數(shù)據(jù)：1個向量存儲每條鏈路的最短備份路徑集合Ω（BPi，j），路徑可由一系列節(jié)點描述，單條路徑的存儲空間不會超過V，則該向量存儲空間最多為1個向量作為鏈表存儲單條備份路徑拼接結(jié)果，所需存儲空間最多為1個向量存儲鏈路優(yōu)先級排序結(jié)果，存儲空間為；1個向量存儲鏈路的備份路徑構(gòu)造結(jié)果，存儲空間為因此，MPR-QoS算法的空間復雜度為

5　性能評估與分析

NS2作為主流的網(wǎng)絡仿真工具，可以有效地實現(xiàn)網(wǎng)絡協(xié)議和算法的正確性驗證和性能分析。本文以此為仿真平臺，對MPR-QoS算法和已有鏈路故障恢復算法進行對比仿真，并從鏈路故障恢復能力、重路由流量QoS滿足率、鏈路過載率和算法運行時間4個方面討論MPR-QoS算法的性能。

5.1實驗環(huán)境設置

實驗拓撲采用Tier-1骨干網(wǎng)絡［17］，仿真參數(shù)設置如表3。計算鏈路最短備份路徑的k最短路徑算法中的k值取5。

鏈路故障場景做以下設置。共配置9個共享風險鏈路組（SRLG）事件，各事件包含共享風險鏈路2～5條，令SRLG事件發(fā)生故障概率（式（2）中的rp）范圍為［0.05%，0.5%］，各SRLG事件故障下其組內(nèi)鏈路的條件概率范圍為［0.3，1］。在獨立故障鏈路中取10%作為高概率故障鏈路，其故障概率范圍為［0.1%，0.5%］，其余鏈路的故障概率范圍為［0.01%，0.1%］。共配置50組故障概率場景，針對每組故障概率場景在不同的隨機數(shù)種子（seed）下進行50次故障恢復仿真。每次仿真中隨機選擇1條鏈路作為故障鏈路，若該鏈路包含于某概率共享風險鏈路組中，則按照條件概率選擇并發(fā)的關聯(lián)故障鏈路，并取實驗結(jié)果的平均值作為最終仿真結(jié)果。

表3　仿真參數(shù)設置

對比算法描述如下：SelectBP［11］算法考慮備份路徑的可用帶寬約束，不考慮備份路徑時延，以最小化重路由流量丟棄量為目標；R3［8］算法以多重故障下的網(wǎng)絡無擁塞為目標；FR-TE［9］算法以故障恢復過程的全網(wǎng)范圍內(nèi)負載均衡最優(yōu)化為目標。

5.2性能分析

本文從故障恢復率、重路由流量QoS滿足率、鏈路過載率和算法運行時間4個方面對算法進行性能比較，仿真結(jié)果表明MPR-QoS算法具有以下優(yōu)勢。

（1）提升了故障恢復率：故障恢復率是完全恢復的故障鏈路所占比例，算法MPR-QoS考慮備份路徑數(shù)目N分別為2，3，4三種情況，算法對比在2種不同時敏業(yè)務下進行，結(jié)果如圖1所示。由圖可知，MPR-QoS算法隨著備份路徑數(shù)N的增大，故障恢復率呈逐漸上升趨勢，且在高時敏業(yè)務時提升了約17.5%，因此N值可以設置的大一些，但是備份路徑數(shù)過多會增加路由器的工作量，使得算法實用性較差，且網(wǎng)絡對于可以設置的備份路徑數(shù)量有嚴格的限制，因此綜合考慮，將MPR-QoS的N值設為4。N為4時，相比較其它故障恢復算法，低時敏業(yè)務時MPR-QoS算法故障恢復率最多提升了35.1%，高時敏業(yè)務時MPR-QoS算法故障恢復率最多提升了48.0%。仍以備份路徑取4為例，相比低時敏業(yè)務需求，高時敏業(yè)務需求時，MPR-QoS算法故障恢復率下降了約2.8%，而其它故障恢復算法故障恢復率最多下降了約19.9%，表明業(yè)務時敏需求的增強對MPR-QoS算法的故障恢復率影響更小。主要原因是MPR-QoS算法采用概率關聯(lián)故障模型只挑選可靠的備份路徑，且優(yōu)先保護高優(yōu)先級鏈路，使得易發(fā)生故障和高負載鏈路獲得更多的保護資源。由于缺乏時延限制，SelectBP，F(xiàn)R-TE和R 3算法在高時敏業(yè)務下，故障恢復效果較差，受業(yè)務時敏性影響大，F(xiàn)R-TE和R 3算法沒有考慮備份路徑的可靠性問題，故障恢復率較低。

（2）顯著提升了鏈路故障時的重路由流量QoS滿足率，且網(wǎng)絡業(yè)務時敏性越強，算法優(yōu)勢越明顯：重路由流量QoS滿足率是滿足業(yè)務QoS需求的重路由流量占總重路由流量的比例，不同業(yè)務時敏需求下4種算法的重路由流量QoS滿足率的仿真結(jié)果如圖2所示，其中業(yè)務時敏需求分布范圍為［50ms，275 ms］，與現(xiàn)實網(wǎng)絡中的大部分業(yè)務時延需求相一致［9］，設置MPR-QoS算法的備份路徑H值與業(yè)務時敏需求相匹配，N值取4。從圖中可以看出，MPR-QoS算法的重路由流量QoS滿足率始終維持在98%以上，基本不受業(yè)務時敏需求的影響，而SelectBP，F(xiàn)R-TE和R3算法隨著業(yè)務時敏需求的增強，重路由流量QoS滿足率迅速下降，F(xiàn)R-TE算法在業(yè)務需求50ms時相比275 ms時，重路由流量QoS滿足率下降量達54.8%。主要原因是MPR-QoS算法考慮了QoS約束，而其它3種算法缺乏這一限制，當業(yè)務時延需求增強時，滿足QoS需求的流量逐漸下降，嚴重影響業(yè)務傳輸質(zhì)量。

（3）避免了鏈路過載情況的發(fā)生：鏈路過載率是因重路由過載的鏈路占所有鏈路的比例。由于運營商一般將鏈路利用率控制在40%以內(nèi)［11］，本文仿真分布范圍為［5%，40%］鏈路利用率時鏈路過載情況，圖3為加載低時敏業(yè)務時的仿真結(jié)果。由圖中可以看出，MPR-QoS和SelectBP算法鏈路過載率始終保持在5%以內(nèi)，與鏈路利用率無關；FR-TE和R 3算法隨著鏈路利用率的升高，鏈路出現(xiàn)大范圍的過載，當鏈路利用率達到40%時，2種算法的鏈路過載率超過45%，大大降低了故障恢復性能。主要原因是MPR-QoS和SelectBP算法僅采用具有可用帶寬的鏈路來恢復故障，且嚴格控制備份路徑的重路由流量，最大程度地避免了鏈路過載情況的發(fā)生。

（4）降低了鏈路故障恢復問題的求解時間：表4表示4種算法求解鏈路故障恢復問題的平均運行時間。從表中可以看出，相較于MPR-QoS和SelectBP算法，F(xiàn)R-TE和R3算法時間開銷較大，極大地影響鏈路故障恢復時配置保護資源所需的時間。主要原因是MPR-QoS和SelectBP算法采用了多輪啟發(fā)式算法，大大縮短了問題求解時間，而FR-TE和R3算法采用傳統(tǒng)的線性規(guī)劃方法求解約束優(yōu)化問題，求解時間隨著網(wǎng)絡規(guī)模的增長呈指數(shù)規(guī)律增加。

表4　算法運行時間（s）

6　結(jié)束語

本文研究了具有QoS約束的鏈路故障恢復問題。以往的故障恢復算法目標是尋找可連通的備份路徑，并盡最大努力地保證故障鏈路的重路由，忽略了業(yè)務的QoS需求，特別對于高時延敏感業(yè)務，重路由后的流量中無效流量占很大的比例。針對此問題，本文在網(wǎng)絡可用帶寬資源和業(yè)務時延約束下最大化重路由流量，提出故障概率關聯(lián)的多備份路徑模型，并將故障恢復問題建模為M ILP模型，利用提出的MPR-QoS算法進行求解。此外通過數(shù)學推導證明提出的算法理論上是正確的。仿真結(jié)果表明，與傳統(tǒng)的故障恢復算法相比，MPR-QoS算法提升了故障恢復率，避免了鏈路過載現(xiàn)象的發(fā)生，降低了運行時間，顯著地提升了鏈路故障時的重路由流量QoS滿足率，且網(wǎng)絡業(yè)務時延敏感需求越強，算法優(yōu)勢就越明顯。

圖1　故障恢復率

圖2　重路由流量QoS滿足率

圖3　鏈路過載率

［1］W ELLBROCK G and X IA T J.How w ill optical transport deal w ith future network traffic grow th？［C］.Op tical Communication（ECOC），Cannes，F(xiàn)rance，2014:21-25.doi: 10.1109/ECOC.2014.6964248.

［2］TURNER D，LEVCHENKO K，SNOEREN A C，et al. California fault lines:understanding the causes and im pact of network failu res［C］.ACM SIGCOMM，New Delhi，India，2010:315-326.doi:10.1145/1851275.1851220.

［3］張民貴，劉斌.IP網(wǎng)絡的快速故障恢復［J］.電子學報，2008，36（8）:1595-1602.

ZHANG M ingui and LIU Bin.Fast failure recovery of IP networks［J］.Acta Electronica Sinica，2008，36（8）:1595-1602.

［4］齊寧，汪斌強，王志明.可重構(gòu)服務承載網(wǎng)容錯構(gòu)建算法研究［J］.電子與信息學報，2012，34（2）:468-473.doi: 10.3724/SP.J.1146.2011.00670.

QINing，WANG Binqiang，and WANG Zhim ing.Research on reconfigurab le service carrying network resilient construction algorithm s［J］.Journal of Electronics&Information Technology，2012，34（2）:468-473.doi:10.3724/SP.J. 1146.2011.00670.

［5］SHAND M and BRYANT S.IP fast reroute framework［P］America，RFC5714，2010.

［6］王禹，王振興，張連成.一種基于結(jié)構(gòu)化備份子圖的路由系統(tǒng)失效恢復方法［J］.電子與信息學報，2013，35（9）:2254-2260. doi:10.3724/SP.J.1146.2012.01669.

WANG Yu，WANG Zhenxing，and ZHANG Liancheng.A failure recovery method for routing system based on structured backup subgraph［J］.Journal of Electronics& Information Technology，2013，35（9）:2254-2260.doi: 10.3724/SP.J.1146.2012.01669.

［7］YANG B H，LIU J D，and SHENKER S，et al.Keep forward ing:Towards k-link failure resilient routing［C］.IEEE INFOCOM 2014 IEEE Conference on Computer Communications，Toronto，Canada，2014:1617-1625.doi: 10.1109/INFOCOM.2014.6848098.

［8］WANG Y，WANG H，MAHIMKAR A，et al.R3:resilient rou ting reconfiguration［C］.ACM SIGCOMM，New Delh i，India，2010:291-302.doi:10.1145/1851275.1851218.

［9］SUCHARA M，XU D，DOVERSPIKE R，et al.Network architecture for joint failure recovery and traffic engineering［C］.ACM SIGMETRICS，New York，NY，USA，2011:97-108.doi:10.1145/2007116.2007128.

［10］BANNER R and ORDA A.Design ing low-capacity backup networks for fast restoration［C］.2010 Proceedings IEEE INFOCOM，San Diego，America，2010:1-9.doi: 10.1109/INFCOM.2010.5462007.

［11］ZHENG Q，CAO G H，THOMAS F，et al.Cross-layer app roach for m inim izing rou ting disruption in IP networks［J］. IEEE Transactions on Paralleland D istributed Systems，2014，25（7）:1659-1669.doi:10.1109/TPDS.2013.157.

［12］M ISRA S，XUE G L，and YANG D J.Polynom ial time app roximations for multi-path routing w ith bandw idth and delay constrains［C］.IEEE INFOCOM，Rio de Janeiro，Brazil，2009:558-566.doi:10.1109/INFCOM.2009.5061962.

［13］TERESA G，M IGUEL S，JOSE C，et al.Two heuristics for calculating a shared risk link group disjoint set of paths of m in-sum cost［J］.Journal of Network and System Managem ent，2014，37（10）:332-338.doi:10.1007/s10922-014-9332-6.

［14］ZHENG Q，CAO G，PORTA T L，et al.Optim al recovery from large-scale failu res in IP networks［C］.IEEE ICDCS，Macau，China，2012:295-304.doi:10.1109/ICDCS.2012.47.

［15］JOHNSTON M，LEE H W，and MODIANO E.A robust optim ization approach to backup network design w ith random failures［C］.IEEE INFOCOM，Shanghai，China，2011: 1512-1520.doi:10.1287/op re.1050.0238.

［16］周靈，王建新.路徑節(jié)點驅(qū)動的低代價最短路徑樹算法［J］.計算機研究與發(fā)展，2011，48（5）:721-728.

ZHOU Ling and WANG Jianxin.Path nodes-driven least-cost shortest path tree algorithm［J］.Journal of Computer Research and Development，2011，48（5）:721-728.

［17］ZHENG Q，ZHAO J，and CAO G H.A cross-layer approach for IP network protection［C］.Dependable System s and Networks（DSN），Boston，MA，USA，2012:1-12.

崔文巖：男，1987年生，博士生，研究方向為信息系統(tǒng)網(wǎng)絡抗毀技術(shù).

孟相如：男，1963年生，博士，教授，研究方向為寬帶通信網(wǎng).

楊歡歡：男，1988年生，博士生，研究方向為下一代通信技術(shù).

Link Failure Recovery A lgorithm Based on M ultiple Backup Pathsw ith QoSConstraint

CUIWenyan①MENG Xiangru①YANG Huanhuan①②LI Jizhen①CHEN T ianping①KANG Qiaoyan①
①（College of Information and Navigation，Air Force Engineering University，Xi’an 710077，China）
②（Departm ent of E lectronic Engineering，Tsinghua University，Beijing 100084，China）

Recovery of link failure is not only the issue of selecting a connected backup path，but the QoS requirement in the process of failure recovery of the network service shou ld be also taken into account.The probabilistically correlated failuremodel and rerouting traffic disruption optim ization target are built based on multip le backup paths strategy.Furthermore，a mathematical model of the failu re recovery p roblem is modeled，which takes them inimum rerouting traffic disruption as the target and the QoS requirement as the constrain，and a link failure recovery algorithm based on multiple backup pathsw ith QoS constrain is p roposed.The p roposed algorithm takes reducing rerouting traffic disruption farthest as the target and adop ts the im proved k shortest path algorithm with QoS constrain to splice the single backup path，and it gives the linksmore protection resourcew ith high priority.Moreover，the correctness of the p roposed algorithm is p roved，and the time comp lex and the space com p lex are com puted.The sim ulation results under NS2 show that the proposed algorithm significan tly im p roves link failure recovery rate and theQoS satisfaction rate of the rerouting traffic，and it performs betterwhen the QoS constrain is stronger.

Link failure recovery；M u ltip le backup paths；QoS；Reroute

s:The National Natural Science Foundation of China（61201209，61401499），Natural Science Foundation of Shaanxi P rovince（2013JQ 8013，2015JM 6340）

TP393

A

1009-5896（2016）08-1850-08

10.11999/JEIT 151230

2015-11-03；改回日期：2016-03-03；網(wǎng)絡出版：2016-05-09

崔文巖cw y_edu@163.com

國家自然科學基金（61201209，61401499），陜西省自然科學基金（2013JQ 8013，2015JM 6340）