Method and system for fast computation of routes under multiple network states with communication continuation

• US 7,158,486 B2
• Filed: 03/12/2002
• Issued: 01/02/2007
• Est. Priority Date: 03/12/2001
• Status: Expired due to Fees

• Current Assignee: OpCoast LLC
• Original Assignee: OpCoast LLC
• Inventors: Rhodes, David L.
• Primary Examiner(s): Levitan; Dmitry
• Application Number:
  US10/095,862
• Publication Number:
  US 20020172157A1
• Time in Patent Office: 1,757 Days
• Field of Search: 370254-258, 370/351, 370/389
• US Class Current: 370/256
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing

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.

Claims

1. A method of computing routes on a network, which is composed of a plurality of nodes and a plurality of edges, representing network links, wherein each edge can be in a plurality of states, each edge having an edge metric value in each of its states, comprising the steps of

(a) generating a plurality of shortest path trees from a start node of the plurality of nodes, each shortest path tree including a subset of nodes from the plurality of nodes, a set of distance values, and a subset of edges from the plurality of edges, each distance value corresponding to a node of the set of nodes, the subset of edges of the plurality of edges having corresponding edge metric values that make up a shortest path between the start node and each other node of the subset of nodes, wherein VSET is the subset of nodes that are currently included in the shortest path tree and ESET is the subset of edges that are currently in the shortest path tree, said generating step further comprising the steps of:

(b) setting each edge of the plurality of edges to a state of the plurality of states for said each edge having a lowest edge metric value for said each edge;

(c) initiating a current routing scenario (CASE N);

(d) creating a shortest path tree (TREE N) for the current routing scenario (CASE N), wherein TREE N includes a start node at a distance value of zero;

(e) filling the TREE N, by performing the steps of;

1. if the shortest path tree of CASE N is complete, end CASE N and proceed to step (e)3(e) of prior CASE N unless there is no prior CASE N in which case stop, else proceed to step (e)2;

2. select an edge (EMIN) having a minimum edge metric value from any node, Vx, in VSET to a node VMIN, wherein edge EMIN and node VMIN are not in TREE, Vx is in VSET, and EMIN is not in ESET;

3. if additional higher-valued states are not available for EMIN or if further edge exploration is not allowed then proceed to step (e)4, else

a. place EMIN into its next higher valued state;

b. create a new routing scenario CASE N* with EMiN in said higher valued state;

c. copy TREE N into TREE N*;

d. recursively continue at step (e) wherein TREE N is TREE N*;

e. return the edge metric value of EMIN in TREE N to its prior state and proceed to step (e)3;

4. Add VMIN to VSET and add EMIN to ESET in TREE N, define the distance to node VMIN in TREE N as the sum of the edge metric value of EMIN and the distance value of Vx, and proceed step (e)1.

2. The method of claim 1 further comprising a step of sorting link metrics.

3. The method of claim 1 wherein the metric includes at least one of distance, delay, bandwidth and user-assigned metrics.

4. The method of claim 1 wherein the metrics are multiplicative.

5. The method of claim 1 wherein the steps are performed at a communications source.

6. The method of claim 1 wherein the steps are performed at one or more routers.

7. The method of claim 1 wherein the steps are performed only when a significant change in network conditions occur.

8. The method of claim 1 wherein the links are duplex links.

9. The method of claim 1 wherein each node performs steps (a) through (c) as a source node.

10. The method of claim 1 wherein routes are computed on-demand.

11. The method of claim 1 wherein routes are pre-computed.

12. A method for determining intermediate routing points on a network between a start node and a destination node during a change in edge metric status, the network being composed of nodes and links that may take on a plurality of possible metric statuses, comprising:

(a) retrieving or computing a first shortest path tree from a starting node of the network and a second shortest path tree from the starting node of the network, the first shortest path tree being for a first network state before the change in edge metric status and the second shortest path tree being for a second network state after the change in edge metric status

(b) determining a set of nodes common to said first and second shortest path trees from a graph isomorphism between the first and second shortest path trees;

(c) for each node in the set of nodes, retrieving or computing a shortest path tree from said each node as a starting node for the first network state and retrieving or computing a shortest path tree from said each node as a starting node for the second network state; and

(d) based upon the shortest path trees retrieved or computed in step c, determining a set of feasible intermediate routing nodes from the set of nodes, wherein, for each feasible intermediate routing node of the set of feasible routing nodes, a route from said each feasible intermediate routing node to the destination node is the same in the first network state and the second network state.

13. The method of claim 12 wherein the routes are determined during network non-convergence for continuous communications.

14. The method of claim 12 wherein the routes are determined during network convergence for computing potential explicit routing points.