Tie-breaking in shortest path determination

Abstract

A consistent tie-breaking decision between equal-cost shortest (lowest cost) paths is achieved by comparing an ordered set of node identifiers for each of a plurality of end-to-end paths. Alternatively, the same results can be achieved, on-the-fly, as a shortest path tree is constructed, by making a selection of an equal-cost path using the node identifiers of the diverging branches of the tree. Both variants allow a consistent selection to be made of equal-cost paths, regardless of where in the network the shortest paths are calculated. This ensures that traffic flow between any two nodes, in both the forward and reverse directions, will always follow the same path through the network.

1 - 52 . (canceled) 
     
     
         53 . A method of determining forwarding information for use in forwarding packets at a forwarding node of a packet-forwarding network, the forwarding node having a processor and each node of the network having a unique node identifier, the method comprising:
 determining, by the forwarding node, shortest paths between a first node and a second node of the network;   determining, by the forwarding node, when at least two of the shortest paths have substantially equal-cost;   forming, by the forwarding node for each substantially equal-cost path, a set of node identifiers which define the set of nodes in the path;   ordering, by the forwarding node, each set of node identifiers using a first ordering criterion to form a path identifier, and concatenating the node identifiers in that order to form a path identifier, wherein the first ordering criterion is independent of the order in which node identifiers appear in the path; and   selecting, by the forwarding node, between the plurality of equal-cost paths by comparing the path identifiers.   
     
     
         54 . The method of  claim 53 , wherein determining when the plurality of shortest paths have substantially equal-cost comprises determining when the plurality of shortest paths have exactly equal-cost. 
     
     
         55 . The method of  claim 53 , wherein the first ordering criterion creates a totally ordered set of node identifiers. 
     
     
         56 . The method of  claim 53 , wherein the first ordering criterion is one of increasing lexicographic order and decreasing lexicographic order. 
     
     
         57 . The method of  claim 53 , further comprising ordering the plurality of path identifiers into an ordered list using a second ordering criterion. 
     
     
         58 . The method of  claim 57 , wherein:
 the second ordering criterion creates a totally ordered set of path identifiers; and   selecting between the plurality of equal-cost paths comprises selecting the equal-cost path that appears at one end of the ordered list of path identifiers.   
     
     
         59 . The method of  claim 58 , wherein selecting between the plurality of equal-cost paths comprises selecting the equal-cost path that appears one of:
 first in the ordered list of path identifiers; and   last in the ordered list of path identifiers.   
     
     
         60 . The method of  claim 57 , wherein the second ordering criterion is one of:
 increasing lexicographic order; and   decreasing lexicographic order.   
     
     
         61 . The method of  claim 57 , wherein selecting at least one equal-cost path of the plurality of equal-cost paths by comparing the path identifiers comprises one of:
 selecting two of the substantially equal-cost paths by using two different first ordering criteria to form two sets of path identifiers and a common second ordering criterion to select two different path identifiers, one from each of the two sets; and   selecting two of the substantially equal-cost paths by using a common first ordering criterion to form path identifiers and two different second ordering criteria to select two different path identifiers.   
     
     
         62 . The method of  claim 57 , further comprising selecting four of the substantially equal-cost paths by:
 using two different first ordering criteria and a common second ordering criterion to create two respective ordered lists of path identifiers, each ordered list of path identifiers corresponding to a respective one of the two different first ordering criteria; and   selecting the equal-cost paths corresponding to path identifiers that appear first and last in each of the two ordered lists of path identifiers.   
     
     
         63 . The method of  claim 61 , wherein:
 the common ordering criteria is one of increasing lexicographic order and decreasing lexicographic order; and   the two different ordering criteria are increasing lexicographic order and decreasing lexicographic order.   
     
     
         64 . A forwarding node for use in a packet-forwarding network, comprising:
 a processor; and   a non-transitory processor-readable medium storing instructions executable by the processor:   to determine shortest paths between a first node and a second node of the network;   to determine when at least two of the shortest paths have equal-cost;   to form for each equal-cost path, a set of node identifiers which define the set of nodes in the path;   to select, by the forwarding node, one of the equal-cost paths, the selected equal-cost path having the property that, if the node identifiers assigned to nodes in each equal-cost path are sorted according to a first ordering criterion to derive a path identifier for each equal-cost path, and if the resulting path identifiers are sorted according to a second ordering criterion to derive an ordered list of path identifiers, then the selected equal-cost path is at one extreme of the ordered list of path identifiers.   
     
     
         65 . The forwarding node of  claim 64 , wherein the instructions executable to determine when the plurality of shortest paths have substantially equal-cost comprise instructions executable to determine when the plurality of shortest paths have exactly equal-cost. 
     
     
         66 . The forwarding node of  claim 64 , wherein the first ordering criterion creates a totally ordered set of node identifiers. 
     
     
         67 . The forwarding node of  claim 64 , wherein the first ordering criterion is one of increasing lexicographic order and decreasing lexicographic order. 
     
     
         68 . The forwarding node of  claim 64 , further comprising instructions executable to order the plurality of path identifiers into an ordered list using a second ordering criterion. 
     
     
         69 . The forwarding node of  claim 68 , wherein:
 the second ordering criterion creates a totally ordered set of path identifiers; and   selecting between the plurality of equal-cost paths comprises selecting the equal-cost path that appears at one end of the ordered list of path identifiers.   
     
     
         70 . The forwarding node of  claim 69 , wherein the instructions executable to select between the plurality of equal-cost paths comprises instructions executable to select the equal-cost path that appears one of:
 first in the ordered list of path identifiers; and   last in the ordered list of path identifiers.   
     
     
         71 . The forwarding node of  claim 70 , wherein the second ordering criterion is one of:
 increasing lexicographic order; and   decreasing lexicographic order.   
     
     
         72 . The forwarding node of  claim 70 , wherein the instructions executable to select at least one equal-cost path of the plurality of equal-cost paths by comparing the path identifiers comprises one of:
 instructions executable to select two of the substantially equal-cost paths by using two different first ordering criteria to form two sets of path identifiers and a common second ordering criterion to select two different path identifiers, one from each of the two sets; and   instructions executable to select two of the substantially equal-cost paths by using a common first ordering criterion to form path identifiers and two different second ordering criteria to select two different path identifiers.   
     
     
         73 . The forwarding node of  claim 70 , wherein the instruction further comprise instructions executable to select four of the substantially equal-cost paths by:
 using two different first ordering criteria and a common second ordering criterion to create two respective ordered lists of path identifiers, each ordered list of path identifiers corresponding to a respective one of the two different first ordering criteria; and   selecting the equal-cost paths corresponding to path identifiers that appear first and last in each of the two ordered lists of path identifiers.   
     
     
         74 . The forwarding node of  claim 72 , wherein:
 the common ordering criteria is one of increasing lexicographic order and decreasing lexicographic order; and   the two different ordering criteria are increasing lexicographic order and decreasing lexicographic order.   
     
     
         75 . A computer program product comprising a non-transitory machine-readable medium bearing instructions which, when executed by at least one processor, cause the at least one processor to implement the method of  claim 53 . 
     
     
         76 . A method of determining forwarding information for use in forwarding packets at a forwarding node of a packet-forwarding network, the forwarding node having a processor and each node of the network having a unique node identifier, the method comprising:
 determining, by the forwarding node, shortest paths between a first node and a second node of the network;   determining, by the forwarding node while determining the shortest paths, when at least two of the shortest paths have equal-cost, each equal-cost path comprising a branch which diverges from a divergence node common to the equal-cost paths;   
       selecting, by the forwarding node, in each diverging branch, a node identifier using a first selection criterion to form a branch identifier, the first selection criterion being independent of an order in which nodes corresponding to the node identifiers appear in the branch; and
 selecting, by the forwarding node, between the plurality of branches by comparing the branch identifiers. 
 
     
     
         77 . The method of  claim 76 , wherein the first selection criterion is a total ordering criterion. 
     
     
         78 . The method of  claim 76 , wherein the first selection criterion is lexicographic order. 
     
     
         79 . The method of  claim 78 , wherein the selecting a node identifier comprises selecting one of:
 a node identifier appearing first in lexicographic order;   a node identifier appearing last in lexicographic order.   
     
     
         80 . The method of  claim 76 , wherein selecting a node identifier comprises selecting, in each diverging branch, the respective node identifier which best meets the first selection criterion. 
     
     
         81 . The method of  claim 80 , wherein:
 the diverging branches converge at a convergence node; and   selecting the respective node identifier that best meets the first selection criterion comprises, for each diverging branch:   recording the node identifier of a respective node adjacent to the convergence node on that branch;   processing from the convergence node along the branch toward the divergence node node-by-node until a respective node adjacent to the divergence node is reached while comparing each node identifier with the previously recorded node identifier and recording the node identifier of those two node identifiers which meets the first selection criterion; and   when the respective node adjacent to the divergence node is reached, selecting the recorded node identifier as the respective branch identifier for the branch.   
     
     
         82 . The method of  claim 76 , wherein selecting at least one branch of the plurality of branches comprises comparing branch identifiers using a second selection criterion. 
     
     
         83 . The method of  claim 82 , wherein the second selection criterion is a total ordering criterion. 
     
     
         84 . The method of  claim 83 , wherein the second selection criterion is lexicographic order. 
     
     
         85 . The method of  claim 84 , wherein selecting at least one branch of the plurality of branches comprises selecting one of:
 a branch identifier appearing first in lexicographic order;   a branch identifier appearing last in lexicographic order.   
     
     
         86 . The method of  claim 76 , wherein selecting at least one branch of the plurality of branches comprises successive steps of comparing two of the branch identifiers. 
     
     
         87 . The method of  claim 82 , wherein selecting at least one branch of the plurality of branches by comparing the branch identifiers comprises one of:
 selecting two of the branches by using two different first selection criteria to form two different sets of branch identifiers and a common second selection criterion to select one branch identifier from each of the two sets; and   selecting two of the branches by using a common first selection criterion to form branch identifiers and two different second selection criteria to select two different branch identifiers.   
     
     
         88 . The method of  claim 82 , wherein selecting at least one of the plurality of branches by comparing the branch identifiers comprises selecting four of the branches by:
 using two different first selection criteria, forming two respective sets of branch identifiers, each set of branch identifiers corresponding to a respective one of the two different first selection criteria; and   using two different second selection criteria, selecting two respective branch identifiers from each of the two sets of branch identifiers associated with the two different first selection criteria.   
     
     
         89 . The method of  claim 87 , wherein:
 the common selection criterion is one of largest node identifier and smallest node identifier; and   the two different selection criteria are largest branch identifier and smallest branch identifier.   
     
     
         90 . A computer program product comprising a non-transitory machine-readable storage medium bearing instructions which, when executed by a processor, cause the processor to implement the method of  claim 76 .