RFC 956
Algorithms for synchronizing network clocks
RFC 956: Algorithms for Synchronizing Network Clocks 🕰️💖
Okay bestie, let's start with the basics 🎀. This is RFC 956, titled Algorithms for Synchronizing Network Clocks. D.L. Mills wrote it in September 1985 while working at M/A-COM Linkabit, and it's part of the Network Working Group series. The header doesn't list a category, and there's no Obsoletes or Updates line on it, so it doesn't replace or change any earlier RFC. 🦋
Status of This Memo ✨
This RFC talks about clock synchronization algorithms for the ARPA-Internet community. It's basically asking people for discussion and suggestions on how to make things better 🫶. Distribution is unlimited, so anyone can read and share it 💅.
Table of Contents 🌸
1. Introduction
2. Majority-Subset Algorithms
3. Clustering Algorithms
4. Application to Time-Synchronization Data
5. Summary and Conclusions
6. References
Appendix
A. Experimental Determination of Internet Host Clock Accuracies
A1. UDP Time Protocol Experiment
A2. ICMP Timestamp Message Experiment
A3. Comparison of UDP and ICMP TimeList of Tables 🍓
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 Data
Table 4. Clustering Algorithm using ICMP Timestamp Data
Table 5. ISI-MCON-GW Majority-Subset Algorithm
Table 6. ISI-MCON-GW Clustering Algorithm
Table 7. LL-GW (a) Majority-Subset Algorithm
Table 8. LL-GW (a) Clustering Algorithm
Table 9. LL-GW (b) Majority-Subset Algorithm
Table 10. LL-GW (b) Clustering Algorithm
Table A1. UDP Host Clock Offsets for Various Internet Hosts
Table A2. UDP Offset Distribution < 9 sec
Table A3. UDP Offset Distribution < 270 sec
Table A4. ICMP Offset Distribution < 9 hours
Table A5. ICMP Offset Distribution < 270 sec
Table A6. ICMP Offset Distribution < 27 sec
Table A7. ICMP Offset Distribution < .9 sec
Table A8. Comparison of UDP and ICMP Host Clock Offsets1. Introduction 💫
Okay so the Internet crowd got really into figuring out accurate time from a bunch of clocks that don't fully trust each other 👀. Why? Because several times, reliable and super accurate clock servers started giving totally wrong answers after seasonal thunderstorms knocked out their main power supply ⛈️. Yikes 😭. Then you add malfunctioning hardware, buggy software, operator mistakes, and random errors in whatever mechanism sets or syncs clocks over Internet paths, and it's chaos 💀. Depending on the operating system, the damage can be anything from mild confusion to major disruption, especially when files or messages get the wrong timestamps or critical network transactions happen in the wrong order 🙈.
This report suggests a stochastic model built on maximum-likelihood estimation 🧠. It also gives algorithms for computing a good estimator from a bunch of time-offset samples measured between one or more clocks connected by network links 💜. The model gives a principled way to detect and fix errors caused by faulty clocks or super noisy links 🔥. The report also describes experiments with Internet hosts and ARPANET paths, which show how well the algorithms actually work ✨.
Several mechanisms in the Internet protocol suite record and transmit the time an event happens 🕒. These include the ICMP Timestamp message [6], Time Protocol [7], Daytime protocol [8], and IP Timestamp option [9]. A new Network Time Protocol [12] has been proposed too 🌈. You can find more info on network time synchronization in the References at the end. Synchronization protocols are described in [3] and [12], and synchronization algorithms are in [2], [5], and [10]. Experimental results on measured roundtrip delays and clock offsets in the Internet are discussed in [4] and [11]. For a full mathematical treatment of clock synchronization, check [1] 🤓.
In [10], the problem of synchronizing a set of clocks that don't trust each other is discussed, and algorithms are offered that maximize, in some sense, the expectation that a correct set of "good" clocks can be pulled out of a population that also includes "bad" ones 🎯. The technique is based on overlapping, discrete confidence intervals that are assigned a priori 🦋. The model makes the reasonable assumption that "bad" clocks show errors far outside these confidence intervals, so they can be easily spotted and kicked out of the voting process 🙅♀️.
As you can see from the data summarized in Appendix A, host clocks in a real network commonly show different amounts of dispersion, both relative to each other and to a standard-time reference like a radio clock 📻. The sources of dispersion include random errors from observation effects and from the synchronization mechanism itself (if one is used). They also include systematic errors from hardware or software failure, poor radio reception, and operator mistakes 🌸. In general, you can't accurately quantify whether a particular clock's dispersion makes it "good" or "bad," except on a statistical basis 🤷♀️. So from a practical standpoint, a statistical-estimation approach is preferred over a discrete-decision one 💅.
A basic assumption in this report is that most "good" clocks show errors clustered around zero offset from standard time, as determined for example by a radio clock 🎀. The remaining "bad" clocks show errors randomly spread across the observing interval 🌀. The problem is to pick the good clocks out from the bad ones and to estimate the correction to apply to the local clock so it displays the most accurate time ⏰. The algorithms in this report try to do this using maximum-likelihood techniques, which are, at this point, still theory 📚.
Now, the algorithms in [10] and in this report are basically filtering and smoothing algorithms, and they can produce errors, sometimes gross ones, if the sample distribution wanders far from a priori assumptions 😬. So a big design issue is robustness when the sample data sets are skewed 🍑. The approach in [10] uses theorem-proving to justify the robustness of the discrete algorithms it presents. The statistical models in this report aren't really suited for that 🙃. This report instead relies on detailed observation and experiments, with a summary included as an appendix 🔍. That gives an excellent qualitative foundation for judging robustness, but extra quantitative confidence should be built up using statistical mechanics 🧪. Bestie, that's the plan 💖.
2. Majority-Subset Algorithms 👑
Here's a stochastic model that fits a system of clocks that don't trust each other 💅. An experiment is made up of one or more measurements of time differences, or offsets, between several clocks in the network ⏱️. Usually, though not necessarily, one of those clocks is the observer's local clock, and observations are made against each of several other clocks in the network 👀. If some clocks are presumed more accurate, or trusted more, than others, you can express that by weighting their measurements accordingly ⚖️. The result is a set of statistics, including means and variances, which let the observer estimate the best time to set the local clock to 🎯.
A maximum-likelihood estimator is a statistic that maximizes the probability that a particular outcome of an experiment is due to a presumed set of assumptions about the experiment's constraints 🧠. For example, say you assume that at least k of n observations include only samples from a single distribution. Then a maximum-likelihood estimator for the mean of that distribution can be computed like this: find the variance for every k-sample subset of the n observations, pick the subset with the smallest variance, and use its mean as the estimator for the distribution mean 🌸.
For instance, let n be the number of clocks, and let k be the next largest integer in n/2, which is the minimum majority 🍓. A majority subset is a subset made up of k of the n offset measurements 💫. Each of these subsets is a selection of k out of n possibilities, so the total number of subsets is C(n,k) 🧮. The 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 20Obviously, the number of computations gets awkward once n goes past about 10 😵💫. Representative majority subsets for n = 3, 4, 5 are shown in Table 2 🦋.
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,5Let's say you choose n = 5. Then you have to calculate the mean and variance for ten subsets, indexed as shown in Table 2 🧁.
Next up is a maximum-likelihood algorithm that handles multiple samples and weights 🎀. It works like this: let n be the number of clocks, and let w(1), w(2), ..., w(n) be a set of integer weights, where w(i) is the weight for the ith clock 🏋️♀️. For the ith clock, there are three accumulators, W(i), X(i), and Y(i), and each one starts at zero 🫧. The ith clock gets polled some number of times. Each reply x makes n(i) get added to W(i), the weighted sample offset n(i)*x gets added to X(i), and its square (n(i)*x)2 gets added to Y(i) 💌. Polling keeps going for each of the n clocks in turn 🔁.
Then, using a majority-subset table like Table 2, you calculate the total weight W = sum(W(i)), plus the weighted sums X = sum(X(i)) and Y = sum(Y(i)*Y(i)), for each i in the jth majority subset (row) 🌈. From W, X, and Y, you compute the mean m(j) and variance s(j) ✨:
m(j) = X/W and s(j) = Y/W - m(j)*m(j) .Once that's done for all rows, select the row j with the smallest s(j), and return its associated mean m(j) as the maximum-likelihood estimate of the local-clock offset 💖. That's the whole thing, and it's giving main character energy 👑🫶.
3. Clustering Algorithms ✨
Okay bestie, another way to build a maximum-likelihood estimator is through clustering algorithms 🦋 These sort the points in a sample set into clusters based on their stochastic properties, and they're most useful when large numbers of samples are available 💅 One algorithm works on a sample set and selectively discards points that are presumed to be outside the cluster, like this:
- Start with a sample set of n observations
{x(1),x(2),...,x(n) - Compute the mean of the n observations in the sample set. Discard the single sample
x(i)with value furthest from the mean, leaving n-1 observations in the set. - Continue with step 2 until only a single observation is left, at which point declare its value the maximum-likelihood estimator.
This algorithm will usually (but not necessarily) converge to the desired result if the majority of observations come from "good" clocks 🌸 By hypothesis, those are clustered about zero offset relative to the reference clock, with the rest scattered randomly over the observation interval. It's giving clean, tidy vibes ✨
The following Table 3 summarizes the results of this algorithm applied to the UDP data shown in Appendix A 🎀 That data represents the measured clock offsets of 163 host clocks in the Internet system. It was assembled using the UDP Time protocol [7], where time is represented to a precision of one second. Each line of the table is the result of step 2 above, along with the size of the sample set and its (unweighted) mean and variance. The "Discard" column shows the value of the observation discarded at that step.
Size Mean Var Discard
-------------------------------
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 0Table 3. Clustering Algorithm using UDP Time Protocol Data
In Table 3 only a few of the 163 steps are shown 🧚 These include the ones near the beginning, which illustrate a rapid convergence as the relatively few outliers get discarded. The large outlier discarded in the first step is almost certainly due to equipment or operator failure 😭 The two outliers close to one hour discarded in the next two steps are probably simple operator mistakes, like entering summer time instead of standard time 🙈 By the time only 50 samples are left, the 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 error has shrunk to about a second and the variance has vanished for practical purposes. Literally iconic 👑
The following Table 4 summarizes the results of the clustering algorithm applied to the ICMP data shown in Appendix A 💜 That data represents the measured clock offsets of 504 host clocks in the Internet system. It was assembled using ICMP Timestamp messages [6], where time is represented to a precision of one millisecond. The columns in Table 4 should be interpreted in the same way as in Table 3, except that the data in Table 4 are in milliseconds, while the data in Table 3 are in seconds.
Size Mean Var Discard
-------------------------------
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 -8Table 4. Clustering Algorithm using ICMP Timestamp Data
As in Table 3 above, only some of the 504 steps are shown in Table 4. The distinguishing feature of the Table 4 data is that the raw data are much noisier 🌈 Only some 30 host clocks are closer than one second from the reference clock, while half were further than one minute away and over 100 were further than one hour away. The fact that the algorithm converged to within 8 msec of the reference time under these conditions should be considered fairly remarkable 🤯 That's especially true given the probability that many of the outliers discarded are almost certainly due to defective protocol implementations. Additional information on these experiments is presented in Appendix A.
4. Application to Time-Synchronization Data ✨
Okay so a variation of these algorithms can level up the offset estimates from a single clock 💅 by tossing out noise samples caused by occasional retransmissions in the network, for example. You grab a set of n independent samples by polling the clock. Then you use a majority-subset table to work out the m(j) and s(j) statistics and the maximum-likelihood estimate, same as above. For this, the majority-subset table could also include larger subsets. That way you can get the maximum-likelihood estimates from each of several clocks and feed them into the algorithm above 🫶
To test how well this works, the team ran experiments with two WIDEBAND/EISN gateways 🎀 that had WWVB radio clocks and were hooked up to the ARPANET. The goal was to find the limits of accuracy when comparing these clocks over ARPANET paths. One gateway (ISI-MCON-GW) sits at the Information Sciences Institute near Los Angeles, and the other (LL-GW) is at Lincoln Laboratories near Boston. Both gateways are PDP11/44 computers running the EPOS operating system, with clock-interface boards whose oscillators are phase-locked to the WWVB clock.
The clock readings from the gateways were compared with the DCNet WWVB reference clock using ICMP Timestamp messages, which record each timestamp with a precision of a millisecond. ngl, the path over the ARPANET between the gateways and the measurement host can cause occasional measurement errors as big as several seconds 😭. In principle you can shrink these errors with a big sample population, but the algorithms above get you higher accuracy with way fewer samples 🦋
They measured each gateway separately by sending an ICMP Timestamp Request message from the ARPANET address of DCN1 to the gateway's ARPANET address, then computing the round-trip delay and clock offset from the ICMP Timestamp Reply message. They kept this going for 1000 message exchanges, which took anywhere from seven minutes to several hours depending on the sample interval selected.
The tables below sum up the results of both the majority-subset and clustering algorithms applied to data from three experiments, one with ISI-MCON-GW and two with LL-GW. The ISI-MCON-GW and LL-GW (a) experiments were built to find accuracy limits using a continuous sequence of request/reply volleys, which gave over two samples per second. The remaining LL-GW (b) experiment looked at accuracy limits at a much slower rate of about one sample every ten seconds.
Each of the three experiments gets two tables, one for the majority-subset algorithm and one for the clustering algorithm. The two rows of the majority-subset tables show statistics from the raw data and from the filtered data processed by a C(5,3) majority-subset algorithm. In every case the extrema and variance are dramatically smaller for the filtered data than for the raw data, which lends credence to the conjecture that the mean statistic for the filtered data is probably a good maximum-likelihood estimator of the true offset 🔥
Mean Var Max Min
--------------------------------------------
Raw data 637 2.1E+7 32751 -1096
C(5,3) -15 389 53 -103
Table 5. ISI-MCON-GW Majority-Subset Algorithm
Size Mean Var Discard
-------------------------------
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 Algorithm
Mean Dev Max Min
--------------------------------------------
Raw data 566 1.8E+7 32750 -143
C(5,3) -23 81 14 -69
Table 7. LL-GW (a) Majority-Subset Algorithm
Size Mean Var Discard
-------------------------------
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 Algorithm
Mean Dev Max Min
--------------------------------------------
Raw data 378 2.1E+7 32760 -32758
C(5,3) -21 1681 329 -212
Table 9. LL-GW (b) Majority-Subset Algorithm
Size Mean Var Discard
-------------------------------
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 AlgorithmThe rows of the clustering tables show the result of selected steps as the algorithm discards samples furthest from the mean. The first twenty steps or so toss out samples with gross errors over 30 seconds 💀. These samples came from a defect in the timestamping procedure implemented in the WIDEBAND/EISN gateway code, which caused gross errors in about two percent of the ICMP Timestamp Reply messages. The samples were left in the raw data as received, so they could show how the algorithms would behave in such extreme cases. As the tables make clear, both the majority-subset and clustering algorithms effectively coped with the situation.
In the statement of the clustering algorithm, the terminating condition was specified as when only a single sample is left in the sample set. But it isn't necessary to go that far. For instance, from the design of the experiment and the reference clocks, accuracies better than about ten milliseconds are probably unrealistic. A rough idea of the accuracy of the mean is evident from the deviation, computed as the square root of the variance. So attempts to keep going once the variance drops below 100 or so are probably misguided 🙈. This occurs when between 500 and 900 samples remain in the sample set, depending on the particular experiment. Note that in any case between 300 and 700 samples fall within ten milliseconds of the final estimate, depending on experiment.
Comparing the majority-subset and clustering algorithms on the basis of variance reveals something interesting: the result of the C(5,3) majority-subset algorithm is equivalent to the clustering algorithm when between roughly 900 and 950 samples remain in the sample set. This, together with the moderately high variance in the 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 Conclusions ✨
okay so the principles of maximum-likelihood estimation are already super well known and widely used in communication electronics 💅 in this note we propose two algorithms that use these principles. one is based on majority-subset techniques, which is the move when you only have a small number of samples 🌸. the other is based on clustering techniques, which is the move when you have a large number of samples 🦋.
the algorithms were tested on raw data collected with Internet hosts and gateways over ARPANET paths 🛰️ the goal was setting a local host clock against a remote reference while keeping accuracy in the order of ten milliseconds ⏰ the results show these algorithms are honestly so effective at spotting and tossing out glitches caused by hardware or software failures or operator mistakes 🗑️✨ they also show that time synchronization can be maintained across the ARPANET in the order of ten milliseconds even with glitches many times the mean roundtrip delay. iconic behaviour, no notes 💖
the results point to the need for an improved time-synchronization protocol that combines the best features of the ICMP Timestamp message [6] and the UDP Time protocol [7] 🎀 these are the features the paper suggests for it:
- The protocol should be based on UDP, which provides the flexibility to handle simultaneous, multiplexed queries and responses.
- The message format should be based on the ICMP Timestamp message format, which provides the arrival and departure times at the server and allows the client to calculate the roundtrip delay and offset accurately.
- The data format should be based on the UDP Time format, which specifies 32-bit time in seconds since 1 January 1900, but extended additional bits for the fractional part of a second.
- Provisions to specify the expected accuracy should be included along with information about the reference clock or synchronizing mechanism, as well as the expected drift rate and the last time the clock was set or synchronized.
the next step should be formulating a protocol with the features above, then implementing and testing it in the Internet environment 🧪 future development should land on a distributed, symmetric protocol, maybe similar to the ones described in [1], for distributing highly reliable timekeeping information using a hierarchical set of trusted clocks 👑 that's the dream, bestie 🌙
6. References 📚
here are all the sources, bestie 🫶
- Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Comm. COM-28, 8 (August 1980), 1260-1266.
- Mills, D.L. Time Synchronization in DCNET Hosts. DARPA Internet Project Report IEN-173, COMSAT Laboratories, February 1981.
- Mills, D.L. DCNET Internet Clock Service. DARPA Network Working Group Report RFC-778, COMSAT Laboratories, April 1981.
- Mills, D.L. Internet Delay Experiments. DARPA Network Working Group Report RFC-889, M/A-COM Linkabit, December 1983.
- Mills, D.L. DCN Local-Network Protocols. DARPA Network Working Group Report RFC-891, M/A-COM Linkabit, December 1983.
- Postel, J. Internet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences Institute, September 1981.
- Postel, J. Time Protocol. DARPA Network Working Group Report RFC-868, USC Information Sciences Institute, May 1983.
- Postel, J. Daytime Protocol. DARPA Network Working Group Report RFC-867, USC Information Sciences Institute, May 1983.
- Su, Z. A Specification of the Internet Protocol (IP) Timestamp Option. DARPA Network Working Group Report RFC-781. SRI International, May 1981.
- Marzullo, K., and S. Owicki. Maintaining the Time in a Distributed System. ACM Operating Systems Review 19, 3 (July 1985), 44-54.
- Mills, D.L. Experiments in Network Clock Synchronization. DARPA Network Working Group Report RFC-957, M/A-COM Linkabit, September 1985.
- Mills, D.L. Network Time Protocol (NTP). DARPA Network Working Group Report RFC-958, M/A-COM Linkabit, September 1985.
Appendix A. Experimental Determination of Internet Host Clock Accuracies 🧚
following is a summary of three experiments built to reveal how accurate various Internet host clocks are ⏱️ the first uses the UDP Time protocol, which is only precise to one second, while the second uses the ICMP Timestamp message, which bumps the precision up to one millisecond 📈 the third experiment compares what UDP and ICMP report. in the UDP Time protocol, time is a 32-bit field counting seconds past 0000 UT on 1 January 1900 💫 in the ICMP Timestamp message, time is a 32-bit field counting milliseconds past 0000 UT of each day.
all the experiments here were run from the Internet host DCN6.ARPA, which is normally synchronized to a WWV radio clock 📻 to get better accuracy during the experiments, the DCN6.ARPA host was resynchronized to a WWVB radio clock. after several experiments with other hosts equipped with WWVB and WWV radio clocks and GOES satellite clocks, it's estimated that the maximum measurement error in the experiments below is less than about 30 msec relative to standard NBS time determined at the Boulder/Fort Collins transmitting sites 🎯 that's a very tight error bar, iykyk 🍓
A1. UDP Time Protocol Experiment 🌸
in the first experiment, four UDP Time protocol requests were sent at about three-second intervals to each of the 1775 hosts listed in the NIC Internet host table 📨 a total of 555 samples came back from 163 hosts and got compared with a local reference based on a WWVB radio clock, which is known to be accurate to within a few milliseconds ⚡ not all of these hosts were listed as supporting the UDP Time protocol in the NIC Internet host table 🙈 and some that were listed as supporting it either failed to respond or responded with various error messages 💀
in the following table, Host is the canonical name of the host and Count is the number of replies received. the remaining data represent the time offset, in seconds, needed to correct the local (reference) clock so it agrees with the host cited. the Max and Min values are the maximum and minimum of these offsets, while Mean is the mean value and Var is the variance, all rounded to the nearest second 📊✨
Host Count Max Min Mean Var
-----------------------------------------------------------
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
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
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
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 Hostsokay so this is the big table of real hosts and how far off their clocks were 🕰️✨ Table A1 is literally a snapshot of UDP Host Clock Offsets for a huge list of Internet hosts, and each row shows the count, max, min, mean and variance of the offsets. Some of these clocks are wildly off (SRI-UNICORN.ARPA is at -38486 💀) and some are basically perfect (lots of them sit at 0 🫶). Main character energy for the clocks that are dead-on 👑
The list here is basically the lineup of hosts that were on the network back then, and it's giving archive vibes 🦋
Okay, the important part is the bit right after the table, because it tells you which clocks are the most trustworthy 🔥. DCN1.ARPA (WWVB), DCN6.ARPA (WWV) and FORD1.ARPA (GOES) are all synchronized to radio clocks 📻, so under normal radio receiving conditions they should be accurate to well within a second relative to NBS standard time 🌈. Not me getting obsessed with how precise that is 😭🎀
Then there are some hosts that don't have their own radio, they borrow time from one of those reliable ones using the protocols in RFC-891 🧚. That's DCN5.ARPA, DCN7.ARPA and UMD1.ARPA (all synced to DCN1.ARPA 💜), plus UMICH1.ARPA (synced to FORD1.ARPA 🍓).
And the last bit is kind of a vibe check 🙈. It is highly likely, but not confirmed, that a bunch of the other hosts with really low offsets are also getting their local time from one of those hosts or from other radio clocks. Like, they probably are, we just can't prove it yet 💅 iykyk ✨
The raw numbers from the weighted data give a mean of -261 sec, a max of 3729 sec, and a min of -38486 sec. ✨ Bestie, if a clock got set off those alone it would be a gross error 💀.
A closer look at the distribution is seriously interesting 🔥. Table A2 is a histogram of the offsets within a few seconds of reference time. In this table and the ones that follow, "Offset" is in seconds and marks the lower-valued corner of a histogram bin, which runs up to the next higher value. "Count" is how many samples landed in that bin.
Offset Count Offset Count
------------- -------------
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 secOut of the 163 host clocks, 16 are accurate to within a second 🎀, while 125 are off by more than ten seconds 😭. It's considered highly likely that most of those 16 are synchronized directly or indirectly to a radio clock 📻. Table A3 shows the same data on a bigger scale 🦋.
Offset Count Offset Count
------------- -------------
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 sec138 of the 163 host clocks are within a minute, and four are off by more than 4.5 minutes 🙈. It's considered likely that most host clocks, except for the 16 we already flagged as probably tied to a radio clock, are set manually by an operator 🧚. Some hosts are way off. For example, SRI-UNICORN.ARPA is more than ten hours off 💀. Also notice the skew: most host clocks are set slow compared to standard time 🐢.
A2. ICMP Timestamp Messages Experiment ⏰
For the second experiment, four ICMP Timestamp messages were sent at roughly three-second intervals to each of the 1775 hosts and 110 gateways in the NIC Internet host table. That gave 1910 samples from 504 hosts and gateways, which were compared to a local reference built on a WWVB radio clock. That clock is accurate to within a few milliseconds 🫶. ICMP Timestamp support is optional in the DoD Internet protocol suite, so it's not surprising that most hosts and gateways don't support it 🥲. Plus, several widely distributed implementations of this feature have known bugs 🐛. The whole situation turned out to be a super useful robustness test for the clustering algorithm from the main body of this note 💅.
The full table of ICMP offsets by host is too big to include, so Tables A4 through A7 show the interesting parts of the distribution 🌈. The raw statistics from the weighted data give a mean of -2.8E+6 msec, a maximum of 8.6E+7 msec, and a minimum of -8.6E+7 msec. Setting a local clock from those alone would be ridiculous 💀. But when the clustering algorithm is used, the estimate improves to within 8 msec of the correct value ✨. That's an improvement of about six orders of magnitude, which is so remarkable that we need a closer look at the distributions 👑.
The reason the clustering algorithm did so well shows up when you look at the histograms in Tables A4 through A7, one after another 🔍. Table A4 uses an hours scale. It shows that 80 percent of the samples sit in a one-hour band on either side of zero offset 🍓. But, surprise, there's a big spread of samples outside that band, especially on the negative side 😳. It's almost certain that most or all of those outliers come from defective ICMP Timestamp implementations 🙅♀️. Also, invalid timestamps and those with the high-order bit set (which means unknown or nonstandard time) were already excluded from this data.
Offset Count Offset Count
------------- -------------
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 hoursTable A5 squeezes the distribution into a range of 4.5 minutes. About half of the 370 samples left after the outliers beyond 4.5 minutes are dropped sit in the band 30 seconds either side of zero offset, then they gradually taper off toward the edges of the table 🌸. This is the kind of distribution you'd expect when an operator sets host clocks by hand 🧑💻.
Offset Count Offset Count
------------- -------------
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 secTable A6 compresses the distribution into a range of 27 seconds 💖. About 29 percent of the 188 samples left after the outliers beyond 27 seconds are dropped sit in the band 3 seconds either side of zero offset. From there it tapers off gradually, though less dramatically 🦋. This pattern fits a transition region, where some clocks are set manually and others get set through some kind of protocol interaction with a reference clock 🤖. A fair number of the clocks showing offsets in the 3-27 second range were probably set with the UDP Time protocol at some point, but then drifted away because of local-oscillator drift ⏳.
Offset Count Offset Count
------------- -------------
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 secFinally, Table A7 squeezes everything into a range of 0.9 second 😭. Only 30 of the original 504 samples survived, and only 12 of those sit within a band 0.1 seconds either side of zero offset 🎯. That group includes the clocks that stay continuously synchronized to a radio clock, like the DCNet clocks, some FORDnet and UMDnet clocks, and a few others 📡.
Offset Count Offset Count
------------- -------------
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 secThe biggest takeaway from these histograms is the strong central tendency in every single one of them, even though the scale changes across six orders of magnitude 🌈. So a clustering algorithm that throws out outliers from the mean will reliably converge on a maximum-likelihood estimate close to the actual value 👑💜.
A3. Comparison of UDP and ICMP Time 🕰️
The third experiment was set up to check how accurate the different host implementations of the UDP Time protocol and ICMP Timestamp messages are 🧐. For every host that responded to UDP Time in the first experiment, a separate test ran both UDP and ICMP together, which keeps the effect of clock drift to a minimum 🫧. Out of the 162 hosts that responded to UDP requests, 45 also responded to ICMP requests with apparently correct time. The rest either sent back unknown or nonstandard ICMP time (29 hosts) or didn't respond to ICMP requests at all (88 hosts) 🙃.
Table A8 shows both the UDP time (in seconds) and the ICMP time (in milliseconds) returned by each of the 45 hosts that answered both UDP and ICMP requests 🍰. The data is sorted first by the indicated UDP offset, then by the indicated ICMP offset. The seven hosts at the top are continuously synchronized, directly or indirectly, to a radio clock, as we covered earlier in the first experiment ✨. It's probable, though not confirmed, that the hosts below them with discrepancies of a second or less are sometimes synchronized to one of those top hosts 🤝.
Host UDP time ICMP time
-------------------------------------------------
DCN6.ARPA 0 sec 0 msec
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
DEVVAX.TN.CORNELL.EDU 3657 3657026
PATCH.ARPA -86380 20411
IPTO-FAX.ARPA -86402 -1693
NETWOLF.ARPA 10651435 -62164450Table A8. Comparison of UDP and ICMP Host Clock Offsets
Okay so, we expected a gap of up to a second between UDP and ICMP time, because every implementation truncates and rounds a little differently 🫶. Most hosts totally vibe with that. But some gaps are way bigger, which might mean buggy implementations, long swapping delays, and so on 💀. Take UCI-CIP5.ARPA: its ICMP time sits almost 2.5 seconds behind its UDP time 😭.
Plot twist 🌸: OSLO-VAX.ARPA and DEVVAX.TN.CORNELL.EDU agree with each other within nominals, BUT both are a couple of minutes or so away from being exactly one hour early (3600 seconds) 🕐. That's giving "someone mixed up summer time and standard time" energy, probably an operator 🙈.
Okay this one is a total mess 💀. PATCH.ARPA, IPTO-FAX.ARPA and NETWOLF.ARPA are clearly broken. When the digging happened for PATCH.ARPA and IPTO-FAX.ARPA, it turned out they'd been set by hand one day late (-86400 seconds), by accident, but otherwise the time of day was close 🙈. Since the ICMP time rolls over at 2400 UT, their ICMP offset was within nominals. For NETWOLF.ARPA, nobody has an explanation for those super defective UDP and ICMP times 😭, though it was behaving within nominals at least in the first experiment 🫠🦋.
📦 where this page comes from
- ietf: rfc956 1985-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms