Tree Engineering for Bit Index Explicit Replication (BIER-TE)
Extracted elements (29)
A BP can be reused across multiple BFRs provided no single forwarding path ever traverses more than one BFR in the reuse set, either because they lie on mutually exclusive alternative paths (case A) or on different branches of the same tree (case B). Reuse across sequentially traversed BFRs is forbidden because the first BFR clears the BP.
All leaf BFERs — those that never forward received BIER-TE packets onward — can share a single local_decap() bit position, saving significant BP space. Non-leaf BFERs require a unique BP because their BIFT must distinguish between decapsulating and transiting the same packet.
BIER-TE redefines bit positions (BPs) to indicate adjacencies in the network topology rather than BFERs as in non-TE BIER. A packet's BitString therefore encodes the edges of the forwarding tree, enabling per-packet stateless strict and loose path steering without requiring in-network routing state.
BIER-TE's forwarding pseudocode is derived from the BIER forwarding pseudocode with one key change: step [1] (clearing bits from the original Packet->BitString after the first copy) is omitted, because BIER-TE does not need to suppress duplicates from multiple bits sharing the same BFR-NBR. All necessary bit clearing is done via the AdjacentBits mask applied to each packet copy.
BIER-TE's reference control plane is a centralized BIER-TE controller that directly populates BIFTs, eliminating the need for Bit Index Routing Tables (BIRTs) on BFRs and for BFR-specific routing underlay extensions. Distributed or decentralized control plane options are equally feasible but require additional coordination protocols not specified here.
BIER-TE uses explicit BitStrings rather than Bloom filters to represent tree edges because Bloom filters introduce false-positive heuristic risk and cannot clear bits during forwarding, which is necessary to prevent loops. Explicit BitStrings can be seen as a special, lossless Bloom filter.
Except for optional forward_routed() adjacencies, BIER-TE does not require a routing underlay and can operate without IGP dependency. The BIER-TE controller directly populates BIFTs, replacing in-network autonomous path calculations with explicitly engineered paths.
In ring topologies, a single bit position with DNC set on forward_connected() adjacencies pointing clockwise allows a packet to traverse the entire ring without consuming one bit per link. Two ring BPs (one per direction) suffice for a full bidirectional ring, with DNC cleared at a designated 'stop' link to prevent endless circulation.
The ECMP() seed parameter allows the BIER-TE controller to assign different seeds to consecutive ECMP hops, preventing hash polarization where all traffic is forced down a single path through a multi-tier topology. Nodes on parallel (non-sequential) branches may safely share the same seed.
When the required number of BPs exceeds a single BitStringLength, multiple SIs and/or subdomains are used, consistent with non-TE BIER practice. SIs extend capacity within a subdomain; separate subdomains serve different service instances requiring distinct replication scopes or path-steering policies.
BIER and BIER-TE can co-exist in the same domain by partitioning the BIFT-id address space (e.g., via non-overlapping MPLS label ranges or disjoint subdomains), since a BFR must interpret a BIER-TE BitString differently from a non-TE BIER BitString. A packet is always forwarded end-to-end exclusively via BIER or BIER-TE ('ships in the night').
Forward_routed() adjacencies enable incremental BIER-TE deployment: only nodes requiring replication or path steering must support BIER-TE. Non-BIER-TE-capable intermediate routers are traversed transparently via unicast tunneling (MPLS label stack or IP/GRE), and forward_routed() adjacencies also allow leveraging routing underlay FRR and ECMP towards the next BIER-TE-capable BFR.
When BIER-TE is deployed alongside components developed for BIER (such as multicast flow overlays) that use BFR-ids, BIER-TE deployments MUST assign BFR-ids to BFRs and insert them into the BFIR-id field of BIER packet headers, mirroring BIER behavior.
BFRs that support both BIER-TE and BIER MUST support a configuration that enables BIER-TE forwarding rules instead of non-TE BIER rules for all BIFTs of one or more BIER subdomains.
BIER-TE forwarding MAY support ECMP() adjacencies; this is optional because ECMP can alternatively be achieved via forward_routed() adjacencies leveraging routing underlay ECMP or by explicit BPs for each ECMP path.
BIER-TE forwarding SHOULD support forward_connected() adjacencies with the DNC flag set, as this is needed to save bit positions in ring topologies.
BIER-TE forwarding SHOULD support more than one adjacency per bit position to enable bit savings in hub-and-spoke scenarios.
DNC is only permissible for forward_connected() adjacencies. No need or benefit of DNC for other adjacency types was identified, and associated risks were not analyzed.
Every BP in a BIER-TE BIFT MUST support having zero or one adjacency. BIER-TE forwarding MUST support forward_connected() (with DNC not set), forward_routed(), and local_decap() adjacency types.
For ECMP() adjacencies, if a packet's encapsulation contains an entropy field, the entropy field SHOULD be respected; two packets with the same entropy field value SHOULD be sent on the same adjacency to preserve flow ordering.
Packets sent to a forward_connected() adjacency with the DNC flag set MUST NOT have that bit position cleared in the copy made for that adjacency. The bit position is still cleared in copies made towards all other adjacencies.
A forward_connected() adjacency performs L2 unicast forwarding to a directly connected BFR neighbor on a specified interface without involving a routing underlay. It optionally carries a DoNotClear (DNC) flag that suppresses clearing of its BP in the packet copy sent to that adjacency.
A forward_routed() adjacency encapsulates the BIER-TE packet for delivery by the routing underlay to a specified L3 neighbor address. It supports any encapsulation (MPLS label stack, IP/GRE, etc.) that can carry a BIER-TE payload, enabling traffic to traverse non-BIER-TE routers.
A local_decap() adjacency removes the BIER header and passes the payload to the next-protocol handler (IP, IPv6, Ethernet, etc.) within the BFR, making the BFR act as a BFER for matching packets. An optional VRF parameter scopes the payload delivery.
An ECMP() adjacency holds a list of two or more non-ECMP adjacencies and an optional seed parameter. An implementation-specific hash selects one adjacency per packet; packets with the same entropy field value SHOULD be sent to the same adjacency. The seed parameter allows the BIER-TE controller to prevent polarization across consecutive ECMP hops.
The BIER-TE Bit Index Forwarding Table (BIFT) is indexed by BIFT-index = SI * BSL + BP - 1. Each entry may contain zero or more adjacencies of types forward_connected(), forward_routed(), local_decap(), or ECMP(). BIFT entries are populated only on the upstream BFR of each adjacency; all other BFRs leave those entries empty.
Duplicate packets can arise when a BitString encodes a non-tree graph (redundant BFR connections). The BIER-TE controller MUST ensure only tree-shaped BitStrings are installed in BFIRs. Physical reconnection of links before the controller updates BitStrings can cause transient duplicates; forward_connected() adjacency link-layer addressing provides partial protection.
Loop prevention is achieved by clearing all bit positions associated with the receiving BFR's adjacencies from every outgoing packet copy before forwarding. DNC adjacencies are the only exception; they are constrained to forward_connected() adjacencies, whose link-layer port-unique destination addresses (e.g., MAC addresses) provide an additional safeguard against inadvertent loop closure from physical miswiring.
BIER-TE forwarding computes PktAdjacentBits as (Packet->BitString AND AdjacentBits[SI]), clears all adjacent bits in the packet header (Packet->BitString AND NOT AdjacentBits[SI]), then loops over PktAdjacentBits: for each set bit, iterates over BIFT adjacencies, resolves ECMP if needed, copies the packet, restores the DNC bit if applicable, and dispatches via forward_connected (L2 unicast), forward_routed (L3 encap), or local_decap.