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 - 20 . (canceled) 
     
     
         21 . A method of determining forwarding information for use in forwarding packets at a forwarding node of a packet-forwarding network, each node of the network having a unique node identifier, the method comprising:
 determining lowest cost paths between a first node and a second node of the network;   determining that a plurality of lowest cost path have substantially equal cost, at least one of the lowest cost paths traversing a largest number of nodes and at least one other of the lowest cost paths traversing fewer than the largest number of nodes; and   selecting a lowest cost path that satisfies a condition that:   processing the plurality of lowest cost paths according to the steps of:   for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a first ordering criterion to derive a respective path identifier;   for each lowest cost path traversing fewer nodes than the largest number of nodes, adding at least one additional identifier to the corresponding path identifier, the adding being consistent with the first ordering criterion; and   ordering the path identifiers according to a second ordering criterion;   would put the path identifier of the selected lowest cost path at one extreme of the ordered path identifiers.   
     
     
         22 . The method of  claim 21 , further comprising selecting the lowest cost path that satisfies the condition by:
 for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a first ordering criterion to derive a respective path identifier;   for each lowest cost path traversing fewer nodes than the largest number of nodes, adding at least one additional identifier to the corresponding path identifier, the adding being consistent with the first ordering criterion;   ordering the path identifiers according to a second ordering criterion; and   selecting a lowest cost path having a path identifier at one extreme of the ordered path identifiers.   
     
     
         23 . The method of  claim 22 , wherein adding at least one additional identifier comprises:
 when the first ordering criterion is increasing ordering, adding at least one additional identifier, each additional identifier being deemed to be higher than all node identifiers; and   when the first ordering criterion is decreasing ordering, adding at least one additional identifier, each additional identifier being deemed to be lower than all node identifiers.   
     
     
         24 . The method of  claim 23 , wherein adding at least one additional identifier comprises adding additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a number of identifiers not less than the largest number of nodes. 
     
     
         25 . The method of  claim 23 , wherein adding at least one additional identifier comprises adding additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a common number of identifiers. 
     
     
         26 . The method of  claim 22 , wherein:
 the first ordering criterion is an increasing ordering criterion; and   adding at least one identifier comprises adding at least one additional identifier having a value deemed to be greater than any node identifier to a trailing end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes.   
     
     
         27 . The method of  claim 22 , wherein:
 the first ordering criterion is a decreasing ordering criterion; and   adding at least one identifier comprises adding at least one additional identifier having a value deemed to be lower than any node identifier to a trailing end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes.   
     
     
         28 . The method of  claim 22 , wherein:
 the first ordering criterion is an increasing ordering criterion; and   adding at least one identifier comprises adding additional identifiers having a value deemed to be lower than any node identifier to a leading end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until all path identifiers have a common number of identifiers.   
     
     
         29 . The method of  claim 22 , wherein:
 the first ordering criterion is a decreasing ordering criterion; and   adding at least one identifier comprises adding additional identifiers having a value deemed to be greater than any node identifier to a leading end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until all path identifiers have a common number of identifiers.   
     
     
         30 . The method of  claim 22 , wherein adding at least one additional identifier comprises adding additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a number of identifiers equal to the largest number of nodes. 
     
     
         31 . The method of  claim 22 , wherein the first ordering criterion is a lexicographic ordering criterion. 
     
     
         32 . A network node comprising at least one processor and at least one processor-readable storage medium storing instructions for execution by the at least on processor to determine forwarding information for use in forwarding packets at a forwarding node of a packet-forwarding network in which each node of the network has a unique node identifier, the instructions comprising:
 instructions executable to determine lowest cost paths between a first node and a second node of the network;   instructions executable to determine that a plurality of lowest cost path have substantially equal cost, at least one of the lowest cost paths traversing a largest number of nodes and at least one other of the lowest cost paths traversing fewer than the largest number of nodes; and   instructions executable to select a lowest cost path that satisfies a condition that:   processing the plurality of lowest cost paths according to the steps of:   for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a first ordering criterion to derive a respective path identifier;   for each lowest cost path traversing fewer nodes than the largest number of nodes, adding at least one additional identifier to the corresponding path identifier, the adding being consistent with the first ordering criterion; and   ordering the path identifiers according to a second ordering criterion;   would put the path identifier of the selected lowest cost path at one extreme of the ordered path identifiers.   
     
     
         33 . The network node of  claim 32 , further comprising instructions executable to select the lowest cost path meeting the condition, comprising:
 instructions executable to sort, for each lowest cost path, respective node identifiers assigned to nodes traversed by the lowest cost path according to a first ordering criterion to derive a respective path identifier;   instructions executable to add, for each lowest cost path traversing fewer nodes than the largest number of nodes, at least one additional identifier to the corresponding path identifier, the adding being consistent with the first ordering criterion;   instructions executable to order the path identifiers according to a second ordering criterion; and   instructions executable to select a lowest cost path having a path identifier at one extreme of the ordered path identifiers.   
     
     
         34 . The network node of  claim 33 , wherein the instructions executable to add at least one additional identifier comprise instructions executable:
 when the first ordering criterion is increasing ordering, to add at least one additional identifier, each additional identifier being deemed to be higher than all node identifiers; and   when the first ordering criterion is decreasing ordering, to add at least one additional identifier, each additional identifier being deemed to be lower than all node identifiers.   
     
     
         35 . The network node of  claim 33 , wherein the instructions executable to add at least one additional identifier comprises instructions executable to add additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a number of identifiers not less than the largest number of nodes. 
     
     
         36 . The network node of  claim 33 , wherein the instructions executable to add at least one additional identifier comprises instructions executable to add additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a common number of identifiers. 
     
     
         37 . The network node of  claim 33 , wherein:
 the first ordering criterion is an increasing ordering criterion; and   the instructions executable to add at least one identifier comprise instructions executable to add at least one additional identifier having a value deemed to be greater than any node identifier to a trailing end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes.   
     
     
         38 . The network node of  claim 33 , wherein:
 the first ordering criterion is a decreasing ordering criterion; and   the instructions executable to add at least one identifier comprise instructions executable to add at least one additional identifier having a value deemed to be lower than any node identifier to a trailing end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes.   
     
     
         39 . The network node of  claim 33 , wherein:
 the first ordering criterion is an increasing ordering criterion; and   the instructions executable to add at least one identifier comprise instructions executable to add at least one additional identifier having a value deemed to be lower than any node identifier to a leading end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes.   
     
     
         40 . The network node of  claim 33 , wherein:
 the first ordering criterion is a decreasing ordering criterion; and   the instructions executable to add at least one identifier comprise instructions executable to add additional identifiers having a value deemed to be greater than any node identifier to a leading end of the respective path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until all path identifiers have a common number of identifiers.   
     
     
         41 . The network node of  claim 33 , wherein the instructions executable to add at least one additional identifier comprise instructions executable to add additional identifiers to each path identifier for each lowest cost path traversing fewer nodes than the largest number of nodes until each path identifier has a number of identifiers equal to the largest number of nodes. 
     
     
         42 . The network node of  claim 33 , wherein the first ordering criterion is a lexicographic ordering criterion.