@TITLE = A Comparison of Certain Timekeeping Systems and the Network
Time Protocol<$FSponsored by: Defense Advanced Research Projects Agency
under NASA Ames Research Center contract number NAG 2-638 and National
Science Foundation grant number NCR-89-13623.>

@AUTHOR = David L. Mills
Electrical Engineering Department
University of Delaware
25 March 1991

@AUTHOR = Abstract

@ABSTRACT = This document describes and compares three timekeeping
systems in objectives, architecture and design. These systems are:
Digital Time Synchronization Service (DTSS), Probabilistic Clock
Synchronization (PCS) and Network Time Protocol (NTP), which have been
submitted to the standards bodies as the basis of an international
standard. Each of the three can be used to synchronize local clocks in a
computer network with distributed and diversified services.

Author's note: This document is a preliminary draft and is subject to
change before publication in final form. It is intended for
informational purposes and used only in connection with professional
activities. Please do not cite this document in any publication and do
not redistribute it without this notice.

@HEAD LEVEL 1 =  Introduction

This report discusses the scope, application and function of three
network time-synchronization architectures and protocols with respect to
possible standards activities. These include the Distributed Time
Synchronization Service (DTSS) described in [DEC89], the Probabilistic
Clock Synchronization (PCS) described in [CRI89b] and the Network Time
Protocol (NTP) described in [MIL90b]. A document [ISO90] has been
submitted to the ISO Working Group JTC1/SC21/WG7 proposing DTSS for
consideration. Another document [CCI90] has been submitted to the CCITT
Study Group VII proposing NTP for consideration. In addition, it is
expected that PCS will also become a candidate for consideration. It may
be that one of these three architectures will eventually be selected for
ISO/CCITT standardization or some other architecture synthesized from
one or more of them.

In most developed nations time is considered a metricated, civil
constant, disseminated by national means, coordinated by international
agreement and intended for ubiquitous, free access. Today, the
timekeeing systems of most countries are coordinated with Coordinated
Universal Time (UTC), which is maintained by cooperative agreement using
astronomical observations. Users of computer network applications expect
local clocks to be synchronous with UTC with acceptable accuracy,
stability and reliability.

As will be evident from later discussion, there are wide variations in
the perceived requirements and expectations of the three timekeeping
systems considered in this report; however, each of these systems shares
the common goal of providing accurate, stable and reliable local clocks.
In the following  the accuracy of a clock is how well its time compares
with a designated reference clock or national standard, the stability is
how well it can maintain a constant frequency and the precision is to
what degree time can be resolved in a particular timekeeping system. The
offset of two clocks is the time difference between them, while the skew
is the frequency difference between them. The reliability of a
timekeeping system is the fraction of the time it can be kept operating
and providing correct time with respect to stated stability and accuracy
tolerances.

@HEAD LEVEL 1 =  Time Synchronization Systems
An important feature of a computer network providing distributed
services is the capability to synchronize the local clocks of the
various processors in the network. This capability can be provided by a
timekeeping system consisting of time servers (called masters in PCS) in
the form of dedicated or shared processors which exchange timing
messages between themselves and provide timing information to the
clients (called clerks in DTSS and slaves in PCS) of the network
population. Many applications needing time synchronization also need to
coordinate local time with standard time as disseminated from national
standards laboratories via radio, telephone or satellite. This can be
done by connecting some servers to a designated reference clock or
national standard, called a primary clock. The servers connected to
primary clocks are designated primary servers; others that may depend on
them are designated secondary servers. The secondary servers are clients
of the primary servers and may themselves serve a client population
including other secondary servers.

It is generally considered impractical to equip every processor with a
primary clock such as a radio timecode receiver or telephone modem;
therefore, a timekeeping system will usually employ one or more primary
clocks and provide synchronization using a synchronization protocol such
as DTSS, PCS or NTP. Using the protocol, servers and clients exchange
timing messages at intervals depending on the accuracy required.
Information in these messages can also used to determine reachability
between the servers and to organize the set of servers and clients as a
hierarchical synchronization subnet. Each client or server selects a set
of servers or peers from within the subnet population on the basis of
accuracy, stability and reliability. In order to assure reliability, at
least three peers operating over disjoint network paths are required. In
some systems the selection of peers is engineered prior to operation;
while, in others, the selection can be automated.

Since time is ubiquitous, it may develop that most or all computers in a
network or internet will be members of the synchronization subnet, so
there is some question as to the ability of the synchronization protocol
to scale up in the number of servers and clients in the subnet. There
are of course natural boundaries imposed by administrative, legal and
political constraints and these impose natural boundaries on topology
and reachability. However, there are other boundaries imposed by
technical reasons, such as the quality and utilization of transmission
links, the speed of the processors and so forth.

