1. Introduction This document is a reference and implementation guide for the Network Time Protocol Version 4 (NTPv4), which is widely used to synchronize the system clocks among a set of distributed time servers and clients. This document defines the core architecture, protocol, state machines, data structures and algorithms. It is intended primarily for developers and not as a formal standard. This and related documents collectively replace the Network Time Protocol Version 3 (NTPv3) specification RFC 1305 [6] and previous versions of that specification. The core protocol continues to be compatible with all prior versions except the original (unnumbered) version of the protocol. While certain minor changes have been made in some protocol header fields, these do not affect the interoperability between NTPv4 and previous versions. The NTP subnet model includes a number of widely accessible primary time servers synchronized by wire or radio to national standards. The purpose of the NTP protocol is to convey timekeeping information from these primary servers to secondary time servers and clients via both private networks and the public Internet. Crafted algorithms mitigate errors that may result from network disruptions, server failures and possible hostile action. Servers and clients are configured as a forest where time values flow from the primary servers at the root via branching secondary servers toward clients at the leaves of the forest. The NTPv4 reference implementation available at www.ntp.org is consistent with the model described in this document. However, neither this implementation nor this document is intended as a definitive formal standard. Formal standards documents consistent with IETF requirements are in process at the time of writing. When a conflict is found between this document and the formal standards documents, the latter prevail. The NTPv4 design overcomes significant shortcomings in the NTPv3 design, corrects certain bugs and incorporates new features. In particular, the reference implementation uses floating double data types throughout, except for the first-order timestamp differences required to calculate offset and delay. The time resolution is better than one nanosecond and frequency resolution better than one nanosecond per second. Additional improvements include a new clock discipline algorithm which is more responsive to system clock hardware frequency fluctuations. Typical primary servers using modern machines are precise within a few tens of microseconds. Typical secondary servers and clients on fast LANs are within a few hundred microseconds with poll intervals up to 1024 seconds, which was the maximum with NTPv3. With NTPv4, servers and clients are within a few tens of milliseconds with poll intervals up to 36 hours. The main body of this document describes only the core protocol and data structures necessary to interoperate between conforming implementations. Additional detail is provided in the form of a skeleton program included as an appendix. This program includes data structures and code segments for the core algorithms and in addition the mitigation algorithms used to enhance reliability and accuracy. While the skeleton and other descriptions in this document apply to a particular implementation, they are not intended as the only way the required functions can be implemented. While the NTPv3 symmetric key authentication scheme described in this document carries over from NTPv3, the Autokey public key authentication scheme new to NTPv4 is described in [3]. The NTP protocol includes the modes of operation described in Section 2 using the data types described in Section 5 and the data structures in Section 6. The implementation model described in Section 4 is based on a multiple-process, threaded architecture, although other architectures could be used as well. The on-wire protocol described in Section 7 is based on a returnable-time design which depends only on measured clock offsets, but does not require reliable message delivery. The synchronization subnet is a self-organizing, hierarchical, master-slave network with synchronization paths determined by a shortest-path spanning tree and defined metric. While multiple masters (primary servers) may exist, there is no requirement for an election protocol. This remaining sections of this document define the data structures and algorithms suitable for a fully featured NTPv4 implementation. Details specific to NTP packet formats commonly used with the User Datagram Protocol (UDP) are presented in Appendix A. Appendix B contains the code skeleton with definitions, structures and code segments that represent the basic structure of the reference implementation. 2. Modes of Operation An NTP implementation operates as a primary server, secondary server or client. A primary server is synchronized directly to a reference clock, such as a GPS receiver or telephone modem service. A client is synchronized to one or more upstream servers, but does not provide synchronization to dependent clients. A secondary server has one or more upstream servers and one or more downstream servers or clients. All servers and clients claiming full NTPv4 compliance must implement the entire suite of algorithms described in this document. In order to maintain stability in large NTP subnets, secondary servers must be fully NTPv4 compliant. Primary servers and clients complying with a subset of NTP, called the Simple Network Time Protocol (SNTPv4) [4], do not need to implement all algorithms. SNTP is intended for primary servers equipped with a single reference clock, as well as clients with a single upstream server and no dependent clients. The fully developed NTPv4 implementation is intended for secondary servers with multiple upstream servers and multiple downstream servers or clients. Other than these considerations, NTP and SNTP servers and clients are completely interoperable and can be mixed and matched in NTP subnest. Servers retain no state after returning the response to a client packet; clients retain state in the form of a data structure called an association. Persistent associations are mobilized when the service starts and are never demobilized. Ephemeral associations are mobilized during operation, such as upon the arrival of a broadcast packet, and demobilized by timeout or error. Preemptable associations are mobilized when or after the service starts and demobilized when deemed no longer useful for synchronization. The code skeleton and reference implementation summarized in Appendix B includes suitable algorithms for ephemeral and preemptable associations, but they are not discussed in the main body of this document. There are three NTP protocol variants, symmetric, client/server and broadcast. Each is associated with an association mode as shown in Table 1. In the client/server variant a client association sends mode-3 (client) packets to a server, which returns mode-4 (server) packets. Servers provide synchronization to one or more clients, but do not accept synchronization from them. A server can also be a reference clock which obtains time directly from a standard source such as a GPS receiver or telephone modem service. We say that clients pull synchronization from servers. In the symmetric variant a peer operates as both a server and client using either a symmetric- active or symmetric-passive association. A symmetric-active association sends mode-1 (symmetric-active) packets to a symmetric-active peer association. Alternatively, a symmetric- passive association can be mobilized upon arrival of a mode-1 packet. That association sends mode-2 (symmetric-passive) packets and persists until error or timeout. We say that peers both push and pull synchronization to and from each other. For the purposes of this document, a peer operates like a client, so a reference to client implies peer as well. In the broadcast variant a broadcast server association sends periodic mode-5 (broadcast) packets which are received by multiple mode-6 (broadcast client) associations. It is useful to provide an initial volley where the client operating in mode 3 exchanges several packets with the server in order to calibrate the propagation delay and to run the Autokey security protocol, after which the client reverts to mode 6. We say that broadcast servers push synchronization to willing consumers. Following conventions established by the telephone industry, the level of each server in the hierarchy is defined by a number called the stratum, with the primary servers assigned stratum one and the secondary servers at each level assigned one greater than the preceding level. As the stratum increases from one, the accuracies achievable degrade somewhat depending on the particular network path and system clock stability. It is useful to assume that mean errors, and thus a metric called the synchronization distance, increase approximately in proportion to the stratum and measured roundtrip delay. Drawing from the experience of the telephone industry, which learned such lessons at considerable cost, the subnet topology should be organized to produce the lowest synchronization distances, but must never be allowed to form a loop. In NTP the subnet topology is determined using a variant of the Bellman-Ford distributed routing algorithm, which computes the shortest-distance spanning tree rooted on the primary servers. As a result of this design, the algorithm automatically reorganizes the subnet to produce the most accurate and reliable time, even when one or more primary or secondary servers or the network paths between them fail. 3. Definitions A number of terms used throughout this document have a precise technical definition. A timescale is a frame of reference where time is expressed as the value of a monotonic-increasing binary counter with an indefinite number of bits. It counts in seconds and fraction with the decimal point somewhere in the middle. The Coordinated Universal Time (UTC) timescale represents mean solar time as disseminated by national standards laboratories. The system time is represented by the system clock maintained by the operating system kernel. The goal of the NTP algorithms is to minimize both the time difference and frequency difference between UTC and the system clock. When these differences have been reduced below nominal tolerances, the system clock is said to be synchronized to UTC. The date of an event is the UTC time at which it takes place. Dates are ephemeral values which always increase in step with reality and are designated with upper case T in this document. It is convenient to define another timescale coincident with the running time of the NTP program that provides the synchronization function. This is convenient in order to determine intervals for the various repetitive functions like poll events. Running time is usually designated with lower case t. A timestamp T(t) represents either the UTC date or time offset from UTC at running time t. Which meaning is intended should be clear from context. Let T(t) be the time offset, R(t) the frequency offset, D(t) the ageing rate (first derivative of R(t) with respect to t). Then, if T(t0) is the UTC time offset determined at t = t0, the UTC time offset after some interval t is (1), where e is a stochastic error term discussed later in this document. While the D(t) term is important when characterizing precision oscillators, it is ordinary neglected for computer oscillators. In this document all time values are in seconds (s) and all frequency values in seconds-per- second (s/s). It is sometimes convenient to express frequency offsets in parts-per- million (PPM), where 1 PPM is equal to 1e-6 s/s. It is important in computer timekeeping applications to assess the performance of the timekeeping function. The NTP performance model includes four statistics which are updated each time a client makes a measurement with a server. The offset q represents the maximum- likelihood time offset of the server clock relative to the system clock. The delay d represents the roundtrip delay between the client and server. The dispersion e represents the maximum error inherent in the measurement. It increases at a rate equal to the maximum disciplined system clock frequency tolerance F, typically 15 PPM. The jitter j, defined as the root-mean-square (RMS) average of the most recent time offset differences, represents the nominal error in estimating q. While the q, d, e, and j statistics represent measurements of the system clock relative to the each server clock separately, the NTP protocol includes mechanisms to combine the statistics of several servers to more accurately discipline and calibrate the system clock. The system offset Q represents the maximum-likelihood offset estimate for the server population. The system jitter J represents the nominal error in estimating Q. The d and e statistics are accumulated at each stratum level from the reference clocks to produce the root delay D and root dispersion E statistics. The synchronization distance represents the maximum error due all causes. The detailed formulations of these statistics are given later in this document. They are available to the dependent applications in order to assess the performance of the synchronization function. 4. Implementation Model Figure 1 shows two processes dedicated to each server, a peer process to receive messages from the server or reference clock and a poll process to transmit messages to the server or reference clock. These processes operate on a common data structure called an association, which contains the statistics described above along with various other data described later. A client sends an NTP packet to one or more servers and processes the replies as received. The server interchanges addresses and ports, overwrites certain fields in the packet and returns it immediately (client/ server mode) or at some time later (symmetric modes). As each NTP message is received, the offset q between the peer clock and the system clock is computed along with the associated statistics d, e and j. The system process includes the selection, clustering and combining algorithms which mitigate among the various servers and reference clocks to determine the most accurate and reliable candidates to synchronize the system clock. The selection algorithm uses Byzantine principles to cull the falsetickers from the incident population leaving the truechimers as result. The clustering algorithm uses statistical principles to sift the most accurate truechimers leaving the survivors as result. The combining algorithm develops the final clock offset as a statistical average of the survivors. The clock discipline process, which is actually part of the system process, includes engineered algorithms to control the time and frequency of the system clock, here represented as a variable frequency oscillator (VFO). Timestamps struck from the VFO close the feedback loop which maintains the system clock time. Associated with the clock discipline process is the clock adjust process, which runs once each second to inject a computed time offset and maintain constant frequency. The RMS average of past time offset differences represents the nominal error or system jitter J. The RMS average of past frequency offset differences represents the oscillator frequency stability or frequency wander Y. A client sends messages to each server with a poll interval of 2t seconds, as determined by the poll exponent t. In NTPv4 t ranges from 4 (16 s) through 17 (36 h). The value of t is determined by the clock discipline algorithm to match the loop time constant . A server responds with messages at an update interval of m seconds. For stateless servers, , since the server responds immediately. However, in symmetric modes each of two peers manages the time constant as a function of current system offset and system jitter, so may not agree with the same t. It is important that the dynamic behavior of the clock discipline algorithms be carefully controlled in order to maintain stability in the NTP subnet at large. This requires that the peers agree on a common t equal to the minimum poll exponent of both peers. The NTP protocol includes provisions to properly negotiate this value. While not shown in the figure, the implementation model includes some means to set and adjust the system clock. The operating system is assumed to provide two functions, one to set the time directly, for example the Unix settimeofday() function, and another to adjust the time in small increments advancing or retarding the time by a designated amount, for example the Unix adjtime() function. In the intended design the clock discipline process uses the adjtime() function if the adjustment is less than a designated threshold, and the settimeofday() function if above the threshold. The manner in which this is done and the value of the threshold is described later. 5. Data Types All NTP time values are represented in twos-complement format, with bits numbered in big- endian fashion from zero starting at the left, or high-order, position. There are three NTP time formats, a 128-bit date format, a 64-bit timestamp format and a 32-bit short format, as shown in Figure 2. The 128-bit date format is used where sufficient storage and word size are available. It includes a 64-bit signed seconds field spanning 584 billion years and a 64-bit fraction field resolving .05 attosecond. For convenience in mapping between formats, the seconds field is divided into a 32-bit era field and a 32-bit timestamp field. Eras cannot be produced by NTP directly, nor is there need to do so. When necessary, they can be derived from external means, such as the filesystem or dedicated hardware. The 64-bit timestamp format is used in packet headers and other places with limited word size. It includes a 32-bit unsigned seconds field spanning 136 years and a 32 bit fraction field resolving 232 picoseconds. The 32-bit short format is used in delay and dispersion header fields where the full resolution and range of the other formats are not justified. It includes a 16-bit unsigned seconds field and a 16-bit fraction field. In the date format the prime epoch, or base date of era 0, is 0 h 1 January 1900 UTC, when all bits are zero. Dates are relative to the prime epoch; values greater than zero represent times after that date; values less than zero represent times before it. Timestamps are unsigned values and operations on them produce a result in the same or adjacent eras. Era 0 includes dates from the prime epoch to some time in 2036, when the timestamp field wraps around and the base date for era 1 is established. In either format a value of zero is a special case representing unknown or unsynchronized time. Table 2 shows a number of historic NTP dates together with their correspondnig Modified Julian Day (MJD), NTP era and NTP timestamp. Let p be the number of significant bits in the second fraction. The clock resolution is defined , in seconds. In order to minimize bias and help make timestamps unpredictable to an intruder, the nonsignificant bits should be set to an unbiased random bit string. The clock precision is defined as the running time to read the system clock, in seconds. Note that the precision defined in this way can be larger or smaller than the resolution. The term r, representing the precision used in this document, is the larger of the two. The only operation permitted with dates and timestamps is twos-complement subtraction, yielding a 127-bit or 63-bit signed result. It is critical that the first-order differences between two dates preserve the full 128-bit precision and the first-order differences between two timestamps preserve the full 64-bit precision. However, the differences are ordinarily small compared to the seconds span, so they can be converted to floating double format for further processing and without compromising the precision. It is important to note that twos-complement arithmetic does not know the difference between signed and unsigned values; only the conditional branch instructions. Thus, although the distinction is made between signed dates and unsigned timestamps, they are processed the same way. A perceived hazard with 64-bit timestamp calculations spanning an era, such as could happen in 2036, might result in incorrect values. In point of fact, if the client is set within 68 years of the server before the protocol is started, correct values are obtained even if the client and server are in adjacent eras. Further discussion on this issue is on the NTP project page linked from www.ntp.org. Some time values are represented in exponent format, including the precision, time constant and poll interval values. These are in 8-bit signed integer format in log2 (log to the base 2) seconds. The only operations permitted on them are increment and decrement. For the purpose of this document and to simplify the presentation, a reference to one of these state variables by name means the exponentiated value, e.g., the poll interval is 1024 s, while reference by name and exponent means the actual value, e.g., the poll exponent is 10. To convert system time in any format to NTP date and timestamp formats requires that the number of seconds s from the prime epoch to the system time be determined. The era is the integer quotient and the timestamp the integer remainder as in (2) and , which works for positive and negative dates. To convert from NTP era and timestamp to system time requires the calculation (3) to determine the number of seconds since the prime epoch. Converting between NTP and system time can be a little messy, but beyond the scope of this document. Note that the number of days in era 0 is one more than the number of days in most other eras and this won't happen again until the year 2400 in era 3. In the description of state variables to follow, explicit reference to integer type implies a 32-bit unsigned integer. This simplifies bounds checks, since only the upper limit needs to be defined. Without explicit reference, the default type is 64-bit floating double. Exceptions will be noted as necessary. 6. Data Structures The NTP protocol state machines described in following sections are defined using state variables and flow chart fragments. State variables are separated into classes according to their function in packet headers, peer and poll processes, the system process and the clock discipline process. Packet variables represent the NTP header values in transmitted and received packets. Peer and poll variables represent the contents of the association for each server separately. System variables represent the state of the server as seen by its dependent clients. Clock discipline variables represent the internal workings of the clock discipline algorithm. Additional constant and variable classes are defined in Appendix B. 6.1 Structure Conventions In the text and diagrams to follow, state variables are rendered in fixed-width font, while equation variables are rendered in italic or Greek font. Ordinary text and named routines are rendered in native font. In order to distinguish between different variables of the same name but used in different processes, the following Unix-like structure member naming convention is adopted. Table 3 summarizes the naming conventions in this and subsequent figures and tables in this document. A receive packet variable v is a member of the packet structure r with fully qualified name r.v. In a similar manner x.v is a transmit packet variable, p.v is a peer variable, s.v is a system variable and c.v is a clock discipline variable. There is a set of peer variables for each association; there is only one set of system and clock variables. Most flow chart fragments begin with a statement label and end with a named go-to or exit. A subroutine call includes a dummy () following the name and return at the end.to the point following the call. 6.2 Global Parameters In addition to the variable classes a number of global parameters are defined in this document, including those shown with values in Table 4. While these are the only parameters needed in this document, a larger collection is necessary in the skeleton and larger still for the reference implementation. Section B.1 contains those used by the skeleton for the mitigation algorithms, clock discipline algorithm and related implementation-dependent functions. Some of these parameter values are cast in stone, like the NTP port number assigned by the IANA and the version number assigned NTPv4 itself. Others like the frequency tolerance, involve an assumption about the worst case behavior of a system clock once synchronized and then allowed to drift when its sources have become unreachable. The minimum and maximum parameters define the limits of state variables as described in later sections. While shown with fixed values in this document, some implementations may make them variables adjustable by configuration commands. For instance, the reference implementation computes the value of PRECISION as log2 of the minimum time in several iterations to read the system clock. 6.3 Packet Header Variables The most important state variables from an external point of view are the packet header variables described below. The NTP packet header follows the UDP and IP headers and the physical header specific to the underlying transport network. It consists of a number of 32-bit (4-octet) words, although some fields use multiple words and others are packed in smaller fields within a word. The NTP packet header shown in Appendix A has 12 words followed by optional extension fields and finally an optional message authentication code (MAC) consisting of the key identifier and message digest fields. The optional extension fields described in Appendix A are used by the Autokey security protocol [3], which is not described here. The MAC is used by both Autokey and the symmetric key authentication scheme described in Appendix A. As is the convention in other Internet protocols, all fields are in network byte order, commonly called big-endian. A list of the packet header variables is shown in Table 5 and described in detail below. The packet header fields apply to both transmitted (x prefix) and received packets (r prefix). The variables are interpreted as follows: leap 2-bit integer warning of an impending leap second to be inserted or deleted in the last minute of the current month, coded as follows: 0 no warning 1 last minute of the day has 61 seconds 2 last minute of the day has 59 seconds 3 alarm condition (the clock has never been synchronized) version. 3-bit integer representing the NTP version number, currently 4. mode 3-bit integer representing the mode, with values defined as follows: 0 reserved 1 symmetric active 2 symmetric passive 3 client 4 server 5 broadcast 6 NTP control message 7 reserved for private use stratum 8-bit integer representing the stratum, with values defined as follows: 0 unspecified or invalid 1 primary server (e.g., equipped with a GPS receiver) 2-255 secondary server (via NTP) It is customary to map the stratum value 0 in received packets to MAXSTRAT (16) in the peer variable p.stratum and to map p.stratum values of MAXSTRAT or greater to 0 in transmitted packets. This allows reference clocks, which normally appear at stratum 0, to be conveniently mitigated using the same algorithms used for external sources. poll 8-bit signed integer representing the maximum interval between successive messages, in log2 seconds. In the reference implementation the limits are set by MINPOLL (4) and MAXPOLL (17), but the default limits are 6 and 10, respectively. precision 8-bit signed integer representing the precision of the system clock, in log2 seconds. For instance a value of -18 corresponds to a precision of about one microsecond. The precision is normally determined when the service first starts up as the minimum time of several iterations to read the system clock. rootdelay Total roundtrip delay to the reference clock, in NTP short format. rootdisp Total dispersion to the reference clock, in NTP short format. refid 32-bit code identifying the particular server or reference clock. The interpretation depends on the value in the stratum field. For packet stratum 0 (unspecified or invalid) this is a four-character ASCII string, called the kiss code, used for debugging and monitoring purposes. For stratum 1 (reference clock) this is a four-octet, left-justified, zero-padded ASCII string assigned to the radio clock. While not specifically enumerated in this document, the following have been used as ASCII identifiers: GOES Geosynchronous Orbit Environment Satellite GPS Global Position System PPS Generic pulse-per-second IRIG Inter-Range Instrumentation Group WWVB LF Radio WWVB Ft. Collins, CO 60 kHz DCF77 LF Radio DCF77 Mainflingen, DE 77.5 kHz HBG LF Radio HBG Prangins, HB 75 kHz MSF LF Radio MSF Rugby, UK 60 kHz JJY LF Radio JJY Fukushima, JP 40 kHz, Saga, JP 60 kHz LORC MF Radio LORAN C 100 kHz TDF MF Radio Allouis, FR 162 kHz CHU HF Radio CHU Ottawa, Ontario WWV HF Radio WWV Ft. Collins, CO WWVH HF Radio WWVH Kaui, HI NIST NIST telephone modem USNO USNO telephone modem PTB etc. European telephone modem Above stratum 1 (secondary servers and clients) this is the reference identifier of the server. If using the IPv4 address family, the identifier is the four-octet IPv4 address. If using the IPv6 address family, it is the first four octets of the MD5 hash of the IPv6 address. reftime Time when the system clock was last set or corrected, in NTP timestamp format. org Time at the client when the request departed for the server, in NTP timestamp format. rec Time at the server when the request arrived from the client, in NTP timestamp format. xmt Time at the server when the response left for the client, in NTP timestamp format. dst Time at the client when the reply arrived from the server, in NTP timestamp format. Note: This value is not included in a header field; it is determined upon arrival of the packet and made avaiable in the packet buffer data structure. keyid 32-bit unsigned integer used by the client and server to designate a secret 128-bit MD5 key. Together, the keyid and digest fields collectively are called message authentication code (MAC). digest 128-bit bitstring computed by the keyed MD5 message digest algorithm described in Appendix A. 7. On-Wire Protocol The NTP on-wire protocol is the core mechanism to exchange time values between servers, peers and clients. It is inherently resistant to lost or duplicate data packets. Data integrity is provided by the IP and UDP checksums. No flow-control or retransmission facilities are provided or necessary. The protocol uses timestamps, either extracted from packet headers or struck from the system clock upon the arrival or departure of a packet. Timestamps are precision data and should be restruck in case of link level retransmission and corrected for the time to compute a MAC on transmit. The on-wire protocol uses four timestamps numbered T1 through T4 and three state variables org, rec and xmt, as shown in Figure 3. This figure shows the most general case where each of two peers, A and B, independently measure the offset and delay relative to the other. For purposes of illustration the individual timestamp values are shown in lower case with subscripts indicating the order of transmission and reception. In the figure the first packet transmitted by A containing only the transmit timestamp T3 with value t1. B receives the packet at t2 and saves the origin timestamp T1 with value t1 in state variable org and the destination timestamp T4 with value t2 in state variable rec. At this time or some time later B sends a packet to A containing the org and rec state variables in T1 and T2, respectively and in addition the transmit timestamp T3 with value t3, which is saved in the xmt state variable. When this packet arrives at A the packet header variables T1, T2, T3 and destination timestamp T4 represent the four timestamps necessary to compute the offset and delay of B relative to A, as described later. Before the A state variables are updated, two sanity checks are performed in order to protect against duplicate or bogus packets. A packet is a duplicate if the transmit timestamp T3 in the packet matches the xmt state variable. A packet is bogus if the origin timestamp T1 in the packet does not match the org state variable. In either of these cases the state variables are updated, but the packet is discarded. The four most recent timestamps, T1 through T4, are used to compute the offset of B relative to A (4) and the roundtrip delay (5). Note that the quantities within parentheses are computed from 64-bit unsigned timestamps and result in signed values with 63 significant bits plus sign. These values can represent dates from 68 years in the past to 68 years in the future. However, the offset and delay are computed as the sum and difference of these values, which contain 62 significant bits and two sign bits, so can represent unambiguous values from 34 years in the past to 34 years in the future. In other words, the time of the client must be set within 34 years of the server before the service is started. This is a fundamental limitation with 64-bit integer arithmetic. In implementations where floating double arithmetic is available, the first-order differences can be converted to floating double and the second-order sums and differences computed in that arithmetic. Since the second-order terms are typically very small relative to the timestamps themselves, there is no loss in significance, yet the unambiguous range is increased from 34 years to 68 years. Additional considerations on these issues, as well as the behavior when moving beyond the prime era, are discussed in online white papers at www.ntp.org but beyond the scope of this document. In some scenarios where the frequency offset between the client and server is relatively large and the actual propagation time small, it is possible that the delay computation becomes negative. For instance, if the frequency difference is 100 PPM and the interval T4 - T1 is 64 s, the apparent delay is -6.4 ms. Since negative values are misleading in subsequent computations, the value of d should be clamped not less than the system precision s.precision r defined below. The discussion above assumes the most general case where two symmetric peers independently measure the offsets and delays between them. In the case of a stateless server, the protocol can be simplified. A stateless server copies T3 and T4 from the client packet to T1 and T2 of the server packet and tacks on the transmit timestamp T3 before sending it to the client. Additional details for filling in the remaining protocol fields are given in the next section and in Appendix B. A SNTP primary server implementing the on-wire protocol has no upstream servers except a single reference clock In principle, it is indistinguishable from an NTP primary server which has the mitigation algorithms, presumably to mitigate between multiple reference clocks. Upon receiving a client request, a SNTP primary server constructs and sends the reply packet as shown in Figure 5 below. Note that the dispersion field in the packet header must be calculated in the same way as in the NTP case. A SNTP client using the on-wire protocol has a single server and no downstream clients. It can operate with any subset of the NTP on-wire protocol, the simplest using only the transmit timestamp of the server packet and ignoring all other fields. However, the additional complexity to implement the full on-wire protocol is minimal and is encouraged. 8. Peer Process The peer process is called upon arrival of a server packet. It runs the on-wire protocol to determine the clock offset and roundtrip delay and in addition computes statistics used by the system and poll processes. Peer variables are instantiated in the association data structure when the structure is initialized and updated by arriving packets. There is a peer process, poll process and association for each server. The discussion in this section covers only the variables and routines necessary for a conforming NTPv4 implementation. Additional implementation details are in Section B.5. The engineering principles and measured performance with the reference implementation are discussed in [2]. 8.1 Peer Process Variables Table 6 summarizes the common names, formula names and a short description of each peer variable, all of which have prefix p. The following configuration variables are normally initialized when the association is mobilized, either from a configuration file or upon arrival of the first packet for an ephemeral association. p.srcadr IP address of the remote server or reference clock. In the reference implementation reference clock addresses are by convention in IPv4 format with prefix 127.127.t.u, where t is the device driver number and u the instantiation number. This becomes the destination IP address in packets sent from this association. p.srcport UDP port number of the server or reference clock. This becomes the destination port number in packets sent from this association. When operating in symmetric modes (1 and 2) this field must contain the NTP port number PORT (123) assigned by the IANA. In other modes it can contain any number consistent with local policy. p.dstadr IP address of the client. This becomes the source IP address in packets sent from this association. p.dstport UDP port number of the client, ordinarily the NTP port number PORT (123) assigned by the IANA. This becomes the source port number in packets sent from this association. p.keyid Symmetric key ID for the 128-bit MD5 key used to generate and verify the MAC. The client and server or peer can use different values, but they must map to the same key. The variables defined below are updated from the packet header as each packet arrives. They are interpreted in the same way as the as the packet variables of the same names. p.leap, p.version, p.mode, p.stratum, p.ppoll, p.rootdelay, p.rootdisp, p.refid, p.reftime It is convenient for later processing to convert the NTP short format packet values p.rootdelay and p.rootdisp to floating doubles as peer variables. The p.org, p.rec, p.xmt variables represent the timestamps computed by the on-wire protocol described previously. The p.offset, p.delay, p.disp, p.jitter variables represent the current time values and statistics produced by the clock filter algorithm. The offset and delay are computed by the on-wire protocol; the dispersion and jitter are calculated as described below. Strictly speaking, the epoch p.t is not a timestamp; it records the system timer upon arrival of the latest packet selected by the clock filter algorithm. 8.2 Peer Process Operations Figure 4 shows the peer process code flow upon the arrival of a packet. Additional details specific to the reference implementation are shown in the receive() and access() routines in Section B.5. There is no specific method required for access control, although it is recommended that implementations include a match-and-mask scheme similar to many others now in widespread use, as well as in the reference implementation. Format checks require correct field length and alignment, acceptable version number (1-4) and correct extension field syntax, if present. There is no specific requirement for authentication; however, if authentication is implemented, the symmetric key scheme described in Appendix A must be included among the supported. This scheme uses the MD5 keyed hash algorithm Section B.2. For the most vulnerable applications the Autokey public key scheme described in [3] and supported by the reference implementation in is recommended. Next, the association table is searched for matching source address and source port using the find_assoc() routine in Section B.5. The dispatch table near the beginning of that section is indexed by the packet mode and association mode (0 if no matching association) to determine the dispatch code and thus the case target. The significant cases are FXMT, NEWPS and NEWBC. FXMIT. This is a client (mode 3) packet matching no association. The server constructs a server (mode 4) packet and returns it to the client without retaining state. The server packet is constructed as in Figure 5 and the fast_xmit() routine in Section B.5. If the s.rootdelay and s.rootdisp system variables are stored in floating double, they must be converted to NTP short format first. Note that, if authentication fails, the server returns a special message called a crypto-NAK. This message includes the normal NTP header data shown in the figure, but with a MAC consisting of four octets of zeros. The client is free to accept or reject the data in the message. NEWBC. This is a broadcast (mode 5) packet matching no association. The client mobilizes a client (mode 3) association as shown in the mobilize() and clear() routines in Section B.2. The reference implementation first performs the necessary steps to run the Autokey protocol and determine the propagation delay, then continues in listen-only (mode 6) to receive further packets. Note the distinction between a mode-6 packet, which is reserved for the NTP monitor and control functions, and a mode-6 association. NEWPS. This is a symmetric active (1) packet matching no association. The client mobilizes a symmetric passive (mode 2) association as shown in the mobilize() and clear() routines in Section B.2. Code flow continues to the match_assoc fragment described below. In other cases the packet matches an existing association and code flows to the match_assoc fragment in Figure 6. The packet timestamps are carefully checked to avoid invalid, duplicate or bogus packets, as shown in the figure. Note that a crypto-NAK is considered valid only if it survives these tests. Next, the peer variables are copied from the packet header variables as shown in Figure 7 and the packet() routine in Section B.5. The reference implementation includes a number of data range checks shown in Table 7 and discards the packet if the ranges are exceeded; however, the header fields are copied even if errors occur, since they are necessary in symmetric modes to construct the subsequent poll message. The 8-bit p.reach shift register in the poll process described later is used to determine whether the server is reachable or not and provide information useful to insure the server is reachable and the data are fresh. The register is shifted left by one bit when a packet is sent and the rightmost bit is set to zero. As valid packets arrive, the rightmost bit is set to one. If the register contains any nonzero bits, the server is considered reachable; otherwise, it is unreachable. Since the peer poll interval might have changed since the last packet, the poll_update() routine in Section B.8 is called to redetermine the host poll interval. The on-wire protocol calculates the clock offset q and roundtrip delay d from the four most recent timestamps as shown in Figure 3. While it is in principle possible to do all calculations except the first-order timestamp differences in fixed-point arithmetic, it is much easier to convert the first-order differences to floating doubles and do the remaining calculations in that arithmetic,. and this will be assumed in the following description. The dispersion statistic e(t) represents the maximum error due to the frequency tolerance and time since the last measurement. It is initialized (6) when the measurement is made at t0. Here rR is the peer precision in the packet header r.precision and r the system precision s.precision, both expressed in seconds. These terms are necessary to account for the uncertainty in reading the system clock in both the server and the client. The dispersion then grows at constant rate TOLERANCE (F); in other words, at time t, . With the default value F = 15 PPM, this amounts to about 1.3 s per day. With this understanding, the argument t will be dropped and the dispersion represented simply as e. The remaining statistics are computed by the clock filter algorithm described in the next section. 8.3 Clock Filter Algorithm The clock filter algorithm grooms the stream of on-wire data to select the samples most likely to represent the correct time. The algorithm produces the p.offset q, p.delay d, p.dispersion e, p.jitter j, and time of arrival p.t t used by the mitigation algorithms to determine the best and final offset used to discipline the system clock. They are also used to determine the server health and whether it is suitable for synchronization. The core processing steps of this algorithm are shown in Figure 8 with more detail in the clock_filter() routine in Section B.5. The clock filter algorithm saves the most recent sample tuples (q, d, e, t) in an 8-stage shift register in the order that packets arrive. Here t is the system timer, not the peer variable of the same name. The following scheme is used to insure sufficient samples are in the register and that old stale data are discarded. Initially, the tuples of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, t). As valid packets arrive, the (q, d, e, t) tuples are shifted into the register causing old samples to be discarded, so eventually only valid samples remain. If the three low order bits of the reach register are zero, indicating three poll intervals have expired with no valid packets received, the poll process calls the clock filter algorithm with the dummy tuple just as if the tuple had arrived from the network. If this persists for eight poll intervals, the register returns to the initial condition. In the next step the shift register stages are copied to a temporary list and the list sorted by increasing d. Let j index the stages starting with the lowest d. If the sample epoch t0 is not later than the last valid sample epoch p.t, the routine exits without affecting the current peer variables. Otherwise, let ej be the dispersion of the jth entry, then (7) is the peer dispersion p.disp. Note the overload of e, whether input to the clock filter or output, the meaning should be clear from context. The observer should note (a) if all stages contain the dummy tuple with dispersion MAXDISP, the computed dispersion is a little less than 16 s, (b) each time a valid tuple is shifted into the register, the dispersion drops by a little less than half, depending on the valid tuples dispersion, (c) after the fourth valid packet the dispersion is usually a little less than 1 s, which is the assumed value of the MAXDIST parameter. used by the selection algorithm to determine whether the peer variables are acceptable or not. Let the first stage offset in the sorted list be q0; then, for the other stages in any order, the jitter is the RMS average (8), where n is the number of valid tuples in the register. In order to insure consistency and avoid divide exceptions in other computations, the j is bounded from below by the system precision r expressed in seconds. While not in general considered a major factor in ranking server quality, jitter is a valuable indicator of fundamental timekeeping performance and network congestion state. Of particular importance to the mitigation algorithms is the peer synchronization distance, which is computed from the root delay and root dispersion. The root delay is (9) and the root dispersion is (10). Note that e and therefore increase at rate F. The peer synchronization distance is defined (11) and recalculated as necessary. The l is a component of the root synchronization distance L used by the mitigation algorithms as a metric to evaluate the quality of time available from each server. Note that there is no state variable for l, as it depends on the time since the last update. As a practical matter, a not uncommon hazard in global Internet timekeeping is an occasional isolated offset surge, called a popcorn spike, due to some transient delay phenomenon in the network. The reference implementation uses a popcorn spike suppressor to reduce errors due this cause. It operates by tracking the exponentially averaged jitter and discarding an offset spike that exceeds a threshold equal to some multiple of the average. The spike itself is then used to update the average, so the threshold is self-adaptive. 9. System Process As each new sample (q, d, e, t) is produced by the clock filter algorithm, the sample is processed by the mitigation algorithms consisting of the selection, clustering, combining and clock discipline algorithms in the system process. The selection algorithm scans all associations and casts off the falsetickers, which have demonstrably incorrect time, leaving the truechimers as result. In a series of rounds the clustering algorithm discards the association statistically furthest from the centroid until a minimum number of survivors remain. The combining algorithm produces the best and final offset on a weighted average basis and selects one of the associations as the system peer providing the best statistics for performance evaluation. The final offset is passed to the clock discipline algorithm to steer the system clock to the correct time. The statistics (q, d, e, t) associated with the system peer are used to construct the system variables inherited by dependent servers and clients and made available to other applications running on the same machine. The discussion in following sections covers only the basic variables and routines necessary for a conforming NTPv4 implementation. Additional implementation details are in Section B.6. An interface that might be considered in a formal specification is represented by the function prototypes in Section B.1. The engineering principles and measured performance with the reference implementation are discussed in [2]. 9.1 System Process Variables The variables and parameters associated with the system process are summarized in Table 8, which gives the variable name, formula name and short description. Unless noted otherwisse, all variables have assumed prefix s. All the variables except s.t and s.p have the same format and interpretation as the peer variables of the same name. The remaining variables are defined below. s.t Integer representing the value of the system timer at the last update. s.p System peer association pointer. s.precision 8-bit signed integer representing the precision of the system clock, in log2 seconds.ZA s.offset Offset computed by the combining algorithm. s.jitter Jitter computed by the cluster and combining algorithms. The variables defined below are updated from the system peer process as described later. They are interpreted in the same way as the as the peer variables of the same names. s.leap, s.stratum, s.rootdelay, s.rootdisp, s.refid, s.reftime Initially, all variables are cleared to zero, then the s.leap is set to 3 (unsynchronized) and s.stratum is set to MAXSTRAT (16). The remaining statistics are determined as described below. 9.2 System Process Operations The system process implements the selection, clustering, combining and clock discipline algorithms shown in Figure 1. The clock_select() routine in Figure 9 includes the selection algorithm of Section 9.2.1 that produces a majority clique of truechimers based on agreement principles. The clustering algorithm of Section 9.2.2 discards the outliers of the clique to produce the survivors used by the combining algorithm in Section 9.2.3, which in turn provides the final offset for the clock discipline algorithm in Section 9.2.4. If the selection algorithm cannot produce a majority clique, or if the clustering algorithm cannot produce at least CMIN survivors, the system process terminates with no further processing. If successful, the clustering algorithm selects the statistically best candidate as the system peer and its variables are inherited as the system variables. The selection and clustering algorithms are described below separately, but combined in the code skeleton and reference implementation. 9.2.1 Selection Algorithm The selection algorithm operates to find the truechimers using Byzantine agreement principles originally proposed by Marzullo [1], but modified to improve accuracy. An overview of the algorithm is in Figure 10 and the first half of the clock_select() routine in Section B.6.1. First, those servers which are unusable according to the rules of the protocol are detected and discarded by the accept() routine in Figure 11 and Section B.6.3. Next, a set of tuples {p, type, edge} is generated for the remaining servers, where p is an association pointer, type and edge identifies the upper (+1), middle (0) and lower (-1) endpoint of a correctness interval , where l is the root distance calculated in (11). The tuples are placed on a list and sorted by edge. The list is processed from the lowest to the highest, then from highest to lowest using the algorithm in Figure 10 and in Section B.6.1 and described in detail in [2]. The algorithm starts with the assumption that there are no falsetickers (f = 0) and attempts to find a nonempty intersection interval containing the midpoints of all correct servers, i.e., truechimers. If a nonempty interval cannot be found, it increases the number of assumed falsetickers by one and tries again. If a nonempty interval is found and the number of falsetickers is less than the number of truechimers, a majority clique has been found and the midpoints (offsets) represent the survivors available for the clustering algorithm. Otherwise, there are no suitable candidates to synchronize the system clock. While not shown on the flow chart, l is increased by MINDISP (.005 s) when constructing the tuples. The reason for this is to avoid problems with very fast processors and networks. Occasionally, due to random fluctuations and jitter, two legitimate correctness intervals fail to overlap and may cause both to be declared falseticker. The MINDISP increment acts like a shim to decrease the likelihood this might occur. In the reference implementation MINDISP is a configurable value that can be changed to fit each scenario. 9.2.2 Clustering Algorithm The members of the majority clique are placed on the survivor list, and sorted first by stratum, then by root distance l. The sorted list is processed by the clustering algorithm in Figure 12 and the second half of the clock_select() algorithm in Section B.6.1. It operates in a series of rounds where each round discards the furthest statistical outlier until a specified minimum number of survivors NMIN (3) are left or until no further improvement is possible. In each round let n be the number of survivors and s index the survivor list. Assume jp is the peer jitter of the s survivor. Compute (12) as the selection jitter. Then choose and . If or , no further reduction in selection jitter is possible, so the algorithm terminates and the remaining survivors are processed by the combining algorithm. Otherwise, the algorithm casts off the jmax survivor, reduces n by one and makes another round. 9.2.3 Combining Algorithm The remaining survivors are processed by the clock_combine() routine in Figure 13 and Section B.6.4 to produce the best and final data for the clock discipline algorithm. The routine processes the peer offset q and jitter j to produce the system offset Q and system peer jitter Jp, where each server statistic is weighted by the reciprocal of the root distance. and the result normalized. The system peer jitter Jp is a component of the system jitter described later. The system statistics are passed to the clock_update() routine in Figure 14 and Section B.6.4. If there is only one survivor, the offset passed to the clock discipline algorithm is and the system peer jitter is . Otherwise, the selection jitter Js is computed as in (8), where q0 represents the offset of the system peer and j ranges over the survivors. The first survivor on the survivor list is selected as the system peer, here represented by the statistics (q, d, e, j). By rule, an update is discarded if its time of arrival p.t is not strictly later than the last update used s.t. Let m = p.t - s.t be the time since the last update or update interval. If the update interval is less than or equal to zero, the update is discarded. Otherwise, the system variables are updated from the system peer variables as shown in Figure 14. Note that s.stratum is set to p.stratum plus one. The arrows labelled IGNOR, PANIC, ADJ and STEP refer to return codes from the local_clock() routine described in the next section. IGNORE means the update has been ignored as an outlier. PANIC means the offset is greater than the panic threshold PANICT (1000 s) and normally causes the program to exit with a diagnostic message to the system log. STEP means the offset is less than the panic threshold, but greater than the step threshold STEPT (125 ms). Since this means all peer data have been invalidated, all associations are reset and the client begins as at initial start. ADJ means the offset is less than the step threshold and thus a valid update for the local_clock() routine described later. In this case the system variables are updated as shown in Figure 14. There is one exception not shown. The dispersion increment is bounded from below by MINDISP. In subnets with very fast processors and netowrks and very small dispersion and delay this forces a monotone-definite increase in E, which avoids loops between peers operating at the same stratum. Figure 15 shows how the error budget grows from the packet variables, on-wire protocol and system peer processe to produce the system variables that are passed to dependent applications and clients. The system jitter is defined (13), where Js is the selection jitter relative to the system peer computed as in (12). The system jitter is passed to dependent applications programs as the nominal error statistic. The root delay D and root dispersion E statistics are relative to the primary server reference clock and thus inherited by each server along the path. The system synchronization distance is defined (14), which is passed to dependent application programs as the maximum error statistic. 9.2.4 Clock Discipline Algorithm The NTPv4 clock discipline algorithm, shortened to discipline in the following, functions as a combination of two philosophically quite different feedback control systems. In a phase-locked loop (PLL) design, periodic phase updates at update intervals m are used directly to minimize the time error and indirectly the frequency error. In a frequency-locked loop (FLL) design, periodic frequency updates at intervals m are used directly to minimize the frequency error and indirectly the time error. As shown in [2], a PLL usually works better when network jitter dominates, while a FLL works better when oscillator wander dominates. This section contains an outline of how the NTPv4 design works. An in-depth discussion of the design principles is provided in [2], which also includes a performance analysis. Recall from Figure 1 how the clock discipline and clock adjust processes interact with the other algorithms in NTPv4. The output of the combining algorithm represents the best estimate of the system clock offset relative to the server ensemble. The discipline adjusts the frequency of the VFO to minimize this offset. Finally, the timestamps of each server are compared to the timestamps derived from the VFO in order to calculate the server offsets and close the feedback loop. The discipline is implemented as the feedback control system shown in Figure 16. The variable qr represents the combining algorithm offset (reference phase) and qc the VFO offset (control phase). Each update produces a signal Vd representing the instantaneous phase difference . The clock filter for each server functions as a tapped delay line, with the output taken at the tap selected by the clock filter algorithm. The selection, clustering and combining algorithms combine the data from multiple filters to produce the signal Vs. The loop filter, with impulse response F(t), produces the signal Vc which controls the VFO frequency wc and thus its phase , which closes the loop. The Vc signal is generated by the clock adjust process in Section 9.3. It runs at intervals of one second in the NTP daemon or one tick in the kernel implementation. The characteristic behavior of this model, which is determined by F(t) and the various gain factors given in Section B.6.6. The transient behavior of the PLL/FLL feedback loop is determined by the impulse response of the loop filter F(t). The loop filter shown in Figure 17 predicts a phase adjustment x as a function of Vs. The PLL predicts a frequency adjustment as an integral , while the FLL predicts an adjustment as a function of . The two adjustments are combined to correct the frequency y as shown in Figure 16. The x and y are then used by the clock_adjust() routine to control the VFO frequency. The detailed equations that implement these functions are best presented in the routines of Sections B.6.6 and B.7.1. Ordinarily, the pseudo-linear feedback loop described above operates to discipline the system clock. However, there are cases where a nonlinear algorithm offers considerable improvement. One case is when the discipline starts without knowledge of the intrinsic clock frequency. The pseudo-linear loop takes several hours to develop an accurate measurement and during most of that time the poll interval cannot be increased. The nonlinear loop described below does this in 15 minutes. Another case is when occasional bursts of large jitter are present due to congested network links. The state machine described below resists error bursts lasting less than 15 minutes. The remainder of this section describes how the discipline works. Table 9 contains a summary of the variables and parameters including the program name, formula name and short description. Unless noted otherwisse, all variables have assumed prefix c. The variables c.t, c.tc, c.state, and c.count are integers; the memainder are floating doubles. The function of each will be explained in the algorithm descriptions below. The discipline is implemented by the local_clock() routine, which is called from the clock_update() routine in Figure 14. The local_clock() routine pseudo code in Section B.6.6 has two parts; first the state machine shown in Figure 18 and second the algorithm that determines the time constant and thus the poll interval in Figure 19. The state transition function in Figure 18 is implemented by the rst() function shown at the lower left of the figure. The local_clock() routine exits immediately if the offset is greater than the panic threshold. The reference implementation sends a message to the operator and system log to set the clock manually within that range. A command line option can be used to override this behavior, but only for the first occurrence. Subsequent behavior depends on the offset magnitude and a state machine that determines if the offset and frequency are adjusted in steps or gradual increments. The state machine transition function is shown in Table 10.. The first column is the state name; the second column shows the next state and actions if the offset is less than the step threshold; the third column shows the next state and actions if the offset is greater than the step threshold; the fourth shows a brief comment. The next state is indicated by an arrow Ζ followed by the next state name. Some actions are conditional on whether the update interval m exceeds the stepout threshold WATCH (900 s). In order to speed convergence when the program is restarted, the reference implementation records the frequency offset in a file once each hour. When the program is started and the file has not been created, the machine starts in the NSET state, where it initializes the time and transitions to the FREQ state. The machine stays in that state until the first update after the stepout interval, when it computes the frequency directly and transitions to the SYNC state. When started after the frequency file has been written, the machine starts in the FSET state, where it initializes the time, reads the frequency file and transitions to the SYNC state, but steps the time if the offset exceeds the step threshold. The calculations are carefully designed so that time corrections and frequency corrections can be done independently. In SYNC state the time and frequency are normally adjusted in small increments, unless the offset exceeds the step threshold, in which case the state machine transitions to the SPIK state and avoids setting the time. If further updates exceed the step threshold, they are ignored until after the stepout interval, when the time is stepped. If during the stepout interval an offset is less than the step threshold, the machine transitions to SYNC state and operations resume normally. The remaining portion of the local_clock() routine is shown in Figure 19. The time constant t is determined by comparing the clock jitter j with the magnitude of the current residual offset QR. produced by the clock adjust routine in the next section. If the residual offset is greater than PGATE (4) times the clock jitter, be hysteresis counter is reduced by two; otherwise, it is increased by one. If the hysteresis counter increases to the upper limit LIMIT (30), the time constant is increased by one; if it decreases to the lower limit -LIMIT (-30), the time constant is decreased by one. Normally, the time constant hovers near MAXPOLL, but quickly decreases it frequency surges due to a temperature spike, for example. The clock jitter statistc J in Figure 18 and the clock wander statistic Y in Figure 19 are implemented as exponential averages of RMS offset differences and RMS frequency differences, respectively. Let xi be a measurement at time i of either J or Y, the first-order sample difference and the exponential average,. Then, (15), .where AVG (4) is the averaging parameter in Table 9, is the exponential average at time . The clock jitter statistic is used by the poll-adjust algorithm above; the clock wander statistic is used only for performance monitoring. It is most useful as a canary to detect stalled fans and failed air conditioning systems. 9.3 Clock Adjust Process The actual clock adjustment is performed by the clock_adjust() routine shown in Figure 20 and Section B.7.1. It runs at one-second intervals to add the frequency offset f in Figure 19 and a fixed percentage of the residual offset QR. in Figure 18. The QR. is in effect the exponential decay of the Q value produced by the loop filter at each update. The TC parameter scales the time constant to match the poll interval for convenience. Note that the dispersion E increases by F at each second. The clock adjust process includes a timer interrupt facility driving the system timer c.t. It begins at zero when the service starts and increments once each second. At each interrupt the clock_adjust() routine is called to incorporate the clock discipline time and frequency adjustments, then the associations are scanned to determine if the system timer equals or exceeds the p.next state variable defined in the next section. If so, the poll process is called to send a packet and compute the next p.next value. 10. Poll Process Each association supports a poll process that runs at regular intervals to construct and send packets in symmetric, client and broadcast server associations. It runs continuously, whether or not servers are reachable. The discussion in this section covers only the variables and routines necessary for a conforming NTPv4 implementation. Additional implementation details are in Section B.8. Further details and rationale for the engineering design are discussed in [2]. 10.1 Poll Process Variables and Parameters The poll process variables are allocated in the association data structure along with the peer process variables. Table 11 shows the names, formula names and short definition for each one. Following is a detailed description of the variables, all of which carry the p prefix. p.hpoll Signed integer representing the poll exponent, in log2 seconds. p.last Integer representing the system timer value when the most recent packet was sent. p.next Integer representing the system timer value when the next packet is to be sent. p.reach 8-bit integer shift register. When a packet is sent, the register is shifted left one bit, with zero entering from the right and overflow bits discarded. p.unreach Integer representing the number of seconds the server has been unreachable. 10.2 Poll Process Operations As described previously, once each second the clock_adjust() routine is called. This routine calls the poll() routine in Figure 21 and Section B.8.1 for each association in turn. If the time for the next poll message is greater than the system timer, the routine returns immediately. A mode-5 (broadcast server) association always sends a packet, but a mode-6 (broadcast client) association never sends a packet, but runs the routine to update the p.reach and p.unreach variables. The poll() routine calls the peer_xmit() routine in Figure 22 and Section B.8.3 to send a packet. If in a burst (p.burst > 0), nothing further is done except call the poll_update() routine to set the next poll interval. If not in a burst, the p.reach variable is shifted left by one bit, with zero replacing the rightmost bit. If the server has not been heard for the last three poll intervals, the clock_filter() routine is called to increase the dispersion as described in Section 8.3. If the BURST flag is lit and the server is reachable and a valid source of synchronization is available, the client sends a burst of BCOUNT (8) packets at each poll interval. This is useful to accurately measure jitter with long poll intervals. If the IBURST flag is lit and this is the first packet sent when the server becomes unreachable, the client sends a burst. This is useful to quickly reduce the synchronization distance below the distance threshold and synchronize the clock. The figure also shows the mechanism which backs off the poll interval if the server becomes unreachable. If p.reach is nonzero, the server is reachable and p.unreach is set to zero; otherwise, p.unreach is incremented by one for each poll to the maximum UNREACH (24). Thereafter for each poll p.hpoll is increased by one, which doubles the poll interval up to the maximum MAXPOLL determined by the poll_update() routine. When the server again becomes reachable, p.unreach is set to zero, p.hpoll is reset to t and operation resumes normally. When a packet is sent from an association, some header values are copied from the peer variables left by a previous packet and others from the system variables. Figure 22 includes a flow diagram and a table showing which values are copied to each header field. In those implementations using floating double data types for root delay and root dispersion, these must be converted to NTP short format. All other fields are either copied intact from peer and system variables or struck as a timestamp from the system clock. The poll_update() routine shown in Figure 23 and Section B.8.2 is called when a valid packet is received and immediately after a poll message is sent. If in a burst, the poll interval is fixed at 2 s; otherwise, the host poll exponent is set to the minimum of p.poll from the last packet received and p.hpoll from the poll() routine, but not less than MINPOLL nor greater than MAXPOLL. Thus the clock discipline can be oversampled, but not undersampled. This is necessary to preserve subnet dynamic behavior and protect against protocol errors. Finally, the poll exponent is converted to an interval which establishes the time at the next poll p.next. 11. References 1. Marzullo, K., and S. Owicki. Maintaining the time in a distributed system. ACM Operating Systems Review 19, 3 (July 1985), 44-54. 2. Mills, D.L. Computer Network Time Synchronization - the Network Time Protocol. CRC Press, 2006, 304 pp. 3. Mills, D.L. The Autokey security architecture, protocol and algorithms. Electrical and Com- puter Engineering Technical Report 06-1-1, University of Delaware, January 2006, 59 pp. 4. Mills, D., D. Plonka and J. Montgomery. Simple network time protocol (SNTP) version 4 for IPv4, IPv6 and OSI. Network Working Group Report RFC-4330, University of Delaware, December 2005, 27 pp. 5. Mills, D.L., A. Thyagarajan and B.C. Huffman. Internet timekeeping around the globe. Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Long Beach CA, December 1997). 6. Mills, D.L., Network Time Protocol (Version 3) specification, implementation and analysis. Network Working Group Request for Comments RFC-1305, University of Delaware, March 1992. 7. Rivest, R. “The MD5 message-digest algorithm. Network Working Group Request for Com- ments RFC-1321. MIT Laboratory for Computer Science and RSA Data Security, Inc., April 1992. Figure 1. Implementation Model Figure 2. NTP Time Formats Table 3. Name Prefix Conventions Table 5. Packet Header Variables Figure 3. On-Wire Protocol Table 6. Peer Process Variables Figure 7. Packet Processing Figure 15. System Variables Processing Table 8. System Process Variables and Parameters Table 11. Poll Process Variables and Parameters Figure 22. transmit() Routine Table 4. Global Parameters Figure 16. Clock Discipline Feedback Loop Figure 17. Clock Discipline Loop Filter Table 7. Packet Error Checks Table 1. Association and Packet Modes Figure 5. Client Packet Processing Figure 4. Receive Processing Figure 23. poll_update() Routine Figure 6. Timestamp Processing Figure 11. accept() Routine Figure 8. Clock Filter Processing Figure 21. poll() Routine Figure 10. Selection Algorithm Figure 12. Clustering Algorithm Figure 13. clock_combine() Routine Figure 14. clock_update() Routine Figure 9. clock_select() Routine Figure 20. clock_adjust() Routine Figure 18. local_clock() Routine (1 of 2) Table 10. Clock Discipline State Transition Table Figure 19. local_clock() Routine (2 of 2) Table 9. Clock Discipline Variables and Parameters Table 2. Interesting Historic NTP Dates