Subject: Selective Acknowledgements... (fwd)
From: Luigi Rizzo <[email-masked]>
To: [email-masked]
Cc: [email-masked] (Luigi Rizzo)
Date: Mon, 18 Dec 1995 20:27:05 +0100 (MET)

Hi,

Jamshid Mahdavi <[email-masked]> pointed me to this group where
(among others) discussions on SACKs are being done. I have browsed
in the archives of the "[email-masked]" mailing list, and I believe
I am not replicating anything. Thus I enclose my original posting
(which was sent almost three weeks ago to comp.protocols.tcpip,
slightly edited after browsing on the archives of the mailing list)
and Jamshid suggestions.

----- A proposal for a compact encoding of selective acks -----

Date: Fri, 1 Dec 1995 14:02:03 +0100 (MET)
From: Luigi Rizzo <[email-masked]>
To: [email-masked]
Subject: A proposal for selective acks

[In the following I assume that the reader has read the section of
RFC1072 dealing with selective ACKS (which is a nice reading, as
most papers from Van Jacobson).]

The proposal for SACKs by Van Jacobson [RFC1072] is very clear and
detailed about a possible implementation, to the point that one
wonders why they haven't been actually included in RFC1323 and
implemented.

A possible explaination is that the SACK option, as specified in
RFC1072, might suffer from the limited amount of space available
for TCP options. This only enables to selectively ack a limited
number of out-of-sequence segments, thus reducing the effectiveness
of the mechanism. The problem comes from the need of passing both
the relative origin and the size of each segment, totalling 4 bytes
[or more] per segment.

However, consider the typical case in which SACKs would be useful,
i.e. the transfer of large blocks of data. In these conditions,
the sender should mostly send maximum-sized segments.  Now look at
the reassembly queue at the receiving station:  starting from the
first unacked byte, we have a sequence of holes (H) and segments
(S), starting with a hole and ending with a segment, as below.

	HHH SSSS HH SS HH SS HHHH SSSS HH SSS

What I expect to see (have not verified, though) is a sequence of
Holes-Segments whose size is generally a multiple of the MSS in
use for the connection. The only exceptions could possibly be first
hole (because of some odd-length communication before the large
block of data begins), and the last segment (which may contain less
than an MSS because no more data are available).

If the above is true, a SACK option could comprise the following fields:

  h1    the size of the first hole. The hole starts at the point
	indicated by the ACK field in the header.  [alternatively,
	this could be the sequence number of the first segment in
	the reassembly queue]

  s1	the size of the last segment.

  ss    the GCD of all the remaining blocks of segments/holes. This
	should usually represent the MSS in use. [Simple simulations
	showed that as the size of the string increases the chances
	of "ss" being larger than 1 segment becomes negligible]

  b[]	a bitmap indicating which segments (of size ss) are 
	present or not after the first hole
  
  lb	the number of elements in the bitmap b[]. Actually,
	only 3 bits are needed for lb because the option length
	could be used to derive the size of b[] in bytes.

Following the description of the SACK option in RFC1072, we could
represent h1, s1, ss as 16-bit integers, and use 2 bytes for option
kind+len. This would leave up to (40-8)=32 bytes for b[]+lb, i.e.
room for over 250 segments. Even if some room is taken by other
options (e.g. timestamps), there is still sufficient room to deal
with large windows [20 bytes=160 segments].

Note that only ones in b[] are meaningful: these SACKs, as RFC1072
ones, are cumulative. Thus so the receiver can send multiple SACK
with different values for h1, to deal with the following situations:

  * the send window is very large, and the bitmap is not large enough;
  * for some reason (the sender changes to a new MSS which is prime
    wrt the previous one; or the sender is sending very small segments,
    etc.) ss becomes very small.
  * there is a high loss rate even on SACKs, so we need to send several
    of them to be sure that at least one goes through. SACK segments
    are valuable in that can save a lot of traffic.
  * lots of segments arrive out of order, so we need to update the
    SACKs.

As a matter of fact, h1 could be thought of as a "skip" field, thus
it might be necessary to encode it with a larger number of bits,
say 32. But this is not a real problem as the encoding of the SACKs
is reasonably compact.

Maybe the data in b[] can be compressed further, especially if the
losses are not very large (in this case runs of '1' could be encoded
efficiently, as in FAX documents). If the losses become large,
though, I suspect that there is little chance for compression.

------------------- end of original message -----------------------

Jamshid Mahdavi <[email-masked]> suggests that the IETF is currently
considering a new proposal for SACK, but the details that he supplied
do not allow me to understand in which framework they are supposed to
work. I started looking at the problem due to the bad connectivity
problems we are having (losses in the 30-60% and more) with overseas
connections, and would like a SACK mechanism that works even in this
[somewhat depressing] scenario.

	Luigi
====================================================================
Luigi Rizzo                     Dip. di Ingegneria dell'Informazione
email: [email-masked]       Universita' di Pisa
tel: +39-50-568533              via Diotisalvi 2, 56126 PISA (Italy)
fax: +39-50-568522              http://www.iet.unipi.it/~luigi/
====================================================================