Algorithms for synchronizing network clocks (RFC0956)
Original Publication Date: 1985-Sep-01
Included in the Prior Art Database: 2001-Jul-12
Internet Society Requests For Comment (RFCs)
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
Network Working Group D.L. Mills Request for Comments: 956 M/A-COM Linkabit
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
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 pr...