QoS约束的链路故障多备份路径恢复算法

崔文岩　孟相如　杨欢欢　李纪真　陈天平　康巧燕（空军工程大学信息与导航学院西安710077）（清华大学电子工程系北京100084）



QoS约束的链路故障多备份路径恢复算法

崔文岩*①孟相如①杨欢欢①②李纪真①陈天平①康巧燕①①
①（空军工程大学信息与导航学院西安710077）
②（清华大学电子工程系北京100084）

链路故障的恢复，不仅仅是选择一条连通的备份路径问题，还应考虑网络业务故障恢复过程中的QoS需求。针对此问题，该文基于多备份路径策略，构建概率关联故障模型和重路由流量丢弃量优化目标。并基于该优化目标，以业务的QoS需求为约束，建立故障恢复问题的数学模型，提出一种QoS约束的链路故障多备份路径恢复算法。该算法构建单条备份路径时，以最大程度地减少重路由流量丢弃为目标，并采用改进的QoS约束的k最短路径法进行拼接，且给与高优先级链路更多的保护资源。此外还证明了算法的正确性并分析了时间空间复杂度。在NS2环境下的仿真结果表明，该算法显著提升了链路故障恢复率和重路由流量QoS满足率，且QoS约束条件越强，相较于其它算法优势越明显。

链路故障恢复；多备份路径；QoS；重路由

1　引言

随着通信技术的快速发展，网络链路带宽得到不断扩充。目前全球至少有来自20多个国家的53个运营商已经部署或正在考虑部署400 GB/s的骨干网络［1］。高速骨干网链路即使短暂的故障也会造成大量的数据包丢弃，严重影响通信质量。根据对ISP的观察，骨干网链路一年内大约有30%的概率会出现故障［2］，表明链路故障是网络中较为普遍的现象。因此，加快故障的恢复速度，降低故障造成的业务丢弃已成为当前研究亟待解决的问题。

网络故障主要表现为链路故障，链路故障恢复策略可分为主动式和被动式两种［3，4］。被动式策略在网络故障后动态自适应地进行全网资源重分配，但路由重新收敛花费较多的时间而不可接受。因此目前故障快速恢复研究以主动式策略为主，通过提前对网络进行资源规划和预留，使得故障时能迅速切换，如基于多拓扑［5］和基于备份路径的故障恢复技术。多拓扑技术需要配置多个拓扑子层，路由存储消耗大；基于备份路径的故障恢复技术提供端到端路径重路由，在全局范围内进行流量分配，易于基于现有协议实现。因此，备份路径技术是当前故障恢复领域研究的热点［611］-。

故障恢复的本质在于维持故障链路承载流量的传输，因此应从流量持续传输角度解决故障恢复问题。大部分故障恢复工作集中在如何选择可靠备份路径上，且一般利用单一备份路径进行故障恢复。然而当流量超出备份路径可用带宽时，单一备份路径无法满足故障恢复的要求。受到这一启发，文献［8］将多路径技术引入到故障恢复中，采用多条备份路径共同承担流量，减少了流量的丢弃。在此基础上，文献［9］提出一种结合故障恢复与流量工程的网络结构，在多路径故障恢复基础上进行流量工程优化，其目的是进行负载均衡，且假设备份路径可用带宽满足故障恢复需求。文献［10］考虑了不同故障状况，通过将重路由流量分配给有跳数限制的多条备份路径，在网络投入运行之前就设计好应对各种故障场景的最低容量备份网络。文献［11］提出一种跨层故障恢复模型，考虑了备份链路的可靠性，提升了故障恢复成功率。然而，上述故障恢复算法大都以最大化重路由为目标，未考虑恢复后的流量是否满足用户的需求。但是经由备份路径的重路由流量即使最终传输成功，由于时延超时、链路过载等原因，也无法满足业务的服务质量需求（Quality of Service，QoS），属于无效流量。虽然文献［12］提出了一种满足QoS约束的自适应调整的多路径路由，但未考虑故障恢复问题。因此，目前已提出的大部分链路故障恢复算法不能很好地确保业务的服务质量。

