Patent ID: 7397761

Claim:
A method of routing data of a connection request through a network of nodes interconnected by links and having one or more ingress-egress node pairs between which a stream of data or packets of the connection is routed as a flow over one or more paths, comprising the steps of: (a) generating a maximum 2-route flow for each of the ingress-egress node pairs in the network, wherein: (i) the maximum 2-route flow has the maximum total amount of flow that enters the destination node for that flow, including flow over both active and backup paths, that over the path between the two nodes of each pair, without exceeding capacities of links of the path; (ii) the maximum 2-route flow is expressed as a non-negative liner sum of elementary 2-flows, each elementary 2-flow having one demand unit along a pair of link-disjoint paths; (b) generating a set of 2-critical links with associated criticality indices for each of the ingress-egress node pairs based on the corresponding maximum 2-route flow; (c) modifying a graph of the network by the steps of (c1) eliminating any links in the graph having residual capacity less than a demand of the connection request, and (c2) weighting each link in the modified graph based on the criticality indices of the links; (d) determining a disjoint path pair through the modified graph between an ingress node and an egress node of the connection request; (e) selecting one of the disjoint path pair as an active path and the other one of the disjoint path pair as a backup path; and (f) routing the data over the active path.