Subject: [tcpm] TCP window updates combined with dup acks sent in response to packet loss

From: Lawrence Stewart <[email-masked]>
Date: Thu, 12 Mar 2015 01:37:16 +1100

[BCCed to [email-masked]]

Hi all,

Please consider the code below from FreeBSD 10.1's TCP input processing:

        /*
         * In ESTABLISHED state: drop duplicate ACKs; ACK out of range
         * ACKs.  If the ack is in the range
         *      tp->snd_una < th->th_ack <= tp->snd_max
         * then advance tp->snd_una to th->th_ack and drop
         * data from the retransmission queue.  If this ACK reflects
         * more up to date window information we update our window
information.
         */
        case TCPS_ESTABLISHED:
        case TCPS_FIN_WAIT_1:
        case TCPS_FIN_WAIT_2:
        case TCPS_CLOSE_WAIT:
        case TCPS_CLOSING:
        case TCPS_LAST_ACK:
                if (SEQ_GT(th->th_ack, tp->snd_max)) {
                        TCPSTAT_INC(tcps_rcvacktoomuch);
                        goto dropafterack;
                }
                if ((tp->t_flags & TF_SACK_PERMIT) &&
                    ((to.to_flags & TOF_SACK) ||
                     !TAILQ_EMPTY(&tp->snd_holes)))
                        tcp_sack_doack(tp, &to, th->th_ack);

                /* Run HHOOK_TCP_ESTABLISHED_IN helper hooks. */
                hhook_run_tcp_est_in(tp, th, &to);

                if (SEQ_LEQ(th->th_ack, tp->snd_una)) {
                        if (tlen == 0 && tiwin == tp->snd_wnd) {
                                TCPSTAT_INC(tcps_rcvdupack);

                                <dupack processing omitted>

Now for a dupack to be treated as such for the purposes of triggering
fast retransmit/fast recovery, the dupack must not update the window as
per the "tiwin == tp->snd_wnd" condition above, which has existed since
at least BSD 4.4 (I didn't bother looking further back in history).

Grenville (CCed) has encountered proof of this condition forcing
connections to recover via RTO when legitimate dupacks sent in response
to a packet loss also contain a window update.

In the example tcpdump excerpt attached, the advertised receive window
is growing as the Linux receiver side app reads data from the socket
buffer while the dupacks are generated. The FreeBSD sender side sees
them as window updates and processes them as such, bypassing the dupack
processing code. The send window is consumed and because only dup acks
are returning, UNA is not advanced and so the connection stalls,
requiring two RTOs to recover from the 2 dropped packets.

With SACK in the mix as is the case for the provided example, it seems
obvious to me that the existence of SACK blocks could and should be used
to realise that a window update combined with a dupack is not a pure
window update and therefore should be processed by the dupack handling
code for fast retransmit/fast recovery purposes.

For connections without SACK, is there any existing guidance on how to
deal with this? My Google fu and skimming of the RFCs that seemed
relevant to this matter turned up nothing, and so I'm imagining a
potential algorithm for inferring if a window update can count as a
dupack for fast retransmit/fast recovery purposes or not. Wanted to get
some input from others before spending any more time on it though.

Cheers,
Lawrence

---

From: Mark Allman <[email-masked]>
Date: Wed, 11 Mar 2015 10:48:38 -0400

> fast retransmit/fast recovery, the dupack must not update the window 

Right, per RFC 5681.

> code for fast retransmit/fast recovery purposes.

Right, per RFC 6675.

allman

---

From: Lawrence Stewart <[email-masked]>
Date: Thu, 12 Mar 2015 02:35:58 +1100

Hi Mark,

>> fast retransmit/fast recovery, the dupack must not update the window 

But does 5681 (and its predecessors) document the implementation, or did
this specific bit of the implementation come about from some work?

>> code for fast retransmit/fast recovery purposes.

Gah, I missed the key bit of text near the end of the definitions
section when I skimmed earlier. Thanks for the (re)pointer.

Question still remains whether relaxing the 5681 definition that a
dupack for fast retransmit/fast recovery purposes can't update the
window is something that could/should be considered for non-SACK
connections. Does anyone recall any attempts to specify such an
algorithm? Is it not worth the effort given the prevalence of SACK?

Cheers,
Lawrence

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 11 Mar 2015 09:01:08 -0700

> algorithm? Is it not worth the effort given the prevalence of SACK?
not worth the effort IMO

>
> Cheers,
> Lawrence
>
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Mark Allman <[email-masked]>
Date: Wed, 11 Mar 2015 12:19:04 -0400

> > Right, per RFC 5681.
> 
> But does 5681 (and its predecessors) document the implementation, or
> did this specific bit of the implementation come about from some work?

The spec followed the implementation.  For all of 5681.

The rule makes perfect sense.  An ACK that rolls in with the same ACK
number and an updated advertised window is ambiguous.  Just as an ACK
with the same ack number we have previously seen but with data on it is.
We are just deciding to key on an unambiguous signal in this case.  That
makes good sense to me.

> algorithm? Is it not worth the effort given the prevalence of SACK?

If you care about RTOs enough to want to add a bunch of goop to infer
cases where loss and window updates happen simultaneously and therefore
make it hard to collect the requisite number of dupacks then you should
care enough to use SACK.  And, SACK is so widely supported I can't see
how the right answer to this question is anything but "use SACK".

allman

---

From: Lawrence Stewart <[email-masked]>
Date: Thu, 12 Mar 2015 12:10:50 +1100

> We are just deciding to key on an unambiguous signal in this case.  That

It does indeed make sense as a conservative default. I was just curious
about the history.

> how the right answer to this question is anything but "use SACK".

I desperately want to agree with you and draw a line under this, but at
Netflix we still see non-zero percentages of non SACK flows from various
classes of consumer electronics device which is annoying and something I
have no control over.

I don't have recent numbers at hand, but over a ~72 hour period ~12
months ago, there were ~60 device classes out of ~400 that had 1% or
higher of non SACK flows, and of those ~60, ~5 had 5% or higher non SACK
flows with the highest being 8%. Most of those 60 device classes don't
make up any sizeable proportion of our total number of flows, but it
would obviously be preferable to achieve the best experience possible on
any Netflix enabled device. I will have fresh data in the coming weeks
after we roll out some permanent logging changes I've been working on.

I shall ponder some more. Thanks to you and Yuchung for the input.

Cheers,
Lawrence

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 11 Mar 2015 20:41:56 -0700

> after we roll out some permanent logging changes I've been working on.
I suspect that some lack of sack was due to stupid middleboxes
removing sack options. They don't know what they are missing.

If we spend time to make non-sack happier they stay alive happily.
SACK is the most useful feature I've seen in TCP beyond 793.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 13 Mar 2015 10:42:40 +0000

Lawrence,

Well, I can see that very light-weight implementations of TCP don't support SACK (IoT; but then, SoCs are nowadays powerful&cheap enough and have enough memory to deal with at least a minimum SACK implementation).

For devices capable of decoding video streams, there really is no excuse to not deploy a SACK capable TCP stack; have you tested those devices that you mention which don't support SACK in house and ruled out path interference (ie. meddleboxes removing SACK, when they do some Seq# rewriting etc)?

Because of the above, I would suspect that you are probably looking at such path impairments rather than end-device impairments...

OTOH, You may want to look into TLP [1]. TLP is also only defined for SACK-enabled sessions;

One thought: If you have TS enabled on these real-world flows you mentioned, and the data transmitted just before has all those packets sent with newer timestamps then the one in the window update - perhaps that could be a high enough bar to do a one-time TLP in NewReno...

One would assume that for a genuine window-update, the reflected timestamps wouldn't go stale for that long (>1RTT).

Perhaps combining the information with what you have in TS may be conservative enough, to do a TLP one RTT after the 3rd window update; note that a non-SACK TLP will have to be the next segment after SndUna, not the highest.

But when you are implementing this, you probably need to be wary of Eifel detection IPR.

In this particular case, of course SACK should have triggered the fast retransmission.

Best regards,
  Richard

[1] https://tools.ietf.org/html/draft-dukkipati-tcpm-tcp-loss-probe-01

> -----Original Message-----
> From: tcpm [mailto:[email-masked]] On Behalf Of Yuchung Cheng
> Sent: Donnerstag, 12. März 2015 04:42
> To: Lawrence Stewart
> Cc: [email-masked] Extensions; [email-masked]
> Subject: Re: [tcpm] TCP window updates combined with dup acks sent in
> response to packet loss
>

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sat, 14 Mar 2015 11:36:33 -0700

Hi Lawrence,

On Wed, Mar 11, 2015 at 8:35 AM, Lawrence Stewart <[email-masked]>
wrote:

> algorithm? Is it not worth the effort given the prevalence of SACK?

Can't we send window updates and dupack separately by using different ACKs?
Then, we don't have to relax the 5681 definition.
--
Yoshi

---

From: Rick Jones <[email-masked]>
Date: Sat, 14 Mar 2015 15:02:38 -0700

On 03/14/2015 11:36 AM, Yoshifumi Nishida wrote:
> Hi Lawrence,
>
> On Wed, Mar 11, 2015 at 8:35 AM, Lawrence Stewart <[email-masked]
> <mailto:[email-masked]>> wrote:
>

I've not memorized TCP chapter and verse, but I suspect it is only a 
SHOULD that one bundle ACKs and window updates.  Still, in the broadest 
handwaving sense, particularly with the presence of the stateless 
offloads and I suppose copy avoidance, sending a standalone ACK or 
window update is just as many CPU cycles as sending a data segment.

And I suppose considering something like segmentation offload, sending 
an ACK may actually be more expensive than sending a data segment, since 
one will get multiple data segments in a single trip down the protocol 
stack.  And receive-offload means receiving a bare ACK or window update 
is more expensive than receiving a data segment for the same sort of 
(somewhat handwaving) reasoning.

rick jones

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sun, 15 Mar 2015 14:27:42 +0000

Hi Rick,

Isn't most hardware doing receive-offload only on in-sequence segments?

Both window updates and reordering (loss) would be handled by the CPU TCP stack, I would assume (but it's been a while since I last studied offload-engine datasheets).

I raised my suspicion that the effect he observes is likely on a path where something disallows SACK - and it would probably make more sense to put effort in fixing such broken paths.

Perhaps Lawrence can come up with (anonymized) samples of the issue; if TS works there, and the sender has a reasonable good understanding of the RTT, something like TLP might be safe enough to do... short of RTO recovery.

Best regards,
  Richard

> From: tcpm [mailto:[email-masked]] On Behalf Of Rick Jones
> Sent: Samstag, 14. März 2015 23:03
> To: [email-masked]
> handwaving sense, particularly with the presence of the stateless offloads
> and I suppose copy avoidance, sending a standalone ACK or window update is
> just as many CPU cycles as sending a data segment.
> 
> And I suppose considering something like segmentation offload, sending an
> ACK may actually be more expensive than sending a data segment, since one
> will get multiple data segments in a single trip down the protocol stack.
> And receive-offload means receiving a bare ACK or window update is more
> expensive than receiving a data segment for the same sort of (somewhat
> handwaving) reasoning.
> 
> rick jones
>

---

From: Rick Jones <[email-masked]>
Date: Wed, 18 Mar 2015 13:15:30 -0700

On 03/15/2015 07:27 AM, Scheffenegger, Richard wrote:
> Both window updates and reordering (loss) would be handled by the CPU
> TCP stack, I would assume (but it's been a while since I last studied
> offload-engine datasheets).

In the Linux world at least, Large Receive Offload in hardware has been 
"deprecated" in favor of Generic Receive Offload part-way up the stack. 
  The shift was to address concerns on routers where LRO would lead to 
bogus PathMTU hits.

I perhaps simply extrapolated too far from the "can't we separate ACKs 
and window updates" comment to assume it was meant for the normal data path.

rick

> I raised my suspicion that the effect he observes is likely on a path
> where something disallows SACK - and it would probably make more
> sense to put effort in fixing such broken paths.
>
> Perhaps Lawrence can come up with (anonymized) samples of the issue;
> if TS works there, and the sender has a reasonable good understanding
> of the RTT, something like TLP might be safe enough to do... short of
> RTO recovery.

---

From: Ted Faber <[email-masked]>
Date: Wed, 18 Mar 2015 13:28:10 -0700

> "deprecated" in favor of Generic Receive Offload part-way up the stack.

Hi, Rick.

On a related note, a student working with Joe Touch and me on
implementing the Extended Data Option (EDO) in Linux has encountered
some interactions with GRO.  We'll have a tech report with the details
out in a couple days (including the code) and Joe's sending a
presentation to the Dallas IETF.

If you're knowledegable about GRO - and it sounds like you are - we'd
love to get some feedback.

Thanks!

-- 
Ted Faber
http://www.isi.edu/~faber           PGP:
http://www.isi.edu/~faber/pubkeys.asc
Unexpected attachment on this mail? See
http://www.isi.edu/~faber/FAQ.html#SIG

---

From: Lawrence Stewart <[email-masked]>
Date: Mon, 23 Mar 2015 14:44:57 -0500

Hi Richard,

Apologies for the delay.

On 03/13/15 21:42, Scheffenegger, Richard wrote:
> Lawrence,
>
> Well, I can see that very light-weight implementations of TCP don't
> support SACK (IoT; but then, SoCs are nowadays powerful&cheap enough
> and have enough memory to deal with at least a minimum SACK
> implementation).
>
> For devices capable of decoding video streams, there really is no
> excuse to not deploy a SACK capable TCP stack; have you tested those
> devices that you mention which don't support SACK in house and ruled
> out path interference (ie. meddleboxes removing SACK, when they do
> some Seq# rewriting etc)?

There's a mix. I know for sure that some of the devices weren't
advertising SACK, and others I have no idea if it was the device or a
middle box. After I finish gathering some fresh data to determine how
often Netflix is seeing window updates combined with dup acks for non
SACK flows which end up triggering an RTO, I'll be able to figure out
whether this is worth looking into deeper or not.

I just wanted to initiate this initial discussion to figure out what the
history around this topic was and gather some thoughts.

> Because of the above, I would suspect that you are probably looking
> at such path impairments rather than end-device impairments...

 From my perspective, it makes no difference - if I have to try ensure
the highest possible user experience across a TCP session that is being
crippled by stupid middle boxes, lucky me :/

> OTOH, You may want to look into TLP [1]. TLP is also only defined for

Implementing TLP for FreeBSD has been on my todo list for some time
unless someone beats me to it.

> One thought: If you have TS enabled on these real-world flows you
> mentioned, and the data transmitted just before has all those packets
> sent with newer timestamps then the one in the window update -
> perhaps that could be a high enough bar to do a one-time TLP in
> NewReno...
>
>
>
> One would assume that for a genuine window-update, the reflected
> timestamps wouldn't go stale for that long (>1RTT).
>
> Perhaps combining the information with what you have in TS may be
> conservative enough, to do a TLP one RTT after the 3rd window update;
> note that a non-SACK TLP will have to be the next segment after
> SndUna, not the highest.
>

Sounds plausible. I'll revisit this discussion once I have some fresh 
data at hand.

> In this particular case, of course SACK should have triggered the

Indeed.

Cheers,
Lawrence

---

From: Lawrence Stewart <[email-masked]>
Date: Mon, 23 Mar 2015 15:55:01 -0500

Hi Yoshifumi,

Apologies for the delay.

> Then, we don't have to relax the 5681 definition.

We certainly could, but the existence proof that Linux doesn't and the 
fact that it's perfectly legitimate wire behaviour puts this issue in 
the grey area. That being said, I'm not advocating any particular course 
of action - just interested in exploring the history and gathering thoughts.

Cheers,
Lawrence