[bug #19434] Processing of Fast retransmit bug

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

URL:
  <http://savannah.nongnu.org/bugs/?19434>

                 Summary: Processing of Fast retransmit bug
                 Project: lwIP - A Lightweight TCP/IP stack
            Submitted by: olegreen
            Submitted on: Wednesday 03/28/2007 at 12:00
                Category: TCP
                Severity: 3 - Normal
              Item Group: Faulty Behaviour
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

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).





    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #1, bug #19434 (project lwip):

>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?


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #2, bug #19434 (project lwip):

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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Update of bug #19434 (project lwip):

                  Status:                    None => Invalid                
             Open/Closed:                    Open => Closed                

    _______________________________________________________

Follow-up 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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #4, bug #19434 (project lwip):

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?

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #5, bug #19434 (project lwip):

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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #6, bug #19434 (project lwip):

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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Update of bug #19434 (project lwip):

                  Status:                 Invalid => In Progress            
             Assigned to:                    None => kieranm                
             Open/Closed:                  Closed => Open                  

    _______________________________________________________

Follow-up 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.



    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #8, bug #19434 (project lwip):

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)
    _______________________________________________________

Additional Item Attachment:

File name: lwip_rtime.patch               Size:4 KB


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #9, bug #19434 (project lwip):

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...


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #10, bug #19434 (project lwip):

Well spotted - thanks.  

Updated patch attached

(file #12473)
    _______________________________________________________

Additional Item Attachment:

File name: lwip_rtime.patch               Size:5 KB


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Follow-up Comment #11, bug #19434 (project lwip):

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)]


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[bug #19434] Processing of Fast retransmit bug

Ashley Duncan

Update of bug #19434 (project lwip):

                  Status:             In Progress => Fixed                  
             Open/Closed:                    Open => Closed                

    _______________________________________________________

Follow-up Comment #12:

OK, checked in with that additional change.

Thanks for your help!

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?19434>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/



_______________________________________________
lwip-devel mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/lwip-devel