Robust synchronization of absolute and difference clocks over networks

ABSTRACT

We present a detailed re-examination of the problem of inexpensive yet accurate clock synchronization for networked devices. Based on an empirically validated, parsimonious abstraction of the CPU oscillator as a timing source, accessible via the TSC register in popular PC architectures, we build on the key observation that the measurement of time differences, and absolute time, requires separate clocks, both at a conceptual level and practically, with distinct algorithmic, robustness, and accuracy characteristics. Combined with round-trip time based filtering of network delays between the host and the remote time server, we define robust algorithms for the synchronization of the absolute and difference TSCclocks over a network. We demonstrate the effectiveness of the principles, and algorithms using months of real data collected using multiple servers. We give detailed performance results for a full implementation running live and unsupervised under numerous scenarios, which show very high reliability, and accuracy approaching fundamental limits due to host system noise. Our synchronization algorithms are inherently robust to many factors including packet loss, server outages, route changes, and network congestion.

REFERENCES

• 1: D. L. Mills, Internet Time Synchronization: The Network Time Protocol, RFC Editor, 1989
• 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: 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
• 5: RIPE NCC Test Traffic Measurements. [Online]. Available: http://www.ripe.net/ttm/
• 6: Darryl Veitch , Satish Babu , Attila Pàsztor, Robust synchronization of software clocks across the internet, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028817]
• 7: D. Mills, "The network computer as precision timekeeper," in Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting, Reston, VA, Dec. 1996, pp. 96-108.
• 8: A. Pásztor and D. Veitch, "A precision infrastructure for active probing," in Proc. Passive and Active Measurement Workshop (PAM2001), Amsterdam, The Netherlands, Apr. 23-24, 2001, pp. 33-44.
• 9: E. Corell, P. Saxholm, and D. Veitch, "A user friendly TSC clock," in Proc. Passive and Active Measurement Conf. (PAM2006), Adelaide, Australia, Mar. 30-31, 2006, 10 pp.
• 10: Endace Measurement Systems. [Online]. Available: http://www.endace.com/
• 11: 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]
• 12: P. Abry, D. Veitch, and P. Flandrin, "Long-range dependence: Revisiting aggregation with wavelets," J. Time Series Analysis, vol. 19, no. 3, pp. 253-266, May 1998.
• 13: Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
• 14: J. Ridoux and D. Veitch, "A methodology for clock benchmarking," in Tridentcom, Orlando, FL, May 21-23, 2007, pp. 141-150.
• 15: J. Ridoux and D. Veitch, "Ten microseconds over LAN, for free," in Proc. Int. IEEE Symp. Precision Clock Synchronization for Measurement, Control and Communication (ISPCS'07), Vienna, Austria, Oct. 1-3, 2007, pp. 105-109.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Measurement techniques

General Terms:
Management, Measurement, Performance

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