SYSTEM AND METHOD FOR RESOURCE PLACEMENT ACROSS CLOUDS FOR DATA INTENSIVE WORKLOADS

• US 20190196879A1
• Filed: 12/21/2017
• Published: 06/27/2019
• Est. Priority Date: 12/21/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dutta, Debojyoti, Huang, Xinyuan
• Granted Patent: US 10,705,882 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 41/0803 Configuration setting

Abstract

Systems, methods, computer-readable media are disclosed for determining a point of delivery (POD) device or network component on a cloud for workload and resource placement in a multi-cloud environment. A method includes determining a first amount of data for transitioning from performing a first function on input data to performing a second function on a first outcome of the first function; determining a second amount of data for transitioning from performing the second function on the first outcome to performing a third function on a second outcome of the second function; determining a processing capacity for each of one or more network nodes on which the first function and the third function are implemented; and selecting the network node for implementing the second function based on the first amount of data, the second amount of data, and the processing capacity for each of the network nodes.

Claims

1. A computer-implemented method for selecting a network node to implement a network function, the method comprising:

determining a first amount of data for transitioning from performing a first function on input data to performing a second function on a first outcome of the first function;

determining a second amount of data for transitioning from performing the second function on the first outcome to performing a third function on a second outcome of the second function;

determining a processing capacity for each of one or more network nodes on which the first function and the third function are implemented; and

selecting the network node for implementing the second function based on the first amount of data, the second amount of data, and the processing capacity for each of the network nodes.

2. The method of claim 1, wherein, when the first function and the third function are implemented on a first network node, determining the processing capacity includes determining the processing capacity of the first network node.

3. The method of claim 2, wherein selecting the network node further comprises:

selecting the first network node for implementing the second function if the processing capacity of the first network node is equal to or greater than the first amount of data and the second amount of data.

4. The method of claim 2, wherein selecting the network node further comprises:

selecting a second network node for implementing the second function if the processing capacity of the first network node is less than the first amount of data and the second amount of data.

5. The method of claim 4, wherein selecting the network node further comprises:

selecting a network node as the second network node with a corresponding network capacity that is greater than the first amount of data and the second amount of data and a cost associated with transitioning data corresponding to the first outcome from the first network node to the second network node is minimized among all costs associated with transitioning the data corresponding to the first outcome from the first network node to any other available network node.

6. The method of claim 1, wherein when the first function and third function are implemented on a first network node and a second network node respectively, the method further comprises:

determining a first processing capacity of the first network node;

determining a second processing capacity of the second network node;

selecting the first network node for implementing the second function if the first processing capacity of the first network node is equal to or greater than the first amount of data and the second amount of data;

selecting the second network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data, and

(2) the second capacity of the second network node is equal to or greater than the first amount of data and the second amount of data; and

selecting a third network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data,

(2) the second capacity of the second network node is less than the first amount of data and the second amount of data,

(3) a corresponding network capacity of the third network node is equal to or greater than the first amount of data and the second amount of data, and

(4) a first cost associated with transitioning data corresponding to the first outcome from the first network node to the third network node and a second cost associated with transitioning data corresponding to the second outcome from the third network node to the second network node are minimized among all costs associated with transitioning the data corresponding to the first outcome and the data corresponding to the second outcome from the first network node and the third network node, respectively, to any other available network node.

7. The method of claim 1, further comprising:

receiving an indication of a plurality of data segments to be processed according to the first function, the second function and the third function at a predetermined time;

at any one of a plurality of target times prior to the predetermined time,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process available ones of the plurality of data segments using the first function, the second function and third function to yield first processed data; and

storing the first processed data.

8. The method of claim 7, further comprising:

determining, at the predetermined time, if the plurality of data segments are unchanged;

if the plurality of data segments are unchanged,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process ones of the plurality of data segments received between a last one of the plurality of target times and the predetermined time using the first function, the second function and third function to yield second processed data;

storing the second processed data; and

combining the first processed data and the second processed data; and

if the plurality of data segments are changed,

discarding the first processed data;

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process the plurality of data segments received using the first function, the second function and third function to yield third processed data; and

storing the third processed data.

9. A system for selecting a network node to implement a network function, the system comprising:

memory configured to store computer-readable instructions therein; and

one or more processors configured to execute the computer-readable instructions to perform functions including;

determining a first amount of data for transitioning from performing a first function on input data to performing a second function on a first outcome of the first function;

determining a second amount of data for transitioning from performing the second function on the first outcome to performing a third function on a second outcome of the second function;

determining a processing capacity for each of one or more network nodes on which the first function and the third function are implemented; and

selecting the network node for implementing the second function based on the first amount of data, the second amount of data, and the processing capacity for each of the network nodes.

10. The system of claim 9, wherein, when the first function and the third function are implemented on a first network node,

the one or more processors are configured to execute the computer-readable instructions to determine the processing capacity of the first network node;

the one or more processors are configured to execute the computer-readable instructions to select the first network node for implementing the second function if the respective capacity of the first network node is equal to or greater than the first amount of data and the second amount of data; and

the one or more processors are configured to execute the computer-readable instructions to select a second network node for implementing the second function if the processing capacity of the first network node is less than the first amount of data and the second amount of data.

11. The system of claim 10, wherein the one or more processors are configured to execute the computer-readable instructions to select a network node as the second network node with a corresponding network capacity that is greater than the first amount of data and the second amount of data and a cost associated with transitioning data corresponding to the first outcome from the first network node to the second network node is minimized among all costs associated with transitioning the data corresponding to the first outcome from the first network node to any other available network node.

