@TITLE = On the Chronometry and Metrology of Computer Network Timescales and their Application to the Network Time Protocol<$FSponsored by: Defense Advanced Research Projects Agency under NASA Ames Research Center contract number NAG 2-638 and National Science Foundation grant number NCR-89-13623.> @AUTHOR = David L. Mills Electrical Engineering Department University of Delaware @AUTHOR = Abstract @ABSTRACT = This paper summarizes issues in computer network timekeeping with respect to the Network Time Protocol, which is used to synchronize time in many of the hosts and gateways of the Internet. It describes the methods used to coordinate and disseminate international time services and how they are incorporated into NTP time servers. It discusses the hazards on reckoning NTP dates with the conventional civil calendar and a standard method for numbering the days. Finally, the paper describes the NTP timescale, its mapping to conventional civil time and date and its interpretation of leap seconds. Keywords: network clock synchronization, standard time distribution, timescale coordination, leap seconds, Network Time Protocol. @HEAD LEVEL 1 = Introduction Each year brings exotic new applications for precision timekeeping, such as measuring the density of the universe [RAW87] and calibrating global warming [SCI91]. Recent improvements in time-transfer technology have doubled the precisions attainable about every seven years to the current regime of better than a few nanoseconds over the global range. While inexpensive, ubiquitous time transfer using a global computer network ordinarily cannot approach such precisions, accuracies of a few tens of milliseconds have been demonstrated for most paths in the Internet of today [MIL90a]. Among the requirements for ubiquitous timekeeping in a global computer networking community is to provide a standard chronometry for precision dating of present and future events. This requires a standard interpretation of computer timekeeping media with respect to conventional civil time and date as disseminated by national means. Among the problems addressed must be the rationalization with the calendar, the ambiguity of presentation and the interpretation of leap seconds. This paper consists of an extended discussion on computer network chronometry, which is the precise determination of computer time and frequency relative to international standards, and on calendar metrology, which is the determination of conventional civil time and date according to the modern calendar. It describes the methods conventionally used to establish civil time and date and the various timescales now in use. In particular, it characterizes the Network Time Protocol (NTP) timescale relative to the Coordinated Universal Time (UTC) timescale, and establishes the precise interpretation of UTC leap seconds in NTP. In the following discussion the terms time, timescale, oscillator, clock, epoch, timestamp, calendar and date are used in a technical sense. Strictly speaking, the time of an event is an abstraction which determines the ordering of events in some given frame of reference or timescale. An oscillator is a generator capable of precise frequency (relative to the given timescale) within a specified tolerance. A clock is an oscillator together with a counter which records the (fractional) number of cycles since being initialized with a given value at a given time. The value of the counter at any given time t is called its epoch and recorded as the timestamp T(t) of that epoch. In general, epoches are not continuous and depend on the precision of the counter. A calendar is a mapping from epoches in some timescale to the year-day dates used in everyday life. Since multiple calendars are in use today and sometimes disagree on the dating of the same epoches in the past, the metrology of past and present epoches is an art practiced by historians. However, the ultimate timescale for our world is based on cosmic oscillators, such as the Sun, Moon and other galactic orbiters. Since the frequencies of these oscillators are relatively unstable and not known exactly, the ultimate reference standard oscillator has been chosen by international agreement as a synthesis of many observations of an atomic transition of exquisite stability. The frequency of each heavenly and Earthbound oscillator defines a distinctive timescale, not necessarily always continuous, relative to that of the standard oscillator. In this paper the stability of a clock is how well it can maintain a constant frequency, the accuracy is how well its time compares with national standards and the precision is to what degree time can be resolved in a particular timekeeping system. The time offset of two clocks is the time difference between them, while the frequency offset is the frequency difference between them. In this paper reference to simply <169>offset<170> means time offset, unless indicated otherwise. The reliability of a timekeeping system is the fraction of the time it can be kept connected to the network and operating correctly relative to stated accuracy and stability tolerances. In order to synchronize clocks, there must be some way to directly or indirectly compare them in time and frequency. In network architectures such as DECnet and Internet local clocks are synchronized from designated time servers, which are timekeeping systems belonging to a synchronization subnet, in which each server measures the offsets between its local clock and the clocks of its neighbor servers or peers in the subnet. In this paper to synchronize frequency means to adjust the clocks in the subnet to run at the same frequency, to synchronize time means to set them to agree at a particular epoch with respect to Coordinated Universal Time (UTC), as provided by national standards, and to synchronize clocks means to synchronize them in both frequency and time. @HEAD LEVEL 1 = Network Time Protocol The Network Time Protocol (NTP) is used by Internet time servers and their peers to synchronize clocks, as well as automatically organize and maintain the time synchronization subnet itself. It is evolved from the Time Protocol [POS83] and the ICMP Timestamp Message [DOD81a], but is specifically designed for high accuracy, stability and reliability, even when used over typical Internet paths involving multiple gateways and unreliable networks. The following sections contain an overview of the procedures and algorithms used in NTP. A formal description and error analysis of the protocol is contained in [MIL90b]. A detailed description of the NTP architecture and protocols is contained in [MIL91], while a summary of operational experience and performance is contained in [MIL90a]. NTP and its implementations have evolved and proliferated in the Internet over the last decade, with NTP Version 2 now adopted as an Internet Standard [MIL89] and NTP Version 3 proposed for adoption [MIL90b]. NTP is built on the Internet Protocol (IP) [DOD81b] and User Datagram Protocol (UDP) [POS80], which provide a connectionless transport mechanism; however, it is readily adaptable to other protocol suites. The protocol can operate in several modes appropriate to different scenarios involving private workstations, public servers and various network configurations. A lightweight association-management capability, including dynamic reachability and variable poll-interval mechanisms, is used to manage state information and reduce resource requirements. Optional features include message authentication based on crypto-checksums and provisions for remote control and monitoring. In NTP one or more primary servers synchronize directly to external reference sources such as radio clocks. Secondary time servers synchronize to the primary servers and others in the synchronization subnet. A typical subnet is shown in Figure 1a, in which the nodes represent subnet servers, with normal level numbers determined by the hop count to the root, and the heavy lines the active synchronization paths and direction of timing information flow. The light lines represent backup synchronization paths where timing information is exchanged, but not necessarily used to synchronize the local clocks. Figure 1b shows the same subnet, but with the line marked x out of service. The subnet has re-configured itself automatically to use backup paths, with the result that one of the servers has dropped from stratum 2 to stratum 3. In practice each NTP server synchronizes with several other servers in order to survive outages and Byzantine failures using methods similar to those described in [SHI87] Figure 2<$&fig2> shows the overall organization of the NTP time-server model, which has much in common with the phase-lock methods summarized in [RAM90]. Timestamps exchanged between the server and possibly many other subnet peers are used to determine individual roundtrip delays and clock offsets, as well as provide reliable error bounds. Figure 3<$&fig3> shows how NTP timestamps are numbered and exchanged between peers A and B. Let <$ET sub i>, <$ET sub {i-1}>, <$ET sub {i-2}>, <$ET sub {i-3}> be the values of the four most recent timestamps as shown and let @CENTER = <$Ea~=~T sub {i-2}~-~T sub {i-3}> and <$Eb~=~T sub {i- 1}~-~T sub i>. If the network delays from A to B and from B to A are similar, the roundtrip delay <$Edelta> and clock offset <$Etheta> of B relative to A at time <$ET sub i> are: @CENTER = <$Edelta~=~a~-~b> and <$Etheta~=~{a~+~b} over 2>. Each NTP message includes the latest three timestamps <$ET sub {i-1}>, <$ET sub {i-2}> and <$ET sub {i-3}>, while the fourth timestamp <$ET sub i> is determined upon arrival of the message. Thus, both the server and the peer can independently calculate delay and offset using a single bidirectional message stream. This is a symmetric, continuously sampled, time-transfer scheme similar to those used in some digital telephone networks [LIN80]. Among its advantages are that the transmission times and received message orders are unimportant and that reliable delivery is not required. As shown in Figure 2, the computed delays and offsets for each peer are processed by the data-filter algorithm to reduce incidental timing noise. As described in [MIL90b], this algorithm selects from among the last several samples the one with minimum <$Edelta> and presents the associated <$Etheta> as the output. The peer-selection algorithm determines from among all peers a suitable subset of peers capable of providing the most accurate and trustworthy time using principles similar to those described in [VAS88]. In NTP this is done using a cascade of two subalgorithms, one a version of an algorithm proposed in [MAR85] and the other based on maximum likelihood principles to improve accuracy [MIL91]. The resulting offsets of this subset are first combined on a weighted- average basis using an algorithm similar to that described in [JON83] and then processed by a phase-lock loop (PLL). In the PLL the combined effects of the filtering, selection and combining operations are to produce a phase-correction term, which is processed by the loop filter to control the local clock, which functions as a voltage-controlled oscillator (VCO). The VCO furnishes the timing (phase) reference to produce the timestamps used in all timing calculations. @HEAD LEVEL 1 = Methods for Time and Frequency Synchronization The primary servers of a synchronization subnet must themselves synchronize to a source of standard time, such as a radio clock or telephone modem. It is of considerable interest to explore how this can be done and what accuracies can be expected. The following sections discuss issues involved in providing accurate and stable reference sources using national means of dissemination. @HEAD LEVEL 2 = Time and Frequency Standards A primary frequency standard is an oscillator that can maintain extremely precise frequency relative to a physical phenomenon, such as a transition in the orbital states of an electron. Presently available atomic oscillators are based on the transitions of the hydrogen, cesium and rubidium atoms. Table 1<$&tab1> shows the characteristics for typical oscillators of these types compared with those for various types of quartz-crystal oscillators found in electronic equipment. Present practice is to operate multiple cesium-based clocks at national standards laboratories and coordinate their readings using satellite- based time-transfer methods. On the other hand, local clocks used in computing equipment almost always are designed with uncompensated quartz oscillators. For the three atomic oscillators listed in Table 1 the Drift/Aging column shows the maximum offset from nominal standard frequency due to systematic mechanical and electrical characteristics. In the case of quartz oscillators (oven-controlled, digital-temperature-compensated, analog-temperature-compensated or uncompensated) this offset is not constant, which results in a gradual change in frequency with time, called aging. Even if a quartz oscillator is temperature compensated by some means, it must be periodically compared to a primary standard in order to maintain the highest accuracy. For all types of oscillators the stability column shows the maximum variation in frequency per day due to circuit noise and environmental factors. As the telephone networks of the world are evolving rapidly to digital technology, consideration should be given to the methods used for synchronization in digital networks [BEL86]. A network of clocks in which each oscillator is phase-locked to a single frequency standard is called isochronous, while a network in which some oscillators are phase- locked to different master oscillators, but with the master oscillators closely synchronized in frequency (not necessarily phase-locked), to a single frequency standard is called plesiochronous. The NTP synchronization subnet operating in the Internet is a plesiochronous system in which multiple primary time servers synchronize using radio clocks and national broadcast services. The industry has agreed on a classification of clock oscillators as a function of minimum accuracy, minimum stability and other factors [ALL74]. There are three factors which determine the classification: stability, jitter and wander. Stability refers to the systematic variation of frequency with time and is synonymous with aging, drift, trends, etc. Jitter (also called timing jitter) refers to short-term variations in frequency with components greater than 10 Hz, while wander refers to long-term variations in frequency with components less than 10 Hz. The classification determines the oscillator stratum (not to be confused with the NTP stratum described previously), with the more accurate oscillators assigned the lower strata and less accurate oscillators the higher strata, as shown in Table 2<$&tab2>. The construction, operation and maintenance of stratum-one oscillators is assumed to be consistent with national standards and often includes cesium oscillators or precision quartz oscillators synchronized to national standards. Oscillators assigned higher strata represent the stability required for interexchange systems, exchange switches and PBX systems, respectively. With respect to this classification, most computer local clocks would be assigned stratum-four. These clocks are most often constructed using an uncompensated quartz oscillator with typical frequency tolerance of 10-5 and stability of 10-6 per day. @HEAD LEVEL 2 = Time and Frequency Dissemination In order that atomic and civil time can be coordinated throughout the world, national administrations operate primary time and frequency standards and coordinate them cooperatively by observing various radio and satellite broadcasts and through occasional use of portable atomic clocks. Most seafaring nations of the world operate some sort of broadcast time service for the purpose of calibrating chronographs, which are used in conjunction with ephemeris data to determine navigational position. In many countries the service is primitive and limited to seconds-pips broadcast by marine communication stations at certain hours. For example, a chronograph error of one second represents a longitudinal position error of about 0.23 nautical mile at the Equator. The U.S. National Institute of Standards and Technology (NIST - formerly National Bureau of Standards) operates three radio services for the dissemination of primary time and frequency information. One of these uses high-frequency (HF or CCIR band 7) transmissions from Fort Collins, CO (WWV), and Kauai, HI (WWVH). Signal propagation is usually by reflection from the upper ionospheric layers, which vary in height and density throughout the day and season and result in unpredictable amplitude and delay variations at the receiver. While these transmissions and those of Canada from Ottawa, Ontario (CHU), and other countries can be received over large areas in the western hemisphere, reliable frequency comparisons can be made only to the order of 10-7 and time accuracies are limited to the order of a millisecond [BLA74]. Available radio clocks which operate with these transmissions provide accuracies to the order of ten milliseconds and are priced in the $1,500 range. A second service operated by NIST uses low-frequency (LF or CCIR band 5) transmissions from Boulder, CO (WWVB), and can be received over the continental U.S. and adjacent coastal areas. Signal propagation is via the lower ionospheric layers, which are relatively stable and have predictable diurnal variations in height. With appropriate receiving and averaging techniques and corrections for diurnal and seasonal propagation effects, frequency comparisons to within 10-11 are possible and time accuracies of from a few to 50 microseconds can be obtained [BLA74]. Some countries in western Europe operate similar services which use transmissions from Rugby, U.K. (MSF). Mainflingen, Germany (DCF77), and Allouis, France (France Inter). Available radio clocks which operate with these transmissions provide accuracies to the order of a millisecond and are priced in the $1,500 range. The third service operated by NIST uses ultra-high frequency (UHF or CCIR band 9) transmissions from the Geosynchronous Orbit Environmental Satellites (GOES), and can be received over most of the western hemisphere. Available radio clocks which operate with these transmissions provide accuracies to the order of a millisecond and are priced in the $6,000 range. Another service offered by NIST uses an ordinary telephone and modem [NBS88]. The service is intended for use by personal workstations to set clock-calendars, for example. However, in order to maintain an accuracy of a few milliseconds using an uncompensated quartz oscillator at typical limits of tolerance, it would be necessary to make a long- distance call every few minutes, which would not be suitable for a large population of clients calling on a regular basis without further redistribution. The U.S. Department of Defense is developing the Global Positioning System (GPS) for worldwide precision navigation. This system will eventually provide 24-hour worldwide coverage using a constellation of 21 satellites in 12-hour orbits. For time-transfer applications GPS has a potential accuracy in the order of a few nanoseconds; however, various considerations of defense policy may limit accuracy to hundreds of nanoseconds [VAN84]. Available radio clocks provide accuracies to 100 ns and are priced in the $10,000 range. There are several other navigation systems such as LORAN-C, operated by the U.S. Coast Guard and agencies of other countries, OMEGA, operated by the U.S. Navy, and various communication systems using very-low- frequency (VLF or CCIR band 4) transmissions. These systems can provide accuracies in the order from less than one to about fifty microseconds; however, the broadcast formats of these systems are not well suited for standard time distribution and the receivers have to be initialized with position information before use. Note that not all transmission formats used by NIST radio broadcast services [NBS79] and not all currently available radio clocks include provisions for year information and leap-second warning. This information must be determined from other sources. NTP includes provisions to distribute advance warnings of leap seconds using the leap-indicator bits described in the NTP specification. The protocol is designed so that these bits can be set manually or by the radio clocks at the primary time servers and then automatically distributed throughout the synchronization subnet to all other time servers. @HEAD LEVEL 1 = Calendar Metrology In the simplest terms a calendar system is a method to rationalize sightings of the Sun and Moon with certain religious and agricultural seasons which recur at characteristic frequencies. The various metrologies of the calendar amount to systems to assign day-numbers and sometimes day-names which determine the periodicity of these holy and secular oscillators. One might ask whether a (suitably disambiguated) NTP timestamp documenting the adventures of Alexander the Great merits the precision implied in its format. The following sections consider this issue in the light of the Western civil calendar and the establishment of a standard day-numbering plan. @HEAD LEVEL 2 = Evolution of the Calendar The calendar systems used in the ancient world reflect the agricultural, political and ritual needs characteristic of the societies in which they flourished. Astronomical observations to establish the winter and summer solstices were in use three to four millennia ago [CAL86]. By the 14th century BC the Shang Chinese had established the solar year as 365.25 days and the lunar month as 29.5 days. The lunisolar calendar, in which the ritual month is based on the Moon and the agricultural year on the Sun, was used throughout the ancient Near East (except Egypt) and Greece from the third millennium BC. Early calendars used either thirteen lunar months of 28 days or twelve alternating lunar months of 29 and 30 days and haphazard means to reconcile the 354/364-day lunar year with the 365-day vague solar year. The ancient Egyptian lunisolar calendar had twelve 30-day lunar months, but was guided by the seasonal appearance of the star Sirius (Sothis). In order to reconcile this calendar with the solar year, a civil calendar was invented by adding five intercalary days for a total of 365 days. However, in time it was observed that the civil year was about one-fourth day shorter than the actual solar year and thus would precess relative to it over a 1460-year cycle called the Sothic cycle. Along with the Shang Chinese, the ancient Egyptians had thus established the solar year at 365.25 days, or within about 11 minutes of the present determination. In 432 BC, about a century after the Chinese had done so, the Greek astronomer Meton calculated there were 110 lunar months of 29 days and 125 lunar months of 30 days for a total of 235 lunar months in 6940 solar days, or just over 19 years. The 19-year cycle, called the Metonic cycle, established the lunar month at 29.532 solar days, or within about two minutes of the present determination. The Roman republican calendar was based on a lunar year and by 50 BC was eight weeks out of step with the solar year. Julius Caesar invited the Alexandrian astronomer Sosigenes to redesign the calendar, which led to the adoption in 46 BC of the Julian calendar. This calendar is based on a year of 365 days with an intercalary day inserted every four years. However, for the first 36 years an intercalary day was mistakenly inserted every three years instead of every four. The result was 12 intercalary days instead of nine, and a series of corrections that was not complete until 8 AD. The seven-day Sumerian week was introduced only in the fourth century AD by Emperor Constantine I. During the Roman era a 15-year census cycle, called the Indiction cycle, was instituted for taxation purposes. The sequence of day-names for consecutive occurrences of a particular day of the year does not recur for 28 years, called the solar cycle. Thus, the least common multiple of the 28-year solar cycle, 19-year Metonic cycle and 15-year Indiction cycle results in a grand 7980-year supercycle called the Julian Era, which began in 4713 BC. A particular combination of the day of the week, day of the year, phase of the Moon and round of the census will recur beginning in 3268 AD. By 1545 the discrepancy in the Julian year relative to the solar year had accumulated to ten days. In February 1582, following a plan originally devised by the astronomer Luigi Lilio, Pope Gregory XIII issued a papal bull which decreed that the day following Thursday, 4 October 1582 on the old (Julian) calendar would be Friday, 15 October 1582 on the new (Gregorian) calendar and, furthermore, that the solar year would henceforth consist of 365.2425 days [MOY82]. In order to realize the new value, only those centennial years divisible by 400 would be leap years, while the remaining centennial years would not, making the new year within about 24 seconds of the actual solar year at that time. Since the beginning of the Common Era and prior to 1990 there were 474 intercalary days inserted in the Julian calendar, but 14 of these were removed in the Gregorian calendar. While the Gregorian calendar is in use throughout most of the world today, some countries did not adopt it until early in the twentieth century. While it remains a fascinating field for time historians, the above narrative provides conclusive evidence that conjugating calendar dates of significant events and assigning NTP timestamps to them is approximate at best. In principle, reliable dating of such events requires only an accurate count of the days relative to some globally alarming event, such as a comet passage or supernova explosion; however, only historically persistent and politically stable societies, such as the ancient Chinese and Egyptian, and especially the ancient Maya [MOR83], possessed the means and will to do so. @HEAD LEVEL 2 = The Modified Julian Day System In order to measure the span of the universe or the decay of the proton, it is necessary to have a standard day-numbering plan. Accordingly, the International Astronomical Union has adopted the use of the standard second and Julian Day Number (JDN) to date cosmological events and related phenomena. The standard day consists of 86,400 standard seconds, where time is expressed as a fraction of the whole day, and the standard year consists of 365.25 standard days. In the scheme devised in 1583 by the French scholar Joseph Justus Scaliger and named after his father, Julius Caesar Scaliger, JDN 0.0 corresponds to 12h (noon) on the first day of the Julian Era, 1 January 4713 BC, and runs in days and fractions since then. The Modified Julian Date (MJD), which is sometimes used to represent dates near our own era in conventional time and with fewer digits, is defined as <$E roman MJD~=~roman JD~-~2,400,000.5>. While the JDN timescale is based on an absolute day numbering, it is not uniform relative to the absolute (atomic) timescale, since the Earth rotation is not constant and is gradually slowing down from 365.24232 days in 45 BC to 365.24219879 mean tropical days in the first year of our own century. For historical purposes the years prior to the Common Era (BC) are reckoned according to the Julian calendar, while the years of the Common Era (AD) are reckoned according to the Gregorian calendar. Since Monday, 1 January 1 AD in the Gregorian calendar corresponds to Monday, 3 January 1 in the Julian calendar [DER90], JDN 1,721,426.0 corresponds to 12h on the first day of the Common Era, 1 January 1 AD. Following the convention that our century began at 0h on 1 January 1900, at which time the solar year was already 12h old, that eclectic instant corresponds to MJD 15,020.0 and the origin of all existing Internet timescales, including that of NTP. @HEAD LEVEL 1 = Timescale Chronometry International timescales are based on atomic clocks of exquisite stability compared to the astronomical clocks we normally live by. Occasionally, there is a need to correct the conventional civil timescale to account for unpredictable wobbles in Earth rotation and related phenomena. The following sections discuss these issues with respect to the NTP timescale; in particular, how it handles leap seconds. @HEAD LEVEL 2 = Determination of Frequency For many years the most important use of time and frequency information was for worldwide navigation and space science, which depend on astronomical observations of the Sun, Moon and stars [TIM86]. Sidereal time is based on the transit of stars across the celestial meridian of an observer. The mean sidereal day is 23 hours, 56 minutes and 4.09 seconds, but varies about ‘30 ms throughout the year due to polar wandering and orbit variations. Ephemeris time is based on tables with which a standard time interval such as the tropical year - one complete revolution of the Earth around the Sun - can be determined through observations of the Sun, Moon and planets. In 1958 the standard second was defined as 1/31,556,925.9747 of the tropical year that began this century. On this scale the tropical year in 1900 was 365.2421987 days and the lunar month - one complete revolution of the Moon around the Earth - was 29.53059 days; however, the actual tropical year can be determined only to an accuracy of about 50 ms and the mean value has been increasing by about 5.3 ms per year. Without correction for this factor, an NTP timestamp would be in error over 26 seconds at the dawn of recorded history. Of the three heavenly oscillators readily apparent to ancient mariners and astronomers - the Earth rotation about its axis, the Earth revolution around the Sun and the Moon revolution around the Earth - none of the three have the intrinsic stability, relative to modern technology, to serve as a standard reference oscillator. In 1967 the standard second was redefined as <169>9,192,631,770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the cesium-133 atom.<170> Prior to 0h 1 January 1972 national frequency standards were occasionally corrected to agree with astronomical observations. Since then the time and frequency standards of the world have been based on International Atomic Time (TAI), which is defined and maintained using multiple cesium-beam oscillators to an accuracy of a few parts in 1013, or a few tens of nanoseconds per day. Note that, while this provides an extraordinarily precise timescale, it does not necessarily agree with conventional solar time and may not in fact even be absolutely uniform, unless subtle atomic conspiracies can be ruled out [RAW87]. @HEAD LEVEL 2 = Determination of Time and Leap Seconds The International Bureau of Weights and Measures (IBWM) uses astronomical observations provided by the U.S. Naval Observatory and other observatories to determine UTC. Starting from apparent mean solar time as observed, the UT0 timescale is determined using corrections for Earth orbit and inclination (the Equation of Time, as used by sundials), the UT1 (navigator's) timescale by adding corrections for polar migration and the UT2 timescale by adding corrections for known periodicity variations. While standard frequencies are based on TAI, conventional civil time is based on UT1, which is presently slowing relative to TAI by a fraction of a second per year. When the magnitude of correction approaches 0.7 second, a leap second is inserted or deleted in the TAI timescale on the last day of June or December. For the most precise coordination and timestamping of events since 1972, it is necessary to know when leap seconds are implemented in UTC and how the seconds are numbered. As specified in CCIR Report 517, which is reproduced in [BLA74], a leap second is inserted following second 23:59:59 on the last day of June or December and becomes second 23:59:60 of that day. A leap second would be deleted by omitting second 23:59:59 on one of these days, although this has never happened. Leap seconds were inserted prior to 1 January 1990 on the occasions listed in Table 3<$&tab3> (courtesy U.S. Naval Observatory). Published IBWM corrections consist not only of leap seconds, which result in step discontinuities relative to TAI, but 100-ms UT1 adjustments called DUT1, which provide increased accuracy for navigation and space science. Note that the NTP time column actually shows the epoch following the last second of the day given in the UTC date and MJD columns (except for the first line), which is the precise epoch of insertion. The offset column shows the cumulative seconds offset between the TAI timescale and the UTC timescale; that is, the number of seconds to add to the TAI clock in order to maintain nominal agreement with the UTC clock. Finally, note that the epoch of insertion is relative to the timescale immediately prior to that epoch; e.g., the epoch of the 31 December 1990 insertion is determined on the timescale in effect following the 31 December 1989 insertion, which means the actual insertion relative to the TAI clock was fifteen seconds later than the apparent time on the UTC timescale. The UTC timescale thus ticks in standard (atomic) seconds and was set to the value 0h MJD 41,317.0 at the epoch determined by astronomical observation to be 0h on 1 January 1972 according to the Gregorian calendar; that is, the inaugural tick of the UTC Era. In fact, the inaugural tick which synchronized the cosmic oscillators, Julian clock, UTC clock and Gregorian calendar forevermore was displaced about ten seconds from the civil clock then in use, while the GPS clock is ahead of the UTC clock by seven seconds in early 1991. Subsequently, the UTC clock has marched backward relative to the Julian timescale exactly one second on scheduled occasions at monumental epoches embedded in the institutional memory of our civilization. Note in passing that leap- second adjustments affect the number of seconds per day and thus the number of seconds per year. Apparently, should we choose to worry about it, the UTC clock, Julian clock and various cosmic clocks will inexorably drift apart with time until rationalized by some future papal bull. @HEAD LEVEL 2 = The NTP Timescale and Reckoning with UTC In NTP epoches are determined by copying the current value of the local clock to a timestamp variable when some significant event, such as the arrival of a message, occurs. Since NTP timestamps are cherished data and, in fact, represent the main product of the protocol, a special timestamp format has been established. An NTP timestamp is represented as a 64-bit unsigned fixed-point number, in seconds relative to 0h on 1 January 1900. The integer part is in the first 32 bits and the fraction part in the last 32 bits. The precision of this representation is about 232 picoseconds, which should be adequate for even the most exotic requirements. Should NTP be in use when this 64-bit field overflows some time in 2036, external means will be necessary to qualify time relative to 1900 and time relative to 2036 (and other multiples of 136 years). Timestamped data requiring such qualification will be so precious that appropriate means should be readily available. Since a large body of today's protocol architects expect to continue plying their trade as of 2036, some consideration as to the choice of format and origin of the NTP timescale may be in order. It is of course simple to mitigate the rollover problem simply by redefining the origin as, for example 2,272,060,800 or 1 January 1972, which results in a continuous timescale through all but the last two years of the next century. This does not, of course, change the interpretation of the NTP timestamp itself, just its representation in conventional civil time. Also, as will become evident shortly, in order to establish the most precise representation with respect to conventional civil time, it is necessary to retain a record of leap-second insertions, which cannot be predicted far in advance. Having surmounted that requirement, it does not seem odious to record the 136-year NTP epoch for such cherished timestamps upon the election of a pope, for example. The NTP timescale is based on the UTC timescale, but not necessarily always coincident with it. At 0h on 1 January 1972 (MJD 41,317.0), the first tick of the UTC Era, the NTP clock was set to 2,272,060,800, representing the number of standard seconds since 0h on 1 January 1900 (MJD 15,020.0). The insertion of leap seconds in UTC and subsequently into NTP does not affect the UTC or NTP oscillator, only the conversion to conventional civil UTC time. However, since the only institutional memory available to NTP are the UTC broadcast services, the NTP timescale is in effect reset to UTC as each timecode is received. Thus, when a leap second is inserted in UTC and subsequently in NTP, knowledge of all previous leap seconds is lost. Another way to describe this is to say there are as many NTP timescales as historic leap seconds. In effect, a new timescale is established after each new leap second. Thus, all previous leap seconds, not to mention the apparent origin of the timescale itself, lurch backward one second as each new timescale is established. If a clock synchronized to NTP in 1991 was used to establish the UTC epoch of an event that occurred in early 1972 without correction, the event would appear sixteen seconds late relative to UTC. However, NTP primary time servers resolve the epoch using the broadcast timecode, so that the NTP clock is set to the broadcast value on the current timescale. As a result, for the most precise determination of epoch relative to the historic UTC clock, the user must subtract from the apparent NTP epoch the offsets shown in Table 2 at the relative epoches shown. This is a feature of almost all present day time-distribution mechanisms. The chronometry involved can be illustrated with the help of Figure 4<$&fig4>, which shows the details of seconds numbering just before, during and after the last scheduled leap insertion at 23:59:59 on 31 December 1990. Notice the NTP leap bits are set on the day prior to insertion, as indicated by the <169>+<170> symbols on the figure. Since this makes the day one second longer than usual, the NTP day rollover will not occur until the end of the first occurrence of second 800. The UTC time conversion routines must notice the apparent time and the leap bits and handle the timescale conversions accordingly. Immediately after the leap insertion both timescales resume ticking the seconds as if the leap had never happened. The chronometric correspondence between the UTC and NTP timescales continues, but NTP has forgotten about all past leap insertions. In NTP chronometric determination of UTC time intervals spanning leap seconds will thus be in error, unless the exact times of insertion are known. It is possible that individual systems may use internal data formats other than the NTP timestamp format; however, a persuasive argument exists to use a two-part representation, one part for whole days (MJD or some fixed offset from it) and the other for the seconds (or some scaled value, such as milliseconds). This not only facilitates conversion between NTP and conventional civil time, but makes the insertion of leap seconds much easier. All that is required is to change the modulus of the seconds counter, which on overflow increments the day counter. This design insures that continuity of the timescale is assured, even if outside synchronization is lost before, during or after leap-second insertion. Since timestamp data are unaffected, synchronization is assured, even if timestamp data are in flight at the instant and originated before or at that instant. @HEAD LEVEL 1 = Summary By international agreement the primary frequency reference for our civilization is the atomic oscillator. The standard second is determined as a specified number of atomic cycles, the standard day as 86,400 standard seconds and the standard (Julian) year as 365.25 standard days. The Julian clock is synchronized to atomic frequency and its timescale calibrated in standard days (JDN), where JDN 0.0 corresponds to 12h on 1 January 4713 BC. While the Julian clock is elegant and everlasting, it is not useful in precision chronometric calculation of conventional civil time of day and day of year, since our solar day and solar year oscillators are slightly unstable and incommensurate. In order to maintain the nominal solar year, the Gregorian calendar mandates the insertion of leap days, which can be determined in advance. In order to maintain the nominal solar day, leap seconds must be inserted at times which cannot be reliably determined in advance. The basis of civil time is the UTC clock, which was cloned from the Julian clock at 0h on 1 January 1972. Without knowledge of prior leap seconds, an event determined on the UTC timescale can appear many seconds late on the Julian timescale. The NTP timescale is based on the UTC timescale and runs at atomic frequency; however, it is calibrated in standard seconds after 0h on 1 January 1900. The NTP timescale is, in effect, redefined at each leap second; that is, since the NTP oscillator is phase-continuous spanning a leap second, the number of apparent NTP seconds since UTC came into being does not change. However, the number of actual UTC seconds has in fact changed. Reconciliation of the NTP and UTC timescales requires global institutional memory in the form of a table of occurrences such as shown in Table 3. @HEAD LEVEL 1 = References @INDENT HEAD = [ALL74] @INDENT = Allan, D.W., J.H. Shoaf and D. Halford. Statistics of time and frequency data analysis. In: Blair, B.E. (Ed.). Time and Frequency Theory and Fundamentals. National Bureau of Standards Monograph 140, U.S. Department of Commerce, 1974, 151-204. @INDENT HEAD = [BEL86] @INDENT = Bell Communications Research. Digital Synchronization Network Plan. Technical Advisory TA-NPL-000436, 1 November 1986. @INDENT HEAD = [CAL86] @INDENT = <169>Calendar.<170> The Encyclopaedia Britannica Macropaedia, 15th ed., vol. 15, pp. 460-477. Encyclopaedia Britannica Co., New York, NY, 1986. @INDENT HEAD = [DER90] @INDENT = Dershowitz, N., and E.M. Reingold. Calendrical Calculations. Software Practice and Experience 20, 9 (September 1990), 899-928. @INDENT HEAD = [DOD81a] @INDENT = Defense Advanced Research Projects Agency. Internet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences Institute, September 1981. @INDENT HEAD = [DOD81b] @INDENT = Defense Advanced Research Projects Agency. Internet Protocol. DARPA Network Working Group Report RFC-791, USC Information Sciences Institute, September 1981. @INDENT HEAD = [JON83] @INDENT = Jones, R.H., and P.V. Tryon. Estimating time from atomic clocks. J. Research of the National Bureau of Standards 88, 1 (January- February 1983), 17-24. @INDENT HEAD = [LIN80] @INDENT = Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Communications COM-28, 8 (August 1980), 1260-1266. @INDENT HEAD = [MAR85] @INDENT = Marzullo, K., and S. Owicki. Maintaining the time in a distributed system. ACM Operating Systems Review 19, 3 (July 1985), 44- 54. @INDENT HEAD = [MIL89] @INDENT = Mills, D.L. Network Time Protocol (Version 2) specification and implementation. DARPA Network Working Group Report RFC-1119, University of Delaware, September 1989. @INDENT HEAD = [MIL90a] @INDENT = 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. @INDENT HEAD = [MIL90b] @INDENT = Mills, D.L. Network Time Protocol (Version 3) specification, implementation and analysis. Electrical Engineering Department Report 90-6-1, University of Delaware, June 1990. @INDENT HEAD = [MIL91] @INDENT = Mills, D.L. Internet time synchronization: the Network Time Protocol. IEEE Trans. Communications 30, 9 (September 1991) (to appear). @INDENT HEAD = [MOR83] @INDENT = Morley, S.G., G.W. Brainerd and R.J. Sharer. The Ancient Maya, 4th ed., pp. 598-600. Stanford University Press, Stanford, CA, 1983. @INDENT HEAD = [MOY82] @INDENT = Moyer, G. The Gregorian Calendar. Scientific American 246, 5 (May 1982), 144-152. @INDENT HEAD = [NBS88] @INDENT = Automated Computer Time Service (ACTS). NBS Research Material 8101, U.S. Department of Commerce, 1988. @INDENT HEAD = [POS80] @INDENT = Postel, J. User Datagram Protocol. DARPA Network Working Group Report RFC-768, USC Information Sciences Institute, August 1980. @INDENT HEAD = [POS83] @INDENT = Postel, J. Time protocol. DARPA Network Working Group Report RFC-868, USC Information Sciences Institute, May 1983. @INDENT HEAD = [RAM90] @INDENT = Ramanathan, P., K.G. Shin and R.W. Butler. Fault-tolerant clock synchronization in distributed systems. IEEE Computer 23, 10 (October 1990), 33-42. @INDENT HEAD = [RAW87] @INDENT = Rawley, L.A., J.H. Taylor, M.M. Davis and D.W. Allan. Millisecond pulsar PSR 1937+21: a highly stable clock. Science 238 (6 November 1987), 761-765. @INDENT HEAD = [SCI91] @INDENT = ScienceScope. Sounding out the threat of global warning. Science 251 (8 February 1991), 615. @INDENT HEAD = [SHI87] @INDENT = Shin, K.G., and P. Ramanathan. Clock synchronization of a large multiprocessor system in the presence of malicious faults. IEEE Trans. Computers C-36, 1 (January 1987), 2-12. @INDENT HEAD = [TIM86] @INDENT = <169>Time.<170> The Encyclopaedia Britannica Macropaedia, 15th ed., vol. 28, pp. 652-664. Encyclopaedia Britannica Co., New York, NY, 1986. @INDENT HEAD = [VAS88] @INDENT = 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.