Subject: [Tsvwg] early retransmit limits

From: Mark Allman <[email-masked]>
Date: Thu, 24 Apr 2003 08:21:02 -0400

Now for something different and the same....

I'm interested in hearing some opinions on what to do about limiting
the use of early retransmit.  We are in the process of updating the
ID on the subject -- the current version is
draft-allman-tcp-early-rexmt-00.txt.  To briefly recap the draft
says that when the amount of outstanding data is < 4 segments and
the TCP sender has no new data to send (ala limited transmit) then
TCP can use ownd-1 dupacks to trigger fast retransmit behavior
rather than waiting for the RTO to fire.  The idea is basically that
in this case TCP knows that it will never get 3 duplicate ACKs and
cannot induce 3 duplicate ACKs with new data.

In the draft we sketch two versions of "worst case" scenarios
whereby one-third of the packets sent into the network are needless
retransmits caused by reordering not loss.  So, the question is
what, if anything, do we do about this worst case.  So, I'd like to
see some discussion / opinions on a range of reasonable options...

OPTION A
--------
Just don't do early retransmit.  The cost, in terms of network
wasteage and/or network wasteage prevention is just not worth it
for the benefits that ER provides.

OPTION B
--------
Ust use early retransmit without worrying about preventing bogus
retransmits.  In other words, the cases where this really breaks and
sends a huge amount of wasteful traffic into the network are
pathelogical and ER is tightly scoped enough that we don't need to
worry about a limit.

OPTION C
--------
Allow ER, but only once per connection.  Most connections
(especially those that will benefit from ER) are short.  So, this
will help lots of connections.  Also, this scheme is easy and cheap
to implement.  But, it will not help long connections through
networks where cwnd is less than 4 segments (due to either low
bandwidth or lots of statistical multiplexing).

OPTION D
--------
Allow some percentage of transmissions to be spurious.  The
deployment path here is sort of two-fold.

(D.1) If the sender and receiver are using timestamps the sender can
    use Eifel to figure out whether an ERed segment was spurious or
    not.  Alternatively, if the receiver sends DSACKs (which the
    sender has to "learn" by seeing one) then we can use those to
    detect spuriously ERed segments.  In either case, we count the
    number of ERed segments that were wrongly sent and make sure
    that this number is some small precent (say 3% -- an order of
    magnitude less than the worst case ER wasteage) of the total
    traffic being sent.

(D.2) In the case when neither timestamps nor DSACKs are used the
    sender can still use ER.  But, the sender must not ER more than
    some small percent (same as above - say 3%) of segments via ER.
    Essentially, this scheme makes the conservative assumption that
    every segment sent with ER is bogus for limiting purposes.
    (And, so, it is clearly more advantageous to the sender to use a
    D.1-like scheme.)

OPTION E
--------
The same D.1, but replace D.2 with OPTION C -- so, if you don't have
fine-grained information about the spuriousness of what you are
sending then you can only send one ER per connection.  (Of course,
this would also have to come with a way to detect that DSACK was
supported -- say, by overlapping the first two packets by one byte
or some such kludginess.)

OPTION x
--------
Some other tightly specified option that someone thinks of.  Send
text.

My personal leaning is towards option B.  (And, I do not speak for
my co-authors who can (and hopefully will) assert their own
preferences.)  One of the problems is that C, D and E only address
and limit the spuriousness for long connections.  But, for
connections that only send 3 packets (2 unique data packets and a
retransmit -- see draft for a better sketch of this "worst case")
none of these mitigations actually helps at all.  Also, I think the
worst case is pathelogical enough (2 (or 3) segment window,
persisten reordering that is just so and a TCP that cannot send new
data) that even without limiting we're not going to see a ton of
spurious retransmits running around the network because of ER.

I'd be thrilled to hear opinions on which option others like best.

Thanks!

allman

--
Mark Allman -- BBN/NASA GRC -- http://roland.grc.nasa.gov/~mallman/
_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 24 Apr 2003 15:23:51 +0200

