For a multi-tenant virtual network system, a non-transitory machine readable medium of processing a data message that is associated with a virtual network that is defined for a particular tenant over a plurality of public cloud datacenters, the program for execution by at least one hardware processing unit, the program comprising sets of instructions for:
- determining that the data message is associated with an external service machine outside of the virtual network and the plurality of public cloud datacenters;
- based on a tenant identifier (TID) for the particular tenant in the virtual network system, performing a first source network address translation (SNAT) operation to modify a first source network address of the data message to a modified second source network address;
- performing a second SNAT operation to modify the modified second source network address of the data message to a modified third source network address;
- and
- forwarding the data message, with the third modified source network address to the external service machine through an external network that is outside of the public cloud datacenters.