• a simple set of packets that are transferred via UDP over a network to exchange time information
• a series of algorithms for combining time estimates from multiple sources
• an authentication scheme based on symmetric-key cryptography
• a series of algorithms for managing a local clock
• algorithms for handling leap seconds, time scales and other "real-world" issues

The first of these things is what most people associate with NTP when they use it on their PC.

Basic Operation

The basic operation of NTP that people may be familiar with is synchronising the clock in one computer to that in another. This works as follows:

1. One computer (the client) sends a packet to a specified NTP Server. In this packet it stores the time the packet left as defined by its clock (T1C)
2. The NTP server receives the packet and notes the time it received the packet, according to its clock (T1S)
3. The NTP server sends a packet back to the client noting what time it was sent according to its clock (T2S). The packet sent back contains all three time stamps, T1C, T1S and T2S
4. The client receives the packet from the server and notes what time it receives the packet according to its clock (T2C)

The client now has four time stamps. From this it can determine the round-trip delay and clock offset.

Let a = T1S - T1C
and b = T2S - T2C

Round-trip delay, D = a - b and
Clock offset, O = (a+b)/2

A long and boring analysis defines the maximum error that can accrue under any condition called the synchronisation distance, L; and the error expected under normal operating conditions called the dispersion, E. The dispersion E depends on several factors including

1. The error in reading and adjusting the local clock. In the Kelunji Echo this is approximately 4 microseconds
2. The error due to the frequency tolerance of the clock and the time since the clock was last set
3. The estimated error caused by each peer being used as a reference. When using the GPS receiver in the Kelunji Echo, this is less than one microsecond
4. The estimated error caused by combining estimates from a number of clocks

Typically, these values are much smaller than the network delays. For the Kelunji Echo the dispersion value will normally only be around 5 microseconds, whereas even on a high speed Ethernet, the round trip delay will often be around 1 millisecond. The analysis referred to above indicates that a good estimate for the synchronisation distance, L is

L = D/2 + E

This implies that the true clock offset will be (a+b)/2 ± L These values O and L are the primary values determined by the NTP algorithm.

Actual Architecture

The actual NTP architecture is much more complicated (and clever) than the basic algorithm would imply. The overall architecture is shown in the picture below.

This diagram shows the different parts of the system. The servers on the left of the diagram are what were referred to in the simple description above. They exchange NTP messages with a number of clients. Each client then uses the clock filtering, selection, clustering and combining algorithms to determine a new estimate of its local clock offset. This offset is then used by the clock discipline algorithm to drive the loop filter for the local clock. Each of these stages will be described in turn.

Data Filtering

The NTP data filtering algorithm has evolved over several years of experimentation and experience with Internet paths. It is designed specifically to provide high accuracy together with low computational burden. The problem comes down to estimating the true clock offset and round-trip delay from a sample population of these values.

The fact that most networks are operating with relatively light loads for most of the time suggests the use of a minimum filter. This selects from the most recent n samples of (D, O) pairs, that sample with the lowest delay, D. In the standard implementation, the most recent 8 pairs are used and sorted in to order of increasing D. The first pair in the list is then used as the best estimate of D and O and the other values in the list are used to compute the dispersion E.

Selection, Clustering and Combining

As each new estimated offset is obtained for a peer as described above, a series of algorithms are executed to determine whether the estimate should be kept and then to combine all such estimates to come up with the "best" overall estimate of local clock offset. The details of these algorithms are not generally of interest here, the interested reader is referred to the developers Web site for further details.

Local Clock Design

This is one of the most useful aspects of the NTP protocol for our application. As shown in the diagram above, it assumes the presence of a variable frequency oscillator and implements a loop filter to control this. In both the Kelunji D Series and Echo, we have such an oscillator in the form of a voltage controlled oscillator where we can set the control voltage to change the frequency of oscillation. The problem then reduces to the clock discipline algorithm itself.

In NTP Version 4, the algorithm functions as a true hybrid of two philosophically quite different feedback control systems. In a phase-locked-loop (PLL) design, the measured time (or phase) error is used to discipline a type II feedback loop which controls the phase and frequency of the clock oscillator. In a frequency-locked-loop (FLL) design, the measured time and frequency errors are used separately to discipline type I feedback loops, one controlling the time (phase) and the other controlling the frequency. Experiments have confirmed that a hybrid combination of the two can significantly improve the performance of the system under widely varying conditions of network delay and clock oscillator instability. It is this hybrid system that is employed in NTP version 4.

Each time a new estimate of clock offset, O, becomes available, an adjustment for the VCO is calculated. This is done in two parts, one is to correct for time or phase errors and the other is to correct for frequency errors. It is in determining the details of how these two estimates are made that the NTP developers spent much research and testing.

Poll Interval

One issue we have not yet discussed, is how often a new estimate of clock offset should be made to ensure that the clock stays "on time". This is another area where NTP version 4 is considerably improved on earlier versions. In NTP parlance, this is called the poll interval, and the algorithms are designed for poll intervals ranging from 16 seconds to greater than one day. The poll interval is determined dynamically based on the observed clock offset measurements. Typically, if the temperature of the oscillator is constant, the poll interval will increase as better and better estimates are obtained of the oscillator frequency. When the temperature changes, the oscillator frequency will change and the poll interval will reduce to try and track these changes.

In the Kelunji Echo release 1 software, the poll interval using the GPS receiver is allowed to vary automatically from 16 seconds up to 1024 seconds. With these settings, the clock is usually kept to be within 1 millisecond of UTC. If a tighter tolerance was required, a smaller allowable poll interval could be selected.

Copyright © 2004, Environmental Systems and Services, Pty Ltd
Last modified: 2004-08-31