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

Patent metadata

Field	Value
Publication number	US-11184248-B1
Application number	US-201916383461-A
Country	US
Kind code	B1
Filing date	Apr 12, 2019
Priority date	Jan 28, 2019
Publication date	Nov 23, 2021
Grant date	Nov 23, 2021

Abstract

A method and system for allocating network resources are described. The method includes receiving a plurality of forecasted network traffic patterns for a network. A representative subset of the plurality of forecasted network traffic patterns is selected based on an analysis of the plurality of forecasted network traffic patterns using a topology of the network. The selected representative subset of the plurality of forecasted network traffic patterns is used to determine a resource allocation for the network.

First claim

What is claimed is:

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 parti

Assignees

• Facebook Inc

Inventors

• Ahuja Satyajeet Singh
• Gopalan Abishek
• Dangui Vinayak
• Nagarajan Gayathrinath
• Lapukhov Petr V

Classifications

• H04L41/147 Primary

  for predicting network behaviour · CPC title

• H04L47/83

  based on usage prediction · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L41/145 Primary

  involving simulating, designing, planning or modelling of a network · CPC title

• H04L47/41

  by acting on aggregated flows or links · CPC title