# US 2020/0287733 A1 · Bit indexed explicit replication using multiprotocol label switching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0287733 A1
- Document ID: US20200287733A1
- Status: Published application
- Kind: A1
- Application number: 16/876,217
- Filed: 2020-05-18
- Published: 2020-09-10
- Earliest claimed: 2013-09-17
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Ijsbrand Wijnands; Gregory J. Shepherd; Christian J. Martin; Neale D. R. Ranns; Jesper Skriver
- Web page: https://patentgrep.com/patent/US20200287733A1

## CPC

- H04L 12/18: for broadcast or conference {, e.g. multicast}
- H04L 12/1886: {with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains}
- H04L 45/16: Multipoint routing
- H04L 45/74: Address processing for routing
- H04L 45/18: Loop-free operations
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 1

A method performed by a node in a network of nodes, the method comprising:
receiving a packet comprising a top label;
determining whether the top label is associated with a BIER enabled node;
in response to determining that the top label is associated with a BIER node, determining a first next-hop neighbor node;
determining whether the first next-hop neighbor node is a BIER enabled node;
in response to determining the first next-hop neighbor node is not a BIER enabled node:
adding a label to the packet, wherein the added label corresponds to label switched path (LSP) between the node an egress node of the network;
forwarding the packet with the added label to the first next-hop neighbor node.

### Claim 2 (depends on 1)

The method of claim 1 further comprising:
in response to determining that the top label is associated with a BIER node, determining a second next-hop neighbor node;
determining whether the second next-hop neighbor node is a BIER enabled node;
in response to determining the second next-hop neighbor node is a BIER enabled node:
selecting a bit forwarding table;
selecting a row as a selected row in the bit forwarding table, wherein the selected row is selected based, at least in part, on a bit position value corresponding to a first set bit in a packet bit mask (PBM) of the packet;
copying the packet to create a copied packet;
replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and
forwarding the copied packet to the second next-hop neighbor node, wherein the forwarding is based, at least in part, on the routing label.

### Claim 3 (depends on 2)

The method of claim 2 further comprising
prior to forwarding the copied packet, modifying the copy of the PBM of the copied packet by clearing one or more bits that had been set in the packet.

### Claim 4 (depends on 2)

The method of claim 2, wherein the selected row comprises:
a bit mask value,
information identifying the second next-hop neighbor node, and
the routing label associated with the second next-hop neighbor node.

### Claim 5 (depends on 1)

The method of claim 1 further comprising:
in response to determining the first next-hop neighbor node is not a BIER enabled node:
identifying a BIER-enabled node along a shortest path towards the egress node.

### Claim 6 (depends on 1)

The method of claim 1 further comprising:
the first next-hop neighbor node receiving the packet with the added label;
the first next-hop neighbor removing the top label from the packet it receives;
the first next-hop neighbor forwards the packet to a neighbor node after removing the top label.

### Claim 7 (depends on 6)

The method of claim 6 further comprising:
the neighbor node receiving the packet from the first next-hop neighbor node;
the neighbor node determining whether the router label of the packet it receives is associated with another BIER enabled node;
in response to determining that the router label is associated with another BIER node, the neighbor node accessing its bit forwarding table using the router label contained in the packet received from the first next-hop neighbor node.

### Claim 8 (depends on 6)

The method of claim 6 further comprising the first next-hop neighbor adding another label to the packet after the first next-hop neighbor removes the top label and before the first next-hop neighbor forwards the packet to the neighbor node.

### Claim 9 (depends on 1)

The method of claim 1, wherein the determining the first next-hop neighbor node comprises:
accessing a bit forwarding table using the top label and a packet bit mask (PBM) contained in the packet;
wherein the first next-hop neighbor node is mapped in an entry of the bit forwarding table to a set bit in the PBM.

### Claim 10 (depends on 9)

The method of claim 9 wherein each bit in the PBM is mapped to a respective egress node of the network.

### Claim 11

