BIER-TE Fast ReRoute

1.1. Terminology

BIER:

Bit Index Explicit Replication.¶

BIER-TE:

BIER Traffic/Tree 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.¶

F-BM:

Forwarding Bit Mask.¶

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.¶

FRR:

Fast Re-Route.¶

PLR:

Point of Local Repair.¶

IGP:

Interior Gateway Protocol.¶

LSDB:

Link State DataBase.¶

SPF:

Shortest Path First.¶

SPT:

Shortest Path Tree.¶

3.1. Extensions to BIER-TE BIFT

Every BFR has an extended BIER-TE BIFT to support BIER-TE FRR protection against the failure of its neighbor transit node. The forwarding entry with transit node (say N) as its BFR-NBR in the BIFT comprises a FRR forwarding entry (or FRR entry for short). The FRR entry contains a flag FPA (which is short for FRR Protection is Active) and a backup path from the BFR to each of N's next hop nodes.¶

In normal operations, the flag FPA in the FRR entry for neighbor transit node N is set to 0 (zero). The flag FPA is set to 1 (one) when transit node N fails. FPA == 1 means that the FRR protection for transit node N is active and the FRR entry will be used to forward the packet with the BP for the adjacency from the BFR to node N towards N's next hop nodes on the P2MP path encoded in the packet's BitString along the backup paths.¶

The backup path from the BFR to a N's next hop node X is a path that satisfies a set of constraints and does not traverse transit node N or any link connected to N. In one implementation, the backup path is represented by the BitPositions for the adjacencies along the backup path.¶

3.2. Updated Forwarding Procedure

The forwarding procedure defined in [I-D.ietf-bier-te-arch] is updated/enhanced for using an extended BIER-TE BIFT to support BIER-TE FRR.¶

For a multicast packet with the BP in the BitString indicating a BFR-NBR as a transit node of the P2MP path encoded in the packet, the updated forwarding procedure on a BFR sends the packet towards the transit node's next hop nodes on the P2MP path if the transit node fails.¶

It checks whether FPA equals to 1 (one) in the forwarding entry with the BFR-NBR that is a transit node of the P2MP path. If FPA is 1 (i.e., the transit node fails and the FRR protection for the transit node is active), the procedure clears the BP for the adjacency to the transit node in the packet's BitString first. Secondly, for any local decap BP for a destination/BFER in the BitString, it removes/clears the BP if the BP is on the backup path and is not reachable by the forward connected adjacency BPs in the BitString (i.e., is not on any branch from the BFR as PLR). And then, for each next hop node of the failed transit node that is on the P2MP path encoded in the packet's BitString, it copies and sends the packet to the next hop node along the backup path from the BFR to the next hop node.¶

For each next hop node of transit node BFR-NBR (which is named as N for simplicity), when N's next hop node is on the P2MP path, the forwarding procedure clears the BP for the adjacency from N to the N's next hop node in the packet's BitString and adds the BPs for the backup path from the BFR to the N's next hop node. This lets the packet be copied and sent to the N's next hop nodes along the backup paths when transit node N fails and then towards the destinations along the P2MP path.¶

The updated procedure is described in Figure 1. It can also be used by the BFR to forward multicast packets in normal operations.¶

  Packet = the packet received by BFR;
  FOR each BP k (from the rightmost in Packet's BitString) {
     IF (BP k is local decap adjacency) {
        copies Packet, sends the copy to the multicast
        flow overlay and clears bit k in Packet's BitString
     } ELSE IF (BP k is forward connect adjacency of the BFR) {
        finds the forwarding entry in the BIER-TE BIFT for the domain
        using BP k;
        Clears BP k in Packet's BitString;
        IF (FPA == 1) {//FRR for BFR-NBR/transit N is Active
           FOR each BP j for a BFER in Packet's BitString {
              IF (BP j is on a backup path and
                       is not reachable by BPs in BitString) {
                 Clears BP j in Packet's BitString
              }
           }
           FOR each N's next hop on P2MP path in Packet's BitString {
              Clears the BP for the adjacency from N to the next hop;
              Adds the BPs for the backup path to N's next hop
              into Packet's BitString
           }
        } //Adjacency to N removed, backup path to N's next hop added
        ELSE {
           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
        }
     }
  }