At 14:21 24.04.2003, Mark Allman wrote:
>My personal leaning is towards option B.

As I said before, I'm convinced that option B is the right way to go.

>Also, I think the

I'm also convinced that this worst-case is so pathological that we 
shouldn't worry about it.

///Reiner

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 24 Apr 2003 10:05:15 -0400 (EDT)

> pathelogical and ER is tightly scoped enough that we don't need to

I think I prefer option B, but if there is a concern about too many
spurious retransmits occuring... perhaps one option may be to use a timer
similar to the delayed ack timer. That way, the sender provides the
opportunity for either new data to be sent or the ack for a reordered
segment to arrive.

~armando

0--                                                  --0
| Armando L. Caro Jr.      |  Protocol Engineering Lab |
| www.cis.udel.edu/~acaro  |    University of Delaware |
0--                                                  --0

---

From: Urtzi Ayesta <[email-masked]>
Date: Thu, 24 Apr 2003 16:15:57 +0200

hi all,

here are some thoughts

I wouldn't go for options D and E since they need to specify a parameter 
(the percentage)
and in my opinion this introduces some arbitrariness that I'm not 
comfortable with
since we don't know much about what this value should be.
In this sense we are introducing some complexity into the algorithm 
without a
remarkable benefit.

I wouldn't go for setting a hard threshold (option C) since
the aim of ER is to avoid lengthy timeouts for short TCP connections
as well as for interactive applications which send data in bursts.
Setting a hard threshold we  fail in the case of interactive applications.
Maybe we could consider setting a larger hard threshold to provide
some flexibility for long sessions as well, but again what should be the 
value
of this threshold...

as a coauthour I wouldn't go for option A... :-)

So my personal leaning is also towards B.
I expect that systematic high reordering to be pathological behaviour
and ER is in a certain way self-controling since
it would only trigger when the flying number of segments is small.

regards,
urtzi

---

From: Urtzi Ayesta <[email-masked]>
Date: Thu, 24 Apr 2003 16:36:09 +0200

>opportunity for either new data to be sent or the ack for a reordered
this seems to be a reasonable possibility. The value of the timer
could be the same as the one for delayed ACK, couldn't it?

thanks
urtzi

---

From: Mark Allman <[email-masked]>
Date: Thu, 24 Apr 2003 11:07:51 -0400

Armando-

> if there is a concern about too many spurious retransmits
> occuring... perhaps one option may be to use a timer similar to
> the delayed ack timer. That way, the sender provides the
> opportunity for either new data to be sent or the ack for a
> reordered segment to arrive.

I don't follow... Are you saying that we should do Vern Paxson's
trick of using < 3 dupacks, but adding a small timeout as well?  So,
something like "after 2 dupacks + 20 msec we can fast retransmit".
If not, can you try to explain again (maybe with an example)?  I am
just not sure I am following yet.

Thanks!

allman

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 24 Apr 2003 15:22:24 -0400 (EDT)

On Thu, 24 Apr 2003, Mark Allman wrote:

> trick of using < 3 dupacks, but adding a small timeout as well?

I don't know which trick you are referring to, but it sounds like Vern's
trick is similar to what I was thinking...

> So, something like "after 2 dupacks + 20 msec we can fast retransmit".

Yes. I am not sure about the 20ms begin the delay though. Maybe Urtzi's
idea of the same delay as the delayed ack algorithm uses would fine. But
anyway, let's first understand the idea properly...

The idea is to allow early retransmit to occur, but to try being
conservative by allowing the chance for either (a) 3 dupacks or (b) the
hole to be filled in case of reordering.

