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