A deeper study on segment shared protection

Author

Tapolcai, János ; Ho, Pin-Han

Author_Institution

Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont., Canada

fYear

2004

fDate

10-12 May 2004

Firstpage

319

Lastpage

325

Abstract

This paper studies the survivable routing problem for segment shared protection (SSP) in mesh communication networks with bandwidth-guaranteed tunnels. Firstly, the NP-completeness proof is given to this problem. Then, we extend the integer linear program (ILP) formulation for SSP by additionally considering the constraint on the restoration time for each connection request and the switching/merging capability in each node. Extensive simulation efforts are addressed to investigate the performance impairment by adopting different upper bounds of the two constraints. The computation time and the problem size in the CPLEX solver are analyzed.

Keywords

communication complexity; constraint handling; integer programming; linear programming; CPLEX solver; NP-completeness proof; bandwidth-guaranteed tunnels; connection request; integer linear program; merging capability; mesh communication networks; performance impairment; protection domain; restoration time; segment shared protection; survivable routing problem; switching capability; Bandwidth; Communication networks; Communication switching; Computational modeling; Merging; Protection; Routing; Switches; Time factors; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on

ISSN

1087-4089

Print_ISBN

0-7695-2135-5

Type

conf

DOI

10.1109/ISPAN.2004.1300499

Filename

1300499