flow

NTP Procedure Descriptions and Flow Diagrams: 

6-Feb-08 1 NTP Procedure Descriptions and Flow Diagrams David L. Mills University of Delaware http://www.eecis.udel.edu/~mills mailto:mills@udel.edu

NTP process overview: 

6-Feb-08 2 NTP process overview Peer process runs when a packet is received. Poll process sends packets at intervals determined by the clock discipline process and remote server. System process runs when a new peer process update is received. Clock discipline process runs at intervals determined by the measured network jitter and clock oscillator (VFO) frequency wander. Clock adjust process runs at intervals of one second. RemoteServers Server 1 Server 2 Peer/Poll 1 Server 3 Peer/Poll 2 Peer/Poll 3 Selection and Clustering Algorithms Combining Algorithm Loop Filter VFO Clock Discipline Process SystemProcess Peer/PollProcesses Clock Adjust Process

NTP peer protocol: 

6-Feb-08 3 NTP peer protocol Packet header includes T1, T2 and T3 timestamps. Peer state variables org, rec and xmt record the transmit and receive times of the most recent packet received. When a packet is transmitted Copy org to T1 and rec to T2. Copy the current time to xmt and to T3. When a packet received If T3 is the same as xmt, this is a duplicate packet. If T1 is not the same as org, this is a bogus packet. Otherwise, copy T3 to pkt and copy the current time to T4 and rec. Note that the protocol is symmetric and allows time values to flow both ways simultaneously and is resistant to replays and drops. Note the special conditions when either or both peers first start up.

NTP peer protocol example: 

6-Feb-08 4 NTP peer protocol example 0 0. 0 0 t2 = clock t3 t4 t5. t1 t5 t6 t7 org rec t3 t4 t7? t8 t5 t6 t5? t6 org rec t1 t2 0 t2 t4 t3. t2 t6 t5. t1 0 0 t1 t2 t3. t3? t4 t4 t3 t2 t1 t5 t6 t8 t7 t4 t2 t3 t6 t7 t8 t6 = clock t1 = clock t5 = clock t4 = clock t8 = clock t3 = clock t7 = clock t1 t5 org origin timestamp rec receive timestampxmt transmit timestamp PacketVariables Peer B StateVariables PacketVariables Peer A StateVariables State VariablesName Description T1 T3 T2 T4 T1 T3 T2 T4 t7 t3? xmt t3 0 t1 xmt t5 t5? t1? tn origin timestamptn+1 receive timestamptn+2 transmit timestamptn+3 destination timestamp Packet VariablesName Description

Computing time values and error estimates: 

6-Feb-08 5 Computing time values and error estimates S S Packet Variables Peer Variables Client System Variables S Server Packet variables are computed directly from the packet header. Peer variables are groomed by the clock filter. System variables are groomed from the available peers.

Variable, Parameter and Procedure Libraries: 

6-Feb-08 6 Variable, Parameter and Procedure Libraries 1. NTP Packet header format2. Process variables3. Parameters4. Procedure cross index

Naming conventions: 

6-Feb-08 7 Naming conventions The names on the following pages are distinguished by the process to which the belong. When necessary to disambiguate the name, the prefix tags above will prepend he name. r. receive packet x. transmit packet p. peer/poll process s. system process c. local clock process p.f. clock filter s.m chime list s.v. survivor list The variable names and formula names are used interchangeably to improve readability and reduce flow chart size.

NTP packet header format: 

6-Feb-08 8 NTP packet header format Strat Poll LI Mode VN Root Delay Root Dispersion Reference ID Reference Timestamp (64) Origin Timestamp (64) Receive Timestamp (64) Transmit Timestamp (64) Prec Name Formula Description leap leap leap indicator (LI)version version version number (VN)mode mode modestratum stratum stratumpoll t poll interval (log2 s)precision r precision (log2 s)rootdelay D root delayrootdisp E root dispersionrefid refid reference IDreftime reftime reference timestamporg T1 origin timestamp rec T2 receive timestamp xmt T3 transmit timestampdst* T4 destination timestamp* MAC (optional 160) * Strictly speaking, dst is not a packet variable; it is the value of the system clock upon arrival. Message Authentication Code (MAC) Name Formula Description keyid key ID mac message digest Packet Variables

