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

楊振啟，何文庭，楊云雪

（南京信息工程大學 計算機與軟件學院，江蘇 南京210044）

0 引 言

1 MPLS快速重路由技術

MPLS快速重路由技術利用預先建立的備份路徑來應對網絡出現的故障，根據備份路徑的保護方式，主要有Detour和Bypass兩種路徑保護方式［10］。

Detour路徑保護方式為每條工作路徑建立單獨的LSP作為備份路徑，稱作Detour LSP。Detour方式資源消耗較大，但是能夠快速對故障進行恢復，因此只適用對網絡的關鍵路徑進行保護。

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

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

2 多故障恢復算法

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

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

2.1 算法思想

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

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

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

2.2 鏈路帶寬資源共享機制

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

網絡模型圖G（V，E）：有向模型圖，V代表節點集合，E代表鏈路集合。

工作LSP：網絡正常情況下用于傳輸數據流的LSP。

主備份LSP：網絡發生故障時，首先采用的備份LSP，已預先建立。

從備份LSP：網絡發生故障，主備份LSP失效時，另外采用的備份LSP，預先計算好，但未建立。

主節點：備份路徑上有流量流出的節點，負責管理備份鏈路的預留帶寬資源共享信息。

服務帶寬S［e］：工作LSP上，傳輸數據流所需帶寬。

預留帶寬R ［e］：備份LSP上，為傳輸所保護的LSP的數據而預留的帶寬。

故障點F：在網絡中發生的故障，F∈（V∪E）。

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

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

2.3 多故障恢復算法步驟

多故障恢復算法采用Detour路徑保護方式，對RSVP Traffic Engineering（RSVP－TE）進行擴展以用作信令協議，其步驟如下：

（1）在一個MPLS網絡中，當一條工作LSP的源節點收到建立工作LSP請求時，它使用CSPF算法或者根據顯式設置的路徑選擇一條到達目的節點的工作路徑。

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

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

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

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

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

2.4 多故障恢復算法的實現

如圖1所示的網絡來說明算法的實現過程。

圖1 網絡模型

網絡由7個節點和10條鏈路組成。現在已有一條工作LSP1：R1→R2→R7，設置和保持優先級為2，其中鏈路R1→R2，節點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。為方便敘述，本文假設各工作LSP上的鏈路使用帶寬和備份LSP上的鏈路預留帶寬都為1Mb，網絡中其他鏈路的預留帶寬都為0。某一時刻，節點R5收到消息，請求建立一條從R5到R7工作LSP，設置和保持優先級是3，帶寬是1Mb。

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

3 仿真測試

本文在添加了 MNS和RSVP－TE－NS模塊的網絡模擬器NS2.26的基礎上進行擴展，實現仿真［13－15］，檢測新算法在備份帶寬資源消耗率和故障恢復時延兩方面性能的表現。

在測試備份帶寬資源消耗率時，應用網絡模型G（V，E），∣V∣＝n，∣E∣＝m，選定網絡的尺寸n分別為｛10，15，20，25，30｝。實驗分別測試標準局部路徑保護（FRR）和新的多故障恢復算法（New）在選定的網絡尺寸中的備份資源消耗率，實驗結果如圖2所示。

圖2 不同網絡尺寸下的備份資源消耗率

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

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

圖3 實驗網絡模型

實驗中，模擬網絡模型在不同位置發生不同的故障，如表1所示。

表1 故障事件

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

圖4 故障恢復時延

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

4 結束語

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

［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，Fast 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網絡的故障恢復方案 ［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］.計算機工程與設計，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流量工程快速重路由的研究與應用 ［D］.成都：西南交通大學，2009.］

［8］Tacca M，Kai Wu，Fymagalli 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）.［任金秋，張建輝，汪斌強.支持多故障恢復的 MPLS快速重路由 ［J］.計 算 機 工 程 與 設 計，2008，29（15）：3861－3903.］

［10］Guichard J.Definitive MPLS network designs［M］.Beijing：Post and Telecom Press，2007（in Chinese）. ［Guichard J.MPLS網絡設計權威指南 ［M］.陳武，譯.北京：人民郵電出版社，2007.］

［11］Luc De Ghein.MPLS fundamentals［M］.Beijing：Post and Telecom Press，2008（in Chinese）.［Luc De Ghein.MPLS技術架構 ［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）.［潘顯志，李向麗，邱寶志.基于優先級的MPLS重路由轉發機制［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故障恢復機制及其仿真研究 ［J］.計算機工程與設計，2008，29（16）：4189－4193.］