Subject: RE: [Sip] Encapsulating EPIC in UDPComp

From: [email-masked]
Date: Fri, 17 Aug 2001 17:47:13 -0500

> For comparison, the compression ratio using only the existing UDPComp
> tokens is given below:
> 
> EPIC algorithm with no encapsulation:                   9.78
> 
> UDPComp using existing tokens only:                     1.17

Richard,

I'm a bit puzzled by the numbers. According to your own data sent
earlier (http://www.cdt.luth.se/robhc/msg02428.html), even a
generic LZSS can achieve a compression ratio of 9.87 with a combined
dictionary. What is the point here?

BR,
Zhigang

_______________________________________________
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: "Price, Richard" <[email-masked]>
Date: Mon, 20 Aug 2001 11:20:37 +0100

Hi,

The discrepancy is because the second set of compression ratios does
not include a user-specific dictionary. In this case, the compression
ratio for the EPIC algorithm with no protocol overhead is 9.78 (vs
15.53 including a user-specific dictionary).

The purpose of the second set of compression ratios is to check the
protocol overhead of UDPComp. This may be quite substantial because
UDPComp employs a standard decompressor, not specifically optimized
for any one particular compression algorithm.

At present the decompressor doesn't even understand Huffman encoding,
so an explicit 1-2 byte index has to be sent for each text string
instead. This reduces the compression ratio as follows:

No encapsulation at all:                              9.78

UDPComp encapsulation:                                1.17

Fortunately it is pretty easy to add Huffman encoding to UDPComp, and
the protocol overhead is reduced substantially. For the most powerful
variant of Huffman compression the overhead is as follows:

UDPComp encapsulation with Huffman encoding:          8.24

This is a much lower overhead (5 bytes per compressed message).

Regards,

Richard P

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Friday, August 17, 2001 11:47 PM
> To: Price, Richard; [email-masked]; [email-masked]
> Cc: [email-masked]
> Subject: RE: [Sip] Encapsulating EPIC in UDPComp
> 
>

---

From: "Liu Zhigang.C (NRC/Dallas)" <[email-masked]>
Date: Mon, 20 Aug 2001 11:11:39 -0500

Still, the numbers indicate that with a combined dictionary (including
user-specific) can easily boost the compression ratio to close to 10,
even for the generic approach like LZSS (I would assume LZW will
have similar result). Then, shouldn't we assume a combined dictionary 
in all comparisons?

BR,
Zhigang

> From: ext Price, Richard [mailto:[email-masked]]
> Sent: August 20, 2001 5:21 AM
> To: Liu Zhigang.C (NRC/Dallas); [email-masked]; [email-masked]

---

From: "Price, Richard" <[email-masked]>
Date: Tue, 21 Aug 2001 10:21:30 +0100

Hi,

Good point about the unidirectional nature of UDPComp. Since there is
currently no shared information between the two flow directions, the
dynamic dictionary takes longer to populate. I have rerun the
simulations using the unidirectional flows only - results are below with
the results for a shared dynamic dictionary given for comparison:

                                Unidirectional flows      Shared flows

No encapsulation at all:                6.72                  9.78

UDPComp encapsulation:                  0.80                  1.17

UDPComp with Huffman (type A):          4.04                  5.90

UDPComp with Huffman (type B):          4.41                  6.29

UDPComp with Huffman (type C):          4.65                  6.85

UDPComp with Huffman (type D):          5.96                  8.24

Concerning the choice of tokens to provide in UDPComp, we have one set
of results using the existing UDPComp tokens only, as well as 4 sets of
results using tokens generated by different variants of Huffman encoding. 
For an explanation of the 4 types of Huffman encoding please see my
original email below.

Note that the Huffman tokens replace the original READ token as they
basically have the same function, and providing both types simultaneously
would be inefficient.

Regards,

Richard P

> From: Jan Christoffersson [mailto:[email-masked]]
> Sent: Monday, August 20, 2001 2:32 PM
> To: Price, Richard
> Cc: [email-masked]'; [email-masked]'; 'Jonathan Rosenberg'
> Subject: Re: [rohc] Encapsulating EPIC in UDPComp
> 
> 
> Hi Richard,
> I have a few comments to the performance figures when EPIC 
> (or some other
> compression algorithm) is encapsulated in UDPComp. As defined 
> in the draft
> UDPComp is unidirectional. This means that all messages from 
> the "Simple SIP
> to SIP" flow from <draft-ietf-sip-call-flows-05.txt> can't be 
> used in the
> dynamic dictionary, only previous messages sent in the same 
> direction as the
> current message. This would have significant impact on the performance
> figures,  I believe.
> Another thing which I think will have impact on the 
> performance is the choice
> of tokens. For example, the READ-token has nothing to do with 
> dictionary/code
> book management, it just says ''read from a certain place in 
> the dictionary
> and append this to the decompressed message''. But this is 
> typically what the
> references in  Lempel-Ziv compression algorithms mean. In 
> practice this means
> that we are using two tokens with the same meaning to read a 
> string from the
> dictionary, surely one token would be sufficient? I guess the 
> there is room
> for plenty of discussion on what types of tokens are needed 
> to support both
> the different compression algorithms that people would like 
> to use and maybe
> also to support the kind of dictionary/code book 
> manipulations that are
> desired.
> 
> Regards,
> Jan Christoffersson
> 
> "Price, Richard" wrote:
> 
> > 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 P
> >
> > --------------------------------------------------------------------
> >
> > This is a follow-up to my earlier posting on the performance of
> > various signaling compression algorithms. I mentioned that 
> one of the
> > ideas of UDPComp is to make the compression algorithm a local
> > implementation decision at the compressor: this makes the protocol
> > very lightweight and flexible, but potentially reduces the 
> compression
> > efficiency due to transmitting the semantics of the compression
> > algorithm in each packet.
> >
> > As promised, here are some performance figures to illustrate this
> > overhead. We tested the EPIC algorithm encapsulated in UDPComp using
> > the "Simple SIP to SIP" flow from 
> <draft-ietf-sip-call-flows-05.txt>.
> >
> > We assume that the compressor and decompressor each contain a static
> > dictionary of text strings commonly used in SIP. This can 
> be "learnt"
> > by compressing sufficient SIP messages, or alternatively 
> can be fixed
> > a-priori. We also use a dynamic dictionary (i.e. compress 
> relative to
> > previous messages in the flow).
> >
> > Note that UDPComp offers significant flexibility in the choice of
> > "token" used to transmit text strings from the compressor to the
> > decompressor. Currently the scheme sends a fixed 1-2 byte index to
> > reference each text string, but additional tokens can 
> easily be added
> > (for example tokens that use Huffman codes to reference 
> text strings).
> > We have provided a range of performance figures using 
> different types
> > of token to transmit the data.
> >
> > The decrease in compression ratio is caused by sending a 
> 1-2 byte index
> > to reference each text string. In contrast, the EPIC 
> algorithm usually
> > references a text string by sending a short Huffman code (typically
> > 1 - 4 bits).
> >
> > To improve the compression ratio it is possible to add 
> Huffman codes to
> > UDPComp. In general this is straightforward: the only 
> potential problem
> > is that the Huffman codes are chosen specifically for EPIC, 
> and different
> > variants of Lempel-Ziv may need a different set of Huffman 
> codes. Thus,
> > it may be necessary to download new sets of Huffman codes to the
> > decompressor depending on the choice of algorithm.
> >
> > Adding Huffman codes to UDPComp can be done in several ways. Firstly
> > we have a choice between EPIC-LITE (which uses ordinary 
> Huffman codes)
> > and EPIC (which uses a special version of Huffman encoding 
> capable of
> > compressing text strings down to less than one bit - for example 3
> > common text strings in a row might together be indicated by 
> sending a
> > single "0" bit).
> >
> > Secondly, we have a choice between selecting a global set of Huffman
> > codes for all text strings, and using a different set for 
> each dictionary
> > entry. In the latter case the Huffman code for each text 
> string actually
> > changes depending on the previously received string. This 
> improves the
> > compression ratio at a cost of higher memory requirements 
> (which may be
> > a problem if we have to store the Huffman codes in working memory).
> >
> > Compression ratios for each choice are given below:
> >
> > UDPComp using EPIC-LITE with global Huffman codes:      5.90
> >
> > UDPComp using EPIC-LITE with local Huffman codes:       6.29
> >
> > UDPComp using EPIC with global Huffman codes:           6.85
> >
> > UDPComp using EPIC with local Huffman codes:            8.24
> >
> > Initial results are promising: if required we can make the 
> overhead of
> > encapsulating EPIC within UDPComp negligible (essentially it is just
> > the 5 bytes of initial UDPComp header per message). I 
> believe the next
> > step should be to check how other compression algorithms 
> fit into the
> > UDPComp framework, and to decide on a "sweet spot" between 
> compression
> > efficiency and standardizing the protocol in the given timeframe.
> >
> >   
> --------------------------------------------------------------
> ----------
> >                           Name: RMRL-Disclaimer.txt
> >    RMRL-Disclaimer.txt    Type: Plain Text (text/plain)
> >                       Encoding: 7bit
>

---

From: "Price, Richard" <[email-masked]>
Date: Tue, 21 Aug 2001 10:41:26 +0100

Hi,

Does UDPComp currently have the ability to support a user-specific
dictionary? If no additional effort is required then we should certainly
assume a combined dictionary in all comparisons.

If UDPComp needs to be modified then we should compare results with and
without a user-specific dictionary - if the gain in compression efficiency
is big enough then we can make the necessary modifications to UDPComp.

Regards,

Richard P

> From: Liu Zhigang.C (NRC/Dallas) [mailto:[email-masked]]
> Sent: Monday, August 20, 2001 5:12 PM

---

From: "Liu Zhigang.C (NRC/Dallas)" <[email-masked]>
Date: Tue, 21 Aug 2001 12:02:41 -0500

> dictionary? If no additional effort is required then we 
> should certainly assume a combined dictionary in all comparisons.

To me, yes, the user-specific dictionary is just a matter 
of pre-population (of entries in codebook for LZW, or byte 
array for LZSS). The effort should be much less than 
that of adding Huffman Coding (especially if it is dynamic).
See more comments below.

> If UDPComp needs to be modified then we should compare 
> results with and without a user-specific dictionary - 
> if the gain in compression efficiency is big enough 
> then we can make the necessary modifications to UDPComp.

The results are already shown from various sources (you, Hans
and us). Quoting your number (from 1.17 to 9.87), I would say 
the gain is big. And more important, the associated complexity 
is almost trivial. We can simply use the existing WRITE to 
pre-populate the codebook, plus a flag indicating no message 
should be delivered to the upper layer. Furthermore, it is 
generic and no SIP knowledge is assumed. 

Should we apply the same standard on all approaches, including 
EPIC?

BR,
Zhigang

---

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

> 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,
> 

Yes, yes, yes! This is exactly the direction that I was arguing for at IETF.
The idea with UDPComp is that you define a very general purpose decoder,
define a protocol for conveying commands to the decoder, and then allow the
implementors to choose an encoding mechanism that utilizes the facilities
and capabilities of the decoder and protocol. THis is much like the way
compression is done for video and audio, where the decoder is really simple,
and the compression lies within the encoder.

What Richard is proposing here are some new capabilities to add to the
protocol/decoder (namely, support for Huffman codes). I think this is the
tact we should take - examination of capabilities to add in order to find
the right sweet spot between compression efficiency and flexibility. I think
that this will ultimately be much more fruitful than needless bantering
about whose proposal supports what capabilities, and the relative
performances under some two dozen call flows. That kind of approach will
mean we never finish in time for the 3g deliverables.

Now, I have some comments on how I would incorporate Huffman codes into
UDPComp, which are very detailed, and I will post separately. 

-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

---

From: "Price, Richard" <[email-masked]>
Date: Wed, 22 Aug 2001 13:27:10 +0100

Hi,

Wonderful! If we can standardize a decompressor with a hierarchical
dictionary then we can support all of the proposed algorithms
(EPIC, TCCB, Lempel-Ziv etc.).

The overhead of this scheme is pretty low (3 bits per Huffman code),
but I believe we can reduce it even further. Comments inline...

Regards,

Richard P

> From: Jonathan Rosenberg [mailto:[email-masked]]
> Sent: Wednesday, August 22, 2001 5:57 AM
> To: Price, Richard; [email-masked]'; [email-masked]'
> Cc: Jonathan Rosenberg
> Subject: RE: Encapsulating EPIC in UDPComp
>  
> 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.

On the contrary, your proposal is exactly how I hoped Huffman
coding would be introduced!

> 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.

Yes. In EPIC, the Huffman codes are local to each dictionary item.

> 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. 

EPIC is similar to TCCB, except that we use n levels of encoding
(where n is determined by the BNF description of SIP).

> 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.

I would propose to take this one step further, and make the Huffman
code indicate not only the location of the dictionary item, but also
the type of token (READ, WRITE etc.). We could do this as follows:

-   Keep all of the existing token types (READ, WRITE, WRITE-REFERENCE)
    but prefix them with a large bit pattern, say "11111111".

-   Reserve the remaining prefix codes ("00000000" to "11111110") for
    the Huffman codes.

-   When a token is sent explicitly, attach a "shorthand" Huffman code
    that can be used to send the token in future.

When we send the Huffman code, it implicitly specifies the token type
(READ, WRITE etc.) as well as the location of the item to be read or
written.

The advantage of this approach is that schemes like EPIC and Lempel-Ziv
only ever send Huffman codes when reading and writing entries in the
dictionary. Once UDPComp has successfully transmitted these Huffman codes
to the decompressor there is no need to send the tokens explicitly any
more. This makes the overhead of UDPComp negligible (in fact, the only
overhead is the reserved bit pattern "11111111" that we used to send
the tokens explicitly in the first place).

> 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.

Agreed. However we should make this indicator flag part of the Huffman
code as well, so that we don't have to send it explicitly every time.

> 
> 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.

Note that there is still a 3 bit overhead for each Huffman code,
due to transmitting 2 bits for the token type and 1 bit to
indicate when to go back to the top of the tree. If we make these
part of the Huffman code then we can eliminate even this overhead.

> 
> 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.
> 

A similar enhancement might be to allow 1 Huffman code to indicate
several consecutive choices of branches on the tree. This is
especially useful when there is a single very likely route through
the tree, as we can specify this route using only a single short
Huffman code.

> Comments? Hopefully this makes some sense...

It made perfect sense to me, which is probably a bad sign...

---

From: "Price, Richard" <[email-masked]>
Date: Wed, 22 Aug 2001 17:00:28 +0100

Hi,

I believe the term "tree structure" for the new UDPComp dictionary is
the source of the confusion - it's nothing to do with a "Huffman tree"
per se. In fact, each dictionary item in the tree has its own set of
codes (generated by Huffman or some other algorithm).

The reason for making the dictionary tree-like is so that we can
capture the hierarchical nature of SIP. For example a SIP message can
be divided up into headers, and each header can be further subdivided
into different values. For the "tree-based" dictionary we can change
the Huffman codes we send based on the exact part of the SIP message
we are currently compressing. However we can also support Lempel-Ziv
just by ignoring the tree structure and making the dictionary flat.

Hope this helps!

Richard P

> Sent: Wednesday, August 22, 2001 3:12 PM
> To: Jonathan Rosenberg
> Cc: Price, Richard; [email-masked]'; [email-masked]'
> Subject: Re: [rohc] RE: Encapsulating EPIC in UDPComp
> 
> 
> 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:
> 
> >
> >
> > 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.
> >
> 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
> 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.
> >
> > 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.
> >
> > This is larger than the original (15 bytes), typical for 
> the case where
> > there is no static or user specific codebook.
> >
> > 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
> > Mailing list for Robust Header Compression WG
> > Archive: http://www.cdt.luth.se/rohc/
>

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 22 Aug 2001 12:14:44 -0400

> Sent: Wednesday, August 22, 2001 10:12 AM
> To: Jonathan Rosenberg
> Cc: 'Price, Richard'; [email-masked]'; [email-masked]'

Yes. There is no reason to keep the fixed length tokens in that draft.

> hand, each character (or string) appears only once, right? 

No, thats not true. I think things are confused because there are really two
trees here. One is the tree that represents the Huffman code itself (since a
Huffman table can be represented as traversing a tree with bits at each
vertex). THe other is the tree of contexts, which basically tell you which
table is being used. Let me explain.

The Huffman codes effectively encode string values (Richard has proposed
they encode more than that, which I agree with, but thats an orthogonal
issue. Lets keep it simple for explanatory purposes). Each entry in the
table contains an arbitrary string, which is the string to be outputted as
part of the decompressed message. Consider a simple table:

Code     value
---------------------------------------
0          [email-masked]
10         INVITE
111        From:
1100       Via:

Call this "table 1". I can have many such tables, each of which contains a
Huffman code for a series of strings.

The idea is that you start compression/decompression with a "root table".
The output of the Huffman code not only specifies the string to output into
the decompressed message, but also basically specifies a pointer to the
"next table". So, really, if the above table were the root table, it should
really look like:

Code     value                           Next table
----------------------------------------------------
0          [email-masked]          table 2
10         INVITE                           table 3
111        From:                            table 4
1100       Via:                             table 5

Rather than explicitly specifying the next table by a table number, I do it
with a bit. A value of 0 indicates that you use the root table. A value of 1
means you use a table which is unique to the sequence of huffman codes that
have been traversed from the root till now. Thus, determination of which
table to use is effectively modeled as a tree as well:

      Please view in a fixed-width font such as Courier.

                                 start
                                   |
                                   |
                                   |
                       ..........................
                       .                        .
                       .                        .
                       .        Root table      .
                       .            /           .
                       ..........................
                        |        |      |       |
                       0|      10|   111|   1100|
                   .........  ....... .......  ..............
                   . Table .  .Table. .Table.  .  Table     .
                   . /0    .  ./10  . ./111 .  ./1100       .
                   .       .  .     . .     .  .            .
                   .........  ....... .......  ..............
                                                |        |
                                              1 |       0|
                                                |        |
                                                |        |
                                            ........   .......
                                            . Table.   .Table.
                                            ./1100/1   ./1100/0
                                            .      .   .     .
                                            ........   .......

So, we start at the root (table /). If the code transmitted is 1100, we
output the string "Via:" to the decompressed message, and then use the table
named /1100 (i.e., 1100 is like a subdirectory off the root). Now, lets
assume this table has two entries:

Code      String
----------------
0         SIP/2.0/UDP
1         SIP/2.0/TCP

The next thing sent by the compressor is "use the current table, and read
index 0". This outputs SIP/2.0/UDP to the decompressed message, and sets the
table to /1100/0. The process continues. 

Now, what is interesting is when you have Huffman tables with only one
entry. Consider table /1100/1. Lets say its like this:

Code     String
----------------
00       CRLF CSeq:

So, lets say we started from the root, and the encoder sent 1100, which
resulted in outputing "Via:". Then, it sends a command which means "output
the string at index 1 of the current table. Then, if the next table has only
one entry, output that, and then if the next has one entry, output that, and
so on, until you come to a table with more than one entry". So, the
decompressor reads entry 1 from table /1100, and outputs "SIP/2.0/TCP". The
next table, /1100/1 has only one entry, so that is output as well, resulting
in "CRLF CSeq:" being written into the decompressed message. This is very,
very useful as a primitive, since it totally reduces the overhead to zero.
If you extend this command a little bit, and allow the encoder to say
"output the next N things assuming there is only one entry in each table",
you can implement LZSS at the encoder with this primitive command, without
the decoder even having to know what LZSS stands for, or how it works. You
do need an efficient way to tell the encoder to construct a series of tables
in sequence, though. Doing that is easy as well.

Hope that clarifies. 

Thanks,
Jonathan R.
---

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 22 Aug 2001 12:18:40 -0400

> Sent: Wednesday, August 22, 2001 12:00 PM
> To: 'Jan Christoffersson'; Jonathan Rosenberg
> Cc: [email-masked]'; [email-masked]'
> Subject: RE: [rohc] RE: Encapsulating EPIC in UDPComp
> 
> 
> Hi,
> 

Exactly correct! I just typed an email and sent it explaining this in more
detail. 

> just by ignoring the tree structure and making the dictionary flat.

Right! Note that this is not SIP specific. All protocols generally have a
structure where the previous thing restricts what is coming next. Some of
them have deep hierarchies, some are flat, but the point is, they are all
trees. By defining a general purpose "tree context construction and access"
protocol, we can cover a lot of protocols and a lot of algorithms. I have
argued that this tree structure covers LZW, LZSS, TCCB, and EPIC, which is a
pretty good set of coverage...

-Jonathan R.

---

---

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

> Sent: Wednesday, August 22, 2001 8:27 AM
> To: 'Jonathan Rosenberg'; [email-masked]'; [email-masked]'

Great! I had thought you were proposing that a pre-agreed upon Huffman code
be referenced during startup time, or that it was downloaded at startup
time. The proposal here is that the Huffman codes are constructed as you go,
since you need that to support dynamic codebooks, which I think we all agree
is needed. Of course, one can easily support downloading of the codes at
start time if a primitive is defined which is "WRITE this, but don't output
anything into a decompressed message".

> Yes. In EPIC, the Huffman codes are local to each dictionary item.

I think that you will need such a thing in general to achieve really good
compression.

> the type of token (READ, WRITE etc.).

Excellent idea! Our goal should ultimately be that the encoder output is
always a series of huffman codes, with some extra stuff to write the strings
into the codebooks that are not already there. Some more thoughts on that
below.

> We could do this as follows:
> 

I agree with that, but I'm not sure that you want to use these large bit
patterns to represent the initial commands. The result will be that initial
WRITEs and READs are really, really large. You only need these large codes
when there are lots of Huffman codes in any particular table. That won't
always be the case at all. 

One way to solve this is to have a really nice way to dynamically construct
the Huffman codes. Lets say you have a Huffman code represented by some
tree. Adding a new string can be done in only one way. You take an existing
vertex somewhere in the tree, and remove the subtree (if present). Add two
new branches below that vertex. Add the subtree to the right branch, and
place your new string to the the other. 

Here's an example Huffman tree. Assume 0 is left, 1 is right:

       /\
      /\ A
      B C

THis corresponds to:

00  B
01  C
1   A

Now, we wish to add D. TO do that, we send a command that reads like: "WRITE
into the table, spltting at 00, and the value is D". So, the decoder finds
the vertex 00. TO do this, it starts at the root, goes left, and then left
again. This is the vertex which currently encodes B. It removes B, adds two
branches, places B on the right, and the new element on the left:

    /\
   /\ A
  /\ C      
  D B

Now, this table looks like:

1  A
01 C
001 B
000 D

So, the idea is that we always start with a default table that has two codes
in it, which says "WRITE" in one of the two places:

initial table:

Code       output
-------------------
0          WRITE the string which follows by splitting the indicated vertex
in the curren table
1          WRITE the string which follows into the root table (i.e, change
contexts) by splitting the indicated vertex

This code would need to be followed by the identity of the vertex, and then
the text itself.

This way, you start off with very efficient codes that write into the table.
As the table gets larger, you use the efficient codes for the common
strings, and the code for writing into the table gets longer.

Rather than simply enclosing the text as a string, we should either Huffman
encode that with a standardized table, or else take all of the text in a
message, put them together, compress it as an independent blob, and then
send that together.

> the tokens explicitly in the first place).

