Subject: Re: [Dtls-iot] 32 bit alignment with IoT

From: Richard Kelsey <[email-masked]>
Date: Mon, 6 Jan 2014 12:02:25 -0500

> From: Michael Richardson <mcr at sandelman.ca>
> Date: Wed, 18 Dec 2013 10:23:34 -0500
> 
> Padding sent as zeroes is pretty easy to compress out if one is compressing
> generically.  I've advocated for doing sensible protocol design, leaving
> ourselves appropriate places to introduce new values, and look at what the
> byte count is after some naive, trivial compression as provided by 6lowpan HC
> and GHC.

GHC is good at compressing out blocks of zeroes.  It doesn't do
anything with single zero bytes, which 16-bit alignment of small
values produces.  For example, DCHPv6 has a lot of 16-bit fields
where the high byte is zero.  GHC doesn't help.

Also, having implemented GHC, I don't consider it trivial.  You
either have to write generic compression code, which consumes a
chunk of RAM and/or CPU cycles, or build GHC into the protocol
implementation, which adds more complexity.  If a protocol is
intended for the IoT then we should keep it compact and not rely
on GHC or other compression scheme.

                                       -Richard
This email and any attachments may be confidential. If so, do not disseminate without the sender’s authorization. If you are not the intended recipient, please delete it and notify the sender. Email transmissions cannot be guaranteed to be error-free or virus-free and we accept no liability. Silicon Labs does not intend or authorize emails to act as legally binding contracts.

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 6 Jan 2014 21:28:40 +0100

> where the high byte is zero.  GHC doesn't help.

Indeed.  I considered adding something like a predictor byte code (which carries a bitfield saying which of the following uncompressed bytes are zero, as in RFC 2687’s FSE construction).
I didn’t come up with anything that was a real improvement with my current corpus, so I left it out.
But I’m not claiming I examined the entire design space — I don’t have a good corpus of DHCPv6 packets to work with (hint, hint).

> Also, having implemented GHC, I don't consider it trivial.  

Well, it is trivial compared to, say, RFC 1951, but it is still LZ compression.
There also is a “low-hanging fruit” style implementation technique for the compressor, maybe something for LWIG to document.
The decompressor, though, should indeed be trivial (but does need a second buffer).

I completely agree that is is better to shoot for compact protocol encodings in the first place than to fix garrulous encodings after the fact by compression.  But we do have a few of the latter that aren’t going away.

Grüße, Carsten

---

From: Michael StJohns <[email-masked]>
Date: Mon, 06 Jan 2014 17:27:40 -0500

Are we trying to solve the wrong problem?  E.g. the trade off is between 
processing time (and energy) and transmission time (and energy).  So any 
reduction of the energy used for transmission, is probably going to be 
somewhat offset by the cost of compression.  The question then becomes 
is it worth it to spend the time (and engineering cycles) in this space 
for a small reduction in transmitted bits?

Mike

On 1/6/2014 3:28 PM, Carsten Bormann wrote:
> _______________________________________________
> dtls-iot mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dtls-iot

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 6 Jan 2014 23:44:14 +0100

On 06 Jan 2014, at 23:27, Michael StJohns <[email-masked]> wrote:

> The question then becomes is it worth it to spend the time (and engineering cycles) in this space for a small reduction in transmitted bits?

Among other things (payload sizes etc.), the answer depends on the garrulity of the legacy protocol.

For DTLS 1.2 (with our current cipher suites) in 6LoWPAN applications, I’m pretty sure the answer is a resounding YES.
If DTLS 1.3 goes right, this may become less obvious.
(For IPv6 and UDP headers, the answer is so obviously yes that RFC 6282 is a mandatory part of 6LoWPAN, and we are even considering getting rid of the uncompressed option.)

Grüße, Carsten

---

From: Michael Richardson <[email-masked]>
Date: Mon, 06 Jan 2014 18:22:09 -0500

> Well, it is trivial compared to, say, RFC 1951, but it is still LZ
    > compression.  There also is a “low-hanging fruit” style implementation
    > technique for the compressor, maybe something for LWIG to document.

https://github.com/mcr/roll-ghc/blob/master/ghc.c
is 118 lines.... I didn't know how to use the contexts, so I didn't.

With only this code only, I was able to match the manually "compressed"
(optimized) version of ROLL DIO messages, fitting the result into a single
15.4 frame.

    > I completely agree that is is better to shoot for compact protocol
    > encodings in the first place than to fix garrulous encodings after the
    > fact by compression.  But we do have a few of the latter that aren’t
    > going away.

I moderately agree with this statement slightly.

--
Michael Richardson <[email-masked]>, Sandelman Software Works

---

From: Michael Richardson <[email-masked]>
Date: Mon, 06 Jan 2014 18:27:02 -0500

Michael StJohns <[email-masked]> wrote:
    > Are we trying to solve the wrong problem?  E.g. the trade off is
    > between processing time (and energy) and transmission time (and
    > energy).  So any reduction of the energy used for transmission, is
    > probably going to be somewhat offset by the cost of compression.  The
    > question then becomes is it worth it to spend the time (and engineering
    > cycles) in this space for a small reduction in transmitted bits?

The tradeoff is quite complex.

The transmission cost has some serious step functions: if you need more than
one 15.4 frame,  your cost goes up significantly, because you might have to
stay awake a lot longer to get your packet through, and might have to
retransmit the whole thing from scratch.

CPU cycles, in even the smallest devices are becoming cheaper and cheaper,
but cost of transmit power is not.  That's why we are moving away from
purpose built protocols (like Zwave) to interoperable network protocols, the
NRE for the purpose built protocols is better spent writing compression
algorithms.

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 7 Jan 2014 08:38:06 +0100

On 07 Jan 2014, at 00:22, Michael Richardson <[email-masked]> wrote:

> is 118 lines….

Nice example of a low-hanging fruit implementation (63 SLOC for the actual compressor).

> I didn't know how to use the contexts, so I didn’t.

The contexts are gone from the current spec, but with more code you could use more back referencing than just the run length encoding this simple code is using.

(This code is emitting a 0x90 for 18 zeroes, cnt < 16 on line 52 isn’t the right termination condition.
The examples also include another 0x90 at the end that doesn’t seem to be an actual stop code; none is needed for compression of header-like payloads anyway.
But all this can be easily fixed.  
Also, run codes with more than two consecutive 0xc0s could be further compressed with little additional effort.
On the other hand, you don’t actually make use of the insts array, so this could be a simple pointer.)

> (optimized) version of ROLL DIO messages, fitting the result into a single

Nice!

> I moderately agree with this statement slightly.

:-)

You have to modulate this statement with a suitable value for “compact”, indeed.

Grüße, Carsten