rfc956.txt

RFC 相关的技术文档

Algorithms for Synchronizing Network Clocks


                              Mean    Dev     Max     Min
              --------------------------------------------
              Raw data        566     1.8E+7  32750   -143
              C(5,3)          -23     81      14      -69 

              Table 7. LL-GW (a) Majority-Subset Algorithm

                    Size    Mean    Var     Discard
                    -------------------------------
                    1000    566     1.8E+7  32750  
                    990     242     8.5E+6  32726  
                    983     10      1.0E+6  32722  
                    982     -23     231     -143   
                    980     -23     205     -109   
                    970     -22     162     29     
                    960     -23     128     13     
                    940     -23     105     -51    
                    900     -24     89      1      
                    800     -25     49      -9     
                    700     -26     31      -36    
                    600     -26     21      -34    
                    500     -27     14      -20    
                    400     -29     7       -23    
                    300     -30     3       -33    
                    200     -29     1       -27    
                    100     -29     0       -28    
                    1       -29     0       -29    

                Table 8. LL-GW (a) Clustering Algorithm

                              Mean    Dev     Max     Min
             -------------------------------------------- 
             Raw data        378     2.1E+7  32760   -32758
             C(5,3)          -21     1681    329     -212  

              Table 9. LL-GW (b) Majority-Subset Algorithm













Mills                                                          [Page 11]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


                    Size    Mean    Var     Discard
                    -------------------------------
                    1000    377     2.1E+7  -32758 
                    990     315     1.0E+7  32741  
                    981     18      1.1E+6  32704  
                    980     -16     16119   -1392  
                    970     -17     5382    554    
                    960     -21     3338    311    
                    940     -24     2012    168    
                    900     -22     1027    -137   
                    800     -23     430     -72    
                    700     -23     255     -55    
                    600     -22     167     -45    
                    500     -22     109     -40    
                    400     -21     66      -6     
                    300     -18     35      -29    
                    200     -17     15      -23    
                    100     -19     3       -15    
                    50      -21     0       -19    
                    20      -21     0       -21    
                    10      -20     0       -20    
                    1       -20     0       -20    

                Table 10. LL-GW (b) Clustering Algorithm

   The rows of the clustering tables show the result of selected steps
   in the algorithm as it discards samples furthest from the mean.  The
   first twenty steps or so discard samples with gross errors over 30
   seconds.  These samples turned out to be due to a defect in the
   timestamping procedure implemented in the WIDEBAND/EISN gateway code
   which caused gross errors in about two percent of the ICMP Timestamp
   Reply messages.  These samples were left in the raw data as received
   in order to determine how the algorithms would behave in such extreme
   cases.  As apparent from the tables, both the majority-subset and
   clustering algorithms effectively coped with the situation.

   In the statement of the clustering algorithm the terminating
   condition was specified as when only a single sample is left in the
   sample set.  However, it is not necessary to proceed that far.  For
   instance, it is known from the design of the experiment and the
   reference clocks that accuracies better than about ten milliseconds
   are probably unrealistic.  A rough idea of the accuracy of the mean
   is evident from the deviation, computed as the square root of the
   variance. Thus, attempts to continue the algorithm beyond the point
   where the variance drops below 100 or so are probably misguided.
   This occurs when between 500 and 900 samples remain in the sample



Mills                                                          [Page 12]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


   set, depending upon the particular experiment.  Note that in any case
   between 300 and 700 samples fall within ten milliseconds of the final
   estimate, depending on experiment.

   Comparing the majority-subset and clustering algorithms on the basis
   of variance reveals the interesting observation that the result of
   the C(5,3) majority-subset algorithm is equivalent to the clustering
   algorithm when between roughly 900 and 950 samples remain in the
   sample set.  This together with the moderately high variance in the
   ISI-MCON-GW and LL-GW (b) cases suggests a C(6,4) or even C(7,4)
   algorithm might yield greater accuracies.

5.  Summary and Conclusions

   The principles of maximum-likelihood estimation are well known and
   widely applied in communication electronics.  In this note two
   algorithms using these principles are proposed, one based on
   majority-subset techniques appropriate for cases involving small
   numbers of samples and the other based on clustering techniques
   appropriate for cases involving large numbers of samples.

   The algorithms were tested on raw data collected with Internet hosts
   and gateways over ARPANET paths for the purpose of setting a local
   host clock with respect to a remote reference while maintaining
   accuracies in the order of ten milliseconds.  The results demonstrate
   the effectiveness of these algorithms in detecting and discarding
   glitches due to hardware or software failure or operator mistakes.
   They also demonstrate that time synchronization can be maintained
   across the ARPANET in the order of ten milliseconds in spite of
   glitches many times the mean roundtrip delay.

   The results point to the need for an improved time-synchronization
   protocol combining the best features of the ICMP Timestamp message
   [6] and UDP Time protocol [7].  Among the features suggested for this
   protocol are the following:

      1.  The protocol should be based on UDP, which provides the
          flexibility to handle simultaneous, multiplexed queries and
          responses.

      2.  The message format should be based on the ICMP Timestamp
          message format, which provides the arrival and departure times
          at the server and allows the client to calculate the roundtrip
          delay and offset accurately.





Mills                                                          [Page 13]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


      3.  The data format should be based on the UDP Time format, which
          specifies 32-bit time in seconds since 1 January 1900, but
          extended additional bits for the fractional part of a second.

      4.  Provisions to specify the expected accuracy should be included
          along with information about the reference clock or
          synchronizing mechanism, as well as the expected drift rate
          and the last time the clock was set or synchronized.

   The next step should be formulating an appropriate protocol with the
   above features, together with implementation and test in the Internet
   environment.  Future development should result in a distributed,
   symmetric protocol, similar perhaps to those described in [1], for
   distributing highly reliable timekeeping information using a
   hierarchical set of trusted clocks.

6.  References

   1.  Lindsay, W.C., and A.V.  Kantak.  Network synchronization of
       random signals.  IEEE Trans.  Comm.  COM-28, 8 (August 1980),
       1260-1266.

   2.  Mills, D.L.  Time Synchronization in DCNET Hosts.  DARPA Internet
       Project Report IEN-173, COMSAT Laboratories, February 1981.

   3.  Mills, D.L.  DCNET Internet Clock Service.  DARPA Network Working
       Group Report RFC-778, COMSAT Laboratories, April 1981.

   4.  Mills, D.L.  Internet Delay Experiments.  DARPA Network Working
       Group Report RFC-889, M/A-COM Linkabit, December 1983.

   5.  Mills, D.L.  DCN Local-Network Protocols.  DARPA Network Working
       Group Report RFC-891, M/A-COM Linkabit, December 1983.

   6.  Postel, J.  Internet Control Message Protocol.  DARPA Network
       Working Group Report RFC-792, USC Information Sciences Institute,
       September 1981.

   7.  Postel, J.  Time Protocol.  DARPA Network Working Group Report
       RFC-868, USC Information Sciences Institute, May 1983.

   8.  Postel, J.  Daytime Protocol.  DARPA Network Working Group Report
       RFC-867, USC Information Sciences Institute, May 1983.

   9.  Su, Z.  A Specification of the Internet Protocol (IP) Timestamp
       Option.  DARPA Network Working Group Report RFC-781.  SRI
       International, May 1981.


Mills                                                          [Page 14]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks


   10. Marzullo, K., and S.  Owicki.  Maintaining the Time in a
       Distributed System.  ACM Operating Systems Review 19, 3 (July
       1985), 44-54.

   11. Mills, D.L.  Experiments in Network Clock Synchronization.  DARPA
       Network Working Group Report RFC-957, M/A-COM Linkabit, September
       1985.

   12. Mills, D.L.  Network Time Protocol (NTP).  DARPA Network Working
       Group Report RFC-958, M/A-COM Linkabit, September 1985.

Appendix A.

   Experimental Determination of Internet Host Clock Accuracies

   Following is a summary of the results of three experiments designed
   to reveal the accuracies of various Internet host clocks.  The first
   experiment uses the UDP Time protocol, which is limited in precision
   to one second, while the second uses the ICMP Timestamp message,
   which extends the precision to one millisecond.  In the third
   experiment the results indicated by UDP and ICMP are compared.  In
   the UDP Time protocol time is indicated as a 32-bit field in seconds
   past 0000 UT on 1 January 1900, while in the ICMP Timestamp message
   time is indicated as a 32-bit field in milliseconds past 0000 UT of
   each day.

   All experiments described herein were conducted from Internet host
   DCN6.ARPA, which is normally synchronized to a WWV radio clock.  In
   order to improve accuracy during the experiments, the DCN6.ARPA host
   was resynchronized to a WWVB radio clock.  As the result of several
   experiments with other hosts equipped with WWVB and WWV radio clocks
   and GOES satellite clocks, it is estimated that the maximum
   measurement error in the following experiments is less than about 30
   msec relative to standard NBS time determined at the Boulder/Fort
   Collins transmitting sites.

   A1.  UDP Time Protocol Experiment

      In the first experiment four UDP Time protocol requests were sent
      at about three-second intervals to each of the 1775 hosts listed
      in the NIC Internet host table.  A total of 555 samples were
      received from 163 hosts and compared with a local reference based
      on a WWVB radio clock, which is known to be accurate to within a
      few milliseconds.  Not all of these hosts were listed as
      supporting the UDP Time protocol in the NIC Internet host table,
      while some that were listed as supporting this protocol either
      failed to respond or responded with various error messages.


Mills                                                          [Page 15]



RFC 956                                                   September 1985
Algorithms for Synchronizing Network Clocks