System for maintaining multiple loop free paths between source node and destination node in computer network

• US 5,881,243 A
• Filed: 05/07/1997
• Issued: 03/09/1999
• Est. Priority Date: 05/07/1997
• Status: Expired due to Fees

• Current Assignee: J. Joaquin Garcia-Luna-Aceves, William T. Zaumen
• Original Assignee: J. Joaquin Garcia-Luna-Aceves, William T. Zaumen
• Inventors: Zaumen, William T., Garcia-Luna-Aceves, J. Joaquin
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US08/852,357
• Time in Patent Office: 671 Days
• Field of Search: 395/200.53, 395/200.54, 395/200.68, 395/200.71, 395/200.69, 370/256, 370/238, 370/351, 370/255, 370/254
• US Class Current: 709/241
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/18 Loop-free operations

Abstract

A system for maintaining routing tables at each router in a computer network. The system is based on (a) a feasibility condition that provides multiple loop-free paths through a computer network and that minimizes the amount of synchronization among routers necessary for the correct operation of a routing algorithm, and (b) a method that manages the set of successors during the time it synchronizes its routing-table update activity with other routers, in order to efficiently compute multiple loop-free paths, including the shortest path, through a computer network.

Claims

1. A method of maintaining multiple loop-free paths between a source node and a destination node in a computer network, the source node being a router, a computer, or a special-purpose device;

the destination node being a computer, a router, a device, or a network connected to the source node either directly or through one or more intermediate nodes;

each intermediate node being a computer, a router, or a special-purpose device; and

the method comprising the following steps;

(a) generating a list of neighbor nodes, each neighbor node being adjacent to and directly connected to the source node;

(b) generating a list of neighbor-node lengths, each neighbor-node length being measured on a link or an attached network from the source node to a corresponding one of the neighbor nodes;

(c) generating a list of the neighbor-to-destination lengths, each neighbor-to-destination length being measured from one of the neighbor nodes to the destination node;

(d) generating a list of the smallest value of the neighbor-to-destination length being measured from each of the neighbor nodes to the destination node;

(e) generating the shortest loop-free path length, the shortest loop-free path length representing the length of a shortest loop-free path from the source node to the destination node;

(f) generating the feasible length, the feasible length representing the smallest value of the shortest loop-free path length;

(g) selecting a successor set comprised of successor nodes, each successor node being the next node along a loop-free path from the source to the destination node;

(h) determining whether a condition has been met that may cause the source to change its set of successor nodes or its shortest loop-free path length;

(i) performing the following steps, in the event the condition has been met;

(j) selecting those neighbor nodes for whom the smallest values of their adjacent-to-destination lengths are smaller than the feasible length;

(k) storing each selected neighbor node as a successor node in the successor set, each successor node being the next node along a loop-free path from the source node to the destination node;

(l) for each neighbor node in the successor set, adding the neighbor-to-destination length to its corresponding neighbor node length, each sum forming a distance from the source node to the destination node through one of the selected neighbor nodes;

(m) storing each corresponding distance as a loop-free path length from the source node to the destination node through the given neighbor node;

(n) determining the smallest loop-free path length;

(o) storing the smallest loop-free path length as the shortest loop-free path length;

(p) selecting the neighbor nodes for whom the sum of the neighbor-to-destination length and the corresponding neighbor-node length equal the shortest path length;

(q) storing each selected neighbor in the shortest-path set.

2. The method of maintaining loop-free paths according to claim 1, wherein each generated length for the shortest loop-free path is reported by the source node to the source node'"'"'s neighbor nodes.

3. The method of maintaining loop-free paths according to claim 1, wherein each generated length for the shortest loop-free path is reported by the source node to the source node'"'"'s neighbor nodes at regular intervals of time.

4. The method of maintaining loop-free paths according to claim 1, wherein the step of generating a list of the smallest value of the neighbor-to-destination length being measured from each of the neighbor nodes to the destination node includes the following steps for a given neighbor node:

generating a smallest value for the neighbor-to-destination length of the given neighbor node,

comparing the generated smallest value for the neighbor-to-destination length of a given neighbor node to a previously generated length for the smallest value of the neighbor-to-destination length of the same given neighbor node, and

choosing the smaller of the lengths as the smallest value of the neighbor-to-destination length of a given neighbor node.

5. The method of maintaining loop-free paths according to claim 1, wherein the step of generating the feasible length comprises the steps of:

comparing the generated value for the shortest loop-free path length to a previously generated length for the feasible length; and

choosing the smaller of the lengths as the feasible length.

6. The method of maintaining loop-free paths according to claim 1, wherein the step of determining whether a condition has been met that may cause the source to change its set of successor nodes or its shortest loop-free path length includes the following steps:

determining whether a length from the source node to an neighbor node has increased or decreased;

determining whether a distance reported from an neighbor node to the source node has increased or decreased, the reported distance being measured from the neighbor node to the destination node.

7. The method of maintaining loop-free paths according to claim 1, wherein the step of determining the smallest loop-free path length includes the following steps:

comparing the distance from the source node to the destination node through each neighbor node for whom the value of its adjacent-to-destination length is smaller than the source node'"'"'s feasible length;

obtaining the minimum of such distances; and

making the smallest loop-free path length equal to the smallest distance.

