Subject: [tcpm] flow control and fast recovery

From: Alejandro Popovsky <[email-masked]>
Date: Fri, 09 Aug 2013 17:43:41 -0300

Hi,

I have been observing that many connections become limited
by the receiver window during fast recovery, even when this window
is above RTT*maximumPathRate (and using windows scaling).

This is because during fast recovery the congestion window is
artificially inflated on each duplicate ack (after the third). And the
number of unacked bytes may come up to double RTT*maximumPathRate.

For this to be prevented, the receiver may grow its reception window
up to double its size when generating duplicate acks.

I observed this at the traffic of service providers that were having an
important percentage of their traffic limited by flow control (most of the
traffic is generally limited by the network, or by the data generation rate
at the source).

Best regards, Alejandro Popovsky.

---

From: John Leslie <[email-masked]>
Date: Sat, 10 Aug 2013 21:34:34 -0400

> number of unacked bytes may come up to double RTT*maximumPathRate.

   Good catch! I never thought that through...

> up to double its size when generating duplicate acks.

   Does this deserve mention in draft-ietf-tcpm-tcp-rfc4614bis (the
TCP Roadmap)?

--
John Leslie <[email-masked]>

---

From: Michael Welzl <[email-masked]>
Date: Sun, 11 Aug 2013 09:56:54 +0200

>   Does this deserve mention in draft-ietf-tcpm-tcp-rfc4614bis (the

I don't know how that would relate to the roadmap document - but if it's correct (and a bug in the standard, rather than just an implementation), it deserves fixing!

I'm curious to hear what people think about this,

cheers,
Michael

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 11 Aug 2013 01:44:10 -0700

Hi Alejandro,
Is it possible to see tcpdump files for this? It might be better if we
can discuss with real data.
--
Yoshifumi

On Fri, Aug 9, 2013 at 1:43 PM, Alejandro Popovsky <[email-masked]> wrote:
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: [email-masked]
Date: Sun, 11 Aug 2013 14:19:50 -0300

Hi Yoshifumi

I have just left an example connection in:
http://www.palermo.edu/ingenieria/comm/exampleDumpFlowCtrlFastRecovery.pcap

I am leaving also an analysis of the connection showing the flow control 
limitation reached during fast recovery, here:
http://www.palermo.edu/ingenieria/comm/flowCtrlFastRecovery.pdf

Let me know if you want some other examples.

Best regards, Alejandro.

---

From: Christoph Paasch <[email-masked]>
Date: Sun, 11 Aug 2013 21:05:04 +0200

Hello,

> http://www.palermo.edu/ingenieria/comm/exampleDumpFlowCtrlFastRecovery.pcap

the trace looks rather like the receiver has its window capped at 64K. E.g.,
through a socket-option. Because from the beginning on, the announced window
is at 64K and it never changes.

If the client would not cap the window, the autotuning should do its job to
adjust the window at 2*BDP, and thus allow full speed - even during
recovery.

Cheers,
Christoph

> 
> I am leaving also an analysis of the connection showing the flow
> control limitation reached during fast recovery, here:

---

From: Alejandro Popovsky <[email-masked]>
Date: Mon, 12 Aug 2013 03:07:07 -0300

Hi Christoph,

I left another example where the receiver is tuning its receive window, 
but not
as dynamically as to prevent a sender stall during fast recovery:

http://www.palermo.edu/ingenieria/comm/flowCtrlFastRecovery2.pdf

http://www.palermo.edu/ingenieria/comm/exampleDumpFlowCtrlFastRecovery2.pcap

Best regards, Alejandro.

On 11/08/13 04:05 PM, Christoph Paasch wrote:
>>> On Fri, Aug 9, 2013 at 1:43 PM, Alejandro Popovsky wrote:
>>>> Hi,
>>>>

---

From: Mark Allman <[email-masked]>
Date: Mon, 12 Aug 2013 07:52:33 -0400

> I don't know how that would relate to the roadmap document - 

Yeah - seems misplaced there.

> but if it's correct (and a bug in the standard, rather than just an
> implementation), it deserves fixing!

It is correct.  It has been that way for a very long time.  It is not "a
bug in the standard" that can be readily fixed, it is fundamental.
I.e., the receiver has said "do not send more than X bytes" and yet the
sender's congestion control would allow it to send more than X bytes if
the advertised window space was there.  But, it isn't, so what is the
sender to do?  Send bytes in the hopes that by the time they get there
perhaps there will be room in the receive buffer to hold them?

The fix is more buffering at the receiver.  We can give guidance on
that, but at the end of the day there is no bug here.  This is how TCP
is supposed to work.  I.e., the receiver is supposed to be able to limit
the sender via flow control.  And, the sender is supposed to pick its
sending rate based on the network conditions, but with a limit of no
faster than the receiver has advertised it can take data.

