Patent ID: 7400589

Claim:
A method for computing an optimal route between a first network element (NE) and other NEs of a network using a weighted graph of interconnected nodes that represent the network, the optimal route being subject to at least one subset sequence constraint, the method comprising: defining a respective serial restriction group identifying nodes of the weighted graph that are subject to each subset sequence constraint, wherein the at least one subset sequence constraint includes a strong constraint in which a path cannot allowably extend through any two pairs of consecutive nodes in the serial restriction group; creating a list of temporary labels respectively associated with the nodes of the graph, each node being assigned a primary label, and nodes in each serial restriction group being additionally associated with a backup label, the list initially comprising a most optimal primary label of a root node that represents the first NE; examining the list of temporary labels to identify a most optimal label, and making the identified label permanent to remove it from the list; selectively updating primary labels in the list for every node adjacent the permanently labeled node in order to ensure that the primary labels identify an optimal allowable path from the root node to the adjacent node; and repeating the examining and selectively updating until all primary labels of nodes representing the other NEs are permanent.