In one embodiment, a system includes a plurality of first host machines implementing a public-cloud computing environment, wherein at least one of the first host machines comprises at least one public-cloud virtual machine (VM) that performs network address translation; and a plurality of second host machines implementing a private-cloud computing environment, wherein at least one of the second host machines comprises one or more private-cloud virtual machines, wherein the public-cloud VM is configured to receive, via a network tunnel from the private-cloud VM, one or more first packets to be sent to a public Internet Protocol (IP) address of a public network host, translate, using a NAT mapping, a source address of each first packet from a private IP address of the private-cloud VM to an IP address of the public-cloud VM, and send the first packet to the IP address of the public-cloud VM.