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