Graceful reassignment of excessively long communications paths in networks

Modern broadband telecommunications networks transport diverse classes of traffic through flexible end-to-end communications paths. For instance, Internet Protocol (IP) networks with Multi-Protocol Label Switching (MPLS) carry traffic through label switched paths. These flexible paths are often changed in real, or near-real, time in response to congestion and failures detected in the network. As a result, over time, some of these communications paths become excessively long (referred to as out-of-kilter), leading to poor service performance and waste of network resources. An effective reassignment scheme may require reassignment of communications paths with acceptable length (referred to as in-kilter) in order to generate spare capacity on certain links for the out-of-kilter paths. A graceful reassignment solution provides an ordered sequence of reassignments that satisfies the following: (i) the total number of reassigned communications paths does not exceed a specified limit, (ii) no temporary capacity violations are incurred on any network link during the execution of the sequence of reassignments (reassignments are executed sequentially, one at a time), (iii) a communications path is reassigned only as a unit without being split among multiple alternate routes (iv) all reassigned communications paths will be in-kilter, (v) none of the reassignments of communications paths that were originally in-kilter can be excluded from the specified solution without resulting in some capacity violation, and (vi) the sequence of reassignments approximately optimizes a predefined objective, such as maximizing the number of reassigned out-of-kilter communications paths or maximizing the total load reassigned from out-of-kilter communications paths. The resulting problem is formulated as a multi-period, multi-commodity network flow problem with integer variables. We present a search heuristic that takes advantage of certain problem properties to find subsequences of reassignments that become part of the solution, without performing an exhaustive search. Each subsequence reassigns at least one out-of-kilter communication path.