rfc957.txt

RFC 相关的技术文档

RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


2.2.  Linear Phase Adjustments

   The correction is introduced as a signed 32-bit integer in
   milliseconds.  If the magnitude of the correction is less than 128
   ms, the low-order 16 bits replaces bits 0-15 in the Clock-Adjust
   register. At suitable intervals, depending on the jitter of the
   intrinsic oscillator, the value of this register is divided by a
   fixed value, forming a quotient which is first added to the Clock
   Register, then subtracted from the Clock-Adjust Register.  This
   technique has several advantages:

      1.  The clock never runs backwards;  that is, successive
          timestamps always increase monotonically.

      2.  In the event of loss of correction information, the clock
          slews to the last correction received.

      3.  The rate of slew is proportional to the magnitude of the last
          correction.  This allows rapid settling in case of large
          corrections, but provides high stability in case of small
          corrections.

      4.  The sequence of computations preserves the highest precision
          and minimizes the propagation of round-off errors.

   Experience has indicated the choice of 256 as appropriate for the
   dividend above, which yields a maximum slew-rate magnitude less than
   0.5 ms per adjustment interval and a granularity of about 2.0
   microseconds, which is of the same order as the intrinsic tolerance
   of the crystal oscillators used in typical clock interfaces.  In the
   case of crystal-derived clocks, an adjustment interval of four
   seconds has worked well, which yields a maximum slew-rate magnitude
   of 125 microseconds per second.  In the case of power-frequency
   clocks or especially noisy links, the greatly increased jitter
   requires shorter adjustment intervals in the range of 0.5 second,
   which yields a maximum slew-rate magnitude of 1.0 ms per second.

   In most cases, independent corrections are generated over each link
   at intervals of 30 seconds or less.  Using the above choices a single
   sample error of 128 ms causes an error at the next sample interval no
   greater than about 7.5 ms with the longer adjustment interval and 30
   ms with the shorter.  The number of adjustment intervals to reduce
   the residual error by half is about 177, or about 12 minutes with the
   longer interval and about 1.5 minutes with the shorter.  This
   completely characterizes the linear dynamics of the mechanism.




Mills                                                           [Page 6]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


2.3.  Nonlinear Phase Adjustments

   When the magnitude of the correction exceeds 128 ms, the possiblity
   exists that the clock is so far out of synchronization with the
   reference host that the best action is an immediate and wholesale
   replacement of Clock Register contents, rather than a graduated
   slewing as described above.  In practice the necessity to do this is
   rare and occurs when the local host or reference host is rebooted,
   for example. This is fortunate, since step changes in the clock can
   result in the clock apparently running backward, as well as incorrect
   delay and offset measurements of the synchronization mechanism
   itself.

   However, it sometimes happens that, due to link retransmissions or
   occasional host glitches, a single correction sample will be computed
   with magnitude exceeding 128 ms.  In practice this happens often
   enough that a special procedure has been incorporated into the
   design.  If a sample exceeding the limit is received, its value is
   saved temporarily and does not affect the Clock-Adjust Register.  In
   addition, a timer is initialized, if not already running, to count
   down to zero in a specified time, currently 30 seconds.

   If the timer is already running when a new correction sample with
   magnitude exceeeding 128 ms arrives, its value and the saved sample
   value are averaged with equal weights to form a new saved sample
   value. If a new correction sample arrives with magnitude less than
   128 ms, the timer is stopped and the saved sample value discarded.
   If the timer counts down to zero, the saved sample value replaces the
   contents of the Clock Register and the Clock-Adjust Register is set
   to zero.  This procedure has the effect that occasional spikes in
   correction values are discarded, but legitimate step changes are
   prefiltered and then used to reset the clock after no more than a
   30-second delay.

3.  Synchronizing Network Clocks

   The algorithms described in the previous section are designed to
   achieve a high degree of accuracy and stability of the logical clocks
   in each participating host.  In this section algorithms will be
   described which synchronize these logical clocks to each other and to
   standard time derived from NBS broadcasts.  These algorithms are
   designed to minimize the cumulative errors using linear synchronizing
   techniques. See [10] for a discussion of algorithms using nonlinear
   techniques.





Mills                                                           [Page 7]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


3.1.  Reference Clocks and Reference Hosts

   The accuracy of the entire network of logical clocks depends on the
   accuracy of the device used as the reference clock.  In the DCnet
   clones the reference clock takes the form of a precision crystal
   oscillator which is synchronized via radio or satellite with the NBS
   standard clocks in Boulder, CO.  The date and time derived from the
   oscillator can be sent continuously or read upon command via a serial
   asynchronous line.  Stand-alone units containing the oscillator,
   synchronizing receiver and controlling microprocessor are available
   from a number of manufacturers.

   The device driver responsible for the reference clock uses its
   serial-line protocol to derive both an "on-time" timestamp relative
   to the logical clock of the reference host and an absolute time
   encoded in messages sent by the clock.  About once every 30 seconds
   the difference between these two quantities is calculated and used to
   correct the logical clock according to the mechanisms described
   previously.  The corrected logical clock is then used to correct all
   other logical clocks in the network.  Note the different
   nomenclature:  The term "reference clock" applies to the physical
   clock itself, while the term "reference host" applies to the logical
   clock of the host to which it is connected. Each has an individual
   address, delay and offset in synchronizing messages.

   There are three different commercial units used as reference clocks
   in DCnet clones.  One of these uses the LF radio broadcasts on 60 KHz
   from NBS radio WWVB, another the HF radio broadcasts on 5, 10 and 15
   MHz from NBS radio WWV or WWVH and the third the UHF broadcasts from
   a GOES satellite.  The WWVB and GOES clocks claim accuracies in the
   one-millisecond range.  The WWV clock claims accuracies in the 100-ms
   range, although actual accuracies have been measured somewhat better
   than that.

   All three clocks include some kind of quality indication in their
   messages, although of widely varying detail.  At present this
   indication is used only to establish whether the clock is
   synchronized to the NBS clocks and convey this information to the
   network routing algorithm as described later.  All clocks include
   some provision to set the local-time offset and propagation delay,
   although for DCnet use all clocks are set at zero offset relative to
   Universal Time (UT).  Due to various uncertaincies in propagation
   delay, serial-line speed and interrupt latencies, the absolute
   accuracy of timestamps derived from a reference host equipped with a
   WWVB or GOES reference clock is probably no better than a couple of
   milliseconds.