Right. My proposal above reduces that as well, since this overhead is not
once per message, but once per new token.

> code as well, so that we don't have to send it explicitly every time.

Right, that is the proposal above.

> the tree, as we can specify this route using only a single short

Hmm, interesting idea. You need to be careful about this, though, since
management of this tangle of tables can be complex. It would be really nice
to maintain a simple structure. 

I think the way to do what you are proposing is to define a command which is
"WRITE into the current table, splitting the specified vertex. The element
to write is found by reading from here with the following huffman codes:
XXX, and then the next table is the existing one at the end of the read".

This turns the tree of tables into a more general purpose digraph, which is
probably a really good idea. It can save a lot of overhead in the management
of the table. Protocols, like SIP, have many "paths" through the message
which can arrive at a common piece of data (for example, the SIP URL). This
way, the encoding for the SIP URL appears only once in memory, rather than
based on each path to get to it.

Maybe time to start writing all of this up in an updated I-D for UDPComp,
since its probably hard to get it from these terse emails....

-Jonathan R.

---

---

From: "Liu Zhigang.C (NRC/Dallas)" <[email-masked]>
Date: Wed, 22 Aug 2001 18:55:43 -0500

Hi,

Support for Huffman codes is clearly beneficial and the detailed
discussion here cleared many confusions in my head. However, I hope 
we still keep simplicity in mind while stretching out for extreme 
compression efficiency. From byte array to list, to tree, to 
graph, each one can cover the previous one but at the price 
of higher complexity. 

