In one embodiment, a secure transport layer tunnel may be established over a public network between a first cloud gateway in a private cloud and a second cloud gateway in a public cloud, where the secure transport layer tunnel is configured to provide a link layer network extension between the private cloud and the public cloud. In addition, a cloud virtual Ethernet module (cVEM) may be executed (instantiated) within the public cloud, where the cVEM is configured to switch inter-virtual-machine (VM) traffic between the private cloud and one or more private application VMs in the public cloud connected to the cVEM.