A method is implemented by a network device for enabling destination network address translation in a cloud network. The method includes determining that packets having a first public address as a source address and a second public address as a destination address are to be forwarded to a first host that is assigned a first private address and sending a first advertisement message to a gateway indicating that packets having the first public address as a source address and the second public address as a destination address are to be forwarded to a first switch connected to the first host, where the first switch is configured to translate the destination address of those packets from the second public address to the first private address assigned to the first host.