Fermat's Library | A Brief History of NTP Time: Confessions of an Internet Timekeeper annotated/explained version.

1

A Brief History of NTP Time: Confessions of an Internet Timekeeper

1,2

David L. Mills, Fellow ACM, Senior Member IEEE

3

Abstract

This paper traces the origins and evolution of the Network Time Protocol (NTP) over two decades of con-

tinuous operation. The technology has been continuously improved from hundreds of milliseconds in the

rowdy Internet of the early 1980s to tens of nanoseconds in the Internet of the new century. It includes a

blend of history lesson and technology reprise, but with overtones of amateur radio when a new country

shows up on the Internet with NTP running.

This narrative is decidedly personal, since the job description for an Internet timekeeper is highly individ-

ualized and invites very few applicants. There is no attempt here to present a comprehensive tutorial, only

a almanac of personal observations, eclectic minutae and fireside chat. Many souls have contributed to the

technology, some of which are individually acknowledged in this paper, the rest too numerous left to

write their own memoirs.

Keywords: computer network, time synchronization,

technical history, algorithmic memoirs

1. Introduction

An argument can be made that the Network Time Proto-

col (NTP) is the longest running, continuously operat-

ing, distributed application in the Internet. As NTP is

approaching its third decade, it is of historic interest to

document the origins and evolution of the architecture,

protocol and algorithms. Not incidentally, NTP was an

active participant in the early development of the Inter-

net technology and its timestamps recorded many mile-

stones in measurement and prototyping programs.

This paper documents significant milestones in the evo-

lution of computer network timekeeping technology

over four generations of NTP to the present. The NTP

software distributions for Unix, Windows and VMS has

been maintained by a corps of almost four dozen volun-

teers at various times. There are too many to list here,

but the major contributors are revealed in the discussion

to follow. The current NTP software distribution, docu-

mentation and related materials, newsgroups and links

are on the web at www.ntp.org. In addition, all papers

and reports cited in this paper (except [23]) are in Post-

Script and PDF at www.eecis.udel.edu/~mills. Further

information, including executive summaries, project

reports and briefing slide presentations are at

www.eecis.udel.edu/~mills/ntp.htm.

There are three main threads interwoven in the follow-

ing. First is a history lesson on significant milestones for

the specifications, implementations and coming-out par-

ties. These milestones calibrate and are calibrated by

developments elsewhere in the Internet community. Sec-

ond is a chronology of the algorithmic refinements lead-

ing to better and better accuracy, stability and robustness

that continue to the present. These algorithms represent

the technical contributions as documented in the refer-

ences. Third is a discussion of the various proof-of-per-

formance demonstrations and surveys conducted over

the years, each attempting to outdo the previous in cali-

brating the performance of NTP in the Internet of the

epoch. Each of these three threads winds through the

remainder of this narrative.

2. On the Antiquity of NTP

NTP’s roots can be traced back to a demonstration at

NCC 79 believed to be the first public coming-out party

of the Internet operating over a transatlantic satellite net-

work. However, it was not until 1981 that the synchroni-

zation technology was documented in the now historic

Internet Engineering Note series as IEN-173 [35]. The

first specification of a public protocol developed from it

1. Sponsored by: DARPA Information Technology Office Order G409/J175, Contract F30602-98-1-0225, and Dig-

ital Equipment Corporation Research Agreement 1417.

2. This document has been submitted for publication. It is provided as a convenience to the technical community

and should not be cited or redistributed.

3. Author’s address: Electrical and Computer Engineering Department, University of Delaware, Newark, DE

19716, mills@udel.edu, http://www.eecis.udel.edu/~mills.

2

appeared in RFC-778 [34]. The first deployment of the

technology in a local network was as an integral func-

tion of the Hello routing protocol documented in RFC-

891 [32], which survived for many years in a network

prototyping and testbed operating system called the

Fuzzball [24].

What later became known as NTP Version 0 was imple-

mented in 1985, both in Fuzzball by this author and in

Unix by Louis Mamakos and Michael Petry at U Mary-

land. Fragments of their code survive in the software

running today. RFC-958 contains the first formal speci-

fication of this version [29], but it did little more than

document the NTP packet header and offset/delay calcu-

lations still used today. Considering the modest speeds

