draft-ietf-ntp-ntpv4-proto-04.txt   draft-ietf-ntp-ntpv4-proto-05.txt 
NTP WG J. Burbank, Ed. NTP WG J. Burbank, Ed.
Internet-Draft W. Kasch, Ed. Internet-Draft W. Kasch, Ed.
Obsoletes: RFC 4330, RFC 1305 JHU/APL Obsoletes: RFC 4330, RFC 1305 JHU/APL
(if approved) J. Martin, Ed. (if approved) J. Martin, Ed.
Intended status: Standards Track Netzwert AG Intended status: Standards Track Daedelus
Expires: July 21, 2007 D. Mills Expires: September 24, 2007 D. Mills
U. Del. U. Delaware
January 17, 2007 March 23, 2007
Network Time Protocol Version 4 Protocol And Algorithms Specification Network Time Protocol Version 4 Protocol And Algorithms Specification
draft-ietf-ntp-ntpv4-proto-04 draft-ietf-ntp-ntpv4-proto-05
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 38 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on July 21, 2007. This Internet-Draft will expire on September 24, 2007.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
The Network Time Protocol (NTP) is widely used to synchronize The Network Time Protocol (NTP) is widely used to synchronize
computer clocks in the Internet. This memorandum describes Version 4 computer clocks in the Internet. This document describes NTP Version
of the NTP (NTPv4), introducing several changes from Version 3 of NTP 4 (NTPv4), which is backwards compatible with NTP Version 3 (NTPv3)
(NTPv3) described in RFC 1305, including the introduction of a described in RFC 1305, as well as previous versions of the protocol.
modified protocol header to accomodate Internet Protocol Version 6.
NTPv4 also includes optional extensions to the NTPv3 It includes a modified protocol header to accommodate the Internet
protocol,including a dynamic server discovery mechanism. Protocol Version 6 address family. NTPv4 includes fundamental
improvements in the mitigation and discipline algorithms which extend
the potential accuracy to the tens of microseconds with modern
workstations and fast LANs. It includes a dynamic server discovery
scheme, so that in many cases specific server configuration is not
required. It corrects certain errors in the NTPv3 design and
implementation and includes an optional extension mechanism.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 5 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 5
2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 5 2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 5
3. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Protocol Modes . . . . . . . . . . . . . . . . . . . . . . . 6
4. Implementation Model . . . . . . . . . . . . . . . . . . . . 10 3.1. Simple Network Time Protocol (SNTP) . . . . . . . . . . . 7
5. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Dynamic Server Discovery . . . . . . . . . . . . . . . . 8
6. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 17 4. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.1. Structure Conventions . . . . . . . . . . . . . . . . . . 17 5. Implementation Model . . . . . . . . . . . . . . . . . . . . 11
6.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 17 6. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3. Packet Header Variables . . . . . . . . . . . . . . . . . 19 7. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 17
6.3.1. The Kiss-o'-Death Packet . . . . . . . . . . . . . . 25 7.1. Structure Conventions . . . . . . . . . . . . . . . . . . 17
6.3.2. NTP Extension Field Format . . . . . . . . . . . . . 26 7.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 17
7. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 28 7.3. Packet Header Variables . . . . . . . . . . . . . . . . . 18
8. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 32 7.4. The Kiss-o'-Death Packet . . . . . . . . . . . . . . . . 24
8.1. Peer Process Variables . . . . . . . . . . . . . . . . . 32 7.5. NTP Extension Field Format . . . . . . . . . . . . . . . 25
8.2. Peer Process Operations . . . . . . . . . . . . . . . . . 35 8. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 27
8.3. Clock Filter Algorithm . . . . . . . . . . . . . . . . . 42 9. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 31
9. System Process . . . . . . . . . . . . . . . . . . . . . . . 45 9.1. Peer Process Variables . . . . . . . . . . . . . . . . . 31
9.1. System Process Variables . . . . . . . . . . . . . . . . 45 9.2. Peer Process Operations . . . . . . . . . . . . . . . . . 34
9.2. System Process Operations . . . . . . . . . . . . . . . . 47 10. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . 38
9.2.1. Selection Algorithm . . . . . . . . . . . . . . . . . 48 11. System Process . . . . . . . . . . . . . . . . . . . . . . . 40
9.2.2. Clustering Algorithm . . . . . . . . . . . . . . . . 50 11.1. System Process Variables . . . . . . . . . . . . . . . . 40
9.2.3. Combining Algorithm . . . . . . . . . . . . . . . . . 52 11.2. System Process Operations . . . . . . . . . . . . . . . . 42
9.2.4. Clock Discipline Algorithm . . . . . . . . . . . . . 56 11.2.1. Selection Algorithm . . . . . . . . . . . . . . . . 44
9.3. Clock Adjust Process . . . . . . . . . . . . . . . . . . 64 11.2.2. Cluster Algorithm . . . . . . . . . . . . . . . . . 45
10. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 65 11.2.3. Combine Algorithm . . . . . . . . . . . . . . . . . 46
10.1. Poll Process Variables and Parameters . . . . . . . . . . 65 11.3. Clock Discipline Algorithm . . . . . . . . . . . . . . . 48
10.2. Poll Process Operations . . . . . . . . . . . . . . . . . 66 12. Clock Adjust Process . . . . . . . . . . . . . . . . . . . . 52
11. Security Considerations . . . . . . . . . . . . . . . . . . . 67 13. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 52
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67 13.1. Poll Process Variables . . . . . . . . . . . . . . . . . 52
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 68 13.2. Poll Process Operations . . . . . . . . . . . . . . . . . 53
14. Informative References . . . . . . . . . . . . . . . . . . . 68 14. Security Considerations . . . . . . . . . . . . . . . . . . . 55
Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 68 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 56
A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 69 16. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 56
A.1.1. Definitions, Constants, Parameters . . . . . . . . . 69 17. Informative References . . . . . . . . . . . . . . . . . . . 56
A.1.2. Packet Data Structures . . . . . . . . . . . . . . . 72 Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 57
A.1.3. Association Data Structures . . . . . . . . . . . . . 73 A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 58
A.1.4. System Data Structures . . . . . . . . . . . . . . . 76 A.1.1. Definitions, Constants, Parameters . . . . . . . . . 58
A.1.5. Local Clock Data Structures . . . . . . . . . . . . . 77 A.1.2. Packet Data Structures . . . . . . . . . . . . . . . 61
A.1.6. Function Prototypes . . . . . . . . . . . . . . . . . 77 A.1.3. Association Data Structures . . . . . . . . . . . . 62
A.2. Main Program and Utility Routines . . . . . . . . . . . . 78 A.1.4. System Data Structures . . . . . . . . . . . . . . . 64
A.3. Kernel Input/Output Interface . . . . . . . . . . . . . . 82 A.1.5. Local Clock Data Structures . . . . . . . . . . . . 65
A.4. Kernel System Clock Interface . . . . . . . . . . . . . . 82 A.1.6. Function Prototypes . . . . . . . . . . . . . . . . 65
A.5. Peer Process . . . . . . . . . . . . . . . . . . . . . . 84 A.2. Main Program and Utility Routines . . . . . . . . . . . . 66
A.5.1. receive() . . . . . . . . . . . . . . . . . . . . . . 85 A.3. Kernel Input/Output Interface . . . . . . . . . . . . . . 69
A.5.2. packet() . . . . . . . . . . . . . . . . . . . . . . 90 A.4. Kernel System Clock Interface . . . . . . . . . . . . . . 69
A.5.3. clock_filter() . . . . . . . . . . . . . . . . . . . 92 A.5. Peer Process . . . . . . . . . . . . . . . . . . . . . . 71
A.5.4. fast_xmit() . . . . . . . . . . . . . . . . . . . . . 93 A.5.1. receive() . . . . . . . . . . . . . . . . . . . . . 72
A.5.5. access() . . . . . . . . . . . . . . . . . . . . . . 95 A.5.2. clock_filter() . . . . . . . . . . . . . . . . . . . 79
A.6. System Process . . . . . . . . . . . . . . . . . . . . . 95 A.5.3. fast_xmit() . . . . . . . . . . . . . . . . . . . . 83
A.6.1. clock_select() . . . . . . . . . . . . . . . . . . . 95 A.5.4. access() . . . . . . . . . . . . . . . . . . . . . . 85
A.6.2. root_dist() . . . . . . . . . . . . . . . . . . . . . 99 A.5.5. System Process . . . . . . . . . . . . . . . . . . . 85
A.6.3. accept() . . . . . . . . . . . . . . . . . . . . . . 100 A.5.6. Clock Adjust Process . . . . . . . . . . . . . . . . 99
A.6.4. clock_update() . . . . . . . . . . . . . . . . . . . 100 A.5.7. Poll Process . . . . . . . . . . . . . . . . . . . . 100
A.6.5. clock_combine() . . . . . . . . . . . . . . . . . . . 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 107
A.6.6. local_clock() . . . . . . . . . . . . . . . . . . . . 103 Intellectual Property and Copyright Statements . . . . . . . . . 108
A.6.7. rstclock() . . . . . . . . . . . . . . . . . . . . . 109
A.7. Clock Adjust Process . . . . . . . . . . . . . . . . . . 109
A.7.1. clock_adjust() . . . . . . . . . . . . . . . . . . . 109
A.8. Poll Process . . . . . . . . . . . . . . . . . . . . . . 110
A.8.1. poll() . . . . . . . . . . . . . . . . . . . . . . . 110
A.8.2. poll_update() . . . . . . . . . . . . . . . . . . . . 112
A.8.3. peer_xmit() . . . . . . . . . . . . . . . . . . . . . 114
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115
Intellectual Property and Copyright Statements . . . . . . . . . 116
1. Introduction 1. Introduction
This document specifies the Network Time Protocol Version 4 (NTPv4), This document defines the Network Time Protocol Version 4 (NTPv4),
which is widely used to synchronize the system clocks among a set of which is widely used to synchronize the system clocks among a set of
distributed time servers and clients. This document defines the core distributed time servers and clients. It describes the core
architecture, protocol, state machines, data structures and architecture, protocol, state machines, data structures and
algorithms. This document describes NTPv4, which introduces new algorithms. NTPv4 introduces new functionality to NTPv3, as
functionality to NTPv3 as described in [1], and functionality described in [1], and functionality expanded from SNTPv4 as described
expanded from that of SNTPv4 as described in [2] (SNTPv4 is a subset in [2] (SNTPv4 is a subset of NTPv4). This document obsoletes [1],
of NTPv4). This document obsoletes RFC 1305 and RFC 4330. While and [2]. While certain minor changes have been made in some protocol
certain minor changes have been made in some protocol header fields, header fields, these do not affect the interoperability between NTPv4
these do not affect the interoperability between NTPv4 and previous and previous versions of NTP and SNTP.
versions.
The NTP subnet model includes a number of widely accessible primary The NTP subnet model includes a number of widely accessible primary
time servers synchronized by wire or radio to national standards. time servers synchronized by wire or radio to national standards.
The purpose of the NTP protocol is to convey timekeeping information The purpose of the NTP protocol is to convey timekeeping information
from these primary servers to secondary time servers and clients via from these primary servers to secondary time servers and clients via
both private networks and the public Internet. Crafted algorithms both private networks and the public Internet. Crafted algorithms
mitigate errors that may result from network disruptions, server mitigate errors that may result from network disruptions, server
failures and possible hostile action. Servers and clients are failures and possible hostile action. Servers and clients are
configured such that values flow from the primary servers at the root configured such that values flow from the primary servers at the root
via branching secondary servers toward clients. via branching secondary servers toward clients.
The NTPv4 design overcomes significant shortcomings in the NTPv3 The NTPv4 design overcomes significant shortcomings in the NTPv3
design, corrects certain bugs and incorporates new features. In design, corrects certain bugs and incorporates new features. In
particular, expanded NTP timestamp definitions encourage the use of particular, expanded NTP timestamp definitions encourage the use of
floating double data types throughout any implementation. The time floating double data types throughout the implementation. The time
resolution is better than one nanosecond and frequency resolution resolution is better than one nanosecond and frequency resolution
better than one nanosecond per second. Additional improvements better than one nanosecond per second. Additional improvements
include a new clock discipline algorithm which is more responsive to include a new clock discipline algorithm which is more responsive to
system clock hardware frequency fluctuations. Typical primary system clock hardware frequency fluctuations. Typical primary
servers using modern machines are precise within a few tens of servers using modern machines are precise within a few tens of
microseconds. Typical secondary servers and clients on fast LANs are microseconds. Typical secondary servers and clients on fast LANs are
within a few hundred microseconds with poll intervals up to 1024 within a few hundred microseconds with poll intervals up to 1024
seconds, which was the maximum with NTPv3. With NTPv4, servers and seconds, which was the maximum with NTPv3. With NTPv4, servers and
clients are within a few tens of milliseconds with poll intervals up clients are within a few tens of milliseconds with poll intervals up
to 36 hours. to 36 hours.
The main body of this document describes only the core protocol and The main body of this document describes the core protocol and data
data structures necessary to interoperate between conforming structures necessary to interoperate between conforming
implementations. Additional detail is provided in the form of a implementations. Appendix A contains additional detail in the form
skeleton program included as an appendix. This program includes data of a skeleton program including data structures and code segments for
structures and code segments for the core algorithms and in addition the core algorithms and in addition the mitigation algorithms used to
the mitigation algorithms used to enhance reliability and accuracy. enhance reliability and accuracy. While the skeleton and other
While the skeleton and other descriptions in this document apply to a descriptions in this document apply to a particular implementation,
particular implementation, they are not intended as the only way the they are not intended as the only way the required functions can be
required functions can be implemented. While the NTPv3 symmetric key implemented. While the NTPv3 symmetric key authentication scheme
authentication scheme described in this document carries over from described in this document carries over from NTPv3, the Autokey
NTPv3, the Autokey public key authentication scheme new to NTPv4 is public key authentication scheme new to NTPv4 is described in [3].
described in [3].
The NTP protocol includes the modes of operation described in The NTP protocol includes the modes of operation described in
Section 2 using the data types described in Section 5 and the data Section 2 using the data types described in Section 6 and the data
structures in Section 6. The implementation model described in structures in Section 7. The implementation model described in
Section 4 is based on a multiple-process, threaded architecture, Section 5 is based on a multiple-process, threaded architecture,
although other architectures could be used as well. The on-wire although other architectures could be used as well. The on-wire
protocol described in Section 7 is based on a returnable-time design protocol described in Section 8 is based on a returnable-time design
which depends only on measured clock offsets, but does not require which depends only on measured clock offsets, but does not require
reliable message delivery. The synchronization subnet is a self- reliable message delivery. The synchronization subnet is a self-
organizing, hierarchical, master-slave network with synchronization organizing, hierarchical, master-slave network with synchronization
paths determined by a shortest-path spanning tree and defined metric. paths determined by a shortest-path spanning tree and defined metric.
While multiple masters (primary servers) may exist, there is no While multiple masters (primary servers) may exist, there is no
requirement for an election protocol. requirement for an election protocol.
The remaining sections of this document define the data structures This document includes material from [4], which contains flow charts
and algorithms suitable for a fully featured NTPv4 implementation. and equations unsuitable for RFC format. There is much additional
Appendix A contains the code skeleton with definitions, structures information in [5], including an extensive technical analysis and
and code segments that represent the basic structure of the reference performance assessment of the protocol and algorithms in this
implementation. document. The reference implementation itself is available at
www.ntp.org.
The remainder of this document contains numerous variables and The remainder of this document contains numerous variables and
mathematical expressions. Those variables take the form of Greek mathematical expressions. Some variables take the form of Greek
characters. Those Greek characters are spelled out by their full characters, which are spelled out by their full case-sensitive name.
name, with the "cap" prefix added to variables referring to the For example DELTA refers to the uppercase Greek character, while
corresponding upper case Greek character. For example capdelta delta refers to the lowercase character. Furthermore, subscripts are
refers to the uppercase Greek character, where delta refers to the denoted with '_', for example theta_i refers to the lowercase Greek
lowercase Greek character. Furthermore, subscripts are denoted with character theta with subscript i, or phonetically theta sub i.
a '_' separating the variable name and the subscript. For example
'theta_i' refers to the variable lowercase Greek character theta with
subscript i, or phonetically 'theta sub i.'
1.1. Requirements Notation 1.1. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [4]. document are to be interpreted as described in [6].
2. Modes of Operation 2. Modes of Operation
An NTP implementation operates as a primary server, secondary server An NTP implementation operates as a primary server, secondary server
or client. A primary server is synchronized directly to a reference or client. A primary server is synchronized directly to a reference
clock, such as a GPS receiver or telephone modem service. A client clock, such as a GPS receiver or telephone modem service. A client
is synchronized to one or more upstream servers, but does not provide is synchronized to one or more upstream servers, but does not provide
synchronization to dependent clients. A secondary server has one or synchronization to dependent clients. A secondary server has one or
more upstream servers and one or more downstream servers or clients. more upstream servers and one or more downstream servers or clients.
All servers and clients claiming full NTPv4 compliance must implement All servers and clients claiming full NTPv4 compliance must implement
the entire suite of algorithms described in this document. In order the entire suite of algorithms described in this document. In order
to maintain stability in large NTP subnets, secondary servers must be to maintain stability in large NTP subnets, secondary servers must be
fully NTPv4 compliant. fully NTPv4 compliant.
Primary servers and clients complying with a subset of NTP, called 3. Protocol Modes
the Simple Network Time Protocol (SNTPv4) [2], do not need to
implement all algorithms. SNTP is intended for primary servers There are three NTP protocol variants, symmetric, client/server and
equipped with a single reference clock, as well as clients with a broadcast. Each is associated with an association mode as shown in
single upstream server and no dependent clients. The fully developed Figure 1. Persistent associations are mobilized upon startup and are
NTPv4 implementation is intended for secondary servers with multiple never demobilized. Ephemeral associations are mobilized upon arrival
upstream servers and multiple downstream servers or clients. Other of a packet and are demobilized upon error or timeout.
than these considerations, NTP and SNTP servers and clients are
completely interoperable and can be mixed and matched in NTP subnets.
+-------------------+--------------+-------------+ +-------------------+--------------+-------------+
| Association Mode | Assoc. Mode | Packet Mode | | Association Mode | Assoc. Mode | Packet Mode |
+-------------------+--------------+-------------+ +-------------------+--------------+-------------+
| Symmetric Active | 1 | 1 or 2 | | Symmetric Active | 1 | 1 or 2 |
| Symmetric Passive | 2 | 1 | | Symmetric Passive | 2 | 1 |
| Client | 3 | 4 | | Client | 3 | 4 |
| Server | 4 | 3 | | Server | 4 | 3 |
| Broadcast Server | 5 | 5 | | Broadcast Server | 5 | 5 |
| Broadcast Client | 6 | N/A | | Broadcast Client | 6 | N/A |
+-------------------+--------------+-------------+ +-------------------+--------------+-------------+
Table 1: Association and Packet Modes Figure 1: Association and Packet Modes
There are three NTP protocol variants, symmetric, client/server and In the client/server variant a persistent client association sends
broadcast. Each is associated with an association mode as shown in client (mode 3) packets to a server, which returns server (mode 4)
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 packets. Servers provide synchronization to one or more clients, but
do not accept synchronization from them. A server can also be a do not accept synchronization from them. A server can also be a
reference clock which obtains time directly from a standard source reference clock driver which obtains time directly from a standard
such as a GPS receiver or telephone modem service. We say that source such as a GPS receiver or telephone modem service. We say
clients pull synchronization from servers. that clients pull synchronization from servers.
In the symmetric variant a peer operates as both a server and client In the symmetric variant a peer operates as both a server and client
using either a symmetric-active or symmetric-passive association. A using either a symmetric active or symmetric passive association. A
symmetric-active association sends mode-1 (symmetric-active) packets persistent symmetric active association sends symmetric active (mode
to a symmetric-active peer association. Alternatively, a symmetric- 1) packets to a symmetric active peer association. Alternatively, an
passive association can be mobilized upon arrival of a mode-1 packet. ephemeral symmetric passive association can be mobilized upon arrival
That association sends mode-2 (symmetric-passive) packets and of a symmetric active packet matching no association. That
persists until error or timeout. Peers both push and pull association sends symmetric passive (mode 2) packets and persists
synchronization to and from each other. For the purposes of this until error or timeout. Peers both push and pull synchronization to
document, a peer operates like a client, so a reference to client and from each other. For the purposes of this document, a peer
implies peer as well. operates like a client, so a reference to client implies peer as
well.
In the broadcast variant a broadcast server association sends In the broadcast variant a persistent broadcast server association
periodic mode-5 (broadcast) packets which are received by multiple sends periodic broadcast server (mode 5) packets which can be
mode-6 (broadcast client) associations. It is useful to provide an received by multiple clients. Upon reception of a broadcast server
initial volley where the client operating in mode 3 exchanges several packet matching no association, an ephemeral broadcast client (mode
packets with the server in order to calibrate the propagation delay 6) association is mobilized and persists until error or timeout. It
and to run the Autokey security protocol, after which the client is useful to provide an initial volley where the client operating in
reverts to mode 6. We say that broadcast servers push client mode exchanges several packets with the server in order to
synchronization to willing consumers. calibrate the propagation delay and to run the Autokey security
protocol, after which the client reverts to broadcast client mode.
We say that broadcast servers push synchronization to willing
consumers.
Following conventions established by the telephone industry, the Following conventions established by the telephone industry, the
level of each server in the hierarchy is defined by a number called level of each server in the hierarchy is defined by a number called
the stratum, with the primary servers assigned stratum one and the the stratum, with the primary servers assigned stratum one and the
secondary servers at each level assigned one greater than the secondary servers at each level assigned one greater than the
preceding level. As the stratum increases from one, the accuracies preceding level. As the stratum increases from one, the accuracies
achievable degrade somewhat depending on the particular network path achievable degrade somewhat depending on the particular network path
and system clock stability. It is useful to assume that mean errors, and system clock stability. It is useful to assume that mean errors,
and thus a metric called the synchronization distance, increase and thus a metric called the synchronization distance, increase
approximately in proportion to the stratum and measured roundtrip approximately in proportion to the stratum and measured roundtrip
delay. It is important to note that NTP stratum is only loosely delay. It is important to note that NTP stratum is only loosely
modeled after telecommunications stratum. The NTP stratum numbers modeled after the telecommunications stratum, which is defined by
and telecommunications stratum numbers do not correlate with one international agreement.
another. Telecommunications stratum numbers are rigorously defined
by international standards that are not covered within this document.
Drawing from the experience of the telephone industry, which learned Drawing from the experience of the telecommunications industry, which
such lessons at considerable cost, the subnet topology should be learned such lessons at considerable cost, the subnet topology should
organized to produce the lowest synchronization distances, but must be organized to produce the lowest synchronization distances, but
never be allowed to form a loop. In NTP the subnet topology is must never be allowed to form a loop. In NTP the subnet topology is
determined using a variant of the Bellman-Ford distributed routing determined using a variant of the Bellman-Ford distributed routing
algorithm, which computes the shortest-distance spanning tree rooted algorithm, which computes the shortest-distance spanning tree rooted
on the primary servers. As a result of this design, the algorithm on the primary servers. As a result of this design, the algorithm
automatically reorganizes the subnet to produce the most accurate and automatically reorganizes the subnet to produce the most accurate and
reliable time, even when one or more primary or secondary servers or reliable time, even when one or more primary or secondary servers or
the network paths fail. the network paths fail.
3. Definitions 3.1. Simple Network Time Protocol (SNTP)
Primary servers and clients complying with a subset of NTP, called
the Simple Network Time Protocol (SNTPv4) [2], do not need to
implement the mitigation algorithms described in Section 9 and
following sections. SNTP is intended for primary servers equipped
with a single reference clock, as well as for 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 subnets.
An SNTP primary server implementing the on-wire protocol described in
Section 8 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, an SNTP primary server constructs
and sends the reply packet as described in Figure 2 of Section 9.2.
Note that the dispersion field in the packet header must be updated
as described in Section 4.
+-----------------------------------+
| Packet Variable <-- Variable |
+-----------------------------------+
| x.leap <-- s.leap |
| x.version <-- r.version |
| x.mode <-- 4 |
| x.stratum <-- s.stratum |
| x.poll <-- r.poll |
| x.precision <-- s.precision |
| x.rootdelay <-- s.rootdelay |
| x.rootdisp <-- s.rootdisp |
| x.refid <-- s.refid |
| x.reftime <-- s.reftime |
| x.org <-- r.xmt |
| x.rec <-- r.dst |
| x.xmt <-- clock |
| x.keyid <-- r.keyid |
| x.digest <-- md5 digest |
+-----------------------------------+
Figure 2: fast_xmit Packet Header
A SNTP client implementing the on-wire protocol has a single server
and no dependent 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.
3.2. Dynamic Server Discovery
There are two special associations, manycast client and manycast
server, which provide a dynamic server discovery function. There are
two types of manycast client associations, persistent and ephemeral.
The persistent manycast client sends client (mode 3) packets to a
designated IPv4 or IPv6 broadcast or multicast group address.
Designated manycast servers in range of the time-to-live (TTL) field
in the packet listen for packets with that address. If suitable for
synchronization, the server returns an ordinary server (mode 4)
packet, but using its unicast address rather than its broadcast
address. Upon receipt an ephemeral client (mode 3) association is
mobilized using the addresses and other data in the persistent
manycast client association and server packet header. The ephemeral
client association persists until error or timeout.
The manycast client continues to send packets until a specified
minimum number of client associations have been mobilized. If fewer
than this number have been found, the client sends packets starting
with a TTL of one and increasing by one for each subsequent packet
until reaching a designated maximum. Upon reaching the maximum,
packets are not sent until after a designated timeout, after which
the cycle repeats. If at least the minimum number of associations
have been found, the client sends one packet at each timeout.
It is the intent that ephemeral associations compete with other
associations and newly discovered associations. As each crop of
ephemeral associations are mobilized, the mitigation algorithms
described in Section 10 and Section 11.2 sift the best candidates
from the population and the remaining ephemeral associations time out
and are demobilized. In this way the population includes only the
best and freshest candidates to discipline the system clock. The
reference implementation includes intricate means to do this, but
these are beyond the scope of this document.
4. Definitions
A number of terms used throughout this document have a precise A number of terms used throughout this document have a precise
technical definition. A timescale is a frame of reference where time technical definition. A timescale is a frame of reference where time
is expressed as the value of a monotonic-increasing binary counter is expressed as the value of a monotonic-increasing binary counter
with an indefinite number of bits. It counts in seconds and fraction with an indefinite number of bits. It counts in seconds and fraction
with the decimal point somewhere in the middle. The Coordinated with the decimal point somewhere in the middle. The Coordinated
Universal Time (UTC) timescale represents mean solar time as Universal Time (UTC) timescale represents mean solar time as
disseminated by national standards laboratories. The system time is disseminated by national standards laboratories. The system time is
represented by the system clock maintained by the operating system represented by the system clock maintained by the hardware and
kernel. The goal of the NTP algorithms is to minimize both the time operating system. The goal of the NTP algorithms is to minimize both
difference and frequency difference between UTC and the system clock. the time difference and frequency difference between UTC and the
When these differences have been reduced below nominal tolerances, system clock. When these differences have been reduced below nominal
the system clock is said to be synchronized to UTC. 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 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 ephemeral values which always increase in step with reality and
are designated with upper case T in this document. It is convenient are designated with upper case T in this document. It is convenient
to define another timescale coincident with the running time of the to define another timescale coincident with the running time of the
NTP program that provides the synchronization function. This is NTP program that provides the synchronization function. This is
convenient in order to determine intervals for the various repetitive convenient in order to determine intervals for the various repetitive
functions like poll events. Running time is usually designated with functions like poll events. Running time is designated with lower
lower case t. case t.
A timestamp T(t) represents either the UTC date or time offset from 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 UTC at running time t. Which meaning is intended should be clear
from the context. Let T(t) be the time offset, R(t) the frequency from the 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 offset, D(t) the ageing rate (first derivative of R(t) with respect
to t). Then, if T(t_0) is the UTC time offset determined at t=t_0, to t). Then, if T(t_0) is the UTC time offset determined at t=t_0,
the UTC time offset after some interval is: the UTC time offset after some interval is
T(t+t_0) = T(t_0) + R(t_0)(t+t_0)+(1/2)*D(t_0)(t+t_0)^2 + e, T(t+t_0) = T(t_0) + R(t_0)(t+t_0) + 1/2 * D(t_0)(t+t_0)^2 + e,
where e is a stochastic error term discussed later in this document. where e is a stochastic error term discussed later in this document.
While the D(t) term is important when characterizing precision While the D(t) term is important when characterizing precision
oscillators, it is ordinarily neglected for computer oscillators. In oscillators, it is ordinarily neglected for computer oscillators. In
this document all time values are in seconds (s) and all frequency this document all time values are in seconds (s) and all frequency
values are in seconds-per-second (s/s). It is sometimes convenient values are in seconds-per-second (s/s). It is sometimes convenient
to express frequency offsets in parts-per-million (PPM), where 1 PPM to express frequency offsets in parts-per-million (PPM), where 1 PPM
is equal to 1*10^(-6) seconds. is equal to 10^(-6) seconds.
It is important in computer timekeeping applications to assess the It is important in computer timekeeping applications to assess the
performance of the timekeeping function. The NTP performance model performance of the timekeeping function. The NTP performance model
includes four statistics which are updated each time a client makes a includes four statistics which are updated each time a client makes a
measurement with a server. The offset theta represents the maximum- measurement with a server. The offset (theta) represents the
likelihood time offset of the server clock relative to the system maximum-likelihood time offset of the server clock relative to the
clock. The delay del represents the roundtrip delay between the system clock. The delay (delta) represents the round trip delay
client and server. The dispersion epsilon represents the maximum between the client and server. The dispersion (epsilon) represents
error inherent in the measurement. It increases at a rate equal to the maximum error inherent in the measurement. It increases at a
the maximum disciplined system clock frequency tolerance phi, rate equal to the maximum disciplined system clock frequency
typically 15 PPM. The jitter psi, defined as the root-mean-square tolerance (PHI), typically 15 PPM. The jitter (psi) is defined as
(RMS) average of the most recent time offset differences, represents the root-mean-square (RMS) average of the most recent offset
the nominal error in estimating theta. differences, represents the nominal error in estimating the offset.
While the theta, del, epsilon, and psi statistics represent While the theta, delta, epsilon, and psi statistics represent
measurements of the system clock relative to the each server clock measurements of the system clock relative to the each server clock
separately, the NTP protocol includes mechanisms to combine the separately, the NTP protocol includes mechanisms to combine the
statistics of several servers to more accurately discipline and statistics of several servers to more accurately discipline and
calibrate the system clock. The system offset captheta represents calibrate the system clock. The system offset (THETA) represents the
the maximum-likelihood offset estimate for the server population. maximum-likelihood offset estimate for the server population. The
The system jitter, defined as vartheta, represents the nominal error system jitter (PSI) represents the nominal error in estimating the
in estimating captheta. The del and epsilon statistics are system offset. The delta and epsilon statistics are accumulated at
accumulated at each stratum level from the reference clocks to each stratum level from the reference clock to produce the rootdelay
produce the root delay delta and root dispersion capepsilon (DELTA) and root dispersion (EPSILON) statistics. The
statistics. The synchronization distance gamma=capepsilon+delta/2 synchronization distance (LAMBDA) equal to EPSILON + DELTA / 2
represents the maximum error due all causes. The detailed represents the maximum error due all causes. The detailed
formulations of these statistics are given later in this document. formulations of these statistics are given in Section 11.2. They are
They are available to the dependent applications in order to assess available to the dependent applications in order to assess the
the performance of the synchronization function. performance of the synchronization function.
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 | Strat | Poll | Prec |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Reference Timestamp +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Origin Timestamp +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Receive Timestamp +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Transmit Timestamp +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Extension Field 1 (Optional) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Extension Field 2 (Optional) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Authentication .
. (Optional) (160 bits) .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: NTPv4 Message Format
4. Implementation Model 5. Implementation Model
Figure 2 shows two processes dedicated to each server, a peer process Figure 3 shows the architecture of a typical, multiple-thread
to receive messages from the server or reference clock and a poll implementation. It includes two processes dedicated to each server,
process to transmit messages to the server or reference clock. . 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.
.......................................................... .....................................................................
. Remote .. Peer/Poll .. System . . Remote . Peer/Poll . System . Clock .
. Servers .. Processes .. Process . . Servers . Processes . Process .Discipline.
. .. .. . . . . . Process .
.----------..-------------..-------------- . .+--------+. +-----------+. +------------+ . .
.| |->| |..| | . .| |->| |. | | . .
.|Server 1|..|Peer/Poll 1|->| | . .|Server 1| |Peer/Poll 1|->| | . .
.| |<-| |..| | ............ .| |<-| |. | | . .
.----------..-------------..| | . Clock . .+--------+. +-----------+. | | . .
.Discipline. . . ^ . | | . .
. .. ^ ..| | .. Process . . . | . | | . .
. .. | ..| | .. . .+--------+. +-----------+. | | +-----------+. .
.----------..-------------..| | |-----------|.. . .| |->| |. | Selection |->| |. +------+ .
.| |->| |..| Selection |->| ..-------- . .|Server 2| |Peer/Poll 2|->| and | | Combine |->| Loop | .
.|Server 2|..|Peer/Poll 2|->| and | | Combining |->| Loop | . .| |<-| |. | Cluster | | Algorithm |. |Filter| .
.| |<-| |..| Clustering | | Algorithm |..|Filter| . .+--------+. +-----------+. | Algorithms |->| |. +------+ .
.----------..-------------..| Algorithms |->| |.----------- . . ^ . | | +-----------+. | .
. .. ^ ..| | |-----------|. | . . | . | | . | .
. .. | ..| | . | .+--------+. +-----------+. | | . | .
.----------..-------------..| | . | .| |->| |. | | . | .
.| |->| |..| | . | .|Server 3| |Peer/Poll 3|->| | . | .
.|Server 3|..|Peer/Poll 3|->| | . | .| |<-| |. | | . | .
.| |<-| |..| | . | .+--------+. +-----------+. +------------+ . | .
.----------..-------------..|------------| . | ....................^.........................................|......
....................^..................................... | | . V .
| | | . +-----+ .
| \|/ +--------------------------------------| VFO | .
| ............... . +-----+ .
| . /-----\ . . Clock .
'----------------------------------<-| VFO |-<-. . Adjust .
. \-----/ .
. Clock Adjust.
. Process . . Process .
............... ............
Figure 2: NTPv4 Algorithm Interactions Figure 3: Implementatin Model
These processes operate on a common data structure called an These processes operate on a common data structure, called an
association, which contains the statistics described above along with association, which contains the statistics described above along with
various other data described later. A client sends an NTP packet to various other data described in Section 9. A client sends packets to
one or more servers and processes the replies as received. The one or more servers and processes the replies as received. The
server interchanges addresses and ports, overwrites certain fields in server interchanges addresses and ports, overwrites certain fields in
the packet and returns it immediately (client/ server mode) or at the packet and returns it immediately (client/server mode) or at some
some time later (symmetric modes). As each NTP message is received, time later (symmetric modes). As each NTP message is received, the
the offset theta between the peer clock and the system clock is offset theta between the peer clock and the system clock is computed
computed along with the associated statistics del, epsilon, and psi. along with the associated statistics delta, epsilon and psi.
The system process includes the selection, clustering and combining The system process includes the selection, cluster and combine
algorithms which mitigate among the various servers and reference algorithms which mitigate among the various servers and reference
clocks to determine the most accurate and reliable candidates to clocks to determine the most accurate and reliable candidates to
synchronize the system clock. The selection algorithm uses Byzantine synchronize the system clock. The selection algorithm uses Byzantine
principles to discard the falsetickers from the incident population, principles to discard the falsetickers from the incident population,
leaving only truechimers. A 'truechimer' is a clock that maintains leaving only truechimers. A truechimer is a clock that maintains
timekeeping accuracy to a previously published (and trusted) timekeeping accuracy to a previously published (and trusted)
standard, while a 'falseticker' is a clock that does not maintain standard, while a falseticker is a clock that shows misleading or
that level of timekeeping accuracy. The clustering algorithm uses inconsistent time. The cluster algorithm uses statistical principles
statistical principles to sift the most accurate truechimers leaving to sift the most accurate truechimers leaving the survivors as
the survivors as result. The combining algorithm develops the final result. The combine algorithm develops the final clock offset as a
clock offset as a statistical average of the survivors. statistical average of the survivors.
The clock discipline process, which is actually part of the system The clock discipline process, which is actually part of the system
process, includes engineered algorithms to control the time and process, includes engineered algorithms to control the time and
frequency of the system clock, here represented as a variable frequency of the system clock, here represented as a variable
frequency oscillator (VFO). Timestamps struck from the VFO close the frequency oscillator (VFO). Timestamps struck from the VFO close the
feedback loop which maintains the system clock time. Associated with feedback loop which maintains the system clock time. Associated with
the clock discipline process is the clock adjust process, which runs the clock discipline process is the clock adjust process, which runs
once each second to inject a computed time offset and maintain once each second to inject a computed time offset and maintain
constant frequency. The RMS average of past time offset differences constant frequency. The RMS average of past time offset differences
represents the nominal error or system jitter vartheta. The RMS represents the nominal error or system clock jitter. The RMS average
average of past frequency offset differences represents the of past frequency offset differences represents the oscillator
oscillator frequency stability or frequency wander cappsi. frequency stability or frequency wander. These terms are given
precise interpretation in Section 11.2.
A client sends messages to each server with a poll interval of 2^tau A client sends messages to each server with a poll interval of 2^tau
seconds, as determined by the poll exponent tau. In NTPv4 tau ranges seconds, as determined by the poll exponent tau. In NTPv4, tau
from 4 (16 s) through 17 (36 h). The value of tau is determined by ranges from 4 (16 s) through 17 (36 h). The value of tau is
the clock discipline algorithm to match the loop time constant determined by the clock discipline algorithm to match the loop time
T_c=2^tau. A server responds with messages at an update interval of constant T_c = 2^tau. In client/server mode the server responds
mu seconds. For stateless servers, mu=T_c, since the server responds immediately; however, in symmetric modes each of two peers manages
immediately. However, in symmetric modes each of two peers manages tau as a function of current system offset and system jitter, so may
the time constant as a function of current system offset and system not agree with the same value. It is important that the dynamic
jitter, so may not agree with the same tau. It is important that the behavior of the clock discipline algorithm be carefully controlled in
dynamic behavior of the clock discipline algorithms be carefully order to maintain stability in the NTP subnet at large. This
controlled in order to maintain stability in the NTP subnet at large. requires that the peers agree on a common tau equal to the minimum
This requires that the peers agree on a common tau equal to the poll exponent of both peers. The NTP protocol includes provisions to
minimum poll exponent of both peers. The NTP protocol includes properly negotiate this value.
provisions to properly negotiate this value.
While not shown in the figure, the implementation model includes some The implementation model includes some means to set and adjust the
means to set and adjust the system clock. The operating system is system clock. The operating system is assumed to provide two
assumed to provide two functions, one to set the time directly, for functions, one to set the time directly, for example the Unix
example the Unix settimeofday() function, and another to adjust the settimeofday() function, and another to adjust the time in small
time in small increments advancing or retarding the time by a increments advancing or retarding the time by a designated amount,
designated amount, for example the Unix adjtime() function for example the Unix adjtime() function. In this and following
(parentheses following a name indicate reference to a function rather references, parentheses following a name indicate reference to a
than a simple variable). In the intended design the clock discipline function rather than a simple variable. In the intended design the
process uses the adjtime() function if the adjustment is less than a clock discipline process uses the adjtime() function if the
designated threshold, and the settimeofday() function if above the adjustment is less than a designated threshold, and the
threshold. The manner in which this is done and the value of the settimeofday() function if above the threshold. The manner in which
threshold is described later. this is done and the value of the threshold as described in
Section 10.
5. Data Types 6. Data Types
All NTP time values are represented in twos-complement format, with All NTP time values are represented in twos-complement format, with
bits numbered in big-endian (as described in Appendix A of [5]) bits numbered in big-endian (as described in Appendix A of [7])
fashion from zero starting at the left, or high-order, position. 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 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 3. timestamp format and a 32-bit short format, as shown in Figure 4.
The 128-bit date format is used where sufficient storage and word The 128-bit date format is used where sufficient storage and word
size are available. It includes a 64-bit signed seconds field size are available. It includes a 64-bit signed seconds field
spanning 584 billion years and a 64-bit fraction field resolving .05 spanning 584 billion years and a 64-bit fraction field resolving .05
attosecond (i.e. 0.5e-18). For convenience in mapping between attosecond (i.e., 0.5e-18). For convenience in mapping between
formats, the seconds field is divided into a 32-bit era field and a formats, the seconds field is divided into a 32-bit Era Number field
32-bit timestamp field. Eras cannot be produced by NTP directly, nor and a 32-bit Era Offset field. Eras cannot be produced by NTP
is there need to do so. When necessary, they can be derived from directly, nor is there need to do so. When necessary, they can be
external means, such as the filesystem or dedicated hardware. derived from external means, such as the filesystem or dedicated
hardware.
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seconds | Fraction | | Seconds | Fraction |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NTP Short Format NTP Short Format
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seconds | | Seconds |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fraction | | Fraction |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NTP Timestamp Format NTP Timestamp Format
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Era Number | | Era Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Era Offset | | Era Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
skipping to change at page 14, line 32 skipping to change at page 14, line 34
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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Era Number | | Era Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Era Offset | | Era Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Fraction | | Fraction |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NTP Date Format NTP Date Format
Figure 3: NTP Time Format Figure 4: NTP Time Formats
The 64-bit timestamp format is used in packet headers and other The 64-bit timestamp format is used in packet headers and other
places with limited word size. It includes a 32-bit unsigned seconds places with limited word size. It includes a 32-bit unsigned seconds
field spanning 136 years and a 32-bit fraction field resolving 232 field spanning 136 years and a 32-bit fraction field resolving 232
picoseconds. The 32-bit short format is used in delay and dispersion picoseconds. The 32-bit short format is used in delay and dispersion
header fields where the full resolution and range of the other header fields where the full resolution and range of the other
formats are not justified. It includes a 16-bit unsigned seconds formats are not justified. It includes a 16-bit unsigned seconds
field and a 16-bit fraction field. field and a 16-bit fraction field.
In the date format the prime epoch, or base date of era 0, is 0 h 1 In the date and timestamp formats the prime epoch, or base date of
January 1900 UTC, when all bits are zero. It should be noted that era 0, is 0 h 1 January 1900 UTC, when all bits are zero. It should
strictly speaking, UTC did not exist prior to 1 January 1972, but it be noted that strictly speaking, UTC did not exist prior to 1 January
is convenient to assume it has existed for all eternity, even if all 1972, but it is convenient to assume it has existed for all eternity,
knowledge of historic leap seconds has been lost. Dates are relative even if all knowledge of historic leap seconds has been lost. Dates
to the prime epoch; values greater than zero represent times after are relative to the prime epoch; values greater than zero represent
that date; values less than zero represent times before it. times after that date; values less than zero represent times before
it. Note that the Era Offset field of the date format and the
Seconds field of the timestamp format have the same interpretation.
Timestamps are unsigned values and operations on them produce a Timestamps are unsigned values and operations on them produce a
result in the same or adjacent eras. Era 0 includes dates from the 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 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 around and the base date for era 1 is established. In either format
a value of zero is a special case representing unknown or a value of zero is a special case representing unknown or
unsynchronized time. Table 2 shows a number of historic NTP dates unsynchronized time. Figure 5 shows a number of historic NTP dates
together with their corresponding Modified Julian Day (MJD), NTP era together with their corresponding Modified Julian Day (MJD), NTP era
and NTP timestamp. and NTP timestamp.
+-------------+------------+-----+---------------+------------------+ +-------------+------------+-----+---------------+------------------+
| Year | MJD | NTP | NTP Timestamp | Epoch | | Year | MJD | NTP | NTP Timestamp | Epoch |
| | | Era | | | | | | Era | Era Offset | |
+-------------+------------+-----+---------------+------------------+ +-------------+------------+-----+---------------+------------------+
| 1 Jan -4712 | -2,400,001 | -49 | 1,795,583,104 | 1st day Julian | | 1 Jan -4712 | -2,400,001 | -49 | 1,795,583,104 | 1st day Julian |
| 1 Jan -1 | -679,306 | -14 | 139,775,744 | 2 BCE | | 1 Jan -1 | -679,306 | -14 | 139,775,744 | 2 BCE |
| 1 Jan 0 | -678,491 | -14 | 171,311,744 | 1 BCE | | 1 Jan 0 | -678,491 | -14 | 171,311,744 | 1 BCE |
| 1 Jan 1 | -678,575 | -14 | 202,939,144 | 1 CE | | 1 Jan 1 | -678,575 | -14 | 202,939,144 | 1 CE |
| 4 Oct 1582 | -100,851 | -3 | 2,873,647,488 | Last day Julian | | 4 Oct 1582 | -100,851 | -3 | 2,873,647,488 | Last day Julian |
| 15 Oct 1582 | -100,840 | -3 | 2,874,597,888 | First day | | 15 Oct 1582 | -100,840 | -3 | 2,874,597,888 | First day |
| | | | | Gregorian | | | | | | Gregorian |
| 31 Dec 1899 | 15019 | -1 | 4,294,880,896 | Last day NTP Era | | 31 Dec 1899 | 15019 | -1 | 4,294,880,896 | Last day NTP Era |
| | | | | -1 | | | | | | -1 |
| 1 Jan 1900 | 15020 | 0 | 0 | First day NTP | | 1 Jan 1900 | 15020 | 0 | 0 | First day NTP |
| | | | | Era 0 | | | | | | Era 0 |
| 1 Jan 1970 | 40,587 | 0 | 2,208,988,800 | First day UNIX | | 1 Jan 1970 | 40,587 | 0 | 2,208,988,800 | First day UNIX |
| 1 Jan 1972 | 41,317 | 0 | 2,272,060,800 | First day UTC | | 1 Jan 1972 | 41,317 | 0 | 2,272,060,800 | First day UTC |
| 31 Dec 1999 | 51,543 | 0 | 3,155,587,200 | Last day 20th | | 31 Dec 1999 | 51,543 | 0 | 3,155,587,200 | Last day 20th |
| | | | | Century | | | | | | Century |
| 8 Feb 2036 | 64,731 | 1 | 63,104 | First day NTP | | 8 Feb 2036 | 64,731 | 1 | 63,104 | First day NTP |
| | | | | Era 1 | | | | | | Era 1 |
+-------------+------------+-----+---------------+------------------+ +-------------+------------+-----+---------------+------------------+
Table 2: Interesting Historic NTP Dates Figure 5: Interesting Historic NTP Dates
Let p be the number of significant bits in the second fraction. The Let p be the number of significant bits in the second fraction. The
clock resolution is defined 2^(-p), in seconds. In order to minimize clock resolution is defined 2^(-p), in seconds. In order to minimize
bias and help make timestamps unpredictable to an intruder, the non- bias and help make timestamps unpredictable to an intruder, the non-
significant bits should be set to an unbiased random bit string. The significant bits should be set to an unbiased random bit string. The
clock precision is defined as the running time to read the system clock precision is defined as the running time to read the system
clock, in seconds. Note that the precision defined in this way can clock, in seconds. Note that the precision defined in this way can
be larger or smaller than the resolution. The term rho, representing be larger or smaller than the resolution. The term rho, representing
the precision used in this document, is the larger of the two. the precision used in the protocol, is the larger of the two.
The only operation permitted with dates and timestamps is twos- The only arithmetic operation permitted on dates and timestamps is
complement subtraction, yielding a 127-bit or 63-bit signed result. twos-complement subtraction, yielding a 127-bit or 63-bit signed
It is critical that the first-order differences between two dates result. It is critical that the first-order differences between two
preserve the full 128-bit precision and the first-order differences dates preserve the full 128-bit precision and the first-order
between two timestamps preserve the full 64-bit precision. However, differences between two timestamps preserve the full 64-bit
the differences are ordinarily small compared to the seconds span, so precision. However, the differences are ordinarily small compared to
they can be converted to floating double format for further the seconds span, so they can be converted to floating double format
processing and without compromising the precision. for further processing and without compromising the precision.
It is important to note that twos-complement arithmetic does not know It is important to note that twos-complement arithmetic does not know
the difference between signed and unsigned values; only the the difference between signed and unsigned values; only the
conditional branch instructions. Thus, although the distinction is conditional branch instructions do. Thus, although the distinction
made between signed dates and unsigned timestamps, they are processed is made between signed dates and unsigned timestamps, they are
the same way. A perceived hazard with 64-bit timestamp calculations processed the same way. A perceived hazard with 64-bit timestamp
spanning an era, such as possible in 2036, might result in incorrect calculations spanning an era, such as possible in 2036, might result
values. In point of fact, if the client is set within 68 years of in incorrect values. In point of fact, if the client is set within
the server before the protocol is started, correct values are 68 years of the server before the protocol is started, correct values
obtained even if the client and server are in adjacent eras. are obtained even if the client and server are in adjacent eras.
Some time values are represented in exponent format, including the Some time values are represented in exponent format, including the
precision, time constant and poll interval values. These are in precision, time constant and poll interval. These are in 8-bit
8-bit signed integer format in log2 (log to the base 2) seconds. signed integer format in log2 (log to the base 2) seconds. The only
arithmetic operations permitted on them are increment and decrement.
The only operations permitted on them are increment and decrement.
For the purpose of this document and to simplify the presentation, a For the purpose of this document and to simplify the presentation, a
reference to one of these state variables by name means the reference to one of these variables by name means the exponentiated
exponentiated value, e.g., the poll interval is 1024 s, while value, e.g., the poll interval is 1024 s, while reference by name and
reference by name and exponent means the actual value, e.g., the poll exponent means the actual value, e.g., the poll exponent is 10.
exponent is 10.
To convert system time in any format to NTP date and timestamp 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 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 system time be determined. To determine the integer era and
the timestamp the integer remainder as in: timestamp given s,
era = s / 2^(32) and timestamp = s - era*2^(32) era = s / 2^(32) and timestamp = s - era * 2^(32),
which works for positive and negative dates. To convert from NTP era which works for positive and negative dates. To determine s given
and timestamp to system time requires the calculation the era and timestamp,
s = era*2^(32) + timestamp s = era * 2^(32) + timestamp.
to determine the number of seconds since the prime epoch. Converting Converting between NTP and system time can be a little messy, but
between NTP and system time can be a little messy, but beyond the beyond the scope of this document. Note that the number of days in
scope of this document. Note that the number of days in era 0 is one era 0 is one more than the number of days in most other eras and this
more than the number of days in most other eras and this won't happen won't happen again until the year 2400 in era 3.
again until the year 2400 in era 3.
In the description of state variables to follow, explicit reference In the description of state variables to follow, explicit reference
to integer type implies a 32-bit unsigned integer. This simplifies to integer type implies a 32-bit unsigned integer. This simplifies
bounds checks, since only the upper limit needs to be defined. bounds checks, since only the upper limit needs to be defined.
Without explicit reference, the default type is 64-bit floating Without explicit reference, the default type is 64-bit floating
double. Exceptions will be noted as necessary. double. Exceptions will be noted as necessary.
6. Data Structures 7. Data Structures
The NTP protocol state machines described in following sections are The NTP protocol state machines described in following sections are
defined using state variables and flow chart fragments. State defined using state variables and code fragments defined in
variables are separated into classes according to their function in Appendix A. State variables are separated into classes according to
packet headers, peer and poll processes, the system process and the their function in packet headers, peer and poll processes, the system
clock discipline process. Packet variables represent the NTP header process and the clock discipline process. Packet variables represent
values in transmitted and received packets. Peer and poll variables the NTP header values in transmitted and received packets. Peer and
represent the contents of the association for each server separately. poll variables represent the contents of the association for each
System variables represent the state of the server as seen by its server separately. System variables represent the state of the
dependent clients. Clock discipline variables represent the internal server as seen by its dependent clients. Clock discipline variables
workings of the clock discipline algorithm. Additional constant and represent the internal workings of the clock discipline algorithm.
variable classes are defined in Appendix A. Additional parameters and variable classes are defined in Appendix A.
6.1. Structure Conventions 7.1. Structure Conventions
In order to distinguish between different variables of the same name In order to distinguish between different variables of the same name
but used in different processes, the naming convention summarized in but used in different processes, the naming convention summarized in
Table 3 is employed. A receive packet variable v is a member of the Figure 6 is adopted. A receive packet variable v is a member of the
packet structure r with fully qualified name r.v. In a similar 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 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 system variable and c.v is a clock discipline variable. There
is a set of peer variables for each association; there is only one is a set of peer variables for each association; there is only one
set of system and clock variables. Most flow chart fragments begin set of system and clock variables.
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.
+------+---------------------------------+ +------+---------------------------------+
| Name | Description | | Name | Description |
+------+---------------------------------+ +------+---------------------------------+
| r. | receive packet header variable | | r. | receive packet header variable |
| x. | transmit packet header variable | | x. | transmit packet header variable |
| p. | peer/poll variable | | p. | peer/poll variable |
| s. | system variable | | s. | system variable |
| c. | clock discipline variable | | c. | clock discipline variable |
+------+---------------------------------+ +------+---------------------------------+
Table 3: Name Prefix Conventions Figure 6: Prefix Conventions
6.2. Global Parameters 7.2. Global Parameters
In addition to the variable classes a number of global parameters are In addition to the variable classes a number of global parameters are
defined in this document, including those shown with values in defined in this document, including those shown with values in
Table 4. Figure 7.
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
| Name | Value | Description | | Name | Value | Description |
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
| PORT | 123 | NTP port number | | PORT | 123 | NTP port number |
| VERSION | 4 | version number | | VERSION | 4 | version number |
| TOLERANCE | 15e-6 | frequency tolerance (s/s) | | TOLERANCE | 15e-6 | frequency tolerance PHI (s/s) |
| MINPOLL | 4 | minimum poll exponent (16 s) | | MINPOLL | 4 | minimum poll exponent (16 s) |
| MAXPOLL | 17 | maximum poll exponent (36 h) | | MAXPOLL | 17 | maximum poll exponent (36 h) |
| MAXDISP | 16 | maximum dispersion (s) | | MAXDISP | 16 | maximum dispersion (16 s) |
| MINDISP | .005 | minimum dispersion increment (s) | | MINDISP | .005 | minimum dispersion increment (s) |
| MAXDIST | 1 | distance threshold (s) | | MAXDIST | 1 | distance threshold (1 s) |
| MAXSTRAT | 16 | maximum stratum number | | MAXSTRAT | 16 | maximum stratum number |
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
Table 4: Global Parameters Figure 7: Global Parameters
While these are the only parameters needed in this document, a larger While these are the only global parameters needed in this document, a
collection is necessary in the skeleton and larger still for any larger collection is necessary in the skeleton and larger still for
implementation. Appendix A.1.1 contains those used by the skeleton any implementation. Appendix A.1.1 contains those used by the
for the mitigation algorithms, clock discipline algorithm and related skeleton for the mitigation algorithms, clock discipline algorithm
implementation-dependent functions. Some of these parameter values and related implementation-dependent functions. Some of these
are cast in stone, like the NTP port number assigned by the IANA and parameter values are cast in stone, like the NTP port number assigned
the version number assigned NTPv4 itself. Others like the frequency by the IANA and the version number assigned NTPv4 itself. Others
tolerance, involve an assumption about the worst case behavior of a like the frequency tolerance (also called PHI), involve an assumption
system clock once synchronized and then allowed to drift when its about the worst case behavior of a system clock once synchronized and
sources have become unreachable. The minimum and maximum parameters then allowed to drift when its sources have become unreachable. The
define the limits of state variables as described in later sections. 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 While shown with fixed values in this document, some implementations
may make them variables adjustable by configuration commands. For may make them variables adjustable by configuration commands. For
instance, the reference implementation computes the value of instance, the reference implementation computes the value of
PRECISION as log2 of the minimum time in several iterations to read PRECISION as log2 of the minimum time in several iterations to read
the system clock. the system clock.
6.3. Packet Header Variables 7.3. Packet Header Variables
The most important state variables from an external point of view are
the packet header variables described in Figure 8 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 [3]. The optional MAC is used
by both Autokey and the symmetric key cryptographic algorithm
described in report.
+-----------+------------+-----------------------+ +-----------+------------+-----------------------+
| Name | Formula | Description | | Name | Formula | Description |
+-----------+------------+-----------------------+ +-----------+------------+-----------------------+
| leap | leap | leap indicator (LI) | | leap | leap | leap indicator (LI) |
| version | version | version number (VN) | | version | version | version number (VN) |
| mode | mode | mode | | mode | mode | mode |
| stratum | stratum | stratum | | stratum | stratum | stratum |
| poll | poll | poll exponent | | poll | poll | poll exponent |
| precision | rho | precision exponent | | precision | rho | precision exponent |
| rootdelay | delta | root delay | | rootdelay | delta_r | root delay |
| rootdisp | capepsilon | root dispersion | | rootdisp | epsilon_r | root dispersion |
| refid | refid | reference ID | | refid | refid | reference ID |
| reftime | reftime | reference timestamp | | reftime | reftime | reference timestamp |
| org | T1 | origin timestamp | | org | T1 | origin timestamp |
| rec | T2 | receive timestamp | | rec | T2 | receive timestamp |
| xmt | T3 | transmit timestamp | | xmt | T3 | transmit timestamp |
| dst | T4 | destination timestamp | | dst | T4 | destination timestamp |
| keyid | keyid | key ID | | keyid | keyid | key ID |
| digest | digest | message digest | | digest | digest | message digest |
+-----------+------------+-----------------------+ +-----------+------------+-----------------------+
Table 5: Packet Header Variables Figure 8: Packet Header Variables
The most important state variables from an external point of view are
the packet header variables described below. The NTP packet consists
of a 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 [3]. The
optional MAC is used by both Autokey and the symmetric key
cryptographic algorithms described in the main body of this report.
The NTP packet header follows the UDP and IP headers and the physical The NTP packet header follows the UDP and IP headers and the physical
header specific to the underlying transport network. It consists of header specific to the underlying transport network. Some fields use
a number of 32-bit (4-octet) words, although some fields use multiple multiple words and others are packed in smaller fields within a word.
words and others are packed in smaller fields within a word. The NTP The NTP packet header shown in Figure 9 has 12 words followed by
packet header shown in Figure 4 has 12 words followed by optional optional extension fields and finally an optional message
extension fields and finally an optional message authentication code authentication code (MAC) consisting of the key identifier field and
(MAC) consisting of the key identifier and message digest fields. message digest field.
The optional extension fields described in this section 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 NTP
header is shown in Figure 4 , where the size of some multiple-word
fields is shown in bits if not the default 32 bits. The header
extends from the beginning of the packet to the end of the Transmit
Timestamp field. When using the IPv4 address family these fields are
backwards compatible with NTPv3. 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. The message authentication code (MAC) consists of a 32-bit
Key Identifier followed by a 128bit Message Digest. The message
digest, or cryptosum, is calculated as in [6] over all header and
optional extension fields.
0 1 2 3 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 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 | Strat | Poll | Prec | |LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay | | Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion | | Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference ID | | Reference ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Reference Timestamp + + Reference Timestamp (64) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Origin Timestamp + + Origin Timestamp (64) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Receive Timestamp + + Receive Timestamp (64) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Transmit Timestamp + + Transmit Timestamp (64) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Extension Field 1 (Optional) + + Extension Field 1 (variable) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Extension Field 2 (Optional) + + Extension Field 2 (variable) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . | Key Identifier |
. Authentication . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. (Optional) (160 bits) . | |
. . | Message Digest (128) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: NTPv4 Message Format Figure 9: Packet Header Format
The variables are interpreted as follows: The extension fields are used to add optional capabilities, for
example, the Autokey security protocol [3]. The extension field
format is presented in order that the packet can be parsed without
knowledge of the extension field functions. The MAC is used by both
Autokey and the symmetric key authentication scheme described in
Appendix A.
leap: 2-bit integer warning of an impending leap second to be A list of the packet header variables is shown in Figure 8 and
inserted or deleted in the last minute of the current month, coded as described in detail below. Except for a minor variation when using
follows: 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 9 the size of
some multiple-word fields is shown in bits if not the default 32
bits. The 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 10.
+-------+-------------------------------------------------+ +-------+-------------------------------------------------+
| Value | Meaning | | Value | Meaning |
+-------+-------------------------------------------------+ +-------+-------------------------------------------------+
| 0 | no warning | | 0 | no warning |
| 1 | last minute of the day has 61 seconds | | 1 | last minute of the day has 61 seconds |
| 2 | last minute of the day has 59 seconds | | 2 | last minute of the day has 59 seconds |
| 3 | alarm condition (the clock is not synchronized) | | 3 | alarm condition (the clock is not synchronized) |
+-------+-------------------------------------------------+ +-------+-------------------------------------------------+
Table 6: Leap Indicator Figure 10: Leap Indicator
version: 3-bit integer representing the NTP version number, currently VN Version Number (version): 3-bit integer representing the NTP
4. version number, currently 4.
mode: 3-bit integer representing the mode, with values defined as Mode (mode): 3-bit integer representing the mode, with values defined
follows: in Figure 11.
+-------+--------------------------+ +-------+--------------------------+
| Value | Meaning | | Value | Meaning |
+-------+--------------------------+ +-------+--------------------------+
| 0 | reserved | | 0 | reserved |
| 1 | symmetric active | | 1 | symmetric active |
| 2 | symmetric passive | | 2 | symmetric passive |
| 3 | client | | 3 | client |
| 4 | server | | 4 | server |
| 5 | broadcast | | 5 | broadcast |
| 6 | NTP control message | | 6 | NTP control message |
| 7 | reserved for private use | | 7 | reserved for private use |
+-------+--------------------------+ +-------+--------------------------+
Table 7: Mode Figure 11: Association Modes
stratum: 8-bit integer representing the stratum, with values defined Stratum (stratum): 8-bit integer representing the stratum, with
as follows: values defined in Figure 12.
+--------+-----------------------------------------------------+ +--------+-----------------------------------------------------+
| Value | Meaning | | Value | Meaning |
+--------+-----------------------------------------------------+ +--------+-----------------------------------------------------+
| 0 | unspecified or invalid | | 0 | unspecified or invalid |
| 1 | primary server (e.g., equipped with a GPS receiver) | | 1 | primary server (e.g., equipped with a GPS receiver) |
| 2-15 | secondary server (via NTP) | | 2-15 | secondary server (via NTP) |
| 16 | client-only | | 16-255 | undefined |
| 17-255 | undefined |
+--------+-----------------------------------------------------+ +--------+-----------------------------------------------------+
Table 8: Stratum Figure 12: Packet Stratum
It is customary to map the stratum value 0 in received packets to 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 MAXSTRAT (16) in the peer variable p.stratum and to map p.stratum
values of MAXSTRAT or greater to 0 in transmitted packets. This values of MAXSTRAT or greater to 0 in transmitted packets. This
allows reference clocks, which normally appear at stratum 0, to be allows reference clocks, which normally appear at stratum 0, to be
conveniently mitigated using the same algorithms used for external conveniently mitigated using the same algorithms used for external
sources. sources.
poll: 8-bit signed integer representing the maximum interval between Poll: 8-bit signed integer representing the maximum interval between
successive messages, in log2 seconds. Suggested default limits for successive messages, in log2 seconds. Suggested default limits for
minimum and maximum poll intervals are 6 and 10, respectively. minimum and maximum poll intervals are 6 and 10, respectively.
precision: 8-bit signed integer representing the precision of the Precision: 8-bit signed integer representing the precision of the
system clock, in log2 seconds. For instance a value of -18 system clock, in log2 seconds. For instance a value of -18
corresponds to a precision of about one microsecond. The precision corresponds to a precision of about one microsecond. The precision
can be determined when the service first starts up as the minimum can be determined when the service first starts up as the minimum
time of several iterations to read the system clock. time of several iterations to read the system clock.
rootdelay: Total roundtrip delay to the reference clock, in NTP short Root Delay (rootdelay): Total round trip delay to the reference
format. clock, in NTP short format.
rootdisp: Total dispersion to the reference clock, in NTP short Root Dispersion (rootdisp): Total dispersion to the reference clock,
format. in NTP short format.
refid: 32-bit code identifying the particular server or reference Reference ID (refid): 32-bit code identifying the particular server
clock. The interpretation depends on the value in the stratum field. or reference clock. The interpretation depends on the value in the
For packet stratum 0 (unspecified or invalid) this is a four- stratum field. For packet stratum 0 (unspecified or invalid) this is
character ASCII string, called the kiss code, used for debugging and a four-character ASCII string, called the kiss code, used for
monitoring purposes. For stratum 1 (reference clock) this is a four- debugging and monitoring purposes. For stratum 1 (reference clock)
octet, left-justified, zero-padded ASCII string assigned to the this is a four-octet, left-justified, zero-padded ASCII string
reference clock. While not specifically enumerated in this document, assigned to the reference clock. While not specifically enumerated
the following have been used as ASCII identifiers: in this document, the identifiers in Figure 13 have been used as
ASCII identifiers:
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
| ID | Clock Source | | ID | Clock Source |
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
| GOES | Geosynchronous Orbit Environment Satellite | | GOES | Geosynchronous Orbit Environment Satellite |
| GPS | Global Position System | | GPS | Global Position System |
| GAL | Galileo Positioning System | | GAL | Galileo Positioning System |
| PPS | Generic pulse-per-second | | PPS | Generic pulse-per-second |
| IRIG | Inter-Range Instrumentation Group | | IRIG | Inter-Range Instrumentation Group |
| WWVB | LF Radio WWVB Ft. Collins, CO 60 kHz | | WWVB | LF Radio WWVB Ft. Collins, CO 60 kHz |
skipping to change at page 24, line 29 skipping to change at page 23, line 42
| TDF | MF Radio Allouis, FR 162 kHz | | TDF | MF Radio Allouis, FR 162 kHz |
| CHU | HF Radio CHU Ottawa, Ontario | | CHU | HF Radio CHU Ottawa, Ontario |
| WWV | HF Radio WWV Ft. Collins, CO | | WWV | HF Radio WWV Ft. Collins, CO |
| WWVH | HF Radio WWVH Kauai, HI | | WWVH | HF Radio WWVH Kauai, HI |
| NIST | NIST telephone modem | | NIST | NIST telephone modem |
| ACTS | NIST telephone modem | | ACTS | NIST telephone modem |
| USNO | USNO telephone modem | | USNO | USNO telephone modem |
| PTB | European telephone modem | | PTB | European telephone modem |
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
Table 9: Reference IDs Figure 13: Reference Identifiers
Above stratum 1 (secondary servers and clients) this is the reference Above stratum 1 (secondary servers and clients) this is the reference
identifier of the server. If using the IPv4 address family, the identifier of the server and is intended to detect timing loops. If
identifier is the four-octet IPv4 address. If using the IPv6 address using the IPv4 address family, the identifier is the four-octet IPv4
family, it is the first four octets of the MD5 hash of the IPv6 address. If using the IPv6 address family, it is the first four
address. 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.
reftime: Time when the system clock was last set or corrected, in NTP Reference Timestamp: Time when the system clock was last set or
timestamp format. corrected, in NTP timestamp format.
org: Time at the client when the request departed for the server, in Origin Timestamp (org): Time at the client when the request departed
NTP timestamp format. for the server, in NTP timestamp format.
rec: Time at the server when the request arrived from the client, in Receive Timestamp (rec): Time at the server when the request arrived
NTP timestamp format. from the client, in NTP timestamp format.
xmt: Time at the server when the response left for the client, in NTP Transmit Timestamp (xmt): Time at the server when the response left
timestamp format. for the client, in NTP timestamp format.
dst: Time at the client when the reply arrived from the server, in Destination Timestamp (dst): Time at the client when the reply
NTP timestamp format. Note: This value is not included in a header arrived from the server, in NTP timestamp format.
field; it is determined upon arrival of the packet and made available
in the packet buffer data structure.
keyid: 32-bit unsigned integer used by the client and server to Note: Destination Timestamp field is not included as a header field;
designate a secret 128-bit MD5 key. Together, the keyid and digest it is determined upon arrival of the packet and made available in the
fields collectively are called message authentication code (MAC). packet buffer data structure.
digest: 128-bit bitstring computed by the keyed MD5 message digest The MAC consists of the Key Identifier followed by the Message
algorithm described in Appendix A. Digest. The message digest, or cryptosum, is calculated as in [8]
over all header and optional extension fields, but not the MAC
itself.
6.3.1. The Kiss-o'-Death Packet Key Identifier (keyid): 32-bit unsigned integer used by the client
and server to designate a secret 128-bit MD5 key.
If the Stratum field is 0, which is an 'unspecified' Stratum field Message Digest (digest): 128-bit bitstring computed by the keyed MD5
value, the Reference Identifier field can be used to convey messages message digest computed over all the words in the header and
useful for status reporting and access control. In NTPv4 and SNTPv4, extension fields, but not the MAC itself.
packets of this kind are called Kiss-o'-Death (KoD) packets and the
ASCII messages they convey are called kiss codes. The KoD packets 7.4. The Kiss-o'-Death Packet
got their name because an early use was to tell clients to stop
sending packets that violate server access controls. The kiss codes If the Stratum field is 0, which implies unspecified or invalid, the
can provide useful information for an intelligent client. These Reference Identifier field can be used to convey messages useful for
codes are encoded in four-character ASCII strings left justified and status reporting and access control. These are called Kiss-o'-Death
zero filled. The strings are designed for character displays and log (KoD) packets and the ASCII messages they convey are called kiss
files. A list of the currently-defined kiss codes is given below: 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 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 14. Other than
displaying the kiss code, KoD packets have no protocol significance
and are discarded after inspection.
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
| Code | Meaning | | Code | Meaning |
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
| ACST | The association belongs to a unicast server | | ACST | The association belongs to a unicast server |
| AUTH | Server authentication failed | | AUTH | Server authentication failed |
| AUTO | Autokey sequence failed | | AUTO | Autokey sequence failed |
| BCST | The association belongs to a broadcast server | | BCST | The association belongs to a broadcast server |
| CRYP | Cryptographic authentication or identification failed | | CRYP | Cryptographic authentication or identification failed |
| DENY | Access denied by remote server | | DENY | Access denied by remote server |
skipping to change at page 25, line 50 skipping to change at page 25, line 29
| NKEY | No key found. Either the key was never installed or is | | NKEY | No key found. Either the key was never installed or is |
| | not trusted | | | not trusted |
| RATE | Rate exceeded. The server has temporarily denied access | | RATE | Rate exceeded. The server has temporarily denied access |
| | because the client exceeded the rate threshold | | | because the client exceeded the rate threshold |
| RMOT | Alteration of association from a remote host running | | RMOT | Alteration of association from a remote host running |
| | ntpdc. | | | ntpdc. |
| STEP | A step change in system time has occurred, but the | | STEP | A step change in system time has occurred, but the |
| | association has not yet resynchronized | | | association has not yet resynchronized |
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
Table 10: Currently-defined NTP Kiss Codes Figure 14: Kiss Codes
6.3.2. NTP Extension Field Format 7.5. NTP Extension Field Format
In NTPv4 one or more extension fields can be inserted after the In NTPv4 one or more extension fields can be inserted after the
header and before the MAC, which is always present when extension header and before the MAC, which is always present when an extension
fields are present. The extension fields can occur in any order; field is present. Other than defining the field format, this
however, in some cases there is a preferred order which improves the document makes no use of the field contents. An extension field
protocol efficiency. contains a request or response message in the format shown in
Figure 15.
An extension field contains a request or response message in the
format shown in Figure 5.
0 1 2 3 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 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 | | Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID | | Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp | | Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp | | Filestamp |
skipping to change at page 26, line 41 skipping to change at page 26, line 31
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature Length | | Signature Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . .
. Signature . . Signature .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Padding (as needed) | | Padding (as needed) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: NTP Extension Field Format Figure 15: Extension Field Format
All extension fields are zero-padded to a word (4 octets) boundary.
The Length field covers the entire extension field, including the
Length and Padding fields. While the minimum field length is 4 words
(16 octets), a maximum field length remains to be established.
The RE, VN, and Code fields together form a Field Type field, a 16- All extension fields are zero-padded to a word (4 octets) boundary
bit integer which indicates the type of extension message contained and the last is padded to a 64-bit (8 octet) boundary. The Field
within the extension field. Type field is specific to the defined function and is not elaborated
here. While the minimum field length containing required fields is 4
words (16 octets), a maximum field length remains to be established.
The Length field is a 16-bit integer which indicates the length of The Length field is a 16-bit integer which indicates the length of
the entire extension field in octets, including the Length and the entire extension field in octets, including the Padding field.
Padding fields.
The 32-bit Association ID field is set by clients to the value The 32-bit Association ID field is set by clients to the value
previously received from the server or 0 otherwise. The server sets previously received from the server or 0 otherwise. The server sets
the Association ID field when sending a response as a handle for the Association ID field when sending a response as a handle for
subsequent exchanges. If the association ID value in a request does subsequent exchanges.
not match the association ID of any association, the server returns
the request with the first two bits of the Field Type field set to 1.
The Timestamp and Filestamp 32-bit fields carry the seconds field of The Timestamp and Filestamp 32-bit fields carry the seconds field of
an NTP timestamp. The Timestamp field establishes the signature an NTP timestamp. The Timestamp field establishes the signature
epoch of the data field in the message, while the filestamp epoch of the data in the extension field, while the filestamp
establishes the generation epoch of the file that ultimately produced establishes the generation epoch of the file that ultimately produced
the data. the data.
The 32-bit Value Length field indicates the length of the Value field The 32-bit Value Length field indicates the length of the Value field
in octets. The minimum length of the Value field is 0, in which case in octets. The minimum length of this field is 0, in which case the
the Value field is omitted. Value field itself is omitted.
The 32-bit Value Length field indicates the length of the Value field The 32-bit Signature Length field indicates the length of the
in octets. The minimum length of the Value field is 0. Signature field in octets. The minimum length of this field is 0.
In which case the Signature field itself is omitted.
Zero padding is applied, as necessary, to extend the extension field If both the Value Length and Signature Length fields are 0, both of
to a word (4-octet) boundary. If multiple extension fields are these words can be omitted, in which case the extension field has
present, the last extension field is zero-padded to a double-word (8 length 4 words.
octet) boundary.
The presence of the MAC and extension fields in the packet is The presence of the MAC and extension fields in the packet is
determined from the length of the remaining area after the header to determined from the length of the remaining area after the header to
the end of the packet. The parser initializes a pointer just after the end of the packet. The parser initializes a pointer just after
the header. If the Length field is not a multiple of 4, a format the header. If the Length field is not a multiple of 4, a format
error has occurred and the packet is discarded. The following cases error has occurred and the packet is discarded. The following cases
are possible based on the remaining length in words. are possible based on the remaining length in words.
0 The packet is not authenticated. 0 The packet contains no MAC and is not authenticated.
1 The packet is an error report or crypto-NAK. 1 The packet is an error report or crypto-NAK.
2, 3, 4 The packet is discarded with a format error. 2, 3, 4 The packet is discarded with a format error.
5 The remainder of the packet is the MAC. 5 The remainder of the packet is the 160-bit MAC.
>5 One or more extension fields are present. >5 One or more extension fields are present.
If an extension field is present, the parser examines the Length If an extension field is present, the parser examines the Length
field. If the length is less than 4 or not a multiple of 4, a format field. If the length is less than 4 or not a multiple of 4, a format
error has occurred and the packet is discarded; otherwise, the parser error has occurred and the packet is discarded; otherwise, the parser
increments the pointer by this value. The parser now uses the same increments the pointer by this value. The parser now uses the same
rules as above to determine whether a MAC is present and/or another rules as above to determine whether a MAC is present and/or another
extension field. An additional implementation dependent test is extension field. An additional implementation dependent test is
necessary to ensure the pointer does not stray outside the buffer necessary to ensure the pointer does not stray outside the buffer
space occupied by the packet. space occupied by the packet.
7. On Wire Protocol 8. On Wire Protocol
The heart of the NTP on-wire protocol is the core mechanism which
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, 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.
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
to mean 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 prefix determined by scoping rules.
The on-wire protocol uses four timestamps numbered T1 through T4 and
three state variables org, rec and xmt, as shown in Figure 17. 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 a number indicating the order of
transmission and reception.
t2 t3 t6 t7 t2 t3 t6 t7
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T1 | 0 | | t2 | | t4 | | t6 | T1 | 0 | | t1 | | t3 | | t5 |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T2 | 0 | | t1 | | t3 | | t5 | Packet T2 | 0 | | t2 | | t4 | | t6 | Packet
+---------+ +---------+ +---------+ +---------+ Variables +---------+ +---------+ +---------+ +---------+ Variables
T3 |t2=clock | | t2 | |t6=clock | | t6 | T3 | t1 | |t3=clock | | t5 | |t7=clock |
+---------+ +---------+ +---------+ +---------+
T4 | t1 | |t3=clock | | t5 | |t7=clock |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T4 |t2=clock | |t6=clock |
+---------+ +---------+
Peer B Peer B
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
org | t1 | | t1 | | T3<>t1? | | t5 | org | t1 | | t1 | | T3<>t1? | | t5 |
+---------+ +---------+ +---------+ +---------+ State +---------+ +---------+ +---------+ +---------+ State
rec | t2 | | t2 | | t6 | | t6 | Variables rec | t2 | | t2 | | t6 | | t6 | Variables
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
xmt | 0 | | t3 | | T1<>t3? | | t7 | xmt | 0 | | t3 | | T1<>t3? | | t7 |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
t2 t3 t6 t7 t2 t3 t6 t7
--------------------------------------------------------- ---------------------------------------------------------
/\ \ /\ \ /\ \ /\ \
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \/ / \/ / \/ / \/
--------------------------------------------------------- ---------------------------------------------------------
t1 t4 t5 t8 t1 t4 t5 t8
t1 t4 t5 t8 t1 t4 t5 t8
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T1 | 0 | | t2 | | t4 | | t6 | T1 | 0 | | t1 | | t3 | | t5 |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T2 | 0 | | t1 | | t3 | | t5 | Packet T2 | 0 | | t2 | | t4 | | t6 | Packet
+---------+ +---------+ +---------+ +---------+ Variables +---------+ +---------+ +---------+ +---------+ Variables
T3 | 0 | |t4=clock | | t4 | |t8=clock | T3 |t1=clock | | t3 | |t5=clock | | t7 |
+---------+ +---------+ +---------+ +---------+
T4 |t1=clock | | t3 | |t5=clock | | t7 |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
T4 |t4=clock | |t8=clock |
+---------+ +---------+
Peer A Peer A
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
org | 0 | | T3<>0? | | t3 | | T3<>t3? | org | 0 | | T3<>0? | | t3 | | T3<>t3? |
+---------+ +---------+ +---------+ +---------+ State +---------+ +---------+ +---------+ +---------+ State
rec | 0 | | t4 | | t4 | | t8 | Variables rec | 0 | | t4 | | t4 | | t8 | Variables
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
xmt | t1 | | T1=t1? | | t5 | | T1<>t5? | xmt | t1 | | T1=t1? | | t5 | | T1<>t5? |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
Figure 7: On-Wire Protocol Figure 17: On-Wire Protocol
The NTP on-wire protocol is the core mechanism to exchange time In the figure the first packet transmitted by A contains only the
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.
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
to mean 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 prefix determined by scoping rules.
The on-wire protocol uses four timestamps numbered T1 through T4 and
three state variables org, rec and xmt, as shown in Figure 7. 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 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 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 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 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 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 the transmit timestamp T3 with value t3, which is saved in the xmt
state variable. When this packet arrives at A the packet header state variable. When this packet arrives at A the packet header
variables T1, T2, T3 and destination timestamp T4 represent the four variables T1, T2, T3 and destination timestamp T4 represent the four
timestamps necessary to compute the offset and delay of B relative to timestamps necessary to compute the offset and delay of B relative to
A, as described later. A, as described below.
Before the A state variables are updated, two sanity checks are Before the A state variables are updated, two sanity checks are
performed in order to protect against duplicate or bogus packets. A performed in order to protect against duplicate or bogus packets. A
packet is a duplicate if the transmit timestamp T3 in the packet packet is a duplicate if the transmit timestamp T3 in the packet
matches the xmt state variable. A packet is bogus if the origin 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 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 either of these cases the state variables are updated, then the
is discarded. packet is discarded.
The four most recent timestamps, T1 through T4, are used to compute The four most recent timestamps, T1 through T4, are used to compute
the offset of B relative to A the offset of B relative to A
theta = T(B) - T(A) = 1/2*(T2-T1)+(T4-T3) theta = T(B) - T(A) = 1/2 * [(T2-T1) + (T4-T3)]
and the roundtrip delay and the roundtrip delay
delta = T(ABA)- = (T4-T1)-(T3-T2) delta = T(ABA) = (T4-T1) - (T3-T2).
Note that the quantities within parentheses are computed from 64-bit Note that the quantities within parentheses are computed from 64-bit
unsigned timestamps and result in signed values with 63 significant unsigned timestamps and result in signed values with 63 significant
bits plus sign. These values can represent dates from 68 years in 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 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 are computed as sums and differences of these values, which contain
62 significant bits and two sign bits, so can represent unambiguous 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 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 words, the time of the client must be set within 34 years of the
server before the service is started. This is a fundamental server before the service is started. This is a fundamental
limitation with 64-bit integer arithmetic. limitation with 64-bit integer arithmetic.
In implementations where floating double arithmetic is available, the In implementations where floating double arithmetic is available, the
first-order differences can be converted to floating double and the first-order differences can be converted to floating double and the
second-order sums and differences computed in that arithmetic. Since second-order sums and differences computed in that arithmetic. Since
the second-order terms are typically very small relative to the the second-order terms are typically very small relative to the
timestamps themselves, there is no loss in significance, yet the timestamp magnitudes, there is no loss in significance, yet the
unambiguous range is increased from 34 years to 68 years. unambiguous range is restored from 34 years to 68 years.
In some scenarios where the frequency offset between the client and In some scenarios where the initial frequency offset of the client is
server is relatively large and the actual propagation time small, it relatively large and the actual propagation time small, it is
is possible that the delay computation becomes negative. For possible that the delay computation becomes negative. For instance,
instance, if the frequency difference is 100 PPM and the interval if the frequency difference is 100 PPM and the interval T4-T1 is 64
T4-T1 is 64 s, the apparent delay is -6.4 ms. Since negative values s, the apparent delay is -6.4 ms. Since negative values are
are misleading in subsequent computations, the value of del should be misleading in subsequent computations, the value of delta should be
clamped not less than the system precision defined. 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 The discussion above assumes the most general case where two
symmetric peers independently measure the offsets and delays between symmetric peers independently measure the offsets and delays between
them. In the case of a stateless server, the protocol can be them. In the case of a stateless server, the protocol can be
simplified. A stateless server copies T3 and T4 from the client 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 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 timestamp T3 before sending it to the client. Additional details for
filling in the remaining protocol fields are given in the next filling in the remaining protocol fields are given in a Section 9 and
section and in Appendix A. following sections and in the appendix.
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 Table 4 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 9. Peer Process
The peer process is called upon arrival of a server packet. It runs The process descriptions to follow include a listing of the important
the on-wire protocol to determine the clock offset and roundtrip state variables followed by an overview of the process operations
delay and in addition computes statistics used by the system and poll implemented as routines. Frequent reference is made to the skeleton
processes. Peer variables are instantiated in the association data in the appendix. The skeleton includes C-language fragments that
structure when the structure is initialized and updated by arriving describe the functions in more detail. It includes the parameters,
packets. There is a peer process, poll process and association for variables and declarations necessary for a conforming NTPv4
each server. implementation. However, many additional variables and routines may
be necessary in a working implementation.
The discussion in this section covers only the variables and routines The peer process is called upon arrival of a server or peer packet.
necessary for a conforming NTPv4 implementation. It runs the on-wire protocol to determine the clock offset and round
trip 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.
8.1. Peer Process Variables 9.1. Peer Process Variables
Table 11, Table 12, Table 13, and Table 14 summarize the common Figure 18, Figure 19, Figure 20 and Figure 21 summarize the common
names, formula names and a short description of each peer variable, names, formula names and a short description of the peer variables.
all of which have prefix p. The common names and formula names are interchangeable; formula names
are intended for equations where space is important. Unless noted
otherwise, all peer variables have assumed prefix p.
+---------+----------+-----------------------+ +---------+----------+-----------------------+
| Name | Formula | Description | | Name | Formula | Description |
+---------+----------+-----------------------+ +---------+----------+-----------------------+
| srcaddr | srcaddr | source address | | srcaddr | srcaddr | source address |
| srcport | srcport | source port | | srcport | srcport | source port |
| dstaddr | dstaddr | destination address | | dstaddr | dstaddr | destination address |
| dstport | destport | destination port | | dstport | destport | destination port |
| keyid | keyid | key identifier key ID | | keyid | keyid | key identifier key ID |
+---------+----------+-----------------------+ +---------+----------+-----------------------+
Table 11: Peer Process Configuration Variables Figure 18: Peer Process Configuration Variables
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. 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.
+-----------+------------+---------------------+ +-----------+------------+---------------------+
| Name | Formula | Description | | Name | Formula | Description |
+-----------+------------+---------------------+ +-----------+------------+---------------------+
| leap | leap | leap indicator | | leap | leap | leap indicator |
| version | version | version number | | version | version | version number |
| mode | mode | mode | | mode | mode | mode |
| stratum | stratum | stratum | | stratum | stratum | stratum |
| ppoll | ppoll | peer poll exponent | | ppoll | ppoll | peer poll exponent |
| rootdelay | delta | root delay | | rootdelay | delta_r | root delay |
| rootdisp | capepsilon | root dispersion | | rootdisp | epsilon_r | root dispersion |
| refid | refid | reference ID | | refid | refid | reference ID |
| reftime | reftime | reference timestamp | | reftime | reftime | reference timestamp |
+-----------+------------+---------------------+ +-----------+------------+---------------------+
Table 12: Peer Process Packet Variables Figure 19: Peer Process Packet Variables
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.
------------------
| receive |
------------------
\| /
------------------ no------------------
| format OK? |-->| format error |
------------------ ------------------
\| / yes
------------------ no------------------
| access OK? |-->| access error |
------------------ ------------------
\| / yes
------------------yes------------------
| mode = 3? |-->| client_packet |
------------------ ------------------
\| / no
------------------yes------------------
| auth OK? |-->| auth error |
------------------ ------------------
\| / yes
------------------
| match_assoc |
------------------
Figure 8: Receive Processing
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.
+------+---------+--------------------+ +------+---------+--------------------+
| Name | Formula | Description | | Name | Formula | Description |
+------+---------+--------------------+ +------+---------+--------------------+
| t | t | epoch |
| org | T1 | origin timestamp | | org | T1 | origin timestamp |
| rec | T2 | receive timestamp | | rec | T2 | receive timestamp |
| xmt | T3 | transmit timestamp | | xmt | T3 | transmit timestamp |
| t | t | packet time |
+------+---------+--------------------+ +------+---------+--------------------+
Table 13: Peer Process Timestamp Variables Figure 20: Peer Process Timestamp Variables
+--------+---------+-----------------+ +--------+---------+-----------------+
| Name | Formula | Description | | Name | Formula | Description |
+--------+---------+-----------------+ +--------+---------+-----------------+
| offset | theta | clock offset | | offset | theta | clock offset |
| delay | del | roundtrip delay | | delay | delta | roundtrip delay |
| disp | epsilon | dispersion | | disp | epsilon | dispersion |
| jitter | psi | jitter | | jitter | psi | jitter |
| filter | filter | clock filter |
| tp | t_p | filter time |
+--------+---------+-----------------+ +--------+---------+-----------------+
Table 14: Peer Process Statistics Variables Figure 21: Peer Process Statistics Variables
The p.org, p.rec, p.xmt variables represent the timestamps computed The following configuration variables are normally initialized when
by the on-wire protocol described previously. The p.offset, p.delay, the association is mobilized, either from a configuration file or
p.disp, p.jitter variables represent the current time values and upon arrival of the first packet for an unknown association.
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 srcaddr: IP address of the remote server or reference clock. This
becomes the destination IP address in packets sent from this
association.
Figure 8 shows the peer process code flow upon the arrival of a srcport: UDP port number of the server or reference clock. This
packet. There is no specific method required for access control, becomes the destination port number in packets sent from this
although it is recommended that implementations include a match-and- association. When operating in symmetric modes (1 and 2) this field
mask scheme similar to many others now in widespread use. Format must contain the NTP port number PORT (123) assigned by the IANA. In
checks require correct field length and alignment, acceptable version other modes it can contain any number consistent with local policy.
number (1-4) and correct extension field syntax, if present. There
is no specific requirement for authentication; however, if 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 19 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. Note however, unlike the NTPv3
design, the leap and stratum variables are never reset unless the
association is reset, which happens only if the system time is
stepped. 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 20 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 21 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 in Appendix A.5.1 shows the peer process code
flow upon the arrival of a packet. The access() routine in
Appendix A.5.4 implements access restrictions using an access control
list (ACL). 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.
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 authentication is implemented, the symmetric key scheme described in
Section 6 must be included among the supported. This scheme uses the Appendix A.2 must be among the supported schemes. This scheme uses
MD5 keyed hash algorithm described in Appendix A.2. For the most the MD5 keyed hash algorithm described in [8].
vulnerable applications the Autokey public key scheme described in
[3] is recommended.
Next, the association table is searched for matching source address Next, the association table is searched for matching source address
and source port using the find_assoc() routine in Appendix A.5.1. and source port using the find_assoc() routine in Appendix A.5.1.
The dispatch table near the beginning of that section is indexed by Figure 22 is a dispatch table where the columns correspond to the
the packet mode and association mode (0 if no matching association) packet mode and rows correspond to the association mode. The
to determine the dispatch code and thus the case target. The intersection of the association and packet modes dispatches
significant cases are FXMT, NEWPS and NEWBC. processing to one of the following steps.
-----------------
| client_packet |
-----------------
\ | /
-----------------
| copy header |
-----------------
\ | /
-----------------
| copy T1,T2 |
-----------------
\ | /
-----------------
| T3 = clock |
-----------------
\ | /
----------------- yes --------------
| copy header | --> | MD5 digest |-\
----------------- -------------- |
| no |
\ | / |
----------------- |
| NAK digest | |
----------------- |
|-----------------------------/
\ | /
-----------------
| fast_xmit() |
-----------------
\ | /
-----------------
| xmt = T3 |
-----------------
\ | /
-----------------
| return |
-----------------
Packet Variable <-- Variable +------------------+---------------------------------------+
x.leap <-- s.leap | | Packet Mode |
x.version <-- r.version +------------------+-------+-------+-------+-------+-------+
x.mode <-- 4 | Association Mode | 1 | 2 | 3 | 4 | 5 |
x.stratum <-- s.stratum +------------------+-------+-------+-------+-------+-------+
x.poll <-- r.poll | No Association 0 | NEWPS | DSCRD | FXMIT | MANY | NEWBC |
x.precision <-- s.precision | Symm. Active 1 | PROC | PROC | DSCRD | DSCRD | DSCRD |
x.rootdelay <-- s.rootdelay | Symm. Passive 2 | PROC | ERR | DSCRD | DSCRD | DSCRD |
x.rootdisp <-- s.rootdisp | Client 3 | DSCRD | DSCRD | DSCRD | PROC | DSCRD |
x.refid <-- s.refid | Server 4 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD |
x.reftime <-- s.reftime | Broadcast 5 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD |
x.org <-- r.xmt | Bcast Client 6 | DSCRD | DSCRD | DSCRD | DSCRD | PROC |
x.rec <-- r.dst +------------------+-------+-------+-------+-------+-------+
x.xmt <-- clock
x.keyid <-- r.keyid
x.digest <-- md5 digest
Figure 9: Client Packet Processing
FXMIT. This is a client (mode 3) packet matching no association. Figure 22: Peer Dispatch Table
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 9 and the fast_xmit() routine in Appendix A.5.4. 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 MUST include the normal NTP header data
shown in the figure, but with a MAC consisting of four octets of
zeros. The client MAY accept or reject the data in the message.
NEWBC. This is a broadcast (mode 5) packet matching no association. DSCRD. This is a nonfatal violation of protocol as the result of a
The client mobilizes a client (mode 3) association as shown in the programming error, long delayed packet or replayed packet. The peer
mobilize() and clear() routines in Appendix A.2. Implementations process discards the packet and exits.
supporting authentication first perform the necessary steps to run
the Autokey or other 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 ERR. This is a fatal violation of protocol as the result of a
association. The client mobilizes a symmetric passive (mode 2) programming error, long delayed packet or replayed packet. The peer
association as shown in the mobilize() and clear() routines in process discards the packet, demobilizes the symmetric passive
Appendix A.2. Code flow continues to the match_assoc() fragment association and exits.
described below. In other cases the packet matches an existing
association and code flows to the match_assoc fragment in Figure 10.
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 11 and the packet() routine in Appendix A.5.2.
Implementations MUST include a number of data range checks as shown
in Table 15 and discard the packet if the ranges are exceeded;
however, the header fields MUST be copied even if errors occur, since
they are necessary in symmetric modes to construct the subsequent
poll message.
--------------- FXMIT. This is a client (mode 3) packet matching no association
| match assoc | (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
--------------- yes ---------------- constructed by the fast_xmit() routine in Appendix A.5.3. The packet
| T3 = 0? | --> | format error | header is assembled from the receive packet and system variables as
--------------- ---------------- shown in Figure 23. If the s.rootdelay and s.rootdisp system
\ | / no variables are stored in floating double, they must be converted to
--------------- yes ---------------- NTP short format first.
| T3 = xmt? | --> | duplicate |
--------------- ----------------
\ | / no
--------------- no ---------------- yes
| mode = 5? | --> |T1 or T2 = 0? |--\
--------------- ---------------- |
| yes \ | / no |
\ | /<-----\ ---------------- |
| \-| T1 = xmt? | |
---------------- ---------------- |
| auth = NAK? | no \ | /<------/
---------------- |
yes\|/ no\|/ ----------------
--------- ------ | org = T3 |
|org=T3| |auth| | rec = T4 |
|rec=T4| |err | ----------------
--------- ------ \ | /
\|/ ----------------
--------- | return |
|packet | ----------------
---------
Figure 10: Timestamp Processing +-----------------------------------+
---------------- | Packet Variable --> Variable |
| packet | +-----------------------------------+
---------------- | r.leap --> p.leap |
\ | / | r.mode --> p.mode |
---------------- | r.stratum --> p.stratum |
| copy header | | r.poll --> p.ppoll |
---------------- | r.rootdelay --> p.rootdelay |
\ | / | r.rootdisp --> p.rootdisp |
---------------- bad ---------------- | r.refid --> p.refid |
| header? | --> |header error | | r.reftime --> p.reftime |
---------------- ---------------- | r.keyid --> p.keyid |
\ | / +-----------------------------------+
----------------
| reach |= 1 |
----------------
\ | /
----------------
| poll update |
----------------
\ | /
----------------------------------------
| theta = 1/2*(T2-T1)+(T3-T4) |
| del = (T4-T1)-(T3-T2) |
| epsilon = rho_r+rho+capphi*((T4-T1) |
----------------------------------------
\ | /
----------------
| clock filter |
----------------
Peer Variables <-- Packet Variables Figure 23: Receive Packet Header
p.leap <-- r.leap
p.mode <-- r.mode Note that, if authentication fails, the server returns a special
p.stratum <-- r.stratum message called a crypto-NAK. This message includes the normal NTP
p.ppoll <-- r.ppoll header data shown in Figure 9, but with a MAC consisting of four
p.rootdelay <-- r.rootdelay octets of zeros. The client MAY accept or reject the data in the
p.rootdisp <-- r.rootdisp message. After these actions the peer process exits.
p.refid <-- r.refid
p.reftime <-- r.reftime 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 using its unicast destination
address. A crypto-NAK is not sent if authentication fails. After
these actions the peer process exits.
MANY: This is 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 is a broadcast (mode 5) packet matching no association.
The client mobilizes either a client (mode 3) or broadcast client
(mode 6) association as shown in the mobilize() and clear() routines
in Appendix A.2. Then the packet() routine in Appendix A.5.1.1
validates the packet and initializes the peer variables.
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 is a symmetric active (mode 1) packet matching no
association. The client mobilizes a symmetric passive (mode 2)
association as shown in the mobilize() routine and clear() routines
in Appendix A.2. Processing continues in the PROC section below.
PROC. The packet matches an existing association. The packet
timestamps are carefully checked to avoid invalid, duplicate or bogus
packets. Additional checks are summarized in Figure 24. Note that
all packets, including a crypto-NAK, are considered valid only if
they survive these tests.
Figure 11: Packet Processing
+--------------------------+----------------------------------------+ +--------------------------+----------------------------------------+
| Packet Type | Description | | Packet Type | Description |
+--------------------------+----------------------------------------+ +--------------------------+----------------------------------------+
| 1 duplicate packet | The packet is at best an old duplicate | | 1 duplicate packet | The packet is at best an old duplicate |
| | or at worst a replay by a hacker. | | | or at worst a replay by a hacker. |
| | This can happen in symmetric modes if | | | This can happen in symmetric modes if |
| | the poll intervals are uneven. | | | the poll intervals are uneven. |
| 2 bogus packet | | | 2 bogus packet | |
| 3 invalid | One or more timestamp fields are | | 3 invalid | One or more timestamp fields are |
| | invalid. This normally happens in | | | invalid. This normally happens in |
| | symmetric modes when one peer sends | | | symmetric modes when one peer sends |
| | the first packet to the other and | | | the first packet to the other and |
| | before the other has received its | | | before the other has received its |
| | first reply. | | | first reply. |
| 4 access denied | The access controls have black | | 4 access denied | The access controls have black |
| 5 authentication failure | The cryptographic message digest does | | 5 authentication failure | The cryptographic message digest does |
| | not match the MAC. | | | not match the MAC. |
| 6 unsynchronized | The server is not synchronized to a | | 6 unsynchronized | The server is not synchronized to a |
| | valid source. | | | valid source. |
| 7 bad header data | One or more header fields are invalid. | | 7 bad header data | One or more header fields are invalid. |
| 8 autokey error | Public key cryptography has failed to |
| | authenticate the packet. |
| 9 crypto error | Mismatched or missing cryptographic |
| | keys or certificates. |
+--------------------------+----------------------------------------+ +--------------------------+----------------------------------------+
Table 15: Packet Error Checks Figure 24: Packet Error Checks
The 8-bit p.reach shift register in the poll process described later Processing continues in the packet() routine in Appendix A.5.1.1. It
is used to determine whether the server is reachable or not and copies the packet variables to the peer variables as shown in
provide information useful to insure the server is reachable and the Figure 23 and the packet() routine in Appendix A.5.2">. The
data are fresh. The register is shifted left by one bit when a receive() routine implements tests 1-5 in Figure 24; the packet()
packet is sent and the rightmost bit is set to zero. As valid routine implements tests 6-7. If errors are found the packet is
packets arrive, the rightmost bit is set to one. If the register discarded and the peer process exits.
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
Appendix A.8.2 is called to re-determine the host poll interval.
The on-wire protocol calculates the clock offset theta and roundtrip The on-wire protocol calculates the clock offset theta and roundtrip
delay del from the four most recent timestamps as shown in Figure 7. delay delta from the four most recent timestamps as described in
While it is in principle possible to do all calculations except the Section 8. While it is in principle possible to do all calculations
first-order timestamp differences in fixed-point arithmetic, it is except the first-order timestamp differences in fixed-point
much easier to convert the first-order differences to floating arithmetic, it is much easier to convert the first-order differences
doubles and do the remaining calculations in that arithmetic, and to floating doubles and do the remaining calculations in that
this will be assumed in the following description. The dispersion arithmetic, and this will be assumed in the following description.
statistic epsilon(t) represents the maximum error due to the
frequency tolerance and time since the last measurement. It is
initialized
epsilon(t_o) = rho_r + rho +capphi(T4-T1) 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 packet() routine sets the rightmost bit 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 Appendix A.5.7.2 is called to redetermine the host poll
interval.
when the measurement is made at t _0. Here rho_r is the peer The dispersion statistic epsilon(t) represents the maximum error due
precision in the packet header r.precision and rho the system to the frequency tolerance and time since the last packet was sent It
precision s.precision, both expressed in seconds. These terms are is initialized
necessary to account for the uncertainty in reading the system clock
in both the server and the client. The dispersion then grows at epsilon(t_0) = r.rho + s.rho + PHI * (T4-T1)
constant rate TOLERANCE (cappsi); in other words, at time t,
epsilon(t)=epsilon(t_0)+cappsi(t-t_0). With the default value when the measurement is made at t_0 according to the seconds counter.
cappsi=15 PPM, this amounts to about 1.3 s per day. With this 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 understanding, the argument t will be dropped and the dispersion
represented simply as epsilon. The remaining statistics are computed represented simply as epsilon. The remaining statistics are computed
by the clock filter algorithm described in the next section. by the clock filter algorithm described in the next section.
8.3. Clock Filter Algorithm 10. Clock Filter Algorithm
-----------------------
| clock filter |
-----------------------
\ | /
-----------------------
| shift sample theta, |
| del, epsilon, and t |
| filter shift registr|
-----------------------
\ | /
-----------------------
| copy filter to a |
| temporary list. sort|
| list by increasing |
| del. Let theta_i |
| del_i, epsilon_i, |
| t_i be the ith entry|
| on the sorted list. |
-----------------------
\ | /
----------------------- no
| t_0 > t? |----\
----------------------- |
\ | / yes |
----------------------- |
| theta = theta_0 | |
| del = del_0 | |
| epsilon | |
| = sum(epsilon_i) | |
| ---------- | |
| 2^(i+1) | |
| psi | |
| = sqrt(1/7* ... | |
| ... sum( ... | |
| (theta_0-theta_i)^2 | |
| t = t_0 | |
----------------------- |
\ | / |
----------------------- |
| clock_select() | |
----------------------- |
\ | /<------------/
-----------------------
| return |
-----------------------
Figure 12: Clock Filter Processing The clock filter algorithm, part of the peer process, is implemented
The clock filter algorithm grooms the stream of on-wire data to in the clock_filter() routine in Appendix A.5.2. It grooms the
select the samples most likely to represent the correct time. The stream of on-wire data to select the samples most likely to represent
algorithm produces the p.offset theta, p.delay del, p.dispersion accurate time. The algorithm produces the variables shown in
epsilon, p.jitter psi, and time of arrival p.t t used by the Figure 21, including the offset (theta), delay (delta), dispersion
mitigation algorithms to determine the best and final offset used to (epsilon), jitter (psi) and time of arrival (t). These data are used
discipline the system clock. They are also used to determine the by the mitigation algorithms to determine the best and final offset
server health and whether it is suitable for synchronization. The used to discipline the system clock. They are also used to determine
core processing steps of this algorithm are shown in Figure 12 with the server health and whether it is suitable for synchronization.
more detail in the clock_filter() routine in Appendix A.5.3.
The clock filter algorithm saves the most recent sample tuples The clock filter algorithm saves the most recent sample tuples
(theta, del, epsilon, t) in an 8-stage shift register in the order (theta, delta, epsilon, t) in the filter structure, which functions
that packets arrive. Here t is the system timer, not the peer as an 8-stage shift register. The tuples are saved in the order that
variable of the same name. The following scheme is used to insure packets arrive. Here t is the packet time of arrival according to
sufficient samples are in the register and that old stale data are the seconds counter and should not be confused with the peer variable
discarded. Initially, the tuples of all stages are set to the dummy tp.
tuple (0,MAXDISP, MAXDISP, 0). As valid packets arrive, the (theta,
del, epsilon, t) tuples are shifted into the register causing old The following scheme is used to insure sufficient samples are in the
samples to be discarded, so eventually only valid samples remain. If filter and that old stale data are discarded. Initially, the tuples
the three low order bits of the reach register are zero, indicating of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, 0).
three poll intervals have expired with no valid packets received, the As valid packets arrive, tuples are shifted into the filter causing
poll process calls the clock filter algorithm with the dummy tuple old tuples to be discarded, so eventually only valid tuples remain.
just as if the tuple had arrived from the network. If this persists If the three low order bits of the reach register are zero,
for eight poll intervals, the register returns to the initial indicating three poll intervals have expired with no valid packets
condition. 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 In the next step the shift register stages are copied to a temporary
list and the list sorted by increasing del. Let j index the stages list and the list sorted by increasing delta. Let i index the stages
starting with the lowest del. If the sample epoch t_0 is not later starting with the lowest delta. If the first tuple epoch t_0 is not
than the last valid sample epoch p.t, the routine exits without later than the last valid sample epoch p.t, the routine exits without
affecting the current peer variables. Otherwise, let epsilon_j be affecting the current peer variables. Otherwise, let epsilon_i be
the dispersion of the jth entry, then the dispersion of the ith entry, then
i=n-1 i=n-1
--- epsilon_i --- epsilon_i
capepsilon = \ ---------- capepsilon = \ ----------
/ (i+1) / (i+1)
--- 2 --- 2
i=0 i=0
is the peer dispersion p.disp. Note the overload of epsilon, whether 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 input to the clock filter or output, the meaning should be clear from
context. context.
skipping to change at page 44, line 23 skipping to change at page 39, line 50
| | n-1 | | | | n-1 | |
| | --- | | | | --- | |
| 1 | \ 2 | | | 1 | \ 2 | |
psi = | -------- * | / (theta_0-theta_j) | | psi = | -------- * | / (theta_0-theta_j) | |
| (n-1) | --- | | | (n-1) | --- | |
| | j=1 | | | | j=1 | |
| +----- -----+ | | +----- -----+ |
| | | |
+----- -----+ +----- -----+
where n is the number of valid tuples in the register. In order to where n is the number of valid tuples in the filter (n > 1). In
insure consistency and avoid divide exceptions in other computations, order to insure consistency and avoid divide exceptions in other
the psi is bounded from below by the system precision rho expressed computations, the psi is bounded from below by the system precision
in seconds. While not in general considered a major factor in s.rho expressed in seconds. While not in general considered a major
ranking server quality, jitter is a valuable indicator of fundamental factor in ranking server quality, jitter is a valuable indicator of
timekeeping performance and network congestion state. fundamental timekeeping performance and network congestion state. Of
particular importance to the mitigation algorithms is the peer
Of particular importance to the mitigation algorithms is the peer synchronization distance, which is computed from the delay and
synchronization distance, which is computed from the root delay and dispersion.
root dispersion. The root delay is
del ' = delta_r + del
and the root dispersion is
epsilon ' = capepsilon_r + epsilon + psi
Note that epsilon and therefore increase at rate capphi. The peer lambda = (delta / 2) + epsilon.
synchronization distance is defined
lambda = (del ' / 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.
and recalculated as necessary. The lambda is a component of the root It is important to note that, unlike NTPv3, NTPv4 associations do not
synchronization distance caplambda used by the mitigation algorithms show a timeout condition by setting the stratum peer variable to 16.
as a metric to evaluate the quality of time available from each In NTPv4 lambda increases with time, so eventually the
server. Note that there is no state variable for lambda, as it synchronization distance exceeds the distance threshold MAXDIST, in
depends on the time since the last update. which case the association is considered unfit for synchronization.
9. System Process 11. System Process
As each new sample (theta, delta, epsilon, t) is produced by the As each new sample (theta, delta, epsilon, jitter, t) is produced by
clock filter algorithm, the sample is processed by the mitigation the clock filter algorithm, all peer processes are scanned by the
algorithms consisting of the selection, clustering, combining and mitigation algorithms consisting of the selection, cluster, combine
clock discipline algorithms in the system process. The selection and clock discipline algorithms in the system process. The selection
algorithm scans all associations and casts off the falsetickers, algorithm scans all associations and casts off the falsetickers,
which have demonstrably incorrect time, leaving the truechimers as which have demonstrably incorrect time, leaving the truechimers as
result. In a series of rounds the clustering algorithm discards the result. In a series of rounds the cluster algorithm discards the
association statistically furthest from the centroid until a minimum association statistically furthest from the centroid until a
number of survivors remain. The combining algorithm produces the specified minimum number of survivors remain. The combine algorithm
best and final offset on a weighted average basis and selects one of produces the best and final statistics on a weighted average basis.
the associations as the system peer providing the best statistics for The final offset is passed to the clock discipline algorithm to steer
performance evaluation. The final offset is passed to the clock the system clock to the correct time.
discipline algorithm to steer the system clock to the correct time.
The statistics (theta, delta, epsilon, 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 the basic variables and The cluster algorithm selects one of the survivors as the system
routines necessary for a conforming NTPv4 implementation. Additional peer. The associated statistics (theta, delta, epsilon, jitter, t)
implementation details are in Appendix A. An interface that might be are used to construct the system variables inherited by dependent
considered in a formal specification is represented by the function servers and clients and made available to other applications running
prototypes in Appendix A.1.6. on the same machine.
9.1. System Process Variables 11.1. System Process Variables
The variables and parameters associated with the system process are Figure 27 summarizes the common names, formula names and a short
summarized in Table 16, which gives the variable name, formula name description of each system variable. Unless noted otherwise, all
and short description. Unless noted otherwise, all variables have variables have assumed prefix s.
assumed prefix s.
+-----------+------------+---------------------+ +-----------+------------+------------------------+
| Name | Formula | Description | | Name | Formula | Description |
+-----------+------------+---------------------+ +-----------+------------+------------------------+
| t | t | epoch | | t | t | update time |
| p | p | system peer identifier |
| leap | leap | leap indicator | | leap | leap | leap indicator |
| stratum | stratum | stratum | | stratum | stratum | stratum |
| precision | rho | precision | | precision | rho | precision |
| p | p | system peer pointer | | offset | THETA | combined offset |
| offset | captheta | combined offset | | jitter | PSI | combined jitter |
| jitter | varsigma | combined jitter | | rootdelay | DELTA | root delay |
| rootdelay | capdelta | root delay | | rootdisp | EPSILON | root dispersion |
| rootdisp | capepsilon | root dispersion |
| refid | refid | reference ID | | refid | refid | reference ID |
| reftime | reftime | reference time | | reftime | reftime | reference time |
| NMIN | 3 | minimum survivors | | NMIN | 3 | minimum survivors |
| CMIN | 1 | minimum candidates | | CMIN | 1 | minimum candidates |
+-----------+------------+---------------------+ +-----------+------------+------------------------+
Table 16: System Process Variables and Parameters
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.
s.offset: Offset computed by the combining algorithm.
s.jitter: Jitter computed by the cluster and combining algorithms. Figure 27: System Process Variables
The variables defined below are updated from the system peer process Except for the t, p, offset and jitter variables and the NMIN and
as described later. They are interpreted in the same way as the as CMIN constants, the variables have the same format and interpretation
the peer variables of the same names. as the peer variables of the same name. The NMIN and CMIN parameters
are used by the selection and cluster algorithms described in the
next section.
s.leap, s.stratum, s.rootdelay, s.rootdisp, s.refid, s.reftime The t variable is the seconds counter at the last update determined
by the clock_update() routine in Appendix A.5.5.4. The p variable is
the system peer identifier determined by the cluster() routine in
Section 11.2.2. The precision variable has the same format as the
packet variable of the same name. The precision is defined as the
larger of the resolution and time to read the clock, in log2 units.
For instance, the precision of a mains-frequency clock incrementing
at 60 Hz is 16 ms, even when the system clock hardware representation
is to the nanosecond.
Initially, all variables are cleared to zero, then the s.leap is set The offset and jitter variables are determined by the combine()
to 3 (unsynchronized) and s.stratum is set to MAXSTRAT (16). The routine in Section 11.2.3. These values represent the best and final
remaining statistics are determined as described below. offset and jitter used to discipline the system clock. Initially,
all variables are cleared to zero, then the leap is set to 3
(unsynchronized) and stratum is set to MAXSTRAT (16). Remember that
MAXSTRAT is mapped to zero in the transmitted packet.
9.2. System Process Operations 11.2. System Process Operations
The system process implements the selection, clustering, combining Figure 28 summarizes the system process operations performed by the
and clock discipline algorithms. The clock_select() routine in clock_select() routine. The selection algorithm described in
Figure 15 includes the selection algorithm of Section 9.2.1 that Section 11.2.1 produces a majority clique of presumed correct
produces a majority clique of truechimers based on agreement candidates (truechimers) based on agreement principles. The cluster
principles. The clustering algorithm of Section 9.2.2 discards the algorithm described in Section 11.2.2 discards outlyers to produce
outliers of the clique to produce the survivors used by the combining the most accurate survivors. The combine algorithm described in
algorithm in Section 9.2.3 , which in turn provides the final offset Section 11.2.3 provides the best and final offset for the clock
for the clock discipline algorithm in Section 9.2.4. If the discipline algorithm described in Appendix A.5.5.6. If the selection
selection algorithm cannot produce a majority clique, or if the algorithm cannot produce a majority clique, or if it cannot produce
clustering algorithm cannot produce at least CMIN survivors, the at least CMIN survivors, the system process exits without
system process terminates with no further processing. If successful, disciplining the system clock. If successful, the cluster algorithm
the clustering algorithm selects the statistically best candidate as selects the statistically best candidate as the system peer and its
the system peer and its variables are inherited as the system variables are inherited as the system variables.
variables. The selection and clustering algorithms are described
below separately, but combined in the code skeleton.
------------------------- +-----------------+
| clock_select() | | clock_select() |
------------------------- +-----------------+
\|/ ................................|...........
-----------------------------------|--------------- . V .
| ----------- ---------------------- | . yes +---------+ +-----------------+ .
| /---| accept? | | scan candidates | | . +--| accept? | | scan candidates | .
| | ----------- | | | . | +---------+ | | .
| | yes no| | | | . V no | | | .
| ----------- | | | | . +---------+ | | | .
| | add peer| | | | | . | add peer| | | | .
| ----------- | | | | . +---------- | | | .
| | \|/ | | | . | V | | .
| \-------->----->| | | . +---------->-->| | .
| | | | . | | .
| selection algorithm ---------------------- | . Selection Algorithm +-----------------+ .
| \|/ | .................................|..........
------------------------------------|-------------- V
no ----------------------- no +-------------------+
/--------------| survivors? | +-------------| survivors? |
| ----------------------- | +-------------------+
| \|/ yes | | yes
| ----------------------- | V
| | clustering algorithm| | +-------------------+
| ----------------------- | | Cluster Algorithm |
| \|/ | +-------------------+
| ----------------------- | |
|<---------yes-| n < CMIN? | | V
\|/ ----------------------- V yes +-------------------+
------------------------- \|/ no |<------------| n < CMIN? |
| s.p = NULL | ----------------------- | +-------------------+
------------------------- | s.p = vo.p | V |
\|/ ----------------------- +-----------------+ V no
------------------------- \|/ | s.p = NULL | +-------------------+
| return (UNSYNC) | ----------------------- +-----------------+ | s.p = vo.p |
------------------------- | return (SYNC) | | +-------------------+
----------------------- V |
+-----------------+ V
| return (UNSYNC) | +-------------------+
+-----------------+ | return (SYNC) |
+-------------------+
Figure 15: clock_select() routine Figure 28: clock_select() Routine
9.2.1. Selection Algorithm 11.2.1. Selection Algorithm
The selection algorithm operates to find the truechimers using Note that the selection and cluster algorithms are described
Byzantine agreement principles originally proposed by Marzullo [7], separately, but combined in the code skeleton. The selection
but modified to improve accuracy. An overview of the algorithm is algorithm operates to find an intersection interval containing a
listed below and the first half of the clock_select() routine in majority clique of truechimers using Byzantine agreement principles
Appendix A.6.1. First, those servers which are unusable according to originally proposed by Marzullo [9], but modified to improve
the rules of the protocol are detected and discarded by the accept() accuracy. An overview of the algorithm is given below and in the
routine in Figure 16 and Appendix A.6.3. Next, a set of tuples {p, first half of the clock_select() routine in Appendix A.5.5.1.
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 [theta-
lambda,theta+lambda], where lambda is the root distance.
1. For each of m associations, construct a correctness interval First, those servers which are unusable according to the rules of the
[(theta-rootdist()),(theta+rootdist())]. protocol are detected and discarded by the accept() routine in
Appendix A.5.5.3. Next, a set of tuples (p, type, edge) is generated
for the remaining candidates. Here, p is the association identifier
and type identifies the upper (+1), middle (0) and lower (-1)
endpoints of a correctness interval centered on theta for that
candidate. This results in three tuples, lowpoint (p, -1, theta -
lambda), midpoint (p, 0, theta) and highpoint (p, +1, theta +
lambda), where lambda is the root synchronization distance calculated
on each use by the rootdist() routine in Appendix A.5.1.1. The steps
of the algorithm are:
2. Select the lowpoint, midpoint and highpoint of these intervals. 1. For each of m associations, place three tuples as defined above
Sort these values in a list from lowest to highest. Set the on the candidate list.
number of falsetickers f=0.
2. Sort the tuples on the list by the edge component. Order the
lowpoint, midpoint and highpoint of these intervals from lowest to
highest. Set the number of falsetickers f = 0.
3. Set the number of midpoints d=0. Set c=0. Scan from lowest 3. Set the number of midpoints d=0. Set c=0. Scan from lowest
endpoint to highest. Add one to c for every lowpoint, subtract endpoint to highest. Add one to c for every lowpoint, subtract one
one for every highpoint, add one to d for every midpoint. If for every highpoint, add one to d for every midpoint. If c >= m - f,
c>=m-f, stop; set l=current lowpoint stop; set l = current lowpoint.
4. Set c=0. Scan from highest endpoint to lowest. Add one to c for 4. Set c = 0. Scan from highest endpoint to lowest. Add one to c
every highpoint, subtract one for every lowpoint, add one to d for every highpoint, subtract one for every lowpoint, add one to d
for every midpoint. If c>=m-f, stop; set u=current highpoint. for every midpoint. If c>=m-f, stop; set u=current highpoint.
5. Is d=f and l<u? If yes, then follow step 5A, else, follow step 5. Is d = f and l < u? If yes, then follow step 5A; else, follow
5B. step 5B.
A. Success: the intersection interval is [l, u].
B. Add one to f. Is f < (m / 2)? If yes, then go to step 3
again. If no, then go to step 6.
6. Failure; a majority clique could not be found. Stop algorithm.
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
as described in detail in [8]. 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.
--------------------
| accept() |
--------------------
\|/
--------------------
| leap = 11? |
| stratum >= |--any yes---\ server not
| MAXSTRAT? | | synchronized
-------------------- |
\|/ all no |
-------------------- |
| reach = 0? |---yes----->| server not
-------------------- | reachable
\|/ no |
-------------------- |
| root_dist() >= | |
| MAXDIST? |---yes----->| root distance
-------------------- | exceeded
\|/ no |
-------------------- |
| refid = addr? |---yes----->| server/client
-------------------- | sync loop
\|/ no |
-------------------- |
| return (YES) | -----------------------
-------------------- | return (NO) |
-----------------------
Figure 16: accept() routine
9.2.2. Clustering Algorithm
The members of the majority clique are placed on the survivor list, 5A. Success: the intersection interval is [l, u].
and sorted first by stratum, then by root distance lambda. The
sorted list is processed by the clustering algorithm below and the
second half of the clock_select() algorithm in Appendix A.6.1.
1. Let (theta, phi, Lambda) represent a candidate peer with 5B. Add one to f. Is f < (m / 2)? If yes, then go to step 3 again.
offset theta, jitter psi and a weight factor If no, then go to step 6.
Lambda=stratum*MAXDIST+rootdist().
2. Sort the candidates by increasing Lambda. Let n be the number 6. Failure; a majority clique could not be found. There are no
of candidates and NMIN the minimum number of survivors. suitable candidates to discipline the system clock.
3. For each candidate compute the selection jitter psi_S (RMS The algorithm is described in detail in Appendix A.5.5.1. Note that
peer offset differences between this and all other candidates). it 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 midpoint of
each truechimer (theta) represents the candidates available to the
cluster algorithm.
4. Select psi_max as the candidate with maximum psi_S. If a majority clique is not found, or if the number of truechimers is
less than CMIN, there are insufficient candidates to discipline the
system clock. CMIN defines the minimum number of servers consistent
with the correctness requirements. Suspicious operators would set
CMIN to insure multiple redundant servers are available for the
algorithms to mitigate properly. However, for historic reasons the
default value for CMIN is one.
5. Select psi_min as the candidate with minimum psi_S. 11.2.2. Cluster Algorithm
6. Is psi_max < psi_min or n <= NMIN? If yes, go to step 6y. If The candidates of the majority clique are placed on the survivor list
no, go to step 6n. in the form of tuples (p, theta_p, psi_p, lambda_p), where p is an
association identifier, theta_p, psi_p, and stratum_p the current
offset, jitter and stratum of association p, respectively, and
lambda_p is a merit factor equal to stratum_p * MAXDIST + lambda,
where lambda is the root synchronization distance for association p.
The list is processed by the cluster algorithm below and the second
half of the clock_select() algorithm in Appendix A.5.5.1.
6y. Done. The remaining cluster survivors are correct. The 1. Let (p, theta_p, psi_p, lambda_p) represent a survivor candidate.
survivors are in the v. structure sorted by Lambda.
6n. Delete the outlyer candidate with psi_max; reduce n by one, 2. Sort the candidates by increasing lambda_p. Let n be the number
and go back to step 3. of candidates and NMIN the minimum required number of survivors.
It operates in a series of rounds where each round discards the 3. For each candidate compute the selection jitter psi_s:
furthest statistical outlier until a specified minimum number of 1/2
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 psi_p is the peer jitter of the s
survivor. Compute
+----- -----+ +----- -----+
| 1/2 | | n-1 |
| +----- -----+ | | --- |
| | n-1 | | 1 | \ 2 |
| | --- | | psi_s = ---- * | / (theta_s - theta_j) |
| 1 | \ 2 | | n-1 | --- |
psi_s = | -------- * | / (theta_s-theta_j) | | | j=1 |
| (n-1) | --- | |
| | j=1 | |
| +----- -----+ |
| |
+----- -----+ +----- -----+
as the selection jitter. Then choose psi_max=max(psi) and 4. Select psi_max as the candidate with maximum psi_s.
psi_min=min(psi). If psi_max<psi_min or n<NMIN, 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 case off the psi_max survivor, reduces n by
one and makes another round.
9.2.3. Combining Algorithm 5. Select psi_min as the candidate with minimum psi_p.
---------------------
| clock_combine() |
---------------------
\|/
---------------------
| y = z = w = 0 |
---------------------
\|/
---------------------
| scan cluster | ------------------
| survivors |-->| x = rootdist() |
| | ------------------
| | \|/
| | ------------------
| |<--| y+= 1/x |
| | | z+=theta_i/x |
| | | w+=(theta_i - |
| | | theta_o)^2 |
--------------------- ------------------
\|/ done
-----------------------
| captheta = z/y |
| vartheta = sqrt(w/y)|
-----------------------
\|/
-----------------------
| return |
-----------------------
Variable/Process/Description 6. Is psi_max < psi_min or n <= NMIN? If yes, follow step 6A;
captheta/system/combined clock offset otherwise, follow step 6B.
vartheta_p/system/combined jitter
theta_0/survivor list/first survivor offset
theta_i/survivor list/ith survivor offset
x,y,z,w/ /temporaries
Figure 18: clock_combine() routine 6A. Done. The remaining candidates on the survivor list are ranked
-------------------- in the order of preference. The first entry on the list represents
| clock_update() | the system peer; its variables are used later to update the system
-------------------- variables.
\|/
--------------------
/----no----->| p.t > s.t |
| --------------------
| \|/ yes
| --------------------
| | s.t = p.t |
| --------------------
| \|/
| --------------------
| | local_clock() |
| --------------------
| \|/
|<--------------------+-----------------\
| panic\|/ | adj step\|/
| ------------- | -------------------
| | panic exit| | | clear all assoc.|
| ------------- | -------------------
| ----------------- \|/
| |*update system | -----------------
| | variables | | leap = 3 |
| ----------------- | quamtum = |
| \|/ | MAXSTRAT |
| | -----------------
\---------------------+----------------/
|
---------------
| return |
---------------
System Variables <-- System Peer Variables 6B. Delete the outlyer candidate with psi_max; reduce n by one and go
leap <-- leap back to step 3.
stratum <-- stratum + 1
refid <-- refid
reftime <-- reftime
capdelta <-- capdelta_r + del
capepsilon <-- capepsilon_r+epsilon+cappsi*mu+psi+|captheta|
* update system variables
Figure 19: clock_update() routine The algorithm operates in a series of rounds where each round
discards the statistical outlyer with maximum selection jitter psi_s.
However, if psi_s is less than the minimum peer jitter psi_p, no
improvement is possible by discarding outlyers. This and the minimum
number of survivors represent the terminating conditions of the
algorithm. Upon termination, the final value of psi_max is saved as
the system selection jitter PSI_s for use later.
11.2.3. Combine Algorithm
The remaining survivors are processed by the clock_combine() routine The remaining survivors are processed by the clock_combine() routine
in Figure 18 and Appendix A.6.5 to produce the best and final data in Appendix A.5.5.5 to produce the best and final data for the clock
for the clock discipline algorithm. The routine processes the peer discipline algorithm. The clock_combine() routine processes peer
offset theta and jitter psi to produce the system offset captheta and offset and jitter statistics to produce the combined system offset
system peer jitter vartheta_p, where each server statistic is THETA and system peer jitter PSI_p, where each server statistic is
weighted by the reciprocal of the root distance and the result weighted by the reciprocal of the root synchronization distance and
normalized. The system peer jitter vartheta_p is a component of the the result normalized.
system jitter described later.
The system statistics are passed to the clock_update() routine in The combined THETA is passed to the clock_update() routine in
Figure 19 and Appendix A.6.4. If there is only one survivor, the Appendix A.5.5.4. The first candidate on the survivor list is
offset passed to the clock discipline algorithm is captheta=theta and nominated as the system peer with identifier p. The system peer
the system peer jitter is vartheta=psi. Otherwise, the selection jitter PSI_p is a component of the system jitter PSI. It is used
jitter vartheta_s is computed as in (8), where theta_0 represents the along with the selection jitter PSI_s to produce the system jitter:
offset of the system peer and j ranges over the survivors.
Peer Variables Client System Variables
---------------- -----------------
| theta = 1/2* |-------------------->| captheta = |
| [(T2 - T1)+ | | (combine |
| (T3 - T4)] | | (theta_j)) |
---------------- -----------------
| del = [(T4 - |--sum--------------->| capdelta= |
| T1) - (T3 - | /|\ | capdelta_r + |
| T2)] | | | del |
---------------- | -----------------
| epsilon = | | | capepsilon = |
| | | |capepsilon_r + |
| rho_r + rho +| | | epsilon + |
| captheta*( | | | vartheta + |
| T4 - T1) |------------sum----->| absolutevalue(|
---------------- | /|\ | theta) |
| psi = | | | -----------------
| sqrt((1/n)-1)*| | | | psi_s = |
| (sum(theta_0)| | | | sqrt(1/(m-1)* |
| -theta_i)^2))|---|---\ | | sum(theta_0- |
---------------- | | | | theta_j)^2) |
/|\ | | | -----------------
| | | | \|/
| | \------------------>sum
server| | | |
---------------- | | \|/
| rho_r | | | |
---------------- | | -----------------
| capdelta_r |>--/ | | vartheta = |
---------------- | | sqrt( |
| capepsilon_r |>------------/ | (vartheta_p)^2|
---------------- | + |
| (vartheta_s)^2|
-----------------
Figure 20: System Variables Processing PSI = [(PSI_s)^2 + (PSI_p)^2]
The first survivor on the survivor list is selected as the system
peer, here represented by the statistics (theta, del, epsilon, psi).
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 mu=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 19. Note that s.stratum is set to
p.stratum plus one.
The arrows labeled IGNOR, PANIC, ADJ and STEP refer to return codes Each time an update is received from the system peer, the
from the local_clock() routine described in the next section. IGNORE clock_update() routine in Appendix A.5.5.4 is called. By rule, an
means the update has been ignored as an outlier. PANIC means the update is discarded if its time of arrival p.t is not strictly later
offset is greater than the panic threshold PANICT (1000 s) and SHOULD than the last update used s.t. The labels IGNOR, PANIC, ADJ and STEP
cause the program to exit with a diagnostic message to the system refer to return codes from the local_clock() routine described in the
log. STEP means the offset is less than the panic threshold, but next section.
greater than the step threshold STEPT (125 ms). Since this means all
peer data have been invalidated, all associations SHOULD be 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 19.
There is one exception not shown. The dispersion increment is IGNORE means the update has been ignored as an outlyer. PANIC means
bounded from below by MINDISP. In subnets with very fast processors the offset is greater than the panic threshold PANICT (1000 s) and
and networks and very small dispersion and delay this forces a SHOULD cause the program to exit with a diagnostic message to the
monotone-definite increase in capepsilon, which avoids loops between system log. STEP means the offset is less than the panic threshold,
peers operating at the same stratum. but greater than the step threshold STEPT (125 ms). Since this means
all peer data have been invalidated, all associations MUST be reset
and the client begins as at initial start.
Figure 20 shows how the error budget grows from the packet variables, ADJ means the offset is less than the step threshold and thus a valid
on-wire protocol and system peer process to produce the system update. In this case the system variables are updated from the peer
variables that are passed to dependent applications and clients. The variables as shown in Figure 30.
system jitter is defined
vartheta = sqrt((vartheta_p)^2+(vartheta_s)^2) +-------------------------------------------+
| System Variable <-- System Peer Variable | |
+-------------------------------------------+
| s.leap <-- p.leap |
| s.stratum <-- p.stratum + 1 |
| s.offset <-- THETA |
| s.jitter <-- PSI |
| s.rootdelay <-- p.delta_r + delta |
| s.rootdisp <-- p.epsilon_r + p.epsilon + |
| p.psi + PHI * (s.t - p.t) |
| + |THETA| |
| s.refid <-- p.refid |
| s.reftime <-- p.reftime |
| s.t <-- p.t |
+-------------------------------------------+
where vartheta_s is the selection jitter relative to the system peer. Figure 30: System Variables Update
The system jitter is passed to dependent applications programs as the
nominal error statistic. The root delay capdelta and root dispersion
capepsilon statistics are relative to the primary server reference
clock and thus inherited by each server along the path. The system
synchronization distance is defined
caplambda = capdelta/2 + capepsilon There is an important detail not shown. The dispersion increment
(p.epsilon + p.psi + PHI * (s.t - p.t) + |THETA|) is bounded from
below by MINDISP. In subnets with very fast processors and networks
and very small delay and dispersion this forces a monotone-definite
increase in s.rootdisp (EPSILON), which avoids loops between peers
operating at the same stratum.
which is passed to dependent application programs as the maximum The system variables are available to dependent application programs
error statistic. as nominal performance statistics. The system offset THETA is the
clock offset relative to the available synchronization sources. The
system jitter PSI is an estimate of the error in determining this
value, elsewhere called the expected error. The root delay DELTA is
the total round trip delay relative to the primary server. The root
dispersion EPSILON is the dispersion accumulated over the network
from the primary server. Finally, the root synchronization distance
is defined
9.2.4. Clock Discipline Algorithm LAMBDA = EPSILON + DELTA / 2,
---------
theta_r + | \ +----------------+
NTP --------->| Phase \ V_d | | V_s
theta_c - | Detector ------>| Clock Filter |-----+
+-------->| / | | |
| | / +----------------+ |
| --------- |
| |
----- |
/ \ |
| VFO | |
\ / |
----- +-------------------------------------+ |
^ | Loop Filter | |
| | | |
| | +---------+ x +-------------+ | |
| V_c | | |<-----| | | |
+------|-| Clock | y | Phase/Freq |<---|------+
| | Adjust |<-----| Prediction | |
| | | | | |
| +---------+ +-------------+ |
| |
+-------------------------------------+
Figure 21: Clock Discipline Feedback Loop which represents the maximum error due all causes and is designated
the root synchronization distance.
11.3. Clock Discipline Algorithm
The NTPv4 clock discipline algorithm, shortened to discipline in the The NTPv4 clock discipline algorithm, shortened to discipline in the
following, functions as a combination of two philosophically quite following, functions as a combination of two philosophically quite
different feedback control systems. In a phase-locked loop (PLL) different feedback control systems. In a phase-locked loop (PLL)
design, periodic phase updates at update intervals m are used design, periodic phase updates at update intervals mu seconds are
directly to minimize the time error and indirectly the frequency used directly to minimize the time error and indirectly the frequency
error. In a frequency-locked loop (FLL) design, periodic frequency error. In a frequency-locked loop (FLL) design, periodic frequency
updates at intervals mu are used directly to minimize the frequency updates at intervals mu are used directly to minimize the frequency
error and indirectly the time error. As shown in [8], a PLL usually error and indirectly the time error. As shown in [5], a PLL usually
works better when network jitter dominates, while a FLL works better works better when network jitter dominates, while a FLL works better
when oscillator wander dominates. This section contains an outline when oscillator wander dominates. This section contains an outline
of how the NTPv4 design works. An in-depth discussion of the design of how the NTPv4 design works. An in-depth discussion of the design
principles is provided in [8], which also includes a performance principles is provided in [5], which also includes a performance
analysis. analysis.
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 The discipline is implemented as the feedback control system shown in
Figure 21. The variable theta_r represents the combining algorithm Figure 31. The variable theta_r represents the combine algorithm
offset (reference phase) and theta_c the VFO offset (control phase). offset (reference phase) and theta_c the VFO offset (control phase).
Each update produces a signal V_d representing the instantaneous Each update produces a signal V_d representing the instantaneous
phase difference theta_r - theta_c. The clock filter for each server phase difference theta_r - theta_c. The clock filter for each server
functions as a tapped delay line, with the output taken at the tap functions as a tapped delay line, with the output taken at the tap
selected by the clock filter algorithm. The selection, clustering selected by the clock filter algorithm. The selection, cluster and
and combining algorithms combine the data from multiple filters to combine algorithms combine the data from multiple filters to produce
produce the signal V_s. The loop filter, with impulse response F(t), the signal V_s. The loop filter, with impulse response F(t),
produces the signal V_c which controls the VFO frequency omega_c and produces the signal V_c which controls the VFO frequency omega_c and
thus its phase theta_c=integral(omega_c,dt) which closes the loop. thus the integral of the phase theta_c which closes the loop. The
The V_c signal is generated by the clock adjust process in V_c signal is generated by the clock adjust process in Section 12.
Section 9.3. The characteristic behavior of this model, which is The detailed equations that implement these functions are best
determined by F(t) and the various gain factors given in presented in the routines of Appendix A.5.5.6 and Appendix A.5.6.1.
Appendix A.6.6.
The transient behavior of the PLL/FLL feedback loop is determined by theta_r + +---------\ +----------------+
the impulse response of the loop filter F(t). The loop filter shown NTP --------->| Phase \ V_d | | V_s
in Figure 22 predicts a phase adjustment x as a function of Vs. The theta_c - | Detector ------>| Clock Filter |----+
PLL predicts a frequency adjustment yFLL as an integral of Vs*mu with +-------->| / | | |
repsect to t, while the FLL predicts an adjustment yPLL as a function | +---------/ +----------------+ |
of Vs /mu. The two adjustments are combined to correct the frequency
y as shown in Figure 22. 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 Appendix A.6.6 and Appendix A.7.1.
x <------(Phase Correction)<--.
|
y_FLL |
.-(FLL Predict)<-------+<--V_s
| |
\|/ |
y <--(Sum) |
^ |
| | | |
'-(PLL Predict)<-------' ----- |
y_PLL / \ |
| VFO | |
\ / |
----- ....................................... |
^ . Loop Filter . |
| . +---------+ x +-------------+ . |
| V_c . | |<-----| | . |
+------.-| Clock | y | Phase/Freq |<---------+
. | Adjust |<-----| Prediction | .
. | | | | .
. +---------+ +-------------+ .
.......................................
Figure 22: Clock Discipline Loop Filter Figure 31: Clock Discipline Feedback Loop
Ordinarily, the pseudo-linear feedback loop described above operates Ordinarily, the pseudo-linear feedback loop described above operates
to discipline the system clock. However, there are cases where a to discipline the system clock. However, there are cases where a
nonlinear algorithm offers considerable improvement. One case is nonlinear algorithm offers considerable improvement. One case is
when the discipline starts without knowledge of the intrinsic clock when the discipline starts without knowledge of the intrinsic clock
frequency. The pseudo-linear loop takes several hours to develop an frequency. The pseudo-linear loop takes several hours to develop an
accurate measurement and during most of that time the poll interval accurate measurement and during most of that time the poll interval
cannot be increased. The nonlinear loop described below does this in cannot be increased. The nonlinear loop described below does this in
15 minutes. Another case is when occasional bursts of large jitter 15 minutes. Another case is when occasional bursts of large jitter
are present due to congested network links. The state machine are present due to congested network links. The state machine
described below resists error bursts lasting less than 15 minutes. described below resists error bursts lasting less than 15 minutes.
The remainder of this section describes how the discipline works. Figure 32 contains a summary of the variables and parameters
Table 17 contains a summary of the variables and parameters including including the variables (lower case) or parameters (upper case) name,
the program name, formula name and short description. Unless noted formula name and short description. Unless noted otherwise, all
otherwisse, all variables have assumed prefix c. The variables c.t, variables have assumed prefix c. The variables t, tc, state, hyster
c.tc, c.state, and c.count are integers; the memainder are floating and count are integers; the remaining variables are floating doubles.
doubles. The function of each will be explained in the algorithm The function of each will be explained in the algorithm descriptions
descriptions below. below.
+--------+------------+-------------------------+ +--------+------------+--------------------------+
| Name | Formula | Description | | Name | Formula | Description |
+--------+------------+-------------------------+ +--------+------------+--------------------------+
| t | timer | seconds counter | | t | timer | seconds counter |
| offset | captheta | combined offset | | offset | theta | combined offset |
| resid | captheta_r | residual offset | | resid | theta_r | residual offset |
| freq | phi | clock frequency | | freq | phi | clock frequency |
| jitter | psi | clock jitter | | jitter | psi | clock offset jitter |
| wander | cappsi | frequency wander | | wander | omega | clock frequency wander |
| tc | tau | time constant(log2) | | tc | tau | time constant(log2) |
| state | state | state | | state | state | state |
| adj | adj | frequency adjustment | | adj | adj | frequency adjustment |
| count | count | hysteresis counter | | hyster | hyster | hysteresis counter |
| STEPT | 125 | step threshold (.125 s) | | STEPT | 125 | step threshold (.125 s) |
| WATCH | 900 | stepout thresh(s) | | WATCH | 900 | stepout thresh(s) |
| PANICT | 1000 | panic threshold(1000 s) | | PANICT | 1000 | panic threshold(1000 s) |
| LIMIT | 30 | hysteresis limit | | LIMIT | 30 | hysteresis limit |
| PGATE | 4 | hysteresis gate | | PGATE | 4 | hysteresis gate |
| TC | 16 | time constant scale | | TC | 16 | time constant scale |
| AVG | 8 | averaging constant | | AVG | 8 | averaging constant |
+--------+------------+-------------------------+ +--------+------------+--------------------------+
Table 17: Clock Discipline Variables And Parameters
=====================================================================
| State | captheta < STEP | captheta > STEP | Comments |
---------------------------------------------------------------------
| NSET | > FREQ; adjust | > FREQ; step | no frequency |
| | time | time | file |
---------------------------------------------------------------------
| FSET | > SYNC; adjust | > SYNC; step | frequency file |
| | time | time | |
---------------------------------------------------------------------
| SPIK | > SYNC; adjust | if (<900 s)>SPIK | outlier detected |
| | freq, adjust time | else SYNC; step | |
| | | freq; step time | |
---------------------------------------------------------------------
| FREQ | if (<900 s)> FREQ | if (<900 s)>FREQ | initial frequency |
| | else >SYNC; step | else >SYNC; step | |
| | freq, adjust time | freq, adjust time | |
---------------------------------------------------------------------
| SYNC | >SYNC; adjust freq| if (<900 s)>SPIK | normal operation |
| | adjust time | else >SYNC; step | |
| | | freq; step time | |
---------------------------------------------------------------------
Figure 23 Figure 32: Clock Discipline Variables and Parameters
The discipline is implemented by the local_clock() routine, which is The discipline is implemented by the local_clock() routine, which is
called from the clock_update() routine. The local_clock() routine called from the clock_update() routine. The local_clock() routine in
pseudo code in Appendix A.6.6 has two parts; first the state machine Appendix A.5.5.6 has two parts; the first implements the clock state
shown in Figure 24 and second the algorithm that determines the time machine and the second determines the time constant and thus the poll
constant and thus the poll interval in Figure 25. The state interval.
transition function in Figure 24 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.
---
| A |
---
||
\/
--- yes ---
| B |-->| C |
--- ---
no ||
\/
---
| D |
---
||
\/
--- no --- yes SYNC SPIK FREQ
| E |<--| F |----------------------------------
--- --- || ||
SYNC || \/ \/
SPIKE FSET \/ FREQ NSET --- ---
------------------------- | G | | H |
|| || || || --- ---
|| || \/ \/ || yes || || no
|| || --- --- || || \/
|| --- | H | | I | || || ---
\/ | I | --- --- || || | J |
--- --- no || ||yes || || || ---
| K | || || || \/ || || || || yes
--- || \/ || --- || || || \/
|| || --- || | L | || || || ---
|| || | M ||| --- || || || | M |
|| || --- || || || || || ---
|| || || \/ \/ \/ \/ || ||
|| || || ------------>\/<----------- \/ \/
|| || || --- --->\/<-----
|| || || | N | ---
|| || || --- | O |
|| || || ---
|| || || ||
|| || || \/
|| || || --- --- ---
----->-------->----| P |----><--------| Q |<------| R |
--- || --- ---
--- \/ ||
| S | --- \/
--- | T | ---
|| --- | U |
\/ ---
--- ||
| V | \/
--- ---
|| | W |
\/ ---
---
| X |
---
A: local_clock()
B: |captheta|>PANICT?
C: return(PANIC)
D: freq=0
rval=IGNOR
E:
F: |captheta|>STEPT?
G: state=SPIK
H: mu<WATCH
I: captheta_g=captheta
J: FREQ?
K: Calculate new freq adjustment from captheta, tau, and mu using
hybrid PLL and FLL
L: rst(FREQ,0)
M: freq=((captheta-captheta_B-captheta_R)/mu)
N: return(rval)
O: step_time(captheta)
rval=STEP
P: rval=ADJ
Q: rst(SYNC,0)
R: state=NSET?
S: rst(new,off)
T: tc
U: rst(FREQ,0)
V: state=new
captheta_B=off-captheta_R
captheta_R=off
W: return(rval)
X: return
Figure 24: local_clock() routine (1 of 2)
-----
| A |
-----
\|/
-----
| B |
-----
\|/
-----
| C |-no-----\
----- |
\|/yes |
----- -----
| D | | E |
----- -----
\|/ \|/
----- -----
| F |no\ | G |no\
----- | ----- |
\|/yes| \|/yes|
| | | |
----- | ----- |
| H | | | I | |
----- | ----- |
| J | | | K | |
----- | ----- |
|y no-><-no y| |
---- | ---- |
| L| | | M| |
-------><---------/
\|/
-----
| N |
-----
\|/
-----
| O |
-----
\|/
-----
| P |
-----
A: tc
B: state=SYNC
C: |captheta_g| > PGATE?
D: count -= 2*tau
E: count += tau
F: count <= -LIMIT?
G: count >= LIMIT?
H: count = 0
I: count = 0
J: tau>MINPOLL
K: tau<MAXPOLL
L: tau--
M: tau++
N: phi += freq
O: cappsi = sqrt(expectationvalue(phi^2))
P: return(rval)
Figure 25: local_clock() routine (2 of 2)
The remaining portion of the local_clock() routine is shown in
Figure 25. The time constant tau is determined by comparing the
clock jitter psi with the magnitude of the current residual offset
captheata_R. 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 statistic vartheta and the clock wander statistic The local_clock() routine exits immediately if the offset is greater
cappsi are implemented as exponential averages of RMS offset than the panic threshold PANICT (1000 s). The state transition
differences and RMS frequency differences, respectively. Let x_i be function is implemented by the rstclock() function in
a measurement at time i of either vartheta or cappsi,y_i = x_i - Appendix A.5.5.7. Figure 33 shows the state transition function used
x_(i-1) the first-order sample difference and y_i_HAT the exponential bu this routine. It has four columns showing respectively the state
average. Then, name, predicate and action if the offset theta is less than the step
threshold, the predicate and actions otherwise, and finally some
comments.
y_(i+1)_HAT = sqrt((y_i_HAT)^2+[(y_i)^2-(y_i_HAT)^2)/AVG]) +-------+---------------------+-------------------+--------------+
| State | theta < STEP | theta > STEP | Comments |
+-------+---------------------+-------------------+--------------+
| NSET | ->FREQ | ->FREQ | no frequency |
| | adjust time | step time | file |
+-------+---------------------+-------------------+--------------+
| FSET | ->SYNC | ->SYNC | frequency |
| | adjust time | step time | file |
+-------+---------------------+-------------------+--------------+
| SPIK | ->SYNC | if < 900 s ->SPIK | outlyer |
| | adjust freq | else ->SYNC | detected |
| | adjust time | step freq | |
| | | step time | |
+-------+---------------------+-------------------+--------------+
| FREQ | if < 900 s ->FREQ | if < 900 s ->FREQ | initial |
| | else ->SYNC | else ->SYNC | frequency |
| | step freq | step freq | |
| | adjust time | adjust time | |
+-------+---------------------+-------------------+--------------+
| SYNC | ->SYNC | if < 900 s ->SPIK | normal |
| | adjust freq | else ->SYNC | operation |
| | adjust time | step freq | |
| | | step time | |
+-------+---------------------+-------------------+--------------+
where AVG (4) is the averaging parameter in Table 17, is the Figure 33: State Transition Function
exponential average at time i + 1. The clock jitter statistic is
used by the poll-adjust algorithm above; the clock wander statistic
issued only for performance monitoring.
9.3. Clock Adjust Process In the table entries the next state is identified by the arrow ->
----- with the actions listed below. Actions such as adjust time and
| A | adjust frequency are implemented by the PLL/FLL feedback loop in the
----- local_clock() routine. A step clock action is implemented by setting
\|/ the clock directly, but this is done only after the stepout threshold
----- WATCH (900 s) when the offset is more than the step threshold STEPT
| B | (.125 s). This resists clock steps under conditions of extreme
----- network congestion.
\|/
-----
| C |
-----
\|/
-----
| D |
-----
\|/
-----
| E |
-----
\|/
-----
| F |-----no----\
----- |
\|/yes \|/
----- -----
| H |<--------| G |
----- -----
A: clock_adjust() The jitter (psi) and wander (omega) statistics are computed using an
B: capepsilon += captheta exponential average with weight factor AVG. The time constant
C: tmp = captheta_r/TC(tau) exponent (tau) is determined by comparing psi with the magnitude of
D: captheta_R -= tmp the current offset theta. If the offset is greater than PGATE (4)
E: adjust_time(phi + tmp) times the clock jitter, the hysteresis counter hyster is reduced by
F: next < timer? two; otherwise, it is increased by one. If hyster increases to the
G: poll() upper limit LIMIT (30), tau is increased by one; if it decreases to
H: return the lower limit -LIMIT (-30), tau is decreased by one. Normally, tau
hovers near MAXPOLL, but quickly decreases if a temperature spike
causes a frequency surge.
Figure 26: clock_adjust() Routine 12. Clock Adjust Process
The actual clock adjustment is performed by the clock_adjust() The actual clock adjustment is performed by the clock_adjust()
routine shown in Figure 26 and Appendix A.7.1. It runs at one-second routine in Appendix Appendix A.5.6.1. It runs at one-second
intervals to add the frequency offset in Figure 25 and a fixed intervals to add the frequency correction and a fixed percentage of
percentage of the residual offset captheta_R. The captheta_R is in the residual offset theta_r. The theta_r is in effect the
effect the exponential decay of the captheta value produced by the exponential decay of the theta value produced by the loop filter at
loop filter at each update. The TC parameter scales the time each update. The TC parameter scales the time constant to match the
constant to match the poll interval for convenience. Note that the poll interval for convenience. Note that the dispersion EPSILON
dispersion capepsilon increases by capphi at each second. increases by PHI at each second.
The clock adjust process includes a timer interrupt facility driving The clock adjust process includes a timer interrupt facility driving
the system timer c.t. It begins at zero when the service starts and the seconds counter c.t. It begins at zero when the service starts
increments once each second. At each interrupt the clock_adjust() and increments once each second. At each interrupt the
routine is called to incorporate the clock discipline time and clock_adjust() routine is called to incorporate the clock discipline
frequency adjustments, then the associations are scanned to determine time and frequency adjustments, then the associations are scanned to
if the system timer equals or exceeds the p.next state variable determine if the seconds counter equals or exceeds the p.next state
defined in the next section. If so, the poll process is called to variable defined in the next section. If so, the poll process is
send a packet and compute the next p.next value. called to send a packet and compute the next p.next value.
10. Poll Process 13. Poll Process
Each association supports a poll process that runs at regular Each association supports a poll process that runs at regular
intervals to construct and send packets in symmetric, client and intervals to construct and send packets in symmetric, client and
broadcast server associations. It runs continuously, whether or not broadcast server associations. It runs continuously, whether or not
servers are reachable. The discussion in this section covers the servers are reachable in order to manage the clock filter and reach
variables and routines necessary for a conforming NTPv4 register.
implementation. Further details and rationale for the engineering
design are discussed in [8].
10.1. Poll Process Variables and Parameters 13.1. Poll Process Variables
Figure 34 summarizes the common names, formula names and a short
description of the poll process variables(lower case) and parameters
(upper case). Unless noted otherwise, all variables have assumed
prefix p.
+---------+---------+--------------------+ +---------+---------+--------------------+
| Name | Formula | Description | | Name | Formula | Description |
+---------+---------+--------------------+ +---------+---------+--------------------+
| hpoll | hpoll | host poll exponent | | hpoll | hpoll | host poll exponent |
| last | last | last poll time | | last | last | last poll time |
| next | next | next poll time | | next | next | next poll time |
| reach | reach | reach register | | reach | reach | reach register |
| unreach | unreach | unreach counter | | unreach | unreach | unreach counter |
| UNREACH | 24 | unreach limit | | UNREACH | 24 | unreach limit |
| BCOUNT | 8 | burst count | | BCOUNT | 8 | burst count |
| BURST | flag | burst enable | | BURST | flag | burst enable |
| IBURST | flag | iburst enable | | IBURST | flag | iburst enable |
+---------+---------+--------------------+ +---------+---------+--------------------+
Table 18: Poll Process Variables And Parameters Figure 34: Poll Process Variables
The poll process variables are allocated in the association data The poll process variables are allocated in the association data
structure along with the peer process variables. Table 18 shows the structure along with the peer process variables. Following is a
names, formula names and short definition for each one. Following is detailed description of the variables. The parameters will be called
a detailed description of the variables, all of which carry the p out in the following text.
prefix.
p.hpoll: Signed integer representing the poll exponent, in log2 hpoll: signed integer representing the poll exponent, in log2 seconds
seconds.
p.last: Integer representing the system timer value when the most last: integer representing the seconds counter when the most recent
recent packet was sent. packet was sent
p.next: Integer representing the system timer value when the next next: integer representing the seconds counter when the next packet
packet is to be sent. is to be sent
p.reach: 8-bit integer shift register. When a packet is sent, the reach: 8-bit integer shift register shared by the peer and poll
register is shifted left one bit, with zero entering from the right processes
and overflow bits discarded.
p.unreach: Integer representing the number of seconds the server has unreach: integer representing the number of seconds the server has
been unreachable. been unreachable
10.2. Poll Process Operations 13.2. Poll Process Operations
As described previously, once each second the clock_adjust() routine As described previously, once each second the clock_adjust() routine
MUST be called. This routine calls the poll() routine in in the clock adjust process is called. This routine calls the poll()
Appendix A.8.1 for each association in turn. If the time for the routine in Appendix A.5.7.1 for each association in turn. If the
next poll message is greater than the system timer, the routine MUST time for the next poll message is greater than the seconds counter,
return immediately. A mode-5 (broadcast server) association MUST the routine returns immediately. Symmetric (modes 1, 2), client
send a packet, but a mode-6 (broadcast client) association MUST NOT (mode 3) and broadcast server (mode 5) associations routinely send
send a packet, but MUST run the routine to update the p.reach and packets. A broadcast client (mode 6) association runs the routine to
p.unreach variables. The poll() routine calls the peer_xmit() update the reach and unreach variables, but does not send packets.
routine in Appendix A.8.3 to send a packet. If in a burst (p.burst > The poll() routine calls the peer_xmit() routine in Appendix A.5.7.3
0), nothing further is done except call the poll_update() routine to to send a packet. If in a burst (burst > 0), nothing further is done
set the next poll interval. 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, If not in a burst, the reach variable is shifted left by one bit,
with zero replacing the rightmost bit. If the server has not been with zero replacing the rightmost bit. If the server has not been
heard for the last three poll intervals, the clock_filter() routine heard for the last three poll intervals, the clock_filter() routine
is called to increase the dispersion as described in Section 8.3. If is called to increase the dispersion as described in
the BURST flag is lit and the server is reachable and a valid source Appendix A.5.7.3.
of synchronization is available, the client sends a burst of BCOUNT
(8) packets at each poll interval. This is useful to accurately 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. The interval between
packets in the burst is two seconds. This is useful to accurately
measure jitter with long poll intervals. If the IBURST flag is lit measure jitter with long poll intervals. If the IBURST flag is lit
and this is the first packet sent when the server becomes and this is the first packet sent when the server has been
unreachable, the client sends a burst. This is useful to quickly unreachable, the client sends a burst. This is useful to quickly
reduce the synchronization distance below the distance threshold and reduce the synchronization distance below the distance threshold and
synchronize the clock. The figure also shows the mechanism which synchronize the clock.
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 tau
and operation resumes normally.
When a packet is sent from an association, some header values are If the P_MANY flag is lit in the p.flags word of the association,
copied from the peer variables left by a previous packet and others this is a manycast client association. Manycast client associations
from the system variables. includes a flow diagram and a table send client mode packets to designated multicast group addresses at
showing which values are copied to each header field. In those MINPOLL intervals. The association starts out with a TTL of 1. If
implementations using floating double data types for root delay and by the time of the next poll there are fewer than MINCLOCK servers
root dispersion, these must be converted to NTP short format. All have been mobilized, the ttl is increased by one. If the ttl reaches
other fields are either copied intact from peer and system variables the limit TTLMAX, without finding MINCLOCK servers, the poll interval
or struck as a timestamp from the system clock. increases until reaching BEACON, when it starts over from the
beginning.
The poll_update() routine shown in Appendix A.8.2 is called when a The poll() routine includes a feature that backs off the poll
valid packet is received and immediately after a poll message is interval if the server becomes unreachable. If reach is nonzero, the
sent. If in a burst, the poll interval is fixed at 2 s; otherwise, server is reachable and unreach is set to zero; otherwise, unreach is
the host poll exponent is set to the minimum of p.poll from the last incremented by one for each poll to the maximum UNREACH. Thereafter
packet received and p.hpoll from the poll() routine, but not less for each poll hpoll is increased by one, which doubles the poll
than MINPOLL nor greater than MAXPOLL. Thus the clock discipline can interval up to the maximum MAXPOLL determined by the poll_update()
be oversampled, but not undersampled. This is necessary to preserve routine. When the server again becomes reachable, unreach is set to
subnet dynamic behavior and protect against protocol errors. zero, hpoll is reset to the t.c system variable and operation resumes
Finally, the poll exponent is converted to an interval which normally.
establishes the time at the next poll p.next.
11. Security Considerations A packet is sent by the xmit_packet() routine in Appendix A.3. Some
header values are copied from the peer variables left by a previous
packet and others from the system variables. Figure 35 shows 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.
+-----------------------------------+
| Packet Variable <-- Variable |
+-----------------------------------+
| x.leap <-- s.leap |
| x.version <-- s.version |
| x.mode <-- s.mode |
| x.stratum <-- s.stratum |
| x.poll <-- s.poll |
| x.precision <-- s.precision |
| x.rootdelay <-- s.rootdelay |
| x.rootdisp <-- s.rootdisp |
| x.refid <-- s.refid |
| x.reftime <-- s.reftime |
| x.org <-- p.xmt |
| x.rec <-- p.dst |
| x.xmt <-- clock |
| x.keyid <-- p.keyid |
| x.digest <-- md5 digest |
+-----------------------------------+
Figure 35: xmit_packet Packet Header
The poll_update() routine shown in Appendix A.5.7.2 is called when a
valid packet is received and immediately after a poll message has
been sent. If in a burst, the poll interval is fixed at 2 s;
otherwise, the host poll exponent hpoll is set to the minimum of
ppoll from the last packet received and 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.
The poll exponent is converted to an interval which when added to the
last variable determines the next variable and thus the time for the
next poll. Finally, the last variable is set to the current seconds
counter.
14. Security Considerations
NTPv4 provides an optional authentication field that utilizes the MD5 NTPv4 provides an optional authentication field that utilizes the MD5
algorithm. MD5, as the case for SHA-1, is derived from MD4, which algorithm. MD5, as the case for SHA-1, is derived from MD4, which
has long been known to be weak. In 2004, techniques for efficiently has long been known to be weak. In 2004, techniques for efficiently
finding collisions in MD5 were announced. A summary of the weakness finding collisions in MD5 were announced. A summary of the
of MD5 can be found in [9]. apropriateness of MD5 can be found in [10].
In the case of NTP as specified herein, NTP broadcast clients are In the case of NTP as specified herein, NTP broadcast clients are
vulnerable to disruption by misbehaving or hostile SNTP or NTP vulnerable to disruption by misbehaving or hostile SNTP or NTP
broadcast servers elsewhere in the Internet. Access controls and/or broadcast servers elsewhere in the Internet. Access controls and/or
cryptographic authentication means should be provided for additional cryptographic authentication means should be provided for additional
security in such cases. security in such cases.
12. IANA Considerations 15. IANA Considerations
UDP/TCP Port 123 was previously assigned by IANA for this protocol. UDP/TCP Port 123 was previously assigned by IANA for this protocol.
The IANA has assigned the IPv4 multicast group address 224.0.1.1 and The IANA has assigned the IPv4 multicast group address 224.0.1.1 and
the IPv6 multicast address ending :101 for NTP. This document the IPv6 multicast address ending :101 for NTP. This document
introduces NTP extension fields allowing for the development of introduces NTP extension fields allowing for the development of
future extensions to the protocol, where a particular extension is to future extensions to the protocol, where a particular extension is to
be identified by the Field Type sub-field within the extension field. be identified by the Field Type sub-field within the extension field.
IANA is requested to establish and maintain a registry for Extension IANA is requested to establish and maintain a registry for Extension
Field Types associated with this protocol, populating this registry Field Types associated with this protocol, populating this registry
with no initial entries. As future needs arise, new Extension Field with no initial entries. As future needs arise, new Extension Field
Types may be defined. Following the policies outlined in [10], new Types may be defined. Following the policies outlined in [11], new
values are to be defined by IETF Consensus. consensus.
13. Acknowledgements 16. Acknowledgements
This authors would like to thank Karen O'Donoghue, Brian Haberman, The editors would like to thank Karen O'Donoghue, Brian Haberman,
Greg Dowd, Mark Elliot, and Harlan Stenn for technical reviews of Greg Dowd, Mark Elliot, and Harlan Stenn for technical reviews of
this document. this document.
14. Informative References 17. Informative References
[1] Mills, D., "Network Time Protocol (Version 3) Specification, [1] Mills, D., "Network Time Protocol (Version 3) Specification,
Implementation", RFC 1305, March 1992. Implementation and Analysis", RFC 1305, Current Status DRAFT
STANDARD, March 1992.
[2] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for [2] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for
IPv4, IPv6 and OSI", RFC 4330, January 2006. IPv4, IPv6 and OSI", RFC 4330, draft-mills-sntp-v4-01 (work in
progress), Current Status INFORMATIONAL, January 2006.
[3] University of Delaware, "The Autokey security architecture, [3] Mills, D.L., "The Autokey security architecture, protocol and
protocol and algorithms. Electrical and Computer Engineering algorithms. Electrical and Computer Engineering Technical
Technical Report 06-1-1", NDSS , January 2006. Report 06-1-1", NDSS , January 2006.
[4] Bradner, S., "Key words for use in RFCs to Indicate Requirement [4] Mills, D.L., Electrical and Computer Engineering Technical
Levels", BCP 14, RFC 2119, March 1997. Report 06-6-1, NDSS, June 2006., "Network Time Protocol Version
4 Reference and Implementation Guide.", 2006.
[5] Postel, J., "Internet Protocol", STD 5, RFC 791, [5] Mills, D.L., "Computer Network Time Synchronization - the
September 1981. Network Time Protocol. CRC Press, 304pp.", 2006.
[6] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, [6] Bradner, S., "Key words for use in RFCs to Indicate Requirement
April 1992. Levels", BCP 14, RFC 2119, Current Status BEST CURRENT
PRACTICE, March 1997.
[7] Marzullo and S. Owicki, "Maintaining the time in a distributed [7] Postel, J., "Internet Protocol", STD 5, RFC 791, Updated
system.", ACM Operating Systems Review 19 , July 1985. by RFC1349, Current Status STANDARD, September 1981.
[8] Mills, D. L., "Computer Network Time Synchronization - the [8] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
Network Time Protocol. CRC Press, 304pp.", 2006. Current Status INFORMATIONAL, April 1992.
[9] Bellovin, S. and E. Rescorla, Proceedings of the 13th annual [9] Marzullo and S. Owicki, "Maintaining the time in a distributed
system.", ACM Operating Systems Review 19 , July 1985.
[10] Bellovin, S. and E. Rescorla, Proceedings of the 13th annual
ISOC Network and Distributed System Security Symposium, ISOC Network and Distributed System Security Symposium,
"Deploying a new Hash Algorithm", February 2006. "Deploying a new Hash Algorithm", February 2006.
[10] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA [11] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
Considerations Section in RFCs", BCP 26, RFC 2434, Considerations Section in RFCs", BCP 26, RFC 2434, Updated
October 1998. by RFC3692, Current Status BEST CURRENT PRACTICE, October 1998.
Appendix A. Code Skeleton Appendix A. Code Skeleton
This appendix is intended to describe the protocol and algorithms of This appendix is intended to describe the protocol and algorithms of
an implementation in a general way using what is called a code an implementation in a general way using what is called a code
skeleton program. This consists of a set of definitions, structures skeleton program. This consists of a set of definitions, structures
and code segments which illustrate the protocol operations without and code fragments which illustrate the protocol operations without
the complexities of an actual implementation of the protocol. This the complexities of an actual implementation of the protocol. This
program is not an executable and is not designed to run in the program is not an executable and is not designed to run in the
ordinary sense. It is designed to be compiled only in order to ordinary sense. It is designed to be compiled only in order to
verify consistent variable and type usage. The program is not verify consistent variable and type usage.
intended to be fast or compact, just to demonstrate the algorithms
with sufficient fidelity to understand how they work. The code
skeleton consists of eight segments, a header segment included by
each of the other segments, plus a code segment for the main program,
kernel I/O and system clock interfaces, and peer, system,
clock_adjust and poll processes. These are presented in order below
along with definitions and variables specific to each process.
A.1. Global Definitions Most of the features of the reference implementation are included
here, with the following exceptions: There are no provisions for
reference clocks or public key (Autokey) cryptography. There is no
huff-n'-puff filter, anti-clockhop hysteresis or monitoring
provisions. Many of the values that can be tinkered in the reference
implementation are assumed constants here. There are only minimal
provisions for the kiss-o'death packet and no responding code.
Following are definitions and other data shared by all programs. The program is not intended to be fast or compact, just to
These values are defined in a header file ntp4.h which is included in demonstrate the algorithms with sufficient fidelity to understand how
all files. they work. The code skeleton consists of eight segments, a header
segment included by each of the other segments, plus a code segment
for the main program, kernel I/O and system clock interfaces, and
peer, system, clock_adjust and poll processes. These are presented
in order below along with definitions and variables specific to each
process.
A.1. Global Definitions
A.1.1. Definitions, Constants, Parameters A.1.1. Definitions, Constants, Parameters
#include <math.h> s/* avoids complaints about sqrt() */
#include <math.h> /* avoids complaints about sqrt() */
#include <sys/time.h> /* for gettimeofday() and friends */ #include <sys/time.h> /* for gettimeofday() and friends */
#include <stdlib.h> /* for malloc() and friends */ #include <stdlib.h> /* for malloc() and friends */
/* /*
* Data types * Data types
* *
* This program assumes the int data type is 32 bits and the long data * This program assumes the int data type is 32 bits and the long data
* type is 64 bits. The native data type used in most calculations is * type is 64 bits. The native data type used in most calculations is
* floating double. The data types used in some packet header fields * floating double. The data types used in some packet header fields
* require conversion to and from this representation. Some header * require conversion to and from this representation. Some header
* fields involve partitioning an octet, here represented by individual * fields involve partitioning an octet, here represeted by individual
* octets. * octets.
* *
* The 64-bit NTP timestamp format used in timestamp calculations is * The 64-bit NTP timestamp format used in timestamp calculations is
* unsigned seconds and fraction with the decimal point to the left of * unsigned seconds and fraction with the decimal point to the left of
* bit 32. The only operation permitted with these values is * bit 32. The only operation permitted with these values is
* subtraction, yielding a signed 31-bit difference. The 32-bit NTP * subtraction, yielding a signed 31-bit difference. The 32-bit NTP
* short format used in delay and dispersion calculations is seconds and * short format used in delay and dispersion calculations is seconds and
* fraction with the decimal point to the left of bit 16. The only * fraction with the decimal point to the left of bit 16. The only
* operations permitted with these values are addition and * operations permitted with these values are addition and
* multiplication by a constant. * multiplication by a constant.
* *
* The IPv4 address is 32 bits, while the IPv6 address is 128 bits. The * The IPv4 address is 32 bits, while the IPv6 address is 128 bits. The
* message digest field is 128 bits as constructed by the MD5 algorithm. * message digest field is 128 bits as constructed by the MD5 algorithm.
* The precision and poll interval fields are signed log2 seconds. * The precision and poll interval fields are signed log2 seconds.
*/ */
typedef unsigned long tstamp; typedef unsigned long tstamp; /* NTP timestamp format */
typedef unsigned int tdist; typedef unsigned int tdist; /* NTP short format */
typedef unsigned long ipaddr; typedef unsigned long ipaddr; /* IPv4 or IPv6 address */
typedef unsinged int ipport; typedef unsigned long digest; /* md5 digest */
typedef unsigned long digest; typedef signed char s_char; /* precision and poll interval (log2) */
typedef signed char s_char;
/* /*
* Arithmetic conversion macroni * Timestamp conversion macroni
*/ */
#define FRIC 65536. /* 2^16 as a double */
#define D2FP(r) ((tdist)((r) * FRIC)) /* NTP short */
#define FP2D(r) ((double)(r) / FRIC)
/* NTP timestamp format */ #define FRAC 4294967296. /* 2^32 as a double */
/* NTP short format */ #define D2LFP(a) ((tstamp)((a) * FRAC)) /* NTP timestamp */
/* IPv4 or IPv6 address */
/* IP port number */
/* md5 digest */
/* precision and poll interval (log2) */
#define LOG2D(a) ((a) < 0 ? 1. / (1L << -(a)) : \ #define LFP2D(a) ((double)(a) / FRAC)
#define U2LFP(a) ((a).tv_sec + JAN_1970 << 32 + (unsigned long) \
((a).tv_usec / 1e6 * FRAC))
/*
* Arithmetic conversions
*/
#define LOG2D(a) ((a) < 0 ? 1. / (1L << -(a)) : \
1L << (a)) /* poll, etc. */ 1L << (a)) /* poll, etc. */
#define LFP2D(a) ((double)(a) / 0x100000000L) /* NTP timestamp */
#define D2LFP(a) ((tstamp)((a) * 0x100000000L))
#define FP2D(a) (double)(a) / 0x10000L) /* NTP short */
#define D2FP(a) ((tdist)((a) * 0x10000L))
#define SQUARE(x) (x * x) #define SQUARE(x) (x * x)
#define SQRT(x) (sqrt(x)) #define SQRT(x) (sqrt(x))
/* /*
* Global constants. Some of these might be converted to variables * Global constants. Some of these might be converted to variables
* which can be tinkered by configuration or computed on-fly. For * which can be tinkered by configuration or computed on-fly. For
* instance, PRECISION could be calculated on-fly and * instance, the reference implementation computes PRECISION on-fly and
* provide performance tuning for the defines marked with % below. * provides performance tuning for the defines marked with % below.
*/ */
#define VERSION 4 /* version number */ #define VERSION 4 /* version number */
#define PORT 123 /* NTP poert number */
#define MINDISP .01 /* % minimum dispersion (s) */ #define MINDISP .01 /* % minimum dispersion (s) */
#define MAXDISP 16 /* % maximum dispersion (s) */ #define MAXDISP 16 /* maximum dispersion (s) */
#define MAXDIST 1 /* % distance threshold (s) */ #define MAXDIST 1 /* % distance threshold (s) */
#define NOSYNC 3 /* leap unsync */ #define NOSYNC 0x3 /* leap unsync */
#define MAXSTRAT 16 /* maximum stratum (infinity metric) */ #define MAXSTRAT 16 /* maximum stratum (infinity metric) */
#define MINPOLL 4 /* % minimum poll interval (16 s)*/ #define MINPOLL 6 /* % minimum poll interval (64 s)*/
#define MAXPOLL 17 /* % maximum poll interval (36.4 h) */ #define MAXPOLL 17 /* % maximum poll interval (36.4 h) */
#define MINCLOCK 3 /* minimum manycast survivors */
#define MAXCLOCK 10 /* maximum manycast candidates */
#define TTLMAX 8 /* max ttl manycast */
#define BEACON 15 /* max interval between beacons */
#define PHI 15e-6 /* % frequency tolerance (15 PPM) */ #define PHI 15e-6 /* % frequency tolerance (15 PPM) */
#define NSTAGE 8 /* clock register stages */ #define NSTAGE 8 /* clock register stages */
#define NMAX 50 /* % maximum number of peers */ #define NMAX 50 /* maximum number of peers */
#define NSANE 1 /* % minimum intersection survivors */ #define NSANE 1 /* % minimum intersection survivors */
#define NMIN 3 /* % minimum cluster survivors */ #define NMIN 3 /* % minimum cluster survivors */
/* /*
* Global return values * Global return values
*/ */
#define TRUE 1 /* boolean true */ #define TRUE 1 /* boolean true */
#define FALSE 0 /* boolean false */ #define FALSE 0 /* boolean false */
#define NULL 0 /* empty pointer */ #define NULL 0 /* empty pointer */
skipping to change at page 71, line 38 skipping to change at page 60, line 24
/* /*
* Peer flags * Peer flags
*/ */
#define P_FLAGS 0 /* any peer flags */ #define P_FLAGS 0 /* any peer flags */
#define P_EPHEM 0x01 /* association is ephemeral */ #define P_EPHEM 0x01 /* association is ephemeral */
#define P_BURST 0x02 /* burst enable */ #define P_BURST 0x02 /* burst enable */
#define P_IBURST 0x04 /* intial burst enable */ #define P_IBURST 0x04 /* intial burst enable */
#define P_NOTRUST 0x08 /* authenticated access */ #define P_NOTRUST 0x08 /* authenticated access */
#define P_NOPEER 0x10 /* authenticated mobilization */ #define P_NOPEER 0x10 /* authenticated mobilization */
#define P_MANY 0x20 /* manycast client */
/* /*
* Authentication codes * Authentication codes
*/ */
#define A_NONE 0 /* no authentication */ #define A_NONE 0 /* no authentication */
#define A_OK 1 /* authentication OK */ #define A_OK 1 /* authentication OK */
#define A_ERROR 2 /* authentication error */ #define A_ERROR 2 /* authentication error */
#define A_CRYPTO 3 /* crypto-NAK */ #define A_CRYPTO 3 /* crypto-NAK */
/* /*
skipping to change at page 73, line 12 skipping to change at page 61, line 49
char poll; /* poll interval */ char poll; /* poll interval */
s_char precision; /* precision */ s_char precision; /* precision */
tdist rootdelay; /* root delay */ tdist rootdelay; /* root delay */
tdist rootdisp; /* root dispersion */ tdist rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
tstamp org; /* origin timestamp */ tstamp org; /* origin timestamp */
tstamp rec; /* receive timestamp */ tstamp rec; /* receive timestamp */
tstamp xmt; /* transmit timestamp */ tstamp xmt; /* transmit timestamp */
int keyid; /* key ID */ int keyid; /* key ID */
digest digest; /* message digest */ digest mac; /* message digest */
tstamp dst; /* destination timestamp */ tstamp dst; /* destination timestamp */
} r; } r;
/* /*
* Transmit packet * Transmit packet
*/ */
struct x { struct x {
ipaddr dstaddr; /* source (local) address */ ipaddr dstaddr; /* source (local) address */
ipaddr srcaddr; /* destination (remote) address */ ipaddr srcaddr; /* destination (remote) address */
char version; /* version number */ char version; /* version number */
char leap; /* leap indicator */ char leap; /* leap indicator */
char mode; /* mode */ char mode; /* mode */
char stratum; /* stratum */ char stratum; /* stratum */
skipping to change at page 73, line 36 skipping to change at page 62, line 24
char poll; /* poll interval */ char poll; /* poll interval */
s_char precision; /* precision */ s_char precision; /* precision */
tdist rootdelay; /* root delay */ tdist rootdelay; /* root delay */
tdist rootdisp; /* root dispersion */ tdist rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
tstamp org; /* origin timestamp */ tstamp org; /* origin timestamp */
tstamp rec; /* receive timestamp */ tstamp rec; /* receive timestamp */
tstamp xmt; /* transmit timestamp */ tstamp xmt; /* transmit timestamp */
int keyid; /* key ID */ int keyid; /* key ID */
digest digest; /* message digest */ digest mac; /* message digest */
} x; } x;
A.1.3. Association Data Structures A.1.3. Association Data Structures
/* /*
* Filter stage structure. Note the t member in this and other * Filter stage structure. Note the t member in this and other
* structures refers to process time, not real time. Process time * structures refers to process time, not real time. Process time
* increments by one second for every elapsed second of real time. * increments by one second for every elapsed second of real time.
*/ */
struct f { struct f {
skipping to change at page 74, line 16 skipping to change at page 62, line 51
/* /*
* Association structure. This is shared between the peer process and * Association structure. This is shared between the peer process and
* poll process. * poll process.
*/ */
struct p { struct p {
/* /*
* Variables set by configuration * Variables set by configuration
*/ */
ipaddr srcaddr; /* source (remote) address */ ipaddr srcaddr; /* source (remote) address */
ipport srcport; /* source port number *.
ipaddr dstaddr; /* destination (local) address */ ipaddr dstaddr; /* destination (local) address */
ipport dstport; /* destination port number */
char version; /* version number */ char version; /* version number */
char mode; /* mode */ char hmode; /* host mode */
int keyid; /* key identifier */ int keyid; /* key identifier */
int flags; /* option flags */ int flags; /* option flags */
/* /*
* Variables set by received packet * Variables set by received packet
*/ */
char leap; /* leap indicator */ char leap; /* leap indicator */
char mode; /* mode */ char pmode; /* peer mode */
char stratum; /* stratum */ char stratum; /* stratum */
char ppoll; /* peer poll interval */ char ppoll; /* peer poll interval */
double rootdelay; /* root delay */ double rootdelay; /* root delay */
double rootdisp; /* root dispersion */ double rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
#define begin_clear org /* beginning of clear area */ #define begin_clear org /* beginning of clear area */
tstamp org; /* originate timestamp */ tstamp org; /* originate timestamp */
tstamp rec; /* receive timestamp */ tstamp rec; /* receive timestamp */
tstamp xmt; /* transmit timestamp */ tstamp xmt; /* transmit timestamp */
skipping to change at page 75, line 8 skipping to change at page 63, line 41
double delay; /* peer delay */ double delay; /* peer delay */
double disp; /* peer dispersion */ double disp; /* peer dispersion */
double jitter; /* RMS jitter */ double jitter; /* RMS jitter */
/* /*
* Poll process variables * Poll process variables
*/ */
char hpoll; /* host poll interval */ char hpoll; /* host poll interval */
int burst; /* burst counter */ int burst; /* burst counter */
int reach; /* reach register */ int reach; /* reach register */
int ttl; /* ttl (manycast) */
#define end_clear unreach /* end of clear area */ #define end_clear unreach /* end of clear area */
int unreach; /* unreach counter */ int unreach; /* unreach counter */
int last; /* last poll time */ int outdate; /* last poll time */
int next; /* next poll time */ int nextdate; /* next poll time */
} p; } p;
A.1.4. System Data Structures A.1.4. System Data Structures
/* /*
* Chime list. This is used by the intersection algorithm. * Chime list. This is used by the intersection algorithm.
*/ */
struct m { /* m is for Marzullo */ struct m { /* m is for Marzullo */
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
int type; /* high +1, mid 0, low -1 */ int type; /* high +1, mid 0, low -1 */
skipping to change at page 76, line 42 skipping to change at page 64, line 43
double rootdelay; /* root delay */ double rootdelay; /* root delay */
double rootdisp; /* root dispersion */ double rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
struct m m[NMAX]; /* chime list */ struct m m[NMAX]; /* chime list */
struct v v[NMAX]; /* survivor list */ struct v v[NMAX]; /* survivor list */
struct p *p; /* association ID */ struct p *p; /* association ID */
double offset; /* combined offset */ double offset; /* combined offset */
double jitter; /* combined jitter */ double jitter; /* combined jitter */
int flags; /* option flags */ int flags; /* option flags */
int n; /* number of survivors */
} s; } s;
A.1.5. Local Clock Data Structures A.1.5. Local Clock Data Structures
/* /*
* Local clock structure * Local clock structure
*/ */
struct c { struct c {
tstamp t; /* update time */ tstamp t; /* update time */
int state; /* current state */ int state; /* current state */
double offset; /* current offset */ double offset; /* current offset */
double base; /* base offset */
double last; /* previous offset */ double last; /* previous offset */
int count; /* jiggle counter */ int count; /* jiggle counter */
double freq; /* frequency */ double freq; /* frequency */
double jitter; /* RMS jitter */ double jitter; /* RMS jitter */
double wander; /* RMS wander */ double wander; /* RMS wander */
} c; } c;
A.1.6. Function Prototypes A.1.6. Function Prototypes
/* /*
* Peer process * Peer process
*/ */
void receive(struct r *); /* receive packet */ void receive(struct r *); /* receive packet */
void fast_xmit(struct r *, int, int); void packet(struct p *, struct r *); /* process packet */
/* transmit a reply packet */ void clock_filter(struct p *, double, double, double); /* filter */
struct p *find_assoc(struct r *); double root_dist(struct p *); /* calculate root distance */
/* search the association table */ int fit(struct p *); /* determine fitness of server */
void packet(struct p *, struct r *); void clear(struct p *, int); /* clear association */
/* process packet */ int access(struct r *); /* determine access restrictions */
void clock_filter(struct p *, double, double, double);
/* filter */
int accept(struct p *);
/* determine fitness of server */
int access(struct r *);
/* determine access restrictions */
/* /*
* System process * System process
*/ */
int main(); /* main program */
void clock_select(); /* find the best clocks */ void clock_select(); /* find the best clocks */
void clock_update(struct p *); /* update the system clock */ void clock_update(struct p *); /* update the system clock */
void clock_combine(); /* combine the offsets */ void clock_combine(); /* combine the offsets */
double root_dist(struct p *); /* calculate root distance */
/* /*
* Clock discipline process * Local clock process
*/ */
int local_clock(struct p *, double); /* clock discipline */ int local_clock(struct p *, double); /* clock discipline */
void rstclock(int, double, double); /* clock state transition */ void rstclock(int, double, double); /* clock state transition */
/* /*
* Clock adjust process * Clock adjust process
*/ */
void clock_adjust(); /* one-second timer process */ void clock_adjust(); /* one-second timer process */
/* /*
* Poll process * Poll process
*/ */
void poll(struct p *); /* poll process */ void poll(struct p *); /* poll process */
void poll_update(struct p *, int); /* update the poll interval */ void poll_update(struct p *, int); /* update the poll interval */
void peer_xmit(struct p *); /* transmit a packet */ void peer_xmit(struct p *); /* transmit a packet */
void fast_xmit(struct r *, int, int); /* transmit a reply packet */
/* /*
* Main program and utility routines * Utility routines
*/ */
int main(); /* main program */
struct p *mobilize(ipaddr, ipaddr, int, int, int, int);
/* mobilize */
void clear(struct p *, int); /* clear association */
digest md5(int); /* generate a message digest */ digest md5(int); /* generate a message digest */
struct p *mobilize(ipaddr, ipaddr, int, int, int, int); /* mobilize */
struct p *find_assoc(struct r *); /* search the association table */
/* /*
* Kernel I/O Interface * Kernel interface
*/ */
struct r *recv_packet(); /* wait for packet */ struct r *recv_packet(); /* wait for packet */
void xmit_packet(struct x *); /* send packet */ void xmit_packet(struct x *); /* send packet */
/*
* Kernel system clock interface
*/
void step_time(double); /* step time */ void step_time(double); /* step time */
void adjust_time(double); /* adjust (slew) time */ void adjust_time(double); /* adjust (slew) time */
tstamp get_time(); /* read time */ tstamp get_time(); /* read time */
A.2. Main Program and Utility Routines A.2. Main Program and Utility Routines
#include "ntp4.h"
/* /*
* Definitions * Definitions
*/ */
#define PRECISION -18 /* precision (log2 s) */ #define PRECISION -18 /* precision (log2 s) */
#define IPADDR 0 /* any IP address */ #define IPADDR 0 /* any IP address */
#define MODE 0 /* any NTP mode */ #define MODE 0 /* any NTP mode */
#define KEYID 0 /* any key identifier */ #define KEYID 0 /* any key identifier */
/* /*
* main() - main program * main() - main program
*/ */
int int
main() main()
{ {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
struct r *r; /* receive packet pointer */ struct r *r; /* receive packet pointer */
/* /*
skipping to change at page 79, line 15 skipping to change at page 66, line 49
* main() - main program * main() - main program
*/ */
int int
main() main()
{ {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
struct r *r; /* receive packet pointer */ struct r *r; /* receive packet pointer */
/* /*
* Read command line options and initialize system variables. * Read command line options and initialize system variables.
* Implementations MAY measure the precision specific * The reference implementation measures the precision specific
* to each machine by measuring the clock increments to read the * to each machine by measuring the clock increments to read the
* system clock. * system clock.
*/ */
memset(&s, sizeof(s), 0); memset(&s, sizeof(s), 0);
s.leap = NOSYNC; s.leap = NOSYNC;
s.stratum = MAXSTRAT; s.stratum = MAXSTRAT;
s.poll = MINPOLL; s.poll = MINPOLL;
s.precision = PRECISION; s.precision = PRECISION;
s.p = NULL; s.p = NULL;
/* /*
* Initialize local clock variables * Initialize local clock variables
skipping to change at page 80, line 4 skipping to change at page 67, line 39
*/ */
while (/* mobilize configurated associations */ 0) { while (/* mobilize configurated associations */ 0) {
p = mobilize(IPADDR, IPADDR, VERSION, MODE, KEYID, p = mobilize(IPADDR, IPADDR, VERSION, MODE, KEYID,
P_FLAGS); P_FLAGS);
} }
/* /*
* Start the system timer, which ticks once per second. Then * Start the system timer, which ticks once per second. Then
* read packets as they arrive, strike receive timestamp and * read packets as they arrive, strike receive timestamp and
* call the receive() routine. * call the receive() routine.
*/ */
while (0) { while (0) {
r = recv_packet(); r->dst = get_time(); receive(r); r = recv_packet();
r->dst = get_time();
receive(r);
} }
} }
/* /*
* mobilize() - mobilize and initialize an association * mobilize() - mobilize and initialize an association
*/ */
struct p struct p
*mobilize( *mobilize(
ipaddr srcaddr, /* IP source address */ ipaddr srcaddr, /* IP source address */
ipaddr dstaddr, /* IP destination address */ ipaddr dstaddr, /* IP destination address */
skipping to change at page 80, line 31 skipping to change at page 68, line 18
int flags /* peer flags */ int flags /* peer flags */
) )
{ {
struct p *p; /* peer process pointer */ struct p *p; /* peer process pointer */
/* /*
* Allocate and initialize association memory * Allocate and initialize association memory
*/ */
p = malloc(sizeof(struct p)); p = malloc(sizeof(struct p));
p->srcaddr = srcaddr; p->srcaddr = srcaddr;
p->srcport = PORT;
p->dstaddr = dstaddr; p->dstaddr = dstaddr;
p->dstport = PORT;
p->version = version; p->version = version;
p->mode = mode; p->hmode = mode;
p->keyid = keyid; p->keyid = keyid;
p->hpoll = MINPOLL; p->hpoll = MINPOLL;
clear(p, X_INIT); clear(p, X_INIT);
p->flags == flags; p->flags == flags;
return (p); return (p);
} }
/* /*
* clear() - reinitialize for persistent association, demobilize * find_assoc() - find a matching association
* for ephemeral association.
*/ */
void struct p /* peer structure pointer or NULL */
clear( *find_assoc(
struct p *p, /* peer structure pointer */ struct r *r /* receive packet pointer */
int kiss /* kiss code */
) )
{ {
int i; struct p *p; /* dummy peer structure pointer */
/* /*
* The first thing to do is return all resources to the bank. * Search association table for matching source
* Typical resources are not detailed here, but they include * address, source port and mode.
* dynamically allocated structures for keys, certificates, etc.
* If an ephemeral association and not initialization, return
* the association memory as well.
*/ */
/* return resources */ while (/* all associations */ 0) {
if (s.p == p) if (r->srcaddr == p->srcaddr && r->mode == p->hmode)
s.p = NULL; return(p);
if (kiss != X_INIT && (p->flags & P_EPHEM)) {
free(p);
return;
} }
return (NULL);
/*
* Initialize the association fields for general reset.
*/
memset(BEGIN_CLEAR(p), LEN_CLEAR, 0); p->leap = NOSYNC;
p->stratum = MAXSTRAT;
p->ppoll = MAXPOLL;
p->hpoll = MINPOLL;
p->disp = MAXDISP;
p->jitter = LOG2D(s.precision); p->refid = kiss;
for (i = 0; i < NSTAGE; i++)
p->f[i].disp = MAXDISP;
/*
* Randomize the first poll just in case thousands of broadcast
* clients have just been stirred up after a long absence of the
* broadcast server.
*/
p->last = p->t = c.t;
p->next = p->last + (random() & ((1 << MINPOLL) - 1));
} }
/* /*
* md5() - compute message digest * md5() - compute message digest
*/ */
digest digest
md5( md5(
int keyid /* key identifier */ int keyid /* key identifier */
) )
{ {
/* /*
* Compute a keyed cryptographic message digest. The key * Compute a keyed cryptographic message digest. The key
* identifier is associated with a key in the local key cache. * identifier is associated with a key in the local key cache.
* The key is prepended to the packet header and extension fieds * The key is prepended to the packet header and extension fieds
* and the result hashed by the MD5 algorithm as described in * and the result hashed by the MD5 algorithm as described in
skipping to change at page 82, line 40 skipping to change at page 69, line 48
xmit_packet( xmit_packet(
struct x *x /* transmit packet pointer */ struct x *x /* transmit packet pointer */
) )
{ {
/* send packet x */ /* send packet x */
} }
A.4. Kernel System Clock Interface A.4. Kernel System Clock Interface
/* /*
* System clock utility functions
*
* There are three time formats: native (Unix), NTP and floating double. * There are three time formats: native (Unix), NTP and floating double.
* The get_time() routine returns the time in NTP long format. The Unix * The get_time() routine returns the time in NTP long format. The Unix
* routines expect arguments as a structure of two signed 32-bit words * routines expect arguments as a structure of two signed 32-bit words
* in seconds and microseconds (timeval) or nanoseconds (timespec). The * in seconds and microseconds (timeval) or nanoseconds (timespec). The
* step_time() and adjust_time() routines expect signed arguments in * step_time() and adjust_time() routines expect signed arguments in
* floating double. The simplified code shown here is for illustration * floating double. The simplified code shown here is for illustration
* only and has not been verified. * only and has not been verified.
*/ */
#define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */ #define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */
skipping to change at page 83, line 19 skipping to change at page 70, line 28
struct timeval unix_time; struct timeval unix_time;
/* /*
* There are only two calls on this routine in the program. One * There are only two calls on this routine in the program. One
* when a packet arrives from the network and the other when a * when a packet arrives from the network and the other when a
* packet is placed on the send queue. Call the kernel time of * packet is placed on the send queue. Call the kernel time of
* day routine (such as gettimeofday()) and convert to NTP * day routine (such as gettimeofday()) and convert to NTP
* format. * format.
*/ */
gettimeofday(&unix_time, NULL); gettimeofday(&unix_time, NULL);
return (U2LFP(unix_time));
return ((unix_time.tv_sec + JAN_1970) * 0x100000000L +
(unix_time.tv_usec * 0x100000000L) / 1000000);
} }
/* /*
* step_time() - step system time to given offset valuet * step_time() - step system time to given offset valuet
*/ */
void void
step_time( step_time(
double offset /* clock offset */ double offset /* clock offset */
) )
{ {
struct timeval unix_time; struct timeval unix_time;
tstamp ntp_time; tstamp ntp_time;
/* /*
* Convert from double to native format (signed) and add to the * Convert from double to native format (signed) and add to the
* current time. Note the addition is done in native format to * current time. Note the addition is done in native format to
* avoid overflow or loss of precision. * avoid overflow or loss of precision.
*/ */
ntp_time = D2LFP(offset); gettimeofday(&unix_time, NULL); gettimeofday(&unix_time, NULL);
unix_time.tv_sec += ntp_time / 0x100000000L; ntp_time = D2LFP(offset) + U2LFP(unix_time);;
unix_time.tv_usec += ntp_time % 0x100000000L; unix_time.tv_sec = ntp_time >> 32;
unix_time.tv_sec += unix_time.tv_usec / 1000000; unix_time.tv_usec = (long)((ntp_time - unix_time.tv_sec <<
unix_time.tv_usec %= 1000000; 32) / FRAC * 1e6);
settimeofday(&unix_time, NULL); settimeofday(&unix_time, NULL);
} }
/* /*
* adjust_time() - slew system clock to given offset value * adjust_time() - slew system clock to given offset value
*/ */
void void
adjust_time( adjust_time(
double offset /* clock offset */ double offset /* clock offset */
) )
{ {
struct timeval unix_time; struct timeval unix_time;
tstamp ntp_time; tstamp ntp_time;
/* /*
* Convert from double to native format (signed) and add to the * Convert from double to native format (signed) and add to the
* current time. * current time.
*/ */
ntp_time = D2LFP(offset); ntp_time = D2LFP(offset);
unix_time.tv_sec = ntp_time / 0x100000000L; unix_time.tv_sec = ntp_time >> 32;
unix_time.tv_usec = ntp_time % 0x100000000L; unix_time.tv_usec = (long)((ntp_time - unix_time.tv_sec <<
unix_time.tv_sec += unix_time.tv_usec / 1000000; 32) / FRAC * 1e6);
unix_time.tv_usec %= 1000000;
adjtime(&unix_time, NULL); adjtime(&unix_time, NULL);
} }
A.5. Peer Process A.5. Peer Process
#include "ntp4.h"
/* /*
* A crypto-NAK packet includes the NTP header followed by a MAC * A crypto-NAK packet includes the NTP header followed by a MAC
* consisting only of the key identifier with value zero. It tells the * consisting only of the key identifier with value zero. It tells the
* receiver that a prior request could not be properly authenticated, * receiver that a prior request could not be properly authenticated,
* but the NTP header fields are correct. * but the NTP header fields are correct.
* *
* A kiss-o'-death packet has an NTP header with leap 3 (NOSYNC) and * A kiss-o'-death packet is an NTP header with leap 0x3 (NOSYNC) and
* stratum 0. It tells the receiver that something drastic * stratum 16 (MAXSTRAT. It tells the receiver that something drastic
* has happened, as revealled by the kiss code in the refid field. The * has happened, as revealled by the kiss code in the refid field. The
* NTP header fields may or may not be correct. * NTP header fields may or may not be correct.
*/ */
/* /*
* Definitions * Peer process parameters and constants
*/ */
#define SGATE 3 /* spike gate (clock filter */ #define SGATE 3 /* spike gate (clock filter */
#define BDELAY .004 /* broadcast delay (s) */ #define BDELAY .004 /* broadcast delay (s) */
/* /*
* Dispatch codes * Dispatch codes
*/ */
#define ERR -1 /* error */ #define ERR -1 /* error */
#define DSCRD 0 /* discard packet */ #define DSCRD 0 /* discard packet */
#define PROC 1 /* process packet */ #define PROC 1 /* process packet */
#define BCST 2 /* broadcast packet */ #define BCST 2 /* broadcast packet */
#define FXMIT 3 /* client packet */ #define FXMIT 3 /* client packet */
#define NEWPS 4 /* new symmetric passive client */ #define NEWPS 4 /* new symmetric passive client */
#define NEWBC 5 /* new broadcast client */ #define NEWBC 5 /* new broadcast client */
/* /*
* Dispatch matrix * Dispatch matrix
* active passv client server bcast */ * active passv client server bcast */
int table[7][5] = { int table[7][5] = {
/* nopeer */{ NEWPS, DSCRD, FXMIT, DSCRD, NEWBC }, /* nopeer */ { NEWPS, DSCRD, FXMIT, MANY, NEWBC },
/* active */{ PROC, PROC, DSCRD, DSCRD, DSCRD }, /* active */{ PROC, PROC, DSCRD, DSCRD, DSCRD },
/* passv */{ PROC, ERR, DSCRD, DSCRD, DSCRD }, /* passv */{ PROC, ERR, DSCRD, DSCRD, DSCRD },
/* client */{ DSCRD, DSCRD, DSCRD, PROC, DSCRD }, /* client */{ DSCRD, DSCRD, DSCRD, PROC, DSCRD },
/* server */{ DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, /* server */{ DSCRD, DSCRD, DSCRD, DSCRD, DSCRD },
/* bcast */{ DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, /* bcast */{ DSCRD, DSCRD, DSCRD, DSCRD, DSCRD },
/* bclient */{ DSCRD, DSCRD, DSCRD, DSCRD, PROC} /* bclient */{ DSCRD, DSCRD, DSCRD, DSCRD, PROC}
}; };
/* /*
* Miscellaneous macroni * Miscellaneous macroni
skipping to change at page 86, line 29 skipping to change at page 73, line 37
if (r->version > VERSION /* or format error */) if (r->version > VERSION /* or format error */)
return; /* format error */ return; /* format error */
/* /*
* Authentication is conditioned by two switches which can be * Authentication is conditioned by two switches which can be
* specified on a per-client basis. * specified on a per-client basis.
* *
* P_NOPEER do not mobilize an association unless * P_NOPEER do not mobilize an association unless
* authenticated * authenticated
* P_NOTRUST do not allow access unless authenticated * P_NOTRUST do not allow access unless authenticated
* (implies P_NOPEER)* * (implies P_NOPEER)
*
* There are four outcomes: * There are four outcomes:
* *
* A_NONE the packet has no MAC * A_NONE the packet has no MAC
* A_OK the packet has a MAC and authentication * A_OK the packet has a MAC and authentication
* succeeds * succeeds
* A_ERROR the packet has a MAC and authentication fails * A_ERROR the packet has a MAC and authentication fails
* A_CRYPTO crypto-NAK. the MAC has four octets only. * A_CRYPTO crypto-NAK. The MAC has four octets only.
* *
* Note: The AUTH(x, y) macro is used to filter outcomes. If x * Note: The AUTH(x, y) macro is used to filter outcomes. If x
* is zero, acceptable outcomes of y are NONE and OK. If x is * is zero, acceptable outcomes of y are NONE and OK. If x is
* one, the only acceptable outcome of y is OK. * one, the only acceptable outcome of y is OK.
*/ */
has_mac = /* length of MAC field */ 0; if (has_mac == 0) { has_mac = /* length of MAC field */ 0;
if (has_mac == 0) {
auth = A_NONE; /* not required */ auth = A_NONE; /* not required */
} else if (has_mac == 4) { } else if (has_mac == 4) {
auth == A_CRYPTO; /* crypto-NAK */ auth == A_CRYPTO; /* crypto-NAK */
} else { } else {
if (r->mac != md5(r->keyid)) if (r->mac != md5(r->keyid))
auth = A_ERROR; /* auth error */ auth = A_ERROR; /* auth error */
else else
auth = A_OK; /* auth OK */ auth = A_OK; /* auth OK */
} }
/* /*
* Find association and dispatch code. If there is no * Find association and dispatch code. If there is no
* association to match, the value of p->mode is assumed NULL. * association to match, the value of p->hmode is assumed NULL.
*/ */
p = find_assoc(r); p = find_assoc(r);
switch(table[p->mode][r->mode]) { switch(table[p->hmode][r->mode]) {
/* /*
* Client packet. Send server reply (no association). If * Client packet and no association. Send server reply without
* authentication fails, send a crypto-NAK packet. * saving state.
*/ */
case FXMIT: case FXMIT:
/*
* If unicast destination address, send server packet.
* If authentication fails, send a crypto-NAK packet.
/*
if (/* not multicast dstaddr */0) {
if (AUTH(p->flags & P_NOTRUST, auth)) if (AUTH(p->flags & P_NOTRUST, auth))
fast_xmit(r, M_SERV, auth); fast_xmit(r, M_SERV, auth);
else if (auth == A_ERROR) else if (auth == A_ERROR)
fast_xmit(r, M_SERV, A_CRYPTO); fast_xmit(r, M_SERV, A_CRYPTO);
return; /* M_SERV packet sent */ return; /* M_SERV packet sent */
}
/* /*
* New symmetric passive client (ephemeral association). It is * This must be manycast. Do not repspond if we are not
* mobilized in the same version as in the packet. If * synchronized or if our stratum is above the
* authentication fails, send a crypto-NAK packet. If restrict * manycaster.
* no-moblize, send a symmetric active packet instead. */
if (s.leap == NOSYNC || s.stratum > r->stratum)
return;
/*
* Respond only if authentication is ok. Note that the
* unicast addreess is used, not the multicast.
*/
if (AUTH(p->flags & P_NOTRUST, auth))
fast_xmit(r, M_SERV, auth);
return;
/*