Network Time Synchronization Research Project

gif

Maya glyph alautun

Researchers involved: David Mills, graduate students and many volunteers

Funding: Defense Advanced Research Projects Agency (DARPA), National Science Foundation (NSF), Navy Surface Weapons Center (NSWC) and Jet Propulsion Laboratory/NASA

Briefing Slides

Note: The recommended format is PDF and Adobe Acrobat Reader 3 or later. Due to increasing browser butchery with Microsoft Power Point HTML, this format has been discontinued.

NTPv4 Specification Documents

The NTPv4 protocol specification began life as: Mills, D.L. Network Time Protocol Version 4 Reference and Implementation Guide. Electrical and Computer Engineering Technical Report 06-06-1, University of Delaware, June 2006, 83 pp, PDF. It was subsequently reformatted as an Internet Draft and published as the following document.

The NTPv4 Autokey specification began life as: Mills, D.L. The Autokey Security Architecture, Protocol and Algorithms. Electrical and Computer Engineering Technical Report 06-1-1, University of Delaware, January 2006, 59 pp, PDF. It was subsequently reformatted as an Internet Draft and published as the following document.

The following document discusses software, hardware and driver timestamping schemes. It analyzes the errors with each scheme and combinations of schemes. It makes a specific recommendation on interoperation between all three schemes to achieve accuracies approaching IEEE 1588.

Importance of the Problem

The Network Time Protocol (NTP) is widely used in the Internet to synchronize computer clocks to national standard time. The NTP architecture, protocol and algorithms have evolved well over two decades to the NTP Version 3 specification and implementations for Unix, VMS and Windows, as well as the NTP Version 4 implementation now being deployed. The architecture and security models provide for operation in point-to-point (unicast) and point-to-multipoint (multicast) modes, and include provisions for secure authentication using both symmetric key and public key cryptography.

Previous funded research has resulted in a series of improvements in accuracy and reliability of the protocol and supporting algorithms. Used in the Internet of today with computers ranging from personal workstations to supercomputers, NTP provides accuracies generally in the range of a millisecond in LANs and up to a few tens of milliseconds in the global Internet. When kernel support for precision timing signals, such as a pulse-per-second (PPS) signal, is available the accuracy can be improved ultimately to the order of one nanosecond in time and one nanosecond per second in frequency.

The current NTP Version 4 reference implementation represents a significant enhancement to the existing protocol, architecture and algorithms of NTP Version 3. Specifically, these involve provisions for an autonomous configuration capability which provides for automatic server discovery and secure server authentication. Both of these enhancements are necessary in order for large, diversified synchronization subnets to survive electronic warfare attacks which can compromise NTP servers or destabilize the source mitigation and clock discipline algorithms. The design of robust protocols and algorithms which survive such attacks presents a significant challenge, especially for networks with many thousands of servers and clients such as the existing public Internet and private enterprise networks.

Brief Description of Work and Results

In order to provide specific accuracy and reliability requirements, NTP requires configuration engineering specific to each time server and client site. However, in a tactical network subject to damage and repair, as well as a widely deployed real-time network such as the Defense Simulation Internet (DSI), manual configuration engineering is not acceptable. Our research effort is designed to develop an autonomous configuration capability for NTP Version 4 using multicast methods to achieve diversity and redundancy, as well as cryptographically secure source discovery.

A robust security model has long been an intrinsic feature in the current and previous NTP versions. However, this model does not scale well to very large networks which may fragment and reform frequently due to attack and repair. The NTP Version 3 security model, which is based on symmetric key cryptography with predistributed keys, does not work well in multicast modes and imposes an excessive burden on the key management and distribution scheme in cases where keys can be compromised. These problems are exacerbated by the need to coordinate key management and time synchronization, since each of these services depends on the other.

Our approach involves the use of public key cryptography and the crafted Autokey protocol, which provides reliable key distribution and management functions while avoiding excessive processor and memory resources. The algorithms use standard message digest algorithms and timestamped digital signatures combined with backwards computable hash functions for all modes, including multicast modes. All revealed values, including public keys and certificates, are secured using public key cryptography, but this is done infrequently in a manner that does not degrade synchronization quality.

A goal of our ongoing research is refinement of the IP multicast support in NTP Version 4. This the new Manycast mode, in which potential clients troll for prospective servers in the near neighborhood using an expanding-ring search. A number of crafted algorithms are used to minimize excessive network traffic and insure a near-optimal client/server configuration. The scheme is exceptionally robust, in that server and network failures are automatically detected and the NTP subnet automatically reconfigured in response.

In a related effort, the precision time kernel support now incorporated in the kernels for Tru64, Solaris, Linux and FreeBSD has been updated to improve accuracy and resolution to the nanosecond. In addition, a plan has been worked out with NIST for the distribution of International Atomic Time (TAI) via NTP using the Autokey protocol. A new project is extending NTP technology to the interplanetary and deep space environment, especially Mars exploration missions. Finally, Internet historians may be interested in a somewhat salty chronicle of NTP history since its first tick in a Fuzzball circa 1981. These activities are described in papers cited at the end of this page.

Present Status

