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

CUI Wenyan; MENG Xiangru; YANG Huanhuan; LI Jizhen; CHEN Tianping; KANG Qiaoyan

doi:10.11999/JEIT151230

Volume 38 Issue 8

Sep. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(8): 1850-1857

CUI Wenyan, MENG Xiangru, YANG Huanhuan, LI Jizhen, CHEN Tianping, KANG Qiaoyan. Link Failure Recovery Algorithm Based on Multiple Backup Paths with QoS Constraint[J]. Journal of Electronics & Information Technology, 2016, 38(8): 1850-1857. doi: 10.11999/JEIT151230

Citation:

CUI Wenyan, MENG Xiangru, YANG Huanhuan, LI Jizhen, CHEN Tianping, KANG Qiaoyan. Link Failure Recovery Algorithm Based on Multiple Backup Paths with QoS Constraint[J]. Journal of Electronics & Information Technology, 2016, 38(8): 1850-1857. doi: 10.11999/JEIT151230

Citation:

PDF( 292 KB)

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

doi: 10.11999/JEIT151230

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

Funds:

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

Received Date: 2015-11-03
Rev Recd Date: 2016-03-03
Publish Date: 2016-08-19

Abstract

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

FullText(HTML)

References(21)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views