RFC 9262: Tree Engineering for Bit Index Explicit Replication (BIER-TE)

3.2.1. The BIER-TE Controller

This architecture describes the BIER-TE control plane, as shown in Figure 3, as consisting of:¶

The single, centralized BIER-TE controller is used in this document as the reference option for the BIER-TE control plane, but other options are equally feasible. The BIER-TE control plane could equally be implemented without automated configuration/protocols, by an operator via a CLI on the BFRs. In that case, operator-configured local policy on the BFIR would have to determine how to set the appropriate BIER header fields. The BIER-TE control plane could also be decentralized and/or distributed, but this document does not consider any additional protocols and/or procedures that would then be necessary to coordinate its (distributed/decentralized) entities to achieve the above-described functionality.¶

4.2.1. Forward Connected

A "forward_connected()" adjacency is an adjacency towards a directly connected BFR-NBR using an interface address of that BFR on the connecting interface. A forward_connected() adjacency does not route packets; only L2 forwards them to the neighbor.¶

Packets sent to an adjacency with "DoNotClear" (DNC) set in the BIFT MUST NOT have the bit position for that adjacency cleared when the BFR creates a copy for it. The bit position will still be cleared for copies of a packet made towards other adjacencies. This can be used, for example, in ring topologies as explained in Section 5.1.6.¶

For protection against loops caused by misconfiguration (see Section 5.2.1), DNC is only permissible for forward_connected() adjacencies. No need or benefit of DNC for other types of adjacencies was identified, and associated risks were not analyzed.¶

4.2.2. Forward Routed

A "forward_routed()" adjacency is an adjacency towards a BFR that uses a (tunneling) encapsulation that will cause a packet to be forwarded by the routing underlay towards the adjacent BFR indicated via the l3-neighbor parameter of the forward_routed() adjacency. This can leverage any feasible encapsulation, such as MPLS or tunneling over IP/IPv6, as long as the BIER-TE packet can be identified as a payload. This identification can rely on either the BIER/BIER-TE co-existence mechanisms described in Section 4.3 or explicit support for a BIER-TE payload type in the tunneling encapsulation.¶

Forward_routed() adjacencies are necessary to pass BIER-TE traffic across routers that are not BIER-TE capable or to minimize the number of required BPs by tunneling over (BIER-TE-capable) routers on which neither replication nor path steering is desired, or simply to leverage the routing underlay's path redundancy and FRR towards the next BFR. They may also be useful to a multi-subnet adjacent BFR for leveraging the routing underlay ECMP independently of BIER-TE ECMP (Section 4.2.3).¶

4.2.3. ECMP

(Non-TE) BIER ECMP is tied to the BIER BIFT processing semantic and is therefore not directly usable with BIER-TE.¶

A BIER-TE "Equal-Cost Multipath" (ECMP()) adjacency as shown in Figure 4 for BIFT-index 7 has a list of two or more non-ECMP() adjacencies as parameters and an optional seed parameter. When a BIER-TE packet is copied onto such an ECMP() adjacency, an implementation-specific so-called hash function will select one out of the list's adjacencies to which the packet is forwarded. 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 adjacency. The seed parameter permits the design of hash functions that are easy to implement at high speed without running into polarization issues across multiple consecutive ECMP hops. See Section 5.1.7 for details.¶

4.2.4. Local Decap(sulation)

A "local_decap()" adjacency passes a copy of the payload of the BIER-TE packet to the protocol ("NextProto") within the BFR (IP/IPv6, Ethernet,...) responsible for that payload according to the packet header fields. A local_decap() adjacency turns the BFR into a BFER for matching packets. Local_decap() adjacencies require the BFER to support routing or switching for NextProto to determine how to further process the packets.¶

5.1.1. P2P Links

On a "point-to-point" (P2P) link that connects two BFRs, the same bit position can be used on both BFRs for the adjacency to the neighboring BFR. A P2P link therefore requires only one bit position.¶

5.1.2. BFERs

Every non-leaf BFER is given a unique bit position with a local_decap() adjacency.¶

5.1.3. Leaf BFERs

A leaf BFER is one where incoming BIER-TE packets never need to be forwarded to another BFR but are only sent to the BFER to exit the BIER-TE domain. For example, in networks where "Provider Edge" (PE) routers are spokes connected to Provider (P) routers, those PEs are leaf BFERs, unless there is a U-turn between two PEs.¶

