Bit indexed explicit replication using multiprotocol label switching

• US 10,659,242 B2
• Filed: 07/31/2018
• Issued: 05/19/2020
• Est. Priority Date: 09/17/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Shepherd, Gregory J., Martin, Christian J., Ranns, Neale D. R., Skriver, Jesper
• Primary Examiner(s): Sefcheck, Gregory B
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US16/049,907
• Publication Number:
  US 20190058606A1
• Time in Patent Office: 658 Days
• Field of Search: None
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/74 Address processing for routing

Abstract

Various systems and methods for performing bit indexed explicit replication (BIER) using multiprotocol label switching (MPLS). For example, one method involves receiving a packet that includes a MPLS label. The packet also includes a multicast forwarding entry. The method also involves determining, based on the value of the MPLS label, whether to use the multicast forwarding entry to forward the packet. The method further includes forwarding the packet.

Claims

1. A method performed by a node, the method comprising:

selecting a bit forwarding table based, at least in part, on information in a received packet, wherein

the bit forwarding table is associated with one or more label values,

the received packet comprises a top label and a bit mask, and

the bit forwarding table is selected, at least in part, in response to a determination that the top label of the received packet is associated with a BIER-enabled node;

selecting a row as a selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on a label value identified in the top label and a bit position value corresponding to a first set bit in the bit mask, and

the selected row comprises a routing label associated with a neighbor node;

copying the received packet to create a copied packet;

replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and

forwarding the copied packet to the neighbor node, wherein the forwarding is based, at least in part, on the routing label.

2. The method of claim 1, wherein

each of the one or more label values associated with the bit forwarding table corresponds to at least one bit position values.

3. The method of claim 1, wherein

the copied packet comprises a copy of the bit mask.

4. The method of claim 3, further comprising

prior to the forwarding, modifying the copy of the bit mask of the copied packet by clearing one or more bits that had been set in the received packet.

5. The method of claim 3, wherein

the selected row further comprises

a bit mask value,

information identifying the neighbor node, and

a routing label associated with the neighbor node.

6. The method of claim 1, further comprising

selecting a second row as a second selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on the label value identified in the top label and a second bit position value corresponding to a second set bit in the bit mask, and

the second selected row comprises a second routine label associated with a second neighbor node;

copying the received packet to create a second copied packet; and

forwarding the second copied packet to the second neighbor node, wherein

the forwarding is based, at least in part, on the second routing label.

7. The method of claim 6, further comprising:

prior to forwarding the second copied packet, replacing the top label in the second copied packet with the routing label from the second selected row of the bit forwarding table.

8. A network device comprising:

one or more network interface cards;

a memory configured to store a bit routing table; and

a processor configured to perform a method comprising;

selecting a bit forwarding table based, at least in part, on information in a received packet, wherein

the bit forwarding table is associated with one or more label values,

the received packet comprises a top label and a bit mask, and

the bit forwarding table is selected, at least in part, in response to a determination that the top label of the received packet is associated with a BIER-enabled node;

selecting a row as a selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on a label value identified in the top label and a bit position value corresponding to a first set bit in the bit mask, and

the selected row comprises a routing label associated with a neighbor node;

copying the received packet to create a copied packet;

replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and

forwarding the copied packet to the neighbor node, wherein

the forwarding is based, at least in part, on the routing label.

9. The network device of claim 8, wherein

each of the one or more label values associated with the bit forwarding table corresponds to at least one bit position values.

10. The network device of claim 8, wherein the copied packet comprises a copy of the bit mask.

11. The network device of claim 10, wherein the method further comprises:

prior to the forwarding, modifying the copy of the bit mask of the copied packet by clearing one or more bits that had been set in the received packet.

12. The network device of claim 10, wherein

the selected row further comprises

a bit mask value, information identifying the neighbor node, and

a routing label associated with the neighbor node.

13. The network device of claim 8, wherein the method further comprises:

selecting a second row as a second selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on the label value identified in the top label and a second bit position value corresponding to a second set bit in the bit mask, and

the second selected row comprises a second routing label associated with a second neighbor node;

copying the received packet to create a second copied packet; and

forwarding the second copied packet to the second neighbor node, wherein

the forwarding is based, at least in part, on the second routing label.

14. The network device of claim 13, wherein the method further comprises:

prior to forwarding the second copied packet, replacing the top label in the second copied packet with the routing label from the second selected row of the bit forwarding table.

15. A system comprising

a first node configured to perform a method comprising:

selecting a bit forwarding table based, at least in part, on information in a received packet, wherein

the bit forwarding table is associated with one or more label values,

the received packet comprises a top label and a bit mask, and

the bit forwarding table is selected, at least in part, in response to a determination that the top label of the received packet is associated with a BIER-enabled node;

selecting a row as a selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on a label value identified in the top label and a bit position value corresponding to a first set bit in the bit mask, and

the selected row comprises a routing label associated with a neighbor node;

copying the received packet to create a copied packet;

replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and

forwarding the copied packet to the neighbor node, wherein

the forwarding is based, at least in part, on the routing label.

16. The system of claim 15, wherein

each of the one or more label values associated with the bit forwarding table corresponds to at least one bit position values.

17. The system of claim 15, wherein the copied packet comprises a copy of the bit mask.

18. The system of claim 17, wherein the method further comprises:

prior to the forwarding, modifying the copy of the bit mask of the copied packet by clearing one or more bits that had been set in the received packet.

19. The system of claim 17, wherein

the selected row further comprises

a bit mask value, information identifying the neighbor node, and

a routing label associated with the neighbor node.

20. The system of claim 15, wherein the method further comprises:

selecting a second row as a second selected row in the bit forwarding table, wherein

the selected row is selected based, at least in part, on the label value identified in the top label and a second bit position value corresponding to a second set bit in the bit mask, and

the second selected row comprises a second routing label associated with a second neighbor node;

copying the received packet to create a second copied packet; and

forwarding the second copied packet to the second neighbor node, wherein

the forwarding is based, at least in part, on the second routing label.