4.1. Example BIER-TE Topology

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

                           26'       19'       20'    4
        /--------------------(  G  )---------------(  H  )
       /                    /  18'\               16'/|28'
      /                  6'/       \17'             / |
     /            ________/       ( I )____________/  |
 25'/            /             14'/      15'          |
   /          5'/                /                    |
  /   8'   7'  /    3'     4'   /13'           12'    |27'
( A )--------( B )------------( C )-----------------( D ) 1
  5            \1'              \9'   11'            /24'
                \                \                  /
                 \2'   21'   22'  \10'             /
                ( E )------------( F )____________/
                  3                2   23'

The BitPositions for the forward connected adjacencies are represented by i', where i is from 1 to 28. 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 28) 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), . . . , 24'(8:10000000) 25'(9:00000001), 26'(9:00000010), ..., 28'(9:00001000).¶

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 3' and 4' are assigned to two ends of the link. BitPosition 3' is assigned on node B to B's end of the link. It is the forward connected adjacency of node C. BitPosition 4' is assigned on node C to C's end of the link. It is the forward connected adjacency of node B.¶

4.2. BIER-TE BIFT on a BFR

Every BFR in a BIER-TE domain/topology has a BIER-TE BIFT. For the BIER-TE topology in Figure 2, each of 9 nodes/BFRs A, B, C, D, E, F, G, H and I has its BIER-TE BIFT for the topology.¶

The BIER-TE BIFT on BFR B (i.e. node B) is shown in Figure 3.¶

The 1st forwarding entry in the BIFT is for BitPosition 2', which is the forward connected adjacency from B to E. For a multicast packet with BitPosition 2', 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 2nd forwarding entry in the BIFT is for BitPosition 4', which is the forward connected adjacency from B to C. For a multicast packet with BitPosition 4', 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 3rd forwarding entry in the BIFT is for BitPosition 6', which is the forward connected adjacency from B to G. For a multicast packet with BitPosition 6', 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 4-th forwarding entry in the BIFT is for BitPosition 8', which is the forward connected adjacency from B to A. For a multicast packet with BitPosition 8', 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.¶

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

The BIER-TE BIFT on BFR E (i.e. node E) is shown in Figure 4.¶

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

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

The 3rd forwarding entry in the BIFT locally decapsulates a multicast packet with BitPosition 3 and passes a copy of the payload of the packet to the packet's NextProto. It is for BitPosition 3, which is the local decap adjacency for BFER (i.e., egress) E. For a multicast packet with BitPosition 3, which indicates that the P2MP path in the packet has node E 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 E.¶

 +----------------+--------------+------------+
 |  Adjacency BP  |    Action    |  BFR-NBR   |
 | (SI:BitString) |              | (Next Hop) |
 +================+==============+============+
 |  1'(6:00000001)| fw-connected |     B      |
 +----------------+--------------+------------+
 | 22'(8:00001000)| fw-connected |     F      |
 +----------------+--------------+------------+
 |  3 (0:00000100)| local-decap  |            |
 +----------------+--------------+------------+

4.3. Extended BIER-TE BIFT on a BFR

Every BFR has an extended BIER-TE BIFT to support BIER-TE FRR protection against the failure of its neighbor transit node.¶

For example, the extended BIER-TE BIFT on BFR B is illustrated in Figure 5. Each forwarding entry with transit node (such as E, C and G) as its BFR-NBR in the BIFT comprises a FRR entry. Each of these FRR entries contains a flag FPA and a number of backup paths. For a forwarding entry with transit node X, its FRR entry has a backup path to each of node X's next hop nodes except for BFR B itself. FPA is set to zero in normal operations. FPA in the FRR entry for neighbor transit node X is set to one when node X fails.¶

On BFR B, the 1st forwarding entry in the BIFT has BFR-NBR E as transit node. Nodes F and B are the next hop nodes of node E in Figure 2. The backup path from B to F without E or links attached to E goes through the link from B to C and then the link from C to F. This backup path from B to F is represented by B-->F: {4', 10'} in the FRR entry of the forwarding entry.¶

FPA in the FRR entry is set to 0 (zero) in normal operations. When transit node E fails, the FPA is set to 1 (one) and the FRR entry is used to forward a multicast packet with BitPosition 2' for adjacency from B to E towards E's next hop node F along the backup path from B to F if the P2MP path in the packet traverses node F.¶

