Distributed network address translation for efficient cloud service access

A non-transitory machine-readable medium storing a program for coordinating distributed network address translation (NAT) in a network within which a plurality of logical networks are implemented, the logical networks comprising a plurality of tenant logical networks and a set of logical networks, each logical network in the set comprising a set of service virtual machines (VMs) for access by VMs of the tenant logical networks, the program executable by at least one processing unit of a controller server within said network, the program comprising sets of instructions for:

• defining a plurality of replacement network address and port number pairs, each pair for uniquely identifying a VM across the plurality of the tenant logical networks;
• and
• sending, to at least one host that is hosting a VM of a tenant first logical network for which access is requested to the service VMs of a second logical network in the set of logical networks, (i) a set of replacement network address and port number pairs from the plurality of replacement network address and port number pairs, and (ii) a set of rules identifying the VM of the tenant first logical network as a VM that requires a replacement of source network address and source port number for accessing the service VMs of the second logical network,
• wherein a replacement network address and port number pair sent to a host is for the host to replace, based on said set of rules, a source network address and a source port number with the replacement network address and port number pair in a packet that is destined from the VM of the tenant first logical network to a service VM of the second logical network.