SLA-aware Placement of Multi-Virtual Machine Elastic Services in Compute Clouds

Elastic services comprise multiple virtualized resources that can be added and deleted on demand to match variability in the workload. Service owner profiles the service to determine its most appropriate sizing under different workload conditions. This variable sizing is formalized through service level agreement (SLA) between the service owner and cloud provider. Cloud provider obtains maximum benefit when it succeeds to fully allocate the resource set demanded by the elastic service subject to its SLA. Failure to do so may result in SLA breach and financial losses to the provider. We define a novel combinatorial optimization problem called elastic services placement problem (ESPP) to maximize the provider’s benefit from SLA compliant placement. We observe that ESPP extends the generalized assignment problem (GAP), which is a well studied combinatorial optimization problem. However, ESPP turns out to be considerably harder to solve as it does not admit a constant factor approximation. We show that using simple transformation, ESPP can be presented as a multi-unit combinatorial auction. We further present a column generation method to obtain near optimal solutions for ESPP for large data centers where exact solutions cannot be obtained in a reasonable amount of time using a direct integer programming formulation. We demonstrate the feasibility of our approach through an extensive simulation study. Our results show that we are capable of consistently obtaining good solutions in a time efficient manner. Moreover, if one is willing to trade precision to gain in computation time, our method allows to explicitly manage this tradeoff.

By: David Breitgand; Amir Epstein

Published in: H-0287 in 2010


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 .