share/doc/smm/12.timed/timed.ms

   1 .\" $FreeBSD$
   2 .\"
   3 .\" Copyright (c) 1986, 1993
   4 .\"     The Regents of the University of California.  All rights reserved.
   5 .\"
   6 .\" Redistribution and use in source and binary forms, with or without
   7 .\" modification, are permitted provided that the following conditions
   8 .\" are met:
   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. All advertising materials mentioning features or use of this software
  15 .\"    must display the following acknowledgement:
  16 .\"     This product includes software developed by the University of
  17 .\"     California, Berkeley and its contributors.
  18 .\" 4. Neither the name of the University nor the names of its contributors
  19 .\"    may be used to endorse or promote products derived from this software
  20 .\"    without specific prior written permission.
  21 .\"
  22 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32 .\" SUCH DAMAGE.
  33 .\"
  34 .\"     @(#)timed.ms    8.1 (Berkeley) 6/8/93
  35 .\"
  36 .TL
  37 The Berkeley
  38 .UX
  39 .br
  40 Time Synchronization Protocol
  41 .AU
  42 Riccardo Gusella, Stefano Zatti, and James M. Bloom
  43 .AI
  44 Computer Systems Research Group
  45 Computer Science Division
  46 Department of Electrical Engineering and Computer Science
  47 University of California, Berkeley
  48 Berkeley, CA 94720
  49 .FS
  50 This work was sponsored by the Defense Advanced Research Projects Agency
  51 (DoD), monitored by the Naval Electronics Systems
  52 Command under contract No. N00039-84-C-0089, and by the Italian CSELT
  53 Corporation.
  54 The views and conclusions contained in this document are those of the
  55 authors and should not be interpreted as representing official policies,
  56 either expressed or implied, of the Defense Research Projects Agency,
  57 of the US Government, or of CSELT.
  58 .FE
  59 .LP
  60 .OH 'The Berkeley UNIX Time Synchronization Protocol''SMM:12-%'
  61 .EH 'SMM:12-%''The Berkeley UNIX Time Synchronization Protocol'
  62 .SH
  63 Introduction
  64 .PP
  65 The Time Synchronization Protocol (TSP)
  66 has been designed for specific use by the program \fItimed\fP,
  67 a local area network clock synchronizer for
  68 the UNIX 4.3BSD operating
  69 system.
  70 Timed is built on the DARPA UDP protocol [4] and
  71 is based on a master slave scheme.
  72 .PP
  73 TSP serves a dual purpose.
  74 First, it supports messages for the synchronization of the clocks
  75 of the various hosts in a local area network.
  76 Second, it supports messages for the election that occurs
  77 among slave time daemons when, for any reason, the master disappears.
  78 The synchronization mechanism and the election procedure
  79 employed by the program timed are described
  80 in other documents [1,2,3].
  81 .PP
  82 Briefly, the synchronization software, which works in a
  83 local area network, consists of a collection of \fItime daemons\fP
  84 (one per machine) and is based on a master-slave
  85 structure.
  86 The present implementation keeps processor clocks synchronized
  87 within 20 milliseconds.
  88 A \fImaster time daemon\fP measures the time
  89 difference between the clock of the machine on which it
  90 is running and those of all other machines.  The current implementation
  91 uses ICMP \fITime Stamp Requests\fP [5] to measure the clock difference
  92 between machines.
  93 The master computes the \fInetwork time\fP as the average of the
  94 times provided by nonfaulty clocks.\**
  95 .FS
  96 A clock is considered to be faulty when its value
  97 is more than a small specified
  98 interval apart from the majority of the clocks
  99 of the machines on the same network.
 100 See [1,2] for more details.
 101 .FE
 102 It then sends to each \fIslave time daemon\fP the
 103 correction that should be performed on the clock of its machine.
 104 This process is repeated periodically.
 105 Since the correction is expressed as a time difference rather than an
 106 absolute time, transmission delays do not interfere with synchronization.
 107 When a machine comes up and joins the network,
 108 it starts a slave time daemon, which
 109 will ask the master for the correct time and will reset the machine's clock
 110 before any user activity can begin.
 111 The time daemons therefore maintain a single network time in spite of
 112 the drift of clocks away from each other.
 113 .PP
 114 Additionally, a time daemon on gateway machines may run as
 115 a \fIsubmaster\fP.
 116 A submaster time daemon functions as a slave on one network that
 117 already has a master and as master on other networks.
 118 In addition, a submaster is responsible for propagating broadcast
 119 packets from one network to the other.
 120 .PP
 121 To ensure that service provided is continuous and reliable,
 122 it is necessary to implement an election algorithm that will elect a
 123 new master should the machine running the current master crash, the master
 124 terminate (for example, because of a run-time error), or the network be
 125 partitioned.
 126 Under our algorithm, slaves are able to realize when the master has
 127 stopped functioning and to elect a new master from among themselves.
 128 It is important to note that since the failure of the master results
 129 only in a gradual divergence of clock values, the election
 130 need not occur immediately.
 131 .PP
 132 All the communication occurring among time daemons uses the TSP
 133 protocol.
 134 While some messages need not be sent in a reliable way,
 135 most communication in TSP requires reliability not provided by the underlying
 136 protocol.
 137 Reliability is achieved by the use of acknowledgements, sequence numbers, and
 138 retransmission when message losses occur.
 139 When a message that requires acknowledgment is not acknowledged after
 140 multiple attempts,
 141 the time daemon that has sent the message will assume that the
 142 addressee is down.
 143 This document will not describe the details of how reliability is
 144 implemented, but will only point out when
 145 a message type requires a reliable transport mechanism.
 146 .PP
 147 The message format in TSP is the same for all message types;
 148 however, in some instances, one or more fields are not used.
 149 The next section describes the message format.
 150 The following sections describe
 151 in detail the different message types, their use and the contents
 152 of each field.  NOTE:  The message format is likely to change in
 153 future versions of timed.
 154 .sp 2
 155 .SH
 156 Message Format
 157 .PP
 158 All fields are based upon 8-bit bytes.  Fields should be sent in
 159 network byte order if they are more than one byte long.
 160 The structure of a TSP message is the following:
 161 .IP 1)
 162 A one byte message type.
 163 .IP 2)
 164 A one byte version number, specifying the protocol version which the
 165 message uses.
 166 .IP 3)
 167 A two byte sequence number to be used for recognizing duplicate messages
 168 that occur when messages are retransmitted.
 169 .IP 4)
 170 Eight bytes of packet specific data.  This field contains two 4 byte time
 171 values, a one byte hop count, or may be unused depending on the type
 172 of the packet.
 173 .IP 5)
 174 A zero-terminated string of up to 256 \s-2ASCII\s+2 characters with the name of
 175 the machine sending the message.
 176 .PP
 177 The following charts describe the message types,
 178 show their fields, and explain their usages.
 179 For the purpose of the following discussion, a time daemon can
 180 be considered to be in
 181 one of three states: slave, master, or candidate for election to master.
 182 Also, the term \fIbroadcast\fP refers to
 183 the sending of a message to all active time daemons.
 184 .sp 1
 185 .SH
 186 Adjtime Message
 187 .so time
 188 .LP
 189 Type: TSP_ADJTIME (1)
 190 .sp 1
 191 .PP
 192 The master sends this message to a slave to communicate
 193 the difference between
 194 the clock of the slave and
 195 the network time the master has just computed.
 196 The slave will accordingly
 197 adjust the time of its machine.
 198 This message requires an acknowledgment.
 199 .sp 1
 200 .SH
 201 Acknowledgment Message
 202 .so unused
 203 .LP
 204 Type: TSP_ACK (2)
 205 .sp 1
 206 .PP
 207 Both the master and the slaves use this message for
 208 acknowledgment only.
 209 It is used in several different contexts, for example
 210 in reply to an Adjtime message.
 211 .sp 1
 212 .SH
 213 Master Request Message
 214 .so unused
 215 .LP
 216 Type: TSP_MASTERREQ (3)
 217 .sp 1
 218 .PP
 219 A newly-started time daemon broadcasts this message to
 220 locate a master.  No other action is implied by this packet.
 221 It requires a Master Acknowledgment.
 222 .sp 1
 223 .SH
 224 Master Acknowledgement
 225 .so unused
 226 .LP
 227 Type: TSP_MASTERACK (4)
 228 .sp 1
 229 .PP
 230 The master sends this message to acknowledge the Master Request message
 231 and the Conflict Resolution Message.
 232 .sp 1
 233 .SH
 234 Set Network Time Message
 235 .so date
 236 .LP
 237 Type: TSP_SETTIME (5)
 238 .sp 1
 239 .PP
 240 The master sends this message to slave time daemons to set their time.
 241 This packet is sent to newly started time daemons and when the network
 242 date is changed.
 243 It contains the master's time as an approximation of the network time.
 244 It requires an acknowledgment.
 245 The next
 246 synchronization round will eliminate the small time difference
 247 caused by the random delay in the communication channel.
 248 .sp 1
 249 .SH
 250 Master Active Message
 251 .so unused
 252 .LP
 253 Type: TSP_MASTERUP (6)
 254 .sp 1
 255 .PP
 256 The master broadcasts this message to
 257 solicit the names of the active slaves.
 258 Slaves will reply with a Slave Active message.
 259 .sp 1
 260 .SH
 261 Slave Active Message
 262 .so unused
 263 .LP
 264 Type: TSP_SLAVEUP (7)
 265 .sp 1
 266 .PP
 267 A slave sends this message to the master in answer to a Master Active message.
 268 This message is also sent when a new slave starts up to inform the master that
 269 it wants to be synchronized.
 270 .sp 1
 271 .SH
 272 Master Candidature Message
 273 .so unused
 274 .LP
 275 Type: TSP_ELECTION (8)
 276 .sp 1
 277 .PP
 278 A slave eligible to become a master broadcasts this message when its election
 279 timer expires.
 280 The message declares that the slave wishes to become the new master.
 281 .sp 1
 282 .SH
 283 Candidature Acceptance Message
 284 .so unused
 285 .LP
 286 Type: TSP_ACCEPT (9)
 287 .sp 1
 288 .PP
 289 A slave sends this message to accept the candidature of the time daemon
 290 that has broadcast an Election message.
 291 The candidate will add the slave's name to the list of machines that it
 292 will control should it become the master.
 293 .sp 1
 294 .SH
 295 Candidature Rejection Message
 296 .so unused
 297 .LP
 298 Type: TSP_REFUSE (10)
 299 .sp 1
 300 .PP
 301 After a slave accepts the candidature of a time daemon, it will reply
 302 to any election messages from other slaves
 303 with this message.
 304 This rejects any candidature other than the first received.
 305 .sp 1
 306 .SH
 307 Multiple Master Notification Message
 308 .so unused
 309 .LP
 310 Type: TSP_CONFLICT (11)
 311 .sp 1
 312 .PP
 313 When two or more masters reply to a Master Request message, the slave
 314 uses this message to inform one of them that more than one master exists.
 315 .sp 1
 316 .SH
 317 Conflict Resolution Message
 318 .so unused
 319 .LP
 320 Type: TSP_RESOLVE (12)
 321 .sp 1
 322 .PP
 323 A master which has been informed of the existence of other masters
 324 broadcasts this message to determine who the other masters are.
 325 .sp 1
 326 .SH
 327 Quit Message
 328 .so unused
 329 .LP
 330 Type: TSP_QUIT (13)
 331 .sp 1
 332 .PP
 333 This message is sent by the master in three different contexts:
 334 1) to a candidate that broadcasts a Master Candidature message,
 335 2) to another master when notified of its existence,
 336 3) to another master if a loop is detected.
 337 In all cases, the recipient time daemon will become a slave.
 338 This message requires an acknowledgement.
 339 .sp 1
 340 .SH
 341 Set Date Message
 342 .so date
 343 .LP
 344 Type: TSP_SETDATE (22)
 345 .sp 1
 346 .PP
 347 The program \fIdate\fP\|(1) sends this message to the local time daemon
 348 when a super-user wants to set the network date.
 349 If the local time daemon is the master, it will set the date;
 350 if it is a slave, it will communicate the desired date to the master.
 351 .sp 1
 352 .SH
 353 Set Date Request Message
 354 .so date
 355 .LP
 356 Type: TSP_SETDATEREQ (23)
 357 .sp 1
 358 .PP
 359 A slave that has received a Set Date message will communicate the
 360 desired date to the master using this message.
 361 .sp 1
 362 .SH
 363 Set Date Acknowledgment Message
 364 .so unused
 365 .LP
 366 Type: TSP_DATEACK (16)
 367 .sp 1
 368 .PP
 369 The master sends this message to a slave in acknowledgment of a
 370 Set Date Request Message.
 371 The same message is sent by the local time daemon to the program
 372 \fIdate(1)\fP to confirm that the network date has been set by the
 373 master.
 374 .sp 1
 375 .SH
 376 Start Tracing Message
 377 .so unused
 378 .LP
 379 Type: TSP_TRACEON (17)
 380 .sp 1
 381 .PP
 382 The controlling program \fItimedc\fP sends this message to the local
 383 time daemon to start the recording in a system file of
 384 all messages received.
 385 .sp 1
 386 .SH
 387 Stop Tracing Message
 388 .so unused
 389 .LP
 390 Type: TSP_TRACEOFF (18)
 391 .sp 1
 392 .PP
 393 \fITimedc\fP sends this message to the local
 394 time daemon to stop the recording of
 395 messages received.
 396 .sp 1
 397 .SH
 398 Master Site Message
 399 .so unused
 400 .LP
 401 Type: TSP_MSITE (19)
 402 .sp 1
 403 .PP
 404 \fITimedc\fP sends this message to the local time daemon to find out
 405 where the master is running.
 406 .sp 1
 407 .SH
 408 Remote Master Site Message
 409 .so unused
 410 .LP
 411 Type: TSP_MSITEREQ (20)
 412 .sp 1
 413 .PP
 414 A local time daemon broadcasts this message to find the location
 415 of the master.
 416 It then uses the Acknowledgement message to
 417 communicate this location to \fItimedc\fP.
 418 .sp 1
 419 .SH
 420 Test Message
 421 .so unused
 422 .LP
 423 Type: TSP_TEST (21)
 424 .sp 1
 425 .PP
 426 For testing purposes, \fItimedc\fP sends this message to a slave
 427 to cause its election timer to expire.  NOTE: \fItimed\fP
 428 is not normally compiled to support this.
 429 .sp 1
 430 .SH
 431 .SH
 432 Loop Detection Message
 433 .so loop
 434 .LP
 435 Type: TSP_LOOP (24)
 436 .sp 1
 437 .PP
 438 This packet is initiated by all masters occasionally to attempt to detect loops.
 439 All submasters forward this packet onto the networks over which they are master.
 440 If a master receives a packet it sent out initially,
 441 it knows that a loop exists and tries to correct the problem.
 442 .SH
 443 References
 444 .IP 1.
 445 R. Gusella and S. Zatti,
 446 \fITEMPO: A Network Time Controller for Distributed Berkeley UNIX System\fP,
 447 USENIX Summer Conference Proceedings, Salt Lake City, June 1984.
 448 .IP 2.
 449 R. Gusella and S. Zatti, \fIClock Synchronization in a Local Area Network\fP,
 450 University of California, Berkeley, Technical Report, \fIto appear\fP.
 451 .IP 3.
 452 R. Gusella and S. Zatti,
 453 \fIAn Election Algorithm for a Distributed Clock Synchronization Program\fP,
 454 University of California, Berkeley, CS Technical Report #275, Dec. 1985.
 455 .IP 4.
 456 Postel, J., \fIUser Datagram Protocol\fP, RFC 768.
 457 Network Information Center, SRI International, Menlo Park, California,
 458 August 1980.
 459 .IP 5.
 460 Postel, J., \fIInternet Control Message Protocol\fP, RFC 792.
 461 Network Information Center, SRI International, Menlo Park, California,
 462 September 1981.