Patent Document ID: 9143398
Application ID: 13728863
Patent Flag: 1

Claim One:
1. A method implemented by an apparatus for allocating shared spare resource capacity for a plurality of flows on a plurality of working paths in a network, the method comprising: iteratively updating shortest cost link information for a plurality of primary backup paths corresponding to the working paths using initial spare capacity provisioning information for the primary backup paths; iteratively updating spare capacity provisioning information for the primary backup paths according to the updated shortest cost link information for the primary backup paths to provide final spare capacity provisioning information for the primary backup paths, wherein the iteratively updating steps for the primary backup paths comprise: determining, for a plurality of primary backup paths corresponding to the working paths, flow failure information and tabu link information using link information for the working paths and link failure information for the working paths; determining initial spare capacity provisioning information for the primary backup paths using the flow failure information; determining link cost of the initial spare capacity provisioning information; determining new link information for the primary backup paths to minimize shortest path using the link cost and excluding the tabu link information; upon determining that that the new link information provide shorter path than current link information, replacing the current link information with the new link information for the primary backup paths; updating the spare capacity provisioning information for the primary backup paths using the new link information; and repeating the steps to provide final spare capacity information for the primary backup paths; and iteratively updating shortest cost link information for a plurality of secondary backup paths corresponding to the working paths using initial spare capacity provisioning information for the secondary backup paths and the final spare capacity provisioning information for the primary backup paths as obtained by iteratively updating the spare capacity provisioning information for the primary backup paths; and iteratively updating spare capacity provisioning information for the secondary backup paths according to the updated shortest cost link information for the secondary backup paths to provide final spare capacity provisioning information for the secondary backup paths and the primary backup paths, wherein the iteratively updating steps for the secondary backup paths comprise implementing for the secondary backup paths similar determining, replacing, updating and repeating steps as the iteratively updating steps for the primary backup paths, while keeping the final spare capacity information for the primary backup paths fixed in value, thereby to provide final spare capacity information for a plurality of secondary backup paths for the working paths with minimum total capacity shared among the primary backup paths and the secondary backup paths, and wherein, when a working path fails, traffic is routed to a corresponding primary backup path, and when both the working path and the corresponding primary backup path fail, traffic is routed to a corresponding secondary backup.