Providing stateful services deployed in redundant gateways connected to asymmetric network

A method for ensuring that data messages requiring stateful processing are received at a gateway device storing state information, the method comprising:

• using a first cost to advertise, from a first gateway device of a datacenter, an availability of a set of internet protocol (IP) addresses to an external network, the first cost being a higher cost than a second cost used by a second gateway device of the datacenter to advertise the availability of the set of IP addresses, said higher first cost used by the first gateway to direct data messages from the external network that need stateful processing to the second gateway device that stores state information for providing the stateful processing based on the lower second cost advertised by the second gateway, wherein the stateful processing comprises at least one of (i) a stateful load balancing service, (ii) a firewall service, and (iii) a virtual private network (VPN) service;
• to redirect a particular data message from the external network that needs stateful services and that reaches the first gateway device despite the advertised higher first cost, performing a redirection operation comprising:
• receiving the particular data message from the external network at the first gateway device directed to an IP address in the set of advertised IP addresses;
• determining, based on a policy-based routing rule, that the received particular data message requires stateful processing provided at the second gateway device;
• and
• based on the determination, forwarding the received particular data message to an uplink interface of the second gateway device for the second gateway device to provide the stateful processing, wherein the uplink interface of the second gateway device connects to the external network.