Bit index explicit replication forwarding using replication cache

• US 9,832,031 B2
• Filed: 10/23/2015
• Issued: 11/28/2017
• Est. Priority Date: 10/24/2014
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Zhao, Katherine, Yong, Lucy
• Primary Examiner(s): Hsu, Alpus H
• Application Number:
  US14/921,835
• Publication Number:
  US 20160119159A1
• Time in Patent Office: 767 Days
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop

Abstract

A data packet forwarding method including receiving, by a network node, a data packet that comprises a bit string, a BFIR identifier (ID), and a multicast replication path (MRP) ID, wherein the BFIR ID identifies an ingress network node for a multicast group, and wherein the MRP ID identifies the multicast group, identifying an entry in a BIER Replication Path Cache Table (BRCT) using the BFIR ID and the MRP ID, wherein the entry identifies a replication neighbor (NBR) list associated with the BFIR ID and the MRP ID, and forwarding the data packet in accordance with the replication NBR list.

Claims

1. A data packet forwarding method comprising:

receiving, by a network node, a data packet that comprises a bit string, a Bit Index Explicit Replication (BIER) forwarding ingress router (BFIR) identifier (ID), and a multicast replication path (MRP) ID, wherein the BFIR ID identifies an ingress network node for a multicast group, and wherein the MRP ID identifies the multicast group;

computing, by the network node, a set of next hops and an updated bit string based on the bit string and a replication neighbor (NBR) list;

updating, by the network node, an entry in a BIER Replication Path Cache Table (BRCT) employed in the network node using the BFIR ID and the MRP ID, wherein the entry identifies the replication NBR list associated with the BFIR ID and the MRP ID; and

forwarding, by the network node, the data packet with the updated bit string to each next hop.

2. The method of claim 1, wherein the replication NBR list identifies one or more next-hop network nodes, and wherein forwarding the data packet comprises sending the data packet to the one or more next-hop network nodes.

3. The method of claim 1, further comprising generating, by the network node, a new entry using the BFIR ID and the MRP ID in the BRCT when the entry in the BRCT does not exist.

4. The method of claim 1, further comprising setting, by the network node, an entry expire timer for the entry.

5. The method of claim 4, further comprising removing, by the network node, the entry when the entry expire timer expires.

6. The method of claim 1, further comprising creating, by the network node, the replication NBR list for the entry using the bit string.

7. The method of claim 1, further comprising creating, by the network node, the entry in the BRCT when the entry in the BRCT does not exist.

8. A data packet forwarding method comprising:

receiving, by a network node, a control packet that comprises a bit string, a Bit Index Explicit Replication (BIER) forwarding ingress router (BFIR) identifier (ID), and a multicast replication path (MRP) ID, wherein the BFIR ID identifies an ingress network node for a multicast group, wherein the MRP ID identifies the multicast group, and wherein the control packet does not comprise a multicast payload;

generating, by the network node, an entry in a BIER Replication Path Cache Table (BRCT) employed in the network node using the BFIR ID and the MRP ID, wherein the entry identifies a replication neighbor (NBR) list associated with the BFIR ID and the MRP ID;

receiving, by a network node, a data packet that comprises the MRP ID; and

forwarding, by the network node, the data packet in accordance with the entry in the BRCT.

9. The method of claim 8, further comprising, by the network node, creating the replication NBR list for the entry using the bit string.

10. The method of claim 8, wherein forwarding the data packet does not modify the bit string.

11. The method of claim 8, further comprising setting, by the network node, an entry expire timer for the entry.

12. The method of claim 11, further comprising removing, by the network node, the entry when the entry expire timer expires.

13. The method of claim 8, further comprising forwarding, by the network node, the control packet, wherein the control packet is forwarded in a control plane, and wherein the data packet is forwarded in a data plane.

14. A data packet forwarding method comprising:

obtaining, by a network node, a Bit Index Explicit Replication (BIER) forwarding ingress router (BFIR) identifier (ID) and a multicast replication path (MRP) ID, wherein the BFIR ID identifies an ingress network node for a multicast group, and wherein the MRP ID identifies the multicast group;

generating, by the network node, an index for an entry in a BIER Replication Path Cache Table (BRCT) employed in the network node using the BFIR ID and the MRP ID; and

generating, by the network node, the entry in the BRCT that comprises the index and a replication neighbor (NBR) list associated with the index, wherein the replication NBR list identifies one or more next-hop network nodes.

15. The method of claim 14, wherein obtaining the BFIR ID and the MRP ID comprises processing a header for a BIER packet.

16. The method of claim 15, further comprising creating, by the network node, the replication NBR list using a bit string in the header for the BIER packet.

17. The method of claim 14, wherein generating the index comprises concatenating the BFIR ID and the MRP ID.

18. The method of claim 14, wherein obtaining the MRP ID comprises generating the MRP ID for the multicast group.

19. The method of claim 14, further comprising setting, by the network node, an entry expire timer for the entry.

20. The method of claim 19, further comprising removing, by the network node, the entry when the entry expire timer expires.