rfc1059.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

Network Working Group                                        D. Mills
Request for Comments:  1059                    University of Delaware
                                                            July 1988

                   Network Time Protocol (Version 1)
                    Specification and Implementation

Status of this Memo

   This memo describes the Network Time Protocol (NTP), specifies its
   formal structure and summarizes information useful for its
   implementation.  NTP provides the mechanisms to synchronize time and
   coordinate time distribution in a large, diverse internet operating
   at rates from mundane to lightwave.  It uses a returnable-time design
   in which a distributed subnet of time servers operating in a self-
   organizing, hierarchical master-slave configuration synchronizes
   logical clocks within the subnet and to national time standards via
   wire or radio.  The servers can also redistribute reference time via
   local routing algorithms and time daemons.

   The NTP architectures, algorithms and protocols which have evolved
   over several years of implementation and refinement are described in
   this document.  The prototype system, which has been in regular
   operation in the Internet for the last two years, is described in an
   Appendix along with performance data which shows that timekeeping
   accuracy throughout most portions of the Internet can be ordinarily
   maintained to within a few tens of milliseconds, even in cases of
   failure or disruption of clocks, time servers or nets.  This is a
   Draft Standard for an Elective protocol.  Distribution of this memo
   is unlimited.

                             Table of Contents

   1.      Introduction                                               3
   1.1.    Related Technology                                         4
   2.      System Architecture                                        6
   2.1.    Implementation Model                                       7
   2.2.    Network Configurations                                     9
   2.3.    Time Scales                                               10
   3.      Network Time Protocol                                     12
   3.1.    Data Formats                                              12
   3.2.    State Variables and Parameters                            13
   3.2.1.  Common Variables                                          15
   3.2.2.  System Variables                                          17
   3.2.3.  Peer Variables                                            18
   3.2.4.  Packet Variables                                          19
   3.2.5.  Clock Filter Variables                                    19
   3.2.6.  Parameters                                                20



Mills                                                           [Page 1]

RFC 1059                 Network Time Protocol                 July 1988


   3.3.    Modes of Operation                                        21
   3.4.    Event Processing                                          22
   3.4.1.  Timeout Procedure                                         23
   3.4.2.  Receive Procedure                                         24
   3.4.3.  Update Procedure                                          27
   3.4.4.  Initialization Procedures                                 29
   4.      Filtering and Selection Algorithms                        29
   4.1.    Clock Filter Algorithm                                    29
   4.2     Clock Selection Algorithm                                 30
   4.3.    Variable-Rate Polling                                     32
   5.      Logical Clocks                                            33
   5.1.    Uniform Phase Adjustments                                 35
   5.2.    Nonuniform Phase Adjustments                              36
   5.3.    Maintaining Date and Time                                 37
   5.4.    Calculating Estimates                                     37
   6.      References                                                40

   Appendices
   Appendix A. UDP Header Format                                     43
   Appendix B. NTP Data Format                                       44
   Appendix C. Timeteller Experiments                                47
   Appendix D. Evaluation of Filtering Algorithms                    49
   Appendix E. NTP Synchronization Networks                          56

   List of Figures
   Figure 2.1. Implementation Model                                   8
   Figure 3.1. Calculating Delay and Offset                          26
   Figure 5.1. Clock Registers                                       34
   Figure D.1. Calculating Delay and Offset                          50
   Figure E.1. Primary Service Network                               57

   List of Tables
   Table 2.1. Dates of Leap-Second Insertion                         11
   Table 3.1. System Variables                                       14
   Table 3.2. Peer Variables                                         14
   Table 3.3. Packet Variables                                       15
   Table 3.4. Parameters                                             15
   Table 4.1. Outlyer Selection Procedure                            32
   Table 5.1. Clock Parameters                                       35
   Table C.1. Distribution Functions                                 47
   Table D.1. Delay and Offset Measurements (UMD)                    52
   Table D.2.a Delay and Offset Measurements (UDEL)                  52
   Table D.2.b Offset Measurements (UDEL)                            53
   Table D.3. Minimum Filter (UMD - NCAR)                            54
   Table D.4. Median Filter (UMD - NCAR)                             54
   Table D.5. Minimum Filter (UDEL - NCAR)                           55
   Table E.1. Primary Servers                                        56




Mills                                                           [Page 2]

RFC 1059                 Network Time Protocol                 July 1988


1.  Introduction

   This document describes the Network Time Protocol (NTP), including
   the architectures, algorithms and protocols to synchronize local
   clocks in a set of distributed clients and servers.  The protocol was
   first described in RFC-958 [24], but has evolved in significant ways
   since publication of that document.  NTP is built on the Internet
   Protocol (IP) [10] and User Datagram Protocol (UDP) [6], which
   provide a connectionless transport mechanism;  however, it is readily
   adaptable to other protocol suites.  It is evolved from the Time
   Protocol [13] and the ICMP Timestamp message [11], but is
   specifically designed to maintain accuracy and robustness, even when
   used over typical Internet paths involving multiple gateways and
   unreliable nets.

   The service environment consists of the implementation model, service
   model and time scale described in Section 2.  The implementation
   model is based on a multiple-process operating system architecture,
   although other architectures could be used as well.  The service
   model is based on a returnable-time design which depends only on
   measured offsets, or skews, but does not require reliable message
   delivery.  The subnet is a self-organizing, hierarchical master-slave
   configuration, with synchronization paths determined by a minimum-
   weight spanning tree.  While multiple masters (primary servers) may
   exist, there is no requirement for an election protocol.

   NTP itself is described in Section 3.  It provides the protocol
   mechanisms to synchronize time in principle to precisions in the
   order of nanoseconds while preserving a non-ambiguous date well into
   the next century.  The protocol includes provisions to specify the
   characteristics and estimate the error of the local clock and the
   time server to which it may be synchronized.  It also includes
   provisions for operation with a number of mutually suspicious,
   hierarchically distributed primary reference sources such as radio
   clocks.

   Section 4 describes algorithms useful for deglitching and smoothing
   clock-offset samples collected on a continuous basis.  These
   algorithms began with those suggested in [22], were refined as the
   results of experiments described in [23] and further evolved under
   typical operating conditions over the last two years.  In addition,
   as the result of experience in operating multiple-server nets
   including radio-synchronized clocks at several sites in the US and
   with clients in the US and Europe, reliable algorithms for selecting
   good clocks from a population possibly including broken ones have
   been developed and are described in Section 4.

   The accuracies achievable by NTP depend strongly on the precision of



Mills                                                           [Page 3]

RFC 1059                 Network Time Protocol                 July 1988


   the local clock hardware and stringent control of device and process
   latencies.  Provisions must be included to adjust the software
   logical clock time and frequency in response to corrections produced
   by NTP.  Section 5 describes a logical clock design evolved from the
   Fuzzball implementation described in [15].  This design includes
   offset-slewing, drift-compensation and deglitching mechanisms capable
   of accuracies in order of a millisecond, even after extended periods
   when synchronization to primary reference sources has been lost.

   The UDP and NTP packet formats are shown in Appendices A and B.
   Appendix C presents the results of a survey of about 5500 Internet
   hosts showing how their clocks compare with primary reference sources
   using three different time protocols, including NTP.  Appendix D
   presents experimental results using several different deglitching and
   smoothing algorithms.  Appendix E describes the prototype NTP primary
   service net, as well as proposed rules of engagement for its use.

