Bit indexed explicit replication using multiprotocol label switching

• US 10,225,090 B2
• Filed: 09/17/2014
• Issued: 03/05/2019
• 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, Ranns, Neale D. R., Skriver, Jesper
• Primary Examiner(s): Shah, Chirag G
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US14/488,790
• Publication Number:
  US 20150078378A1
• Time in Patent Office: 1,630 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:

receiving, from a sender node, a packet comprising;

a multiprotocol label switching (MPLS) label, and

a multicast forwarding entry comprising a packet bit mask having one or more bits set by the sender node, wherein the one or more bits correspond to at least one neighbor node of the node;

selecting an entry in a bit forwarding table based on determining that;

a first value of a first bit is stored in a bit string at a particular bit position; and

a second value of a second bit stored in the entry indicates that the entry is to be selected;

identifying, based on the bit forwarding table and the packet bit mask, the at least one neighbor node, wherein

the at least one neighbor node is identified by

selecting a subset of entries from the bit forwarding table, wherein the subset corresponds to the MPLS label,

determining a first set bit in the packet bit mask, and

selecting an entry among the subset of entries that corresponds to the first set bit;

copying the packet to create a copied packet that comprises a copy of the packet bit mask;

modifying the copy of the packet bit mask in the copied packet by clearing one or more of the bits that were set by the sender node;

removing a topmost label of an MPLS label stack of the copied packet;

creating, based on the bit forwarding table, a new topmost label identifying the at least one neighbor node;

attaching to the copied packet the new topmost label; and

forwarding the copied packet to the at least one neighbor node.

2. The method of claim 1, further comprising:

selecting forwarding information stored by the node based on the MPLS label; and

selecting the at least one neighbor node based on the forwarding information.

3. The method of claim 2, further comprising:

comparing the multicast forwarding entry with the forwarding information stored by the node by performing a logical AND operation between the multicast forwarding entry and at least a portion of the forwarding information.

4. The method of claim 1, wherein

the multicast forwarding entry comprises a plurality of elements, and

each element of the plurality of elements corresponds to a respective node.

5. The method of claim 1, further comprising:

updating the multicast forwarding entry by clearing a bit in the multicast forwarding entry.

6. The method of claim 1, wherein

the MPLS label identifies a bit mask length.

7. The method of claim 1, further comprising:

allocating a respective label range for each bit mask size of a plurality of bit mask sizes.

8. The method of claim 1, wherein

a plurality of neighbor nodes comprises the at least one neighbor node of the node, and

the method further comprises allocating a respective label range for each neighbor of the plurality of neighbors.

9. The method of claim 1, wherein

clearing the one or more bits that were set by the sender node comprises performing a logical AND operation between the packet bit mask and an inverse of the entry that was selected from the subset of entries.

10. The method of claim 1, wherein

the node comprises the bit forwarding table, and

the bit forwarding table is indexed based on a bit position of each bit.

11. A system comprising:

a first node configured to

receive, from a sender node, a packet comprising;

a multiprotocol label switching (MPLS) label, and

a multicast forwarding entry comprising a packet bit mask having one or more bits set by the sender node, wherein the one or more bits correspond to at least one neighbor node of the first node;

selecting an entry in a bit forwarding table based on determining that;

a first value of a first bit is stored in the bit string at a particular bit position, and

a second value of a second bit stored in the entry indicates that the entry is to be selected;

identify, based on the bit forwarding table and the packet bit mask, the at least one neighbor nodes, wherein

the at least one neighbor node is identified by

selecting a subset of entries from the bit forwarding table, wherein the subset corresponds to the MPLS label,

determining a first set bit in the packet bit mask, and

selecting an entry among the subset of entries that corresponds to the first set bit;

copy the packet to create a copied packet that comprises a copy of the packet bit mask;

modify the copy of the packet bit mask in the copied packet by clearing one or more of the bits that were set by the sender node;

remove a topmost label of an MPLS label stack of the copied packet;

creating, based on the bit forwarding table, a new topmost label identifying the at least one neighbor node;

attach to the copied packet the new topmost label; and

forward the packet to the at least one neighbor node.

12. The system of claim 11, wherein the first node is further configured to:

select forwarding information stored by the first node based on the MPLS label; and

select the at least one neighbor node based on the forwarding information.

13. The system of claim 11, wherein

the multicast forwarding entry comprises a plurality of elements, and

each element of the plurality of elements corresponds to a respective node.

14. The system of claim 11, wherein the first node is further configured to:

update the multicast forwarding entry by clearing a bit in the multicast forwarding entry.

15. The system of claim 11, wherein the first node is further configured to:

compare the multicast forwarding entry with forwarding information stored by the first node by performing a logical AND operation between the multicast forwarding entry and at least a portion of the forwarding information.

16. A non-transitory computer readable storage medium comprising instructions that are executable by one or more processors to perform operations comprising:

receiving, by a node, a packet comprising;

a multiprotocol label switching (MPLS) label, and

a multicast forwarding entry comprising a packet bit mask having one or more bits set by a sender node, wherein the one or more bits correspond to at least one neighbor node of the node;

selecting an entry in a bit forwarding table based on determining that;

a first value of a first bit is stored in the bit string at a particular bit position; and

a second value of a second bit stored in the entry indicates that the entry is to be selected;

identifying, based on the bit forwarding table and the packet bit mask, the at least one neighbor node, wherein

the at least one neighbor node is identified by

selecting a subset of entries from the bit forwarding table, wherein the subset corresponds to the MPLS label,

determining a first set bit in the packet bit mask, and

selecting an entry among the subset of entries that corresponds to the first set bit;

copying the packet to create a copied packet that comprises a copy of the packet bit mask;

modifying the copy of the packet bit mask in the copied packet by clearing one or more of the bits that were set by the sender node;

removing a topmost label of an MPLS label stack of the copied packet;

creating, based on the bit forwarding table, a new topmost label identifying the one or more neighbor nodes;

attaching to the copied packet the new topmost label; and

forwarding the copied packet to the at least one neighbor node.

17. The non-transitory computer readable storage medium of claim 16, wherein the operations further comprise:

selecting forwarding information stored by the node based on the MPLS label; and

selecting the neighbor node based on the forwarding information.

18. The non-transitory computer readable storage medium of claim 16, wherein

the multicast forwarding entry comprises a plurality of elements, and

each element of the plurality of elements corresponds to a respective node.

19. The non-transitory computer readable storage medium of claim 16, wherein the operations further comprise:

updating the multicast forwarding entry by clearing a bit in the multicast forwarding entry.

20. The non-transitory computer readable storage medium of claim 16, wherein the operations further comprise:

comparing the multicast forwarding entry with forwarding information stored by the node, by performing a logical AND operation between the multicast forwarding entry and a portion the forwarding information.