Debian Codegraph @

rfc8279.html

raw
1 <pre>Internet Engineering Task Force (IETF) IJ. Wijnands, Ed.
2 Request for Comments: 8279 Cisco Systems, Inc.
3 Category: Experimental E. Rosen, Ed.
4 ISSN: 2070-1721 Juniper Networks, Inc.
5 A. Dolganow
6 Nokia
7 T. Przygienda
8 Juniper Networks, Inc.
9 S. Aldrin
10 Google, Inc.
11 November 2017
12
13
14 <span class="h1">Multicast Using Bit Index Explicit Replication (BIER)</span>
15
16 Abstract
17
18 This document specifies a new architecture for the forwarding of
19 multicast data packets. It provides optimal forwarding of multicast
20 packets through a "multicast domain". However, it does not require a
21 protocol for explicitly building multicast distribution trees, nor
22 does it require intermediate nodes to maintain any per-flow state.
23 This architecture is known as "Bit Index Explicit Replication"
24 (BIER). When a multicast data packet enters the domain, the ingress
25 router determines the set of egress routers to which the packet needs
26 to be sent. The ingress router then encapsulates the packet in a
27 BIER header. The BIER header contains a bit string in which each bit
28 represents exactly one egress router in the domain; to forward the
29 packet to a given set of egress routers, the bits corresponding to
30 those routers are set in the BIER header. The procedures for
31 forwarding a packet based on its BIER header are specified in this
32 document. Elimination of the per-flow state and the explicit tree-
33 building protocols results in a considerable simplification.
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 <span class="grey">Wijnands, et al. Experimental [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
55
56
57 Status of This Memo
58
59 This document is not an Internet Standards Track specification; it is
60 published for examination, experimental implementation, and
61 evaluation.
62
63 This document defines an Experimental Protocol for the Internet
64 community. This document is a product of the Internet Engineering
65 Task Force (IETF). It represents the consensus of the IETF
66 community. It has received public review and has been approved for
67 publication by the Internet Engineering Steering Group (IESG). Not
68 all documents approved by the IESG are a candidate for any level of
69 Internet Standard; see <a href="./rfc7841#section-2">Section&nbsp;2 of RFC 7841</a>.
70
71 Information about the current status of this document, any errata,
72 and how to provide feedback on it may be obtained at
73 <a href="https://www.rfc-editor.org/info/rfc8279">https://www.rfc-editor.org/info/rfc8279</a>.
74
75 Copyright Notice
76
77 Copyright (c) 2017 IETF Trust and the persons identified as the
78 document authors. All rights reserved.
79
80 This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
81 Provisions Relating to IETF Documents
82 (<a href="https://trustee.ietf.org/license-info">https://trustee.ietf.org/license-info</a>) in effect on the date of
83 publication of this document. Please review these documents
84 carefully, as they describe your rights and restrictions with respect
85 to this document. Code Components extracted from this document must
86 include Simplified BSD License text as described in Section 4.e of
87 the Trust Legal Provisions and are provided without warranty as
88 described in the Simplified BSD License.
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108 <span class="grey">Wijnands, et al. Experimental [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
111
112
113 Table of Contents
114
115 <a href="#section-1">1</a>. Introduction ....................................................<a href="#page-4">4</a>
116 <a href="#section-2">2</a>. The BFR Identifier and BFR-Prefix ...............................<a href="#page-7">7</a>
117 <a href="#section-3">3</a>. Encoding BFR Identifiers in BitStrings ..........................<a href="#page-8">8</a>
118 <a href="#section-4">4</a>. Layering .......................................................<a href="#page-11">11</a>
119 <a href="#section-4.1">4.1</a>. The Routing Underlay ......................................<a href="#page-11">11</a>
120 <a href="#section-4.2">4.2</a>. The BIER Layer ............................................<a href="#page-12">12</a>
121 <a href="#section-4.3">4.3</a>. The Multicast Flow Overlay ................................<a href="#page-13">13</a>
122 <a href="#section-5">5</a>. Advertising BFR-ids and BFR-Prefixes ...........................<a href="#page-13">13</a>
123 <a href="#section-6">6</a>. BIER Intra-Domain Forwarding Procedures ........................<a href="#page-15">15</a>
124 <a href="#section-6.1">6.1</a>. Overview ..................................................<a href="#page-15">15</a>
125 <a href="#section-6.2">6.2</a>. BFR Neighbors .............................................<a href="#page-17">17</a>
126 <a href="#section-6.3">6.3</a>. The Bit Index Routing Table ...............................<a href="#page-18">18</a>
127 <a href="#section-6.4">6.4</a>. The Bit Index Forwarding Table ............................<a href="#page-19">19</a>
128 <a href="#section-6.5">6.5</a>. The BIER Forwarding Procedure .............................<a href="#page-20">20</a>
129 <a href="#section-6.6">6.6</a>. Examples of BIER Forwarding ...............................<a href="#page-23">23</a>
130 <a href="#section-6.6.1">6.6.1</a>. Example 1 ..........................................<a href="#page-23">23</a>
131 <a href="#section-6.6.2">6.6.2</a>. Example 2 ..........................................<a href="#page-24">24</a>
132 <a href="#section-6.7">6.7</a>. Equal-Cost Multipath Forwarding ...........................<a href="#page-26">26</a>
133 <a href="#section-6.7.1">6.7.1</a>. Non-deterministic ECMP .............................<a href="#page-27">27</a>
134 <a href="#section-6.7.2">6.7.2</a>. Deterministic ECMP .................................<a href="#page-28">28</a>
135 <a href="#section-6.8">6.8</a>. Prevention of Loops and Duplicates ........................<a href="#page-29">29</a>
136 <a href="#section-6.9">6.9</a>. When Some Nodes Do Not Support BIER .......................<a href="#page-30">30</a>
137 <a href="#section-6.10">6.10</a>. Use of Different BitStringLengths within a Domain ........<a href="#page-33">33</a>
138 <a href="#section-6.10.1">6.10.1</a>. BitStringLength Compatibility Check ...............<a href="#page-34">34</a>
139 <a href="#section-6.10.2">6.10.2</a>. Handling BitStringLength Mismatches ...............<a href="#page-36">36</a>
140 6.10.3. Transitioning from One BitStringLength to
141 Another ...........................................<a href="#page-36">36</a>
142 <a href="#section-7">7</a>. Operational Considerations .....................................<a href="#page-37">37</a>
143 <a href="#section-7.1">7.1</a>. Configuration .............................................<a href="#page-37">37</a>
144 <a href="#section-8">8</a>. IANA Considerations ............................................<a href="#page-37">37</a>
145 <a href="#section-9">9</a>. Security Considerations ........................................<a href="#page-38">38</a>
146 <a href="#section-10">10</a>. References ....................................................<a href="#page-39">39</a>
147 <a href="#section-10.1">10.1</a>. Normative References .....................................<a href="#page-39">39</a>
148 <a href="#section-10.2">10.2</a>. Informative References ...................................<a href="#page-39">39</a>
149 Acknowledgements ..................................................<a href="#page-40">40</a>
150 Contributors ......................................................<a href="#page-41">41</a>
151 Authors' Addresses ................................................<a href="#page-43">43</a>
152
153
154
155
156
157
158
159
160
161
162
163
164 <span class="grey">Wijnands, et al. Experimental [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
167
168
169 <span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
170
171 This document specifies a new architecture for the forwarding of
172 multicast data packets. The architecture provides optimal forwarding
173 of multicast data packets through a "multicast domain". However, it
174 does not require the use of a protocol for explicitly building
175 multicast distribution trees, and it does not require intermediate
176 nodes to maintain any per-flow state. This architecture is known as
177 "Bit Index Explicit Replication" (BIER).
178
179 A router that supports BIER is known as a "Bit-Forwarding Router"
180 (BFR). The BIER control-plane protocols (see <a href="#section-4.2">Section 4.2</a>) run within
181 a "BIER domain", allowing the BFRs within that domain to exchange the
182 information needed for them to forward packets to each other
183 using BIER.
184
185 A multicast data packet enters a BIER domain at a "Bit-Forwarding
186 Ingress Router" (BFIR), and leaves the BIER domain at one or more
187 "Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a
188 multicast data packet from another BFR in the same BIER domain, and
189 forwards the packet to another BFR in the same BIER domain, will be
190 known as a "transit BFR" for that packet. A single BFR may be a BFIR
191 for some multicast traffic while also being a BFER for some multicast
192 traffic and a transit BFR for some multicast traffic. In fact, for a
193 given packet, a BFR may be a BFIR and/or a transit BFR and/or (one
194 of) the BFER(s) for that packet.
195
196 A BIER domain may contain one or more sub-domains. Each BIER domain
197 MUST contain at least one sub-domain, the "default sub-domain" (also
198 denoted "sub-domain 0"). If a BIER domain contains more than one
199 sub-domain, each BFR in the domain MUST be provisioned to know the
200 set of sub-domains to which it belongs. Each sub-domain is
201 identified by a sub-domain-id in the range [0,255].
202
203 For each sub-domain to which a given BFR belongs, if the BFR is
204 capable of acting as a BFIR or a BFER, it MUST be provisioned with a
205 "BFR-id" that is unique within the sub-domain. A BFR-id is a small
206 unstructured positive integer. For instance, if a particular BIER
207 sub-domain contains 1,374 BFRs, each one could be given a BFR-id in
208 the range [1,1374].
209
210 If a given BFR belongs to more than one sub-domain, it may (though it
211 need not) have a different BFR-id for each sub-domain.
212
213 When a multicast packet arrives from outside the domain at a BFIR,
214 the BFIR determines the set of BFERs to which the packet will be
215 sent. The BFIR also determines the sub-domain in which the packet
216 will be sent. Determining the sub-domain in which a given packet
217
218
219
220 <span class="grey">Wijnands, et al. Experimental [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
223
224
225 will be sent is known as "assigning the packet to a sub-domain".
226 Procedures for choosing the sub-domain to which a particular packet
227 is assigned are outside the scope of this document. However, once a
228 particular packet has been assigned to a particular sub-domain, it
229 remains assigned to that sub-domain until it leaves the BIER domain.
230 That is, the sub-domain to which a packet is assigned MUST NOT be
231 changed while the packet is in flight through the BIER domain.
232
233 Once the BFIR determines the sub-domain and the set of BFERs for a
234 given packet, the BFIR encapsulates the packet in a "BIER header".
235 The BIER header contains a bit string in which each bit represents a
236 single BFR-id. To indicate that a particular BFER is to receive a
237 given packet, the BFIR sets the bit corresponding to that BFER's
238 BFR-id in the sub-domain to which the packet has been assigned. We
239 will use the term "BitString" to refer to the bit string field in the
240 BIER header. We will use the term "payload" to refer to the packet
241 that has been encapsulated. Thus, a "BIER-encapsulated" packet
242 consists of a "BIER header" followed by a "payload".
243
244 The number of BFERs to which a given packet can be forwarded is
245 limited only by the length of the BitString in the BIER header.
246 Different deployments can use different BitString lengths. We will
247 use the term "BitStringLength" to refer to the number of bits in the
248 BitString. It is possible that some deployments will have more BFERs
249 in a given sub-domain than there are bits in the BitString. To
250 accommodate this case, the BIER encapsulation includes both the
251 BitString and a "Set Identifier" (SI). It is the BitString and the
252 SI together that determine the set of BFERs to which a given packet
253 will be delivered:
254
255 o By convention, the least significant (rightmost) bit in the
256 BitString is "bit 1", and the most significant (leftmost) bit is
257 "bit BitStringLength".
258
259 o If a BIER-encapsulated packet has an SI of n and a BitString with
260 bit k set, then the packet must be delivered to the BFER whose
261 BFR-id (in the sub-domain to which the packet has been assigned)
262 is n*BitStringLength+k.
263
264 For example, suppose the BIER encapsulation uses a BitStringLength of
265 256 bits. By convention, the least significant (rightmost) bit is
266 bit 1, and the most significant (leftmost) bit is bit 256. Suppose
267 that a given packet has been assigned to sub-domain 0 and needs to be
268 delivered to three BFERs, where those BFERs have BFR-ids in
269 sub-domain 0 of 13, 126, and 235, respectively. The BFIR would
270 create a BIER encapsulation with the SI set to zero and with bits 13,
271 126, and 235 of the BitString set. (All other bits of the BitString
272 would be clear.) If the packet also needs to be sent to a BFER whose
273
274
275
276 <span class="grey">Wijnands, et al. Experimental [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
279
280
281 BFR-id is 257, the BFIR would have to create a second copy of the
282 packet, and the BIER encapsulation would specify an SI of 1, and a
283 BitString with bit 1 set and all the other bits clear.
284
285 It is generally advantageous to assign the BFR-ids of a given
286 sub-domain so that as many BFERs as possible can be represented in a
287 single bit string.
288
289 Suppose a BFR (call it "BFR-A") receives a packet whose BIER
290 encapsulation specifies an SI of 0 and a BitString with bits 13, 26,
291 and 235 set. Suppose BFR-A has two BFR neighbors, BFR-B and BFR-C,
292 such that the best path to BFERs 13 and 26 is via BFR-B, but the best
293 path to BFER 235 is via BFR-C. BFR-A will then replicate the packet,
294 sending one copy to BFR-B and one copy to BFR-C. However, BFR-A will
295 clear bit 235 in the BitString of the packet copy it sends to BFR-B
296 and will clear bits 13 and 26 in the BitString of the packet copy it
297 sends to BFR-C. As a result, BFR-B will forward the packet only
298 towards BFERs 13 and 26, and BFR-C will forward the packet only
299 towards BFER 235. This ensures that each BFER receives only one copy
300 of the packet.
301
302 Detailed procedures for forwarding a BIER-encapsulated packet through
303 a BIER domain can be found in <a href="#section-6">Section 6</a>.
304
305 With this forwarding procedure, a multicast data packet can follow an
306 optimal path from its BFIR to each of its BFERs. Further, since the
307 set of BFERs for a given packet is explicitly encoded into the BIER
308 header, the packet is not sent to any BFER that does not need to
309 receive it. This allows for optimal forwarding of multicast traffic.
310 This optimal forwarding is achieved without any need for transit BFRs
311 to maintain per-flow state or to run a multicast tree-building
312 protocol.
313
314 The idea of encoding the set of egress nodes into the header of a
315 multicast packet is not new. For example, [<a href="#ref-Boivie_Feldman">Boivie_Feldman</a>] proposes
316 to encode the set of egress nodes as a set of IP addresses, and
317 proposes mechanisms and procedures that are in some ways similar to
318 those described in the current document. However, since BIER encodes
319 each BFR-id as a single bit in a bit string, it can represent up to
320 128 BFERs in the same number of bits that it would take to carry the
321 IPv6 address of a single BFER. Thus, BIER scales to a much larger
322 number of egress nodes per packet.
323
324 BIER does not require that each transit BFR look up the best path to
325 each BFER that is identified in the BIER header; the number of
326 lookups required in the forwarding path for a single packet can be
327
328
329
330
331
332 <span class="grey">Wijnands, et al. Experimental [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
335
336
337 limited to the number of neighboring BFRs; this can be much smaller
338 than the number of BFERs. See <a href="#section-6">Section 6</a> (especially <a href="#section-6.5">Section 6.5</a>) for
339 details.
340
341 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
342 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
343 "OPTIONAL" in this document are to be interpreted as described in
344 <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a> [<a href="./rfc2119" title="&quot;Key words for use in RFCs to Indicate Requirement Levels&quot;">RFC2119</a>] [<a href="./rfc8174" title="&quot;Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words&quot;">RFC8174</a>] when, and only when, they appear in all
345 capitals, as shown here.
346
347 <span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. The BFR Identifier and BFR-Prefix</span>
348
349 Each BFR MUST be assigned a single "BFR-prefix" for each sub-domain
350 to which it belongs. A BFR's BFR-prefix MUST be an IP address
351 (either IPv4 or IPv6) of the BFR. It is RECOMMENDED that the
352 BFR-prefix be a loopback address of the BFR.
353
354 If a BFR belongs to more than one sub-domain, it may (though it need
355 not) have a different BFR-prefix in each sub-domain.
356
357 All BFR-prefixes used within a given sub-domain MUST belong to the
358 same address family (either IPv4 or IPv6).
359
360 The BFR-prefix of a given BFR in a given sub-domain MUST be routable
361 in that sub-domain. Whether a particular BFR-prefix is routable in a
362 given sub-domain depends on the "routing underlay" associated with
363 that sub-domain. The notion of "routing underlay" is described in
364 <a href="#section-4.1">Section 4.1</a>.
365
366 A "BFR Identifier" (BFR-id) is a number in the range [1,65535].
367 Within a given sub-domain, every BFR that may need to function as a
368 BFIR or BFER MUST have a single BFR-id, which identifies it uniquely
369 within that sub-domain. A BFR that does not need to function as a
370 BFIR or BFER in a given sub-domain does not need to have a BFR-id in
371 that sub-domain.
372
373 The value 0 is not a legal BFR-id.
374
375 The procedure for assigning a particular BFR-id to a particular BFR
376 is outside the scope of this document. However, it is RECOMMENDED
377 that the BFR-ids for each sub-domain be assigned "densely" from the
378 numbering space, as this will result in a more efficient encoding
379 (see <a href="#section-3">Section 3</a>). That is, if there are 256 or fewer BFERs, it is
380 RECOMMENDED to assign all the BFR-ids from the range [1,256]. If
381 there are more than 256 BFERs but less than 512, it is RECOMMENDED to
382 assign all the BFR-ids from the range [1,512], with as few "holes" as
383
384
385
386
387
388 <span class="grey">Wijnands, et al. Experimental [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
391
392
393 possible in the earlier range. However, in some deployments, it may
394 be advantageous to depart from this recommendation; this is discussed
395 further in <a href="#section-3">Section 3</a>.
396
397 In some deployments, it may not be possible to support (in a given
398 sub-domain) the full range of 65,535 BFR-ids. For example, if the
399 BFRs in a given sub-domain only support 16 SIs and if they only
400 support BitStringLengths of 256 or less, then only 16*256=4,096
401 BFR-ids can be supported in that sub-domain.
402
403 <span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Encoding BFR Identifiers in BitStrings</span>
404
405 To encode a BFR-id in a BIER data packet, one must convert the BFR-id
406 to an SI and a BitString. This conversion depends upon the parameter
407 we are calling "BitStringLength". The conversion is done as follows.
408 If the BFR-id is N, then
409
410 o SI is the integer part of the quotient (N-1)/BitStringLength.
411
412 o The BitString has one bit position set. If the low-order bit is
413 bit 1 and the high-order bit is bit BitStringLength, the bit
414 position that represents BFR-id N is
415 ((N-1) modulo BitStringLength)+1.
416
417 If several different BFR-ids all resolve to the same SI, then all of
418 those BFR-ids can be represented in a single BitString. The
419 BitStrings for all of those BFR-ids are combined using a bitwise
420 logical OR operation.
421
422 Within a given BIER domain (or even within a given BIER sub-domain),
423 different values of BitStringLength may be used. Each BFR MUST be
424 provisioned to know the following:
425
426 o The BitStringLength ("Imposition BitStringLength") and sub-domain
427 ("Imposition sub-domain") to use when it imposes (as a BFIR) a
428 BIER encapsulation on a particular set of packets, and
429
430 o The BitStringLengths ("Disposition BitStringLengths") that it will
431 process when (as a BFR or BFER) it receives packets from a
432 particular sub-domain.
433
434 It is not required that a BFIR use the same Imposition
435 BitStringLength or the same Imposition sub-domain for all packets on
436 which it imposes the BIER encapsulation. However, if a particular
437 BFIR is provisioned to use a particular Imposition BitStringLength
438 and a particular Imposition sub-domain when imposing the
439 encapsulation on a given set of packets, all other BFRs with BFR-ids
440 in that sub-domain SHOULD be provisioned to process received BIER
441
442
443
444 <span class="grey">Wijnands, et al. Experimental [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
447
448
449 packets with that BitStringLength (i.e., all other BFRs with BFR-ids
450 in that sub-domain SHOULD be provisioned with that BitStringLength as
451 a Disposition BitStringLength for that sub-domain). Exceptions to
452 this rule MAY be made under certain conditions; this is discussed in
453 <a href="#section-6.10">Section 6.10</a>.
454
455 When a BIER encapsulation is specified, the specification MUST define
456 a default BitStringLength for the encapsulation. Every BFIR
457 supporting that encapsulation MUST be capable of being provisioned
458 with that default BitStringLength as its Imposition BitStringLength.
459 Every BFR and BFER supporting that encapsulation MUST be capable of
460 being provisioned with that default BitStringLength as a Disposition
461 BitStringLength.
462
463 The specification of a BIER encapsulation MAY also allow the use of
464 other BitStringLengths.
465
466 If a BFR is capable of being provisioned with a given value of
467 BitStringLength as an Imposition BitStringLength, it MUST also be
468 capable of being provisioned with that same value as one of its
469 Disposition BitStringLengths. It SHOULD be capable of being
470 provisioned with each legal smaller value of BitStringLength as (a)
471 its Imposition BitStringLength, and (b) one of its Disposition
472 BitStringLengths.
473
474 In order to support transition from one BitStringLength to another,
475 every BFR MUST be capable of being provisioned to simultaneously use
476 two different Disposition BitStringLengths.
477
478 A BFR MUST support SI values in the range [0,15] and MAY support SI
479 values in the range [0,255]. ("Supporting the values in a given
480 range" means, in this context, that any value in the given range is
481 legal and will be properly interpreted.) Note that for a given
482 BitStringLength, the total number of BFR-ids that can be represented
483 is the product of the BitStringLength and the number of supported
484 SIs. For example, if a deployment uses (in a given sub-domain) a
485 BitStringLength of 64 and supports 256 SIs, that deployment can only
486 support 16384 BFR-ids in that sub-domain. Even a deployment that
487 supports 256 SIs will not be able to support 65,535 BFR-ids unless it
488 uses a BitStringLength of at least 256.
489
490 When a BFIR determines that a multicast data packet, assigned to a
491 given sub-domain, needs to be forwarded to a particular set of
492 destination BFERs, the BFIR partitions that set of BFERs into
493 subsets, where each subset contains the target BFERs whose BFR-ids in
494 the given sub-domain all resolve to the same SI. Call these the
495 "SI-subsets" for the packet. Each SI-subset can be represented by a
496 single BitString. The BFIR creates a copy of the packet for each
497
498
499
500 <span class="grey">Wijnands, et al. Experimental [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
503
504
505 SI-subset. The BIER encapsulation is then applied to each packet.
506 The encapsulation specifies a single SI for each packet and contains
507 the BitString that represents all the BFR-ids in the corresponding
508 SI-subset. Of course, in order to properly interpret the BitString,
509 it must be possible to infer the sub-domain-id from the encapsulation
510 as well.
511
512 Suppose, for example, that a BFIR determines that a given packet
513 needs to be forwarded to three BFERs, whose BFR-ids (in the
514 appropriate sub-domain) are 27, 235, and 497. The BFIR will have to
515 forward two copies of the packet. One copy, associated with SI=0,
516 will have a BitString with bits 27 and 235 set. The other copy,
517 associated with SI=1, will have a BitString with bit 241 set.
518
519 In order to minimize the number of copies that must be made of a
520 given multicast packet, it is RECOMMENDED that the BFR-ids used in a
521 given sub-domain be assigned "densely" (see <a href="#section-2">Section 2</a>) from the
522 numbering space. This will minimize the number of SIs that have to
523 be used in that sub-domain. However, depending upon the details of a
524 particular deployment, other assignment methods may be more
525 advantageous. Suppose, for example, that in a certain deployment,
526 every multicast flow is intended either for the "east coast" or for
527 the "west coast", but not for both coasts. In such a deployment, it
528 would be advantageous to assign BFR-ids so that all the "west coast"
529 BFR-ids fall into the same SI-subset and so that all the "east coast"
530 BFR-ids fall into the same SI-subset.
531
532 When a BFR receives a BIER data packet, it will infer the SI from the
533 encapsulation. The set of BFERs to which the packet needs to be
534 forwarded can then be inferred from the SI and the BitString.
535
536 In some of the examples given later in this document, we will use a
537 BitStringLength of 4 and will represent a BFR-id in the form
538 "SI:xyzw", where SI is the Set Identifier of the BFR-id (assuming a
539 BitStringLength of 4) and xyzw is a string of 4 bits. A
540 BitStringLength of 4 is used only in the examples; we would not
541 expect actual deployments to have such a small BitStringLength.
542
543 It is possible that several different forms of BIER encapsulation
544 will be developed. If so, the particular encapsulation that is used
545 in a given deployment will depend on the type of network
546 infrastructure that is used to realize the BIER domain. Details of
547 the BIER encapsulation(s) will be given in companion documents. An
548 encapsulation for use in MPLS networks is described in
549 [<a href="#ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>]; that document also describes a very similar
550 encapsulation that can be used in non-MPLS networks.
551
552
553
554
555
556 <span class="grey">Wijnands, et al. Experimental [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
559
560
561 <span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Layering</span>
562
563 It is helpful to think of the BIER architecture as consisting of
564 three layers: the "routing underlay", the "BIER layer", and the
565 "multicast flow overlay".
566
567 <span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. The Routing Underlay</span>
568
569 The "routing underlay" establishes "adjacencies" between pairs of
570 BFRs and determines one or more "best paths" from a given BFR to a
571 given set of BFRs. Each such path is a sequence of BFRs
572 &lt;BFR(k), BFR(k+1), ..., BFR(k+n)&gt; such that BFR(k+j) is "adjacent" to
573 BFR(k+j+1) (for 0&lt;=j&lt;n).
574
575 At a given BFR, say BFR-A, for every IP address that is the address
576 of a BFR in the BIER domain, the routing underlay will map that IP
577 address into a set of one or more "equal-cost" adjacencies. If a
578 BIER data packet has to be forwarded by BFR-A to a given BFER, say
579 BFER-B, the packet will follow the path from BFR-A to BFER-B that is
580 determined by the routing underlay.
581
582 It is expected that in a typical deployment, the routing underlay
583 will be the default topology that the Interior Gateway Protocol
584 (IGP), e.g., OSPF, uses for unicast routing. In that case, the
585 underlay adjacencies are just the OSPF adjacencies. A BIER data
586 packet traveling from BFR-A to BFER-B will follow the path that OSPF
587 has selected for unicast traffic from BFR-A to BFER-B.
588
589 If one wants to have multicast traffic from BFR-A to BFER-B travel a
590 path that is different from the path used by the unicast traffic from
591 BFR-A to BFER-B, one can use a different underlay. For example, if
592 multi-topology OSPF is being used, one OSPF topology could be used
593 for unicast traffic and the other for multicast traffic. (Each
594 topology would be considered to be a different underlay.)
595 Alternatively, one could deploy a routing underlay that creates a
596 multicast-specific tree of some sort. BIER could then be used to
597 forward multicast data packets along the multicast-specific tree,
598 while unicast packets follow the "ordinary" OSPF best path. (In a
599 case like this, many multicast flows could be traveling along a
600 single tree, and the BitString carried by a particular packet would
601 identify those nodes of the tree that need to receive that packet.)
602 It is even possible to have multiple routing underlays used by BIER,
603 as long as one can infer from a data packet's BIER encapsulation
604 which underlay is being used for that packet.
605
606
607
608
609
610
611
612 <span class="grey">Wijnands, et al. Experimental [Page 11]</span></pre>
613 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
614 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
615
616
617 If multiple routing underlays are used in a single BIER domain, each
618 BIER sub-domain MUST be associated with a single routing underlay
619 (though multiple sub-domains may be associated with the same routing
620 underlay). A BFR that belongs to multiple sub-domains MUST be
621 provisioned to know which routing underlay is used by each
622 sub-domain. By default (i.e., in the absence of any provisioning to
623 the contrary), each sub-domain uses the default topology of the
624 unicast IGP as the routing underlay.
625
626 In scenarios where External BGP (EBGP) is used as the IGP, the
627 underlay adjacencies, by default, are the BGP adjacencies.
628
629 Specification of the protocols and procedures of the routing underlay
630 is outside the scope of this document.
631
632 <span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. The BIER Layer</span>
633
634 The BIER layer consists of the protocols and procedures that are used
635 in order to transmit a multicast data packet across a BIER domain,
636 from its BFIR to its BFERs. This includes the following components:
637
638 o Protocols and procedures that a given BFR uses to advertise, to
639 all other BFRs in the same BIER domain:
640
641 * its BFR-prefix;
642
643 * its BFR-id in each sub-domain for which it has been provisioned
644 with a BFR-id;
645
646 * the set of Disposition BitStringLengths it has been provisioned
647 to use for each sub-domain;
648
649 * optionally, information about the routing underlay associated
650 with each sub-domain.
651
652 o The procedures used by a BFIR to impose a BIER header on a
653 multicast data packet.
654
655 o The procedures for forwarding BIER-encapsulated packets and for
656 modifying the BIER header during transit.
657
658 o The procedures used by a BFER to decapsulate a BIER packet and
659 properly dispatch it.
660
661
662
663
664
665
666
667
668 <span class="grey">Wijnands, et al. Experimental [Page 12]</span></pre>
669 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
670 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
671
672
673 <span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a>. The Multicast Flow Overlay</span>
674
675 The "multicast flow overlay" consists of the set of protocols and
676 procedures that enable the following set of functions.
677
678 o When a BFIR receives a multicast data packet from outside the BIER
679 domain, the BFIR must determine the set of BFERs for that packet.
680 This information is provided by the multicast flow overlay.
681
682 o When a BFER receives a BIER-encapsulated packet from inside the
683 BIER domain, the BFER must determine how to further forward the
684 packet. This information is provided by the multicast flow
685 overlay.
686
687 For example, suppose the BFIR and BFERs are Provider Edge (PE)
688 routers providing Multicast Virtual Private Network (MVPN) service.
689 The multicast flow overlay consists of the protocols and procedures
690 described in [<a href="./rfc6513" title="&quot;Multicast in MPLS/BGP IP VPNs&quot;">RFC6513</a>] and [<a href="./rfc6514" title="&quot;BGP Encodings and Procedures for Multicast in MPLS/BGP IP VPNs&quot;">RFC6514</a>]. The MVPN signaling described
691 in those RFCs enables an ingress PE to determine the set of egress
692 PEs for a given multicast flow (or set of flows); it also enables an
693 egress PE to determine the "Virtual Routing and Forwarding Tables"
694 (VRFs) to which multicast packets from the backbone network should be
695 sent. MVPN signaling also has several components that depend on the
696 type of "tunneling technology" used to carry multicast data through
697 the network. Since BIER is, in effect, a new type of "tunneling
698 technology", some extensions to the MVPN signaling are needed in
699 order to properly interface the multicast flow overlay with the BIER
700 layer. These are specified in [<a href="#ref-BIER_MVPN">BIER_MVPN</a>].
701
702 MVPN is just one example of a multicast flow overlay. Protocols and
703 procedures for other overlays will be provided in companion
704 documents. It is also possible to implement the multicast flow
705 overlay by means of a "Software-Defined Network" (SDN) controller.
706 Specification of the protocols and procedures of the multicast flow
707 overlay is outside the scope of this document.
708
709 <span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Advertising BFR-ids and BFR-Prefixes</span>
710
711 As stated in <a href="#section-2">Section 2</a>, each BFER is assigned (by provisioning) a
712 BFR-id (for a given BIER sub-domain). Each BFER must advertise these
713 assignments to all the other BFRs in the domain. Similarly, each BFR
714 is assigned (by provisioning) a BFR-prefix (for a given BIER domain)
715 and must advertise this assignment to all the other BFRs in the
716 domain. Finally, each BFR has been provisioned to use a certain set
717 of Disposition BitStringLengths for each sub-domain and must
718 advertise these to all other BFRs in the domain.
719
720
721
722
723
724 <span class="grey">Wijnands, et al. Experimental [Page 13]</span></pre>
725 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
726 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
727
728
729 If the BIER domain is also a link-state routing IGP domain (i.e., an
730 OSPF or IS-IS domain), the advertisement of the BFR-prefix,
731 &lt;sub-domain-id, BFR-id&gt;, and BitStringLength can be done using the
732 advertisement capabilities of the IGP. For example, if a BIER domain
733 is also an OSPF domain, these advertisements can be done using the
734 OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism.
735 Details of the necessary extensions to OSPF and IS-IS will be
736 provided in companion documents. (See [<a href="#ref-OSPF_BIER_EXTENSIONS">OSPF_BIER_EXTENSIONS</a>] and
737 [<a href="#ref-ISIS_BIER_EXTENSIONS">ISIS_BIER_EXTENSIONS</a>].)
738
739 If, in a particular deployment, the BIER domain is not an OSPF or
740 IS-IS domain, procedures suitable to the deployment must be used to
741 advertise this information. Details of the necessary procedures will
742 be provided in companion documents. For example, if BGP is the only
743 routing algorithm used in the BIER domain, the procedures of
744 [<a href="#ref-BGP_BIER_EXTENSIONS">BGP_BIER_EXTENSIONS</a>] may be used.
745
746 These advertisements enable each BFR to associate a given
747 &lt;sub-domain-id, BFR-id&gt; with a given BFR-prefix. As will be seen in
748 subsequent sections of this document, knowledge of this association
749 is an important part of the forwarding process.
750
751 Since each BFR needs to have a unique (in each sub-domain) BFR-id,
752 two different BFRs will not advertise ownership of the same
753 &lt;sub-domain-id, BFR-id&gt; unless there has been a provisioning error.
754
755 o If BFR-A determines that BFR-B and BFR-C have both advertised the
756 same BFR-id for the same sub-domain, BFR-A MUST log an error.
757 Suppose that the duplicate BFR-id is "N". When BFR-A is
758 functioning as a BFIR, it MUST NOT encode the BFR-id value N in
759 the BIER encapsulation of any packet that has been assigned to the
760 given sub-domain, even if it has determined that the packet needs
761 to be received by BFR-B and/or BFR-C.
762
763 This will mean that BFR-B and BFR-C cannot receive multicast
764 traffic at all in the given sub-domain until the provisioning
765 error is fixed. However, that is preferable to having them
766 receive each other's traffic.
767
768 o Suppose that BFR-A has been provisioned with BFR-id N for a
769 particular sub-domain but that it has not yet advertised its
770 ownership of BFR-id N for that sub-domain. Suppose also that it
771 has received an advertisement from a different BFR (say BFR-B)
772 that is advertising ownership of BFR-id N for the same sub-domain.
773 In such a case, BFR-A SHOULD log an error and MUST NOT advertise
774 its own ownership of BFR-id N for that sub-domain as long as the
775 advertisement from BFR-B is extant.
776
777
778
779
780 <span class="grey">Wijnands, et al. Experimental [Page 14]</span></pre>
781 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span>
782 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
783
784
785 This procedure may prevent the accidental misconfiguration of a
786 new BFR from impacting an existing BFR.
787
788 If a BFR advertises that it has a BFR-id of 0 in a particular
789 sub-domain, other BFRs receiving the advertisement MUST interpret
790 that advertisement as meaning that the advertising BFR does not have
791 a BFR-id in that sub-domain.
792
793 <span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. BIER Intra-Domain Forwarding Procedures</span>
794
795 This section specifies the rules for forwarding a BIER-encapsulated
796 data packet within a BIER domain. These rules are not intended to
797 specify an implementation strategy; to conform to this specification,
798 an implementation need only produce the same results that these rules
799 produce.
800
801 <span class="h3"><a class="selflink" id="section-6.1" href="#section-6.1">6.1</a>. Overview</span>
802
803 This section provides a brief overview of the BIER forwarding
804 procedures. Subsequent subsections specify the procedures in more
805 detail.
806
807 To forward a BIER-encapsulated packet:
808
809 1. Determine the packet's sub-domain.
810
811 2. Determine the packet's BitStringLength and BitString.
812
813 3. Determine the packet's SI.
814
815 4. From the sub-domain, the SI, and the BitString, determine the set
816 of destination BFERs for the packet.
817
818 5. Using information provided by the routing underlay associated
819 with the packet's sub-domain, determine the next-hop adjacency
820 for each of the destination BFERs.
821
822 6. It is possible that the packet's BitString will have one or more
823 bits that correspond to BFR-ids that are not in use. It is also
824 possible that the packet's BitString will have one or more bits
825 that correspond to BFERs that are unreachable, i.e., that have no
826 next-hop adjacency. In the following, we will consider the
827 "next-hop adjacency" for all such bit positions to be the "null"
828 next hop.
829
830 7. Partition the set of destination BFERs such that all the BFERs in
831 a single partition have the same next hop. We will say that each
832 partition is associated with a next hop.
833
834
835
836 <span class="grey">Wijnands, et al. Experimental [Page 15]</span></pre>
837 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span>
838 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
839
840
841 8. For each partition:
842
843 a. Make a copy of the packet.
844
845 b. Clear any bit in the packet's BitString that identifies a
846 BFER that is not in the partition.
847
848 c. Transmit the packet to the associated next hop. (If the
849 next hop is the null next hop, the packet is discarded.)
850
851 If a BFR receives a BIER-encapsulated packet whose &lt;sub-domain, SI,
852 BitString&gt; triple identifies that BFR itself, then the BFR is also a
853 BFER for that packet. As a BFER, it must pass the payload to the
854 multicast flow overlay. If the BitString has bits set for other
855 BFRs, the packet also needs to be forwarded further within the BIER
856 domain. If the BF(E)R also forwards one or more copies of the packet
857 within the BIER domain, the bit representing the BFR's own BFR-id
858 MUST be clear in all the copies.
859
860 When BIER on a BFER is to pass a packet to the multicast flow
861 overlay, it of course decapsulates the packet by removing the BIER
862 header. However, it may be necessary to provide the multicast flow
863 overlay with contextual information obtained from the BIER
864 encapsulation. The information that needs to pass between the BIER
865 layer and the multicast flow overlay is specific to the multicast
866 flow overlay. Specification of the interaction between the BIER
867 layer and the multicast flow overlay is outside the scope of this
868 specification.
869
870 If the BIER encapsulation contains a "Time to Live" (TTL) value, this
871 value is not, by default, inherited by the payload. If a particular
872 multicast flow overlay needs to know the TTL value, this needs to be
873 specified in whatever specification defines the interaction between
874 BIER and that multicast flow overlay.
875
876 If the BIER encapsulation contains a Traffic Class field, a
877 Type of Service field, a Differentiated Services field, or any field
878 of that sort, the value of that field is not, by default, passed to
879 the multicast flow overlay. If a particular multicast flow overlay
880 needs to know the values of such fields, this fact needs to be
881 specified in whatever specification defines the interaction between
882 BIER and that multicast flow overlay.
883
884 When BIER on a BFER passes a packet to the multicast flow overlay,
885 the overlay will determine how to further dispatch the packet. If
886 the packet needs to be forwarded into another BIER domain, then the
887 BFR will act as a BFER in one BIER domain and as a BFIR in another.
888
889
890
891
892 <span class="grey">Wijnands, et al. Experimental [Page 16]</span></pre>
893 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span>
894 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
895
896
897 A BIER-encapsulated packet cannot pass directly from one BIER domain
898 to another; at the boundary between BIER domains, the packet must be
899 decapsulated and passed to the multicast flow overlay.
900
901 Note that when a BFR transmits multiple copies of a packet within a
902 BIER domain, only one copy will be destined to any given BFER.
903 Therefore, it is not possible for any BIER-encapsulated packet to be
904 delivered more than once to any BFER.
905
906 <span class="h3"><a class="selflink" id="section-6.2" href="#section-6.2">6.2</a>. BFR Neighbors</span>
907
908 The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those
909 BFRs that, according to the routing underlay, are adjacencies of
910 BFR-A. Each BFR-NBR will have a BFR-prefix.
911
912 Suppose a BIER-encapsulated packet arrives at BFR-A. From the
913 packet's encapsulation, BFR-A learns (a) the sub-domain of the packet
914 and (b) the BFR-ids (in that sub-domain) of the BFERs to which the
915 packet is destined. Then, using the information advertised per
916 <a href="#section-5">Section 5</a>, BFR-A can find the BFR-prefix of each destination BFER.
917 Given the BFR-prefix of a particular destination BFER, say BFER-D,
918 BFR-A learns from the routing underlay (associated with the packet's
919 sub-domain) an IP address of the BFR that is the next hop on the path
920 from BFR-A to BFER-D. Let's call this next hop "BFR-B". BFR-A must
921 then determine the BFR-prefix of BFR-B. (This determination can be
922 made from the information advertised per <a href="#section-5">Section 5</a>.) This BFR-prefix
923 is the BFR-NBR of BFR-A on the path from BFR-A to BFER-D.
924
925 Note that if the routing underlay provides multiple equal-cost paths
926 from BFR-A to BFER-D, BFR-A may have multiple BFR-NBRs for BFER-D.
927
928 Under certain circumstances, a BFR may have adjacencies (in a
929 particular routing underlay) that are not BFRs. Please see
930 <a href="#section-6.9">Section 6.9</a> for a discussion of how to handle those circumstances.
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948 <span class="grey">Wijnands, et al. Experimental [Page 17]</span></pre>
949 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span>
950 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
951
952
953 <span class="h3"><a class="selflink" id="section-6.3" href="#section-6.3">6.3</a>. The Bit Index Routing Table</span>
954
955 The "Bit Index Routing Table" (BIRT) is a table that maps from the
956 BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of
957 that BFER, and to the BFR-NBR on the path to that BFER. As an
958 example, consider the topology shown in Figure 1. In this diagram,
959 we represent the BFR-id of each BFR in the SI:xyzw form discussed in
960 <a href="#section-3">Section 3</a>.
961
962 ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
963 4 (0:1000) \ \ 1 (0:0001)
964 \ \
965 ( E ) ( F )
966 3 (0:0100) 2 (0:0010)
967
968 Figure 1: BIER Topology 1
969
970 This topology will result in the BIRT of Figure 2 at BFR-B. The
971 first column shows the BFR-id as a number and also (in parentheses)
972 in the SI:BitString format that corresponds to a BitStringLength
973 of 4. (The actual minimum BitStringLength is 64, but we use 4 in the
974 examples.)
975
976 Note that a BIRT is specific to a particular BIER sub-domain.
977
978 --------------------------------------------
979 | BFR-id | BFR-Prefix | BFR-NBR |
980 | (SI:BitString) | of Dest BFER | |
981 ============================================
982 | 4 (0:1000) | A | A |
983 --------------------------------------------
984 | 1 (0:0001) | D | C |
985 --------------------------------------------
986 | 3 (0:0100) | E | E |
987 --------------------------------------------
988 | 2 (0:0010) | F | C |
989 --------------------------------------------
990
991 Figure 2: Bit Index Routing Table at BFR-B
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004 <span class="grey">Wijnands, et al. Experimental [Page 18]</span></pre>
1005 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span>
1006 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1007
1008
1009 <span class="h3"><a class="selflink" id="section-6.4" href="#section-6.4">6.4</a>. The Bit Index Forwarding Table</span>
1010
1011 The "Bit Index Forwarding Table" (BIFT) is derived from the BIRT as
1012 follows. (Note that a BIFT is specific to a particular sub-domain.)
1013
1014 Suppose that several rows in the BIRT have the same SI and the same
1015 BFR-NBR. By taking the logical OR of the BitStrings of those rows,
1016 we obtain a bit mask that corresponds to that combination of SI and
1017 BFR-NBR. We will refer to this bit mask as the "Forwarding Bit Mask"
1018 (F-BM) for that &lt;SI, BFR-NBR&gt; combination.
1019
1020 For example, in Figure 2, we see that two of the rows have the same
1021 SI (0) and same BFR-NBR (C). The bit mask that corresponds to
1022 &lt;SI=0, BFR-NBR-C&gt; is 0011 ("0001" OR'd with "0010").
1023
1024 The BIFT is used to map from the BFR-id of a BFER to the
1025 corresponding F-BM and BFR-NBR. For example, Figure 3 shows the BIFT
1026 that is derived from the BIRT of Figure 2. Note that BFR-ids 1 and 2
1027 have the same SI and the same BFR-NBR; hence, they have the
1028 same F-BM.
1029
1030 -------------------------------------
1031 | BFR-id | F-BM | BFR-NBR |
1032 | (SI:BitString) | | |
1033 =====================================
1034 | 1 (0:0001) | 0011 | C |
1035 -------------------------------------
1036 | 2 (0:0010) | 0011 | C |
1037 -------------------------------------
1038 | 3 (0:0100) | 0100 | E |
1039 -------------------------------------
1040 | 4 (0:1000) | 1000 | A |
1041 -------------------------------------
1042
1043 Figure 3: Bit Index Forwarding Table
1044
1045 This BIFT is programmed into the data plane and used to forward
1046 packets, applying the rules specified below in <a href="#section-6.5">Section 6.5</a>.
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060 <span class="grey">Wijnands, et al. Experimental [Page 19]</span></pre>
1061 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span>
1062 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1063
1064
1065 <span class="h3"><a class="selflink" id="section-6.5" href="#section-6.5">6.5</a>. The BIER Forwarding Procedure</span>
1066
1067 Below is the procedure that a BFR uses for forwarding a
1068 BIER-encapsulated packet.
1069
1070 1. Determine the packet's SI, BitStringLength, and sub-domain.
1071
1072 2. If the BitString consists entirely of zeroes, discard the packet;
1073 the forwarding process has been completed. Otherwise, proceed to
1074 step 3.
1075
1076 3. Find the position (call it "k") of the least significant (i.e.,
1077 of the rightmost) bit that is set in the packet's BitString.
1078 (Remember, bits are numbered from 1, starting with the least
1079 significant bit.)
1080
1081 4. If bit k identifies the BFR itself, copy the packet, and send the
1082 copy to the multicast flow overlay. Then clear bit k in the
1083 original packet, and go to step 2. Otherwise, proceed to step 5.
1084
1085 5. Use the value k, together with the SI, sub-domain, and
1086 BitStringLength, as the "index" into the BIFT.
1087
1088 6. Extract from the BIFT the F-BM and the BFR-NBR.
1089
1090 7. Copy the packet. Update the copy's BitString by AND'ing it with
1091 the F-BM (i.e., PacketCopy-&gt;BitString &amp;= F-BM). Then forward the
1092 copy to the BFR-NBR. (If the BFR-NBR is null, the copy is just
1093 discarded.) Note that when a packet is forwarded to a particular
1094 BFR-NBR, its BitString identifies only those BFERs that are to be
1095 reached via that BFR-NBR.
1096
1097 8. Now update the original packet's BitString by AND'ing it with the
1098 INVERSE of the F-BM (i.e., Packet-&gt;BitString &amp;= ~F-BM). (This
1099 clears the bits that identify the BFERs to which a copy of the
1100 packet has just been forwarded.) Go to step 2.
1101
1102 This procedure causes the packet to be forwarded to a particular
1103 BFR-NBR only once. The number of lookups in the BIFT is the same as
1104 the number of BFR-NBRs to which the packet must be forwarded; it is
1105 not necessary to do a separate lookup for each destination BFER.
1106
1107 When a packet is sent to a particular BFR-NBR, the BitString is not
1108 the only part of the BIER header that needs to be modified. If there
1109 is a TTL field in the BIER header, it will need to be decremented.
1110 In addition, when either of the encapsulations of [<a href="#ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>]
1111 is used, the BIFT-id field is likely to require modification, based
1112 on signaling from the BFR-NBR to which the packet is being sent. The
1113
1114
1115
1116 <span class="grey">Wijnands, et al. Experimental [Page 20]</span></pre>
1117 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span>
1118 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1119
1120
1121 BIFT-id field of an incoming BIER packet implicitly identifies an SI,
1122 a sub-domain, and a BitStringLength. If the packet is sent to a
1123 particular BFR-NBR, the BIFT-id field must be changed to whatever
1124 value that BFR-NBR has advertised for the same SI, sub-domain, and
1125 BitStringLength. (If the encapsulation of Section 2.1 of
1126 [<a href="#ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>] is used, this is essentially an MPLS label swap
1127 operation.)
1128
1129 Suppose it has been decided (by the above rules) to send a packet to
1130 a particular BFR-NBR. If that BFR-NBR is connected via multiple
1131 parallel interfaces, it may be desirable to apply some form of load
1132 balancing. Load-balancing algorithms are outside the scope of this
1133 document. However, if the packet's encapsulation contains an entropy
1134 field, the entropy field SHOULD be respected; two packets with the
1135 same value of the entropy field SHOULD be sent on the same interface
1136 (if possible).
1137
1138 In some cases, the routing underlay may provide multiple equal-cost
1139 paths (through different BFR-NBRs) to a given BFER. This is known as
1140 "Equal-Cost Multipath" (ECMP). The procedures described in this
1141 section must be augmented in order to support load balancing over
1142 ECMP. The necessary augmentations can be found in <a href="#section-6.7">Section 6.7</a>.
1143
1144 In the event that unicast traffic to the BFR-NBR is being sent via a
1145 "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic
1146 sent to the BFR-NBR SHOULD also be sent via that tunnel. This allows
1147 any existing "fast reroute" schemes to be applied to multicast
1148 traffic as well as to unicast traffic.
1149
1150 Some examples of these forwarding procedures can be found in
1151 <a href="#section-6.6">Section 6.6</a>.
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172 <span class="grey">Wijnands, et al. Experimental [Page 21]</span></pre>
1173 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span>
1174 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1175
1176
1177 The rules given in this section can be represented by the following
1178 pseudocode:
1179
1180 void ForwardBitMaskPacket (Packet)
1181 {
1182 SI=GetPacketSI(Packet);
1183 Offset=SI*BitStringLength;
1184 for (Index = GetFirstBitPosition(Packet-&gt;BitString); Index ;
1185 Index = GetNextBitPosition(Packet-&gt;BitString, Index)) {
1186 F-BM = BIFT[Index+Offset]-&gt;F-BM;
1187 if (!F-BM) continue;
1188 BFR-NBR = BIFT[Index+Offset]-&gt;BFR-NBR;
1189 PacketCopy = Copy(Packet);
1190 PacketCopy-&gt;BitString &amp;= F-BM;
1191 PacketSend(PacketCopy, BFR-NBR);
1192 Packet-&gt;BitString &amp;= ~F-BM;
1193 }
1194 }
1195
1196 Figure 4: Pseudocode
1197
1198 This pseudocode assumes that, at a given BFER, the BFR-NBR entry
1199 corresponding to the BFER's own BFR-id will be the BFER's own
1200 BFR-prefix. It also assumes that the corresponding F-BM has only
1201 one bit set, the bit representing the BFER itself. In this case, the
1202 "PacketSend" function sends the packet to the multicast flow overlay.
1203
1204 This pseudocode also assumes that the F-BM for the null next hop
1205 contains a 1 in a given bit position if and only if that bit position
1206 corresponds to either an unused BFR-id or an unreachable BFER. When
1207 the BFR-NBR is null, the "PacketSend" function discards the packet.
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228 <span class="grey">Wijnands, et al. Experimental [Page 22]</span></pre>
1229 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span>
1230 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1231
1232
1233 <span class="h3"><a class="selflink" id="section-6.6" href="#section-6.6">6.6</a>. Examples of BIER Forwarding</span>
1234
1235 In this section, we give two examples of BIER forwarding, based on
1236 the topology in Figure 1. In these examples, all packets have been
1237 assigned to the default sub-domain, all packets have SI=0, and the
1238 BitStringLength is 4. Figure 5 shows the BIFT entries for SI=0 only.
1239 For compactness, we show the first column of the BIFT, the BFR-id,
1240 only as an integer.
1241
1242 BFR-A BIFT BFR-B BIFT BFR-C BIFT
1243 ------------------- ------------------- -------------------
1244 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR |
1245 =================== =================== ===================
1246 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D |
1247 ------------------- ------------------- -------------------
1248 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F |
1249 ------------------- ------------------- -------------------
1250 | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B |
1251 ------------------- ------------------- -------------------
1252 | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B |
1253 ------------------- ------------------- -------------------
1254
1255 Figure 5: BIFTs Used in the Forwarding Examples
1256
1257 <span class="h4"><a class="selflink" id="section-6.6.1" href="#section-6.6.1">6.6.1</a>. Example 1</span>
1258
1259 BFR-D, BFR-E, and BFR-F are BFERs. BFR-A is the BFIR. Suppose that
1260 BFIR-A has learned from the multicast flow overlay that BFER-D is
1261 interested in a given multicast flow. If BFIR-A receives a packet of
1262 that flow from outside the BIER domain, BFIR-A applies the BIER
1263 encapsulation to the packet. The encapsulation must be such that the
1264 SI is zero. The encapsulation also includes a BitString, with just
1265 bit 1 set and with all other bits clear (i.e., 0001). This indicates
1266 that BFER-D is the only BFER that needs to receive the packet.
1267 BFIR-A then follows the procedures of <a href="#section-6.5">Section 6.5</a>, as follows:
1268
1269 o Since the packet's BitString is 0001, BFIR-A finds that the first
1270 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
1271 determines that the bit mask F-BM is 0111 and the BFR-NBR is
1272 BFR-B.
1273
1274 o BFR-A then makes a copy of the packet and applies the F-BM to the
1275 copy: Copy-&gt;BitString &amp;= 0111. The copy's BitString is now 0001
1276 (0001 &amp; 0111).
1277
1278 o The copy is now sent to BFR-B.
1279
1280
1281
1282
1283
1284 <span class="grey">Wijnands, et al. Experimental [Page 23]</span></pre>
1285 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span>
1286 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1287
1288
1289 o BFR-A then updates the packet's BitString by applying the inverse
1290 of the F-BM: Packet-&gt;BitString &amp;= ~F-BM. As a result, the
1291 packet's BitString is now 0000 (0001 &amp; 1000).
1292
1293 o As the packet's BitString is now zero, the forwarding procedure is
1294 complete.
1295
1296 When BFR-B receives the multicast packet from BFR-A, it follows the
1297 same procedure. The result is that a copy of the packet, with a
1298 BitString of 0001, is sent to BFR-C. BFR-C applies the same
1299 procedures and, as a result, sends a copy of the packet, with a
1300 BitString of 0001, to BFR-D.
1301
1302 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
1303 F-BM of 0001 and a BFR-NBR of BFR-D itself. This will cause a copy
1304 of the packet to be delivered to the multicast flow overlay at BFR-D.
1305 The packet's BitString will be set to 0000, and the packet will not
1306 be forwarded any further.
1307
1308 <span class="h4"><a class="selflink" id="section-6.6.2" href="#section-6.6.2">6.6.2</a>. Example 2</span>
1309
1310 This example is similar to example 1, except that BFIR-A has learned
1311 from the multicast flow overlay that both BFER-D and BFER-E are
1312 interested in a given multicast flow. If BFIR-A receives a packet of
1313 that flow from outside the BIER domain, BFIR-A applies the BIER
1314 encapsulation to the packet. The encapsulation must be such that the
1315 SI is zero. The encapsulation also includes a BitString with
1316 two bits set: bit 1 is set (as in example 1) to indicate that BFR-D
1317 is a BFER for this packet, and bit 3 is set to indicate that BFR-E is
1318 a BFER for this packet. That is, the BitString (assuming again a
1319 BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows
1320 the procedures of <a href="#section-6.5">Section 6.5</a>, as follows:
1321
1322 o Since the packet's BitString is 0101, BFIR-A finds that the first
1323 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
1324 determines that the bit mask F-BM is 0111 and the BFR-NBR is
1325 BFR-B.
1326
1327 o BFR-A then makes a copy of the packet and applies the F-BM to the
1328 copy: Copy-&gt;BitString &amp;= 0111. The copy's BitString is now 0101
1329 (0101 &amp; 0111).
1330
1331 o The copy is now sent to BFR-B.
1332
1333
1334
1335
1336
1337
1338
1339
1340 <span class="grey">Wijnands, et al. Experimental [Page 24]</span></pre>
1341 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span>
1342 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1343
1344
1345 o BFR-A then updates the packet's BitString by applying the inverse
1346 of the F-BM: Packet-&gt;BitString &amp;= ~F-BM. As a result, the
1347 packet's BitString is now 0000 (0101 &amp; 1000).
1348
1349 o As the packet's BitString is now zero, the forwarding procedure is
1350 complete.
1351
1352 When BFR-B receives the multicast packet from BFR-A, it follows the
1353 procedure of <a href="#section-6.5">Section 6.5</a>, as follows:
1354
1355 o Since the packet's BitString is 0101, BFR-B finds that the first
1356 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-B
1357 determines that the bit mask F-BM is 0011 and the BFR-NBR is
1358 BFR-C.
1359
1360 o BFR-B then makes a copy of the packet and applies the F-BM to the
1361 copy: Copy-&gt;BitString &amp;= 0011. The copy's BitString is now 0001
1362 (0101 &amp; 0011).
1363
1364 o The copy is now sent to BFR-C.
1365
1366 o BFR-B then updates the packet's BitString by applying the inverse
1367 of the F-BM: Packet-&gt;BitString &amp;= ~F-BM. As a result, the
1368 packet's BitString is now 0100 (0101 &amp; 1100).
1369
1370 o Now BFR-B finds the next bit in the packet's (modified) BitString.
1371 This is bit 3. Looking at entry 3 in its BIFT, BFR-B determines
1372 that the F-BM is 0100 and the BFR-NBR is BFR-E.
1373
1374 o BFR-B then makes a copy of the packet and applies the F-BM to the
1375 copy: Copy-&gt;BitString &amp;= 0100. The copy's BitString is now 0100
1376 (0100 &amp; 0100).
1377
1378 o The copy is now sent to BFR-E.
1379
1380 o BFR-B then updates the packet's BitString by applying the inverse
1381 of the F-BM: Packet-&gt;BitString &amp;= ~F-BM. As a result, the
1382 packet's BitString is now 0000 (0100 &amp; 1011).
1383
1384 o As the packet's BitString is now zero, the forwarding procedure is
1385 complete.
1386
1387 Thus, BFR-B forwards two copies of the packet. One copy of the
1388 packet, with BitString 0001, has now been sent from BFR-B to BFR-C.
1389 Following the same procedures, BFR-C will forward the packet to
1390 BFER-D.
1391
1392
1393
1394
1395
1396 <span class="grey">Wijnands, et al. Experimental [Page 25]</span></pre>
1397 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span>
1398 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1399
1400
1401 At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
1402 F-BM of 0001 and a BFR-NBR of BFR-D itself. This will cause a copy
1403 of the packet to be delivered to the multicast flow overlay at BFR-D.
1404 The packet's BitString will be set to 0000, and the packet will not
1405 be forwarded any further.
1406
1407 The other copy of the packet has been sent from BFR-B to BFER-E, with
1408 BitString 0100.
1409
1410 At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an
1411 F-BM of 0100 and a BFR-NBR of BFR-E itself. This will cause a copy
1412 of the packet to be delivered to the multicast flow overlay at BFR-E.
1413 The packet's BitString will be set to 0000, and the packet will not
1414 be forwarded any further.
1415
1416 <span class="h3"><a class="selflink" id="section-6.7" href="#section-6.7">6.7</a>. Equal-Cost Multipath Forwarding</span>
1417
1418 In many networks, the routing underlay will provide multiple
1419 equal-cost paths from a given BFR to a given BFER. When forwarding
1420 multicast packets through the network, it can be beneficial to take
1421 advantage of this by load-balancing among those paths. This feature
1422 is known as "Equal-Cost Multipath (ECMP) forwarding".
1423
1424 BIER supports ECMP forwarding, but the procedures of <a href="#section-6.5">Section 6.5</a> must
1425 be modified slightly. Two ECMP procedures are defined. In the first
1426 (described in <a href="#section-6.7.1">Section 6.7.1</a>), the choice among equal-cost paths taken
1427 by a given packet from a given BFR to a given BFER depends on
1428 (a) routing, (b) the packet's entropy, and (c) the other BFERs to
1429 which that packet is destined. In the second (described in
1430 <a href="#section-6.7.2">Section 6.7.2</a>), the choice depends only upon the packet's entropy.
1431
1432 There are trade-offs between the two forwarding procedures described
1433 here. In the procedure of <a href="#section-6.7.1">Section 6.7.1</a>, the number of packet
1434 replications is minimized. The procedure in <a href="#section-6.7.1">Section 6.7.1</a> also uses
1435 less memory in the BFR. In the procedure of <a href="#section-6.7.2">Section 6.7.2</a>, the path
1436 traveled by a given packet from a given BFR to a given BFER is
1437 independent of the other BFERs to which the packet is destined.
1438 While the procedures of <a href="#section-6.7.2">Section 6.7.2</a> may cause more replications,
1439 they provide a more predictable behavior.
1440
1441 The two procedures described here operate on identical packet formats
1442 and will interoperate correctly. However, if deterministic behavior
1443 is desired, then all BFRs would need to use the procedure from
1444 <a href="#section-6.7.2">Section 6.7.2</a>.
1445
1446
1447
1448
1449
1450
1451
1452 <span class="grey">Wijnands, et al. Experimental [Page 26]</span></pre>
1453 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span>
1454 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1455
1456
1457 <span class="h4"><a class="selflink" id="section-6.7.1" href="#section-6.7.1">6.7.1</a>. Non-deterministic ECMP</span>
1458
1459 Figure 6 shows the operation of non-deterministic ECMP in BIER.
1460
1461 BFR-A BIFT BFR-B BIFT BFR-C BIFT
1462 ------------------- ------------------- -------------------
1463 | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR |
1464 =================== =================== ===================
1465 | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D |
1466 ------------------- ------------------- -------------------
1467 | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F |
1468 ------------------- | | 0110 | E | -------------------
1469 | 3 | 0111 | B | ------------------- | 3 | 1100 | B |
1470 ------------------- | 3 | 0110 | E | -------------------
1471 | 4 | 1000 | A | ------------------| | 4 | 1100 | B |
1472 ------------------- | 4 | 1000 | A | -------------------
1473 -------------------
1474
1475 ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
1476 4 (0:1000) \ \ 1 (0:0001)
1477 \ \
1478 ( E ) ------------ ( F )
1479 3 (0:0100) 2 (0:0010)
1480
1481 Figure 6: Example of Non-deterministic ECMP
1482
1483 In this example, BFR-B has two equal-cost paths to reach BFER-F: one
1484 via BFR-C and one via BFR-E. Since the BFR-id of BFER-F is 2, this
1485 is reflected in entry 2 of BFR-B's BIFT. Entry 2 shows that BFR-B
1486 has a choice of two BFR-NBRs for BFER-B and that a different F-BM is
1487 associated with each choice. When BFR-B looks up entry 2 in the
1488 BIFT, it can choose either BFR-NBR. However, when following the
1489 procedures of <a href="#section-6.5">Section 6.5</a>, it MUST use the F-BM corresponding to the
1490 BFR-NBR that it chooses.
1491
1492 How the choice is made is an implementation matter. However, the
1493 usual rules for ECMP apply: packets of a given flow SHOULD NOT be
1494 split among two paths, and any entropy field in the packet's
1495 encapsulation SHOULD be respected.
1496
1497 Note, however, that by the rules of <a href="#section-6.5">Section 6.5</a>, any packet destined
1498 for both BFER-D and BFER-F will be sent via BFR-C.
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508 <span class="grey">Wijnands, et al. Experimental [Page 27]</span></pre>
1509 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-28" ></span>
1510 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1511
1512
1513 <span class="h4"><a class="selflink" id="section-6.7.2" href="#section-6.7.2">6.7.2</a>. Deterministic ECMP</span>
1514
1515 With the procedures of <a href="#section-6.7.1">Section 6.7.1</a>, where ECMP paths exist, the
1516 path a packet takes to reach any particular BFER depends not only on
1517 routing and on the packet's entropy but also on the set of other
1518 BFERs to which the packet is destined.
1519
1520 For example, consider the following scenario in the network of
1521 Figure 6.
1522
1523 o There is a sequence of packets being transmitted by BFR-A, some of
1524 which are destined for both D and F and some of which are destined
1525 only for F.
1526
1527 o All the packets in this sequence have the same entropy value (call
1528 it "Q").
1529
1530 o At BFR-B, when a packet with entropy value Q is forwarded via
1531 entry 2 in the BIFT, the packet is sent to E.
1532
1533 Using the forwarding procedure of <a href="#section-6.7.1">Section 6.7.1</a>, packets of this
1534 sequence that are destined for both D and F are forwarded according
1535 to entry 1 in the BIFT and thus will reach F via the path A-B-C-F.
1536 However, packets of this sequence that are destined only for F are
1537 forwarded according to entry 2 in the BIFT and thus will reach F via
1538 the path A-B-E-F.
1539
1540 That procedure minimizes the number of packets transmitted by BFR-B.
1541 However, consider the following scenario:
1542
1543 o Beginning at time t0, the multicast flow in question needs to be
1544 received ONLY by BFER-F.
1545
1546 o Beginning at a later time, t1, the flow needs to be received by
1547 both BFER-D and BFER-F.
1548
1549 o Beginning at a later time, t2, the flow no longer needs to be
1550 received by D, but still needs to be received by F.
1551
1552 Then, from t0 until t1, the flow will travel to F via the path
1553 A-B-E-F. From t1 until t2, the flow will travel to F via the path
1554 A-B-C-F. And from t2, the flow will again travel to F via the path
1555 A-B-E-F.
1556
1557 The problem is that if D repeatedly joins and leaves the flow, the
1558 flow's path from B to F will keep switching. This could cause F to
1559 receive packets out of order. It also makes troubleshooting
1560 difficult. For example, if there is some problem on the E-F link,
1561
1562
1563
1564 <span class="grey">Wijnands, et al. Experimental [Page 28]</span></pre>
1565 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-29" ></span>
1566 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1567
1568
1569 receivers at F will get good service when the flow is also going to D
1570 (avoiding the E-F link) but bad service when the flow is not going
1571 to D. Since it is hard to know which path is being used at any given
1572 time, this may be hard to troubleshoot. Also, it is very difficult
1573 to perform a traceroute that is known to follow the path taken by the
1574 flow at any given time.
1575
1576 The source of this difficulty is that, in the procedures of
1577 <a href="#section-6.7.1">Section 6.7.1</a>, the path taken by a particular flow to a particular
1578 BFER depends upon whether there are lower-numbered BFERs that are
1579 also receiving the flow. Thus, the choice among the ECMP paths is
1580 fundamentally non-deterministic.
1581
1582 Deterministic forwarding can be achieved by using multiple BIFTs,
1583 such that each row in a BIFT has only one path to each destination
1584 but the multiple ECMP paths to any particular destination are spread
1585 across the multiple tables. When a BIER-encapsulated packet arrives
1586 to be forwarded, the BFR uses a hash of the BIER entropy field to
1587 determine which BIFT to use, and then the normal BIER forwarding
1588 algorithm (as described in Sections <a href="#section-6.5">6.5</a> and <a href="#section-6.6">6.6</a>) is used with the
1589 selected BIFT.
1590
1591 As an example, suppose there are two paths to destination X (call
1592 them "X1" and "X2") and four paths to destination Y (call them "Y1",
1593 "Y2", "Y3", and "Y4"). If there are, say, four BIFTs, one BIFT would
1594 have paths X1 and Y1, one would have X1 and Y2, one would have X2 and
1595 Y3, and one would have X2 and Y4. If traffic to X is split evenly
1596 among these four BIFTs, the traffic will be split evenly between the
1597 two paths to X; if traffic to Y is split evenly among these four
1598 BIFTs, the traffic will be split evenly between the four paths to Y.
1599
1600 Note that if there are three paths to one destination and four paths
1601 to another, 12 BIFTs would be required in order to get even splitting
1602 of the load to each of those two destinations. Of course, each BIFT
1603 uses some memory, and one might be willing to have less optimal
1604 splitting in order to have fewer BIFTs. How that trade-off is made
1605 is an implementation or deployment decision.
1606
1607 <span class="h3"><a class="selflink" id="section-6.8" href="#section-6.8">6.8</a>. Prevention of Loops and Duplicates</span>
1608
1609 The BitString in a BIER-encapsulated packet specifies the set of
1610 BFERs to which that packet is to be forwarded. When a
1611 BIER-encapsulated packet is replicated, no two copies of the packet
1612 will ever have a BFER in common. If one of the packet's BFERs
1613 forwards the packet further, that BFER will first clear the bit that
1614 identifies itself. As a result, duplicate delivery of packets is not
1615 possible with BIER.
1616
1617
1618
1619
1620 <span class="grey">Wijnands, et al. Experimental [Page 29]</span></pre>
1621 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-30" ></span>
1622 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1623
1624
1625 As long as the routing underlay provides a loop-free path between
1626 each pair of BFRs, BIER-encapsulated packets will not loop. Since
1627 the BIER layer does not create any paths of its own, there is no need
1628 for any BIER-specific loop-prevention techniques beyond the
1629 forwarding procedures specified in <a href="#section-6.5">Section 6.5</a>.
1630
1631 If, at some time, the routing underlay is not providing a loop-free
1632 path between BFIR-A and BFER-B, then BIER-encapsulated packets may
1633 loop while traveling from BFIR-A to BFER-B. However, such loops will
1634 never result in delivery of duplicate packets to BFER-B.
1635
1636 These properties of BIER eliminate the need for the "Reverse Path
1637 Forwarding" (RPF) check that is used in conventional IP multicast
1638 forwarding.
1639
1640 <span class="h3"><a class="selflink" id="section-6.9" href="#section-6.9">6.9</a>. When Some Nodes Do Not Support BIER</span>
1641
1642 The procedures of <a href="#section-6.2">Section 6.2</a> presuppose that, within a given BIER
1643 domain, all the nodes adjacent to a given BFR in a given routing
1644 underlay are also BFRs. However, it is possible to use BIER even
1645 when this is not the case, as long as the ingress and egress nodes
1646 are BFRs. In this section, we describe procedures that can be used
1647 if the routing underlay is an SPF-based IGP that computes a
1648 shortest-path tree from each node to all other nodes in the domain.
1649
1650 At a given BFR, say "BFR-B", start with a copy of the IGP-computed
1651 shortest-path tree from BFR-B to each router in the domain. (This
1652 tree is computed by the SPF algorithm of the IGP.) Let's call this
1653 copy the "BIER-SPF tree rooted at BFR-B". BFR-B then modifies this
1654 BIER-SPF tree as follows.
1655
1656 1. BFR-B looks in turn at each of its child nodes on the BIER-SPF
1657 tree.
1658
1659 2. If one of the child nodes does not support BIER, BFR-B removes
1660 that node from the tree. The child nodes of the node that has
1661 just been removed are then re-parented on the tree, so that BFR-B
1662 now becomes their parent.
1663
1664 3. BFR-B then continues to look at each of its child nodes,
1665 including any nodes that have been re-parented to BFR-B as a
1666 result of the previous step.
1667
1668 When all of the child nodes (the original child nodes plus any new
1669 ones) have been examined, BFR-B's children on the BIER-SPF tree will
1670 all be BFRs.
1671
1672
1673
1674
1675
1676 <span class="grey">Wijnands, et al. Experimental [Page 30]</span></pre>
1677 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-31" ></span>
1678 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1679
1680
1681 When the BIFT is constructed, BFR-B's child nodes on the BIER-SPF
1682 tree are considered to be the BFR-NBRs. The F-BMs must be computed
1683 appropriately, based on the BFR-NBRs.
1684
1685 BFR-B may now have BFR-NBRs that are not "directly connected" to
1686 BFR-B via Layer 2. To send a packet to one of these BFR-NBRs, BFR-B
1687 will have to send the packet through a unicast tunnel. In an MPLS
1688 network, this may be as simple as finding the IGP unicast next hop to
1689 the child node and pushing on (above the BIER encapsulation header)
1690 an MPLS label that the IGP next hop has bound to an address of the
1691 child node. (This assumes that the packet is using an MPLS-based
1692 BIER encapsulation, such as the one specified in Section 2.1 of
1693 [<a href="#ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>].) Of course, the BIFT-id in the BIER
1694 encapsulation header must be the BIFT-id advertised by the child node
1695 for the packet's SI, sub-domain, and BitStringLength.
1696
1697 If for some reason the unicast tunnel cannot be an MPLS tunnel, any
1698 other kind of tunnel can be used, as long as the encapsulation for
1699 that tunnel type has a way of indicating that the payload is a
1700 BIER-encapsulated packet.
1701
1702 Note that if a BIER-encapsulated packet is not using an MPLS-based
1703 BIER encapsulation, it will not be possible to send it through an
1704 MPLS tunnel unless it is known that the tunnel only carries BIER
1705 packets; this is because MPLS has no "next protocol type" field.
1706 This is not a problem if an MPLS-based BIER encapsulation is used,
1707 because in that case the BIER encapsulation begins with an MPLS label
1708 that identifies the packet as a BIER-encapsulated packet.
1709
1710 Of course, the above is not meant as an implementation technique,
1711 just as a functional description.
1712
1713 While the above description assumes that the routing underlay
1714 provides an SPF tree, it may also be applicable to other types of
1715 routing underlays.
1716
1717 The technique above can also be used to provide "node protection"
1718 (i.e., to provide fast reroute around nodes that are believed to have
1719 failed). If BFR-B has a failed BFR-NBR, BFR-B can remove the failed
1720 BFR-NBR from the BIER-SPF tree and can then re-parent the child
1721 BFR-NBRs of the failed BFR-NBR so that they appear to be BFR-B's own
1722 child nodes on the tree (i.e., so that they appear to be BFR-B's
1723 BFR-NBRs). The usual BIER forwarding procedures then apply.
1724 However, getting the packet from BFR-B to the child nodes of the
1725 failed BFR-NBR is a bit more complicated, as it may require using a
1726 unicast bypass tunnel to get around the failed node.
1727
1728
1729
1730
1731
1732 <span class="grey">Wijnands, et al. Experimental [Page 31]</span></pre>
1733 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-32" ></span>
1734 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1735
1736
1737 A simpler variant of step 2 above would be the following:
1738
1739 If one of the child nodes does not support BIER, BFR-B removes
1740 that node from the tree. All BFERs that are reached through that
1741 child node are then re-parented on the tree, so that BFR-B now
1742 becomes their parent.
1743
1744 This variant is simpler because the set of BFERs that are reached
1745 through a particular child node of BFR-B can be determined from the
1746 F-BM in the BIFT. However, if this variant is used, the results are
1747 less optimal, because packets will be unicast directly from BFR-B to
1748 the BFERs that are reachable through the non-BIER child node.
1749
1750 When using a unicast MPLS tunnel to get a packet to a BFR-NBR:
1751
1752 o The TTL of the MPLS label entry representing the tunnel SHOULD be
1753 set to a large value, rather than being copied from the TTL value
1754 from the BIER encapsulation header, and
1755
1756 o When the tunnel labels are popped off, the TTL from the tunnel
1757 labels SHOULD NOT be copied to the BIER encapsulation header.
1758
1759 In other words, the TTL processing for the tunnel SHOULD be as
1760 specified in [<a href="./rfc3443" title="&quot;Time To Live (TTL) Processing in Multi-Protocol Label Switching (MPLS) Networks&quot;">RFC3443</a>] for "Pipe Model" and "Short Pipe Model" Label
1761 Switched Paths (LSPs). The same principle applies if the tunnels are
1762 not MPLS tunnels; the BIER packet SHOULD NOT inherit the TTL from the
1763 tunnel encapsulation. That way, the TTL of the BIER encapsulation
1764 header constrains only the number of BFRs that the packet may
1765 traverse, not the total number of hops.
1766
1767 If two BIER packets have the same value in the entropy field of their
1768 respective BIER headers and if both are transmitted through a given
1769 tunnel, it is desirable for the tunnel encapsulation to preserve the
1770 fact that the two packets have the same entropy.
1771
1772 The material in this section presupposes that if a given router is a
1773 BFR, then it supports BIER on all its interfaces. It is, however,
1774 possible that a router will have some line cards that support BIER
1775 and some that do not. In such a case, one can think of the router as
1776 a "partial BFR" that supports BIER only on some of its interfaces.
1777 If it is desired to deploy such partial BFRs, one can use the
1778 multi-topology features of the IGP to set up a BIER-specific
1779 topology. This topology would exclude all the non-BIER-capable
1780 interfaces that attach to BFRs. BIER would then have to be run in a
1781 sub-domain that is bound to this topology. If unicast tunnels are
1782 used to bypass non-BFRs, either (a) the tunnels have to be restricted
1783 to this topology or (b) the tunnel endpoints have to be BFRs that do
1784 not have any non-BIER-capable interfaces.
1785
1786
1787
1788 <span class="grey">Wijnands, et al. Experimental [Page 32]</span></pre>
1789 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-33" ></span>
1790 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1791
1792
1793 <span class="h3"><a class="selflink" id="section-6.10" href="#section-6.10">6.10</a>. Use of Different BitStringLengths within a Domain</span>
1794
1795 The procedures of this section apply only when the same encapsulation
1796 is used throughout the BIER domain. Consideration of the scenario
1797 where both multiple encapsulations and multiple BitStringLengths are
1798 used in a given BIER domain is outside the scope of this document.
1799
1800 It is possible for different BFRs within a BIER domain to be using
1801 different Imposition and/or Disposition BitStringLengths. As stated
1802 in <a href="#section-3">Section 3</a>:
1803
1804 "if a particular BFIR is provisioned to use a particular Imposition
1805 BitStringLength and a particular Imposition sub-domain when imposing
1806 the encapsulation on a given set of packets, all other BFRs with
1807 BFR-ids in that sub-domain SHOULD be provisioned to process received
1808 BIER packets with that BitStringLength (i.e., all other BFRs with
1809 BFR-ids in that sub-domain SHOULD be provisioned with that
1810 BitStringLength as a Disposition BitStringLength for that
1811 sub-domain)."
1812
1813 Note that mis-provisioning can result in "black holes". If a BFIR
1814 creates a BIER packet with a particular BitStringLength and if that
1815 packet needs to travel through a BFR that cannot process received
1816 BIER packets with that BitStringLength, then it may be impossible to
1817 forward the packet to all of the BFERs identified in its BIER header.
1818 <a href="#section-6.10.1">Section 6.10.1</a> defines a procedure, the "BitStringLength
1819 Compatibility Check", that can be used to detect the possibility of
1820 such black holes.
1821
1822 However, failure of the BitStringLength Compatibility Check does not
1823 necessarily result in the creation of black holes; <a href="#section-6.10.2">Section 6.10.2</a>
1824 specifies OPTIONAL procedures that allow BIER forwarding to proceed
1825 without black holes, even if the BitStringLength Compatibility Check
1826 fails.
1827
1828 If the procedures of <a href="#section-6.10.2">Section 6.10.2</a> are not deployed but the
1829 BitStringLength Compatibility Check fails at some BFIR, the BFIR has
1830 two choices:
1831
1832 o Create BIER packets with the provisioned Imposition
1833 BitStringLength, even though the packets may not be able to reach
1834 all the BFERs identified in their BitStrings.
1835
1836 o Use an Imposition BitStringLength that passes the Compatibility
1837 Check (assuming that there is one), even if this is not the
1838 provisioned Imposition BitStringLength.
1839
1840
1841
1842
1843
1844 <span class="grey">Wijnands, et al. Experimental [Page 33]</span></pre>
1845 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-34" ></span>
1846 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1847
1848
1849 <a href="#section-6.10.1">Section 6.10.1</a> discusses the implications of making one or the other
1850 of these choices.
1851
1852 There will be times when an operator wishes to change the
1853 BitStringLengths used in a particular BIER domain. <a href="#section-6.10.3">Section 6.10.3</a>
1854 specifies a simple procedure that can be used to transition a BIER
1855 domain from one BitStringLength to another.
1856
1857 <span class="h4"><a class="selflink" id="section-6.10.1" href="#section-6.10.1">6.10.1</a>. BitStringLength Compatibility Check</span>
1858
1859 When a BFIR needs to encapsulate a packet, the BFIR first assigns the
1860 packet to a sub-domain. The BFIR then chooses an Imposition
1861 BitStringLength L for the packet. The choice of Imposition
1862 BitStringLength is determined by provisioning. However, the BFIR
1863 should also perform the BitStringLength Compatibility Check defined
1864 below.
1865
1866 The combination of sub-domain S and Imposition BitStringLength L
1867 passes the BitStringLength Compatibility Check if and only if the
1868 following condition holds:
1869
1870 Every BFR that has advertised its membership in sub-domain S has
1871 also advertised that it is using Disposition BitStringLength L
1872 (and possibly other BitStringLengths as well) in that sub-domain.
1873 (If MPLS encapsulation (Section 2.1 of [<a href="#ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>]) is
1874 being used, this means that every BFR that is advertising a label
1875 for sub-domain S is advertising a label for the combination of
1876 sub-domain S and Disposition BitStringLength L.)
1877
1878 If a BFIR has been provisioned to use a particular Imposition
1879 BitStringLength and a particular sub-domain for some set of packets,
1880 and if that combination of Imposition BitStringLength and sub-domain
1881 does not pass the BitStringLength Compatibility Check, the BFIR
1882 SHOULD log this fact as an error. It then has the following two
1883 choices about what to do with the packets:
1884
1885 1. The BFIR MAY use the provisioned Imposition BitStringLength
1886 anyway. If the procedure of either option 2 or option 3 of
1887 <a href="#section-6.10.2">Section 6.10.2</a> is deployed, this will not cause black holes and
1888 may actually be the optimal result. It should be understood,
1889 though, that the BFIR cannot determine by signaling whether those
1890 procedures have been deployed.
1891
1892 2. If the BFIR is capable of using an Imposition BitStringLength
1893 that does pass the BitStringLength Compatibility Check for the
1894 particular sub-domain, the BFIR MAY use that Imposition
1895 BitStringLength instead.
1896
1897
1898
1899
1900 <span class="grey">Wijnands, et al. Experimental [Page 34]</span></pre>
1901 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-35" ></span>
1902 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1903
1904
1905 Which of these two choices to make is itself determined by
1906 provisioning.
1907
1908 Note that discarding the packets is not one of the allowable choices.
1909 Suppose, for example, that all the BFIRs are provisioned to use
1910 Imposition BitStringLength L for a particular sub-domain S but one
1911 BFR has not been provisioned to use Disposition BitStringLength L for
1912 sub-domain S. This will cause the BitStringLength Compatibility
1913 Check to fail. If the BFIR sends packets with BitStringLength L and
1914 sub-domain S, the mis-provisioned BFR will not be able to forward
1915 those packets, and thus the packets may only be able to reach a
1916 subset of the BFERs to which they are destined. However, this is
1917 still better than having the BFIRs drop the packets; if the BFIRs
1918 discard the packets, the packets won't reach any of the BFERs to
1919 which they are destined at all.
1920
1921 If the procedures of <a href="#section-6.10.2">Section 6.10.2</a> have not been deployed, choice 2
1922 above might seem like a better option. However, there might not be
1923 any Imposition BitStringLength that a given BFIR can use that also
1924 passes the BitStringLength Compatibility Check. If it is desired to
1925 use choice 2 in a particular deployment, then there should be a
1926 "Fallback Disposition BitStringLength" (call it "F") such that:
1927
1928 o Every BFR advertises that it uses BitStringLength F as a
1929 Disposition BitStringLength for every sub-domain, and
1930
1931 o If a BFIR is provisioned to use Imposition BitStringLength X and
1932 Imposition sub-domain S for a certain class of packets but the
1933 BitStringLength Compatibility Check fails for the combination of
1934 BitStringLength X and sub-domain S, then the BFIR will fall back
1935 to using BitStringLength F as the Imposition BitStringLength
1936 whenever the Imposition sub-domain is S.
1937
1938 It is RECOMMENDED that the value of F be the default BitStringLength
1939 for the encapsulation being used.
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956 <span class="grey">Wijnands, et al. Experimental [Page 35]</span></pre>
1957 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-36" ></span>
1958 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
1959
1960
1961 <span class="h4"><a class="selflink" id="section-6.10.2" href="#section-6.10.2">6.10.2</a>. Handling BitStringLength Mismatches</span>
1962
1963 Suppose that a packet has been BIER-encapsulated with a
1964 BitStringLength value of X and that the packet has arrived at BFR-A.
1965 Now suppose that according to the routing underlay the next hop is
1966 BFR-B, but BFR-B is not using X as one of its Disposition
1967 BitStringLengths. What should BFR-A do with the packet? BFR-A has
1968 three options. It MUST do one of the three, but the choice of which
1969 procedure to follow is a local matter. The three options are:
1970
1971 1. BFR-A MAY discard the packet.
1972
1973 2. BFR-A MAY re-encapsulate the packet, using a BIER header whose
1974 BitStringLength value is supported by BFR-B.
1975
1976 Note that if BFR-B only uses Disposition BitStringLength values
1977 that are smaller than the BitStringLength value of the packet,
1978 this may require creating additional copies of the packet.
1979 Whether additional copies actually have to be created depends
1980 upon the bits that are actually set in the original packet's
1981 BitString.
1982
1983 3. BFR-A MAY treat BFR-B as if BFR-B did not support BIER at all,
1984 in which case BFR-A applies the rules of <a href="#section-6.9">Section 6.9</a>.
1985
1986 Note that there is no signaling that enables a BFR to advertise which
1987 of the three options it will use.
1988
1989 Option 2 can be useful if there is a region of the BIER domain where
1990 the BFRs are capable of using a long BitStringLength as well as a
1991 region where the BFRs are only capable of using a shorter
1992 BitStringLength.
1993
1994 <span class="h4"><a class="selflink" id="section-6.10.3" href="#section-6.10.3">6.10.3</a>. Transitioning from One BitStringLength to Another</span>
1995
1996 Suppose one wants to migrate the BitStringLength used in a particular
1997 BIER domain from one value (X) to another value (Y). The following
1998 migration procedure can be used. This procedure allows the BFRs to
1999 be reprovisioned one at a time and does not require a "flag day".
2000
2001 1. Upgrade all the BFRs in the domain so that they use both value X
2002 and value Y as their Disposition BitStringLengths.
2003
2004 2. Reprovision the BFIRs so that they use BitStringLength value Y as
2005 the Imposition BitStringLength.
2006
2007 3. One may then optionally reprovision all the BFRs so that they no
2008 longer use Disposition BitStringLength X.
2009
2010
2011
2012 <span class="grey">Wijnands, et al. Experimental [Page 36]</span></pre>
2013 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-37" ></span>
2014 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2015
2016
2017 <span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Operational Considerations</span>
2018
2019 BIER offers a radical simplification over current IP multicast
2020 operations: no tree-building control plane, no per-flow forwarding
2021 state, no Reverse Path Forwarding (RPF), no Rendezvous Point (RP),
2022 etc. BIER packet forwarding/replication is along the unicast paths
2023 to each bit position set in the packet, ensuring that the
2024 encapsulated multicast packets follow the same path as unicast to
2025 each set bit in the header. The BIER FIB can be derived from the
2026 SPF-calculated unicast FIB or from any other forwarding-path
2027 calculation in or out of band. Each bit will follow this unicast
2028 path from the entry point of the BIER domain to the edge device with
2029 that assigned bit.
2030
2031 Due to these differences, operational expectations from traditional
2032 multicast solutions do not apply to a BIER domain. There is no
2033 granular per-flow state at each node defining a tree. Monitoring
2034 flows at the forwarding-plane level ((S,G) entries) is not provided
2035 in a BIER node. BIER FIB packet counters may be maintained for
2036 BFR-ids or next-hop neighbors. Any flow-based metrics will require
2037 deeper packet inspection; this topic is outside the scope of this
2038 document. In this way, BIER is again more like unicast.
2039
2040 It is this reduction in state that allows for one of the key
2041 operational benefits of BIER: deterministic convergence. The BIER
2042 FIB can converge immediately after the unicast FIB regardless of how
2043 many multicast flows are transiting the links. Careful monitoring of
2044 (S,G) utilization is not required within a BIER domain.
2045
2046 <span class="h3"><a class="selflink" id="section-7.1" href="#section-7.1">7.1</a>. Configuration</span>
2047
2048 A BIER domain requires that each edge node (BFER) be given a unique
2049 bit position in the BIER mask (BFR-id). The BFR-id must be
2050 configured on each BFER and associated with a unique IP address of
2051 that BFER. Any existing manual or automated configuration tools must
2052 provide access to BIER-specific configuration. The association of
2053 the BFR-id with a unique address of the BFER to which it is assigned
2054 must also be advertised into the IGP of the BIER domain. This may be
2055 implied from the BIER configuration or require IGP-specific
2056 configuration. This document does not dictate any specific
2057 configuration methodology.
2058
2059 <span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. IANA Considerations</span>
2060
2061 This document does not require any IANA actions.
2062
2063
2064
2065
2066
2067
2068 <span class="grey">Wijnands, et al. Experimental [Page 37]</span></pre>
2069 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-38" ></span>
2070 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2071
2072
2073 <span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. Security Considerations</span>
2074
2075 When BIER is paired with a particular multicast flow overlay, it
2076 inherits the security considerations of that layer. Similarly, when
2077 BIER is paired with a particular routing underlay, it inherits the
2078 security considerations of that layer.
2079
2080 If the BIER encapsulation of a particular packet specifies an SI or a
2081 BitString other than the one intended by the BFIR, the packet is
2082 likely to be misdelivered. If the BIER encapsulation of a packet is
2083 modified (through error or malfeasance) in a way other than that
2084 specified in this document, the packet may be misdelivered. Some
2085 modifications of the BIER encapsulation, e.g., setting every bit in
2086 the BitString, may result in (intentional or unintentional)
2087 denial-of-service (DoS) attacks.
2088
2089 If a BFIR is compromised, it may impose a BIER encapsulation with all
2090 the bits in the BitString set; this would also result in a DoS
2091 attack.
2092
2093 Every BFR MUST be provisioned to know which of its interfaces lead to
2094 a BIER domain and which do not. BIER-encapsulated packets MUST NOT
2095 be accepted from outside the BIER domain. (Reception of
2096 BIER-encapsulated packets from outside the BIER domain would create
2097 an attack vector for DoS attacks, as an attacker might set all the
2098 bits in the BitString.)
2099
2100 If two interfaces lead to different BIER domains, the BFR MUST be
2101 provisioned to know that those two interfaces lead to different BIER
2102 domains. If the provisioning is not correct, BIER-encapsulated
2103 packets from one BIER domain may "leak" into another; this is likely
2104 to result in misdelivery of packets.
2105
2106 DoS attacks may also result from incorrect provisioning (through
2107 error or malfeasance) of the BFRs.
2108
2109 If the procedures used for advertising BFR-ids and BFR-prefixes are
2110 not secure, an attack on those procedures may result in incorrect
2111 delivery of BIER-encapsulated packets.
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124 <span class="grey">Wijnands, et al. Experimental [Page 38]</span></pre>
2125 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-39" ></span>
2126 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2127
2128
2129 <span class="h2"><a class="selflink" id="section-10" href="#section-10">10</a>. References</span>
2130
2131 <span class="h3"><a class="selflink" id="section-10.1" href="#section-10.1">10.1</a>. Normative References</span>
2132
2133 [<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate
2134 Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>,
2135 DOI 10.17487/RFC2119, March 1997,
2136 &lt;<a href="https://www.rfc-editor.org/info/rfc2119">https://www.rfc-editor.org/info/rfc2119</a>&gt;.
2137
2138 [<a id="ref-RFC3443">RFC3443</a>] Agarwal, P. and B. Akyol, "Time To Live (TTL) Processing
2139 in Multi-Protocol Label Switching (MPLS) Networks",
2140 <a href="./rfc3443">RFC 3443</a>, DOI 10.17487/RFC3443, January 2003,
2141 &lt;<a href="https://www.rfc-editor.org/info/rfc3443">https://www.rfc-editor.org/info/rfc3443</a>&gt;.
2142
2143 [<a id="ref-RFC8174">RFC8174</a>] Leiba, B., "Ambiguity of Uppercase vs Lowercase in
2144 <a href="./rfc2119">RFC 2119</a> Key Words", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc8174">RFC 8174</a>,
2145 DOI 10.17487/RFC8174, May 2017,
2146 &lt;<a href="https://www.rfc-editor.org/info/rfc8174">https://www.rfc-editor.org/info/rfc8174</a>&gt;.
2147
2148 <span class="h3"><a class="selflink" id="section-10.2" href="#section-10.2">10.2</a>. Informative References</span>
2149
2150 [<a id="ref-BGP_BIER_EXTENSIONS">BGP_BIER_EXTENSIONS</a>]
2151 Xu, X., Ed., Chen, M., Patel, K., Wijnands, IJ., and A.
2152 Przygienda, "BGP Extensions for BIER", Work in Progress,
2153 <a href="./draft-ietf-bier-idr-extensions-03">draft-ietf-bier-idr-extensions-03</a>, August 2017.
2154
2155 [<a id="ref-BIER_MVPN">BIER_MVPN</a>]
2156 Rosen, E., Ed., Sivakumar, M., Aldrin, S., Dolganow, A.,
2157 and T. Przygienda, "Multicast VPN Using BIER", Work in
2158 Progress, <a href="./draft-ietf-bier-mvpn-09">draft-ietf-bier-mvpn-09</a>, November 2017.
2159
2160 [<a id="ref-Boivie_Feldman">Boivie_Feldman</a>]
2161 Boivie, R. and N. Feldman, <a style="text-decoration: none" href='https://www.google.com/search?sitesearch=datatracker.ietf.org%2Fdoc%2Fhtml%2F&amp;q=inurl:draft-+%22Small+Group+Multicast%22'>"Small Group Multicast"</a>, Work
2162 in Progress, <a href="./draft-boivie-sgm-02">draft-boivie-sgm-02</a>, February 2001.
2163
2164 [<a id="ref-ISIS_BIER_EXTENSIONS">ISIS_BIER_EXTENSIONS</a>]
2165 Ginsberg, L., Ed., Przygienda, A., Aldrin, S., and J.
2166 Zhang, "BIER Support via ISIS", Work in Progress,
2167 <a href="./draft-ietf-bier-isis-extensions-06">draft-ietf-bier-isis-extensions-06</a>, October 2017.
2168
2169 [<a id="ref-MPLS_BIER_ENCAPS">MPLS_BIER_ENCAPS</a>]
2170 Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A.,
2171 Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation
2172 for Bit Index Explicit Replication in MPLS and non-MPLS
2173 Networks", Work in Progress, <a href="./draft-ietf-bier-mpls-encapsulation-12">draft-ietf-bier-mpls-</a>
2174 <a href="./draft-ietf-bier-mpls-encapsulation-12">encapsulation-12</a>, October 2017.
2175
2176
2177
2178
2179
2180 <span class="grey">Wijnands, et al. Experimental [Page 39]</span></pre>
2181 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-40" ></span>
2182 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2183
2184
2185 [<a id="ref-OSPF_BIER_EXTENSIONS">OSPF_BIER_EXTENSIONS</a>]
2186 Psenak, P., Ed., Kumar, N., Wijnands, IJ., Dolganow, A.,
2187 Przygienda, T., Zhang, J., and S. Aldrin, "OSPF Extensions
2188 for BIER", Work in Progress, <a href="./draft-ietf-bier-ospf-bier-extensions-09">draft-ietf-bier-ospf-bier-</a>
2189 <a href="./draft-ietf-bier-ospf-bier-extensions-09">extensions-09</a>, October 2017.
2190
2191 [<a id="ref-RFC6513">RFC6513</a>] Rosen, E., Ed., and R. Aggarwal, Ed., "Multicast in
2192 MPLS/BGP IP VPNs", <a href="./rfc6513">RFC 6513</a>, DOI 10.17487/RFC6513,
2193 February 2012, &lt;<a href="https://www.rfc-editor.org/info/rfc6513">https://www.rfc-editor.org/info/rfc6513</a>&gt;.
2194
2195 [<a id="ref-RFC6514">RFC6514</a>] Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP
2196 Encodings and Procedures for Multicast in MPLS/BGP IP
2197 VPNs", <a href="./rfc6514">RFC 6514</a>, DOI 10.17487/RFC6514, February 2012,
2198 &lt;<a href="https://www.rfc-editor.org/info/rfc6514">https://www.rfc-editor.org/info/rfc6514</a>&gt;.
2199
2200 Acknowledgements
2201
2202 The authors wish to thank Rajiv Asati, Alia Atlas, John Bettink, Ross
2203 Callon (who contributed much of the text on deterministic ECMP),
2204 Nagendra Kumar, Christian Martin, Neale Ranns, Albert Tian, Ramji
2205 Vaithianathan, Xiaohu Xu, and Jeffrey Zhang for their ideas and
2206 contributions to this work.
2207
2208 The authors also wish to thank Sue Hares, Victor Kuarsingh, and Dan
2209 Romascanu for their reviews of this document.
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236 <span class="grey">Wijnands, et al. Experimental [Page 40]</span></pre>
2237 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-41" ></span>
2238 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2239
2240
2241 Contributors
2242
2243 The following people contributed significantly to the content of this
2244 document and should be considered co-authors:
2245
2246 Gregory Cauchie
2247 Bouygues Telecom
2248 Email: [email protected]
2249
2250 Mach(Guoyi) Chen
2251 Huawei
2252 Email: [email protected]
2253
2254 Arkadiy Gulko
2255 Thomson Reuters
2256 195 Broadway
2257 New York, NY 10007
2258 United States of America
2259 Email: [email protected]
2260
2261 Wim Henderickx
2262 Nokia
2263 Copernicuslaan 50
2264 Antwerp 2018
2265 Belgium
2266 Email: [email protected]
2267
2268 Martin Horneffer
2269 Deutsche Telekom
2270 Hammer Str. 216-226
2271 Muenster 48153
2272 Germany
2273 Email: [email protected]
2274
2275 Luay Jalil
2276 Verizon
2277 1201 East Arapaho Rd.
2278 Richardson, TX 75081
2279 United States of America
2280 Email: [email protected]
2281
2282 Uwe Joorde
2283 Deutsche Telekom
2284 Hammer Str. 216-226
2285 Muenster D-48153
2286 Germany
2287 Email: [email protected]
2288
2289
2290
2291
2292 <span class="grey">Wijnands, et al. Experimental [Page 41]</span></pre>
2293 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-42" ></span>
2294 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2295
2296
2297 Greg Shepherd
2298 Cisco Systems
2299 170 West Tasman Drive
2300 San Jose, CA 95134
2301 United States of America
2302 Email: [email protected]
2303
2304 Jeff Tantsura
2305 Email: [email protected]
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348 <span class="grey">Wijnands, et al. Experimental [Page 42]</span></pre>
2349 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-43" ></span>
2350 <span class="grey"><a href="./rfc8279">RFC 8279</a> Multicast with BIER November 2017</span>
2351
2352
2353 Authors' Addresses
2354
2355 IJsbrand Wijnands (editor)
2356 Cisco Systems, Inc.
2357 De Kleetlaan 6a
2358 Diegem 1831
2359 Belgium
2360
2361 Email: [email protected]
2362
2363
2364 Eric C. Rosen (editor)
2365 Juniper Networks, Inc.
2366 10 Technology Park Drive
2367 Westford, Massachusetts 01886
2368 United States of America
2369
2370 Email: [email protected]
2371
2372
2373 Andrew Dolganow
2374 Nokia
2375 438B Alexandra Rd #08-07/10
2376 Alexandra Technopark
2377 Singapore 119968
2378 Singapore
2379
2380 Email: [email protected]
2381
2382
2383 Tony Przygienda
2384 Juniper Networks, Inc.
2385 1194 N. Mathilda Ave.
2386 Sunnyvale, California 94089
2387 United States of America
2388
2389 Email: [email protected]
2390
2391
2392 Sam K. Aldrin
2393 Google, Inc.
2394 1600 Amphitheatre Parkway
2395 Mountain View, California 94043
2396 United States of America
2397
2398 Email: [email protected]
2399
2400
2401
2402
2403
2404 Wijnands, et al. Experimental [Page 43]
2405 </pre>