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 determining forwarding information for use in forwarding packets at a first node of a packet-forwarding network, each node of the network having a unique node identifier, the method comprising:
determining, by a network node having a processor, shortest paths between the first node and a second node of the network;
determining, by the network node, when a plurality of shortest paths have substantially equal-cost;
forming, by the network node for each substantially equal-cost path, a set of node identifiers which define the set of nodes in the path;
ordering, by the network node, each set of node identifiers using a first ordering criterion to form a path identifier, wherein the first ordering criterion is independent of an order in which node identifiers appear in the path;
selecting, by the network node, between the plurality of equal-cost paths by comparing the path identifiers.
2. A method according to claim 1 where determining when the plurality of shortest paths have substantially equal-cost comprises determining when the plurality of shortest paths have exactly equal-cost.
3. A method according to claim 1 wherein the first ordering criterion creates a totally ordered set of node identifiers.
4. A method according to claim 1 wherein the first ordering criterion is one of: increasing lexicographic order, decreasing lexicographic order.
5. A method according to claim 1 further comprising ordering the plurality of path identifiers into an ordered list using a second ordering criterion.
6. A method according to claim 5 wherein the second ordering criterion creates a totally ordered set of path identifiers; and wherein 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.
7. A method according to claim 6 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; last in the ordered list of path identifiers.
8. A method according to claim 5 wherein the second ordering criterion is one of: increasing lexicographic order, decreasing lexicographic order.
9. A method according to claim 5 further comprising selecting two of the substantially equal-cost paths by at least one of: using different first ordering criteria and a common second ordering criterion; using a common first ordering criterion and different second ordering criteria.
10. A method according to claim 9 wherein the first ordering criteria are: increasing lexicographic order, decreasing lexicographic order; and the second ordering criteria are: increasing lexicographic order, decreasing lexicographic order.
11. A method according to claim 5 further comprising selecting four of the substantially equal-cost paths by: using two different first ordering criteria and a common second ordering criterion; using the same two first ordering criteria and a different second ordering criterion.
12. 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 1 .
13. A method of determining forwarding information for use in forwarding packets at a first node of a packet-forwarding network, each node of the network having a unique node identifier, the method comprising:
determining, by a network node having a processor, shortest paths between the first node and a second node of the network by iteratively forming a shortest path tree;
determining, by the network node while forming the shortest path tree, when a plurality of paths have equal-cost, each equal-cost path comprising a branch which diverges from a divergence node common to the equal-cost paths;
the network node identifying, in each diverging branch, a node identifier using a first selection criterion to form a branch identifier;
selecting, by the network node, between the plurality of branches by comparing the branch identifiers.
14. A method according to claim 13 wherein the first selection criterion uses a total ordering criterion to compare and select a node identifier in each branch.
15. A method according to claim 13 wherein the first selection criterion uses lexicographic order to compare and select a node identifier in each branch.
16. A method according to claim 15 wherein the first selection criterion uses lexicographic order to select one of: a node identifier appearing first in lexicographic order; a node identifier appearing last in lexicographic order.
17. A method according to claim 13 further comprising recording the node identifier which meets the first selection criterion in each of the diverging branches while backtracking to the divergence node.
18. A method according to claim 17 further comprising, at each backwards step, comparing the recorded node identifier with a new node identifier encountered at that step and recording the node identifier which meets the first selection criterion.
19. A method according to claim 13 further comprising selecting between the plurality of branches by selecting a branch identifier using a second selection criterion.
20. A method according to claim 19 wherein the second selection criterion uses a total ordering criterion to compare and select from the branch identifiers.
21. A method according to claim 20 wherein the second selection criterion uses lexicographic order to select a branch identifier from the branch identifiers.
22. A method according to claim 21 wherein the second selection criterion uses lexicographic order to select one of: a node identifier appearing first in lexicographic order; a node identifier appearing last in lexicographic order.
23. A method according to claim 19 further comprising selecting two of the equal-cost paths by at least one of: using different first selection criteria and a common second selection criterion; using a common first selection criterion and different second selection criteria.
24. A method according to claim 23 wherein the first selection criteria are: largest node identifier; smallest node identifier; and the second selection criteria are largest branch identifier; smallest branch identifier.
25. A method according to claim 19 further comprising selecting four of the equal-cost paths by: using two different first selection criteria and a common second selection criterion; using the same two first selection criteria and a different second selection criterion.
26. A method according to claim 13 which selects between the plurality of branches on a pair-wise basis.
27. A method according to claim 13 comprising using Dijkstra's algorithm to iteratively form a shortest path tree.
28. 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 13 .
29. A network node comprising:
a processor configured to:
determine shortest paths between the network node and a second node of a network;
determine when a plurality of shortest paths have substantially equal-cost;
form, for each substantially equal-cost path, a set of node identifiers which define the set of nodes in the path;
order each set of node identifiers using a first ordering criterion to form a path identifier, wherein the first ordering criterion is independent of an order in which node identifiers appear in the path; and
select between the plurality of equal-cost paths by comparing the path identifiers.
30. A network comprising a plurality of network nodes configured according to an arrangement of the network node of claim 29 .