Per-prefix LFA FRR with bit indexed explicit replication

• US 10,003,494 B2
• Filed: 01/23/2015
• Issued: 06/19/2018
• Est. Priority Date: 09/17/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Shepherd, Gregory J., Martin, Christian J., Asati, Rajiv
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US14/603,547
• Publication Number:
  US 20150138961A1
• Time in Patent Office: 1,243 Days
• Field of Search: None
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74 Address processing for routing

Abstract

Various systems and methods for performing bit indexed explicit replication (BIER). For example, one method involves receiving a packet at a node. The packet includes a bit string includes information identifying a plurality of destinations. The node selects an entry in a bit indexed forwarding table (BIFT). The BIFT includes both a primary path entry and a backup path entry. The node forwards the packet based on information in the entry.

Claims

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.