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

doi:10.11999/JEIT151230

Abstract
Figure/Table
References (17)
Related Citation (15)

Download: PDF (292 KB)
Export: BibTeX | EndNote (RIS)

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.

Key words： Link failure recovery Multiple backup paths QoS Reroute

Received: 03 November 2015 Published: 09 May 2016

PACS:

TP393

Fund:

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

Corresponding Authors: CUI Wenyan E-mail: cwy_edu@163.com

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	CUI Wenyan
	MENG Xiangru
	YANG Huanhuan
	LI Jizhen
	CHEN Tianping
	KANG Qiaoyan

Cite this article:

CUI Wenyan,MENG Xiangru,YANG Huanhuan等. Link Failure Recovery Algorithm Based on Multiple Backup Paths with QoS Constraint[J]. JEIT, 2016, 38(8): 1850-1857.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT151230 OR http://jeit.ie.ac.cn/EN/Y2016/V38/I8/1850

[1]	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.
[3]	张民贵, 刘斌. 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.
[4]	齐宁, 汪斌强, 王志明. 可重构服务承载网容错构建算法研究[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.
[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 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.
[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 Systems and Networks (DSN), Boston, MA, USA, 2012: 1-12.