allman

---

From: "Zimmermann, Alexander" <[email-masked]>
Date: Mon, 12 Aug 2013 13:31:14 +0000

Am 12.08.2013 um 13:52 schrieb Mark Allman <[email-masked]>:

> The fix is more buffering at the receiver.

This is for example exactly what Linux do. It only announces the
half of the socket buffer at the beginning of the connect to have enough
room for growing during recovery. (But maybe this is not true anymore due to
some patches from Google. Yuchung should know this :-) )

Alex

>  We can give guidance on

---

From: Rick Jones <[email-masked]>
Date: Mon, 12 Aug 2013 08:08:22 -0700

> some patches from Google. Yuchung should know this :-) )

I think you will find that Linux can more than double the receive window it will advertise over the life of a connection (and correspondingly increase its SO_SNDBUF).  Take a look at tcp_rmem and tcp_smem.  I think you will find that if you look at the SO_[RCV|SND]BUF at the beginning of a connection on which setsockopt() has not been called, they will be at the second of the three values in each sysctl.  If you look again at the end of a reasonably long-lived connection they will have grown to the values in the third value.

One way to see this with netperf:

netperf -H <remote> -- -o lss_size,lss_size_end,rsr_size,rsr_size_end

I suspect that will track rather closely with what one sees in a packet trace.

rick jones

---

From: Yuchung Cheng <[email-masked]>
Date: Mon, 12 Aug 2013 09:42:04 -0700

> some patches from Google. Yuchung should know this :-) )

The Linux receiver buffer auto-tuning is buggy. The rule of thumb is
to keep rwin 2 times (estimated) cwin for limited transmit during fast
recovery but it does not. That bug was hidden for years until Linux
sender uses Proportional Rate Reduction to recover losses quicker and
the prior rate-halving algorithm is sorta broken.

In addition to slowing down fast recovery, it also causes burst right
after recovery when all lost packets are acked (which may lead to
another loss). Not sure about other stacks tho.

Mirja's preso in tcpm mentioned about this too (slide 6)
http://www.ietf.org/proceedings/87/slides/slides-87-tcpm-10.pdf

---

From: Yoshifumi Nishida <[email-masked]>
Date: Mon, 12 Aug 2013 22:39:48 -0700

Hi Alejandro,

Thanks for the dump file.
Please correct me if I miss something.

During the first retransmit and fast recovery, the sender can transmit
2/sender's cwnd - MSS bytes of new data. (because 1MSS is consumed by
retransmission)
This means in the worst case, you will need to have 3/2 sender's cwnd
receiver buffer to keep all data transmitted during this period.
But, the worst case can only happen when the retransmit segment by
fast retransmit arrives after all new data has arrived.
(Another example will be a case where the receiver's application
becomes slow to read data all of sudden during loss recovery.)

You're right that if we want to prepare the worst case, the receiver
will need 1.5 times larger size of buffer than the sender's buffer.
But, I'm not sure this is a problem. Because I'm not very sure TCP
needs to guarantee full performance when sender's buffer size equals
receiver's buffer size.

In your tcpdump, the first retransmit segment by fast retransmit seems
to be lost, hence you got extra dup acks.
But, I think this is not a situation that fast retransmit logic expects.

Thanks,
--
Yoshifumi

On Sun, Aug 11, 2013 at 11:07 PM, Alejandro Popovsky <[email-masked]> wrote:
> Hi Christoph,
>
> I left another example where the receiver is tuning its receive window, but
> not

---

From: Yuchung Cheng <[email-masked]>
Date: Tue, 13 Aug 2013 08:56:55 -0700

> needs to guarantee full performance when sender's buffer size equals
It's not about sender's buffer size.

It'll be easier to explain with time sequence graph, but I doubt this
list allows binary attachment so
try this
tcptrace -CSzxy <pcap> && xplot.org b2a_tsg.xpl

During the recovery, the rwin remains stale and the yellow line is horizontal.

The fundamental problem is that the receiver (likely a Linux box) does
not account for OOO packets received to adjust RWIN.
But congestion control, or cwin, does account for SACKed packets and
retransmits.

When the receiver have too many OOO packets it unintentionally thwart
the sender, creating a bubble in the data pipeline at 5s.

Due to bufferbloat, by the time the loss happens, the network has
buffered a ton. By the time the fast retransmit finally arrives to
repair the losses, the rwin opens up the flood gate, hence the big
jump of the yellow line. Interesting the sender is probably
application-limited so it didn't send out a burst.

So the receiver is unintentionally throttling the sender to make
forward progress during recovery. Not a good idea unless the receiver
really can't afford the extra 100KB.

---

From: Tim Shepard <[email-masked]>
Date: Mon, 12 Aug 2013 13:59:04 -0400

