Subject: Re: SACK option
From: [email-masked] (Fred Bohle)
To: dab
Cc: [email-masked]
Date: Thu, 30 Jan 92 17:55:41 EST

OK, you want a vote, here is mine.

Yes, split the document in two parts.  Pass the first one up
as you suggest.

Hold the second while we resolve how the SACK option is formatted
and how it is used.

The question in my mind is why does Van say at least 4 SACK values
are required???

Fred
------------------------------------------------------------------------
Fred Bohle			EMAIL: [email-masked]
Interlink Computer Sciences	AT&T : 301-317-6600 
9145 Guilford Road, Suite 175
Columbia, MD 21046
------------------------------------------------------------------------

Date: Thu, 30 Jan 92 15:22:56 CST
From: dab@hemlock (David Borman)
To: [email-masked]
Subject: SACK option
Cc: [email-masked]

Bob Braden and I discussed the issue about what to do with
the SACK option.  When we all agreed on the SACK option at the
Santa Fe IETF meeting, it was generally felt that even though we
didn't have a solid feeling for the semantics of the SACK option,
we at least knew what the format should look like.

Well, we don't feel that that is true anymore.  The discussion that
I have had with Van Jacobson, the limited discussion here on the mailing
list, and the silence from the vast majority of this mailing list
(there are 74 individuals and 6 exploders on this mailing list)
indicates that we really have to get a better feel for the SACK
option before we can say that we know what it should look like. 

So, to expedite matters, Bob has agreed to split the document into
two pieces.  The first part will contain the description of the
Window Scale and Timestamps options.  This document will be sent
to the IESG with a recomendation that it be published as a proposed
standard.  The other document will contain the SACK option, and we
can continue to bash it around until we get it right, or at least
have a better understanding of what it is trying to accomplish.

Our intention would be to pull the two documents back into a single
document at a later point in time.  They would get published as
individual proposed standards, and then when they are both ready
to go to draft status, we would pull them back together.

If anyone has any objections to this approach, nows the time to
speak up.  Otherwise, I'll take silence as agreeing to splitting
the document into two pieces.

			-David Borman, [email-masked]

Date: Mon, 27 Jan 92 17:29:36 -0500
From: [email-masked] (Jim DeMarco)
To: dab
Cc: [email-masked]
Subject: What to do???
Reply-To: [email-masked]

>So, changing the length to 16 bits, without scaling, is really not a
>viable solution.  Ok, then, I'm reducing my options to just two:
>
>	1) Leave the SACK option as currently stated in the draft,
>	   and publish it.
>	2) Change the SACK from a hard ack to a soft ack, and
>	   publish it.
>
>My preference is for #2.

I'd like to vote for #2.  This proposed option has the least amount of
*real-world* experience (as far as I know).  Let's implement soft
SACKs and find out how well it works.  After all, this is a "proposal"
and is still subject to change depending on what our implementation
experience shows us.

--Jim                                   [email-masked]

Date: Mon, 27 Jan 92 12:46:06 -0500
From: [email-masked] (Olafur Gudmundsson)
To: [email-masked]
Subject: Re: SACK option
Cc: [email-masked]

 > 
 > Ok, I sent out my mail to voice Van's concerns about the changes
 > that were made to the SACK option, and I have seen very
 > little response to it.  I suppose everyone is off at Usenix...
 > I would like to get this thing published as a proposed RFC, so that
 > leaves me these options:

 > 	1) Pass it up to the IESG as is.
 > 	2) Change the SACK from a hard ack to a soft ack, and
 > 	   pass it up to the IESG
To summarize the arguments: 
The argument against soft ack is that the receiver may run out of 
buffer space and it may get stuck because it can not receive the packet
that drains the out of sequence queue. 

The argument for soft ack is that less bandwidth is wasted on retransmissions. 

If receiver has fixed buffers allocated to a connection this is
hard or soft SACK is of no consequence. 

If receiver behaves as the BSD as having one buffer pool a deadlock can 
occurre.

If soft ack is the way we go then we may have a behavior that is realy 
strange, and wasteful. The scenario goes as follows:
A packet get lost, SACK is sent back reflecting that this packet got lost,
but everything after it got there. 
Sender retransmits that packet and sends some more packets, by the time the
retransmitted packet arrives to the receiver, the first SACK'ed packet 
after it has been dropped. New retransmit cycle takes place, under 
this condition the throughput drops down to few packets per roundtrip time. 

I personaly think that by careful engineering both behaviors (deadlock and
silly SACK) can be avoided and/or prevented. 

To avoid the problem of having to hold on to packets that have been
SACK'ed when number of free buffers is limited is to suspend 
SACK's and to drop all packets that arrive on connections that have
a packets received out of order. 
TCP should make the choice of stop sending SACK's when buffer pool falls
below a certain mark. 
When buffer space becomes even thighter it starts dropping all out of
sequence packets. 
Even if receiver agrees to support SACK's it is always free to suspending
sending SACK's  when it deems so necessary. 

 >	3) Change the length part of the SACK back to a 16 bit
 >	   value, so that the SACK contain 4 slots instead of 3,
 >	   and pass it up to the IESG.
I'm neutral on this one but the reason the meeting changed this one
was to separate the window scaling and the SACK's. 
If the SACK is 16 bits host needs to support window scaling to be able 
to support SACK. If it is 32 bits implementors are free to support only
SACK's. The argument about number of slots is valid but, I think am not 
ready to agree to this argument without getting more information on the 
assumptions used in the simulations that Van ran. 
Most packet losses on the Internet are random, burst losses are infrequent
and to my experience occur about the same time as connectivity is lost
(routing problems and crashing gateways). 
Therefore I agree with Van that if optimation is needed it should be
to accommodate random losses. 

 >	4) Do both 2 & 3. Change the SACK from a hard ack to a soft
 > 	   ack, and change the length part of the SACK back to a 16
 >	   bit value, so that the SACK contain 4 slots instead of 3,
 >	   and pass it up to the IESG.

 > Any other option (and probably options 3 & 4) would probably require
 > that this get held up a bit more... not what I want to see.

 > I am inclined to do option #2, change the SACK to a soft ack, and
 > then pass it on to the IESG, leaving the offset/length fields at
 > 32 bits each.  Van had indicated to me that he really would like
 > to see it be a soft ack, but that he could live with the 32 bit
 > offset/length fields, even if he didn't like it.
#1 and #3 are fine by me. The arguments for 2 are sound to much like 
a particular implementation likes that better than the other option 
rather than strong argument against doing things that way. 
Of course this is the most widely used implementation. 
Given that window scaling is a simple change I'm sure that for 
most implementing the SACK's and the timestamp addition it is not 
a big problem of adding window scaling at the same time. 

 > This gets the thing published, and we can then hammer out any
 > problems with SACK later. Any changes would necessitate a new
 > TCP option number to avoid interoperability problems, but I don't
 > really view that as a serious obstacle.

 > 			-David Borman, [email-masked]

-	-	-	-	-	-	-	-	-
Olafur Gudmundsson  Dept. of Computer Science University of Maryland
Internet: [email-masked]               UUCP: {...!}uunet!mimsy!ogud
UPS: College Park MD. 20742             Tel: (301)-405-2767 FAX:6707

Date: Mon, 27 Jan 92 10:10:30 CST
From: dab@hemlock (David Borman)
To: [email-masked]
Subject: Re: What to do???

I received a letter from Thomas Skibo that he did not copy to the
mailing list, and he brought up a very valid point.

I mentioned changing the length field of the SACK from 32 to 16 bits,
to allow there to be 4 slots instead of 3.  Unfortunatly, my brain was
in the wrong gear...  I was thinking of NACKs spread out evenly over
the window, in which case the 16 bit length field would work.  But
as Thomas pointed out, the SACK option is acknowlding the data that
did arrive, and if you have a large window and not much loss, you will
get many packets together and with the 16 length you would not be able
put them into a single SACK option when the length exceeds 64K.

So, changing the length to 16 bits, without scaling, is really not a
viable solution.  Ok, then, I'm reducing my options to just two:

	1) Leave the SACK option as currently stated in the draft,
	   and publish it.
	2) Change the SACK from a hard ack to a soft ack, and
	   publish it.

My preference is for #2.

I'd like to see some e-mail voting out there.  Please either reply
to the mailing list, or directly to me.  I'll count up the votes,
and announce the results to the mailing list.  I'd like to wrap
up this issue, and get the thing published.

			-David Borman, [email-masked]

P.S. There is one other option.  Pull the SACK option out into
a seperate document, and publish the document with just the Window
Shift and Timestamp options, and continue to discuss the SACK option...

Subject: What to do?
To: [email-masked]
Date: Fri, 24 Jan 92 9:21:42 CST
From: [email-masked]

After reading what Dave wrote about Van's concerns, I would like the SACK to
be advisory since our implementation also over commits its receive buffers.

Otherwise I don't have any problems at the moment with the current draft. 
Send it in with this one change.

Kurt Matthys

Date: Thu, 23 Jan 92 17:25:54 CST
From: dab@hemlock (David Borman)
To: [email-masked]
Subject: What to do???

Ok, I sent out my mail to voice Van's concerns about the changes
that were made to the SACK option, and I have seen very
little response to it.  I suppose everyone is off at Usenix...
I would like to get this thing published as a proposed RFC, so that
leaves me these options:

	1) Pass it up to the IESG as is.
	2) Change the SACK from a hard ack to a soft ack, and
	   pass it up to the IESG
	3) Change the length part of the SACK back to a 16 bit
	   value, so that the SACK contain 4 slots instead of 3,
	   and pass it up to the IESG.
	4) Do both 2 & 3. Change the SACK from a hard ack to a soft
	   ack, and change the length part of the SACK back to a 16
	   bit value, so that the SACK contain 4 slots instead of 3,
	   and pass it up to the IESG.

Any other option (and probably options 3 & 4) would probably require
that this get held up a bit more... not what I want to see.

I am inclined to do option #2, change the SACK to a soft ack, and
then pass it on to the IESG, leaving the offset/length fields at
32 bits each.  Van had indicated to me that he really would like
to see it be a soft ack, but that he could live with the 32 bit
offset/length fields, even if he didn't like it.

This gets the thing published, and we can then hammer out any
problems with SACK later. Any changes would necessitate a new
TCP option number to avoid interoperability problems, but I don't
really view that as a serious obstacle.

			-David Borman, [email-masked]

To: [email-masked] (David Borman)
Cc: [email-masked]
Subject: Re: SACK option 
Date: Tue, 21 Jan 92 09:33:11 +0000
From: Christian Huitema <[email-masked]>

A couple of months ago, I contributed a message explaining why I was not very
enthusiastic about SACKs, essentially because SACKs trade network efficiency
for longer delays and larger memory requirements. SACKs have two theoretical
advantages:

1) they enable the emitter to "only retransmit the missing bits", instead of
retransmitting the full window, resulting in better network utilisation.

2) they enable the emitter to "decommit s-acked buffers", thus resulting in
better memory utilisation at the emitter side.

Van's idea of "soft-sacks", which would be merely hints of "I believe I have
received bytes X to Y and Z to T, so please retransmit up to X-1 and also Y+1
to Z-1, but maybe I am wrong, so expect me to ask you to also retransmit X to
Y, basically destroys the second advantage. Indeed, as he points out, the
memory can only be decommitted at the emitter side if the corresponding part
was committed at the receiver side. Committing memory at the receiver side is
contradictory with "system buffer" implementations, where the only bytes
which can be safely hard-acknowledged are those already processed by the
application.

If you buy that, as I am ready to, then you should pursue your analysis a bit
more. Your sacks are not "selective acks" anymore, as they do not enable the
emitter to decommit its memory; in fact, they are "selective nacks", or
SNACKs, telling the emitter that something is missing, and would you please
retransmit it asap.

Then, if you also buy the "random loss" hypothesis, you can go a bit further
(in fact, if you do not buy that, you should not do selective acks at all).
Why not simply redesign the SNACK option to contain a sequence of sequence
numbers, essentially meaning: I did not receive byte number X. It will then
be easy for the emitter to figure out which packets are concerned -- as easy
as if a length field was present. And you could stick many of these numbers
in the packets.

