OPTIMIZED HADOOP TASK SCHEDULER IN AN OPTIMALLY PLACED VIRTUALIZED HADOOP CLUSTER USING NETWORK COST OPTIMIZATIONS

• US 20160350146A1
• Filed: 05/29/2015
• Published: 12/01/2016
• Est. Priority Date: 05/29/2015
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Udupi, Yathiraj B., Dutta, Debojyoti, Marathe, Madhav V., Nambiar, Raghunath O.
• Application Number:
  US14/726,336
• Publication Number:
  US 20160350146A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2009/45595 Network integration; Enabling network access in virtual machine instances
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/0897 by horizontal or vertical scaling of resources, or by migrating entities, e.g. virtual resources or entities
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/586 of virtual routers

Abstract

The present disclosure describes, among other things, a method for optimizing task scheduling in an optimally placed virtualized cluster using network cost optimizations. The method comprises computing a first network cost matrix for a plurality of available physical nodes, determining a first solution to a first optimization problem of virtual machine placement onto the plurality of available physical nodes based on the first network cost matrix, wherein the first solution comprises one or more optimally placed virtual machines, computing a second network cost matrix for allocating one or more tasks to one or more possible optimally placed virtual machines of the first solution, and determining a second solution to a second optimization problem of task allocation onto one or more possible optimally placed virtual machines of the first solution based on the second network cost matrix.

Claims

1. A method for optimizing task scheduling in an optimally placed virtualized cluster using network cost optimizations, the method comprising:

computing a first network cost matrix for a plurality of available physical nodes;

determining a first solution to a first optimization problem of virtual machine placement onto the plurality of available physical nodes based on the first network cost matrix, wherein the first solution comprises one or more optimally placed virtual machines;

computing a second network cost matrix for allocating one or more tasks to one or more possible optimally placed virtual machines of the first solution; and

determining a second solution to a second optimization problem of task allocation onto one or more possible optimally placed virtual machines of the first solution based on the second network cost matrix.

2. The method of claim 1, wherein the first optimization problem is a non-linear optimization problem.

3. The method of claim 1, wherein:

rows and columns of the first network cost matrix are both indexed by available physical nodes; and

entries of the first network cost matrix comprises network costs between possible pairs of physical nodes.

4. The method of claim 1, wherein determining the first solution comprises:

minimizing an objective function which calculates an aggregate network cost of possible data transfers between a selected subset of physical hosts to determine one or more physical hosts for creating a number of optimally placed virtual machines.

5. The method of claim 1, wherein determining the first solution comprises:

minimizing an aggregate network cost of possible data transfers between a selected subset of physical hosts subject to a constraint that a total number of selected subset of physical hosts in the first solution has the capacity to create a desired number of optimally placed virtual machines.

6. The method of claim 1, wherein the second optimization problem is a linear programming based constraint optimization problem.

7. The method of claim 1, wherein:

rows and columns of the second network cost matrix are indexed by the one or more optimally placed virtual machines and the one or more tasks; and

entries of the second network cost matrix comprises network costs, each network cost comprises a measure of data transfer time of moving data from a data split node to a particular physical node having a selected optimally placed virtual machine thereon to perform a particular task.

8. The method of claim 1, wherein determining the second solution comprises:

minimizing an objective function which calculates an aggregate network cost for performing the one or more tasks allocated respectively to a selected subset of optimally placed virtual machines.

9. The method of claim 1, wherein determining the second solution comprises:

minimizing an aggregate network cost for task allocation subject to one or more constraints.

10. The method of claim 9, wherein the one or more constraints comprises:

a first constraint ensuring each one of the one or more optimally placed virtual machine in the second solution has a number of allocated tasks which is less than or equal to a maximum number of tasks allowed for a particular optimally placed virtual machine.

11. The method of claim 9, wherein the one or more constraints comprises:

a second constraint ensuring, in the second solution, that a task is allocated to only one optimally placed virtual machine.

12. A system for optimizing task scheduling in an optimally placed virtualized cluster using network cost optimizations comprising:

at least one memory element;

at least one processor coupled to the at least one memory element; and

a virtual machine placement optimizer that when executed by the at least one processor is configured to;

compute a first network cost matrix for a plurality of available physical nodes;

determine a first solution to a first optimization problem of virtual machine placement onto the plurality of available physical nodes based on the first network cost matrix, wherein the first solution comprises one or more optimally placed virtual machines;

a task allocation optimizer that when executed by the at least one processor is configured to;

compute a second network cost matrix for allocating one or more tasks to one or more possible optimally placed virtual machines of the first solution; and

determine a second solution to a second optimization problem of task allocation onto one or more possible optimally placed virtual machines of the first solution based on the second network cost matrix.

13. The system of claim 12, wherein:

rows and columns of the first network cost matrix are both indexed by available physical nodes; and

entries of the first network cost matrix comprises network costs between possible pairs of physical nodes.

14. The system of claim 12, wherein determining the first solution comprises:

minimizing an objective function which calculates an aggregate network cost of possible data transfers between a selected subset of physical hosts to determine one or more physical hosts for creating a number of optimally placed virtual machines.

15. The system of claim 12, wherein determining the first solution comprises:

minimizing an aggregate network cost of possible data transfers between a selected subset of physical hosts subject to a constraint that a total number of selected subset of physical hosts in the first solution has the capacity to create a desired number of optimally placed virtual machines.

16. A computer-readable non-transitory medium comprising one or more instructions, for optimizing task scheduling in an optimally placed virtualized cluster using network cost optimizations, that when executed on a processor configure the processor to perform one or more operations comprising:

computing a first network cost matrix for a plurality of available physical nodes;

determining a first solution to a first optimization problem of virtual machine placement onto the plurality of available physical nodes based on the first network cost matrix, wherein the first solution comprises one or more optimally placed virtual machines;

computing a second network cost matrix for allocating one or more tasks to one or more possible optimally placed virtual machines of the first solution; and

determining a second solution to a second optimization problem of task allocation onto one or more possible optimally placed virtual machines of the first solution based on the second network cost matrix.

17. The medium of claim 16, wherein:

rows and columns of the second network cost matrix are indexed by the one or more optimally placed virtual machines and the one or more tasks; and

entries of the second network cost matrix comprises network costs, each network cost comprises a measure of data transfer time of moving data from a data split node to a particular physical node having a selected optimally placed virtual machine thereon to perform a particular task.

18. The medium of claim 16, wherein determining the second solution comprises:

minimizing an objective function which calculates an aggregate network cost for performing the one or more tasks allocated respectively to a selected subset of optimally placed virtual machines.

19. The medium of claim 16, wherein determining the second solution comprises:

minimizing an aggregate network cost for task allocation subject to one or more constraints.

20. The medium of claim 19, wherein the one or more constraints comprises one or more of the following:

a first constraint ensuring each one of the one or more optimally placed virtual machine in the second solution has a number of allocated tasks which is less than or equal to a maximum number of tasks allowed for a particular optimally placed virtual machine; and

a second constraint ensuring, in the second solution, that a task is allocated to only one optimally placed virtual machine.