Apparatus and method for graceful reassignment of out-of-kilter communications paths
View Patent ↗A method is disclosed that provides an ordered sequence of reassignments of communications paths to new routes. The network may have multiple excessively long communications paths, referred to as out-of-kilter paths, while other communications paths are of acceptable length, referred to as in-kilter paths. The method approximately optimizes a predefined objective such as maximizing the number of reassigned out-of kilter communications paths. The method may reassign multiple in-kilter paths to new routes in order to free up capacity and allow the reassignment of an out-of-kilter path. Reassignments are executed one at a time according to the ordered sequence determined by the method, and no capacity violations are incurred on any network link at any point in time during the execution of the sequence of reassignments. All reassigned communications paths will be in-kilter.
1. A method of reassigning communications paths in a communications network comprising the steps of:
(a) analyzing a representation of a set of out-of-kilter communications paths and a representation of a set of in-kilter communications paths to generate an analysis;
(b) generating a set of permitted changes, based upon the analysis, to both the representation of the set of out-of-kilter communications paths and the representation of the set of in-kilter communications paths; and
(c) generating, in response to the set of permitted changes, an ordered sequence of recommended reassignments of communications paths and associating at least one out-of-kilter communications path associated with the ordered sequence of recommended reassignments with a new in-kilter communications path, wherein communications paths which are originally in-kilter are reassigned only if such reassignments make it feasible to reassign an out-of-kilter communications path.
2. A method of reassigning communications paths in a communications network comprising the steps of:
(a) analyzing a representation of a set of out-of-kilter communications paths and a representation of a set of in-kilter communications paths to generate an analysis;
(b) generating a set of permitted changes, based upon the analysis, to both the representation of the set of out-of-kilter communications paths and the representation of the set of in-kilter communications paths;
(c) generating multiple backward subsequences, each backward subsequence having an out of-kilter communications path as its first reassignment; and
(d) generating, in response to the set of backward subsequences, an ordered sequence of recommended reassignments of communications paths wherein each out-of-kilter communications path in a backward subsequence is associated with a new in-kilter communications path in the ordered sequence of recommended reassignments.
3. The method of claim 2 wherein each backward subsequence found is translated to a forward subsequence, and all forward subsequences are combined to form a single ordered sequence of recommended reassignments.
4. A device for reassigning communications paths in a communications network comprising:
(a) means for determining subsequences of communications paths that will be reassigned onto new routes wherein each ordered subsequence comprising in-kilter communications paths and an out-of-kilter communications path;
(b) means for determining an ordered sequence of reassignments of the communications paths that will be reassigned in an ordered subsequences; and
(c) means for executing the reassignments in the ordered sequence of reassignments sequentially according to the order in the sequence wherein after execution all reassigned communications paths are in-kilter, each reassigned communications path is reassigned with its entire load onto a single new route, communications paths which are originally in-kilter are reassigned only if such reassignments make it feasible to reassign an out-of-kilter communications path, and none of the link capacity constraints is violated after executing each of the reassignments.
5. The device of claim 4 further comprising means for transmitting the ordered sequence of recommended reassignments.
6. A method of reassigning communications paths in a communications network comprising the steps of:
(a) determining ordered subsequences of communications paths that will be reassigned onto new routes wherein each ordered subsequence comprising in-kilter communications paths and an out-of-kilter communications path;
(b) determining an ordered sequence of reassignments of the communications paths in all ordered subsequences; and
(c) executing the reassignments in the ordered sequence of reassignments sequentially according to the order in the sequence wherein after execution all reassigned communications paths are in-kilter, each reassigned communications path is reassigned with its entire load onto a single new route, communications paths which are originally in-kilter are reassigned only if such reassignments make it feasible to reassign an out-of-kilter communications path, and none of the link capacity constraints is violated after executing each of the reassignments.
7. The method of claim 6 wherein the number of reassignments in the ordered sequence of recommended reassignments is less than a predetermined number.
8. The method of claim 6 further comprising the step of generating multiple backward subsequences, each backward subsequence having an out of-kilter communications path as its first reassignment.
9. The method of claim 8 wherein each backward subsequence found is translated to a forward subsequence, and all forward subsequences are combined to form a single ordered sequence of recommended reassignments.