Subject: [Tsvwg] early retransmit

From: Mark Allman <[email-masked]>
Date: Tue, 25 Feb 2003 07:43:05 -0500

Folks-

In December the Early Retransmit (ER) scheme that was originally
coupled with Limited Transmit (LT) (RFC 3042) received some
discussion on the list.  When doing limited transmit we decoupled it
from early retransmit because we had clear consensus for LT but not
the story was somewhat rockier for ER (which does not mean that we
had consensus *against* ER -- just that it was clear that if left
coupled ER would have held LT back).  

In any case, there seemed to be some positive vibes for ER in
Decemeber and so a few of us dusted off the old text, updated it and
released it again.  The id will appear in the archives shortly, but
until then you can grab it form the URL below...

    Mark Allman, Konstantin Avrachenkov, Urtzi Ayesta, Josh
    Blanton. Early Retransmit for TCP, February 2003. Internet-Draft
    draft-allman-tcp-early-rexmt-00.txt (work in progress).
    http://roland.grc.nasa.gov/~mallman/papers/draft-allman-tcp-early-rexmt-00.txt

We'd love to see feedback in a couple of areas...

(1) Is early retransmit, as specified, ever a good idea?  (That is,
    should we stop now? is it just fundementally busted?)

(2) The draft details a couple of scenarios in which reordering
    coupled with ER could cause a significant fraction (1/3) of
    traffic to be spurious.  We wonder if these scenarios are a big
    concern?  Or, are the probabilities low enough that we shouldn't
    worry about adding a bunch of complexity to deal with them?

(3) If we should deal with these cases with some algorithmic
    mechanism, what should we use?  We have a bunch of possible
    schemes sketched in the appendix.  Should we mandate one of
    these?  Or, something else?

Of course, any other feedback is always welcome.

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: "Armando L. Caro Jr." <[email-masked]>
Date: Tue, 25 Feb 2003 13:15:10 -0500 (EST)

Mark,

I have a few comments on the draft (and the topic in general)...

The draft says:

   "Research shows that a general reduction in
    the number of duplicate ACKs required to trigger fast retransmission
    of a segment to two (rather than three) leads to a reduction in the
    ratio of good to bad retransmits by a factor of three [Pax97].
    However, this analysis did not include the additional conditioning
    on the event that the ownd was smaller than 4 segments."

I don't see how the condition of ownd < 4 segments matters. If 3 dupacks
is more appropriate to due the amount of reordering, then less than 3
isn't appropriate regardless of ownd.

I prefer solutions which induce the possibility of 3 dupacks (or 4 missing
reports for SCTP). Hari Balakrishnan's solution of sending zero-byte
segments and Marco Mellia et al.'s solution of breaking segments into
smaller pieces are two ideas which I think deserve more attention.
Although these mechanisms may add _some_ load to the network, I think more
research is needed with these type of solutions.

I also think that more research is needed to determine what dupack
threshold is appropriate. It may be worthwhile to investigate the use of
a mechanism which begins with a conservative threshold, and then gets
adjusted over time. To start, DSACKs/Eifel/etc may be useful for
increasing the threshold.

~armando

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

---

From: Ethan Blanton <[email-masked]>
Date: Tue, 25 Feb 2003 13:31:47 -0500

> isn't appropriate regardless of ownd.

It may be slightly aggressive, but if it is effective at helping to
avoid RTOs and doesn't cause "too many" needless retransmits, I think
it's worth playing with.

> research is needed with these type of solutions.

Going on the (common, I think) that load is mostly per-packet rather
than per-byte, it seems to me that retransmitting on two dupacks (or
whatever) could in some cases cause less "needless" traffic, even if
it blows it sometimes and retransmits unnecessarily, than
indiscriminately sending some extra packets in every window.

I'm not saying these other methods don't have merit, or that they
should not be researched -- I think they should.  But I would say that
their existence does not preclude the usefulness of trying and
evaluating early retransmit, and especially comparisons between the
various methods' virtues and disadvantages.

Ethan

---

From: Mark Allman <[email-masked]>
Date: Tue, 25 Feb 2003 13:40:55 -0500

> I don't see how the condition of ownd < 4 segments matters. If 3
> dupacks is more appropriate to due the amount of reordering, then
> less than 3 isn't appropriate regardless of ownd.

