Optimal routing with failure-independent path protection

TY - JOUR

T1 - Optimal routing with failure-independent path protection

AU - Stidsen, Thomas

AU - Petersen, Bjørn

AU - Spoorendonk, Simon

AU - Zachariasen, Martin

AU - Rasmussen, Kasper Bonne

PY - 2010/3

Y1 - 2010/3

N2 - Reliable communication has become crucial in today's information society. Modern communication networks are required to deliver reliable communication to their customers. Unfortunately, protection against network failures significantly hampers efficient utilization of network investments, because the associated routing problems become much harder. In this article we present a rigorous mathematical analysis of one of the most promising protection methods: Failure independent path protection. We present an LP model which is solved by column generation. The subproblem is proven to be strongly NP-hard, but still solvable for medium sized networks through the use of specialized dynamic programming algorithms. This enables us to evaluate the performance of failure independent path protection for eight networks with up to 37 nodes and 57 links. The results indicate that only between 3% and 8% extra network capacity is necessary when compared with the capacity required by complete rerouting (which is the absolute lower bound for single link failure protection).

AB - Reliable communication has become crucial in today's information society. Modern communication networks are required to deliver reliable communication to their customers. Unfortunately, protection against network failures significantly hampers efficient utilization of network investments, because the associated routing problems become much harder. In this article we present a rigorous mathematical analysis of one of the most promising protection methods: Failure independent path protection. We present an LP model which is solved by column generation. The subproblem is proven to be strongly NP-hard, but still solvable for medium sized networks through the use of specialized dynamic programming algorithms. This enables us to evaluate the performance of failure independent path protection for eight networks with up to 37 nodes and 57 links. The results indicate that only between 3% and 8% extra network capacity is necessary when compared with the capacity required by complete rerouting (which is the absolute lower bound for single link failure protection).

U2 - 10.1002/net.20323

DO - 10.1002/net.20323

M3 - Journal article

SN - 0028-3045

VL - 55

SP - 125

EP - 137

JO - Networks

JF - Networks

IS - 2

ER -