Failure-Oriented Path Restoration Algorithm for Survivable Networks

In this article, a new polynomial-time approximation algorithm called Service Path Local Optimization (SPLO) is proposed for the online restoration problem. SPLO is shown to perform competitively with existing offline heuristics algorithm in terms of spare capacity. SPLO is designed for online computation where only one request is computed at any one time, and the decision making does not depend on future requests. The polynomial-time and online nature of the algorithm makes SPLO suitable for use in real-time on-demand path request applications. SPLO can be combined with a non-polynomial post-processing component that re-optimizes the backup paths. Significant reductions in spare capacity requirements are achievable at the expense of higher computation time. Further, the potential for SPLO as an algorithm in traffic engineering applications is investigated by looking at the performance impact when source-destination-based traffic aggregation is applied. We also introduce a new concept called path intermix where the service path¿s allocated bandwidth can be used by the backup paths protecting that particular service path.