Process variables I: 

6-Feb-08 9 Process variables I Name Formula Description Configuration Variables srcaddr source address dstaddr destination address version version version hmode hmode host mode keyid keyid key ID flags option flagsPacket Variablesleap leap leap indicator pmode pmode packet mode stratum stratum stratum ppoll t poll interval rootdelay D root delay rootdisp E root dispersion refid refid reference ID reftime reftime reference timestamp org T1 origin timestamp rec T2 receive timestamp xmt T3 transmit timestampWorking Variables t t update time filter clock filter offset q clock offset delay d roundtrip delay disp e dispersion jitter j jitter Peer Process Variables (p.) Name Formula Description t t update time offset q clock offset delay d roundtrip delay disp e dispersion Clock Filter Variables (p.f.) Name Formula Description t t update time leap leap leap indicator stratum stratum stratum poll t poll interval precision r precision rootdelay D root delay rootdisp E root dispersion refid refid reference ID reftime reftime reference time chime chime list survivor survivor list p p system peer offset Q combined offset jitter J combined jitter flags option flags System Process Variables (s.)

Process variables II: 

6-Feb-08 10 Process variables II Name Formula Description hpoll hpoll host poll interval burst count burst counter reach reach reach register unreach unreach unreach counter outdate last poll time nextdate next poll time Poll Process Variables (p.) Survivor List Variables (s.v.) Name Formula Description t t update time state state current state offset q current offset base qB base offset last qB previous offset count count jiggle counter freq freq frequency jitter j RMS jitter wander h RMS wander Local Clock Process Variables (c.) Name Formula Description p p association ID metric l survivor metric Name Formula Description p p association ID type t edge type edge edge edge offset Chime List Variables (s.m.) Message Authentication Code (MAC) Name Formula Description keyid keyid key ID mac mac message digest

Parameters I: 

6-Feb-08 11 Parameters I Name Value Description VERSION 4 version number PRECISION -18 precision (log2 s) MINDISP .01 minimum dispersion (s) MAXDISP 16 maximum dispersion (s) MAXDIST 1 distance threshold (s) MAXSTRAT 16 maximum stratum (infinity metric) MINPOLL 4 minimum poll interval (16 s) MAXPOLL 17 maximum poll interval (36.4 h) PHI 15e-6 frequency tolerance (15 PPM) NSTAGE 8 clock register stages NMAX 50 maximum number of peers NSANE 1 minimum intersection survivors NMIN 3 minimum cluster survivorsSGATE 3 spike gate thresholdBDELAY .004 broadcast delay (s) Peer Process Parameters M_SACT 1 symmetric activeM_PASV 2 symmetric passiveM_CLNT 3 clientM_SERV 4 serverM_BCST 5 broadcastM_BCLN 6 broadcast client (pseudo mode) Mode Assignments

Parameters II: 

6-Feb-08 12 Parameters II Name Value Description STEPT 0.128 step threshold (s) WATCH 900 stepout threshold (s) PANICT 1000 panic threshold (s) PLL 65536 PLL loop gain FLL 18 FLL loop gain AVG 4 parameter averaging constant ALLAN 1500 compromise Allan intercept (s) LIMIT 30 poll-adjust threshold MAXFREQ 500e-6 frequency tolerance (500 PPM) PGATE 4 poll-adjust gate Local Clock Process Parameters Name Value DescriptionUNREACH 12 unreach counter threshold BCOUNT 8 packets in a burst BTIME 2 burst interval (s) Poll Process Parameters Name Value DescriptionA_NONE 0 not authenticated A_OK 1 authentiction OK A_ERROR 2 authentication errorA.CRYPTO 3 crypto_NAK receivedA.NKEY 4 yhntrusted key Authentication Code Assignments

Procedure cross index I: 

