Method and apparatus for selecting between multiple equal cost paths
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23)
-
Specification