Subject: [Roll] ghc-02 vs grrc-00 examples

From: Michael Richardson <[email-masked]>
Date: Sat, 03 Sep 2011 21:57:05 -0400

In case you haven't read both 
            draft-goyal-roll-rpl-compression-00
and         draft-bormann-6lowpan-ghc-02

here are the numbers listedn for ROLL examples:

GRRC:
   DIO: started at 87 bytes; compressed to 48 bytes, compression factor 1.81
   DIO: started at 89 bytes; compressed to 50 bytes, compression factor 1.78

GHC:
   DIO: started at 92 bytes; compressed to 53 bytes, compression factor 1.74
   DAO: started at 50 bytes; compressed to 27 bytes, compression factor 1.85
   ND:  started at 48 bytes; compressed to 26 bytes, compression factor 1.85

The compression rates are almost identical, and this is without using
GHC's "contexts", which as far as I can tell is not well enough
documented to understand.

What I do not know if how the two sample packets compare: are they even
close to expressing the same thing.

In particular the GRRC document does not list the *actual* packet
contents, since GRRC is not sensitive to the actual field contents.
As such I will be taking Bormann's packets, plus some from Contiki. 
(Hmm. I only brought one econotag to the cottage)

<TCPDUMP-MAINTAINER>
IF YOU HAVE PCAP TRACES OF ROLL PACKETS PLEASE SEND THEM, AS MY SAMPLES
ARE TOO SIMPLE!!!
</TCPDUMP-MAINTAINER>

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Mukul Goyal <[email-masked]>
Date: Sat, 3 Sep 2011 21:44:08 -0500 (CDT)

Hi Michael

Since GHC performance depends on actual packet contents, you would need to use a variety of examples - some showing the best performance GHC is capable of and others where the performance is not so good. Then we have to come up with examples which we could consider as the common case and see how GHC performs for them. I am looking forward to your results eagerly.

Regards
Mukul

----- Original Message -----
From: "Michael Richardson" <[email-masked]>
To: [email-masked]
Sent: Saturday, September 3, 2011 8:57:05 PM
Subject: [Roll] ghc-02 vs grrc-00 examples

GRRC:

GHC:

<TCPDUMP-MAINTAINER>

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Michael Richardson <[email-masked]>
Date: Sun, 04 Sep 2011 12:14:22 -0400

>>>>> "Mukul" == Mukul Goyal <[email-masked]> writes:
    Mukul> Since GHC performance depends on actual packet contents, you
    Mukul> would need to use a variety of examples - some showing the
    Mukul> best performance GHC is capable of and others where the
    Mukul> performance is not so good. Then we have to come up with
    Mukul> examples which we could consider as the common case and see
    Mukul> how GHC performs for them. I am looking forward to your
    Mukul> results eagerly.

GRRC also depends upon the contents of the packets.
It depends upon the assumption that there are fields which are never
used in practice.  

It would be very helpful if you could send pcap captures of rpl-19
format DIO messages which you have applied your re-encoding to.

---

From: Michael Richardson <[email-masked]>
Date: Sun, 04 Sep 2011 21:54:39 -0400

I am attempting to construct an RPL message according to the criteria in
GRRC section 5.1.  Some comments on the GRRC.  If we go this direction,
we need to fix some of these things.

 - there is no reason for the Rouer Information Option to be 24 bytes.
   It can easily be 16 bytes in an uncompressed packet, as long as we are
   dealing with normal subnets, a /64 so we can elide 8 bytes of the prefix.
   This means that the size is not 87 bytes, but in fact 79 bytes.
   The compressed size is not 48 bytes, but 40. 

 - the 40 bytes best case has pretty much everything turned off, or
   perhaps taken from a "context".   This is very significant to me, as
   it means that in fact everything is either provisioned, or must be
   defaults.   This concerns me greatly, as it significantly limits the
   ability to tweak values.  Yes, you can tweak a few values at a time,
   and I guess if they work, then one can update the context.

 - the Metric objects all have implicit length.  We have only defined 
   types 0-5. types 6, and 7 are undefined.  Should they be defined, 
   older implementations will not know how big they are, they should
   always be placed last, as processing could stop at the first object
   that is unknown.

 - I can't see how the DTSN can be taken from a context.  It needs to
   be either transmitted, or be zero.  In particular, as is pointed out
   in draft-dvir-roll-security-extensions, increasing the sequence
   number is the only response available to a bogus DIO message in the
   network. 

 - rpl-19 does no define a defaul value for MaxRankIncrease.  What it
   says is that if 0, this mechanism is disable. GRRC will need to be
   more clear, perhaps defining a default when I1=0.

 - ditto for LifeTime Unit/Default Lifeime, rpl-19 does not define a
   default lifetime or lifetime unit as far as I can see.

 - (I am rather ignorant of metrics, suggestions welcome)

So I have as my inputs. (for those using Lookout, pick a fixed width font)
I'm interested in this email if you think my assumptions are wrong.

ORIGINAL PACKET:

00000000: 9b01 7a5f 

DIO base            8000 0007 0000 0000 0000 0000  ..z_........ ...
00000010: 0000 0000 0000 0000 0000 face            

DODAG cfg option                        040e 0014  ................
00000020: 030a 0000 0100 0000 0000 0000 

ROUTE INFO                              0316 4000  ............... 
00000030: 0001 5180 2001 4830 16ca 0001 0000 0000  ............ ...
00000040: 0000 0000 

