Matchmaking Algorithm Sample Clauses

Matchmaking Algorithm. The matchmaking is a variant of a Bin Packing problem [41], a combinatorial NP-hard5 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 (e.g. cpu, storage, deployed services) • 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 5 Nondeterministic Polynomial-time hard. 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 d...