3 .\" Copyright (c) 1986, 1993
4 .\" The Regents of the University of California. All rights reserved.
6 .\" Redistribution and use in source and binary forms, with or without
7 .\" modification, are permitted provided that the following conditions
9 .\" 1. Redistributions of source code must retain the above copyright
10 .\" notice, this list of conditions and the following disclaimer.
11 .\" 2. Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
13 .\" documentation and/or other materials provided with the distribution.
14 .\" 3. Neither the name of the University nor the names of its contributors
15 .\" may be used to endorse or promote products derived from this software
16 .\" without specific prior written permission.
18 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 .\" @(#)timed.ms 8.1 (Berkeley) 6/8/93
36 Time Synchronization Protocol
38 Riccardo Gusella, Stefano Zatti, and James M. Bloom
40 Computer Systems Research Group
41 Computer Science Division
42 Department of Electrical Engineering and Computer Science
43 University of California, Berkeley
46 This work was sponsored by the Defense Advanced Research Projects Agency
47 (DoD), monitored by the Naval Electronics Systems
48 Command under contract No. N00039-84-C-0089, and by the Italian CSELT
50 The views and conclusions contained in this document are those of the
51 authors and should not be interpreted as representing official policies,
52 either expressed or implied, of the Defense Research Projects Agency,
53 of the US Government, or of CSELT.
56 .OH 'The Berkeley UNIX Time Synchronization Protocol''SMM:12-%'
57 .EH 'SMM:12-%''The Berkeley UNIX Time Synchronization Protocol'
61 The Time Synchronization Protocol (TSP)
62 has been designed for specific use by the program \fItimed\fP,
63 a local area network clock synchronizer for
64 the UNIX 4.3BSD operating
66 Timed is built on the DARPA UDP protocol [4] and
67 is based on a master slave scheme.
69 TSP serves a dual purpose.
70 First, it supports messages for the synchronization of the clocks
71 of the various hosts in a local area network.
72 Second, it supports messages for the election that occurs
73 among slave time daemons when, for any reason, the master disappears.
74 The synchronization mechanism and the election procedure
75 employed by the program timed are described
76 in other documents [1,2,3].
78 Briefly, the synchronization software, which works in a
79 local area network, consists of a collection of \fItime daemons\fP
80 (one per machine) and is based on a master-slave
82 The present implementation keeps processor clocks synchronized
83 within 20 milliseconds.
84 A \fImaster time daemon\fP measures the time
85 difference between the clock of the machine on which it
86 is running and those of all other machines. The current implementation
87 uses ICMP \fITime Stamp Requests\fP [5] to measure the clock difference
89 The master computes the \fInetwork time\fP as the average of the
90 times provided by nonfaulty clocks.\**
92 A clock is considered to be faulty when its value
93 is more than a small specified
94 interval apart from the majority of the clocks
95 of the machines on the same network.
96 See [1,2] for more details.
98 It then sends to each \fIslave time daemon\fP the
99 correction that should be performed on the clock of its machine.
100 This process is repeated periodically.
101 Since the correction is expressed as a time difference rather than an
102 absolute time, transmission delays do not interfere with synchronization.
103 When a machine comes up and joins the network,
104 it starts a slave time daemon, which
105 will ask the master for the correct time and will reset the machine's clock
106 before any user activity can begin.
107 The time daemons therefore maintain a single network time in spite of
108 the drift of clocks away from each other.
110 Additionally, a time daemon on gateway machines may run as
112 A submaster time daemon functions as a slave on one network that
113 already has a master and as master on other networks.
114 In addition, a submaster is responsible for propagating broadcast
115 packets from one network to the other.
117 To ensure that service provided is continuous and reliable,
118 it is necessary to implement an election algorithm that will elect a
119 new master should the machine running the current master crash, the master
120 terminate (for example, because of a run-time error), or the network be
122 Under our algorithm, slaves are able to realize when the master has
123 stopped functioning and to elect a new master from among themselves.
124 It is important to note that since the failure of the master results
125 only in a gradual divergence of clock values, the election
126 need not occur immediately.
128 All the communication occurring among time daemons uses the TSP
130 While some messages need not be sent in a reliable way,
131 most communication in TSP requires reliability not provided by the underlying
133 Reliability is achieved by the use of acknowledgements, sequence numbers, and
134 retransmission when message losses occur.
135 When a message that requires acknowledgment is not acknowledged after
137 the time daemon that has sent the message will assume that the
139 This document will not describe the details of how reliability is
140 implemented, but will only point out when
141 a message type requires a reliable transport mechanism.
143 The message format in TSP is the same for all message types;
144 however, in some instances, one or more fields are not used.
145 The next section describes the message format.
146 The following sections describe
147 in detail the different message types, their use and the contents
148 of each field. NOTE: The message format is likely to change in
149 future versions of timed.
154 All fields are based upon 8-bit bytes. Fields should be sent in
155 network byte order if they are more than one byte long.
156 The structure of a TSP message is the following:
158 A one byte message type.
160 A one byte version number, specifying the protocol version which the
163 A two byte sequence number to be used for recognizing duplicate messages
164 that occur when messages are retransmitted.
166 Eight bytes of packet specific data. This field contains two 4 byte time
167 values, a one byte hop count, or may be unused depending on the type
170 A zero-terminated string of up to 256 \s-2ASCII\s+2 characters with the name of
171 the machine sending the message.
173 The following charts describe the message types,
174 show their fields, and explain their usages.
175 For the purpose of the following discussion, a time daemon can
176 be considered to be in
177 one of three states: slave, master, or candidate for election to master.
178 Also, the term \fIbroadcast\fP refers to
179 the sending of a message to all active time daemons.
185 Type: TSP_ADJTIME (1)
188 The master sends this message to a slave to communicate
189 the difference between
190 the clock of the slave and
191 the network time the master has just computed.
192 The slave will accordingly
193 adjust the time of its machine.
194 This message requires an acknowledgment.
197 Acknowledgment Message
203 Both the master and the slaves use this message for
205 It is used in several different contexts, for example
206 in reply to an Adjtime message.
209 Master Request Message
212 Type: TSP_MASTERREQ (3)
215 A newly-started time daemon broadcasts this message to
216 locate a master. No other action is implied by this packet.
217 It requires a Master Acknowledgment.
220 Master Acknowledgement
223 Type: TSP_MASTERACK (4)
226 The master sends this message to acknowledge the Master Request message
227 and the Conflict Resolution Message.
230 Set Network Time Message
233 Type: TSP_SETTIME (5)
236 The master sends this message to slave time daemons to set their time.
237 This packet is sent to newly started time daemons and when the network
239 It contains the master's time as an approximation of the network time.
240 It requires an acknowledgment.
242 synchronization round will eliminate the small time difference
243 caused by the random delay in the communication channel.
246 Master Active Message
249 Type: TSP_MASTERUP (6)
252 The master broadcasts this message to
253 solicit the names of the active slaves.
254 Slaves will reply with a Slave Active message.
260 Type: TSP_SLAVEUP (7)
263 A slave sends this message to the master in answer to a Master Active message.
264 This message is also sent when a new slave starts up to inform the master that
265 it wants to be synchronized.
268 Master Candidature Message
271 Type: TSP_ELECTION (8)
274 A slave eligible to become a master broadcasts this message when its election
276 The message declares that the slave wishes to become the new master.
279 Candidature Acceptance Message
285 A slave sends this message to accept the candidature of the time daemon
286 that has broadcast an Election message.
287 The candidate will add the slave's name to the list of machines that it
288 will control should it become the master.
291 Candidature Rejection Message
294 Type: TSP_REFUSE (10)
297 After a slave accepts the candidature of a time daemon, it will reply
298 to any election messages from other slaves
300 This rejects any candidature other than the first received.
303 Multiple Master Notification Message
306 Type: TSP_CONFLICT (11)
309 When two or more masters reply to a Master Request message, the slave
310 uses this message to inform one of them that more than one master exists.
313 Conflict Resolution Message
316 Type: TSP_RESOLVE (12)
319 A master which has been informed of the existence of other masters
320 broadcasts this message to determine who the other masters are.
329 This message is sent by the master in three different contexts:
330 1) to a candidate that broadcasts a Master Candidature message,
331 2) to another master when notified of its existence,
332 3) to another master if a loop is detected.
333 In all cases, the recipient time daemon will become a slave.
334 This message requires an acknowledgement.
340 Type: TSP_SETDATE (22)
343 The program \fIdate\fP\|(1) sends this message to the local time daemon
344 when a super-user wants to set the network date.
345 If the local time daemon is the master, it will set the date;
346 if it is a slave, it will communicate the desired date to the master.
349 Set Date Request Message
352 Type: TSP_SETDATEREQ (23)
355 A slave that has received a Set Date message will communicate the
356 desired date to the master using this message.
359 Set Date Acknowledgment Message
362 Type: TSP_DATEACK (16)
365 The master sends this message to a slave in acknowledgment of a
366 Set Date Request Message.
367 The same message is sent by the local time daemon to the program
368 \fIdate(1)\fP to confirm that the network date has been set by the
372 Start Tracing Message
375 Type: TSP_TRACEON (17)
378 The controlling program \fItimedc\fP sends this message to the local
379 time daemon to start the recording in a system file of
380 all messages received.
386 Type: TSP_TRACEOFF (18)
389 \fITimedc\fP sends this message to the local
390 time daemon to stop the recording of
400 \fITimedc\fP sends this message to the local time daemon to find out
401 where the master is running.
404 Remote Master Site Message
407 Type: TSP_MSITEREQ (20)
410 A local time daemon broadcasts this message to find the location
412 It then uses the Acknowledgement message to
413 communicate this location to \fItimedc\fP.
422 For testing purposes, \fItimedc\fP sends this message to a slave
423 to cause its election timer to expire. NOTE: \fItimed\fP
424 is not normally compiled to support this.
428 Loop Detection Message
434 This packet is initiated by all masters occasionally to attempt to detect loops.
435 All submasters forward this packet onto the networks over which they are master.
436 If a master receives a packet it sent out initially,
437 it knows that a loop exists and tries to correct the problem.
441 R. Gusella and S. Zatti,
442 \fITEMPO: A Network Time Controller for Distributed Berkeley UNIX System\fP,
443 USENIX Summer Conference Proceedings, Salt Lake City, June 1984.
445 R. Gusella and S. Zatti, \fIClock Synchronization in a Local Area Network\fP,
446 University of California, Berkeley, Technical Report, \fIto appear\fP.
448 R. Gusella and S. Zatti,
449 \fIAn Election Algorithm for a Distributed Clock Synchronization Program\fP,
450 University of California, Berkeley, CS Technical Report #275, Dec. 1985.
452 Postel, J., \fIUser Datagram Protocol\fP, RFC 768.
453 Network Information Center, SRI International, Menlo Park, California,
456 Postel, J., \fIInternet Control Message Protocol\fP, RFC 792.
457 Network Information Center, SRI International, Menlo Park, California,