Subject: [manet] Ideas about a schema-based compression/decompression for RFC5444

From: Henning Rogge <[email-masked]>
Date: Wed, 23 Jan 2013 12:32:10 +0100

This is an example for a "schema based compression" I am thinking about. 
I use NHDP without the address part as an example to describe the idea.

This example is not complete, because I still have to work through the 
details of the address block.

Schema Number: 42
-----------------
Header:
* Message Type 0
* Optional Fields: mhashoplimit, mhassequencenumber
* Address Length: 4
* Hop Limit 1

Mandatory Message TLVs:
* TLV type 1
*-- extension type 0
*-- value length 1

Optional Message TLVs:
* TLV type 0:
*-- extension type 0
*-- value length 1

Compression idea
----------------

Remove everything from RFC5444 message that can be reconstructed from 
Schema. Use bitfields to describe which optional TLVs are present in 
TLV-block.

The message to be compressed is a normal NHDP message with 4-byte 
addresses, hoplimit 1, sequence number 0x1234, a VALDIITY_TIME TLV with 
value 0x10 and an INTERVAL_TIME TLV with value 0x01.

Compression
-----------

The message always starts with the schema number (maybe a two-byte 
schema number would be better to allow versioning?)

# 42

Add compressed msg-size to message.

# xx xx

If the msg-flags and msg-addr-length field is specified in the schema, 
skip them. Otherwise add them to the message

# (none in this example)

Add all optional message header fields that are marked in the flags and 
are not already defined in the schema.

# 12 34 (sequence number value)

Add a bitfield with one bit for each Optional Message TLV. Add another 
bit if TLVs follow that are not present in the Schema.

# 80 ( 1st optional message TLV is present, no "other TLVs")

Add all mandatory and all selected optional TLVs to the message. Leave 
out all fields that can be reconstructed from the Schema.

# 10 (value of VALIDITY-TIME TLV)
# 01 (value of INTERVAL-TIME TLV)

If there are other TLVs (not described in the schema), add the number of 
bytes needed to describe them and the TLVs itself

# (none in this example)

Result
------