Consider how redundant disjoint traffic can reach BFER1/BFER2 as shown in Figure 7: when BFER1/BFER2 are non-leaf BFERs as shown on the right-hand side, one traffic copy would be forwarded to BFER1 from BFR1, but the other one could only reach BFER1 via BFER2, which makes BFER2 a non-leaf BFER. Likewise, BFER1 is a non-leaf BFER when forwarding traffic to BFER2. Note that the BFERs on the left-hand side of the figure are only guaranteed to be leaf BFERs by correctly applying a routing configuration that prohibits transit traffic from passing through the BFERs, which is commonly applied in these topologies.¶

        BFR1(P) BFR2(P)             BFR1(P)  BFR2(P)
          |  \ /  |                    |       |
          |   X   |                    |       |
          |  / \  |                    |       |
     BFER1(PE)  BFER2(PE)        BFER1(PE)----BFER2(PE)

                                           ^ U-turn link

         Leaf BFER /               Non-leaf BFER /
          PE router                  PE router

In most situations, leaf BFERs that are to be addressed via the same BitString can share a single bit position for their local_decap() adjacency in that BitString and therefore save bit positions. On a non-leaf BFER, a received BIER-TE packet may only need to transit the BFER, or it may also need to be decapsulated. Whether or not to decapsulate the packet therefore needs to be indicated by a unique bit position populated only on the BIFT of this BFER with a local_decap() adjacency. On a leaf BFER, packets never need to pass through; any packet received is therefore usually intended to be decapsulated. This can be expressed by a single, shared bit position that is populated with a local_decap() adjacency on all leaf BFERs addressed by the BitString.¶

The possible exceptions to this leaf BFER bit position optimization scenario can be cases where the bit position on the prior BIER-TE BFR (which created the packet copy for the leaf BFER in question) is populated with multiple adjacencies as an optimization -- for example, as described in Sections 5.1.4 and 5.1.5. With either of these two optimizations, the sender of the packet could only control explicitly whether the packet was to be decapsulated on the leaf BFER in question, if the leaf BFER has a unique bit position for its local_decap() adjacency.¶

However, if the bit position is shared across a leaf BFER and packets are therefore decapsulated -- potentially unnecessarily -- this may still be appropriate if the decapsulated payload of the BIER-TE packet indicates whether or not the packets need to be further processed/received. This is typically true, for example, if the payload is IP multicast, because IP multicast on a BFER would know the membership state of the IP multicast payload and be able to discard it if the packets were delivered unnecessarily by the BIER-TE layer. If the payload has no such membership indication and the BFIR wants to have explicit control regarding which BFERs are to receive and decapsulate a packet, then these two optimizations cannot be used together with shared bit position optimization for a leaf BFER.¶

5.1.4. LANs

In a LAN, the adjacency to each neighboring BFR is given a unique bit position. The adjacency of this bit position is a forward_connected() adjacency towards the BFR, and this bit position is populated into the BIFT of all the other BFRs on that LAN.¶

                                 BFR1
                                  |p1
                           LAN1-+-+---+-----+
                              p3|   p4|   p2|
                              BFR3  BFR4  BFR7

If bandwidth on the LAN is not an issue and most BIER-TE traffic should be copied to all neighbors on a LAN, then bit positions can be saved by assigning just a single bit position to the LAN and populating the bit position of the BIFTs of each BFR on the LAN with a list of forward_connected() adjacencies to all other neighbors on the LAN.¶

This optimization does not work in the case of BFRs redundantly connected to more than one LAN with this optimization. These BFRs would receive duplicates and forward those duplicates into the other LANs. Such BFRs require separate bit positions for each LAN they connect to.¶

5.1.5. Hub and Spoke

In a setup with a hub and multiple spokes connected via separate P2P links to the hub, all P2P adjacencies from the hub to the spokes' links can share the same bit position. The bit position on the hub's BIFT is set up with a list of forward_connected() adjacencies, one for each spoke.¶

This option is similar to the bit position optimization in LANs: redundantly connected spokes need their own bit positions, unless they are themselves leaf BFERs.¶

This type of optimized BP could be used, for example, when all traffic is "broadcast" traffic (very dense receiver sets), such as live TV or many-to-many telemetry, including situational awareness. This BP optimization can then be used to explicitly steer different traffic flows across different ECMP paths in data-center or broadband-aggregation networks with minimal use of BPs.¶

