Workload placement among resource-on-demand systems

• US 8,087,025 B1
• Filed: 06/29/2005
• Issued: 12/27/2011
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Graupner, Sven
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): WAI, ERIC CHARLES
• Application Number:
  US11/170,219
• Time in Patent Office: 2,372 Days
• Field of Search: 706/19, 709225-226, 709/202, 718/104, 707/10
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/505 considering the load

Abstract

Each of a plurality of nodes in an overlay network includes information for a corresponding resource-on-demand system, wherein the information may be used to select a resource-on-demand system to host the workload. A request to place a workload is received at a node in an overlay network. A distributed control algorithm is executed for selecting a resource-on-demand system host the workload.

Claims

1. A method comprising:

determining workload requirements for a workload;

creating, by a computer system, an ant including the workload requirements; and

using the ant to select a resource-on-demand system from a plurality of resource-on-demand systems to host the workload based on a probability the resource-on-demand system is operable to satisfy the workload requirements,

wherein using the ant to select a resource-on-demand system includes,

the ant traversing a path in an overlay network, wherein the path includes a plurality of nodes in the overlay network and the overlay network is organized in a hierarchy comprising a plurality of levels;

receiving information about corresponding resource-on-demand systems from the plurality of nodes in the overlay network, wherein the receiving of the information comprises receiving information about corresponding resource-on-demand systems from a plurality of nodes in a first level in the hierarchy;

determining whether any of the corresponding resource-on-demand systems is operable to satisfy the workload requirements; and

in response to none of the corresponding resource-on-demand systems being operable to satisfy the workload requirements, determining whether any of corresponding resource-on-demand systems for nodes in the overlay network in a lower-level in the hierarchy is operable to satisfy the workload requirements;

determining a probability to satisfy the workload requirements for each resource-on-demand system corresponding to each traversed overlay node; and

selecting one of the resource-on-demand systems to host the workload based on the determined probabilities.

2. The method of claim 1, further comprising:

receiving a request to place the workload at a node in the overlay network,

wherein each of the plurality of nodes in the overlay network stores information for a corresponding resource-on-demand system, the information being operable to be used to select a resource-on-demand system to host a workload.

3. The method of claim 2, further comprising:

using a plurality of ants representing a plurality of workloads to be placed to select data centers for placing the plurality of workloads.

4. The method of claim 2, wherein using the ant to select a resource-on-demand system further comprises:

using the ant to compare the workload requirements to the information stored in each of the plurality of nodes in the overlay network to select the resource-on-demand system to host the workload.

5. The method of claim 4, wherein using the ant to compare the workload requirements to the information stored in each of the plurality of nodes in the overlay network to select a resource-on-demand system to host the workload further comprises:

determining whether a corresponding resource-on-demand system for a first node in the overlay network visited by the ant is operable to satisfy the workload requirements; and

selecting the corresponding resource-on-demand system for the first node to host the application in response to the corresponding resource-on-demand system for the first node being operable to satisfy the workload requirements.

6. The method of claim 5, further comprising:

determining whether a corresponding resource-on-demand system for a neighbor node of the first node in the overlay network is operable to satisfy the workload requirements in response to the corresponding resource-on-demand system for the first node not being operable to satisfy the workload requirements; and

selecting the corresponding resource-on-demand system for the neighbor node to host the workload in response to the corresponding resource-on-demand system for the neighbor node being operable to satisfy the workload requirements.

7. The method of claim 6, wherein determining whether a corresponding resource-on-demand system for a neighbor node of the first node in the overlay network is operable to satisfy the workload requirements comprises:

selecting the neighbor node of the first node as a next node for the ant to visit; and

using the ant to determine whether the selected neighbor node or at least one neighbor node of the selected neighbor node has a corresponding resource-on-demand system operable to satisfy the workload requirements.

8. The method of claim 1, wherein determining a probability further comprises:

determining a capacity for each resource-on-demand system;

determining a closeness of each resource-on-demand system to a cooperating resource-on-demand system hosting an application communicating with the workload being placed; and

comparing the determined capacity and the determined closeness to the workload requirements.

9. The method of claim 1, wherein the ant stops traversing nodes in the overlay network after a predetermined number of nodes have been traversed.

10. The method of claim 1, wherein using the ant to select a resource-on-demand system further comprises:

using the ant to determine capacity for at least one resource-on-demand system, wherein the capacity is utilization of a configuration of the at least one resource-on-demand system; and

comparing to the capacity to the workload requirements of the workload.

11. The method of claim 10, wherein the capacity is expressed in terms of resource shares, wherein a resource share is a normalized metric for expressing a resource-on-demand system'"'"'s capability of handling a maximum amount of workload related to a particular type of application or class of service.

12. The method of claim 11, wherein the capacity is a utilization of a deployed capacity or an available capacity of a configuration of the at least one resource-on-demand system.

13. The method of claim 1, further comprising:

determining an available capacity and a deployed capacity for a resource-on-demand system; and

selecting the resource-on-demand system to host the workload if at least one of the available capacity and deployed capacity is operable to satisfy a required capacity of the workload.

14. The method of claim 1, wherein the resource-on-demand system is a data center.

15. A method comprising:

receiving an ant including workload requirements to place a workload and including a distributed control algorithm, wherein the ant is configured to traverse a plurality of nodes in an overlay network, and each of the plurality of nodes includes a computer system and the overlay network is organized in a hierarchy comprising a plurality of levels;

receiving information about corresponding resource-on-demand systems from the plurality of nodes in the overlay network, wherein the receiving of the information comprises receiving information about corresponding resource-on-demand systems from a plurality of nodes in a first level in the hierarchy;

determining whether any of the corresponding resource-on-demand systems is operable to satisfy the workload requirements; and

in response to none of the corresponding resource-on-demand systems being operable to satisfy the workload requirements, determining whether any of corresponding resource-on-demand systems for nodes in the overlay network in a lower-level in the hierarchy is operable to satisfy the workload requirements;

executing the distributed control algorithm of the ant at the plurality of nodes in the overlay network to select a resource-on-demand system from a plurality of resource-on-demand systems to host the workload, wherein the executing comprises determining a probability to satisfy the workload requirements for each resource-on-demand system corresponding to each traversed overlay node; and

selecting one of the resource-on-demand systems to host the workload based on the determined probabilities.

16. The method of claim 15, wherein executing a distributed control algorithm further comprises:

executing a round robin search algorithm to select the resource-on-demand system for hosting the workload.

17. The method of claim 16, wherein executing a round robin search algorithm comprises:

selecting nodes in a round robin manner; and

comparing information about a corresponding resource-on-demand system from each of the nodes to the workload requirements.

18. The method of claim 15, wherein executing the distributed control algorithm further comprises:

randomly selecting the plurality of nodes in the overlay network; and

comparing information about the corresponding resource-on-demand system from each of the randomly selected nodes to the workload requirements.

19. The method of claim 15, wherein executing the distributed control algorithm further comprises:

using a greedy algorithm to select the plurality of nodes in the overlay network; and

comparing information about the corresponding resource-on-demand system from each of the plurality of nodes to the workload requirements.

20. The method of claim 15, wherein executing a distributed control algorithm further comprises:

receiving information about corresponding resource-on-demand systems from nodes in a region in the overlay network; and

comparing information about corresponding resource-on-demand system for each node in the region with the workload requirements.

21. The method of claim 15, wherein executing the distributed control algorithm further comprises:

determining capacity of the corresponding resource-on-demand system from each of the plurality of nodes in the overlay network;

comparing the capacity of the corresponding resource-on-demand system from each of the plurality of nodes with the workload requirements; and

selecting the resource-on-demand system to host the workload if there is sufficient capacity to satisfy the workload demand requirements.

22. The method of claim 21, wherein the capacity is expressed in terms of resource shares, wherein a resource share is a normalized metric for expressing a resource-on-demand system'"'"'s capability of handling a maximum amount of workload related to a particular type of application or class of service.

23. The method of claim 22, wherein the capacity is a utilization of a deployed capacity or an available capacity of a configuration of the at least one resource-on-demand system.

24. An overlay network comprising a plurality of nodes and the overlay network is organized in a hierarchy comprising a plurality of levels, wherein a computer system hosting a node of the plurality of nodes comprises:

a receiver operable to receive a request for placing a workload at a resource-on-demand system, wherein each of the plurality of nodes in the overlay network stores information for a corresponding resource-on-demand system, the information being operable to be used to select a resource-on-demand system to host the workload;

a storage device storing information for a corresponding resource-on-demand system of the node; and

a processor operable to execute an ant having workload requirements for the workload for determining a probability the corresponding resource-on-demand system of the node is operable to satisfy workload requirements for hosting the workload,

