Method and apparatus for selecting between multiple equal cost paths

• US 8,750,820 B2
• Filed: 08/20/2012
• Issued: 06/10/2014
• Est. Priority Date: 09/08/2009
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Rockstar Consortium US LP (Rockstar Consortium Inc.)
• Inventors: Allan, David, Bragg, Nigel, Chiabaut, Jerome
• Primary Examiner(s): Ng, Fan
• Application Number:
  US13/589,372
• Publication Number:
  US 20120307832A1
• Time in Patent Office: 659 Days
• Field of Search: 370/229, 370/235, 370/238, 370/238.1, 455/403, 455/422.1, 455/445
• US Class Current: 455/403
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

Abstract

Each equal cost path is assigned a path ID created by concatenating an ordered set of link IDs which form the path through the network. The link IDs are created from the node IDs on either set of the link. The link IDs are sorted from lowest to highest to facilitate ranking of the paths. The low and high ranked paths are selected from this ranked list as the first set of diverse paths through the network. Each of the link IDs on each of the paths is then renamed, for example by inverting either all of the high node IDs or low node IDs. After re-naming the links, new path IDs are created by concatenating an ordered set of renamed link IDs. The paths are then re-ranked and the low and high re-ranked paths are selected from this re-ranked list as the second set of diverse paths.

Claims

1. A method of selecting between multiple equal cost paths in a communication network, the method comprising:

determining a set of equal cost paths between a pair of nodes on a communication network, each path comprising at least one link;

constructing a first link identifier for each link of the at least one link on each of the equal cost paths, each of the first link identifiers being created by concatenating ordered node identifiers of nodes that connect to the link on the communication network;

constructing a first path identifier for each of the equal cost paths, each of the first path identifiers being created by concatenating first link identifiers of the at least one link forming the respective path through the communication network;

ranking the first path identifiers in a path-independent manner to select a first set of diverse paths through the communication network;

constructing a second link identifier for each link of the at least one link on the equal cost paths, each of the second link identifiers being created by concatenating a node identifier of one of the nodes that connect to the each link on the communication network with an inverted node identifier of other of the nodes that connect to the each link on the communication network, the node identifiers being concatenated to form the respective second link identifiers in the same order as determined when constructing the first link identifiers;

constructing a second path identifier for each of the equal cost paths, each of the second path identifiers being created by concatenating second link identifiers of the at least one link forming the respective equal cost path through the communication network; and

ranking the second path identifiers in a path-independent manner to select a second set of diverse paths through the communication network.

2. The method of claim 1, wherein the concatenated ordered node identifiers used to form the first link identifiers are ordered such that a low node identifier forms the most significant bits of the first link identifier and a high node identifier forms the least significant bits of the first link identifier.

3. The method of claim 1, wherein constructing the first path identifiers comprises sorting the first link identifiers so that the order in which the first link identifiers appear within the first path identifiers is path-independent.

4. The method of claim 1, wherein constructing the first path identifiers comprises sorting the first link identifiers from lowest to highest.

5. The method of claim 1, wherein ranking the first path identifiers comprises ordering the first path identifiers from lowest to highest.

6. The method of claim 5, wherein the first set of diverse paths through the communication network comprise the path with the lowest ranked first path identifier and the path with the highest ranked first path identifier.

7. The method of claim 1, wherein constructing the second link identifiers comprises applying an identical inversion function to one of the node identifiers of each of the links to create the inverted node identifiers.

8. The method of claim 7, wherein the identical inversion function is an exclusive OR (XOR) function.

9. The method of claim 7, wherein the concatenated ordered node identifiers used to form the second link identifiers are ordered such that a low node identifier forms the most significant bits of the second link identifier and a high node identifier forms the least significant bits of the second link identifier, and wherein the identical inversion function is applied to the high node identifier.

10. The method of claim 1, wherein constructing the second path identifiers comprises sorting the second link identifiers so that the order in which the second link identifiers appear within the second path identifiers is path-independent.

11. The method of claim 1, wherein the second link identifiers are ordered from lowest to highest prior to concatenation when forming the second path identifiers.

12. The method of claim 1, wherein ranking the second path identifiers comprises ordering the second path identifiers from lowest to highest.

13. The method of claim 12, wherein the second set of diverse paths through the communication network comprise the path with the lowest ranked second path identifier and the path with the highest ranked second path identifier.

14. The method of claim 1, further comprising applying a first inversion function to all node identifiers before creating the first link identifiers and the second link identifiers to preferentially select a transit node on the communication network through which the first set of diverse paths will pass.

15. The method of claim 14, wherein constructing the second link identifiers comprises applying a second inversion function to one of the nodes identifiers of each of the links to create the inverted node identifiers to enable the second set of diverse paths to be selected that pass through the transit node and diverge away from the transit node.

16. A method of operating a communication network, the communication network comprising a plurality of nodes interconnected by links, the method comprising, at each node:

implementing a link state routing protocol process to enable the node to exchange network configuration information with other nodes on the communication network and to calculate paths through the communication network; and

for each set of equal cost paths between a pair of nodes on the communication network, each path comprising at least one link;

constructing a first link identifier for each link of the at least one link on each of the equal cost paths, each of the first link identifiers being created by concatenating ordered node identifiers of nodes that connect to the link on the communication network;

constructing a first path identifier for each of the equal cost paths, each of the first path identifiers being created by concatenating the first link identifiers of the at least one link forming the respective equal cost path through the communication network;

ranking the first path identifiers in a path-independent manner to select a first set of diverse paths through the communication network;

constructing a second link identifier for each link of the at least one link on the equal cost paths, each of the second link identifiers being created by concatenating a node identifier of one of the nodes that connect to the each link on the communication network with an inverted node identifier of other of the nodes that connect to the each link on the communication network, the node identifiers being concatenated in the same order as determined when constructing the first link identifiers;

constructing a second path identifier for each of the equal cost paths, each of the second path identifiers being created by concatenating the second link identifiers of the at least one link forming the respective equal cost path through the communication network; and

ranking the second path identifiers in a path-independent manner to select a second set of diverse paths through the communication network.

17. The method of claim 16, wherein each node identifier is administratively assigned from separate ranges of node identifiers according to node classification to enable the first set of diverse paths and the second set of diverse paths to diverge at selected locations of the communication network.

18. The method of claim 17, wherein nodes on an edge of the communication network are assigned node identifiers from a low range and nodes on the interior of the communication network are assigned node identifiers from a high range, to cause the first set of diverse paths and the second set of diverse paths to be link-diverse at the edge of the communication network.

19. The method of claim 16, wherein constructing the second link identifiers comprises applying an identical inversion function to one of the node identifiers of each of the links to create the inverted node identifiers.

20. The method of claim 19, wherein the concatenated ordered node identifiers used to form each of the second link identifiers are ordered such that a low node identifier forms the most significant bits of the respective second link identifier and a high node identifier forms the least significant bits of the respective second link identifier, and wherein the identical inversion function is applied to the high node identifier.

21. The method of claim 16, wherein node identifiers of transit nodes are administratively assigned so that the transit nodes become in turn transit points during successive repetitions of the construction of the first link identifiers and the second link identifiers.

22. The method of claim 21, wherein selective inversion functions chosen to match the administratively assigned node identifiers of the transit nodes are serially applied to all node identifiers during iterations of the steps of creating the first link identifiers and the second link identifiers, creating the first path identifiers and the second path identifiers, and ranking the first path identifiers and the second path identifiers, to cause different paths to be selected through each assigned transit node on the communication network in turn during the iterations.

23. The method of claim 22, wherein the selective inversion function is an exclusive OR (XOR) function.