+--------------+------------+----------+------------------------+
| Adjacency BP |   Action   | BFR-NBR  |     FRR Entry          |
|(SI:BitString)|            |(Next Hop)|---+--------------------+
|              |            |          |FPA|  Backup Paths      |
+==============+============+==========+===+====================+
|2'(6:00000010)|fw-connected|    E     | 0 |B-->F: {4',10'}     |
+--------------+------------+----------+---+--------------------+
|4'(6:00000010)|fw-connected|    C     | 0 |B-->F: {2',22'}     |
|              |            |          |   |B-->D: {6',20',27'} |
|              |            |          |   |B-->I: {6',17'}     |
+--------------+------------+----------+---+--------------------+
|6'(6:00100000)|fw-connected|    G     | 0 |B-->I: {4',14'}     |
|              |            |          |   |B-->H: {4',14',16'} |
|              |            |          |   |B-->A: {8'}         |
+--------------+------------+----------+---+--------------------+
|8'(6:10000000)|fw-connected|    A     | 0 |B-->G: {6'}         |
+--------------+------------+----------+---+--------------------+

On BFR B, the 2nd forwarding entry in the BIFT has BFR-NBR C as transit node. Nodes F, D, I and B are the next hop nodes of node C in Figure 2. The backup path from B to F without C or links attached to C goes through the link from B to E and then the link from E to F. This backup path from B to F is represented by B-->F: {2', 22'} in the FRR entry of the forwarding entry.¶

The backup path from B to D without C or links attached to C goes through the link from B to G, the link from G to H and then the link from H to D. This backup path from B to D is represented by B-->D: {6', 20', 27'} in the FRR entry of the forwarding entry.¶

The backup path from B to I without C or links attached to C goes through the link from B to G and then the link from G to I. This backup path from B to I is represented by B-->I: {6', 17'} in the FRR entry of the forwarding entry.¶

FPA in the FRR entry is set to 0 (zero) in normal operations. When transit node C fails, the FPA is set to 1 (one) and the FRR entry is used to forward a multicast packet with BitPosition 4' for adjacency from B to C towards C's next hop nodes F, D or I along the backup paths from B to F, D or I respectively if the P2MP path in the packet traverses nodes F, D or I.¶

On BFR B, the 3rd forwarding entry in the BIFT has BFR-NBR G as transit node. Nodes I, H, A and B are the next hop nodes of node G in Figure 2. The backup path from B to I without G or links attached to G goes through the link from B to C and then the link from C to I. This backup path from B to I is represented by B-->I: {4', 14'} in the FRR entry of the forwarding entry.¶

The backup path from B to H without G or links attached to G goes through the link from B to C, the link from C to I and then the link from I to H. This backup path from B to H is represented by B-->H: {4', 14', 16'} in the FRR entry of the forwarding entry.¶

The backup path from B to A without G or links attached to G goes through the link from B to A. This backup path from B to A is represented by B-->A: {8'} in the FRR entry of the forwarding entry.¶

FPA in the FRR entry is set to 0 (zero) in normal operations. When transit node G fails, the FPA is set to 1 (one) and the FRR entry is used to forward a multicast packet with BitPosition 6' for adjacency from B to G towards G's next hop nodes I, H or A along the backup paths from B to I, H or A respectively if the P2MP path in the packet traverses nodes I, H or A.¶

On BFR B, the 4-th forwarding entry in the BIFT has BFR-NBR A as transit node. Nodes G and B are the next hop nodes of node A. The backup path from B to G without A or links attached to A goes through the link from B to G. This backup path from B to G is represented by B-->G: {6'} in the FRR entry of the forwarding entry.¶

FPA in the FRR entry is set to 0 (zero) in normal operations. When node A fails, the FPA is set to 1 (one) and the FRR entry is used to forward a multicast packet with BitPosition 8' for adjacency from B to A towards A's next hop node G along the backup path from B to G if the P2MP path in the packet traverses node A as a transit node.¶

4.4. Forwarding using Extended BIER-TE BIFT

Suppose that there is an explicit multicast P2MP path from ingress A to egresses H and D, traversing from A to G to H and from A to B to C to D. This path is represented by BPs as {26', 20', 7', 4', 12', 4, 1}. The forwarding behaviors in normal operations and in case of BFR C failure are described below.¶

8.1. Normative References

[I-D.ietf-bier-te-arch]

Eckert, T., Cauchie, G., and M. Menth, "Tree Engineering for Bit Index Explicit Replication (BIER-TE)", Work in Progress, Internet-Draft, draft-ietf-bier-te-arch-10, 9 July 2021, <https://www.ietf.org/archive/id/draft-ietf-bier-te-arch-10.txt>.

[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>.

[RFC5226]

Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 5226, DOI 10.17487/RFC5226, May 2008, <https://www.rfc-editor.org/info/rfc5226>.

[RFC5250]

Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, July 2008, <https://www.rfc-editor.org/info/rfc5250>.

[RFC5286]

Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for IP Fast Reroute: Loop-Free Alternates", RFC 5286, DOI 10.17487/RFC5286, September 2008, <https://www.rfc-editor.org/info/rfc5286>.

[RFC5714]

Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 5714, DOI 10.17487/RFC5714, January 2010, <https://www.rfc-editor.org/info/rfc5714>.

[RFC5880]

Katz, D. and D. Ward, "Bidirectional Forwarding Detection (BFD)", RFC 5880, DOI 10.17487/RFC5880, June 2010, <https://www.rfc-editor.org/info/rfc5880>.

[RFC7356]

Ginsberg, L., Previdi, S., and Y. Yang, "IS-IS Flooding Scope Link State PDUs (LSPs)", RFC 7356, DOI 10.17487/RFC7356, September 2014, <https://www.rfc-editor.org/info/rfc7356>.

[RFC7490]

Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490, DOI 10.17487/RFC7490, April 2015, <https://www.rfc-editor.org/info/rfc7490>.

[RFC7684]

Psenak, P., Gredler, H., Shakir, R., Henderickx, W., Tantsura, J., and A. Lindem, "OSPFv2 Prefix/Link Attribute Advertisement", RFC 7684, DOI 10.17487/RFC7684, November 2015, <https://www.rfc-editor.org/info/rfc7684>.

[RFC7770]

Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and S. Shaffer, "Extensions to OSPF for Advertising Optional Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, February 2016, <https://www.rfc-editor.org/info/rfc7770>.

[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>.

[RFC8279]

Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., Przygienda, T., and S. Aldrin, "Multicast Using Bit Index Explicit Replication (BIER)", RFC 8279, DOI 10.17487/RFC8279, November 2017, <https://www.rfc-editor.org/info/rfc8279>.

[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>.

8.2. Informative References

[I-D.eckert-bier-te-frr]

Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Protection Methods for BIER-TE", Work in Progress, Internet-Draft, draft-eckert-bier-te-frr-03, 5 March 2018, <https://www.ietf.org/archive/id/draft-eckert-bier-te-frr-03.txt>.

[I-D.ietf-rtgwg-segment-routing-ti-lfa]

Litkowski, S., Bashandy, A., Filsfils, C., Francois, P., Decraene, B., and D. Voyer, "Topology Independent Fast Reroute using Segment Routing", Work in Progress, Internet-Draft, draft-ietf-rtgwg-segment-routing-ti-lfa-07, 29 June 2021, <https://www.ietf.org/archive/id/draft-ietf-rtgwg-segment-routing-ti-lfa-07.txt>.

[I-D.ietf-spring-segment-protection-sr-te-paths]

Hegde, S., Bowers, C., Litkowski, S., Xu, X., and F. Xu, "Segment Protection for SR-TE Paths", Work in Progress, Internet-Draft, draft-ietf-spring-segment-protection-sr-te-paths-01, 11 July 2021, <https://www.ietf.org/archive/id/draft-ietf-spring-segment-protection-sr-te-paths-01.txt>.

[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>.

[RFC8401]

Ginsberg, L., Ed., Przygienda, T., Aldrin, S., and Z. Zhang, "Bit Index Explicit Replication (BIER) Support via IS-IS", RFC 8401, DOI 10.17487/RFC8401, June 2018, <https://www.rfc-editor.org/info/rfc8401>.

[RFC8444]

Psenak, P., Ed., Kumar, N., Wijnands, IJ., Dolganow, A., Przygienda, T., Zhang, J., and S. Aldrin, "OSPFv2 Extensions for Bit Index Explicit Replication (BIER)", RFC 8444, DOI 10.17487/RFC8444, November 2018, <https://www.rfc-editor.org/info/rfc8444>.