Subject: Compressed ACKs and ACK Compaction

From: Dr G Fairhurst <[email-masked]>
Date: Thu, 14 Oct 1999 20:27:36 +0100

Perhaps we have at least three different situations:

First, links (or should we say network paths) which suffer loss of ACKs
If the
network (or link) can't buffer the capacity, it may loose the ACK
packet.

Second, links which suffer bandwidth asymmetry and predominantly suffer
delay
of ACKs.  I believe in the cases we've looked at using  Hybrid
Satellie/Terrestrial nets
the usual case seems to be that the network "queue" in the bottleneck
router builds out to such an extent that the RTO is exceeded and
retransmission occurs (without necessarily any
real loss).  ACK suppression (also called ACK filtering) helps, but
isn't always
sufficient and has some problems associated with TCP self clocking.

Third, half duplex and rate adaptive systems in which return bandwidth
really
does change quickly (<RTT) and may be often be a function of the level
of forward traffic.

I'm interested in them all, but what follows is a proposal for situation
2.

ACK COMPACTION

While there is some discussion about compressing ACKs and forwarding a
"compound" ACK to a gateway which explodes them, we recently published
some on-going work on
ACK Compaction:

ACK Compaction uses similar techniques as ACK Suppression, but with
several modifications. When a queue of ACKs builds up at the return
interface, older ACKs will be deleted from the front of the queue,
leaving the latest ACK for transmission. In performing ACK Compaction,
the transmitter appends information to this remaining ACK that is later
used by an expander for extraction (regeneration) of deleted ACKs. The
information contains the number of deleted ACKs (one byte) and the total
number of bytes acknowledged by the deleted ACKs (two bytes).

It is important at the tunnel end point to accurately estimate the
initial inter-arrival time
to space the first compacted ACK, since an underestimation may cause the
sender to transmit a large burst of packets to the network  or an
overestimation may result in a slow growth of cwnd. The expander,
therefore, continuously measures the average inter-arrival
time between initial normal ACKs (not compacted). The average value is
estimated using a recent window of N received ACKs. Prior to the
compaction of ACKs (from the queue that is built at the return
interface), the interface transmits packets at the line speed. The most
recent estimated average value, therefore, represents the inter-arrival
time for the first compacted packet.

In the case of Hybrid Satellite/Terrestrial nets you often choose to use
tunnelling anyway
on the return path between the satellite terminal and the internet -
hence this addresses some
of the issues about whether there may be alternate paths (the answer is
yes - but they *must*
pass through the tunnel end point). The work of the UDLR WG springs to
mind...

IPSEC and much of the problems with PEP do apply ... as the mail list
has suggested.

You may be interested to read the CCR paper that was recently published
by one of my Postdoctoral Research Fellows:

Return Link Optimization for Internet Service Provision Using DVB-S
Networks, N. K. G. Samaraweera
http://www.acm.org/sigcomm/ccr/archive/1999/jul99/ccr-9907-samaraweera4.html

We are now working on an updated version for a Journal publication
including some of our
experimental data.

Gorry Fairhurst

---

From: Hari Balakrishnan <[email-masked]>
Date: Thu, 14 Oct 1999 17:49:05 -0400

Garry,

> time for the first compacted packet.

Yes, you need to be careful about the rate at which you generate and space out 
new ACKs at the "other end" of the reverse link.  The pilc-asym draft calls the 
module that does this an ACK reconstructor.  It describes how to make the 
reconstructor adapt to and generate acks at the "right" rate, without any 
information in the packet header coming from the other side.

Both your scheme and the one outlined by Goran require that information be 
carried in the header.  Obviously, with this information, you can *potentially* 
do better.  But I wonder if you really need it---if the reconstructor can adapt 
without it and do quite well, why add this complexity and protocol for it?

Hari

PS: Notice that with the reconstructor described in the draft, if the "other 
end" changes during a connection, there's no problem---the reconstructor state 
is soft and is easily and automatically regenerated.

---

From: Dr G Fairhurst <[email-masked]>
Date: Sun, 17 Oct 1999 16:48:02 +0100

Hari Balakrishnan wrote:

> > ACK COMPACTION\

This sounds interesting,  I'm anxious you don't prescribe only one solution,
but accurately frame the problem and the potential techniques.

> without it and do quite well, why add this complexity and protocol for it?

This is not so, it was certainly not our intention to imply that our
scheme necessarily does this.  The "expander" in our current scheme does
not utilize any timing information in the "compressed" ACK stream, but does
the expansion using a rate-based scheme. The additional information carried
in the ACK stream is to ensure conservative behaviour.

> is soft and is easily and automatically regenerated.

This is good, and indeed is true also of our scheme, although in our scheme if
the remote tunnel end point moves, it must move to a router which implements
ACK compaction (i.e. we do not have a handshake procedure to negotiate
any settings of the remote tunnel).  In practice, such movement is probably
going to minimal since I believe it would would introduce security complications.

ISSUE:

ACK Filtering / Suppression has a serious negative impact on cwnd growth,
have you discussed this (I didn't find it in the section about this), and a
potential problem with promoting ACK Congestion.

REFERENCE:

Perhaps you'd be kind enough to acknowledge our paper as a reference?

> > http://www.acm.org/sigcomm/ccr/archive/1999/jul99/ccr-9907-samaraweera4.html

QUESTION:

One thing that always worried me was the impact of SACK - have you a
scheme proposed which would accommodate this sensibly?

Gorry Fairhurst.