idnits 2.17.1 draft-chen-bier-egress-protect-01.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 21, 2021) is 1131 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 120 -- Looks like a reference, but probably isn't: '65535' on line 120 == Unused Reference: 'RFC5226' is defined on line 765, but no explicit reference was found in the text == Unused Reference: 'RFC5250' is defined on line 770, but no explicit reference was found in the text == Unused Reference: 'RFC5714' is defined on line 779, but no explicit reference was found in the text == Unused Reference: 'RFC5880' is defined on line 783, but no explicit reference was found in the text == Unused Reference: 'RFC7684' is defined on line 797, but no explicit reference was found in the text == Unused Reference: 'RFC7770' is defined on line 802, but no explicit reference was found in the text == Unused Reference: 'RFC8556' is defined on line 817, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-segment-routing-ti-lfa' is defined on line 824, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-spring-segment-protection-sr-te-paths' is defined on line 830, but no explicit reference was found in the text == Unused Reference: 'RFC8296' is defined on line 841, but no explicit reference was found in the text == Unused Reference: 'RFC8401' is defined on line 847, but no explicit reference was found in the text == Unused Reference: 'RFC8444' is defined on line 852, but no explicit reference was found in the text ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) ** Downref: Normative reference to an Informational RFC: RFC 5714 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-segment-routing-ti-lfa-05 == Outdated reference: A later version (-06) exists of draft-ietf-spring-segment-protection-sr-te-paths-00 Summary: 2 errors (**), 0 flaws (~~), 15 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Chen 3 Internet-Draft M. McBride 4 Intended status: Standards Track Futurewei 5 Expires: August 25, 2021 A. Wang 6 China Telecom 7 G. Mishra 8 Verizon Inc. 9 Y. Liu 10 China Mobile 11 Y. Fan 12 Casa Systems 13 L. Liu 14 Fujitsu 15 X. Liu 16 Volta Networks 17 February 21, 2021 19 BIER Egress Protection 20 draft-chen-bier-egress-protect-01 22 Abstract 24 This document describes a mechanism for fast protection against the 25 failure of an egress node of a "Bit Index Explicit Replication" 26 (BIER) domain. It does not have any per-flow state in the core of 27 the domain. For a multicast packet to an egress node of the domain, 28 when the egress node fails, its upstream hop as a PLR sends the 29 packet to the egress' backup node once the PLR detects the failure. 31 Requirements Language 33 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 34 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 35 document are to be interpreted as described in [RFC2119] [RFC8174] 36 when, and only when, they appear in all capitals, as shown here. 38 Status of This Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at https://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on August 25, 2021. 55 Copyright Notice 57 Copyright (c) 2021 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (https://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the Simplified BSD License. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 73 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 74 2. Overview of BIER Egress Protection . . . . . . . . . . . . . 4 75 3. Protocol Extensions . . . . . . . . . . . . . . . . . . . . . 5 76 3.1. Extensions to OSPF . . . . . . . . . . . . . . . . . . . 5 77 3.2. Extensions to IS-IS . . . . . . . . . . . . . . . . . . . 6 78 4. BIER Extensions . . . . . . . . . . . . . . . . . . . . . . . 7 79 4.1. Egress Protection Bit Index Routing Tables . . . . . . . 7 80 4.2. Egress Protection Bit Index Forwarding Tables . . . . . . 9 81 4.3. Updated Forwarding Procedure . . . . . . . . . . . . . . 9 82 4.4. Switching between EP and Normal Forwarding . . . . . . . 10 83 5. Example Application of BIER Egress Protection . . . . . . . . 11 84 5.1. Example BIER Topology . . . . . . . . . . . . . . . . . . 11 85 5.2. BIRT and BIFT on a BFR . . . . . . . . . . . . . . . . . 12 86 5.3. EP-BIRTs and EP-BIFTs on a BFR . . . . . . . . . . . . . 13 87 5.4. Forwarding using EP-BIFT . . . . . . . . . . . . . . . . 15 88 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 89 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 90 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17 91 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 92 9.1. Normative References . . . . . . . . . . . . . . . . . . 17 93 9.2. Informative References . . . . . . . . . . . . . . . . . 18 94 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 96 1. Introduction 98 [RFC8279] specifies "Bit Index Explicit Replication" (BIER). It 99 provides optimal forwarding of multicast data packets through a 100 "multicast/BIER domain". It does not require the use of a protocol 101 for explicitly building multicast distribution trees, and it does not 102 require intermediate nodes to maintain any per-flow state. 104 This document describes a mechanism for fast protection against the 105 failure of an egress node of a "Bit Index Explicit Replication" 106 (BIER) domain, which is called BIER Egress Protection. 108 This BIER Egress Protection does not require intermediate nodes to 109 maintain any per-flow state for fast protection against the failure 110 of an egress node of the flow. 112 1.1. Terminology 114 BFR: Bit-Forwarding Router. 116 BFIR: Bit-Forwarding Ingress Router. 118 BFER: Bit-Forwarding Egress Router. 120 BFR-id: BFR Identifier. It is a number in the range [1,65535]. 122 BFR-NBR: BFR Neighbor. 124 F-BM: Forwarding Bit Mask. 126 BFR-prefix: An IP address (either IPv4 or IPv6) of a BFR. 128 BIRT: Bit Index Routing Table. It is a table that maps from the BFR- 129 id (in a particular sub-domain) of a BFER to the BFR-prefix of 130 that BFER, and to the BFR-NBR on the path to that BFER. 132 BIFT: Bit Index Forwarding Table. 134 FRR: Fast Re-Route. 136 PLR: Point of Local Repair. 138 LFA: Loop-Free Alternate. 140 RLFA: Remote LFA. 142 DLFA: Remote LFA with Directed forwarding. 144 IGP: Interior Gateway Protocol. 146 LSDB: Link State DataBase. 148 SPF: Shortest Path First. 150 SPT: Shortest Path Tree. 152 OSPF: Open Shortest Path First. 154 IS-IS: Intermediate System to Intermediate System. 156 LSA: Link State Advertisement in OSPF. 158 LSP: Link State Protocol Data Unit (PDU) in IS-IS. 160 SPT-old(R): The SPT rooted at node R using LSDB before X fails 161 (i.e., old LSDB). 163 SPT-new(R, X): The SPT rooted at node R using LSDB without X after X 164 fails (i.e., new LSDB). 166 P-Space P(R,X): The set of nodes that are reachable from R without 167 going through X. In other words, it is the set of nodes that 168 are not downstream of X in SPT-old(R). 170 Extended P-Space P'(R,X): The set of nodes that are reachable from R 171 or a neighbor of R, without going through X. 173 Q-Space Q(D,X): The set of nodes that do not use X to reach 174 destination D using the old LSDB. 176 PQ node(R,X): A member of both the P-Space P(R, X) (or the extended 177 P-Space P'(R, X)) and the Q-Space (D, X). 179 2. Overview of BIER Egress Protection 181 For fast protecting an egress node of a BIER domain, a backup egress 182 node is configured on the egress node. After the configuration, the 183 egress node distributes the information about the backup egress to 184 its direct neighbors. 186 For clearly distinguishing between an egress node and a backup egress 187 node, an egress node is called a primary egress node sometimes. 189 For a multicast packet to a primary egress node of the domain, when 190 the primary egress node fails, its upstream hop as a point of local 191 repair (PLR) sends the packet to the backup egress node configured to 192 protect the primary egress node once the PLR detects the failure. 194 A Bit-Forwarding Router (BFR) in a BIER sub-domain builds and 195 maintains an "Egress Protection Bit Index Routing Table" (EP-BIRT) 196 for each of its BFR Neighbors (BFR-NBRs) that are egress nodes of the 197 domain to provide fast protection against the failure of an egress 198 node. The BFR builds each EP-BIRT based on a BIRT defined in 199 [RFC8279]. An "Egress Protection Bit Index Forwarding Table" (EP- 200 BIFT) is derived from an EP-BIRT in a way that is similar to the way 201 in which a BIFT is derived from a BIRT, which is defined in 202 [RFC8279]. 204 Once the BFR as a PLR detects the failure of its BFR-NBR X that is a 205 primary egress node of the domain, for a multicast packet targeting 206 to the primary egress node, the PLR uses the EP-BIFT for X to send 207 the packet to the backup egress node configured to protect the 208 primary egress node. 210 3. Protocol Extensions 212 This section defines extensions to OSPF and IS-IS for advertising the 213 backup information (including the backup egress node for protecting a 214 primary egress node) to its direct neighbors. 216 3.1. Extensions to OSPF 218 When a node P (as a primary egress node) has a backup egress node 219 configured to protect against its failure, node P advertises the 220 information about the backup egress node to its neighbors in its 221 router information opaque LSA of LS type 9 or 10. The information is 222 included in a backup egress node TLV. The format of the TLV is shown 223 in Figure 1. 225 After each of the neighbors receives the backup egress node TLV, it 226 knows that node P as a primary egress node will be protected by the 227 backup egress node in the TLV. Once detecting the failure of node P, 228 it sends the packet targeting to node P towards the backup egress 229 node. 231 0 1 2 3 232 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Type (TBD1) | Length | 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 | Reserved | BFR-id of backup egress node | 237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 238 | Sub-TLVs (Optional) | 239 : : 240 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 242 Figure 1: OSPF Backup Egress TLV 244 Type: 2 octets, its value (TBD1) is to be assigned by IANA. 246 Length: 2 octets, its value is 4 plus the length of the Sub-TLVs 247 included. If no Sub-TLV is included, its value is 4. 249 Reserved: 2 octets, it MUST be set to zero when sending and be 250 ignored while receiving. 252 BFR-id of backup egress node: 2 octets, its value is the BFR-id of 253 the backup egress node configured to protect against the failure of 254 the primary egress node. 256 Sub-TLVs (Optional): No Sub-TLV is defined now. 258 3.2. Extensions to IS-IS 260 For supporting fast protection against the failure of a primary 261 egress node in a BIER domain, a new IS-IS TLV, called IS-IS backup 262 egress node TLV, is defined. It contains the BFR-id of a backup 263 egress node. 265 When a node P (as a primary egress node) has a backup egress node 266 configured to protect against its failure, node P advertises the 267 information about the backup egress node to its neighbors using a IS- 268 IS backup egress node TLV. 270 This TLV may be advertised in IS-IS Hello (IIH) PDUs, LSPs, or in 271 Circuit Scoped Link State PDUs (CS-LSP) [RFC7356]. The format of the 272 TLV is shown in Figure 2. 274 0 1 2 3 275 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 277 | Type (TBD2) | Length | BFR-id of backup egress node | 278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 ~ Sub-TLVs (Optional) ~ 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 Figure 2: IS-IS Backup Egress TLV 284 Type: 1 octet, its value (TBD2) is to be assigned by IANA. 286 Length: 1 octet, its value is 2 plus the length of the Sub-TLVs 287 included. If no Sub-TLV is included, its value is 2. 289 BFR-id of backup egress node: 2 octets, its value is the BFR-id of 290 the backup egress node configured to protect against the failure of 291 the primary egress node. 293 Sub-TLVs (Optional): No Sub-TLV is defined now. 295 4. BIER Extensions 297 4.1. Egress Protection Bit Index Routing Tables 299 If a BFR is a direct neighbor of an egress node in a BIER sub-domain, 300 it builds and maintains a number of "Egress Protection Bit Index 301 Routing Tables" (EP-BIRTs). There is an EP-BIRT for each of the 302 BFR's neighbors that are egress nodes of the domain. The BFR builds 303 each EP-BIRT based on its BIRT. Comparing to the BIRT, an EP-BIRT 304 has a piece of new backup information for each BFER. 306 The new backup information for a BFER indicates if the BFER as an 307 egress node is protected by the BFR. If so, the information further 308 includes the backup egress node configured to protect the BFER. 310 In one implementation, the new backup information is represented by 311 {EP, BE-BFER}. EP (short for Egress Protection) is a flag, 312 indicating whether the BFER as an egress node is protected. EP = 1 313 means that the BFER is protected. EP = 0 means that the BFER is not 314 protected. BE-BFER (short for Backup Egress BFER) is the BFER (i.e., 315 BFER-id) of the backup egress node when EP = 1. BE-BFER is NULL (0) 316 when EP = 0. 318 In the EP-BIRT for BFR-NBR X that is an egress node, the row having X 319 as BFER and as its next hop BFR-NBR contains the new backup 320 information {EP = 1, BE-BFER}, where BE-BFER is the BFER (i.e., BFER- 321 id) of backup egress node for protecting the egress node. Each of 322 the other rows in the EP-BIRT contains the new backup information {EP 323 = 0, BE-BFER = NULL}. 325 When the egress node fails, for a multicast packet targeting to the 326 primary egress node BFER (PE-BFER), the BFR sends the packet to the 327 BE-BFER through using the route to the backup egress node. The BFR 328 clears the bit for PE-BFER and adds the bit for BE-BFER in the 329 packet's BitString first, and then forwards the packet according to 330 the forwarding entry for BE-BFER. 332 The EP-BIRT for BFR-NBR X that is an egress node considers the 333 failure of X. It has a route or say a next hop (i.e., BFR-NBR N on 334 the path, where N is not X) to every BFER except for X. 336 The BFR may build the EP-BIRT for BFR-NBR X by copying its BIRT to 337 the EP-BIRT and sets the new information for each BFER to empty such 338 as {EP = 0, BE-BFER = NULL} first. And then it updates each of the 339 rows in the EP-BIRT that has X as BFER or next hop BFR-NBR X. 341 For the BFR-id of a BFER in the EP-BIRT for egress node X, when the 342 next hop BFR-NBR on the path to the BFER is X, the BFR checks whether 343 the BFER is X. If the BFER is not X, the BFR changes next hop BFR- 344 NBR X to a backup next hop (BNH) when there is a BNH on a backup path 345 to the BFER without going through X and the link from the BFR to X. 346 If the BFER is X, the BFR adds the new backup information {EP = 1, 347 BE-BFER} for the BFER as PE-BFER. 349 If there is not any BNH to a BFER to protect against the failure of 350 X, the next hop BFR-NBR X to the BFER in the EP-BIRT for BFR-NBR X is 351 changed to NULL. For a multicast packet having the BFER as one of 352 its destinations, if the next hop BFR-NBR to the BFER is NULL, the 353 BFR does not send the packet to the next hop BFR-NBR NULL but drops 354 it when X fails. 356 Note: In another option, the next hop BFR-NBR X to the BFER in the 357 EP-BIRT for BFR-NBR X keeps unchanged when there is not any BNH to 358 the BFER to protect against the failure of X. In this case, for a 359 multicast packet having the BFER as one of its destinations, the BFR 360 sends the packet to X when X fails. 362 In one implementation, the BNH is the Loop-Free Node-Protecting 363 Alternate defined in [RFC5286] to protect against the failure of X 364 and link from the BFR to X. In another implementation, the BNH is 365 the virtual Loop-Free Alternate (LFA), i.e., PQ node, defined in 366 [RFC7490]. In a special case, a PQ node is a Loop-Free Node- 367 Protecting Alternate defined in [RFC5286]. 369 4.2. Egress Protection Bit Index Forwarding Tables 371 From each EP-BIRT on the BFR, an "Egress Protection Bit Index 372 Forwarding Table" (EP-BIFT) is derived. In addition to having a 373 route to a BFER in each row of the EP-BIFT which is the same as the 374 EP-BIRT, it has a "Forwarding Bit Mask" (F-BM) in its each row. For 375 the rows in the EP-BIRT that have the same SI and the same BFR-NBR 376 and the same new backup information {EP, BE-BFER}, the F-BM for each 377 of these rows in the EP-BIFT is the logical OR of the BitStrings of 378 these rows. 380 This EP-BIFT is programmed into the data plane and is not used to 381 forward any packet in normal operations. It is activated to forward 382 a packet with a BIER header once the BFR detects the failure of BFR- 383 NBR. The header contains SI, BitString, BitStringLength, and sub- 384 domain. 386 4.3. Updated Forwarding Procedure 388 The forwarding procedure defined in [RFC8279] is updated/enhanced for 389 an EP-BIFT to consider the egress protection (i.e., the new 390 information {EP, BE-BFER} in the EP-BIFT). For a multicast packet 391 with the BitString indicating a BFER as one of its destinations, the 392 updated forwarding procedure sends the packet towards the backup 393 egress node of the BFER if the BFER is protected. It checks whether 394 EP = 1 in the forwarding entry for the BFER. If EP = 1, the 395 procedure clears the bit for the BFER as PE-BFER and adds the bit for 396 BE-BFER in the packet's BitString first, and then forwards the packet 397 using the row (i.e., forwarding entry) for BE-BFER. 399 The updated procedure is described in Figure 3. It is used with an 400 EP-BIFT for BFR-NBR X as egress node on a BFR to forward multicast 401 packets when X fails. It can also be used with a BIFT on the BFR to 402 forward multicast packets in normal operations if the new backup 403 information in each row of the BIFT is empty such as {EP = 0, BE-BFER 404 = NULL}. 406 Packet = the packet received by BFR; 407 FOR each BFER k (from the rightmost in Packet's BitString) { 408 IF BFER k is the BFR itself { 409 copies Packet, sends the copy to the multicast 410 flow overlay and clears bit k in Packet's BitString 411 } ELSE { 412 finds the row in the EP-BIFT for the sub-domain using 413 Packet's SI and BitString as the key/index 414 IF EP == 1 { 415 clears bit k in Packet's BitString; //BFER k is PE-BFER 416 adds bit j in Packet's BitString; //BFER j is BE-BFER 417 } ELSE { 418 IF BFR-NBR in the row is not NULL { 419 Copies Packet, updates the copy's BitString by ANDing 420 it with F-BM in the row,sends updated copy to BFR-NBR 421 } // BFR-NBR == NULL, not sent Packet to BFR-NBR 422 updates Packet's BitString by ANDing it with the INVERSE 423 of the F-BM in the row 424 } 425 } 426 } 428 Figure 3: Updated Forwarding Procedure 430 4.4. Switching between EP and Normal Forwarding 432 The EP-BIFTs will be pre-computed and installed ready for activation 433 when an egress node failure is detected. Once the BFR detects the 434 failure of its BFR-NBR X as an egress, it activates the EP-BIFT for X 435 to forward packets with BIER headers and de-activates its BIFT. 436 After activation of the EP-BIFT, it remains in effect until it is no 437 longer required. 439 In general, when the routing protocol has re-converged on the new 440 topology taking into account the failure of X, the BIRT is re- 441 computed using the updated LSDB and the BIFT is re-derived from the 442 BIRT. Once the BIFT is installed ready for activation, it is 443 activated to forward packets with BIER headers and the EP-BIFT for X 444 is de-activated. 446 From the new topology, the BFR computes/re-computes the EP-BIRT for 447 each BFR-NBR Y as an egress of the BFR and the EP-BIFT for Y is 448 derived/re-derived from the EP-BIRT for Y. The EP-BIFT is installed/ 449 re-installed ready for activation when Y fails. 451 5. Example Application of BIER Egress Protection 453 This section illustrates an example application of BIER Egress 454 Protection on a BFR in a BIER topology in Figure 4. 456 5.1. Example BIER Topology 458 An example BIER topology for a BIER sub-domain is shown in Figure 4. 459 It has 8 nodes/BFRs A, B, C, D, E, F, G and H. Each of the links 460 connecting these nodes/BFRs has a cost. The link cost of 1 is 461 default and is not indicated in the figure. The link costs of other 462 values such as 2 and 3 are indicated in the figure. 464 4 (0:01000) 465 /--------( G )--------- ( H ) Backup Egress for D 466 2/ 2\______ / \ 467 / _____)____/ \ 468 / / (____ (CE) Receiver 469 / / \ / 470 / / \ / 471 ( A )----------( B )-----------( C )----------( D ) Primary Egress 472 5 (0:10000) \ \ 1 (0:00001) 473 3\ \ 474 \ \ 475 ( E )-----------( F ) 476 3 (0:00100) 2 (0:00010) 478 Figure 4: Example BIER Topology 480 Nodes/BFRs D, F, E, H and A are BFERs and have BFR-ids 1, 2, 3, 4, 481 and 5 respectively. For simplicity, these BFR-ids are represented by 482 (SI:BitString), where SI = 0 and BitString is of 5 bits. BFR-ids 1, 483 2, 3, 4, and 5 are represented by (0:00001), (0:00010), (0:00100), 484 (0:01000) and (0:10000) respectively. 486 BFER H is configured to protect BFER D on BFR D. Suppose that this 487 information is distributed to BFR D's neighbors BFR C and BFR G by 488 IGP. BFR C and BFR G know that H is the backup egress to protect the 489 primary egress D. 491 CE is a multicast traffic Receiver, which is dual homed to primary 492 egress node D and backup egress node H for protecting primary egress 493 D. During normal operations, there is no multicast traffic to CE 494 from backup egress node H and CE receives the multicast traffic only 495 from primary egress node D. There is no duplicated traffic to 496 receiver CE. This is different from MoFRR in [RFC7431], where the 497 same traffic is sent through two separated paths/trees to both 498 primary egress node D and backup egress node H, to which the receiver 499 CE is dual homed. When primary egress node D fails, the multicast 500 traffic is sent to CE from backup egress node H. 502 The fast egress protection mechanism in this document will use less 503 network resources such as link bandwidth than MoFRR in [RFC7431]. 505 5.2. BIRT and BIFT on a BFR 507 Every BFR in a BIER sub-domain/topology builds and maintains a Bit 508 Index Routing Table (BIRT). For the BIER topology in Figure 4, each 509 of 8 nodes/BFRs A, B, C, D, E, F, G and H builds and maintains a BIRT 510 using the LSDB for the topology. 512 The BIRT built on BFR C (i.e. node C) is shown in Figure 5. 514 +----------------+--------------+------------+ 515 | BFR-id | BFR-Prefix | BFR-NBR | 516 | (SI:BitString) | of Dest BFER | (Next Hop) | 517 +================+==============+============+ 518 | 1 (0:00001) | D | D | 519 +----------------+--------------+------------+ 520 | 2 (0:00010) | F | F | 521 +----------------+--------------+------------+ 522 | 3 (0:00100) | E | F | 523 +----------------+--------------+------------+ 524 | 4 (0:01000) | H | H | 525 +----------------+--------------+------------+ 526 | 5 (0:10000) | A | B | 527 +----------------+--------------+------------+ 529 Figure 5: Bit Index Routing Table on BFR C 531 The 1st row in the BIRT indicates that the next hop BFR-NBR on the 532 shortest path to BFER D with BFR-id 1 is BFR D. 534 The 2nd row in the BIRT indicates that the next hop BFR-NBR on the 535 shortest path to BFER F with BFR-id 2 is BFR F. 537 The 3rd row in the BIRT indicates that the next hop BFR-NBR on the 538 shortest path to BFER E with BFR-id 3 is BFR F. 540 The 4-th row in the BIRT indicates that the next hop BFR-NBR on the 541 shortest path to BFER H with BFR-id 4 is BFR H. 543 The 5-th row in the BIRT indicates that the next hop BFR-NBR on the 544 shortest path to BFER A with BFR-id 5 is BFR B. 546 From this BIRT on BFR C, a Bit Index Forwarding Table (BIFT) is 547 derived. This BIFT is shown in Figure 6. 549 The 2nd and 3-th rows in the BIRT have the same SI = 0 and next hop 550 BFR-NBR = F. The F-BM for each of these two rows in the BIFT is the 551 logical OR of the BitStrings of these rows, which is 00110 (00010 OR 552 00100 = 00110). 554 The F-BM for 1st row in the BIFT is 00001. 556 The F-BM for 4-th row in the BIFT is 01000. 558 The F-BM for 5-th row in the BIFT is 10000. 560 +----------------+---------+------------+ 561 | BFR-id | F-BM | BFR-NBR | 562 | (SI:BitString) | | (Next Hop) | 563 +================+=========+============+ 564 | 1 (0:00001) | 00001 | D | 565 +----------------+---------+------------+ 566 | 2 (0:00010) | 00110 | F | 567 +----------------+---------+------------+ 568 | 3 (0:00100) | 00110 | F | 569 +----------------+---------+------------+ 570 | 4 (0:01000) | 01000 | H | 571 +----------------+---------+------------+ 572 | 5 (0:10000) | 10000 | B | 573 +----------------+---------+------------+ 575 Figure 6: Bit Index Forwarding Table on BFR C 577 5.3. EP-BIRTs and EP-BIFTs on a BFR 579 Each of the BFRs that are neighbors of egress nodes (i.e., BFERs) in 580 a BIER sub-domain/topology builds and maintains a number of Egress 581 Protection Bit Index Routing Tables (EP-BIRTs). 583 For the BIER topology in Figure 4, 585 BFR B is the neighbor of BFERs A and E; 586 BFR C is the neighbor of BFERs D, F and H; 587 BFR E is the neighbor of BFER F; 588 BFR F is the neighbor of BFER E; 589 BFR G is the neighbor of BFERs D and H. 591 Each of 5 nodes/BFRs B, C, E, F and G builds and maintains a number 592 of EP-BIRTs using the LSDB for the topology for its every BFR-NBR as 593 an egress node. 595 For example, BFR C (i.e., node C) in the BIER topology builds and 596 maintains three EP-BIRTs for its three BFR-NBRs (BFERs D, F and H) 597 that are egress nodes respectively. 599 The EP-BIRT for BEFR D built by BFR C based on the BIRT on BFR C 600 (refer to Figure 5) is shown in Figure 7. 602 The BIRT is copied to the EP-BIRT for BFER D (i.e., the first three 603 columns of the EP-BIRT). The new backup information (i.e., the 4-th 604 column) for every row in the EP-BIRT is initialized to {EP = 0, BE- 605 BFER = 0/NULL}. 607 +--------------+--------------+----------+----------------+ 608 | BFR-id | BFR-Prefix | BFR-NBR | {EP,BE-BFER} | 609 |(SI:BitString)| of Dest BFER |(Next Hop)| (Backup Info) | 610 +==============+==============+==========+================+ 611 | 1 (0:00001) | D | D/NULL |EP=1, BE-BFER=H | 612 +--------------+--------------+----------+----------------+ 613 | 2 (0:00010) | F | F |EP=0, BE-BFER=0 | 614 +--------------+--------------+----------+----------------+ 615 | 3 (0:00100) | E | F |EP=0, BE-BFER=0 | 616 +--------------+--------------+----------+----------------+ 617 | 4 (0:01000) | H | H |EP=0, BE-BFER=0 | 618 +--------------+--------------+----------+----------------+ 619 | 5 (0:10000) | A | B |EP=0, BE-BFER=0 | 620 +--------------+--------------+----------+----------------+ 622 Figure 7: EP-BIRT for BFER D on BFR C 624 In the EP-BIRT for BFER D, the row that has BFR-NBR == D is the 1st 625 row. This row has the new backup information {EP = 1, BE-BFER = H}, 626 which indicates that BFER D (i.e., primary egress node D) is 627 protected by BFER H (i.e., backup egress node H). Each of the other 628 rows has the new backup information {EP = 0, BE-BFER = 0/NULL}. 630 The 1st row in the EP-BIRT indicates that the next hop BFR-NBR on the 631 path to BFER D with BFR-id 1 is NULL (changed to NULL from D). There 632 is no backup next hop (BNH) to D when D fails. 634 The 2nd row in the EP-BIRT indicates that the next hop BFR-NBR on the 635 path to BFER F with BFR-id 2 is BFR F. 637 The 3rd row in the EP-BIRT indicates that the next hop BFR-NBR on the 638 path to BFER E with BFR-id 3 is BFR F. 640 The 4-th row in the EP-BIRT indicates that the next hop BFR-NBR on 641 the path to BFER H with BFR-id 4 is BFR H. 643 The 5-th row in the EP-BIRT indicates that the next hop BFR-NBR on 644 the path to BFER A with BFR-id 5 is BFR B. 646 From this EP-BIRT for BFER D on BFR C, an Egress Protection Bit Index 647 Forwarding Table (EP-BIFT) is derived. This EP-BIFT for BFER D is 648 shown in Figure 8. 650 The 2nd and 3rd rows in the EP-BIRT have the same SI = 0, the same 651 next hop BFR-NBR = E and the same backup information {EP=0, BE- 652 BFER=0}. The F-BM for each of these two rows in the EP-BIFT is the 653 logical OR of the BitStrings of these rows, which is 00110 (00010 OR 654 00100 = 00110). 656 +----------------+---------+------------+----------------+ 657 | BFR-id | F-BM | BFR-NBR | {EP,BE-BFER} | 658 | (SI:BitString) | | (Next Hop) | (Backup Info) | 659 +================+=========+============+================+ 660 | 1 (0:00001) | 00001 | NULL |EP=1, BE-BFER=H | 661 +----------------+---------+------------+----------------+ 662 | 2 (0:00010) | 00110 | F |EP=0, BE-BFER=0 | 663 +----------------+---------+------------+----------------+ 664 | 3 (0:00100) | 00110 | F |EP=0, BE-BFER=0 | 665 +----------------+---------+------------+----------------+ 666 | 4 (0:01000) | 01000 | H |EP=0, BE-BFER=0 | 667 +----------------+---------+------------+----------------+ 668 | 5 (0:10000) | 10000 | B |EP=0, BE-BFER=0 | 669 +----------------+---------+------------+----------------+ 671 Figure 8: EP-BIFT for BFER D on BFR C 673 The F-BM for 1st row in the EP-BIFT is 00001. 674 The F-BM for 4-th row in the EP-BIFT is 01000. 675 The F-BM for 5-th row in the EP-BIFT is 10000. 677 5.4. Forwarding using EP-BIFT 679 Suppose that there is a multicast traffic from BFR A as ingress/BFIR 680 to egresses/BFERs D, F and E. For every packet of the traffic, after 681 receiving it, BFR A adds a BIER header into the packet and sends the 682 packet with the BIER header to BFR B, which sends the packet BFR C. 683 The BIER header contains (SI:BitString) = (0:00111) for egresses/ 684 BFERs D, F and E. 686 In normal operations, after receiving the packet from BFR B, BFR C 687 copies, updates and sends the packet to BFR D and BFR F using the 688 BIFT on BFR C according to the forwarding procedure defined in 689 [RFC8279]. 691 Once BFR C detects the failure of its BFR-NBR D, which is a BFER, 692 after receiving the packet from BFR B, BFR C copies, updates and 693 sends the packet using the EP-BIFT for BFER D on BFR C according to 694 the updated forwarding procedure. 696 For the packet targeting to BFER D (i.e., primary egress node), BFR C 697 sends it towards BFER H (i.e., backup egress node), which is 698 configured to protect BFER D. 700 For example, once BFR C detects the failure of its BFR-NBR D, after 701 receiving the packet from BFR B, BFR C copies, updates and sends the 702 packet to BFR H and BFR F using the EP-BIFT for BFER D on BFR C. 704 The packet received by BFR C from BFR B contains (SI:BitString) = 705 (0:00111). The rightmost one bit in BitString is bit 1. For BFER 1 706 (0:00001) (i.e., BFR D as BFER), BFR C gets the 1st row (i.e., 707 forwarding entry) in the EP-BIFT for BFER D. EP = 1 in the row 708 indicates that BFER D is protected against the failure of D. BFR C 709 clears bit 1 in Packet's BitString and sets bit 4 (i.e., the bit for 710 BE-BFER = H) in Packet's BitString to one. The BitString in Packet 711 is 01110 now. This lets BFR C send Packet to BE-BFER H. 713 For the packet containing BitString = 01110, the rightmost one bit in 714 BitString is bit 2. For BFER 2 (0:00010) (i.e., BFR F as BFER), BFR 715 C gets the 2nd row (i.e., forwarding entry) in the EP-BIFT for BFER 716 D. EP = 0 and the next hop BFR-NBR is F in the row. BFR C copies, 717 updates and sends the packet to F. 719 The packet sent to F contains the updated BitString = 00110, which is 720 01110 & F-BM in the 2nd row = 01110 & 00110 = 00110. 722 After sending the packet to F, BFR C updates the original packet by 723 ANDing its BitString with the INVERSE of the F-BM in the 2nd row. 724 The updated BitString = 01000, which is 01110 & ~F-BM in the row = 725 01110 & 11001 = 01000. 727 For the packet containing BitString = 01000, the rightmost one bit in 728 BitString is bit 4. For BFER 4 (0:01000) (i.e., BFR H as BFER), BFR 729 C gets the 4-th row (i.e., forwarding entry) in the EP-BIFT for BFER 730 D. EP = 0 and the next hop BFR-NBR is H in the row. BFR C copies, 731 updates and sends the packet to H. The packet sent to H contains 732 BitString = 01000. 734 After sending the packet to H, BFR C updates the original packet by 735 ANDing its BitString with the INVERSE of the F-BM in the 4-th row. 736 The updated BitString = 00000, which is 01000 & ~F-BM in the row = 737 01000 & 10111 = 00000. 739 The updated packet has BitString without any one bit. BFR C finishes 740 forwarding the packet to F and H (backup for D). BFR F will sends 741 the packet to E. 743 6. Security Considerations 745 TBD. 747 7. IANA Considerations 749 No requirements for IANA. 751 8. Acknowledgements 753 The authors would like to thank people for their comments to this 754 work. 756 9. References 758 9.1. Normative References 760 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 761 Requirement Levels", BCP 14, RFC 2119, 762 DOI 10.17487/RFC2119, March 1997, 763 . 765 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 766 IANA Considerations Section in RFCs", RFC 5226, 767 DOI 10.17487/RFC5226, May 2008, 768 . 770 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 771 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 772 July 2008, . 774 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 775 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 776 DOI 10.17487/RFC5286, September 2008, 777 . 779 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 780 RFC 5714, DOI 10.17487/RFC5714, January 2010, 781 . 783 [RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding Detection 784 (BFD)", RFC 5880, DOI 10.17487/RFC5880, June 2010, 785 . 787 [RFC7356] Ginsberg, L., Previdi, S., and Y. Yang, "IS-IS Flooding 788 Scope Link State PDUs (LSPs)", RFC 7356, 789 DOI 10.17487/RFC7356, September 2014, 790 . 792 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 793 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 794 RFC 7490, DOI 10.17487/RFC7490, April 2015, 795 . 797 [RFC7684] Psenak, P., Gredler, H., Shakir, R., Henderickx, W., 798 Tantsura, J., and A. Lindem, "OSPFv2 Prefix/Link Attribute 799 Advertisement", RFC 7684, DOI 10.17487/RFC7684, November 800 2015, . 802 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 803 S. Shaffer, "Extensions to OSPF for Advertising Optional 804 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 805 February 2016, . 807 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 808 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 809 May 2017, . 811 [RFC8279] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 812 Przygienda, T., and S. Aldrin, "Multicast Using Bit Index 813 Explicit Replication (BIER)", RFC 8279, 814 DOI 10.17487/RFC8279, November 2017, 815 . 817 [RFC8556] Rosen, E., Ed., Sivakumar, M., Przygienda, T., Aldrin, S., 818 and A. Dolganow, "Multicast VPN Using Bit Index Explicit 819 Replication (BIER)", RFC 8556, DOI 10.17487/RFC8556, April 820 2019, . 822 9.2. Informative References 824 [I-D.ietf-rtgwg-segment-routing-ti-lfa] 825 Litkowski, S., Bashandy, A., Filsfils, C., Decraene, B., 826 and D. Voyer, "Topology Independent Fast Reroute using 827 Segment Routing", draft-ietf-rtgwg-segment-routing-ti- 828 lfa-05 (work in progress), November 2020. 830 [I-D.ietf-spring-segment-protection-sr-te-paths] 831 Hegde, S., Bowers, C., Litkowski, S., Xu, X., and F. Xu, 832 "Segment Protection for SR-TE Paths", draft-ietf-spring- 833 segment-protection-sr-te-paths-00 (work in progress), 834 September 2020. 836 [RFC7431] Karan, A., Filsfils, C., Wijnands, IJ., Ed., and B. 837 Decraene, "Multicast-Only Fast Reroute", RFC 7431, 838 DOI 10.17487/RFC7431, August 2015, 839 . 841 [RFC8296] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 842 Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation 843 for Bit Index Explicit Replication (BIER) in MPLS and Non- 844 MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January 845 2018, . 847 [RFC8401] Ginsberg, L., Ed., Przygienda, T., Aldrin, S., and Z. 848 Zhang, "Bit Index Explicit Replication (BIER) Support via 849 IS-IS", RFC 8401, DOI 10.17487/RFC8401, June 2018, 850 . 852 [RFC8444] Psenak, P., Ed., Kumar, N., Wijnands, IJ., Dolganow, A., 853 Przygienda, T., Zhang, J., and S. Aldrin, "OSPFv2 854 Extensions for Bit Index Explicit Replication (BIER)", 855 RFC 8444, DOI 10.17487/RFC8444, November 2018, 856 . 858 Authors' Addresses 860 Huaimo Chen 861 Futurewei 862 Boston, MA 863 USA 865 Email: Huaimo.chen@futurewei.com 867 Mike McBride 868 Futurewei 870 Email: michael.mcbride@futurewei.com 872 Aijun Wang 873 China Telecom 874 Beiqijia Town, Changping District 875 Beijing, 102209 876 China 878 Email: wangaj3@chinatelecom.cn 879 Gyan S. Mishra 880 Verizon Inc. 881 13101 Columbia Pike 882 Silver Spring MD 20904 883 USA 885 Phone: 301 502-1347 886 Email: gyan.s.mishra@verizon.com 888 Yisong Liu 889 China Mobile 891 Email: liuyisong@chinamobile.com 893 Yanhe Fan 894 Casa Systems 895 USA 897 Email: yfan@casa-systems.com 899 Lei Liu 900 Fujitsu 902 USA 904 Email: liulei.kddi@gmail.com 906 Xufeng Liu 907 Volta Networks 909 McLean, VA 910 USA 912 Email: xufeng.liu.ietf@gmail.com