Subject: Re: internet draft on suggested mod to the Nagle algorithm

From: David Borman <[email-masked]>
Date: Thu, 4 Feb 1999 11:07:58 -0600 (CST)

Greg,

(This message got a bit longer than I anticipated... Oh well.)

I like the proposed modification to the Nagle algorithm.  But I do
have to say that I'm biased, because I implemented this in BSD/OS
several years ago, as part of an overall effort to improve BSD/OS's
performance when doing web traffic (BSD/OS 2.1, patch K210-019, August
1996).  My goal was to eliminate any artificial delays in the TCP
traffic, and to make the TCP packets as full as possible.

Basicly, I changed our TCP so that when an application does a single
write, if there isn't any outstanding un-acked data, all the new data
will go out (subject to constraints of the congestion window), including
the trailing partial packet.  It has been working very well, and is
basicly similar to the proposed text of:

        If a TCP has less than a full-sized packet to transmit,
        and if any previous less than full-sized packet has not
        yet been acknowledged, do not transmit a packet.

My changes were well worth it.  Your suggestion of adding a SND_SML
state might be a simpler implementation than what I did, though we
were dealing with more issues than just the TCP Nagle issue.  In BSD,
sosend() only copies down at most MCLBYTES (2K in BSD/OS) from the user
to the kernel, and then hands that single piece down to tcp_output().

We were seeing problems on FDDI where TCP would get the initial 2K
of the data, and it would send it out right away, even when there was
more data that could have filled a 4K packet, it just hadn't been
copied down from the user yet.  The next 2K would stall due to Nagle,
and the successive 2K would then allow a 4K packet to be sent.

We were also seeing the problem you addressed, where a 2000 byte write
would send the initial 1460 bytes, followed by a delay before sending
the other 540 bytes, due to Nagle.

In a nutshell, our code does the Nagle decision once on the whole
chunk of data written in a single write by the application.  So,
the trailing partial packet goes out immediatly, because there was
no outstanding data when the write call was issued.  We actually
remember this state across successive calls to tcp_output(), since
sosend() hands down the large write from the user in multiple pieces.
The old code would generate:

	User write 4096 -> kernel
		sosend 2048 -> tcp_output
			send 1460 (defer 588 bytes)
		sosend 2048 -> tcp_output
			send 1460 (defer 1176 bytes)
	(wait for ACK or timeout)
			send 1176
			
What we didn't want, and what we initially got, was:

	User write 4096 -> kernel
		sosend 2048 -> tcp_output()
			send 1460
			send 588
		sosend 2048 -> tcp_output()
			send 1460 (defer 588 bytes)
	(wait for ACK or timeout)
			send 588 bytes

After adding state across successive calls to tcp_output(), our
code does:
	User write 4096 -> kernel
		sosend 2048 -> tcp_output()
			send 1460 (defer 588 bytes)
		sosend 2048 -> tcp_output()
			send 1460
			send 1080

(All the above examples assume the congestion window is large
enough to allow all the data to go out...)

So, it is important to point out to implementors that with this
change to Nagle, you need to keep track of whether or not there is
more data waiting to be copied down from the user.

Another thought is that perhaps Nagle should only apply when you have
successive small packets.  Then the text becomes something like:

	If a TCP has less than a full-sized packet to transmit,
        and if the last insequence packet sent was less than a
	full-sized packet and has not yet been acknowledged, do
	not transmit a packet.

But then if the application did:
	write(s, buf1, 1500);
	write(s, buf2, 1500);
	write(s, buf3, 1500);

You'd get:
	1st write:	send 1460 bytes
			send 40 bytes
	2nd write:	send 1460 bytes
			send 40 bytes
	3rd write:	send 1460 bytes
			send 40 bytes

whereas the current Nagle code would produce:

	1st write:	send 1460 bytes  (defer 40 bytes)
	2nd write:	send 40 + 1420 = 1460 bytes (defer 80 bytes)
	3rd write:	send 80 + 1380 = 1460 bytes  (defer 120 bytes)
			(wait for ACK or timeout)
			send 120 bytes

