Batched path computation in resource-constrained networks

A method of performing batched path computation for a plurality of flows to be installed within a network from a common source to a plurality of different destinations, the method comprising:

• determining, by a controller of the network, a minimum bandwidth of respective bandwidths required for the plurality of flows;
• determining, by the controller for the plurality of flows and based at least on the minimum bandwidth, respective shortest paths of the network from the common source to the respective destinations of the plurality of flows, wherein each of the shortest paths satisfies at least the minimum bandwidth;
• determining, by the controller after determining the shortest paths, that a first shortest path, from the shortest paths, from the common source to a destination of a first flow from the plurality of flows satisfies the bandwidth required for the first flow;
• by the controller, after routing the first flow to the first shortest path on a network model of the network, installing the flow to the network as routed to the first shortest path;
• by the controller after determining that a second shortest path, from the shortest paths, from the common source to a destination of a second flow from the plurality of flows does not satisfy the bandwidth required for the second flow, adding the second flow to a set of flows to route again.

A controller for a network, the controller comprising:

• one or more processors coupled to a memory;
• a path computation module configured for execution by the one or more processors to determine, prior to installing to the network any of a plurality of label-switched paths (LSPs) having a common source and different destination, a minimum bandwidth of respective bandwidths required for the plurality of LSPs;
• wherein the path computation module is further configured for execution by the one or more processors to determine, for the plurality of LSPs and based at least on the minimum bandwidth, respective shortest paths of the network from the common source to the different destinations of the plurality of LSPs, wherein each of the shortest paths satisfies at least the minimum bandwidth;
• wherein the path computation module is further configured for execution by the one or more processors to determine, after determining the shortest paths, that a first shortest path, from the shortest paths, from the common source to a destination of a first LSP from the plurality of LSPs satisfies the bandwidth required for the first LSP,
• wherein the path computation module is further configured for execution by the one or more processors to, after determining that a second shortest path, from the shortest paths, from the common source to a destination of a second LSP from the plurality of LSPs does not satisfy the bandwidth required for the second LSP, add the second LSP to a set of LSPs to route again;
• and
• a path provisioning module configured for execution by the one or more processors to, in response to the path computation module routing the first LSP to the first shortest path on a network model of the network, install the LSP to the network as routed to the first shortest path.

A non-transitory computer-readable medium comprising instructions for causing one or more programmable processors of a controller of a network to:

• determine, prior to installing to the network any of a plurality of label-switched paths (LSPs) having a common source and different respective destinations, a minimum bandwidth of respective bandwidths required for the plurality of LSPs;
• determine, for the plurality of LSPs based at least on the minimum bandwidth, respective shortest paths of the network from the common source to the respective destinations of the plurality of LSPs, wherein each of the shortest paths satisfies at least the minimum bandwidth;
• determine, after determining the shortest paths, that a first shortest path, from the shortest paths, from the common source to a destination of a first LSP from the plurality of LSPs satisfies the bandwidth required for the first LSP;
• after routing the first LSP to the first shortest path on a network model of the network, install the LSP to the network as routed to the first shortest path;
• after determining that a second shortest path, from the shortest paths, from the common source to a destination of a second LSP from the plurality of LSPs does not satisfy the bandwidth required for the second LSP, add the second LSP to a set of LSPs to route again.