From wikistone
Jump to: navigation, search
(Created page with "From: http://www.eecis.udel.edu/~mills/ntp/html/select.html Clock Select Algorithm Last update: 13-Apr-2012 14:58 UTC The clock select algorithm determines from a set of so...")
 
Line 17: Line 17:
  
 
While the NTP algorithm is based on DTSS, it remains to establish which point in the correctness interval represents the best estimate of the offset for each candidate. The best point is at the midpoint θ0 of the correctness interval; however, the midpoint might not be within the intersection interval. A candidate with a correctness interval that contains points in the intersection interval is a truechimer and the best offset estimate is the midpoint of its correctness interval. A candidate with a correctness interval that contains no points in the intersection interval is a falseticker.
 
While the NTP algorithm is based on DTSS, it remains to establish which point in the correctness interval represents the best estimate of the offset for each candidate. The best point is at the midpoint θ0 of the correctness interval; however, the midpoint might not be within the intersection interval. A candidate with a correctness interval that contains points in the intersection interval is a truechimer and the best offset estimate is the midpoint of its correctness interval. A candidate with a correctness interval that contains no points in the intersection interval is a falseticker.
 +
 +
[[File:dtss_intersection_interval.gif|thumb|center|alt=DTSS algorithm|DTSS algorithm]]

Revision as of 15:44, 28 October 2013

From: http://www.eecis.udel.edu/~mills/ntp/html/select.html

Clock Select Algorithm

Last update: 13-Apr-2012 14:58 UTC

The clock select algorithm determines from a set of sources , which are correct (truechimers) and which are not (falsetickers) according to a set of formal correctness assertions. The principles are based on the observation that the maximum error in determining the offset of a candidate cannot exceed one-half the roundtrip delay to the primary reference clock at the time of measurement. This must be increased by the maximum error that can accumulate since then. The selection metric, called the root distance,, is one-half the roundtrip root delay plus the root dispersion plus minor error contributions not considered here.

First, a number of sanity checks is performed to sift the selectable candidate from among the source population. The sanity checks are sumarized as follows:.

  • A stratum error occurs if (1) the source had never been synchronized or (2) the stratum of the source is below the floor option or not below the ceiling option of the tos command. The default values for these options are 0 and 15, respectively. Note that 15 is a valid stratum, but a server operating at that stratum cannot synchronize clients.
  • A distance error occurs for a source if the root distance (also known ad synchronization distance) of the source is not below the distance threshold maxdist option of the tos command. The default value for this option is 1.5 s for networks including only the Earth, but this should be increased to 2.5 s for networks including the Moon.
  • A loop error occurs if the source is synchronized to the client. This can occur if two peers are configured with each other in symmetric modes.
  • An unreachable error occurs if the source is unreachable or if the server or peer command for the source includes the noselect option.

Sources showing one or more of these errors are considered nonselectable; only the selectable candidates are considered in the following algorithm. Given the measured offset θ0 and root distance λ, this defines a correctness interval [θ0 − λ, θ0 + λ] of points where the true value of θ lies somewhere on the interval. The given problem is to determine from a set of correctness intervals, which represent truechimers and which represent falsetickers. The principles must be given a precise definition. The intersection interval is the smallest interval containing points from the largest number of correctness intervals. An algorithm that finds the intersection interval was devised by Keith Marzullo in his doctoral dissertation. It was first implemented in the Digital Time Synchronization Service (DTSS) for the VMS operating system for the VAX.

While the NTP algorithm is based on DTSS, it remains to establish which point in the correctness interval represents the best estimate of the offset for each candidate. The best point is at the midpoint θ0 of the correctness interval; however, the midpoint might not be within the intersection interval. A candidate with a correctness interval that contains points in the intersection interval is a truechimer and the best offset estimate is the midpoint of its correctness interval. A candidate with a correctness interval that contains no points in the intersection interval is a falseticker.

DTSS algorithm
DTSS algorithm