Correlation-Aware Heuristic Search for Intelligent Virtual Machine Provisioning in Cloud Systems


  • Chuan Luo Microsoft Research, China
  • Bo Qiao Microsoft Research, China
  • Wenqian Xing Microsoft Research, China Microsoft 365, United States
  • Xin Chen Microsoft Research, China Microsoft 365, United States
  • Pu Zhao Microsoft Research, China
  • Chao Du Microsoft Research, China
  • Randolph Yao Microsoft Azure, United States
  • Hongyu Zhang The University of Newcastle, Australia
  • Wei Wu L3S Research Center, Leibniz University Hannover, Germany
  • Shaowei Cai State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China
  • Bing He Microsoft Research, China
  • Saravanakumar Rajmohan Microsoft 365, United States
  • Qingwei Lin Microsoft Research, China



Heuristic Search, Applications, Cloud


The optimization of resource is crucial for the operation of public cloud systems such as Microsoft Azure, as well as servers dedicated to the workloads of large customers such as Microsoft 365. Those optimization tasks often need to take unknown parameters into consideration and can be formulated as Prediction+Optimization problems. This paper proposes a new Prediction+Optimization method named Correlation-Aware Heuristic Search (CAHS) that is capable of accounting for the uncertainty in unknown parameters and delivering effective solutions to difficult optimization problems. We apply this method to solving the predictive virtual machine (VM) provisioning (PreVMP) problem, where the VM provisioning plans are optimized based on the predicted demands of different VM types, to ensure rapid provisions upon customers' requests and to pursue high resource utilization. Unlike the current state-of-the-art PreVMP approaches that assume independence among the demands for different VM types, CAHS incorporates demand correlation when conducting prediction and optimization in a novel and effective way. Our experiments on two public benchmarks and one industrial benchmark demonstrate that CAHS can achieve better performance than its nine state-of-the-art competitors. CAHS has been successfully deployed in Microsoft Azure and significantly improved its performance. The main ideas of CAHS have also been leveraged to improve the efficiency and the reliability of the cloud services provided by Microsoft 365.




How to Cite

Luo, C., Qiao, B., Xing, W., Chen, X., Zhao, P., Du, C., Yao, R., Zhang, H., Wu, W., Cai, S., He, B., Rajmohan, S., & Lin, Q. (2021). Correlation-Aware Heuristic Search for Intelligent Virtual Machine Provisioning in Cloud Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12363-12372.



AAAI Technical Track on Search and Optimization