5.1.6. Rings

In L3 rings, instead of assigning a single bit position for every P2P link in the ring, it is possible to save bit positions by setting the "DoNotClear" (DNC) flag on forward_connected() adjacencies.¶

For the ring shown in Figure 9, a single bit position will suffice to forward traffic entering the ring at BFRa or BFRb all the way up to BFR1, as follows.¶

On BFRa, BFRb, BFR30,... BFR3, the bit position is populated with a forward_connected() adjacency pointing to the clockwise neighbor on the ring and with DNC set. On BFR2, the adjacency also points to the clockwise neighbor BFR1, but without DNC set.¶

Handling DNC this way ensures that copies forwarded from any BFRs in the ring to a BFR outside the ring will not have the ring bit position set, therefore minimizing the risk of creating loops.¶

               v        v
               |        |
        L1     |   L2   |   L3
    /-------- BFRa ---- BFRb --------------------\
    |                                            |
    \- BFR1 - BFR2 - BFR3 - ... - BFR29 - BFR30 -/
        |      |    L4               |      |
     p33|                         p15|
        BFRd                       BFRc

Note that this example only permits packets intended to make it all the way around the ring to enter it at BFRa and BFRb. Note also that packets will always travel clockwise. If packets should be allowed to enter the ring at any of the ring's BFRs, then one would have to use two ring bit positions, one for each direction: clockwise and counterclockwise.¶

Both would be set up to stop rotating on the same link, e.g., L1. When the ring's BFIR creates the clockwise copy, it will clear the counterclockwise bit position because the DNC bit only applies to the bit for which the replication is done (likewise for the clockwise bit position for the counterclockwise copy). As a result, the ring's BFIR will send a copy in both directions, serving BFRs on either side of the ring up to L1.¶

5.1.7. Equal-Cost Multipath (ECMP)

An ECMP() adjacency allows the use of just one BP to deliver packets to one of N adjacencies instead of one BP for each adjacency. In the common example case shown in Figure 10, a link bundle of three links L1,L2,L3 connects BFR1 and BFR2, and only one BP is used instead of three BPs to deliver packets from BFR1 to BFR2.¶

             --L1-----
        BFR1 --L2----- BFR2
             --L3-----

  BIFT entry in BFR1:
  ------------------------------------------------------------------
  | Index |  Adjacencies                                           |
  ==================================================================
  | 0:6   |  ECMP({forward_connected(L1, BFR2),                    |
  |       |        forward_connected(L2, BFR2),                    |
  |       |        forward_connected(L3, BFR2)}, seed)             |
  ------------------------------------------------------------------

  BIFT entry in BFR2:
  ------------------------------------------------------------------
  | Index |  Adjacencies                                           |
  ==================================================================
  | 0:6   |  ECMP({forward_connected(L1, BFR1),                    |
  |       |        forward_connected(L2, BFR1),                    |
  |       |        forward_connected(L3, BFR1)}, seed)             |
  ------------------------------------------------------------------

This document does not standardize any ECMP algorithm because it is sufficient for implementations to document their freely chosen ECMP algorithm. Figure 11 shows an example ECMP algorithm and would double as its documentation: a BIER-TE controller could determine which adjacency is chosen based on the seed and adjacencies parameters and on packet entropy.¶

   forward(packet, ECMP(adj(0), adj(1),... adj(N-1), seed)):
      i = (packet(bier-header-entropy) XOR seed) % N
      forward packet to adj(i)

