Patent ID: 7209975

Claim:
A method of establishing connections between source network elements and destination network elements in a communication network comprising a plurality of first network elements, the method comprising: partitioning the first network elements into at least two areas wherein a shared network element is shared between the at least two areas; assigning values to links between the first network elements; for each of the connections: generating a working path between one of the source network elements and one of the destination network elements through the shared network element; generating a first backup sub-path within a first one of the at least two areas between the one of the source network elements and the shared network element; and generating a second backup sub-path within a second one of the at least two areas between the shared network element and the one of the destination network elements; wherein generating the working paths, the first backup sub-paths, and the second backup sub-paths comprises employing at least one of an integer linear program and a heuristic operating on the values to determine the working paths, the first backup sub-paths, and the second backup sub-paths.