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