If you dont feel confortable with a sequence number only, then you could
imagine that the SNACK contains holes, with a "first byte of hole (32),
length of hole (16)" philosophy. You could even save space by mandating that
the first hole id be omitted, as it is equal to the sequence number.

Christian Huitema
PS.
SNACKs work fine for multipoint, too...

Date: Mon, 20 Jan 92 17:10:44 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked], [email-masked]
Subject: Re:  SACK option

I am still against any interaction between the SACK option and 
window scaling. Has anyone looked at this problem from a 
data compression angle? The algorithm proposed by Van et all is 
essentially an ad-hoc lossy compression algorithm. Before we 
start truncating random offsets (even when we don't have to!) 
I think someone should show that no non-lossy compression algorithm 
that gives us 6 slots is possible. Given that droped packets are not 
on the critical path I think we can afford to spend some cycles.

Stated more formally:

Is there a fuction f such that finverse(f(y)) = y where 
y is an arbitrary 6 slot SACK and sizeof(f(y)) <= 12 * 16 bits.

This is what data compression research is for. Even if such 
an algorithm turns out to be more "complex" then the orginal 
SACK proposal we probably come out ahead because the resulting 
offsets and lengths will be correct if the function is correct and 
it should be possible to write a machine independant version of 
the function in C and give it away. You might also be able to 
do better than 6 slots. 

Sean O'Malley

Date: Mon, 20 Jan 92 17:22:53 -0600
From: [email-masked] (David Borman)
To: [email-masked]
Subject: SACK option

Well, I have yet to see anything on the mailing list from Van
Jacobson about the changes to the SACK option that were agreed
upon at the last IETF meeting, and I know he has some concerns
because he told me about them when I saw him the week before last.

I would like to see this document get approved, but I'd also like to
make sure that what gets approved is something that everyone can live
with, Van included.  So, to expidite matters, I'll bring up Vans points
for him.

1) First, the issue of whether the SACK is a hard ACK or just advisory
   information.  As you know, it was agreed upon at the IETF meeting that
   the SACK would be a hard ACK of data.  Van feels that it should be
   the other way around, that the SACK is just advisory information.

   I was the one who brought up the issue to begin with, because in doing
   my implementation it occured to me that my code could potentially, on
   the receiver side, throw away data that had been received out of sequence,
   and that had been SACKed.  I didn't really care whether they were hard
   acks or advisory, as long as it was specified.

   Bob Braden pointed out that if you have real buffers reserved on the
   reciever side, then it doesn't matter which way you set things up,
   either way will work.  Van's view is that on a system where the buffers
   are not pre-allocated (like the BSD code) and the receiving host often
   over-commits its receive buffers, the hard SACK can cause connections
   and/or hosts to hang.  The worst case scenario is that the receiver needs
   to free up some of its buffers to allow more packets to come in, but all
   of the buffers are sitting on TCP resequencing queues, and cannot be
   thrown away because they have been SACKed, and they cannot be delivered to
   the user because there is a hole in the data.

   So, Van would like to see the SACK be made strictly advisory; SACKs are
   just hints to the re-transmitter about what should be retransmitted, it
   is not a commitment that the SACKed data will never have to be resent.

2) The second concern that Van brought up is about the changing of the
   fields of the SACK option from 16 to 32 bits.  As everyone knows, due
   to the maximum length of the TCP options, with the 16-bit fields you
   could have up to 6 sacks per SACK option, and with 32-bit fields you
   can only have 3 sacks per SACK option.  His claim is that with the
   simulations that he has been running, it shows that you really need
   between 4 and 6 slots in the SACK, and that 4 is a minimal number.
   There are three things that could be done:
	1) Leave it at 32-bits, we'll just have to deal with only
	   having 3 slots/SACK option.
		If Van is right, then leaving things as they
		are will keep the SACK option from being as
		useful as it could be.
	2) Leave the offset at 32-bits, and change the length back
	   to 16 bits.  This would allow 4 slots/SACK option.
		This means that if you loose more than 64K worth
		of packets in a row, you will have to use multiple
		slots in the SACK to acknowledge them, or not be
		able to SACK all the data.  The flip side is that
		if you have random drop, which Van claims is the
		case, the loses will be spread out over the window,
		so you won't be having large lengths, and you get
		one more slot in the SACK.
	3) Change both fields back to 16 bits, allowing 6 slots/SACK,
	   but buying back the interaction with the window scale option...
		Van says something like: "What's the problem?  It's
		not complicated.  When the packet comes in, you shift
		the values by the window scale option, and use those
		new values.  When sending the SACK, you shift the
		value just before filling in the fields.  It is not
		a difficult problem, and then you have 6 slots in
		the SACK".

