VARIABLE DESCRIPTIONS Following is a list of all variables used in this skeleton. In order to regularize and simplify the notation, variable names are expressed in structure member notation. Some structures are members of other structures, as shown in Unix syntax. r. receive packet x. transmit packet p. peer process s. system process c. local clock process p.f. clock filter s.m. chime list s.v. survivor list s.p. system peer pointer Reference in the following to remote means the remote server or symmetric peer; reference to local means the local client or symmetric peer. The data formats of all variables are in floating double unless indicated otherwise. PACKET These are the values contained in the NTP header portion of the UDP packet transmitted over the netwoork. The following descriptions are from the transmitter's point of view. All fields are transmitted in network byte order. The version-4 header format is unchanged from previous versions with the exception of extension fields, which are not covered in this description. x.dstaddr *peer_xmit, *fast_xmit r.srcaddr receive, fast_xmit, find_assoc This is the sender and port address in either the IPv4 or IPv6 address family format. x.srcaddr *peer_xmit, *fast_xmit r.dstaddr receive, fast_xmit This is the receiver and port address in either the IPv4 or IPv6 address family format. x.version *peer_xmit, *fast_xmit r.version receive, fast_xmit, find_assoc p.version peer_xmit This is a 3-bit field specifying the version number, normally 4. NTP version 4 is compatible with previous versions 1 through 3 with only minor differences that do not affect timekeeping quality. x.leap *peer_xmit, *fast_xmit r.leap packet This is a 2-bit field specifying the leap indicator with the following values: 0b00 SYNC no pending leap event 0b01 INSERT insert one second after minute 23:59 on either 30 June or 31 December 0b10 DELETE delete one second after minute 23:59 on either 30 June or 31 December 0b11 NOSYNC not yet synchronized The NOSYNC indication persists until the server is first synchronized, then is replaced by one of the other three indications. x.mode *peer_xmit, *fast_xmit r.mode receive, packet, find_assoc This is a 3-bit field specifying the mode with the following values: 0 reserved 1 symmetric active 2 symmetric passive 3 client 4 server 5 broadcast 6 defined control/monitoring protocol 7 private control/monitoring protocol x.stratum *peer_xmit, *fast_xmit r.stratum packet This is an eight-bit field specifying the stratum with the following values: 0 reserved 1 primary server synchronized by radio or telephone modem 2-15 stratum 16-255 invalid For the purposes of comparison, stratum 0 should be considered 256 and thus greater than any valid stratum. x.poll *peer_xmit, *fast_xmit r.poll packet, fast_xmit This is the poll interval expressed in powers of two between MINPOLL (6) for 64 s and MAXPOLL (10) for 1024 s in this skeleton. Actual values useable in practice can range from 4 (16 s) to 17 (36 h). x.precision *peer_xmit, *fast_xmit r.precision packet This is the precision expressed in signed powers of two. For this purpose, the precision is defined as the time taken by the kernel to read and return the system clock. For instance, on a Blade 1500 this is about 400 ns, which results in a precision of -21. x.rootdelay *peer_xmit, *fast_xmit r.rootdelay packet This is the roundtrip delay to the primary reference source at the root of the synchronization tree, in NTP short format.. x.rootdisp *peer_xmit, *fast_xmit r.rootdisp packet This is the dispersion to the primary reference source at the root of the synchronization tree, in NTP short format. x.refid *peer_xmit, *fast_xmit r.refid packet For primary (stratum 1) servers this is the 4-character identifier assigned the radio or modem source. For strata 2 through 15 this depends on the address family. If the x.dstaddr in the packet is from the IPv4 family, this is the 32-bit address of the system peer; otherwise it is the 32 low=order bits of the MD5 digest of the IPv6 address. For all other strata it is the four-character kiss code as explained elswhere in this document. x.reftime *peer_xmit, *fast_xmit r.reftime packet This is the reference timestamp in NTP long format. x.org *peer_xmit, *fast_xmit r.org receive, packet This is the originate timestamp in NTP long format. It is copied from the r.xmt field of the last received NTP packet. x.rec *peer_xmit, *fast_xmit r.rec packet This is the receive timestamp in NTP long format. It is copied from the r.rec field of the last received NTP packet. x.xmt *peer_xmit, *fast_xmit r.xmt receive, packet, fast_xmit This is the transmit timestamp in NTP long format. It is struck on departure of the transmitted packet. r.dst *main, receive, fast_xmit This is the destination timestamp in NTP long format. It is struck on arrival of a received packet and not part of the NTP header. The following variables constitute the optional message authentication code (MAC). x.keyid *peer_xmit, *fast_xmit r.keyid receive, fast_xmit This is the key identifier for the message digest. For symmetric key cryptography the value can range from 1 to 65535. A value of zero implies a crypto-NAK, ordinarily indicating that the last packet received was not correctly authenticatied. Values greater than 65535 are reserved for public key (Autokey) cryptgraphy, which is described elsewhere. x.mac *peer_xmit, *fast_xmit r.mac receive This is the MD5 message digest computed from the specified key and NTP header and extension fields, but not the MAC itself. PEER PROCESS These variables are copied from the received packet or constructed by the code segments in the skeleton. Note the distinction between process time, which is derived from a counter that counts the seconds, and real time, which is derived from NTP timestamps and the system clock. There is one peer process per association to manage these variables. It can be persistent, in which case it is mobilized by configuration parameters, or ephemeral, in which case it is mobilized and demobilized as operation continues. A peer process is activated upon arrival of a packet with matching source address, port, version and mode. p.t *reset, local_clock, *clock_filter, clock_update, clear This is the process time at the last clock filter update, expressed as an integer. p.srcaddr *mobilize, peer_xmit, find_assoc This is the remote IP address in either the IPv4 or IPv6 address family format. p.dstaddr *mobilize, peer_xmit, fit This is the local IP address in either the IPv4 or IPv6 address family format. p.version peer_xmit, find_assoc, *mobilize For ephemeral associations this is the NTP version number in the received packet (r.version) that mobilized the association, expressed as an integer. For persistent associations this is the version specified at configuration time. p.leap *packet, *clear, fit, clock_update This is the leap indicator (r.leap) of the last received packet in packet format. p.pmode *packet This is the mode (r.mode) of the last received packet in packet format. p.hmode *mobilize, poll, receive, peer_xmit, find_assoc p.stratum *packet, *clear, fit, clock_select, clock_update This is the stratum (r.stratum) of the last received packet in packet format. p.ppoll *packet, *clear, poll_update This is the poll interval (r.poll) of the last received packet in packet format. p.rootdelay *packet, clock_update This is the root delay (r.rootdelay) of the last received packet converted to floating double format. p.rootdisp *packet, clock_update This is the root dispersion (r.dispersion) of the last received packetconverted to floating double format. p.refid *packet, fit, *clear This is the reference identifier (r.refid) of the last received packet in packet format. p.reftime *packet, clock_update This is the reference timestamp (r.reftime) of the last received packet in packet format. p.org *receive, peer_xmit This is the originate timestamp (r.org) of the last received packet in packet format. p.rec *receive, peer_xmit This is the receive timestamp (r.rec) of the last received packet in packet format. p.xmt *receive, peer_xmit This is the transmit timestamp (r.xmt) of the last received packet format. p.keyid *mobilize, receive, peer_xmit This is the key identifier for the key used to construct the message digest in the last received packet in packet format. p.offset *clock_filter, clock_select, clock_update, clock_combine This is the offset of the local clock relative to the remote server determined by the clock filter algorithm. This is the value to add to the local clock time to equal the time at the server. p.delay *clock_filter, root_dist, clock_update This is the roundtrip delay determined at the last clock filter update. p.disp *clock_filter, root_dist, *reset This is the dispersion determined at the last clock filter update. p.jitter *clock_filter, root_dist, clock_select, clock_update, *clear This is the jitter determined at the last clock filter update. p.hmode *mobilize, receive, poll, peer_xmit, find_assoc This is the mode of the association. p.hpoll packet, poll, *poll_update, peer_xmit, *mobilize This is the host poll interval expressed in powers of two in seconds. p.reach *packet, fit, *poll This is an integer shift register that indicates server synchronization status. If zero the server is considered unreachable; if nonzer at least one poll has been answered in the last eight polls sent. p.unreach *poll This is an integer that counts the number of polls sent while the reachability register (p.reach) is zero. p.burst clock_filter, *poll, poll_update This is an integer that counts down the packets remaining to be sent during a burst. p.outdate *clear, *poll, poll_update This is an integer specifying the process time at the last poll event. p.nextdate *clear, poll, poll_update, clock_adjust This is an integer specifying the process time at the next scheduled poll event. p.flags *mobilize, clear, receive, poll This is an array of bits used as flags by various algorithms. CLOCK FILTER These variables represent one stage of the clock filter. Each stage holds the result of a roundtrip exchange of packets between the client and server. Upon arrival of the reply the client determines offset, delay and related values. The stages are shifted left as new exchanges are complete, with the oldest stage discarded and the newest stage replaced by the new values. p.f.t *clock_filter This is the process time upon arrival of the reply packet. p.f.offset *clock_filter This is the time offset determined from the timestamps upon arrival of the reply packet. p.f.delay *clock_filter This is the roundtrip delay determined from the timestamps upon arrival of the reply packet. p.f.disp *clock_filter This is the dispersion determined from the timestamps upon arrival of the reply packet. SYSTEM PROCESS Conceptually there is only one system process, but it is useful in descriptions to represent its variables as structure members. The process is activated by the clock filter algorithm which selects which stage of the shift register contains the best sample values. s.t local_clock, *rstclock, clock_update This is the process time of the last clock filter update. s.leap *main, clock_filter, *clock_update, peer_xmit, fast_xmit This is the leap indicator provided by a configuration parameter or derived from the leap bits of available servers. There is some craft in this, as the servers might disagree due to unavailability of reliable sources or sheer laziness of the implementors. A consensus algorithm is for further study. s.stratum *main, *clock_update, peer_xmit, fast_xmit This is the system stratum determined as one greater than the system peer stratum at the last clock update. s.poll *main, *local_clock, clock_adjust, clock_filter, clock_update, poll This is the system poll interval, also the time constant of the clock discipline algorithm. It is determined by the local clock discipline expressed in powers of two and confined to thr range 4-17. s.precision *main, local_clock, packet, clock_filter, clear, peer_xmit, fast_xmit This is the measured precision of the local clock, in seconds to the logarithm to the base two. s.rootdelay *clock_update, root_dist, peer_xmit, fast_xmit This is the total roundtrip delay via the system peer to the root of the synchronization subnet. s.rootdisp *clock_adjust, *clock_update, root_dist, peer_xmit, fast_xmit This is the total disperson via the system peer to the root of the synchronization subnet. s.refid *clock_update, peer_xmit, fast_xmit This is the reference identifier of the system peer in packet format. s.reftime *clock_update, peer_xmit, fast_xmit This is the timestamp struck at the time of the last system clock update. s.p *clock_select, clock_update, poll, *clear, *main This is the peer pointer of the system peer. s.flags *main, receive This is an array of bits used as flags by various algorithms. CHIME LIST (clock_select() intersection algorithm)) s.m.p *clock_select This is a peer structure pointer. s.m.type *clock_select This is an integer defining the upper (+1), mid (0) or lower (-1) edge of a correctness interval for the s.m.p peer structure. s.m.edge *clock_select This is one of the upper/mid/lower edges of a correctness interval for the s.m.p peer structure. SURVIVOR LIST (clock_select() clustering algorithm) s.v.p *clock_select This is a peer structure pointer. s.v.metric *clock_select This is the sort metric for the s.v.p peer structure. LOCAL CLOCK PROCESS c.t local_clock, *clock_adjust, clock_filter, root_dist, clear, clock_update, poll, poll_update This is the current process time incremented at one-second intervals from program startup. c.state local_clock, *rstclock This is the current state of the clock state machine. c.offset *local_clock, *rstclock, clock_adjust This is the current clock offset determined by the clock discipline algorithm. c.base local_clock, *rstclock This is the difference between the current clock offset and the current clock offset determined by the clock adjust process. c.last local_clock, *rstclock, clock_update, This is the last clock offset determined by the clock discipline algorithm. c.count *local_clock This is a counter used to adjust the poll interval by the clock discipline algorithm. c.freq *local_clock, clock_adjust This is the frequency determined by the clock discipline algorithm. c.jitter *local_clock This is the exponentially weighted RMS offset differences determined by the clock discipline algorithm. c.stab *local_clock This is the exponentially weighted RMS frequency differences determined by the clock discipline algorithm. Global constants PARAMETERS VERSION 4 /* version number */ This is the version number for mobilized associations. If an association is mobilized by an arriving packet, the version of the association is that of the packet. If an association is mobilized by configuration, the version number is provided by configuration data. PRECISION -18 /* precision (log2 s) */ This is the precision of the machine on which the program runs, expressed as (negative) powers of 2 in seconds. It is intended that this be determined at run time by measuring the time taken for a kernel call to read the system clock. MINDISP .01 /* % minimum dispersion (s) */ This is the minimum dispersion included in the dispersion increment from the current stratum to the next higher stratum. Higher values discourage clockhopping and timing loops, but decrease the clustering algorithm selectivity, and vice versa. Lower values are appropriate for low-stratum servers with multiple sources, while higher values are appropriate for client workstations and PCs. MAXDISP 16 /* maximum dispersion (s) */ This is the maximum dispersion assumed for a nonworking server, a fixed parameter. MAXDIST 1 /* % distance threshold (s) */ This is the distance threshold below which the server is assume fit for service. With the default value of 1 s, the server becomes fit after about the first four clock updates. The threshold can be set higher, whichwould reduce the number required for fitness, or lower to increase the number. NOSYNC 0x3 /* leap unsync */ Before the server is heard for the first time, the leap bits are set to this value, a fixed parameter. MAXSTRAT 16 /* maximum stratum (infinity metric) */ A stratum number of zero in a received packet is mapped to MAXSTRAT. The inverse mapping is used on transmitted packets. Internal to the program, this value is considered "infinity", meaning the server is unreachable or out of service. MINPOLL 4 /* % minimum poll interval (16 s)*/ This is the minimum poll interval consistent with a stable clock discipline function using one-second clock adjustment increments. MAXPOLL 17 /* % maximum poll interval (36.4 h) */ This is the maximum poll interval usable under most conditions with typical computer clock oscillators. PHI 15e-6 /* % frequency tolerance (15 PPM) */ This is the assumed maximum frequency tolerance of the disciplined clock oscillator. Increasing it to as much as 500e-6 (500 PPM) would make the theoretical computer sciency community more comfortable, but would invite serious clockhopping problems. Best to leave it alone. NSTAGE 8 /* clock register stages */ This is the number of stages in the clock filter shift register. A fixed parameter. NMAX 50 /* maximum number of peers */ This is the maximum number of sources that can be used by the clock selection algorithm. In most cases, more than ten is counterproductive. NSANE 1 /* % minimum intersection survivors */ This is the minimum number of intersection survivors providing sufficient redundancy for reliable synchronization. Byzantine agreement principles require at least four; however, for this demonstration we require only one. NMIN 3 /* % minimum cluster survivors */ This is the minimum number of survivors produced by the clusterinig algorithm in the clock_select() routine, assuming at least that many are available from the intersection algorithm in that routine. LOCAL CLOCK PROCESS STEPT .128 /* step threshold (s) */ This is the step threshold used by the clock discipline algorithm. If offsets greater than this persist beyond the stepout threshold, a step clock adjustment is made. It can be increased to reduce the likelihood that a step might occur under the most adverse conditions, but this may result in undesirable consequences, like extended periods while the client must be considered unsynchronized with the remaining population. WATCH 900 /* stepout threshold (s) */ This is the stepout threshold used by the clock discipline algorithm. See the STEPT parameter. PANICT 1000 /* panic threshold (s) */ This is the panic threshold beyond which the server or the client must be assumed unreliable. The program exits requiring operator intervention. PLL 65536 /* PLL loop gain */ FLL MAXPOLL + 1 /* FLL loop gain */ AVG 4 /* parameter averaging constant */ ALLAN 1500 /* compromise Allan intercept (s) */ These parameters are used by the clock discipline algorithm to control the response to time and frequency errors. They have been tediously optimized for optimum response over a poll interval range from 16 s to 36.4 h and don't you dare change them. LIMIT 30 /* poll-adjust threshold */ This is a hysteresis threshold used to adjust the system poll interval. BDELAY .004 /* broadcast delay (s) */ This is the assumed propagation delay for a broadcast packet when no other means are available to determine the actual delay. MAXFREQ 500e-6 /* frequency tolerance (500 PPM) */ This is the maximum frequency tolerance of the clock discipline algorithm. The algorithm can correct for hardware clock frequency errors up to this value, but for errors larger than this value, a constant residual time offset will result. PGATE 4 /* poll-adjust gate */ This is a tuning parameter for the poll-adjust function used by the clock discipline algorithm. Larger values widen the offset range which allow the poll interval to increase, while smaller values have the opposite effect. PEER PROCESS SGATE 3 /* spike gate */ This is a tuning parameter for the popcorn spike suppressor used by the clock filter. Higher values trim fewer spikes but result in larger clock jitter. Lower values have the opposite effect. POLL PROCESS UNREACH 12 /* unreach counter threshold */ BCOUNT 8 /* packets in a burst */ BTIME 2 /* burst interval (s) */ PROCEDURES The following procedures are used in this skeleton. The name of the procedure is given first followed by a cross index list of other procedures associated with this procedure. Other procedures that call this procedure are identified by "*"; the remaining procedure are called by this procedure. A short functional description follows the cross index list. local_clock *clock_update, rstclock, fabs, exit, step_time, adjust_time This is the clock discipline algorithm used to generate time and frequency corrections for the local clock. rstclock *local_clock This routine is used by the local clock discipline to update state variables. clock_adjust *kernel, poll This routine is called by the kernel timer routines at one second intervals. It implements time and frequency corrections determined by the local clock discipline and also implements a poll timer for each association. receive *main, md5, mobilize, packet This routine receives packets from the kernel I/O system, performs various error checks on the header and data, mobilizes ephemeral associations when necessary and calls the packet routine to process the timestamps. packet *receive, clock_filter This routine captures header data for later use, calculates offset, delay and dispersion and calls the clock filter algorithm. clock_filter *packet, clock_select This routine determines from a window of the last eight roundtrip measurements the best values for offset, delay, dispersion and jitter. It then calls the clock select algorithm to determine the best from among the available servers and peers and calls the clock update algorithm to implement adjustments in offset and fequency as required. root_dist *fit, *clock_select, *clock_combine This routine calculates the synchronization distance via the designated server or peer to the root of the sunchronization subnet. fit *clock_select, *poll This routine determines if a potential remote server or peer is suitable for synchronization. clear *receive, *clock_update, *poll, *peer_xmit This routine returns all system resources acquired by the association to the system and initializes the association variables (peer structure) to the initial state. main *system, mobilize, receive This is the main program called by the system at startup. clock_select *clock_filter, *poll, clock_update, fit This routine selects which remote servers or peers are among the best candidates for synchronization and determines which among them to inherit the stratum and other variables as the system peer. clock_update *clock_select, local_clock This routine updates the system variables from the system peer and calls the clock discipline algorithm to adjust the system clock time and frequency. clock_combine *clock_select This routine calculates the final clock offset from the weighted contributions of the clock-select survivors. poll *clock_adjust, clock_select, peer_xmit, poll_update This routine is called at regular poll intervals from the clock_adjust routine to send NTP packets to remote servers or peers. poll_update *packet, *poll This routine determines the poll interval used by the poll routine. peer_xmit *poll, md5 This routine constructs and transmits a NTP packet from a local server or peer association to a remote server or peer. fast_xmit *receive, md5 This routine constructs and transmits a NTP packet in response to a NTP client packet from a remote server. There is no state preserved for arriving client mode packets, so no association is involved. md5 *receive, *peer_xmit, *fast_xmit This routine returns the MD5 message digest using a local key and the NTP message header and extension fields. find_assoc *receive This routine finds an association with packet variables matching the source address, port, version and mode. mobilize *main, *receive This routine allocates and initializes the association memory (peer structure) used to run the protocol. access *receive This routine determines from an access control list whether an arriving packet is acceptable and returns a word of restrict flags. KERNEL INTERFACE recv_packet *main This routine is called by the kernel I/O system when a new packet buffer arrives from the network and returns a pointer to the buffer. get_time *main This routine returns the current system clock time. step_time *local_clock This routine steps the system clock to a specified time. adjust_time *local_clock This routine slews the system clock by a specified offset.