buglwIP - A Lightweight TCP/IP stack - Bugs: bug #20287, tcp_output_nagle sends too early

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #20287: tcp_output_nagle sends too early

Submitted by:  Simon Goldschmidt <goldsimon>
Submitted on:  Thu 28 Jun 2007 10:40:41 AM UTC  
 
Category:  TCP Severity:  4 - Important
Item Group:  Faulty Behaviour Status:  Fixed
Privacy:  Public Assigned to:  Simon Goldschmidt <goldsimon>
Open/Closed:  Closed Planned Release:  None
lwIP version:  None

( Jump to the original submission)

Wed 21 Nov 2007 06:39:55 PM UTC, comment #28: 

I regard this as fixed, please don't hesitate to reopen it if you find errors/problems!

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 21 Nov 2007 05:59:37 PM UTC, comment #27: 

I chose to check it in like that: it's stable for me and I have the feeling it only gets tested by others after checking in.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 12 Nov 2007 08:09:18 PM UTC, comment #26: 

> Sending anyway if there's a SYN, FIN or RST is a very good idea.


I changed that again:

SYN is always in an extra segment: either the segment including SYN has a next pointer set (so nagle would send) or pcb->unacked would be NULL (no segment sent before SYN).

RST is only sent using tcp_rst() which sends directly using ip_output() (since it doesn't have a pcb to use for the RST).

What remains is FIN. And I think here it is not enough to check pcb->unsent for FIN, the FIN could be in pcb->unsent->next or even after that. Therefore, I think it's better to set pcb->flags |= TF_FIN (or something) and to always send ('disable nagle') if pcb->flags & TF_FIN. That way, once a connection has been closed, everything enqueued is sent (there won't come anything new anyway, so waiting - what nagle does - wouldn't help).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 12 Nov 2007 12:43:03 PM UTC, comment #25: 

If in tcp_enqueue, the number of enqueued pbufs has reached the maximum limit, TCP has to wait for data to be acknowledged to enqueue more. If this limit is reached at a point where nagle would wait and not send (e.g. the only unsent segment is half full; at least one segment in unacked), lwIP is stuck until the remote side acknowledges unacked data. This typically leads to an ACK being sent by a remote TCP timer because of the delayed ACK strategy.

In consequence, when TCP_SND_QUEUELEN is set low and an application enqueues many small packets (e.g. 12 bytes), this can happen very fast and leads to very poor throughput (2 packets every ~200 ms).

As the current implementation always sends what is enqueued, this was not a problem until now.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 12 Nov 2007 12:27:20 PM UTC, comment #24: 

I'm not sure I fully understand why we need a special case for when there's been a memory error. 

Sending anyway if there's a SYN, FIN or RST is a very good idea.

Kieran Mansley <kieranm>
Project Member
Sun 11 Nov 2007 09:10:04 PM UTC, comment #23: 

Is everyone OK with using the last free bit of tcp_pcb->flags for remembering a memory error in tcp_enqueue?

This is needed to fix nagle while still sending segments (in tcp_output) that are incomplete due to memory restrictions (TCP_SND_BUF / TCP_SND_QUEUELEN or empty pool).

Also, I chose to send anyway if a segment to be sent includes SYN, FIN or RST, but I don't really know if that is necessary...

attaching the new patch

(file #14360)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 11 Nov 2007 08:33:39 PM UTC, comment #22: 

Don't know where my head was... TCP_NODELAY obviously doesn't work for that, we'd have to create another flag.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Sun 11 Nov 2007 05:47:22 PM UTC, comment #21: 

Just a little status update for anyone who's interested:

Checking for the nagle condition in tcp_output is not enough because if one of the memory error or memory check conditions prevents tcp from adding more data to the unsent segment, the nagle condition will prevent sending the segment.

And because a segment is not sent until it is full, segments are only acknowledged when the remote side times out (because of delayed ACK) (where without the new nagle, small packets were sent, which is still inefficient, but faster than delayed-ACK-timeout).

A solution for this would be to still send if nagle says NO when a memerr has occurred (e.g. by setting TF_NODELAY to pcb->flags).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 09 Nov 2007 01:10:38 PM UTC, comment #20: 

Hmm, it's been a while but I think the status was 'works for me'. I only wanted some feedback from others since this really a crucial part of the stack's TCP implementation...

I can check it in and we'll see what the (hopefully numerous) tests say before we release 1.3.0...

But first I'll do some more tests at home. I should be able to find some time for it this weekend.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 09 Nov 2007 01:05:20 PM UTC, comment #19: 

Any status update on this?  Sounds like it's done, and just needs checking in.

Kieran Mansley <kieranm>
Project Member
Fri 05 Oct 2007 03:14:38 PM UTC, comment #18: 

This has taken some time, but finally, I found some free time to work on it ;-)

The main change is checking the nagle conditions in tcp_output in the last while-loop (effectively calling tcp_output_segment only for 'full' segments or on idle connections).

tcp_output_nagle remains defined as 'if(nagle_ok(pcb)) { tcp_output(pcb);}', but can be omitted (at the cost of always calling tcp_output, which checks a lot and then does nothing).
As a result, in the netconn API, I still use tcp_output_nagle.

As this is an integral part of the stack, I'd like you all to test it, please, before I check it in!

(file #14094)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 29 Aug 2007 09:25:45 AM UTC, comment #17: 

No, not yet. I plan to have more time to spend on this next month :-(

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 29 Aug 2007 09:12:55 AM UTC, comment #16: 

Is this done?

Kieran Mansley <kieranm>
Project Member
Mon 09 Jul 2007 01:11:53 PM UTC, comment #15: 

> I'd prefer not to add the call to tcp_output from tcp_write as the API would lose some flexibility.


OK, you're right. Don't know if anyone uses it like this, but we can also call it from netconn_send.

I'll work on the modification of tcp_output, then. For speed reasons, it might be interesting to leave the nagle decision in a define, though. I'll test that.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 09 Jul 2007 01:09:10 PM UTC, comment #14: 

I'd prefer not to add the call to tcp_output from tcp_write as the API would lose some flexibility.

I think it would be OK to move nagle into tcp_output however.

Kieran Mansley <kieranm>
Project Member
Mon 09 Jul 2007 01:07:16 PM UTC, comment #13: 

I'd favour moving all the nagle code into tcp_output. This would add one function call per tcp_write call, but it's more like what people suppose TCP does, I think.

Maybe we should also put a call to tcp_output into tcp_write, to simplify the raw API?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 09 Jul 2007 01:03:04 PM UTC, comment #12: 

Or perhaps have a flag to tcp_output to say "send as much as possible" or "just send one segment", and leave the nagle code as is?  Haven't thought this through, but might be simpler.

Kieran Mansley <kieranm>
Project Member
Mon 09 Jul 2007 01:01:25 PM UTC, comment #11: 

OK, I see what you mean.

In that case, is it possible to move all the nagle code into tcp_output?  I don't like having duplicated functionality - twice as much code, more bugs etc.

Kieran Mansley <kieranm>
Project Member
Mon 09 Jul 2007 12:50:27 PM UTC, comment #10: 

Imagine you are sending 500 byte chunks, have no unsent queue and some segments in unacked (with TCP_MSS of 1460):

tcp_output_nagle wouldn't send until the first segment is filled (in this example, 1000 bytes in a segment, then a next segment would be created).

At this point, after having enqueued the 3rd segment, tcp_output_nagle would really call tcp_output, which would then send as much as it can, resulting in sending 2 segments: the first with 1000 bytes and the second with 500 bytes. A proper implementation would hold back the second segment until it is filled.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 09 Jul 2007 12:43:55 PM UTC, comment #9: 

Can you give a little more information (to save me having to think about it too hard!) to why this extra nagle code is necessary in tcp_output?  Is it that we enqueue code when not nagle constrained, and then try and output it when we should be nagle constrained?

Kieran Mansley <kieranm>
Project Member
Fri 29 Jun 2007 07:17:32 PM UTC, comment #8: 

Seems ok for me...

Frédéric Bernon <fbernon>
Project Member
Fri 29 Jun 2007 05:49:10 PM UTC, comment #7: 

- As a first fix, I've added a check that snd_queuelen doesn't overflow. I'm still checking if it needs to be converted to u16_t.

- I figured tcp_output_nagle does still send too much data: if 2 segments are enqueued (e.g. one of size==mss, the other has only 12 bytes), both segments will be sent by tcp_enqueue. Thus, it is necessarry to have the nagle check inside the last while-loop in tcp_output also.

Any objections about that? It would only get active if TF_NODELAY is not set, so we would have a real implementation of the nagle algorithm that is on all the time until disabled (even for raw api).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 28 Jun 2007 07:55:38 PM UTC, comment #6: 

The new algorithm performs much better.

Because small chunks are put together to form bigger segments more often, the tcp_pcb->snd_queuelen is more possible to overflow now, however.

There is some incosistency about the snd_queuelen variable, anyway: one time it is referred to as 'the total number of pbufs for this segment', another time with 'update number of segments on the queues'. I think the number of pbufs makes more sense to configure for small systems, but overflowing should be checked (not only with an assert, can happen in runtime environments, also).

And we should convert snd_buflen to an u16_t: if you have a send-buffer of 32KBytes and want fill that up with many small pbufs, you easily get more than 255 pbufs in that chain!

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 28 Jun 2007 12:11:04 PM UTC, comment #5: 

Sorry, unsent of course! (in the patch, it's correct!)

I'll change
if(pcb->snd_queuelen > 1)
to

if((pcb->unsent != NULL) && (pcb->unsent->next != NULL))

at home and see if that does the trick. If so, I'll check it in like that.

Thanks for sharing your thoughts on this.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 28 Jun 2007 11:20:15 AM UTC, comment #4: 

I would understand it if you wanted to send if pcb->unsent contains more than one segment, but I don't understand the significance of pcb->unacked having more than one segment.

Otherwise, I agree with what you said.

Kieran Mansley <kieranm>
Project Member
Thu 28 Jun 2007 11:07:18 AM UTC, comment #3: 

Sorry, my phrase was a little easy to misunderstand.

The
'if MIN(available_window_space, data_available_to_send) >= MSS {'
is currently implemented as
'pcb->snd_queuelen > 1'
which is wrong.

I think available_window_space is taken care of by tcp_output, so we don't need to test this in the tcp_output_nagle condition.

As for data_available_to_send >= MSS: unfortunately, we can't check it like that unless we change data segmentation in tcp_enqueue: I don't think it makes sense delaying a segment if we wouldn't fill it anyway. Nagle algorithm should avoid sending many small segments and since we're not able to fill all segments, we should send every 'full' segment (i.e. segment which isn't filled further).

That's why I propose to send when pcb->unacked contains more than one segment.

Is this correct?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 28 Jun 2007 10:50:44 AM UTC, comment #2: 

From your description I think you've slightly misunderstood the nagle algorithm (or made a typo in your description!)  I've not looked at the patch to see which it is, but as I understand nagle can be summarised as:

if MIN(available_window_space, data_available_to_send) >= MSS {
  send_MSS_segment_now();
}
else {
  if(unacked_queue_is_empty()) {
    send_as_large_a_packet_as_possible_now();
  }
  else {
    leave_data_available_to_send_on_unsent_queue();
  }
}

I don't think the ordering of the two "if" statements is important, as long as the second "else" only happens if both are false.

The difference to your description ("the nagle algorithm should only send unsent data (if unacked is empty) when there is a full segment to send") is that nagle should always send unsent data if the unacked queue is empty.

I don't doubt that the current version doesn't quite fit with that description, but want to make sure that any replacement does.

Kieran Mansley <kieranm>
Project Member
Thu 28 Jun 2007 10:42:04 AM UTC, comment #1: 

Attaching a simple patch as proposed.

(file #13193)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 28 Jun 2007 10:40:41 AM UTC, original submission:  

Our implementation TCP nagle algorithm (tcp_output_nagle, previously included in netconn_write/do_write), sends if pcb->snd_queuelen > 1.

The problem with that is that pcb->snd_queuelen is > 1 even if there is no segment on the unsent queue but some segments are on the unacked queue. Also, if a segment on the unsent queue consists of multiple pbufs, pcb->snd_queuelen will be > 1. But the nagle algorithm should only send unsent data (if unacked is empty) when there is a full segment to send.

I propose to change the condition ((tpcb)->snd_queuelen > 1) to ((tpcb)->unsent != NULL) && ((tpcb)->unsent->next != NULL) which means more than one segment is unsent. Since we currently don't fill up every segment, we would sent non-full segments, but that can't be changed (unless in a way suggested in task #7040).

I'd like to hear opinions from others before changing this, maybe there is a better solution?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.

 

Attached Files
file #14360:  tcp_nagle2.patch added by goldsimon (4KiB - text/x-patch)
file #14094:  tcp_nagle.patch added by goldsimon (2KiB - text/x-patch)
file #13193:  tcp_output_nagle.patch added by goldsimon (1KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by fbernon (Posted a comment)
  • -email is unavailable- added by kieranm (Posted a comment)
  • -email is unavailable- added by goldsimon (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2007-11-21 goldsimon StatusNone => Fixed
        Open/ClosedOpen => Closed
    2007-11-11 goldsimon Attached File- => Added tcp_nagle2.patch, #14360
    2007-10-05 goldsimon Attached File- => Added tcp_nagle.patch, #14094
    2007-07-13 kieranm Planned Release => 1.3.0
    2007-06-28 goldsimon Attached File- => Added tcp_output_nagle.patch, #13193

    Back to the top


    Powered by Savane 3.5