Subject: [tcpm] Updating Proportional Rate Reduction RFC6937 to PS

From: Matt Mathis <[email-masked]>
Date: Sat, 17 Oct 2020 18:56:20 -0700

Following a discussion with the tcpm chairs, the authors of RFC6937 plan to
introduce a .bis document to update PRR from Experimental to Proposed
Standard.   PRR is supported in one form or another in 3 major operating
systems and has come to be very widely deployed over the last several years.

There have been no changes to the base algorithms for PRR-CRB (Conservative
Rate Bound) and PRR-SSRB (Slow Start Rate Bound).  However PRR can be
substantially improved by using a heuristic to dynamically switch
between algorithms, depending on the presence of additional losses.    We
plan to present a candidate heuristic, however there has not been any deep
studies of alternatives.  This approach was first described in section 5.2.
of Flach et al "An Internet-Wide Analysis of Traffic Policing"
<https://dl.acm.org/doi/abs/10.1145/2934872.2934873> and has already been
upstream for several years.

I could use some editorial advice:  RFC 6937 is too long and much too
"tutorial" in tone.   Does it work for RFC 6937.bis to state the
algorithms in normative language, but to have non-normative references
to RFC 6937 for context and background?  Can somebody point me to a pair of
existing RFC's that use this approach?   How much explanation should remain
in RFC 6937.bis?

We are aiming to have something ready for the next tcpm meeting.

Thanks,
--MM--
The best way to predict the future is to create it.  - Alan Kay

We must not tolerate intolerance;
       however our response must be carefully measured:
            too strong would be hypocritical and risks spiraling out of
control;
            too weak risks being mistaken for tacit approval.

---

From: Michael Welzl <[email-masked]>
Date: Sun, 18 Oct 2020 23:07:05 +0200

Hi,

Are there any known bad experiences with PRR at all?

I like RFC 6937, as I appreciate that it's trying to do the right thing, in the right way (and, as a side note, at least I did enjoy its “tutorial” tone writing style) … but I do think that there may be situations where the RFC 6675 style reduction has an advantage, as it allows the queue to drain for half an RTT before sending again.

We once saw consistent double drops upon entering FR/FR from CA in local tests with a large queue (above a BDP), and ended up blaming PRR for it, as it would detect loss (little loss) and quite immediately set the rate to half of the previous rate, which (in case of an above-BDP bottleneck queue) was still faster than the capacity limit. Then, the queue never really got a chance to drain (it seemed), it filled up again, and there was another loss. Now, one could argue that such long queues are not a case to optimize for anyway, but e.g. Cubic’s backoff could show the same behavior with a shorter queue.

We didn’t investigate this deeper, and now I can’t be say for sure if this really was PRR’s fault - but shortly after this experience, I stumbled over this:
https://www.ee.technion.ac.il/~isaac/p/sigcomm16_vcc_extended.pdf
(long version of the VCC Sigcomm’16 paper)

… which also finds double drops occuring as a result of PRR (see appendix B).  I have to admit that I don’t fully get the discussion around ECN in this appendix; altogether, I’m not really convinced there are  hard facts about this being a “problem” at all, but I thought it’d be worth bringing to the group’s attention. Maybe someone has investigated this deeper and found out if this is a real issue or not.

Cheers,
Michael

> On Oct 18, 2020, at 3:56 AM, Matt Mathis <mattmathis=[email-masked]> wrote:
> 
> Following a discussion with the tcpm chairs, the authors of RFC6937 plan to introduce a .bis document to update PRR from Experimental to Proposed Standard.   PRR is supported in one form or another in 3 major operating systems and has come to be very widely deployed over the last several years.
> 
> There have been no changes to the base algorithms for PRR-CRB (Conservative Rate Bound) and PRR-SSRB (Slow Start Rate Bound).  However PRR can be substantially improved by using a heuristic to dynamically switch between algorithms, depending on the presence of additional losses.    We plan to present a candidate heuristic, however there has not been any deep studies of alternatives.  This approach was first described in section 5.2. of Flach et al "An Internet-Wide Analysis of Traffic Policing" <https://dl.acm.org/doi/abs/10.1145/2934872.2934873> and has already been upstream for several years.
> 
> I could use some editorial advice:  RFC 6937 is too long and much too "tutorial" in tone.   Does it work for RFC 6937.bis to state the algorithms in normative language, but to have non-normative references to RFC 6937 for context and background?  Can somebody point me to a pair of existing RFC's that use this approach?   How much explanation should remain in RFC 6937.bis?
> 
>             too strong would be hypocritical and risks spiraling out of control;
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Matt Mathis <[email-masked]>
Date: Mon, 19 Oct 2020 10:20:13 -0700

