Communications - May 2010

fined in a feedback framework, so we lose their benefits, which include not only much higher accuracy, but also far higher robustness. It is worth noting that in networking, time differences are arguably more commonly used than absolute times. Delay jitter, RTTs, inter-arrival times, and code execution times are all examples of time differences that are best measured with a difference clock.

One disadvantage of a feed-forward approach is that it does not in itself guarantee that the clock never moves backward; however, a causality enforcing clock-read function can fix this without compromising the core design.

a Question of support

The NTP system is the incumbent, supported by all major operating systems. Let us look at some kernel support issues, focusing on FreeBSD and Linux.

The system clock maintained by the kernel (which supplies the well-known gettimeofday() function call), and the kernel support for algorithms to discipline it, have historically been, and remain, closely tied to the needs of the ntpd daemon. In particular, the counter abstractions ( timecoun-ter in FreeBSD and clocksource in Linux), which give processes access to different hardware counters available in the system, fail to provide direct access to the raw counter values. Instead, these are accessible only via timestamps taken by the system clock that uses the counters under the hood. In other words, the kernel APIs support the feedback paradigm only; feed-forward algorithms are, quite simply, barred from participation.

Another important consequence
of the ntpd-oriented nature of the
existing system clock synchroniza-
tion architecture is that the feedback
loop encourages a separation of the
algorithm “intelligence” between user
space and the kernel. The ntpd dae-
mon operates in the former, but the
system clock has its own adaptive pro-
cedures that are, in effect, a secondary
synchronization system. Two feed-
back systems linked via a feedback
loop are difficult to keep stable, main-
tain, and even understand. In con-
trast, by making raw counter values
accessible from user space, feed-for-
ward algorithms can avoid the second-
ary system altogether and concentrate
the algorithm intelligence and design
in a single, well-defined place. The di-
vision of labor is then clean: the syn-
chronization algorithm is in charge of
synchronization; the kernel handles
the timestamping.

the forgotten challenge

Before continuing, we should point out an annoying truth: synchronization over networks is actually impossible. To understand this, let’s reduce the problem to its essence by assuming zero network congestion and system load, so that all delays take their constant, minimal values.

Let A = d� – d¯ denote the true path asymmetry, where d� and d¯ are the true minimum one-way delays to and from the server, respectively; and let r = d� + d¯ be the minimal RTT (see Figure 2). The problem is the existence of a fundamental ambiguity because path asymmetry cannot be measured independently of clock error. The essence of this is the following: if I receive a timestamp T from the server at t = 1. 1 reading T = 1, I cannot tell if I am perfectly synchronized to a server d¯= 0.1 seconds away or, alternatively, if I am 1 second behind true time (packet actually arrived at t = 2. 1) and the server is 1. 1 seconds away.

The asymmetry ambiguity cannot be circumvented, even in principle, by any algorithm. There is, however, some good news. First, this is a problem that plagues absolute clocks only; difference clocks are unaffected. Second, bidirectional exchanges allow constraints flowing from causality ( packets can’t arrive before they are sent) to act. Hence, the asymmetry and the associated clock error are boxed in, even if they can’t be known precisely.

The question remains, how are absolute clocks achieving the impossible? What are they returning? In practice, in the absence of any external side-infor-mation on A, we must guess a value, and Â = 0 is typically chosen corresponding

figure 5. Performance of RaDclock and ntpd over 14 days synchronizing to a stratum- 1 server on the Lan with a 1024 s polling period; time series (left) and histograms (right). stability issues are encountered for the feedback control of ntpd, resulting in an iQR (inter-Quartile Range) which is four times wider.