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). A set of interfaces on each side of the network edge device for a set of equal cost paths, in some embodiments, are bonded together in the network edge device to correspond to a single interface on either side of a logical bridge including at least one logical switch providing a stateful service implemented by the network edge device. The bond is implemented, in some embodiments, by a bonding module executing on the network edge device that maintains a mapping between ingress and egress interfaces to allow deterministic forwarding through the network edge device in the presence of bonded interfaces.