algorithm
Click on the red underlined text to get to the source
... NTP), including
the architectures, algorithms and protocols to synchronize local
clocks in a set of distributed clients and servers. The protocol was
...
... clocks.
Section 4 describes algorithms useful for deglitching and smoothing
clock-offset samples collected on a continuous basis. These
algorithms ...
... algorithms useful for deglitching and smoothing
clock-offset samples collected on a continuous basis. These
algorithms began with those suggested in [22], were refined as the
results of experiments described in [23 ...
... with clients in the US and Europe, reliable algorithms for selecting
good clocks from a population possibly including broken ones have
been developed and are described in Section 4.
...
... presents experimental results using several different deglitching and
smoothing algorithms. Appendix E describes the prototype NTP primary
service net, as well as proposed rules of engagement for its use.
...
... design. One or more processes synchronize to an external reference
source, such as a radio clock or NTP daemon, and the routing
algorithm constructs a minimum-weight spanning tree rooted on these
processes. The clock offsets are then distributed along the arcs of
...
... hosts and send periodic
corrections to them. In this model the master is determined using an
election algorithm [25] designed to avoid situations where either no
...
... convergence
functions, those involving interactive convergence algorithms and
those involving interactive consistency algorithms ...
... algorithms and
those involving interactive consistency algorithms. Interactive
convergence algorithms ...
... algorithms. Interactive
convergence algorithms use statistical clustering techniques such as
the fault-tolerant average algorithm of [17 ...
... convergence algorithms use statistical clustering techniques such as
the fault-tolerant average algorithm of [17], the CNV algorithm of
...
... the fault-tolerant average algorithm of [17], the CNV algorithm of
[19], the majority-subset algorithm ...
... 19], the majority-subset algorithm of [22], the egocentric algorithm
of [27] and the algorithms ...
...
Interactive consistency algorithms are designed to detect faulty
clock processes which might indicate grossly inconsistent offsets in
successive readings or to different readers. These algorithms ...
... algorithms are designed to detect faulty
clock processes which might indicate grossly inconsistent offsets in
successive readings or to different readers. These algorithms use an
agreement protocol involving successive rounds of readings, possibly
...
... relayed and possibly augmented by digital signatures. Examples
include the fireworks algorithm of [17] and the optimum algorithm of
...
... include the fireworks algorithm of [17] and the optimum algorithm of
[30]. However, these algorithms ...
... algorithm of
[30]. However, these algorithms require large numbers of messages,
especially when large numbers of clocks are involved, and are
designed to detect faults that have rarely been found in the Internet ...
... view, the system of distributed NTP peers operates as a set of
coupled phase-locked oscillators, with the update algorithm
functioning as a phase detector and the logical clock as a voltage-
...
... 3]. The clock filter and
selection algorithms are designed so that the clock synchronization
subnet ...
... client/servers or peers arranged in a dynamically reconfigurable,
hierarchically distributed configuration. It also requires
sophisticated algorithms for association management, data
...
...
The update algorithm is initiated upon receipt of a message and at
other times. It processes the offset data from each peer and selects
the best peer using algorithms ...
... algorithm is initiated upon receipt of a message and at
other times. It processes the offset data from each peer and selects
the best peer using algorithms such as those described in Section 4.
This may involve many observations of a few clocks or a few
observations of many clocks, depending on the accuracies required.
...
... The local clock process operates upon the offset data produced by the
update algorithm and adjusts the phase and frequency of the logical
clock using mechanisms such as described in Section 5. This may
...
... should be organized to produce the highest accuracies, but must never
be allowed to form a loop. The clock filter and selection algorithms
used in NTP accomplish this by using a variant of the Bellman-Ford
...
... used in NTP accomplish this by using a variant of the Bellman-Ford
distributed routing algorithm [29] to compute the minimum-weight
spanning trees ...
... synchronization distance. If not,
the filter and selection algorithms will select the best of the
available servers and cast out outlyers as intended.
...
...
When the filter and selection algorithms suggested in Section 4 are
used, the following state variables are defined. There is one set of
...
...
This is the maximum dispersion assumed by the filter algorithms,
currently set to 65535 milliseconds.
...
...
When the filter and selection algorithms suggested in Section 4
are used, this is the size of the Clock Filter (peer.filter ...
...
When the filter and selection algorithms suggested in Section 4
are used, this is the threshold used to discard noisy data. While
...
...
When the filter algorithm suggested in Section 4 is used, this is
the filter weight used to discard noisy data. While a value of
...
... Select Weight (PEER.SELECT)
When the selection algorithm suggested in Section 4 is used, this
is the select weight used to discard outlyers. data. While a
value of 0.75 is suggested, the value may be changed to suit local
...
... peer.rec <- 0
Then the clock selection algorithm is called, which may result in a
new clock source (sys.peer). In other cases the protocol ceases
operation and the storage and timer ...
...
The c and d values are then input to the clock filter algorithm to
produce the delay estimate (peer.delay) and offset estimate
(peer.offset) for the peer involved. If d becomes nonpositive due to
...
... to the point that d becomes positive again. Specification of the
clock filter algorithm is not an integral part of the NTP
specification; however, one found to work well in the Internet
environment ...
... to confirm the clock is operating correctly. In this way the clock
filter and selection algorithms operate in the usual way and can be
used to mitigate the clock itself, should it appear to be operating
correctly, yet deliver bogus time.
...
... The update procedure is called when a new delay/offset estimate is
available. First, the clock selection algorithm determines the best
peer on the basis of estimated accuracy and reliability, which may
...
... peer.rec <- 0
and the clock selection algorithm is called again, which results in a
null clock source (sys.peer = 0). A new selection will occur when
the filters ...
... filters fill up again and the dispersion settles down.
Specification of the clock selection algorithm and logical clock
procedure is not an integral part of the NTP specification. A clock
...
... procedure is not an integral part of the NTP specification. A clock
selection algorithm found to work well in the Internet environment is
described in Section 4, while a logical clock procedure is described
...
... Internet environment is
described in Section 4, while a logical clock procedure is described
in Section 5. The clock selection algorithm described in Section 4
usually picks the server at the highest stratum and minimum delay
among all those available, unless that server appears to be a
...
... usually picks the server at the highest stratum and minimum delay
among all those available, unless that server appears to be a
falseticker. The result is that the algorithms all work to build a
minimum-weight spanning tree relative to the primary servers and thus
...
... Filtering Algorithms ...
... A very important factor affecting the accuracy and reliability of
time distribution is the complex of algorithms used to deglitch and
smooth the offset estimates and to cast out outlyers due to failure
of the primary reference sources or propagation media. The
...
... smooth the offset estimates and to cast out outlyers due to failure
of the primary reference sources or propagation media. The
algorithms suggested in this section were developed and refined over
several years of operation in the Internet under widely varying net
...
... several years of operation in the Internet under widely varying net
configurations and utilizations. While these algorithms are believed
the best available at the present time, they are not an integral part
of the NTP ...
... NTP specification.
There are two algorithms described in the following, the clock filter
algorithm ...
... algorithms described in the following, the clock filter
algorithm, which is used to select the best offset samples from a
given clock, and the clock selection algorithm, which is used to
...
... algorithm, which is used to select the best offset samples from a
given clock, and the clock selection algorithm, which is used to
select the best clock among a hierarchical set of clocks.
...
...
The clock filter algorithm is executed upon arrival of each NTP
message that results in new delay/offset sample pairs. New sample
...
... Clock Selection Algorithm ...
...
The clock selection algorithm uses the values of peer.delay,
peer.offset and peer.dispersion calculated by the clock filter
...
... peer.offset and peer.dispersion calculated by the clock filter
algorithm and is called when these values change or when the
reachability status changes. It constructs a list of candidate ...
... this host. This is analogous to the split-horizon rule used in
some variants of the Bellman-Ford routing algorithm.
4. The sum of the peer synchronizing distance (peer.distance) plus
...
... estimated precision of measurement. If no keywords are found, the
clock source variable (sys.peer) is set to zero and the algorithm
terminates.
...
... determined by peer 2. Similar outcomes occur in the case of four
peers. While these outcomes depend on judicious choice of w, the
behavior of the algorithm is substantially the same for values of w
between 0.5 and 1.0.
...
...
The above simulations assume the clock filter algorithm operates to
select the oldest sample in the shift register at each step; that
...
... to increase the polling interval above 64 seconds without significant
increase in loop error or degradation of transient response. Thus,
when a clock is selected according to the algorithms of Section 4,
the polling interval peer.hpoll is always set at NTP.MINPOLL.
...
... an estimate of error relative to the primary reference source and is
used by the filtering algorithms to improve the quality and
reliability of the offset estimates.
...
...
Estimates of error and drift rate are not essential for the correct
functioning of the clock algorithms, but do improve the accuracy and
adjustment with respect to net overheads. The estimated error allows
...
... an NTP message sent by that peer, since they can be used as weights
in such algorithms as described in [22], as well as to improve the
estimates during periods when offsets are not available. It is most
...
... T and the rate offsets are produced. In many reachability and
routing algorithms, such as GGP, EGP and local-net control
algorithms, peers exchange messages on the order of once or twice a
...
... routing algorithms, such as GGP, EGP and local-net control
algorithms, peers exchange messages on the order of once or twice a
minute. If NTP peers exchanged messages at a rate of one per minute
...
... Lundelius, J., and N. Lynch, "A New Fault-Tolerant Algorithm for Clock Synchronization:, Proc. Third Annual ACM Symposium on Principles of Distributed Computing, pgs. 75-88, August 1984. ...
... Mills, D., "Algorithms for Synchronizing Network Clocks", RFC- 956, M/A-COM Linkabit, September 1985. ...
... Gusella, R., and S. Zatti, "An Election Algorithm for a Distributed Clock Synchronization Program", Technical Report UCB/CSD 86/275, University of California, Berkeley, December 1985. ...
... Tripathi, S., and S. Chang, "ETempo: A Clock Synchronization Algorithm for Hierarchical LANs - Implementation and Measurements", Systems Research Center Technical Report TR-86-48, University of Maryland, 1986. ...
... 0 DCN Determined by DCN routing algorithm
1 WWVB WWVB radio clock (60 kHz)
1 GOES GOES satellite ...
... Appendix D. Evaluation of Filtering Algorithms ...
...
A number of algorithms for deglitching and filtering time-offset data
were described in RFC-956 ...
... 956. These fall in two classes: majority-
subset algorithms, which attempt to separate good subsets from bad by
comparing their means, and clustering algorithms, which attempt to
...
... subset algorithms, which attempt to separate good subsets from bad by
comparing their means, and clustering algorithms, which attempt to
improve the estimate by repeatedly casting out outlyers. The former
class ...
... 956 and after further development and
experimentation using typical Internet paths, a better algorithm was
found for casting out outlyers from a continuous stream of offset
...
... stream of offset
observations spaced at intervals in the order of minutes. The
algorithm is described as a variant of a median filter, in which a
window consisting of the last n sample offsets is continuously
...
... window consisting of the last n sample offsets is continuously
updated and the median sample selected as the estimate. However, in
the modified algorithm the outlyer (sample furthest from the median)
is then discarded and the entire process repeated until only a single
sample offset is left, which is then selected as the estimate.
...
... sample offset is left, which is then selected as the estimate.
The modified algorithm was found to be more resistant to glitches and
to provide a more accurate estimate than the unmodified one. It has
been implemented in the NTP ...
... years. However, recent experiments have shown there is an even
better one which provides comparable accuracy together with a much
lower computational burden. The key to the new algorithm became
evident through an examination of scatter diagrams plotting sample
offset versus roundtrip delay.
...
... one, which means the queues are often idle for relatively long
periods. In addition, the routing algorithm most often operates to
minimize the number of packet-switch hops and thus the number of
...
... almost half the measurements showed gross errors, which was due to
equipment failure at that site. These data were intentionally left
in the sample set to see how well the algorithms dealt with the
problem.
...
... Based on these data, the minimum filter was selected as the standard
algorithm. Since its performance did not seem to much improve for
values of n above eight, this value was chosen as the standard.
...