home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc956 < prev    next >
Text File  |  1991-04-21  |  67KB  |  1,482 lines

  1.  
  2. Network Working Group                                         D.L. Mills
  3. Request for Comments: 956                               M/A-COM Linkabit
  4.                                                           September 1985
  5.  
  6.               Algorithms for Synchronizing Network Clocks
  7.  
  8.  
  9. Status of this Memo
  10.  
  11.    This RFC discussed clock synchronization algorithms for the
  12.    ARPA-Internet community, and requests discussion and suggestions for
  13.    improvements.  Distribution of this memo is unlimited.
  14.  
  15. Table of Contents
  16.  
  17.    1.      Introduction
  18.    2.      Majority-Subset Algorithms
  19.    3.      Clustering Algorithms
  20.    4.      Application to Time-Synchronization Data
  21.    5.      Summary and Conclusions
  22.    6.      References
  23.    Appendix
  24.    A.      Experimental Determination of Internet Host Clock Accuracies
  25.    A1.     UDP Time Protocol Experiment
  26.    A2.     ICMP Timestamp Message Experiment
  27.    A3.     Comparison of UDP and ICMP Time
  28.  
  29. List of Tables
  30.  
  31.    Table 1.  C(n,k) for n from 2 to 20
  32.    Table 2.  Majority Subsets for n = 3,4,5
  33.    Table 3.  Clustering Algorithm using UDP Time Protocol Data
  34.    Table 4.  Clustering Algorithm using ICMP Timestamp Data
  35.    Table 5.  ISI-MCON-GW Majority-Subset Algorithm
  36.    Table 6.  ISI-MCON-GW Clustering Algorithm
  37.    Table 7.  LL-GW (a) Majority-Subset Algorithm
  38.    Table 8.  LL-GW (a) Clustering Algorithm
  39.    Table 9.  LL-GW (b) Majority-Subset Algorithm
  40.    Table 10. LL-GW (b) Clustering Algorithm
  41.    Table A1. UDP Host Clock Offsets for Various Internet Hosts
  42.    Table A2. UDP Offset Distribution < 9 sec
  43.    Table A3. UDP Offset Distribution < 270 sec
  44.    Table A4. ICMP Offset Distribution < 9 hours
  45.    Table A5. ICMP Offset Distribution < 270 sec
  46.    Table A6. ICMP Offset Distribution < 27 sec
  47.    Table A7. ICMP Offset Distribution < .9 sec
  48.    Table A8. Comparison of UDP and ICMP Host Clock Offsets
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55. Mills                                                           [Page 1]
  56.  
  57.  
  58.  
  59. RFC 956                                                   September 1985
  60. Algorithms for Synchronizing Network Clocks
  61.  
  62.  
  63. 1.  Introduction
  64.  
  65.    The recent interest within the Internet community in determining
  66.    accurate time from a set of mutually suspicious network clocks has
  67.    been prompted by several occasions in which gross errors were found
  68.    in usually reliable, highly accurate clock servers after seasonal
  69.    thunderstorms which disrupted their primary power supply.  To these
  70.    sources of error should be added those due to malfunctioning
  71.    hardware, defective software and operator mistakes, as well as random
  72.    errors in the mechanism used to set and/or synchronize the clocks via
  73.    Internet paths.  The results of these errors can range from simple
  74.    disorientation to major disruption, depending upon the operating
  75.    system, when files or messages are incorrectly timestamped or the
  76.    order of critical network transactions is altered.
  77.  
  78.    This report suggests a stochastic model based on the principles of
  79.    maximum-likelihood estimation, together with algorithms for computing
  80.    a good estimator from a number of time-offset samples measured
  81.    between one or more clocks connected via network links.  The model
  82.    provides a rational method for detecting and resolving errors due to
  83.    faulty clocks or excessively noisy links.  Included in this report
  84.    are descriptions of certain experiments conducted with Internet hosts
  85.    and ARPANET paths which give an indication of the effectiveness of
  86.    the algorithms.
  87.  
  88.    Several mechanisms have been specified in the Internet protocol suite
  89.    to record and transmit the time at which an event takes place,
  90.    including the ICMP Timestamp message [6], Time Protocol [7], Daytime
  91.    protocol [8] and IP Timestamp option [9].  A new Network Time
  92.    Protocol [12] has been proposed as well.  Additional information on
  93.    network time synchronization can be found in the References at the
  94.    end of this document.  Synchronization protocols are described in [3]
  95.    and [12] and synchronization algorithms in [2], [5] and [10].
  96.    Experimental results on measured roundtrip delays and clock offsets
  97.    in the Internet are discussed in [4] and [11].  A comprehensive
  98.    mathematical treatment of clock synchronization can be found in [1].
  99.  
  100.    In [10] the problem of synchronizing a set of mutually suspicious
  101.    clocks is discussed and algorithms offered which maximize in some
  102.    sense the expectation that a correct set of "good" clocks can be
  103.    extracted from the population including also "bad" ones.  The
  104.    technique is based upon overlapping, discrete confidence intervals
  105.    which are assigned a-priori.  The model assumes the reasonable
  106.    presumption that "bad" clocks display errors far outside these
  107.    confidence intervals, so can be easily identified and discarded from
  108.    the voting process.
  109.  
  110.  
  111.  
  112. Mills                                                           [Page 2]
  113.  
  114.  
  115.  
  116. RFC 956                                                   September 1985
  117. Algorithms for Synchronizing Network Clocks
  118.  
  119.  
  120.    As apparent from the data summarized in Appendix A, host clocks in a
  121.    real network commonly indicate various degrees of dispersion with
  122.    respect to each other and to a standard-time reference such as a
  123.    radio clock.  The sources of dispersion include random errors due to
  124.    observational phenomena and the synchronization mechanism itself, if
  125.    used, as well as systematic errors due to hardware or software
  126.    failure, poor radio reception conditions or operator mistakes.  In
  127.    general, it is not possible to accurately quantify whether the
  128.    dispersion of any particular clock qualifies the clock as "good" or
  129.    "bad," except on a statistical basis.  Thus, from a practical
  130.    standpoint, a statistical-estimation approach to the problem is
  131.    preferred over a discrete-decision one.
  132.  
  133.    A basic assumption in this report is that the majority of "good"
  134.    clocks display errors clustered around a zero offset relative to
  135.    standard time, as determined for example from a radio clock, while
  136.    the remaining "bad" clocks display errors distributed randomly over
  137.    the observing interval.  The problem is to select the good clocks
  138.    from the bad and to estimate the correction to apply to the local
  139.    clock in order to display the most accurate time.  The algorithms
  140.    described in this report attempt to do this using maximum-likelihood
  141.    techniques, which are theory.
  142.  
  143.    It should be noted that the algorithms discussed in [10] and in this
  144.    report are are basically filtering and smoothing algorithms and can
  145.    result in errors, sometimes gross ones, if the sample distribution
  146.    departs far from a-priori assumptions.  Thus, a significant issue in
  147.    the design of these algorithms is robustness in the face of skewed
  148.    sample data sets.  The approach in [10] uses theorem-proving to
  149.    justify the robustness of the discrete algorithms presented;
  150.    however, the statistical models in this report are not suited for
  151.    that.  The approach taken in this report is based on detailed
  152.    observation and experiments, a summary of which is included as an
  153.    appendix.  While this gives an excellent qualitative foundation upon
  154.    which to judge robustness, additional quantitative confidence should
  155.    be developed through the use of statistical mechanics.
  156.  
  157. 2.  Majority-Subset Algorithms
  158.  
  159.    A stochastic model appropriate to a system of mutually suspicious
  160.    clocks can be constructed as follows.  An experiment consists of one
  161.    or more measurements of time differences or offsets between several
  162.    clocks in the network.  Usually, but not necessarily, one of the
  163.    clocks is the local clock at the observer and observations are
  164.    conducted with each of several other clocks in the network.  The fact
  165.    that some clocks are presumed more accurate or trusted more highly
  166.    than others can be expressed by weighting the measurements
  167.  
  168.  
  169. Mills                                                           [Page 3]
  170.  
  171.  
  172.  
  173. RFC 956                                                   September 1985
  174. Algorithms for Synchronizing Network Clocks
  175.  
  176.  
  177.    accordingly.  The result is a set of statistics, including means and
  178.    variances, from which the observer is able to estimate the best time
  179.    at which to set the local clock.
  180.  
  181.    A maximum-likelihood estimator is a statistic that maximizes the
  182.    probability that a particular outcome of an experiment is due to a
  183.    presumed set of assumptions on the constraints of the experiment.
  184.    For example, if it is assumed that at least k of n observations
  185.    include only samples from a single distribution, then a
  186.    maximum-likelihood estimator for the mean of that distribution might
  187.    be computed as follows: Determine the variance for every k-sample
  188.    subset of the n observations. Then select the subset with smallest
  189.    variance and use its mean as the estimator for the distribution mean.
  190.  
  191.    For instance, let n be the number of clocks and k be the next largest
  192.    integer in n/2, that is, the minimum majority.  A majority subset is
  193.    a subset consisting of k of the n offset measurements.  Each of these
  194.    subsets can be represented by a selection of k out of n
  195.    possibilities, with the total number of subsets equal to C(n,k).  The
  196.    number of majority subsets is tallied for n from 2 to 20 in Table 1.
  197.  
  198.      (n,k)           C(n,k)                  (n,k)           C(n,k)
  199.      ----------------------                  ----------------------
  200.      (2,2)           1                       (11,6)          462   
  201.      (3,2)           3                       (12,7)          792   
  202.      (4,3)           4                       (13,7)          1716  
  203.      (5,3)           10                      (14,8)          3003  
  204.      (6,4)           15                      (15,8)          6435  
  205.      (7,4)           35                      (16,9)          11440 
  206.      (8,5)           56                      (17,9)          24310 
  207.      (9,5)           126                     (18,10)         43758 
  208.      (10,6)          210                     (19,10)         92378 
  209.                                              (20,11)         167960
  210.  
  211.                    Table 1. C(n,k) for n from 2 to 20
  212.  
  213.    Obviously, the number of computations required becomes awkward as n
  214.    increases beyond about 10.  Representative majority subsets for n =
  215.    3,4,5 are shown in Table 2.
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Mills                                                           [Page 4]
  227.  
  228.  
  229.  
  230. RFC 956                                                   September 1985
  231. Algorithms for Synchronizing Network Clocks
  232.  
  233.  
  234.                  C(3,2)          C(4,3)          C(5,3)
  235.                  ------          ------          ------
  236.                  1,2             1,2,3           1,2,3
  237.                  1,3             1,2,4           1,2,4
  238.                  2,3             1,3,4           1,2,5
  239.                                  2,3,4           1,3,4
  240.                                                  1,3,5
  241.                                                  1,4,5
  242.                                                  2,3,4
  243.                                                  2,3,5
  244.                                                  2,4,5
  245.                                                  3,4,5
  246.  
  247.                 Table 2. Majority Subsets for n = 3,4,5
  248.  
  249.    Choosing n = 5, for example, requires calculation of the mean and
  250.    variance for ten subsets indexed as shown in Table 2.
  251.  
  252.    A maximum-likelihood algorithm with provision for multiple samples
  253.    and weights might operate as follows:  Let n be the number of clocks
  254.    and w(1),w(2),...,w(n) a set of integer weights, with w(i) the weight
  255.    associated with the ith clock.  For the ith clock three accumulators
  256.    W(i), X(i) and Y(i) are provided, each initialized to zero.  The ith
  257.    clock is polled some number of times, with each reply x causing n(i)
  258.    to be added to W(i), as well as the weighted sample offset n(i)*x
  259.    added to X(i) and its square (n(i)*x)2 added to Y(i).  Polling is
  260.    continued for each of the n clocks in turn.
  261.  
  262.    Next, using a majority-subset table such as shown in Table 2,
  263.    calculate the total weight W = sum(W(i)) and weighted sums X =
  264.    sum(X(i)) and Y = sum(Y(i)*Y(i)) for each i in the jth majority
  265.    subset (row). From W, X and Y calculate the mean m(j) and variance
  266.    s(j):
  267.  
  268.               m(j) = X/W   and   s(j) = Y/W - m(j)*m(j) .
  269.  
  270.    When this is complete for all rows, select the row j with the
  271.    smallest s(j) and return the associated mean m(j) as the
  272.    maximum-likelihood estimate of the local-clock offset.
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283. Mills                                                           [Page 5]
  284.  
  285.  
  286.  
  287. RFC 956                                                   September 1985
  288. Algorithms for Synchronizing Network Clocks
  289.  
  290.  
  291. 3.  Clustering Algorithms
  292.  
  293.    Another method for developing a maximum-likelihood estimator is
  294.    through the use of clustering algorithms.  These algorithms operate
  295.    to associate points in a sample set with clusters on the basis of
  296.    stochastic properties and are most useful when large numbers of
  297.    samples are available.  One such algorithm operates on a sample set
  298.    to selectively discard points presumed outside the cluster as
  299.    follows:
  300.  
  301.       1.  Start with a sample set of n observations {x(1),x(2),...,x(n)
  302.  
  303.       2.  Compute the mean of the n observations in the sample set.
  304.           Discard the single sample x(i) with value furthest from the
  305.           mean, leaving n-1 observations in the set.
  306.  
  307.       3.  Continue with step 2 until only a single observation is left,
  308.           at which point declare its value the maximum-likelihood
  309.           estimator.
  310.  
  311.    This algorithm will usually (but not necessarily) converge to the
  312.    desired result if the majority of observations are the result of
  313.    "good" clocks, which by hypothesis are clustered about zero offset
  314.    relative to the reference clock, with the remainder scattered
  315.    randomly over the observation interval.
  316.  
  317.    The following Table 3 summarizes the results of this algorithm
  318.    applied to the UDP data shown in Appendix A, which represents the
  319.    measured clock offsets of 163 host clocks in the Internet system.
  320.    These data were assembled using the UDP Time protocol [7], in which
  321.    time is represented to a precision of one second.  Each line of the
  322.    table represents the result of step 2 above along with the size of
  323.    the sample set and its (unweighted) mean and variance.  The "Discard"
  324.    column shows the value of the observation discarded at that step.
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340. Mills                                                           [Page 6]
  341.  
  342.  
  343.  
  344. RFC 956                                                   September 1985
  345. Algorithms for Synchronizing Network Clocks
  346.  
  347.  
  348.                     Size    Mean    Var     Discard
  349.                     -------------------------------
  350.                     163     -210    9.1E+6  -38486 
  351.                     162     26      172289  3728   
  352.                     161     3       87727   3658   
  353.                     160     -20     4280    -566   
  354.                     150     -17     1272    88     
  355.                     100     -18     247     -44    
  356.                     50      -4      35      8      
  357.                     20      -1      0       -2     
  358.                     19      -1      0       -2     
  359.                     18      -1      0       -2     
  360.                     17      -1      0       1      
  361.                     16      -1      0       -1     
  362.                     15      -1      0       -1     
  363.                     14      -1      0       -1     
  364.                     13      0       0       0      
  365.                     1       0       0       0      
  366.  
  367.        Table 3. Clustering Algorithm using UDP Time Protocol Data
  368.  
  369.    In Table 3 only a few of the 163 steps are shown, including those
  370.    near the beginning which illustrate a rapid convergence as the
  371.    relatively few outliers are discarded.  The large outlier discarded
  372.    in the first step is almost certainly due to equipment or operator
  373.    failure. The two outliers close to one hour discarded in the next two
  374.    steps are probably simple operator mistakes like entering summer time
  375.    instead of standard time.  By the time only 50 samples are left, the
  376.    error has shrunk to about 4 sec and the largest outlier is within 12
  377.    sec of the estimate.  By the time only 20 samples are left, the error
  378.    has shrunk to about a second and the variance has vanished for
  379.    practical purposes.
  380.  
  381.    The following Table 4 summarizes the results of the clustering
  382.    algorithm applied to the ICMP data shown in Appendix A, which
  383.    represents the measured clock offsets of 504 host clocks in the
  384.    Internet system. These data were assembled using ICMP Timestamp
  385.    messages [6], in which time is represented to a precision of one
  386.    millisecond.  The columns in Table 4 should be interpreted in the
  387.    same way as in Table 3, except that the data in Table 4 are in
  388.    milliseconds, while the data in Table 3 are in seconds.
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397. Mills                                                           [Page 7]
  398.  
  399.  
  400.  
  401. RFC 956                                                   September 1985
  402. Algorithms for Synchronizing Network Clocks
  403.  
  404.  
  405.                     Size    Mean    Var     Discard
  406.                     -------------------------------
  407.                     504     -3.0E+6 3.2E+14 8.6E+7 
  408.                     500     -3.3E+6 2.9E+14 8.6E+7 
  409.                     450     -1.6E+6 3.0E+13 -2.5E+7
  410.                     400     29450   2.2E+11 3.6E+6 
  411.                     350     -3291   4.1E+9  -185934
  412.                     300     3611    1.6E+9  -95445 
  413.                     250     2967    6.8E+8  66743  
  414.                     200     4047    2.3E+8  39288  
  415.                     150     1717    8.6E+7  21346  
  416.                     100     803     1.9E+7  10518  
  417.                     80      1123    8.4E+6  -4863  
  418.                     60      1119    3.1E+6  4677   
  419.                     50      502     1.5E+6  -2222  
  420.                     40      432     728856  2152   
  421.                     30      84      204651  -987   
  422.                     20      30      12810   338    
  423.                     15      28      2446    122    
  424.                     10      7       454     49     
  425.                     8       -2      196     24     
  426.                     6       -9      23      0      
  427.                     4       -10     5       -13    
  428.                     2       -8      0       -8     
  429.  
  430.         Table 4. Clustering Algorithm using ICMP Timestamp Data
  431.  
  432.    As in Table 3 above, only some of the 504 steps are shown in Table 4.
  433.    The distinguishing feature of the data in Table 4 is that the raw
  434.    data are much more noisy - only some 30 host clocks are closer than
  435.    one second from the reference clock, while half were further than one
  436.    minute and over 100 further than one hour from it.  The fact that the
  437.    algorithm converged to within 8 msec of the reference time under
  438.    these conditions should be considered fairly remarkable in view of
  439.    the probability that many of the outliers discarded are almost
  440.    certainly due to defective protocol implementations.  Additional
  441.    information on these experiments is presented in Appendix A.
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.  
  454. Mills                                                           [Page 8]
  455.  
  456.  
  457.  
  458. RFC 956                                                   September 1985
  459. Algorithms for Synchronizing Network Clocks
  460.  
  461.  
  462. 4.  Application to Time-Synchronization Data
  463.  
  464.    A variation of the above algorithms can be used to improve the offset
  465.    estimates from a single clock by discarding noise samples produced by
  466.    occasional retransmissions in the network, for example.  A set of n
  467.    independent samples is obtained by polling the clock.  Then, a
  468.    majority-subset table is used to compute the m(j) and s(j) statistics
  469.    and the maximum-likelihood estimate determined as above.  For this
  470.    purpose the majority-subset table could include larger subsets as
  471.    well. In this manner the maximum-likelihood estimates from each of
  472.    several clocks can be determined and used in the algorithm above.
  473.  
  474.    In order to test the effectiveness of this algorithm, a set of
  475.    experiments was performed using two WIDEBAND/EISN gateways equipped
  476.    with WWVB radio clocks and connected to the ARPANET.  These
  477.    experiments were designed to determine the limits of accuracy when
  478.    comparing these clocks via ARPANET paths.  One of the gateways
  479.    (ISI-MCON-GW) is located at the Information Sciences Institute near
  480.    Los Angeles, while the other (LL-GW) is located at Lincoln
  481.    Laboratories near Boston.  Both gateways consist of PDP11/44
  482.    computers running the EPOS operating system and clock-interface
  483.    boards with oscillators phase-locked to the WWVB clock.
  484.  
  485.    The clock indications of the WIDEBAND/EISN gateways were compared
  486.    with the DCNet WWVB reference clock using ICMP Timestamp messages,
  487.    which record the individual timestamps with a precision of a
  488.    millisecond. However, the path over the ARPANET between these
  489.    gateways and the measurement host can introduce occasional
  490.    measurement errors as large as several seconds.  In principle the
  491.    effect of these errors can be minimized by using a large sample
  492.    population;  however, use of the above algorithms allows higher
  493.    accuracies to be obtained with far fewer samples.
  494.  
  495.    Measurements were made separately with each of the two gateways by
  496.    sending an ICMP Timestamp Request message from the ARPANET address of
  497.    DCN1 to the ARPANET address of the gateway and computing the
  498.    round-trip delay and clock offset from the ICMP Timestamp Reply
  499.    message.  This process was continued for 1000 message exchanges,
  500.    which took from seven minutes to several hours, depending on the
  501.    sample interval selected.
  502.  
  503.    The tables below summarize the results of both the majority-subset
  504.    and clustering algorithms applied to the data from three experiments,
  505.    one with ISI-MCON-GW and two with LL-GW.  The ISI-MCON-GW and LL-GW
  506.    (a) experiments were designed to determine the limits of accuracy
  507.    when using a continuous sequence of request/reply volleys, which
  508.  
  509.  
  510.  
  511. Mills                                                           [Page 9]
  512.  
  513.  
  514.  
  515. RFC 956                                                   September 1985
  516. Algorithms for Synchronizing Network Clocks
  517.  
  518.  
  519.    resulted in over two samples per second.  The remaining LL-GW (b)
  520.    experiment was designed to determine the limits of accuracy using a
  521.    much lower rate of about one sample every ten seconds.
  522.  
  523.    For each of the three experiments two tables are shown, one using the
  524.    majority-subset algorithm and the other the clustering algorithm. The
  525.    two rows of the majority-subset tables show the statistics derived
  526.    both from the raw data and from the filtered data processed by a
  527.    C(5,3) majority-subset algorithm.  In all cases the extrema and
  528.    variance are dramatically less for the filtered data than the raw
  529.    data, lending credence to the conjecture that the mean statistic for
  530.    the filtered data is probably a good maximum-likelihood estimator of
  531.    the true offset.
  532.  
  533.                               Mean    Var     Max     Min
  534.              -------------------------------------------- 
  535.              Raw data        637     2.1E+7  32751   -1096
  536.              C(5,3)          -15     389     53      -103 
  537.  
  538.              Table 5. ISI-MCON-GW Majority-Subset Algorithm
  539.  
  540.                     Size    Mean    Var     Discard
  541.                     -------------------------------
  542.                     1000    637     2.1E+7  32751  
  543.                     990     313     1.0E+7  32732  
  544.                     981     15      1.0E+6  32649  
  545.                     980     -18     2713    -1096  
  546.                     970     -15     521     -122   
  547.                     960     -15     433     -97    
  548.                     940     -15     332     -75    
  549.                     900     -15     239     26     
  550.                     800     -15     141     12     
  551.                     700     -16     87      5      
  552.                     600     -17     54      -31    
  553.                     500     -16     33      -5     
  554.                     400     -18     18      -9     
  555.                     300     -19     7       -12    
  556.                     200     -19     2       -21    
  557.                     100     -18     0       -19    
  558.                     1       -17     0       -17    
  559.  
  560.                Table 6. ISI-MCON-GW Clustering Algorithm
  561.  
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568. Mills                                                          [Page 10]
  569.  
  570.  
  571.  
  572. RFC 956                                                   September 1985
  573. Algorithms for Synchronizing Network Clocks
  574.  
  575.  
  576.                               Mean    Dev     Max     Min
  577.               --------------------------------------------
  578.               Raw data        566     1.8E+7  32750   -143
  579.               C(5,3)          -23     81      14      -69 
  580.  
  581.               Table 7. LL-GW (a) Majority-Subset Algorithm
  582.  
  583.                     Size    Mean    Var     Discard
  584.                     -------------------------------
  585.                     1000    566     1.8E+7  32750  
  586.                     990     242     8.5E+6  32726  
  587.                     983     10      1.0E+6  32722  
  588.                     982     -23     231     -143   
  589.                     980     -23     205     -109   
  590.                     970     -22     162     29     
  591.                     960     -23     128     13     
  592.                     940     -23     105     -51    
  593.                     900     -24     89      1      
  594.                     800     -25     49      -9     
  595.                     700     -26     31      -36    
  596.                     600     -26     21      -34    
  597.                     500     -27     14      -20    
  598.                     400     -29     7       -23    
  599.                     300     -30     3       -33    
  600.                     200     -29     1       -27    
  601.                     100     -29     0       -28    
  602.                     1       -29     0       -29    
  603.  
  604.                 Table 8. LL-GW (a) Clustering Algorithm
  605.  
  606.                               Mean    Dev     Max     Min
  607.              -------------------------------------------- 
  608.              Raw data        378     2.1E+7  32760   -32758
  609.              C(5,3)          -21     1681    329     -212  
  610.  
  611.               Table 9. LL-GW (b) Majority-Subset Algorithm
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625. Mills                                                          [Page 11]
  626.  
  627.  
  628.  
  629. RFC 956                                                   September 1985
  630. Algorithms for Synchronizing Network Clocks
  631.  
  632.  
  633.                     Size    Mean    Var     Discard
  634.                     -------------------------------
  635.                     1000    377     2.1E+7  -32758 
  636.                     990     315     1.0E+7  32741  
  637.                     981     18      1.1E+6  32704  
  638.                     980     -16     16119   -1392  
  639.                     970     -17     5382    554    
  640.                     960     -21     3338    311    
  641.                     940     -24     2012    168    
  642.                     900     -22     1027    -137   
  643.                     800     -23     430     -72    
  644.                     700     -23     255     -55    
  645.                     600     -22     167     -45    
  646.                     500     -22     109     -40    
  647.                     400     -21     66      -6     
  648.                     300     -18     35      -29    
  649.                     200     -17     15      -23    
  650.                     100     -19     3       -15    
  651.                     50      -21     0       -19    
  652.                     20      -21     0       -21    
  653.                     10      -20     0       -20    
  654.                     1       -20     0       -20    
  655.  
  656.                 Table 10. LL-GW (b) Clustering Algorithm
  657.  
  658.    The rows of the clustering tables show the result of selected steps
  659.    in the algorithm as it discards samples furthest from the mean.  The
  660.    first twenty steps or so discard samples with gross errors over 30
  661.    seconds.  These samples turned out to be due to a defect in the
  662.    timestamping procedure implemented in the WIDEBAND/EISN gateway code
  663.    which caused gross errors in about two percent of the ICMP Timestamp
  664.    Reply messages.  These samples were left in the raw data as received
  665.    in order to determine how the algorithms would behave in such extreme
  666.    cases.  As apparent from the tables, both the majority-subset and
  667.    clustering algorithms effectively coped with the situation.
  668.  
  669.    In the statement of the clustering algorithm the terminating
  670.    condition was specified as when only a single sample is left in the
  671.    sample set.  However, it is not necessary to proceed that far.  For
  672.    instance, it is known from the design of the experiment and the
  673.    reference clocks that accuracies better than about ten milliseconds
  674.    are probably unrealistic.  A rough idea of the accuracy of the mean
  675.    is evident from the deviation, computed as the square root of the
  676.    variance. Thus, attempts to continue the algorithm beyond the point
  677.    where the variance drops below 100 or so are probably misguided.
  678.    This occurs when between 500 and 900 samples remain in the sample
  679.  
  680.  
  681.  
  682. Mills                                                          [Page 12]
  683.  
  684.  
  685.  
  686. RFC 956                                                   September 1985
  687. Algorithms for Synchronizing Network Clocks
  688.  
  689.  
  690.    set, depending upon the particular experiment.  Note that in any case
  691.    between 300 and 700 samples fall within ten milliseconds of the final
  692.    estimate, depending on experiment.
  693.  
  694.    Comparing the majority-subset and clustering algorithms on the basis
  695.    of variance reveals the interesting observation that the result of
  696.    the C(5,3) majority-subset algorithm is equivalent to the clustering
  697.    algorithm when between roughly 900 and 950 samples remain in the
  698.    sample set.  This together with the moderately high variance in the
  699.    ISI-MCON-GW and LL-GW (b) cases suggests a C(6,4) or even C(7,4)
  700.    algorithm might yield greater accuracies.
  701.  
  702. 5.  Summary and Conclusions
  703.  
  704.    The principles of maximum-likelihood estimation are well known and
  705.    widely applied in communication electronics.  In this note two
  706.    algorithms using these principles are proposed, one based on
  707.    majority-subset techniques appropriate for cases involving small
  708.    numbers of samples and the other based on clustering techniques
  709.    appropriate for cases involving large numbers of samples.
  710.  
  711.    The algorithms were tested on raw data collected with Internet hosts
  712.    and gateways over ARPANET paths for the purpose of setting a local
  713.    host clock with respect to a remote reference while maintaining
  714.    accuracies in the order of ten milliseconds.  The results demonstrate
  715.    the effectiveness of these algorithms in detecting and discarding
  716.    glitches due to hardware or software failure or operator mistakes.
  717.    They also demonstrate that time synchronization can be maintained
  718.    across the ARPANET in the order of ten milliseconds in spite of
  719.    glitches many times the mean roundtrip delay.
  720.  
  721.    The results point to the need for an improved time-synchronization
  722.    protocol combining the best features of the ICMP Timestamp message
  723.    [6] and UDP Time protocol [7].  Among the features suggested for this
  724.    protocol are the following:
  725.  
  726.       1.  The protocol should be based on UDP, which provides the
  727.           flexibility to handle simultaneous, multiplexed queries and
  728.           responses.
  729.  
  730.       2.  The message format should be based on the ICMP Timestamp
  731.           message format, which provides the arrival and departure times
  732.           at the server and allows the client to calculate the roundtrip
  733.           delay and offset accurately.
  734.  
  735.  
  736.  
  737.  
  738.  
  739. Mills                                                          [Page 13]
  740.  
  741.  
  742.  
  743. RFC 956                                                   September 1985
  744. Algorithms for Synchronizing Network Clocks
  745.  
  746.  
  747.       3.  The data format should be based on the UDP Time format, which
  748.           specifies 32-bit time in seconds since 1 January 1900, but
  749.           extended additional bits for the fractional part of a second.
  750.  
  751.       4.  Provisions to specify the expected accuracy should be included
  752.           along with information about the reference clock or
  753.           synchronizing mechanism, as well as the expected drift rate
  754.           and the last time the clock was set or synchronized.
  755.  
  756.    The next step should be formulating an appropriate protocol with the
  757.    above features, together with implementation and test in the Internet
  758.    environment.  Future development should result in a distributed,
  759.    symmetric protocol, similar perhaps to those described in [1], for
  760.    distributing highly reliable timekeeping information using a
  761.    hierarchical set of trusted clocks.
  762.  
  763. 6.  References
  764.  
  765.    1.  Lindsay, W.C., and A.V.  Kantak.  Network synchronization of
  766.        random signals.  IEEE Trans.  Comm.  COM-28, 8 (August 1980),
  767.        1260-1266.
  768.  
  769.    2.  Mills, D.L.  Time Synchronization in DCNET Hosts.  DARPA Internet
  770.        Project Report IEN-173, COMSAT Laboratories, February 1981.
  771.  
  772.    3.  Mills, D.L.  DCNET Internet Clock Service.  DARPA Network Working
  773.        Group Report RFC-778, COMSAT Laboratories, April 1981.
  774.  
  775.    4.  Mills, D.L.  Internet Delay Experiments.  DARPA Network Working
  776.        Group Report RFC-889, M/A-COM Linkabit, December 1983.
  777.  
  778.    5.  Mills, D.L.  DCN Local-Network Protocols.  DARPA Network Working
  779.        Group Report RFC-891, M/A-COM Linkabit, December 1983.
  780.  
  781.    6.  Postel, J.  Internet Control Message Protocol.  DARPA Network
  782.        Working Group Report RFC-792, USC Information Sciences Institute,
  783.        September 1981.
  784.  
  785.    7.  Postel, J.  Time Protocol.  DARPA Network Working Group Report
  786.        RFC-868, USC Information Sciences Institute, May 1983.
  787.  
  788.    8.  Postel, J.  Daytime Protocol.  DARPA Network Working Group Report
  789.        RFC-867, USC Information Sciences Institute, May 1983.
  790.  
  791.    9.  Su, Z.  A Specification of the Internet Protocol (IP) Timestamp
  792.        Option.  DARPA Network Working Group Report RFC-781.  SRI
  793.        International, May 1981.
  794.  
  795.  
  796. Mills                                                          [Page 14]
  797.  
  798.  
  799.  
  800. RFC 956                                                   September 1985
  801. Algorithms for Synchronizing Network Clocks
  802.  
  803.  
  804.    10. Marzullo, K., and S.  Owicki.  Maintaining the Time in a
  805.        Distributed System.  ACM Operating Systems Review 19, 3 (July
  806.        1985), 44-54.
  807.  
  808.    11. Mills, D.L.  Experiments in Network Clock Synchronization.  DARPA
  809.        Network Working Group Report RFC-957, M/A-COM Linkabit, September
  810.        1985.
  811.  
  812.    12. Mills, D.L.  Network Time Protocol (NTP).  DARPA Network Working
  813.        Group Report RFC-958, M/A-COM Linkabit, September 1985.
  814.  
  815. Appendix A.
  816.  
  817.    Experimental Determination of Internet Host Clock Accuracies
  818.  
  819.    Following is a summary of the results of three experiments designed
  820.    to reveal the accuracies of various Internet host clocks.  The first
  821.    experiment uses the UDP Time protocol, which is limited in precision
  822.    to one second, while the second uses the ICMP Timestamp message,
  823.    which extends the precision to one millisecond.  In the third
  824.    experiment the results indicated by UDP and ICMP are compared.  In
  825.    the UDP Time protocol time is indicated as a 32-bit field in seconds
  826.    past 0000 UT on 1 January 1900, while in the ICMP Timestamp message
  827.    time is indicated as a 32-bit field in milliseconds past 0000 UT of
  828.    each day.
  829.  
  830.    All experiments described herein were conducted from Internet host
  831.    DCN6.ARPA, which is normally synchronized to a WWV radio clock.  In
  832.    order to improve accuracy during the experiments, the DCN6.ARPA host
  833.    was resynchronized to a WWVB radio clock.  As the result of several
  834.    experiments with other hosts equipped with WWVB and WWV radio clocks
  835.    and GOES satellite clocks, it is estimated that the maximum
  836.    measurement error in the following experiments is less than about 30
  837.    msec relative to standard NBS time determined at the Boulder/Fort
  838.    Collins transmitting sites.
  839.  
  840.    A1.  UDP Time Protocol Experiment
  841.  
  842.       In the first experiment four UDP Time protocol requests were sent
  843.       at about three-second intervals to each of the 1775 hosts listed
  844.       in the NIC Internet host table.  A total of 555 samples were
  845.       received from 163 hosts and compared with a local reference based
  846.       on a WWVB radio clock, which is known to be accurate to within a
  847.       few milliseconds.  Not all of these hosts were listed as
  848.       supporting the UDP Time protocol in the NIC Internet host table,
  849.       while some that were listed as supporting this protocol either
  850.       failed to respond or responded with various error messages.
  851.  
  852.  
  853. Mills                                                          [Page 15]
  854.  
  855.  
  856.  
  857. RFC 956                                                   September 1985
  858. Algorithms for Synchronizing Network Clocks
  859.  
  860.  
  861.       In the following table "Host" is the canonical name of the host
  862.       and "Count" the number of replies received.  The remaining data
  863.       represent the time offset, in seconds, necessary to correct the
  864.       local (reference) clock to agree with the host cited.  The "Max"
  865.       and "Min" represent the maximum and minimum of these offsets,
  866.       while "Mean" represents the mean value and "Var" the variance, all
  867.       rounded to the nearest second.
  868.  
  869.          Host                    Count   Max     Min     Mean    Var
  870.          -----------------------------------------------------------
  871.          BBN-CLXX.ARPA           4       -11     -12     -11     0
  872.          BBN-KIWI.ARPA           4       -11     -12     -11     0
  873.          BBN-META.ARPA           4       -11     -12     -11     0
  874.          BBNA.ARPA               1       22      22      22      0
  875.          BBNG.ARPA               4       87      87      87      0
  876.          BELLCORE-CS-GW.ARPA     3       72      71      71      0
  877.          BLAYS.PURDUE.EDU        2       -1      -1      -1      0
  878.          CMU-CC-TE.ARPA          4       -94     -95     -94     0
  879.          CMU-CS-C.ARPA           3       6       5       5       0
  880.          CMU-CS-CAD.ARPA         4       -37     -37     -37     0
  881.          CMU-CS-CFS.ARPA         3       -42     -43     -42     0
  882.          CMU-CS-G.ARPA           3       -30     -31     -30     0
  883.          CMU-CS-GANDALF.ARPA     3       -42     -43     -42     0
  884.          CMU-CS-H.ARPA           4       -36     -37     -36     0
  885.          CMU-CS-IUS.ARPA         3       -44     -45     -44     0
  886.          CMU-CS-IUS2.ARPA        3       -44     -44     -44     0
  887.          CMU-CS-K.ARPA           3       -31     -31     -31     0
  888.          CMU-CS-SAM.ARPA         4       -74     -75     -74     0
  889.          CMU-CS-SPEECH.ARPA      4       -39     -40     -39     0
  890.          CMU-CS-SPEECH2.ARPA     4       -49     -50     -49     0
  891.          CMU-CS-SPICE.ARPA       4       -131    -132    -131    0
  892.          CMU-CS-THEORY.ARPA      4       -36     -37     -36     0
  893.          CMU-CS-UNH.ARPA         4       -44     -45     -44     0
  894.          CMU-CS-VLSI.ARPA        4       -66     -66     -66     0
  895.          CMU-RI-ARM.ARPA         3       -41     -41     -41     0
  896.          CMU-RI-CIVE.ARPA        3       -44     -45     -44     0
  897.          CMU-RI-FAS.ARPA         4       -27     -28     -27     0
  898.          CMU-RI-ISL1.ARPA        4       -18     -19     -18     0
  899.          CMU-RI-ISL3.ARPA        3       -49     -50     -49     0
  900.          CMU-RI-LEG.ARPA         3       -33     -33     -33     0
  901.          CMU-RI-ML.ARPA          4       42      42      42      0
  902.          CMU-RI-ROVER.ARPA       4       -48     -49     -48     0
  903.          CMU-RI-SENSOR.ARPA      2       -40     -41     -40     0
  904.          CMU-RI-VI.ARPA          3       -65     -65     -65     0
  905.          COLUMBIA.ARPA           1       8       8       8       0
  906.          CU-ARPA.CS.CORNELL.EDU  4       5       3       4       0
  907.          CYPRESS.ARPA            4       2       1       1       0
  908.  
  909.  
  910. Mills                                                          [Page 16]
  911.  
  912.  
  913.  
  914. RFC 956                                                   September 1985
  915. Algorithms for Synchronizing Network Clocks
  916.  
  917.  
  918.          DCN1.ARPA               4       0       0       0       0
  919.          DCN5.ARPA               4       0       0       0       0
  920.          DCN6.ARPA               4       0       0       0       0
  921.          DCN7.ARPA               4       -1      -1      0       0
  922.          DCN9.ARPA               4       -3      -3      -3      0
  923.          DEVVAX.TN.CORNELL.EDU   2       3659    3658    3658    0
  924.          ENEEVAX.ARPA            4       73      72      72      0
  925.          FORD-WDL1.ARPA          4       -59     -60     -59     0
  926.          FORD1.ARPA              4       0       0       0       0
  927.          GUENEVERE.PURDUE.EDU    3       1       0       0       0
  928.          GVAX.CS.CORNELL.EDU     4       -18     -18     -18     0
  929.          IM4U.ARPA               4       -6      -6      -6      0
  930.          IPTO-FAX.ARPA           4       0       0       0       0
  931.          KANKIN.ARPA             4       -3      -4      -3      0
  932.          MERLIN.PURDUE.EDU       2       3       3       3       0
  933.          MIT-ACHILLES.ARPA       4       16      16      16      0
  934.          MIT-AGAMEMNON.ARPA      4       -63     -64     -63     0
  935.          MIT-ANDROMACHE.ARPA     4       -28     -28     -28     0
  936.          MIT-APHRODITE.ARPA      4       -7      -8      -7      0
  937.          MIT-APOLLO.ARPA         4       -8      -9      -8      0
  938.          MIT-ARES.ARPA           4       -25     -26     -25     0
  939.          MIT-ARTEMIS.ARPA        4       -34     -35     -34     0
  940.          MIT-ATHENA.ARPA         4       -37     -37     -37     0
  941.          MIT-ATLAS.ARPA          4       -26     -26     -26     0
  942.          MIT-CASTOR.ARPA         4       -35     -35     -35     0
  943.          MIT-DAFFY-DUCK.ARPA     2       -72     -73     -72     0
  944.          MIT-DEMETER.ARPA        4       -28     -29     -28     0
  945.          MIT-GOLDILOCKS.ARPA     1       -20     -20     -20     0
  946.          MIT-HECTOR.ARPA         4       -23     -24     -23     0
  947.          MIT-HELEN.ARPA          4       6       5       5       0
  948.          MIT-HERA.ARPA           4       -34     -35     -34     0
  949.          MIT-HERACLES.ARPA       4       -36     -36     -36     0
  950.          MIT-JASON.ARPA          4       -36     -37     -36     0
  951.          MIT-MENELAUS.ARPA       4       -32     -33     -32     0
  952.          MIT-MULTICS.ARPA        3       25      23      24      0
  953.          MIT-ODYSSEUS.ARPA       4       20      19      19      0
  954.          MIT-ORPHEUS.ARPA        4       -34     -35     -34     0
  955.          MIT-PARIS.ARPA          4       -35     -35     -35     0
  956.          MIT-POSEIDON.ARPA       4       -39     -41     -40     0
  957.          MIT-PRIAM.ARPA          4       -24     -25     -24     0
  958.          MIT-REAGAN.ARPA         4       115     115     115     0
  959.          MIT-THESEUS.ARPA        4       -43     -44     -43     0
  960.          MIT-TRILLIAN.ARPA       4       -38     -39     -38     0
  961.          MIT-TWEETY-PIE.ARPA     3       106     105     105     0
  962.          MIT-ZERMATT.ARPA        4       -75     -76     -75     0
  963.          MIT-ZEUS.ARPA           4       -37     -39     -38     0
  964.          MOL.ARPA                2       -3      -3      -3      0
  965.  
  966.  
  967. Mills                                                          [Page 17]
  968.  
  969.  
  970.  
  971. RFC 956                                                   September 1985
  972. Algorithms for Synchronizing Network Clocks
  973.  
  974.  
  975.          MUNGO.THINK.COM         4       -1      -1      -1      0
  976.          NETWOLF.ARPA            4       158     157     157     0
  977.          ORBIT.ARPA              3       -4      -5      -4      0
  978.          OSLO-VAX.ARPA           3       3729    3727    3728    1
  979.          PATCH.ARPA              1       18      18      18      0
  980.          RADC-MULTICS.ARPA       4       -14     -15     -14     0
  981.          RICE-ZETA.ARPA          1       -31     -31     -31     0
  982.          RICE.ARPA               1       7       7       7       0
  983.          ROCHESTER.ARPA          4       -18     -18     -18     0
  984.          ROCK.THINK.COM          4       2       2       2       0
  985.          SCRC-QUABBIN.ARPA       4       -100    -100    -100    0
  986.          SCRC-RIVERSIDE.ARPA     4       -128    -128    -128    0
  987.          SCRC-STONY-BROOK.ARPA   4       -100    -100    -100    0
  988.          SCRC-VALLECITO.ARPA     4       -57     -57     -57     0
  989.          SCRC-YUKON.ARPA         4       -65     -65     -65     0
  990.          SEBASTIAN.THINK.COM     4       -14     -15     -14     0
  991.          SEISMO.CSS.GOV          3       -1      -1      0       0
  992.          SRI-BISHOP.ARPA         4       -40     -41     -40     0
  993.          SRI-DARWIN.ARPA         2       -29     -30     -29     0
  994.          SRI-HUXLEY.ARPA         2       -28     -29     -28     0
  995.          SRI-KIOWA.ARPA          4       -29     -30     -29     0
  996.          SRI-LASSEN.ARPA         3       -11     -12     -11     0
  997.          SRI-MENDEL.ARPA         4       74      73      73      0
  998.          SRI-PINCUSHION.ARPA     4       -50     -51     -50     0
  999.          SRI-RITTER.ARPA         4       -23     -24     -23     0
  1000.          SRI-TIOGA.ARPA          4       127     127     127     0
  1001.          SRI-UNICORN.ARPA        4       -38486  -38486  -38486  0
  1002.          SRI-WHITNEY.ARPA        4       -24     -24     -24     0
  1003.          SRI-YOSEMITE.ARPA       4       -26     -27     -26     0
  1004.          SU-AIMVAX.ARPA          2       -54     -55     -54     0
  1005.          SU-COYOTE.ARPA          1       14      14      14      0
  1006.          SU-CSLI.ARPA            4       -1      -1      -1      0
  1007.          SU-PSYCH.ARPA           1       -52     -52     -52     0
  1008.          SU-SAFE.ARPA            1       -60     -60     -60     0
  1009.          SU-SIERRA.ARPA          4       -53     -53     -53     0
  1010.          SU-SUSHI.ARPA           4       -105    -106    -105    0
  1011.          SU-WHITNEY.ARPA         2       -14     -14     -14     0
  1012.          TESLA.EE.CORNELL.EDU    3       -2      -3      -2      0
  1013.          THORLAC.THINK.COM       4       -20     -20     -20     0
  1014.          TRANTOR.ARPA            4       4       3       3       0
  1015.          TZEC.ARPA               4       -6      -7      -6      0
  1016.          UBALDO.THINK.COM        4       -13     -13     -13     0
  1017.          UCI-CIP.ARPA            2       -566    -567    -566    0
  1018.          UCI-CIP2.ARPA           2       -175    -175    -175    0
  1019.          UCI-CIP3.ARPA           2       -89     -90     -89     0
  1020.          UCI-CIP4.ARPA           2       -51     -51     -51     0
  1021.          UCI-CIP5.ARPA           2       -26     -28     -27     1
  1022.  
  1023.  
  1024. Mills                                                          [Page 18]
  1025.  
  1026.  
  1027.  
  1028. RFC 956                                                   September 1985
  1029. Algorithms for Synchronizing Network Clocks
  1030.  
  1031.  
  1032.          UCI-ICSA.ARPA           2       -24     -24     -24     0
  1033.          UCI-ICSC.ARPA           1       0       0       0       0
  1034.          UCI-ICSD.ARPA           1       -24     -24     -24     0
  1035.          UCI-ICSE.ARPA           1       -10     -10     -10     0
  1036.          UDEL-DEWEY.ARPA         1       88      88      88      0
  1037.          UDEL-MICRO.ARPA         2       64      64      64      0
  1038.          UIUC.ARPA               4       105     103     104     0
  1039.          UIUCDCSB.ARPA           4       65      65      65      0
  1040.          UMD1.ARPA               4       0       0       0       0
  1041.          UMICH1.ARPA             4       -1      -1      0       0
  1042.          UO.ARPA                 4       -2      -3      -2      0
  1043.          USC-ISI.ARPA            4       -45     -45     -45     0
  1044.          USC-ISIC.ARPA           4       28      26      27      0
  1045.          USC-ISID.ARPA           4       26      25      25      0
  1046.          USC-ISIE.ARPA           4       -53     -54     -53     0
  1047.          USC-ISIF.ARPA           4       -29     -29     -29     0
  1048.          USGS2-MULTICS.ARPA      3       75      74      74      0
  1049.          UT-ALAMO.ARPA           4       22      22      22      0
  1050.          UT-BARKLEY.ARPA         4       57      56      56      0
  1051.          UT-EMIL.ARPA            4       29      28      28      0
  1052.          UT-GOTTLOB.ARPA         4       42      41      41      0
  1053.          UT-HASKELL.ARPA         4       6       6       6       0
  1054.          UT-JACQUES.ARPA         4       21      20      20      0
  1055.          UT-SALLY.ARPA           3       1       0       0       0
  1056.          VALENTINE.THINK.COM     4       -10     -11     -10     0
  1057.          WENCESLAS.THINK.COM     4       -2      -3      -2      0
  1058.          XAVIER.THINK.COM        4       -14     -14     -14     0
  1059.          XEROX.ARPA              4       0       0       0       0
  1060.          YAXKIN.ARPA             3       -4      -5      -4      0
  1061.          YON.THINK.COM           4       -11     -12     -11     0
  1062.          ZAPHOD.PURDUE.EDU       4       -230    -231    -230    0
  1063.          ZOTZ.ARPA               4       17      16      16      0
  1064.  
  1065.          Table A1. UDP Host Clock Offsets for Various Internet Hosts
  1066.  
  1067.       The above list includes several host clocks known to be
  1068.       synchronized to various radio clocks, including DCN1.ARPA (WWVB),
  1069.       DCN6.ARPA (WWV) and FORD1.ARPA (GOES).  Under normal radio
  1070.       receiving conditions these hosts should be accurate to well within
  1071.       a second relative to NBS standard time.  Certain other host clocks
  1072.       are synchronized to one of these hosts using protocols described
  1073.       in RFC-891, including DCN5.ARPA, DCN7.ARPA and UMD1.ARPA
  1074.       (synchronized to DCN1.ARPA) and UMICH1.ARPA (synchronized to
  1075.       FORD1.ARPA).  It is highly likely, but not confirmed, that several
  1076.       other hosts with low offsets derive local time from one of these
  1077.       hosts or from other radio clocks.
  1078.  
  1079.  
  1080.  
  1081. Mills                                                          [Page 19]
  1082.  
  1083.  
  1084.  
  1085. RFC 956                                                   September 1985
  1086. Algorithms for Synchronizing Network Clocks
  1087.  
  1088.  
  1089.       The raw statistics computed from the weighted data indicate a mean
  1090.       of -261 sec, together with a maximum of 3729 sec and a minimum of
  1091.       -38486 sec.  Obviously, setting a local clock on the basis of
  1092.       these statistics alone would result in a gross error.
  1093.  
  1094.       A closer look at the distribution of the data reveals some
  1095.       interesting features.  Table A2 is a histogram showing the
  1096.       distribution within a few seconds of reference time.  In this and
  1097.       following tables, "Offset" is in seconds and indicates the
  1098.       lower-valued corner of the histogram bin, which extends to the
  1099.       next higher value, while "Count" indicates the number of samples
  1100.       falling in that bin.
  1101.  
  1102.                  Offset  Count           Offset  Count
  1103.                  -------------           -------------
  1104.                  0 sec   13              (continued)  
  1105.                  1       1               -1      3    
  1106.                  2       1               -2      3    
  1107.                  3       2               -3      3    
  1108.                  4       1               -4      2    
  1109.                  5       2               -5      0    
  1110.                  6       1               -6      2    
  1111.                  7       1               -7      1    
  1112.                  8       1               -8      1    
  1113.                  9       0               -9      0    
  1114.                  > 9     30              < -9    95   
  1115.  
  1116.                  Table A2. Offset Distribution < 9 sec
  1117.  
  1118.       A total of 16 of the 163 host clocks are within a second in
  1119.       accuracy, while a total of 125 are off more than ten seconds.  It
  1120.       is considered highly likely that most of the 16 host clocks within
  1121.       a second in offset are synchronized directly or indirectly to a
  1122.       radio clock. Table A3 is a histogram showing the distribution over
  1123.       a larger scale.
  1124.  
  1125.  
  1126.  
  1127.  
  1128.  
  1129.  
  1130.  
  1131.  
  1132.  
  1133.  
  1134.  
  1135.  
  1136.  
  1137.  
  1138. Mills                                                          [Page 20]
  1139.  
  1140.  
  1141.  
  1142. RFC 956                                                   September 1985
  1143. Algorithms for Synchronizing Network Clocks
  1144.  
  1145.  
  1146.                  Offset  Count           Offset  Count
  1147.                  -------------           -------------
  1148.                  0 sec   35              (continued)  
  1149.                  30      3               -30     50   
  1150.                  60      8               -60     42   
  1151.                  90      3               -90     8    
  1152.                  120     1               -120    4    
  1153.                  150     1               -150    2    
  1154.                  180     0               -180    1    
  1155.                  210     0               -210    0    
  1156.                  240     0               -240    1    
  1157.                  270     0               -270    0    
  1158.                  > 270   2               < -270  2    
  1159.  
  1160.                 Table A3. Offset Distribution < 270 sec
  1161.  
  1162.       A total of 138 of the 163 host clocks are within a minute in
  1163.       accuracy, while a total of four host clocks are off more than 4.5
  1164.       minutes.  It is considered likely that most host clocks, with the
  1165.       exception of the 16 identified above as probably synchronized to a
  1166.       radio clock, are set manually by an operator.  Inspection of the
  1167.       raw data shows some hosts to be very far off;  for instance,
  1168.       SRI-UNICORN.ARPA is off more than ten hours.  Note the interesting
  1169.       skew in the data, which show that most host clocks are set slow
  1170.       relative to standard time.
  1171.  
  1172.    A2.  ICMP Timestamp Messages Experiment
  1173.  
  1174.       The the second experiment four ICMP Timestamp messages were sent
  1175.       at about three-second intervals to each of the 1775 hosts and 110
  1176.       gateways listed in the NIC Internet host table.  A total of 1910
  1177.       samples were received from 504 hosts and gateways and compared
  1178.       with a local reference based on a WWVB radio clock, which is known
  1179.       to be accurate to within a few milliseconds.  Support for the ICMP
  1180.       Timestamp messages is optional in the DoD Internet protocol suite,
  1181.       so it is not surprising that most hosts and gateways do not
  1182.       support it.  Moreover, bugs are known to exist in several widely
  1183.       distributed implementations of this feature.  The situation proved
  1184.       an interesting and useful robustness test for the clustering
  1185.       algorithm described in the main body of this note.
  1186.  
  1187.       While the complete table of ICMP offsets by host is too large to
  1188.       reproduce here, the following Tables A4 through A7 show the
  1189.       interesting characteristics of the distribution.  The raw
  1190.       statistics computed from the weighted data indicate a mean of
  1191.       -2.8E+6 msec, together with a maximum of 8.6E+7 msec and a minimum
  1192.       of -8.6E+7 msec.  Setting a local clock on the basis of these
  1193.  
  1194.  
  1195. Mills                                                          [Page 21]
  1196.  
  1197.  
  1198.  
  1199. RFC 956                                                   September 1985
  1200. Algorithms for Synchronizing Network Clocks
  1201.  
  1202.  
  1203.       statistics alone would be ridiculous; however, as described in the
  1204.       main body of this note, use of the clustering algorithm improves
  1205.       the estimate to within 8 msec of the correct value.  The apparent
  1206.       improvement of about six orders in magnitude is so remarkable as
  1207.       to require a closer look at the distributions.
  1208.  
  1209.       The reasons for the remarkable success of the clustering algorithm
  1210.       are apparent from closer examination of the sequence of histograms
  1211.       shown in Tables A4 through A7.  Table A4 shows the distribution in
  1212.       the scale of hours, from which it is evident that 80 percent of
  1213.       the samples lie in a one-hour band either side of zero offset;
  1214.       but, strangely enough, there is a significant dispersion in
  1215.       samples outside of this band, especially in the negative region.
  1216.       It is almost certain that most or all of the latter samples
  1217.       represent defective ICMP Timestamp implementations.  Note that
  1218.       invalid timestamps and those with the high-order bit set
  1219.       (indicating unknown or nonstandard time) have already been
  1220.       excluded from these data.
  1221.  
  1222.                  Offset  Count           Offset  Count
  1223.                  -------------           -------------
  1224.                  0 hr    204             (continued)  
  1225.                  1       10              -1      194  
  1226.                  2       0               -2      0    
  1227.                  3       0               -3      2    
  1228.                  4       0               -4      17   
  1229.                  5       0               -5      10   
  1230.                  6       0               -6      1    
  1231.                  7       0               -7      22   
  1232.                  8       0               -8      20   
  1233.                  9       0               -9      0    
  1234.                  > 9     0               < -9    13   
  1235.  
  1236.               Table A4. ICMP Offset Distribution < 9 hours
  1237.  
  1238.       Table A5 shows the distribution compressed to the range of 4.5
  1239.       minutes.  About half of the 370 samples remaining after the
  1240.       outliers beyond 4.5 minutes are excluded lie in the band 30
  1241.       seconds either side of zero offset, with a gradual tapering off to
  1242.       the limits of the table. This type of distribution would be
  1243.       expected in the case of host clocks set manually by an operator.
  1244.  
  1245.  
  1246.  
  1247.  
  1248.  
  1249.  
  1250.  
  1251.  
  1252. Mills                                                          [Page 22]
  1253.  
  1254.  
  1255.  
  1256. RFC 956                                                   September 1985
  1257. Algorithms for Synchronizing Network Clocks
  1258.  
  1259.  
  1260.                  Offset  Count           Offset  Count
  1261.                  -------------           -------------
  1262.                  0 sec   111             (continued)  
  1263.                  30      25              -30     80   
  1264.                  60      26              -60     28   
  1265.                  90      13              -90     18   
  1266.                  120     7               -120    19   
  1267.                  150     5               -150    9    
  1268.                  180     3               -180    10   
  1269.                  210     3               -210    6    
  1270.                  240     1               -240    2    
  1271.                  270     2               -270    2    
  1272.                  > 270   29              < -270  105  
  1273.  
  1274.               Table A5. ICMP Offset Distribution < 270 sec
  1275.  
  1276.       Table A6 shows the distribution compressed to the range of 27
  1277.       seconds.  About 29 percent of the 188 samples remaining after the
  1278.       outliers beyond 27 seconds are excluded lie in the band 3 seconds
  1279.       either side of zero offset, with a gradual but less pronounced
  1280.       tapering off to the limits of the table.  This type of
  1281.       distribution is consistent with a transition region in which some
  1282.       clocks are set manually and some by some kind of protocol
  1283.       interaction with a reference clock.  A fair number of the clocks
  1284.       showing offsets in the 3-27 second range have probably been set
  1285.       using the UDP Time protocol at some time in the past, but have
  1286.       wandered away as the result of local-oscillator drifts.
  1287.  
  1288.                  Offset  Count           Offset  Count
  1289.                  -------------           -------------
  1290.                  0 sec   32              (continued)  
  1291.                  3       15              -3      22   
  1292.                  6       9               -6      12   
  1293.                  9       6               -9      8    
  1294.                  12      13              -12     8    
  1295.                  15      5               -15     5    
  1296.                  18      8               -18     9    
  1297.                  21      8               -21     7    
  1298.                  24      9               -24     3    
  1299.                  27      6               -27     3    
  1300.                  > 27    114             < -27   202  
  1301.  
  1302.               Table A6. ICMP Offset Distribution < 27 sec
  1303.  
  1304.       Finally, Table A7 shows the distribution compressed to the range
  1305.       of 0.9 second.  Only 30 of the original 504 samples have survived
  1306.       and only 12 of these are within a band 0.1 seconds either side of
  1307.  
  1308.  
  1309. Mills                                                          [Page 23]
  1310.  
  1311.  
  1312.  
  1313. RFC 956                                                   September 1985
  1314. Algorithms for Synchronizing Network Clocks
  1315.  
  1316.  
  1317.       zero offset. The latter include those clocks continuously
  1318.       synchronized to a radio clock, such as the DCNet clocks, some
  1319.       FORDnet and UMDnet clocks and certain others.
  1320.  
  1321.                  Offset  Count           Offset  Count
  1322.                  -------------           -------------
  1323.                  0 sec   6               (continued)  
  1324.                  .1      3               -.1     6    
  1325.                  .2      1               -.2     3    
  1326.                  .3      1               -.3     0    
  1327.                  .4      0               -.4     0    
  1328.                  .5      1               -.5     2    
  1329.                  .6      0               -.6     0    
  1330.                  .7      1               -.7     0    
  1331.                  .8      4               -.8     2    
  1332.                  .9      0               -.9     0    
  1333.                  > .9    208             < -.9   266  
  1334.  
  1335.               Table A7. ICMP Offset Distribution < .9 sec
  1336.  
  1337.      The most important observation that can be made about the above
  1338.       histograms is the pronounced central tendency in all of them, in
  1339.       spite of the scale varying over six orders of magnitude.  Thus, a
  1340.       clustering algorithm which operates to discard outliers from the
  1341.       mean will reliably converge on a maximum-likelihood estimate close
  1342.       to the actual value.
  1343.  
  1344.    A3.  Comparison of UDP and ICMP Time
  1345.  
  1346.       The third experiment was designed to assess the accuracies
  1347.       produced by the various host implementations of the UDP Time
  1348.       protocol and ICMP Timestamp messages.  For each of the hosts
  1349.       responding to the UDP Time protocol in the first experiment a
  1350.       separate test was conducted using both UDP and ICMP in the same
  1351.       test, so as to minimize the effect of clock drift.  Of the 162
  1352.       hosts responding to UDP requests, 45 also responded to ICMP
  1353.       requests with apparently correct time, but the remainder either
  1354.       responded with unknown or nonstandard ICMP time (29) or failed to
  1355.       respond to ICMP requests at all (88).
  1356.  
  1357.       Table A8 shows both the UDP time (seconds) and ICMP time
  1358.       (milliseconds) returned by each of the 45 hosts responding to both
  1359.       UDP and ICMP requests.  The data are ordered first by indicated
  1360.       UDP offset and then by indicated ICMP offset.  The seven hosts at
  1361.       the top of the table are continuously synchronized, directly or
  1362.       indirectly to a radio clock, as described earlier under the first
  1363.  
  1364.  
  1365.  
  1366. Mills                                                          [Page 24]
  1367.  
  1368.  
  1369.  
  1370. RFC 956                                                   September 1985
  1371. Algorithms for Synchronizing Network Clocks
  1372.  
  1373.  
  1374.       experiment.  It is probable, but not confirmed, that those hosts
  1375.       below showing discrepancies of a second or less are synchronized
  1376.       on occasion to one of these hosts.
  1377.  
  1378.          Host                    UDP time        ICMP time
  1379.          -------------------------------------------------
  1380.          DCN6.ARPA               0 sec           0 msec
  1381.          DCN7.ARPA               0               0
  1382.          DCN1.ARPA               0               -6
  1383.          DCN5.ARPA               0               -7
  1384.          UMD1.ARPA               0               8
  1385.          UMICH1.ARPA             0               -21
  1386.          FORD1.ARPA              0               31
  1387.          TESLA.EE.CORNELL.EDU    0               132
  1388.          SEISMO.CSS.GOV          0               174
  1389.          UT-SALLY.ARPA           -1              -240
  1390.          CU-ARPA.CS.CORNELL.EDU  -1              -514
  1391.          UCI-ICSE.ARPA           -1              -1896
  1392.          UCI-ICSC.ARPA           1               2000
  1393.          DCN9.ARPA               -7              -6610
  1394.          TRANTOR.ARPA            10              10232
  1395.          COLUMBIA.ARPA           11              12402
  1396.          GVAX.CS.CORNELL.EDU     -12             -11988
  1397.          UCI-CIP5.ARPA           -15             -17450
  1398.          RADC-MULTICS.ARPA       -16             -16600
  1399.          SU-WHITNEY.ARPA         17              17480
  1400.          UCI-ICSD.ARPA           -20             -20045
  1401.          SU-COYOTE.ARPA          21              21642
  1402.          MIT-MULTICS.ARPA        27              28265
  1403.          BBNA.ARPA               -34             -34199
  1404.          UCI-ICSA.ARPA           -37             -36804
  1405.          ROCHESTER.ARPA          -42             -41542
  1406.          SU-AIMVAX.ARPA          -50             -49575
  1407.          UCI-CIP4.ARPA           -57             -57060
  1408.          SU-SAFE.ARPA            -59             -59212
  1409.          SU-PSYCH.ARPA           -59             -58421
  1410.          UDEL-MICRO.ARPA         62              63214
  1411.          UIUCDCSB.ARPA           63              63865
  1412.          BELLCORE-CS-GW.ARPA     71              71402
  1413.          USGS2-MULTICS.ARPA      76              77018
  1414.          BBNG.ARPA               81              81439
  1415.          UDEL-DEWEY.ARPA         89              89283
  1416.          UCI-CIP3.ARPA           -102            -102148
  1417.          UIUC.ARPA               105             105843
  1418.          UCI-CIP2.ARPA           -185            -185250
  1419.          UCI-CIP.ARPA            -576            -576386
  1420.          OSLO-VAX.ARPA           3738            3739395
  1421.  
  1422.  
  1423. Mills                                                          [Page 25]
  1424.  
  1425.  
  1426.  
  1427. RFC 956                                                   September 1985
  1428. Algorithms for Synchronizing Network Clocks
  1429.  
  1430.  
  1431.          DEVVAX.TN.CORNELL.EDU   3657            3657026
  1432.          PATCH.ARPA              -86380          20411
  1433.          IPTO-FAX.ARPA           -86402          -1693
  1434.          NETWOLF.ARPA            10651435        -62164450
  1435.  
  1436.          Table A8. Comparison of UDP and ICMP Host Clock Offsets
  1437.  
  1438.       Allowing for various degrees of truncation and roundoff abuse in
  1439.       the various implementations, discrepancies of up to a second could
  1440.       be expected between UDP and ICMP time.  While the results for most
  1441.       hosts confirm this, some discrepancies are far greater, which may
  1442.       indicate defective implementations, excessive swapping delays and
  1443.       so forth.  For instance, the ICMP time indicated by UCI-CIP5.ARPA
  1444.       is almost 2.5 seconds less than the UDP time.
  1445.  
  1446.       Even though the UDP and ICMP times indicated by OSLO-VAX.ARPA and
  1447.       DEVVAX.TN.CORNELL.EDU agree within nominals, the fact that they
  1448.       are within a couple of minutes or so of exactly one hour early
  1449.       (3600 seconds) lends weight to the conclusion they were
  1450.       incorrectly set, probably by an operator who confused local summer
  1451.       and standard time.
  1452.  
  1453.       Something is clearly broken in the case of PATCH.ARPA,
  1454.       IPTO-FAX.ARPA and NETWOLF.ARPA.  Investigation of the PATCH.ARPA
  1455.       and IPTO-FAX.ARPA reveals that these hosts were set by hand
  1456.       accidently one day late (-86400 seconds), but otherwise close to
  1457.       the correct time-of-day.  Since the ICMP time rolls over at 2400
  1458.       UT, the ICMP offset was within nominals.  No explanation is
  1459.       available for the obviously defective UDP and ICMP times indicated
  1460.       by NETWOLF.ARPA, although it was operating within nominals at
  1461.       least in the first experiment.
  1462.  
  1463.  
  1464.  
  1465.  
  1466.  
  1467.  
  1468.  
  1469.  
  1470.  
  1471.  
  1472.  
  1473.  
  1474.  
  1475.  
  1476.  
  1477.  
  1478.  
  1479.  
  1480. Mills                                                          [Page 26]
  1481.  
  1482.