MPLS快速重路由多故障恢復(fù)算法的研究

楊振啟，何文庭，楊云雪

（南京信息工程大學(xué) 計算機(jī)與軟件學(xué)院，江蘇 南京210044）

0 引 言

1 MPLS快速重路由技術(shù)

MPLS快速重路由技術(shù)利用預(yù)先建立的備份路徑來應(yīng)對網(wǎng)絡(luò)出現(xiàn)的故障，根據(jù)備份路徑的保護(hù)方式，主要有Detour和Bypass兩種路徑保護(hù)方式［10］。

Detour路徑保護(hù)方式為每條工作路徑建立單獨的LSP作為備份路徑，稱作Detour LSP。Detour方式資源消耗較大，但是能夠快速對故障進(jìn)行恢復(fù)，因此只適用對網(wǎng)絡(luò)的關(guān)鍵路徑進(jìn)行保護(hù)。

Bypass路徑保護(hù)方式使用一條備份路徑對多條工作路徑同時進(jìn)行保護(hù)，稱為Bypass Tunnel。Bypass方式同時對多條LSP進(jìn)行保護(hù)，減少了資源消耗，但是備份路徑上的預(yù)留資源不能共享，故障恢復(fù)速度較慢，適用對全局工作路徑進(jìn)行保護(hù)。

通常來說，Bypass路徑保護(hù)是在預(yù)知容易發(fā)生故障的地點預(yù)先建立好備份路徑，而Detour路徑保護(hù)是在工作路徑建立或者撤消的同時分布式建立或者撤消備份路徑。為了能夠?qū)崿F(xiàn)不同的備份LSP共享鏈路預(yù)留帶寬資源，有效減少鏈路帶寬資源的消耗，本文的多故障恢復(fù)算法采用Detour路徑保護(hù)方式對工作路徑實施保護(hù)。

2 多故障恢復(fù)算法

當(dāng)前的快速重路由模型和算法大多是針對網(wǎng)絡(luò)的單一故障，缺乏對于網(wǎng)絡(luò)多點故障恢復(fù)技術(shù)的研究。由于資源消耗大或者故障檢測點之間缺乏對多點故障的認(rèn)知能力，針對單點故障的模型和算法很難使用于多點故障的情況。而在目前已提出的多故障恢復(fù)算法中，為了降低備份寬帶資源消耗，主要在全局路徑保護(hù)模型的基礎(chǔ)上進(jìn)行改進(jìn)，先將一條工作路徑劃分為若干區(qū)域，在各區(qū)域中再進(jìn)行局部恢復(fù)。但是這些算法在如何劃分區(qū)域、如何解決域間共享段發(fā)生故障時進(jìn)行有效恢復(fù)、故障恢復(fù)時間、資源消耗等問題上存在不少困難。如果采用局部路徑保護(hù)的方式，則可以避免采用全局路徑保護(hù)所遇到的問題。然而，這樣會消耗大量的網(wǎng)絡(luò)帶寬資源，不利于對整個網(wǎng)絡(luò)進(jìn)行保護(hù)。

顯效:無出現(xiàn)惡心、牽拉疼痛、低血壓等并發(fā)癥,肌松良好、術(shù)野顯露好,生命體征循環(huán)指標(biāo)麻醉前后穩(wěn)定;有效:生命體征循環(huán)指標(biāo)麻醉前后有一定波動,肌松較好,牽拉疼痛不明顯;無效:生命體征循環(huán)指標(biāo)麻醉前后明顯波動。老年人腹部手術(shù)麻醉效果為顯效、有效百分率之和[3]。

2.1 算法思想

本文從如何有效的管理備份鏈路預(yù)留帶寬資源的角度出發(fā)，提出一種鏈路帶寬資源共享機(jī)制，降低局部路徑保護(hù)方式的備份資源消耗率，提高局部路徑保護(hù)模型在多故障網(wǎng)絡(luò)中使用的可行性，使得網(wǎng)絡(luò)的多故障能夠得到快速有效的恢復(fù)。