为此，本文针对QoS约束下的链路故障恢复问题进行研究，即在网络可用带宽和业务时延需求约束下进行最大化重路由流量问题求解。首先基于多备份路径策略建立概率关联故障模型和重路由流量丢弃优化目标，并构建QoS约束的故障多备份路径恢复问题的数学优化模型。然后，设计QoS约束的链路故障多备份路径恢复算法（Multiple backup Paths Recovery for link failure w ith QoS constrain algorithm，MPR-QoS）对此问题进行求解。MPR-QoS算法在构建单条备份路径时，利用改进的QoS约束的k最短路径法进行拼接，并以最大化减少重路由流量丢弃为目标，且分配给高优先级链路更多的保护资源。此外还证明了算法的正确性并对时间空间复杂度进行了分析。最后，在NS2仿真环境下从故障恢复率、重路由流量QoS满足率、链路过载率和算法运行时间等方面验证了本文算法的优越性。

2　问题描述

2.1备份路径策略

备份路径策略是基于备份路径故障恢复方法的关键问题［8］，对故障恢复效果有较大影响。虽然采用更多的备份路径可以减少流量的丢弃，但是如果备份路径数量过大会大大增加配置复杂度和存储开销，并且网络对节点对之间可以设置的备份路径数量有严格的限制，为此，本文设定每条链路最多拥有N条备份路径。文献［9］指出拥塞网络的队列时延随跳数呈指数规律增加，且光网络中的信号质量随着路径跳数的增加而迅速下降，因此为支撑QoS需求，对备份路径施加跳数限制是非常有必要的，文中限制备份路径最大跳数为H。网络拓扑利用有权无向图G（V，E）表示，其中V和E分别表示路由器节点和链路集合。

2.2概率关联故障模型

当前的链路故障恢复算法大多是针对独立故障的，而事实上有时候链路故障并不是完全独立的，比如当底层光纤链路故障时，由其承载的多条逻辑链路可能会同时失效，即链路故障之间存在概率关联。共享风险链路组（Shared Risk Link Group，SRLG）模型［13］用来表示一组共享同一风险的链路集合，当SRLG中的一条链路失效时，该组中其它链路以1的概率出现失效。但实际上关联故障并非100%绝对关联，拥有关联故障的两条链路中的一条链路发生故障时，另一条链路只是以某一概率发生故障。为此，我们给出了概率共享风险链路组概念，在传统的SRLG模型中加入故障关联概率来表示拥有一定概率关联的故障模型。

定义1概率共享风险链路组（Probabilistically Shared Risk Link G roup，PSRLG），设R为SRLG事件集合，当任意事件r R∈发生时，故障发生概率不为0的链路集合构成事件r的PSRLG，如式（1）所示。

用rp表示事件r发生概率，链路和存在故障关联时，各自发生故障的概率分别用和表示。

2.3优化目标

式（4）中假设N条备份路径均可用，根据前面分析，链路之间存在概率关联故障，那么链路故障时也可能同时发生故障，如果发生故障，其上承载的重路由流量被丢弃。利用表示链路故障概率，并设链路故障时的故障概率为则考虑备份路径可靠性时链路故障下的重路由流量丢弃量可用式（5）表示。

那么，网络中所有链路因故障造成的重路由流量丢弃量之和可以表示为

本文算法的设计目标就是在业务QoS需求约束下，使得式（8）值最小，式（8）即为本文的优化目标。

3　故障多备份路径恢复问题的数学模型

本节以最小化重路由流量丢弃为目标，以业务QoS需求为约束，利用多备份路径技术，对故障恢复问题进行混合整数线性规划（M ixed Integer Linear Program，M ILP）建模。

（2）目标函数：

本文的目标函数是最小化全网范围内的重路由流量丢弃量。它包含两部分，一是超出所有备份路径重路由能力部分，二是因备份路径自身故障而丢弃部分。

（3）约束条件：

（a）流守恒约束：

（b）容量约束：

式（11）为重路由流量约束，式（12）为链路带宽容量约束。重路由流量约束表示链路的所有备份路径重路由流量最大是其负载。链路带宽容量约束表示每条链路承载的重路由流量不应超过其可用带宽。其中表示链路故障时分配给链路的流量，其值可用式（13）表示。

feuv）由从节点i到u经过不同跳数的所有备份路径重路由流量之和构成，如式（14）所示，式（13）与式（14）是等价关系。

（c）变量约束：

式（15）表示每条链路最多有N条备份路径，每条备份路径的时延最大为H跳。式（16）表示备份路径预留带宽非负。满足整数约束条件式（17），因此本模型属于非确定性多项式时间难问题（NP-hard）。

4　 MPR-QoS算法设计

