Routing restorable service-level-guaranteed connections using maximum 2-route flows

Apparatus for 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, the apparatus comprising:

• an input module for receiving 1) a request for a path with a service demand for routing data between one of the ingress-egress pairs of the network;
• and 2) the data associated with the request;
• a processing module for determining the path of the request, wherein the processing module determines the path by:
• (1) 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 linear sum of elementary 2-flows, each elementary 2-flow having one demand unit along a pair of link-disjoint paths;
• (2) 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;
• (3) modifying a graph of the network by the steps of
• (i) eliminating any links in the graph having residual capacity less than a demand of the connection request, and
• (ii) weighting each link in the modified graph based on the criticality indices of the links;
• and
• (4) determining a disjoint path pair through the modified graph between an ingress node and an egress node of the connection request;
• and
• a switch-fabric for transfeffing data from the input module to an output module of a router in accordance with the path of the request.

A computer-readable medium having stored thereon a plurality of instructions which, when executed by a processor, cause the processor to implement a method for 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, the method 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.