Heterogeneous and Multidimensional Clairvoyant Dynamic Bin Packing for Virtual Machine Placement.

Although the public cloud still occupies the largest portion of the total cloud infrastructure, the private cloud is attracting increasing interest because of its better security and privacy control. According to previous research, a high upfront cost is among the most serious challenges associated with private cloud computing. Virtual machine placement (VMP) is a critical operation for cloud computing, as it improves performance and reduces cost. Extensive VMP methods have been researched, but few have been designed to reduce the upfront cost of private clouds. To fill this gap, in this paper, a heterogeneous and multidimensional clairvoyant dynamic bin packing (CDBP) model, in which the scheduler can conduct more efficient scheduling with additional time information to reduce the size of the datacenter and, thereby, decrease the upfront cost, is applied. An innovative branch-and-bound algorithm with the divide-and-conquer strategy (DCBB) is proposed to reduce the number of servers (#servers), with fast processing speed. In addition, some algorithms based on first fit (FF) and the ant colony system (ACS) are modified to apply them to the CDBP model. Experiments are conducted on generated and real-world data to check the performance and efficiency of the algorithms. The results confirm that the DCBB can make a tradeoff between performance and efficiency and also achieves a much faster convergence speed than that of other search-based algorithms. Furthermore, the DCBB yields the optimal solution under real-world workloads in much less runtime (by an order of magnitude) than required by the original branch-and-bound (BB) algorithm.