Link Failure Recovery Algorithm Based on Multiple Backup Paths with QoS Constraint
CUI Wenyan① MENG Xiangru① YANG Huanhuan①② LI Jizhen① CHEN Tianping① KANG Qiaoyan①
①(College of Information and Navigation, Air Force Engineering University, Xi’an 710077, China) ②(Department of Electronic 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 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.
崔文岩,孟相如,杨欢欢,李纪真,陈天平,康巧燕. QoS约束的链路故障多备份路径恢复算法[J]. 电子与信息学报, 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. JEIT, 2016, 38(8): 1850-1857.
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.
[2]
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.
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.
[5]
SHAND M and BRYANT S. IP fast reroute framework[P] America, RFC5714, 2010.
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 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.
[8]
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.
[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. 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.
[11]
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.
[12]
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.
[13]
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.
[14]
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.
[15]
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.
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 Systems and Networks (DSN), Boston, MA, USA, 2012: 1-12.