Bridging of non-capable subnetworks in bit indexed explicit replication

• US 10,164,794 B2
• Filed: 04/28/2017
• Issued: 12/25/2018
• Est. Priority Date: 04/28/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Ranns, Neale D. R., Shepherd, Gregory J., Nainar, Nagendra Kumar
• Primary Examiner(s): Tran, Phuc
• Application Number:
  US15/582,090
• Publication Number:
  US 20180316520A1
• Time in Patent Office: 606 Days
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459

Abstract

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.

Claims

1. A method, comprising:

receiving, from a first network node not configured for bit indexed forwarding, a data message comprising a local label and 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;

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;

subsequent to the modifying, accessing an entry in a bit indexed forwarding table corresponding to a relative bit position of an intended destination node for the message; and

forwarding a copy of the data message comprising a forwarded message bit array to a second network node identified in the accessed forwarding table entry, wherein the second network node is configured for bit indexed forwarding.

2. The method of claim 1, wherein the first network node does not store a bit indexed forwarding table.

3. The method of claim 2, wherein

the first network 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, wherein

the one or more relative bit positions associated with the local label are stored in the ingress filter data structure as a filter bit array, and

each of the plurality of network destination nodes is represented by the same relative bit position in the filter bit array as in the message bit array.

5. The method of claim 4, wherein modifying the message bit array comprises:

performing a bitwise logical AND operation combining the message bit array with the filter bit array; and

replacing the message bit array with a result of the bitwise logical AND operation.

6. The method of claim 1, further comprising, prior to receiving the data message:

receiving from the first network node a tree descriptor message comprising a descriptor bit array, wherein

each of the plurality of network destination nodes is represented by the same relative bit position in the descriptor bit array as in the message bit array,

bit values within the descriptor bit array identify designated network destination nodes, and

the designated network destination nodes are destination nodes, from among the plurality of destination nodes, designated to be reached via a path including the first network node; and

storing, in the ingress filter data structure, an identification of relative bit positions corresponding to the designated network destination nodes.

7. The method of claim 6, wherein storing the identification of relative bit positions comprises storing the descriptor bit array.

8. The method of claim 6, wherein

the tree descriptor message further comprises a tree identifier associated with a label-switched path, and

the tree descriptor message further comprises a label request.

9. The method of claim 8, further comprising, subsequent to receiving the tree descriptor message and prior to receiving the data message:

allocating the local label for the label-switched path associated with the tree identifier; and

sending the local label to the first network node.

10. The method of claim 6, wherein

the first network node does not store a bit indexed routing table, and

the tree descriptor message comprises an explicit route object.

11. A network device, comprising:

a network interface;

a processor operably coupled to the network interface and adapted to

receive, from a first network node not configured for bit indexed forwarding, a data message comprising a local label and 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,

modify 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,

subsequent to modifying the message bit array, access an entry in a bit indexed forwarding table corresponding to a relative bit position of an intended destination node for the message, and

forward a copy of the data message comprising a forwarded message bit array to a second network node identified in the accessed forwarding table entry, wherein the second network node is configured for bit indexed forwarding.

12. The network device of claim 11, wherein the first network node does not store a bit indexed forwarding table.

13. The network device of claim 12, wherein

the first network 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.

14. The network device of claim 11, further comprising a set of storage locations adapted to store the ingress filter data structure.

15. The network device of claim 11, wherein

the one or more relative bit positions associated with the local label are stored in the ingress filter data structure as a filter bit array, and

each of the plurality of network destination nodes is represented by the same relative bit position in the filter bit array as in the message bit array.

16. The network device of claim 15, wherein the processor is further adapted to modify the message bit array by:

performing a bitwise logical AND operation combining the message bit array with the filter bit array; and

replacing the message bit array with a result of the bitwise logical AND operation.

17. The network device of claim 11, wherein the processor is further adapted to, prior to receiving the data message:

receive from the first network node a tree descriptor message comprising a descriptor bit array, wherein

each of the plurality of network destination nodes is represented by the same relative bit position in the descriptor bit array as in the message bit array,

bit values within the descriptor bit array identify designated network destination nodes, and

the designated network destination nodes are destination nodes, from among the plurality of destination nodes, designated to be reached via a path including the first network node; and

store, in the ingress filter data structure, an identification of relative bit positions corresponding to the designated network destination nodes.

18. The network device of claim 17, wherein the processor is further adapted to store the identification of relative bit positions by storing the descriptor bit array.

19. The network device of claim 17, wherein

the tree descriptor message further comprises a tree identifier associated with a label-switched path, and

the tree descriptor message further comprises a label request.

20. The network device of claim 19, wherein the processor is further adapted to, subsequent to receiving the tree descriptor message and prior to receiving the data message:

allocate the local label for the label-switched path associated with the tree identifier; and

send the local label to the first network node.