Method and system for fast computation of routes under multiple network states with communication continuation
First Claim
1. A method for computing routes on a network, which is composed of nodes and links that may take on a multitude of possible metrics, comprising the steps of:
- (a) initiating a current routing scenario;
(b) creating an initial shortest path tree of the current routing scenario including a start node;
(c) checking the shortest path tree for completeness;
(d) selecting an edge for inclusion in the shortest path tree;
(e) creating a new current routing scenario as a copy of the current routing scenario wherein the node reached by the edge selected in (d) is considered in its next state and recursively applying steps (c) through (h) to the new current routing scenario;
(f) adding the edge selected in (d) to the shortest path tree and continuing at step (c) should further edge state exploration be not possible or allowed;
(g) creating a new current routing scenario as a copy of the current routing scenario wherein the edge selected in step (d) is put into its next metric value and recursively applying steps (c) through (h) to the new current routing scenario;
(h) returning the edge metric for the selected edge to its prior value and continuing at step (f).
0 Assignments
0 Petitions
Accused Products
Abstract
A system and method for network routing is provided where significant (those that impact optimal network routes) state changes of network components are considered. A set of optimal communication paths are generated for a number of actual and potential component failure scenarios. An optimal communication path is generated for each failure scenario. In addition, a method that enables continued communication using intermediate routing points and routing update propagation during periods of network non-convergence or congestion is disclosed.
102 Citations
19 Claims
-
1. A method for computing routes on a network, which is composed of nodes and links that may take on a multitude of possible metrics, comprising the steps of:
-
(a) initiating a current routing scenario;
(b) creating an initial shortest path tree of the current routing scenario including a start node;
(c) checking the shortest path tree for completeness;
(d) selecting an edge for inclusion in the shortest path tree;
(e) creating a new current routing scenario as a copy of the current routing scenario wherein the node reached by the edge selected in (d) is considered in its next state and recursively applying steps (c) through (h) to the new current routing scenario;
(f) adding the edge selected in (d) to the shortest path tree and continuing at step (c) should further edge state exploration be not possible or allowed;
(g) creating a new current routing scenario as a copy of the current routing scenario wherein the edge selected in step (d) is put into its next metric value and recursively applying steps (c) through (h) to the new current routing scenario;
(h) returning the edge metric for the selected edge to its prior value and continuing at step (f). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 19)
-
-
13. A method for propagating network metric updates comprising the steps of:
-
(a) retrieval of or computation of a shortest path tree from a starting node for the network;
(b) selection of node from a set of destinations such that the path in the shortest path tree includes as many other nodes in said destination set as possible;
(c) sending of the metric update to the node selected in (b) and marking all nodes along the path in the tree as ‘
updated’
;
(d) continuation of steps (b) through (d) until all destination nodes are updated.
-
-
17. A method for determining intermediate routing points on a network, which is composed of nodes and links that may take on a multitude of possible metrics, during a change in edge metric status comprising the steps of:
-
(a) retrieval of or computation of shortest path trees from a starting node for the network in the state prior to and after the said metric status change;
(b) determination of a set of nodes from the graph isomorphism between the two shortest path trees from step (a);
(c) for each node in the set determined at step (b), retrieval of or computation of a shortest path tree from each as a starting node for both states before and after said metric status change;
(d) determination of feasible intermediate routing points as those nodes in the set computed at (b) wherein the route to the destination from the potential intermediate node is the same irrespective of the status change by inspecting the paths computed at step (c).
-
Specification