The heuristic was designed to address the "double drops" that you noted.
Both RFC 6675 and PRR-SSRB can be too aggressive in situations where there
are burst losses that cause the flight size to fall below ssthresh.
Sometimes these are ok, but they often cause lost retransmissions.  The new
heuristic is to prevent these situation from persisting.

These situations are hard to reason about because they can not be caused by
events that are modeled by simple queues.  The Flatch paper is about token
bucket policers which cause huge losses when they run out of tokens -- all
without significant queues.  Other potential events include bursty cross
traffic from long RTT or non-responsive flows.

With packet conservation, a single flow can not cause self inflicted losses
that last more than one RTT, and thus can't cause lost retransmissions.
If there are lost retransmissions something happened that is outside the
scope a simple network model.

While I agree that 6675's half RTT of silence reduces queue pressure, the
responsibility for that really belongs to congestion control, which should
not be controlling against queue full.  The goal of PRR is to minimize the
opportunities to lose the self clock by accurately controlling flightsize
to the target set by the congestion control.

The heuristic also helps in the situation where there was a large step
change in the available bandwidth, and the CC can not possibly estimate the
the correct flightsize quickly enough.

Thanks,
--MM--

On Sun, Oct 18, 2020 at 2:07 PM Michael Welzl <[email-masked]> wrote:

> I like RFC 6937, as I appreciate that it's trying to do the right thing,
> in the right way (and, as a side note, at least I did enjoy its “tutorial”
> tone writing style) … but I do think that there may be situations where the
> RFC 6675 style reduction has an advantage, as it allows the queue to drain
> for half an RTT before sending again.
>
> We once saw consistent double drops upon entering FR/FR from CA in local
> tests with a large queue (above a BDP), and ended up blaming PRR for it, as
> it would detect loss (little loss) and quite immediately set the rate to
> half of the previous rate, which (in case of an above-BDP bottleneck queue)
> was still faster than the capacity limit. Then, the queue never really got
> a chance to drain (it seemed), it filled up again, and there was another
> loss. Now, one could argue that such long queues are not a case to optimize
> for anyway, but e.g. Cubic’s backoff could show the same behavior with a
> shorter queue.
>
> We didn’t investigate this deeper, and now I can’t be say for sure if this
> really was PRR’s fault - but shortly after this experience, I stumbled over
> this:
> … which also finds double drops occuring as a result of PRR (see appendix
> B).  I have to admit that I don’t fully get the discussion around ECN in
> this appendix; altogether, I’m not really convinced there are  hard facts
> about this being a “problem” at all, but I thought it’d be worth bringing
> to the group’s attention. Maybe someone has investigated this deeper and
> found out if this is a real issue or not.
>
> Cheers,
> Michael
>
>
> On Oct 18, 2020, at 3:56 AM, Matt Mathis <
> mattmathis=[email-masked]> wrote:
>
> Following a discussion with the tcpm chairs, the authors of RFC6937 plan
> to introduce a .bis document to update PRR from Experimental to Proposed
> There have been no changes to the base algorithms for PRR-CRB
> (Conservative Rate Bound) and PRR-SSRB (Slow Start Rate Bound).  However
> PRR can be substantially improved by using a heuristic to dynamically
> switch between algorithms, depending on the presence of additional losses.
>   We plan to present a candidate heuristic, however there has not been any
> deep studies of alternatives.  This approach was first described in section
> 5.2. of Flach et al "An Internet-Wide Analysis of Traffic Policing"

---

From: Michael Welzl <[email-masked]>
Date: Mon, 19 Oct 2020 23:47:29 +0200

Hi,

In line:

> On Oct 19, 2020, at 7:20 PM, Matt Mathis <[email-masked]> wrote:
> 
> The heuristic was designed to address the "double drops" that you noted.    Both RFC 6675 and PRR-SSRB can be too aggressive in situations where there are burst losses that cause the flight size to fall below ssthresh.  Sometimes these are ok, but they often cause lost retransmissions.  The new heuristic is to prevent these situation from persisting.

I get that, but what I’m concerned about is a case where pipe is *not* below ssthresh, so the heuristics don’t even apply. It’s enough to consider the “diagram" on page 7, where it’s clear that RFC 6675 takes a break from segment 4 to 11 but PRR (or rate-halving) doesn’t. This is fine when the new rate is smaller than the bottleneck’s capacity, but if it’s not, the queue should just overflow again, I believe.

(again, these are all more suspicions than anything else - I only have indications, from our own experiments and the paper I pointed to, nothing really clear that shows that this really happens; come to think of it, it actually wouldn’t be hard for me to run a check in our testbed… perhaps that would be better than making a fuss here about something that may turn out to be nothing. Then again, maybe it’s a good conversation to have anyway, just to see what the thinking around this type of concern is.)

