UTC synchronization algorithms

Introduction

This page defines and explains the algorithms that Timekeeper uses to fulfil its central role in the UTC Architecture.

This information may be of interest if you are working on the time system or need a detailed understanding of the internals of UTC on Fuchsia. If you simply wish to develop components on Fuchsia that use UTC, consider reading the much shorter and simpler UTC Overview and UTC Behavior pages instead.

Time source components such as HTTPSDate time source also use a range of protocol-specific algorithms to compute their time samples; refer to the README.md in each time source component for further details.

Overview

The operation of Timekeeper is split into answering seven separate questions:

1. Should a time sample be accepted? Each time a sample is received from a time source Timekeeper decides whether it should be accepted (in which case it may lead to a change in the system’s understanding of UTC) or rejected (in which case it is discarded).
2. Which time source should be used? Timekeeper maintains a primary UTC estimate that may be influenced by time samples from the Primary, Fallback, or Gating time sources. When more than one of these sources is installed Timekeeper decides which source should be used at each point in time.
3. How should a time sample change the estimated UTC? Timekeeper maintains an estimate of the most probable UTC at all times, along with the uncertainty of this estimate. Timekeeper updates both this estimate and the uncertainty each time a sample is accepted from a time source.
4. What strategy should be used to converge the reported UTC? Each time the estimated UTC changes as the result of a time sample, Timekeeper chooses how to converge the UTC reported to clients with this new estimate. One option is to immediately step the reported time. Another option is to slew the reported time at some rate for some duration.
5. How should a sequence of time samples change the estimated frequency? A sequence of time samples may be used to estimate errors in a device’s oscillator. Correcting for these frequency errors increases the accuracy of the system.
6. How can clock error be bounded? The time reported by the UTC clock is unlikely to perfectly match the true UTC. Although the exact error is not known, Timekeeper may estimate and publish a bound on the error.
7. What clock updates should be made? Once a convergence strategy has been selected it must be implemented by making one or more updates to the UTC clock object. Estimated frequency and error bound changes should also update the UTC clock object.

In some other time synchronization systems (for example NTP) the same algorithm is used to answer more than one of these questions. This can make it difficult to clearly reason about the behavior of a particular feature, to avoid unintentional interactions between features, or to adjust components of the algorithm in response to new requirements. Timekeeper intentionally uses separate algorithms to answer each question. This leads to a system that is simpler to develop, analyze, and debug and provides greater flexibility to change or reconfigure individual algorithms when supporting a wide range of different products.

The interactions between these algorithms are summarized in Figure 1, where black elements are present in all configurations and grey elements are only present when an optional time source role is present.

Notation

The following sections sometimes use equations to define portions of the algorithms. These equations are formatted in code font for ease of identification and use the following notation:

• |x| The absolute value of x.
• sign(x) The sign of x. Returns -1 if x if negative and +1 if x if zero or positive.
• sqrt(x) The square root of x.
• sum(x) The sum of property x over all points within some dataset.
• clamp(x,y,z) The value x limited to be no less than y and no greater than z, i.e. clamp(x, y, z) = min(z, max(y, x))

Text in UPPER_CASE_SNAKE_CASE refers to configurable parameters that control the behavior of the algorithms. These parameters and their default values are discussed in configurable parameters.

Details

Should a time sample be accepted?

Time samples are subjected to simple validity tests before being accepted:

1. Any time sample received less than MIN_SAMPLE_INTERVAL after the previous accepted time sample from the same source is rejected. This limits the maximum resource utilization in Timekeeper as a result of time source bugs.
2. Any time sample with a UTC earlier than backstop time is rejected. Accepting a sample before backstop time could cause Timekeeper to place its estimate of UTC earlier than backstop time.
3. Any time sample with a monotonic time far from the current monotonic time is an indication of an error. Time samples where monotonic time is in the future or greater than MIN_SAMPLE_INTERVAL in the past will be rejected.
4. When Timekeeper is configured with a gating source, any time sample from a non-gating source where |sample_utc - (gating_utc + estimated_frequency * (sample_monotonic - gating_monotonic))| > GATING_THRESHOLD is rejected. In this expression gating_utc and gating_monotonic refer to the UTC and monotonic times in the most recently accepted sample from the gating source. This check ensures that all other sources remain consistent with the gating source.

The algorithms designers considered whether to reject time samples that were inconsistent with current estimated UTC (either by being before current UTC or significantly after current UTC) but concluded this was undesirable. Any system that rejects new inputs based on the current estimate is vulnerable to permanent failure if its estimate becomes erroneous and in the case of two mismatched inputs there is no reason to believe the first is more reliable than the second. A system that can recover from an error, even at the cost of a significant jump in time, is preferable to one that cannot.

Which time source should be used?