Unless the pattern of reordering a connection experiences is
effected by the amount of load that connection is placing on the
network.  The Bennett, Partridge, et. al. study on reordering (ToN,
12/1999) suggests that reordering and congestion are linked (but, I
do not think they analyzed that correlation at the connection
level).

Maybe all that needs stated a bit better.  But, I think the point is
still valid.  (And, you might be right... my point is really that we
don't know.)

> I prefer solutions which induce the possibility of 3 dupacks (or 4
> missing reports for SCTP). 

Well, that is best.  I like limited transmit.  And, you'll note that
this ID is for the case when you don't have new data to send.  But,
you knew that because...

> Hari Balakrishnan's solution of sending zero-byte segments and

So, I'd be interested in hearing from people who understand these
sorts of things... Given that I am going to form up a packet and
send it across a network path, what is the marginal cost of adding
data to that packet?  I.e., what is the delta in effort between a
zero byte packet and a full packet?  (I realize that this is likely
hard to quantify in any sort of general way.  But, is it "a lot more
effort" or "not much more effort" or what?)

My gut says that in the general case we might as well dump data into
the packet.

> Marco Mellia et al.'s solution of breaking segments into smaller
> pieces are two ideas which I think deserve more attention.
> Although these mechanisms may add _some_ load to the network, I
> think more research is needed with these type of solutions.

I agree that more research is needed.  No doubt.

But, it comes down to a question of what is the unit that matters.
Is it the number of bytes I throw into the network or the number of
packets I inject?  (And, yes, I am sure the answer is "both". ;)

I think early retransmit sounds like a fine idea.  Digging a little
deeper into one of my questions of this morning... What sorts of
limitations should we place on the use of ER?  I think a possible
approach is to say that you should use DSACK or Eifel or something
in conjunction with ER to detect the cases when ER retransmitted
spuriously.  And, if you figure that out then you have to stop using
ER.

> threshold is appropriate. It may be worthwhile to investigate the
> use of a mechanism which begins with a conservative threshold, and
> then gets adjusted over time. To start, DSACKs/Eifel/etc may be
> useful for increasing the threshold.

    Ethan Blanton, Mark Allman. On Making TCP More Robust to Packet
    Reordering. ACM Computer Communication Review, 32(1), January
    2002.
    http://roland.grc.nasa.gov/~mallman/papers/tcp-reorder-ccr.ps

    Ethan Blanton, Robert Dimond, Mark Allman. Practices for TCP
    Senders in the Face of Segment Reordering, February
    2003. Internet-Draft draft-blanton-tcp-reordering-00.txt (work
    in progress).

    Ming Zhang, Brad Karp, Sally Floyd, and Larry Peterson.  RR-TCP:
    A Reordering-Robust TCP with DSACK, ICSI Technical Report
    TR-02-006, Berkeley, CA, July 2002.
    http://www.icir.org/bkarp/reordering-TR.ps.gz

I am sure others, too.

allman

---

From: Randall Stewart <[email-masked]>
Date: Tue, 25 Feb 2003 13:09:32 -0600

>>less than 3 isn't appropriate regardless of ownd.
I had this same sort of thought as well.. I just could not
see the connection between ownd < 4...

> this ID is for the case when you don't have new data to send.  But,

Yes, when you have enough data in the pipe things are fine.. its
for these cases where you don't that a problem arises.. in my
recent testing I have seen this A LOT in trailing packets in
my simulated satellite network... you end up always taking
a RTO if its in the last 2 or 3 packets that the drop occurs...
something not all that uncommon when you are looking at
2-6% error rates...surprisingly... I also have seen
this a lot when you approach the peer rwnd limit and
thus stop sending again..

I think in all my recent work almost all the RTO drops
were this form.. rwnd full & drop in last few packets OR
trailing edge of a transfer....

>>Hari Balakrishnan's solution of sending zero-byte segments and
This does not help an SCTP case.. since you are not allowed
to send a data segment with zero bytes... I like using the
DSACK info (since SCTP has it :>) and combine this with
a limit on reducing your limit once for some time say
a RTT (only when you are in this state.. no data to send)...

> My gut says that in the general case we might as well dump data into

Well, I am NOT an expert but I have been digging a bit deeper
into one of the Routers that is in the I-net.. and I don't
really think it makes that much difference if the packet
is 50 bytes or 1500 bytes.. you still have all of the
internal structures you must use in moving the packet through
the router... often times these are optimized to fit a full
MTU depending of course on how the packet is being switched
through the router... sometimes you can get by with smaller
pieces...depending on the type of forwarding that is going
on of course...

It would be worth doing a little lab work to see if you route
N fulls size segments through a network and contrast that with
N small segments.. does it make a huge difference... There will
be some.. but I don't know how much...

Maybe when I get a few cycles (don't hold your breath :-0) I will
set something up...I am interested in knowing this little gem.. for
at least one of the routers that is out in the world :-)

> I agree that more research is needed.  No doubt.
Yep... it still needs to be baked a bit...

> spuriously.  And, if you figure that out then you have to stop using

I like DSACK myself (as I said above :>)

R

-- 
Randall R. Stewart
[email-masked] 815-342-5222 (cell phone)

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Tue, 25 Feb 2003 14:14:29 -0500 (EST)

On Tue, 25 Feb 2003, Mark Allman wrote:

> I think early retransmit sounds like a fine idea.

I don't have a problem with exploring this idea... I was just showing my
preference :-)  Is this draft being pushed as "experimental"?

> Digging a little deeper into one of my questions of this morning...
> What sorts of limitations should we place on the use of ER? I think a
> possible approach is to say that you should use DSACK or Eifel or
> something in conjunction with ER to detect the cases when ER
> retransmitted spuriously.  And, if you figure that out then you have
> to stop using ER.

Yeah, I like this idea.

In the draft, you also mention the possibility of limiting a connection to
only one early rtx. I think that this limitation is too restrictive.
Application-limited connections may need multiple early rtxs. I think that
if early rtxs are done at all, then they should be allowed until the
sender detects a problem in doing so... possibly using the approach you
describe above with DSACK/Eifel.

~armando

0--                                                  --0

---

From: Urtzi Ayesta <[email-masked]>
Date: Tue, 25 Feb 2003 20:26:51 +0100

Hello all,

>increasing the threshold.
That would be ideal, but short connections don't have time to determine
which dupack is appropriate and experiencing a timeout has a dramatic 
impact
on their transfer time. Early retransmission may reduce the timeout 
incidence
at the cost of unnecessary retransmissions.
To limit the number of unnecessary retransmission one could think of using
ER at most once (as suggested in the appendix). This would still permit
short connections to recover more effectively from a loss.

>isn't appropriate regardless of ownd.
it matters, if you only reduce the number of duplicate ACKS when ownd < 
4, then
the result found by Pax97 is not valid anymore. One would expect a 
smaller reduction
on the ratio.

>research is needed with these type of solutions.
Solutions to induce the reception 3 dupacks may increase the number of 
segments
sistematically, whereas ER proposes to retransmit early only in situations
where the sender will inevitably timeout if a packet has been indeed lost.

---

From: Urtzi Ayesta <[email-masked]>
Date: Tue, 25 Feb 2003 20:30:01 +0100

> trailing edge of a transfer.... 

In fact, this particular scenario is one of the motivations for ER.

urtzi

---

From: Mark Allman <[email-masked]>
Date: Tue, 25 Feb 2003 14:34:06 -0500

> I don't have a problem with exploring this idea... I was just
> showing my preference :-) 