> These situations are hard to reason about because they can not be caused by events that are modeled by simple queues.  The Flatch paper is about token bucket policers which cause huge losses when they run out of tokens -- all without significant queues.  Other potential events include bursty cross traffic from long RTT or non-responsive flows.

Ok, but that’s not the case I mean, mine is simpler (above). Even just a single packet loss would suffice for the situation I’m talking about.

> With packet conservation, a single flow can not cause self inflicted losses that last more than one RTT, and thus can't cause lost retransmissions.

Hmmmmmm….. I doubt this; I think the backoff factor and queue also play a role. The point is that the new cwnd may be too much, just like the old was too much.

>     If there are lost retransmissions something happened that is outside the scope a simple network model.
> 
> While I agree that 6675's half RTT of silence reduces queue pressure, the responsibility for that really belongs to congestion control, which should not be controlling against queue full.

I agree with the thought, but in IETF terms I think that a recovery mechanism in a PS RFC has to be compatible with RFC 5681 too.

>   The goal of PRR is to minimize the opportunities to lose the self clock by accurately controlling flightsize to the target set by the congestion control.
> 
> The heuristic also helps in the situation where there was a large step change in the available bandwidth, and the CC can not possibly estimate the the correct flightsize quickly enough. 

I understand; generally, I don’t doubt that there are many good aspects to PRR, and that it will work better than RFC 6675 in many cases. The half-RTT-of-nothing pattern is just odd.
So maybe what I’m worrying about is a corner case. But, as we talk about proceeding to PS, I think it deserves a thought.

Cheers,
Michael

---

From: Matt Mathis <[email-masked]>
Date: Mon, 19 Oct 2020 22:25:19 -0700

I don't understand the situation you are thinking about.  If the bottleneck
BW changes and it causes loss any loss, you would expect to see a whole RTT
of periodic losses between the first detected loss, and the ACK from the
first retransmission.  If inflight (aka pipe) is larger than ssthresh, PRR
will always send less data than has left the network.  This is
guaranteed by the
conservative self clock and the "proportional" part of the algorithm.  Yes
it drains the queue slowly, and yes cross traffic can cause additional
losses, but that is because the cross traffic is being too aggressive (e.g.
the cross traffic has to still be increasing its instantaneous rate for
some reason).

Thanks,
--MM--

On Mon, Oct 19, 2020 at 2:47 PM Michael Welzl <[email-masked]> wrote:

> > The heuristic was designed to address the "double drops" that you
> noted.    Both RFC 6675 and PRR-SSRB can be too aggressive in situations
> where there are burst losses that cause the flight size to fall below
> ssthresh.  Sometimes these are ok, but they often cause lost
> retransmissions.  The new heuristic is to prevent these situation from
> persisting.
>
> I get that, but what I’m concerned about is a case where pipe is *not*
> below ssthresh, so the heuristics don’t even apply. It’s enough to consider
> the “diagram" on page 7, where it’s clear that RFC 6675 takes a break from
> segment 4 to 11 but PRR (or rate-halving) doesn’t. This is fine when the
> new rate is smaller than the bottleneck’s capacity, but if it’s not, the
> queue should just overflow again, I believe.
>
> (again, these are all more suspicions than anything else - I only have
> indications, from our own experiments and the paper I pointed to, nothing
> really clear that shows that this really happens; come to think of it, it
> actually wouldn’t be hard for me to run a check in our testbed… perhaps
> that would be better than making a fuss here about something that may turn
> out to be nothing. Then again, maybe it’s a good conversation to have
> anyway, just to see what the thinking around this type of concern is.)
>
>
> > These situations are hard to reason about because they can not be caused
> by events that are modeled by simple queues.  The Flatch paper is about
> token bucket policers which cause huge losses when they run out of tokens
> -- all without significant queues.  Other potential events include bursty
> cross traffic from long RTT or non-responsive flows.
>
> Ok, but that’s not the case I mean, mine is simpler (above). Even just a
> single packet loss would suffice for the situation I’m talking about.
>
>
> > With packet conservation, a single flow can not cause self inflicted
> losses that last more than one RTT, and thus can't cause lost
> retransmissions.
>
> Hmmmmmm….. I doubt this; I think the backoff factor and queue also play a
> role. The point is that the new cwnd may be too much, just like the old was
> too much.
>
>
> > While I agree that 6675's half RTT of silence reduces queue pressure,
> the responsibility for that really belongs to congestion control, which
> should not be controlling against queue full.
>
> I agree with the thought, but in IETF terms I think that a recovery
> mechanism in a PS RFC has to be compatible with RFC 5681 too.
>
>
> >   The goal of PRR is to minimize the opportunities to lose the self
> clock by accurately controlling flightsize to the target set by the
> congestion control.
> >
> I understand; generally, I don’t doubt that there are many good aspects to
> PRR, and that it will work better than RFC 6675 in many cases. The
> half-RTT-of-nothing pattern is just odd.
> So maybe what I’m worrying about is a corner case. But, as we talk about
> proceeding to PS, I think it deserves a thought.
>
> Cheers,
> Michael
>
>