網(wǎng)絡(luò)故障不僅可能發(fā)生在工作路徑，還可能發(fā)生在備份路徑上面。此外，新算法對鏈路預(yù)留帶寬的共享管理措施使得多條備份路徑能夠共享一條鏈路的預(yù)留資源，但是當(dāng)這些備份路徑所保護(hù)的工作路徑有兩條或者兩條以上同時發(fā)生故障時，將會發(fā)生多條備份路徑搶占預(yù)留資源的情況。為了應(yīng)對這些可能出現(xiàn)的情況，本文采取主從備份的措施，為工作路徑提供兩條備份路徑，并對備份路徑設(shè)置優(yōu)先級。主從備份路徑是本地節(jié)點根據(jù)受約束最短路徑優(yōu)先算法（CSPF）計算出來的或者顯示設(shè)置的最優(yōu)路徑和次優(yōu)路徑。

MPLS快速重路由技術(shù)是基于MPLS流量工程（MPLS－TE）來實現(xiàn)的［11］。MPLS－TE為了保證重要隧道的順利建立，采用優(yōu)先級機(jī)制［12］。可以為每一條隧道配置兩個優(yōu)先級：設(shè)置和保持。設(shè)置優(yōu)先級和保持優(yōu)先級都通過各自相應(yīng)的數(shù)值來說明一條TE隧道是否可以搶占另一條TE隧道。優(yōu)先級的值越低，重要程度越高。本文為每條工作路徑的備份路徑添加相應(yīng)的設(shè)置優(yōu)先級和保持優(yōu)先級。

2.2 鏈路帶寬資源共享機(jī)制

為了說明鏈路帶寬資源共享機(jī)制的工作原理和多故障恢復(fù)算法步驟，文中定義了如下概念：

網(wǎng)絡(luò)模型圖G（V，E）：有向模型圖，V代表節(jié)點集合，E代表鏈路集合。

工作LSP：網(wǎng)絡(luò)正常情況下用于傳輸數(shù)據(jù)流的LSP。

主備份LSP：網(wǎng)絡(luò)發(fā)生故障時，首先采用的備份LSP，已預(yù)先建立。

從備份LSP：網(wǎng)絡(luò)發(fā)生故障，主備份LSP失效時，另外采用的備份LSP，預(yù)先計算好，但未建立。

主節(jié)點：備份路徑上有流量流出的節(jié)點，負(fù)責(zé)管理備份鏈路的預(yù)留帶寬資源共享信息。

服務(wù)帶寬S［e］：工作LSP上，傳輸數(shù)據(jù)流所需帶寬。

預(yù)留帶寬R ［e］：備份LSP上，為傳輸所保護(hù)的LSP的數(shù)據(jù)而預(yù)留的帶寬。

故障點F：在網(wǎng)絡(luò)中發(fā)生的故障，F(xiàn)∈（V∪E）。

Detour路徑保護(hù)方式對每條受保護(hù)路徑構(gòu)建單獨的LSP作為保護(hù)路徑，當(dāng)兩條不同的保護(hù)路徑同時經(jīng)過同一條鏈路時，在該鏈路上預(yù)留的帶寬是兩條保護(hù)路徑所需帶寬的總和。為了提高鏈路帶寬資源的利用率，本文對鏈路預(yù)留帶寬資源進(jìn)行共享處理。當(dāng)主備份LSP選定后，將沿著該備份LSP發(fā)送一個信令消息，該信令消息攜帶了受保護(hù)的鏈路與節(jié)點和所需預(yù)留帶寬的信息，LSP上的各個主節(jié)點收到信令消息后，按照式（1）為其所負(fù)責(zé)的鏈路預(yù)留相應(yīng)的帶寬。

式中：R——鏈路預(yù)留的帶寬，R ［i］——第i條備份LSP所需的預(yù)留帶寬，B——鏈路上工作LSP的使用帶寬。這樣，便可實現(xiàn)多條備份LSP共享一條鏈路上的預(yù)留資源，而不是進(jìn)行簡單的資源累加，能夠有效降低帶寬資源的消耗率。

2.3 多故障恢復(fù)算法步驟

多故障恢復(fù)算法采用Detour路徑保護(hù)方式，對RSVP Traffic Engineering（RSVP－TE）進(jìn)行擴(kuò)展以用作信令協(xié)議，其步驟如下：

（1）在一個MPLS網(wǎng)絡(luò)中，當(dāng)一條工作LSP的源節(jié)點收到建立工作LSP請求時，它使用CSPF算法或者根據(jù)顯式設(shè)置的路徑選擇一條到達(dá)目的節(jié)點的工作路徑。

（2）源節(jié)點沿工作LSP向目的節(jié)點發(fā)送一個PATH信令消息，目的節(jié)點收到后，沿工作LSP反向發(fā)送一個攜帶了預(yù)留資源信息的RESV信令消息以建立工作LSP。