6-Feb-08 13 Procedure cross index I System Process Routines Name Description Related Routines main main program *system, mobilize, recv_packet, receive clock_select clock select *clock_filter, fit, clock_update clock_update clock update *clock_select, clock_combine, local_clock clock_combine clock combine *clock_update, root_distance root_dist root distance *fit, *clock_select, *clock_combine fit fit to synchronize *clock_select, *poll, root_dist Peer Process Routines Name Description Related Routines receive receive packet *main, md5, mobilize, packet, find_assoc,access, fast_xmit packet process packet *receive, clock_filter clock_filter clock filter *packet, *poll Name Description Related Routines local_clock clock discipline *clock_update, rstclock, step_time, adjust_time rstclock state transition *local_clock Clock Adjust Process Routines Name Description Related Routines clock_adjust clock_adjust *kernel, poll Local Clock Process Routines

Procedure cross index II: 

6-Feb-08 14 Procedure cross index II Name Description Related Routines md5 message digest *receive, *peer_xmit, *fast_xmit find_assoc find association *receive mobilize mobilize association *main, *receive clear clear association *receive, *clock_update, *poll, *peer_xmit access access mask *receive name description related routines recv_packet receive packet *mainxmit_packet send packet peer_xmit, fast_xmit get_time get time *main, peer_xmit, fast_xmit step_time step time *local_clock adjust_time adjust time *local_clock name description related routines poll poll *clock_adjust, clock_filtert, peer_xmit, poll_update poll_update poll update *packet, *poll peer_xmit peer transmit *poll, md5 fast_xmit fast transmit *receive, md5 Kernel Interface Routines Poll Process Routines Utility Routines

Packet sanity tests (reference implementation only): 

6-Feb-08 15 Packet sanity tests (reference implementation only)

Flow Diagrams: 

6-Feb-08 16 Flow Diagrams 1. Main Program2. Peer Process3. System Process4. Clock Discipline Process5. Clock Adjust Process6. Poll Process

Control flow: 

6-Feb-08 17 Control flow The main program waits for a packet arrival, then control flows by each of the procedures connected by solid arrows. A client request requires no persistent association; the server response is handled directly by fast_xmit. The packet procedure calls poll_update since it updates the packet poll variable. The main program waits for one second, then calls clock_adjust. At the poll timeout, control flows by each of the procedures connected by solid arrows. The peer_xmit procedure calls clock_filter when the server has not been heard for three poll intervals. It calls clear on timeout for ephemeral associaitons. The dotted arrows show which procdures are called by each procedure with control returning to the calling procedure.

Procedure flow: 

6-Feb-08 18 Procedure flow main wait for pkt receive() packet() clock_filter() clock_select() clock_update() local_clock() main 1-s timer clock_adjust() poll timeout? poll() peer_xmit() fit() root_dist () clock_combine() clear() fast_xmit() mobilize() find_assoc() access() recv_packet() xmit_packet() step_time() adjust_timet() get_time() rstclock() md5() yes no poll_update()

Main program: 

6-Feb-08 19 Main program main wait for pkt receive() mobilize() persistent associations T4 = get_time() mobilize() clear() allocate association memory exit initialize clear() exit demobilize association persistent? initialize association variables yes no start timer

Peer process: 

6-Feb-08 20 Peer process receive procedure Verify integrity, authenticity and consistency of packet data. Match packet to persistent association (client) or reply directly (server). packet procedure Compute clock offset, roundtrip delay and dispersion. Copy packet header data to peer state variables clock_filter procedure Select the best from among the past eight samples. Calculate filter dispersion, jitter and related values. Implement popcorn spike suppressor.

Peer process: receive() procedure I: 

6-Feb-08 21 Peer process: receive() procedure I Packet Mode Association Mode The default (empty box) behavior is to discard the packet. yes yes auth = md5() format OK? access OK? go to(hmode, pmode) in transition matrix receive no access deny no format error find_assoc() FXMIT exit fast_xmit() ERROR exit clear()

Peer process: receive() procedure II: 

6-Feb-08 22 Peer process: receive() procedure II NEWPS auth = M_OK? mobilize() M_PASV association exit PROC no yes PROC clear() auth = A_OK? packet() yes T3 = xmt? no duplicate pkt T1 = 0? T1 = xmt? yes no mode = M_BCST exit T3 = 0? yes invalid no auth error no yes no yes yes no auth = A_CRYPTO? yes org=T3rec=T4 org=T3rec=T4 exit no yes no NEWBC auth = M_OK mobilize() M_BCLN association exit

