How NTP Reckons the Time (Computer Network Time Synchronization)

To understand how NTP works, it may be helpful to describe in general how it reckons the time. The NTP daemon implements several semiautonomous cooperating sequential processes. There is a peer process and poll process and related state variables, called an association, for each remote NTP server and local reference clock, such as a radio or satellite receiver or telephone modem. The poll process sends messages to the server at intervals varying from less than a minute to over a day. The actual intervals are determined on the basis of expected time quality and allowable network overhead, as described further in this topic. The peer process receives the reply and calculates the time offset and other values.

First, client A sends the current time T1 to server B. On arrival, B saves T1 along with the current time T2. Server B does not have to respond immediately since it might have other things to do or simply wants to pace the client and avoid runaway loops. Some time later, B sends the current time T3 along with the saved T1 and T2 to A. On arrival, A reads its clock T4 and proceeds to compute both time offset 8 and round-trip delay 5 of B relative to A:

tmp93_thumb


Note that while this method is described as a client/server exchange, it is symmetric and operates as well in a peer-peer exchange in which either peer can function as a server for the other as a client. Also note that the protocol provides a way to detect duplicate and bogus packets.

The time values from Equation 2.1 are processed by the clock filter algorithm, which selects the best from among the previous eight values.The job of the select algorithm is to find and discard falsetickers and pass the truechimers on to the cluster algorithm. The job of the cluster algorithm is to select from among the truechimers the most reliable and accurate time values on the basis of statistical principles. Assuming a sufficient number of truechimers are available, statistical outliers are discarded until only three candidates survive. The combine algorithm averages the survivor offsets weighted by a statistic called the root distance.


The result of the algorithms to this point is a single time value representing the best guess of the system clock offset with respect to the server population as a whole. This value is redetermined as each message arrives and results in a new offset update.The clock adjust process closes the feedback loop by amortizing the offsets between updates using incremental adjustments at 1-s intervals. The adjustments are implemented by the system clock, which operates as a variable-frequency oscillator (VFO). The VFO implements the system clock from which the timestamps are determined and closes the feedback loop.

The NTP subnet is a forest of multiple trees in which each client has a network path to each of a number of configured servers, and each of these servers has a network path to each of their configured servers, and so on. Each of these paths is associated with a metric computed from the number of server hops (strata) to the primary servers at the roots of the forest. The NTP algorithms operate as a distributed Bellman-Ford routing protocol to construct a shortest-path spanning tree among these paths. This results in minimum-distance paths from each primary server at the root via intervening secondary servers to every configured client at the leaves of the tree. The roots for secondary servers and clients in different regions of the subnet may have different primary servers, but the overall distance to each primary server will always be the minimum over all available paths. As a practical matter, this approach provides the most accurate, most reliable timekeeping in the subnet as a whole.

Next post:

Previous post: