Reducing the upfront cost of private clouds with clairvoyant virtual machine placement

作     者：Zhao, Yan Liu, Hongwei Wang, Yan Zhang, Zhan Zuo, Decheng 

作者机构：Harbin Inst Technol Dept Comp Sci & Technol Harbin Heilongjiang Peoples R China Macquarie Univ Dept Comp Sydney NSW Australia 

出 版 物：《JOURNAL OF SUPERCOMPUTING》 (超高速计算杂志)

年 卷 期：2019年第75卷第1期

页      面：340-369页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National High-tech R&D Program of China (863 Program) [2013AA01A215] National Laboratory of High-effect Server and Storage Techniques [2014HSSA05] 

主　　题：Virtual machine placement Dynamic bin packing Private cloud computing Resource management 

摘      要：Although public clouds still occupy the largest portion of the total cloud infrastructure, private clouds are attracting increasing interest from both industry and academia because of their better security and privacy control. According to the existing studies, the high upfront cost is among the most critical challenges associated with private clouds. To reduce cost and improve performance, virtual machine placement (VMP) methods have been extensively investigated;however, few of these methods have focused on private clouds. This paper proposes a heterogeneous and multidimensional clairvoyant dynamic bin-packing model, in which the scheduler can conduct more efficient VMP processes using additional information on the arrival time and duration of virtual machines to reduce the datacenter scale and thereby decrease the upfront cost of private clouds. In addition, a novel branch-and-bound algorithm with a divide-and-conquer strategy (DCBB) is proposed to effectively and efficiently handle the derived problem. One state-of-the-art and several classic VMP methods are also modified to adapt to the proposed model to observe their performance and compare with our proposed algorithm. Extensive experiments are conducted on both real-world and synthetic workloads to evaluate the accuracy and efficiency of the algorithms. The experimental results demonstrate that DCBB delivers near-optimal solutions with a convergence rate that is much faster than those of the other search-based algorithms evaluated. In particular, DCBB yields the optimal solution for a real-world workload with an execution time that is an order of magnitude shorter than that required by the original branch-and-bound algorithm.