链路故障恢复问题的M ILP模型是NP-hard问题，虽然可以利用单纯形法等传统线性规划方法求解，但随着问题规模的增加，计算时间复杂度较高，并不适用于大规模网络故障恢复问题的求解。因此，本节设计MPR-QoS算法对QoS约束下的故障多备份路径恢复问题进行求解。该算法由单条备份路径拼接和备份路径选择两个子算法构成，其求解目标是在QoS约束下通过为网络中每条链路选择最多N条备份路径，并合理分配资源使得全网重路由流量丢弃量最小。

4.1单条备份路径拼接链路的备份路径选择是逐条进行的，单条备份路径的选择类似于计算最短路径的k最短路径算法，从节点开始，通过逐条添加链路来扩充备份路径。假设链路已有1k-条备份路径，额外添加一条备份路径减少的流量丢弃量可用式（18）表示。

MPR-QoS算法在进行单条备份路径拼接时，目的是要构造一条使最大的。以链路的第k条备份路径的拼接算法为例给出表1所示的单条备份路径拼接算法。单条备份路径拼接采用改进的k最短路径法，使之保证每一条备份路径存在可用的带宽且满足业务时延约束，选取最短备份路径集合最大的最短备份路径作为链路的第k条备份路径。

表1　 M PR-QoS的单条备份路径拼接算法（链路ije，第k条备份路径拼接算法）

4.2备份路径选择由于承载较多流量负载的链路在故障时重路由流量较多，很可能因为网络中没有足够多的带宽资源而造成重路由流量的丢弃，而高故障概率链路更易发生故障，因此本文利用链路的流量负载与故障概率之积来确定其受保护优先级，定义链路的优先级如式（19）。

MPR-QoS算法在备份路径选择阶段的算法是一种启发式的多轮迭代算法，如表2所示。该算法首先按照承载流量负载大小和故障概率计算链路的优先级LP，并根据LP值的大小依次为每一条链路构造最多N条备份路径，构建每一条备份路径的同时，更新链路的剩余重路由流量负载和网络带宽资源。

相比较已有的基于备份路径的故障恢复算法［14，15］，MPR-QoS算法的优势在于，一是通过为每条链路确定优先级，使得高优先级链路获得更多的保护资源，降低了全网范围内因故障造成的流量负载的丢弃；二是在每一轮迭代构造单条备份路径时，不仅考虑可用带宽资源，还考虑备份路径的时延，在业务QoS约束下，确保每一条新增的备份路径均最大程度地减少重路由流量的丢弃。最终，MPR-QoS算法既满足了业务QoS约束，又最大程度地保证了故障链路流量负载的重路由。

表2　M PR-QoS的备份路径选择算法

4.3MPR-QoS正确性证明

定理1在给定的网络拓扑约束下，假设k最短路径算法能生成k条最短路径，那么MPR-QoS的单条备份路径拼接算法能生成满足可用带宽和业务时延约束的备份路径集合Ω（BPi，j）。

证明考察4.1节算法描述可知单条备份路径拼接算法对k最短路径算法的扩展主要在两个方面：（1）在k条最短路径构建过程中增加跳数H限制，改变了k条最短路径生成的判断条件；（2）在k条最短路径生成完毕后增加可用带宽约束，保留满足可用带宽备份路径至Ω（BPi，j）。k最短路径算法可以通过构建包含k个最短路径的k最短路径树Tk，树Tk的根节点为i，叶子节点为终节点j的k个备份。为此，单条备份路径拼接算法基于k最短路径树Tk实现［16］。

下面采用数学归纳法证明。

当k=1时，生成树Tk只包含1条最短路径。如果该最短路径构建过程中H超时，得到Ω（BPi，j）为空；如果H时延满足但不存在可用带宽，同样得到Ω（BPi，j）为空；如果2个条件均满足，得到Ω（BPi，j）包含一个元素。命题成立。

假设当k=n时命题成立。即单条备份路径拼接算法能生成满足可用带宽和时延约束的备份路径集。

当k=n+1时，讨论第n+1条备份路径生成的情况，即利用已求得的p1，p2，…，pn求取pn+1。

我们利用偏离路径概念构建Tk。假设p=（m1，m2，…，）和q=（n1，n2，…，ns）分别为i到j的两条路径，如果有满足以下约束的x，

单条备份路径拼接算法相比基于最短偏离路径的pn+1生成算法，主要改变发生在遍历mt寻找至节点j最短路径的过程，此过程加入了时延及带宽约束。每一个节点mt至j的最短路径可以采用Dijkstra算法求解，加入时延及带宽约束后得到的节点mt至j的最短路径集合是未加约束的子集，即缩小了偏离节点范围，得到的mt至j的最短路径可能是次最短路径；由于k=n时命题成立，pn上从i到mt的路径是满足时延及带宽约束的最短路径，将i到mt与mt至j的最短路径拼接即可得到pn+1的候选路径；最后选取可用带宽最大的路径作为pn+1。

