Novel algorithms for shared segment protection

被引:94
作者
Xu, DH [1 ]
Xiong, YZ [1 ]
Qiao, CM [1 ]
机构
[1] SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA
基金
美国国家科学基金会;
关键词
bandwidth sharing; dynamic provisioning; multi-protocol label switched (MPLS); optical network; protection;
D O I
10.1109/JSAC.2003.816624
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
The major challenges in designing survivable schemes are how to allocate minimal amount of spare resources (e.g., bandwidth) using fast (e.g., polynomial-time) algorithms, and in case a failure occurs, to be able to quickly recover from it. All existing approaches invariably make tradeoffs. In this paper, we propose novel shared segment protection algorithms which make little or no compromise. We develop an elegant integer linear programming (ILP) model to determine an optimal set of segments to protect a given active path. Although the ILP approach is useful for a medium-size network, it is too time consuming for large networks. Accordingly, we also design a fast heuristic algorithm based on dynamic programming to obtain a near-optimal set of segments. Although the heuristic algorithm has a polynomial time complexity, it can achieve a bandwidth efficiency as high as some best-performing shared path protection schemes and at the same time, much faster recovery than these shared path protection schemes. The proposed scheme is also applicable to a wide range of networking technologies including Internet protocol and wavelength-division multiplexing networks under the generalized multiprotocol label switched framework.
引用
收藏
页码:1320 / 1331
页数:12
相关论文
共 28 条
[1]  
BARONI S, 1998, NUMBER WAVELENGTH AR
[2]  
CHAUHAN S, 2001, SUB PATH PROTECTION
[3]   Optical network design and restoration [J].
Doshi, BT ;
Dravida, S ;
Harshavardhana, P ;
Hauser, O ;
Wang, YF .
BELL LABS TECHNICAL JOURNAL, 1999, 4 (01) :58-84
[4]  
Grover WD, 1998, ICC 98 - 1998 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS VOLS 1-3, P537, DOI 10.1109/ICC.1998.682929
[5]  
GROVER WD, 2003, P INT C COMM ICC 03
[6]   An efficient primary-segmented backup scheme for dependable real-time communication in multihop networks [J].
Gummadi, KP ;
Pradeep, MJ ;
Murthy, CSR .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2003, 11 (01) :81-94
[7]  
Haskin D. L., 2000, METHOD SETTING ALTER
[8]   A framework for service-guaranteed shared protection in WDM mesh networks [J].
Ho, PH ;
Mouftah, HT .
IEEE COMMUNICATIONS MAGAZINE, 2002, 40 (02) :97-103
[9]  
Kodialam M., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P902, DOI 10.1109/INFCOM.2000.832265
[10]  
Kodialam M, 2001, IEEE INFOCOM SER, P376