-
65b5f111
by Miroslav Lichvar at 2024-11-18T15:51:42+01:00
quantiles: fix assertion for requested k
-
77962bb5
by Miroslav Lichvar at 2024-11-21T09:05:58+01:00
quantiles: add functions to get max k and min step
-
c92358e0
by Miroslav Lichvar at 2024-11-21T15:59:47+01:00
ntp+hwclock: add margin to estimated delay quantiles
Extend the interval of accepted delays by half of the quantile minimum
step in both directions to make room for floating-point errors in the
quantile calculation and an error that will be intentionally added in
the next commit.
-
2da4e3ce
by Miroslav Lichvar at 2024-11-21T15:59:56+01:00
quantiles: force step update with stable input values
The algorithm was designed for estimating quantiles in streams of
integer values. When the estimate is equal to the input value, the
step state variable does not change. This causes problems for the
floating-point adaptation used for measurents of delay in chrony.
One problem is numerical instability due to the strict comparison of
the input value and the current estimate.
Another problem is with signals that are so stable that the nanosecond
resolution of the system functions becomes the limitation. There is a
large difference in the value of the step state variable, which
determines how quickly the estimate will adapt to a new distribution,
between signals that are constant in the nanosecond resolution and
signals that can move in two nanoseconds.
Change the estimate update to never consider the input value equal to
the current estimate and don't set the estimate exactly to the input
value. Keep it off by a quarter of the minimum step to force jumping
around the input value if it's constant and decreasing the step variable
to negative values. Also fix the initial adjustment to step at least by
the minimum step (the original algorithm is described with ceil(), not
fabs()).
-
d22c8fbc
by Miroslav Lichvar at 2024-11-21T16:00:23+01:00
quantiles: add parameter to limit negative step
Add a new parameter to limit the negative value of the step state
variable. It's set as a maximum delay in number of updates before the
actual step applied to the quantile estimate starts growing from the
minimum step when the input value is consistently larger or smaller than
the estimate.
This prevents the algorithm from effectively becoming the slower 1U
variant if the quantile estimate is stable most of the time.
Set it to 100 updates for the NTP delay and 1000 updates for the hwclock
delay. An option could be added later to make it configurable.