Recent SDN-based solutions give cloud providers the opportunity to extend their "as-a-service" model with the offer of complete network virtualization. They provide tenants with the freedom to specify the network topologies and addressing schemes of their choosing, while guaranteeing the required level of isolation among them. These platforms, however, have been targeting the datacenter of a single cloud provider with full control over the infrastructure. This paper extends this concept further by supporting the creation of virtual networks that span across several datacenters, which may belong to distinct cloud providers, while including private facilities owned by the tenant. In order to achieve this, we introduce a new network layer above the existing cloud hypervisors, affording the necessary level of control over the communications while hiding the heterogeneity of the clouds. The benefits of this approach are various, such as enabling finer decisions on where to place the virtual machines (e.g., to fulfill legal requirements), avoiding single points of failure, and potentially decreasing costs. Although our focus in the paper is on architecture design, we also present experimental results of a first prototype of the proposed solution.