Bridging of non-capable subnetworks in bit indexed explicit replication
Methods and network devices are disclosed for traversal, within a network configured for bit indexed forwarding, of a subnetwork having nodes not configured for bit indexed forwarding. In one embodiment, a method includes receiving, from a first network node not configured for bit indexed forwarding, a data message comprising a local label and a message bit array. Bit values in the message bit array identify intended destination nodes for the message. The embodiment further includes modifying the message bit array to exclude as intended destination nodes for the message any nodes not represented by one or more relative bit positions associated with the local label and stored in an ingress filter data structure. In addition, the embodiment includes forwarding a copy of the data message to a second network node, which is configured for bit indexed forwarding, identified in an accessed entry of a bit indexed forwarding table.
1. A method, comprising:
receiving a data message comprising a message bit array, wherein
each of a plurality of network destination nodes is represented by a relative bit position within the message bit array, and
bit values in the message bit array identify intended destination nodes for the message from among the plurality of network destination nodes;
identifying one or more neighbor nodes corresponding to relative bit positions of one or more intended destination nodes for the message, wherein at least one of the neighbor nodes is a label-switching neighbor node not configured for forwarding using the message bit array; and
for each label-switching neighbor node among the one or more neighbor nodes,
determining a respective remote label assigned for use by the label-switching neighbor node;
encapsulating a copy of the data message to carry the remote label in addition to the message bit array; and
forwarding the copy of the data message to the label-switching neighbor node.
2. The method of claim 1 , wherein the label-switching neighbor node does not store a bit indexed forwarding table.
3. The method of claim 2 , wherein
the label-switching network neighbor node does store a bit indexed routing table; and
the bit indexed routing table comprises
router identifiers for network nodes,
a mapping of relative bit positions to respective represented network destination nodes within the plurality of network destination nodes, and
a mapping of network destination nodes within the plurality of network destination nodes to respective neighbor nodes via which the destination nodes are reachable.
4. The method of claim 1 , further comprising, prior to receiving the data message:
receiving the remote label from the label-switching neighbor node; and
storing the remote label into an entry in a bit indexed forwarding table.
5. The method of claim 4 , further comprising, prior to receiving the remote label:
sending a tree descriptor message to the label-switching neighbor node, wherein
the tree descriptor message comprises a tree identifier and a descriptor bit array,
each of the plurality of network destination nodes is represented by a relative bit position within the descriptor bit array, and
bit values in the descriptor bit array identify destination nodes, from among the plurality of destination nodes, to be reached via a network tree identified by the tree identifier.
6. The method of claim 5 , wherein
the tree descriptor message further comprises a payload object; and
the descriptor bit array is within the payload object.
7. The method of claim 5 , wherein the tree descriptor message further comprises one or more explicit route objects.
8. A network device, comprising:
a network interface; and
a processor operably coupled to the network interface and adapted to
receive a data message comprising a message bit array, wherein
each of a plurality of network destination nodes is represented by a relative bit position within the message bit array, and
bit values in the message bit array identify intended destination nodes for the message from among the plurality of network destination nodes,
identify one or more neighbor nodes corresponding to relative bit positions of one or more intended destination nodes for the message, wherein at least one of the neighbor nodes is a label-switching neighbor node not configured for forwarding using the message bit array, and
for each label-switching neighbor node among the one or more neighbor nodes,
determine a respective remote label assigned for use by the label-switching neighbor node,
encapsulate a copy of the data message to carry the remote label in addition to the message bit array, and
forward the copy of the data message to the label-switching neighbor node.
9. The network device of claim 8 , wherein the label-switching neighbor node does not store a bit indexed forwarding table.
10. The network device of claim 9 , wherein
the label-switching neighbor node does store a bit indexed routing table; and
the bit indexed routing table comprises
router identifiers for network nodes,
a mapping of relative bit positions to respective represented network destination nodes within the plurality of network destination nodes, and
a mapping of network destination nodes within the plurality of network destination nodes to respective neighbor nodes via which the destination nodes are reachable.
11. The network device of claim 8 , wherein the processor is further adapted to, prior to receiving the data message:
receive the remote label from the label-switching neighbor node; and
store the remote label into an entry in a bit indexed forwarding table.
12. The network device of claim 11 , further comprising a set of storage locations adapted to store the bit indexed forwarding table.
13. The network device of claim 11 , wherein the processor is further adapted to, prior to receiving the remote label:
send a tree descriptor message to the label-switching neighbor node, wherein
the tree descriptor message comprises a tree identifier and a descriptor bit array,
each of the plurality of network destination nodes is represented by a relative bit position within the descriptor bit array, and
bit values in the descriptor bit array identify destination nodes, from among the plurality of destination nodes, to be reached via a network tree identified by the tree identifier.
14. The network device of claim 13 , wherein
the tree descriptor message further comprises a payload object; and
the descriptor bit array is within the payload object.
15. A non-transitory computer readable medium comprising computer readable instructions executable to:
receive a data message comprising a message bit array, wherein
each of a plurality of network destination nodes is represented by a relative bit position within the message bit array, and
bit values in the message bit array identify intended destination nodes for the message from among the plurality of network destination nodes;
identify one or more neighbor nodes corresponding to relative bit positions of one or more intended destination nodes for the message, wherein at least one of the neighbor nodes is a label-switching neighbor node not configured for forwarding using the message bit array; and
for each label-switching neighbor node among the one or more neighbor nodes,
determine a respective remote label assigned for use by the label-switching neighbor node,
encapsulate a copy of the data message to carry the remote label in addition to the message bit array, and
forward the copy of the data message to the label-switching neighbor node.
16. The computer readable medium of claim 15 , wherein the label-switching neighbor node does not store a bit indexed forwarding table.
17. The computer readable medium of claim 16 , wherein
the label-switching neighbor node does store a bit indexed routing table; and
the bit indexed routing table comprises
router identifiers for network nodes,
a mapping of relative bit positions to respective represented network destination nodes within the plurality of network destination nodes, and
a mapping of network destination nodes within the plurality of network destination nodes to respective neighbor nodes via which the destination nodes are reachable.
18. The computer readable medium of claim 15 , wherein the instructions are further executable to, prior to receiving the data message:
receive the remote label from the label-switching neighbor node; and
store the remote label into an entry in a bit indexed forwarding table.
19. The computer readable medium of claim 18 , wherein the instructions are further executable to, prior to receiving the remote label:
send a tree descriptor message to the label-switching neighbor node, wherein
the tree descriptor message comprises a tree identifier and a descriptor bit array,
each of the plurality of network destination nodes is represented by a relative bit position within the descriptor bit array, and
bit values in the descriptor bit array identify destination nodes, from among the plurality of destination nodes, to be reached via a network tree identified by the tree identifier.
20. The computer readable medium of claim 19 , wherein
the tree descriptor message further comprises a payload object; and
the descriptor bit array is within the payload object.