rfc1305.txt

RFC 的详细文档！

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 agreement
methods summarized in [LAM85] and [SRI87].

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 [HAL84], the CNV algorithm of [LUN84], the majority-subset
algorithm of [MIL85a], the non-Byzantine algorithm of [RIC88], the
egocentric algorithm of [SCH86], the intersection algorithm of [MAR85]
and [DEC89] 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 [HAL84] and the optimum algorithm of [SRI87].
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. While it
is possible to bound the maximum errors in the time-transfer procedures,
assuming sufficiently generous tolerances are adopted for the hardware
components, this generally results in rather poor accuracies and
stabilities. The approach taken in the NTP design and its predecessors
involves mutually coupled oscillators and maximum-likelihood estimation
and clock-selection procedures, together with a design that allows
provable assertions on error bounds to be made relative to stated
assumptions on the correctness of the primary reference sources. 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 functioning as a phase detector and the local clock as a
disciplined oscillator, but with deterministic error bounds calculated
at each step in the time-transfer process.

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 [LIN80]. The clock filter and
selection algorithms are designed so that the clock synchronization
subnet self-organizes into a hierarchical-master-slave configuration
[MIT80]. With respect to timekeeping accuracy and stability, the
similarity of NTP to digital telephone systems is not accidental, since
systems like this have been studied extensively [LIN80], [BRA80]. What
makes the NTP model unique is the adaptive configuration, polling,
filtering, selection and correctness mechanisms which tailor the
dynamics of the system to fit the ubiquitous Internet environment.

System Architecture

In the NTP model a number of primary reference sources, synchronized by
wire or radio to national standards, are connected to widely accessible
resources, such as backbone gateways, and operated as primary time
servers. The purpose of NTP is to convey timekeeping information from
these servers to other time servers via the Internet and also to cross-
check clocks and mitigate errors due to equipment or propagation
failures. Some number of local-net hosts or gateways, acting as
secondary time servers, run NTP with one or more of the primary servers.
In order to reduce the protocol overhead, the secondary servers
distribute time via NTP to the remaining local-net hosts. In the
interest of reliability, selected hosts can be equipped with less
accurate but less expensive radio clocks and used for backup in case of
failure of the primary and/or secondary servers or communication paths
between them.

Throughout this document a standard nomenclature has been adopted: the
stability of a clock is how well it can maintain a constant frequency,
the accuracy is how well its frequency and time compare with national
standards and the precision is how precisely these quantities can be
maintained within a particular timekeeping system. Unless indicated
otherwise, the offset of two clocks is the time difference between them,
while the skew is the frequency difference (first derivative of offset
with time) between them. Real clocks exhibit some variation in skew
(second derivative of offset with time), which is called drift; however,
in this version of the specification the drift is assumed zero.

NTP is designed to produce three products: clock offset, roundtrip delay
and dispersion, all of which are relative to a selected reference clock.
Clock offset represents the amount to adjust the local clock to bring it
into correspondence with the reference clock. Roundtrip delay provides
the capability to launch a message to arrive at the reference clock at a
specified time. Dispersion represents the maximum error of the local
clock relative to the reference clock. Since most host time servers will
synchronize via another peer time server, there are two components in
each of these three products, those determined by the peer relative to
the primary reference source of standard time and those measured by the
host relative to the peer. Each of these components are maintained
separately in the protocol in order to facilitate error control and
management of the subnet itself. They provide not only precision
measurements of offset and delay, but also definitive maximum error
bounds, so that the user interface can determine not only the time, but
the quality of the time as well.

There is no provision for peer discovery or virtual-circuit management
in NTP. Data integrity is provided by the IP and UDP checksums. No flow-
control or retransmission facilities are provided or necessary.
Duplicate detection is inherent in the processing algorithms. The
service can operate in a symmetric mode, in which servers and clients
are indistinguishable, yet maintain a small amount of state information,
or in client/server mode, in which servers need maintain no state other
than that contained in the client request. A lightweight association-
management capability, including dynamic reachability and variable poll-
rate mechanisms, is included only to manage the state information and
reduce resource requirements. Since only a single NTP message format is
used, the protocol is easily implemented and can be used in a variety of
solicited or unsolicited polling mechanisms.

It should be recognized that clock synchronization requires by its
nature long periods and multiple comparisons in order to maintain
accurate timekeeping. While only a few measurements are usually adequate
to reliably determine local time to within a second or so, periods of
many hours and dozens of measurements are required to resolve oscillator
skew and maintain local time to the order of a millisecond. Thus, the
accuracy achieved is directly dependent on the time taken to achieve it.
Fortunately, the frequency of measurements can be quite low and almost
always non-intrusive to normal net operations.

Implementation Model

In what may be the most common client/server model a client sends an NTP
message to one or more servers and processes the replies as received.
The server interchanges addresses and ports, overwrites certain fields
in the message, recalculates the checksum and returns the message
immediately. Information included in the NTP message allows the client
to determine the server time with respect to local time and adjust the
local clock accordingly. In addition, the message includes information
to calculate the expected timekeeping accuracy and reliability, as well
as select the best from possibly several servers.

While the client/server model may suffice for use on local nets
involving a public server and perhaps many workstation clients, the full
generality of NTP requires distributed participation of a number of
client/servers or peers arranged in a dynamically reconfigurable,
hierarchically distributed configuration. It also requires sophisticated
algorithms for association management, data manipulation and local-clock
control. Throughout the remainder of this document the term host refers
to an instantiation of the protocol on a local processor, while the term
peer refers to the instantiation of the protocol on a remote processor
connected by a network path.