As introduced in UTC architecture, Timekeeper may be configured to use four different time source roles although it is unlikely that any given product will require more than two.

The primary source, fallback source, and gating source (if these exist) may each be used to drive the primary time estimate and the externally visible clock. These sources are listed in decreasing order of preference; generally a primary time source would be more accurate but less available than a fallback source which in turn would be more accurate but less available than a gating source. A monitor source is subject to consistency checks against a gating source (if one exists) but is otherwise completely independent, driving a separate time estimate and an internal userspace clock that can be compared against the externally visible clock to assess the performance of the monitor time source.

Time sources may take many minutes or hours to converge on an accurate solution so time sources are always launched when Timekeeper is initialized rather than only after the failure of some other time source.

Timekeeper selects the time source based on reported status and the presence of time samples:

1. The primary time source is used if its most recent status is healthy and its most recent valid sample was within SOURCE_KEEPALIVE;
2. Otherwise, the fallback time source is used if its most recent status is healthy and its most recent valid sample was within SOURCE_KEEPALIVE;
3. Otherwise, the gating time source is used if its most recent status is healthy.

Note: As of Q4 2020 gating and fallback sources are not yet supported and therefore the time source selection algorithm has not yet been implemented.

The algorithm designers considered whether to include hysteresis or failure counting in the time source selection algorithm but concluded this would not add sufficient value to compensate for the additional complexity. Many failure modes are accommodated internal to the time sources so complete time source failures should be rare events.

How should a time sample change the estimated UTC?

Each valid sample received from the selected time source should be used to update Timekeeper’s estimate of UTC. Each of these samples contains some error and the size of this error varies between samples. The UTC estimate must therefore combine information from multiple samples rather than blindly following the most recent sample.

This state estimation problem is commonly and efficiently solved using a Kalman filter in other domains. Timekeeper defines a simple two dimensional Kalman filter to maintain the UTC estimate where the two states are UTC time and frequency, expressed as utc nanoseconds per monotonic nanosecond. Note that frequency is maintained external to the filter through the frequency correction algorithm; filter frequency is excluded from the Kalman filter’s measurement model and has a covariance of zero.

The parameters in the Kalman filter are presented in Figure 2.

Note that, as a result of the fixed frequency estimate and the spare process covariance matrix, only the upper left element of the state covariance matrix is ever non-zero. This value is limited to a lower limit of MIN_COVARIANCE to prevent the filter from over-indexing on its internal state and rejecting new inputs.

What strategy should be used to converge the reported UTC?

After each update to the estimated UTC, Timekeeper decides whether to immediately step the userspace clock to the new estimate or apply a rate correction to gradually slew the userspace clock to the new estimate. These options are illustrated in Figure 3.

Step changes in time can be disruptive for time clients and can lead to errors in their calculations so slewing is preferred whenever possible. Slewing is constrained to a maximum rate because slewing at a substantially unrealistic rate could also induce errors in clients; for example, slewing at double real time would be undesirable. Each slew operation is constrained to a maximum duration to bound the time over which the clock is known to be inaccurate; for example, slewing away an error of multiple hours over a period of two weeks would be undesirable.

For small corrections a slew is applied using a fixed small rate for as long as is necessary to achieve the correction. For larger corrections, once the slew duration would reach some maximum, a slew is applied for a fixed duration using whatever rate is necessary to achieve the correction. Once the rate would exceed some maximum Timekeeper resorts to using a time step instead of a slew.

In summary:

1. If |estimated_utc - clock_utc| > MAX_RATE_CORRECTION * MAX_SLEW_DURATION, make a step change to the clock;
2. Otherwise, if |estimated_utc - clock_utc| > PREFERRED_RATE_CORRECTION * MAX_SLEW_DURATION, apply a rate correction of (estimated_utc - clock_utc)/MAX_SLEW_DURATION for a duration of MAX_SLEW_DURATION;
3. Otherwise, apply a rate correction of sign(estimated_utc - clock_utc) * PREFERRED_RATE_CORRECTION for a duration of |estimated_utc - clock_utc|/PREFERRED_RATE_CORRECTION.

How should a sequence of time samples change the estimated frequency?

A device’s oscillator is likely to have some inherent frequency error due to manufacturing imperfections. Estimating the oscillator frequency to account for this error can increase the accuracy of the UTC clock or reduce the frequency at which clock corrections must be made.

The algorithm works with frequency in the form it is applied by the Kalman filter, nanoseconds on the utc clock per nanosecond on the monotonic clock. Note this is the inverse of the oscillator's physical frequency (i.e. nanoseconds on the monotonic clock per nanosecond of real time). An oscillator that is running fast will produce more than one monotonic tick per nanosecond of real time and therefore the UTC clock should run at less than one utc nanosecond per monotonic nanosecond to compensate.

