Executive Summary: Computer Network Time Synchronization

Last update: May 3, 2023 19:04 UTC (011154ffc)

gif

from Alice’s Adventures in Wonderland, Lewis Carroll

The executive is the one on the left.

Abstract

The Network Time Protocol (NTP) and other protocols are used to synchronize the clocks in an estimated total of 25 million servers, workstations and PCs of the public Internet and private networks. This document contains an overview and functional description of NTP, and its design principles. The material in this document is intended for network architects, administrators and technical operating personel. Additional technical details on design and operation are discussed in related white papers in this collection.

Introduction

This document contains an overview and functional description of the Network Time Protocol (NTP), which is used to synchronize computer clocks in the Internet to a common timescale. The discussion is intended for site managers and administrators as well as technical planning and support staff. This document does not describe the architecture, protocols and algorithm in detail; for that, see the tutorial collection How NTP Works.

The standard timescale used by most nations of the world is Coordinated Universal Time (UTC), which is based on the Earth’s rotation about its axis, and the Gregorian Calendar, which is based on the Earth’s rotation about the Sun. The UTC timescale is disciplined with respect to International Atomic Time (TAI) by inserting leap seconds at intervals of about 18 months. UTC time is disseminated by various means, including radio and satellite navigation systems, telephone modems and portable clocks. Insertion of leap seconds in the NTP and POSIX timescale is discussed in the white paper The NTP Timescale and Leap Seconds.

Special purpose receivers are available for many time-dissemination services, including the Global Position System (GPS) and other services operated by various national governments. For reasons of cost and convenience, it is not possible to equip every computer with one of these receivers. However, it is possible to equip some number of computers acting as primary time servers to synchronize a much larger number of secondary servers and clients connected by a common network. In order to do this, a distributed network clock synchronization protocol is required which can read a server clock, transmit the reading to one or more clients and adjust each client clock as required. Protocols that do this include the Network Time Protocol (NTP), IEEE 1588 Precision Time Protocol (PTP), Digital Time Synchronization Service (DTSS), and others found in the literature (See Further Reading).

Protocol Design Issues

The synchronization protocol determines the time offset of the server clock relative to the client clock. The various synchronization protocols in use today provide different means to do this, but they all follow the same general model. On request, the server sends a message including its current clock value or timestamp and the client records its own timestamp upon arrival of the message. Additional information on the NTP timescale and timescale calculations is in the white papers NTP Timestamp Calculations and The NTP Era and Era Numbering.

For the best accuracy, the client needs to measure the server-client propagation delay to determine its clock offset relative to the server. Since it is not possible to determine the one-way delays, unless the actual clock offset is known, the protocol measures the total roundtrip delay and calculates the propagation delay is half the roundtrip delay. This assumes the propagation delays are statistically equal in each direction. In general, this is a useful approximation; however, in the Internet of today, network paths and the associated delays can differ significantly due to the individual service providers.

The community served by the synchronization protocol can be very large. For instance, the NTP community in the Internet of today includes over 1000 public primary time servers synchronized by radio, satellite and telephone modem, and well over 25 million secondary servers and clients. In addition, there are many thousands of private communities in large government, corporate and institution networks.

Each community is organized as a tree graph or subnet, with the primary servers at the root and secondary servers and clients at increasing hop count, or stratum level, in corporate, department and desktop networks. It is usually necessary at each stratum level to employ redundant servers and diverse network paths in order to protect against broken software, hardware, networks and potential hostile attack.

Synchronization protocols work in one or more association modes, depending on the protocol design. Client/server mode, also called master/slave mode, is supported in NTP, PTP and DTSS. In this mode, a client synchronizes to a stateless server as in the conventional RPC model. NTP also supports symmetric mode, which allows either of two peer servers to synchronize to the other, in order to provide mutual backup.

NTP, PTP and DTSS support a broadcast mode which allows many clients to synchronize to one or a few servers, reducing network traffic when large numbers of clients are involved. In NTP, IP multicast can be used when the subnet spans multiple networks.

Configuration management can be a serious problem in large subnets. Various schemes which index public /reflibs and network directory services are used in NTP and DTSS to discover servers. Both protocols use broadcast modes to support large client populations; but, since listen-only clients cannot calibrate the delay, accuracy can suffer. In NTP and PTP, clients determine the delay at the time a server is first discovered by polling the server in client/server mode and then reverting to listen-only mode. In addition, NTP clients can broadcast a special “manycast” message to solicit responses from nearby servers and continue in client/server mode with the respondents. Additional details about the NTP protocol are in the white paper Analysis and Simulation of the NTP On-Wire Protocols. Additional details about NTP and PTP interoperation are in the white paper IEEE 1588 Precision Time Protocol.

Precision and Accuracy

