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

崔文岩; 孟相如; 杨欢欢; 李纪真; 陈天平; 康巧燕

doi:10.11999/JEIT151230

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

doi: 10.11999/JEIT151230

1.
(空军工程大学信息与导航学院西安 710077) ②(清华大学电子工程系北京 100084)

基金项目:

国家自然科学基金(61201209, 61401499)，陕西省自然科学基金(2013JQ8013，2015JM6340)

计量
- 文章访问数: 1400
- HTML全文浏览量: 133
- PDF下载量: 452
- 被引次数: 0
出版历程
- 收稿日期: 2015-11-03
- 修回日期: 2016-03-03
- 刊出日期: 2016-08-19

Link Failure Recovery Algorithm Based on Multiple Backup Paths with QoS Constraint

1.
(College of Information and Navigation, Air Force Engineering University, Xi&rsquo

Funds:

The National Natural Science Foundation of China (61201209, 61401499), Natural Science Foundation of Shaanxi Province (2013JQ8013, 2015JM6340)

摘要

摘要: 链路故障的恢复，不仅仅是选择一条连通的备份路径问题，还应考虑网络业务故障恢复过程中的QoS需求。针对此问题，该文基于多备份路径策略，构建概率关联故障模型和重路由流量丢弃量优化目标。并基于该优化目标，以业务的QoS需求为约束，建立故障恢复问题的数学模型，提出一种QoS约束的链路故障多备份路径恢复算法。该算法构建单条备份路径时，以最大程度地减少重路由流量丢弃为目标，并采用改进的QoS约束的k最短路径法进行拼接，且给与高优先级链路更多的保护资源。此外还证明了算法的正确性并分析了时间空间复杂度。在NS2环境下的仿真结果表明，该算法显著提升了链路故障恢复率和重路由流量QoS满足率，且QoS约束条件越强，相较于其它算法优势越明显。
- 链路故障恢复 /
- 多备份路径 /
- QoS /
- 重路由
Abstract: 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 should be also taken into account. The probabilistically correlated failure model and rerouting traffic disruption optimization target are built based on multiple backup paths strategy. Furthermore, a mathematical model of the failure recovery problem is modeled, which takes the minimum rerouting traffic disruption as the target and the QoS requirement as the constrain, and a link failure recovery algorithm based on multiple backup paths with QoS constrain is proposed. The proposed algorithm takes reducing rerouting traffic disruption farthest as the target and adopts the improved k shortest path algorithm with QoS constrain to splice the single backup path, and it gives the links more protection resource with high priority. Moreover, the correctness of the proposed algorithm is proved, and the time complex and the space complex are computed. The simulation results under NS2 show that the proposed algorithm significantly improves link failure recovery rate and the QoS satisfaction rate of the rerouting traffic, and it performs better when the QoS constrain is stronger.
- Link failure recovery /
- Multiple backup paths /
- QoS /
- Reroute

HTML全文

参考文献(21)

WELLBROCK G and XIA T J. How will optical transport deal with future network traffic growth?[C]. Optical Communication(ECOC), Cannes, France, 2014: 21-25. doi: 10.1109/ECOC.2014.6964248.

TURNER D, LEVCHENKO K, SNOEREN A C, et al. California fault lines: understanding the causes and impact of network failures[C]. ACM SIGCOMM, New Delhi, India, 2010: 315-326. doi: 10.1145/1851275.1851220.

张民贵, 刘斌. IP网络的快速故障恢复[J]. 电子学报, 2008, 36(8): 1595-1602.

ZHANG Mingui and LIU Bin. Fast failure recovery of IP networks[J]. Acta Electronica Sinica, 2008, 36(8): 1595-1602.

齐宁, 汪斌强, 王志明. 可重构服务承载网容错构建算法研究[J]. 电子与信息学报, 2012, 34(2): 468-473. doi: 10.3724/SP.J.1146.2011. 00670.

QI Ning, WANG Binqiang, and WANG Zhiming. Research on reconfigurable service carrying network resilient construction algorithms[J]. Journal of Electronics Information Technology, 2012, 34(2): 468-473. doi: 10.3724/SP.J. 1146.2011.00670.

SHAND M and BRYANT S. IP fast reroute framework[P] America, RFC5714, 2010.

王禹, 王振兴, 张连成. 一种基于结构化备份子图的路由系统失效恢复方法[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.

YANG B H, LIU J D, and SHENKER S, et al. Keep forwarding: 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.

WANG Y, WANG H, MAHIMKAR A, et al. R3: resilient routing reconfiguration[C]. ACM SIGCOMM, New Delhi, India, 2010: 291-302. doi: 10.1145/1851275.1851218.

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.

BANNER R and ORDA A. Designing low-capacity backup networks for fast restoration[C]. 2010 Proceedings IEEE INFOCOM, San Diego, America, 2010: 1-9. doi: 10.1109/INFCOM.2010.5462007.

ZHENG Q, CAO G H, THOMAS F, et al. Cross-layer approach for minimizing routing disruption in IP networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(7): 1659-1669. doi: 10.1109/TPDS.2013.157.

MISRA S, XUE G L, and YANG D J. Polynomial time approximations for multi-path routing with bandwidth and delay constrains[C]. IEEE INFOCOM, Rio de Janeiro, Brazil, 2009: 558-566. doi: 10.1109/INFCOM.2009.5061962.

TERESA G, MIGUEL S, JOSE C, et al. Two heuristics for calculating a shared risk link group disjoint set of paths of min-sum cost[J]. Journal of Network and System Management, 2014, 37(10): 332-338. doi: 10.1007/s10922- 014-9332-6.

ZHENG Q, CAO G, PORTA T L, et al. Optimal recovery from large-scale failures in IP networks[C]. IEEE ICDCS, Macau, China, 2012: 295-304. doi: 10.1109/ICDCS.2012.47.

JOHNSTON M, LEE H W, and MODIANO E. A robust optimization approach to backup network design with random failures[C]. IEEE INFOCOM, Shanghai, China, 2011: 1512-1520. doi: 10.1287/opre.1050.0238.

周灵, 王建新. 路径节点驱动的低代价最短路径树算法[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.

ZHENG Q, ZHAO J, and CAO G H. A cross-layer approach for IP network protection[C]. Dependable Systems and Networks (DSN), Boston, MA, USA, 2012: 1-12.

施引文献

资源附件(0)

访问统计