Placement Throughput Bottleneck Mitigation in Virtual Machines Scheduling

Efficient utilization of cloud resources is a fundamental optimization problem studied in academia and industry alike. In this problem, the user wishes to deploy an application composed of virtual machines or containers. Upon such user request, a network orchestrator typically performs some computation on the available resources and decides how to best satisfy the request. In Network Function Virtualization environments, the orchestrator must decide upon such request in a timely manner to allow network functionalities to react to the network state. Unfortunately, existing scheduling algorithms used by the orchestrators may be too slow to react. In this paper, we evaluate Openstack's Nova scheduler and demonstrate that acquiring the system's state is a performance bottleneck. We then show that the use of a periodically updating state cache can mitigate the performance problem at the expense of a higher than normal placement failures. We then design an algorithm for dynamically changing the cache refresh interval. We evaluate our algorithm on real workloads and show that it attains similar accuracy to traditional algorithms while also achieving an up to 4x throughput increase.