Mills                                                           [Page 8]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


3.2.  Distribution of Timing Information

   The timekeeping accuracy at the various hosts in the network depends
   critically on the precision whith which corrections can be
   distributed throughout the network.  In the DCnet design a
   distributed routing algorithm is used to determine minimum-delay
   routes between any two hosts in the net.  The algorithms used, which
   are described in detail in [5] and only in outline form here, provide
   reachability and delay information, as well as clock offsets, between
   neighboring hosts by means of periodic exchanges of routing packets
   called Hello messages. This information is then incorporated into a
   set of routing tables maintained by each host and spread throughout
   the network by means of the Hello messages.

   The detailed mechanisms to accomplish these functions have been
   carefully designed to minimize timing uncertaincies.  For instance,
   all timestamping is done in the drivers themselves, which are given
   the highest priority for resource access.  The mechanism to measure
   roundtrip delays on the individual links is insensitive to the delays
   inherent in the processing of the Hello message itself, as well as
   the intervals between transmissions.  Finally, care is taken to
   isolate and discard transient timing errors that occur when a host is
   rebooted or a link is restarted.

   The routing algorithm uses a table called the Host Table, which
   contains for each host in the network the computed roundtrip delay
   and clock offset, in milliseconds.  In order to separately identify
   each reference clock, if there is more than one in the network, a
   separate entry is used for each clock, as well as each host.  The
   delay and offset fields of the host itself are set to zero, as is the
   delay field of each attached reference clock.  The offset field of
   each attached reference clock is recomputed periodically as described
   above.

   Hello messages containing a copy of the Host Table are sent
   periodically to each neighbor host via the individual links
   connecting them.  In the case of broadcast networks the Hello message
   is broadcast to all hosts sharing the same cable.  The Hello message
   also contains a timestamp inserted at the time of transmission, as
   well as information used to accurately compute the roundtrip delay on
   point-to-point links.

   A host receiving a Hello message processes the message for each host
   in turn, including those corresponding to the reference clocks.  It
   adds the delay field in the message to the previously determined
   roundtrip link delay and compares this with the entry already in its
   Host Table.  If the sum is greater than the delay field in the Host


Mills                                                           [Page 9]



RFC 957                                                   September 1985
Experiments in Network Clock Synchronization


   Table, nothing further is done.  If the sum is less, an update
   procedure is executed.  The update procedure, described in detail in
   [5], causes the new delay to replace the old and the routing to be
   amended accordingly.

   The update procedure also causes a new correction sample to be
   computed as the difference between the timestamp in the Hello message
   and the local clock, which is used to correct the local clock as
   described above.  In addition, the sum of this correction sample plus
   the offset field in the Hello message replaces the offset field in
   the Hello Table.  The effect of these procedures is that the local
   clock is corrected relative to the neighbor clock only if the
   neighbor is on the path of least delay relative to the selected
   reference clock.  If there is no route to the reference clock, as
   determined by the routing algorithm, no corrections are computable
   and the local clock free-runs relative to the last received
   correction.

   As the result of the operation of the routing algorithm, all local
   clocks in the network will eventually stabilize at a constant offset
   relative to the reference clock, depending upon the drift rates of
   the individual oscillators.  For most applications the offset is
   small and can be neglected.  For the most precise measurements the
   computed offset in the Host Table entry associated with any host,
   including the reference clock, can be used to adjust the apparent
   time relative to the local clock of that host.  However, since the
   computed offsets are relatively noisy, it is necessary to smooth them
   using some algorithm depending upon application.  For this reason,
   the computed offsets are provided separately from the local time.

4.  Experimental Validation of the Design

   The original DCnet was established as a "port expander" net connected
   to an ARPAnet IMP in 1978.  It was and is intended as an experimental
   testbed for the development of protocols and measurement of network
   performance.  Since then the DCnet network-layer protocols have
   evolved to include multi-level routing, logical addressing,
   multicasting and time synchronization.  Several DCnet clones have
   been established in the US and Europe and connected to the DARPA
   Internet system.  The experiments described below were performed
   using the DCnet clone at Linkabit East, near Washington, DC, and
   another at Ford Motor Division, near Detroit, MI.  Other clones at
   Ford Aerospace and the Universities of Maryland and Michigan were
   used for calibration and test, while clones at various sites in
   Norway and Germany were used for occasional tests.  Additional




Mills                                                          [Page 10]