A fast reroute (FRR) technique is implemented at the edge of a network. In accordance with the technique, if an edge device detects a node or link failure that prevents it from communicating with a neighboring routing domain, the edge device reroutes at least some data packets addressed to that domain to a backup edge device which, in turn, forwards the packets to the neighboring domain. The rerouted packets are designated as being "protected" (i.e., rerouted) data packets before they are forwarded to the backup edge device. To differentiate which data packets are protected and which are not, the backup edge device employs different sets of VPN label values for protected and non-protected network traffic. That is, the backup edge device may allocate two different VPN label values for at least some destination address prefixes that are reachable through the neighboring domain: a first VPN label value for FRR protected traffic and a second VPN label value for non-protected traffic. Upon receiving a data packet containing a protected VPN label value, the backup edge device is not permitted to reroute the packet a second time, e.g., in response to another inter-domain node or link failure, thereby preventing loops from developing at the edge of the network.