case (a)

   1. Suppose the sender sends segments 1, 2, and 3.

   2. The receiver receives segments 2 and 3, and sends two dupacks for 1.

   3. The sender receives two dupacks for 1 (i.e., segment 1 is missing).

   4. Since the TCP sender has no other data in flight and no more
      data to send, ER comes into play. However, the sender delays x ms before
      retransmitting.

   5. If within the x ms delay the sending application provides the
      TCP sender with more data to send, ER is not triggered. Instead,
      the TCP sender sends segment 4 and waits for the third dupack
      for segment 1 to arrive. Upon receiving the third dupack for
      segment 1, the TCP can do a "normal" Fast Retransmit.

   6. Otherwise, retransmit segment 1.

case (b)

   1. Sender sends segments 1, 2, and 3.

   2. The receiver receives segments 2, 3, and 1... in that order.

   3. The sender receives two dupacks for 1, which may begin to imply
      that segment 1 is missing.

   4. Again, since the TCP sender has no other data in flight and no
      more data to send, ER comes into play, but delays x ms before
      retransmitting.

   5. If the ack for segment 1 arrives at the sender before the x ms
      delay expires, then the sender infers that a reordering occured
      (as in this example) and no retransmission is necessary.

   6. Otherwise, retransmit segment 1.

~armando

0--                                                  --0

---

From: Mark Allman <[email-masked]>
Date: Thu, 24 Apr 2003 15:40:13 -0400

Armando-

Thanks for the clarification.  The ideas makes good sense to me
now.

I'm happy to throw that option on the list as a possibility.  So,
the list is something like:

    option A - no ER
    option B - ER as defined in the draft
    option C - ER, but only once per connection
    option D - use Eifel or DSACKs to ensure that bogus ERs are <
	some small percent of the data sent; if we don't have DSACK
	or timestamps, then just say that ERs cannot amount to more
	than this small percent of the data we send
    option E - use Eifel or DSACKs as option D; if we don't have
	timestamps or DSACKs then revert to option C and ER at most
	once per connection
    option F - ER after ownd - 1 dupacks arrive and some timeout
	occurs (hoping that in the idle time we get an ACK that
	indicates reordering or a new segment to send ala limited
	transmit) 

I still don't like A.  Go figure...

And, I still think C-E are predicated on us thinking that B would
cause too much spurious traffic in the network.  F tries to be more
robust than B (at the cost of a bit of extra machinery).  Is F
enough better that we then don't need to think about C-E?  

I still like B.  But, wait ....

I guess what I'd really like to know is whether folks are worried
about option B.  Several people have indicated on the list (and off
to me today) that they think ER ala B is scoped enough that it is
Just OK.  Before having a long discussion about C-F I guess I'd like
to get a feeling for whether some are concerned about B (which I
think is clearly the easiest path).

Thanks!

allman

---

From: Joseph Ishac <[email-masked]>
Date: Thu, 24 Apr 2003 17:38:23 -0400

> think is clearly the easiest path).

I can't think a way to really break option B, so I'd vote for it ;)

However, I think it would be beneficial to research the benefit of
options that strengthen ER (~if needed~).  So, if network conditions
change and reordering becomes more prevalent, we would know what the
benefit/impact of using ER would be (in its different forms).

On a side note.  There are studies to try and make TCP more robust to
packet reordering.  One such method is to increase dupthresh, and I'll
use that in the next example.  Suppose that during a connection, we've
grown dupthresh to a value greater than three.  If the connection then
later experiences an ER situation, is ER still valid? (b/c an increased
dupthresh would mean that you've experienced some amount of reordering,
which is non-negligible)

-Joseph

---

From: "Srijith. K" <[email-masked]>
Date: Fri, 25 Apr 2003 10:22:24 +0800 (SGT)

To add to option F, the *max* of the delay should be such that you give
just enough time for the ACK of the retransmitted packet to reach the
sender before the timeout occurs.

So, d(max)=RTO-x
where x can be RTT(smooth) or RTT(max) or RTT(prev).

Srijith

