How Does NTP Work? (2024)

The Network Time Protocol (NTP) is a system for synchronizing the clocksof hosts and clients across the Internet. NTP is a protocol intended tosynchronize all computers participating in the network to within a fewmilliseconds of Coordinated Universal Time (UTC). The core of the protocolis NTP’s clock discipline algorithm that adjusts the local computer’sclock time and tick frequency in response to an external source — such asanother trusted NTP server, a radio or satellite receiver, or a telephonemodem. A core problem in NTP is establishing the trust and accuracy ofnodes in the NTP network. This is done through a combination of selectionand filtering algorithms to choose from the most reliable and accuratepeer in the synchronization network.

An argument can be made that the Network Time Protocol (NTP) is thelongest running, continuously operating, distributed application on theInternet, with roots that can be traced back to 1979. The firstdocumentation of the protocol was made available in 1981 as InternetEngineering Note series 173IEN-173. Since then, it hasevolved into Network Time Protocol Version 4, documented in RFC5905 and ported to almostevery client and server platform available today. NTP is running onmillions of servers and clients across the world to keep accurate time ondevices throughout the Internet.

NTP Network Architecture

NTP uses a hierarchical network architecture that forms a tree structure.Each level of this hierarchy is called a stratum and is assigneda number starting with zero representing reference hardware clocks.A level one server is synchronized with a level zero server, and thisrelationship continues so that a server synchronized to a stratum $n $ server runs at stratum $n + 1$. The stratum number thereforerepresents the distance from an accurate reference clock. In general, thestratum of a node in the server is an indication of quality andreliability but this is not always the case; it is common to find stratumthree time sources that are higher quality than other stratum two timesources.

Wikipedia hasa good set of definitions for the different stratum that I’ve providedhere with slight modification:

Stratum 0: These are high-precision timekeeping devices such as atomicclocks, GPS or other radio clocks. They generate a very accurate timesignal that is directly connected to a connected computer. Stratum0 devices are also known as reference clocks. NTP servers cannot advertisethemselves as stratum 0.
Stratum 1: These are computers that are directly attached to stratum0 devices. Their system time is synchronized to within a few microsecondsof their attached devices. Stratum 1 servers may peer with other stratum1 servers for sanity check and backup. They are also referred to asprimary time servers.
Stratum 2: These are computers that are synchronized over a network tostratum 1 servers. Often a stratum 2 computer queries several stratum1 servers and selects the most accurate time representation from them.Stratum 2 computers may also peer with other stratum 2 computers toprovide more stable and robust time for all devices in the peer group.
Stratum 3: These are computers that are synchronized to stratum 2 servers. Theyemploy the same algorithms for peering and data sampling as stratum 2, andcan themselves act as servers for stratum 4 computers, and so on.

And this hierarchy continues up to stratum 15. The following figuredepicts the hierarchical nature of the NTP system. Reference clocks at thetop of the hierarchy are accurate time pieces and stratum 1 are computersdirectly attached to those time pieces. From there, increasing stratanumbers indicate where each computer synchronizes time data from.

Within the NTP network, clients poll one or more servers at an interval toretrieve updated timestamp information.

The Local Clock Model

To make the NTP system as accurate and reliable as possible requires firstan accurate and reliable local clock on host systems. For most purposes,the local clock is assumed to be a quartz crystal clock, which isa typical digital timepiece used in watches and computers. When a voltageis applied to the crystal it causes it to change shape; when the voltageis removed the crystal returns to its original shape (generating a smallamount of voltage in the process). This change and return of shape happensat a stable frequency that can be adjusted during the manufacturingprocess. Once set, the crystal can maintain the frequency over longperiods of time.

The local computer system uses the frequency that crystal oscillates at toincrement the logical clock of the computer. Since the crystal oscillatesat a pre-defined rate, the computer system can use this rate as a model oftime. Quartz is accurate enough that it can maintain time within a fewmilliseconds per day. Over time however, these imperfections of a fewmilliseconds per day can accumulate, making the clock inaccurate. EnterNTP. NTP adjusts these inaccuracies at periodic intervals usingcorrections that are received by more accurate time servers. For hostsrequiring the highest reliability, the computer is attached to a localhardware clock such as an atomic clock and receives time informationdirectly from that attached clock.

The Phase and Frequency Locked Loop (PLL/FLL)