of networks and computers of the era, the nominal accu-

racy that could be achieved on an Ethernet was in the

low tens of milliseconds. Even on paths spanning the

Atlantic, where the jitter could reach over one second,

the accuracy was generally better than 100 ms.

Vers i on 1 o f th e N T P sp e cifi cati o n wa s d oc u me nted

three years later in RFC-1059 [27]. It contained the first

comprehensive specification of the protocol and algo-

rithms, including primitive versions of the clock filter,

selection and discipline algorithms. The design of these

algorithms was guided largely by a series of experi-

ments, documented in RFC-956 [31], in which the basic

theory of the clock filter algorithm was developed and

refined. This was the first version which defined the use

of client/server and symmetric modes and, of course, the

first version to make use of the version field in the

header.

A transactions paper on NTP Version 1 appeared in

1991 [21]. This was the first paper that exposed the NTP

model, including the architecture, protocol and algo-

rithms, to the technical engineering community. While

this model is generally applicable today, there have been

a continuing series of enhancements and new features

introduced over years, some of which are described in

following sections.

The NTP Version 2 specification followed as RFC-1119

in 1989 [25]. A completely new implementation slavish

to the specification was built by Dennis Fergusson at U

Toronto. This was the first RFC in PostScript and as

such the single most historically unpopular document in

the RFC publishing process. This document was the first

to include a formal model and state machine describing

the protocol and pseudo-code defining the operations. It

introduced the NTP Control Message Protocol for use in

managing NTP servers and clients, and the crypto-

graphic authentication scheme based on symmetric-key

cryptography, both of which survive to the present day.

There was considerable discussion during 1989 about

the newly announced Digital Time Synchronization Ser-

vice (DTSS) [23], which was adopted for the Enterprise

network. The DTSS and NTP communities had much

the same goals, but somewhat different strategies for

achieving them. One problem with DTSS, as viewed by

the NTP community, was a possibly serious loss of

accuracy, since the DTSS design did not discipline the

clock frequency. The problem with the NTP design, as

viewed from the DTSS community, was the lack of for-

mal correctness principles in the design process. A key

component in the DTSS design upon which the correct-

ness principles were based was an agreement algorithm

invented by Keith Marzullo in his dissertation.

In the finest Internet tradition of stealing good ideas, the

Marzullo algorithm was integrated with the existing

suite of NTP mitigation algorithms, including the filter-

ing, clustering and combining algorithms, which the

DTSS design lacked. However, the Marzullo algorithm

in its original form produced excessive jitter and seri-

ously degraded timekeeping quality over typical Internet

paths. The algorithm, now called the intersection algo-

rithm, was modified to avoid this problem. The resulting

suite of algorithms has survived substantially intact to

the present day, although many modifications and

improvements have been made over the years.

In 1992 the NTP Version 3 specification appeared [18],

again in PostScript and now running some 113 pages.

The specification included an appendix describing a for-

mal error analysis and an intricate error budget includ-

ing all error contributions between the primary reference

source over intervening servers to the eventual client.

This provided the basis to support maximum error and

estimated error statistics, which provide a reliable char-

acterization of timekeeping quality, as well as a reliable

metric for selecting the best from among a population of

available servers. As in the Version 2 specification, the

model was described using a formal state machine and

pseudo code. This version also introduced broadcast

mode and included reference clock drivers in the state

machine.

Lars Mathiesen at U Copenhagen carefully revised the

version 2 implementation to comply with the version 3

specification. There was considerable give and take

between the specification and implementation and some

changes were made in each to reach consensus, so that

the implementation was aligned precisely with the spec-

ification. This was a major effort which lasted over a

year during which the specification and implementation

converged to a consistent formal model.

3

In the years since the version 3 specification, NTP has

evolved in various ways adding new features and algo-

rithm revisions while still preserving interoperability

with older versions. Somewhere along the line, it

became clear that a new version number was needed,

since the state machine and pseudo code had evolved

somewhat from the version 3 specification, so it became

NTP Version 4. The evolution process was begun with a

number of white papers, including [14] and [11].

Subsequently, a simplified version 4 protocol model was

developed for the Simple Network Protocol (SNTP) ver-

sion 4 in RFC-2030 [9]. SNTP is compatible with NTP

