Dynamic vector bin packing for virtual machine placement in cloud

Abstract

Virtual machine placement is a crucial challenge in cloud computing in utilizing physical machine resources in data centers. Virtual Machine placement is formulated as the MinUsageTime Dynamic Vector Bin Packing Problem (DVBP), aiming to minimize the total usage time of the physical machines. This report provides inclusive proof that DVBP is an NP-hard problem. This report also evaluates state-of-the-art algorithms in non-clairvoyant and clairvoyant scenarios, where future information about the items is known. For non-clairvoyant scenarios, algorithms such as First Fit and Next Fit are implemented, and new algorithms such as Resource Max and Round-Robin Next Fit are proposed for replacement. Similarly, clairvoyant scenarios' algorithms like Classify By Departure Time and Hybrid Algorithm are evaluated, and a new algorithm such as Closest Remaining Time is proposed as an alternative. Overall, 22 algorithms are evaluated (9 of which are original to this project). This report provides the pseudocode of the algorithm during the implementation. It optimizes the implementation of the best-fit and worst-fit algorithms by proving the theorem to prune the search space effectively. The evaluation includes theoretical competitiveness analysis and empirical analysis of a simulation of real-life datasets by Microsoft Azure. Theoretically, this report proves that the competitive ratio of any algorithm is bounded by the number of items. Empirically, the insights from the total usage time of the physical machines by various algorithms are discussed through the simulation results.