Algorithms for synchronizing network clocks
RFC 956
|
Document |
Type |
|
RFC - Unknown
(September 1985; No errata)
|
|
Authors |
|
|
|
Last updated |
|
2013-03-02
|
|
Stream |
|
Legacy
|
|
Formats |
|
plain text
html
pdf
htmlized
bibtex
|
Stream |
Legacy state
|
|
(None)
|
|
Consensus Boilerplate |
|
Unknown
|
|
RFC Editor Note |
|
(None)
|
IESG |
IESG state |
|
RFC 956 (Unknown)
|
|
Telechat date |
|
|
|
Responsible AD |
|
(None)
|
|
Send notices to |
|
(None)
|
Network Working Group D.L. Mills
Request for Comments: 956 M/A-COM Linkabit
September 1985
Algorithms for Synchronizing Network Clocks
Status of this Memo
This RFC discussed clock synchronization algorithms for the
ARPA-Internet community, and requests discussion and suggestions for
improvements. Distribution of this memo is unlimited.
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 Time
List 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 Offsets
Mills [Page 1]
RFC 956 September 1985
Algorithms for Synchronizing Network Clocks
1. Introduction
The recent interest within the Internet community in determining
accurate time from a set of mutually suspicious network clocks has
been prompted by several occasions in which gross errors were found
in usually reliable, highly accurate clock servers after seasonal
thunderstorms which disrupted their primary power supply. To these
sources of error should be added those due to malfunctioning
hardware, defective software and operator mistakes, as well as random
errors in the mechanism used to set and/or synchronize the clocks via
Internet paths. The results of these errors can range from simple
disorientation to major disruption, depending upon the operating
system, when files or messages are incorrectly timestamped or the
order of critical network transactions is altered.
This report suggests a stochastic model based on the principles of
maximum-likelihood estimation, together with algorithms for computing
a good estimator from a number of time-offset samples measured
between one or more clocks connected via network links. The model
provides a rational method for detecting and resolving errors due to
faulty clocks or excessively noisy links. Included in this report
are descriptions of certain experiments conducted with Internet hosts
and ARPANET paths which give an indication of the effectiveness of
the algorithms.
Several mechanisms have been specified in the Internet protocol suite
to record and transmit the time at which an event takes place,
including 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 as well. Additional information on
network time synchronization can be found in the References at the
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 offsets
in the Internet are discussed in [4] and [11]. A comprehensive
mathematical treatment of clock synchronization can be found in [1].
In [10] the problem of synchronizing a set of mutually suspicious
clocks is discussed and algorithms offered which maximize in some
sense the expectation that a correct set of "good" clocks can be
extracted from the population including also "bad" ones. The
technique is based upon overlapping, discrete confidence intervals
which are assigned a-priori. The model assumes the reasonable
presumption that "bad" clocks display errors far outside these
confidence intervals, so can be easily identified and discarded from
the voting process.
Mills [Page 2]
RFC 956 September 1985
Algorithms for Synchronizing Network Clocks
As apparent from the data summarized in Appendix A, host clocks in a
Show full document text