IEN 173
Time Synchronization in DCNET Hosts
D.L. Mills, COMSAT Laboratories
25-Feb-81
Introduction
The difficulty in establishing an absolute time reference
for use in internet measurements and experiments has been
often lamented. While time standards calibrated to the
precision necessary for internet delay measurements (in the
order of a millisecond) are readily available, the cost to
equip each host which may participate in these experiments
is significant and the broadcast services they depend upon
may not be available where needed. This note describes an
alternative mechanism using local-net protocols to
synchronize a logical clock in each of a set of internet
hosts to a single physical clock, such as an NBS radio
clock. The mechanism has been incorporated as an integral
component of the DCNET network routing algorithm and depends
for its accuracy upon the careful control of link delays.
For this reason it may not be practically applicable as a
retrofit in the ARPANET, for example. Nevertheless, the
principles can be applied in cases where somewhat less
precision is acceptable and where the participating hosts or
gateways support the required protocol.
The DCNET Routing Algorithm
The DCNET includes a number of PDP11-compatible hosts
interconnected by dedicated and dial-up links of various
types, including simple synchronous and asynchronous
point-to-point links, high-speed interprocessor channels and
self-contained retransmission systems. All of these links
include inherent delays which vary with transmission rate,
message length and coding, as well as occasional
retransmissions. In addition, the host operating system can
introduce delays due to interrupt latency, interprocess
communication and process scheduling. These delays
typically include a fixed component due to propagation
phenomena, together with a relatively small variable
component due to internal queueing, coding and
retransmission mechanisms.
The DCNET architectural design includes the notion of
virtual host, which is a process resident in a physical host
and labelled with a unique internet address. One or more of
these virtual hosts can reside in a single physical host and
can migrate about the network from time to time in arbitrary
ways. Each virtual host can support multiple internet
protocols, connections and, in addition, a virtual clock.
Each physical host contains a physical clock which can
operate at an arbitrary rate and, in addition, a 32-bit
Time Synchronization in DCNET Hosts PAGE 2
logical clock which operates at 1000 Hz. Not all physical
hosts implement the full 32-bit precision; however, in such
cases the resolution of the logical clock may be somewhat
less.
Routing of datagrams from a physical host to each of the
virtual hosts in the network is determined by a set of Host
Tables, one in each physical host, which are updated by
HELLO messages exhanged on the links connecting them. The
HELLO messages are exchanged frequently, but not so as to
materially degrade the throughput of the link for ordinary
data messages. They contain information necessary to
compute the roundtrip delay and logical clock offset of the
receiving physical host relative to the sending one,
together with a table of delay and offset estimates computed
between the sending physical host and each of the virtual
hosts in the network. For the purpose of these estimates
the delay and offset of each virtual host relative to the
physical host in which it resides is assumed zero.
The Host Table is updated by HELLO messages from each
neighboring physical host and in certain other cases. The
updating algorithm is similar to that used in the ARPANET
and other places in that the roundtrip delay calculated to a
neighbor is added to each of the delay estimates given in
its HELLO message and compared with the corresponding delay
estimates in the Host Table. If a delay computed in this
way is less than the delay already in the Host Table, the
routing to the corresponding virtual host is changed
accordingly. The detailed operation of this algorithm,
which includes provisions for host up-down logic and loop
suppression, is summarized elsewhere [1].
Virtual Clocks
The Host Table update procedure represents a convenient
mechanism to implement a common time reference for each
logical clock in the network. For this purpose each virtual
clock residing in a physical host is assumed to run in
synchronism with zero offset relative to the logical clock
of that host. The offsets of the other virtual hosts in the
network, relative to this logical clock, are computed along
with the delays as HELLO messages arrive from neighboring
physical hosts. A physical host, upon receiving a HELLO
message, adds one-half the difference between its logical
clock and its neighbor's logical clock contained in the
HELLO message to each of the offset values in the message
and stores the result in its own Host Table. Note that both
the delay and offset values are stored only if the neighbor
is in fact on the least-delay path to the virtual host and
that the link delay is assumed equal in both directions.
Also, note that should a virtual host move from one physical
host to another, the delays and offsets in all Host Tables
Time Synchronization in DCNET Hosts PAGE 3
relative to that virtual host would likely change.
Any user process in a physical host can reference its
time-of-day calculations to any virtual host in the network
by simply adding the appropriate virtual clock offset to the
current value of the logical clock. Ordinarily, all network
experiments use the same virtual host for this purpose,
although not necessarily the same one in successive
experiments. In the current implementation one of the
physical hosts contains a special virtual host connected to
an NBS radio clock. The offset stored in the Host Table
corresponding to this virtual host reflects the offset of
this clock relative to the logical clock. Using the above
mechanism, the remaining physical hosts can reference their
logical clocks to the receiver as well. One of the physical
hosts is shortly to be moved not far from an atomic clock
which is referenced to the Naval Observatory clock using a
local television station. We are now assembling interface
hardware for access to this standard and plan to use the
above mechanism to reference all clocks to it.
Implementation Considerations
The absolute accuracy of the available NBS radio clocks is
claimed to be of the order of a millisecond. Since this
precision compares with that of the standard internet
timestamps used for the most precise delay measurements, it
would be natural to strive for a corresponding precision
within a set of hosts using the mechanism described above.
Ordinarily, this would require a crystal oscillator, counter
and interface at each host. The oscillator stability found
in commercial equipment of this type is of the order of a
few parts per million under laboratory conditions. An
uncorrected logical clock based on this equipment could be
expected to maintain time to within a millisecond for at
least eight minutes and to within three minutes in a year.
In the case of the mechanism described above, the
corrections take the form of offsets contained in periodic
HELLO messages. A careful analysis of the non-systematic
errors inherent in these messages reveals contributions from
a number of sources dominated by the following:
1. The interval between the instant the local clock is read
and the departure of the first bit of the timestamp on
the link.
2. The effect of the data coding conventions (e.g.
character stuffing or bit stuffing) used to maintain
data transparency.
3. The effect of retransmissions, where used.
Time Synchronization in DCNET Hosts PAGE 4
4. The interval between the arrival of the first bit of the
timestamp and the instant it is compared with the local
clock.
The effects of the first and last of these delays has been
minimized in the DCNET implementation by careful control of
internal latencies and scheduling mechanisms and is limited
to the order of a millisecond. The effects of character and
bit stuffing can be estimated under the assumption that all
character codes are equally likely. In that case, the
effects of character stuffing would contribute a factor of
about 1/256 to the uncertainty in data rate and the effects
of bit stuffing would contribute about 1/32. Thus, for the
case of 1200-bps character-stuffing links carrying HELLO
messages of typically 800 bits, the uncertainty would be of
the order of two milliseconds. The effects of bit stuffing
in the high-speed links are negligible in comparison.
Although HELLO messages are never retransmitted by a DCNET
host, some of the DCNET links, in particular those based on
the ACC Error Control Units (ECU), contain internal
retransmission features. Since retransmissions occur so
seldom in the present configuration, their effects have been
ignored; however, a simple range-gate technique similar to
that used in radar systems could be used to filter out
retransmissions, should that become a problem.
From the above considerations the uncertainty in delays
measured using HELLO messages can be conservatively assumed
in the order of five milliseconds. For ease of analysis in
the following, we will assume the uncertainty to be a random
variable with a zero-mean Gaussian distribution and a
standard deviation of five milliseconds. Thus, in order to
reduce the uncertainty to the order of a millisecond,
something over 25 independent samples would be required.
The maximum interval between successive HELLO messages is
thirty seconds, so that the required precision can in
principle be achieved in about twelve minutes.
Precise determination of clock offsets requires that the
drift rates between the various logical clocks be estimable
with sufficient precision. The approach chosen in the DCNET
design has been to initialize a variable representing the
current offset of the local logical clock relative to that
of a neighbor each time a HELLO message arrives from that
neighbor which updates the Host Table entry for the selected
virtual host. Once each second the period of the logical
clock is increased by a quantity equal to 1/1024 of this
variable and the variable is decreased by the same quantity.
The effect is that of a first-order recursive filter in
smoothing the corrections and distributing them so as to
minimize the phase jitter as viewed by the user process. In
addition, if updates from the selected virtual host are lost
due to failure of some host or link, the logical clock will
Time Synchronization in DCNET Hosts PAGE 5
continue the correction process until the last offset
received is compensated.
In order to provide for the initial setting of the logical
clock and subsequent drift correction without disruptive
phase discontinuties, the full 32-bit clock value is stored
only if the (signed) offset exceeds 16 bits; that is, only
if the high-order 16 bits must be changed. In other cases
the low-order 16 bits are corrected by slewing the phase of
the clock according to the current offset as described
above. The high-order 16 bits correspond roughly to
minutes, while the low-order 16 bits correspond to
milliseconds. Most internet measurments will be concerned
primarily with the latter, so this behavior is appropriate.
This yields a slew rate of about one microsecond per second
for each millisecond of offset.
The dynamics of this procedure insure a smooth transition in
apparent drift rate from a maximum of 30 parts per thousand
for the maximum offset to one part per million for the
smallest. The maximum time required to slew the phase of a
physical clock over the full (plus-minus) thirty-second
range to steady state is about two hours. During the
slewing interval the offset estimates continue to be valid,
although of somewhat degraded accuracy.
In a multiple-host network where the logical-clock
corrections must pass through a number of physical hosts,
the robustness of this method depends on the cooperation of
all intervening hosts. In general, this requires all hosts
to track the same virtual host offset and, in addition,
introduces additional dynamics in the drift-correction
process. The effect is that of a set of coupled first-order
recursive filters, where the input of each stage is
connected to the output of the previous stage, and all have
the same time constant described previously. So long as the
drift rates are constant over at least several hours, this
is not a problem; however, in the case where some logical
clocks are derived from power-line sources, this can lead to
significant loss in accuracy.
On Power Line Clocks
The short-term drift rates of power-line clocks relative to
standard time have been observed to exceed several parts per
thousand, with sharp changes in sign and magnitude occuring
near periods of large load fluctuations. In experiments
with the current DCNET implementation, discrepancies of
several seconds are routinely observed between the
power-line clock and the NBS radio clock. However, it is
evident that the power systems for considerable portions of
this country are closely synchronized in phase relative to
each other. For instance, the DCNET hosts at COMSAT
Time Synchronization in DCNET Hosts PAGE 6
Headquarters in Washington, D.C., and at Ford Scientific
Research Laboratories in Dearborn, Michigan, have never been
observed to slip a power-line cycle relative to each other.
These observations suggest that, if logical clocks are to be
synchronized to an atomic clock or NBS radio clock, then
physical clocks based on the power mains are not feasible,
at least for accuracies of the order of milliseconds. On
the other hand, for the short-term delay measurements
required for many internet experiments and where reference
to absolute time is not essential, the use of the power
mains as a synchronization reference may be quite practical.
This holds, of course, only in those cases where the power
systems in the areas where measurements are made are in fact
synchronous and probably would not apply, for example, for
European sites.
On Radio Clocks
Two of the NBS radio clocks on the market include the
Spectracom 8170 WWVB Synchronized Clock and the True Time
468-DC Satellite Synchronized Clock. The former uses the
60-KHz NBS broadcast from Boulder, Colorado, while the
latter uses the NOAA GOES satellites. Both have claimed
accuracy in the order of a millisecond and both support a
service area including the continental US. A Spectracom
8170 is now in service connected to one of the DCNET hosts
and serves as a master clock for the network. A few notes
on its characteristics may be of interest, especially to
others in the internet community planning on using similar
equipment.
The characteristics of electromagnetic wave propagation at
60 KHz combine some features of the waveguide model
applicable at frequencies below about 30 KHz and the ray
model applicable at higher frequencies [2]. Both models
explain how the E layer, an ionized region about 100 km
above the earth's surface, guides or reflects
electromagnetic waves over long distances. In the case of
60-KHz transmissions from Boulder, the models predict
greater signal attenuation at times of the most intense
ionizing radiation from the sun on the D region, which lies
just below the E region and through which the signals must
pass. Thus, one would expect that received signal levels
would be highest at nighttime in winter and lowest in
daytime in summer, with respect to the midpoint of the path
from Boulder to the receiver. This has been observed in
Washington, DC, where the receiver often drops out of phase
lock for varying periods in the late afternoon.
Measurements of the received signal level with a
communications reveiver confirm variations of 20-30
decibels.
Time Synchronization in DCNET Hosts PAGE 7
Atmospheric discharges (called sferics) due to lightning can
be a severe problem at these frequencies in Summer and could
be expected to disrupt the receiver during summer evenings
when propagation conditions are relatively good from active
electrical areas like the Gulf Coast. Although other
stations share the 60-KHz assigned frequency, including MSF
in Rugby, UK, co-channel interference does not seem to be a
problem. On the other hand, some household electrical
appliances, including television deflection circuits and
solid-state lamp dimmers, can generate copious harmonics
that disrupt the receiver. The ferrite antenna supplied
with the receiver does not seem to be as effective as would
ordinarily be expected in dealing with this problem.
Even when phase lock has been lost, the receiver coasts
indefinately using the last clock update received. Although
the receiver indicates a signal loss of over ten minutes,
both by a front-panel indicator and in the time message sent
to the attached host, the indicated time should remain
accurate to within an order of one part in a million, as
suggested by tests using an accurate frequency counter. The
DCNET implementation polls the receiver every thirty seconds
and tracks the time messages as long as they are available,
but retains the last received message for later inspection,
if desired. In addition, if the time messages are lost the
system continues to follow the information in the last
message.
Summary and Conclusions
The above analysis indicates that logical clocks in
neighboring physical hosts can be synchronized using
ordinary local-network routing update messages, so long as
the oscillator drift rates are stable and do not differ
radically. A multiple-host network can readily be
synchronized so long as each pair of neighboring hosts can,
although this can require rather long settling times. Here,
two hosts are assumed synchronized when the offsets between
their respective logical clocks can be calculated to a
precision of the order of a millisecond.
Delay and offset variances along internet paths are likely
to be so large as to make the technique described above
impractical, at least if millisecond accuracy is to be
preserved. The present plan of installing radio clocks in
the internet gateways appears to be the most sensible
alternative. The gateways thus form an attractive time
reference for the hosts on the attached local networks. The
gateways themselves could include the offsets between their
own clocks in Gateway-Gateway Protocol (GGP) routing update
messages, if not all of them were equipped with NBS radio
clocks, and could conveniently provide this information in
GGP echo messages to the local network hosts. In order for
Time Synchronization in DCNET Hosts PAGE 8
this to be most effective, the timestamping mechanism used
by the gateways (and hosts, of course) should be implemented
as close to the network interface driver as possible,
preferably by the driver itself.
A local-network host can synchronize its logical clock to a
gateway by a mechanism suggested by the DCNET routing update
procedure. The host sends a GGP echo packet timestamped
with its logical clock to a gateway. The gateway timestamps
it with its own logical clock upon arrival and again when it
is retransmitted to the host. The local host uses these
three timestamps, together with the time of arrival of the
reply packet, to compute the delay and offset as described
above. The use of three timestamps in the GGP echo packet
allows the host to compensate for the internal delay within
the gateway, if significant.
References
1. COMSAT Laboratories Quarterly Progress Reports. Stay
tuned.
2. Davies, K. Ionospheric Radio Propagation. NBS
Monograph 80, National Bureau of Standards, Washington,
DC, 1966.