and the proposed Nagle (and the current BSD/OS) would produce:

	1st write:	send 1460 bytes
			send 40 bytes
	2nd write:	send 1460 bytes (defer 40 bytes)
	3rd write	send 40 + 1420 = 1460 bytes (defer 80 bytes)
			(wait for ACK or timeout)
			send 80 bytes

As long as the application is not doing multiple writes to send
a single transaction request, the proposed code would work just
fine.  In fact, my implementation was geared to optimize with the
assumption that the application was smart enough to send the entire
request in a single write system call.

As for sending multiple requests in a row, I think the additional
idea about SO_EXPLICITPUSH could be used to fix the delay of the
final packet.  I've bounced this idea around before, but never
followed through on it.  My suggestion is to just add a MSG_PUSH
flag that would be used on the last send to indicate that the
application doesn't intend to send anymore data at this time.

I don't like SO_EXPLICITPUSH, because that means that the kernel
is trusting the application to remember to tell it when it is
done sending the data.  If the application forgets, then it could
adversly affect the performance below what would have happened
had SO_EXPLICITPUSH not been set.  I'd rather have the kernel
continue to be as aggressive as normal in sending out data, but
take the MSG_PUSH bit as a suggestion that it should be more
aggessive and transmit any delayed data, since no more data will
be written at this time.

			-David Borman, [email-masked]

---

From: [email-masked] (Alan Cox)
Date: Thu, 4 Feb 1999 18:47:15 +0000 (GMT)

> aggessive and transmit any delayed data, since no more data will

The Linux TCP_CORK option is basically doing the same thing but the other
way around. An application has to actively turn this behaviour on and request
its use.  It also solves the sendfile() interaction problems more cleanly than
a send this data then the file api which is really oriented at web traffic.

That the unix socket API needs a "just buffer this for a minute" option is
fairly indisputable. Since most applications won't support sensible use of
such API's a better heuristic is good news too.

Alan

---

From: Kacheong Poon <[email-masked]>
Date: Thu, 4 Feb 1999 13:50:39 -0800 (PST)

> 	full-sized packet and has not yet been acknowledged, do

I second this change.  This implies that in the TCP context, if an
application does a single send, TCP will send out all available data.
I think Rick Jones will also agree with this as this is what his stack
does.  In case people are interested, Solaris's TCP stack also does
this.

							K. Poon.
							[email-masked]

---

From: "Eric A. Hall" <[email-masked]>
Date: Thu, 04 Feb 1999 11:07:01 -0800

>                         (wait for ACK or timeout)

