Failure protection is provided between two routers that are actively implementing load sharing using network address translation. Failure protection is achieved by generating state information at the two routers and then exchanging the state information between the two routers so that each router has a combined set of state information that can be used in the event of a failure of the other router.