Well, having put forth Vans viewpoints (Van, if I mis-represented you,
please set the record straight), I'll offer my views.  I don't have
any problem with making the first change.  As I said before, I really
don't care whether SACKs are hard or advisory, as long as it is set
one way or the other.  And since my code is based on the BSD code,
I'm inclined to advocate making SACK strictly advisory.

As for the slots/SACK issue, in my mind it comes down to a couple of
questions:
	1) Do you want to buy into the interoperation between the
	   SACK and the Window Scale options?  If that's ok, then
	   lets go back to all 16-bit fields.
	2) Do you belive that losses will be random, or in clumps?
	   If you belive the former, then a 16-bit length field is
	   fine, and will give a fourth slot in the SACK.  If you
	   belive the latter, then you'll probably want the 32-bit
	   fields.

I don't like having interaction between the SACK and the Window Scale
option. If Van can support the argument that we need at least 4 slots,
I'd be willing to accept changing the length to 16-bits to allow a
fouth slot in the SACK.

After thinking about the SACK option and the number of slots, I sent
a message to Van about it.  My back-of-the-envelope analysis says that
the minimum number of slots needed in the SACK is dependent on the
loss rate:  If you lose less than one packet per RTT, then you
only need 1 slot.  If you lose 1-2 packets per RTT, then you need
two slots.  At 2-3 losses per RTT, you need 3 slots.  And so on.
With that kind of thinking, then as long as there is a limit to
the number of slots/SACK, there will be a threshhold for losses;
below that threshhold, things will work just fine.  Above that
threshhold, you will not be as effecient as possible.

Attached is a copy of the note I sent to Van.

			-David Borman, [email-masked]

