Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels

• Published in: IEEE/ACM transactions on networking 2004-12, Vol.12 (6), p.1105-1118
• Main Authors: Pin-Han Ho, Tapolcai, J., Cinkler, T.
• Format: Article
• Language: English
• Subjects: Bandwidth; Bandwidths; Communication networks; Communications networks; Computer networks; Heuristic algorithms; High performance computing; Integer linear programming; Integer linear programming (ILP); Integer programming; Joints; Linear programming; Merging; Network topologies; Network topology; Networks; Protection; Restoration; Routing; Routing (telecommunications); segment shared protection (SSP); Segments; shared risk link group (SRLG); Simulation; Studies; survivable routing; Switching theory; Throughput; working and protection paths
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2004.838592

This paper focuses on the problem of dynamic survivable routing for segment shared protection (SSP) in mesh communication networks provisioning bandwidth guaranteed tunnels. With SSP, a connection is settled by concatenating a series of protection domains, each of which contains a working and protection segment pair behaving as a self-healing unit for performing local restoration whenever the working segment is subject to any unexpected interruption. We first discuss the advantages of using SSP-the ability to shorten the restoration time as well as achieve a higher throughput by saving spare capacity required for 100% restorability; then the survivable routing problem is formulated into an Integer Linear Programming (ILP), where the switching/merging node pair of each protection domain along with the corresponding least-cost working and protection segment pair can be jointly determined for a dynamically arrived connection request. A novel approach of arc-reversal transformation is devised to deal with the situation that the working segments of two neighbor protection domains may overlap with each other by more than a single node. Due to a very high computation complexity induced in solving the ILP, a novel heuristic algorithm is proposed, named Cascaded Diverse Routing (CDR), to allocate protection domains for a connection request by performing diverse routing across a set of predefined candidate switching/merging node pairs. Experiments are conducted on five two-connected network topologies to verify the ILP and the CDR algorithm. We first determine the best diameter of protection domains for the CDR scheme in each network topology. Using the results of best diameters, CDR is compared with two reported schemes, namely PROMISE and OPDA. We demonstrate in the simulation results that the path-shared protection schemes are outperformed by the SSP schemes in terms of blocking probability under all possible arrangements in the experiment and that CDR yields better performance than PROMISE and OPDA due to the extra efforts in manipulating the location of working segments at the expense of longer computation time.