Precision Time Synchronization


from pogo, Walt Kelly

Researchers involved: David Mills, undergraduate and graduate students

Funding: equipment grants from Arbiter, Austron, Bancomm, Cisco, Digital, Hewlett Packard, Spectracom, Sun Microsystems, TrueTime, US Coast Guard, US Naval Observatory

Briefing Slides

Importance of the Problem

As generally available computers and networks are becoming increasing fast, accuracy expectations are extending from milliseconds to nanoseconds. The performance of existing computer hardware over extended periods where outside synchronization sources are lost is in some cases unacceptable. Recent surveys have shown that the intrinsic frequency offset of typical workstations and servers is from a few to a few hundred parts per million, which can result in timekeeping errors from a few to a few hundred microseconds, even when the clock is disciplined by NTP. Measurements made using fast, modern workstations demonstrate that the kernel time can be reliably disciplined to the order of a few tens of nanoseconds when sufficiently accurate and stable external reference sources are available.

However, most current Unix workstation kernel implementations do not provide precision time and frequency synchronization to the degree believed necessary for future real-time applications, such as distributed conferencing control and resource management. This project designs, implements, tests and refines the hardware and software algorithms to provide precision time synchronization to the degree possible with available computing equipment and synchronization sources.

Brief Description of Work and Results

Late models of workstations manufactured by Digital, Hewlett Packard and Sun Microsystems have been obtained under equipment grants. In addition, Global Positioning Service (GPS) receivers and cesium oscillators have been donated by several manufacturers and government agencies. We have pursued the analysis, simulation and synthesis of clock discipline algorithms that has resulted in a continuing refinement of the algorithms incorporated in the NTP software implementations over the last two decades. In addition, we have explored the application of external timekeeping devices and signals to improve timekeeping accuracy to the order of nanoseconds in modern workstations.

An important aspect in this investigation is the continued refinement of the algorithms used to distribute and maintain precision time in the Internet. Recent work demonstrates that the accuracy and stability of the system clock can be maintained with NTP message intervals much longer than previously possible. At the current level of refinement, accuracies of a millisecond or two can be maintained with update intervals up to several hours and at somewhat reduced accuracies to well over one day. This is an important feature when per-call toll charges are involved and in cases where low probability of intercept is required. This work is conducted in collaboration with NIST Boulder (Judah Levine) and USNO Washington (Richard Schmidt) and uses hybrid algorithms developed jointly by David Mills and Judah Levine.

Previously, we designed, built and tested generic Unix operating system kernel modifications for precision timekeeping. These modifications, described in RFC-1589, have been incorporated in experimental kernels for Digital, Sun and Hewlett Packard workstations. They are now incorporated in the production kernels for Digital and Sun workstations and in Linux and FreeBSD software distributions.

The kernel modifications have been rewritten to improve the resolution to the order of one nanosecond in time and one nanosecond per second in frequency. The new modifications have been incorporated in experimental kernels for Digital and Sun workstations and in FreeBSD software distributions. The software can be compiled for 64-bit machines, in which some variables occupy the full 64-bit word, or for 32-bit machines, where these variables are implemented using a macro package for double precision arithmetic. The software can be compiled for kernels where the time variable is represented in seconds and nanoseconds and for kernels in which this variable is represented in seconds and microseconds. In either case, and when the requisite hardware counter is available, the resolution of the system clock is to the nanosecond.

The new modifications also support a pulse-per-second (PPS) signal source using an external routine that captures transitions of this signal via a serial port device. The routines have been implemented and tested in Digital Unix, Sun SunOS and FreeBSD kernels. We expect the modifications will be integrated in Sun Solaris and Linux in the normal course of development.

The new NTP version includes several new reference drivers for new clock devices and operating modes. Two of these drivers use the audio hardware and software of Sun Microsystems' workstations and servers, together with advanced digital signal processing algorithms for filtering, demodulation and decoding the audio signals. One of these drivers is designed for the Canadian time/frequency station CHU and is used in conjunction with an ordinary shortwave radio. The other is designed for the IRIG-B and IRIG-E signals generated by some receivers and laboratory equipment. Performance with this driver and the IRIG-B signal of a GPS receiver provides reliable synchronization within a few microseconds on a Sun UltraSPARC. This is the best performance achieved without kernel modifications.

The new NTP Version 4 software daemon for Unix, VMS and Windows provides the capability to discipline the system clock well below the microsecond resolution formerly attainable. With sufficiently stable reference sources and the nanokernel modifications described above, the long term accuracy and stability can be improved to the order of one nanosecond in time and one nanosecond per second in frequency.

Past work involved the design and fabrication of workstation bus peripherals for precision time. An oven-stabilized precision clock oscillator using FPGA technology has been designed and implemented for the Sun Microsystems SBus. Hardware and software interfaces have been developed for the PPS and IRIG signals generated by some radio clocks and laboratory instruments. With these enhancements, residual jitter in computer time can be reduced to a few microseconds and stability to a few parts in 109.

An inexpensive LORAN-C precision timing receiver has been designed, built and tested. It is intended both as a backup for the GPS receivers and as a precision frequency stabilized source for the GPS receivers to reduce the effect of the intentional dither in the civil broadcast signal. It consists of three components, an ISA bus peripheral for a standard PC, an external temperature-stabilized quartz crystal oscillator, and a C-language control program. Unlike our much more expensive Austron LORAN-C receiver, this receiver is completely automatic as it acquires up to four stations in a LORAN-C chain and disciplines the oscillator to within a few parts in 1010. Two receivers of this type have been built, one operating in our laboratory and the other operating at a site in Europe.

A special purpose DSP development unit has been built and populated with experimental algorithms. One of these is a demodulator/decoder for radiotelegraph transmissions used by fixed and mobile shortwave communication services. Another is a demodulator/decoder for the WWV time/frequency service operated by NIST. Both algorithms operate with an ordinary shortwave receiver and use matched filters, soft decision and maximum likelihood techniques to achieve theoretical optimum performance. The performance is so good that reliable operation can be achieved when the broadcast signals cannot be heard by ear.

Future Plans

Other areas that may be explored include clock discipline algorithms for use with precision oscillators, such as the existing FPGA-based precision oscillator. This device is ordinarily loosely disciplined by NTP; however, where accuracy requirements dictate, it can be stabilized using a LORAN-C receiver. As available resources permit, we plan to redesign the existing LORAN-C receiver as a PCI bus peripheral. We also plan to implement the discipline function itself, now performed by daemon or kernel emulation, entirely in the FPGA. This design provides an accurate, stable synchronization source independent of the daemon or kernel which, even if the daemon or network fails for extended periods, can continue to provide accurate time.

Selected Publications

  1. Mills, D.L., and P.-H. Kamp. The nanokernel. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, November 2000). Paper: PostScript | PDF, Slides: PostScript | PDF | PowerPoint
  2. Mogul, J., D. Mills, J. Brittenson, J. Stone and U. Windl. Pulse-per-second API for Unix-like operating systems, version 1. Request for Comments RFC-2783, Internet Engineering Task Force, March 2000, 31 pp. ASCII
  3. Mills, D.L. Adaptive hybrid clock discipline algorithm for the Network Time Protocol. IEEE/ACM Trans. Networking 6, 5 (October 1998), 505-514. PostScript | PDF
  4. Mills, D.L., A. Thyagarajan and B.C. Huffman. Internet timekeeping around the globe. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Long Beach CA, December 1997), 365-371. PostScript | PDF
  5. Mills, D.L. A precision radio clock for WWV transmissions. Electrical Engineering Report 97-8-1, University of Delaware, August 1997, 25 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  6. Mills, D.L. Clock discipline algorithms for the Network Time Protocol Version 4. Electrical Engineering Report 97-3-3, University of Delaware, March 1997, 35 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  7. Mills, D.L. The network computer as precision timekeeper. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, December 1996), 96-108. PostScript | PDF
  8. Mills, D.L. An optimal linear receiver and codec for a class of radiotelegraph signals. Electrical Engineering Department Report 95-8-1, University of Delaware, August 1995, 91 pp. Abstract: PostScript | PDF, Body: PostScript | PDF, Appendix A Operations: PostScript | PDF, Appendix B RTTY Analysis: PostScript | PDF, Appendix C DCD Analysis:PostScript | PDF
  9. Mills, D.L. Precision synchronization of computer network clocks. ACM Computer Communication Review 24, 2 (April 1994). 28-43. PostScript | PDF Condensed from: Ibid. Electrical Engineering Department Report 93-11-1, University of Delaware, November 1993, 66 pp.
  10. Mills, D.L. Precision synchronization of computer network clocks. Electrical Engineering Department Report 93-11-1, University of Delaware, November 1993, 66 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  11. Mills, D.L. Modelling and analysis of computer network clocks. Electrical Engineering Department Report 92-5-2, University of Delaware, May 1992, 29 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  12. Mills, D.L. A computer-controlled LORAN-C receiver for precision timekeeping. Electrical Engineering Department Report 92-3-1, University of Delaware, March 1992, 63 pp. Abstract: PostScript | PDF, Body: PostScript | PDF, Appendix A Host Computer Interface: PostScript | PDF, Appendix B Program Listing: PostScript | PDF, Appendix C Schematic Drawings: PostScript | PDF