Peer process: packet() procedure: 

6-Feb-08 23 clock_filter (q, d, e, T4) ok Peer process: packet() procedure header? packet bad header error exit poll_update() Peer PacketVariables Variablesleap ← leapmode ← modestratum ← stratumpoll ← ppoll D ← DE ← Erefid ← refidreftime ← reftime *copy header *Copy Header reach |= 1 Variable Process DescriptionT1 packet origin timestampT2 packet receive timestampT3 packet transmit timestampT4 packet destination timestampq peer offsetd peer delaye poll dispersionr.r packet peer poll intervalp.r peer host poll intervalreach poll reach registerPHI parameter frequency tolerance packet() Procedure

peer process: clock_filter() procedure: 

6-Feb-08 24 tmp = q no peer process: clock_filter() procedure Create (xi, yi, zi, wi) from each sample in clock filter; save in temporary array; sort array by increasing delay y Shift sample (x, y, z, w) in clock filter; adjust dispersion e for old samples yes no clock_filter (x, y, z, w yes t0 > t popcorn spike? exit yes no burst = 0? clock select() Variable Process Descriptionq peer clock offsetd peer roundtrip delaye peer filter dispersionj peer filter jittert peer last update timen peer number of filter samples(x, y, z, w) from packet procedure tmp temporaryburst poll burst counter t local clock poll interval t = t0 clock_filter() Procedure

System process: 

6-Feb-08 25 System process clock_select procedure select algorithm: classify available servers as truechimers or falsetickers. cluster algorithm: find and discard outlyers until no more than three survivors remain. clock_update procedure call clock_combine procedure to combine weighted server offsets. Call local_clock procedure to discipline the system clock. Update system variables rootdist function Return synchronization distance to the primary reference source. fit function Return TRUE if selected server is acceptable and root distance less than 1s

System process: clock_select() procedure: 

6-Feb-08 26 no System process: clock_select() procedure clock_select() clock update() selectalgorithm cluster algorithm fit()? scan candidates yes add peer exit survivors? survivors? no yes no s.p = v0.p exit yes s.p = NULL Name Process Descriptions.p system system peervi system survivor list sample clock_select() Procedure

System process: intersection algorithm: 

6-Feb-08 27 System process: intersection algorithm no Set the number of midpoints d = 0. Set c = 0. Scan from lowest endpoint to highest. Add one to c for every lowpoint, subtract one for every highpoint, add one to d for every midpoint. If c ≥ m - f, stop; set l = current lowpoint Set c = 0. Scan from highest endpoint to lowest. Add one to c for every highpoint, subtract one for every lowpoint, add one to d for every midpoint. If c ≥ m - f, stop; set u = current highpoint. Add one to f. Is f < m / 2? Select the lowpoint, midpoint and highpoint of these intervals. Sort these values in a list from lowest to highest. Set the number of falsetickers f = 0. Failure; a majority clique could not be found.. Success; the intersection interval is [l, u]. yes For each of m associations construct a correctness interval[q – rootdist(), q + rootdist()] If d ≤ f and l < u? no yes

system process: cluster algorithm: 

6-Feb-08 28 system process: cluster algorithm For each candidate compute the selection jitter jS (RMS peer offset differences between this and all other candidates). Select jmax as the candidate with maximum jS. Delete the outlyer candidate with jmax; reduce n by one. Done. The remaining cluster survivors are the pick of the litter. The survivors are in the v. structure sorted by L. no yes Let (q, j, L) represent a candidate peer with offset q, jitter j and a weight factor L = stratum * MAXDIST + rootdist(). Select jmin as the candidate with minimum j. Sort the candidates by increasing L. Let n be the number of candidates and NMIN the minimum number of survivors. jmax < jmin or n ≤ NMIN

System process: clock_update() procedure: 

6-Feb-08 29 ADJ System process: clock_update() procedure local_clock() clock_update() yes no PANIC clear all associations STEP *update system variables panic exit IGNOR exit System PeerVariables Variablesleap ← leapstratum ← stratumrefid ← refidreftime ← reftimeD ← D + dE ← E + e + PHI m + j + |q| clock_update Procedure stratum = MAXSTRATpoll = MINPOLL Name Process Descriptionp.t peer times.t system offsets.stratum system stratums.poll system poll intervalMAXSTRAT parameter max stratumMINPOLL parameter min poll interval *Update System Variables

system process: clock_combine() procedure: 

6-Feb-08 30 system process: clock_combine() procedure exit done scancluster survivors y = z = w = 0 x = rootdist() clock_combine() Variable Process DescriptionQ system combined clock offsetJ system combined jitterq0 survivor list first survivor offsetqi survivor list ith survivor offsetx, y, z, w temporaries combine() Procedure

System process: fit() and root_dist() functions: 

6-Feb-08 31 System process: fit() and root_dist() functions exit((D + d) / 2 + E + e + PHI m + j) root_dist() no all no no exit (NO) fit() exit (YES) yes refid = addr? reach = 0?leap = 11?stratum >15? yes any yes server not synchronized root distance exceeded server/client sync loop Variable Process Descriptionleap peer leap indicatorstratum peer stratumrefid peer reference IDaddr system hashed local IP addrreach poll reach shift register Variable Process DescriptionD peer root delayd peer delayE peer root dispersione peer dispersionm peer time since last updatej peer jitterPHI parameter frequency tolerance fit() function rootdist() Function rootdist() > MAXDIST?

Clock discipline process: 

6-Feb-08 32 Clock discipline process local_clock() function Discipline system clock using adaptiver-parameter, phase/frequency-lock loop. rstclock procedure Transition to new state and initialize variables. adjust_freq segment Adjust oscillator frequency using PLL/FLL feedback loop. step_freq segment Step oscillator frequency when first starting and no previous information. tc segment Adjust time constant as a function of prevailing jitter and oscillator stability.

Clock discipline process: local clock() function I: 

6-Feb-08 33 no yes no no yes Clock discipline process: local clock() function I |Q| > PANICT? SYNC exit (panic) local_ clock() |Q| > STEPT? FREQ SPIK m > WATCH yes state = SPIK m > WATCH FREQ step_freq SPIK SYNC exit (IGNOR) yes adjust_freq exit (STEP) FSET tc NSET state = FREQ NSET FSET state = NSET? QR = Q QR = Q no step_time (Q) QR = 0 tc no yes Variable Process DescriptionQ local clock offsetQR local clock residual offsetj local clock jitterm local clock time since last updatestate local clock statecount local clock counterSTEPT parameter step threshold (.125 s)WATCH parameter stepout thresh. (900 s)PANICT parameter panic thresh. (1000 s) local_clock() Function

Clock discipline process: state transition matrix: 

6-Feb-08 34 Clock discipline process: state transition matrix

Clock discipline process: local_clock() function II: 

6-Feb-08 35 Clock discipline process: local_clock() function II adjust freq tc calculate new freq adjustment f from Q and m using hybrid PLL and FLL calculate new freq adjustment step freq yes |Q| < PGATE j count += t count > LIMIT count = LIMIT no yes count -= 2t t++ t < MAXPOLL count < -LIMIT count = -LIMIT yes t-- t > MINPOLL no no no no yes yes exit (ADJ) tc Variable Process DescriptionQ local clock offsetQR local clock residual offsetj local clock jitterm local clock time since last updatef local clock frequency adjustmenth local clock frequency wandert local clock poll intervalfreq local clock frequencycount local clock counterMAXPOLL parameter max poll intervalMINPOLL parameter min poll intervalLIMIT parameter hysteresis limit AVG parameter averaging constant freq += f local_clock() Procedure state = SYNC

Clock adjust process: clock_adjust() procedure: 

6-Feb-08 36 Clock adjust process: clock_adjust() procedure clock_adjust() procedure Called by kernel timer routines once each second. Adjusts system clock frequency as computed by PLL/FLL. system process computes initial system clock offset. Reduce residual clock offset as exponential decay. This procedure can also be implemented in the kernel for reduced sawtooth error.

Clock adjust process: clock_adjust() procedure: 

6-Feb-08 37 Clock adjust process: clock_adjust() procedure clock_adjust() QR -= tmp exit Name Process Descriptiont local clock poll intervalQR local clock current offsetE system root dispersionfreq local clock frequencytmp local temporaryPHI parameter tolerance (15 PPM)PLL parameter PLL loop gain E += PHI adjust_time (freq + tmp) clock_adjust() Procedure

Poll process: 

6-Feb-08 38 Poll process poll() procedure Determine when to transmit a packet according to poll and burst schedules. peer_xmit() and fast_xmit() procedures Format and transmit an NTP packet. poll update() procedure Mitigate the poll interval as a function of the host and peer poll intervals and defined lower and upper limits.

Poll process: poll() procedure variables: 

6-Feb-08 39 Poll process: poll() procedure variables Name Process Description hpoll poll host poll intervalhmode poll host mode count poll burst counter reach poll reach register unreach poll unreach counter t local clock current time t local clock poll intervalp system system peerM_BCST parameter broadcast serverM-BCLN parameter broadcast clientB_BURST peer flag burst enableB_IBURST peer flag initial burst enableB_COUNT parameter pkts in a burst poll() Procedure

Poll process: poll() procedure: 

6-Feb-08 40 yes yes yes yes no no Poll process: poll() procedure unreach++ hpoll++ burst = 0? unreach > UNREACH reach = 0? reach & 0x7 = 0? clock_filter (0, 0, ∞, t) burst-- unreach = 0 peer_xmit() reach <<= 1 B_BURST? burst = BCOUNT B_IBURST? fit()? hpoll = c.t poll() no no yes no no yes yes no poll_update() hmode = M_BCLN? hmode= M_BCST? yes yes yes no s.p = NULL? burst = BCOUNT unreach = 0? yes no no yes exit

Poll process: peer_xmit() and fast_xmit() procedures: 

6-Feb-08 41 Poll process: peer_xmit() and fast_xmit() procedures peer_xmit()fast_xmit() *copy header mac = md5() xmit_packet() exit T1, T2 T3 = clock Packet Desig.Variable Variableleap ← s.leapversion ← p.versionmode ← p.hmodestratum ← s.stratumpoll ← p.hpollr ← s.rD ← s.D E ← s.E refid ← s.refidreftime ← s.reftimeT1 ← p.org T2 ← p.rec T3 ← clockkeyid ← p.keyidmac ← md5 *peer_xmit() Procedure Packet Desig.Packet Variable leap ← s.leapversion ← r.versionmode ← M_SERVstratum ← s.stratumpoll ← r.pollr ← s.rD ← s.D E ← s.E refid ← s.refidreftime ← s.reftimeT1 ← r.T3 T2 ← r.T4T3 ← clockkeyid ← r.keyidmac ← md5 *fast_xmit() Procedure

Poll process: poll_update() procedure: 

6-Feb-08 42 yes no Poll process: poll_update() procedure timer running? burst = 0? hpoll = max(min(MAXPOLL, poll), MINPOLL)) poll_update() n timer = BTIME no yes exit Variable Process Descriptionppoll peer peer poll intervalhpoll poll host poll intervalburst poll burst countertimer kernel system timerBTIME parameter burst time MINPOLL parameter minimum poll intervalMAXPOLL parameter maximum poll interval poll_update() Procedure timer = (max(min(ppoll, hpoll), MINPOLL))

Further information: 

6-Feb-08 43 Further information Network Time Protocol (NTP): http://www.ntp.org/ Current NTP Version 3 and 4 software and documentation FAQ and links to other sources and interesting places David L. Mills: http://www.eecis.udel.edu/~mills Papers, reports and memoranda in PostScript and PDF formats Briefings in HTML, PostScript, PowerPoint and PDF formats Collaboration resources hardware, software and documentation Songs, photo galleries and after-dinner speech scripts FTP server ftp.udel.edu (pub/ntp directory) Current NTP Version 3 and 4 software and documentation repository Collaboration resources repository Related project descriptions and briefings See “Current Research Project Descriptions and Briefings” at http://www.eecis.udel.edu/~mills/status.htm