BIER-TE for Broadcast Link

1.1. Terminology

BIER:

Bit Index Explicit Replication.¶

BIER-TE:

BIER Traffic Engineering.¶

BFR:

Bit-Forwarding Router.¶

BFIR:

Bit-Forwarding Ingress Router.¶

BFER:

Bit-Forwarding Egress Router.¶

BFR-id:

BFR Identifier. It is a number in the range [1,65535].¶

BFR-NBR:

BFR Neighbor.¶

BFR-prefix:

An IP address (either IPv4 or IPv6) of a BFR.¶

BIRT:

Bit Index Routing Table. It 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.¶

BIFT:

Bit Index Forwarding Table.¶

IGP:

Interior Gateway Protocol.¶

LSDB:

Link State DataBase.¶

OSPF:

Open Shortest Path First.¶

IS-IS:

Intermediate System to Intermediate System.¶

2.1. Example BIER-TE Topology with LAN

An example BIER-TE topology with a LAN for a BIER-TE domain is shown in Figure 1. It has 9 nodes/BFRs A, B, C, D, E, F, G, H and K. Nodes/BFRs D, F, E, H, A and K are BFERs and have local decap adjacency BitPositions (BPs for short) 1, 2, 3, 4, 5 and 6 respectively. For simplicity, these BPs are represented by (SI:BitString), where SI = 0 and BitString is of 8 bits. BPs 1, 2, 3, 4, 5 and 6 are represented by 1 (0:00000001), 2 (0:00000010), 3 (0:00000100), 4 (0:00001000), 5 (0:00010000) and 6 (0:00100000) respectively.¶

                                           6
                                         ( K )
                                          /14'
                                         /
                                   4'   /13'       |         4
                          /-----------( G )--------+       ( H )
                         /                  16'    |________/
                        /                          |       17'
                       /3'                _________|
    5   1'       2'   /            6'    /15'      |     18'
  ( A )------------( B )--------------( C )        +--------( D )
    \10'           7'\    5'            \11'       |          1
     \                \                  \        LAN
      \                \                  \
       \           9'   \8'                \12'
        \--------------( E )              ( F )
                         3                  2

The BitPositions for the forward connected adjacencies are represented by i', where i is from 1 to 18. In one option, they are encoded as (n+i), where n is a power of 2 such as 32768. For simplicity, these BitPositions are represented by (SI:BitString), where SI = (6 + (i-1)/8) and BitString is of 8 bits. BitPositions i' (i from 1 to 18) are represented by 1'(6:00000001), 2'(6:00000010), 3'(6:00000100), 4'(6:00001000), 5'(6:00010000), 6'(6:00100000), 7'(6:01000000), 8'(6:10000000), 9'(7:00000001), 10'(7:00000010), . . . , 16'(7:10000000), 17'(8:00000001), 18'(8:00000010).¶

For a link between two nodes X and Y, there are two BitPositions for two forward connected adjacencies. These two forward connected adjacency BitPositions are assigned on nodes X and Y respectively. The BitPosition assigned on X is the forward connected adjacency of Y. The BitPosition assigned on Y is the forward connected adjacency of X.¶

For example, for the link between nodes B and C in the figure, two forward connected adjacency BitPositions 5' and 6' are assigned to two ends of the link. BitPosition 5' is assigned on node B to B's end of the link. It is the forward connected adjacency of node C. BitPosition 6' is assigned on node C to C's end of the link. It is the forward connected adjacency of node B.¶

For a LAN (i.e., broadcast link) connecting nodes X1, X2, ..., Xm, there are m BitPositions for m forward connected adjacencies. These m forward connected adjacency BitPositions are assigned on nodes X1, X2, ..., Xm respectively.¶

For the LAN connecting 4 nodes C, G, H and D in the figure, 4 forward connected adjacency BitPositions 15', 16', 17' and 18' are assigned to C, G, H and D respectively.¶

2.2. BIER-TE BIFT on BFR

Every BFR in a BIER-TE domain/topology has a BIER-TE BIFT. This section shows the BIER-TE BIFT on every BFR/node of the BIER-TE topology with LAN in Figure 1.¶

For the BIER-TE topology in Figure 1, each of 9 nodes/BFRs A, B, C, D, E, F, G, H and K has its BIER-TE BIFT for the topology. The BIFT on a BFR comprises a forwarding entry for each of the adjacencies of the BFR.¶