In the example shown in Figure 12, all traffic from BFR1 towards BFR10 is intended to be ECMP load-split equally across the topology. This example is not meant as a likely setup; rather, it illustrates that ECMP can be used to share BPs not only across link bundles but also across alternative paths across different transit BFRs, and it explains the use of the seed parameter.¶

                 BFR1         (BFIR)
               /L11  \L12
              /       \
          BFR2         BFR3
         /L21 \L22    /L31 \L32
        /      \     /      \
       BFR4  BFR5   BFR6  BFR7
        \      /     \      /
         \    /       \    /
          BFR8         BFR9
              \       /
               \     /
                BFR10         (BFER)

  BIFT entry in BFR1:
  ------------------------------------------------------------------
  | 0:6   |  ECMP({forward_connected(L11, BFR2),                   |
  |       |        forward_connected(L12, BFR3)}, seed1)           |
  ------------------------------------------------------------------

  BIFT entry in BFR2:
  ------------------------------------------------------------------
  | 0:7   |  ECMP({forward_connected(L21, BFR4),                   |
  |       |        forward_connected(L22, BFR5)}, seed1)           |
  ------------------------------------------------------------------

  BIFT entry in BFR3:
  ------------------------------------------------------------------
  | 0:7   |  ECMP({forward_connected(L31, BFR6),                   |
  |       |        forward_connected(L32, BFR7)}, seed1)           |
  ------------------------------------------------------------------

  BIFT entry in BFR4, BFR5:
  ------------------------------------------------------------------
  | 0:8   |  forward_connected(Lxx, BFR8)  |xx differs on BFR4/BFR5|
  ------------------------------------------------------------------

  BIFT entry in BFR6, BFR7:
  ------------------------------------------------------------------
  | 0:8   |  forward_connected(Lxx, BFR9)  |xx differs on BFR6/BFR7|
  ------------------------------------------------------------------

  BIFT entry in BFR8, BFR9:
  ------------------------------------------------------------------
  | 0:9   |  forward_connected(Lxx, BFR10) |xx differs on BFR8/BFR9|
  ------------------------------------------------------------------

Note that for the following discussion of ECMP, only the BIFT ECMP() adjacencies on BFR1, BFR2, and BFR3 are relevant. The reuse of BPs across BFRs in this example is further explained in Section 5.1.9 below.¶

With the ECMP setup shown in the topology above, traffic would not be equally load-split. Instead, links L22 and L31 would see no traffic at all: BFR2 will only see traffic from BFR1, for which the ECMP hash in BFR1 selected the first adjacency in the list of two adjacencies given as parameters to the ECMP: link L11-to-BFR2. BFR2 again performs ECMP with two adjacencies on that subset of traffic using the same seed1 and will therefore again select the first of its two adjacencies: L21-to-BFR4. Therefore, L22 and BFR5 see no traffic (likewise for L31 and BFR6).¶

This issue in BFR2/BFR3 is called "polarization". It results from the reuse of the same hash function across multiple consecutive hops in topologies like these. To resolve this issue, the ECMP() adjacency on BFR1 can be set up with a different seed2 than the ECMP() adjacencies on BFR2/BFR3. BFR2/BFR3 can use the same hash because packets will not sequentially pass across both of them. Therefore, they can also use the same BP (i.e., 0:7).¶

Note that ECMP solutions outside of BIER often hide the seed by auto-selecting it from local entropy such as unique local or next-hop identifiers. Allowing the BIER-TE controller to explicitly set the seed gives the BIER-TE controller the ability to control the selection of the same path or different paths across multiple consecutive ECMP hops.¶

5.1.8. Forward Routed Adjacencies

                   ...............
         ...BFR1--...           ...--L1-- BFR2...
                  ... .Routers. ...--L2--/
         ...BFR4--...           ...--L3-- BFR3...
                  ...           ...--L4--/ |
                   ...............         |
                                          LO
                    Network Area 1

5.1.9. Reuse of Bit Positions (without DNC)

BPs can be reused across multiple BFRs to minimize the number of BPs needed. This happens when adjacencies on multiple BFRs use the DNC flag as described above, but it can also be done for non-DNC adjacencies. This section only discusses this non-DNC case.¶

Because a given BP is cleared when passing a BFR with an adjacency for that BP, reusing BPs across multiple BFRs does not introduce any problems with duplicates or loops that do not also exist when every adjacency has a unique BP. Instead, the challenge when reusing BPs is whether the desired Tree Engineering goals can still be achieved.¶

A BP cannot be reused across two BFRs that would need to be passed sequentially for some path: the first BFR will clear the BP, so those paths cannot be built. A BP can be set across BFRs that would only occur across (A) different paths or (B) different branches of the same tree.¶

An example of (A) was given in Figure 12, where BP 0:7, BP 0:8, and BP 0:9 are each reused across multiple BFRs because a single packet/path would never be able to reach more than one BFR sharing the same BP.¶

