Method and system for shared backup allocation in networks based on partial information

1. A computer implemented method for allocating bandwidth in a network having multiple primary paths, the method comprising:

using a computer to identify a respective bridge set for each of at least two different primary paths of the multiple primary paths, the primary path defined by a respective source node and a destination node, wherein each bridge set comprises a plurality of bridges, such that:

each link of the respective primary path is protected by at least one bridge of the respective bridge set,

each bridge comprises at least one link and protects a subpath connecting two nodes of one of the at least two primary paths, and

each bridge is link-disjointed from a respective subpath that the bridge protects, wherein

a first bridge protecting a subpath of one of the at least two primary paths and a second bridge protecting a subpath of another of the at least two primary paths have at least one common link.

2. The method of claim 1 , wherein the using the computer to identify the respective bridge set comprises executing a dynamic programming algorithm.

3. The method of claim 2 , wherein the dynamic programming algorithm comprises:

for each value of i from i=1 to a maximum subpath length of the primary path, wherein i represents a subpath length defined by a number of links in the subpath:

selecting a bridge set for protecting each subpath of the primary path having length i, such that all subpaths of length less than or equal to i are protected by the selected bridge set comprising one or more bridges that are nested within one another or link-disjoint from one another.

4. The method of claim 3 , wherein the using a computer to identify the respective bridge set further comprises:

identifying a minimum cost bridge subset from the selected bridge sets, such that the minimum cost bridge subset protects all subpaths of the primary path.

5. The method of claim 1 , further comprising guaranteeing quality of service with respect to bandwidth when a link or a node of one or more of the at least two primary paths fails.

6. The method of claim 1 , wherein the respective bridge set includes a leading bridge and a set of bridges nested within the leading bridge, such that an inner domain of each nested bridge is nested within an inner domain of the leading bridge.

7. The method of claim 1 , further comprising selecting a minimum cost primary path before using the computer to identify the respective bridge set.

8. The method of claim 1 , wherein the respective set of bridges comprises a plurality of superbridges, each of the plurality of superbridges comprising a leading bridge, wherein at least one of the plurality of superbridges further comprises a plurality of inner bridges nested within the leading bridge.

9. A computer readable medium encoded with computer executable instructions, such that when the computer executable instructions are executed by a processor, the processor performs a computer implemented method for allocating bandwidth in a network having multiple primary paths, the method comprising:

identifying a respective bridge set for each of at least two link-disjoint primary paths of the multiple primary paths, each bridge set comprising a plurality of bridges, such that:

each link of the respective primary path is protected by at least one bridge of the respective bridge set,

each bridge comprises at least one link and protects a subpath connecting two nodes of one of the at least two primary paths, and

each bridge is link-disjointed from a respective subpath that the bridge protects,

wherein

a first bridge protecting a subpath of one of the at least two primary paths and a second bridge protecting a subpath of another of the at least two primary paths have at least one common link.

10. The computer readable medium of claim 9 , wherein the identifying the respective bridge set further comprises:

executing a dynamic programming algorithm for the respective primary path.

11. The computer readable medium of claim 10 , wherein the dynamic programming algorithm comprises:

for each value of i from i=1 to a maximum subpath length of the primary path, wherein i represents a length of a subpath defined by a number of links in the subpath:

selecting a bridge set for protecting each subpath of the primary path having length i, such that all subpaths of length less than or equal to i are protected by the selected bridge set comprising one or more bridges that are nested within one another or link-disjoint from one another.

12. The computer readable medium of claim 11 , wherein the identifying the respective bridge set includes identifying a minimum cost subset of the selected bridge sets, such that the subset protects all subpaths of the primary path.

13. The computer readable medium of claim 9 , wherein the method further comprises:

guaranteeing quality of service with respect to bandwidth when a link or a node of one or more of the at least two primary paths fails.

14. The computer readable medium of claim 9 , wherein the respective bridge set includes a leading bridge and a set of bridges nested within the leading bridge, such that an inner domain of each nested bridge is nested within an inner domain of the leading bridge.

