idnits 2.17.1 draft-bergmann-bier-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 : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (April 03, 2016) is 2944 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 318, but not defined == Outdated reference: A later version (-08) exists of draft-ietf-bier-architecture-03 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group O. Bergmann 3 Internet-Draft C. Bormann 4 Intended status: Standards Track S. Gerdes 5 Expires: October 5, 2016 Universitaet Bremen TZI 6 H. Chen 7 Huawei Technologies 8 April 03, 2016 10 Constrained-Cast: Source-Routed Multicast for RPL 11 draft-bergmann-bier-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 October 5, 2016. 36 Copyright Notice 38 Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . . . . . 3 58 5. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 5.1. Multicast Listener Advertisement Object (MLAO) . . . . . 4 60 5.2. Routing Header . . . . . . . . . . . . . . . . . . . . . 5 61 6. Implementation . . . . . . . . . . . . . . . . . . . . . . . 6 62 7. Benefits . . . . . . . . . . . . . . . . . . . . . . . . . . 7 63 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 64 8.1. ICMPv6 Parameter Registration . . . . . . . . . . . . . . 7 65 8.2. IPv6 Routing Type Registration . . . . . . . . . . . . . 7 66 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 67 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 68 10.1. Normative References . . . . . . . . . . . . . . . . . . 8 69 10.2. Informative References . . . . . . . . . . . . . . . . . 8 70 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 72 1. Introduction 74 As defined in [RFC6550], RPL Multicast assumes that the RPL network 75 operates in Storing Mode. Multicast DAOs are used to indicate 76 subscription to multicast address to a parent; these DAOs percolate 77 up and create bread-crumbs. This specification, although part of RFC 78 6550, appears to be incomplete and untested. More importantly, 79 Storing Mode is not in use in constrained node networks outside 80 research operating environments. 82 The present specification addresses multicast forwarding for RPL 83 networks in the much more common Non-Storing Mode. Non-Storing is 84 based on the root node adding source-routing information to downward 85 packets. Evidently, to make this work, RPL multicast needs to 86 source-route multicast packets. A source route here is a list of 87 outgoing interfaces, which subsets the whole set of potential 88 forwarders available in the RPL DODAG to those that need to forward 89 in order to reach known multicast listeners. 91 Including an actual list of outgoing interfaces is rarely applicable, 92 as this is likely to be a large list of 16-byte IPv6 addresses. Even 93 with [RFC6554] style compression, the size of the list becomes 94 prohibitively quickly. 96 1.1. Terminology 98 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 99 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 100 document are to be interpreted as described in RFC 2119 [RFC2119]. 102 In this specification, the term "byte" is used in its now customary 103 sense as a synonym for "octet". 105 All multi-byte integers in this protocol are interpreted in network 106 byte order. 108 2. The BIER Approach 110 Bit-Indexed Explicit Replication [I-D.ietf-bier-architecture] lists 111 all egress routers in a bitmap included in each multicast packet. 112 This requires creating a mostly contiguous numbering of all egress 113 routers; more importantly, BIER requires the presence of a network 114 map in each forwarders to be able to interpret the bitmap and map it 115 to a set of local outgoing interfaces. 117 3. The Constrained-Cast Approach 119 Constrained-Cast employs Bloom Filters [BLOOM] as a compact 120 representation of a match or non-match for elements in a large set: 121 Each element to be included is hashed with multiple hash functions; 122 the result is used to index a bitmap and set the corresponding bit. 123 To check for the presence of an element, the same hash functions are 124 applied to obtain bit positions; if all corresponding bits are set, 125 this is used to indicate a match. (Multiple hash functions are most 126 easily obtained by adding a varying seed value to a single hash 127 algorithm.) 129 By including a bloom filter in each packet that matches all outgoing 130 interfaces that need to forward the packet, each forwarder can 131 efficiently decide whether (and on which interfaces) to forward the 132 packet. 134 4. False Positives 136 Bloom filters are probabilistic. A false positive might be 137 indicating a match where the bits are set by aliasing of the hash 138 values. In case of Constrained-Cast, this causes spurious 139 transmission and wastes some energy and radio bandwidth. However, 140 there is no semantic damage (hosts still filter out unneeded 141 multicasts). The total waste in energy and spectrum can be 142 visualized as the false-positive-rate multiplied by the density of 143 the RPL network. A network can easily live with a significant 144 percentage of false positives. By changing the set of hash functions 145 (i.e., seed) over time, the root can avoid a single node with a false 146 positive to become an unnecessary hotspot for that multicast group. 148 5. Protocol 150 The protocol uses DAO-like "MLAO" messages to announce membership to 151 the root as specified in Section 5.1. 153 For downward messages, the root adds a new routing header that 154 includes a hash function identifier and a seed value; another one of 155 its fields gives the number of hash functions (k) to ask for k 156 instances of application of the hash function, with increasing seed. 157 The format of the new routing header is specified in Section 5.2. 159 Typical sizes of the bloom filter bitmap that the root inserts into 160 the packet can be 64, 128, or 256 bit, which may lead to acceptable 161 false positive rates if the total number of forwarders in the 10s and 162 100s. (To do: write more about the math here. Note that this number 163 tallies forwarding routers, not end hosts.) 165 A potential forwarder that receives a multicast packet adorned with a 166 constrained-cast routing header first checks that the packet is 167 marked with a RPL rank smaller than its own (loop prevention). If 168 yes, it then forwards the packet to all outgoing interfaces that 169 match the bloom filter in the packet. 171 5.1. Multicast Listener Advertisement Object (MLAO) 173 The header format of the MLAO is depicted in Figure 1. The basic 174 structure of the MLAO message is similar to the RPL Destination 175 Advertisement Object (DAO). In particular, it starts with RPL ICMP 176 base header with a type value of 155 and the code {IANA TBD1} (MLAO), 177 followed by the Checksum, RPLInstanceID, parameters and flags as in a 178 DAO. A sequence number allows ordering of MLAOs generated by a 179 sender. 181 0 1 2 3 182 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 183 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 184 | Type = 0x05 | Option Length | Reserved | Prefix Length | 185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 187 + + 188 | Group Address | 189 . . 190 . . 191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 193 Figure 1: RPL Target Option for MLAO 195 The next header field indicates the group that the sender is 196 interested in. This field usually contains a 128 bit IPv6 multicast 197 group address. Shorter group identifiers could be used together with 198 a protocol for explicit creation of groups. The MLAO message must 199 have at least one RPL target option to specify the address of the 200 listener that has generated the MLAO. As the MLAO message is 201 forwarded hop-by-hop upwards the routing tree using link-local 202 addresses only, the target option is the only way to communicate the 203 interface address to be used for group subscription. 205 5.2. Routing Header 207 0 1 2 3 208 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 209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 210 | Next Header | Hdr Ext Len | Routing Type | Segments Left | 211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 212 | Sequence Number | Func set | Modulus | 213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 214 | | 215 . . 216 . Filter data . 217 . . 218 | | 219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 221 Figure 2: Routing header 223 Routing Type: {IANA TBD2} 253 225 Segments Left: This value is always 0, so network nodes that do not 226 support this routing header do not generate ICMP6 error messages. 228 Sequence Number: 16 bits sequence number. The number space is 229 unique for a sequence of multicast datagrams for a specific group 230 that arrive at the DAG root on their way up. The DAG root 231 increments the number for each datagram it sends down the 232 respective DODAG. 234 Func set: The set of hash functions used to generate the Filter data 235 value. 237 Note: As the function set contains a combination of several distinct 238 hash functions, it is currently unclear if 8 bits number space is 239 large enough. 241 Modulus: The modulus that is used by the hash functions, minus 64 242 (the minimum filter data size that can be used). The sender 243 chooses the modulus (and thus the filter data size) to achieve its 244 objectives for false positive rates (Section 4). 246 Filter data: A bit field that indicates which nodes should relay 247 this multicast datagram. The length of this field is a multiple 248 of 8 bytes. The actual length is derived from the contents of the 249 field Header Ext Length. 251 Note: The modulus could be derived from the length of the filter data 252 which is known from the extension header size. On the other hand, 253 keeping a separate record of the modulus means that the sender could 254 leave out 8-byte multiples of trailing zero bits if they happen to 255 occur. But then, a modulus that leaves 8-byte sequences of zero bits 256 in the filter is probably too large. 258 6. Implementation 260 In 2013, Constrained-Cast was implemented in Contiki. It turns out 261 that forwarders can compute the hash functions once for their 262 outgoing interfaces and then cache them, simply bit-matching their 263 outgoing interface hash bits against the bloom filter in the packet 264 (a match is indicated when all bits in the outgoing interface hash 265 are set in the bloom filter). 267 The Root computes the tree for each multicast group, computes the 268 bloom filter for it, caches these values, and then simply adds the 269 bloom filter routing header to each downward packet. For adding a 270 new member, the relevant outgoing interfaces are simply added to the 271 bloom filter. For removing a leaving member, however, the bloom 272 filter needs to be recomputed (which can be sped up logarithmically 273 if desired). 275 7. Benefits 277 Constrained-Cast: 279 o operates in Non-Storing Mode, with the simple addition of a 280 membership information service; 282 o performs all routing decisions at the root. 284 Further optimizations might include using a similar kind of bloom 285 filter routing header for unicast forwarding as well (representing, 286 instead of the outgoing interface list, a list of children that 287 forwarding parents need to forward to). 289 8. IANA Considerations 291 The following registrations are done following the procedure 292 specified in [RFC6838]. 294 Note to RFC Editor: Please replace all occurrences of "[RFC-XXXX]" 295 with the RFC number of this specification and "IANA TBD1" with the 296 code selected for TBD1 below and "IANA TBD2" with the value selected 297 for TBD2 below. 299 8.1. ICMPv6 Parameter Registration 301 IANA is requested to add the following entry to the Code fields of 302 the RPL Control Codes registry: 304 +------+------+------------+ 305 | Code | Name | Reference | 306 +------+------+------------+ 307 | TBD1 | MLAO | [RFC-XXXX] | 308 +------+------+------------+ 310 8.2. IPv6 Routing Type Registration 312 IANA is requested to add the following entries to the IPv6 Routing 313 Types registry: 315 +-------+----------------------+------------+ 316 | Value | Name | Reference | 317 +-------+----------------------+------------+ 318 | TBD2 | CCast Routing Header | [RFC-XXXX] | 319 +-------+----------------------+------------+ 321 9. Acknowledgments 323 This work has been supported by Siemens Corporate Technology. 325 10. References 327 10.1. Normative References 329 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 330 Requirement Levels", BCP 14, RFC 2119, 331 DOI 10.17487/RFC2119, March 1997, 332 . 334 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 335 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 336 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 337 Low-Power and Lossy Networks", RFC 6550, 338 DOI 10.17487/RFC6550, March 2012, 339 . 341 10.2. Informative References 343 [BLOOM] Bloom, B., "Space/time trade-offs in hash coding with 344 allowable errors", ISSN 0001-0782, ACM 345 Press Communications of the ACM vol 13 no 7 pp 422-426, 346 1970, . 348 [I-D.ietf-bier-architecture] 349 Wijnands, I., Rosen, E., Dolganow, A., P, T., and S. 350 Aldrin, "Multicast using Bit Index Explicit Replication", 351 draft-ietf-bier-architecture-03 (work in progress), 352 January 2016. 354 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 355 Routing Header for Source Routes with the Routing Protocol 356 for Low-Power and Lossy Networks (RPL)", RFC 6554, 357 DOI 10.17487/RFC6554, March 2012, 358 . 360 [RFC6838] Freed, N., Klensin, J., and T. Hansen, "Media Type 361 Specifications and Registration Procedures", BCP 13, 362 RFC 6838, DOI 10.17487/RFC6838, January 2013, 363 . 365 Authors' Addresses 367 Olaf Bergmann 368 Universitaet Bremen TZI 369 Postfach 330440 370 Bremen D-28359 371 Germany 373 Phone: +49-421-218-63904 374 Email: bergmann@tzi.org 376 Carsten Bormann 377 Universitaet Bremen TZI 378 Postfach 330440 379 Bremen D-28359 380 Germany 382 Phone: +49-421-218-63921 383 Email: cabo@tzi.org 385 Stefanie Gerdes 386 Universitaet Bremen TZI 387 Postfach 330440 388 Bremen D-28359 389 Germany 391 Phone: +49-421-218-63906 392 Email: gerdes@tzi.org 394 Hao Chen 395 Huawei Technologies 396 12, E. Mozhou Rd 397 Nanjing 211111 398 China 400 Phone: +86-25-5662-7052 401 Email: philips.chenhao@huawei.com