| blob | 82a2d7d4a75a47f10004b1d50355619979dbb8e9 |
1 = Clock Select Algorithm
2 include::include-html.ad[]
4 The clock select algorithm determines from a set of sources, which are
5 correct (_truechimers_) and which are not (_falsetickers_) according to
6 a set of formal correctness assertions. The principles are based on the
7 observation that the maximum error in determining the offset of a
8 candidate cannot exceed one-half the roundtrip delay to the primary
9 reference clock at the time of measurement. This must be increased by
10 the maximum error that can accumulate since then. The selection metric,
11 called the _root distance,_, is one-half the roundtrip root delay plus
12 the root dispersion plus minor error contributions not considered here.
14 First, a number of sanity checks is performed to sift the selectable
15 candidate from among the source population. The sanity checks are
16 summarized as follows:
18 1. A _stratum error_ occurs if (1) the source had never been
19 synchronized or (2) the stratum of the source is below the +floor+
20 option or not below the +ceiling+ option of the
21 link:miscopt.html#tos[+tos+] command. The default values for these
22 options are 0 and 15, respectively. Note that 15 is a valid stratum, but
23 a server operating at that stratum cannot synchronize clients.
24 2. A _distance error_ occurs for a source if the root distance (also
25 known as synchronization distance) of the source is not below the
26 distance threshold +maxdist+ option of the link:miscopt.html#tos[+tos+]
27 command. The default value for this option is 1.5 s for networks
28 including only the Earth, but this should be increased to 2.5 s for
29 networks including the Moon.
30 3. A _loop_ _error_ occurs if the source is synchronized to the client.
31 This can occur if two peers are configured with each other in symmetric
32 modes.
33 4. An _unreachable_ _error_ occurs if the source is unreachable or if
34 the +server+ or +peer+ command for the source includes the +noselect+
35 option.
37 Sources showing one or more of these errors are considered
38 nonselectable; only the selectable candidates are considered in the
39 following algorithm. Given the measured offset θ~0~ and root
40 distance λ, this defines a _correctness interval_ [θ~0~ −
41 λ, θ~0~ + λ] of points where the true value of
42 θ lies somewhere on the interval. The given problem is to
43 determine from a set of correctness intervals, which represent
44 truechimers and which represent falsetickers. The principles must be
45 given a precise definition. The _intersection interval_ is the
46 _smallest interval containing points from the largest number of
47 correctness intervals._ An algorithm that finds the intersection
48 interval was devised by Keith Marzullo in his doctoral
49 dissertation. It was first implemented in the Digital Time
50 Synchronization Service (DTSS) for the VMS operating system for the
51 VAX.
53 While the NTP algorithm is based on DTSS, it remains to establish which
54 point in the correctness interval represents the best estimate of the
55 offset for each candidate. The best point is at the midpoint θ~0~ of the
56 correctness interval; however, the midpoint might not be within the
57 intersection interval. A candidate with a correctness interval that
58 contains points in the intersection interval is a truechimer and the
59 best offset estimate is the midpoint of its correctness interval. A
60 candidate with a correctness interval that contains no points in the
61 intersection interval is a falseticker.
63 image:pic/flt3.gif[]
65 Figure 1. Intersection Interval
67 Figure 1 shows correctness intervals for each of four candidates A, B, C
68 and D. We need to find the maximum number of candidates that contain
69 points in common. The result is the interval labeled DTSS. In the figure
70 there are three truechimers A, B and C, and one falseticker D. In DTSS
71 any point in the intersection interval can represent the true time;
72 however, as shown below, this may throw away valuable statistical
73 information. In any case, the clock is considered correct if the number
74 of truechimers found in this way are greater than half the total number
75 of candidates.
77 The question remains, which is the best point to represent the true time
78 of each correctness interval? Fortunately, we already have the maximum
79 likelihood estimate at the midpoint of each correctness interval. But,
80 while the midpoint of candidate C is outside the intersection interval,
81 its correctness interval contains points in common with the intersection
82 interval, so the candidate is a truechimer and the midpoint is chosen to
83 represent its time.
85 The DTSS correctness assertions do not consider how best to represent
86 the truechimer time. To support the midpoint choice, consider the
87 selection algorithm as a method to reject correctness intervals that
88 cannot contribute to the final outcome; that is, they are falsetickers.
89 The remaining correctness intervals can contribute to the final outcome;
90 that is, they are truechimers. Samples in the intersection interval are
91 usually of very low probability and thus poor estimates for truechimer
92 time. On the other hand, the midpoint sample produced by the clock
93 filter algorithm is the maximum likelihood estimate and thus best
94 represents the truechimer time.
96 image:pic/flt6.gif[]
98 Figure 2. Clock Select Algorithm
100 The algorithm operates as shown in Figure 2. Let _m_ be the number of
101 candidates and _f_ the number of falsetickers, initially zero. Move a
102 pointer from the leftmost endpoint towards the rightmost endpoint in
103 Figure 1 and count the number of candidates, stopping when that number
104 reaches _m_ − _f_; this is the left endpoint of the intersection
105 interval. Then, do the same, but moving from the rightmost endpoint
106 towards the leftmost endpoint; this is the right endpoint of the
107 intersection interval. If the left endpoint is less than the right
108 endpoint, the intersection interval has been found. Otherwise, increase
109 _f_ by 1. If _f_ is less than _n_ / 2, try again; otherwise, the
110 algorithm fails and no truechimers could be found.
112 The clock select algorithm again scans the correctness intervals. If the
113 right endpoint of the correctness interval for a candidate is greater
114 than the left endpoint of the intersection interval, or if the left
115 endpoint of the correctness interval is less than the right endpoint of
116 the intersection interval, the candidate is a truechimer; otherwise, it
117 is a falseticker.
119 In practice, with fast LANs and modern computers, the correctness
120 interval can be quite small, especially when the candidates are multiple
121 reference clocks. In such cases the intersection interval might be
122 empty, due to insignificant differences in the reference clock offsets.
123 To avoid this, the size of the correctness interval is padded to the
124 value of +mindist+, with default 1 ms. This value can be changed using
125 the +mindist+ option of the link:miscopt.html#tos[+tos+] command.
127 '''''
129 include::includes/footer.adoc[]