×

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
First Claim
Patent Images

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.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×