Andrei Gudkov

Jiaxi Wu, Pavel Popov, Wenquan Yang et al.

We address the problem of under-utilization of resources in datacenters during cloud operations, specifically focusing on the challenge of online virtual machine (VM) scheduling. Rather than following the traditional approach of scheduling VMs based solely on their static flavors, we take into account their dynamic CPU utilization. We employ $Γ$-robustness theory to manage the dynamic nature and introduce a novel variant of bin packing - Probabilistic k-Bins Packing (PkBP), which theoretically protects the Physical Machines (PMs) from hotspots formation within a specified probability $α$. We develop a scheduling algroithm named CloseRadiusFit and cold-start AI based prediction algorithms for the online version of PkBP. To verify the quality of our approach towards the optimal solutions, we solve the Offline PkBP problem by designing a novel Mixed Integer Linear Programming (MILP) model and a combination of numerical upper and lower bounds. Our experimental results demonstrate that CloseRadiusFit achieves narrow gaps of 1.6% and 3.1% when compared to the lower and upper bounds, respectively.

Andrei Gudkov, Elizaveta Ponomareva, Alexis Pospelov

Increasing demand for computational power has led cloud providers to employ multi-NUMA servers and offer multi-NUMA virtual machines to their customers. However, multi-NUMA VMs introduce additional complexity to scheduling algorithms. Beyond merely selecting a host for a VM, the scheduler has to map virtual NUMA topology onto the physical NUMA topology of the server to ensure optimal VM performance and minimize interference with co-located VMs. Under these constraints, maximizing the number of allocated multi-NUMA VMs on a host becomes a combinatorial optimization problem. In this paper, we derive closed-form expressions to compute the maximum number of VMs for a given flavor that can be additionally allocated onto a physical server. We consider nontrivial scenarios of mapping 2- and 4-NUMA symmetric VMs to 4- and 8-NUMA physical topologies. Our results have broad applicability, ranging from real-time dashboards (displaying available cluster capacity per VM flavor) to optimization tools for large-scale cloud resource reorganization.