# US 10,122,614 B2 · Failure protection for traffic-engineered bit indexed explicit replication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,122,614 B2 - Document ID: US10122614B2 - Status: Granted - Kind: B2 - Application number: 15/054,480 - Filed: 2016-02-26 - Published: 2016-09-01 - Granted: 2018-11-06 - Earliest claimed: 2015-02-26 - Assignees: Cisco Technology, Inc. - Applicants: Cisco Technology, Inc. - Inventors: Toerless Eckert; Ijsbrand Wijnands; Gregory A. Shepherd; Neale D. R. Ranns - Web page: https://patentgrep.com/patent/US10122614B2 ## CPC - H04L 45/16: Multipoint routing - H04L 12/4633: {Interconnection of networks using encapsulation techniques, e.g. tunneling} - H04L 45/02: Topology update or discovery - H04L 45/28: using route fault recovery - H04L 69/22: Parsing or analysis of headers - H04L 45/745: Address table lookup; Address filtering - H04L 49/201: Multicast operation; Broadcast operation - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 5) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 8) The method of claim 8, wherein the message is a multicast message; and forwarding the message comprises forwarding a replica of the message. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 11) 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. ### Claim 18 (depends on 11) 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. ### Claim 19 (depends on 18) 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.