buglwIP - A Lightweight TCP/IP stack - Bugs: bug #28106, duplicate acknowledge for fast...

 
 

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

bug #28106: duplicate acknowledge for fast retransmit could have not null length

Submitted by:  Oleg Tyshev <olegreen>
Submitted on:  Fri 27 Nov 2009 02:47:31 PM UTC  
 
Category: TCPSeverity: 3 - Normal
Item Group: Faulty BehaviourStatus: Fixed
Privacy: PublicAssigned to: Simon Goldschmidt <goldsimon>
Open/Closed: ClosedPlanned Release: None
lwIP version: CVS Head

(Jump to the original submission Jump to the original submission)

Thu 03 Dec 2009 07:43:03 PM UTC, comment #16:

Checked in. (Also moved some code down a bit in tcp_output that isn't used in the send_empty_ack case.)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 03 Dec 2009 09:55:20 AM UTC, comment #15:

Yes,

if pure ACK interleaved with data will be a problem, it is other issue.

Oleg Tyshev <olegreen>
Wed 02 Dec 2009 04:50:03 PM UTC, comment #14:

Does this mean that the patch from comment #4 (slightly changed: only use tcp_send_empty_ack() at places 2 and 3, not 1 and 4 - see comment #5) is OK for you?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 02 Dec 2009 04:38:16 PM UTC, comment #13:

Kieran, you are right.
I didn't thought at first that (unacked == NULL) condition in tcp_do_output_nagle() is sign of that some data already sent.

It will be fine later to implement forcing data delivery, may be using PSH flag.

It will be interesting to test fast retransmit with bi-directional transmit of high volumes,
how often will appear effect described in comment #2, comment #3.
(Sending pure ACK interleaved with data)

Oleg Tyshev <olegreen>
Wed 02 Dec 2009 09:19:15 AM UTC, comment #12:

I'm a bit confused about what is being suggested here. Oleg: could you illustrate the problem you're describing with an example of what you think will happen now, and what you think should happen?

Nagle must not affect the sending of pure acknowledgements. It should only affect whether payload bytes are sent.

Kieran Mansley <kieranm>
Project Administrator
Tue 01 Dec 2009 05:49:57 PM UTC, comment #11:

> Data should be sent from unsent queue
> [..]
> 2. together with acknowledge after tcp_ack_now()


Are you sure about that? That would mean the nagle algorithm would include a timeout, which I haven't heard of yet. I guess this is implemented by the condition "unacked == NULL" (which in turn is achieved through fast and slow retransmission).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Tue 01 Dec 2009 02:45:58 PM UTC, comment #10:

For (tcp_do_output_nagle(pcb) == 0) with TF_ACK_NOW can help following patch:

- if((tcp_do_output_nagle(pcb) == 0) &&
- ((pcb->flags & (TF_NAGLEMEMERR | TF_FIN)) == 0)){
- break;
+ if (tcp_do_output_nagle(pcb) == 0) {
+ if ((pcb->flags & (TF_NAGLEMEMERR | TF_FIN)) == 0) {
+ break;
+ }
+ else if (pcb->flags & TF_ACK_NOW) {
+ output_only_one_segment = 1;
+ }
....
+ if (output_only_one_segment) {
+ break;
+ }

(file #19175)

Oleg Tyshev <olegreen>
Tue 01 Dec 2009 10:11:17 AM UTC, comment #9:

Ok,

Data should be sent from unsent queue
1. if nagle not prevent sending by send()
2. together with acknowledge after tcp_ack_now()
3. together with delayed acknowledge from tcp_fasttmr()

It looks like we have error in 2.:
unsent queue has very little data,
tcp_do_output_nagle() prevent sending data and pure acknowledge, exception is only fast retransmit.
Pcb has TF_ACK_NOW flag but nothing is sent.

Good review of delayed acks is here:
http://kb.pert.geant.net/PERTKB/TCPAcks
---
RFC 831 first suggested a delayed acknowledgement (Delayed ACK) strategy, where a receiver doesn't always immediately acknowledge segments as it receives them. This recommendation was carried forth and specified in more detail in RFC 1122 and RFC 5681 (formerly known as RFC 2581). RFC 5681 mandates that an acknowledgement be sent for at least every other full-size segment, and that no more than 500ms expire before any segment is acknowledged.

The resulting behavior is that, for longer transfers, acknowledgements are only sent for every two segments received ("ack every other"). This is in order to reduce the amount of reverse flow traffic (and in particular the number of small packets). For transactional (request/response) traffic, the delayed acknowledgement strategy often makes it possible to "piggy-back" acknowledgements on response data segments.
--

In our implementaion ack sent not for each full-size segment but for each 2nd segment (see tcp_ack()).

Now flags TF_ACK_NOW and TF_ACK_DELAY are cleared in tcp_send_empty_ack().

tcp_fasttmr() checks TF_ACK_DELAY and data won't be sent.

Oleg Tyshev <olegreen>
Mon 30 Nov 2009 04:01:52 PM UTC, comment #8:

tcp_send_empty_ack does nothing else than tcp_output did before when unsent was NULL. The only difference is it is done right away, not after tcp_receive returns (where tcp_input calls tcp_output).

> It means that only 2nd received data segment will be acknowledged


That's fully intentional and is called 'delayed ACK' (and it doesn't get changed by my patch).

> and tcp_fasttmr() won't send delayed for sending data.


I'm afraid I don't understand what you're trying to say.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 30 Nov 2009 03:41:43 PM UTC, comment #7:

tcp_send_empty_ack() clears TF_ACK_NOW and TF_ACK_DELAY
It means that only 2nd received data segment will be acknowledged and
tcp_fasttmr() won't send delayed for sending data.

Other hand with cleared flags we can avoid sending data interleaved with duplicated ACK (see comment #3).

Oleg Tyshev <olegreen>
Mon 30 Nov 2009 02:00:26 PM UTC, comment #6:

> Yes, first case with old segment could stay with send_ach_now()


Might be less invasive that way...

> I don't know about 4th:
> each 0 segment will be answered with 0 segment immediately,
> in case erroneous seqno ping-pong will last endless?


That's true, but it's already like that now: tcp_ack_now leads() to sending an empty ACK, too (when unsent is empty) as tcp_output() gets called later from tcp_input()...

Anyway, I think I'll prefer to not change the 4th, too, as that won't make too many problems, I guess.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 30 Nov 2009 11:07:38 AM UTC, comment #5:

Yes, it looks like in Linux data packet not considered to be dupack.

tcp_send_empty_ack patch

  • the whole segment is < rcv_nxt
  • if the incoming segment is out-of-sequence
  • The incoming segment is not withing the window
  • Segments with length 0 out of the window

Yes, first case with old segment could stay with send_ach_now()
I don't know about 4th:
each 0 segment will be answered with 0 segment immediately,
in case erroneous seqno ping-pong will last endless?

Oleg Tyshev <olegreen>
Sun 29 Nov 2009 01:55:11 PM UTC, comment #4:

The attached patch moves the empty-ACK-sending code from tcp_output() to a new dedicated function (tcp_send_empty_ack) that is used from tcp_output.

To fix this bug, all 4 calls to tcp_ack_now() inside tcp_receive() have been changed to call tcp_send_empty_ack() (the first might not be required).

Any comments before checking in?

(file #19149)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 27 Nov 2009 04:37:34 PM UTC, comment #3:

Linux has:

#define FLAG_NOT_DUP (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)

i.e. if the packet has data, updates the window, or acks new data, it is not a duplicate. The first of these is the point in question. Looks like other stacks all consider a packet with data in as not a duplicate, so the change brings us in line with everyone else.

You are quite right that if packets carrying data get interleaved with the duplicate ACKs it will fail to do fast retransmission due to the dup ack count being reset, but for most network stacks that would be an unusual case because received packets would normal be processed in batches. That might not be the case for users of lwIP, particularly where there are small windows and so not many packets in flight, but it's better that we're compatible with other stacks than with older versions of lwIP.

Kieran Mansley <kieranm>
Project Administrator
Fri 27 Nov 2009 03:46:45 PM UTC, comment #2:

It is bad, that current implementation of lwip is not compatible with old one :(

Kieran, I don't understand how fast retransmit works if dup ACK should have 0 length.

suppose host A send packets:
seqno 1 ack 100
seqno 2 ack 101
seqno 3 ack 102 - X this packet lost
seqno 4 ack 103
seqno 5 ack 104

host B send packets
seqno 105 ack 1 len 1
seqno 106 ack 2 len 1
seqno 107 ack 3 len 1
seqno 108 ack 3 len 0 (send dup ack)
seqno 108 ack 3 len 1 (send own data)
seqno 109 ack 3 len 0
seqno 109 ack 3 len 1
seqno 110 ack 3 len 0
seqno 110 ack 3 len 1

Host A receives (ack 3 len 0) - variable dupack incremented
(ack 3 len 1) - dupack reseted
(ack 3 len 0) - dupack incremented
(ack 3 len 1) - dupack reseted
and so on

Without length testing it seems to work.

Stevens in TCP/IP Illustrated use 4.4BSD-Lite sources.
It is interesting what say about duplicate ACKs standard
and how it is implemented e.g. in Linux?

Oleg Tyshev <olegreen>
Fri 27 Nov 2009 02:57:18 PM UTC, comment #1:

Yes, that's an interesting case, and I agree with your deduction. It's not just necessary because of the change to our stack, many other stacks will have this requirement for an ACK to be seen as a duplicate.

We currently have no function to send a pure ACK with no data, but it is necessary in this case.

Kieran Mansley <kieranm>
Project Administrator
Fri 27 Nov 2009 02:47:31 PM UTC, original submission:

Last post I have done was for bug with status fixed,
title was not completely correct too.
So I submit new bug.

In new implementation of fast retransmit we have following rules:
/* (From Stevens TCP/IP Illustrated Vol II, p970.) Its only a

  • duplicate ack if:
  • 1) It doesn't ACK new data
  • 2) length of received packet is zero (i.e. no payload)
  • 3) the advertised window hasn't changed
  • 4) There is outstanding unacknowledged data (retransmission timer running)
  • 5) The ACK is == biggest ACK sequence number so far seen (snd_una)

*/

We check clause 2
"length of received packet is zero (i.e. no payload)"

It means that we should ourself generate zero length ACK for each new segment in out of sequence queue.
But now we call tcp_ack_now(pcb).
If unsent queue has something, we send non zero length ACK packet.

Actually in RFCs I didn't found mentioning about zero length ACK,
only Stevens.

Oleg Tyshev <olegreen>

 

Attached Files
file #19175:  tcp_output.patch added by olegreen (1KiB - text/x-patch)
file #19149:  lwip_28106_1.patch added by goldsimon (6KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by goldsimon (Updated the item)
  • -unavailable- added by kieranm (Posted a comment)
  • -unavailable- added by olegreen (Submitted the item)
  •  

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

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 7 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Thu 03 Dec 2009 07:43:03 PM UTCgoldsimonStatusIn Progress=>Fixed
      Open/ClosedOpen=>Closed
    Tue 01 Dec 2009 02:45:58 PM UTColegreenAttached File-=>Added tcp_output.patch, #19175
    Sun 29 Nov 2009 01:55:30 PM UTCgoldsimonStatusNone=>In Progress
      Assigned toNone=>goldsimon
    Sun 29 Nov 2009 01:55:11 PM UTCgoldsimonAttached File-=>Added lwip_28106_1.patch, #19149
    Fri 27 Nov 2009 02:59:49 PM UTCkieranmPlanned Release=>1.3.2

    Back to the top


    Powered by Savane 3.1-cleanup1