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.
Appendix E. NTP Synchronization Networks
This section discusses net configuration issues for implementing a
ubiquitous NTP service in the Internet system. Section E.1 describes
the NTP primary service net now in operation, including an analysis
of failure scenarios. Section E.2 suggests how secondary service
nets, which obtain wholesale time from the primary service net, can
be configured to deliver accurate and reliable retail time to the
general host population.
E.1. Primary Service Network
The primary service net consists of five primary servers, each of
which is synchronized via radio or satellite to a national time
standard and thus operates at stratum one. Each server consists of
an LSI-11 Fuzzball, a WWVB or GOES radio clock and one or more net
interfaces. Some servers provide switching and gateway services as
well. Table E.1 shows the name, Internet address, type of clock,
operating institution and identifying code.
Name Address Clock Operating Institution and (Code)
----------------------------------------------------------------------
DCN5.ARPA 128.4.0.5 WWVB U Delaware, Newark, DE (UDEL)
FORD1.ARPA 128.5.0.1 GOES Ford Research, Dearborn, MI
(FORD)
NCAR.NSF.NET 128.116.64.3 WWVB National Center for Atmospheric
Research, Boulder, CO (NCAR)
UMD1.UMD.EDU 128.8.10.1 WWVB U Maryland, College Park, MD
(UMD)
WWVB.ISI.EDU 128.9.2.129 WWVB USC Information Sciences
Institute, Marina del Rey, CA
(ISI)
Table E.1. Primary Servers
Figure E.1 shows how the five primary servers are interconnected as
NTP peers. Note that each server actively probes two other servers
(along the direction of the arrows), which means these probes will
continue even if one or both of the two probed servers are down. On
the other hand, each server is probed by two other servers, so that
the result, assuming all servers are up, is that every server peers
with every other server.
+------------------------------------------------+
V |
+--------+ +--------+ +--------+
| |<-------------| |<-------------| |
| NCAR | | ISI | | FORD |
| |----+ +--| |<--+ +---->| |
+--------+ | | +--------+ | | +--------+
| | | | | A
| +---|------|---------------|----+ |
| | | | | |
| | +------|---------------|---------+ |
| | | | | |
| | | | V |
| +--------+ | | +--------+ |
| | |<--+ +--| | |
+-->| UMD | | UDEL |---+
| |--------------------->| |
+--------+ +--------+
Figure E.1. Primary Service Network
All of the five primary servers shown are directly connected to a
radio clock and thus normally operate at stratum one. However, if
the radio clock itself becomes disabled or the propagation path to
its synchronizing source fails, then the server drops to stratum two
and synchronizes via NTP with its neighbor at the smallest
synchronizing distance. If a radio clock appears to operate
correctly but delivers incorrect time (falseticker), the server may
remain synchronized to the clock. However, gross discrepancies will
become apparent via the NTP peer paths, which will ordinarily result
in an operator alarm.
Assume that, if a radio clock appears up, it is a truechimer;
otherwise, the clock appears down. Then the above configuration will
continue to provide correct time at all primary servers as long as at
least one radio clock is up, all servers are up and the servers
remain connected to each other through the net. The fact that the
graph and all of its subgraphs are completely connected lends an
incredible resilience to the configuration.
If some radio clocks appear up but are in fact falsetickers, the
primary servers connected to those clocks will not provide correct
time. However, as the consequents of the voting procedure and
complete connectivity of the graph and its subgraphs, any combination
of two falsetickers or of one falseticker and one down server will be
detected by their truechimer neighbors.
E.2. Secondary Service Networks
A secondary server operating at stratum n > 1 ordinarily obtains
synchronization using at least three peer paths, two with servers at
stratum n-1 and one or more with servers at stratum n. In the most
robust configurations a set of servers agree to provide backup
service for each other, so distribute some of their peer paths over
stratum-(n-1) servers and others over stratum-n servers in the same
set. For instance, in the case of a stratum-2 service net with two
secondary servers and the primary service net of Figure E.1, there
are five possible configurations where each stratum-1 path ends on a
different primary server. Such configurations can survive the loss
of three out of the four stratum-1 servers or net paths and will
reject a single falseticker on one of the two stratum-1 paths for
each server.
Ordinary hosts can obtain retail time from primary or secondary
service net using NTP in client/server mode, which does not require
dedicated server resources as does symmetric mode. It is anticipated
that ordinary hosts will be quite close to a secondary server,
perhaps on the same cable or local net, so that the frequency of NTP
request messages need only be high enough, perhaps one per hour or
two, to trim the drift from the local clock.