Many security challenges arise when mutually untrusted tenants are co-located in the same virtualized network infrastructure. Cloud systems commonly employ different network isolation mechanisms to prevent interferences among tenants' networks, which may rely on different and complementary isolation strategies. In this work, we define three complementary strategies for addressing multi-tenant isolation in cloud networks, observe that no current virtualization architecture implements all the three strategies, and propose a novel architectural design to cover the identified gap.