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