The NTP Version 4 software distribution and documentation continues to evolve with incremental refinements in the source mitigation and clock discipline algorithms. The software and documentation have been incorporated in a CVS repository to assist in developer coordination. New reference clock drivers have been contributed for a total of 44 different drivers, including those operating directly from the audio signal of a communications receiver. The code has been ported to several new architectures and operating systems for a total of 24 ports. A web site www.ntp.org has been established along with mailing lists for bug reports and the volunteer maintenance corps.

A major milestone has been passed with new support for the IPv6 addressing family in addition to the original IPv4 addressing family. All NTP modes and cryptographic means can operate in both families, even at the same time in one machine. Version 2 of the Autokey public key cryptography support has been completed and tested. Version 2 includes five identity schemes based on certificate trails and challenge/response algorithms. Simplified means to generate and install the required public keys, certificates and identity values have been implemented. Manycast mode support has been refined and tested in a production environment.

Support for IPv6 and both Autokey and Manycast are now in the NTP Version 4 distribution available for public download from the NTP web site. This software has been deployed in about ten percent of the Internet population (including Antarctica), as suggested by monitoring data for a busy primary server here.

Future Plans

We expect to refine the NTP Autokey and Manycast models to improve stability in networks with large numbers of servers and clients. The means proposed to do this involve a whisper campaign where Manycast servers keep track of dependent clients by means of specific Autokey messages. The servers would then run load balancing and stratum selection algorithms suggested in a recent dissertation. Finally, we expect to develop and publish a definitive protocol specification and vulnerability analysis.

