rfc956.txt

RFC 相关的技术文档

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
   real network commonly indicate various degrees of dispersion with
   respect to each other and to a standard-time reference such as a
   radio clock.  The sources of dispersion include random errors due to
   observational phenomena and the synchronization mechanism itself, if
   used, as well as systematic errors due to hardware or software
   failure, poor radio reception conditions or operator mistakes.  In
   general, it is not possible to accurately quantify whether the
   dispersion of any particular clock qualifies the clock as "good" or
   "bad," except on a statistical basis.  Thus, from a practical
   standpoint, a statistical-estimation approach to the problem is
   preferred over a discrete-decision one.

   A basic assumption in this report is that the majority of "good"
   clocks display errors clustered around a zero offset relative to
   standard time, as determined for example from a radio clock, while
   the remaining "bad" clocks display errors distributed randomly over
   the observing interval.  The problem is to select the good clocks
   from the bad and to estimate the correction to apply to the local
   clock in order to display the most accurate time.  The algorithms
   described in this report attempt to do this using maximum-likelihood
   techniques, which are theory.

   It should be noted that the algorithms discussed in [10] and in this
   report are are basically filtering and smoothing algorithms and can
   result in errors, sometimes gross ones, if the sample distribution
   departs far from a-priori assumptions.  Thus, a significant issue in
   the design of these algorithms is robustness in the face of skewed
   sample data sets.  The approach in [10] uses theorem-proving to
   justify the robustness of the discrete algorithms presented;
   however, the statistical models in this report are not suited for
   that.  The approach taken in this report is based on detailed
   observation and experiments, a summary of which is included as an
   appendix.  While this gives an excellent qualitative foundation upon
   which to judge robustness, additional quantitative confidence should
   be developed through the use of statistical mechanics.

2.  Majority-Subset Algorithms

   A stochastic model appropriate to a system of mutually suspicious
   clocks can be constructed as follows.  An experiment consists of one
   or more measurements of time differences or offsets between several
   clocks in the network.  Usually, but not necessarily, one of the
   clocks is the local clock at the observer and observations are
   conducted with each of several other clocks in the network.  The fact
   that some clocks are presumed more accurate or trusted more highly
   than others can be expressed by weighting the measurements


Mills                                                           [Page 3]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


   accordingly.  The result is a set of statistics, including means and
   variances, from which the observer is able to estimate the best time
   at which to set the local clock.

   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 on the constraints of the experiment.
   For example, if it is assumed 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 might
   be computed as follows: Determine the variance for every k-sample
   subset of the n observations. Then select the subset with smallest
   variance and use its mean as the estimator for the distribution mean.

   For instance, let n be the number of clocks and k be the next largest
   integer in n/2, that is, the minimum majority.  A majority subset is
   a subset consisting of k of the n offset measurements.  Each of these
   subsets can be represented by a selection of k out of n
   possibilities, with the total number of subsets equal to 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 20

   Obviously, the number of computations required becomes awkward as n
   increases beyond about 10.  Representative majority subsets for n =
   3,4,5 are shown in Table 2.










Mills                                                           [Page 4]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


                 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,5

   Choosing n = 5, for example, requires calculation of the mean and
   variance for ten subsets indexed as shown in Table 2.

   A maximum-likelihood algorithm with provision for multiple samples
   and weights might operate as follows:  Let n be the number of clocks
   and w(1),w(2),...,w(n) a set of integer weights, with w(i) the weight
   associated with the ith clock.  For the ith clock three accumulators
   W(i), X(i) and Y(i) are provided, each initialized to zero.  The ith
   clock is polled some number of times, with each reply x causing n(i)
   to be added to W(i), as well as the weighted sample offset n(i)*x
   added to X(i) and its square (n(i)*x)2 added to Y(i).  Polling is
   continued for each of the n clocks in turn.

   Next, using a majority-subset table such as shown in Table 2,
   calculate the total weight W = sum(W(i)) and 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 calculate the mean m(j) and variance
   s(j):

              m(j) = X/W   and   s(j) = Y/W - m(j)*m(j) .

   When this is complete for all rows, select the row j with the
   smallest s(j) and return the associated mean m(j) as the
   maximum-likelihood estimate of the local-clock offset.










Mills                                                           [Page 5]