NTP Timestamp Calculations
Last update: June 24, 2022 21:25 UTC (3a8d52d62)
from The Wizard of Oz, L. Frank Baum
Public transport in Oz
Table of Contents
Abstract
This document presents a mathematical analysis of the principles of clock offset and roundtrip delay calculations used by the Network Time Protocol (NTP). The analysis is based on the properties of finite additive groups using two’s complement arithmetic. An important conclusion is that the correct time synchronization is assured if the NTP client is set reliably within 68 years when first started.
1. Introduction
The timestamp calculations described in this document are used by the NTP protocol machine and clock discipline algorithms to adjust the time of the client clock to align with the time of the server clock. The calculations are not designed to set the client clock directly, only to provide an offset correction relative to the server clock and without respect to any arbitrary epoch.
The conclusion in this document is so important as to be previewed here.
If the client clock is set within 68 years of the server clock before the NTP protocol is started, the NTP algorithms will set the client clock to the server clock with accuracy and without ambiguity.
The discussion in this document is designed to support and confirm this statement before, at and beyond the timescale overflow event that will occur in 2036.
Time is an abstraction that establishes an ordering of events relative to a timescale. In NTP, a date is a point on the timescale expressed in one of two formats, datestamp and timestamp. As shown in Figure 1, a datestamp is a 128-bit, signed fixed-point number in seconds and fraction, with the decimal point to the left of bit 64. Dates are relative to the prime epoch, 0 h, 1 January 1900; dates prior to the prime epoch have negative values, while dates since then have positive values. A timestamp is a 64-bit, unsigned fixed-point number in seconds and fraction with the decimal point to the left of bit 32. Datestamps are used in internal calculations where extended range and freedom from overflow are important, while timestamps are used in packet headers where economy of storage is important.
Figure 1. NT Data Formats
Datestamps span the age of the Universe with a precision less than the time light transits an atom. Timestamps span a 136-year interval , called an era, with a precision of 232 ps. The datestamp format includes a timestamp field that specifies the seconds and fraction of an era, together with an era number field that specifies the timestamp origin. There is a special convention in both timestamp and datestamp formats where the value zero represents an undefined or unknown date that should not be used in time related calculations.
3. Datestamps and Timestamps as Finite Groups
In the remainder of this document, the decimal point in datestamps and timestamps formats is not significant and the numbers are interpreted as 128-bit or 64-bit integers. Datestamps and timestamps are elements of additive groups consisting of integers and the operations of two’s complement arithmetic. There are only two operations in the NTP additive group, addition and complement, each modulo 2128 for the datestamps group and 264 for the timestamp group, but otherwise the operations are the same. Datestamps are a signed data type, while timestamps are an unsigned data type.
Let A and B be elements of an additive group of integers modulo 2n for some n. Addition is defined A + B = B + A mod 2n. The identity 0 is defined such that A + 0 = 0 + A = A mod 2n. The complement (inverse) -A is defined such that A + (-A) = 0 mod 2n. To form the complement -A, first invert each bit of A, then add the constant 1 to the result. Equivalently, -A = 2n - A. Finally, the offset of B relative to A is defined A + (-B) mod 2n. This is the only allowable operation involving datestamp or timestamp operands and results in a signed data type.
4. Time Difference Calculations
For the additive group of 2n elements, the arithmetic logic unit (ALU) consists of a straight binary adder that does not distinguish the sign of the operands or result. However, in two’s complement notation, the sign is implicit in the most significant bit S. The ALU produces an n-bit result together with a carry bit C representing the n+1th bit. For timestamp calculations, the C bit is in effect the least significant bit of the era number of the datestamp, but most often it is implicit in the calculation of offset.
The mathematics involved in additive group calculations can be illustrated with the following examples. Let A and B be unsigned integers modulo 2n, where n = 4. The integers 0-7 with S = 0 are positive, while the integers 8-15 with S = 1 are negative. Let A = 7 and B = 5, then the offset A + (-B) = 7 + (-5) = 7 + 11 = 2 mod 16. Reversing the operands, let A = 5 and B = 7, then A + (-B) = 5 + (-7) = 5 + 9 = -2 mod 16. Note that, while the operands are unsigned type, the resulting offset is interpreted as signed type. This represents typical cases when the operands are in the same era. If, for example, A is in the next era later than B, let A = 2 and B =14. Then, A + (-B) = 2 + (-14) = 4 mod 16. Note that the modular operations can be performed before, during and after the calculation. Similar examples can be contrived for other values of n, A, and B, as long as the offset is less than 2n-1= 8 in these examples.
Returning to the interpretation of timestamps as fixed-point numbers, note that the integer portion represents an era of 136 years. This suggests the following general rule.
Let the system clock be set within 68 years of the correct time, even if the correct time is not known exactly. Then, the offset can be correctly computed by the on-wire protocol and used to adjust the system clock to the correct time relative to an external source.
As a practical example, consider an NTP client started somewhere in 2012. In principle, the system clock can be initially set any time between after 1944 in era 0 and before 2080 in era 1. However, since an era is 136 years, 1944 in era 0 corresponds to timestamp year 44, while 2080 in era 1 also corresponds to timestamp year 44. To avoid possible ambiguity, the time should be initially set within a more narrow range than 68 years, perhaps 50 years. In such cases, the NTP on-wire protocol and clock discipline will eventauly align the system clock to the correct time in 2012.
5. On-Wire Protocol Implications
Timestamp calculations are carefully constructed to avoid overflow while preserving precision. The only arithmetic operation permitted on raw timestamps is subtraction, which produces signed 64-bit timestamp differences from 68 years in the past to 68 years in the future.
All of the timestamp calculations discussed in this document involve differences between timestamps recorded at events such as the arrival or departure of an NTP packet. As described in previous sections of this document, the calculations apply whether or not the differences span none, one or more eras. The crucial distinction is whether the client clock is set within 68 years of the server clock before the protocol is started.
As in the protocol specification, let T1 be the client timestamp on the request packet, T2 the server timestamp upon arrival, T3 the server timestamp on departure of the reply packet and T4 the client timestamp upon arrival. The NTP on-wire protocol calculates the clock offset
offset = [(T2 - T1) + (T3 - T4)] / 2
and roundtrip delay
delay = (T4 - T1) - (T3 - T2)
In both the offset and delay equations, the calculations require raw timestamp differences that span no more than 68 years in the future to 68 years in the past. The previous discussion in this document confirms these differences can be computed correctly regardless of whether they span between two eras, as long as the eras are adjacent.
The offset and delay calculations require sums and differences of these raw timestamp differences that can span no more than from 34 years in the future to 34 years in the past without overflow. This is a fundamental limitation in 64-bit integer calculations.
In the NTPv4 reference implementation, all calculations involving offset and delay values use 64-bit floating double arithmetic, with the exception of raw timestamp subtraction, as mentioned above. The raw timestamp differences are then converted to 64-bit floating double format without loss of precision or chance of overflow in subsequent calculations.
While this design benefits present and future NTP versions, it will not of course benefit previous versions that may be etched in hardware or firmware. Previous versions of the public NTP software, including NTP Version 3 (xntpd) will have the same problem, but these versions use integer arithmetic throughout and are much harder to update.
NTP Version 3 has in addition well known ambiguities due to 16-bit overflows in some cases and is not recommended for new systems. However, it is important to note that Simple Network Time Protocol (SNTP) clients that set the clock directly and do not include the offset and delay calculations described in this document do not have the overflow problem and can continue to be used without hazard, at least until 2036.