from Alice's Adventures in Wonderland, Lewis Carroll
Listen carefully to what I say; it is very complicated.
Last update:
The mechanics of the NTP algorithms which select the best data sample from each available server and the best subset of the server population have been finely crafted to resist network jitter, faults in the network or server operations, and to deliver the best possible accuracy. Most of the time these algorithms do a good job without requiring explicit manual tailoring of the configuration file. However, there are times when the accuracy can be improved by some careful tailoring. The following sections explain how to do this using explicit configuration items and special signals, when available, that are generated by some radio clocks and laboratory instruments.
In order to provide robust backup sources, primary (stratum-1) servers are usually operated in a diversity configuration, in which the server operates with a number of remote servers in addition to one or more radio or modem clocks. In these configurations the suite of algorithms used in NTP to refine the data from each peer separately and to select and combine the data from a number of servers and clocks. As the result of these algorithms, a set of survivors are identified which can presumably provide the most reliable and accurate time. Ordinarily, the individual clock offsets of the survivors are combined on a weighted average basis to produce an offset used to control the system clock.
However, because of small but significant systematic time offsets between the survivors, it is in general not possible to achieve the lowest jitter and highest stability in these configurations. This happens because the selection algorithm tends to clockhop between survivors of substantially the same quality, but showing small systematic offsets between them. In addition, there are a number of configurations involving pulse-per-second (PPS) signals, modem backup services and other special cases, so that a set of mitigation rules becomes necessary to select a single peer from among the survivors. These rules are based on a set of special characteristics of the various remote servers and reference clock drivers specified in the configuration file.
The mitigation rules are designed to provide an intelligent selection between various sources of substantially the same statistical quality without compromising the normal operation of the NTP algorithms. While they have been implemented in NTP Version 4 and will be incorporated in the NTP Version 4 specification when published, they are not in the NTP Version 3 specification RFC-1305. The rules are based on the concept of prefer peer, which is specified by including the prefer keyword with the associated server or peer command in the configuration file. This keyword can be used with any server or peer, but is most commonly used with a radio clock. While the rules do not forbid it, it does not seem useful to designate more than one peer as preferred, since the additional complexities to mitigate among them do not seem justified from on-air experience.
The prefer scheme works on the set of peers that have survived the sanity checks and intersection algorithms of the clock selection procedures. Ordinarily, the members of this set can be considered truechimers and any one of them could in principle provide correct time; however, due to various error contributions, not all can provide the most accurate and stable time. The job of the clustering algorithm, which is invoked at this point, is to select the best subset of the survivors providing the least variance in the combined ensemble average, compared to the variance in each member of the subset separately. The detailed operation of the clustering algorithm, which is given in RFC-1305, is beyond the scope of discussion here. It operates in rounds, where a survivor, presumably the worst of the lot, is discarded in each round until one of several termination conditions is met. An example terminating condition is when the number of survivors is about to be reduced below three.
In the prefer scheme the clustering algorithm is modified so that the prefer peer is never discarded; on the contrary, its potential removal becomes a termination condition. If the original algorithm were about to toss out the prefer peer, the algorithm terminates immediately. The prefer peer can still be discarded by the sanity checks and intersection algorithm, of course, but it will always survive the clustering algorithm. If it does not survive or for some reason it fails to provide updates, it will eventually become unreachable and the clock selection will remitigate to select the next best source.
Along with this behavior, the clock selection procedures are modified so that the combining algorithm is not used when a prefer peer is present. Instead, the offset of the prefer peer is used exclusively as the synchronization source. In the usual case involving a radio clock and a flock of remote stratum-1 peers, and with the radio clock designated a prefer peer, the result is that the high quality radio time disciplines the server clock as long as the radio itself remains operational and with valid time, as determined from the remote peers, sanity checks and intersection algorithm.
In order to understand the effects of the various intricate schemes involved, it is necessary to understand some arcane details on how the algorithms decide on a synchronization source when more than one source is available. This is done on the basis of a set of explicit mitigation rules, which define special classes of remote serves and local radio clocks as a function of configuration declarations and clock driver type:
Reference clock drivers operate in the manner described in the Reference Clock Drivers page and its dependencies. The drivers are ordinarily operated at stratum zero, so that as the result of ordinary NTP operations, the server itself operates at stratum one, as required by the NTP specification. In some cases described below, the driver is intentionally operated at an elevated stratum, so that it will be selected only if no other survivor is present with a lower stratum. In the case of the PPS peer or kernel time discipline, these sources appear active only if the prefer peer has survived the intersection and clustering algorithms, as described below, and its clock offset relative to the current local clock is less than a specified value, currently 128 ms.
The modem clock drivers are a special case. Ordinarily, the update interval between modem calls to synchronize the system clock is many times longer than the interval between polls of either a remote server or local radio clock. In order to provide the best stability, the operation of the clock discipline algorithm changes gradually from a phase-lock mode at the shorter update intervals to a frequency-lock mode at the longer update intervals. If remote servers or local radio clocks together with a modem peer operate in the same client, the following things can happen.
First the clock selection algorithm can select one or more remote servers or local radio clocks and the clock discipline algorithm will optimize for the shorter update intervals. Then, the selection algorithm can select the modem peer, which requires a much different optimization. The intent in the design is to allow the modem peer to control the system clock either when no other source is available or, if the modem peer happens to be marked as prefer, then it always controls the clock, as long as it passes the sanity checks and intersection algorithm. There still is room for suboptimal operation in this scheme, since a noise spike can still cause a clockhop either way. Nevertheless, the optimization function is slow to adapt, so that a clockhop or two does not cause much harm.
The local clock driver is another special case. Normally, this driver is eligible for selection only if no other source is available. When selected, vernier adjustments introduced via the configuration file or remotely using the ntpdc program can be used to trim the local clock frequency and time. However, if the local clock driver is designated the prefer peer, this driver is always selected and all other sources are ignored. This behavior is intended for use when the kernel time is controlled by some means external to NTP, such as the NIST lockclock algorithm or another time synchronization protocol such as DTSS. In this case the only way to disable the local clock driver is to mark it unsynchronized using the leap indicator bits. In the case of modified kernels with the ntp_adjtime() system call, this can be done automatically if the external synchronization protocol uses it to discipline the kernel time.
The mitigation rules apply in the intersection and clustering algorithms described in the NTP specification. The intersection algorithm first scans all peers with a persistent association and includes only those that satisfy specified sanity checks. In addition to the checks required by the specification, the mitigation rules require either the local-clock peer or modem peer to be included only if marked as the prefer peer. The intersection algorithm operates on the included population to select only those peers believed to represent the correct time. If one or more peers survive the algorithm, processing continues in the clustering algorithm. Otherwise, if there is a modem peer, it is declared the only survivor; otherwise, if there is a local-clock peer, it is declared the only survivor. Processing then continues in the clustering algorithm.
The clustering algorithm repeatedly discards outlyers in order to reduce the residual jitter in the survivor population. As required by the NTP specification, these operations continue until either a specified minimum number of survivors remain or the minimum select dispersion of the population is greater than the maximum peer dispersion of any member. The mitigation rules require an additional terminating condition which stops these operations at the point where the prefer peer is about to be discarded.
The mitigation rules establish the choice of system peer, which determines the stratum, reference identifier and several other system variables which are visible to clients of the server. In addition, they establish which source or combination of sources control the local clock.