idnits 2.17.1 draft-bormann-6lowpan-ghc-03.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 03, 2011) is 4589 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 268, but not defined == Outdated reference: A later version (-21) exists of draft-ietf-6lowpan-nd-17 ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) == Outdated reference: A later version (-04) exists of draft-bormann-6lowpan-roadmap-00 == Outdated reference: A later version (-14) exists of draft-ietf-core-link-format-07 Summary: 1 error (**), 0 flaws (~~), 5 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 October 03, 2011 5 Expires: April 5, 2012 7 6LoWPAN Generic Compression of Headers and Header-like Payloads 8 draft-bormann-6lowpan-ghc-03 10 Abstract 12 This short I-D provides a complete design for a simple addition to 13 6LoWPAN Header Compression that enables the compression of generic 14 headers and header-like payloads. 16 Status of this Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on April 5, 2012. 33 Copyright Notice 35 Copyright (c) 2011 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 1.1. The Header Compression Coupling Problem . . . . . . . . . 3 52 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 53 2. 6LoWPAN-GHC . . . . . . . . . . . . . . . . . . . . . . . . . 4 54 3. Integrating 6LoWPAN-GHC into 6LoWPAN-HC . . . . . . . . . . . 5 55 3.1. Compressing payloads (UDP and ICMPv6) . . . . . . . . . . 5 56 3.2. Compressing extension headers . . . . . . . . . . . . . . 5 57 3.3. Indicating GHC capability . . . . . . . . . . . . . . . . 6 58 4. IANA considerations . . . . . . . . . . . . . . . . . . . . . 8 59 5. Security considerations . . . . . . . . . . . . . . . . . . . 9 60 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 61 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 62 7.1. Normative References . . . . . . . . . . . . . . . . . . . 11 63 7.2. Informative References . . . . . . . . . . . . . . . . . . 11 64 Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 13 65 Appendix B. Things we probably won't do . . . . . . . . . . . . . 20 66 B.1. Context References . . . . . . . . . . . . . . . . . . . . 20 67 B.2. Nibblecode . . . . . . . . . . . . . . . . . . . . . . . . 20 68 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 23 70 1. Introduction 72 1.1. The Header Compression Coupling Problem 74 6LoWPAN-HC [RFC6282] defines a scheme for header compression in 75 6LoWPAN [RFC4944] packets. As with most header compression schemes, 76 a new specification is needed for every new kind of header that needs 77 to be compressed. In addition, [RFC6282] does not define an 78 extensibility scheme like the ROHC profiles defined in ROHC [RFC3095] 79 [RFC5795]. This leads to the difficult situation that 6LoWPAN-HC 80 tended to be reopened and reexamined each time a new header receives 81 consideration (or an old header is changed and reconsidered) in the 82 6lowpan/roll/core cluster of IETF working groups. While [RFC6282] 83 finally got completed, the underlying problem remains unsolved. 85 The purpose of the present contribution is to plug into [RFC6282] as 86 is, using its NHC (next header compression) concept. We add a 87 slightly less efficient, but vastly more general form of compression 88 for headers of any kind and even for header-like payloads such as 89 those exhibited by routing protocols, DHCP, etc. The objective is to 90 arrive at something that can be defined on a single page and 91 implemented in a couple of lines of code, as opposed to a general 92 data compression scheme such as that defined in [RFC1951]. 94 1.2. Terminology 96 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 97 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 98 document are to be interpreted as described in RFC 2119 [RFC2119]. 100 The term "byte" is used in its now customary sense as a synonym for 101 "octet". 103 2. 6LoWPAN-GHC 105 The format of a compressed header or payload is a simple bytecode. A 106 compressed header consists of a sequence of pieces, each of which 107 begins with a code byte, which may be followed by zero or more bytes 108 as its argument. Some code bytes cause bytes to be laid out in the 109 destination buffer, some simply modify some decompression variables. 111 At the start of decompressing a header or payload within a L2 packet 112 (= fragment), variables "sa" and "na" are initialized as zero. 114 The code bytes are defined as follows: 116 +----------+---------------------------------------------+----------+ 117 | code | Action | Argument | 118 | byte | | | 119 +----------+---------------------------------------------+----------+ 120 | 0kkkkkkk | Append k = 0b0kkkkkkk bytes of data in the | k bytes | 121 | | bytecode argument (k < 96) | of data | 122 | | | | 123 | 1000nnnn | Append 0b0000nnnn+2 bytes of zeroes | | 124 | | | | 125 | 10010000 | STOP code (end of compressed data, see | | 126 | | Section 3.2) | | 127 | | | | 128 | 101nssss | Set up extended arguments for a | | 129 | | backreference: sa += 0b0ssss000, na += | | 130 | | 0b0000n000 | | 131 | | | | 132 | 11nnnkkk | Backreference: n = na+0b00000nnn+2; s = | | 133 | | 0b00000kkk+sa+n; append n bytes from | | 134 | | previously output bytes, starting s bytes | | 135 | | to the left of the current output pointer; | | 136 | | set sa = 0, na = 0 | | 137 +----------+---------------------------------------------+----------+ 139 Note that the following bit combinations are reserved at this time: 140 011xxxxx (possibly for Appendix B.1), and 1001nnnn (where nnnn > 0, 141 possibly for Appendix B.2). 143 For the purposes of the backreferences, the expansion buffer is 144 initialized with the pseudo-header as defined in [RFC2460], at the 145 end of which the target buffer begins. These pseudo-header bytes are 146 therefore available for backreferencing, but not copied into the 147 final result. 149 3. Integrating 6LoWPAN-GHC into 6LoWPAN-HC 151 6LoWPAN-GHC is intended to plug in as an NHC format for 6LoWPAN-HC 152 [RFC6282]. This section shows how this can be done (without 153 supplying the detailed normative text yet, although it could be 154 implemented from this page). 156 3.1. Compressing payloads (UDP and ICMPv6) 158 GHC is by definition generic and can be applied to different kinds of 159 packets. All the examples given in Appendix A are for ICMPv6 160 packets; a single NHC value suffices to define an NHC format for 161 ICMPv6 based on GHC (see below). 163 In addition it may be useful to include an NHC format for UDP, as 164 many headerlike payloads (e.g., DHCPv6) are carried in UDP. 165 [RFC6282] already defines an NHC format for UDP (11110CPP). What 166 remains to be done is to define an analogous NHC byte formatted, e.g. 167 as shown in Figure 1, and simply reference the existing 168 specification, indicating that for 0b11010cpp NHC bytes, the UDP 169 payload is not supplied literally but compressed by 6LoWPAN-GHC. 171 0 1 2 3 4 5 6 7 172 +---+---+---+---+---+---+---+---+ 173 | 1 | 1 | 0 | 1 | 0 | C | P | 174 +---+---+---+---+---+---+---+---+ 176 Figure 1: Proposed NHC byte for UDP GHC 178 To stay in the same general numbering space, we propose 0b11011111 as 179 the NHC byte for ICMPv6 GHC (Figure 2). 181 0 1 2 3 4 5 6 7 182 +---+---+---+---+---+---+---+---+ 183 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 184 +---+---+---+---+---+---+---+---+ 186 Figure 2: Proposed NHC byte for ICMPv6 GHC 188 3.2. Compressing extension headers 190 If the compression of specific extension headers is considered 191 desirable, this can be added in a similar way, e.g. as in Figure 3 192 (however, probably only EID 0 to 3 need to be assigned). As there is 193 no easy way to extract the length field from the GHC-encoded header 194 before decoding, this would make detecting the end of the extension 195 header somewhat complex. The easiest (and most efficient) approach 196 is to completely elide the length field (in the same way NHC already 197 elides the next header field in certain cases) and reconstruct it 198 only on decompression. To serve as a terminator for the extension 199 header, the reserved bytecode 0b10010000 has been assigned as a stop 200 marker -- this is only needed for extension headers, not for final 201 payloads. 203 0 1 2 3 4 5 6 7 204 +---+---+---+---+---+---+---+---+ 205 | 1 | 0 | 1 | 1 | EID |NH | 206 +---+---+---+---+---+---+---+---+ 208 Figure 3: Proposed NHC byte for extension header GHC 210 3.3. Indicating GHC capability 212 The 6LoWPAN baseline includes just [RFC4944], [RFC6282], 213 [I-D.ietf-6lowpan-nd] (see [I-D.bormann-6lowpan-roadmap]). To enable 214 the use of GHC, 6LoWPAN nodes need to know that their neighbors 215 implement it. While this can also simply be administratively 216 required, a transition strategy as well as a way to support mixed 217 networks is required. 219 One way to know a neighbor does implement GHC is receiving a packet 220 from that neighbor with GHC in it ("implicit capability detection"). 221 However, there needs to be a way to bootstrap this, as nobody ever 222 would start sending packets with GHC otherwise. 224 To minimize the impact on [I-D.ietf-6lowpan-nd], we propose adding an 225 ND option 6LoWPAN Capability Indication (6CIO), as illustrated in 226 Figure 4. 228 0 1 2 3 229 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 230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 231 | Type | Length = 1 |_____________________________|G| 232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 233 |_______________________________________________________________| 234 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 Figure 4: 6LoWPAN Capability Indication Option (6CIO) 238 The G bit indicates whether the node sending the option is GHC 239 capable. 241 The 6CIO option will typically only be ever sent in 6LoWPAN-ND RS 242 packets (it then cannot itself be GHC compressed unless the host 243 desires to limit itself to talking to GHC capable routers); the 244 resulting 6LoWPAN-ND RA can already make use of GHC and thus indicate 245 GHC capability implicitly, which in turn allows the nodes to use GHC 246 in the 6LoWPAN-ND NS/NA exchange. 248 6CIO can also be used for future options that need to be negotiated 249 between 6LoWPAN peers; an IANA registry will administrate the flags. 250 (Bits marked by underscores in Figure 4 are reserved for future 251 allocation, i.e., they MUST be sent as zero and MUST be ignored on 252 reception until allocated. Length values larger than 1 MUST be 253 supported for future extensions; the additional bits in the option 254 are then reserved in the same way. For the purposes of the IANA 255 registry, the bits are numbered in msb-first order from the 16th bit 256 of the option onwards, i.e., the G bit is flag number 15.) 257 (Additional bits may also be used by a followon version of this 258 document if some bit combinations that have been left reserved here 259 are then used in an upward compatible manner.) 261 4. IANA considerations 263 In the IANA registry for the 6LOWPAN_NHC header type, IANA would need 264 to add the assignments in Figure 5. 266 10110IIN: Extension header GHC [RFCthis] 267 11010CPP: UDP GHC [RFCthis] 268 11011111: ICMPv6 GHC [RFCthis] 270 Figure 5: IANA assignments for the NHC byte 272 IANA needs to allocate an ND option number for 6CIO. 274 An IANA registry is needed for 6LoWPAN capability flags. (Policy 275 TBD.) 277 5. Security considerations 279 The security considerations of [RFC4944] and [RFC6282] apply. As 280 usual in protocols with packet parsing/construction, care must be 281 taken in implementations to avoid buffer overflows and in particular 282 (with respect to the back-referencing) out-of-area references during 283 decompression. 285 One additional consideration is that an attacker may send a forged 286 packet that makes a second node believe a third victim node is GHC- 287 capable. If it is not, this may prevent packets sent by the second 288 node from reaching the third node. 290 No mitigation is proposed (or known) for this attack, except that a 291 node that does implement GHC is not vulnerable. However, with 292 unsecured ND, a number of attacks with similar outcomes are already 293 possible, so there is little incentive to make use of this additional 294 attack. With secured ND, 6CIO is also secured; nodes relying on 295 secured ND therefore should use 6CIO bidirectionally (and limit the 296 implicit capability detection to secured ND packets carrying GHC) 297 instead of basing their neighbor capability assumptions on receiving 298 any kind of unprotected packet. 300 6. Acknowledgements 302 Colin O'Flynn has repeatedly insisted that some form of compression 303 for ICMPv6 and ND packets might be beneficial. He actually wrote his 304 own draft, [I-D.oflynn-6lowpan-icmphc], which compresses better, but 305 addresses basic ICMPv6/ND only and needs a much longer spec (around 306 17 pages of detailed spec, as compared to the single page of core 307 spec here). This motivated the author to try something simple, yet 308 general. Special thanks go to Colin for indicating that he indeed 309 considers his draft superseded by the present one. 311 The examples given are based on pcap files that Colin O'Flynn and 312 Owen Kirby provided. 314 7. References 316 7.1. Normative References 318 [I-D.ietf-6lowpan-nd] 319 Shelby, Z., Chakrabarti, S., and E. Nordmark, "Neighbor 320 Discovery Optimization for Low Power and Lossy Networks 321 (6LoWPAN)", draft-ietf-6lowpan-nd-17 (work in progress), 322 June 2011. 324 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 325 Requirement Levels", BCP 14, RFC 2119, March 1997. 327 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 328 (IPv6) Specification", RFC 2460, December 1998. 330 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 331 "Transmission of IPv6 Packets over IEEE 802.15.4 332 Networks", RFC 4944, September 2007. 334 [RFC6282] Hui, J. and P. Thubert, "Compression Format for IPv6 335 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 336 September 2011. 338 7.2. Informative References 340 [I-D.bormann-6lowpan-roadmap] 341 Bormann, C., "6LoWPAN Roadmap and Implementation Guide", 342 draft-bormann-6lowpan-roadmap-00 (work in progress), 343 March 2011. 345 [I-D.ietf-core-link-format] 346 Shelby, Z., "CoRE Link Format", 347 draft-ietf-core-link-format-07 (work in progress), 348 July 2011. 350 [I-D.oflynn-6lowpan-icmphc] 351 O'Flynn, C., "ICMPv6/ND Compression for 6LoWPAN Networks", 352 draft-oflynn-6lowpan-icmphc-00 (work in progress), 353 July 2010. 355 [RFC1951] Deutsch, P., "DEFLATE Compressed Data Format Specification 356 version 1.3", RFC 1951, May 1996. 358 [RFC3095] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H., 359 Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, 360 K., Liu, Z., Martensson, A., Miyazaki, A., Svanbro, K., 361 Wiebke, T., Yoshimura, T., and H. Zheng, "RObust Header 362 Compression (ROHC): Framework and four profiles: RTP, UDP, 363 ESP, and uncompressed", RFC 3095, July 2001. 365 [RFC5795] Sandlund, K., Pelletier, G., and L-E. Jonsson, "The RObust 366 Header Compression (ROHC) Framework", RFC 5795, 367 March 2010. 369 Appendix A. Examples 371 This section demonstrates some relatively realistic examples derived 372 from actual PCAP dumps taken at previous interops. Unfortunately, 373 for these dumps, no context information was available, so the 374 relatively powerful effect of context-based compression is not shown. 375 (TBD: Add a couple DHCP examples.) 377 Figure 6 shows an RPL DODAG Information Solicitation, a quite short 378 RPL message that obviously cannot be improved much. 380 IP header: 381 60 00 00 00 00 08 3a ff fe 80 00 00 00 00 00 00 382 02 1c da ff fe 00 20 24 ff 02 00 00 00 00 00 00 383 00 00 00 00 00 00 00 1a 384 Payload: 385 9b 00 6b de 00 00 00 00 386 Pseudoheader: 387 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 20 24 388 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 1a 389 00 00 00 08 00 00 00 3a 390 copy: 04 9b 00 6b de 391 4 nulls: 82 392 Compressed: 393 04 9b 00 6b de 82 394 Was 8 bytes; compressed to 6 bytes, compression factor 1.33 396 Figure 6: A simple RPL example 398 Figure 7 shows an RPL DODAG Information Object, a longer RPL control 399 message that is improved a bit more (but would likely benefit 400 additionally from a context reference). Note that the compressed 401 output exposes an inefficiency in the simple-minded compressor used 402 to generate it; this does not devalue the example since constrained 403 nodes are quite likely to make use of simple-minded compressors. 405 IP header: 406 60 00 00 00 00 5c 3a ff fe 80 00 00 00 00 00 00 407 02 1c da ff fe 00 30 23 ff 02 00 00 00 00 00 00 408 00 00 00 00 00 00 00 1a 409 Payload: 410 9b 01 7a 5f 00 f0 01 00 88 00 00 00 20 02 0d b8 411 00 00 00 00 00 00 00 ff fe 00 fa ce 04 0e 00 14 412 09 ff 00 00 01 00 00 00 00 00 00 00 08 1e 80 20 413 ff ff ff ff ff ff ff ff 00 00 00 00 20 02 0d b8 414 00 00 00 00 00 00 00 ff fe 00 fa ce 03 0e 40 00 415 ff ff ff ff 20 02 0d b8 00 00 00 00 416 Pseudoheader: 417 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 418 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 1a 419 00 00 00 5c 00 00 00 3a 420 copy: 09 9b 01 7a 5f 00 f0 01 00 88 421 3 nulls: 81 422 copy: 04 20 02 0d b8 423 7 nulls: 85 424 ref(52): ff fe 00 -> ref 101nssss 0 6/11nnnkkk 1 1: a6 c9 425 copy: 08 fa ce 04 0e 00 14 09 ff 426 2 nulls: 80 427 copy: 01 01 428 7 nulls: 85 429 copy: 06 08 1e 80 20 ff ff 430 ref(2): ff ff -> ref 11nnnkkk 0 0: c0 431 ref(4): ff ff ff ff -> ref 11nnnkkk 2 0: d0 432 4 nulls: 82 433 ref(48): 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 fa ce 434 -> ref 101nssss 1 4/11nnnkkk 6 0: b4 f0 435 copy: 03 03 0e 40 436 ref(9): 00 ff -> ref 11nnnkkk 0 7: c7 437 ref(28): ff ff ff -> ref 101nssss 0 3/11nnnkkk 1 1: a3 c9 438 ref(24): 20 02 0d b8 00 00 00 00 439 -> ref 101nssss 0 2/11nnnkkk 6 0: a2 f0 440 Compressed: 441 09 9b 01 7a 5f 00 f0 01 00 88 81 04 20 02 0d b8 442 85 a6 c9 08 fa ce 04 0e 00 14 09 ff 80 01 01 85 443 06 08 1e 80 20 ff ff c0 d0 82 b4 f0 03 03 0e 40 444 c7 a3 c9 a2 f0 445 Was 92 bytes; compressed to 53 bytes, compression factor 1.74 447 Figure 7: A longer RPL example 449 Similarly, Figure 8 shows an RPL DAO message. One of the embedded 450 addresses is copied right out of the pseudoheader, the other one is 451 effectively converted from global to local by providing the prefix 452 FE80 literally, inserting a number of nulls, and copying (some of) 453 the IID part again out of the pseudoheader. Note that a simple 454 implementation would probably emit fewer nulls and copy the entire 455 IID; there are multiple ways to encode this 50-byte payload into 27 456 bytes. 458 IP header: 459 60 00 00 00 00 32 3a ff 20 02 0d b8 00 00 00 00 460 00 00 00 ff fe 00 33 44 20 02 0d b8 00 00 00 00 461 00 00 00 ff fe 00 11 22 462 Payload: 463 9b 02 58 7d 01 80 00 f1 05 12 00 80 20 02 0d b8 464 00 00 00 00 00 00 00 ff fe 00 33 44 06 14 00 80 465 f1 00 fe 80 00 00 00 00 00 00 00 00 00 ff fe 00 466 11 22 467 Pseudoheader: 468 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 33 44 469 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 11 22 470 00 00 00 32 00 00 00 3a 471 copy: 0c 9b 02 58 7d 01 80 00 f1 05 12 00 80 472 ref(52): 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 33 44 473 -> ref 101nssss 1 4/11nnnkkk 6 4: b4 f4 474 copy: 08 06 14 00 80 f1 00 fe 80 475 9 nulls: 87 476 ref(58): ff fe 00 11 22 -> ref 101nssss 0 6/11nnnkkk 3 5: a6 dd 477 Compressed: 478 0c 9b 02 58 7d 01 80 00 f1 05 12 00 80 b4 f4 08 479 06 14 00 80 f1 00 fe 80 87 a6 dd 480 Was 50 bytes; compressed to 27 bytes, compression factor 1.85 482 Figure 8: An RPL DAO message 484 Figure 9 shows the effect of compressing a simple ND neighbor 485 solicitation (again, no context-based compression). 487 IP header: 488 60 00 00 00 00 30 3a ff 20 02 0d b8 00 00 00 00 489 00 00 00 ff fe 00 3b d3 fe 80 00 00 00 00 00 00 490 02 1c da ff fe 00 30 23 491 Payload: 492 87 00 a7 68 00 00 00 00 fe 80 00 00 00 00 00 00 493 02 1c da ff fe 00 30 23 01 01 3b d3 00 00 00 00 494 1f 02 00 00 00 00 00 06 00 1c da ff fe 00 20 24 495 Pseudoheader: 496 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 3b d3 497 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 498 00 00 00 30 00 00 00 3a 499 copy: 04 87 00 a7 68 500 4 nulls: 82 501 ref(32): fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 502 -> ref 101nssss 1 2/11nnnkkk 6 0: b2 f0 503 copy: 04 01 01 3b d3 504 4 nulls: 82 505 copy: 02 1f 02 506 5 nulls: 83 507 copy: 02 06 00 508 ref(24): 1c da ff fe 00 -> ref 101nssss 0 2/11nnnkkk 3 3: a2 db 509 copy: 02 20 24 510 Compressed: 511 04 87 00 a7 68 82 b2 f0 04 01 01 3b d3 82 02 1f 512 02 83 02 06 00 a2 db 02 20 24 513 Was 48 bytes; compressed to 26 bytes, compression factor 1.85 515 Figure 9: An ND neighbor solicitation 517 Figure 10 shows the compression of an ND neighbor advertisement. 519 IP header: 520 60 00 00 00 00 30 3a fe fe 80 00 00 00 00 00 00 521 02 1c da ff fe 00 30 23 20 02 0d b8 00 00 00 00 522 00 00 00 ff fe 00 3b d3 523 Payload: 524 88 00 26 6c c0 00 00 00 fe 80 00 00 00 00 00 00 525 02 1c da ff fe 00 30 23 02 01 fa ce 00 00 00 00 526 1f 02 00 00 00 00 00 06 00 1c da ff fe 00 20 24 527 Pseudoheader: 528 fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 529 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 3b d3 530 00 00 00 30 00 00 00 3a 531 copy: 05 88 00 26 6c c0 532 3 nulls: 81 533 ref(48): fe 80 00 00 00 00 00 00 02 1c da ff fe 00 30 23 534 -> ref 101nssss 1 4/11nnnkkk 6 0: b4 f0 535 copy: 04 02 01 fa ce 536 4 nulls: 82 537 copy: 02 1f 02 538 5 nulls: 83 539 copy: 02 06 00 540 ref(24): 1c da ff fe 00 -> ref 101nssss 0 2/11nnnkkk 3 3: a2 db 541 copy: 02 20 24 542 Compressed: 543 05 88 00 26 6c c0 81 b4 f0 04 02 01 fa ce 82 02 544 1f 02 83 02 06 00 a2 db 02 20 24 545 Was 48 bytes; compressed to 27 bytes, compression factor 1.78 547 Figure 10: An ND neighbor advertisement 549 Figure 11 shows the compression of an ND router solicitation. Note 550 that the relatively good compression is not caused by the many zero 551 bytes in the link-layer address of this particular capture (which are 552 unlikely to occur in practice): 7 of these 8 bytes are copied from 553 the pseudo header (the 8th byte cannot be copied as the universal/ 554 local bit needs to be inverted). 556 IP header: 557 60 00 00 00 00 18 3a ff fe 80 00 00 00 00 00 00 558 ae de 48 00 00 00 00 01 ff 02 00 00 00 00 00 00 559 00 00 00 00 00 00 00 02 560 Payload: 561 85 00 90 65 00 00 00 00 01 02 ac de 48 00 00 00 562 00 01 00 00 00 00 00 00 563 Pseudoheader: 564 fe 80 00 00 00 00 00 00 ae de 48 00 00 00 00 01 565 ff 02 00 00 00 00 00 00 00 00 00 00 00 00 00 02 566 00 00 00 18 00 00 00 3a 567 copy: 04 85 00 90 65 568 ref(33): 00 00 00 00 01 -> ref 101nssss 0 3/11nnnkkk 3 4: a3 dc 569 copy: 02 02 ac 570 ref(42): de 48 00 00 00 00 01 571 -> ref 101nssss 0 4/11nnnkkk 5 3: a4 eb 572 6 nulls: 84 573 Compressed: 574 04 85 00 90 65 a3 dc 02 02 ac a4 eb 84 575 Was 24 bytes; compressed to 13 bytes, compression factor 1.85 577 Figure 11 579 Figure 12 shows the compression of an ND router advertisement. The 580 indefinite lifetime is compressed to four bytes by backreferencing; 581 this could be improved (at the cost of minor additional decompressor 582 complexity) by including some simple runlength mechanism. 584 IP header: 585 60 00 00 00 00 60 3a ff fe 80 00 00 00 00 00 00 586 10 34 00 ff fe 00 11 22 fe 80 00 00 00 00 00 00 587 ae de 48 00 00 00 00 01 588 Payload: 589 86 00 55 c9 40 00 0f a0 1c 5a 38 17 00 00 07 d0 590 01 01 11 22 00 00 00 00 03 04 40 40 ff ff ff ff 591 ff ff ff ff 00 00 00 00 20 02 0d b8 00 00 00 00 592 00 00 00 00 00 00 00 00 20 02 40 10 00 00 03 e8 593 20 02 0d b8 00 00 00 00 21 03 00 01 00 00 00 00 594 20 02 0d b8 00 00 00 00 00 00 00 ff fe 00 11 22 595 Pseudoheader: 596 fe 80 00 00 00 00 00 00 10 34 00 ff fe 00 11 22 597 fe 80 00 00 00 00 00 00 ae de 48 00 00 00 00 01 598 00 00 00 60 00 00 00 3a 599 copy: 0c 86 00 55 c9 40 00 0f a0 1c 5a 38 17 600 2 nulls: 80 601 copy: 06 07 d0 01 01 11 22 602 4 nulls: 82 603 copy: 06 03 04 40 40 ff ff 604 ref(2): ff ff -> ref 11nnnkkk 0 0: c0 605 ref(4): ff ff ff ff -> ref 11nnnkkk 2 0: d0 606 4 nulls: 82 607 copy: 04 20 02 0d b8 608 12 nulls: 8a 609 copy: 04 20 02 40 10 610 ref(38): 00 00 03 -> ref 101nssss 0 4/11nnnkkk 1 3: a4 cb 611 copy: 01 e8 612 ref(24): 20 02 0d b8 00 00 00 00 613 -> ref 101nssss 0 2/11nnnkkk 6 0: a2 f0 614 copy: 02 21 03 615 ref(84): 00 01 00 00 00 -> ref 101nssss 0 9/11nnnkkk 3 7: a9 df 616 ref(40): 00 20 02 0d b8 00 00 00 00 00 00 00 617 -> ref 101nssss 1 3/11nnnkkk 2 4: b3 d4 618 ref(120): ff fe 00 11 22 619 -> ref 101nssss 0 14/11nnnkkk 3 3: ae db 620 Compressed: 621 0c 86 00 55 c9 40 00 0f a0 1c 5a 38 17 80 06 07 622 d0 01 01 11 22 82 06 03 04 40 40 ff ff c0 d0 82 623 04 20 02 0d b8 8a 04 20 02 40 10 a4 cb 01 e8 a2 624 f0 02 21 03 a9 df b3 d4 ae db 625 Was 96 bytes; compressed to 58 bytes, compression factor 1.66 627 Figure 12: An ND router advertisement 629 Appendix B. Things we probably won't do 631 This appendix documents parts of the proposal that so far have not 632 proven themselves sufficiently using real-life packets. They may 633 come back if they turn out to be useful; otherwise, they are to be 634 removed on the way to RFC. 636 B.1. Context References 638 A previous version of GHC also allowed the use of context references. 639 However, it appears that context references are more useful at the 640 IPv6/NHC level than here - contexts that are useful often already 641 have been unpacked into the pseudoheader, so they can be used by 642 backreferences. So none of the examples in Appendix A strongly need 643 this capability. Context references might be more useful if we find 644 good ways to populate the 6LoWPAN context with certain strings that 645 are likely to turn up in a certain LoWPAN. 647 +----------+---------------------------------------------+----------+ 648 | code | Action | Argument | 649 | byte | | | 650 +----------+---------------------------------------------+----------+ 651 | 0110iiii | Append all bytes (possibly filling an | | 652 | | incomplete byte with zero bits) from | | 653 | | Context i | | 654 | | | | 655 | 0111iiii | Append 8 bytes from Context i; i.e., the | | 656 | | context value truncated/zero-extended to 8 | | 657 | | bytes, and then append 0000 00FF FE00 | | 658 | | (i.e., 14 bytes total) | | 659 +----------+---------------------------------------------+----------+ 661 B.2. Nibblecode 663 (It is to be decided whether the mechanism described in this section 664 is worth its additional complexity. To make this decision, it would 665 be useful to obtain more packet captures, in particular those that do 666 include ASCII data - the packet-capture-based examples in Appendix A 667 currently do not include nibblecode.) 669 Some headers/header-like structures, such as those used in CoAP or 670 DNS, may use ASCII data. There is very little redundancy by 671 repetition in these (DNS actually has its own compression mechanism 672 for repetition), so the backreferencing mechanism provided in the 673 bytecode is not very effective. 675 Efficient stateless compression for small amounts of ASCII data of 676 this kind is pretty much confined to Huffman (or, for even more 677 complexity, arithmetic) coding. The complexity can be reduced 678 significantly by moving to n-ary Huffman coding, i.e., optimizing not 679 to the bit level, but to a larger level of granularity. Informal 680 experiments by the author show that a 16ary Huffman coding is close 681 to optimal at least for a small corpus of URI data. In other words, 682 basing the encoding on nibbles (4-bit half-bytes) is both nearly 683 optimal and relatively inexpensive to implement. 685 The actual letter frequencies that will occur in more general 6LoWPAN 686 ASCII data are hard to predict. As a first indication, the author 687 has analyzed an HTTP-based URI corpus and found the following lower 688 case letters to be the ASCII characters that occur with highest 689 frequency: aeinorst - it is therefore most useful to compress these. 691 In the encoding proposed, each byte representing one of these eight 692 highly-compressed characters is represented by a single 4-bit nibble 693 from the range 0x8 to 0xF. Bytes representing printable ASCII 694 characters, more specifically bytes from 0x20 to 0x7F, are 695 represented by both of their nibbles. Bytes from 0x00 to 0x1F and 696 from 0x80 to 0xFF are represented by a 0x1 nibble followed by both 697 nibbles of the byte. An 0x0 nibble terminates the nibblecode 698 sequence and returns to bytecode on the next byte boundary. 700 The first nibble of the nibblecode is transmitted right in the "enter 701 nibblecode" bytecode (0x9x - note that since it is never useful to 702 immediately return to bytecode, the bytecode 0x90 is allocated for a 703 different purpose). All other nibbles of the nibblecode are 704 transmitted as a sequence of bytes in most-significant-nibble-first 705 order; any unused nibble in the last byte of a nibblecode sequence is 706 set to 0x0. 708 The encoding is summarized in Figure 13. 710 0 1 711 0 1 2 3 4 5 6 7 8 9 0 1 712 +---+---+---+---+ 713 | 8-F | aeinorst 714 +---+---+---+---+ 89ABCDEF 716 +---+---+---+---+---+---+---+---+ 717 | 2-7 | 0-F | other ASCII 718 +---+---+---+---+---+---+---+---+ 720 +---+---+---+---+---+---+---+---+---+---+---+---+ 721 | 1 | 0-F | 0-F | 0xHH 722 +---+---+---+---+---+---+---+---+---+---+---+---+ 724 +---+---+---+---+ 725 | 0 | return to bytecode 726 +---+---+---+---+ 728 Figure 13: A nibble-based encoding 730 As an example for what level of compression can be expected, the 121 731 bytes of ASCII text shown in Figure 14 (taken from 732 [I-D.ietf-core-link-format]) are compressed into 183 nibbles of 733 nibblecode, which (including delimiter and padding overhead) need 93 734 bytes, resulting in a net compression factor of 1.30. (Note that 735 RFC 4944/6LoWPAN-HC supports compression only in the first of a 736 sequence of adaptation layer fragments; 93 bytes may not all fit into 737 the first fragment, so any remaining payload would be sent without 738 the benefit of compression.) 740 ;anchor="/sensors/temp" 741 ;rel=describedby, 742 ;anchor="/sensors/temp";rel=alternate 744 Figure 14: Example input text (line-wrapped) 746 Author's Address 748 Carsten Bormann 749 Universitaet Bremen TZI 750 Postfach 330440 751 Bremen D-28359 752 Germany 754 Phone: +49-421-218-63921 755 Fax: +49-421-218-7000 756 Email: cabo@tzi.org