Systems and methods for distributed network-aware service placement

Patent metadata

Field	Value
Publication number	US-9794370-B2
Application number	US-201514936469-A
Country	US
Kind code	B2
Filing date	Nov 9, 2015
Priority date	Nov 9, 2015
Publication date	Oct 17, 2017
Grant date	Oct 17, 2017

Abstract

Exemplary methods for distributed multi-component network-aware service placement in a resource pool include utilizing a hierarchy of agents associated with computing resources of a cloud architecture. An agent in the hierarchy can merge solution encodings to find cover sets indicating feasible placement solutions that can cover an entire application placement request. The agent can partition the components across its children nodes such that global network traffic is minimized. An application graph is generated with components as vertices and edges indicating connections between the components and having associated weights indicating a data transfer rate between the components. The edges can be sorted, and each cover set can be processed by repeatedly assigning unassigned pairs of components having higher data transfer rates to a common assignment set. If multiple placement solutions are found, determined placement costs for each can be used to identify the preferred placement.

First claim

What is claimed is:

1. A method in a root agent for network-aware decentralized service placement, wherein the root agent executes at an electronic device and acts as a parent to a 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, the method comprising:
receiving, at the root agent, 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, by the root agent 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, by the root agent 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 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, by the root agent 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.

2. The method of claim 1 , further comprising:
prior to the receiving of the plurality of sets of solution encodings, transmitting a service request description to each of the plurality of intermediate agents, wherein the service request description specifies the requirements for the plurality of components,
wherein the plurality of sets of solution encodings are received from the plurality of intermediate agents.

3. The method of claim 1 , wherein the partitioning includes:
generating, by the root agent, an application graph including a plurality of vertices corresponding to the plurality of components of the application and a plurality of edges connecting pairs of the plurality of vertices, wherein each of the plurality of edges is associated with a data transfer amount expected to be transmitted between the pair of components connected by the edge.

4. The method of claim 3 , wherein the partitioning further includes:
generating a sorted list of edges including all of the plurality of edges that is sorted according to the data transfer amounts of the plurality of edges.

5. The method of claim 4 , wherein the partitioning further includes:
for each of the one or more cover sets,
when one or more of the plurality of components are determined to have an inflexible placement location based upon the cover set, placing the one or more components into the plurality of assignment sets based upon the inflexible placement locations, and
iteratively processing one or more edges of the sorted list of edges to assign one or more of the plurality of components to the assignment sets until all of the sorted list of edges have been processed or until all of the components have been placed into the plurality of assignment sets.

6. The method of claim 1 , wherein the one or more candidate placement solutions comprise a plurality of candidate placement solutions, and wherein the method further comprises:
determining a plurality of cost values corresponding to the plurality of candidate placement solutions, wherein each of the plurality of cost values is determined based upon an anticipated amount of network traffic resulting between the electronic devices associated with the plurality of intermediate agents that would result from the corresponding candidate placement solution being selected; and
determining the selected one of the plurality of candidate placement solutions based upon the determined plurality of cost values.

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

8. The method of claim 7 , wherein the another agent comprises a root agent in the hierarchy.

9. The method of claim 7 , wherein the another agent comprises another intermediate agent in the hierarchy.

10. The method of claim 7 , wherein the requirements include at least one affinity or location constraint associated with one or more of the plurality of components.

11. The method of claim 7 , wherein:
the one or more components includes a plurality of components; and
the partitioning includes generating an application graph including a plurality of vertices corresponding to the plurality of components and a plurality of edges connecting pairs of the plurality of vertices, wherein each of the plurality of edges is associated with a data transfer amount expected to be transmitted between the pair of components connected by the edge.

12. The method of claim 11 , wherein the partitioning further includes:
generating a sorted list of edges including all of the plurality of edges, wherein the sorted list of edges is sorted according to the data transfer amounts of the plurality of edges.

13. The method of claim 12 , wherein the partitioning further includes:
for each of the one or m

Assignees

• Ericsson Telefon Ab L M
• ERICSSON TELEFON AB L M (publ)

Inventors

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

Classifications

• H04L47/70

  Admission control; Resource allocation · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L67/32 Primary

  Electricity · mapped topic

• H04L67/60

  Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources (admission control or resource allocation H04L47/70) · CPC title