Return to timed.ms CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 22.timed

Annotation of 43BSDReno/share/doc/smm/22.timed/timed.ms, revision 1.1

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.