as implemented for the IPv4, IPv6 and OSI protocol

stacks, but does not include the crafted mitigation and

discipline algorithms. These algorithms are unnecessary

for an implementation intended solely as a server. SNTP

version 4 has been used in several standalone NTP serv-

ers integrated with GPS receivers.

There is a certain sense of the radio amateur in the

deployment of NTP around the globe. Certainly, each

new country found running NTP was a new notch for the

belt. A particularly satisfying conquest was when the

national standards laboratory of a new country came up

an NTP primary server connected directly to the

national time and frequency ensemble. Internet time-

keepers Judah Levine at NIST and Richard Schmidt at

USNO deployed public NTP primary time servers at

several locations in the US and overseas. There was a

period where NTP was well lit in the US and Europe but

dark elsewhere in South America, Africa and the Pacific

Rim. Today, the Sun never sets or even gets close to the

horizon on NTP. The most rapidly growing populations

are in Eastern Europe and South America, but the real

prize is a new one found in Antarctica. Experience in

global timekeeping is documented in [8].

One of the real problems in fielding a large, complex

software distribution is porting to idiosyncratic hard-

ware and operating systems. There are now over two

dozen ports of the distribution for just about every hard-

ware platform running Unix, Windows and VMS mar-

keted over the last twenty years, some of them truly

historic in their own terms. Various distributions have

run on everything from embedded controllers to super-

computers. Maintaining the configuration scripts and

patch library is a truly thankless job and getting good at

it may not be a career enhancer. Volunteer Harlan Stenn

currently manages this process using modern autocon-

figure tools. New versions are tested first in our research

net DCnet, then in bigger sandboxes like CAIRN and

finally put up for public release at www.ntp.org. The

bug stream arrives at bugs@mail.ntp.org.

At this point the history lesson is substantially complete.

However, along the way several specific advancements

need to be identified. The remaining sections of this

paper discuss a number of them in detail.

3. Autonomous Deployment

It became clear as the NTP development continued that

the most valuable enhancement would be the capability

for a number of clients and servers to automatically con-

figure and deploy in an NTP subnet delivering the best

timekeeping quality, while conserving processor and

network resources. Not only would this avoid the

tedious chore of engineering specific configuration files

for each server and client, but it would provide a robust

response and reconfiguration scheme should compo-

nents of the subnet fail. The DTSS model described in

[23] goes a long way to achieve this goal, but has serious

deficiencies, notably the lack of cryptographic authenti-

cation. The following discussion summarizes the

progress toward that goal.

Some time around 1985 Project Athena at MIT was

developing the Kerberos security model, which provides

cryptographic authentication of users and services. Fun-

damental to the Kerberos design is the ticket used to

access computer and network services. Tickets have a

designated lifetime and must be securely revoked when

their lifetime expires. Thus, all Kerberos facilities had to

have secure time synchronization services. While the

NTP protocol contains specific provisions to deflect

bogus packets and replays, these provisions are inade-

quate to deflect more sophisticated attacks such as mas-

querade. To deflect these attacks NTP packets were

protected by a cryptographic message digest and private

key. This scheme used the Digital Encryption Standard

operating in Cipher Block Chaining mode (DES-CBC).

Provision of DES-based source authentication created

problems for the public software distribution. Due to the

International Trade in Arms Regulations (ITAR) at the

time, DES could not be included in NTP distributions

exported outside the US and Canada. Initially, the way

to deal with this was to provide two versions of DES in

the source code, one operating as an empty stub and the

other with the algorithm but encrypted with DES and a

secret key. The idea was that, if a potential user could

provide proof of residence, the key was revealed. Later,

this awkward and cumbersome method was replaced

simply by maintaining two distributions, one intended

for domestic use and the other for export. Recipients

were placed on their honor to fetch the politically cor-

rect version.

4

However, there was still the need to authenticate NTP

packets in the export version. Louis Mamakos of U

Maryland adapted the MD5 message digest algorithm

for NTP. This algorithm is specifically designed for the

same function as the DES-CBC algorithm, but is free of

ITAR restrictions. In NTP Version 4 the export distribu-

tion has been discontinued and the DES source code

deleted; however, the algorithm interface is compatible

with widely available cryptographic libraries, such as

