Route precomputation method and apparatus for bandwidth guaranteed traffic

1. A method of determining one or more routes between at least a given pair of nodes in a network utilizing a route precomputation algorithm having at least a route generation phase and a route selection phase, the method comprising the steps of:

applying in the route generation phase a maximum-flow algorithm to a first set of information characterizing links between the given pair of nodes in the network, the output of the maximum-flow algorithm being utilizable to generate a second set of information characterizing corresponding admissible flows; and

determining in the route selection phase the one or more routes based on the second set of information.

2. The method of claim 1 wherein the applying and determining steps are repeated for each of a plurality of node pairs of the network.

3. The method of claim 1 wherein the applying step computes a maximum flow from a first one of the given pair of nodes to a second one of the given pair of nodes utilizing the maximum-flow algorithm.

4. The method of claim 3 wherein an admissible flow graph is generatable from the computed maximum flow by setting edge capacities in a corresponding network graph to flow values determined from the computed maximum flow.

5. The method of claim 1 wherein the determining step generates a designated maximum number k of routes that are incrementally consistent with one another.

6. The method of claim 1 wherein the determining step utilizes a shortest widest path (SWP) algorithm to determine the one or more routes based on the second set of information.

7. The method of claim 1 wherein the first set of information is representable as a graph comprising vertices corresponding to network nodes and edges corresponding to links between the nodes.

8. The method of claim 1 wherein the second set of information is representable as an admissible flow graph.

9. The method of claim 8 wherein the admissible flow graph is configured such that any route therethrough will not cause flow constriction.

10. The method of claim 1 wherein the applying and determining steps are configured so as to maintain flow scalability for the determined routes.

11. The method of claim 1 wherein the applying and determining steps are configured such that a set of k+i generated routes has substantially the same route quality regardless of whether the routes are generated collectively as k+i routes or the routes are generated by first generating k routes and subsequently generating i additional routes.

12. The method of claim 1 wherein the route generation phase and the route selection phase are each implemented as corresponding offline phases of a multiple-phase precomputation algorithm.

13. The method of claim 12 wherein the multiple-phase precomputation algorithm further includes an online route selection phase in which a particular one of a plurality of routes determined in the offline route selection phase is selected for use in satisfying a particular traffic demand.

14. The method of claim 1 further comprising the step of storing information specifying each determined route and an associated permissible bandwidth that can be routed along that route.

15. The method of claim 1 wherein the network comprises a multi-protocol label switched (MPLS) data network.

16. The method of claim 1 wherein the determined one or more routes are utilizable to route a transmission demand comprising a label switched path (LSP) request defined by a tuple (s i , d i , b i ) where s i and d i refer to ingress and egress nodes, respectively, of the network and b i denotes bandwidth required by the demand.

17. The method of claim 1 wherein the determined one or more routes are utilizable to route bandwidth guaranteed traffic.

18. The method of claim 1 wherein the applying and determining steps are implemented at least in part in a central controller of a network-based system.

19. An apparatus for use in determining one or more routes between at least a given pair of nodes in a network, the apparatus comprising:

a processor; and

a memory coupled to the processor;

wherein the processor is operative to control execution of a route precomputation algorithm having at least a route generation phase and a route selection phase;

wherein in the route generation phase a maximum-flow algorithm is applied to a first set of information characterizing links between the given pair of nodes in the network, the output of the maximum-flow algorithm being utilizable to generate a second set of information characterizing corresponding admissible flows; and

wherein in the route selection phase one or more routes are determined based on the second set of information.

20. A computer-readable medium encoded with one or more programs for use in determining one or more routes between at least a given pair of nodes in a network, utilizing a route precomputation algorithm having at least a route generation phase and a route selection phase, the one or more programs when executed implementing the steps of:

applying in the route generation phase a maximum-flow algorithm to a first set of information characterizing links between the given pair of nodes in the network, the output of the maximum-flow algorithm being utilizable to generate a second set of information characterizing corresponding admissible flows; and

determining in the route selection phase the one or more routes based on the second set of information.