服务质量约束的链路故障恢复方法

摘要

本发明涉及一种服务质量约束的链路故障恢复方法，首先建立了一种服务质量约束的链路故障多备份路径恢复数学模型，优化目标为最小化网络中所有链路因故障造成的重路由流量中断量之和，在确保业务服务质量的条件下最大程度地重路由流量，最后采用启发式迭代算法LFR‑QoS对建立的链路故障多备份路径恢复数学模型进行求解，经过单条备份路径拼接、备份路径选择2个子算法步骤后，得到了既考虑服务质量QoS约束又考虑链路故障恢复率的链路多条备份路径优化结果，实现了受损链路的有效快速修复，并克服了SelectBP链路故障恢复算法存在的复杂度高、修改拓扑信息等问题。

主权项

一种基于LFR‑QoS算法的链路故障多备份路径恢复优化方法，其特征在于步骤如下：步骤1：建立基于多备份路径策略的概率关联故障模型设R为共享风险链路组SRLG事件集合，当任意事件r∈R发生时，故障发生概率不为0的链路集合构成事件r的概率共享风险链路组PSRLG，如式(1)：r_PSRLG＝{e_i,j∈E:p_r(i,j)≠0}    (1)其中，p_r(i,j)为SRLG事件r发生时链路e_i,j发生故障的概率；用p_r表示事件r发生概率，链路e_u,v和e_i,j存在故障关联时，各自发生故障的概率分别用p_u,v和p_i,j表示，如式(2)与式(3)：p_u,v＝p_r·p_r(u,v)    (2)p_i,j＝p_r·p_r(i,j)    (3)根据(2)式和(3)式，只有当p_r≠0时p_u,v和p_i,j不为0，链路e_u,v和e_i,j存在故障关联时各自发生故障的概率同时受到事件r的影响；步骤2：给出优化目标函数TD$TD={\Sigma }_{e_{i,j}\in E}\left({\Sigma }_{k=1}^N\right(1-{\Pi }_{e_{u,v}\in S\left(B_{i,j}^k\right)}\left(1-p_r·p_r\left(u,v\right)\right))r_{i,j}^k+p_r·p_r(i,j)\left(l_{i,j}-{\Sigma }_{k=1}^N{r}_{i,j}^k\right))$其中，任意链路e_i,j∈E，表示链路e_i,j的第k条备份路径，表示构成的所有链路集合，链路e_u,v代表中任意元素，表示第k条备份路径为链路e_i,j保留的带宽，l_i,j表示无故障时其流量负载，N为备份路径的总数量；步骤3：建立链路故障恢复模型1)变量表示第k条备份路径为链路e_i,j保留的带宽；若e_u,v是构成的某一条链路则置为1；否则为0；2)目标函数Min TD3)约束条件①流守恒约束$\begin{array}{cc}{\Sigma }_{\forall u:e_{v,u}\in E}{f}_{e_{v,u}}^h\left(e_{i,j}\right)-{\Sigma }_{\forall u:e_{u,v}\in E}{f}_{e_{u,v}}^{h-1}\left(e_{i,j}\right)=0& \forall e_{i,j}\in E,\forall v\in V/\left\{i,j\right\}\end{array}---\left(10\right)$约束(10)是网络中节点流守恒限制，表示链路e_i,j故障时，通过h‑1跳数备份路径进入任意节点v∈V/{i,j}的所有流量之和等于流出该节点的经过h跳数的所有备份路径流量之和，链路e_i,j的端节点不满足此约束，其中表示链路e_i,j故障时，从节点i到u经过h跳数的所有备份路径重路由流量之和；②容量约束${\Sigma }_{k=1}^N{r}_{i,j}^k\le l_{i,j}---\left(11\right)$${\Sigma }_{e_{i,j}\in E}{f}_{e_{u,v}}\left(e_{i,j}\right)\le c_{u,v}-l_{u,v}---\left(12\right)$式(11)为重路由流量约束，表示链路e_i,j的所有备份路径重路由流量最大是其负载；式(12)为链路带宽容量约束，表示每条链路承载的重路由流量不应超过其可用带宽；其中表示链路e_i,j故障时分配给链路e_u,v的流量，其值用式(13)表示；$f_{e_{u,v}}\left(e_{i,j}\right)={\Sigma }_{k=1}^N{x}_{u,v}^{i,j,k}{r}_{i,j}^k---\left(13\right)$③变量约束1≤k≤N,0≤h≤H    (15)$r_{i,j}^k\ge 0---\left(16\right)$$x_{u,v}^{i,j,k}\in \{0,1\}---\left(17\right)$式(15)表示每条链路最多有N条备份路径，每条备份路径的时延最大为H跳；式(16)表示备份路径预留带宽非负；满足整数约束条件式(17)；步骤4：采用启发式迭代算法LFR‑QoS算法求解步骤3建立的链路故障恢复模型：LFR‑QoS算法由单条备份路径拼接和备份路径选择2个子算法构成，其中单条备份路径拼接子算法具体包括以下步骤：4a：采用k最短路径法计算链路e_i,j的最短备份路径集合Ω(BP_i,j)，且存在可用的带宽并满足时延约束；4b：计算Ω(BP_i,j)中的每条最短备份路径BP的重路由流量ΔTD_i,j；4c：将ΔTD_i,j值最大的最短备份路径BP作为链路e_i,j的第k条备份路径；步骤5：采用备份路径选择子算法为每一条链路构造最多N条备份路径，具体包括以下步骤：5a：计算每一条链路e_i,j的优先级LP_i,j＝p_i,jl_i,j；5b：按照LP_i,j值从大到小顺序对e_i,j排序；5c：对于每一条链路e_i,j，从第一条备份路径开始，调用单条备份路径拼接子算法构造第k条备份路径直到k＝N或者构造失败。