Computer Network Time Synchronization

Preface

Mumpsimus (n): Middle English noun denoting an incorrigible dogmatic old pendant - jokingly called a foolosopher about 1550 - which grew to include any incorrect opinion stubbornly clung to.

Jeffrey Kacirk
Forgotten English, 1997

This book is all about wrangling a herd of network computers so that all display the correct time. This may seem like a really narrow business, but the issues go far beyond winding the clock on your display taskbar. Carefully coordinated, reliable and accurate time is vital for traffic control in the air and on the ground, buying and selling things and TV network programming. Even worse, ill-gotten time might cause DNS caches to expire and the entire Internet to implode on the root servers, which was considered a serious threat on the eve of the Millennium in 1999. Critical data files might expire before they are created, and an electronic message might arrive before it was sent. Reliable and accurate computer time is necessary for any real-time distributed computer application, which is what much of our public infrastructure has become.

This book speaks to the technological infrastructure of time dissemination, distribution and synchronization, specifically the architecture, protocols and algorithms of the Network Time Protocol (NTP). NTP has been active in one form or another for over two decades on the public Internet and numerous private networks on the nether side of firewalls. Just about everything today that can be connected to a network wire has support for NTP - print servers, wi-fi access points, routers of every stripe and even battery backup systems. NTP subnets are in space, on the seabed, onboard warships and on every continent, including Antarctica. NTP comes with Windows/XP and NT2000, as well as all flavors of Unix. About 25 million clients implode on the NTP time servers at NIST alone.

This book is designed primarily as a reference book, but is suitable for a specialized university course at the senior and graduate level in both computer engineering and computer science departments. Some chapters may go down more easily for an electrical engineer, especially those dealing with mathematical concepts; others more easily for a computer scientist, especially those dealing with computing theory, but each will learn from the other. There are things for mathematicians and cryptographers, even something for historians.

The presentation in this book begins in Chapter 1 with a general overview of the architecture, protocols and algorithms for computer network timekeeping. This includes how time flows from national time standards via radio, satellite and telephone modem to hundreds of primary time servers, then via NTP subnets to millions of secondary servers and clients at increasing stratum levels. Chapter 2 describes the principal components of an NTP client and how it works with redundant servers and diverse network paths. Chapter 3 contains an in-depth description of the critical algorithms so important for consistency, accuracy and reliability which any good computer scientist will relish. The actual algorithm used to adjust the computer clock is so special that Chapter 4 is completely dedicated to its description and operation. As the word network is prominent in the title of this book, Chapter 5 presents an overview of the principles guiding network configuration and resource discovery.

Along about now, you should ask how well the contraption works. Chapter 6 evaluates the performance of typical NTP subnets with respect to network delay variations and clock frequency errors. It shows the results of a survey of NTP servers and clients to determine typical time and frequency error distributions. It then analyzes typical NTP configurations to determine such things as processor and network overhead and engineered defenses against flood attacks.

An NTP subnet ultimately depends on national and international means to disseminate standard time to the general population, including Internet computers. Chapter 7 describes a number of systems and drivers for current radio, satellites and telephone modem dissemination means. Chapter 8 describes specialized kernel software used in some computer systems to improve timekeeping accuracy and precision ultimately to the order of nanoseconds.In modern experience we have learned that computer security is a very serious business, and timekeeping networks are not exempt. What may be different for NTP subnets is that by their very nature, the data exchanged are public values transmitted from public servers over public networks, so servers and clients of public networks might be seen as very inviting targets for tempo-terrorists. In addition, there are devilishly intricate issues when dated material such as cryptographic certificates must be verified by the protocol that uses them. Chapter 9 describes the NTP security model and authentication protocol, which shares headers with NTP, while Chapter 10 describes a number of cryptographic algorithms designed to prove industrial-strength group membership.

Computer network timekeeping, like many other physical systems is not without errors, both deterministic and stochastic. Chapter 11 contains an intricate analysis of errors inherent in reading the system clock and disciplining its time and frequency relative to the clock in another computer. Chapter 12 is on modelling and analysis of the computer clock, together with a mathematical description of its characteristics.

Timekeeping on the global scale is a discipline all its own. Chapter 13 describes how we reckon the time according to the stars and atoms. It explains the relationships between the international timescales TAI, UTC and JDN dear to physicists and navigators and the NTP timescale. If we use NTP for historic and future dating, there are issues of rollover and precision. Even the calendar gets in the act, as the astronomers have their ways and the historians theirs. Since the topic of history comes up, Chapter 15 reveals the events of historic interest since computer network timekeeping started over two decades ago.

While a detailed description of a typical NTP implementation is beyond the scope of this book, it may be of some interest to explore its general architecture, organization and operation. Chapter 14 includes a set of flow charts, state variables, processes and routines of the current public software implementation, together with an explanation of how it operates. Finally, Chapter 16 is a bibliography of papers, reports and other documents relevant to computer network timekeeping.

The book in its entirety would certainly be of interest to an NTP administrator as a reference volume. It is would be useful as a case study involving a widely deployed, distributed application with technology drawn from diverse interdisciplinary fields. The algorithms described in various chapters could be useful as a companion to a computer science book on algorithms. As a case study in cryptographic techniques, the material in Chapters 9 and 10 is particularly relevant, as the security model for NTP is complicated by the need to authenticate the server and reckon the time simultaneously. Astronomers and physicists will find the clock discipline algorithm described in Chapter 4 similar to but different from the algorithms they are used to. Engineers will find Chapters 4, 11 and 12 relevant to a course on control feedback systems.

The development, deployment and maintenance of NTP in the Internet has been a daunting task made possible by over four dozen volunteers from several professions and from several countries. NTP enthusiasts have much in common with radio amateurs (example myself), even if the boss sees little need to wind the clock to the nanosecond. We have been fortunate that several manufacturers have donated radio and satellite receivers, computers and cool gadgets over the years. Especially valued is the mutual support of Judah Levine at NIST and Richard Schmidt at USNO, intrepid timekeepers in their own right.

David L. Mills
September 2005

Table of Contents

1 Basic Concepts
2 How NTP Works
3 In the Belly of the Beast
4 Clock Discipline Algorithm
5 NTP Subnet Configuration
6 NTP Performance in the Internet
7 Primary Servers and Reference Clocks
8 Kernel Timekeeping Support
9 Cryptographic Authentication
10 Identity Schemes
11 Analysis of Errors
12 Modeling and Analysis of Computer Clocks
13 Metrology and Chronometry of the NTP Timescale
14 NTP Reference Implementation
15 Technical History of NTP
16 Bibliography on Computer Network Time Synchronization