Selling reserved instances (or virtual machines) is a basic service in cloud computing. In this paper, we consider a more flexible pricing model for instance reservation, in which a customer can propose the time length and number of resources of her request, while in today's industry, customers can only choose from several predefined reservation packages. Under this model, we design randomized mechanisms for customers coming online to optimize social welfare and providers' revenue. We first consider a simple case, where the requests from the customers do not vary too much in terms of both length and value density. We design a randomized mechanism that achieves a competitive ratio @math for both and , which is a improvement as there is usually no revenue guarantee in previous works such as azar2015ec,wang2015selling . This ratio can be improved up to @math when we impose a realistic constraint on the maximum number of resources used by each request. On the hardness side, we show an upper bound @math on competitive ratio for any randomized mechanism. We then extend our mechanism to the general case and achieve a competitive ratio @math for both social welfare and revenue, where @math is the ratio of the maximum request length to the minimum request length and @math is the ratio of the maximum request value density to the minimum request value density. This result outperforms the previous upper bound @math for deterministic mechanisms wang2015selling . We also prove an upper bound @math for any randomized mechanism. All the mechanisms we provide are in a greedy style. They are truthful and easy to be integrated into practical cloud systems.
There are many works that concern online resource allocation for cloud computing @cite_18 @cite_24 @cite_1 @cite_13 @cite_16 @cite_21 . Among these works, the pay-as-you-go model is considered in @cite_13 , and authors in @cite_24 propose a framework for cloud resource allocation when agents' value functions are continuous and concave. In @cite_16 , a more general scheduling problem is studied. The authors also take both social welfare and revenue into consideration. However, the their competitive ratios are related to the total amount of resources. In @cite_21 , the authors propose online strategies to reserve instances without any a priori knowledge of future demands. Those strategies are optimal when considering cost management.
@cite_18 @cite_21 @cite_1 @cite_24 @cite_16 @cite_13
2087111544 2051996845 2125053293 2310680702
Current cloud computing providers allocate their virtual machine (VM) instances via fixed price-based or auction-like mechanisms. However, these mechanisms have one limitation, they are all offline mechanisms, therefore they need to collect information and be invoked periodically. In this paper, we address this limitation by designing an online mechanism for dynamic provisioning and allocation of VM instances in clouds. Our proposed mechanism, MOVMPA, is invoked as soon as a user places a request or some VM instances already allocated become available again. When invoked, the mechanism selects users who would be allocated VM instances for the period they requested for, and ensures that those users will continue using those VMs for the entire period requested. We prove that the mechanism is incentive compatible and also investigate its performance through extensive simulation experiments. Infrastructure-as-a-service (IaaS) clouds offer diverse instance purchasing options. A user can either run instances on demand and pay only for what it uses, or it can prepay to reserve instances for a long period, during which a usage discount is entitled. An important problem facing a user is how these two instance options can be dynamically combined to serve time-varying demands at minimum cost. Existing strategies in the literature, however, require either exact knowledge or the distribution of demands in the long-term future, which significantly limits their use in practice. Unlike existing works, we propose two practical online algorithms , one deterministic and another randomized, that dynamically combine the two instance options online without any knowledge of the future. We show that the proposed deterministic (resp., randomized) algorithm incurs no more than @math (resp., @math ) times the minimum cost obtained by an optimal offline algorithm that knows the exact future a priori , where @math is the entitled discount after reservation. Our online algorithms achieve the best possible competitive ratios in both the deterministic and randomized cases, and can be easily extended to cases when short-term predictions are reliable. Simulations driven by a large volume of real-world traces show that significant cost savings can be achieved with prevalent IaaS prices. Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and resource allocation in cloud computing. This work, to the authors' knowledge, represents the first online combinatorial auction designed in the cloud computing paradigm, which is general and expressive enough to both (a) optimize system efficiency across the temporal domain instead of at an isolated time point, and (b) model dynamic provisioning of heterogeneous Virtual Machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio e+ 1 over e-1 3.30 in social welfare in typical scenarios. The framework consists of three main steps: (1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with an additive loss of 1 over e-1 in competitive ratio, (2) a randomized auction sub-framework that applies primal-dual optimization for translating a centralized co-operative social welfare approximation algorithm into an auction mechanism, retaining a similar approximation ratio while adding truthfulness, and (3) a primal-dual update plus dual fitting algorithm for approximating the one-shot optimization with a ratio λ close to e. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework, as well as its three independent modules, can be instructive in auction design for other related problems. Cloud providers provision their various resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. The users are charged based on a pay-as-you-go model, and their payments should be determined by considering both their incentives and the incentives of the cloud providers. Auction markets can capture such incentives, where users name their own prices for their requested VMs. We design an auction-based online mechanism for VM provisioning, allocation, and pricing in clouds that considers several types of resources. Our proposed online mechanism makes no assumptions about future demand of VMs, which is the case in real cloud settings. The proposed online mechanism is invoked as soon as a user places a request or some of the allocated resources are released and become available. The mechanism allocates VM instances to selected users for the period they are requested for, and ensures that the users will continue using their VM instances for the entire requested period. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. We prove that the mechanism is incentive-compatible, that is, it gives incentives to the users to reveal their actual requests. We investigate the performance of our proposed mechanism through extensive experiments.