And, I do not think you are alone.  When we coupled ER and limited
transmit we got the same sort of reaction---i.e., that limited
transmit seemed nice and should go forward, but there was some
reservation about ER.

> Is this draft being pushed as "experimental"?

??

Without thinking about it or consulting with anyone (ADs,
co-authors, etc.) I'd say that experimental sounds about right for
the current state.  Although, if we mandated use of some spurious
rexmt detection to turn off ER or some some limit (like
once/connection) then I think it should be PS.  What harm would
there be in practice?  

(The harm would be 1 bogus retransmit / connection.  If the real
world caused that to happen to every connection then I'd step back
and say that it wasn't ready.  But, I doubt that is the case.)

Thanks!

allman

---

From: Urtzi Ayesta <[email-masked]>
Date: Tue, 25 Feb 2003 20:33:42 +0100

>describe above with DSACK/Eifel.
I agree. This sounds as a reasonable thing to do. There is no reason for 
long-lived
connections to stop using ER if packets were indeed lost.

urtzi

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Tue, 25 Feb 2003 14:35:45 -0500 (EST)

On Tue, 25 Feb 2003, Urtzi Ayesta wrote:

> segments sistematically, whereas ER proposes to retransmit early only
> in situations where the sender will inevitably timeout if a packet has
> been indeed lost.

Yes, this point is valid... agreed.

~armando

0--                                                  --0

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 28 Feb 2003 14:15:33 +0100

a few comments to the draft:

- First of all, I think, it's nice work, and I hope that we can move 
forward with this soon.

- section 1:
Do you really need to make a special case for (4) (connections winding 
down)? Isn't this just a special case of (1) (application limited connections)?

- You talk about [All00] and the many short http transfers. I don't 
question that result, but I think that you could maybe put it a bit more 
into perspective. From our recent measurements, we find that http 1.1 and 
especially pipelining are becoming increasingly popular. Thus, http 
transfers should be getting longer on average these days.

- Concerning the solutions mentioned in the appendix. How about if the 
sender maintained a ratio of ER-based-spurious-retransmits over 
total-number-of-transmitted-segments, assuming something like 
Eifel/DSACK/FRTO-based detection. Then we could say that this ratio MUST 
not be larger than some threshold, say 2 percent. As soon as the ratio goes 
higher, we turn off ER, and turn it on again as soon as the ratio goes 
below the threshold again.
	We do something similar with a new retransmit timer we are working on. It 
maintains the ratio of timeout-based-spurious-retransmits over 
total-number-of-transmitted-segments. We use that ratio to dynamically 
adapt the conservativeness of the new retransmit timer.
	In general, I think that we could allow TCP some redundancy in the form of 
occasional spurious retransmits (e.g., 5 percent in total), when on the 
other hand the avt people are allowed to define FEC for their streams.

///Reiner

---

From: Sourabh Ladha <[email-masked]>
Date: Fri, 28 Feb 2003 09:16:51 -0500 (EST)

Greetings,

> down)? Isn't this just a special case of (1) (application limited connections)?

