RFC 1059
Network Time Protocol (version 1) specification and implementation
RFC 1059: Network Time Protocol (Version 1) Specification and Implementation 🎀⏰
okay bestie, let's get into it 💖 This one is by D. Mills from the University of Delaware, dated July 1988, and it's in the Network Working Group series as RFC 1059. It's a Draft Standard for an Elective protocol 📜, which is the category that matters for the whole vibe. It doesn't obsolete or update anything, since the header doesn't list any RFCs it replaces or changes. Iconic start, honestly 🦋
Status of This Memo 📜
okay so this memo describes the Network Time Protocol (NTP), lays out its formal structure, and sums up info that's useful for actually implementing it 🔥 NTP gives you the tools to sync time and coordinate how time gets distributed across a big, messy internet, whether things are running at mundane speeds or at lightwave speeds ⚡ It uses a returnable-time design, where a distributed subnet of time servers runs in a self-organizing, hierarchical master-slave setup 👑 and keeps logical clocks in sync with each other and with national time standards, over wire or radio. Servers can also pass reference time along using local routing algorithms and time daemons 💅
the NTP architectures, algorithms and protocols that grew over several years of implementing and refining are all in here 🌸 The prototype system has been running in regular operation on the Internet for the last two years, and it's covered in an Appendix along with performance data 📊 That data shows that timekeeping accuracy across most of the Internet can usually stay within a few tens of milliseconds, even when clocks, time servers or nets fail or get disrupted 🫶 This is a Draft Standard for an Elective protocol, and distribution of this memo is unlimited 🌈
Table of Contents 🗂️
1. Introduction 3
1.1. Related Technology 4
2. System Architecture 6
2.1. Implementation Model 7
2.2. Network Configurations 9
2.3. Time Scales 10
3. Network Time Protocol 12
3.1. Data Formats 12
3.2. State Variables and Parameters 13
3.2.1. Common Variables 15
3.2.2. System Variables 17
3.2.3. Peer Variables 18
3.2.4. Packet Variables 19
3.2.5. Clock Filter Variables 19
3.2.6. Parameters 20
3.3. Modes of Operation 21
3.4. Event Processing 22
3.4.1. Timeout Procedure 23
3.4.2. Receive Procedure 24
3.4.3. Update Procedure 27
3.4.4. Initialization Procedures 29
4. Filtering and Selection Algorithms 29
4.1. Clock Filter Algorithm 29
4.2 Clock Selection Algorithm 30
4.3. Variable-Rate Polling 32
5. Logical Clocks 33
5.1. Uniform Phase Adjustments 35
5.2. Nonuniform Phase Adjustments 36
5.3. Maintaining Date and Time 37
5.4. Calculating Estimates 37
6. References 40
Appendices
Appendix A. UDP Header Format 43
Appendix B. NTP Data Format 44
Appendix C. Timeteller Experiments 47
Appendix D. Evaluation of Filtering Algorithms 49
Appendix E. NTP Synchronization Networks 56
List of Figures
Figure 2.1. Implementation Model 8
Figure 3.1. Calculating Delay and Offset 26
Figure 5.1. Clock Registers 34
Figure D.1. Calculating Delay and Offset 50
Figure E.1. Primary Service Network 57
List of Tables
Table 2.1. Dates of Leap-Second Insertion 11
Table 3.1. System Variables 14
Table 3.2. Peer Variables 14
Table 3.3. Packet Variables 15
Table 3.4. Parameters 15
Table 4.1. Outlyer Selection Procedure 32
Table 5.1. Clock Parameters 35
Table C.1. Distribution Functions 47
Table D.1. Delay and Offset Measurements (UMD) 52
Table D.2.a Delay and Offset Measurements (UDEL) 52
Table D.2.b Offset Measurements (UDEL) 53
Table D.3. Minimum Filter (UMD - NCAR) 54
Table D.4. Median Filter (UMD - NCAR) 54
Table D.5. Minimum Filter (UDEL - NCAR) 55
Table E.1. Primary Servers 561. Introduction ✨
okay so this document describes NTP, including the architectures, algorithms and protocols used to sync local clocks across a whole set of distributed clients and servers 🕰️ NTP was first described in RFC-958 [24], but it has evolved in some big ways since that document came out 🌱 It's built on the Internet Protocol (IP) [10] and the User Datagram Protocol (UDP) [6], which give you a connectionless transport mechanism. It's still readily adaptable to other protocol suites though, so no stress 💜 NTP evolved from the Time Protocol [13] and the ICMP Timestamp message [11], but it's specifically designed to keep accuracy and robustness, even over typical Internet paths that involve multiple gateways and unreliable nets 🔥
the service environment is made up of the implementation model, service model and time scale, which are all covered in Section 2 🧚 The implementation model is based on a multiple-process operating system architecture, but other architectures could be used too. The service model is a returnable-time design that depends only on measured offsets, or skews, and it does not need reliable message delivery 💅 The subnet is a self-organizing, hierarchical master-slave configuration, and its synchronization paths get figured out by a minimum-weight spanning tree 🌳 Multiple masters (primary servers) may exist, and there is no requirement for an election protocol. no drama, no elections 👑
Section 3 is where NTP itself lives 🎀 It gives you the protocol mechanisms to sync time, in principle, to precisions on the order of nanoseconds, while still preserving a non-ambiguous date well into the next century 🤯 The protocol has provisions for specifying the characteristics of the local clock and the time server it may be synced to, and for estimating the error in each. It also works with a number of mutually suspicious, hierarchically distributed primary reference sources, like radio clocks 📻
the vibe here is "trust, but verify": the sources might not all be honest, so the protocol is built to handle that 🙈
Section 4 is all about algorithms for deglitching and smoothing clock-offset samples that get collected on a continuous basis 🧼 These started with the ones suggested in [22], got refined through the experiments in [23], and kept evolving under typical operating conditions over the last two years 📈 Experience from running multiple-server nets, including radio-synchronized clocks at several sites in the US and clients in the US and Europe, also led to reliable algorithms for picking good clocks out of a population that might include broken ones. Those are described in Section 4 too 💖
accuracy depends strongly on the precision of the local clock hardware and on tight control of device and process latencies 😭 Provisions must be included to adjust the software logical clock time and frequency in response to corrections produced by NTP. Section 5 describes a logical clock design that evolved from the Fuzzball implementation described in [15]. It includes offset-slewing, drift-compensation and deglitching mechanisms, and it can reach accuracies on the order of a millisecond, even after long stretches where sync to primary reference sources has been lost 🌈
the UDP and NTP packet formats are in Appendices A and B 📦 Appendix C shows the results of a survey of about 5500 Internet hosts, comparing how their clocks line up with primary reference sources using three different time protocols, NTP included ⏱️ Appendix D presents experimental results from several different deglitching and smoothing algorithms 🧪 And Appendix E describes the prototype NTP primary service net, plus proposed rules of engagement for using it ✨
part 1 done, bestie! 🫶 Part 2 picks up with Section 1.1 (Related Technology) 🦋
1.1. Related Technology 🎀
okay so bestie, the internet already had ways to record and send the time before NTP showed up 🕰️✨ there's the Daytime protocol [12], the Time Protocol [13], the ICMP Timestamp message [11], and the IP Timestamp option [9]. people have also run experiments on measured times and roundtrip delays across the Internet, and you can read about those in [14], [23] and [31] 📊. other synchronization protocols get discussed in [7], [17], [20] and [28] 💅. NTP is a mix of ideas from both linear and nonlinear synchronization methods. linear methods for digital telephone network synchronization are summarized in [3], and nonlinear methods for process synchronization are summarized in [27] 🧠
the Fuzzball routing protocol [15], which people sometimes call Hellospeak 🍓, builds time synchronization right into its routing design 🌈 one or more processes sync to an outside reference source, like a radio clock or an NTP daemon, and the routing algorithm builds a minimum-weight spanning tree rooted on those processes. the clock offsets then get passed along the arcs of that tree to every process in the system, and the process clocks get corrected using the procedure in Section 5 of this document ⭐ it's giving NTP vibes for sure, and Hellospeak really did influence how NTP was designed. but Hellospeak itself isn't an Internet protocol, and it isn't suited for use outside its local-net environment 🙈
the Unix 4.3bsd model [20] uses one master time daemon that measures the offsets of a bunch of slave hosts and sends them periodic corrections 👑 in this setup, the master gets picked with an election algorithm [25]. that algorithm is designed so you never end up with no master or with more than one master 🔥 the election needs broadcast capability, though, and broadcast isn't a feature the Internet has everywhere 😭 this model was later extended to allow hierarchical setups, where a slave on one network acts as a master on another [28]. but to pull that off, the model needs handcrafted configuration tables to set up the hierarchy and stop loops from forming 🧩 on top of that, the election process has overhead that's burdensome (though presumably infrequent), and the offset measurement and correction process needs twice as many messages as NTP does per update 💀
a whole lot of research has gone into keeping time accurate when some clocks can't be trusted 🫶 a truechimer is a clock that keeps its timekeeping accurate to a previously published (and trusted) standard. a falseticker is a clock that doesn't 🙅♀️ figuring out which clock is which is an interesting abstract problem, and it can be tackled with methods summarized in [19] and [27] 🔍
a convergence function works on the offsets between the clocks in a system, and it boosts accuracy by cutting down or wiping out the errors that falsetickers cause ✨ there are two classes of convergence functions: interactive convergence algorithms and interactive consistency algorithms 🦋 interactive convergence algorithms use statistical clustering techniques, like the fault-tolerant average algorithm of [17], the CNV algorithm of [19], the majority-subset algorithm of [22], the egocentric algorithm of [27], and the algorithms in Section 4 of this document 💜
interactive consistency algorithms are built to catch faulty clock processes, the ones that might show offsets that are grossly inconsistent across successive readings or between different readers 👀 they use an agreement protocol with successive rounds of readings, which might be relayed and might be augmented by digital signatures 🔐 the fireworks algorithm of [17] and the optimum algorithm of [30] are examples. but these algorithms need huge numbers of messages, especially when lots of clocks are involved, and they're designed to catch faults that have rarely shown up in Internet experience 🥱 so for those reasons, this document doesn't look at them any further ✌️
in practice, you can only tell truechimers from falsetickers on a statistical basis, especially with hierarchical setups and a statistically noisy Internet 🌸 so the approach in this document (and in its predecessors) uses mutually coupled oscillators plus maximum-likelihood estimation and selection procedures 🧁 analytically speaking, the system of distributed NTP peers acts like a set of coupled phase-locked oscillators: the update algorithm works as a phase detector, and the logical clock works as a voltage-controlled oscillator 🌀 that similarity isn't an accident, because systems like this have been studied a lot [3], [4] and [5] 🤓
the particular offset measurement and computation procedure in Section 3 is a variant of the returnable-time system used in some digital telephone networks [3] 💖 the clock filter and selection algorithms are designed so the clock synchronization subnet self-organizes into a hierarchical master-slave configuration [5] 🪜 what makes the NTP model unique is its adaptive configuration, polling, filtering and selection functions, which tune the system's dynamics to fit the ubiquitous Internet environment 🎯 main character energy, honestly 👑
2. System Architecture 🏗️
okay the purpose of NTP is to connect a bunch of primary reference sources (the ones synced to national standards by wire or radio) to widely accessible resources, like backbone gateways 📡 those gateways act as primary time servers, and they use NTP between themselves to cross-check clocks and handle errors caused by equipment or propagation failures 🛡️ then some local-net hosts or gateways act as secondary time servers, running NTP with one or more of the primary servers 🧚 to keep protocol overhead low, the secondary servers pass time along via NTP to the rest of the local-net hosts 🌷 for reliability, selected hosts can get less accurate but cheaper radio clocks, and they're used as backup if the primary and/or secondary servers or the communication paths between them fail 🫧
there's no provision for peer discovery, acquisition, or authentication in NTP 🙈 data integrity comes from the IP and UDP checksums 💜 no circuit-management, duplicate-detection or retransmission facilities are provided, and they aren't necessary either 🌈 the service can run in a symmetric mode, where servers and clients look exactly the same, while still keeping a small amount of state information 🪞 or it can run in client/server mode, where servers don't need to keep any state beyond what's in the client's request 📦 a lightweight association-management capability (including dynamic reachability and variable polling rate mechanisms) is included, but only to manage the state information and cut down on resource requirements 🎀 since only a single NTP message format is used, the protocol is easy to implement and can be used in a variety of solicited or unsolicited polling mechanisms ⭐
now, here's the vibe check ⏳ clock synchronization takes long periods and lots of comparisons to keep timekeeping accurate, by its very nature 🕰️ a few measurements are usually enough to reliably pin down local time to within a second or so, but you need many hours and dozens of measurements to resolve oscillator drift and keep local time within the order of a millisecond 😭 so the accuracy you get depends directly on how long you take to get it. the good news? the frequency of measurements can be quite low, and it's almost always non-intrusive to normal net operations 💅✨
2.1. Implementation Model
okay so the most common setup is basically client/server 💅 a client sends an NTP message to one or more servers and processes the replies as they come in. the server swaps the addresses and ports, overwrites certain fields in the message, recalculates the checksum, and sends it back immediately 🚀 the info in the message lets the client work out the server's time compared to its own local time and adjust its logical clock to match ⏰ it also includes stuff to calculate the expected timekeeping accuracy and reliability, so the client can pick the best one out of possibly several servers 🎀
ngl client/server might be enough for a local net with a public server and maybe lots of workstation clients 💻 but the full generality of NTP needs a bunch of client/servers or peers arranged in a dynamically reconfigurable, hierarchically distributed configuration 🌈 it also needs sophisticated algorithms for association management, data manipulation and logical clock control 🧠 Figure 2.1 shows a possible implementation model with four processes sharing a partitioned data base, with a partition dedicated to each peer and interconnected by a message-passing system ✨
+---------+
| Update |
+--------->| +----------+
| |Algorithm| |
| +----+----+ |
| | |
| V V
+----+----+ +---------+ +---------+
| | | Local | | |
| Receive | | +---->| Timeout |
| | | Clock | | |
+---------+ +---------+ +-+-----+-+
A A | |
| | V V
===========================================
Peers Network Peers
Figure 2.1. Implementation Modelthe timeout process is driven by independent timers for each peer 🕰️ it collects info in the data base and sends NTP messages to other peers in the net. every message contains the local time the message is sent, together with previously received info and other info needed to compute the estimated error and manage the association. the message transmission rate is determined by the accuracy expected of the local system, as well as its peers 💖
the receive process gets NTP messages, and perhaps messages in other protocols too, including ICMP, other UDP or TCP time protocols, local-net protocols and directly connected radio clocks 📡 when an NTP message comes in, the offset between the sender's clock and the local clock gets computed and tossed into the data base along with other info useful for error estimation and clock selection 🫶
the update algorithm kicks off when a message arrives and at other times too 🔥 it processes the offset data from each peer and picks the best peer using algorithms like the ones in Section 4. this might mean lots of observations of a few clocks, or a few observations of many clocks, depending on the accuracies required 👑
the local clock process takes the offset data from the update algorithm and adjusts the phase and frequency of the logical clock using mechanisms like the ones in Section 5 🧚 this can result in a step change or a gradual slew adjustment of the logical clock to bring the offset to zero. the logical clock gives a stable source of time info to other users of the system and for later reference by NTP itself 🌸
2.2. Network Configurations
okay bestie, the setup here is a primary time server connected to a primary reference source, usually a radio clock synced to national standard time ⭐ a secondary time server gets its time sync, possibly through other secondary servers, from a primary server 💜 under normal circumstances a subnet of primary and secondary servers is meant to form a hierarchical master-slave configuration, with the more accurate servers near the top and the less accurate ones below 🦋
borrowing from the telephone industry (they've been doing this forever 💅), each server's accuracy is defined by a number called its stratum. the stratum of a primary server is one, and each level further down the hierarchy is one greater than the level before it 🎀 with current tech and receiving equipment, single-sample accuracies in the order of a millisecond can be hit at the radio clock interface, and in the order of a few milliseconds at the packet interface to the net 😭 accuracies like that need special care in the design and implementation of the operating system, as described in [15], and in the logical clock mechanism, as described in Section 5 🔧
as the stratum goes up from one, the single-sample accuracies you can get will degrade depending on the communication paths and local clock stabilities 📉 to skip the tedious calculations [4] needed to estimate errors for each specific setup, it's useful to assume errors add up approximately in proportion to the minimum total roundtrip path delay between each server and the primary reference source it syncs to. this is called the synchronization distance 🌈
again, the telephone industry learned these lessons the hard way and at serious cost, so the sync paths should be organized to produce the highest accuracies, but must never be allowed to form a loop 🙈 NTP does this with a variant of the Bellman-Ford distributed routing algorithm [29], which computes minimum-weight spanning trees rooted on the primary servers 🧠 the result is that each server operates at the lowest stratum and, when there are multiple peers at the same stratum, at the lowest synchronization distance 👑
because of all this, the subnet reconfigures itself automatically into a hierarchical master-slave configuration to produce the most accurate time, even when one or more primary or secondary servers, or the communication paths between them, fail ✨ that includes the case where all the normal primary servers (e.g., backbone WWVB clocks) on a possibly partitioned subnet fail, but one or more backup primary servers (e.g., local WWV clocks) keep running 🦋
however, if every primary server across the subnet fails, the remaining secondary servers will sync among themselves for some time, then gradually drop off the subnet and coast on their last offset and frequency computations 🌙 since those computations are expected to be very precise, especially in frequency, even extended outages of a day or more should result in timekeeping errors of not over a few tens of milliseconds 🤯
with multiple primary servers, the spanning-tree computation will usually pick the server at minimum synchronization distance 💖 but when those servers are roughly the same distance away, the computation may randomly select among them because of normal dispersive delays 🎲 that usually doesn't hurt accuracy as long as any discrepancy between the primary servers is small compared to the synchronization distance. if it isn't, the filter and selection algorithms will pick the best of the available servers and cast out outliers, as intended 🗑️💅
2.3. Time Scales
so since 1972, the various national time scales have been based on International Atomic Time (TA), which is currently maintained using multiple cesium-beam clocks to an accuracy of a few parts in 10^12 ⚛️🤓 the Bureau International de l'Heure (BIH) uses astronomical observations from the US Naval Observatory and other observatories to determine corrections for small changes in the mean rotation period of the Earth 🌍 that gives you Universal Coordinated Time (UTC), which is currently falling behind TA at a fraction of a second per year 🐢 when the correction gets close to 0.7 second, a leap second is inserted or deleted in UTC on the last day of June or December 🕛 more info on time scales is in [26] 📚
for the most precise coordination and timestamping of events since 1972, you need to know when leap seconds were inserted or deleted in UTC and how the seconds are numbered 🎀 a leap second is inserted after second 23:59:59 on the last day of June or December, and it becomes second 23:59:60 of that day 😳 a leap second would be deleted by skipping second 23:59:59 on one of those days, although that has never happened 🙈 leap seconds were inserted on the following fourteen occasions before January 1988 (courtesy of the US Naval Observatory) 📅
1 June 1972 8 December 1978
2 December 1972 9 December 1979
3 December 1973 10 June 1981
4 December 1974 11 June 1982
5 December 1975 12 June 1983
6 December 1976 13 June 1985
7 December 1977 14 December 1987
Table 2.1. Dates of Leap-Second Insertionlike UTC, NTP runs on an abstract oscillator that's synced in frequency to the TA time scale 🕰️ at 0000 hours on 1 January 1972, the NTP time scale was set to 2,272,060,800, which is the number of TA seconds since 0000 hours on 1 January 1900 🧮 inserting leap seconds in UTC doesn't touch the oscillator itself, only the translation between TA and UTC (aka conventional civil time) 🌸 but since the only institutional memory NTP assumes is the UTC radio broadcast service, the NTP time scale is effectively reset to UTC every time an offset estimate is computed 🔄 so when a leap second gets inserted in UTC and then in NTP, knowledge of all the previous leap seconds is lost 😱 for example, if a clock synced to NTP in early 1988 was used to time an event that happened in early 1972, it would be fourteen seconds early 💀
when NTP is used to measure intervals between events that straddle a leap second, special considerations apply 👀 if you need the elapsed time between events, like the half life of a proton, NTP timestamps of those events can be used directly ⚡ if you need the order of events relative to UTC, like the order of funds transfers, NTP timestamps can also be used directly 💸 but if you need the elapsed time between events relative to UTC, like the intervals between payments on a mortgage, then NTP timestamps must be converted to UTC using the above table and its successors 🏠✨
the current formats used by NBS radio broadcast services [2] don't include provisions for advance notice of leap seconds, so that info has to come from other sources 📻 NTP does include provisions to distribute advance warnings of leap seconds using the Leap Indicator bits described in Section 3 🎉 the protocol is designed so these bits can be set manually at the primary clocks, then automatically distributed throughout the system to all logical clocks, and then put into effect as described in Section 5 💜
3. Network Time Protocol ✨
Okay bestie, this section is the real deal 💅. It's the formal definition of NTP: data formats, entities, state variables, events, and the procedures that process those events 🔥. The spec is built on the implementation model from Figure 2.1, but that's not the only model a spec could use 🦋. The point is to show what NTP does at its core and lay a foundation for a more rigorous, comprehensive, and verifiable spec 🧚.
3.1. Data Formats
All the math here, whether it's written out or implied, is two's-complement arithmetic 🔢. Data is specified as integer or fixed-point quantities. Implementations will probably scale externally derived numbers for their own internal use, so the precision and decimal-point placement for fixed-point quantities are not specified 🤷♀️. Unless stated otherwise, quantities are unsigned and can fill the whole field width (if one is designated), with an implied zero in front of the most significant (leftmost) bit 💖. Hardware and software built for signed quantities will give surprising results when the sign bit is set 💀. It's suggested that externally derived, unsigned fixed-point quantities like timestamps get shifted right one bit for internal use, since the precision of the full field width is rarely justified ✨.
NTP timestamps are cherished data, and they're basically the main product of the protocol 👑, so they get their own special format. An NTP timestamp is a 64-bit unsigned fixed-point number, measured in seconds relative to 0000 UT on 1 January 1900 🎀. The integer part lives in the first 32 bits and the fraction part in the last 32 bits, like this:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Integer Part |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fraction Part |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+This format makes multiple-precision arithmetic easy and converting to Time Protocol representation (seconds) convenient 🧮. It does make converting to ICMP Timestamp message representation (milliseconds) more complicated 🙃. The precision is about 0.2 nanosecond, which should be more than enough for even the most exotic requirements 🌈.
Timestamps get set by copying the current value of the logical clock into a timestamp variable whenever something significant happens, like a message arriving ⏱️. For the highest accuracy, do this as close to the hardware or software driver tied to the event as you possibly can. Specifically, departure timestamps should be redetermined for each link-level retransmission 🔁. Sometimes a timestamp just isn't available, like when the host has rebooted or the protocol has only just started up 😭. In those cases the 64-bit field is set to zero, which means the value is invalid or undefined 🚫.
Heads up: since some time in 1968, the most significant bit (bit 0 of the Integer Part) has been set, and the 64-bit field will overflow sometime in 2036 ⏳. If NTP is still in use in 2036, some external method will be needed to tell whether a time is relative to 1900 or to 2036 (or to another multiple of 136 years) 👀. Timestamped data that needs that sorting will be so precious that the means to do it should be readily available 💎. Also, every 136 years there's an 0.2-nanosecond interval, which we'll henceforth ignore, when the 64-bit field is zero and therefore counts as invalid 🙈.
3.2. State Variables and Parameters
Here's a tabular rundown of all the state variables and parameters the protocol uses 📋. They're sorted into classes: system variables (which relate to the operating system environment and the logical clock mechanism) 🖥️, peer variables (specific to each peer operating in symmetric mode or client mode) 🤝, packet variables (which represent the contents of the NTP message) 📦, and parameters (which are fixed in all implementations of the current version) 💜. For each class, the description of a variable is followed by its name and the procedure or value that controls it. Variables are in lower case, while parameters are in upper case 🔠.
System Variables Name Control
-------------------------------------------------------
Logical Clock sys.clock update
Clock Source sys.peer selection
algorithm
Leap Indicator sys.leap update
Stratum sys.stratum update
Precision sys.precision system
Synchronizing Distance sys.distance update
Estimated Drift Rate sys.drift system
Reference Clock Identifier sys.refid update
Reference Timestamp sys.reftime update
Table 3.1. System Variables Peer Variables Name Control
-------------------------------------------------------
Peer Address peer.srcadr system
Peer Port peer.srcport system
Local Address peer.dstadr system
Local Port peer.dstport system
Peer State peer.state receive,
transmit
Reachability Register peer.reach receive,
transmit
Peer Timer peer.timer system
Timer Threshold peer.threshold system
Leap Indicator peer.leap receive
Stratum peer.stratum receive
Peer Poll Interval peer.ppoll receive
Host Poll Interval peer.hpoll receive,
transmit
Precision peer.precision receive
Synchronizing Distance peer.distance receive
Estimated Drift Rate peer.drift receive
Reference Clock Identifier peer.refid receive
Reference Timestamp peer.reftime receive
Originate Timestamp peer.org receive
Receive Timestamp peer.rec receive
Filter Register peer.filter filter
algorithm
Delay Estimate peer.delay filter
algorithm
Offset Estimate peer.offset filter
algorithm
Dispersion Estimate peer.dispersion filter
Table 3.2. Peer Variables Packet Variables Name Control
-------------------------------------------------------
Peer Address pkt.srcadr transmit
Peer Port pkt.srcport transmit
Local Address pkt.dstadr transmit
Local Port pkt.dstport transmit
Leap Indicator pkt.leap transmit
Version Number pkt.version transmit
Stratum pkt.stratum transmit
Poll pkt.poll transmit
Precision pkt.precision transmit
Synchronizing Distance pkt.distance transmit
Estimated Drift Rate pkt.drift transmit
Reference Clock Identifier pkt.refid transmit
Reference Timestamp pkt.reftime transmit
Originate Timestamp pkt.org transmit
Receive Timestamp pkt.rec transmit
Transmit Timestamp pkt.xmt transmit
Table 3.3. Packet Variables Parameters Name Value
-------------------------------------------------------
NTP Version NTP.VERSION 1
NTP Port NTP.PORT 123
Minimum Polling Interval NTP.MINPOLL 6 (64 sec)
Maximum Polling Interval NTP.MAXPOLL 10 (1024
sec)
Maximum Dispersion NTP.MAXDISP 65535 ms
Reachability Register Size PEER.WINDOW 8
Shift Register Size PEER.SHIFT 4/8
Dispersion Threshold PEER.THRESHOLD 500 ms
Filter Weight PEER.FILTER .5
Select Weight PEER.SELECT .75
Table 3.4. ParametersOkay, so here's the lowdown on each variable the protocol uses 🧁. More details on formats and how they're used show up in later sections and appendices 📚.
3.2.1. Common Variables 🎀
okay so these are the variables that show up in the system, peer, and packet classes, so they're literally everywhere 💅
Peer Address (peer.srcadr, pkt.srcadr) and Peer Port (peer.srcport, pkt.srcport)
These are the 32-bit Internet address and 16-bit port number of the remote host. The remote host is the other side of the conversation 🦋
Local Address (peer.dstadr, pkt.dstadr) and Local Port (peer.dstport, pkt.dstport)
These are the 32-bit Internet address and 16-bit port number of the local host. They're in the state variables so things can work with multi-homing (a host with more than one address), which is so iconic 🌈
Leap Indicator (sys.leap, peer.leap, pkt.leap)
This is a two-bit code that warns about an upcoming leap second getting inserted into the NTP time scale ⏰ The bits get set before 23:59 on the day of insertion and reset after 00:01 on the next day. That makes the number of seconds in the day of insertion go up or down by one. For primary servers, an operator sets the bits by hand, but for secondary servers, the protocol sets them. The two bits are coded like this:
00 no warning (day has 86400 seconds)
01 +1 second (day has 86401 seconds)
seconds)
10 -1 second (day has 86399 seconds)
seconds)
11 alarm condition (clock not synchronized)Except for the alarm condition (11), NTP itself doesn't do anything with these bits. It just passes them along to the time-conversion routines, which aren't part of NTP. The alarm condition shows up when, for whatever reason, the logical clock isn't synchronized. That can happen right when things first come up, or after a long stretch with no outside reference source available 😭
Stratum (sys.stratum, peer.stratum, pkt.stratum)
This is an integer for the stratum of the logical clock. A value of zero means unspecified, one means a primary clock (synchronized by outside means), and everything else is a stratum level (synchronized by NTP) 🍓 When comparing, zero counts as greater than any other value, so it's the big boss of the comparison 👑
Peer Poll Interval (peer.ppoll, pkt.poll)
This is a signed integer, used only in symmetric mode, for the minimum interval between messages sent to the peer. It's measured in seconds as a power of two, so a value of six means a minimum interval of 64 seconds ⭐ The value of this variable must not be less than NTP.MINPOLL and must not be greater than NTP.MAXPOLL.
Precision (sys.precision, peer.precision, pkt.precision)
This is a signed integer for the precision of the logical clock, in seconds, rounded to the nearest power of two. For example, a 60-Hz line-frequency clock would get the value -6, and a 1000-Hz crystal-derived clock would get -10 ✨
Synchronizing Distance (sys.distance, peer.distance, pkt.distance)
This is a fixed-point number for the estimated roundtrip delay to the primary clock, in seconds 🧚
Estimated Drift Rate (sys.drift, peer.drift, pkt.drift)
This is a fixed-point number for the estimated drift rate of the local clock, in dimensionless units 🌸
Reference Clock Identifier (sys.refid, peer.refid, pkt.refid)
This is a code that identifies the particular reference clock or server. What it means depends on the stratum. For stratum zero (unspecified) or one (primary clock), it's an ASCII string naming the reason or the clock, respectively. For stratum values greater than one (synchronized by NTP), it's the 32-bit Internet address of the reference server 💜
Reference Timestamp (sys.reftime, peer.reftime, pkt.reftime)
This is the local time, in timestamp format, of when the logical clock was last updated. If the logical clock has never been synchronized, the value is zero 🙈
3.2.2. System Variables 💖
these are the ones the operating system uses to keep the logical clock in sync 🫶
Logical Clock (sys.clock)
This is the current local time, in timestamp format. Local time comes from the hardware clock of the machine and ticks along at intervals that depend on the design. A design that works, including slewing and drift-compensation mechanisms, is described in Section 5 📖
Clock Source (sys.peer)
This is a selector that identifies the current clock source. Usually it's a pointer to a structure holding the peer variables 🦋
3.2.3. Peer Variables 🌈
this is the list of state variables used by the peer management and measurement functions. There's one set of these for every peer running in client mode or symmetric mode 💅
Peer State (peer.state)
This is a bit-encoded quantity used for various control functions 🎀
Host Poll Interval (peer.hpoll)
This is a signed integer, used only in symmetric mode, for the minimum interval between messages expected from the peer. It's measured in seconds as a power of two, so a value of six means a minimum interval of 64 seconds 🍓 The value of this variable must not be less than NTP.MINPOLL and must not be greater than NTP.MAXPOLL.
Reachability Register (peer.reach)
This is a code used to figure out the reachability status of the peer. It works as a shift register, with bits entering from the least significant (rightmost) end. The size of the register is PEER.SHIFT bits 👑
Peer Timer (peer.timer)
This is an integer counter that controls the interval between transmitted NTP messages ⏰
Timer Threshold (peer.threshold)
This is the timer value that, once reached, makes the timeout procedure run 🌸
Originate Timestamp (peer.org, pkt.org)
This is the local time, in timestamp format, at the peer when its latest NTP message was sent. If the peer becomes unreachable, the value gets set to zero 🥺
Receive Timestamp (peer.rec, pkt.rec)
This is the local time, in timestamp format, of when the latest NTP message from the peer arrived. If the peer becomes unreachable, the value gets set to zero ✨
3.2.4. Packet Variables 🧚
this is the list of variables used in NTP messages, on top of the common variables from above 💜
Version Number (pkt.version)
This is an integer for the version number of the sender. NTP messages always go out with the current version number, NTP.VERSION, and they'll always be accepted if the version number matches NTP.VERSION. Exceptions may be advised on a case-by-case basis at times when the version number changes 🎀
Transmit Timestamp (pkt.xmt)
This is the local time, in timestamp format, at which the NTP message left the sender 🦋
3.2.5. Clock Filter Variables 🌸
when the filter and selection algorithms suggested in Section 4 are used, these state variables get defined. There's one set of them for every peer running in client mode or symmetric mode 🫶
Filter Register (peer.filter)
This is a shift register of PEER.WINDOW bits, where each stage is a tuple made of the measured delay concatenated with the measured offset from one observation. Delay/offset observations enter from the least significant (rightmost) end, get shifted toward the most significant (leftmost) end, and eventually get thrown away as new observations come in. The register gets cleared to zeros when (a) the peer becomes unreachable or (b) the logical clock has just been reset in a way that causes a big discontinuity in local time 💀
Delay Estimate (peer.delay)
This is a signed, fixed-point number for the latest delay estimate output from the filter, in seconds. Even though the number is signed, only values greater than zero count as valid delay estimates 🔥
Offset Estimate (peer.offset)
This is a signed, fixed-point number for the latest offset estimate output from the filter, in seconds 🌈
Dispersion Estimate (peer.dispersion)
This is a fixed-point number for the latest dispersion estimate output from the filter, in scrambled units 🙈
3.2.6. Parameters 👑
this is the list of parameters that every implementation in the Internet system assumes. Everyone has to agree on these values, otherwise you get unnecessary network overhead and the peer associations won't stay stable 🥹
Version Number (NTP.VERSION)
This is the NTP version number, which is currently one (1) 💖
NTP Port (NTP.PORT)
This is the port number (123) that the Internet Number Czar assigned to NTP 🧚
Minimum Polling Interval (NTP.MINPOLL)
This is the minimum polling interval allowed by any peer in the Internet system. It's currently set to 6 (64 seconds) ⭐
Maximum Polling Interval (NTP.MAXPOLL)
This is the maximum polling interval allowed by any peer in the Internet system. It's currently set to 10 (1024 seconds) 🌸
Maximum Dispersion (NTP.MAXDISP)
This is the maximum dispersion assumed by the filter algorithms. It's currently set to 65535 milliseconds 🍓
Reachability Register Size (PEER.WINDOW)
This is the size of the Reachability Register (peer.reach). It's currently set to eight (8) bits 🎀
Shift Register Size (PEER.SHIFT)
When the filter and selection algorithms suggested in Section 4 are used, this is the size of the Clock Filter (peer.filter) shift register, in bits. For crystal-stabilized oscillators, a value of eight (8) is suggested, while for mains-frequency oscillators, a value of four (4) is suggested. More considerations are given in Section 5 🔥
Dispersion Threshold (PEER.THRESHOLD)
When the filter and selection algorithms suggested in Section 4 are used, this is the threshold used to discard noisy data. A value of 500 milliseconds is suggested, but it can be changed to suit local conditions on particular peer paths 🫶
Filter Weight (PEER.FILTER)
When the filter algorithm suggested in Section 4 is used, this is the filter weight used to discard noisy data. A value of 0.5 is suggested, but it can be changed to suit local conditions on particular peer paths 🦋
Select Weight (PEER.SELECT)
When the selection algorithm suggested in Section 4 is used, this is the select weight used to discard outliers. A value of 0.75 is suggested, but it can be changed to suit local conditions on particular peer paths 👑
3.3. Modes of Operation ✨
okay so an NTP host can be in one of three modes 💖: client, server, or symmetric. 🦋 Which one it's in depends on whether the peer.srcport or peer.dstport peer variable holds the assigned NTP service port, NTP.PORT (123). Here's the lineup:
peer.srcport peer.dstport Mode
-------------------------------------------
not NTP.PORT not NTP.PORT not possible
not NTP.PORT NTP.PORT server
NTP.PORT not NTP.PORT client
NTP.PORT NTP.PORT symmetricbestie, the chart does the work for us 😭. Neither port being 123 is the one combo that's not possible 💀.
So in client mode, a host every now and then sends an NTP message to a server. The server basically just swaps the addresses and ports, fills in the info it needs to, and sends the message right back to the client 🎀. The server doesn't have to remember anything between requests, which is so iconic of it 🧚. Clients get to pick how long they wait between messages, based on whatever's happening locally 🌸.
Symmetric mode is where the client/server split just... vanishes 🫶. Each host keeps a table with one entry per active peer 💅. Every entry has a code that uniquely identifies the peer (like its Internet address and port), plus status info and a copy of the timestamps it last got. A host in symmetric mode keeps sending NTP messages to each peer, and every message carries the newest timestamps 🌈. The gap between messages gets worked out together by the host and each peer, using the polling variables peer.ppoll and peer.hpoll ⭐.
When two peers in symmetric mode are trading messages and each one figures out the other is reachable, they've formed an association 💜. At least one of them has to be in active state, meaning it keeps sending messages to the other whether or not it can reach it 🔥. A peer that isn't active is in passive state 🙈. If a passive peer realizes the other one has gone unreachable, it stops sending and frees up the storage and timer resources the association was using 🧹. A client-mode peer is always active, and a server-mode peer is always passive 👑.
3.4. Event Processing 🌈
The big events in NTP happen when the peer timer goes off, which happens once for each peer in symmetric or client mode 💖, and when an NTP message shows up from one of the peers ✨. Events can also come from an operator command or a detected system fault, like a primary clock failing 😬. This section walks through what gets done when each of those happens 🦋.
3.4.1. Timeout Procedure 🎀
The timeout procedure runs in client and symmetric modes once the peer timer (peer.timer) hits the timer threshold (peer.threshold) variable 💅. First, the reachability register (peer.reach) gets shifted one spot to the left, and a zero fills the empty bit 🫧. Then an NTP message gets built and sent to the peer 💌. If the peer is active, or it's passive and peer.reach is nonzero (meaning reachable), the peer.timer restarts from zero and peer.threshold gets set like this:
peer.threshold <- max( min( peer.ppoll, peer.hpoll,
NTP.MAXPOLL), NTP.MINPOLL) .If the peer is active and peer.reach is zero (unreachable), the peer variables get updated like this 😭:
peer.hpoll <- NTP.MINPOLL
peer.disp <- NTP.MAXDISP
peer.filter <- 0 (cleared)
peer.org <- 0
peer.rec <- 0After that, the clock selection algorithm gets called, and it might pick a new clock source (sys.peer) 🔥. In other cases the protocol just stops, and the storage and timer resources get reclaimed so they can be reused later 🧚.
Now for building the NTP message itself (check Appendices A and B for the formats 📚). First the IP and UDP packet variables get copied over from the peer variables, and the source and destination addresses and ports get swapped 🔄:
pkt.srcadr <- peer.dstadr pkt.srcport <- peer.dstport
pkt.dstadr <- peer.srcadr pkt.dstport <- peer.srcportNext, the NTP packet variables get copied from the system and peer variables, rescaled where needed 🍓:
pkt.leap <- sys.leap pkt.distance <- sys.distance
pkt.version <- NTP.VERSION pkt.drift <- sys.drift
pkt.stratum <- sys.stratum pkt.refid <- sys.refid
pkt.poll <- peer.hpoll pkt.reftime <- sys.reftime
pkt.precision <- sys.precisionLast, the timestamp variables get copied. It depends on whether the peer is in symmetric mode and reachable, symmetric mode and not reachable (but still active), or client mode 🎀:
Symmetric Reachable Symmetric Active Client
- ------------------- ------------------- -------------------
pkt.org <- peer.org pkt.org <- 0 pkt.org <- sys.clock
pkt.rec <- peer.rec pkt.rec <- 0 pkt.rec <- sys.clock
pkt.xmt <- sys.clock pkt.xmt <- sys.clock pkt.xmt <- sys.clockThe order of the copies matters a lot 🙈. The copying itself shouldn't eat into the measurement accuracy, which means the sys.clock values should be copied last, like really last 💅. Filling pkt.org and pkt.rec with zeros in the symmetric unreachable case is on purpose: it stops old data from getting reused after a possibly super long stretch of being unreachable 🧊. Using sys.clock for those fields in the client case is genius too 🧠. If the message somehow comes back unchanged (like when you're testing against an Internet-echo server), you can still work out the roundtrip time accurately without any special handling ⏱️✨.
3.4.2. Receive Procedure ✨
okay so this one runs every time an NTP message lands in our inbox 📬🎀. first thing we check is the version number. if pkt.version doesn't match our NTP.VERSION, the message gets tossed 🗑️, though exceptions can be made case by case when the version number itself changes 🦋.
next we ask: is the sender's clock unsynchronized (pkt.leap = 11)? are we in server mode? or are we in symmetric mode and the sender's stratum is higher than ours (pkt.stratum > sys.stratum)? if any of that is true, the message just gets bounced back to the sender with its timestamps 💌. the addresses and ports get swapped in the IP and UDP headers:
pkt.srcadr <-> pkt.dstadr pkt.srcport <-> pkt.dstportthen we refresh the packet variables from our system variables:
pkt.leap <- sys.leap pkt.distance <- sys.distance
pkt.version <- NTP.VERSION pkt.drift <- sys.drift
pkt.stratum <- sys.stratum pkt.refid <- sys.refid
pkt.precision <- sys.precision pkt.reftime <- sys.reftimepkt.poll stays exactly as it was 💅. the timestamps get updated in this order:
pkt.org <- pkt.xmt
pkt.rec <- sys.clock
pkt.xmt <- sys.clockthen it's sent back to the sender and the server receive procedure is over right there 🏁.
if none of that applies, we match the source and destination Internet addresses and ports in the IP and UDP headers to the correct peer. if it matches, we keep going to the next step 🙌. if there's no match and symmetric mode isn't indicated (pkt.srcport or pkt.dstport isn't NTP.PORT), the message has to be a reply to an older message from a client that's no longer running 👻. so we drop it and the receive procedure ends.
if there's no match but symmetric mode is indicated (both pkt.srcport and pkt.dstport equal NTP.PORT), an implementation-specific instantiation procedure gets called to create and initialize a fresh set of peer variables and start the peer timer 🧚. these peer variables get set from the IP and UDP headers:
peer.srcadr <- pkt.srcadr peer.srcport <- pkt.srcport
peer.dstadr <- pkt.dstadr peer.dstport <- pkt.dstportand these get initialized:
peer.state <- symmetric (passive)
peer.timer <- 0 (enabled)
peer.hpoll <- NTP.MINPOLL
peer.disp <- NTP.MAXDISPeverything else in the peer variables is undefined and gets set to zero 🫶.
once instantiation is done and the match happens, we set the least significant bit of the reachability register (peer.reach), which marks the peer as reachable ✅. then we copy the following peer variables over from the NTP packet variables and system variables, rescaling where needed:
peer.leap <- pkt.leap peer.distance <- pkt.distance
peer.stratum <- pkt.stratum peer.drift <- pkt.drift
peer.ppoll <- pkt.poll peer.refid <- pkt.refid
peer.precision <- pkt.precision peer.reftime <- pkt.reftime
peer.org <- pkt.xmt peer.rec <- sys.clock
peer.threshold <- max( min( peer.ppoll, peer.hpoll,
NTP.MAXPOLL), NTP.MINPOLL)⚠️ if either pkt.org or pkt.rec is zero, the sender didn't have reliable values for them, so the receive procedure stops right there 🛑.
if both of them are nonzero, we calculate the roundtrip delay and the clock offset relative to the peer 🧮. number the times of sending and receiving NTP messages as shown in Figure 3.1, and let i be an even integer. then t(i-3), t(i-2), t(i-1) and t(i) are the contents of pkt.org, pkt.rec, pkt.xmt and peer.rec, respectively.
| |
t(1) |------------------->| t(2)
| |
t(4) |<-------------------| t(3)
| |
t(5) |------------------->| t(6)
| |
t(8) |<-------------------| t(7)
| |
...
Figure 3.1. Calculating Delay and Offsetthe roundtrip delay d and the clock offset c of the receiving peer relative to the sending peer work out to:
d = (t(i) - t(i-3)) - (t(i-1) - t(i-2))
c = [(t(i-2) - t(i-3)) + (t(i-1) - t(i))]/2 .this whole approach is basically a continuously sampled, returnable-time system, kind of like what some digital telephone networks use 📞🌸. the perks: the order and timing of the messages don't matter, and reliable delivery isn't required 🙈. the accuracy you can actually get depends on the statistical behaviour of the outbound and inbound net paths. more analysis and experimental results on this are in Appendix D 📚.
the c and d values then go into the clock filter algorithm, which spits out the delay estimate (peer.delay) and the offset estimate (peer.offset) for that peer 🔥. if d ends up nonpositive because of low delays, long polling intervals and high drift rates, it should be considered invalid 🥺. BUT even then it can still be useful to update the local clock and reduce the drift rate until d goes positive again 💜. the clock filter algorithm isn't an official part of the NTP spec, though the one that works really well on the Internet is described in Section 4 ✨.
when a primary clock is hooked up to the host, it's convenient to treat it like an ordinary peer in the database 🕰️. these clocks usually get polled once or twice a minute, and the returned timecheck is used to produce a new update for the logical clock. the update procedure then gets called with these assumed peer variables:
peer.offset <- timecheck - sys.clock
peer.delay <- as determined
peer.dispersion <- 0
peer.leap <- selected by operator, ordinarily 00
peer.stratum <- 0
peer.distance <- 0
peer.refid <- ASCII identifier
peer.reftime <- timecheckfor this kind of clock, peer.delay and peer.refid can just be constants that reflect the clock's type and accuracy 🎀. by convention, peer.delay is ten times the expected mean error of the clock. so for example that's 10 milliseconds for a WWVB clock and 1000 milliseconds for a less accurate WWV clock, but there's a floor of 100 milliseconds 💅. other peer variables, like the peer timer and the reachability register, can control the polling interval and confirm the clock is still working correctly 🧚♀️. this way the clock filter and selection algorithms work the usual way, and they can help mitigate the clock itself if it looks like it's working but is actually delivering bogus time 🙃.
3.4.3. Update Procedure 💫
the update procedure gets called whenever a new delay/offset estimate is available 🔔. first the clock selection algorithm picks the best peer based on estimated accuracy and reliability, which might mean a new clock source (sys.peer) 👑. if sys.peer points at the peer data structure with the just-updated estimates, we use that peer's state variables to update the system state variables like this:
sys.leap <- peer.leap
sys.stratum <- peer.stratum + 1
sys.distance <- peer.distance + peer.delay
sys.refid <- peer.srcadr
sys.reftime <- peer.recfinally, the logical clock procedure gets called with peer.offset as its argument. this updates the logical clock (sys.clock) and recomputes the estimated drift rate (sys.drift) 🌈. sometimes the logical clock gets reset instead of slewed to its final value. when that happens, the peer variables of all reachable peers get updated like this:
peer.hpoll <- NTP.MINPOLL
peer.disp <- NTP.MAXDISP
peer.filter <- 0 (cleared)
peer.org <- 0
peer.rec <- 0then the clock selection algorithm runs again, and this time the result is a null clock source (sys.peer = 0) 🥲. a new selection happens once the filters fill back up and the dispersion settles down 🌸.
the clock selection algorithm and the logical clock procedure aren't an official part of the NTP spec either 🫠. a clock selection algorithm that works well on the Internet is described in Section 4, and a logical clock procedure is described in Section 5 🎀. the one in Section 4 usually picks the server at the highest stratum with the minimum delay out of all the available ones, unless that server looks like a falseticker 🚫. the end result is that all these algorithms work together to build a minimum-weight spanning tree relative to the primary servers. that gives you a hierarchical master-slave system, kind of like some digital telephone networks 🧚.
3.4.4. Initialization Procedures 🌅
when the NTP host reboots, it initializes all the system variables like this:
sys.clock <- best available estimate
sys.leap <- 11 (unsynchronized)
sys.stratum <- 0 (undefined)
sys.precision <- as required
sys.distance <- 0 (undefined)
sys.drift <- as determined
sys.refid <- 0 (undefined)
sys.reftime <- 0 (undefined)sys.clock is presumably undefined after a reboot 🙃. but some designs, like the Fuzzball, can get an estimate from the reboot environment, so it's not always a total mystery ✨. sys.precision is determined by the intrinsic architecture of the local hardware clock 🔧. sys.drift gets worked out as a side effect of later logical clock updates, from whatever source is available 💅.
next, an implementation-specific instantiation procedure gets called over and over to set up the client peers or symmetric (active) peers that will actively probe other servers during regular operation 🧚. the mode and addresses of these peers are determined from information read during the reboot procedure or from operator commands 👩💻.
4. Filtering Algorithms ✨
a super important factor for how accurate and reliable time distribution is comes down to the algorithms that deglitch and smooth the offset estimates, and that cast out outliers caused by failures in the primary reference sources or the propagation media 🧹💖. the algorithms in this section were developed and refined over several years of operation on the Internet, under super varied network configurations and utilization levels 🌍. they're believed to be the best available right now, but they aren't an integral part of the NTP specification 🫶.
there are two algorithms covered here. first is the clock filter algorithm, which picks the best offset samples from a given clock 🔍. second is the clock selection algorithm, which picks the best clock out of a hierarchical set of clocks 👑.
4.1. Clock Filter Algorithm 🫧
okay so the clock filter algorithm runs every time an NTP message shows up with fresh delay/offset sample pairs, bestie 💖 New pairs get shifted into the filter register (peer.filter) from the left end. Zeros fall off first, then the older pairs start falling off the right end. 🍓
Next, the pairs in peer.filter with nonzero delay get copied onto a temporary list and sorted by increasing delay. The delay estimate (peer.delay) and the offset estimate (peer.offset) are whatever delay/offset values belong to the minimum-delay sample. If there's a tie, it's an arbitrary pick, no drama ✨
Now the dispersion estimate (peer.dispersion) is a weighted sum of the offsets on that list. Say the list has PEER.SHIFT entries, and the first m of them hold valid samples in order of increasing delay. If X(i) (0 =< i < PEER.SHIFT) is the offset of the ith sample, then:
d(i) = |X(i) - X(0)| if i < m and |X(i) - X(0)| < 2^15
d(i) = 2^15 - 1 otherwise
peer.dispersion = Sum(d(i)*w^i) ,
(0 =< i < PEER.SHIFT)Here w < 1 is a weighting factor that got tuned by experiment so it matches typical offset distributions 🎀 The peer.dispersion variable is a quality indicator, and the vibe is simple: higher number, lower quality 📉 The plan is that any sample whose peer.dispersion goes over a configured threshold won't get used in later processing. The prototype implementation uses w = 0.5 (that's PEER.FILTER) and a PEER.THRESHOLD of 500 ms. That combo makes sure every stage of peer.filter gets filled and that the offsets stay within a few seconds of each other 🦋
4.2. Clock Selection Algorithm 👑
The clock selection algorithm is the main character of this whole thing 💅 It uses the peer.delay, peer.offset and peer.dispersion values that the clock filter algorithm calculated, and it runs whenever those values change or when the reachability status changes. It builds a list of candidate estimates using a bunch of criteria that are designed to maximize accuracy and reliability, then sorts that list by estimated precision. Last step, it keeps casting out outlyers based on dispersion until only one candidate is left 🔥
The selection process checks each peer, one at a time. It looks at the stuff captured from the last NTP message header it got, plus the latest clock filter estimates. It only keeps peers that pass all of these criteria:
- The peer must be reachable and operating in client or symmetric modes.
- The peer logical clock must be synchronized, as indicated by the Leap Indicator bits being other than 11.
- If the peer is operating at stratum two or greater, it must not be synchronized to this host, which means its reference clock identifier (peer.refid) must not match the Internet address of this host. This is analogous to the split-horizon rule used in some variants of the Bellman-Ford routing algorithm 🌈
- The sum of the peer synchronizing distance (peer.distance) plus peer.delay must be less than 2^13 (8192) milliseconds. Also, the peer stratum (peer.stratum) must be less than eight and peer.dispersion must be less than a configured threshold PEER.THRESHOLD (currently 500 ms). These range checks were established through experience with the prototype implementation, but may be changed in future. 🧚
For every peer that passes those criteria, a sixteen-bit keyword gets built. The low-order thirteen bits are the sum of peer.distance plus peer.delay, and the high-order three bits are the peer.stratum reduced by one and truncated to three bits (so zero gets mapped to seven, iykyk 🙈). The keyword and a pointer to the peer data structure get inserted in order of increasing keyword values, and the list gets truncated at a maximum of eight entries. The end result is the order the peers should be picked in, based on estimated measurement precision ✨ If no keywords turn up at all, the clock source variable (sys.peer) gets set to zero and the algorithm just ends 💀
The final procedure is built to catch falsetickers and other stuff that could cause gross errors 😭 Let m be the number of samples left in the list. For each i (0 =< i < m), compute the dispersion d(i) of the list relative to i:
d(i) = Sum(|X(j) - X(i)|*w^j) ,
(0 =< j < m)Here w < 1 is a weighting factor that got adjusted by experiment for the characteristic you want (more on that below). Then cast out the entry with the maximum d(i), or if there's a tie, the maximum i, and repeat the whole thing. Once only one entry is left, sys.peer gets set to that entry's peer data structure pointer, and the peer.hpoll variable in that structure gets set to NTP.MINPOLL, as required by the logical clock mechanism described in Section 5 🎀
This procedure favors the peers near the head of the list, since those are at the highest stratum with the lowest delay and can presumably give the most precise time 👑 With a good choice of weighting factor w (also called PEER.SELECT), entries get trimmed from the tail of the list. The exception is when a few outlyers disagree a lot with the rest. In that case the outlyers get tossed first 💅
Let's see how this works on outlyers. Picture three entries, with some offsets clustered around zero and others clustered around one. For w = 0.75, which the prototype implementations use, and multiplying by 16 for convenience, the first entry has weight w^0 = 16, the second has w^1 = 12, and the third has w^2 = 9. Table 4.1 shows every combination of peer offsets, with the dispersion about each of the three entries, plus what the procedure does with them 🦋
Peer 0 1 2 Dispersion Cast Result
Weight 16 12 9 0 1 2 Out
------------------------------------------------------
0 0 0 0 0 0 2 0 0
0 0 1 9 9 28 2 0 0
0 1 0 12 25 12 1 0 0
0 1 1 21 16 16 0 1 1
1 0 0 21 16 16 0 0 0
1 0 1 12 25 12 1 1 1
1 1 0 9 9 28 2 1 1
1 1 1 0 0 0 2 1 1Table 4.1. Outlyer Selection Procedure
In the four cases where peer 0 and peer 1 disagree, peer 2 is the one that decides the outcome 🫶 Similar outcomes happen with four peers. Those outcomes do depend on picking w carefully, but the algorithm behaves pretty much the same for any w between 0.5 and 1.0 ✨
4.3. Variable-Rate Polling 🌸
As NTP service grows across the Internet, the network traffic it creates can get seriously heavy, especially in the primary service net 😩 So it's useful to explore variable-rate polling, where the gaps between NTP messages can be adjusted to fit whatever the network conditions are like, in terms of delay dispersion and loss rate. The prototype NTP implementation uses this trick to cut network overhead down to one-sixteenth of the maximum rate, depending on the dispersion and loss it observes 🍓
The prototype implementation adjusts the polling interval peer.hpoll based on the reachability register (peer.reach) along with the dispersion (peer.dispersion) variable. As long as sys.peer doesn't point at the peer data structure, peer.reach is nonzero (reachable), and peer.dispersion is less than the PEER.THRESHOLD parameter, peer.hpoll goes up by one on each call to the update procedure, capped at NTP.MAXPOLL. After the timeout procedure, if peer.reach shows that no messages have arrived for the preceding two polling intervals (the low-order two bits are zero), peer.hpoll goes down by one, but not below NTP.MINPOLL. If peer.reach becomes zero (unreachable), peer.hpoll gets set to NTP.MINPOLL 💜
So the net effect is this: for peers that aren't picked for synchronization and are in symmetric mode, the polling intervals creep upward once the filter register (peer.filter) is full and peer.dispersion has settled down 📈 But they drop again if peer.dispersion goes up, if the loss rate goes up, or if the peer becomes unreachable 🌈
5. Logical Clocks ✨
Okay so, to build a logical clock your host needs a hardware clock (an oscillator plus an interface) that's precise and stable enough for the job 🕰️. The logical clock gets nudged by periodic offset corrections that come from NTP or another time-sync protocol, like Hellospeak [15] or the Unix 4.3bsd TSP [20]. The Fuzzball logical clock is the one we're looking at next. It has extra features for precise time and frequency adjustment, and it can keep time within a millisecond and frequency within a day per millisecond 💅
So the logical clock runs on a 48-bit Clock Register that ticks at 1000-Hz (at the decimal point). There's also a 32-bit Clock-Adjust Register that slews the Clock Register whenever offset corrections come in, and a Drift-Compensation Register that trims the oscillator frequency 🎀 Some interface designs, like the DEC KWV11, add a Counter Register as an auxiliary counter. Check out the layout and decimal point positions in Figure 5.1 below 👀
Clock Register
0 16 32
+---------------+---------------+---------------+
| | | |
+---------------+---------------+---------------+
A
decimal point
Clock-Adjust Register
0 16
+---------------+---------------+
| | |
+---------------+---------------+
A
decimal point
Drift-Compensation Register
0 16
+---------------+
| |
+---------------+
A
decimal point
Counter Register
0 16
+---------------+
| |
+---------------+
A
decimal pointFigure 5.1. Clock Registers
The Clock Register, Clock-Adjust Register and Drift-Compensation Register all live in memory 🧠 On typical clock interfaces like the DEC KWV11, the Counter Register is a buffered counter driven by a crystal oscillator. When it overflows, an interrupt goes off, which bumps the Clock Register at bit 15 and carries the propagation through as needed ⚡ To get the time of day, you read the Counter Register (reading it doesn't interrupt the counting, which is so cute of it) and add that value to the Clock Register, with the decimal points lined up 🌸
Other interface designs, like the LSI-11 event-line mechanism, do it differently. Each clock tick sends an interrupt every 16-2/3 or 20 ms, depending on the interface and the mains frequency. When that happens, the matching increment in milliseconds, expressed to 32 bits of precision, gets added to the Clock Register with the decimal points aligned 🦋
5.1. Uniform Phase Adjustments
Left alone, the logical clock just runs at the speed of its own oscillator, which is a vibe but not an accurate one 😭 A correction comes in as a signed 32-bit integer in milliseconds. It gets added to the Drift-Compensation Register, and it also replaces bits 0-15 of the Clock-Adjust Register, with bits 16-31 set to zero. Every adjustment interval of CLOCK.ADJ, the clock computes a correction made of two parts. The first is the phase component: take the Clock-Adjust Register, shift it right CLOCK.PHASE bits, and subtract that from the Clock-Adjust Register. The second is the frequency component: take the Drift-Compensation Register and shift it right CLOCK.FREQ bits. Add the phase and frequency parts together and you get the correction, which then gets added to the Clock Register. This keeps going until a new correction shows up 🔁
Now, the implementation has to be careful. It needs to keep the Clock Register monotonic (time never runs backward), keep the highest precision it can, and avoid spreading roundoff errors everywhere. A good way to handle that is to buffer the corrections and add them in with the increment the next time the Clock Register updates 🧩 Monotonicity is guaranteed with the parameters in Table 5.1, as long as the increment is at least 2 ms. The table shows the parameters we just talked about, plus a few more, for both a crystal-stabilized oscillator and a mains-frequency oscillator 📊
Parameter Name Crystal Mains
-------------------------------------------------------------------
Update Interval CLOCK.ADJ 4 sec 1 sec
Phase Shift CLOCK.PHASE -8 -9
Frequency Shift CLOCK.FREQ -16 -16
Maximum Aperture CLOCK.MAX +-128 ms +-256 ms
Shift Register Size PEER.SHIFT 8 4
Host Poll Interval peer.hpoll NTP.MINPOLL NTP.MINPOLL
(64 sec) (64 sec)Table 5.1. Clock Parameters
Here's the big picture: this whole setup is a second-order phase-lock loop. It adjusts both the logical clock's phase and its frequency to cancel out the jitter, wander and drift of the oscillator 🌈 The team simulated a loop using the Table 5.1 values for a crystal-stabilized oscillator, along with the clock filter from Section 4. The transient response went like this: for a 100 ms phase correction, the loop hit zero error in 34 minutes, overshot by 7 ms at 76 minutes, and settled to under 1 ms in about four hours. The biggest frequency error was about 6 ppm at 40 minutes, and it dropped back under 1 ppm in about eight hours. For a 10 ppm frequency correction, the loop settled within 1 ppm in about nine hours and within 0.1 ppm in about a day. These numbers are right for normal computers with board-mounted crystals and no oven temperature control 💖
Mains-frequency oscillators are a whole different story 🙈 The national power grid has much higher jitter and wander, with daily peak-to-peak phase swings that can go past four seconds, so those loops need different parameters. The simulation with the Table 5.1 mains values and the Section 4 clock filter gave a transient response similar to the crystal case, but with time constants only one-fourth as long. When they tested it against real phase-offset data from typical Summer days, when jitter and wander were at their worst, the loop errors were a few tens of milliseconds and never went above 150 ms 🔥
Heads up, though: the simulations assume the clock filter always picks the oldest sample in the shift register at each step 👀 So the filter acts like a delay line, with a delay equal to the polling interval times the number of stages. That's the worst case, because the bigger the overall delay, the harder it is to keep loop errors low while also getting a good transient response. The Table 5.1 parameters were worked out experimentally under that scenario and with the rule that the polling interval couldn't drop below 64 seconds. With these parameters, you can't push the polling interval above 64 seconds without a big jump in loop error or a worse transient response. So when a clock gets selected using the Section 4 algorithms, peer.hpoll is always set to NTP.MINPOLL ✨
5.2. Nonuniform Phase Adjustments
Sometimes a correction is so big that it goes past the maximum aperture CLOCK.MAX. Then the clock might be so far out of sync with the reference source that the best move is to immediately swap out the whole Clock Register contents, instead of slowly slewing it like we did before 💀 In practice, this is rare, and it usually happens after the local host or reference source reboots, for example. That's lucky, honestly, because step changes can make the clock look like it's running backward, and they can also mess up the delay and offset measurements of the synchronization mechanism itself 😵💫
Lots of experience with the Internet suggests the CLOCK.MAX values in Table 5.1 are the right ones to use. In practice, a single time-server source only goes past these values during extreme congestion, or when several nodes or links fail at once 🌪️ The most common reason it gets exceeded is when the time-server source changes and the new and old sources disagree by more than the maximum. That can happen because of systematic errors in the primary reference source, or because the synchronizing paths have very different delays 🫶
5.3. Maintaining Date and Time
Converting from NTP format into the common date and time formats that application programs use is way easier if the internal local-clock format keeps separate date and time registers 📅 The time register is designed to roll over every 24 hours, give or take a leap second as signaled by the Leap Indicator bits. Its overflows (and underflows) bump the date register up (or down) by one. Together, the date and time registers show the number of days and seconds since some earlier reference time, but they aren't corrected for leap seconds yet 🧚
Here's how a leap second gets handled. On the day before a leap second is inserted, the Leap Indicator bits get set at the primary servers, probably by hand 🙋♀️ Those bits eventually show up at the local host and get passed to the logical clock procedure. That changes the modulus of the time register, which is just the length of the current day, so it goes up or down by one second as needed. On the day after the insertion, the bits get turned off at the primary servers. Turning them off automatically is possible, but the procedure suggested here makes sure every clock has already rolled over, so none of them get reset to the previous day by accident because of corrections right near the rollover moment 🌙
5.4. Estimating Errors ✨
Okay so after an NTP message comes in and before the next one shows up, the local clock's accuracy is expected to slip a little 📉. How much it slips depends on the error at the last update time plus how much the local oscillator drifts over time. The fun part is that you can estimate both the error and the drift from data you already collect during normal operation 🧠. Those estimates can then tell you how often NTP neighbors should swap messages, which keeps the net overhead under control 💅.
NTP messages carry a bunch of goodies: the sender's local-clock precision, its reference time, its estimated drift, and something called the synchronizing distance 🎀. The local precision, together with the precision of the peer clocks, sets the short-term jitter characteristics of the offset estimates. The reference time and estimated drift give you an error estimate for the moment the latest update was received. The synchronizing distance estimates the error relative to the primary reference source, and the filtering algorithms use it to make the offset estimates better and more reliable 🫶.
Honestly the error and drift estimates aren't essential for the clock algorithms to work correctly 🙈. They do make things more accurate and help with tuning net overheads, though. The estimated error lets the recipient work out how often independent samples are needed to keep a specified estimated error. The estimated drift rate lets the recipient estimate the optimum polling interval ⭐.
Here's the wild part: you can compute the estimated drift rate of the local clock super precisely by just adding the n offsets received during an interval T to an accumulator 🤯. If X1 and X2 are the accumulator values at the beginning and end of T, the estimated drift rate r is:
X2 - X1 n
r = ------- --- .
n TThe intrinsic (uncorrected) drift rate of typical crystal oscillators at room temperature is somewhere from a few parts per million (ppm) up to as much as 100 ppm, which is up to a few seconds per day 😭. For most purposes, a particular crystal oscillator's drift stays constant to within maybe one ppm. So if T can be estimated to within 100 ms, for example, it takes about a day of accumulation to estimate r to an uncertainty on the order of one ppm 🌈.
Some idea of the local clock's estimated error can come from the variance of the offsets about the mean per unit time. You get this by adding the n offset squares received during T to an accumulator. If Y1 and Y2 are the accumulator values at the beginning and end of T, the estimated error s is:
Y2 - Y1 (X2 - X1)^2 n
s = ( ------- - ----------- ) --- .
n n * n TThe quantities r and s are super useful to the peer, as we just covered 💖. But they're also useful to the recipient of an NTP message that peer sent 👑. They can be used as weights in algorithms like the ones described in [22], and they can improve the estimates during stretches when offsets aren't available. It's most useful when the latest r and s estimates are included in every NTP message that gets sent, but there's still plenty of room to decide the details of how they're computed and stored 🦋.
The formulae above imply equal weighting for all the offsets received throughout the accumulation interval T. One way to get that is a software shift register built as a circular buffer 🧚. A single pointer points at the active entry, and it moves forward one entry each time a new offset gets stored. There are two accumulators, one for the offsets and one for their squares. When a new offset arrives, the new offset minus the old active entry gets added to the first accumulator, and the square of that difference gets added to the second. Last step: the new offset gets stored in the circular buffer 🍓.
How big the circular buffer needs to be depends on the accumulation interval T and how fast offsets get produced 📏. In lots of reachability and routing algorithms, like GGP, EGP and local-net control algorithms, peers swap messages about once or twice a minute. If NTP peers exchanged messages once per minute and T were one day, the circular buffer would need to be 1440 words long 😳. A less costly design might aggregate the data in roughly half-hour segments instead, which shrinks the buffer to 48 words without really hurting the quality of the data 💅✨.
6. References 📚
- Lamport, L., "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, Vol. 21, No. 7, pgs. 558-565, July 1978.
- "Time and Frequency Dissemination Services", NBS Special Publication No. 432, US Department of Commerce, 1979.
- Lindsay, W., and A. Kantak, "Network Synchronization of Random Signals", IEEE Trans. Comm., COM-28, No. 8, pgs. 1260-1266, August 1980.
- Braun, W., "Short Term Frequency Effects in Networks of Coupled Oscillators", IEEE Trans. Comm., COM-28, No. 8, pgs. 1269-1275, August 1980.
- Mitra, D., "Network Synchronization: Analysis of a Hybrid of Master-Slave and Mutual Synchronization", IEEE Trans. Comm. COM-28, No. 8, pgs. 1245-1259, August 1980.
- Postel, J., "User Datagram Protocol", RFC-768, USC/Information Sciences Institute, August 1980.
- Mills, D., "Time Synchronization in DCNET Hosts", IEN-173, COMSAT Laboratories, February 1981.
- Mills, D., "DCNET Internet Clock Service", RFC-778, COMSAT Laboratories, April 1981.
- Su, Z., "A Specification of the Internet Protocol (IP) Timestamp Option", RFC-781, SRI International, May 1981.
- Defense Advanced Research Projects Agency, "Internet Protocol", RFC-791, USC/Information Sciences Institute, September 1981.
- Defense Advanced Research Projects Agency, "Internet Control Message Protocol", RFC-792, USC/Information Sciences Institute, September 1981.
- Postel, J., "Daytime Protocol", RFC-867, USC/Information Sciences Institute, May 1983.
- Postel, J., "Time Protocol", RFC-868, USC/Information Sciences Institute, May 1983.
- Mills, D., "Internet Delay Experiments", RFC-889, M/A-COM Linkabit, December 1983.
- Mills, D., "DCN Local-Network Protocols", RFC-891, M/A-COM Linkabit, December 1983.
- Gusella, R., and S. Zatti, "TEMPO - A Network Time Controller for a Distributed Berkeley UNIX System", IEEE Distributed Processing Technical Committee Newsletter 6, No. SI-2, pgs. 7-15, June 1984. Also in: Proc. Summer 1984 USENIX, Salt Lake City, June 1984.
- Halpern, J., Simons, B., Strong, R., and D. Dolly, "Fault-Tolerant Clock Synchronization", Proc. Third Annual ACM Symposium on Principles of Distributed Computing, pgs. 89-102, August 1984.
- Lundelius, J., and N. Lynch, "A New Fault-Tolerant Algorithm for Clock Synchronization:, Proc. Third Annual ACM Symposium on Principles of Distributed Computing, pgs. 75-88, August 1984.
- Lamport, L., and P. Melliar-Smith "Synchronizing Clocks in the Presence of Faults", JACM 32, No. 1, pgs. 52-78, January 1985.
- Gusella, R., and S. Zatti, "The Berkeley UNIX 4.3BSD Time Synchronization Protocol: Protocol Specification", Technical Report UCB/CSD 85/250, University of California, Berkeley, June 1985.
- Marzullo, K., and S. Owicki, "Maintaining the Time in a Distributed System", ACM Operating Systems Review 19, No. 3, pgs. 44-54, July 1985.
- Mills, D., "Algorithms for Synchronizing Network Clocks", RFC-956, M/A-COM Linkabit, September 1985.
- Mills, D., "Experiments in Network Clock Synchronization", RFC-957, M/A-COM Linkabit, September 1985.
- Mills, D., "Network Time Protocol (NTP)", RFC-958, M/A-COM Linkabit, September 1985.
- Gusella, R., and S. Zatti, "An Election Algorithm for a Distributed Clock Synchronization Program", Technical Report UCB/CSD 86/275, University of California, Berkeley, December 1985.
- Sams, H., "Reference Data for Engineers: Radio, Electronics, Computer and Communications (Seventh Edition)", Indianapolis, 1985.
- Schneider, F., "A Paradigm for Reliable Clock Synchronization", Technical Report TR 86-735, Cornell University, February 1986.
- Tripathi, S., and S. Chang, "ETempo: A Clock Synchronization Algorithm for Hierarchical LANs - Implementation and Measurements", Systems Research Center Technical Report TR-86-48, University of Maryland, 1986.
- Bertsekas, D., and R. Gallager, "Data Networks", Prentice-Hall, Englewood Cliffs, NJ, 1987.
- Srikanth, T., and S. Toueg. "Optimal Clock Synchronization", JACM 34, No. 3, pgs. 626-645, July 1987.
- Rickert, N., "Non Byzantine Clock Synchronization - A Programming Experiment", ACM Operating Systems Review 22, No. 1, pgs. 73-78, January 1988.
Appendix A. UDP Header Format 🎀
Picture this: an NTP packet is the UDP header followed by the NTP data portion 💜. The format of the UDP header and how its fields get interpreted are described in [6], and they aren't part of the NTP specification itself. They're shown below anyway, just for completeness 🫶.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Source Port
UDP source port number. In a client request, this field is assigned by the client host. In a server reply, it's copied from the Destination Port field of the client request. In symmetric mode, both the Source Port and Destination Port fields are assigned the NTP service-port number 123 💅.
Destination Port
UDP destination port number. In a client request, this field is assigned the NTP service-port number 123. In a server reply, it's copied from the Source Port field of the client request. In symmetric mode, both the Source Port and Destination Port fields are assigned the NTP service-port number 123 🌸.
Length
Length of the request or reply, including the UDP header, in octets 📦.
Checksum
Standard UDP checksum ✅.
Appendix B. NTP Data Format - Version 1 ✨
okay bestie, this is the NTP data portion that sits right after the UDP header 💖 here's the layout, then what each field means 🎀
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |0 0 0| Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Synchronizing Distance |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Estimated Drift Rate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference Clock Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Reference Timestamp (64 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originate Timestamp (64 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Receive Timestamp (64 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Transmit Timestamp (64 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Leap Indicator (LI) 🌸
This is a two-bit code that warns about an impending leap second, which gets inserted at the end of the last day of the current month. The bits mean:
00 no warning
01 +1 second (following minute has 61 seconds)
10 -1 second (following minute has 59 seconds)
11 alarm condition (clock not synchronized)Version Number (VN) 🦋
A three-bit code for the version number. Right now it's one (1) ✨
Reserved 🫶
A three-bit field that's all zeros and is saved for future use, so nothing to see here yet 🧚
Stratum 👑
An integer that tells you the stratum level of the local clock. The values go like this:
0 unspecified
1 primary reference (e.g., radio clock)
2...n secondary reference (via NTP)Poll 💜
A signed integer giving the maximum interval between successive messages, in seconds, rounded to the nearest power of two.
Precision 🍓
A signed integer giving the precision of the local clock, in seconds, rounded to the nearest power of two.
Synchronizing Distance 🔥
A fixed-point number giving the estimated roundtrip delay to the primary synchronizing source, in seconds. The fraction point sits between bits 15 and 16.
Estimated Drift Rate ⭐
A fixed-point number giving the estimated drift rate of the local clock. It's dimensionless, and the fraction point is to the left of the most significant bit.
Reference Clock Identifier 🌈
This is the code that identifies the particular reference clock. For type 0 (unspecified) or type 1 (primary reference), it's a left-justified, zero-filled ASCII string. Some examples:
Type Code Meaning
---------------------------------------------------
0 DCN Determined by DCN routing algorithm
1 WWVB WWVB radio clock (60 kHz)
1 GOES GOES satellite clock (468 MHz)
1 WWV WWV radio clock (5/10/15 MHz)
(and others as necessary)For type 2 and greater (secondary reference), it's the 32-bit Internet address of the reference host instead. 💅
Reference Timestamp 🧚
The local time at which the local clock was last set or corrected.
Originate Timestamp 🎀
The local time at which the request left the client host for the service host.
Receive Timestamp 🦋
The local time at which the request arrived at the service host.
Transmit Timestamp 💖
The local time at which the reply left the service host for the client host.
Appendix C. Timeteller Experiments 🧪
okay this one is giving science-experiment main character energy 😭 back in January 1988 they ran a glorious three-day experiment to update the data collected in June 1985 and reported in RFC-957 🎀 they sent four packets, five seconds apart, to every host and gateway in the NIC data base, using UDP/NTP, UDP/TIME and ICMP/TIMESTAMP ✨ then they averaged the clock offsets (in milliseconds) for each protocol against local time, which was synced via NTP to a radio-clock host.
ICMP/TIMESTAMP has much finer granularity (milliseconds) than UDP/TIME (seconds), but it has no provisions for the date, so it's not suitable as a time-synchronization protocol. They still put it in the experiments as a sanity check and to measure precision 🤓
In the latest survey, 5498 hosts and 224 gateways were checked. 46 responded to UDP/NTP requests, 1158 to UDP/TIME and 1963 to ICMP/TIMESTAMP 💜 Back in the 1985 survey of 1775 hosts and 110 gateways, 163 responded to UDP/TIME requests and 504 to ICMP/TIMESTAMP. There were no UDP/NTP implementations at that time at all 🌸 There are way more hosts and gateways in the rapidly growing domain-name system that aren't in the NIC data base, so they weren't surveyed 🙈
Table C.1 shows, for each of the three protocols, the error X where the distribution function P[x =< X] has the value shown:
P[x=<X] UDP/NTP UDP/TIME ICMP/TIMESTAMP
------------------------------------------------------
.1 11 4632 5698
.2 37 18238 27965
.3 66 38842 68596
.4 177 68213 127367
.5 364 126232 201908
.6 567 195950 285092
.7 3466 267119 525509
.8 20149 422129 2.91426E+06
.9 434634 807135 5.02336E+07
1 1.17971E+09 1.59524E+09 2.11591E+09
Table C.1. Distribution FunctionsSo here's the tea ☕ ten percent of the UDP/NTP responses show errors of 11 milliseconds or less, while ten percent of the UDP/TIME responses show errors greater than 807135 milliseconds (about 13 minutes) 😭 Fifty percent of the UDP/NTP timetellers are within 364 milliseconds, but fifty percent of the UDP/TIME tellers are within 126232 milliseconds (just over two minutes). Surprisingly, ICMP/TIMESTAMP responses show errors even larger than UDP/TIME 💀
The maximum error across all three protocols went past what could be recorded, which was about 12 days! Clearly, there are good timetellers and bad 🫠👑
Appendix D. Evaluation of Filtering Algorithms 🔍
okay so back in RFC-956 there were a bunch of algorithms for deglitching and filtering time-offset data 💅 they split into two classes. Majority-subset algorithms try to separate good subsets from bad by comparing their means. Clustering algorithms try to improve the estimate by repeatedly casting out outlyers. The first class was suggested for picking the best (i.e. the most reliable) clocks from a population, and the second was suggested for improving the offset estimate for a single clock given a series of observations ✨
After RFC-956 came out, and after more development and experiments on typical Internet paths, they found a better way to cast out outlyers from a continuous stream of offset observations spaced minutes apart 🦋 It's a variant of a median filter. A window holding the last n sample offsets keeps getting updated, and the median sample gets picked as the estimate. The twist is that the outlyer (the sample furthest from the median) gets thrown out, and the whole process repeats until only a single sample offset is left, and that one becomes the estimate. 🎀
The modified algorithm was more resistant to glitches and gave a more accurate estimate than the unmodified one ✨ It's been running in the NTP daemons for the Fuzzball and Unix operating systems, and it's been in regular operation for about two years 🌈 But then recent experiments showed there's an even better one 😭 It gives comparable accuracy with a much lower computational burden 🔥 The key to the new algorithm came out of looking at scatter diagrams that plot sample offset against roundtrip delay 📊
To see how a scatter diagram gets built, we need to look at how offsets and delays get computed 🧠 Number the times of sending and receiving NTP messages as shown in Figure D.1, and let i be an even integer. Then the timestamps t(i-3), t(i-2), t(i-1) and t(i) are enough to calculate the offset and delay of each peer relative to the other 💜
Peer 1 Peer 2
| |
t(1) |------------------->| t(2)
| |
t(4) |<-------------------| t(3)
| |
t(5) |------------------->| t(6)
| |
t(8) |<-------------------| t(7)
| |
...
Figure D.1. Calculating Delay and OffsetHere's the math 🧮 The roundtrip delay d and the clock offset c of the receiving peer relative to the sending peer are:
d = (t(i) - t(i-3)) - (t(i-1) - t(i-2))
c = [(t(i-2) - t(i-3)) + (t(i-1) - t(i))]/2 .Okay so bestie, the wedge thing is literally the whole vibe 🧚✨ Two assumptions are hiding in the background here: the delay is the same in both directions, and the drift rates of the client and server clocks are small and basically match 🫶. If those held, the scatter diagram would look like a neat horizontal line running right from the point (d,c). But that is NOT what real life looks like 💀 The typical plot is a wedge 🎀 with its tip at (d,c) that flares out to the right. The edges come from lines leaving (d,c) with slopes +0.5 and -0.5, which trace what happens when the delay goes up in one direction while the other direction stays chill. Sometimes the points pile up right along those two edge lines, with only a few sitting inside the wedge, and that would mean the delays went up in both directions at once 😭
Honestly, once you think about it, the shape makes total sense 🦋 Packet-switched networks usually run with tiny average queue lengths, around one, so the queues are empty most of the time. On top of that, routing is usually tuned to use as few packet-switch hops as possible, which means fewer queues to wait in. So a NTP packet landing on a busy queue in one direction is already pretty unlikely, and landing on busy queues in both directions is even less likely 🍓
So at low utilization and low hop counts, the points should hang out near the tip of the wedge and start stretching right along those edge lines as the utilization and hop counts climb. When things get even busier, the points should start filling in the wedge as it keeps opening up. And wouldn't you know it, that is what people actually see on real Internet paths through ARPANET, NSFNET, and other nets 👑
These observations make the median filter look kinda sus as a way to throw out offset outlyers 🙈 They point toward a different idea, which we could call a minimum filter. The scatter plots make it super clear that the best offset samples are the ones with the lowest delays. So the move is to look at the n most recent samples, pick the one with the lowest delay, and use its offset as the estimate ✨ To test this, they ran an experiment between selected hosts that had radio clocks, so the delays and offsets could be measured without depending on the measurement process itself 🌸
The raw delays and offsets came from NTP runs between hosts at U Maryland (UMD) and U Delaware (UDEL), over net paths to each other and to other hosts at Ford Research (FORD), Information Sciences Institute (ISI), and National Center for Atmospheric Research (NCAR). For this purpose, every host can be treated as synced to within a few milliseconds of NBS time, which means the delays and offsets only reflect the net paths 💖
The results are in Table D.1 (UMD) and Table D.2 (UDEL). For each path they show the error X where the distribution function P[x =< X] hits the value listed. The probabilities are listed in steps that get smaller as the function climbs, so the low-error-probability region, which is the part we actually care about, can be pinned down more precisely 🧁
UMD FORD ISI NCAR UMD FORD ISI NCAR
Delay 1525 2174 1423 Offset 1525 2174 1423
--------------------------- ---------------------------
.1 493 688 176 .1 2 17 1
.2 494 748 179 .2 4 33 2
.3 495 815 187 .3 9 62 3
.4 495 931 205 .4 18 96 8
.5 497 1013 224 .5 183 127 13
.6 503 1098 243 .6 4.88E+8 151 20
.7 551 1259 265 .7 4.88E+8 195 26
.8 725 1658 293 .8 4.88E+8 347 35
.9 968 2523 335 .9 4.88E+8 775 53
.99 1409 6983 472 .99 4.88E+8 2785 114
.999 14800 11464 22731 .999 4.88E+8 5188 11279
1 18395 15892 25647 1 4.88E+8 6111 12733
Table D.1. Delay and Offset Measurements (UMD)
UDEL FORD UMD ISI NCAR
Delay 2986 3442 3215 2756
-----------------------------------
.1 650 222 411 476
.2 666 231 436 512
.3 692 242 471 554
.4 736 256 529 594
.5 787 272 618 648
.6 873 298 681 710
.7 1013 355 735 815
.8 1216 532 845 1011
.9 1836 1455 1019 1992
.99 4690 3920 1562 4334
.999 15371 6132 2387 11234
1 21984 8942 4483 21427
Table D.2.a Delay Measurements (UDEL)
UDEL FORD UMD ISI NCAR
Offset 2986 3442 3215 2756
-----------------------------------
.1 83 2 16 12
.2 96 5 27 24
.3 108 9 36 36
.4 133 13 48 51
.5 173 20 67 69
.6 254 30 93 93
.7 429 51 130 133
.8 1824 133 165 215
.9 4.88E+8 582 221 589
.99 4.88E+8 1757 539 1640
.999 4.88E+8 2945 929 5278
1 5.63E+8 4374 1263 10425
Table D.2.b Offset Measurements (UDEL)The big takeaway 🔥 is that accuracy under a few seconds is usually doable for all but about one percent of the measurements, but once that last one percent gets included, things fall apart FAST 💀 Quick side note: for UMD to FORD, almost half the measurements were gross errors, and that came from equipment failure at that site. They left that data in on purpose, so they could see how well the algorithms handle a mess 🫶
Next up, Table D.3 (minimum filter) and Table D.4 (median filter) compare different values of n using the raw UMD - NCAR sample data 🌈 The minimum filter keeps getting lower errors than the median filter with the nearest value of n 😌 The really dramatic bit, for both filters, is how much the error shrinks at the top end of the range. In fact, using either filter with n of at least three means no error is bigger than 100 milliseconds 🎀
Filter Samples
1 2 4 8 16
P[x=<X] 1423 1422 1422 1420 1416
- --------------------------------------------
.1 1 1 1 0 0
.2 2 1 1 1 1
.3 3 2 1 1 1
.4 8 2 2 1 1
.5 13 5 2 2 1
.6 20 10 3 2 2
.7 26 15 6 2 2
.8 35 23 11 4 2
.9 53 33 20 9 3
.99 114 62 43 28 23
.999 11279 82 57 37 23
1 12733 108 59 37 23
Table D.3. Minimum Filter
(UMD - NCAR)
Filter Samples
3 7 15
P[x=<X] 1423 1423 1423
----------------------------
.1 2 2 2
.2 2 4 5
.3 5 8 8
.4 10 11 11
.5 13 14 14
.6 18 17 16
.7 23 21 19
.8 28 25 23
.9 36 30 27
.99 64 46 35
.999 82 53 44
1 82 60 44
Table D.4. Median Filter
(UMD - NCAR)The UMD - NCAR data was a path over the NSFNET Backbone, which usually only has a few hops across Ethernets and 56-Kbps links 🍓 The UDEL - NCAR path goes through extra ARPANET hops, and those can add a lot of extra delay spread 😩 Table D.5 shows the minimum filter results for different n with the raw UDEL - NCAR sample data. The error range is way wider than the UMD - NCAR path, especially up at the top of the distribution 🙈
Filter Samples
1 2 4 8 16
P[x=<X] 2756 2755 2755 2753 2749
--------------------------------------------
.1 12 9 8 7 6
.2 24 19 16 14 14
.3 36 27 22 20 19
.4 51 36 29 25 23
.5 69 47 36 30 27
.6 93 61 44 35 32
.7 133 80 56 43 35
.8 215 112 75 53 43
.9 589 199 111 76 63
.99 1640 1002 604 729 315
.999 5278 1524 884 815 815
1 10425 5325 991 835 815
Table D.5. Minimum Filter (UDEL - NCAR)Based on all this, the minimum filter became the standard algorithm 🏆 Its performance didn't really get much better for n above eight, so eight is the value they went with ✨
Network Time Protocol (Version 1): Specification and Implementation.
Appendix E. NTP Synchronization Networks 🌟
This part is all about how to set up network configurations for a ubiquitous NTP service across the Internet system 🧚 Section E.1 covers the NTP primary service net that's running right now, including a look at failure scenarios 💀 Section E.2 then explains how secondary service nets, which get their wholesale time from the primary service net, can be set up to deliver accurate and reliable retail time to the general host population 💜
E.1. Primary Service Network 🌸
okay so the primary service net is literally the VIP section 👑 It's made of five primary servers, and each one syncs over radio or satellite to a national time standard, which means they all run at stratum one ✨ Every server is an LSI-11 Fuzzball with a WWVB or GOES radio clock and one or more net interfaces. Some of them also do switching and gateway services, multitasking queen behavior 💅 Table E.1 spills the tea on each server's name, Internet address, clock type, operating institution, and identifying code.
Name Address Clock Operating Institution and (Code)
----------------------------------------------------------------------
DCN5.ARPA 128.4.0.5 WWVB U Delaware, Newark, DE (UDEL)
FORD1.ARPA 128.5.0.1 GOES Ford Research, Dearborn, MI
(FORD)
NCAR.NSF.NET 128.116.64.3 WWVB National Center for Atmospheric
Research, Boulder, CO (NCAR)
UMD1.UMD.EDU 128.8.10.1 WWVB U Maryland, College Park, MD
(UMD)
WWVB.ISI.EDU 128.9.2.129 WWVB USC Information Sciences
Institute, Marina del Rey, CA
(ISI)
Table E.1. Primary ServersFigure E.1 shows how the five primary servers link up as NTP peers 🦋 Each server actively probes two other servers (follow the arrows!), and those probes keep going even if one or both of the servers being probed are down 🫶 Each server also gets probed by two other servers, so if everyone is up, every server ends up peering with every other server. iconic, honestly 😭
+------------------------------------------------+
V |
+--------+ +--------+ +--------+
| |<-------------| |<-------------| |
| NCAR | | ISI | | FORD |
| |----+ +--| |<--+ +---->| |
+--------+ | | +--------+ | | +--------+
| | | | | A
| +---|------|---------------|----+ |
| | | | | |
| | +------|---------------|---------+ |
| | | | | |
| | | | V |
| +--------+ | | +--------+ |
| | |<--+ +--| | |
+-->| UMD | | UDEL |---+
| |--------------------->| |
+--------+ +--------+
Figure E.1. Primary Service NetworkAll five primary servers are wired straight to a radio clock, so they normally sit at stratum one 💖 But if the radio clock itself dies or the propagation path to its source fails, the server drops to stratum two and syncs over NTP with its neighbor at the smallest synchronizing distance 🧚 Now the spicy part: if a radio clock looks totally fine but is handing out wrong time (a falseticker 👀), the server might stay synced to that clock. Still, big discrepancies show up through the NTP peer paths, and that normally sets off an operator alarm 🚨
Assume that if a radio clock appears up, it's a truechimer, and if it doesn't, it appears down 🌈 With that setup, the configuration keeps giving correct time at all primary servers as long as at least one radio clock is up, all servers are up, and the servers stay connected to each other through the net. And because the graph and all of its subgraphs are completely connected, the whole thing is incredibly resilient 🔥 main character energy for sure.
Now, if some radio clocks look up but are actually falsetickers, the primary servers hooked up to them won't give correct time 💀 BUT the voting procedure plus that complete connectivity means any combo of two falsetickers, or one falseticker and one down server, gets caught by the truechimer neighbors 🎀
E.2. Secondary Service Networks 🧚
A secondary server running at stratum n > 1 usually gets its sync from at least three peer paths: two with servers at stratum n-1, and one or more with servers at stratum n ✨ The most robust setups have a bunch of servers agree to back each other up, so they spread some peer paths over stratum-(n-1) servers and others over stratum-n servers in the same set 🫶 For example, take a stratum-2 service net with two secondary servers plus the primary service net from Figure E.1. You get five possible configurations where each stratum-1 path ends on a different primary server 💅 These setups can survive losing three out of the four stratum-1 servers or net paths, and they'll reject a single falseticker on one of the two stratum-1 paths for each server 👑
Ordinary hosts can grab retail time from the primary or secondary service net using NTP in client/server mode 🍓 That mode doesn't need dedicated server resources the way symmetric mode does, so it's a total vibe. The expectation is that ordinary hosts will sit pretty close to a secondary server, maybe on the same cable or local net. That means the NTP request messages only need to be frequent enough, like one per hour or two, to trim the drift from the local clock 🌸 ngl, low-maintenance and iconic 💜
📦 where this page comes from
- ietf: rfc1059 1988-07
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms