Article

Free access

Improved algorithms for synchronizing computer network clocks

Author:

David L. MillsAuthors Info & Claims

SIGCOMM '94: Proceedings of the conference on Communications architectures, protocols and applications

Pages 317 - 327

https://doi.org/10.1145/190314.190343

Published: 01 October 1994 Publication History

Abstract

The Network Time Protocol (NTP) is widely deployed in the Internet to synchronize computer clocks to each other and to international standards via telephone modem, radio and satellite. The protocols and algorithms have evolved over more than a decade to produce the present NTP Version 3 specification and implementations. Most of the estimated deployment of 100,000 NTP servers and clients enjoy synchronization to within a few tens of milliseconds in the Internet of today.

This paper describes specific improvements developed for NTP Version 3 which have resulted in increased accuracy, stability and reliability in both local-area and wide-area networks. These include engineered refinements of several algorithms used to measure time differences between a local clock and a number of peer clocks in the network, as well as to select the best ensemble from among a set of peer clocks and combine their differences to produce a clock accuracy better than any in the ensemble.

This paper also describes engineered refinements of the algorithms used to adjust the time and frequency of the local clock, which functions as a disciplined oscillator. The refinements provide automatic adjustment of message-exchange intervals in order to minimize network traffic between clients and busy servers while maintaining the best accuracy. Finally, this paper describes certain enhancements to the Unix operating system software in order to realize submillisecond accuracies with fast workstations and networks.

References

[1]

Allan, D.W. Time and frequency (time-domain) estimation and prediction of precision clocks and oscillators. IEEE Trans. on Ultrasound, Ferroelectrics, and Frequency Control UFFC-34, 6 (November 1987), 647- 654. Also in: SuUivan, D.B., D.W. Allan, D.A. Howe and F.L. Walls (Eds.). Characterization of Clocks and Oscillators. NIST Technical Note 1337, U.S. Department of Commerce, 1990, 121-128.]]

[2]

Bishop, M. A security analysis of the NTP protocol. Report to the Privacy and Security Research Group. Department of Mathematics and Computer Science, Dartmouth College, June 1990.]]

[3]

Defense Advanced Research Projects Agency. Intemet Protocol. DARPA Network Working Group Report RFC-791, USC Information Sciences institute, September 1981.]]

[4]

Defense Advanced Research Projects Agency. Intemet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences institute, September 1981.]]

[5]

Digital Time Service Functional Specification Version T. 1.0.5. Digital Equipment Corporation, 1989.]]

[6]

Deering, S.E., and D.R. Cheriton. Multicast routing in datagram intemetworks and extended LANs. ACM Trans. Computing Systems 8, 2 (May 1990), 85-100.]]

Digital Library

[7]

Data Encryption Standard. Federal Information Processing Standards Publication 46. National Bureau of Standards, U.S. Department of Commerce, 1977.]]

[8]

Levine, J., M. Weiss, D.D. Davis, D.W. Allan, and D.B. Sullivan. The NIST automated computer time service. J. Research National Institute of Standards and Technology 94, 5 (September-October 1989), 311-321.]]

[9]

Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Communications COM-28, 8 (August 1980), 12~-1266.]]

[10]

Marzullo, K., and S. Owicki. Maintaining the time in a distributed system. ACM Operating Systems Review 19, 3 (July 1985), 44-54.]]

Digital Library

[11]

Mills, D.L. Network Time Protocol (version 2) - specification and implementation. DARPA Network Working Group Report RFC-1119, University of Delaware, September 1989.]]

Digital Library

[12]

Mills, D.L. Measured performance of the Network Time Protocol in the Internet system. ACM Computer Communication Review 20, 1 (January 1990), 65-75.]]

Digital Library

[13]

Mills, D.L. Interact time synchronization: the Network Time Protocol. iEEE Trans. Communications COM-39,10 (October 1991), 1482-1493. Also in: Yang, Z., and T.A. Marsland (F_.ds.). Global States and Time in Distributed Systems, ~ Press, Los Alamitos, CA, 91-102.]]

[14]

Mills, D.L. Network Time Protocol (Version 3) specification, implementation and analysis. DARPA Network Working Group Report RFC-1305, University of Delaware, March 1992, 113 pp.]]

Digital Library

[15]

Mills, D.L. Modelling and analysis of computer network clocks. Electrical Engineering Department Report 92-5-2, University of Delaware, May 1992, 29 pp.]]

[16]

Mills, D.L. Simple Network Time Protocol (SNTP). DARPA Network Working Group Report RFC- 1361, University of Delaware, August 1992, 10 pp.]]

Digital Library

[17]

Mills, D.L. Precision synchronizatin of computer network clocks. Electrical Engineering Department Report 93-11-1, University of Delaware, November 1993, 66 pp.]]

[18]

NIST Time and Frequency Dissemination Services. NBS Special Publication 432 (Revised 1990), National Institute of Science and Technology, U.S. Department of Commerce, 1990.]]

[19]

Postel, J. User Datagram Protocol. DARPA Network Working Group Report RFC-768, USC Information Sciences institute, August 1980.]]

Digital Library

[20]

Postel, J. Time protocol. DARPA Network Working Group Report RFC-868, USC Information Sciences Institute, May 1983.]]

[21]

Ramanathan, P., K.G. Shin and R.W. Buffer. Faulttolerant clock synchronization in distributed systems. IEEE Computer 23,10 (October 1990), 33-42.]]

Digital Library

[22]

MD5 Message-Digest Algorithm, RSA Data Security, Inc., 1990.]]

[23]

Shin, K.G., and P. Ramanathan. Clock synchronization of a large multiproc~ssor system in the presence of malicious faults. IEEE Trans. Computers C-36,1 (January 1987), 2-12.]]

Digital Library

[24]

Vasanthavada, N., and P.N. Marinos. Synchronization of fault-tolerant clocks in the presence of malicious failures. IEEE Trans. Computers C-37, 4 (April 1988), 440-448.]]

Digital Library

Cited By

Khozin MHolzapfel F(2023)External Synchronization of Distributed Redundant Flight Control ComputersSAE International Journal of Aerospace10.4271/01-17-02-001017:2Online publication date: 1-Dec-2023
https://doi.org/10.4271/01-17-02-0010
Курбатов АКондрашов ДДраничников ИПопов Ф(2022)INFORMATION MEASURING SYSTEM STRENGTH TESTS. SYNCHRONIZATION SUBSYSTEM OF MEASURING AND EXECUTIVE EQUIPMENTЮжно-Сибирский научный вестник10.25699/SSSB.2022.41.1.010(17-22)Online publication date: 28-Feb-2022
https://doi.org/10.25699/SSSB.2022.41.1.010
Song ZDang L(2022)Library Personalized Service System Based on Computer Network TechnologySecurity and Communication Networks10.1155/2022/25508202022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2550820
Show More Cited By

Index Terms

Improved algorithms for synchronizing computer network clocks

Recommendations

Precision synchronization of computer network clocks

This paper builds on previous work involving the Network Time Protocol, which is used to synchronize computer clocks in the Internet. It describes a series of incremental improvements in system hardware and software which result in significantly better ...
Improved algorithms for synchronizing computer network clocks

The Network Time Protocol (NTP) is widely deployed in the Internet to synchronize computer clocks to each other and to international standards via telephone modem, radio and satellite. The protocols and algorithms have evolved over more than a decade to ...
A Hybrid Approach for Synchronizing Clocks in Distributed Systems
Cloud Computing – CLOUD 2019
Abstract
The art of synchronizing clocks across a wide area network has got a new dimension when it comes to the reality of achieving the demand for high-accuracy synchronization; even for local or small computing systems. Before implementing any clock ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '94: Proceedings of the conference on Communications architectures, protocols and applications

October 1994

328 pages

ISBN:0897916824

DOI:10.1145/190314

Chairman:
Jon Crowcroft
Univ. College London, UK

ACM SIGCOMM Computer Communication Review Volume 24, Issue 4
Oct. 1994
318 pages
ISSN:0146-4833
DOI:10.1145/190809
Editor:
David Oran
Digital Equipment Corp., Littleton, MA
Issue’s Table of Contents

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COMM94

Sponsor:

SIGCOMM

COMM94: ACM SIGCOMM '94

August 31 - September 2, 1994

London, United Kingdom

Acceptance Rates

SIGCOMM '94 Paper Acceptance Rate 29 of 141 submissions, 21%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
870
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)5

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khozin MHolzapfel F(2023)External Synchronization of Distributed Redundant Flight Control ComputersSAE International Journal of Aerospace10.4271/01-17-02-001017:2Online publication date: 1-Dec-2023
https://doi.org/10.4271/01-17-02-0010
Курбатов АКондрашов ДДраничников ИПопов Ф(2022)INFORMATION MEASURING SYSTEM STRENGTH TESTS. SYNCHRONIZATION SUBSYSTEM OF MEASURING AND EXECUTIVE EQUIPMENTЮжно-Сибирский научный вестник10.25699/SSSB.2022.41.1.010(17-22)Online publication date: 28-Feb-2022
https://doi.org/10.25699/SSSB.2022.41.1.010
Song ZDang L(2022)Library Personalized Service System Based on Computer Network TechnologySecurity and Communication Networks10.1155/2022/25508202022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2550820
Checco ABianchi GLeith D(2017)BLCACM Transactions on Privacy and Security10.1145/304176020:2(1-25)Online publication date: 25-May-2017
https://dl.acm.org/doi/10.1145/3041760
Osterweil LBishop MConboy HPhan HSimidchieva BAvrunin GClarke LPeisert S(2017)Iterative Analysis to Improve Key Properties of Critical Human-Intensive ProcessesACM Transactions on Privacy and Security10.1145/304104120:2(1-31)Online publication date: 15-Mar-2017
https://dl.acm.org/doi/10.1145/3041041
Liu J(2015)A Novel Method for Estimating the Relative Clock Offset between Skew-Free Clocks2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2015.7417249(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/GLOCOM.2015.7417249
Liu J(2014)An Efficient Method of Estimating the Ratio of Clock Frequency2014 IEEE Military Communications Conference10.1109/MILCOM.2014.147(849-858)Online publication date: Oct-2014
https://doi.org/10.1109/MILCOM.2014.147
Liu J(2014)Studying the Effective Bandwidth through the Distribution of One-Way DelaysProceedings of the 2014 IEEE 22nd International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2014.11(11-20)Online publication date: 9-Sep-2014
https://dl.acm.org/doi/10.1109/MASCOTS.2014.11
Jun Liu (2014)A novel method for estimating the variable and constant components of one-way delays without using the synchronized clocks2014 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICCNC.2014.6785479(1028-1033)Online publication date: Feb-2014
https://doi.org/10.1109/ICCNC.2014.6785479
Liu J(2014)A Novel Method for Estimating the Relative Clock Offset between Skew-Free Clocks2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2014.7417249(1-6)Online publication date: Dec-2014
https://doi.org/10.1109/GLOCOM.2014.7417249
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents