idnits 2.17.1 draft-thubert-roll-bier-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- -- The draft header indicates that this document updates RFC6550, but the abstract doesn't seem to mention this, which it should. -- The draft header indicates that this document updates RFC6282, but the abstract doesn't seem to mention this, which it should. -- The draft header indicates that this document updates RFC6775, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year (Using the creation date from RFC6282, updated by this document, for RFC5378 checks: 2008-10-08) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 22, 2018) is 2285 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-20) exists of draft-ietf-6lo-backbone-router-05 == Outdated reference: A later version (-21) exists of draft-ietf-6lo-rfc6775-update-11 == Outdated reference: A later version (-18) exists of draft-ietf-roll-aodv-rpl-02 == Outdated reference: A later version (-06) exists of draft-thubert-6lo-bier-dispatch-04 -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL P. Thubert, Ed. 3 Internet-Draft Cisco 4 Updates: 6282,6550,6775 (if approved) January 22, 2018 5 Intended status: Standards Track 6 Expires: July 26, 2018 8 RPL-BIER 9 draft-thubert-roll-bier-01 11 Abstract 13 This specification extends RPL to provide unicast and multicast 14 routing based on bitStrings such as used in Bit Index Explicit 15 Replication and its source-routed Traffic Engineering variant, which 16 correspond to RPL storing and Non-Storing Modes respectively. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on July 26, 2018. 35 Copyright Notice 37 Copyright (c) 2018 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 54 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 5 55 4. Extensions to RFC 6550 . . . . . . . . . . . . . . . . . . . 5 56 4.1. RPL-BIER MOPs . . . . . . . . . . . . . . . . . . . . . . 6 57 4.1.1. RPL-BIER Non-Storing Mode . . . . . . . . . . . . . . 6 58 4.1.2. RPL-BIER Storing Mode . . . . . . . . . . . . . . . . 6 59 4.2. BitString Information . . . . . . . . . . . . . . . . . . 7 60 5. Updating the 6LoWPAN Framework . . . . . . . . . . . . . . . 8 61 5.1. Extensions to RFC 6775 . . . . . . . . . . . . . . . . . 8 62 5.2. Extensions to RFC 6282 . . . . . . . . . . . . . . . . . 9 63 5.3. New Neighbor Discovery Options and Messages . . . . . . . 9 64 5.3.1. 6LoWPAN ND Bit Position Option . . . . . . . . . . . 9 65 5.3.2. Address Mapping Message . . . . . . . . . . . . . . . 10 66 6. BitString formats . . . . . . . . . . . . . . . . . . . . . . 11 67 6.1. Bit-by-bit BitStrings . . . . . . . . . . . . . . . . . . 11 68 6.1.1. Allocating a Bit Position in a Bit-by-bit BitString . 12 69 6.1.2. Aggregation of Bit-by-bit BitStrings . . . . . . . . 13 70 6.1.3. Forwarding Based on Bit-by-bit BitStrings . . . . . . 13 71 6.1.4. Reliable Multicast based on Bit-by-bit BitStrings . . 14 72 6.2. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 14 73 6.2.1. Computing and Saving Bloom Filters . . . . . . . . . 15 74 6.2.2. Forwarding based on Bloom Filters . . . . . . . . . . 15 75 6.2.3. Hash Functions Distribution . . . . . . . . . . . . . 15 76 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 15 77 8. Security Considerations . . . . . . . . . . . . . . . . . . . 15 78 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 79 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 80 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 81 11.1. Normative References . . . . . . . . . . . . . . . . . . 16 82 11.2. Informative References . . . . . . . . . . . . . . . . . 16 83 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 18 85 1. Introduction 87 The design of Low Power and Lossy Networks (LLNs) is generally 88 focused on saving energy, which is the most constrained resource of 89 all. Other design constraints, such as a limited memory capacity, 90 duty cycling of the LLN devices and low-power lossy transmissions, 91 derive from that primary concern. 93 The IETF produced the "Routing Protocol for Low Power and Lossy 94 Networks" [RFC6550] (RPL) to provide routing services within such 95 constraints. In order to cope with lossy transmissions, RPL forms 96 Direction-Oriented Directed Acyclic Graphs (DODAGs) that provide 97 multiple forwarding solutions to most of the intermediate hops. 99 Because it is designed to adapt to fuzzy connectivity with lazy 100 control, RPL can only provide a best effort routability, connecting 101 most of the LLN nodes, most of the time. 103 RPL is a Distance-Vector protocol, which, compared to link-state 104 protocols, limits the amount of topological knowledge that needs to 105 be installed and maintained in each node. RPL also leverages Routing 106 Stretch to reduce further the amount of control traffic and routing 107 state that is required to operate the protocol. Finally, broken 108 routes may be fixed lazily and on-demand, based on dataplane 109 inconsistency discovery, which avoids wasting energy in the proactive 110 repair of unused paths. 112 RPL enables various trade-offs between routing stretch, amount of 113 routing state and packet size, with the introduction of different 114 modes of operation (MOPs): 116 o With Reactive Discovery of Point-to-Point (P2P) Routes (aka on- 117 demand) [RFC6997][I-D.ietf-roll-aodv-rpl], a limited number of 118 routes are optimized on-demand, between select pairs of devices 119 for which a service with some particular characteristics is 120 needed. 121 o In Storing Mode of operation (aka Storing Mode), Multipoint to 122 Point (MP2P) routes from the LLN nodes to the root and Point to 123 Multipoint (P2MP) routes from the root to the LLN nodes are 124 optimized, but P2P routes between LLN nodes are stretched via a 125 common parent. In Storing Mode, RPL requires that nodes maintain 126 routing information for the maximum number of child nodes in their 127 sub-DODAG. If a network is composed of similar nodes, this means 128 that each node should be able to store a number of routes that is 129 in the order of the total number of nodes in the network. 130 o In Non-Storing Mode of operation (aka Non-Storing Mode), MP2P and 131 P2MP routes are also optimized, but downwards routes can only be 132 computed by the root and P2MP forwarding relies on strict source- 133 routing. This increases the size of the packets and limits the 134 depth of the DODAG. The Non-Storing Mode also results in 135 additional stretch for P2P routes, whereby all packets must 136 transit via the root following the default route all the way up, 137 to be then source-routed down. 139 In order to alleviate the issues above and improve the existing 140 multicast operations, this specification introduces the use of 141 bitStrings in RPL LLNs. BitStrings are already used in the art as a 142 datapath analog to one or more IPv6 [RFC8200] addresses: 144 o With the Bit Index Explicit Replication (BIER), introduced in the 145 "BIER Architecture" [RFC8279], each it in a bitStrings represents 146 a particular destination. This specification introduces a RPL- 147 BIER Storing Mode that applies BIER operations to RPL Storing 148 Mode. 149 o "Traffic Engineering for Bit Index Explicit Replication" 150 [I-D.eckert-bier-te-arch] (BIER-TE) adds support for Traffic 151 Engineering by explicit hop-by-hop forwarding and loose hop 152 forwarding of packets along a unicast route. With BIER-TE, each 153 bit in a bitStrings represents a particular intermediate link. 154 This specification introduces a RPL-BIER Non-Storing Mode that 155 applies BIER-TE operations to RPL Non-Storing Mode. 157 This specification provides new signaling in RPL to enable RPL-BIER 158 operations. In addition to classical bitStrings, this specification 159 proposes an new technique that derives from Bloom Filters. This 160 technique provides elasticity to the size of the bitString, which is 161 not constrained to a fixed number of entries, and a trade-off between 162 the number of bits that are needed for routing and the chances to 163 waste energy forwarding down a path where no target exist. The Bloom 164 Filters mechanism applies to RPL-BIER in both modes of operations. 166 In order to carry routing information in a concise fashion in a Low- 167 Power Wireless Personal Area Network (6LoWPAN) for Route-Over use 168 cases, the 6LoWPAN adaptation layer framework [RFC4944] [RFC6282] was 169 extended with the 6LoWPAN Routing Header (6LoRH) specification 170 [RFC8138], which uses the 6LoWPAN Paging Dispatch [RFC8025]. The 171 original specification includes the formats necessary for RPL such as 172 the Source Route Header (SRH) and is intended to be extended for 173 additional routing artifacts. A companion document to this, the 174 "6loRH for BitStrings" [I-D.thubert-6lo-bier-dispatch], 175 specification, proposes new 6LoRH formats to enable the concise 176 encoding of the BIER bitStrings and of the Bloom Filters described 177 therein. 179 In the current practice of LLN networks, the Non-Storing Mode is 180 largely favored, because it does not place a restriction on how large 181 a network formed of a particular device can become. One major 182 benefit of introducing bitStrings is that the amount of state that is 183 required for routing in Storing Mode is no more growing in the order 184 of the total number of nodes in the network but linearly with the 185 number of children attached to the RPL router. In other words, the 186 maximum number of children that a router is willing to accept 187 determines both the size of the Neighbor Cache for 6LoWPAN Neighbor 188 Discovery (6LoWPAN ND) [RFC6775][I-D.ietf-6lo-rfc6775-update] and the 189 size of the routing table that is required in RPL-BIER Storing Mode. 191 2. Terminology 193 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 194 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 195 "OPTIONAL" in this document are to be interpreted as described in 196 [RFC2119]. 198 The Terminology used in this document is consistent with and 199 incorporates that described in Terms Used in Routing for Low-Power 200 and Lossy Networks (LLNs). [RFC7102]. 202 Other terms in use in LLNs are found in Terminology for Constrained- 203 Node Networks [RFC7228]. 205 The term "byte" is used in its now customary sense as a synonym for 206 "octet". 208 "RPL", "RPL Packet Information" (RPI) and "RPL Instance" are defined 209 in the "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks" 210 [RFC6550] specification. 212 The terms Bit-Forwarding Egress Routers (BFR), BFR-id and bitString 213 are defined in [RFC8279]. A bitString indicates a continuous 214 sequence of bits indexed by an offset in the sequence. The leftmost 215 bit is bit 0 and corresponds to the value 0x80 of the leftmost byte 216 in the BitString. With this specification, a bitString maybe used to 217 encode one or more unsigned integer(s) as a bit position in the 218 bitString (bit-by-bit), or a Bloom filter. 220 3. Applicability 222 BIER and other bit-indexed methods that would leverage bitStrings 223 will generally require additional information in the packet to 224 complement the bitString. For instance, BIER has the concept of a 225 BFR-id and an Entropy value in the BIER header. Since those 226 additional fields depend on the bit-indexed method, they are expected 227 to be transported separately from the bitString. This specification 228 concentrates on the bitString and a group identifier which enables a 229 network to grow beyond the size of one bitString. 231 TBD Do we need entropy ? 233 4. Extensions to RFC 6550 235 This specification introduces two new modes of operation for RPL, the 236 RPL-BIER Non-Storing Mode which is discussed in Section 4.1.1 and the 237 RPL-BIER Storing Mode which is discussed in Section 4.1.2. A new 238 Control Message Options (CMO) is introduced to transport the 239 bitStrings in Section 4.2. 241 4.1. RPL-BIER MOPs 243 In RPL-BIER modes of operation, one or more RPL Target Option are 244 replaced by a new BitString Information Option which represent the 245 advertised target(s) by a combination of a bitString and control 246 information. 248 4.1.1. RPL-BIER Non-Storing Mode 250 In Non-Storing RPL-BIER, a bit in classical BIER bit-by-bit 251 bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see 252 Section 6.2) is associated to a next-hop from the perspective of an 253 intermediate router. RPL Non-Storing Mode DAO messages are used to 254 advertise the relation between a target and its parent (transit) 255 directly to the root. 257 If multiple Targets Options were to be placed consecutively to 258 factorize a Transit Information Option (TIO) in a classical RPL Non- 259 Storing Mode DAO message, they are replaced by a single BIO with the 260 aggregated bitString that represents all these targets. 262 4.1.2. RPL-BIER Storing Mode 264 In RPL-BIER Storing Mode, a bit in classical BIER Bit-by-bit 265 bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see 266 Section 6.2) is associated to a final destination. RPL Storing Mode 267 DAO messages are used to advertise recursively the targets to the 268 parent(s) all the way to the root. 270 The BitString Information Option(s) in the DAO message contain 271 collectively an aggregated bitString that represents the advertising 272 node and all of its descendants. Parents save the bitString per 273 child, and use it to forward down the DODAG as discussed in 274 Section 6.1.3. 276 The Transit Information Option is not used. The lack of transit 277 information is compensated by a more frequent transmission of DAO 278 messages and a full use of the RPL data plane loop avoidance and 279 inconsistency detection mechanisms (section 11.2 of [RFC6550]), in 280 collaboration with a periodic 6LoWPAN ND (re)registration that 281 maintains the 6LBR and the root aware of which devices are actually 282 present in the network with the associated lifetime and sequence 283 information. 285 4.2. BitString Information 287 Section 6.7 of [RFC6550] specifies optional CMOs to be placed in RPL 288 messages such as the Destination Advertisement Object (DAO) message. 289 The RPL Target Option and the Transit Information Option (TIO) are 290 such optional fields; the former indicates a node to be reached and 291 the latter specifies a parent that can be used to reach that node. 292 Options may be factorized; one or more contiguous TIOs apply to the 293 one or more contiguous Target options that immediately precede the 294 TIOs in the RPL message. 296 This specification introduces a new CMO, the BitString Information 297 option (BIO). A BIO is used as an alternate to one or more Target 298 Option(s) in Storing and Non-Storing Mode DAOs using bit-by-bit 299 bitStrings, and its format is as follows: 301 0 1 2 3 302 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 304 | Type = 0x0B | Option Length | BitStringType | Group ID | 305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 306 | | 307 + + 308 . . 309 . BitString . 310 . . 311 + + 312 | | 313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 Figure 1: BitString Information option format 317 Option Type: 0x0B (to be confirmed by IANA) 318 Option Length: In bytes; variable, depending on the Type. 319 BitString Type: Indicates the size of the bitString field as 320 indicated in Table 1 below. 322 +----------------+----------------+ 323 | BitString Type | BitString Size | 324 +----------------+----------------+ 325 | 15 | 8 bits | 326 +----------------+----------------+ 327 | 16 | 16 bits | 328 +----------------+----------------+ 329 | 17 | 48 bits | 330 +----------------+----------------+ 331 | 18 | 96 bits | 332 +----------------+----------------+ 333 | 19 | 160 bits | 334 +----------------+----------------+ 336 Group ID : 8-bit unsigned integer. The Group ID for the bit-by- 337 bit bitString. 338 BitString: 8 to 160 bits, depending on the Type. 340 5. Updating the 6LoWPAN Framework 342 5.1. Extensions to RFC 6775 344 It is noted that RPL does not provide a Duplicate Address Detection 345 (DAD) and relies on 6LoWPAN ND to ensure that addresses are unique 346 within the network. For that purpose, a 6LoWPAN Border Router (6LBR) 347 maintains the list of addresses that are currently in use in the 348 network that it serves. In the case of a RPL LLN, the 6LBR is 349 typically collocated with the RPL root, and serves the RPL DODAG. 350 With 6LoWPAN ND[RFC6775] [I-D.ietf-6lo-rfc6775-update], a Duplicate 351 Address Request (DAR) / Duplicate Address Confirmation (DAC) exchange 352 is used to perform the DAD operation . Scalability is achieved by 353 federating multiple DODAGs with IPv6 Backbone Routers (6BBRs) 354 [I-D.ietf-6lo-backbone-router]. 356 In that context, it makes sense to also leverage the 6LBR to ensure 357 that a tuple (groupID, bitString) is assigned unequivocally to an 358 IPv6 address for the bit-by-bit operation. This specification 359 extends the role of a 6LBR to 1) assign the tuple to the IPv6 address 360 and 2) resolve an IPv6 address into a tuple. To achieve this, RFC 361 6775 is updated as follows: 363 o A BIER Address Resolution (BAR) / BIER Address Confirmation (BAC) 364 exchange is introduced for the purpose of the bitString lookup 365 operation (see Section 6.1.1). 366 o A new Bit Position Option (BPO) is introduced to carry the 367 corresponding bit position bitString in 6LoWPAN ND exchanges. The 368 BPO is transported in BAC, NA and DAC messages in response to BAR, 369 NS and DAR messages, respectively (see Section 5.3.1). 371 5.2. Extensions to RFC 6282 373 This specification also extends the 6LoWPAN framework with the 374 capability to transform an address into a tuple (Control field, 375 bitString) as part of the 6LoWPAN Header Compression [RFC6282] 376 (6LoWPAN HC). Since the 6LBR and the Header Compression functions 377 are typically collocated, the latter may exploit local tables built 378 by the former to map a destination IPv6 address into a bitString. 380 In Storing Mode, P2P stretched routing via a common parent can be 381 obtained if the destination is expressed as a tuple (Control field, 382 bitString). This can be achieved with a BAR/BAC exchange with the 383 6LBR. 385 5.3. New Neighbor Discovery Options and Messages 387 In order to allocate and lookup a bitString, this specification 388 extends 6LoWPAN ND with the following new messages and formats. 390 5.3.1. 6LoWPAN ND Bit Position Option 392 The Bit Position Option (BPO) is intended to be used to return a 393 bitString and related information in 6LoWPAN ND BA, DAC and BAC 394 messages with a Status of 0 indicating success, the NA and DAC 395 messages transporting an Address Registration Option (ARO) indicating 396 the IPv6 address that is mapped with the bit position. Its format is 397 as follows: 399 0 1 2 3 400 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 402 | Type | Length | Group ID | Bit Position | 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 | Reserved | 405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 Figure 2: Bit Position Option format 409 Option Fields 411 Type: 38 (to be confirmed by IANA) 412 Length: 8-bit unsigned integer. The length of the option 413 (including the type and length fields) in units of 8 414 bytes. The Length MUST be set to 1. 415 Group ID: 8-bit unsigned integer. The GroupID for the bit-by- 416 bit bitString. 417 Bit Position: 8-bit unsigned integer. The offset in the the bit- 418 by-bit bitString. 420 5.3.2. Address Mapping Message 422 For the multihop lookup exchanges between a 6LR that needs to perform 423 a Header Compression including the bitString for the destination, and 424 its 6LBR, which knows if the mapping exists and what it is, this 425 specification introduces two new ICMPv6 message called the BIER 426 Address Resolution (BAR) and the BIER Address Confirmation (BAC). We 427 avoid reusing the NS and NA messages for this purpose, since these 428 messages are not subject to the hop limit=255 check as they are 429 forwarded by intermediate 6LRs. 431 The BAR and BAC use the same ICMPv6 type value which this 432 specification, allocates for a generic Address Mapping service, but 433 use different Codes. This is done to save addressable space in the 434 ICMPv6 type values which is getting crowded, and because it is 435 expected that in the future, other mapping techniques may be needed 436 as well. 438 The Status field and Information Lifetime are not meaningful in the 439 BAR message. When and only when the BAC message carries a status of 440 0, indicating success, the Information Lifetime must contain valid 441 information and the message must carry a Bit Position Option 442 (Section 5.3.1). 444 0 1 2 3 445 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 | Type | Code | Checksum | 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Status | Reserved | Information Lifetime | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | | 452 + + 453 | | 454 + Looked-up Address + 455 | | 456 + + 457 | | 458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 460 Figure 3: Address Mapping Message format 462 Message Fields 464 Type: 160 (to be confirmed by IANA) 465 Code: 8-bit unsigned integer. 1 for BAR and 2 for BAC. 466 Other values are reserved. 467 Checksum:: The ICMP checksum. See [RFC4443]. 469 Status: 8-bit unsigned integer. Indicates the status of the 470 lookup in the BAC. See Table 2 below. 472 +--------+--------------------------------------------+ 473 | Status | Description | 474 +--------+--------------------------------------------+ 475 | 0 | Success | 476 +--------+--------------------------------------------+ 477 | 1 | Looked-up Address not Found | 478 +--------+--------------------------------------------+ 479 | 2..255 | Allocated using Standards Action [RFC5226] | 480 +--------+--------------------------------------------+ 482 Information Lifetime: 16-bit unsigned integer. The length of time 483 in units of 60 seconds (relative to the time the 484 packet is received) that this mapping information is 485 valid. A value of all zero bits (0x0) assumes a 486 default value of 10,000 (~one week). 487 Looked-up Address: 128-bit field. Carries the IPv6 address that is 488 being mapped. 490 6. BitString formats 492 This specification introduces two BitString formats, the bit-by-bit 493 and the Bloom Filter. 495 6.1. Bit-by-bit BitStrings 497 In the bit-by-bit case, each bit is mapped in an unequivocal fashion 498 with a single addressable resource in the network. In RPL-BIER 499 Storing Mode, this is an IPv6 address as advertised in RPL Storing 500 Mode DAO messages, whereas in RPL-BIER Non-Storing Mode, this is a 501 parent-child relationship as advertised in RPL Non-Storing Mode DAO 502 messages. 504 if every node in a large network is given one or more bits in a bit- 505 by-bit bitString, then the bitString may grow very large and lead to 506 undesirably large overhead in the data plane. BIER allows to divide 507 a potentially the very large abstract bitString into segments, aka 508 groups, indexed by a groupID. 510 In the protocol elements that use a bitString, only the relevant 511 group(s) are transported, and the advertised bitString is in fact the 512 segment that corresponds to the groupID. It results that a bit 513 position in the large abstract bitString is advertised either as the 514 tuple (groupID, segment) or the tuple (groupID, bit position within 515 segment). 517 For simplicity, when dealing with protocol elements, the 518 specification uses the term bitString to refer to the tuple (groupID, 519 segment) and a bitwise operation between bitStrings is really a 520 bitwise operation between segments of a same groupID. 522 TBD: do we allow multiple (groupID, bitString) tuples in one packet? 524 6.1.1. Allocating a Bit Position in a Bit-by-bit BitString 526 Several methods may be used to associate a bit in a biString to an 527 IPv6 address. In order to guarantee interoperability, this 528 specification RECOMMENDS that all implementations provide at least 529 the method described therein. 531 With 6LoWPAN ND, a 6LoWPAN Node (6LN) registers with address(es) to 532 one or more 6LoWPAN Router [RFC6775] to perform Duplicate Address 533 Detection (DAD). As part of the DAD process, the 6LN validates that 534 a Global Unicast Address (GUA) or a Unique Local Address (ULA) is 535 effectively unique using a unicast DAR/DAC exchange with the 6LBR 536 (this procedure is updated in [I-D.ietf-6lo-rfc6775-update]). 538 In a network that supports this specification, the 6LBR maintains a 539 configurable number of groups (up to 32, indexed by groupID), and for 540 each group, it maintains a pool of free bit positions. Upon a new 541 registration, the 6LBR selects a groupID and a free bit position and 542 associates it to the IPv6 address. 544 The bitString Size in any given group should be configurable. The 545 policy for selecting the groupID for a new registration is left to 546 implementation. It is noted that in large networks that require 547 multiple groups, associating groups with immediate children of the 548 root may be an option to limit the number of groups that the RPL 549 routers must be aware of. 551 If the 6LBR accepts the registration, then it returns a DAC message 552 with a status of 0 indicating success, adding a 6LoWPAN ND Bit 553 Position Option (Section 5.3.1) to the DAC message to indicate the 554 groupID and bit. 556 The 6LR maintains a binding cache entry (BCE) for the 6LN based on 557 successful DAC messages. With this specification, the 6LR also 558 stores the matching between the address and the bitString and uses it 559 for searching its children when forwarding packets in Non-Storing 560 Mode (see Section 6.1.3). 562 If the 6LN child does not support the BIER encoding 563 (e.g.[I-D.thubert-6lo-bier-dispatch]), then the packet is converted 564 in a format that the child supports (e.g.[RFC8138]). 566 6.1.2. Aggregation of Bit-by-bit BitStrings 568 BitStrings are aggregated by a 'OR' operation so that all the bits 569 that are set in either bitString is set in the resulting bitString. 570 In the concise form of a tuple (groupID, bitString), the aggregation 571 is done on a group-by-group basis, between segments of a same group. 573 In RPL-BIER Storing Mode, the bit-by-bit BitStrings are passed from 574 child to parent using DAO messages, in a fashion similar to RPL 575 Storing Mode [RFC6550]. The BitString Information option (Figure 1) 576 is used in replacement of the Target option. A DAO message contains 577 one BIO per group, and the parent that receives the messages 578 associates the BIO information to the advertising child. In order to 579 build a DAO message, the parent regenerates its own BIO, one per 580 group, by aggregating the bitStrings from all of its children with 581 its own, and places the resulting BIOs in the DAO message. 583 6.1.3. Forwarding Based on Bit-by-bit BitStrings 585 Forwarding is based on matching a bitString in a packet with those of 586 children. For unicast packets, only one matching child gets the 587 packet. For multicast packets, all matching children get a copy. 588 Matches are found by scanning all children and performing bitwise 589 operations as follows. 591 In order to search for a match, a reference bitString is initialized 592 with the destination bitString in the packet. A match is found with 593 a child if the bitwise 'AND' between the reference bitString and the 594 bitString stored for that child does not result in a NULL bitString 595 of all zeroes. 597 In Non-Storing Mode, a packet is copied to all matching children, 598 which are found by trying all children. 600 In Non-Storing Mode, if a child is selected for forwarding, then an 601 'XOR' operation is performed between the reference bitString and the 602 bitString resulting from the 'AND' operation. If the 'XOR' operation 603 does not result in a NULL bitString, denoting that more children 604 should get the packet, then the result of the 'XOR' operation becomes 605 the new reference bitString and the search continues. The 'XOR' 606 operation allows to stop the search loop as soon as all matches are 607 found; it also avoids forwarding twice to a same destination along 608 different downwards path in the DODAG. 610 6.1.4. Reliable Multicast based on Bit-by-bit BitStrings 612 Multicast from the root to a a collection of target 6LNs can be made 613 reliable with the following operation: 615 A multicast packet is identified by a unique packetID which is also 616 found in the acknowledgments. The root signals the set of targets 617 with a destination bitString that has the bits set for each of them, 618 and the message is forwarded as described on Section 6.1.3. 620 Listeners acknowledge with an acknowledgment packet that contains the 621 same information, the packetID and the bitString representing the 622 listener. The bitStrings in acknowledgment packets are aggregated 623 recursively on the way back as indicated in Section 6.1.2. 625 The root aggregates the bitStrings from its children into one 626 acknowledgment bitString. It then checks that the acknowledgment 627 bitString is correct, by and 'AND' operation with the destination 628 bitString that should result in the acknowledgment bitString. If 629 this is not the case, bits that are set in the acknowledgment 630 bitString and not in the destination bitString are in the 631 acknowledgment bitString. 633 The root generates the bitString of the devices that did not 634 acknowledge the multicast message by a bitwise 'XOR' operation 635 between the destination bitString and the acknowledgment bitString, 636 and may use it to selectively retry the multicast. 638 6.2. Bloom Filters 640 A Bloom Filter can be seen as an additional compression technique for 641 the bitString representation. A Bloom Filter may generate false 642 positives, which, in the case of BIER, result in undue forwarding of 643 a packet down a path where no listener exists. 645 As an example, the Constrained-Cast [I-D.bergmann-bier-ccast] 646 specification employs Bloom Filters as a compact representation of a 647 match or non-match for elements in a set that may be larger than the 648 number of bits in the BitString. 650 In the case of a Bloom Filter, a number of Hash functions must be run 651 to obtain a multi-bit signature of an encoded element. This 652 specification uses the 5-bits Control field to signal an Identifier 653 of the set of Hash functions being used to generate a certain 654 bitString, so as to enable the migration from a set of Hash functions 655 to the next. 657 6.2.1. Computing and Saving Bloom Filters 659 6.2.2. Forwarding based on Bloom Filters 661 6.2.3. Hash Functions Distribution 663 7. Implementation Status 665 TBD 667 8. Security Considerations 669 TBD 671 9. IANA Considerations 673 This document extends the IANA registry created by RFC 6550 for RPL 674 Control Codes as follows: 676 +------+-------------+---------------+ 677 | Code | Description | Reference | 678 +------+-------------+---------------+ 679 | 0x0B | bitString | This document | 680 +------+-------------+---------------+ 682 RPL Control Codes 684 This document is updating the registry created by RFC 6550 for the 685 RPL 3-bit Mode of Operation (MOP) as follows: 687 +-----------+---------------------------------------+---------------+ 688 | MOP value | Description | Reference | 689 +-----------+---------------------------------------+---------------+ 690 | 6 | RPL-BIER Non-Storing Mode of | This document | 691 | | operation | | 692 | | | | 693 | 7 | RPL-BIER Storing Mode of operation | This document | 694 +-----------+---------------------------------------+---------------+ 696 DIO Mode of operation 698 10. Acknowledgments 700 11. References 701 11.1. Normative References 703 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 704 Requirement Levels", BCP 14, RFC 2119, 705 DOI 10.17487/RFC2119, March 1997, 706 . 708 [RFC4443] Conta, A., Deering, S., and M. Gupta, Ed., "Internet 709 Control Message Protocol (ICMPv6) for the Internet 710 Protocol Version 6 (IPv6) Specification", STD 89, 711 RFC 4443, DOI 10.17487/RFC4443, March 2006, 712 . 714 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 715 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 716 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 717 Low-Power and Lossy Networks", RFC 6550, 718 DOI 10.17487/RFC6550, March 2012, 719 . 721 [RFC6775] Shelby, Z., Ed., Chakrabarti, S., Nordmark, E., and C. 722 Bormann, "Neighbor Discovery Optimization for IPv6 over 723 Low-Power Wireless Personal Area Networks (6LoWPANs)", 724 RFC 6775, DOI 10.17487/RFC6775, November 2012, 725 . 727 [RFC8200] Deering, S. and R. Hinden, "Internet Protocol, Version 6 728 (IPv6) Specification", STD 86, RFC 8200, 729 DOI 10.17487/RFC8200, July 2017, 730 . 732 [RFC8279] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., 733 Przygienda, T., and S. Aldrin, "Multicast Using Bit Index 734 Explicit Replication (BIER)", RFC 8279, 735 DOI 10.17487/RFC8279, November 2017, 736 . 738 11.2. Informative References 740 [I-D.bergmann-bier-ccast] 741 Bergmann, O., Bormann, C., Gerdes, S., and H. Chen, 742 "Constrained-Cast: Source-Routed Multicast for RPL", 743 draft-bergmann-bier-ccast-02 (work in progress), October 744 2016. 746 [I-D.eckert-bier-te-arch] 747 Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic 748 Engineering for Bit Index Explicit Replication BIER-TE", 749 draft-eckert-bier-te-arch-06 (work in progress), November 750 2017. 752 [I-D.ietf-6lo-backbone-router] 753 Thubert, P., "IPv6 Backbone Router", draft-ietf-6lo- 754 backbone-router-05 (work in progress), January 2018. 756 [I-D.ietf-6lo-rfc6775-update] 757 Thubert, P., Nordmark, E., Chakrabarti, S., and C. 758 Perkins, "An Update to 6LoWPAN ND", draft-ietf-6lo- 759 rfc6775-update-11 (work in progress), December 2017. 761 [I-D.ietf-roll-aodv-rpl] 762 Anamalamudi, S., Zhang, M., Sangi, A., Perkins, C., and S. 763 Anand, "Asymmetric AODV-P2P-RPL in Low-Power and Lossy 764 Networks (LLNs)", draft-ietf-roll-aodv-rpl-02 (work in 765 progress), September 2017. 767 [I-D.thubert-6lo-bier-dispatch] 768 Thubert, P., Brodard, Z., Jiang, H., and G. Texier, "A 769 6loRH for BitStrings", draft-thubert-6lo-bier-dispatch-04 770 (work in progress), January 2018. 772 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 773 "Transmission of IPv6 Packets over IEEE 802.15.4 774 Networks", RFC 4944, DOI 10.17487/RFC4944, September 2007, 775 . 777 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 778 IANA Considerations Section in RFCs", RFC 5226, 779 DOI 10.17487/RFC5226, May 2008, 780 . 782 [RFC6282] Hui, J., Ed. and P. Thubert, "Compression Format for IPv6 783 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 784 DOI 10.17487/RFC6282, September 2011, 785 . 787 [RFC6997] Goyal, M., Ed., Baccelli, E., Philipp, M., Brandt, A., and 788 J. Martocci, "Reactive Discovery of Point-to-Point Routes 789 in Low-Power and Lossy Networks", RFC 6997, 790 DOI 10.17487/RFC6997, August 2013, 791 . 793 [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and 794 Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January 795 2014, . 797 [RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for 798 Constrained-Node Networks", RFC 7228, 799 DOI 10.17487/RFC7228, May 2014, 800 . 802 [RFC8025] Thubert, P., Ed. and R. Cragie, "IPv6 over Low-Power 803 Wireless Personal Area Network (6LoWPAN) Paging Dispatch", 804 RFC 8025, DOI 10.17487/RFC8025, November 2016, 805 . 807 [RFC8138] Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie, 808 "IPv6 over Low-Power Wireless Personal Area Network 809 (6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138, 810 April 2017, . 812 Author's Address 814 Pascal Thubert (editor) 815 Cisco Systems, Inc 816 Building D 817 45 Allee des Ormes - BP1200 818 MOUGINS - Sophia Antipolis 06254 819 FRANCE 821 Phone: +33 497 23 26 34 822 Email: pthubert@cisco.com