Method and apparatus for selecting between multiple equal cost paths

• US 8,248,925 B2
• Filed: 10/07/2009
• Issued: 08/21/2012
• Est. Priority Date: 09/08/2009
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Rockstar Bidco LP (Rockstar Consortium Inc.)
• Inventors: Chiabaut, Jerome, Bragg, Nigel, Allan, David
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ng, Fan
• Application Number:
  US12/574,872
• Publication Number:
  US 20110060844A1
• Time in Patent Office: 1,049 Days
• Field of Search: None
• US Class Current: 370/229
• 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 when creating the path ID 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 through the network. Selective naming of node IDs and use of different inversion functions can be exploited to further optimize distribution of traffic on the network.

Claims

1. An apparatus for selecting between multiple equal cost paths in a communication network, the apparatus comprising:

a memory comprising instructions;

a processor communicatively coupled to the memory, the instructions operative to configure the processor to implement the steps of;

determining, by the apparatus a set of equal cost paths between a pair of nodes on a communication network, each path including a plurality of links;

constructing first link IDs for each link on each of the equal cost paths, each of the first link IDs being created by concatenating the ordered node IDs of nodes that connect to the link on the network;

constructing first path IDs for each of the equal cost paths, each of the first path IDs being created by concatenating first link IDs of the plurality of links forming that path through the communication network;

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

constructing second link IDs for each link on the equal cost paths, each of the second link IDs being created by concatenating a node ID of one of the nodes that connects to the link on the network with an inverted node ID of the other of the nodes that connects to that link on the network, the node IDs being concatenated to form the second link IDs in the same order as determined when constructing the first link IDs;

constructing second path IDs for each of the equal cost paths, each of the second path IDs being created by concatenating second link IDs of the plurality of links forming that path through the communication network; and

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

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

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

4. The apparatus of claim 1, wherein the step of constructing the first path IDs for each of the equal cost paths comprises sorting the link IDs from lowest to highest.

5. The apparatus of claim 1, wherein the step of ranking the first path IDs comprises ordering the first path IDs from lowest to highest.

6. The apparatus of claim 5, wherein the first set of diverse paths through the communication network are the path with the lowest ranked first path ID and the path with the highest ranked first path ID.

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

8. The apparatus of claim 7, wherein the inversion function is an XOR function.

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

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

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

12. The apparatus of claim 1, wherein the step of ranking the second path IDs comprises ordering the second path IDs from lowest to highest.

13. The apparatus of claim 12, wherein the second set of diverse paths through the communication network are the paths with the lowest ranked second path ID and the path with the highest ranked second path ID.

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

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

16. A communication network, comprising:

a plurality of nodes interconnected by links, each node having a node ID and including at least one processor and associated memory, the memory of each node further containing data and instructions which, when loaded into the processor, cause the node to implement a link state routing protocol process to enable the node to exchange network configuration information with the other nodes on the network and to calculate paths through the network, the memory of each node further containing data and instructions which, when loaded into the processor, cause the node to perform a method including the steps of;

determining a set of equal cost paths between a pair of nodes on a communication network, each path including a plurality of links;

constructing first link IDs for each link on each of the equal cost paths, each of the first link IDs being created by concatenating the ordered node IDs of nodes that connect to the link on the network;

constructing first path IDs for each of the equal cost paths, each of the first path IDs being created by concatenating the first link IDs of the plurality of links forming that path through the communication network;

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

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

constructing second path IDs for each of the equal cost paths, each of the second path IDs being created by concatenating the second link IDs of the plurality of links forming that path through the communication network; and

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

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

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

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

20. The apparatus of claim 19, wherein the concatenated ordered node IDs used to form the second link IDs are ordered such that the low node ID forms the most significant bits of the link ID and the high node ID forms the least significant bits of the link ID, and wherein the inversion function is applied to the high node ID.

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

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

23. The apparatus of claim 22, wherein the inversion function is an XOR function.