idnits 2.17.1 draft-bormann-6lowpan-ghc-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 date (September 06, 2012) is 4250 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 368, but not defined ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) == Outdated reference: A later version (-04) exists of draft-bormann-6lowpan-roadmap-01 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 6LoWPAN Working Group C. Bormann 3 Internet-Draft Universitaet Bremen TZI 4 Intended status: Standards Track September 06, 2012 5 Expires: March 10, 2013 7 6LoWPAN Generic Compression of Headers and Header-like Payloads 8 draft-bormann-6lowpan-ghc-05 10 Abstract 12 This short I-D provides a simple addition to 6LoWPAN Header 13 Compression that enables the compression of generic headers and 14 header-like payloads, without a need to define a new header 15 compression scheme for each new such header or header-like payload. 17 Status of this Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on March 10, 2013. 34 Copyright Notice 36 Copyright (c) 2012 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.1. The Header Compression Coupling Problem . . . . . . . . . 3 53 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. 6LoWPAN-GHC . . . . . . . . . . . . . . . . . . . . . . . . . 5 56 3. Integrating 6LoWPAN-GHC into 6LoWPAN-HC . . . . . . . . . . . 6 57 3.1. Compressing payloads (UDP and ICMPv6) . . . . . . . . . . 6 58 3.2. Compressing extension headers . . . . . . . . . . . . . . 6 59 3.3. Indicating GHC capability . . . . . . . . . . . . . . . . 7 60 3.4. Using the 6CIO Option . . . . . . . . . . . . . . . . . . 8 61 4. IANA considerations . . . . . . . . . . . . . . . . . . . . . 10 62 5. Security considerations . . . . . . . . . . . . . . . . . . . 11 63 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 64 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 65 7.1. Normative References . . . . . . . . . . . . . . . . . . . 13 66 7.2. Informative References . . . . . . . . . . . . . . . . . . 13 67 Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 15 68 Appendix B. Things we probably won't do . . . . . . . . . . . . . 22 69 B.1. Context References . . . . . . . . . . . . . . . . . . . . 22 70 B.2. Nibblecode . . . . . . . . . . . . . . . . . . . . . . . . 22 71 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 25 73 1. Introduction 75 1.1. The Header Compression Coupling Problem 77 6LoWPAN-HC [RFC6282] defines a scheme for header compression in 78 6LoWPAN [RFC4944] packets. As with most header compression schemes, 79 a new specification is needed for every new kind of header that needs 80 to be compressed. In addition, [RFC6282] does not define an 81 extensibility scheme like the ROHC profiles defined in ROHC [RFC3095] 82 [RFC5795]. This leads to the difficult situation that 6LoWPAN-HC 83 tended to be reopened and reexamined each time a new header receives 84 consideration (or an old header is changed and reconsidered) in the 85 6LoWPAN/roll/CoRE cluster of IETF working groups. While [RFC6282] 86 finally got completed, the underlying problem remains unsolved. 88 The purpose of the present contribution is to plug into [RFC6282] as 89 is, using its NHC (next header compression) concept. We add a 90 slightly less efficient, but vastly more general form of compression 91 for headers of any kind and even for header-like payloads such as 92 those exhibited by routing protocols, DHCP, etc. The objective is an 93 extremely simple specification that can be defined on a single page 94 and implemented in a small number of lines of code, as opposed to a 95 general data compression scheme such as that defined in [RFC1951]. 97 1.2. Terminology 99 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 100 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 101 document are to be interpreted as described in RFC 2119 [RFC2119]. 103 The term "byte" is used in its now customary sense as a synonym for 104 "octet". 106 1.3. Notation 108 This specification uses a trivial notation for code bytes and the 109 bitfields in them the meaning of which should be mostly obvious. 110 More formally speaking, the meaning of the notation is: 112 Potential values for the code bytes themselves are expressed by 113 templates that represent 8-bit most-significant-bit-first binary 114 numbers (without any special prefix), where 0 stands for 0, 1 for 1, 115 and variable segments in these code byte templates are indicated by 116 sequences of the same letter such as kkkkkkk or ssss, the length of 117 which indicates the length of the variable segment in bits. 119 In the notation of values derived from the code bytes, 0b is used as 120 a prefix for expressing binary numbers in most-significant-bit first 121 notation (akin to the use of 0x for most-significant-digit-first 122 hexadecimal numbers in the C programming language). Where the 123 abovementioned sequences of letters are then referenced in such a 124 binary number in the text, the intention is that the value from these 125 bitfields in the actual code byte be inserted. 127 Example: The code byte template 129 101nssss 131 stands for a byte that starts (most-significant-bit-first) with the 132 bits 1, 0, and 1, and continues with five variable bits, the first of 133 which is referenced as "n" and the next four are referenced as 134 "ssss". Based on this code byte template, a reference to 136 0b0ssss000 138 means a binary number composed from a zero bit, the four bits that 139 are in the "ssss" field (for 101nssss, the four least significant 140 bits) in the actual byte encountered, kept in the same order, and 141 three more zero bits. 143 2. 6LoWPAN-GHC 145 The format of a GHC-compressed header or payload is a simple 146 bytecode. A compressed header consists of a sequence of pieces, each 147 of which begins with a code byte, which may be followed by zero or 148 more bytes as its argument. Some code bytes cause bytes to be laid 149 out in the destination buffer, some simply modify some decompression 150 variables. 152 At the start of decompressing a header or payload within a L2 packet 153 (= fragment), variables "sa" and "na" are initialized as zero. 155 The code bytes are defined as follows: 157 +----------+---------------------------------------------+----------+ 158 | code | Action | Argument | 159 | byte | | | 160 +----------+---------------------------------------------+----------+ 161 | 0kkkkkkk | Append k = 0b0kkkkkkk bytes of data in the | k bytes | 162 | | bytecode argument (k < 96) | of data | 163 | | | | 164 | 1000nnnn | Append 0b0000nnnn+2 bytes of zeroes | | 165 | | | | 166 | 10010000 | STOP code (end of compressed data, see | | 167 | | Section 3.2) | | 168 | | | | 169 | 101nssss | Set up extended arguments for a | | 170 | | backreference: sa += 0b0ssss000, na += | | 171 | | 0b0000n000 | | 172 | | | | 173 | 11nnnkkk | Backreference: n = na+0b00000nnn+2; s = | | 174 | | 0b00000kkk+sa+n; append n bytes from | | 175 | | previously output bytes, starting s bytes | | 176 | | to the left of the current output pointer; | | 177 | | set sa = 0, na = 0 | | 178 +----------+---------------------------------------------+----------+ 180 Note that the following bit combinations are reserved at this time: 181 011xxxxx (possibly for Appendix B.1), and 1001nnnn (where 0b0000nnnn 182 > 0, possibly for Appendix B.2). 184 For the purposes of the backreferences, the expansion buffer is 185 initialized with the pseudo-header as defined in [RFC2460], at the 186 end of which the target buffer begins. These pseudo-header bytes are 187 therefore available for backreferencing, but not copied into the 188 final result. 190 3. Integrating 6LoWPAN-GHC into 6LoWPAN-HC 192 6LoWPAN-GHC is intended to plug in as an NHC format for 6LoWPAN-HC 193 [RFC6282]. This section shows how this can be done (without 194 supplying the detailed normative text yet, although it could be 195 implemented from this page). 197 3.1. Compressing payloads (UDP and ICMPv6) 199 GHC is by definition generic and can be applied to different kinds of 200 packets. All the examples given in Appendix A are for ICMPv6 201 packets; a single NHC value suffices to define an NHC format for 202 ICMPv6 based on GHC (see below). 204 In addition it may be useful to include an NHC format for UDP, as 205 many headerlike payloads (e.g., DHCPv6) are carried in UDP. 206 [RFC6282] already defines an NHC format for UDP (11110CPP). What 207 remains to be done is to define an analogous NHC byte formatted, e.g. 208 as shown in Figure 1, and simply reference the existing 209 specification, indicating that for 0b11010cpp NHC bytes, the UDP 210 payload is not supplied literally but compressed by 6LoWPAN-GHC. 212 0 1 2 3 4 5 6 7 213 +---+---+---+---+---+---+---+---+ 214 | 1 | 1 | 0 | 1 | 0 | C | P | 215 +---+---+---+---+---+---+---+---+ 217 Figure 1: Proposed NHC byte for UDP GHC (actual value to be allocated 218 by IANA) 220 To stay in the same general numbering space, we propose 0b11011111 as 221 the NHC byte for ICMPv6 GHC (Figure 2). 223 0 1 2 3 4 5 6 7 224 +---+---+---+---+---+---+---+---+ 225 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 226 +---+---+---+---+---+---+---+---+ 228 Figure 2: Proposed NHC byte for ICMPv6 GHC (actual value to be 229 allocated by IANA) 231 3.2. Compressing extension headers 233 If the compression of specific extension headers is considered 234 desirable, this can be added in a similar way, e.g. as in Figure 3 235 (however, probably only EID 0 to 3 need to be assigned). As there is 236 no easy way to extract the length field from the GHC-encoded header 237 before decoding, this would make detecting the end of the extension 238 header somewhat complex. The easiest (and most efficient) approach 239 is to completely elide the length field (in the same way NHC already 240 elides the next header field in certain cases) and reconstruct it 241 only on decompression. To serve as a terminator for the extension 242 header, the reserved bytecode 0b10010000 has been assigned as a stop 243 marker -- this is only needed for extension headers, not for final 244 payloads. 246 0 1 2 3 4 5 6 7 247 +---+---+---+---+---+---+---+---+ 248 | 1 | 0 | 1 | 1 | EID |NH | 249 +---+---+---+---+---+---+---+---+ 251 Figure 3: Proposed NHC byte for extension header GHC 253 3.3. Indicating GHC capability 255 The 6LoWPAN baseline includes just [RFC4944], [RFC6282], 256 [I-D.ietf-6lowpan-nd] (see [I-D.bormann-6lowpan-roadmap]). To enable 257 the use of GHC, 6LoWPAN nodes need to know that their neighbors 258 implement it. While this can also simply be administratively 259 required, a transition strategy as well as a way to support mixed 260 networks is required. 262 One way to know a neighbor does implement GHC is receiving a packet 263 from that neighbor with GHC in it ("implicit capability detection"). 264 However, there needs to be a way to bootstrap this, as nobody ever 265 would start sending packets with GHC otherwise. 267 To minimize the impact on [I-D.ietf-6lowpan-nd], we propose adding an 268 ND option 6LoWPAN Capability Indication (6CIO), as illustrated in 269 Figure 4. 271 0 1 2 3 272 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 273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 274 | Type | Length = 1 |_____________________________|G| 275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 276 |_______________________________________________________________| 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 Figure 4: 6LoWPAN Capability Indication Option (6CIO) 281 The G bit indicates whether the node sending the option is GHC 282 capable. 284 Once a node receives either an explicit or an implicit indication of 285 GHC capability from another node, it may send GHC-compressed packets 286 to that node. Where that capability has not been recently confirmed, 287 similar to the way PLPMTUD [RFC4821] finds out about changes in the 288 network, a node SHOULD make use of NUD (neighbor unreachability 289 detection) failures to switch back to basic 6LoWPAN header 290 compression [RFC6282]. (Where context information is used in a 291 potential future version of this specification, as in Appendix B.1, 292 robustness may also be increased by making use of checksum error 293 indications that might point out errors in decompression.) 295 3.4. Using the 6CIO Option 297 The 6CIO option will typically only be ever sent in 6LoWPAN-ND RS 298 packets (it then cannot itself be GHC compressed unless the host 299 desires to limit itself to talking to GHC capable routers); the 300 resulting 6LoWPAN-ND RA can already make use of GHC and thus indicate 301 GHC capability implicitly, which in turn allows the nodes to use GHC 302 in the 6LoWPAN-ND NS/NA exchange. 304 6CIO can also be used for future options that need to be negotiated 305 between 6LoWPAN peers; an IANA registry will administrate the flags. 306 (Bits marked by underscores in Figure 4 are reserved for future 307 allocation, i.e., they MUST be sent as zero and MUST be ignored on 308 reception until allocated. Length values larger than 1 MUST be 309 accepted by implementations in order to enable future extensions; the 310 additional bits in the option are then reserved in the same way. For 311 the purposes of the IANA registry, the bits are numbered in msb-first 312 order from the 16th bit of the option onward, i.e., the G bit is flag 313 number 15.) (Additional bits may also be used by a follow-on version 314 of this document if some bit combinations that have been left 315 reserved here are then used in an upward compatible manner.) 317 Where the use of this option by other specifications is envisioned, 318 the following items have to be kept in mind: 320 o The option can be used in any ND packet. 322 o Specific bits are set in the option to indicate that a capability 323 is present in the sender. (There may be other ways to infer this 324 information, as is the case in this specification.) Bit 325 combinations may be used as desired. The absence of the 326 capability _indication_ is signaled by setting these bits to zero; 327 this does not necessarily mean that the capability is absent. 329 o The intention is not to modify the semantics of the specific ND 330 packet carrying the option, but to provide the general capability 331 indication described above. 333 o Specifications have to be designed such that receivers that do not 334 receive or do not process such a capability indication can still 335 interoperate (presumably without exploiting the indicated 336 capability). 338 o The option is meant to be used sparsely, i.e. once a sender has 339 reason to believe the capability indication has been received, 340 there no longer is a need to continue sending it. 342 4. IANA considerations 344 [This section to be removed/replaced by the RFC Editor.] 346 In the IANA registry for the "LOWPAN_NHC Header Type" (in the "IPv6 347 Low Power Personal Area Network Parameters"), IANA needs to add the 348 assignments in Figure 5. 350 10110IIN: Extension header GHC [RFCthis] 351 11010CPP: UDP GHC [RFCthis] 352 11011111: ICMPv6 GHC [RFCthis] 354 Figure 5: IANA assignments for the NHC byte 356 IANA needs to allocate an ND option number for the 6CIO ND option 357 format in the Registry "IPv6 Neighbor Discovery Option Formats" 358 [RFC4861]. 360 IANA needs to create a registry for "6LoWPAN capability bits" within 361 the "Internet Control Message Protocol version 6 (ICMPv6) 362 Parameters". The bits are allocated by giving their numbers as small 363 non-negative integers as defined in section Section 3.4, preferably 364 in the range 0..47. The policy is "RFC Required" [RFC5226]. The 365 initial content of the registry is as in Figure 6: 367 0..14: unassigned 368 15: GHC capable bit (G bit) [RFCthis] 369 16..47: unassigned 371 Figure 6 373 5. Security considerations 375 The security considerations of [RFC4944] and [RFC6282] apply. As 376 usual in protocols with packet parsing/construction, care must be 377 taken in implementations to avoid buffer overflows and in particular 378 (with respect to the back-referencing) out-of-area references during 379 decompression. 381 One additional consideration is that an attacker may send a forged 382 packet that makes a second node believe a third victim node is GHC- 383 capable. If it is not, this may prevent packets sent by the second 384 node from reaching the third node (at least until robustness features 385 such as those discussed in Section 3.3 kick in). 387 No mitigation is proposed (or known) for this attack, except that a 388 node that does implement GHC is not vulnerable. However, with 389 unsecured ND, a number of attacks with similar outcomes are already 390 possible, so there is little incentive to make use of this additional 391 attack. With secured ND, 6CIO is also secured; nodes relying on 392 secured ND therefore should use 6CIO bidirectionally (and limit the 393 implicit capability detection to secured ND packets carrying GHC) 394 instead of basing their neighbor capability assumptions on receiving 395 any kind of unprotected packet. 397 6. Acknowledgements 399 Colin O'Flynn has repeatedly insisted that some form of compression 400 for ICMPv6 and ND packets might be beneficial. He actually wrote his 401 own draft, [I-D.oflynn-6lowpan-icmphc], which compresses better, but 402 addresses basic ICMPv6/ND only and needs a much longer spec (around 403 17 pages of detailed spec, as compared to the single page of core 404 spec here). This motivated the author to try something simple, yet 405 general. Special thanks go to Colin for indicating that he indeed 406 considers his draft superseded by the present one. 408 The examples given are based on pcap files that Colin O'Flynn and 409 Owen Kirby provided. 411 Erik Nordmark provided input that helped shaping the 6CIO option. 413 Yoshihiro Ohba insisted on clarifying the notation used for the 414 definition of the bytecodes and their bitfields. 416 7. References 418 7.1. Normative References 420 [I-D.ietf-6lowpan-nd] 421 Shelby, Z., Chakrabarti, S., and E. Nordmark, "Neighbor 422 Discovery Optimization for Low Power and Lossy Networks 423 (6LoWPAN)", draft-ietf-6lowpan-nd-21 (work in progress), 424 August 2012. 426 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 427 Requirement Levels", BCP 14, RFC 2119, March 1997. 429 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 430 (IPv6) Specification", RFC 2460, December 1998. 432 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 433 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 434 September 2007. 436 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 437 "Transmission of IPv6 Packets over IEEE 802.15.4 438 Networks", RFC 4944, September 2007. 440 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 441 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 442 May 2008. 444 [RFC6282] Hui, J. and P. Thubert, "Compression Format for IPv6 445 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 446 September 2011. 448 7.2. Informative References 450 [I-D.bormann-6lowpan-roadmap] 451 Bormann, C., "6LoWPAN Roadmap and Implementation Guide", 452 draft-bormann-6lowpan-roadmap-01 (work in progress), 453 March 2012. 455 [I-D.oflynn-6lowpan-icmphc] 456 O'Flynn, C., "ICMPv6/ND Compression for 6LoWPAN Networks", 457 draft-oflynn-6lowpan-icmphc-00 (work in progress), 458 July 2010. 460 [RFC1951] Deutsch, P., "DEFLATE Compressed Data Format Specification 461 version 1.3", RFC 1951, May 1996. 463 [RFC3095] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H., 464 Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, 465 K., Liu, Z., Martensson, A., Miyazaki, A., Svanbro, K., 466 Wiebke, T., Yoshimura, T., and H. Zheng, "RObust Header 467 Compression (ROHC): Framework and four profiles: RTP, UDP, 468 ESP, and uncompressed", RFC 3095, July 2001. 470 [RFC4821] Mathis, M. and J. Heffner, "Packetization Layer Path MTU 471 Discovery", RFC 4821, March 2007. 473 [RFC5795] Sandlund, K., Pelletier, G., and L-E. Jonsson, "The RObust 474 Header Compression (ROHC) Framework", RFC 5795, 475 March 2010. 477 [RFC6690] Shelby, Z., "Constrained RESTful Environments (CoRE) Link 478 Format", RFC 6690, August 2012. 480 Appendix A. Examples 482 This section demonstrates some relatively realistic examples derived 483 from actual PCAP dumps taken at previous interops. Unfortunately, 484 for these dumps, no context information was available, so the 485 relatively powerful effect of context-based compression is not shown. 486 (TBD: Add a couple DHCP examples.) 488 Figure 7 shows an RPL DODAG Information Solicitation, a quite short 489 RPL message that obviously cannot be improved much. 491 IP header: 492 60 00 00 00 00 08 3a ff fe 80 00 00 00 00 00 00 493 02 1c da ff fe 00 20 24 ff 02 00 00 00 00 00 00 494 00 00 00 00 00 00 00 1a 495 Payload: 496 9b 00 6b de 00 00 00 00 497 Pseudoheader: 498 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 20 24 499 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 1a 500 00 00 00 08 00 00 00 3a 501 copy: 04 9b 00 6b de 502 4 nulls: 82 503 Compressed: 504 04 9b 00 6b de 82 505 Was 8 bytes; compressed to 6 bytes, compression factor 1.33 507 Figure 7: A simple RPL example 509 Figure 8 shows an RPL DODAG Information Object, a longer RPL control 510 message that is improved a bit more (but would likely benefit 511 additionally from a context reference). Note that the compressed 512 output exposes an inefficiency in the simple-minded compressor used 513 to generate it; this does not devalue the example since constrained 514 nodes are quite likely to make use of simple-minded compressors. 516 IP header: 517 60 00 00 00 00 5c 3a ff fe 80 00 00 00 00 00 00 518 02 1c da ff fe 00 30 23 ff 02 00 00 00 00 00 00 519 00 00 00 00 00 00 00 1a 520 Payload: 521 9b 01 7a 5f 00 f0 01 00 88 00 00 00 20 02 0d b8 522 00 00 00 00 00 00 00 ff fe 00 fa ce 04 0e 00 14 523 09 ff 00 00 01 00 00 00 00 00 00 00 08 1e 80 20 524 ff ff ff ff ff ff ff ff 00 00 00 00 20 02 0d b8 525 00 00 00 00 00 00 00 ff fe 00 fa ce 03 0e 40 00 526 ff ff ff ff 20 02 0d b8 00 00 00 00 527 Pseudoheader: 528 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 529 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 1a 530 00 00 00 5c 00 00 00 3a 531 copy: 09 9b 01 7a 5f 00 f0 01 00 88 532 3 nulls: 81 533 copy: 04 20 02 0d b8 534 7 nulls: 85 535 ref(52): ff fe 00 -> ref 101nssss 0 6/11nnnkkk 1 1: a6 c9 536 copy: 08 fa ce 04 0e 00 14 09 ff 537 2 nulls: 80 538 copy: 01 01 539 7 nulls: 85 540 copy: 06 08 1e 80 20 ff ff 541 ref(2): ff ff -> ref 11nnnkkk 0 0: c0 542 ref(4): ff ff ff ff -> ref 11nnnkkk 2 0: d0 543 4 nulls: 82 544 ref(48): 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 fa ce 545 -> ref 101nssss 1 4/11nnnkkk 6 0: b4 f0 546 copy: 03 03 0e 40 547 ref(9): 00 ff -> ref 11nnnkkk 0 7: c7 548 ref(28): ff ff ff -> ref 101nssss 0 3/11nnnkkk 1 1: a3 c9 549 ref(24): 20 02 0d b8 00 00 00 00 550 -> ref 101nssss 0 2/11nnnkkk 6 0: a2 f0 551 Compressed: 552 09 9b 01 7a 5f 00 f0 01 00 88 81 04 20 02 0d b8 553 85 a6 c9 08 fa ce 04 0e 00 14 09 ff 80 01 01 85 554 06 08 1e 80 20 ff ff c0 d0 82 b4 f0 03 03 0e 40 555 c7 a3 c9 a2 f0 556 Was 92 bytes; compressed to 53 bytes, compression factor 1.74 558 Figure 8: A longer RPL example 560 Similarly, Figure 9 shows an RPL DAO message. One of the embedded 561 addresses is copied right out of the pseudoheader, the other one is 562 effectively converted from global to local by providing the prefix 563 FE80 literally, inserting a number of nulls, and copying (some of) 564 the IID part again out of the pseudoheader. Note that a simple 565 implementation would probably emit fewer nulls and copy the entire 566 IID; there are multiple ways to encode this 50-byte payload into 27 567 bytes. 569 IP header: 570 60 00 00 00 00 32 3a ff 20 02 0d b8 00 00 00 00 571 00 00 00 ff fe 00 33 44 20 02 0d b8 00 00 00 00 572 00 00 00 ff fe 00 11 22 573 Payload: 574 9b 02 58 7d 01 80 00 f1 05 12 00 80 20 02 0d b8 575 00 00 00 00 00 00 00 ff fe 00 33 44 06 14 00 80 576 f1 00 fe 80 00 00 00 00 00 00 00 00 00 ff fe 00 577 11 22 578 Pseudoheader: 579 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 33 44 580 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 11 22 581 00 00 00 32 00 00 00 3a 582 copy: 0c 9b 02 58 7d 01 80 00 f1 05 12 00 80 583 ref(52): 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 33 44 584 -> ref 101nssss 1 4/11nnnkkk 6 4: b4 f4 585 copy: 08 06 14 00 80 f1 00 fe 80 586 9 nulls: 87 587 ref(58): ff fe 00 11 22 -> ref 101nssss 0 6/11nnnkkk 3 5: a6 dd 588 Compressed: 589 0c 9b 02 58 7d 01 80 00 f1 05 12 00 80 b4 f4 08 590 06 14 00 80 f1 00 fe 80 87 a6 dd 591 Was 50 bytes; compressed to 27 bytes, compression factor 1.85 593 Figure 9: An RPL DAO message 595 Figure 10 shows the effect of compressing a simple ND neighbor 596 solicitation (again, no context-based compression). 598 IP header: 599 60 00 00 00 00 30 3a ff 20 02 0d b8 00 00 00 00 600 00 00 00 ff fe 00 3b d3 fe 80 00 00 00 00 00 00 601 02 1c da ff fe 00 30 23 602 Payload: 603 87 00 a7 68 00 00 00 00 fe 80 00 00 00 00 00 00 604 02 1c da ff fe 00 30 23 01 01 3b d3 00 00 00 00 605 1f 02 00 00 00 00 00 06 00 1c da ff fe 00 20 24 606 Pseudoheader: 607 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 3b d3 608 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 609 00 00 00 30 00 00 00 3a 610 copy: 04 87 00 a7 68 611 4 nulls: 82 612 ref(32): fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 613 -> ref 101nssss 1 2/11nnnkkk 6 0: b2 f0 614 copy: 04 01 01 3b d3 615 4 nulls: 82 616 copy: 02 1f 02 617 5 nulls: 83 618 copy: 02 06 00 619 ref(24): 1c da ff fe 00 -> ref 101nssss 0 2/11nnnkkk 3 3: a2 db 620 copy: 02 20 24 621 Compressed: 622 04 87 00 a7 68 82 b2 f0 04 01 01 3b d3 82 02 1f 623 02 83 02 06 00 a2 db 02 20 24 624 Was 48 bytes; compressed to 26 bytes, compression factor 1.85 626 Figure 10: An ND neighbor solicitation 628 Figure 11 shows the compression of an ND neighbor advertisement. 630 IP header: 631 60 00 00 00 00 30 3a fe fe 80 00 00 00 00 00 00 632 02 1c da ff fe 00 30 23 20 02 0d b8 00 00 00 00 633 00 00 00 ff fe 00 3b d3 634 Payload: 635 88 00 26 6c c0 00 00 00 fe 80 00 00 00 00 00 00 636 02 1c da ff fe 00 30 23 02 01 fa ce 00 00 00 00 637 1f 02 00 00 00 00 00 06 00 1c da ff fe 00 20 24 638 Pseudoheader: 639 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 640 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 3b d3 641 00 00 00 30 00 00 00 3a 642 copy: 05 88 00 26 6c c0 643 3 nulls: 81 644 ref(48): fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 645 -> ref 101nssss 1 4/11nnnkkk 6 0: b4 f0 646 copy: 04 02 01 fa ce 647 4 nulls: 82 648 copy: 02 1f 02 649 5 nulls: 83 650 copy: 02 06 00 651 ref(24): 1c da ff fe 00 -> ref 101nssss 0 2/11nnnkkk 3 3: a2 db 652 copy: 02 20 24 653 Compressed: 654 05 88 00 26 6c c0 81 b4 f0 04 02 01 fa ce 82 02 655 1f 02 83 02 06 00 a2 db 02 20 24 656 Was 48 bytes; compressed to 27 bytes, compression factor 1.78 658 Figure 11: An ND neighbor advertisement 660 Figure 12 shows the compression of an ND router solicitation. Note 661 that the relatively good compression is not caused by the many zero 662 bytes in the link-layer address of this particular capture (which are 663 unlikely to occur in practice): 7 of these 8 bytes are copied from 664 the pseudo header (the 8th byte cannot be copied as the universal/ 665 local bit needs to be inverted). 667 IP header: 668 60 00 00 00 00 18 3a ff fe 80 00 00 00 00 00 00 669 ae de 48 00 00 00 00 01 ff 02 00 00 00 00 00 00 670 00 00 00 00 00 00 00 02 671 Payload: 672 85 00 90 65 00 00 00 00 01 02 ac de 48 00 00 00 673 00 01 00 00 00 00 00 00 674 Pseudoheader: 675 fe 80 00 00 00 00 00 00 ae de 48 00 00 00 00 01 676 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 02 677 00 00 00 18 00 00 00 3a 678 copy: 04 85 00 90 65 679 ref(33): 00 00 00 00 01 -> ref 101nssss 0 3/11nnnkkk 3 4: a3 dc 680 copy: 02 02 ac 681 ref(42): de 48 00 00 00 00 01 682 -> ref 101nssss 0 4/11nnnkkk 5 3: a4 eb 683 6 nulls: 84 684 Compressed: 685 04 85 00 90 65 a3 dc 02 02 ac a4 eb 84 686 Was 24 bytes; compressed to 13 bytes, compression factor 1.85 688 Figure 12 690 Figure 13 shows the compression of an ND router advertisement. The 691 indefinite lifetime is compressed to four bytes by backreferencing; 692 this could be improved (at the cost of minor additional decompressor 693 complexity) by including some simple runlength mechanism. 695 IP header: 696 60 00 00 00 00 60 3a ff fe 80 00 00 00 00 00 00 697 10 34 00 ff fe 00 11 22 fe 80 00 00 00 00 00 00 698 ae de 48 00 00 00 00 01 699 Payload: 700 86 00 55 c9 40 00 0f a0 1c 5a 38 17 00 00 07 d0 701 01 01 11 22 00 00 00 00 03 04 40 40 ff ff ff ff 702 ff ff ff ff 00 00 00 00 20 02 0d b8 00 00 00 00 703 00 00 00 00 00 00 00 00 20 02 40 10 00 00 03 e8 704 20 02 0d b8 00 00 00 00 21 03 00 01 00 00 00 00 705 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 11 22 706 Pseudoheader: 707 fe 80 00 00 00 00 00 00 10 34 00 ff fe 00 11 22 708 fe 80 00 00 00 00 00 00 ae de 48 00 00 00 00 01 709 00 00 00 60 00 00 00 3a 710 copy: 0c 86 00 55 c9 40 00 0f a0 1c 5a 38 17 711 2 nulls: 80 712 copy: 06 07 d0 01 01 11 22 713 4 nulls: 82 714 copy: 06 03 04 40 40 ff ff 715 ref(2): ff ff -> ref 11nnnkkk 0 0: c0 716 ref(4): ff ff ff ff -> ref 11nnnkkk 2 0: d0 717 4 nulls: 82 718 copy: 04 20 02 0d b8 719 12 nulls: 8a 720 copy: 04 20 02 40 10 721 ref(38): 00 00 03 -> ref 101nssss 0 4/11nnnkkk 1 3: a4 cb 722 copy: 01 e8 723 ref(24): 20 02 0d b8 00 00 00 00 724 -> ref 101nssss 0 2/11nnnkkk 6 0: a2 f0 725 copy: 02 21 03 726 ref(84): 00 01 00 00 00 -> ref 101nssss 0 9/11nnnkkk 3 7: a9 df 727 ref(40): 00 20 02 0d b8 00 00 00 00 00 00 00 728 -> ref 101nssss 1 3/11nnnkkk 2 4: b3 d4 729 ref(120): ff fe 00 11 22 730 -> ref 101nssss 0 14/11nnnkkk 3 3: ae db 731 Compressed: 732 0c 86 00 55 c9 40 00 0f a0 1c 5a 38 17 80 06 07 733 d0 01 01 11 22 82 06 03 04 40 40 ff ff c0 d0 82 734 04 20 02 0d b8 8a 04 20 02 40 10 a4 cb 01 e8 a2 735 f0 02 21 03 a9 df b3 d4 ae db 736 Was 96 bytes; compressed to 58 bytes, compression factor 1.66 738 Figure 13: An ND router advertisement 740 Appendix B. Things we probably won't do 742 This appendix documents parts of the proposal that so far have not 743 proven themselves sufficiently using real-life packets. They may 744 come back if they turn out to be useful; otherwise, they are to be 745 removed on the way to RFC. 747 B.1. Context References 749 A previous version of GHC also allowed the use of context references. 750 However, it appears that context references are more useful at the 751 IPv6/NHC level than here - contexts that are useful often already 752 have been unpacked into the pseudoheader, so they can be used by 753 backreferences. So none of the examples in Appendix A strongly need 754 this capability. Context references might be more useful if we find 755 good ways to populate the 6LoWPAN context with certain strings that 756 are likely to turn up in a certain LoWPAN. 758 +----------+---------------------------------------------+----------+ 759 | code | Action | Argument | 760 | byte | | | 761 +----------+---------------------------------------------+----------+ 762 | 0110iiii | Append all bytes (possibly filling an | | 763 | | incomplete byte with zero bits) from | | 764 | | Context i | | 765 | | | | 766 | 0111iiii | Append 8 bytes from Context i; i.e., the | | 767 | | context value truncated/zero-extended to 8 | | 768 | | bytes, and then append 0000 00FF FE00 | | 769 | | (i.e., 14 bytes total) | | 770 +----------+---------------------------------------------+----------+ 772 B.2. Nibblecode 774 (It is to be decided whether the mechanism described in this section 775 is worth its additional complexity. To make this decision, it would 776 be useful to obtain more packet captures, in particular those that do 777 include ASCII data - the packet-capture-based examples in Appendix A 778 currently do not include nibblecode.) 780 Some headers/header-like structures, such as those used in CoAP or 781 DNS, may use ASCII data. There is very little redundancy by 782 repetition in these (DNS actually has its own compression mechanism 783 for repetition), so the backreferencing mechanism provided in the 784 bytecode is not very effective. 786 Efficient stateless compression for small amounts of ASCII data of 787 this kind is pretty much confined to Huffman (or, for even more 788 complexity, arithmetic) coding. The complexity can be reduced 789 significantly by moving to n-ary Huffman coding, i.e., optimizing not 790 to the bit level, but to a larger level of granularity. Informal 791 experiments by the author show that a 16ary Huffman coding is close 792 to optimal at least for a small corpus of URI data. In other words, 793 basing the encoding on nibbles (4-bit half-bytes) is both nearly 794 optimal and relatively inexpensive to implement. 796 The actual letter frequencies that will occur in more general 6LoWPAN 797 ASCII data are hard to predict. As a first indication, the author 798 has analyzed an HTTP-based URI corpus and found the following lower 799 case letters to be the ASCII characters that occur with highest 800 frequency: aeinorst - it is therefore most useful to compress these. 802 In the encoding proposed, each byte representing one of these eight 803 highly-compressed characters is represented by a single 4-bit nibble 804 from the range 0x8 to 0xF. Bytes representing printable ASCII 805 characters, more specifically bytes from 0x20 to 0x7F, are 806 represented by both of their nibbles. Bytes from 0x00 to 0x1F and 807 from 0x80 to 0xFF are represented by a 0x1 nibble followed by both 808 nibbles of the byte. An 0x0 nibble terminates the nibblecode 809 sequence and returns to bytecode on the next byte boundary. 811 The first nibble of the nibblecode is transmitted right in the "enter 812 nibblecode" bytecode (0x9x - note that since it is never useful to 813 immediately return to bytecode, the bytecode 0x90 is allocated for a 814 different purpose). All other nibbles of the nibblecode are 815 transmitted as a sequence of bytes in most-significant-nibble-first 816 order; any unused nibble in the last byte of a nibblecode sequence is 817 set to 0x0. 819 The encoding is summarized in Figure 14. 821 0 1 822 0 1 2 3 4 5 6 7 8 9 0 1 823 +---+---+---+---+ 824 | 8-F | aeinorst 825 +---+---+---+---+ 89ABCDEF 827 +---+---+---+---+---+---+---+---+ 828 | 2-7 | 0-F | other ASCII 829 +---+---+---+---+---+---+---+---+ 831 +---+---+---+---+---+---+---+---+---+---+---+---+ 832 | 1 | 0-F | 0-F | 0xHH 833 +---+---+---+---+---+---+---+---+---+---+---+---+ 835 +---+---+---+---+ 836 | 0 | return to bytecode 837 +---+---+---+---+ 839 Figure 14: A nibble-based encoding 841 As an example for what level of compression can be expected, the 121 842 bytes of ASCII text shown in Figure 15 (taken from [RFC6690]) are 843 compressed into 183 nibbles of nibblecode, which (including delimiter 844 and padding overhead) need 93 bytes, resulting in a net compression 845 factor of 1.30. (Note that RFC 4944/6LoWPAN-HC supports compression 846 only in the first of a sequence of adaptation layer fragments; 93 847 bytes may not all fit into the first fragment, so any remaining 848 payload would be sent without the benefit of compression.) 850 ;anchor="/sensors/temp" 851 ;rel=describedby, 852 ;anchor="/sensors/temp";rel=alternate 854 Figure 15: Example input text (line-wrapped) 856 Author's Address 858 Carsten Bormann 859 Universitaet Bremen TZI 860 Postfach 330440 861 Bremen D-28359 862 Germany 864 Phone: +49-421-218-63921 865 Fax: +49-421-218-7000 866 Email: cabo@tzi.org