  Modern network virtualization platforms enable users to specify custom
topologies and arbitrary addressing schemes for their virtual networks. These
platforms have, however, been targeting the data center of a single provider,
which is insufficient to support (critical) applications that need to be
deployed across multiple trust domains, while enforcing diverse security
requirements. This paper addresses this limitation by presenting a novel
solution for the central resource allocation problem of network virtualization
-- the virtual network embedding, which aims to find efficient mappings of
virtual network requests onto the substrate network. We improve over the
state-of-the-art by considering security as a first-class citizen of virtual
networks, while enhancing the substrate infrastructure with resources from
multiple cloud providers. Our solution enables the definition of flexible
policies in three core elements: on the virtual links, where alternative
security compromises can be explored (e.g., encryption); on the virtual
switches, supporting various degrees of protection and redundancy if necessary;
and on the substrate infrastructure, extending it across multiple clouds,
including public and private facilities, with their inherently diverse trust
levels associated. We propose an optimal solution to this problem formulated as
a Mixed Integer Linear Program (MILP). The results of our evaluation give
insight into the trade-offs associated with the inclusion of security demands
into network virtualization. In particular, they provide evidence that
enhancing the user's virtual networks with security does not preclude high
acceptance rates and an efficient use of resources, and allows providers to
increase their revenues.
