rfc957.txt

RFC 相关的技术文档

Network Working Group                                         D.L. Mills
Request for Comments: 957                               M/A-COM Linkabit
                                                          September 1985

              Experiments in Network Clock Synchronization


Status of this Memo

   This RFC discusses some experiments in clock synchronization in the
   ARPA-Internet community, and requests discussion and suggestions for
   improvements.  Distribution of this memo is unlimited.

Table of Contents

   1.      Introduction
   2.      Design of the Synchronization Algorithm
   2.1.    The Logical Clock
   2.2.    Linear Phase Adjustments
   2.3.    Nonlinear Phase Adjustments
   3.      Synchronizing Network Clocks
   3.1.    Reference Clocks and Reference Hosts
   3.2.    Distribution of Timing Information
   4.      Experimental Validation of the Design
   4.1.    Experiment Design
   4.2.    Experiment Execution
   4.3.    Discussion of Results
   4.3.1.  On Power-Grid Clocks
   4.3.2.  On Clocks Synchronized via Network Links
   4.3.3.  On the Accuracy of Radio Clocks
   4.3.3.1. The Spectracom 8170 WWVB Radio Clock
   4.3.3.2. The True Time 468-DC GOES Radio Clock
   4.3.3.3. The Heath GC-1000 WWV Radio Clock
   4.3.4.  On Handling Disruptions
   4.4.    Additional Experiments
   5.      Summary and Conclusions
   6.      References

List of Figures

   Figure 1. Clock Registers
   Figure 2. Network Configuration











Mills                                                           [Page 1]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


List of Tables

   Table 1. Experiment Hosts
   Table 2. Link Measurements
   Table 3. First Derivative of Delay
   Table 4. GOES Radio Clock Offsets
   Table 5. WWV Radio Clock Offsets
   Table 6. ISI-MCON-GW Clock Statistics
   Table 7. LL-GW Clock Statistics
   Table 8. LL-GW Clock Statistics

1.  Introduction

   One of the services frequently neglected in computer network design
   is a high-quality, time-of-day clock capable of generating accurate
   timestamps with small residual errors compared to intrinsic one-way
   network delays.  Such a service would be useful for tracing the
   progress of complex transactions, synchronizing cached data bases,
   monitoring network performance and isolating problems.

   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], [10] and [11].
   Experimental results on measured roundtrip delays in the Internet are
   discussed in [4].  A comprehensive mathematical treatment of clock
   synchronization can be found in [1].

   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].  Issues on time
   synchronization are discussed in [4] and synchronization algorithms
   in [2] and [5].  Experimental results on measured roundtrip delays in
   the Internet are discussed in [2].  A comprehensive mathematical
   treatment of the subject can be found in [1], while an interesting
   discussion on mutual-synchonization techniques can be found in [10].

   There are several ways accurate timestamps can be generated.  One is
   to provide at every service point an accurate, machine-readable clock
   synchronized to a central reference, such as the National Bureau of
   Standards (NBS).  Such clocks are readily available in several models
   ranging in accuracies of a few hundred milliseconds to less than a


Mills                                                           [Page 2]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


   millisecond and are typically synchronized to special ground-based or
   satellite-based radio broadcasts.  While the expense of the clocks
   themselves, currently in the range $300 to $3000, can often be
   justified, all require carefully sited antennas well away from
   computer-generated electromagnetic noise, as well as shielded
   connections to the clocks.  In addition, these clocks can require a
   lengthy synchonization period upon power-up, so that a battery-backup
   power supply is required for reliable service in the event of power
   interruptions.

   If the propagation delays in the network are stable or can be
   predicted accurately, timestamps can be generated by a central
   server, equipped with a clock such as described above, in response to
   requests from remote service points.  However, there are many
   instances where the trans-network delay to obtain a timestamp would
   be intolerable, such as when timestamping a message before
   transmission.  In addition, propagation delays are usually not
   predictable with precisions in the order required, due to
   probabilistic queuing and channel-contention delays.

   In principle, a clock of sufficient accuracy can be provided at each
   service point using a stable, crystal-controlled clock which is
   corrected from time to time by messages from a central server.
   Suitable inexpensive, crystal-controlled clock interfaces are
   available for virtually any computer.  The interesting problem
   remaining is the design of the synchronization algorithm and protocol
   used to transmit the corrections.  In this document one such design
   will be described and its performance assessed.  This design has been
   incorprated as an integral part of the network routing and control
   protocols of the Distributed Computer Network (DCnet) architecture
   [5], clones of which have been established at several sites in the US
   and Europe.  These protocols have been in use since 1979 and been
   continuously tested and refined since then.

