On the time synchronization of distributed log files in networks with local broadcast media

ABSTRACT

Real-world experiments in computer networks typically result in a set of log files, one for each system involved in the experiment. Each log file contains event timestamps based on the local clock of the respective system. These clocks are not perfectly accurate, and deviate from each other. For a thorough analysis, however, a common time basis is necessary. In this paper, we tackle the fundamental problem of creating such a common time base for experiments in networks with local broadcast media, where transmissions can be received by more than one node. We show how clock deviations and event times can be estimated with very high accuracy, without introducing any additional traffic in the network. The proposed method is applied after the experiment is completed, using just the set of local log files as its input. It leads to a large linear program with a very specific structure. We exploit the structure to solve the synchronization problem quickly and efficiently, and present an implementation of a specialized solver. Furthermore, we give analytical and numerical evaluation results and present real-world experiments, all underlining the performance and accuracy of the method.

REFERENCES

• 1: D. L. Mills, "Internet time synchronization: The network time protocol," in Global States and Time in Distributed Systems, Z. Yang and T. A. Marsland, Eds. New York: IEEE Computer Society Press, 1994.
• 2: D. Mills, Network Time Protocol (Version 3) Specification, Implementation, RFC Editor, 1992
• 3: K. Römer, P. Blum, and L. Meier, "Time synchronization and calibration in wireless sensor networks," in Handbook of Sensor Networks: Algorithms and Architectures, I. Stojmenovic, Ed. Hoboken, NJ: Wiley, Sep. 2005, pp. 199-237.
• 4: Paulo Veríssimo , Luís Rodrigues , Antonio Casimiro, CesiumSpray>: a Precise and Accurate Global Time Servicefor Large-scale Systems, Real-Time Systems, v.12 n.3, p.243-294, May 1997 [doi>10.1023/A:1007949113722]
• 5: Michael Mock , Reiner Frings , Edgar Nett , Spiro Trikaliotis, Continuous Clock Synchronization in Wireless Real-Time Applications, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems, p.125, October 16-18, 2000
• 6: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 7: R. M. Karp, J. Elson, C. H. Papadimitriou, and S. Shenker, "Global synchronization in sensornets," in Proc. 6th Latin American Symp. Theoretical Informatics (LATIN'04), Apr. 2004, pp. 609-624.
• 8: A. Duda, G. Harrus, Y. Haddad, and G. Bernard, "Estimating global time in distributed systems," in Proc. 7th Int. Conf. Distributed Computing Systems (ICDCS'87), Sep. 1987, pp. 299-306.
• 9: P. Ashton, "Algorithms for off-line clock synchronization," Dept. Comput. Sci., Univ. Canterbury, U.K., Tech. Rep. TR COSC 12/95, Dec. 1995.
• 10: S. B. Moon, P. Skelly, and D. F. Towsley, "Estimation and removal of clock skew from network delay measurements," in Proc. IEEE INFOCOM'99 , Mar. 1999, pp. 227-234.
• 11: L. Zhang, Z. Liu, and C. H. Xia, "Clock synchronization algorithms for network measurements," in Proc. IEEE INFOCOM'02, Jun. 2002, pp. 160-169.
• 12: D. W. Allan, "Time and frequency (time-domain) characterization, estimation, and prediction of precision clocks and oscillators," IEEE Trans. Ultrason. Ferroelectr. Freq. Contr., vol. UFFC-34, no. 6, pp. 647-654, Nov. 1987.
• 13: W. Kiess and M. Mauve, "Real-world evaluation of mobile ad hoc networks," in Multi-Hop Ad Hoc Networks From Theory to Reality, M. Conti, J. Crowcroft, and A. Passarella, Eds. Hauppauge, NY: Nova Science, 2007, pp. 1-22.
• 14: 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]
• 15: H. Kopetz , W. Ochsenreiter, Clock synchronization in distributed real-time systems, IEEE Transactions on Computers, v.36 n.8, p.933-940, Aug. 1987 [doi>10.1109/TC.1987.5009516]
• 16: D. Applegate, W. Cook, S. Dash, and M. Mevenkamp, QSopt Linear Programming Solver. ver. 1.01 [Online]. Available: http://www2.isye. gatech.edu/~wcook/qsopt/
• 17: S. Mehrotra, "On the implementation of a primal-dual interior point method," SIAM J. Optimization, vol. 2, no. 4, pp. 575-601, 1992.
• 18: J. Nocedal and S. J. Wright, Numerical Optimization. Berlin, Germany: Springer, 1999.
• 19: J. F. Sturm, O. Romanko, and I. Pólik, SeDuMi. ver. 1.1R2 [Online]. Available: http://www.sedumi.mcmaster.ca/
• 20: B. Scheuermann, W. Kiess, M. Roos, F. Jarre, and M. Mauve, "Error bounds and consistency of maximum likelihood time synchronization," Dept. Comput. Sci., Heinrich Heine Univ., Düsseldorf, Germany, Tech. Rep. TR-2008-001, 2008.
• 21: The ns-2 Network Simulator. ver. 2.30 [Online]. Available: http://www.isi.edu/nsnam/ns
• 22: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Management, Performance

Keywords:
broadcast channels, experiments, offline time synchronization, synchronization, timestamps