For the highest accuracy it is usually desirable to implant the
synchronization protocol at the lower protocol layers of the reference
model. While the particular layer is not stated in PCS, both DTS and NTP
are implemented at at the transport layer and operated in connectionless
mode. Therefore, the protocol itself must provide protection from lost
or duplicate messages and determine whether its peers are reachable for
the purposes of synchronization. A lightweight association-management
capability, including directory cacheing, dynamic reachability, peer
selection and variable message-interval mechanisms, can be used to
manage state information and reduce resource requirements, as in PCS and
NTP. Optional features may include message authentication based on
crypto-checksums, as in NTP, and provisions for remote management, as in
DTSS and NTP.

In typical systems one or more primary servers synchronize directly to
primary clocks, such as timecode receivers (called time providers in
DTSS). Secondary time servers synchronize to the primary servers and
others in the synchronization subnet. A typical subnet is shown in
Figure 1a<$&fig1>, in which the nodes represent subnet servers, with
normal level numbers determined by the hop count to the root, and the
heavy lines the active synchronization paths and direction of timing
information flow. The light lines represent backup synchronization paths
where timing and reachability information is exchanged, but not
necessarily used to synchronize the local clocks. Figure 1b shows the
same subnet, but with the line marked x out of service. The subnet has
re-configured itself automatically to use backup paths, with the result
that one of the servers has dropped from level 2 to level 3.

Figure 2<$&fig2> shows the overall organization of a typical
synchronization client, although some architectures do not incorporate
all the components shown. Timestamps exchanged between the client and
possibly several subnet peers are used to determine the offsets between
the client clock and each peer clock, as well as other data necessary to
compute error bounds inherited from the peers and servers along the
synchronization paths to the primary servers.

In some systems the data for each peer are processed by the data-filter
algorithm separately to reduce incidental timing noise. The filter
algorithm selects from among the last several samples the one with
presumed minimum error as its output. Then, the peer-selection algorithm
determines from among all peers a suitable subset of peers capable of
providing the most accurate and dependable time. The particular
algorithm used and the rationale for its design are crucial to the
accuracy, stability and reliability of the timekeeping system. Various
systems use either or both of two algorithms, one a version of an
algorithm proposed by Marzullo and Owicki [MAR85] and the other based on
maximum likelihood principles.

The selection algorithm provides both a combined clock offset and a
confidence interval over which this offset can be considered valid. In
some systems the combined offset is determined as the midpoint of the
confidence interval, while in others it is computed by a weighted-
average procedure designed to improve accuracy. Finally, the combined
offset is processed by a phase-lock loop (PLL). In the PLL the combined
effects of the filtering, selection and combining operations are to
produce a phase-correction term, which is processed by the loop filter
to control the local clock, which functions as a voltage-controlled
oscillator (VCO). The VCO furnishes the timing (phase) reference to
produce the timestamps used in all timing calculations.

The various systems incorporate different PLL models based on
assumptions of the accuracy and stability required. A type-I PLL can
correct for time offset, but not frequency offset; therefore, it
requires periodic corrections depending on the intrinsic frequency
offset and accuracy required. A type-II PLL can correct for both time
and frequency offsets, but requires an initial interval or training in
order to stabilize the frequency-offset data. A type-II PLL can
significantly reduce the message rate and increase the accuracy during
possibly lengthy periods when contact with all servers is lost. However,
real clocks exhibit some degree of instability as the result of aging,
environmental changes, etc., so the improvement in performance using a
type-II PLL is limited. These issues are discussed in further detail in
a later section of this document.

Clock offsets are computed using some form of the scheme illustrated in
Figure 3<$&fig3>, shows how timestamps are numbered and exchanged
between peers A and B. Let <$ET sub i>, <$ET sub {i-1}>, <$ET sub {i-
2}>, <$ET sub {i-3}> be the values of the four most recent timestamps as
shown and let <$Ea~=~T sub {i-2}~-~T sub {i-3}> and <$Eb~=~T sub {i-1}~-
~T sub i>. Then, the roundtrip delay <$Edelta> and clock offset
<$Etheta> of B relative to A at time <$ET sub i> are:

@CENTER = <$Edelta~=~a~-~b~~~~ and ~~~~theta~=~{a~+~b} over 2> .

In NTP each message includes the latest three timestamps <$ET sub {i-
1}>, <$ET sub {i-2}> and <$ET sub {i-3}>, while the fourth timestamp
<$ET sub i> is determined upon arrival of the message. Thus, both peers
can independently calculate delay and offset using a single
bidirectional message stream and cross-check each other, as well as
quickly reconfigure should other servers or network paths fail. Since
the latest timestamps recorded at the server are included in its message
and no more than one message to the same peer can be sent during a
single clock tick, this scheme provides inherent protection against
message loss or duplication.