A phase-locked loop or PLL is any control system that generates anoutput signal whose phase is related to the phase of an input signal. Thesimplest version of a PLL is an electronic circuit consisting ofa variable frequency oscillator and a phase detector that operate ina continuous feedback loop. The oscillator generates a periodic signal,and the phase detector compares the phase of that signal with the phase ofthe input periodic signal, adjusting the oscillator to keep the phasesmatched.

The following figure provides a more in-depth example.

In the figure, $x_i$ represents the reference timestamp froma reliable source and $c_i$ the local timestamp. Both timestamps areat the $i$th update. The difference between these timestamps $x_i - c_i$is the input offset, which is processed by the clock filter. Thefilter recorded the most recent offsets and selects one from the set asthe output offset to change the local clock with. The loop fliter is thenused to produce the correction required for the local clock oscillator. Ifa correction is required, the local clock is gradually skewed to thecorrect value so that the clock shows smooth time indications and so thattime values are monotonically increasing.

The Clock Synchronization Algorithm

During typical operation, an NTP client regularly polls one or more NTPservers to receive updated time data. Upon receipt of new data, the clientcomputes the time offset and round-trip delay from the server as in thefollowing figure.

The time offset $ \theta $, thedifference in absolute time between the two clocks, is definedmathematically by

$${\displaystyle \theta =\left\vert {\frac {(t_{2}-t_{1})+(t_{3}-t_{4})}{2}}\right\vert .}$$

More intuitively, the offset calculation is the absolute time differencebetween the two clocks time it takes for packets to transmit between theclient and the server.

Using the time data, we can also calculate the network delay $ \delta $:

$${\displaystyle \delta ={(t_{4}-t_{1})-(t_{3}-t_{2})} .}$$

where,

$t1$ is the client’s timestamp of the request packet transmission,
$t2$ is the server’s timestamp of the request packet reception,
$t3$ is the server’s timestamp of the response packet transmission and
$t4$ is the client’s timestamp of the response packet reception.

At the very heart of NTP are the algorithms used to improve the accuracyof the values for $ \theta $ and $ \delta $ using filtering andselection algorithms. The complexity of these algorithms varies dependingon the statistical properties of the path between peers and the accuraciesrequired. For example, if two nodes are on the same gigabit LAN, the pathdelays between messages sent between peers are usually within or below anyrequired clock accuracies. In a case like this, the raw offsets deliveredby the receive procedure can be used to directly adjust the local clock.In other cases, two nodes may be distributed widely over the Internet andthe delay might be much larger than acceptable.

Clock Filtering Algorithm

There are a number of algorithms for filtering time-offset data to removeglitches that fall into roughly two broad categories: majority-subsetalgorithms and clustering algorithms. Majority-subset algorithmsattempt to separate good subsets of data from bad subsets of data bycomparing statistics like mean and variance to select the best clock froma population of different clocks. Clustering algorithms work, on the otherhand, by removing outliers to improve the overall offset estimate fora clock given a series of observations.

The full implementation of NTP’s clock filtering algorithm is describedfairly succinctly in the presentation NTP Architecture, Protocol andAlgorithms.

Clock Selection Algorithm

Likely the single most important factor in maintaining high reliabilitywithin NTP is choosing a peer. Whenever an event comes in and new offsetestimates are calculated for a peer, the peer selection algorithm is usedto determine which peer should be selected as the clock source.

Within the NTP network, a key design assumption that helps with theselection algorithm is that accurate clocks are relatively numerous andcan be represented by random variables narrowly distributed close to UTC,while erroneous clocks are relatively rare and can be represented byrandom variables widely distributed throughout the measurement space.

The peer selection procedure thus begins by constructing a list ofcandidate peers by stratum. To be included on the candidate list the peermust pass certain sanity checks. For example, one check requires that the peer must notbe the host itself. Another check requires the peers must havereachability registers that are at least half full,which avoids using data from low quality associations or obviously brokenimplementations. If no candidates pass the sanity checks, the existingclock selection, if any, is cancelled and the local clock free-runs at itsintrinsic frequency.

The list is then pruned from the end to be no longer than a maximum size,currently set to five. Starting from the beginning, the list is truncatedat the first entry where the number of different strata in the listexceeds a maximum, currently set to two. This procedure is designed tofavor those peers near the head of the candidate list, which are at thelowest stratum and lowest delay and presumably can provide the mostaccurate time.

The full implementation of NTP’s selection algorithm is also given in thepresentation NTP Architecture, Protocol andAlgorithms.

Clock Combining Algorithm