> From [email-masked] Fri Jan 10 17:59:10 1992
> To: [email-masked]
> Subject: SACK
> Cc: [email-masked]
> Status: R
> 
> 
> Van,
> 
> With regards to the # of SACK entries needed, you said to me that
> the minimum number needed was four, and you talked about some
> "leap-frogging" as the reason.  I don't remember exactly what
> you were saying, so I've sat down and done some thinking about
> this.  As you said, the loss that we are concerned about is where
> the loss rate is random, not bursty, so our losses are distributed
> over the window.
> 
> It seems to me that the number of slots needed in the SACK option
> is dependent only on how often packets are lost per RTT, and that
> the higher the loss rate, the more slots are needed.
> 
> Here's my thinking:
> 
> For the sake of argument, let's assume that we can send 10 full-size
> packets per RTT, and that the receivers window is large enough that
> the sender isn't going to have to slow down.  If we have exactly one
> lost packet, the we'll see something like this from when the lost
> packet was first sent:
> 
> 	Time	Sender			Receiver
> 	----	------			--------
> 	0.0RTT	packet 1 is sent & lost
> 	0.1RTT	packet 2 is sent
> 	0.2RTT	packet 3 is sent
> 	0.3RTT	packet 4 is sent
> 	0.4RTT	packet 5 is sent
> 	0.5RTT	packet 6 is sent	(Packet 1 does not arrive...)
> 	0.6RTT	packet 7 is sent	Packet 2 arrives, ACK:0/SACK:2 sent
> 	0.7RTT	packet 8 is sent	Packet 3 arrives, ACK:0/SACK:2-3 sent
> 	0.8RTT	packet 9 is sent	Packet 4 arrives, ACK:0/SACK:2-4 sent
> 	0.9RTT	packet 10 is sent	Packet 5 arrives, ACK:0/SACK:2-5 sent
> 	1.0RTT	packet 11 is sent	Packet 6 arrives, ACK:0/SACK:2-6 sent
> 	1.1RTT	ACK:0/SACK:2 arrives	Packet 7 arrives, ACK:0/SACK:2-7 sent
> 	       	Packet 12 is sent
> 	1.2RTT	ACK:0/SACK:2-3 arrives	Packet 8 arrives, ACK:0/SACK:2-8 sent
> 		Packet 13 is sent
> 	1.3RTT	ACK:0/SACK:2-4 arrives	Packet 9 arrives, ACK:0/SACK:2-9 sent
> ***		Packet 1 is sent
> 	1.4RTT	ACK:0/SACK:2-5 arrives	Packet 10 arrives, ACK:0/SACK:2-10 sent
> 		Packet 14 is sent
> 	1.5RTT	ACK:0/SACK:2-6 arrives	Packet 11 arrives, ACK:0/SACK:2-11 sent
> 		Packet 15 is sent
> 	1.6RTT	ACK:0/SACK:2-7 arrives	Packet 12 arrives, ACK:0/SACK:2-12 sent
> 		Packet 16 is sent
> 	1.7RTT	ACK:0/SACK:2-8 arrives	Packet 13 arrives, ACK:0/SACK:2-13 sent
> 		Packet 17 is sent
> 	1.8RTT	ACK:0/SACK:2-9 arrives	Packet 1 arrives, ACK:13 sent
> 		Packet 18 is sent
> 	1.9RTT	ACK:0/SACK:2-10 arrives	Packet 14 arrives, ACK:14 sent
> 		Packet 19 is sent
> 	2.0RTT	ACK:0/SACK:2-11 arrives	Packet 15 arrives, ACK:15 sent
> 		Packet 20 is sent
> 	2.1RTT	ACK:0/SACK:2-12 arrives	Packet 16 arrives, ACK:16 sent
> 		Packet 21 is sent
> 	2.1RTT	ACK:0/SACK:2-13 arrives	Packet 17 arrives, ACK:17 sent
> 		Packet 22 is sent
> 	2.1RTT	ACK:13 arrives		Packet 18 arrives, ACK:18 sent
> 		Packet 22 is sent
> 	2.2RTT	ACK:14 arrives		Packet 19 arrives, ACK:19 sent
> 		Packet 23 is sent
> 
> 
> So, at 1.5RTT + 2 packets, the reciever stops sending SACK for the missing
> packet.  By 2 RTT + 1 packet, everything is all cleaned up.  If there were
> no dropped packets between when packet 1 was lost and when it was
> retransmitted, then just 1 SACK slot is needed.  Packet 1 gets retransmitted
> at 1RTT+3 pkt, so if the drop rate is less than 1 packet per 1RTT+3pkt, then 
> only 1 slot/SACK is needed.  If the drop rate is such that between 1-2
> packets per 1RTT+3pkt is lost, then we would have the above scenario
> overlapped once, and a SACK with 2 slots is needed during the overlap.
> Likewise, if the drop rate is between 2-3 packets/1RTT+3pkt, then a
> three slot SACK is needed, and so on, and so on.  In general, if the
> drop rate is more than D packets per 1RTT+Npkt, you will need a SACK option
> with D+1 slots to achieve maximum throughput, where D is the # of dropped
> packets, and N is the # of SACKs needed to kick off the retransmit.
> 
> This analysis doesn't support your contention that three SACK slots is
> not enough.  What it does support is that the more lossy the network,
> the more slots you need.
> 
> Back-of-the-envelop says that the maximum number of SACK slots needed
> would be on the order of the number of packets that can be sent per RTT.
> 
> What are the loss rates that you are using in your simulations?
> 
> Any comments or holes in my logic?
> 
> 			-David Borman, [email-masked]
> 

Date: Thu, 9 Jan 92 03:52:31 CST
From: [email-masked] (Zubin Dittia)
To: [email-masked], [email-masked]
Subject: SACK option...

If we allow 32 bits for the relative offset and length fields in
the SACK option, I was wondering if it might make more sense to
use the starting sequence number and the ending sequence number
(or the starting sequence number and the block length) for each
block of data being acknowledged.  Could someone explain why
relative offset and length were selected, and the trade-offs
involved, if any.

Zubin.