draft-ietf-ntp-ntpv4-proto-13.txt   rfc5905.txt 
NTP WG J. Burbank Internet Engineering Task Force (IETF) D. Mills
Internet-Draft W. Kasch Request for Comments: 5905 U. Delaware
Obsoletes: RFC 4330, RFC 1305 JHU/APL Obsoletes: 1305, 4330 J. Martin, Ed.
(if approved) J. Martin, Ed. Category: Standards Track ISC
Intended status: Standards Track Daedelus ISSN: 2070-1721 J. Burbank
Expires: April 12, 2010 D. Mills W. Kasch
U. Delaware JHU/APL
October 9, 2009 June 2010
Network Time Protocol Version 4 Protocol And Algorithms Specification
draft-ietf-ntp-ntpv4-proto-13
Status of this Memo Network Time Protocol Version 4: Protocol and Algorithms Specification
This Internet-Draft is submitted to IETF in full conformance with the Abstract
provisions of BCP 78 and BCP 79. This document may contain material
from IETF Documents or IETF Contributions published or made publicly
available before November 10, 2008. The person(s) controlling the
copyright in some of this material may not have granted the IETF
Trust the right to allow modifications of such material outside the
IETF Standards Process. Without obtaining an adequate license from
the person(s) controlling the copyright in such materials, this
document may not be modified outside the IETF Standards Process, and
derivative works of it may not be created outside the IETF Standards
Process, except to format it for publication as an RFC or to
translate it into languages other than English.
Internet-Drafts are working documents of the Internet Engineering The Network Time Protocol (NTP) is widely used to synchronize
Task Force (IETF), its areas, and its working groups. Note that computer clocks in the Internet. This document describes NTP version
other groups may also distribute working documents as Internet- 4 (NTPv4), which is backwards compatible with NTP version 3 (NTPv3),
Drafts. described in RFC 1305, as well as previous versions of the protocol.
NTPv4 includes a modified protocol header to accommodate the Internet
Protocol version 6 address family. NTPv4 includes fundamental
improvements in the mitigation and discipline algorithms that 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.
Internet-Drafts are draft documents valid for a maximum of six months Status of This Memo
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at This is an Internet Standards Track document.
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at This document is a product of the Internet Engineering Task Force
http://www.ietf.org/shadow.html. (IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 5741.
This Internet-Draft will expire on April 12, 2010. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc5905.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents
publication of this document (http://trustee.ietf.org/license-info). (http://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
Abstract include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
The Network Time Protocol (NTP) is widely used to synchronize This document may contain material from IETF Documents or IETF
computer clocks in the Internet. This document describes NTP Version Contributions published or made publicly available before November
4 (NTPv4), which is backwards compatible with NTP Version 3 (NTPv3) 10, 2008. The person(s) controlling the copyright in some of this
described in RFC 1305, as well as previous versions of the protocol. material may not have granted the IETF Trust the right to allow
NTPv4 includes a modified protocol header to accommodate the Internet modifications of such material outside the IETF Standards Process.
Protocol Version 6 address family. NTPv4 includes fundamental Without obtaining an adequate license from the person(s) controlling
improvements in the mitigation and discipline algorithms which extend the copyright in such materials, this document may not be modified
the potential accuracy to the tens of microseconds with modern outside the IETF Standards Process, and derivative works of it may
workstations and fast LANs. It includes a dynamic server discovery not be created outside the IETF Standards Process, except to format
scheme, so that in many cases specific server configuration is not it for publication as an RFC or to translate it into languages other
required. It corrects certain errors in the NTPv3 design and than English.
implementation and includes an optional extension mechanism.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction ....................................................4
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 6 1.1. Requirements Notation ......................................5
2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 6 2. Modes of Operation ..............................................6
3. Protocol Modes . . . . . . . . . . . . . . . . . . . . . . . 7 3. Protocol Modes ..................................................6
3.1. Dynamic Server Discovery . . . . . . . . . . . . . . . . 8 3.1. Dynamic Server Discovery ...................................7
4. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 9 4. Definitions .....................................................8
5. Implementation Model . . . . . . . . . . . . . . . . . . . . 11 5. Implementation Model ...........................................10
6. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 13 6. Data Types .....................................................12
7. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 17 7. Data Structures ................................................16
7.1. Structure Conventions . . . . . . . . . . . . . . . . . . 17 7.1. Structure Conventions .....................................16
7.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 17 7.2. Global Parameters .........................................16
7.3. Packet Header Variables . . . . . . . . . . . . . . . . . 18 7.3. Packet Header Variables ...................................17
7.4. The Kiss-o'-Death Packet . . . . . . . . . . . . . . . . 25 7.4. The Kiss-o'-Death Packet ..................................24
7.5. NTP Extension Field Format . . . . . . . . . . . . . . . 26 7.5. NTP Extension Field Format ................................25
8. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 27 8. On-Wire Protocol ...............................................26
9. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 31 9. Peer Process ...................................................30
9.1. Peer Process Variables . . . . . . . . . . . . . . . . . 32 9.1. Peer Process Variables ....................................31
9.2. Peer Process Operations . . . . . . . . . . . . . . . . . 34 9.2. Peer Process Operations ...................................33
10. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . 38 10. Clock Filter Algorithm ........................................37
11. System Process . . . . . . . . . . . . . . . . . . . . . . . 40 11. System Process ................................................39
11.1. System Process Variables . . . . . . . . . . . . . . . . 41 11.1. System Process Variables .................................40
11.2. System Process Operations . . . . . . . . . . . . . . . . 42 11.2. System Process Operations ................................41
11.2.1. Selection Algorithm . . . . . . . . . . . . . . . . 44 11.2.1. Selection Algorithm ...............................43
11.2.2. Cluster Algorithm . . . . . . . . . . . . . . . . . 45 11.2.2. Cluster Algorithm .................................44
11.2.3. Combine Algorithm . . . . . . . . . . . . . . . . . 46 11.2.3. Combine Algorithm .................................45
11.3. Clock Discipline Algorithm . . . . . . . . . . . . . . . 48 11.3. Clock Discipline Algorithm ...............................47
12. Clock Adjust Process . . . . . . . . . . . . . . . . . . . . 52 12. Clock-Adjust Process ..........................................51
13. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 52 13. Poll Process ..................................................51
13.1. Poll Process Variables . . . . . . . . . . . . . . . . . 52 13.1. Poll Process Variables ...................................51
13.2. Poll Process Operations . . . . . . . . . . . . . . . . . 53 13.2. Poll Process Operations ..................................52
14. Simple Network Time Protocol (SNTP) . . . . . . . . . . . . . 55 14. Simple Network Time Protocol (SNTP) ...........................54
15. Security Considerations . . . . . . . . . . . . . . . . . . . 56 15. Security Considerations .......................................55
16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 59 16. IANA Considerations ...........................................58
17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 60 17. Acknowledgements ..............................................59
18. References . . . . . . . . . . . . . . . . . . . . . . . . . 60 18. References ....................................................59
18.1. Normative References . . . . . . . . . . . . . . . . . . 60 18.1. Normative References .....................................59
18.2. Informative References . . . . . . . . . . . . . . . . . 60 18.2. Informative References ...................................59
Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 61 Appendix A. Code Skeleton .......................................61
A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 62 A.1. Global Definitions .......................................61
A.1.1. Definitions, Constants, Parameters . . . . . . . . . 62 A.1.1. Definitions, Constants, Parameters .....................61
A.1.2. Packet Data Structures . . . . . . . . . . . . . . . 65 A.1.2. Packet Data Structures .................................65
A.1.3. Association Data Structures . . . . . . . . . . . . 66 A.1.3. Association Data Structures ............................66
A.1.4. System Data Structures . . . . . . . . . . . . . . . 69 A.1.4. System Data Structures .................................68
A.1.5. Local Clock Data Structures . . . . . . . . . . . . 70 A.1.5. Local Clock Data Structures ............................69
A.1.6. Function Prototypes . . . . . . . . . . . . . . . . 70 A.1.6. Function Prototypes ....................................69
A.2. Main Program and Utility Routines . . . . . . . . . . . . 71 A.2. Main Program and Utility Routines ..........................70
A.3. Kernel Input/Output Interface . . . . . . . . . . . . . . 74 A.3. Kernel Input/Output Interface ..............................73
A.4. Kernel System Clock Interface . . . . . . . . . . . . . . 74 A.4. Kernel System Clock Interface ..............................74
A.5. Peer Process . . . . . . . . . . . . . . . . . . . . . . 76 A.5. Peer Process ...............................................76
A.5.1. receive() . . . . . . . . . . . . . . . . . . . . . 77 A.5.1. receive() ..............................................77
A.5.2. clock_filter() . . . . . . . . . . . . . . . . . . . 84 A.5.2. clock_filter() .........................................85
A.5.3. fast_xmit() . . . . . . . . . . . . . . . . . . . . 88 A.5.3. fast_xmit() ............................................88
A.5.4. access() . . . . . . . . . . . . . . . . . . . . . . 89 A.5.4. access() ...............................................89
A.5.5. System Process . . . . . . . . . . . . . . . . . . . 89 A.5.5. System Process .........................................90
A.5.6. Clock Adjust Process . . . . . . . . . . . . . . . . 104 A.5.6. Clock Adjust Process ..................................103
A.5.7. Poll Process . . . . . . . . . . . . . . . . . . . . 105 A.5.7. Poll Process ..........................................104
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 112
1. Introduction 1. Introduction
This document defines the Network Time Protocol Version 4 (NTPv4), This document defines the Network Time Protocol version 4 (NTPv4),
which is widely used to synchronize system clocks among a set of which is widely used to synchronize system clocks among a set of
distributed time servers and clients. It describes 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. NTPv4 introduces new functionality to NTPv3, as algorithms. NTPv4 introduces new functionality to NTPv3, as
described in [RFC1305], and functionality expanded from SNTPv4 as described in [RFC1305], and functionality expanded from Simple NTP
described in [RFC4330] (SNTPv4 is a subset of NTPv4). This document version 4 (SNTPv4) as described in [RFC4330] (SNTPv4 is a subset of
obsoletes [RFC1305], and [RFC4330]. While certain minor changes have NTPv4). This document obsoletes [RFC1305] and [RFC4330]. While
been made in some protocol header fields, these do not affect the certain minor changes have been made in some protocol header fields,
interoperability between NTPv4 and previous versions of NTP and SNTP. these do not affect the interoperability between NTPv4 and previous
versions of NTP and SNTP.
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. Precisely tuned both private networks and the public Internet. Precisely tuned
algorithms mitigate errors that may result from network disruptions, algorithms mitigate errors that may result from network disruptions,
server failures and possible hostile actions. Servers and clients server failures, and possible hostile actions. Servers and clients
are configured such that values flow towards clients from the primary are configured such that values flow towards clients from the primary
servers at the root via branching secondary servers. servers at the root via branching secondary servers.
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
the floating double data type throughout the implementation. As a the floating double data type throughout the implementation. As a
result, the time resolution is better than one nanosecond and result, the time resolution is better than one nanosecond, and
frequency resolution is less than one nanosecond per second. frequency resolution is less than one nanosecond per second.
Additional improvements include a new clock discipline algorithm Additional improvements include a new clock discipline algorithm that
which is more responsive to system clock hardware frequency is more responsive to system clock hardware frequency fluctuations.
fluctuations. Typical primary servers using modern machines are Typical primary servers using modern machines are precise within a
precise within a few tens of microseconds. Typical secondary servers few tens of microseconds. Typical secondary servers and clients on
and clients on fast LANs are within a few hundred microseconds with fast LANs are within a few hundred microseconds with poll intervals
poll intervals up to 1024 seconds, which was the maximum with NTPv3. up to 1024 seconds, which was the maximum with NTPv3. With NTPv4,
With NTPv4, servers and clients are precise within a few tens of servers and clients are precise within a few tens of milliseconds
milliseconds with poll intervals up to 36 hours. with poll intervals up to 36 hours.
The main body of this document describes the core protocol and data The main body of this document describes the core protocol and data
structures necessary to interoperate between conforming structures necessary to interoperate between conforming
implementations. Appendix A contains a full featured example in the implementations. Appendix A contains a full-featured example in the
form of a skeleton program, including data structures and code form of a skeleton program, including data structures and code
segments for the core algorithms as well as the mitigation algorithms segments for the core algorithms as well as the mitigation algorithms
used to enhance reliability and accuracy. While the skeleton program used to enhance reliability and accuracy. While the skeleton program
and other descriptions in this document apply to a particular and other descriptions in this document apply to a particular
implementation, they are not intended as the only way the required implementation, they are not intended as the only way the required
functions can be implemented. While the NTPv3 symmetric key functions can be implemented. The contents of Appendix A are non-
authentication scheme described in this document has been carried normative examples designed to illustrate the protocol's operation
over from NTPv3, the Autokey public key authentication scheme new to and are not a requirement for a conforming implementation. While the
NTPv4 is described in [I-D.ietf-ntp-autokey]. NTPv3 symmetric key authentication scheme described in this document
has been carried over from NTPv3, the Autokey public key
authentication scheme new to NTPv4 is described in [RFC5906].
The NTP protocol includes modes of operation described in Section 2 The NTP protocol includes modes of operation described in Section 2
using data types described in Section 6 and data structures described using data types described in Section 6 and data structures described
in Section 7. The implementation model described in Section 5 is in Section 7. The implementation model described in Section 5 is
based on a threaded, multi-process architecture, although other based on a threaded, multi-process architecture, although other
architectures could be used as well. The on-wire protocol described architectures could be used as well. The on-wire protocol described
in Section 8 is based on a returnable-time design which depends only in Section 8 is based on a returnable-time design that depends only
on measured clock offsets, but does not require reliable message on measured clock offsets, but does not require reliable message
delivery. Reliable message delivery such as TCP[RFC0793] can delivery. Reliable message delivery such as TCP [RFC0793] can
actually make the delivered NTP packet less reliable since retries actually make the delivered NTP packet less reliable since retries
would increase the delay value and other errors. The synchronization would increase the delay value and other errors. The synchronization
subnet is a self-organizing, hierarchical, master-slave network with subnet is a self-organizing, hierarchical, master-slave network with
synchronization paths determined by a shortest-path spanning tree and synchronization paths determined by a shortest-path spanning tree and
defined metric. While multiple masters (primary servers) may exist, defined metric. While multiple masters (primary servers) may exist,
there is no requirement for an election protocol. there is no requirement for an election protocol.
This document includes material from [ref9], which contains flow This document includes material from [ref9], which contains flow
charts and equations unsuited for RFC format. There is much charts and equations unsuited for RFC format. There is much
additional information in [ref7], including an extensive technical additional information in [ref7], including an extensive technical
analysis and performance assessment of the protocol and algorithms in analysis and performance assessment of the protocol and algorithms in
this document. The reference implementation is available at this document. The reference implementation is available at
www.ntp.org. www.ntp.org.
The remainder of this document contains numerous variables and The remainder of this document contains numerous variables and
mathematical expressions. Some variables take the form of Greek mathematical expressions. Some variables take the form of Greek
characters, which are spelled out by their full case-sensitive name. characters, which are spelled out by their full case-sensitive name.
For example DELTA refers to the uppercase Greek character, while For example, DELTA refers to the uppercase Greek character, while
delta refers to the lowercase character. Furthermore, subscripts are delta refers to the lowercase character. Furthermore, subscripts are
denoted with '_', for example theta_i refers to the lowercase Greek denoted with '_'; for example, theta_i refers to the lowercase Greek
character theta with subscript i, or phonetically theta sub i. In character theta with subscript i, or phonetically theta sub i. In
this document all time values are in seconds (s), and all frequencies this document, all time values are in seconds (s), and all
will be specified as fractional frequency offsets (FFO) (pure frequencies will be specified as fractional frequency offsets (FFOs)
number). It is often convenient to express these FFOs in parts per (pure number). It is often convenient to express these FFOs in parts
million (ppm). per million (ppm).
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 [RFC2119]. document are to be interpreted as described in [RFC2119].
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 to a reference clock or client. A primary server is synchronized to a reference clock
directly traceable to UTC (eg, GPS, Galileo, etc). A client directly traceable to UTC (e.g., GPS, Galileo, etc.). A client
synchronizes to one or more upstream servers, but does not provide synchronizes 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 who are fully NTPv4 compliant MUST implement All servers and clients who are fully NTPv4-compliant 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 SHOULD to maintain stability in large NTP subnets, secondary servers SHOULD
be fully NTPv4 compliant. Alternative algorithms MAY be used, but be fully NTPv4-compliant. Alternative algorithms MAY be used, but
their output MUST be identical to the algorithms described in this their output MUST be identical to the algorithms described in this
specification. specification.
3. Protocol Modes 3. Protocol Modes
There are three NTP protocol variants, symmetric, client/server and There are three NTP protocol variants: symmetric, client/server, and
broadcast. Each is associated with an association mode (a broadcast. Each is associated with an association mode (a
description of the relationship between two NTP speakers) as shown in description of the relationship between two NTP speakers) as shown in
Figure 1. In addition, persistent associations are mobilized upon Figure 1. In addition, persistent associations are mobilized upon
startup and are never demobilized. Ephemeral associations are startup and are never demobilized. Ephemeral associations are
mobilized upon the arrival of a packet and are demobilized upon error mobilized upon the arrival of a packet and are demobilized upon error
or timeout. or timeout.
+-------------------+--------------+-------------+ +-------------------+-------------------+------------------+
| Association Mode | Assoc. Mode | Packet Mode | | Association Mode | Assoc. Mode Value | Packet Mode Value|
+-------------------+--------------+-------------+ +-------------------+-------------------+------------------+
| 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 |
+-------------------+--------------+-------------+ +-------------------+-------------------+------------------+
Figure 1: Association and Packet Modes Figure 1: Association and Packet Modes
In the client/server variant a persistent client sends packet mode 4 In the client/server variant, a persistent client sends packet mode 4
packets to a server, which returns packet mode 3 packets. Servers packets to a server, which returns packet mode 3 packets. Servers
provide synchronization to one or more clients, but do not accept provide synchronization to one or more clients, but do not accept
synchronization from them. A server can also be a reference clock synchronization from them. A server can also be a reference clock
driver which obtains time directly from a standard source such as a driver that obtains time directly from a standard source such as a
GPS receiver or telephone modem service. In this variant, clients GPS receiver or telephone modem service. In this variant, clients
pull synchronization from servers. 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
persistent symmetric active association sends symmetric active (mode persistent symmetric active association sends symmetric active (mode
1) packets to a symmetric active peer association. Alternatively, an 1) packets to a symmetric active peer association. Alternatively, an
ephemeral symmetric passive association can be mobilized upon arrival ephemeral symmetric passive association can be mobilized upon the
of a symmetric active packet with no matching association. That arrival of a symmetric active packet with no matching association.
association sends symmetric passive (mode 2) packets and persists That association sends symmetric passive (mode 2) packets and
until error or timeout. Peers both push and pull synchronization to persists until error or timeout. Peers both push and pull
and from each other. For the purposes of this document, a peer synchronization to and from each other. For the purposes of this
operates like a client, so references to client imply peer as well. document, a peer operates like a client, so references to client
imply peer as well.
In the broadcast variant a persistent broadcast server association In the broadcast variant, a persistent broadcast server association
sends periodic broadcast server (mode 5) packets which can be sends periodic broadcast server (mode 5) packets that can be received
received by multiple clients. Upon reception of a broadcast server by multiple clients. Upon reception of a broadcast server packet
packet without a matching association, an ephemeral broadcast client without a matching association, an ephemeral broadcast client (mode
(mode 6) association is mobilized and persists until error or 6) association is mobilized and persists until error or timeout. It
timeout. It is useful to provide an initial volley where the client is useful to provide an initial volley where the client operating in
operating in client mode exchanges several packets with the server, client mode exchanges several packets with the server, so as to
so as to calibrate the propagation delay and to run the Autokey calibrate the propagation delay and to run the Autokey security
security protocol, after which the client reverts to broadcast client protocol, after which the client reverts to broadcast client mode. A
mode. A broadcast server pushes synchronization to clients and other broadcast server pushes synchronization to clients and other servers.
servers.
Following loosely the conventions established by the telephone Loosely following the conventions established by the telephone
industry, the level of each server in the hierarchy is defined by a industry, the level of each server in the hierarchy is defined by a
stratum number. Primary servers are assigned stratum one; secondary stratum number. Primary servers are assigned stratum one; secondary
servers at each lower level are assigned stratum numbers one greater servers at each lower level are assigned stratum numbers one greater
than the preceding level. As the stratum number increases, its than the preceding level. As the stratum number increases, its
accuracy degrades depending on the particular network path and system accuracy degrades depending on the particular network path and system
clock stability. Mean errors, measured by synchronization distances, clock stability. Mean errors, measured by synchronization distances,
increase approximately in proportion to stratum numbers and measured increase approximately in proportion to stratum numbers and measured
roundtrip delay. round-trip delay.
As a standard practice, timing network topology should be organized As a standard practice, timing network topology should be organized
to avoid timing loops and minimize the synchronization distance. In to avoid timing loops and minimize the synchronization distance. In
NTP the subnet topology is determined using a variant of the Bellman- NTP, the subnet topology is determined using a variant of the
Ford distributed routing algorithm, which computes the shortest-path Bellman-Ford distributed routing algorithm, which computes the
spanning tree rooted on the primary servers. As a result of this shortest-path spanning tree rooted on the primary servers. As a
design, the algorithm automatically reorganizes the subnet, so as to result of this design, the algorithm automatically reorganizes the
produce the most accurate and reliable time, even when there are subnet, so as to produce the most accurate and reliable time, even
failures in the timing network. when there are failures in the timing network.
3.1. Dynamic Server Discovery 3.1. Dynamic Server Discovery
There are two special associations, manycast client and manycast There are two special associations, manycast client and manycast
server, which provide a dynamic server discovery function. There are server, which provide a dynamic server discovery function. There are
two types of manycast client associations, persistent and ephemeral. two types of manycast client associations: persistent and ephemeral.
The persistent manycast client sends client (mode 3) packets to a The persistent manycast client sends client (mode 3) packets to a
designated IPv4 or IPv6 broadcast or multicast group address. designated IPv4 or IPv6 broadcast or multicast group address.
Designated manycast servers within range of the time-to-live (TTL) Designated manycast servers within range of the time-to-live (TTL)
field in the packet header listen for packets with that address. If field in the packet header listen for packets with that address. If
a server is suitable for synchronization, it returns an ordinary a server is suitable for synchronization, it returns an ordinary
server (mode 4) packet using the client's unicast address. Upon server (mode 4) packet using the client's unicast address. Upon
receiving this packet, the client mobilizes an ephemeral client (mode receiving this packet, the client mobilizes an ephemeral client (mode
3) association. The ephemeral client association persists until 3) association. The ephemeral client association persists until
error or timeout. error or timeout.
skipping to change at page 9, line 23 skipping to change at page 8, line 28
mobilized, the client stops transmission for a time-out period to mobilized, the client stops transmission for a time-out period to
clear all associations, and then repeats the search cycle. If a clear all associations, and then repeats the search cycle. If a
minimum number of associations has been mobilized, then the client minimum number of associations has been mobilized, then the client
starts transmitting one packet per time-out period to maintain the starts transmitting one packet per time-out period to maintain the
associations. Field constraints limit the minimum value to 1 and the associations. Field constraints limit the minimum value to 1 and the
maximum to 255. These limits may be tuned for individual application maximum to 255. These limits may be tuned for individual application
needs. needs.
The ephemeral associations compete among themselves. As new The ephemeral associations compete among themselves. As new
ephemeral associations are mobilized, the client runs the mitigation ephemeral associations are mobilized, the client runs the mitigation
algorithms described in Section 10 and Section 11.2 for the best algorithms described in Sections 10 and 11.2 for the best candidates
candidates out of the population, the remaining ephemeral out of the population, the remaining ephemeral associations are timed
associations are timed out and demobilized. In this way the out and demobilized. In this way, the population includes only the
population includes only the best candidates that have most recently best candidates that have most recently responded with an NTP packet
responded with an NTP packet to discipline the system clock. to discipline the system clock.
4. Definitions 4. Definitions
A number of technical terms are defined in this section. A timescale A number of technical terms are defined in this section. A timescale
is a frame of reference where time is expressed as the value of a is a frame of reference where time is expressed as the value of a
monotonically increasing binary counter with an indefinite number of monotonically increasing binary counter with an indefinite number of
bits. It counts in seconds and fractions of a second, when a decimal bits. It counts in seconds and fractions of a second, when a decimal
point is employed. The Coordinated Universal Time (UTC) timescale is point is employed. The Coordinated Universal Time (UTC) timescale is
defined by ITU-R TF.460[ITU-R_TF.460]. Under the auspices of the defined by ITU-R TF.460 [ITU-R_TF.460]. Under the auspices of the
Metre Convention of 1865, in 1975 the CGPM[CGPM] strongly endorsed Metre Convention of 1865, in 1975 the CGPM [CGPM] strongly endorsed
the use of UTC as the basis for civil time. the use of UTC as the basis for civil time.
The Coordinated Universal Time (UTC) timescale represents mean solar The Coordinated Universal Time (UTC) timescale represents mean solar
time as disseminated by national standards laboratories. The system time as disseminated by national standards laboratories. The system
time is represented by the system clock maintained by the hardware time is represented by the system clock maintained by the hardware
and operating system. The goal of the NTP algorithms is to minimize and operating system. The goal of the NTP algorithms is to minimize
both the time difference and frequency difference between UTC and the both the time difference and frequency difference between UTC and the
system clock. When these differences have been reduced below nominal system clock. When these differences have been reduced below nominal
tolerances, 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 the event takes place. The date of an event is the UTC time at which the event takes place.
Dates are ephemeral values designated with upper case T. Running time Dates are ephemeral values designated with uppercase T. Running time
is another timescale that is coincident to the synchronization is another timescale that is coincident to the synchronization
function of the NTP program. function of the NTP program.
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 aging rate (first derivative of R(t) with respect to offset, and D(t) the aging rate (first derivative of R(t) with
t). Then, if T(t_0) is the UTC time offset determined at t = t_0, respect to t). Then, if T(t_0) is the UTC time offset determined at
the UTC time offset at time t is t = t_0, the UTC time offset at time t is
T(t) = T(t_0) + R(t_0)(t-t_0) + 1/2 * D(t_0)(t-t_0)^2 + e, T(t) = 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 10^(-6) seconds/second. is equal to 10^(-6) s/s.
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 that are updated each time a client makes a
measurement with a server. The offset (theta) represents the measurement with a server. The offset (theta) represents the
maximum-likelihood time offset of the server clock relative to the maximum-likelihood time offset of the server clock relative to the
system clock. The delay (delta) represents the round trip delay system clock. The delay (delta) represents the round-trip delay
between the client and server. The dispersion (epsilon) represents between the client and server. The dispersion (epsilon) represents
the maximum error inherent in the measurement. It increases at a the maximum error inherent in the measurement. It increases at a
rate equal to the maximum disciplined system clock frequency rate equal to the maximum disciplined system clock frequency
tolerance (PHI), typically 15 PPM. The jitter (psi) is defined as tolerance (PHI), typically 15 ppm. The jitter (psi) is defined as
the root-mean-square (RMS) average of the most recent offset the root-mean-square (RMS) average of the most recent offset
differences, represents the nominal error in estimating the offset. differences, and it represents the nominal error in estimating the
offset.
While the theta, delta, epsilon, and psi statistics represent While the theta, delta, epsilon, and psi statistics represent
measurements of the system clock relative to each server clock measurements of the system clock relative to 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 (THETA) represents the calibrate the system clock. The system offset (THETA) represents the
maximum-likelihood offset estimate for the server population. The maximum-likelihood offset estimate for the server population. The
system jitter (PSI) represents the nominal error in estimating the system jitter (PSI) represents the nominal error in estimating the
system offset. The delta and epsilon statistics are accumulated at system offset. The delta and epsilon statistics are accumulated at
each stratum level from the reference clock to produce the root delay each stratum level from the reference clock to produce the root delay
(DELTA) and root dispersion (EPSILON) statistics. The (DELTA) and root dispersion (EPSILON) statistics. The
synchronization distance (LAMBDA) equal to EPSILON + DELTA / 2 synchronization distance (LAMBDA) equal to EPSILON + DELTA / 2
represents the maximum error due all causes. The detailed represents the maximum error due to all causes. The detailed
formulations of these statistics are given in Section 11.2. They are formulations of these statistics are given in Section 11.2. They are
available to the dependent applications in order to assess the available to the dependent applications in order to assess the
performance of the synchronization function. performance of the synchronization function.
5. Implementation Model 5. Implementation Model
Figure 2 shows the architecture of a typical, multi-threaded Figure 2 shows the architecture of a typical, multi-threaded
implementation. It includes two processes dedicated to each server, implementation. It includes two processes dedicated to each server,
a peer process to receive messages from the server or reference clock a peer process to receive messages from the server or reference
and a poll process to transmit messages to the server or reference clock, and a poll process to transmit messages to the server or
clock. reference clock.
..................................................................... .....................................................................
. Remote . Peer/Poll . System . Clock . . Remote . Peer/Poll . System . Clock .
. Servers . Processes . Process .Discipline. . Servers . Processes . Process .Discipline.
. . . . Process . . . . . Process .
.+--------+. +-----------+. +------------+ . . .+--------+. +-----------+. +------------+ . .
.| |->| |. | | . . .| |->| |. | | . .
.|Server 1| |Peer/Poll 1|->| | . . .|Server 1| |Peer/Poll 1|->| | . .
.| |<-| |. | | . . .| |<-| |. | | . .
.+--------+. +-----------+. | | . . .+--------+. +-----------+. | | . .
skipping to change at page 12, line 8 skipping to change at page 11, line 14
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 in Section 9. A client sends packets to various other data described in Section 9. A client sends packets to
one or more servers and then processes returned packets when they are one or more servers and then processes returned packets when they are
received. The server interchanges source and destination addresses received. The server interchanges source and destination addresses
and ports, overwrites certain fields in the packet and returns it and ports, overwrites certain fields in the packet and returns it
immediately (in the client/server mode) or at some time later (in the immediately (in the client/server mode) or at some time later (in the
symmetric modes). As each NTP message is received, the offset theta symmetric modes). As each NTP message is received, the offset theta
between the peer clock and the system clock is computed along with between the peer clock and the system clock is computed along with
the associated statistics delta, epsilon and psi. the associated statistics delta, epsilon, and psi.
The system process includes the selection, cluster and combine The system process includes the selection, cluster, and combine
algorithms that mitigate among the various servers and reference algorithms that 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
fault detection principles to discard the presumably incorrect fault detection principles to discard the presumably incorrect
candidates called "falsetickers" from the incident population, candidates called "falsetickers" from the incident population,
leaving only good candidates called "truechimers". A truechimer is a leaving only good candidates called "truechimers". A truechimer is a
clock that maintains timekeeping accuracy to a previously published clock that maintains timekeeping accuracy to a previously published
and trusted standard, while a falseticker is a clock that shows and trusted standard, while a falseticker is a clock that shows
misleading or inconsistent time. The cluster algorithm uses misleading or inconsistent time. The cluster algorithm uses
statistical principles to find the most accurate set of truechimers. statistical principles to find the most accurate set of truechimers.
The combine algorithm computes the final clock offset by The combine algorithm computes the final clock offset by
statistically averaging the surviving truechimers. statistically averaging the surviving truechimers.
The clock discipline process is a system process that controls the The clock discipline process is a system process that controls the
time and frequency of the system clock, here represented as a time and frequency of the system clock, here represented as a
variable frequency oscillator (VFO). Timestamps struck from the VFO variable frequency oscillator (VFO). Timestamps struck from the VFO
close the feedback loop which maintains the system clock time. close the feedback loop that maintains the system clock time.
Associated with the clock discipline process is the clock adjust Associated with the clock discipline process is the clock-adjust
process, which runs once each second to inject a computed time offset process, which runs once each second to inject a computed time offset
and maintain constant frequency. The RMS average of past time offset and maintain constant frequency. The RMS average of past time offset
differences represents the nominal error or system clock jitter. The differences represents the nominal error or system clock jitter. The
RMS average of past frequency offset differences represents the RMS average of past frequency offset differences represents the
oscillator frequency stability or frequency wander. These terms are oscillator frequency stability or frequency wander. These terms are
given precise interpretation in Section 11.3. given precise interpretation in Section 11.3.
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 seconds, as determined by the poll exponent tau. In NTPv4, tau
ranges from 4 (16 s) through 17 (36 h). The value of tau is ranges from 4 (16 s) to 17 (36 h). The value of tau is determined by
determined by the clock discipline algorithm to match the loop time the clock discipline algorithm to match the loop-time constant T_c =
constant T_c = 2^tau. In client/server mode the server responds 2^tau. In client/server mode, the server responds immediately;
immediately; however, in symmetric modes each of two peers manages however, in symmetric modes, each of two peers manages tau as a
tau as a function of current system offset and system jitter, so may function of current system offset and system jitter, so they may not
not agree with the same value. It is important that the dynamic agree with the same value. It is important that the dynamic behavior
behavior of the clock discipline algorithm be carefully controlled in of the clock discipline algorithm be carefully controlled in order to
order to maintain stability in the NTP subnet at large. This maintain stability in the NTP subnet at large. This requires that
requires that the peers agree on a common tau equal to the minimum the peers agree on a common tau equal to the minimum poll exponent of
poll exponent of both peers. The NTP protocol includes provisions to both peers. The NTP protocol includes provisions to properly
properly negotiate this value. negotiate this value.
The implementation model includes some means to set and adjust the The implementation model includes some means to set and adjust the
system clock. The operating system is assumed to provide two system clock. The operating system is assumed to provide two
functions, one to set the time directly, for example the Unix functions: one to set the time directly, for example, the Unix
settimeofday() function, and another to adjust the time in small settimeofday() function, and another to adjust the time in small
increments advancing or retarding the time by a designated amount, increments advancing or retarding the time by a designated amount,
for example the Unix adjtime() function. In this and following for example, the Unix adjtime() function. In this and following
references, parentheses following a name indicate reference to a references, parentheses following a name indicate reference to a
function rather than a simple variable. In the intended design the function rather than a simple variable. In the intended design the
clock discipline process uses the adjtime() function if the clock discipline process uses the adjtime() function if the
adjustment is less than a designated threshold, and the adjustment is less than a designated threshold, and the
settimeofday() function if above the threshold. The manner in which settimeofday() function if above the threshold. The manner in which
this is done and the value of the threshold as described in this is done and the value of the threshold as described in
Section 10. Section 10.
6. 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 [RFC0791]) bits numbered in big-endian (as described in Appendix A of [RFC0791])
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 3.
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 Number field formats, the seconds field is divided into a 32-bit Era Number field
and a 32-bit Era Offset field. Eras cannot be produced by NTP and a 32-bit Era Offset field. Eras cannot be produced by NTP
directly, nor is there need to do so. When necessary, they can be directly, nor is there need to do so. When necessary, they can be
derived from external means, such as the filesystem or dedicated derived from external means, such as the filesystem or dedicated
hardware. hardware.
skipping to change at page 14, line 47 skipping to change at page 13, line 47
Figure 3: NTP Time Formats Figure 3: 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 and timestamp formats the prime epoch, or base date of In the date and timestamp formats, the prime epoch, or base date of
era 0, is 0 h 1 January 1900 UTC, when all bits are zero. It should era 0, is 0 h 1 January 1900 UTC, when all bits are zero. It should
be noted that strictly speaking, UTC did not exist prior to 1 January be noted that strictly speaking, UTC did not exist prior to 1 January
1972, but it is convenient to assume it has existed for all eternity, 1972, but it is convenient to assume it has existed for all eternity,
even if all knowledge of historic leap seconds has been lost. Dates even if all knowledge of historic leap seconds has been lost. Dates
are relative to the prime epoch; values greater than zero represent are relative to the prime epoch; values greater than zero represent
times after that date; values less than zero represent times before times after that date; values less than zero represent times before
it. Note that the Era Offset field of the date format and the it. Note that the Era Offset field of the date format and the
Seconds field of the timestamp format have the same interpretation. 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. Figure 4 shows a number of historic NTP dates unsynchronized time. Figure 4 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.
+-------------+------------+-----+---------------+------------------+ +-------------+------------+-----+---------------+------------------+
| Date | MJD | NTP | NTP Timestamp | Epoch | | Date | MJD | NTP | NTP Timestamp | Epoch |
| | | Era | Era Offset | | | | | 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 |
skipping to change at page 15, line 43 skipping to change at page 14, line 43
| 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 |
+-------------+------------+-----+---------------+------------------+ +-------------+------------+-----+---------------+------------------+
Figure 4: Interesting Historic NTP Dates Figure 4: 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 as 2^(-p), in seconds. In order to
bias and help make timestamps unpredictable to an intruder, the non- minimize bias and help make timestamps unpredictable to an intruder,
significant bits should be set to an unbiased random bit string. The the non-significant bits should be set to an unbiased random bit
clock precision is defined as the running time to read the system string. The clock precision is defined as the running time to read
clock, in seconds. Note that the precision defined in this way can the system clock, in seconds. Note that the precision defined in
be larger or smaller than the resolution. The term rho, representing this way can be larger or smaller than the resolution. The term rho,
the precision used in the protocol, is the larger of the two. representing the precision used in the protocol, is the larger of the
two.
The only arithmetic operation permitted on dates and timestamps is The only arithmetic operation permitted on dates and timestamps is
twos-complement subtraction, yielding a 127-bit or 63-bit signed twos-complement subtraction, yielding a 127-bit or 63-bit signed
result. It is critical that the first-order differences between two result. It is critical that the first-order differences between two
dates preserve the full 128-bit precision and the first-order dates preserve the full 128-bit precision and the first-order
differences between two timestamps preserve the full 64-bit differences between two timestamps preserve the full 64-bit
precision. However, the differences are ordinarily small compared to precision. However, the differences are ordinarily small compared to
the seconds span, so they can be converted to floating double format the seconds span, so they can be converted to floating double format
for further 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 It is important to note that twos-complement arithmetic does not
distinguish between signed and unsigned values (although comparisons distinguish between signed and unsigned values (although comparisons
can take sign into account); only the conditional branch instructions can take sign into account); only the conditional branch instructions
do. Thus, although the distinction is made between signed dates and do. Thus, although the distinction is made between signed dates and
unsigned timestamps, they are processed the same way. A perceived unsigned timestamps, they are processed the same way. A perceived
hazard with 64-bit timestamp calculations spanning an era, such as hazard with 64-bit timestamp calculations spanning an era, such as is
possible in 2036, might result in over-run. In point of fact, if the possible in 2036, might result in over-run. In point of fact, if the
client is set within 68 years of the server before the protocol is client is set within 68 years of the server before the protocol is
started, correct values are obtained even if the client and server started, correct values are obtained even if the client and server
are in adjacent eras. 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. These are in 8-bit precision, time constant, and poll interval. These are in 8-bit
signed integer format in log2 (log base 2) seconds. The only signed integer format in log2 (log base 2) seconds. The only
arithmetic operations permitted on them are increment and decrement. arithmetic 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 variables by name means the exponentiated reference to one of these variables by name means the exponentiated
value, e.g., the poll interval is 1024 s, while reference by name and value, e.g., the poll interval is 1024 s, while reference by name and
exponent means the actual value, e.g., the poll exponent is 10. exponent means the actual value, e.g., the poll 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. To determine the integer era and the system time be determined. To determine the integer era and
timestamp given s, 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 determine s given which works for positive and negative dates. To determine s given
the era and timestamp, the era and timestamp,
s = era * 2^(32) + timestamp. s = era * 2^(32) + timestamp.
Converting between NTP and system time can be a little messy, and Converting between NTP and system time can be a little messy, and is
beyond the scope of this document. Note that the number of days in beyond the scope of this document. Note that the number of days in
era 0 is one more than the number of days in most other eras and this era 0 is one more than the number of days in most other eras, and
won't happen again until the year 2400 in era 3. this won't happen 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.
7. Data Structures 7. Data Structures
The NTP protocol state machines are defined in the following The NTP state machines are defined in the following sections. State
sections. State variables are separated into classes according to variables are separated into classes according to their function in
their function in packet headers, peer and poll processes, the system packet headers, peer and poll processes, the system process, and the
process and the clock discipline process. Packet variables represent clock discipline process. Packet variables represent the NTP header
the NTP header values in transmitted and received packets. Peer and values in transmitted and received packets. Peer and poll variables
poll variables represent the contents of the association for each represent the contents of the association for each server separately.
server separately. System variables represent the state of the System variables represent the state of the server as seen by its
server as seen by its dependent clients. Clock discipline variables dependent clients. Clock discipline variables represent the internal
represent the internal workings of the clock discipline algorithm. workings of the clock discipline algorithm. An example is described
An example is described in Appendix A. in Appendix A.
7.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
Figure 5 is adopted. A receive packet variable v is a member of the Figure 5 is adopted. A receive packet variable v is a member of the
packet structure r with fully qualified name r.v. In a similar 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,
is a system variable and c.v is a clock discipline variable. There s.v is a system variable, and c.v is a clock discipline variable.
is a set of peer variables for each association; there is only one There is a set of peer variables for each association; there is only
set of system and clock variables. one set of system and clock variables.
+------+---------------------------------+ +------+---------------------------------+
| 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 |
+------+---------------------------------+ +------+---------------------------------+
Figure 5: Prefix Conventions Figure 5: Prefix Conventions
7.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
defined in this document, including those shown with values in are defined in this document, including those shown with values in
Figure 6. Figure 6.
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
| Name | Value | Description | | Name | Value | Description |
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
| PORT | 123 | NTP port number | | PORT | 123 | NTP port number |
| VERSION | 4 | NTP version number | | VERSION | 4 | NTP version number |
| TOLERANCE | 15e-6 | frequency tolerance PHI (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) |
skipping to change at page 18, line 24 skipping to change at page 17, line 24
| MINDISP | .005 | minimum dispersion increment (s) | | MINDISP | .005 | minimum dispersion increment (s) |
| MAXDIST | 1 | distance threshold (1 s) | | MAXDIST | 1 | distance threshold (1 s) |
| MAXSTRAT | 16 | maximum stratum number | | MAXSTRAT | 16 | maximum stratum number |
+-----------+-------+----------------------------------+ +-----------+-------+----------------------------------+
Figure 6: Global Parameters Figure 6: Global Parameters
While these are the only global parameters needed for While these are the only global parameters needed for
interoperability, a larger collection is necessary in any interoperability, a larger collection is necessary in any
implementation. Appendix A.1.1 contains those used by the skeleton implementation. Appendix A.1.1 contains those used by the skeleton
for the mitigation algorithms, clock discipline algorithm and related for the mitigation algorithms, clock discipline algorithm, and
implementation-dependent functions. Some of these parameter values related implementation-dependent functions. Some of these parameter
are cast in stone, like the NTP port number assigned by the IANA and values are cast in stone, like the NTP port number assigned by the
the version number assigned NTPv4 itself. Others like the frequency IANA and the version number assigned NTPv4 itself. Others, like the
tolerance (also called PHI), involve an assumption about the worst frequency tolerance (also called PHI), involve an assumption about
case behavior of a system clock once synchronized and then allowed to the worst-case behavior of a system clock once synchronized and then
drift when its sources have become unreachable. The minimum and allowed to drift when its sources have become unreachable. The
maximum parameters define the limits of state variables as described minimum and maximum parameters define the limits of state variables
in later sections of this document. 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.
7.3. Packet Header Variables 7.3. Packet Header Variables
The most important state variables from an external point of view are The most important state variables from an external point of view are
the packet header variables described in Figure 7 and below. The NTP the packet header variables described in Figure 7 and below. The NTP
packet header consists of an integral number of 32-bit (4 octet) packet header consists of an integral number of 32-bit (4 octet)
words in network byte order. The packet format consists of three words in network byte order. The packet format consists of three
components, the header itself, one or more optional extension fields components: the header itself, one or more optional extension fields,
and an optional message authentication code (MAC). The header and an optional message authentication code (MAC). The header
component is identical to the NTPv3 header and previous versions. component is identical to the NTPv3 header and previous versions.
The optional extension fields are used by the Autokey public key The optional extension fields are used by the Autokey public key
cryptographic algorithms described in [I-D.ietf-ntp-autokey]. The cryptographic algorithms described in [RFC5906]. The optional MAC is
optional MAC is used by both Autokey and the symmetric key used by both Autokey and the symmetric key cryptographic algorithm
cryptographic algorithm described in this RFC. described in this RFC.
+-----------+------------+-----------------------+ +-----------+------------+-----------------------+
| 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 |
skipping to change at page 19, line 28 skipping to change at page 18, line 28
| 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 |
| dgst | dgst | message digest | | dgst | dgst | message digest |
+-----------+------------+-----------------------+ +-----------+------------+-----------------------+
Figure 7: Packet Header Variables Figure 7: Packet Header Variables
The NTP packet is a UDP datagram[RFC0768]. Some fields use multiple The NTP packet is a UDP datagram [RFC0768]. Some fields use multiple
words and others are packed in smaller fields within a word. The NTP words and others are packed in smaller fields within a word. The NTP
packet header shown in Figure 8 has 12 words followed by optional packet header shown in Figure 8 has 12 words followed by optional
extension fields and finally an optional message authentication code extension fields and finally an optional message authentication code
(MAC) consisting of the key identifier field and message digest (MAC) consisting of the Key Identifier field and Message Digest
field. field.
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 | Stratum | Poll | Precision | |LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay | | Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion | | Root Dispersion |
skipping to change at page 21, line 6 skipping to change at page 20, line 6
| Key Identifier | | Key Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| dgst (128) | | dgst (128) |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 8: Packet Header Format Figure 8: Packet Header Format
The extension fields are used to add optional capabilities, for The extension fields are used to add optional capabilities, for
example, the Autokey security protocol [I-D.ietf-ntp-autokey]. The example, the Autokey security protocol [RFC5906]. The extension
extension field format is presented in order that the packet can be field format is presented in order for the packet to be parsed
parsed without knowledge of the extension field functions. The MAC without the knowledge of the extension field functions. The MAC is
is used by both Autokey and the symmetric key authentication scheme. used by both Autokey and the symmetric key authentication scheme.
A list of the packet header variables is shown in Figure 7 and A list of the packet header variables is shown in Figure 7 and
described in detail below. Except for a minor variation when using described in detail below. Except for a minor variation when using
the IPv6 address family, these fields are backwards compatible with the IPv6 address family, these fields are backwards compatible with
NTPv3. The packet header fields apply to both transmitted packets (x NTPv3. The packet header fields apply to both transmitted packets (x
prefix) and received packets (r prefix). In Figure 8 the size of prefix) and received packets (r prefix). In Figure 8, the size of
some multiple-word fields is shown in bits if not the default 32 some multiple-word fields is shown in bits if not the default 32
bits. The basic header extends from the beginning of the packet to bits. The basic header extends from the beginning of the packet to
the end of the Transmit Timestamp field. the end of the Transmit Timestamp field.
The fields and associated packet variables (in parentheses) are The fields and associated packet variables (in parentheses) are
interpreted as follows: interpreted as follows:
LI Leap Indicator (leap): 2-bit integer warning of an impending leap 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 second to be inserted or deleted in the last minute of the current
month with values defined in Figure 9. month with values defined in Figure 9.
skipping to change at page 22, line 40 skipping to change at page 21, line 40
| 17-255 | reserved | | 17-255 | reserved |
+--------+-----------------------------------------------------+ +--------+-----------------------------------------------------+
Figure 11: Packet Stratum Figure 11: 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 clock selection algorithms used conveniently mitigated using the same clock selection algorithms used
for external sources (See Appendix A.5.5.1 for an example). for external sources (see Appendix A.5.5.1 for an example).
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.
Root Delay (rootdelay): Total round trip delay to the reference Root Delay (rootdelay): Total round-trip delay to the reference
clock, in NTP short format. clock, in NTP short format.
Root Dispersion (rootdisp): Total dispersion to the reference clock, Root Dispersion (rootdisp): Total dispersion to the reference clock,
in NTP short format. in NTP short format.
Reference ID (refid): 32-bit code identifying the particular server Reference ID (refid): 32-bit code identifying the particular server
or reference clock. The interpretation depends on the value in the or reference clock. The interpretation depends on the value in the
stratum field. For packet stratum 0 (unspecified or invalid) this is stratum field. For packet stratum 0 (unspecified or invalid), this
a four-character ASCII[RFC1345] string, called the kiss code, used is a four-character ASCII [RFC1345] string, called the "kiss code",
for debugging and monitoring purposes. For stratum 1 (reference used for debugging and monitoring purposes. For stratum 1 (reference
clock) this is a four-octet, left-justified, zero-padded ASCII string clock), this is a four-octet, left-justified, zero-padded ASCII
assigned to the reference clock. The authoritative list of Reference string assigned to the reference clock. The authoritative list of
Identifiers is maintained by IANA, however any string beginning with Reference Identifiers is maintained by IANA; however, any string
the ASCII character "X" is reserved for unregistered experimentation beginning with the ASCII character "X" is reserved for unregistered
and development. The identifiers in Figure 12 have been used as experimentation and development. The identifiers in Figure 12 have
ASCII identifiers: 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 23, line 47 skipping to change at page 22, line 49
| 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 |
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
Figure 12: Reference Identifiers Figure 12: Reference Identifiers
Above stratum 1 (secondary servers and clients) this is the reference Above stratum 1 (secondary servers and clients): this is the
identifier of the server and can be used to detect timing loops. If reference identifier of the server and can be used to detect timing
using the IPv4 address family, the identifier is the four-octet IPv4 loops. If using the IPv4 address family, the identifier is the four-
address. If using the IPv6 address family, it is the first four octet IPv4 address. If using the IPv6 address family, it is the
octets of the MD5 hash of the IPv6 address. Note that, when using first four octets of the MD5 hash of the IPv6 address. Note that,
the IPv6 address family on an NTPv4 server with a NTPv3 client, the when using the IPv6 address family on an NTPv4 server with a NTPv3
Reference Identifier field appears to be a random value and a timing client, the Reference Identifier field appears to be a random value
loop might not be detected. and a timing loop might not be detected.
Reference Timestamp: Time when the system clock was last set or Reference Timestamp: Time when the system clock was last set or
corrected, in NTP timestamp format. corrected, in NTP timestamp format.
Origin Timestamp (org): Time at the client when the request departed Origin Timestamp (org): Time at the client when the request departed
for the server, in NTP timestamp format. for the server, in NTP timestamp format.
Receive Timestamp (rec): Time at the server when the request arrived Receive Timestamp (rec): Time at the server when the request arrived
from the client, in NTP timestamp format. from the client, in NTP timestamp format.
Transmit Timestamp (xmt): Time at the server when the response left Transmit Timestamp (xmt): Time at the server when the response left
for the client, in NTP timestamp format. for the client, in NTP timestamp format.
Destination Timestamp (dst): Time at the client when the reply Destination Timestamp (dst): Time at the client when the reply
arrived from the server, in NTP timestamp format. arrived from the server, in NTP timestamp format.
Note: Destination Timestamp field is not included as a header field; Note: The Destination Timestamp field is not included as a header
it is determined upon arrival of the packet and made available in the field; it is determined upon arrival of the packet and made available
packet buffer data structure. in the packet buffer data structure.
If NTP has access to the physical layer, then the timestamps are If the NTP has access to the physical layer, then the timestamps are
associated with the beginning of the symbol after the start of frame. associated with the beginning of the symbol after the start of frame.
Otherwise, implementations should attempt to associate the timestamp Otherwise, implementations should attempt to associate the timestamp
to the earliest accessible point in the frame. to the earliest accessible point in the frame.
The MAC consists of the Key Identifier followed by the Message The MAC consists of the Key Identifier followed by the Message
Digest. The message digest, or cryptosum, is calculated as in Digest. The message digest, or cryptosum, is calculated as in
[RFC1321] over all NTP header and optional extension fields, but not [RFC1321] over all NTP-header and optional extension fields, but not
the MAC itself. the MAC itself.
Extension Field n: See Section 7.5 for a description of the format of Extension Field n: See Section 7.5 for a description of the format of
this field. this field.
Key Identifier (keyid): 32-bit unsigned integer used by the client Key Identifier (keyid): 32-bit unsigned integer used by the client
and server to designate a secret 128-bit MD5 key. and server to designate a secret 128-bit MD5 key.
Message Digest (digest): 128-bit MD5 hash computed over the key Message Digest (digest): 128-bit MD5 hash computed over the key
followed by the NTP packet header and extensions fieds (but not the followed by the NTP packet header and extensions fields (but not the
Key Identifier or Message Digest fields). Key Identifier or Message Digest fields).
It should be noted that the MAC computation used here differs from It should be noted that the MAC computation used here differs from
those defined in [RFC1305] and [RFC4330] but is consistent with how those defined in [RFC1305] and [RFC4330] but is consistent with how
existing implementations generate a MAC. existing implementations generate a MAC.
7.4. The Kiss-o'-Death Packet 7.4. The Kiss-o'-Death Packet
If the Stratum field is 0, which implies unspecified or invalid, the If the Stratum field is 0, which implies unspecified or invalid, the
Reference Identifier field can be used to convey messages useful for Reference Identifier field can be used to convey messages useful for
status reporting and access control. These are called Kiss-o'-Death status reporting and access control. These are called Kiss-o'-Death
(KoD) packets and the ASCII messages they convey are called kiss (KoD) packets and the ASCII messages they convey are called kiss
codes. The KoD packets got their name because an early use was to codes. The KoD packets got their name because an early use was to
tell clients to stop sending packets that violate server access tell clients to stop sending packets that violate server access
controls. The kiss codes can provide useful information for an controls. The kiss codes can provide useful information for an
intelligent client, either NTPv4 or SNTPv4. Kiss codes are encoded intelligent client, either NTPv4 or SNTPv4. Kiss codes are encoded
in four-character ASCII strings left justified and zero filled. The in four-character ASCII strings that are left justified and zero
strings are designed for character displays and log files. A list of filled. The strings are designed for character displays and log
the currently-defined kiss codes is given in Figure 13. Recipients files. A list of the currently defined kiss codes is given in
of kiss codes MUST inspect them and in the following cases take these Figure 13. Recipients of kiss codes MUST inspect them and, in the
actions: following cases, take these actions:
a. For kiss codes: DENY, RSTR the client MUST demobilize any a. For kiss codes DENY and RSTR, the client MUST demobilize any
associations to that server and stop sending packets to that associations to that server and stop sending packets to that
server; server;
b. For kiss code: RATE the client MUST immediately reduce its b. For kiss code RATE, the client MUST immediately reduce its
polling interval to that server and continue to reduce it each polling interval to that server and continue to reduce it each
time it receives a RATE kiss code. time it receives a RATE kiss code.
c. Kiss codes beginning with the ASCII character "X" are for c. Kiss codes beginning with the ASCII character "X" are for
unregistered experimentation and development and MUST be ignored unregistered experimentation and development and MUST be ignored
if not recognized. if not recognized.
d. Other than the above conditions, KoD packets have no protocol d. Other than the above conditions, KoD packets have no protocol
significance and are discarded after inspection. 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. |
| DROP | Lost peer in symmetric mode | | DROP | Lost peer in symmetric mode. |
| RSTR | Access denied due to local policy | | RSTR | Access denied due to local policy. |
| INIT | The association has not yet synchronized for the first | | INIT | The association has not yet synchronized for the first |
| | time | | | time. |
| MCST | The association belongs to a dynamically discovered server | | MCST | The association belongs to a dynamically discovered server.|
| 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. |
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
Figure 13: Kiss Codes Figure 13: Kiss Codes
The Receive Timestamp and the Transmit Timestamp (set by the server) The Receive Timestamp and the Transmit Timestamp (set by the server)
are undefined when in a KoD packet and MUST NOT be relied upon to are undefined when in a KoD packet and MUST NOT be relied upon to
have valid values and MUST be discarded. have valid values and MUST be discarded.
7.5. 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 an extension header and before the MAC, which is always present when an extension
field is present. Other than defining the field format, this field is present. Other than defining the field format, this
document makes no use of the field contents. An extension field document makes no use of the field contents. An extension field
contains a request or response message in the format shown in contains a request or response message in the format shown in
Figure 14. Figure 14.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . .
. Value . . Value .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Padding (as needed) | | Padding (as needed) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 14: Extension Field Format Figure 14: Extension Field Format
All extension fields are zero-padded to a word (4 octets) boundary. All extension fields are zero-padded to a word (four octets)
The Field Type field is specific to the defined function and is not boundary. The Field Type field is specific to the defined function
elaborated here. While the minimum field length containing required and is not elaborated here. While the minimum field length
fields is 4 words (16 octets), a maximum field length remains to be containing required fields is four words (16 octets), a maximum field
established. length remains to be established.
The Length field is a 16-bit unsigned integer which indicates the The Length field is a 16-bit unsigned integer that indicates the
length of the entire extension field in octets, including the Padding length of the entire extension field in octets, including the Padding
field. field.
8. On Wire Protocol 8. On-Wire Protocol
The heart of the NTP on-wire protocol is the core mechanism which The heart of the NTP on-wire protocol is the core mechanism that
exchanges time values between servers, peers and clients. It is exchanges time values between servers, peers, and clients. It is
inherently resistant to lost or duplicate packets. Data integrity is inherently resistant to lost or duplicate packets. Data integrity is
provided by the IP and UDP checksums. No flow control or provided by the IP and UDP checksums. No flow control or
retransmission facilities are provided or necessary. The protocol retransmission facilities are provided or necessary. The protocol
uses timestamps, either extracted from packet headers or struck from uses timestamps, which are either extracted from packet headers or
the system clock upon the arrival or departure of a packet. struck from the system clock upon the arrival or departure of a
Timestamps are precision data and should be restruck in case of link packet. Timestamps are precision data and should be restruck in the
level retransmission and corrected for the time to compute a MAC on case of link-level retransmission and corrected for the time to
transmit. compute a MAC in transmit.
NTP messages make use of two different communication modes, one-to- NTP messages make use of two different communication modes, one-to-
one and one-to-many, commonly referred to as unicast and broadcast. one and one-to-many, commonly referred to as unicast and broadcast.
For the purposes of this document, the term broadcast is interpreted For the purposes of this document, the term broadcast is interpreted
as any available one-to-many mechanism. For IPv4 this equates to as any available one-to-many mechanism. For IPv4, this equates to
either IPv4 broadcast or IPv4 multicast. For IPv6 this equates to either IPv4 broadcast or IPv4 multicast. For IPv6, this equates to
IPv6 multicast. For this purpose, IANA has allocated the IPv4 IPv6 multicast. For this purpose, IANA has allocated the IPv4
multicast address 224.0.1.1 and the IPv6 multicast address ending multicast address 224.0.1.1 and the IPv6 multicast address ending
:101, with prefix determined by scoping rules. Any other non- :101, with the prefix determined by scoping rules. Any other non-
allocated multicast address may also be used in addition to these allocated multicast address may also be used in addition to these
allocated multicast addresses. allocated multicast addresses.
The on-wire protocol uses four timestamps numbered t1 through t4 and The on-wire protocol uses four timestamps numbered t1 through t4 and
three state variables org, rec and xmt, as shown in Figure 15. This three state variables org, rec, and xmt, as shown in Figure 15. This
figure shows the most general case where each of two peers, A and B, figure shows the most general case where each of two peers, A and B,
independently measure the offset and delay relative to the other. independently measure the offset and delay relative to the other.
For purposes of illustration the packet timestamps are shown in lower For purposes of illustration, the packet timestamps are shown in
case, while the state variables are shown in upper case. The state lowercase, while the state variables are shown in uppercase. The
variables are copied from the packet timestamps upon arrival or state variables are copied from the packet timestamps upon arrival or
departure of a packet. departure of a packet.
t2 t3 t6 t7 t2 t3 t6 t7
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
| 0 | | t1 | | t3 | | t5 | | 0 | | t1 | | t3 | | t5 |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
| 0 | | t2 | | t4 | | t6 | Packet | 0 | | t2 | | t4 | | t6 | Packet
+---------+ +---------+ +---------+ +---------+ Timestamps +---------+ +---------+ +---------+ +---------+ Timestamps
| t1 | |t3=clock | | t5 | |t7=clock | | t1 | |t3=clock | | t5 | |t7=clock |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
skipping to change at page 30, line 4 skipping to change at page 28, line 51
|t4=clock | |t8=clock | |t4=clock | |t8=clock |
+---------+ +---------+ +---------+ +---------+
Peer A Peer A
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
org | 0 | | t3<>0? | | T3 | | t7<>T3? | org | 0 | | t3<>0? | | T3 | | t7<>T3? |
+---------+ +---------+ +---------+ +---------+ State +---------+ +---------+ +---------+ +---------+ State
rec | 0 | | T4 | | T4 | | T8 | Variables rec | 0 | | T4 | | T4 | | T8 | Variables
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
xmt | T1 | | t1=T1? | | T5 | | t5=T5? | xmt | T1 | | t1=T1? | | T5 | | t5=T5? |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
Figure 15: On-Wire Protocol Figure 15: On-Wire Protocol
In the figure the first packet transmitted by A contains only the In the figure, the first packet transmitted by A contains only the
origin timestamp t1, which is then copied to T1. B receives the origin timestamp t1, which is then copied to T1. B receives the
packet at t2 and copies t1 to T1 and the receive timestamp t2 to T2. packet at t2 and copies t1 to T1 and the receive timestamp t2 to T2.
At this time or some time later at t3, B sends a packet to A At this time or some time later at t3, B sends a packet to A
containing t1 and t2 and in addition the transmit timestamp t3. All containing t1 and t2 and the transmit timestamp t3. All three
three timestamps are copied to the corresponding state variables. A timestamps are copied to the corresponding state variables. A
receives the packet at t4 containing the three timestamps t1, t2 and receives the packet at t4 containing the three timestamps t1, t2, and
t3 and in addition the destination timestamp t4. These four t3 and the destination timestamp t4. These four timestamps are used
timestamps are used to compute the offset and delay of B relative to to compute the offset and delay of B relative to A, as described
A, as described below. below.
Before the xmt and org state variables are updated, two sanity checks Before the xmt and org state variables are updated, two sanity checks
are performed in order to protect against duplicate, bogus or are performed in order to protect against duplicate, bogus, or
replayed packets. In the exchange above, a packet is duplicate or replayed packets. In the exchange above, a packet is duplicate or
replay if the transmit timestamp t3 in the packet matches the org replay if the transmit timestamp t3 in the packet matches the org
state variable T3. A packet is bogus if the origin timestamp t1 in state variable T3. A packet is bogus if the origin timestamp t1 in
the packet does not match the xmt state variable T1. In either of the packet does not match the xmt state variable T1. In either of
these cases the state variables are updated, then the packet is these cases, the state variables are updated, then the packet is
discarded. To protect against replay of the last transmitted packet, discarded. To protect against replay of the last transmitted packet,
the xmt state variable is set to zero immediately after a successful the xmt state variable is set to zero immediately after a successful
bogus check. bogus check.
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) + (T3-T4)] theta = T(B) - T(A) = 1/2 * [(T2-T1) + (T3-T4)]
and the round trip delay and the round-trip 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 sums and differences 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 they can represent
values from 34 years in the past to 34 years in the future. In other unambiguous values from 34 years in the past to 34 years in the
words, the time of the client must be set within 34 years of the future. In other words, the time of the client must be set within 34
server before the service is started. This is a fundamental years of the server before the service is started. This is a
limitation with 64-bit integer arithmetic. fundamental 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
timestamp magnitudes, there is no loss in significance, yet the timestamp magnitudes, there is no loss in significance, yet the
unambiguous range is restored from 34 years to 68 years. unambiguous range is restored from 34 years to 68 years.
In some scenarios where the initial frequency offset of the client is In some scenarios where the initial frequency offset of the client is
relatively large and the actual propagation time small, it is relatively large and the actual propagation time small, it is
possible for the delay computation to becomes negative. For possible for the delay computation to become 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 delta should misleading in subsequent computations, the value of delta should be
be clamped not less than s.rho, where s.rho is the system precision clamped not less than s.rho, where s.rho is the system precision
described in Section 11.1, expressed in seconds. 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 a Section 9 and filling in the remaining protocol fields are given in a Section 9 and
following sections and in the appendix. following sections and in the appendix.
skipping to change at page 31, line 39 skipping to change at page 30, line 40
delay. This vulnerability can be avoided by setting the xmt state delay. This vulnerability can be avoided by setting the xmt state
variable to zero after computing the offset and delay. variable to zero after computing the offset and delay.
9. Peer Process 9. Peer Process
The process descriptions to follow include a listing of the important The process descriptions to follow include a listing of the important
state variables followed by an overview of the process operations state variables followed by an overview of the process operations
implemented as routines. Frequent reference is made to the skeleton implemented as routines. Frequent reference is made to the skeleton
in the appendix. The skeleton includes C-language fragments that in the appendix. The skeleton includes C-language fragments that
describe the functions in more detail. It includes the parameters, describe the functions in more detail. It includes the parameters,
variables and declarations necessary for a conforming NTPv4 variables, and declarations necessary for a conforming NTPv4
implementation. However, many additional variables and routines may implementation. However, many additional variables and routines may
be necessary in a working implementation. be necessary in a working implementation.
The peer process is called upon arrival of a server or peer packet. The peer process is called upon arrival of a server or peer packet.
It runs the on-wire protocol to determine the clock offset and round 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 trip delay and computes statistics used by the system and poll
poll processes. Peer variables are instantiated in the association processes. Peer variables are instantiated in the association data
data structure when the structure is initialized and updated by structure when the structure is initialized and updated by arriving
arriving packets. There is a peer process, poll process and packets. There is a peer process, poll process, and association
association for each server. process for each server.
9.1. Peer Process Variables 9.1. Peer Process Variables
Figure 16, Figure 17, Figure 18 and Figure 19 summarize the common Figures 16, 17, 18, and 19 summarize the common names, formula names,
names, formula names and a short description of the peer variables. and a short description of the peer variables. The common names and
The common names and formula names are interchangeable; formula names formula names are interchangeable; formula names are intended to
are intended to increase readability of equations in this increase readability of equations in this specification. Unless
specification. Unless noted otherwise, all peer variables have noted otherwise, all peer variables have assumed prefix p.
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 |
+---------+----------+-----------------------+ +---------+----------+-----------------------+
skipping to change at page 33, line 6 skipping to change at page 32, line 4
+------+---------+--------------------+ +------+---------+--------------------+
| Name | Formula | Description | | Name | Formula | Description |
+------+---------+--------------------+ +------+---------+--------------------+
| 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 | | t | t | packet time |
+------+---------+--------------------+ +------+---------+--------------------+
Figure 18: Peer Process Timestamp Variables Figure 18: Peer Process Timestamp Variables
+--------+---------+-----------------+ +--------+---------+-----------------+
| Name | Formula | Description | | Name | Formula | Description |
+--------+---------+-----------------+ +--------+---------+-----------------+
| offset | theta | clock offset | | offset | theta | clock offset |
| delay | delta | roundtrip delay | | delay | delta | round-trip delay|
| disp | epsilon | dispersion | | disp | epsilon | dispersion |
| jitter | psi | jitter | | jitter | psi | jitter |
| filter | filter | clock filter | | filter | filter | clock filter |
| tp | t_p | filter time | | tp | t_p | filter time |
+--------+---------+-----------------+ +--------+---------+-----------------+
Figure 19: Peer Process Statistics Variables Figure 19: Peer Process Statistics Variables
The following configuration variables are normally initialized when The following configuration variables are normally initialized when
the association is mobilized, either from a configuration file or the association is mobilized, either from a configuration file or
upon the arrival of the first packet for an unknown association. upon the arrival of the first packet for an unknown association.
srcaddr: IP address of the remote server or reference clock. This srcaddr: IP address of the remote server or reference clock. This
becomes the destination IP address in packets sent from this becomes the destination IP address in packets sent from this
association. association.
srcport: UDP port number of the server or reference clock. This srcport: UDP port number of the server or reference clock. This
becomes the destination port number in packets sent from this becomes the destination port number in packets sent from this
association. When operating in symmetric modes (1 and 2) this field association. When operating in symmetric modes (1 and 2), this field
must contain the NTP port number PORT (123) assigned by the IANA. In must contain the NTP port number PORT (123) assigned by the IANA. In
other modes it can contain any number consistent with local policy. other modes, it can contain any number consistent with local policy.
dstaddr: IP address of the client. This becomes the source IP dstaddr: IP address of the client. This becomes the source IP
address in packets sent from this association. address in packets sent from this association.
dstport: UDP port number of the client, ordinarily the NTP port dstport: UDP port number of the client, ordinarily the NTP port
number PORT (123) assigned by the IANA. This becomes the source port number PORT (123) assigned by the IANA. This becomes the source port
number in packets sent from this association. number in packets sent from this association.
keyid: Symmetric key ID for the 128-bit MD5 key used to generate and 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 verify the MAC. The client and server or peer can use different
skipping to change at page 34, line 6 skipping to change at page 32, line 51
The variables defined in Figure 17 are updated from the packet header The variables defined in Figure 17 are updated from the packet header
as each packet arrives. They are interpreted in the same way as the as each packet arrives. They are interpreted in the same way as the
packet variables of the same names. It is convenient for later packet variables of the same names. It is convenient for later
processing to convert the NTP short format packet values r.rootdelay processing to convert the NTP short format packet values r.rootdelay
and r.rootdisp to floating doubles as peer variables. and r.rootdisp to floating doubles as peer variables.
The variables defined in Figure 18 include the timestamps exchanged The variables defined in Figure 18 include the timestamps exchanged
by the on-wire protocol in Section 8. The t variable is the seconds 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 counter c.t associated with these values. The c.t variable is
maintained by the clock adjust process described in Section 12. It maintained by the clock-adjust process described in Section 12. It
counts the seconds since the service was started. The variables counts the seconds since the service was started. The variables
defined in Figure 19 include the statistics computed by the defined in Figure 19 include the statistics computed by the
clock_filter() routine described in Section 10. The tp variable is clock_filter() routine described in Section 10. The tp variable is
the seconds counter associated with these values. the seconds counter associated with these values.
9.2. Peer Process Operations 9.2. Peer Process Operations
The receive routine defines the process flow upon the arrival of a The receive routine defines the process flow upon the arrival of a
packet. An example is described by the receive() routine in packet. An example is described by the receive() routine in
Appendix A.5.1. There is no specific method required for access Appendix A.5.1. There is no specific method required for access
control, although it is recommended that implementations include such control, although it is recommended that implementations include such
a scheme, which is similar to many others now in widespread use. The a scheme, which is similar to many others now in widespread use. The
access() routine in Appendix A.5.4 describes a method of implementing access() routine in Appendix A.5.4 describes a method of implementing
access restrictions using an access control list (ACL). Format access restrictions using an access control list (ACL). Format
checks require correct field length and alignment, acceptable version checks require correct field length and alignment, acceptable version
number (1-4) and correct extension field syntax, if present. number (1-4), and correct extension field syntax, if present.
There is no specific requirement for authentication; however, if There is no specific requirement for authentication; however, if
authentication is implemented, then the MD5 keyed hash algorithm authentication is implemented, then the MD5-keyed hash algorithm
described in [RFC1321] must be supported. described in [RFC1321] must be supported.
Next, the association table is searched for matching source address Next, the association table is searched for matching source address
and source port, for example using the find_assoc() routine in and source port, for example, using the find_assoc() routine in
Appendix A.5.1. Figure 20 is a dispatch table where the columns Appendix A.5.1. Figure 20 is a dispatch table where the columns
correspond to the packet mode and rows correspond to the association correspond to the packet mode and rows correspond to the association
mode. The intersection of the association and packet modes mode. The intersection of the association and packet modes
dispatches processing to one of the following steps. dispatches processing to one of the following steps.
+------------------+---------------------------------------+ +------------------+---------------------------------------+
| | Packet Mode | | | Packet Mode |
+------------------+-------+-------+-------+-------+-------+ +------------------+-------+-------+-------+-------+-------+
| Association Mode | 1 | 2 | 3 | 4 | 5 | | Association Mode | 1 | 2 | 3 | 4 | 5 |
+------------------+-------+-------+-------+-------+-------+ +------------------+-------+-------+-------+-------+-------+
skipping to change at page 34, line 51 skipping to change at page 33, line 48
| Symm. Active 1 | PROC | PROC | DSCRD | DSCRD | DSCRD | | Symm. Active 1 | PROC | PROC | DSCRD | DSCRD | DSCRD |
| Symm. Passive 2 | PROC | ERR | DSCRD | DSCRD | DSCRD | | Symm. Passive 2 | PROC | ERR | DSCRD | DSCRD | DSCRD |
| Client 3 | DSCRD | DSCRD | DSCRD | PROC | DSCRD | | Client 3 | DSCRD | DSCRD | DSCRD | PROC | DSCRD |
| Server 4 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | | Server 4 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD |
| Broadcast 5 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | | Broadcast 5 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD |
| Bcast Client 6 | DSCRD | DSCRD | DSCRD | DSCRD | PROC | | Bcast Client 6 | DSCRD | DSCRD | DSCRD | DSCRD | PROC |
+------------------+-------+-------+-------+-------+-------+ +------------------+-------+-------+-------+-------+-------+
Figure 20: Peer Dispatch Table Figure 20: Peer Dispatch Table
DSCRD. This indicates a nonfatal violation of protocol as the result DSCRD. This indicates a non-fatal violation of protocol as the
of a programming error, long delayed packet or replayed packet. The result of a programming error, long-delayed packet, or replayed
peer process discards the packet and exits. packet. The peer process discards the packet and exits.
ERR. This indicates a fatal violation of protocol as the result of a ERR. This indicates a fatal violation of protocol as the result of a
programming error, long delayed packet or replayed packet. The peer programming error, long-delayed packet, or replayed packet. The peer
process discards the packet, demobilizes the symmetric passive process discards the packet, demobilizes the symmetric passive
association and exits. association, and exits.
FXMIT. This indicates a client (mode 3) packet matching no FXMIT. This indicates a client (mode 3) packet matching no
association (mode 0). If the destination address is not a broadcast association (mode 0). If the destination address is not a broadcast
address, the server constructs a server (mode 4) packet and returns address, the server constructs a server (mode 4) packet and returns
it to the client without retaining state. The server packet header it to the client without retaining state. The server packet header
is constructed. An example is described by the fast_xmit() routine is constructed. An example is described by the fast_xmit() routine
in Appendix A.5.3. The packet header is assembled from the receive in Appendix A.5.3. The packet header is assembled from the receive
packet and system variables as shown in Figure 21. If the packet and system variables as shown in Figure 21. If the
s.rootdelay and s.rootdisp system variables are stored in floating s.rootdelay and s.rootdisp system variables are stored in floating
double, they must be converted to NTP short format first. double, they must be converted to NTP short format first.
skipping to change at page 35, line 42 skipping to change at page 34, line 40
| r.reftime --> p.reftime | | r.reftime --> p.reftime |
| r.keyid --> p.keyid | | r.keyid --> p.keyid |
+-----------------------------------+ +-----------------------------------+
Figure 21: Receive Packet Header Figure 21: Receive Packet Header
Note that, if authentication fails, the server returns a special Note that, if authentication fails, the server returns a special
message called a crypto-NAK. This message includes the normal NTP message called a crypto-NAK. This message includes the normal NTP
header data shown in Figure 8, but with a MAC consisting of four header data shown in Figure 8, but with a MAC consisting of four
octets of zeros. The client MAY accept or reject the data in the octets of zeros. The client MAY accept or reject the data in the
message. After these actions the peer process exits. message. After these actions, the peer process exits.
If the destination address is a multicast address, the sender is If the destination address is a multicast address, the sender is
operating in manycast client mode. If the packet is valid and the operating in manycast client mode. If the packet is valid and the
server stratum is less than the client stratum, the server sends an server stratum is less than the client stratum, the server sends an
ordinary server (mode 4) packet, but using its unicast destination ordinary server (mode 4) packet, but one which uses its unicast
address. A crypto-NAK is not sent if authentication fails. After destination address. A crypto-NAK is not sent if authentication
these actions the peer process exits. fails. After these actions, the peer process exits.
MANY: This indicates a server (mode 4) packet matching no MANY: This indicates a server (mode 4) packet matching no
association. Ordinarily, this can happen only as the result of a association. Ordinarily, this can happen only as the result of a
manycast server reply to a previously sent multicast client packet. manycast server reply to a previously sent multicast client packet.
If the packet is valid, an ordinary client (mode 3) association is If the packet is valid, an ordinary client (mode 3) association is
mobilized and operation continues as if the association was mobilized mobilized and operation continues as if the association was mobilized
by the configuration file. by the configuration file.
NEWBC. This indicates a broadcast (mode 5) packet matching no NEWBC. This indicates a broadcast (mode 5) packet matching no
association. The client mobilizes either a client (mode 3) or association. The client mobilizes either a client (mode 3) or
broadcast client (mode 6) association. Examples are shown in the broadcast client (mode 6) association. Examples are shown in the
mobilize() and clear() routines in Appendix A.2. Then the packet is mobilize() and clear() routines in Appendix A.2. Then, the packet is
validated and the peer variables initialized. An example is provided validated and the peer variables initialized. An example is provided
by the packet() routine in Appendix A.5.1.1. by the packet() routine in Appendix A.5.1.1.
If the implementation supports no additional security or calibration If the implementation supports no additional security or calibration
functions, the association mode is set to broadcast client (mode 6) functions, the association mode is set to broadcast client (mode 6)
and the peer process exits. Implementations supporting public key and the peer process exits. Implementations supporting public key
authentication MAY run the Autokey or equivalent security protocol. authentication MAY run the Autokey or equivalent security protocol.
Implementations SHOULD set the association mode to 3 and run a short Implementations SHOULD set the association mode to 3 and run a short
client/server exchange to determine the propagation delay. Following client/server exchange to determine the propagation delay. Following
the exchange the association mode is set to 6 and the peer process 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 continues in listen-only mode. Note the distinction between a mode-6
packet, which is reserved for the NTP monitor and control functions, packet, which is reserved for the NTP monitor and control functions,
and a mode-6 association. and a mode-6 association.
NEWPS. This indicates a symmetric active (mode 1) packet matching no NEWPS. This indicates a symmetric active (mode 1) packet matching no
association. The client mobilizes a symmetric passive (mode 2) association. The client mobilizes a symmetric passive (mode 2)
association. An example is shown in the mobilize() and clear() association. An example is shown in the mobilize() and clear()
routines in Appendix A.2. Processing continues in the PROC section routines in Appendix A.2. Processing continues in the PROC section
below. below.
PROC. This indicates a packet matching an existing association. The PROC. This indicates a packet matching an existing association. The
packet timestamps are carefully checked to avoid invalid, duplicate packet timestamps are carefully checked to avoid invalid, duplicate,
or bogus packets. Additional checks are summarized in Figure 22. or bogus packets. Additional checks are summarized in Figure 22.
Note that all packets, including a crypto-NAK, are considered valid Note that all packets, including a crypto-NAK, are considered valid
only if they survive these tests. only if they survive these tests.
+--------------------------+----------------------------------------+ +--------------------------+----------------------------------------+
| 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 |
skipping to change at page 37, line 30 skipping to change at page 36, line 30
| | the source. | | | the source. |
| 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. |
+--------------------------+----------------------------------------+ +--------------------------+----------------------------------------+
Figure 22: Packet Error Checks Figure 22: Packet Error Checks
Processing continues by coping the packet variables to the peer Processing continues by copying the packet variables to the peer
variables as shown in Figure 21. An example is described by the variables as shown in Figure 21. An example is described by the
packet() routine in Appendix A.5.1.1. The receive() routine packet() routine in Appendix A.5.1.1. The receive() routine
implements tests 1-5 in Figure 22; the packet() routine implements implements tests 1-5 in Figure 22; the packet() routine implements
tests 6-7. If errors are found the packet is discarded and the peer tests 6-7. If errors are found, the packet is discarded and the peer
process exits. process exits.
The on-wire protocol calculates the clock offset theta and round trip The on-wire protocol calculates the clock offset theta and round-trip
delay delta from the four most recent timestamps as described in delay delta from the four most recent timestamps as described in
Section 8. While it is in principle possible to do all calculations Section 8. While it is, in principle, possible to do all
except the first-order timestamp differences in fixed-point calculations except the first-order timestamp differences in fixed-
arithmetic, it is much easier to convert the first-order differences point arithmetic, it is much easier to convert the first-order
to floating doubles and do the remaining calculations in that differences to floating doubles and do the remaining calculations in
arithmetic, and this will be assumed in the following description. that arithmetic, and this will be assumed in the following
description.
Next, the 8-bit p.reach shift register in the poll process described 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 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 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 a packet is sent and the rightmost bit is set to zero. As valid
packets arrive, the rightmost bit is set to one. If the register packets arrive, the rightmost bit is set to one. If the register
contains any nonzero bits, the server is considered reachable; contains any nonzero bits, the server is considered reachable;
otherwise, it is unreachable. Since the peer poll interval might otherwise, it is unreachable. Since the peer poll interval might
have changed since the last packet, the host poll interval is have changed since the last packet, the host poll interval is
reviewed. An example is provided by the poll_update() routine in reviewed. An example is provided by the poll_update() routine in
Appendix A.5.7.2. Appendix A.5.7.2.
The dispersion statistic epsilon(t) represents the maximum error due The dispersion statistic epsilon(t) represents the maximum error due
to the frequency tolerance and time since the last packet was sent. to the frequency tolerance and time since the last packet was sent.
It is initialized It is initialized
epsilon(t_0) = r.rho + s.rho + PHI * (T4-T1) epsilon(t_0) = r.rho + s.rho + PHI * (T4-T1)
when the measurement is made at t_0 according to the seconds counter. when the measurement is made at t_0 according to the seconds counter.
Here r.rho is the packet precision described in Section 7.3 and s.rho Here, r.rho is the packet precision described in Section 7.3 and
is the system precision described in Section 11.1, both expressed in s.rho is the system precision described in Section 11.1, both
seconds. These terms are necessary to account for the uncertainty in expressed in seconds. These terms are necessary to account for the
reading the system clock in both the server and the client. 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 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 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 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.
10. Clock Filter Algorithm 10. Clock Filter Algorithm
The clock filter algorithm is part of the peer process. It grooms The clock filter algorithm is part of the peer process. It grooms
the stream of on-wire data to select the samples most likely to the stream of on-wire data to select the samples most likely to
represent accurate time. The algorithm produces the variables shown represent accurate time. The algorithm produces the variables shown
in Figure 19, including the offset (theta), delay (delta), dispersion in Figure 19, including the offset (theta), delay (delta), dispersion
(epsilon), jitter (psi) and time of arrival (t). These data are used (epsilon), jitter (psi), and time of arrival (t). These data are
by the mitigation algorithms to determine the best and final offset used by the mitigation algorithms to determine the best and final
used to discipline the system clock. They are also used to determine offset used to discipline the system clock. They are also used to
the server health and whether it is suitable for synchronization. determine the server health and whether it is suitable for
synchronization.
The clock filter algorithm saves the most recent sample tuples The clock filter algorithm saves the most recent sample tuples
(theta, delta, epsilon, t) in the filter structure, which functions (theta, delta, epsilon, t) in the filter structure, which functions
as an 8-stage shift register. The tuples are saved in the order that as an 8-stage shift register. The tuples are saved in the order that
packets arrive. Here t is the packet time of arrival according to packets arrive. Here, t is the packet time of arrival according to
the seconds counter and should not be confused with the peer variable the seconds counter and should not be confused with the peer variable
tp. tp.
The following scheme is used to insure sufficient samples are in the The following scheme is used to ensure sufficient samples are in the
filter and that old stale data are discarded. Initially, the tuples filter and that old stale data are discarded. Initially, the tuples
of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, 0). of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, 0).
As valid packets arrive, tuples are shifted into the filter causing As valid packets arrive, tuples are shifted into the filter causing
old tuples to be discarded, so eventually only valid tuples remain. old tuples to be discarded, so eventually only valid tuples remain.
If the three low order bits of the reach register are zero,
If the three low-order bits of the reach register are zero,
indicating three poll intervals have expired with no valid packets indicating three poll intervals have expired with no valid packets
received, the poll process calls the clock filter algorithm with a received, the poll process calls the clock filter algorithm with a
dummy tuple just as if the tuple had arrived from the network. If dummy tuple just as if the tuple had arrived from the network. If
this persists for eight poll intervals, the register returns to the this persists for eight poll intervals, the register returns to the
initial condition. 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 delta. Let i index the stages list and the list sorted by increasing delta. Let i index the stages
starting with the lowest delta. If the first tuple epoch t_0 is not starting with the lowest delta. If the first tuple epoch t_0 is not
later than the last valid sample epoch tp, the routine exits without later than the last valid sample epoch tp, the routine exits without
affecting the current peer variables. Otherwise, let epsilon_i be affecting the current peer variables. Otherwise, let epsilon_i be
the dispersion of the ith entry, then the dispersion of the ith entry, then
i=n-1 i=n-1
--- epsilon_i --- epsilon_i
epsilon = \ ---------- epsilon = \ ----------
/ (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 39, line 30 skipping to change at page 38, line 34
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.
The observer should note (a) if all stages contain the dummy tuple The observer should note (a) if all stages contain the dummy tuple
with dispersion MAXDISP, the computed dispersion is a little less with dispersion MAXDISP, the computed dispersion is a little less
than 16 s, (b) each time a valid tuple is shifted into the register, than 16 s, (b) each time a valid tuple is shifted into the register,
the dispersion drops by a little less than half, depending on the the dispersion drops by a little less than half, depending on the
valid tuples dispersion, (c) after the fourth valid packet the valid tuples dispersion, and (c) after the fourth valid packet the
dispersion is usually a little less than 1 s, which is the assumed dispersion is usually a little less than 1 s, which is the assumed
value of the MAXDIST parameter used by the selection algorithm to value of the MAXDIST parameter used by the selection algorithm to
determine whether the peer variables are acceptable or not. determine whether or not the peer variables are acceptable.
Let the first stage offset in the sorted list be theta_0; then, for Let the first stage offset in the sorted list be theta_0; then, for
the other stages in any order, the jitter is the RMS average the other stages in any order, the jitter is the RMS average
+----- -----+^1/2 +----- -----+^1/2
| 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 filter (n > 1). In where n is the number of valid tuples in the filter (n > 1). In
skipping to change at page 39, line 47 skipping to change at page 38, line 52
+----- -----+^1/2 +----- -----+^1/2
| 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 filter (n > 1). In where n is the number of valid tuples in the filter (n > 1). In
order to insure consistency and avoid divide exceptions in other order to ensure consistency and avoid divide exceptions in other
computations, the psi is bounded from below by the system precision computations, the psi is bounded from below by the system precision
s.rho expressed in seconds. While not in general considered a major s.rho expressed in seconds. While not in general considered a major
factor in ranking server quality, jitter is a valuable indicator of factor in ranking server quality, jitter is a valuable indicator of
fundamental timekeeping performance and network congestion state. Of fundamental timekeeping performance and network congestion state. Of
particular importance to the mitigation algorithms is the peer 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 delay and
dispersion. dispersion.
lambda = (delta / 2) + epsilon. lambda = (delta / 2) + epsilon.
Note that epsilon and therefore lambda increase at rate PHI. The Note that epsilon and therefore lambda increase at rate PHI. The
lambda is not a state variable, since lambda is recalculated at each lambda is not a state variable, since lambda is recalculated at each
use. It is a component of the root synchronization distance used by use. It is a component of the root synchronization distance used by
the mitigation algorithms as a metric to evaluate the quality of time the mitigation algorithms as a metric to evaluate the quality of time
available from each server. available from each server.
It is important to note that, unlike NTPv3, NTPv4 associations do not It is important to note that, unlike NTPv3, NTPv4 associations do not
show a timeout condition by setting the stratum to 16 and leap show a timeout condition by setting the stratum to 16 and leap
indicator to 3. The association variables retain the values indicator to 3. The association variables retain the values
determined upon arrival of the last packet. In NTPv4 lambda determined upon arrival of the last packet. In NTPv4, lambda
increases with time, so eventually the synchronization distance increases with time, so eventually the synchronization distance
exceeds the distance threshold MAXDIST, in which case the association exceeds the distance threshold MAXDIST, in which case the association
is considered unfit for synchronization. is considered unfit for synchronization.
An example implementation of the clock filter algorithm is shown in An example implementation of the clock filter algorithm is shown in
the clock_filter() routine of Appendix A.5.2. the clock_filter() routine of Appendix A.5.2.
11. System Process 11. System Process
As each new sample (theta, delta, epsilon, jitter, t) is produced by As each new sample (theta, delta, epsilon, jitter, t) is produced by
the clock filter algorithm, all peer processes are scanned by the the clock filter algorithm, all peer processes are scanned by the
mitigation algorithms consisting of the selection, cluster, combine mitigation algorithms consisting of the selection, cluster, combine,
and 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 cluster algorithm discards the result. In a series of rounds, the cluster algorithm discards the
association statistically furthest from the centroid until a association statistically furthest from the centroid until a
specified minimum number of survivors remain. The combine algorithm specified minimum number of survivors remain. The combine algorithm
produces the best and final statistics on a weighted average basis. produces the best and final statistics on a weighted average basis.
The final offset is passed to the clock discipline algorithm to steer The final offset is passed to the clock discipline algorithm to steer
the system clock to the correct time. the system clock to the correct time.
The cluster algorithm selects one of the survivors as the system The cluster algorithm selects one of the survivors as the system
peer. The associated statistics (theta, delta, epsilon, jitter, t) peer. The associated statistics (theta, delta, epsilon, jitter, t)
are used to construct the system variables inherited by dependent are used to construct the system variables inherited by dependent
servers and clients and made available to other applications running servers and clients and made available to other applications running
on the same machine. on the same machine.
11.1. System Process Variables 11.1. System Process Variables
Figure 23 summarizes the common names, formula names and a short Figure 23 summarizes the common names, formula names, and a short
description of each system variable. Unless noted otherwise, all description of each system variable. Unless noted otherwise, all
variables have assumed prefix s. variables have assumed prefix s.
+-----------+------------+------------------------+ +-----------+------------+------------------------+
| Name | Formula | Description | | Name | Formula | Description |
+-----------+------------+------------------------+ +-----------+------------+------------------------+
| t | t | update time | | t | t | update time |
| p | p | system peer identifier | | p | p | system peer identifier |
| leap | leap | leap indicator | | leap | leap | leap indicator |
| stratum | stratum | stratum | | stratum | stratum | stratum |
skipping to change at page 41, line 32 skipping to change at page 40, line 32
| rootdisp | EPSILON | root dispersion | | rootdisp | EPSILON | root dispersion |
| v | v | survivor list | | v | v | survivor list |
| 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 |
+-----------+------------+------------------------+ +-----------+------------+------------------------+
Figure 23: System Process Variables Figure 23: System Process Variables
Except for the t, p, offset and jitter variables and the NMIN and Except for the t, p, offset, and jitter variables and the NMIN and
CMIN constants, the variables have the same format and interpretation CMIN constants, the variables have the same format and interpretation
as the peer variables of the same name. The NMIN and CMIN parameters as the peer variables of the same name. The NMIN and CMIN parameters
are used by the selection and cluster algorithms described in the are used by the selection and cluster algorithms described in the
next section. next section.
The t variable is the seconds counter at the time of the last update. The t variable is the seconds counter at the time of the last update.
An example is shown by the clock_update() routine in An example is shown by the clock_update() routine in
Appendix A.5.5.4. The p variable is the system peer identifier 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 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. variable has the same format as the packet variable of the same name.
skipping to change at page 42, line 12 skipping to change at page 41, line 15
Initially, all variables are cleared to zero, then the leap is set to Initially, all variables are cleared to zero, then the leap is set to
3 (unsynchronized) and stratum is set to MAXSTRAT (16). Remember 3 (unsynchronized) and stratum is set to MAXSTRAT (16). Remember
that MAXSTRAT is mapped to zero in the transmitted packet. that MAXSTRAT is mapped to zero in the transmitted packet.
11.2. System Process Operations 11.2. System Process Operations
Figure 24 summarizes the system process operations performed by the Figure 24 summarizes the system process operations performed by the
clock select routine. The selection algorithm described in clock select routine. The selection algorithm described in
Section 11.2.1 produces a majority clique of presumed correct Section 11.2.1 produces a majority clique of presumed correct
candidates (truechimers) based on agreement principles. The cluster candidates (truechimers) based on agreement principles. The cluster
algorithm described in Section 11.2.2 discards outlyers to produce algorithm described in Section 11.2.2 discards outliers to produce
the most accurate survivors. The combine algorithm described in the most accurate survivors. The combine algorithm described in
Section 11.2.3 provides the best and final offset for the clock Section 11.2.3 provides the best and final offset for the clock
discipline algorithm. An example is described in Appendix A.5.5.6. discipline algorithm. An example is described in Appendix A.5.5.6.
If the selection algorithm cannot produce a majority clique, or if it If the selection algorithm cannot produce a majority clique, or if it
cannot produce at least CMIN survivors, the system process exits cannot produce at least CMIN survivors, the system process exits
without disciplining the system clock. If successful, the cluster without disciplining the system clock. If successful, the cluster
algorithm selects the statistically best candidate as the system peer algorithm selects the statistically best candidate as the system peer
and its variables are inherited as the system variables. and its variables are inherited as the system variables.
+-----------------+ +-----------------+
skipping to change at page 44, line 15 skipping to change at page 43, line 15
11.2.1. Selection Algorithm 11.2.1. Selection Algorithm
Note that the selection and cluster algorithms are described Note that the selection and cluster algorithms are described
separately, but combined in the code skeleton. The selection separately, but combined in the code skeleton. The selection
algorithm operates to find an intersection interval containing a algorithm operates to find an intersection interval containing a
majority clique of truechimers using Byzantine agreement principles majority clique of truechimers using Byzantine agreement principles
originally proposed by Marzullo [ref6], but modified to improve originally proposed by Marzullo [ref6], but modified to improve
accuracy. An overview of the algorithm is given below and described accuracy. An overview of the algorithm is given below and described
in the first half of the clock_select() routine in Appendix A.5.5.1. in the first half of the clock_select() routine in Appendix A.5.5.1.
First, those servers which are unusable according to the rules of the First, those servers that are unusable according to the rules of the
protocol are detected and discarded as shown by the accept() routine protocol are detected and discarded as shown by the accept() routine
in Appendix A.5.5.3. Next, a set of tuples (p, type, edge) is 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 generated for the remaining candidates. Here, p is the association
identifier and type identifies the upper (+1), middle (0) and lower identifier and type identifies the upper (+1), middle (0), and lower
(-1) endpoints of a correctness interval centered on theta for that (-1) endpoints of a correctness interval centered on theta for that
candidate. This results in three tuples, lowpoint (p, -1, theta - candidate. This results in three tuples, lowpoint (p, -1, theta -
lambda), midpoint (p, 0, theta) and highpoint (p, +1, theta + lambda), midpoint (p, 0, theta), and highpoint (p, +1, theta +
lambda), where lambda is the root synchronization distance. An lambda), where lambda is the root synchronization distance. An
example of this calculation is shown by the rootdist() routine in example of this calculation is shown by the rootdist() routine in
Appendix A.5.1.1. The steps of the algorithm are: Appendix A.5.1.1. The steps of the algorithm are:
1. For each of m associations, place three tuples as defined above 1. For each of m associations, place three tuples as defined above
on the candidate list. on the candidate list.
2. Sort the tuples on the list by the edge component. Order the 2. Sort the tuples on the list by the edge component. Order the
lowpoint, midpoint and highpoint of these intervals from lowest to lowpoint, midpoint, and highpoint of these intervals from lowest to
highest. Set the number of falsetickers f = 0. 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 one endpoint to highest. Add one to c for every lowpoint, subtract one
for every highpoint, add one to d for every midpoint. If c >= m - f, for every highpoint, add one to d for every midpoint. If 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 4. Set c = 0. Scan from highest endpoint to lowest. Add one to c
for 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.
skipping to change at page 45, line 7 skipping to change at page 44, line 7
5A. Success: the intersection interval is [l, u]. 5A. Success: the intersection interval is [l, u].
5B. Add one to f. Is f < (m / 2)? If yes, then go to step 3 again. 5B. Add one to f. Is f < (m / 2)? If yes, then go to step 3 again.
If no, then go to step 6. If no, then go to step 6.
6. Failure; a majority clique could not be found. There are no 6. Failure; a majority clique could not be found. There are no
suitable candidates to discipline the system clock. suitable candidates to discipline the system clock.
The algorithm is described in detail in Appendix A.5.5.1. Note that The algorithm is described in detail in Appendix A.5.5.1. Note that
it starts with the assumption that there are no falsetickers (f = 0) it starts with the assumption that there are no falsetickers (f = 0)
and attempts to find a nonempty intersection interval containing the and attempts to find a non-empty intersection interval containing the
midpoints of all correct servers, i.e., truechimers. If a nonempty midpoints of all correct servers, i.e., truechimers. If a non-empty
interval cannot be found, it increases the number of assumed interval cannot be found, it increases the number of assumed
falsetickers by one and tries again. If a nonempty interval is found falsetickers by one and tries again. If a non-empty interval is
and the number of falsetickers is less than the number of found and the number of falsetickers is less than the number of
truechimers, a majority clique has been found and the midpoint of truechimers, a majority clique has been found and the midpoint of
each truechimer (theta) represents the candidates available to the each truechimer (theta) represents the candidates available to the
cluster algorithm. cluster algorithm.
If a majority clique is not found, or if the number of truechimers is If a majority clique is not found, or if the number of truechimers is
less than CMIN, there are insufficient candidates to discipline the less than CMIN, there are insufficient candidates to discipline the
system clock. CMIN defines the minimum number of servers consistent system clock. CMIN defines the minimum number of servers consistent
with the correctness requirements. Suspicious operators would set with the correctness requirements. Suspicious operators would set
CMIN to insure multiple redundant servers are available for the CMIN to ensure multiple redundant servers are available for the
algorithms to mitigate properly. However, for historic reasons the algorithms to mitigate properly. However, for historic reasons the
default value for CMIN is one. default value for CMIN is one.
11.2.2. Cluster Algorithm 11.2.2. Cluster Algorithm
The candidates of the majority clique are placed on the survivor list The candidates of the majority clique are placed on the survivor list
v in the form of tuples (p, theta_p, psi_p, lambda_p), where p is an v 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 association identifier, theta_p, psi_p, and stratum_p the current
offset, jitter and stratum of association p, respectively, and offset, jitter and stratum of association p, respectively, and
lambda_p is a merit factor equal to stratum_p * MAXDIST + lambda, lambda_p is a merit factor equal to stratum_p * MAXDIST + lambda,
where lambda is the root synchronization distance for association p. where lambda is the root synchronization distance for association p.
The list is processed by the cluster algorithm below. An example is The list is processed by the cluster algorithm below. An example is
shown by the second half of the clock_select() algorithm in shown by the second half of the clock_select() algorithm in
Appendix A.5.5.1. Appendix A.5.5.1.
1. Let (p, theta_p, psi_p, lambda_p) represent a survivor candidate. 1. Let (p, theta_p, psi_p, lambda_p) represent a survivor candidate.
2. Sort the candidates by increasing lambda_p. Let n be the number 2. Sort the candidates by increasing lambda_p. Let n be the number
of candidates and NMIN the minimum required number of survivors. of candidates and NMIN the minimum required number of survivors.
3. For each candidate compute the selection jitter psi_s: 3. For each candidate, compute the selection jitter psi_s:
+----- -----+^1/2 +----- -----+^1/2
| n-1 | | n-1 |
| --- | | --- |
| 1 \ 2 | | 1 \ 2 |
psi_s = | ---- * / (theta_s - theta_j) | psi_s = | ---- * / (theta_s - theta_j) |
| n-1 --- | | n-1 --- |
| j=1 | | j=1 |
+----- -----+ +----- -----+
skipping to change at page 46, line 15 skipping to change at page 45, line 15
5. Select psi_min as the candidate with minimum psi_p. 5. Select psi_min as the candidate with minimum psi_p.
6. Is psi_max < psi_min or n <= NMIN? If yes, follow step 6A; 6. Is psi_max < psi_min or n <= NMIN? If yes, follow step 6A;
otherwise, follow step 6B. otherwise, follow step 6B.
6A. Done. The remaining candidates on the survivor list are ranked 6A. Done. The remaining candidates on the survivor list are ranked
in the order of preference. The first entry on the list represents in the order of preference. The first entry on the list represents
the system peer; its variables are used later to update the system the system peer; its variables are used later to update the system
variables. variables.
6B. Delete the outlyer candidate with psi_max; reduce n by one and go 6B. Delete the outlier candidate with psi_max; reduce n by one and go
back to step 3. back to step 3.
The algorithm operates in a series of rounds where each round The algorithm operates in a series of rounds where each round
discards the statistical outlyer with maximum selection jitter psi_s. discards the statistical outlier with maximum selection jitter psi_s.
However, if psi_s is less than the minimum peer jitter psi_p, no However, if psi_s is less than the minimum peer jitter psi_p, no
improvement is possible by discarding outlyers. This and the minimum improvement is possible by discarding outliers. This and the minimum
number of survivors represent the terminating conditions of the number of survivors represent the terminating conditions of the
algorithm. Upon termination, the final value of psi_max is saved as algorithm. Upon termination, the final value of psi_max is saved as
the system selection jitter PSI_s for use later. the system selection jitter PSI_s for use later.
11.2.3. Combine Algorithm 11.2.3. Combine Algorithm
The clock combine route processes the remaining survivors to produce The clock combine route processes the remaining survivors to produce
the best and final data for the clock discipline algorithm. The the best and final data for the clock discipline algorithm. The
routine processes peer offset and jitter statistics to produce the routine processes peer offset and jitter statistics to produce the
combined system offset THETA and system peer jitter PSI_p, where each combined system offset THETA and system peer jitter PSI_p, where each
skipping to change at page 46, line 47 skipping to change at page 45, line 47
candidate on the survivor list is nominated as the system peer with candidate on the survivor list is nominated as the system peer with
identifier p. The system peer jitter PSI_p is a component of the identifier p. The system peer jitter PSI_p is a component of the
system jitter PSI. It is used along with the selection jitter PSI_s system jitter PSI. It is used along with the selection jitter PSI_s
to produce the system jitter: to produce the system jitter:
PSI = [(PSI_s)^2 + (PSI_p)^2]^1/2 PSI = [(PSI_s)^2 + (PSI_p)^2]^1/2
Each time an update is received from the system peer, the clock Each time an update is received from the system peer, the clock
update routine is called. By rule, an update is discarded if its update routine is called. By rule, an update is discarded if its
time of arrival p.t is not strictly later than the last update used time of arrival p.t is not strictly later than the last update used
s.t. The labels IGNOR, PANIC, ADJ and STEP refer to return codes s.t. The labels IGNOR, PANIC, ADJ, and STEP refer to return codes
from the local clock routine described in the next section. from the local clock routine described in the next section.
IGNORE means the update has been ignored as an outlyer. PANIC means IGNORE means the update has been ignored as an outlier. PANIC means
the offset is greater than the panic threshold PANICT (1000 s) and the offset is greater than the panic threshold PANICT (1000 s) and
SHOULD cause the program to exit with a diagnostic message to the SHOULD cause the program to exit with a diagnostic message to the
system log. STEP means the offset is less than the panic threshold, system log. STEP means the offset is less than the panic threshold,
but greater than the step threshold STEPT (125 ms). In this case the but greater than the step threshold STEPT (125 ms). In this case,
clock is stepped to the correct offset, but since this means all peer the clock is stepped to the correct offset, but since this means all
data have been invalidated, all associations MUST be reset and the peer data have been invalidated, all associations MUST be reset and
client begins as at initial start. the client begins as at initial start.
ADJ means the offset is less than the step threshold and thus a valid ADJ means the offset is less than the step threshold and thus a valid
update. In this case the system variables are updated from the peer update. In this case, the system variables are updated from the peer
variables as shown in Figure 25. variables as shown in Figure 25.
+-------------------------------------------+ +-------------------------------------------+
| System Variable <-- System Peer Variable | | | System Variable <-- System Peer Variable | |
+-------------------------------------------+ +-------------------------------------------+
| s.leap <-- p.leap | | s.leap <-- p.leap |
| s.stratum <-- p.stratum + 1 | | s.stratum <-- p.stratum + 1 |
| s.offset <-- THETA | | s.offset <-- THETA |
| s.jitter <-- PSI | | s.jitter <-- PSI |
| s.rootdelay <-- p.delta_r + delta | | s.rootdelay <-- p.delta_r + delta |
skipping to change at page 47, line 44 skipping to change at page 46, line 44
below by MINDISP. In subnets with very fast processors and networks below by MINDISP. In subnets with very fast processors and networks
and very small delay and dispersion this forces a monotone-definite and very small delay and dispersion this forces a monotone-definite
increase in s.rootdisp (EPSILON), which avoids loops between peers increase in s.rootdisp (EPSILON), which avoids loops between peers
operating at the same stratum. operating at the same stratum.
The system variables are available to dependent application programs The system variables are available to dependent application programs
as nominal performance statistics. The system offset THETA is the as nominal performance statistics. The system offset THETA is the
clock offset relative to the available synchronization sources. The clock offset relative to the available synchronization sources. The
system jitter PSI is an estimate of the error in determining this system jitter PSI is an estimate of the error in determining this
value, elsewhere called the expected error. The root delay DELTA is value, elsewhere called the expected error. The root delay DELTA is
the total round trip delay relative to the primary server. The root the total round-trip delay relative to the primary server. The root
dispersion EPSILON is the dispersion accumulated over the network dispersion EPSILON is the dispersion accumulated over the network
from the primary server. Finally, the root synchronization distance from the primary server. Finally, the root synchronization distance
is defined is defined as:
LAMBDA = EPSILON + DELTA / 2, LAMBDA = EPSILON + DELTA / 2,
which represents the maximum error due all causes and is designated which represents the maximum error due all causes and is designated
the root synchronization distance. the root synchronization distance.
An example of the clock update routine is provided An example of the clock update routine is provided in
inAppendix A.5.5.4. Appendix A.5.5.4.
11.3. Clock Discipline Algorithm 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 quite philosophically
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 mu seconds are design, periodic phase updates at update intervals mu seconds are
used 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 [ref7], a PLL error and indirectly the time error. As shown in [ref7], a PLL
usually works better when network jitter dominates, while a FLL works usually works better when network jitter dominates, while an FLL
better when oscillator wander dominates. This section contains an works better when oscillator wander dominates. This section contains
outline of how the NTPv4 design works. An in-depth discussion of the an outline of how the NTPv4 design works. An in-depth discussion of
design principles is provided in [ref7], which also includes a the design principles is provided in [ref7], which also includes a
performance analysis. performance analysis.
The discipline is implemented as the feedback control system shown in The discipline is implemented as the feedback control system shown in
Figure 26. The variable theta_r represents the combine algorithm Figure 26. 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, cluster and selected by the clock filter algorithm. The selection, cluster, and
combine algorithms combine the data from multiple filters to produce combine algorithms combine the data from multiple filters to 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 the integral of the phase theta_c which closes the loop. The thus the integral of the phase theta_c which closes the loop. The
V_c signal is generated by the clock adjust process in Section 12. V_c signal is generated by the clock-adjust process in Section 12.
The detailed equations that implement these functions are best The detailed equations that implement these functions are best
presented in the routines of Appendix A.5.5.6 and Appendix A.5.6.1. presented in the routines of Appendices A.5.5.6 and A.5.6.1.
theta_r + +---------\ +----------------+ theta_r + +---------\ +----------------+
NTP --------->| Phase \ V_d | | V_s NTP --------->| Phase \ V_d | | V_s
theta_c - | Detector ------>| Clock Filter |----+ theta_c - | Detector ------>| Clock Filter |----+
+-------->| / | | | +-------->| / | | |
| +---------/ +----------------+ | | +---------/ +----------------+ |
| | | |
----- | ----- |
/ \ | / \ |
| VFO | | | VFO | |
skipping to change at page 49, line 29 skipping to change at page 48, line 29
+------.-| Clock | y | Phase/Freq |<---------+ +------.-| Clock | y | Phase/Freq |<---------+
. | Adjust |<-----| Prediction | . . | Adjust |<-----| Prediction | .
. | | | | . . | | | | .
. +---------+ +-------------+ . . +---------+ +-------------+ .
....................................... .......................................
Figure 26: Clock Discipline Feedback Loop Figure 26: 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 non-linear 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 non-linear loop described below does this
15 minutes. Another case is when occasional bursts of large jitter in 15 minutes. Another case is when occasional bursts of large
are present due to congested network links. The state machine jitter 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.
Figure 27 contains a summary of the variables and parameters Figure 27 contains a summary of the variables and parameters
including the variables (lower case) or parameters (upper case) name, including the variable (lowercase) or parameter (uppercase) name,
formula name and short description. Unless noted otherwise, all formula name, and short description. Unless noted otherwise, all
variables have assumed prefix c. The variables t, tc, state, hyster variables have assumed prefix c. The variables t, tc, state, hyster,
and count are integers; the remaining variables are floating doubles. and count are integers; the remaining variables are floating doubles.
The function of each will be explained in the algorithm descriptions The function of each will be explained in the algorithm descriptions
below. below.
+--------+------------+--------------------------+ +--------+------------+--------------------------+
| Name | Formula | Description | | Name | Formula | Description |
+--------+------------+--------------------------+ +--------+------------+--------------------------+
| t | timer | seconds counter | | t | timer | seconds counter |
| offset | theta | combined offset | | offset | theta | combined offset |
| resid | theta_r | residual offset | | resid | theta_r | residual offset |
skipping to change at page 50, line 33 skipping to change at page 49, line 33
| TC | 16 | time constant scale | | TC | 16 | time constant scale |
| AVG | 8 | averaging constant | | AVG | 8 | averaging constant |
+--------+------------+--------------------------+ +--------+------------+--------------------------+
Figure 27: Clock Discipline Variables and Parameters Figure 27: Clock Discipline Variables and Parameters
The process terminates immediately if the offset is greater than the The process terminates immediately if the offset is greater than the
panic threshold PANICT (1000 s). The state transition function is panic threshold PANICT (1000 s). The state transition function is
described by the rstclock() function in Appendix A.5.5.7. Figure 28 described by the rstclock() function in Appendix A.5.5.7. Figure 28
shows the state transition function used by this routine. It has shows the state transition function used by this routine. It has
four columns showing respectively the state name, predicate and four columns showing, respectively, the state name, predicate and
action if the offset theta is less than the step threshold, the action if the offset theta is less than the step threshold, the
predicate and actions otherwise, and finally some comments. predicate and actions otherwise, and finally some comments.
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| State | theta < STEP | theta > STEP | Comments | | State | theta < STEP | theta > STEP | Comments |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| NSET | ->FREQ | ->FREQ | no frequency | | NSET | ->FREQ | ->FREQ | no frequency |
| | adjust time | step time | file | | | adjust time | step time | file |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| FSET | ->SYNC | ->SYNC | frequency | | FSET | ->SYNC | ->SYNC | frequency |
| | adjust time | step time | file | | | adjust time | step time | file |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| SPIK | ->SYNC | if < 900 s ->SPIK | outlyer | | SPIK | ->SYNC | if < 900 s ->SPIK | outlier |
| | adjust freq | else ->SYNC | detected | | | adjust freq | else ->SYNC | detected |
| | adjust time | step freq | | | | adjust time | step freq | |
| | | step time | | | | | step time | |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| FREQ | if < 900 s ->FREQ | if < 900 s ->FREQ | initial | | FREQ | if < 900 s ->FREQ | if < 900 s ->FREQ | initial |
| | else ->SYNC | else ->SYNC | frequency | | | else ->SYNC | else ->SYNC | frequency |
| | step freq | step freq | | | | step freq | step freq | |
| | adjust time | adjust time | | | | adjust time | adjust time | |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
| SYNC | ->SYNC | if < 900 s ->SPIK | normal | | SYNC | ->SYNC | if < 900 s ->SPIK | normal |
| | adjust freq | else ->SYNC | operation | | | adjust freq | else ->SYNC | operation |
| | adjust time | step freq | | | | adjust time | step freq | |
| | | step time | | | | | step time | |
+-------+---------------------+-------------------+--------------+ +-------+---------------------+-------------------+--------------+
Figure 28: State Transition Function Figure 28: State Transition Function
In the table entries the next state is identified by the arrow -> In the table entries, the next state is identified by the arrow ->
with the actions listed below. Actions such as adjust time and with the actions listed below. Actions such as adjust time and
adjust frequency are implemented by the PLL/FLL feedback loop in the adjust frequency are implemented by the PLL/FLL feedback loop in the
local_clock() routine. A step clock action is implemented by setting local_clock() routine. A step clock action is implemented by setting
the clock directly, but this is done only after the stepout threshold 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 WATCH (900 s) when the offset is more than the step threshold STEPT
(.125 s). This resists clock steps under conditions of extreme (.125 s). This resists clock steps under conditions of extreme
network congestion. network congestion.
The jitter (psi) and wander (omega) statistics are computed using an The jitter (psi) and wander (omega) statistics are computed using an
exponential average with weight factor AVG. The time constant exponential average with weight factor AVG. The time constant
exponent (tau) is determined by comparing psi with the magnitude of exponent (tau) is determined by comparing psi with the magnitude of
the current offset theta. If the offset is greater than PGATE (4) the current offset theta. If the offset is greater than PGATE (4)
times the clock jitter, the hysteresis counter hyster is reduced by times the clock jitter, the hysteresis counter hyster is reduced by
two; otherwise, it is increased by one. If hyster increases to the two; otherwise, it is increased by one. If hyster increases to the
upper limit LIMIT (30), tau is increased by one; if it decreases to upper limit LIMIT (30), tau is increased by one; if it decreases to
the lower limit -LIMIT (-30), tau is decreased by one. Normally, tau the lower limit -LIMIT (-30), tau is decreased by one. Normally, tau
hovers near MAXPOLL, but quickly decreases if a temperature spike hovers near MAXPOLL, but quickly decreases if a temperature spike
causes a frequency surge. causes a frequency surge.
12. Clock Adjust Process 12. Clock-Adjust Process
The actual clock adjustment process runs at one-second intervals to The actual clock-adjust process runs at one-second intervals to add
add the frequency correction and a fixed percentage of the residual the frequency correction and a fixed percentage of the residual
offset theta_r. The theta_r is in effect the exponential decay of offset theta_r. The theta_r is, in effect, the exponential decay of
the theta value produced by the loop filter at each update. The TC the theta value produced by the loop filter at each update. The TC
parameter scales the time constant to match the poll interval for parameter scales the time constant to match the poll interval for
convenience. Note that the dispersion EPSILON increases by PHI at convenience. Note that the dispersion EPSILON increases by PHI at
each second. each second.
The clock adjust process includes a timer interrupt facility driving The clock-adjust process includes a timer interrupt facility driving
the seconds counter c.t. It begins at zero when the service starts the seconds counter c.t. It begins at zero when the service starts
and increments once each second. At each interrupt the and increments once each second. At each interrupt, the
clock_adjust() routine is called to incorporate the clock discipline clock_adjust() routine is called to incorporate the clock discipline
time and frequency adjustments, then the associations are scanned to time and frequency adjustments, then the associations are scanned to
determine if the seconds counter equals or exceeds the p.next state determine if the seconds counter equals or exceeds the p.next state
variable defined in the next section. If so, the poll process is variable defined in the next section. If so, the poll process is
called to send a packet and compute the next p.next value. called to send a packet and compute the next p.next value.
An example of the clock adjustment process is shown by the An example of the clock-adjust process is shown by the clock_adjust()
clock_adjust() routine in Appendix A.5.6.1. routine in Appendix A.5.6.1.
13. 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 in order to manage the clock filter and reach servers are reachable in order to manage the clock filter and reach
register. register.
13.1. Poll Process Variables 13.1. Poll Process Variables
Figure 29 summarizes the common names, formula names and a short Figure 29 summarizes the common names, formula names, and a short
description of the poll process variables(lower case) and parameters description of the poll process variables (lowercase) and parameters
(upper case). Unless noted otherwise, all variables have assumed (uppercase). Unless noted otherwise, all variables have assumed
prefix p. 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 |
+---------+---------+--------------------+ +---------+---------+--------------------+
Figure 29: Poll Process Variables and Parameters Figure 29: Poll Process Variables and Parameters
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. Following is a structure along with the peer process variables. The following is a
detailed description of the variables. The parameters will be called detailed description of the variables. The parameters will be called
out in the following text. out in the following text.
hpoll: signed integer representing the poll exponent, in log2 seconds hpoll: signed integer representing the poll exponent, in log2 seconds
last: integer representing the seconds counter when the most recent last: integer representing the seconds counter when the most recent
packet was sent packet was sent
next: integer representing the seconds counter when the next packet next: integer representing the seconds counter when the next packet
is to be sent is to be sent
reach: 8-bit integer shift register shared by the peer and poll reach: 8-bit integer shift register shared by the peer and poll
processes processes
unreach: integer representing the number of seconds the server has unreach: integer representing the number of seconds the server has
been unreachable been unreachable
13.2. Poll Process Operations 13.2. Poll Process Operations
As described previously, once each second the clock adjust process is As described previously, once each second the clock-adjust process is
called. This routine calls the poll routine for each association in called. This routine calls the poll routine for each association in
turn. If the time for the next poll message is greater than the turn. If the time for the next poll message is greater than the
seconds counter, the routine returns immediately. Symmetric (modes seconds counter, the routine returns immediately. Symmetric (modes
1, 2), client (mode 3) and broadcast server (mode 5) associations 1, 2), client (mode 3), and broadcast server (mode 5) associations
routinely send packets. A broadcast client (mode 6) association runs routinely send packets. A broadcast client (mode 6) association runs
the routine to update the reach and unreach variables, but does not the routine to update the reach and unreach variables, but does not
send packets. The poll process calls the transmit process to send a send packets. The poll process calls the transmit process to send a
packet. If in a burst (burst > 0), nothing further is done except packet. If in a burst (burst > 0), nothing further is done except
call the poll update routine to set the next poll interval. call the poll update routine to set the next poll interval.
If not in a burst, the 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 is heard for the last three poll intervals, the clock filter routine is
called to increase the dispersion. An example is shown in called to increase the dispersion. An example is shown in
skipping to change at page 54, line 38 skipping to change at page 53, line 38
increases until reaching BEACON, when it starts over from the increases until reaching BEACON, when it starts over from the
beginning. beginning.
The poll() routine includes a feature that backs off the poll The poll() routine includes a feature that backs off the poll
interval if the server becomes unreachable. If reach is nonzero, the interval if the server becomes unreachable. If reach is nonzero, the
server is reachable and unreach is set to zero; otherwise, unreach is server is reachable and unreach is set to zero; otherwise, unreach is
incremented by one for each poll to the maximum UNREACH. Thereafter incremented by one for each poll to the maximum UNREACH. Thereafter
for each poll hpoll is increased by one, which doubles the poll for each poll hpoll is increased by one, which doubles the poll
interval up to the maximum MAXPOLL determined by the poll_update() interval up to the maximum MAXPOLL determined by the poll_update()
routine. When the server again becomes reachable, unreach is set to routine. When the server again becomes reachable, unreach is set to
zero, hpoll is reset to the tc system variable and operation resumes zero, hpoll is reset to the tc system variable, and operation resumes
normally. normally.
A packet is sent by the transmit process. Some header values are A packet is sent by the transmit process. Some header values are
copied from the peer variables left by a previous packet and others copied from the peer variables left by a previous packet and others
from the system variables. Figure 30 shows which values are copied from the system variables. Figure 30 shows which values are copied
to each header field. In those implementations using floating double to each header field. In those implementations, using floating
data types for root delay and root dispersion, these must be double data types for root delay and root dispersion, these must be
converted to NTP short format. All other fields are either copied converted to NTP short format. All other fields are either copied
intact from peer and system variables or struck as a timestamp from intact from peer and system variables or struck as a timestamp from
the system clock. the system clock.
+-----------------------------------+ +-----------------------------------+
| Packet Variable <-- Variable | | Packet Variable <-- Variable |
+-----------------------------------+ +-----------------------------------+
| x.leap <-- s.leap | | x.leap <-- s.leap |
| x.version <-- s.version | | x.version <-- s.version |
| x.mode <-- s.mode | | x.mode <-- s.mode |
skipping to change at page 55, line 31 skipping to change at page 54, line 31
| x.keyid <-- p.keyid | | x.keyid <-- p.keyid |
| x.digest <-- md5 digest | | x.digest <-- md5 digest |
+-----------------------------------+ +-----------------------------------+
Figure 30: xmit_packet Packet Header Figure 30: xmit_packet Packet Header
The poll update routine is called when a valid packet is received and The poll update routine is called when a valid packet is received and
immediately after a poll message has been sent. If in a burst, the 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 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 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 and hpoll from the poll routine, but not less than MINPOLL or greater
greater than MAXPOLL. Thus the clock discipline can be oversampled, than MAXPOLL. Thus, the clock discipline can be oversampled but not
but not undersampled. This is necessary to preserve subnet dynamic undersampled. This is necessary to preserve subnet dynamic behavior
behavior and protect against protocol errors. and protect against protocol errors.
The poll exponent is converted to an interval which when added to the The poll exponent is converted to an interval, which, when added to
last poll time variable determines the value of the next poll time the last poll time variable, determines the value of the next poll
variable. Finally, the last poll time variable is set to the current time variable. Finally, the last poll time variable is set to the
seconds counter. current seconds counter.
14. Simple Network Time Protocol (SNTP) 14. Simple Network Time Protocol (SNTP)
Primary servers and clients complying with a subset of NTP, called Primary servers and clients complying with a subset of NTP, called
the Simple Network Time Protocol (SNTPv4) [RFC4330], do not need to the Simple Network Time Protocol (SNTPv4) [RFC4330], do not need to
implement the mitigation algorithms described in Section 9 and implement the mitigation algorithms described in Section 9 and
following sections. SNTP is intended for primary servers equipped following sections. SNTP is intended for primary servers equipped
with a single reference clock, as well as for clients with a single with a single reference clock, as well as for clients with a single
upstream server and no dependent clients. The fully developed NTPv4 upstream server and no dependent clients. The fully developed NTPv4
implementation is intended for secondary servers with multiple implementation is intended for secondary servers with multiple
skipping to change at page 56, line 39 skipping to change at page 55, line 38
| x.reftime <-- s.reftime | | x.reftime <-- s.reftime |
| x.org <-- r.xmt | | x.org <-- r.xmt |
| x.rec <-- r.dst | | x.rec <-- r.dst |
| x.xmt <-- clock | | x.xmt <-- clock |
| x.keyid <-- r.keyid | | x.keyid <-- r.keyid |
| x.digest <-- md5 digest | | x.digest <-- md5 digest |
+-----------------------------------+ +-----------------------------------+
Figure 31: fast_xmit Packet Header Figure 31: fast_xmit Packet Header
A SNTP client implementing the on-wire protocol has a single server An SNTP client implementing the on-wire protocol has a single server
and no dependent clients. It can operate with any subset of the NTP and no dependent clients. It can operate with any subset of the NTP
on-wire protocol, the simplest approach using only the transmit on-wire protocol, the simplest approach using only the transmit
timestamp of the server packet and ignoring all other fields. timestamp of the server packet and ignoring all other fields.
However, the additional complexity to implement the full on-wire However, the additional complexity to implement the full on-wire
protocol is minimal so that a full implementation is encouraged. protocol is minimal so that a full implementation is encouraged.
15. Security Considerations 15. Security Considerations
NTP security requirements are even more stringent than most other NTP security requirements are even more stringent than most other
distributed services. First, the operation of the authentication distributed services. First, the operation of the authentication
mechanism and the time synchronization mechanism are inextricably mechanism and the time synchronization mechanism are inextricably
intertwined. Reliable time synchronization requires cryptographic intertwined. Reliable time synchronization requires cryptographic
keys which are valid only over a designated time interval; but, time keys that are valid only over a designated time interval; but, time
intervals can be enforced only when participating servers and clients intervals can be enforced only when participating servers and clients
are reliably synchronized to UTC. In addition, the NTP subnet is are reliably synchronized to UTC. In addition, the NTP subnet is
hierarchical by nature, so time and trust flow from the primary hierarchical by nature, so time and trust flow from the primary
servers at the root through secondary servers to the clients at the servers at the root through secondary servers to the clients at the
leaves. leaves.
An NTP client can claim to have authentic time to dependent An NTP client can claim to have authentic time to dependent
applications only if all servers on the path to the primary servers applications only if all servers on the path to the primary servers
are authenticated. In NTP each server authenticates the next lower are authenticated. In NTP each server authenticates the next lower
stratum servers and authenticates by induction the lowest stratum stratum servers and authenticates by induction the lowest stratum
(primary) servers. It is important to note that authentication in (primary) servers. It is important to note that authentication in
the context of NTP does not necessarily imply the time is correct. A the context of NTP does not necessarily imply the time is correct.
NTP client mobilizes a number of concurrent associations with An NTP client mobilizes a number of concurrent associations with
different servers and uses a crafted agreement algorithm to pluck different servers and uses a crafted agreement algorithm to pluck
truechimers from the population possibly including falsetickers. truechimers from the population possibly including falsetickers.
The NTP specification assumes the goal of the intruder is to inject The NTP specification assumes that the goal of the intruder is to
false time values, disrupt the protocol or clog the network, servers inject false time values, disrupt the protocol, or clog the network,
or clients with spurious packets that exhaust resources and deny servers, or clients with spurious packets that exhaust resources and
service to legitimate applications. There are a number of defense deny service to legitimate applications. There are a number of
mechanisms already built in the NTP architecture, protocol and defense mechanisms already built in the NTP architecture, protocol,
algorithms. The on-wire timestamp exchange scheme is inherently and algorithms. The on-wire timestamp exchange scheme is inherently
resistant to spoofing, packet loss and replay attacks. The resistant to spoofing, packet-loss, and replay attacks. The
engineered clock filter, selection and clustering algorithms are engineered clock filter, selection and clustering algorithms are
designed to defend against evil cliques of Byzantine traitors. While designed to defend against evil cliques of Byzantine traitors. While
not necessarily designed to defeat determined intruders, these not necessarily designed to defeat determined intruders, these
algorithms and accompanying sanity checks have functioned well over algorithms and accompanying sanity checks have functioned well over
the years to deflect improperly operating but presumably friendly the years to deflect improperly operating but presumably friendly
scenarios. However, these mechanisms do not securely identify and scenarios. However, these mechanisms do not securely identify and
authenticate servers to clients. Without specific further authenticate servers to clients. Without specific further
protection, an intruder can inject any or all of the following protection, an intruder can inject any or all of the following
attacks: attacks:
1. An intruder can intercept and archive packets forever, as well as 1. An intruder can intercept and archive packets forever, as well as
all the public values ever generated and transmitted over the all the public values ever generated and transmitted over the
net. net.
2. An intruder can generate packets faster than the server, network 2. An intruder can generate packets faster than the server, network
or client can process them, especially if they require expensive or client can process them, especially if they require expensive
cryptographic computations. cryptographic computations.
3. In a wiretap attack the intruder can intercept, modify and replay 3. In a wiretap attack, the intruder can intercept, modify, and
a packet. However, it cannot permanently prevent onward replay a packet. However, it cannot permanently prevent onward
transmission of the original packet; that is, it cannot break the transmission of the original packet; that is, it cannot break the
wire, only tell lies and congest it. Generally, the modified wire, only tell lies and congest it. Generally, the modified
packet cannot arrive at the victim before the original packet, packet cannot arrive at the victim before the original packet,
nor does it have the server private keys or identity parameters. nor does it have the server private keys or identity parameters.
4. In a middleman or masquerade attack the intruder is positioned 4. In a middleman or masquerade attack, the intruder is positioned
between the server and client, so it can intercept, modify and between the server and client, so it can intercept, modify and
replay a packet and prevent onward transmission of the original replay a packet and prevent onward transmission of the original
packet. However, the middleman does not have the server private packet. However, the middleman does not have the server private
keys. keys.
The NTP security model assumes the following possible limitations: The NTP security model assumes the following possible limitations:
1. The running times for public key algorithms are relatively long 1. The running times for public key algorithms are relatively long
and highly variable. In general, the performance of the time and highly variable. In general, the performance of the time
synchronization function is badly degraded if these algorithms synchronization function is badly degraded if these algorithms
must be used for every NTP packet. must be used for every NTP packet.
2. In some modes of operation it is not feasible for a server to 2. In some modes of operation, it is not feasible for a server to
retain state variables for every client. It is however feasible retain state variables for every client. It is however feasible
to regenerated them for a client upon arrival of a packet from to regenerated them for a client upon arrival of a packet from
that client. that client.
3. The lifetime of cryptographic values must be enforced, which 3. The lifetime of cryptographic values must be enforced, which
requires a reliable system clock. However, the sources that requires a reliable system clock. However, the sources that
synchronize the system clock must be trusted. This circular synchronize the system clock must be trusted. This circular
interdependence of the timekeeping and authentication functions interdependence of the timekeeping and authentication functions
requires special handling. requires special handling.
4. Client security functions must involve only public values 4. Client security functions must involve only public values
transmitted over the net. Private values must never be disclosed transmitted over the net. Private values must never be disclosed
beyond the machine on which they were created, except in the case beyond the machine on which they were created, except in the case
of a special trusted agent (TA) assigned for this purpose. of a special trusted agent (TA) assigned for this purpose.
Unlike the Secure Shell (SSH) security model, where the client must Unlike the Secure Shell (SSH) security model, where the client must
be securely authenticated to the server, in NTP the server must be be securely authenticated to the server, in NTP the server must be
securely authenticated to the client. In SSH each different securely authenticated to the client. In SSH, each different
interface address can be bound to a different name, as returned by a interface address can be bound to a different name, as returned by a
reverse-DNS query. In this design separate public/private key pairs reverse-DNS query. In this design, separate public/private key pairs
may be required for each interface address with a distinct name. A may be required for each interface address with a distinct name. A
perceived advantage of this design is that the security compartment perceived advantage of this design is that the security compartment
can be different for each interface. This allows a firewall, for can be different for each interface. This allows a firewall, for
instance, to require some interfaces to authenticate the client and instance, to require some interfaces to authenticate the client and
others not. others not.
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. Such disruption can be broadcast servers elsewhere in the Internet. Such disruption can be
minimized by several approaches. Filtering can be employed to limit minimized by several approaches. Filtering can be employed to limit
the access of NTP clients to known or trusted NTP broadcast servers. the access of NTP clients to known or trusted NTP broadcast servers.
Such filtering will prevent malicious traffic from reaching the NTP Such filtering will prevent malicious traffic from reaching the NTP
clients. Cryptographic authentication at the client will only allow clients. Cryptographic authentication at the client will only allow
timing information from properly signed NTP messages to be utilized timing information from properly signed NTP messages to be utilized
in synchronzing its clock. Higher levels of authentication may be in synchronizing its clock. Higher levels of authentication may be
gained by the use of the Autokey mechanism[I-D.ietf-ntp-autokey]. gained by the use of the Autokey mechanism [RFC5906].
Section 8 describes a potential security concern with the replay of Section 8 describes a potential security concern with the replay of
client requests. Following the recommendations in that section client requests. Following the recommendations in that section
provides protection against such attacks. provides protection against such attacks.
It should be noted that this specification is describing an existing It should be noted that this specification is describing an existing
implementation. While the security shortfalls of the MD5 algorithm implementation. While the security shortfalls of the MD5 algorithm
are well-known, its use in the NTP specification is consistent with are well-known, its use in the NTP specification is consistent with
widescale deployment in the Internet community. widescale deployment in the Internet community.
16. IANA Considerations 16. 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 has established and will maintain a registry for Extension Field
Field Types associated with this protocol, populating this registry Types associated with this protocol, populating this registry with no
with no initial entries. As future needs arise, new Extension Field initial entries. As future needs arise, new Extension Field Types
Types may be defined. Following the policies outlined in [RFC5226], may be defined. Following the policies outlined in [RFC5226], new
new values are to be defined by IETF Review. values are to be defined by IETF Review.
The IANA is requested to create a new registry for NTP Reference The IANA has created a new registry for NTP Reference Identifier
Identifier codes. This should include the current codes defined in codes. This includes the current codes defined in Section 7.3, and
Section 7.3, and may be extended on a First-Come-First-Serve (FCFS) may be extended on a First-Come-First-Serve (FCFS) basis. The format
basis. The format of the registry is: of the registry is:
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
| ID | Clock Source | | ID | Clock Source |
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
| GOES | Geosynchronous Orbit Environment Satellite | | GOES | Geosynchronous Orbit Environment Satellite |
| GPS | Global Position System | | GPS | Global Position System |
| ... | ... | | ... | ... |
+------+----------------------------------------------------------+ +------+----------------------------------------------------------+
Figure 32: Reference Identifier Codes Figure 32: Reference Identifier Codes
The IANA is requested to create a new registry for NTP Kiss-o'-Death The IANA has created a new registry for NTP Kiss-o'-Death codes.
codes. This should include the current codes defined in Section 7.4, This includes the current codes defined in Section 7.4, and may be
and may be extended on a FCFS basis. The format of the registry is: extended on a FCFS basis. The format of the registry is:
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
| 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. |
| ... | ... | | ... | ... |
+------+------------------------------------------------------------+ +------+------------------------------------------------------------+
Figure 33: Kiss Codes Figure 33: Kiss Codes
For both Reference Identifiers and Kiss-o'-Death codes, IANA is For both Reference Identifiers and Kiss-o'-Death codes, IANA is
requested to never assign a code beginning with the character "X", as requested to never assign a code beginning with the character "X", as
this is reserved for experimentation and development. this is reserved for experimentation and development.
17. Acknowledgements 17. Acknowledgements
The editors would like to thank Karen O'Donoghue, Brian Haberman, The editors would like to thank Karen O'Donoghue, Brian Haberman,
Greg Dowd, Mark Elliot, Harlan Stenn, Yaakov Stein, Stewart Bryant, Greg Dowd, Mark Elliot, Harlan Stenn, Yaakov Stein, Stewart Bryant,
and Danny Mayer for technical reviews and specific text contributions and Danny Mayer for technical reviews and specific text contributions
to this document. to this document.
18. References 18. References
18.1. Normative References 18.1. Normative References
[RFC0768] Postel, J., "User Datagram Protocol", STD 6, RFC 768, [RFC0768] Postel, J., "User Datagram Protocol", STD 6, RFC 768,
August 1980. August 1980.
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981. September 1981.
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, [RFC0793] Postel, J., "Transmission Control Protocol", STD 7,
RFC 793, September 1981. RFC 793, September 1981.
[RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm",
April 1992. RFC 1321, April 1992.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
18.2. Informative References 18.2. Informative References
[CGPM] Bureau International des Poids et Mesures, "Comptes Rendus [CGPM] Bureau International des Poids et Mesures, "Comptes
de la 15e CGPM", 1976. Rendus de la 15e CGPM", 1976.
[I-D.ietf-ntp-autokey] [ITU-R_TF.460] International Telecommunications Union, "ITU-R TF.460
Haberman, B. and D. Mills, "Network Time Protocol Version Standard-frequency and time-signal emissions",
4 Autokey Specification", draft-ietf-ntp-autokey-06 (work February 2002.
in progress), July 2009.
[ITU-R_TF.460] [RFC1305] Mills, D., "Network Time Protocol (Version 3)
International Telecommunications Union, "ITU-R TF.460 Specification, Implementation and Analysis",
Standard-frequency and time-signal emissions", RFC 1305, March 1992.
February 2002.
[RFC1305] Mills, D., "Network Time Protocol (Version 3) [RFC1345] Simonsen, K., "Character Mnemonics and Character
Specification, Implementation", RFC 1305, March 1992. Sets", RFC 1345, June 1992.
[RFC1345] Simonsen, K., "Character Mnemonics and Character Sets", [RFC4330] Mills, D., "Simple Network Time Protocol (SNTP)
RFC 1345, June 1992. Version 4 for IPv4, IPv6 and OSI", RFC 4330,
January 2006.
[RFC4330] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing
for IPv4, IPv6 and OSI", RFC 4330, January 2006. an IANA Considerations Section in RFCs", BCP 26,
RFC 5226, May 2008.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an [RFC5906] Haberman, B., Ed. and D. Mills, "Network Time
IANA Considerations Section in RFCs", BCP 26, RFC 5226, Protocol Version 4: Autokey Specification", RFC 5906,
May 2008. June 2010.
[ref6] Marzullo and S. Owicki, "Maintaining the time in a [ref6] Marzullo and S. Owicki, "Maintaining the time in a
distributed system.", ACM Operating Systems Review 19 , distributed system", ACM Operating Systems Review 19,
July 1985. July 1985.
[ref7] Mills, D.L., "Computer Network Time Synchronization - the [ref7] Mills, D.L., "Computer Network Time Synchronization -
Network Time Protocol. CRC Press, 304pp.", 2006. the Network Time Protocol", CRC Press, 304 pp, 2006.
[ref9] Mills, D.L., Electrical and Computer Engineering Technical [ref9] Mills, D.L., Electrical and Computer Engineering
Report 06-6-1, NDSS, June 2006., "Network Time Protocol Technical Report 06-6-1, NDSS, June 2006, "Network
Version 4 Reference and Implementation Guide.", 2006. Time Protocol Version 4 Reference and Implementation
Guide", 2006.
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 fragments which illustrate the protocol operations without and code fragments that 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. ordinary sense.
Most of the features of the reference implementation are included Most of the features of the reference implementation are included
here, with the following exceptions: There are no provisions for here, with the following exceptions: there are no provisions for
reference clocks or public key (Autokey) cryptography. There is no reference clocks or public key (Autokey) cryptography. There is no
huff-n'-puff filter, anti-clockhop hysteresis or monitoring huff-n'-puff filter, anti-clockhop hysteresis, or monitoring
provisions. Many of the values that can be tinkered in the reference provisions. Many of the values that can be tinkered in the reference
implementation are assumed constants here. There are only minimal implementation are assumed constants here. There are only minimal
provisions for the kiss-o'death packet and no responding code. provisions for the kiss-o'-death packet and no responding code.
The program is not intended to be fast or compact, just to The program is not intended to be fast or compact, just to
demonstrate the algorithms with sufficient fidelity to understand how demonstrate the algorithms with sufficient fidelity to understand how
they work. The code skeleton consists of eight segments, a header they work. The code skeleton consists of eight segments, a header
segment included by each of the other segments, plus a code segment segment included by each of the other segments, plus a code segment
for the main program, kernel I/O and system clock interfaces, and for the main program, kernel I/O and system clock interfaces, and
peer, system, clock_adjust and poll processes. These are presented peer, system, clock_adjust, and poll processes. These are presented
in order below along with definitions and variables specific to each in order below along with definitions and variables specific to each
process. process.
A.1. Global Definitions A.1. Global Definitions
A.1.1. Definitions, Constants, Parameters A.1.1. Definitions, Constants, Parameters
#include <math.h> /* 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 */
#include <string.h> /* for memset() */ #include <string.h> /* for memset() */
/* /*
* 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 represented 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 long tstamp; /* NTP timestamp format */ typedef unsigned long long tstamp; /* NTP timestamp format */
typedef unsigned int tdist; /* NTP short format */ typedef unsigned int tdist; /* NTP short format */
typedef unsigned long ipaddr; /* IPv4 or IPv6 address */ typedef unsigned long ipaddr; /* IPv4 or IPv6 address */
typedef unsigned long digest; /* md5 digest */ typedef unsigned long digest; /* md5 digest */
typedef signed char s_char; /* precision and poll interval (log2) */ typedef signed char s_char; /* precision and poll interval (log2) */
/* /*
skipping to change at page 63, line 31 skipping to change at page 62, line 45
/* /*
* Arithmetic conversions * Arithmetic conversions
*/ */
#define LOG2D(a) ((a) < 0 ? 1. / (1L << -(a)) : \ #define LOG2D(a) ((a) < 0 ? 1. / (1L << -(a)) : \
1L << (a)) /* poll, etc. */ 1L << (a)) /* poll, etc. */
#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 * that can be tinkered by configuration or computed on-the-fly. For
* instance, the reference implementation computes PRECISION on-fly and * instance, the reference implementation computes PRECISION on-the-fly
* provides performance tuning for the defines marked with % below. * and provides performance tuning for the defines marked with % below.
*/ */
#define VERSION 4 /* version number */ #define VERSION 4 /* version 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 0x3 /* leap unsync */ #define NOSYNC 0x3 /* leap unsync */
#define MAXSTRAT 16 /* maximum stratum (infinity metric) */ #define MAXSTRAT 16 /* maximum stratum (infinity metric) */
#define MINPOLL 6 /* % minimum poll interval (64 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 MINCLOCK 3 /* minimum manycast survivors */
#define MAXCLOCK 10 /* maximum manycast candidates */ #define MAXCLOCK 10 /* maximum manycast candidates */
#define TTLMAX 8 /* max ttl manycast */ #define TTLMAX 8 /* max ttl manycast */
#define BEACON 15 /* max interval between beacons */ #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 */
skipping to change at page 65, line 10 skipping to change at page 64, line 23
* Association state codes * Association state codes
*/ */
#define X_INIT 0 /* initialization */ #define X_INIT 0 /* initialization */
#define X_STALE 1 /* timeout */ #define X_STALE 1 /* timeout */
#define X_STEP 2 /* time step */ #define X_STEP 2 /* time step */
#define X_ERROR 3 /* authentication error */ #define X_ERROR 3 /* authentication error */
#define X_CRYPTO 4 /* crypto-NAK received */ #define X_CRYPTO 4 /* crypto-NAK received */
#define X_NKEY 5 /* untrusted key */ #define X_NKEY 5 /* untrusted key */
/* /*
* Protocol mode definitionss * Protocol mode definitions
*/ */
#define M_RSVD 0 /* reserved */ #define M_RSVD 0 /* reserved */
#define M_SACT 1 /* symmetric active */ #define M_SACT 1 /* symmetric active */
#define M_PASV 2 /* symmetric passive */ #define M_PASV 2 /* symmetric passive */
#define M_CLNT 3 /* client */ #define M_CLNT 3 /* client */
#define M_SERV 4 /* server */ #define M_SERV 4 /* server */
#define M_BCST 5 /* broadcast server */ #define M_BCST 5 /* broadcast server */
#define M_BCLN 6 /* broadcast client */ #define M_BCLN 6 /* broadcast client */
/* /*
skipping to change at page 65, line 31 skipping to change at page 65, line 4
* Clock state definitions * Clock state definitions
*/ */
#define NSET 0 /* clock never set */ #define NSET 0 /* clock never set */
#define FSET 1 /* frequency set from file */ #define FSET 1 /* frequency set from file */
#define SPIK 2 /* spike detected */ #define SPIK 2 /* spike detected */
#define FREQ 3 /* frequency mode */ #define FREQ 3 /* frequency mode */
#define SYNC 4 /* clock synchronized */ #define SYNC 4 /* clock synchronized */
#define min(a, b) ((a) < (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) < (b) ? (b) : (a)) #define max(a, b) ((a) < (b) ? (b) : (a))
A.1.2. Packet Data Structures A.1.2. Packet Data Structures
/* /*
* The receive and transmit packets may contain an optional message * The receive and transmit packets may contain an optional message
* authentication code (MAC) consisting of a key identifier (keyid) and * authentication code (MAC) consisting of a key identifier (keyid) and
* message digest (mac). NTPv4 supports optional extension fields which * message digest (mac in the receive structure and dgst in the transmit
* are inserted after the the header and before the MAC, but these are * structure). NTPv4 supports optional extension fields that
* not described here. * are inserted after the header and before the MAC, but these are
* * not described here.
* Receive packet *
* * Receive packet
* Note the dst timestamp is not part of the packet itself. It is *
* captured upon arrival and returned in the receive buffer along with * Note the dst timestamp is not part of the packet itself. It is
* the buffer length and data. Note that some of the char fields are * captured upon arrival and returned in the receive buffer along with
* packed in the actual header, but the details are omitted here. * the buffer length and data. Note that some of the char fields are
*/ * packed in the actual header, but the details are omitted here.
struct r { */
ipaddr srcaddr; /* source (remote) address */ struct r {
ipaddr dstaddr; /* destination (local) address */ ipaddr srcaddr; /* source (remote) address */
char version; /* version number */ ipaddr dstaddr; /* destination (local) address */
char leap; /* leap indicator */ char version; /* version number */
char mode; /* mode */ char leap; /* leap indicator */
char stratum; /* stratum */ char mode; /* mode */
char poll; /* poll interval */ char stratum; /* stratum */
s_char precision; /* precision */ char poll; /* poll interval */
tdist rootdelay; /* root delay */ s_char precision; /* precision */
tdist rootdisp; /* root dispersion */ tdist rootdelay; /* root delay */
char refid; /* reference ID */ tdist rootdisp; /* root dispersion */
tstamp reftime; /* reference time */ char refid; /* reference ID */
tstamp org; /* origin timestamp */ tstamp reftime; /* reference time */
tstamp rec; /* receive timestamp */ tstamp org; /* origin timestamp */
tstamp xmt; /* transmit timestamp */ tstamp rec; /* receive timestamp */
int keyid; /* key ID */ tstamp xmt; /* transmit timestamp */
digest mac; /* message digest */ int keyid; /* key ID */
tstamp dst; /* destination timestamp */ digest mac; /* message digest */
} r; tstamp dst; /* destination timestamp */
} 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 */
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 dgst; /* message digest */ digest dgst; /* 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 {
tstamp t; /* update time */ tstamp t; /* update time */
double offset; /* clock ofset */ double offset; /* clock ofset */
double delay; /* roundtrip delay */ double delay; /* roundtrip delay */
double disp; /* dispersion */ double disp; /* dispersion */
} f; } f;
/* /*
* Association structure. This is shared between the peer process and * Association structure. This is shared between the peer process
* poll process. * and poll process.
*/ */
struct p { struct p {
/* /*
* Variables set by configuration * Variables set by configuration
*/ */
ipaddr srcaddr; /* source (remote) address */ ipaddr srcaddr; /* source (remote) address */
ipaddr dstaddr; /* destination (local) address */ ipaddr dstaddr; /* destination (local) address */
char version; /* version number */ char version; /* version number */
char hmode; /* host mode */ char hmode; /* host mode */
skipping to change at page 69, line 8 skipping to change at page 68, line 8
int ttl; /* ttl (manycast) */ 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 outdate; /* last poll time */ int outdate; /* last poll time */
int nextdate; /* 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 */
double edge; /* correctness interval edge */ double edge; /* correctness interval edge */
} m; } m;
/* /*
* Survivor list. This is used by the clustering algorithm. * Survivor list. This is used by the clustering algorithm.
*/ */
struct v { struct v {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
double metric; /* sort metric */ double metric; /* sort metric */
} v; } v;
/* /*
* System structure * System structure
*/ */
struct s { struct s {
skipping to change at page 72, line 27 skipping to change at page 71, line 31
if (/* frequency file */ 0) { if (/* frequency file */ 0) {
c.freq = /* freq */ 0; c.freq = /* freq */ 0;
rstclock(FSET, 0, 0); rstclock(FSET, 0, 0);
} else { } else {
rstclock(NSET, 0, 0); rstclock(NSET, 0, 0);
} }
c.jitter = LOG2D(s.precision); c.jitter = LOG2D(s.precision);
/* /*
* Read the configuration file and mobilize persistent * Read the configuration file and mobilize persistent
* associations with specified addresses, version, mode, key ID * associations with specified addresses, version, mode, key ID,
* and flags. * and flags.
*/ */
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 = recv_packet();
r->dst = get_time(); r->dst = get_time();
receive(r); receive(r);
} }
return(0); return(0);
} }
skipping to change at page 74, line 12 skipping to change at page 73, line 16
/* /*
* 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 fields * The key is prepended to the packet header and extension fields
* and the result hashed by the MD5 algorithm as described in * and the result hashed by the MD5 algorithm as described in
* RFC-1321. Return a MAC consisting of the 32-bit key ID * RFC 1321. Return a MAC consisting of the 32-bit key ID
* concatenated with the 128-bit digest. * concatenated with the 128-bit digest.
*/ */
return (/* MD5 digest */ 0); return (/* MD5 digest */ 0);
} }
A.3. Kernel Input/Output Interface A.3. Kernel Input/Output Interface
/* /*
* Kernel interface to transmit and receive packets. Details are * Kernel interface to transmit and receive packets. Details are
* deliberately vague and depend on the operating system. * deliberately vague and depend on the operating system.
* *
* recv_packet - receive packet from network * recv_packet - receive packet from network
*/ */
struct r /* receive packet pointer*/ struct r /* receive packet pointer*/
*recv_packet() { *recv_packet() {
return (/* receive packet r */ 0); return (/* receive packet r */ 0);
} }
/* /*
skipping to change at page 75, line 4 skipping to change at page 74, line 10
) )
{ {
/* send packet x */ /* send packet x */
} }
A.4. Kernel System Clock Interface A.4. Kernel System Clock Interface
/* /*
* System clock utility functions * 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
* The get_time() routine returns the time in NTP long format. The Unix * double. The get_time() routine returns the time in NTP long format.
* routines expect arguments as a structure of two signed 32-bit words * The Unix routines expect arguments as a structure of two signed
* in seconds and microseconds (timeval) or nanoseconds (timespec). The * 32-bit words in seconds and microseconds (timeval) or nanoseconds
* step_time() and adjust_time() routines expect signed arguments in * (timespec). The step_time() and adjust_time() routines expect signed
* floating double. The simplified code shown here is for illustration * arguments in floating double. The simplified code shown here is for
* only and has not been verified. * illustration only and has not been verified.
*/ */
#define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */ #define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */
/* /*
* get_time - read system time and convert to NTP format * get_time - read system time and convert to NTP format
*/ */
tstamp tstamp
get_time() get_time()
{ {
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 (U2LFP(unix_time));
} }
/* /*
* step_time() - step system time to given offset valuet * step_time() - step system time to given offset value
*/ */
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.
*/ */
gettimeofday(&unix_time, NULL); gettimeofday(&unix_time, NULL);
ntp_time = D2LFP(offset) + U2LFP(unix_time); ntp_time = D2LFP(offset) + U2LFP(unix_time);
unix_time.tv_sec = ntp_time >> 32; unix_time.tv_sec = ntp_time >> 32;
unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) << unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) <<
32) / FRAC * 1e6); 32) / FRAC * 1e6);
settimeofday(&unix_time, NULL); settimeofday(&unix_time, NULL);
} }
skipping to change at page 76, line 31 skipping to change at page 76, line 4
/* /*
* 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 >> 32; unix_time.tv_sec = ntp_time >> 32;
unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) << unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) <<
32) / FRAC * 1e6); 32) / FRAC * 1e6);
adjtime(&unix_time, NULL); adjtime(&unix_time, NULL);
} }
A.5. Peer Process A.5. Peer Process
/* /*
* 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
* receiver that a prior request could not be properly authenticated, * the receiver that a prior request could not be properly
* but the NTP header fields are correct. * authenticated, but the NTP header fields are correct.
* *
* A kiss-o'-death packet is an NTP header with leap 0x3 (NOSYNC) and * A kiss-o'-death packet is an NTP header with leap 0x3 (NOSYNC) and
* stratum 16 (MAXSTRAT. It tells the receiver that something drastic * stratum 16 (MAXSTRAT). It tells the receiver that something
* has happened, as revealed by the kiss code in the refid field. The * drastic has happened, as revealed by the kiss code in the refid
* NTP header fields may or may not be correct. * field. The NTP header fields may or may not be correct.
*/ */
/* /*
* Peer process parameters and constants * 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
*/
#define ERR -1 /* error */
#define DSCRD 0 /* discard packet */
#define PROC 1 /* process packet */
#define BCST 2 /* broadcast packet */
#define FXMIT 3 /* client packet */
#define MANY 4 /* manycast packet */
#define NEWPS 5 /* new symmetric passive client */
#define NEWBC 6 /* new broadcast client */
/* /*
* Dispatch matrix * Dispatch codes
* active passv client server bcast */ */
int table[7][5] = { #define ERR -1 /* error */
/* nopeer */ { NEWPS, DSCRD, FXMIT, MANY, NEWBC }, #define DSCRD 0 /* discard packet */
/* active */ { PROC, PROC, DSCRD, DSCRD, DSCRD }, #define PROC 1 /* process packet */
/* passv */ { PROC, ERR, DSCRD, DSCRD, DSCRD }, #define BCST 2 /* broadcast packet */
/* client */ { DSCRD, DSCRD, DSCRD, PROC, DSCRD }, #define FXMIT 3 /* client packet */
/* server */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, #define MANY 4 /* manycast packet */
/* bcast */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, #define NEWPS 5 /* new symmetric passive client */
/* bclient */ { DSCRD, DSCRD, DSCRD, DSCRD, PROC} #define NEWBC 6 /* new broadcast client */
};
/* /*
* Miscellaneous macroni * Dispatch matrix
* * active passv client server bcast */
* This macro defines the authentication state. If x is 0, int table[7][5] = {
* authentication is optional, otherwise it is required. /* nopeer */ { NEWPS, DSCRD, FXMIT, MANY, NEWBC },
*/ /* active */ { PROC, PROC, DSCRD, DSCRD, DSCRD },
#define AUTH(x, y) ((x) ? (y) == A_OK : (y) == A_OK || \ /* passv */ { PROC, ERR, DSCRD, DSCRD, DSCRD },
(y) == A_NONE) /* client */ { DSCRD, DSCRD, DSCRD, PROC, DSCRD },
/* server */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD },
/* bcast */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD },
/* bclient */ { DSCRD, DSCRD, DSCRD, DSCRD, PROC}
};
/*
* Miscellaneous macroni
*
* This macro defines the authentication state. If x is 0,
* authentication is optional; otherwise, it is required.
*/
#define AUTH(x, y) ((x) ? (y) == A_OK : (y) == A_OK || \
(y) == A_NONE)
/* /*
* These are used by the clear() routine * These are used by the clear() routine
*/ */
#define BEGIN_CLEAR(p) ((char *)&((p)->begin_clear)) #define BEGIN_CLEAR(p) ((char *)&((p)->begin_clear))
#define END_CLEAR(p) ((char *)&((p)->end_clear)) #define END_CLEAR(p) ((char *)&((p)->end_clear))
#define LEN_CLEAR (END_CLEAR((struct p *)0) - \ #define LEN_CLEAR (END_CLEAR((struct p *)0) - \
BEGIN_CLEAR((struct p *)0)) BEGIN_CLEAR((struct p *)0))
A.5.1. receive() A.5.1. receive()
/* /*
* receive() - receive packet and decode modes * receive() - receive packet and decode modes
*/ */
void void
receive( receive(
struct r *r /* receive packet pointer */ struct r *r /* receive packet pointer */
) )
{ {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
int auth; /* authentication code */ int auth; /* authentication code */
int has_mac; /* size of MAC */ int has_mac; /* size of MAC */
int synch; /* synchronized switch */ int synch; /* synchronized switch */
/* /*
* Check access control lists. The intent here is to implement a * Check access control lists. The intent here is to implement
* whitelist of those IP addresses specifically accepted and/or * a whitelist of those IP addresses specifically accepted
* a blacklist of those IP addresses specifically rejected. * and/or a blacklist of those IP addresses specifically
* There could be different lists for authenticated clients and * rejected. There could be different lists for authenticated
* unauthenticated clients. * clients and unauthenticated clients.
*/ */
if (!access(r)) if (!access(r))
return; /* access denied */ return; /* access denied */
/* /*
* The version must not be in the future. Format checks include * The version must not be in the future. Format checks include
* packet length, MAC length and extension field lengths, if * packet length, MAC length and extension field lengths, if
* present. * present.
*/ */
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 that 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; has_mac = /* length of MAC field */ 0;
if (has_mac == 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->hmode is assumed NULL. * association to match, the value of p->hmode is assumed NULL.
*/ */
p = find_assoc(r); p = find_assoc(r);
switch(table[(unsigned int)(p->hmode)][(unsigned int)(r->mode)]) { switch(table[(unsigned int)(p->hmode)][(unsigned int)(r->mode)])
{
/* /*
* Client packet and no association. Send server reply without * Client packet and no association. Send server reply without
* saving state. * saving state.
*/ */
case FXMIT: case FXMIT:
/* /*
* If unicast destination address, send server packet. * If unicast destination address, send server packet.
* If authentication fails, send a crypto-NAK packet. * If authentication fails, send a crypto-NAK packet.
*/ */
/* not multicast dstaddr */ /* not multicast dstaddr */
if (0) { if (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 */
} }
/* /*
* This must be manycast. Do not respond if we are not * This must be manycast. Do not respond if we are not
* synchronized or if our stratum is above the * synchronized or if our stratum is above the
* manycaster. * manycaster.
*/ */
if (s.leap == NOSYNC || s.stratum > r->stratum) if (s.leap == NOSYNC || s.stratum > r->stratum)
return; return;
/* /*
* Respond only if authentication is ok. Note that the * Respond only if authentication is OK. Note that the
* unicast address is used, not the multicast. * unicast address is used, not the multicast.
*/ */
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);
return; return;
/* /*
* New manycast client ephemeral association. It is mobilized in * New manycast client ephemeral association. It is mobilized
* the same version as in the packet. If authentication fails, * in the same version as in the packet. If authentication
* ignore the packet. Verify the server packet by comparing the * fails, ignore the packet. Verify the server packet by
* r->org timestamp in the packet with the p->xmt timestamp in * comparing the r->org timestamp in the packet with the p->xmt
* the multicast client association. If they match, the server * timestamp in the multicast client association. If they
* packet is authentic. Details omitted. * match, the server packet is authentic. Details omitted.
*/ */
case MANY: case MANY:
if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth)) if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth))
return; /* authentication error */ return; /* authentication error */
p = mobilize(r->srcaddr, r->dstaddr, r->version, M_CLNT, p = mobilize(r->srcaddr, r->dstaddr, r->version, M_CLNT,
r->keyid, P_EPHEM); r->keyid, P_EPHEM);
break; break;
/* /*
* New symmetric passive association. It is mobilized in the same * New symmetric passive association. It is mobilized in the
* version as in the packet. If authentication fails, send a * same version as in the packet. If authentication fails,
* crypto-NAK packet. If restrict no-moblize, send a symmetric * send a crypto-NAK packet. If restrict no-moblize, send a
* active packet instead. * symmetric active packet instead.
*/ */
case NEWPS: case NEWPS:
if (!AUTH(p->flags & P_NOTRUST, auth)) { if (!AUTH(p->flags & P_NOTRUST, auth)) {
if (auth == A_ERROR) if (auth == A_ERROR)
fast_xmit(r, M_SACT, A_CRYPTO); fast_xmit(r, M_SACT, A_CRYPTO);
return; /* crypto-NAK packet sent */ return; /* crypto-NAK packet sent */
} }
if (!AUTH(p->flags & P_NOPEER, auth)) { if (!AUTH(p->flags & P_NOPEER, auth)) {
fast_xmit(r, M_SACT, auth); fast_xmit(r, M_SACT, auth);
return; /* M_SACT packet sent */ return; /* M_SACT packet sent */
} }
p = mobilize(r->srcaddr, r->dstaddr, r->version, M_PASV, p = mobilize(r->srcaddr, r->dstaddr, r->version, M_PASV,
r->keyid, P_EPHEM); r->keyid, P_EPHEM);
break; break;
/* /*
* New broadcast client association. It is mobilized in the same * New broadcast client association. It is mobilized in the
* version as in the packet. If authentication fails, ignore the * same version as in the packet. If authentication fails,
* packet. Note this code does not support the initial volley * ignore the packet. Note this code does not support the
* feature in the reference implementation. * initial volley feature in the reference implementation.
*/ */
case NEWBC: case NEWBC:
if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth)) if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth))
return; /* authentication error */ return; /* authentication error */
if (!(s.flags & S_BCSTENAB)) if (!(s.flags & S_BCSTENAB))
return; /* broadcast not enabled */ return; /* broadcast not enabled */
p = mobilize(r->srcaddr, r->dstaddr, r->version, M_BCLN, p = mobilize(r->srcaddr, r->dstaddr, r->version, M_BCLN,
r->keyid, P_EPHEM); r->keyid, P_EPHEM);
break; /* processing continues */ break; /* processing continues */
/* /*
* Process packet. Placeholdler only. * Process packet. Placeholdler only.
*/ */
case PROC: case PROC:
break; /* processing continues */ break; /* processing continues */
/* /*
* Invalid mode combination. We get here only in case of * Invalid mode combination. We get here only in case of
* ephemeral associations, so the correct action is simply to * ephemeral associations, so the correct action is simply to
* toss it. * toss it.
*/ */
case ERR: case ERR:
clear(p, X_ERROR); clear(p, X_ERROR);
return; /* invalid mode combination */ return; /* invalid mode combination */
/* /*
* No match; just discard the packet. * No match; just discard the packet.
*/ */
case DSCRD: case DSCRD:
return; /* orphan abandoned */ return; /* orphan abandoned */
} }
/* /*
* Next comes a rigorous schedule of timestamp checking. If the * Next comes a rigorous schedule of timestamp checking. If the
* transmit timestamp is zero, the server is horribly broken. * transmit timestamp is zero, the server is horribly broken.
*/ */
if (r->xmt == 0) if (r->xmt == 0)
return; /* invalid timestamp */ return; /* invalid timestamp */
/* /*
* If the transmit timestamp duplicates a previous one, the * If the transmit timestamp duplicates a previous one, the
* packet is a replay. * packet is a replay.
*/ */
if (r->xmt == p->xmt) if (r->xmt == p->xmt)
return; /* duplicate packet */ return; /* duplicate packet */
/* /*
* If this is a broadcast mode packet, skip further checking. * If this is a broadcast mode packet, skip further checking.
* If the origin timestamp is zero, the sender has not yet heard * If the origin timestamp is zero, the sender has not yet heard
* from us. Otherwise, if the origin timestamp does not match * from us. Otherwise, if the origin timestamp does not match
* the transmit timestamp, the packet is bogus. * the transmit timestamp, the packet is bogus.
*/ */
synch = TRUE; synch = TRUE;
if (r->mode != M_BCST) { if (r->mode != M_BCST) {
if (r->org == 0) if (r->org == 0)
synch = FALSE; /* unsynchronized */ synch = FALSE; /* unsynchronized */
else if (r->org != p->xmt) else if (r->org != p->xmt)
synch = FALSE; /* bogus packet */ synch = FALSE; /* bogus packet */
} }
/* /*
skipping to change at page 82, line 21 skipping to change at page 82, line 15
synch = TRUE; synch = TRUE;
if (r->mode != M_BCST) { if (r->mode != M_BCST) {
if (r->org == 0) if (r->org == 0)
synch = FALSE; /* unsynchronized */ synch = FALSE; /* unsynchronized */
else if (r->org != p->xmt) else if (r->org != p->xmt)
synch = FALSE; /* bogus packet */ synch = FALSE; /* bogus packet */
} }
/* /*
* Update the origin and destination timestamps. If * Update the origin and destination timestamps. If
* unsynchronized or bogus, abandon ship. * unsynchronized or bogus, abandon ship.
*/ */
p->org = r->xmt; p->org = r->xmt;
p->rec = r->dst; p->rec = r->dst;
if (!synch) if (!synch)
return; /* unsynch */ return; /* unsynch */
/* /*
* The timestamps are valid and the receive packet matches the * The timestamps are valid and the receive packet matches the
* last one sent. If the packet is a crypto-NAK, the server * last one sent. If the packet is a crypto-NAK, the server
* might have just changed keys. We demobilize the association * might have just changed keys. We demobilize the association
* and wait for better times. * and wait for better times.
*/ */
if (auth == A_CRYPTO) { if (auth == A_CRYPTO) {
clear(p, X_CRYPTO); clear(p, X_CRYPTO);
return; /* crypto-NAK */ return; /* crypto-NAK */
} }
/* /*
* If the association is authenticated, the key ID is nonzero * If the association is authenticated, the key ID is nonzero
* and received packets must be authenticated. This is designed * and received packets must be authenticated. This is designed
* to avoid a bait-and-switch attack, which was possible in past * to avoid a bait-and-switch attack, which was possible in past
* versions. * versions.
*/ */
if (!AUTH(p->keyid || (p->flags & P_NOTRUST), auth)) if (!AUTH(p->keyid || (p->flags & P_NOTRUST), auth))
return; /* bad auth */ return; /* bad auth */
/* /*
* Everything possible has been done to validate the timestamps * Everything possible has been done to validate the timestamps
* and prevent bad guys from disrupting the protocol or * and prevent bad guys from disrupting the protocol or
* injecting bogus data. Earn some revenue. * injecting bogus data. Earn some revenue.
*/ */
packet(p, r); packet(p, r);
} }
A.5.1.1. packet() A.5.1.1. packet()
/* /*
* packet() - process packet and compute offset, delay and * packet() - process packet and compute offset, delay, and
* dispersion. * dispersion.
*/ */
void void
packet( packet(
struct p *p, /* peer structure pointer */ struct p *p, /* peer structure pointer */
struct r *r /* receive packet pointer */ struct r *r /* receive packet pointer */
) )
{ {
double offset; /* sample offsset */ double offset; /* sample offsset */
double delay; /* sample delay */ double delay; /* sample delay */
double disp; /* sample dispersion */ double disp; /* sample dispersion */
/* /*
* By golly the packet is valid. Light up the remaining header * By golly the packet is valid. Light up the remaining header
* fields. Note that we map stratum 0 (unspecified) to MAXSTRAT * fields. Note that we map stratum 0 (unspecified) to MAXSTRAT
* to make stratum comparisons simpler and to provide a natural * to make stratum comparisons simpler and to provide a natural
* interface for radio clock drivers that operate for * interface for radio clock drivers that operate for
* convenience at stratum 0. * convenience at stratum 0.
*/ */
p->leap = r->leap; p->leap = r->leap;
if (r->stratum == 0) if (r->stratum == 0)
p->stratum = MAXSTRAT; p->stratum = MAXSTRAT;
else else
p->stratum = r->stratum; p->stratum = r->stratum;
p->pmode = r->mode; p->pmode = r->mode;
skipping to change at page 84, line 15 skipping to change at page 84, line 20
*/ */
if (r->rootdelay / 2 + r->rootdisp >= MAXDISP || p->reftime > if (r->rootdelay / 2 + r->rootdisp >= MAXDISP || p->reftime >
r->xmt) r->xmt)
return; /* invalid header values */ return; /* invalid header values */
poll_update(p, p->hpoll); poll_update(p, p->hpoll);
p->reach |= 1; p->reach |= 1;
/* /*
* Calculate offset, delay and dispersion, then pass to the * Calculate offset, delay and dispersion, then pass to the
* clock filter. Note carefully the implied processing. The * clock filter. Note carefully the implied processing. The
* first-order difference is done directly in 64-bit arithmetic, * first-order difference is done directly in 64-bit arithmetic,
* then the result is converted to floating double. All further * then the result is converted to floating double. All further
* processing is in floating double arithmetic with rounding * processing is in floating-double arithmetic with rounding
* done by the hardware. This is necessary in order to avoid * done by the hardware. This is necessary in order to avoid
* overflow and preseve precision. * overflow and preserve precision.
* *
* The delay calculation is a special case. In cases where the * The delay calculation is a special case. In cases where the
* server and client clocks are running at different rates and * server and client clocks are running at different rates and
* with very fast networks, the delay can appear negative. In * with very fast networks, the delay can appear negative. In
* order to avoid violating the Principle of Least Astonishment, * order to avoid violating the Principle of Least Astonishment,
* the delay is clamped not less than the system precision. * the delay is clamped not less than the system precision.
*/ */
if (p->pmode == M_BCST) { if (p->pmode == M_BCST) {
offset = LFP2D(r->xmt - r->dst); offset = LFP2D(r->xmt - r->dst);
delay = BDELAY; delay = BDELAY;
disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI * disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI *
2 * BDELAY; 2 * BDELAY;
} else { } else {
offset = (LFP2D(r->rec - r->org) + LFP2D(r->dst - offset = (LFP2D(r->rec - r->org) + LFP2D(r->dst -
skipping to change at page 85, line 15 skipping to change at page 85, line 24
double delay, /* roundtrip delay */ double delay, /* roundtrip delay */
double disp /* dispersion */ double disp /* dispersion */
) )
{ {
struct f f[NSTAGE]; /* sorted list */ struct f f[NSTAGE]; /* sorted list */
double dtemp; double dtemp;
int i; int i;
/* /*
* The clock filter contents consist of eight tuples (offset, * The clock filter contents consist of eight tuples (offset,
* delay, dispersion, time). Shift each tuple to the left, * delay, dispersion, time). Shift each tuple to the left,
* discarding the leftmost one. As each tuple is shifted, * discarding the leftmost one. As each tuple is shifted,
* increase the dispersion since the last filter update. At the * increase the dispersion since the last filter update. At the
* same time, copy each tuple to a temporary list. After this, * same time, copy each tuple to a temporary list. After this,
* place the (offset, delay, disp, time) in the vacated * place the (offset, delay, disp, time) in the vacated
* rightmost tuple. * rightmost tuple.
*/ */
for (i = 1; i < NSTAGE; i++) { for (i = 1; i < NSTAGE; i++) {
p->f[i] = p->f[i - 1]; p->f[i] = p->f[i - 1];
p->f[i].disp += PHI * (c.t - p->t); p->f[i].disp += PHI * (c.t - p->t);
f[i] = p->f[i]; f[i] = p->f[i];
} }
p->f[0].t = c.t; p->f[0].t = c.t;
p->f[0].offset = offset; p->f[0].offset = offset;
skipping to change at page 86, line 4 skipping to change at page 86, line 13
p->disp += f[i].disp / (2 ^ (i + 1)); p->disp += f[i].disp / (2 ^ (i + 1));
p->jitter += SQUARE(f[i].offset - f[0].offset); p->jitter += SQUARE(f[i].offset - f[0].offset);
} }
p->jitter = max(SQRT(p->jitter), LOG2D(s.precision)); p->jitter = max(SQRT(p->jitter), LOG2D(s.precision));
/* /*
* Prime directive: use a sample only once and never a sample * Prime directive: use a sample only once and never a sample
* older than the latest one, but anything goes before first * older than the latest one, but anything goes before first
* synchronized. * synchronized.
*/ */
if (f[0].t - p->t <= 0 && s.leap != NOSYNC) if (f[0].t - p->t <= 0 && s.leap != NOSYNC)
return; return;
/* /*
* Popcorn spike suppressor. Compare the difference between the * Popcorn spike suppressor. Compare the difference between the
* last and current offsets to the current jitter. If greater * last and current offsets to the current jitter. If greater
* than SGATE (3) and if the interval since the last offset is * than SGATE (3) and if the interval since the last offset is
* less than twice the system poll interval, dump the spike. * less than twice the system poll interval, dump the spike.
* Otherwise, and if not in a burst, shake out the truechimers. * Otherwise, and if not in a burst, shake out the truechimers.
*/ */
if (fabs(p->offset - dtemp) > SGATE * p->jitter && (f[0].t - if (fabs(p->offset - dtemp) > SGATE * p->jitter && (f[0].t -
p->t) < 2 * s.poll) p->t) < 2 * s.poll)
return; return;
p->t = f[0].t; p->t = f[0].t;
if (p->burst == 0) if (p->burst == 0)
skipping to change at page 86, line 51 skipping to change at page 87, line 16
* A distance error occurs if the root distance exceeds the * A distance error occurs if the root distance exceeds the
* distance threshold plus an increment equal to one poll * distance threshold plus an increment equal to one poll
* interval. * interval.
*/ */
if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll)) if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll))
return (FALSE); return (FALSE);
/* /*
* A loop error occurs if the remote peer is synchronized to the * A loop error occurs if the remote peer is synchronized to the
* local peer or the remote peer is synchronized to the current * local peer or the remote peer is synchronized to the current
* system peer. Note this is the behavior for IPv4; for IPv6 the * system peer. Note this is the behavior for IPv4; for IPv6
* MD5 hash is used instead. * the MD5 hash is used instead.
*/ */
if (p->refid == p->dstaddr || p->refid == s.refid) if (p->refid == p->dstaddr || p->refid == s.refid)
return (FALSE); return (FALSE);
/* /*
* An unreachable error occurs if the server is unreachable. * An unreachable error occurs if the server is unreachable.
*/ */
if (p->reach == 0) if (p->reach == 0)
return (FALSE); return (FALSE);
skipping to change at page 88, line 34 skipping to change at page 88, line 48
void void
fast_xmit( fast_xmit(
struct r *r, /* receive packet pointer */ struct r *r, /* receive packet pointer */
int mode, /* association mode */ int mode, /* association mode */
int auth /* authentication code */ int auth /* authentication code */
) )
{ {
struct x x; struct x x;
/* /*
* Initialize header and transmit timestamp. Note that the * Initialize header and transmit timestamp. Note that the
* transmit version is copied from the receive version. This is * transmit version is copied from the receive version. This is
* for backward compatibility. * for backward compatibility.
*/ */
x.version = r->version; x.version = r->version;
x.srcaddr = r->dstaddr; x.srcaddr = r->dstaddr;
x.dstaddr = r->srcaddr; x.dstaddr = r->srcaddr;
x.leap = s.leap; x.leap = s.leap;
x.mode = mode; x.mode = mode;
if (s.stratum == MAXSTRAT) if (s.stratum == MAXSTRAT)
x.stratum = 0; x.stratum = 0;
else else
x.stratum = s.stratum; x.stratum = s.stratum;
x.poll = r->poll; x.poll = r->poll;
skipping to change at page 89, line 12 skipping to change at page 89, line 27
x.rootdisp = D2FP(s.rootdisp); x.rootdisp = D2FP(s.rootdisp);
x.refid = s.refid; x.refid = s.refid;
x.reftime = s.reftime; x.reftime = s.reftime;
x.org = r->xmt; x.org = r->xmt;
x.rec = r->dst; x.rec = r->dst;
x.xmt = get_time(); x.xmt = get_time();
/* /*
* If the authentication code is A.NONE, include only the * If the authentication code is A.NONE, include only the
* header; if A.CRYPTO, send a crypto-NAK; if A.OK, send a valid * header; if A.CRYPTO, send a crypto-NAK; if A.OK, send a valid
* MAC. Use the key ID in the received packet and the key in the * MAC. Use the key ID in the received packet and the key in
* local key cache. * the local key cache.
*/ */
if (auth != A_NONE) { if (auth != A_NONE) {
if (auth == A_CRYPTO) { if (auth == A_CRYPTO) {
x.keyid = 0; x.keyid = 0;
} else { } else {
x.keyid = r->keyid; x.keyid = r->keyid;
x.dgst = md5(x.keyid); x.dgst = md5(x.keyid);
} }
} }
xmit_packet(&x); xmit_packet(&x);
} }
A.5.4. access() A.5.4. access()
/* /*
* access() - determine access restrictions * access() - determine access restrictions
*/ */
int int
access( access(
struct r *r /* receive packet pointer */ struct r *r /* receive packet pointer */
) )
{
/* {
* The access control list is an ordered set of tuples /*
* consisting of an address, mask and restrict word containing * The access control list is an ordered set of tuples
* defined bits. The list is searched for the first match on the * consisting of an address, mask, and restrict word containing
* source address (r->srcaddr) and the associated restrict word * defined bits. The list is searched for the first match on
* is returned. * the source address (r->srcaddr) and the associated restrict
*/ * word is returned.
return (/* access bits */ 0); */
} return (/* access bits */ 0);
}
A.5.5. System Process A.5.5. System Process
A.5.5.1. clock_select() A.5.5.1. clock_select()
/* /*
* clock_select() - find the best clocks * clock_select() - find the best clocks
*/ */
void void
clock_select() { clock_select() {
struct p *p, *osys; /* peer structure pointers */ struct p *p, *osys; /* peer structure pointers */
double low, high; /* correctness interval extents */ double low, high; /* correctness interval extents */
int allow, found, chime; /* used by intersection algorithm */ int allow, found, chime; /* used by intersection algorithm */
int n, i, j; int n, i, j;
/* /*
* We first cull the falsetickers from the server population, * We first cull the falsetickers from the server population,
* leaving only the truechimers. The correctness interval for * leaving only the truechimers. The correctness interval for
* association p is the interval from offset - root_dist() to * association p is the interval from offset - root_dist() to
* offset + root_dist(). The object of the game is to find a * offset + root_dist(). The object of the game is to find a
* majority clique; that is, an intersection of correctness * majority clique; that is, an intersection of correctness
* intervals numbering more than half the server population. * intervals numbering more than half the server population.
* *
* First construct the chime list of tuples (p, type, edge) as * First, construct the chime list of tuples (p, type, edge) as
* shown below, then sort the list by edge from lowest to * shown below, then sort the list by edge from lowest to
* highest. * highest.
*/ */
osys = s.p; osys = s.p;
s.p = NULL; s.p = NULL;
n = 0; n = 0;
while (fit(p)) { while (fit(p)) {
s.m[n].p = p; s.m[n].p = p;
s.m[n].type = +1; s.m[n].type = +1;
s.m[n].edge = p->offset + root_dist(p); s.m[n].edge = p->offset + root_dist(p);
skipping to change at page 90, line 44 skipping to change at page 91, line 13
s.m[n].edge = p->offset; s.m[n].edge = p->offset;
n++; n++;
s.m[n].p = p; s.m[n].p = p;
s.m[n].type = -1; s.m[n].type = -1;
s.m[n].edge = p->offset - root_dist(p); s.m[n].edge = p->offset - root_dist(p);
n++; n++;
} }
/* /*
* Find the largest contiguous intersection of correctness * Find the largest contiguous intersection of correctness
* intervals. Allow is the number of allowed falsetickers; found * intervals. Allow is the number of allowed falsetickers;
* is the number of midpoints. Note that the edge values are * found is the number of midpoints. Note that the edge values
* limited to the range +-(2 ^ 30) < +-2e9 by the timestamp * are limited to the range +-(2 ^ 30) < +-2e9 by the timestamp
* calculations. * calculations.
*/ */
low = 2e9; high = -2e9; low = 2e9; high = -2e9;
for (allow = 0; 2 * allow < n; allow++) { for (allow = 0; 2 * allow < n; allow++) {
/* /*
* Scan the chime list from lowest to highest to find * Scan the chime list from lowest to highest to find
* the lower endpoint. * the lower endpoint.
*/ */
found = 0; found = 0;
chime = 0; chime = 0;
for (i = 0; i < n; i++) { for (i = 0; i < n; i++) {
chime -= s.m[i].type; chime -= s.m[i].type;
if (chime >= n - found) { if (chime >= n - found) {
low = s.m[i].edge; low = s.m[i].edge;
skipping to change at page 91, line 34 skipping to change at page 92, line 4
chime = 0; chime = 0;
for (i = n - 1; i >= 0; i--) { for (i = n - 1; i >= 0; i--) {
chime += s.m[i].type; chime += s.m[i].type;
if (chime >= n - found) { if (chime >= n - found) {
high = s.m[i].edge; high = s.m[i].edge;
break; break;
} }
if (s.m[i].type == 0) if (s.m[i].type == 0)
found++; found++;
} }
/* /*
* If the number of midpoints is greater than the number * If the number of midpoints is greater than the number
* of allowed falsetickers, the intersection contains at * of allowed falsetickers, the intersection contains at
* least one truechimer with no midpoint. If so, * least one truechimer with no midpoint. If so,
* increment the number of allowed falsetickers and go * increment the number of allowed falsetickers and go
* around again. If not and the intersection is * around again. If not and the intersection is
* nonempty, declare success. * non-empty, declare success.
*/ */
if (found > allow) if (found > allow)
continue; continue;
if (high > low) if (high > low)
break; break;
} }
/* /*
* Clustering algorithm. Construct a list of survivors (p, * Clustering algorithm. Construct a list of survivors (p,
* metric) from the chime list, where metric is dominated first * metric) from the chime list, where metric is dominated first
* by stratum and then by root distance. All other things being * by stratum and then by root distance. All other things being
* equal, this is the order of preference. * equal, this is the order of preference.
*/ */
s.n = 0; s.n = 0;
for (i = 0; i < n; i++) { for (i = 0; i < n; i++) {
if (s.m[i].edge < low || s.m[i].edge > high) if (s.m[i].edge < low || s.m[i].edge > high)
continue; continue;
p = s.m[i].p; p = s.m[i].p;
s.v[n].p = p; s.v[n].p = p;
s.v[n].metric = MAXDIST * p->stratum + root_dist(p); s.v[n].metric = MAXDIST * p->stratum + root_dist(p);
s.n++; s.n++;
} }
/* /*
* There must be at least NSANE survivors to satisfy the * There must be at least NSANE survivors to satisfy the
* correctness assertions. Ordinarily, the Byzantine criteria * correctness assertions. Ordinarily, the Byzantine criteria
* require four, survivors, but for the demonstration here, one * require four survivors, but for the demonstration here, one
* is acceptable. * is acceptable.
*/ */
if (s.n < NSANE) if (s.n < NSANE)
return; return;
/* /*
* For each association p in turn, calculate the selection * For each association p in turn, calculate the selection
* jitter p->sjitter as the square root of the sum of squares * jitter p->sjitter as the square root of the sum of squares
* (p->offset - q->offset) over all q associations. The idea is * (p->offset - q->offset) over all q associations. The idea is
* to repeatedly discard the survivor with maximum selection * to repeatedly discard the survivor with maximum selection
* jitter until a termination condition is met. * jitter until a termination condition is met.
*/ */
while (1) { while (1) {
struct p *p, *q, *qmax; /* peer structure pointers */ struct p *p, *q, *qmax; /* peer structure pointers */
double max, min, dtemp; double max, min, dtemp;
max = -2e9; min = 2e9; max = -2e9; min = 2e9;
for (i = 0; i < s.n; i++) { for (i = 0; i < s.n; i++) {
p = s.v[i].p; p = s.v[i].p;
if (p->jitter < min) if (p->jitter < min)
min = p->jitter; min = p->jitter;
dtemp = 0; dtemp = 0;
skipping to change at page 93, line 12 skipping to change at page 93, line 30
if (dtemp > max) { if (dtemp > max) {
max = dtemp; max = dtemp;
qmax = q; qmax = q;
} }
} }
/* /*
* If the maximum selection jitter is less than the * If the maximum selection jitter is less than the
* minimum peer jitter, then tossing out more survivors * minimum peer jitter, then tossing out more survivors
* will not lower the minimum peer jitter, so we might * will not lower the minimum peer jitter, so we might
* as well stop. To make sure a few survivors are left * as well stop. To make sure a few survivors are left
* for the clustering algorithm to chew on, we also stop * for the clustering algorithm to chew on, we also stop
* if the number of survivors is less than or equal to * if the number of survivors is less than or equal to
* NMIN (3). * NMIN (3).
*/ */
if (max < min || n <= NMIN) if (max < min || n <= NMIN)
break; break;
/* /*
* Delete survivor qmax from the list and go around * Delete survivor qmax from the list and go around
* again. * again.
*/ */
s.n--; s.n--;
} }
/* /*
* Pick the best clock. If the old system peer is on the list * Pick the best clock. If the old system peer is on the list
* and at the same stratum as the first survivor on the list, * and at the same stratum as the first survivor on the list,
* then don't do a clock hop. Otherwise, select the first * then don't do a clock hop. Otherwise, select the first
* survivor on the list as the new system peer. * survivor on the list as the new system peer.
*/ */
if (osys->stratum == s.v[0].p->stratum) if (osys->stratum == s.v[0].p->stratum)
s.p = osys; s.p = osys;
else else
s.p = s.v[0].p; s.p = s.v[0].p;
clock_update(s.p); clock_update(s.p);
} }
A.5.5.2. root_dist() A.5.5.2. root_dist()
/* /*
* root_dist() - calculate root distance * root_dist() - calculate root distance
*/ */
double double
root_dist( root_dist(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
skipping to change at page 95, line 26 skipping to change at page 95, line 4
* synchronized, (2) the server stratum is invalid. * synchronized, (2) the server stratum is invalid.
*/ */
if (p->leap == NOSYNC || p->stratum >= MAXSTRAT) if (p->leap == NOSYNC || p->stratum >= MAXSTRAT)
return (FALSE); return (FALSE);
/* /*
* A distance error occurs if the root distance exceeds the * A distance error occurs if the root distance exceeds the
* distance threshold plus an increment equal to one poll * distance threshold plus an increment equal to one poll
* interval. * interval.
*/ */
if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll)) if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll))
return (FALSE); return (FALSE);
/* /*
* A loop error occurs if the remote peer is synchronized to the * A loop error occurs if the remote peer is synchronized to the
* local peer or the remote peer is synchronized to the current * local peer or the remote peer is synchronized to the current
* system peer. Note this is the behavior for IPv4; for IPv6 the * system peer. Note this is the behavior for IPv4; for IPv6
* MD5 hash is used instead. * the MD5 hash is used instead.
*/ */
if (p->refid == p->dstaddr || p->refid == s.refid) if (p->refid == p->dstaddr || p->refid == s.refid)
return (FALSE); return (FALSE);
/* /*
* An unreachable error occurs if the server is unreachable. * An unreachable error occurs if the server is unreachable.
*/ */
if (p->reach == 0) if (p->reach == 0)
return (FALSE); return (FALSE);
skipping to change at page 96, line 4 skipping to change at page 95, line 31
return (FALSE); return (FALSE);
return (TRUE); return (TRUE);
} }
A.5.5.4. clock_update() A.5.5.4. clock_update()
/* /*
* clock_update() - update the system clock * clock_update() - update the system clock
*/ */
void void
clock_update( clock_update(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
double dtemp; double dtemp;
/* /*
* If this is an old update, for instance as the result of a * If this is an old update, for instance, as the result of a
* system peer change, avoid it. We never use an old sample or * system peer change, avoid it. We never use an old sample or
* the same sample twice. * the same sample twice.
*/ */
if (s.t >= p->t) if (s.t >= p->t)
return; return;
/* /*
* Combine the survivor offsets and update the system clock; the * Combine the survivor offsets and update the system clock; the
* local_clock() routine will tell us the good or bad news. * local_clock() routine will tell us the good or bad news.
*/ */
s.t = p->t; s.t = p->t;
skipping to change at page 96, line 27 skipping to change at page 96, line 4
if (s.t >= p->t) if (s.t >= p->t)
return; return;
/* /*
* Combine the survivor offsets and update the system clock; the * Combine the survivor offsets and update the system clock; the
* local_clock() routine will tell us the good or bad news. * local_clock() routine will tell us the good or bad news.
*/ */
s.t = p->t; s.t = p->t;
clock_combine(); clock_combine();
switch (local_clock(p, s.offset)) { switch (local_clock(p, s.offset)) {
/* /*
* The offset is too large and probably bogus. Complain to the * The offset is too large and probably bogus. Complain to the
* system log and order the operator to set the clock manually * system log and order the operator to set the clock manually
* within PANIC range. The reference implementation includes a * within PANIC range. The reference implementation includes a
* command line option to disable this check and to change the * command line option to disable this check and to change the
* panic threshold from the default 1000 s as required. * panic threshold from the default 1000 s as required.
*/ */
case PANIC: case PANIC:
exit (0); exit (0);
/* /*
* The offset is more than the step threshold (0.125 s by * The offset is more than the step threshold (0.125 s by
* default). After a step, all associations now have * default). After a step, all associations now have
* inconsistent time valurs, so they are reset and started * inconsistent time values, so they are reset and started
* fresh. The step threshold can be changed in the reference * fresh. The step threshold can be changed in the reference
* implementation in order to lessen the chance the clock might * implementation in order to lessen the chance the clock might
* be stepped backwards. However, there may be serious * be stepped backwards. However, there may be serious
* consequences, as noted in the white papers at the NTP project * consequences, as noted in the white papers at the NTP project
* site. * site.
*/ */
case STEP: case STEP:
while (/* all associations */ 0) while (/* all associations */ 0)
clear(p, X_STEP); clear(p, X_STEP);
s.stratum = MAXSTRAT; s.stratum = MAXSTRAT;
s.poll = MINPOLL; s.poll = MINPOLL;
break; break;
/* /*
* The offset was less than the step threshold, which is the * The offset was less than the step threshold, which is the
* normal case. Update the system variables from the peer * normal case. Update the system variables from the peer
* variables. The lower clamp on the dispersion increase is to * variables. The lower clamp on the dispersion increase is to
* avoid timing loops and clockhopping when highly precise * avoid timing loops and clockhopping when highly precise
* sources are in play. The clamp can be changed from the * sources are in play. The clamp can be changed from the
* default .01 s in the reference implementation. * default .01 s in the reference implementation.
*/ */
case SLEW: case SLEW:
s.leap = p->leap; s.leap = p->leap;
s.stratum = p->stratum + 1; s.stratum = p->stratum + 1;
s.refid = p->refid; s.refid = p->refid;
s.reftime = p->reftime; s.reftime = p->reftime;
s.rootdelay = p->rootdelay + p->delay; s.rootdelay = p->rootdelay + p->delay;
dtemp = SQRT(SQUARE(p->jitter) + SQUARE(s.jitter)); dtemp = SQRT(SQUARE(p->jitter) + SQUARE(s.jitter));
dtemp += max(p->disp + PHI * (c.t - p->t) + dtemp += max(p->disp + PHI * (c.t - p->t) +
skipping to change at page 98, line 19 skipping to change at page 97, line 29
void void
clock_combine() clock_combine()
{ {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
double x, y, z, w; double x, y, z, w;
int i; int i;
/* /*
* Combine the offsets of the clustering algorithm survivors * Combine the offsets of the clustering algorithm survivors
* using a weighted average with weight determined by the root * using a weighted average with weight determined by the root
* distance. Compute the selection jitter as the weighted RMS * distance. Compute the selection jitter as the weighted RMS
* difference between the first survivor and the remaining * difference between the first survivor and the remaining
* survivors. In some cases the inherent clock jitter can be * survivors. In some cases, the inherent clock jitter can be
* reduced by not using this algorithm, especially when frequent * reduced by not using this algorithm, especially when frequent
* clockhopping is involved. The reference implementation can be * clockhopping is involved. The reference implementation can
* configured to avoid this algorithm by designating a preferred * be configured to avoid this algorithm by designating a
* peer. * preferred peer.
*/ */
y = z = w = 0; y = z = w = 0;
for (i = 0; s.v[i].p != NULL; i++) { for (i = 0; s.v[i].p != NULL; i++) {
p = s.v[i].p; p = s.v[i].p;
x = root_dist(p); x = root_dist(p);
y += 1 / x; y += 1 / x;
z += p->offset / x; z += p->offset / x;
w += SQUARE(p->offset - s.v[0].p->offset) / x; w += SQUARE(p->offset - s.v[0].p->offset) / x;
} }
s.offset = z / y; s.offset = z / y;
skipping to change at page 99, line 4 skipping to change at page 98, line 17
* Clock discipline parameters and constants * Clock discipline parameters and constants
*/ */
#define STEPT .128 /* step threshold (s) */ #define STEPT .128 /* step threshold (s) */
#define WATCH 900 /* stepout threshold (s) */ #define WATCH 900 /* stepout threshold (s) */
#define PANICT 1000 /* panic threshold (s) */ #define PANICT 1000 /* panic threshold (s) */
#define PLL 65536 /* PLL loop gain */ #define PLL 65536 /* PLL loop gain */
#define FLL MAXPOLL + 1 /* FLL loop gain */ #define FLL MAXPOLL + 1 /* FLL loop gain */
#define AVG 4 /* parameter averaging constant */ #define AVG 4 /* parameter averaging constant */
#define ALLAN 1500 /* compromise Allan intercept (s) */ #define ALLAN 1500 /* compromise Allan intercept (s) */
#define LIMIT 30 /* poll-adjust threshold */ #define LIMIT 30 /* poll-adjust threshold */
#define MAXFREQ 500e-6 /* frequency tolerance (500 PPM) */ #define MAXFREQ 500e-6 /* frequency tolerance (500 ppm) */
#define PGATE 4 /* poll-adjust gate */ #define PGATE 4 /* poll-adjust gate */
/* /*
* local_clock() - discipline the local clock * local_clock() - discipline the local clock
*/ */
int /* return code */ int /* return code */
local_clock( local_clock(
struct p *p, /* peer structure pointer */ struct p *p, /* peer structure pointer */
double offset /* clock offset from combine() */ double offset /* clock offset from combine() */
) )
skipping to change at page 99, line 29 skipping to change at page 98, line 42
int rval; int rval;
double etemp, dtemp; double etemp, dtemp;
/* /*
* If the offset is too large, give up and go home. * If the offset is too large, give up and go home.
*/ */
if (fabs(offset) > PANICT) if (fabs(offset) > PANICT)
return (PANIC); return (PANIC);
/* /*
* Clock state machine transition function. This is where the * Clock state machine transition function. This is where the
* action is and defines how the system reacts to large time * action is and defines how the system reacts to large time
* and frequency errors. There are two main regimes: when the * and frequency errors. There are two main regimes: when the
* offset exceeds the step threshold and when it does not. * offset exceeds the step threshold and when it does not.
*/ */
rval = SLEW; rval = SLEW;
mu = p->t - s.t; mu = p->t - s.t;
freq = 0; freq = 0;
if (fabs(offset) > STEPT) { if (fabs(offset) > STEPT) {
switch (c.state) { switch (c.state) {
/* /*
* In S_SYNC state we ignore the first outlyer amd * In S_SYNC state, we ignore the first outlier and
* switch to S_SPIK state. * switch to S_SPIK state.
*/ */
case SYNC: case SYNC:
state = SPIK; state = SPIK;
return (rval); return (rval);
/* /*
* In S_FREQ state we ignore outlyers and inlyers. At * In S_FREQ state, we ignore outliers and inliers. At
* the first outlyer after the stepout threshold, * the first outlier after the stepout threshold,
* compute the apparent frequency correction and step * compute the apparent frequency correction and step
* the time. * the time.
*/ */
case FREQ: case FREQ:
if (mu < WATCH) if (mu < WATCH)
return (IGNORE); return (IGNORE);
freq = (offset - c.offset) / mu; freq = (offset - c.offset) / mu;
/* fall through to S_SPIK */ /* fall through to S_SPIK */
/* /*
* In S_SPIK state we ignore succeeding outlyers until * In S_SPIK state, we ignore succeeding outliers until
* either an inlyer is found or the stepout threshold is * either an inlier is found or the stepout threshold is
* exceeded. * exceeded.
*/ */
case SPIK: case SPIK:
if (mu < WATCH) if (mu < WATCH)
return (IGNORE); return (IGNORE);
/* fall through to default */ /* fall through to default */
/* /*
* We get here by default in S_NSET and S_FSET states * We get here by default in S_NSET and S_FSET states
* and from above in S_FREQ state. Step the time and * and from above in S_FREQ state. Step the time and
* clamp down the poll interval. * clamp down the poll interval.
* *
* In S_NSET state an initial frequency correction is * In S_NSET state, an initial frequency correction is
* not available, usually because the frequency file has * not available, usually because the frequency file has
* not yet been written. Since the time is outside the * not yet been written. Since the time is outside the
* capture range, the clock is stepped. The frequency * capture range, the clock is stepped. The frequency
* will be set directly following the stepout interval. * will be set directly following the stepout interval.
* *
* In S_FSET state the initial frequency has been set * In S_FSET state, the initial frequency has been set
* from the frequency file. Since the time is outside * from the frequency file. Since the time is outside
* the capture range, the clock is stepped immediately, * the capture range, the clock is stepped immediately,
* rather than after the stepout interval. Guys get * rather than after the stepout interval. Guys get
* nervous if it takes 17 minutes to set the clock for * nervous if it takes 17 minutes to set the clock for
* the first time. * the first time.
* *
* In S_SPIK state the stepout threshold has expired and * In S_SPIK state, the stepout threshold has expired
* the phase is still above the step threshold. Note * and the phase is still above the step threshold.
* that a single spike greater than the step threshold * Note that a single spike greater than the step
* is always suppressed, even at the longer poll * threshold is always suppressed, even at the longer
* intervals. * poll intervals.
*/ */
default: default:
/* /*
* This is the kernel set time function, usually * This is the kernel set time function, usually
* implemented by the Unix settimeofday() system * implemented by the Unix settimeofday() system
* call. * call.
*/ */
step_time(offset); step_time(offset);
c.count = 0; c.count = 0;
skipping to change at page 101, line 22 skipping to change at page 100, line 34
rstclock(FREQ, p->t, 0); rstclock(FREQ, p->t, 0);
return (rval); return (rval);
} }
break; break;
} }
rstclock(SYNC, p->t, 0); rstclock(SYNC, p->t, 0);
} else { } else {
/* /*
* Compute the clock jitter as the RMS of exponentially * Compute the clock jitter as the RMS of exponentially
* weighted offset differences. This is used by the * weighted offset differences. This is used by the
* poll-adjust code. * poll-adjust code.
*/ */
etemp = SQUARE(c.jitter); etemp = SQUARE(c.jitter);
dtemp = SQUARE(max(fabs(offset - c.last), dtemp = SQUARE(max(fabs(offset - c.last),
LOG2D(s.precision))); LOG2D(s.precision)));
c.jitter = SQRT(etemp + (dtemp - etemp) / AVG); c.jitter = SQRT(etemp + (dtemp - etemp) / AVG);
switch (c.state) { switch (c.state) {
/* /*
* In S_NSET state this is the first update received and * In S_NSET state, this is the first update received
* the frequency has not been initialized. The first * and the frequency has not been initialized. The
* thing to do is directly measure the oscillator * first thing to do is directly measure the oscillator
* frequency. * frequency.
*/ */
case NSET: case NSET:
rstclock(FREQ, p->t, offset); rstclock(FREQ, p->t, offset);
return (IGNORE); return (IGNORE);
/* /*
* In S_FSET state this is the first update and the * In S_FSET state, this is the first update and the
* frequency has been initialized. Adjust the phase, but * frequency has been initialized. Adjust the phase,
* don't adjust the frequency until the next update. * but don't adjust the frequency until the next update.
*/ */
case FSET: case FSET:
rstclock(SYNC, p->t, offset); rstclock(SYNC, p->t, offset);
break; break;
/* /*
* In S_FREQ state ignore updates until the stepout * In S_FREQ state, ignore updates until the stepout
* threshold. After that, correct the phase and * threshold. After that, correct the phase and
* frequency and switch to S_SYNC state. * frequency and switch to S_SYNC state.
*/ */
case FREQ: case FREQ:
if (c.t - s.t < WATCH) if (c.t - s.t < WATCH)
return (IGNORE); return (IGNORE);
freq = (offset - c.offset) / mu; freq = (offset - c.offset) / mu;
break; break;
/* /*
* We get here by default in S_SYNC and S_SPIK states. * We get here by default in S_SYNC and S_SPIK states.
* Here we compute the frequency update due to PLL and * Here we compute the frequency update due to PLL and
* FLL contributions. * FLL contributions.
*/ */
default: default:
/* /*
* The FLL and PLL frequency gain constants * The FLL and PLL frequency gain constants
* depend on the poll interval and Allan * depending on the poll interval and Allan
* intercept. The FLL is not used below one-half * intercept. The FLL is not used below one
* the Allan intercept. Above that the loop gain * half the Allan intercept. Above that the
* increases in steps to 1 / AVG. * loop gain increases in steps to 1 / AVG.
*/ */
if (LOG2D(s.poll) > ALLAN / 2) { if (LOG2D(s.poll) > ALLAN / 2) {
etemp = FLL - s.poll; etemp = FLL - s.poll;
if (etemp < AVG) if (etemp < AVG)
etemp = AVG; etemp = AVG;
freq += (offset - c.offset) / (max(mu, freq += (offset - c.offset) / (max(mu,
ALLAN) * etemp); ALLAN) * etemp);
} }
/* /*
* For the PLL the integration interval * For the PLL the integration interval
* (numerator) is the minimum of the update * (numerator) is the minimum of the update
* interval and poll interval. This allows * interval and poll interval. This allows
* oversampling, but not undersampling. * oversampling, but not undersampling.
*/ */
etemp = min(mu, LOG2D(s.poll)); etemp = min(mu, LOG2D(s.poll));
dtemp = 4 * PLL * LOG2D(s.poll); dtemp = 4 * PLL * LOG2D(s.poll);
freq += offset * etemp / (dtemp * dtemp); freq += offset * etemp / (dtemp * dtemp);
rstclock(SYNC, p->t, offset); rstclock(SYNC, p->t, offset);
break; break;
} }
} }
skipping to change at page 103, line 4 skipping to change at page 102, line 20
etemp = min(mu, LOG2D(s.poll)); etemp = min(mu, LOG2D(s.poll));
dtemp = 4 * PLL * LOG2D(s.poll); dtemp = 4 * PLL * LOG2D(s.poll);
freq += offset * etemp / (dtemp * dtemp); freq += offset * etemp / (dtemp * dtemp);
rstclock(SYNC, p->t, offset); rstclock(SYNC, p->t, offset);
break; break;
} }
} }
/* /*
* Calculate the new frequency and frequency stability (wander). * Calculate the new frequency and frequency stability (wander).
* Compute the clock wander as the RMS of exponentially weighted * Compute the clock wander as the RMS of exponentially weighted
* frequency differences. This is not used directly, but can, * frequency differences. This is not used directly, but can,
* along with the jitter, be a highly useful monitoring and * along with the jitter, be a highly useful monitoring and
* debugging tool * debugging tool.
*/ */
freq += c.freq; freq += c.freq;
c.freq = max(min(MAXFREQ, freq), -MAXFREQ); c.freq = max(min(MAXFREQ, freq), -MAXFREQ);
etemp = SQUARE(c.wander); etemp = SQUARE(c.wander);
dtemp = SQUARE(freq); dtemp = SQUARE(freq);
c.wander = SQRT(etemp + (dtemp - etemp) / AVG); c.wander = SQRT(etemp + (dtemp - etemp) / AVG);
/* /*
* Here we adjust the poll interval by comparing the current * Here we adjust the poll interval by comparing the current
* offset with the clock jitter. If the offset is less than the * offset with the clock jitter. If the offset is less than the
* clock jitter times a constant, then the averaging interval is * clock jitter times a constant, then the averaging interval is
* increased, otherwise it is decreased. A bit of hysteresis * increased; otherwise, it is decreased. A bit of hysteresis
* helps calm the dance. Works best using burst mode. * helps calm the dance. Works best using burst mode.
*/ */
if (fabs(c.offset) < PGATE * c.jitter) { if (fabs(c.offset) < PGATE * c.jitter) {
c.count += s.poll; c.count += s.poll;
if (c.count > LIMIT) { if (c.count > LIMIT) {
c.count = LIMIT; c.count = LIMIT;
if (s.poll < MAXPOLL) { if (s.poll < MAXPOLL) {
c.count = 0; c.count = 0;
s.poll++; s.poll++;
} }
} }
skipping to change at page 104, line 4 skipping to change at page 103, line 11
if (c.count < -LIMIT) { if (c.count < -LIMIT) {
c.count = -LIMIT; c.count = -LIMIT;
if (s.poll > MINPOLL) { if (s.poll > MINPOLL) {
c.count = 0; c.count = 0;
s.poll--; s.poll--;
} }
} }
} }
return (rval); return (rval);
} }
A.5.5.7. rstclock() A.5.5.7. rstclock()
/* /*
* rstclock() - clock state machine * rstclock() - clock state machine
*/ */
void void
rstclock( rstclock(
int state, /* new state */ int state, /* new state */
double offset, /* new offset */ double offset, /* new offset */
double t /* new update time */ double t /* new update time */
) )
{ {
/* /*
* Enter new state and set state variables. Note we use the time * Enter new state and set state variables. Note, we use the
* of the last clock filter sample, which must be earlier than * time of the last clock filter sample, which must be earlier
* the current time. * than the current time.
*/ */
c.state = state; c.state = state;
c.last = c.offset = offset; c.last = c.offset = offset;
s.t = t; s.t = t;
} }
A.5.6. Clock Adjust Process A.5.6. Clock Adjust Process
A.5.6.1. clock_adjust() A.5.6.1. clock_adjust()
/* /*
* clock_adjust() - runs at one-second intervals * clock_adjust() - runs at one-second intervals
*/ */
void void
clock_adjust() { clock_adjust() {
double dtemp; double dtemp;
/* /*
* Update the process time c.t. Also increase the dispersion * Update the process time c.t. Also increase the dispersion
* since the last update. In contrast to NTPv3, NTPv4 does not * since the last update. In contrast to NTPv3, NTPv4 does not
* declare unsynchronized after one day, since the dispersion * declare unsynchronized after one day, since the dispersion
* threshold serves this function. When the dispersion exceeds * threshold serves this function. When the dispersion exceeds
* MAXDIST (1 s), the server is considered unfit for * MAXDIST (1 s), the server is considered unfit for
* synchronization. * synchronization.
*/
c.t++;
s.rootdisp += PHI;
/* */
* Implement the phase and frequency adjustments. The gain c.t++;
* factor (denominator) is not allowed to increase beyond the s.rootdisp += PHI;
* Allan intercept. It doesn't make sense to average phase noise
* beyond this point and it helps to damp residual offset at the
* longer poll intervals.
*/
dtemp = c.offset / (PLL * min(LOG2D(s.poll), ALLAN));
c.offset -= dtemp;
/* /*
* This is the kernel adjust time function, usually implemented * Implement the phase and frequency adjustments. The gain
* by the Unix adjtime() system call. * factor (denominator) is not allowed to increase beyond the
*/ * Allan intercept. It doesn't make sense to average phase
adjust_time(c.freq + dtemp); * noise beyond this point and it helps to damp residual offset
* at the longer poll intervals.
*/
dtemp = c.offset / (PLL * min(LOG2D(s.poll), ALLAN));
c.offset -= dtemp;
/* /*
* Peer timer. Call the poll() routine when the poll timer * This is the kernel adjust time function, usually implemented
* expires. * by the Unix adjtime() system call.
*/ */
while (/* all associations */ 0) { adjust_time(c.freq + dtemp);
struct p *p; /* dummy peer structure pointer */
if (c.t >= p->nextdate) /*
poll(p); * Peer timer. Call the poll() routine when the poll timer
} * expires.
*/
while (/* all associations */ 0) {
struct p *p; /* dummy peer structure pointer */
/* if (c.t >= p->nextdate)
* Once per hour write the clock frequency to a file poll(p);
*/ }
/*
* if (c.t % 3600 == 3599) /*
* write c.freq to file * Once per hour, write the clock frequency to a file.
*/ */
} /*
* if (c.t % 3600 == 3599)
* write c.freq to file
*/
}
A.5.7. Poll Process A.5.7. Poll Process
/* /*
* Poll process parameters and constants * Poll process parameters and constants
*/ */
#define UNREACH 12 /* unreach counter threshold */ #define UNREACH 12 /* unreach counter threshold */
#define BCOUNT 8 /* packets in a burst */ #define BCOUNT 8 /* packets in a burst */
#define BTIME 2 /* burst interval (s) */ #define BTIME 2 /* burst interval (s) */
skipping to change at page 106, line 12 skipping to change at page 105, line 20
void void
poll( poll(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
int hpoll; int hpoll;
int oreach; int oreach;
/* /*
* This routine is called when the current time c.t catches up * This routine is called when the current time c.t catches up
* to the next poll time p->nextdate. The value p->outdate is * to the next poll time p->nextdate. The value p->outdate is
* the last time this routine was executed. The poll_update() * the last time this routine was executed. The poll_update()
* routine determines the next execution time p->nextdate. * routine determines the next execution time p->nextdate.
* *
* If broadcasting, just do it, but only if we are synchronized. * If broadcasting, just do it, but only if we are synchronized.
*/ */
hpoll = p->hpoll; hpoll = p->hpoll;
if (p->hmode == M_BCST) { if (p->hmode == M_BCST) {
p->outdate = c.t; p->outdate = c.t;
if (s.p != NULL) if (s.p != NULL)
peer_xmit(p); peer_xmit(p);
poll_update(p, hpoll); poll_update(p, hpoll);
return; return;
} }
/* /*
* If manycasting, start with ttl = 1. The ttl is increased by * If manycasting, start with ttl = 1. The ttl is increased by
* one for each poll until MAXCLOCK servers have been found or * one for each poll until MAXCLOCK servers have been found or
* ttl reaches TTLMAX. If reaching MAXCLOCK, stop polling until * ttl reaches TTLMAX. If reaching MAXCLOCK, stop polling until
* the number of servers falls below MINCLOCK, then start all * the number of servers falls below MINCLOCK, then start all
* over. * over.
*/ */
if (p->hmode == M_CLNT && p->flags & P_MANY) { if (p->hmode == M_CLNT && p->flags & P_MANY) {
p->outdate = c.t; p->outdate = c.t;
if (p->unreach > BEACON) { if (p->unreach > BEACON) {
p->unreach = 0; p->unreach = 0;
p->ttl = 1; p->ttl = 1;
peer_xmit(p); peer_xmit(p);
} else if (s.n < MINCLOCK) { } else if (s.n < MINCLOCK) {
skipping to change at page 107, line 4 skipping to change at page 106, line 11
p->ttl++; p->ttl++;
peer_xmit(p); peer_xmit(p);
} }
p->unreach++; p->unreach++;
poll_update(p, hpoll); poll_update(p, hpoll);
return; return;
} }
if (p->burst == 0) { if (p->burst == 0) {
/* /*
* We are not in a burst. Shift the reachability * We are not in a burst. Shift the reachability
* register to the left. Hopefully, some time before the * register to the left. Hopefully, some time before
* next poll a packet will arrive and set the rightmost * the next poll a packet will arrive and set the
* bit. * rightmost bit.
*/ */
oreach = p->reach; oreach = p->reach;
p->outdate = c.t; p->outdate = c.t;
p->reach = p->reach << 1; p->reach = p->reach << 1;
if (!(p->reach & 0x7)) if (!(p->reach & 0x7))
clock_filter(p, 0, 0, MAXDISP); clock_filter(p, 0, 0, MAXDISP);
if (!p->reach) { if (!p->reach) {
/* /*
* The server is unreachable, so bump the * The server is unreachable, so bump the
* unreach counter. If the unreach threshold has * unreach counter. If the unreach threshold
* been reached, double the poll interval to * has been reached, double the poll interval
* minimize wasted network traffic. Send a burst * to minimize wasted network traffic. Send a
* only if enabled and the unreach threshold has * burst only if enabled and the unreach
* not been reached. * threshold has not been reached.
*/ */
if (p->flags & P_IBURST && p->unreach == 0) { if (p->flags & P_IBURST && p->unreach == 0) {
p->burst = BCOUNT; p->burst = BCOUNT;
} else if (p->unreach < UNREACH) } else if (p->unreach < UNREACH)
p->unreach++; p->unreach++;
else else
hpoll++; hpoll++;
p->unreach++; p->unreach++;
} else { } else {
/* /*
* The server is reachable. Set the poll * The server is reachable. Set the poll
* interval to the system poll interval. Send a * interval to the system poll interval. Send a
* burst only if enabled and the peer is fit. * burst only if enabled and the peer is fit.
*/ */
p->unreach = 0; p->unreach = 0;
hpoll = s.poll; hpoll = s.poll;
if (p->flags & P_BURST && fit(p)) if (p->flags & P_BURST && fit(p))
p->burst = BCOUNT; p->burst = BCOUNT;
} }
} else { } else {
/* /*
* If in a burst, count it down. When the reply comes * If in a burst, count it down. When the reply comes
* back the clock_filter() routine will call * back the clock_filter() routine will call
* clock_select() to process the results of the burst. * clock_select() to process the results of the burst.
*/ */
p->burst--; p->burst--;
} }
/* /*
* Do not transmit if in broadcast client mode. * Do not transmit if in broadcast client mode.
*/ */
if (p->hmode != M_BCLN) if (p->hmode != M_BCLN)
peer_xmit(p); peer_xmit(p);
skipping to change at page 109, line 4 skipping to change at page 107, line 20
} }
/* /*
* Do not transmit if in broadcast client mode. * Do not transmit if in broadcast client mode.
*/ */
if (p->hmode != M_BCLN) if (p->hmode != M_BCLN)
peer_xmit(p); peer_xmit(p);
poll_update(p, hpoll); poll_update(p, hpoll);
} }
A.5.7.2. poll_update() A.5.7.2. poll_update()
/* /*
* poll_update() - update the poll interval for association p * poll_update() - update the poll interval for association p
* *
* Note: This routine is called by both the packet() and poll() routine. * Note: This routine is called by both the packet() and poll() routine.
* Since the packet() routine is executed when a network packet arrives * Since the packet() routine is executed when a network packet arrives
* and the poll() routine is executed as the result of timeout, a * and the poll() routine is executed as the result of timeout, a
* potential race can occur, possibly causing an incorrect interval for * potential race can occur, possibly causing an incorrect interval for
* the next poll. This is considered so unlikely as to be negligible. * the next poll. This is considered so unlikely as to be negligible.
*/ */
void void
poll_update( poll_update(
struct p *p, /* peer structure pointer */ struct p *p, /* peer structure pointer */
int poll /* poll interval (log2 s) */ int poll /* poll interval (log2 s) */
) )
{ {
/* /*
* This routine is called by both the poll() and packet() * This routine is called by both the poll() and packet()
* routines to determine the next poll time. If within a burst * routines to determine the next poll time. If within a burst
* the poll interval is two seconds. Otherwise, it is the * the poll interval is two seconds. Otherwise, it is the
* minimum of the host poll interval and peer poll interval, but * minimum of the host poll interval and peer poll interval, but
* not greater than MAXPOLL and not less than MINPOLL. The * not greater than MAXPOLL and not less than MINPOLL. The
* design insures that a longer interval can be preempted by a * design ensures that a longer interval can be preempted by a
* shorter one if required for rapid response. * shorter one if required for rapid response.
*/ */
p->hpoll = max(min(MAXPOLL, poll), MINPOLL); p->hpoll = max(min(MAXPOLL, poll), MINPOLL);
if (p->burst > 0) { if (p->burst > 0) {
if (p->nextdate != c.t) if (p->nextdate != c.t)
return; return;
else else
p->nextdate += BTIME; p->nextdate += BTIME;
} else { } else {
/* /*
* While not shown here, the reference implementation * While not shown here, the reference implementation
* randomizes the poll interval by a small factor. * randomizes the poll interval by a small factor.
*/ */
p->nextdate = p->outdate + (1 << max(min(p->ppoll, p->nextdate = p->outdate + (1 << max(min(p->ppoll,
p->hpoll), MINPOLL)); p->hpoll), MINPOLL));
} }
/* /*
* It might happen that the due time has already passed. If so, * It might happen that the due time has already passed. If so,
* make it one second in the future. * make it one second in the future.
*/ */
if (p->nextdate <= c.t) if (p->nextdate <= c.t)
p->nextdate = c.t + 1; p->nextdate = c.t + 1;
} }
A.5.7.3. peer_xmit() A.5.7.3. peer_xmit()
/* /*
* transmit() - transmit a packet for association p * transmit() - transmit a packet for association p
*/ */
void void
peer_xmit( peer_xmit(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
struct x x; /* transmit packet */ struct x x; /* transmit packet */
skipping to change at page 111, line 39 skipping to change at page 109, line 9
x.rootdisp = D2FP(s.rootdisp); x.rootdisp = D2FP(s.rootdisp);
x.refid = s.refid; x.refid = s.refid;
x.reftime = s.reftime; x.reftime = s.reftime;
x.org = p->org; x.org = p->org;
x.rec = p->rec; x.rec = p->rec;
x.xmt = get_time(); x.xmt = get_time();
p->xmt = x.xmt; p->xmt = x.xmt;
/* /*
* If the key ID is nonzero, send a valid MAC using the key ID * If the key ID is nonzero, send a valid MAC using the key ID
* of the association and the key in the local key cache. If * of the association and the key in the local key cache. If
* something breaks, like a missing trusted key, don't send the * something breaks, like a missing trusted key, don't send the
* packet; just reset the association and stop until the problem * packet; just reset the association and stop until the problem
* is fixed. * is fixed.
*/ */
if (p->keyid) if (p->keyid)
if (/* p->keyid invalid */ 0) { if (/* p->keyid invalid */ 0) {
clear(p, X_NKEY); clear(p, X_NKEY);
return; return;
} }
x.dgst = md5(p->keyid); x.dgst = md5(p->keyid);
xmit_packet(&x); xmit_packet(&x);
} }
Authors' Addresses Authors' Addresses
Dr. David L. Mills
University of Delaware
Newark, DE 19716
US
Phone: +1 302 831 8247
EMail: mills@udel.edu
Jim Martin (editor)
Internet Systems Consortium
950 Charter Street
Redwood City, CA 94063
US
Phone: +1 650 423 1378
EMail: jrmii@isc.org
Jack Burbank Jack Burbank
The Johns Hopkins University Applied Physics Laboratory The Johns Hopkins University Applied Physics Laboratory
11100 Johns Hopkins Road 11100 Johns Hopkins Road
Laurel, MD 20723-6099 Laurel, MD 20723-6099
US US
Phone: +1 443 778 7127 Phone: +1 443 778 7127
Email: jack.burbank@jhuapl.edu EMail: jack.burbank@jhuapl.edu