Dynamic application placement under service and memory constraints

• US 20060242647A1
• Filed: 04/21/2005
• Published: 10/26/2006
• Est. Priority Date: 04/21/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kimbrel, Tracy Jay, Steinder, Malgorzata, Tantawi, Asser Nasreldin, Sviridenko, Maxim
• Application Number:
  US11/110,766
• Publication Number:
  US 20060242647A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

An optimization problem models the dynamic placement of applications on servers under two types of simultaneous resource requirements, those that are dependent on the loads placed on the applications and those that are independent. The demand (load) for applications changes over time and the goal is to satisfy all the demand while changing the solution (assignment of applications to servers) as little as possible.

Claims

1. A method for on-demand application resource allocation under one or more load-dependent resource constraints and one or more load-independent resource constraints by dynamically reconfiguring placement of applications on servers in a rigorous mathematical language, the method comprising the steps of:

describing a plurality of servers and a plurality of applications as abstract sets of elements corresponding to the plurality of servers and the plurality of applications, respectively,

defining sets of load-dependent and sets of load independent capacities of said abstract sets of elements,

determining a feasibility for a given assignment of applications to servers,

determining a feasibility for distributing demand between servers, and

dynamically reconfiguring placement of applications on servers based on an objective function to optimize a placement of applications on servers.

2. The method for on-demand application resource allocation recited in claim 1, wherein the objective function comprises a total number of applications assignment changes from a previous time interval to a current time interval.

3. A method for on-demand application resource allocation under one or more load-dependent resource constraints and one or more load-independent resource constraints comprising the steps of:

ordering servers by decreasing value of their densities defined as available service capacity divided by memory capacity for each server;

ordering applications by decreasing densities defined as number of requests in a given time interval divided by memory requirements for each application;

initially loading a highest density application to a highest density server which has enough memory for that application and loading other applications on servers according said steps of ordering; and

dynamically reconfiguring placement of applications on servers according to an objective function which satisfy all applications demand while respecting memory and processing constraints of every server.

4. The method for on-demand application resource allocation recited in claim 3, wherein the step of initially loading comprises the steps of:

for each application assigned to a server, determining if the application completely fits the server;

if the application completely fits the server, deleting the application from a sorted list of the ordered applications, updating server and memory demand capacities, and recomputing new densities of applications;

otherwise,

if the application does not completely the server, deleting the server from a sorted list of the ordered servers, assigning part of a demand for the application to the server, computing a new application density with remaining demand, and re-inserting the application into the list of ordered applications; and

returning to the ordering steps until the sorted list of ordered applications is empty.

5. The method for on-demand application resource allocation recited in claim 4, wherein in the step of dynamically reconfiguring placement of applications on servers comprises the steps of:

defining a bipartite graph between a set of servers and a set of applications with an edge between every application-server pair such that a server of the pair has a copy of the application of the pair; and

solving a bipartite flow problem on the bipartite graph where application demand defines an amount of flow located at that vertex and server demand capacity defines capacity of a corresponding vertex.

6. The method for on-demand application resource allocation recited in claim 5, wherein the step of dynamically reconfiguring placement of applications further comprises the steps of:

determining if a feasible solution is found in the step of solving and, if not, defining and solving an initial placement problem using remaining server resources and unrouted demand to define memory and demand capacities and requirements;

determining if there is a feasible solution to the initial placement problem and, if not, deleting an edge which minimizes a ratio of flow sent by the edge to a memory of application incident to it from a current bipartite graph; and

returning to the step of defining a bipartite graph until a feasible solution is found to the flow problem.

7. A system for on-demand application resource allocation under one or more load-dependent resource constraints and one or more load-independent resource constraints comprising:

a plurality of servers arranged in one or more clusters;

a plurality of application clusters, each said application cluster running on one or more servers in a cluster of servers;

a request router receiving application requests from a plurality of clients and directing the requests to appropriate application clusters;