Besides increasing compression ratio from the encoding point of
view (which has been dwelt on with much detail in this thread), 
we should also remember other simple mechanisms that boost compression 
ratio even without complicated encoding, such as user-specific
dictionary 
and cross session dictionary. The former puts redundancy in dictionary 
early so that they can be used right away, and the latter allows the 
dictionary (after "hard working" synchronization) to be used for later 
session. These are simple concepts that are orthogonal to encoding 
algorithms. 

Another useful mechanism is the "shared dictionary" (as Jan mentioned
early). This fits especially well to the (approximately) zigzag pattern 
of SIP messages. It incurs some challenge to the dynamic assignment 
of Huffman codes in the tree structured dictionary. But I believe
it is doable.

In short, we should tackle the problem from all angles by combining
capabilities as Jonathan said. As to find "the right sweet spot 
between compression efficiency and flexibility", I would like to 
add simplicity as another dimension.

BR,
Zhigang

> From: ext Jonathan Rosenberg [mailto:[email-masked]]
> Sent: August 22, 2001 11:51 AM
> To: 'Price, Richard'; Jonathan Rosenberg; [email-masked]';
> [email-masked]'
> Subject: [Sip] RE: Encapsulating EPIC in UDPComp
> 
>

---

From: "Price, Richard" <[email-masked]>
Date: Wed, 29 Aug 2001 12:59:55 +0100

Hi,

A few more thoughts on the dictionary structure enclosed inline.

Regards,

Richard P

> Sent: Wednesday, August 22, 2001 5:51 PM
> To: Price, Richard; Jonathan Rosenberg; [email-masked]';
> [email-masked]'

This is a very nice idea but I'm not sure how to make it robust against
misordering or packet loss between the compressor and decompressor.
The compressor will need to continue sending the explicit form of the
token until it receives confirmation that it has arrived at the
decompressor, after which it can switch to the more efficient Huffman
code for the token. Using the above technique, can we make sure that
writing the same Huffman code into the table more than once will not
cause problems?

> based on each path to get to it.

Once the decompressor arrives at the common piece of data (say the
SIP URL), how should it decide where to go next? Algorithms like EPIC
and TCCB automatically jump back to the dictionary item which
preceded the SIP URL and keep going from there. Alternatively we
could just link the SIP URL to every possible dictionary item that
might follow it. This is simpler but less efficient - the decompressor
"forgets" which part of the SIP message happened to contain the SIP
URL and needs to be sent this information again.