> http://www.palermo.edu/ingenieria/comm/exampleDumpFlowCtrlFastRecovery2.pcap

I took a look at that trace.

Note that in this trace that there was apparently no delay at all in
delivering the whole transfer of data to the receiver.  This can be
seen by plotting the acknowledgement numbers returned as a function of
the time the acknowledgement numbers were recevied by the sender
(which can serve as a fairly good proxy for the time the data was
received by the receiver).

If you look at the acknowledgement numbers vs time before and after
the loss and recovery episode you can see that they are colinear,
which indicates that the loss and recovery event never let the queue
at the bottleneck go empty, so there was always useful data to be sent
through the bottleneck, so it never went idle.  And apparently the
SACK blocks got enough information to the sender so that the recovery
episode wasted no time sending duplicate data through the bottleneck.

The end-to-end flow control window appears to be much larger than it
needs to be to enable the sender to saturate the bottleneck link on
the path.

This example does show significant queue bloat at the bottleneck.  It
would be nice to see this same demo with codel or fq_codel managing
the queue length at the bottleneck.

A few pictures attached below.  ( Also the .xplot.gz file for those of
you with a working copy of my xplot program. )

			-Tim Shepard
			 [email-masked]

---

From: Alejandro Popovsky <[email-masked]>
Date: Wed, 14 Aug 2013 05:06:16 -0300

Hi Tim

You are right. "Thanks" to buffer-bloating, throughput at the receiver
side never went down even when the sender stalled.

It looks like "loss-based congestion detection" at the sender
combined with receivers with "big RWIN" or "auto-tuning RWIN" avoid
interruption of data flow at the receiver during "fast recovery RWIN
limitations" because of large buffer accumulation (although this
may not be desirable).

"Delay based congestion detection" would not have this large buffer
accumulations when fast recovery happens but might be further away
from the RWIN limit.

Best regards, Alejandro.

P.S. A receiver with auto tuning, detecting that RTT is growing too much
because of the sender just "trying to fill the pipe", could decrease RWIN
(but not during fast recovery) without noticeable decrease in throughput.

>			 shep at alum.mit.edu

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 14 Aug 2013 01:19:05 -0700

Hi Yuchung,

I tried to mention how much buffer size will be required to guarantee
fast retransmit and fast recovery works propoerly.
But, I'm not very sure if this plot is a proper example for detailed
discussions on standards. Because the behavior of the sender is a bit
strange to me.
It seems that it tries to do rate halving (or PRR) at the beginning of
recovery, but it speeds up after a while even though it stills in
recovery phase.
This aggressive increase will require more buffer space at the
receiver, but I think it's not a standard behavior.
Thanks,
--
Yoshifumi

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 14 Aug 2013 08:36:13 -0700

> recovery, but it speeds up after a while even though it stills in
I am pretty sure it's doing PRR as specified in the RFC
http://tools.ietf.org/html/rfc6937#section-3

Note once the pipe is below ssthresh PRR will do slow-start, just like
normal CC.

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 14 Aug 2013 22:13:28 -0700

Hi Yuchung,

> Note once the pipe is below ssthresh PRR will do slow-start, just like

Oh. I see. Thanks for pointing out.
Then, I think at least we should avoid slow-start increase when TCP
retransmits retransmited packets, although I don't have a clear idea
for the best behavior in this kind of situation, yet.
Because this is basically an indication of packet loss during recovery
phase. (or, spurious RTO caused by bufferbloat, but even so, I think
we'll still need to slow down)
--
Yoshifumi

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 20 Aug 2013 07:01:22 +0000

HI Yoshifumi,

> retransmits retransmited packets, although I don't have a clear idea for
> the best behavior in this kind of situation, yet.
> phase.

So far, lost retransmission detection, or fast recovery of a lost retransmission, has not been mentioned in any RFC; the default behavior of stack compliant with the RFCs is to run into a RTO - which is a pretty hefty reaction to continued loss (congestion indication) during recovery. OTOH, one particular OS has demonstrated, that by simply ignoring the congestion signal due to lost retransmissions also doesn't lead to an instant network meltdown.

Once I've finished what I'm currently focused on, I would like to submit a paper to sketch out lost retransmission detection and recovery (with SACK). I think such a draft would be the proper place to mention the expected behavior.

Best regards,

Richard Scheffenegger

---

From: Yoshifumi Nishida <[email-masked]>
Date: Thu, 22 Aug 2013 08:36:39 -0700

Hi Richard,

> So far, lost retransmission detection, or fast recovery of a lost retransmission, has not been mentioned in any RFC; the default behavior of stack compliant with the RFCs is to run into a RTO - whi…

I agree that this is an interesting and an important point. As
bufferbloat tends to increase cwnd, we might run into situations where
we see congestion indications during recovery while ACK clocking is
still working more often.
--
Yoshifumi