Subject: [quicwg/base-drafts] Remove ack_delay_exponent TP (#2670)

From: Nick Banks <[email-masked]>
Date: Tue, 07 May 2019 07:20:37 -0700

I asked the question on Slack and got quite a bit of feedback so I figured I'd open an issue.

Right now, it seems all but one implementation (quicly) is using the default ack_delay_exponent value of 8. Quicly is using an even higher value of 10 because they don't care about more than millisecond timer resolution.

This leads me to believe that having this be a configurable value (in the QUIC TP) is an over design, and we should simplify this. Pick a value (8 or 10, I personally don't care which) and just leave it at that.

The only argument I've heard for keeping it configurable is that intra-DC environments might want to have a smaller exponent to have more fine grain ACK delays. I'm not sure that's a great reason, personally. At that small of time granularity, most OS timers aren't going to be very accurate. So, even if you can calculate an extremely accurrate RTT, it's not going to help your loss recovery timers any.

-- 
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/2670

---

From: ianswett <[email-masked]>
Date: Tue, 07 May 2019 15:18:37 -0700

I don't think this adds a lot of complexity, so I'm happy with the status quo.

-- 
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/2670#issuecomment-490275354

---

From: Marten Seemann <[email-masked]>
Date: Wed, 08 May 2019 03:32:55 +0000 (UTC)

> Right now, it seems all but one implementation (quicly) is using the default ack_delay_exponent value of 8. Quicly is using an even higher value of 10 because they don't care about more than millis…

The default value is not 8, it's 3. So what quicly makes a pretty big difference here: They're using a multiplier of 1024 instead of 8.

As I've already remarked on Slack, if we want to allow implementations to scale this value, it seems to make more sense to specify a multiplier instead of an exponent.

-- 
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/2670#issuecomment-490333921

---

From: Nick Banks <[email-masked]>
Date: Wed, 08 May 2019 07:25:49 -0700

@marten-seemann You're right. I was mixing up 3 and 2^3 (8). So, right now the default suggests an 8 microsecond ack_delay accuracy and quicly is using a ~1 millisecond ack_delay accuracy. The more I think about it, the higher value might well be the better one.

The goal of this issue was to see if we could actually all just agree on a single scaling (or multiplier) value.  To me, configurability is only useful if we have good reason for different values.

As I understand it, changing this value just affects the accuracy of the ack_delay field in the ACK frame. This in turns, effects the accuracy of the network RTT calculation for the largest acknowledged packet in the ACK frame. My question is what truely is the difference between being able to measure the RTT with sub-millisecond accuracy (even in intra-DC) if the timers aren't that accurate? The primary point of measuring RTT is to have it factor into loss recovery timers.

Additionally, since the endpoint setting the timer is the one with the actual restriction on timer accuracy, it seems to be, if this value was to be configurable, it should be the receiver of the ACK frame to dictate how accurate the ack_delay needs to be; not the sender.

It just feels like this is really over complicating things. If folks really feel like this field needs to be configurable, I'd like to understand why, so that I might make the same optimizations/choices in winquic. 

I personally think the argument of "it's not that much more complex to keep it" isn't a great one. IMO, any additional complexity for no explicit reason is bad complexity. These things add up pretty fast.

-- 
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/2670#issuecomment-490507144

---

From: ianswett <[email-masked]>
Date: Wed, 08 May 2019 07:33:49 -0700

Clock accuracies vary a lot by environment(ie: ours are better than 1ms, but not as good as being in the Linux kernel) as do RTTs, so I would expect a datacenter to set this to 0 or 1 and user facing traffic to pick the default of 3 or a higher value.

-- 
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/2670#issuecomment-490510604

---

From: Nick Banks <[email-masked]>
Date: Wed, 08 May 2019 07:40:23 -0700

Sure, I understand that. Being able to query an accurate time is one thing; scheduling a timer that accurate is another. On Windows you can query microsecond time, but only configure to a 1 ms timer accuracy at best (depending on configuration and scheduler). But is that reason to have 1 microsecond ack_delay accuracy?

Also, like I pointed out above, the accuracy is dependent on your peer. They don't necessarily know your timer or clock accuracy.

-- 
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/2670#issuecomment-490513439

---

From: ianswett <[email-masked]>
Date: Wed, 08 May 2019 08:18:18 -0700

The idea is if you schedule a timer for 1ms, but it goes off at 1357us, you can indicate the actual delay instead of the intended delay.

So the peer shouldn't need to know your timer accuracy, but ideally your clock accuracy is fairly good.

-- 
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/2670#issuecomment-490529066

---

From: Nick Banks <[email-masked]>
Date: Wed, 08 May 2019 08:24:23 -0700

Sorry if I was unclear. I wasn't referring to computing how long you actually delayed. I was referring to calculating the time you set for your PTO timer. That's effectively where the adjusted rtt measurement comes into play, right? Does it really matter if the rtt is 53.112 ms or just 53.1 ms or 53 ms, when you set the PTO timer, if your timer doesn't have that accuracy?

-- 
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/2670#issuecomment-490531544

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 08 May 2019 17:04:30 -0700

I'm fine with status quo, but if we are to make a change, I like @marten-seemann's proposal of changing ack_delay_exponent to a multiplier.

As @nibanks has pointed out, quicly uses ack_delay_exponent of 10 because it uses a millisecond timer. However, exponent of 10 is slightly incorrect, because 2<sup>10</sup> is 1,024.

Generally speaking, I do not think that people would have a timer granularity of 2<sup>N</sup> microseconds, where N is an integer. I expect people granularity of 10<sup>N</sup> microsecond timers instead.

To put it another way, the base of the exponent not being 10 leads to either inaccuracy of ACK.ack_delay, or the size of the ack_delay field becoming larger than what it could be.

That said, @marten-seemann's suggestion of using a multiplier allows accurate representation of ack-delay for any timer that have X microsecond granularity, at the cost of probably spending 1 more byte in TP. I think it has the best flexibility without sacrificing anything in practice.

-- 
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/2670#issuecomment-490694770

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 08 May 2019 18:50:23 -0700

@kazuho makes a good point about the inaccuracy of 2^N when it comes to timer granularity.  I don't think a multiplier is any more expensive, and it's certainly more accurate.

-- 
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/2670#issuecomment-490712288

---

From: Nick Banks <[email-masked]>
Date: Wed, 08 May 2019 19:22:51 -0700

I'd be happy with just saying ack_delay is units of milliseconds and do away with ack_delay_exponent. I really don't see a reason to have more accurate time for this field.

-- 
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/2670#issuecomment-490717920

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 08 May 2019 20:05:38 -0700

> I'd be happy with just saying ack_delay is units of milliseconds and do away with ack_delay_exponent.

While millisecond granularity would be sufficient (and also efficient in terms of the size of the ACK frame) for connections between the web browsers and the servers, more accuracy is desirable for intra-datacenter connections (as @ianswett has pointed out).

Therefore, my preference would be to retain a TP that can be used to scale the granularity.

-- 
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/2670#issuecomment-490725586

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 08 May 2019 20:25:27 -0700

This really isn't much complexity, so I would like to keep the TP around, albeit preferably as a multiplier.

-- 
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/2670#issuecomment-490728935

---

From: Martin Thomson <[email-masked]>
Date: Wed, 08 May 2019 21:59:10 -0700

Looks like multiplication is beating exponentiation.  (Also consistency over inconsistency.)

-- 
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/2670#issuecomment-490743825

---

From: MikkelFJ <[email-masked]>
Date: Wed, 08 May 2019 22:45:36 -0700

In praxis you can’t trust any timer to be at any resolution, so messuring the diff in nanoseconds and downshifting by exponent would be simpler, faster, and more precise. Otherwise you hsve to deal with division or choose a power of 2 anyway.

________________________________
Fra: Martin Thomson <[email-masked]>
Sendt: torsdag, maj 9, 2019 6:59 AM
Til: quicwg/base-drafts
Cc: Subscribed
Emne: Re: [quicwg/base-drafts] Remove ack_delay_exponent TP (#2670)

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub<https://github.com/quicwg/base-drafts/issues/2670#issuecomment-490743825>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AABPGN32VIBRFKZXRGFMDXTPUOVRRANCNFSM4HLJKNXA>.

-- 
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/2670#issuecomment-490752113

---

From: ianswett <[email-masked]>
Date: Thu, 09 May 2019 05:11:52 -0700

I don't see a reason to change this to a multiplier, except for personal taste.  Shifts are objectively faster and I haven't seen anyone indicate they need or really want a multiplier that can't be expressed today.

-- 
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/2670#issuecomment-490877457

---

From: Nick Banks <[email-masked]>
Date: Thu, 09 May 2019 07:22:28 -0700

First, if the parameter ends up staying, I agree with @ianswett and I would just leave things as they are, with no changes (though maybe we update the default to 10?).

But I still haven't seen a specific answer to two things:

1) The endpoint setting the timers for loss detection is the one who knows the accuracy of the timer; not the one sending the ACK frame. So, shouldn't the endpoint that sets the timer tell it's peer what ack_delay_exponent to use, not the other way around?

2) Even in intra-DC environments, where RTT is nearly 0 ms, that doesn't change how accurate timers can be set. In the default case for Windows, for instance, 15.6 ms is still average accuracy a timer can get. At best, that can be reduced to 1 ms. But at that small of an interval, any kind of scheduling interruption will add extra delay too. So practically, I don't ever see sub-millisecond timers being viable. Therefore, why do we ever need sub-millisecond ack_delay values communicated over the wire? Any fractional delay would just be included in the rtt variance (and IMO, rightly so).

-- 
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/2670#issuecomment-490925674

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 07:26:08 -0700

On timers: you don't know what hardware and software will be deployed in the future or in special projects. Wether that precision is really important is a different question.

-- 
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/2670#issuecomment-490927163

---

From: Nick Banks <[email-masked]>
Date: Thu, 09 May 2019 14:30:59 +0000 (UTC)

@mikkelfj I can agree to that. But as far as "what might happen in the future", in the QUIC WG, it seems that the general guideline has been: if you don't have a scenario for it now (i.e. not in the charter) then defer it as either a possible extension or a future version.

-- 
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/2670#issuecomment-490929147

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 07:41:30 -0700

So, I don't know what you can typically expect, but I have a timer implementation that uses nanosleep because why not? Recent Linux kernels can wait on microsecond resolution on x86 arch even if its general Hz/jiffie setting is higher.
http://man7.org/linux/man-pages/man7/time.7.html
http://man7.org/linux/man-pages/man2/nanosleep.2.html
That doesn't change my view that exponents are more manageable though.

-- 
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/2670#issuecomment-490933336

---

From: ianswett <[email-masked]>
Date: Thu, 09 May 2019 08:19:09 -0700

1) I think it makes slightly more sense for the receiver to specify it, since the receiver is the one setting a delayed ack alarm, but I can imagine it working ok either way.  It pairs with max_ack_delay in some ways, and that's receiver specified, so I think keeping it on the receiver side is preferable.