In PCS a request message sent by a client (slave) to a server (master)
includes the <$ET sub {i-3}> timestamp, which is returned by the server
in its reply and used as a unique message identifier in the same way as
NTP. Since a master is expected to reply immediately upon receipt of a
request, the client computes the time offset by simply adding one-half
the measured delay to the master time included in the reply.

In DTSS a request message sent by a client (clerk) to a server does not
include the <$ET sub {i-3}> timestamp; however, all DTSS messages
include a 64-bit sequence number (message ID) which can be used to match
replies to requests. A server reply includes the quantity and <$ET sub
{i-1}~-~T sub {i-2}>, which is the interval from when the server
received the request and when it transmitted the reply at <$ET sub {i-
1}>. While this scheme accommodates cases where a server deliberately
delays its reply, possibly due to congestion or load-balancing, it is
not symmetric and imposes a deliberate hierarchy which may not be
desirable in all cases.

In both DTSS, PCS and NTP (version 3) the errors are minimized by the
control-feedback design shown in Figure 2. In practice, errors due to
stochastic network delays usually dominate; however, it is not usually
possible to characterize network delays as a stationary random process,
since network queues can grow and shrink in chaotic fashion and arriving
customer traffic is frequently bursty.

Nevertheless, it is a simple exercise to calculate bounds on network
errors as a function of measured delay. The true offset of B relative to
A is called <$Etheta> in Figure 3. Let x denote the actual delay between
the departure of a message from A and its arrival at B. Therefore,
<$Ex~+~theta~=~T sub {i-2}~-~T sub {i-3}~==~a>. Since x must be positive
in our universe, <$Ex~=~a~-~theta~>>=~0>, which requires
<$Etheta~<<=~a>. A similar argument requires that <$Eb~<<=~theta>, so
surely <$Eb~<<=~theta~<<=~a>. This inequality can also be expressed

@CENTER = <$Eb~=~{a~+~b} over 2~-~{a~-~b} over 2~<<=~theta~<<=~{a~+~b}
over 2~+~{a~-~b} over 2~=~a> ,

which is equivalent to

@CENTER = <$Etheta~-~delta over 2~<<=~theta hat~<<=~theta~+~delta over
2> .

In other words, the true clock offset <$Etheta hat> must lie in a
confidence interval of size equal to the measured delay and centered
about the measured offset. This interval is called the inaccuracy
interval in DTSS. In PCS it is used as a filter to discard samples above
a given threshold in order to bound the error.

Real systems are subject to stochastic errors due to local clock
resolution and stability. If these errors can be bounded by design and
manufacture to specific tolerances, then it is possible to calculate
their affect on the confidence interval. All three timekeeping systems
include provisions to calculate these bounds as a byproduct of normal
synchronization activities and include their contribution in the
resulting error bounds provided to the user. In DTSS this is done
explicitly as part of the architecture of the clerk-user interface.

Since NTP is based on a hierarchical subnet topology, provisions are
necessary to calculate the effects of all errors accumulated on the
synchronization path to the primary clock, including the effect of all
servers, local clocks and the primary clock itself. In addition, one of
the requirements placed on NTP is the ability to calculate not only the
clock offset, but the roundtrip delay and error bound to each peer. This
requirement arises from the perceived user needs to control the
departure of a message to arrive at a peer at a designated time. For
this reason the delay calculation and the error-bound calculation are
kept separate and accumulate separately along the synchronization path
to the primary clock.

@HEAD LEVEL 1 =  Issues and Discussion

The preceding overview should provide some insight on the architectures,
protocols and algorithms adopted by the DTSS, PCS and NTP timekeeping
systems. However, there are important issues which characterize the
design approach in the three systems which need to be addressed in
further detail. The following sections address some of the most
important of them.

@HEAD LEVEL 2 =  Frequency Compensation

The NTP local-clock model includes the capability to estimate the
intrinsic frequency of the local oscillator and compensate for its error
with respect to standard time as distributed via the synchronization
subnet. This section contains an overview of the issues and rationale
for the inclusion of this feature. It should be pointed out that nothing
in the NTP local-clock algorithm design precludes its adaptation to
other timekeeping systems.

NTP uses a type-II PLL designed to stabilize time and frequency offset
and automatically adjust the message rate and error bounds based on
observed timing noise and clock stability. The various design parameters
were determined using a mathematical model and verified both by
simulation and measurement in several implementations. While not
identified explicitly as such, the PCS self-adjusting, logical-clock
scheme is in fact a type-II PLL. The DTSS design uses a type-I PLL
stating as rationale (private communication) its increased complexity
and vulnerability to mis-implement.

