Method for mapping media components employing machine learning

Patent metadata

Field	Value
Publication number	US-9684706-B2
Application number	US-201314378480-A
Country	US
Kind code	B2
Filing date	Jan 28, 2013
Priority date	Feb 15, 2012
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

The present document relates to cloud computing. In particular, the present document relates to methods and systems for cloud computing which enable the efficient and flexible placement of application components within a cloud. A computing device ( 101 ) is described. The computing device ( 101 ) is adapted to receive a plurality of component placement requests for one or more components ( 703 ) of a corresponding plurality of applications ( 700 ); determine a plurality of feature vectors ( 203 ) from the plurality of component placement requests, respectively; wherein each feature vector ( 203 ) comprises vector dimensions which describe different attributes of the respective component placement request: determine a plurality of placement decisions ( 205 ) regarding the plurality of component placement requests, respectively: wherein each placement decision ( 205 ) comprises an indication of one or more executing computing devices ( 101 ) onto which the one or more components ( 703 ) of the respective application ( 700 ) have been placed; cluster the plurality of feature vectors ( 203 ), thereby yielding one or more clusters ( 202 ); wherein each cluster ( 202 ) comprises a default feature vector ( 203 ) describing the different attributes of a default component placement request; determine a default placement decision ( 205 ) for each of the one or more clusters; and store the one or more default feature vectors and the respective one or more default placement decisions ( 205 ) in a database ( 204 ) of the computing device ( 101 ).

First claim

The invention claimed is:

1. A computing device comprising:
hardware including at least one data processor, wherein said hardware is adapted to:
receive a plurality of component placement requests for one or more components of a corresponding plurality of applications;
determine a plurality of feature vectors from the plurality of component placement requests, respectively; wherein each feature vector comprises vector dimensions which describe different attributes of the respective component placement request;
determine a plurality of placement decisions regarding the plurality of component placement requests, respectively; wherein each placement decision comprises an indication of one or more executing computing devices onto which the one or more components of the respective application have been placed;
cluster the plurality of feature vectors, thereby yielding one or more clusters; wherein each cluster comprises a default feature vector describing the different attributes of a default component placement request;
determine a default placement decision for each of the one or more clusters;
store the one or more default feature vectors and the respective one or more default placement decisions in a database of the computing device;
receive a new component placement request for one or more components of a new application;
determine a new feature vector from the new component placement request; and
determine where to place the one or more components of the new application based on the one or more default feature vectors.

2. The computing device of claim 1 , wherein the clustering is performed using a machine learning algorithm, in particular a support vector machine algorithm.

3. The computing device of claim 1 , wherein the hardware is further adapted to:
determine that a first vector dimension of the plurality of feature vectors has a correlation with the corresponding placement decisions which is smaller than a correlation threshold; and
remove the first vector dimension from the plurality of feature vectors.

4. The computing device of claim 1 , wherein the hardware is further adapted to:
receive control messages from other computing devices; and
determine the plurality of placement decisions based on the received control messages.

5. The computing device of claim 1 , wherein the vector dimensions are indicative of one or more of:
a location of a sink and/or a source of data processed by an application component;
a number of sinks and/or sources processed by an application;
computing resources required by an application component; wherein the computing resources are one or more of: processor resources, memory resources, bandwidth resources;
connection attributes required by an application component; wherein the connection attributes are one or more of: bandwidth, latency, maximum bit error rate; and
a graph structure of the one or more components of an application; wherein the graph structure indicates how the one or more components of the application are interlinked.

6. The computing device of claim 1 , wherein the hardware is further adapted to:
determine a minimum distance of the new feature vector from the one or more default feature vectors; and
if the minimum distance is below a minimum threshold, determine where to place the one or more components of the new application based on the default placement decision corresponding to the default feature vector at the minimum distance from the new feature vector.

7. The computing device of claim 6 , wherein the minimum distance is determined based on a weighted difference of the respective vector dimensions of the new feature vector and the one or more default feature vectors.

8. The computing device of claim 6 , wherein the hardware is further adapted to:
pass the component placement request to an executing computing device indicated within the default placement decision.

9. The computing device of claim 6 , wherein:
the computing device is positioned in a first topological area;
the computing device comprises a topological list indicating a plurality of reference computing devices positioned in a plurality of topological areas other than the first topological area, respectively;
the computing device comprises a local resource list indicating available computing resources of the computing device and of at least one neighbor computing device positioned in a neighborhood of the computing device; and
upon determining that the minimum distance is greater than a minimum threshold, the hardware is further adapted to:
determine, based on the topological list, if the one or more components of the new application are to be placed in the first topological area or in one of the plurality of topological areas other than the first topological area;
if it is determined that the one or more components of the new application are to be placed in one of the plurality of topological areas other than the first topological area, pass the component placement request to the reference computing device of the respective topological area of the plurality of topological areas other than the first topological area; and
if it is determined that the one or more components of the new application are to be placed in the first topological area, identify from the local resource list a selected computing device having the computing resources for executing the one or more components of the new application.

10. The computing device of claim 1 , wherein:
the computing device is a default application server of a point-to-multipoint, a point-to-point or a multipoint-to-multipoint application; and
the default application server is a default point of access in a cloud of a plurality of computing devices for setting up the point-to-multipoint, the point-to-point or the multipoint-to-multipoint application.

11. The computing device of claim 1 , wherein said hardware is further adapted to:
cause the one or more components of the new application to be placed in accordance with the determination made regarding where to place said one or more components of the new application.

12. A method for placing one or more components of a new application onto a computing device of a media cloud, the method comprising:
receiving a plurality of component placement requests for one or more components of a corresponding plurality of applications;
determining a plurality of feature vectors from the plurality of component placement requests, respectively; wherein each feature vector comprises vector dimensions which describe different attributes of the respective component placement request;
determining a plurality of placement decisions regarding the plurality of component placement requests, respectively; wherein each placement decision comprises an indication of one or more executing computing devices onto which the one or more components of the respective application have been placed;
clustering the plurality of feature vectors, thereby yielding one or more clusters; wherein each cluster is represented by a default feature vector describing the different attributes of a respective default component placement request;
determining a default placement decision corresponding to a default feature vector, for each of the one or more clusters;
storing the one or more default feature vectors and the respective one or more default placement decisions in a database of the computing device; and
using the one or more default feature vectors and the respective one or more default placement decisions stored in the database for placing the one or more components of the new application, wherein using comprises:
receiving a new component placemen

Assignees

• Alcatel Lucent

Inventors

• Satzke Klaus
• Wahl Stefan

Classifications

• 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 Primary

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

• G06N99/005

  Physics · mapped topic

• H04L67/327

  Electricity · mapped topic

• G06F17/30598 Primary

  Physics · mapped topic