Network resource allocation using forecasted network traffic patterns selected utilizing network topology

1. A method, comprising:

receiving a plurality of forecasted network traffic patterns for a network;

selecting a representative subset of the plurality of forecasted network traffic patterns based on an analysis of the plurality of forecasted network traffic patterns using a topology of the network, selecting the representative subset further including

selecting a plurality of non-dominated forecasted network traffic patterns from the plurality of forecasted network traffic patterns; and

using the selected representative subset of the plurality of forecasted network traffic patterns to determine a resource allocation for the network.

2. The method of claim 1 , wherein the plurality of non-dominated forecasted network traffic patterns correspond to additional capacity for the network.

3. The method of claim 1 , wherein the selecting the representative subset further includes:

enumerating a plurality of edge-cut sets for the topology of the network, each of the plurality of edge-cut sets including a particular number of edges and separating the topology into a plurality of partitions, each of the plurality of partitions including greater than one network component;

determining a portion of the plurality of forecasted network traffic patterns for aggregated traffic between the plurality of partitions for each of the plurality of edge-cut sets; and

determining a particular forecasted network traffic pattern having a maximum

aggregated traffic between the plurality of partitions.

4. The method of claim 3 wherein the selecting the representative subset further includes:

repeating the enumerating the plurality of edge-cut sets, determining the portion of the plurality of forecasted network traffic patterns, and determining the particular forecasted network traffic pattern for another number of edges.

5. The method of claim 3 wherein the selecting the representative subset further includes:

determining whether the maximum aggregated traffic for the particular forecasted network traffic pattern matches a previously selected maximum aggregated traffic for a previously selected forecasted network traffic pattern; and

based on a determination that the maximum aggregated traffic does not match the previously selected maximum aggregated traffic, selecting the particular forecasted network traffic pattern as a member of the selected representative subset of the forecasted network traffic pattern.

6. The method of claim 5 wherein the selecting the representative subset further includes:

repeating the enumerating the plurality of edge-cut sets, determining the portion of the plurality of forecasted network traffic patterns, determining the particular forecasted network traffic pattern, determining whether the maximum aggregated traffic matches the previously selected maximum aggregated traffic and selecting the particular forecasted network traffic pattern as a member of the selected representative subset for another number of edges.

7. A system for allocating network resources, comprising:

a processor configured to:

receive a plurality of forecasted network traffic patterns for a network;

select a representative subset of the plurality of forecasted network traffic patterns based on an analysis of the plurality of forecasted network traffic patterns using a topology of the network, the processor being configured to select the representative subset further including the processor being configured to

select a plurality of non-dominated forecasted network traffic patterns from the plurality of forecasted network traffic patterns; and

use the selected representative subset of the plurality of forecasted network traffic patterns to determine a resource allocation for the network; and

a memory coupled to the processor and configured to provide the processor with instructions.

8. The system of claim 7 , wherein the plurality of non-dominated forecasted network traffic patterns correspond to additional capacity for the network.

9. The system of claim 7 wherein to selecting the representative subset the processor is further configured to:

enumerate a plurality of edge-cut sets for the topology of the network, each of the plurality of edge-cut sets including a particular number of edges and separating the topology into a plurality of partitions, each of the plurality of partitions including greater than one network component;

determine a portion of the plurality of forecasted network traffic patterns for aggregated traffic between the plurality of partitions for each of the plurality of edge-cut sets; and

determine a particular forecasted network traffic pattern having a maximum aggregated traffic between the plurality of partitions.

10. The system of claim 9 wherein to select the representative subset the processor is further configured to:

repeat the enumerating the plurality of edge-cut sets, determining the portion of the plurality of forecasted network traffic patterns, and determining the particular forecasted network traffic pattern for another number of edges.

11. The system of claim 9 wherein to select the representative subset the processor is further configured to:

determine whether the maximum aggregated traffic for the particular forecasted network traffic pattern matches a previously selected maximum aggregated traffic for a previously selected forecasted network traffic pattern; and

select the particular forecasted network traffic pattern as a member of the selected representative subset of the forecasted network traffic pattern based on a determination that the maximum aggregated traffic does not match the previously selected maximum aggregated traffic.

12. The system of claim 11 wherein to select the representative subset the processor further configured to:

repeat the enumerating the plurality of edge-cut sets, determining the portion of the plurality of forecasted network traffic patterns, determining the particular forecasted network traffic pattern, determining whether the maximum aggregated traffic matches the previously selected maximum aggregated traffic and selecting the particular forecasted network traffic pattern as a member of the selected representative subset for another number of edges.

13. A computer program product for allocating network resource, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a plurality of forecasted network traffic patterns for a network;

selecting a representative subset of the plurality of forecasted network traffic patterns based on an analysis of the plurality of forecasted network traffic patterns using a topology of the network, the selecting the representative subset further including

selecting a plurality of non-dominated forecasted network traffic patterns from the plurality of forecasted network traffic patterns; and

using the selected representative subset of the plurality of forecasted network traffic patterns to determine a resource allocation for the network.

14. The computer program product of claim 13 , wherein the plurality of non-dominated forecasted network traffic patterns correspond to additional capacity for the network.

15. The computer program product of claim 13 wherein the instructions for selecting the representative subset further include instructions for:

enumerating a plurality of edge-cut sets for the topology of the network, each of the plurality of edge-cut sets including a particular number of edges and separating the topology into a plurality of partitions, each of the plurality of partitions including greater than one network component;

determining a portion of the plurality of forecasted network traffic patterns for aggregated traffic between the plurality of partitions for each of the plurality of edge-cut sets; and

determining a particular forecasted network traffic pattern having a maximum aggregated traffic between the plurality of partitions.

16. The computer program product of claim 15 wherein the instructions for selecting the representative subset further include instructions for:

determining whether the maximum aggregated traffic for the particular forecasted network traffic pattern matches a previously selected maximum aggregated traffic for a previously selected forecasted network traffic pattern; and

based on a determination that the maximum aggregated traffic does not match the previously selected maximum aggregated traffic, selecting the particular forecasted network traffic pattern as a member of the selected representative subset of the forecasted network traffic pattern.

17. The computer program product of claim 16 wherein the instructions for selecting the representative subset further include instructions for:

repeating the enumerating the plurality of edge-cut sets, determining the portion of the plurality of forecasted network traffic patterns, determining the particular forecasted network traffic pattern, determining whether the maximum aggregated traffic matches the previously selected maximum aggregated traffic and selecting the particular forecasted network traffic pattern as a member of the selected representative subset for another number of edges.

18. The method of claim 1 , wherein the network having sufficient capacity to meet first demands of a non-dominated forecasted network traffic pattern of the plurality of non-dominated forecasted network traffic patterns corresponds to the network being capable of meeting second demands for at least one other forecasted network traffic pattern of the plurality of forecasted network traffic patterns that corresponds to the non-dominated forecasted network traffic pattern.

19. The system of claim 7 , wherein the network having sufficient capacity to meet first demands of a non-dominated forecasted network traffic pattern of the plurality of non-dominated forecasted network traffic patterns corresponds to the network being capable of meeting second demands for at least one other forecasted network traffic pattern of the plurality of forecasted network traffic patterns that corresponds to the non-dominated forecasted network traffic pattern.

20. The computer program product of claim 13 , wherein the network having sufficient capacity to meet first demands of a non-dominated forecasted network traffic pattern of the plurality of non-dominated forecasted network traffic patterns corresponds to the network being capable of meeting second demands for at least one other forecasted network traffic pattern of the plurality of forecasted network traffic patterns that corresponds to the non-dominated forecasted network traffic pattern.