wherein the ant is configured to traverse a plurality of nodes in the overlay network, and selecting the resource-on-demand system to host the workload comprises receiving information about corresponding resource-on-demand systems from the plurality of nodes in the overlay network; and

selecting one of the resource-on-demand systems to host the workload based on the determined probabilities,

wherein the receiving of the information comprises receiving information about corresponding resource-on-demand systems from a plurality of nodes in a first level in the hierarchy;

determining whether any of the corresponding resource-on-demand systems is operable to satisfy the workload requirements; and

in response to none of the corresponding resource-on-demand systems being operable to satisfy the workload requirements, determining whether any of corresponding resource-on-demand systems for nodes in the overlay network in a lower-level in the hierarchy is operable to satisfy the workload requirements.

25. The computer system of claim 24, wherein the information for a corresponding resource-on-demand system comprises:

capacity for the resource-on-demand system expressed in terms of resource shares, wherein a resource share is a normalized metric for expressing a resource-on-demand system'"'"'s capability of handling a maximum amount of workload related to a particular type of application or class of service.

26. The computer system of claim 25, wherein the capacity is a utilization of a deployed capacity or an available capacity of a configuration of the corresponding resource-on-demand system.

27. The computer system of claim 25, wherein the workload requirements are expressed in service shares, wherein the service shares are for the workload to be placed include the resource utilization of the workload to be placed determined as a function of the resource shares.

28. The computer system of claim 24, wherein the plurality of nodes is operable to execute a distributed control algorithm for selecting a resource-on-demand system to host the workload.

29. The computer system of claim 24, wherein the overlay network comprises a distributed-hash table overlay network.

30. The computer system of claim 24, wherein the information for corresponding resource-on-demand systems that is related by a predetermined metric is stored at nodes in close proximity in the overlay network.

31. The computer system of claim 30, wherein the predetermined metric is latency, such that workloads including applications communicating with each other are placed at resource-on-demand systems to minimize communication latency between the applications.

32. A computer system hosting a node in an overlay network comprising a plurality of nodes and the overlay network is organized in a hierarchy comprising a plurality of levels, wherein the plurality of nodes include information for corresponding resource-on-demand systems and being operable to execute a distributed control algorithm for selecting a resource-on-demand system to host a workload based on information for a corresponding resource-on-demand system in at least one of the plurality of nodes, the computer system comprising:

a receiver means for receiving a request for placing a workload at a resource-on-demand system, wherein each of the plurality of nodes in the overlay network stores information for a corresponding resource-on-demand system, the information being operable to be used to select a resource-on-demand system to host the workload;

a storage device means for storing information for a corresponding resource-on-demand system of the node; and

a processor means operable to execute an ant including the distributed control algorithm for determining whether the corresponding resource-on-demand system of the node is operable to satisfy workload requirements for hosting the workload,

wherein the ant is configured to traverse the plurality of nodes in the overlay network, and selecting the resource-on-demand system to host the workload comprises receiving information about corresponding resource-on-demand systems from the plurality of nodes in the overlay network;

determining a probability to satisfy the workload requirements for each resource-on-demand system corresponding to each traversed overlay node; and

selecting one of the resource-on-demand systems to host the workload based on the determined probabilities,

wherein the receiving of the information comprises receiving information about corresponding resource-on-demand systems from a plurality of nodes in a first level in the hierarchy;

determining whether any of the corresponding resource-on-demand systems is operable to satisfy the workload requirements; and

in response to none of the corresponding resource-on-demand systems being operable to satisfy the workload requirements, determining whether any of corresponding resource-on-demand systems for nodes in the overlay network in a lower-level in the hierarchy is operable to satisfy the workload requirements.

33. The computer system of claim 32, wherein the information for a corresponding resource-on-demand system comprises:

capacity for the resource-on-demand system expressed in terms of resource shares, wherein a resource share is a normalized metric for expressing a resource-on-demand system'"'"'s capability of handling a maximum amount of workload related to a particular type of application or class of service.

34. The computer system of claim 33, wherein the capacity is a utilization of a deployed capacity or an available capacity of a configuration of the corresponding resource-on-demand system.

35. The computer system of claim 34, wherein the workload requirements are expressed in service shares, wherein the service shares include the resource utilization of the workload to be placed determined as a function of the resource shares.