Figure 1<$&fig1> shows an implementation model for a host including
three processes sharing a partitioned data base, with a partition
dedicated to each peer, and interconnected by a message-passing system.
The transmit process, driven by independent timers for each peer,
collects information in the data base and sends NTP messages to the
peers. Each message contains the local timestamp when the message is
sent, together with previously received timestamps and other information
necessary to determine the hierarchy and manage the association. The
message transmission rate is determined by the accuracy required of the
local clock, as well as the accuracies of its peers.

The receive process receives NTP messages and perhaps messages in other
protocols, as well as information from directly connected radio clocks.
When an NTP message is received, the offset between the peer clock and
the local clock is computed and incorporated into the data base along
with other information useful for error determination and peer
selection. A filtering algorithm described in Section 4 improves the
accuracy by discarding inferior data.

The update procedure is initiated upon receipt of a message and at other
times. It processes the offset data from each peer and selects the best
one using the algorithms of Section 4. This may involve many
observations of a few peers or a few observations of many peers,
depending on the accuracies required.

The local-clock process operates upon the offset data produced by the
update procedure and adjusts the phase and frequency of the local clock
using the mechanisms described in Section 5. This may result in either a
step-change or a gradual phase adjustment of the local clock to reduce
the offset to zero. The local clock provides a stable source of time
information to other users of the system and for subsequent reference by
NTP itself.

Network Configurations

The synchronization subnet is a connected network of primary and
secondary time servers, clients and interconnecting transmission paths.
A primary time server is directly synchronized to a primary reference
source, usually a radio clock. A secondary time server derives
synchronization, possibly via other secondary servers, from a primary
server over network paths possibly shared with other services. Under
normal circumstances it is intended that the synchronization subnet of
primary and secondary servers assumes a hierarchical-master-slave
configuration with the primary servers at the root and secondary servers
of decreasing accuracy at successive levels toward the leaves.

Following conventions established by the telephone industry [BEL86], the
accuracy of each server is defined by a number called the stratum, with
the topmost level (primary servers) assigned as one and each level
downwards (secondary servers) in the hierarchy assigned as one greater
than the preceding level. With current technology and available radio
clocks, single-sample accuracies in the order of a millisecond can be
achieved at the network interface of a primary server. Accuracies of
this order require special care in the design and implementation of the
operating system and the local-clock mechanism, such as described in
Section 5.

As the stratum increases from one, the single-sample accuracies
achievable will degrade depending on the network paths and local-clock
stabilities. In order to avoid the tedious calculations [BRA80]
necessary to estimate errors in each specific configuration, it is
useful to assume the mean measurement errors accumulate approximately in
proportion to the measured delay and dispersion relative to the root of
the synchronization subnet. Appendix H contains an analysis of errors,
including a derivation of maximum error as a function of delay and
dispersion, where the latter quantity depends on the precision of the
timekeeping system, frequency tolerance of the local clock and various
residuals. Assuming the primary servers are synchronized to standard
time within known accuracies, this provides a reliable, determistic
specification on timekeeping accuracies throughout the synchronization
subnet.

Again drawing from the experience of the telephone industry, which
learned such lessons at considerable cost [ABA89], the synchronization
subnet topology should be organized to produce the highest accuracy, but
must never be allowed to form a loop. An additional factor is that each
increment in stratum involves a potentially unreliable time server which
introduces additional measurement errors. The selection algorithm used
in NTP uses a variant of the Bellman-Ford distributed routing algorithm
[37] to compute the minimum-weight spanning trees rooted on the primary
servers. The distance metric used by the algorithm consists of the
(scaled) stratum plus the synchronization distance, which itself
consists of the dispersion plus one-half the absolute delay. Thus, the
synchronization path will always take the minimum number of servers to
the root, with ties resolved on the basis of maximum error.

As a result of this design, the subnet reconfigures automatically in a
hierarchical-master-slave configuration to produce the most accurate and
reliable time, even when one or more primary or secondary servers or the
network paths between them fail. This includes the case where all normal
primary servers (e.g., highly accurate WWVB radio clock operating at the
lowest synchronization distances) on a possibly partitioned subnet fail,
but one or more backup primary servers (e.g., less accurate WWV radio
clock operating at higher synchronization distances) continue operation.
However, should all primary servers throughout the subnet fail, the
remaining secondary servers will synchronize among themselves while
distances ratchet upwards to a preselected maximum <169>infinity<170>
due to the well-known properties of the Bellman-Ford algorithm. Upon
reaching the maximum on all paths, a server will drop off the subnet and
free-run using its last determined time and frequency. Since these
computations are expected to be very precise, especially in frequency,
even extended outage periods can result in timekeeping errors not
greater than a few milliseconds per day with appropriately stabilized
oscillators (see Section 5).

In the case of multiple primary servers, the spanning-tree computation
will usually select the server at minimum synchronization distance.
However, when these servers are at approximately the same distance, the
computation may result in random selections among them as the result of
normal dispersive delays. Ordinarily, this does not degrade accuracy as
long as any discrepancy between the primary servers is small compared to
the synchronization distance. If not, the filter and selection
algorithms will select the best of the available servers and cast out
outlyers as intended.

Network Time Protocol

This section consists of a formal definition of the Network Time
Protocol, including its data formats, entities, state variables, events
and event-processing procedures. The specification is based on the
implementation model illustrated in Figure 1, but it is not intended
that this model is the only one upon which a specification can be based.
In particular, the specification is intended to illustrate and clarify
the intrinsic operations of NTP, as well as to serve as a foundation for
a more rigorous, comprehensive and verifiable specification.

Data Formats