Dynamic VM Scaling: Provisioning and Pricing through an Online Auction
Today’s IaaS clouds allow dynamic scaling of VMs allocated to a user, according to real-time demand of the user. There are two types of scaling: horizontal scaling (scale-out) by allocating more VM instances to the user, and vertical scaling (scale-up) by boosting resources of VMs owned by the user. It has been a daunting issue how to efficiently allocate the resources on physical servers to meet the scaling demand of users on the go, which achieves the best server utilization and user utility. An accompanying critical challenge is how to effectively charge the incremental resources, such that the economic benefits of both the cloud provider and cloud users are guaranteed. There has been online auction design dealing with dynamic VM provisioning, where the resource bids are not related to each other, failing to handle VM scaling where later bids may rely on earlier bids of the same user. As the first in the literature, this paper designs an efficient, truthful online auction for resource provisioning and pricing in the practical cases of dynamic VM scaling, where: (i) users bid for customized VMs to use in future durations, and can bid again in the following time to increase resources, indicating both scale-up and scale-out options; (ii) the cloud provider packs the demanded VMs on heterogeneous servers for energy cost minimization on the go. We carefully design resource prices maintained for each type of resource on each server to achieve threshold-based online allocation and charging, as well as a novel competitive analysis technique based on sub-modularity of the offline objective, to show a good competitive ratio is achieved. The efficacy of the online auction is validated through solid theoretical analysis and trace-driven simulations.
A number of online auction mechanisms have been proposed to achieve dynamic cloud resource allocation and pricing. They treat dynamically-arrival user demands as independent bids, ignoring possible connections among bids submitted at different times by a user. In the practical scenarios of VM scaling, a user may bid repeatedly after submitting his initial bid, to increase the resources needed, and hence later bids from the same user are related to earlier bids. With such time-coupling bids, the existing cloud auction mechanisms are not applicable: This system has identified that the offline optimal resource allocation problem, whose solution any online decisions strive to approach, renders a completely different form from those studied in existing online cloud auctions. This brings significant difficulty in online mechanism design to approximate the offline optimum, and calls for new solutions.
• The users bid for future resources with production (server) cost, is to exploit the online primal-dual framework which requires that the corresponding offline optimization problem is convex with linear constraints.
• It identify that the offline optimization problem for VM scaling with time-coupling bids is non-standard, with a submodular objective function and non-linear constraints, such that none of the existing primal-dual frameworks is applicable.
Targeting market-driven, dynamic resource provisioning and pricing for VM scaling, this paper proposes a provenly efficient online auction mechanism. The following practical auction model is investigated: (i) Users bid for tailor-made VMs (with customized bundles of resources) to use in future durations, e.g., based on empirical estimation/prediction of resource needs of their jobs; (ii) a user can bid again in the following time to increase resources, either before or after the start of his VM usage, when he learns better his resource need, and the bid indicates his preferences in scaleup or scale-out; (iii) the cloud provider packs the demanded VMs onto heterogeneous servers on the go, considering scaling preferences of users and striving for energy cost minimization on servers. Our online auction design aims to achieve truthfulness, individual rationality, computational efficiency, and competitiveness in social welfare, i.e., a small ratio between the social welfare of the online mechanism over that of the offline optimum, computed assuming full knowledge over the system span. The well proposed established technique for online auctions, where users bid for future resources with production (server) cost, is to exploit the online primal-dual framework , which requires that the corresponding offline optimization problem is convex with linear constraints. We identify that the offline optimization problem for VM scaling with time-coupling bids is non-standard, with a sub modular objective function and non-linear constraints, such that none of the existing primal-dual frameworks is applicable.
This work designs a truthful and efficient online auction for dynamic resource scaling and pricing, where cloud users repeatedly bid for resources into the future with increased amounts, according to their scale-up/out preferences. We consider server energy cost minimization in social welfare maximization, and reveal an important property, sub modularity, of the objective function in the resulting significantly more challenging offline problem. A novel competitive analysis framework is established for sub modular function optimization with non-linear constraints, demonstrating a good competitive ratio of our online mechanism. The current work focuses on dynamic increase of resources, which is supported in today’s IaaS clouds. On the other hand, resource scale-down and scale-in involve selling resources back to the provider. Designing efficient online mechanisms for a bi-directional market is significantly more challenging, which we seek to investigate in our future work, possibly exploiting double auctions.