Re: [p2p-hackers] TCP over UDP "magic number" questions

Sat, 21 Oct 2006 16:17:18 -0700

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


On Oct 21, 2006, at 2:56 PM, David Barrett wrote:

Fantastic references.  So if I understand correctly:

 

Mill’s nonlinear filter

Use a smaller ALPHA when the new sample (RTT) is greater than the current estimate (SRTT) to more quickly adapt to sudden increases in network delay (SRTT = ALPHA*SRTT * (1-ALPHA)*RTT):

1)       What ALPHA should be used if RTT > SRTT? (0.875, as by original TCP spec?  Or less?)

2)       What ALPHA should be used if RTT < SRTT? (0.9?  0.925? 0.950?)

 

Karn’s algorithm

Calcuate RTT only using clean samples, and back off the RTO to handle the case where a connection suddenly slows (otherwise you’ll timeout everything forever and never get another valid ACK on which you can measure RTT).

-          Initialize RTO to RTO_SET on each send (versus recomputing based on SRTT).

-          Only update SRTT and RTO_SET if the RTT sample isn’t dirtied by retransmits.

-          On timeout, back off both RTO an RTO_SET

3)       How much do you back off – just double?

 

Van Jacobson

Calculate RTO using the variance of RTT samples, instead of a fixed BETA value.

-          SRTT = SRTT + GAIN0*( RTT - SRTT )

-          VAR = VAR + GAIN1*( |RTT – SRTT| - VAR )

-          RTO = SRTT + 4*VAR

4)       Jacobson recommends 0.125 and 0.25 for GAIN0 and GAIN1, respectively (conveniently reducing the divide to a shift).  However, doesn’t at least GAIN0 need to be variable based on Mill’s nonlinear filter?

 

Nagle Algorithm

If unconfirmed data in the pipe, coalesce small packets into big to reduce overhead by buffering until you have at least MSS bytes.

5)       In a file-transfer setting where all packets are basically the same size (ie, MSS), it’s safe to ignore the Nagle algorithm, correct?

 

Thanks for the very specific help.

 

-david

 

From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Michael Parker
Sent: Saturday, October 21, 2006 11:12 AM
To: theory and practice of decentralized computer networks
Subject: Re: [p2p-hackers] TCP over UDP "magic number" questions

 

Hi David,

 

A while ago, I attempted the same thing -- writing a protocol that attempted to mimc TCP over UDP (since the latter is a lot easier to get through firewalls with). I didn't finish the implementation (had to focus on finishing up my Master's thesis instead -- oops), but I read a lot of the literature. From what I could tell, when you can't figure out what a parameter value should be, go with RFC 2581 -- I think it does a good job of giving you the values that will squeeze out most of the performance of your protocol. The other two algorithms you must implement or face serious performance degradation are Karn's algorithm (see "Estimating Round-Trip Times in Reliable Transport Protocols" by Karn & Partridge) and Nagle's algorithm (RFC 896). The only RFC I sought to implement as an optimization was limited retransmit (which is an easy change), or RFC 3042.

 

Now trying to address some of your questions inline...

 

 

On Oct 20, 2006, at 4:22 PM, David Barrett wrote:



Following up on my earlier question, TCP has a bunch of “magic numbers” whose best values vary depending upon the source you consult.  I’m curious if you have any input on:

 

1)       What’s a good initial value for the cwnd, whether starting from scratch or after a RTO?  I know RFC2581 says one thing, and 3465 says another, and others say other things.  I’m curious what you actually use and like, and why.

I'd stick with RFC 2581 -- I'm always hesitant of those experimental extensions, since there are so damn many.

 

For points 2 through 5, from the sender's perspective, it either detects loss using a timeout (which is bad), or a fast retransmit (which is more lenient). To generalize: If the RTO expires, set cwnd to 1 MSS and the ssthresh to half the amount of outstanding data. For a fast retransmit, ssthresh is again set to half the amount of data in flight, while the cwnd is set to sshthresh+3 and is increased by 1 (MSS) for each new ACK (the effect of this is to keep the amount of outstanding data constant until the retransmitted packet is received). RFC 2581 spells this out in gory detail, and addresses some points I've missed.



6)       What ALPHA value do you use for RTT smoothing?  RFC 793 (3.7) recommends between .8 and .9; any preference? (updatedRTT = ALPHA*oldRTT + (1-ALPHA)*newRTT)  I’m using .85 for lack of a better idea.

I would stick with the values and implementation found in the appendix of Van Jacobsen's paper "Congestion Avoidance and Control".  If you haven't read that already, do so.



7)       What BETA value do you use for RTO calculation?  RFC 893 (3.6) recommends between 1.3 and 2.0; any preference?  (retransmitTimeout = BETA * rtt)  I’m using 1.65, for no particular reason.

I think 2.0 is the standard, and you can implement it with a shift to boot ;)

 

When I have time tonight, I'll try and look this all up again... It's been awhile since I've poured over it.

 

- Mike

_______________________________________________
p2p-hackers mailing list

_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers

Reply via email to