Scalable Constraint-based Virtual Data Center Allocation

Scalable Constraint-based Virtual Data Center Allocation

Sam Bayless, Nodir Kodirov, Ivan Beschastnikh, Holger H. Hoos, Alan J. Hu

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 546-554. https://doi.org/10.24963/ijcai.2017/77

Constraint-based techniques can solve challenging problems arising from highly diverse applications. This paper considers the problem of virtual data center (VDC) allocation, an important, emerging challenge for modern data center operators. To solve this problem, we introduce NETSOLVER, which is based on the general-purpose constraint solver MONOSAT. NETSOLVER represents a major improvement over existing approaches: it is sound, complete, and scalable, providing support for end-to-end, multi-path bandwidth guarantees across all the layers of hosting infrastructure, from servers to top-of-rack switches to aggregation switches to access routers. NETSOLVER scales to realistic data center sizes and VDC topologies, typically requiring just seconds to allocate VDCs of 5–15 virtual machines to physical data centers with 1000+ servers, maintaining this efficiency even when the data center is nearly saturated. In many cases, NETSOLVER can allocate 150%−300% as many total VDCs to the same physical data center as previous methods. Essential to our solution efficiency is our formulation of VDC allocation using monotonic theories, illustrating the practical value of the recently proposed SAT modulo monotonic theories approach.
Keywords:
Constraints and Satisfiability: Applications
Constraints and Satisfiability: Modeling/Formulation
Constraints and Satisfiability: Solvers and Tools