The combine algorithm is the simplest of the bunch: it computes the finalclock offset by averaging the surviving clocks that havebeen filtered and selected to produce a final offset used for adjustingthe clock using the PLL/FLL clock control system.

NTP Message Formats

An NTP timestamp records the number of standard seconds relative to UTC.UTC started measuring time on 1 January 1972. The conceptual NTP clock wasset to 2,272,060,800.0 at this same point in time, which represents thenumber of standard seconds since 1 January 1972 (the start of UTC) and1 January 1900 (the conceptual start of NTP time).

An NTP timestamp is encoded as a 64-bit unsigned number, where the first32 bits encode the integer portion of the timestamp and the last 32 bitsencode the fractional portion. This format allows for convenientmultiple-precision arithmetic and easy conversion to other time formats asrequired. The 32 bits of precision of a timestamp provide about 232picoseconds of accuracy, which is likely more than enough precision forpractical applications over networked systems.

NTP hosts and clients exchange timestamp records by copying the currentvalue of the local clock to a timestamp variable in response to anincoming NTP message. An NTP host parses the incoming message, sets thetimestamp on the message, and returns it to the client.

 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |LI | VN |Mode | Stratum | Poll | Precision | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Root Delay | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Root Dispersion | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reference ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Reference Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Origin Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Receive Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Transmit Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | . . . Extension Field 1 (variable) . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | . . . Extension Field 2 (variable) . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Key Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | dgst (128) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Some of the keys fields are described here:

LI (Leap Indicator): Warns of an impending leap second to be inserted ordeleted at the end of the current day.
VN (Version Number): Identifies the present NTP version.
Mode, Stratum, Precision: Indicate the current operating mode, stratumand precision
Poll: Controls the interval between NTP messages sent by the host toa peer. The sending host always uses the minimum of its own pollinterval and the peer poll interval.
Root Delay/Dispersion: Indicate the estimated roundtrip delay andestimated dispersion, respective to the primary reference source.
Reference ID, Reference Timestamp: Identify the reference clock and thetime of its last update, intended primarily for management functions.
Origin Timestamp: The time when the last received NTP message wasoriginated, copied from its transmit timestamp field upon arrival.
Receive Timestamp: The local time when the latest NTP message wasreceived.
Transmit Timestamp: The local time when the latest NTP message wastransmitted.

The NTP state machine running on each host machine maintains statevariables for each of the above quantities as well as recording the IPaddress and ports of the host and its peers, a timer recording theinterval between transmitting NTP messages, a register recording if thepeer is reachable or not, as well as data measuring the current andestimated measured delay and offset associated with each single observation.

NTP also tracks the current clock source which identifies the clock thatis currently being used to track time and the local clock time derivedfrom the logical clock on the host machine.

In normal client-server operation, a server receives a message with thisformat from a peer, and the server populates the message with updatedtimestamp data before sending it back to the peer.

Each NTP host also sets a reachability shift register for each peer theycommunicate with. Each time a message is received the lowest order bit inthe register is set to one, and the remaining positions are shifted to theleft. The peer is considered reachable if the register is not zero, thatis, if the peer has sent at least one message in the last eight updateintervals. Peers who are unreachable may have their state informationcleared.

Recap

NTP is a system of clients and peers that communicate timestampinformation in a hierarchical format where nodes closer to the root of thehierarchy are, in general, considered more accurate keepers of time thannodes lower down in the hierarchy. Each NTP host responds to incomingmessages requesting time information and keeps an active peer associationfor each of the clients to track key information.

In response to receiving time information, an NTP peer runs a process thatincludes the selection, cluster, and combine algorithms that mitigateamong the various servers and reference clocks to determine the mostaccurate and reliable candidates to synchronize the with clock. Theselection algorithm uses Byzantine fault detection principles to discardthe presumably incorrect candidates called “falsetickers” from theincident population, leaving only good candidates called “truechimers”.A truechimer is a clock that maintains timekeeping accuracy toa previously published and trusted standard, while a falseticker isa clock that shows misleading or inconsistent time. The cluster algorithmuses statistical principles to find the most accurate set of truechimers.The combine algorithm computes the final clock offset by statisticallyaveraging the surviving truechimers.

Once an appropriate clock adjustment, the adjustment itself is processedby a phase-locked and frequency-locked loop.

Resources

This article provides an introduction to NTP, and should provideda good overview for someone wanting to learn more about the protocol. Ifyou want to learn more, there are several great resources to choose from: