RFC relevance of algorithm

As per Relevance of the word algorithm, we have this rfc below:

Network Working Group D.L.
Request for Comments: 956 M/A-COM
September 1985

Algorithms for Synchronizing Network

Status of this

This RFC discussed clock synchronization algorithms for
ARPA-Internet community, and requests discussion and suggestions
improvements. Distribution of this memo is unlimited

Table of

1.
2. Majority-Subset
3. Clustering
4. Application to Time-Synchronization
5. Summary and
6.

A. Experimental Determination of Internet Host Clock
A1. UDP Time Protocol
A2. ICMP Timestamp Message
A3. Comparison of UDP and ICMP

List of

Table 1. C(n,k) for n from 2 to 20
Table 2. Majority Subsets for n = 3,4,5
Table 3. Clustering Algorithm using UDP Time Protocol
Table 4. Clustering Algorithm using ICMP Timestamp
Table 5. ISI-MCON-GW Majority-Subset
Table 6. ISI-MCON-GW Clustering
Table 7. LL-GW (a) Majority-Subset
Table 8. LL-GW (a) Clustering
Table 9. LL-GW (b) Majority-Subset
Table 10. LL-GW (b) Clustering
Table A1. UDP Host Clock Offsets for Various Internet
Table A2. UDP Offset Distribution < 9
Table A3. UDP Offset Distribution < 270
Table A4. ICMP Offset Distribution < 9
Table A5. ICMP Offset Distribution < 270
Table A6. ICMP Offset Distribution < 27
Table A7. ICMP Offset Distribution < .9
Table A8. Comparison of UDP and ICMP Host Clock

Mills [Page 1]

RFC 956 September 1985
Algorithms for Synchronizing Network

1.

The recent interest within the Internet community in
accurate time from a set of mutually suspicious network clocks
been prompted by several occasions in which gross errors were
in usually reliable, highly accurate clock servers after
thunderstorms which disrupted their primary power supply. To
sources of error should be added those due to
hardware, defective software and operator mistakes, as well as
errors in the mechanism used to set and/or synchronize the clocks
Internet paths. The results of these errors can range from
disorientation to major disruption, depending upon the
system, when files or messages are incorrectly timestamped or
order of critical network transactions is altered

This report suggests a stochastic model based on the principles
maximum-likelihood estimation, together with algorithms for
a good estimator from a number of time-offset samples
between one or more clocks connected via network links. The
provides a rational method for detecting and resolving errors due
faulty clocks or excessively noisy links. Included in this
are descriptions of certain experiments conducted with Internet
and ARPANET paths which give an indication of the effectiveness
the algorithms

Several mechanisms have been specified in the Internet protocol
to record and transmit the time at which an event takes place
including the ICMP Timestamp message [6], Time Protocol [7],
protocol [8] and IP Timestamp option [9]. A new Network
Protocol [12] has been proposed as well. Additional information
network time synchronization can be found in the References at
end of this document. Synchronization protocols are described in [3]
and [12] and synchronization algorithms in [2], [5] and [10].
Experimental results on measured roundtrip delays and clock
in the Internet are discussed in [4] and [11]. A
mathematical treatment of clock synchronization can be found in [1].

In [10] the problem of synchronizing a set of mutually
clocks is discussed and algorithms offered which maximize in
sense the expectation that a correct set of "good" clocks can
extracted from the population including also "bad" ones.
technique is based upon overlapping, discrete confidence
which are assigned a-priori. The model assumes the
presumption that "bad" clocks display errors far outside
confidence intervals, so can be easily identified and discarded
the voting process

Mills [Page 2]

RFC 956 September 1985
Algorithms for Synchronizing Network

As apparent from the data summarized in Appendix A, host clocks in
real network commonly indicate various degrees of dispersion
respect to each other and to a standard-time reference such as
radio clock. The sources of dispersion include random errors due
observational phenomena and the synchronization mechanism itself,
used, as well as systematic errors due to hardware or
failure, poor radio reception conditions or operator mistakes.
general, it is not possible to accurately quantify whether
dispersion of any particular clock qualifies the clock as "good"
"bad," except on a statistical basis. Thus, from a
standpoint, a statistical-estimation approach to the problem
preferred over a discrete-decision one

A basic assumption in this report is that the majority of "good
clocks display errors clustered around a zero offset relative
standard time, as determined for example from a radio clock,
the remaining "bad" clocks display errors distributed randomly
the observing interval. The problem is to select the good
from the bad and to estimate the correction to apply to the
clock in order to display the most accurate time. The
described in this report attempt to do this using maximum-
techniques, which are theory

It should be noted that the algorithms discussed in [10] and in
report are are basically filtering and smoothing algorithms and
result in errors, sometimes gross ones, if the sample
departs far from a-priori assumptions. Thus, a significant issue
the design of these algorithms is robustness in the face of
sample data sets. The approach in [10] uses theorem-proving
justify the robustness of the discrete algorithms presented
however, the statistical models in this report are not suited
that. The approach taken in this report is based on
observation and experiments, a summary of which is included as
appendix. While this gives an excellent qualitative foundation
which to judge robustness, additional quantitative confidence
be developed through the use of statistical mechanics

2. Majority-Subset

A stochastic model appropriate to a system of mutually
clocks can be constructed as follows. An experiment consists of
or more measurements of time differences or offsets between
clocks in the network. Usually, but not necessarily, one of
clocks is the local clock at the observer and observations
conducted with each of several other clocks in the network. The
that some clocks are presumed more accurate or trusted more
than others can be expressed by weighting the

Mills [Page 3]

RFC 956 September 1985
Algorithms for Synchronizing Network

accordingly. The result is a set of statistics, including means
variances, from which the observer is able to estimate the best
at which to set the local clock

A maximum-likelihood estimator is a statistic that maximizes
probability that a particular outcome of an experiment is due to
presumed set of assumptions on the constraints of the experiment
For example, if it is assumed that at least k of n
include only samples from a single distribution, then
maximum-likelihood estimator for the mean of that distribution
be computed as follows: Determine the variance for every k-
subset of the n observations. Then select the subset with
variance and use its mean as the estimator for the distribution mean

For instance, let n be the number of clocks and k be the next
integer in n/2, that is, the minimum majority. A majority subset
a subset consisting of k of the n offset measurements. Each of
subsets can be represented by a selection of k out of
possibilities, with the total number of subsets equal to C(n,k).
number of majority subsets is tallied for n from 2 to 20 in Table 1.

(n,k) C(n,k) (n,k) C(n,k
---------------------- ----------------------
(2,2) 1 (11,6) 462
(3,2) 3 (12,7) 792
(4,3) 4 (13,7) 1716
(5,3) 10 (14,8) 3003
(6,4) 15 (15,8) 6435
(7,4) 35 (16,9) 11440
(8,5) 56 (17,9) 24310
(9,5) 126 (18,10) 43758
(10,6) 210 (19,10) 92378
(20,11) 167960

Table 1. C(n,k) for n from 2 to 20

Obviously, the number of computations required becomes awkward as
increases beyond about 10. Representative majority subsets for n =
3,4,5 are shown in Table 2.

Mills [Page 4]

RFC 956 September 1985
Algorithms for Synchronizing Network

C(3,2) C(4,3) C(5,3)
------ ------ ------
1,2 1,2,3 1,2,3
1,3 1,2,4 1,2,4
2,3 1,3,4 1,2,5
2,3,4 1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

Table 2. Majority Subsets for n = 3,4,5

Choosing n = 5, for example, requires calculation of the mean
variance for ten subsets indexed as shown in Table 2.

A maximum-likelihood algorithm with provision for multiple
and weights might operate as follows: Let n be the number of
and w(1),w(2),...,w(n) a set of integer weights, with w(i) the
associated with the ith clock. For the ith clock three
W(i), X(i) and Y(i) are provided, each initialized to zero. The
clock is polled some number of times, with each reply x causing n(i
to be added to W(i), as well as the weighted sample offset n(i)*
added to X(i) and its square (n(i)*x)2 added to Y(i). Polling
continued for each of the n clocks in turn

Next, using a majority-subset table such as shown in Table 2,
calculate the total weight W = sum(W(i)) and weighted sums X =
sum(X(i)) and Y = sum(Y(i)*Y(i)) for each i in the jth
subset (row). From W, X and Y calculate the mean m(j) and
s(j):

m(j) = X/W and s(j) = Y/W - m(j)*m(j) .

When this is complete for all rows, select the row j with
smallest s(j) and return the associated mean m(j) as
maximum-likelihood estimate of the local-clock offset

Mills [Page 5]

RFC 956 September 1985
Algorithms for Synchronizing Network

3. Clustering

Another method for developing a maximum-likelihood estimator
through the use of clustering algorithms. These algorithms
to associate points in a sample set with clusters on the basis
stochastic properties and are most useful when large numbers
samples are available. One such algorithm operates on a sample
to selectively discard points presumed outside the cluster
follows

1. Start with a sample set of n observations {x(1),x(2),...,x(n

2. Compute the mean of the n observations in the sample set
Discard the single sample x(i) with value furthest from
mean, leaving n-1 observations in the set

3. Continue with step 2 until only a single observation is left
at which point declare its value the maximum-
estimator

This algorithm will usually (but not necessarily) converge to
desired result if the majority of observations are the result
"good" clocks, which by hypothesis are clustered about zero
relative to the reference clock, with the remainder
randomly over the observation interval

The following Table 3 summarizes the results of this
applied to the UDP data shown in Appendix A, which represents
measured clock offsets of 163 host clocks in the Internet system
These data were assembled using the UDP Time protocol [7], in
time is represented to a precision of one second. Each line of
table represents the result of step 2 above along with the size
the sample set and its (unweighted) mean and variance. The "Discard
column shows the value of the observation discarded at that step

Mills [Page 6]

RFC 956 September 1985
Algorithms for Synchronizing Network

Size Mean Var
-------------------------------
163 -210 9.1E+6 -38486
162 26 172289 3728
161 3 87727 3658
160 -20 4280 -566
150 -17 1272 88
100 -18 247 -44
50 -4 35 8
20 -1 0 -2
19 -1 0 -2
18 -1 0 -2
17 -1 0 1
16 -1 0 -1
15 -1 0 -1
14 -1 0 -1
13 0 0 0
1 0 0 0

Table 3. Clustering Algorithm using UDP Time Protocol

In Table 3 only a few of the 163 steps are shown, including
near the beginning which illustrate a rapid convergence as
relatively few outliers are discarded. The large outlier
in the first step is almost certainly due to equipment or
failure. The two outliers close to one hour discarded in the next
steps are probably simple operator mistakes like entering summer
instead of standard time. By the time only 50 samples are left,
error has shrunk to about 4 sec and the largest outlier is within 12
sec of the estimate. By the time only 20 samples are left, the
has shrunk to about a second and the variance has vanished
practical purposes

The following Table 4 summarizes the results of the
algorithm applied to the ICMP data shown in Appendix A,
represents the measured clock offsets of 504 host clocks in
Internet system. These data were assembled using ICMP
messages [6], in which time is represented to a precision of
millisecond. The columns in Table 4 should be interpreted in
same way as in Table 3, except that the data in Table 4 are
milliseconds, while the data in Table 3 are in seconds

Mills [Page 7]

RFC 956 September 1985
Algorithms for Synchronizing Network

Size Mean Var
-------------------------------
504 -3.0E+6 3.2E+14 8.6E+7
500 -3.3E+6 2.9E+14 8.6E+7
450 -1.6E+6 3.0E+13 -2.5E+7
400 29450 2.2E+11 3.6E+6
350 -3291 4.1E+9 -185934
300 3611 1.6E+9 -95445
250 2967 6.8E+8 66743
200 4047 2.3E+8 39288
150 1717 8.6E+7 21346
100 803 1.9E+7 10518
80 1123 8.4E+6 -4863
60 1119 3.1E+6 4677
50 502 1.5E+6 -2222
40 432 728856 2152
30 84 204651 -987
20 30 12810 338
15 28 2446 122
10 7 454 49
8 -2 196 24
6 -9 23 0
4 -10 5 -13
2 -8 0 -8

Table 4. Clustering Algorithm using ICMP Timestamp

As in Table 3 above, only some of the 504 steps are shown in Table 4.
The distinguishing feature of the data in Table 4 is that the
data are much more noisy - only some 30 host clocks are closer
one second from the reference clock, while half were further than
minute and over 100 further than one hour from it. The fact that
algorithm converged to within 8 msec of the reference time
these conditions should be considered fairly remarkable in view
the probability that many of the outliers discarded are
certainly due to defective protocol implementations.
information on these experiments is presented in Appendix A

Mills [Page 8]

RFC 956 September 1985
Algorithms for Synchronizing Network

4. Application to Time-Synchronization

A variation of the above algorithms can be used to improve the
estimates from a single clock by discarding noise samples produced
occasional retransmissions in the network, for example. A set of
independent samples is obtained by polling the clock. Then,
majority-subset table is used to compute the m(j) and s(j)
and the maximum-likelihood estimate determined as above. For
purpose the majority-subset table could include larger subsets
well. In this manner the maximum-likelihood estimates from each
several clocks can be determined and used in the algorithm above

In order to test the effectiveness of this algorithm, a set
experiments was performed using two WIDEBAND/EISN gateways
with WWVB radio clocks and connected to the ARPANET.
experiments were designed to determine the limits of accuracy
comparing these clocks via ARPANET paths. One of the
(ISI-MCON-GW) is located at the Information Sciences Institute
Los Angeles, while the other (LL-GW) is located at
Laboratories near Boston. Both gateways consist of PDP11/44
computers running the EPOS operating system and clock-
boards with oscillators phase-locked to the WWVB clock

The clock indications of the WIDEBAND/EISN gateways were
with the DCNet WWVB reference clock using ICMP Timestamp messages
which record the individual timestamps with a precision of
millisecond. However, the path over the ARPANET between
gateways and the measurement host can introduce
measurement errors as large as several seconds. In principle
effect of these errors can be minimized by using a large
population; however, use of the above algorithms allows
accuracies to be obtained with far fewer samples

Measurements were made separately with each of the two gateways
sending an ICMP Timestamp Request message from the ARPANET address
DCN1 to the ARPANET address of the gateway and computing
round-trip delay and clock offset from the ICMP Timestamp
message. This process was continued for 1000 message exchanges
which took from seven minutes to several hours, depending on
sample interval selected

The tables below summarize the results of both the majority-
and clustering algorithms applied to the data from three experiments
one with ISI-MCON-GW and two with LL-GW. The ISI-MCON-GW and LL-
(a) experiments were designed to determine the limits of
when using a continuous sequence of request/reply volleys,

Mills [Page 9]

RFC 956 September 1985
Algorithms for Synchronizing Network

resulted in over two samples per second. The remaining LL-GW (b
experiment was designed to determine the limits of accuracy using
much lower rate of about one sample every ten seconds

For each of the three experiments two tables are shown, one using
majority-subset algorithm and the other the clustering algorithm.
two rows of the majority-subset tables show the statistics
both from the raw data and from the filtered data processed by
C(5,3) majority-subset algorithm. In all cases the extrema
variance are dramatically less for the filtered data than the
data, lending credence to the conjecture that the mean statistic
the filtered data is probably a good maximum-likelihood estimator
the true offset

Mean Var Max
--------------------------------------------
Raw data 637 2.1E+7 32751 -1096
C(5,3) -15 389 53 -103

Table 5. ISI-MCON-GW Majority-Subset

Size Mean Var
-------------------------------
1000 637 2.1E+7 32751
990 313 1.0E+7 32732
981 15 1.0E+6 32649
980 -18 2713 -1096
970 -15 521 -122
960 -15 433 -97
940 -15 332 -75
900 -15 239 26
800 -15 141 12
700 -16 87 5
600 -17 54 -31
500 -16 33 -5
400 -18 18 -9
300 -19 7 -12
200 -19 2 -21
100 -18 0 -19
1 -17 0 -17

Table 6. ISI-MCON-GW Clustering

Mills [Page 10]

RFC 956 September 1985
Algorithms for Synchronizing Network

Mean Dev Max
--------------------------------------------
Raw data 566 1.8E+7 32750 -143
C(5,3) -23 81 14 -69

Table 7. LL-GW (a) Majority-Subset

Size Mean Var
-------------------------------
1000 566 1.8E+7 32750
990 242 8.5E+6 32726
983 10 1.0E+6 32722
982 -23 231 -143
980 -23 205 -109
970 -22 162 29
960 -23 128 13
940 -23 105 -51
900 -24 89 1
800 -25 49 -9
700 -26 31 -36
600 -26 21 -34
500 -27 14 -20
400 -29 7 -23
300 -30 3 -33
200 -29 1 -27
100 -29 0 -28
1 -29 0 -29

Table 8. LL-GW (a) Clustering

Mean Dev Max
--------------------------------------------
Raw data 378 2.1E+7 32760 -32758
C(5,3) -21 1681 329 -212

Table 9. LL-GW (b) Majority-Subset

Mills [Page 11]

RFC 956 September 1985
Algorithms for Synchronizing Network

Size Mean Var
-------------------------------
1000 377 2.1E+7 -32758
990 315 1.0E+7 32741
981 18 1.1E+6 32704
980 -16 16119 -1392
970 -17 5382 554
960 -21 3338 311
940 -24 2012 168
900 -22 1027 -137
800 -23 430 -72
700 -23 255 -55
600 -22 167 -45
500 -22 109 -40
400 -21 66 -6
300 -18 35 -29
200 -17 15 -23
100 -19 3 -15
50 -21 0 -19
20 -21 0 -21
10 -20 0 -20
1 -20 0 -20

Table 10. LL-GW (b) Clustering

The rows of the clustering tables show the result of selected
in the algorithm as it discards samples furthest from the mean.
first twenty steps or so discard samples with gross errors over 30
seconds. These samples turned out to be due to a defect in
timestamping procedure implemented in the WIDEBAND/EISN gateway
which caused gross errors in about two percent of the ICMP
Reply messages. These samples were left in the raw data as
in order to determine how the algorithms would behave in such
cases. As apparent from the tables, both the majority-subset
clustering algorithms effectively coped with the situation

In the statement of the clustering algorithm the
condition was specified as when only a single sample is left in
sample set. However, it is not necessary to proceed that far.
instance, it is known from the design of the experiment and
reference clocks that accuracies better than about ten
are probably unrealistic. A rough idea of the accuracy of the
is evident from the deviation, computed as the square root of
variance. Thus, attempts to continue the algorithm beyond the
where the variance drops below 100 or so are probably misguided
This occurs when between 500 and 900 samples remain in the

Mills [Page 12]

RFC 956 September 1985
Algorithms for Synchronizing Network

set, depending upon the particular experiment. Note that in any
between 300 and 700 samples fall within ten milliseconds of the
estimate, depending on experiment

Comparing the majority-subset and clustering algorithms on the
of variance reveals the interesting observation that the result
the C(5,3) majority-subset algorithm is equivalent to the
algorithm when between roughly 900 and 950 samples remain in
sample set. This together with the moderately high variance in
ISI-MCON-GW and LL-GW (b) cases suggests a C(6,4) or even C(7,4)
algorithm might yield greater accuracies

5. Summary and

The principles of maximum-likelihood estimation are well known
widely applied in communication electronics. In this note
algorithms using these principles are proposed, one based
majority-subset techniques appropriate for cases involving
numbers of samples and the other based on clustering
appropriate for cases involving large numbers of samples

The algorithms were tested on raw data collected with Internet
and gateways over ARPANET paths for the purpose of setting a
host clock with respect to a remote reference while
accuracies in the order of ten milliseconds. The results
the effectiveness of these algorithms in detecting and
glitches due to hardware or software failure or operator mistakes
They also demonstrate that time synchronization can be
across the ARPANET in the order of ten milliseconds in spite
glitches many times the mean roundtrip delay

The results point to the need for an improved time-
protocol combining the best features of the ICMP Timestamp
[6] and UDP Time protocol [7]. Among the features suggested for
protocol are the following

1. The protocol should be based on UDP, which provides
flexibility to handle simultaneous, multiplexed queries
responses

2. The message format should be based on the ICMP
message format, which provides the arrival and departure
at the server and allows the client to calculate the
delay and offset accurately

Mills [Page 13]

RFC 956 September 1985
Algorithms for Synchronizing Network

3. The data format should be based on the UDP Time format,
specifies 32-bit time in seconds since 1 January 1900,
extended additional bits for the fractional part of a second

4. Provisions to specify the expected accuracy should be
along with information about the reference clock
synchronizing mechanism, as well as the expected drift
and the last time the clock was set or synchronized

The next step should be formulating an appropriate protocol with
above features, together with implementation and test in the
environment. Future development should result in a distributed
symmetric protocol, similar perhaps to those described in [1],
distributing highly reliable timekeeping information using
hierarchical set of trusted clocks

6.

1. Lindsay, W.C., and A.V. Kantak. Network synchronization
random signals. IEEE Trans. Comm. COM-28, 8 (August 1980),
1260-1266.

2. Mills, D.L. Time Synchronization in DCNET Hosts. DARPA
Project Report IEN-173, COMSAT Laboratories, February 1981.

3. Mills, D.L. DCNET Internet Clock Service. DARPA Network
Group Report RFC-778, COMSAT Laboratories, April 1981.

4. Mills, D.L. Internet Delay Experiments. DARPA Network
Group Report RFC-889, M/A-COM Linkabit, December 1983.

5. Mills, D.L. DCN Local-Network Protocols. DARPA Network
Group Report RFC-891, M/A-COM Linkabit, December 1983.

6. Postel, J. Internet Control Message Protocol. DARPA
Working Group Report RFC-792, USC Information Sciences Institute
September 1981.

7. Postel, J. Time Protocol. DARPA Network Working Group
RFC-868, USC Information Sciences Institute, May 1983.

8. Postel, J. Daytime Protocol. DARPA Network Working Group
RFC-867, USC Information Sciences Institute, May 1983.

9. Su, Z. A Specification of the Internet Protocol (IP)
Option. DARPA Network Working Group Report RFC-781.
International, May 1981.

Mills [Page 14]

RFC 956 September 1985
Algorithms for Synchronizing Network

10. Marzullo, K., and S. Owicki. Maintaining the Time in
Distributed System. ACM Operating Systems Review 19, 3 (
1985), 44-54.

11. Mills, D.L. Experiments in Network Clock Synchronization.
Network Working Group Report RFC-957, M/A-COM Linkabit,
1985.

12. Mills, D.L. Network Time Protocol (NTP). DARPA Network
Group Report RFC-958, M/A-COM Linkabit, September 1985.

Appendix A

Experimental Determination of Internet Host Clock

Following is a summary of the results of three experiments
to reveal the accuracies of various Internet host clocks. The
experiment uses the UDP Time protocol, which is limited in
to one second, while the second uses the ICMP Timestamp message
which extends the precision to one millisecond. In the
experiment the results indicated by UDP and ICMP are compared.
the UDP Time protocol time is indicated as a 32-bit field in
past 0000 UT on 1 January 1900, while in the ICMP Timestamp
time is indicated as a 32-bit field in milliseconds past 0000 UT
each day

All experiments described herein were conducted from Internet
DCN6.ARPA, which is normally synchronized to a WWV radio clock.
order to improve accuracy during the experiments, the DCN6.ARPA
was resynchronized to a WWVB radio clock. As the result of
experiments with other hosts equipped with WWVB and WWV radio
and GOES satellite clocks, it is estimated that the
measurement error in the following experiments is less than about 30
msec relative to standard NBS time determined at the Boulder/
Collins transmitting sites

A1. UDP Time Protocol

In the first experiment four UDP Time protocol requests were
at about three-second intervals to each of the 1775 hosts
in the NIC Internet host table. A total of 555 samples
received from 163 hosts and compared with a local reference
on a WWVB radio clock, which is known to be accurate to within
few milliseconds. Not all of these hosts were listed
supporting the UDP Time protocol in the NIC Internet host table
while some that were listed as supporting this protocol
failed to respond or responded with various error messages

Mills [Page 15]

RFC 956 September 1985
Algorithms for Synchronizing Network

In the following table "Host" is the canonical name of the
and "Count" the number of replies received. The remaining
represent the time offset, in seconds, necessary to correct
local (reference) clock to agree with the host cited. The "Max
and "Min" represent the maximum and minimum of these offsets
while "Mean" represents the mean value and "Var" the variance,
rounded to the nearest second

Host Count Max Min Mean
-----------------------------------------------------------
BBN-CLXX.ARPA 4 -11 -12 -11 0
BBN-KIWI.ARPA 4 -11 -12 -11 0
BBN-META.ARPA 4 -11 -12 -11 0
BBNA.ARPA 1 22 22 22 0
BBNG.ARPA 4 87 87 87 0
BELLCORE-CS-GW.ARPA 3 72 71 71 0
BLAYS.PURDUE.EDU 2 -1 -1 -1 0
CMU-CC-TE.ARPA 4 -94 -95 -94 0
CMU-CS-C.ARPA 3 6 5 5 0
CMU-CS-CAD.ARPA 4 -37 -37 -37 0
CMU-CS-CFS.ARPA 3 -42 -43 -42 0
CMU-CS-G.ARPA 3 -30 -31 -30 0
CMU-CS-GANDALF.ARPA 3 -42 -43 -42 0
CMU-CS-H.ARPA 4 -36 -37 -36 0
CMU-CS-IUS.ARPA 3 -44 -45 -44 0
CMU-CS-IUS2.ARPA 3 -44 -44 -44 0
CMU-CS-K.ARPA 3 -31 -31 -31 0
CMU-CS-SAM.ARPA 4 -74 -75 -74 0
CMU-CS-SPEECH.ARPA 4 -39 -40 -39 0
CMU-CS-SPEECH2.ARPA 4 -49 -50 -49 0
CMU-CS-SPICE.ARPA 4 -131 -132 -131 0
CMU-CS-THEORY.ARPA 4 -36 -37 -36 0
CMU-CS-UNH.ARPA 4 -44 -45 -44 0
CMU-CS-VLSI.ARPA 4 -66 -66 -66 0
CMU-RI-ARM.ARPA 3 -41 -41 -41 0
CMU-RI-CIVE.ARPA 3 -44 -45 -44 0
CMU-RI-FAS.ARPA 4 -27 -28 -27 0
CMU-RI-ISL1.ARPA 4 -18 -19 -18 0
CMU-RI-ISL3.ARPA 3 -49 -50 -49 0
CMU-RI-LEG.ARPA 3 -33 -33 -33 0
CMU-RI-ML.ARPA 4 42 42 42 0
CMU-RI-ROVER.ARPA 4 -48 -49 -48 0
CMU-RI-SENSOR.ARPA 2 -40 -41 -40 0
CMU-RI-VI.ARPA 3 -65 -65 -65 0
COLUMBIA.ARPA 1 8 8 8 0
CU-ARPA.CS.CORNELL.EDU 4 5 3 4 0
CYPRESS.ARPA 4 2 1 1 0

Mills [Page 16]

RFC 956 September 1985
Algorithms for Synchronizing Network

DCN1.ARPA 4 0 0 0 0
DCN5.ARPA 4 0 0 0 0
DCN6.ARPA 4 0 0 0 0
DCN7.ARPA 4 -1 -1 0 0
DCN9.ARPA 4 -3 -3 -3 0
DEVVAX.TN.CORNELL.EDU 2 3659 3658 3658 0
ENEEVAX.ARPA 4 73 72 72 0
FORD-WDL1.ARPA 4 -59 -60 -59 0
FORD1.ARPA 4 0 0 0 0
GUENEVERE.PURDUE.EDU 3 1 0 0 0
GVAX.CS.CORNELL.EDU 4 -18 -18 -18 0
IM4U.ARPA 4 -6 -6 -6 0
IPTO-FAX.ARPA 4 0 0 0 0
KANKIN.ARPA 4 -3 -4 -3 0
MERLIN.PURDUE.EDU 2 3 3 3 0
MIT-ACHILLES.ARPA 4 16 16 16 0
MIT-AGAMEMNON.ARPA 4 -63 -64 -63 0
MIT-ANDROMACHE.ARPA 4 -28 -28 -28 0
MIT-APHRODITE.ARPA 4 -7 -8 -7 0
MIT-APOLLO.ARPA 4 -8 -9 -8 0
MIT-ARES.ARPA 4 -25 -26 -25 0
MIT-ARTEMIS.ARPA 4 -34 -35 -34 0
MIT-ATHENA.ARPA 4 -37 -37 -37 0
MIT-ATLAS.ARPA 4 -26 -26 -26 0
MIT-CASTOR.ARPA 4 -35 -35 -35 0
MIT-DAFFY-DUCK.ARPA 2 -72 -73 -72 0
MIT-DEMETER.ARPA 4 -28 -29 -28 0
MIT-GOLDILOCKS.ARPA 1 -20 -20 -20 0
MIT-HECTOR.ARPA 4 -23 -24 -23 0
MIT-HELEN.ARPA 4 6 5 5 0
MIT-HERA.ARPA 4 -34 -35 -34 0
MIT-HERACLES.ARPA 4 -36 -36 -36 0
MIT-JASON.ARPA 4 -36 -37 -36 0
MIT-MENELAUS.ARPA 4 -32 -33 -32 0
MIT-MULTICS.ARPA 3 25 23 24 0
MIT-ODYSSEUS.ARPA 4 20 19 19 0
MIT-ORPHEUS.ARPA 4 -34 -35 -34 0
MIT-PARIS.ARPA 4 -35 -35 -35 0
MIT-POSEIDON.ARPA 4 -39 -41 -40 0
MIT-PRIAM.ARPA 4 -24 -25 -24 0
MIT-REAGAN.ARPA 4 115 115 115 0
MIT-THESEUS.ARPA 4 -43 -44 -43 0
MIT-TRILLIAN.ARPA 4 -38 -39 -38 0
MIT-TWEETY-PIE.ARPA 3 106 105 105 0
MIT-ZERMATT.ARPA 4 -75 -76 -75 0
MIT-ZEUS.ARPA 4 -37 -39 -38 0
MOL.ARPA 2 -3 -3 -3 0

Mills [Page 17]

RFC 956 September 1985
Algorithms for Synchronizing Network

MUNGO.THINK.COM 4 -1 -1 -1 0
NETWOLF.ARPA 4 158 157 157 0
ORBIT.ARPA 3 -4 -5 -4 0
OSLO-VAX.ARPA 3 3729 3727 3728 1
PATCH.ARPA 1 18 18 18 0
RADC-MULTICS.ARPA 4 -14 -15 -14 0
RICE-ZETA.ARPA 1 -31 -31 -31 0
RICE.ARPA 1 7 7 7 0
ROCHESTER.ARPA 4 -18 -18 -18 0
ROCK.THINK.COM 4 2 2 2 0
SCRC-QUABBIN.ARPA 4 -100 -100 -100 0
SCRC-RIVERSIDE.ARPA 4 -128 -128 -128 0
SCRC-STONY-BROOK.ARPA 4 -100 -100 -100 0
SCRC-VALLECITO.ARPA 4 -57 -57 -57 0
SCRC-YUKON.ARPA 4 -65 -65 -65 0
SEBASTIAN.THINK.COM 4 -14 -15 -14 0
SEISMO.CSS.GOV 3 -1 -1 0 0
SRI-BISHOP.ARPA 4 -40 -41 -40 0
SRI-DARWIN.ARPA 2 -29 -30 -29 0
SRI-HUXLEY.ARPA 2 -28 -29 -28 0
SRI-KIOWA.ARPA 4 -29 -30 -29 0
SRI-LASSEN.ARPA 3 -11 -12 -11 0
SRI-MENDEL.ARPA 4 74 73 73 0
SRI-PINCUSHION.ARPA 4 -50 -51 -50 0
SRI-RITTER.ARPA 4 -23 -24 -23 0
SRI-TIOGA.ARPA 4 127 127 127 0
SRI-UNICORN.ARPA 4 -38486 -38486 -38486 0
SRI-WHITNEY.ARPA 4 -24 -24 -24 0
SRI-YOSEMITE.ARPA 4 -26 -27 -26 0
SU-AIMVAX.ARPA 2 -54 -55 -54 0
SU-COYOTE.ARPA 1 14 14 14 0
SU-CSLI.ARPA 4 -1 -1 -1 0
SU-PSYCH.ARPA 1 -52 -52 -52 0
SU-SAFE.ARPA 1 -60 -60 -60 0
SU-SIERRA.ARPA 4 -53 -53 -53 0
SU-SUSHI.ARPA 4 -105 -106 -105 0
SU-WHITNEY.ARPA 2 -14 -14 -14 0
TESLA.EE.CORNELL.EDU 3 -2 -3 -2 0
THORLAC.THINK.COM 4 -20 -20 -20 0
TRANTOR.ARPA 4 4 3 3 0
TZEC.ARPA 4 -6 -7 -6 0
UBALDO.THINK.COM 4 -13 -13 -13 0
UCI-CIP.ARPA 2 -566 -567 -566 0
UCI-CIP2.ARPA 2 -175 -175 -175 0
UCI-CIP3.ARPA 2 -89 -90 -89 0
UCI-CIP4.ARPA 2 -51 -51 -51 0
UCI-CIP5.ARPA 2 -26 -28 -27 1

Mills [Page 18]

RFC 956 September 1985
Algorithms for Synchronizing Network

UCI-ICSA.ARPA 2 -24 -24 -24 0
UCI-ICSC.ARPA 1 0 0 0 0
UCI-ICSD.ARPA 1 -24 -24 -24 0
UCI-ICSE.ARPA 1 -10 -10 -10 0
UDEL-DEWEY.ARPA 1 88 88 88 0
UDEL-MICRO.ARPA 2 64 64 64 0
UIUC.ARPA 4 105 103 104 0
UIUCDCSB.ARPA 4 65 65 65 0
UMD1.ARPA 4 0 0 0 0
UMICH1.ARPA 4 -1 -1 0 0
UO.ARPA 4 -2 -3 -2 0
USC-ISI.ARPA 4 -45 -45 -45 0
USC-ISIC.ARPA 4 28 26 27 0
USC-ISID.ARPA 4 26 25 25 0
USC-ISIE.ARPA 4 -53 -54 -53 0
USC-ISIF.ARPA 4 -29 -29 -29 0
USGS2-MULTICS.ARPA 3 75 74 74 0
UT-ALAMO.ARPA 4 22 22 22 0
UT-BARKLEY.ARPA 4 57 56 56 0
UT-EMIL.ARPA 4 29 28 28 0
UT-GOTTLOB.ARPA 4 42 41 41 0
UT-HASKELL.ARPA 4 6 6 6 0
UT-JACQUES.ARPA 4 21 20 20 0
UT-SALLY.ARPA 3 1 0 0 0
VALENTINE.THINK.COM 4 -10 -11 -10 0
WENCESLAS.THINK.COM 4 -2 -3 -2 0
XAVIER.THINK.COM 4 -14 -14 -14 0
XEROX.ARPA 4 0 0 0 0
YAXKIN.ARPA 3 -4 -5 -4 0
YON.THINK.COM 4 -11 -12 -11 0
ZAPHOD.PURDUE.EDU 4 -230 -231 -230 0
ZOTZ.ARPA 4 17 16 16 0

Table A1. UDP Host Clock Offsets for Various Internet

The above list includes several host clocks known to
synchronized to various radio clocks, including DCN1.ARPA (WWVB),
DCN6.ARPA (WWV) and FORD1.ARPA (GOES). Under normal
receiving conditions these hosts should be accurate to well
a second relative to NBS standard time. Certain other host
are synchronized to one of these hosts using protocols
in RFC-891, including DCN5.ARPA, DCN7.ARPA and UMD1.
(synchronized to DCN1.ARPA) and UMICH1.ARPA (synchronized
FORD1.ARPA). It is highly likely, but not confirmed, that
other hosts with low offsets derive local time from one of
hosts or from other radio clocks

Mills [Page 19]

RFC 956 September 1985
Algorithms for Synchronizing Network

The raw statistics computed from the weighted data indicate a
of -261 sec, together with a maximum of 3729 sec and a minimum
-38486 sec. Obviously, setting a local clock on the basis
these statistics alone would result in a gross error

A closer look at the distribution of the data reveals
interesting features. Table A2 is a histogram showing
distribution within a few seconds of reference time. In this
following tables, "Offset" is in seconds and indicates
lower-valued corner of the histogram bin, which extends to
next higher value, while "Count" indicates the number of
falling in that bin

Offset Count Offset
------------- -------------
0 sec 13 (continued)
1 1 -1 3
2 1 -2 3
3 2 -3 3
4 1 -4 2
5 2 -5 0
6 1 -6 2
7 1 -7 1
8 1 -8 1
9 0 -9 0
> 9 30 < -9 95

Table A2. Offset Distribution < 9

A total of 16 of the 163 host clocks are within a second
accuracy, while a total of 125 are off more than ten seconds.
is considered highly likely that most of the 16 host clocks
a second in offset are synchronized directly or indirectly to
radio clock. Table A3 is a histogram showing the distribution
a larger scale

Mills [Page 20]

RFC 956 September 1985
Algorithms for Synchronizing Network

Offset Count Offset
------------- -------------
0 sec 35 (continued)
30 3 -30 50
60 8 -60 42
90 3 -90 8
120 1 -120 4
150 1 -150 2
180 0 -180 1
210 0 -210 0
240 0 -240 1
270 0 -270 0
> 270 2 < -270 2

Table A3. Offset Distribution < 270

A total of 138 of the 163 host clocks are within a minute
accuracy, while a total of four host clocks are off more than 4.5
minutes. It is considered likely that most host clocks, with
exception of the 16 identified above as probably synchronized to
radio clock, are set manually by an operator. Inspection of
raw data shows some hosts to be very far off; for instance
SRI-UNICORN.ARPA is off more than ten hours. Note the
skew in the data, which show that most host clocks are set
relative to standard time

A2. ICMP Timestamp Messages

The the second experiment four ICMP Timestamp messages were
at about three-second intervals to each of the 1775 hosts and 110
gateways listed in the NIC Internet host table. A total of 1910
samples were received from 504 hosts and gateways and
with a local reference based on a WWVB radio clock, which is
to be accurate to within a few milliseconds. Support for the
Timestamp messages is optional in the DoD Internet protocol suite
so it is not surprising that most hosts and gateways do
support it. Moreover, bugs are known to exist in several
distributed implementations of this feature. The situation
an interesting and useful robustness test for the
algorithm described in the main body of this note

While the complete table of ICMP offsets by host is too large
reproduce here, the following Tables A4 through A7 show
interesting characteristics of the distribution. The
statistics computed from the weighted data indicate a mean
-2.8E+6 msec, together with a maximum of 8.6E+7 msec and a
of -8.6E+7 msec. Setting a local clock on the basis of

Mills [Page 21]

RFC 956 September 1985
Algorithms for Synchronizing Network

statistics alone would be ridiculous; however, as described in
main body of this note, use of the clustering algorithm
the estimate to within 8 msec of the correct value. The
improvement of about six orders in magnitude is so remarkable
to require a closer look at the distributions

The reasons for the remarkable success of the clustering
are apparent from closer examination of the sequence of
shown in Tables A4 through A7. Table A4 shows the distribution
the scale of hours, from which it is evident that 80 percent
the samples lie in a one-hour band either side of zero offset
but, strangely enough, there is a significant dispersion
samples outside of this band, especially in the negative region
It is almost certain that most or all of the latter
represent defective ICMP Timestamp implementations. Note
invalid timestamps and those with the high-order bit
(indicating unknown or nonstandard time) have already
excluded from these data

Offset Count Offset
------------- -------------
0 hr 204 (continued)
1 10 -1 194
2 0 -2 0
3 0 -3 2
4 0 -4 17
5 0 -5 10
6 0 -6 1
7 0 -7 22
8 0 -8 20
9 0 -9 0
> 9 0 < -9 13

Table A4. ICMP Offset Distribution < 9

Table A5 shows the distribution compressed to the range of 4.5
minutes. About half of the 370 samples remaining after
outliers beyond 4.5 minutes are excluded lie in the band 30
seconds either side of zero offset, with a gradual tapering off
the limits of the table. This type of distribution would
expected in the case of host clocks set manually by an operator

Mills [Page 22]

RFC 956 September 1985
Algorithms for Synchronizing Network

Offset Count Offset
------------- -------------
0 sec 111 (continued)
30 25 -30 80
60 26 -60 28
90 13 -90 18
120 7 -120 19
150 5 -150 9
180 3 -180 10
210 3 -210 6
240 1 -240 2
270 2 -270 2
> 270 29 < -270 105

Table A5. ICMP Offset Distribution < 270

Table A6 shows the distribution compressed to the range of 27
seconds. About 29 percent of the 188 samples remaining after
outliers beyond 27 seconds are excluded lie in the band 3
either side of zero offset, with a gradual but less
tapering off to the limits of the table. This type
distribution is consistent with a transition region in which
clocks are set manually and some by some kind of
interaction with a reference clock. A fair number of the
showing offsets in the 3-27 second range have probably been
using the UDP Time protocol at some time in the past, but
wandered away as the result of local-oscillator drifts

Offset Count Offset
------------- -------------
0 sec 32 (continued)
3 15 -3 22
6 9 -6 12
9 6 -9 8
12 13 -12 8
15 5 -15 5
18 8 -18 9
21 8 -21 7
24 9 -24 3
27 6 -27 3
> 27 114 < -27 202

Table A6. ICMP Offset Distribution < 27

Finally, Table A7 shows the distribution compressed to the
of 0.9 second. Only 30 of the original 504 samples have
and only 12 of these are within a band 0.1 seconds either side

Mills [Page 23]

RFC 956 September 1985
Algorithms for Synchronizing Network

zero offset. The latter include those clocks
synchronized to a radio clock, such as the DCNet clocks,
FORDnet and UMDnet clocks and certain others

Offset Count Offset
------------- -------------
0 sec 6 (continued)
.1 3 -.1 6
.2 1 -.2 3
.3 1 -.3 0
.4 0 -.4 0
.5 1 -.5 2
.6 0 -.6 0
.7 1 -.7 0
.8 4 -.8 2
.9 0 -.9 0
> .9 208 < -.9 266

Table A7. ICMP Offset Distribution < .9

The most important observation that can be made about the
histograms is the pronounced central tendency in all of them,
spite of the scale varying over six orders of magnitude. Thus,
clustering algorithm which operates to discard outliers from
mean will reliably converge on a maximum-likelihood estimate
to the actual value

A3. Comparison of UDP and ICMP

The third experiment was designed to assess the
produced by the various host implementations of the UDP
protocol and ICMP Timestamp messages. For each of the
responding to the UDP Time protocol in the first experiment
separate test was conducted using both UDP and ICMP in the
test, so as to minimize the effect of clock drift. Of the 162
hosts responding to UDP requests, 45 also responded to
requests with apparently correct time, but the remainder
responded with unknown or nonstandard ICMP time (29) or failed
respond to ICMP requests at all (88).

Table A8 shows both the UDP time (seconds) and ICMP
(milliseconds) returned by each of the 45 hosts responding to
UDP and ICMP requests. The data are ordered first by
UDP offset and then by indicated ICMP offset. The seven hosts
the top of the table are continuously synchronized, directly
indirectly to a radio clock, as described earlier under the

Mills [Page 24]

RFC 956 September 1985
Algorithms for Synchronizing Network

experiment. It is probable, but not confirmed, that those
below showing discrepancies of a second or less are
on occasion to one of these hosts

Host UDP time ICMP
-------------------------------------------------
DCN6.ARPA 0 sec 0
DCN7.ARPA 0 0
DCN1.ARPA 0 -6
DCN5.ARPA 0 -7
UMD1.ARPA 0 8
UMICH1.ARPA 0 -21
FORD1.ARPA 0 31
TESLA.EE.CORNELL.EDU 0 132
SEISMO.CSS.GOV 0 174
UT-SALLY.ARPA -1 -240
CU-ARPA.CS.CORNELL.EDU -1 -514
UCI-ICSE.ARPA -1 -1896
UCI-ICSC.ARPA 1 2000
DCN9.ARPA -7 -6610
TRANTOR.ARPA 10 10232
COLUMBIA.ARPA 11 12402
GVAX.CS.CORNELL.EDU -12 -11988
UCI-CIP5.ARPA -15 -17450
RADC-MULTICS.ARPA -16 -16600
SU-WHITNEY.ARPA 17 17480
UCI-ICSD.ARPA -20 -20045
SU-COYOTE.ARPA 21 21642
MIT-MULTICS.ARPA 27 28265
BBNA.ARPA -34 -34199
UCI-ICSA.ARPA -37 -36804
ROCHESTER.ARPA -42 -41542
SU-AIMVAX.ARPA -50 -49575
UCI-CIP4.ARPA -57 -57060
SU-SAFE.ARPA -59 -59212
SU-PSYCH.ARPA -59 -58421
UDEL-MICRO.ARPA 62 63214
UIUCDCSB.ARPA 63 63865
BELLCORE-CS-GW.ARPA 71 71402
USGS2-MULTICS.ARPA 76 77018
BBNG.ARPA 81 81439
UDEL-DEWEY.ARPA 89 89283
UCI-CIP3.ARPA -102 -102148
UIUC.ARPA 105 105843
UCI-CIP2.ARPA -185 -185250
UCI-CIP.ARPA -576 -576386
OSLO-VAX.ARPA 3738 3739395

Mills [Page 25]

RFC 956 September 1985
Algorithms for Synchronizing Network

DEVVAX.TN.CORNELL.EDU 3657 3657026
PATCH.ARPA -86380 20411
IPTO-FAX.ARPA -86402 -1693
NETWOLF.ARPA 10651435 -62164450

Table A8. Comparison of UDP and ICMP Host Clock

Allowing for various degrees of truncation and roundoff abuse
the various implementations, discrepancies of up to a second
be expected between UDP and ICMP time. While the results for
hosts confirm this, some discrepancies are far greater, which
indicate defective implementations, excessive swapping delays
so forth. For instance, the ICMP time indicated by UCI-CIP5.
is almost 2.5 seconds less than the UDP time

Even though the UDP and ICMP times indicated by OSLO-VAX.ARPA
DEVVAX.TN.CORNELL.EDU agree within nominals, the fact that
are within a couple of minutes or so of exactly one hour
(3600 seconds) lends weight to the conclusion they
incorrectly set, probably by an operator who confused local
and standard time

Something is clearly broken in the case of PATCH.ARPA
IPTO-FAX.ARPA and NETWOLF.ARPA. Investigation of the PATCH.
and IPTO-FAX.ARPA reveals that these hosts were set by
accidently one day late (-86400 seconds), but otherwise close
the correct time-of-day. Since the ICMP time rolls over at 2400
UT, the ICMP offset was within nominals. No explanation
available for the obviously defective UDP and ICMP times
by NETWOLF.ARPA, although it was operating within nominals
least in the first experiment

Mills [Page 26]

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX