idnits 2.17.1 draft-chen-bier-frr-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([RFC8279]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 2, 2021) is 1021 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-07) exists of draft-chen-bier-egress-protect-01 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-segment-routing-ti-lfa-06 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Chen, Ed. 3 Internet-Draft M. McBride 4 Intended status: Informational Futurewei 5 Expires: January 3, 2022 S. Lindner 6 M. Menth 7 University of Tuebingen 8 A. Wang 9 China Telecom 10 G. Mishra 11 Verizon Inc. 12 Y. Liu 13 China Mobile 14 Y. Fan 15 Casa Systems 16 L. Liu 17 Fujitsu 18 X. Liu 19 Volta Networks 20 July 2, 2021 22 BIER Fast ReRoute 23 draft-chen-bier-frr-03 25 Abstract 27 BIER is a scalable multicast overlay [RFC8279] that utilizes a 28 routing underlay, e.g., IP, to build up its Bit Index Forwarding 29 Tables (BIFTs). This document proposes Fast Reroute Extensions for 30 BIER (BIER-FRR). It protects BIER traffic after detecting the 31 failure of a link or node in the core of a BIER domain until affected 32 BIFT entries are recomputed after reconvergence of the routing 33 underlay. The BIER-FRR extensions are applied locally at the point 34 of local repair (PLR) and do not introduce any per-flow state. The 35 document specifies nomenclature for BIER-FRR and gives examples for 36 its integration in BIER forwarding. Furthermore, it presents 37 operation modes for BIER-FRR. Link and node protection may be chosen 38 as protection level. Moreover, the backup strategies tunnel-based 39 BIER-FRR and LFA-based BIER-FRR are defined and compared. 41 Requirements Language 43 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 44 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 45 document are to be interpreted as described in [RFC2119] [RFC8174] 46 when, and only when, they appear in all capitals, as shown here. 48 Status of This Memo 50 This Internet-Draft is submitted in full conformance with the 51 provisions of BCP 78 and BCP 79. 53 Internet-Drafts are working documents of the Internet Engineering 54 Task Force (IETF). Note that other groups may also distribute 55 working documents as Internet-Drafts. The list of current Internet- 56 Drafts is at https://datatracker.ietf.org/drafts/current/. 58 Internet-Drafts are draft documents valid for a maximum of six months 59 and may be updated, replaced, or obsoleted by other documents at any 60 time. It is inappropriate to use Internet-Drafts as reference 61 material or to cite them other than as "work in progress." 63 This Internet-Draft will expire on January 3, 2022. 65 Copyright Notice 67 Copyright (c) 2021 IETF Trust and the persons identified as the 68 document authors. All rights reserved. 70 This document is subject to BCP 78 and the IETF Trust's Legal 71 Provisions Relating to IETF Documents 72 (https://trustee.ietf.org/license-info) in effect on the date of 73 publication of this document. Please review these documents 74 carefully, as they describe your rights and restrictions with respect 75 to this document. Code Components extracted from this document must 76 include Simplified BSD License text as described in Section 4.e of 77 the Trust Legal Provisions and are provided without warranty as 78 described in the Simplified BSD License. 80 Table of Contents 82 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 83 2. Extensions for BIER-FRR . . . . . . . . . . . . . . . . . . . 5 84 2.1. Definition of Forwarding Actions . . . . . . . . . . . . 5 85 2.2. Definition of Backup Forwarding Entries . . . . . . . . . 5 86 2.3. Activating and Deactivating Backup Forwarding Entries . . 6 87 2.4. Computation of the Backup F-BM . . . . . . . . . . . . . 7 88 3. Representations for BIER-FRR Forwarding Data . . . . . . . . 7 89 3.1. Potential Emergence of Redundant Packets . . . . . . . . 7 90 3.2. Primary BIFT and Single Backup BIFT . . . . . . . . . . . 9 91 3.3. Primary BIFT and Failure-Specific Backup BIFTs . . . . . 10 92 4. Protection Levels . . . . . . . . . . . . . . . . . . . . . . 11 93 4.1. Link Protection . . . . . . . . . . . . . . . . . . . . . 11 94 4.2. Node Protection . . . . . . . . . . . . . . . . . . . . . 12 95 4.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 12 97 5. Backup Strategies . . . . . . . . . . . . . . . . . . . . . . 12 98 5.1. Tunnel-Based BIER-FRR . . . . . . . . . . . . . . . . . . 12 99 5.1.1. Tunnel-Based BIER-FRR with Link Protection . . . . . 13 100 5.1.2. Tunnel-Based BIER-FRR with Node Protection . . . . . 14 101 5.1.3. Implementation Experience . . . . . . . . . . . . . . 16 102 5.2. LFA-based BIER-FRR . . . . . . . . . . . . . . . . . . . 16 103 5.2.1. Relation of BIER-LFAs to IP-LFAs and Prerequisites . 16 104 5.2.2. Definition of BIER-LFAs . . . . . . . . . . . . . . . 16 105 5.2.3. Protection Coverage of BIER-LFA Types . . . . . . . . 17 106 5.2.4. Sets of Supported BIER-LFAs . . . . . . . . . . . . . 18 107 5.2.5. Link Protection . . . . . . . . . . . . . . . . . . . 18 108 5.2.6. Node Protection . . . . . . . . . . . . . . . . . . . 20 109 5.2.7. Optimization Potential to Reduce Redundant BIER 110 Packets in Failure Cases . . . . . . . . . . . . . . 22 111 6. Comparison . . . . . . . . . . . . . . . . . . . . . . . . . 22 112 6.1. Comparison of LFA-Based Protection for IP-FRR and BIER- 113 FRR . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 114 6.2. Advantages and Disadvantages of Tunnel-Based BIER-FRR . . 23 115 6.2.1. Advantages . . . . . . . . . . . . . . . . . . . . . 23 116 6.2.2. Disadvantages . . . . . . . . . . . . . . . . . . . . 23 117 6.3. Advantages and Disadvantages of LFA-Based BIER-FRR . . . 24 118 6.3.1. Advantages . . . . . . . . . . . . . . . . . . . . . 24 119 6.3.2. Disadvantages . . . . . . . . . . . . . . . . . . . . 24 120 7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 121 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 122 9. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 25 123 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 124 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 125 11.1. Normative References . . . . . . . . . . . . . . . . . . 25 126 11.2. Informative References . . . . . . . . . . . . . . . . . 26 127 Appendix A. Specific Backup Strategy Examples . . . . . . . . . 26 128 A.1. LFA-based BIER-FRR using Single BIFT . . . . . . . . . . 26 129 A.2. LFA-based BIER-FRR using Multiple Backup BIFTs . . . . . 28 130 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 132 1. Introduction 134 With BIER [RFC8279], a Bit-Forwarding Router (BFR) forwards BIER 135 packets based on a bitstring in the BIER header using the information 136 in the Bit Index Forwarding Table (BIFT). Its entries are locally 137 derived from a routing underlay or set by a controller. In case of a 138 persistent link or node failure, BIER traffic may not be delivered 139 until the BIFT has been updated based on the reconverged routing 140 underlay or by the controller. 142 BIER packets are usually forwarded without an outer IP header. If a 143 link or node fails, the corresponding BFR neighbor (BFR-NBR) is no 144 longer reachable. Fast reroute (FRR) mechanisms in the routing 145 underlay, e.g., IP-FRR, apply only to IP packets so that BIER traffic 146 would be dropped. BIER traffic can be delivered again only after 147 reconvergence of the routing underlay and recalculation of the BIFT. 148 Thus, tunneling BIER packets can help to reach the BFR-NBR in case of 149 a link failure by leveraging FRR capabilities of the routing underlay 150 if such mechanisms are available. However, this does not help in 151 case of a node failure. Then, all destinations having the failed 152 node as BFR-NBR cannot be reached anymore. As BIER carries multicast 153 traffic which has often realtime requirements, there is a particular 154 need to protect BIER traffic against too long outages after failures. 156 In this document we propose nomenclature for Fast Reroute Extensions 157 for BIER (BIER-FRR). As soon as a BFR detects a BFR-NBR is 158 unreachable, BIER-FRR enables a BFR to quickly reroute affected BIER 159 packets with the help of backup forwarding entries. To avoid 160 redundant packets, backup forwarding entries should be processed 161 prior to normal forwarding entries. To achieve that goal, two 162 possible representations for backup forwarding entries are proposed. 164 The protection level can be either link protection or node 165 protection. Link protection protects only the failure of a link. It 166 is simple but may not work if a BFR fails. Node protection is more 167 complex but also protects against the failure of BFRs. The backup 168 strategy determines the selection of the backup forwarding entries. 170 Examples for backup strategies are tunnel-based BIER-FRR and LFA- 171 based BIER-FRR 173 o Tunnel-based BIER-FRR leverages mechanisms of the routing underlay 174 for FRR purposes. The routing underlay restores connectivity 175 faster than BIER as a reconverged routing underlay is prerequisite 176 for recalculation of the BIFT. If the routing underlay leverages 177 FRR mechanisms, its forwarding ability is restored long before 178 reconvergence is completed. To leverage fast restoration of the 179 routing underlay, BIER traffic affected by a failure is tunneled 180 over the routing underlay. 182 o LFA-based BIER-FRR reroutes BIER traffic to alternative neighbors 183 in case of a failure. It utilizes the principles of IP-FRR but 184 requires that LFAs are BFRs. Normal BIER-LFAs can be reached 185 without tunneling, remote BIER-LFAs utilize a tunnel, and 186 topology-independent BIER-LFAs leverage explicit paths to reach 187 the backup BFR-NBR. In contrast to tunnel-based FRR, LFA-based 188 BIER-FRR does not require fast reroute mechanisms in the routing 189 underlay. 191 BIER-FRR as presented in this document follows a primary/backup path 192 principle, also known as 1:1 protection. It is opposite to 1+1 193 protection which denotes a live-live protection principle. This has 194 been considered for BIER in [BrAl17]. 196 2. Extensions for BIER-FRR 198 In this section, forwarding actions and backup forwarding entries are 199 defined. Then, the computation of the backup F-BM and the BIER 200 forwarding process with BIER-FRR are explained. 202 2.1. Definition of Forwarding Actions 204 A BFR-NBR is directly connected if it is a next hop on the network 205 layer, i.e., if it can be reached via the link layer technology. 206 Otherwise, the BFR-NBR is indirectly connected. 208 We define the following forwarding actions. 210 o Plain: Sends the mere BIER packet to a BFR-NBR via a direct link 211 and without a tunnel header. That means, the packet is not sent 212 over the routing underlay. 214 o Tunnel: Encapsulates the BIER packet with a tunnel header towards 215 a BFR-NBR and sends it over the routing underlay. 217 o Explicit: Forwards the packet over an explicit path to a BFR-NBR. 218 The path information must be given. If segment routing is used 219 for this purpose, the segment IDs (SIDs) must be given. Two 220 forwarding actions of type Explicit are equal only if they share 221 the same explicit path. 223 The forwarding actions in the BIFT as proposed in [RFC8279] are given 224 implicitly as they are derived from the connectedness of the BFR-NBR. 225 If the BFR-NBR is directly connected, the forwarding action is Plain. 226 If the BFR-NBR is not directly connected, the forwarding action is 227 Tunnel. 229 2.2. Definition of Backup Forwarding Entries 231 The BIFT as proposed in [RFC8279] contains a F-BM and a BFR-NBR for a 232 specific BFER. They constitute a primary forwarding entry. BIER-FRR 233 extends this regular BIFT by additional columns containing backup 234 forwarding entries. A backup forwarding entry contains 236 o a backup F-BM (BF-BM), 238 o a backup BFR-NBR (BBFR-NBR), 240 o a backup forwarding action (BFA), and 241 o a backup entry active (BEA) flag. 243 Backup F-BM and backup BFR-NBR have the same structure as their 244 primary counterparts. The backup forwarding action is a forwarding 245 action as defined in Section 2.1. The BEA flag indicates whether the 246 backup forwarding entry is active. When it is active, the backup 247 F-BM, backup BFR-NBR, and the backup forwarding action are used for 248 the forwarding of BIER packets instead of the primary forwarding 249 entry. The structure of the extended BIFT is given in Figure 1. 251 +--------+------+---------+--------+----------+--------+----+ 252 | BFR-id | F-BM | BFR-NBR | BF-BM | BBFR-NBR | BFA | BEA| 253 +========+======+=========+========+==========+========+====+ 254 | ... | ... | ... | ... | ... | ... | | 255 +--------+------+---------+--------+----------+--------+----+ 257 Figure 1: Structure of an extended BIFT with backup forwarding 258 entries. 260 The primary action is not given in the BIFT as it is derived from the 261 BFR-NBR. In contrast, the backup forwarding action is given in the 262 extended BIFT. Moreover, an explicit path must be indicated in case 263 of forwarding action Explicit. However, explicit paths are 264 implementation-specific and, therefore, this information is not 265 indicated in the table. The values for the backup BFR-NBR and the 266 backup action depend on the desired protection level and the backup 267 strategy. Examples for them are described in Section 5.1 and 268 Section 5.2. The backup F-BM depends on the backup BFR-NBR. Its 269 computation is explained in Section 2.4. 271 2.3. Activating and Deactivating Backup Forwarding Entries 273 When a primary BFR-NBR is not reachable over the implicit primary 274 action, a failure is observed. Then, the BEA flag of the 275 corresponding backup forwarding entry is set. 277 If the primary BFR-NBR is directly connected, the information about 278 the failed interface is sufficient to detect its unreachability. If 279 the primary BFR-NBR is indirectly connected, a BFD session between 280 the BFR as PLR and the BFR-NBR may be used to monitor its 281 reachability. 283 If the primary BFR-NBR is reachable again, the BEA flag is 284 deactivated. This may be caused by the disappearance of the failure 285 or by a change of the primary BFR-NBR due to a reconfiguration of the 286 BIFT. 288 2.4. Computation of the Backup F-BM 290 The primary F-BM of a specific BFER indicates all BFERs that share 291 the same primary BFR-NBR. The backup F-BM of a specific BFER 292 indicates 294 o all BFERs that share the primary and backup BFR-NBR of the 295 specific BFER and 297 o all BFERs that have the backup BFR-NBR of the specific BFER as 298 primary BFR-NBR. 300 3. Representations for BIER-FRR Forwarding Data 302 We show that backup entries need to be used first to reduce the 303 number of redundant packets in the single extended BIFT (presented in 304 Section 2.2). This may be hard or cannot be achieved on some 305 hardware platforms. Therefore, two alternate representations of 306 forwarding entries are proposed. The first is a primary BIFT and 307 single backup BIFT (SBB). The second is a primary BIFT and multiple 308 failure-specific backup BIFTs (FBB). 310 3.1. Potential Emergence of Redundant Packets 312 The BIER forwarding procedure in failure-free scenarios avoids 313 redundant packets, i.e., it ensures that at most a single copy is 314 sent per link for every BIER packet. However, this property might be 315 violated when BIER-FRR as presented in Section 2 is applied to 316 protect against a failure. 318 Figure 2 shows an example of a BIER network. BFRs have the prefix 319 "B" and are numbered by their BFR-ids. To simplify the example, 320 every BFR is a BFER and its bit position in the bitstring equals its 321 BFR-id. The number on a link is its cost which is used by the 322 routing underlay for computing the shortest paths. 324 1 1 325 B1 --------- B6 ------------ B5 BFR Bi is BFER 326 | | | (i = 1,2,3,4,5,6,7; 327 | | | i is BFR-id of Bi) 328 2 | | 1 | 329 | 1 | | 1 cost of link B1-B2 is 2 330 B2 --------- B7 | cost of link B3-B4 is 4 331 | | cost of other links is 1 332 1 | | 333 | 4 | 334 B3 ------------------------- B4 336 Figure 2: BIER network example. 338 The extended BIFT with backup forwarding entries for LFA-based BIER- 339 FRR with link protection built by BFR B1 is illustrated in Figure 3. 341 +------+----------+-------+----------+--------+----------+---+ 342 |BFR-id| F-BM |BFR-NBR| BF-BM |BBFR-NBR| BFA |BEA| 343 +======+==========+=======+==========+========+==========+===+ 344 | 2 | 0000110 | B2 | 1111110 | B6 | Plain | | 345 +------+----------+-------+----------+--------+----------+---+ 346 | 3 | 0000110 | B2 | 1111110 | B6 | Plain | | 347 +------+----------+-------+----------+--------+----------+---+ 348 | 4 | 1111000 | B6 | 1111110 | B2 | Plain | | 349 +------+----------+-------+----------+--------+----------+---+ 350 | 5 | 1111000 | B6 | 1111110 | B2 | Plain | | 351 +------+----------+-------+----------+--------+----------+---+ 352 | 6 | 1111000 | B6 | 1111110 | B2 | Plain | | 353 +------+----------+-------+----------+--------+----------+---+ 354 | 7 | 1111000 | B6 | 1111110 | B2 | Plain | | 355 +------+----------+-------+----------+--------+----------+---+ 357 Figure 3: B1's extended BIFT for LFA-based FRR with link protection. 359 We show how redundant packets can occur in case of a failure. To 360 that end, we consider the extended BIFT for BFR 1 in Figure 3. It 361 has backup forwarding entries for LFA-based FRR and link protection. 362 For a BIER packet with destinations B2 and B6 (i.e., bitstring 363 0100010), BFR B1 sends a single packet copy on link B1-B2 and on link 364 B1-B6 in the absence of a failure. 366 When the link B1-B6 fails, B1 as a PLR detects the failure. 367 Therefore, B1 sets the BEA flag for all destinations that have B6 as 368 BFR-NBR. We consider again that B1 sends a BIER packet to B2 and B6. 369 At first, it sends a copy with bitstring 0000010 to B2 using the 370 corresponding primary forwarding entry in the extended BIFT in 371 Figure 3. 373 Then, B1 sends another copy of the packet with bitstring 0100000 for 374 B6 to B2 using the backup forwarding entry since the BEA flag is 375 activated. 377 This is a second (redundant) copy over the same link B1-B2. It can 378 be prevented if the backup forwarding entry is used first. When 379 using the backup forwarding entry, B1 sends only a single copy of the 380 packet with bitstring 0100010 to B2. It will not send any copy of 381 the packet to B2 again since the bitstring in the packet will be all 382 cleaned by the BF-BM 1111110. Thus, prioritized processing of BFERs 383 with unreachable BFR-NBRs helps to reduce redundant packet copies. 385 3.2. Primary BIFT and Single Backup BIFT 387 The extended BIFT may be separated into two BIFTs. One is a primary 388 BIFT and the other is a single backup BIFT. The primary BIFT is the 389 same as the regular BIFT. The backup BIFT contains the backup 390 forwarding entries, including BF-BM, BBFR-NBR, BFA and BEA in the 391 extended BIFT. When a BFR as a PLR detects that BFR-NBR N is 392 unreachable, it activates the BEA flag for all BFERs in the backup 393 BIFT that have BFR-NBR as primary BFR-NBR. When a BFR forwards a 394 BIER packet, it processes the packet first using the backup BIFT and 395 then using the primary BIFT. With this prioritization, the number of 396 redundant packet copies can be reduced. 398 B1's extended BIFT in Figure 3 is separated into the primary BIFT in 399 Figure 4 and the single backup BIFT in Figure 5. 401 +--------+---------+---------+ 402 | BFR-id | F-BM | BFR-NBR | 403 +========+=========+=========+ 404 | 2 | 0000110 | B2 | 405 +--------+---------+---------+ 406 | 3 | 0000110 | B2 | 407 +--------+---------+---------+ 408 | 4 | 1111000 | B6 | 409 +--------+---------+---------+ 410 | 5 | 1111000 | B6 | 411 +--------+---------+---------+ 412 | 6 | 1111000 | B6 | 413 +--------+---------+---------+ 414 | 7 | 1111000 | B6 | 415 +--------+---------+---------+ 417 Figure 4: B1's primary BIFT for the BIER network example. 419 +------+----------+--------+-----------+---+-----------------+ 420 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 421 | | | | | | failure of | 422 +======+==========+========+===========+===+=================+ 423 | 2 | 1111110 | B6 | Plain | | Link B1->B2 | 424 +------+----------+--------+-----------+---+-----------------+ 425 | 3 | 1111110 | B6 | Plain | | Link B1->B2 | 426 +------+----------+--------+-----------+---+-----------------+ 427 | 4 | 1111110 | B2 | Plain | | Link B1->B6 | 428 +------+----------+--------+-----------+---+-----------------+ 429 | 5 | 1111110 | B2 | Plain | | Link B1->B6 | 430 +------+----------+--------+-----------+---+-----------------+ 431 | 6 | 1111110 | B2 | Plain | | Link B1->B6 | 432 +------+----------+--------+-----------+---+-----------------+ 433 | 7 | 1111110 | B2 | Plain | | Link B1->B6 | 434 +------+----------+--------+-----------+---+-----------------+ 436 Figure 5: B1's backup BIFT for the BIER network example. 438 Each forwarding entry in the backup BIFT contains BF-BM, BBFR-NBR, 439 BFA and BEA. When a BFR-NBR fails, the BEA flag is activated for all 440 BFERs in the backup BIFT that have BFR-NBR as primary BFR-NBR. For 441 example, BFERs B4, B5, B6 and B7 have BFR-NBR B6 as their primary 442 BFR-NBR. When BFR-NBR B6 fails, the BEA flag for BFERs B4, B5, B6 443 and B7 is activated, i.e., the BEA in the last four entries in the 444 backup BIFT is set to one. 446 3.3. Primary BIFT and Failure-Specific Backup BIFTs 448 As an alternative, the information in the extended BIFT may be 449 represented in a primary BIFT and several, failure-specific backup 450 BIFTs. A failure-specific backup BIFT is a backup BIFT for the 451 unreachability of BFR-NBR N. A backup BIFT for the failure of N is 452 simply called a backup BIFT for N. It has the same structure as the 453 regular BIFT but has an entry for a backup forwarding action. Thus, 454 a BFR has a primary BIFT, which is the same as the regular BIFT, and 455 a backup BIFT for each of its BFR-NBRs. 457 The BFR uses the primary BIFT to forward BIER packets under failure- 458 free conditions. When the BFR as a PLR detects that BFR-NBR N is 459 unreachable, it uses the backup BIFT for N to forward all BIER 460 packets. After the routing underlay has re-converged on the new 461 network topology, the primary BIFT is re-computed. Once the re- 462 computed primary BIFT is installed, it is used to forward all BIER 463 packets. 465 We illustrate the concept using the example from extended BIFT in 466 Figure 3. Figure 4 shows the primary BIFT of B1 in this context. 468 BFR B1 in Figure 2 has two neighbors: B6 and B2. B1 has two backup 469 BIFTs with link protection: one for B6 and another for B2. B1 has 470 also two backup BIFTs with node protection. Figure 6 is B1's backup 471 BIFT for B6 to react to the unreachability of B1 in a similar way as 472 with the extended BIFT in Figure 3. 474 +--------+---------+---------+-----------------+-----------------+ 475 | BFR-id | F-BM | BFR-NBR |Forwarding Action|Comment: protects| 476 | | | | | failure of | 477 +========+=========+=========+=================+=================+ 478 | 2 | 1111110 | B2 | Plain | | 479 +--------+---------+---------+-----------------+-----------------+ 480 | 3 | 1111110 | B2 | Plain | | 481 +--------+---------+---------+-----------------+-----------------+ 482 | 4 | 1111110 | B2 | Plain | Link B1->B6 | 483 +--------+---------+---------+-----------------+-----------------+ 484 | 5 | 1111110 | B2 | Plain | Link B1->B6 | 485 +--------+---------+---------+-----------------+-----------------+ 486 | 6 | 1111110 | B2 | Plain | Link B1->B6 | 487 +--------+---------+---------+-----------------+-----------------+ 488 | 7 | 1111110 | B2 | Plain | Link B1->B6 | 489 +--------+---------+---------+-----------------+-----------------+ 491 Figure 6: B1's backup BIFT for B6 for LFA-based BIER FRR with link 492 protection. 494 Once B1 as a PLR detects that B6 is unreachable through the link to 495 B6, it uses the backup BIFT for B6 to forward all BIER packets. As 496 this representation is equivalent to the concept of single primary 497 and single backup BIFT, redundant packets for the same forwarding 498 action are avoided. 500 4. Protection Levels 502 Link and node protection may be supported. Link protection protects 503 against the failure of an adjacent link while node protection 504 protects against the failure of a neighboring node and the path 505 towards that node. Depending on the supported service, link 506 protection or node protection may be relevant. Both protection 507 levels can be combined with any backup strategy in Section 5. 509 4.1. Link Protection 511 With link protection the backup path avoids the failed link (i.e., 512 the failed primary path from the PLR to the primary BFR-NBR, 513 excluding the primary BFR-NBR), but the backup path may include the 514 primary BFR-NBR. Therefore, the backup path is still operational if 515 the primary path fails. The disadvantage of link protection is that 516 it fails if the primary BFR-NBR itself is not operational. However, 517 link protection has also advantages. It often leads to shorter 518 backup paths than node protection. In case of tunnel-based BIER-FRR, 519 link protection causes at most one redundant packet while node 520 protection can cause more redundant packets. In case of LFA-based 521 BIER-FRR, link protection can protect more BFERs with normal BIER- 522 LFAs than node protection. 524 4.2. Node Protection 526 With node protection, the backup path avoids the failed node and the 527 link to the node (i.e., the failed primary path from the PLR to the 528 primary BFR-NBR, including the primary BFR-NBR). Therefore, the 529 backup path must not include the primary path or the primary BFR-NBR 530 so that the backup path is still operational if these elements fail. 531 If a BFER and its primary BFR-NBR are the same, only link protection 532 is possible for that BFER. An advantage of node protection is the 533 improved protection quality compared to link protection. However, 534 node protection has also disadvantages. It often leads to longer 535 backup paths than link protection. For tunnel-based BIER-FRR, 536 possibly more redundant packets are transmitted over a link than with 537 link protection. For LFA-based BIER-FRR, possibly fewer BFERs can be 538 protected with normal BIER-LFAs so that more remote BIER-LFAs or 539 topology-independent BIER-LFAs are needed which are more complex. 541 4.3. Example 543 In Figure 2, B1's primary path towards BFER B5 is B1-B6-B5. Node 544 protection for BFER B5 can be achieved only via the backup path 545 B1-B2-B3-B4-B5. Link protection for BFER 5 is achieved via the 546 backup path B1-B2-B7-B6 and in addition via the backup path 547 B1-B2-B3-B4-B5-B6. The backup entries depend on the protection level 548 and on the backup strategy. Example BIFTs for link and node 549 protection are given in Section 5. 551 5. Backup Strategies 553 The backup strategies determine the selection of the backup 554 forwarding entries. They have an impact on the backup BFR-NBR and on 555 the backup action, and thereby on the backup path. In the following, 556 tunnel-based BIER-FRR and LFA-based BIER-FRR are presented. 558 5.1. Tunnel-Based BIER-FRR 560 The routing underlay may be able to forward packets towards their 561 destinations despite an existing failure. This may be achieved, 562 e.g., due to FRR mechanisms in the routing underlay. In that case, 563 the primary BFR-NBR is not reachable via the primary action (Plain), 564 but it may be reachable via a backup action (Tunnel). 566 Tunnel-based BIER-FRR encapsulates BIER packets affected by a failure 567 in the routing underlay to leverage its fast restoration capability. 568 The affected BIER packets can be delivered towards their destinations 569 as soon as the connectivity in the routing underlay is restored. The 570 appropriate backup forwarding entries in a BIFT for BIER-FRR depend 571 on the desired protection level. 573 5.1.1. Tunnel-Based BIER-FRR with Link Protection 575 With link protection, the backup BFR-NBRs equal the primary BFR-NBRs. 576 If a primary BFR-NBR is directly connected to the BFR as a PLR, the 577 corresponding backup forwarding action is Tunnel. As a result, the 578 BIER packets affected by a failure are tunneled over the routing 579 underlay to their BFR-NBR instead of being sent directly as plain 580 BIER packets to the BFR-NBR. If a primary BFR-NBR is not directly 581 connected to the BFR as a PLR (i.e., the implicit, primary action is 582 Tunnel), the corresponding backup action is also Tunnel. The backup 583 F-BMs are the same as the primary F-BMs, which is in line with the 584 computation of the backup F-BMs in Section 2.4. 586 +------+----------+--------+-----------+---+-----------------+ 587 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 588 | | | | | | failure of | 589 +======+==========+========+===========+===+=================+ 590 | 2 | 0000110 | B2 | Tunnel | | Link B1->B2 | 591 +------+----------+--------+-----------+---+-----------------+ 592 | 3 | 0000110 | B2 | Tunnel | | Link B1->B2 | 593 +------+----------+--------+-----------+---+-----------------+ 594 | 4 | 1111000 | B6 | Tunnel | | Link B1->B6 | 595 +------+----------+--------+-----------+---+-----------------+ 596 | 5 | 1111000 | B6 | Tunnel | | Link B1->B6 | 597 +------+----------+--------+-----------+---+-----------------+ 598 | 6 | 1111000 | B6 | Tunnel | | Link B1->B6 | 599 +------+----------+--------+-----------+---+-----------------+ 600 | 7 | 1111000 | B6 | Tunnel | | Link B1->B6 | 601 +------+----------+--------+-----------+---+-----------------+ 603 Figure 7: B1's backup BIFT for tunnel-based BIER-FRR with link 604 protection. 606 Figure 7 shows B1's backup BIFT for tunnel-based BIER-FRR with link 607 protection for the BIER network example of Figure 2. The backup BFR- 608 NBRs and backup F-BMs in this backup BIFT are the same as the primary 609 BFR-NBRs and primary F-BMs in the primary BIFT in Figure 4, but the 610 backup actions in this backup BIFT are Tunnel while the primary 611 actions in the primary BIFT are Plain (which are not shown, but 612 implied). 614 When B1 as a PLR detects failure of its link to B6, a BIER packet 615 with bitstring 0100000 for B6 is tunneled by B1 towards B6 via the 616 routing underlay. The exact path of the backup tunnel depends on the 617 routing underlay. It may be B1-B2-B7-B6 or B1-B2-B3-B4-B5-B6. 619 If a BIER packet is destined to {B2, B5, B7}, first an encapsulated 620 packet copy is forwarded via link B1-B2 to backup BFR-NBR B6 with 621 backup action Tunnel to deliver packet copies to BFER B5 and B7. 622 Then, a non-encapsulated packet copy is forwarded via link B1-B2 to 623 BFR-NBR B2 with primary action Plain to deliver a packet copy to BFER 624 B2. Thus, with tunnel-based BIER-FRR, a single redundant packet copy 625 can occur in case of a failure because an encapsulated packet copy 626 and a non-encapsulated packet copy are forwarded over the same link. 627 This happens although BIER packets affected by failures are forwarded 628 before BIER packets not affected by failures. 630 A BIER packet with bitstring 1000000 for B7 is forwarded on the 631 backup path B1-B2-B7-B6-B7 as it is first delivered to the backup 632 BFR-NBR B6. Thus, the backup path can be unnecessarily long. This 633 phenomenon is known from facility backup method in [RFC4090] which 634 takes similar paths as tunnel-based BIER-FRR. 636 5.1.2. Tunnel-Based BIER-FRR with Node Protection 638 To determine the backup forwarding entries with node protection, a 639 case analysis for the BFER to protect is needed. If the BFER is the 640 same as its primary BFR-NBR, node protection is not possible for that 641 BFER. Therefore, link protection is applied, i.e., the backup BFR- 642 NBR is set to the primary BFR-NBR. If that level of protection is 643 not sufficient, egress protection in [I-D.chen-bier-egress-protect] 644 may be applied. Otherwise (i.e., the BFER is different from its 645 primary BFR-NBR), the backup BFR-NBR is set to the primary BFR-NBR's 646 primary BFR-NBR for that BFER, i.e., the backup BFR-NBR is a next 647 next hop BFR. In all cases, the backup action is Tunnel. In the 648 first case, the backup F-BM is set to all zeroes plus the bit enabled 649 for the BFER to protect. In the second case, the backup F-BM is 650 computed in the way described in Section 2.4. 652 +------+----------+--------+----------+---+-----------------+ 653 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 654 | | | | | | failure of | 655 +======+==========+========+==========+===+=================+ 656 | 2 | 0000010 | B2 | Tunnel | | Link B1->B2 | 657 +------+----------+--------+----------+---+-----------------+ 658 | 3 | 0000100 | B3 | Tunnel | | BFR-NBR B2 | 659 +------+----------+--------+----------+---+-----------------+ 660 | 4 | 0011000 | B5 | Tunnel | | BFR-NBR B6 | 661 +------+----------+--------+----------+---+-----------------+ 662 | 5 | 0011000 | B5 | Tunnel | | BFR-NBR B6 | 663 +------+----------+--------+----------+---+-----------------+ 664 | 6 | 0100000 | B6 | Tunnel | | Link B1->B6 | 665 +------+----------+--------+----------+---+-----------------+ 666 | 7 | 1000000 | B7 | Tunnel | | BFR-NBR B6 | 667 +------+----------+--------+----------+---+-----------------+ 669 Figure 8: B1's backup BIFT for tunnel-based BIER-FRR with node 670 protection. 672 Figure 8 shows B1's backup BIFT for tunnel-based BIER-FRR with node 673 protection for the BIER network example in Figure 2. BFERs B2 and B6 674 are direct neighbors of B1. To protect them, only link protection is 675 applied as B1's primary BFR-NBR for them are those nodes themselves. 676 According to the description above, only the bit for B2 is set in the 677 backup F-BM of B2. The same holds for B6. For BFER B5, the backup 678 BFR-NBR is B5 as it is B1's next next hop BFR towards B5. Similarly, 679 for BFER B7, the backup BFR-NBR is B7. When B1 as a PLR detects the 680 failure of its BFR-NBR B6, a BIER packet with bitstring 1010010 for 681 {B2, B5, B7} is processed as follows. An encapsulated copy of the 682 packet is sent via tunnel B1-B2-B3-B4-B5, another encapsulated copy 683 is sent via tunnel B1-B2-B7, and a non-encapsulated copy is sent via 684 link B1-B2. In this example, two redundant packets are sent on link 685 B1-B2. Thus, with node protection, more redundant packets copies may 686 be sent than with link protection. 688 Caveat: If the routing underlay does not provide node protection, 689 tunnel-based BIER-FRR cannot provide node protection, either. This 690 is shown by the following example. The underlay in the networking 691 example of Figure 2 offers only link protection. B6 fails and B1 692 must forward a packet to B5. According to the backup BIFT in 693 Figure 8 the packet is tunneled towards B5 and the tunnel path 694 B1-B2-B7-B6-B5 may be taken for this purpose by the underlay due to 695 FRR with link protection. However, B6 is also unreachable at B7 so 696 that the packet is returned to B2 and the packet loops between B2 and 697 B7. 699 5.1.3. Implementation Experience 701 Tunnel-based BIER-FRR has been implemented in P4 for the software- 702 switch bmv2 [MeLi20b] and the hardware switching ASIC Tofino 703 [MeLi21]. Performance results have been provided. 705 5.2. LFA-based BIER-FRR 707 LFA-based BIER-FRR leverages alternate BFRs to deliver BIER packets 708 to BFERs for which the primary BFR-NBR is unreachable. It does not 709 rely on any fast restoration/protection mechanisms in the underlay. 710 First, some prerequisites for LFA-based BIER-FRR are clarified, BIER- 711 LFAs are defined, and then link and node protection for LFA-based 712 BIER-FRR are discussed using a single backup BIFT. 714 5.2.1. Relation of BIER-LFAs to IP-LFAs and Prerequisites 716 A loop-free alternate (LFA) for a specific destination is an 717 alternate node to which a packet is sent if the primary next hop for 718 this destination is not reachable. This alternate node should be 719 able to forward the packet without creating a forwarding loop. LFAs 720 have been defined for IP networks in [RFC5286], [RFC7490] and 721 [I-D.ietf-rtgwg-segment-routing-ti-lfa]. We denote such LFAs as IP- 722 LFAs. BIER-LFAs are very similar to IP-LFAs, but a BIER-LFA node 723 must be a BFR. If only a subset of the nodes in the routing underlay 724 are BFRs, some IP-LFAs in the routing underlay may not be usable as 725 BIER-LFAs. To compute BIER-LFAs, network topology and link cost 726 information from the routing underlay are needed. This is a 727 difference to tunnel-based BIER-FRR where knowledge about the primary 728 BIFTs of a PLR and its BFR-NBRs is sufficient. 730 LFA-based BIER-FRR may reuse IP-LFAs in the following sense as BIER- 731 LFAs. If an IP-LFA node for the destination of a specific BFER is a 732 BFR, it may be reused as backup BFR-NBR for that BFER together with 733 the backup action that is applied for that IP-LFA on the IP layer. A 734 normal IP-LFA corresponds to backup action plain, a remote IP-LFA to 735 Tunnel, and a TI-IP-LFA to Explicit. 737 5.2.2. Definition of BIER-LFAs 739 As for IP-LFAs, there are several, different types of BIER-LFAs: 741 o A BFR is a normal BIER-LFA for a specific BFER if it is directly 742 connected to the PLR and 744 1. the BFER can be reached from it through the BIER domain 745 2. both the path from the PLR to it and the path from it to the 746 BFER are disjoint with the primary path from the PLR to the 747 primary BFR-NBR. These paths 749 + may contain the primary BFR-NBR for link protection, and 751 + must not contain the primary BFR-NBR for node protection. 753 o A BFR is a remote BIER-LFA for a specific BFER if it is not 754 directly connected to the PLR, if it can be reached via a tunnel 755 from the PLR, and if it also satisfies the aforementioned 756 conditions 1 and 2. 758 o A BFR is a TI-BIER-LFA for a specific BFER if it is not directly 759 connected to the PLR, if it cannot be reached via a tunnel from 760 the PLR, if it is reachable from the PLR via an explicit path 761 (i.e., with the help of a SR header), and if it also satisfies the 762 aforementioned conditions 1 and 2. 764 For some BFERs, one or more normal BIER-LFAs are available at a 765 specific PLR. For other BFERs, only remote and TI-LFAs are 766 available. And there may be some BFERs, for which only TI-LFAs are 767 available. 769 The backup actions to reroute BIER packets depending on the BIER-LFA 770 types are: 772 o For normal BIER-LFA: Plain 774 o For remote BIER-LFA: Tunnel 776 o For TI-BIER-LFA: Explicit 778 5.2.3. Protection Coverage of BIER-LFA Types 780 The protection coverage is the set of BFERs that can be protected 781 with a desired protection level by a certain BIER-LFA type. The 782 BIER-LFA types have the following properties: 784 o Normal BIER-LFAs 786 * The protection coverage is the least because some or many BFERs 787 cannot be protected with the desired protection level or even 788 not at all. 790 * Redundant packet copies are avoided. 792 * No encapsulation overhead. 794 o Remote BIER-LFAs 796 * They increase the protection coverage of normal BIER-LFAs. 798 * Redundant packet copies may occur on a link similar to tunnel- 799 based BIER-FRR. 801 * Same encapsulation overhead as with tunnel-based BIER-FRR. 803 o TI-BIER-LFAs 805 * They complement the protection coverage of normal and remote 806 BIER-LFAs to 100%. 808 * Redundant packets may occur on a link similar to tunnel-based 809 BIER-FRR. 811 * Same or similar encapsulation overhead as with tunnel-based 812 BIER-FRR depending on the FRR mechanism in the routing 813 underlay. 815 5.2.4. Sets of Supported BIER-LFAs 817 Normal BIER-LFAs are simplest, as they require neither tunneling nor 818 explicit paths. Remote BIER-LFAs are more powerful, but entail more 819 header overhead and require more functionality from the PLR. TI- 820 BIER-LFAs are most complex as they require the use of explicit paths. 821 When LFA-based BIER-FRR is utilized, the set of supported BIER-LFAs 822 must be indicated. The following options are available: 824 o Option 1: only normal BIER-LFAs are supported 826 o Option 2: normal and remote BIER-LFAs are supported 828 o Option 3: all BIER-LFA types are supported 830 5.2.5. Link Protection 832 With link protection, normal BIER-LFAs are preferred over remote LFAs 833 and remote BIER-LFAs are preferred over TI-BIER-LFAs. Depending on 834 the set of supported BIER-LFAs, a BFER may not be protectable. 836 Figure 5 illustrates B1's backup BIFT for LFA-based BIER-FRR with 837 link protection in the networking example of Figure 2. 839 If the link B1-B6 fails, B1 cannot reach the BFERs B4, B5, B6, and B7 840 over their primary BFR-NBR. Therefore, B1 sends their traffic via 841 the backup BFR-NBR B2 together with the traffic for B2 and B3 as B2 842 is their primary BFR-NBR. As a consequence, the backup F-BM is 843 1111110 in that case. Likewise, if the link B1-B2 fails, B1 sends 844 all traffic to B6, and the backup F-BM is 1111110 also in that case. 846 B1 requires only normal BIER-LFAs to protect all BFERs. This can be 847 substantially different for other BFRs. Figure 9 and Figure 10 show 848 the backup BIFTs for B7 and B5 respectively. BFR B7 requires one 849 normal BIER-LFA, three remote BIER-LFAs, and two TI-BIER-LFAs to 850 protect all BFERs. And BFR B5 requires even one normal BIER-LFA, one 851 remote BIER-LFA, and four TI-BIER-LFAs as backup BFR-NBRs. Thus, 852 depending on the set of supported BIER-LFAs, a BFER cannot be 853 protected by BIER-FRR. 855 We now assume B7 has a BIER packet with destinations {B1, B4, B5, 856 B6}. When link B7-B6 fails, the packet copy for B1 is sent to B2 857 using forwarding action Plain, the packet copy to B4 is tunneled via 858 B2 to B3, and the packet copies towards B5 and B6 are sent via 859 explicit paths towards B4 and B1 respectively. As these packet 860 copies have different headers, they all need to be sent. Hence, we 861 observe three redundant copies. 863 +------+----------+--------+-----------+---+-----------------+ 864 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 865 | | | | | | failure of | 866 +======+==========+========+===========+===+=================+ 867 | 1 | 0000111 | B2 | Plain | | Link B7->B6 | 868 +------+----------+--------+-----------+---+-----------------+ 869 | 2 | 0000110 | B1 | Tunnel | | Link B1->B2 | 870 +------+----------+--------+-----------+---+-----------------+ 871 | 3 | 0000110 | B1 | Tunnel | | Link B1->B2 | 872 +------+----------+--------+-----------+---+-----------------+ 873 | 4 | 0001000 | B3 | Tunnel | | Link B1->B6 | 874 +------+----------+--------+-----------+---+-----------------+ 875 | 5 | 0010000 | B4 | Explicit | | Link B1->B6 | 876 +------+----------+--------+-----------+---+-----------------+ 877 | 6 | 0100000 | B1 | Explicit | | Link B1->B6 | 878 +------+----------+--------+-----------+---+-----------------+ 880 Figure 9: B7's backup BIFT with link protection. 882 +------+----------+--------+-----------+---+-----------------+ 883 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 884 | | | | | | failure of | 885 +======+==========+========+===========+===+=================+ 886 | 1 | 1100011 | B3 | Explicit | | Link B5->B6 | 887 +------+----------+--------+-----------+---+-----------------+ 888 | 2 | 1100011 | B3 | Explicit | | Link B5->B6 | 889 +------+----------+--------+-----------+---+-----------------+ 890 | 3 | 0000100 | B4 | Plain | | Link B5->B6 | 891 +------+----------+--------+-----------+---+-----------------+ 892 | 4 | 0001000 | B3 | Tunnel | | Link B5->B4 | 893 +------+----------+--------+-----------+---+-----------------+ 894 | 6 | 1100011 | B3 | Explicit | | Link B5->B6 | 895 +------+----------+--------+-----------+---+-----------------+ 896 | 7 | 1100011 | B3 | Explicit | | Link B5->B6 | 897 +------+----------+--------+-----------+---+-----------------+ 899 Figure 10: B5's backup BIFT with link protection. 901 5.2.6. Node Protection 903 To determine the backup forwarding entries with node protection, a 904 case analysis for the BFER to protect is needed again. If the BFER 905 is the same as its primary BFR-NBR, node protection is not possible 906 for that BFER. In this case, link protection is applied. Otherwise, 907 the BFER must be protected by a node-protecting BIER-LFA. Thereby, 908 normal BIER-LFAs are preferred over remote BIER-LFAs and remote BIER- 909 LFAs are preferred over TI-BIER-LFAs. Depending on the set of 910 allowed BIER-LFAs, a BFER may not be protectable. 912 Figure 11 illustrates B1's backup BIFT for the LFA-based BIER-FRR 913 with node protection in the networking example of Figure 2. 915 +------+----------+--------+-----------+---+-----------------+ 916 |BFR-id| BF-BM |BBFR-NBR| BFA |BEA|Comment: protects| 917 | | | | | | failure of | 918 +======+==========+========+===========+===+=================+ 919 | 2 | 1111010 | B6 | Plain | | BFR-NBR B2 | 920 +------+----------+--------+-----------+---+-----------------+ 921 | 3 | 0000100 | B4 | Tunnel | | BFR-NBR B2 | 922 +------+----------+--------+-----------+---+-----------------+ 923 | 4 | 0001000 | B3 | Tunnel | | BFR-NBR B6 | 924 +------+----------+--------+-----------+---+-----------------+ 925 | 5 | 0010000 | B4 | Explicit | | BFR-NBR B6 | 926 +------+----------+--------+-----------+---+-----------------+ 927 | 6 | 1100100 | B2 | Plain | | BFR-NBR B6 | 928 +------+----------+--------+-----------+---+-----------------+ 929 | 7 | 1100100 | B2 | Plain | | BFR-NBR B6 | 930 +------+----------+--------+-----------+---+-----------------+ 932 Figure 11: B1's backup BIFT with node protection. 934 As the primary BFR-NBR of B1 for BFER B6 is B6 itself, only link 935 protection can be applied. Therefore, B2 is used as normal, link- 936 protection BIER-LFA to protect B6. Likewise, the primary BFR-NBR of 937 B1 for BFER B2 is B2, and therefore, B2 is protected with B6 as 938 normal, link-protecting BIER-LFA. BFER B7 is protected against the 939 failure of node B6 with B2 as normal, node-protecting BIER-LFA as B2 940 has a shortest path towards B7 that does not traverse B6. The backup 941 F-BMs for BFER 6 and BFER 7 are {B2, B6, B7} because if B6 is 942 unreachable, the traffic for these BFERs is sent via link B1-B2 with 943 forwarding action Plain. 945 BFER B4 is not reachable through a normal LFA when BFR B6 fails. 946 However, B3 is a remote, node-protecting BIER-LFA for BFER B4 because 947 B3 has a shortest path towards B4, and B3 is reachable through a 948 shortest path from B1, and the resulting backup path from B1 to B4 949 does not traverse B6. Likewise, B4 is a remote LFA for BFER B3 if 950 BFR B2 fails. 952 BFER B5 is neither reachable through a normal BIER-LFA nor through a 953 remote BIER-LFA when BFR B6 fails. However, B4 is a node-protecting 954 TI-LFA for BFER B5 because B4 has a shortest path towards B5 that 955 does not traverse B6. Moreover, B4 is reachable through the explicit 956 path B1-B2-B3-B4. 958 5.2.7. Optimization Potential to Reduce Redundant BIER Packets in 959 Failure Cases 961 Redundant packets occur with LFA-based BIER-FRR if BIER packets are 962 sent over a specific link in different forms. These forms are 964 o plain BIER packets (plain primary transmission or reroute to 965 normal BIER-LFA) 967 o BIER packets encapsulated to a specific BFR-NBR (tunneled primary 968 transmission or reroute to remote BIER-LFA) 970 o BIER packets with an encoded explicit path (reroute to TI-LFA) 972 When different remote LFAs are addressed, even multiple redundant 973 packets can be caused through remote LFAs. The same can happen with 974 TI-LFAs. Some redundant packets can be avoided if remote LFAs or TI- 975 LFAs are chosen such that they can protect several BFERs and thereby 976 avoid the need for another remote LFA or TI-LFA. However, this may 977 lead to longer backup paths. This is a new, potential optimization 978 objective for the choice of remote or TI-BIER-LFAs which does not 979 exist for IP-FRR. Its relevance may depend on the use case. 981 We illustrate this optimization potential. We consider LFA-based 982 BIER-FRR with link protection for B7. Its backup BIFT is given in 983 Figure 9. As observed in Section 5.2.5, B7 needs to send four copies 984 to forward a packet to {B1, B4, B5, B6}. If we choose the more 985 complex TI-BIER-LFA B4 to protect BFER B4 instead of the remote BIER- 986 LFA B3, then only two redundant copies need to be sent. 988 6. Comparison 990 This section first discusses the difference of IP-LFAs for IP-FRR and 991 BIER-LFAs for BIER-FRR. Then it discusses advantages and 992 disadvantages of tunnel-based and LFA-based BIER-FRR. 994 6.1. Comparison of LFA-Based Protection for IP-FRR and BIER-FRR 996 LFAs have been first proposed for IP networks. They are simple in 997 the sense that they do not require any tunneling overhead. However, 998 some destinations cannot be protected against some link failures and 999 even more destinations cannot be protected against some node 1000 failures. Therefore, remote LFAs (R-LFAs) have been defined to 1001 improve that coverage by tunneling the affected traffic to another 1002 node from where the traffic can reach the destination via normal 1003 forwarding. Nevertheless, there may be still some destinations that 1004 cannot be protected against link or node failures. Therefore, 1005 topology-independent LFAs (TI-LFAs) have been defined where affected 1006 traffic is tunneled via an explicit path (preferably using segment 1007 routing headers) to another node from where the traffic can reach its 1008 destination via normal IP forwarding. With TI-LFAs, all destinations 1009 can be protected against any failures as long as connectivity exists. 1011 LFA-based BIER-FRR adopts the idea of LFAs. It differs from IP-FRR 1012 as the LFA target node, i.e., the node to which the traffic is 1013 deviated, must be a BFR. If an IP-LFA target is a BFR, it can be 1014 utilized as a BIER-LFA; otherwise it cannot serve as BIER-LFA. Thus, 1015 if only some nodes of the underlay are BFRs, the BIER-LFAs will be 1016 substantially different from IP-LFAs. Moreover, this makes it more 1017 difficult to find normal LFAs for which tunneling is not needed. 1018 That means, LFA-based BIER-FRR is likely to require more remote LFAs 1019 and TI-LFAs than IP-FRR under such conditions. 1021 6.2. Advantages and Disadvantages of Tunnel-Based BIER-FRR 1023 6.2.1. Advantages 1025 o Computation of backup forwarding entries is very simple. Only 1026 primary BIFTs of a PLR and its BFR-NBRs are needed to compute the 1027 backup forwarding entries. Routing information from the routing 1028 underlay is not needed. 1030 o The forwarding action Explicit is not needed. However, depending 1031 on the underlay, explicit forwarding may be used to achieve FRR in 1032 the underlay. 1034 6.2.2. Disadvantages 1036 o It requires a FRR mechanism on the underlay. 1038 o It is limited to the protection level of the underlay. E.g., if 1039 the underlay supports only link protection, tunnel-based BIER-FRR 1040 cannot provide node protection. 1042 o Redundant packet copies may occur in tunnel-based BIER-FRR. 1044 o In case of node protection, backup paths may be extended more than 1045 needed. 1047 o Requires a tunneling header for any rerouting, which creates 1048 header overhead. 1050 6.3. Advantages and Disadvantages of LFA-Based BIER-FRR 1052 6.3.1. Advantages 1054 o Does not rely on any fast protection of the underlay. 1056 o Can provide better protection on the BIER layer than on the IP 1057 layer; this is possible if LFA-based BIER-FRR utilizes BIER-LFAs 1058 with better protection level than LFA-based IP-FRR. E.g., the 1059 underlay may provide only FRR with link protection while BIER-FRR 1060 may provide node protection for BIER traffic. 1062 o Avoids header overhead for normal BIER-LFAs. 1064 6.3.2. Disadvantages 1066 o Computation of backup forwarding entries requires routing 1067 information from the underlay. 1069 o Computation of backup forwarding entries more complex if some 1070 nodes of the underlay are not BFRs. 1072 o Need for forwarding action Tunnel to protect some BFERs, which 1073 adds header overhead. 1075 o Need for forwarding action Explicit to achieve full protection 1076 coverage for some topologies; otherwise only partial protection 1077 coverage. This requires support for explicit paths, e.g., segment 1078 routing. 1080 o More remote and TI-LFAs needed than for IP-FRR if some nodes in 1081 the routing underlay are not BFRs. 1083 o Redundant packet copies may occur in LFA-based BIER-FRR (but it's 1084 less than with tunnel-based BIER-FRR). 1086 7. Security Considerations 1088 TBD. 1090 8. IANA Considerations 1092 No requirements for IANA. 1094 9. Contributors 1096 Daniel Merling 1097 Germany 1098 Email: daniel.merling@uni-tuebingen.de 1100 Xuesong Geng 1101 China 1102 Email: gengxuesong@huawei.com 1104 10. Acknowledgements 1106 The authors would like to thank Jeffrey Zhang, Tony Przygienda and 1107 Shaofu Peng for their comments to this work. 1109 11. References 1111 11.1. Normative References 1113 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1114 Requirement Levels", BCP 14, RFC 2119, 1115 DOI 10.17487/RFC2119, March 1997, 1116 . 1118 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 1119 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 1120 DOI 10.17487/RFC5286, September 2008, 1121 . 1123 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 1124 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 1125 RFC 7490, DOI 10.17487/RFC7490, April 2015, 1126 . 1128 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1129 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1130 May 2017, . 1132 [RFC8279] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 1133 Przygienda, T., and S. Aldrin, "Multicast Using Bit Index 1134 Explicit Replication (BIER)", RFC 8279, 1135 DOI 10.17487/RFC8279, November 2017, 1136 . 1138 11.2. Informative References 1140 [BrAl17] Braun, W., Albert, M., Eckert, T., and M. Menth, 1141 "Performance Comparison of Resilience Mechanisms for 1142 Stateless Multicast Using BIER", May 2017. 1144 [I-D.chen-bier-egress-protect] 1145 Chen, H., McBride, M., Wang, A., Mishra, G. S., Liu, Y., 1146 Fan, Y., Liu, L., and X. Liu, "BIER Egress Protection", 1147 draft-chen-bier-egress-protect-01 (work in progress), 1148 February 2021. 1150 [I-D.ietf-rtgwg-segment-routing-ti-lfa] 1151 Litkowski, S., Bashandy, A., Filsfils, C., Francois, P., 1152 Decraene, B., and D. Voyer, "Topology Independent Fast 1153 Reroute using Segment Routing", draft-ietf-rtgwg-segment- 1154 routing-ti-lfa-06 (work in progress), February 2021. 1156 [MeLi20b] Merling, D., Lindner, S., and M. Menth, "P4-Based 1157 Implementation of BIER and BIER-FRR for Scalable and 1158 Resilient Multicast", November 2020. 1160 [MeLi21] Merling, D., Lindner, S., and M. Menth, "Hardware-based 1161 Evaluation of Scalable and Resilient Multicast with BIER 1162 in P4", March 2020. 1164 [RFC4090] Pan, P., Ed., Swallow, G., Ed., and A. Atlas, Ed., "Fast 1165 Reroute Extensions to RSVP-TE for LSP Tunnels", RFC 4090, 1166 DOI 10.17487/RFC4090, May 2005, 1167 . 1169 Appendix A. Specific Backup Strategy Examples 1171 This appendix demonstrates the computations of some specific backup 1172 strategy options in details. 1174 A.1. LFA-based BIER-FRR using Single BIFT 1176 In the LFA-based BIER-FRR using single BIFT, every BFR has a single 1177 BIFT for a level of protection. Its structure is the same as the one 1178 in Figure 1. 1180 The following presents the details in BFR B1 in Figure 2 for building 1181 the BIFT for BIER-FRR link protection. 1183 At first, BFR B1 obtains a BIER-LFA as BBFR-NBR for each BFER. B6 is 1184 normal BIER-LFA as BBFR-NBR for BFER B2 and B3. B2 is normal BIER- 1185 LFA as BBFR-NBR for BFER B4, B5, B6 and B7. Figure 12 illustrates 1186 B1's intermediate BIFT for link protection filled with values for 1187 BBFR-NBRs and BFAs. 1189 +------+---------+-------+----------+--------+----------+---+ 1190 |BFR-id| F-BM |BFR-NBR| BF-BM |BBFR-NBR| BFA |BEA| 1191 +======+=========+=======+==========+========+==========+===+ 1192 | 2 | 0000110 | B2 | | B6 | Plain | | 1193 +------+---------+-------+----------+--------+----------+---+ 1194 | 3 | 0000110 | B2 | | B6 | Plain | | 1195 +------+---------+-------+----------+--------+----------+---+ 1196 | 4 | 1111000 | B6 | | B2 | Plain | | 1197 +------+---------+-------+----------+--------+----------+---+ 1198 | 5 | 1111000 | B6 | | B2 | Plain | | 1199 +------+---------+-------+----------+--------+----------+---+ 1200 | 6 | 1111000 | B6 | | B2 | Plain | | 1201 +------+---------+-------+----------+--------+----------+---+ 1202 | 7 | 1111000 | B6 | | B2 | Plain | | 1203 +------+---------+-------+----------+--------+----------+---+ 1205 Figure 12: B1's intermediate BIFT for link protection. 1207 From the intermediate BIFT, BFERs B2 and B3 have the same BFR-NBR B2 1208 and BBFR-NBR B6, BFERs B4 to B7 have the same BFR-NBR B6 as the BBFR- 1209 NBR B6 for BFER B2. According to Section 2.4, the BF-BM for BFER B2 1210 has the bits for B2 and B3 as well as the bits for B4 to B7, which is 1211 1111110. The BF-BM for BFER B3 is also 1111110. Similarly, the BF- 1212 BM for each of BFERs B3 to B7 is computed, which is 1111110. 1214 With the BF-BMs, BFR B1 has the BIFT for link protection, which is 1215 illustrated in Figure 13. 1217 +------+---------+-------+----------+--------+----------+---+ 1218 |BFR-id| F-BM |BFR-NBR| BF-BM |BBFR-NBR| BFA |BEA| 1219 +======+=========+=======+==========+========+==========+===+ 1220 | 2 | 0000110 | B2 | 1111110 | B6 | Plain | | 1221 +------+---------+-------+----------+--------+----------+---+ 1222 | 3 | 0000110 | B2 | 1111110 | B6 | Plain | | 1223 +------+---------+-------+----------+--------+----------+---+ 1224 | 4 | 1111000 | B6 | 1111110 | B2 | Plain | | 1225 +------+---------+-------+----------+--------+----------+---+ 1226 | 5 | 1111000 | B6 | 1111110 | B2 | Plain | | 1227 +------+---------+-------+----------+--------+----------+---+ 1228 | 6 | 1111000 | B6 | 1111110 | B2 | Plain | | 1229 +------+---------+-------+----------+--------+----------+---+ 1230 | 7 | 1111000 | B6 | 1111110 | B2 | Plain | | 1231 +------+---------+-------+----------+--------+----------+---+ 1233 Figure 13: B1's BIFT for BIER-FRR link protection. 1235 A.2. LFA-based BIER-FRR using Multiple Backup BIFTs 1237 For the LFA-based BIER-FRR using multiple backup BIFTs, in addition 1238 to a primary BIFT, a BFR has a backup BIFT for each of its BFR-NBRs 1239 with a level of protection. The backup BIFT for BFR-NBR N with link 1240 protection (or simply called the backup BIFT for link to N) assumes 1241 that the link to N failed. The BFR uses it to protect against the 1242 failure of its link to N. The backup BIFT for N with node protection 1243 (or simply called the backup BIFT for N) assumes that node N failed. 1244 The BFR uses it to protect against the failure of N. Once the BFR as 1245 a PLR detects the failure of its link to N, it uses the backup BIFT 1246 for link to N to forward all BIER packets. When the BFR as a PLR 1247 detects the failure of its BFR-NBR N, it uses the backup BIFT for N 1248 to forward all BIER packets. 1250 Even though a BFR has multiple backup BIFTs, the LFA-based BIER-FRR 1251 using multiple backup BIFTs is scalable. Both the size of a backup 1252 BIFT and the number of backup BIFTs on the BFR are small. Assume a 1253 BIER network has 1000 BFRs and 100 BFERs, and each BFR has 10 BFR- 1254 NBRs on average. The size of a backup BIFT is 100 forwarding 1255 entries. The number of backup BIFTs on the BFR is 20 on average. 1256 The total size of all backup BIFTs is 100*20 = 2000 forwarding 1257 entries. 1259 The following presents the details in BFR B1 in Figure 2 for building 1260 the backup BIFT for link to B2 to support BIER-FRR link protection. 1262 To support link protection, BFR B1 in Figure 2 has two backup BIFTs: 1263 one for link to B2 and the other for link to B6. The backup BIFT for 1264 link to B2 is illustrated in Figure 14. 1266 +--------+---------+---------+-----------------+-----------------+ 1267 | BFR-id | F-BM | BFR-NBR |Forwarding Action|Comment: protects| 1268 | | | | | failure of | 1269 +========+=========+=========+=================+=================+ 1270 | 2 | 1111110 | B6 | Plain | Link B1->B2 | 1271 +--------+---------+---------+-----------------+-----------------+ 1272 | 3 | 1111110 | B6 | Plain | Link B1->B2 | 1273 +--------+---------+---------+-----------------+-----------------+ 1274 | 4 | 1111110 | B6 | Plain | | 1275 +--------+---------+---------+-----------------+-----------------+ 1276 | 5 | 1111110 | B6 | Plain | | 1277 +--------+---------+---------+-----------------+-----------------+ 1278 | 6 | 1111110 | B6 | Plain | | 1279 +--------+---------+---------+-----------------+-----------------+ 1280 | 7 | 1111110 | B6 | Plain | | 1281 +--------+---------+---------+-----------------+-----------------+ 1283 Figure 14: B1's backup BIFT for link to B2. 1285 BFR B1 builds the backup BIFT for link to B2 in two steps. In the 1286 first step, it builds the backup BIRT for link to B2 through copying 1287 its regular BIRT to the backup BIRT and then changing BFR-NBR B2 in 1288 the backup BIRT to a backup BFR-NBR to protect against the failure of 1289 the link to B2. The backup BIRT for link to B2 built by B1 is 1290 illustrated in Figure 15. 1292 +------+-------------+---------+-----------------+-----------------+ 1293 |BFR-id|BFER's Prefix| BFR-NBR |Forwarding Action|Comment: protects| 1294 | | | | | failure of | 1295 +======+=============+=========+=================+=================+ 1296 | 2 | B2 | B6 | Plain | Link B1->B2 | 1297 +------+-------------+---------+-----------------+-----------------+ 1298 | 3 | B3 | B6 | Plain | Link B1->B2 | 1299 +------+-------------+---------+-----------------+-----------------+ 1300 | 4 | B4 | B6 | Plain | | 1301 +------+-------------+---------+-----------------+-----------------+ 1302 | 5 | B5 | B6 | Plain | | 1303 +------+-------------+---------+-----------------+-----------------+ 1304 | 6 | B6 | B6 | Plain | | 1305 +------+-------------+---------+-----------------+-----------------+ 1306 | 7 | B7 | B6 | Plain | | 1307 +------+-------------+---------+-----------------+-----------------+ 1309 Figure 15: B1's backup BIRT for link to B2. 1311 The BFR-NBR in each of the first two routing entries with BFR-NBR B2 1312 originally from the BIRT is changed to its corresponding backup BFR- 1313 NBR. The BFR-NBR B2 in the first entry is changed to backup BFR-NBR 1314 BIER-LFA B6. The BFR-NBR B2 in the second entry is changed to backup 1315 BFR-NBR BIER-LFA B6. 1317 In the second step, BFR B1 derives the backup BIFT for link to B2 1318 from the backup BIRT for link to B2 in the same way as it derives its 1319 regular BIFT from its BIRT defined in [RFC8279]. The result of the 1320 backup BIFT for link to B2 is the one shown in Figure 14. 1322 When BFR B1 as a PLR detects the failure of its link to B2, it 1323 forwards all the BIER packets using the FRR-BIFT for link to B2. 1324 There is no redundant packet. For example, for a BIER packet with 1325 destinations B2 and B6 (i.e., bitstring 0100010), BFR B1 sends a 1326 single packet copy on the link to B6 using the backup BIFT for link 1327 to B2 after detecting the failure of its link to B2. It will not 1328 send any copy of the packet to B6 again since the bitstring in the 1329 packet will be all cleaned by the F-BM 1111110 after sending the 1330 packet to B6 via its link to B6. Similarly, for a BIER packet with 1331 destinations B2, B5 and B7 (i.e., bitstring 1010010), BFR B1 sends a 1332 single packet copy on its link to B6 using the backup BIFT for link 1333 to B2 after detecting the failure of its link to B2. 1335 Authors' Addresses 1337 Huaimo Chen (editor) 1338 Futurewei 1339 Boston, MA 1340 USA 1342 Email: Huaimo.chen@futurewei.com 1344 Mike McBride 1345 Futurewei 1347 Email: michael.mcbride@futurewei.com 1349 Steffen Lindner 1350 University of Tuebingen 1352 Email: steffen.lindner@uni-tuebingen.de 1354 Michael Menth 1355 University of Tuebingen 1357 Email: menth@uni-tuebingen.de 1358 Aijun Wang 1359 China Telecom 1360 Beiqijia Town, Changping District 1361 Beijing 102209 1362 China 1364 Email: wangaj3@chinatelecom.cn 1366 Gyan S. Mishra 1367 Verizon Inc. 1368 13101 Columbia Pike 1369 Silver Spring MD 20904 1370 USA 1372 Phone: 301 502-1347 1373 Email: gyan.s.mishra@verizon.com 1375 Yisong Liu 1376 China Mobile 1378 Email: liuyisong@chinamobile.com 1380 Yanhe Fan 1381 Casa Systems 1382 USA 1384 Email: yfan@casa-systems.com 1386 Lei Liu 1387 Fujitsu 1388 USA 1390 Email: liulei.kddi@gmail.com 1392 Xufeng Liu 1393 Volta Networks 1394 McLean, VA 1395 USA 1397 Email: xufeng.liu.ietf@gmail.com