Dynamic algorithm for determining a shortest path tree between network nodes

• US 6,704,320 B1
• Filed: 03/24/1999
• Issued: 03/09/2004
• Est. Priority Date: 03/24/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Narvaez, Paolo, Tzeng, Hong-Yi, Siu, Kai-Yeung
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/275,591
• Time in Patent Office: 1,812 Days
• Field of Search: 370/408, 370/238, 370/230, 370/351, 370/352, 370/356, 370/255, 370/231, 370/256, 370/235, 370/252, 709/241, 709/244, 709/238, 709/239
• US Class Current: 370/408
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

A dynamic shortest path tree (SPT) algorithm for a router determines a new SPT for a root node in response to a link-state or other network topology change. The dynamic SPT algorithm determines the new SPT as an optimization problem in a linear programming framework based in an existing SPT in the router. The dynamic SPT algorithm emulates maximum decrement of a ball and string model by iteratively selecting nodes of the existing SPT for consideration and update of parent node, child nodes, and distance attributes based on the maximum decrement. For the maximum decrement, a node in the existing SPT is selected by each iteration based on the greatest potential decrease (or least increase) in its distance attribute. The ball and string model that may be employed for the dynamic SPT algorithm represents a network of nodes and links with a ball representing a node and a string representing a link or edge. The length of a string is defined by its link'"'"'s weight. The set of strings connecting the balls defines a path between the root node and a particular node. The shortest path is the path defined by the strings from a root node to a particular node that are tight. For the dynamic SPT algorithm, an increase (or decrease) in an edge weight in an existing SPT corresponds to a lengthening (or shortening) of a string. By sequentially pulling balls away in a single direction from the ball of the root node, the new SPT becomes defined by the balls and tight strings.

Claims

1. A routing processor of a router for routing packet network based on a shortest path tree (SPT) defining paths between nodes in the network, the routing processor comprising:

an initialization module adapted to generate, for a current SPT, a temporary list of nodes in the network affected by a change in the weight of a link between two nodes in the network, wherein the change corresponds to the addition of a new link in the network or an increase or decrease in the weight of an existing link in the network;

a node selection module adapted to select a node of the list in accordance with a maximum decrement criterion, the maximum decrement criterion identifying the node in the list having a most negative or a least positive associated distance change resulting from the change in the weight of the link;

an update module adapted to update one or more paths in current SPT for nodes reachable from the selected node, wherein the selected node is removed from the list and zero, one, or more of the reachable nodes are added to the list;

wherein the node selection module and the update module repeatedly select nodes and update paths until the list is empty to generate an updated SPT, the router thereby causing one or more packets to be routed in accordance with the updated SPT,

wherein the initialization module is further adapted to define a temporary tree data structure for a current SPT, the temporary tree data structure including a set of edges interconnecting a root node with one or more nodes of the plurality of nodes, each node having associated parent and child nodes and associated distance attribute, and each edge corresponding to a link and having the associated weight of the link,

wherein the initialization module is further adapted to generate the temporary list of one or more nodes effected by a change of an edge weight, each entry of the temporary list having the associated parent node, a new distance attribute resulting from the weight change, and a distance change, and

wherein the update processor is further adapted to update the one or more paths defined in the temporary tree data structure by;

(1) updating the parent and child nodes associated with the node selected in step (b),

(2) updating, with the distance change, the distance attribute of the selected node and each descendent node of the selected node,

(3) defining, if necessary, a new distance attribute and a distance change for each node receiving an edge from either the node selected in step (b) or a descendent node of the selected node,

(4) adding to the temporary list each node receiving an edge in step (f) and the corresponding parent node, new distance attribute, and distance change, and

(5) setting, when the temporary list is empty, the updated temporary tree data structure as the updated SPT.

2. The invention as recited in claim 1, wherein the initialization processor is further adapted to, if a current SPT doesn'"'"'t exist, generate a current SPT by defining the temporary tree data structure as the root node and the remaining nodes of the plurality of nodes, the associated parent and child nodes of each of the remaining nodes being set to the null set, and the associate distance attribute of each of the remaining nodes being set to zero.

3. The invention as recited in claim 1, wherein the initialization processor:

1) updates the edge weight in the temporary tree data structure corresponding to the change in the edge weight;

2) defines a set of one or more nodes each i) having a parent node and a distance attribute, ii) interconnected to the root node, and iii) affected by the weight change of the edge;

determines the new distance attribute for each node, the new distance attribute corresponding to a path having a minimum sum of the edge weights from the root node to the node when an edge weight changes; and

adds the nodes of the set to the temporary list; and

(3) determines a distance change for each node of the temporary list, the distance change corresponding to the difference between the distance attribute and the new distance.

4. The invention as recited in claim 3, wherein each edge is defined by a source node and an end node the initialization processor defines each node of the temporary tree data structure as an anchored node, and the initialization processor generates the temporary list for either of two cases of the change of the edge weight:

a first case corresponding to an increase in edge weight and a second case corresponding to a decrease in edge weight.

5. The invention as recited in claim 4, wherein the initialization processor generates the temporary list for the first case by:

if the edge is in the temporary tree data structure,;

A) determining the descendent nodes of the end node that are reachable through edges of the temporary tree data structure and setting each of the determined descendent as a floating node; and

for each edge having an end node being a floating node and a source node being an anchored node;

B) setting the new distance attribute of the end node as the distance attribute of the source node combined with the updated edge weight, the distance change of the end node to the difference between the new distance attribute and the distance attribute of the end node, and adding to the temporary list the end node and the corresponding source node as the parent node, the new distance attribute and the distance change; and

wherein the node selection processor is adapted to set the selected node and each descendent node as being anchored nodes.

6. The invention as recited in claim 4, wherein:

the initialization processor generates the temporary list for the second case by setting the new distance attribute of the end node as the distance attribute of the source node combined with the updated edge weight; and

if the new distance attribute is less than the distance attribute of the end node, setting the distance change of the end node to the difference between the new distance attribute and the distance attribute of the end node, and adding to the temporary list the end node and the corresponding source node as the parent node, the new distance attribute and the distance change.

7. A method for routing packets in a packet network based on a shortest path tree (SPT) defining paths between nodes in the network, comprising the steps of:

(a) generating, for a current SPT, a temporary list of nodes in the network affected by a change in the weight of a link between two nodes in the network, wherein the change corresponds to the addition of a new link in the network or an increase or decrease in the weight of an existing link in the network;

(b) selecting a node of the list in accordance with a maximum decrement criterion, the maximum decrement criterion identifying the node in the list having a most negative or a least positive associated distance change resulting from the change in the weight of the link;

(c) updating one or more paths in current SPT for nodes reachable from the selected node, wherein the selected node is removed from the list and zero, one, or more of the reachable nodes are added to the list;

(d) repeating steps (b) and (c) until the list is empty to generate an updated SPT, thereby routing one or more packets in accordance with the updated SPT; and

(e) defining a temporary tree data structure for a current SPT, the temporary tree data structure including a set of edges interconnecting a root node with one or more nodes of the plurality of nodes, each node having associated parent and child nodes and associated distance attribute, and each edge corresponding to a link and having the associated weight of the link; and

wherein;

step (a) generates the temporary list of one or more nodes effected by a change of an edge weight, each entry of the temporary list having the associated parent node, a new distance attribute resulting from the weight change, and a distance change;

step (c) updates the one or more paths defined in the temporary tree data structure by;

(c1) updating the parent and child nodes associated with the node selected in step (b),

(c2) updating, with the distance change, the distance attribute of the selected node and each descendent node of the selected node,

(c3) defining, if necessary, a new distance attribute and a distance change for each node receiving an edge from either the node selected in step (b) or a descendent node of the selected node, and

(c4) adding to the temporary list each node receiving an edge in step (f) and the corresponding parent node, new distance attribute, and distance change; and

for step (d) repeating the steps (b) and (c) until the temporary list is empty, the updated temporary tree data structure being the updated SPT.

8. The method as recited in claim 7, further comprising the steps of:

if a current SPT doesn'"'"'t exist, generating a current SPT by defining the temporary tree data structure as the root node and the remaining nodes of the plurality of nodes, the associated parent and child nodes of each of the remaining nodes being set to the null set, and the associate distance attribute of each of the remaining nodes being set to zero.