则当k=n+1时命题成立。

通过以上证明可知定理1得证。

MPR-QoS备份路径选择算法通过多轮迭代运算完成，主要嵌套单条备份路径拼接算法实现，本质上是迭代运算过程。因此，在单条备份路径拼接算法可以正确执行的情况下，备份路径选择算法可以正确执行。另外，MPR-QoS算法基于k最短路径算法实现，同样可以保证产生的路径是无环路的。

证毕

4.4MPR-QoS时间、空间复杂度分析

MPR-QoS算法的单条备份路径拼接过程类似于k最短路径算法，因此拥有同样的计算复杂度O（E+V）lg（V）。由于网络中共有E条链路，每条链路最多有N条备份路径，则MPR-QoS算法的计算复杂度为O（E+V）lg（V）N E。

MPR-QoS算法采用4个1维向量存储算法运行产生的数据：1个向量存储每条链路的最短备份路径集合Ω（BPi，j），路径可由一系列节点描述，单条路径的存储空间不会超过V，则该向量存储空间最多为1个向量作为链表存储单条备份路径拼接结果，所需存储空间最多为1个向量存储链路优先级排序结果，存储空间为；1个向量存储链路的备份路径构造结果，存储空间为因此，MPR-QoS算法的空间复杂度为

5　性能评估与分析

NS2作为主流的网络仿真工具，可以有效地实现网络协议和算法的正确性验证和性能分析。本文以此为仿真平台，对MPR-QoS算法和已有链路故障恢复算法进行对比仿真，并从链路故障恢复能力、重路由流量QoS满足率、链路过载率和算法运行时间4个方面讨论MPR-QoS算法的性能。

5.1实验环境设置

实验拓扑采用Tier-1骨干网络［17］，仿真参数设置如表3。计算链路最短备份路径的k最短路径算法中的k值取5。

链路故障场景做以下设置。共配置9个共享风险链路组（SRLG）事件，各事件包含共享风险链路2～5条，令SRLG事件发生故障概率（式（2）中的rp）范围为［0.05%，0.5%］，各SRLG事件故障下其组内链路的条件概率范围为［0.3，1］。在独立故障链路中取10%作为高概率故障链路，其故障概率范围为［0.1%，0.5%］，其余链路的故障概率范围为［0.01%，0.1%］。共配置50组故障概率场景，针对每组故障概率场景在不同的随机数种子（seed）下进行50次故障恢复仿真。每次仿真中随机选择1条链路作为故障链路，若该链路包含于某概率共享风险链路组中，则按照条件概率选择并发的关联故障链路，并取实验结果的平均值作为最终仿真结果。

表3　仿真参数设置

对比算法描述如下：SelectBP［11］算法考虑备份路径的可用带宽约束，不考虑备份路径时延，以最小化重路由流量丢弃量为目标；R3［8］算法以多重故障下的网络无拥塞为目标；FR-TE［9］算法以故障恢复过程的全网范围内负载均衡最优化为目标。

5.2性能分析

本文从故障恢复率、重路由流量QoS满足率、链路过载率和算法运行时间4个方面对算法进行性能比较，仿真结果表明MPR-QoS算法具有以下优势。

（1）提升了故障恢复率：故障恢复率是完全恢复的故障链路所占比例，算法MPR-QoS考虑备份路径数目N分别为2，3，4三种情况，算法对比在2种不同时敏业务下进行，结果如图1所示。由图可知，MPR-QoS算法随着备份路径数N的增大，故障恢复率呈逐渐上升趋势，且在高时敏业务时提升了约17.5%，因此N值可以设置的大一些，但是备份路径数过多会增加路由器的工作量，使得算法实用性较差，且网络对于可以设置的备份路径数量有严格的限制，因此综合考虑，将MPR-QoS的N值设为4。N为4时，相比较其它故障恢复算法，低时敏业务时MPR-QoS算法故障恢复率最多提升了35.1%，高时敏业务时MPR-QoS算法故障恢复率最多提升了48.0%。仍以备份路径取4为例，相比低时敏业务需求，高时敏业务需求时，MPR-QoS算法故障恢复率下降了约2.8%，而其它故障恢复算法故障恢复率最多下降了约19.9%，表明业务时敏需求的增强对MPR-QoS算法的故障恢复率影响更小。主要原因是MPR-QoS算法采用概率关联故障模型只挑选可靠的备份路径，且优先保护高优先级链路，使得易发生故障和高负载链路获得更多的保护资源。由于缺乏时延限制，SelectBP，FR-TE和R 3算法在高时敏业务下，故障恢复效果较差，受业务时敏性影响大，FR-TE和R 3算法没有考虑备份路径的可靠性问题，故障恢复率较低。

