idnits 2.17.1 draft-eckert-bier-cgm2-rbs-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC8296]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 311: '...BS address. Therefore, N MUST support...' RFC 2119 keyword, line 318: '... BFR MUST support a value of N large...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (25 October 2021) is 914 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 767 == Missing Reference: 'Index' is mentioned on line 746, but not defined == Outdated reference: A later version (-13) exists of draft-ietf-bier-te-arch-10 Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 BIER T. Eckert 3 Internet-Draft Futurewei Technologies USA 4 Intended status: Experimental 25 October 2021 5 Expires: 28 April 2022 7 Carrier Grade Minimalist Multicast (CGM2) using Bit Index Explicit 8 Replication (BIER) with Recursive BitString Structure (RBS) Addresses 9 draft-eckert-bier-cgm2-rbs-00 11 Abstract 13 This memo introduces the architecture of a multicast architecture 14 derived from BIER-TE, which this memo calls Carrier Grade Minimalist 15 Multicast (CGM2). It reduces limitations and complexities of BIER-TE 16 by replacing the representation of the in-packet-header delivery tree 17 of packets through a "flat" BitString of adjacencies with a 18 hierarchical structure of BFR-local BitStrings called the Recursive 19 BitString Structure (RBS) Address. 21 Benefits of CGM2 with RBS addresses include smaller/fewer BIFT in 22 BFR, less complexity for the network architect and in the CGM2 23 controller (compared to a BIER-TE controller) and fewer packet copies 24 to reach a larger set of BFER. 26 The additional cost of forwarding with RBS addresses is a slightly 27 more complex processing of the RBS address in BFR compared to a flat 28 BitString and the novel per-hop rewrite of the RBS address as opposed 29 to bit-reset rewrite in BIER/BIER-TE. 31 CGM2 can support the traditional deployment model of BIER/BIER-TE 32 with the BIER/BIER-TE domain terminating at service provider PE 33 routers as BFIR/BFER, but it is also the intention of this document 34 to expand CGM2 domains all the way into hosts, and therefore 35 eliminating the need for an IP Multicast flow overlay, further 36 reducing the complexity of Multicast services using CGM2. Note that 37 this is not fully detailed in this version of the document. 39 This document does not specify an encapsulation for CGM2/RBS 40 addresses. It could use existing encapsulations such as [RFC8296], 41 but also other encapsulations such as IPv6 extension headers. 43 Status of This Memo 45 This Internet-Draft is submitted in full conformance with the 46 provisions of BCP 78 and BCP 79. 48 Internet-Drafts are working documents of the Internet Engineering 49 Task Force (IETF). Note that other groups may also distribute 50 working documents as Internet-Drafts. The list of current Internet- 51 Drafts is at https://datatracker.ietf.org/drafts/current/. 53 Internet-Drafts are draft documents valid for a maximum of six months 54 and may be updated, replaced, or obsoleted by other documents at any 55 time. It is inappropriate to use Internet-Drafts as reference 56 material or to cite them other than as "work in progress." 58 This Internet-Draft will expire on 28 April 2022. 60 Copyright Notice 62 Copyright (c) 2021 IETF Trust and the persons identified as the 63 document authors. All rights reserved. 65 This document is subject to BCP 78 and the IETF Trust's Legal 66 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 67 license-info) in effect on the date of publication of this document. 68 Please review these documents carefully, as they describe your rights 69 and restrictions with respect to this document. Code Components 70 extracted from this document must include Simplified BSD License text 71 as described in Section 4.e of the Trust Legal Provisions and are 72 provided without warranty as described in the Simplified BSD License. 74 Table of Contents 76 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3 77 1.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 3 78 1.2. Encapsulation Considerations . . . . . . . . . . . . . . 4 79 2. CGM2/RBS Architecture . . . . . . . . . . . . . . . . . . . . 5 80 3. CGM2/RBS forwarding plane . . . . . . . . . . . . . . . . . . 6 81 3.1. RBS BIFT . . . . . . . . . . . . . . . . . . . . . . . . 7 82 3.2. Reference encoding of RBS addresses . . . . . . . . . . . 8 83 3.3. RBS Address . . . . . . . . . . . . . . . . . . . . . . . 8 84 3.3.1. RecursiveUnit . . . . . . . . . . . . . . . . . . . . 8 85 3.3.2. AddressingField . . . . . . . . . . . . . . . . . . . 9 86 4. BIER-RBS Example . . . . . . . . . . . . . . . . . . . . . . 9 87 4.1. BFR B . . . . . . . . . . . . . . . . . . . . . . . . . . 10 88 4.2. BFR R . . . . . . . . . . . . . . . . . . . . . . . . . . 12 89 4.3. BFR S . . . . . . . . . . . . . . . . . . . . . . . . . . 13 90 4.4. BFR C . . . . . . . . . . . . . . . . . . . . . . . . . . 14 91 4.5. BFR D . . . . . . . . . . . . . . . . . . . . . . . . . . 14 92 4.6. BFR E . . . . . . . . . . . . . . . . . . . . . . . . . . 15 93 5. RBS forwarding Pseudocode . . . . . . . . . . . . . . . . . . 16 94 6. Operational and design considerations (informational) . . . . 18 95 6.1. Comparison with BIER-TE / BIER . . . . . . . . . . . . . 18 96 6.1.1. Eliminating the need for large BIFT . . . . . . . . . 18 97 6.1.2. Reducing number of duplicate packet copies across 98 BFR . . . . . . . . . . . . . . . . . . . . . . . . . 19 99 6.1.3. BIER-TE forwarding plane complexities . . . . . . . . 20 100 6.1.4. BIER-TE controller complexities . . . . . . . . . . . 20 101 6.1.5. BIER-TE specification complexities . . . . . . . . . 20 102 6.1.6. Forwarding plane complexity . . . . . . . . . . . . . 21 103 6.2. CGM2 / RBS controller considerations . . . . . . . . . . 21 104 6.3. Analysis of performance gain with CGM2 . . . . . . . . . 21 105 6.4. Example use case scenarios . . . . . . . . . . . . . . . 21 106 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21 107 8. Security considerations . . . . . . . . . . . . . . . . . . . 21 108 9. Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . 21 109 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 110 10.1. Normative References . . . . . . . . . . . . . . . . . . 22 111 10.2. Informative References . . . . . . . . . . . . . . . . . 22 112 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 22 114 1. Overview 116 1.1. Introduction 118 Carrier Grade Minimalist Multicast (CGM2) is an architecture derived 119 from the BIER-TE architecture [I-D.ietf-bier-te-arch] with the 120 following changes/improvements. 122 CGM2 forwarding is based on the principles of BIER-TE forwarding: It 123 is based on an explicit, in-packet, "source routed" tree indicated 124 through bits for each adjacency that the packet has to traverse. 125 Like in BIER-TE, adjacencies can be L2 to a subnet local neighbor in 126 support of "native" deployment of CGM2 and/or L3, so-called "routed" 127 adjacencies to support incremental or partial deployment of CGM2 as 128 needed. 130 The address used to replicate packets in the network is not a flat 131 network wide BitString as in BIER-TE, but a hierarchical structure of 132 BitStrings called a Recursive BitString Structure (RBS) Address. The 133 significance of the BitPositions (BP) in each BitString is only local 134 to the BIFT of the router/BFR that is processing this specific 135 BitString. 137 RBS addressing allows for a more compact representation of a large 138 set of adjacencies especially in the common case of sparse set of 139 receivers in large Service Provider Networks (SP). 141 CGM2 thereby eliminates the challenges in BIER [RFC8279] and BIER-TE 142 having to send multiple copies of the same packet in large SP 143 networks and the complexities especially for BIER-TE (but also BIER) 144 to engineer multiple set identifier (SI) and/or sub-domains (SD) 145 BIER-TE topologies for limited size BitStrings (e.g.: 265) to cover 146 large network topologies. 148 Like BIER-TE, CGM2 is intended to leverage a Controller to minimize 149 the control plane complexity in the network to only a simple unicast 150 routing underlay required only for routed adjacencies. 152 The controller centric architecture provides most easily any type of 153 required traffic optimization for its multicast traffic due to their 154 need to perform often NP-complete calculations across the whole 155 topology: reservation of bandwidth to support CIR/PIR traffic buffer/ 156 latency to support Deterministic Network (DetNet) traffic, cost 157 optimized Steiner trees, failure point disjoint trees for higher 158 resilience including DetNet deterministic services. 160 CGM2 can be deployed as BIER/BIER-TE are specified today, by 161 encapsulating IP Multicast traffic at Provider Edge (PE) routers, but 162 it is also considered to be highly desirable to extend CGM2 all the 163 way into Multicast Sender/Receivers to eliminate the overhead of an 164 Overlay Control plane for that (legacy) IP Multicast layer and the 165 need to deal with yet another IP multicast group addressing space. 166 In this deployment option Controller signaling extends directly (or 167 indirectly via BFIR) into senders. 169 1.2. Encapsulation Considerations 171 This document does not define a specific BIER-RBS encapsulation nor 172 does it preclude that multiple different encapsulations may be 173 beneficial to better support different use-cases or operator/user 174 technology preferences. Instead, it discusses considerations for 175 specific choices. 177 BIER-RBS can easily re-use [RFC8296] encapsulation. The RBS address 178 is inserted into the [RFC8296] BitString field. The BFR forwarding 179 plane needs to be configured (from Controller or control plane) that 180 the BIFT-id(s) used with RBS addresses are mapped to BIFT and 181 forwarding rules with RBS semantic. 183 SI/SD fields of [RFC8296] may be used as in BIER-TE, but given that 184 CGM2 is designed (as described in the Overview section) to simplify 185 multicast services, a likely and desirable configuration would be to 186 only use a single BIFT in each BFR for RBS addresses, and mapping 187 these to a single SD and SI 0. 189 IP Multicast [RFC1112] was defined as an extension of IP [RFC791], 190 reusing the same network header, and IPv6 multicast inherits the same 191 approach. In comparison, [RFC8296] defines BIER encapsulation as a 192 completely separate (from IP) layer 3 protocol, and duplicates both 193 IP and MPLS header elements into the [RFC8296] header. This not only 194 results in always unused, duplicate header parameters (such as TC vs. 195 DSCP), but it also foregoes the option to use any non-considered IPv6 196 extension headers with BIER and would require the introduction of a 197 whole new BIER specific socket API into host operating systems if it 198 was to be supported natively in hosts. 200 Therefore an encapsulation of RBS addresses using an IP and/or IPv6 201 extension header may be more desirable in otherwise IP and/or IPv6 202 only deployments, for example when CGM2 is extended into hosts, 203 because it would allow to support CGM2 via existing IP/IPv6 socket 204 APIs as long as they support extension headers, which the most 205 important host stacks do today. 207 2. CGM2/RBS Architecture 209 This section describes the basic CGM2 architecture via Figure 1 210 through its key differences over the BIER-TE architecture. 212 Optional 213 |<-IGMP/PIM-> multicast flow <-PIM/IGMP->| 214 overlay 216 CGM2 [CGM2 Controller] 217 control plane . ^ ^ ^ 218 . / | \ BIFT configuration 219 .......... | | | per-flow RBS setup 220 . | | | 221 . v v v 222 Src (-> ... ) -> BFIR-----BFR-----BFER -> (... ->) Rcvr 224 |<----------------->| 225 CGM2 with RBS-address forwarding plane 227 |<.............. <- CGM domain ---> ...............| 229 |<--------------------->| 230 Routing underlay (optional) 232 Figure 1: CGM2/RBS Architecture 234 In the "traditional" option, when deployed with a domain spanning 235 from BFIR to BFER, the CGM2 architecture is very much like the BIER- 236 TE architecture, in which the BIER-TE forwarding rules for 237 (BitString,SI,SD) addresses are replaced by the RBS address 238 forwarding rules. 240 The CGM2 Controller replaces the BIER-TE controller, populating 241 during network configuration the BIFT, which are very much like BIER- 242 TE BIFT, except that they do not cover a network-wide BP address 243 space, but instead each BFR BIFT only needs as many BP in its BIFT as 244 it has link-local adjacencies, and in partial deployments also 245 additional L3 adjacencies to tunnel across non-CGM capable routers. 247 Per-flow operations in this "traditional" option is very much as in 248 BIER/BIER-TE, with the CGM2 controller determining the RBS address 249 (instead of the BIER-TE (BitString,SI,SD)) to be imposed as part of 250 the RBS address header (compared to the BIER encapsulation [RFC8296]) 251 on the BFIR. 253 To eliminate the need for an IP Multicast flow overlays, a CGM2 254 domain may extend all the way into Sender/Receiver hosts. This is 255 called "end-to-end" deployment model. In that case, the sender host 256 and CGM2 controller collaborate to determine the desired receivers 257 for a packet as well as desired path policy/requirements, the 258 controller indicates to the sender of the packet the necessary RBS 259 address and address of the BFIR, and the Sender imposes an 260 appropriate RBS address header together with a unicast encapsulation 261 towards the BFIR. 263 CGM2 is also intended so especially simplify controller operations 264 that also instantiate QoS policies for multicast traffic flows, such 265 as bandwidth and latency reservations (e.g.: DetNet). As in BIER-TE, 266 this is orthogonal to the operations of the CGM2/RBS address 267 forwarding operations and will be covered in separate documents. 269 3. CGM2/RBS forwarding plane 271 Instead of a (flat) BitString as in BIER-TE that use a network wide 272 shared BP address space for adjacencies across multiple BFR, CGM2 273 uses a structured address built from so-called RecursiveUnits (RU) 274 that contain BitStrings, each of which is to be parsed by exactly one 275 BFR along the delivery tree of the packet. 277 The equivalent to a BIER/BIER-TE BitString is therefore called the 278 RecursiveUnit BitString Structure (RBS) Address. Forwarding for 279 CGMP2 is therefore also called RBS forwarding. 281 3.1. RBS BIFT 283 RBS BIFT as shown in Figure 2 are, like BIER-TE BIFT, tables that are 284 indexed by BP, containing for each BP an adjacency. The core 285 difference over BIER-TE BIFT is that the BP of the BIFT are all local 286 to the BFR, whereas in BIER-TE, the BP are shared across a BIER-TE 287 domain, each BFR can only use a subset the BP for its own 288 adjacencies, and only in some cases can BP be shared for adjacencies 289 across two (or more) BFR. Because of this difference, most of the 290 complexities of BIER-TE BIFT are not required with BIER-RBS BIFT, see 291 Section 6.1.3. 293 +--+---------+-------------+ 294 |BP|Recursive| Adjacency| 295 +--+---------+-------------+ 296 | 1| 1|adjacenct BFR| 297 +--+---------+-------------+ 298 | 2| 0| punt/host| 299 +--+---------+-------------+ 300 | ..... ... | 301 +--+---------+-------------+ 302 | N| ...| ... | 303 +--+---------+-------------+ 305 Figure 2: RBS BIFT 307 An RBS BIFT has a configured number of N addressable BP entries. 308 When a BFR receives a packet with an RBS address, it expects that the 309 BitString inside the RBS address that needs to be parsed by the BFR 310 (see Section 3.3 has a length that matches N according to the 311 encapsulation used for the RBS address. Therefore, N MUST support 312 configuration in increments of the supported size of the BitString in 313 the encapsulation of the RBS Address. In the reference encoding (see 314 Section 3.3), the increment for N is 1 (bit). If an encapsulation 315 would call for a byte accurate encoding of the BitString, N would 316 have to be configurable in increments of 8. 318 BFR MUST support a value of N larger than the maximum number of 319 adjacencies through which RBS forwarding/replication of a single 320 packet is required, such as the number of physical interfaces on BFR 321 that are intended to be deployed as a Provider Core (P) routers. 323 RBS BIFT introduce a new "Recursive" flag for each BP. These are 324 used for adjacencies to other BFR to indicate that the BFR processing 325 the packet RBS address BitString also has to expect for every BP with 326 the recursive flag set another RU inside the RBS address. 328 3.2. Reference encoding of RBS addresses 330 Structure elements of the RBS Address and its components are 331 parameterized according to a specific encapsulation for RBS 332 addresses, such as the total size of the TotalLen field and the unit 333 in which it is counted (see Section 3.3). These parameters are 334 outside the scope of this document. Instead, this document defines 335 example parameters that together form the so called "Reference 336 encoding of RBS addresses". This encoding may or may not be adopted 337 for any particular encapsulation of RBS addresses. 339 3.3. RBS Address 341 An RBS address is structured as shown in Figure 3. 343 +----------+-----+---------------+---------+ 344 | TotalLen | Rsv | RecursiveUnit | Padding | 345 +----------+-----+---------------+---------+ 346 . . 347 .... TotalLen ....... 349 Figure 3: RBS Address 351 TotalLen counts in some unit, such as bits, nibbles or bytes the 352 length of the RBS Address excluding itself and Padding. For the 353 reference encoding, TotalLen is an 8-bit field that counts the size 354 of the RBS address in bits, permitting for up to 256 bit long RBS 355 addresses. 357 In case additional, non-recursive flags/fields are determined to be 358 required in the RBS Address, they should be encoded in a field 359 between TotalLen and RecursiveUnit, which is called Rsv. In the 360 reference encoding, this field has a length of 0. 362 Padding is used to align the RBS address as required by the 363 encapsulation. In the reference encoding, this alignment is to 8 364 bits (byte boundaries). Therefore, Padding (bits) = (8 - TotalLen % 365 8). 367 3.3.1. RecursiveUnit 369 The RecursiveUnit field is structured as shown in Figure 4. 371 +-+-+-+-+-+ -+-+-+-+-+-+-+-+-+ -+-+-+-+-+-+-+-+ -+ 372 | BitString...| AddressingField...| RecursiveUnit 1...M| 373 +-+-+-+-+-+ -+-+-+-+-+-+-+-+-+ -+-+-+-+-+-+-+-+- -+ 375 Figure 4: RBS RecursiveUnit 377 The BitString field indicates the bit positions (BPs) to which the 378 packet is to be replicated using the BIFT of the BFR that is 379 processing the Recursive unit. 381 For each of M BP set in the BitString of the RecursiveUnit for which 382 the Recursive flag is set in the BIFT of the BFR, the RecursiveUnit 383 contains a RecursiveUnit i, i=1...M, in order of increasing BP index. 385 If adjacencies between BFR are not configured as recursive in the 386 BIFT, this recursive extraction does not happen for an adjacency, no 387 RecursiveUnit i has to be encoded for the BP, and BFRs across such 388 adjacencies would have to share the BP of a common BIFT as in BIER- 389 TE. This option is not further discussed in this version of the 390 document. 392 3.3.2. AddressingField 394 The AddressingField of an RBS address is structured as shown in 395 Figure 5. 397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ 398 | L1 | L2 |...| L(M-1) | 399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ 401 Figure 5: RBS AddressingField 403 The AddressingField consists of one or more fields Li, i=1...(M-1). 404 Li is the length of RecursiveUnit i for the i'th recursive bit set in 405 the BitString preceding it. 407 In the reference encoding, the lengths are 8-bit fields indicating 408 the length of RecursiveUnits in bits. 410 The length of the M'th RecursiveUnit is not explicitly encoded but 411 has to be calculated from TotalLen. 413 4. BIER-RBS Example 415 Figure 6 shows an example for RBS forwarding. 417 +-+ +-+ +-+ 418 | |-----| |------|C|-=> Client2 419 +-+ +-+ +-+ 420 / \ \ /=>/ \ 421 / \ \ / | 422 +-+ +-+ +-+ +-+ 423 Client1 =>-|B|-=>-|R|-=>-|S|-=>-|D|-=> Client3 424 +-+ +-+ +-+ +-+ 425 \ / 426 \ +-+ 427 \-=>-|E|-=> Client4 428 +-+ 430 Figure 6: Example Network Topology 432 A packet from Client1 connected to BFIR B is intended to be 433 replicated to Client2,3,4. The example initially assumes the 434 traditional option of the architecture, in which the imposition of 435 the header for the RBS address happens on BFIR B, for example based 436 on functions of an IP multicast flow overlay. 438 A controller determines that the packet should be forwarded hop-by- 439 hop across the network as shown in Figure 7. 441 Client 1 ->B(impose BIER-RBS) 442 =>R( 443 => E (dispose BIER-RBS) 444 => Client4 445 => S( 446 =>C (dispose BIER-RBS) 447 => Client2 448 =>D (dispose BIER-RBS) 449 => Client3 450 ) 451 ) 453 Figure 7: Desired example forwarding tree 455 4.1. BFR B 457 The 34 bit long (without padding) RBS address shown in Figure 8 is 458 constructed to represent the desired tree from Figure 7 and is 459 imposed at B onto the packet through an appropriate header supporting 460 the reference encoding of RBS addresses. 462 .............. RecursiveUnit ................. 463 . . 464 +-------+----+-----+-----+-----+----+-----+------+-----+-----+ 465 |Tlen:34|B:01|R:011|L1:10|S:011|L1:3|C:001|D:0001|E:001|Pad:6| 466 +-------+----+-----+-----+-----+----+-----+------+-----+-----+ 467 8bit 2bit 3bit 8bit 3bit 8bit 3bit 4bit 3bit 6bit 469 Figure 8: RBS Address imposed at BFIR-B 471 In Figure 8 and further the illustrations of RBS addresses, 472 BitStrings are preceded by the name of the BFR for whom they are 473 destined and their values are shown as binary with the lowest BP 1 474 starting on the left. TotalLength (Tlen:), AddressingField (L1:) and 475 Padding (Pad:) fields are shown with decimal values. 477 RBS forwarding on B examines this address based on its RBS BIFT with 478 N=2 BP entries, which is shown in Figure 9. 480 +--+---------+---------+ 481 |BP|Recursive|Adjacency| 482 +--+---------+---------+ 483 | 1| 0| client1 | 484 +--+---------+---------+ 485 | 2| 1| R | 486 +--+---------+---------+ 488 Figure 9: BIER-RBS BIFT on B 490 This results in the parsing of the RBS address as shown in Figure 10, 491 which shows that B does not need (nor can) parse all structural 492 elements, but only those relevant to its own RBS forwarding 493 procedure. 495 ......... RecursiveUnit ............... 496 . . 497 . ......,.. RecursiveUnit 1 ......... 498 . . . 499 +-------+----+----------------------------------+-----+ 500 |Tlen:34|B:01|R:01100001010011000000110010001001|Pad:6| 501 +-------+----+----------------------------------+-----+ 502 8bit 2bit 32bit 6bit 504 Figure 10: RBS Address as processed by BFIR-B 506 There is only one BP towards BFR R set in the BitString B:01, so the 507 RecursiveUnit 1 follows directly after the end of the BitString B:01 508 and it covers the whole Tlen - length of BitString (34 - 2 = 32 bit). 510 B rewrites the RBS address by replacing the RecursiveUnit with 511 RecursiveUnit 1 and adjusts the Padding to zero bits. The resulting 512 RBS address is shown in Figure 11. It then sends the packet copy 513 with that rewritten RBS address to BFR R. 515 4.2. BFR R 517 BFR R receives from BFR B the packet with that RBS address shown in 518 Figure 11. 520 .............. RecursiveUnit ............ 521 . . 522 +-------+-----+-----+-----+----+-----+------+-----+ 523 |Tlen:32|R:011|L1:18|S:011|L1:3|C:001|D:0001|E:001| 524 +-------+-----+-----+-----+----+-----+------+-----+ 525 8bit 3bit 8bit 3bit 8bit 3bit 4bit 3bit 526 . . . 527 . RecursiveUnit 1...... ..... 528 . 529 RecursiveUnit 2 ... 531 Figure 11: RBS Address processed by BFR-R 533 BFR R parses the RBS Address as shown in Figure 12 using its RBS BIFT 534 of N=3 BP entries shown in Figure 13. 536 .............. RecursiveUnit ............ 537 . . 538 +-------+-----+-----+--------------------+-----+ 539 |Tlen:32|R:011|L1:18|S:011000000110010001|E:001| 540 +-------+-----+-----+--------------------+-----+ 541 8bit 3bit 8bit 18bit 3bit 542 . . . 543 . RecursiveUnit 1... ..... 544 . 545 RecursiveUnit 2 ... 547 Figure 12: RBS Address processed by BFR-R 549 Because there are two recursive BP set in the BitString for R, one 550 for BFR S and one for BFR E, one Length field L1 is required in the 551 AddressingField, indicating the length of the RecursiveUnit 1 for BFR 552 S, followed by the remainder of the RBS address being the 553 RecursiveUnit 2 for BFR E. 555 +--+---------+---------+ 556 |BP|Recursive|Adjacency| 557 +--+---------+---------+ 558 | 1| 1| B | 559 +--+---------+---------+ 560 | 2| 1| S | 561 +--+---------+---------+ 562 | 3| 1| E | 563 +--+---------+---------+ 565 Figure 13: RBS BIFT on BFR R 567 BFR R accordingly creates one copy for BFR S using RecursiveUnit 1, 568 and only copy for BFR E using RecursiveUnit 2, updating Padding 569 accordingly for each copy. 571 4.3. BFR S 573 BFR S receives from BFR B the packet and parses the RBS address as 574 shown in Figure 14 using its RBS BIFT of N=3 BP shown in Figure 15. 576 .... RecursiveUnit .... 577 . . 578 +-------+-----+----+-----+------+-----+ 579 |Tlen:18|S:011|L1:3|C:001|D:0001|Pad:6| 580 +-------+-----+----+-----+------+-----+ 581 8bit 3bit 8bit 3bit 4bit 3bit 582 . . . . 583 .... ...... 584 RecursiveUnit 1 . . 585 . 586 RecursiveUnit 2 ....... 588 Figure 14: RBS Address processed by BFR-S 590 +--+---------+---------+ 591 |BP|Recursive|Adjacency| 592 +--+---------+---------+ 593 | 1| 1| R | 594 +--+---------+---------+ 595 | 2| 1| C | 596 +--+---------+---------+ 597 | 3| 1| D | 598 +--+---------+---------+ 600 Figure 15: RBS BIFT on BFR-S 602 BFR S accordingly sends one packet copy with RecursiveUnit 1 in the 603 RBS address to BFR C and a second packet copy with RecursiveUnit 2 to 604 BFR D. 606 4.4. BFR C 608 BFR C receives from BFR S the packet and parses the RBS address 609 according to its N=3 BP entries BIFT (shown in Figure 17) as shown in 610 Figure 16. 612 +-------+-----+-----+ 613 |Tlen:3 |C:001|Pad:5| 614 +-------+-----+-----+ 615 8bit 3bit 5bi 617 Figure 16: RBS Address processed by BFR-C 619 +--+---------+-------------+ 620 |BP|Recursive| Adjacency| 621 +--+---------+-------------+ 622 | 1| 1| S | 623 +--+---------+-------------+ 624 | 2| 1| D | 625 +--+---------+-------------+ 626 | 3| 0| local_decap| 627 +--+---------+-------------+ 629 Figure 17: RBS BIFT on BFR-C 631 BFR S accordingly creates one packet copy for BP 3 where the RBS 632 address encapsulation is disposed of, and the packet is ultimately 633 forwarded to Client 2, for example because of an IP multicast payload 634 for which the multicast flow overlay identifies Client 2 as an 635 interested receiver, as in BIER/BIER-TE. 637 To avoid having to use an IP flow overlay, the BIFT could instead 638 have one BP allocated for every non-RBS destination, in this example 639 BP 3 would then explicitly be allocated for Client 2, and instead of 640 disposing of the RBS address encapsulation, BFR C would impose or 641 rewrite a unicast encapsulation to make the packet become a unicast 642 packet directed to Client 2. This option is not further detailed in 643 this version of the document. 645 4.5. BFR D 647 The procedures for processing of the packet on BFR D are very much 648 the same as on BFR C. Figure 18 shows the RBS address at BFR D, 649 Figure 19 shows the N=4 bit RBS BIFT of BFR D. 651 +-------+------+-----+ 652 |Tlen:4 |D:0001|Pad:4| 653 +-------+------+-----+ 654 8bit 4bit 4bit 656 Figure 18: RBS Address processed by BFR-D 658 +--+---------+-------------+ 659 |BP|Recursive| Adjacency| 660 +--+---------+-------------+ 661 | 1| 1| S | 662 +--+---------+-------------+ 663 | 2| 1| C | 664 +--+---------+-------------+ 665 | 3| 1| E | 666 +--+---------+-------------+ 667 | 4| 0| local_decap| 668 +--+---------+-------------+ 670 Figure 19: RBS BIFT on BFR-D 672 4.6. BFR E 674 The procedures for processing of the packet on BFR E are very much 675 the same as on BFR C and D. Figure 20 shows the RBS address at BFR 676 D, Figure 21 shows the N=E bit RBS BIFT of BFR E. 678 +-------+-----+-----+ 679 |Tlen:3 |E:001|Pad:5| 680 +-------+-----+-----+ 681 8bit 3bit 5bit 683 Figure 20: RBS Address processed by BFR-E 685 +--+---------+-------------+ 686 |BP|Recursive| Adjacency| 687 +--+---------+-------------+ 688 | 1| 1| R | 689 +--+---------+-------------+ 690 | 2| 1| D | 691 +--+---------+-------------+ 692 | 3| 0| local_decap| 693 +--+---------+-------------+ 695 Figure 21: RBS BIFT on BFR-E 697 5. RBS forwarding Pseudocode 699 The following example RBS forwarding Pseudocode assumes the reference 700 encoding of bit-accurate length of BitStrings and RecursiveUnits as 701 well as 8-bit long TotalLen and AddressingField Lengths. All packet 702 field addressing and address/offset calculations is therefore bit- 703 accurate instead of byte accurate (which is what most CPU memory 704 access today is). 706 void ForwardRBSPacket (Packet) 707 { 708 RBS = GetPacketMulticastAddr(Packet); 709 Total_len = RBS; 710 Rsv = Total_len + length(Total_Len); 711 BitStringA = Rsv + length(Rsv); 712 AddressingField = BitStringA + BIFT.entries; 714 // [1] calculate number of recursive bits set in BitString 715 CopyBitString(*BitStringA, *RecursiveBits, BIFT.entries); 716 And(*RecursiveBits,*BIFTRecursiveBits, BIFT.entries); 717 N = CountBits(*RecursiveBits, BIFT.entries); 719 // Start of first RecursiveUnit in RBS address 720 // After AddressingField array with 8-bit length fields 721 RecursiveUnit = AddressingField + (N - 1) * 8; 723 RemainLength = *Total_len - length(Rsv) 724 - BIFT.entries; 726 Index = GetFirstBitPosition(*BitStringA); 727 while (Index) { 728 PacketCopy = Copy(Packet); 730 if (BIFT.BP[Index].recursive) { 731 if(N == 1) { 732 RecursiveUnitLength = RemainLength; 733 } else { 734 RecursiveUnitLength = *AddressingField; 735 N--; 736 AddressingField += 8; 737 RemainLength -= RecursiveUnitLength; 738 RemainLength -= 8; // 8 bit of AddressingField 739 } 740 RewriteRBS(PacketCopy, RecursiveUnit, RecursiveUnitLength); 741 SendTo(PacketCopy, BIFT.BP[Index].adjacency); 743 RecursiveUnit += RecursiveUnitLength; 744 } else { 745 DisposeRBSheader(PacketCopy); 746 SendTo(PacketCopy, BIFT.BP[Index].adjacency); 747 } 748 Index = GetNextBitPosition(*BitStringA, Index); 749 } 751 Figure 22: RBS address forwarding Pseudocode 753 Explanations for Figure 22. 755 RBS is the (bit accurate) address of the RBS address in packet header 756 memory. BitStringA is the address of the RBS address BitString in 757 memory. length(Total_Len) and length(Rsv) are the bit length of the 758 two RBS address fields, e.g.: 8 bit and 0 bit for the reference 759 encoding. 761 The BFR local BIFT has a total number of BIFT.entries addressable BP 762 1...BIFTentries. The BitString therefore has BIFT.entries bits. 764 BIFT.RecursiveBits is a BitString pre-filled by the control plane 765 with all the BP with the recursive flag set. This is constructed 766 from the Recursive flag setting of the BP of the BIFT. The code 767 starting at [1] therefore counts the number of recursive BP in the 768 packets BitString. 770 Because the AddressingField does not have an entry for the last (or 771 only) RecursiveUnit, its length has to be calculated by taking 772 TotalLen into account. 774 RewriteRBS needs to replace RBS address with the RecursiveUnit 775 address, keeping only Rsv, recalculating TotalLen and adding 776 appropriate Padding. 778 For non-recursive BP, the Pseudocode assumes disposition of the 779 RBSheader. This is not strictly necessary but non-disposing cases 780 are outside of scope of this version of the document. 782 6. Operational and design considerations (informational) 784 6.1. Comparison with BIER-TE / BIER 786 This section discusses informationally, how and where CGM2 can avoid 787 different complexities of BIER/BIER-TE, and where it introduces new 788 complexities. 790 6.1.1. Eliminating the need for large BIFT 792 In a BIER domain with M BFER, every BFR requires M BIFT entries. If 793 the supported BSL is N and M > 2 ^ N, then S = (M / 2 ^ N) set 794 indices (SI) are required, and S copies of the packet have to be sent 795 by the BFIR to reach all targeted BFER. 797 In CGM2, the number of BIFT entries does not need to scale with the 798 number of BFER or paths through the network, but can be limited to 799 only the number of L2 adjacencies of the BFR. Therefore CGM2 800 requires minimum state maintenance on each BFR, and multiple SI are 801 not required. 803 6.1.2. Reducing number of duplicate packet copies across BFR 805 If the total size of an RBS encoded delivery tree is larger than a 806 supported maximum RBS header size, then the CGM2 controller simply 807 needs to divide the tree into multiple subtrees, each only addressing 808 a part of the BFER (leaves) of the target tree and pruning any 809 unnecessary branches. 811 B1 812 / \ 813 B2 B3 814 / \ / \ 815 / \/ \ 816 B4 B5 B6 817 /..| / \ |..\ 818 B7..B99 B100..B200 B201...B300 820 Figure 23: Simple Topology Example 822 Consider the simple topology in Figure 23 and a multicast packet that 823 needs to reach all BFER B7...B300. Assume that the desired maximum 824 RBM header size is such that a RBS address size of <= 256 bits is 825 desired. The CGM2 controller could create an RBS address 826 B1=>B2=>B4=>(B7..B99), for a first packet, an RBS address 827 B1=>B3=>B5=>(B100..B200) for a second packet and a third RBS address 828 B1=>B3=>B6=>B201...B300. 830 The elimination of larger BIFT state in BFR through multiple SI in 831 BIER/BIER-TE does come at the expense of replicating initial hops of 832 a tree in RBS addresses, such as in the example the encoding of 833 B1=>B3 in the example. 835 Consider that the assignment of BFIR-ids with BIER in the above 836 example is not carefully engineered. It is then easily possible that 837 the BFR-ids for B7..B99 are not sequentially, but split over a larger 838 BFIR-id space. If the same is true for all BFER, then it is possible 839 that each of the three BFR B4,B5 and B6 has attached BFER from three 840 different SI and one may need to send for example three multiple 841 packets to B7 to address all BFER B7..B99 or to B5 to address all 842 B100..B200 or B6 to address all B201...B300. These unnecessary 843 duplicate packets across B4, B5 or B6 are because of the addressing 844 principle in BIER and are not necessary in CGM2, as long as the total 845 length of an RBS address does not require it. 847 For more analysis, see Section 6.3. 849 6.1.3. BIER-TE forwarding plane complexities 851 BIER-TE introduces forwarding plane complexities to allow reducing 852 the BSL required. While all of these could be supported / 853 implemented with CGM2, this document contends that they are not 854 necessary, therefore providing significant overall simplifications. 856 * BIER-TE supports multiple adjacencies in a single BIFT Index to 857 allow compressing multiple adjacencies into a single Index for 858 traffic that is known to always require replications to all those 859 adjacencies (such as when flooding TV traffic). 861 * BIER-TE support ECMP adjacencies which have to calculate which out 862 of 2 or more possible adjacencies a packet should be forwarded to. 864 * BIER-TE supports special Do-Not-Clear (DNC) behavior of 865 adjacencies to permit reuse of such a bit for adjacencies on 866 multiple consecutive BFR. This behavior specifically also raises 867 the risk of looping packets. 869 6.1.4. BIER-TE controller complexities 871 BIER-TE introduces BIER-TE controller plane mechanisms that allow to 872 reuse bits of the flat BIER-TE BitStrings across multiple BFR solely 873 to reduce the number of BP required but without introducing 874 additional complexities for the BIER-TE forwarding plane. 876 * Shared BP for all Leaf BFR. 878 * Shared BP for both Interfaces of p2p links. 880 * Shared bits for multi-access subnets (LANs). 882 These bit-sharing mechanisms are unnecessary and inapplicable to CGM2 883 because there is no need to share BP across the BIFT of multiple BFR. 885 6.1.5. BIER-TE specification complexities 887 The BIER-TE specification distinguishes between forward (link scope) 888 and routed (underlay routed) adjacencies to highlight, explain and 889 emphasize on the ability of BIER-TE to be deployed in an overlay 890 fashion especially also to reduce the necessary BSL, even when all 891 routers in the domain could or do support BIER-TE. 893 In CGM2, routed adjacencies are considered to be only required in 894 partial deployments to forward across non-CGM2 enabled routers. This 895 specification does therefore not highlight link scope vs. routed 896 adjacencies as core distinct features. 898 6.1.6. Forwarding plane complexity 900 CGM2 introduces some more processing calculation steps to extract the 901 BitString that needs to be examined by a BFR from the RBS address. 902 These additional steps are considered to be non-problematic for 903 todays programmable forwarding planes such as P4. 905 Whereas BIER-TE clears bit on each hops processing, CGM2 rewrites the 906 address on every hop by extracting the recursive unit for the next 907 hop and make it become the packet copies address. This rewrite 908 shortens the RBS address. This hopefully has only the same 909 complexity as (tunnel) encapsulations/decapsulations in existing 910 forwarding planes. 912 6.2. CGM2 / RBS controller considerations 914 TBD. Any aspects not covered in Section 6.1. 916 6.3. Analysis of performance gain with CGM2 918 TBD: Comparison of number of packets/header sizes required in large 919 real-world operator topology between BIER/BIER-TE and CGM2. 921 6.4. Example use case scenarios 923 TBD. 925 7. Acknowledgements 927 This work is based on the design published by Sheng Jiang, Xu Bing, 928 Yan Shen, Meng Rui, Wan Junjie and Wang Chuang {jiangsheng|bing.xu|ya 929 nshen|mengrui|wanjunjie2|wangchuang}@huawei.com, see [CGM2Design]. 931 8. Security considerations 933 TBD. 935 9. Changelog 937 [RFC-Editor: please remove this section]. 939 This document is written in https://github.com/cabo/kramdown-rfc2629 940 markup language. This documents source is maintained at 941 https://github.com/toerless/bier-cgm2-rbs, please provide feedback to 942 the appropriate IETF mailing list and submit an Issue to the GitHub. 944 00 - Initial version from [CGM2Design]. 946 10. References 948 10.1. Normative References 950 [I-D.ietf-bier-te-arch] 951 Eckert, T., Cauchie, G., and M. Menth, "Tree Engineering 952 for Bit Index Explicit Replication (BIER-TE)", Work in 953 Progress, Internet-Draft, draft-ietf-bier-te-arch-10, 9 954 July 2021, . 957 [RFC1112] Deering, S., "Host extensions for IP multicasting", STD 5, 958 RFC 1112, DOI 10.17487/RFC1112, August 1989, 959 . 961 [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, 962 DOI 10.17487/RFC0791, September 1981, 963 . 965 [RFC8279] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 966 Przygienda, T., and S. Aldrin, "Multicast Using Bit Index 967 Explicit Replication (BIER)", RFC 8279, 968 DOI 10.17487/RFC8279, November 2017, 969 . 971 [RFC8296] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 972 Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation 973 for Bit Index Explicit Replication (BIER) in MPLS and Non- 974 MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January 975 2018, . 977 10.2. Informative References 979 [CGM2Design] 980 Jiang, S., Xu, B.(., Shen, Y., Rui, M., Junjie, W., and W. 981 Chuang, "Novel Multicast Protocol Proposal Introduction", 982 10 October 2021, 983 . 986 Author's Address 988 Toerless Eckert 989 Futurewei Technologies USA 990 2220 Central Expressway 991 Santa Clara, CA 95050 992 United States of America 993 Email: tte@cs.fau.de