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

• US 10,326,649 B2
• Filed: 07/17/2015
• Issued: 06/18/2019
• 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): Rahman, Sm A
• Assistant Examiner(s): Pant, Ranjan
• Application Number:
  US14/802,825
• Publication Number:
  US 20160142253A1
• Time in Patent Office: 1,432 Days
• 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/823 Prediction of resource usage
• 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 method for operating a cloud computing infrastructure. In one embodiment, the 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 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 method for operating a cloud computing system, the method comprising:

receiving a user application request having one or more user specified objectives and allocation constraints, wherein the user application request specifying requirements for placing logical entities on physical entities in a computing infrastructure, and each allocation constraint corresponds to an allocation domain being used in the placing of the logical entities to the physical entities, and the allocation domains are created based on 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;

generating one or more bias weights for each allocation domain, wherein each bias weight for each allocation domain indicates an importance of the allocation domain in accommodating the user application request, and generation of the bias weights is based on a use of a domain expert for mapping components of the objective function to a set of biasing functions;

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

generating, using said computed biased probability distribution in accordance with the user specified objectives, a set of candidate placement solutions that satisfy the one or more user specified objectives and allocation constraints;

comparing each candidate placement solution with the allocation constraints;

identifying an optimized placement solution among the set of candidate placement solutions based on the comparison of each candidate placement solution with the allocation constraint; and

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

wherein a programmed process device performs one of said receiving, said bias weight generating, said computing, said sample placement solution generating, said obtaining, said optimizing and said reconfiguring.

2. The method according to claim 1, wherein identifying the optimized placement solution comprises using an objective function evaluation process that satisfies combined user objectives and constraints given a current state of resources in said computing infrastructure.

3. The method according to claim 2, further comprising:

iteratively repeating said probability distribution computing using said bias weights; and

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

4. The method according to claim 3, 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 infrastructure; and

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

5. The method according to claim 4, wherein identifying the 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.

6. The method according to claim 4, 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.

7. The method according to claim 5, further comprising creating a bias weight using 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 one or more optimal placement solutions.

8. The method according to claim 2, 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 the generated placement solution 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.

9. A method for operating a cloud computing system, the method comprising:

receiving a user application request having one or more user specified objectives and allocation constraints, said request specifying one or more 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;

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;

creating an allocation policy for each allocation domain;

generating a set of candidate placement solutions that satisfy the user specified objectives and allocation constraints, wherein generation of the candidate placement solutions is based on a biased probability distribution associated with bias weights for each allocation domain;

evaluating each said generated candidate placement solution against the allocation policy corresponding to each allocation domain for the received application request to assess compliance of said allocated constraints in said cloud infrastructure;

using the assessed compliance to identify an optimized placement solution from the evaluation among each candidate placement solution with the allocation policy, wherein the identified optimized placement solution satisfies the user specified objectives and allocation constraints; and

wherein a programmed process device performs one of said receiving, constructing, creating, and evaluating.

10. The method as in claim 9, 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.

11. The method as in claim 10, 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.

12. The method as in claim 11, 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.

13. The method as in claim 12, 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.

14. The method as in claim 9, further comprising:

generating the bias weights for each allocation domain based on said user specified objectives and allocation constraints;

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

obtaining an optimized placement solution from said plurality of candidate placement solutions that satisfies all said user specified objectives and 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.

15. A method for operating a cloud computing system, the method comprising:

receiving a user application request having one or more user specified objectives and allocation constraints, wherein the user application request specifying requirements for placing logical entities on physical entities in a computing infrastructure, and each allocation constraint corresponds to an allocation domain being used in the placing of the logical entities to the physical entities, and the allocation domains are created based on 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;

generating one or more bias weights for each allocation domain, wherein each bias weight for each allocation domain indicates an importance of the allocation domain in accommodating the user application request, and generation of the bias weights is based on a use of a domain expert for mapping components of the objective function to a set of biasing functions;

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

generating, using the computed biased probability distribution in accordance with the user specified objectives, a set of candidate placement solutions that satisfy the user specified objectives and allocation constraints, given a current state of resources in said computing infrastructure;

iteratively repeating said probability distribution computing using said bias weights;

evaluating each of the plurality of candidate optimized placement solutions, with an objective function that satisfies the user specified objectives and allocation constraints based on the current state of resources in said computing infrastructure;

identifying at least one candidate optimized placement solution that satisfy said user objectives and constraints based on the evaluation, wherein, at each iteration, said bias weights are adjusted to generate more candidate optimized placement solutions at each successive iteration; and

dynamically reconfiguring the computing infrastructure by allocating the logical entities in the request to the physical entities based on the identified candidate optimized placement solution,

wherein a programmed process device performs one of said receiving, said bias weight generating, said computing, said candidate placement solution generating, said obtaining, said iteratively repeating, said adjusting, and said reconfiguring.

16. The method according to claim 15, wherein said bias weights corresponds to one of:

a specified optimization objective or an allocation constraint, said method comprising;

obtaining a current state information from a model of the current computing system; and

computing the bias weights based on the current state and the respective optimization objective or allocation constraint; and

maintaining a set of variables, an objective function of said variables set, and a bias function, related its objective function.

17. The method according to claim 15, 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 the candidate placement solution in said computing infrastructure;

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

evaluating each said generated candidate placement solution 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 method as in claim 17, wherein said constructing an allocation domain comprises:

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; and

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, said method 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.

19. The method as in claim 18, wherein said one or more functions are univariate, bivariant or multivariate functions.

20. The method as in claim 18, wherein an allocation domain comprises a resources AD for allocating PE resources, said method further comprising:

receiving, at the processor device, a variable associated with a physical entity, the variable including a vector having values used in determining one or more of;

an availability of the physical entity corresponding to a host device i, and a demand of a logical entity on that physical entity resource;

evaluating a function f(i) for determining whether an availability of that host device relative to a demand indicated in said vector variable, satisfies an allocation policy;

making an LE placement on a PE based on said function evaluation; and

updating said vector resulting from the LE placement.