Existing network virtualization systems sh … Existing network virtualization systems share a few characteristics, namely they target one data center of a single operator and only offer traditional networking services. As such, their support for critical applications that need to be deployed across multiple trust domains, while enforcing diverse security
requirements, is limited. This paper enhances the state-of-the-art by presenting a multi-cloud network virtualization system, allowing the provision of virtual networks of containers. Our solution enables a provider to enrich its network substrate with public and private cloud-based resources, increasing flexibility and the range of supplied services. One challenging aspect that we tackle is the embedding of virtual network requests to the substrate infrastructure, as existing work is unfit to a modern data center context, scales poorly or does not consider the security of virtual resources. We propose a scalable heuristic that considers security as a first-class citizen and is specifically tailored to a hybrid multi-cloud domain. We evaluate our algorithm with large-scale simulations that consider realistic network topologies and our prototype in a substrate composed of one private data center and two public clouds. The system scales well for networks of thousands of switches employing diverse topologies and improves on the virtual network acceptance ratio, provider revenue, and embedding delays. Our results show that the acceptance ratios are less than 1% from the optimal and that the system can provision a 10 thousand container virtual network in approximately 2 minutes. irtual network in approximately 2 minutes.