Optimization solvers based on methods from constraint programming (OR-Tools, Chufed, Gecode), optimization modulo theory (Z3), and mathematical programming (CPLEX) are successfully applied nowadays to solve many non-trivial examples. However, for solving the problem of automated deployment in the Cloud of component-based applications, their computational requirements are huge making automatic optimization practically impossible with the ..current general optimization techniques. To overcome the dificulty, we exploited the sweet spots of the underlying problem in order to identify search space reduction methods. We came up with 15 symmetry breaking strategies which we tested in a static symmetry breaking setting on the solvers enumerated above and on 4 classes of problems. As a result, all symmetry breaking strategies led to significant improvement of the computational time of all solvers, most notably, Z3 performed the best compared to the others. As an observation, the symmetry breaking strategies confirmed that, when applied in a static setting, they may interact badly with the underlying techniques implemented by the solvers.
The problem of automated deployment in the Cloud of component-based applications received
attention due to increased demand of digitalization of businesses. It consists of the following
steps: (1) selection of the computing resources, (2) the distribution/assignment of the application
components over the available computing resources, and (3) its dynamic modification to cope
with peaks of user requests. In paper [
The contributions of [
This paper extends [
Gecode [
The rest of the paper is organized as follows. Section 2 briefly introduces the problem and the particularities of each formalization. Section 3 shows the need for strategies to reduce the search space and, to this aim, introduces symmetry breaking techniques as well as the principles to combine them. Conclusions of the experimental analysis are presented in Section 4.
Problem Definition The description of the problem first appeared in [
The structural constraints are application-specific and derived in accordance with the analysis of the case studies. These are: • Conflict: components in conflict cannot be deployed on the same VM. • Co-location: components in co-location must be deployed on the same VM. • Exclusive deployment: Only one of the components in exclusive deployment must be deployed in the same deployment plan. • Require-Provide: one component requires or provides some functionalities ofered, respectively provides, of another. Such an interaction induces constraints on the number of instances corresponding to the interacting components as follows. • Full deployment: components in this relationship must be deployed on all VMs leased, except those which would induce conflicts between components. • Deployment with bounded number of instances occur when the number of instances of deployed components must be equal, greater or less than some values.
General constraints are always considered in the formalization and are related to the: (i) basic allocation rules, (ii) occupancy criteria, (iii) hardware capacity of the VM ofers, and (iv) link between the VM ofers and the components hardware/software requirements.
We stated the problems as a linear constraint optimization problem (COP). We redirect the
reader to [
Problem Formalization The formalization for all three types of solvers, that is constraint programming solvers, SMT solvers, and mathematical programming solver, has almost a oneto-one correspondence between linear constraints present in the definition of COP and the implementation. We did not apply optimizations exploiting the particularities of the modelling languages because we wanted to have a fair comparison of the diferent formalisms. However, in the future work we plan to take advantage of their sweet spots.
Minizinc models The Minizinc models are the ones newly introduced in this paper. They are organized as follows: (i) there are surrogate models for each problem in which the maximum number of needed VMs is computed; (ii) there is a model gathering together all constraints, both general and application specific (the model corresponding to each application instantiates the constraints needed for its modeling) (iii) there is a model gathering together all symmetry breakers developed which are then instantiated based on the tests which want to be performed.
The principles of the experimental analysis were introduced in [
We consider four case studies (Secure Web Container, Secure Billing Email Service, Oryx2,
and Wordpress) which exhibit: (i) diferent hardware characteristics of components and the
rich interactions type in between (structural constraints); (ii) the kind of linear constraints used
to formalize the problem; and (iii) the kind of solution we are searching for. A full description
of these case studies is in [
The scalability and efectiveness are evaluated from two perspectives: number of VM ofers, respectively number of deployed instances of components. For Secure Web Container, Secure Billing Email and Oryx2 applications, we considered up to 500 VM ofers. Additionally, for the Wordpress application, we considered up to 12 instances of the Wordpress component to be deployed. The set of ofers was crawled from the Amazon CPs ofers list.
Aiming to reduce the search space size, a set of strategies have been selected in order to exploit the particularities of the problem: (i) the VMs needed for application deployment might have diferent characteristics; (ii) applications components might be in conflict hence conflict-type constraints can be exploited; (iii) the number of instances to be deployed is unknown.
Our approach is incremental and experimental: we start with traditional symmetry breakers that have been used for other problems related to bin-packing and combine them with the aim of further search space reduction.
∑︀=1 (+1), = 1, − 1.
Price-based ordering (PR). This strategy aims to break symmetry by ordering the vector containing the types of used VMs decreasingly by price, i.e. ≥ +1, = 1, − 1. This means that the solution will be characterized by the fact that the columns of the assignment matrix will be ordered decreasingly by the price of the corresponding VMs. Lexicographic ordering (LX). This corresponds to the traditional strategy aiming to break column-wise symmetries. The constraints to be added aiming to ensure that two columns, − 1 and ( + 1) are in a decreasing lexicographic order, i.e. * ≻ * (+1), are ⋀︀ ( = =1 (+1)) =⇒ ≥
(+1), ∀ = 1, .
Load-based ordering (L). This is a column-wise symmetry breaker which orders decreasingly the columns by the number of the component instances they accommodate: ∑︀ =1 ≥ Fixed values (FV). The search space can be reduced also by fixing the values of some variables starting from the application specific constraints, in particular conflict constrains. More precisely, the graph composed by the components being in conflict is used to identify components which must be placed on diferent machines and hence the values of the corresponding decision variables are fixed. The identification of these components is done by constructing the clique with maximum deployment size. 3.1.1.2. Composed symmetry breakers The symmetry breakers above can be composed leading to the following symmetry breakers: • FV-PR, FV-L, FV-LX, PR-L, PR-LX, L-PR, L-LX, • FV-PR-L, FV-PR-LX, FV-L-PR, FV-L-LX, PR-L-LX, L-PR-LX, • FV-PR-L-LX, FV-L-PR-LX These symmetry breakers are so the subsequent breaks ties of the former. For example, FV-PR ifxes on separate machines the decision variables corresponding to the component instances being in the clique with maximum deployment size and the machines left unoccupied are ordered decreasingly by price. In the case of PR-L-LX, the machines are ordered decreasingly by price, those with the same price are ordered decreasingly by the number of components they host and those with the same number of instances are ordered lexicographically.
It is worth noticing that the symmetry breakers involving FV must apply FV the very first. This is because FV is used as a preprocessing step which has a positive impact on the solvers as it introduces equalities.
We used Minizinc v0.7.0 as the constraint modeling language. We mention that the Minizinc models follow the formalization and no optimizations were performed because we wanted to be as close as possible to the OMT and CPLEX formalizations in order to have a fair computational comparison between the newly considered solvers and the existing results. The CP solvers used (Chufed, Gecode, OR-Tools) are called from Minizinc IDE with the default values for parameters. The OMT formalization is done using the Z3 Python API and uses quantifier-free linear integer arithmetic. Z3 was used with the default values of the parameters. In the case of the mathematical programming solver CPLEX, we used the Python API with the no symmetry breaking option manually activated.
The source code and the experimental results are available online at https://github.com/ BogdanD02/Cloud-Resource-Provisioning, release v1.0.0. All reported timings are in seconds. They only include the actual solving time of the optimization problem and not the pre-processing steps.
All tests in this paper were performed on an Intel(R) Core (TM) i5-9400F CPU @ 3.90GHz using Chufed v0.10.4, Gecode v6.3.0, OR-Tools v9.0.0, CPLEX v12.9.0 and Z3 v4.10.2.
We conducted various tests involving 5 solvers and 15 symmetry breakers. Because of lack of space, we can not include all of them here and we direct the reader to check them in the folder PlotData from release v1.0.0 at https://github.com/BogdanD02/ Cloud-Resource-Provisioning.
We draw the following remarks: 1. Using the 15 symmetry breakers, out of the 5 solvers, the best one from the computational time point of view is Z3.
2. For the virtual best solver, that is Z3, the best symmetry breaker is FVPR. This is because we have many Wordpress files to be analyzed ( 40 files corresponding to Wordpress with 3 up to 12 instances and 20, 40, 250, 500 ofers), compared to the other applications ( 4 ifles corresponding to 20, 40, 250, 500 ofers for each of the other applications) for which reduction methods which exploit the graph representation, that is FV, is of benefit. 3. We also considered the best symmetry breaker for Z3 for each of the case studies. In case of Secure Web Container and Secure Billing Email Service applications the best is FVL, while for Oryx2 is FVLX. There is no surprise that symmetry breakers involving FV give best results, however for more reliable results we should consider more test cases for Secure Billing, Secure Web and Oryx2, since now there are only 4 files analyzed corresponding to diferent number of ofers. We plan to run more tests for each of the case studies for a more accurate analysis. 4. One would expect that the best symmetry breaker is one composing a higher number of individual symmetry breakers as more symmetries are broken so the search space is significantly reduced. However, this is not true: FVPR, composing 2 symmetry breakers, is better than those composing 3 or 4. An explanation for this is, on one hand the number of added constraints which influence the solving time, on the other hand, when using static symmetry breaking, the symmetry breakers can interact badly with the SMT solvers which we used as black box. [6] de Moura, L., Bjørner, N.: Z3: An Eficient SMT Solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 337–340.
Springer Berlin Heidelberg, Berlin, Heidelberg (2008) [7] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: Minizinc: Towards a standard CP modelling language. In: Bessiere, C. (ed.) Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4741, pp. 529–543. Springer (2007) [8] Perron, L., Furnon, V.: OR-Tools, https://developers.google.com/optimization/