Explicit block encoding of multicast group membership information with bit index explicit replication (bier)

Patent metadata

Field	Value
Publication number	US-2016127142-A1
Application number	US-201514596110-A
Country	US
Kind code	A1
Filing date	Jan 13, 2015
Priority date	Nov 4, 2014
Publication date	May 5, 2016
Grant date	—

Abstract

A network device executes a method to forward a packet that is encoded using an explicit block encoding of multicast group membership information with Bit Index Explicit Replication. The method includes receiving a packet, where the packet includes a bitstring having a set of blocks, each block including a set identifier field and a SubBitString field. The method further includes selecting a block for processing, finding a first bit position of a SubBitString identifying a destination bit-forwarding router (BFR), looking up a forwarding bitmask for the destination BFR and a next-hop to reach the destination BFR in a bit index forwarding table, creating a copy of the packet, applying a bit-wise AND operation on the copy of the packet with the forwarding bitmask, forwarding the copy of the packet to the next-hop, and applying a bit-wise AND operation on the packet with an inverse of the forwarding bitmask.

First claim

1 . A method implemented by a network device to forward a packet that is encoded using an explicit block encoding of multicast group membership information with Bit Index Explicit Replication (BIER), the method comprising the steps of:
receiving a packet, wherein the packet includes a bitstring having a set of blocks, each block including a set identifier (SI) field and a SubBitString field; selecting an unprocessed block from the set of blocks for processing; finding a first bit position of a SubBitString of the selected block, wherein the first bit position identifies a destination bit-forwarding router (BFR); looking up a forwarding bitmask for the destination BFR and a next-hop neighbor to reach the destination BFR in a bit index forwarding table (BIFT); creating a copy of the packet; applying a bit-wise AND operation on a bitstring of the copy of the packet with the forwarding bitmask; forwarding the copy of the packet to the next-hop neighbor; and applying a bit-wise AND operation on the bitstring of the packet with an inverse of the forwarding bitmask.

2 . The method of claim 1 , wherein the BIFT maintains a mapping of a BFR-id of the destination BFR to a corresponding forwarding bitmask and a next-hop neighbor to reach the destination BFR.

3 . The method of claim 2 , further comprising:
determining the BFR-id of the destination BFR based on the found first bit position of the SubBitString of the selected block.

4 . The method of claim 3 , wherein the BFR-id is given by SI*SubBitStringLength+index, where SI is a value in the SI field of the selected block, SubBitStringLength is a length of the SubBitString field, and index is the found first bit position of the SubBitString of the selected block.

5 . The method of claim 1 , wherein the bit-wise AND operation on the bitstring of the copy of the packet is applied on each SubBitString of the copy of the packet with a portion of the forwarding bitmask that corresponds to that SubBitString.

6 . The method of claim 1 , wherein the bit-wise AND operation on the bitstring of the packet is applied on each SubBitString of the packet with a portion of the inversed forwarding bitmask that corresponds to that SubBitString.

7 . The method of claim 1 , further comprising:
applying bit inversion to the forwarding bitmask to obtain the inversed forwarding bitmask.

8 . The method of claim 1 , further comprising:
checking whether the SubBitString is equal to zero; and finding a next first bit position of the SubBitString in response to determining that the SubBitString is not equal to zero.

9 . The method of claim 1 , further comprising:
checking whether all of the blocks of the bitstring of the packet have been processed; and selecting a next unprocessed block in response to determining that not all of the blocks of the bitstring of the packet have been processed.

10 . A network device configured to forward a packet that is encoded using an explicit block encoding of multicast group membership information with Bit Index Explicit Replication (BIER), the network device comprising:
a non-transitory machine readable medium to store a BIER module; and a network processor communicatively coupled to the non-transitory machine readable medium, the network processor configured to execute the BIER module, wherein the BIER module is configured to receive a packet that includes a bitstring having a set of blocks, each block including a set identifier (SI) field and a SubBitString field, select an unprocessed block from the set of blocks for processing, find a first bit position of a SubBitString of the selected block, where the first bit position identifies a destination bit-forwarding router (BFR), look up a forwarding bitmask for the destination BFR and a next-hop neighbor to reach the destination BFR in a bit index forwarding table (BIFT), create a copy of the packet, apply a bit-wise AND operation on a bitstring of the copy of the packet with the forwarding bitmask, forward the copy of the packet to the next-hop neighbor, and apply a bit-wise AND operation on the bitstring of the packet with an inverse of the forwarding bitmask.

11 . A non-transitory machine readable storage medium having stored therein instructions to be executed by a network device to forward a packet that is encoded using an explicit block encoding of multicast group membership information with Bit Index Explicit Replication (BIER), the instructions when executed by the network device cause the network device to perform a set of operations comprising:
receiving a packet, wherein the packet includes a bitstring having a set of blocks, each block including a set identifier (SI) field and a SubBitString field; selecting an unprocessed block from the set of blocks for processing; finding a first bit position of a SubBitString of the selected block, wherein the first bit position identifies a destination bit-forwarding router (BFR); looking up a forwarding bitmask for the destination BFR and a next-hop neighbor to reach the destination BFR in a bit index forwarding table (BIFT); creating a copy of the packet; applying a bit-wise AND operation on a bitstring of the copy of the packet with the forwarding bitmask; forwarding the copy of the packet to the next-hop neighbor; and applying a bit-wise AND operation on the bitstring of the packet with an inverse of the forwarding bitmask.

12 . The non-transitory machine readable storage medium of claim 11 , wherein the BIFT maintains a mapping of a BFR-id of the destination BFR to a corresponding forwarding bitmask and a next-hop neighbor to reach the destination BFR.

13 . The non-transitory machine readable storage medium of claim 12 , wherein the instructions when executed by the network device cause the network device to perform a further set of operations comprising:
determining the BFR-id of the destination BFR based on the found first bit position of the SubBitString of the selected block.

14 . The non-transitory machine readable storage medium of claim 13 , wherein the BFR-id is given by SI*SubBitStringLength+index, where SI is a value in the SI field of the selected block, SubBitStringLength is a length of the SubBitString field, and index is the found first bit position of the SubBitString of the selected block.

15 . The non-transitory machine readable storage medium of claim 11 , wherein the bit-wise AND operation on the bitstring of the copy of the packet is applied on each SubBitString of the copy of the packet with a portion of the forwarding bitmask that corresponds to that SubBitString.

16 . The non-transitory machine readable storage medium of claim 11 , wherein the bit-wise AND operation on the bitstring of the packet is applied on each SubBitString of the packet with a portion of the inversed forwarding bitmask that corresponds to that SubBitString.

17 . The non-transitory machine readable storage medium of claim 11 , wherein the instructions when executed by the network device cause the network device to perform a further set of operations comprising:
applying bit inversion to the forwarding bitmask to obtain the inversed forwarding bitmask.

18 . The non-transitory machine readable storage medium of claim 11 , wherein the instructions when executed by the network device cause the network device to perform a further set of operations comprising:
checking whether the SubBitString is equal to zero; and finding a next first bit position of the SubBitString in response to determining that the SubBitString is not equal to zero.

19

Assignees

• Ericsson Telefon Ab L M

Inventors

• Tian Albert Jining
• Lakshmikanthan Ramanathan
• Tantsura Evgeny

Classifications

• H04L12/1886 Primary

  with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains · CPC title

• H04L45/74

  Address processing for routing · CPC title

• H04L45/50 Primary

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L12/18

  for broadcast or conference {, e.g. multicast} · CPC title

• H04L45/60

  Router architectures · CPC title