fast rate, the rate error being the skew
x. The red clock Cd(t) = t + E(t) is more
realistic, its error E(t) varies with time,
and the clock is said to drift. Far from
aimless, drift is in fact very closely related to temperature changes. Figure 6
(discussed later in greater detail) gives
a close-up view of the drift E(t) (black
curve) for an unsynchronized clock in
a Pentium PC over a two-day period.
PhotograPh by sergei yahchybekov/getty images
At the heart of every clock is hardware. In PCs this is an oscillator found
on the motherboard. The oscillator
“ticks” at a nearly constant rate—in
fact typically varying on average by
only 0.1 ppm (parts per million). Hardware counters such as the HPET (High
Performance Event Timer) count these
ticks, giving the operating system access to a slowly drifting source of timing. From such a counter, a clock can
be defined that, roughly speaking,
converts counter tick units into seconds and adds a constant to set the
time origin:
C(t) = C0(t) + p(t) · HPET(t)
where p(t) is the (slowly time varying)
period in seconds of the HPET counter. The role of the clock synchronization algorithm is to set and regularly
update the values of C0 and p(t) to reduce the drift, or error E(t) = C(t) – t, as
much as possible.
Enter the Internet. The sync algo-
rithm has no way of correcting the drift
of C(t), inherited from the counter,
without calling on some independent
expert: a reference timing source, or
master. Attaching extra hardware is
possible but expensive, and is point-
less unless it is reliable. A good-quality
GPS with consistently good satellite
visibility can cost many thousands of
dollars by the time you have persuaded
the building supervisor to mount it on
the roof and run a cable to your office.
Oh, and it will take you six months to
make it happen—minimum. An atom-
ic clock is even more expensive and still
requires GPS to avoid drift on weekly
timescales and beyond. In contrast,
synchronizing over the network can be
done with no lead time, no dollars, and
not much effort.
the Key challenge:
Delay Variability
Clock synchronization is trivial in principle. You ask the expert what the time
is, he looks at his clock, tells you, and
you set your watch. Simple. The problem is that each of these steps takes
time, and on the Internet, these delays can be large, unpredictable, and
highly variable. The key challenge—
almost the only one—for a synchronization algorithm, is to be able to cope
with these variations, to robustly and
precisely negate the errors caused by
delay variability.
The delays suffered by timing packets are generated in both the host computer and the network (and the server,
but we will be generous and assume a