Bit indexed explicit replication

• US 10,498,547 B2
• Filed: 11/30/2017
• Issued: 12/03/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 J.
• Primary Examiner(s): Crompton, Christopher R
• Application Number:
  US15/827,084
• Publication Number:
  US 20180083790A1
• Time in Patent Office: 733 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

Methods, devices and computer readable storage media for performing bit indexed explicit replication (BIER) are disclosed. One embodiment of a method includes receiving, at an ingress node of a network, a data packet comprising a multicast group identifier. This embodiment also includes obtaining, from a group membership table, a bit mask corresponding to the multicast group identifier. The bit mask comprises a plurality of bit positions, and each bit position corresponds to a respective egress node of the network. The embodiment also includes encapsulating the data packet with the bit mask and forwarding the encapsulated data packet using the bit mask.

Claims

1. A method comprising:

receiving, at an ingress node of a network configured for bit indexed forwarding, a data packet comprising a multicast group identifier;

obtaining, from a group membership table stored at the ingress node, a bit mask corresponding to the multicast group identifier, wherein

the bit mask comprises a plurality of bit positions, and

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

encapsulating the data packet with the bit mask; and

forwarding the encapsulated data packet using the bit mask.

2. The method of claim 1, further comprising:

receiving at the ingress node a signaling message from a first egress node of the network, wherein the signaling message comprises

a request to join or to leave a multicast group corresponding to the multicast group identifier, and

a bit position, within the bit mask, assigned to the first egress node.

3. The method of claim 2, further comprising:

generating or updating an entry in the group membership table using information in the signaling message.

4. The method of claim 1, further comprising:

receiving at the ingress node an advertisement sent by a first egress node of the network, wherein the advertisement identifies the first egress node and a bit position, within the bit mask, assigned to the first egress node.

5. The method of claim 4, further comprising:

generating or updating, using information from the advertisement, a bit routing table at the ingress node, wherein an entry of the bit routing table comprises

an identifier of the first egress node,

an identifier of the bit position assigned to the first egress node, and

an identifier of an egress interface or neighbor node via which the first egress node is reachable from the ingress node.

6. The method of claim 5, further comprising:

generating or updating, using the bit routing table, a bit forwarding table at the ingress node.

7. The method of claim 1, wherein the multicast group identifier comprises an address associated with a multicast group.

8. A network device, comprising:

one or more network interfaces adapted to receive, at an ingress node of a network configured for bit indexed forwarding, a data packet comprising a multicast group identifier;

a processor adapted to

obtain, from a group membership table stored at the network device, a bit mask corresponding to the multicast group identifier of a received data packet, wherein the bit mask comprises a plurality of bit positions, and

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

encapsulate the received data packet with the bit mask, and

forward the encapsulated data packet, using the bit mask, via one or more of the network interfaces.

9. The network device of claim 8, wherein the one or more network interfaces are further adapted to receive at the ingress node a signaling message from a first egress node of the network, wherein the signaling message comprises

a request to join or to leave a multicast group corresponding to the multicast group identifier, and

a bit position, within the bit mask, assigned to the first egress node.

10. The network device of claim 9, wherein the processor is further adapted to generate or update an entry in the group membership table using information in the signaling message.

11. The network device of claim 8, wherein the one or more network interfaces are further adapted to receive at the ingress node an advertisement sent by a first egress node of the network, wherein the advertisement identifies the first egress node and a bit position, within the bit mask, assigned to the first egress node.

12. The network device of claim 11, wherein the processor is further adapted to generate or update, using information in the advertisement, a bit routing table at the network device, wherein an entry of the bit routing table comprises

an identifier of the first egress node,

an identifier of the bit position assigned to the first egress node, and

an identifier of an egress interface or neighbor node via which the first egress node is reachable from the ingress node.

13. The network device of claim 12, wherein the processor is further adapted to generate or update, using the bit routing table, a bit forwarding table at the network device.

14. The network device of claim 8, wherein the multicast group identifier comprises an address associated with a multicast group.

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, at an ingress node of a network configured for bit indexed forwarding, a data packet comprising a multicast group identifier;

obtaining, from a group membership table stored at the ingress node, a bit mask corresponding to the multicast group identifier, wherein

the bit mask comprises a plurality of bit positions, and

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

encapsulating the data packet with the bit mask; and

forwarding the encapsulated data packet using the bit mask.

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

receiving at the ingress node a signaling message from a first egress node of the network, wherein the signaling message comprises

a request to join or to leave a multicast group corresponding to the multicast group identifier, and

a bit position, within the bit mask, assigned to the first egress node.

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

generating or updating an entry in the group membership table using information in the signaling message.

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

receiving at the ingress node an advertisement sent by a first egress node of the network, wherein the advertisement identifies the first egress node and a bit position, within the bit mask, assigned to the first egress node.

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

generating or updating, using information from the advertisement, a bit routing table at the ingress node, wherein an entry of the bit routing table comprises

an identifier of the first egress node,

an identifier of the bit position assigned to the first egress node, and

an identifier of an egress interface or neighbor node via which the first egress node is reachable from the ingress node.

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

generating or updating, using the bit routing table, a bit forwarding table at the ingress node.