Application placement through multiple allocation domain agents and flexible cloud scheduler framework

• US 9,800,465 B2
• Filed: 11/14/2014
• Issued: 10/24/2017
• Est. Priority Date: 11/14/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Steinder, Malgorzata, Tantawi, Asser N.
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US14/542,103
• Publication Number:
  US 20160142338A1
• Time in Patent Office: 1,075 Days
• Field of Search: 709226, 709213, 710 36, 711150
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

There are provided a system, a method and a computer program product for operating a cloud computing infrastructure. In one embodiment, the system and method performs allocation domain modeling and provides a cloud scheduler framework that takes as input desired optimization objectives and the workload constraints and efficiently produces a placement solution that satisfies the constraints while optimizing the objectives in a way that adjusts itself depending on the objectives. As the objectives change, e.g., due to actions from system administrators or due to changes in business policies, the system optimizes itself accordingly and still produces efficient and optimized placement solutions. The system and method constructs an Allocation Domain (AD) that is a particular facet for allocating a logical entity to a physical entity. An AD is created using: variables, functional definitions (functions of variables), and a policy specification that includes a Boolean expression (of the functional definitions).

Claims

1. A system for operating a cloud computing system comprising:

a memory storage device; and

a processor device, coupled to the memory storage device, and configured to;

receive a user application request having one or more user specified objectives and allocation constraints, said user request specifying requirements for placing logical entities on physical entities in a computing infrastructure;

generate one or more bias weights based on said user specified objectives and allocation constraints by employing an allocation domain that is created using a set of primitive variables, a set of functional definitions for the set of primitive variables, a policy specification for the set of functional definitions, and at least one post-allocation change to the set of primitive variables;

compute a probability distribution using said bias weights, said bias weights increasing likelihood of generating an optimized placement solution;

generate, using said biased computed biased probability distribution, several sample placement solutions;

obtain an optimized placement solution from said several sample solutions that satisfies all said user specified objectives and said user specified allocation constraints; and

dynamically reconfigure the computing infrastructure by allocating the logical entities in the request to the physical entities based on said optimized placement solution.

2. The system according to claim 1, wherein to obtain an optimized placement solution, said processor device is further configured to:

evaluate said several sample placement solutions using an objective function based on a combination of said user objectives and allocation constraints, and

obtain said optimized placement solution based on said objective function evaluating that satisfies combined user objectives and constraints given a current state of resources in said computing infrastructure.

3. The system according to claim 2, wherein said processor device is further configured to:

iteratively repeat computing said probability distribution using said bias weights, said generating several placement solutions and said optimizing to obtain the optimized placement solution that satisfy said user objectives and constraints; and

adjust, at each iteration, said bias weights to generate more optimized sample placement solutions at each successive iteration.

4. The system according to claim 3, wherein to adjust said bias weights, said processor device is further configured to:

maintain a set of variables, a variable representing a state of PE resources and an objective for placing a logical entity on a physical entity;

specify one or more objective functions using said variables set, a function defining a condition for allocating an LE to a PE based on a current state of said computing (cloud) infrastructure; and

create a biasing function related to the objective function and the current infrastructure state.

5. A system for operating a cloud computing system comprising:

a memory storage device; and

a processor device, coupled to the memory storage device, and configured to;

receive a user application request having one or more user specified objectives and allocation constraints, said request specifying requirements for placing logical entities (LE) on physical entities (PE) in a computing infrastructure;

construct an allocation domain (AD) corresponding to each received user specified allocation constraint, each AD representing a particular allocation of a LE to a PE in a sample placement solution in said computing infrastructure;

wherein the AD is created using;

a set of primitive variables, a set of functional definitions for the set of primitive variables, a policy specification for the set of functional definitions, and at least one post-allocation change to the set of primitive variables;

dynamically create an allocation policy specific to an allocation domain; and

evaluate each said generated sample placement solutions against an allocation policy corresponding to each said one or more allocation domains for a particular received application request to ensure compliance of said allocated constraints in said cloud infrastructure.

6. The system as in claim 5, wherein to construct an allocation domain, said processor device is further configured to:

create and modify one or more variables for said AD, each variable representing a state of PE resources and an allocation constraint for placing a LE on a PE;

specify one or more functions using said one or more AD variables, a function defining a condition for allocating an LE to a PE based on a current state of said computing infrastructure.

7. The system as in claim 6, wherein said processor device is further configured to:

evaluate each of said one or more functions associated with one or more AD variables implicated by said received user application request;

make an LE placement on a PE of a computing infrastructure based on said function evaluation that satisfies said allocation policy; and

update AD variables resulting from the LE placement.

8. The system as in claim 6, wherein to evaluate each of said one or more functions, said processor device is further configured to:

implement a Boolean expression to determine whether each of said one or more functions associated with one or more AD variables implicated by said allocation constraints of said application placement request, are satisfied.

9. A computer program product comprising a computer readable storage medium tangibly embodying a program of instructions executable by the computer for operating a cloud computing system, the program of instructions, when executing, performing the following steps:

receiving a user application request having one or more user specified objectives and allocation constraints, said user request specifying requirements for placing logical entities on physical entities in a computing infrastructure;

generating one or more bias weights based on said user specified objectives and allocation constraints by employing an allocation domain that is created using a set of primitive variables, a set of functional definitions for the set of primitive variables, a policy specification for the set of functional definitions, and at least one post-allocation change to the set of primitive variables;

computing a probability distribution using said bias weights, said bias weights increasing likelihood of generating an optimized placement solution;

generating, using said biased computed biased probability distribution, several sample placement solutions;

