Re: [tcpm] Window update algorithm differences

[Matt Mathis <[e-mail]>]

I don't recall all of the details (since it is part of the spec that I don't 
normally deal with) but I believe that problem has to do with deadlocks caused 
by lost window updates when zero window probing.

The problem is that zero window probes and keep alives have to update SND.WND, 
even though they are technically out of window (but by just one byte).

I believe the failure case is if both directions go into zero window probing, 
and then both ends read queued data (freeing window space) but neither end can 
send data in window to cause the other end to see its new window announcement.

I think the fix is to make first window check smidgen wide, do the window 
update processing, and then exclude the edge case further down, such that the 
net window is the same as 793, as updated by 1323.   I recall a comment 
someplace about "accepting window updates from out of order segments", which 
is the key.

I hope this helps,
--MM--
-------------------------------------------
Matt Mathis     http://staff.psc.edu/mathis
Work:412.268.3319    Home/Cell:412.654.7529
-------------------------------------------
Evil is defined by mortals who think they know
"The Truth" and use force to apply it to others.

On Wed, 11 Jun 2008, Andre Oppermann wrote:

> There is some considerable disagreement on the correctness of the original
> window update test in various operating systems.  Here is an overview of
> the current approaches used by the popular and open source TCP implementations:
>
> RFC793: section 3.9, page 72
>  SND.UNA < SEG.ACK =< SND.NXT, update window but not SND.WU.[SEQ|ACK]
>  (SND.WU.SEQ < SEG.SEQ or (SND.WU.SEQ = SEG.SEQ and SND.WU.ACK =< SEG.ACK))
>  update everything.
>
> Stevens Vol.2: section 29.7, page 981-983
> FreeBSD: src/sys/netinet/tcp_input.c, rev. 1.376
> OpenBSD: src/sys/netinet/tcp_input.c, rev. 1.215
> NetBSD: src/sys/netinet/tcp_input.c, rev. 1.287
>  SEG.SEQ > SND.WU.SEQ or (SEG.SEQ = SND.WU.SEQ and (SEG.ACK > SND.WU.ACK or
>  (SEG.ACK = SND.WU.ACK and SEG.WND > SND.WND))) update everything.
>
> OpenSolaris: src/uts/common/inet/tcp/tcp.c, @swnd_update, rev. 6707
>  SEG.ACK > SND.WU.ACK or SEG.SEQ > SND.WU.SEQ or
>  (SEG.SEQ = SND.WU.SEQ and SEQ.WND > SND.WND) update everything.
>
> Linux: net/ipv4/tcp_input.c, @tcp_ack_update_window(), rel. 2.6.25
>  SEG.ACK > SND.UNA or SEG.SEQ > SND.WU.SEQ or
>  (SEG.SEQ = SND.WU.SEQ and SEG.WND > SND.WND) update everything.
>
> The OpenSolaris code contains some comments about being better in case
> of bi-directional traffic and alleged problems with the RFC793 method.
> The Linux code contains some general comments about the incorrectness
> of the BSD method without further elaboration.
>
> The obvious question is which one is correct or better than the others?
>
> Lets have a look at the basic requirement of the send window update.
>
>  o Only newer than already seen segment should update the send window
>    to prevent old and outdated information being used.
>
>  o All evolves around how to reliably detect newer updates.
>
> Lets have a look at what makes a segment new:
>
>  o When using timestamps, either the reflected TS is higher than the
>    last one we got (we're sending data), or the TS from the other end
>    is newer than what we currently reflect (we're receiving data or
>    a window update).
>    Problem: what to do when the round trip time is faster than the
>    timestamp resolution?  Fall back to the SEQ and ACK checks.
>
>    SEG.TSECR > TS_RECENT_AGE or SEG.TSVAL > TS_RECENT
>
>  o Data we sent has been ack'ed.
>    Problem: None really.  Doesn't trigger on old retransmits or out-of
>    order.
>
>    SEG.ACK > SND.UNA  (and implicit SEG.ACK <= SND.NXT)
>
>  o We receive new data.
>    Problem: out-of order into reassembly queue, retransmits of missing
>    segments, reordering of segments.  Retransmit contains newer value.
>
>    SEG.SEQ > RCV.NXT
>
>  o No data sent or received but window increases.
>    Problem: old delayed segment.  Only allow if window increases.
>
>    SEG.WND > SND.WND
>
>
> Hence I propose the following updated acceptable window update check:
>
>  [1] (TS and SEG.TSECR > TS_RECENT_AGE or SEG.TSVAL > TS_RECENT or
>  [2] SEG.ACK > SND.UNA or
>  [3] (SEG.SEQ > SND.WU.SEQ and SEG.ACK >= SND.UNA) or
>  [4] (SEG.SEQ = SND.WU.SEQ and SEG.ACK = SND.UNA and SEG.WND > SND.WND)
>
> 	SND.WND <- SEG.WND
>  [5]	SEG.SEQ > SND.WU.SEQ
> 		SND.WU.SEQ <- SEG.SEQ
>  [6]	(SND.WU.ACK <- SEG.ACK)
>
> [1] If either timestamp is newer than what we've already seen this
>     is a new segment and the window it contains is certain to be valid
>     without any further checks.
> [2] This is reliable indicator of a genuine window update.  With the
>     arrival of new data that is ack'ed the window also has been updated.
> [3] A higher sequence number tells us new data was received but if
>     the ACK is lower than what we've already seen it must be a retransmit.
> [4] A pure window update if the sequence number is the same, the ACK is
>     not lower than what we've already seen and the advertised window is
>     larger than the one we had.
> [5] Only change the last update that gave us a window update if it is
>     higher than what we have.  This prevents retransmitted or reordered
>     segments without a new ACK from updating our window.  With timestamps
>     we can reliably differentiate retransmits from out-of order segments.
> [6] Tracking the last ACK that updated the window has become unnecessary.
>     SND.WU.ACK is also known as SND.WL2.
>
> Cases:
>
>  o In unidirectional send we trigger always on [2] when our data is ack'ed.
>  o In unidirectional receive we trigger on [3] for in-order segments.  Out
>    of order segments do not update the window unless they advance SND.WU.SEQ.
>    Retransmits are not detected unless timestamps are enabled.  In that case
>    [1] triggers if the RTT is larger than the resolution of the timestamp
>    clock.  Otherwise window updates will resume when all missing segments
>    are retransmitted and new segments beyond SND.WU.SEQ arrive.
>  o In bidirectional traffic we trigger on [3] and [2].  If the transfer has
>    loss or is re-ordered in either or both directions we also trigger in all
>    important cases due to [2] when new data was ack'ed, and [3] new data with
>    an up to date ACK is received.  Above all the timestamp check allows all
>    new segments no matter what order they are in.
>
>
> Feedback and pointing out of mistakes are welcome.
>
> BTW: TAC's are gone for good!
>
> -- 
> Andre
>
> [e-mail]
> _______________________________________________
> tcpm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tcpm
>
_______________________________________________
tcpm mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/tcpm