Generating Heuristic Policies from Optimization in Large Scale Cloud Computing VM scheduling
Yuexian Zhang, Jianchen Hu, Xunhang Sun, Qiaozhu Zhai, Lei Zhu, Su Li, Wenli Zhou, Fangzhu Ming, Xiaoyu Cao, Feng Gao · 2023
The VM placement problem has emerged as a critical challenge in cloud resource scheduling. This type of problem, often formulated as a vector bin packing problem, is known to be NP-hard. For practical large-scale problems, the optimization-based algorithm fails to promptly accommodate on-demand user requests, while the heuristic algorithms face the scalability issues. To tackle the online VM placement problem, this paper shows a VM placement model considering NUMA architecture and presents an algorithm that converts optimal fine-grained solutions into coarse-grained placement policies so that the online implementation is simply the heuristic placement policies. The placement policies, which are generated from the offline optimal solutions of the past few time-steps, are refreshed (time- or event-triggered) every few steps. Our experiments demonstrate that the algorithm we proposed can balance the quality of the solution with execution time compared to BestFit and FirstFit in large scale cloud computing backgrounds.