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.］