Method and apparatus for pre-provisioning networks to support fast restoration with minimum overbuild

• US 20050243711A1
• Filed: 05/03/2004
• Published: 11/03/2005
• Est. Priority Date: 05/03/2004
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Alicherry, Mansoor Ali Khan, Bhatia, Randeep Singh
• Granted Patent: US 7,609,624 B2
• Time in Patent Office: Days
• US Class Current: 370/216
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery

Abstract

Improved network design techniques are provided. More particularly, the invention provides network design techniques for pre-provisioning networks to support fast restoration with minimum overbuild. In one aspect of the invention, 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, wherein the network is assumed to have no pre-existing working traffic. A capacity partition is determined 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/operation enables control over the number of backup tunnels, associated with the at least one link, on which working traffic can be rerouted. Further, the capacity partition determination step/operation substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild. A minimal overbuild may comprise an overbuild equivalent to no more than two times an overbuild required for an optimal solution.

Claims

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, 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 substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild.

2. The method of claim 1, wherein a minimal overbuild comprises an overbuild equivalent to no more than two times an overbuild required for an optimal solution.

3. The method of claim 1, wherein the capacity partition determination step further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild when working traffic of the at least one link has to be rerouted on a single bypass tunnel.

4. The method of claim 1, wherein the capacity partition determination step further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild when working traffic of the at least one link can be split and rerouted on no more than two bypass tunnels.

5. The method of claim 1, wherein the capacity partition determination step further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild independent of at least one of a nature of the working traffic and a routing associated with the working traffic.

6. 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.

7. 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.

8. The method of claim 1, wherein the capacity partition determination step further comprises adapting the capacity partition based on a change in the network topology.

9. The method of claim 1, wherein the network topology comprises an optical network topology.

10. The method of claim 1, wherein the network topology comprises a multi-protocol label switching network topology.

11. The method of claim 1, wherein the network topology comprises an asynchronous transfer mode network topology.

12. 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, 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 substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild.

13. The apparatus of claim 12, wherein a minimal overbuild comprises an overbuild equivalent to no more than two times an overbuild required for an optimal solution.

14. The apparatus of claim 12, wherein the capacity partition determination operation further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild when working traffic of the at least one link has to be rerouted on a single bypass tunnel.

15. The apparatus of claim 12, wherein the capacity partition determination operation further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild when working traffic of the at least one link can be split and rerouted on no more than two bypass tunnels.

16. The apparatus of claim 12, wherein the capacity partition determination operation further substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild independent of at least one of a nature of the working traffic and a routing associated with the working traffic.

17. The apparatus of claim 12, wherein the capacity partition determination operation further comprises determining the capacity partition in accordance with a spanning tree based methodology.

18. The apparatus of claim 12, wherein the capacity partition determination operation further comprises determining the capacity partition in accordance with a 2-edge connected graph based methodology.

19. The apparatus of claim 12, wherein the capacity partition determination operation further comprises adapting the capacity partition based on a change in the network topology.

20. The apparatus of claim 12, wherein the network topology comprises an optical network topology.

21. The apparatus of claim 12, wherein the network topology comprises a multi-protocol label switching network topology.

22. The apparatus of claim 12, wherein the network topology comprises an asynchronous transfer mode network topology.

23. An article of manufacture for designing a protection capacity to be reserved in a network, comprising a machine readable 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; 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, 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 substantially guarantees at least one of a minimal failure restoration time and a minimal overbuild.