Multicast traffic steering using tree identity in bit indexed explicit replication (BIER)
Methods and network devices are disclosed for multicast traffic steering in a communications network. In one embodiment, a method includes receiving, at a node in a network, a multicast message comprising an incoming message bit array and a tree identifier value. The embodiment further includes selecting a bit indexed forwarding table stored at the node and corresponding to the tree identifier value, accessing within the selected forwarding table an entry corresponding to an intended destination node for the message, and forwarding, to a neighboring node identified in the accessed entry, a copy of the message comprising a forwarded message bit array in place of the incoming message bit array. An embodiment of a network device includes one or more network interfaces and a processor adapted to perform steps of the method.
1. A method comprising:
receiving, at a node in a network, a multicast message comprising an incoming message bit array, a set identifier value and a first tree identifier value, wherein
each destination node among multiple possible destination nodes for the message is represented by a relative bit position in the incoming message bit array,
a bit value at a relative bit position in the incoming message bit array indicates whether the corresponding destination node is an intended destination node for the message,
the set identifier value selects a set of specific destination nodes within the multiple possible destination nodes, and
the first tree identifier value represents a first set of paths through the network linking a source node to each of the specific destination nodes;
selecting a bit indexed forwarding table stored at the node and corresponding to the set identifier value and the first tree identifier value;
accessing, within the selected bit indexed forwarding table, a forwarding table entry corresponding to an intended destination node for the message; and
forwarding, to a neighboring node identified in the accessed forwarding table entry, a copy of the message comprising a forwarded message bit array in place of the incoming message bit array.
2. The method of claim 1 , wherein
the forwarding table entry comprises a neighbor bit array,
the multiple possible destination nodes correspond to the same respective relative bit positions in the neighbor bit array as in the incoming message bit array, and
a bit value at a relative bit position in the neighbor bit array indicates whether the corresponding destination node is reachable from the neighboring node identified in the forwarding table entry.
3. The method of claim 1 , wherein the accessing comprises identifying an entry in the selected bit indexed forwarding table for which an intended destination node for the message is also a reachable destination node from the neighboring node identified in the entry.
4. The method of claim 3 , wherein the identifying an entry comprises:
identifying a relative bit position in the incoming message bit array corresponding to an intended destination node; and
identifying an entry in the selected bit indexed forwarding table for which the identified relative bit position corresponds to a reachable destination node.
5. The method of claim 1 , wherein
the multicast message further comprises a service header, and
the message bit array and first tree identifier value are stored within the service header.
6. The method of claim 5 , wherein the multicast message further comprises an Internet Protocol (IP) header.
7. The method of claim 1 , wherein
multiple neighboring nodes are identified in the accessed forwarding table entry, and
the forwarding comprises
selecting, from among the multiple neighboring nodes, a selected neighboring node, and
forwarding the copy of the message to the selected neighboring node.
8. The method of claim 7 , wherein the selecting comprises using a respective weight value associated with each of the multiple neighboring nodes in the accessed forwarding table entry.
9. The method of claim 7 , wherein the selecting comprises accessing a hash table.
10. The method of claim 1 , further comprising:
receiving a second tree identifier value and associated forwarding information, wherein the second tree identifier value represents a second set of paths through the network linking the source node to each of the specific destination nodes; and
generating a forwarding table corresponding to the second tree identifier.
11. A network device associated with a network node, the network device comprising:
one or more network interfaces; and
a processor adapted to
receive at the network node a multicast message comprising an incoming message bit array, a set identifier value and a tree identifier value, wherein
each destination node among multiple possible destination nodes for the message is represented by a relative bit position in the incoming message bit array,
a bit value at a relative bit position in the incoming message bit array indicates whether the corresponding destination node is an intended destination node for the message,
the set identifier value selects a set of specific destination nodes within the multiple possible destination nodes, and
the tree identifier value represents a set of paths through the network linking a source node to each of the specific destination nodes,
select a bit indexed forwarding table stored at the node and corresponding to the set identifier value and the tree identifier value,
access, within the selected bit indexed forwarding table, a forwarding table entry corresponding to an intended destination node for the message, and
forward, to a neighboring node identified in the accessed forwarding table entry, a copy of the message comprising a forwarded message bit array in place of the incoming message bit array.
12. The network device of claim 11 , further comprising a memory adapted to store one or more bit indexed forwarding tables comprising forwarding table entries.
13. The network device of claim 12 , wherein
the memory is further adapted to store a bit indexed forwarding table entry comprising a neighbor bit array,
the multiple possible destination nodes correspond to the same respective relative bit positions in the neighbor bit array as in the incoming message bit array, and
a bit value at a relative bit position in the neighbor bit array indicates whether the corresponding destination node is reachable from the neighboring node identified in the forwarding table entry.
14. The network device of claim 12 , wherein
the memory is further adapted to store a bit indexed forwarding table having multiple neighboring nodes identified in the accessed forwarding table entry, and
the processor is further adapted, in forwarding the copy of the message, to select, from among the multiple neighboring nodes, a selected neighboring node, and forward the copy of the message to the selected neighboring node.
15. The network device of claim 14 , wherein the processor is further adapted, in selecting the selected neighboring node, to use a respective weight value associated with each of the multiple neighboring nodes in the accessed forwarding table entry.
16. The network device of claim 14 , wherein the processor is further adapted, in selecting the selected neighboring node, to access a hash table.
17. The network device of claim 11 , wherein the processor is further adapted, in accessing the forwarding table entry corresponding to an intended destination node, to identify an entry in the selected bit indexed forwarding table for which an intended destination node for the message is also a reachable destination node from the neighboring node identified in the entry.
18. The network device of claim 11 , wherein
the processor is further adapted to receive a multicast message comprising a service header, and
the message bit array and tree identifier value are stored within the service header.
19. The network device of claim 18 , wherein the processor is further adapted to receive a multicast message comprising an IP header in addition to the service header.