Granted Patent B2

US 7,889,641 · App. 11/779,429 · Granted Feb 15, 2011

Abstract

Claims (56)

1. A method of defining Fast Reroute (FRR) bypass tunnels on a Multi-Protocol Label Switching (MPLS) network using a path-flow formulation, comprising:

specifying a network facility to protect;

computing, using a path-flow formulation, a plurality of candidate bypass Label-Switched Paths (LSP) that protect one or more routes through the facility, satisfy predetermined path and bandwidth constraints, and have explicit routes, to carry traffic flows in the event of a failure of the protected facility; and

selecting from among the candidate bypass LSPs one or more bypass LSPs by allocating protection bandwidth to the bypass LSPs.

2. The method of claim 1 wherein selecting from among the candidate bypass LSPs one or more bypass LSPs by allocating protection bandwidth to the bypass LSPs comprises formulating and solving a linear programming (LP) problem on the set of candidate bypass LSPs with the protection bandwidth to be allocated to the bypass LSPs being a decision variable.

3. The method of claim 2 wherein selecting bypass LSPs by allocating bandwidth to them further comprises specifying an integer maximum number of bypass LSPs for a protected facility, and formulating and solving an integer linear programming (ILP) problem on the candidate bypass LSPs.

4. The method of claim 1 further comprising:

inspecting previously defined bypass LSPs protecting the selected facilities by applying the predetermined path and bandwidth constraints to the existing bypass LSPs;

repairing the existing bypass LSPs to conform to the predetermined path and bandwidth constraints; and

adding the repaired, existing bypass LSPs to the plurality of candidate bypass LSPs prior to selecting bypass LSPs from among the candidate bypass LSPs.

5. The method of claim 1 wherein computing a plurality of candidate bypass LSPs comprises:

determining all Point of Local Repair (PLR) and Merge Point (MP) routers of the facility to be protected; and for each PLR/MP pair,

determining the protected route bandwidth and the bottleneck RSVP bandwidth;

creating a bypass bundle from the PLR to the MP;

associating the protected route with the bypass bundle;

assigning backup bandwidth, based on the bottleneck RSVP bandwidth; and

associating the bypass bundle with the PLR interface.

6. The method of claim 1 wherein the predetermined path constraints include a maximum number of hops.

7. The method of claim 1 wherein the predetermined path constraints include a maximum increase in the number of hops.

8. The method of claim 1 wherein the predetermined path constraints include a maximum delay.

9. The method of claim 1 wherein the predetermined path constraints include a maximum delay increase.

10. The method of claim 1 wherein the predetermined path constraints include a diversity constraint that each bypass LSP be disjoint of the facility it protects.

11. The method of claim 10 wherein the predetermined path constraints include constraints derived from a shared risk group definition that could impact the diversity constraint between the bypass LSPs and the protected facility.

12. The method of claim 1 wherein the predetermined path constraints include a minimum bandwidth for each bypass LSP.

13. The method of claim 1 wherein the predetermined path constraints include a limit on the number of parallel bypass LSPs that protect the same facility.

14. The method of claim 1 wherein the predetermined path constraints include taboo links that may not be used in bypass LSPs.

15. The method of claim 1 wherein the predetermined path constraints include constraints derived from the MPLS capability on network facilities.

16. The method of claim 1 wherein the predetermined path constraints include constraints derived from the RSVP capability on network facilities.

17. The method of claim 1 wherein the predetermined path constraints include constraints derived from the IP routing capability on network facilities.

18. The method of claim 1 wherein the predetermined path constraints include constraints derived from resource bits colored on each interface of a link for MPLS traffic engineering purposes.

19. The method of claim 1 wherein one predetermined bandwidth constraint is the bandwidth pool of the facility to be protected.

20. The method of claim 1 wherein allocating protection bandwidth to the bypass LSPs comprising allocating to a first bypass LSP on a given link, less bandwidth than the RSVP maximum of the corresponding protected route if a second bypass LSP also traversing the link shares a link on the protected route with the first bypass LSP.

21. A non-transitory computer readable medium including one or more computer programs operative to cause a computer to define Fast Reroute (FRR) bypass Label-Switched Paths (LSP) for a Multi-Protocol Label Switching (MPLS) network using a path-flow formulation, the computer programs operative to cause the computer to perform the steps of:

receiving network topology information;

receiving identification of a network facility to protect;

receiving predetermined path and bandwidth constraints;

computing, using a path-flow formulation, a plurality of candidate bypass LSPs that protect one or more routes through the facility, satisfy the predetermined path and bandwidth constraints, and have explicit routes, to carry traffic flows in the event of a failure of the protected facility;

selecting from among the candidate bypass LSPs one or more bypass LSPs by allocating protection bandwidth to the bypass LSPs; and

outputting the bypass LSPs.

22. The computer readable medium of claim 21 wherein the computer programs are further operative to cause the computer to perform the steps of:

receiving identification of previously defined bypass LSPs protecting the selected facilities;

inspecting the existing bypass LSPs by applying the predetermined path and bandwidth constraints to the existing bypass LSPs;

repairing the existing bypass LSPs to conform to the predetermined path and bandwidth constraints; and

adding the repaired, existing bypass LSPs to the plurality of candidate bypass LSPs prior to selecting bypass LSPs from among the candidate bypass LSPs.

23. The computer readable medium of claim 21 wherein computing a plurality of candidate bypass LSPs that satisfy the predetermined path and bandwidth constraints comprises:

determining all Point of Local Repair (PLR) and Merge Point (MP) routers of the facility to be protected; and

for each PLR/MP pair,

determining the protected route bandwidth and the bottleneck RSVP bandwidth;

creating a bypass bundle from the PLR to the MP;

associating the protected route with the bypass bundle;

assigning backup bandwidth, based on the bottleneck RSVP bandwidth; and

associating the bypass bundle with the PLR interface.

24. The method of claim 1 wherein two or more of the bypass LSPs share one or more links in the network routes they protect, reducing the aggregate protection bandwidth of the bypass LSPs such that each bypass LSP protects a bottleneck bandwidth along its protected route and such that the combined bandwidth of each bypass LSP that shares a protected route link is less than or equal to the minimum RSVP bandwidth of the shared link.

25. The method of claim 24 wherein reducing the aggregate protection bandwidth of the bypass LSPs comprises formulating and solving a linear programming problem with an objective function that the spare link load is the largest possible value of the total backup bandwidth of its contained bypass LSPs, subject to the constraints:

the sum of protection bandwidths of each bypass LSP that shares a protected route link is less than or equal to the minimum RSVP bandwidth of the shared protected route link; and

each bypass LSP has at least the bandwidth of the minimum RSVP bandwidth of any link in its protected route.

Assignments (21)