IEEE Circuits and Systems Magazine - Q2 2020 - 14

are known. Clocks do not know how far apart they are
from each other. But a statistical argument is made that,
at any time, any two clocks are within some constant
maximum deviation with a certain probability.
Software algorithms use standard communication
networks and exchange synchronization messages
to get the clocks synchronized. They are frequently
used in situations where a loose synchronization
in the range of milliseconds is acceptable (such as
the Internet). Pure hardware clock synchronization
achieves much tighter synchronization through the
use of special synchronization hardware at each
node and a separated network solely for clock signals
(such as the Sync-E). Due to the cost and size of those
additional hardware, it is only affordable when the
system spread is within a limited range. Hybrid solutions are based on software algorithms with moderate hardware support. They can achieve reasonably
tight synchronization and are still cost effective in
comparison to pure hardware approaches. The supporting hardware usually carries out the tasks of
maintaining the local clock, applying the required
corrections and providing some facilities to ease the
exchange of synchronization-related messages (such
as in the case of PTP).
In the development of clock synchronization algorithm, following factors must be taken into consideration.
■■ Network configuration: broadcast or point-to-point
or bus, fully-connected or partially-connected.
■■ Internal or external: internal synchronization only
considers the clock states of the nodes in the
network while external further requires the synchronization to an external time standard (e.g.
UTC). The criterion for internal synchronization
is precision while accuracy is additionally considered for external.
■■ Clock model: clock synchronization algorithm
executes on local processor and takes the clock
readings of local and remote clocks as inputs. The
computed correction is then applied to correct local clock time. Most nodes are equipped with a
clock of oscillator-plus-counter. Synchronization
on those local hardware clocks (i.e. the physical clocks) is not possible since directly tuning
the oscillator is difficult if not impossible. Thus,
the concept of logical clock is introduced, whose
value is determined by adding an adjustment
term to physical clock (please refer to figure 1).
The adjustment term can be either a discrete
value changed at each re-synchronization, or a
linear function of time. The discrete adjustment
may cause a logical clock to instantaneously leap
forward or be set back. Such behaviors of abrupt
14

time-jump and negative-time cannot be tolerated
by most applications. Therefore, a linear function
of time for clock adjustment is often mandatory.
■■ Clock rate variation: this is caused by oscillator's
frequency instability. Practically speaking, frequency drift is the key reason for network's gradually-out-of-sync.
■■ Message exchange method: this defines the way
that nodes exchange clocking-related messages.
The first type is asymmetric approach (masterslave structure) where one dedicated node is designed as master providing time to the other nodes
designed as slaves. The second one is symmetric
approach where all nodes participate in an active
manner and execute the full clock synchronization algorithm. Another one is the hierarchical
approach where synchronization is spread at different levels and within each level there may again
be categorized as either asymmetric or symmetric. Asymmetric scheme is a low-cost solution in
terms of message traffic but it bears the risk of
single point failure. Symmetric method is more robust but with a higher traffic cost.
■■ Network uncertainty: the time that it takes for a
packet-switched network to deliver synchronization message is nondeterministic.
■■ Fault type: this describes the faults that a synchronization algorithm must deal with. There
are clock-related faults (clock byzantine failure
and clock timing failure), processor-related faults
(processor crash failure and processor performance failure) and link-related fault (link omission
failure and link performance failure).
In operation, algorithm needs to perform three key
tasks: synchronization event detection, remote clock
estimation and clock correction. Due to frequency instability, clocks must be re-synchronized periodically
to guarantee precision and accuracy. Algorithms therefore are usually round-based, each round being devoted to the re-synchronization of all the clocks. The
function for resynchronization-event-detection must
be activated periodically. When a new round initializes, every node needs to get some knowledge of the
values of remote clocks. Due to the indeterministic
communication delays and clock drifts, only estimates
can be made. It is essential that these estimations are
closely resemble the remote clock values since those
clock readings will form the inputs for directing the
subsequent clock correction. The action of clock correction can be implemented in two different fashions:
clock state correction where only clock's current state
is modified and clock rate correction where clock rate
can be adjusted as well.

IEEE CIRCUITS AND SYSTEMS MAGAZINE

SECOND QUARTER 2020

IEEE Circuits and Systems Magazine - Q2 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2020