[Olsr-dev] Compressing OLSRd messages

[Henning Rogge]

Just some more thoughts on this.

Am Sonntag 17 April 2011, 20:59:58 schrieb Amadeus:
> For example: Let's assume we have to encode the following IPs for our
> package:
> 
> 10.8.40.1, 10.8.40.2, 10.8.40.3, 10.8.40.4, 10.8.40.5, 10.8.40.7,
> 10.8.40.20, 10.8.40.23, 10.8.6.5, 10.8.40.6, 10.8.128.80, 10.8.129.97
> 
> As you can easily see there's a lot of packets strting with the prefix
> 10.8. But to simplify our example we assume our splitting is done on
> byte level. That way we get:
> 
> 10 (8 (6 (5, 6), 40 (1, 2, 3, 4, 5, 7, 20, 23), 128 (80), 129 (97) ) )
> 
> In order to be able to properly parse those 18 nodes of the tree when
> trying to read the packet we have to add the number of direct children
> for each node. In our case we simply get:
> 
> 1 10 1 8 4 6 2 5 6 40 8 1 2 3 4 5 7 20 23 128 1 80 129 1 97
Did you have looked for a good encoding for a Patricia Tree?
(Patricia-Trees can have multiple characters at each node, so we would not 
need the '1 child' in between nodes, just a length field). Maybe there is some 
clever trick to get trees like this down to a compact byte sequence.

> Since there's only up to 256 possible values for the number of direct
> childs we can store the cound of childs with one byte each. This results
> in only about 25 bytes instead of 48 bytes for the 12 IPv4 addresses we
> stored in this tree. In case of IPv6 the savings should be even bigger
> given the much larger addresses there. Typically the coding of the tree
> is smaller than the uncompressed list starting from the third entry you
> add. But even if the tree is slightly larger than the uncompressed list:
> Since you usually repeat addresses in the OLSR packet you get to save on
> bandwidth there.
Maybe there is a good way to add tree based compression as an additional 
option to the already present prefix/postfix compression in the packetbb 
address blocks.

Henning Rogge

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20110419/0d1b55a3/attachment.sig>