>       data to send, ER comes into play. However, the sender delays x ms
> before retransmitting.
>
> the TCP sender sends segment 4 and waits for the third dupack for
> segment 1 to arrive. Upon receiving the third dupack for segment
> 1, the TCP can do a "normal" Fast Retransmit.
>

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 24 Apr 2003 22:29:25 -0400 (EDT)

> I can't think a way to really break option B, so I'd vote for it ;)

Yes, you do... reordering ;-)

> packet reordering.  One such method is to increase dupthresh, and I'll

Well, my assumption was that the work that people are doing with TCP and
reordering is because reordering _does_ occur. I remember reading at least
one paper which said that reordering wasn't pathological (that was the
title actually). So my question is... is it _that_ unlikely that the
network is reordering, ownd < 4, and the sender doesn't have any more data
to send. Personally, _I_ don't know that we can say that, but maybe
someone else has more insight in this area.

> dupthresh would mean that you've experienced some amount of reordering,

Maybe this problem is where option F would work well. If the dupack
threshold is dynamic based on reordering experienced, then ER comes into
play anytime ownd < dupack threshold. Then by using a delayed ER (option
F), the sender is being extra conservative and taking into consideration
the reordering already experienced.

~armando

0--                                                  --0

---

From: "Srijith. K" <[email-masked]>
Date: Fri, 25 Apr 2003 10:30:20 +0800 (SGT)

Opps.. on second thought:

d(max)=(RTO-time_already_waiting_for_ack) - x

x=RTT(smooth) or RTT(max) or RTT(prev)

Regards,
Srijith

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 24 Apr 2003 22:33:00 -0400 (EDT)

> where x can be RTT(smooth) or RTT(max) or RTT(prev).

I think that the guidelines used for the delayed ack algorithm is a good
starting point. Recommended: 200ms. Max: 500ms. If delayed ER gets close
to a timeout, then the extra complexity isn't worth the potential gain.

~armando

0--                                                  --0

---

From: Mark Allman <[email-masked]>
Date: Thu, 24 Apr 2003 23:15:50 -0400

> options that strengthen ER (~if needed~).  So, if network
> conditions change and reordering becomes more prevalent, we would
> know what the benefit/impact of using ER would be (in its
> different forms).

I agree that if reordering became a lot more prevlent then it would
behoove us to re-think ER (both in terms of network resource
wasteage and the cwnd sacrifice that ER causes).  Put another way,
spurious ERs cause a penalty for the connection itself and so there
is an incentive to not spuriously ER.

> On a side note.  There are studies to try and make TCP more robust
> to packet reordering.  One such method is to increase dupthresh,
> and I'll use that in the next example.  Suppose that during a
> connection, we've grown dupthresh to a value greater than three.
> If the connection then later experiences an ER situation, is ER
> still valid? (b/c an increased dupthresh would mean that you've
> experienced some amount of reordering, which is non-negligible)

Maybe.  In the dupthresh adjustment schemes sketched in
draft-blanton-tcp-reordering-00.txt the dupthresh is cwnd-1 at its
maximum.  So, as the window drains dupthresh is reduced.  But,
clearly, we could keep a maxdupthresh that indicates if we have ever
changed dupthresh based on reordering.  But, if we're headed down
that road then I think all we really need to do is look for
duplicate ACKs and no loss and set a flag if we see such an event.
Then we can use that as input to some sort of ER decision.  (A
dupack can be caused by packet replication in the network, but
everything I have seen shows that to be quite rare.)  My own opinion
right now is that this is a bit of overkill for ER because its so
tightly scoped.  But, something to keep in mind for down the road if
ER ends up busting a lot.

Thanks!

allman

---

From: Mark Allman <[email-masked]>
Date: Thu, 24 Apr 2003 23:48:14 -0400

> So my question is... is it _that_ unlikely that the network is
> reordering, ownd < 4, and the sender doesn't have any more data to
> send. Personally, _I_ don't know that we can say that, but maybe

