Method and apparatus for selecting between multiple equal cost paths

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.

What is claimed is: 
     
         1 . A method of selecting between a plurality of equal-cost paths in a communication network, the method comprising:
 determining a set of equal-cost paths between a pair of nodes of the communication network, each equal-cost path comprising at least one link;   assigning a respective unique identifier to each link of the at least one link on each of the equal-cost paths;   forming a path identifier for each of the equal-cost paths to form a plurality of path identifiers, each path identifier corresponding to one equal-cost path in the set of equal-cost paths and being formed by ordering link identifiers of the at least one link on a respective equal-cost path using a first ordering criterion and concatenating the link identifiers in that order; and   selecting at least one equal-cost path of the set of equal-cost paths by comparing the plurality of path identifiers.   
     
     
         2 . The method of  claim 1 , wherein:
 each node of the communication network has a unique node identifier; and   assigning the respective unique identifier to each link of the at least one link on each of the equal-cost paths comprises forming a respective link identifier by concatenating ordered node identifiers of two nodes of the communication network that are connected by the each link.   
     
     
         3 . The method of  claim 2 , further comprising applying an identical inversion function to each of the link identifiers to create inverted link identifiers, wherein forming a path identifier for each of the equal-cost paths comprises ordering the inverted link identifiers of the at least one link on the respective equal-cost path using the first ordering criterion and concatenating the inverted link identifiers in that order. 
     
     
         4 . The method of  claim 3 , wherein the inversion function is an XOR function. 
     
     
         5 . The method of  claim 2 , further comprising applying an inversion function to all the node identifiers to create inverted node identifiers, wherein assigning the respective unique identifier to the each link of the at least one link on the each of the equal-cost paths comprises forming the link identifier by concatenating the ordered inverted node identifiers of the two nodes of the communication network that are connected by the each link. 
     
     
         6 . The method of  claim 5 , wherein the inversion function is an XOR function. 
     
     
         7 . The method of  claim 2 , wherein the concatenated ordered node identifiers used to form the link identifiers are ordered such that a lowest node identifier forms most significant bits of the link identifier and a highest node identifier forms least significant bits of the link identifier. 
     
     
         8 . The method of  claim 1 , wherein the first ordering criterion is independent of an order in which the links corresponding to the link identifiers appear on the each equal-cost path. 
     
     
         9 . The method of  claim 1 , further comprising ordering the plurality of path identifiers into an ordered list using a second ordering criterion, wherein selecting the at least one equal-cost path of the set of equal-cost paths comprises selecting the equal-cost path that appears first or last in the ordered list of the path identifiers. 
     
     
         10 . The method of  claim 9 , wherein selecting the at least one equal-cost path of the set of equal-cost paths by comparing the plurality of path identifiers comprises selecting two of the equal-cost paths by selecting the equal-cost paths that appear first and last in the ordered list of the path identifiers. 
     
     
         11 . The method of  claim 1 , wherein ordering the link identifiers comprises sorting the link identifiers from lowest to highest. 
     
     
         12 . A method of operating a communication network, the communication network comprising a plurality of nodes interconnected by links, the method comprising, at each node:
 determining a set of equal-cost paths between a pair of nodes of the communication network, each equal-cost path comprising at least one link;   assigning a respective unique identifier to each link of the at least one link on each of the equal-cost paths;   forming a path identifier for each of the equal-cost paths to form a plurality of path identifiers, each path identifier corresponding to one equal-cost path in the set of equal-cost paths and being formed by ordering link identifiers of the at least one link on a respective equal-cost path using a first ordering criterion and concatenating the link identifiers in that order; and   selecting at least one equal-cost path of the set of equal-cost paths by comparing the plurality of path identifiers.   
     
     
         13 . The method of  claim 12 , wherein:
 each node of the communication network has a unique node identifier; and   assigning the respective unique identifier to each link of the at least one link on each of the equal-cost paths comprises forming a respective link identifier by concatenating ordered node identifiers of two nodes of the communication network that are connected by the each link.   
     
     
         14 . The method of  claim 13 , wherein each node identifier is administratively assigned from separate ranges of node identifiers according to a node classification. 
     
     
         15 . The method of  claim 13 , wherein nodes on an edge of the communication network are assigned node identifiers from a low range and the nodes on an interior of the communication network are assigned node identifiers from a high range. 
     
     
         16 . The method of  claim 13 , wherein the concatenated ordered node identifiers used to form the link identifiers are ordered such that a lowest node identifier forms most significant bits of the link identifier and a highest node identifier forms least significant bits of the link identifier. 
     
     
         17 . The method of  claim 12 , wherein the first ordering criterion is independent of an order in which the links corresponding to the link identifiers appear on the each equal-cost path. 
     
     
         18 . The method of  claim 12 , further comprising ordering the plurality of path identifiers into an ordered list using a second ordering criterion, wherein selecting the at least one equal-cost path of the set of equal-cost paths comprises selecting the equal-cost path that appears first or last in the ordered list of the path identifiers. 
     
     
         19 . The method of  claim 18 , wherein selecting the at least one equal-cost path of the set of equal-cost paths by comparing the plurality of path identifiers comprises selecting two of the equal-cost paths by selecting the equal-cost paths that appear first and last in the ordered list of the path identifiers. 
     
     
         20 . The method of  claim 12 , wherein ordering the link identifiers comprises sorting the link identifiers from lowest to highest.