Assume that the example was changed: BFR1 has no ECMP() adjacency for BP 0:6 but instead has BP 0:5 with forward_connected() to BFR2 and BP 0:6 with forward_connected() to BFR3. Packets with both BP 0:5 and BP 0:6 would now be able to reach both BFR2 and BFR3, and the still-existing reuse of BP 0:7 between BFR2 and BFR3 is a case of (B) where reusing a BP is perfect because it does not limit the set of useful path choices, as in the following example.¶

If instead of reusing BP 0:7 BFR3 used a separate BP 0:10 for its ECMP() adjacency, no useful additional path steering options would be enabled. If duplicates at BFR10 were undesirable, this would be done by not setting BP 0:5 and BP 0:6 for the same packet. If the duplicates were desirable (e.g., resilient transmission), the additional BP 0:10 would also not render additional value.¶

Reuse may also save BPs in larger topologies. Consider the topology shown in Figure 14.¶

                       area1
                   BFR1a BFR1b
                     /    \
        ....................................
        .                Core              .
        ....................................
        |    /       \    /           \  |
      BFR2a BFR2b  BFR3a BFR3b      BFR6a BFR6b
       /-------\   /---------\      /--------\
       | area2 |   |  area3  | ...  | area6  |
       | ring  |   |  ring   |      | ring   |
       \-------/   \---------/      \--------/
       more BFRs    more BFRs        more BFRs

A BFIR/sender (e.g., video headend) is attached to area 1, and the five areas 2...6 contain receivers/BFERs. Assume that each area has a distribution ring, each with two BPs to indicate the direction (as explained before). These two BPs could be reused across the five areas. Packets would be replicated through other BPs from the core to the desired subset of areas, and once a packet copy reaches the ring of the area, the two ring BPs come into play. This reuse is a case of (B), but it limits the topology choices: packets can only flow around the same direction in the rings of all areas. This may or may not be acceptable based on the desired path steering options: if resilient transmission is the path engineering goal, then it is likely a good optimization; however, if the bandwidth of each ring were to be optimized separately, it would not be a good limitation.¶

5.1.10. Summary of BP Optimizations

In this section, we reviewed a range of techniques by which a BIER-TE controller can create a BIER-TE topology in a way that minimizes the number of necessary BPs.¶

Without any optimization, a BIER-TE controller would attempt to map the network subnet topology 1:1 into the BIER-TE topology, every adjacent neighbor in the subnet would require a forward_connected() BP, and every BFER would require a local_decap() BP.¶

The optimizations described in this document are then as follows:¶

Note that this list of optimizations is not exhaustive. Further optimizations of BPs are possible, especially when both the set of required path steering choices and the possible subsets of BFERs that should be able to receive traffic are limited. The hub-and-spoke optimization is a simple example of such traffic-pattern-dependent optimizations.¶

5.2.1. Loops

Whenever BIER-TE creates a copy of a packet, the BitString of that copy will have all bit positions cleared that are associated with adjacencies on the BFR. This prevents packets from looping. The only exceptions are adjacencies with DNC set.¶

With DNC set, looping can happen. Consider in Figure 15 that link L4 from BFR3 is (inadvertently) plugged into the L1 interface of BFRa (instead of BFR2). This creates a loop where the ring's clockwise bit position is never cleared for copies of the packets traveling clockwise around the ring.¶

               v        v
               |        |
        L1     |   L2   |   L3
    /-------- BFRa ---- BFRb ---------------------\
    |        .                                    |
    |         ......  Wrong link wiring           |
    |               .                             |
    \- BFR1 - BFR2   BFR3 - ... - BFR29 - BFR30 -/
        |      |    L4               |      |
     p33|                         p15|
        BFRd                       BFRc

To inhibit looping in the face of such physical misconfiguration, only forward_connected() adjacencies are permitted to have DNC set, and the link layer port unique unicast destination address of the adjacency (e.g., "Media Access Control" (MAC) address) protects against closing the loop. Link layers without port unique link layer addresses should not be used with the DNC flag set.¶

5.2.2. Duplicates

Duplicates happen when the graph expressed by a BitString is not a tree but is redundantly connecting BFRs with each other. In Figure 16, a BitString of p2,p3,p4,p5 would result in duplicate packets arriving on BFER4. The BIER-TE controller must therefore ensure that only BitStrings that are trees are created.¶

                 BFIR1
                /    \
               / p2   \ p3
              BFR2   BFR3
               \ p4   / p5
                \    /
                 BFER4

