RFC 956 (rfc956) - Page 2 of 26

Algorithms for synchronizing network clocks

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