Efficient and robust routing of potentially-variable traffic for path restoration following link failure

Apparatus for supporting recovery from failure of a path in a network of nodes interconnected by links, the apparatus comprising a processor adapted to:

• (a) generate, for each of a plurality of potential intermediate nodes between an ingress point and an egress point of the network, a sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point;
• (b) select, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first link-disjoint path set between the ingress point and the intermediate node, and a second link-disjoint path set between the intermediate node and the egress point, each link-disjoint path set comprising a backup path and at least one primary path having no shared links with the backup path;
• (c) implement, during a first routing phase, a first routing method for routing a first fraction of a service level between the ingress point and the intermediate node along each of the one or more primary paths of the first link-disjoint path set;
• (d) implement, during a second routing phase, a second routing method for routing a second fraction of the service level between the intermediate node and the egress point along each of the one or more primary paths of the second link-disjoint path set;
• (el compute a split ratio by determining the minimum value, across all links e, of the link capacity for link e divided by the sum of the ingress capacity constraints of the paths of the first link-disjoint path set that contain link e and the egress capacity constraints of the paths of the second link-disjoint path set that contain link e;
• wherein:
• the first fraction of the service level is determined by the product of the split ratio and the capacity constraint between the ingress point and the intermediate node;
• and the second fraction of the service level is determined by the product of the split ratio and the capacity constraint between the intermediate node and the egress point.

A network of nodes interconnected by links, wherein the network comprises an apparatus for supporting recovery from failure of a path of the network, the apparatus comprising a processor adapted to:

• (a) generate, for each of a plurality of potential intermediate nodes between an ingress point and an egress point of the network, a sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point;
• (b) select, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first link-disjoint path set between the ingress point and the intermediate node, and a second link-disjoint path set between the intermediate node and the egress point, each link-disjoint path set comprising a backup path and at least one primary path having no shared links with the backup path;
• (c) implement, during a first routing phase, a first routing method for routing a first fraction of a service level between the ingress point and the intermediate node along each of the one or more primary paths of the first link-disjoint path set;
• (d) implement, during a second routing phase, a second routing method for routing a second fraction of the service level between the intermediate node and the egress point along each of the one or more primary paths of the second link-disjoint path set (e) compute a split ratio by determining the minimum value, across all links e, of the link capacity for link e divided by the sum of the ingress capacity constraints of the paths of the first link-disjoint path set that contain link e and the egress capacity constraints of the paths of the second link-disjoint path set that contain link e;
• wherein:
• the first fraction of the service level is determined by the product of the split ratio and the capacity constraint between the ingress point and the intermediate node;
• and the second fraction of the service level is determined by the product of the split ratio and the capacity constraint between the intermediate node and the egress point.