An oscillator is characterized by its frequency tolerance and stability.
A tolerance specification is usually in terms of a maximum frequency
deviation with respect to a calibrated source. Typical values range from
10-5 for an uncompensated quartz-crystal oscillator to 10-12 for a
cesium-beam oscillator. A stability specification is usually in terms of
a maximum frequency change over a specified interval. Typical values
range from 1-7 per day for an quartz oscillator to 10-12 per year for a
cesium oscillator. However, quartz oscillators also exhibit an aging
effect which varies from unit to unit and can result in a long term
gradual frequency change as much as 10-5 per year. In addition, quartz
oscillators without temperature compensation or control exhibit
frequency variations dependent on ambient temperature of about 10-6 per
degree Celsius.

The main reason to be concerned about tolerance and stability is the
message rate necessary to keep a local clock within a specified
accuracy. For instance, if a local clock is to be synchronized to within
a millisecond and has an oscillator with a frequency offset of 10-5, it
must be updated at least once every couple of minutes. If this
oscillator is allowed to run for a day without outside correction, it
will be in error by almost a second. On the other hand, if its
particular intrinsic frequency can be estimated and corrected by some
means, the intervals between corrections can be considerably increased.
This feature has considerable practical benefits in cases where servers
dispense time to several hundred clients, as is now the case with many
Internet NTP primary servers.

While there are considerable advantages in using frequency estimates,
there are limits imposed by the intrinsic stability of the local-clock
oscillator, which is usually not temperature compensated. Measurements
made with workstations and mainframe computers located in typical office
environments show some oscillators with intrinsic frequency errors over
one second, but with stability after frequency compensation often less
than 10-7 per day; however, these data may vary somewhat between various
equipments and locations. With accurate frequency compensation and
stabilities in this order, message rates can in principle be reduced to
about one in about three hours to maintain millisecond accuracy.

In the NTP design considerable attention was paid to the issue of how to
optimize the performance in the face of widely varying tolerance and
stability specifications without requiring specific design configuration
for each individual oscillator. The particular design adopted, called an
adaptive-parameter, type-II, phase-lock loop (PLL) has the capability to
automatically sense the in-operation stability regime of the local
oscillator and then adjust the PLL characteristics (bandwidth) and
message intervals accordingly. The design has been tested using many
types of equipment using compensated and uncompensated quartz
oscillators, as well as cesium oscillators.

@HEAD LEVEL 2 =  Reliability

One thing learned while developing timekeeping technology is the
overwhelming importance of reliability. Many papers and articles have
been written on this issue with profound theoretical and practical
implications. Typical methods are based on the availability of a number
of peers, together with an algorithm that seeks a subset of greater than
half of them which satisfy some convergence criterion.

For the purposes of this discussion, the reliability of the timekeeping
system refers to its ability to sustain peer connectivity and
synchronization in the face of service interruptions on the servers or
links between them. Both DTSS, PCS and NTP explicitly address this point
using the principles of redundancy and diversity. A highly redundant
system employs multiple servers at each level of the hierarchy, while a
highly diverse system employs multiple disjoint peer paths with few
common points of failure. Experience in the Internet shows that these
features are necessary and vital in order to provide reliable and
trustable time.

However, along with the issues of redundancy and diversity go the issues
of how to make efficient use of the multiple assets required and here
the proposed systems differ somewhat. In the DTSS model timekeeping
service clients on a LAN or extended LAN send periodic requests to a
subset of a set of time servers registered in a well-known directory
service, selecting the members of the subset at random for each round.
Local time servers periodically exchange timing information with each
other and, optionally, with global time servers presumably in an
extended WAN. If all local servers are lost, a clerk can directly poll a
member of a configured global set.

In NTP the synchronization subnet peers exchange messages over paths
which are independently configured. This establishes the topology of the
subnet, over which messages are sent continuously, although usually at
relatively long intervals. Using a distance measure based on maximum-
likelihood estimates of roundtrip delay and total error accumulated at
each level of server from the primary reference source, a subset of
presumed accurate and stable peers is selected and their readings
combined on the basis of distance. While the subnet topology must be
engineered on the basis of anticipated physical interconnectivity, the
actual topology formed by the system results in the lowest distance and
thus lowest error at each level.

The approach followed in DTSS utilizes an algorithm due to Marzullo and
Owicki, in which an interval called the inaccuracy interval is
associated with the apparent clock value for each peer. The algorithm
strives to find the smallest interval containing the most peers, while
discarding peers whose intervals are disjoint from the intersection.

