Re: [lwip-users] Recent tcp_rexmit() changes

[K.J. Mansley]

On Thu, 2004-07-22 at 20:20, Karl Jeacle wrote:

> The new Stevens-inspired Fast Retransmit code in tcp_receive() makes
> sense, and therefore the change in tcp_rexmit() to move just a single
> unacked segment to the unsent queue instead of all unacked segments
> seems to make sense too. I was happy to see a bug fix!
> 
> However, these changes have an impact on how tcp_output() operates.
> Lines 435-436 of tcp_out.c initiate a while loop that outputs segments
> from the unsent queue:
> 
>   while (seg != NULL &&
>   ntohl(seg->tcphdr->seqno) - pcb->lastack + seg->len <= wnd) {
> 
> The difference between the seqno of the first segment on the unsent
> queue and the last ackno will normally be less than the window, so
> segments are output as you would expect.
> 
> But what happens if A is sending data to B, large windows are in use,
> and a number of packets are dropped? What will the new code do?

I can see your problem, and how the previous behaviour would have
avoided it.  However, having had a good read through TCP/IP Illustrated
I think what we currently have is the "correct" behaviour.

> FR will halve the window, and the new tcp_rexmit() will place just one
> unacked segment at the start of the unsent queue. This segment will
> pass the while() check above and be transmitted, but the next segment
> on the queue will have a much higher sequence number, and the halved
> window will mean that the while() condition fails, and so tcp_output()
> cannot send any more data.

Unfortunately it would seem that this is intentional, and part of the
congestion avoidance algorithm.  If there has been only a single packet
loss (the sort of thing FR is intended to help with) subsequent received
acknowledgements (assuming you had >3 segments in flight) will trigger
further transmissions as the cwnd is increased each time, eventually
allowing more data out.  Only sending one packet avoids (i)
retransmitting lots of packets that might not have been lost and (ii)
causing a spike in traffic that might overload whatever it was that got
overloaded and dropped the packet in the first place.

However, if there have been many segments lost you won't get the
duplicate acks (as they rely on out of order packets, i.e. some that
have not been lost!) and so the normal "slow" retransmit algorithm will
come into play...

> tcp_slowtmr() will eventually call tcp_rexmit(), and one more unacked
> segment will be moved to the unsent queue and transmitted. This cycle
> of tcp_slowtmr() calling tcp_rexmit() to send one segment will continue
> until all missing segments have arrived at the receiver. If a large
> window is used and several packets are dropped, this causes a serious
> delay in transmission.

What should happen here, and this is where I'm not sure if we're right
or not, is that the sender should re-enter slow start.  The congestion
window should be set to 1 segment, and then increased by 1 segment each
time an acknowledgement is received.  (NB. I don't think the
acknowledgement needs to be for new data).  This should allow increasing
numbers of segments to be released from the unsent queue, but does
require many round trip times to recover to previous levels.

> Previously what happened was that ALL unacked segments were placed
> on the unsent queue, so despite the halving of the window, the while()
> condition would succeed, and tcp_output() would just continue (re)sending
> older unacked segments before starting to send new segments again.
> 
> Introducing the new more economical tcp_rexmit() code means that we'll
> need a smarter tcp_output() that doesn't choke when a number of older
> unacked segments suddenly need to be retransmitted.

I suspect the problem, if any, is in the slow retransmit, slow start
recovery portion.  As you are able to observe this problem, would it be
possible for you to (with a little debug tracing) see if slow start is
performing as it should?

If it is, then you might just be seeing the fact that, when faced with
many lost segments, TCP backs off dramatically.  If anyone can see
somewhere that I've gone wrong, please do correct me - this is a fairly
complex part of the protocol.

Kieran