When links are incorrectly physically reconnected before the BIER-TE controller updates BitStrings in BFIRs, duplicates can happen. Like loops, these can be inhibited by link layer addressing in forward_connected() adjacencies.¶

If interface or loopback addresses used in forward_routed() adjacencies are moved from one BFR to another, duplicates are equally likely to happen. Such readdressing operations must be coordinated with the BIER-TE controller.¶

5.3.1. Why SIs and Subdomains?

For (non-TE) BIER and BIER-TE forwarding, the most important result of using multiple SIs and/or subdomains is the same: multicast flow overlay packets that need to be sent to BFERs in different SIs or subdomains require multiple BIER packets, each one with a BitString for a different (SI,subdomain) combination. Each such BitString uses one BSL-sized SI block in the BIFT of the subdomain. We call this a BIFT:SI (block).¶

SIs and subdomains have different purposes in the BIER architecture and also the BIER-TE architecture. This impacts how operators manage them and especially how flow overlays will likely use them.¶

By default, every possible BFIR/BFER in a BIER network would likely be given a BFR-id in subdomain 0 (unless there are > 64k BFIRs/BFERs).¶

If there are different flow services (or service instances) requiring replication to different subsets of BFERs, then it will likely not be possible to achieve the best replication efficiency for all of these service instances via subdomain 0. Ideal replication efficiency for N BFERs exists in a subdomain if they are split over no more than ceiling(N/BitStringLength) SIs.¶

If service instances justify additional BIER:SI state in the network, additional subdomains will be used: BFIRs/BFERs are assigned BFR-ids in those subdomains, and each service instance is configured to use the most appropriate subdomain. This results in improved replication efficiency for different services.¶

Even if creation of subdomains and assignment of BFR-ids to BFIRs/BFERs in those subdomains is automated, it is not expected that individual service instances can deal with BFERs in different subdomains. A service instance may only support configuration of a single subdomain it should rely on.¶

To be able to easily reuse (and modify as little as possible) existing BIER procedures (including flow overlay and routing underlay), when BIER-TE forwarding is added, we therefore reuse SIs and subdomains logically in the same way as they are used in BIER: all necessary BFIRs/BFERs for a service use a single BIER-TE BIFT and are split across as many SIs as necessary (see Section 5.3.2). Different services may use different subdomains that primarily exist to provide more efficient replication (and, for BIER-TE, desirable path steering) for different subsets of BFIRs/BFERs.¶

5.3.2. Assigning Bits for the BIER-TE Topology

In BIER, BitStrings only need to carry bits for BFERs; this leads to the model where BFR-ids map 1:1 to each bit in a BitString.¶

In BIER-TE, BitStrings need to carry bits to indicate not only the receiving BFER but also the intermediate hops/links across which the packet must be sent. The maximum number of BFERs that can be supported in a single BitString or BIFT:SI depends on the number of bits necessary to represent the desired topology between them.¶

"Desired" topology means that it depends on the physical topology and the operator's desire to¶

The total number of bits to describe the topology vs. the number of BFERs in a BIFT:SI can range widely based on the size of the topology and the amount of alternative paths in it. In a BIER-TE topology crafted by a BIER-TE expert, the higher the percentage of non-BFER bits, the higher the likelihood that those topology bits are not just BIER-TE overhead without additional benefit but instead will allow the expression of desirable path steering alternatives.¶

5.3.3. Assigning BFR-ids with BIER-TE

BIER-TE forwarding does not use BFR-ids, nor does it require that the BFIR-id field of the BIER header be set to a particular value. However, other parts of a BIER-TE deployment may need a BFR-id -- specifically, multicast flow overlay signaling and multicast flow overlay packet disposition; in that case, BFRs need to also have BFR-ids for BIER-TE SDs.¶

For example, for BIER overlay signaling, BFIRs need to have a BFR-id, because this BFIR BFR-id is carried in the BFIR-id field of the BIER header to indicate to the overlay signaling on the receiving BFER which BFIR originated the packet.¶

In BIER, BFR-id = SI * BSL + BP, such that the SI and BP of a BFER can be calculated from the BFR-id and vice versa. This also means that every BFR with a BFR-id has a reserved BP in an SI, even if that is not necessary for BIER forwarding, because the BFR may never be a BFER (i.e., will only be a BFIR).¶