2.  Design of the Synchronization Algorithm

   The synchronization algorithm is distributed in nature, with protocol
   peers maintained in every host on the network.  Peers communicate
   with each other on a pairwise basis using special control messages,
   called Hello messages, exchanged periodically over the ordinary data
   links between them.  The Hello messages contain information necessary
   for each host to calculate the delay and offset between the local
   clock of the host and the clock of every other host on the network
   and are also used to drive the routing algorithm.

   The synchronization algorithm includes several features to improve
   the accuracy and stability of the local clock in the case of host or


Mills                                                           [Page 3]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


   link failures.  In following sections the design of the algorithm is
   summarized.  Full design details are given in [5] along with a formal
   description of the Hello protocol.

2.1.  The Logical Clock

   In the DCnet model each service point, or host, is equipped with a
   hardware clock, usually in the form of an off-the-shelf interface.
   Using this and software registers, a logical clock is constructed
   including a 48-bit Clock Register, which increments at a 1000 Hz
   rate, a 32-bit Clock-Adjust Register, which is used to slew the Clock
   Register in response to raw corrections received over the net, and a
   Counter Register, which is used in some interface designs as an
   auxilliary counter.  The configuration and decimal point of these
   registers are shown in Figure 1.

           Clock Register                                   

           0               16               32              
           +---------------+---------------+---------------+
           |               |               |               |
           +---------------+---------------+---------------+
                                           A                
                                     decimal point          

           Clock-Adjust Register                            

                           0               16               
                           +---------------+---------------+
                           |               |               |
                           +---------------+---------------+
                                           A                
                                     decimal point          

           Counter Register                                 

                           0              16                
                           +---------------+                
                           |               |                
                           +---------------+                
                                           A                
                                     decimal point          

                       Figure 1. Clock Registers

   The Clock Register and Clock-Adjust Register are implemented in
   memory.  In typical clock interface designs such as the DEC KMV11-A


Mills                                                           [Page 4]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


   the Counter Register is implemented in the interface as a buffered
   counter driven by a crystal oscillator.  A counter overflow is
   signalled by an interrupt, which results in an increment of the Clock
   Register at bit 15 and the propagation of carries as required.  The
   time of day is determined by reading the Counter Register, which does
   not disturb its counting process, and adding its value to that of the
   Clock Register with decimal points aligned.

   In other interface designs such as the simple LSI-11 event-line
   mechanism, each tick of the clock is signalled by an interrupt at
   intervals of 10, 16-2/3 or 20 ms, depending on interface and clock
   source.  When this occurs the appropriate number of milliseconds,
   expressed to 32 bits in precision, is added to the Clock Register
   with decimal points aligned.

   It should be noted at this point that great care in operating system
   design is necessary in order to preserve the full accuracy of
   timestamps with respect to the application program, which must be
   protected from pre-emption, excessive device latencies and so forth.
   In addition, the execution times of all sequences operating with the
   interrupt system disabled must be strictly limited.  Since the PDP11
   operating system most often used in the DCnet (the "Fuzzball"
   operating system) has been constructed with these considerations
   foremost in mind, it has been especially useful for detailed network
   performance testing and evaluation.  Other systems, in particular the
   various Unix systems, have not been found sufficiently accurate for
   this purpose.

   Left uncorrected, the host logical clock runs at the rate of its
   intrinsic oscillator, whether derived from a crystal or the power
   frequency.  The correction mechanism uses the Clock-Adjust Register,
   which is updated from time to time as raw corrections are received.
   The corrections are computed using roundtrip delays and offsets
   derived from the routing algorithm, described later in this document,
   which are relatively noisy compared to the precision of the logical
   clock.  A carefully designed smoothing mechansim insures stability,
   as well as isolation from large transients that occur due to link
   retransmissions, host reboots and similar disruptions.











Mills                                                           [Page 5]