Per-prefix LFA FRR with bit indexed explicit replication

• US 10,536,324 B2
• Filed: 05/30/2018
• Issued: 01/14/2020
• 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): Sefcheck, Gregory B
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US15/993,050
• Publication Number:
  US 20180278470A1
• Time in Patent Office: 594 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

Methods, devices and program instructions are disclosed for performing bit indexed explicit replication (BIER) including fast reroute capability. One embodiment of a method includes receiving, from an egress node of a BIER network, an advertisement at a forwarding node, where the advertisement identifies a mapping of the egress node to a bit position of a packet bit string to be carried by a packet through the network. The embodiment further includes generating or updating a primary entry for the egress node in a bit indexed routing table (BIRT) for the forwarding node, and determining whether a backup entry for the egress node is to be included in the BIRT. In response to a determination that a backup entry is to be included, the embodiment further includes generating or updating the backup entry in the BIRT.

Claims

1. A method comprising:

receiving, at a forwarding node in a network configured for bit indexed forwarding, an advertisement, wherein

the advertisement is received from an egress node of the network, and

the advertisement identifies a mapping of the egress node to a bit position of a packet bit string to be carried by a packet through the network;

generating or updating a primary entry for the egress node in a bit indexed routing table for the forwarding node, wherein

the primary entry comprises information identifying the bit position, the egress node, and a primary neighbor node for forwarding of a packet to the egress node;

determining whether a backup entry for the egress node is to be included in the bit indexed routing table;

in response to a determination that a backup entry is to be included, generating or updating the backup entry in the bit indexed routing table, wherein

the backup entry comprises information identifying the bit position, the egress node, and a backup neighbor node for forwarding of a packet to the egress node when a path through the primary neighbor node becomes unavailable;

receiving a packet comprising a packet bit string; and

forwarding the packet according to information in either the primary entry or the backup entry.

2. The method of claim 1, further comprising determining the primary neighbor node.

3. The method of claim 1, further comprising determining the backup neighbor node.

4. The method of claim 1, further comprising:

generating or updating a primary entry for the egress node in a bit indexed forwarding table for the forwarding node;

determining whether a backup path exists for the egress node; and

in response to a determination that a backup path exists for the egress node, generating or updating a backup entry for the egress node in the bit indexed forwarding table.

5. The method of claim 4, wherein the primary entry for the egress node in the bit indexed forwarding table comprises information identifying the bit position and the primary neighbor node.

6. The method of claim 5, wherein the primary entry for the egress node in the bit indexed forwarding table further comprises information identifying bit positions mapped to one or more additional egress nodes reachable via the primary neighbor node.

7. The method of claim 4, wherein the backup entry for the egress node in the bit indexed forwarding table comprises information identifying the bit position and the backup neighbor node.

8. The method of claim 7, wherein the backup entry for the egress node in the bit indexed forwarding table further comprises information identifying bit positions mapped to one or more additional egress nodes reachable via the backup neighbor node.

9. A network device, comprising:

a network interface adapted for communication with one or more nodes of a network configured for bit indexed forwarding;

device memory configured to store a bit indexed routing table for a forwarding node of the network; and

a processor operably coupled to the network interface and the memory locations, wherein the processor is configured to

receive an advertisement from an egress node of the network, wherein the advertisement identifies a mapping of the egress node to a bit position of a packet bit string to be carried by a packet through the network,

generate or update a primary entry for the egress node in the bit indexed routing table, wherein the primary entry comprises information identifying the bit position, the egress node, and a primary neighbor node for forwarding of a packet to the egress node;

determine whether a backup entry for the egress node is to be included in the bit indexed routing table;

in response to a determination that a backup entry is to be included, generate or update the backup entry in the bit indexed routing table, wherein the backup entry comprises information identifying the bit position, the egress node, and a backup neighbor node for forwarding of a packet to the egress node when a path through the primary neighbor node becomes unavailable;

receive a packet comprising a packet bit string; and

forward the packet according to information in either the primary entry or the backup entry.

10. The network device of claim 9, wherein the processor is further configured to determine the primary neighbor node.

11. The network device of claim 9, wherein the processor is further configured to determine the backup neighbor node.

12. The network device of claim 9, further comprising additional device memory configured to store a bit indexed forwarding table for the forwarding node of the network, and wherein the processor is further configured to

generate or update a primary entry for the egress node in the bit indexed forwarding table,

determine whether a backup path exists for the egress node, and

in response to a determination that a backup path exists for the egress node, generate or update a backup entry for the egress node in the bit indexed forwarding table.

13. The network device of claim 12, wherein the primary entry for the egress node in the bit indexed forwarding table comprises information identifying the bit position and the primary neighbor node.

14. The network device of claim 13, wherein the primary entry for the egress node in the bit indexed forwarding table further comprises information identifying bit positions mapped to one or more additional egress nodes reachable via the primary neighbor node.

15. The network device of claim 12, wherein the backup entry for the egress node in the bit indexed forwarding table comprises information identifying the bit position and the backup neighbor node.

16. The network device of claim 15, wherein the backup entry for the egress node in the bit indexed forwarding table further comprises information identifying bit positions mapped to one or more additional egress nodes reachable via the backup neighbor node.

17. A non-transitory computer readable storage medium comprising program instructions, wherein the program instructions are operable, when executed by a processor for a forwarding node of a network configured for bit indexed forwarding, to perform a method comprising:

receiving an advertisement, wherein

the advertisement is received from an egress node of the network, and

the advertisement identifies a mapping of the egress node to a bit position of a packet bit string to be carried by a packet through the network;

generating or updating a primary entry for the egress node in a bit indexed routing table for the forwarding node, wherein

the primary entry comprises information identifying the bit position, the egress node, and a primary neighbor node for forwarding of a packet to the egress node;

determining whether a backup entry for the egress node is to be included in the bit indexed routing table;

in response to a determination that a backup entry is to be included, generating or updating the backup entry in the bit indexed routing table, wherein

the backup entry comprises information identifying the bit position, the egress node, and a backup neighbor node for forwarding of a packet to the egress node when a path through the primary neighbor node becomes unavailable;

receiving a packet comprising a packet bit string; and

forwarding the packet according to information in either the primary entry or the backup entry.

18. The non-transitory computer readable storage medium of claim 17, wherein the method further comprises determining the primary neighbor node.

19. The non-transitory computer readable storage medium of claim 17, wherein the method further comprises determining the backup neighbor node.

20. The non-transitory computer readable storage medium of claim 17, wherein the method further comprises:

generating or updating a primary entry for the egress node in a bit indexed forwarding table for the forwarding node;

determining whether a backup path exists for the egress node; and

in response to a determination that a backup path exists for the egress node, generating or updating a backup entry for the egress node in the bit indexed forwarding table.