Subject: RE: [rohc] ROHC-TCP, ack number compression

From: "Lars-Erik Jonsson (LU/EAB)" <[email-masked]>
Date: Mon, 22 Nov 2004 12:51:33 +0100

Mark,

I know you tried in your previous mail to give numbers on what 
savings we could expect, but I would like to get that clearer.

We need to look at the overall savings, i.e.:

* Compare uncompressed with compressed not using shared compression,
  and then add shared compression to that.

* When comparing shared versus not-shared, the not-shared case
  should be with the best possible alternative for ack optimization
  that we can come up with. 

As I still believe adding shared compression is an ugly solution
that is conceptually different than what we have ever done in
ROHC, I really want to understand how much it will actually give
us in terms of compression gains, and I want to see alternatives
carefully investigated before I'm willing to consider supporting
shared compression. If there are alternatives that can give us
almost as much, I would prefer not to go with shared operation.

/L-E

> -----Original Message-----
> From: West, Mark [mailto:[email-masked]]
> Sent: den 22 november 2004 12:35
> To: Lars-Erik Jonsson (LU/EAB)
> Cc: [email-masked]'
> Subject: RE: [rohc] ROHC-TCP, ack number compression
> 
> 
> 
> 
> > > - the remote compressor (decompressor) has to store a history
> > > of 'expected' ACK numbers (and the other end has to know how
> > > long this is!) [this is single biggest complexity issue, for me];
> >
> > Long in what regard? I have not thought much about this 
> yet, just get
> > the feeling we will have to do so. As Carsten noted, we will have to
> > be robust to losses, with e.g. a generation number. How much will we
> > save in the end?
> >
> 
> I hadn't thought about it much at the time, but have done a bit more
> thinking now (and hopefully untangled my brain in the process!)
> 
> So... the basic observation is that (for many links) a packet 
> sent from
> A -> B with msn_A, seqno_A, and payload_size_A can be used to 
> derive an
> acknowledgement value in the reverse direction.  That is, 
> there may be a
> packet with ackno_B == (seqno_A + payload_size_A).
> 
> First of all, the compressor at A must indicate to B that it 
> is storing
> tuples (msn_A, seqno_A + payload_size_A) and that B may use these to
> compress ack numbers.  A will store these tuples in a list of bounded
> size.  (There isn't a 'generation number' per se -- we use 
> the msn as the
> index).
> 
> B, on correct decompression, maintains its own list (assuming that it
> wants to do this -- it should be possible for B to signal A that it
> doesn't want to, so A can avoid storing the tuples 
> unnecessarily).  When B
> wants to compress an ack value, it looks it up in the list.  
> If it finds a
> match, then it needs to signal (robustly) the value of msn_A to A.
> 
> This, though, is just a general initialise value + LSB 
> encoding problem.
> (i.e. B may encode msn_a as irregular in the first n packets it sends,
> followed by suitable LSB encoding)
> 
> To manage the length of the list of tuples, B will only ever refer to
> msn_a values that stay the same or increase.  So, for 
> example, once B has
> referenced msn_A of 238, it will never refer to an msn_A < 
> 238; so A can
> discard these from its history.  A, in its turn, needs to be able to
> signal an error if it would ever overflow its tuple-storage 
> (i.e. it would
> have to discard something that B believes to be available for 
> reference).
> Each tuple is <= 8 octets [depending upon how much msn is kept], so
> storage shouldn't be a major issue...
> 
> It clearly has to be optional at both ends to do this.  If 
> A's storage is
> insufficent for a link, it will discover this (by overflowing 
> its buffer);
> if B's storage is insufficient it will realise (by not being 
> able to find
> ack numbers in its history).
> 
> In terms of saving, if we expect an ack ratio of 2, then every other
> packet in the forward direction will be referenced (and the typical
> 'interval' in msn_A is 2, rather than 1400+ for the actual 
> ackno).  This
> is quite a saving.
> 
> Retransmissions may cause some inefficiency (and I haven't 
> thought through
> all of the cases yet), but I *think* only where multiple, 
> non-contiguous
> packets are lost.
> 
> It sort of feels like it ought to work, in a fairly simple way.  But I
> might just be missing something glaringly obvious :-)
> 
> Cheers,
> 
> Mark.
> 
> 
> -- 
> 
> Visit our website at www.roke.co.uk
> 
> Roke Manor Research Ltd, Roke Manor, Romsey, Hampshire SO51 0ZN, UK.
> 
> The information contained in this e-mail and any attachments 
> is confidential to
> Roke Manor Research Ltd and must not be passed to any third 
> party without
> permission. This communication is for information only and 
> shall not create or
> change any contractual relationship.
> 

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: "West, Mark" <[email-masked]>
Date: Mon, 22 Nov 2004 13:30:28 +0000 (GMT)

Hmmm... it's often hard to put accurate numbers on these things without
acutally implementing it... :-)

However, let me try and discuss the numbers a bit more and see if that
clarifies things (there's always a first time!)

Uncompressed ack number = 32 bits (that one, at least, is easy)

Now, for this bit, I'm going to have to make some assumptions:

- MSS is ~1460 octets;
- robust to moderate loss / re-ordering -- allowing 3 bits for this;
- ack ratio == 2;
- this is a simple case without particular note of retransmissions

Expected compressed ack value with 'basic' LSB encoding is based on the
MSS and the ack ratio -- so we expect the 'average' stride to be ~2920.
This translates into 12 bits without any robustness; so we'd expect 15
bits once we've accounted for loss and re-ordering.

With a reverse-path ack compression scheme, I need to track changes in the
msn.  With an ack ratio of 2, this would require 1 bit.  The robustness
tax takes me up to around 4 bits.

With an 'implicit' ack 'stride' compression scheme (i.e. the decompressor
infers the stride from successive acks and the msn), you should be able to
achieve similar performance to reverse-path compression *if* the payload
size in the forward path remains fixed (dropping back to 'normal'
compression where it changes).  So, the expected size is somewhere between
4 and 15 bits -- it's quite hard to suggest where it might fall...
... plus it feels a bit fragile, but that might be because I haven't
thought through all the options.

With an 'explicit' ack 'stride' compression, you need first of all to make
assumptions about (i) the number of different strides you want to support;
and (ii) the range of strides (in terms of bit-reduction).  I'm assuming
that signalling the ack stride only takes a few bits (in terms of some
cost in indicator and 2 bits [say] to indicate the scaling factor) and
would need to be done relatively frequently.  However, this should add
less than 1 bit to the expected ack encoding.  The reduction that you
would get depends upon the scaling factor that you'd be able to use.
Maybe you could get 5 bits?

Summary:

- uncompressed ack           : 32 bits
- 'vanilla' ack compression  : 15 bits
- bi-directional compression :  4 bits
- implicit ack stride        : ?? bits
- explicit ack stride        : 10 bits ?

If I've made some dodgy assumptions or screwed up any of the calculations,
then I'm sure that folks will correct me... :-)

Cheers,

Mark.

--
Mark A. West, Senior Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone +44 (0)1794 833311   Fax  +44 (0)1794 833433

On Mon, 22 Nov 2004, Lars-Erik Jonsson (LU/EAB) wrote:

> Date: Mon, 22 Nov 2004 12:51:33 +0100
> From: "Lars-Erik Jonsson (LU/EAB)" <[email-masked]>
> To: "'West, Mark'" <[email-masked]>
> Cc: "[email-masked]'" <[email-masked]>