A relax-and-round optimization algorithm for online NUMA-aware virtual machine placement

The performance of virtual machine (VM) placement algorithm is directly related to the economic profit for the cloud service operator. Due to the high real-time computational demand, the current optimization-based approaches, which require the solution of an integer programming problem, cannot be implemented online for large-scale problems. We present an efficient relax-and-round optimization algorithm to solve this problem. First, we propose a VM placement model whose objective is to maximize the residual resource value of the resource pool so it can reserve resources for unknown future VM demand. Second, we handle the non-uniform memory access (NUMA) structure by the introduction of additional decision variables specifying the NUMA node. Finally, we propose a heuristic relax-and-round algorithm to efficiently solve the integer programming problem with guaranteed constraint satisfaction. The proposed approach is tested on HUAWEI cloud platform. The result shows that the performance of the proposed approach is much better than the current approximate or intelligent optimization approaches (Best-Fit, First-Fit, Deep Reinforcement Learning and etc.), and comparable to the exact approach, but the computational efficiency is much better than the exact approach.