In BIER-TE, for a non-leaf BFER, there is usually a single BP for that BFER with a local_decap() adjacency on the BFER. The BFR-id for such a BFER can therefore be determined using the same procedure as that used for (non-TE) BIER: BFR-id = SI * BSL + BP.¶

As explained in Section 5.1.3, leaf BFERs do not need such a unique local_decap() adjacency. Likewise, BFIRs that are not also BFERs may not have a unique local_decap() adjacency either. For all those BFIRs and (leaf) BFERs, the controller needs to determine unique BFR-ids that do not collide with the BFR-ids derived from the non-leaf BFER local_decap() BPs.¶

While this document defines no requirements on how to allocate such BFR-ids, a simple option is to derive it from the (SI,BP) of an adjacency that is unique to the BFR in question. For a BFIR, this can be the first adjacency that is only populated on this BFIR; for a leaf BFER, this could be the first BP with an adjacency towards that BFER.¶

5.3.4. Mapping from BFRs to BitStrings with BIER-TE

In BIER, applications of the flow overlay on a BFIR can calculate the (SI,BP) of a BFER from the BFR-id of the BFER and can therefore easily determine the BitStrings for a BIER packet to a set of BFERs with known BFR-ids.¶

In BIER-TE, this mapping needs to be equally supported for flow overlays. This section outlines two core options, based on what type of Tree Engineering the BIER-TE controller needs to perform for a particular application.¶

"Independent branches":

For a given flow overlay instance, the branches from a BFIR to every BFER are calculated by the BIER-TE controller to be independent of the branches to any other BFER. Shortest path trees are the most common examples of trees with independent branches.¶

"Interdependent branches":

When a BFER is added to or deleted from a particular distribution tree, the BIER-TE controller has to recalculate the branches to other BFERs, because they may need to change. Steiner trees are examples of interdependent branch trees.¶

If "independent branches" are used, the BIER-TE controller can signal to the BFIR flow overlay for every BFER an SI:BitString that represents the branch to that BFER. The flow overlay on the BFIR can then, independently of the controller, calculate the SI:BitString for all desired BFERs by ORing their BitStrings. This allows flow overlay applications to operate independently of the controller whenever they need to determine which subset of BFERs needs to receive a particular packet.¶

If "interdependent branches" are required, an application would need to query the SI:BitString for a given set of BFERs whenever the set changes.¶

Note that in either case (unlike the scenario for BIER), the bits may need to change upon link/node failure/recovery, network expansion, or network resource consumption by other traffic as part of achieving Traffic Engineering goals (e.g., reoptimization of lower-priority traffic flows). Interactions between such BFIR applications and the BIER-TE controller do therefore need to support dynamic updates to the SIs:BitStrings.¶

Communications between the BFIR flow overlay and the BIER-TE controller require some way to identify the BFERs. If BFR-ids are used in the deployment, as outlined in Section 5.3.3, then those are the "natural" BFR-ids. If BFR-ids are not used, then any other unique identifier, such as a BFR's BFR-prefix [RFC8279], could be used.¶

5.3.5. Assigning BFR-ids for BIER-TE

It is not currently determined if a single subdomain could or should be allowed to forward both (non-TE) BIER and BIER-TE packets. If this should be supported, there are two options:¶

5.3.6. Example Bit Allocations

             area1           area2        area3
            BFR1a BFR1b  BFR2a BFR2b   BFR3a BFR3b
              |  \         /    \        /  |
              ................................
              .                Core          .
              ................................
              |    /       \    /        \  |
            BFR4a BFR4b  BFR5a BFR5b   BFR6a BFR6b
             area4          area5        area6

5.3.7. Summary

BIER-TE can, like BIER, support multiple SIs within a subdomain. This allows application of the mapping BFR-id = SI * BSL + BP. This also permits the reuse of the BIER architecture concept of BFR-ids and, therefore, minimization of BIER-TE-specific functions in possible BIER layer control plane mechanisms with BIER-TE, including flow overlay methods and BIER header fields.¶

The number of BFIRs/BFERs possible in a subdomain is smaller than in BIER because BIER-TE uses additional bits for the topology.¶

Subdomains in BIER-TE can be used as they are in BIER to create more efficient replication to known subsets of BFERs.¶

Assigning bits for BFERs intelligently into the right SI is more important in BIER-TE than in BIER because of replication efficiency and the overall amount of bits required.¶