1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" &lt;html>
4
<meta name="generator" content="HTML Tidy, see www.w3.org">
5
<title>Executive Summary - Computer Network Time
6
Synchronization</title>
9
<h3>Executive Summary - Computer Network Time Synchronization</h3>
11
<img align="left" src="pic/alice12.gif" alt="gif"><a href=
12
"pictures.htm">from <i>Alice's Adventures in Wonderland</i>, Lewis
15
<p>The executive is the one on the left.<br clear="left">
21
<p>The standard timescale used by most nations of the world is
22
Coordinated UniversalTime (UTC), which is based on the Earth's
23
rotation about its axis, and the Gregorian Calendar, which is based
24
on the Earth's rotation about the Sun. The UTC timescale is
25
disciplined with respect to International Atomic Time (TAI) by
26
inserting leap seconds at intervals of about 18 months. UTC time is
27
disseminated by various means, including radio and satellite
28
navigation systems, telephone modems and portable clocks.</p>
30
<p>Special purpose receivers are available for many
31
time-dissemination services, including the Global Position System
32
(GPS) and other services operated by various national governments.
33
For reasons of cost and convenience, it is not possible to equip
34
every computer with one of these receivers. However, it is possible
35
to equip some number of computers acting as primary time servers to
36
synchronize a much larger number of secondary servers and clients
37
connected by a common network. In order to do this, a distributed
38
network clock synchronization protocol is required which can read a
39
server clock, transmit the reading to one or more clients and
40
adjust each client clock as required. Protocols that do this
41
include the Network Time Protocol (NTP), Digital Time
42
Synchronization Protocol (DTSS) and others found in the literature
43
(See "Further Reading" at the end of this article.)</p>
45
<h4>Protocol Design Issues</h4>
47
<p>The synchronization protocol determines the time offset of the
48
server clock relative to the client clock. The various
49
synchronization protocols in use today provide different means to
50
do this, but they all follow the same general model. On request,
51
the server sends a message including its current clock value or <i>
52
timestamp</i> and the client records its own timestamp upon arrival
53
of the message. For the best accuracy, the client needs to measure
54
the server-client propagation delay to determine its clock offset
55
relative to the server. Since it is not possible to determine the
56
one-way delays, unless the actual clock offset is known, the
57
protocol measures the total roundtrip delay and assumes the
58
propagation times are statistically equal in each direction. In
59
general, this is a useful approximation; however, in the Internet
60
of today, network paths and the associated delays can differ
61
significantly due to the individual service providers.</p>
63
<p>The community served by the synchronization protocol can be very
64
large. For instance, the NTP community in the Internet of 1998
65
includes over 230 primary time servers, synchronized by radio,
66
satellite and modem, and well over 100,000 secondary servers and
67
clients. In addition, there are many thousands of private
68
communities in large government, corporate and institution
69
networks. Each community is organized as a tree graph or <i>
70
subnet</i>, with the primary servers at the root and secondary
71
servers and clients at increasing hop count, or stratum level, in
72
corporate, department and desktop networks. It is usually necessary
73
at each stratum level to employ redundant servers and diverse
74
network paths in order to protect against broken software, hardware
75
and network links.</p>
77
<p>Synchronization protocols work in one or more association modes,
78
depending on the protocol design. Client/server mode, also called
79
master/slave mode, is supported in both DTSS and NTP. In this mode,
80
a client synchronizes to a stateless server as in the conventional
81
RPC model. NTP also supports symmetric mode, which allows either of
82
two peer servers to synchronize to the other, in order to provide
83
mutual backup. DTSS and NTP support a broadcast mode which allows
84
many clients to synchronize to one or a few servers, reducing
85
network traffic when large numbers of clients are involved. In NTP,
86
IP multicast can be used when the subnet spans multiple
89
<p>Configuration management can be a serious problem in large
90
subnets. Various schemes which index public databases and network
91
directory services are used in DTSS and NTP to discover servers.
92
Both protocols use broadcast modes to support large client
93
populations; but, since listen-only clients cannot calibrate the
94
delay, accuracy can suffer. In NTP, clients determine the delay at
95
the time a server is first discovered by polling the server in
96
client/server mode and then reverting to listen-only mode. In
97
addition, NTP clients can broadcast a special "manycast" message to
98
solicit responses from nearby servers and continue in client/server
99
mode with the respondents.</p>
101
<h4>Security Issues</h4>
103
<p>A reliable network time service requires provisions to prevent
104
accidental or malicious attacks on the servers and clients in the
105
network. Reliability requires that clients can determine that
106
received messages are authentic; that is, were actually sent by the
107
intended server and not manufactured or modified by an intruder.
108
Ubiquity requires that any client can verify the authenticity of
109
any server using only public information. This is especially
110
important in such ubiquitous network services as directory
111
services, cryptographic key management and time
114
<p>NTP includes provisions to cryptographically authenticate
115
individual servers using symmetric-key cryptography in which
116
clients authenticate servers using shared secret keys. However, the
117
secret keys must be distributed in advance using secure means
118
beyond the scope of the protocol. This can be awkward and fragile
119
with a large population of potential clients, possibly intruding
122
<p>Modern public-key cryptography provides means to reliably bind
123
the server identification credentials and related public values
124
using public directory services. However, these means carry a high
125
computing cost, especially when large numbers of time-critical
126
clients are involved as often the case with NTP servers. In
127
addition, there are problems unique to NTP in the interaction
128
between the authentication and synchronization functions, since
129
each requires the other for success.</p>
131
<p>The recent NTP Version 4 includes a revised security model and
132
authentication scheme supporting both symmetric and public-key
133
cryptography. The public-key variant is specially crafted to reduce
134
the risk of intrusion, minimize the consumption of processor
135
resources and minimize the vulnerability to hacker attack.</p>
137
<h4>Computer Clock Modelling and Error Analysis</h4>
139
Most computers include a quartz resonator-stabilized oscillator and
140
hardware counter that interrupts the processor at intervals of a
141
few milliseconds. At each interrupt, a quantity called <i>tick</i>
142
is added to a system variable representing the clock time. The
143
clock can be read by system and application programs and set on
144
occasion to an external reference. Once set, the clock readings
145
increment at a nominal rate, depending on the value of <i>tick</i>.
146
Typical Unix system kernels provide a programmable mechanism to
147
increase or decrease the value of <i>tick</i> by a small, fixed
148
amount in order to amortize a given time adjustment smoothly over
149
multiple <i>tick</i> intervals.
151
<p>Clock errors are due to variations in network delay and
152
latencies in computer hardware and software (jitter), as well as
153
clock oscillator instability (wander). The time of a client
154
relative to its server can be expressed</p>
156
<center><i>T</i>(<i>t</i>) = <i>T</i>(<i>t</i><sub>0</sub>) + <i>
157
R</i>(<i>t - t</i><sub>0</sub>) + 1/2 <i>D</i>(<i>t -
158
t</i><sub>0</sub>)<sup>2</sup>,</center>
160
<p>where <i>t</i> is the current time, <i>T</i> is the time offset
161
at the last measurement update <i>t</i><sub>0</sub>, <i>R</i> is
162
the frequency offset and <i>D</i> is the drift due to resonator
163
ageing. All three terms include systematic offsets that can be
164
corrected and random variations that cannot. Some protocols,
165
including DTSS, estimate only the first term in this expression,
166
while others, including NTP, estimate the first two terms. Errors
167
due to the third term, while important to model resonator aging in
168
precision applications, are neglected, since they are usually
169
dominated by errors in the first two terms.</p>
171
<p>The synchronization protocol estimates <i>
172
T</i>(<i>t</i><sub>0</sub>) (and <i>R</i>(<i>t</i><sub>0</sub>),
173
where relevant) at regular intervals <font face="symbol">t</font>
174
and adjusts the clock to minimize <i>T</i>(<i>t</i>) in future. In
175
common cases, <i>R</i> can have systematic offsets of several
176
hundred parts-per-million (PPM) with random variations of several
177
PPM due to ambient temperature changes. If not corrected, the
178
resulting errors can accumulate to seconds per day. In order that
179
these errors do not exceed a nominal specification, the protocol
180
must periodically re-estimate <i>T</i> and <i>R</i> and compensate
181
for variations by adjusting the clock at regular intervals. As a
182
practical matter, for nominal accuracies of tens of milliseconds,
183
this requires clients to exchange messages with servers at
184
intervals in the order of tens of minutes.</p>
186
<p>Analysis of quartz-resonator stabilized oscillators show that
187
errors are a function of the averaging time, which in turn depends
188
on the interval between corrections. At correction intervals less
189
than a few hundred seconds, errors are dominated by jitter, while,
190
at intervals greater than this, errors are dominated by wander. As
191
explained later, the characteristics of each regime determine the
192
algorithm used to discipline the clock. These errors accumulate at
193
each stratum level from the root to the leaves of the subnet tree.
194
It is possible to quantify these errors by statistical means, as in
195
NTP. This allows real-time applications to adjust audio or video
196
playout delay, for example. However, the required statistics may be
197
different for various classes of applications. Some applications
198
need absolute error bounds guaranteed never to exceeded, as
199
provided by the following correctness principles.</p>
201
<h4>Correctness Principles</h4>
203
<p>Applications requiring reliable time synchronization such as air
204
traffic control must have confidence that the local clock is
205
correct within some bound relative to a given timescale such as
206
UTC. There is a considerable body of literature that studies these
207
issues with respect to various failure models such as fail-stop and
208
Byzantine disagreement. While these models inspire much confidence
209
in a theoretical setting, most require multiple message rounds for
210
each measurement and would be impractical in a large computer
211
network such as the Internet. However, it can be shown that the
212
worst-case error in reading a remote server clock cannot exceed
213
one-half the roundtrip delay measured by the client. This is a
214
valuable insight, since it permits strong statements about the
215
correctness of the timekeeping system.</p>
217
<p>In the Probabilistic Clock Synchronization (PCS) scheme devised
218
by Cristian, a maximum error tolerance is established in advance
219
and time value samples associated with roundtrip delays that exceed
220
twice this value are discarded. By the above argument, the
221
remaining samples must represent time values within the specified
222
tolerance. As the tolerance is decreased, more samples fail the
223
test until a point where no samples survive. The tolerance can be
224
adjusted for the best compromise between the highest accuracy
225
consistent with acceptable sample survival rate.</p>
227
<p>In a scheme devised by Marzullo and exploited in NTP and DTSS,
228
the worst-case error determined for each server determines a
229
correctness interval. If each of a number of servers are in fact
230
synchronized to a common timescale, the actual time must be
231
contained in the intersection of their correctness intervals. If
232
some intervals do not intersect, then the clique containing the
233
maximum number of intersections is assumed correct <i>
234
truechimers</i> and the others assumed incorrect <i>
235
falsetickers</i>. Only the truechimers are used to adjust the
238
<h4>Data Grooming Algorithms</h4>
240
By its very nature, clock synchronization is a continuous process,
241
resulting in a sequence of measurements with each of possibly
242
several servers and resulting in a clock adjustment. In some
243
protocols, crafted algorithms are used to improve the time and
244
frequency estimates and refine the clock adjustment. Algorithms
245
described in the literature are based on trimmed-mean and median
246
filter methods. The clock filter algorithm used in NTP is based on
247
the above observation that the correctness interval depends on the
248
roundtrip delay. The algorithm accumulates offset/delay samples in
249
a window of several samples and selects the offset sample
250
associated with the minimum delay. In general, larger window sizes
251
provide better estimates; however, stability considerations limit
252
the window size to about eight.
254
<p>The same principle could be used when selecting the best subset
255
of servers and combining their offsets to determine the clock
256
adjustment. However, different servers often show different
257
systematic offsets, so the best statistic for the central tendency
258
of the server population may not be obvious. Various kinds of
259
clustering algorithms have been found useful for this purpose. The
260
one used in NTP sorts the offsets by a quality metric, then
261
calculates the variance of all servers relative to each server
262
separately. The algorithm repeatedly discards the outlyer with the
263
largest variance until further discards will not improve the
264
residual variance or until a minimum number of servers remain. The
265
final clock adjustment is computed as a weighted average of the
268
<p>At the heart of the synchronization protocol is the algorithm
269
used to adjust the system clock in accordance with the final
270
adjustment determined by the above algorithms. This is called the
271
clock discipline algorithm or simply the discipline. Such
272
algorithms can be classed according to whether they minimize the
273
time offset or frequency offset or both. For instance, the
274
discipline used in DTSS minimizes only the time offset, while the
275
one used in NTP minimizes both time and frequency offsets. While
276
the DTSS algorithm cannot remove residual errors due to systematic
277
frequency errors, the NTP algorithm is more complicated and less
278
forgiving of design and implementation mistakes.</p>
280
<p>All clock disciplines function as a feedback loop, with measured
281
offsets used to adjust the clock oscillator phase and frequency to
282
match the external synchronization source. The behavior of feedback
283
loops is well understood and modelled by mathematical analysis. The
284
significant design parameter is the time constant, or
285
responsiveness to external or internal variations in time or
286
frequency. Optimum selection of time constant depends on the
287
interval between update messages. In general, the longer these
288
intervals, the larger the time constant and vice versa. In practice
289
and with typical network configurations the optimal poll intervals
290
vary between one and twenty minutes for network paths to some
291
thousands of minutes for modem paths.</p>
293
<h4>Further Reading</h4>
297
<p>Cristian, F. Probabilistic clock synchronization. In Distributed
298
Computing 3, Springer Verlag, 1989, 146-158.</p>
302
<p>Digital Time Service Functional Specification Version T.1.0.5.
303
DigitalEquipment Corporation, 1989.</p>
307
<p>Gusella, R., and S. Zatti. TEMPO - A network time controller for
308
a distributed Berkeley UNIX system. IEEE Distributed Processing
309
Technical Committee Newsletter 6, NoSI-2 (June 1984), 7-15. Also
310
in: Proc. Summer 1984 USENIX (Salt Lake City, June 1984).</p>
314
<p>Kopetz, H., and W. Ochsenreiter. Clock synchronization in
315
distributed real-time systems. IEEE Trans. Computers C-36, 8
316
(August 1987), 933-939.</p>
320
<p>Lamport, L., and P.M. Melliar-Smith. Synchronizing clocks in the
321
presence of faults. JACM 32, 1 (January 1985), 52-78.</p>
325
<p>Marzullo, K., and S. Owicki. Maintaining the time in a
326
distributed system. ACM Operating Systems Review 19, 3 (July 1985),
331
<p>Mills, D.L. Adaptive hybrid clock discipline algorithm for the
332
Network Time Protocol. <i>IEEE/ACM Trans. Networking 6, 5</i>
333
(October 1998), 505-514.</p>
337
<p>Mills, D.L. Improved algorithms for synchronizing computer
338
network clocks. <i>IEEE/ACM Trans. Networks 3, 3</i> (June 1995),
343
<p>Mills, D.L. Internet time synchronization: the Network Time
344
Protocol. IEEE Trans. Communications COM-39, 10 (October 1991),
345
1482-1493. Also in: Yang, Z., and T.A. Marsland (Eds.). Global
346
States and Time in Distributed Systems, IEEE Press, Los Alamitos,
351
<p>Mills, D.L. Modelling and analysis of computer network clocks.
352
Electrical Engineering Department Report 92-5-2, University of
353
Delaware, May 1992, 29 pp.</p>
357
<p>NIST Time and Frequency Dissemination Services. NBS Special
358
Publication432 (Revised 1990), National Institute of Science and
359
Technology, U.S. Department of Commerce, 1990.</p>
363
<p>Schneider, F.B. A paradigm for reliable clock synchronization.
364
Department of Computer Science Technical Report TR 86-735, Cornell
365
University, February 1986.</p>
369
<p>Srikanth, T.K., and S. Toueg. Optimal clock synchronization.
370
JACM 34, 3 (July 1987), 626-645.</p>
374
<p>Stein, S.R. Frequency and time - their measurement and
375
characterization (Chapter 12). In: E.A. Gerber and A. Ballato
376
(Eds.). Precision Frequency Control, Vol. 2, Academic Press, New
377
York 1985, 191-232, 399-416. Also in: Sullivan, D.B., D.W. Allan,
378
D.A. Howe and F.L. Walls (Eds.). Characterization of Clocks and
379
Oscillators. National Institute of Standards and Technology
380
Technical Note 1337, U.S. Government Printing Office (January,
381
1990), TN61-TN119.</p>
386
<a href="index.htm"><img align="left" src="pic/home.gif" alt=
389
<address><a href="mailto:mills@udel.edu">David L. Mills
390
<mills@udel.edu></a></address>
added
removed
html/exec.htm
