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

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.

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.

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.

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.