SYSTEMS AND METHODS FOR DECENTRALIZED SERVICE PLACEMENT IN A RESOURCE POOL

• US 20170078409A1
• Filed: 09/16/2015
• Published: 03/16/2017
• Est. Priority Date: 09/16/2015
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: YAZIR, Yagiz Onat, Abbasi, Zahra, HALN, Joacim
• Granted Patent: US 9,894,165 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 a leaf agent executing at a computing device and acting as a child to a parent agent in a hierarchy of agents for enabling decentralized service placement, 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, 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;

generating, based upon the query placement partition and a set of resources available at one or more computing devices associated with the leaf agent, one or more solution encodings indicating possible placements of some or all of the components of the service request description that the one or more computing devices can locally provide while satisfying the resource requirements of the some or all of the components; and

transmitting, by the leaf agent to the parent agent, the one or more solution encodings.

2. The method of claim 1, wherein generating the one or more solution encodings comprises:

generating, based upon the plurality of groups identified by the query placement partition, one or more affinity-based encodings, wherein each of the one or more affinity-based encodings indicates a maximal number of components from each of the plurality of groups that could potentially be provided by the one or more computing devices.

3. The method of claim 2, wherein generating the one or more solution encodings further comprises:

generating, based upon the one or more affinity-based encodings and a description of available local resources of the one or more computing devices, one or more refined encodings, wherein each of the one or more refined encodings is derived from one of the one or more affinity-based encodings and indicates numbers of the components of the corresponding affinity-based encoding that the one or more computing devices can actually provide given the available local resources.

4. The method of claim 1, wherein the resource requirements include, for each of the plurality of components, one or more of:

a processing resource requirement;

a memory resource requirement;

a storage resource requirement; and

a network interface requirement.

5. The method of claim 1, 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.

6. The method of claim 1, further comprising

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

7. 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.

8. 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.

9. The method of claim 1, 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;

the generating of the query placement partition is further based upon the at least one affinity or location constraint; and

the one or more solution encodings are generated to satisfy the at least one affinity or location constraint.

10. A method in an intermediate agent executing at an electronic device and acting as a parent to a plurality of agents in a hierarchy and further acting as a child to another agent in the hierarchy, the method for enabling decentralized service placement, the method comprising:

receiving, at the intermediate agent from the another 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 some or all of the components of the service request description that one or more computing devices associated with the corresponding agent or associated with all descendant agents of the corresponding agent can provide while satisfying the resource requirements of the some or all of the components;

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; and

transmitting, by the intermediate agent, the one or more merged solution encodings to the another agent acting as a parent to the intermediate agent.

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

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

13. The method of claim 10, further comprising:

generating, by the intermediate agent, one or more local solution encodings indicating possible placements of some or all of the components of the service request description that the electronic device executing the intermediate agent can locally provide while satisfying the resource requirements of the some or all of the components,

wherein the merging of the plurality of solution encodings into the one or more solution encodings also includes merging the generated one or more local solution encodings with the plurality of solution encodings received from the plurality of agents.

14. The method of claim 10, wherein the another agent acts as a root agent in the hierarchy.

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 system providing decentralized service placement, comprising:

a plurality of agents executing at one or more electronic devices and that are configured in a hierarchy, including;

a root agent acting as a root of the hierarchy, wherein the root agent is configured to;

receive service requests from clients indicating resource requirements for services to be deployed including pluralities of components,

transmit service request descriptions based upon the service requests to a plurality of intermediate agents of the hierarchy to be distributed to a plurality of leaf agents of the hierarchy,

receive solution encodings corresponding to the service request descriptions from the plurality of intermediate agents, wherein the solution encodings are generated by the plurality of intermediate agents and indicate sets of possible placements of some or all of the components of each of the service request descriptions that can be provided by a plurality of computing devices associated with the plurality of leaf agents that satisfy resource requirements of the some or all of the components, and

determine, based upon the received solution encodings, whether the service requests can be placed using the plurality of computing devices;

the plurality of intermediate agents, wherein each of the intermediate agents is configured to;

receive the transmitted service request descriptions transmitted from the root agent or another of the plurality of intermediate agents,

transmit the received service request descriptions to one or more other intermediate agents or one or more of the plurality of leaf agents,

receive solution encodings corresponding to the service request descriptions from the one or more other intermediate agents or the one or more of the plurality of leaf agents,

merge the received solution encodings, and

transmit the merged solution encodings to the root agent or to the another of the plurality of intermediate agents; and

the plurality of leaf agents, wherein each of the plurality of leaf agents is configured to;

receive, from one of the plurality of intermediate agents, the service request descriptions,

generate query placement partitions for the service request descriptions, wherein each query placement partition identifies a plurality of groups of a plurality of components specified in the service request description, wherein the plurality of groups include at least one colocation group and at least one non-colocation group,

generate solution encodings based upon the generated query placement partitions and a set of resources available at one or more computing devices associated with the leaf agent, wherein each of the solution encodings indicates possible placements of some or all of the components of the corresponding service request description that the one or more computing devices can locally provide while satisfying the resource requirements of the some or all of the components, and

transmit, to the one of the plurality of intermediate agents, the solution encodings.

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

18. The system 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 system of claim 16, wherein the root agent is further configured to:

determine, based upon the received solution encodings, deployment configurations for the service requests that are determined as able to be placed; and

cause ones of the one or more computing devices to implement the some or all of the components of the service requests that are determined as able to be placed.

20. The system of claim 16, wherein the root agent is further configured to:

determine, based upon the received service requests, which of the plurality of intermediate agents to which the root agent will transmit the service request descriptions.

21. The system of claim 16, wherein the root agent is configured to transmit the service request descriptions to all of the plurality of intermediate agents of the hierarchy that act as children of the root agent in the hierarchy.

22. The system of claim 16, wherein at least some of the plurality of intermediate agents are executed by a plurality of network devices, wherein each network device comprises a switch device or a router device, and wherein at least some of the plurality of leaf agents are executed by server computing devices.

23. The system of claim 16, wherein:

one or more of the service requests received by the root agent specify at least one affinity or location constraint associated with at least some of the plurality of components of the corresponding service request; and

each of the plurality of leaf agents generate the solution encodings, for those of the service requests that specify at least one affinity or location constraint, such that the corresponding solution encoding satisfies the at least one affinity or location constraint.