Network classless time protocol based on clock offset optimization

ABSTRACT

Time synchronization is critical in distributed environments. A variety of network protocols, middleware and business applications rely on proper time synchronization across the computational infrastructure and depend on the clock accuracy. The Network Time Protocol (NTP) is the current widely accepted standard for synchronizing clocks over the Internet. NTP uses a hierarchical scheme in order to synchronize the clocks in the network. In this paper we present a novel non-hierarchical peer-to-peer approach for time synchronization termed CTP--Classless Time Protocol. This approach exploits convex optimization theory in order to evaluate the impact of each clock offset on the overall objective function. We define the clock offset problem as an optimization problem and derive its optimal solution. Based on the solution we develop a distributed protocol that can be implemented over a communication network, prove its convergence to the optimal clock offsets and show its properties. For compatibility, CTP may use the packet format and number of measurements used by NTP. We also present methodology and numerical results for evaluating and comparing the accuracy of time synchronization schemes. We show that the CTP outperforms hierarchical schemes such as NTP in the sense of clock accuracy with respect to a universal clock.

REFERENCES

• 1: [1] "Task 4-Using Syslog, NTP and modem call records to isolate and troubleshoot faults," in Basic Dial NMS Implementation Guide. San Jose, CA: Cisco, 2000 [Online]. Available: http://www.cisco.com/uni-vercd/cc/td/doc/cisintwk/intsolns/dialsol/nmssol/syslog.htm
• 2: William Su , Sung-Ju Lee , Mario Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management, v.11 n.1, p.3-30, January–February 2001 [doi>10.1002/nem.386]
• 3: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 4: 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]
• 5: 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]
• 6: [6] D. L. Mills, "Internet time synchronization: The network time protocol," IEEE Trans. Commun., vol. COM-39, no. 10, pp. 1482-1493, Oct. 1991.
• 7: David L. Mills, Improved algorithms for synchronizing computer network clocks, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.245-254, June 1995 [doi>10.1109/90.392384]
• 8: D. Mills, Network Time Protocol (Version 3) Specification, Implementation, RFC Editor, 1992
• 9: Omer Gurewitz , Israel Cidon , Moshe Sidi, Network Time Synchronization Using Clock Offset Optimization, Proceedings of the 11th IEEE International Conference on Network Protocols, p.212, November 04-07, 2003
• 10: [10] J. Elson, R. Karp, C. Papadimitriou, and S. Shenker, "Global synchronization in sensornets," in Proc. 6th Latin American Symposium on Theoretical Informatics (LATIN'04), Buenos Aires, 2004, pp. 609-624.
• 11: [11] Q. Li and D. Rus, "Global clock synchronization in sensor networks," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 564-574.
• 12: 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
• 13: [13] S. Moon, P. Skelley, and D. Towsley, "Estimation and removal of clock skew from network delay measurements," in Proc. IEEE INFOCOM, New York, 1999, pp. 227-234.
• 14: [14] L. Zhang, Z. Liu, and C. H. Xia, "Clock synchronization algorithms for network measurements," in Proc. IEEE INFOCOM, New York, 2002, pp. 160-169.
• 15: [15] B. Patt-Shamir, "A theory of clock synchronization," Ph.D. dissertation, Massachusetts Inst. Technol., Cambridge, MA, 1994.
• 16: [16] O. Gurewitz and M. Sidi, "Estimating one-way delays from cyclic-path delay measurements," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 1038-1044.
• 17: Masato Tsuru , Tetsuya Takine , Yuji Oie, Estimation of Clock offset from one-way delay measurement on asymmetric paths, Proceedings of the 2002 Symposium on Applications and the Internet (SAINT) Workshops, p.126, January 28-February 01, 2002
• 18: [18] J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 3rd ed. New York: Springer-Verlag, 2002.
• 19: [19] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations. Philadelphia, PA: SIAM, 1995.
• 20: [20] O. Gurewitz, I. Cidon, and M. Sidi, Network classless time protocol based on clock offset optimization, CCIT, Tech. Rep. 430, Jun. 2003 [Online]. Available: http://www.ee.technion.ac.il/CCIT/info/Publications/Articles/430.pdf
• 21: [21] R. T. Rockafellar, Convex Analysis. Princeton, NJ: Princeton Univ. Press, 1972.
• 22: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 23: [23] N. Minar, "A survey of the NTP network," MIT, Dec. 1999 [Online]. Available: http://www.media.mit.edu/nelson/research/ntp-survey99/
• 24: [24] A. Mukherjee, "On the dynamics and significance of low frequency components of Internet load," Internetworking: Research and Experience , vol. 5, no. 4, pp. 163-205, 1994.
• 25: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 26: [26] A. Corlett, D. I. Pullin, and S. Sargood, "Statistics of one-way Internet packet delays," presented at the 53rd IETF, Minneapolis, MN, Mar. 2002.
• 27: [27] E. W. Zegura, K. Calvert, and S. Bhattacharjee, "How to model an internetwork," in Proc. IEEE INFOCOM, San Francisco, CA, 1996, pp. 594-602.
• 28: [28] 802.20 Evaluation Criteria-Ver. 05. Draft Permanent Document of IEEE Working Group 802.20. Sep. 2003.
• 29: [29] R. Keralapura, C. N. Chuah, G. Iannaccone, and S. Bhattacharrya, "Service availability: A new approach to characterizing network topologies," in Proc. IEEE IWQoS, Jun. 2004, pp. 232-241.
• 30: [30] M. A. Lombardi, NIST Time and Frequency Services NIST, Special Publication 432, 2002, p. 59.

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.2 Network Protocols
      C.2.4 Distributed Systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies

General Terms:
Design, Management, Performance

Keywords:
UTC, classless time protocol (CTP), estimation, measurements, network management, one-way delay, time synchronization