# US 7,609,624 B2 · Method and apparatus for pre-provisioning networks to support fast restoration with minimum overbuild > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,609,624 B2 - Document ID: US7609624B2 - Status: Granted - Kind: B2 - Application number: 10/838,098 - Filed: 2004-05-03 - Published: 2005-11-03 - Granted: 2009-10-27 - Earliest claimed: 2004-05-03 - Assignees: Alcatel-Lucent USA Inc. - Inventors: Mansoor Ali Khan Alicherry; Randeep Singh Bhatia - Web page: https://patentgrep.com/patent/US7609624B2 ## CPC - H04L 12/5601: {Transfer mode dependent, e.g. ATM} - H04L 2012/5627: {Fault tolerance and recovery} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Improved network design techniques are provided. For example, a technique for designing a protection capacity to be reserved in a network comprises the following steps/operations. One or more link capacities associated with a network topology are obtained. The network is assumed to have no pre-existing working traffic. A capacity partition including a working capacity portion and a protection capacity portion is determined for at least one link in the network topology. The protection capacity portion is reserved for rerouting working traffic upon a failure and enabling control over the number of backup tunnels, associated with the at least one link, on which working traffic can be rerouted. Determining the capacity partition substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild. A minimal overbuild may include an overbuild equivalent to no more than two times an overbuild required for an optimal solution. ## Claims ### Claim 1 A method of designing a protection capacity to be reserved in a network, the method comprising the steps of: obtaining one or more link capacities associated with a network topology, wherein the network is assumed to have no pre-existing working traffic; and determining a capacity partition for at least one link in the network topology, the capacity partition comprising a working capacity portion and a protection capacity portion, the protection capacity portion being reserved for rerouting working traffic upon a failure, the capacity partition determination step further comprising the step of initially generating a spanning tree by considering one or more links of the network topology in decreasing order of link capacity and selectively adding the one or more links to the spanning tree to form an acyclic graph, wherein the capacity partition determination step enables control over the number of backup tunnels associated with the at least one link, on which working traffic can be rerouted, and further wherein the capacity partition determination step provides for a link based local failure restoration and a minimal protection capacity reserved in the network. ### Claim 2 (depends on 1) The method of claim 1, wherein a minimal protection capacity comprises a protection capacity equivalent to no more than two times a protection capacity required for an optimal solution. ### Claim 3 (depends on 1) The method of claim 1, wherein the capacity partition determination step further provides for a link based local failure restoration and a minimal protection capacity when working traffic of the at least one link has to be rerouted on a single bypass tunnel. ### Claim 4 (depends on 1) The method of claim 1, wherein the capacity partition determination step further provides for a link based local failure restoration and a minimal protection capacity when working traffic of the at least one link can be split and rerouted on no more than two bypass tunnels. ### Claim 5 (depends on 1) The method of claim 1, wherein the capacity partition determination step further provides for a link based local failure restoration and a minimal protection capacity independent of at least one of a nature of the working traffic and a routing associated with the working traffic. ### Claim 6 (depends on 1) The method of claim 1, wherein the capacity partition determination step further comprises determining the capacity partition in accordance with a spanning tree based methodology. ### Claim 7 (depends on 1) The method of claim 1, wherein the capacity partition determination step further comprises determining the capacity partition in accordance with a 2-edge connected graph based methodology. ### Claim 8 (depends on 1) The method of claim 1, wherein the network topology comprises an optical network topology. ### Claim 9 (depends on 1) The method of claim 1, wherein the network topology comprises a multi-protocol label switching network topology. ### Claim 10 (depends on 1) The method of claim 1, wherein the network topology comprises an asynchronous transfer mode network topology. ### Claim 11 Apparatus for designing a protection capacity to be reserved in a network, comprising: a memory; and at least one processor coupled to the memory and operative to: (i) obtain one or more link capacities associated with a network topology, wherein the network is assumed to have no pre-existing working traffic; and (ii) determine a capacity partition for at least one link in the network topology, the capacity partition comprising a working capacity portion and a protection capacity portion, the protection capacity portion being reserved for rerouting working traffic upon a failure, the capacity partition determination operation further comprising initially generating a spanning tree by considering one or more links of the network topology in decreasing order of link capacity and selectively adding the one or more links to the spanning tree to form an acyclic graph, wherein the capacity partition determination operation enables control over the number of backup tunnels associated with the at least one link, on which working traffic can be rerouted, and further wherein the capacity partition determination operation provides for a link based local failure restoration and a minimal protection capacity reserved in the network. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein a minimal protection capacity comprises a protection capacity equivalent to no more than two times a protection capacity required for an optimal solution. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the capacity partition determination operation further provides for a link based local failure restoration and a minimal protection capacity when working traffic of the at least one link has to be rerouted on a single bypass tunnel. ### Claim 14 (depends on 11) The apparatus of claim 11, wherein the capacity partition determination operation further provides for a link based local failure restoration and a minimal protection capacity when working traffic of the at least one link can be split and rerouted on no more than two bypass tunnels. ### Claim 15 (depends on 11) The apparatus of claim 11, wherein the capacity partition determination operation further provides for a link based local failure restoration and a minimal protection capacity independent of at least one of a nature of the working traffic and a routing associated with the working traffic. ### Claim 16 (depends on 11) The apparatus of claim 11, wherein the capacity partition determination operation further comprises determining the capacity partition in accordance with a spanning tree based methodology. ### Claim 17 (depends on 11) The apparatus of claim 11, wherein the capacity partition determination operation further comprises determining the capacity partition in accordance with a 2-edge connected graph based methodology. ### Claim 18 (depends on 11) The apparatus of claim 11, wherein the network topology comprises an optical network topology. ### Claim 19 (depends on 11) The apparatus of claim 11, wherein the network topology comprises a multi-protocol label switching network topology. ### Claim 20 (depends on 11) The apparatus of claim 11, wherein the network topology comprises an asynchronous transfer mode network topology. ### Claim 21 An article of manufacture for designing a protection capacity to be reserved in a network, comprising a computer readable storage medium containing one or more programs which when executed implement the steps of: obtaining one or more link capacities associated with a network topology, wherein the network is assumed to have no pre-existing working traffic; determining a capacity partition for at least one link in the network topology, the capacity partition comprising a working capacity portion and a protection capacity portion, the protection capacity portion being reserved for rerouting working traffic upon a failure, the capacity partition determination step further comprising the step of initially generating a spanning tree by considering one or more links of the network topology in decreasing order of link capacity and selectively adding the one or more links to the spanning tree to form an acyclic graph, wherein the capacity partition determination step enables control over the number of backup tunnels associated with the at least one link, on which working traffic can be rerouted, and further wherein the capacity partition determination step provides for a link based local failure restoration and a minimal protection capacity. ### Claim 22 (depends on 7) The method of claim 7, wherein the 2-edge connected graph based methodology considers adding links to the spanning tree created by a spanning tree based methodology. ### Claim 23 (depends on 1) The method of claim 1, wherein the capacity partition determination step further comprises adapting the capacity partition in response to a change in the network topology, wherein the change in the network topology comprises at least one of an addition of a link and a deletion of a link.