（2）显著提升了链路故障时的重路由流量QoS满足率，且网络业务时敏性越强，算法优势越明显：重路由流量QoS满足率是满足业务QoS需求的重路由流量占总重路由流量的比例，不同业务时敏需求下4种算法的重路由流量QoS满足率的仿真结果如图2所示，其中业务时敏需求分布范围为［50ms，275 ms］，与现实网络中的大部分业务时延需求相一致［9］，设置MPR-QoS算法的备份路径H值与业务时敏需求相匹配，N值取4。从图中可以看出，MPR-QoS算法的重路由流量QoS满足率始终维持在98%以上，基本不受业务时敏需求的影响，而SelectBP，FR-TE和R3算法随着业务时敏需求的增强，重路由流量QoS满足率迅速下降，FR-TE算法在业务需求50ms时相比275 ms时，重路由流量QoS满足率下降量达54.8%。主要原因是MPR-QoS算法考虑了QoS约束，而其它3种算法缺乏这一限制，当业务时延需求增强时，满足QoS需求的流量逐渐下降，严重影响业务传输质量。

（3）避免了链路过载情况的发生：链路过载率是因重路由过载的链路占所有链路的比例。由于运营商一般将链路利用率控制在40%以内［11］，本文仿真分布范围为［5%，40%］链路利用率时链路过载情况，图3为加载低时敏业务时的仿真结果。由图中可以看出，MPR-QoS和SelectBP算法链路过载率始终保持在5%以内，与链路利用率无关；FR-TE和R 3算法随着链路利用率的升高，链路出现大范围的过载，当链路利用率达到40%时，2种算法的链路过载率超过45%，大大降低了故障恢复性能。主要原因是MPR-QoS和SelectBP算法仅采用具有可用带宽的链路来恢复故障，且严格控制备份路径的重路由流量，最大程度地避免了链路过载情况的发生。

（4）降低了链路故障恢复问题的求解时间：表4表示4种算法求解链路故障恢复问题的平均运行时间。从表中可以看出，相较于MPR-QoS和SelectBP算法，FR-TE和R3算法时间开销较大，极大地影响链路故障恢复时配置保护资源所需的时间。主要原因是MPR-QoS和SelectBP算法采用了多轮启发式算法，大大缩短了问题求解时间，而FR-TE和R3算法采用传统的线性规划方法求解约束优化问题，求解时间随着网络规模的增长呈指数规律增加。

表4　算法运行时间（s）

6　结束语

本文研究了具有QoS约束的链路故障恢复问题。以往的故障恢复算法目标是寻找可连通的备份路径，并尽最大努力地保证故障链路的重路由，忽略了业务的QoS需求，特别对于高时延敏感业务，重路由后的流量中无效流量占很大的比例。针对此问题，本文在网络可用带宽资源和业务时延约束下最大化重路由流量，提出故障概率关联的多备份路径模型，并将故障恢复问题建模为M ILP模型，利用提出的MPR-QoS算法进行求解。此外通过数学推导证明提出的算法理论上是正确的。仿真结果表明，与传统的故障恢复算法相比，MPR-QoS算法提升了故障恢复率，避免了链路过载现象的发生，降低了运行时间，显著地提升了链路故障时的重路由流量QoS满足率，且网络业务时延敏感需求越强，算法优势就越明显。

图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，France，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网络的快速故障恢复［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］齐宁，汪斌强，王志明.可重构服务承载网容错构建算法研究［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］王禹，王振兴，张连成.一种基于结构化备份子图的路由系统失效恢复方法［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］周灵，王建新.路径节点驱动的低代价最短路径树算法［J］.计算机研究与发展，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年生，博士生，研究方向为信息系统网络抗毁技术.

孟相如：男，1963年生，博士，教授，研究方向为宽带通信网.

杨欢欢：男，1988年生，博士生，研究方向为下一代通信技术.

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；网络出版：2016-05-09

崔文岩cw y_edu@163.com

国家自然科学基金（61201209，61401499），陕西省自然科学基金（2013JQ 8013，2015JM 6340）