Network virtualization is emerging as a po … Network virtualization is emerging as a powerful technique to allow multiple virtual networks (VN), eventually speciﬁed by different tenants, to run on a shared infrastructure. With the recent advances on Software Deﬁned Networks(SDN), network virtualization– traditionally limited to Virtual Local Area Networks (VLAN) – has gained new traction. Amajorchallengeinnetworkvirtualizationishowtomakeefﬁcientuseoftheshared resources. Virtual network embedding (VNE) addresses this problem by ﬁnding an effective mapping of the virtual nodes and links onto the substrate network (SN). VNE has been studied in the network virtualization literature, with several different algorithms having been proposed to solve the problem. Typically, these algorithms address various requirements, such as quality of service (QoS), economic costs or dependability. A mostly unexplored perspective on this problem is providing security assurances, a gap increasingly more relevant to organizations, as they move their critical services to the cloud. Recently proposed virtualization platforms give tenants the freedom to specify their network topologies and addressing schemes. These platforms have been targeting only a datacenter of a single cloud provider, forcing complete trust on the provider to run the workloads correctly and limiting dependability. Unfortunately, there is increasing evidence that problems do occur at a cloud scale, of both malicious and benign natures. Thus, in this thesis we argue that security and dependability is becoming a critical factor that should be considered by VNE algorithms. Motivated by this, we deﬁne the secure and dependable VNE problem, and design an algorithm that addresses this problem in multiple cloud environments. By not relying on a single cloud we avoid internet-scale single points of failures, ensuring the recovery from cloud outages by replicating workloads across providers. Our solution can also enhance security by leaving sensitive workloads in more secure clouds: for instance, in private clouds under control of the user or in facilities that employ the required security features. The results from our experiments show that there is a cost in providing security and availability that may reduce the provider proﬁt. However, a relatively small increase in the price of the richer features of our solution (e.g., security resources) enables the provider to offer secure and dependable network services at a proﬁt. Our experiments also show that our algorithm behaves similarly to the most commonly used VNE algorithm when security and dependability are not requested by VNs. nd dependability are not requested by VNs.