idnits 2.17.1 draft-ietf-ntp-ntpv4-algorithms-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1.a on line 18. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5 on line 788. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 765. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 772. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 778. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'MIL05' is mentioned on line 568, but not defined == Unused Reference: 'NTP05' is defined on line 710, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 1305 (ref. 'MIL92') (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 2030 (ref. 'MIL96') (Obsoleted by RFC 4330) Summary: 3 errors (**), 0 flaws (~~), 5 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Time Protocol Working W. Kasch (Editor) 3 Group JHU/APL 4 Internet-Draft J. Burbank, Editor 5 Expires: April, 2006 JHU/APL 6 October, 2005 8 The Network Time Protocol Version 4 Algorithm Specification 9 11 Status of this Memo 13 This document is an Internet-Draft and is subject to all provisions 14 of Section 3 of RFC 3978. By submitting this Internet-Draft, each 15 author represents that any applicable patent or other IPR claims of 16 which he or she is aware have been or will be disclosed, and any of 17 which he or she becomes aware will be disclosed, in accordance with 18 Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as 23 Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months and may be updated, replaced, or obsoleted by other 27 documents at any time. It is inappropriate to use Internet-Drafts 28 as reference material or to cite them other than as "work in 29 progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt. 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html. 37 This document is a submission of the IETF NTP WG. Comments should 38 be directed to the NTP WG mailing list, ntpwg@lists.ntp.isc.org. 40 This Internet-Draft will expire on April, 2006. 42 Abstract 44 The Network Time Protocol (NTP) is widely used to synchronize 45 computer clocks in the Internet. This memorandum describes 46 the algorithms used by Version 4 of the NTP (NTPv4) to calculate 47 time values. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 2. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . . 5 55 3. Clock Selection Algorithm . . . . . . . . . . . . . . . . . . 7 57 4. Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . 8 59 5. Clock Combining Algorithm . . . . . . . . . . . . . . . . . . 9 61 6. Polling Algorithm . . . . . . . . . . . . . . . . . . . . . . 10 63 7. Clock Discipline Algorithm . . . . . . . . . . . . . . . . . . 10 64 7.1 Poll Interval Control . . . . . . . . . . . . . . . . . . 12 65 7.2 State Machine . . . . . . . . . . . . . . . . . . . . . . 13 67 8. Security Considerations . . . . . . . . . . . . . . . . . . . . 15 69 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 15 71 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 73 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 74 11.1 Normative References . . . . . . . . . . . . . . . . . . 15 75 11.2 Informative References . . . . . . . . . . . . . . . . . 15 77 12. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 16 79 Intellectual Property and Copyright Statements . . . . . . . . 17 81 1. Introduction 83 The Network Time Protocol Version 3 (NTPv3) specified in RFC 1305 84 [MIL92] has been widely used to synchronize computer clocks in the 85 global Internet. It provides comprehensive mechanisms to access 86 national time and frequency dissemination services, organize the NTP 87 subnet of servers and clients and adjust the system clock in each 88 participant. In most places of the Internet of today, NTP provides 89 accuracies of 1-50 ms, depending on the characteristics of the 90 synchronization source and network paths. 92 NTP is designed for use by clients and servers with a wide range of 93 capabilities and over a wide range of network jitter and clock 94 frequency wander characteristics. Many users of NTP in the Internet 95 of today use a software distribution available from www.ntp.org. The 96 distribution, which includes the full suite of NTP options, 97 mitigation algorithms and security schemes, is a relatively complex, 98 real-time application. While the software has been ported to a wide 99 variety of hardware platforms ranging from personal computers to 100 supercomputers, its sheer size and complexity is not appropriate for 101 many applications. This facilitated the development of the Simple 102 Network Time Protocol Version 4 (SNTPv4) as described in RFC 2030 103 [MIL96]. 105 Since the standardization of NTPv3, there has been significant 106 development which has led to Version 4 of the Network Time Protocol 107 (NTPv4). This document describes NTPv4, which introduces new 108 functionality to NTPv3 as described in RFC 1305, and functionality 109 expanded from that of SNTPv4 as described in RFC 2030 (SNTPv4 is a 110 subset of NTPv4). 112 When operating with current and previous versions of NTP and SNTP, 113 NTPv4 requires no changes to the protocol or implementations now 114 running or likely to be implemented specifically for future NTP or 115 SNTP versions. The NTP and SNTP packet formats are the same and the 116 arithmetic operations to calculate the client time, clock offset and 117 roundtrip delay are the same. To a NTP or SNTP server, NTP and SNTP 118 clients are indistinguishable; to a NTP or SNTP client, NTP and SNTP 119 servers are indistinguishable. 121 NTP usually operates simultaneously with multiple servers and may 122 have multiple clients of its own. NTP employs several algorithms 123 that together allow the calculation of time from messages that come 124 from an NTP or SNTP server. The overall organization of the 125 algorithms is illustrated in Figure 1. For every server there are two 126 processes, a peer process which receives and processes each packet, 127 and a companion poll process which sends packets to the server at 128 programmed intervals. State variables and data measurements 129 are maintained separately for each pair of processes in a block of 130 memory called the peer variables. The peer and poll processes 132 .......................................................... 133 . Remote .. Peer/Poll .. System . 134 . Servers .. Processes .. Process . 135 . .. .. . 136 .----------..-------------..-------------- . 137 .| |->| |..| | . 138 .|Server 1|..|Peer/Poll 1|->| | . 139 .| |<-| |..| | ............. 140 .----------..-------------..| | . Clock . 141 .Discipline . 142 . .. ^ ..| | .. Process . 143 . .. | ..| | .. . 144 .----------..-------------..| | |-----------|.. . 145 .| |->| |..| Selection |->| ..-------- . 146 .|Server 2|..|Peer/Poll 2|->| and | | Combining |->| Loop |->.-- 147 .| |<-| |..| Clustering | | Algorithm |..|Filter| . | 148 .----------..-------------..| Algorithms |->| |.------------ | 149 . .. ^ ..| | |-----------|. | 150 . .. | ..| | . | 151 .----------..-------------..| | . | 152 .| |->| |..| | . | 153 .|Server 3|..|Peer/Poll 3|->| | . | 154 .| |<-| |..| | . | 155 .----------..-------------..|------------| . | 156 ....................^..................................... | 157 | | 158 | | 159 | ............... | 160 | . /-----\ . | 161 '----------------------------------<-| VFO |-<-.---+ 162 . \-----/ . 163 . Clock Adjust. 164 . Process . 165 ............... 167 Figure 1. NTPv4 Algorithm Interactions 169 together with their variables collectively belong to an association. 170 Associations can be either temporary or permanent. Permanent 171 associations are described as persistent, while temporary 172 associations are referred to as preemptable or ephemeral. 174 As each NTP packet arrives, the server time is compared to the system 175 clock and an offset specific to that server is determined. The system 176 process refines these offsets using the selection, clustering and 177 combining algorithms and delivers a correction to the clock 178 discipline process, which functions as a lowpass filter to smooth the 179 data and close the feedback loop. The clock adjust process runs at 180 one-second intervals to amortize the corrections in small adjustments 181 that approximate a continuous, monotonic clock. The output of the 182 combining algorithm represents the best estimate of the system clock 183 offset relative to the server ensemble. The discipline algorithm 184 adjusts the frequency of the variable frequency oscillator (VFO) to 185 minimize this offset. Finally, the timestamps of each server are 186 compared to timestamps derived from the VFO in order to calculate the 187 server offsets and close the feedback loop. 189 This document is organized as follows. Section 2 describes the clock 190 filter algorithm. Section 3 describes the clock selection algorithm. 191 Section 4 describes the clustering algorithm. Section 5 describes 192 the clock combining algorithm. Section 6 describes the polling 193 algorithm. Section 7 describes the clock discipline algorithm. 195 NTPv4 is hereafter referred to simply as NTP, unless explicitly 196 noted. 198 2. Clock Filter Algorithm 200 The NTP clock filter algorithm selects the most appropriate sample 201 data while rejecting noise spikes due to packet collisions and 202 network congestion. The clock offset (?) and roundtrip delay (d) 203 samples are computed from the four most recent timestamps. Without 204 making any assumptions about the delay distributions, but assuming 205 the frequency difference or skew between the server and peer clocks 206 can be neglected, let (?,d) represent the offset and delay when the 207 path is otherwise idle; thus (?,d) represents the true offset and 208 delay values. The clock filter algorithm essentially acts as an 209 accurate estimator and produces an estimate of the time, known as 210 (?hat,dhat), from a sample sequence (?i,di), where i denotes a 211 particular sample at some time, collected for the path over an 212 appropriate interval under ambient traffic conditions. 214 The design of the clock filter algorithm was suggested by the 215 observation that packet switching networks are most often operated 216 well below the knee of the throughput-delay curve, which means that 217 packet queues are mostly small with relatively infrequent bursts. In 218 addition, the routing algorithm most often operates to minimize the 219 number of packet-switch hops and thus the number of queues. Not only 220 is the probability that an NTP packet finds a busy queue in one 221 direction relatively low, but the probability of packets from a 222 single exchange finding busy queuesin both directions is even lower. 223 Therefore, the best offset samples should occur with the lowest 224 delays. 226 Upon arrival of an NTP packet resulting from some poll interval at 227 time t=0, a shift register containing four variables (?i,di,ei,ti) is 228 populated with the 0th sample, (?0,d0,e0,t0). Here, e is the error 229 (in seconds), which is initially set to precision and grown at a rate 230 r=15 ppm for each epoch. If a packet has not arrived for three 231 successive poll intervals, then the sample (0,0,16,t) is shifted into 232 the register, where t is the last current known time. Missing data 233 samples that force this condition are never used in subsequent filter 234 calculations, but do prevent very old (i.e. stale) samples from being 235 used. 237 Next, the register contents are copied to a temporary list and sorted 238 by the metric ? designed to avoid missing data and devalued samples 239 older than the compromise Allan intercept ssuby(x) = 1500 s. The 240 Allan intercept is the intersection coordinate (x, y) of the phase 241 and frequency lines. It characterizes each particular timing source 242 and clock oscillator. A useful statistic is the x value, which 243 specifies the optimum time constant for the particular source and 244 oscillator combination. The x value ranges from about 500 s to 2000 245 s. Above this value the performance is limited by oscillator wander, 246 while below this value the performance is limited by system jitter. 247 For comparison, the NTPv4 clock discipline time constant is about 248 1000 s at a poll interval of 64 s. The y statistic represents the 249 best stability that can be achieved for the particular source and 250 oscillator, but is not useful for performance optimization. For this 251 reason, the term Allan intercept applies to the x value at the 252 intercept point. 254 If ej = infinity, then ?j = infinity; else, if tj-t > ssuby(x) then 255 ?j=Ksubd + ej; else, ?j=dj, where Ksubd=1 s is the selection 256 threshold. The algorithm essentially sorts the data by exchanging 257 sets; however, an exchange is not made unless to do so would reduce 258 the metric by at least the value of the precision. In other words, it 259 does not make sense to change the order in the list, which might 260 result in the loss of otherwise good samples, unless the metric 261 change is significant. The first entry (?0,d0,e0,t0) on the temporary 262 list represents the lowest delay sample, which is used to update the 263 peer offset ?=?0 and peer delay d=d0. The peer dispersion e is 264 calculated from the temporary list: 266 e=sum from k=0 to k=n-1 of [esubk/2^(k+1)]. 268 Finally, the temporary list is trimmed by discarding all entries 269 where ?j= infinity and all but the first devalued entry ?j >= Ksubd, 270 if one is present, leaving m (0<=mKsubs*psi, where Ksubs is a tuning parameter 281 that defaults to 3, the sample is a popcorn spike and is discarded. 283 Note that the peer jitter will increase to protect a legitimate step 284 change. 286 As demonstrated by simulation and practical experience, it is prudent 287 to avoid using samples more than once. Let tp be the epoch the peer 288 variables were last updated and t0 the epoch of the first sample on 289 the temporary list. If t0<=tp, the new sample is a duplicate or 290 earlier than the last one used. If this is true, the algorithm exits 291 without updating the system clock; otherwise, tp=t0 and the offset 292 can be used to update the system clock. The components of the tuple 293 (?, d, e, psi, tp) are called the peer variables. 295 3. Clock Selection Algorithm 297 In order to provide reliable synchronization, NTP uses multiple 298 redundant servers and multiple disjoint network paths whenever 299 possible. When a number of associations are established, it is not 300 clear beforehand which are truechimers and which are falsetickers. 301 A 'truechimer' is a clock that maintains timekeeping accuracy to a 302 previously published (and trusted) standard, while a 'falseticker' 303 is a clock that do not maintain that level of timekeeping accuracy. 304 Crucial to the success of this approach is a robust algorithm which 305 finds and discards the falsetickers from the raw server population, 306 since the timekeeping accuracy of a particular server may not be 307 known a priori. The clock selection algorithm determines from among 308 all associations a suitable subset of truechimers capable of 309 providing the most accurate and trustworthy time using principles 310 similar to [DOL95]. 312 The true offset ? of a correctly operating clock relative to UTC must 313 be contained in a computable range, called the confidence interval, 314 equal to the root distance defined below. Marzullo and Owicki [BER00] 315 devised an algorithm designed to find the intersection 316 interval containing the correct time given the confidence intervals 317 of m clocks, of which no more than f are considered incorrect. The 318 algorithm finds the smallest intersection interval containing points 319 in at least (m-f) of the given confidence intervals. 321 The clock selection algorithm operates as follows: 323 1. For each of m associations, construct a correctness interval 324 [? - rootdist(), ? + rootdist()]. 326 2. Select the lowpoint, midpoint and highpoint of these intervals. 327 Sort these values in a list from lowest to highest. Set the 328 number of falsetickers f = 0. 330 3. Set the number of midpoints d = 0. Set c = 0. Scan from lowest 331 endpoint to highest. Add one to c for every lowpoint, subtract 332 one for every highpoint, add one to d for every midpoint. 333 If c = m - f, stop; set l = current lowpoint. 335 4. Set c = 0. Scan from highest endpoint to lowest. Add one to c for 336 every highpoint, subtract one for every lowpoint, add one to d 337 for every midpoint. If c = m - f, stop; set u = current 338 highpoint. 340 5. Is d = f and l < u? 342 if yes, then follow step 5y, else, follow step 5n. 344 5y. Success: the intersection interval is [l,u]. 346 5n. Add one to f. Is f < m / 2? If yes, then go to step 3 again. 347 If no, then go to step 6. 349 6. Failure; a majority clique could not be found. Stop algorithm. 351 4. Clustering Algorithm 353 NTP configurations usually include several servers in order to 354 provide sufficient redundancy for the selection algorithm to 355 determine which are truechimers and which are not. When a sizeable 356 number of servers are present, the individual clock offsets for each 357 are not always the same, even if each server is closely synchronized 358 to UTC by one means or another. Small systematic differences in the 359 order of a millisecond or two are usually due to interface and 360 network latencies. Larger differences are due to asymmetric delays 361 and in the extreme due to asymmetric satellite/landline delays. 363 The clustering algorithm sifts the truechimers of the selection 364 algorithm to identify the survivors providing the best accuracy. In 365 principle, the sift could result in a single survivor and its offset 366 estimate used to discipline the system clock; however, a better 367 estimate usually results if the offsets of a number of survivors are 368 averaged together. So, a balance must be struck between reducing the 369 selection jitter by casting off outlyers and improving the offset 370 estimate by including more survivors in the average. 372 The clustering algorithm steps follow: 374 1. Let (?, ?, ?) represent a candidate peer with offset ?, jitter j 375 and a weight factor ? = stratum * MAXDIST + rootdist(). 377 2. Sort the candidates by increasing ?. Let n be the number of 378 candidates and NMIN the minimum number of survivors. 380 3. For each candidate compute the selection jitter jsubS (RMS peer 381 offset differences between this and all other candidates). 383 4. Select jsubmax as the candidate with maximum jsubS. 385 5. Select jsubmin as the candidate with minimum jsubS. 387 6. Does the condition (jsubmax < jsubmin OR n = NMIN) hold true? 389 If yes, go to step 6y. If no, go to step 6n. 391 6y. Done. The remaining cluster survivors are correct. The 392 survivors are in the v. structure sorted by ?. 394 6n. Delete the outlyer candidate with jsubmax; reduce n by one, and 395 go back to step 3. 397 5. Clock Combining Algorithm 399 The selection and clustering algorithms operate to select a single 400 system peer based on stratum and root distance. The result is that 401 the NTP subnet forms a logical tree with the primary servers at 402 the root and other servers at increasing stratum levels toward the 403 leaves. However, since each server on the tree ordinarily runs the 404 NTP protocol with several other servers at equal or lower stratum, 405 these servers can provide diversity paths for backup and cross 406 checking. While these other paths are not ordinarily used directly 407 for synchronization, it is possible that increased accuracy can be 408 obtained by averaging their offsets according to appropriately chosen 409 weights. 411 The result of the clustering algorithm is a set of survivors (there 412 must be at least one) that represent truechimers, or correct clocks. 413 If only one peer survives or if the prefer peer is among the 414 survivors, that peer becomes the system peer and the combining 415 algorithm is not used. Otherwise, the final clock correction is 416 determined by the combining algorithm. 418 Let the tuples (?subi,psisubi,?subi)represent the peer offset, peer 419 jitter, and root distance for the ith survivor. Then the combined 420 peer offset and peer jitter is, respectively: 422 T=a*sum over all i of [?subi/?subi] and psisubr=a*sum over all i of 423 [(psisubi)^2/?subi]^(1/2), 425 where a is a normalization constant: 427 a=1/[sum over all i of [1/?subi]. 429 The result T is the system offset processed by the clock discipline 430 algorithm. Note that the root distance cannot be less than 431 the precision in order to avoid divide exceptions. 433 Let psisubs represent the selection jitter associated with the system 434 peer and psisubr as above. Then the system jitter is defined as: 436 sj=[(psisubr)^2+(psisubs)^2]^(1/2). 438 The system jitter represents the best estimate of error in computing 439 the clock offset. It is interpreted as the expected error statistic 440 available to application program. 442 6. Polling Algorithm 444 The poll process determines whether and when to send a poll message 445 to the server. Ordinarily, polls are sent at regular intervals 446 determined by the clock discipline time constant. In some cases 447 where justified by network load, performance can be improved and 448 network jitter reduced by sending several messages instead of just 449 one. This can be done when the server is unreachable, when it is 450 reachable or both. The most common cases where this is advisable is 451 when using very large poll intervals in the order of several hours or 452 more. 454 The poll interval starts out normally at about one minute. If the 455 offset is less than a tuning constant times the system jitter for 456 some number of polls, it is increased, but usually not above 1024 s. 457 Otherwise, it is decreased, but usually not below 64 s. The limits 458 can be changed to a lower limit of 16 s and/or to an upper limit of 459 36 h. In order to minimize network traffic, when a server has not 460 been heard for some time, the poll interval is increased in stages to 461 1024 s. 463 7. Clock Discipline Algorithm 465 The clock discipline algorithm synchronizes the computer clock with 466 respect to the best time value from each server and the best 467 combination of servers. This algorithm automatically adapts to 468 changes in operating environment without manual configuration or 469 real-time management functions. The clock discipline algorithm is 470 implemented as the feedback control system shown in Figure 2. 472 --------- 473 ?r + | \ +----------------+ 474 NTP --------->| Phase \ Vd | | Vs 475 ?c - | Detector ------>| Clock Filter |-----+ 476 +-------->| / | | | 477 | | / +----------------+ | 478 | --------- | 479 | | 480 ----- | 481 / \ | 482 | VFO | | 483 \ / | 484 ----- +-------------------------------------+ | 485 ^ | Loop Filter | | 486 | | | | 487 | | +---------+ x +-------------+ | | 488 | | | |<-----| | | | 489 +------|-| Clock | y | Phase/Freq |<---|------+ 490 | | Adjust |<-----| Prediction | | 491 | | | | | | 492 | +---------+ +-------------+ | 493 | | 494 +-------------------------------------+ 496 Figure 2. Clock Discipline Algorithm 498 The variable ?subr represents the combined server reference phase and 499 ?subc the control phase of the VFO. Each update received from a 500 server produces a signal Vsubd representing the instantaneous phase 501 difference ?subr - ?subc. The clock filter for each server functions 502 as a tapped delay line, with the output taken at the tap selected by 503 the clock filter algorithm. The selection, clustering and combining 504 algorithms combine the data from multiple filters to produce the 505 signal Vsubs. The loop filter, with impulse response F(t), produces 506 the signal Vsubc which controls the VFO frequency ?subc. Thus, its 507 phase ?subc follows: 509 ?subc = integral over t of (?subc(t)dt) 511 which closes the loop. The Vsubc signal is generated by an 512 adjustment process which runs at intervals of one second in the NTP 513 daemon or one tick in the kernel. 515 The NTPv4 discipline includes both PLL and FLL capabilities. The 516 selection of which mode to use, FLL or PLL and in what combination, 517 is made on the basis of the poll exponent tau. In the NTPv4 design, 518 PLL mode is used at smaller values of tau, while FLL mode is used at 519 larger values. In between, a combination of PLL and FLL modes is 520 used. This improves the clock accuracy and stability, especially for 521 poll intervals larger than the Allan intercept. 523 x <------(Phase Correction)<--. 524 | 525 ysubfll | 526 .-(FLL Predict)<-------+<--Vsubs 527 | | 528 \|/ | 529 y <--(Sum) | 530 ^ | 531 | | 532 '-(PLL Predict)<-------' 533 ysubpll 535 Figure 3. FLL/PLL Prediction Functions 537 In PLL mode y is a time integral over all past values of Vs, so the 538 PLL frequency adjustment required is: 540 ysubPLL = Vsubs*mu/(64Tsubc)^2. 542 where Tsubc is the time constant. In FLL mode, is an average of past 543 frequency changes, as computed from Vsubs and mu. The goal of the 544 algorithm is to reduce Vsubs to zero; so, to the extent this 545 has been successful in the past, previous values can be assumed zero 546 and the average becomes: 548 ysubFLL = (Vsubs-x)/(8mu). 550 where x is the residual phase error computed by the clock adjust 551 process. 553 Finally, in both PLL and FLL modes set the phase to x=Vsubs and 554 frequency y=y+ysubPLL+ysubFLL. 556 Once each second the adjustment process computes a phase increment 557 z=x/(16*Tsubc) and new phase adjustment x=x-z. The phase increment z 558 is passed to the kernel time adjustment function. This continues 559 until the next update which recomputes x and y. 561 A key factor in the performance of the PLL/FLL hybrid algorithm are 562 the weight factors for the ysubPLL and ysubFLL adjustments, which 563 depend on the poll exponent tau which in turn determines the time 564 constant Tsubc = 2^(tau), in seconds. PLL contributions should 565 dominate at the lower values of tau, while FLL contributions should 566 dominate at the higher values. The clock discipline algorithm 567 response times to several PPM deviation examples is presented in 568 [MIL05]. 570 7.1 Poll Interval Control 572 The NTPv4 algorithm aims to set the averaging time somewhere near the 573 Allan intercept. A key to this strategy is the measured clock jitter 574 and oscillator wander statistics. The clock jitter is estimated from 575 phase differences psisubc=^(1/2), where the brackets indicate 576 an exponential average. The oscillator wander is estimated from 577 frequency differences psisubf = Tsubc*^(1/2). As the poll 578 exponent tau increases, it is expected that psisubc will decrease and 579 psisubf will increase, depending on the relative contributions of 580 phase noise and frequency noise. 582 In the NTPv4 algorithm at each update a counter is incremented by one 583 if x is within the bound |x|< 4psisubc, where the constant 4 is 584 determined by experiment, and decremented by one otherwise. 586 In order to avoid needless hunting, a degree of hysteresis is built 587 into the scheme. If the counter reaches an upper limit 30, tau is 588 increased by one; if it reaches a lower limit -30, tau is reduced by 589 two. In either case the counter is reset to zero. Under normal 590 conditions tau increases in stages from a default lower limit of 6 591 (64 s) to a default upper limit of 10 (1024 s). However, if the 592 wander increases because the oscillator frequency is deviating too 593 fast, tau is quickly reduced. Once the oscillator wander subsides, 594 tau is slowly increased again. Under typical operating conditions, 595 tau hovers close to the maximum; but, on occasions of a heat spike 596 when the oscillator wanders more than about 1 PPM, it quickly drops 597 to lower values until the wander subsides. 599 7.2 State Machine 601 The clock discipline must operate over an extremely wide range of 602 network jitter and oscillator wander conditions without manual 603 intervention or prior configuration. As determined by past 604 experience and experiment, the data grooming algorithms work well to 605 sift good data from bad, especially under conditions of light to 606 moderate network and server loads. The PLL/FLL hybrid algorithm may 607 perform poorly and even become unstable under heavy network loading. 608 The state machine functions to bypass some discipline functions under 609 conditions of hardware or software failure, severe time or frequency 610 transients and especially when the poll interval is relatively large. 612 Under normal conditions the NTP discipline algorithm writes the 613 current frequency offset to a file at hourly intervals. Once the file 614 is written and the daemon is restarted after reboot, for example, it 615 initializes the frequency offset from the file, which avoids the 616 training time, possibly several hours, to determine the intrinsic 617 frequency offset when the daemon is started for the first time. 618 When toll charges accrue for every NTP message, as in a telephone 619 modem service, it is important to determine the presence of a a 620 possibly large intrinsic frequency offset, especially if the interval 621 between telephone calls must be 15 minutes or more. For instance, 622 without the state machine it might take many calls spaced at 15 623 minutes until the frequency offset is determined and the call 624 spacing can be increased. With the state machine it usually takes 625 only two calls to complete the process. 627 The clock state machine transition function is shown in Table 1. It 628 determines the action and next state when an update with specified 629 offset occurs in a given state shown in the first column. The second 630 column shows what happens if the offset is less than the step 631 threshold, the third when the step threshold is exceeded but not the 632 stepout threshold and the third when both thresholds are exceeded. 633 The state machine responds to the current state and event to cause 634 the action shown. 636 Table 1. Clock State Machine Transition Function 637 ====================================================================== 638 | State | abs(T) < STEP | abs(T) > STEP | Comments | 639 ---------------------------------------------------------------------- 640 | NSET | > FREQ; adjust | > FREQ; step | no frequency | 641 | | time | time | file | 642 ---------------------------------------------------------------------- 643 | FSET | > SYNC; adjust | > SYNC; step | frequency file | 644 | | time | time | | 645 ---------------------------------------------------------------------- 646 | SPIK | > SYNC; adjust | if (<900 s)>SPIK | outlier detected | 647 | | freq, adjust time | else SYNC; step | | 648 | | | freq; step time | | 649 ---------------------------------------------------------------------- 650 | FREQ | if (<900 s)> FREQ | if (<900 s)>FREQ | initial frequency | 651 | | else >SYNC; step | else >SYNC; step | | 652 | | freq, adjust time | freq, adjust time | | 653 ---------------------------------------------------------------------- 654 | SYNC | >SYNC; adjust freq| if (<900 s)>SPIK | normal operation | 655 | | adjust time | else >SYNC; step | | 656 | | | freq; step time | | 657 ---------------------------------------------------------------------- 659 The actions listed in the state diagram include adjust-frequency, 660 step-frequency, adjust-time and step-time actions. The normal action 661 in the SYNC state is to adjust both frequency and time. The step-time 662 action is to set the system clock, while the step-frequency action is 663 to calculate the frequency offset directly. This has to be done 664 carefully to avoid contamination of the frequency estimate by the 665 phase adjustment since the last update. 667 The machine can be initialized in two states, FSET if the frequency 668 file is present or NSET if it has not yet been created. If the file 669 is not present, this may be the first time the discipline has ever 670 been activated, so it may have to quickly determine the oscillator 671 intrinsic frequency offset. It is important to realize that a number 672 of NTP messages may be exchanged before the mitigation algorithms 673 determine a reliable time offset and call the clock discipline 674 algorithm. 676 When the first valid offset arrives in the NSET state, (1) the time 677 is stepped to that offset, if necessary, (2) the watchdog counter is 678 started and (3) the machine exits to the FREQ state. Subsequently, 679 updates will be ignored until the stepout threshold has been reached, 680 at which time the frequency is stepped, the time is stepped if 681 necessary, and the machine exits to SYNC state. When the first valid 682 offset arrives in the FSET state, the frequency has already been 683 initialized, so the machine does the same things as in the NSET 684 state, but exits to the SYNC state. 686 In the SYNC state the machine watches for outliers above the step 687 threshold. If one is found, the machine exits to SPIK state and 688 starts the watchdog timer. If another offset less than the step 689 threshold is found, the counter is stopped and the machine exits to 690 the SYNC state. If the watchdog timer reaches the stepout threshold, 691 the time and frequency are both stepped as required and the machine 692 exits to the SYNC state. 694 8. Security Considerations 696 There are no security considerations. 698 9. IANA Considerations 700 There are no IANA considerations. 702 10. Acknowledgements 704 11. References 706 11.1 Normative References 708 11.2 Informative References 710 [NTP05] Burbank, J., Martin, J., and Mills, D., "Network Time Protocol 711 Version 4 Protocol Specification," 712 , July 2005, work in 713 progress. 715 [MIL92] Mills, D., "Network Time Protocol (Version 3) Specification, 716 Implementation", RFC 1305, March 1992. 718 [MIL96] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for 719 IPv4, IPv6, and OSI", RFC 2030, October 1996. 721 [DOL95] Dolev, D., J. Halpern, B. Simons, and R. Strong, "Dynamic 722 Fault-Tolerant Clock Synchronization," JACM 42, January 1995, 723 pp. 143-185. 725 [BER00] Berthaud, J. M., "Time Synchronization over Networks using 726 Convex Closures," IEEE/ACM Transactions on Networking, April 727 2000, pp. 265-277. 729 12. Authors' Addresses 731 William T. Kasch (Editor) 732 The Johns Hopkins University Applied Physics Laboratory (JHU/APL) 733 11100 Johns Hopkins Road 734 Laurel, MD 20723 736 Phone: +1 443-778-7463 737 EMail: william.kasch@jhuapl.edu 739 Jack L. Burbank (Editor) 740 JHU/APL 741 11100 Johns Hopkins Road 742 Laurel, MD 20723 744 Phone: +1 443-778-7127 745 EMail: jack.burbank@jhuapl.edu 747 Dr. David L. Mills 748 The University of Delaware 749 Electrical Engineering Department 750 University of Delaware 751 Newark, DE 19716 753 Phone: (302) 831-8247 754 EMail: mills@udel.edu 756 Intellectual Property Statement 758 The IETF takes no position regarding the validity or scope of any 759 Intellectual Property Rights or other rights that might be claimed to 760 pertain to the implementation or use of the technology described in 761 this document or the extent to which any license under such rights 762 might or might not be available; nor does it represent that it has 763 made any independent effort to identify any such rights. Information 764 on the procedures with respect to rights in RFC documents can be 765 found in BCP 78 and BCP 79. 767 Copies of IPR disclosures made to the IETF Secretariat and any 768 assurances of licenses to be made available, or the result of an 769 attempt made to obtain a general license or permission for the use of 770 such proprietary rights by implementers or users of this 771 specification can be obtained from the IETF on-line IPR repository at 772 http://www.ietf.org/ipr. 774 The IETF invites any interested party to bring to its attention any 775 copyrights, patents or patent applications, or other proprietary 776 rights that may cover technology that may be required to implement 777 this standard. Please address the information to the IETF at 778 ietf-ipr@ietf.org. 780 Disclaimer of Validity 782 This document and the information contained herein are provided on an 783 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 784 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 785 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 786 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 787 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 788 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 790 Copyright Statement 792 Copyright (C) The Internet Society (2005). This document is subject 793 to the rights, licenses and restrictions contained in BCP 78, and 794 except as set forth therein, the authors retain all their rights. 796 Acknowledgment 798 Funding for the RFC Editor function is currently provided by the 799 Internet Society.