buglwIP - A Lightweight TCP/IP stack - Bugs: bug #19434, Processing of Fast retransmit bug

 
 

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

bug #19434: Processing of Fast retransmit bug

Submitter:  Oleg Tyshev <olegreen>
Submitted:  Wed 28 Mar 2007 12:00:31 PM UTC
   
 
Category:  TCP Severity:  3 - Normal
Item Group:  Faulty Behaviour Status:  Fixed
Privacy:  Public Assigned to:  kieranm
Open/Closed:  Closed Planned Release:  None
lwIP version:  None

Jump to the original submission

Thu 12 Apr 2007 02:56:47 PM UTC, comment #12: 

OK, checked in with that additional change.

Thanks for your help!

Kieran Mansley <kieranm>
Group Member
Thu 12 Apr 2007 02:09:18 PM UTC, comment #11: 

I have reviewed patch once more.

It looks fine,
but it is necessary to implement retransmission timer stop
(rtime=-1 when all outstanding data has been acknowledged)
or in following scenario we have extra retransmission:

node1       node2
-----------------------
            <-data1
                [(rtime started)]
ACK data1->
                [(rtime restarted)]
 tcp_slowtmr - ++rtime
 tcp_slowtmr - ++rtime
 ...
 tcp_slowtmr - ++rtime

            <-data2
with first tick of tcp_slowtmr
   if (pcb->unacked != NULL && pcb->rtime >= pcb->rto) -->
       [(retransmit data2)]

Oleg Tyshev <olegreen>
Thu 12 Apr 2007 11:01:24 AM UTC, comment #10: 

Well spotted - thanks. 

Updated patch attached