In earlier versions of NTP a probabilistic approach was taken based on
maximum-liklihood methodology familiar in communications systems design.
In simulation studies with the Marzullo algorithm and actual offset data
collected over particularly troublesome Internet paths, the algorithm
proved to be effective, although accuracy suffered considerably. In NTP
Version 3 the Marzullo algorithm is used in tandem with the original
maximum-likelihood algorithm and appears to work exceptionally well.

Of concern to the early users of NTP (Kerberos, part of Project Athena
at MIT) was the vulnerability of the timekeeping system to hostile
attack, since incorrect time could result in denial of service
(premature key expiration, for example). An extensive security analysis
by the Privacy and Security Research Group under the auspices of the
Internet Activities Board concluded that it was not possible to secure
NTP against protocol attack other than through use of cryptographic
authentication. This feature was subsequently introduced in NTP and is
now in regular operation for critical and potentially high-risk servers.

In principle, cryptographic authentication could be introduced in other
timekeeping systems as well, including DTSS and PCS, either as a
component of the protocol or, preferably as a component that can be used
by any service on request. It would not seem possible to safely deploy a
ubiquitous, multinational, distributed timekeeping system or set of
interoperable timekeeping systems without this feature. It should be
noted that cryptographic techniques are computationally intensive, so
that special care may have to be taken to preserve the accuracy of the
synchronization service.

@HEAD LEVEL 2 =  Accuracy Expectations

In many, perhaps most, distributed applications requiring synchronized
local clocks, accuracies in the order of seconds are acceptable.
Applications where inconsistent state in the network can be tolerated
for such periods include distributed archiving, electronic mail and so
forth. However, there are many others where accuracies in the order of
milliseconds are required, such as transaction journaling, distributed
software and hardware maintenance, real-time conferencing and long-
baseline scientific experiments. There are a few others where accuracies
in the order of nanoseconds are required, but these applications
typically rely on special-purpose time-transfer networks, usually via
satellite.

Probably few would dispute the ranking of various applications in the
order of increasing accuracy requirements, but there may be some
disagreement on where to draw a reasonable line between those that would
be considered feasible using a shared packet-switched medium with
stochastic delays and those that require a dedicated medium with
predictable delays. With today's technology using 10-Mbps LANs
interconnected by 1.5-Mbps WANs, the line might be drawn in the
milliseconds; however, considering the HPCC initiative which could lead
to widespread deployment of 1-Gbps links, the line might be drawn in the
microseconds. It would seem, then, that any timekeeping system intended
for wide deployment should contain provisions to accommodate accuracies
of this order.

In general, it is not possible absent a detailed engineering analysis of
each particular scenario to predict the expected accuracy of a
timekeeping system. In principle, both DTSS, PSC and NTP can maintain an
accuracy regime consistent with the underlying resource provisioning.
While no specific examples can be cited for DTSS, experiments with both
PCS and NTP suggest accuracies to a millisecond can be expected for both
protocols when operated over a high speed LAN.
Most users of a distributed timekeeping system are most concerned about
the maximum error that can be displayed, rather than the expected error,
which is usually much smaller. Both DTSS, PCS and NTP include algorithms
designed to avoid malfunctioning servers and provide to the user
confidence bounds which bracket the source of correct time. DTSS does
this by collecting samples from at least three servers, computing the
intersection of their confidence intervals and providing this and its
midpoint to the user. PCS takes a different approach where the user
provides the confidence interval and the protocol discards all samples
with a larger interval.

While NTP includes an algorithm similar to DTSS, it also includes a
considerable burden of procedures designed to provide a best-effort
accuracy, even in the face of severe timing noise that normally occurs
as the result of stochastic network delays and congestion. The reason
for this complexity is to serve both communities - those expecting
reliable error bounds, but can tolerate diminished expected accuracy,
and those expecting the highest accuracy attainable under current
environmental conditions.

@HEAD LEVEL 2 =  Scaling and the Need for Hierarchy

Normally, primary clocks cannot be made available for all clients of a
timekeeping system. Even if there were, some means would have to be
provided to compare their indications, since in practice they are not
completely trustworthy. Therefore, there will be a set of servers, at
least one server for every primary clock, and each may serve multiple
clients or other servers. If the number of clients or servers supported
by a particular server exceeds its capacity or the capacity of its
connected network, it may be necessary to create a multi-level, tree-
structured, hierarchical system, with primary servers represented by the
root(s) of the tree and clients represented by its leaves.

While the available PCS documentation does not address hierarchy issues,
DTSS and NTP are both hierarchical systems. In its present form DTSS is
limited to three levels of hierarchy: one corresponding to the local-
server set, another to the global-server set and the third the clerk
set. Each timekeeping entity is designated as either a server or a
clerk, with synchronization always flowing from server to clerk.

