Bit indexed explicit replication

• US 9,853,822 B2
• Filed: 09/17/2014
• Issued: 12/26/2017
• Est. Priority Date: 09/17/2013
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Shepherd, Gregory J., Martin, Christian
• Primary Examiner(s): Crompton, Christopher R
• Application Number:
  US14/488,761
• Publication Number:
  US 20150078377A1
• Time in Patent Office: 1,196 Days
• Field of Search: 370390
• 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, at a first node in a network, an advertisement sent by an egress node of the network, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;

generating or updating a bit routing table at the first node, wherein

the generating or updating comprises using information from the advertisement, and

an entry of the bit routing table comprises an identifier of the egress node, an identifier of the bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the first node;

receiving, at the first node, a data packet for transmission to one or more egress nodes of the network, wherein

the data packet comprises a multicast forwarding entry,

the multicast forwarding entry comprises the bit mask, and

each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

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

selecting at least one neighbor node based on the comparing;

updating the multicast forwarding entry; and

forwarding a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

2. The method of claim 1, wherein

the multicast forwarding entry comprises a set identifier, and

a value of the set identifier corresponds to a respective set of egress nodes represented by the bit positions of the plurality of bit positions.

3. The method of claim 1, wherein

the updating the multicast forwarding entry comprises clearing a bit within the bit mask.

4. The method of claim 1, wherein

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

5. The method of claim 1, further comprising:

deriving a bit position within the bit mask from a routable address associated with a node.

6. The method of claim 1, further comprising:

generating or updating a bit forwarding table comprising the forwarding information, wherein the generating or updating the bit forwarding table comprises using the bit routing table.

7. The method of claim 1, wherein one or more egress nodes of the network is associated with a respective host computer or receiver.

8. The method of claim 1, wherein receiving an advertisement comprises receiving an interior gateway protocol advertisement.

9. The method of claim 2, wherein at least one bit position within the plurality of bit positions corresponds to different egress nodes for respective different values of the set identifier.

10. The method of claim 2, wherein comparing the multicast forwarding entry with forwarding information comprises selecting a portion of the forwarding information corresponding to the value of the set identifier in the multicast forwarding entry.

11. A system comprising:

a first node configured to

receive an advertisement sent by an egress node of a network comprising the first node, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;

generate or update a bit routing table for the first node, wherein

the first node is configured to generate or update the bit routing table using information from the advertisement, and

an entry of the bit routing table comprises an identifier of the egress node, an identifier of the bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the first node;

receive a data packet for transmission to one or more egress nodes of the network, wherein

the data packet comprises a multicast forwarding entry,

the multicast forwarding entry comprises the bit mask, and

each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

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

select at least one neighbor node based on the comparing;

update the multicast forwarding entry; and

forward a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

12. The system of claim 11, wherein

the multicast forwarding entry comprises a set identifier, and

a value of the set identifier corresponds to a respective set of egress nodes represented by the bit positions of the plurality of bit positions.

13. The system of claim 11, wherein

updating the multicast forwarding entry comprises clearing a bit within the bit mask.

14. The system of claim 11, wherein

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

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

use the bit routing table to generate a bit forwarding table comprising the forwarding information.

16. The system of claim 11, wherein the first node comprises a port processor adapted to receive the advertisement, receive the packet, and forward the packet.

17. The system of claim 16, wherein the first node further comprises a processor adapted to:

generate or update the bit routing table;

compare the multicast forwarding entry with the forwarding information;

select the neighbor node; and

update the multicast forwarding entry.

18. The system of claim 11, wherein the first node comprises memory adapted to store the bit routing table.

19. 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, at a first node in a network, an advertisement sent by an egress node of the network, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;

generating or updating a bit routing table at the first node, wherein

the generating or updating comprises using information from the advertisement, and

an entry of the bit routing table comprises an identifier of the egress node, an identifier of the bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the first node;

receiving, at the first node, a data packet for transmission to one or more egress nodes of the network, wherein

the data packet comprises a multicast forwarding entry,

the multicast forwarding entry comprises the bit mask, and

each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

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

selecting at least one neighbor node based on the comparing;

updating the multicast forwarding entry; and

forwarding a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

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

the multicast forwarding entry comprises a set identifier, and

a value of the set identifier corresponds to a respective set of egress nodes represented by the bit positions of the plurality of bit positions.

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

the updating the multicast forwarding entry comprises clearing a bit within the bit mask.

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

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

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

deriving a bit position within the bit mask from a routable address associated with a node.