Subject: [tcpm] Tuning TCP parameters for the 21st century

From: Jerry Chu <[email-masked]>
Date: Mon, 13 Jul 2009 16:19:07 -0700

Sorry I don't have the I-D ready for submission yet (and the deadline
has passed anyway) so I'll try to describe what we are up to below.
I'll have more data to present in Stockholm.

At Google we have embarked on a mission to make the web faster, not
just for services provided by Google, but for every web user. We started
with TCP because TCP performance has always been a key component of
the end2end web performance. There are a number of default TCP parameter
settings, that, although conservative, have served us well over the
years. We believe the time has come to tune some of the parameters to
get more speed out of a much faster Internet than 10-20 years ago. The
current list includes:

Lowering initRTO
Increasing initcwnd
Lowering minRTO
Lowering delayed ack timer value

I'll start with Lowering initRTO.

RFC1122 contains the following paragraph:

The following values SHOULD be used to initialize the
estimation parameters for a new connection:

(a)  RTT = 0 seconds.

(b)  RTO = 3 seconds.  (The smoothed variance is to be
initialized to the value that will result in this RTO).

The "3secs SHOULD" is reaffirmed in RFC2988.

>From our own measurement of world wide RTT distribution to Google servers
we believe 3secs is too conservative, and like to propose it to be reduced
to 1sec.

Why does it matter?

We have seen SYN-ACK retransmission rates upto a few percentage points to
some of our servers. We also have indirect data showing the SYN (client
side) retransmission to be non-negligible (~1.42% worldwide). At a rate >
1% a large RTO value can have a significant negative impact on the average
end2end latency, hence the user experience. This is especially true for
short connections, including much of the web traffic.

What's the downside?

For those users behind a slow (e.g., dialup, wireless) link, the RTT may
still go up to > 1 sec. We believe a small amount of supriously
retransmitted SYN/SYN-ACK packets should not be a cause for concern (e.g.,
inducing more congestion,...) In some rare case the TCP performance may be
negatively affected by false congestion backoff, resulted from dupacks
caused by multiple spuriously retransmitted SYN/SYN-ACK packets. We believe
there are techniques to detect and mitigate these cases.

I'd like to hear feedback from this list on the feasibility of reducing
initRTO. For some other items (e.g., increasing IW/RW...) unfortunately I
don't have data ready to share yet but if you have an opinion on them I'd
love to hear it too.

Thanks,

Jerry

On Mon, Jul 13, 2009 at 6:54 AM, Eddy, Wesley M. (GRC-MS00)[Verizon]
<[email-masked]> wrote:
>
> I've uploaded a draft TCPM agenda for IETF 75 at:
> http://www.ietf.org/proceedings/09jul/agenda/tcpm.txt
>
> I don't recall seeing an I-D or mail list thread for
> the topic Jerry Chu wants to discuss (lowering the
> initial RTO), so if he can give the mail list a bit
> of a description of his proposal that would be
> helpful.
>
> ---------------------------
> Wes Eddy
> Network & Systems Architect
> Verizon FNS / NASA GRC
> Office: (216) 433-6682
> ---------------------------
>

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Jul 2009 11:46:54 +0200

> short connections, including much of the web traffic.

For short web traffic I'd assume many of the connections go to a server 
with which the client has recently had a tcp connection.

What would be the pros and cons of using the cached rtt measurements 
from previous connections for the SYN?

    Erik

---

From: Joe Touch <[email-masked]>
Date: Tue, 14 Jul 2009 07:15:37 -0700

Erik Nordmark wrote:
> from previous connections for the SYN

You can use more than cached RTT; the technique and some other cacheable
items are described in RFC2140.

The pro is more rapid convergence to an accurate RTT; the con is that
you're using a potentially invalid RTT, but then that's what you do when
you start without knowing the RTT at all anyway.

It has also been implemented in Linux; see RFC4614.

Joe

---

From: Jerry Chu <[email-masked]>
Date: Tue, 14 Jul 2009 11:55:57 -0700

Hi Erik,

It's good to hear from you!

On Tue, Jul 14, 2009 at 2:46 AM, Erik Nordmark<[email-masked]> wrote:
> For short web traffic I'd assume many of the connections go to a server with
> which the client has recently had a tcp connection.
>
> What would be the pros and cons of using the cached rtt measurements from
> previous connections for the SYN?

Yes this is one of the things we've experiemented with. How effective the cache
will depend on how much cache hit and the numbers for us were not very good.
Also Linux dst cache has some implementation/performance issues.

In order to increase the effectiveness of the cache, we're experiementing with a
cache based on /24 (or some other prefix length) rather than
individual dest IP addr.

Note that most likely whatever scheme that may work for the server
side won't work
for the client side but we'd like to see the client side (SYN) to
speed up as well,
hence the proposal to reduce initRTO.

Hope to see you at Stockholm!

Jerry

---

From: Joe Touch <[email-masked]>
Date: Tue, 14 Jul 2009 13:00:16 -0700

...
> Yes we are very aware of your proposal. I think the most effective one to speed
> up short connections is the snd_cwnd reuse, but unfortunately it's also the most
> dicey due to cwnd's highly temporal nature. Is this why snd_cwnd reuse was not
> implemented per rfc2140? Any insight and suggestion will be much appreciated.

