Some embodiments of the invention provide novel methods for facilitating a distributed SNAT (dSNAT) middlebox service operation for a first network at a host computer in the first network on which the dSNAT middlebox service operation is performed and a gateway device between the first network and a second network. The novel methods enable dSNAT that provides stateful SNAT at multiple host computers, thus avoiding the bottleneck problem associated with providing stateful SNAT at gateways and also significantly reduces the need to redirect packets received at the wrong host by using a capacity of off-the-shelf gateway devices to perform IPv6 encapsulation for IPv4 packets and assigning locally unique IPv6 addresses to each host executing a dSNAT middlebox service instance that are used by the gateway device.