Bit Indexed Explicit Replication and the BGP Extensions for BIER

In this article we’ll take a look at the architecture for multicast forwarding called the Bit Indexed Explicit Replication or simply BIER. However, we’ll need to discuss the theory behind the multicast operation first in order to understand BIER benefits later.

Multicast Fundamentals

Multicast transmission is effective for one-to-many or many-to-many communication. Receivers that want to receive multicast traffic join the Multicast Group (MG) so they become its members. Every receiver that joins the MG receives a multicast packet sent to the multicast IP address.

Each MG is identified by the multicast IP address assigned from the Class D address range: 224.0.0.0 to 239.255.255.255. The multicast IP address is an additional address to the interface address that is assigned dynamically. If an application is terminated, the multicast IP address is dynamically released. After the receivers join the MG, the network builds a routing path so that a receiver can get data sent to the MG. The routing path represents a dynamically built spanning-tree.

IP Multicast to Ethernet Multicast  Address Mapping

The last twenty-three bits from the IP multicast address are mapped to the last twenty-three bits of the 48bit MAC multicast address 01:00:5e:00:00:00. The 24th bit is set to 0 in the Ethernet multicast address.

For instance, an IP multicast address 239.100.100.10 is mapped as 01:00:5e:64:64:0A. The first 4 bits (1110) define the class D multicast address (224-239). From the remaining 28 definable bits of an IP multicast address, only 23 bits go into the Ethernet multicast address. The remaining 5 bits create 32 different IP multicast addresses that are mapped to the same Ethernet address. In other words, 32 IP multicast addresses can be mapped to a single Ethernet Multicast address.

IP Group Management Protocol (IGMP)

IGMP is used to dynamically register individual hosts in a multicast group on a particular LAN. Hosts identify group memberships by sending IGMP messages to their upstream local multicast router. Routers listen to IGMP messages and periodically send out queries to discover which groups are active or inactive on a particular subnet (IGMPv1). Hosts can send request for leaving the MG (IGMPv2).

IGMP is not an IP multicast routing protocol that finds an optimal path for multicast traffic sent by a sender to a multicast IP address. There are three major multicast routing protocols. Distance Vector Multicast Routing Protocol (DVMRP), Multicast Open Shortest Path First (MOSPF) and Protocol Independent Multicast (PIM). A multicast enabled router uses one of them.

Multicast Routing Protocols

Multicast routing is about building the forwarding trees from the sender to a group of receivers. There is only one path between every pair of routers, and the path is loop-free. There are two approaches to building the trees:

1. Source-based tree – spanning-tree is built from the receiver to the sender for each sender. This approach assumes that the group members are densely distributed throughout the network and almost all hosts in the network are members of the MG. Network is periodically flooded with multicast traffic, however it has enough capacity to deal with it. A good example of this multicast protocol is the Protocol Independent Multicast – Dense Mode (PIM-DM).

2. Core-based tree – one router is selected as the core or Rendezvous Point (RP) and all the receivers build the shortest path to the core. The tree is shared by all senders. This concept assumes that members of the MG are sparsely distributed throughout the network and bandwidth is not necessarily widely available. The example of this multicast protocol is the PIM Sparse Mode (PIM-SM).

Multicast Using Bit Index Explicit Replication (BIER)

BIER is the new architecture for forwarding multicast traffic published in RFC8279. Rather than building multicast forwarding trees, the multicast packets are encapsulated into a BIER header and are forwarded within BIER domain based on the information in the header. Thanks to BIER header, multicast is not sent to the nodes that do not need to receive the multicast traffic. Therefore, multicast  follows an optimal path within the BIER domain. No transit nodes maintaining the per-flow state or the multicast tree-building protocols are needed.

BIER Domain

BFR domain consists of the Bit-Forwarding Routers (BFRs) having specific functions. For instance, the BFR transit node for a packet receives a multicast data packet from another BFR in the same BIER domain, and forwards the packet to a different BFR in the same BIER domain.

Bit-Forwarding Ingress Router (BFIR) sits at the edge of BIER multicast domain. It represents a point at which the multicast data enters BIER domain. BFIR pushes BIER header onto the packet.

Bit-Forwarding Egress Routers (BFERs) are the points where the multicast leaves BIER domain. BFER removes BIER header before it leaves BIER domain.

Note: BFR may represent BFIR for some multicast traffic while also being a BFER for some multicast traffic and a transit BFR for other multicast traffic.

 

Picture 1: BIER Domain

---

BFR Identification (BFR-ID)

BFIRs and BFERs routers in BIER domain are identified by the BFR-ID. It is a small positive integer. Think of the BFR-ID as an address of BFIR or BFER.

BFR Prefix

Each BFR has an assigned BFR prefix. It is a reachable IP address of a BFR router in BIER domain, preferably a loopback IP address. BFR prefixes are propagated by the IGP or BGP protocol along with the unique BFR-IDs.

BFIR Operation

Once a multicast packet enters BIER domain, BFIR determines the set of BFERs to which it sends the multicast data. It is BIER header which carries the information about the set of listeners that agreed to receive the multicast traffic. More specifically, the header contains a structure called BitString. Each bit position inside a BitString corresponds to a specific BFER. In other words, the BFIR sets that bit if the corresponding BFER should receive the multicast packet.

BitString Length

The length of the BitString in BIER header determines a number of BFERs to which a given multicast packet can be forwarded. String size can be 256, 512, 2048Bits. A string length of 1024bits can accommodate 1024 BFERs.

Set Identifier (SI)

