Patent Publication Number: US-6704320-B1

Title: Dynamic algorithm for determining a shortest path tree between network nodes

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to routing of information packets in a communications network, and, more particularly, to a router determining shortest paths for communicating packets between nodes based on shortest-path trees. 
     2. Description of the Related Art 
     In an interconnected communications network employing packets, such as the Internet, routing protocols are employed by routers of the network to determine how packets are to be forwarded between nodes. Packets received by a node&#39;s router are forwarded to other nodes based on a forwarding table of an interior routing protocol. Interior routing protocols exchange network topology and link-state information (“network topology information”) among routers to allow the node&#39;s router to construct the corresponding forwarding table. An example of a widely-used interior routing protocol is the Open Shortest Path First (OSPF) protocol, as outlined in J. Moy, “OSPF Version 2,” Internet Draft, Request for Comment (RFC) 2178, July, 1997. In addition, some interior routing protocols associate a link cost, known in the art as a weight, with each link between nodes. The link cost may be associated with, for example, available bandwidth or revenue generated by the link. When link-state information (e.g., status, utilization, connectivity, or bandwidth) is exchanged between routers, each router in a regional network has a complete description of the network&#39;s topology. 
     Each router computes paths between nodes, and uses the weights to calculate a set of preferred paths. Each of the set of preferred paths that is computed has a minimum total weight for the path between the particular router and each other router in the region. This set of preferred paths may be defined with a shortest path tree (SPT). A forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet along the shortest path of the SPT to its destination. The SPT may be calculated using an algorithm such as Dijkstra&#39;s algorithm, described in E. Dijkstra, “A note: two problems in connection with graphs,” Numerical Mathematics, vol. 1, 1959, pp. 269-271. 
     When the network topology of a regional network changes (e.g., a link fails, recovers, or changes its routing weights), each router in the region detects the change and updates the network topology information stored by the router. After updating its stored network topology information, each router recalculates a new SPT and forwarding table. In routers of the prior art, the recalculation deletes the current SPT and recalculates the new SPT from scratch (this type of recalculation method is known in the art as a statis algorithm). 
     However, for most changes in network topology, the new SPT does not differ significantly from the old SPT, and in many cases the old and new SPTs are the same. Statis algorithms that recompute the new SPT from scratch are inefficient because they do not take advantage of available information about the prior (outdated) SPT. Another drawback of statis algorithms is that multiple routes of the same shortest distance may coexist from one router to another router. When the SPT is re-computed from scratch, a different one of the coexisting multiple routes may be selected for the SPT than was selected by a prior computation. If a new path of the coexisting multiple routes is selected each time the new SPT is computed, the router may change many entries in its forwarding table frequently and unnecessarily, increasing the risk of routing errors or routing failures associated with implementing the change in routing. 
     To illustrate, FIG. 1 shows a regional network  100  of an Internet Service Provider (ISP) comprising four routers  101 ,  102 ,  103 , and  104 . The routers  101 ,  102 , and  104  are commonly known as access routers and provide users a connection to the network  100 . Router  103  connects the network  100  to a backbone packet network  105  that may be, for example, the Internet. Initially, link  106  (shown by a dashed arrow) between  103  and  104  is not in service (i.e., disconnected or not provisioned). The solid arrows indicate links which are preferred paths defined by an SPT calculated and stored in router  101  (commonly termed as an SPT “rooted at” router  101 ). The numeral next to each solid arrow in FIG. 1 is the weight assigned to the corresponding link. The forwarding table in router  101  contains forwarding entries, each forwarding entry corresponding to next-hop information of each user&#39;s network connection through router  103  to the backbone packet network  105 . Initially, all packets routed from router  101  to backbone packet network  105  pass through router  102 . However, if the link between routers  103  and  104  is established (i.e., either provisioned or recovered) and has a link weight of 1, the network topology changes and the SPT rooted at router  101  must be recomputed. 
     When the SPT is recomputed from scratch, the result may indicate that all paths to the backbone packet network  105  from router  101  now pass through router  104 . Router  101  then changes the next-hop information for some or all network connections passing through router  103  to now pass through router  104 . However, the path weight for the previous and new paths are the same and the changes may not be necessary. These changes may correspond to several thousand updates in the forwarding table of router  101 , many of which may be redundant updates. In addition to redundant updates in forwarding tables, unnecessary changes in the SPT may also cause undesirable fluctuation of traffic load on any given route. 
     SUMMARY OF THE INVENTION 
     The present invention relates to routing packets in a packet network based on a shortest path tree (SPT) defining paths between nodes in the network. In accordance with the present invention, a temporary list of nodes in the network is generated for a current SPT, the list including nodes affected by a change in the weight of a link between two nodes in the network. The change in weight 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 selection process selects 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 process updates 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. The selection process and update process are repeated until the list is empty to generate an updated SPT. A router, for example, then routes one or more packets in accordance with the updated SPT. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which: 
     FIG. 1 shows a regional network connected to a backbone packet network and comprising four routers with one or more routers employing a prior art method of updating a shortest path tree; 
     FIG. 2 shows network of six nodes and a shortest path tree for the network; 
     FIG. 3 shows a new shortest path tree determined after the edge of the network shown in FIG. 2 changes weight; 
     FIG. 4 illustrates a ball-and-string model for the network shown in FIG. 2 as may be employed with the present invention; 
     FIG. 5 illustrates a ball-and-string model for the network shown in FIG. 3 as may be employed with the present invention; 
     FIG. 6A shows an exemplary implementation of pseudo-code for a static version initialization step employed with the dynamic SPT algorithm of the present invention; 
     FIG. 6B shows an exemplary implementation of pseudo-code for a dynamic version initialization step of the dynamic SPT algorithm of the present invention; 
     FIG. 6C shows an exemplary implementation of pseudo-code for a node selection step of the dynamic SPT algorithm of the present invention; 
     FIG. 6D shows an exemplary implementation of pseudo-code for a distance update step of an exemplary implementation of the dynamic SPT algorithm of the present invention; 
     FIG. 6E shows pseudo-code for a node search step of the dynamic SPT algorithm of the present invention; and 
     FIG. 7 shows a block diagram of a processing section of a router generating a shortest path tree with the dynamic SPT algorithm of the present invention. 
    
    
     DETAILED DESCRIPTION 
     In accordance with the present invention, 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 on an existing SPT in the router. The dynamic SPT algorithm emulates a ball and string model by iteratively selecting nodes of the existing SPT for consideration and update of the parent node, child nodes, and distance attributes based on the criterion of maximum decrement. In the ball and string model, a node in the existing SPT is selected in each iteration based on the greatest potential decrease (or least increase) in its distance attribute, which may be termed the criterion of maximum decrement. 
     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&#39;s weight. Each set of strings connecting the balls between the root and a particular node defines a path. 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 the 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. 
     Definitions and the Shortest Path Tree 
     A directed graph G of nodes and edges (links with weights) is defined as G=(V, ε), where V denotes a set of nodes and ε denotes a set of edges in the graph G. 
     An integer value N denotes the total number of nodes in the set V, and an integer value ED denotes the total number of edges in the set ε. The graph G consists of a root node denoted by n 0 , and all other nodes are denoted as n 1 , . . . , n N−1 . Each of the nodes n 1 , . . . , n N−1  may be reached from the root node n 0  by a directed path in G. The length of a path is the sum of the weights of the edges in that path. Each edge e i  (0≦i≦ED-1) has an associated positive weight (cost) of w i . 
     A rooted tree T is a subgraph of G such that every node in G is reachable from the root n 0  through a unique directed path using only edges in the rooted tree T. The distance of a node n i  (i=1, . . . , N−1) in T is the length of the directed path in the rooted tree T connecting n 0  to n i . The shortest distance of a node n i  is the length of a shortest path in G connecting n 0  to n i . A rooted tree T is said to be a shortest path tree (SPT) for the graph G if the distance to every node n i  in rooted tree T is the shortest distance to n i  in G. Multiple SPTs may exist within a given graph G, but each of the shortest distances to the nodes is unique. 
     Determining the Shortest Path Tree 
     With these definitions, the SPT for the root node n 0  may be determined. To determine an SPT, the solution of the SPT by calculation (the “SPT problem”) may be formulated as an SPT optimization problem employing linear programming techniques. Liner programming techniques are known in the art and are described in, for example, David G. Luenberger, “Linear and Nonlinear Programming,” Addison-Wesley (1984). Both primal and dual formulations of the SPT problem employing linear programming techniques may be employed and are known in the art. The following describes the dual formulation as may be employed with the ball-and-string model of the present invention. 
     For every directed edge e i  connecting node n j  to node n k , a (row) vector {overscore (v)} i  is created having a dimension of N (equal to the number of nodes). The N-dimensional row vector {overscore (v)} i  contains all entries set to 0 except for the j th  entry set to a ‘−1’ and the k th  entry set to a ‘+1’. Concatenation of all ED vectors {overscore (v)} i  results in a connectivity matrix A having a dimension ED×N. An N-dimensional (column) vector {overscore (u)}is defined such that the i th  entry u i  corresponds to a distance of node n i  from the root node n 0 , one possible entry u i  is a potential shortest (or Euclidean) distance. If u i *is defined as the shortest distance of node n i  (u 0 *=0), then the difference between shortest distances of nodes n j  and n i  is u j *−u i *≦w l , where w l  is the weight of the edge connecting n i  to n j . Thus, if {overscore (w)} denotes the (column) vector of all edge weights w l  and {overscore (u)}* represents the vector of shortest distances, then {overscore (u)}* satisfies the feasibility constraint as given in equation (1):                  A        u   _       ≤     w   _       ;       u   0     =   0.             (   1   )                         
     There are infinitely many vectors {overscore (u)} that satisfy the above matrix inequality and only one of them corresponds to the vector of shortest distances {overscore (u)}*. The vector of shortest distances {overscore (u)}* may be determined by solving the following linear optimization problem defined by the maximization given in equation (2): 
      max( {overscore (b)}   T   {overscore (u)} )  (2) 
     where the solution of equation (2) is subject to the feasibility constraint given by equation (1), and where {overscore (b)} is an N-dimensional vector with each entry equal to 1. The value of ({overscore (b)} T {overscore (u)}) represents the sum of the potential distances of all nodes. 
     The feasibility constraint of equation (1) ensures that the difference between the distances u i  and u j  associated with nodes n i  and n j  is n 0  greater than the weight of the edge connecting the nodes. This is true for the case of an SPT where the distance u i  is the length of a shortest path from n 0  to n i . The vector of shortest distances {overscore (u)}* may be determined by maximizing the sum of the potential distances u i  of all nodes, while respecting the feasibility constraint of equation (1). 
     In order to determine an SPT from the solution of the vector of shortest distances {overscore (u)}* of the linear optimization problem of (2), the vector of shortest distances {overscore (u)}* may be substituted into the feasibility constraint of equation (1). If the row i provides the matrix equality for equation (1), the corresponding edge e i  may be used for the SPT. 
     Ball-and-String Model 
     The linear programming formulation of the SPT problem may be illustrated with a ball-and-string model. A collection of balls represents the graph G, each of the balls corresponding to a node in V. Each edge e i  has a corresponding weight w i &gt;0 connecting adjacent nodes n i  and n k  in the graph G. Weight w i  corresponds to an inelastic string of length w i  that connects the balls representing nodes n j  and n k . The vector u i  denotes the Euclidean distance between the balls representing n 0  and n i . For the following, the terms “ball” and “node” are used interchangeably. 
     Since none of the strings may stretch beyond its defined length, the vector of Euclidean distances {overscore (u)} always satisfies the feasibility constraint of equation (1). Moreover, a string becomes “tight” when the Euclidean distance between the two attached nodes equals its length. The optimal solution of equation (2) is determined by sequentially pulling the balls (in the same direction) so as to maximize their Euclidean distances from the ball representing the root node n 0 . For the dynamic SPT algorithm, this operation of the ball and string model is the maximum decrement criterion for the distance change for a ball (node) when selecting nodes for consideration during the iterative steps. In other words, a maximum decrease or minimum increase in distance of a node from the root node is used to iteratively select each node (the “sequentially pulling” of the ball and string model) to solve the linear programming formulation of the SPT problem. 
     When the balls (nodes) are stretched out from n 0  as much as possible, their distances from the ball representing the root node form a vector {overscore (u)}* that corresponds to the optimal solution for the SPT. If there is only one SPT in the graph, the strings that are tight define the SPT. If there are multiple SPTs, each string that is tight will correspond to an edge that is part of some SPT. 
     Dynamic SPT Algorithm Employing Ball-and-String Model 
     The dynamic SPT algorithm of the present invention is described with the ball-and-string model. The dynamic SPT algorithm may include a calculation of an initial SPT according to the Dijkstra algorithm (i.e., the static SPT), which is briefly described using the ball-and-string model. 
     The iterative execution of the Dijkstra algorithm may be as follows. If a ball corresponding to the root node n 0  is anchored at a fixed position, while other balls are “floating” in the sense that their attached strings are not tight. Initially, all balls are at the same position. In a first iteration, the ball connected to n 0  and having the shortest string (shortest distance to the root node n 0 ) is pulled away from n 0  (always in the same direction) and is anchored in a similar manner to the anchoring of the ball corresponding to n 0 . 
     For a second iteration, the floating ball that has a string connected to at least one of the anchored nodes and is closest (i.e., the smallest distance through that string) to the root node n 0  is selected, This node is then pulled away (along the same direction as before) until that string becomes tight and the ball is then anchored. The procedure of the second iteration is repeated until all floating balls are anchored. The Euclidean distance of an anchored ball from the root ball then represents its shortest distance. The anchored balls and the set of shortest distance paths form the static SPT. 
     Once the static SPT is determined, and when a change in network topology occurs, new routing may be calculated in accordance with the dynamic SPT algorithm. To determine a new SPT from an outdated SPT using the dynamic SPT algorithm, computational complexity and the changes to the topology (root tree) of the outdated SPT are desirably minimized when the method employs the node selection based on the maximum decrement in distance of the ball and string model. The ball-and-string model of the execution of the dynamic SPT algorithm as follows. 
     When the length of a string changes (corresponding to a change of an edge&#39;s weight), two cases are considered: a first case where the distance increases and a second case where distance decreases. When the length of a string increases, the ball corresponding to the root node n 0  is anchored at a fixed position and the remaining balls (nodes) are all moved in the same direction, such as if the balls are allowed to drop under gravity. The ball (node) attached to the lower end of the string (as well as others) moves away (or “falls” under the gravity illustration) from the anchored ball (node no) for some distance until at least one of the strings attached to the moving ball (node) becomes tight. This step sets all nodes to a “floating” condition and allows them to move together at once. As described before, the resulting Euclidean distance of a node n i  from an anchored root node n 0  is equivalent to the shortest distance of n i . 
     When the length of a string decreases, the ball attached to the lower end of the string (as well as others) moves toward (or “rise” under the gravity illustration) the anchored ball (node n 0 ) for some distance. Following the gradual changes in string lengths between nodes (i.e., the sequence of distance changes performed as the balls are allowed to “rise” with the ball-and-string model) corresponds to the optimal execution of the dynamic SPT algorithm. 
     To illustrate, FIG. 2 shows a network  200  comprising six nodes  201  to  206 . The links (edges) between the nodes are illustrated with either dotted or solid arrows, and the numeral adjacent to each arrow is the weight of the corresponding edge. The numeral inside each node, termed a distance attribute, represents the shortest (Euclidean) distance from the root node (node  201 ) to the node of the distance attribute. The distance attribute is the sum of the weights along the shortest path through the network from the root node to the corresponding node. When the link between nodes  201  and  203  has a weight of 8, for example, the SPT rooted at node  201  comprises the solid lines shown in FIG. 2; and the shortest distance of each node  201  to  206  is the number inside each ball (node). 
     In response to a change in network topology, the edge between nodes  201  and  203  changes weight from 8 to 2. This weight change significantly alters the structure of the SPT rooted at node  201 . FIG. 3 shows a new SPT determined after the edge of the network shown in FIG. 2 changes weight. FIGS. 4 and 5 illustrate the ball-and-string models for the networks in FIG.  2  and FIG. 3, respectively. The straight lines represent tight strings (edges) and the curly lines represent loose strings. The numeral adjacent to a string is the corresponding length of the string (which is the weight of the link). The shortest paths from node  201  to all other nodes are composed of the straight lines in the figures. When the link distance between nodes  201  and  203  is reduced from 8 to 2, node  203  is “raised” to a higher level. 
     FIG. 5 shows that some loose strings in the original model of FIG. 4 now become tight (the strings between nodes  202  and  203 ,  203  and  205 , and  205  and  204 ), while other strings become loose (the strings between nodes  201  and  202 ,  201  and  205 , and  202  and  204 ). Consequently, FIG. 5 shows that the affected nodes rearrange themselves into their optimal positions within the SPT defined by the “tight” strings as node  203  is raised to a higher level and letting all other nodes float. When the method of changing the length of the string between  201  and  203  reduces the length gradually, the sequence of distance changes performed when the balls are allowed to “drop” under “gravity” with the ball-and-string model corresponds to the optimal execution of the dynamic SPT algorithm. 
     The following compares calculation of the new SPT using two different methods to dynamically change the tree corresponding to the old SPT into the new SPT. The first method employs the dynamic SPT algorithm of the present invention based on maximum decrement of the distance attribute when an edge changes. The second method uses the shortest distance method such as employed by the Dijkstra algorithm. 
     Returning to FIG. 3, the edge between nodes  201  and  203  that decreases its weight remains in the new SPT and the shortest distance of node  203 , and hence the distance attribute (Euclidean distance), is reduced to 2. Since node  203  has a shortest distance of 2, node  203  may become the parent node of nodes  202  and  205  in the new SPT, further decreasing the potential shortest distance of node  202  from 7 to 6 and the potential shortest distance of node  205  from 10 to 7. The modification of the SPT continues by considering either node  202  or node  205  to incrementally modify the SPT. 
     In accordance with the dynamic SPT algorithm, after the distance attribute of node  203  changes, node  205  is selected for consideration and modification. Node  205  is selected for consideration and modification before node  202  because node  205  has the greatest distance attribute decrease of Δ=3 (10 to 7), rather than Δ=1 (7 to 6). Using this maximum decrement as the selection criterion in accordance with the present invention may reduce the total number of computations for the new SPT. For this case, the parent (parent attribute) of node  205  becomes node  203  and its distance attribute becomes 7. The distance attribute of its child node, node  206 , becomes 9. Next, either node  202  or node  204  may be selected for consideration and modification. Since node  204  has the largest potential maximum decrement Δ of 2 (i.e., the distance attribute changes from 11 to 9, rather than from 7 to 6 for node  202 ), node  204  is selected as a child of n  205  and acquires a distance attribute of 9. Finally, node  202  is considered and modified. Node  202  becomes a child of node  203  and acquires a distance attribute of 6. 
     If the Dijkstra algorithm is employed, which gives preference to nodes with the smallest potential distances, node  202  is selected for modification before node  205  because node  202 &#39;s potential shortest distance (modified distance attribute) 6 is smaller than the potential shortest distance (modified distance attribute) 7 of node  205 . At node  202 , the parent of node  202  is changed from  201  to  203  and the distance attribute of node  202  is reduced to 6. Since node  202  has node  204  as a child node (child attribute), the distance attribute of node  204  is reduced from 11 to 10. Since node  204  does not have a directed edge to another neighbor, the distance attribute change of node  204  does not affect any other node. Then, the Dijkstra algorithm returns to node  205 , decreases node  205 &#39;s distance attribute to 7, and then defines node  205  as a child attribute of node  203 . Since node  206  is a child node of node  205 , the distance attribute of node  206  is reduced from 12 to 9. Finally, the distance attribute of node  204  is modified a second time by decreasing the distance attribute from 10 to 9 since node  204  is now a child of node  205 . 
     Comparing the first method employing the dynamic SPT algorithm with the second method employing the Dijkstra algorithm illustrates the efficiency of the dynamic SPT algorithm. When nodes  205  and  204  are selected for modification of the SPT before selecting node  202 , as is done by the dynamic SPT algorithm, the total number of computations required is reduced. Specifically, node  204  is considered in only one step by the dynamic SPT algorithm. The distance attribute of node  204  changes directly from 11 to 9, rather than the two steps (i.e., first from 11 to 10 and then from 10 to 9) of the Dijkstra algorithm. The dynamic SPT algorithm gives priority to the selection of nodes whose potential shortest distance decreases the most (or increases the least) as the new SPT is iteratively generated. 
     The dynamic SPT algorithm may be expressed as steps of a method or software program implemented by a processor of a router to generate new SPTs when a network topology change occurs. FIGS. 6A through 6E provide pseudo-code of an exemplary implementation of the dynamic SPT algorithm employed by a processor of a router. The definitions for values, sets, and elements expressed in FIGS. 6A through 6E are as described previously, with additional definitions as follows. 
     Each directed edge e i  that is an element of the set of edges ε(i.e., e i  ∈ε) has a corresponding weight W(e i ), source node S(e i ), and end node E(e i ). The length or distance of a directed path is defined as the sum of weights W(e i ) of the edges e i  that are contained in the path. Given a set of nodes N that are the set or a subset of nodes V (N ⊂ V), two sets of edges are associated with the set of nodes N. The first set is the set of edges directed into the nodes of the set of nodes N, and is defined as I(N)={e ∈ε|E(e) ∈N}. The second set is the set of edges directed out of the nodes of the set of nodes N, and is defined as O(N)={e ∈ε|S(e) ∈N}. The root node n 0  of the SPT is defined by the variable root(G). 
     A temporary tree data structure {haeck over (T)} is maintained by the dynamic SPT algorithm to track the current SPT of a current iteration of the algorithm. The temporary tree data structure {haeck over (T)} contains a list of every node n of the set of nodes N in the directed graph G, including the node&#39;s corresponding parent attribute P(n, {haeck over (T)}), list of child nodes (child attribute) C(n, {haeck over (T)}), distance attribute D(n, {haeck over (T)}), and Boolean attribute V(n, {haeck over (T)}). The Boolean attribute V(n, {haeck over (T)}) has the values floating and anchored to indicate that the node&#39;s distances may be moved (floating) or the node position is set (anchored) in the temporary tree data structure {haeck over (T)}. When the algorithm completes all steps, the remaining temporary tree data structure {haeck over (T)} is set as the new SPT, denoted by T, and each node n has the corresponding value of the Boolean attribute V(n, {haeck over (T)}) set to anchored. 
     A list Q is maintained that temporarily contains a subset of nodes with at least three attributes. The attributes of a node n may preferably be a potential parent node p for node n, potential distance d for node n, and potential distance change (maximum decrement) Δ for node n (denoted as the set Q={n, (p,d,Δ)}. Three instructions (subroutines) are defined that operate on the list Q. The first instruction is defined as the ENQUEUE (Q, {n, (p,d,Δ)})instruction that adds elements to the list Q. The second instruction is defined as the EXTRACTMIN (Q) instruction that removes elements from the list Q. When the EXTRACTMIN instruction is executed, the element having the smallest value for Δ is selected and removed from the list Q. If more than one element exists with a minimum value of Δ, then the value of d is used to determine which element is selected. If more than one element has a minimum value of Δ and they have equivalent values for d, then any of the values having minimum Δ and d may be selected by the EXTRACTMIN instruction. The third instruction routine is defined as the REMOVE (n,Q) instruction that removes elements and corresponding attributes from the list Q. 
     Two additional subroutines may be defined. The first subroutine B max (n, {haeck over (T)}) determines and stores the set of nodes (including the node n) that contains the descendants of n in the temporary tree data structure {haeck over (T)}. The set of nodes is computed by following the path down the temporary tree data structure {haeck over (T)}. Similarly, the second subroutine B val (n, {haeck over (T)}) determines and stores the set of nodes that are reachable from the node n through a path of anchored nodes in the temporary tree data structure {haeck over (T)}. The set of nodes is computed by following the path down through the anchored nodes of the temporary tree data structure {haeck over (T)} (the Boolean attribute V(n, {haeck over (T)}) of the node has the value anchored) and stopping when a floating node is encountered (the Boolean attribute V(n, {haeck over (T)}) of the node has the value floating ). 
     Returning to FIGS. 6A through 6E, the dynamic SPT algorithm includes an initialization step (beginning at Step  1  at line  601  of FIG. 6A) for either (A) creating an initial SPT (lines  603 - 610  of FIG. 6A) or (B) initializing the dynamic SPT algorithm after a network topology change creates an outdated SPT (lines  611 - 639  of FIG.  6 B). After the initialization process, the new SPT is determined with the interative procedure including node selection Step  2 , distance update Step  3 , and node search Step  4 , which are shown in FIGS. 6C through 6E, respectively. 
     An event, such as a router being provisioned or other network topology change, causes the dynamic SPT algorithm to begin at Step  1  (line  601  of FIG.  6 A). Referring again to FIG. 6A, at line  602  the algorithm determines whether a current SPT exists in the node. If n 0  current SPT exists, the algorithm goes to (A) at line  603  to execute a static version of the algorithm to generate an initial SPT. For each node other than the root node n 0  (root(G)) for which the SPT is generated, the parent and child attributes are each set to the null set (lines  605  and  608 ), the node distance attribute is set to zero (line  606 ), and the Boolean attribute is set to floating (line  607 ). The root node (root(G)) and the corresponding initial entries of the attributes for the root node are added to the list Q with an execution of the ENQUEUE routine (line  609 ). As shown in line  610  of FIG. 6A, the static version then proceeds to Step  2  (line  640  of FIG. 6C) to generate the initial SPT. 
     As the execution of the algorithm is the same for the static version and the dynamic version after initialization (i.e., from Step  2  through Step  4  of FIGS.  6 C- 6 E), the following describes the execution of the algorithm following the description of the initialization step type (B) of the dynamic version. The initialization of the static version is a trivial case, and computes an initial SPT for the root node (root(G)) from scratch. The initial SPT may be calculated by other methods at start-up, and so the present invention is not limited to determining the initial SPT as shown in FIGS.  6 A and  6 C- 6 E. Therefore, the type (A) initialization of lines  602 - 610  of FIG. 6A is optional. 
     If at line  602  of FIG. 6A the algorithm determines that a current SPT exists (i.e., when network topology changes), then the algorithm begins a type (B) initialization for the dynamic version (line  611  of FIG.  6 B). First, the initialization of the dynamic version identifies those nodes that may be affected by the changes in the link states. The potentially affected nodes are those that are no longer connected to the root node (root(G)) through the same shortest path as before. Moreover, the initialization of the dynamic version selecting such set of potentially affected nodes minimizes the number of nodes whose changes in distance are subsequently propagated to descendents in the current (original) SPT and which may be considered and modified. Two cases of updating nodes in the temporary tree data structure {haeck over (T)} of the algorithm are shown in FIG.  6 B: Case  1  in which the weight of edges increase (lines  614 - 628 ), and Case  2  in which the weight of edges decrease (lines  630 - 638 ). In either case, the algorithm proceeds to Step  2  (line  640  of FIG. 6C) to begin the iterative generation of the new SPT. 
     Referring again to FIG. 6B, initially, the temporary tree data structure {haeck over (T)} is set as the current SPT with all nodes having their the Boolean attributes set to anchored. In Case  1 , after initializing the temporary node set {haeck over (N)} to the null set (line  613 ), each edge e i  that has a corresponding increase in weight (e i ∈ε + ) (line  614 ) is updated with the corresponding new increase Γ i  in weight (line  615 ). The algorithm then checks if the edge e i  is in the current SPT (temporary tree data structure {haeck over (T)}) at line  616  (i.e., if the source node of the edge e i  is a parent of an end node of the edge e i  (E(e i )) included in {haeck over (T)}). If the edge e i  is in the current SPT, the algorithm deletes the edge e i  and selects the end node E(e i ) of the edge e i  (lines  616 - 617 ). The algorithm also selects, by execution of subroutine B val (n, {haeck over (T)}) at line  618 , all descendent nodes N d  of the end node E(e i ) that are reachable by nodes that have their Boolean attribute set to anchored in the existing SPT. All such descendent nodes (line  620 ) have their Boolean attribute set to floating (line  621 ) and are then included in the temporary node set {haeck over (N)} (line  622 ). The temporary node set {haeck over (N)} covers all the affected nodes. Moreover, only those nodes that are directly coupled to anchored nodes in the current SPT are considered because the descendent nodes N d  of the nodes in temporary node set {haeck over (N)} are updated in subsequent Steps  2 - 4  of the algorithm. 
     For the current (outdated) SPT, all of the nodes initially have their corresponding Boolean attribute set to anchored (an anchored node). As described previously, when the weight of one or more edges increases, the potentially affected nodes have their Boolean attribute set to floating (a floating node) during the initialization of the dynamic version. Each anchored (source) node S(e i ) is determined that is coupled to an edge (link) directed into a floating (end) node E(e i ) in the temporary node set {haeck over (N)}(lines  623 - 624 ). For such nodes, the potential distance newdist of the anchored (source) node is determined by adding the distance of the anchored (source) node S(e i ) and the weight of the edge connecting the floating (end) node E(e i ) and anchored (source) node S(e i ) (line  625 ). The difference Δ between the old distance attribute of the source node S(e i ) and the potential new distance newdist is also stored (line  626 ). The end node E(e i ) with Boolean attribute set to floating and corresponding attributes Δ, potential distance newdist, and potential new parent (the anchored source node S(e i )) are added to the list Q by executing the ENQUEUE routine (line  627 ). In Case  1 , after determining the set of floating nodes for each edge e i  with new increased weight, the algorithm proceeds to Step  2  (line  629 ). 
     For Case  2  at line  630 , the algorithm determines the set of floating nodes for each edge e i  having a new decrease Γ i  in weight (e i ∈ − ). After updating each edge e i  with the corresponding weight decrease Γ i  (lines  631 - 632 ), the potential new distance newdist of its end node E(e i ) is computed by adding the distance of its source node S(e i ) and the new weight W(e i ) (line  633 ). If this potential new distance newdist is smaller than the old distance attribute of the end node E(e i ) (line  634 ), then the node E(e i ) with corresponding attributes of potential new parent S(e i ), potential new distance newdist, and difference Δ between its old distance attribute and the potential new distance newdist (line  636 ) are added to the list Q by executing the ENQUEUE routine (line  637 ). In Case  2 , after determining and adding to the list Q the set of nodes and corresponding attributes for each edge e i  with new decreased weight, the algorithm proceeds to Step  2  (line  639 ). 
     Once the initialization of the dynamic version is complete, the algorithm proceeds to Step  2  (line  640  of FIG. 6C) to begin generating the new SPT. Since the algorithm employs an iterative procedure, at line  641  a test is made to determine if the list Q contains elements (nodes) of the temporary data tree structure {haeck over (T)} that have attributes that may be updated. If the list Q has no such elements, indicating that the algorithm has completed, the temporary tree data structure {haeck over (T)} is set as the new SPT. When the program has determined the new SPT, the program is terminated (line  642 ). Otherwise, processing proceeds to line  644 . 
     A node y with the smallest value (least positive value or most negative value) for potential distance change Δ is extracted from the list Q by executing the EXTRACTMIN instruction (line  644 ). The EXTRACTMIN instruction returns a nodey in the list Q that has a potential distance change Δ that is either the smallest increase in distance (determined in Case  1 ) or largest decrease in distance (determined in Case  2 ). This selected node y has parent node x, potential distance d, and potential distance change Δ. This selected node y is then updated with its new parent indicated in the temporary tree data structure {haeck over (T)} and the temporary tree data structure {haeck over (T)} is modified accordingly to reflect child and parent node relations (lines  646 - 648 ). All the descendent nodes of the selected node y are then identified and stored as the set denoted by N d  by executing the subroutine B max (y, {haeck over (T)}) (line  649 ). The algorithm then proceeds at line  650  to Step  3  beginning at line  651  of FIG.  6 D. 
     As shown in FIG. 6D, the distance attributes of the selected node y and all of node y&#39;s descendent nodes (denoted by the set N d ) (line  652 ) in the temporary tree data structure {haeck over (T)} are updated. The selected node y together with all its descendent nodes have their corresponding distance attributes updated as their old distance attribute D(n, {haeck over (T)}) incremented by Δ (line  653 ). In addition, the Boolean attributes of the selected node y and all its descendent nodes are set to anchored (line  655 ). If any such node n in the set N d  is already in the list Q (line  660 ), the node will be removed from Q by executing the REMOVE subroutine, and the node is no longer updated or modified. However, if the parent attribute of the node n in list Q is the same as the parent attribute of node n in temporary tree data structure {haeck over (T)}, the node is not removed since this indicates that further modifications to the node will occur. At line  658 , the algorithm proceeds to Step  4  shown in FIG.  6 E. 
     As shown in Step  4  of FIG. 6E, the edges directed out of the set of nodes N d  (denoted as the set O(N d ) are searched and updated (line  660 ). The set O(N d ) includes each end node E(e) that is attached to an edge e directed out of a source node S(e) that is included in the set N d . At line  661 , a test is performed to determine if the potential new distance newdist of the end node E(e) (which is equal to W(e) plus the distance attribute of the source node S(e)) is smaller than the old distance attribute of the end node E(e), or if the end node E(e) has its Boolean attribute set to floating,. If the test is true, the potential new distance newdist of E(e) is set to the old potential distance newdist minus the distance of E(e) (line  664 ), and potential new distance change Δ is set to W(e) plus the distance of S(e) (line  665 ). The ENQUEUE instruction is executed and the end node E(e) added to the list Q for further updating (line  667 ). The list Q, therefore, now has the node E(e) added with its potential new distance newdist, change in distance Δ, and its potential new parent p=S(e). After step  4  is completed, processing returns to Step  2  (i.e., line  669  of Step  4  returns to line  640  of Step  2 ), and the process repeated until the list Q is empty. 
     FIG. 7 shows a block diagram of an exemplary processing section  700  of a router, e.g., router of node  201  of FIGS. 2 and 3, employing the dynamic SPT algorithm in accordance with the present invention. Processing section  700  includes a control processor  701 , routing processor  702 , packet classifier  703 , input link interface  704 , buffer section  705 , route allocation processor  706 , output link interface  707 , and memory  710 . An implementation of the processing section and link interfaces of such a router may be embodied in, for example, a PacketStar 6400 router, available from Lucent Technologies Inc. of Murray Hill, N.J. 
     Routing processor  702  may monitor and receive network topology information in accordance with the open shortest path first (OSPF) protocol. The network topology information may be stored in a database in memory  710  for use by the dynamic SPT algorithm of the present invention. Routing processor  702  generates an SPT as described previously, and a corresponding forwarding table. 
     Control processor  701  may coordinate functions of the processing section, including loading new routing information and packet filters into packet classifier  703  based on forwarding tables generated from an SPT. Control processor  701  may also monitor control messages received from the network that follow the OSPF protocol to determine if a new SPT should be calculated. 
     Packets of one or more packet flows are received at the input link interface  704  of the processing section  700 . Input link interface  704  may define one or more input ports, and may comprise the receive sections of one or more line termination cards that terminate at least one transmission line. The termination cards, such as T 1 , T 3  or OC- 3  termination cards, support one or more links through the bandwidth of each transmission line. Packets received from the input link interface are queued for processing in buffer section  705 , and may be concurrently provided to the packet classifier  703 . Buffer section  705  may include buffers allocated to each input port. Packet classifier  703  contains one or more packet filters determining filter rules to be applied to each received packet. Based on the filter rules, route allocation processor  706 , which may be a cross-bar switch, redirects the packet from the buffer section  705  to one or more corresponding output ports of the output link interface  707 . Output link interface  707  may define one or more output ports, and may comprise transmit sections of one or more line termination cards that terminate at least one transmission line. 
     While the exemplary embodiments of the present invention have been described with respect to steps of method, the present invention is not so limited. As would be apparent to one skilled in the art, various functions may be implemented in hardware by circuit elements and may also be implemented in the digital domain as processing steps in a software program. Such software may be employed in, for example, a digital signal processor, micro-controller or general purpose computer. 
     The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits. 
     It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as expressed in the following claims.