Failure-oriented path restoration algorithm for survivable networks

A new polynomial-time approximation algorithm called service path local optimization (SPLO) is presented. SPLO is shown to perform competitively with existing non-polynomial approximations based on the failure-oriented approach. SPLO is designed for online computation where only one request is computed at a 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. In addition, a non-polynomial approximation algorithm based on SPLO called nSPLO is proposed. Result shows that spare capacity is reduced significantly but at the cost of substantially higher computation run-time. The paper also introduces 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. The result shows that path intermix can reduce spare capacity by up to 5% for single node failure.