Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

[David Borman <[e-mail]>]

Probably the more correct way of stating it is that ACK-only packets should be sent with the largest in-window sequence number that has ever been sent.  It is the only way to guarantee that the sequence number of the ACK will be within the window at the receiving side.

That being said, probe packets can be out of window.  And if the window is truly closed, you don’t want to send and ACK-only packet with that sequence number, as it will also be out of window.  Hence, send ACK-only packets with the largest in window sequence number.  In the BSD code probes are only one byte, and in persist state SND.NXT will be the largest in-window that has ever been sent.  But if we are in persist state because the ACK was lost or the window just opened and the probe data is accepted, the ACK will be to the left of the window by the size of the probe packet.  Hence the receiver needs to accept ACK packets one byte to the left of the window to prevent an ACK war.  The more general case is that you need to accept ACKs of at least N bytes to the left of the window, where N represents the largest size of probe that you will ever send.  That, along with sending ACKs with the largest in-window sequence number, will guarantee that you don’t get into an ACK war, even the two sides have different values for N  (only one side needs to accept the ACK to stop the ACK-war, and that will happen on the side with the larger value for N).

			-David Borman

> On Aug 15, 2016, at 5:39 PM, Yoshifumi Nishida <[e-mail]> wrote:
> 
> Hello,
> I personally think this is an interesting corner case for discussion. 
> It looks a minor one, but I'm not not very sure if we can leave it for each implementation. 
> I also guess a question would be if the BSD's fix is the best way for the issue.
> 
> Thanks,
> --
> Yoshi
> 
> On Thu, Aug 11, 2016 at 1:46 PM, Kobby Carmona <[e-mail]> wrote:
> Hi David,
> This makes a lot of sense. We will fix our code.
> Thanks for your help on this,
> 
> BTW,
> Is this issue of mentioned in any RFC? If not do you see a point in adding explicit note on the SEQ of pure ACK in case of retransmission?
> 
>        Kobby
> 
> -----Original Message-----
> From: David Borman [mailto:[e-mail]]
> Sent: Monday, August 08, 2016 12:35 AM
> To: Kobby Carmona <[e-mail]>
> Cc: [e-mail]
> Subject: Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time
> 
>> On Aug 7, 2016, at 3:37 AM, Kobby Carmona <[e-mail]> wrote:
>> 
>> Hi David,
>> The code below is true for fast-retransmit.
>> But in case of retransmit timer expiration (TCPT_REXMT) snd_nxt is set to snd_una. And in this case CQND will be set to 1MSS so in the example below the transmitters can send only a single segment from sequence 2000/12000.
> 
> Your underlying problem is that the ACK-only packets are being sent with the wrong sequence number, and that is what is causing them to be dropped.  One way to fix that is to put SND.NXT back to its previous value after do the the retransmit.  But you are correct, in the BSD code it only does that in the fast retransmit code; when the timer based retransmit code fires, it just pulls back SND.NXT to SND.UNA.  However, in the BSD code that I’m looking at, it keeps track of the largest sequence number sent in SND.MAX, and in the tcp_output() path there is this bit of code:
> 
>       /*
>        * If we are doing retransmissions, then snd_nxt will
>        * not reflect the first unsent octet.  For ACK only
>        * packets, we do not want the sequence number of the
>        * retransmitted packet, we want the sequence number
>        * of the next unsent octet.  So, if there is no data
>        * (and no SYN or FIN), use snd_max instead of snd_nxt
>        * when filling in th_seq.  But if we are in persist
>        * state, snd_max might reflect one byte beyond the
>        * right edge of the window, so use snd_nxt in that
>        * case, since we know we aren't doing a retransmission.
>        * (retransmit and persist are mutually exclusive...)
>        */
>       if (len || (flags & (TH_SYN|TH_FIN)) || tp->t_timer[TCPT_PERSIST])
>               th->th_seq = htonl(tp->snd_nxt);
>       else
>               th->th_seq = htonl(tp->snd_max);
> 
> That is what your implementation appears to be missing, and what is causing your ACK storm.  So yes, some variant of your problem has been seen before, and this is how the BSD code fixed it.
> 
>                        -David Borman
> 
>> 
>>      Kobby
>> 
>> -----Original Message-----
>> From: David Borman [mailto:[e-mail]]
>> Sent: Thursday, August 04, 2016 10:37 PM
>> To: Kobby Carmona <[e-mail]>
>> Cc: [e-mail]
>> Subject: Re: [tcpm] Possible deadlock scenario with retransmission on
>> both sides at the same time
>> 
>> After you pull back SND.NXT and do the retransmission, you should then restore SND.NXT back to where it was, not leave it at the backed off value; then the ACKs wouldn’t be dropped, since they wouldn’t have old seq values.  For example, in the 4.4BSD fast retransmit code it had:
>> 
>>                      tcp_seq onxt = tp->snd_nxt;
>>                      ...
>>                      tp->snd_nxt = th->th_ack;
>>                      ...
>>                      (void) tcp_output(tp);
>>                      ...
>>                      if (SEQ_GT(onxt, tp->snd_nxt))
>>                              tp->snd_nxt = onxt;
>> 
>> 
>>                      -David Borman
>> 
>>> On Aug 4, 2016, at 4:08 AM, Kobby Carmona <[e-mail]> wrote:
>>> 
>>> Hi all,
>>> While running a bidirectional scenario with random drops in a network simulator of our (QLogic's NIC) TCP stack we found a case where it seems there is deadlock in the TCP protocol (the connection will keep sending pure acks from both sides until RTO will expire multiple times and a RST will sent to close the connection).
>>> The scenario is as follows (there is an example with numbers for each stage assuming the MSS and each packet is 1000B):
>>> 1. Both sides are transmitting data and a single packet is dropped on either side and the next two packets are received properly
>>>     Side A - SND.MAX=3000, SND.NXT=3000, SND.UNA=1000, RCV.NXT=11000, out-of-order block 12000-13000
>>>     Side B - SND.MAX =13000, SND.NXT =13000, SND.UNA=11000,
>>> RCV.NXT=1000, out-of-order block 2000-3000 2. RTO timer expires on both sides
>>>     Side A - SND.MAX=3000, SND.NXT=1000, SND.UNA=1000, RCV.NXT=11000, out-of-order block 12000-13000
>>>     Side B - SND.MAX =13000, SND.NXT=11000, SND.UNA=11000, RCV.NXT=1000,
>>> out-of-order block 2000-3000 3. Both sides transmit a single packet to the peer:
>>>     A->B - pkt.seq=1000, pkt.ack=11000, len=1000
>>>     B->A - pkt.seq=11000, pkt.ack=1000, len=1000 3. Both sides receive
>>> the packets and update the receive context:
>>>     Side A - SND.MAX=3000, SND.NXT=2000, SND.UNA=1000, RCV.NXT=13000
>>>     Side B - SND.MAX=13000, SND.NXT=12000, SND.UNA=11000, RCV.NXT=3000 4.
>>> Both sides send another segment:
>>>     A->B - pkt.seq=2000, pkt.ack=13000, len=1000
>>>     B->A - pkt.seq=12000, pkt.ack=3000, len=1000 5. Both sides don't
>>> accept the packet (and don't update SND.UNA) since the sequence on the packet is less than RCV.NXT (sequence number check in page 69 of RFC793) and send a pure ACK instead
>>>     A->B - pkt.seq=2000, pkt.ack=13000, len=0 (pure ACK)
>>>     B->A - pkt.seq=12000, pkt.ack=3000, len=0 (pure ACK) 6. This will
>>> continue forever (until the connection will be terminated by RST) since every packet that ends before RCV.NXT (even a retransmit from SND.UNA) will be dropped.
>>> 
>>> Did anyone encountered this issue before? Is the anything we missed on this sequence?
>>> If this is indeed a real deadlock, there might be several solutions to this which will require a modification in receive processing of RFC793. But I would like to know if you think this is a real issue before dealing with solutions.
>>> Thanks,
>>> 
>>>     Kobby
>>> 
>>> 
>>> _______________________________________________
>>> tcpm mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/tcpm
>> 
>> _______________________________________________
>> tcpm mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/tcpm
> 
> _______________________________________________
> tcpm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tcpm
> 
> _______________________________________________
> tcpm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tcpm