The NTP accuracy expectations depend on the environment and application requirements. In practice, the single factor most affecting accuracy at the longer update intervals used on global network paths is ambient temperature variations. Under typical room temperature conditions, the clock oscillator frequency can vary in the order of one part-per-million (PPM). This results in synchronization accuracy in the order of a few milliseconds at update intervals of fifteen minutes. However, accuracy can be much improved to the order of one millisecond at update intervals of one minute, as used with primary reference clocks.

At the lower update intervals, the primary factor affecting accuracy is jitter due to network and operating system latencies. With a GPS receiver and pulse-per-second (PPS) signal, together with operating system support in typical Unix kernels, the accuracy is in the order of a few microseconds. This of course is a property of the hardware and operating system, not the NTP protocol.

As a rule of thumb, the accuracy over the Internet is proportional to the propagation delay. For a lightly loaded 100-Mb/s Ethernet, the accuracy is in the order of 100 μs. For an intercontinental Internet path, the accuracy can be up to several tens of milliseconds.

On network paths with large asymmetric propagation delays, such as when one direction is via satellite and the other via landline, the errors can reach 100 ms or more. There is no way these errors can be avoided, unless there is prior knowledge of the path characteristics.

Security Issues

A reliable network time service requires provisions to prevent accidental or malicious attacks on the servers and clients in the network. This requires that clients can determine that received messages are authentic; that is, were actually sent by the intended server and not manufactured or modified by an intruder.

NTP includes provisions to cryptographically authenticate individual servers using symmetric-key cryptography in which clients authenticate servers using shared secret keys. However, the secret keys must be distributed in advance using secure means beyond the scope of the protocol. This can be awkward and fragile with a large population of potential clients, possibly including hackers.

Modern public-key cryptography provides means to reliably bind the server identification credentials and related public values using public directory services. However, these means carry a high computing cost, especially when large numbers of time-critical clients are involved as often the case with NTP servers. In addition, there are problems unique to NTP in the interaction between the authentication and synchronization functions, since each requires the other for success.

The NTP Version 4 reference implementation includes a revised security model and authentication scheme supporting both symmetric and public-key cryptography. The public-key variant, called Autokey, is specially crafted to reduce the risk of intrusion, minimize the consumption of processor resources and minimize the vulnerability to hacker attack. Additional details can be found on the white paper NTP Security Analysis.

Computer Clock Modeling and Error Analysis

Most computers include a quartz resonator-stabilized oscillator and hardware counter that interrupts the processor at intervals of a few milliseconds. At each interrupt, a quantity called tick is added to a system variable representing the clock time. The clock can be read by system and application programs and set on occasion to an external reference.

Once set, the clock readings increment at a nominal rate, depending on the value of tick. Typical Unix system kernels provide a programmable mechanism to increase or decrease the value of tick by a small, fixed amount in order to amortize a given time adjustment smoothly over multiple tick intervals.

Clock errors are due to variations in network delay and latencies in computer hardware and software (jitter), as well as clock oscillator instability (wander). The time of a client relative to its server can be expressed

_T_(_t_) = _T_(_t_0) + _R_(_t - t_0) + 1/2 _D_(_t - t_0)2,

where t is the current time, T is the time offset at the last measurement update t₀, R is the frequency offset and D is the drift due to resonator ageing. All three terms include systematic offsets that can be corrected and random variations that cannot. Some protocols, including PTP and DTSS, estimate only the first term in this expression, while others, including NTP, estimate the first two terms. Errors due to the third term, while important to model resonator aging in precision applications, are neglected, since they are usually dominated by errors in the first two terms.

The synchronization protocol estimates T(t₀) (and R(t₀), where relevant) at regular update intervals τ and adjusts the clock to minimize T(t) in future. In common cases, R can have systematic offsets of several hundred parts-per-million (PPM) with random variations of several PPM due to ambient temperature changes. If not corrected, the resulting errors can accumulate to seconds per day.

In order that these errors do not exceed a nominal specification, the protocol must periodically re-estimate T and R and compensate for variations by adjusting the clock at regular intervals. As a practical matter, for nominal accuracies of tens of milliseconds, this requires clients to exchange messages with servers at intervals in the order of tens of minutes.

Analysis of quartz-resonator stabilized oscillators show that errors are a function of the averaging time, which in turn depends on the interval between corrections. At correction intervals less than a few hundred seconds, errors are dominated by jitter, while, at intervals greater than this, errors are dominated by wander. The characteristics of each regime determine the algorithm used to discipline the clock. These errors accumulate at each stratum level from the root to the leaves of the subnet tree.

It is possible to quantify these errors by statistical means, as in NTP. This allows real-time applications to adjust audio or video playout delay, for example. However, the required statistics may be different for various classes of applications. Some applications need absolute error bounds guaranteed never to exceede, as provided by the following correctness principles.

