On Monday, October 23, 2006 David Barrett wrote: > I like Mill's nonlinear filter, but I'll need to do more research > on it.
Right. Keep in mind that Mills filter, among other things, also
tends to increase the average estimate; to illustrate that, attached
is the sample run of normal RTT estimate and Mills' estimate with the
values he used in RFC 889: "After a number of trials I concluded that
values of F1 = 15/16 and F2 = 3/4 (with G = 2) gave the best all-
around performance." (this "F" is the "a" value in the chart title)
The chart shows the averaging results of both filters for a
random RTT in the range 0-10 with a uniform distribution. This is,
of course, a simplification, but it does show the expected effect
- Mills' estimate is consistently higher than the "normal" one with
the same base alpha (or F1, in RFC 889 terms) value.
Even more interesting are the plots of estimate*G (with G=2,
as in RFC 889), that are plotted on the same chart. As you can see,
several RTT samples exceed this value for a "normal" 15/16 estimate,
which basically means that TCP would have about five retransmissions
on that interval (if it would really encounter such a nutty RTT
variation, of course). Mills' estimate, on the contrary, exceeds
all the RTT values in the sequence, so no retransmissions would be
necessary.
However, this appears to be simply the result of the higher
estimate value provided by Mills - the nonlinear filtering as such
does not seem to have any special influence on this result. As a
matter of fact, simply increasing G (retransmission factor threshold)
would have pretty much the same effect. It is nteresting that Mills
himself did not found the increase of G to have any positive effect
for his data samples; I'm not entirely sure why this would be the
case. Maybe that was because real-life RTTs are not really random
(much less have a uniform distribution), as in the attached chart,
but are correlated (large RTTs tend to be followed by the large
RTTs), and non-linear filtering would really have some benefits
independent of the increased retransmission threshold.
So I'm providing this chart not to say that Mills' filtering
does not have any positive effects aside from the simple RTT estimate
increase, but rather just to give a simple visual example of what is
happening when Mills' filter is used.
Best wishes -
S.Osokine.
23 Oct 2006.
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of David Barrett
Sent: Monday, October 23, 2006 12:58 AM
To: 'theory and practice of decentralized computer networks'
Subject: RE: [p2p-hackers] TCP over UDP "magic number" questions
Wow, 4614 is a godsend. 2988 is also particularly useful. Ok, so I think
I'll start with a basic NewReno implementation with Karn's algorithm for RTT
measurement (with fixed x2 backoff) and Van Jacobon's technique of SRTT
calculation. I like Mill's nonlinear filter, but I'll need to do more
research on it. Nagle is out. Hopefully this'll get me a good start and I
can get crazy after that. Thanks for all your help!
-david
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Spencer Dawkins
Sent: Saturday, October 21, 2006 5:24 PM
To: theory and practice of decentralized computer networks
Subject: Re: [p2p-hackers] TCP over UDP "magic number" questions
If you're trying to figure out what TCP is really, you might also look at
http://www.ietf.org/rfc/rfc4614.txt, which is the IETF's best shot at hacking
through the 100 or so RFCs that talk about TCP.
I note that RFC 889 doesn't seem to be listed. I think you can ignore it
(unless the functionality got picked up in RFC 1122, which tried to capture
the working lore several years after TCP was redesigned for congestion
avoidance, etc.).
And it's also worth mentioning that TCP will WORK, for some value of "work",
with a lot of simplifying assumptions. I'm not sure Nagle matters for
anything except Telnet/FTP control channel-style communication, and you may
not even know anyone who uses these protocols anymore - they are *so*
last-century :-). There just aren't that many protocols that rely on
server-end echos any more, and that's the problem Nagle was solving.
Thanks,
Spencer
----- Original Message -----
From: Michael Parker
To: theory and practice of decentralized computer networks
Sent: Saturday, October 21, 2006 6:16 PM
Subject: Re: [p2p-hackers] TCP over UDP "magic number" questions
I think Mill's nonlinear filter was a proposed modification to TCP as
described in RFC 889 that never made it. I suspect Van Jacobson's simple
linear filter won out either because it was easy to implement or it produced
better results in trials. (But it could be worth grepping for Mills in the
Linux source code just to make sure.) Don't forget, none of these papers are
very current -- both Nagle's and Van Jacobson's papers appeared in the 1987
proceedings of SIGCOMM. So if you don't see it in the latest RFCs (e.g.,
2581), it probably didn't stand up to the test of time.
As for Karn's algorithm, I think some BSD flavors go through empirically
determined backoffs. I'm pretty sure the book TCP/IP Illustrated Volume 2
spells them out (indeed, all of the TCP/IP implementation) in their gory
details. But just to get it running, I don't think doubling is a bad solution
at all, as unless your connection is really hosed you won't be stepping
through that many backoffs anyway.
In a file transfer scenario, you can probably do without Nagle's algorithm.
It's more useful in an interactive environment like a terminal, where it
drastically increases the ratio of payload to header bytes. (Although some
programs, to appear more responsive when echoing from a server, will turn it
off through the TCP_NODELAY socket option.)
- Mike
rtt.GIF
Description: rtt.GIF
_______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
