Systems and methods for decentralized service placement in a resource pool

• US 10,148,771 B2
• Filed: 01/04/2018
• Issued: 12/04/2018
• Est. Priority Date: 09/16/2015
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Yazir, Ya{hacek over (g)}iz Onat, Halen, Joacim, Abbasi, Zahra
• Primary Examiner(s): Mirza, Adnan M
• Application Number:
  US15/862,204
• Publication Number:
  US 20180131777A1
• Time in Patent Office: 334 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

Exemplary methods for distributed multi-component service placement in a resource pool include utilizing a hierarchy of agents associated with computing resources of a cloud architecture. A root agent in the hierarchy can receive service requests specifying resource requirements and optionally location or affinity constraints, transform these into service request descriptions, and pass the service request descriptions down through the hierarchy to arrive at leaf nodes. The leaf nodes can each, perhaps in parallel, generate solution encodings indicating possible placements of some or all of the components of the service request that one or more computing devices associated with each agent can locally provide while still satisfying the resource requirements. The generated solution encodings can be passed back up and be consolidated as they flow through the hierarchy, allowing the root agent to quickly and accurately determine whether the service request may be fulfilled, and optionally place the service.

Claims

1. A method in computing device functioning as a leaf agent and as a child to a parent agent in a hierarchy of agents for enabling decentralized service placement, where each of the agents are executed by separate computing devices, the method comprising:

receiving, at the leaf agent from the parent agent, a service request description that specifies resource requirements for a plurality of components of a service to be deployed;

generating, at the leaf agent, at least one solution encoding indicating possible placements of at least one of the plurality of components of the service request description that at least one computing device can provide local to the leaf agent while satisfying a resource requirement of the at least one of the plurality of components of the service; and

transmitting, by the leaf agent to the parent agent, the at least one solution encodings.

2. The method of claim 1, wherein generating the at least one solution encoding comprises:

generating, based upon a plurality of groups identified by a query placement partition, at least one affinity-based encoding, wherein the at least one affinity-based encoding indicates a maximal number of components from each of the plurality of groups that could potentially be provided by the at least one computing device local to the leaf agent.

3. The method of claim 2, wherein generating at least one solution encoding further comprises:

generating, based upon the at least one affinity-based encoding and a description of available resources of the at least one computing device local to the leaf agent, at least one refined encoding, wherein the at least one refined encoding is derived from the at least one affinity-based encoding and indicates numbers of the components of a corresponding affinity-based encoding that the at least one computing device local to the leaf agent can provide given available local resources.

4. The method of claim 2, further comprising:

generating, based upon the resource requirements, a query placement partition identifying a plurality of groups of the plurality of components, wherein the plurality of groups includes at least one colocation group and at least one non-colocation group, wherein at least one of the plurality of groups identified by the query placement partition includes one or more non-colocation identifiers that identify one or more of the plurality of components that cannot be placed along with one or more other components of the group.

5. The method of claim 4, further comprising

transmitting, by the leaf agent to the parent agent, the generated query placement partition.

6. The method of claim 4, wherein the received service request description further specifies at least one affinity or location constraint associated with at least at least one of the plurality of components, wherein the generating of the query placement partition is further based upon the at least one affinity or location constraint, and wherein the at least one solution encoding is generated to satisfy the at least one affinity or location constraint.

7. The method of claim 1, wherein the resource requirements include, for each of the plurality of components, at least one of a processing resource requirement, a memory resource requirement, a storage resource requirement, and a network interface requirement.

8. The method of claim 1, wherein the parent agent is an intermediate agent in the hierarchy, acts as a parent to another leaf agent in the hierarchy, and acts as a child to another agent in the hierarchy.

9. The method of claim 1, wherein the parent agent is executed by a network device, wherein the network device is a switch, router, or bridge.

10. A method executing by a computing device functioning as an intermediate agent and acting as a parent to a plurality of agents in a hierarchy and further acting as a child to a parent agent in the hierarchy, where each of the agents are executed by separate computing devices, the method for enabling decentralized service placement, the method comprising:

receiving, at the intermediate agent from the parent agent, a service request description that specifies resource requirements for a plurality of components of a service to be deployed;

transmitting, by the intermediate agent, the service request description to the plurality of agents acting as children of the intermediate agent in the hierarchy;

receiving, by the intermediate agent from the plurality of agents, a plurality of solution encodings generated by the plurality of agents, wherein each of the plurality of solution encodings indicates an aggregated set of possible placements of at least one of the plurality of components of the service request description that at least one computing devices associated with a corresponding agent or associated with all descendant agents of the corresponding agent can provide while satisfying resource requirements of the at least one of the plurality of components; and

transmitting, by the intermediate agent to the parent agent, a merged solution encoding derived from the plurality of solutions encodings.

11. The method of claim 10, wherein the merged solution encoding is derived by merging, by the intermediate agent, the plurality of solution encodings into one or more solution encodings that indicate another aggregated set of possible placements of some or all of the components of the service request description that one or more computing devices associated with the intermediate agent or associated with all descendant agents of the intermediate agent can provide while satisfying the resource requirements of the some or all of the components.

12. The method of claim 10, wherein the plurality of agents acting as children of the intermediate agent act as intermediate agents in the hierarchy.

13. The method of claim 10, wherein the plurality of agents acting as children of the intermediate agent act as leaf agents in the hierarchy.

14. The method of claim 10, further comprising:

generating, by the intermediate agent, at least one local solution encoding indicating possible placements of at least one the components of the service request description that the computing device executing the intermediate agent can provide at a computing device local to the intermediate agent, while satisfying the resource requirements of the at least one of the plurality of components,

wherein the merged solution encoding is generated by the merging of the plurality of solution encodings and includes merging the generated at least one local solution encoding with the plurality of solution encodings received from the plurality of agents.

15. The method of claim 10, wherein the received service request description further specifies at least one affinity or location constraint associated with at least some of the plurality of components.

16. A method executing by a computing device functioning as a root agent and acting as a parent to a plurality of agents in a hierarchy, where each of the agents are executed by separate computing devices, the method for enabling decentralized service placement, the method comprising:

receiving a service request from a client indicating resource requirements for a service to be deployed including a plurality of components for the service; and

transmitting a service request description based upon the service request to a plurality of intermediate agents of the hierarchy to be distributed to a plurality of leaf agents of the hierarchy;

receiving at least one solution encoding corresponding to the service request description from the plurality of intermediate agents, wherein the at least one solution encoding is generated by at least one intermediate agent in the plurality of intermediate agents and indicates sets of possible placements of at least one of the plurality of components of the service request description that can be provided by a plurality of computing devices associated with the intermediate agent and a plurality of leaf agents that are descendants of the intermediate agent, where the plurality of computing devices satisfy resource requirements of the at least one of the plurality of components of the service, and

determining, based upon the received at least one solution encoding, whether the service request can be placed using the plurality of computing devices.

17. The method of claim 16, wherein the hierarchy includes a plurality of levels of the plurality of intermediate agents.

18. The method of claim 16, wherein a first set of the plurality of leaf agents is associated with a first set of the one or more computing devices at a first data center that is geographically separate from a second data center having a second set of the one or more computing devices associated with a second set of the plurality of leaf agents.

19. The method of claim 16, further comprising:

determining, based upon the received at least one solution encoding, deployment configurations for the service; and

instructing the plurality computing devices to implement the plurality of components of the service requests are able to be placed.

20. The method of claim 16, further comprising:

determining which of the plurality of intermediate agents to which the root agent will transmit the service request description.