SI along with the BitString determines the set of BFERs to which a packet will be delivered. SI is helpful when the number of BFERs is higher than the BitStringLength. Let’s say BFIR needs to send a packet to BFERs 12, 100 and 257 in subdomain 0 while the BitString length is 256. In this case, BFIR encapsulates the packet with the SI set to zero and the bits 12, 100 of the BitString set. All other bits are clear. BFIR also creates a second copy of the multicast packet with the SI set to 1 and with bits 1 of the BitString set. All other bits are clear.

Subdomain ID

A BIER domain contains at least one sub-domain that is called the default-subdomain (sub-domain 0). If there are more sub-domains in BIER domain, Each sub-domain is identified by a sub-domain-id in the range (0,255). BFR needs to know a set of the sub-domains to which it belongs.

Transit BFR Operation

Transit BFR receives a multicast packet from BFIR with multicast traffic encapsulated inside BIER header. The header contains the BitString with a certain bits set so that particular BFERs are reliably identified. BFR replicates the multicast packets to the particular BFR neighbors (BFR-NBR) based on the bit position inside the BitString. Eventually, multicast packets reach BFERs that remove BIER header and forward multicast to receivers. The transit BFR clears certain bits inside the BitString based on the Bit Index Forwarding Table (BIFT). This ensures that BFERs receive only one copy of the packet.

Bit Index Routing Table (BIRT)

The BIRT is a table that maps the BFR-ID of a BFER to the BFR-prefix of the BFER and to the BFR-NBR on the path to that BFER.

Picture 2:  BIER Topology

---

Having a network topology depicted on the Picture 2, the BIRT for BFR-B is:

BFR-ID (SI:BitString)	BFR-Prefix of the BFER	BFR-NBR
4 (0:1000)	A	A
1 (0:0001)	D	C
3 (0:0100)	E	E
2 (0:0010)	F	C

Table 1: Bit Index Routing Table at BFR-B

---

Note: Set identifier (SI) is set to 0 for all BFRs. The BFIR-A has BFR-ID set to 4, BFR-E has BFR-ID set to 3 etc.

 

Bit Index Forwarding Table (BIFT)

The BIFT is derived from the BIRT and is used to forward the packets. BIFT holds the next-hop information for every possible BFER destination. BFR-IDs with the same SI that can be reached via the same next-hop share the same Forwarding Bit Mask (F-BM). The mask is created on BFRs, applying logical OR between all BFR-IDs reachable using the same next-hop. For instance, F-BM for both FBER-D and FBER-F is 0011 on transit FBR-B, created by boolean OR between BFR-IDs 00001 (BFER-D) and 0010 (BFER-F).

BFR-ID (SI:BitString)	F-BM	BFR-NBR
1 (0:0001)	0011	C
2 (0:0010)	0011	C
3 (0:0100)	0100	E
4 (0:1000)	1000	A

Table 2: Bit Index Forwarding Table at BFR-B

---

BIER Forwarding

Suppose that BFIR-A has learned from the multicast flow overlay (by MVPN signaling) that both BFER-E and BFER-D are interested in receiving the multicast. BFIR-A encapsulates a packet to BIER header, setting BitString to 0101 that corresponds with the BFER-D (bit 1) and BFER-E (bit 3). BFIR-A sends the packet to BFR-B.

BFR-B determines the packet’s SI, BitStringLength, and the sub-domain. BFR-B finds that the first bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-B determines that the bit mask F-BM is 0011 and the BFR-NBR is BFR-C. BFR-B then makes a copy of the packet and applies the F-BM to the copy performing AND between the BitString 0101 and F-BM 0011. The copy’s BitString is now 0001. BRF-B sends a copy to BFR-C.

BFR-B then updates the packet’s BitString by applying the inverse of the F-BM (1100) and performs AND between invers eF-BM 1100 and Bitstring 0101. The result is 0100. BFR-B finds the next bit in the packet’s modified BitString. It is bit 3. Looking at entry 3 in its BIFT, BFR-B determines that the F-BM is 0100 and the BFR-NBR is BFR-E. BFR-B then makes a copy of the packet and performs AND between the F-BM 0100 and BitString 0100. The copy’s BitString is now 0100. BFR-B sends a copy to BFR-E. BFR-B then updates the packet’s BitString by applying boolean AND between the inverse of the F-BM (1011) and Bitstring 0100. The result is 0000. As the packet’s BitString is now zero, the forwarding procedure is complete.

One copy of the packets reaches BFER-E with BRF-ID 0100. The other copy sent towards BFR-C has a BitString set to 0001. BFR-C will forward the packet to BFER-D. At BFER-D, the BIFT entry for BFR-ID 1 will specify an F-BM of 0001 and a BFR-NBR of BFR-D itself. This will cause a copy of the packet to be delivered to the multicast flow overlay at BFR-D. The packet’s BitString will be set to 0000, and the packet will not be forwarded any further.

BGP Extensions for BIER

BGP Extensions for BIER are defined in I-E 005. The draft presents a new optional transitive BGP attribute, referred to as BIER attribute. This attribute carries BIER-specific information such as BFR-ID and the BitString Length. BIER attribute is attached to a BGP UPDATE message by the originator. If BIER path attribute is present, the NLRI is treated by BIER as a BFR-prefix. When creating a BIER attribute the BFR needs to include one BIER TLV for every <Sub-domain, BFR-ID> pair that it supports. Since BIER attribute is an optional transitive BGP path attribute, a non-BFR BGP speakers could still advertise the received route with a BIER attribute.

---

Conclusion:
BIER simplifies multicast operation as no dedicated multicast control protocol for BIER is needed while the existing protocols such as IGP (IS-IS, OSPF) or BGP can be leveraged. BIER uses new type of the forwarding lookup (Bit Index Forwarding Table). It can be implemented by software or hardware changes. Moreover, BIER has the support of big network vendors so it can completely change multicast operation in the future.