RFC 5905
Network Time Protocol Version 4: Protocol and Algorithms Specification
Pages: 110
Proposed Standard
→ Errata
Obsoletes: 1305 4330
Updated by: 7822 8573 9109
Proposed Standard
→ Errata
Obsoletes: 1305 4330
Updated by: 7822 8573 9109
Part 2 of 5 – Pages 16 to 39
7. Data Structures
The NTP state machines are defined in the following sections. 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. An example is described in Appendix A.7.1. Structure Conventions
In order to distinguish between different variables of the same name but used in different processes, the naming convention summarized in Figure 5 is adopted. 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. +------+---------------------------------+ | Name | Description | +------+---------------------------------+ | r. | receive packet header variable | | x. | transmit packet header variable | | p. | peer/poll variable | | s. | system variable | | c. | clock discipline variable | +------+---------------------------------+ Figure 5: Prefix Conventions7.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 Figure 6.
+-----------+-------+----------------------------------+ | Name | Value | Description | +-----------+-------+----------------------------------+ | PORT | 123 | NTP port number | | VERSION | 4 | NTP version number | | TOLERANCE | 15e-6 | frequency tolerance PHI (s/s) | | MINPOLL | 4 | minimum poll exponent (16 s) | | MAXPOLL | 17 | maximum poll exponent (36 h) | | MAXDISP | 16 | maximum dispersion (16 s) | | MINDISP | .005 | minimum dispersion increment (s) | | MAXDIST | 1 | distance threshold (1 s) | | MAXSTRAT | 16 | maximum stratum number | +-----------+-------+----------------------------------+ Figure 6: Global Parameters While these are the only global parameters needed for interoperability, a larger collection is necessary in any implementation. Appendix A.1.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 (also called PHI), 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 of this document. 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.7.3. Packet Header Variables
The most important state variables from an external point of view are the packet header variables described in Figure 7 and below. The NTP packet header consists of an integral number of 32-bit (4 octet) words in network byte order. The packet format consists of three components: the header itself, one or more optional extension fields, and an optional message authentication code (MAC). The header component is identical to the NTPv3 header and previous versions. The optional extension fields are used by the Autokey public key cryptographic algorithms described in [RFC5906]. The optional MAC is used by both Autokey and the symmetric key cryptographic algorithm described in this RFC.
+-----------+------------+-----------------------+ | Name | Formula | Description | +-----------+------------+-----------------------+ | leap | leap | leap indicator (LI) | | version | version | version number (VN) | | mode | mode | mode | | stratum | stratum | stratum | | poll | poll | poll exponent | | precision | rho | precision exponent | | rootdelay | delta_r | root delay | | rootdisp | epsilon_r | root dispersion | | refid | refid | reference ID | | reftime | reftime | reference timestamp | | org | T1 | origin timestamp | | rec | T2 | receive timestamp | | xmt | T3 | transmit timestamp | | dst | T4 | destination timestamp | | keyid | keyid | key ID | | dgst | dgst | message digest | +-----------+------------+-----------------------+ Figure 7: Packet Header Variables The NTP packet is a UDP datagram [RFC0768]. Some fields use multiple words and others are packed in smaller fields within a word. The NTP packet header shown in Figure 8 has 12 words followed by optional extension fields and finally an optional message authentication code (MAC) consisting of the Key Identifier field and Message Digest field.
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 |Mode | Stratum | Poll | Precision | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Root Delay | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Root Dispersion | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reference ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Reference Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Origin Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Receive Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Transmit Timestamp (64) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | . . . Extension Field 1 (variable) . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | . . . Extension Field 2 (variable) . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Key Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | dgst (128) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8: Packet Header Format
The extension fields are used to add optional capabilities, for example, the Autokey security protocol [RFC5906]. The extension field format is presented in order for the packet to be parsed without the knowledge of the extension field functions. The MAC is used by both Autokey and the symmetric key authentication scheme. A list of the packet header variables is shown in Figure 7 and described in detail below. Except for a minor variation when using the IPv6 address family, these fields are backwards compatible with NTPv3. The packet header fields apply to both transmitted packets (x prefix) and received packets (r prefix). In Figure 8, the size of some multiple-word fields is shown in bits if not the default 32 bits. The basic header extends from the beginning of the packet to the end of the Transmit Timestamp field. The fields and associated packet variables (in parentheses) are interpreted as follows: LI Leap Indicator (leap): 2-bit integer warning of an impending leap second to be inserted or deleted in the last minute of the current month with values defined in Figure 9. +-------+----------------------------------------+ | Value | Meaning | +-------+----------------------------------------+ | 0 | no warning | | 1 | last minute of the day has 61 seconds | | 2 | last minute of the day has 59 seconds | | 3 | unknown (clock unsynchronized) | +-------+----------------------------------------+ Figure 9: Leap Indicator VN Version Number (version): 3-bit integer representing the NTP version number, currently 4. Mode (mode): 3-bit integer representing the mode, with values defined in Figure 10.
+-------+--------------------------+ | Value | Meaning | +-------+--------------------------+ | 0 | reserved | | 1 | symmetric active | | 2 | symmetric passive | | 3 | client | | 4 | server | | 5 | broadcast | | 6 | NTP control message | | 7 | reserved for private use | +-------+--------------------------+ Figure 10: Association Modes Stratum (stratum): 8-bit integer representing the stratum, with values defined in Figure 11. +--------+-----------------------------------------------------+ | Value | Meaning | +--------+-----------------------------------------------------+ | 0 | unspecified or invalid | | 1 | primary server (e.g., equipped with a GPS receiver) | | 2-15 | secondary server (via NTP) | | 16 | unsynchronized | | 17-255 | reserved | +--------+-----------------------------------------------------+ Figure 11: Packet Stratum 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 clock selection algorithms used for external sources (see Appendix A.5.5.1 for an example). Poll: 8-bit signed integer representing the maximum interval between successive messages, in log2 seconds. Suggested default limits for minimum and maximum poll intervals 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 can be determined when the service first starts up as the minimum time of several iterations to read the system clock.
Root Delay (rootdelay): Total round-trip delay to the reference clock, in NTP short format. Root Dispersion (rootdisp): Total dispersion to the reference clock, in NTP short format. Reference ID (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 [RFC1345] 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 reference clock. The authoritative list of Reference Identifiers is maintained by IANA; however, any string beginning with the ASCII character "X" is reserved for unregistered experimentation and development. The identifiers in Figure 12 have been used as ASCII identifiers: +------+----------------------------------------------------------+ | ID | Clock Source | +------+----------------------------------------------------------+ | GOES | Geosynchronous Orbit Environment Satellite | | GPS | Global Position System | | GAL | Galileo Positioning System | | PPS | Generic pulse-per-second | | IRIG | Inter-Range Instrumentation Group | | WWVB | LF Radio WWVB Ft. Collins, CO 60 kHz | | DCF | LF Radio DCF77 Mainflingen, DE 77.5 kHz | | HBG | LF Radio HBG Prangins, HB 75 kHz | | MSF | LF Radio MSF Anthorn, UK 60 kHz | | JJY | LF Radio JJY Fukushima, JP 40 kHz, Saga, JP 60 kHz | | LORC | MF Radio LORAN C station, 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 Kauai, HI | | NIST | NIST telephone modem | | ACTS | NIST telephone modem | | USNO | USNO telephone modem | | PTB | European telephone modem | +------+----------------------------------------------------------+ Figure 12: Reference Identifiers Above stratum 1 (secondary servers and clients): this is the reference identifier of the server and can be used to detect timing loops. 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. Note that, when using the IPv6 address family on an NTPv4 server with a NTPv3 client, the Reference Identifier field appears to be a random value and a timing loop might not be detected. Reference Timestamp: Time when the system clock was last set or corrected, in NTP timestamp format. Origin Timestamp (org): Time at the client when the request departed for the server, in NTP timestamp format. Receive Timestamp (rec): Time at the server when the request arrived from the client, in NTP timestamp format. Transmit Timestamp (xmt): Time at the server when the response left for the client, in NTP timestamp format. Destination Timestamp (dst): Time at the client when the reply arrived from the server, in NTP timestamp format. Note: The Destination Timestamp field is not included as a header field; it is determined upon arrival of the packet and made available in the packet buffer data structure. If the NTP has access to the physical layer, then the timestamps are associated with the beginning of the symbol after the start of frame. Otherwise, implementations should attempt to associate the timestamp to the earliest accessible point in the frame. The MAC consists of the Key Identifier followed by the Message Digest. The message digest, or cryptosum, is calculated as in [RFC1321] over all NTP-header and optional extension fields, but not the MAC itself. Extension Field n: See Section 7.5 for a description of the format of this field. Key Identifier (keyid): 32-bit unsigned integer used by the client and server to designate a secret 128-bit MD5 key. Message Digest (digest): 128-bit MD5 hash computed over the key followed by the NTP packet header and extensions fields (but not the Key Identifier or Message Digest fields). It should be noted that the MAC computation used here differs from those defined in [RFC1305] and [RFC4330] but is consistent with how existing implementations generate a MAC.
7.4. The Kiss-o'-Death Packet
If the Stratum field is 0, which implies unspecified or invalid, the Reference Identifier field can be used to convey messages useful for status reporting and access control. These are called Kiss-o'-Death (KoD) packets and the ASCII messages they convey are called kiss codes. The KoD packets got their name because an early use was to tell clients to stop sending packets that violate server access controls. The kiss codes can provide useful information for an intelligent client, either NTPv4 or SNTPv4. Kiss codes are encoded in four-character ASCII strings that are left justified and zero filled. The strings are designed for character displays and log files. A list of the currently defined kiss codes is given in Figure 13. Recipients of kiss codes MUST inspect them and, in the following cases, take these actions: a. For kiss codes DENY and RSTR, the client MUST demobilize any associations to that server and stop sending packets to that server; b. For kiss code RATE, the client MUST immediately reduce its polling interval to that server and continue to reduce it each time it receives a RATE kiss code. c. Kiss codes beginning with the ASCII character "X" are for unregistered experimentation and development and MUST be ignored if not recognized. d. Other than the above conditions, KoD packets have no protocol significance and are discarded after inspection.
+------+------------------------------------------------------------+ | Code | Meaning | +------+------------------------------------------------------------+ | ACST | The association belongs to a unicast server. | | AUTH | Server authentication failed. | | AUTO | Autokey sequence failed. | | BCST | The association belongs to a broadcast server. | | CRYP | Cryptographic authentication or identification failed. | | DENY | Access denied by remote server. | | DROP | Lost peer in symmetric mode. | | RSTR | Access denied due to local policy. | | INIT | The association has not yet synchronized for the first | | | time. | | MCST | The association belongs to a dynamically discovered server.| | NKEY | No key found. Either the key was never installed or is | | | not trusted. | | RATE | Rate exceeded. The server has temporarily denied access | | | because the client exceeded the rate threshold. | | RMOT | Alteration of association from a remote host running | | | ntpdc. | | STEP | A step change in system time has occurred, but the | | | association has not yet resynchronized. | +------+------------------------------------------------------------+ Figure 13: Kiss Codes The Receive Timestamp and the Transmit Timestamp (set by the server) are undefined when in a KoD packet and MUST NOT be relied upon to have valid values and MUST be discarded.7.5. NTP Extension Field Format
In NTPv4, one or more extension fields can be inserted after the header and before the MAC, which is always present when an extension field is present. Other than defining the field format, this document makes no use of the field contents. An extension field contains a request or response message in the format shown in Figure 14.
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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Field Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . . . Value . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (as needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 14: Extension Field Format All extension fields are zero-padded to a word (four octets) boundary. The Field Type field is specific to the defined function and is not elaborated here. While the minimum field length containing required fields is four words (16 octets), a maximum field length remains to be established. The Length field is a 16-bit unsigned integer that indicates the length of the entire extension field in octets, including the Padding field.8. On-Wire Protocol
The heart of the NTP on-wire protocol is the core mechanism that exchanges time values between servers, peers, and clients. It is inherently resistant to lost or duplicate 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, which are 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 the case of link-level retransmission and corrected for the time to compute a MAC in transmit. NTP messages make use of two different communication modes, one-to- one and one-to-many, commonly referred to as unicast and broadcast. For the purposes of this document, the term broadcast is interpreted as any available one-to-many mechanism. For IPv4, this equates to either IPv4 broadcast or IPv4 multicast. For IPv6, this equates to IPv6 multicast. For this purpose, IANA has allocated the IPv4 multicast address 224.0.1.1 and the IPv6 multicast address ending :101, with the prefix determined by scoping rules. Any other non- allocated multicast address may also be used in addition to these allocated multicast addresses.
The on-wire protocol uses four timestamps numbered t1 through t4 and three state variables org, rec, and xmt, as shown in Figure 15. 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 packet timestamps are shown in lowercase, while the state variables are shown in uppercase. The state variables are copied from the packet timestamps upon arrival or departure of a packet.
t2 t3 t6 t7 +---------+ +---------+ +---------+ +---------+ | 0 | | t1 | | t3 | | t5 | +---------+ +---------+ +---------+ +---------+ | 0 | | t2 | | t4 | | t6 | Packet +---------+ +---------+ +---------+ +---------+ Timestamps | t1 | |t3=clock | | t5 | |t7=clock | +---------+ +---------+ +---------+ +---------+ |t2=clock | |t6=clock | +---------+ +---------+ Peer B +---------+ +---------+ +---------+ +---------+ org | T1 | | T1 | | t5<>T1? | | T5 | +---------+ +---------+ +---------+ +---------+ State rec | T2 | | T2 | | T6 | | T6 | Variables +---------+ +---------+ +---------+ +---------+ xmt | 0 | | T3 | | t3=T3? | | T7 | +---------+ +---------+ +---------+ +---------+ t2 t3 t6 t7 --------------------------------------------------------- /\ \ /\ \ / \ / \ / \ / \ / \/ / \/ --------------------------------------------------------- t1 t4 t5 t8 t1 t4 t5 t8 +---------+ +---------+ +---------+ +---------+ | 0 | | t1 | | t3 | | t5 | +---------+ +---------+ +---------+ +---------+ | 0 | | t2 | | t4 | | t6 | Packet +---------+ +---------+ +---------+ +---------+ Timestamps |t1=clock | | t3 | |t5=clock | | t7 | +---------+ +---------+ +---------+ +---------+ |t4=clock | |t8=clock | +---------+ +---------+ Peer A +---------+ +---------+ +---------+ +---------+ org | 0 | | t3<>0? | | T3 | | t7<>T3? | +---------+ +---------+ +---------+ +---------+ State rec | 0 | | T4 | | T4 | | T8 | Variables +---------+ +---------+ +---------+ +---------+ xmt | T1 | | t1=T1? | | T5 | | t5=T5? | +---------+ +---------+ +---------+ +---------+ Figure 15: On-Wire Protocol
In the figure, the first packet transmitted by A contains only the origin timestamp t1, which is then copied to T1. B receives the packet at t2 and copies t1 to T1 and the receive timestamp t2 to T2. At this time or some time later at t3, B sends a packet to A containing t1 and t2 and the transmit timestamp t3. All three timestamps are copied to the corresponding state variables. A receives the packet at t4 containing the three timestamps t1, t2, and t3 and the destination timestamp t4. These four timestamps are used to compute the offset and delay of B relative to A, as described below. Before the xmt and org state variables are updated, two sanity checks are performed in order to protect against duplicate, bogus, or replayed packets. In the exchange above, a packet is duplicate or replay if the transmit timestamp t3 in the packet matches the org state variable T3. A packet is bogus if the origin timestamp t1 in the packet does not match the xmt state variable T1. In either of these cases, the state variables are updated, then the packet is discarded. To protect against replay of the last transmitted packet, the xmt state variable is set to zero immediately after a successful bogus check. The four most recent timestamps, T1 through T4, are used to compute the offset of B relative to A theta = T(B) - T(A) = 1/2 * [(T2-T1) + (T3-T4)] and the round-trip delay delta = T(ABA) = (T4-T1) - (T3-T2). 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 sums and differences of these values, which contain 62 significant bits and two sign bits, so they 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 timestamp magnitudes, there is no loss in significance, yet the unambiguous range is restored from 34 years to 68 years. In some scenarios where the initial frequency offset of the client is relatively large and the actual propagation time small, it is possible for the delay computation to become 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 delta should be clamped not less than s.rho, where s.rho is the system precision described in Section 11.1, expressed in seconds. 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 a Section 9 and following sections and in the appendix. Note that the on-wire protocol as described resists replay of a server response packet. However, it does not resist replay of the client request packet, which would result in a server reply packet with new values of T2 and T3 and result in incorrect offset and delay. This vulnerability can be avoided by setting the xmt state variable to zero after computing the offset and delay.9. Peer Process
The process descriptions to follow include a listing of the important state variables followed by an overview of the process operations implemented as routines. Frequent reference is made to the skeleton in the appendix. The skeleton includes C-language fragments that describe the functions in more detail. It includes the parameters, variables, and declarations necessary for a conforming NTPv4 implementation. However, many additional variables and routines may be necessary in a working implementation. The peer process is called upon arrival of a server or peer packet. It runs the on-wire protocol to determine the clock offset and round- trip delay and 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 process for each server.
9.1. Peer Process Variables
Figures 16, 17, 18, and 19 summarize the common names, formula names, and a short description of the peer variables. The common names and formula names are interchangeable; formula names are intended to increase readability of equations in this specification. Unless noted otherwise, all peer variables have assumed prefix p. +---------+----------+-----------------------+ | Name | Formula | Description | +---------+----------+-----------------------+ | srcaddr | srcaddr | source address | | srcport | srcport | source port | | dstaddr | dstaddr | destination address | | dstport | destport | destination port | | keyid | keyid | key identifier key ID | +---------+----------+-----------------------+ Figure 16: Peer Process Configuration Variables +-----------+------------+---------------------+ | Name | Formula | Description | +-----------+------------+---------------------+ | leap | leap | leap indicator | | version | version | version number | | mode | mode | mode | | stratum | stratum | stratum | | ppoll | ppoll | peer poll exponent | | rootdelay | delta_r | root delay | | rootdisp | epsilon_r | root dispersion | | refid | refid | reference ID | | reftime | reftime | reference timestamp | +-----------+------------+---------------------+ Figure 17: Peer Process Packet Variables +------+---------+--------------------+ | Name | Formula | Description | +------+---------+--------------------+ | org | T1 | origin timestamp | | rec | T2 | receive timestamp | | xmt | T3 | transmit timestamp | | t | t | packet time | +------+---------+--------------------+ Figure 18: Peer Process Timestamp Variables
+--------+---------+-----------------+ | Name | Formula | Description | +--------+---------+-----------------+ | offset | theta | clock offset | | delay | delta | round-trip delay| | disp | epsilon | dispersion | | jitter | psi | jitter | | filter | filter | clock filter | | tp | t_p | filter time | +--------+---------+-----------------+ Figure 19: Peer Process Statistics Variables The following configuration variables are normally initialized when the association is mobilized, either from a configuration file or upon the arrival of the first packet for an unknown association. srcaddr: IP address of the remote server or reference clock. This becomes the destination IP address in packets sent from this association. 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. dstaddr: IP address of the client. This becomes the source IP address in packets sent from this association. 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. 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 in Figure 17 are updated from the packet header as each packet arrives. They are interpreted in the same way as the packet variables of the same names. It is convenient for later processing to convert the NTP short format packet values r.rootdelay and r.rootdisp to floating doubles as peer variables. The variables defined in Figure 18 include the timestamps exchanged by the on-wire protocol in Section 8. The t variable is the seconds counter c.t associated with these values. The c.t variable is maintained by the clock-adjust process described in Section 12. It
counts the seconds since the service was started. The variables defined in Figure 19 include the statistics computed by the clock_filter() routine described in Section 10. The tp variable is the seconds counter associated with these values.9.2. Peer Process Operations
The receive routine defines the process flow upon the arrival of a packet. An example is described by the receive() routine in Appendix A.5.1. There is no specific method required for access control, although it is recommended that implementations include such a scheme, which is similar to many others now in widespread use. The access() routine in Appendix A.5.4 describes a method of implementing access restrictions using an access control list (ACL). 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, then the MD5-keyed hash algorithm described in [RFC1321] must be supported. Next, the association table is searched for matching source address and source port, for example, using the find_assoc() routine in Appendix A.5.1. Figure 20 is a dispatch table where the columns correspond to the packet mode and rows correspond to the association mode. The intersection of the association and packet modes dispatches processing to one of the following steps. +------------------+---------------------------------------+ | | Packet Mode | +------------------+-------+-------+-------+-------+-------+ | Association Mode | 1 | 2 | 3 | 4 | 5 | +------------------+-------+-------+-------+-------+-------+ | No Association 0 | NEWPS | DSCRD | FXMIT | MANY | NEWBC | | Symm. Active 1 | PROC | PROC | DSCRD | DSCRD | DSCRD | | Symm. Passive 2 | PROC | ERR | DSCRD | DSCRD | DSCRD | | Client 3 | DSCRD | DSCRD | DSCRD | PROC | DSCRD | | Server 4 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | | Broadcast 5 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | | Bcast Client 6 | DSCRD | DSCRD | DSCRD | DSCRD | PROC | +------------------+-------+-------+-------+-------+-------+ Figure 20: Peer Dispatch Table DSCRD. This indicates a non-fatal violation of protocol as the result of a programming error, long-delayed packet, or replayed packet. The peer process discards the packet and exits.
ERR. This indicates a fatal violation of protocol as the result of a programming error, long-delayed packet, or replayed packet. The peer process discards the packet, demobilizes the symmetric passive association, and exits. FXMIT. This indicates a client (mode 3) packet matching no association (mode 0). If the destination address is not a broadcast address, the server constructs a server (mode 4) packet and returns it to the client without retaining state. The server packet header is constructed. An example is described by the fast_xmit() routine in Appendix A.5.3. The packet header is assembled from the receive packet and system variables as shown in Figure 21. If the s.rootdelay and s.rootdisp system variables are stored in floating double, they must be converted to NTP short format first. +-----------------------------------+ | Packet Variable --> Variable | +-----------------------------------+ | r.leap --> p.leap | | r.mode --> p.mode | | r.stratum --> p.stratum | | r.poll --> p.ppoll | | r.rootdelay --> p.rootdelay | | r.rootdisp --> p.rootdisp | | r.refid --> p.refid | | r.reftime --> p.reftime | | r.keyid --> p.keyid | +-----------------------------------+ Figure 21: Receive Packet Header 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 Figure 8, but with a MAC consisting of four octets of zeros. The client MAY accept or reject the data in the message. After these actions, the peer process exits. If the destination address is a multicast address, the sender is operating in manycast client mode. If the packet is valid and the server stratum is less than the client stratum, the server sends an ordinary server (mode 4) packet, but one which uses its unicast destination address. A crypto-NAK is not sent if authentication fails. After these actions, the peer process exits. MANY: This indicates a server (mode 4) packet matching no association. Ordinarily, this can happen only as the result of a manycast server reply to a previously sent multicast client packet.
If the packet is valid, an ordinary client (mode 3) association is mobilized and operation continues as if the association was mobilized by the configuration file. NEWBC. This indicates a broadcast (mode 5) packet matching no association. The client mobilizes either a client (mode 3) or broadcast client (mode 6) association. Examples are shown in the mobilize() and clear() routines in Appendix A.2. Then, the packet is validated and the peer variables initialized. An example is provided by the packet() routine in Appendix A.5.1.1. If the implementation supports no additional security or calibration functions, the association mode is set to broadcast client (mode 6) and the peer process exits. Implementations supporting public key authentication MAY run the Autokey or equivalent security protocol. Implementations SHOULD set the association mode to 3 and run a short client/server exchange to determine the propagation delay. Following the exchange, the association mode is set to 6 and the peer process continues in listen-only mode. 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 indicates a symmetric active (mode 1) packet matching no association. The client mobilizes a symmetric passive (mode 2) association. An example is shown in the mobilize() and clear() routines in Appendix A.2. Processing continues in the PROC section below. PROC. This indicates a packet matching an existing association. The packet timestamps are carefully checked to avoid invalid, duplicate, or bogus packets. Additional checks are summarized in Figure 22. Note that all packets, including a crypto-NAK, are considered valid only if they survive these tests.
+--------------------------+----------------------------------------+ | Packet Type | Description | +--------------------------+----------------------------------------+ | 1 duplicate packet | The packet is at best an old duplicate | | | or at worst a replay by a hacker. | | | This can happen in symmetric modes if | | | the poll intervals are uneven. | | 2 bogus packet | | | 3 invalid | One or more timestamp fields are | | | invalid. This normally happens in | | | symmetric modes when one peer sends | | | the first packet to the other and | | | before the other has received its | | | first reply. | | 4 access denied | The access controls have blacklisted | | | the source. | | 5 authentication failure | The cryptographic message digest does | | | not match the MAC. | | 6 unsynchronized | The server is not synchronized to a | | | valid source. | | 7 bad header data | One or more header fields are invalid. | +--------------------------+----------------------------------------+ Figure 22: Packet Error Checks Processing continues by copying the packet variables to the peer variables as shown in Figure 21. An example is described by the packet() routine in Appendix A.5.1.1. The receive() routine implements tests 1-5 in Figure 22; the packet() routine implements tests 6-7. If errors are found, the packet is discarded and the peer process exits. The on-wire protocol calculates the clock offset theta and round-trip delay delta from the four most recent timestamps as described in Section 8. 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. Next, the 8-bit p.reach shift register in the poll process described in Section 13 is used to determine whether 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 host poll interval is reviewed. An example is provided by the poll_update() routine in Appendix A.5.7.2. The dispersion statistic epsilon(t) represents the maximum error due to the frequency tolerance and time since the last packet was sent. It is initialized epsilon(t_0) = r.rho + s.rho + PHI * (T4-T1) when the measurement is made at t_0 according to the seconds counter. Here, r.rho is the packet precision described in Section 7.3 and s.rho is the system precision described in Section 11.1, 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 PHI; in other words, at time t, epsilon(t) = epsilon(t_0) + PHI * (t-t_0). With the default value PHI = 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 epsilon. The remaining statistics are computed by the clock filter algorithm described in the next section.10. Clock Filter Algorithm
The clock filter algorithm is part of the peer process. It grooms the stream of on-wire data to select the samples most likely to represent accurate time. The algorithm produces the variables shown in Figure 19, including the offset (theta), delay (delta), dispersion (epsilon), jitter (psi), and time of arrival (t). These data are 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 clock filter algorithm saves the most recent sample tuples (theta, delta, epsilon, t) in the filter structure, which functions as an 8-stage shift register. The tuples are saved in the order that packets arrive. Here, t is the packet time of arrival according to the seconds counter and should not be confused with the peer variable tp. The following scheme is used to ensure sufficient samples are in the filter and that old stale data are discarded. Initially, the tuples of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, 0). As valid packets arrive, tuples are shifted into the filter causing old tuples to be discarded, so eventually only valid tuples 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 a
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 delta. Let i index the stages
starting with the lowest delta. If the first tuple epoch t_0 is not
later than the last valid sample epoch tp, the routine exits without
affecting the current peer variables. Otherwise, let epsilon_i be
the dispersion of the ith entry, then
i=n-1
--- epsilon_i
epsilon = \ ----------
/ (i+1)
--- 2
i=0
is the peer dispersion p.disp. Note the overload of epsilon, 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, and (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 or not the peer variables are acceptable.
Let the first stage offset in the sorted list be theta_0; then, for
the other stages in any order, the jitter is the RMS average
+----- -----+^1/2
| n-1 |
| --- |
1 | \ 2 |
psi = -------- * | / (theta_0-theta_j) |
(n-1) | --- |
| j=1 |
+----- -----+
where n is the number of valid tuples in the filter (n > 1). In
order to ensure consistency and avoid divide exceptions in other
computations, the psi is bounded from below by the system precision s.rho 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 delay and dispersion. lambda = (delta / 2) + epsilon. Note that epsilon and therefore lambda increase at rate PHI. The lambda is not a state variable, since lambda is recalculated at each use. It is a component of the root synchronization distance used by the mitigation algorithms as a metric to evaluate the quality of time available from each server. It is important to note that, unlike NTPv3, NTPv4 associations do not show a timeout condition by setting the stratum to 16 and leap indicator to 3. The association variables retain the values determined upon arrival of the last packet. In NTPv4, lambda increases with time, so eventually the synchronization distance exceeds the distance threshold MAXDIST, in which case the association is considered unfit for synchronization. An example implementation of the clock filter algorithm is shown in the clock_filter() routine of Appendix A.5.2.
(page 39 continued on part 3)