2) If you have a 100us RTT and >1ms timer granularity, then I think this becomes more important, not less.  In that case, you want to pace over the true RTT, not the SRTT without adjusting for max_ack_delay, because that may be 10x or more too slow.   And to second @mikkelfj point, sub-millisecond timers are now fairly common.

-- 
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/2670#issuecomment-490948169

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 09 May 2019 09:45:05 -0700

@ianswett 
> I don't see a reason to change this to a multiplier, except for personal taste. Shifts are objectively faster and I haven't seen anyone indicate they need or really want a multiplier that can't be…

Thinking a bit more about the problem, to me it seems that using examples might help in moving the discussion forward.

Consider the case where an endpoint uses a millisecond timer, sets max_ack_delay to 25ms, and the RTT is 5 milliseconds. The endpoint sends an ACK when the ack-delay timer fires.

If the endpoint uses ack_delay_exponent of 10 (i.e., 1024 microseconds as an approximation of 1 millisecond), the sender would set ACK.ack_delay to 25, and the receiver would interpret the value as 25.6 milliseconds (i.e. 1024*25=25,600). Then, the calculated RTT becomes 4.4ms, which is 12% smaller than the actual value.

Is this error acceptable? I _think_ it is, because a millisecond timer would have +- 1ms inaccuracy. Although it is a bit concerning that the RTT would always be underestimated in the above case.

But the question is: what is the rational for using shifts instead of multipliers, when there are these types of errors? While it is true that bit shift is faster than multiplication, the different does not matter for an encrypted transport.

-- 
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/2670#issuecomment-490979849

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 09:49:56 -0700

Are you not forgetting that numbers are stored in base 2, so if you divide by, say 100 or 25000, you do not get an exact representation at the lower bit? Receiver side multiply by said factor will now introduce an inaccuracy. On the contrary, if you keep your time management in base 2 sender side (if you can be bothered), there is no additional precision loss beyond the chosen resolution.

-- 
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/2670#issuecomment-490981462

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 09 May 2019 09:54:10 -0700

@mikkelfj Could you please elaborate where division happens? ack_delay_exponent is chosen by the sender of the ACK frame. Therefore, no division is happening in the example above.

-- 
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/2670#issuecomment-490982913

---

From: ianswett <[email-masked]>
Date: Thu, 09 May 2019 10:00:36 -0700

One correction on your example @kazuho.  The rtt sample that would result would not go lower than min_rtt, so it would only be 4.4ms if the min_rtt was <=4.4ms.

-- 
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/2670#issuecomment-490985121

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 10:01:14 -0700

It happens because timers don't work as you describe.
When the timer fires it is either a spurious wake-up or a proper wake-up, but likely rounded up to some internal quant that is a not a clean multiple of anything. Additionally the wake-up is is possibly coalesced so different things might happen before your event gets activated.
Hence, the sane thing to do is to is:
t1 = now.
delay = 250ms
sleel(250ms)
t2 = now
ack.delay = (t2 - t1) / unit_multiplier.
If you do not do that, any rounding errors is dwarfed by assumptions on time precision.

