A number of algorithms for deglitching and filtering time-offset data
were described in RFC-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
improve the estimate by repeatedly casting out outlyers. The former
class was suggested as a technique to select the best (i.e. the most
reliable) clocks from a population, while the latter class was
suggested as a technique to improve the offset estimate for a single
clock given a series of observations.
Following publication of RFC-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
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
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.
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 daemons developed for the Fuzzball and
Unix operating systems and been in regular operation for about two
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.
To see how a scatter diagram is constructed, it will be useful to
consider how offsets and delays are computed. Number the times of
sending and receiving NTP messages as shown in Figure D.1 and let i
be an even integer. Then the timestamps t(i-3), t(i-2) and t(i-1)
and t(i) are sufficient to calculate the offset and delay of each
peer relative to the other.
Peer 1 Peer 2
| |
t(1) |------------------->| t(2)
| |
t(4) |<-------------------| t(3)
| |
t(5) |------------------->| t(6)
| |
t(8) |<-------------------| t(7)
| |
...
Figure D.1. Calculating Delay and Offset
The roundtrip delay d and clock offset c of the receiving peer
relative to the sending peer are:
d = (t(i) - t(i-3)) - (t(i-1) - t(i-2))
c = [(t(i-2) - t(i-3)) + (t(i-1) - t(i))]/2 .
Two implicit assumptions in the above are that the delay distribution
is independent of direction and that the intrinsic drift rates of the
client and server clocks are small and close to the same value. If
this is the case the scatter diagram would show the samples
concentrated about a horizontal line extending from the point (d,c)
to the right. However, this is not generally the case. The typical
diagram shows the samples dispersed in a wedge with apex (d,c) and
opening to the right. The limits of the wedge are determined by
lines extending from (d,c) with slopes +0.5 and -0.5, which
correspond to the locus of points as the delay in one direction
increases while the delay in the other direction does not. In some
cases the points are concentrated along these two extrema lines, with
relatively few points remaining within the opening of the wedge,
which would correspond to increased delays on both directions.
Upon reflection, the reason for the particular dispersion shown in
the scatter diagram is obvious. Packet-switching nets are most often
operated with relatively small mean queue lengths in the order of
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
queues. Thus, not only is the probability that an arriving NTP
packet finds a busy queue in one direction reasonably low, but the
probability of it finding a busy queue in both directions is even
lower.
From the above discussion one would expect that, at low utilizations
and hop counts the points should be concentrated about the apex of
the wedge and begin to extend rightward along the extrema lines as
the utilizations and hop counts increase. As the utilizations and
hop counts continue to increase, the points should begin to fill in
the wedge as it expands even further rightward. This behavior is in
fact what is observed on typical Internet paths involving ARPANET,
NSFNET and other nets.
These observations cast doubt on the median-filter approach as a good
way to cast out offset outlyers and suggests another approach which
might be called a minimum filter. From the scatter diagrams it is
obvious that the best offset samples occur at the lower delays.
Therefore, an appropriate technique would be simply to select from
the n most recent samples the sample with lowest delay and use its
associated offset as the estimate. An experiment was designed to
test this technique using measurements between selected hosts
equipped with radio clocks, so that delays and offsets could be
determined independent of the measurement procedure itself.
The raw delays and offsets were measured by NTP from hosts at U
Maryland (UMD) and U Delaware (UDEL) via net paths to each other and
other hosts at Ford Research (FORD), Information Sciences Institute
(ISI) and National Center for Atmospheric Research (NCAR). For the
purposes here, all hosts can be assumed synchronized to within a few
milliseconds to NBS time, so that the delays and offsets reflect only
the net paths themselves.
The results of the measurements are given in Table D.1 (UMD) and
Table D.2 (UDEL), which show for each of the paths the error X for
which the distribution function P[x =< X] has the value shown. Note
that the values of the distribution function are shown by intervals
of decreasing size as the function increases, so that its behavior in
the interesting regime of low error probability can be more
accurately determined.
UMD FORD ISI NCAR UMD FORD ISI NCAR
Delay 1525 2174 1423 Offset 1525 2174 1423
--------------------------- ---------------------------
.1 493 688 176 .1 2 17 1
.2 494 748 179 .2 4 33 2
.3 495 815 187 .3 9 62 3
.4 495 931 205 .4 18 96 8
.5 497 1013 224 .5 183 127 13
.6 503 1098 243 .6 4.88E+8 151 20
.7 551 1259 265 .7 4.88E+8 195 26
.8 725 1658 293 .8 4.88E+8 347 35
.9 968 2523 335 .9 4.88E+8 775 53
.99 1409 6983 472 .99 4.88E+8 2785 114
.999 14800 11464 22731 .999 4.88E+8 5188 11279
1 18395 15892 25647 1 4.88E+8 6111 12733
Table D.1. Delay and Offset Measurements (UMD)
UDEL FORD UMD ISI NCAR
Delay 2986 3442 3215 2756
-----------------------------------
.1 650 222 411 476
.2 666 231 436 512
.3 692 242 471 554
.4 736 256 529 594
.5 787 272 618 648
.6 873 298 681 710
.7 1013 355 735 815
.8 1216 532 845 1011
.9 1836 1455 1019 1992
.99 4690 3920 1562 4334
.999 15371 6132 2387 11234
1 21984 8942 4483 21427
Table D.2.a Delay Measurements (UDEL)
UDEL FORD UMD ISI NCAR
Offset 2986 3442 3215 2756
-----------------------------------
.1 83 2 16 12
.2 96 5 27 24
.3 108 9 36 36
.4 133 13 48 51
.5 173 20 67 69
.6 254 30 93 93
.7 429 51 130 133
.8 1824 133 165 215
.9 4.88E+8 582 221 589
.99 4.88E+8 1757 539 1640
.999 4.88E+8 2945 929 5278
1 5.63E+8 4374 1263 10425
Table D.2.b Offset Measurements (UDEL)
The results suggest that accuracies less than a few seconds can
usually be achieved for all but one percent of the measurements, but
that accuracies degrade drastically when the remaining measurements
are included. Note that in the case of the UMD measurements to FORD
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.
The next two tables compare the results of minimum filters (Table
D.3) and median filters (Table D.4) for various n when presented with
the UMD - - NCAR raw sample data. The results show consistently
lower errors for the minimum filter when compared with the median
filter of nearest value of n. Perhaps the most dramatic result of
both filters is the greatly reduced error at the upper end of the
range. In fact, using either filter with n at least three results in
no errors greater than 100 milliseconds.
Filter Samples
1 2 4 8 16
P[x=<X] 1423 1422 1422 1420 1416
- --------------------------------------------
.1 1 1 1 0 0
.2 2 1 1 1 1
.3 3 2 1 1 1
.4 8 2 2 1 1
.5 13 5 2 2 1
.6 20 10 3 2 2
.7 26 15 6 2 2
.8 35 23 11 4 2
.9 53 33 20 9 3
.99 114 62 43 28 23
.999 11279 82 57 37 23
1 12733 108 59 37 23
Table D.3. Minimum Filter
(UMD - NCAR)
Filter Samples
3 7 15
P[x=<X] 1423 1423 1423
----------------------------
.1 2 2 2
.2 2 4 5
.3 5 8 8
.4 10 11 11
.5 13 14 14
.6 18 17 16
.7 23 21 19
.8 28 25 23
.9 36 30 27
.99 64 46 35
.999 82 53 44
1 82 60 44
Table D.4. Median Filter
(UMD - NCAR)
While the UMD - NCAR data above represented a path across the NSFNET
Backbone, which normally involves only a few hops via Ethernets and
56-Kbps links, the UDEL - NCAR path involves additional ARPANET hops,
which can contribute substantial additional delay dispersion. The
following Table D.5. shows the results of a minimum filter for
various n when presented with the UDEL - NCAR raw sample data. The
range of error is markedly greater than the UMD - NCAR path above,
especially near the upper end of the distribution function.
Filter Samples
1 2 4 8 16
P[x=<X] 2756 2755 2755 2753 2749
--------------------------------------------
.1 12 9 8 7 6
.2 24 19 16 14 14
.3 36 27 22 20 19
.4 51 36 29 25 23
.5 69 47 36 30 27
.6 93 61 44 35 32
.7 133 80 56 43 35
.8 215 112 75 53 43
.9 589 199 111 76 63
.99 1640 1002 604 729 315
.999 5278 1524 884 815 815
1 10425 5325 991 835 815
Table D.5. Minimum Filter (UDEL - NCAR)
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.
Network Time Protocol (Version 1): Specification and Implementation.