Oscillator errors are bounded by specification to some small value (typically tens of parts per million) hence the UTC estimate algorithm above is stable and reliable even when a frequency estimate is unavailable; the frequency estimate is an enhancement that is beneficial to performance but not necessary.

The frequency estimate is refined over a much longer time period than the UTC estimate. This places the time constants of the two algorithms far apart to avoid potential interactions and ensures the frequency algorithm will not track transient errors such as a temperature driven error while a device is under heavy use. This high time constant means frequency errors would remain in the system for a long time and. As a design philosophy, Timekeeper favors making no improvement in the frequency estimate to introducing an error in the frequency estimate.

Timekeeper estimates a period frequency for each FREQUENCY_ESTIMATION_WINDOW period providing all of the following conditions are met:

1. At least FREQUENCY_ESTIMATION_MIN_SAMPLES time samples were accepted during the period. This avoids placing an excessive weight on a small number of samples if time was unavailable for most of the period.
2. No step changes in time occurred during the period. A step change is evidence of a significant error either before or after the step. These periods are not used to avoid incorporating this error.
3. No part of the period falls within 12 hours of the UTC time at which a leap second may have occurred. Some time sources indulge in leap second smearing where they introduce a significant frequency error for a 24 hour period rather than a step change. These periods are not used to avoid incorporating this frequency error. This affects a maximum of two 24 hour periods a year, fewer if the system tracks whether the next leap second is scheduled.

The period frequency is calculated as the gradient of a least squares linear regression over the (monotonic, utc) tuples for all time samples accepted in the period as illustrated in Figure 4.

This is implemented using the following equation:

period_frequency = {sum(utc * monotonic) - sum(utc)*sum(monotonic)/n}
                   / {sum(monotonic^2) - sum(monotonic)^2/n}

Where n is the number of accepted samples within the period. Note that MIN_SAMPLE_INTERVAL places an upper bounds on this value. The overall frequency estimate is calculated as the exponentially weighted moving average (EWMA) of the period frequencies. In all cases the final estimated frequency is constrained to be within double the standard deviation of the oscillator error such that no combination of the events could cause the frequency error to be wildly inaccurate to the point where it could impact the correctness of the Kalman filter. i.e.

estimated_frequency = clamp(
    period_frequency * FREQUENCY_ESTIMATION_SMOOTHING +
       previous_estimated_frequency * (1 - FREQUENCY_ESTIMATION_SMOOTHING),
    1 - 2 * OSCILLATOR_ERROR_SIGMA,
    1 + 2 * OSCILLATOR_ERROR_SIGMA)

EWMA provides a simple way to blend data across multiple periods while retaining minimal state.

How can clock error be bounded?

For the UTC clock, the error bound is defined as half of a 95% confidence interval. In other words, for a randomly selected time on a randomly selected Fuchsia device, there is a ≥95% probability that the true value of UTC is between reported_utc - error_bound and reported_utc + error_bound. Attempting to report any higher level of confidence would imply a level of certainty that Timekeeper cannot provide because some time failure modes are invisible to Timekeeper. For example, the local oscillator could be running outside its specified tolerance due to a defect or a remote time source could send an incorrect time due to a bug.

The error in the UTC clock is composed of three components:

1. A known difference between the reported clock time and the Kalman filter UTC estimate while a slew is in progress.

   The current clock value and the UTC estimate are easily calculated at any point therefore calculating the difference is trivial. The error bound includes the complete difference, however, this is overly pessimistic.

2. An unknown difference between the Kalman filter UTC estimate and the time standard used by the remote time source.

   Each time source supplies error standard deviations with its time samples. The probability distribution of these errors is not known and may differ between time sources. However, based on the central limit theorem, the normalized sum of independent random variables approaches a normal distribution even if the original random variables were not normally distributed. Since the Kalman filter is averaging the input samples (albeit not equally), it is expected that the error distribution of the Kalman filter approaches a normal distribution as the filter accumulates a large number of samples, with a standard deviation that is determined by the covariance. This error bound includes a term of twice the square root of covariance in the error bound to account for this error component. This this may either be optimistic or pessimistic for early time samples while the filter error is dominated by the unknown probability distribution received from the time source.

3. A known difference between the time standard used by the remote time source and true UTC.

   Some sources, such as Google, "smear" leap seconds by deliberately introducing an error of up to 500ms to the reported time during the 24 hours surrounding a leap second. This algorithm does not document this error in the error bound, reasoning that the complexity and computational cost of documenting smearing error is not worth the benefit to time clients. Leap seconds occurred five times between 2000 and 2020 causing a smearing error on 0.07% of all days in this range. It is unlikely this can cause the final bound to fail the 95% confidence criteria.

