In cloud computing, a cloud provider is faced with the problem of allocating physical resources to an incoming stream of requests for virtual resources in such a way to satisfy requirements and maximize resource usage while providing good performance. Traditionally, when a request is for a virtual machine (VM), the problem of placing it on a particular physical machine (PM) may be expressed as a bin packing or an online, stochastic knapsack problem. The typically large size of such a problem forces one to resort to approximate and heuristics-based optimization techniques. Now, the trend is for a request to involve more than just a single VM. In particular, a request consists of a set of heterogeneous VMs with some interrelationships due to communication needs and other dependability-induced constraints. The placement of such constrained, networked virtual clusters in the physical infrastructure, including compute, storage, and networking resources is much more challenging. Several research avenues are and have been explored to deal with such a problem, albeit mostly in other areas such as mapping task graphs in parallel systems and provisioning of virtual private networks. The sheer size of the cloud incites one to investigate statistical approaches to solving this cloud placement problem.
In this paper, we provide an algorithm for the placement of constrained, networked virtual clusters in the cloud, that is based on importance sampling (also known as cross-entropy). A straightforward implementation of such a technique proves inefficient. We considerably enhance the method by biasing the sampling process to incorporate communication needs and other constraints of requests to yield an efficient algorithm that is linear in the size of the cloud. We investigate the quality of the results of using our algorithm on a simulated cloud, where we study the effects of the various parameters on the solution and performance of the algorithm.
By: Asser N. Tantawi
Published in: RC25248 in 2011
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .