idnits 2.17.1 draft-ietf-ntp-ntpv4-algorithms-01.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 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1087. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1064. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1071. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1077. ** 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.) -- The document date (November 9, 2005) is 6743 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '6' is defined on line 1022, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 1305 (ref. '1') (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 2030 (ref. '2') (Obsoleted by RFC 4330) Summary: 3 errors (**), 0 flaws (~~), 4 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NTP WG W. Kasch, Ed. 3 Internet-Draft J. Burbank, Ed. 4 Expires: May 13, 2006 JHU/APL 5 D. Mills 6 U. Del. 7 November 9, 2005 9 The Network Time Protocol Version 4 Algorithm Specification 10 draft-ietf-ntp-ntpv4-algorithms-01 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on May 13, 2006. 37 Copyright Notice 39 Copyright (C) The Internet Society (2005). 41 Abstract 43 The Network Time Protocol (NTP) is widely used to synchronize 44 computer clocks in the Internet. This memorandum describes the 45 algorithms used by Version 4 of the NTP (NTPv4) to calculate time 46 values. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 2. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . . 6 52 3. Clock Selection Algorithm . . . . . . . . . . . . . . . . . . 8 53 4. Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . 9 54 5. Clock Combining Algorithm . . . . . . . . . . . . . . . . . . 10 55 6. Polling Algorithm . . . . . . . . . . . . . . . . . . . . . . 11 56 7. Clock Discipline Algorithm . . . . . . . . . . . . . . . . . . 17 57 7.1. Poll Interval Control . . . . . . . . . . . . . . . . . . 20 58 7.2. State Machine . . . . . . . . . . . . . . . . . . . . . . 20 59 8. Security Considerations . . . . . . . . . . . . . . . . . . . 22 60 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 61 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 62 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 63 11.1. Normative References . . . . . . . . . . . . . . . . . . . 22 64 11.2. Informative References . . . . . . . . . . . . . . . . . . 23 65 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 66 Intellectual Property and Copyright Statements . . . . . . . . . . 25 68 1. Introduction 70 The Network Time Protocol Version 3 (NTPv3) specified in [1] has been 71 widely used to synchronize computer clocks in the global Internet. 72 It provides comprehensive mechanisms to access national time and 73 frequency dissemination services, organize the NTP subnet of servers 74 and clients and adjust the system clock in each participant. In most 75 places of the Internet of today, NTP provides accuracies of 1-50 ms, 76 depending on the characteristics of the synchronization source and 77 network paths. 79 NTP is designed for use by clients and servers with a wide range of 80 capabilities and over a wide range of network jitter and clock 81 frequency wander characteristics. Many users of NTP in the Internet 82 of today use a software distribution available from www.ntp.org. The 83 distribution, which includes the full suite of NTP options, 84 mitigation algorithms and security schemes, is a relatively complex, 85 real-time application. While the software has been ported to a wide 86 variety of hardware platforms ranging from personal computers to 87 supercomputers, its sheer size and complexity is not appropriate for 88 many applications. This facilitated the development of the Simple 89 Network Time Protocol Version 4 (SNTPv4) as described in [2]. 91 Since the standardization of NTPv3, there has been significant 92 development which has led to Version 4 of the Network Time Protocol 93 (NTPv4). This document describes NTPv4, which introduces new 94 functionality to NTPv3 as described in RFC 1305, and functionality 95 expanded from that of SNTPv4 as described in RFC 2030 (SNTPv4 is a 96 subset of NTPv4). 98 When operating with current and previous versions of NTP and SNTP, 99 NTPv4 requires no changes to the protocol or implementations now 100 running or likely to be implemented specifically for future NTP or 101 SNTP versions. The NTP and SNTP packet formats are the same and the 102 arithmetic operations to calculate the client time, clock offset and 103 round trip delay are the same. To a NTP or SNTP server, NTP and SNTP 104 clients are indistinguishable; to a NTP or SNTP client, NTP and SNTP 105 servers are indistinguishable. 107 NTP usually operates simultaneously with multiple servers and may 108 have multiple clients of its own. NTP employs several algorithms 109 that together allow the calculation of time from messages that come 110 from an NTP or SNTP server. The overall organization of the 111 algorithms is illustrated in Figure 1. For every server there are 112 two processes, a peer process which receives and processes each 113 packet, and a companion poll process which sends packets to the 114 server at programmed intervals. State variables and data 115 measurements are maintained separately for each pair of processes in 116 a block of memory called the peer variables. The peer and poll 117 processes together with their variables collectively belong to an 118 association. Associations can be either temporary or permanent. 119 Permanent associations are described as persistent, while temporary 120 associations are referred to as preemptable or ephemeral. 121 .......................................................... 122 . Remote .. Peer/Poll .. System . 123 . Servers .. Processes .. Process . 124 . .. .. . 125 .----------..-------------..-------------- . 126 .| |->| |..| | . 127 .|Server 1|..|Peer/Poll 1|->| | . 128 .| |<-| |..| | ............ 129 .----------..-------------..| | . Clock . 130 .Discipline. 131 . .. ^ ..| | .. Process . 132 . .. | ..| | .. . 133 .----------..-------------..| | |-----------|.. . 134 .| |->| |..| Selection |->| ..-------- . 135 .|Server 2|..|Peer/Poll 2|->| and | | Combining |->| Loop | . 136 .| |<-| |..| Clustering | | Algorithm |..|Filter| . 137 .----------..-------------..| Algorithms |->| |.----------- 138 . .. ^ ..| | |-----------|. | 139 . .. | ..| | . | 140 .----------..-------------..| | . | 141 .| |->| |..| | . | 142 .|Server 3|..|Peer/Poll 3|->| | . | 143 .| |<-| |..| | . | 144 .----------..-------------..|------------| . | 145 ....................^..................................... | 146 | | 147 | \|/ 148 | ............... 149 | . /-----\ . 150 '----------------------------------<-| VFO |-<-. 151 . \-----/ . 152 . Clock Adjust. 153 . Process . 154 ............... 156 Figure 1 NTPv4 Algorithm Interactions 158 As each NTP packet arrives, the server time is compared to the system 159 clock and an offset specific to that server is determined. The 160 system process refines these offsets using the selection, clustering 161 and combining algorithms and delivers a correction to the clock 162 discipline process, which functions as a lowpass filter to smooth the 163 data and close the feedback loop. The clock adjust process runs at 164 one-second intervals to amortize the corrections in small adjustments 165 that approximate a continuous, monotonic clock. The output of the 166 combining algorithm represents the best estimate of the system clock 167 offset relative to the server ensemble. The discipline algorithm 168 adjusts the frequency of the variable frequency oscillator (VFO) to 169 minimize this offset. Finally, the timestamps of each server are 170 compared to timestamps derived from the VFO in order to calculate the 171 server offsets and close the feedback loop. 173 Depending on whether an NTP host is acting as server or client, or 174 whether the host is an SNTP or full NTP host, the subset of 175 algorithms it employs varies. The relationship between host role/ 176 type and algorithm employment is summarized in Table 1. 178 Table 1. Relationship between Algorithms and NTP Host Type/Role 179 ===================================================================== 180 | Algorithm | Applicability | 181 --------------------------------------------------------------------- 182 | Clock Filter | Required by all NTP Servers | 183 --------------------------------------------------------------------- 184 | Clock Selection | Applies to NTP hosts utilizing more than one | 185 | source | 186 --------------------------------------------------------------------- 187 | Clustering | Applies to NTP hosts utilizing more than one | 188 | | source | 189 --------------------------------------------------------------------- 190 | Clock Combining | Applies to NTP hosts utilizing more than one | 191 | | source | 192 --------------------------------------------------------------------- 193 | Polling | Applies to all NTP hosts. | 194 --------------------------------------------------------------------- 195 | Clock Discipline | Not required by SNTP clients. Applies to all| 196 | | other NTP hosts. | 197 --------------------------------------------------------------------- 199 This document is organized as follows. Section 2 describes the clock 200 filter algorithm. Section 3 describes the clock selection algorithm. 201 Section 4 describes the clustering algorithm. Section 5 describes 202 the clock combining algorithm. Section 6 describes the polling 203 algorithm. Section 7 describes the clock discipline algorithm. 204 Sections 8 and 9 presents Security Considerations and IANA 205 Considerations, respectively. Much of the information contained 206 within this document is based on material from. [3] 208 NTPv4 is hereafter referred to simply as NTP, unless explicitly 209 noted. 211 The remainder of this document contains numerous variables and 212 mathematical expressions. Those variables take the form of Greek 213 characters. Those Greek characters are spelled out by their full 214 name, with capitolized variables referring to the upper case Greek 215 character. For example Delta refers to the uppercase Greek 216 character, where delta refers to the lowercase Greek character. 217 Furthermore, subscripts are denoted with a '_' separating the 218 variable name and the subscript. For example 'theta_i' refers to the 219 variable lowercase Greek character theta with subscript i, or 220 phenotically 'theta sub i.' 222 2. Clock Filter Algorithm 224 The NTP clock filter algorithm selects the most appropriate sample 225 data while rejecting noise spikes due to packet collisions and 226 network congestion. The clock offset (theta) and roundtrip delay 227 (delta) samples are computed from the four most recent timestamps. 228 Without making any assumptions about the delay distributions, but 229 assuming the frequency difference or skew between the server and peer 230 clocks can be neglected, let (theta, delta) represent the offset and 231 delay when the path is otherwise idle; thus (theta, delta) represents 232 the true offset and delay values. The clock filter algorithm 233 essentially acts as an accurate estimator and produces an estimate of 234 the time, known as (theta_hat, delta_hat), from a sample sequence 235 (theta_i, delta_i), where i denotes a particular sample at some time, 236 collected for the path over an appropriate interval under ambient 237 traffic conditions. 239 The design of the clock filter algorithm was suggested by the 240 observation that packet switching networks are most often operated 241 well below the knee of the throughput-delay curve, which means that 242 packet queues are mostly small with relatively infrequent bursts. In 243 addition, the routing algorithm most often operates to minimize the 244 number of packet-switch hops and thus the number of queues. Not only 245 is the probability that an NTP packet finds a busy queue in one 246 direction relatively low, but the probability of packets from a 247 single exchange finding busy queuesin both directions is even lower. 248 Therefore, the best offset samples should occur with the lowest 249 delays. 251 Upon arrival of an NTP packet resulting from some poll interval at 252 time t=0, a shift register containing four variables (theta_i, 253 delta_i, e_i, t_i) is populated with the 0th sample, (theta_0, 254 delta_0, e_0, t_0). Here, e is the error (in seconds), which is 255 initially set to precision and grown at a rate r=15 ppm for each 256 epoch. If a packet has not arrived for three successive poll 257 intervals, then the sample (0, 0, 16, t) is shifted into the 258 register, where t is the last current known time. Missing data 259 samples that force this condition are never used in subsequent filter 260 calculations, but do prevent very old (i.e. stale) samples from being 261 used. 263 Next, the register contents are copied to a temporary list and sorted 264 by the metric lambda designed to avoid missing data and devalued 265 samples older than the compromise Allan intercept sigma_y(x) = 1500 266 s. The Allan intercept is the intersection coordinate (x, y) of the 267 phase and frequency lines. It characterizes each particular timing 268 source and clock oscillator. A useful statistic is the x value, 269 which specifies the optimum time constant for the particular source 270 and oscillator combination. The x value ranges from about 500 s to 271 2000 s. Above this value the performance is limited by oscillator 272 wander, while below this value the performance is limited by system 273 jitter. For comparison, the NTPv4 clock discipline time constant is 274 about 1000 s at a poll interval of 64 s. The y statistic represents 275 the best stability that can be achieved for the particular source and 276 oscillator, but is not useful for performance optimization. For this 277 reason, the term Allan intercept applies to the x value at the 278 intercept point. 280 If e_j = infinity, then lambda_j = infinity; else, if t_j-t > 281 sigma_y(x) then lambda_j = K_d + e_j; else, lambda_j = delta_j, where 282 K_d = 1 s is the selection threshold. The algorithm essentially 283 sorts the data by exchanging sets; however, an exchange is not made 284 unless to do so would reduce the metric by at least the value of the 285 precision. In other words, it does not make sense to change the 286 order in the list, which might result in the loss of otherwise good 287 samples, unless the metric change is significant. The first entry 288 (theta_0, delta_0, e_0, t_0) on the temporary list represents the 289 lowest delay sample, which is used to update the peer offset theta = 290 theta_0 and peer delay delta = d_0. The peer dispersion e is 291 calculated from the temporary list: 293 e=sum from k=0 to k=n-1 of [e_k/(2^(k+1))]. 295 Finally, the temporary list is trimmed by discarding all entries 296 where lambda_j = infinity and all but the first devalued entry 297 lambda_j >= K_d, if one is present, leaving m (0 <= m < n) surviving 298 entries on the list. The peer jitter psi is used by the clustering 299 algorithm as a quality metric and in the computation of the expected 300 error: 302 psi=[ (1 / (m-1) ) * (sum from k = 1 to k = m-1 of [ (theta_k - 303 theta_0)^2) ]) ^ (1/2) ) ]. 305 A 'popcorn spike' is a transient outlier, usually only a single 306 sample, that is typical of congested Internet paths. The popcorn 307 spike suppressor is designed to detect and remove them. Let 308 theta_prime be the peer offset determined by the previous message and 309 psi the current peer jitter. If |theta - theta_prime| > (K_s * psi), 310 where K_s is a tuning parameter that defaults to 3, the sample is a 311 popcorn spike and is discarded. 313 Note that the peer jitter will increase to protect a legitimate step 314 change. 316 As demonstrated by simulation and practical experience, it is prudent 317 to avoid using samples more than once. Let t_p be the epoch the peer 318 variables were last updated and t_0 the epoch of the first sample on 319 the temporary list. If t_0 <= t_p, the new sample is a duplicate or 320 earlier than the last one used. If this is true, the algorithm exits 321 without updating the system clock; otherwise, t_p = t_0 and the 322 offset can be used to update the system clock. The components of the 323 five-tuple (theta, delta, e, psi, t_p) are called the peer variables. 325 3. Clock Selection Algorithm 327 In order to provide reliable synchronization, NTP uses multiple 328 redundant servers and multiple disjoint network paths whenever 329 possible. When a number of associations are established, it is not 330 clear beforehand which are truechimers and which are falsetickers. A 331 'truechimer' is a clock that maintains timekeeping accuracy to a 332 previously published (and trusted) standard, while a 'falseticker' is 333 a clock that do not maintain that level of timekeeping accuracy. 334 Crucial to the success of this approach is a robust algorithm which 335 finds and discards the falsetickers from the raw server population, 336 since the timekeeping accuracy of a particular server may not be 337 known a priori. The clock selection algorithm determines from among 338 all associations a suitable subset of truechimers capable of 339 providing the most accurate and trustworthy time using principles 340 similar to. [4] 342 The true offset theta of a correctly operating clock relative to UTC 343 must be contained in a computable range, called the confidence 344 interval, equal to the root distance defined below. Marzullo and 345 Owicki devised an algorithm designed to find the intersection 346 interval containing the correct time given the confidence intervals 347 of m clocks, of which no more than f are considered incorrect. The 348 algorithm finds the smallest intersection interval containing points 349 in at least (m - f) of the given confidence intervals. [5] 351 The clock selection algorithm operates as follows: 353 1. For each of m associations, construct a correctness interval 354 [(theta - rootdist()), (theta + rootdist())]. 356 2. Select the lowpoint, midpoint and highpoint of these 357 intervals. Sort these values in a list from lowest to highest. 358 Set the number of falsetickers f = 0. 360 3. Set the number of midpoints d = 0. Set c = 0. Scan from 361 lowest endpoint to highest. Add one to c for every lowpoint, 362 subtract one for every highpoint, add one to d for every midpoint. 363 If c >= m - f, stop; set l = current lowpoint 365 4. Set c = 0. Scan from highest endpoint to lowest. Add one to 366 c for every highpoint, subtract one for every lowpoint, add one to 367 d for every midpoint. If c >= m - f, stop; set u = current 368 highpoint. 370 5. Is d = f and l < u? 372 if yes, then follow step 5y, else, follow step 5n. 374 5y. Success: the intersection interval is [l, u]. 376 5n. Add one to f. Is f < (m / 2)? If yes, then go to step 3 377 again. If no, then go to step 6. 379 6. Failure; a majority clique could not be found. Stop 380 algorithm. 382 4. Clustering Algorithm 384 NTP configurations usually include several servers in order to 385 provide sufficient redundancy for the selection algorithm to 386 determine which are truechimers and which are not. When a sizeable 387 number of servers are present, the individual clock offsets for each 388 are not always the same, even if each server is closely synchronized 389 to UTC by one means or another. Small systematic differences in the 390 order of a millisecond or two are usually due to interface and 391 network latencies. Larger differences are due to asymmetric delays 392 and in the extreme due to asymmetric satellite/landline delays. 394 The clustering algorithm sifts the truechimers of the selection 395 algorithm to identify the survivors providing the best accuracy. In 396 principle, the sift could result in a single survivor and its offset 397 estimate used to discipline the system clock; however, a better 398 estimate usually results if the offsets of a number of survivors are 399 averaged together. So, a balance must be struck between reducing the 400 selection jitter by casting off outlyers and improving the offset 401 estimate by including more survivors in the average. 403 The clustering algorithm steps follow: 405 1. Let (theta, phi, Lambda) represent a candidate peer with 406 offset theta, jitter j and a weight factor Lambda = stratum * 407 MAXDIST + rootdist(). 409 2. Sort the candidates by increasing Lambda. Let n be the number 410 of candidates and NMIN the minimum number of survivors. 412 3. For each candidate compute the selection jitter jsubS (RMS 413 peer offset differences between this and all other candidates). 415 4. Select j_max as the candidate with maximum j_S. 417 5. Select j_min as the candidate with minimum j_S. 419 If yes, go to step 6y. If no, go to step 6n. 421 6y. Done. The remaining cluster survivors are correct. The 422 survivors are in the v. structure sorted by Lambda. 424 6n. Delete the outlyer candidate with j_max; reduce n by one, and 425 go back to step 3. 427 5. Clock Combining Algorithm 429 The selection and clustering algorithms operate to select a single 430 system peer based on stratum and root distance. The result is that 431 the NTP subnet forms a logical tree with the primary servers at the 432 root and other servers at increasing stratum levels toward the 433 leaves. However, since each server on the tree ordinarily runs the 434 NTP protocol with several other servers at equal or lower stratum, 435 these servers can provide diversity paths for backup and cross 436 checking. While these other paths are not ordinarily used directly 437 for synchronization, it is possible that increased accuracy can be 438 obtained by averaging their offsets according to appropriately chosen 439 weights. 441 The result of the clustering algorithm is a set of survivors (there 442 must be at least one) that represent truechimers, or correct clocks. 443 If only one peer survives or if the prefer peer is among the 444 survivors, that peer becomes the system peer and the combining 445 algorithm is not used. Otherwise, the final clock correction is 446 determined by the combining algorithm. 448 Let the three-tuple (theta_i, psi_i, Lambda_i) represent the peer 449 offset, peer jitter, and root distance for the ith survivor. Then 450 the combined peer offset and peer jitter is, respectively: 452 T = (a*sum) over all i of [theta_i / Lambda_i] and psi_r = (a * sum) 453 over all i of [(psi_i)^2 / Lambda_i]^(1/2), 455 where a is a normalization constant: 457 a=1/[sum over all i of [1 / Lambda_i]. 459 The result T is the system offset processed by the clock discipline 460 algorithm. Note that the root distance cannot be less than the 461 precision in order to avoid divide exceptions. 463 Let psi_s represent the selection jitter associated with the system 464 peer and psi_r as above. Then the system jitter is defined as: 466 sj=[(psi_r)^2 + (psi_s)^2]^(1/2). 468 The system jitter represents the best estimate of error in computing 469 the clock offset. It is interpreted as the expected error statistic 470 available to application program. 472 6. Polling Algorithm 474 The poll process determines whether and when to send a poll message 475 to the server. Ordinarily, polls are sent at regular intervals 476 determined by the clock discipline time constant. In some cases 477 where justified by network load, performance can be improved and 478 network jitter reduced by sending several messages instead of just 479 one. This can be done when the server is unreachable, when it is 480 reachable or both. The most common cases where this is advisable is 481 when using very large poll intervals in the order of several hours or 482 more 484 The poll interval starts out normally at about one minute. If the 485 offset is less than a tuning constant times the system jitter for 486 some number of polls, it is increased, but usually not above 1024 487 seconds Otherwise, it is decreased, but usually not below 64 seconds. 488 The limits can be changed to a lower limit of 16 seconds and/or to an 489 upper limit of 36 hours. In order to minimize network traffic, when 490 a server has not been heard for some time, the poll interval is 491 increased in stages to 1024 seconds. 493 The poll process sends packets to the server at designated intervals 494 tau and updates the "reach" register which establishes whether the 495 server is reachable. Table 2 shows the poll process routines and 496 Table 3 the variables shared by the process routines, including 497 poll(), peer_xmit(), fast_xmit() and poll_update(). 499 Table 2. Poll Process Routines 500 ===================================================================== 501 | Name | Description | Related routines | 502 --------------------------------------------------------------------- 503 | poll | poll | *clock_adjust, clock_filtert, | 504 | | | peer_xmit, poll_update | 505 --------------------------------------------------------------------- 506 | poll_update | poll update | *packet, *poll | 507 --------------------------------------------------------------------- 508 | peer_xmit | peer transmit | *poll, md5 | 509 --------------------------------------------------------------------- 510 | fast_xmit | fast transmit | *receive, md5 | 511 --------------------------------------------------------------------- 513 Table 3. Poll Process Variables 514 ===================================================================== 515 | Name | Process | Variable Description | 516 --------------------------------------------------------------------- 517 | hpoll | poll | host poll interval | 518 | hmode | poll | host mode | 519 | count | poll | burst counter | 520 | reach | poll | "reach" register | 521 | unreach | poll | unreach counter | 522 | t | local clock | current time | 523 | tau | local clock | poll interval | 524 | rho | system | system peer | 525 | M_BCST | parameter | broadcast server | 526 | M-BCLN | parameter | broadcast client | 527 | B_BURST | peer flag | burst enable | 528 | B_IBURST | peer flag | initial burst enable | 529 | B_COUNT | parameter | pkts in a burst | 530 --------------------------------------------------------------------- 532 The poll() routine is described in Figure 2. Each time the poll() 533 routine is called, the reach variable is shifted left by one bit. 534 When a packet is accepted by the packet() routine in the peer process 535 the rightmost bit is set to one. As long as reach is nonzero, the 536 server is considered reachable. However, if the rightmost three bits 537 become zero, indicating that packets from the server have not been 538 received for at least three poll intervals, a sample with MAXDIST 539 dispersion is shifted in the clock filter. This causes the server to 540 be devalued in the mitigation process. The unreach counter 541 increments at each poll interval; it is reset to zero if the reach 542 register is nonzero. If the counter exceeds the UNREACH parameter, 543 the poll exponent is incremented for each succeeding poll. This 544 reduces useless network load in case of server failure. The poll() 545 routine can operate in three modes. 547 Ordinarily, polls are sent at the interval selected by hpoll and 548 ppoll poll exponents assigned. However, if the iburst feature is 549 enabled and the server is not reachable, a burst of eight polls is 550 sent at two-second intervals. Alternatively or in addition, if the 551 burst feature is enabled and the server is reachable, a burst of 552 eight polls is sent as with iburst. This is especially useful at 553 very large poll intervals of many hours. The remaining routines are 554 straightforward. The poll() routine calls the peer_xmit() routine 555 when an association has been mobilized. The receive() routine calls 556 fast_xmit() when a client mode packet is received. Both cases are 557 shown in Figure 3. These routines copy values from the association 558 (peer_xmit()) or from the arriving packet (fast_xmit()) as shown in 559 the accompanying tables. The poll_update() routine shown in Figure 4 560 determines the next poll interval or burst interval. Variable names 561 in both routines are referenced in Tables 4 and 5, respectively. 562 --------------- ----------------- 563 | poll() |-->| hmode=M_BCST? | 564 --------------- ----------------- 565 if hmode=M_BCST == YES: 566 --------------- 567 |s.rho = NULL?| 568 --------------- 569 if s.rho=NULL == YES: 570 --------------- --------------- 571 |poll_update()|-->| exit() | 572 --------------- --------------- 573 if s.rho=NULL == NO: 574 --------------- 575 |hmode=M_BCLN?| 576 --------------- 577 if hmode=M_BCLN == YES: 578 --------------- --------------- 579 |poll_update()|-->| exit() | 580 --------------- --------------- 581 if hmode_M_BCLN == NO: 582 --------------- --------------- --------------- 583 | peer_xmit() |-->|poll_update()|-->| exit() | 584 --------------- --------------- --------------- 585 if hmode=M_BCST == NO: 586 --------------- 587 | burst = 0? | 588 --------------- 589 if burst = 0 == YES: 590 --------------- --------------- 591 | reach <<=1 |-->| reach = 0? | 592 --------------- --------------- 593 if reach = 0 == YES: 594 ---------------------- 595 | unreach > UNREACH? | 596 ---------------------- 597 if unreach > UNREACH == YES: 598 --------------- --------------- -----go to----- 599 | hpoll++ |-->| unreach++ |-->|hmode=M_BCLN?| 600 --------------- --------------- --------------- 601 (go to hmode=M_BCLN routine earlier in the figure) 602 if unreach > UNREACH == NO: 603 --------------- 604 | B_IBURST? | 605 --------------- 606 if B_IBURST == YES: 607 --------------- 608 | fit()? | 609 --------------- 610 if fit() == YES: 611 ---------------- -----go to----- 612 | burst=BCOUNT |-->| unreach++ | 613 ---------------- --------------- 614 if fit() == NO: 615 -----go to----- 616 | unreach++ | 617 --------------- 618 if B_IBURST == NO: 619 -----go to----- 620 | unreach++ | 621 --------------- 622 if reach = 0 == NO: 623 --------------- 624 | unreach = 0?| 625 --------------- 626 if unreach = 0 == YES: 627 -------------------- 628 | reach & 0x7 = 0? | 629 -------------------- 630 if reach & 0x7 = 0 == YES: 631 --------------------------- 632 | clock_filter(0,0,inf,t) | 633 --------------------------- 634 \|/ 635 ----------------- 636 | hpoll = c,tau | 637 ----------------- 638 \|/ 640 ----------------- 641 | B_BURST? | 642 ----------------- 643 if B_BURST == YES: 644 --------------- 645 | unreach = 0?| 646 --------------- 647 if unreach = 0 == YES: 648 --------------- -----go to----- 649 |burst=BCOUNT |-->|hmode=M_BCLN?| 650 --------------- --------------- 651 if unreach = 0 == NO: 652 -----go to----- 653 |hmode=M_BCLN?| 654 --------------- 655 if B_BURST == NO: 656 -----go to----- 657 |hmode=M_BCLN?| 658 --------------- 659 if unreach = 0 == NO: 660 -----go to----- 661 | hpoll=c,tau | 662 --------------- 663 if burst = 0 == NO: 664 --------------- -----go to----- 665 | burst-- |-->|hmode=M_BCLN?| 666 --------------- --------------- 667 END OF ROUTINE 669 Figure 2. Poll Routine 671 Table 4. Peer Fast Transmit Table 672 ===================================================================== 673 | Variable Name | Description | 674 --------------------------------------------------------------------- 675 | T1 | Origin Timestamp in NTP packet field | 676 | T2 | Receive Timestamp in NTP packet field | 677 | T3 | ??? | 678 | mac | ??? | 679 --------------------------------------------------------------------- 680 --------------------------- 681 | peer_xmit(),fast_xmit() | 682 --------------------------- 683 \|/ 684 --------------------------- 685 | *copy header | 686 --------------------------- 687 \|/ 688 --------------------------- 689 | T1, T2 | 690 --------------------------- 691 \|/ 692 --------------------------- 693 | T3 = clock | 694 --------------------------- 695 \|/ 696 --------------------------- 697 | mac = md5() | 698 --------------------------- 699 \|/ 700 --------------------------- 701 | xmitpacket() | 702 --------------------------- 703 \|/ 704 --------------------------- 705 | exit | 706 --------------------------- 708 Figure 3. Peer Fast Transmit 710 Table 5. Poll Process Variables 711 ===================================================================== 712 | Name | Process | Variable Description | 713 --------------------------------------------------------------------- 714 | ppoll | peer | peer poll interval | 715 | hpoll | poll | host poll interval | 716 | burst | poll | burst counter | 717 | timer | poll | poll timer | 718 | BTIME | parameter | burst time | 719 | MINPOLL | parameter | minimum poll interval | 720 | MAXPOLL | parameter | maximum poll interval | 721 --------------------------------------------------------------------- 722 --------------------------- 723 | poll_update() | 724 --------------------------- 725 \|/ 726 --------------------------- 727 | burst = 0? | 728 --------------------------- 729 if burst = 0 == YES: 730 -------------------------------------- 731 |hpoll=max(min(MAXPOLL,poll),MINPOLL)| 732 -------------------------------------- 733 \|/ 734 -------------------------------------- 735 |timer=(max(min(ppoll,hpoll),MINPOLL)| 736 -------------------------------------- 737 \|/ 738 -------------------------------------- 739 | exit | 740 -------------------------------------- 741 if burst = 0 == NO: 742 -------------------------------------- 743 | timer running? | 744 -------------------------------------- 745 if timer running == YES: 746 -------------------------------------- 747 | exit | 748 -------------------------------------- 749 if timer running == NO: 750 -------------------------------------- 751 | timer = BTIME | 752 -------------------------------------- 753 \|/ 754 -------------------------------------- 755 | exit | 756 -------------------------------------- 757 END OF ROUTINE 759 Figure 4. Poll Update 761 7. Clock Discipline Algorithm 763 The clock discipline algorithm synchronizes the computer clock with 764 respect to the best time value from each server and the best 765 combination of servers. This algorithm automatically adapts to 766 changes in operating environment without manual configuration or 767 real-time management functions. The clock discipline algorithm is 768 implemented as the feedback control system shown in Figure 5. 770 --------- 771 thetar + | \ +----------------+ 772 NTP --------->| Phase \ V_d | | V_s 773 thetac - | Detector ------>| Clock Filter |-----+ 774 +-------->| / | | | 775 | | / +----------------+ | 776 | --------- | 777 | | 778 ----- | 779 / \ | 780 | VFO | | 781 \ / | 782 ----- +-------------------------------------+ | 783 ^ | Loop Filter | | 784 | | | | 785 | | +---------+ x +-------------+ | | 786 | | | |<-----| | | | 787 +------|-| Clock | y | Phase/Freq |<---|------+ 788 | | Adjust |<-----| Prediction | | 789 | | | | | | 790 | +---------+ +-------------+ | 791 | | 792 +-------------------------------------+ 794 Figure 5. Clock Discipline Algorithm 796 The variable theta_r represents the combined server reference phase 797 and theta_c the control phase of the VFO. Each update received from 798 a server produces a signal V_d representing the instantaneous phase 799 difference theta_r - theta_c. The clock filter for each server 800 functions as a tapped delay line, with the output taken at the tap 801 selected by the clock filter algorithm. The selection, clustering 802 and combining algorithms combine the data from multiple filters to 803 produce the signal V_s. The loop filter, with impulse response F(t), 804 produces the signal V_c which controls the VFO frequency omega_c. 805 Thus, its phase theta_c follows: 807 theta_c = integral over t of (omega_c(t) dt) 809 which closes the loop. The V_c signal is generated by an adjustment 810 process which runs at intervals of one second in the NTP daemon or 811 one tick in the kernel. are set to 0, 813 The NTPv4 discipline includes both PLL and FLL capabilities. The 814 selection of which mode to use, FLL or PLL and in what combination, 815 is made on the basis of the poll exponent tau. In the NTPv4 design, 816 PLL mode is used at smaller values of tau, while FLL mode is used at 817 larger values. In between, a combination of PLL and FLL modes is 818 used. This improves the clock accuracy and stability, especially for 819 poll intervals larger than the Allan intercept. 820 x <------(Phase Correction)<--. 821 | 822 y_FLL | 823 .-(FLL Predict)<-------+<--V_s 824 | | 825 \|/ | 826 y <--(Sum) | 827 ^ | 828 | | 829 '-(PLL Predict)<-------' 830 y_PLL 832 Figure 6. FLL/PLL Prediction Functions 834 In PLL mode y is a time integral over all past values of V_s, so the 835 PLL frequency adjustment required is: 837 y_PLL = [ (V_s * mu) / ( (64 * T_c) ^ 2) ]. 839 where T_c is the time constant. In FLL mode, is an average of past 840 frequency changes, as computed from V_s and mu. The goal of the 841 algorithm is to reduce V_s to zero; so, to the extent this has been 842 successful in the past, previous values can be assumed zero and the 843 average becomes: 845 y_FLL = [ (V_s - x) / (8 * mu) ]. 847 where x is the residual phase error computed by the clock adjust 848 process. 850 Finally, in both PLL and FLL modes set the phase to x = V_s and 851 frequency y = [y + y_PLL + y_FLL]. 853 Once each second the adjustment process computes a phase increment z 854 = [ x / (16 * T_c) ] and new phase adjustment x = x - z. The phase 855 increment z is passed to the kernel time adjustment function. This 856 continues until the next update which recomputes x and y. 858 A key factor in the performance of the PLL/FLL hybrid algorithm are 859 the weight factors for the y_PLL and y_FLL adjustments, which depend 860 on the poll exponent tau which in turn determines the time constant 861 T_c = (2 ^ tau), in seconds. PLL contributions should dominate at 862 the lower values of tau, while FLL contributions should dominate at 863 the higher values. The clock discipline algorithm response times to 864 several PPM deviation examples is presented in . [3] 866 7.1. Poll Interval Control 868 The NTPv4 algorithm aims to set the averaging time somewhere near the 869 Allan intercept. A key to this strategy is the measured clock jitter 870 and oscillator wander statistics. The clock jitter is estimated from 871 phase differences psi_c = ( ^ (1/2) ), where the brackets 872 indicate an exponential average. The oscillator wander is estimated 873 from frequency differences psi_f = (T_c * ^ (1/2) ). As 874 the poll exponent tau increases, it is expected that psisubc will 875 decrease and psisubf will increase, depending on the relative 876 contributions of phase noise and frequency noise. 878 In the NTPv4 algorithm at each update a counter is incremented by one 879 if x is within the bound |x|< (4 * psi_c), where the constant 4 is 880 determined by experiment, and decremented by one otherwise. 882 In order to avoid needless hunting, a degree of hysteresis is built 883 into the scheme. If the counter reaches an upper limit 30, tau is 884 increased by one; if it reaches a lower limit -30, tau is reduced by 885 two. In either case the counter is reset to zero. Under normal 886 conditions tau increases in stages from a default lower limit of 6 887 (64 s) to a default upper limit of 10 (1024 seconds). However, if 888 the wander increases because the oscillator frequency is deviating 889 too fast, tau is quickly reduced. Once the oscillator wander 890 subsides, tau is slowly increased again. Under typical operating 891 conditions, tau hovers close to the maximum; but, on occasions of a 892 heat spike when the oscillator wanders more than about 1 PPM, it 893 quickly drops to lower values until the wander subsides. 895 7.2. State Machine 897 The clock discipline must operate over an extremely wide range of 898 network jitter and oscillator wander conditions without manual 899 intervention or prior configuration. As determined by past 900 experience and experiment, the data grooming algorithms work well to 901 sift good data from bad, especially under conditions of light to 902 moderate network and server loads. The PLL/FLL hybrid algorithm may 903 perform poorly and even become unstable under heavy network loading. 904 The state machine functions to bypass some discipline functions under 905 conditions of hardware or software failure, severe time or frequency 906 transients and especially when the poll interval is relatively large. 908 Under normal conditions the NTP discipline algorithm writes the 909 current frequency offset to a file at hourly intervals. Once the 910 file is written and the daemon is restarted after reboot, for 911 example, it initializes the frequency offset from the file, which 912 avoids the training time, possibly several hours, to determine the 913 intrinsic frequency offset when the daemon is started for the first 914 time. When toll charges accrue for every NTP message, as in a 915 telephone modem service, it is important to determine the presence of 916 a possibly large intrinsic frequency offset, especially if the 917 interval between telephone calls must be 15 minutes or more. For 918 instance, without the state machine it might take many calls spaced 919 at 15 minutes until the frequency offset is determined and the call 920 spacing can be increased. With the state machine it usually takes 921 only two calls to complete the process. 923 The clock state machine transition function is shown in Table 6. It 924 determines the action and next state when an update with specified 925 offset occurs in a given state shown in the first column. The second 926 column shows what happens if the offset is less than the step 927 threshold, the third when the step threshold is exceeded but not the 928 stepout threshold and the third when both thresholds are exceeded. 929 The state machine responds to the current state and event to cause 930 the action shown. 932 Table 6. Clock State Machine Transition Function 933 ===================================================================== 934 | State | abs(T) < STEP | abs(T) > STEP | Comments | 935 --------------------------------------------------------------------- 936 | NSET | > FREQ; adjust | > FREQ; step | no frequency | 937 | | time | time | file | 938 --------------------------------------------------------------------- 939 | FSET | > SYNC; adjust | > SYNC; step | frequency file | 940 | | time | time | | 941 --------------------------------------------------------------------- 942 | SPIK | > SYNC; adjust | if (<900 s)>SPIK | outlier detected | 943 | | freq, adjust time | else SYNC; step | | 944 | | | freq; step time | | 945 --------------------------------------------------------------------- 946 | FREQ | if (<900 s)> FREQ | if (<900 s)>FREQ | initial frequency | 947 | | else >SYNC; step | else >SYNC; step | | 948 | | freq, adjust time | freq, adjust time | | 949 --------------------------------------------------------------------- 950 | SYNC | >SYNC; adjust freq| if (<900 s)>SPIK | normal operation | 951 | | adjust time | else >SYNC; step | | 952 | | | freq; step time | | 953 --------------------------------------------------------------------- 955 The actions listed in the state diagram include adjust-frequency, 956 step-frequency, adjust-time and step-time actions. The normal action 957 in the SYNC state is to adjust both frequency and time. The step- 958 time action is to set the system clock, while the step-frequency 959 action is to calculate the frequency offset directly. This has to be 960 done carefully to avoid contamination of the frequency estimate by 961 the phase adjustment since the last update. 963 The machine can be initialized in two states, FSET if the frequency 964 file is present or NSET if it has not yet been created. If the file 965 is not present, this may be the first time the discipline has ever 966 been activated, so it may have to quickly determine the oscillator 967 intrinsic frequency offset. It is important to realize that a number 968 of NTP messages may be exchanged before the mitigation algorithms 969 determine a reliable time offset and call the clock discipline 970 algorithm. 972 When the first valid offset arrives in the NSET state, (1) the time 973 is stepped to that offset, if necessary, (2) the watchdog counter is 974 started and (3) the machine exits to the FREQ state. Subsequently, 975 updates will be ignored until the stepout threshold has been reached, 976 at which time the frequency is stepped, the time is stepped if 977 necessary, and the machine exits to SYNC state. When the first valid 978 offset arrives in the FSET state, the frequency has already been 979 initialized, so the machine does the same things as in the NSET 980 state, but exits to the SYNC state. 982 In the SYNC state the machine watches for outliers above the step 983 threshold. If one is found, the machine exits to SPIK state and 984 starts the watchdog timer. If another offset less than the step 985 threshold is found, the counter is stopped and the machine exits to 986 the SYNC state. If the watchdog timer reaches the stepout threshold, 987 the time and frequency are both stepped as required and the machine 988 exits to the SYNC state. 990 8. Security Considerations 992 There are no security considerations. 994 9. IANA Considerations 996 There are no IANA considerations. 998 10. Acknowledgements 1000 11. References 1002 11.1. Normative References 1003 11.2. Informative References 1005 [1] Mills, D., "Network Time Protocol (Version 3) Specification, 1006 Implementation", RFC 1305, March 1992. 1008 [2] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 for 1009 IPv4, IPv6 and OSI", RFC 2030, October 1996. 1011 [3] "D. Mills, "Computer Network Time Synchronization: The Network 1012 Time Protocol", DRAFT.", . 1014 [4] "Dolev, D., Halpern, J., Simons, B., and Strong R., "Dynamic 1015 Fault-Tolerant Clock Synchronization," JACM 42, January 1995, 1016 pp. 143-185.", . 1018 [5] "Berthaud, J.M., "Time Synchronization over Networks using 1019 Convex Closures," IEEE/ACM Transactions on Networking, April 1020 2000, pp. 265-277.", . 1022 [6] "Burbank, J., Martin, J., and Mills, D., Network Time Protocol 1023 Version 4 Protocol Specification, 1024 , October 2005, work in 1025 progress.", . 1027 Authors' Addresses 1029 William Kasch (editor) 1030 The Johns Hopkins University Applied Physics Lab 1031 11100 Johns Hopkins Road 1032 Laurel, Maryland 20723-6099 1033 United States 1035 Phone: +1 443 778 7463 1036 Email: william.kasch@jhuapl.edu 1038 Jack Burbank (editor) 1039 The Johns Hopkins University Applied Physics Laboratory 1040 11100 Johns Hopkins Road 1041 Laurel, Maryland 20723-6099 1042 United States 1044 Phone: +1 443 778 7127 1045 Email: jack.burbank@jhuapl.edu 1047 Dr. David L. Mills 1048 University of Delaware 1049 Newark, Delaware 19716 1050 United States 1052 Phone: +1 302 831 8247 1053 Email: mills@udel.edu 1055 Intellectual Property Statement 1057 The IETF takes no position regarding the validity or scope of any 1058 Intellectual Property Rights or other rights that might be claimed to 1059 pertain to the implementation or use of the technology described in 1060 this document or the extent to which any license under such rights 1061 might or might not be available; nor does it represent that it has 1062 made any independent effort to identify any such rights. Information 1063 on the procedures with respect to rights in RFC documents can be 1064 found in BCP 78 and BCP 79. 1066 Copies of IPR disclosures made to the IETF Secretariat and any 1067 assurances of licenses to be made available, or the result of an 1068 attempt made to obtain a general license or permission for the use of 1069 such proprietary rights by implementers or users of this 1070 specification can be obtained from the IETF on-line IPR repository at 1071 http://www.ietf.org/ipr. 1073 The IETF invites any interested party to bring to its attention any 1074 copyrights, patents or patent applications, or other proprietary 1075 rights that may cover technology that may be required to implement 1076 this standard. Please address the information to the IETF at 1077 ietf-ipr@ietf.org. 1079 Disclaimer of Validity 1081 This document and the information contained herein are provided on an 1082 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1083 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1084 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1085 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1086 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1087 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1089 Copyright Statement 1091 Copyright (C) The Internet Society (2005). This document is subject 1092 to the rights, licenses and restrictions contained in BCP 78, and 1093 except as set forth therein, the authors retain all their rights. 1095 Acknowledgment 1097 Funding for the RFC Editor function is currently provided by the 1098 Internet Society.