15. The computer readable medium of claim 9 , wherein each respective set of bridges comprises a plurality of superbridges, each of the plurality of superbridges comprising a leading bridge, wherein at least one of the plurality of superbridges further comprises a plurality of inner bridges nested within the leading bridge.

16. A system for allocating bandwidth in a network having at least two primary paths, the system comprising:

a computer processor programmed to identity a protecting bridge set for each primary path, two or more of the at least two primary paths originating from different source nodes in the network, wherein each protecting bridge set comprises a plurality of bridges, such that:

each link of the respective primary path is protected by at least one bridge of the respective bridge set, and

each bridge comprises at least one link and protects a subpath connecting two nodes of one of the at least two primary paths,

wherein none of the plurality of bridges shares any link with a subpath of the respective primary path protected by the bridge, and one of the plurality of bridges that protects a subpath of one of the at least two primary paths and another of the plurality of bridges that protects another subpath of another of the at least two primary paths have at least one common link.

17. The system of claim 16 , wherein the computer processor is programmed to execute a dynamic programming algorithm.

18. The system of claim 17 , wherein the dynamic programming algorithm comprises:

for each of the at least two primary paths:

for each value of i from i=1 to a maximum subpath length of the primary path, wherein i represents a length of a subpath defined by a number of links in the subpath:

selecting a bridge set for protecting each subpath of the primary path having length i, such that all subpaths of the primary path having length less than or equal to i are protected by the selected bridge set comprising one or more bridges that are nested or link-disjoint from one another.

19. The system of claim 18 , wherein the computer processor is further configured to identify as the protecting bridge set minimum cost bridge subset selected from the selected bridge sets, such that the minimum cost subset protects all subpaths of the primary path.

20. The system of claim 16 , wherein the system is further configured to guarantee quality of service with respect to bandwidth when a link or a node of one or more of the at least two primary paths fails.

21. The system of claim 16 , wherein the identified bridge set comprises at least one leading bridge and a set of bridges nested within the leading bridge, such that an inner domain of each nested bridge is nested within an inner domain of the leading bridge.

22. The system of claim 16 , wherein the computer processor is further configured to select a minimum cost primary path before identifying the bridge set.

23. A network comprising:

a plurality of nodes; and

a plurality of links connecting the plurality of nodes, wherein the plurality of nodes and the plurality of links define at least two link-disjoint primary paths in the network, each primary path comprising a respective source node configured to allocate bandwidth for the primary path, wherein the respective source node comprises:

a computer processor programmed to identify a bridge set for protecting the primary path, the identified bridge set including a plurality of bridges, such that:

each link of the primary path is protected by at least one bridge of the identified bridge set,

each bridge comprises at least one link and protects a subpath connecting two of nodes included within the primary path, and

each of the plurality of bridges is link-disjointed from a respective subpath that the bridge protects,

wherein at least two different bridges protecting respectively subpaths of the at least two link-disjoint primary paths share at least one common link.

24. A method for allocating a bandwidth in a network, the method comprising:

allocating a bridge set for protecting a given primary path in the network, the primary path comprising a plurality of nodes and a plurality links connecting the plurality of nodes, wherein:

the allocated bridge set comprises a plurality of bridges, each bridge protecting a subpath of the primary path, the subpath including one or more links of the primary path, such that each link of the primary path is protected by at least one bridge of the allocated bridge set;

each of the plurality of bridges is link-disjointed from a respective subpath that the bridge protects; and

the plurality of bridges comprises a plurality of superbridges, each of the plurality of superbridges comprising a leading bridge, wherein at least one of the plurality of superbridges further comprises a plurality of inner bridges nested within the leading bridge.

25. The method of claim 24 , wherein a first of the plurality of superbridges is nested within a second of the plurality of superbridges.

26. The method of claim 24 , wherein the allocating further comprises:

using a dynamic algorithm to determine bridges for protecting each subpath of the primary path, starting with subpaths comprising a single link and incrementally proceeding up to a subpath comprising the primary path; and

selecting, from the determined bridges a minimal cost bridge set that protects the primary path as the allocated bridge set for protecting the primary path.