Subject: [manet] RFC5444 schema-based compression V3

From: Henning Rogge <[email-masked]>
Date: Mon, 28 Jan 2013 11:37:46 +0100

Hi,

I made ome small revisions all over the place in the document.

I think its getting to the point to start an I-D. Just the packet-level 
TLV-block compression and some ideas for address compression are still 
missing.

And we have to decide how to transport the compressed data over the network!

Henning Rogge

-----------------------

RFC5444 Schema Compression V3
=============================

Changes since V2:
- explicit "any" placeholder in schema
- usage of RFC6256
- quantity of address-tlvs "per address"
- added missing message header flag octet in uncompressed example
- more explanation of example compression
- layout cleanup

Changes since V1:
- restructured text to make it easier to read
- added compression for address-TLVs
- simplified Schema description
   (no more differentiation between mandatory and optional TLVs)
- added explanation for TLVs schema fields

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

Describe the typical content of a RFC5444 message in your deployment 
with a Schema.

Remove everything from the RFC5444 message that can be constructed from 
Schema. Use bitfields to describe how many TLVs of each kind are present 
in a TLV-block and their data.

Use RFC6256 to encode compressable numbers larger than 255.

Schema content
--------------

Schema field values can a list of possible values (the list can contain 
a single value) or an interval of numbers. Schema fields can be empty 
when the field is not restricted by the Schema in any ways and has 
always to be fully transmitted over the network.

Fields for Message Header:
- each of the fields of the Message Headers schema describes one of the 
possible fields described in RFC5444 chapter 5.2

Fields for TLVs:
- "quantity" limits the number of times a TLV can be present in a 
TLV-block. The VALIDITY_TIME TLV is mandatory for all NHDP messages and 
can only be present once, so its quantity is "1". The INTERVAL_TIME TLV 
is optional for NHDP messages, but must not be there more than once, so 
its quantity is "0-1". Quantity for address TLVs is PER ADDRESS!
- "extension type" sets the extension type of the TLV if known.
- "value length" restricts the length of the TLVs value in octets (to a 
range or a fixed length).
- "value" restricts the value itself of the TLV.

Example schema
--------------

Schema Number:        42

Message Header:
* Type:               0
* MHasOrig:           0
* MHasHopLimit:       1
* MHasHopCount:       0
* MHasSeqnum:         1
* Address Length:     4
* Originator Address: *
* Hop Limit:          1
* Hop Count:          *
* Sequence Number:    *

Message TLVs:
* TLV type 0: (INTERVAL_TIME)
+-- quantity:         0-1
+-- extension type:   0
+-- value length:     1
+-- value:            *
|
* TLV type 1 (VALIDITY_TIME)
+-- quantity:         1
+-- extension type:   0
+-- value length:     1
+-- value:            *

Addresses Block TLVs:
* TLV type 2 (LOCAL_IF)
+-- quantity:         0-1
+-- extension type:   0
+-- value length:     1
+-- value:            0-1
|
* TLV type 3 (LINK_STATUS)
+-- quantity:         0-1
+-- extension type:   0
+-- value length:     1
+-- value:            0-2
|
+ TLV type 4 (OTHER_NEIGHBOR)
+-- quantity:         0-1
+-- extension type:   0
+-- value length:     1
+-- value:            0-1

Example message for compression
-------------------------------

The message to be compressed in this example is a NHDP message:
- 4-byte addresses,
- hoplimit 1,
- sequence number 0x1234

- an INTERVAL_TIME Message-TLV with value 0x02
- a VALDIITY_TIME Message-TLV with value 0x20

- an address block with the IP's 10.0.0.1, 10.0.0.2 and 10.0.0.3
- 3-byte head (10.0.0), no prefixes
- one LOCAL_IF TLV for index 0 and value 0x00
- one LINK_STATUS_TLV for indices 1-2 and the values 0x01/0x02
- one OTHER_NEIGHBOR TLV for indices 1-2 and the values 0x01/0x00

Example compression
-------------------

# The message always starts with the schema number (compressed with 
RFC6256).
42

# Add compressed msg-size to message (also compressed with RFC6256).
17

# Skip the msg-flags AND msg-addr-length field if specified in the 
schema, otherwise add them to the message.
(none in this example)

# Add all optional message header fields (Originator, Hoplimit, 
Hopcount, Sequence Number) that are marked in the flags and are not 
already defined in the schema.
12 34 (sequence number value)