obtaining an optimized placement solution from said several sample solutions that satisfies all said user specified objectives and said user specified allocation constraints; and

dynamically reconfiguring the computing infrastructure by allocating the logical entities in the request to the physical entities based on said optimized placement solution.

10. The computer program product according to claim 9, wherein said obtaining an optimized placement solution to comprises:

evaluating, said several sample placement solutions, using an objective function based on a combination of said user objectives and allocation constraints, and

obtaining said optimized placement solution based on said objective function evaluating that satisfies combined user objectives and constraints given a current state of resources in said computing infrastructure.

11. The computer program product according to claim 10, further comprising:

iteratively repeating said probability distribution computing using said bias weights, said generating several placement solutions and said optimizing to obtain the optimized placement solution that satisfy said user objectives and constraints; and

adjusting, at each iteration, said bias weights to generate more optimized sample placement solutions at each successive iteration.

12. The computer program product according to claim 11, wherein said adjusting bias weights comprises:

maintaining a set of variables, a variable representing a state of PE resources and an objective for placing a logical entity on a physical entity;

specifying one or more objective functions using said variables set, a function defining a condition for allocating an LE to a PE based on a current state of said computing (cloud) infrastructure; and

creating a biasing function related to the objective function and the current infrastructure state.

13. The computer program product according to claim 12, wherein said obtaining an optimized placement solution comprises:

minimizing a scalar objective function comprising a combination of received objective functions each weighted with a respective weight obtained by an importance-based sampling method and a respective biasing weight applied to each objective function.

14. The computer program product according to claim 13, creating a bias weight using one of:

a domain expert for mapping components of the objective function to individual biasing functions;

or

a semi-supervised learning system that automatically generates random placement solutions using parameterized biasing functions, calculates corresponding values of the objective function; and

continuously adjusts parameters of the biasing functions so as to generate optimal placement solutions.

15. The computer program product according to claim 12, wherein a user objective comprises one or more of:

a load balancing objective, a network communications overhead minimizing objective, a software licensing minimization cost, and a physical proximity deviation minimizing objective;

said bias function comprising one or more of;

a load balance biasing function associated with distributing a load based on the load balancing objective;

a network traffic biasing function associated with placement of communicating virtual machines close to each other to avoid networking traffic;

a software license sharing biasing function associated with increasing license sharing to minimize a software licensing cost objective; and

a location proximity biasing function for minimizing a deviation from location user preferences related to placement of virtual entities with respect to each other.

16. The computer program product according to claim 10, further comprising:

constructing an allocation domain (AD) corresponding to each received user specified allocation constraint, each AD representing a particular allocation of a LE to a PE in a placement solution in said computing infrastructure;

dynamically creating an allocation policy specific to an allocation domain; and

evaluating each said generated sample placement solutions against an allocation policy corresponding to each said one or more allocation domains for a particular received application request to ensure compliance of said allocated constraints in said cloud infrastructure.

17. A computer program product comprising a computer readable storage medium tangibly embodying a program of instructions executable by the computer for operating a cloud computing system, the program of instructions, when executing, performing the following steps:

receiving a user application request having one or more user specified objectives and allocation constraints, said request specifying requirements for placing logical entities (LE) on physical entities (PE) in a computing infrastructure;

constructing an allocation domain (AD) corresponding to each received user specified allocation constraint, each AD representing a particular allocation of a LE to a PE in a sample placement solution in said computing infrastructure, wherein the AD is created using;

a set of primitive variables, a set of functional definitions for the set of primitive variables, a policy specification for the set of functional definitions, and at least one post-allocation change to the set of primitive variables;

dynamically creating an allocation policy specific to an allocation domain; and

evaluating each said generated sample placement solutions against an allocation policy corresponding to each said one or more allocation domains for a particular received application request to ensure compliance of said allocated constraints in said cloud infrastructure.

18. The computer program product as in claim 17, wherein said constructing an allocation domain comprises one or more of:

creating and modifying one or more variables for said AD, each variable representing a state of PE resources and an allocation constraint for placing a LE on a PE;

specifying one or more functions using said one or more AD variables, a function defining a condition for allocating an LE to a PE based on a current state of said computing infrastructure.

19. The computer program product as in claim 18, further comprising:

evaluating each of said one or more functions associated with one or more AD variables implicated by said received user application request;

making an LE placement on a PE of a computing infrastructure based on said function evaluation that satisfies said allocation policy; and

updating AD variables resulting from the LE placement.

20. The computer program product as in claim 19, wherein said evaluating each of said one or more functions comprises:

implementing a Boolean expression to determine whether each of said one or more functions associated with one or more AD variables implicated by said allocation constraints of said application placement request, are satisfied.

21. The computer program product as in claim 20, further comprising:

managing creation, modifying or updating of allocation policy state and said one or more allocation domain variables and functions, using a corresponding AD agent (ADA); and

managing all corresponding ADAs by an AD manager (ADM), said ADAs and ADM providing a common interfaces to provide a realization of specific ADs applied to the computing infrastructure.

22. The computer program product as in claim 17, further comprising:

generating one or more bias weights based on said user specified objectives and allocation constraints;

computing a probability distribution using said bias weights, said bias weights increasing likelihood of generating an optimized placement solution;

generating, using said biased computed biased probability distribution, several sample placement solutions;

obtaining an optimized placement solution from said several sample solutions that satisfies all said user specified objectives and said user specified allocation constraints; and

dynamically reconfiguring the computing infrastructure by allocating the logical entities in the request to the physical entities based on said optimized placement solution.