Other mechanisms have been specified in the Internet protocol
suite to record and transmit the time at which an event takes place, including the Daytime protocol [POS83a], Time Protocol [POS83b],
ICMP Timestamp message [DAR81b] and IP Timestamp option [SU81]. Experimental results on measured clock offsets and roundtrip delays in
the Internet are discussed in [MIL83a], [MIL85b], [COL88] and [MIL88a]. Other synchronization algorithms are discussed in [LAM78],
[GUS84], [HAL84], [LUN84], [LAM85], [MAR85], [MIL85a], [MIL85b], [MIL85c], [GUS85b], [SCH86], [TRI86], [RIC88], [MIL88a], [DEC89] and
[MIL91a], while protocols based on them are described in [MIL81a], [MIL81b], [MIL83b], [GUS85a], [MIL85c], [TRI86], [MIL88a], [DEC89]
and [MIL91a]. NTP uses techniques evolved from them and both linear-systems and agreement methodologies. Linear methods for digital
telephone network synchronization are summarized in [LIN80], while agreement methods for
clock synchronization are summarized in [LAM85].
The Digital Time Service (DTS) [DEC89] has many of the same service objectives as NTP. The DTS design places heavy emphasis on
configuration management and correctness principles when operated in a managed LAN or LAN-cluster environment, while NTP places heavy
emphasis on the accuracy and stability of the service operated in an unmanaged, global-internet environment. In DTS a synchronization
subnet consists of clerks, servers, couriers and time providers. With respect to the NTP nomenclature, a time provider is a primary
reference source, a courier is a secondary server intended to import time from one or more distant primary servers for local
redistribution and a server is intended to provide time for possibly many end nodes or clerks. Unlike NTP, DTS does not need or use
mode or stratum information in clock selection and does not include provisions to filter timing noise, select the most accurate from a
set of presumed correct clocks or compensate for inherent frequency errors.
In fact, the latest revisions in NTP have adopted certain features of DTS in order to support correctness principles. These include
mechanisms to bound the maximum errors inherent in the time-transfer procedures and the use of a provably correct (subject to stated
assumptions) mechanism to reject inappropriate peers in the clock-selection procedures. These features are described in Section 4 and
Appendix H of this document.
The Fuzzball routing protocol [MIL83b], sometimes called Hellospeak, incorporates time synchronization directly into the
routing-protocol design. One or more processes synchronize to an external reference source, such as a radio clock or NTP daemon, and
the routing algorithm constructs a minimum-weight spanning tree rooted on these processes. The clock offsets are then distributed
along the arcs of the spanning tree to all processes in the system and the various process clocks corrected using the procedure
described in Section 5 of this document. While it can be seen that the design of Hellospeak strongly influenced the design of NTP,
Hellospeak itself is not an Internet protocol and is unsuited for use outside its local-net environment.
The Unix 4.3bsd time daemon timed [GUS85a] uses a single master-time daemon to measure offsets of a number of slave hosts and send
periodic corrections to them. In this model the master is determined using an election algorithm [GUS85b] designed to avoid situations
where either no master is elected or more than one master is elected. The election process requires a broadcast capability, which is
not a ubiquitous feature of the Internet. While this model has been extended to support hierarchical configurations in which a slave
on one network serves as a master on the other [TRI86], the model requires handcrafted configuration tables in order to establish the
hierarchy and avoid loops. In addition to the burdensome, but presumably infrequent, overheads of the election process, the offset
measurement/correction process requires twice as many messages as NTP per update.
A scheme with features similar to NTP is described in [KOP87]. This scheme is intended for multi-server LANs where each of a set of
possibly many time servers determines its local-time offset relative to each of the other servers in the set using periodic
timestamped messages, then determines the local-clock correction using the Fault-Tolerant Average (FTA) algorithm of [LUN84]. The FTA
algorithm, which is useful where up to k servers may be faulty, sorts the offsets, discards the k highest and lowest ones and averages
the rest. The scheme, as described in [SCH86], is most suitable to LAN environments which support broadcast and would result in
unacceptable overhead in an internet environment. In addition, for reasons given in Section 4 of this paper, the statistical
properties of the FTA algorithm are not likely to be optimal in an internet environment with highly dispersive delays.
A good deal of research has gone into the issue of maintaining accurate time in a community where some clocks cannot be trusted. A
truechimer is a clock that maintains timekeeping accuracy to a previously published (and trusted) standard, while a falseticker is a
clock that does not. Determining whether a particular clock is a truechimer or falseticker is an interesting abstract problem which
can be attacked using agreement methods summarized in [LAM85] and [SRI87].
A convergence function operates upon the offsets between the clocks in a system to increase the accuracy by reducing or eliminating
errors caused by falsetickers. There are two classes of convergence functions, those involving interactive-convergence algorithms and
those involving interactive-consistency algorithms. Interactive-convergence algorithms use statistical clustering techniques such as
the fault-tolerant average algorithm of [HAL84], the CNV algorithm of [LUN84], the majority-subset algorithm of [MIL85a], the
non-Byzantine algorithm of [RIC88], the egocentric algorithm of [SCH86], the intersection algorithm of [MAR85] and [DEC89] and the
algorithms in Section 4 of this document.
Interactive-consistency algorithms are designed to detect faulty clock processes which might indicate grossly inconsistent offsets in
successive readings or to different readers. These algorithms use an agreement protocol involving successive rounds of readings,
possibly relayed and possibly augmented by digital signatures. Examples include the fireworks algorithm of [HAL84] and the optimum
algorithm of [SRI87]. However, these algorithms require large numbers of messages, especially when large numbers of clocks are
involved, and are designed to detect faults that have rarely been found in the Internet experience. For these reasons they are not
considered further in this document.
In practice it is not possible to determine the truechimers from the falsetickers on other than a statistical basis, especially with
hierarchical configurations and a statistically noisy Internet. While it is possible to bound the maximum errors in the time-transfer
procedures, assuming sufficiently generous tolerances are adopted for the hardware components, this generally results in rather poor
accuracies and stabilities. The approach taken in the NTP design and its predecessors involves mutually coupled oscillators and
maximum-likelihood estimation and clock-selection procedures, together with a design that allows provable assertions on error bounds
to be made relative to stated assumptions on the correctness of the primary reference sources. From the analytical point of view, the
system of distributed NTP peers operates as a set of coupled phase-locked oscillators, with the update algorithm functioning as a
phase detector and the local clock as a disciplined oscillator, but with deterministic error bounds calculated
at each step in the time-transfer process.
The particular choice of offset measurement and computation procedure described in Section 3 is a variant of the returnable-time
system used in some digital telephone networks [LIN80]. The clock filter and selection algorithms are designed so that the clock
synchronization subnet self-organizes into a hierarchical-master-slave configuration [MIT80]. With respect to timekeeping accuracy and
stability, the similarity of NTP to digital telephone systems is not accidental, since systems like this have been studied extensively
[LIN80], [BRA80]. What makes the NTP model unique is the adaptive configuration, polling, filtering, selection and correctness
mechanisms which tailor the dynamics of the system to fit the ubiquitous Internet environment.