Patent ID: 7978594
Filing Date: 2011-07-12
Classification: H04L

Abstract:
1. A computer-implemented method for supporting recovery from failure of a link in a network of nodes interconnected by links, the method comprising: (a) the computer generating, 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) the computer selecting, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point, each path structure comprising a primary path and one or more link backup detours protecting each link on the primary path; (c) the computer implementing, after completion of step (b) and 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 the primary path of the first path structure; (d) the computer implementing, after completion of step (b) and 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 the primary path of the second path structure; and (e) the computer computing 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 path structure that contain link e and the egress capacity constraints of the paths of the second path structure 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.