Some embodiments of the invention provide novel methods for providing a stateful service at a network edge device (e.g., an NSX edge) that has a plurality of north-facing interfaces (e.g., interfaces to an external network) and a plurality of corresponding south-facing interfaces (e.g., interfaces to a logical network). In some embodiments, the network edge device receives data messages from a first gateway device from a logical network, provides the stateful network service to the data message, and forwards the data message towards the destination through a corresponding interface connected to a physical network.