12. The system of claim 10, wherein the first network node and the second network node are associated with different cloud environments.

13. The system of claim 9, wherein when the first function and third function are implemented on a first network node and a second network node respectively, the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

determining a first processing capacity of the first network node;

determining a second processing capacity of the second network node;

selecting the first network node for implementing the second function if the first processing capacity of the first network node is equal to or greater than the first amount of data and the second amount of data;

selecting the second network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data, and

(2) the second capacity of the second network node is equal to or greater than the first amount of data and the second amount of data; and

selecting a third network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data,

(2) the second capacity of the second network node is less than the first amount of data and the second amount of data,

(3) a corresponding network capacity of the third network node is equal to or greater than the first amount of data and the second amount of data, and

(4) a first cost associated with transitioning data corresponding to the first outcome from the first network node to the third network node and a second cost associated with transitioning data corresponding to the second outcome from the third network node to the second network node are minimized among all costs associated with transitioning the data corresponding to the first outcome and the data corresponding to the second outcome from the first network node and the third network node, respectively, to any other available network node.

14. The system of claim 9, wherein the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

receiving an indication of a plurality of data segments to be processed according to the first function, the second function and the third function at a predetermined time;

at any one of a plurality of target times prior to the predetermined time,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process available ones of the plurality of data segments using the first function, the second function and third function to yield first processed data; and

storing the first processed data.

15. The system of claim 14, wherein the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

determining, at the predetermined time, if the plurality of data segments are unchanged;

if the plurality of data segments are unchanged,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process ones of the plurality of data segments received between a last one of the plurality of target times and the predetermined time using the first function, the second function and third function to yield second processed data;

storing the second processed data; and

combining the first processed data and the second processed data; and

if the plurality of data segments are changed,

discarding the first processed data;

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process the plurality of data segments received using the first function, the second function and third function to yield third processed data; and

storing the third processed data.

20. The one or more non-transitory computer-readable medium of claim 14, wherein the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

determining, at the predetermined time, if the plurality of data segments are unchanged;

if the plurality of data segments are unchanged,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process ones of the plurality of data segments received between a last one of the plurality of target times and the predetermined time using the first function, the second function and third function to yield second processed data;

storing the second processed data; and

combining the first processed data and the second processed data; and

if the plurality of data segments are changed,

discarding the first processed data;

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting of a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process the plurality of data segments received using the first function, the second function and third function to yield third processed data; and

storing the third processed data.

16. One or more non-transitory computer-readable medium having computer-readable instructions stored therein, which when executed by one or more processors, cause the one or more processors to select a network node for implementing a network function by performing the functions of:

determining a first amount of data for transitioning from performing a first function on input data to performing a second function on a first outcome of the first function;

determining a second amount of data for transitioning from performing the second function on the first outcome to performing a third function on a second outcome of the second function;

determining a processing capacity for each of one or more network nodes on which the first function and the third function are implemented; and

selecting the network node for implementing the second function based on the first amount of data, the second amount of data, and the processing capacity for each of the network nodes.

17. The one or more non-transitory computer-readable medium of claim 16, wherein, when the first function and the third function are implemented on a first network node, determining the processing capacity includes determining the processing capacity of the first network node;

selecting the network node comprises selecting the first network node for implementing the second function if the processing capacity of the first network node is equal to or greater than the first amount of data and the second amount of data; and

selecting the network node comprises a second network node for implementing the second function if the processing capacity of the first network node is less than the first amount of data and the second amount of data, the second network node having (1) a corresponding network capacity that is greater than the first amount of data and the second amount of data and (2) a cost associated with transitioning data corresponding to the first outcome from the first network node to the second network node is minimized among all costs associated with transitioning the data corresponding to the first outcome from the first network node to any other available network node.

18. The one or more non-transitory computer-readable medium of claim 16, wherein when the first function and third function are implemented on a first network node and a second network node respectively, the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

determining a first processing capacity of the first network node;

determining a second processing capacity of the second network node;

selecting the first network node for implementing the second function if the first processing capacity of the first network node is equal to or greater than the first amount of data and the second amount of data;

selecting the second network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data, and

(2) the second capacity of the second network node is equal to or greater than the first amount of data and the second amount of data; and

selecting a third network node for implementing the second function if,

(1) the first processing capacity of the first network node is less than the first amount of data and the second amount of data,

(2) the second capacity of the second network node is less than the first amount of data and the second amount of data,

(3) a corresponding network capacity of the third network node is equal to or greater than the first amount of data and the second amount of data, and

(4) a first cost associated with transitioning data corresponding to the first outcome from the first network node to the third network node and a second cost associated with transitioning data corresponding to the second outcome from the third network node to the second network node are minimized among all costs associated with transitioning the data corresponding to the first outcome and the data corresponding to the second outcome from the first network node and the third network node, respectively, to any other available network node.

19. The one or more non-transitory computer-readable medium of claim 16, wherein the one or more processors are configured to execute the computer-readable instructions to further perform the functions of:

receiving an indication of a plurality of data segments to be processed according to the first function, the second function and the third function at a predetermined time;

at any one of a plurality of target times prior to the predetermined time,

performing the determining of the first amount of data, the determining of the second amount of data, the determining of the processing capacity and the selecting a network node;

configuring network nodes corresponding to the first function, the second function and the third function to process available ones of the plurality of data segments using the first function, the second function and third function to yield first processed data; and

storing the first processed data.