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 and analysis," RFC 1305 (Draft Standard), Mar. 1992 {Online}. Available: http://www.ietf.org/rfc/rfc1305.txt
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. P. Veríssimo, L. Rodrigues, and A. Casimiro, "Cesiumspray: A precise and accurate global time service for large-scale systems," Real-Time Syst., vol. 12, no. 3, pp. 243-294, 1997.
5. M. Mock, R. Frings, E. Nett, and S. Trikaliotis, "Continuous clock synchronization in wireless real-time applications," in Proc. 19th IEEE Symp. Reliable Distributed Systems (SRDS'00), Oct. 2000, pp. 125-132.
6. J. Elson, L. Girod, and D. Estrin, "Fine-grained network time synchronization using reference broadcasts," in Proc. 5th USENIX Symp. Operating Systems Design and Implementation (OSDI'02), Dec. 2002, pp. 147-163.
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. D. Veitch, S. Babu, and A. Pàsztor, "Robust synchronization of software clocks across the Internet," in Proc. 4th ACM SIGCOMM Internet Measurement Conf. (IMC'04), Oct. 2004, pp. 219-232.
15. H. Kopetz and W. Ochsenreiter, "Clock synchronization in distributed real-time systems," IEEE Trans. Commun., vol. 36, no. 8, pp. 933-940, 1987.
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. C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing," in Proc. 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99), Feb. 1999, pp. 90-100.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network services

    • Network management

    • Network monitoring