8. A method of maintaining multiple loop-free paths to every destination node among nodes within a computer network or internetwork, each node executing the method being a router, a computer, or a special-purpose device, and the method comprising the following steps:

(a) generating for each node a list of nodes that are neighbors to the node, each neighbor node being directly connected to the node;

(b) generating for each node a list of neighbor-node lengths, each neighbor-node length being measured from the node to one of its neighbor nodes;

(c) generating for each node a list of destination nodes, each destination node being connected to the node either directly or through one or multiple other nodes;

(d) generating for each node a list of neighbor-to-destination lengths, each neighbor-to-destination length being measured from one of the node'"'"'s neighbor nodes to one of the node'"'"'s destination nodes;

(e) generating a list of the smallest value of the neighbor-to-destination length being measured from each of the node'"'"'s neighbor nodes to each of the node'"'"'s destination nodes;

(f) generating for each node a list of shortest loop-free path lengths, each shortest loop-free path length representing the length of a shortest loop-free path from the node to one of the node'"'"'s destination nodes;

(g) generating for each node a list of the feasible length for the node to each of the node'"'"'s destination nodes, each feasible length representing the smallest value of the shortest loop-free path length from the node to a given node'"'"'s destination nodes;

(h) generating for each node a set of successor nodes for each of the node'"'"'s destination nodes, each successor node being the next node along a loop-free path from the node to one of the node'"'"'s destination nodes;

(i) determining whether a condition has been met that may cause a given node to change its set of successor nodes or its shortest loop-free path length;

(j) in the event the condition has been met, performing the following steps;

(k) retrieving from the given node'"'"'s neighbor-to-destination lengths the neighbor-to-destination lengths from each of the given node'"'"'s neighbor nodes to the given destination node;

(l) selecting those neighbor nodes of the given node for whom the smallest values of their neighbor-to-destination lengths to the given destination node are smaller than the given node'"'"'s feasible length to the given destination node;

(m) storing each of the given node'"'"'s selected neighbor nodes for each given destination as a successor node in the successor set, each successor node being the next node along a loop-free path to a given destination;

(n) for each selected neighbor node in the given node'"'"'s successor set for a given destination, adding the neighbor-to-destination length for the given destination to its corresponding neighbor node length, each sum forming a distance from the given node to the given destination node;

(o) storing each corresponding distance as a loop-free path length from the given node to the given destination node;

(p) determining the smallest loop-free path length to each of the given node'"'"'s destination nodes;

(q) for each of the given node'"'"'s destination nodes, storing the smallest distance as the given node'"'"'s shortest loop-free path length to the given destination node;

(r) for each of the given node'"'"'s destination nodes, selecting the neighbor nodes for whom the sum of the neighbor-to-destination length and the corresponding neighbor-node length equal the shortest path length from the given node to a given destination node;

(q) for each of the given node'"'"'s destination nodes, storing each selected neighbor in the shortest-path set of the destination.

9. The method of maintaining loop-free paths to every destination node according to claim 8, wherein each generated length for a shortest loop-free path is reported, by the corresponding node from which the shortest loop-free path length is measured, to the corresponding node'"'"'s neighbor nodes.

10. The method of maintaining loop-free paths to every destination node according to claim 8, wherein each generated length for a shortest loop-free path is reported, by the corresponding node from which the shortest loop-free path length is measured, to the corresponding node'"'"'s neighbor nodes at regular intervals of time.

11. The method of maintaining loop-free paths to every destination node according to claim 8, wherein the step of generating a list of the smallest value of the neighbor-to-destination length being measured from each of the node'"'"'s neighbor nodes to each of the node'"'"'s destination nodes includes the following steps, the following steps being performed for each generation of each smallest value of the neighbor-to-destination length:

generating a smallest value for the neighbor-to-destination length of a given neighbor node for a given destination node;

comparing the generated smallest value for the neighbor-to-destination length of a given neighbor node for a given destination node to a previously-generated length for the smallest value of the neighbor-to-destination length of the same given neighbor node for the same given destination node; and

choosing the smaller of the lengths as the smallest value of the neighbor-to-destination length of a given neighbor node for a given destination node.

12. The method of maintaining loop-free paths to every destination node according to claim 8, wherein the step of generating for each node a list of the feasible length for the node to each of the node'"'"'s destination nodes includes the following steps:

generating a smallest value for shortest loop-free path;

comparing the generated smallest value for the shortest loop-free path length to a previously generated length for the smallest value of the shortest loop-free path length; and

choosing the smaller of the lengths as the smallest value of the shortest loop-free path length.

13. The method of maintaining loop-free paths to every destination node according to claim 8, wherein the step of determining whether a condition has been met that may cause a given node to change its set of successor nodes or its shortest loop-free path length comprises the following steps:

determining whether a length from the given node to an neighbor node has increased or decreased;

determining whether a distance reported from an neighbor node to the given node has increased or decreased, the reported distance being measured from the neighbor node to the destination node.

14. The method of maintaining loop-free paths according to claim 8, wherein the step of determining the smallest loop-free path length to each of the given node'"'"'s destination nodes comprises the following steps:

comparing the distance from the given node to the given node'"'"'s destination node through each of the given node'"'"'s neighbor nodes for whom the value of its adjacent-to-destination length is smaller than the given node'"'"'s feasible length;

obtaining the minimum of such distances; and

making the smallest loop-free path length equal to the smallest distance.