A Probabilistic Framework and Statistical Sampling Approach to Optimized Placement in the Cloud

We consider a cloud system environment, consisting of physical entities, subjected to user requests, consisting of virtual entities with relationship constraints among them, such as location constraints. In this case, the resource allocation problem is a mapping of virtual to physical entities which 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 outline an efficient technique that is based on random search methods and uses a probabilistic framework and statistical sampling methods. In particular, the proposed technique utilizes (1) importance sampling as a mechanism for describing 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.