Selected Publications

  1. Mills, D.L. Network Time Protocol Version 4 Reference and Implementation Guide. Electrical and Computer Engineering Technical Report 06-06-1, University of Delaware, June 2006, 83 pp, PDF
  2. Mills, D.L. The Autokey security architecture, protocol and algorithms. Electrical and Computer Engineering Technical Report 06-1-1, University of Delaware, January 2006, 59 pp. PDF
  3. Mills, D., D. Plonka and J. Montgomery. Simple network time protocol (SNTP) version 4 for IPv4, IPv6 and OSI. Network Working Group Report RFC-4330, University of Delaware, December 2005, 27 pp. ASCII Major revision and update of: Ibid. Network Working Group Report RFC-2030, University of Delaware, October 1996, 20 pp.
  4. Mills, D.L., J. Levine, R. Schmidt and D. Plonka. Coping with overload on the Network Time Protocol public servers. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Washington DC, December 2004), 5-16. Paper: PostScript | PDF, Slides: PostScript | PDF | PowerPoint
  5. Mills, D.L. The Autokey security architecture, protocol and algorithms. Electrical and Computer Engineering Technical Report 04-4-1, University of Delaware, April 2004, 57 pp. PDF
  6. Mills, D.L. A brief history of NTP time: confessions of an Internet timekeeper. ACM Computer Communications Review 33, 2 (April 2003), 9-22. PostScript | PDF
  7. Levine, J., and D. Mills. Using the Network Time Protocol to transmit International Atomic Time (TAI). Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, November 2000). Paper: PostScript | PDFMinar, N. A survey of the NTP network. MIT Media Laboratory, December 1999, 10 pp. PostScript | PDF
  8. Mills, D.L. Cryptographic authentication for real-time network protocols. In: AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 45 (1999), 135-144. Paper: PostScript | PDF, Slides: PostScript | PowerPoint
  9. Mills, D.L. Adaptive hybrid clock discipline algorithm for the Network Time Protocol. IEEE/ACM Trans. Networking 6, 5 (October 1998), 505-514. PostScript | PDF.
  10. Mills, D.L., A. Thyagarajan and B.C. Huffman. Internet timekeeping around the globe. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Long Beach CA, December 1997), 365-371. Paper: PostScript | PDF Slides: PostScript | PowerPoint | PDF
  11. Sethi, A.S., H. Gao, and D.L. Mills. Management of the Network Time Protocol (NTP) with SNMP. Computer and Information Sciences Report 98-09, University of Delaware, November 1997, 32 pp. PostScript | PDF
  12. Mills, D.L. Clock discipline algorithms for the Network Time Protocol Version 4. Electrical Engineering Report 97-3-3, University of Delaware, March 1997, 35 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  13. Mills, D.L. Authentication scheme for distributed, ubiquitous, real-time protocols. Proc. Advanced Telecommunications/Information Distribution Research Program (ATIRP) Conference (College Park MD, January 1997), 293-298. Paper: PostScript | PDF Slides: PostScript | PowerPoint | PDF
  14. Mills, D.L. The network computer as precision timekeeper. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, December 1996), 96-108. Paper: PostScript | PDF Slides: PostScript | PowerPoint | PDF.
  15. Mills, D.L. Proposed authentication enhancements for the Network Time Protocol version 4. Electrical Engineering Report 96-10-3, University of Delaware, October 1996, 36 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  16. Mills, D.L. Simple network time protocol (SNTP) version 4 for IPv4, IPv6 and OSI. Network Working Group Report RFC-2030, University of Delaware, October 1996, 18 pp. ASCII Major revision and update of: Ibid. Network Working Group Report RFC-1769, University of Delaware, March 1995, 14 pp. ASCII Also published (with figures) as Ibid Electrical Engineering Department Report 96-10-2, University of Delaware, October 1996, 14 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  17. Mills, D.L. Improved algorithms for synchronizing computer network clocks. IEEE/ACM Trans. Networks 3, 3 (June 1995), 245-254. PostScript | PDF Revised from: ibid. Proc. ACM SIGCOMM 94 Symposium (London UK, September 1994), 317-327. PostScript | PDF
  18. Mills, D.L. Simple network time protocol (SNTP) version 4 for IPv4, IPv6 and OSI. Network Working Group Report RFC-2030, University of Delaware, October 1996, 18 pp. ASCII Major revision and update of: Ibid. Network Working Group Report RFC-1769, University of Delaware, March 1995, 14 pp. ASCII Also published (with figures) as Ibid Electrical Engineering Department Report 96-10-2, University of Delaware, October 1996, 14 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  19. Mills, D.L. Proposed authentication enhancements for the Network Time Protocol version 4. Electrical Engineering Report 96-10-3, University of Delaware, October 1996, 36 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  20. Mills, D.L, and A. Thyagarajan. Network time protocol version 4 proposed changes. Electrical Engineering Department Report 94-10-2, University of Delaware, October 1994, 32 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  21. Mills, D.L. Unix kernel modifications for precision time synchronization. Electrical Engineering Department Report 94-10-1, University of Delaware, October 1994, 24 pp. Abstract: PostScript | PDF, Body: PostScript | PDF Major revision and update of: Network Working Group Report RFC-1589, University of Delaware, March 1994. 31 pp. ASCII
  22. Mills, D.L. A kernel model for precision timekeeping. Network Working Group Report RFC-1589, University of Delaware, March 1994. 31 pp. ASCII
  23. Mills, D.L. Precision synchronization of computer network clocks. Electrical Engineering Department Report 93-11-1, University of Delaware, November 1993, 66 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  24. Mills, D.L. Modelling and analysis of computer network clocks. Electrical Engineering Department Report 92-5-2, University of Delaware, May 1992, 29 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  25. Mills, D.L. Network Time Protocol (Version 3) specification, implementation and analysis. Network Working Group Report RFC-1305, University of Delaware, March 1992, 113 pp. Abstract: PostScript | PDF, Body: PostScript | PDF, Appendices: PostScript | PDF Revised from: Electrical Engineering Department Report 90-6-1, University of Delaware, June 1990, 103 pp. Abstract: PostScript | PDF, Body: PostScript | PDF, Appendices: PostScript | PDF
  26. Mills, D.L. On the chronology and metrology of computer network timescales and their application to the Network Time Protocol. ACM Computer Communications Review 21, 5 (October 1991), 8-17. PostScript | PDF
  27. Mills, D.L. Internet time synchronization: the Network Time Protocol. IEEE Trans. Communications COM-39, 10 (October 1991), 1482-1493. PostScript | PDF Also in: Yang, Z., and T.A. Marsland (Eds.). Global States and Time in Distributed Systems. IEEE Computer Society Press, Los Alamitos, CA, 1994, 91-102. Condensed from: Ibid. Network Working Group Report RFC-1129, University of Delaware, October 1989. Also published as: Electrical Engineering Department Report 89-9-1, University of Delaware, September 1989.
  28. Mills, D.L. On the accuracy and stability of clocks synchronized by the Network Time Protocol in the Internet system. ACM Computer Communication Review 20, 1 (January 1990), 65-75. PostScript | PDF
  29. Mills, D.L. Internet time synchronization: the Network Time Protocol. Network Working Group Report RFC-1129, University of Delaware, October 1989, 27 pp. Abstract: PostScript | PDF, Body: PostScript | PDF Also published as: Electrical Engineering Department Report 89-9-1, University of Delaware, September 1989.
  30. Mills, D.L. Measured performance of the Network Time Protocol in the Internet system. Network Working Group Report RFC-1128. University of Delaware, October 1989, 18 pp. Abstract: PostScript | PDF, Body: PostScript | PDF Also published as: Electrical Engineering Department Report 89-9-3, University of Delaware, September 1989, 16 pp. Abstract: PostScript | PDF, Body: PostScript | PDF
  31. Mills, D.L. Network Time Protocol (Version 2) specification and implementation. Network Working Group Report RFC-1119, 61 pp. University ofDelaware, September 1989. Abstract: PostScript | PDF, Body: PostScript | PDF Also published as: Electrical Engineering Department Report 89-9-2, University of Delaware, September 1989. Abstract: PostScript | PDF, Body: PostScript | PDF
  32. Mills, D.L. Network Time Protocol (Version 1) specification and implementation. Network Working Group Report RFC-1059. University of Delaware, July 1988. ASCII. Also published as: Electrical Engineering Department Report 88-4-1, University of Delaware, May 1988.
  33. Mills, D.L. A distributed-protocol authentication scheme. Network Working Group Report RFC-1004, University of Delaware, April 1987. ASCII