The BIER-TE BIFT on BFR A (i.e., node A) is shown in Figure 2. There are three adjacencies of A. The 1st one is the forward connected adjacency from A to B (represented by BP 2'); the 2nd is the forward connected adjacency from A to E (represented by BP 9'); the 3rd is the local decap adjacency (represented by BP 5) for BFER (i.e., egress) A. The BIFT on A has three forwarding entries.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           | 2'(6:00000010)  | fw-connected |     B      |
           +-----------------+--------------+------------+
           | 9'(7:00000001)  | fw-connected |     E      |
           +-----------------+--------------+------------+
           | 5 (0:00010000)  | local-decap  |            |
           +-----------------+--------------+------------+

The 1st forwarding entry in the BIFT is for BitPosition 2', which is the forward connected adjacency from A to B. For a multicast packet with BitPosition 2', which indicates that the P2MP path in the packet traverses the adjacency from A to B, the forwarding entry forwards the packet to B along the link from A to B.¶

The 2nd forwarding entry in the BIFT is for BitPosition 9', which is the forward connected adjacency from A to E. For a multicast packet with BitPosition 9', which indicates that the P2MP path in the packet traverses the adjacency from A to E, the forwarding entry forwards the packet to E along the link from A to E.¶

The 3rd forwarding entry in the BIFT locally decapsulates a multicast packet with BitPosition 5 and passes a copy of the payload of the packet to the packet's NextProto. It is for BitPosition 5, which is the local decap adjacency for BFER (i.e., egress) A. For a multicast packet with BitPosition 5, which indicates that the P2MP path in the packet has node A as one of its destinations (i.e., egress nodes), the forwarding entry decapsulates the packet and passes a copy of the payload of the packet to the packet's NextProto within node A.¶

The BIER-TE BIFT on BFR B (i.e., node B) is shown in Figure 3. There are four forward connected adjacencies of B. They are the forward connected adjacencies from B to A (represented by BP 1'), B to G (represented by BP 4'), B to C (represented by BP 6') and B to E (represented by BP 8') respectively. The BIFT on B has four forwarding entries for these adjacencies.¶

           +----------------+--------------+------------+
           |  Adjacency BP  |    Action    |  BFR-NBR   |
           | (SI:BitString) |              | (Next Hop) |
           +================+==============+============+
           | 1'(6:00000001) | fw-connected |     A      |
           +----------------+--------------+------------+
           | 4'(6:00001000) | fw-connected |     G      |
           +----------------+--------------+------------+
           | 6'(6:00100000) | fw-connected |     C      |
           +----------------+--------------+------------+
           | 8'(6:10000000) | fw-connected |     E      |
           +----------------+--------------+------------+

The 1st forwarding entry in the BIFT is for BitPosition 1', which is the forward connected adjacency from B to A. For a multicast packet with BitPosition 1', which indicates that the P2MP path in the packet traverses the adjacency from B to A, the forwarding entry forwards the packet to A along the link from B to A.¶

The 2nd forwarding entry in the BIFT is for BitPosition 4', which is the forward connected adjacency from B to G. For a multicast packet with BitPosition 4', which indicates that the P2MP path in the packet traverses the adjacency from B to G, the forwarding entry forwards the packet to G along the link from B to G.¶

The 3rd forwarding entry in the BIFT is for BitPosition 6', which is the forward connected adjacency from B to C. For a multicast packet with BitPosition 6', which indicates that the P2MP path in the packet traverses the adjacency from B to C, the forwarding entry forwards the packet to C along the link from B to C.¶

The 4-th forwarding entry in the BIFT is for BitPosition 8', which is the forward connected adjacency from B to E. For a multicast packet with BitPosition 8', which indicates that the P2MP path in the packet traverses the adjacency from B to E, the forwarding entry forwards the packet to E along the link from B to E.¶