（3）在工作LSP上的某個節(jié)點一旦收到RESV消息，立即利用CSPF算法或者顯式設(shè)置選擇最優(yōu)和次優(yōu)備份LSP，即主從備份LSP，為本節(jié)點相鄰的下游節(jié)點或者鏈路提供局部路徑保護(hù)。主備份LSP的建立遵循當(dāng)前的規(guī)范，在LSP上預(yù)留足夠的帶寬，提供有保證的恢復(fù)。然而，為了節(jié)省資源，將不對從備份LSP預(yù)先建立連接。

（4）該節(jié)點沿選擇的主備份LSP發(fā)送PATH消息以建立LSP，PATH消息中攜帶的信息有：工作LSP上該節(jié)點相鄰的下游節(jié)點與鏈路的信息、預(yù)留的鏈路帶寬、設(shè)置優(yōu)先級與保持優(yōu)先級。

（5）主備份LSP上的各個主節(jié)點收到PATH消息后，保存其中信息，并對所負(fù)責(zé)的鏈路的預(yù)留帶寬資源按照式（1）進(jìn)行共享管理。

（6）工作LSP上的各個節(jié)點收到RESV消息后，執(zhí)行步驟（3） －（5）以建立自己的備份LSP。當(dāng)RESV消息到達(dá)源節(jié)點時，算法工作結(jié)束。

2.4 多故障恢復(fù)算法的實現(xiàn)

如圖1所示的網(wǎng)絡(luò)來說明算法的實現(xiàn)過程。

圖1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)由7個節(jié)點和10條鏈路組成?，F(xiàn)在已有一條工作LSP1：R1→R2→R7，設(shè)置和保持優(yōu)先級為2，其中鏈路R1→R2，節(jié)點R2和鏈路R2→R7的主備份LSP分別為：R1→R3→R4→R2、R1→R3→R4→R7、R2→R4→R7；從備份LSP為：R1→R3→R5→R4→R2、R1→R3→R5→R6→R7、R2→R4→R6→R7。為方便敘述，本文假設(shè)各工作LSP上的鏈路使用帶寬和備份LSP上的鏈路預(yù)留帶寬都為1Mb，網(wǎng)絡(luò)中其他鏈路的預(yù)留帶寬都為0。某一時刻，節(jié)點R5收到消息，請求建立一條從R5到R7工作LSP，設(shè)置和保持優(yōu)先級是3，帶寬是1Mb。

首先，R5根據(jù)CSPF算法選擇一條工作LSP2：R5→R4→R7，然后沿著LSP2發(fā)送PATH消息。節(jié)點R7收到PATH消息后，立即沿LSP2反向發(fā)送RESV消息以建立LSP2。R4首先收到RESV消息，為LSP2預(yù)留帶寬B［47］＝1Mb，然后根據(jù)CSPF算法為鏈路R4→R7選擇了主備份LSP：R4→R6→R7，從備份LSP：R4→R2→R7，并沿著主備份LSP發(fā)送一個包含R4相鄰下游鏈路R4→R7，預(yù)留帶寬1Mb和保持與設(shè)置優(yōu)先級3信息的PATH消息。備份路徑上的主節(jié)點R6和R7收到PATH消息后，保存PATH消息中攜帶的信息，并根據(jù)式（1）來處理備份鏈路上的預(yù)留帶寬共享問題，得到R ［46］＝R ［67］＝1Mb。另外，因為LSP1的兩條備份LSP經(jīng)過鏈路R4→R7，所以根據(jù)式（1）有，R ［47］＝2Mb。當(dāng)節(jié)點R5收到RESV消息后，為LSP2預(yù)留帶寬B ［54］＝1Mb。然后根據(jù)CSPF算法為鏈路R5→R4和節(jié)點R4選擇了各自的主備份LSP：R5→R3→R4和R5→R6→R7，從備份LSP：R5→R6→R4和R5→R3→R1→R2→R7，并沿著從備份LSP發(fā)送包含鏈路R5→R4和節(jié)點R4的信息的PATH消息。主備份LSP上的主節(jié)點收到PATH消息后，保存PATH消息中攜帶的信息，為各自負(fù)責(zé)的鏈路預(yù)留帶寬，有：R ［53］＝R ［56］＝R ［34］＝R ［67］＝1Mb。至此，工作LSP2和其主備份LSP建立完畢，在鏈路R3→R4上只需預(yù)留1Mb的帶寬，而在傳統(tǒng)的快速重路由機(jī)制中則需預(yù)留2MB的帶寬。由此可見，對網(wǎng)絡(luò)進(jìn)行路徑保護(hù)時，新算法能夠有效減少備份鏈路預(yù)留帶寬資源的消耗，并且更好地應(yīng)對網(wǎng)絡(luò)的多故障情況。

