idnits 2.17.1 draft-thubert-6lo-bier-dispatch-05.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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 24, 2018) is 2104 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: 'RFCthis' is mentioned on line 327, but not defined == Outdated reference: A later version (-30) exists of draft-ietf-6tisch-architecture-14 == Outdated reference: A later version (-13) exists of draft-ietf-detnet-architecture-06 Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 6lo P. Thubert, Ed. 3 Internet-Draft Cisco 4 Intended status: Standards Track Z. Brodard 5 Expires: January 25, 2019 Ecole Polytechnique 6 H. Jiang 7 G. Texier 8 Telecom Bretagne 9 July 24, 2018 11 A 6loRH for BitStrings 12 draft-thubert-6lo-bier-dispatch-05 14 Abstract 16 This specification extends the 6LoWPAN Routing Header to signal 17 BitStrings such as utilized in Bit Index Explicit Replication and its 18 Traffic Engineering variant. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at https://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on January 25, 2019. 37 Copyright Notice 39 Copyright (c) 2018 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (https://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3 57 4. The BIER-6LoRH encoding . . . . . . . . . . . . . . . . . . . 4 58 4.1. The Bit-by-bit BitStrings . . . . . . . . . . . . . . . . 5 59 4.2. The Enumeration BitStrings . . . . . . . . . . . . . . . 5 60 4.3. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 5 61 4.4. Types of BIER-6LoRH header . . . . . . . . . . . . . . . 6 62 5. Implementation Status . . . . . . . . . . . . . . . . . . . . 8 63 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 64 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 65 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 66 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 67 9.1. Normative References . . . . . . . . . . . . . . . . . . 8 68 9.2. Informative References . . . . . . . . . . . . . . . . . 9 69 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 71 1. Introduction 73 The type of information that needs to be present in a packet inside 74 the LLN but not outside of the LLN varies with the routing operation, 75 but there is overall a need for an extensible compression technique 76 that would simplify the IP-in-IP encapsulation, when needed, and 77 optimally compress existing routing artifacts found in LLNs. 79 The 6LoWPAN Routing Header (6LoRH) [RFC8025] [RFC8138] is such a 80 technique, that extends the 6lo adaptation layer framework [RFC4944], 81 [RFC6282] so as to carry routing information for Route-over use 82 cases. The original specification includes the formats necessary for 83 RPL such as the Source Route Header (SRH) and is intended to be 84 extended for additional routing artifacts. 86 The Bit Index Explicit Replication (BIER), as introduced in the BIER 87 Architecture [I-D.ietf-bier-architecture], can be used as an 88 alternate artifact to route multicast as well as unicast traffic. 89 The Traffic Engineering for Bit Index Explicit Replication 90 [I-D.eckert-bier-te-arch] (BIER-TE) adds support for traffic 91 engineering by explicit hop-by-hop forwarding and loose hop 92 forwarding of packets along a unicast route. 94 This specification provides additional formats for the 6LoRH 95 compression to carry BitStrings such as used for Bit Index Explicit 96 Replication and its Traffic Engineering variant (BIER and BIER-TE, 97 respectively). 99 2. Terminology 101 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 102 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 103 "OPTIONAL" in this document are to be interpreted as described in 104 [RFC2119]. 106 The Terminology used in this document is consistent with and 107 incorporates that described in Terms Used in Routing for Low-Power 108 and Lossy Networks (LLNs). [RFC7102]. 110 Other terms in use in LLNs are found in Terminology for Constrained- 111 Node Networks [RFC7228]. 113 The term "byte" is used in its now customary sense as a synonym for 114 "octet". 116 "RPL", "RPL Packet Information" (RPI) and "RPL Instance" are defined 117 in the RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks 118 [RFC6550] specification. 120 The terms Bit-Forwarding Egress Routers (BFR), BFR-id and BitString 121 are defined in [I-D.ietf-bier-architecture]. A BitString indicates a 122 continuous sequence of bits indexed by an offset in the sequence. 123 The leftmost bit is bit 0 and corresponds to the value 0x80 of the 124 leftmost octet in the BitString. 126 3. Applicability 128 BIER and other bit-indexed methods that would leverage BitStrings 129 will generally require additional information in the packet to 130 complement the BitString. For instance, BIER has the concept of a 131 BFR-id and an Entropy value in the BIER header. Since those 132 additional fields depend on the bit-indexed method, they are expected 133 to be transported separately from the BitString. This specification 134 concentrates on the BitString and a group identifier which enables a 135 network to grow beyond the size of one bitString. 137 Within the context of "the Deterministic Networking (DetNet) 138 Architecture" [I-D.ietf-detnet-architecture] ), the "BIER-TE-based 139 OAM, Replication and Elimination" 140 [I-D.thubert-bier-replication-elimination] document details how BIER- 141 TE can be leveraged to activate the Deterministic Networking 142 Replication and Elimination functions in a manner that is abstract to 143 the data plane forwarding information. An adjacency, which is 144 represented by a bit in the BIER header, can be mapped in the data 145 plane to an Ethernet hop, a Label Switched Path, or it may correspond 146 to a loose or a strict IPv6 Source Routed Path. 148 In the context of LLNs, the 6TiSCH Architecture 149 [I-D.ietf-6tisch-architecture] introduces the concept of a Track that 150 is a directional traffic-engineered path between a source and a 151 destination. A Track is indicated in a packet by a Source or 152 Destination IPv6 Address and a RPL Local Instance. The RPL Instance 153 is carried in an IPv6 packet as part of the RPL Packet Information 154 (RPI), and a bit in the RPI indicates whether the Instance is Local 155 to the Source or the Destination Address. The RPI can be compressed 156 as a RPI 6LoRH header (RPI-6LoRH) as described in [RFC8138]. 158 The 6TiSCH requirements for DetNet [I-D.thubert-6tisch-4detnet] 159 indicate that a 6TiSCH Track may leverage replication and elimination 160 as defined in DetNet. This specification enables this behavior as 161 follows: if a BIER-6LoRH is positioned right after a RPI-6LoRH, then 162 the BitString in the BIER-6LoRH applies to the context of the Track 163 indicated by the source or destination address of the packet and the 164 local Instance ID associated to the source or destination of the 165 packet. 167 4. The BIER-6LoRH encoding 169 The BIER 6LoRH (BIER-6LoRH) is a Critical 6LoWPAN Routing Header that 170 provides a variable-size container for a BitString such as, a but not 171 limited to, a BIER BitString. 173 The capability to parse the BIER BitString is necessary to forward 174 the packet so the Type cannot be ignored. 176 0 1 177 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+ 179 |1|0|0| Control |6LoRHType 15-29| BitString | 180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+ 182 Figure 1: The BIER-6LoRH 184 This specification provides a 5-bit Control field that can be used to 185 encode information that is specific to the BitString. The type and 186 size of the BitString are encoded in the 6LoRHType. 188 4.1. The Bit-by-bit BitStrings 190 In the bit-by-bit case, each bit is mapped in an unequivocal fashion 191 with a single addressable resource in the network. This may rapidly 192 lead to large BitStrings, and BIER allows to divide a network into 193 groups that partition the network so that a given BitString is 194 locally significant to one group only. This specification uses the 195 5-bits Control field to encode the group. 197 When groups are used, it may be that a packet is sent to different 198 groups at the same time. In that case, multiple BIER-6LoRH headers 199 can be prepended to a same packet, each one for a different group. 200 As the packet flows along the multicast distribution tree, a BIER- 201 6LoRH header that has no more destination in a given branch may be 202 removed to make the packet shorter. 204 The encoding value indicates the size of the BitString. The size of 205 the BitString used in a given packet is smallest that can represent 206 all of the bits that are set for this particular packet, so for a 207 same network various sizes may be used for different packets 208 depending on the destinations. 210 4.2. The Enumeration BitStrings 212 For unicast and when very few destinations are targeted for a given 213 message, it may be that it is more economical to list the bit offsets 214 one by one than it is to represent the full BitString that can hold 215 all of the bit offsets. 217 In the Enumeration case, a BitString actually encodes the offset of 218 one bit as an unsigned integer, using the number of bits indicated in 219 the control field, and BitStrings are concatenated without 220 intermediate padding. The overall concatenation must be aligned to a 221 byte boundary. To achieve this, trailing bits are added to the right 222 of the concatenation as padding to the next byte boundary. 224 To optimize the compression, the lower numbers can be expressed with 225 less bits, and multiple Enumeration BIER-6LoRH headers may be used to 226 encode offsets that require different numbers of bits for their 227 representation. 229 4.3. Bloom Filters 231 A Bloom Filter can be seen as an additional compression technique for 232 the bitString representation. A Bloom Filter may generate false 233 positives, which, in the case of BIER, result in undue forwarding of 234 a packet down a path where no listener exists. 236 As an example, the Constrained-Cast [I-D.ietf-roll-ccast] 237 specification employs Bloom Filters as a compact representation of a 238 match or non-match for elements in a set that may be larger than the 239 number of bits in the BitString. 241 In the case of a Bloom Filter, a number of Hash functions must be run 242 to obtain a multi-bit signature of an encoded element. This 243 specification uses the 5-bits Control field to signal an Identifier 244 of the set of Hash functions being used to generate a certain 245 BitString, so as to enable the migration from a set of Hash functions 246 to the next. 248 4.4. Types of BIER-6LoRH header 250 The Type of a BIER-6LoRH header indicates the size of the BitString 251 and whether the BitString is operated as an uncompressed bit-by-bit 252 mapping, as an enumeration, or as a Bloom filter. 254 +--------------+--------------+----------------------+--------------+ 255 | BitString | Encoding | Control field | BitString | 256 | Type | | | Size | 257 +--------------+--------------+----------------------+--------------+ 258 | 15 | bit-by-bit | Group ID | 8 bits | 259 +--------------+--------------+----------------------+--------------+ 260 | 16 | bit-by-bit | Group ID | 16 bits | 261 +--------------+--------------+----------------------+--------------+ 262 | 17 | bit-by-bit | Group ID | 32 bits | 263 +--------------+--------------+----------------------+--------------+ 264 | 18 | bit-by-bit | Group ID | 56 bits | 265 +--------------+--------------+----------------------+--------------+ 266 | 19 | bit-by-bit | Group ID | 96 bits | 267 +--------------+--------------+----------------------+--------------+ 268 | 20 | bit-by-bit | Group ID | 160 bits | 269 +--------------+--------------+----------------------+--------------+ 270 | 21 | bit-by-bit | Group ID | 256 bits | 271 +--------------+--------------+----------------------+--------------+ 272 | 22 | Enumeration | Number of elements | 4 bits | 273 +--------------+--------------+----------------------+--------------+ 274 | 23 | Enumeration | Number of elements | 6 bits | 275 +--------------+--------------+----------------------+--------------+ 276 | 24 | Enumeration | Number of elements | 8 bits | 277 +--------------+--------------+----------------------+--------------+ 278 | 25 | Bloom filter | Hash function Set ID | 8 bits | 279 +--------------+--------------+----------------------+--------------+ 280 | 26 | Bloom filter | Hash function Set ID | 16 bits | 281 +--------------+--------------+----------------------+--------------+ 282 | 27 | Bloom filter | Hash function Set ID | 48 bits | 283 +--------------+--------------+----------------------+--------------+ 284 | 28 | Bloom filter | Hash function Set ID | 96 bits | 285 +--------------+--------------+----------------------+--------------+ 286 | 29 | Bloom filter | Hash function Set ID | 160 bits | 287 +--------------+--------------+----------------------+--------------+ 289 Table 1: The BIER-6LoRH Types 291 In order to address a potentially large number of devices, the 292 BitString may grow very large. Yet, the maximum frame size for a 293 given MAC layer may limit the number of bits that can be dedicated to 294 routing. With this specification, a number of BIER-6LoRH headers of 295 a same type (bit-by-bit or Bloom filter) may be placed contiguously 296 in the packet. This results in a larger BitString that is the 297 concatenation of the BitStrings in the individual headers in the 298 order they are appearing in the packet. 300 5. Implementation Status 302 A research-stage implementation was developed at Cisco's Paris 303 Innovation Lab (PIRL) by Zacharie Brodard. It was implemented on 304 OpenWSN open-source firmware and tested on the OpenMote-CC2538 305 hardware. It implements the header types 15, 16, 17, 18 and 19 (bit- 306 by-bit encoding without group ID) in order to allow a BIER-TE 307 protocol over IEE802.15.4e. 309 Links: 311 github: https://github.com/zach-b/openwsn-fw/tree/BIER 313 OpenWSN firmware: https://openwsn.atlassian.net/wiki/pages/ 314 viewpage.action?pageId=688187 316 OpenMote hardware: http://www.openmote.com/ 318 6. Security Considerations 320 The security considerations of [RFC8138] apply. 322 7. IANA Considerations 324 This document extends the IANA registry created by [RFC8138] for the 325 6LoWPAN Routing Header Type, and adds the following values: 327 15..29 : BIER-6LoRH [RFCthis] 329 8. Acknowledgments 331 9. References 333 9.1. Normative References 335 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 336 Requirement Levels", BCP 14, RFC 2119, 337 DOI 10.17487/RFC2119, March 1997, 338 . 340 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 341 "Transmission of IPv6 Packets over IEEE 802.15.4 342 Networks", RFC 4944, DOI 10.17487/RFC4944, September 2007, 343 . 345 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 346 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 347 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 348 Low-Power and Lossy Networks", RFC 6550, 349 DOI 10.17487/RFC6550, March 2012, 350 . 352 [RFC8025] Thubert, P., Ed. and R. Cragie, "IPv6 over Low-Power 353 Wireless Personal Area Network (6LoWPAN) Paging Dispatch", 354 RFC 8025, DOI 10.17487/RFC8025, November 2016, 355 . 357 [RFC8138] Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie, 358 "IPv6 over Low-Power Wireless Personal Area Network 359 (6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138, 360 April 2017, . 362 9.2. Informative References 364 [I-D.eckert-bier-te-arch] 365 Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic 366 Engineering for Bit Index Explicit Replication BIER-TE", 367 draft-eckert-bier-te-arch-06 (work in progress), November 368 2017. 370 [I-D.ietf-6tisch-architecture] 371 Thubert, P., "An Architecture for IPv6 over the TSCH mode 372 of IEEE 802.15.4", draft-ietf-6tisch-architecture-14 (work 373 in progress), April 2018. 375 [I-D.ietf-bier-architecture] 376 Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and 377 S. Aldrin, "Multicast using Bit Index Explicit 378 Replication", draft-ietf-bier-architecture-08 (work in 379 progress), September 2017. 381 [I-D.ietf-detnet-architecture] 382 Finn, N., Thubert, P., Varga, B., and J. Farkas, 383 "Deterministic Networking Architecture", draft-ietf- 384 detnet-architecture-06 (work in progress), June 2018. 386 [I-D.ietf-roll-ccast] 387 Bergmann, O., Bormann, C., Gerdes, S., and H. Chen, 388 "Constrained-Cast: Source-Routed Multicast for RPL", 389 draft-ietf-roll-ccast-01 (work in progress), October 2017. 391 [I-D.thubert-6tisch-4detnet] 392 Thubert, P., "6TiSCH requirements for DetNet", draft- 393 thubert-6tisch-4detnet-01 (work in progress), June 2015. 395 [I-D.thubert-bier-replication-elimination] 396 Thubert, P., Eckert, T., Brodard, Z., and H. Jiang, "BIER- 397 TE extensions for Packet Replication and Elimination 398 Function (PREF) and OAM", draft-thubert-bier-replication- 399 elimination-03 (work in progress), March 2018. 401 [RFC6282] Hui, J., Ed. and P. Thubert, "Compression Format for IPv6 402 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 403 DOI 10.17487/RFC6282, September 2011, 404 . 406 [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and 407 Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January 408 2014, . 410 [RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for 411 Constrained-Node Networks", RFC 7228, 412 DOI 10.17487/RFC7228, May 2014, 413 . 415 Authors' Addresses 417 Pascal Thubert (editor) 418 Cisco Systems 419 Village d'Entreprises Green Side 420 400, Avenue de Roumanille 421 Batiment T3 422 Biot - Sophia Antipolis 06410 423 FRANCE 425 Phone: +33 4 97 23 26 34 426 Email: pthubert@cisco.com 428 Zacharie Brodard 429 Ecole Polytechnique 430 Route de Saclay 431 Palaiseau 91128 432 FRANCE 434 Phone: +33 6 73 73 35 09 435 Email: zacharie.brodard@polytechnique.edu 436 Hao Jiang 437 Telecom Bretagne 438 2, rue de la Chataigneraie 439 Cesson-Sevigne 35510 440 FRANCE 442 Phone: +33 7 53 70 97 34 443 Email: hao.jiang@telecom-bretagne.eu 445 Geraldine Texier 446 Telecom Bretagne 447 2, rue de la Chataigneraie 448 Cesson-Sevigne 35510 449 FRANCE 451 Phone: +33 2 99 12 70 38 452 Email: geraldine.texier@telecom-bretagne.eu