IMO (4) may be called a special case of (1). But the idea that point
makes to state is that one of the things ER is specifically meant for
is the trail of the connection, at the last phase of the window and so the
emphasis.

> below the threshold again.

Correct. Infact there was exactly a similar discussion offline to include
a similar approach in the appendix for the next ID update by which time
we would have researched this and other solutions further.

Sourabh

---

From: Urtzi Ayesta <[email-masked]>
Date: Fri, 28 Feb 2003 15:55:57 +0100

Hi all

> down)? Isn't this just a special case of (1) (application limited 

Maybe we should modify a bit the approach of this part. Indeed the 
problems of points (2) and (3)
are handled by Limited Transmit.
It is not exactly having a small congestion window what makes connections
prone to timeout, but the addition of having small congestion window and 
not to have more "new" data to send.
In the of case of small congestion window and more "new" data,  Limited 
Tramited would take over and
eventually induce the reception of three duplicate ACKs.

For ER we had in mind two main motivations. The first case
corresponds to long lived interactive applications which send data in 
small bursts, such as telnet
and network games. The second case correspond to the fact any loss of 
the last three packets
would provoke a timeout, which is especially harmful for short connections.

> Eifel/DSACK/FRTO-based detection. Then we could say that this ratio 
> MUST not be larger than some threshold, say 2 percent. As soon as the 
> ratio goes higher, we turn off ER, and turn it on again as soon as the 
> ratio goes below the threshold again    We do something similar with a 
> new retransmit timer we are working on. It maintains the ratio of 
> timeout-based-spurious-retransmits over 
>     In general, I think that we could allow TCP some redundancy in the 
> form of occasional spurious retransmits (e.g., 5 percent in total), 
> when on the other hand the avt people are allowed to define FEC for 
> their streams.
>
This is clearly a point which needs further discussion.
Maybe a higher value for this threshold could be considered If we take 
into consideration  that the
overload  introduced by ER on average would be equal to
Porcentage_Packet_reordering x Ratio_spurios-rtx_Total-rtx.

regards,
Urtzi