METRIC              020c 
metric 1                 0700 6002 0102 
constraint 2                            0402 6002 1000 

summary:
00000000: 9b01 7a5f 8000 0007 0000 0000 0000 0000 
00000010: 0000 0000 0000 0000 0000 face 040e 0014 
00000020: 030a 0000 0100 0000 0000 0000 0316 4000
00000030: 0001 5180 2001 4830 16ca 0001 0000 0000
00000040: 0000 0000 020c 0700 6002 0102 0402 6002
00000050: 1000 

DIO Base 4 bytes base object, 2 header, 2 bytes for DODAGID.
    must be:
         C=0           - no context.
         I=0           - use context?
         L=1           - implicit value 128.
         V=0           - implicit value 0.
         R=1           - 4-bit rank.
         G=0           - Ground value=0, MOP=0 (non-storing), Pref=0.
         T=0           - DTSN field (HOW CAN THIS BE OMITTED?)
         F=0           - no flags, no reserved.
         Ra=0x7        - Rank value.
         Compr=14      - 2 bytes DODAGID.
         DODAGID       - 0xfa 0xce

 results in:
   0x28 0x7e 0xfa 0xce

DODAG cfg option, 2+1.
      F = 0             - flags, A and PCS fields are zero.
      T1= 0             - DIOIntervalDoublings - default value. (from rpl-19)
      T2= 0             - DIORedundancyConstant- default value. (from rpl-19)
      I1= 0             - MaxRankIncrease. default value
      I2= 0             - MinHopRankInc. default value
      O = 0             - RPL Object Function 0 used.
      R = 0             - no reserved field.
      L = 0             - Default Lifetime is elided.

 results in:
   0x84 0x03 0x00

ROUTE INFO, 24 bytes.
 results in:
   0x03 0x16 0x40 0x00
   0x00 0x01 0x51 0x80  <- lifetime, 86400s value.
   0x20 0x01 0x48 0x30    2001:4830:16ca:1::/64
   0x16 0xca 0x00 0x01
   0x00 0x00 0x00 0x00  <- should be omitted.
   0x00 0x00 0x00 0x00

METRIC 8 bytes, 2+3+3.
 0x82 0x06      header.
 object1: T=5   ETX Object
          C=0   metric
          P1/P2=00  highest precedence
          A=0x03    multiplicative
  data: 0xa3 0x01 0x02

 object2: T=3   throughput (made up)
          C=1   constraint          
          O=1   optional
          P2/A=0
  data: 0x60 0x10 0x00  (1 kib/s)

RESULTING PACKET

00000000: 9b01 7a5f                     ICMP
00000004: 287e face                     DIO Base
00000008: 8403 00                       DODAG cfg
0000000b: 0316 4000 0001 5180 2001 4830 16ca 0001  ROUTE INFO (2001:4830:16ca:1::/64)
0000001b: 0000 0000 0000 0000  METRIC
00000023: 8206 a301 0260 1000

---

From: Michael Richardson <[email-masked]>
Date: Sun, 04 Sep 2011 22:10:00 -0400

The result of running a "reasonable" packet, consistent with Example 5.1
From GRRC, outlined in previous message, through a most-primitive, 
single pass GHC compressor.  You can see my code at:

See:
  https://github.com/mcr/roll-ghc

"make check" to run two packets through it. Packet #2 is in the previous
email.  This code gets 1.46 ratio, actually better than on Bormann's
example packet, which was probably more pessimistic about packets
contents. (he has a DAO example as well).

RUNNING 01-bormann          ...Input 92 Output 69 ratio=133%...SUCCEEDED.
RUNNING 02-grrc             ...Input 82 Output 56 ratio=146%...SUCCEEDED.

My code does not make use of the GHC nibble mode (probably not relevant
except for CoAP), nor of the the contexts, nor does it extract from the
pseudo-header values, nor does it look for sequences to repeat longer
than 2 bytes.  (I know that in case 01- there is a sequence of 0xff,
that is two bytes longer than necessary)

I think it's important that we can get almost as good results with a
VERY stupid application of -02 GHC.  It's quite possible that an aware
RPL encoder could encode directly to GHC, perhaps using the
pseudo-header, and certainly using the HC contexts, which are already
assumed to be present.  

The GHC code may already be there and can be applied to CoAP.

The other advantage for GHC is that it means that all nodes continue to
have a full RPL decoder, so there is no issue of whether or not a
product (or a SKU of one) will interoperate out of the box.

====

input packet:
00000000  9b 01 7a 5f 80 00 00 07  00 00 00 00 00 00 00 00  |..z_............|
00000010  00 00 00 00 00 00 00 00  00 00 fa ce 04 0e 00 14  |................|
00000020  03 0d 00 00 01 00 00 00  00 00 00 00 03 16 40 00  |..............@.|
00000030  00 01 51 80 20 01 48 30  16 ca 00 01 00 00 00 00  |..Q. .H0........|
00000040  00 00 00 00 02 0c 07 00  60 02 01 02 04 02 60 02  |........`.....`.|
00000050  10 00                                             |..|
00000052

output packet:
00000000  05 9b 01 7a 5f 80 80 01  07 90 08 fa ce 04 0e 00  |...z_...........|
00000010  14 03 0d 80 01 01 85 03  03 16 40 80 0b 01 51 80  |..........@...Q.|
00000020  20 01 48 30 16 ca 00 01  86 0d 02 0c 07 00 60 02  | .H0..........`.|
00000030  01 02 04 02 60 02 10 90                           |....`...|
00000038