In summary, the error bound is calculated in the following way: error_bound = 2 * sqrt(covariance[0,0]) + |estimated_utc - clock_utc|

Until the Kalman filter has been initialized by receipt of the first time sample, the error bound is set to ZX_CLOCK_UNKNOWN_ERROR. This includes the case where the clock has been initialized from the real-time clock (RTC) but the network time is not yet available.

The error bound calculation is summarized in Figure 5:

What clock updates should be made?

Changes to the rate and offset of the clock follow directly from selecting a convergence strategy and estimating the oscillator frequency as discussed in earlier algorithms. The error bound defined by the previous algorithm is a continuously changing value that must be periodically published in the clock.

While a large slew is in progress the clock is continually approaching the Kalman filter estimate and therefore the error bound is continuously decreasing. To limit resource utilization Timekeeper only updates zx_clock_details_v1.error_bound during a slew when either some other clock update is required or when the error in the last reported value exceeds ERROR_BOUND_UPDATE.

While a slew is not in progress, the error bound is continuously and slowly increasing as the oscillator frequency error accumulates. Outside a slew, timekeeper updates zx_clock_details_v1.error_bound at some conveniently low frequency, ensuring that the error in the last reported value never exceeds ERROR_BOUND_UPDATE.

In summary, Timekeeper makes updates to the UTC clock as follows:

• Step changes to the clock are always implemented as a single clock update.
• Clock slews are usually implemented as two clock updates: a rate change to 1/estimated_frequency + rate_correction when the slew is started followed by a rate change to 1/estimated_frequency after a delay of slew_duration. If a subsequent update is accepted before this second clock change, the second clock change is discarded.
• If a new frequency estimate is calculated while no clock slew is in progress, the clock rate is changed to 1/estimated_frequency (if a clock slew is in progress, the clock update at the end of the slew picks up the new frequency update).
• If |last_set_error_bound - error_bound| > ERROR_BOUND_UPDATE, the error bound is updated.

Configurable Parameters

The previous sections introduced a number of parameters that may be used to configure the behavior of the algorithms. The following tables provide more information about each of these parameters and justify the initial value that is used.

GATING_THRESHOLD

The gating threshold limits how close time samples from non-gating sources must be to the UTC that the gating source indicates. This may be used to ensure less trusted sources are broadly consistent with a cryptographically verifiable time source.

MIN_SAMPLE_INTERVAL

The minimum sample interval bounds the maximum rate at which Timekeeper is willing to accept new samples from a time source in order to limit the Timekeeper resource utilization. Note this is relevant since in the fuchsia.time.external.PushSource protocol it is the time source that determines when time samples should be generated. This value is also used to apply an upper limit on the monotonic age of time samples.

SOURCE_KEEPALIVE

The source keepalive determines how frequently a source that declares itself to be healthy needs to produce samples in order to remain selected. If a time source fails to generate any time samples for this period and a source lower in the primary > fallback > gating hierarchy is available that other source will be used instead. This parameter is not used unless either a fallback or gating time source is configured.

OSCILLATOR_ERROR_SIGMA

The standard deviation of the system oscillator frequency error, used to control the growth in uncertainty during the prediction phase of the Kalman filter.

MIN_COVARIANCE

Minimum covariance bounds the minimum uncertainty of the UTC estimate in the Kalman filter. This helps the filter not drink its own bathwater after receiving very low uncertainty samples from a time source.

MAX_RATE_CORRECTION

Max rate correction bounds the fastest rate at which Timekeeper will deliberately adjust the clock frequency in order to slew away a UTC error. This is in addition to any clock frequency adjustment used to compensate for an oscillator frequency error.

MAX_SLEW_DURATION

Max slew duration bounds the longest duration for which Timekeeper will apply a clock frequency adjustment in response to a single time sample. Consecutive time samples may introduce errors that each trigger a slew and therefore this per-sample duration does not constrain the total time over which Timekeeper may be in the process of slewing.

PREFERRED_RATE_CORRECTION

The rate at while Timekeeper adjusts the clock frequency to slew away small errors.This is in addition to any clock frequency adjustment used to compensate for an oscillator frequency error.

FREQUENCY_ESTIMATION_WINDOW

The time period over which a set of time samples are collected to update the frequency estimate.

FREQUENCY_ESTIMATION_MIN_SAMPLES

The minimum number of samples that must be received in a frequency estimation window for it to be eligible for a frequency estimate.

FREQUENCY_ESTIMATION_SMOOTHING

The factor applied to the current period during the exponentially weighted moving average calculation of frequency.

ERROR_BOUND_UPDATE

The minimum change in value that causes the error bound in UTC clock details to be updated even when no rate or offset changes are required. This parameter controls how frequently the clock must be updated while a significant slew is in progress.