3 仿真測試

本文在添加了 MNS和RSVP－TE－NS模塊的網(wǎng)絡(luò)模擬器NS2.26的基礎(chǔ)上進(jìn)行擴(kuò)展，實現(xiàn)仿真［13－15］，檢測新算法在備份帶寬資源消耗率和故障恢復(fù)時延兩方面性能的表現(xiàn)。

在測試備份帶寬資源消耗率時，應(yīng)用網(wǎng)絡(luò)模型G（V，E），∣V∣＝n，∣E∣＝m，選定網(wǎng)絡(luò)的尺寸n分別為｛10，15，20，25，30｝。實驗分別測試標(biāo)準(zhǔn)局部路徑保護(hù)（FRR）和新的多故障恢復(fù)算法（New）在選定的網(wǎng)絡(luò)尺寸中的備份資源消耗率，實驗結(jié)果如圖2所示。

圖2 不同網(wǎng)絡(luò)尺寸下的備份資源消耗率

由圖2可知，在不同的網(wǎng)絡(luò)尺寸下，新算法的備份帶寬資源消耗率更小，并且當(dāng)網(wǎng)絡(luò)尺寸增大時，由于有更多的備份LSP參與共享鏈路預(yù)留帶寬的原因，備份帶寬資源消耗率有所降低。

在測試故障恢復(fù)時延時，采用如圖3所示的網(wǎng)絡(luò)模型，設(shè)各條鏈路帶寬100Mbps，時延10ms。假設(shè)有兩條工作LSP：LSP1（R1→R2→R3→R4→R5）和LSP2（R10→R11→R8→R9），LSP1的設(shè)置和保持優(yōu)先級是2，LSP2的設(shè)置和保持優(yōu)先級是3，在網(wǎng)絡(luò)模型中運(yùn)行本文提出的多故障恢復(fù)算法。

圖3 實驗網(wǎng)絡(luò)模型

實驗中，模擬網(wǎng)絡(luò)模型在不同位置發(fā)生不同的故障，如表1所示。

表1 故障事件

記錄不同情況下的故障恢復(fù)時延，如圖4所示。

圖4 故障恢復(fù)時延

由圖4可知，在事件1－5中，由于只用到主備份LSP，無論發(fā)生單點故障還是多點故障，故障恢復(fù)時延都能夠控制在50ms以內(nèi)。然而，在事件6中，故障恢復(fù)時延明顯增加，這是因為工作LSP與主備份LSP同時發(fā)生故障，此時需要使用其從備份LSP，通過從備份LSP來轉(zhuǎn)發(fā)受故障影響的數(shù)據(jù)流。在事件7中，出現(xiàn)了搶占備份LSP的情況。此時，因為LSP1的設(shè)置優(yōu)先級更低，所以搶占鏈路R7→R3成功，LSP2只能建立預(yù)先計算好的從備份LSP，因此其恢復(fù)時延也有明顯增加。但是，由于從備份LSP是預(yù)先計算好的，不需要再耗費(fèi)時間來選擇備份LSP，因此，新算法仍然能夠維持較低的恢復(fù)時延，及時恢復(fù)受影響流量的轉(zhuǎn)發(fā)工作。

4 結(jié)束語

MPLS快速重路由按照保護(hù)的范圍可以分為局部路徑保護(hù)和全局路徑保護(hù)，在目前已提出的多故障恢復(fù)算法中，主要在全局路徑保護(hù)模型的基礎(chǔ)上進(jìn)行改進(jìn)。雖然降低了備份帶寬資源消耗率，但是故障恢復(fù)的有效性和快速性欠佳。本文提出的MPLS快速重路由多故障恢復(fù)算法，能夠在不同的備份LSP之間共享鏈路預(yù)留的帶寬資源，在具備局部路徑保護(hù)的快速恢復(fù)特點的同時降低了備份帶寬資源消耗率，并為工作LSP建立主從備份LSP。無論是在同一路徑上還是在不同路徑上發(fā)生多點故障，新算法都能夠快速有效地切換流量。

