Algorithms for synchronizing network clocks
RFC 956

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions

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