Subject: [rohc] (deflate) fixed huffman vs. dynamic huffman

From: Cristian CONSTANTIN <[email-masked]>
Date: Thu, 11 Aug 2005 12:45:27 +0200

hi!

first of all a question I had in mind for a long time; are the udvm
impl. of decomp. algorithms (deflate, lz, etc) published in the 
draft-ietf-rohc-sigcomp-user-guide-02.txt intended for real world usage?

now, why using fixed huffman codes and not dynamic ones?
for example, compressing a real sip packet with both static and
dynamic codes leads to:

uncompressed size: 1111 bytes
static huffman codes: 762 bytes (68% of the original)
dynamic huffman codes: 636 bytes (57% of the original)

so, the one compressed with dynamic huffman codes is sensible smaller;
is the dynamic codes one not used bec. it would be more intensive cpu-wise?
by the way, what would be an acceptable cpu time spent for decompressing an
sip compressed packet using an udvm decompresor? (ms, hundreds of us,
tenths of us?)

bye now!
cristian
-- 
 _          | There are many people who use UNIX or Linux  
(_'_        | who IMHO do not understand UNIX.
  (_'rist   |              --David Korn  
GPG public key at wwwkeys.de.pgp.net
_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: "Finking, Robert" <[email-masked]>
Date: Fri, 12 Aug 2005 09:06:20 +0100

Regardless of processing time, surely the main point is what do you
gain? (Mark's first point)

To use dynamic huffman tables, you need to transmit them across the link
- how often are you going to have to update your dynamic tables to
continue to gain a benefit over static ones? The danger is you actually
end up making bandwidth utilisation worse if your huff tables are fairly
skewed to a particular dataset, which changes characteristics over the
retransmit interval. To mitigate against this you need to retransmit
often - maybe every message, which means you lose a lot of the benefit
of having dynamic tables, whilst increasing the system complexity a
great deal.

The figures originally quoted were for a real sip packet, but to be sure
that the extra cost in complexity is worth it you need to do analysis on
large amounts of data.

No doubt it is possible to squeeze a bit more out here, but the engineer
in me is saying "good enough".

Regards

Raffles

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Adam Roach
Sent: Thursday, August 11, 2005 5:17 PM
To: Cristian CONSTANTIN
Cc: West, Mark; [email-masked]
Subject: Re: [rohc] (deflate) fixed huffman vs. dynamic huffman

Cristian CONSTANTIN wrote:

>
>>In terms of acceptable CPU time, this is highly dependent upon 
>>circumstances.  However, the simple answer is always, 'as fast as 
>>possible'!  Since SigComp is there to reduce latency, saving a few 
>>10's of ms in serialisation delay by adding 100's of ms of processing 
>>is a bad bargain.  I'd expect decompression times to be well under 1ms

>>on a desktop PC...
>>    
>>
>
>cristian: thanks, but does anyone have some real life data here?
>  
>

A lot of the answer to this question depends on the platform you're on. 
(For example, my profiling showed that about 20% of the processing time 
used by my SigComp stack was performing SHA-1 hashing; on a Sparc 
processor, this jumps to nearly 30% -- hardly surprising, since the 
Sparc lacks rotate instructions).

In any case, on a low-speed ARM processor (something in the range of 10 
to 20 MHz), using Deflate on approximately 1000 byte messages, I was 
seeing decompression times on the order of 200 ms. On a server, yes, 
this ended up being something more in the hundreds-of-microseconds 
range; we weren't as concerned about characterizing that side of the 
connection, so that number didn't stick with me.

(To address Mark's comment, this 200 ms processing on the terminal plus 
the negligible compression latency introduced on the network server was 
saving us about 900 ms of radio latency, so the trade-off was pretty 
obvious).

/a