from The Wizard of Oz, L. Frank Baum
Public transport in Oz
Last update 26-May-2012
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 finit additive groups using twos complement arithmetics. An important conclusion is that the correct time synchronization is assured if the NTP client is set reliably within 68 years when first started.
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.
In the remainder of this document, the decimal point in datestamps and timestamps formats is not significant and the numbers interpreted as 128-bit or 64-bit integers. Datestamps and timestamp are elements of additive groups consisting of integers and the operations of twos-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 2_n_ for some _n_. Addition is defined _A_ + _B_ = _B_ + _A_ mod 2_n_. The identity 0 is defined such that _A_ + 0 = 0 + _A_ = _A_ mod 2_n_. The complement (inverse) -_A_ is defined such that _A_ + (-_A_) = 0 mod 2_n_. To form the complement -_A_, first invert each bit of _A_, then add the constant 1 to the result. Equivalently, -_A_ = 2_n_ - _A_. Finally, the _offset_ of _B_ relative to _A_ is defined _A_ + (-_B_) mod 2_n_. This is the only allowable operation involving datestamp or timestamp operands and results in a signed data type.
For the additive group of 2_n_ 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 twos-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 2_n_, 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 2_n_-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.
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_ = [(_T_<sub>2</sub> - _T_<sub>1</sub>) + (_T_<sub>3</sub> - _T_<sub>4</sub>)] / 2
and roundtrip delay
_delay_ = (_T_<sub>4</sub> - _T_<sub>1</sub>) - (_T_<sub>3</sub> - _T_<sub>2</sub>).
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.
Was this page helpful?
Glad to hear it!
Sorry to hear that.