NTP was developed in the context of the Internet and is blessed or
cursed by its characteristics. Extrapolating from a recent survey in
Noway, where some eight percent of about 5000 hosts responded to NTP
messages, and a recent estimate of well over 100,000 hosts in the
aggregate system, there are probably over 8,000 NTP-speaking hosts on
the Internet. This does not count a sizeable number of NTP-capable hosts
that do not participate continuously, but choose to read a server clock
vicariously every few hours using designer protocols. The present
Internet with well over 2,000 networks is hierarchically organized in
levels from the NSFNET backbone, through about sixteen regional
consortiums to about a thousand autonomously administered domains.

Therefore, NTP provides multiple levels of hierarchy, with each level
identified by a number called the stratum. The stratum number and subnet
topology are automatically determined as a function of timekeeping
quality, with synchronization always flowing from the root to the
leaves. The present NTP synchronization subnet routinely operates with
five or more levels of hierarchy. However, it may happen that the subnet
is reconfigured as the result of a broken or deteriorated primary clock
or server, so that the stratum number direction of synchronization flow
may at times be reversed between some servers.

@HEAD LEVEL 2 =  Configuration Strategies

Experience with NTP has proven that configuring a timekeeping system
with a constantly changing topology, multiple levels of hierarchy and
hundreds or thousands of servers and clients can be a daunting task.
Carried to extreme, this could mean that every computer in the Internet
must be made aware of at least three servers with which to synchronize.
This issue is not addressed in the available PCS or NTP documentation
other than to relegate it to the management functions.

In practice, NTP configuration relies on directory services (Domain Name
System) augmented by informal databases. Server and client configuration
consists of manually selecting a number of likely upstream servers,
selecting a operating mode and building a configuration file. In most
cases the upstream servers do not need to know about their downstream
clients and the configuration files on a particular LAN are usually
identical. In order to handle cases when a server is down, clients
normally include more than three servers in this file and the protocol
selects the best ones from among the set.

DTSS also relies on directory services; however, it also includes an
elaborate server-discovery scheme based on periodically <169>enumerating
the globals;<170> that is, querying the directory services to extract a
list of available servers. The assumption is that DTSS requires no
manual configuration at all, other than to set certain architectural
constants which presumably are invariant over a management domain.

While not detracting from the DTSS scheme as a valuable management tool,
it is not clear whether the particular enumeration scheme used by DTSS
would be feasible in an environment such as the Internet with an
estimated over 8,000 servers on over 2,000 networks operating in over
100 administrative domains. Presumably the directory information would
have to be stratified in hierarchical levels or the information cached
at strategic places. There is also an argument, as there also is in the
case of cryptographic authentication, that these kinds of services
should be management-based and available for use beyond timekeeping
services. These are issues appropriate for further study.

@HEAD LEVEL 2 =  Synchronization Strategies

There are considerable differences between DTSS, PCS and NTP on the
strategy for discovering servers and using them. As mentioned
previously, DTSS discovers servers with the aid of directory services
and an architected discovery protocol, while NTP relies on directory
services and handcrafted configuration tables. The available PCS
documentation does not discuss how to do this, but presumes some means
is readily available. The principle difference between the timekeeping
systems is the scheme used to select among the discovered servers and
the strategy of their use.

In DTS a set of local servers is cached by the clerk. At intervals
determined by the required accuracy and current confidence interval the
client selects one of them at random and attempts to read its clock,
which results in a new sample including time offset and confidence
interval. The clerk stops at the first response and makes a new
selection if a maximum number of attempts is reached. Operation
continues in this way until a minimum number of servers have responded.
If insufficient local servers have been found, the process continues
with a set of global servers. The resulting sample set is then processed
to obtain the final time offset and confidence interval. Note that only
one reading from each server is obtained at each round; however, in the
case of a time provider, multiple samples may be accumulated in order to
assess the health of the device.

Like DTSS at intervals determined by the required accuracy and current
confidence interval the PCS client attempts to read the clock of a
predetermined server. At each round the attempts succeed if the
confidence interval is less than a predetermined architectural constant
and fails if a maximum number of attempts is reached. Extensions to the
protocol provide for server failures in three ways. One called active
master set is to send a multicast request to a number of redundant
servers and save the first reply. Another called ranked master group
requires each client to use a single default server unless directed
otherwise by an unstated server-client protocol. The third called active
master ring, in which multiple servers are arranged on a ring. At each
round a client selects one of them at random. If attempts to synchronize
fail, the client tries the next server on the ring and so on.

