TTiimmeedd IInnssttaallllaattiioonn aanndd OOppeerraattiioonn GGuuiiddee _R_i_c_c_a_r_d_o _G_u_s_e_l_l_a_, _S_t_e_f_a_n_o _Z_a_t_t_i_, _J_a_m_e_s _M_. _B_l_o_o_m Computer Systems Research Group Computer Science Division Department of Electrical Engineering and Computer Science University of California, Berkeley Berkeley, CA 94720 _K_i_r_k _S_m_i_t_h Engineering Computer Network Department of Electrical Engineering Purdue University West Lafayette, IN 47906 IInnttrroodduuccttiioonn The clock synchronization service for the UNIX 4.3BSD operating system is composed of a collection of time daemons (_t_i_m_e_d) running on the machines in a local area network. The algorithms implemented by the service is based on a mas- ter-slave scheme. The time daemons communicate with each other using the _T_i_m_e _S_y_n_c_h_r_o_n_i_z_a_t_i_o_n _P_r_o_t_o_c_o_l (TSP) which is built on the DARPA UDP protocol and described in detail in [4]. A time daemon has a twofold function. First, it sup- ports the synchronization of the clocks of the various hosts in a local area network. Second, it starts (or takes part in) the election that occurs among slave time daemons when, for any reason, the master disappears. The synchronization mechanism and the election procedure employed by the program _t_i_m_e_d are described in other documents [1,2,3]. The next paragraphs are a brief overview of how the time daemon works. This document is mainly concerned with the adminis- trative and technical issues of running _t_i_m_e_d at a particu- lar site. ----------- This work was sponsored by the Defense Advanced Research Projects Agency (DoD), monitored by the Naval Electronics Systems Command under contract No. N00039-84-C-0089, and by the CSELT Corporation of Italy. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing official poli- cies, either expressed or implied, of the Defense Research Projects Agency, of the US Government, or of CSELT. SMM:11-2 Timed Installation and Operation A _m_a_s_t_e_r _t_i_m_e _d_a_e_m_o_n measures the time differences between the clock of the machine on which it is running and those of all other machines. The master computes the _n_e_t_- _w_o_r_k _t_i_m_e as the average of the times provided by nonfaulty clocks.1 It then sends to each _s_l_a_v_e _t_i_m_e _d_a_e_m_o_n the correc- tion that should be performed on the clock of its machine. This process is repeated periodically. Since the correction is expressed as a time difference rather than an absolute time, transmission delays do not interfere with the accuracy of the synchronization. When a machine comes up and joins the network, it starts a slave time daemon which will ask the master for the correct time and will reset the machine's clock before any user activity can begin. The time daemons are able to maintain a single network time in spite of the drift of clocks away from each other. The present implemen- tation keeps processor clocks synchronized within 20 mil- liseconds. To ensure that the service provided is continuous and reliable, it is necessary to implement an election algorithm to elect a new master should the machine running the current master crash, the master terminate (for example, because of a run-time error), or the network be partitioned. Under our algorithm, slaves are able to realize when the master has stopped functioning and to elect a new master from among themselves. It is important to note that, since the failure of the master results only in a gradual divergence of clock values, the election need not occur immediately. The machines that are gateways between distinct local area networks require particular care. A time daemon on such machines may act as a _s_u_b_m_a_s_t_e_r. This artifact depends on the current inability of transmission protocols to broad- cast a message on a network other than the one to which the broadcasting machine is connected. The submaster appears as a slave on one network, and as a master on one or more of the other networks to which it is connected. A submaster classifies each network as one of three types. A _s_l_a_v_e _n_e_t_w_o_r_k is a network on which the submaster acts as a slave. There can only be one slave network. A _m_a_s_t_e_r _n_e_t_w_o_r_k is a network on which the submaster acts as a master. An _i_g_n_o_r_e_d _n_e_t_w_o_r_k is any other network which already has a valid master. The submaster tries periodi- cally to become master on an ignored network, but gives up immediately if a master already exists. ----------- 1 A clock is considered to be faulty when its value is more than a small specified interval apart from the majority of the clocks of the other machines [1,2]. Timed Installation and Operation SMM:11-3 GGuuiiddeelliinneess While the synchronization algorithm is quite general, the election one, requiring a broadcast mechanism, puts con- straints on the kind of network on which time daemons can run. The time daemon will only work on networks with broad- cast capability augmented with point-to-point links. Machines that are only connected to point-to-point, non- broadcast networks may not use the time daemon. If we exclude submasters, there will normally be, at most, one master time daemon in a local area internetwork. During an election, only one of the slave time daemons will become the new master. However, because of the characteris- tics of its machine, a slave can be prevented from becoming the master. Therefore, a subset of machines must be desig- nated as potential master time daemons. A master time dae- mon will require CPU resources proportional to the number of slaves, in general, more than a slave time daemon, so it may be advisable to limit master time daemons to machines with more powerful processors or lighter loads. Also, machines with inaccurate clocks should not be used as masters. This is a purely administrative decision: an organization may well allow all of its machines to run master time daemons. At the administrative level, a time daemon on a machine with multiple network interfaces, may be told to ignore all but one network or to ignore one network. This is done with the _-_n _n_e_t_w_o_r_k and _-_i _n_e_t_w_o_r_k options respectively at start- up time. Typically, the time daemon would be instructed to ignore all but the networks belonging to the local adminis- trative control. There are some limitations to the current implementa- tion of the time daemon. It is expected that these limita- tions will be removed in future releases. The constant NHOSTS in /usr/src/etc/timed/globals.h limits the maximum number of machines that may be directly controlled by one master time daemon. The current maximum is 29 (NHOSTS - 1). The constant must be changed and the program recompiled if a site wishes to run _t_i_m_e_d on a larger (inter)network. In addition, there is a _p_a_t_h_o_l_o_g_i_c_a_l _s_i_t_u_a_t_i_o_n to be avoided at all costs, that might occur when time daemons run on multiply-connected local area networks. In this case, as we have seen, time daemons running on gateway machines will be submasters and they will act on some of those networks as master time daemons. Consider machines A and B that are both gateways between networks X and Y. If time daemons were started on both A and B without constraints, it would be possible for submaster time daemon A to be a slave on network X and the master on network Y, while submaster time daemon B is a slave on network Y and the master on network X. This _l_o_o_p of master time daemons will not function SMM:11-4 Timed Installation and Operation properly or guarantee a unique time on both networks, and will cause the submasters to use large amounts of system resources in the form of network bandwidth and CPU time. In fact, this kind of _l_o_o_p can also be generated with more than two master time daemons, when several local area networks are interconnected. IInnssttaallllaattiioonn In order to start the time daemon on a given machine, the following lines should be added to the _l_o_c_a_l _d_a_e_m_o_n_s section in the file _/_e_t_c_/_r_c_._l_o_c_a_l: if [ -f /etc/timed ]; then /etc/timed _f_l_a_g_s & echo -n ' timed' >/dev/console fi In any case, they must appear after the network is config- ured via ifconfig(8). Also, the file _/_e_t_c_/_s_e_r_v_i_c_e_s should contain the follow- ing line: timed 525/udp timeserver The _f_l_a_g_s are: -n network to consider the named network. -i network to ignore the named network. -t to place tracing information in _/_u_s_r_/_a_d_m_/_t_i_m_e_d_._l_o_g. -M to allow this time daemon to become a master. A time daemon run without this option will be forced in the state of slave during an elec- tion. DDaaiillyy OOppeerraattiioonn _T_i_m_e_d_c_(_8_) is used to control the operation of the time daemon. It may be used to: +o measure the differences between machines' clocks, +o find the location where the master _t_i_m_e_d is running, +o cause election timers on several machines to expire at the same time, Timed Installation and Operation SMM:11-5 +o enable or disable tracing of messages received by _t_i_m_e_d. See the manual page on _t_i_m_e_d(8) and _t_i_m_e_d_c(8) for more detailed information. The _d_a_t_e_(_1_) command can be used to set the network date. In order to set the time on a single machine, the _-_n flag can be given to date(1). SMM:11-6 Timed Installation and Operation RReeffeerreenncceess 1. R. Gusella and S. Zatti, _T_E_M_P_O_: _A _N_e_t_w_o_r_k _T_i_m_e _C_o_n_- _t_r_o_l_l_e_r _f_o_r _D_i_s_t_r_i_b_u_t_e_d _B_e_r_k_e_l_e_y _U_N_I_X _S_y_s_t_e_m, USENIX Summer Conference Proceedings, Salt Lake City, June 1984. 2. R. Gusella and S. Zatti, _C_l_o_c_k _S_y_n_c_h_r_o_n_i_z_a_t_i_o_n _i_n _a _L_o_c_a_l _A_r_e_a _N_e_t_w_o_r_k, University of California, Berkeley, Technical Report, _t_o _a_p_p_e_a_r. 3. R. Gusella and S. Zatti, _A_n _E_l_e_c_t_i_o_n _A_l_g_o_r_i_t_h_m _f_o_r _a _D_i_s_t_r_i_b_u_t_e_d _C_l_o_c_k _S_y_n_c_h_r_o_n_i_z_a_t_i_o_n _P_r_o_g_r_a_m, University of California, Berkeley, CS Technical Report #275, Dec. 1985. 4. R. Gusella and S. Zatti, _T_h_e _B_e_r_k_e_l_e_y _U_N_I_X _4_._3_B_S_D _T_i_m_e _S_y_n_c_h_r_o_n_i_z_a_t_i_o_n _P_r_o_t_o_c_o_l, UNIX Programmer's Manual, 4.3 Berkeley Software Distribution, Volume 2c.