Excess capacity planning for the protection of virtual paths

In this paper, the problem of allocation of excess capacity to the physical layer for semi-dedicated VP protection scheme has been studied. In the case of a link failure, the semi-dedicated protection scheme will allocate reserve capacity in the remaining links to the protection of virtual paths whose working paths have been affected. The paper develops three solution strategies for excess bandwidth calculation. The optimal solution can be obtained by an integer linear programming model that will be unsuitable for large problems. A heuristic based on decomposition of the optimal solution to a series of smaller integer linear programming problems is presented. A simpler heuristic based on K-edge-disjoint shortest paths problem is developed which has an O(n⁴) complexity where n is the number of nodes in the network