It is important to note that both DTSS and PCS <169>forget<170> all past
history at each round. In effect, each round is statistically
independent, with the only state memory the local clock and adjustment
procedure. The only exception to this was noted with respect to the DTSS
time-provider interface, where a history of samples is maintained for
purposes of evaluating the health of the device. However, the NTP model
specifically includes a limited amount of state history for the purposes
of improving timing accuracy and error bounds.

One of the problems with systems that forget state at each round is that
the time offset and error bound at each round can be quite different,
depending on the particular statistics of the server selected at each
round. A user of the service is then faced with the problem of how to
interpret the differences and possibly to maintain a quality indicator
based on memory of the reported confidence intervals themselves. In the
case of PCS this variance can be reduced through judicious selection of
the maximum error bound; however, this may result in an unacceptable
rate of outages and searches for redundant servers.

On the other hand, NTP includes specific provisions to remember state in
the form of the data filter shown in Figure 2. It has been
experimentally verified that dramatic improvements in accuracy can be
obtained using what in [MIL90b] is called a minimum filter. This device
remembers the last several samples, including time offset and error
bound, and selects the output sample with minimum error bound. The state
information is maintained separately for each peer, since different
peers can have markedly different statistics.

@HEAD LEVEL 2 =  Flexible Access

Although DTSS, PCS and NTP are designed to somewhat different models,
they have a common goal of accurate, reliable service. In order to
accomplish this goal, all three require exacting conformance to the
specifications and possibly costly implementations. However, there may
be cases where the cost to implement the full protocol is not justified
with respect to the perceived requirements. In DTSS a hard line is drawn
in that the protocol can operate in only one way and all clerks must
implement the full suite of (clerk) protocol mechanisms. This issue is
not addressed in the available documentation on PCS; however, several
alternatives for slave-server access procedures are suggested.

In NTP it is possible for a client or sever to select among several
modes of operation, including multicasting and client-server
(synchronization flows only from server to client), and peer-peer
(synchronization information flows either way, depending on timekeeping
quality). It should be pointed out that some of these modes, especially
the multicasting mode, where servers simply broadcast the time at
designated intervals, do not enjoy all the advantages of the fully
implemented protocol; however, it cases involving simple workstations
and personal computers, they seem justified.

@HEAD LEVEL 2 =  Leap Seconds

A timekeeping system with profound reliability requirements and accuracy
expectations of less than a second is always confronted with the issue
of how to deal with leap seconds, which are introduced from time to time
in the UTC timescale. There are many issues involved, some of which are
addressed in [MIL90b], the issues come down to whether to allow the
clocks of the timekeeping system to converge to a newly leaped timescale
at their individual intrinsic rates, or to require that all clocks
assume the new timescale at the instant of the leap. The former is the
case with DTSS and, by impute, PCS. In DTSS the problem is solved simply
by increasing the confidence interval at each server by one second just
before the end of the UTC month.

The design approach taken in NTP was to require the accuracy expectation
to be preserved always, including during, at and beyond the leap event.
This has introduced a degree of complexity, since the protocol must
provide for the advance distribution of leap-second warning, together
with appropriate provisions in the local-clock algorithm. It is the
expectation in the design that leap-second warnings are made available
from the primary clocks as decreed by national standards bodies. While
this expectation has been fulfilled in most time and frequency
dissemination services in the U.S., it has not yet been fulfilled by
all.

@HEAD LEVEL 1 =  References

@INDENT HEAD = [CCI90]

@INDENT =  Time Synchronization Service. CCITT Study Group VII Temporary
Document 433, International Telephone and Telegraph Consultative
Committee, February 1990.

@INDENT HEAD = [CRI89a]

@INDENT =  Cristian, F. Probabilistic clock synchronization. IBM Almaden
Research Center Report RJ 6432 (62550), March 1989.

@INDENT HEAD = [CRI89b]

@INDENT =  Cristian, F. A probabilistic approach to distributed clock
synchronization. Proc. Ninth IEEE International Conference on
Distributed Computing Systems (June 1989), 288-296.

@INDENT HEAD = [DEC89]

@INDENT =  Digital Time Service Functional Specification Version
T.1.0.5. Digital Equipment Corporation, 1989.

@INDENT HEAD = [ISO90]

@INDENT =  Overview of a Distributed Time Synchronization Service
(DTSS). ISO Document ISO/IEC JTC 1/SC21 N4503, International Standards
Organization, 1990.

@INDENT HEAD = [MIL89]

@INDENT =  Mills, D.L. Network Time Protocol (Version 2) specification
and implementation. DARPA Network Working Group Report RFC-1119,
University of Delaware, September 1989.

@INDENT HEAD = [MIL90a]

