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

From: "Lars-Erik Jonsson (LU/EAB)" <[email-masked]>
Date: Fri, 19 Nov 2004 08:18:57 +0100

> (3) relies upon the fact that, whilst it need not be the 
> case, it is highly
> likely that an ack value in the reverse path is directly 
> acking a packet in
> the forward path (i.e. it contains seq_no + payload_len).  
> Thus, if you know
> that the other endpoint has seen the packet in the forward 
> direction [you
> have decompressed the packet!], then you can identify an ack 
> by indicating
> which packet is being acked (by the MSN).
> 
> If you assume that the ack flow more-or-less moves in step 
> (i.e. increasing
> MSNs), then you get:
> 	Ack ratio assumed == 2
> 	Resilience to loss assumed ~ 4 packets
> 		=> 3+ bits of Ack Number (actually would need 
> to allow for
> more of a window)
> The advantage is, therefore, pretty clear in terms of 
> potential savings.
> 
> The disadvantages of this approach are:
> 
> - it only works when the compressor/decompressor can share data;
> 
> - 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? 

> - the issue of switching between 'MSN-based' and 'raw-ackno-based'
> compression (which, if we assume only happens rarely, shouldn't
> be too much of an issue).

I would rather ask:
1) How do two corresponding rohc pairs agree to use "bi-dir compr"?
2) Is the association between co-located compressor/decompressor
   used for this the same association used for piggybacked feedback?
2) Should it be possible to enable/disable this during operation?

I would not say enabling "bi-dir compr" is not much of an issue.

/L-E

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

---

From: "West, Mark" <[email-masked]>
Date: Mon, 22 Nov 2004 11:34:39 +0000 (GMT)

> be robust to losses, with e.g. a generation number. How much will we

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.

---

From: Kristofer Sandlund <[email-masked]>
Date: Mon, 22 Nov 2004 13:58:08 +0100

Hi Mark,

This seems like a really complex scheme. Wouldn't explicit signaling of 
ACK_stride be a simpler and _almost_ as efficient a solution to this? Then, the 
decompressor at B could infer this value with or without the help of the 
co-located compressor without the spec having to go into this messy area.

With the scheme you suggest, compressor B has to "(robustly) signal msn_a to A", 
so why not send an explicit scale value instead? If the compressor at B is 
implemented to use the co-located decompressor's info, it should seldom have to 
send the SEQ_scale more than once and manage scaling on "many" packets. Then we 
also get out of having to have some feature negotiation (or feature rejection as 
you suggest).

/Kristofer Sandlund, Effnet AB

---

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

Hi Kristofer,

> co-located compressor without the spec having to go into this messy area.

I don't feel that this is particularly complex (but that may just be me!)

The problem with explicit signaling is that (i) you have to take the
overhead of signalling it; and (ii) if you simplify this signalling (to a
small number of powers-of-two, for example) you reduce the efficacy of the
scaling.

However, if no-one feels that reverse-path compression of acks is worth
the effort, then I guess we don't do it...  I just want to make sure that
we discuss it!

> also get out of having to have some feature negotiation (or feature rejection as

note that the 'robust signalling' is no different from anything else that
we do.  And, in the main, it reduces to signalling a 'packet index' rather
than a 'byte index', which is less prone to variability.

And I don't think it's a complex 'negotiation': the compressor *does* need
to signal that it is storing ack numbers (in order for the other end-point
to know that it can use them).  If there's a way for the peer to say, 'I'm
not going to use them' it would potentially optimise storage needs, but it
doesn't affect the correctness/interoperability.

My view is also that explicit scaling will need to be sent relatively
regularly (assuming that it's a large enough value to give a sensible
reduction).  Which certainly doesn't mean that it isn't worth the effort!

Comments?

Cheers,

Mark.

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 22 Nov 2004 16:03:17 +0100

On Nov 22 2004, at 14:39 Uhr, West, Mark wrote:

> to signal that it is storing ack numbers

Also, we need some way to bind the forward and reverse channels, as 
well as the CIDs.
This may be interesting on some channels.
(There was a reason we did the state ID dance for SigComp...)

Gruesse, Carsten

---

From: "West, Mark" <[email-masked]>
Date: Tue, 23 Nov 2004 00:37:20 +0000 (GMT)

> Also, we need some way to bind the forward and reverse channels, as

True -- something that I had managed to ignore... :-)

> (There was a reason we did the state ID dance for SigComp...)

Good point: I'd managed to overlook flow separation issues (for example).
But do you really think that this is as messy as SigComp..?  We have a
little more control over the endpoints.  And so I don't think that the
SigComp state model is directly applicable.  (But I've still probably been
guilty of over simplifying...)

Cheers,

Mark.