Bit indexed explicit replication for layer 2 networking

• US 10,218,524 B2
• Filed: 11/07/2014
• Issued: 02/26/2019
• 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., Nainar, Nagendra Kumar
• Primary Examiner(s): Shah, Chirag G
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US14/536,153
• Publication Number:
  US 20150078380A1
• Time in Patent Office: 1,572 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/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• 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 link layer protocol frame at a network device. The link layer protocol frame includes a MAC address that identifies the link layer protocol frame as a being a multicast frame. The method then involves selecting a subset of ports included on the network device and forwarding the link layer protocol frame to only the selected subset of ports.

Claims

1. A method comprising:

receiving a link layer protocol frame at a link layer network device, wherein

the link layer protocol frame comprises a multicast media access control (MAC) address and a set identifier value, wherein

the set identifier value identifies a respective set of bit position mappings among a plurality of sets of bit position mappings, and

each of the plurality of sets of bit position mappings is stored in a respective bit forwarding table among a plurality of bit forwarding tables, and

the link layer network device comprises a plurality of ports;

determining whether the link layer protocol frame comprises a tag indicating that the link layer protocol frame is a bit indexed explicit replication (“

BIER”

) frame;

in response to determining that the link layer protocol frame comprises the tag indicating that the link layer protocol frame is a BIER frame,

accessing a frame bit mask within the link layer protocol frame, wherein

the frame bit mask comprises a plurality of bit positions,

each bit position within the frame bit mask represents a link layer destination device among a plurality of link layer destination devices, and

each of the plurality of link layer destination devices is represented by at least one relative bit position in the frame bit mask, and

selecting a subset of ports of the plurality of ports by accessing a relevant bit forwarding table at the link layer network device, wherein

the selecting comprises

using the set identifier value to select the relevant bit forwarding table from among the plurality of bit forwarding tables, and

using the frame bit mask to select the subset of ports from the relevant bit forwarding table, wherein

 

the subset of ports includes less than all of the plurality of ports; and

forwarding a modified copy of the link layer protocol frame to each selected port.

2. The method of claim 1, further comprising:

receiving an address announcement comprising information identifying a relative bit position assigned to one of the plurality of link layer destination devices.

3. The method of claim 2, further comprising:

updating the bit forwarding table, wherein the bit forwarding table relates the relative bit position assigned to a destination device to a port for forwarding to the destination device.

4. The method of claim 1, further comprising:

modifying the frame bit mask.

5. The method of claim 1, wherein

the link layer protocol frame is an Ethernet frame.

6. The method of claim 1, further comprising:

if the MAC address is a unicast MAC address, selecting a port corresponding to a destination device associated with the unicast MAC address, wherein the unicast MAC address comprises an identifier of a relative bit position representing the destination device in the frame bit mask.

7. The method of claim 1, further comprising:

detecting a connection failure between the link layer network device and a first link layer destination device, wherein

the first link layer destination device is one of the plurality of link layer destination devices, and

a second link layer destination device is another one of the plurality of link layer destination devices;

in response to detecting the connection failure, transferring ownership of a related bit position in the frame bit mask from the first link layer destination device to the second link layer destination device.

8. The method of claim 1, further comprising:

in response to determining that the link layer protocol frame does not comprise the tag indicating that the link layer protocol frame is a BIER frame, forwarding a copy of the link layer protocol frame to one or more of the plurality of ports.

9. A link layer network device comprising:

a memory for storing a bit forwarding table;

one or more ports configured to receive a link layer protocol frame, wherein

the frame comprises a multicast media access control (MAC) address and a set identifier value, wherein

the set identifier value identifies a respective set of bit position mappings among a plurality of sets of bit position mappings, and

each of the plurality of sets of bit position mappings is stored in a respective bit forwarding table among a plurality of bit forwarding tables; and

a processor configured to

determine whether the link layer protocol frame comprises a tag indicating that the link layer protocol frame is a bit indexed explicit replication (“

BIER”

) frame,

in response to determining that the link layer protocol frame comprises the tag indicating that the link layer protocol frame is a BIER frame,

access a frame bit mask within the link layer protocol frame, wherein

the frame bit mask comprises a plurality of bit positions,

each bit position within the frame bit mask represents a link layer destination device among a plurality of link layer destination devices, and

each of the plurality of link layer destination devices is represented by at least one relative bit position in the frame bit mask, and

select a subset of ports of the plurality of ports joy accessing a relevant bit forwarding table at the link layer network device, wherein

selecting the subset of ports comprises

 

using the set identifier value to select the relevant bit forwarding table from among the plurality of bit forwarding tables, and

 

using the frame bit mask to select the subset of ports from the relevant bit forwarding table, wherein the subset of ports includes less than all of the plurality of ports, and;

forward a modified copy of the link layer protocol frame to each selected port.

10. The link layer network device of claim 9, wherein the processor is further configured to:

receive an address announcement comprising information identifying a relative bit position assigned to one of the plurality of link layer destination devices.

11. The link layer network device of claim 10, wherein the processor is further configured to:

update the bit forwarding table in response to receiving the address announcement.

12. The link layer network device of claim 9, wherein the processor is further configured to:

modify the frame bit mask.

13. The link layer network device of claim 9, wherein the processor is further configured to:

if the MAC address is a unicast MAC address, select a port corresponding to a destination device associated with the unicast MAC address, wherein the unicast MAC address comprises an identifier of a relative bit position representing the destination device in the frame bit mask.

14. A system comprising:

storage means for storing a bit forwarding table;

network interface means for receiving a link layer protocol frame, wherein

the frame comprises a multicast media access control (MAC) address and a set identifier value, wherein

the set identifier value identifies a respective set of bit position mappings among a plurality of sets of bit position mappings, and

each of the plurality of sets of bit position mappings is stored in a respective bit forwarding table among a plurality of bit forwarding tables, and

the network interface means comprises a plurality of ports; and

processing means for

determining whether the link layer protocol frame comprises a tag indicating that the link layer protocol frame is a bit indexed explicit replication (“

BIER”

) frame;

in response to determining that the link layer protocol frame comprises the tag indicating that the link layer protocol frame is a BIER frame,

accessing a frame bit mask within the link layer protocol frame, wherein

the frame bit mask comprises a plurality of bit positions,

each bit position within the frame bit mask represents a link layer destination device among a plurality of link layer destination devices, and

each of the plurality of intended destination devices is represented by at least one relative bit position in the frame bit mask, and

selecting a subset of ports of the plurality of ports by accessing a relevant bit forwarding table at a link layer network device, wherein

the selecting comprises

 

using the set identifier value to select the relevant bit forwarding table from among the plurality of bit forwarding tables, and

 

using the frame bit mask to select the subset of ports from the relevant bit forwarding table, wherein the subset of ports includes less than all of the plurality of ports, and

forwarding a copy of the link layer protocol frame to each selected port.

15. The system of claim 14, wherein the processing means is further for:

receiving an address announcement

including information identifying a relative bit position assigned to one of the plurality of intended destination devices.

16. The system of claim 15, wherein the processing means is further for:

updating the bit forwarding table in response to receiving the address announcement.

17. The system of claim 14, wherein the processing means is further for:

if the MAC address is a unicast MAC address, selecting a port corresponding to a destination device associated with the unicast MAC address, wherein the unicast MAC address comprises an identifier of a relative bit position representing the destination device in the frame bit mask.