rsaref2.0 from RSA Laboratories. If needed, there are

numerous sources of the DES source code from foreign

archive sites, so it is readily possible to obtain it and

install in the standard distribution.

While MD5-based source authentication has worked

well, it requires secret keys, which complicates key dis-

tribution and, especially for multicast-based modes, is

vulnerable to compromise. Public-key cryptography

simplifies key distribution, but can severely degrade

timekeeping quality. The Internet Engineering Task

Force (IETF) has defined several cryptographic algo-

rithms and protocols, but these require persistent state,

which is not possible in some NTP modes. Some appre-

ciation of the problems is apparent from the observation

that secure timekeeping requires secure cryptographic

media, but secure media require reliable lifetime

enforcement [4]. The implied circularity applies to any

secure time synchronization service, including NTP.

These problems were addressed in NTP Version 4 with a

new security model and protocol called Autokey.

Autokey uses a combination of public-key cryptography

and a pseudo-random keystream [1]. Since public-key

cryptography hungers for large chunks of processor

resources and can degrade timekeeping quality, the algo-

rithms are used sparingly in an offline mode to sign and

verify time values, while the much less expensive key-

stream is used to authenticate the packets relative to the

signed values. Furthermore, Autokey is completely self-

configuring, so that servers and clients can be deployed

and redeployed in an arbitrary topology and automati-

cally exchange signed values without manual interven-

tion. Further information is available at

www.eecid.udel.edu/~mills/autokey.htm.

The flip side of autonomous deployment is how a ragtag

bunch of servers and clients randomly deployed in a net-

work substrate can find each other and automatically

configure which servers directly exchange time values

and which depend on intervening servers. The technol-

ogy which supports this feature is called Autoconfigure

and has evolved as follows.

In the beginning, almost all NTP servers operated in cli-

ent/server mode, where a client sends requests at inter-

vals ranging from one minute to tens of minutes,

depending on accuracy requirements. In this mode time

values flow outward from the primary servers through

possibly several layers of secondary servers to the cli-

ents. In some cases involving multiply redundant serv-

ers, peers operate in symmetric mode and values can

flow from one peer to the other or vice versa, depending

on which one is closest to the primary source according

to a defined metric. Some institutions like U Delaware

and GTE, for example, operate multiple primary servers,

each connected to one or more redundant radio and sat-

ellite receivers using different dissemination services.

This forms an exceptionally robust synchronization

source for both on-campus and off-campus public

access.

In NTP Version 3, configuration files had to be con-

structed manually using information found in the lists of

public servers at www.ntp.org, although some sites par-

tially automated the process using crafted DNS records.

Where very large numbers of clients are involved, such

as in large corporations with hundreds and thousands of

personal computers and workstations, the method of

choice is broadcast mode, which was added in NTP Ver-

sion 3, or multicast mode, which was added in NTP Ver-

sion 4.

However, since clients to not send to servers, there was

no way to calibrate and correct for the server-client

propagation delay in NTP Version 3. This is provided in

NTP Version 4 by a protocol modification in which the

client, once receiving the first broadcast packet, exe-

cutes a volley of client/server exchanges in order to cali-

brate the delay and then reverted to listen-only mode.

Coincidentally, this initial exchange is used by the

Autokey protocol to retrieve the server credentials and

verify its authenticity.

Notwithstanding the progress toward a truly autono-

mous deployment capability described here, there still

remains work to be done. The current research project

funded by DARPA under the Next Generation Internet

program is actively pursuing this goal, as discussed in a

following section.

4. Radios, we have Radios

For as many years as NTP has ticked on this planet, the

definitive source for public NTP servers has been a set

of tables, one for primary servers and the other for sec-

ondary servers, maintained at www.ntp.org. Each server

in those tables is operated as a public service and main-

tained by a volunteer staff. Primary (stratum 1) servers

have up to several hundred clients and a few operated by

NIST and USNO may have several times that number. A

5

stratum-1 server requires a primary reference source,

usually a radio or satellite receiver or modem. Following

is a history lesson on the development and deployment

of NTP stratum-1 servers.

The first use of radios as a primary reference source was

in 1981 when a Spectracom WWVB receiver was con-

nected to a Fuzzball at COMSAT Laboratories in

