Patent ID: 7680055

Claim:
A method for increasing the capability of a network topology model having a plurality of nodes connected by existing links to maintain service continuity in the presence of faults, said method comprising: (a) adding new links to the network topology model to protect against single node failures; and (b) adjusting link weights for the network topology model to reduce at least one of a cost of network operation, and an imbalance in link utilizations; wherein step (a) comprises the sub-steps of: (1) failing one of the plurality of nodes in the network topology; (2) calculating a first number of disconnected node pairs; (3) selecting a pair of nodes which are neighbors to the failed node; (4) adding a new link between the pair of nodes; (5) calculating a second number of disconnected node pairs; (6) retaining the new link and setting the first number equal to the second number when the second number is less than the first number; (7) repeating sub-steps (3) through (6) for randomly selected combinations of pairs of neighbor nodes until the first number equals zero; (8) repeating sub-steps (1) through (7) for each of the plurality of nodes in the network topology as modified by the addition of the retained links; (9) removing one of the plurality of retained links in the modified network topology; (10) restoring the removed link when the removal causes any node pair to become disconnected for any single node failure; and (11) repeating sub-steps (9) through (11) for each of the plurality of retained new links in the modified network topology.