Investigating the Impact of Biasing on the Quality of Optimized Application Placement in the Cloud

We consider a cloud environment, consisting of physical entities, subjected to user application requests, consisting of logical entities with relationship constraints among them, such as location constraints. We are concerned with the application placement problem, which is a mapping of logical to physical entities that satisfies the constraints and optimizes an objective function, which combines system and user performance. The typical problem size, nature of relationship constraints, complexity and adaptability requirement of the objective function, as well as solution timing budget make traditional techniques for solving this combinatorial optimization problem infeasible.

In this paper we describe an efficient technique that is based on random search methods and uses biased statistical sampling methods. In particular, the proposed technique utilizes (1) importance sampling as a mechanism for characterizing the optimal solution through marginal distributions, (2) independent sampling via a modified Gibbs sampler with intra-sample dependency, and (3) a jumping distribution that uses conditionals derived from the relationship constraints given in the user request and cloud system topology, and the importance sampling marginal distributions as posterior distributions. We demonstrate the feasibility of our methodology using several large-size simulation experiments. We note that the magnitude of biasing has an important impact on the quality of placement. Thus, we investigate the tradeoff between biasing and optimality of placement solutions.