Abstract
Software as a Service (SaaS) allows companies and individuals to use software, hosted and managed by a SaaS provider, on a pay-per-use basis instead of paying for the entire upfront cost. SaaS providers can lease their computing infrastructure to instantiate VMs that run their software services from Infrastructure as a Service (IaaS) providers on a pay per use basis. SaaS customers can subscribe to and unsubscribe from a software service at anytime. Thus, the SaaS cloud provider should dynamically determine the number of needed VMs to run software services as a function of the demand in a way that minimizes the SaaS cost of using VMs from an IaaS but at the same time guaranteeing an agreed upon Quality of Service (QoS) to the SaaS customers. This paper presents a heuristic technique based on hill-climbing that can be used by SaaS providers to determine the type and quantity of VMs to be leased in order to best satisfy customer demands for sofware services. The hill-climbing approach yields a near optimal solution within 2% of the minimum cost in most cases by visiting around 10-4 of the search space.