draft-ietf-ntp-ntpv4-proto-03.txt   draft-ietf-ntp-ntpv4-proto-04.txt 
NTP WG J. Burbank, Ed. NTP WG J. Burbank, Ed.
Internet-Draft JHU/APL Internet-Draft W. Kasch, Ed.
Obsoletes: RFC 4330 (if approved) J. Martin, Ed. Obsoletes: RFC 4330, RFC 1305 JHU/APL
(if approved) J. Martin, Ed.
Intended status: Standards Track Netzwert AG Intended status: Standards Track Netzwert AG
Expires: April 26, 2007 D. Mills Expires: July 21, 2007 D. Mills
U. Del. U. Del.
October 23, 2006 January 17, 2007
Network Time Protocol Version 4 Reference and Implementation Guide Network Time Protocol Version 4 Protocol And Algorithms Specification
draft-ietf-ntp-ntpv4-proto-03 draft-ietf-ntp-ntpv4-proto-04
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 37 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on April 26, 2007. This Internet-Draft will expire on July 21, 2007.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2006). Copyright (C) The IETF Trust (2007).
Abstract Abstract
The Network Time Protocol (NTP) is widely used to synchronize The Network Time Protocol (NTP) is widely used to synchronize
computer clocks in the Internet. This memorandum describes Version 4 computer clocks in the Internet. This memorandum describes Version 4
of the NTP (NTPv4), introducing several changes from Version 3 of NTP of the NTP (NTPv4), introducing several changes from Version 3 of NTP
(NTPv3) described in RFC 1305, including the introduction of a (NTPv3) described in RFC 1305, including the introduction of a
modified protocol header to accomodate Internet Protocol Version 6. modified protocol header to accomodate Internet Protocol Version 6.
NTPv4 also includes optional extensions to the NTPv3 NTPv4 also includes optional extensions to the NTPv3
protocol,including a dynamic server discovery mechanism. protocol,including a dynamic server discovery mechanism.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 4 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 5
2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 4 2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 5
3. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 6 3. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Implementation Model . . . . . . . . . . . . . . . . . . . . 9 4. Implementation Model . . . . . . . . . . . . . . . . . . . . 10
5. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 12 5. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 13
6. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 15 6. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 17
6.1. Structure Conventions . . . . . . . . . . . . . . . . . . 16 6.1. Structure Conventions . . . . . . . . . . . . . . . . . . 17
6.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 16 6.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 17
6.3. Packet Header Variables . . . . . . . . . . . . . . . . . 18 6.3. Packet Header Variables . . . . . . . . . . . . . . . . . 19
6.3.1. The Kiss-o'-Death Packet . . . . . . . . . . . . . . 22 6.3.1. The Kiss-o'-Death Packet . . . . . . . . . . . . . . 25
6.3.2. NTP Extension Field Format . . . . . . . . . . . . . 23 6.3.2. NTP Extension Field Format . . . . . . . . . . . . . 26
7. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 25 7. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 28
8. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 29 8. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 32
8.1. Peer Process Variables . . . . . . . . . . . . . . . . . 30 8.1. Peer Process Variables . . . . . . . . . . . . . . . . . 32
8.2. Peer Process Operations . . . . . . . . . . . . . . . . . 32 8.2. Peer Process Operations . . . . . . . . . . . . . . . . . 35
9. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . 39 8.3. Clock Filter Algorithm . . . . . . . . . . . . . . . . . 42
10. System Process . . . . . . . . . . . . . . . . . . . . . . . 42 9. System Process . . . . . . . . . . . . . . . . . . . . . . . 45
10.1. System Process Variables . . . . . . . . . . . . . . . . 42 9.1. System Process Variables . . . . . . . . . . . . . . . . 45
10.2. System Process Operations . . . . . . . . . . . . . . . . 43 9.2. System Process Operations . . . . . . . . . . . . . . . . 47
10.2.1. Selection Algorithm . . . . . . . . . . . . . . . . . 44 9.2.1. Selection Algorithm . . . . . . . . . . . . . . . . . 48
10.2.2. Clustering Algorithm . . . . . . . . . . . . . . . . 46 9.2.2. Clustering Algorithm . . . . . . . . . . . . . . . . 50
10.2.3. Combining Algorithm . . . . . . . . . . . . . . . . . 48 9.2.3. Combining Algorithm . . . . . . . . . . . . . . . . . 52
10.2.4. Clock Discipline Algorithm . . . . . . . . . . . . . 52 9.2.4. Clock Discipline Algorithm . . . . . . . . . . . . . 56
10.3. Clock Adjust Process . . . . . . . . . . . . . . . . . . 60 9.3. Clock Adjust Process . . . . . . . . . . . . . . . . . . 64
11. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 61 10. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 65
11.1. Poll Process Variables and Parameters . . . . . . . . . . 61 10.1. Poll Process Variables and Parameters . . . . . . . . . . 65
11.2. Poll Process Operations . . . . . . . . . . . . . . . . . 62 10.2. Poll Process Operations . . . . . . . . . . . . . . . . . 66
12. Security Considerations . . . . . . . . . . . . . . . . . . . 63 11. Security Considerations . . . . . . . . . . . . . . . . . . . 67
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 63 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67
14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 64 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 68
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 64 14. Informative References . . . . . . . . . . . . . . . . . . . 68
15.1. Normative References . . . . . . . . . . . . . . . . . . 64 Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 68
15.2. Informative References . . . . . . . . . . . . . . . . . 64 A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 69
Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 65 A.1.1. Definitions, Constants, Parameters . . . . . . . . . 69
A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 65 A.1.2. Packet Data Structures . . . . . . . . . . . . . . . 72
A.2. Definitions, Constants, Parameters . . . . . . . . . . . 65 A.1.3. Association Data Structures . . . . . . . . . . . . . 73
A.3. Packet Data Structures . . . . . . . . . . . . . . . . . 69 A.1.4. System Data Structures . . . . . . . . . . . . . . . 76
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 109 A.1.5. Local Clock Data Structures . . . . . . . . . . . . . 77
Intellectual Property and Copyright Statements . . . . . . . . . 110 A.1.6. Function Prototypes . . . . . . . . . . . . . . . . . 77
A.2. Main Program and Utility Routines . . . . . . . . . . . . 78
A.3. Kernel Input/Output Interface . . . . . . . . . . . . . . 82
A.4. Kernel System Clock Interface . . . . . . . . . . . . . . 82
A.5. Peer Process . . . . . . . . . . . . . . . . . . . . . . 84
A.5.1. receive() . . . . . . . . . . . . . . . . . . . . . . 85
A.5.2. packet() . . . . . . . . . . . . . . . . . . . . . . 90
A.5.3. clock_filter() . . . . . . . . . . . . . . . . . . . 92
A.5.4. fast_xmit() . . . . . . . . . . . . . . . . . . . . . 93
A.5.5. access() . . . . . . . . . . . . . . . . . . . . . . 95
A.6. System Process . . . . . . . . . . . . . . . . . . . . . 95
A.6.1. clock_select() . . . . . . . . . . . . . . . . . . . 95
A.6.2. root_dist() . . . . . . . . . . . . . . . . . . . . . 99
A.6.3. accept() . . . . . . . . . . . . . . . . . . . . . . 100
A.6.4. clock_update() . . . . . . . . . . . . . . . . . . . 100
A.6.5. clock_combine() . . . . . . . . . . . . . . . . . . . 103
A.6.6. local_clock() . . . . . . . . . . . . . . . . . . . . 103
A.6.7. rstclock() . . . . . . . . . . . . . . . . . . . . . 109
A.7. Clock Adjust Process . . . . . . . . . . . . . . . . . . 109
A.7.1. clock_adjust() . . . . . . . . . . . . . . . . . . . 109
A.8. Poll Process . . . . . . . . . . . . . . . . . . . . . . 110
A.8.1. poll() . . . . . . . . . . . . . . . . . . . . . . . 110
A.8.2. poll_update() . . . . . . . . . . . . . . . . . . . . 112
A.8.3. peer_xmit() . . . . . . . . . . . . . . . . . . . . . 114
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115
Intellectual Property and Copyright Statements . . . . . . . . . 116
1. Introduction 1. Introduction
This document is a reference and implementation guide for the Network This document specifies the Network Time Protocol Version 4 (NTPv4),
Time Protocol Version 4 (NTPv4), which is widely used to synchronize which is widely used to synchronize the system clocks among a set of
the system clocks among a set of distributed time servers and distributed time servers and clients. This document defines the core
clients. This document defines the core architecture, protocol, architecture, protocol, state machines, data structures and
state machines, data structures and algorithms. This document algorithms. This document describes NTPv4, which introduces new
describes NTPv4, which introduces new functionality to NTPv3 as functionality to NTPv3 as described in [1], and functionality
described in [1], and functionality expanded from that of SNTPv4 as expanded from that of SNTPv4 as described in [2] (SNTPv4 is a subset
described in [2] (SNTPv4 is a subset of NTPv4). This document of NTPv4). This document obsoletes RFC 1305 and RFC 4330. While
obsoletes RFC 1305 and RFC 4330. While certain minor changes have certain minor changes have been made in some protocol header fields,
been made in some protocol header fields, these do not affect the these do not affect the interoperability between NTPv4 and previous
interoperability between NTPv4 and previous versions. versions.
The NTP subnet model includes a number of widely accessible primary The NTP subnet model includes a number of widely accessible primary
time servers synchronized by wire or radio to national standards. time servers synchronized by wire or radio to national standards.
The purpose of the NTP protocol is to convey timekeeping information The purpose of the NTP protocol is to convey timekeeping information
from these primary servers to secondary time servers and clients via from these primary servers to secondary time servers and clients via
both private networks and the public Internet. Crafted algorithms both private networks and the public Internet. Crafted algorithms
mitigate errors that may result from network disruptions, server mitigate errors that may result from network disruptions, server
failures and possible hostile action. Servers and clients are failures and possible hostile action. Servers and clients are
configured such that values flow from the primary servers at the root configured such that values flow from the primary servers at the root
via branching secondary servers toward clients. via branching secondary servers toward clients.
skipping to change at page 4, line 8 skipping to change at page 5, line 8
skeleton program included as an appendix. This program includes data skeleton program included as an appendix. This program includes data
structures and code segments for the core algorithms and in addition structures and code segments for the core algorithms and in addition
the mitigation algorithms used to enhance reliability and accuracy. the mitigation algorithms used to enhance reliability and accuracy.
While the skeleton and other descriptions in this document apply to a While the skeleton and other descriptions in this document apply to a
particular implementation, they are not intended as the only way the particular implementation, they are not intended as the only way the
required functions can be implemented. While the NTPv3 symmetric key required functions can be implemented. While the NTPv3 symmetric key
authentication scheme described in this document carries over from authentication scheme described in this document carries over from
NTPv3, the Autokey public key authentication scheme new to NTPv4 is NTPv3, the Autokey public key authentication scheme new to NTPv4 is
described in [3]. described in [3].
The NTP protocol includes the modes of operation described in Section The NTP protocol includes the modes of operation described in
2 using the data types described in Section 5 and the data structures Section 2 using the data types described in Section 5 and the data
in Section 6. The implementation model described in Section 4 is structures in Section 6. The implementation model described in
based on a multiple-process, threaded architecture, although other Section 4 is based on a multiple-process, threaded architecture,
architectures could be used as well. The on-wire protocol described although other architectures could be used as well. The on-wire
in Section 7 is based on a returnable-time design which depends only protocol described in Section 7 is based on a returnable-time design
on measured clock offsets, but does not require reliable message which depends only on measured clock offsets, but does not require
delivery. The synchronization subnet is a self-organizing, reliable message delivery. The synchronization subnet is a self-
hierarchical, master-slave network with synchronization paths organizing, hierarchical, master-slave network with synchronization
determined by a shortest-path spanning tree and defined metric. paths determined by a shortest-path spanning tree and defined metric.
While multiple masters (primary servers) may exist, there is no While multiple masters (primary servers) may exist, there is no
requirement for an election protocol. requirement for an election protocol.
The remaining sections of this document define the data structures The remaining sections of this document define the data structures
and algorithms suitable for a fully featured NTPv4 implementation. and algorithms suitable for a fully featured NTPv4 implementation.
Appendix A contains the code skeleton with definitions, structures Appendix A contains the code skeleton with definitions, structures
and code segments that represent the basic structure of the reference and code segments that represent the basic structure of the reference
implementation. implementation.
The remainder of this document contains numerous variables and The remainder of this document contains numerous variables and
skipping to change at page 6, line 39 skipping to change at page 7, line 39
Drawing from the experience of the telephone industry, which learned Drawing from the experience of the telephone industry, which learned
such lessons at considerable cost, the subnet topology should be such lessons at considerable cost, the subnet topology should be
organized to produce the lowest synchronization distances, but must organized to produce the lowest synchronization distances, but must
never be allowed to form a loop. In NTP the subnet topology is never be allowed to form a loop. In NTP the subnet topology is
determined using a variant of the Bellman-Ford distributed routing determined using a variant of the Bellman-Ford distributed routing
algorithm, which computes the shortest-distance spanning tree rooted algorithm, which computes the shortest-distance spanning tree rooted
on the primary servers. As a result of this design, the algorithm on the primary servers. As a result of this design, the algorithm
automatically reorganizes the subnet to produce the most accurate and automatically reorganizes the subnet to produce the most accurate and
reliable time, even when one or more primary or secondary servers or reliable time, even when one or more primary or secondary servers or
the network paths. the network paths fail.
3. Definitions 3. Definitions
A number of terms used throughout this document have a precise A number of terms used throughout this document have a precise
technical definition. A timescale is a frame of reference where time technical definition. A timescale is a frame of reference where time
is expressed as the value of a monotonic-increasing binary counter is expressed as the value of a monotonic-increasing binary counter
with an indefinite number of bits. It counts in seconds and fraction with an indefinite number of bits. It counts in seconds and fraction
with the decimal point somewhere in the middle. The Coordinated with the decimal point somewhere in the middle. The Coordinated
Universal Time (UTC) timescale represents mean solar time as Universal Time (UTC) timescale represents mean solar time as
disseminated by national standards laboratories. The system time is disseminated by national standards laboratories. The system time is
skipping to change at page 7, line 38 skipping to change at page 8, line 38
While the D(t) term is important when characterizing precision While the D(t) term is important when characterizing precision
oscillators, it is ordinarily neglected for computer oscillators. In oscillators, it is ordinarily neglected for computer oscillators. In
this document all time values are in seconds (s) and all frequency this document all time values are in seconds (s) and all frequency
values are in seconds-per-second (s/s). It is sometimes convenient values are in seconds-per-second (s/s). It is sometimes convenient
to express frequency offsets in parts-per-million (PPM), where 1 PPM to express frequency offsets in parts-per-million (PPM), where 1 PPM
is equal to 1*10^(-6) seconds. is equal to 1*10^(-6) seconds.
It is important in computer timekeeping applications to assess the It is important in computer timekeeping applications to assess the
performance of the timekeeping function. The NTP performance model performance of the timekeeping function. The NTP performance model
includes four statistics which are updated each time a client makes a includes four statistics which are updated each time a client makes a
measurement with a server. The offset theta represents the maximum measurement with a server. The offset theta represents the maximum-
likelihood time offset of the server clock relative to the system likelihood time offset of the server clock relative to the system
clock. The delay del represents the roundtrip delay between the clock. The delay del represents the roundtrip delay between the
client and server. The dispersion epsilon represents the maximum client and server. The dispersion epsilon represents the maximum
error inherent in the measurement. It increases at a rate equal to error inherent in the measurement. It increases at a rate equal to
the maximum disciplined system clock frequency tolerance phi, the maximum disciplined system clock frequency tolerance phi,
typically 15 PPM. The jitter varphi, defined as the root-mean-square typically 15 PPM. The jitter psi, defined as the root-mean-square
(RMS) average of the most recent time offset differences, represents (RMS) average of the most recent time offset differences, represents
the nominal error in estimating theta. the nominal error in estimating theta.
While the theta, del, epsilon, and psi statistics represent While the theta, del, epsilon, and psi statistics represent
measurements of the system clock relative to the each server clock measurements of the system clock relative to the each server clock
separately, the NTP protocol includes mechanisms to combine the separately, the NTP protocol includes mechanisms to combine the
statistics of several servers to more accurately discipline and statistics of several servers to more accurately discipline and
calibrate the system clock. The system offset captheta represents calibrate the system clock. The system offset captheta represents
the maximum-likelihood offset estimate for the server population. the maximum-likelihood offset estimate for the server population.
The system jitter vartheta represents the nominal error in estimating The system jitter, defined as vartheta, represents the nominal error
captheta. The del and epsilon statistics are accumulated at each in estimating captheta. The del and epsilon statistics are
stratum level from the reference clocks to produce the root delay accumulated at each stratum level from the reference clocks to
delta and root dispersion E statistics. The synchronization distance produce the root delay delta and root dispersion capepsilon
gamma=E+delta/2 represents the maximum error due all causes. The statistics. The synchronization distance gamma=capepsilon+delta/2
detailed formulations of these statistics are given later in this represents the maximum error due all causes. The detailed
document. They are available to the dependent applications in order formulations of these statistics are given later in this document.
to assess the performance of the synchronization function. They are available to the dependent applications in order to assess
the performance of the synchronization function.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Strat | Poll | Prec | |LI | VN |Mode | Strat | Poll | Prec |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay | | Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion | | Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 9, line 50 skipping to change at page 10, line 50
. . . .
. Authentication . . Authentication .
. (Optional) (160 bits) . . (Optional) (160 bits) .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: NTPv4 Message Format Figure 1: NTPv4 Message Format
4. Implementation Model 4. Implementation Model
Figure 1 shows two processes dedicated to each server, a peer process Figure 2 shows two processes dedicated to each server, a peer process
to receive messages from the server or reference clock and a poll to receive messages from the server or reference clock and a poll
process to transmit messages to the server or reference clock. . process to transmit messages to the server or reference clock. .
.......................................................... ..........................................................
. Remote .. Peer/Poll .. System . . Remote .. Peer/Poll .. System .
. Servers .. Processes .. Process . . Servers .. Processes .. Process .
. .. .. . . .. .. .
.----------..-------------..-------------- . .----------..-------------..-------------- .
.| |->| |..| | . .| |->| |..| | .
.|Server 1|..|Peer/Poll 1|->| | . .|Server 1|..|Peer/Poll 1|->| | .
skipping to change at page 10, line 41 skipping to change at page 11, line 41
| | | |
| \|/ | \|/
| ............... | ...............
| . /-----\ . | . /-----\ .
'----------------------------------<-| VFO |-<-. '----------------------------------<-| VFO |-<-.
. \-----/ . . \-----/ .
. Clock Adjust. . Clock Adjust.
. Process . . Process .
............... ...............
Figure 1 NTPv4 Algorithm Interactions
Figure 2: NTPv4 Algorithm Interactions Figure 2: NTPv4 Algorithm Interactions
These processes operate on a common data structure called an These processes operate on a common data structure called an
association, which contains the statistics described above along with association, which contains the statistics described above along with
various other data described later. A client sends an NTP packet to various other data described later. A client sends an NTP packet to
one or more servers and processes the replies as received. The one or more servers and processes the replies as received. The
server interchanges addresses and ports, overwrites certain fields in server interchanges addresses and ports, overwrites certain fields in
the packet and returns it immediately (client/ server mode) or at the packet and returns it immediately (client/ server mode) or at
some time later (symmetric modes). As each NTP message is received, some time later (symmetric modes). As each NTP message is received,
the offset theta between the peer clock and the system clock is the offset theta between the peer clock and the system clock is
computed along with the associated statistics del, epsilon, and computed along with the associated statistics del, epsilon, and psi.
varphi.
The system process includes the selection, clustering and combining The system process includes the selection, clustering and combining
algorithms which mitigate among the various servers and reference algorithms which mitigate among the various servers and reference
clocks to determine the most accurate and reliable candidates to clocks to determine the most accurate and reliable candidates to
synchronize the system clock. The selection algorithm uses Byzantine synchronize the system clock. The selection algorithm uses Byzantine
principles to remote the falsetickers from the incident population, principles to discard the falsetickers from the incident population,
leaving only truechimers. A 'truechimer' is a clock that maintains leaving only truechimers. A 'truechimer' is a clock that maintains
timekeeping accuracy to a previously published (and trusted) timekeeping accuracy to a previously published (and trusted)
standard, while a 'falseticker' is a clock that does not maintain standard, while a 'falseticker' is a clock that does not maintain
that level of timekeeping accuracy. The clustering algorithm uses that level of timekeeping accuracy. The clustering algorithm uses
statistical principles to sift the most accurate truechimers leaving statistical principles to sift the most accurate truechimers leaving
the survivors as result. The combining algorithm develops the final the survivors as result. The combining algorithm develops the final
clock offset as a statistical average of the survivors. clock offset as a statistical average of the survivors.
The clock discipline process, which is actually part of the system The clock discipline process, which is actually part of the system
process, includes engineered algorithms to control the time and process, includes engineered algorithms to control the time and
skipping to change at page 11, line 36 skipping to change at page 12, line 34
the clock discipline process is the clock adjust process, which runs the clock discipline process is the clock adjust process, which runs
once each second to inject a computed time offset and maintain once each second to inject a computed time offset and maintain
constant frequency. The RMS average of past time offset differences constant frequency. The RMS average of past time offset differences
represents the nominal error or system jitter vartheta. The RMS represents the nominal error or system jitter vartheta. The RMS
average of past frequency offset differences represents the average of past frequency offset differences represents the
oscillator frequency stability or frequency wander cappsi. oscillator frequency stability or frequency wander cappsi.
A client sends messages to each server with a poll interval of 2^tau A client sends messages to each server with a poll interval of 2^tau
seconds, as determined by the poll exponent tau. In NTPv4 tau ranges seconds, as determined by the poll exponent tau. In NTPv4 tau ranges
from 4 (16 s) through 17 (36 h). The value of tau is determined by from 4 (16 s) through 17 (36 h). The value of tau is determined by
the clock discipline algorithm to match the loop time constant T_c = the clock discipline algorithm to match the loop time constant
2^tau. A server responds with messages at an update interval of mu T_c=2^tau. A server responds with messages at an update interval of
seconds. For stateless servers, mu = T_c, since the server responds mu seconds. For stateless servers, mu=T_c, since the server responds
immediately. However, in symmetric modes each of two peers manages immediately. However, in symmetric modes each of two peers manages
the time constant as a function of current system offset and system the time constant as a function of current system offset and system
jitter, so may not agree with the same tau. It is important that the jitter, so may not agree with the same tau. It is important that the
dynamic behavior of the clock discipline algorithms be carefully dynamic behavior of the clock discipline algorithms be carefully
controlled in order to maintain stability in the NTP subnet at large. controlled in order to maintain stability in the NTP subnet at large.
This requires that the peers agree on a common tau equal to the This requires that the peers agree on a common tau equal to the
minimum poll exponent of both peers. The NTP protocol includes minimum poll exponent of both peers. The NTP protocol includes
provisions to properly negotiate this value. provisions to properly negotiate this value.
While not shown in the figure, the implementation model includes some While not shown in the figure, the implementation model includes some
means to set and adjust the system clock. The operating system is means to set and adjust the system clock. The operating system is
assumed to provide two functions, one to set the time directly, for assumed to provide two functions, one to set the time directly, for
example the Unix settimeofday() function, and another to adjust the example the Unix settimeofday() function, and another to adjust the
time in small increments advancing or retarding the time by a time in small increments advancing or retarding the time by a
designated amount, for example the Unix adjtime()1 function designated amount, for example the Unix adjtime() function
(parentheses following a name indicate reference to a function rather (parentheses following a name indicate reference to a function rather
than a simple variable). In the intended design the clock discipline than a simple variable). In the intended design the clock discipline
process uses the adjtime() function if the adjustment is less than a process uses the adjtime() function if the adjustment is less than a
designated threshold, and the settimeofday() function if above the designated threshold, and the settimeofday() function if above the
threshold. The manner in which this is done and the value of the threshold. The manner in which this is done and the value of the
threshold is described later. threshold is described later.
5. Data Types 5. Data Types
All NTP time values are represented in twos-complement format, with All NTP time values are represented in twos-complement format, with
skipping to change at page 14, line 10 skipping to change at page 15, line 10
is convenient to assume it has existed for all eternity, even if all is convenient to assume it has existed for all eternity, even if all
knowledge of historic leap seconds has been lost. Dates are relative knowledge of historic leap seconds has been lost. Dates are relative
to the prime epoch; values greater than zero represent times after to the prime epoch; values greater than zero represent times after
that date; values less than zero represent times before it. that date; values less than zero represent times before it.
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. Table 2 shows a number of historic NTP dates
together with their corresponding Modified Julian Day (MJD), NTP era together with their corresponding Modified Julian Day (MJD), NTP era
and NTP timestamp. and NTP timestamp.
Year MJD NTP Era NTP Timestamp Epoch
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 0 -678,491 -14 171,311,744 1 BCE
1 Jan 1 -678,575 -14 202,939,144 1 CE
4 Oct 1582 -100,851 -3 2,873,647,488 Last day Julian
15 Oct 1582 -100,840 -3 2,874,597,888 1st day Gregorian
31 Dec 1899 15019 -1 4,294,880,896 Last d NTPEra-1
1 Jan 1900 15020 0 0 First d NTPEra0
1 Jan 1970 40,587 0 2,208,988,800 First day UNIX
1 Jan 1972 41,317 0 2,272,060,800 First day UTC
31 Dec 1999 51,543 0 3,155,587,200 Last d 20th Cent
8 Feb 2036 64,731 1 63,104 1st day NTPEra1
Figure 4: Interesting Historic NTP Dates +-------------+------------+-----+---------------+------------------+
| Year | MJD | NTP | NTP Timestamp | Epoch |
| | | Era | | |
+-------------+------------+-----+---------------+------------------+
| 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 0 | -678,491 | -14 | 171,311,744 | 1 BCE |
| 1 Jan 1 | -678,575 | -14 | 202,939,144 | 1 CE |
| 4 Oct 1582 | -100,851 | -3 | 2,873,647,488 | Last day Julian |
| 15 Oct 1582 | -100,840 | -3 | 2,874,597,888 | First day |
| | | | | Gregorian |
| 31 Dec 1899 | 15019 | -1 | 4,294,880,896 | Last day NTP Era |
| | | | | -1 |
| 1 Jan 1900 | 15020 | 0 | 0 | First day NTP |
| | | | | Era 0 |
| 1 Jan 1970 | 40,587 | 0 | 2,208,988,800 | First day UNIX |
| 1 Jan 1972 | 41,317 | 0 | 2,272,060,800 | First day UTC |
| 31 Dec 1999 | 51,543 | 0 | 3,155,587,200 | Last day 20th |
| | | | | Century |
| 8 Feb 2036 | 64,731 | 1 | 63,104 | First day NTP |
| | | | | Era 1 |
+-------------+------------+-----+---------------+------------------+
Table 2: 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 2p, in seconds. In order to minimize clock resolution is defined 2^(-p), in seconds. In order to minimize
bias and help make timestamps unpredictable to an intruder, the non- bias and help make timestamps unpredictable to an intruder, the non-
significant bits should be set to an unbiased random bit string. The significant bits should be set to an unbiased random bit string. The
clock precision is defined as the running time to read the system clock precision is defined as the running time to read the system
clock, in seconds. Note that the precision defined in this way can clock, in seconds. Note that the precision defined in this way can
be larger or smaller than the resolution. The term rho, representing be larger or smaller than the resolution. The term rho, representing
the precision used in this document, is the larger of the two. the precision used in this document, is the larger of the two.
The only operation permitted with dates and timestamps is twos- The only operation permitted with dates and timestamps is twos-
complement subtraction, yielding a 127-bit or 63-bit signed result. complement subtraction, yielding a 127-bit or 63-bit signed result.
It is critical that the first-order differences between two dates It is critical that the first-order differences between two dates
skipping to change at page 16, line 8 skipping to change at page 17, line 17
The NTP protocol state machines described in following sections are The NTP protocol state machines described in following sections are
defined using state variables and flow chart fragments. State defined using state variables and flow chart fragments. State
variables are separated into classes according to their function in variables are separated into classes according to their function in
packet headers, peer and poll processes, the system process and the packet headers, peer and poll processes, the system process and the
clock discipline process. Packet variables represent the NTP header clock discipline process. Packet variables represent the NTP header
values in transmitted and received packets. Peer and poll variables values in transmitted and received packets. Peer and poll variables
represent the contents of the association for each server separately. represent the contents of the association for each server separately.
System variables represent the state of the server as seen by its System variables represent the state of the server as seen by its
dependent clients. Clock discipline variables represent the internal dependent clients. Clock discipline variables represent the internal
workings of the clock discipline algorithm. Additional constant and workings of the clock discipline algorithm. Additional constant and
variable classes are defined in Appendix A.. variable classes are defined in Appendix A.
6.1. Structure Conventions 6.1. Structure Conventions
In order to distinguish between different variables of the same name In order to distinguish between different variables of the same name
but used in different processes, the naming convention summarized in but used in different processes, the naming convention summarized in
Table 2 is employed. A receive packet variable v is a member of the Table 3 is employed. A receive packet variable v is a member of the
packet structure r with fully qualified name r.v. In a similar packet structure r with fully qualified name r.v. In a similar
manner x.v is a transmit packet variable, p.v is a peer variable, s.v manner x.v is a transmit packet variable, p.v is a peer variable, s.v
is a system variable and c.v is a clock discipline variable. There is a system variable and c.v is a clock discipline variable. There
is a set of peer variables for each association; there is only one is a set of peer variables for each association; there is only one
set of system and clock variables. Most flow chart fragments begin set of system and clock variables. Most flow chart fragments begin
with a statement label and end with a named go-to or exit. A with a statement label and end with a named go-to or exit. A
subroutine call includes a dummy () following the name and return at subroutine call includes a dummy () following the name and return at
the end.to the point following the call. the end to the point following the call.
+------+---------------------------------+ +------+---------------------------------+
| Name | Description | | Name | Description |
+------+---------------------------------+ +------+---------------------------------+
| r. | receive packet header variable | | r. | receive packet header variable |
| x. | transmit packet header variable | | x. | transmit packet header variable |
| p. | peer/poll variable | | p. | peer/poll variable |
| s. | system variable | | s. | system variable |
| c. | clock discipline variable | | c. | clock discipline variable |
+------+---------------------------------+ +------+---------------------------------+
Table 2: Name Prefix Conventions Table 3: Name Prefix Conventions
6.2. Global Parameters 6.2. Global Parameters
In addition to the variable classes a number of global parameters are In addition to the variable classes a number of global parameters are
defined in this document, including those shown with values in defined in this document, including those shown with values in
Figure 5 Table 4.
Name Value Description
PORT 123 NTP port number
VERSION 4 version number
TOLERANCE 15e-6 frequency tolerance (s/s)
MINPOLL 4 minimum poll exponent (16 s)
MAXPOLL 17 maximum poll exponent (36 h)
MAXDISP 16 maximum dispersion (s)
MINDISP .005 minimum dispersion increment (s)
MAXDIST 1 distance threshold (s)
MAXSTRAT 16 maximum stratum number
Figure 5: Global Parameters +-----------+-------+----------------------------------+
| Name | Value | Description |
+-----------+-------+----------------------------------+
| PORT | 123 | NTP port number |
| VERSION | 4 | version number |
| TOLERANCE | 15e-6 | frequency tolerance (s/s) |
| MINPOLL | 4 | minimum poll exponent (16 s) |
| MAXPOLL | 17 | maximum poll exponent (36 h) |
| MAXDISP | 16 | maximum dispersion (s) |
| MINDISP | .005 | minimum dispersion increment (s) |
| MAXDIST | 1 | distance threshold (s) |
| MAXSTRAT | 16 | maximum stratum number |
+-----------+-------+----------------------------------+
. While these are the only parameters needed in this document, a Table 4: Global Parameters
larger collection is necessary in the skeleton and larger still for
any implementation. Section B.1 contains those used by the skeleton While these are the only parameters needed in this document, a larger
collection is necessary in the skeleton and larger still for any
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 related
implementation-dependent functions. Some of these parameter values implementation-dependent functions. Some of these parameter values
are cast in stone, like the NTP port number assigned by the IANA and are cast in stone, like the NTP port number assigned by the IANA and
the version number assigned NTPv4 itself. Others like the frequency the version number assigned NTPv4 itself. Others like the frequency
tolerance, involve an assumption about the worst case behavior of a tolerance, involve an assumption about the worst case behavior of a
system clock once synchronized and then allowed to drift when its system clock once synchronized and then allowed to drift when its
sources have become unreachable. The minimum and maximum parameters sources have become unreachable. The minimum and maximum parameters
define the limits of state variables as described in later sections. define the limits of state variables as described in later sections.
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.
Name Formula Description 6.3. Packet Header Variables
leap leap leap indicator (LI)
version version version number (VN)
mode mode mode
stratum stratum stratum
poll poll poll exponent
precision rho precision exponent
rootdelay delta root delay
rootdisp E root dispersion
refid refid reference ID
reftime reftime reference timestamp
org T1 origin timestamp
rec T2 receive timestamp
xmt T3 transmit timestamp
dst T4 destination timestamp
keyid keyid key ID
digest digest message digest
Figure 6: Packet Header Variables +-----------+------------+-----------------------+
| Name | Formula | Description |
+-----------+------------+-----------------------+
| leap | leap | leap indicator (LI) |
| version | version | version number (VN) |
| mode | mode | mode |
| stratum | stratum | stratum |
| poll | poll | poll exponent |
| precision | rho | precision exponent |
| rootdelay | delta | root delay |
| rootdisp | capepsilon | root dispersion |
| refid | refid | reference ID |
| reftime | reftime | reference timestamp |
| org | T1 | origin timestamp |
| rec | T2 | receive timestamp |
| xmt | T3 | transmit timestamp |
| dst | T4 | destination timestamp |
| keyid | keyid | key ID |
| digest | digest | message digest |
+-----------+------------+-----------------------+
6.3. Packet Header Variables Table 5: 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 below. The NTP packet consists the packet header variables described below. The NTP packet consists
of a number of 32-bit (4 octet) words in network byte order. The of a number of 32-bit (4 octet) words in network byte order. The
packet format consists of three components, the header itself, one or packet format consists of three components, the header itself, one or
more optional extension fields and an optional message authentication more optional extension fields and an optional message authentication
code (MAC). The header component is identical to the NTPv3 header code (MAC). The header component is identical to the NTPv3 header
and previous versions. The optional extension fields are used by the and previous versions. The optional extension fields are used by the
Autokey public key cryptographic algorithms described in [3]. The Autokey public key cryptographic algorithms described in [3]. The
optional MAC is used by both Autokey and the symmetric key optional MAC is used by both Autokey and the symmetric key
cryptographic algorithms described in the main body of this report. cryptographic algorithms described in the main body of this report.
The NTP packet header follows the UDP and IP headers and the physical The NTP packet header follows the UDP and IP headers and the physical
header specific to the underlying transport network. It consists of header specific to the underlying transport network. It consists of
a number of 32-bit (4-octet) words, although some fields use multiple a number of 32-bit (4-octet) words, although some fields use multiple
words and others are packed in smaller fields within a word. The NTP words and others are packed in smaller fields within a word. The NTP
packet header shown in Appendix A has 12 words followed by optional packet header shown in Figure 4 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 and message digest fields. (MAC) consisting of the key identifier and message digest fields.
The optional extension fields described in this section are used by The optional extension fields described in this section are used by
the Autokey security protocol [3], which is not described here. The the Autokey security protocol [3], which is not described here. The
MAC is used by both Autokey and the symmetric key authentication MAC is used by both Autokey and the symmetric key authentication
scheme described in Appendix A. As is the convention in other scheme described in Appendix A. As is the convention in other
Internet protocols, all fields are in network byte order, commonly Internet protocols, all fields are in network byte order, commonly
called big-endian. called big-endian.
A list of the packet header variables is shown in Figure 6 and A list of the packet header variables is shown in Table 5 and
described in detail below. The packet header fields apply to both described in detail below. The packet header fields apply to both
transmitted (x prefix) and received packets (r prefix). The NTP transmitted (x prefix) and received packets (r prefix). The NTP
header is shown in Figure 7 header is shown in Figure 4 , where the size of some multiple-word
fields is shown in bits if not the default 32 bits. The header
extends from the beginning of the packet to the end of the Transmit
Timestamp field. When using the IPv4 address family these fields are
backwards compatible with NTPv3. When using the IPv6 address family
on an NTPv4 server with a NTPv3 client, the Reference Identifier
field appears to be a random value and a timing loop might not be
detected. The message authentication code (MAC) consists of a 32-bit
Key Identifier followed by a 128bit Message Digest. The message
digest, or cryptosum, is calculated as in [6] over all header and
optional extension fields.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Strat | Poll | Prec | |LI | VN |Mode | Strat | Poll | Prec |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay | | Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion | | Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 19, line 51 skipping to change at page 21, line 46
| | | |
+ Extension Field 2 (Optional) + + Extension Field 2 (Optional) +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . .
. Authentication . . Authentication .
. (Optional) (160 bits) . . (Optional) (160 bits) .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: NTPv4 Message Format Figure 4: NTPv4 Message Format
, where the size of some multiple-word fields is shown in bits if not
the default 32 bits. The header extends from the beginning of the
packet to the end of the Transmit Timestamp field. The
interpretation of the header fields is shown in the main body of this
report. When using the IPv4 address family these fields are
backwards compatible with NTPv3. When using the IPv6 address family
on an NTPv4 server with a NTPv3 client, the Reference Identifier
field appears to be a random value and a timing loop might not be
detected. The message authentication code (MAC) consists of a 32-bit
Key Identifier followed by a 128bit Message Digest. The message
digest, or cryptosum, is calculated as in [6] over all header and
optional extension fields.
The variables are interpreted as follows: The variables are interpreted as follows:
leap: 2-bit integer warning of an impending leap second to be leap: 2-bit integer warning of an impending leap second to be
inserted or deleted in the last minute of the current month, inserted or deleted in the last minute of the current month, coded as
coded as follows: follows:
0 no warning +-------+-------------------------------------------------+
1 last minute of the day has 61 seconds | Value | Meaning |
2 last minute of the day has 59 seconds +-------+-------------------------------------------------+
3 alarm condition (the clock is not synchronized) | 0 | no warning |
| 1 | last minute of the day has 61 seconds |
| 2 | last minute of the day has 59 seconds |
| 3 | alarm condition (the clock is not synchronized) |
+-------+-------------------------------------------------+
version: Table 6: Leap Indicator
3-bit integer representing the NTP version number, currently 4.
mode: 3-bit integer representing the mode, with values defined version: 3-bit integer representing the NTP version number, currently
as follows: 4.
0 reserved mode: 3-bit integer representing the mode, with values defined as
1 symmetric active follows:
2 symmetric passive
3 client
4 server
5 broadcast
6 NTP control message
7 reserved for private use
stratum: 8-bit integer representing the stratum, with values +-------+--------------------------+
defined as follows: | Value | Meaning |
+-------+--------------------------+
| 0 | reserved |
| 1 | symmetric active |
| 2 | symmetric passive |
| 3 | client |
| 4 | server |
| 5 | broadcast |
| 6 | NTP control message |
| 7 | reserved for private use |
+-------+--------------------------+
0 unspecified or invalid Table 7: Mode
1 primary server (e.g., equipped with a GPS receiver)
2-15 secondary server (via NTP) stratum: 8-bit integer representing the stratum, with values defined
16 client-only as follows:
17-255 undefined
+--------+-----------------------------------------------------+
| Value | Meaning |
+--------+-----------------------------------------------------+
| 0 | unspecified or invalid |
| 1 | primary server (e.g., equipped with a GPS receiver) |
| 2-15 | secondary server (via NTP) |
| 16 | client-only |
| 17-255 | undefined |
+--------+-----------------------------------------------------+
Table 8: 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 MAXSTRAT (16) in the peer variable p.stratum and to map p.stratum
p.stratum values of MAXSTRAT or greater to 0 in transmitted values of MAXSTRAT or greater to 0 in transmitted packets. This
packets. This allows reference clocks, which normally appear at allows reference clocks, which normally appear at stratum 0, to be
stratum 0, to be conveniently mitigated using the same algorithms conveniently mitigated using the same algorithms used for external
used for external sources. sources.
poll: 8-bit signed integer representing the maximum interval poll: 8-bit signed integer representing the maximum interval between
between successive messages, in log2 seconds. Suggested default successive messages, in log2 seconds. Suggested default limits for
limits for minimum and maximum poll intervals are 6 and 10, ' minimum and maximum poll intervals are 6 and 10, respectively.
respectively.
precision: 8-bit signed integer representing the precision of precision: 8-bit signed integer representing the precision of the
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 corresponds to a precision of about one microsecond. The precision
precision can be determined when the service first starts up as can be determined when the service first starts up as the minimum
the minimum time of several iterations to read the system clock. time of several iterations to read the system clock.
rootdelay: Total roundtrip delay to the reference clock, in NTP rootdelay: Total roundtrip delay to the reference clock, in NTP short
short format. format.
rootdisp: Total dispersion to the reference clock, in NTP short rootdisp: Total dispersion to the reference clock, in NTP short
format. format.
refid: 32-bit code identifying the particular server or refid: 32-bit code identifying the particular server or reference
referenceclock. The interpretation depends on the value in the clock. The interpretation depends on the value in the stratum field.
stratum field. For packet stratum 0 (unspecified or invalid) For packet stratum 0 (unspecified or invalid) this is a four-
this is a four-character ASCII string, called the kiss code, character ASCII string, called the kiss code, used for debugging and
used for debugging and monitoring purposes. For stratum 1 monitoring purposes. For stratum 1 (reference clock) this is a four-
(reference clock) this is a four-octet, left-justified, octet, left-justified, zero-padded ASCII string assigned to the
zero-padded ASCII string assigned to the radio clock. While not reference clock. While not specifically enumerated in this document,
specifically enumerated in this document, the following have the following have been used as ASCII identifiers:
been used as ASCII identifiers:
GOES Geosynchronous Orbit Environment Satellite +------+----------------------------------------------------------+
GPS Global Position System | ID | Clock Source |
PPS Generic pulse-per-second +------+----------------------------------------------------------+
IRIG Inter-Range Instrumentation Group | GOES | Geosynchronous Orbit Environment Satellite |
WWVB LF Radio WWVB Ft. Collins, CO 60 kHz | GPS | Global Position System |
DCF LF Radio DCF77 Mainflingen, DE 77.5 kHz | GAL | Galileo Positioning System |
HBG LF Radio HBG Prangins, HB 75 kHz | PPS | Generic pulse-per-second |
MSF LF Radio MSF Rugby, UK 60 kHz | IRIG | Inter-Range Instrumentation Group |
JJY LF Radio JJY Fukushima, JP 40 kHz, Saga, JP 60 kHz | WWVB | LF Radio WWVB Ft. Collins, CO 60 kHz |
LORC MF Radio LORAN C 100 kHz | DCF | LF Radio DCF77 Mainflingen, DE 77.5 kHz |
TDF MF Radio Allouis, FR 162 kHz | HBG | LF Radio HBG Prangins, HB 75 kHz |
CHU HF Radio CHU Ottawa, Ontario | MSF | LF Radio MSF Anthorn, UK 60 kHz (Rugby until April 2007) |
WWV HF Radio WWV Ft. Collins, CO | JJY | LF Radio JJY Fukushima, JP 40 kHz, Saga, JP 60 kHz |
WWVH HF Radio WWVH Kaui, HI | LORC | MF Radio LORAN C 100 kHz |
NIST NIST telephone modem | TDF | MF Radio Allouis, FR 162 kHz |
USNO USNO telephone modem | CHU | HF Radio CHU Ottawa, Ontario |
PTB etc. European telephone modem | WWV | HF Radio WWV Ft. Collins, CO |
| WWVH | HF Radio WWVH Kauai, HI |
| NIST | NIST telephone modem |
| ACTS | NIST telephone modem |
| USNO | USNO telephone modem |
| PTB | European telephone modem |
+------+----------------------------------------------------------+
Above stratum 1 (secondary servers and clients) this is the Table 9: Reference IDs
reference identifier of the server. If using the IPv4 address
family, the identifier is the four-octet IPv4 address. If using
the IPv6 address family, it is the first four octets of the MD5
hash of the IPv6 address.
reftime: Time when the system clock was last set or corrected, Above stratum 1 (secondary servers and clients) this is the reference
in NTP timestamp format. identifier of the server. If using the IPv4 address family, the
identifier is the four-octet IPv4 address. If using the IPv6 address
family, it is the first four octets of the MD5 hash of the IPv6
address.
org: Time at the client when the request departed for the reftime: Time when the system clock was last set or corrected, in NTP
server, in NTP timestamp format. timestamp format.
rec: Time at the server when the request arrived from the org: Time at the client when the request departed for the server, in
client, in NTP timestamp format. NTP timestamp format.
xmt: Time at the server when the response left for the rec: Time at the server when the request arrived from the client, in
client, in NTP timestamp format. NTP timestamp format.
dst: Time at the client when the reply arrived from the xmt: Time at the server when the response left for the client, in NTP
server, in NTP timestamp format. Note: This value is not timestamp format.
included in a header field; it is determined upon arrival
of the packet and made available in the packet buffer data dst: Time at the client when the reply arrived from the server, in
structure. NTP timestamp format. Note: This value is not included in a header
field; it is determined upon arrival of the packet and made available
in the packet buffer data structure.
keyid: 32-bit unsigned integer used by the client and server to keyid: 32-bit unsigned integer used by the client and server to
designate a secret 128-bit MD5 key. Together, the keyid and designate a secret 128-bit MD5 key. Together, the keyid and digest
digest fields collectively are called message authentication fields collectively are called message authentication code (MAC).
code (MAC).
digest: 128-bit bitstring computed by the keyed MD5 message digest: 128-bit bitstring computed by the keyed MD5 message digest
digest algorithm described in Appendix A. algorithm described in Appendix A.
6.3.1. The Kiss-o'-Death Packet 6.3.1. The Kiss-o'-Death Packet
If the Stratum field is 0, which is an 'unspecified' Stratum field If the Stratum field is 0, which is an 'unspecified' Stratum field
value, the Reference Identifier field can be used to convey messages value, the Reference Identifier field can be used to convey messages
useful for status reporting and access control. In NTPv4 and SNTPv4, useful for status reporting and access control. In NTPv4 and SNTPv4,
packets of this kind are called Kiss-o'-Death (KoD) packets and the packets of this kind are called Kiss-o'-Death (KoD) packets and the
ASCII messages they convey are called kiss codes. The KoD packets ASCII messages they convey are called kiss codes. The KoD packets
got their name because an early use was to tell clients to stop got their name because an early use was to tell clients to stop
sending packets that violate server access controls. The kiss codes sending packets that violate server access controls. The kiss codes
skipping to change at page 23, line 29 skipping to change at page 25, line 50
| 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 9: Currently-defined NTP Kiss Codes Table 10: Currently-defined NTP Kiss Codes
6.3.2. NTP Extension Field Format 6.3.2. NTP Extension Field Format
In NTPv4 one or more extension fields can be inserted after the In NTPv4 one or more extension fields can be inserted after the
header and before the MAC, which is always present when extension header and before the MAC, which is always present when extension
fields are present. The extension fields can occur in any order; fields are present. The extension fields can occur in any order;
however, in some cases there is a preferred order which improves the however, in some cases there is a preferred order which improves the
protocol efficiency. protocol efficiency.
An extension field contains a request or response message in the An extension field contains a request or response message in the
format shown in Figure 10 format shown in Figure 5.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Field Type | Length | | Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID | | Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp | | Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp | | Filestamp |
skipping to change at page 24, line 30 skipping to change at page 26, line 41
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature Length | | Signature Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . .
. Signature . . Signature .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Padding (as needed) | | Padding (as needed) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 10: NTP Extension Field Format Figure 5: NTP Extension Field Format
. All extension fields are zero-padded to a word (4 octets) All extension fields are zero-padded to a word (4 octets) boundary.
boundary. The Length field covers the entire extension field, The Length field covers the entire extension field, including the
including the Length and Padding fields. While the minimum field Length and Padding fields. While the minimum field length is 4 words
length is 4 words (16 octets), a maximum field length remains to be (16 octets), a maximum field length remains to be established.
established.
The RE, VN, and Code fields together form a Field Type field, a 16- The RE, VN, and Code fields together form a Field Type field, a 16-
bit integer which indicates the type of extension message contained bit integer which indicates the type of extension message contained
within the extension field. within the extension field.
The Length field is a 16-bit integer indicates the length of the The Length field is a 16-bit integer which indicates the length of
entire extension field in octets, including the Length and Padding the entire extension field in octets, including the Length and
fields. Padding fields.
The 32-bit Association ID field is set by clients to the value The 32-bit Association ID field is set by clients to the value
previously received from the server or 0 otherwise. The server sets previously received from the server or 0 otherwise. The server sets
the Association ID field when sending a response as a handle for the Association ID field when sending a response as a handle for
subsequent exchanges. If the association ID value in a request does subsequent exchanges. If the association ID value in a request does
not match the association ID of any association, the server returns not match the association ID of any association, the server returns
the request with the first two bits of the Field Type field set to 1. the request with the first two bits of the Field Type field set to 1.
The Timestamp and Filestamp 32-bit fields carry the seconds field of The Timestamp and Filestamp 32-bit fields carry the seconds field of
an NTP timestamp. The Timestamp field establishes the signature an NTP timestamp. The Timestamp field establishes the signature
epoch of the data field in the message, while the filestamp epoch of the data field in the message, while the filestamp
establishes the generation epoch of the file that ultimately produced establishes the generation epoch of the file that ultimately produced
the data. the data.
The 32-bit Value Length field indicates the length of the Value field The 32-bit Value Length field indicates the length of the Value field
in octets. The minimum length of the Value field is 0. in octets. The minimum length of the Value field is 0, in which case
the Value field is omitted.
The 32-bit Value Length field indicates the length of the Value field The 32-bit Value Length field indicates the length of the Value field
in octets. The minimum length of the Value field is 0. in octets. The minimum length of the Value field is 0.
Zero padding is applied, as necessary, to extend the extension field Zero padding is applied, as necessary, to extend the extension field
to a word (4-octet) boundary. If multiple extension fields are to a word (4-octet) boundary. If multiple extension fields are
present, the last extension field is zero-padded to a double-word (8 present, the last extension field is zero-padded to a double-word (8
octet) boundary. octet) boundary.
The presence of the MAC and extension fields in the packet is The presence of the MAC and extension fields in the packet is
skipping to change at page 26, line 51 skipping to change at page 29, line 51
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
Peer A Peer A
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
org | 0 | | T3<>0? | | t3 | | T3<>t3? | org | 0 | | T3<>0? | | t3 | | T3<>t3? |
+---------+ +---------+ +---------+ +---------+ State +---------+ +---------+ +---------+ +---------+ State
rec | 0 | | t4 | | t4 | | t8 | Variables rec | 0 | | t4 | | t4 | | t8 | Variables
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
xmt | t1 | | T1=t1? | | t5 | | T1<>t5? | xmt | t1 | | T1=t1? | | t5 | | T1<>t5? |
+---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+
Figure 12: On-Wire Protocol Figure 7: On-Wire Protocol
The NTP on-wire protocol is the core mechanism to exchange time The NTP on-wire protocol is the core mechanism to exchange time
values between servers, peers and clients. It is inherently values between servers, peers and clients. It is inherently
resistant to lost or duplicate data packets. Data integrity is resistant to lost or duplicate data 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, either extracted from packet headers or struck from
the system clock upon the arrival or departure of a packet. the system clock upon the arrival or departure of a packet.
Timestamps are precision data and should be restruck in case of link Timestamps are precision data and should be restruck in case of link
level retransmission and corrected for the time to compute a MAC on level retransmission and corrected for the time to compute a MAC on
transmit. 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
to mean any available one to many mechanism. For IPv4 this equates to mean any available one to many mechanism. For IPv4 this equates
to either IPv4 broadcast or IPv4 multicast. For IPv6 this equates to 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. :101, with prefix determined by scoping rules.
The on-wire protocol uses four timestamps numbered T_1 through T_4 The on-wire protocol uses four timestamps numbered T1 through T4 and
and three state variables org, rec and xmt, as shown in Figure 12. three state variables org, rec and xmt, as shown in Figure 7. This
This figure shows the most general case where each of two peers, A figure shows the most general case where each of two peers, A and B,
and B, independently measure the offset and delay relative to the independently measure the offset and delay relative to the other.
other. For purposes of illustration the individual timestamp values For purposes of illustration the individual timestamp values are
are shown in lower case with subscripts indicating the order of shown in lower case with subscripts indicating the order of
transmission and reception. transmission and reception.
In the figure the first packet transmitted by A containing only the In the figure the first packet transmitted by A containing only the
transmit timestamp T3 with value t1. B receives the packet at t2 and transmit timestamp T3 with value t1. B receives the packet at t2 and
saves the origin timestamp T1 with value t1 in state variable org and saves the origin timestamp T1 with value t1 in state variable org and
the destination timestamp T4 with value t2 in state variable rec. At the destination timestamp T4 with value t2 in state variable rec. At
this time or some time later B sends a packet to A containing the org this time or some time later B sends a packet to A containing the org
and rec state variables in T1 and T2, respectively and in addition and rec state variables in T1 and T2, respectively and in addition
the transmit timestamp T3 with value t3, which is saved in the xmt the transmit timestamp T3 with value t3, which is saved in the xmt
state variable. When this packet arrives at A the packet header state variable. When this packet arrives at A the packet header
skipping to change at page 28, line 8 skipping to change at page 31, line 8
performed in order to protect against duplicate or bogus packets. A performed in order to protect against duplicate or bogus packets. A
packet is a duplicate if the transmit timestamp T3 in the packet packet is a duplicate if the transmit timestamp T3 in the packet
matches the xmt state variable. A packet is bogus if the origin matches the xmt state variable. A packet is bogus if the origin
timestamp T1 in the packet does not match the org state variable. In timestamp T1 in the packet does not match the org state variable. In
either of these cases the state variables are updated, but the packet either of these cases the state variables are updated, but the packet
is discarded. is discarded.
The four most recent timestamps, T1 through T4, are used to compute The four most recent timestamps, T1 through T4, are used to compute
the offset of B relative to A the offset of B relative to A
theta = T(B) - T(A) = 1/2*(T_2-T_1)+(T_3-T_4) theta = T(B) - T(A) = 1/2*(T2-T1)+(T4-T3)
and the roundtrip delay and the roundtrip delay
del = T(ABA)- = (T_4-T_1)-(T_3-T_2) delta = T(ABA)- = (T4-T1)-(T3-T2)
Note that the quantities within parentheses are computed from 64-bit Note that the quantities within parentheses are computed from 64-bit
unsigned timestamps and result in signed values with 63 significant unsigned timestamps and result in signed values with 63 significant
bits plus sign. These values can represent dates from 68 years in bits plus sign. These values can represent dates from 68 years in
the past to 68 years in the future. However, the offset and delay the past to 68 years in the future. However, the offset and delay
are computed as the sum and difference of these values, which contain are computed as the sum and difference of these values, which contain
62 significant bits and two sign bits, so can represent unambiguous 62 significant bits and two sign bits, so can represent unambiguous
values from 34 years in the past to 34 years in the future. In other values from 34 years in the past to 34 years in the future. In other
words, the time of the client must be set within 34 years of the words, the time of the client must be set within 34 years of the
server before the service is started. This is a fundamental server before the service is started. This is a fundamental
limitation with 64-bit integer arithmetic.. limitation with 64-bit integer arithmetic.
In implementations where floating double arithmetic is available, the In implementations where floating double arithmetic is available, the
first-order differences can be converted to floating double and the first-order differences can be converted to floating double and the
second-order sums and differences computed in that arithmetic. Since second-order sums and differences computed in that arithmetic. Since
the second-order terms are typically very small relative to the the second-order terms are typically very small relative to the
timestamps themselves, there is no loss in significance, yet the timestamps themselves, there is no loss in significance, yet the
unambiguous range is increased from 34 years to 68 years. unambiguous range is increased from 34 years to 68 years.
In some scenarios where the frequency offset between the client and In some scenarios where the frequency offset between the client and
server is relatively large and the actual propagation time small, it server is relatively large and the actual propagation time small, it
is possible that the delay computation becomes negative. For is possible that the delay computation becomes negative. For
instance, if the frequency difference is 100 PPM and the interval T_4 instance, if the frequency difference is 100 PPM and the interval
- T_1 is 64 s, the apparent delay is -6.4 ms. Since negative values T4-T1 is 64 s, the apparent delay is -6.4 ms. Since negative values
are misleading in subsequent computations, the value of del should be are misleading in subsequent computations, the value of del should be
clamped not less than the system precision s.precision rho defined clamped not less than the system precision defined.
below.
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 T_3 and T_4 from the client simplified. A stateless server copies T3 and T4 from the client
packet to T_1 and T_2 of the server packet and tacks on the transmit packet to T1 and T2 of the server packet and tacks on the transmit
timestamp T_3 before sending it to the client. Additional details timestamp T3 before sending it to the client. Additional details for
for filling in the remaining protocol fields are given in the next filling in the remaining protocol fields are given in the next
section and in Appendix A. section and in Appendix A.
A SNTP primary server implementing the on-wire protocol has no A SNTP primary server implementing the on-wire protocol has no
upstream servers except a single reference clock In principle, it is upstream servers except a single reference clock In principle, it is
indistinguishable from an NTP primary server which has the mitigation indistinguishable from an NTP primary server which has the mitigation
algorithms, presumably to mitigate between multiple reference clocks. algorithms, presumably to mitigate between multiple reference clocks.
Upon receiving a client request, a SNTP primary server constructs and Upon receiving a client request, a SNTP primary server constructs and
sends the reply packet as shown in Figure 5 below. Note that the sends the reply packet as shown in Table 4 below. Note that the
dispersion field in the packet header must be calculated in the same dispersion field in the packet header must be calculated in the same
way as in the NTP case. way as in the NTP case.
A SNTP client using the on-wire protocol has a single server and no A SNTP client using the on-wire protocol has a single server and no
downstream clients. It can operate with any subset of the NTP on- downstream clients. It can operate with any subset of the NTP on-
wire protocol, the simplest using only the transmit timestamp of the wire protocol, the simplest using only the transmit timestamp of the
server packet and ignoring all other fields. However, the additional server packet and ignoring all other fields. However, the additional
complexity to implement the full on-wire protocol is minimal and is complexity to implement the full on-wire protocol is minimal and is
encouraged. encouraged.
skipping to change at page 29, line 28 skipping to change at page 32, line 28
The peer process is called upon arrival of a server packet. It runs The peer process is called upon arrival of a server packet. It runs
the on-wire protocol to determine the clock offset and roundtrip the on-wire protocol to determine the clock offset and roundtrip
delay and in addition computes statistics used by the system and poll delay and in addition computes statistics used by the system and poll
processes. Peer variables are instantiated in the association data processes. Peer variables are instantiated in the association data
structure when the structure is initialized and updated by arriving structure when the structure is initialized and updated by arriving
packets. There is a peer process, poll process and association for packets. There is a peer process, poll process and association for
each server. each server.
The discussion in this section covers only the variables and routines The discussion in this section covers only the variables and routines
necessary for a conforming NTPv4 implementation. Additional necessary for a conforming NTPv4 implementation.
implementation details are in Section B.5.
8.1. Peer Process Variables 8.1. Peer Process Variables
Name Formula Description
Configuration Variables
srcaddr srcaddr source address
srcport srcport source port
dstaddr dstaddr destination address
dstport destport destination port
keyid keyid key identifier key ID
Packet Variables
leap leap leap indicator
version version version number
mode mode mode
stratum stratum stratum
ppoll ppoll peer poll exponent
rootdelay delta root delay
rootdisp E root dispersion
refid refid reference ID
reftime reftime reference timestamp
Timestamp Variables
t t epoch
org T1 origin timestamp
rec T2 receive timestamp
xmt T3 transmit timestamp
Statistics Variables
offset theta clock offset
delay del roundtrip delay
disp epsilon dispersion
jitter varphi jitter
Figure 13: Peer Process Variables Table 11, Table 12, Table 13, and Table 14 summarize the common
names, formula names and a short description of each peer variable,
all of which have prefix p.
Figure 13 summarizes the common names, formula names and a short +---------+----------+-----------------------+
description of each peer variable, all of which have prefix p. The | Name | Formula | Description |
following configuration variables are normally initialized when the +---------+----------+-----------------------+
association is mobilized, either from a configuration file or upon | srcaddr | srcaddr | source address |
arrival of the first packet for an ephemeral association. | srcport | srcport | source port |
| dstaddr | dstaddr | destination address |
| dstport | destport | destination port |
| keyid | keyid | key identifier key ID |
+---------+----------+-----------------------+
Table 11: Peer Process Configuration Variables
The following configuration variables are normally initialized when
the association is mobilized, either from a configuration file or
upon arrival of the first packet for an ephemeral association.
p.srcadr: IP address of the remote server or reference clock. This p.srcadr: 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.
p.srcport: UDP port number of the server or reference clock. This p.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.
skipping to change at page 31, line 14 skipping to change at page 33, line 26
address in packets sent from this association. address in packets sent from this association.
p.dstport: UDP port number of the client, ordinarily the NTP port p.dstport: UDP port number of the client, ordinarily the NTP port
number PORT (123) assigned by the IANA. This becomes the source port number 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.
p.keyid: Symmetric key ID for the 128-bit MD5 key used to generate p.keyid: Symmetric key ID for the 128-bit MD5 key used to generate
and verify the MAC. The client and server or peer can use different and verify the MAC. The client and server or peer can use different
values, but they must map to the same key. values, but they must map to the same key.
+-----------+------------+---------------------+
| Name | Formula | Description |
+-----------+------------+---------------------+
| leap | leap | leap indicator |
| version | version | version number |
| mode | mode | mode |
| stratum | stratum | stratum |
| ppoll | ppoll | peer poll exponent |
| rootdelay | delta | root delay |
| rootdisp | capepsilon | root dispersion |
| refid | refid | reference ID |
| reftime | reftime | reference timestamp |
+-----------+------------+---------------------+
Table 12: Peer Process Packet Variables
The variables defined below are updated from the packet header as The variables defined below 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 as
the packet variables of the same names. the packet variables of the same names.
------------------ ------------------
| receive | | receive |
------------------ ------------------
\| / \| /
------------------ no------------------ ------------------ no------------------
| format OK? |-->| format error | | format OK? |-->| format error |
------------------ ------------------ ------------------ ------------------
\| / yes \| / yes
------------------ no------------------ ------------------ no------------------
| access OK? |-->| access error | | access OK? |-->| access error |
skipping to change at page 31, line 41 skipping to change at page 34, line 29
------------------ ------------------ ------------------ ------------------
\| / no \| / no
------------------yes------------------ ------------------yes------------------
| auth OK? |-->| auth error | | auth OK? |-->| auth error |
------------------ ------------------ ------------------ ------------------
\| / yes \| / yes
------------------ ------------------
| match_assoc | | match_assoc |
------------------ ------------------
Figure 14: Receive Processing Figure 8: Receive Processing
p.leap, p.version, p.mode, p.stratum, p.ppoll, p.rootdelay, p.leap, p.version, p.mode, p.stratum, p.ppoll, p.rootdelay,
p.rootdisp, p.refid, p.reftime p.rootdisp, p.refid, p.reftime
It is convenient for later processing to convert the NTP short format It is convenient for later processing to convert the NTP short format
packet values p.rootdelay and p.rootdisp to floating doubles as peer packet values p.rootdelay and p.rootdisp to floating doubles as peer
variables. variables.
+------+---------+--------------------+
| Name | Formula | Description |
+------+---------+--------------------+
| t | t | epoch |
| org | T1 | origin timestamp |
| rec | T2 | receive timestamp |
| xmt | T3 | transmit timestamp |
+------+---------+--------------------+
Table 13: Peer Process Timestamp Variables
+--------+---------+-----------------+
| Name | Formula | Description |
+--------+---------+-----------------+
| offset | theta | clock offset |
| delay | del | roundtrip delay |
| disp | epsilon | dispersion |
| jitter | psi | jitter |
+--------+---------+-----------------+
Table 14: Peer Process Statistics Variables
The p.org, p.rec, p.xmt variables represent the timestamps computed The p.org, p.rec, p.xmt variables represent the timestamps computed
by the on-wire protocol described previously. The p.offset, p.delay, by the on-wire protocol described previously. The p.offset, p.delay,
p.disp, p.jitter variables represent the current time values and p.disp, p.jitter variables represent the current time values and
statistics produced by the clock filter algorithm. The offset and statistics produced by the clock filter algorithm. The offset and
delay are computed by the on-wire protocol; the dispersion and jitter delay are computed by the on-wire protocol; the dispersion and jitter
are calculated as described below. Strictly speaking, the epoch p.t are calculated as described below. Strictly speaking, the epoch p.t
is not a timestamp; it records the system timer upon arrival of the is not a timestamp; it records the system timer upon arrival of the
latest packet selected by the clock filter algorithm. latest packet selected by the clock filter algorithm.
8.2. Peer Process Operations 8.2. Peer Process Operations
Figure 14 shows the peer process code flow upon the arrival of a Figure 8 shows the peer process code flow upon the arrival of a
packet. There is no specific method required for access control, packet. There is no specific method required for access control,
although it is recommended that implementations include a match-and- although it is recommended that implementations include a match-and-
mask scheme similar to many others now in widespread use. Format mask scheme similar to many others now in widespread use. 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. There number (1-4) and correct extension field syntax, if present. There
is no specific requirement for authentication; however, if is no specific requirement for authentication; however, if
authentication is implemented, the symmetric key scheme described in authentication is implemented, the symmetric key scheme described in
Section 6 must be included among the supported. This scheme uses the Section 6 must be included among the supported. This scheme uses the
MD5 keyed hash algorithm Section A.2. For the most vulnerable MD5 keyed hash algorithm described in Appendix A.2. For the most
applications the Autokey public key scheme described in [3] is vulnerable applications the Autokey public key scheme described in
recommended. [3] is recommended.
Next, the association table is searched for matching source address Next, the association table is searched for matching source address
and source port using the find_assoc() routine in Section A.5. The and source port using the find_assoc() routine in Appendix A.5.1.
dispatch table near the beginning of that section is indexed by the The dispatch table near the beginning of that section is indexed by
packet mode and association mode (0 if no matching association) to the packet mode and association mode (0 if no matching association)
determine the dispatch code and thus the case target. The to determine the dispatch code and thus the case target. The
significant cases are FXMT, NEWPS and NEWBC. significant cases are FXMT, NEWPS and NEWBC.
----------------- -----------------
| client_packet | | client_packet |
----------------- -----------------
\ | / \ | /
----------------- -----------------
| copy header | | copy header |
----------------- -----------------
\ | / \ | /
----------------- -----------------
| copy T_1,T_2 | | copy T1,T2 |
----------------- -----------------
\ | / \ | /
----------------- -----------------
| T_3 = clock | | T3 = clock |
----------------- -----------------
\ | / \ | /
-----------------yes----------------- ----------------- yes --------------
| copy header |-->| MD5 digest |-\ | copy header |-->| MD5 digest |-\
----------------- ----------------- | ----------------- -------------- |
| no | | no |
\ | / | \ | / |
----------------- | ----------------- |
| NAK digest | | | NAK digest | |
----------------- | ----------------- |
|-----------------------------/ |-----------------------------/
\ | / \ | /
----------------- -----------------
| fast_xmit() | | fast_xmit() |
----------------- -----------------
\ | / \ | /
----------------- -----------------
| xmt = T_3 | | xmt = T3 |
----------------- -----------------
\ | / \ | /
----------------- -----------------
| return | | return |
----------------- -----------------
Packet Variable <-- Variable Packet Variable <-- Variable
x.leap <-- s.leap x.leap <-- s.leap
x.version <-- r.version x.version <-- r.version
x.mode <-- 4 x.mode <-- 4
skipping to change at page 33, line 38 skipping to change at page 37, line 4
x.precision <-- s.precision x.precision <-- s.precision
x.rootdelay <-- s.rootdelay x.rootdelay <-- s.rootdelay
x.rootdisp <-- s.rootdisp x.rootdisp <-- 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 <-- clock x.xmt <-- clock
x.keyid <-- r.keyid x.keyid <-- r.keyid
x.digest <-- md5 digest x.digest <-- md5 digest
Figure 9: Client Packet Processing
Figure 15: Client Packet Processing
FXMIT. This is a client (mode 3) packet matching no association. FXMIT. This is a client (mode 3) packet matching no association.
The server constructs a server (mode 4) packet and returns it to the The server constructs a server (mode 4) packet and returns it to the
client without retaining state. The server packet is constructed as client without retaining state. The server packet is constructed as
in Figure 15 and the fast_xmit() routine in Section B.5. If the in Figure 9 and the fast_xmit() routine in Appendix A.5.4. If the
s.rootdelay and s.rootdisp system variables are stored in floating s.rootdelay and s.rootdisp system variables are stored in floating
double, they must be converted to NTP short format first. Note that, double, they must be converted to NTP short format first. Note that,
if authentication fails, the server returns a special message called if authentication fails, the server returns a special message called
a crypto-NAK. This message includes the normal NTP header data shown a crypto-NAK. This message MUST include the normal NTP header data
in the figure, but with a MAC consisting of four octets of zeros. shown in the figure, but with a MAC consisting of four octets of
The client is free to accept or reject the data in the message. zeros. The client MAY accept or reject the data in the message.
NEWBC. This is a broadcast (mode 5) packet matching no association. NEWBC. This is a broadcast (mode 5) packet matching no association.
The client mobilizes a client (mode 3) association as shown in the The client mobilizes a client (mode 3) association as shown in the
mobilize() and clear() routines in Section A.2. Implementations mobilize() and clear() routines in Appendix A.2. Implementations
supporting authentication first perform the necessary steps to run supporting authentication first perform the necessary steps to run
the Autokey or other protocol, and determine the propagation delay, the Autokey or other protocol, and determine the propagation delay,
then continues in listen-only (mode 6) to receive further packets. then continues in listen-only (mode 6) to receive further packets.
Note the distinction between a mode-6 packet, which is reserved for Note the distinction between a mode-6 packet, which is reserved for
the NTP monitor and control functions, and a mode-6 association. the NTP monitor and control functions, and a mode-6 association.
NEWPS. This is a symmetric active (1) packet matching no NEWPS. This is a symmetric active (1) packet matching no
association. The client mobilizes a symmetric passive (mode 2) association. The client mobilizes a symmetric passive (mode 2)
association as shown in the mobilize() and clear() routines in association as shown in the mobilize() and clear() routines in
Section A.2. Code flow continues to the match_assoc() fragment Appendix A.2. Code flow continues to the match_assoc() fragment
described below. In other cases the packet matches an existing described below. In other cases the packet matches an existing
association and code flows to the match_assoc fragment in Figure 16. association and code flows to the match_assoc fragment in Figure 10.
The packet timestamps are carefully checked to avoid invalid, The packet timestamps are carefully checked to avoid invalid,
duplicate or bogus packets, as shown in the figure. Note that a duplicate or bogus packets, as shown in the figure. Note that a
crypto-NAK is considered valid only if it survives these tests. crypto-NAK is considered valid only if it survives these tests.
Next, the peer variables are copied from the packet header variables Next, the peer variables are copied from the packet header variables
as shown in Figure 17 and the packet() routine in Section A.5. as shown in Figure 11 and the packet() routine in Appendix A.5.2.
Implementations must include a number of data range checks as shown Implementations MUST include a number of data range checks as shown
in Table 3 and discard the packet if the ranges are exceeded; in Table 15 and discard the packet if the ranges are exceeded;
however, the header fields are copied even if errors occur, since however, the header fields MUST be copied even if errors occur, since
they are necessary in symmetric modes to construct the subsequent they are necessary in symmetric modes to construct the subsequent
poll message. poll message.
------------------ ---------------
| match assoc | | match assoc |
---------------- ---------------
\ | / \ | /
----------------yes---------------- --------------- yes ----------------
| T_3 = 0? |-->| format error | | T3 = 0? | --> | format error |
---------------- ---------------- --------------- ----------------
\ | / no \ | / no
----------------yes---------------- --------------- yes ----------------
| T_3 = xmt? |-->| duplicate | | T3 = xmt? | --> | duplicate |
---------------- ---------------- --------------- ----------------
\ | / no \ | / no
----------------no ----------------yes --------------- no ---------------- yes
| mode = 5? |-->|T_1 or T2 = 0?|--\ | mode = 5? | --> |T1 or T2 = 0? |--\
---------------- ---------------- | --------------- ---------------- |
| yes \ | / no | | yes \ | / no |
\ | /<-----\ ---------------- | \ | /<-----\ ---------------- |
| \-| T_1 = xmt? | | | \-| T1 = xmt? | |
---------------- ---------------- | ---------------- ---------------- |
| auth = NAK? | no \ | /<-----/ | auth = NAK? | no \ | /<------/
---------------- | ---------------- |
yes\|/ no\|/ ---------------- yes\|/ no\|/ ----------------
--------- ------ | org = T_3 | --------- ------ | org = T3 |
|org=T_3| |auth| | rec = T_4 | |org=T3| |auth| | rec = T4 |
|rec=T_4| |err | ---------------- |rec=T4| |err | ----------------
--------- ------ \ | / --------- ------ \ | /
\|/ ---------------- \|/ ----------------
--------- | return | --------- | return |
|packet | ---------------- |packet | ----------------
--------- ---------
Figure 16: Timestamp Processing Figure 10: Timestamp Processing
---------------- ----------------
| packet | | packet |
---------------- ----------------
\ | / \ | /
---------------- ----------------
| copy header | | copy header |
---------------- ----------------
\ | / \ | /
----------------bad---------------- ----------------bad----------------
| header? |-->|header error | | header? |-->|header error |
skipping to change at page 36, line 25 skipping to change at page 39, line 25
\ | / \ | /
---------------- ----------------
| reach |= 1 | | reach |= 1 |
---------------- ----------------
\ | / \ | /
---------------- ----------------
| poll update | | poll update |
---------------- ----------------
\ | / \ | /
---------------------------------------- ----------------------------------------
| theta = 1/2*(T_2-T_1)+(T_3-T_4) | | theta = 1/2*(T2-T1)+(T3-T4) |
| del = (T_4-T_1)-(T_3-T_2) | | del = (T4-T1)-(T3-T2) |
| epsilon = rho_r+rho+capphi*((T_4-T_1)| | epsilon = rho_r+rho+capphi*((T4-T1) |
---------------------------------------- ----------------------------------------
\ | / \ | /
---------------- ----------------
| clock filter | | clock filter |
---------------- ----------------
Peer Variables <-- Packet Variables Peer Variables <-- Packet Variables
p.leap <-- r.leap p.leap <-- r.leap
p.mode <-- r.mode p.mode <-- r.mode
p.stratum <-- r.stratum p.stratum <-- r.stratum
p.ppoll <-- r.ppoll p.ppoll <-- r.ppoll
p.rootdelay <-- r.rootdelay p.rootdelay <-- r.rootdelay
p.rootdisp <-- r.rootdisp p.rootdisp <-- r.rootdisp
p.refid <-- r.refid p.refid <-- r.refid
p.reftime <-- r.reftime p.reftime <-- r.reftime
Figure 17: Packet Processing Figure 11: Packet Processing
+----------------+--------------------------------------------------+ +--------------------------+----------------------------------------+
| Packet Type | Description | | Packet Type | Description |
+----------------+--------------------------------------------------+ +--------------------------+----------------------------------------+
| 1 duplicate | The packet is at best an old duplicate or at | | 1 duplicate packet | The packet is at best an old duplicate |
| packet | worst a replay by a hacker. This can happen in | | | or at worst a replay by a hacker. |
| | symmetric modes if the poll intervals are | | | This can happen in symmetric modes if |
| | uneven. | | | the poll intervals are uneven. |
| 2 bogus packet | | | 2 bogus packet | |
| 3 invalid | One or more timestamp fields are invalid. This | | 3 invalid | One or more timestamp fields are |
| | normally happens in symmetric modes when one | | | invalid. This normally happens in |
| | peer sends the first packet to the other and | | | symmetric modes when one peer sends |
| | before the other has received its first reply. | | | the first packet to the other and |
| 4 access | The access controls have black | | | before the other has received its |
| denied | | | | first reply. |
| 5 | The cryptographic message digest does not match | | 4 access denied | The access controls have black |
| authentication | the MAC. | | 5 authentication failure | The cryptographic message digest does |
| failure | | | | not match the MAC. |
| 6 | The server is not synchronized to a valid | | 6 unsynchronized | The server is not synchronized to a |
| unsynchronized | source. | | | valid source. |
| 7 bad header | One or more header fields are invalid. | | 7 bad header data | One or more header fields are invalid. |
| data | | | 8 autokey error | Public key cryptography has failed to |
| 8 autokey | Public key cryptography has failed to | | | authenticate the packet. |
| error | authenticate the packet. | | 9 crypto error | Mismatched or missing cryptographic |
| 9 crypto error | Mismatched or missing cryptographic keys or | | | keys or certificates. |
| | certificates. | +--------------------------+----------------------------------------+
+----------------+--------------------------------------------------+
Table 3: Packet Error Checks Table 15: Packet Error Checks
The 8-bit p.reach shift register in the poll process described later The 8-bit p.reach shift register in the poll process described later
is used to determine whether the server is reachable or not and is used to determine whether the server is reachable or not and
provide information useful to insure the server is reachable and the provide information useful to insure the server is reachable and the
data are fresh. The register is shifted left by one bit when a 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 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 poll_update() routine in have changed since the last packet, the poll_update() routine in
Section A.8 is called to re-determine the host poll interval. Appendix A.8.2 is called to re-determine the host poll interval.
The on-wire protocol calculates the clock offset theta and roundtrip The on-wire protocol calculates the clock offset theta and roundtrip
delay del from the four most recent timestamps as shown in Figure 12. delay del from the four most recent timestamps as shown in Figure 7.
While it is in principle possible to do all calculations except the While it is in principle possible to do all calculations except the
first-order timestamp differences in fixed-point arithmetic, it is first-order timestamp differences in fixed-point arithmetic, it is
much easier to convert the first-order differences to floating much easier to convert the first-order differences to floating
doubles and do the remaining calculations in that arithmetic, and doubles and do the remaining calculations in that arithmetic, and
this will be assumed in the following description. The dispersion this will be assumed in the following description. The dispersion
statistic epsilon(t) represents the maximum error due to the statistic epsilon(t) represents the maximum error due to the
frequency tolerance and time since the last measurement. It is frequency tolerance and time since the last measurement. It is
initialized initialized
epsilon(t_o) = rho_r + rho +cappsi(T_4-T_1) epsilon(t_o) = rho_r + rho +capphi(T4-T1)
when the measurement is made at t _0. Here rho_r is the peer when the measurement is made at t _0. Here rho_r is the peer
precision in the packet header r.precision and rho the system precision in the packet header r.precision and rho the system
precision s.precision, both expressed in seconds. These terms are precision s.precision, both expressed in seconds. These terms are
necessary to account for the uncertainty in reading the system clock necessary to account for the uncertainty in reading the system clock
in both the server and the client. The dispersion then grows at in both the server and the client. The dispersion then grows at
constant rate TOLERANCE (cappsi); in other words, at time t, constant rate TOLERANCE (cappsi); in other words, at time t,
epsilon(t) = epsilon(t_0) + cappsi(t-t_0). With the default value epsilon(t) = epsilon(t_0) + cappsi(t-t_0). With the default value
cappsi = 15 PPM, this amounts to about 1.3 s per day. With this cappsi = 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.
9. Clock Filter Algorithm 8.3. Clock Filter Algorithm
----------------------- -----------------------
| clock filter | | clock filter |
----------------------- -----------------------
\ | / \ | /
----------------------- -----------------------
| shift sample theta, | | shift sample theta, |
| del, epsilon, and t | | del, epsilon, and t |
| filter shift registr| | filter shift registr|
----------------------- -----------------------
\ | / \ | /
skipping to change at page 39, line 37 skipping to change at page 42, line 37
| t_0 > t? |----\ | t_0 > t? |----\
----------------------- | ----------------------- |
\ | / yes | \ | / yes |
----------------------- | ----------------------- |
| theta = theta_0 | | | theta = theta_0 | |
| del = del_0 | | | del = del_0 | |
| epsilon | | | epsilon | |
| = sum(epsilon_i) | | | = sum(epsilon_i) | |
| ---------- | | | ---------- | |
| 2^(i+1) | | | 2^(i+1) | |
| varphi | | | psi | |
| = sqrt(1/7* ... | | | = sqrt(1/7* ... | |
| ... sum( ... | | | ... sum( ... | |
| (theta_0-theta_i)^2 | | | (theta_0-theta_i)^2 | |
| t = t_0 | | | t = t_0 | |
----------------------- | ----------------------- |
\ | / | \ | / |
----------------------- | ----------------------- |
| clock_select() | | | clock_select() | |
----------------------- | ----------------------- |
\ | /<------------/ \ | /<------------/
----------------------- -----------------------
| return | | return |
----------------------- -----------------------
Figure 18: Clock Filter Processing Figure 12: Clock Filter Processing
The clock filter algorithm grooms the stream of on-wire data to The clock filter algorithm grooms the stream of on-wire data to
select the samples most likely to represent the correct time. The select the samples most likely to represent the correct time. The
algorithm produces the p.offset theta, p.delay del, p.dispersion algorithm produces the p.offset theta, p.delay del, p.dispersion
epsilon, p.jitter varphi, and time of arrival p.t t used by the epsilon, p.jitter psi, and time of arrival p.t t used by the
mitigation algorithms to determine the best and final offset used to mitigation algorithms to determine the best and final offset used to
discipline the system clock. They are also used to determine the discipline the system clock. They are also used to determine the
server health and whether it is suitable for synchronization. The server health and whether it is suitable for synchronization. The
core processing steps of this algorithm are shown in Figure 18 with core processing steps of this algorithm are shown in Figure 12 with
more detail in the clock_filter() routine in Section A.5. more detail in the clock_filter() routine in Appendix A.5.3.
The clock filter algorithm saves the most recent sample tuples The clock filter algorithm saves the most recent sample tuples
(theta, del, epsilon, t) in an 8-stage shift register in the order (theta, del, epsilon, t) in an 8-stage shift register in the order
that packets arrive. Here t is the system timer, not the peer that packets arrive. Here t is the system timer, not the peer
variable of the same name. The following scheme is used to insure variable of the same name. The following scheme is used to insure
sufficient samples are in the register and that old stale data are sufficient samples are in the register and that old stale data are
discarded. Initially, the tuples of all stages are set to the dummy discarded. Initially, the tuples of all stages are set to the dummy
tuple (0,MAXDISP, MAXDISP, t). As valid packets arrive, the (theta, tuple (0,MAXDISP, MAXDISP, 0). As valid packets arrive, the (theta,
del, epsilon, t) tuples are shifted into the register causing old del, epsilon, t) tuples are shifted into the register causing old
samples to be discarded, so eventually only valid samples remain. If samples to be discarded, so eventually only valid samples remain. If
the three low order bits of the reach register are zero, indicating the three low order bits of the reach register are zero, indicating
three poll intervals have expired with no valid packets received, the three poll intervals have expired with no valid packets received, the
poll process calls the clock filter algorithm with the dummy tuple poll process calls the clock filter algorithm with the dummy tuple
just as if the tuple had arrived from the network. If this persists just as if the tuple had arrived from the network. If this persists
for eight poll intervals, the register returns to the initial for eight poll intervals, the register returns to the initial
condition. condition.
In the next step the shift register stages are copied to a temporary In the next step the shift register stages are copied to a temporary
list and the list sorted by increasing del. Let j index the stages list and the list sorted by increasing del. Let j index the stages
starting with the lowest del. If the sample epoch t_0 is not later starting with the lowest del. If the sample epoch t_0 is not later
than the last valid sample epoch p.t, the routine exits without than the last valid sample epoch p.t, the routine exits without
affecting the current peer variables. Otherwise, let epsilon_j be affecting the current peer variables. Otherwise, let epsilon_j be
the dispersion of the jth entry, then the dispersion of the jth entry, then
i=n-1 i=n-1
--- e_i --- epsilon_i
e= \ -------- capepsilon = \ ----------
/ (i+1) / (i+1)
--- 2 --- 2
i=0 i=0
is the peer dispersion p.disp. Note the overload of epsilon, whether is the peer dispersion p.disp. Note the overload of epsilon, whether
input to the clock filter or output, the meaning should be clear from input to the clock filter or output, the meaning should be clear from
context. context.
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
skipping to change at page 41, line 16 skipping to change at page 44, line 16
determine whether the peer variables are acceptable or not. determine whether the peer variables are acceptable or not.
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 | |
varphi = | -------- * | / (theta_0-theta_j) | | psi = | -------- * | / (theta_0-theta_j) | |
| (n-1) | --- | | | (n-1) | --- | |
| | j=1 | | | | j=1 | |
| +----- -----+ | | +----- -----+ |
| | | |
+----- -----+ +----- -----+
where n is the number of valid tuples in the register. In order to where n is the number of valid tuples in the register. In order to
insure consistency and avoid divide exceptions in other computations, insure consistency and avoid divide exceptions in other computations,
the varphi is bounded from below by the system precision rho the psi is bounded from below by the system precision rho expressed
expressed in seconds. While not in general considered a major factor in seconds. While not in general considered a major factor in
in ranking server quality, jitter is a valuable indicator of ranking server quality, jitter is a valuable indicator of fundamental
fundamental timekeeping performance and network congestion state. timekeeping performance and network congestion state.
Of particular importance to the mitigation algorithms is the peer Of particular importance to the mitigation algorithms is the peer
synchronization distance, which is computed from the root delay and synchronization distance, which is computed from the root delay and
root dispersion. The root delay is root dispersion. The root delay is
del ' = delta_r + del del ' = delta_r + del
and the root dispersion is and the root dispersion is
epsilon ' = E_r + epsilon + varphi epsilon ' = capepsilon_r + epsilon + psi
Note that epsilon and therefore increase at rate capphi. The peer Note that epsilon and therefore increase at rate capphi. The peer
synchronization distance is defined synchronization distance is defined
lambda = (del ' / 2) + epsilon lambda = (del ' / 2) + epsilon
and recalculated as necessary. The lambda is a component of the root and recalculated as necessary. The lambda is a component of the root
synchronization distance caplambda used by the mitigation algorithms synchronization distance caplambda used by the mitigation algorithms
as a metric to evaluate the quality of time available from each as a metric to evaluate the quality of time available from each
server. Note that there is no state variable for lambda, as it server. Note that there is no state variable for lambda, as it
depends on the time since the last update. depends on the time since the last update.
10. System Process 9. System Process
As each new sample (theta, delta, epsilon, t) is produced by the As each new sample (theta, delta, epsilon, t) is produced by the
clock filter algorithm, the sample is processed by the mitigation clock filter algorithm, the sample is processed by the mitigation
algorithms consisting of the selection, clustering, combining and algorithms consisting of the selection, clustering, combining and
clock discipline algorithms in the system process. The selection clock discipline algorithms in the system process. The selection
algorithm scans all associations and casts off the falsetickers, algorithm scans all associations and casts off the falsetickers,
which have demonstrably incorrect time, leaving the truechimers as which have demonstrably incorrect time, leaving the truechimers as
result. In a series of rounds the clustering algorithm discards the result. In a series of rounds the clustering algorithm discards the
association statistically furthest from the centroid until a minimum association statistically furthest from the centroid until a minimum
number of survivors remain. The combining algorithm produces the number of survivors remain. The combining algorithm produces the
best and final offset on a weighted average basis and selects one of best and final offset on a weighted average basis and selects one of
the associations as the system peer providing the best statistics for the associations as the system peer providing the best statistics for
performance evaluation. The final offset is passed to the clock performance evaluation. The final offset is passed to the clock
discipline algorithm to steer the system clock to the correct time. discipline algorithm to steer the system clock to the correct time.
The statistics (theta, delta, epsilon, t) associated with the system The statistics (theta, delta, epsilon, t) associated with the system
peer are used to construct the system variables inherited by peer are used to construct the system variables inherited by
dependent servers and clients and made available to other dependent servers and clients and made available to other
applications running on the same machine. applications running on the same machine.
The discussion in following sections covers only the basic variables The discussion in following sections covers the basic variables and
and routines necessary for a conforming NTPv4 implementation. routines necessary for a conforming NTPv4 implementation. Additional
Additional implementation details are in Section B.6. An interface implementation details are in Appendix A. An interface that might be
that might be considered in a formal specification is represented by considered in a formal specification is represented by the function
the function prototypes in Section B.1. prototypes in Appendix A.1.6.
10.1. System Process Variables 9.1. System Process Variables
The variables and parameters associated with the system process are The variables and parameters associated with the system process are
summarized in Figure 21, which gives the variable name, formula name summarized in Table 16, which gives the variable name, formula name
and short description. Unless noted otherwise, all variables have and short description. Unless noted otherwise, all variables have
assumed prefix s. assumed prefix s.
Name/Formula/Description
t/t/epoch
leap/leap/leap indicator
stratum/stratum/stratum
precision/rho/precision
p/p/system peer pointer
offset/captheta/combined offset
jitter/varsigma/combined jitter
rootdelay/capdelta/root delay
rootdisp/E/root dispersion
refid/refid/reference ID
reftime/reftime/reference time
NMIN/3/minimum survivors
CMIN/1/minimum candidates
Figure 21: System Process Variables and Parameters +-----------+------------+---------------------+
| Name | Formula | Description |
+-----------+------------+---------------------+
| t | t | epoch |
| leap | leap | leap indicator |
| stratum | stratum | stratum |
| precision | rho | precision |
| p | p | system peer pointer |
| offset | captheta | combined offset |
| jitter | varsigma | combined jitter |
| rootdelay | capdelta | root delay |
| rootdisp | capepsilon | root dispersion |
| refid | refid | reference ID |
| reftime | reftime | reference time |
| NMIN | 3 | minimum survivors |
| CMIN | 1 | minimum candidates |
+-----------+------------+---------------------+
Table 16: System Process Variables and Parameters
All the variables except s.t and s.p have the same format and All the variables except s.t and s.p have the same format and
interpretation as the peer variables of the same name. The remaining interpretation as the peer variables of the same name. The remaining
variables are defined below. variables are defined below.
s.t: Integer representing the value of the system timer at the last s.t: Integer representing the value of the system timer at the last
update. update.
s.p: System peer association pointer. s.p: System peer association pointer.
s.precision: 8-bit signed integer representing the precision of the s.precision: 8-bit signed integer representing the precision of the
skipping to change at page 43, line 30 skipping to change at page 47, line 5
The variables defined below are updated from the system peer process The variables defined below are updated from the system peer process
as described later. They are interpreted in the same way as the as as described later. They are interpreted in the same way as the as
the peer variables of the same names. the peer variables of the same names.
s.leap, s.stratum, s.rootdelay, s.rootdisp, s.refid, s.reftime s.leap, s.stratum, s.rootdelay, s.rootdisp, s.refid, s.reftime
Initially, all variables are cleared to zero, then the s.leap is set Initially, all variables are cleared to zero, then the s.leap is set
to 3 (unsynchronized) and s.stratum is set to MAXSTRAT (16). The to 3 (unsynchronized) and s.stratum is set to MAXSTRAT (16). The
remaining statistics are determined as described below. remaining statistics are determined as described below.
10.2. System Process Operations 9.2. System Process Operations
The system process implements the selection, clustering, combining The system process implements the selection, clustering, combining
and clock discipline algorithms. The clock_select() routine in and clock discipline algorithms. The clock_select() routine in
Figure 22 includes the selection algorithm of Section 9.2.1 that Figure 15 includes the selection algorithm of Section 9.2.1 that
produces a majority clique of truechimers based on agreement produces a majority clique of truechimers based on agreement
principles. The clustering algorithm of Section 9.2.2 discards the principles. The clustering algorithm of Section 9.2.2 discards the
outliers of the clique to produce the survivors used by the combining outliers of the clique to produce the survivors used by the combining
algorithm in Section 9.2.3, which in turn provides the final offset algorithm in Section 9.2.3, which in turn provides the final offset
for the clock discipline algorithm in Section 9.2.4. If the for the clock discipline algorithm in Section 9.2.4. If the
selection algorithm cannot produce a majority clique, or if the selection algorithm cannot produce a majority clique, or if the
clustering algorithm cannot produce at least CMIN survivors, the clustering algorithm cannot produce at least CMIN survivors, the
system process terminates with no further processing. If successful, system process terminates with no further processing. If successful,
the clustering algorithm selects the statistically best candidate as the clustering algorithm selects the statistically best candidate as
the system peer and its variables are inherited as the system the system peer and its variables are inherited as the system
skipping to change at page 44, line 43 skipping to change at page 48, line 43
\|/ ----------------------- \|/ -----------------------
------------------------- \|/ no ------------------------- \|/ no
| s.p = NULL | ----------------------- | s.p = NULL | -----------------------
------------------------- | s.p = vo.p | ------------------------- | s.p = vo.p |
\|/ ----------------------- \|/ -----------------------
------------------------- \|/ ------------------------- \|/
| return (UNSYNC) | ----------------------- | return (UNSYNC) | -----------------------
------------------------- | return (SYNC) | ------------------------- | return (SYNC) |
----------------------- -----------------------
Figure 22: clock_select() routine Figure 15: clock_select() routine
10.2.1. Selection Algorithm 9.2.1. Selection Algorithm
The selection algorithm operates to find the truechimers using The selection algorithm operates to find the truechimers using
Byzantine agreement principles originally proposed by Marzullo [7], Byzantine agreement principles originally proposed by Marzullo [7],
but modified to improve accuracy. An overview of the algorithm is but modified to improve accuracy. An overview of the algorithm is
listed below and the first half of the clock_select() routine in listed below and the first half of the clock_select() routine in
Section A.6.1. First, those servers which are unusable according to Appendix A.6.1. First, those servers which are unusable according to
the rules of the protocol are detected and discarded by the accept() the rules of the protocol are detected and discarded by the accept()
routine in Figure 23 and Section B.6.3. Next, a set of tuples {p, routine in Figure 16 and Appendix A.6.3. Next, a set of tuples {p,
type, edge} is generated for the remaining servers, where p is an type, edge} is generated for the remaining servers, where p is an
association pointer, type and edge identifies the upper (+1), middle association pointer, type and edge identifies the upper (+1), middle
(0) and lower (-1) endpoint of a correctness interval [theta - (0) and lower (-1) endpoint of a correctness interval [theta -
lambda, theta + lambda], where lambda is the root distance. lambda, theta + lambda], where lambda is the root distance.
1. 1. For each of m associations, construct a correctness interval 1. For each of m associations, construct a correctness interval
[(theta - rootdist()), (theta + rootdist())]. [(theta - rootdist()), (theta + rootdist())].
2. 2. Select the lowpoint, midpoint and highpoint of these 2. Select the lowpoint, midpoint and highpoint of these intervals.
intervals. Sort these values in a list from lowest to highest. Sort these values in a list from lowest to highest. Set the
Set the number of falsetickers f = 0. number of falsetickers f=0.
3. 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 for every highpoint, add one to d for every
midpoint. If c >= m - f, stop; set l = current lowpoint
4. 4. Set c = 0. Scan from highest endpoint to lowest. Add one to 3. Set the number of midpoints d=0. Set c=0. Scan from lowest
c for every highpoint, subtract one for every lowpoint, add one endpoint to highest. Add one to c for every lowpoint, subtract
to d for every midpoint. If c >= m - f, stop; set u = current one for every highpoint, add one to d for every midpoint. If
highpoint. c>=m-f, stop; set l=current lowpoint
5. 5. Is d = f and l < u? 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 midpoint. If c>=m-f, stop; set u=current highpoint.
6. if yes, then follow step 5y, else, follow step 5n. 5. Is d=f and l<u? If yes, then follow step 5A, else, follow step
5B.
7. 5y. Success: the intersection interval is [l, u]. A. Success: the intersection interval is [l, u].
8. 5n. Add one to f. Is f < (m / 2)? If yes, then go to step 3 B. Add one to f. Is f < (m / 2)? If yes, then go to step 3
again. If no, then go to step 6. again. If no, then go to step 6.
9. 6. Failure; a majority clique could not be found. Stop 6. Failure; a majority clique could not be found. Stop algorithm.
algorithm.
The tuples are placed on a list and sorted by edge. The list is The tuples are placed on a list and sorted by edge. The list is
processed from the lowest to the highest, then from highest to lowest processed from the lowest to the highest, then from highest to lowest
as described in detail in [8]. The algorithm starts with the as described in detail in [8]. The algorithm starts with the
assumption that there are no falsetickers (f = 0) and attempts to assumption that there are no falsetickers (f=0) and attempts to find
find a nonempty intersection interval containing the midpoints of all a nonempty intersection interval containing the midpoints of all
correct servers, i.e., truechimers. If a nonempty interval cannot be correct servers, i.e., truechimers. If a nonempty interval cannot be
found, it increases the number of assumed falsetickers by one and found, it increases the number of assumed falsetickers by one and
tries again. If a nonempty interval is found and the number of tries again. If a nonempty interval is found and the number of
falsetickers is less than the number of truechimers, a majority falsetickers is less than the number of truechimers, a majority
clique has been found and the midpoints (offsets) represent the clique has been found and the midpoints (offsets) represent the
survivors available for the clustering algorithm. Otherwise, there survivors available for the clustering algorithm. Otherwise, there
are no suitable candidates to synchronize the system clock. are no suitable candidates to synchronize the system clock.
-------------------- --------------------
| accept() | | accept() |
skipping to change at page 46, line 33 skipping to change at page 50, line 33
\|/ no | \|/ no |
-------------------- | -------------------- |
| refid = addr? |---yes----->| server/client | refid = addr? |---yes----->| server/client
-------------------- | sync loop -------------------- | sync loop
\|/ no | \|/ no |
-------------------- | -------------------- |
| return (YES) | ----------------------- | return (YES) | -----------------------
-------------------- | return (NO) | -------------------- | return (NO) |
----------------------- -----------------------
Figure 23: accept() routine Figure 16: accept() routine
10.2.2. Clustering Algorithm 9.2.2. Clustering Algorithm
The members of the majority clique are placed on the survivor list, The members of the majority clique are placed on the survivor list,
and sorted first by stratum, then by root distance lambda. The and sorted first by stratum, then by root distance lambda. The
sorted list is processed by the clustering algorithm below and the sorted list is processed by the clustering algorithm below and the
second half of the clock_select() algorithm in Section B.6.1. second half of the clock_select() algorithm in Appendix A.6.1.
1. Let (theta, phi, Lambda) represent a candidate peer with 1. Let (theta, phi, Lambda) represent a candidate peer with
offset theta, jitter j and a weight factor Lambda = stratum * offset theta, jitter psi and a weight factor
MAXDIST + rootdist(). Lambda=stratum*MAXDIST+rootdist().
2. Sort the candidates by increasing Lambda. Let n be the number 2. Sort the candidates by increasing Lambda. Let n be the number
of candidates and NMIN the minimum number of survivors. of candidates and NMIN the minimum number of survivors.
3. For each candidate compute the selection jitter jsubS (RMS 3. For each candidate compute the selection jitter psi_S (RMS
peer offset differences between this and all other candidates). peer offset differences between this and all other candidates).
4. Select j_max as the candidate with maximum j_S. 4. Select psi_max as the candidate with maximum psi_S.
5. Select j_min as the candidate with minimum j_S. 5. Select psi_min as the candidate with minimum psi_S.
If yes, go to step 6y. If no, go to step 6n. 6. Is psi_max < psi_min or n <= NMIN? If yes, go to step 6y. If
no, go to step 6n.
6y. Done. The remaining cluster survivors are correct. The 6y. Done. The remaining cluster survivors are correct. The
survivors are in the v. structure sorted by Lambda. survivors are in the v. structure sorted by Lambda.
6n. Delete the outlyer candidate with j_max; reduce n by one, and 6n. Delete the outlyer candidate with psi_max; reduce n by one,
go back to step 3. and go back to step 3.
It operates in a series of rounds where each round discards the It operates in a series of rounds where each round discards the
furthest statistical outlier until a specified minimum number of furthest statistical outlier until a specified minimum number of
survivors NMIN (3) are left or until no further improvement is survivors NMIN (3) are left or until no further improvement is
possible. In each round let n be the number of survivors and s index possible. In each round let n be the number of survivors and s index
the survivor list. Assume jp is the peer jitter of the s survivor. the survivor list. Assume psi_p is the peer jitter of the s
Compute survivor. Compute
+----- -----+ +----- -----+
| 1/2 | | 1/2 |
| +----- -----+ | | +----- -----+ |
| | n-1 | | | | n-1 | |
| | --- | | | | --- | |
| 1 | \ 2 | | | 1 | \ 2 | |
varphi_s = | -------- * | / (theta_s-theta_j) | | psi_s = | -------- * | / (theta_s-theta_j) | |
| (n-1) | --- | | | (n-1) | --- | |
| | j=1 | | | | j=1 | |
| +----- -----+ | | +----- -----+ |
| | | |
+----- -----+ +----- -----+
as the selection jitter. Then choose varphi_max = max (varphi) and as the selection jitter. Then choose psi_max=max(psi) and
varphi_min = min (varphi). If varphi_max < varphi_min or n < NMIN, psi_min=min(psi). If psi_max<psi_min or n<NMIN, no further reduction
no further reduction in selection jitter is possible, so the in selection jitter is possible, so the algorithm terminates and the
algorithm terminates and the remaining survivors are processed by the remaining survivors are processed by the combining algorithm.
combining algorithm. Otherwise, the algorithm case off the Otherwise, the algorithm case off the psi_max survivor, reduces n by
varphi_max survivor, reduces n by one and makes another round. one and makes another round.
10.2.3. Combining Algorithm 9.2.3. Combining Algorithm
--------------------- ---------------------
| clock_combine() | | clock_combine() |
--------------------- ---------------------
\|/ \|/
--------------------- ---------------------
| y = z = w = 0 | | y = z = w = 0 |
--------------------- ---------------------
\|/ \|/
--------------------- ---------------------
| scan cluster | ------------------ | scan cluster | ------------------
skipping to change at page 48, line 42 skipping to change at page 52, line 42
| return | | return |
----------------------- -----------------------
Variable/Process/Description Variable/Process/Description
captheta/system/combined clock offset captheta/system/combined clock offset
vartheta_p/system/combined jitter vartheta_p/system/combined jitter
theta_0/survivor list/first survivor offset theta_0/survivor list/first survivor offset
theta_i/survivor list/ith survivor offset theta_i/survivor list/ith survivor offset
x,y,z,w/ /temporaries x,y,z,w/ /temporaries
Figure 25: clock_combine() routine Figure 18: clock_combine() routine
-------------------- --------------------
| clock_update() | | clock_update() |
-------------------- --------------------
\|/ \|/
-------------------- --------------------
/----no----->| p.t > s.t | /----no----->| p.t > s.t |
| -------------------- | --------------------
| \|/ yes | \|/ yes
| -------------------- | --------------------
| | s.t = p.t | | | s.t = p.t |
skipping to change at page 49, line 43 skipping to change at page 53, line 43
--------------- ---------------
| return | | return |
--------------- ---------------
System Variables <-- System Peer Variables System Variables <-- System Peer Variables
leap <-- leap leap <-- leap
stratum <-- stratum + 1 stratum <-- stratum + 1
refid <-- refid refid <-- refid
reftime <-- reftime reftime <-- reftime
capdelta <-- capdelta_r + del capdelta <-- capdelta_r + del
E <-- E_r+epsilon+cappsi*mu+varphi+|captheta| capepsilon <-- capepsilon_r+epsilon+cappsi*mu+psi+|captheta|
* update system variables * update system variables
Figure 26: clock_update() routine Figure 19: clock_update() routine
The remaining survivors are processed by the clock_combine() routine The remaining survivors are processed by the clock_combine() routine
in Figure 25 and Section A.6.4 to produce the best and final data for in Figure 18 and Appendix A.6.5 to produce the best and final data
the clock discipline algorithm. The routine processes the peer for the clock discipline algorithm. The routine processes the peer
offset theta and jitter varphi to produce the system offset captheta offset theta and jitter psi to produce the system offset captheta and
and system peer jitter vartheta_p, where each server statistic is system peer jitter vartheta_p, where each server statistic is
weighted by the reciprocal of the root distance and the result weighted by the reciprocal of the root distance and the result
normalized. The system peer jitter vartheta_p is a component of the normalized. The system peer jitter vartheta_p is a component of the
system jitter described later. system jitter described later.
The system statistics are passed to the clock_update() routine in The system statistics are passed to the clock_update() routine in
Figure 26 and Section A.6.4. If there is only one survivor, the Figure 19 and Appendix A.6.4. If there is only one survivor, the
offset passed to the clock discipline algorithm is captheta = theta offset passed to the clock discipline algorithm is captheta=theta and
and the system peer jitter is vartheta=varphi. Otherwise, the the system peer jitter is vartheta=psi. Otherwise, the selection
selection jitter vartheta_s is computed as in (8), where theta_0 jitter vartheta_s is computed as in (8), where theta_0 represents the
represents the offset of the system peer and j ranges over the offset of the system peer and j ranges over the survivors.
survivors.
Peer Variables Client System Variables Peer Variables Client System Variables
---------------- ----------------- ---------------- -----------------
| theta = 1/2* |-------------------->| captheta = | | theta = 1/2* |-------------------->| captheta = |
| [(T_2 - T_1)+| | (combine | | [(T2 - T1)+ | | (combine |
| (T_3 - T_4)] | | (theta_j)) | | (T3 - T4)] | | (theta_j)) |
---------------- ----------------- ---------------- -----------------
| del = [(T_4 -|--sum--------------->| capdelta= | | del = [(T4 - |--sum--------------->| capdelta= |
| T_1) - (T_3 -| /|\ | capdelta_r + | | T1) - (T3 - | /|\ | capdelta_r + |
| T_2)] | | | del | | T2)] | | | del |
---------------- | ----------------- ---------------- | -----------------
| epsilon = | | | E = E_r + | | epsilon = | | | capepsilon = |
| | | |capepsilon_r + |
| rho_r + rho +| | | epsilon + | | rho_r + rho +| | | epsilon + |
| captheta*( | | | vartheta + | | captheta*( | | | vartheta + |
| T_4 - T_1) |------------sum----->| absolutevalue(| | T4 - T1) |------------sum----->| absolutevalue(|
---------------- | /|\ | theta) | ---------------- | /|\ | theta) |
| varphi = | | | ----------------- | psi = | | | -----------------
| sqrt((1/n)-1)*| | | | varphi_s = | | sqrt((1/n)-1)*| | | | psi_s = |
| (sum(theta_0)| | | | sqrt(1/(m-1)* | | (sum(theta_0)| | | | sqrt(1/(m-1)* |
| -theta_i)^2))|---|---\ | | sum(theta_0- | | -theta_i)^2))|---|---\ | | sum(theta_0- |
---------------- | | | | theta_j)^2) | ---------------- | | | | theta_j)^2) |
/|\ | | | ----------------- /|\ | | | -----------------
| | | | \|/ | | | | \|/
| | \------------------>sum | | \------------------>sum
server| | | | server| | | |
---------------- | | \|/ ---------------- | | \|/
| rho_r | | | | | rho_r | | | |
---------------- | | ----------------- ---------------- | | -----------------
| capdelta_r |>--/ | | vartheta = | | capdelta_r |>--/ | | vartheta = |
---------------- | | sqrt( | ---------------- | | sqrt( |
| E_r |>------------/ | (vartheta_p)^2| | capepsilon_r |>------------/ | (vartheta_p)^2|
---------------- | + | ---------------- | + |
| (vartheta_s)^2| | (vartheta_s)^2|
----------------- -----------------
Figure 27: System Variables Processing Figure 20: System Variables Processing
The first survivor on the survivor list is selected as the system The first survivor on the survivor list is selected as the system
peer, here represented by the statistics (theta, del, epsilon, peer, here represented by the statistics (theta, del, epsilon, psi).
varphi). By rule, an update is discarded if its time of arrival p.t By rule, an update is discarded if its time of arrival p.t is not
is not strictly later than the last update used s.t. Let mu = p.t - strictly later than the last update used s.t. Let mu=p.t-s.t be the
s.t be the time since the last update or update interval. If the time since the last update or update interval. If the update
update interval is less than or equal to zero, the update is interval is less than or equal to zero, the update is discarded.
discarded. Otherwise, the system variables are updated from the Otherwise, the system variables are updated from the system peer
system peer variables as shown in Figure 26. Note that s.stratum is variables as shown in Figure 19. Note that s.stratum is set to
set to p.stratum plus one. p.stratum plus one.
The arrows labeled IGNOR, PANIC, ADJ and STEP refer to return codes The arrows labeled IGNOR, PANIC, ADJ and STEP refer to return codes
from the local_clock() routine described in the next section. IGNORE from the local_clock() routine described in the next section. IGNORE
means the update has been ignored as an outlier. PANIC means the means the update has been ignored as an outlier. PANIC means the
offset is greater than the panic threshold PANICT (1000 s) and offset is greater than the panic threshold PANICT (1000 s) and SHOULD
normally causes the program to exit with a diagnostic message to the cause the program to exit with a diagnostic message to the system
system log. STEP means the offset is less than the panic threshold, log. STEP means the offset is less than the panic threshold, but
but greater than the step threshold STEPT (125 ms). Since this means greater than the step threshold STEPT (125 ms). Since this means all
all peer data have been invalidated, all associations are reset and peer data have been invalidated, all associations SHOULD be reset and
the client begins as at initial start. ADJ means the offset is less the client begins as at initial start. ADJ means the offset is less
than the step threshold and thus a valid update for the local_clock() than the step threshold and thus a valid update for the local_clock()
routine described later. In this case the system variables are routine described later. In this case the system variables are
updated as shown in Figure 26. updated as shown in Figure 19.
There is one exception not shown. The dispersion increment is There is one exception not shown. The dispersion increment is
bounded from below by MINDISP. In subnets with very fast processors bounded from below by MINDISP. In subnets with very fast processors
and networks and very small dispersion and delay this forces a and networks and very small dispersion and delay this forces a
monotone-definite increase in , which avoids loops between peers monotone-definite increase in capepsilon, which avoids loops between
operating at the same stratum. peers operating at the same stratum.
Figure 27 shows how the error budget grows from the packet variables, Figure 20 shows how the error budget grows from the packet variables,
on-wire protocol and system peer process to produce the system on-wire protocol and system peer process to produce the system
variables that are passed to dependent applications and clients. The variables that are passed to dependent applications and clients. The
system jitter is defined system jitter is defined
vartheta = sqrt((vartheta_p)^2+(vartheta_s)^2) vartheta = sqrt((vartheta_p)^2+(vartheta_s)^2)
where vartheta_s is the selection jitter relative to the system peer. where vartheta_s is the selection jitter relative to the system peer.
The system jitter is passed to dependent applications programs as the The system jitter is passed to dependent applications programs as the
nominal error statistic. The root delay capdelta and root dispersion nominal error statistic. The root delay capdelta and root dispersion
E statistics are relative to the primary server reference clock and capepsilon statistics are relative to the primary server reference
thus inherited by each server along the path. The system clock and thus inherited by each server along the path. The system
synchronization distance is defined synchronization distance is defined
caplambda = capdelta/2 + E caplambda = capdelta/2 + capepsilon
which is passed to dependent application programs as the maximum which is passed to dependent application programs as the maximum
error statistic. error statistic.
10.2.4. Clock Discipline Algorithm 9.2.4. Clock Discipline Algorithm
--------- ---------
thetar + | \ +----------------+ theta_r + | \ +----------------+
NTP --------->| Phase \ V_d | | V_s NTP --------->| Phase \ V_d | | V_s
thetac - | Detector ------>| Clock Filter |-----+ theta_c - | Detector ------>| Clock Filter |-----+
+-------->| / | | | +-------->| / | | |
| | / +----------------+ | | | / +----------------+ |
| --------- | | --------- |
| | | |
----- | ----- |
/ \ | / \ |
| VFO | | | VFO | |
\ / | \ / |
----- +-------------------------------------+ | ----- +-------------------------------------+ |
^ | Loop Filter | | ^ | Loop Filter | |
| | | | | | | |
| | +---------+ x +-------------+ | | | | +---------+ x +-------------+ | |
| | | |<-----| | | | | V_c | | |<-----| | | |
+------|-| Clock | y | Phase/Freq |<---|------+ +------|-| Clock | y | Phase/Freq |<---|------+
| | Adjust |<-----| Prediction | | | | Adjust |<-----| Prediction | |
| | | | | | | | | | | |
| +---------+ +-------------+ | | +---------+ +-------------+ |
| | | |
+-------------------------------------+ +-------------------------------------+
Figure 28: Clock Discipline Feedback Loop Figure 21: Clock Discipline Feedback Loop
The NTPv4 clock discipline algorithm, shortened to discipline in the The NTPv4 clock discipline algorithm, shortened to discipline in the
following, functions as a combination of two philosophically quite following, functions as a combination of two philosophically quite
different feedback control systems. In a phase-locked loop (PLL) different feedback control systems. In a phase-locked loop (PLL)
design, periodic phase updates at update intervals m are used design, periodic phase updates at update intervals m are used
directly to minimize the time error and indirectly the frequency directly to minimize the time error and indirectly the frequency
error. In a frequency-locked loop (FLL) design, periodic frequency error. In a frequency-locked loop (FLL) design, periodic frequency
updates at intervals mu are used directly to minimize the frequency updates at intervals mu are used directly to minimize the frequency
error and indirectly the time error. As shown in [8], a PLL usually error and indirectly the time error. As shown in [8], a PLL usually
works better when network jitter dominates, while a FLL works better works better when network jitter dominates, while a FLL works better
skipping to change at page 53, line 6 skipping to change at page 57, line 6
The clock discipline and clock adjust processes interact with the The clock discipline and clock adjust processes interact with the
other algorithms in NTPv4. The output of the combining algorithm other algorithms in NTPv4. The output of the combining algorithm
represents the best estimate of the system clock offset relative to represents the best estimate of the system clock offset relative to
the server ensemble. The discipline adjusts the frequency of the VFO the server ensemble. The discipline adjusts the frequency of the VFO
to minimize this offset. Finally, the timestamps of each server are to minimize this offset. Finally, the timestamps of each server are
compared to the timestamps derived from the VFO in order to calculate compared to the timestamps derived from the VFO in order to calculate
the server offsets and close the feedback loop. the server offsets and close the feedback loop.
The discipline is implemented as the feedback control system shown in The discipline is implemented as the feedback control system shown in
Figure 28. The variable theta_r represents the combining algorithm Figure 21. The variable theta_r represents the combining 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 Vd representing the instantaneous phase Each update produces a signal V_d representing the instantaneous
difference theta_r - theta_c. The clock filter for each server phase difference theta_r - theta_c. The clock filter for each server
functions as a tapped delay line, with the output taken at the tap functions as a tapped delay line, with the output taken at the tap
selected by the clock filter algorithm. The selection, clustering selected by the clock filter algorithm. The selection, clustering
and combining algorithms combine the data from multiple filters to and combining algorithms combine the data from multiple filters to
produce the signal Vs. The loop filter, with impulse response F(t), produce the signal V_s. The loop filter, with impulse response F(t),
produces the signal Vc which controls the VFO frequency omega_c and produces the signal V_c which controls the VFO frequency omega_c and
thus its phase theta_c = integral (omega_c, dt) which closes the thus its phase theta_c=integral(omega_c,dt) which closes the loop.
loop. The Vc signal is generated by the clock adjust process in The V_c signal is generated by the clock adjust process in
Section 9.3. The characteristic behavior of this model, which is Section 9.3. The characteristic behavior of this model, which is
determined by F(t) and the various gain factors given in Section determined by F(t) and the various gain factors given in
A.6.6. Appendix A.6.6.
The transient behavior of the PLL/FLL feedback loop is determined by The transient behavior of the PLL/FLL feedback loop is determined by
the impulse response of the loop filter F(t). The loop filter shown the impulse response of the loop filter F(t). The loop filter shown
in Figure 29 predicts a phase adjustment x as a function of Vs. The in Figure 22 predicts a phase adjustment x as a function of Vs. The
PLL predicts a frequency adjustment yFLL as an integral of Vs*mu with PLL predicts a frequency adjustment yFLL as an integral of Vs*mu with
repsect to t, while the FLL predicts an adjustment yPLL as a function repsect to t, while the FLL predicts an adjustment yPLL as a function
of Vs /mu. The two adjustments are combined to correct the frequency of Vs /mu. The two adjustments are combined to correct the frequency
y as shown in Figure 29. The x and y are then used by the y as shown in Figure 22. The x and y are then used by the
clock_adjust()routine to control the VFO frequency. The detailed clock_adjust()routine to control the VFO frequency. The detailed
equations that implement these functions are best presented in the equations that implement these functions are best presented in the
routines of Sections A.6.6 and A.7.1. routines of Appendix A.6.6 and Appendix A.7.1.
x <------(Phase Correction)<--. x <------(Phase Correction)<--.
| |
y_FLL | y_FLL |
.-(FLL Predict)<-------+<--V_s .-(FLL Predict)<-------+<--V_s
| | | |
\|/ | \|/ |
y <--(Sum) | y <--(Sum) |
^ | ^ |
| | | |
'-(PLL Predict)<-------' '-(PLL Predict)<-------'
y_PLL y_PLL
Figure 29: Clock Discipline Loop Filter Figure 22: Clock Discipline Loop Filter
Ordinarily, the pseudo-linear feedback loop described above operates Ordinarily, the pseudo-linear feedback loop described above operates
to discipline the system clock. However, there are cases where a to discipline the system clock. However, there are cases where a
nonlinear algorithm offers considerable improvement. One case is nonlinear algorithm offers considerable improvement. One case is
when the discipline starts without knowledge of the intrinsic clock when the discipline starts without knowledge of the intrinsic clock
frequency. The pseudo-linear loop takes several hours to develop an frequency. The pseudo-linear loop takes several hours to develop an
accurate measurement and during most of that time the poll interval accurate measurement and during most of that time the poll interval
cannot be increased. The nonlinear loop described below does this in cannot be increased. The nonlinear loop described below does this in
15 minutes. Another case is when occasional bursts of large jitter 15 minutes. Another case is when occasional bursts of large jitter
are present due to congested network links. The state machine are present due to congested network links. The state machine
described below resists error bursts lasting less than 15 minutes. described below resists error bursts lasting less than 15 minutes.
The remainder of this section describes how the discipline works. The remainder of this section describes how the discipline works.
Figure 30 contains a summary of the variables and parameters Table 17 contains a summary of the variables and parameters including
including the program name, formula name and short description. the program name, formula name and short description. Unless noted
Unless noted otherwisse, all variables have assumed prefix c. The otherwisse, all variables have assumed prefix c. The variables c.t,
variables c.t, c.tc, c.state, and c.count are integers; the memainder c.tc, c.state, and c.count are integers; the memainder are floating
are floating doubles. The function of each will be explained in the doubles. The function of each will be explained in the algorithm
algorithm descriptions below. descriptions below.
Name Formula Description +--------+------------+-------------------------+
---- ------- ----------- | Name | Formula | Description |
t timer seconds counter +--------+------------+-------------------------+
offset captheta combined offset | t | timer | seconds counter |
resid captheta_r residual offset | offset | captheta | combined offset |
freq phi clock frequency | resid | captheta_r | residual offset |
jitter varphi clock jitter | freq | phi | clock frequency |
wander cappsi frequency wander | jitter | psi | clock jitter |
tc tau time constant(log2) | wander | cappsi | frequency wander |
state state state | tc | tau | time constant(log2) |
adj adj frequency adjustment | state | state | state |
count count hysteresis counter | adj | adj | frequency adjustment |
STEPT 125 step threshold (.125 s) | count | count | hysteresis counter |
WATCH 900 stepout thresh(s) | STEPT | 125 | step threshold (.125 s) |
PANICT 1000 panic threshold(1000 s) | WATCH | 900 | stepout thresh(s) |
LIMIT 30 hysteresis limit | PANICT | 1000 | panic threshold(1000 s) |
PGATE 4 hysteresis gate | LIMIT | 30 | hysteresis limit |
TC 16 time constant scale | PGATE | 4 | hysteresis gate |
AVG 8 averaging constant | TC | 16 | time constant scale |
| AVG | 8 | averaging constant |
+--------+------------+-------------------------+
Figure 30 Table 17: Clock Discipline Variables And Parameters
===================================================================== =====================================================================
| State | captheta < STEP | captheta > STEP | Comments | | State | captheta < STEP | captheta > STEP | Comments |
--------------------------------------------------------------------- ---------------------------------------------------------------------
| NSET | > FREQ; adjust | > FREQ; step | no frequency | | NSET | > FREQ; adjust | > FREQ; step | no frequency |
| | time | time | file | | | time | time | file |
--------------------------------------------------------------------- ---------------------------------------------------------------------
| FSET | > SYNC; adjust | > SYNC; step | frequency file | | FSET | > SYNC; adjust | > SYNC; step | frequency file |
| | time | time | | | | time | time | |
--------------------------------------------------------------------- ---------------------------------------------------------------------
| SPIK | > SYNC; adjust | if (<900 s)>SPIK | outlier detected | | SPIK | > SYNC; adjust | if (<900 s)>SPIK | outlier detected |
skipping to change at page 55, line 26 skipping to change at page 59, line 26
--------------------------------------------------------------------- ---------------------------------------------------------------------
| FREQ | if (<900 s)> FREQ | if (<900 s)>FREQ | initial frequency | | FREQ | if (<900 s)> FREQ | if (<900 s)>FREQ | initial frequency |
| | else >SYNC; step | else >SYNC; step | | | | else >SYNC; step | else >SYNC; step | |
| | freq, adjust time | freq, adjust time | | | | freq, adjust time | freq, adjust time | |
--------------------------------------------------------------------- ---------------------------------------------------------------------
| SYNC | >SYNC; adjust freq| if (<900 s)>SPIK | normal operation | | SYNC | >SYNC; adjust freq| if (<900 s)>SPIK | normal operation |
| | adjust time | else >SYNC; step | | | | adjust time | else >SYNC; step | |
| | | freq; step time | | | | | freq; step time | |
--------------------------------------------------------------------- ---------------------------------------------------------------------
Figure 31 Figure 23
The discipline is implemented by the local_clock() routine, which is The discipline is implemented by the local_clock() routine, which is
called from the clock_update() routine. The local_clock() routine called from the clock_update() routine. The local_clock() routine
pseudo code in Section B.6.6 has two parts; first the state machine pseudo code in Appendix A.6.6 has two parts; first the state machine
shown in Figure 32 and second the algorithm that determines the time shown in Figure 24 and second the algorithm that determines the time
constant and thus the poll interval in Figure 33. The state constant and thus the poll interval in Figure 25. The state
transition function in Figure 32 is implemented by the rst() function transition function in Figure 24 is implemented by the rst() function
shown at the lower left of the figure. The local_clock() routine shown at the lower left of the figure. The local_clock() routine
exits immediately if the offset is greater than the panic threshold. exits immediately if the offset is greater than the panic threshold.
--- ---
| A | | A |
--- ---
|| ||
\/ \/
--- yes --- --- yes ---
| B |-->| C | | B |-->| C |
--- --- --- ---
skipping to change at page 57, line 27 skipping to change at page 61, line 27
R: state=NSET? R: state=NSET?
S: rst(new,off) S: rst(new,off)
T: tc T: tc
U: rst(FREQ,0) U: rst(FREQ,0)
V: state=new V: state=new
captheta_B=off-captheta_R captheta_B=off-captheta_R
captheta_R=off captheta_R=off
W: return(rval) W: return(rval)
X: return X: return
Figure 32: local_clock() routine (1 of 2) Figure 24: local_clock() routine (1 of 2)
----- -----
| A | | A |
----- -----
\|/ \|/
----- -----
| B | | B |
----- -----
\|/ \|/
----- -----
skipping to change at page 58, line 41 skipping to change at page 62, line 41
H: count = 0 H: count = 0
I: count = 0 I: count = 0
J: tau>MINPOLL J: tau>MINPOLL
K: tau<MAXPOLL K: tau<MAXPOLL
L: tau-- L: tau--
M: tau++ M: tau++
N: phi += freq N: phi += freq
O: cappsi = sqrt(expectationvalue(phi^2)) O: cappsi = sqrt(expectationvalue(phi^2))
P: return(rval) P: return(rval)
Figure 33: local_clock() routine (2 of 2) Figure 25: local_clock() routine (2 of 2)
The remaining portion of the local_clock() routine is shown in The remaining portion of the local_clock() routine is shown in
Figure 33. The time constant tau is determined by comparing the Figure 25. The time constant tau is determined by comparing the
clock jitter varphi with the magnitude of the current residual offset clock jitter psi with the magnitude of the current residual offset
captheata_R. produced by the clock adjust routine in the next captheata_R. produced by the clock adjust routine in the next
section. If the residual offset is greater than PGATE (4) times the section. If the residual offset is greater than PGATE (4) times the
clock jitter, be hysteresis counter is reduced by two; otherwise, it clock jitter, be hysteresis counter is reduced by two; otherwise, it
is increased by one. If the hysteresis counter increases to the is increased by one. If the hysteresis counter increases to the
upper limit LIMIT (30), the time constant is increased by one; if it upper limit LIMIT (30), the time constant is increased by one; if it
decreases to the lower limit -LIMIT (-30), the time constant is decreases to the lower limit -LIMIT (-30), the time constant is
decreased by one. Normally, the time constant hovers near MAXPOLL, decreased by one. Normally, the time constant hovers near MAXPOLL,
but quickly decreases it frequency surges due to a temperature spike, but quickly decreases it frequency surges due to a temperature spike,
for example. for example.
The clock jitter statistic vartheta and the clock wander statistic The clock jitter statistic vartheta and the clock wander statistic
cappsi are implemented as exponential averages of RMS offset cappsi are implemented as exponential averages of RMS offset
differences and RMS frequency differences, respectively. Let x_i be differences and RMS frequency differences, respectively. Let x_i be
a measurement at time i of either vartheta or cappsi,y_i = x_i - a measurement at time i of either vartheta or cappsi,y_i = x_i -
x_(i-1) the first-order sample difference and y_i_HAT the exponential x_(i-1) the first-order sample difference and y_i_HAT the exponential
average. Then, average. Then,
y_(i+1)_HAT = sqrt((y_i_HAT)^2+[(y_i)^2-(y_i_HAT)^2)/AVG]) y_(i+1)_HAT = sqrt((y_i_HAT)^2+[(y_i)^2-(y_i_HAT)^2)/AVG])
where AVG (4) is the averaging parameter in Figure 30, is the where AVG (4) is the averaging parameter in Table 17, is the
exponential average at time i + 1. The clock jitter statistic is exponential average at time i + 1. The clock jitter statistic is
used by the poll-adjust algorithm above; the clock wander statistic used by the poll-adjust algorithm above; the clock wander statistic
issued only for performance monitoring. issued only for performance monitoring.
10.3. Clock Adjust Process 9.3. Clock Adjust Process
----- -----
| A | | A |
----- -----
\|/ \|/
----- -----
| B | | B |
----- -----
\|/ \|/
----- -----
| C | | C |
skipping to change at page 60, line 35 skipping to change at page 64, line 35
\|/ \|/
----- -----
| F |-----no----\ | F |-----no----\
----- | ----- |
\|/yes \|/ \|/yes \|/
----- ----- ----- -----
| H |<--------| G | | H |<--------| G |
----- ----- ----- -----
A: clock_adjust() A: clock_adjust()
B: E += captheta B: capepsilon += captheta
C: tmp = captheta_r/TC(tau) C: tmp = captheta_r/TC(tau)
D: captheta_R -= tmp D: captheta_R -= tmp
E: adjust_time(phi + tmp) E: adjust_time(phi + tmp)
F: next < timer? F: next < timer?
G: poll() G: poll()
H: return H: return
Figure 34: clock_adjust() Routine Figure 26: clock_adjust() Routine
The actual clock adjustment is performed by the clock_adjust() The actual clock adjustment is performed by the clock_adjust()
routine shown in Figure 34 and Section B.7.1. It runs at one-second routine shown in Figure 26 and Appendix A.7.1. It runs at one-second
intervals to add the frequency offset in Figure 33 and a fixed intervals to add the frequency offset in Figure 25 and a fixed
percentage of the residual offset captheta_R. The captheta_R is in percentage of the residual offset captheta_R. The captheta_R is in
effect the exponential decay of the captheta value produced by the effect the exponential decay of the captheta value produced by the
loop filter at each update. The TC parameter scales the time loop filter at each update. The TC parameter scales the time
constant to match the poll interval for convenience. Note that the constant to match the poll interval for convenience. Note that the
dispersion E increases by capphi at each second. dispersion capepsilon increases by capphi at each second.
The clock adjust process includes a timer interrupt facility driving The clock adjust process includes a timer interrupt facility driving
the system timer c.t. It begins at zero when the service starts and the system timer c.t. It begins at zero when the service starts and
increments once each second. At each interrupt the clock_adjust() increments once each second. At each interrupt the clock_adjust()
routine is called to incorporate the clock discipline time and routine is called to incorporate the clock discipline time and
frequency adjustments, then the associations are scanned to determine frequency adjustments, then the associations are scanned to determine
if the system timer equals or exceeds the p.next state variable if the system timer equals or exceeds the p.next state variable
defined in the next section. If so, the poll process is called to defined in the next section. If so, the poll process is called to
send a packet and compute the next p.next value. send a packet and compute the next p.next value.
11. Poll Process 10. Poll Process
Each association supports a poll process that runs at regular Each association supports a poll process that runs at regular
intervals to construct and send packets in symmetric, client and intervals to construct and send packets in symmetric, client and
broadcast server associations. It runs continuously, whether or not broadcast server associations. It runs continuously, whether or not
servers are reachable. The discussion in this section covers only servers are reachable. The discussion in this section covers the
the variables and routines necessary for a conforming NTPv4 variables and routines necessary for a conforming NTPv4
implementation. Additional implementation details are in Section implementation. Further details and rationale for the engineering
B.8. Further details and rationale for the engineering design are design are discussed in [8].
discussed in [8].
Name Formula Description 10.1. Poll Process Variables and Parameters
---- ------- -----------
hpoll hpoll host poll exponent
last last last poll time
next next next poll time
reach reach reach register
unreach unreach unreach counter
UNREACH 24 unreach limit
BCOUNT 8 burst count
BURST flag burst enable
IBURST flag iburst enable
Figure 35 +---------+---------+--------------------+
| Name | Formula | Description |
+---------+---------+--------------------+
| hpoll | hpoll | host poll exponent |
| last | last | last poll time |
| next | next | next poll time |
| reach | reach | reach register |
| unreach | unreach | unreach counter |
| UNREACH | 24 | unreach limit |
| BCOUNT | 8 | burst count |
| BURST | flag | burst enable |
| IBURST | flag | iburst enable |
+---------+---------+--------------------+
11.1. Poll Process Variables and Parameters Table 18: 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. Figure 35 shows the structure along with the peer process variables. Table 18 shows the
names, formula names and short definition for each one. Following is names, formula names and short definition for each one. Following is
a detailed description of the variables, all of which carry the p a detailed description of the variables, all of which carry the p
prefix. prefix.
p.hpoll: Signed integer representing the poll exponent, in log2 p.hpoll: Signed integer representing the poll exponent, in log2
seconds. seconds.
p.last: Integer representing the system timer value when the most p.last: Integer representing the system timer value when the most
recent packet was sent. recent packet was sent.
p.next: Integer representing the system timer value when the next p.next: Integer representing the system timer value when the next
packet is to be sent. packet is to be sent.
p.reach: 8-bit integer shift register. When a packet is sent, the p.reach: 8-bit integer shift register. When a packet is sent, the
register is shifted left one bit, with zero entering from the right register is shifted left one bit, with zero entering from the right
and overflow bits discarded. and overflow bits discarded.
p.unreach: Integer representing the number of seconds the server has p.unreach: Integer representing the number of seconds the server has
been unreachable. been unreachable.
11.2. Poll Process Operations 10.2. Poll Process Operations
As described previously, once each second the clock_adjust() routine As described previously, once each second the clock_adjust() routine
is called. This routine calls the poll() routine in Section B.8.1 MUST be called. This routine calls the poll() routine in
for each association in turn. If the time for the next poll message Appendix A.8.1 for each association in turn. If the time for the
is greater than the system timer, the routine returns immediately. A next poll message is greater than the system timer, the routine MUST
mode-5 (broadcast server) association always sends a packet, but a return immediately. A mode-5 (broadcast server) association MUST
mode-6 (broadcast client) association never sends a packet, but runs send a packet, but a mode-6 (broadcast client) association MUST NOT
the routine to update the p.reach and p.unreach variables. The send a packet, but MUST run the routine to update the p.reach and
poll() routine calls the peer_xmit() routine in Section B.8.3 to send p.unreach variables. The poll() routine calls the peer_xmit()
a packet. If in a burst (p.burst > 0), nothing further is done routine in Appendix A.8.3 to send a packet. If in a burst (p.burst >
except call the poll_update() routine to set the next poll interval. 0), nothing further is done except call the poll_update() routine to
set the next poll interval.
If not in a burst, the p.reach variable is shifted left by one bit, If not in a burst, the p.reach variable is shifted left by one bit,
with zero replacing the rightmost bit. If the server has not been with zero replacing the rightmost bit. If the server has not been
heard for the last three poll intervals, the clock_filter() routine heard for the last three poll intervals, the clock_filter() routine
is called to increase the dispersion as described in Section 8.3. If is called to increase the dispersion as described in Section 8.3. If
the BURST flag is lit and the server is reachable and a valid source the BURST flag is lit and the server is reachable and a valid source
of synchronization is available, the client sends a burst of BCOUNT of synchronization is available, the client sends a burst of BCOUNT
(8) packets at each poll interval. This is useful to accurately (8) packets at each poll interval. This is useful to accurately
measure jitter with long poll intervals. If the IBURST flag is lit measure jitter with long poll intervals. If the IBURST flag is lit
and this is the first packet sent when the server becomes and this is the first packet sent when the server becomes
skipping to change at page 63, line 9 skipping to change at page 67, line 12
When a packet is sent from an association, some header values are When a packet is sent from an association, 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. includes a flow diagram and a table from the system variables. includes a flow diagram and a table
showing which values are copied to each header field. In those showing which values are copied to each header field. In those
implementations using floating double data types for root delay and implementations using floating double data types for root delay and
root dispersion, these must be converted to NTP short format. All root dispersion, these must be converted to NTP short format. All
other fields are either copied intact from peer and system variables other fields are either copied intact from peer and system variables
or struck as a timestamp from the system clock. or struck as a timestamp from the system clock.
The poll_update() routine shown in Section B.8.2 is called when a The poll_update() routine shown in Appendix A.8.2 is called when a
valid packet is received and immediately after a poll message is valid packet is received and immediately after a poll message is
sent. If in a burst, the poll interval is fixed at 2 s; otherwise, sent. If in a burst, the poll interval is fixed at 2 s; otherwise,
the host poll exponent is set to the minimum of p.poll from the last the host poll exponent is set to the minimum of p.poll from the last
packet received and p.hpoll from the poll() routine, but not less packet received and p.hpoll from the poll() routine, but not less
than MINPOLL nor greater than MAXPOLL. Thus the clock discipline can than MINPOLL nor greater than MAXPOLL. Thus the clock discipline can
be oversampled, but not undersampled. This is necessary to preserve be oversampled, but not undersampled. This is necessary to preserve
subnet dynamic behavior and protect against protocol errors. subnet dynamic behavior and protect against protocol errors.
Finally, the poll exponent is converted to an interval which Finally, the poll exponent is converted to an interval which
establishes the time at the next poll p.next. establishes the time at the next poll p.next.
12. Security Considerations 11. Security Considerations
NTPv4 provides an optional authentication field that utilizes the MD5 NTPv4 provides an optional authentication field that utilizes the MD5
algorithm. MD5, as the case for SHA-1, is derived from MD4, which algorithm. MD5, as the case for SHA-1, is derived from MD4, which
has long been known to be weak. In 2004, techniques for efficiently has long been known to be weak. In 2004, techniques for efficiently
finding collisions in MD5 were announced. A summary of the weakness finding collisions in MD5 were announced. A summary of the weakness
of MD5 can be found in [9]. of MD5 can be found in [9].
In the case of NTP as specified herein, NTP broadcast clients are In the case of NTP as specified herein, NTP broadcast clients are
vulnerable to disruption by misbehaving or hostile SNTP or NTP vulnerable to disruption by misbehaving or hostile SNTP or NTP
broadcast servers elsewhere in the Internet. Access controls and/or broadcast servers elsewhere in the Internet. Access controls and/or
cryptographic authentication means should be provided for additional cryptographic authentication means should be provided for additional
security in such cases. security in such cases.
13. IANA Considerations 12. IANA Considerations
UDP/TCP Port 123 was previously assigned by IANA for this protocol. UDP/TCP Port 123 was previously assigned by IANA for this protocol.
The IANA has assigned the IPv4 multicast group address 224.0.1.1 and The IANA has assigned the IPv4 multicast group address 224.0.1.1 and
the IPv6 multicast address ending :101 for NTP. This document the IPv6 multicast address ending :101 for NTP. This document
introduces NTP extension fields allowing for the development of introduces NTP extension fields allowing for the development of
future extensions to the protocol, where a particular extension is to future extensions to the protocol, where a particular extension is to
be identified by the Field Type sub-field within the extension field. be identified by the Field Type sub-field within the extension field.
IANA is requested to establish and maintain a registry for Extension IANA is requested to establish and maintain a registry for Extension
Field Types associated with this protocol, populating this registry Field Types associated with this protocol, populating this registry
with no initial entries. As future needs arise, new Extension Field with no initial entries. As future needs arise, new Extension Field
Types may be defined. Following the policies outlined in [10], new Types may be defined. Following the policies outlined in [10], new
values are to be defined by IETF Consensus. values are to be defined by IETF Consensus.
14. Acknowledgements 13. Acknowledgements
This authors would like to thank Brian Haberman, Greg Dowd, Mark
Elliot, and Harlan Stenn for technical reviews of this document.
15. References This authors would like to thank Karen O'Donoghue, Brian Haberman,
Greg Dowd, Mark Elliot, and Harlan Stenn for technical reviews of
this document.
15.1. Normative References 14. Informative References
[1] Mills, D., "Network Time Protocol (Version 3) Specification, [1] Mills, D., "Network Time Protocol (Version 3) Specification,
Implementation", RFC 1305, March 1992. Implementation", RFC 1305, March 1992.
15.2. Informative References
[2] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for [2] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for
IPv4, IPv6 and OSI", RFC 4330, January 2006. IPv4, IPv6 and OSI", RFC 4330, January 2006.
[3] University of Delaware, "The Autokey security architecture, [3] University of Delaware, "The Autokey security architecture,
protocol and algorithms. Electrical and Com puter Engineering protocol and algorithms. Electrical and Com puter Engineering
Technical Report 06-1-1", NDSS , January 2006. Technical Report 06-1-1", NDSS , January 2006.
[4] Bradner, S., "Key words for use in RFCs to Indicate Requirement [4] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997. Levels", BCP 14, RFC 2119, March 1997.
skipping to change at page 65, line 16 skipping to change at page 69, line 10
This appendix is intended to describe the protocol and algorithms of This appendix is intended to describe the protocol and algorithms of
an implementation in a general way using what is called a code an implementation in a general way using what is called a code
skeleton program. This consists of a set of definitions, structures skeleton program. This consists of a set of definitions, structures
and code segments which illustrate the protocol operations without and code segments which illustrate the protocol operations without
the complexities of an actual implementation of the protocol. This the complexities of an actual implementation of the protocol. This
program is not an executable and is not designed to run in the program is not an executable and is not designed to run in the
ordinary sense. It is designed to be compiled only in order to ordinary sense. It is designed to be compiled only in order to
verify consistent variable and type usage. The program is not verify consistent variable and type usage. The program is not
intended to be fast or compact, just to demonstrate the algorithms intended to be fast or compact, just to demonstrate the algorithms
with sufficient fidelity to understand how they work. Reword or with sufficient fidelity to understand how they work. The code
remove The code skeleton consists of five segments, a header segment skeleton consists of eight segments, a header segment included by
included by each of the other segments, plus a code segment for the each of the other segments, plus a code segment for the main program,
main program and peer, system, clock_adjust and poll processes. kernel I/O and system clock interfaces, and peer, system,
These are presented in order below along with definitions and clock_adjust and poll processes. These are presented in order below
variables specific to each process. along with definitions and variables specific to each process.
A.1. Global Definitions A.1. Global Definitions
Following are definitions and other data shared by all programs. Following are definitions and other data shared by all programs.
These values are defined in a header file ntp4.h which is included in These values are defined in a header file ntp4.h which is included in
all files. all files.
A.2. Definitions, Constants, Parameters A.1.1. Definitions, Constants, Parameters
#include <math.h> s/* avoids complaints about sqrt() */ #include <math.h> s/* avoids complaints about sqrt() */
#include <sys/time.h> /* for gettimeofday() and friends */ #include <sys/time.h> /* for gettimeofday() and friends */
#include <stdlib.h> /* for malloc() and friends */ #include <stdlib.h> /* for malloc() and friends */
/* /*
* Data types * Data types
* *
* This program assumes the int data type is 32 bitsand * This program assumes the int data type is 32 bits and the long data
the long data * type is 64 bits. The native data type used in most calculations is
* type is 64 bits. The native data * floating double. The data types used in some packet header fields
type used in most calculations is * require conversion to and from this representation. Some header
* floating double. The data types used * fields involve partitioning an octet, here represented by individual
in some packet header fields
* require conversion to and from this
representation. Some header
* fields involve partitioning an octet, here
represented by individual
* octets. * octets.
* *
* The 64-bit NTP timestamp format used in * The 64-bit NTP timestamp format used in timestamp calculations is
timestamp calculations is * unsigned seconds and fraction with the decimal point to the left of
* unsigned seconds and fraction with the * bit 32. The only operation permitted with these values is
decimal point to the left of * subtraction, yielding a signed 31-bit difference. The 32-bit NTP
* bit 32. The only operation permitted * short format used in delay and dispersion calculations is seconds and
with these values is * fraction with the decimal point to the left of bit 16. The only
* subtraction, yielding a signed 31-bit * operations permitted with these values are addition and
difference. The 32-bit NTP
* short format used in delay and dispersion
calculations is seconds and
* fraction with the decimal point to the
left of bit 16. The only
* operations permitted with these values
are addition and
* multiplication by a constant. * multiplication by a constant.
* *
* The IPv4 address is 32 bits, while the * The IPv4 address is 32 bits, while the IPv6 address is 128 bits. 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 * The precision and poll interval fields are signed log2 seconds.
constructed by the MD5 algorithm.
* The precision and poll interval fields
are signed log2 seconds.
*/ */
typedef unsigned long tstamp; typedef unsigned long tstamp;
typedef unsigned int tdist; typedef unsigned int tdist;
typedef unsigned long ipaddr; typedef unsigned long ipaddr;
typedef unsinged int ipport; typedef unsinged int ipport;
typedef unsigned long digest; typedef unsigned long digest;
typedef signed char s_char; typedef signed char s_char;
/* /*
* Arithmetic conversion macroni * Arithmetic conversion macroni
*/ */
skipping to change at page 67, line 8 skipping to change at page 70, line 36
#define LFP2D(a) ((double)(a) / 0x100000000L) /* NTP timestamp */ #define LFP2D(a) ((double)(a) / 0x100000000L) /* NTP timestamp */
#define D2LFP(a) ((tstamp)((a) * 0x100000000L)) #define D2LFP(a) ((tstamp)((a) * 0x100000000L))
#define FP2D(a) (double)(a) / 0x10000L) /* NTP short */ #define FP2D(a) (double)(a) / 0x10000L) /* NTP short */
#define D2FP(a) ((tdist)((a) * 0x10000L)) #define D2FP(a) ((tdist)((a) * 0x10000L))
#define SQUARE(x) (x * x) #define SQUARE(x) (x * x)
#define SQRT(x) (sqrt(x)) #define SQRT(x) (sqrt(x))
/* /*
* Global constants. Some of these might be * Global constants. Some of these might be converted to variables
converted to variables * which can be tinkered by configuration or computed on-fly. For
* which can be tinkered by configuration * instance, PRECISION could be calculated on-fly and
or computed on-fly. For * provide performance tuning for the defines marked with % below.
* instance, PRECISION could be calculated
on-fly and
* provide performance tuning for the defines
marked with % below.
*/ */
#define VERSION 4 /* version number */ #define VERSION 4 /* version number */
#define PORT 123 /* NTP poert number */ #define PORT 123 /* NTP poert number */
#define MINDISP .01 /* % minimum dispersion (s) */ #define MINDISP .01 /* % minimum dispersion (s) */
#define MAXDISP 16 /* % maximum dispersion (s) */ #define MAXDISP 16 /* % maximum dispersion (s) */
#define MAXDIST 1 /* % distance threshold (s) */ #define MAXDIST 1 /* % distance threshold (s) */
#define NOSYNC 3 /* leap unsync */ #define NOSYNC 3 /* leap unsync */
#define MAXSTRAT 16 /* maximum stratum (infinity metric) */ #define MAXSTRAT 16 /* maximum stratum (infinity metric) */
#define MINPOLL 4 /* % minimum poll interval (16 s)*/ #define MINPOLL 4 /* % minimum poll interval (16 s)*/
#define MAXPOLL 17 /* % maximum poll interval (36.4 h) */ #define MAXPOLL 17 /* % maximum poll interval (36.4 h) */
skipping to change at page 68, line 51 skipping to change at page 72, line 28
#define M_BCLN 6 /* broadcast client */ #define M_BCLN 6 /* broadcast client */
/* /*
* 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 */
A.3. Packet Data Structures A.1.2. Packet Data Structures
/* /*
* The receive and transmit packets may * The receive and transmit packets may contain an optional message
contain an optional message * authentication code (MAC) consisting of a key identifier (keyid) and
* authentication code (MAC) consisting of a * message digest (mac). NTPv4 supports optional extension fields which
key identifier (keyid) and * message digest (mac). * are inserted after the the header and before the MAC, but these are
NTPv4 supports optional extension fields which * are * not described here.
inserted after the 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 * Note the dst timestamp is not part of the packet itself. It is
itself. It is * captured upon arrival and returned in the receive buffer along with
* captured upon arrival and returned in the * the buffer length and data. Note that some of the char fields are
receive buffer along with * packed in the actual header, but the details are omited here.
* the buffer length and data. Note that some
of the char fields are
* packed in the actual header, but the
details are omited here.
*/ */
struct r { struct r {
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 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 */
skipping to change at page 70, line 21 skipping to change at page 73, line 39
tdist rootdisp; /* root dispersion */ tdist rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
tstamp org; /* origin timestamp */ tstamp org; /* origin timestamp */
tstamp rec; /* receive timestamp */ tstamp rec; /* receive timestamp */
tstamp xmt; /* transmit timestamp */ tstamp xmt; /* transmit timestamp */
int keyid; /* key ID */ int keyid; /* key ID */
digest digest; /* message digest */ digest digest; /* 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 * Association structure. This is shared between the peer process and
peer process and * poll process. * poll process.
*/ */
struct p { struct p {
/* /*
* Variables set by configuration * Variables set by configuration
*/ */
ipaddr srcaddr; /* source (remote) address */ ipaddr srcaddr; /* source (remote) address */
ipport srcport; /* source port number *. ipport srcport; /* source port number *.
ipaddr dstaddr; /* destination (local) address */ ipaddr dstaddr; /* destination (local) address */
ipport dstport; /* destination port number */ ipport dstport; /* destination port number */
skipping to change at page 71, line 41 skipping to change at page 76, line 4
* Poll process variables * Poll process variables
*/ */
char hpoll; /* host poll interval */ char hpoll; /* host poll interval */
int burst; /* burst counter */ int burst; /* burst counter */
int reach; /* reach register */ int reach; /* reach register */
#define end_clear unreach /* end of clear area */ #define end_clear unreach /* end of clear area */
int unreach; /* unreach counter */ int unreach; /* unreach counter */
int last; /* last poll time */ int last; /* last poll time */
int next; /* next poll time */ int next; /* 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
*/ */
skipping to change at page 72, line 31 skipping to change at page 77, line 4
double rootdisp; /* root dispersion */ double rootdisp; /* root dispersion */
char refid; /* reference ID */ char refid; /* reference ID */
tstamp reftime; /* reference time */ tstamp reftime; /* reference time */
struct m m[NMAX]; /* chime list */ struct m m[NMAX]; /* chime list */
struct v v[NMAX]; /* survivor list */ struct v v[NMAX]; /* survivor list */
struct p *p; /* association ID */ struct p *p; /* association ID */
double offset; /* combined offset */ double offset; /* combined offset */
double jitter; /* combined jitter */ double jitter; /* combined jitter */
int flags; /* option flags */ int flags; /* option flags */
} s; } s;
A.1.5 Local Clock Data Structure
A.1.5. Local Clock Data Structures
/* /*
* Local clock structure * Local clock structure
*/ */
struct c { struct c {
tstamp t; /* update time */ tstamp t; /* update time */
int state; /* current state */ int state; /* current state */
double offset; /* current offset */ double offset; /* current offset */
double base; /* base offset */ double base; /* base offset */
double last; /* previous offset */ double last; /* previous offset */
int count; /* jiggle counter */ int count; /* jiggle counter */
double freq; /* frequency */ double freq; /* frequency */
double jitter; /* RMS jitter */ double jitter; /* RMS jitter */
double wander; /* RMS wander */ double wander; /* RMS wander */
} c; } c;
A.1.6 Function Prototypes
A.1.6. Function Prototypes
/* /*
* Peer process * Peer process
*/ */
void receive(struct r *); /* receive packet */ void receive(struct r *); /* receive packet */
void fast_xmit(struct r *, int, int); void fast_xmit(struct r *, int, int);
/* transmit a reply packet */ /* transmit a reply packet */
struct p *find_assoc(struct r *); struct p *find_assoc(struct r *);
/* search the association table */ /* search the association table */
void packet(struct p *, struct r *); void packet(struct p *, struct r *);
skipping to change at page 74, line 12 skipping to change at page 78, line 34
/* mobilize */ /* mobilize */
void clear(struct p *, int); /* clear association */ void clear(struct p *, int); /* clear association */
digest md5(int); /* generate a message digest */ digest md5(int); /* generate a message digest */
/* /*
* Kernel I/O Interface * Kernel I/O Interface
*/ */
struct r *recv_packet(); /* wait for packet */ struct r *recv_packet(); /* wait for packet */
void xmit_packet(struct x *); /* send packet */ void xmit_packet(struct x *); /* send packet */
.* /*
* Kernel system clock interface * Kernel system clock interface
*/ */
void step_time(double); /* step time */ void step_time(double); /* step time */
void adjust_time(double); /* adjust (slew) time */ void adjust_time(double); /* adjust (slew) time */
tstamp get_time(); /* read time */ tstamp get_time(); /* read time */
A.2 Main Program and Utility Routines
A.2. Main Program and Utility Routines
#include "ntp4.h" #include "ntp4.h"
/* /*
* Definitions * Definitions
*/ */
#define PRECISION -18 /* precision (log2 s) */ #define PRECISION -18 /* precision (log2 s) */
#define IPADDR 0 /* any IP address */ #define IPADDR 0 /* any IP address */
#define MODE 0 /* any NTP mode */ #define MODE 0 /* any NTP mode */
#define KEYID 0 /* any key identifier */ #define KEYID 0 /* any key identifier */
skipping to change at page 74, line 40 skipping to change at page 79, line 14
/* /*
* main() - main program * main() - main program
*/ */
int int
main() main()
{ {
struct p *p; /* peer structure pointer */ struct p *p; /* peer structure pointer */
struct r *r; /* receive packet pointer */ struct r *r; /* receive packet pointer */
/* /*
* Read command line options and initialize system * Read command line options and initialize system variables.
variables. * Implementations MAY measure the precision * Implementations MAY measure the precision specific
specific * to each machine by measuring the clock * to each machine by measuring the clock increments to read the
increments to read the * system clock. * system clock.
*/ */
memset(&s, sizeof(s), 0); memset(&s, sizeof(s), 0);
s.leap = NOSYNC; s.leap = NOSYNC;
s.stratum = MAXSTRAT; s.stratum = MAXSTRAT;
s.poll = MINPOLL; s.poll = MINPOLL;
s.precision = PRECISION; s.precision = PRECISION;
s.p = NULL; s.p = NULL;
/* /*
* Initialize local clock variables * Initialize local clock variables
*/ */
memset(&c, sizeof(c), 0); memset(&c, sizeof(c), 0);
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);
} }
skipping to change at page 75, line 18 skipping to change at page 79, line 40
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 spcified addresses, version, mode, * associations with spcified addresses, version, mode, key ID
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.
skipping to change at page 76, line 21 skipping to change at page 80, line 44
p->version = version; p->version = version;
p->mode = mode; p->mode = mode;
p->keyid = keyid; p->keyid = keyid;
p->hpoll = MINPOLL; p->hpoll = MINPOLL;
clear(p, X_INIT); clear(p, X_INIT);
p->flags == flags; p->flags == flags;
return (p); return (p);
} }
/* /*
* clear() - reinitialize for persistent association, * clear() - reinitialize for persistent association, demobilize
demobilize * for ephemeral association. * for ephemeral association.
*/ */
void void
clear( clear(
struct p *p, /* peer structure pointer */ struct p *p, /* peer structure pointer */
int kiss /* kiss code */ int kiss /* kiss code */
) )
{ {
int i; int i;
/* /*
* The first thing to do is return all resources to * The first thing to do is return all resources to the bank.
the bank. * Typical resources are not detailed here * Typical resources are not detailed here, but they include
, but they include * dynamically allocated structures * dynamically allocated structures for keys, certificates, etc.
for keys, certificates, etc. * If an ephemeral * If an ephemeral association and not initialization, return
association and not initialization, return * the association * the association memory as well.
memory as well.
*/ */
/* return resources */ /* return resources */
if (s.p == p) if (s.p == p)
s.p = NULL; s.p = NULL;
if (kiss != X_INIT && (p->flags & P_EPHEM)) { if (kiss != X_INIT && (p->flags & P_EPHEM)) {
free(p); free(p);
return; return;
} }
/* /*
skipping to change at page 77, line 13 skipping to change at page 81, line 34
memset(BEGIN_CLEAR(p), LEN_CLEAR, 0); p->leap = NOSYNC; memset(BEGIN_CLEAR(p), LEN_CLEAR, 0); p->leap = NOSYNC;
p->stratum = MAXSTRAT; p->stratum = MAXSTRAT;
p->ppoll = MAXPOLL; p->ppoll = MAXPOLL;
p->hpoll = MINPOLL; p->hpoll = MINPOLL;
p->disp = MAXDISP; p->disp = MAXDISP;
p->jitter = LOG2D(s.precision); p->refid = kiss; p->jitter = LOG2D(s.precision); p->refid = kiss;
for (i = 0; i < NSTAGE; i++) for (i = 0; i < NSTAGE; i++)
p->f[i].disp = MAXDISP; p->f[i].disp = MAXDISP;
/* /*
* Randomize the first poll just in case thousands * Randomize the first poll just in case thousands of broadcast
of broadcast * clients have just been stirred up after * clients have just been stirred up after a long absence of the
a long absence of the * broadcast server. * broadcast server.
*/ */
p->last = p->t = c.t; p->last = p->t = c.t;
p->next = p->last + (random() & ((1 << MINPOLL) - 1)); p->next = p->last + (random() & ((1 << MINPOLL) - 1));
} }
/* /*
* md5() - compute message digest * md5() - compute message digest
*/ */
digest digest
md5( md5(
int keyid /* key identifier */ int keyid /* key identifier */
) )
{ {
/* /*
* Compute a keyed cryptographic message digest. * Compute a keyed cryptographic message digest. The key
The key * identifier is associated with a key in the local key cache.
* identifier is associated with a key in the local * The key is prepended to the packet header and extension fieds
key cache. * and the result hashed by the MD5 algorithm as described in
* The key is prepended to the packet header and * RFC-1321. Return a MAC consisting of the 32-bit key ID
extension fieds * and the result hashed by the MD5
algorithm as described in * 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 78, line 17 skipping to change at page 82, line 36
/* /*
* xmit_packet - transmit packet to network * xmit_packet - transmit packet to network
*/ */
void void
xmit_packet( xmit_packet(
struct x *x /* transmit packet pointer */ struct x *x /* transmit packet pointer */
) )
{ {
/* send packet x */ /* send packet x */
} }
A.4 Kernel System Clock Interface
* A.4. Kernel System Clock Interface
* There are three time formats: native (Unix),
NTP and floating double. /*
* The get_time() routine returns the time in NTP long * There are three time formats: native (Unix), NTP and floating double.
format. The Unix * The get_time() routine returns the time in NTP long format. The Unix
* routines expect arguments as a structure of two * routines expect arguments as a structure of two signed 32-bit words
signed 32-bit words * in seconds and microseconds (timeval) or nanoseconds (timespec). The
* in seconds and microseconds (timeval) or * step_time() and adjust_time() routines expect signed arguments in
nanoseconds (timespec). The * floating double. The simplified code shown here is for illustration
* step_time() and adjust_time() routines ex
pect signed arguments in
* floating double. The simplified code shown
here is for illustration
* only and has not been verified. * only and has not been verified.
*/ */
#define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */ #define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */
/* /*
* 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()
{ {
skipping to change at page 80, line 6 skipping to change at page 84, line 22
* Convert from double to native format (signed) and add to the * Convert from double to native format (signed) and add to the
* current time. * current time.
*/ */
ntp_time = D2LFP(offset); ntp_time = D2LFP(offset);
unix_time.tv_sec = ntp_time / 0x100000000L; unix_time.tv_sec = ntp_time / 0x100000000L;
unix_time.tv_usec = ntp_time % 0x100000000L; unix_time.tv_usec = ntp_time % 0x100000000L;
unix_time.tv_sec += unix_time.tv_usec / 1000000; unix_time.tv_sec += unix_time.tv_usec / 1000000;
unix_time.tv_usec %= 1000000; unix_time.tv_usec %= 1000000;
adjtime(&unix_time, NULL); adjtime(&unix_time, NULL);
} }
A.5 Peer Process
A.5. Peer Process
#include "ntp4.h" #include "ntp4.h"
/* /*
* A crypto-NAK packet includes the NTP header followed * A crypto-NAK packet includes the NTP header followed by a MAC
by a MAC * consisting only of the key identifier with value zero. It tells the
* consisting only of the key identifier with value zero. * receiver that a prior request could not be properly authenticated,
It tells the
* receiver that a prior request could not be properly
authenticated,
* but the NTP header fields are correct. * but the NTP header fields are correct.
* *
* A kiss-o'-death packet has an NTP header with leap 3 * A kiss-o'-death packet has an NTP header with leap 3 (NOSYNC) and
(NOSYNC) and
* stratum 0. It tells the receiver that something drastic * stratum 0. It tells the receiver that something drastic
* has happened, as revealled by the kiss code in the * has happened, as revealled by the kiss code in the refid field. The
refid field. The
* NTP header fields may or may not be correct. * NTP header fields may or may not be correct.
*/ */
/* /*
* Definitions * Definitions
*/ */
#define SGATE 3 /* spike gate (clock filter */ #define SGATE 3 /* spike gate (clock filter */
#define BDELAY .004 /* broadcast delay (s) */ #define BDELAY .004 /* broadcast delay (s) */
/* /*
* Dispatch codes * Dispatch codes
skipping to change at page 81, line 24 skipping to change at page 85, line 36
#define AUTH(x, y)((x) ? (y) == A_OK : (y) == A_OK || \ #define AUTH(x, y)((x) ? (y) == A_OK : (y) == A_OK || \
(y) == A_NONE) (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
skipping to change at page 85, line 24 skipping to change at page 89, line 35
* 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.
*/ */
skipping to change at page 85, line 50 skipping to change at page 90, line 13
* find_assoc() - find a matching association * find_assoc() - find a matching association
*/ */
struct p /* peer structure pointer or NULL */ struct p /* peer structure pointer or NULL */
*find_assoc( *find_assoc(
struct r *r /* receive packet pointer */ struct r *r /* receive packet pointer */
) )
{ {
struct p *p; /* dummy peer structure pointer */ struct p *p; /* dummy peer structure pointer */
/* /*
* Search association table for matching source * address and * Search association table for matching source
source port. * address and source port.
*/ */
while (/* all associations */ 0) { while (/* all associations */ 0) {
if (r->srcaddr == p->srcaddr && r->port == p->port) if (r->srcaddr == p->srcaddr && r->port == p->port)
return(p); return(p);
} }
return (NULL); return (NULL);
} }
A.5.2 packet()
A.5.2. 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 */
) )
skipping to change at page 87, line 40 skipping to change at page 92, line 5
} else { } else {
offset = (LFP2D(r->rec - r->org) + LFP2D(r->dst offset = (LFP2D(r->rec - r->org) + LFP2D(r->dst
r->xmt)) / 2; r->xmt)) / 2;
delay = max(LFP2D(r->dst - r->org) - LFP2D(r->rec delay = max(LFP2D(r->dst - r->org) - LFP2D(r->rec
r->xmt), LOG2D(s.precision)); r->xmt), LOG2D(s.precision));
disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI * disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI *
LFP2D(r->dst - r->org); LFP2D(r->dst - r->org);
} }
clock_filter(p, offset, delay, disp); clock_filter(p, offset, delay, disp);
} }
A.5.3 clock_filter()
A.5.3. clock_filter()
/* /*
* clock_filter(p, offset, delay, dispersion) - select the best * clock_filter(p, offset, delay, dispersion) - select the best from the
from the * latest eight delay/offset samples. * latest eight delay/offset samples.
*/ */
void void
clock_filter( clock_filter(
struct p *p, /* peer structure pointer */ struct p *p, /* peer structure pointer */
double offset, /* clock offset */ double offset, /* clock offset */
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 */
skipping to change at page 88, line 30 skipping to change at page 92, line 44
p->f[i] = p->f[i - 1]; p->f[i] = p->f[i - 1];
p->f[i].disp += PHI * (c.t - p->t); f[i] = p->f[i]; p->f[i].disp += PHI * (c.t - p->t); 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;
p->f[0].delay = delay; p->f[0].delay = delay;
p->f[0].disp = disp; p->f[0].disp = disp;
f[0] = p->f[0]; f[0] = p->f[0];
/* /*
* Sort the temporary list of tuples by increasing f[].delay. * * Sort the temporary list of tuples by increasing f[].delay.
The first entry on the sorted list represents the best * sample, * The first entry on the sorted list represents the best
but it might be old. * sample, but it might be old.
*/ */
dtemp = p->offset; dtemp = p->offset;
p->offset = f[0].offset; p->offset = f[0].offset;
p->delay = f[0].delay; p->delay = f[0].delay;
for (i = 0; i < NSTAGE; i++) { for (i = 0; i < NSTAGE; i++) {
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));
skipping to change at page 89, line 19 skipping to change at page 93, line 33
*/ */
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)
clock_select(); clock_select();
return; return;
} }
A.5.4 fast_xmit()
A.5.4. fast_xmit()
/* /*
* fast_xmit() - transmit a reply packet for receive packet r * fast_xmit() - transmit a reply packet for receive packet r
*/ */
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 * Initialize header and transmit timestamp. Note that the
the * transmit version is copied from the receive version. * transmit version is copied from the receive version. This is
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.poll = r->poll; x.stratum = s.stratum; x.poll = r->poll;
skipping to change at page 90, line 23 skipping to change at page 95, line 4
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.digest = md5(x.keyid); x.digest = md5(x.keyid);
} }
} }
xmit_packet(&x); xmit_packet(&x);
} }
A.5.5 access()
A.5.5. 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 * The access control list is an ordered set of tuples
* consisting of an address, mask and restrict word containing * consisting of an address, mask and restrict word containing
* defined bits. The list is searched for the first match on the * defined bits. The list is searched for the first match on the
* source address (r->srcaddr) and the associated restrict word * source address (r->srcaddr) and the associated restrict word
* is returned. * is returned.
*/ */
return (/* access bits */ 0); return (/* access bits */ 0);
} }
A.6 System Process
A.6. System Process
#include "ntp4.h" #include "ntp4.h"
A.6.1 clock_select() A.6.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 intersecion algorithm */ int allow, found, chime; /* used by intersecion algorithm */
int n, i, j; int n, i, j;
skipping to change at page 92, line 49 skipping to change at page 97, line 30
* nonempty, declare success. * nonempty, 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 * Clustering algorithm. Construct a list of survivors (p,
(p, * metric) from the chime list, where metric is dominated * metric) from the chime list, where metric is dominated first
first * by stratum and then by root distance. All other * by stratum and then by root distance. All other things being
things being * equal, this is the order of preference. * equal, this is the order of preference.
*/ */
n = 0; 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);
n++; n++;
skipping to change at page 94, line 33 skipping to change at page 99, line 15
* 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.6.2 root_dist()
A.6.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 */
) )
{ {
/* /*
* The root synchronization distance is the maximum error due to * The root synchronization distance is the maximum error due to
* all causes of the local clock relative to the primary server. * all causes of the local clock relative to the primary server.
* It is defined as half the total delay plus total dispersion * It is defined as half the total delay plus total dispersion
* plus peer jitter. * plus peer jitter.
*/ */
return (max(MINDISP, p->rootdelay + p->delay) / 2 + return (max(MINDISP, p->rootdelay + p->delay) / 2 +
p->rootdisp + p->disp + PHI * (c.t - p->t) + p->jitter); p->rootdisp + p->disp + PHI * (c.t - p->t) + p->jitter);
} }
A.6.3 accept()
A.6.3. accept()
/* /*
* accept() - test if association p is acceptable for * accept() - test if association p is acceptable for synchronization
synchronization
*/ */
int int
accept( accept(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
/* /*
* A stratum error occurs if (1) the server has never been * A stratum error occurs if (1) the server has never been
* synchronized, (2) the server stratum is invalid. * synchronized, (2) the server stratum is invalid.
*/ */
skipping to change at page 95, line 47 skipping to change at page 100, line 47
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);
return (TRUE); return (TRUE);
} }
A.6.4 clock_update()
A.6.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;
skipping to change at page 97, line 30 skipping to change at page 103, line 4
s.rootdisp = p->rootdisp + dtemp; break; s.rootdisp = p->rootdisp + dtemp; break;
/* /*
* Some samples are discarded while, for instance, a direct * Some samples are discarded while, for instance, a direct
* frequency measurement is being made. * frequency measurement is being made.
*/ */
case IGNORE: case IGNORE:
break; break;
} }
} }
A.6.5 clock_combine()
A.6.5. clock_combine()
/* /*
* clock_combine() - combine offsets * clock_combine() - combine offsets
*/ */
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;
skipping to change at page 98, line 14 skipping to change at page 103, line 37
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;
s.jitter = SQRT(w / y); s.jitter = SQRT(w / y);
} }
A.6.6 local_clock()
A.6.6. local_clock()
#include "ntp4.h" #include "ntp4.h"
/* /*
* Constants * Constants
*/ */
#define STEPT.128/* step threshold (s) */ #define STEPT.128/* step threshold (s) */
#define WATCH900/* stepout threshold (s) */ #define WATCH900/* stepout threshold (s) */
#define PANICT1000/* panic threshold (s) */ #define PANICT1000/* panic threshold (s) */
#define PLL65536/* PLL loop gain */ #define PLL65536/* PLL loop gain */
skipping to change at page 103, line 16 skipping to change at page 109, line 4
c.count -= s.poll << 1; if (c.count < -LIMIT) { c.count -= s.poll << 1; 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.6.7 rstclock()
A.6.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 * Enter new state and set state variables. Note we use the time
time * of the last clock filter sample, which must be earlier than
* of the last clock filter sample, which must be
earlier than
* the current time. * the current time.
*/ */
c.state = state; c.state = state;
c.base = offset - c.offset; c.base = offset - c.offset;
c.last = c.offset = offset; c.last = c.offset = offset;
s.t = t; s.t = t;
} }
A.7 Clock Adjust Process A.7. Clock Adjust Process
A.7.1 clock_adjust() A.7.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 unaccept for * MAXDIST (1 s), the server is considered unaccept for
* synchroniztion. * synchroniztion.
*/ */
c.t++; c.t++;
s.rootdisp += PHI; s.rootdisp += PHI;
skipping to change at page 104, line 48 skipping to change at page 110, line 34
if (c.t >= p->next) if (c.t >= p->next)
poll(p); poll(p);
} }
/* /*
* Once per hour write the clock frequency to a file * Once per hour write the clock frequency to a file
*/ */
if (c.t % 3600 == 3599) if (c.t % 3600 == 3599)
/* write c.freq to file */ 0; /* write c.freq to file */ 0;
} }
A.8 Poll Process
A.8. Poll Process
#include "ntp4.h" #include "ntp4.h"
/* /*
* Constants * 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) */
A.8.1 poll()
A.8.1. poll()
/* /*
* poll() - determine when to send a packet for association p-> * poll() - determine when to send a packet for association p->
*/ */
void void
poll( poll(
struct p *p /* peer structure pointer */ struct p *p /* peer structure pointer */
) )
{ {
int hpoll; int hpoll;
skipping to change at page 106, line 49 skipping to change at page 112, line 37
p->burst--; p->burst--;
} }
/* /*
* Do not transmit if in broadcast client mode. * Do not transmit if in broadcast client mode.
*/ */
if (p->mode != M_BCLN) if (p->mode != M_BCLN)
peer_xmit(p); peer_xmit(p);
poll_update(p, hpoll); poll_update(p, hpoll);
} }
A.8.2 poll_update()
A.8.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 * Note: This routine is called by both the packet() and poll() routine.
poll() routine. * Since the packet() routine is executed when a network packet arrives
* Since the packet() routine is executed when a network * and the poll() routine is executed as the result of timeout, a
packet arrives * potential race can occur, possibly causing an incorrect interval for
* and the poll() routine is executed as the result of * the next poll. This is considered so unlikely as to be negligible.
timeout, a
* potential race can occur, possibly causing an incorrect
interval for
* 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 hpoll /* poll interval (log2 s) */ int hpoll /* poll interval (log2 s) */
) )
{ {
int poll; int poll;
/* /*
skipping to change at page 108, line 4 skipping to change at page 113, line 48
/* /*
* While not shown here, an implementation * While not shown here, an implementation
* SHOULD randomize the poll interval by a small factor. * SHOULD randomize the poll interval by a small factor.
*/ */
p->next = p->last + (1 << poll); p->next = p->last + (1 << poll);
} }
/* /*
* 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->next <= c.t) if (p->next <= c.t)
p->next = c.t + 1; p->next = c.t + 1;
} }
A.8.3 transmit()
A.8.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 109, line 5 skipping to change at page 114, line 50
* 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.digest = md5(p->keyid); xmit_packet(&x); x.digest = md5(p->keyid);
xmit_packet(&x);
} }
Authors' Addresses Authors' Addresses
Jack Burbank (editor) Jack Burbank (editor)
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
William Kasch (editor)
The Johns Hopkins University Applied Physics Laboratory
11100 Johns Hopkins Road
Laurel, MD 20723-6099
US
Phone: +1 443 778 7463
Email: william.kasch@jhuapl.edu
Jim Martin (editor) Jim Martin (editor)
Netzwert AG Netzwert AG
An den Treptowers 1 An den Treptowers 1
Berlin 12435 Berlin 12435
Germany Germany
Phone: +49.30/5 900 80-1180 Phone: +49.30/5 900 80-1180
Email: jim@netzwert.ag Email: jim@netzwert.ag
Dr. David L. Mills Dr. David L. Mills
University of Delaware University of Delaware
Newark, DE 19716 Newark, DE 19716
US US
Phone: +1 302 831 8247 Phone: +1 302 831 8247
Email: mills@udel.edu Email: mills@udel.edu
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society (2006). Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property Intellectual Property
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
 End of changes. 290 change blocks. 
805 lines changed or deleted 875 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/