Correctness Principles

Applications requiring reliable time synchronization such as air traffic control must have confidence that the local clock is correct within some bound relative to a given timescale such as UTC. There is a considerable body of literature that studies these issues with respect to various failure models such as fail-stop and Byzantine disagreement. While these models inspire much confidence in a theoretical setting, most require multiple message rounds for each measurement and would be impractical in a large computer network such as the Internet.

However, it can be shown that the worst-case error in reading a remote server clock cannot exceed one-half the roundtrip delay measured by the client. This is a valuable insight, since it permits strong statements about the correctness of the timekeeping system.

In the Probabilistic Clock Synchronization (PCS) scheme devised by Cristian, a maximum error tolerance is established in advance and time value samples associated with roundtrip delays that exceed twice this value are discarded. By the above argument, the remaining samples must represent time values within the specified tolerance. As the tolerance is decreased, more samples fail the test until a point where no samples survive. The tolerance can be adjusted for the best compromise between the highest accuracy consistent with acceptable sample survival rate.

In a scheme devised by Marzullo and exploited in NTP and DTSS, the worst-case error determined for each server determines a correctness interval. If each of a number of servers are in fact synchronized to a common timescale, the actual time must be contained in the intersection of their correctness intervals. If some intervals do not intersect, then the clique containing the maximum number of intersections is assumed correct truechimers and the others assumed incorrect falsetickers. Only the truechimers are used to adjust the system clock.

System clock correctness principles require that clock readings must be always monotonic definite increasing, so that no two successive clock readings will be the same. As long as the reading latency exceeds the hardware resolution, this behavior is guaranteed. With reading latencies dropping below the microsecond in modern processors, the system clock in modern operating systems runs in nanoseconds, rather than the microseconds used in the original Unix kernel. With processor speeds exceeding 1 GHz, this assumption may be in jeopardy. Additional information on these topics is in the white paper Timestamp Capture Principles.

Data Grooming Algorithms

By its very nature, clock synchronization is a continuous process, resulting in a sequence of measurements with each of possibly several servers and resulting in a clock adjustment. In some protocols, crafted algorithms are used to improve the time and frequency estimates and refine the clock adjustment. Algorithms described in the literature are based on trimmed-mean and median filter methods.

The clock filter algorithm used in NTP is based on the observation that the correctness interval depends on the roundtrip delay. The algorithm accumulates offset/delay samples in a window of several samples and selects the offset sample associated with the minimum delay. In general, larger window sizes provide better estimates; however, stability considerations limit the window size to about eight.

The same principle could be used when selecting the best subset of servers and combining their offsets to determine the clock adjustment. However, different servers often show different systematic offsets, so the best statistic for the central tendency of the server population may not be obvious.

Various kinds of clustering algorithms have been found useful for this purpose. The one used in NTP sorts the offsets by a quality metric, then calculates the variance of all servers relative to each server separately. The algorithm repeatedly discards the outlier with the largest variance until further discards will not improve the residual variance or until a minimum number of servers remain. The final clock adjustment is computed as a weighted average of the survivors.

Clock Discipline Algorithm

Modern computer clocks use a hardware counter to generate processor interrupts at intervals in the order of a few milliseconds. At each interrupt the processor increments the software system clock by the number of microseconds or nanoseconds between interrupts, often called the tick and sometimes the jiffy.

Most modern processors implement some kind of high resolution hardware counter that can be used to interpolate between ticks. The hardware resolution of the system clock is defined as the time between increments of this counter. However, the actual reading latency due to the kernel interface and interpolation code can range from a few tens of microseconds in older processors to under a microsecond in modern processors.

At the heart of the synchronization protocol is the algorithm used to adjust the system clock in accordance with the final adjustment determined by the data grooming algorithms. This is called the clock discipline algorithm or simply the discipline. Such algorithms can be classed according to whether they minimize the time offset or frequency offset or both. For instance, the discipline used in DTSS minimizes only the time offset, while the one used in NTP minimizes both time and frequency offsets. While the DTSS algorithm cannot remove residual errors due to systematic frequency errors, the NTP algorithm is more complicated and less forgiving of design and implementation mistakes.

All clock disciplines function as a feedback loop, with measured offsets used to adjust the clock oscillator phase and frequency to match the external synchronization source. The behavior of feedback loops is well understood and modeled by mathematical analysis.

The significant design parameter is the time constant, or responsiveness to external or internal variations in time or frequency. Optimum selection of time constant depends on the interval between update messages. In general, the longer these intervals, the larger the time constant and vice versa. In practice and with typical network configurations the optimal poll intervals vary between one and twenty minutes for network paths to some thousands of minutes for modem paths.