A method in a network element that includes multiple interfaces for connecting to a communication network includes receiving via an ingress interface packets that are not allowed to undergo re-routing and that are addressed to a destination via a first egress interface. The packets are forwarded via the first egress interface when there is a valid path from the first egress interface to the destination. When there is no valid path from the first egress interface to the destination, a second egress interface is selected from a group of multiple egress interfaces that have respective paths to the destination and are assigned to packets for which re-routing is allowed, and the packets are forwarded via the second egress interface until recovering a path to the destination.