Tie-breaking in shortest path determination
View Patent ↗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. A method of selecting a path for use in forwarding packets at a 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 of the network and a second node of the network;
determining that a plurality of lowest cost paths have substantially equal cost; and
selecting a lowest cost path from the plurality of lowest cost paths having substantially equal cost, the selected lowest cost path being a path that would be selected 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;
ordering the path identifiers according to a second ordering criterion; and
selecting a lowest cost path having its path identifier at one extreme of the ordered path identifiers;
wherein the first ordering criterion and the second ordering criterion meet a condition selected from:
(1) the first ordering criterion is an increasing ordering and the second ordering criterion is a modified lexicographic ordering which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the second path before the first path; and
(2) the first ordering criterion is a decreasing ordering and the second ordering criterion is a lexicographic ordering which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the first path before the second path.
2. The method of claim 1 , wherein selecting a lowest cost path comprises:
for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to an increasing ordering criterion to derive a respective path identifier;
ordering the path identifiers according to a modified lexicographic ordering criterion which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the second path before the first path; and
selecting a lowest cost path having its path identifier at one extreme of the ordered path identifiers.
3. The method of claim 2 , wherein sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to an increasing ordering criterion to derive a respective path identifier for each lowest cost path comprises sorting the respective node identifiers according to an increasing lexicographic ordering criterion.
4. The method of claim 1 , wherein selecting a lowest cost path comprises:
for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a decreasing ordering criterion to derive a respective path identifier;
ordering the path identifiers according to a lexicographic ordering criterion which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the first path before the second path; and
selecting a lowest cost path having its path identifier at one extreme of the ordered path identifiers.
5. The method of claim 4 , wherein sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a decreasing ordering criterion to derive a respective path identifier for each lowest cost path comprises sorting the respective node identifiers according to a decreasing lexicographic ordering criterion.
6. The method of claim 1 , wherein:
at least one of the lowest cost paths traverses a largest number of nodes and at least one other of the lowest cost paths traverses fewer than the largest number of nodes; and
selecting a lowest cost path from the plurality of lowest cost paths comprises:
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.
7. The method of claim 6 , 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.
8. The method of claim 7 , 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.
9. The method of claim 7 , 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.
10. The method of claim 9 , wherein the first ordering criterion is an increasing lexicographic ordering criterion.
11. The method of claim 7 , wherein:
the first ordering criterion is an 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.
12. The method of claim 11 , wherein the first ordering criterion is a decreasing lexicographic ordering criterion.
13. The method of claim 7 , 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.
14. The method of claim 13 , wherein the first ordering criterion is an increasing lexicographic ordering criterion.
15. The method of claim 7 , wherein:
the first ordering criterion is an 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.
16. The method of claim 15 , wherein the first ordering criterion is a decreasing lexicographic ordering criterion.