We didn't distribute our implementations; the Linux code was developed
separately. We did do some tests using predictive SND_CWND learning.
There are two parts; one is "how fast would a connection speed up if
guessing were perfect", and the other is "how close to that perfect goal
can be achieved using basic prediction".

Granted, our web server didn't have your traffic, but we found that the
impact of SND_CWND was small, and limited to only a small subset of
connections. Connections too short don't benefit from a large window.
Connections too long have little benefit from increasing startup behavior.

(see the tech report at http://www.isi.edu/aln)

> Yes Linux stack maintains a "destination cache" of ssthresh and RTT on
> a per dest IP address basis. It doesn't currently use snd_cwnd, probably
> out of the same concerned mentioned above?

Lack of benefit is also an issue.

> Also it is very conservative
> hence won't use the cached RTT value unless the timestamp option is
> on.
> 
> Also the dst cache is only consulted after 3WHS. So for SYN/SYN-ACK
> the initRTO is still set to 3secs (don't know why).

If you spin the initRTO down too far, you end up resending the SYN
needlessly, no?

Joe

---

From: Jerry Chu <[email-masked]>
Date: Tue, 14 Jul 2009 12:41:42 -0700

On Tue, Jul 14, 2009 at 7:15 AM, Joe Touch<[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>
> Erik Nordmark wrote:
>> Jerry Chu wrote:
>>

Yes Linux stack maintains a "destination cache" of ssthresh and RTT on
a per dest IP address basis. It doesn't currently use snd_cwnd, probably
out of the same concerned mentioned above? Also it is very conservative
hence won't use the cached RTT value unless the timestamp option is
on.

Jerry

>
> Joe
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (MingW32)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAkpckwkACgkQE5f5cImnZruYrQCgkCe/wm7W4F78Iy9K5gEcMtj5
> xekAoMbbvAXZA230zsKCxsdy3toZA+1N
> =o0dt
> -----END PGP SIGNATURE-----
>

---

From: Jerry Chu <[email-masked]>
Date: Tue, 14 Jul 2009 15:32:20 -0700

> Connections too long have little benefit from increasing startup behavior.

Hmm, your conclusion seems a bit counter-intuitive - for a typical web object
of 5-8 pkts in size, starting with an initcwnd of 6, e.g., from the cache will
require only half of the round trips to complete the http transaction compared
to initcwnd = 3.

> Lack of benefit is also an issue.

See above. I thought this should be the one that will give the largest beneift
(in terms of latency reduction) for the web traffic, if done (i.e.,
predicted) correctly.

> If you spin the initRTO down too far, you end up resending the SYN

Correct so there is a fine line to walk. But if > 98% of all TCP connections
experience RTT << 1 sec, it just seems too conservative to have a global
initRTO == 3secs just to avoid spurious retransmission in the < 2% category.

Jerry

> iEYEARECAAYFAkpc49AACgkQE5f5cImnZruF5QCfc5BRj9np2yjizDIqOa+i09bT
> LsQAoMBPrr2dYErruJc0ED7s2hfCQztE
> =uouq

---

From: Joe Touch <[email-masked]>
Date: Tue, 14 Jul 2009 16:02:39 -0700

...
> require only half of the round trips to complete the http transaction compared

First, you get to send 4K or 4 packets (whichever is smaller) at the
start of a connection anyway. Second, RTT is only a fraction of the
overall delays experienced by a message. Finally, connections already
eat 2 RTTs before you do anything to get a response, due to the SYN
handshake followed by the request-response of HTTP. You might be eating
a single RTT off of a 3-4 RTT exchange. Your RTTs may go down by 30-50%,
but since they're not 100% of your delay, you end up benefitting only
around 20% or so.

Larger messages benefit as you open the window to burst the whole thing
out. Here's a back of the envelope:

# packets	was RTTs:	is RTTs:	benefit
	4	2		2		0%
 	10 	3		2		33%
	19	4		2		50%
	32	5		2		60%
	52	6		2		67%
	82	7		2		71%

Note though that at some point your SND_CWND will be opened only as far
as the path allows, at which point sending more packets just takes more
RTTs, so you start to lose. 90% of our max CWNDs were below 9K, which
means we only saw benefits in the 20-30% range (i.e., the first two rows
above). Sure, if you see CWNDs much larger, you might benefit from
reusing old values...
	
> (in terms of latency reduction) for the web traffic, if done (i.e.,

It would if most connections's max CWND was larger than 10, and if most
connections sent more than 20 packets, but neither was the case for us.

> initRTO == 3secs just to avoid spurious retransmission in the < 2% category.

It doesn't matter much if 99.99% of connections wouldn't benefit from
having the initRTO go off earlier anyway. That's the tradeoff. Don't
know if it helps your case, though.

Joe

---

From: Michael Scharf <[email-masked]>
Date: Wed, 15 Jul 2009 11:15:17 +0200

> # packets	was RTTs:	is RTTs:	benefit

A large initial SND_CWND might not result in such a large benefit if
the receiver still announces a small receive window (e. g., the Linux
stack initially announces a receive window of about 6K only). This
issue is documented in an (expired) ID:

  http://tools.ietf.org/html/draft-scharf-tcpm-flow-control-quick-start-00

An example for a limitation by the receive window can also be seen on
slide 19 of

  http://www.ietf.org/proceedings/08nov/slides/iccrg-2.pdf

Note that, at least in case of Linux, it is possible to mitigate this
limitation by an ugly hack: The sender could ignore the announced
receive window during the first RTT of the Slow-Start and
optimistically send more data. As the receiver exponentially opens the
receive window, the received packets are always within the current
receive window - if the receiver does not run out of memory. But of
course this hack violates RFC 793.

BTW: My experiments with different fast startup schemes (with and
without rate pacing) also show that the absolute benefit of a faster
startup is small for many typical Internet workloads. Yet,
applications that frequently transfer mid-sized amounts of data can
indeed benefit. And since only few applications actually use a large
initial SND_CWND, the risk of a moderate increase of the initial
window appears to be rather small. As also mentioned in my ICCRG
presentation, the "Jump-Start" idea of M. Allman et al. seems to have
a quite reasonable performance in many scenarios.

Unfortunately, I cannot back these statements by large-scale
experimental data so far. But if someone wanted to perform some
experiments, e. g., with the "Jump-Start" scheme, I could provide
corresponding Linux kernel patches.

Michael

---

From: Joe Touch <[email-masked]>
Date: Wed, 15 Jul 2009 07:25:00 -0700

Jerry Chu wrote:
...
>> We're taking one more look at T/TCP as well (probably need to start a different
>> mail thread on T/TCP too).

T/TCP is deprecated due to a fairly large security issue that has not
been solved, AFAIK. It'd be useful to have a solution to that issue
before proceeding with it as an approach.

...
>> The SYN/SYN-ACK retransmission rate we measured turned out to be >> 1%
>> in many cases (a bit surprising to us) hence the benefit.

That points to some other problem going on. As a packet loss rate,
that's quite high and causes problems elsewhere in TCP. It would be
useful to understand where the drops are and why. Retransmitting SYNs to
a busy endpoint whose queue is overflowing doesn't help things, e.g.

Joe

---

From: [email-masked]
Date: Wed, 15 Jul 2009 17:58:10 +0200

> that's quite high and causes problems elsewhere in TCP. It would be

It doesn't have to be a packet loss rate, maybe it was a
per-connection measurement. We also found this to occur
for > 0.5% of connections in our own measurement study:

Dragana Damjanovic, Philipp Gschwandtner, Michael Welzl: "Why is this Web
Page coming up so slow? Investigating the Loss of SYN Packets", IFIP/TC6
NETWORKING 2009, 11-15 May 2009, Aachen, Germany.
http://www.welzl.at/research/publications/networking2009.pdf

> a busy endpoint whose queue is overflowing doesn't help things, e.g.

I understand that now, too (thanks to Lachlan who
explained it to me), and hence apologize for having
been ignorant to this rather obvious issue in the
above paper.

- but what about retransmitting SYN/ACKs faster?
Since the other side already sent a SYN, it probably
isn't overloaded.

Cheers,
Michael

---

From: Joe Touch <[email-masked]>
Date: Wed, 15 Jul 2009 09:19:24 -0700

[email-masked] wrote:
...
> isn't overloaded

That presumes the other side already sent a SYN and it's been received,
and that the SYN/ACK is what's getting lost/delayed/retransmitted.  If
not, that won't help.

First find where things are going wrong empirically ;-)

Joe

---

From: Jerry Chu <[email-masked]>
Date: Tue, 14 Jul 2009 17:43:43 -0700

On Tue, Jul 14, 2009 at 4:02 PM, Joe Touch<[email-masked]> wrote:
> overall delays experienced by a message.

Sure and we are looking at other layers (especially HTTP) for performance
optimization as well.

>Finally, connections already

> # packets       was RTTs:       is RTTs:        benefit

Correct. We are trying to pilot our cache code and will find out our snd_cwnd
distribution, and how much it helps (or hurts if it triggers more pkt drops).

Jerry

> iEYEARECAAYFAkpdDo4ACgkQE5f5cImnZrs3fwCfaOB3Ki+FKf1rrJP3kKfdxV2X
> D68AoKxBh/3C0Bh3MVZ8AniBoen9vuX/
> =X+Od

---

From: Rui Paulo <[email-masked]>
Date: Wed, 15 Jul 2009 18:59:44 +0100

> It has also been implemented in Linux; see RFC4614.

And FreeBSD, BTW.

--
Rui Paulo

---

From: Jerry Chu <[email-masked]>
Date: Wed, 15 Jul 2009 14:20:15 -0700

> before proceeding with it as an approach.

Understood. On the high level it seems to me a nonce/cookie exchanged
over one reqular TCP connection (w/ 3WHS) upfront will always be required
but should be sufficient to cover later T/TCP sessions and address the security
concern? (Oh perhaps the cookie can be passed around by attackers to mount
a DDOS attack?)

> a busy endpoint whose queue is overflowing doesn't help things, e.g.

One set of our data show our TCP pkt rexmit rate ranges from 0.8% - 2.4%
globally. Even at 1% drop rate 3secs is a noticeable bump for the average
latency.

Jerry

> iEYEARECAAYFAkpd5rwACgkQE5f5cImnZrslfgCfVmHxe6fxfD7nCq/S5mn8S0Bt
> mwMAnRZPyVGbsvU9x6G1M+hbbR0AnCGn
> =Kghy

---

From: Jerry Chu <[email-masked]>
Date: Wed, 15 Jul 2009 15:34:19 -0700

>  http://tools.ietf.org/html/draft-scharf-tcpm-flow-control-quick-start-00

Yes I remember Linux stack also "slow starts" the receive window.
The good news is that for us the receiver is on the client side dominated by
the Windows stack, which is probably not sophisticated enough to do this.
(Need double check.)

> a quite reasonable performance in many scenarios.

Thanks for the pointers! This seems very relevant to our on-going struggle
with TCP slow start :-).

> corresponding Linux kernel patches.

We're planning for some experiement in this area too. Will let you know
how it goes.

Jerry

---

From: Joe Touch <[email-masked]>
Date: Wed, 15 Jul 2009 16:50:54 -0700

>> concern? (Oh perhaps the cookie can be passed around by attackers to mount

Yeah - that's the problem. See http://www.mid-way.org/doc/ttcp-sec.txt

Nonces are addressed in Sec 5, and there doesn't appear to be a solution.

Joe

---

From: Michael Welzl <[email-masked]>
Date: Thu, 16 Jul 2009 10:39:49 +0200

> and that the SYN/ACK is what's getting lost/delayed/retransmitted.  If

Right -

> First find where things are going wrong empirically ;-)

We've done that. See, for example, fig. 2 (a) of
http://www.welzl.at/research/publications/networking2009.pdf
(page 7 of the pdf)

Since our goal in this paper was to document general failures
of connection setup, we did not strictly split our results
into the case of lost SYNs or lost SYN/ACKs in it.
Section 3 (end of page 3 / beginning of page 4) explains
how lost SYN/ACKs were incorporated in our measurements.

This paper is based on data produced by a student. The
data are more thoroughly documented in his (alas, German)
bachelor thesis. This document is here:
http://www.welzl.at/research/tools/syn-retransmit/benjamin_kaser_bak1.pdf
and the most relevant information is table 2 on page 47.
(Table 1 is similar, just for SYNs, not SYN/ACKs).

If you look at it, with or without German knowledge
you will be able to see the connection to table 1 in
the paper, where we exchanged columns with lines and
omitted some details - apparently just the crucial
ones  :-(    Anyway, the listed measurements are just
the same, and hence you can read the details in the
paper if you're interested in how we obtained our
data.

Table 2 on page 47 of the bachelor thesis has several
details about duplicate SYN/ACKs that we've seen,
e.g. classified by eventually successful and unsuccessful
connections. As a quick summary, in 3432744 connection
attempts, we have seen 56586 duplicate SYN/ACKs in total
(this is a cumulative number, i.e. 4 SYN/ACKs are counted
as 3). Counting only the occurrence of duplicate SYN/ACKs,
we saw them for 0,55% of the 3432744 connection attempts.
In general, the difference between duplicate SYN/ACK
occurrences and duplicate SYN occurrences is negligible
in our measurements.

As I just looked at the data again, I noticed a mistake:
in the paper, we wrote that the problem only happens for
around 0.5% of the connections, but this is really only
from the SYN table, not the SYN/ACK table in the bachelor
thesis. The SYN/ACK table covers the same measurement sets.
Hence, in total, it seems that we also saw > 1% lost SYNs
*or* SYN/ACKs, which exactly matches what Jerry Chu said.
 
BTW I maintain a small website about the whole thing:
http://www.welzl.at/research/tools/syn-retransmit/index.html

Cheers,
Michael

---

From: Jerry Chu <[email-masked]>
Date: Thu, 16 Jul 2009 11:24:53 -0700

On Thu, Jul 16, 2009 at 2:09 AM, David Malone<[email-masked]> wrote:
>> some of our servers.
> Note, that I've seen Google reported to have unusually SYN-ACK
> retransmission rates in this paper:
>
>        http://www.springerlink.com/content/t033171209815745/
>
> Are Google already doing something unusual with their SYN-ACK
> retransmissions?

I can't access the above link so don't know what the unusual SYN-ACK
retransmission rate is. We are experiementing with using RTT history
on a handful of servers as mentioned before. Otherwise our SYN-ACK
retransmit rate seems pretty much on par with the general pkt retransmit
rate, and can go up to a few percentage in regions like India, China...

Jerry

>        David.

---

From: Jerry Chu <[email-masked]>
Date: Thu, 16 Jul 2009 19:36:23 -0700

> http://www.welzl.at/research/tools/syn-retransmit/index.html

Our overall pkt retransmission rate often goes over 1%. I was
wondering if SYN/SYN-ACK pkts are less likely to be dropped
by some routers due to their smaller size so we collected traces
and computed SYN-ACK retransmissions rate on some servers.
We confirmed it to be consistent with the overall pkt drop rate,
i.e., > 1% often.

FYI,

Jerry

>
> Cheers,
> Michael
>
>
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm
>

---

From: Michael Welzl <[email-masked]>
Date: Fri, 17 Jul 2009 08:30:45 +0200

So, after some data have been mentioned, can we
get back to this question:

> >> > Since the other side already sent a SYN, it probably

?

Cheers,
Michael

---

From: Mark Allman <[email-masked]>
Date: Mon, 27 Jul 2009 15:28:05 -0400

Jerry-

A few random thoughts here ...

> From our own measurement of world wide RTT distribution to Google
> servers we believe 3secs is too conservative, and like to propose it
> to be reduced to 1sect.

I am not at all sure this is a good idea.  I have an easier time
believing the others on your list are perhaps reasonable.  But, this one
seems somewhat dubious to me.  A few things ...

  - The fundamental problem here is that you have *no* information.
    That is, we don't know how long the path is before we have done an
    exchange.  When you start from scratch you have nothing to go on
    except defaults.  So, it seems to me on those grounds alone
    conservativeness is fine.  Because,

  - If it was just an extra small packet or two that got sent out that
    doesn't seem like a Big Deal.  But, once you retransmit the SYN you
    no longer can take an RTT sample from the 3WHS per Karn's algorithm.
    So, if in fact the initial RTO is too short then it isn't just going
    to strobe out an extra packet, but what it means is that it's pretty
    likely that the packets in your initial window---after clumsily
    finishing the 3WHS---will likewise be retransmitted because the RTO
    estimate is low and we did not get the opportunity in the 3WHS to
    take an actual RTT sample to better seed the estimator.  This is RTO
    Hell.

  - At first blush timestamps might help here because if used then we
    don't have to use Karn's algorithm.  But, again, since we are just
    initiating a connection how do we know if the peer is going to use
    timestamps?  If the initiator sends a timestamp option then there is
    a chance that timestamps will be in use and therefore there is a
    chance you'll avoid RTO Hell.  But, there is also a chance you
    won't.  The 3WHS responder (sender of the SYN+ACK) will know if
    timestamps will be in use and therefore could perhaps lower the
    initial RTO (basically, this is the ECNSYN trick).  That doesn't
    seem all that unreasonable to me.

  - Now, if you track information across connections as others have
    noted then, sure.  It seems perfectly acceptable to take the view
    that with high confidence you understand that 1sec (or whatever)
    will be fine for an initial RTO over some path that you have
    transmitted traffic across in the recent past and so then you can
    use that.  In this case, you are picking an initial RTO for a
    connection but not flying completely in the dark.

  - It seems that (per the discussion in today's meeting) a naive
    lowering to 1sec is going to be problematic because we have
    bandwidth-on-demand networks, deep queues in access devices are not
    rare, etc.

In a subsequent email you note:

> Correct so there is a fine line to walk. But if > 98% of all TCP
> connections experience RTT << 1 sec, it just seems too conservative to
> have a global initRTO == 3secs just to avoid spurious retransmission
> in the < 2% category.

I agree that it is a fine line.  But, I think your 98%-vs-2% is far too
glib.  That is, we have to look at how bad we're making it for those 2%.
If we degraded each of those 2% by "a smidge" then who cares.  But, if
we really hose those connections (see second bullet above about RTO
Hell) it doesn't seem like a good tradeoff.  It's useful to remember
that TCP was designed to be general and not optimal.  Certainly we don't
want to unduly penalize most of the traffic (/users) to dogmatically
accommodate every last esoteric situation that might happen to crop up
on the third Tuesday of the 6th month following the most recent blue
moon.  But, we also can err on the other side, too.  I think simple
percentages as you have given are pretty superficial and we'd need to go
beyond that to really decide what line we wanted to walk.

Just my two bits ...

allman

---

From: Jerry Chu <[email-masked]>
Date: Tue, 28 Jul 2009 08:32:02 -0700

Mark,

Thanks for your thoughtful comments. The good news is, I'm pretty much on
the same page as you. The problem has to be real and the solution must be
reasonable with acceptable downside if the latter is unavoidable. From our
applications folks the problem seems very real and the performance
difference is not negligible. So I'll focus more on how to rein in the downside.

>    conservativeness is fine.  Because,

Agreed. The question is, how conservative one needs to be? Can we do
better for the majority and still not sacrificing the ones left behind? If
some cost is unavoidable, will the tradeoff be acceptable?

>    take an actual RTT sample to better seed the estimator.  This is RTO

Understood. I've also had this as one of the bullet points on the cost side
in my slides. But my gut feeling was this problem could be mitigated somehow.
(Guess now I'll need to demonstrate how :-)

>    won't.

So the active open side has retransmitted SYN, assuming initRTO of
1sec, and eventually received a SYN-ACK but the TS option was
denied so no good RTT sample can be taken. It will continue to send
the init data with the initRTO.

If the SYN retransmission has been unnecessary because the initRTO
has been too aggressive, more SYN-ACK will be triggered. Assuming
these dup SYN-ACKs are not lost, could they be used as a hint to the
active open side that the initRTO has been too short, so that the RTO
timer can be reverted back to 3secs immediately, in time to avoid further
RTO hell?

One price to pay in the above scenario compared to the default case
of 3secs is that one could have gotten a good RTT sample of say,
2secs but due to the choice of a more aggressive initRTO of 1sec,
one ends up with a fall-back 3secs again for the data phase so any
loss from there will incur more time (3 vs 2secs) to recover. But the
price seems acceptable, and is incurred only when there is immediate
further loss. At least the dreadful endless spurious retransmission,
which would've been unacceptable, is stopped.

>The 3WHS responder (sender of the SYN+ACK) will know if

Correct, but I'd really like to find a solution for the active open side
because there are other techniques the server side can employ (e.g.,
initialize the initRTO from the RTT history...) as a backup if this one
doesn't fly, but those techniques don't work well on the client side.

>    connection but not flying completely in the dark.

Correct. There is a certain amount of added complexity associated
with the cached RTT idea. As such, it is still nice if this reducing initRTO
proposal can fly, not just to cover the client side but also as a simpler
solution for those servers that can't afford to use the more complex
solution.

>    bandwidth-on-demand networks, deep queues in access devices are not

Yes I heard it, loud and clear :-).

> beyond that to really decide what line we wanted to walk.

Understood. See above.

Jerry

---

From: Mark Allman <[email-masked]>
Date: Tue, 28 Jul 2009 14:35:56 -0400

Jerry-

> If the SYN retransmission has been unnecessary because the initRTO has
> been too aggressive, more SYN-ACK will be triggered. Assuming these
> dup SYN-ACKs are not lost, could they be used as a hint to the active
> open side that the initRTO has been too short, so that the RTO timer
> can be reverted back to 3secs immediately, in time to avoid further
> RTO hell?

So, you're saying that if you send N SYNs (N>1) and you get N SYN+ACKs
then you take that to mean the initRTO was too short.

Yeah, perhaps ... 

Are you suggesting something like this ...

  (1) Use an initRTO of 1sec.

  (2) If the RTO fires and you retransmit the SYN back the RTO to 3sec.
      (And, if necessary you exponential backoff even more.)

  (3) After the 3WHS you will either (a) have a good RTT sample from the
      timestamp option and can therefore set the RTO reasonably or (b)
      you retain the 3sec RTO until you get a good RTT sample.

??

That means that if 1sec is not enough in the 3WHS you have to use 3sec
until you have some idea about the network.  However, you also get a
shot [*one shot*] to retransmit sooner based on the notion that most
RTTs are less than 1sec.  

I think I buy that notion ... that both allows for more aggressiveness
for the common case while also protecting against RTO Hell for the long
path cases.  Is that the right walking of the line?

allman

---

From: Jerry Chu <[email-masked]>
Date: Wed, 29 Jul 2009 07:56:01 -0700

Mark,

> path cases.  Is that the right walking of the line?

I can think of a number of variations. The one-shot 1-sec-initRTO idea you
described above also came through my mind but the drawback is you only
get one-shot even though we know statistically > 98% of connections
have RTT < 1 sec so most likely the continuous use of 1-sec-initRTO will
turn
out to be better. (A counter argument might be one-shot is "good enough",
benefitting > 90% of the cases statistically...) The advantage of it is its
simplicity,
restricting the max # of spurious retransmissions caused by the reduced
initRTO
to 1, and obviously avoiding the RTO hell problem.

A different variation that is slightly more complex but allowing the reduced
initRTO to be used more than one-time (hence potentially providing more
benefit
to those > 98% connections) is to only terminate its use upon the detection
of spurious retransmission. Specifically -

1. initRTO = 1sec
2. if a valid pkt with the SYN bit on is received (so it could be either SYN
or
SYN-ACK) and the following two conditions are met:
  2a. the connection state is neither SYN-SENT nor SYN-RCVD
  2b. RTO == 1sec (or no good RTT sample has been taken)
Simply reset the RTO to 3secs.

On a second look it doesn't seem much more complex, although it may be
slightly more work to analyze its thoroughness (e.g., what if all the dup
SYN/SYN-ACK were lost, or all come back late...) Also it does incur
more spurious pkts for those connections with RTT > 2sec.

What do you think?

Jerry

---

From: Mark Allman <[email-masked]>
Date: Wed, 29 Jul 2009 12:05:58 -0400

> I can think of a number of variations. The one-shot 1-sec-initRTO idea
> you described above also came through my mind but the drawback is you
> only get one-shot even though we know statistically > 98% of
> connections have RTT < 1 sec so most likely the continuous use of
> 1-sec-initRTO will turn out to be better. (A counter argument might be
> one-shot is "good enough", benefitting > 90% of the cases
> statistically...) The advantage of it is its simplicity, restricting
> the max # of spurious retransmissions caused by the reduced initRTO to
> 1, and obviously avoiding the RTO hell problem.

Two responses to "one shot":

(1) Yes, one-shot ought to be enough.  Considering losing the SYN,
    retransmitting it using an initRTO of 1sec and reseting the initRTO
    to 3sec.  Now, if there is actually loss in the first RTT of data
    transmission talking about fine-grained performance (i.e., that we
    can get from using 1sec again instead of 3sec) doesn't make a lot of
    sense because 1sec vs. 3sec doesn't matter because performance is
    going to suck no matter what.  So, why bother with anything terribly
    "smart" here?

(2) Using the numbers on your slides it seems to me that the fraction of
    hosts with an RTT of > 1sec is roughly the same as the SYN
    retransmit rate (at an RTT of 3sec, I assume).  To me that says that
    if you use an initRTO of 1sec and then retransmit then the reason
    for that retransmit is just as likely to be loss as it is to be a
    long path.  So, your approach of preferring more than one-shot
    assumes loss.  But, I don't see the measurements you gave as
    suggesting that is the right approach.  The notion of going back to
    3sec just sort of punts.  I.e., the notion is that we have hit a
    situation whereby we don't know what is going on and so let's not
    dogmatically try to push forward, but let's throw up our hands and
    try to do things that ultimately will figure out what is going on.
    And, further, one mistake does not propagate.

So, for me one-shot is just about the right balance here.  Any more than
that we're getting into the corner of a corner case and further in that
corner the empirical evidence is not suggestive of a clear path.  So,
let's just do something that will allow the protocol to get a handle on
things as they are in the specific situation and not try to make guesses
that propagate further.

allman

---

From: <[email-masked]>
Date: Thu, 30 Jul 2009 09:27:55 +0100

It's necessary to disambiguate which ACK is for which SYN - 
i.e. if you have a _very_ long-delay path, you might send out
three SYNs before an ACK to the first SYN comes in. But it appears
at the time to be an ACK to the third SYN, with other
responses lost in transit. So SYN timestamps really are
necessary to disambiguate in this situation. I can see
a cascading sequence where the first ACK comes in just after say
the fifth SYN goes out, and it's immediately necessary to
bump the RTO up to tens of seconds.

related discussion of this is in our TCP Protocol Radius paper:
http://personal.ee.surrey.ac.uk/Personal/L.Wood/publications/index.html#protocol-radius
esp. Fig 2.

L.

<http://www.ee.surrey.ac.uk/Personal/L.Wood/><[email-masked]>

-----Original Message-----
From: [email-masked] on behalf of Mark Allman
Sent: Tue 2009-07-28 19:35
To: Jerry Chu
Cc: [email-masked]
Subject: Re: [tcpm] initial RTO (was Re: Tuning TCP parameters for the 21st century)

Jerry-

Yeah, perhaps ... 

??

allman

---

From: Mark Allman <[email-masked]>
Date: Thu, 30 Jul 2009 07:41:19 -0400

> It's necessary to disambiguate which ACK is for which SYN - i.e. if
> you have a _very_ long-delay path, you might send out three SYNs
> before an ACK to the first SYN comes in. But it appears at the time to
> be an ACK to the third SYN, with other responses lost in transit. So
> SYN timestamps really are necessary to disambiguate in this
> situation. I can see a cascading sequence where the first ACK comes in
> just after say the fifth SYN goes out, and it's immediately necessary
> to bump the RTO up to tens of seconds.

Sure.

I guess Jerry and I are talking about the case where with exceedingly
high probability the RTT is covered by the current 3sec RTO and the vast
majority of the connections have an RTT of less than 1sec.  (So, say,
99.99999% < 3sec and 98% < 1sec.)  So, how then do we use 1sec for the
common case, but still reasonably accommodate the fraction that have
RTTs > 1sec but < 3sec?

Would it be nice to keep pushing and accommodate connections with even
larger RTTs?  Ideally, yeah.  But, I am not sure imposing timestamps or
other mechanisms on everyone to deal with that case is useful.  At some
point you have to engineer your edge case for what it is.

allman

---

From: <[email-masked]>
Date: Thu, 30 Jul 2009 12:51:40 +0100

SYN timestamps benefit _all_ cases...

-----Original Message-----
From: Mark Allman [mailto:[email-masked]]
Sent: Thu 2009-07-30 12:41
To: Wood L Dr (Electronic Eng)
Cc: [email-masked]; [email-masked]
Subject: Re: [tcpm] initial RTO (was Re: Tuning TCP parameters for the 21st century) 

Sure.

allman

---

From: Jerry Chu <[email-masked]>
Date: Thu, 30 Jul 2009 09:38:05 -0700

>    going to suck no matter what.  So, why bother with anything terribly

Guess we have some disagreement here and it's not surprise - although
we seem to agree upon the general principles - keep it simple, focus on
the main benefit not the corner cases, but both principles involve some
degree of subjective calls. E.g., the exit condition to initRTO of 1sec
suggested in my previous email doesn't seem all that complex to me.
It only involves a simple check of dupack (or dup SYN/SYN-ACK).

Also I'm not sure why performance has to suck just because a connection
experience early (e.g., SYN/SYN-ACK) loss? I don't remember if TCP
spec requires a connection to go into congestion avoidance mode after
SYN/SYN-ACK loss? Even if so, for short lived connections with small
amount of data (e.g., HTTP/TCP), a speedy recovery from a more optimal
RTO value does still seem matter. Also the reason for a possible speedy
recovery for a loss event AFTER 3WHS seems equally valid as the one
for 3WHS, assuming these loss events are stochastically independent
of each other..,

>    And, further, one mistake does not propagate.

Again I agree with your statements in general but I just feel one-shot
is a little weak, shy of being "good enough". How about allowing N
shots where N is some TBD (> 1) number? I suspect N=2 may satisfy
the "good enough" criterion, taking cue from MacOS (see my slides on
MacOS's repeated 1sec RTO 5 times...) There may be a couple of
different flavors of allowing N shots, either consecutive-only or not but
that's details.

> things as they are in the specific situation and not try to make guesses

The N-shot solution doesn't add any complexity (just log(N) more bits to
the TCP structure) and seems a strong enough dose for those HTTP
connections suffering the dreadful 3sec pause.

Jerry

---

From: Jerry Chu <[email-masked]>
Date: Thu, 30 Jul 2009 09:45:58 -0700

> bump the RTO up to tens of seconds.

One solution I proposed only requires the detection of  sprurious
retransmission so it doesn't need to match ACKs with their SYNs,
as long as any dupack is received...

Jerry

---

From: Mark Allman <[email-masked]>
Date: Thu, 30 Jul 2009 15:22:27 -0400

Jerry-

Let's put some (rough; based on your slides) numbers to things here ... 

  + With an initRTO of 3sec your data suggests that 98% of the
    connections complete the 3WHS without retransmitting.  So, in 2% of
    the connections we in fact lose a SYN.

  + Also, you note that something like 2% of the connections have an RTT
    longer than 1sec.  (And, I am making the assumption that is really >
    1sec and < 3sec.)

  + So, with an initRTO of 1sec we'd expect to see 2% of the connections
    experience loss, 2% of the connections have a long RTT and
    spuriously retransmit which leaves 96% of the connections Just
    Working.  (All in rough terms.)

  + Forget the 96%... they are good to go.  They got an RTT sample in
    the 3WHS and so presumably are working fine and no longer have to
    worry about the initRTO.

  + The 2% of the connections that experienced loss will have each saved
    2sec in the 3WHS by using an initRTO of 1sec vs. 3sec.  So, if we
    care about X connections that's an aggregate savings of X*0.02*2sec
    when using an initRTO of 1sec versus using an initRTO of 3sec (which
    yields 0sec of savings).

  + The connections that experienced loss will send data in the first
    RTT (say) and experience another 2% loss rate.  If we have a try-2
    approach and again use an initRTO of 1sec then this would save each
    of these connections 2sec over my notion of reverting the initRTO to
    3sec.  In the aggregate the savings here is X*0.0*0.02*2sec.

  + So, now we have saved X*0.02*2sec + X*0.02*0.02*2sec with a try-2
    approach vs. X*0.02*2sec with a try-1 approach.  For X=10K
    connections that is a difference of 8sec in the aggregate (400sec
    with try-1 vs. 408sec with try-2)---or, less than 1msec per
    connection on average if you'd like to do it that way.

  + Then there are the spurious RTOs caused by lowering the initRTO to
    1sec.  We'll have 2% of those in the 3WHS.  The problem is that
    keeping the initRTO at 1sec **ensures** a spurious retransmit in the
    first RTT of data transfer, too.  So, the cwnd will be reduced to an
    MSS, no RTT sample will be taken again, linear increase will be
    forced upon the connection, etc.

  + (Note, I am ignoring connections that use timestamps.  Connections
    that successfully use timestamps will have an RTT sample from the
    3WHS and therefore we don't have to worry about the initRTO
    further.) 

To me the tradeoff is clearly in favor of try-1.  For the advantage of a
*tiny* time savings to the 0.02*0.02 of connections that experience loss
in both the 3WHS and the initial window of data (i.e., what try-2 would
help) you pay by dooming 0.02 of the connections (that now work fine,
BTW) to no exponential ramp up.  That might be a tradeoff you are
personally willing to make---i.e., to sacrifice one type of connection
in favor of another.  But, I don't see that as a good tradeoff for the
standards to make.

Also, note, your scheme of counting SYNs is not overly complicated and
does not have overly onerous state requirements.  I didn't mean to
indicate either of those.  However, it isn't terribly robust either and
I am not ultimately sure how it'd play out.  So, say a connection has a
2sec RTT (works with others, too):
  
  0.0 xmit SYN
  1.0 RTO (==1sec), rexmit SYN
  2.0 rec SYN+ACK (from original transmit) / send ACK / send DATA
  3.0 resend DATA
  3.0 rec SYN+ACK (from retransmit)

Those last two events represent a race condition.  I.e., in this case,
we hope we get the SYN+ACK before we resend the data because then we can
use your scheme to revert to an initRTO of 3sec.  But, we might get it
in the order given above.  And, we might not get that packet at all.
So, it might work and it might not work.  But, the cost of not using it
(possibly saving X*0.02*0.02*2sec) is so small that it seems like
needless complication to me.

Now, there is something you can do here... If you wanted to take the
reception of the SYN+ACK and compare that to the *earliest* SYN
transmission and use that as an RTT sample and then use that to seed the
RTO estimator then fine.  I.e., in this case that'd (correctly) see an
RTT of 2sec.  And, if the original SYN was lost then the returning
SYN+ACK would yield an RTT sample of 3sec.  I.e., using this scheme
might overestimate the RTT, but you won't underestimate it.  If that is
less than 3sec you'd be better off for the first window of data and
you'd be protected against spurious retransmits (to the best of the
standard RTO estimator's abilities) by using a conservative RTT sample.

allman