Systems and methods for distributed network-aware service placement

A method in an intermediate agent for network-aware decentralized service placement, wherein the intermediate agent executes at an electronic device and acts as a parent to a plurality of leaf agents in a hierarchy of agents and further acts as a child to another agent in the hierarchy, the method comprising:

• receiving, at the intermediate agent from the another agent, a service placement solution indicating one or more of a plurality of components of an application that are to be placed by one or more electronic devices associated with the plurality of leaf agents that have resources available for service placement;
• generating, by the intermediate agent based upon the received service placement solution and further based upon a plurality of solution encodings indicating possible placements of some or all of the plurality of components that the one or more electronic devices can provide while satisfying requirements of the some or all of the plurality of components, one or more cover sets indicating feasible placement solutions that can successfully satisfy the requirements of the one or more components;
• partitioning, by the intermediate agent for each of the one or more cover sets, the one or more components of the application into a plurality of assignment sets corresponding to the plurality of leaf agents while adhering to the feasible placement solutions of the cover set to indicate placements of the one or more components that minimize network traffic between the one or more electronic devices associated with the plurality of agents that would result from the placements to yield one or more candidate placement solutions;
• and
• transmitting, by the intermediate agent to a first leaf agent of the plurality of leaf agents, a service placement solution indicating one or more of the one or more components that is to be placed by the electronic device associated with the first leaf agent according to a selected one of the one or more candidate placement solutions.

A non-transitory computer-readable storage medium having instructions which, when executed by one or more processors of an electronic device, cause the electronic device to implement a root agent act as a parent to plurality of intermediate agents in a hierarchy of agents, wherein each of the plurality of intermediate agents acts as a parent to one or more descendant agents associated with one or more electronic devices having resources available for service placement, wherein the root agent is to perform network-aware decentralized service placement by performing operations comprising:

• receiving a plurality of sets of solution encodings corresponding to the plurality of intermediate agents, wherein each of the plurality of sets of solution encodings indicates possible placements of some or all of a plurality of components of an application that the one or more electronic devices associated with the one or more descendant agents of the intermediate agent can locally provide while satisfying requirements of the some or all of the components;
• generating, based upon the plurality of sets of solution encodings, one or more cover sets indicating feasible placement solutions that can successfully satisfy the requirements of all of the components of the application;
• partitioning, for each of the one or more cover sets, the components of the application into a plurality of assignment sets corresponding to the plurality of intermediate agents while adhering to the feasible placement solutions of the cover set to indicate placements of the plurality of components that minimize network traffic travelling between the electronic devices associated with the plurality of intermediate agents that would result from the placements, to yield one or more candidate placement solutions;
• and
• transmitting, to a first intermediate agent of the plurality of intermediate agents, a service placement solution indicating one or more of the plurality of components that are to be placed by the first intermediate agent according to a selected one of the one or more candidate placement solutions.

A non-transitory computer-readable storage medium having instructions which, when executed by one or more processors of an electronic device, cause the electronic device to implement an intermediate agent to act as a parent to a plurality of leaf agents in a hierarchy and further to act as a child to another agent in the hierarchy to perform network-aware decentralized service placement by performing operations comprising:

• receiving, from the another agent, a service placement solution indicating one or more of a plurality of components of an application that are to be placed by one or more electronic devices associated with the plurality of leaf agents that have resources available for service placement;
• generating, based upon the received service placement solution and further based upon a plurality of solution encodings indicating possible placements of some or all of the plurality of components that the one or more electronic devices can provide while satisfying requirements of the some or all of the plurality of components, one or more cover sets indicating feasible placement solutions that can successfully satisfy the requirements of the one or more components;
• partitioning, for each of the one or more cover sets, the one or more components of the application into a plurality of assignment sets corresponding to the plurality of leaf agents while adhering to the feasible placement solutions of the cover set to indicate placements of the one or more components that minimize network traffic between the one or more electronic devices associated with the plurality of agents that would result from the placements to yield one or more candidate placement solutions;
• and
• transmitting, to a first leaf agent of the plurality of leaf agents, a service placement solution indicating one or more of the one or more components that is to be placed by the electronic device associated with the first leaf agent according to a selected one of the one or more candidate placement solutions.