［1］Martin R，Menth M，Canbolat K.Capacity requirements for the facility backup option in MPLS fast reroute ［C］.Poznan，Poland：IEEE High Performance Switching and Routing，2006.

［2］Pan P，Swallow G，Atlas A.IETF RFC 4090，F(xiàn)ast reroute extensions to RSVP－TE for LSP tunnels ［S］.2005.

［3］Daniel W Hong，Choong Seon Hong，Woo Sung Kim.A segment－based protection scheme for MPLS network survivability［J］.Network Operations and Management Symposium，2006.

［4］LI Bin，CHEN Xiangdong.A failures recovery proposal for MPLS network［J］.Microelectronics and Computer，2007，24（1）：126－129（in Chinese）.［李彬，陳向東.一種 MPLS網(wǎng)絡(luò)的故障恢復(fù)方案 ［J］.微電子學(xué)與計算機(jī)，2007，24（1）：126－129.］

［5］Alex Raj，Oliver C Ibe.A survey of IP and multiprotocol label switching fast reroute schemes［J］.Computer Networks，2007，51（8）：1882－1907.

［6］WEI Gong，ZHANG Zhenzhen.MPLS－based distributed fast rerouting algorithm ［J］.Computer Engineering and Design，2007，28（2）：365－367（in Chinese）.［魏功，張貞貞.基于MPLS的分布式快速重路由算法 ［J］.計算機(jī)工程與設(shè)計，2007，28（2）：365－367.］

［7］XU Haibing.Fast reroute research and application based on traffic engineering with MPLS［D］.Chengdu：Southwest Jiaotong University，2009（in Chinese）.［徐海兵.MPLS流量工程快速重路由的研究與應(yīng)用 ［D］.成都：西南交通大學(xué)，2009.］

［8］Tacca M，Kai Wu，F(xiàn)ymagalli A.Local detection and recovery from multi－failure patterns in MPLS－TE Networks ［C］.Istanbul，Turkey：IEEE International Conference on Communications，，2006：658－663.

［9］REN Jinqiu，ZHANG Jianhui，WANG Binqiang.Fast recovery from multi－failure patterns in MPLS networks ［J］.Computer Engineering and Design，2008，29（15）：3861－3903（in Chinese）.［任金秋，張建輝，汪斌強(qiáng).支持多故障恢復(fù)的 MPLS快速重路由 ［J］.計 算 機(jī) 工 程 與 設(shè) 計，2008，29（15）：3861－3903.］

［10］Guichard J.Definitive MPLS network designs［M］.Beijing：Post and Telecom Press，2007（in Chinese）. ［Guichard J.MPLS網(wǎng)絡(luò)設(shè)計權(quán)威指南 ［M］.陳武，譯.北京：人民郵電出版社，2007.］

［11］Luc De Ghein.MPLS fundamentals［M］.Beijing：Post and Telecom Press，2008（in Chinese）.［Luc De Ghein.MPLS技術(shù)架構(gòu) ［M］.陳麒帆，譯.北京：人民郵電出版社，2008.］

［12］PAN Xianzhi，LI Xiangli，QIU Baozhi.Rerouting and forwarding mechanism priority－based in MPLS networks［J］.Microelectronics and Computer，2008，25（3）：149－151（in Chinese）.［潘顯志，李向麗，邱寶志.基于優(yōu)先級的MPLS重路由轉(zhuǎn)發(fā)機(jī)制［J］.微電子學(xué)與計算機(jī)，2008，25（3）：149－151.］

［13］Adami D，Callegari C，Giordano S，et al.Signalling protocols in DiffServ－aware MPLS networks：Design and implementation of RSVP－TE network simulator［C］.IEEE GLOBECOM proceedings，2005.

［14］Adami D，Callegari C，Ceccarelli D，et al.Design and development of MPLS－based recovery strategies in NS2 ［C］.IEEE GLOBECOM Proceedings，2006.

［15］CHEN Xuefei，LI Peng，HUANG He.Research on MPLS recovery mechanism and simulation ［J］.Computer Engineering and Design，2008，29（16）：4189－4193（in Chinese）.［陳雪非，李蓬，黃河.MPLS故障恢復(fù)機(jī)制及其仿真研究 ［J］.計算機(jī)工程與設(shè)計，2008，29（16）：4189－4193.］