Subject: [Sip] RE: Encapsulating EPIC in UDPComp

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 22 Aug 2001 00:57:02 -0400

> -----Original Message-----
> From: Price, Richard [mailto:[email-masked]]
> Sent: Friday, August 17, 2001 11:58 AM
> To: [email-masked]'; [email-masked]'
> Cc: 'Jonathan Rosenberg'
> Subject: Encapsulating EPIC in UDPComp
> 
> 
> Hi,
> 
> Attached is a (rather detailed) posting on the overhead of
> encapsulating EPIC within UDPComp. The conclusion is that by adding
> Huffman codes to UDPComp, the protocol overhead can be made very
> low (just 5 bytes per message).
> 
> Comments are welcome!

Richard is exactly correct that the cost of a general purpose decompressor
like this is a hit in overhead. With purely static codebook indices, the
overhead is quite large as the results below show. I agree totally that some
kind of Huffman coding is needed. I have been thinking about this, and I
have a proposal that is different from what Richard is proposing.

My proposal would be to make the support for huffman coding very general
purpose, and based on a tree-like structure where the codes are dependent on
previous elements. Such a hierarchical structure is needed, I think, to
support the TCCB and EPIC algorithms. TCCB is really about a two level
encoding scheme - the top level are the names of headers, and the second
level are their values. They add some optimizations that are SIP specific
(such as sending nothing when it can be assumed that the header hasn't
changed), which I would rather generalize in some efficient way. 

So, the idea is that when you write into the codebook, you provide a bit
which says whether this write takes place at the current "level" in the
hierarchy, or back at the top. Then, you provide a bitstring that represents
the huffman code for the token, followed by the token. It is the
responsibility of the encoder to make sure that each code is a valid prefix
code. When the encoder sends a read command, it contains a bit which
indicates whether the read is from the top of the tree or the current
position, followed by the code. 

So, lets take a simple example. We want to compress something like:

A: foo
B: bar
A: baz

which is a sort-of sip message thing. We will use a TCCB-like approach,
where we encode the headers and values separately. Assume two bits for the
message type (READ or WRITE), and 8 bits per character. We can do better
using a separate codebook for text, as Richard has proposed.

for the first message, we send:

WRITE, top=TRUE, "A:" code="0"      (2 + 1 + 16 + 1 = 20 bits)
WRITE, top=FALSE, "foo" code="01"   (2 + 1 + 24 + 2 = 29 bits)
WRITE, top=TRUE, "B:" code="11"     (2 + 1 + 16 + 2 = 21 bits)
WRITE, top=FALSE, "bar" code="01"   (2 + 1 + 24 + 2 = 29 bits)
READ, top=TRUE, code=0              (2 + 1 + 1 = 4 bits)
WRITE, top=FALSE, "baz" code="11"   (2 + 1 + 24 + 2 = 29 bits)

TOTAL:                                                132 bits = 16.5 Bytes

This is larger than the original (15 bytes), typical for the case where
there is no static or user specific codebook.

This results in a codebook in the compressor/decompressor that looks like:

   0 "A:"      11 "B:"
   |            |
 -----------   01 "bar"
 |         |
01 "foo"   11 "baz"

Now, if the next message is:

A: foo
B: bar
A: blip

Its compressed as:

READ, top=TRUE, code=0            (2 + 1 + 1 = 4 bits)
READ, top=FALSE, code=01          (2 + 1 + 2 = 5 bits)
READ, top=TRUE, code=11           (2 + 1 + 2 = 5 bits)
READ, top=FALSE, code=01          (2 + 1 + 2 = 5 bits)
READ, top=TRUE, code=0            (2 + 1 + 1 = 4 bits)
WRITE, top=FALSE, "blip" code=001  (2 + 1 + 32 + 3 = 38 bits)
 
                                   Total: 61 bits, 7.625 bytes

Now, this is better, achieving slightly better than 2:1 over a very small
piece of data.

An interesting improvement is that I can specify a command which says "READ
code XX, and then read the next N symbols in the tree if the number of
children at each node is 1, in which case you have no choice about the next
symbol anyway". This is useful for trees that are really deep, as opposed to
wide. If you think about it, this covers LZSS, which can be viewed as a
"hierarchical" codebook where each node is a single character, and the tree
is one where each node has only one child, the next character.

Comments? Hopefully this makes some sense...

-Jonathan R.

---
Jonathan D. Rosenberg, Ph.D.                72 Eagle Rock Ave.
Chief Scientist                             First Floor
dynamicsoft                                 East Hanover, NJ 07936
[email-masked]                     FAX:   (973) 952-5050
http://www.jdrosen.net                      PHONE: (973) 952-5000
http://www.dynamicsoft.com

_______________________________________________
Sip mailing list  http://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Jan Christoffersson <[email-masked]>
Date: Wed, 22 Aug 2001 16:11:43 +0200

Hi Jonathan,
It seems to me that the Huffman coding you describe would be much more efficient
than using the tokens which are given in the UDPComp-draft.
However, I don't quite understand how they can be used for Lempel-Ziv
compression. What puzzles me is that the dictionary, from the Lempel-Ziv point
of view, is considered to be a byte array. This means that the same character
can be present in many of the array elements. In the Huffman tree on the other
hand, each character (or string) appears only once, right? But if you want to be
able to read a string from the dictionary using the command ''READ code XX, and
then read the next N symbols in the tree'', this implies that there must be a
possibility for each symbol to appear more than once. But then again, can this
be so in a Huffman tree?
Can someone help me out here? I think I'm missing something.
Regards,
Jan Christoffersson

Jonathan Rosenberg wrote:

> Mailing list for Robust Header Compression WG
> Archive: http://www.cdt.luth.se/rohc/