-- 
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/2670#issuecomment-490985340

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 09 May 2019 10:11:13 -0700

@ianswett 
> The rtt sample that would result would not go lower than min_rtt, so it would only be 4.4ms if the min_rtt was <=4.4ms.

Good point. Thank you for pointing that out. Though I'd assume that having +-12% jitter between RTT samples would be common.

@mikkelfj Thank you for the clarification. I now see the confusion. I think I should have said "1ms granularity clock" rather than "timer". Does that make things clear?

-- 
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/2670#issuecomment-490988555

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 10:18:27 -0700

not really, because except for rare RTOS systems used in ABS breaking systems and such, there is no such thing as a 1ms granularity. It may be that you best resolution is 1ms, but you might wake up 2500ms later after disk swap is done, or at half the expected sleep time because of some Unix signal and you don't care to rewait after that, or just general noise of kernel processes, interrupts, TLB misses, etc. Of course, the smaller the RTT the more critical this gets. For 25ms the chance of staying within a few percentage reasonable.

I still think the float16 approach is better. It takes all the guessing out be introducing an exponent per timestamp, and it can be decoded in a few nanoseconds.

-- 
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/2670#issuecomment-490990921

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 09 May 2019 10:27:02 -0700

> not really, because except for rare RTOS systems used in ABS breaking systems and such, there is no such thing as a 1ms granularity. It may be that your best resolution is 1ms, but you might wake up 2500ms later after disk swap is done, or at half the expected sleep time because of some Unix signal and you don't care to rewait after that, or just general noise of kernel processes, interrupts, TLB misses, etc.

While I agree with that, I think it is unrelated to the discussion here. Because that issue exists in any code, including https://github.com/quicwg/base-drafts/issues/2670#issuecomment-490985340. I am saying that the value returned by `now` is in milliseconds.

-- 
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/2670#issuecomment-490993809

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 10:33:58 -0700

Well, yes, you will never get it better than now resolution. But that resolution is much higher than ms if you use timespec_get calls. https://en.cppreference.com/w/c/chrono/timespec_get
It is more likely you get thrown by page cache misses. But sure, systems differ. All I'm saying is that if you are able, and can be bothered, exponents do not loose additional precision after computing a time delta. That said, I'd only call now occasionally because it can be expensive, so there you immediately loose precision. But that might be 300ns, not 1ms.

-- 
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/2670#issuecomment-490996306

---

From: MikkelFJ <[email-masked]>
Date: Thu, 09 May 2019 10:48:58 -0700

Just a reference to the float16 format I mentioned: https://gist.github.com/mikkelfj/64deb01b86d68f3d7aacff4b113c22d8

-- 
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/2670#issuecomment-491001385

---

From: Nick Banks <[email-masked]>
Date: Thu, 09 May 2019 11:02:45 -0700

I personally, really want to stay away from any custom encoding formats.

-- 
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/2670#issuecomment-491006096

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 09 May 2019 12:29:53 -0700

If the timer is run in milliseconds and the expression of the value is in microseconds (which is what we will commonly have), it's natural to have a 10^x exponent rather than a 2^x exponent, since systems typically use SI units for time, which are always powers of 10 (same as bandwidth, which are also expressed as powers of 10). While I appreciate that multiplication can be slightly slower than shifting, I don't think this one cost per ack is going to figure anywhere.

Multiplication is a more natural fit here, and I don't expect it to be a significant change, in code or in performance.

-- 
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/2670#issuecomment-491035282

---

From: Christian Huitema <[email-masked]>
Date: Tue, 21 May 2019 09:49:37 -0700

My $0.02: I am happy with the spec as is. If I had to change, I would prefer the delay expressed as an integer number of microseconds, no shift or multiply required.

-- 
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/2670#issuecomment-494470743