a placement controller which receives an application workload prediction and application resource requirements and calculates application densities, defined as number of requests in a given time interval divided by memory requirements, and server densities, defined as available service capacity divided by memory capacity; and

a placement executor responsive to said placement controller which executes application placements on said servers, wherein said placement controller initially causes said placement executor to load a highest density application to a highest density server which has enough memory for that application and loading other applications on servers according said steps of ordering; and

thereafter dynamically reconfigures placement of applications on servers according to an objective function which satisfy all applications demand while respecting memory and processing constraints of every server.

8. The system for on-demand application resource allocation recited in claim 7, wherein the placement controller receives feedback from the placement executor and for each application assigned to a server, determines if the application completely fits the server, and if the application completely fits the server, deletes the application from a sorted list of the ordered applications, updates server and memory demand capacities, and recomputes new densities of applications, but otherwise, if the application does not completely the server, deletes the server from a sorted list of the ordered servers, assigns part of a demand for the application to the server, computes a new application density with remaining demand, and re-inserts the application into the list of ordered applications, until the sorted list of ordered applications is empty.

9. The system for on-demand application resource allocation recited in claim 8, wherein the placement controller defines a bipartite graph between a set of servers and a set of applications with an edge between every application-server pair, and solves a bipartite flow problem on the bipartite graph where application demand defines an amount of flow located at that vertex and server demand capacity defines capacity of a corresponding vertex.

10. The system for on-demand application resource allocation recited in claim 9, wherein the placement controller determines if a feasible solution is found and, if not, defines and solves an initial placement problem using remaining server resources and unrouted demand to define memory and demand capacities and requirements, determines if there is a feasible solution to the initial placement problem and, if not, deletes an edge which minimizes a ratio of flow sent by the edge to a memory of application incident to it from a current bipartite graph, until a feasible solution is found to the flow problem.

11. A computer readable medium containing code for performing on-demand application resource allocation under one or more load-dependent resource constraints and one or more load-independent resource constraints, the code implementing a method comprising the steps of:

ordering servers by decreasing value of their densities defined as available service capacity divided by memory capacity for each server;

ordering applications by decreasing densities defined as number of requests in a given time interval divided by memory requirements for each application;

initially loading a highest density application to a highest density server which has enough memory for that application and loading other applications on servers according said steps of ordering; and

dynamically reconfiguring placement of applications on servers according to an objective function which satisfy all applications demand while respecting memory and processing constraints of every server.

12. The computer readable medium recited in claim 11, wherein the code implements the step of initially loading implements the steps of:

for each application assigned to a server, determining if the application completely fits the server;

if the application completely fits the server, deleting the application from a sorted list of the ordered applications, updating server and memory demand capacities, and recomputing new densities of applications;

otherwise,

if the application does not completely the server, deleting the server from a sorted list of the ordered servers, assigning part of a demand for the application to the server, computing a new application density with remaining demand, and re-inserting the application into the list of ordered applications; and

returning to the ordering steps until the sorted list of ordered applications is empty.

13. The computer readable medium recited in claim 12, wherein which implements the step of dynamically reconfiguring placement of applications on servers implements the steps of:

defining a bipartite graph between a set of servers and a set of applications with an edge between every application-server pair such that a server of the pair has a copy of the application of the pair; and

solving a bipartite flow problem on the bipartite graph where application demand defines an amount of flow located at that vertex and server demand capacity defines capacity of a corresponding vertex.

14. The computer readable medium recited in claim 13, wherein the code which implements the step of dynamically reconfiguring placement of applications further implements the steps of:

determining if a feasible solution is found in the step of solving and, if not, defining and solving an initial placement problem using remaining server resources and unrouted demand to define memory and demand capacities and requirements;

determining if there is a feasible solution to the initial placement problem and, if not, deleting an edge which minimizes a ratio of flow sent by the edge to a memory of application incident to it from a current bipartite graph; and

returning to the step of defining a bipartite graph until a feasible solution is found to the flow problem.