Abstract
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.