RFC 8279
Multicast Using Bit Index Explicit Replication (BIER)
Pages: 43
Proposed Standard
Proposed Standard
Part 2 of 3 – Pages 13 to 29
5. Advertising BFR-ids and BFR-Prefixes
As stated in Section 2, each BFER is assigned (by provisioning) a BFR-id (for a given BIER sub-domain). Each BFER must advertise these assignments to all the other BFRs in the domain. Similarly, each BFR is assigned (by provisioning) a BFR-prefix (for a given BIER domain) and must advertise this assignment to all the other BFRs in the domain. Finally, each BFR has been provisioned to use a certain set of Disposition BitStringLengths for each sub-domain and must advertise these to all other BFRs in the domain.
If the BIER domain is also a link-state routing IGP domain (i.e., an OSPF or IS-IS domain), the advertisement of the BFR-prefix, <sub-domain-id, BFR-id>, and BitStringLength can be done using the advertisement capabilities of the IGP. For example, if a BIER domain is also an OSPF domain, these advertisements can be done using the OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism. Details of the necessary extensions to OSPF and IS-IS will be provided in companion documents. (See [OSPF_BIER_EXTENSIONS] and [ISIS_BIER_EXTENSIONS].) If, in a particular deployment, the BIER domain is not an OSPF or IS-IS domain, procedures suitable to the deployment must be used to advertise this information. Details of the necessary procedures will be provided in companion documents. For example, if BGP is the only routing algorithm used in the BIER domain, the procedures of [BGP_BIER_EXTENSIONS] may be used. These advertisements enable each BFR to associate a given <sub-domain-id, BFR-id> with a given BFR-prefix. As will be seen in subsequent sections of this document, knowledge of this association is an important part of the forwarding process. Since each BFR needs to have a unique (in each sub-domain) BFR-id, two different BFRs will not advertise ownership of the same <sub-domain-id, BFR-id> unless there has been a provisioning error. o If BFR-A determines that BFR-B and BFR-C have both advertised the same BFR-id for the same sub-domain, BFR-A MUST log an error. Suppose that the duplicate BFR-id is "N". When BFR-A is functioning as a BFIR, it MUST NOT encode the BFR-id value N in the BIER encapsulation of any packet that has been assigned to the given sub-domain, even if it has determined that the packet needs to be received by BFR-B and/or BFR-C. This will mean that BFR-B and BFR-C cannot receive multicast traffic at all in the given sub-domain until the provisioning error is fixed. However, that is preferable to having them receive each other's traffic. o Suppose that BFR-A has been provisioned with BFR-id N for a particular sub-domain but that it has not yet advertised its ownership of BFR-id N for that sub-domain. Suppose also that it has received an advertisement from a different BFR (say BFR-B) that is advertising ownership of BFR-id N for the same sub-domain. In such a case, BFR-A SHOULD log an error and MUST NOT advertise its own ownership of BFR-id N for that sub-domain as long as the advertisement from BFR-B is extant.
This procedure may prevent the accidental misconfiguration of a
new BFR from impacting an existing BFR.
If a BFR advertises that it has a BFR-id of 0 in a particular
sub-domain, other BFRs receiving the advertisement MUST interpret
that advertisement as meaning that the advertising BFR does not have
a BFR-id in that sub-domain.
6. BIER Intra-Domain Forwarding Procedures
This section specifies the rules for forwarding a BIER-encapsulated
data packet within a BIER domain. These rules are not intended to
specify an implementation strategy; to conform to this specification,
an implementation need only produce the same results that these rules
produce.
6.1. Overview
This section provides a brief overview of the BIER forwarding
procedures. Subsequent subsections specify the procedures in more
detail.
To forward a BIER-encapsulated packet:
1. Determine the packet's sub-domain.
2. Determine the packet's BitStringLength and BitString.
3. Determine the packet's SI.
4. From the sub-domain, the SI, and the BitString, determine the set
of destination BFERs for the packet.
5. Using information provided by the routing underlay associated
with the packet's sub-domain, determine the next-hop adjacency
for each of the destination BFERs.
6. It is possible that the packet's BitString will have one or more
bits that correspond to BFR-ids that are not in use. It is also
possible that the packet's BitString will have one or more bits
that correspond to BFERs that are unreachable, i.e., that have no
next-hop adjacency. In the following, we will consider the
"next-hop adjacency" for all such bit positions to be the "null"
next hop.
7. Partition the set of destination BFERs such that all the BFERs in
a single partition have the same next hop. We will say that each
partition is associated with a next hop.
8. For each partition:
a. Make a copy of the packet.
b. Clear any bit in the packet's BitString that identifies a
BFER that is not in the partition.
c. Transmit the packet to the associated next hop. (If the
next hop is the null next hop, the packet is discarded.)
If a BFR receives a BIER-encapsulated packet whose <sub-domain, SI,
BitString> triple identifies that BFR itself, then the BFR is also a
BFER for that packet. As a BFER, it must pass the payload to the
multicast flow overlay. If the BitString has bits set for other
BFRs, the packet also needs to be forwarded further within the BIER
domain. If the BF(E)R also forwards one or more copies of the packet
within the BIER domain, the bit representing the BFR's own BFR-id
MUST be clear in all the copies.
When BIER on a BFER is to pass a packet to the multicast flow
overlay, it of course decapsulates the packet by removing the BIER
header. However, it may be necessary to provide the multicast flow
overlay with contextual information obtained from the BIER
encapsulation. The information that needs to pass between the BIER
layer and the multicast flow overlay is specific to the multicast
flow overlay. Specification of the interaction between the BIER
layer and the multicast flow overlay is outside the scope of this
specification.
If the BIER encapsulation contains a "Time to Live" (TTL) value, this
value is not, by default, inherited by the payload. If a particular
multicast flow overlay needs to know the TTL value, this needs to be
specified in whatever specification defines the interaction between
BIER and that multicast flow overlay.
If the BIER encapsulation contains a Traffic Class field, a
Type of Service field, a Differentiated Services field, or any field
of that sort, the value of that field is not, by default, passed to
the multicast flow overlay. If a particular multicast flow overlay
needs to know the values of such fields, this fact needs to be
specified in whatever specification defines the interaction between
BIER and that multicast flow overlay.
When BIER on a BFER passes a packet to the multicast flow overlay,
the overlay will determine how to further dispatch the packet. If
the packet needs to be forwarded into another BIER domain, then the
BFR will act as a BFER in one BIER domain and as a BFIR in another.
A BIER-encapsulated packet cannot pass directly from one BIER domain to another; at the boundary between BIER domains, the packet must be decapsulated and passed to the multicast flow overlay. Note that when a BFR transmits multiple copies of a packet within a BIER domain, only one copy will be destined to any given BFER. Therefore, it is not possible for any BIER-encapsulated packet to be delivered more than once to any BFER.6.2. BFR Neighbors
The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those BFRs that, according to the routing underlay, are adjacencies of BFR-A. Each BFR-NBR will have a BFR-prefix. Suppose a BIER-encapsulated packet arrives at BFR-A. From the packet's encapsulation, BFR-A learns (a) the sub-domain of the packet and (b) the BFR-ids (in that sub-domain) of the BFERs to which the packet is destined. Then, using the information advertised per Section 5, BFR-A can find the BFR-prefix of each destination BFER. Given the BFR-prefix of a particular destination BFER, say BFER-D, BFR-A learns from the routing underlay (associated with the packet's sub-domain) an IP address of the BFR that is the next hop on the path from BFR-A to BFER-D. Let's call this next hop "BFR-B". BFR-A must then determine the BFR-prefix of BFR-B. (This determination can be made from the information advertised per Section 5.) This BFR-prefix is the BFR-NBR of BFR-A on the path from BFR-A to BFER-D. Note that if the routing underlay provides multiple equal-cost paths from BFR-A to BFER-D, BFR-A may have multiple BFR-NBRs for BFER-D. Under certain circumstances, a BFR may have adjacencies (in a particular routing underlay) that are not BFRs. Please see Section 6.9 for a discussion of how to handle those circumstances.
6.3. The Bit Index Routing Table
The "Bit Index Routing Table" (BIRT) is a table that maps from the BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of that BFER, and to the BFR-NBR on the path to that BFER. As an example, consider the topology shown in Figure 1. In this diagram, we represent the BFR-id of each BFR in the SI:xyzw form discussed in Section 3. ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D ) 4 (0:1000) \ \ 1 (0:0001) \ \ ( E ) ( F ) 3 (0:0100) 2 (0:0010) Figure 1: BIER Topology 1 This topology will result in the BIRT of Figure 2 at BFR-B. The first column shows the BFR-id as a number and also (in parentheses) in the SI:BitString format that corresponds to a BitStringLength of 4. (The actual minimum BitStringLength is 64, but we use 4 in the examples.) Note that a BIRT is specific to a particular BIER sub-domain. -------------------------------------------- | BFR-id | BFR-Prefix | BFR-NBR | | (SI:BitString) | of Dest BFER | | ============================================ | 4 (0:1000) | A | A | -------------------------------------------- | 1 (0:0001) | D | C | -------------------------------------------- | 3 (0:0100) | E | E | -------------------------------------------- | 2 (0:0010) | F | C | -------------------------------------------- Figure 2: Bit Index Routing Table at BFR-B
6.4. The Bit Index Forwarding Table
The "Bit Index Forwarding Table" (BIFT) is derived from the BIRT as follows. (Note that a BIFT is specific to a particular sub-domain.) Suppose that several rows in the BIRT have the same SI and the same BFR-NBR. By taking the logical OR of the BitStrings of those rows, we obtain a bit mask that corresponds to that combination of SI and BFR-NBR. We will refer to this bit mask as the "Forwarding Bit Mask" (F-BM) for that <SI, BFR-NBR> combination. For example, in Figure 2, we see that two of the rows have the same SI (0) and same BFR-NBR (C). The bit mask that corresponds to <SI=0, BFR-NBR-C> is 0011 ("0001" OR'd with "0010"). The BIFT is used to map from the BFR-id of a BFER to the corresponding F-BM and BFR-NBR. For example, Figure 3 shows the BIFT that is derived from the BIRT of Figure 2. Note that BFR-ids 1 and 2 have the same SI and the same BFR-NBR; hence, they have the same F-BM. ------------------------------------- | BFR-id | F-BM | BFR-NBR | | (SI:BitString) | | | ===================================== | 1 (0:0001) | 0011 | C | ------------------------------------- | 2 (0:0010) | 0011 | C | ------------------------------------- | 3 (0:0100) | 0100 | E | ------------------------------------- | 4 (0:1000) | 1000 | A | ------------------------------------- Figure 3: Bit Index Forwarding Table This BIFT is programmed into the data plane and used to forward packets, applying the rules specified below in Section 6.5.
6.5. The BIER Forwarding Procedure
Below is the procedure that a BFR uses for forwarding a BIER-encapsulated packet. 1. Determine the packet's SI, BitStringLength, and sub-domain. 2. If the BitString consists entirely of zeroes, discard the packet; the forwarding process has been completed. Otherwise, proceed to step 3. 3. Find the position (call it "k") of the least significant (i.e., of the rightmost) bit that is set in the packet's BitString. (Remember, bits are numbered from 1, starting with the least significant bit.) 4. If bit k identifies the BFR itself, copy the packet, and send the copy to the multicast flow overlay. Then clear bit k in the original packet, and go to step 2. Otherwise, proceed to step 5. 5. Use the value k, together with the SI, sub-domain, and BitStringLength, as the "index" into the BIFT. 6. Extract from the BIFT the F-BM and the BFR-NBR. 7. Copy the packet. Update the copy's BitString by AND'ing it with the F-BM (i.e., PacketCopy->BitString &= F-BM). Then forward the copy to the BFR-NBR. (If the BFR-NBR is null, the copy is just discarded.) Note that when a packet is forwarded to a particular BFR-NBR, its BitString identifies only those BFERs that are to be reached via that BFR-NBR. 8. Now update the original packet's BitString by AND'ing it with the INVERSE of the F-BM (i.e., Packet->BitString &= ~F-BM). (This clears the bits that identify the BFERs to which a copy of the packet has just been forwarded.) Go to step 2. This procedure causes the packet to be forwarded to a particular BFR-NBR only once. The number of lookups in the BIFT is the same as the number of BFR-NBRs to which the packet must be forwarded; it is not necessary to do a separate lookup for each destination BFER. When a packet is sent to a particular BFR-NBR, the BitString is not the only part of the BIER header that needs to be modified. If there is a TTL field in the BIER header, it will need to be decremented. In addition, when either of the encapsulations of [MPLS_BIER_ENCAPS] is used, the BIFT-id field is likely to require modification, based on signaling from the BFR-NBR to which the packet is being sent. The
BIFT-id field of an incoming BIER packet implicitly identifies an SI, a sub-domain, and a BitStringLength. If the packet is sent to a particular BFR-NBR, the BIFT-id field must be changed to whatever value that BFR-NBR has advertised for the same SI, sub-domain, and BitStringLength. (If the encapsulation of Section 2.1 of [MPLS_BIER_ENCAPS] is used, this is essentially an MPLS label swap operation.) Suppose it has been decided (by the above rules) to send a packet to a particular BFR-NBR. If that BFR-NBR is connected via multiple parallel interfaces, it may be desirable to apply some form of load balancing. Load-balancing algorithms are outside the scope of this document. However, if the packet's encapsulation contains an entropy field, the entropy field SHOULD be respected; two packets with the same value of the entropy field SHOULD be sent on the same interface (if possible). In some cases, the routing underlay may provide multiple equal-cost paths (through different BFR-NBRs) to a given BFER. This is known as "Equal-Cost Multipath" (ECMP). The procedures described in this section must be augmented in order to support load balancing over ECMP. The necessary augmentations can be found in Section 6.7. In the event that unicast traffic to the BFR-NBR is being sent via a "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic sent to the BFR-NBR SHOULD also be sent via that tunnel. This allows any existing "fast reroute" schemes to be applied to multicast traffic as well as to unicast traffic. Some examples of these forwarding procedures can be found in Section 6.6.
The rules given in this section can be represented by the following pseudocode: void ForwardBitMaskPacket (Packet) { SI=GetPacketSI(Packet); Offset=SI*BitStringLength; for (Index = GetFirstBitPosition(Packet->BitString); Index ; Index = GetNextBitPosition(Packet->BitString, Index)) { F-BM = BIFT[Index+Offset]->F-BM; if (!F-BM) continue; BFR-NBR = BIFT[Index+Offset]->BFR-NBR; PacketCopy = Copy(Packet); PacketCopy->BitString &= F-BM; PacketSend(PacketCopy, BFR-NBR); Packet->BitString &= ~F-BM; } } Figure 4: Pseudocode This pseudocode assumes that, at a given BFER, the BFR-NBR entry corresponding to the BFER's own BFR-id will be the BFER's own BFR-prefix. It also assumes that the corresponding F-BM has only one bit set, the bit representing the BFER itself. In this case, the "PacketSend" function sends the packet to the multicast flow overlay. This pseudocode also assumes that the F-BM for the null next hop contains a 1 in a given bit position if and only if that bit position corresponds to either an unused BFR-id or an unreachable BFER. When the BFR-NBR is null, the "PacketSend" function discards the packet.
6.6. Examples of BIER Forwarding
In this section, we give two examples of BIER forwarding, based on the topology in Figure 1. In these examples, all packets have been assigned to the default sub-domain, all packets have SI=0, and the BitStringLength is 4. Figure 5 shows the BIFT entries for SI=0 only. For compactness, we show the first column of the BIFT, the BFR-id, only as an integer. BFR-A BIFT BFR-B BIFT BFR-C BIFT ------------------- ------------------- ------------------- | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | =================== =================== =================== | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | ------------------- ------------------- ------------------- | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | ------------------- ------------------- ------------------- | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B | ------------------- ------------------- ------------------- | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B | ------------------- ------------------- ------------------- Figure 5: BIFTs Used in the Forwarding Examples6.6.1. Example 1
BFR-D, BFR-E, and BFR-F are BFERs. BFR-A is the BFIR. Suppose that BFIR-A has learned from the multicast flow overlay that BFER-D is interested in a given multicast flow. If BFIR-A receives a packet of that flow from outside the BIER domain, BFIR-A applies the BIER encapsulation to the packet. The encapsulation must be such that the SI is zero. The encapsulation also includes a BitString, with just bit 1 set and with all other bits clear (i.e., 0001). This indicates that BFER-D is the only BFER that needs to receive the packet. BFIR-A then follows the procedures of Section 6.5, as follows: o Since the packet's BitString is 0001, BFIR-A finds that the first bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A determines that the bit mask F-BM is 0111 and the BFR-NBR is BFR-B. o BFR-A then makes a copy of the packet and applies the F-BM to the copy: Copy->BitString &= 0111. The copy's BitString is now 0001 (0001 & 0111). o The copy is now sent to BFR-B.
o BFR-A then updates the packet's BitString by applying the inverse
of the F-BM: Packet->BitString &= ~F-BM. As a result, the
packet's BitString is now 0000 (0001 & 1000).
o As the packet's BitString is now zero, the forwarding procedure is
complete.
When BFR-B receives the multicast packet from BFR-A, it follows the
same procedure. The result is that a copy of the packet, with a
BitString of 0001, is sent to BFR-C. BFR-C applies the same
procedures and, as a result, sends a copy of the packet, with a
BitString of 0001, to BFR-D.
At BFER-D, the BIFT entry (not pictured) 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.
6.6.2. Example 2
This example is similar to example 1, except that BFIR-A has learned
from the multicast flow overlay that both BFER-D and BFER-E are
interested in a given multicast flow. If BFIR-A receives a packet of
that flow from outside the BIER domain, BFIR-A applies the BIER
encapsulation to the packet. The encapsulation must be such that the
SI is zero. The encapsulation also includes a BitString with
two bits set: bit 1 is set (as in example 1) to indicate that BFR-D
is a BFER for this packet, and bit 3 is set to indicate that BFR-E is
a BFER for this packet. That is, the BitString (assuming again a
BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows
the procedures of Section 6.5, as follows:
o Since the packet's BitString is 0101, BFIR-A finds that the first
bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
determines that the bit mask F-BM is 0111 and the BFR-NBR is
BFR-B.
o BFR-A then makes a copy of the packet and applies the F-BM to the
copy: Copy->BitString &= 0111. The copy's BitString is now 0101
(0101 & 0111).
o The copy is now sent to BFR-B.
o BFR-A then updates the packet's BitString by applying the inverse
of the F-BM: Packet->BitString &= ~F-BM. As a result, the
packet's BitString is now 0000 (0101 & 1000).
o As the packet's BitString is now zero, the forwarding procedure is
complete.
When BFR-B receives the multicast packet from BFR-A, it follows the
procedure of Section 6.5, as follows:
o Since the packet's BitString is 0101, 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.
o BFR-B then makes a copy of the packet and applies the F-BM to the
copy: Copy->BitString &= 0011. The copy's BitString is now 0001
(0101 & 0011).
o The copy is now sent to BFR-C.
o BFR-B then updates the packet's BitString by applying the inverse
of the F-BM: Packet->BitString &= ~F-BM. As a result, the
packet's BitString is now 0100 (0101 & 1100).
o Now BFR-B finds the next bit in the packet's (modified) BitString.
This 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.
o BFR-B then makes a copy of the packet and applies the F-BM to the
copy: Copy->BitString &= 0100. The copy's BitString is now 0100
(0100 & 0100).
o The copy is now sent to BFR-E.
o BFR-B then updates the packet's BitString by applying the inverse
of the F-BM: Packet->BitString &= ~F-BM. As a result, the
packet's BitString is now 0000 (0100 & 1011).
o As the packet's BitString is now zero, the forwarding procedure is
complete.
Thus, BFR-B forwards two copies of the packet. One copy of the
packet, with BitString 0001, has now been sent from BFR-B to BFR-C.
Following the same procedures, BFR-C will forward the packet to
BFER-D.
At BFER-D, the BIFT entry (not pictured) 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. The other copy of the packet has been sent from BFR-B to BFER-E, with BitString 0100. At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an F-BM of 0100 and a BFR-NBR of BFR-E itself. This will cause a copy of the packet to be delivered to the multicast flow overlay at BFR-E. The packet's BitString will be set to 0000, and the packet will not be forwarded any further.6.7. Equal-Cost Multipath Forwarding
In many networks, the routing underlay will provide multiple equal-cost paths from a given BFR to a given BFER. When forwarding multicast packets through the network, it can be beneficial to take advantage of this by load-balancing among those paths. This feature is known as "Equal-Cost Multipath (ECMP) forwarding". BIER supports ECMP forwarding, but the procedures of Section 6.5 must be modified slightly. Two ECMP procedures are defined. In the first (described in Section 6.7.1), the choice among equal-cost paths taken by a given packet from a given BFR to a given BFER depends on (a) routing, (b) the packet's entropy, and (c) the other BFERs to which that packet is destined. In the second (described in Section 6.7.2), the choice depends only upon the packet's entropy. There are trade-offs between the two forwarding procedures described here. In the procedure of Section 6.7.1, the number of packet replications is minimized. The procedure in Section 6.7.1 also uses less memory in the BFR. In the procedure of Section 6.7.2, the path traveled by a given packet from a given BFR to a given BFER is independent of the other BFERs to which the packet is destined. While the procedures of Section 6.7.2 may cause more replications, they provide a more predictable behavior. The two procedures described here operate on identical packet formats and will interoperate correctly. However, if deterministic behavior is desired, then all BFRs would need to use the procedure from Section 6.7.2.
6.7.1. Non-deterministic ECMP
Figure 6 shows the operation of non-deterministic ECMP in BIER. BFR-A BIFT BFR-B BIFT BFR-C BIFT ------------------- ------------------- ------------------- | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | =================== =================== =================== | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | ------------------- ------------------- ------------------- | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | ------------------- | | 0110 | E | ------------------- | 3 | 0111 | B | ------------------- | 3 | 1100 | B | ------------------- | 3 | 0110 | E | ------------------- | 4 | 1000 | A | ------------------| | 4 | 1100 | B | ------------------- | 4 | 1000 | A | ------------------- ------------------- ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D ) 4 (0:1000) \ \ 1 (0:0001) \ \ ( E ) ------------ ( F ) 3 (0:0100) 2 (0:0010) Figure 6: Example of Non-deterministic ECMP In this example, BFR-B has two equal-cost paths to reach BFER-F: one via BFR-C and one via BFR-E. Since the BFR-id of BFER-F is 2, this is reflected in entry 2 of BFR-B's BIFT. Entry 2 shows that BFR-B has a choice of two BFR-NBRs for BFER-B and that a different F-BM is associated with each choice. When BFR-B looks up entry 2 in the BIFT, it can choose either BFR-NBR. However, when following the procedures of Section 6.5, it MUST use the F-BM corresponding to the BFR-NBR that it chooses. How the choice is made is an implementation matter. However, the usual rules for ECMP apply: packets of a given flow SHOULD NOT be split among two paths, and any entropy field in the packet's encapsulation SHOULD be respected. Note, however, that by the rules of Section 6.5, any packet destined for both BFER-D and BFER-F will be sent via BFR-C.
6.7.2. Deterministic ECMP
With the procedures of Section 6.7.1, where ECMP paths exist, the path a packet takes to reach any particular BFER depends not only on routing and on the packet's entropy but also on the set of other BFERs to which the packet is destined. For example, consider the following scenario in the network of Figure 6. o There is a sequence of packets being transmitted by BFR-A, some of which are destined for both D and F and some of which are destined only for F. o All the packets in this sequence have the same entropy value (call it "Q"). o At BFR-B, when a packet with entropy value Q is forwarded via entry 2 in the BIFT, the packet is sent to E. Using the forwarding procedure of Section 6.7.1, packets of this sequence that are destined for both D and F are forwarded according to entry 1 in the BIFT and thus will reach F via the path A-B-C-F. However, packets of this sequence that are destined only for F are forwarded according to entry 2 in the BIFT and thus will reach F via the path A-B-E-F. That procedure minimizes the number of packets transmitted by BFR-B. However, consider the following scenario: o Beginning at time t0, the multicast flow in question needs to be received ONLY by BFER-F. o Beginning at a later time, t1, the flow needs to be received by both BFER-D and BFER-F. o Beginning at a later time, t2, the flow no longer needs to be received by D, but still needs to be received by F. Then, from t0 until t1, the flow will travel to F via the path A-B-E-F. From t1 until t2, the flow will travel to F via the path A-B-C-F. And from t2, the flow will again travel to F via the path A-B-E-F. The problem is that if D repeatedly joins and leaves the flow, the flow's path from B to F will keep switching. This could cause F to receive packets out of order. It also makes troubleshooting difficult. For example, if there is some problem on the E-F link,
receivers at F will get good service when the flow is also going to D (avoiding the E-F link) but bad service when the flow is not going to D. Since it is hard to know which path is being used at any given time, this may be hard to troubleshoot. Also, it is very difficult to perform a traceroute that is known to follow the path taken by the flow at any given time. The source of this difficulty is that, in the procedures of Section 6.7.1, the path taken by a particular flow to a particular BFER depends upon whether there are lower-numbered BFERs that are also receiving the flow. Thus, the choice among the ECMP paths is fundamentally non-deterministic. Deterministic forwarding can be achieved by using multiple BIFTs, such that each row in a BIFT has only one path to each destination but the multiple ECMP paths to any particular destination are spread across the multiple tables. When a BIER-encapsulated packet arrives to be forwarded, the BFR uses a hash of the BIER entropy field to determine which BIFT to use, and then the normal BIER forwarding algorithm (as described in Sections 6.5 and 6.6) is used with the selected BIFT. As an example, suppose there are two paths to destination X (call them "X1" and "X2") and four paths to destination Y (call them "Y1", "Y2", "Y3", and "Y4"). If there are, say, four BIFTs, one BIFT would have paths X1 and Y1, one would have X1 and Y2, one would have X2 and Y3, and one would have X2 and Y4. If traffic to X is split evenly among these four BIFTs, the traffic will be split evenly between the two paths to X; if traffic to Y is split evenly among these four BIFTs, the traffic will be split evenly between the four paths to Y. Note that if there are three paths to one destination and four paths to another, 12 BIFTs would be required in order to get even splitting of the load to each of those two destinations. Of course, each BIFT uses some memory, and one might be willing to have less optimal splitting in order to have fewer BIFTs. How that trade-off is made is an implementation or deployment decision.
(page 29 continued on part 3)