This is at least one extra send operation, which can't be a good thing,
particularly when the network is over-utilized (or near to it) already.
While this isn't as bad as Rick's example (1461-byte writes), it is
still bad utilization. (I'd hate to own the network that did both.)

I'd say that based on this info, it is better to just disable Nagle if
your application is going to be writing small (1.5 segments) chunks, and
leaving it enabled for applications that do large writes, rather than
introducing lots of new frames to the network.

-- 
Eric A. Hall                                            [email-masked]
+1-650-685-0557                                    http://www.ehsco.com

---

From: Kacheong Poon <[email-masked]>
Date: Thu, 4 Feb 1999 18:33:42 -0800 (PST)

> still bad utilization. (I'd hate to own the network that did both.)

Let's look at the problem from an application programmer's point of view. You
are writing a network application, the transfer pattern can be anything. You
notice a performance problem and find that by disabling Nagle algorithm, the
problem goes away.  What will you do in the production code?

Now with the changed Nagle algorithm, for certain kind of transfer pattern,
you do not notice any performance problem.  So you will not turn off Nagle
algorithm.  But in fact, the Nagle algorithm may still kick in sometimes and
help the network.  Just that you only see the little impact from time to time.

Nagle algorithm helps a lot in the case of telnet like traffic.  This we
should not change.  But for some kind of transfer pattern, it helps a lot if
we relax the algorithm.  By doing this, we encourage  application programmer
not to disable the algorithm.  IMHO, this is what the  proposed draft is
about.  We do not want the algorithm to be disabled in general.  We are making
an incentive for programmers not to do that.  At the same time, we do not
adversely affect the network.  Imagine what will happen if every application
programmers disable the algorithm "by default."

> introducing lots of new frames to the network.

The problem is an application can turn the algorithm off any time, regardless
of the transfer pattern.  And the proposed change is not to disable the
algorithm, but to relax it in some cases.  I'd rather see a slight increase
of network traffic in some cases than have most applications turn off the
algorithm by default.

Solaris's TCP stack has some form of the proposed change for many years.  I
have not heard of customer complaints because of it.  At the very least,
there was no network meltdown...

							K. Poon.
							[email-masked]

---

From: Greg Minshall <[email-masked]>
Date: Fri, 05 Feb 1999 11:47:15 -0800

Dave Borman wrote a long message which i am still digesting.  However, 

> 	full-sized packet and has not yet been acknowledged, do

The problem is that if an application does a sequence of small and large 
writes, you send more than one small packet per RTT, which i'd rather avoid.

(All of this is complicated by the fact that most stacks, including the BSD 
stack, actually look at the size of the send() from the application rather 
than the size of packets transmitted over the wire.  I think this is 
reasonable in the sense that, really, applications don't have much hope of 
knowing what MSS might be at any particular point in time.  Others earlier in 
this thread have mentioned this, especially w.r.t. path MTU discovery).

Greg

---

From: Greg Minshall <[email-masked]>
Date: Mon, 08 Feb 1999 17:27:34 -0800

Dave,

If i understand what you did several years ago:

> I changed our TCP so that when an application does a single write, if
> there isn't any outstanding un-acked data, all the new data will go
> out (subject to constraints of the congestion window), including the
> trailing partial packet.

you are doing what various other people (Rick Jones, most notably) have said 
they are doing.  I.e., Nagle sort of at the output of send() rather than in 
tcp_output().  (The BSD code i have, from FreeBSD 2.2.x, does Nagle on *input* 
to tcp_output(), rather than as tcp_output() emits packets to ip_output(); 
this seems sort of an approximation [possibly less than ideal] to what you are 
doing.)

I think this is a fine thing to do.  However, i don't think (as you seem to) 
that this is the same as what the I-D is proposing.

According to the I=D (or, at least the *intent* of the I-D, as Vernon points 
out that the english description may not be ideal!; see below for some 
pseudo-code), if an application calls send() with 20 bytes, and some MSS-sized 
packets are not acknowledged, but no packets < MSS are unacknowledged, then 
(consistent with windows) a packet with a TCP payload of 20 bytes will be 
transmitted.

I think that is *not* what your modification would do.  (Correct me if i am 
wrong!)

So, the $64,000 question is: now that you (hopefully, if i'm getting better at 
explaining it!) know what the modification is, what are your thoughts about it?

Thanks,  Greg
----
(eff.snd.mss is RFC1122 terminology.)

Current Nagle:

	if ((available_data < eff.snd.mss) && (snd.una != snd.nxt))
		don't send;

New Nagle:

	if ((available_data < eff.snd.mss) && (snd.una < snd.sml))
		don't send;
	else
		snd.sml = snd.nxt+available_data;

(and, code to "pull" snd.sml along, so that it doesn't get left behind if the 
sequence space wraps.)

---

From: Neal Cardwell <[email-masked]>
Date: Tue, 9 Feb 1999 13:52:44 -0800 (PST)

> (and, code to "pull" snd.sml along, so that it doesn't get left behind if the 

Just to clarify, i believe the New Nagle pseudocode is a little closer to:

	if (available_data < eff.snd.mss) {
        	if  (snd.una < snd.sml)
                	don't send;
		else
			snd.sml = snd.nxt+available_data;  
	}

neal

---

From: Greg Minshall <[email-masked]>
Date: Tue, 09 Feb 1999 17:24:55 -0800

> Just to clarify, i believe the New Nagle pseudocode is a little closer to:

yes, right.  thanks!