Per-prefix LFA FRR with bit indexed explicit replication

1. A method comprising:

receiving advertisements from egress nodes of a network configured for bit indexed forwarding, wherein

each of the advertisements identifies a respective bit position of a packet bit string to be carried by a packet through the network,

the respective bit position is assigned to a respective egress node from which the respective advertisement is received, and

each of the advertisements comprises a respective router identifier assigned to the respective egress node;

generating a bit indexed forwarding table (BIFT) based on the advertisements, wherein the BIFT comprises a primary path entry and a backup path entry identifying a bit position identified in one of the advertisements;

receiving a packet at a node, wherein

the packet comprises a bit string, and

the bit string includes information identifying a plurality of the egress nodes;

selecting an entry in the BIFT; and

forwarding the packet based on the bit string and the entry.

2. The method of claim 1 , further comprising:

detecting a failure;

switching from the primary path entry to the backup path entry.

3. The method of claim 2 , wherein

the failure comprises one of a node failure or a link failure.

4. The method of claim 1 , further comprising:

generating the primary path entry based on one or more of the advertisements; and

generating the backup path entry based on one or more of the advertisements.

5. The method of claim 1 , further comprising:

detecting a failure; and

updating the BIFT in response to the detecting.

6. The method of claim 1 , further comprising:

detecting reconvergence of the network; and

updating the BIFT in response to the detecting.

7. The method of claim 1 , wherein

the selecting comprises determining whether the primary path entry is active or the backup path entry is active.

8. A network device comprising:

a memory storing a bit indexed forwarding table (BIFT) that was built based on advertisements received by the network device from egress nodes of a network configured for bit indexed forwarding, wherein

each of the advertisements identifies a respective bit position of a packet bit string to be carried by a packet through the network,

the respective bit position is assigned to a respective egress node from which the respective advertisement is received, and

each of the advertisements comprises a respective router identifier assigned to the respective egress node;

a network interface configured to receive a packet, wherein

the packet comprises a bit string, and

the bit string includes information identifying a plurality of the egress nodes; and

a processor configured to

select an entry in the BIFT, wherein

the BIFT comprises a primary path entry and a backup path entry identifying a bit position identified in one of the advertisements, and

forward the packet based on the information and the entry.

9. The network device of claim 8 , wherein the processor is further configured to:

detect a failure;

switch from the primary path entry to the backup path entry.

10. The network device of claim 9 , wherein

the failure comprises one of a node failure or a link failure.

11. The network device of claim 8 , wherein the processor is further configured to:

generate the primary path entry based on one or more of the advertisements; and

generate the backup path entry based on one or more of the advertisements.

12. The network device of claim 8 , wherein the processor is further configured to:

detect a failure; and

update the BIFT in response to detecting the failure.

13. The network device of claim 8 , wherein the processor is further configured to:

detect reconvergence of the network; and

update the BIFT in response to detecting reconvergence.

14. The network device of claim 8 , wherein

selecting the entry comprises determining whether the primary path entry is active or the backup path entry is active.

15. A system comprising:

storage means for storing a bit indexed forwarding table (BIFT) that was built based on advertisements received from egress nodes of a network configured for bit indexed forwarding, wherein

each of the advertisements identifies a respective bit position of a packet bit string to be carried by a packet through the network,

the respective bit position is assigned to a respective egress node from which the respective advertisement is received, and

each of the advertisements comprises a respective router identifier assigned to the respective egress node;

network interface means for receiving a packet, wherein

the packet comprises a bit string, and

the bit string includes information identifying a plurality of the egress nodes;

processing means for

selecting an entry in the BIFT, wherein

the BIFT comprises a primary path entry and a backup path entry identifying a bit position identified in one of the advertisements, and

forwarding the packet based on the information and the entry.

16. The system of claim 15 , wherein the processing means is further configured to:

detect a failure;

switch from the primary path entry to the backup path entry.

17. The system of claim 16 , wherein

the failure comprises one of a node failure or a link failure.

18. The system of claim 15 , wherein the processing means is further configured to:

generate the primary path entry based on one or more of the advertisements; and

generate the backup path entry based on one or more of the advertisements.

19. The system of claim 15 , wherein the processing means is further configured to:

detect reconvergence of the network; and

update the BIFT in response to detecting reconvergence.

20. The system of claim 15 , wherein

selecting the entry comprises determining whether the primary path entry is active or the backup path entry is active.