Methods and network devices are disclosed for failure protection in traffic-engineered bit indexed explicit replication networks. In one embodiment, a method includes determining a protected link or node in a network, where the protected link or node is included in a designated path to be taken by a message through the network to a destination node, the designated path is encoded in a message bit array carried by the message, and assigned bit positions in the message bit array represent respective network links along the designated path. The method further includes determining a backup path to the destination node from a feeder node adapted to forward a message carrying the message bit array into the protected link or node, and populating an entry in a path update table stored at the feeder node. In one embodiment a network device includes a network interface and a processor configured to carry out the methods.