A node comprising:
one or more network interface cards;
a memory configured to store instructions; and
a processor configured to perform a method in response to executing the instructions stored in the memory, the method comprising:
in response to the node receiving a packet comprising a top label, determining whether the top label is associated with a BIER enabled node;
in response to determining that the top label is associated with a BIER node, determining a first next-hop neighbor node;
determining whether the first next-hop neighbor node is a BIER enabled node;
in response to determining the first next-hop neighbor node is not a BIER enabled node:
adding a label to the packet, wherein the added label corresponds to label switched path (LSP) between the node an egress node of a network in which the node and the egress node are contained;
forwarding the packet with the added label to the first next-hop neighbor node.

### Claim 12 (depends on 11)

The node of claim 11 wherein the method further comprises:
in response to determining that the top label is associated with a BIER node, determining a second next-hop neighbor node;
determining whether the second next-hop neighbor node is a BIER enabled node;
in response to determining the second next-hop neighbor node is a BIER enabled node:
selecting a bit forwarding table;
selecting a row as a selected row in the bit forwarding table, wherein the selected row is selected based, at least in part, on a bit position value corresponding to a first set bit in a packet bit mask (PBM) of the packet;
copying the packet to create a copied packet;
replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and
forwarding the copied packet to the second next-hop neighbor node, wherein the forwarding is based, at least in part, on the routing label.

### Claim 13 (depends on 12)

The node of claim 12 wherein the method further comprises:
prior to forwarding the copied packet, modifying the copy of the PBM of the copied packet by clearing one or more bits that had been set in the packet.

### Claim 14 (depends on 12)

The node of claim 12, wherein the selected row comprises:
a bit mask value,
information identifying the second next-hop neighbor node, and
the routing label associated with the second next-hop neighbor node.

### Claim 15 (depends on 11)

The node of claim 11, wherein the method further comprises:
in response to determining the first next-hop neighbor node is not a BIER enabled node:
identifying a BIER-enabled node along a shortest path towards the egress node.

### Claim 16 (depends on 11)

The node of claim 11, wherein the determining the first next-hop neighbor node comprises:
accessing a bit forwarding table using the top label and a packet bit mask (PBM) contained in the packet;
wherein the first next-hop neighbor node is mapped in an entry of the bit forwarding table to a set bit in the PBM.

### Claim 17 (depends on 16)

The node of claim 16 wherein each bit in the PBM is mapped to a respective egress node of the network.

### Claim 18

A system comprising
a node configured to perform a method comprising:
in response to the node receiving a packet comprising a top label, determining whether the top label is associated with a BIER enabled node;
in response to determining that the top label is associated with a BIER node, determining a first next-hop neighbor node;
determining whether the first next-hop neighbor node is a BIER enabled node;
in response to determining the first next-hop neighbor node is not a BIER enabled node:
adding a label to the packet, wherein the added label corresponds to label switched path (LSP) between the node an egress node of a network in which the node and the egress node are contained;
forwarding the packet with the added label to the first next-hop neighbor node.

### Claim 19 (depends on 18)

The system of claim 18 wherein the method further comprises:
in response to determining that the top label is associated with a BIER node, determining a second next-hop neighbor node;
determining whether the second next-hop neighbor node is a BIER enabled node;
in response to determining the second next-hop neighbor node is a BIER enabled node:
selecting a bit forwarding table;
selecting a row as a selected row in the bit forwarding table, wherein the selected row is selected based, at least in part, on a bit position value corresponding to a first set bit in a packet bit mask (PBM) of the packet;
copying the packet to create a copied packet;
replacing the top label in the copied packet with the routing label from the selected row of the bit forwarding table; and
forwarding the copied packet to the second next-hop neighbor node, wherein the forwarding is based, at least in part, on the routing label.

### Claim 20 (depends on 18)

The system of claim 18 wherein the method further comprises, in response to determining the first next-hop neighbor node is not a BIER enabled node, identifying a BIER-enabled node along a shortest path towards the egress node.