9. The method as recited in claim 7, wherein step (a) includes the steps of:

(a1) updating the edge weight in the temporary tree data structure corresponding to the change in the edge weight;

(a2) defining a set of one or more nodes each i) having a parent node and a distance attribute, ii) interconnected to the root node, and iii) affected by the weight change of the edge;

(a3) determining the new distance attribute for each node of the set of step (a2), the new distance attribute corresponding to a path having a minimum sum of the edge weights from the root node to the node when an edge weight changes;

(a4) determining a distance change for each node of the temporary list, the distance change corresponding to the difference between the distance attribute and the new distance; and

(a5) adding the nodes of the set to the temporary list.

10. The method as recited in claim 9, wherein each edge is defined by a source node and an end node, step a) defines each node of the temporary tree data structure as an anchored node, and step (a) generates the temporary list for either of two cases of the change of the edge weight:

a first case corresponding to an increase in edge weight and a second case corresponding to a decrease in edge weight.

11. The method as recited in claim 10, wherein step (a) generates the temporary list for the first case by the steps of:

if the edge is in the temporary tree data structure;

(a2i) determining the descendent nodes of the end node that are reachable through edges of the temporary tree data structure;

(a2ii) setting each of the descendent nodes determined in step (a2i) as a floating node; and

for each edge having an end node being a floating node and a source node being an anchored node;

(a3i) setting the new distance attribute of the end node as the distance attribute of the source node combined with the updated edge weight of step (a

     1),

(a4i) setting the distance change of the end node to the difference between the new distance attribute and the distance attribute of the end node, and

(a5i) adding to the temporary list the end node and the corresponding source node as the parent node, the new distance attribute and the distance change; and

wherein step (b) includes the step of setting the selected node and each descendent node as being anchored nodes.

12. The method as recited in claim 10, wherein step (b) generates the temporary list for the second case by the steps of:

(a3i) setting the new distance attribute of the end node as the distance attribute of the source node combined with the updated edge weight of step (a1); and

if the new distance attribute is less than the distance attribute of the end node;

(a4i) setting the distance change of the end node to the difference between the new distance attribute and the distance attribute of the end node, and

(a5i) adding to the temporary list the end node and the corresponding source node as the parent node, the new distance attribute and the distance change.

13. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for routing packets in a packet network based on a shortest path tree (SPT) defining paths between nodes in the network, the method comprising the steps of:

(a) generating, for a current SPT, a temporary list of nodes in the network affected by a change in the weight of a link between two nodes in the network, wherein the change corresponds to the addition of a new link in the network or an increase or decrease in the weight of an existing link in the network;

(b) selecting a node of the list in accordance with a maximum decrement criterion, the maximum decrement criterion identifying the node in the list having a most negative or a least positive associated distance change resulting from the change in the weight of the link;

(c) updating one or more paths in current SPT for nodes reachable from the selected node, wherein the selected node is removed from the list and zero, one, or more of the reachable nodes are added to the list;

(d) repeating steps (b) and (c) until the list is empty to generate an updated SPT, thereby routing one or more packets in accordance with the updated SPT; and

(e) defining a temporary tree data structure for a current SPT, the temporary tree data structure including a set of edges interconnecting a root node with one or more nodes of the plurality of nodes, each node having associated parent and child nodes and associated distance attribute, and each edge corresponding to a link and having the associated weight of the link; and

wherein;

step (a) generates the temporary list of one or more nodes effected by a change of an edge weight, each entry of the temporary list having the associated parent node, a new distance attribute resulting from the weight change, and a distance change;

step (c) updates the one or more paths defined in the temporary tree data structure by;

(c1) updating the parent and child nodes associated with the node selected in step (b),

(c2) updating, with the distance change, the distance attribute of the selected node and each descendent node of the selected node,

(c3) defining, if necessary, a new distance attribute and a distance change for each node receiving an edge from either the node selected in step (b) or a descendent node of the selected node, and

(c4) adding to the temporary list each node receiving an edge in step (f) and the corresponding parent node, new distance attribute, and distance change; and

for step (d) repeating the steps (b) and (c) until the temporary list is empty, the updated temporary tree data structure being the updated SPT.