idnits 2.17.1 draft-ietf-roll-ccast-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 30, 2017) is 2367 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) == Missing Reference: 'RFC-XXXX' is mentioned on line 349, but not defined Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Roll Working Group O. Bergmann 3 Internet-Draft C. Bormann 4 Intended status: Standards Track S. Gerdes 5 Expires: May 3, 2018 Universitaet Bremen TZI 6 H. Chen 7 Huawei Technologies 8 October 30, 2017 10 Constrained-Cast: Source-Routed Multicast for RPL 11 draft-ietf-roll-ccast-01 13 Abstract 15 This specification defines a protocol for forwarding multicast 16 traffic in a constrained node network employing the RPL routing 17 protocol in non-storing mode. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on May 3, 2018. 36 Copyright Notice 38 Copyright (c) 2017 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 54 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. The BIER Approach . . . . . . . . . . . . . . . . . . . . . . 3 56 3. The Constrained-Cast Approach . . . . . . . . . . . . . . . . 3 57 4. False Positives . . . . . . . . . . . . . . . . . . . . . . . 4 58 5. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 5.1. Multicast Listener Advertisement Object (MLAO) . . . . . 4 60 5.2. Routing Header . . . . . . . . . . . . . . . . . . . . . 5 61 6. Implementation . . . . . . . . . . . . . . . . . . . . . . . 7 62 7. Benefits . . . . . . . . . . . . . . . . . . . . . . . . . . 7 63 8. Security Considerations . . . . . . . . . . . . . . . . . . . 7 64 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 65 9.1. ICMPv6 Parameter Registration . . . . . . . . . . . . . . 8 66 9.2. Critical 6LowPAN Routing Header Type Registration . . . . 8 67 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 68 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 69 11.1. Normative References . . . . . . . . . . . . . . . . . . 8 70 11.2. Informative References . . . . . . . . . . . . . . . . . 9 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 73 1. Introduction 75 As defined in [RFC6550], RPL Multicast assumes that the RPL network 76 operates in Storing Mode. Multicast DAOs are used to indicate 77 subscription to multicast address to a parent; these DAOs percolate 78 up and create bread-crumbs. This specification, although part of RFC 79 6550, appears to be incomplete and untested. More importantly, 80 Storing Mode is not in use in constrained node networks outside 81 research operating environments. 83 The present specification addresses multicast forwarding for RPL 84 networks in the much more common Non-Storing Mode. Non-Storing is 85 based on the root node adding source-routing information to downward 86 packets. Evidently, to make this work, RPL multicast needs to 87 source-route multicast packets. A source route here is a list of 88 identifiers to instruct forwarders to relay the respective IP 89 datagram. 91 As every forwarder in an IP-based constrained node network has at 92 least one network interface, it is straight-forward to use the 93 address of an outgoing interface as identifiers in this source-route. 94 (Typically, this is a globally unique public address of the node's 95 only network adapter.) 96 The source-route subsets the whole set of potential forwarders 97 available in the RPL DODAG to those that need to forward in order to 98 reach known multicast listeners. 100 Including an actual list of outgoing interfaces is rarely applicable, 101 as this is likely to be a large list of 16-byte IPv6 addresses. Even 102 with [RFC6554] style compression, the size of the list becomes 103 prohibitively quickly. 105 1.1. Terminology 107 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 108 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 109 "OPTIONAL" in this document are to be interpreted as described in BCP 110 14 [RFC2119] [RFC8174] when, and only when, they appear in all 111 capitals, as shown here. 113 In this specification, the term "byte" is used in its now customary 114 sense as a synonym for "octet". 116 All multi-byte integers in this protocol are interpreted in network 117 byte order. 119 2. The BIER Approach 121 Bit-Indexed Explicit Replication [I-D.ietf-bier-architecture] lists 122 all egress routers in a bitmap included in each multicast packet. 123 This requires creating a mostly contiguous numbering of all egress 124 routers; more importantly, BIER requires the presence of a network 125 map in each forwarders to be able to interpret the bitmap and map it 126 to a set of local outgoing interfaces. 128 3. The Constrained-Cast Approach 130 Constrained-Cast employs Bloom Filters [BLOOM] as a compact 131 representation of a match or non-match for elements in a large set: 132 Each element to be included is hashed with multiple hash functions; 133 the result is used to index a bitmap and set the corresponding bit. 134 To check for the presence of an element, the same hash functions are 135 applied to obtain bit positions; if all corresponding bits are set, 136 this is used to indicate a match. (Multiple hash functions are most 137 easily obtained by adding a varying seed value to a single hash 138 algorithm.) 140 By including a bloom filter in each packet that matches all outgoing 141 interfaces that need to forward the packet, each forwarder can 142 efficiently decide whether (and on which interfaces) to forward the 143 packet. 145 4. False Positives 147 Bloom filters are probabilistic. A false positive might be 148 indicating a match where the bits are set by aliasing of the hash 149 values. In case of Constrained-Cast, this causes spurious 150 transmission and wastes some energy and radio bandwidth. However, 151 there is no semantic damage (hosts still filter out unneeded 152 multicasts). The total waste in energy and spectrum can be 153 visualized as the false-positive-rate multiplied by the density of 154 the RPL network. A network can easily live with a significant 155 percentage of false positives. By changing the set of hash functions 156 (i.e., seed) over time, the root can avoid a single node with a false 157 positive to become an unnecessary hotspot for that multicast group. 159 5. Protocol 161 The protocol uses DAO-like "MLAO" messages to announce membership to 162 the root as specified in Section 5.1. 164 For downward messages, the root adds a new routing header that 165 includes a hash function identifier and a seed value; another one of 166 its fields gives the number of hash functions (k) to ask for k 167 instances of application of the hash function, with increasing seed. 168 The format of the new routing header is specified in Section 5.2. 170 Typical sizes of the bloom filter bitmap that the root inserts into 171 the packet can be 64, 128, or 256 bit, which may lead to acceptable 172 false positive rates if the total number of forwarders in the 10s and 173 100s. (To do: write more about the math here. Note that this number 174 tallies forwarding routers, not end hosts.) 176 A potential forwarder that receives a multicast packet adorned with a 177 constrained-cast routing header first checks that the packet is 178 marked with a RPL rank smaller than its own (loop prevention). If 179 yes, it then forwards the packet to all outgoing interfaces that 180 match the bloom filter in the packet. 182 5.1. Multicast Listener Advertisement Object (MLAO) 184 The header format of the MLAO is depicted in Figure 1. The basic 185 structure of the MLAO message is similar to the RPL Destination 186 Advertisement Object (DAO). In particular, it starts with RPL ICMP 187 base header with a type value of 155 and the code {IANA TBD1} (MLAO), 188 followed by the Checksum, RPLInstanceID, parameters and flags as in a 189 DAO. 191 0 1 2 3 192 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 193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 194 | Type = 0x05 | Option Length | Reserved | Prefix Length | 195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 197 + + 198 | Group Address | 199 . . 200 . . 201 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 203 Figure 1: RPL Target Option for MLAO 205 The group address field indicates the group that the sender of the 206 MLAO is interested in. This field usually contains a 128 bit IPv6 207 multicast group address. Shorter group identifiers could be used 208 together with a protocol for explicit creation of groups. The MLAO 209 message must have at least one RPL target option to specify the 210 address of the listener that has generated the MLAO. The message is 211 directed to the global unicast address of the DODAG root and travels 212 upwards the routing tree. 214 Note: It has been suggested to use the RPL Transit Option (Type 215 0x06) instead as it is used in Non-Storing mode to inform the 216 DODAG root of path attributes. Specifically, this option can be 217 used to limit the subscription by providing a proper Path 218 Lifetime. 220 5.2. Routing Header 222 This specification uses a new Soure Routing 6LowPAN Routing Header 223 (SRH-6LoRH) type [RFC8138] to convey the Bloom filter that describes 224 the source route for the IPv6 multicast packet to take within the RPL 225 routing tree. The 6LoRH Type for this Constrained Cast Routing 226 Header (CCRH) is set to TBD7. Figure 2 depicts the format of this 227 new routing header. 229 0 1 2 3 230 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 231 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 232 |1|0|0|rsv|BSize| 6LoRH Type 7 | Func set | Modulus | 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Sequence Number | 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 | | 237 . . 238 . Filter data . 239 . . 240 | | 241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 243 Figure 2: Routing header 245 rsv: This field is reserved for future use an MUST be set to 0 when 246 sending a packet containing a CCRH. A receiver MUST ignore the 247 value of the rsv field. 249 BSize: Specifies the size of the included Bloom filter. Currently, 250 only 64 bits, 128 bits, or 256 bits are supported. The BSize 251 field is encoded as specified in Table 1. 253 +-------------+--------------------+ 254 | BSize value | Filter Size (Bits) | 255 +-------------+--------------------+ 256 | 0 | 64 | 257 | 1 | 128 | 258 | 2 | 256 | 259 +-------------+--------------------+ 261 Table 1: Possible Bloom Filter Lengths 263 Func set: The set of hash functions used to generate the Filter data 264 value. 266 Note: As the function set contains a combination of several distinct 267 hash functions, it is currently unclear if 8 bits number space is 268 large enough. 270 Modulus: The modulus that is used by the hash functions, minus 64 271 (the minimum filter data size that can be used). The DAG root 272 chooses the modulus (and thus the filter data size) to achieve its 273 objectives for false positive rates (Section 4). 275 Sequence Number: 32 bits sequence number. The number space is 276 unique for a sequence of multicast datagrams for a specific group 277 that arrive at the DAG root on their way up. The DAG root 278 increments the number for each datagram it sends down the 279 respective DODAG. 281 Filter data: A bit field that indicates which nodes should relay 282 this multicast datagram. The length of this field is a multiple 283 of 8 bytes (2^(BSize + 3) bytes). The actual length is derived 284 from the contents of the field BSize. 286 6. Implementation 288 In 2013, Constrained-Cast was implemented in Contiki. It turns out 289 that forwarders can compute the hash functions once for their 290 outgoing interfaces and then cache them, simply bit-matching their 291 outgoing interface hash bits against the bloom filter in the packet 292 (a match is indicated when all bits in the outgoing interface hash 293 are set in the bloom filter). 295 The Root computes the tree for each multicast group, computes the 296 bloom filter for it, caches these values, and then simply adds the 297 bloom filter routing header to each downward packet. For adding a 298 new member, the relevant outgoing interfaces are simply added to the 299 bloom filter. For removing a leaving member, however, the bloom 300 filter needs to be recomputed (which can be sped up logarithmically 301 if desired). 303 7. Benefits 305 Constrained-Cast: 307 o operates in Non-Storing Mode, with the simple addition of a 308 membership information service; 310 o performs all routing decisions at the root. 312 Further optimizations might include using a similar kind of bloom 313 filter routing header for unicast forwarding as well (representing, 314 instead of the outgoing interface list, a list of children that 315 forwarding parents need to forward to). 317 8. Security Considerations 319 TODO 321 9. IANA Considerations 323 The following registrations are done following the procedure 324 specified in [RFC6838]. 326 Note to RFC Editor: Please replace all occurrences of "[RFC-XXXX]" 327 with the RFC number of this specification and "TBD1" with the code 328 selected for TBD1 below and "TBD7" with the code selected for TBD7. 330 9.1. ICMPv6 Parameter Registration 332 IANA is requested to add the following entry to the Code fields of 333 the RPL Control Codes registry: 335 +------+------+------------+ 336 | Code | Name | Reference | 337 +------+------+------------+ 338 | TBD1 | MLAO | [RFC-XXXX] | 339 +------+------+------------+ 341 9.2. Critical 6LowPAN Routing Header Type Registration 343 IANA is requested to add the following entries to the Critical 344 6LowPAN Routing Header Type Registration registry: 346 +-------+----------------------+------------+ 347 | Value | Name | Reference | 348 +-------+----------------------+------------+ 349 | TBD7 | CCast Routing Header | [RFC-XXXX] | 350 +-------+----------------------+------------+ 352 10. Acknowledgments 354 Thanks to Yasuyuki Tanaka for valuable comments. 356 This work has been supported by Siemens Corporate Technology. 358 11. References 360 11.1. Normative References 362 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 363 Requirement Levels", BCP 14, RFC 2119, 364 DOI 10.17487/RFC2119, March 1997, . 367 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 368 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 369 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 370 Low-Power and Lossy Networks", RFC 6550, 371 DOI 10.17487/RFC6550, March 2012, . 374 [RFC8138] Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie, 375 "IPv6 over Low-Power Wireless Personal Area Network 376 (6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138, 377 April 2017, . 379 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 380 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 381 May 2017, . 383 11.2. Informative References 385 [BLOOM] Bloom, B., "Space/time trade-offs in hash coding with 386 allowable errors", ISSN 0001-0782, ACM 387 Press Communications of the ACM vol 13 no 7 pp 422-426, 388 1970, . 390 [I-D.ietf-bier-architecture] 391 Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and 392 S. Aldrin, "Multicast using Bit Index Explicit 393 Replication", draft-ietf-bier-architecture-08 (work in 394 progress), September 2017. 396 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 397 Routing Header for Source Routes with the Routing Protocol 398 for Low-Power and Lossy Networks (RPL)", RFC 6554, 399 DOI 10.17487/RFC6554, March 2012, . 402 [RFC6838] Freed, N., Klensin, J., and T. Hansen, "Media Type 403 Specifications and Registration Procedures", BCP 13, 404 RFC 6838, DOI 10.17487/RFC6838, January 2013, 405 . 407 Authors' Addresses 408 Olaf Bergmann 409 Universitaet Bremen TZI 410 Postfach 330440 411 Bremen D-28359 412 Germany 414 Phone: +49-421-218-63904 415 Email: bergmann@tzi.org 417 Carsten Bormann 418 Universitaet Bremen TZI 419 Postfach 330440 420 Bremen D-28359 421 Germany 423 Phone: +49-421-218-63921 424 Email: cabo@tzi.org 426 Stefanie Gerdes 427 Universitaet Bremen TZI 428 Postfach 330440 429 Bremen D-28359 430 Germany 432 Phone: +49-421-218-63906 433 Email: gerdes@tzi.org 435 Hao Chen 436 Huawei Technologies 437 12, E. Mozhou Rd 438 Nanjing 211111 439 China 441 Phone: +86-25-5662-7052 442 Email: philips.chenhao@huawei.com