Systems and methods for decentralized service placement in a resource pool

Patent metadata

Field	Value
Publication number	US-10148771-B2
Application number	US-201815862204-A
Country	US
Kind code	B2
Filing date	Jan 4, 2018
Priority date	Sep 16, 2015
Publication date	Dec 4, 2018
Grant date	Dec 4, 2018

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.

First claim

What is claimed is:

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 in

Assignees

• Ericsson Telefon Ab L M

Inventors

• Yazir Ya{hacek over (g)}iz Onat
• Halén Joacim
• Abbasi Zahra

Classifications

• H04L67/16 Primary

  Electricity · mapped topic

• G06F17/30327

  Physics · mapped topic

• G06F17/30424

  Physics · mapped topic

• H04L47/829

  Topology based · CPC title

• G06F9/5027 Primary

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title