The complete message (without the address block and its TLVs has been 
reduced from

# 00 yy yy 53 01 12 34 (message header)
# 00 08 (tlv block length)
# 01 10 01 10 (VALIDITY-TIME 0x10)
# 00 10 01 01 (INTERVAL-TIME 0x01)

to

# 00 xx xx 12 34 80 10 01

Henning Rogge
-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de

---

From: Abdussalam Baryun <[email-masked]>
Date: Wed, 23 Jan 2013 12:41:33 +0100

Do you mean new algorithm of compress than one used for OLSRv2, and
this was the post you mention that will be posted,

AB

---

From: Henning Rogge <[email-masked]>
Date: Wed, 23 Jan 2013 12:50:57 +0100

On 01/23/2013 12:41 PM, Abdussalam Baryun wrote:
> Do you mean new algorithm of compress than one used for OLSRv2,

No.

Its an example for an idea for a schema-based compression for RFC5444.

The idea is that you know MORE about the content of your message in a 
certain deployment than on the generic protocol level. The compression 
tries to take advantage of this by eliminating lots of redundancy that 
can be reconstructed from the Schema.

 > and this was the post you mention that will be posted,

Yes.

Henning Rogge

---

From: Abdussalam Baryun <[email-masked]>
Date: Wed, 23 Jan 2013 12:57:30 +0100

Ok so this schema can be used for all MANET protocols that use 5444
including OSRv2, am I right, please advise,

AB

---

From: Henning Rogge <[email-masked]>
Date: Wed, 23 Jan 2013 13:03:48 +0100

> including OSRv2, am I right, please advise,

Yes, that is the plan.

I think it might allow us to focus on clean protocols during the design 
while being able to get more compact byte encoding on deployment level.

Henning Rogge

---

From: Joseph Macker <[email-masked]>
Date: Wed, 23 Jan 2013 16:42:27 -0500

On Wed, Jan 23, 2013 at 7:03 AM, Henning Rogge <
[email-masked]> wrote:

> mailto:henning.rogge@fkie.**fraunhofer.de<[email-masked]>
> http://www.fkie.fraunhofer.de
>
>
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>
>

---

From: Joseph Macker <[email-masked]>
Date: Wed, 23 Jan 2013 16:51:32 -0500

I, for one, like the idea of considering and discussing how to properly
integrate concepts of schema-based compression.

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 00:58:45 +0100

Hi Henning,

I like the idea/plan and hope it can be in I-D in future, this input
to contribute to its discussions. If this schema is general for all, I
think we may need the schema to be flexible/extendable because may
have reasonable limitation (4 opt tlvs only), not sure, but
comments/questions inline,

> details of the address block.

This Schema number will be for All MANET Router Protocols using
RFC5444, not only for NHDP, am I correct,

All protocol message type in MANET will need to identify its mandatory
and optional TLVs to the 42 Schema, (the addresses block as you said
will be design in the Schema but later)

What was the example optional message TLV, not sure,

> Compression idea

So this Schema is limited to 4 known optionals and 4 uknown, do I make
sense, and could it itself be extendable,

What is the 1st optional message TLV value? I think not given

> out all fields that can be reconstructed from the Schema.

What are the fields that can be reconstructed by Schema 42, was is
described here or its pre-configured

> The complete message (without the address block and its TLVs has been

So I understand you input is for;The Schema part of TLV block compress-describe

> # 00 xx xx 12 34 80 10 01

So is that the validity time is mandatory and interval time is
optional, and both are known to schema 42?

As it was mentioned before in AODVv2 discussions the tradeoffs [1] of
positional and non-positional. It makes the description of
non-positional format message but in a positional format message by
schema way this will help for reduce processing which I like that :)

Thanks, I think it is good idea, if I misunderstood please advise,

[1] http://www.ietf.org/mail-archive/web/manet/current/msg14756.html

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 01:03:59 +0100

As from AODVv2 discussions the tradeoffs of using RFC5444 messages in
positional way or/and non-positional (i.e unspecified) way.

Therefore, This Schema you proposed makes the description of
non-positional format message but in a positional format message by
schema way this will help for reduce processing and lifetime,

 do you agree please advise,

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 01:07:43 +0100

sorry not reduce lifetime;

> schema way this will help for reduce processing and lifetime,

this schema way will help for reduce processing and increase lifetime
for constraint devices,

AB

---

From: "Stan Ratliff (sratliff)" <[email-masked]>
Date: Thu, 24 Jan 2013 03:21:52 +0000

+1

Stan

On Jan 23, 2013, at 4:51 PM, Joseph Macker wrote:

I, for one, like the idea of considering and discussing how to properly integrate concepts of schema-based compression.

On Wed, Jan 23, 2013 at 4:42 PM, Joseph Macker <[email-masked]<mailto:[email-masked]>> wrote:

On Wed, Jan 23, 2013 at 7:03 AM, Henning Rogge <[email-masked]<mailto:[email-masked]>> wrote:
On 01/23/2013 12:57 PM, Abdussalam Baryun wrote:
Ok so this schema can be used for all MANET protocols that use 5444
including OSRv2, am I right, please advise,

Yes, that is the plan.

I think it might allow us to focus on clean protocols during the design while being able to get more compact byte encoding on deployment level.

Henning Rogge

--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961<tel:%2B49%20228%209435-961>,   Fax +49 228 9435 685<tel:%2B49%20228%209435%20685>
mailto:[email-masked]<mailto:[email-masked]> http://www.fkie.fraunhofer.de<http://www.fkie.fraunhofer.de/>

_______________________________________________
manet mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/manet

_______________________________________________
manet mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/manet

---

From: Henning Rogge <[email-masked]>
Date: Thu, 24 Jan 2013 08:55:23 +0100

> comments/questions inline,

It already does support more than 4 optional TLVs.

> RFC5444, not only for NHDP, am I correct,

This number is a locally (at the deployment level) assigned number which 
defines one of the schemas used in the deployment. Making the schema 
number independent from the message type allows for multiple schema for 
a single message type. One IPv4 schema and one IPv6 schema for example, 
or maybe a new schema to get a smooth upgrade path from an older one.

> and optional TLVs to the 42 Schema,

No.

You only should to put in the TLVs your local deployment really USE. If 
you do not use MPRs, you should not add the TLV to the schema.

 > (the addresses block as you said

I will send a full example including address block later today.

> What was the example optional message TLV, not sure,

I would suggest reading RFC 5497 (TimeTLV) and RFC6130 (NHDP):

http://tools.ietf.org/html/rfc5497#section-9.2
http://tools.ietf.org/html/rfc6130#section-18.4

> sense, and could it itself be extendable,

No, it does not... its just padded with enough 0 bits to a smooth number 
of bytes.

In this case its only one byte, because you need zero bits to encode the 
number of Type-1 TLVs (because there is ALWAYS exactly one) and one bit 
to encode the number of Type-0 TLVs.

I will see that it becomes more clear in the full example.

> described here or its pre-configured

Maybe you should read the schema description again and then look into 
RFC5444 to see which fields you can take from the schema.

>> # 01 (value of INTERVAL-TIME TLV)

Here are the TLV values (one for the mandatory TLV, one for the optional 
one) you were looking for.

Yes.

The idea behind the "optional TLVs" is that you can encode them very 
efficiently because they are mentioned in the schema.

Henning Rogge

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 12:06:32 +0100

Thanks Henning for answers, some more discussion in line;

> or maybe a new schema to get a smooth upgrade path from an older one.

Yes I agree, but also the one schema can be used for different
protocols' messages, this is what I understood from your plan, did I
understand the plan?
> you do not use MPRs, you should not add the TLV to the schema.

You mentioned the plan is for all prtocols in MANET, not sure why the
condition now,

80  (Byte) = (1000) (0000) bitfield

does that make sense, I may be misunderstood!

> No, it does not... its just padded with enough 0 bits to a smooth number

You mentioned bitfield with one bit for each Opt-Msg-TLV, then you
mention to add another *bit* (i.e.  I think you meant another fieldbit
not bit, am I right) for unknown/non-present. I understood that each
field is 4 bits. (please note I feel it maybe a stupid question but
need to understand)

> I will see that it becomes more clear in the full example.

Thanks

> efficiently because they are mentioned in the schema.

I agree

AB

---

From: Henning Rogge <[email-masked]>
Date: Thu, 24 Jan 2013 12:32:21 +0100

On 01/24/2013 12:06 PM, Abdussalam Baryun wrote:
>> This number is a locally (at the deployment level) assigned number
>> which defines one of the schemas used in the deployment. Making the
>> schema number independent from the message type allows for multiple
>> schema for a single message type. One IPv4 schema and one IPv6
>> schema for example, or maybe a new schema to get a smooth upgrade
>> path from an older one.
>

Unlikely... because different protocol messages have very different content.

You will most likely specify several schema with different IDs, (at
least) one for each RFC5444 message in use.

>> You only should to put in the TLVs your local deployment really
>> USE. If you do not use MPRs, you should not add the TLV to the
>> schema.
>>
>
> You mentioned the plan is for all prtocols in MANET, not sure why
> the condition now,

The more "optional" and "variable" things you have in your schema, the
less specific it is and the larger the compressed messages will become.

>>>> Add a bitfield with one bit for each Optional Message TLV. Add
>>>> another bit if TLVs follow that are not present in the Schema.
>>>>

0x80 (byte) = (1) (0) (padding=000000)

You need one bit to encode the presence/absence of a TLV that can be 
present only once (or not at all).

You don't need any bit at all to encode the presence of a mandatory TLV 
that can be present only once.

The final "0" bit says "no uncompressed TLVs are following".

So the example use 2 bits of the byte, the rest is padding.

>>> So this Schema is limited to 4 known optionals and 4 uknown, do I
>>> make sense, and could it itself be extendable,
>>
>> No, it does not... its just padded with enough 0 bits to a smooth
>> number of bytes.
>
> mention to add another *bit* (i.e.  I think you meant another
> fieldbit not bit, am I right) for unknown/non-present. I understood
> that each field is 4 bits. (please note I feel it maybe a stupid
> question but need to understand)

It could happen that the message contains a TLV that is not mentioned in
the Schema at all. The last bit activates some kind of "add a real
uncompressed TLV block" feature at the end.

Henning Rogge

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 13:37:04 +0100

Thanks Henning, now I understand this, waiting for your next examples ;)

All the best

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 24 Jan 2013 19:23:04 +0100

> # 00 xx xx 12 34 80 10 01

So it will be:

 # 42 xx xx 12 34 80 10 01

As from the other thread below;
http://www.ietf.org/mail-archive/web/manet/current/msg14840.html

AB

---

From: Henning Rogge <[email-masked]>
Date: Fri, 25 Jan 2013 08:58:24 +0100

>   # 42 xx xx 12 34 80 10 01

Yes, the "00" was a leftover from V1.

Henning Rogge