idnits 2.17.1 draft-wijnands-bier-architecture-00.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 (September 22, 2014) is 3475 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 231 -- Looks like a reference, but probably isn't: '65535' on line 217 -- Looks like a reference, but probably isn't: '256' on line 229 -- Looks like a reference, but probably isn't: '512' on line 231 -- Looks like a reference, but probably isn't: '0' on line 265 -- Looks like a reference, but probably isn't: '15' on line 264 -- Looks like a reference, but probably isn't: '255' on line 265 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 E. Rosen, Ed. 4 Intended status: Standards Track Cisco Systems, Inc. 5 Expires: March 26, 2015 A. Dolganow 6 Alcatel-Lucent 7 T. Przygienda 8 Ericsson 9 September 22, 2014 11 Multicast using Bit Index Explicit Replication 12 draft-wijnands-bier-architecture-00 14 Abstract 16 This document specifies a new architecture for the forwarding of 17 multicast data packets. It provides optimal forwarding of multicast 18 packets through a "multicast domain". However, it does not require 19 any explicit tree-building protocol, nor does it require intermediate 20 nodes to maintain any per-flow state. This architecture is known as 21 "Bit Index Explicit Replication" (BIER). When a multicast data 22 packet enters the domain, the ingress router determines the set of 23 egress routers to which the packet needs to be sent. The ingress 24 router then encapsulates the packet in a BIER header. The BIER 25 header contains a bitstring in which each bit represents exactly one 26 egress router in the domain; to forward the packet to a given set of 27 egress routers, the bits corresponding to those routers are set in 28 the BIER header. Elimination of the per-flow state and the explicit 29 tree-building protocols results in a considerable simplification. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on March 26, 2015. 48 Copyright Notice 50 Copyright (c) 2014 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 2. The BFR Identifier and BFR-Prefix . . . . . . . . . . . . . . 5 67 3. Encoding BFR Identifiers in BitStrings . . . . . . . . . . . 6 68 4. Layering . . . . . . . . . . . . . . . . . . . . . . . . . . 7 69 4.1. The Routing Underlay . . . . . . . . . . . . . . . . . . 7 70 4.2. The BIER Layer . . . . . . . . . . . . . . . . . . . . . 8 71 4.3. The Multicast Flow Overlay . . . . . . . . . . . . . . . 9 72 5. Advertising BFR-ids and BFR-Prefixes . . . . . . . . . . . . 9 73 6. BIER Intra-Domain Forwarding Procedures . . . . . . . . . . . 10 74 6.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 10 75 6.2. BFR Neighbors . . . . . . . . . . . . . . . . . . . . . . 11 76 6.3. The Bit Index Routing Table . . . . . . . . . . . . . . . 12 77 6.4. The Bit Index Forwarding Table . . . . . . . . . . . . . 13 78 6.5. The BIER Forwarding Procedure . . . . . . . . . . . . . . 14 79 6.6. Examples of BIER Forwarding . . . . . . . . . . . . . . . 16 80 6.6.1. Example 1 . . . . . . . . . . . . . . . . . . . . . . 16 81 6.6.2. Example 2 . . . . . . . . . . . . . . . . . . . . . . 17 82 6.7. Equal Cost Multi-path Forwarding . . . . . . . . . . . . 19 83 6.8. Prevention of Loops and Duplicates . . . . . . . . . . . 20 84 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 85 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 86 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21 87 10. Contributor Addresses . . . . . . . . . . . . . . . . . . . . 21 88 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 89 11.1. Normative References . . . . . . . . . . . . . . . . . . 22 90 11.2. Informative References . . . . . . . . . . . . . . . . . 22 91 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 93 1. Introduction 95 This document specifies a new architecture for the forwarding of 96 multicast data packets. It provides optimal forwarding of multicast 97 data packets through a "multicast domain". However, it does not 98 require any explicit tree-building protocol, and does not require 99 intermediate nodes to maintain any per-flow state. This architecture 100 is known as "Bit Index Explicit Replication" (BIER). 102 A router that supports BIER is known as a "Bit-Forwarding Router" 103 (BFR). A BIER domain is a connected set of BFRs, where each BFR has 104 a "BFR-id" that is unique within the domain. A BFR-id is a small 105 unstructured number. For instance, if a particular BIER domain 106 contains 1,374 BFRs, each one could be given a BFR-id in the range 107 1-1374. 109 A multicast data packet enters a BIER domain at a "Bit-Forwarding 110 Ingress Router" (BFIR), and leaves the BIER domain at one or more 111 "Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a 112 multicast data packet from another BFR in the same BIER domain, and 113 forwards the packet to another BFR in the same BIER domain, will be 114 known as a "transit BFR" for that packet. A single BFR may be a BFIR 115 for some multicast traffic while also being a BFER for some multicast 116 traffic and a transit BFR for some multicast traffic. In fact, a BFR 117 may be the BFIR for a given packet and may also be (one of) the 118 BFER(s), for that packet; it may also forward that packet to one or 119 more additional BFRs. 121 When a multicast packet arrives from outside the domain at a BFIR, 122 the BFIR determines the set of BFERs to which the packet must be 123 sent. It then encapsulates the packet in a "BIER header". The BIER 124 header contains a bit string in which each bit represents a single 125 BFR-id. To indicate that a particular BFER needs to receive a given 126 packet, the BFIR sets the bit corresponding to that BFER's BFR-id. 127 We will use term "BitString" to refer to the bit string field in the 128 BIER header. We will use the term "payload" to refer to the packet 129 that has been encapsulated. Thus a "BIER-encapsulated" packet 130 consists of a "BIER header" followed by a "payload". 132 The number of BFERs to which a given packet can be forwarded is 133 limited only by the length of the BitString in the BIER header. 134 Different deployments can use different BitString lengths. We will 135 use the term "BitStringLength" to refer to the number of bits in the 136 BitString. It is possible that some deployment will have more BFERs 137 in a given domain than there are bits in the BitString. To 138 accommodate this case, the BIER encapsulation includes both the 139 BitString and a "Set Identifier" (SI). It is the BitString and the 140 SI together that determine the set of BFERs to which a given packet 141 will be delivered: 143 o by convention, the least significant (rightmost) bit in the 144 BitString is "bit 1", and the most significant (leftmost) bit is 145 "bit BitStringLength". 147 o if a BIER-encapsulated packet has an SI of n, and a BitString with 148 bit k set, then the packet must be delivered to the BFER whose 149 BFR-id is n*BitStringLength+k. 151 For example, suppose the BIER encapsulation uses a BitStringLength of 152 256 bits. By convention, the least significant (rightmost) bit is 153 "bit 1", and the most significant (leftmost) bit is "bit 256". 154 Suppose that a given packet needs to be delivered to three BFERs, 155 where those BFERs have BFR-ids of 13, 126, and 235 respectively. The 156 BFIR would create a BIER encapsulation with the SI set to zero, and 157 with bits 13, 126, and 235 of the BitString set. (All other bits of 158 the BitString would be clear.) If the packet also needs to be sent 159 to a BFER whose BFR-id is 257, the BFIR would have to create a second 160 copy of the packet, and the BIER encapsulation would specify an SI of 161 1, and a BitString with bit 1 set and all the other bits clear. 163 Note that it is generally advantageous to assign the BFR-ids so that 164 as many BFERs as possible can be represented in a single bit string. 166 Suppose a BFR, call it BFR-A, receives a packet whose BIER 167 encapsulation specifies an SI of 0, and a BitString with bits 13, 26, 168 and 235 set. Suppose BFR-A has two BFR neighbors, BFR-B and BFR-C, 169 such that the best path to BFERs 13 and 26 is via BFR-B, but the best 170 path to BFER 235 is via BFR-C. Then BFR-A will replicate the packet, 171 sending one copy to BFR-B and one copy to BFR-C. However, BFR-A will 172 clear bit 235 in the BitString of the packet copy it sends to BFR-B, 173 and will clear bits 13 and 26 in the BitString of the packet copy it 174 sends to BFR-C. As a result, BFR-B will forward the packet only 175 towards BFERs 13 and 26, and BFR-C will forward the packet only 176 towards BFER 235. This ensures that each BFER receives only one copy 177 of the packet. 179 With this forwarding procedure, a multicast data packet can follow an 180 optimal path from its BFIR to each of its BFERs. Further, since the 181 set of BFERs for a given packet is explicitly encoded into the BIER 182 header, the packet is not sent to any BFER that does not need to 183 receive it. This allows for optimal forwarding of multicast traffic. 184 This optimal forwarding is achieved without any need for transit BFRs 185 to maintain per-flow state, or to run a multicast tree-building 186 protocol. 188 The idea of encoding the set of egress nodes into the header of a 189 multicast packet is not new. For example, [Boivie_Feldman] proposes 190 to encode the set of egress nodes as a set of IP addresses, and 191 proposes mechanisms and procedures that are in some ways similar to 192 those described in the current document. However, since BIER encodes 193 each BFR-id as a single bit in a bit string, it can represent up to 194 128 BFERs in the same number of bits that it would take to carry the 195 IPv6 address of a single BFER. Thus BIER scales to a much larger 196 number of egress nodes per packet. 198 BIER does not require that each transit BFR look up the best path to 199 each BFER that is identified in the BIER header; the number of 200 lookups required in the forwarding path for a single packet can be 201 limited to the number of neighboring BFRs; this can be much smaller 202 than the number of BFERs. See Section 6 (especially Section 6.4) for 203 details. 205 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 206 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 207 document are to be interpreted as described in RFC 2119 [RFC2119]. 209 2. The BFR Identifier and BFR-Prefix 211 Each BFR MUST be assigned a "BFR-Prefix". A BFR's BFR-Prefix MUST be 212 an IP address (either IPv4 or IPv6) of the BFR, and MUST be routable 213 within the domain. It is RECOMMENDED that the BFR-prefix be a 214 loopback address of the BFR. Two BFRs in the same BIER domain MUST 215 NOT be assigned the same BFR-Prefix. 217 A "BFR Identifier" (BFR-id) is a number in the range [1,65535]. In 218 general, each BFR in a given BIER domain must be assigned a unique 219 number from this range (i.e., two BFRs in the same BIER domain MUST 220 NOT have the same BFR-id). However, if it is known that a given BFR 221 will never need to function as a BFER, then it is not necessary to 222 assign a BFR-id to that BFR. 224 The procedure for assigning a particular BFR-id to a particular BFR 225 is outside the scope of this document. However, it is RECOMMENDED 226 that the BFR-ids be assigned "densely" from the numbering space, as 227 this will result in a more efficient encoding (see Section 3). That 228 is, if there are 256 or fewer BFERs, it is RECOMMENDED to assign all 229 the BFR-ids from the range [1,256]. If there are more than 256 230 BFERs, but less than 512, it is RECOMMENDED to assign all the BFR-ids 231 from the range [1,512], with as few "holes" as possible in the 232 earlier range. However, in some deployments, it may be advantageous 233 to depart from this recommendation; this is discussed further in 234 Section 3. 236 3. Encoding BFR Identifiers in BitStrings 238 To encode a BFR-id in a BIER data packet, one must convert the BFR-id 239 to an SI and a BitString. This conversion depends upon the parameter 240 we are calling "BitStringLength". The conversion is done as follows. 241 If the BFR-id is N, then 243 o SI is the integer part of the quotient (N-1)/BitStringLength 245 o The BitString has one bit position set. If the low-order bit is 246 bit 1, and the high-order bit is bit BitStringLength, the bit 247 position that represents BFR-id N is 248 ((N-1) modulo BitStringLength)+1. 250 If several different BFR-ids all resolve to the same SI, then all 251 those BFR-ids can be represented in a single BitString. The 252 BitStrings for all of those BFR-ids are combined using a bitwise 253 logical OR operation. 255 Different BIER domains may use different values of BitStringLength. 256 Within a BIER domain, all BFRs MUST use the same BitStringLength 257 value; this value is known by provisioning. A BFR MUST support a 258 BitStringLength value of 256. Particular encapsulation types MAY 259 allow other BitStringLengths to be optionally supported. For 260 example, when using the encapsulation specified in 261 [MPLS_BIER_ENCAPS], a BFR may support any or all of the following 262 BitStringLengths: 64, 128, 256, 512, 1024, 2048, and 4096. 264 A BFR MUST support SI values in the range [0,15], and MAY support SI 265 values in the range [0,255]. 267 It is possible to design procedures that allow BFRs within a given 268 BIER domain to use different BitStringLength values, and to enable 269 each BFR to discover the BitStringLength values used by all the other 270 BFRs in the domain. However, this document presupposes that they all 271 use the same value; procedures for the use of different values may be 272 specified in future documents. 274 When a BFIR determines that a multicast data packet needs to be 275 forwarded to a particular set of destination BFERs, it partitions 276 that set of BFERs into subsets, where each subset contains the target 277 BFERs whose BFR-ids all resolve to the same SI. Call these the 278 "SI-subsets" for the packet. Each SI-subset can be represented by a 279 single BitString. The BFIR creates a copy of the packet for each 280 SI-subset. The BIER encapsulation is then applied to each packet. 281 The encapsulation specifies a single SI for each packet, and contains 282 the BitString that represents all the BFR-ids in the corresponding 283 SI-subset. 285 Suppose, for example, that a BFIR determines that a given packet 286 needs to be forwarded to three BFERs, whose BFR-ids are 27, 235, and 287 497. The BFIR will have to forward two copies of the packet. One 288 copy, associated with SI=0, will have a BitString with bits 27 and 289 235 set. The other copy, associated with SI=1, will have a BitString 290 with bit 241 set. 292 In order to minimize the number of copies that must be made of a 293 given multicast packet, it is RECOMMENDED that the BFR-ids be 294 assigned "densely" (see Section 2) from the numbering space. This 295 will minimize the number of SIs that have to be used in the domain. 296 However, depending upon the details of a particular deployment, other 297 assignment methods may be more advantageous. Suppose, for example, 298 that in a certain deployment, every multicast flow is either intended 299 for the "east coast" or for the "west coast". In such a deployment, 300 it would be advantageous to assign BFR-ids so that all the "west 301 coast" BFR-ids fall into the same SI-subset, and so that all the 302 "east coast" BFR-ids fall into the same SI-subset. 304 When a BFR receives a BIER data packet, it will infer the SI from the 305 encapsulation. Then the set of BFERs to which the packet needs to be 306 forwarded can then be inferred from the SI and the BitString. 308 In some of the examples given later in this document, we will use a 309 BitStringLength of 4, and will represent a BFR-id in the form 310 "SI:xyzw", where SI is the Set Identifier of the BFR-id (assuming a 311 BitStringLength of 4), and xyzw is a string of 4 bits. A 312 BitStringLength of 4 is used only in the examples; we would not 313 expect actual deployments to have such a small BitStringLength. 315 It is expected that there will be several different forms of BIER 316 encapsulation. The particular encapsulation that is used in a given 317 deployment will depend on the type of network infrastructure that is 318 used to realize the BIER domain. Details of the BIER encapsulation 319 will be given in companion documents. An encapsulation for use in 320 MPLS networks is described in [MPLS_BIER_ENCAPS] 322 4. Layering 324 It is helpful to think of the BIER architecture as consisting of 325 three layers: the "routing underlay", the "BIER layer", and the 326 "multicast flow overlay". 328 4.1. The Routing Underlay 330 The "routing underlay" establishes "adjacencies" between pairs of 331 BFRs, and determines one or more "best paths" from a given BFR to a 332 given set of BFRs. Each such path is a sequence of BFRs such that BFR(k+j) is "adjacent" to 334 BFR(k+j+1) (for 0<=j combination. 585 For example, in Figure 2, we see that two of the rows have the same 586 SI (0) and same BFR-NBR (C). The Bit Mask that corresponds to is 0011 ("0001" OR'd with "0010"). 589 The BIFT is used to map from the BFR-id of a BFER to the 590 corresponding F-BM and BFR-NBR. For example, Figure 3 shows the BIFT 591 that is derived from the BIRT of Figure 2. Note that BFR-ids 1 and 2 592 have the same SI and the same BFR-NBR, hence they have the same F-BM. 594 ------------------------------------- 595 | BFR-id | F-BM | BFR-NBR | 596 | (SI:Bitstring) | | | 597 ===================================== 598 | 1 (0:0001) | 0011 | C | 599 ------------------------------------- 600 | 2 (0:0010) | 0011 | C | 601 ------------------------------------- 602 | 3 (0:0100) | 0100 | E | 603 ------------------------------------- 604 | 4 (0:1000) | 1000 | A | 605 ------------------------------------- 607 Figure 3: Bit Index Forwarding Table 609 This Bit Index Forwarding Table (BIFT) is programmed into the data- 610 plane and used to forward packets, applying the rules specified below 611 in Section 6.5. 613 6.5. The BIER Forwarding Procedure 615 Below is the procedure for forwarding a BIER-encapsulated packet. 617 1. Determine the packet's SI. 619 2. Find the position of least significant (rightmost) bit in the 620 packet's BitString that is set. (Remember, bits are numbered 621 from 1, starting with the least significant bit.) Use that bit 622 position, together with the SI, as the 'index' into the BIFT. 624 3. Extract from the BIFT the F-BM and the BFR-NBR. 626 4. Copy the packet. Update the copy's BitString by AND'ing it with 627 the F-BM (i.e., PacketCopy->BitString &= F-BM). Then forward the 628 copy to the BFR-NBR. Note that when a packet is forwarded to a 629 particular BFR-NBR, its BitString identifies only those BFERs 630 that are to be reached via that BFR-NBR. 632 5. Now update the original packet's BitString by AND'ing it with the 633 INVERSE of the F-BM (i.e., Packet->Bitstring &= ~F-BM). (This 634 clears the bits that identify the BFERs to which a copy of the 635 packet has just been forwarded.) Go to step 2. 637 Note that this procedure causes the packet to be forwarded to a 638 particular BFR-NBR only once. The number of lookups in the BIFT is 639 the same as the number of BFR-NBRs to which the packet must be 640 forwarded; it is not necessary to do a separate lookup for each 641 destination BFER. 643 Suppose it has been decided (by the above rules) to send a packet to 644 a particular BFR-NBR. If that BFR-NBR is connected via multiple 645 parallel interfaces, it may be desirable to apply some form of load 646 balancing. Load balancing algorithms are outside the scope of this 647 document. However, if the packet's encapsulation contains an 648 "entropy" field, the entropy field SHOULD be respected; two packets 649 with the same value of the entropy field SHOULD be sent on the same 650 interface (if possible). 652 In some cases, the routing underlay may provide multiple equal cost 653 paths (through different BFR-NBRs) to a given BFER. This is known as 654 "Equal Cost Multiple Paths" (ECMP). The procedures described in this 655 section must be augmented in order to support load balancing over 656 ECMP. The necessary augmentations can be found in Section 6.7. 658 In the event that unicast traffic to the BFR-NBR is being sent via a 659 "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic 660 send to the BFR-NBR SHOULD also be sent via that tunnel. This allows 661 any existing "Fast Reroute" schemes to be applied to multicast 662 traffic as well as to unicast traffic. 664 Some examples of these forwarding procedures can be found in 665 Section 6.6. 667 The rules given in this section can be represented by the following 668 pseudocode: 670 void ForwardBitMaskPacket (Packet) 671 { 672 SI=GetPacketSI(Packet); 673 Offset=SI*BitStringLength; 674 for (Index = GetFirstBitPosition(Packet->BitString); Index ; 675 Index = GetNextBitPosition(Packet->BitString, Index)) { 676 F-BM = BIFT[Index+Offset]->F-BM; 677 if (!F-BM) continue; 678 BFR-NBR = BIFT[Index+Offset]->BFR-NBR; 679 PacketCopy = Copy(Packet); 680 PacketCopy->BitString &= F-BM; 681 PacketSend(PacketCopy, BFR-NBR); 682 Packet->BitString &= ~F-BM; 683 } 684 } 686 Figure 4: Pseudocode 688 Note that at a given BFER, the BFR-NBR entry corresponding to the 689 BFER's own BFR-id will be the BFER's own BFR-prefix. In this case, 690 the "PacketSend" function sends the packet to the multicast flow 691 layer. 693 6.6. Examples of BIER Forwarding 695 In this section, we give two examples of BIER forwarding, based on 696 the topology in Figure 1. In these examples, all packets have SI=0, 697 and the BitStringLength is 4. Figure 5 shows the BIFT entries for 698 SI=0 only. For compactness, we show the first column of the BIFT, 699 the BFR-id, only as an integer. 701 BFR-A BIFT BFR-B BIFT BFR-C BIFT 702 ------------------- ------------------- ------------------- 703 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | 704 =================== =================== =================== 705 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | 706 ------------------- ------------------- ------------------- 707 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | 708 ------------------- ------------------- ------------------- 709 | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B | 710 ------------------- ------------------- ------------------- 711 | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B | 712 ------------------- ------------------- ------------------- 714 Figure 5: BIFTs for Forwarding Examples 716 6.6.1. Example 1 718 BFR-D, BFR-E and BFR-F are BFER's. BFR-A is the BFIR. Suppose that 719 BFIR-A has learned from the multicast flow layer that BFER-D is 720 interested in a given multicast flow. If BFIR-A receives a packet of 721 that flow from outside the BIER domain, BFIR-A applies the BIER 722 encapsulation to the packet. The encapsulation must be such that the 723 SI is zero. The encapsulation also includes a BitString, with just 724 bit 1 set and with all other bits clear (i.e., 0001). This indicates 725 that BFER-D is the only BFER that needs to receive the packet. Then 726 BFIR-A follows the procedures of Section 6.5: 728 o Since the packet's BitString is 0001, BFIR-A finds that the first 729 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A 730 determines that the bit mask F-BM is 0111 and the BFR-NBR is 731 BFR-B. 733 o BFR-A then makes a copy of the packet, and applies F-BM to the 734 copy: Copy->BitString &= 0111. The copy's Bitstring is now 0001 735 (0001 & 0111). 737 o The copy is now sent to BFR-B. 739 o BFR-A then updates the packet's BitString by applying the inverse 740 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 741 packet's BitString is now 0000 (0001 & 1000). 743 o As the packet's BitString is now zero, the forwarding procedure is 744 complete. 746 When BFR-B receives the multicast packet from BFR-A, it follows the 747 same procedure. The result is that a copy of the packet, with a 748 BitString of 0001, is sent to BFR-C. BFR-C applies the same 749 procedures, and as a result sends a copy of the packet, with a 750 BitString of 0001, to BFR-D. 752 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an 753 F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy 754 of the packet to be delivered to the multicast flow layer at BFR-D. 755 The packet's BitString will be set to 0000, and the packet will not 756 be forwarded any further. 758 6.6.2. Example 2 760 This example is similar to Example 1, except that BFIR-A has learned 761 from the multicast flow layer that both BFER-D and BFER-E are 762 interested in a given multicast flow. If BFIR-A receives a packet of 763 that flow from outside the BIER domain, BFIR-A applies the BIER 764 encapsulation to the packet. The encapsulation must be such that the 765 SI is zero. The encapsulation also includes a BitString with two 766 bits set: bit 1 is set (as in example 1) to indicate that BFR-D is a 767 BFER for this packet, and bit 3 is set to indicate that BFR-E is a 768 BFER for this packet. I.e., the BitString (assuming again a 769 BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows 770 the procedures of Section 6.5: 772 o Since the packet's BitString is 0101, BFIR-A finds that the first 773 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A 774 determines that the bit mask F-BM is 0111 and the BFR-NBR is 775 BFR-B. 777 o BFR-A then makes a copy of the packet, and applies the F-BM to the 778 copy: Copy->BitString &= 0111. The copy's Bitstring is now 0101 779 (0101 & 0111). 781 o The copy is now sent to BFR-B. 783 o BFR-A then updates the packet's BitString by applying the inverse 784 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 785 packet's BitString is now 0000 (0101 & 1000). 787 o As the packet's BitString is now zero, the forwarding procedure is 788 complete. 790 When BFR-B receives the multicast packet from BFR-A, it follows the 791 procedure of Section 6.5, as follows: 793 o Since the packet's BitString is 0101, BFR-B finds that the first 794 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-B 795 determines that the bit mask F-BM is 0011 and the BFR-NBR is 796 BFR-C. 798 o BFR-B then makes a copy of the packet, and applies the F-BM to the 799 copy: Copy->BitString &= 0011. The copy's Bitstring is now 0001 800 (0101 & 0011). 802 o The copy is now sent to BFR-C. 804 o BFR-B then updates the packet's BitString by applying the inverse 805 of the F-BM: Packet->Bitstring &= F-BM. As a result, the 806 packet's BitString is now 0100 (0101 & 1100). 808 o Now BFR-B finds the next bit in the packet's (modified) BitString. 809 This is bit 3. Looking at entry 3 in its BIFT, BFR-B determines 810 that the F-BM is 0100 and the BFR-NBR is BFR-E. 812 o BFR-B then makes a copy of the packet, and applies the F-BM to the 813 copy: Copy->BitString &= 0100. The copy's Bitstring is now 0100 814 (0100 & 0100). 816 o The copy is now sent to BFR-E. 818 o BFR-B then updates the packet's BitString by applying the inverse 819 of the F-BM: Packet->Bitstring &= ~F-BM. As a result, the 820 packet's BitString is now 0000 (0100 & 1011). 822 o As the packet's BitString is now zero, the forwarding procedure is 823 complete. 825 Thus BFR-B forwards two copies of the packet. One copy of the 826 packet, with BitString 0001, has now been sent from BFR-B to BFR-C. 827 Following the same procedures, BFR-C will forward the packet to 828 BFER-D. 830 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an 831 F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy 832 of the packet to be delivered to the multicast flow layer at BFR-D. 833 The packet's BitString will be set to 0000, and the packet will not 834 be forwarded any further. 836 The other copy of the packet has been sent from BFR-B to BFER-E, with 837 BitString 0100. 839 At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an 840 F-BM of 0000 and a BFR-NBR of BFR-E itself. This will cause a copy 841 of the packet to be delivered to the multicast flow layer at BFR-E. 842 The packet's BitString will be set to 0000, and the packet will not 843 be forwarded any further. 845 6.7. Equal Cost Multi-path Forwarding 847 In many networks, the routing underlay will provide multiple equal 848 cost paths from a given BFR to a given BFER. When forwarding 849 multicast packets through the network, it can be beneficial to take 850 advantage of this by load balancing among those paths. This feature 851 is known as "equal cost multiple path forwarding", or "ECMP". 853 BIER supports ECMP, but the procedures of Section 6.5 must be 854 modified slightly. This is shown in Figure 6, which is based on the 855 topology of Figure 1. 857 BFR-A BIFT BFR-B BIFT BFR-C BIFT 858 ------------------- ------------------- ------------------- 859 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR | 860 =================== =================== =================== 861 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D | 862 ------------------- ------------------- ------------------- 863 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F | 864 ------------------- | | 0110 | E | ------------------- 865 | 3 | 0111 | B | ------------------- | 3 | 1100 | B | 866 ------------------- | 3 | 0110 | E | ------------------- 867 | 4 | 1000 | A | ------------------| | 4 | 1100 | B | 868 ------------------- | 4 | 1000 | A | ------------------- 869 ------------------- 871 Figure 6: Example of ECMP 873 In this example, BFR-B has two equal cost paths to reach BFER-F, one 874 via BFR-C and one via BFR-E. Since the BFR-id of BFER-F is 2, this 875 is reflected in entry 2 of BFR-B's BIFT. Entry 2 shows that BFR-B 876 has a choice of two BFR-NBRs for BFER-B, and that a different F-BM is 877 associated with each choice. When BFR-B looks up entry 2 in the 878 BIFT, it can choose either BFR-NBR. However, when following the 879 procedures of Section 6.5, it MUST use the F-BM corresponding to the 880 BFR-NBR that it chooses. 882 How the choice is made is an implementation matter. However, the 883 usual rules for ECMP apply: packets of a given flow SHOULD NOT be 884 split among two paths, and any "entropy" field in the packet's 885 encapsulation SHOULD be respected. 887 Note however that by the rules of Section 6.5, any packet destined 888 for both BFER-D and BFER-F will be sent via BFR-C. 890 6.8. Prevention of Loops and Duplicates 892 The BitString in a BIER-encapsulated packet specifies the set of 893 BFERs to which that packet is to be forwarded. When a BIER- 894 encapsulated packet is replicated, no two copies of the packet will 895 ever have a BFER in common. If one of the packet's BFERs forwards 896 the packet further, that will first clear the bit that identifies 897 itself. As a result, duplicate delivery of packets is not possible 898 with BIER. 900 As long as the routing underlay provides a loop free path between 901 each pair of BFRs, BIER-encapsulated packets will not loop. Since 902 the BIER layer does not create any paths of its own, there is no need 903 for any BIER-specific loop prevention techniques beyond the 904 forwarding procedures specified in Section 6.5. 906 If, at some time, the routing underlay is not providing a loop free 907 path between BFIR-A and BFER-B, then BIER encapsulated packets may 908 loop while traveling from BFIR-A to BFER-B. However, such loops will 909 never result in delivery of duplicate packets to BFER-B. 911 These properties of BIER eliminate the need for the "reverse path 912 forwarding" (RPF) check that is used in conventional IP multicast 913 forwarding. 915 7. IANA Considerations 917 This document contains no actions for IANA. 919 8. Security Considerations 921 When BIER is paired with a particular multicast flow layer, it 922 inherits the security considerations of that layer. Similarly, when 923 BIER is paired with a particular routing underlay, it inherits the 924 security considerations of that layer. 926 If the BIER encapsulation of a particular packet specifies an SI or a 927 BitString other than the one intended by the BFIR, the packet is 928 likely to be misdelivered. If the BIER encapsulation of a packet is 929 modified (through error or malfeasance) in a way other than that 930 specified in this document, the packet may be misdelivered. 932 If the procedures used for advertising BFR-ids and BFR-prefixes are 933 not secure, an attack on those procedures may result in incorrect 934 delivery of BIER-encapsulated packets. 936 Every BFR must be provisioned to know which of its interfaces lead to 937 a BIER domain and which do not. If two interfaces lead to different 938 BIER domains, the BFR must be provisioned to know that those two 939 interfaces lead to different BIER domains. If the provisioning is 940 not correct, BIER-encapsulated packets from one BIER domain may 941 "leak" into another; this is likely to result in misdelivery of 942 packets. 944 9. Acknowledgements 946 The authors wish to thank Rajiv Asati, John Bettink, Nagendra Kumar, 947 Christian Martin, Neale Ranns, Greg Shepherd, and Ramji Vaithianathan 948 for their ideas and contributions to this work. 950 10. Contributor Addresses 952 Below is a list of other contributing authors in alphabetical order: 954 Wim Henderickx 955 Alcatel-Lucent 956 Copernicuslaan 50 957 Antwerp 2018 958 Belgium 960 Email: wim.henderickx@alcatel-lucent.com 962 Martin Horneffer 963 Deutsche Telekom 964 Hammer Str. 216-226 965 Muenster 48153 966 DE 968 Email: Martin.Horneffer@telekom.de 970 Uwe Joorde 971 Deutsche Telekom 972 Hammer Str. 216-226 973 Muenster D-48153 974 DE 976 Email: Uwe.Joorde@telekom.de 978 Jeff Tantsura 979 Ericsson 980 300 Holger Way 981 San Jose, CA 95134 982 US 984 Email: jeff.tantsura@ericsson.com 986 11. References 988 11.1. Normative References 990 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 991 Requirement Levels", BCP 14, RFC 2119, March 1997. 993 11.2. Informative References 995 [Boivie_Feldman] 996 Boivie, R. and N. Feldman, "Small Group Multicast", 997 (expired) draft-boivie-sgm-02.txt, February 2001. 999 [MPLS_BIER_ENCAPS] 1000 Wijnands, IJ., "BIER Encapsulation for MPLS Networks", 1001 internet-draft draft-wijnands-mpls-bier-encaps-00.txt, 1002 September 2014. 1004 [OSPF_BIER_EXTENSIONS] 1005 Kumar, N. and P. Psenak, "OSPF Extension for Bit Index 1006 Explicit Replication", internet-draft draft-kumar-ospf- 1007 bier-extension-00.txt, September 2014. 1009 [RFC6513] Rosen, E. and R. Aggarwal, "Multicast in MPLS/BGP IP 1010 VPNs", RFC 6513, February 2012. 1012 [RFC6514] Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP 1013 Encodings and Procedures for Multicast in MPLS/BGP IP 1014 VPNs", RFC 6514, February 2012. 1016 Authors' Addresses 1018 IJsbrand Wijnands (editor) 1019 Cisco Systems, Inc. 1020 De Kleetlaan 6a 1021 Diegem 1831 1022 Belgium 1024 Email: ice@cisco.com 1026 Eric C. Rosen (editor) 1027 Cisco Systems, Inc. 1028 1414 Massachusetts Avenue 1029 Boxborough, Massachusetts 01781 1030 USA 1032 Email: erosen@cisco.com 1034 Andrew Dolganow 1035 Alcatel-Lucent 1036 600 March Rd. 1037 Ottawa, Ontario K2K 2E6 1038 Canada 1040 Email: andrew.dolganow@alcatel-lucent.com 1041 Tony Przygienda 1042 Ericsson 1044 Email: antoni.przygienda@ericsson.com