Robust synchronization of software clocks across the internet

ABSTRACT

Accurate, reliable timestamping which is also convenient and inexpensive is needed in many important areas including real-time network applications and network measurement. Recently the TSC register, which counts CPU cycles in popular PC architectures, was proposed as the basis of a new software clock which in terms of rate performance performs as well as more expensive GPS alternatives. Smooth and precise clock rate is essential to measure time <i>differences</i> accurately. We show how to define a TSC based clock which is also accurate with respect to <i>absolute</i> time. The clock is calibrated by processing, in a novel way, timestamps contained in the usual flow of Network Time Protocol (NTP) packets between a NTP server and the existing software clock, and TSC timestamps made independently on the host side. Using real measurements over 4 months, validated with a GPS synchronized hardware timing solution, the algorithm measured absolute time with a median error of only 30 microseconds when using a nearby stratum-1 NTP server. Results for two other servers are given. We also provide new algorithms for the robust determination of clock rate. We exploit the reliability of the available hardware to design synchronization algorithms which are inherently robust to many factors including packet loss, server outages, route changes, temperature environment, and network congestion.

REFERENCES

• 1: D.L. Mills, "Internet time synchronization: the network time protocol," IEEE Trans. Communications, vol. 39, no. 10, pp. 1482--1493, October 1991, Condensed from RFC-1129.
• 2: Cheng Liao , Margaret Martonosi , Douglas W. Clark, Experience with an adaptive globally-synchronizing clock algorithm, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.106-114, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305631]
• 3: Vern Paxson, On calibrating measurements of packet transit times, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.11-21, June 22-26, 1998, Madison, Wisconsin, United States
• 4: Jonas Andren, Magnus Hilding, and Darryl Veitch, "Understanding end-to-end internet traffic dynamics," in IEEE Global Telecommunications Conference (Globecom'98), Sydney, Australia, Nov. 1998, vol. 2, pp. 1118--1122.
• 5: Attila Pásztor , Darryl Veitch, PC based precision timing without GPS, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 6: "RIPE NCC Test Traffic Measurements," http://www.ripe.net/ttm/.
• 7: Attila Pásztor and Darryl Veitch, "Software infrastructure for accurate active probing," http://www.cubinlab.ee.mu.oz.au/probing/software.shtml/.
• 8: Jörg Micheel , Stephen Donnelly , Ian Graham, Precision timestamping of network packets, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505236]
• 9: D.L. Mills, "The network computer as precision timekeeper," in Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting, Reston VA, December 1996, pp. 96--108.
• 10: Attila P&225;sztor and Darryl Veitch, "A precision infrastructure for active probing," in Passive and Active Measurement Workshop (PAM2001), Amsterdam, The Netherlands, 23--24 April 2001, pp. 33--44.
• 11: Victor Yodaiken, "The RTLinux Manifesto," Tech. Rep., Department of Computer Science, New Mexico Institute of Technology, 1999, available at http://www.rtlinux.org.
• 12: P. Abry, D. Veitch, and P. Flandrin, "Long-range dependence: revisiting aggregation with wavelets," Journal of Time Series Analysis, vol. 19, no. 3, pp. 253--266, May 1998, Bernoulli Society.
• 13: "Cooperative Association for Internet Data Analysis (CAIDA) Skitter project," http://www.caida.org/tools/measurement/skitter/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.m Miscellaneous

General Terms:
Algorithms, Reliability

Keywords:
GPS, NTP, network measurement, round-trip time, software clock, synchronization, timing