---

From: Michael Welzl <[email-masked]>
Date: Tue, 20 Oct 2020 08:11:32 +0200

Hi again,

You don't understand it because it doesn't make sense; I get it now, and I was just wrong, I'm sorry.
I've recently been thinking too much about a paced, non-ack-clocked behavior, where things might indeed play out as I described, even with an overshoot of only one segment.

With ACK clocking, as you said, that can't happen. In fact, I can see it become a problem only in one case: when the overshoot is so high that setting back the cwnd won't save you, even with ack clocking. But I think this translates exactly into "pipe < ssthresh", and this is the case that the heuristics cover - which, as you said, were designed to handle these double drops (*). So it all makes sense to me now, sorry for this excursion into the land on nonsense. Case closed, go home everyone, nothing to see here!  :-)

Cheers,
Michael
--
(*) In practice, I therefore think that these heuristics can play an important role after the very first slow start.

> On 20 Oct 2020, at 07:25, Matt Mathis <[email-masked]> wrote:
> 
> I don't understand the situation you are thinking about.  If the bottleneck BW changes and it causes loss any loss, you would expect to see a whole RTT of periodic losses between the first detected loss, and the ACK from the first retransmission.  If inflight (aka pipe) is larger than ssthresh, PRR will always send less data than has left the network.  This is guaranteed by the
> conservative self clock and the "proportional" part of the algorithm.  Yes it drains the queue slowly, and yes cross traffic can cause additional losses, but that is because the cross traffic is being too aggressive (e.g. the cross traffic has to still be increasing its instantaneous rate for some reason).
> 
> Thanks,
> --MM--

---

From: Mirja Kuehlewind <[email-masked]>
Date: Thu, 22 Oct 2020 11:58:47 +0000

Hi Michael, hi Matt,

Frist I like to note that I support moving RFC6937 to PS and I'm happy to see that there is an additional heuristic to address "double drops". 

Years ago when we worked on RFC6937 in tcpm, I believe I observed a similar problem after slow start, where slow start will not only fill the queue but overshoot to double the cwnd. So when you "only" halve the cwnd as PRR does correctly, you end up will a full queue after recovery and you will see another congestion event soon after. Rate halving however would end up with only 1/4 of the cwnd after recovery and respectively empty the queue. However, in the end there was not much of a difference (regarding throughput and number of losses), only PRR would actually keep the queue slightly longer full... is this case also addressed by this heuristic?

Mirja

On 20.10.20, 08:11, "tcpm on behalf of Michael Welzl" <[email-masked] on behalf of [email-masked]> wrote:

    Hi again,

    Cheers,
    Michael

---

From: Michael Welzl <[email-masked]>
Date: Thu, 22 Oct 2020 14:49:09 +0200

Hi,

> On 22 Oct 2020, at 13:58, Mirja Kuehlewind <[email-masked]> wrote:
> 
> Hi Michael, hi Matt,
> 
> Years ago when we worked on RFC6937 in tcpm, I believe I observed a similar problem after slow start, where slow start will not only fill the queue but overshoot to double the cwnd. So when you "only" halve the cwnd as PRR does correctly, you end up will a full queue after recovery and you will see another congestion event soon after.

Yes - that's a general problem that we're now experiencing, as we're playing around with pacing ... halving cwnd sometimes works ok when senders are *not* paced, because the bursts may cause a drop before cwnd has even overshot to double - but with a fully paced sending behavior, halving cwnd after slow start is really not enough of a back-off, I think.

> Rate halving however would end up with only 1/4 of the cwnd after recovery and respectively empty the queue. However, in the end there was not much of a difference (regarding throughput and number of losses), only PRR would actually keep the queue slightly longer full... is this case also addressed by this heuristic?

I'm curious about this too.

I also wonder - in the case that I was concerned about at first, where there is little loss (e.g., only one packet): yes, ACK clocking will then prevent a double drop from happening, but PRR is also more likely than RFC 6675 to keep a queue full at this point, by avoiding the half-RTT break that may have allowed the queue to drain. So I still have my question: has anybody seen problems with this? Is it only always an advantage?   (I'm suspecting that it is, unless the queue is unreasonably large or there is a large amount of statmux ... but I wonder about data).

Cheers,
Michael