Bit Indexed Explicit Replication

• US 20150078377A1
• Filed: 09/17/2014
• Published: 03/19/2015
• 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
• Granted Patent: US 9,853,822 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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). For example, one method involves receiving a packet at a node. The packet includes a multicast forwarding entry. The multicast forwarding entry has a plurality of elements, and each element corresponds to a particular node. The method also involves comparing the multicast forwarding entry with forwarding information stored by the node. The method involves selecting a neighbor node based on the comparing, updating the multicast forwarding entry in the packet, and forwarding the packet to the neighbor node.

Claims

1. A method comprising:

receiving a packet at a node comprising a multicast forwarding entry, wherein

the multicast forwarding entry comprises a plurality of elements, and

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

comparing the multicast forwarding entry with forwarding information stored by the node;

selecting at least one neighbor node based on the comparing;

updating the multicast forwarding entry; and

forwarding the packet to the at least one neighbor node.

2. The method of claim 1, wherein

the multicast forwarding entry comprises a bit mask comprising a plurality of bits, and

each bit of the plurality of bits corresponds to a respective node.

3. The method of claim 1, wherein

the multicast forwarding entry comprises a set identifier.

4. The method of claim 1, wherein

the updating the multicast forwarding entry comprises clearing a bit.

5. The method of claim 1, wherein

the comparing comprises performing a logical AND operation between the multicast forwarding entry and a portion the forwarding information.

6. The method of claim 1, further comprising:

deriving a bit position from a routable address associated with a node.

7. The method of claim 1, further comprising:

generating a bit forwarding table.

8. The method of claim 1, further comprising:

receiving an advertisement, wherein

the advertisement includes information identifying a bit position and a corresponding node.

9. A system comprising:

a first node configured to

receive a packet at a node comprising a multicast forwarding entry, wherein

the multicast forwarding entry comprises a plurality of elements, and

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

compare the multicast forwarding entry with forwarding information stored by the node;

select at least one neighbor node based on the comparing;

update the multicast forwarding entry; and

forward the packet to the at least one neighbor node.

10. The system of claim 9, wherein

the multicast forwarding entry comprises a bit mask comprising a plurality of bits, and

each bit of the plurality of bits corresponds to one of the respective nodes.

11. The system of claim 9, wherein

the multicast forwarding entry comprises a set identifier.

12. The system of claim 9, wherein

updating the multicast forwarding entry comprises clearing a bit.

13. The system of claim 9, wherein

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

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

generate a bit forwarding table.

15. A non-transitory computer readable storage medium comprising executable instructions, wherein a method is implemented in response to executing the instructions, the method comprising:

receiving a packet at a node comprising a multicast forwarding entry, wherein

the multicast forwarding entry comprises a plurality of elements, and

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

comparing the multicast forwarding entry with forwarding information stored by the node;

selecting at least one neighbor node based on the comparing;

updating the multicast forwarding entry; and

forwarding the packet to the at least one neighbor node.

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

the multicast forwarding entry comprises a bit mask comprising a plurality of bits, and

each bit of the plurality of bits corresponds to a respective node.

17. The non-transitory computer readable storage medium of claim 15, wherein

the multicast forwarding entry comprises a set identifier.

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

the updating the multicast forwarding entry comprises clearing a bit.

19. The non-transitory computer readable storage medium of claim 15, wherein

the comparing comprises performing a logical AND operation between the multicast forwarding entry and a portion the forwarding information.

20. The non-transitory computer readable storage medium of claim 15, wherein the method further comprises:

deriving a bit position from a routable address associated with a node.