Distributed network address translation for efficient cloud service access

A non-transitory machine readable medium storing a program which when executed by at least one processing unit of a computing device in a virtualize environment, the program comprising sets of instructions for:

• maintaining a list of allocated replacement IP address and port number pairs by a NAT agent on a host machine by a network address allocator, wherein the network address allocator maintains a pool of replacement IP addresses and port number pairs and allocates a range of replacement IP address and port number pairs to an NAT agent to uniquely identify tenant VMs across a plurality of tenant logical networks;
• assigning a replacement IP address and port number pair to a tenant VM on the host machine for accessing a service VM;
• storing a mapping of the replacement IP address and port number pair to the tenant VM's actual IP address and port number;
• performing source NAT (SNAT) on packets sent from the tenant VM to the service VM;
• and
• performing destination NAT (DNAT) on packets sent from the service VM to the tenant VM.