I would be concerned if I thought that this would cause a whole lot
of extra stuff to be sent into the network.  But, my feeling is that
the situation that breaks ER is actually not going to add a huge
percentage of unnecessary traffic to the network in general.  I bet
you could find some paths where it may be worse that others, but in
the overall scheme of things I don't think it will lead to
problems.  But, without a whole pile of data from a whole pile of
places I cannot say that for sure.  (And, that sounds like a good
argument for experimental to me.)

> Maybe this problem is where option F would work well. If the
> dupack threshold is dynamic based on reordering experienced, then
> ER comes into play anytime ownd < dupack threshold.

Which may be exactly what we have now if the dupack threshold is
tied to cwnd (ala another i-d of mine).  (Note that not all schemes
might have the same properties.)

allman

---

From: Spencer Dawkins <[email-masked]>
Date: Fri, 25 Apr 2003 05:36:56 -0700 (PDT)

Dear Mark,

You guys understand this stuff more clearly than I do, but my
spin is 

- the only connections affected are either in slow-start or
application-limited, right?

- the biggest burst we would see (on average) is one-half the
dupack threshold, right?

- with a dupack threshold of 3, we're within the burst rate we
see at the beginning of a new connection using initial cwnd=4,
right?

- if we actually DO succeed in losing something on the forward
path, we perform congestion avoidance anyway, right?

If these are true, I don't think we need to worry about the
effect of ER on the network with dupack threshold = 3.

For higher values of dupack threshold, I'm less certain, but the
answer is almost certainly tied to how big the dupack threshold
is allowed to become.

Spencer

---

From: Mark Allman <[email-masked]>
Date: Fri, 25 Apr 2003 09:01:37 -0400

Spencer-

> application-limited, right?

Or, if the advertised window is quite small.

The slow start case may not actually be an issue because you can use
limited transmit if you have new data to send and advertised window
to do it.

> - the biggest burst we would see (on average) is one-half the

I don't follow this... ER acts just like a fast retransmit -- only
it requires fewer duplicate ACKs.  So, I don't understand where the
bursting is coming from.

> see at the beginning of a new connection using initial cwnd=4,

(So, I can't answer this one either.)

> path, we perform congestion avoidance anyway, right?

Right.  ER is just an early fast retransmit.  All the CC changes
still apply.  Really, we're just looking at all the information and
judging that we could never fast retransmit if something was lost
and given that then we're readjusting the trigger for fast
retransmit. 

> answer is almost certainly tied to how big the dupack threshold

Right.  And, all that would have to be worked out if you wanted to
apply ER to dupthresh > 3 -- but, the current document scopes it to
specifically the current, static dupthresh.

Thanks!

allman

---

From: Spencer Dawkins <[email-masked]>
Date: Fri, 25 Apr 2003 06:13:05 -0700 (PDT)

OK, I mispoke...

Me-getting-smarter inline...

Spencer

> limited transmit if you have new data to send and advertised

OK, so with the current dupack threshold = 3, the amount of
additional traffic we might throw in is still less than 3
segments, right?

> it requires fewer duplicate ACKs.  So, I don't understand

Sorry, I misused the word. I meant additional traffic that might
not have happened if we'd RTOed instead. (and if I'm still
confused).

> (So, I can't answer this one either.)

Again, my point was that we are sending a small number of
additional segments (compared to RTO) ...

> and given that then we're readjusting the trigger for fast

So I think we are managing to agree, even though I was
incoherent...

> specifically the current, static dupthresh.

Thanks for helping me understand better...

Spencer

---

From: Mark Allman <[email-masked]>
Date: Fri, 25 Apr 2003 09:22:04 -0400

> not have happened if we'd RTOed instead. (and if I'm still

Ah... ok.  So, the amount of additional traffic that ER would inject
into the network over and above what the RTO would is:

  * zero in the case when the segment in question is actually lost

  * likely one segment in the case when reordering fools ER (that
    is, we likely resent a packet that would never have been resent
    via the RTO timer)

Does that make sense?

allman