Kerveros: Efficient and Scalable Cloud Admission Control


Sultan Mahmud Sajal, Microsoft Research and Pennsylvania State University; Luke Marshall and Beibin Li, Microsoft Research; Shandan Zhou and Abhisek Pan, Microsoft Azure; Konstantina Mellou and Deepak Narayanan, Microsoft Research; Timothy Zhu, Pennsylvania State University; David Dion and Thomas Moscibroda, Microsoft Azure; Ishai Menache, Microsoft Research


The infinite capacity of cloud computing is an illusion: in reality, cloud providers cannot always have enough capacity of the right type, in the right place, at the right time to meet all demand. Consequently, cloud providers need to implement admission-control policies to ensure accepted capacity requests experience high availability. However, admission control in the public cloud is hard due to dynamic changes in both supply and demand: hardware might become unavailable, and actual VM consumption could vary for a variety of reasons including tenant scale-outs and fulfillment of VM reservations made by customers ahead of time. In this paper, we design and implement Kerveros, a flexible admission-control system that has three desired properties: i) high computational scalability to handle a large inventory, ii) accurate capacity provisioning for high VM availability, and iii) good packing efficiency to optimize resource usage. To achieve this, Kerveros uses novel bookkeeping techniques to quickly estimate the capacity available for incoming VM requests. Our system has been deployed in Microsoft Azure. Results from both simulations and production confirm that Kerveros achieves more than four nines of availability while sustaining request processing latencies of a few milliseconds.

OSDI '23 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {288610,
author = {Sultan Mahmud Sajal and Luke Marshall and Beibin Li and Shandan Zhou and Abhisek Pan and Konstantina Mellou and Deepak Narayanan and Timothy Zhu and David Dion and Thomas Moscibroda and Ishai Menache},
title = {Kerveros: Efficient and Scalable Cloud Admission Control},
booktitle = {17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)},
year = {2023},
isbn = {978-1-939133-34-2},
address = {Boston, MA},
pages = {227--245},
url = {},
publisher = {USENIX Association},
month = jul

Presentation Video