@INDENT =  Mills, D.L. On the accuracy and stability of clocks
synchronized by the Network Time Protocol in the Internet system. ACM
Computer Communication Review 20, 1 (January 1990), 65-75.

@INDENT HEAD = [MIL90b]

@INDENT =  Mills, D.L. Network Time Protocol (Version 3) specification,
implementation and analysis. Electrical Engineering Department Report
90-6-1, University of Delaware, June 1990.
@INDENT HEAD = [MIL90c]

@INDENT =  Mills, D.L. Internet time synchronization: the Network Time
Protocol. IEEE Trans. Communications (to appear).

@HEAD LEVEL 1 =  Appendix. Requirements Statements

The following sections contain requirements statements excerpted from
the specification documents.

@HEAD LEVEL 2 =  Distributed Time Synchronization Service (DTSS) [ISO90]

DTSS was designed to meet a number of significant technical goals to
provide a firm underpinning for large, commercial networks. The design
goals include the following:

@INDENT HEAD = 1.

@INDENT = Maximize the probability of a client obtaining the correct
time.

@INDENT HEAD = 2.

@INDENT = Rely on specific measurement, rather than averages or
experimentally determined parameters, to accommodate all network
topologies with[out] operator intervention.

@INDENT HEAD = 3.

@INDENT = Use a client-server model to place complexity on the servers
wherever possible. HEAD = 1.

@INDENT HEAD = 4.

@INDENT = Provide a simple and conventional view of time to consumers.

@INDENT HEAD = 5.

@INDENT = Associate a quality with every value of time. The quality can
be expressed quantitatively as an inaccuracy measurement.

@INDENT HEAD = 6.

@INDENT = Be fault-tolerant; withstand the arbitrary failure of a small
number of servers.

@INDENT HEAD = 7.

@INDENT = Scale from very small networks to networks of at least 105 to
106 real systems.

@INDENT HEAD = 8.

@INDENT = Be highly self-configuring to limit the amount of effort
necessary to set up the service and keep it running.

@INDENT HEAD = 9.

@INDENT = Perform efficiently; do not use unreasonable amounts of
resources.

@INDENT HEAD = 10.

@INDENT = Since time always advances, clocks too must always advance
monotonically.
@INDENT HEAD = 11.

@INDENT = Allow totally decentralized management to avoid the dis-
economies of scale in attempting to manage all the resources in a large
computer network from one control point.

@HEAD LEVEL 2 =  Network Time Protocol (NTP) [MIL90c]

Internet transmission paths can have wide variations in delay and
reliability due to traffic load, route selection and facility outages.
Stable frequency synchronization requires stable local-clock oscillators
and multiple offset comparisons over relatively long periods of time,
while reliable time synchronization requires carefully engineered
selection algorithms and the use of redundant resources and diverse
transmission paths. For instance, while only a few offset comparisons
are usually adequate to determine local time in the Internet to within a
few tens of milliseconds, dozens of measurements over some days are
required to reliably stabilize frequency to a few milliseconds per day.
Thus, the performance requirements of an internet-based time
synchronization system are particularly demanding. A basic set of
requirements must include the following:

@INDENT HEAD = 1.

@INDENT = The primary reference source(s) must be synchronized to
national standards by wire, radio or calibrated atomic clock. The time
servers must deliver continuous local time based on UTC, even when leap
seconds are inserted in the UTC timescale.

@INDENT HEAD = 2.

@INDENT = The time servers must provide accurate and precise time, even
with relatively large delay variations on the transmission paths. This
requires careful design of the filtering and combining algorithms, as
well as an extremely stable local-clock oscillator and synchronization
mechanism.

@INDENT HEAD = 3.

@INDENT = The synchronization subnet must be reliable and survivable,
even under unstable network conditions and where connectivity may be
lost for periods up to days. This requires redundant time servers and
diverse transmission paths, as well as a dynamically reconfigurable
subnet architecture.

@INDENT HEAD = 4.

@INDENT = The synchronization protocol must operate continuously and
provide update information at rates sufficient to compensate for the
expected wander of the room-temperature quartz oscillators used in
ordinary computer systems. It must operate efficiently with large
numbers of time servers and clients in continuous-polled and procedure-
call modes and in multicast and point-to-point configurations.

@INDENT HEAD = 5.

@INDENT = The system must operate in existing internets including a
spectrum of machines ranging from personal workstations to
supercomputers, but make minimal demands on the operating system and
supporting services. Time-server software and especially client software
must be easily installed and configured.

In addition to the above, and in common with other generic,
promiscuously distributed services, the system must include protection
against accidental or willful intrusion and provide a comprehensive
interface for network management. [remaining text deleted]