begin clock-selection procedure
Each peer is examined in turn and added to an endpoint list only if it passes several sanity checks designed to avoid loops and use of
exceptionally noisy data. If no peers survive the sanity checks, the procedure exits without finding a synchronization source. For
each of m survivors three entries of the form [endpoint,type] are added to the endpoint list: [ THETA- LAMBDA ,-1], [ THETA ,0] and [
THETA + LAMBDA ,1]. There will be 3 m entries on the list, which is then sorted by increasing endpoint.
m <-- 0;
for (each peer) /* calling all peers */
if (peer.reach != 0 and peer.dispersion < NTP.MAXDISPERSE and
not (peer.stratum > 1 and peer.refid = peer.hostaddr)) begin
LAMBDA andistance (peer); /* make list entry */
add [THETA - LAMBDA ,-1] to endpoint list;
add [THETA ,0] to endpoint list;
add [THETA + LAMBDA ,1]> to endpoint list;
m <-- m+1;
endif
endfor
if (m = 0) begin /* skedaddle if no candidates */
sys.peer <-- NULL;
sys.stratum <-- 0 (undefined);
exit;
endif
sort endpoint list by increasing endpoint||type;
The following algorithm is adapted from DTS [DEC89] and is designed to produce the largest single intersection containing only
truechimers. The algorithm begins by initializing a value f and counters i and c to zero. Then, starting from the lowest endpoint of
the sorted endpoint list, for each entry [endpoint,type] the value of type is subtracted from the counter i, which is the number of
intersections. If type is zero, increment the value of c, which is the number of falsetickers (see Appendix
H). If i >= m- f for some entry, endpoint of that entry becomes the lower endpoint of the intersection; otherwise, f is
increased by one and the above procedure is repeated. Without resetting f or c, a similar procedure is used to find the upper
endpoint, except that the value of type is added to the counter.. If after both endpoints have been determined c <=f , the
procedure continues having found m - f truechimers; otherwise, f is increased by one and the entire procedure is repeated.
for (f from 0 to f >= m over 2) begin /* calling all truechimers */
c <-- 0;
i <-- 0;
for (each [endpoint, type] from lowest) begin /* find low endpoint */
i <-- i - type;
low <-- endpoint;
if (i >= m - f) break;
if (type = 0) c <-- c + 1 ;
endfor;
i <-- 0;
for (each [endpoint, type] from highest) begin /* find high endpoint */
i <-- i + type;
high <-- endpoint;
if ( i >= m - f ) break;
if ( type = 0) c <-- c + 1;
endfor;
if ( c <= f) break; /* continue until all falsetickers found */
endfor;
if ( low > high) begin /* quit if no intersection found */
sys.peer <- NULL;
exit;
endif;
Note that processing continues past this point only if there are more than m over 2 intersections. However, it is possible, but not
highly likely, that there may be fewer than m over 2 truechimers remaining in the intersection.
|
|