Methods, systems and computer program products provide for recovery from a failure of a primary routing communication protocol stack which routes communications over connections to a virtual Internet Protocol address (VIPA) and at least one port associated with the VIPA to a plurality of other communication protocol stacks associated by the primary routing stack and with the VIPA and the at least one port. At least one backup routing communication protocol stack is identified. The backup routing stack stores an identification of stacks associated with the VIPA and the at least one port as candidate target stacks. Messages are received at the backup routing stack identifying stacks having application instances bound to the VIPA and listening on the at least one port as current actual target stacks. Connections to the VIPA and the at least one port for current actual target stacks are also identified and a routing table constructed from the received messages so as to provide routing path information to current actual target stacks associated with the connection. Messages on the connections to the VIPA and the at least one port are routed through the backup stack utilizing the constructed routing table.