(file #12473)

Kieran Mansley <kieranm>
Group Member
Wed 11 Apr 2007 04:31:14 PM UTC, comment #9: 

With your patch we have 3 functions where rtime is modified
  tcp_slowtmr
  tcp_receive
  tcp_output_segment

In tcp_slowtmr rtime is only incremented.
 
In tcp_output_segment reset of rtime  occurs only once (timer is never stopped).
 
In tcp_receive reset of rtime occurs on ACK of the new data.

It is necessary to reset rtime on retransmit somewhere...

Oleg Tyshev <olegreen>
Wed 11 Apr 2007 02:20:39 PM UTC, comment #8: 

I have a patch for this (attached) but no ability to test it (i) solves the problem and (ii) doesn't break something else.  Would anyone be willing to give it a go?



(file #12464)

Kieran Mansley <kieranm>
Group Member
Thu 29 Mar 2007 07:45:28 AM UTC, comment #7: 

OK, thanks for pointing that out.  I was looking at a different RFC which words things differently.  I think I can see a simple way to modify our current behaviour to conform to that, so will take a look at this when I get the chance.


Kieran Mansley <kieranm>
Group Member
Wed 28 Mar 2007 04:22:40 PM UTC, comment #6: 

from 2988:

5   Managing the RTO Timer

An implementation MUST manage the retransmission timer(s) in such a way that a segment is never retransmitted too early, i.e. less than one RTO after the previous transmission of that segment.

The following is the RECOMMENDED algorithm for managing the retransmission timer:

   (5.1) Every time a packet containing data is sent (including a retransmission), if the timer is not running, start it running          so that it will expire after RTO seconds (for the current value         of RTO).
   (5.2) When all outstanding data has been acknowledged, turn off the retransmission timer.
   (5.3) When an ACK is received that acknowledges new data, restart the retransmission timer so that it will expire after RTO seconds (for the current value of RTO).

When the retransmission timer expires, do the following:

   (5.4) Retransmit the earliest segment that has not been acknowledged by the TCP receiver.
   (5.5) The host MUST set RTO <- RTO * 2 ("back off the timer").  The maximum value discussed in (2.5) above may be used to provide an upper bound to this doubling operation.
   (5.6) Start the retransmission timer, such that it expires after RTO seconds (for the value of RTO after the doubling operation outlined in 5.5).
====
As in 5.3 written, retransmission timer is restated
when ACK that acknowledges new data

But lwip resets timer each time new segment sent. I think it is not correct.

Oleg Tyshev <olegreen>
Wed 28 Mar 2007 02:20:10 PM UTC, comment #5: 

I don't know of any stack that does it that way - the overhead of maintaining all those timers would be large.  Linux does it the way we do for example.  It's also the way it is described in the RFC standards, and conforming to that is an important consideration.

Kieran Mansley <kieranm>
Group Member
Wed 28 Mar 2007 02:12:02 PM UTC, comment #4: 

Theoreticaly, we should have retransmit timer for each outbound segment that handed down to IP.
If no acknowledgment has been received for the data in a given segment before the timer expires, then the segment is retransmitted, up to the TcpMaxDataRetransmissions times.
In Lwip realization we have only one timer pro pcb.
And may be it have to test acks for first unacknowledged segment?

Oleg Tyshev <olegreen>
Wed 28 Mar 2007 01:45:18 PM UTC, comment #3: 

OK, the very slow data rate explains the problem.  There is no bug.  In 68 minutes the packet in question will be retransmitted.  This is just the TCP way of doing things.

If you were to configure a smaller window, it would take much less time to fill, and you'd get the behaviour you expect.  The window should be sized to hold one round trip time of data at the data rate you expect, which for you is just a few bytes!  Setting it to (for example) your MSS, and setting a small MSS if you really are just sending 1 byte packets, would probably help.

Closing this bug as invalid.

Kieran Mansley <kieranm>
Group Member
Wed 28 Mar 2007 01:21:10 PM UTC, comment #2: 

As I have wrote, "B" sends data very slow (transfer rate approx. 1 byte/sec).
So receive window of "A" will be closed in 4096/60 = 68 minutes.
You are right this is the bug of retransmission timeout - not fast retransmit.
Fast retransmit has been once triggered and we can hope only on retransmission timeout.

in tcp_slowtmr() we check pcb->rtime.
It is more then pcb->rto or not?
But in tcp_output_segment()
each time we set pcb->rtime = 0;

Unfortunately I can't generate ethereal log now.
Temporary I am switched to other target.

Oleg Tyshev <olegreen>
Wed 28 Mar 2007 12:18:28 PM UTC, comment #1: 

From what you've written, I can't see the bug. 

From your example:

 - Packet gets dropped
 - Dup-acks are sent by "A"
 - Fast retransmission at "B" kicks in and retransmits packet once
 - Packet is dropped again by "A"
 - More dup-acks are sent by "A"

Up until this point we are in agreement - I'm just restating your example.

Then:
 - fast retransmit at "B" doesn't send the packet again, but this is not a bug, it is not supposed to.
 - eventually the "B" should run out of window space because the dup-acks won't advance the ack number (by definition), and so it will have to stop sending packets.
 - you should then see a retransmission timeout.

As I said before, if you don't see a retransmission timeout, there is another bug, but the fix that you've suggested is wrong and should not be used.

Can you provide an ethereal capture (tcpdump) to illustrate the problem?

Kieran Mansley <kieranm>
Group Member
Wed 28 Mar 2007 12:00:31 PM UTC, original submission:  

I resubmit bug from lwip-user mail list (http://lists.gnu.org/archive/html/lwip-users/2006-06/msg00028.html) and answer, that Kieran Mansley wrote.
May be some one can sooner or later instead of my hack to find out correct realization.
===
For example we have two node.
Data are sent in both destination.


node1                              node2(lwip)
[data1]--->
                                  <---[data2] (1 byte/sec)
ACK
                                  <---[data3]
data3 packet is dropped
dup ACK 1->
                                      pcb->dupacks==1
dup ACK 2->
                                  <---[data4]
                                      pcb->dupacks==2
dup ACK 3->
                                      pcb->dupacks==3


Node2 starts Fast Retransmission
see tcp_receive
if (!(pcb->flags & TF_INFR)) {
pcb->flags |= TF_INFR;
tcp_rexmit(pcb);
} <---data3
data3 packet is dropped again

node1 sends dup ACKs again and again
but we have TF_INFR flag set, it means no tcp_rexmit!!!


We doesn't have retransmission timeout too, because data are sent in both destination.
...
===
Kieran's answer:

Although this patch may solve your particular problem, it shouldn't be
applied to the main tree.  I think how tcp retransmission is supposed to
work in the case you highlight (a fast retransmitted packet is lost) is
that it falls back to slow retransmission.  You should get a
retransmission timeout even though there is bidirectional traffic as
this timeout should only be reset when receiving an ACK that
acknowledges new data.  As Node1 will continue to only send dup ACKs,
there will be no ACKS that acknowledge new data received at Node2, and
so it should be a retransmission timeout and retransmit data3. 

If we're not generating a retransmission timeout in this example, that
is a bug and should be fixed.

The standard fast retransmission algorithms are known to not be
particular high performance when multiple packets are lost - the normal
solution to this is to implement selective acknowledges (RFC2582).

Oleg Tyshev <olegreen>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #12473:  lwip_rtime.patch added by kieranm (5KiB - application/octet-stream)
file #12464:  lwip_rtime.patch added by kieranm (5KiB - 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 kieranm (Posted a comment)
  • -email is unavailable- added by olegreen (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2007-04-12 kieranm StatusIn Progress Fixed
        Open/ClosedOpen Closed
    2007-04-12 kieranm Attached File- Added lwip_rtime.patch, #12473
    2007-04-11 kieranm Attached File- Added lwip_rtime.patch, #12464
    2007-03-29 kieranm StatusInvalid In Progress
        Assigned toNone kieranm
        Open/ClosedClosed Open
    2007-03-28 kieranm StatusNone Invalid
        Open/ClosedOpen Closed

    Back to the top

    Powered by Savane 3.13-bb6a.
    Corresponding source code