On the solution of reroute sequence planning problem in MPLS networks
This paper studies the problem of reroute sequence planning for label switched paths (LSPs) in multiprotocol label switching networks from both the theoretical and practical points of view. This issue arises when the set of LSPs is recalculated by a central path optimization tool to attain a better resource utilization in the network. In this case a sequence of LSPs has to be found for their one by one reconfiguration without service interruption, involving the constraint that the link capacities should not be violated at any time during the rerouting process. The underlying problem is related to discrepancy theory and it is NP-complete. The conditions of existence of any feasible reroute sequence are examined, and algorithms are described for solving the problem. Alternative solutions are also presented for the case when feasible solutions do not exist, finally the performance of these algorithms is investigated by empirical analysis.
rerouting sequence planning mpls path optimization traffic engineering