Migration support for bit indexed explicit replication

• US 10,033,632 B2
• Filed: 01/09/2017
• Issued: 07/24/2018
• Est. Priority Date: 09/17/2013
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Shepherd, Gregory J., Martin, Christian
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US15/401,829
• Publication Number:
  US 20170142006A1
• Time in Patent Office: 561 Days
• Field of Search: None
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/33 using forward notification

Abstract

A method and network device are disclosed for multicast forwarding. In one embodiment, the method includes receiving at a node configured to use a bit-indexed forwarding table a multicast message comprising an incoming message bit array. The method further includes comparing the incoming message bit array to a first neighbor bit array within a first forwarding table entry, and determining that for at least one relative bit position in the bit arrays a corresponding destination node is both a destination for the message and a reachable destination from a first neighboring node. The method further includes forwarding toward the first neighboring node a copy of the message, where a first node on the path of the forwarded message is not configured to use a respective bit-indexed forwarding table. An embodiment of the device includes a network interface, a memory and a processor configured to perform steps of the method.

Claims

1. A method comprising:

receiving advertised information associated with destination nodes that are enabled for bit indexed explicit replication (BIER) within a communications network domain, wherein

the network domain includes one or more BIER-enabled nodes and one or more non-BIER-enabled nodes, and

the advertised information comprises router identifier information and bit position information for the destination nodes;

determining, for a destination node of the network domain, a first node along a designated path linking a BIER-enabled forwarding node in the network domain to the destination node;

if the first node is a BIER-enabled node,

including the first node in a bit indexed routing table at the forwarding node,

wherein the bit indexed routing table stores a mapping of the router identifier information to the bit position information, and

including the first node in a bit indexed forwarding table at the forwarding node; and

if the first node is not a BIER-enabled node,

determining a nearest BIER-enabled node along the designated path,

including the nearest BIER-enabled node in the bit indexed routing table and the bit indexed forwarding table instead of the first node, and

encoding into the bit indexed forwarding table an instruction to forward a data message to the nearest BIER-enabled node via the first node.

2. The method of claim 1, wherein the designated path comprises a path determined by a shortest-path algorithm.

3. The method of claim 1, further comprising:

receiving, from BIER-enabled nodes within the network domain, BIER-related information.

4. The method of claim 3, wherein the BIER-related information comprises a multiprotocol label switching (MPLS) label having a value reserved for BIER forwarding.

5. The method of claim 3, further comprising:

determining whether the first node is a BIER-enabled node.

6. The method of claim 5, wherein determining whether the first node is a BIER-enabled node comprises considering whether received BIER-related information comprises BIER-related information associated with the first node.

7. The method of claim 1, wherein encoding into the bit indexed forwarding table an instruction comprises entering into the bit indexed forwarding table a combination of a first forwarding label for use by the first node and a second forwarding label for use by the nearest BIER-enabled node.

8. A network device for use with a communications network domain, the network device comprising:

one or more network interfaces; and

a processor configured to

receive advertised information associated with destination nodes that are enabled for bit indexed explicit replication (BIER) within the network domain, wherein

the network domain includes one or more BIER-enabled nodes and one or more non-BIER-enabled nodes, and

the advertised information comprises router identifier information and bit position information for the destination nodes,

determine, for a destination node of the network domain, a first node along a designated path linking a BIER-enabled forwarding node in the network domain to the destination node,

if the first node is a BIER-enabled node,

include the first node in a bit indexed routing table at the forwarding node, wherein the bit indexed routing table stores a mapping of the router identifier information to the bit position information, and

include the first node in a bit indexed forwarding table at the forwarding node, and

if the first node is not a BIER-enabled node,

determine a nearest BIER-enabled node along the designated path,

include the nearest BIER-enabled node in the bit indexed routing table and the bit indexed forwarding table instead of the first node, and

encode into the bit indexed forwarding table an instruction to forward a data message to the nearest BIER-enabled node via the first node.

9. The network device of claim 8, wherein the network device implements a network controller.

10. The network device of claim 8, wherein the network device implements the forwarding node.

11. The network device of claim 10, further comprising a set of memory locations configured to store the bit indexed forwarding table.

12. The network device of claim 8, wherein the designated path comprises a path determined by a shortest-path algorithm.

13. The network device of claim 8, wherein the processor is further configured to receive, from BIER-enabled nodes within the network domain, BIER-related information.

14. The network device of claim 13, wherein the BIER-related information comprises a multiprotocol label switching (MPLS) label having a value reserved for BIER forwarding.

15. The network device of claim 13, wherein the processor is further configured to determine whether the first node is a BIER-enabled node.

16. The network device of claim 15, wherein the processor is further configured to consider whether received BIER-related information comprises BIER-related information associated with the first node, in connection with determining whether the first node is a BIER-enabled node.

17. The network device of claim 8, wherein the processor is further configured to enter into the bit indexed forwarding table a combination of a first forwarding label for use by the first node and a second forwarding label for use by the nearest BIER-enabled node, in connection with encoding into the bit indexed forwarding table an instruction.

18. The network device of claim 8, further comprising a first set of memory locations configured to store the bit indexed forwarding table and a second set of memory locations configured to store the bit indexed routing table.