Difference between revisions of "Broker and Matchmaker"

From Gcube Wiki
Jump to: navigation, search
(Broker and Matchmaker)
Line 1: Line 1:
 
==Broker and Matchmaker==
 
==Broker and Matchmaker==
 
The Broker and Matchmaker represents the subsystem promoting and supporting the optimal selection and usage of resources during the VRE deployment phase. In
 
The Broker and Matchmaker represents the subsystem promoting and supporting the optimal selection and usage of resources during the VRE deployment phase. In
particular, it is invoked to select the most appropriate pool of gHNs to be used, among those available in the context of the VRE, during the deployment of the services needed to operate the VRE. Because of this, it interacts with  
+
particular, it is invoked to select the most appropriate pool of gHNs to be used, among those available in the context of the VRE, during the deployment of the services needed to operate the VRE. Because of this, it interacts with:
** the Information System to be aware of the available gHNs as well as of their distinguishing features (e.g. the number of Running Instances currently hosted by it, the RAM the machine is equipped with) and
+
* the Information System to be aware of the available gHNs as well as of their distinguishing features (e.g. the number of Running Instances currently hosted by it, the RAM the machine is equipped with) and
** with the Virtual Organisation Management to act securely and filter out the gHNs that falls out of the operational context of the VRE. From an architectural point of view it mainly consists of a service implementing the matchmaking algorithm.
+
* with the Virtual Organisation Management to act securely and filter out the gHNs that falls out of the operational context of the VRE. From an architectural point of view it mainly consists of a service implementing the matchmaking algorithm.
 +
 
 
== Reference architecture ==
 
== Reference architecture ==
 
The main task of the BM is the selection of the most suitable set of gHNs to deploy a specified set of packages. The matching process, implemented by the BM-Algorithm component, is based on the matchmaking algorithm. The process returns an association between packages to be deployed and gHNs, named
 
The main task of the BM is the selection of the most suitable set of gHNs to deploy a specified set of packages. The matching process, implemented by the BM-Algorithm component, is based on the matchmaking algorithm. The process returns an association between packages to be deployed and gHNs, named

Revision as of 11:38, 9 June 2009

Broker and Matchmaker

The Broker and Matchmaker represents the subsystem promoting and supporting the optimal selection and usage of resources during the VRE deployment phase. In particular, it is invoked to select the most appropriate pool of gHNs to be used, among those available in the context of the VRE, during the deployment of the services needed to operate the VRE. Because of this, it interacts with:

  • the Information System to be aware of the available gHNs as well as of their distinguishing features (e.g. the number of Running Instances currently hosted by it, the RAM the machine is equipped with) and
  • with the Virtual Organisation Management to act securely and filter out the gHNs that falls out of the operational context of the VRE. From an architectural point of view it mainly consists of a service implementing the matchmaking algorithm.

Reference architecture

The main task of the BM is the selection of the most suitable set of gHNs to deploy a specified set of packages. The matching process, implemented by the BM-Algorithm component, is based on the matchmaking algorithm. The process returns an association between packages to be deployed and gHNs, named deployment schema, trying to minimize the number of gHNs used. The deployment schema can then be used by the client (namely, the VREManager) to drive the deployment process.The matching process takes into account the current status of the infrastructure, i.e. the set of services already deployed on gHNs and the current state of the node. This service is able to query the gCube Information Service (IS) to obtain the current deployment status, as well as requirements of packages to be deployed (contained in ServiceProfiles and stored in the IS).

Matching Algorithm

The matchmaking is a variant of a Bin Packing problem, a combinatorial NP-hard problem. In the Bin Packing a set of objects of different size must be packed into a finite number of bins of different capacities minimizing the number of bins used. The relationship between the Bin Packing and the matchmaking problem can be summarized as follow:

  • Input description:
  a. A set of n items with size: d1, d2, ..., dn; corresponding to packages to be deployed
  b. A set of m bins with capacity: c1, c2, ...,cm; corresponding to available GHNs with their features and current status 
  • Problem description:
  c. Store all the items using the smallest number of bins (i.e. GHNs)

Since the Bin Packing problem is NP-hard, the optimal solution will requires exponential time to be found. A most efficient approach uses heuristics to find a sub-optimal solution in polynomial time. Analytical and empirical evaluations suggest that the best heuristic for this problem is the First-Fit Decreasing algorithm. The algorithm is organized in the following steps:

  • Sort objects in decreasing order of size, from the biggest to the smallest
  • Insert each object one by one into the first bin (e.g. GHN) that has room for it. If no bin has room for it, we must start another bin


First-fit decreasing can be implemented in O(n*logn + b*n) time, where b<=min(m,n) is the number of bins actually used, by doing a linear sweep through the bins on each insertion. If compared to the standard Bin Packing problem, the matchmaking algorithm has a number of additional constraints. First of all each package (item) has a set of requirements on the GHN hosting it. These requirements are of different types:

  • Property requirements (e.g. OS type == Linux)
  • Capacity requirements (e.g. CPU speed > 500MHz)
  • Consumption requirements (e.g. disk space > 30MB)
  • Software requirements (e.g. libX v2.4 has to be already installed)

Moreover, two types of dependency among couples of packages to be deployed can be specified. Supported types for relations among packages are:

  • uses – this type of dependency implies that, after deployment, involved packages will establish some kind of interaction.

Although it is desirable to minimize network communication, the fulfilment of this constraint is not to be considered mandatory for a proposed deployment solution.

    • same-host – this type of dependency implies that the two involved packages have to be deployed on the same GHN. Dependencies of this type are mandatory; a violation would lead to a faulty deployment scheme.

These dependencies and requirements can be defined in profiles of services and further refined in a matching request. Finally, in each request is also possible to define a list of favourite gHNs where to deploy the item defined previously. The deployment schema resulting from the matchmaking process must take into account these requirements and dependencies and ensure that:

    • For each package, its requirements are satisfied by the identified GHN;
    • Each GHN satisfies the aggregation of consumption requirements of software being hosted (e.g. the sum of disk space used by packages being installed on a GHN must not exceed the current available disk space for that GHN);
    • As required by the ‘same-host’ constraints, packages are deployed on the same hosts;
    • Minimize the number of GHN hosting packages bound by a ‘uses’ constraint.