Decentralized application placement for web application middleware

• US 7,496,667 B2
• Filed: 01/31/2006
• Issued: 02/24/2009
• Est. Priority Date: 01/31/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Adam, Constantin M., Steinder, Malgorzata, Pacifici, Giovanni, Spreitzer, Michael J., Tang, Chunqiang
• Primary Examiner(s): Avellino; Joseph E
• Assistant Examiner(s): SMARTH, GERALD A
• Application Number:
  US11/344,606
• Publication Number:
  US 20070180083A1
• Time in Patent Office: 1,120 Days
• Field of Search: 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 9/505 considering the load
• 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

Abstract

A decentralized process to ensure 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 decentralized application resource allocation for a cluster of nodes, the method comprising:

utilizing an overlay construction algorithm to identify a subset of nodes in the node cluster for a local node, the local node including a current set of applications executing at the local node, the subset of nodes being logical neighbors of the local node;

receiving, at the local node, resource utilization data of applications from the subset of nodes in the node cluster, wherein receiving resource utilization data includes receiving a list of active applications from each node in the subset of nodes, receiving a resource supply and demand for each active application in the list, and receiving resource utilization data for each active application in the list;

determining a new set of applications to execute at the local node which optimizes an objective function as computed locally by the local node based, at least in part, on the utilization data, wherein determining the new set of applications to execute at the local node further comprises defining a set of running applications executing on the local node, sorting the running applications in increasing order of delivered density, wherein delivered density is defined as a ratio between an amount of CPU delivered to the application and a memory utilized by the application, defining a set of standby applications, the standby applications including applications executing on the subset of nodes and not on the local node and applications not executing anywhere in the cluster of nodes, filtering the set of standby applications by removing from the set of standby applications the applications for which there is no unsatisfied demand, the unsatisfied demand being defined as the difference between demand and supply for resources, sorting the set of standby applications in decreasing order of unsatisfied density, the unsatisfied density defined as a ratio between the unsatisfied demand and the memory utilized by the application, shifting load by attempting to assign as much load as possible from the local node to the subset of nodes, building a plurality of local configurations by successively replacing applications from the sorted set of running applications with applications from the sorted set of standby applications, and selecting from the local configurations an optimal configuration that maximizes CPU utilization on the local node;

modifying which applications are executed at the local node according to the new set of executing applications;

sending from the local node to the subset of nodes in the node cluster application execution changes between the new set of applications and the current set of applications at the local node, wherein sending from the local node to the subset of nodes in the node cluster application execution changes includes using a gossip protocol, in which each node aggregates messages the node has received or originated during a predetermined interval of time, before sending the aggregated messages, inside a single message, to neighboring nodes;

locking, for each application that the local node starts and stops, all nodes located two logical hops away and preventing the nodes from starting and stopping the application; and

acquiring, from a designated node, a lock that prevents other nodes from starting an application that currently is not running anywhere in the cluster of nodes,

wherein the receiving, determining, modifying and sending operations are performed independently and asynchronously at each node in the cluster of nodes.