This document reports about my activity during a two month visit at ICSI, the International Computer Science Institute in Berkeley. The work has been carried out within the framework of the ``Network'' group activity, led by Andres Albanese. Here I wish to extend my thanks to Andres and to Giancarlo Fortino, that helped me in the first steps with Java language.
The main intention of this report is to provide the programmer or the user with an exhaustive documentation on how to interact with the program.
It is not meant to cover the clock synchronization issues, and especially the NTP protocol, for which we refer to the original documentation in the RFC 1305. The interested reader can find in that paper also a review of several papers concerning clock synchronization. In addition, the most recent results in that field can be found in 1997 issues of the "Real Time Systems" journal.
One of the main problems in distributed computing is to establish a basic common knowledge shared by all the components in the system. Based on this foundation, the system can establish some form of cooperation in order to complete the assigned task.
Time is a possible candidate for this basic knowledge: if all the hosts agree on time, they can schedule coordinate action, measure the duration of remote events, issue consistent time-stamps for global data structures. To this purpose, an appropriate way of diffusing time information in the system must be provided.
The NTP protocol has been designed to fulfill this aim: it basically consists in an exchange of time-stamps between a host that acts as a client, obtaining time information, and a server, providing time information. A vital aspect of this protocol is the performance of the network between the client and the server. The NTP client, as well as many descendants and clones, synchronizes the system clock of the host. This is a resource that is widely used by many programs in the system, and its setup can have disruptive effects on the functionality of the system. Therefore setup operations on the system clock are reserved to programs with super-user privileges, and should be as ``smooth'' as possible. Its configuration is a matter of system administration.
While the NTP daemon is running, a program can rely on the fact that the system clock of the host it is running onto is approximately equal to the clock of any other host running a NTP daemon. The value of the system clock can be obtained calling an appropriate system library routine: unfortunately, these routines usually depend on the hardware platform, thus portability of any program using the system clock is heavily em-paired.
The UTC client we are introducing, that we call Syd, does not synchronize the system clock, and therefore can be run as an ordinary user application. Applications that need the current UTC time, can ask for it to Jsyd, that therefore acts as a proxy for the clock information. The access to Syd is limited to the programs that run on the same host. But Syd uses remote NTP servers in order to gather the information it delivers locally: therefore we refer to Syd also as a ``NTP proxy''.
The interaction between Syd and the generic application is through an internal socket: virtually any programming language can use sockets to interact with another program, thus this choice does not impact on the operability of the Syd service. However, programs written in Java (a trademark of Sun Microsystems), can exploit an improved interface through a specialized LogicalClock class.
The adoption of Java language brought two important advantages: Syd is portable with zero effort to any platform that supports Java, and several classes are designed to be reusable. For instance, the bare NTP client can be reused for a different application.
The main disadvantage is the existence of a lower bound to the clock granularity, which is 1 msec for Java. However, this granularity is hardly reachable in practice, due to the limited speed of network communication. The peculiar execution scheme of Java did not produce any observable slack, and we obtained clock precisions of a few msecs.
This report is divided into 3 sections: the first section indicates how to configure Syd, the second describes the protocol to interact with the server, and the third one addresses re-usability issues.
The configuration of Syd is Unix-like: there is a set of built-in defaults, that can be modified by command line parameters. Additional parameters for an advanced use are contained in a human readable configuration file. There is no graphic interface, although one is planned in the future.
The configuration must take into account two basic aspects: the definition of some local characteristics, and the configuration of the interaction with the remote servers.
The former aspect is not critical. One concern is the location of configuration and log files: by default, they are kept in a directory named log_files rooted in the directory where the program is run. This default can be changed using the -l command line option. The name of the configuration file is syd.conf, and the names of the log files are obtained prepending a letter or number to a prefix log_. The user must also provide an upper bound of the local clock drift: this is a measure of the speed with which the local clock ``drifts away'' from the real time. The user can either find this information in the administration manual of the computer, or compute it by measuring the drift during one day: 1 second in one day (backward or forward) stands for less than 12 parts per million (or ppm). Thus 10 seconds in 1 day stands for 120 ppm. The default is 200 ppm, and the user can change this with the command line option -l followed by the the drift in ppm. To stand on the safe side, the user should specify a drift that is at least twice the measured drift. An incorrect configuration of the maximum drift can lead to the failure of the protocol, or to the delivery or inaccurate clock values.
The configuration of the interactions with the servers is much more critical. Syd can gather information from several NTP servers: this is the only way it can guarantee a dependable service. NTP servers can be down, unreachable, or simply provide a degraded service, and only redundancy can provide a way to cope with a degraded performance of one or more servers.
The interaction with each server is configured separately: one server is configured using command line parameters, other servers are configured in the configuration file. In fact, Syd operates a different session for each server.
The operation of a session consists in a series of attempts of reaching a precision of the internal clock below a certain lower bound. The result of these attempts is determined by the communication delays. As soon as a session reaches a precision below that lower bound, it stops retrying and waits for the time when a refresh will be necessary. The series of attempts can have a partial success: it occurs when the reached precision is not below the lower threshold, but does not exceed an upper threshold, that stands for the quality requirement on precision. The session fails when the clock precision exceeds the upper bound.
For each server the user must provide six items, that correspond to the values used to implement the above behavior:
A piece of advice is needed about the value to assign to these parameters, and especially to epsilon, delta and k.
In order to assign the proper values, some statistics should be collected: to this purpose, the log files can be used. Then the user must figure out the required level of reliability of the session: this is 1 - p_f where p_f is the probability of failure due to the session itself (not to the network or whatever reason not inherent to the design of the session). Now, let us choose a value for epsilon, and let p_x be the probability that an attempt exceeds the precision epsilon. Such information is obtained by processing the log files recorded during a sample run. We then have the value of k determined as:
k >= log(p_f) / log(p_x)
and for the value of delta the following inequality holds:
delta >= w * (k-1) * r
where r stands for the maximum drift of the system clock that we met above.
The above formulas are simplified ``rules of thumb'' that give a first approximation of the optimal values. For better results the user should read the papers [cri] and [ala]. An ``expert system'' able to derive more accurate values might appear in the future.
Once the values have been computed for the sessions, the user has to indicate the parameters for the first choice session as command line parameters, and the others as distinct lines in the configuration file.
The command line options corresponding to the parameters are the following (between the parentheses is the default value):
All values that correspond to times are expressed as milliseconds and the order does not matter.
The data in the configuration file are organized in a similar way: each line describes a session, and is composed of six items separated by a tab. Each item corresponds to one of the parameters listed above, in the same order. Items can be replaced by a dash (-) to indicate the default value.
The number of sessions is limited to 10, one defined with the command line, and nine in the configuration file. It is reasonable, but not necessary, to list them in order of reliability and access time. The Syd policy is to deliver the clock value hold by the first running session, beginning with the one defined on the command line and proceeding with the first listed in the configuration file. From time to time failed sessions are restarted.
When Syd is running, other programs can interact with it through its socket connection. The port number for this socket is 1200. The inclusion of such data among the configuration data is one of the planned improvements.
The Syd application behaves, in this case, as a server, while the inquiring program stands as a client. In the following, we refer the inquiring program as ``the client''.
The protocol between Syd and the client is very simple: the client sends a message with no information to Syd, and receives from Syd an encoded packet containing the data needed to compute the present time.
All data correspond to signed integers represented as 8 bytes of 8 bits each. There are 5 pieces of data of this kind:
The first three data are encoded in msecs. The last two stand as thousandths of ppm (1000 stands for 1 ppm). We stress that Syd delivers no information about what server (or session) was used to obtain these data.
Using an abstraction known as ``logical clock'' the client can easily compute the present UTC time and the precision of the estimate starting from the above data and the value of the system clock:
UTC time = system clock + offset
precision = precision + (system clock - origin) * r * 10E-9
One of the valuable effects of passing the ``logical clock'' instead of the bare UTC value is that the client can use the same data structure to compute several times, at different times, the UTC value using the same data structure, and without being exposed to the loss of precision due to the time spent interacting with Syd. The main disadvantage is that the client must access the system clock, and this may hinder the portability of the client program.
Therefore the client program is in charge of implementing the marshaling of the packet provided by Syd, and of computing the values of time and precision from the data contained in the packet. This charge can be avoided if the client is also written in Java, by exploiting the Java class ``logical clock'' which is part of the Syd package hierarchy.
The next section describes the parts of that package explicitly intended for reuse, and in particular the LogicalClock class.
One of the most innovative aspects of Java is the stress placed on software re-usability. The way javadoc documentation utility enforces a structure in the documents that come with a package plays a significant role in the possibility of reusing parts of a package.
While designing Syd, four packages have been explicitly designed in order to be reusable: three of them are directly related to the clock synchronization issue, while the third is a generic synchronization tool.
In this section we briefly sketch the main purpose of each package: for the details of the classes and methods that are exported we address the html documentation that comes with the package.
The main object exported by this package is the LogicalClock, that represents a UTC clock that can be read and written.
A Java program can use this package in order to marshal and operate with a packet received by Syd. In fact, there is a constructor that takes directly the byte array received from Syd, and creates the corresponding LogicalClock. Then the program can repeatedly use this data to know an approximation of the UTC time, since value and precision methods are provided that return the estimate of the current UTC and the precision of the estimate.
There are also two additional methods that ``displace'' this evaluation to an arbitrary time in the past or in the future. To this purpose, the user must provide a parameter indicating the value of the system clock corresponding to the place in time where I want to perform the operation.
This can be extremely useful to keep accurate timing of any activity: for instance, if one wants a lapse of x secs to be from a to c, but some time consuming action must be performed after a, that ends after an impredictable delay lower than x, then the steps are:
To compute the displacements, the programmer should use the method provided by the SystemClock class. Presently, the granularity of the timing is determined by the implementation of the read method of the SystemClock class. Should more accurate clock reading primitives become available, they will be included in the package.
There is also a method that produces a printable string containing the state of the logical clock.
Using this class, the access to the Syd can be as simple as this:
which simply prints the current setup of the logical clock by applying to the toString method.
This package contains some basic tools to interact with an NTP server. The most reusable class is probably the RemoteClockread, that performs the remote clock reading game.
After the read has been performed, the object can reveal the timestamps contained in the packet, the precision of the server's clock, and the system clock when the reading was performed (to be used in following ``displaced'' computations).
This package implements a basic synchronization monitor. Its main purpose is detailed in the html documentation. Here we just say that it is meant to coordinate the activity of a central entity that monitors the activity of a set of warm spares: in Syd it is used to keep trace of the activity of the different sessions.
The operation of Syd produces a considerable amount of logging information. This information is precious in order to make statistics and solve problems.
One file (log_d) is dedicated to trace the activity of the central daemon, that monitors the activity of the sessions. This file contains a snapshot of the state of all the sessions, recorded each time one of them reports a successful refresh of the clock. The states are checked for consistency: all of them must overlap, their intersection must not be empty. Failure to satisfy this requirement is indicated, and can be determined by a possibly underestimated drift, or by a wrong value for the minimum communication delay.
There are other files dedicated to the trace of the other sessions: log_0} stands for the first choice session, and so on. Each has a header that indicates the configuration data for this session, followed by a record for each attempt of reading the remote clock. Each record consists in the timing of the attempt, the mode used for the clock reading, and the final precision achieved. An error message is printed should the timing of the attempt be inconsistent with the expected initial precision. This error can indicate an incorrect value for the minimum communication delay, or for the maximum drift.
The package is provided with a Makefile that prints some interesting graphs when requested to make stat: the script uses gnuplot and other gnu utilities.
[cri] F.Cristian ``Probabilistic Clock Synchronization'', Distributed Computing, n. 3, 1989, pp. 146-158.
[ala] G.Alari, A.Ciuffoletti ``Implementing a probabilistic Clock Synchronization'', Real-Time Systems, n. 1, Vol. 13, 1997.