Clarksburg, MD [34]. This machine provided time syn-

chronization for Fuzzball LANs in Washington, Lon-

don, Oslo and later Munich. These LANs were used in

the DARPA Atlantic Satellite program for satellite mea-

surements and protocol development. Later, the LANs

were used to watch the national power grids of the US,

UK and Norway swish and sway over the heating and

cooling seasons [30].

DARPA purchased four of the Spectracom WWVB

receivers, which were hooked up to Fuzzballs at MIT

Lincoln Laboratories, COMSAT Laboratories, USC

Information Sciences Institute, and SRI International.

The radios were redeployed in 1986 in the NSF Phase I

backbone network, which used Fuzzball routers [26]. It

is a tribute to the manufacturer that all four radios are

serviceable today; two are in regular operation at U Del-

aware, a third serves as backup spare and the fourth is in

the Boston Computer Museum.

These four radios, together with a Heath WWV receiver

at COMSAT Laboratories and a pair of TrueTime GOES

satellite receivers at Ford Motor Headquarters and later

at Digital Western Research Laboratories, provided pri-

mary time synchronization services throughout the

ARPANET, MILNET and dozens of college campuses,

research institutions and military installations. By 1988

two Precision Standard Time WWV receivers joined the

flock, but these along with the Heath WWV receiver are

no longer available. From the early 1990s these nine

pioneer radio-equipped Internet time servers were

joined by an increasing number of volunteer radio-

equipped servers now numbered over 100 in the public

Internet.

As the cost of GPS receivers plummeted from the strato-

sphere (the first one this author bought cost $17,000),

these receivers started popping up all over the place. In

the US and Canada the longwave radio alternative to

GPS is WWVB transmitting from Colorado, while in

Europe it is DCF77 from Germany. However, shortwave

radio WWV from Colorado, WWVH from Hawaii and

CHU from Ottawa have been useful sources. While

GOES satellite receivers are available, GPS receivers are

much less expensive than GOES and provide better

accuracy. Over the years some 37 clock driver modules

supporting these and virtually every radio, satellite and

modem national standard time service in the world have

been written for NTP.

Recent additions to the driver library include drivers for

the WWV, WWVH and CHU transmissions that work

directly from an ordinary shortwave receiver and audio

sound card or motherboard codec. Some of the more

exotic drivers built in our laboratory include a computer-

ized LORAN-C receiver with exceptional stability [19]

and a DSP-based WWV demodulator/decodor using

theoretically optimal algorithms [6].

5. Hunting the Nanoseconds

When the Internet first wound up the NTP clockspring,

computers and networks were much, much slower than

today. A typical WAN speed was 56 kb/s, about the

speed of a telephone modem of today. A large timeshar-

ing computer of the day was the Digital Equipment

TOPS-20, which wasn’t a whole lot faster, but did run an

awesome version of Zork. This was the heyday of the

minicomputer, the most ubiquitous of which was the

Digital Equipment PDP11 and its little brother the LSI-

11. NTP was born on these machines and grew up with

the Fuzzball operating system. There were about two

dozen Fuzzballs scattered at Internet hotspots in the US

and Europe. They functioned as hosts and gateways for

network research and prototyping and so made good

development platforms for NTP.

In the early days most computer hardware clocks were

driven by the power grid as the primary timing source.

Power grid clocks have a resolution of 16 or 20 ms,

depending on country, and the uncorrected time can

wander several seconds over the day and night, espe-

cially in summertime. While power grid clocks have

rather dismal performance relative to accurate civil time,

they do have an interesting characteristic, at least in

areas of the country that are grid-synchronous. Early

experiments in time synchronization and network mea-

surement could assume the time offsets between grid-

synchronized clocks was constant, since they all ran at

the same Hertz, so all NTP had to do was calibrate the

constant offsets.

Later, clocks were driven by an oscillator stabilized by a

quartz crystal resonator, which is much more stable than

the power grid, but has the disadvantage that the intrin-

sic frequency offset between crystal clocks can reach

several hundred parts-per-million (PPM) or several sec-

onds per day. In fact, over the years only Digital has

paid particular attention to the manufacturing tolerance

of the clock oscillator, so their machines make the best

timekeepers. In fact, this is one of the reasons why all