idnits 2.17.1 draft-wijnands-bier-architecture-05.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 (March 6, 2015) is 3337 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: '0' on line 312 -- Looks like a reference, but probably isn't: '255' on line 312 -- Looks like a reference, but probably isn't: '1' on line 263 -- Looks like a reference, but probably isn't: '65535' on line 246 -- Looks like a reference, but probably isn't: '256' on line 261 -- Looks like a reference, but probably isn't: '512' on line 263 -- Looks like a reference, but probably isn't: '15' on line 311 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force IJ. Wijnands, Ed. 3 Internet-Draft Cisco Systems, Inc. 4 Intended status: Standards Track E. Rosen, Ed. 5 Expires: September 7, 2015 Juniper Networks, Inc. 6 A. Dolganow 7 Alcatel-Lucent 8 T. Przygienda 9 Ericsson 10 S. Aldrin 11 Huawei Technologies 12 March 6, 2015 14 Multicast using Bit Index Explicit Replication 15 draft-wijnands-bier-architecture-05 17 Abstract 19 This document specifies a new architecture for the forwarding of 20 multicast data packets. It provides optimal forwarding of multicast 21 packets through a "multicast domain". However, it does not require 22 any explicit tree-building protocol, nor does it require intermediate 23 nodes to maintain any per-flow state. This architecture is known as 24 "Bit Index Explicit Replication" (BIER). When a multicast data 25 packet enters the domain, the ingress router determines the set of 26 egress routers to which the packet needs to be sent. The ingress 27 router then encapsulates the packet in a BIER header. The BIER 28 header contains a bitstring in which each bit represents exactly one 29 egress router in the domain; to forward the packet to a given set of 30 egress routers, the bits corresponding to those routers are set in 31 the BIER header. Elimination of the per-flow state and the explicit 32 tree-building protocols results in a considerable simplification. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on September 7, 2015. 50 Copyright Notice 52 Copyright (c) 2015 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. The BFR Identifier and BFR-Prefix . . . . . . . . . . . . . . 5 69 3. Encoding BFR Identifiers in BitStrings . . . . . . . . . . . 6 70 4. Layering . . . . . . . . . . . . . . . . . . . . . . . . . . 8 71 4.1. The Routing Underlay . . . . . . . . . . . . . . . . . . 8 72 4.2. The BIER Layer . . . . . . . . . . . . . . . . . . . . . 9 73 4.3. The Multicast Flow Overlay . . . . . . . . . . . . . . . 10 74 5. Advertising BFR-ids and BFR-Prefixes . . . . . . . . . . . . 10 75 6. BIER Intra-Domain Forwarding Procedures . . . . . . . . . . . 12 76 6.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 12 77 6.2. BFR Neighbors . . . . . . . . . . . . . . . . . . . . . . 13 78 6.3. The Bit Index Routing Table . . . . . . . . . . . . . . . 14 79 6.4. The Bit Index Forwarding Table . . . . . . . . . . . . . 14 80 6.5. The BIER Forwarding Procedure . . . . . . . . . . . . . . 15 81 6.6. Examples of BIER Forwarding . . . . . . . . . . . . . . . 17 82 6.6.1. Example 1 . . . . . . . . . . . . . . . . . . . . . . 18 83 6.6.2. Example 2 . . . . . . . . . . . . . . . . . . . . . . 18 84 6.7. Equal Cost Multi-path Forwarding . . . . . . . . . . . . 20 85 6.7.1. Non-deterministic ECMP . . . . . . . . . . . . . . . 21 86 6.7.2. Deterministic ECMP . . . . . . . . . . . . . . . . . 22 87 6.8. Prevention of Loops and Duplicates . . . . . . . . . . . 24 88 6.9. When Some Nodes do not Support BIER . . . . . . . . . . . 24 89 6.10. Use of Different BitStringLengths within a Domain . . . . 26 90 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 91 8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 92 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27 93 10. Contributor Addresses . . . . . . . . . . . . . . . . . . . . 27 94 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 95 11.1. Normative References . . . . . . . . . . . . . . . . . . 29 96 11.2. Informative References . . . . . . . . . . . . . . . . . 29 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 29 99 1. Introduction 101 This document specifies a new architecture for the forwarding of 102 multicast data packets. It provides optimal forwarding of multicast 103 data packets through a "multicast domain". However, it does not 104 require any explicit tree-building protocol, and does not require 105 intermediate nodes to maintain any per-flow state. This architecture 106 is known as "Bit Index Explicit Replication" (BIER). 108 A router that supports BIER is known as a "Bit-Forwarding Router" 109 (BFR). A BIER domain is a connected set of BFRs. The BIER control 110 plane protocols (see Section 4.2) run within a BIER domain, allowing 111 the BFRs within that domain to exchange the necessary information. 113 A multicast data packet enters a BIER domain at a "Bit-Forwarding 114 Ingress Router" (BFIR), and leaves the BIER domain at one or more 115 "Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a 116 multicast data packet from another BFR in the same BIER domain, and 117 forwards the packet to another BFR in the same BIER domain, will be 118 known as a "transit BFR" for that packet. A single BFR may be a BFIR 119 for some multicast traffic while also being a BFER for some multicast 120 traffic and a transit BFR for some multicast traffic. In fact, a BFR 121 may be the BFIR for a given packet and may also be (one of) the 122 BFER(s), for that packet; it may also forward that packet to one or 123 more additional BFRs. 125 A BIER domain may contain one or more sub-domains. Each BIER domain 126 MUST contain at least one sub-domain, the "default sub-domain" (also 127 denoted "sub-domain zero"). If a BIER domain contains more than one 128 sub-domain, each BFR in the domain MUST be provisioned to know the 129 set of sub-domains to which it belongs. Each sub-domain is 130 identified by a sub-domain-id in the range [0,255]. 132 For each sub-domain to which a given BFR belongs, if the BFR is 133 capable of acting as a BFIR or a BFER, it MUST be provisioned with a 134 "BFR-id" that is unique within the sub-domain. A BFR-id is a small 135 unstructured number. For instance, if a particular BIER sub-domain 136 contains 1,374 BFRs, each one could be given a BFR-id in the range 137 1-1374. 139 If a given BFR belongs to more than one sub-domain, it may (though it 140 need not) have a different BFR-id for each sub-domain. 142 When a multicast packet arrives from outside the domain at a BFIR, 143 the BFIR determines the set of BFERs to which the packet must be 144 sent. The BFIR also determines the sub-domain over which the packet 145 must be sent. (Procedures for assigning a particular packet to a 146 particular sub-domain are outside the scope of this document.) The 147 BFIR then encapsulates the packet in a "BIER header". The BIER 148 header contains a bit string in which each bit represents a single 149 BFR-id. To indicate that a particular BFER needs to receive a given 150 packet, the BFIR sets the bit corresponding to that BFER's BFR-id in 151 the sub-domain to which the packet has been assigned. We will use 152 term "BitString" to refer to the bit string field in the BIER header. 153 We will use the term "payload" to refer to the packet that has been 154 encapsulated. Thus a "BIER-encapsulated" packet consists of a "BIER 155 header" followed by a "payload". 157 The number of BFERs to which a given packet can be forwarded is 158 limited only by the length of the BitString in the BIER header. 159 Different deployments can use different BitString lengths. We will 160 use the term "BitStringLength" to refer to the number of bits in the 161 BitString. It is possible that some deployment will have more BFERs 162 in a given sub-domain than there are bits in the BitString. To 163 accommodate this case, the BIER encapsulation includes both the 164 BitString and a "Set Identifier" (SI). It is the BitString and the 165 SI together that determine the set of BFERs to which a given packet 166 will be delivered: 168 o by convention, the least significant (rightmost) bit in the 169 BitString is "bit 1", and the most significant (leftmost) bit is 170 "bit BitStringLength". 172 o if a BIER-encapsulated packet has an SI of n, and a BitString with 173 bit k set, then the packet must be delivered to the BFER whose 174 BFR-id (in the sub-domain to which the packet has been assigned) 175 is n*BitStringLength+k. 177 For example, suppose the BIER encapsulation uses a BitStringLength of 178 256 bits. By convention, the least significant (rightmost) bit is 179 "bit 1", and the most significant (leftmost) bit is "bit 256". 180 Suppose that a given packet has been assigned to sub-domain 0, and 181 needs to be delivered to three BFERs, where those BFERs have BFR-ids 182 in sub-domain 0 of 13, 126, and 235 respectively. The BFIR would 183 create a BIER encapsulation with the SI set to zero, and with bits 184 13, 126, and 235 of the BitString set. (All other bits of the 185 BitString would be clear.) If the packet also needs to be sent to a 186 BFER whose BFR-id is 257, the BFIR would have to create a second copy 187 of the packet, and the BIER encapsulation would specify an SI of 1, 188 and a BitString with bit 1 set and all the other bits clear. 190 Note that it is generally advantageous to assign the BFR-ids so that 191 as many BFERs as possible can be represented in a single bit string. 193 Suppose a BFR, call it BFR-A, receives a packet whose BIER 194 encapsulation specifies an SI of 0, and a BitString with bits 13, 26, 195 and 235 set. Suppose BFR-A has two BFR neighbors, BFR-B and BFR-C, 196 such that the best path to BFERs 13 and 26 is via BFR-B, but the best 197 path to BFER 235 is via BFR-C. Then BFR-A will replicate the packet, 198 sending one copy to BFR-B and one copy to BFR-C. However, BFR-A will 199 clear bit 235 in the BitString of the packet copy it sends to BFR-B, 200 and will clear bits 13 and 26 in the BitString of the packet copy it 201 sends to BFR-C. As a result, BFR-B will forward the packet only 202 towards BFERs 13 and 26, and BFR-C will forward the packet only 203 towards BFER 235. This ensures that each BFER receives only one copy 204 of the packet. 206 With this forwarding procedure, a multicast data packet can follow an 207 optimal path from its BFIR to each of its BFERs. Further, since the 208 set of BFERs for a given packet is explicitly encoded into the BIER 209 header, the packet is not sent to any BFER that does not need to 210 receive it. This allows for optimal forwarding of multicast traffic. 211 This optimal forwarding is achieved without any need for transit BFRs 212 to maintain per-flow state, or to run a multicast tree-building 213 protocol. 215 The idea of encoding the set of egress nodes into the header of a 216 multicast packet is not new. For example, [Boivie_Feldman] proposes 217 to encode the set of egress nodes as a set of IP addresses, and 218 proposes mechanisms and procedures that are in some ways similar to 219 those described in the current document. However, since BIER encodes 220 each BFR-id as a single bit in a bit string, it can represent up to 221 128 BFERs in the same number of bits that it would take to carry the 222 IPv6 address of a single BFER. Thus BIER scales to a much larger 223 number of egress nodes per packet. 225 BIER does not require that each transit BFR look up the best path to 226 each BFER that is identified in the BIER header; the number of 227 lookups required in the forwarding path for a single packet can be 228 limited to the number of neighboring BFRs; this can be much smaller 229 than the number of BFERs. See Section 6 (especially Section 6.4) for 230 details. 232 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 233 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 234 document are to be interpreted as described in RFC 2119 [RFC2119]. 236 2. The BFR Identifier and BFR-Prefix 238 Each BFR MUST be assigned a "BFR-Prefix". A BFR's BFR-Prefix MUST be 239 an IP address (either IPv4 or IPv6) of the BFR, and MUST be unique 240 and routable within the BIER domain. It is RECOMMENDED that the 241 BFR-prefix be a loopback address of the BFR. Two BFRs in the same 242 BIER domain MUST NOT be assigned the same BFR-Prefix. Note that a 243 BFR in a given BIER domain has the same BFR-prefix in all the sub- 244 domains of that BIER domain. 246 A "BFR Identifier" (BFR-id) is a number in the range [1,65535]. In 247 general, each BFR in a given BIER sub-domain must be assigned a 248 unique number from this range (i.e., two BFRs in the same BIER sub- 249 domain MUST NOT have the same BFR-id in that sub-domain). However, 250 if it is known that a given BFR will never need to function as a BFER 251 in a given sub-domain, then it is not necessary to assign a BFR-id 252 for that sub-domain to that BFR. 254 Note that the value 0 is not a legal BFR-id. 256 The procedure for assigning a particular BFR-id to a particular BFR 257 is outside the scope of this document. However, it is RECOMMENDED 258 that the BFR-ids for each sub-domain be assigned "densely" from the 259 numbering space, as this will result in a more efficient encoding 260 (see Section 3). That is, if there are 256 or fewer BFERs, it is 261 RECOMMENDED to assign all the BFR-ids from the range [1,256]. If 262 there are more than 256 BFERs, but less than 512, it is RECOMMENDED 263 to assign all the BFR-ids from the range [1,512], with as few "holes" 264 as possible in the earlier range. However, in some deployments, it 265 may be advantageous to depart from this recommendation; this is 266 discussed further in Section 3. 268 3. Encoding BFR Identifiers in BitStrings 270 To encode a BFR-id in a BIER data packet, one must convert the BFR-id 271 to an SI and a BitString. This conversion depends upon the parameter 272 we are calling "BitStringLength". The conversion is done as follows. 273 If the BFR-id is N, then 275 o SI is the integer part of the quotient (N-1)/BitStringLength 277 o The BitString has one bit position set. If the low-order bit is 278 bit 1, and the high-order bit is bit BitStringLength, the bit 279 position that represents BFR-id N is 280 ((N-1) modulo BitStringLength)+1. 282 If several different BFR-ids all resolve to the same SI, then all 283 those BFR-ids can be represented in a single BitString. The 284 BitStrings for all of those BFR-ids are combined using a bitwise 285 logical OR operation. 287 Different BIER domains may use different values of BitStringLength. 288 Each BFIR in a given BIER domain MUST be provisioned to know the 289 BitStringLength to use when imposing a BIER encapsulation on a 290 particular set of packets. This value of BitStringLength SHOULD be a 291 value that is supported by all the BFRs in the domain. (That is, the 292 BitStringLength value used by a BFIR when imposing a BIER 293 encapsulation on a particular packet SHOULD be a value that is 294 supported by all the BFRs and BFERs in the domain that might have to 295 forward or receive the packet.) However, under certain 296 circumstances, it is possible to make exceptions to this rule. This 297 is discussed in Section 6.10. 299 Every BFIR MUST be able to impose a BIER encapsulation whose 300 BitStringLength of 256. Every BFR MUST be able to forward a BIER- 301 encapsulated packet whose BitStringLength is 256. Every BFER MUST be 302 able to receive and properly process a BIER-encapsulated packet whose 303 BitStringLength is 256. 305 Particular BIER encapsulation types MAY allow other BitStringLengths 306 to be OPTIONALLY supported. For example, when using the 307 encapsulation specified in [MPLS_BIER_ENCAPS], a BFR may support any 308 or all of the following BitStringLengths: 64, 128, 256, 512, 1024, 309 2048, and 4096. 311 A BFR MUST support SI values in the range [0,15], and MAY support SI 312 values in the range [0,255]. ("Supporting the values in a given 313 range" means, in this context, that any value in the given range is 314 legal, and will be properly interpreted.) 316 When a BFIR determines that a multicast data packet, assigned to a 317 given sub-domain, needs to be forwarded to a particular set of 318 destination BFERs, the BFIR partitions that set of BFERs into 319 subsets, where each subset contains the target BFERs whose BFR-ids in 320 the given sub-domain all resolve to the same SI. Call these the 321 "SI-subsets" for the packet. Each SI-subset can be represented by a 322 single BitString. The BFIR creates a copy of the packet for each 323 SI-subset. The BIER encapsulation is then applied to each packet. 324 The encapsulation specifies a single SI for each packet, and contains 325 the BitString that represents all the BFR-ids in the corresponding 326 SI-subset. Of course, in order to properly interpret the BitString, 327 it must be possible to infer the sub-domain-id from the encapsulation 328 as well. 330 Suppose, for example, that a BFIR determines that a given packet 331 needs to be forwarded to three BFERs, whose BFR-ids (in the 332 appropriate sub-domain) are 27, 235, and 497. The BFIR will have to 333 forward two copies of the packet. One copy, associated with SI=0, 334 will have a BitString with bits 27 and 235 set. The other copy, 335 associated with SI=1, will have a BitString with bit 241 set. 337 In order to minimize the number of copies that must be made of a 338 given multicast packet, it is RECOMMENDED that the BFR-ids be 339 assigned "densely" (see Section 2) from the numbering space. This 340 will minimize the number of SIs that have to be used in the domain. 341 However, depending upon the details of a particular deployment, other 342 assignment methods may be more advantageous. Suppose, for example, 343 that in a certain deployment, every multicast flow is either intended 344 for the "east coast" or for the "west coast". In such a deployment, 345 it would be advantageous to assign BFR-ids so that all the "west 346 coast" BFR-ids fall into the same SI-subset, and so that all the 347 "east coast" BFR-ids fall into the same SI-subset. 349 When a BFR receives a BIER data packet, it will infer the SI from the 350 encapsulation. The set of BFERs to which the packet needs to be 351 forwarded can then be inferred from the SI and the BitString. 353 In some of the examples given later in this document, we will use a 354 BitStringLength of 4, and will represent a BFR-id in the form 355 "SI:xyzw", where SI is the Set Identifier of the BFR-id (assuming a 356 BitStringLength of 4), and xyzw is a string of 4 bits. A 357 BitStringLength of 4 is used only in the examples; we would not 358 expect actual deployments to have such a small BitStringLength. 360 It is possible that several different forms of BIER encapsulation 361 will be developed. If so, the particular encapsulation that is used 362 in a given deployment will depend on the type of network 363 infrastructure that is used to realize the BIER domain. Details of 364 the BIER encapsulation(s) will be given in companion documents. An 365 encapsulation for use in MPLS networks is described in 366 [MPLS_BIER_ENCAPS] 368 4. Layering 370 It is helpful to think of the BIER architecture as consisting of 371 three layers: the "routing underlay", the "BIER layer", and the 372 "multicast flow overlay". 374 4.1. The Routing Underlay 376 The "routing underlay" establishes "adjacencies" between pairs of 377 BFRs, and determines one or more "best paths" from a given BFR to a 378 given set of BFRs. Each such path is a sequence of BFRs such that BFR(k+j) is "adjacent" to 380 BFR(k+j+1) (for 0<=j and BitStringLength can be done using the 489 advertisement capabilities of the IGP. For example, if a BIER domain 490 is also an OSPF domain, these advertisements can be done using the 491 OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism. 492 Details of the necessary extensions to OSPF and IS-IS will be 493 provided in companion documents. (See [OSPF_BIER_EXTENSIONS] and 494 [ISIS_BIER_EXTENSIONS].) 496 These advertisements enable each BFR to associate a given with a given BFR-prefix. As will be seen in 498 subsequent sections of this document, knowledge of this association 499 is an important part of the forwarding process. 501 Since each BFR needs to have a unique (in each sub-domain) BFR-id, 502 two different BFRs will not advertise ownership of the same unless there has been a provisioning error. 505 o If BFR-A determines that BFR-B and BFR-C have both advertised the 506 same BFR-id for the same sub-domain, BFR-A MUST log an error. 507 Suppose that the duplicate BFR-id is "N". When BFR-A is 508 functioning as a BFIR, it MUST NOT encode the BFR-id value N in 509 the BIER encapsulation of any packet that has been assigned to the 510 given sub-domain, even if it has determined that the packet needs 511 to be received by BFR-B and/or BFR-C. 513 This will mean that BFR-B and BFR-C cannot receive multicast 514 traffic at all in the given sub-domain until the provisioning 515 error is fixed. However, that is preferable to having them 516 receive each other's traffic. 518 o If BFR-A has been provisioned with BFR-id N for a particular sub- 519 domain, has not yet advertised its ownership of BFR-id N for that 520 sub-domain, but has received an advertisement from a different BFR 521 (say BFR-B) that is advertising ownership of BFR-id N for the same 522 sub-domain, then BFR-A SHOULD log an error, and MUST NOT advertise 523 its own ownership of BFR-id N for that sub-domain as long as the 524 advertisement from BFR-B is extant. 526 This procedure may prevent the accidental misconfiguration of a 527 new BFR from impacting an existing BFR. 529 If a BFR advertises that it has a BFR-id of 0 in a particular sub- 530 domain, other BFRs receiving the advertisement MUST interpret that 531 advertisement as meaning that the advertising BFR does not have a 532 BFR-id in that sub-domain. 534 6. BIER Intra-Domain Forwarding Procedures 536 This section specifies the rules for forwarding a BIER-encapsulated 537 data packet within a BIER domain. 539 6.1. Overview 541 This section provides a brief overview of the BIER forwarding 542 procedures. Subsequent sub-sections specify the procedures in more 543 detail. 545 To forward a BIER-encapsulated packet: 547 1. Determine the packet's sub-domain. 549 2. Determine the packet's SI. 551 3. From the sub-domain, the SI and the BitString, determine the set 552 of destination BFERs for the packet. 554 4. Using information provided by the routing underlay associated 555 with the packet's sub-domain, determine the next hop adjacency 556 for each of the destination BFERs. 558 5. Partition the set of destination BFERs such that all the BFERs in 559 a single partition have the same next hop. We will say that each 560 partition is associated with a next hop. 562 6. For each partition: 564 a. Make a copy of the packet. 566 b. Clear any bit in the packet's BitString that identifies a 567 BFER that is not in the partition. 569 c. Transmit the packet to the associated next hop. 571 If a BFR receives a BIER-encapsulated packet whose sub-domain, SI and 572 BitString identify that BFR itself, then the BFR is also a BFER for 573 that packet. As a BFER, it must pass the payload to the multicast 574 flow overlay. If the BitString has more than one bit set, the packet 575 also needs to be forwarded further within the BIER domain. If the 576 BF(E)R also forwards one or more copies of the packet within the BIER 577 domain, the bit representing the BFR's own BFR-id will be cleared in 578 all the copies. 580 When BIER on a BFER passes a packet to the multicast flow overlay, it 581 may need to provide contextual information obtained from the BIER 582 encapsulation. The information that needs to pass between the BIER 583 layer and the multicast flow layer is specific to the multicast flow 584 layer. Specification of the interaction between the BIER layer and 585 the multicast flow layer is outside the scope of this specification. 587 When BIER on a BFER passes a packet to the multicast flow overlay, 588 the overlay will determine how to further dispatch the packet. If 589 the packet needs to be forwarded into another BIER domain, then the 590 BFR will act as a BFER in one BIER domain and as a BFIR in another. 591 A BIER-encapsulated packet cannot pass directly from one BIER domain 592 to another; at the boundary between BIER domains, the packet must be 593 decapsulated and passed to the multicast flow layer. 595 Note that when a BFR transmits multiple copies of a packet within a 596 BIER domain, only one copy will be destined to any given BFER. 597 Therefore it is not possible for any BIER-encapsulated packet to be 598 delivered more than once to any BFER. 600 6.2. BFR Neighbors 602 The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those 603 BFRs that, according to the routing underlay, are adjacencies of 604 BFR-A. Each BFR-NBR will have a BFR-prefix. 606 Suppose a BIER-encapsulated packet arrives at BFR-A. From the 607 packet's encapsulation, BFR-A learns the sub-domain of the packet, 608 and the BFR-ids (in that sub-domain) of the BFERs to which the packet 609 is destined. Then using the information advertised per Section 5, 610 BFR-A can find the BFR-prefix of each destination BFER. Given the 611 BFR-prefix of a particular destination BFER, say BFER-D, BFR-A learns 612 from the routing underlay (associated with the packet's sub-domain) 613 an IP address of the BFR that is the next hop on the path from BFR-A 614 to BFER-D. Let's call this next hop BFR-B. BFR-A must then 615 determine the BFR-prefix of BFR-B. (This determination can be made 616 from the information advertised per Section 5.) This BFR-prefix is 617 the BFR-NBR of BFR-A on the path from BFR-A to BFER-D. 619 Note that if the routing underlay provides multiple equal cost paths 620 from BFR-A to BFER-D, BFR-A may have multiple BFR-NBRs for BFER-D. 622 Under certain circumstances, a BFR may have adjacencies (in a 623 particular routing underlay) that are not BFRs. Please see 624 Section 6.9 for a discussion of how to handle those circumstances. 626 6.3. The Bit Index Routing Table 628 The Bit Index Routing Table (BIRT) is a table that maps from the 629 BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of 630 that BFER, and to the BFR-NBR on the path to that BFER. 632 ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D ) 633 4 (0:1000) \ \ 1 (0:0001) 634 \ \ 635 ( E ) ( F ) 636 3 (0:0100) 2 (0:0010) 638 Figure 1: BIER Topology 1 640 As an example, consider the topology shown in Figure 1. In this 641 diagram, we represent the BFR-id of each BFR in the SI:xyzw form 642 discussed in Section 3. This topology will result in the BIRT of 643 Figure 2 at BFR-B. The first column shows the BFR-id as a number and 644 also (in parentheses) in the SI:BitString format that corresponds to 645 a BitStringLength of 4. (The actual minimum BitStringLength is 64, 646 but we use 4 in the examples.) 648 Note that a BIRT is specific to a particular BIER sub-domain. 650 -------------------------------------------- 651 | BFR-id | BFR-Prefix | BFR-NBR | 652 | (SI:BitString) | of Dest BFER | | 653 ============================================ 654 | 4 (0:1000) | A | A | 655 -------------------------------------------- 656 | 1 (0:0001) | D | C | 657 -------------------------------------------- 658 | 3 (0:0100) | E | E | 659 -------------------------------------------- 660 | 2 (0:0010) | F | C | 661 -------------------------------------------- 663 Figure 2: Bit Index Routing Table at BFR-B 665 6.4. The Bit Index Forwarding Table 667 The "Bit Index Forwarding Table" (BIFT) is derived from the BIRT as 668 follows. (Note that a BIFT is specific to a particular sub-domain.) 670 Suppose that several rows in the BIRT have the same SI and the same 671 BFR-NBR. By taking the logical OR of the BitStrings of those rows, 672 we obtain a bit mask that corresponds to that combination of SI and 673 BFR-NBR. We will refer to this bit mask as the "Forwarding Bit Mask" 674 (F-BM) for that combination. 676 For example, in Figure 2, we see that two of the rows have the same 677 SI (0) and same BFR-NBR (C). The Bit Mask that corresponds to is 0011 ("0001" OR'd with "0010"). 680 The BIFT is used to map from the BFR-id of a BFER to the 681 corresponding F-BM and BFR-NBR. For example, Figure 3 shows the BIFT 682 that is derived from the BIRT of Figure 2. Note that BFR-ids 1 and 2 683 have the same SI and the same BFR-NBR, hence they have the same F-BM. 685 ------------------------------------- 686 | BFR-id | F-BM | BFR-NBR | 687 | (SI:Bitstring) | | | 688 ===================================== 689 | 1 (0:0001) | 0011 | C | 690 ------------------------------------- 691 | 2 (0:0010) | 0011 | C | 692 ------------------------------------- 693 | 3 (0:0100) | 0100 | E | 694 ------------------------------------- 695 | 4 (0:1000) | 1000 | A | 696 ------------------------------------- 698 Figure 3: Bit Index Forwarding Table 700 This Bit Index Forwarding Table (BIFT) is programmed into the data- 701 plane and used to forward packets, applying the rules specified below 702 in Section 6.5. 704 6.5. The BIER Forwarding Procedure 706 Below is the procedure for forwarding a BIER-encapsulated packet. 708 1. Determine the packet's SI. 710 2. Find the position of least significant (rightmost) bit in the 711 packet's BitString that is set. (Remember, bits are numbered 712 from 1, starting with the least significant bit.) Use that bit 713 position, together with the SI, as the 'index' into the BIFT. 715 3. Extract from the BIFT the F-BM and the BFR-NBR. 717 4. Copy the packet. Update the copy's BitString by AND'ing it with 718 the F-BM (i.e., PacketCopy->BitString &= F-BM). Then forward the 719 copy to the BFR-NBR. Note that when a packet is forwarded to a 720 particular BFR-NBR, its BitString identifies only those BFERs 721 that are to be reached via that BFR-NBR. 723 5. Now update the original packet's BitString by AND'ing it with the 724 INVERSE of the F-BM (i.e., Packet->Bitstring &= ~F-BM). (This 725 clears the bits that identify the BFERs to which a copy of the 726 packet has just been forwarded.) Go to step 2. 728 Note that this procedure causes the packet to be forwarded to a 729 particular BFR-NBR only once. The number of lookups in the BIFT is 730 the same as the number of BFR-NBRs to which the packet must be 731 forwarded; it is not necessary to do a separate lookup for each 732 destination BFER. 734 Suppose it has been decided (by the above rules) to send a packet to 735 a particular BFR-NBR. If that BFR-NBR is connected via multiple 736 parallel interfaces, it may be desirable to apply some form of load 737 balancing. Load balancing algorithms are outside the scope of this 738 document. However, if the packet's encapsulation contains an 739 "entropy" field, the entropy field SHOULD be respected; two packets 740 with the same value of the entropy field SHOULD be sent on the same 741 interface (if possible). 743 In some cases, the routing underlay may provide multiple equal cost 744 paths (through different BFR-NBRs) to a given BFER. This is known as 745 "Equal Cost Multiple Paths" (ECMP). The procedures described in this 746 section must be augmented in order to support load balancing over 747 ECMP. The necessary augmentations can be found in Section 6.7. 749 In the event that unicast traffic to the BFR-NBR is being sent via a 750 "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic 751 send to the BFR-NBR SHOULD also be sent via that tunnel. This allows 752 any existing "Fast Reroute" schemes to be applied to multicast 753 traffic as well as to unicast traffic. 755 Some examples of these forwarding procedures can be found in 756 Section 6.6. 758 The rules given in this section can be represented by the following 759 pseudocode: 761 void ForwardBitMaskPacket (Packet) 762 { 763 SI=GetPacketSI(Packet); 764 Offset=SI*BitStringLength; 765 for (Index = GetFirstBitPosition(Packet->BitString); Index ; 766 Index = GetNextBitPosition(Packet->BitString, Index)) { 767 F-BM = BIFT[Index+Offset]->F-BM; 768 if (!F-BM) continue; 769 BFR-NBR = BIFT[Index+Offset]->BFR-NBR; 770 PacketCopy = Copy(Packet); 771 PacketCopy->BitString &= F-BM; 772 PacketSend(PacketCopy, BFR-NBR); 773 Packet->BitString &= ~F-BM; 774 } 775 } 777 Figure 4: Pseudocode 779 Note that at a given BFER, the BFR-NBR entry corresponding to the 780 BFER's own BFR-id will be the BFER's own BFR-prefix. In this case, 781 the "PacketSend" function sends the packet to the multicast flow 782 layer. 784 6.6. Examples of BIER Forwarding 786 In this section, we give two examples of BIER forwarding, based on 787 the topology in Figure 1. In these examples, all packets have been 788 assigned to the default sub-domain, all packets have SI=0, and the 789 BitStringLength is 4. Figure 5 shows the BIFT entries for SI=0 only. 790 For compactness, we show the first column of the BIFT, the BFR-id, 791 only as an integer. 793 BFR-A BIFT BFR-B BIFT BFR-C BIFT 794 ------------------- ------------------- ------------------- 795 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | 796 =================== =================== =================== 797 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | 798 ------------------- ------------------- ------------------- 799 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | 800 ------------------- ------------------- ------------------- 801 | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B | 802 ------------------- ------------------- ------------------- 803 | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B | 804 ------------------- ------------------- ------------------- 806 Figure 5: BIFTs for Forwarding Examples 808 6.6.1. Example 1 810 BFR-D, BFR-E and BFR-F are BFER's. BFR-A is the BFIR. Suppose that 811 BFIR-A has learned from the multicast flow layer that BFER-D is 812 interested in a given multicast flow. If BFIR-A receives a packet of 813 that flow from outside the BIER domain, BFIR-A applies the BIER 814 encapsulation to the packet. The encapsulation must be such that the 815 SI is zero. The encapsulation also includes a BitString, with just 816 bit 1 set and with all other bits clear (i.e., 0001). This indicates 817 that BFER-D is the only BFER that needs to receive the packet. Then 818 BFIR-A follows the procedures of Section 6.5: 820 o Since the packet's BitString is 0001, BFIR-A finds that the first 821 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A 822 determines that the bit mask F-BM is 0111 and the BFR-NBR is 823 BFR-B. 825 o BFR-A then makes a copy of the packet, and applies F-BM to the 826 copy: Copy->BitString &= 0111. The copy's Bitstring is now 0001 827 (0001 & 0111). 829 o The copy is now sent to BFR-B. 831 o BFR-A then updates the packet's BitString by applying the inverse 832 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 833 packet's BitString is now 0000 (0001 & 1000). 835 o As the packet's BitString is now zero, the forwarding procedure is 836 complete. 838 When BFR-B receives the multicast packet from BFR-A, it follows the 839 same procedure. The result is that a copy of the packet, with a 840 BitString of 0001, is sent to BFR-C. BFR-C applies the same 841 procedures, and as a result sends a copy of the packet, with a 842 BitString of 0001, to BFR-D. 844 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an 845 F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy 846 of the packet to be delivered to the multicast flow layer at BFR-D. 847 The packet's BitString will be set to 0000, and the packet will not 848 be forwarded any further. 850 6.6.2. Example 2 852 This example is similar to Example 1, except that BFIR-A has learned 853 from the multicast flow layer that both BFER-D and BFER-E are 854 interested in a given multicast flow. If BFIR-A receives a packet of 855 that flow from outside the BIER domain, BFIR-A applies the BIER 856 encapsulation to the packet. The encapsulation must be such that the 857 SI is zero. The encapsulation also includes a BitString with two 858 bits set: bit 1 is set (as in example 1) to indicate that BFR-D is a 859 BFER for this packet, and bit 3 is set to indicate that BFR-E is a 860 BFER for this packet. I.e., the BitString (assuming again a 861 BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows 862 the procedures of Section 6.5: 864 o Since the packet's BitString is 0101, BFIR-A finds that the first 865 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A 866 determines that the bit mask F-BM is 0111 and the BFR-NBR is 867 BFR-B. 869 o BFR-A then makes a copy of the packet, and applies the F-BM to the 870 copy: Copy->BitString &= 0111. The copy's Bitstring is now 0101 871 (0101 & 0111). 873 o The copy is now sent to BFR-B. 875 o BFR-A then updates the packet's BitString by applying the inverse 876 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 877 packet's BitString is now 0000 (0101 & 1000). 879 o As the packet's BitString is now zero, the forwarding procedure is 880 complete. 882 When BFR-B receives the multicast packet from BFR-A, it follows the 883 procedure of Section 6.5, as follows: 885 o Since the packet's BitString is 0101, BFR-B finds that the first 886 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-B 887 determines that the bit mask F-BM is 0011 and the BFR-NBR is 888 BFR-C. 890 o BFR-B then makes a copy of the packet, and applies the F-BM to the 891 copy: Copy->BitString &= 0011. The copy's Bitstring is now 0001 892 (0101 & 0011). 894 o The copy is now sent to BFR-C. 896 o BFR-B then updates the packet's BitString by applying the inverse 897 of the F-BM: Packet->Bitstring &= F-BM. As a result, the 898 packet's BitString is now 0100 (0101 & 1100). 900 o Now BFR-B finds the next bit in the packet's (modified) BitString. 901 This is bit 3. Looking at entry 3 in its BIFT, BFR-B determines 902 that the F-BM is 0100 and the BFR-NBR is BFR-E. 904 o BFR-B then makes a copy of the packet, and applies the F-BM to the 905 copy: Copy->BitString &= 0100. The copy's Bitstring is now 0100 906 (0100 & 0100). 908 o The copy is now sent to BFR-E. 910 o BFR-B then updates the packet's BitString by applying the inverse 911 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 912 packet's BitString is now 0000 (0100 & 1011). 914 o As the packet's BitString is now zero, the forwarding procedure is 915 complete. 917 Thus BFR-B forwards two copies of the packet. One copy of the 918 packet, with BitString 0001, has now been sent from BFR-B to BFR-C. 919 Following the same procedures, BFR-C will forward the packet to 920 BFER-D. 922 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an 923 F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy 924 of the packet to be delivered to the multicast flow layer at BFR-D. 925 The packet's BitString will be set to 0000, and the packet will not 926 be forwarded any further. 928 The other copy of the packet has been sent from BFR-B to BFER-E, with 929 BitString 0100. 931 At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an 932 F-BM of 0000 and a BFR-NBR of BFR-E itself. This will cause a copy 933 of the packet to be delivered to the multicast flow layer at BFR-E. 934 The packet's BitString will be set to 0000, and the packet will not 935 be forwarded any further. 937 6.7. Equal Cost Multi-path Forwarding 939 In many networks, the routing underlay will provide multiple equal 940 cost paths from a given BFR to a given BFER. When forwarding 941 multicast packets through the network, it can be beneficial to take 942 advantage of this by load balancing among those paths. This feature 943 is known as "equal cost multiple path forwarding", or "ECMP". 945 BIER supports ECMP, but the procedures of Section 6.5 must be 946 modified slightly. Two ECMP procedures are defined. In the first 947 (described in Section 6.7.1), the choice among equal-cost paths taken 948 by a given packet from a given BFR to a given BFER depends on (a) the 949 packet's entropy, and (b) the other BFERs to which that packet is 950 destined. In the second (described in Section 6.7.2), the choice 951 depends only upon the packet's entropy. 953 There are tradeoffs between the two forwarding procedures described 954 here. In the procedure of Section 6.7.1, the number of packet 955 replications is minimized. The procedure in Section 6.7.1 also uses 956 less memory in the BFR. In the procedure of Section 6.7.2, the path 957 traveled by a given packet from a given BFR to a given BFER is 958 independent of the other BFERs to which the packet is destined. 959 While the procedures of Section 6.7.2 may cause more replications, 960 they provide a more predictable behavior. 962 The two procedures described here operate on identical packet formats 963 and will interoperate correctly. However, if deterministic behavior 964 is desired, then all BFRs would need to use the procedure from 965 Section 6.7.2. 967 6.7.1. Non-deterministic ECMP 969 Figure 6 shows the operation of non-deterministic ECMP in BIER. 971 BFR-A BIFT BFR-B BIFT BFR-C BIFT 972 ------------------- ------------------- ------------------- 973 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | 974 =================== =================== =================== 975 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | 976 ------------------- ------------------- ------------------- 977 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | 978 ------------------- | | 0110 | E | ------------------- 979 | 3 | 0111 | B | ------------------- | 3 | 1100 | B | 980 ------------------- | 3 | 0110 | E | ------------------- 981 | 4 | 1000 | A | ------------------| | 4 | 1100 | B | 982 ------------------- | 4 | 1000 | A | ------------------- 983 ------------------- 985 ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D ) 986 4 (0:1000) \ \ 1 (0:0001) 987 \ \ 988 ( E ) ------------ ( F ) 989 3 (0:0100) 2 (0:0010) 991 Figure 6: Example of ECMP 993 In this example, BFR-B has two equal cost paths to reach BFER-F, one 994 via BFR-C and one via BFR-E. Since the BFR-id of BFER-F is 2, this 995 is reflected in entry 2 of BFR-B's BIFT. Entry 2 shows that BFR-B 996 has a choice of two BFR-NBRs for BFER-B, and that a different F-BM is 997 associated with each choice. When BFR-B looks up entry 2 in the 998 BIFT, it can choose either BFR-NBR. However, when following the 999 procedures of Section 6.5, it MUST use the F-BM corresponding to the 1000 BFR-NBR that it chooses. 1002 How the choice is made is an implementation matter. However, the 1003 usual rules for ECMP apply: packets of a given flow SHOULD NOT be 1004 split among two paths, and any "entropy" field in the packet's 1005 encapsulation SHOULD be respected. 1007 Note however that by the rules of Section 6.5, any packet destined 1008 for both BFER-D and BFER-F will be sent via BFR-C. 1010 6.7.2. Deterministic ECMP 1012 With the procedures of Section 6.7.1, where ECMP paths exist, the 1013 path a packet takes to reach any particular BFER depends not only on 1014 routing and on the packet's entropy, but also on the set of other 1015 BFERs to which the packet is destined. 1017 For example consider the following scenario in the network of 1018 Figure 6. 1020 o There is a sequence of packets being transmitted by BFR-A, some of 1021 which are destined for both D and F, and some of which are 1022 destined only for F. 1024 o All the packets in this sequence have the same entropy value, call 1025 it "Q". 1027 o At BFR-B, when a packet with entropy value Q is forwarded via 1028 entry 2 in the BIFT, the packet is sent to E. 1030 Using the forwarding procedure of Section 6.7.1, packets of this 1031 sequence that are destined for both D and F are forwarded according 1032 to entry 1 in the BIFT, and thus will reach F via the path A-B-C-F. 1033 However, packets of this sequence that are destined only for F are 1034 forwarded according to entry 2 in the BIFT, and thus will reach F via 1035 the path A-B-E-F. 1037 That procedure minimizes the number of packets transmitted by BFR B. 1038 However, consider the following scenario: 1040 o Beginning at time t0, the multicast flow in question needs to be 1041 received ONLY by BFER-F; 1043 o Beginning at a later time, t1, the flow needs to be received by 1044 both BFER-D and BFER-F. 1046 o Beginning at a later time, t2, the no longer needs to be received 1047 by D, but still needs to be received by F. 1049 Then from t0 until t1, the flow will travel to F via the path 1050 A-B-E-F. From t1 until t2, the flow will travel to F via the path 1051 A-B-C-F. And from t2, the flow will again travel to F via the path 1052 A-B-E-F. 1054 The problem is that if D repeatedly joins and leaves the flow, the 1055 flow's path from B to F will keep switching. This could cause F to 1056 receive packets out of order. It also makes troubleshooting 1057 difficult. For example, if there is some problem on the E-F link, 1058 receivers at F will get good service when the flow is also going to D 1059 (avoiding the E-F link), but bad service when the flow is not going 1060 to D. Since it is hard to know which path is being used at any given 1061 time, this may be hard to troubleshoot. Also, it is very difficult 1062 to perform a traceroute that is known to follow the path taken by the 1063 flow at any given time. 1065 The source of this difficulty is that, in the procedures of 1066 Section 6.7.1, the path taken by a particular flow to a particular 1067 BFER depends upon whether there are lower numbered BFERs that are 1068 also receiving the flow. Thus the choice among the ECMP paths is 1069 fundamentally non-deterministic. 1071 Deterministic forwarding can be achieved by using multiple BIFTs, 1072 such that each row in a BIFT has only one path to each destination, 1073 but the multiple ECMP paths to any particular destination are spread 1074 across the multiple tables. When a BIER-encapsulated packet arrives 1075 to be forwarded, the BFR uses a hash of the BIER Entropy field to 1076 determine which BIFT to use, and then the normal BIER forwarding 1077 algorithm (as described in Sections 6.5 and 6.6) is used with the 1078 selected BIFT. 1080 As an example, suppose there are two paths to destination X (call 1081 them X1 and X2), and four paths to destination Y (call them Y1, Y2, 1082 Y3, and Y4). If there are, say, four BIFTs, one BIFT would have 1083 paths X1 and Y1, one would have X1 and Y2, one would have X2 and Y3, 1084 and one would have X2 and Y4. If traffic to X is split evenly among 1085 these four BIFTs, the traffic will be split evenly between the two 1086 paths to X; if traffic to Y is split evenly among these four BIFTs, 1087 the traffic will be split evenly between the four paths to Y. 1089 Note that if there are three paths to one destination and four paths 1090 to another, 12 BIFTs would be required in order to get even splitting 1091 of the load to each of those two destinations. Of course, each BIFT 1092 uses some memory, and one might be willing to have less optimal 1093 splitting in order to have fewer BIFTs. How that tradeoff is made is 1094 an implementation or deployment decision. 1096 6.8. Prevention of Loops and Duplicates 1098 The BitString in a BIER-encapsulated packet specifies the set of 1099 BFERs to which that packet is to be forwarded. When a BIER- 1100 encapsulated packet is replicated, no two copies of the packet will 1101 ever have a BFER in common. If one of the packet's BFERs forwards 1102 the packet further, that will first clear the bit that identifies 1103 itself. As a result, duplicate delivery of packets is not possible 1104 with BIER. 1106 As long as the routing underlay provides a loop free path between 1107 each pair of BFRs, BIER-encapsulated packets will not loop. Since 1108 the BIER layer does not create any paths of its own, there is no need 1109 for any BIER-specific loop prevention techniques beyond the 1110 forwarding procedures specified in Section 6.5. 1112 If, at some time, the routing underlay is not providing a loop free 1113 path between BFIR-A and BFER-B, then BIER encapsulated packets may 1114 loop while traveling from BFIR-A to BFER-B. However, such loops will 1115 never result in delivery of duplicate packets to BFER-B. 1117 These properties of BIER eliminate the need for the "reverse path 1118 forwarding" (RPF) check that is used in conventional IP multicast 1119 forwarding. 1121 6.9. When Some Nodes do not Support BIER 1123 The procedures of section Section 6.2 presuppose that, within a given 1124 BIER domain, all the nodes adjacent to a given BFR in a given routing 1125 underlay are also BFRs. However, it is possible to use BIER even 1126 when this is not the case, as long as the ingress and egress nodes 1127 are BFRs. In this section, we assume that the routing underlay is an 1128 SPF-based IGP that computes a shortest path tree from each node to 1129 all other nodes in the domain. 1131 At a given BFR, say BFR B, start with a copy of the IGP-computed 1132 shortest path tree from BFR B to each router in the domain. (This 1133 tree is computed by the SPF algorithm of the IGP.) Let's call this 1134 copy the "BIER-SPF tree rooted at BFR B." BFR B then modifies this 1135 BIER-SPF tree as follows. 1137 1. BFR B looks in turn at each of B's child nodes on the BIER-SPF 1138 tree. 1140 2. If one of the child nodes does not support BIER, BFR B removes 1141 that node from the tree. The child nodes of the node that has 1142 just been removed are then re-parented on the tree, so that BFR B 1143 now becomes their parent. 1145 3. BFR B then continues to look at each of its child nodes, 1146 including any nodes that have been re-parented to B as a result 1147 of the previous step. 1149 When all of the child nodes (the original child nodes plus any new 1150 ones) have been examined, B's children on the BIER-SPF tree will all 1151 be BFRs. 1153 When the BIFT is constructed, B's child nodes on the BIER-SPF tree 1154 are considered to be the BFR-NBRs. The F-BMs and outgoing BIER-MPLS 1155 labels must be computed appropriately, based on the BFR-NBRs. 1157 B may now have BFR-NBRs that are not "directly connected" to B via 1158 layer 2. To send a packet to one of these BFR-NBRs, B will have to 1159 send the packet through a unicast tunnel. This may be as simple as 1160 finding the IGP unicast next hop to the child node, and pushing on 1161 (above the BIER-MPLS label advertised by the child) the MPLS label 1162 that the IGP next hop has bound to an address of the child node. (If 1163 for some reason the unicast tunnel cannot be an MPLS tunnel, any 1164 other kind of tunnel can be used, as long as it is possible to 1165 encapsulate MPLS within that kind of tunnel.) 1167 Of course, the above is not meant as an implementation technique, 1168 just as a functional description. 1170 While the above description assumes that the routing underlay 1171 provides an SPF tree, it may also be applicable to other types of 1172 routing underlay. 1174 Note that the technique above can also be used to provide "node 1175 protection" (i.e., to provide fast reroute around nodes that are 1176 believed to have failed). If BFR B has a failed BFR-NBR, B can 1177 remove the failed BFR-NBR from the BIER-SPF tree, and can then re- 1178 parent the child BFR-NBRs of the failed BFR-NBR so that they appear 1179 to be B's own child nodes on the tree (i.e., so that they appear to 1180 be B's BFR-NBRs). Then the usual BIER forwarding procedures apply. 1181 However, getting the packet from B to the child nodes of the failed 1182 BFR-NBR is a bit more complicated, as it may require using a unicast 1183 bypass tunnel to get around the failed node. 1185 A simpler variant of step 2 above would be the following: 1187 If one of the child nodes does not support BIER, BFR B removes 1188 that node from the tree. All BFERs that are reached through that 1189 child node are then re-parented on the tree, so that BFR B now 1190 becomes their parent. 1192 This variant is simpler because the set of BFERs that are reached 1193 through a particular child node of B can be determined from the F-BM 1194 in the BIFT. However, if this variant is used, the results are less 1195 optimal, because packets will be unicast directly from B to the BFERs 1196 that are reachable through the non-BIER child node. 1198 When using a unicast MPLS tunnel to get a packet to a BFR-NBR, it may 1199 be advantageous to (a) set the TTL of the MPLS label entry 1200 representing the "tunnel" to a large value, rather than copying the 1201 TTL value from the BIER-MPLS label, and (b) when the tunnel labels 1202 are popped off, to avoid copying the TTL from the tunnel labels to 1203 the BIER-MPLS label. That way, the TTL of the BIER-MPLS label would 1204 only control the number of "BFR hops" that the packet may traverse. 1206 6.10. Use of Different BitStringLengths within a Domain 1208 When a BFIR imposes a BIER header on a particular packet, it uses the 1209 value of BitStringLength that it has been provisioned to use when 1210 imposing a BIER header. For the BIER forwarding procedures to work 1211 properly, this BitStringLength must be supported by the intermediate 1212 BFRs and by the BFERs that may receive that packet. 1214 Suppose one wants to migrate the BitStringLength used in a particular 1215 domain from one value (X) to another value (Y). The following 1216 migration procedure can be used. First, upgrade all the BFRs in the 1217 domain so that they support both value X and value Y. Once this is 1218 done, reprovision the BFIRs so that they use BitStringLength value Y. 1220 However, it is always possible that the following situation will 1221 occur. Suppose a packet has been BIER-encapsulated with a 1222 BitStringLength value of X, and that the packet has arrived at BFR-A. 1223 How suppose that according to the routing underlay, the next hop is 1224 BFR-B, but BFR-B does not support the BitStringLength value of X. 1225 What should BFR-A do with the packet? BFR-A has three choices. It 1226 MUST be able to do one of the three, but the choice of which 1227 procedure to follow is a local matter. The three choices are: 1229 o BFR-A MAY discard the packet. 1231 o BFR-A MAY re-encapsulate the packet, using a BIER header whose 1232 BitStringLength value is supported by BFR-B. (Note that if BFR-B 1233 only supports BitStringLength values that are smaller than the 1234 BitStringLength value of the packet, this may require creating an 1235 additional copy of the packet.) 1237 o BFR-A MAY treat BFR-B as if BFR-B did not support BIER at all, and 1238 apply the rules of Section 6.9. 1240 7. IANA Considerations 1242 This document contains no actions for IANA. 1244 8. Security Considerations 1246 When BIER is paired with a particular multicast flow layer, it 1247 inherits the security considerations of that layer. Similarly, when 1248 BIER is paired with a particular routing underlay, it inherits the 1249 security considerations of that layer. 1251 If the BIER encapsulation of a particular packet specifies an SI or a 1252 BitString other than the one intended by the BFIR, the packet is 1253 likely to be misdelivered. If the BIER encapsulation of a packet is 1254 modified (through error or malfeasance) in a way other than that 1255 specified in this document, the packet may be misdelivered. 1257 If the procedures used for advertising BFR-ids and BFR-prefixes are 1258 not secure, an attack on those procedures may result in incorrect 1259 delivery of BIER-encapsulated packets. 1261 Every BFR must be provisioned to know which of its interfaces lead to 1262 a BIER domain and which do not. If two interfaces lead to different 1263 BIER domains, the BFR must be provisioned to know that those two 1264 interfaces lead to different BIER domains. If the provisioning is 1265 not correct, BIER-encapsulated packets from one BIER domain may 1266 "leak" into another; this is likely to result in misdelivery of 1267 packets. 1269 9. Acknowledgements 1271 The authors wish to thank Rajiv Asati, John Bettink, Ross Callon (who 1272 contributed much of the text on deterministic ECMP), Nagendra Kumar, 1273 Christian Martin, Neale Ranns, Greg Shepherd, Albert Tian, Ramji 1274 Vaithianathan, Xiaohu Xu and Jeffrey Zhang for their ideas and 1275 contributions to this work. 1277 10. Contributor Addresses 1279 Below is a list of other contributing authors in alphabetical order: 1281 Gregory Cauchie 1282 Bouygues Telecom 1284 Email: gcauchie@bouyguestelecom.fr 1286 Mach (Guoyi) Chen 1287 Huawei 1288 Email: mach.chen@huawei.com 1290 Arkadiy Gulko 1291 Thomson Reuters 1292 195 Broadway 1293 New York NY 10007 1294 US 1296 Email: arkadiy.gulko@thomsonreuters.com 1298 Wim Henderickx 1299 Alcatel-Lucent 1300 Copernicuslaan 50 1301 Antwerp 2018 1302 BE 1304 Email: wim.henderickx@alcatel-lucent.com 1306 Martin Horneffer 1307 Deutsche Telekom 1308 Hammer Str. 216-226 1309 Muenster 48153 1310 DE 1312 Email: Martin.Horneffer@telekom.de 1314 Uwe Joorde 1315 Deutsche Telekom 1316 Hammer Str. 216-226 1317 Muenster D-48153 1318 DE 1320 Email: Uwe.Joorde@telekom.de 1322 Luay Jalil 1323 Verizon 1324 1201 E Arapaho Rd. 1325 Richardson, TX 75081 1326 US 1328 Email: luay.jalil@verizon.com 1330 Jeff Tantsura 1331 Ericsson 1332 300 Holger Way 1333 San Jose, CA 95134 1334 US 1336 Email: jeff.tantsura@ericsson.com 1338 11. References 1340 11.1. Normative References 1342 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1343 Requirement Levels", BCP 14, RFC 2119, March 1997. 1345 11.2. Informative References 1347 [Boivie_Feldman] 1348 Boivie, R. and N. Feldman, "Small Group Multicast", 1349 (expired) draft-boivie-sgm-02.txt, February 2001. 1351 [ISIS_BIER_EXTENSIONS] 1352 Przygienda, T., Ginsberg, L., Aldrin, S., and J. Zhang, 1353 "OSPF Extensions for Bit Index Explicit Replication", 1354 internet-draft draft-przygienda-bier-isis-ranges-01.txt, 1355 October 2014. 1357 [MPLS_BIER_ENCAPS] 1358 Wijnands, IJ., "BIER Encapsulation for MPLS Networks", 1359 internet-draft draft-wijnands-mpls-bier-encaps-02.txt, 1360 December 2014. 1362 [OSPF_BIER_EXTENSIONS] 1363 Psenak, P., Kumar, N., Wijnands, IJ., Dolganow, A., 1364 Przygienda, T., and J. Zhang, "OSPF Extensions for Bit 1365 Index Explicit Replication", internet-draft draft-psenak- 1366 ospf-bier-extensions-01.txt, October 2014. 1368 [RFC6513] Rosen, E. and R. Aggarwal, "Multicast in MPLS/BGP IP 1369 VPNs", RFC 6513, February 2012. 1371 [RFC6514] Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP 1372 Encodings and Procedures for Multicast in MPLS/BGP IP 1373 VPNs", RFC 6514, February 2012. 1375 Authors' Addresses 1376 IJsbrand Wijnands (editor) 1377 Cisco Systems, Inc. 1378 De Kleetlaan 6a 1379 Diegem 1831 1380 BE 1382 Email: ice@cisco.com 1384 Eric C. Rosen (editor) 1385 Juniper Networks, Inc. 1386 10 Technology Park Drive 1387 Westford, Massachusetts 01886 1388 US 1390 Email: erosen@juniper.net 1392 Andrew Dolganow 1393 Alcatel-Lucent 1394 600 March Rd. 1395 Ottawa, Ontario K2K 2E6 1396 CA 1398 Email: andrew.dolganow@alcatel-lucent.com 1400 Tony Przygienda 1401 Ericsson 1402 300 Holger Way 1403 San Jose, California 95134 1404 US 1406 Email: antoni.przygienda@ericsson.com 1408 Sam K Aldrin 1409 Huawei Technologies 1410 2330 Central Express Way 1411 Santa Clara, California 1412 US 1414 Email: aldrin.ietf@gmail.com