5. Local Clocks

In order to implement a precise and accurate local clock, the host must be equipped with a hardware clock consisting of an oscillator and interface and capable of the required precision and stability. A logical clock is then constructed using these components plus software components that adjust the apparent time and frequency in response to periodic updates computed by NTP or some other time-synchronization protocol such as Hellospeak [MIL83b] or the Unix 4.3bsd TSP [GUS85a]. This section describes the Fuzzball local-clock model and implementation, which includes provisions for precise time and frequency adjustment and can maintain time to within 15 ns and frequency to within 0.3 ms per day. The model is suitable for use with both compensated and uncompensated quartz oscillators and can be adapted to power-frequency oscillators. A summary of the characteristics of these and other types of oscillators can be found in Appendix E, while a comprehensive mathematical analysis of the NTP local-clock model can be found in Appendix G.

It is important to note that the particular implementation described is only one of possibly many implementations that provide equivalent functionality. However, it is equally important to note that the clock model described in Appendix G and which is the basis of the implementation involves a particular kind of control-feedback loop that is potentially unstable if the design rules are broken. The model and parameter described in Appendix G are designed to provide accurate and stable time under typical operating conditions using conventional hardware and in the face of disruptions in hardware or network connectivity. The parameters have been engineered for reliable operation in a multi-level hierarchical subnet where unstable operation at one level can disrupt possibly many other levels.

5.1. Fuzzball Implementation

The Fuzzball local clock consists of a collection of hardware and software registers, together with a set of algorithms, which implement a logical clock that functions as a disciplined oscillator and synchronizes to an external source. Following is a description of its components and manner of operation. Note that all arithmetic is two's complement integer and all shifts "<<" and ">>" are arithmetic (sign-fill for right shifts and zero-fill for left shifts). Also note that x << n is equivalent to x >> -n.

The principal components of the local clock are the 48-bit Clock register and 32-bit Prescaler which function as a disciplined oscillator increments in milliseconds relative to midnight at the fraction point. The 32-bit Clock-Adjust register is used to adjust the oscillator phase in gradual steps to avoid discontinuities in the indicated timescale. Its contents are designated x in the following. The 32-bit Skew-Compensation register is used to trim the oscillator frequency by adding small phase increments at periodic adjustment intervals and can compensate for frequency errors as much as 0.01% or ±100 ppm. Its contents are designated y in the following. The 16-bit Watchdog counter and 32-bit Compliance register are used to determine validity, as well as establish the PLL bandwidth and poll interval (see Appendix G). The contents of the Compliance register are designated z in the following. The 32-bit PPS-Adjust register is used only when a pulse-per-second (PPS) signal is available and is used to adjust the clock.

The principal data structure consists of a 48-bit timestamp and the Offset (THETA), Delay (DELTA) and Dispersion (EPSILON) associated with it. In the Fuzzball implementation the Clock register is designed to increment in units of one millisecond (ms), so a 32-bit Prescaler register is used to interpolate between millisecond increments. The hardware clock consists of a programmable bus timeout clock driven by a crystal oscillator that typically ticks at intervals of a few microseconds. At each tick an interrupt occurs and a constant TICK is added to the Prescaler. When the Prescaler overflows (about once per millisecond), a constant TICK1MS is added to the Clock register.

5.2. Gradual Phase Adjustments

The Clock-Adjust register is used to adjust the phase of the local clock in gradual steps. At each clock interrupt the contents x of the Clock-Adjust register are added to the Prescaler register as follows:

Prescaler <- Prescaler + TICK + x

Since x can be a positive or negative integer, the above operation varies the frequency of the local clock. At each second change the Clock-Adjust register is increased or decreased by CLOCK.ADJUST (typically 8), which has the effect of increasing or decreasing the clock frequency and correspondingly decreasing or increasing the time to adjust the clock. In case the residual offset is less than CLOCK.MAX (typically 128 ms), the clock frequency is adjusted by a smaller amount and the clock epoch adjusted by an amount proportional to the residual offset.

The following algorithm is executed at each clock interrupt:

if (|THETA| >= CLOCK.MAX)               /* phase adjustment */
    if (THETA > 0)
        x <- x + CLOCK.ADJUST
    else if (THETA < 0)
        x <- x - CLOCK.ADJUST
    call adjust-phase
else                                     /* frequency adjustment */
    x <- THETA / CLOCK.PHI
    Prescaler <- Prescaler + x
    THETA <- 0

The procedure adjust-phase is called to adjust the phase and update various state variables. In the Fuzzball implementation the compliance register is a circular buffer of length NTP.WINDOW, which is used to record recent history. At the beginning of each second of local time the compliance register is updated, and the oldest value discarded. An estimate of the compliance is then computed as the exponentially weighted average of the absolute value of all entries.

5.3. Step Phase Adjustments

If the magnitude of the phase adjustment exceeds CLOCK.MAX (typically 128 ms), a step adjustment is performed. The step adjustment is used when the local clock time differs significantly from the reference time, such as after reboot or when a correction is required due to a time-zone change. In a step adjustment, the clock is set directly to the new time, and all ongoing estimates of frequency and compliance are reinitialized.

The following algorithm is used:

if (first update)                       /* never allow step on first update */
    exit
if (|THETA| >= CLOCK.MAXSTEP)          /* step the clock */
    Clock <- Clock + THETA
    THETA <- 0
    Watchdog <- 0
    Compliance <- 0
    return (TRUE)
else
    return (FALSE)

The Watchdog counter is reset to zero each time the Clock-Adjust register is updated. If the counter reaches the value CLOCK.HOLDTC (typically 2048 s or about 34 minutes), the Clock-Adjust register is reset to zero. This provides hysteresis and prevents use of obsolete offset data.

5.4. Implementation Issues

The particular local-clock model described here and in Appendix G is based on a second-order feedback loop. The loop time constant is relatively long, on the order of several hours, in order to minimize the effect of transient network delays and maximize stability. As a result, changes in the frequency correction can take considerable time to complete, especially after reboot or step phase adjustment. In order to speed up the loop response, the Clock-Adjust register can be preloaded with the last value computed before a shutdown.

In the Fuzzball implementation a comprehensive monitoring and control facility is provided to examine all local-clock variables and control the operation of the clock. In addition, a special feature provides a time-of-day display indicating not only the clock reading, but the compliance and whether a valid synchronization source is available. Additional information on the design and implementation of the Fuzzball local clock can be found in [MIL88b].

The local-clock model described here is specifically designed to work with NTP and in the Internet environment. However, there are many other possibilities that may be more appropriate in different circumstances. For instance, some systems may have access to a precision oscillator that is highly stable over long intervals, such as a cesium oscillator or GPS receiver. In such cases the frequency-correction mechanisms may be unnecessary or inappropriate. Furthermore, if high precision over intervals of a second or so is required, such as for voice or video applications, the gradual phase-correction mechanisms described here may not provide adequate precision. In such cases some form of predictor-corrector or phase-locked loop may be necessary to interpolate between infrequent updates from NTP.

As mentioned earlier, in some configurations a precision timing pulse spaced at one-second intervals may be available. In such cases it may be appropriate to use the PPS signal to discipline the local clock frequency, while using NTP to discipline the numbering of the seconds, minutes, hours and days. This can provide precisions in the order of microseconds while still providing authentic UTC time. In such cases care must be taken that the numbering source not fail without taking appropriate action to suppress further updates from the PPS signal.