The BIER-TE BIFT on BFR C (i.e., node C) is shown in Figure 4. There are five forward connected adjacencies of C. They are the forward connected adjacencies from C to B (represented by BP 5'), C to F (represented by BP 12'), C to G (represented by BP 14'), C to H (represented by BP 15') and C to D (represented by BP 16') respectively. The BIFT on C has five forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           |  5'(6:00010000) | fw-connected |     B      |
           +-----------------+--------------+------------+
           | 12'(7:00001000) | fw-connected |     F      |
           +-----------------+--------------+------------+
           | 16'(7:10000000) | fw-connected |     G      |
           +-----------------+--------------+------------+
           | 17'(8:00000001) | fw-connected |     H      |
           +-----------------+--------------+------------+
           | 18'(8:00000010) | fw-connected |     D      |
           +-----------------+--------------+------------+

The BIER-TE BIFT on BFR D (i.e., node D) is shown in Figure 5. There are four adjacencies of D. Three of them are the forward connected adjacencies from D to C (represented by BP 13'), D to G (represented by BP 14') and D to H (represented by BP 15') respectively; the other is the local decap adjacency (represented by BP 1) for BFER (i.e., egress) D. The BIFT on D has four forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           | 15'(7:01000000) | fw-connected |     C      |
           +-----------------+--------------+------------+
           | 16'(7:10000000) | fw-connected |     G      |
           +-----------------+--------------+------------+
           | 17'(8:00000001) | fw-connected |     H      |
           +-----------------+--------------+------------+
           |  1 (0:00000001) | local-decap  |            |
           +-----------------+--------------+------------+

The BIER-TE BIFT on BFR E (i.e., node E) is shown in Figure 6. There are three adjacencies of E. Two of them are the forward connected adjacencies from E to B (represented by BP 7') and E to A (represented by BP 10') respectively; the other is the local decap adjacency (represented by BP 3) for BFER (i.e., egress) E. The BIFT on E has three forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           |  7'(6:01000000) | fw-connected |     B      |
           +-----------------+--------------+------------+
           | 10'(7:00000010) | fw-connected |     A      |
           +-----------------+--------------+------------+
           |  3 (0:00000100) | local-decap  |            |
           +-----------------+--------------+------------+

The BIER-TE BIFT on BFR F (i.e., node F) is shown in Figure 7. There are two adjacencies of F. The 1st one is the forward connected adjacencies from F to C (represented by BP 11'); the 2nd is the local decap adjacency (represented by BP 2) for BFER (i.e., egress) F. The BIFT on F has two forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           | 11'(7:00000100) | fw-connected |     C      |
           +-----------------+--------------+------------+
           |  2 (0:00000010) | local-decap  |            |
           +-----------------+--------------+------------+

The BIER-TE BIFT on BFR G (i.e., node G) is shown in Figure 8. There are four forward connected adjacencies of G. They are the adjacencies from G to B (represented by BP 3'), G to C (represented by BP 13'), G to H (represented by BP 15') and G to D (represented by BP 16') respectively. The BIFT on G has four forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           |  3'(6:00000100) | fw-connected |     B      |
           +-----------------+--------------+------------+
           | 14'(7:00100000) | fw-connected |     K      |
           +-----------------+--------------+------------+
           | 15'(7:01000000) | fw-connected |     C      |
           +-----------------+--------------+------------+
           | 17'(8:00000001) | fw-connected |     H      |
           +-----------------+--------------+------------+
           | 18'(8:00000010) | fw-connected |     D      |
           +-----------------+--------------+------------+

The BIER-TE BIFT on BFR H (i.e., node H) is shown in Figure 9. There are four adjacencies of H. Three of them are the forward connected adjacencies from H to C (represented by BP 13'), H to G (represented by BP 14') and H to D (represented by BP 16') respectively; the other is the local decap adjacency (represented by BP 4) for BFER (i.e., egress) H. The BIFT on H has four forwarding entries for these adjacencies.¶

           +-----------------+--------------+------------+
           |  Adjacency BP   |    Action    |  BFR-NBR   |
           | (SI:BitString)  |              | (Next Hop) |
           +=================+==============+============+
           | 15'(7:01000000) | fw-connected |     C      |
           +-----------------+--------------+------------+
           | 16'(7:10000000) | fw-connected |     G      |
           +-----------------+--------------+------------+
           | 18'(8:00000010) | fw-connected |     D      |
           +-----------------+--------------+------------+
           |  4 (0:00001000) | local-decap  |            |
           +-----------------+--------------+------------+

2.3. Example P2MP Path with LAN

This section presents the issue about receiving duplicated packets at BFER H for any explicit P2MP path/tree from BFIR A to BFERs K, H and F in Figure 1 with minimum height of the tree, which is 3 (hops). Any path will go through the LAN in order to reach BFER H.¶

There are only following explicit P2MP paths from A to K, H and D.¶

               K                                   K
              /14'         H                      /14'
             /        |___/17'                   /               H
            G---------|                         G          |____/17'
           /4'       LAN                       /4'        _|
      2'  /      6'                       2'  /      6'  / |
A--------B----------C               A--------B----------C  LAN
                     \                                   \
                      \12'                                \12'
                       F                                   F

Path 1 from A to K, H and F         Path 2 from A to K, H and F

Path 1 and path 2 are represented by {2', 4', 6', 12', 14', 17', 2, 4, 6}. Path 1 traverses the link/adjacency from A to B (indicated by BP 2'), the link/adjacency from B to G (indicated by BP 4'), the link/adjacency from B to C (indicated by BP 6'), the link/adjacency from G to K (indicated by BP 14'), the link/adjacency from G to H (indicated by BP 17') [the link/adjacency from C to H (also indicated by BP 17') for Path 2], and the link/adjacency from C to F (indicated by BP 12'). Path 1 is represented by {2', 4', 6', 12', 14', 17', 2, 4, 6}. Path 2 has the same representation. The packet at A has this representation.¶

For the packet with the P2MP path, A forwards the packet to B according to the forwarding entry for BP 2' in its BIFT.¶

After receiving the packet from A, B forwards the packet to G and C according to the forwarding entries for BPs 4' and 6' in B's BIFT respectively. The packet received by G has path {12', 14', 17', 2, 4, 6}. The packet received by C has path {12', 14', 17', 2, 4, 6}.¶

After receiving the packet from B, G sends a copy of the packet to K according to the forwarding entry for BP 14' in G's BIFT, and another copy of the packet to H according to the forwarding entry for BP 17' in G's BIFT.¶

After receiving the packet from B, C copies and sends the packet to H and F according to the forwarding entries for BPs 17' and 12' in C's BIFT respectively.¶

Egress node H of the P2MP path receives the duplicated packets. One packet is from G, and the same copy is from C.¶

The reasons for the path leading to duplicated packets include:¶

• A BP is local to a node (i.e., for a link connected to the node). Every node X processes only the BPs in a packet for the links connected to node X. For example, node A processes only BP 2' for link from A to B. Node A removes 2' and sends packet to node B according to the entry for 2' in A's BIER-TE BIFT.¶

• Missing or no enough information for broadcast link (LAN). There is a pseudo node for a LAN in IGP (DR in OSPF and DIS in IS-IS) and the pseudo node is connected to each of the nodes on the LAN. The BPs for these links are missing.¶

The solution proposed for LANs in this document resolve this issue. For a packet with an explicit P2MP path traversing LANs (i.e., broadcast links), the packet is replicated and forwarded statelessly along the path. Each of the egress nodes of the path will not receive any duplicated packet.¶

3.1. New BP Assignments for LAN

For all the nodes/BFRs attached to a LAN (i.e., broadcast link), it is assumed that they are connected a pseudo node. In one implementation, the pseudo node is the Designated Router (DR) of the LAN in OSPF or the Designated Intermediate System (DIS) of the LAN in IS-IS.¶

For the connection between the pseudo node and each of the nodes/BFRs attached to a LAN, two BPs are assigned to it. One is for the adjacency from the BFR to the pseudo node, the other is for the adjacency from the pseudo node to the BFR.¶

The adjacency from a BFR to the pseudo node is called a LAN adjacency. The adjacency from the pseudo node to a BFR is a forward connected adjacency.¶

For example, suppose that the pseudo node for the LAN in Figure 1 is Px. The BP assignments for the LAN (i.e., connections between Px and BFRs C, G, H and D) are illustrated in Figure 11.¶

                                           6
                                         ( K )
                                          /14'
                                         /
                                   4'   /13'        |           4
                          /-----------( G )---------+         ( H )
                         /                 17'      |  ________/
                        /                        18'| /20'    19'
                       /3'                _________ Px
    5  1'        2'   /            6'    /15'   16' |22'   21'
  ( A )------------( B )--------------( C )         +---------( D )
    \10'           7'\    5'            \11'                    1
     \                \                  \
      \                \                  \
       \           9'   \8'                \12'
        \--------------( E )              ( F )
                         3                  2

The connection/adjacency from Px to C is assigned BP 15', and the connection/adjacency from C to Px is assigned BP 16'.¶

The connection/adjacency from Px to G is assigned BP 17', and the connection/adjacency from G to Px is assigned BP 18'.¶

The connection/adjacency from Px to H is assigned BP 19', and the connection/adjacency from H to Px is assigned BP 20'.¶

The connection/adjacency from Px to D is assigned BP 21', and the connection/adjacency from D to Px is assigned BP 22'.¶

In an alternative, all the nodes/BFRs attached to a LAN are assumed fully connected each other (i.e., they are fully meshed). For a connection between any two BFRs on the LAN, two forward connected adjacencies are assigned to the two ends of the connection.¶

For example, there are four BFRs C, G, H and D attached to the LAN in Figure 1. There are six connections among these four BFRs. They are connections between C and G, C and H, C and D, G and H, G and D, H and D. Twelve BPs are needed for these six connections.¶

In general, for n BFRs attached to a LAN, there are n*(n-1)/2 connections among these n BFRs and n*(n-1) BPs are needed for these connections. This may not be scalable. But for this alternative, the BIER-TE BIFT on a BFR needs not to be changed except for considering the full mesh connections among the BFRs attached to a LAN.¶

3.3. Updated Forwarding Procedure

The forwarding procedure defined in [RFC9262] is updated/enhanced for using an improved BIER-TE BIFT to support BIER-TE with LAN.¶

The updated procedure is described in Figure 16. For a multicast packet containing the BitString encoding an explicit P2MP path, if the BP in the BitString is for a LAN adjacency to pseudo node Px for the LAN, the updated forwarding procedure on a BFR sends the packet towards Px's next hop nodes on the P2MP path encoded in the packet.¶

The procedure on a BFR "sends" (i.e., works as sending) the packet with the BP for the LAN adjacency to Px according to the forwarding entry for the BP in the improved BIER-TE BIFT on the BFR. And then it acts on Px to "send" (i.e., works as sending) the packet to each of the Px's next hop nodes that are on the P2MP path using the secondary BIFT for Px.¶

It obtains the secondary BIFT for Px on the BFR, clears all the BPs for the adjacencies of the BFR including the adjacency from the BFR to Px, copies and sends the packet to each of the Px's next hop nodes on the P2MP path using the secondary BIFT for Px.¶

For each Px's next hop node on the P2MP path, which is represented by BP j in the packet's BitString, it gets the forwarding entry for BP j from the secondary BIFT for Px, copies the packet, updates the copy's BitString by clearing all the BPs for Px's adjacencies, and sends the updated copy to the next hop node according to the forwarding entry.¶

  Packet = the packet received by BFR;
  FOR each BP k (from the rightmost in Packet's BitString) {
     IF BP k is local decap adjacency (or say BP of BFER) {
        Copies Packet, sends the copy to the multicast
        flow overlay and clears bit k in Packet's BitString
     } ELSE IF BP k is forward connected adjacency of the BFR {
        Finds the forwarding entry in the BIER-TE BIFT using BP k,
        Copies Packet, updates the copy's BitString by
        clearing all the BPs for the adjacencies of the BFR,
        and sends the updated copy to BFR-NBR
     } ELSE IF BP k is LAN adjacency to Px {
        Obtains the secondary BIFT for Px,
        Clears all the BPs for the adjacencies of the BFR,
        FOR each BP j (from the rightmost in Packet's BitString) {
            IF BP j is Px's forward connected adjacency {
                Gets the forwarding entry for BP j in the
                secondary BIFT for Px,
                Copies Packet, updates the copy's BitString by
                clearing all the BPs for Px's adjacencies,
                and sends the updated copy to BFR-NBR
            }
        }
     }
  }

8.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.

[RFC8556]

Rosen, E., Ed., Sivakumar, M., Przygienda, T., Aldrin, S., and A. Dolganow, "Multicast VPN Using Bit Index Explicit Replication (BIER)", RFC 8556, DOI 10.17487/RFC8556, April 2019, <https://www.rfc-editor.org/info/rfc8556>.

[RFC9262]

Eckert, T., Ed., Menth, M., and G. Cauchie, "Tree Engineering for Bit Index Explicit Replication (BIER-TE)", RFC 9262, DOI 10.17487/RFC9262, October 2022, <https://www.rfc-editor.org/info/rfc9262>.

8.2. Informative References

[RFC8296]

Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation for Bit Index Explicit Replication (BIER) in MPLS and Non-MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January 2018, <https://www.rfc-editor.org/info/rfc8296>.