1.1.  Related Technology

   Other mechanisms have been specified in the Internet protocol suite
   to record and transmit the time at which an event takes place,
   including the Daytime protocol [12], Time Protocol [13], ICMP
   Timestamp message [11] and IP Timestamp option [9].  Experimental
   results on measured times and roundtrip delays in the Internet are
   discussed in [14], [23] and [31].  Other synchronization protocols
   are discussed in [7], [17], [20] and [28].  NTP uses techniques
   evolved from both linear and nonlinear synchronization methodology.
   Linear methods used for digital telephone network synchronization are
   summarized in [3], while nonlinear methods used for process
   synchronization are summarized in [27].

   The Fuzzball routing protocol [15], sometimes called Hellospeak,
   incorporates time synchronization directly into the routing protocol
   design.  One or more processes synchronize to an external reference
   source, such as a radio clock or NTP daemon, and the routing
   algorithm constructs a minimum-weight spanning tree rooted on these
   processes.  The clock offsets are then distributed along the arcs of
   the spanning tree to all processes in the system and the various
   process clocks corrected using the procedure described in Section 5
   of this document.  While it can be seen that the design of Hellospeak
   strongly influenced the design of NTP, Hellospeak itself is not an
   Internet protocol and is unsuited for use outside its local-net
   environment.

   The Unix 4.3bsd model [20] uses a single master time daemon to
   measure offsets of a number of slave hosts and send periodic
   corrections to them.  In this model the master is determined using an
   election algorithm [25] designed to avoid situations where either no



Mills                                                           [Page 4]

RFC 1059                 Network Time Protocol                 July 1988


   master is elected or more than one master is elected.  The election
   process requires a broadcast capability, which is not a ubiquitous
   feature of the Internet.  While this model has been extended to
   support hierarchical configurations in which a slave on one network
   serves as a master on the other [28], the model requires handcrafted
   configuration tables in order to establish the hierarchy and avoid
   loops.  In addition to the burdensome, but presumably infrequent,
   overheads of the election process, the offset measurement/correction
   process requires twice as many messages as NTP per update.

   A good deal of research has gone into the issue of maintaining
   accurate time in a community where some clocks cannot be trusted.  A
   truechimer is a clock that maintains timekeeping accuracy to a
   previously published (and trusted) standard, while a falseticker is a
   clock that does not.  Determining whether a particular clock is a
   truechimer or falseticker is an interesting abstract problem which
   can be attacked using methods summarized in [19] and [27].

   A convergence function operates upon the offsets between the clocks
   in a system to increase the accuracy by reducing or eliminating
   errors caused by falsetickers.  There are two classes of convergence
   functions, those involving interactive convergence algorithms and
   those involving interactive consistency algorithms.  Interactive
   convergence algorithms use statistical clustering techniques such as
   the fault-tolerant average algorithm of [17], the CNV algorithm of
   [19], the majority-subset algorithm of [22], the egocentric algorithm
   of [27] and the algorithms in Section 4 of this document.

   Interactive consistency algorithms are designed to detect faulty
   clock processes which might indicate grossly inconsistent offsets in
   successive readings or to different readers.  These algorithms use an
   agreement protocol involving successive rounds of readings, possibly
   relayed and possibly augmented by digital signatures.  Examples
   include the fireworks algorithm of [17] and the optimum algorithm of
   [30].  However, these algorithms require large numbers of messages,
   especially when large numbers of clocks are involved, and are
   designed to detect faults that have rarely been found in the Internet
   experience.  For these reasons they are not considered further in
   this document.

   In practice it is not possible to determine the truechimers from the
   falsetickers on other than a statistical basis, especially with
   hierarchical configurations and a statistically noisy Internet.
   Thus, the approach taken in this document and its predecessors
   involves mutually coupled oscillators and maximum-likelihood
   estimation and selection procedures.  From the analytical point of
   view, the system of distributed NTP peers operates as a set of
   coupled phase-locked oscillators, with the update algorithm



Mills                                                           [Page 5]

RFC 1059                 Network Time Protocol                 July 1988


   functioning as a phase detector and the logical clock as a voltage-
   controlled oscillator.  This similarity is not accidental, since
   systems like this have been studied extensively [3], [4] and [5].

   The particular choice of offset measurement and computation procedure
   described in Section 3 is a variant of the returnable-time system
   used in some digital telephone networks [3].  The clock filter and