Network virtualization is a key enabler for cloud computing and its economic benefits. However, many security challenges arise when mutually untrusted tenants are co-located in the same virtualized network infrastructure. To address such issues, multi-tenant environments commonly employ isolation mechanisms to prevent interferences among different tenants' network behavior. Even though the need for multi-tenant network isolation is widely accepted, and most cloud systems do employ network virtualization technologies to address this need, it is not always clear what exactly is isolated in each approach and, consequently, the level of security obtained in each case. Aiming to address this matter, in this article we describe three complementary strategies for addressing multi-tenant isolation in cloud networks, classified according to the type of tenant network resource being isolated, namely: data paths, software resources and hardware resources. These three strategies are then applied in the evaluation of existing network virtualization architectures, showing that most of them focus only on data path isolation. We then propose a more holistic design, based on the concept of “tenant network domains”, which combines the aforementioned isolation strategies to create a more secure network virtualization architecture.