Subject: [quicwg/base-drafts] QUIC PTO is too conservative, causing a measurable regression in tail latency (#3526)

From: ianswett <[email-masked]>
Date: Mon, 16 Mar 2020 06:44:16 -0700

Google and Chrome have been running experiments with the new IETF QUIC PTO algorithms post-handshake for a few months with Google QUIC, and it appears the first PTO is too conservative relative to Google QUIC.  On the positive side, the rate of spurious TLPs/PTOs is MUCH lower, so that's WAI.

This slows down detection of tail losses and causes a regression in 95%(and higher) latency metrics.  It's also visible as an increase in rebuffers for YouTube.  The changes aren't enormous, but they're large enough I can't launch this as is. 

I believe it's possible to make the first PTO slightly earlier, and stay aligned with the principles of TCP TLP and RTO.  Specifically, my suggestion is to set first PTO expiry from the left edge(see Section 5 of 6398), not the right edge, but there's an additional safety measure of waiting 1.5RTTs since the last ACK-eliciting packet was sent(1.5 is from TLP).  

It'll be a few more weeks before we have data from Chrome Stable, but I believe this may be enough to remove the regression.  Chromium code [here](https://cs.chromium.org/chromium/src/net/third_party/quiche/src/quic/core/quic_sent_packet_manager.cc?sq=package:chromium&g=0&l=1054).

One other note is we found that only sending one PTO packet seems sufficient as long as a packet number is skipped, so the delayed ack timer doesn't come into play.

@mjoras or others may also have production metrics relevant to this issue.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Mar 2020 17:28:35 -0700

[RFC 6398](https://tools.ietf.org/html/rfc6398#section-5) is entitled "IP Router Alert Considerations and Usage".  Do you refer to (5.1) in [RFC 6298](https://tools.ietf.org/html/rfc6298#section-5)?

> (5.1) Every time a packet containing data is sent (including a retransmission), if the timer is not running, start it running so that it will expire after RTO seconds (for the current value of RTO).

That reads to me like a left edge condition, based on "timer is not running".  Whereas [we say](https://quicwg.org/base-drafts/draft-ietf-quic-recovery.html#name-computing-pto):

> When an ack-eliciting packet is transmitted, the sender schedules a timer for the PTO period as follows:
> `PTO = smoothed_rtt + max(4*rttvar, kGranularity) + max_ack_delay`

I can see one 1.5sRTT factor in [the TLP draft](https://tools.ietf.org/html/draft-dukkipati-tcpm-tcp-loss-probe-01#section-2.1), but that is inflated quite a bit, so I'm not sure exactly what you think motivates this 1.5 value.

I do see the reason for your caution here.  You want to probe based on the first unacknowledged packet, but leave a buffer relative to the last unacknowledged packet (assuming all elicit acknowledgment, of course).  This is because all outstanding packets will all cause an acknowledgment if they arrive.  So this seems sensible, if a little more aggressive than we have been.

I don't know what the usual relationship between RTT and RTTvar is - I'm guessing that like everything it varies greatly.  I'm inferring that the buffer you want is as much based on allowing for variance as much as anything else.  The PTO is chosen to correspond roughly to 4-sigma, which is 99.994% and probably too conservative.  That conservatism is probably what dominates your numbers.  That also suggests that in the cases that drive your numbers, 4rttvar is greater than 0.5rtt.  I'm guess that it is a LOT greater.

Possible alternatives would be to cap rttvar to a proportion of the RTT estimate, maybe just for th purposes of calculating the PTO.  12.5% would get you almost exactly what you describe without changing the PTO calculation.  It seems to me that PTO on 2-sigma and capping rttvar to RTT/4 is probably better.  That's 2-sigma/95% confidence without the cap, and exactly your numbers if the cap has to be used.  Either way, that recognizes that one probe timeout is primarily dependent on the estimated RTT and is less susceptible to variation in that estimate.

I would like to request that you open a separate issue for the packet number skipping thing.  That seems separable.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-599818004

---

From: ianswett <[email-masked]>
Date: Mon, 16 Mar 2020 18:36:28 -0700

Yes, I meant RFC 6298, and I just updated the original post to reflect that.

In terms of rttvar, the production data I'm seeing indicates rttvar is fairly close to 1/2 SRTT on average, which isn't so surprising given SRTT is an EWMA and for it to be on the order of SRTT, it would require estimates fairly close to 0 to balance out the higher estimates.

Unfortunately, rttvar is RTT **variation**, not RTT **variance**(or RTT stdev).  As such, I don't know if we can reason about what fraction of spurious PTOs would be within SRTT + 4*RTTVar, even if we could assume a normal distribution(which is also likely wrong, but I think the least problematic assumption at the moment).

I'd really rather not cap rttvar in any way, since I can't come up with any intellectual justification for that.  The 1.5 constant from TLP does seem a bit arbitrary, but it is larger than SRTT.

We added code in Chrome to try RTTstdev(EWMA'd), but that's even more experimental than the suggestion in my first post on this issue.  I think there's a good chance 2*RTTStdev is the best option(vs 4*RTTVar), but I don't have data to support that yet.

I reopened PR #2952 for packet number skipping.  I can open an issue if needed, but it's a simple non-normative PR.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-599833225

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Mar 2020 20:49:17 -0700

Ah, I slipped into the same trap as usual.  Mean absolute difference from the mean is the EWMA approximation we are using.  Mean absolute difference is always less than standard deviation, with the factor being ~0.8 for a normal distribution.

Do you have information on the distribution of RTT values that might help determine whether 2 is the right multiplier?  If you have a normal distribution or something approximating that, then 3 would be closer (3.2 and change even).

I can justify capping PTO, but it requires that you be comfortable with being more aggressive.  But, at least to me, it seems like this is all about more aggressive sending.  Which naturally improves performance most of the time.  The network is likely to be able to absorb a minutely higher rate of probe packets as a result.

Based on recent history of the RTT estimate, the peer can produce an acknowledgment within sRTT most of the time.  Anything more than value is included only to allow more time for the peer to respond.  However, if this is the trailing edge of a flight of packets, then any packet in that flight can be acknowledged.  Allowing for some amount of variation in delays relative to the leading edge seems sensible, but delays on the trailing edge do not need any such justification.  The only reason not to use the leading edge alone is that you don't want to send probes when you are sending productive data within the congestion window.

On that basis, probing on the RTT estimate is fine.  That means dead air of one RTT, and maybe some wasted probes because of jitter in the network that extends the effective round trip time.  But you don't need to avoid unnecessary probing with very high confidence, you just need to avoid it most of the time.

The risk with probing sooner is that RTT might genuinely increase, so that probes - which might exceed the congestion window - don't help at all.  That should be rare; we have to treat past performance as a predictor for future gains, that's the basis of all of these systems.  As long as there is an exponential backoff on PTO, we're unlikely to cause significant congestion as you only ever send a handful of probes before flipping to persistent congestion.

A shorter and more aggressive timer here also results in hitting persistent congestion earlier.  So if there really is a routing flap that increases RTT significantly - a case where you really want to reset the congestion window anyway - then you will just end up in hitting that state sooner.

Another justification for a shorter PTO is that your estimation disadvantages shorter sequences of packets.  A single packet flight doesn't get probed any sooner under your algorithm, but that is more likely to see loss of the entire flight than a longer sequence of packets.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-599863594

---

From: MikkelFJ <[email-masked]>
Date: Tue, 17 Mar 2020 01:27:00 -0700

Out of curiosity, is there any ongoing work using perceptrons or similar for predicting retransmission behaviour like it is being used in CPU branch prediction? https://www.cs.utexas.edu/~lin/papers/hpca01.pdf https://en.wikipedia.org/wiki/Branch_predictor

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-599940913

---

From: ianswett <[email-masked]>
Date: Sat, 21 Mar 2020 14:18:07 -0700

@martinthomson Everything you said makes sense to me.  I'm hoping to come up with a proposal that does 2 things:
1) Is not a regression for our current gQUIC implementation (or TCP best practices)
2) Build on well publicized and accepted concepts from TCP(ie: TLP and RTO)
3) Reduce the rate of spurious retransmits vs gQUIC.

In terms of RTTVar vs an EWMA'd Stdev, I suspect the end result may be something like: SRTT+4*RTTVar OR SRTT + 2(or 3)*EWMA_Stdev, but I don't have enough data to know for sure yet.  The experiments have been started, so hopefully I should know more in 2 weeks.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-602105942

---

From: ianswett <[email-masked]>
Date: Sun, 29 Mar 2020 13:39:43 -0700

Instead of 1.5*SRTT we could consider SRTT + RTTVar.  I think that's slightly more principled, but should be similar to 1.5*SRTT for typical connections.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3526#issuecomment-605697733