# Add a bitfield with as many bits for each TLV as needed to encode the 
quantity of it (no bit necessary for one fixed quantity, one bit for 
0-1, ...). Append another bit that encodes if 'other TLVs' will follow 
the compressed ones. Append zeros to padd to a full octet.
# If the quantity of a TLV is unrestricted, use RFC6256 to encode the 
quantity.
# The order of the TLVs is the same as defined in the schema.
# In this example INTERVAL_TIME can be present 0-1 times and 
VALIDITY_TIME is always present once.

# binary: (1*INTERVAL_TIME, no "other TLVs")
# (1*VALDIITY_TIME is implicitly defined by the schema)
1 0

# in bytes:
80

# Add all present TLVs to the compressed message. Leave out all fields 
that can be reconstructed from the Schema. Shorten each TLVs remaining 
fields (except tlv-flags) into bitfield as long as the possible 
combinations need. Only compress value if can be expressed in less than 
8 bits (padd with zero-bits before the value if not).

# value of INTERVAL-TIME TLV
02

# value of VALIDITY-TIME TLV
20

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

(none in this example)

# Add the uncompressed address-block to the message.
03 80 03 10 00 00 01 02 03

# Add a bitfield with as many bits for each TLV as needed to encode the 
quantity of it (no bit necessary for one fixed quantity, one bit for 
0-1, ...). Append another bit that encodes if 'other TLVs' will follow 
the compressed ones. Add zeros to padd to a full octet.
# The number of addresses multiplied by the quantity defined in the 
schema determines the possible quantities of address TLVs.
# If the quantity of a TLV is unrestricted, use RFC6256 to encode the 
quantity.
# The order of the TLVs is the same as defined in the schema.
# In this example all TLVs can be present 0-3 times, which means two 
bits are needed to encode the quantity of each compressed address TLV

# binary: (1*LOCAL_IF, 1*LINK_STATUS, 1*OTHER_NEIGHBOR, no other TLVs)
01 01 01 0

# in bytes:
54

# Add all present TLVs to the compressed message. Leave out all fields 
that can be reconstructed from the Schema. Shorten each TLVs remaining 
fields (except tlv-flags) into bitfield as long as the possible 
combinations need. Only compress value if can be expressed in less than 
8 bits (padd with zero-bits before the value if not).

# binary: LOCAL_IF flags, index-start and value
01010000 00 0

# binary: LINK_STATUS flags, index-start, index-end and two values
00110100 01 10 01 10

# binary: OTHER_NEIGHBOR flags, index-start, index-end and two values
00110100 01 10 1 0

# in bytes:
50 00
34 66
34 68

# If there are other TLVs (not described in the schema), add the number 
of bytes needed to describe them (RFC6256 encoded) and the TLVs itself 
(uncompressed).
(none in this example)

Result
------

The complete message has been reduced from

00 53 00 30 53 01 12 34 (message header)
00 08 (message-tlv block length)
00 10 01 02 (INTERVAL-TIME 0x01)
01 10 01 20 (VALIDITY-TIME 0x10)
03 80 03 10 00 00 01 02 03 (3 Addresses, 10.0.0.1,.2 and .3, no prefixes)
00 13 (address-tlv block length)
02 50 01 01 00 (LOCAL_IF index=1 0x00)
03 34 02 03 01 01 02 (LINK_STATUS index=2-3 0x01/0x02)
04 34 02 03 01 01 00 (OTHER_NEIGHBOR index=2-3 0x01/0x00)

(a total of 48 bytes)

to

42 17 12 34  (message header)
80 02 20 (message tlvs)
03 80 03 10 00 00 01 02 03 (address block)
54 50 00 34 66 34 68 (address tlvs)

(a total of 23 bytes)

Comments
--------

A packet-level schema entry should be added to this concept.

I think there could be some more compression if the Schema includes a 
"known prefix" for all addresses (or maybe a list of them?). This would 
help to compress both the originator address and the prefix fields in 
address blocks.

In theory there are a few wasted bits here and there, but I decided NOT 
to do any bit-shifting on data which is larger than 1 byte.

A great addition to this idea would be a protocol for requesting unknown 
schema from your neighbor. And a program that scans a RFC5444 stream and 
suggests a schema based on the watched messages.

-- 
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: Mon, 28 Jan 2013 11:49:15 +0100

+1

AB