Failure protection for traffic-engineered bit indexed explicit replication

• US 10,122,614 B2
• Filed: 02/26/2016
• Issued: 11/06/2018
• Est. Priority Date: 02/26/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Eckert, Toerless, Wijnands, Ijsbrand, Shepherd, Gregory A., Ranns, Neale D. R.
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Reddivalam, Srinivasa
• Application Number:
  US15/054,480
• Publication Number:
  US 20160254991A1
• Time in Patent Office: 984 Days
• Field of Search: None
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods and network devices are disclosed for failure protection in traffic-engineered bit indexed explicit replication networks. In one embodiment, a method includes receiving at a node in a network a message comprising a message bit array, where bit positions in the message bit array correspond to respective links in the network. The method further includes evaluating a bit value at a bit position in the message bit array, where the bit position corresponds to a network link represented in a forwarding table for the node, checking for a failure state of the link represented in the forwarding table, and, responsive to a determination of a failure state of the link, modifying one or more bit values in the message bit array. In one embodiment a network device includes a network interface, a memory configured to store a forwarding table, and a processor configured to carry out the methods.

Claims

1. A method comprising:

receiving at a node in a network a message comprising a message bit array, wherein

bit positions in the message bit array correspond to respective links in the network, and

the message bit array encodes one or more paths to be taken by the message to one or more egress nodes of the network;

evaluating a bit value at a bit position in the message bit array, wherein the bit position corresponds to a network link represented in a forwarding table for the node;

checking for a failure state of the network link represented in the forwarding table; and

responsive to a determination of a failure state of the network link, modifying two or more bit values in the message bit array to form a modified message bit array, wherein

the modified message bit array encodes one or more alternate paths to be taken by the message, when forwarded, to the one or more egress nodes,

modifying the two or more bit values comprises accessing a path update table corresponding to the network link having the failure state, and

the path update table indicates bits within the message bit array to be set and bits within the message bit array to be reset.

2. The method of claim 1, wherein the modifying two or more bit values comprises changing the bit value at the bit position in the message bit array corresponding to the failed network link.

3. The method of claim 1, wherein the modifying two or more bit values further comprises changing a bit value at a bit position in the message bit array corresponding to a network link in the one or more alternate paths to be taken by the message.

4. The method of claim 1, further comprising:

in response to a determination of no failure state of the network link represented in the forwarding table, forwarding the message over the network link if a result of the evaluating indicates that the network link is included in the one or more paths to be taken by the message.

5. The method of claim 1, further comprising:

determining, based on the evaluating the bit value, whether the network link represented in the forwarding table is included in the one or more paths to be taken by the message.

6. The method of claim 5, wherein the checking for a failure state of the network link is performed in response to a determination that the network link is included in the one or more paths to be taken by the message.

7. The method of claim 1, wherein the network link represented in the forwarding table directly connects the network node to an adjacent node in the network.

8. The method of claim 1, further comprising, subsequent to the modifying two or more bit values in the message bit array, forwarding the message, comprising the modified message bit array, over an alternative network link, wherein the alternative network link is included, as a result of the modifying, in a path to be taken by the message.

9. The method of claim 8, wherein

the message is a multicast message;

and

forwarding the message comprises forwarding a replica of the message.

10. The method of claim 1, further comprising:

evaluating a bit value at an additional bit position in the message bit array, wherein the additional bit position corresponds to an additional network link represented in the forwarding table for the node;

checking for a failure state of the additional network link; and

responsive to a determination of a failure state of the additional network link, modifying two or more bit values in the message bit array to form an additional modified message bit array, wherein

the additional modified message bit array encodes one or more additional alternate paths to be taken by the message, when forwarded, to the one or more egress nodes.

11. A network device associated with a node in a network, the network device comprising:

a network interface;

a memory configured to store a forwarding table for the node; and

a processor configured to

receive via the network interface a message comprising a message bit array, wherein

bit positions in the message bit array correspond to respective links in the network, and

the message bit array encodes one or more paths to be taken by the message to one or more egress nodes of the network,

evaluate a bit value at a bit position in the message bit array, wherein the bit position corresponds to a network link represented in the forwarding table,

check for a failure state of the network link represented in the forwarding table, and

responsive to a determination of a failure state of the network link, modify two or more bit values in the message bit array to form a modified message bit array, wherein

the modified message bit array encodes one or more alternate paths to be taken by the message, when forwarded, to the one or more egress nodes,

the processor is configured to, in connection with modifying the two or more bit values, access a path update table corresponding to the network link having the failure state, and

the path update table indicates bits within the message bit array to be set and bits within the message bit array to be reset.

12. The network device of claim 11, wherein the processor is further configured to change the bit value at the bit position in the message bit array corresponding to the failed network link, in connection with modifying the two or more bit values.

13. The network device of claim 11, wherein the processor is further configured to change a bit value at a bit position in the message bit array corresponding to a network link in the one or more alternate paths to be taken by the message, in connection with modifying the two or more bit values.

14. The network device of claim 11, wherein the processor is further configured to, in response to a determination of no failure state of the network link represented in the forwarding table, forward the message over the network link if a result of the evaluating indicates that the network link is included in the one or more paths to be taken by the message.

15. The network device of claim 11, wherein the processor is further configured to determine, based on evaluating the bit value, whether the network link represented in the forwarding table is included in the one or more paths to be taken by the message.

16. The network device of claim 15, wherein the processor is further configured to check for the failure state of the network responsive to a determination that the network link is included in the one or more paths to be taken by the message.

17. The network device of claim 11, wherein the network link represented in the forwarding table directly connects the network node to an adjacent node in the network.

18. The network device of claim 11, wherein the processor is further configured to, subsequent to modifying two or more bit values in the message bit array, forward the message, comprising the modified message bit array, over an alternative network link, wherein the alternative network link is included, as a result of the modifying, in a path to be taken by the message.

19. The network device of claim 18, wherein

the message is a multicast message;

and

the processor is further configured to replicate the message in connection with forwarding the message over the alternative network link.