Per-Prefix LFA FRR With Bit Indexed Explicit Replication

• US 20150138961A1
• Filed: 01/23/2015
• Published: 05/21/2015
• 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
• Granted Patent: US 10,003,494 B2
• Time in Patent Office: Days
• US Class Current: 370/228
• 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 a packet at a node, wherein

the packet comprises a bit string, and

the bit string includes information identifying a plurality of destinations;

selecting an entry in a bit indexed forwarding table (BIFT), wherein

the BIFT comprises a primary path entry and a backup path entry; and

forwarding the packet based on the information and the entry.

3. The method of claim 1, 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; and

generating the backup path entry.

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; 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.

2. The method of claim 2, further comprising:

detecting a failure;

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

8. A network device comprising:

a memory storing a bit indexed forwarding table (BIFT);

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 destinations; and

a processor configured to

select an entry in the BIFT, wherein

the BIFT comprises a primary path entry and a backup path entry, 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; and

generate the backup path entry.

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; 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);

network interface means for receiving a packet, wherein

the packet comprises a bit string, and

the bit string includes information identifying a plurality of destinations;

processing means for

selecting an entry in the BIFT, wherein

the BIFT comprises a primary path entry and a backup path entry, 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; and

generate the backup path entry.

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

detect reconvergence; 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.