Granted Patent B2

US 7,500,013 · App. 10/817,760 · Granted Mar 3, 2009

Abstract

Claims (48)

1. A link-based recovery method for a mesh network, the method comprising:

developing N candidate primary paths, between a source node and a destination node for a demand, as a function of N sets {ABi} of available bandwidths, wherein each set {ABi} corresponds to one of the N candidate primary paths, and each element ABi of each set corresponds to the available bandwidth on a link i of the corresponding candidate primary path;

selecting a first primary path, from the N candidate primary paths, as a function of N sets {LCi} of link costs, wherein each set {LCi} corresponds to one of the N candidate primary paths, and each element LCi of each set corresponds to a link cost of a link i in the corresponding candidate primary path; and

computing a link detour (LD) path for each link i in the first primary path as a function of a set {ABPi} of available LD bandwidths, wherein each element ABPi of the set {ABPi} is equal to the minimum value from the set {ABj} of available bandwidths, wherein each element ABj of the set {ABj} corresponds to total available bandwidth on a link j in a candidate LD path for link i.

2. The invention of claim 1 , wherein:

each link j in each of a plurality of candidate LD paths for link i of the first primary path has a link cost associated with it; and

computing the LD path for each link i in the first primary path comprises selecting the LD path for link i as a function of link cost.

3. The invention of claim 2 , wherein computing an LD path comprises:

computing a sum of the link costs associated with each link j in two or more candidate LD paths for link i of the first primary path to determine an LD path link cost sum; and

choosing the LD path for the link i of the first primary path to be the candidate LD path with the smallest LD path link cost sum.

4. The invention of claim 2 , wherein each link cost is inversely related to the available bandwidth on the link.

5. The invention of claim 2 , wherein each link cost is inversely related to the available shared bandwidth on the link.

6. The invention of claim 1 , wherein:

selecting the first primary path comprises:

computing a sum of the link costs LCi of all links i in each of the N candidate primary path to determine a link cost sum corresponding to each candidate primary path; and

choosing the first primary path to be the candidate primary path with the smallest link cost sum.

7. The invention of claim 1 , wherein developing the N candidate primary paths and selecting the first primary path for the demand are performed at the source node.

8. The invention of claim 1 , wherein computing the link detour (LD) path for a given link i in the first primary path is performed at a controlling node for link i, wherein the controlling node for link i is a terminating node for link i that is immediately upstream of link i with respect to the demand.

9. The invention of claim 1 , comprising:

calculating a LD path cost CPPi for each link i of each candidate primary path, wherein CPPi is a function of at least the administrative weight of each link within the link detour path for link i;

calculating a cost of available bandwidth CABi for each link i of each candidate primary path, wherein CABi is inversely related to the available bandwidth on link i; and

calculating the link cost LCi for each link i of each candidate primary path as a function of CPPi and CABi.

10. The invention of claim 9 , wherein CPPi is calculated and distributed to the rest of the network by a controlling node for link i, wherein the controlling node for link i is a terminating node for link i that is immediately upstream to link i with respect to the demand.

11. The invention of claim 1 , wherein available bandwidth on a link is defined as a measure of total amount of currently unused bandwidth on the link.

12. A protection manager for a mesh communications network, the manager comprising one or more computing elements adapted to:

develop N candidate primary paths, between a source node and a destination node for a demand, as a function of N sets {ABi} of available bandwidths, wherein each set {ABi} corresponds to one of the N candidate primary paths, and each element ABi of each set corresponds to the available bandwidth on a link i of the corresponding candidate primary path;

select a first primary path, from the N candidate primary paths, as a function of N sets {LCi} of link costs, wherein each set {LCi} corresponds to one of the N candidate primary paths, and each element LCi of each set corresponds to a link cost of a link i in the corresponding candidate primary path; and

compute a link detour (LD) path for each link i in the first primary path as function of a set {ABPi} of available LD bandwidths, wherein each element ABPi of the set {ABPi} is equal to the minimum value from the set {ABj} of available bandwidths, wherein each element ABj of the set {ABj} corresponds to total available bandwidth on one link j in an LD path for link i.

13. The invention of claim 12 , wherein:

each link j in each of a plurality of candidate LD paths for link i of the first primary path has a link cost associated with it; and

computing the LD path for each link i in the first primary path comprises selecting the LD path for link i as a function of link cost.

14. The invention of claim 13 , wherein computing an LD path comprises:

computing a sum of the link costs associated with each link j in two or more candidate LD paths for link i of the first primary path to determine an LD path link cost sum; and

choosing the LD path for the link i of the first primary path to be the candidate LD path with the smallest LD path link cost sum.

15. The invention of claim 13 , wherein each link cost is inversely related to the available bandwidth on the link.

16. The invention of claim 13 , wherein each link cost is inversely related to the available shared bandwidth on the link.

17. The invention of claim 12 , wherein:

selecting the first primary path comprises:

computing a sum of the link costs LCi for all links i in the primary path to determine a link cost sum; and

choosing the first primary path to be the primary path with the smallest link cost sum.

18. The invention of claim 12 , wherein developing the N candidate primary paths and selecting the first primary path for the demand are performed at the source node.

19. The invention of claim 12 , wherein computing the link detour (LD) path for a given link i in the first primary path is performed at a controlling node for link i, wherein the controlling node for link i is a terminating node for link i that is immediately upstream of link i with respect to the demand.

20. The invention of claim 12 , wherein the one or more computing elements are adapted to:

calculate a LD path cost CPPi for each link i of each candidate primary path, wherein CPPi is a function of at least the administrative weight of each link within the link detour path for link i;

calculate a cost of available bandwidth CABi for each link i of each candidate primary path, wherein CABi is inversely related to the available bandwidth on link i; and

calculate the link cost LCi for each link i of each candidate primary path as a function of CPPi and CABi.

21. The invention of claim 20 , wherein CPPi is calculated and distributed to the rest of the network by a controlling node for link i, wherein the controlling node for link i is a terminating node for link i that is immediately upstream to link i with respect to the demand.

22. The invention of claim 12 , wherein available bandwidth on a link is defined as a measure of total amount of currently unused bandwidth on the link.

Assignments (8)