Strategy-proof mechanism for time-varying batch virtual machine allocation in clouds

Time-varying resource allocation allows users to define their own unique resource requirement plans during different time periods. This mode of allocation can increase the flexibility of resource usage and reduce resource usage costs for users. Moreover, combining this approach with an auction mechanism can enable resource providers to obtain greater social welfare and benefits; therefore, such resource allocation has become a hot topic in cloud computing. This paper addresses the problem of time-varying batch virtual machine (VM) allocation and pricing in the cloud. Specifically, (1) we propose a novel integer programming model for the time-varying batch VM allocation problem, and (2) we design two truthful auction mechanisms to solve the allocation and pricing problem in a competitive environment. The optimal mechanism includes a dynamic programming (DP)-based resource allocation algorithm and a Vickrey-Clarke-Groves (VCG)-based payment price algorithm. Meanwhile, we also design a greedy mechanism that includes a dominant-resource-based allocation algorithm and a dichotomy-based payment price algorithm. We prove the economic characteristics, including truthfulness and individual rationality, of the above two mechanisms. Furthermore, we prove the approximation ratio of the allocation algorithm in the greedy mechanism. Compared to state-of-the-art research, our approach is characterized by high social welfare, a high served user ratio and a short execution time.

Automated summary

This paper addresses the problem of time-varying batch virtual machine allocation and pricing in the cloud. The authors propose an integer programming model and truthful auction mechanisms, including dynamic programming and VCG algorithm, to solve the problem. In addition, the approximation ratio of the allocation algorithm in the greedy mechanism is also proved.