Subject: RE: [Sip] RE: [rohc] signaling message compression - speed up

From: Jonathan Rosenberg <[email-masked]>
Date: Fri, 7 Sep 2001 15:04:53 -0400

> -----Original Message-----
> From: Price, Richard [mailto:[email-masked]]
> Sent: Monday, September 03, 2001 12:56 PM
> To: 'Liu Zhigang.C (NRC/Dallas)'; [email-masked]
> Cc: [email-masked]
> Subject: [Sip] RE: [rohc] signaling message compression - speed up
> 
> 
> > The schedule of this work item (from what I heard) is
> > quite aggressive. To achieve that, should we start to
> > piece good ideas from different proposals together and 
> > create a new draft? From there, we can proceed with a 
> > few cycles to refine it.
> 
> From the discussions so far, I believe that the following changes
> could usefully be made to the current UDPComp draft:
> 
> Dictionary structure:
> 
> Should be able to handle a wide range of compression algorithms
> (in particular SIP-aware algorithms like EPIC, TCCB and
> template-based compression, as the current overhead for these
> schemes is large). The protocol overhead should be minimal, as
> should the complexity of the dictionary structure.

Agreed. This is the fundamental premise of the UDPComp proposal.

> 
> My current favourite is the digraph dictionary, which is simpler
> than a tree structure and more general to boot. I could provide
> some text on this if it is needed.

I am still concerned about the overhead of indicating how to connect the
digraph together. 

> 
> Context management:
> 
> Currently the context is identified by IP address and port, and is
> initialised empty. However this does not at present allow us to use
> the following:
> 
>   -  User-specific dictionary
>   -  Cross session dictionary
>   -  Shared dictionary
> 
> Perhaps we could make the context selection a local implementation
> decision at the compressor (as per RFC 3095)? This would generalise
> what we can keep in the dictionary across sessions without needing
> additional standardisation.

User specific and static dictionaries can all be supported by a single
decoder capability - the ability to set a codebook entry without
constructing decoder output. With this, the encoder could transfer the user
specific and static codebooks at init time of the session (presumably before
a call is made). 

Cross session and shared dictionaries do require additional context
management.

> > 1) User specific dictionary (seems every agreed during
> > the discussion)
> 
> Having a user-specific dictionary gives a big boost to the
> compression ratio (80% better for EPIC, 40% better for
> TCCB etc.), so we should clearly think about how to capture
> this performance benefit. How does it square with the
> UDPComp idea of making the compression algorithm a local
> implementation decision? How would we go about standardising
> a user-specific dictionary within this framework?

See above idea.

> 
> > 
> > 2) Maintain dynamic dictionary across session. It is 
> > reasonable not to throw away the synchronized dictionary.
> 
> This is another clear win in terms of performance, especially
> if we aren't using preconfigured static dictionaries. I
> believe that the "context" is currently defined by a pair of
> IP addresses and ports. Instead, perhaps we could just make
> context selection a local implementation decision at the
> compressor?

BTW, can we get a concise definition of session? I am confused about exactly
what "dynamic dictionary across sessions" means. Session, in the SIP
defintiion, means something very different than I think you mean.

> 
> > 
> > 3) Shared mode. Should help, especially for SIP messages.
> > 
> > 4) Make sure the dictionary synchronization is robust
> > against packet loss/misordering. Complexity may be
> > affected by dictionary structure.
> 
> The main difficulty here is ensuring that the dictionary
> can continue to be used while entries are in the process of
> being added or modified. Any dictionary structure we use
> must be able to handle this.

Agreed.

> 
> > 
> > 5) Concurrency issue (re dictionary updates) in shared
> > mode.
> > 
> > 6) Make sure a misordered message can still be decompressed
> > correctly (related to 4 and 5 but a different issue)
> > 
> > 7) Protocol is generic. E.g. if tree structured dictionary
> > is used, should make sure Lempel-Ziv is still possible and
> > not penalized. Also, should not depend on SIP-specific
> > knowledge (although is should work well compressing SIP).
> > 
> > 8) Template encoding. Very useful for simple low-end terminals, 
> > which are probably the majority during the introduction
> > of SIP to cellular.
> 
> Template encoding is a compression algorithm, so the dictionary
> structure should be chosen such that template-based encoding is
> supported.

I think it is supported with a tree structured mechanism. Here's how it
would work:

Say you have a template that looks like:

A<x>BCD<y>

Where <x> and <y> are variables, and A,B,C,D are "constants for that
specific template. You have a bunch of templates like this. At init time,
the encoder sends codebook information to the decoder (this requires the
ability to operate as if you were sending a message, but you are just
performing the codebook manipulations, not generating output). The root of
the codebook tree contains empty outputs, but basically uses the "next
codebook" as the top of each template:

ROOT CB
-------

0    <null output> next CB = CB 1
01   <null output> next CB = CB 2
.....

Now, consider CB 1 which is the codebook for the template above. CB 1 would
have a single entry:

CB 1
-----

0   "A"  next CB = CB 3

Then, CB 3 contains, initially, some random thing, and values for the
variable x will go in this CB:

CB 3
-----

0   "whatever" next CB = CB 4

CB 4 looks like:

CB 4
----

0   BCD  next CB = CB 5

CB 5 contains the variable y, and is initialized to some random thing
initially. 

The primitive commands one would use to build this initially are:

WRITE_NO_OUTPUT, top=true, code = 0, value = ""
WRITE_NO_OUTPUT, top=false, code=0, value = "A"
WRITE_NO_OUTPUT, top=false, code=0, value="whatever"
WRITE_NO_OUTPUT, top=false, code=0, value="BCD"

WRITE_NO_OUTPUT is a new primitive that writes to the codebook but generates
no decoder output.

OK, now, when a request comes to be compressed, lets say we got:

AhelloBCDfoo

We would send:

0
0
WRITE, top=false, code=01, value ="hello"
0
WRITE, top=false, code=01, value="foo"

The overhead here is small; as good as log2(number of templates) + (number
of variables) + the overhead of indicating WRITE plus the codebook indices
of each string.

Thats pretty good, I think.

> 
> > 
> > 9) Anything else?
> 
> We might need to introduce pre-downloaded static dictionaries (very
> useful for reducing the working memory requirements, as well as
> for unidirectional links where it is more difficult to dynamically
> modify the dictionary).

Where does the requirement for unidirectional links come from, exactly? Is
that realistic? 

-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