-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNTP_Notes.txt
235 lines (198 loc) · 10.4 KB
/
NTP_Notes.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
Network Time Protocol (NTP) Notes
---------------------------------
Versions:
---------
NTPv0: RFC 778 (1981)
NTPv1: RFC 1059 (1998)
NTPv2: RFC 1119 (1989)
NTPv3: RFC 1305 (1992)
NTPv4: RFC 5905 (2010)
Simple Network Time Protocol (SNTP):
------------------------------------
Simplified version of NTP (does not support some features).
SNTPv4: RFC 5905 (2010)
Below, anything not supported by SNTP will be called out explicitly.
Applications:
Primary Servers with a single reference clock.
Clients with a single upstream server and no dependent clients/servers.
Not applicable for Secondary Servers.
General:
--------
Original author and principal maintainer through v4: David L. Mills of
University of Delaware.
Messages exchanged via UDP on port 123
Architecture:
-------------
Every node (machine or software instance) implementing NTP acts in one of the
following roles:
Primary Server - Synchronized directly to a reference clock. Has no
upstream server. Has one or more downstream server or
client.
Secondary Server - Has one or more upstream servers and one or more
downstream servers or clients
Client - Synchronized to one or more servers but does not provide
synchronization to dependent clients
Network topology formed by such servers and clients is organized and dynamically
re-organized as needed to produce the shortest-distance spanning tree rooted at
a primary server (I guess it uses something called a "Bellman-Ford routing
algorithm").
Server Responsibilities:
------------------------
Return response to client packet
Retain no state
Each server is assigned a 'stratum' indicating how many levels it is removed
from a primary server in a network. Primary servers have stratum 1. Secondary
servers have stratum 1 greater than that of their upstream server.
Stratum 0 devices are precision reference clocks (i.e. atomic clocks, radio
clocks, GNSS or GPS synchronized, PTP synchronized), but an NTP server cannot
advertise itself as stratum 0 ('0' in the field indicates 'unspecified').
Client Responsibilities:
------------------------
A client sends messages to a server every 2**T seconds where the "poll
exponent" T ranges from 4 (16s) to 17 (36hrs). The value of T is determined
by the the Clock Discipline Algorithm (see below) to match the control loop
time constant (Tc). The server responds to messages with an update interval
of 'mu' seconds. For a stateless server, 'mu' = 2**T since it will respond
immediately to any received messages. For an association of peer servers,
both sides must agree on a common poll exponent (equal to the minimum of the
values computed independently by both peers). The NTP protocol provides a
negotiation mechanism for this purpose.
Retain state after response from server in the form of an association
Protocol Variants:
------------------
In the table below, each association (role and protocol variant) corresponds
to both an integer indicating the association and one indicating the packet
mode (for all roles that generate packets).
Association Mode iAssocMode iPacketMode
-----------------------------------------
Symmetric-Active 1 1 or 2
Symmetric-Passive 2 1
Client 3 4
Server 4 3
Broadcast Server 5 5
Broadcast Client 6 (n/a)
Symmetric:
----------
Nodes operate as 'peers', implementing both server and client roles using
either a 'symmetric-active' or a 'symmetric-passive' association.
A symmetric-active node sends mode-1 packets to packets to a symmetric-
active peer association. Alternatively a symmetric-passive association
can be mobilized upon arrival of a mode-1 packet which then sends mode-2
packets until timeout or error.
Client/Server:
--------------
Client sends mode-3 (client) packets to server. Server responds with
mode-4 (server) packets containing synchronization information.
Servers provide synchronization information to one or more clients but do
not accept synchronization from them.
Broadcast:
----------
A broadcaster node sends periodic mode-5 packets which are received by
one or more mode-6 (broadcast client) associations.
Dynamic Server Discovery:
-------------------------
There are two special associations - 'manycast server' and 'manycast client'
- which provide a dynamic server discovery function. A client first sends a
mode-3 packet with a time-to-live (TTL) value of 1 to a specially designated
IPv4 or IPv6 broadcast or multicast group address. Recall that TTL value is
decremented at each hop and the packet is dropped when TTL reaches 0. If no
response is received from the mode-3 packet, TTL is increased to 2 and the
packet is re-sent. When the client receives a response from an NTP server,
an ephemeral association is mobilized for a pre-determined timeout. The
client continues to increment TTL and send mode-3 packets until enough
associations are mobilized to perform the mitigation algorithms (described
below). If TTL reaches the maximum value of 255 without enough associations
mobilized, it will stop transmission for a timeout period to demobilize all
ephemeral associations. The mitigation algorithms are run on all mobilized
associations to identify and use only the best candidates while all others
are allowed to timeout and de-mobilize.
Setting System Clock:
---------------------
The client platform (operating system) is assumed to provide two functions
for controlling the system clock.
The "time set" function (e.g. Unix settimeofday()) is used to set the system
time directly which the "clock adjust" function (e.g. Unix adjtime()) is
used to advance or retard the current time by a small amount. The NTP clock
discipline algorithm will use the former if the adjustment is above a
certain threshold and the latter when it is below that threshold.
Terminology:
------------
Association A data structure for time keeping. Can be 'persistent',
'ephemeral', or 'preemptable'.
Algorithms:
-----------
The client keeps track of the following statistical values and updates them
after each message received from each server.
Hardware-specific:
------------------
Frequency tolerance (PHI): The maximum disciplined clock frequency
uncertainty for a given system clock
Association-specific:
---------------------
Upon receipt of each packet from a server, the client computes all of the
following values. A copy of these exists for every association (for every
server that responds to that client).
Offset (theta): The time offset between system clock and server clock
This is the offset of maximum likelihood (compensating for
path delays and tolerances)
Delay (delta): The round-trip delay between client and server
Jitter (phi): RMS average of most recent offset (theta) values
Dispersion (epsilon): The maximum error inherent in a measurement (depends
on PHI, among other factors)
Combined Statistics:
--------------------
There exists only a single instance of each of these values kept by the
client.
System Offset (THETA): The average (possibly weighted?) of individual offsets
(theta) for each association.
System Jitter (scripty theta): The nominal error in estimating system offset
computed as the RMS average of difference between past system
offsets (RMS average of dTHETA = THETA[n+1] - THETA[n])
Root Delay (DELTA): The accumulation of delay of each stratum from the root
reference clock.
Root Dispersion (EPSILON): The accumulation of dispersion for each stratum
from the root reference clock.
Synchronization Distance (GAMMA): The maximum error due to all causes.
GAMMA = EPSILON + DELTA/2
Selection Algorithm:
--------------------
Uses Byzantine principles to cull "falsetickers" from the population of
associations (removing any clocks that seem wildly wrong). This selection
process leaves a collection of "truechimers" (clocks that seem ok).
Clustering Algorithm:
---------------------
Using statistical principles, condenses the collection of "truechimers" to
a smaller batch of "survivors" which are deemed most accurate.
Combining Algorithm:
--------------------
Computes a final clock offset from the pool of "survivors" from the
clustering algorithm (basically just averages the values).
Clock Discipline Process:
-------------------------
Feedback-based approach to controlling the system clock frequency to minimize
the final clock offset (better synchronize with UTC).
Clock Adjust Process:
---------------------
I don't know why this exists beyond the discipline process.
Apparently this runs once a second to "inject a computed time offset and
maintain constant frequency" according to Mills.
Data Types, Values, and Packets:
--------------------------------
All time values are represented in twos-complement.
Network byte order (big-endian, zero at LHS).
Data Types:
-----------
NTP Date Format (128b) : | [0:31] Era | [32:63] Timestamp | [64:127] Fraction |
Used where sufficient word size and storage is available.
Era is SIGNED integer. Era 0 starts Jan 1, 1900 at 00:00. Era lasts for
2**32-1 seconds = 136 years, 36 days, 6 hrs, 28 min, 15 sec
Timestamp is UNSIGNED integer.
NTP Timestamp Format (64b) : | [0:31] Timestamp | [32:63] Fraction |
Used in packet headers and anywhere else with limited word size
Timestamp is the same as that of the Data Format above. Era must be
divined by other means (e.g. querying whether computers exist). Without
era information, we can't distinguish between (e.g.) January of 1900 and
February of 2036.
NTP Short Format (32b) : | [0:15] Seconds | [16:31] Fraction |
Used in delay and dispersion header fields where range/resolution of other
field types are not needed.