idnits 2.17.1 draft-ietf-ntp-ntpv4-proto-12.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 119 instances of weird spacing in the document. Is it really formatted ragged-right, rather than justified? == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. == There are 2 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == The 'Obsoletes: ' line in the draft header should list only the _numbers_ of the RFCs which will be obsoleted by this document (if approved); it should not include the word 'RFC' in the list. -- The draft header indicates that this document obsoletes RFC1305, but the abstract doesn't seem to directly say this. It does mention RFC1305 though, so this could be OK. -- The draft header indicates that this document obsoletes RFC4330, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 2825 has weird spacing: '... ipaddr srcad...' == Line 2826 has weird spacing: '... ipaddr dstad...' == Line 2827 has weird spacing: '... char ver...' == Line 2828 has weird spacing: '... char lea...' == Line 2829 has weird spacing: '... char mod...' == (114 more instances...) -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 8, 2009) is 5286 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. 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: 'NSTAGE' is mentioned on line 3702, but not defined == Missing Reference: 'NMAX' is mentioned on line 2969, but not defined -- Looks like a reference, but probably isn't: '7' on line 3324 -- Looks like a reference, but probably isn't: '5' on line 3324 -- Looks like a reference, but probably isn't: '0' on line 4295 ** Obsolete normative reference: RFC 793 (Obsoleted by RFC 9293) ** Downref: Normative reference to an Informational RFC: RFC 1321 == Outdated reference: A later version (-08) exists of draft-ietf-ntp-autokey-06 -- Obsolete informational reference (is this intentional?): RFC 1305 (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 4330 (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 4 errors (**), 0 flaws (~~), 13 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NTP WG J. Burbank 3 Internet-Draft W. Kasch 4 Obsoletes: RFC 4330, RFC 1305 JHU/APL 5 (if approved) J. Martin, Ed. 6 Intended status: Standards Track Daedelus 7 Expires: April 11, 2010 D. Mills 8 U. Delaware 9 October 8, 2009 11 Network Time Protocol Version 4 Protocol And Algorithms Specification 12 draft-ietf-ntp-ntpv4-proto-12 14 Status of this Memo 16 This Internet-Draft is submitted to IETF in full conformance with the 17 provisions of BCP 78 and BCP 79. This document may contain material 18 from IETF Documents or IETF Contributions published or made publicly 19 available before November 10, 2008. The person(s) controlling the 20 copyright in some of this material may not have granted the IETF 21 Trust the right to allow modifications of such material outside the 22 IETF Standards Process. Without obtaining an adequate license from 23 the person(s) controlling the copyright in such materials, this 24 document may not be modified outside the IETF Standards Process, and 25 derivative works of it may not be created outside the IETF Standards 26 Process, except to format it for publication as an RFC or to 27 translate it into languages other than English. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF), its areas, and its working groups. Note that 31 other groups may also distribute working documents as Internet- 32 Drafts. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 The list of current Internet-Drafts can be accessed at 40 http://www.ietf.org/ietf/1id-abstracts.txt. 42 The list of Internet-Draft Shadow Directories can be accessed at 43 http://www.ietf.org/shadow.html. 45 This Internet-Draft will expire on April 11, 2010. 47 Copyright Notice 48 Copyright (c) 2009 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents in effect on the date of 53 publication of this document (http://trustee.ietf.org/license-info). 54 Please review these documents carefully, as they describe your rights 55 and restrictions with respect to this document. 57 Abstract 59 The Network Time Protocol (NTP) is widely used to synchronize 60 computer clocks in the Internet. This document describes NTP Version 61 4 (NTPv4), which is backwards compatible with NTP Version 3 (NTPv3) 62 described in RFC 1305, as well as previous versions of the protocol. 63 NTPv4 includes a modified protocol header to accommodate the Internet 64 Protocol Version 6 address family. NTPv4 includes fundamental 65 improvements in the mitigation and discipline algorithms which extend 66 the potential accuracy to the tens of microseconds with modern 67 workstations and fast LANs. It includes a dynamic server discovery 68 scheme, so that in many cases specific server configuration is not 69 required. It corrects certain errors in the NTPv3 design and 70 implementation and includes an optional extension mechanism. 72 Table of Contents 74 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5 75 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 6 76 2. Modes of Operation . . . . . . . . . . . . . . . . . . . . . 6 77 3. Protocol Modes . . . . . . . . . . . . . . . . . . . . . . . 7 78 3.1. Dynamic Server Discovery . . . . . . . . . . . . . . . . 8 79 4. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 9 80 5. Implementation Model . . . . . . . . . . . . . . . . . . . . 11 81 6. Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 13 82 7. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 17 83 7.1. Structure Conventions . . . . . . . . . . . . . . . . . . 17 84 7.2. Global Parameters . . . . . . . . . . . . . . . . . . . . 17 85 7.3. Packet Header Variables . . . . . . . . . . . . . . . . . 18 86 7.4. The Kiss-o'-Death Packet . . . . . . . . . . . . . . . . 25 87 7.5. NTP Extension Field Format . . . . . . . . . . . . . . . 26 88 8. On Wire Protocol . . . . . . . . . . . . . . . . . . . . . . 27 89 9. Peer Process . . . . . . . . . . . . . . . . . . . . . . . . 31 90 9.1. Peer Process Variables . . . . . . . . . . . . . . . . . 32 91 9.2. Peer Process Operations . . . . . . . . . . . . . . . . . 34 92 10. Clock Filter Algorithm . . . . . . . . . . . . . . . . . . . 38 93 11. System Process . . . . . . . . . . . . . . . . . . . . . . . 40 94 11.1. System Process Variables . . . . . . . . . . . . . . . . 41 95 11.2. System Process Operations . . . . . . . . . . . . . . . . 42 96 11.2.1. Selection Algorithm . . . . . . . . . . . . . . . . 44 97 11.2.2. Cluster Algorithm . . . . . . . . . . . . . . . . . 45 98 11.2.3. Combine Algorithm . . . . . . . . . . . . . . . . . 46 99 11.3. Clock Discipline Algorithm . . . . . . . . . . . . . . . 48 100 12. Clock Adjust Process . . . . . . . . . . . . . . . . . . . . 52 101 13. Poll Process . . . . . . . . . . . . . . . . . . . . . . . . 52 102 13.1. Poll Process Variables . . . . . . . . . . . . . . . . . 52 103 13.2. Poll Process Operations . . . . . . . . . . . . . . . . . 53 104 14. Simple Network Time Protocol (SNTP) . . . . . . . . . . . . . 55 105 15. Security Considerations . . . . . . . . . . . . . . . . . . . 56 106 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 59 107 17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 60 108 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 60 109 18.1. Normative References . . . . . . . . . . . . . . . . . . 60 110 18.2. Informative References . . . . . . . . . . . . . . . . . 60 111 Appendix A. Code Skeleton . . . . . . . . . . . . . . . . . . . 61 112 A.1. Global Definitions . . . . . . . . . . . . . . . . . . . 62 113 A.1.1. Definitions, Constants, Parameters . . . . . . . . . 62 114 A.1.2. Packet Data Structures . . . . . . . . . . . . . . . 65 115 A.1.3. Association Data Structures . . . . . . . . . . . . 66 116 A.1.4. System Data Structures . . . . . . . . . . . . . . . 68 117 A.1.5. Local Clock Data Structures . . . . . . . . . . . . 69 118 A.1.6. Function Prototypes . . . . . . . . . . . . . . . . 69 119 A.2. Main Program and Utility Routines . . . . . . . . . . . . 70 120 A.3. Kernel Input/Output Interface . . . . . . . . . . . . . . 73 121 A.4. Kernel System Clock Interface . . . . . . . . . . . . . . 73 122 A.5. Peer Process . . . . . . . . . . . . . . . . . . . . . . 75 123 A.5.1. receive() . . . . . . . . . . . . . . . . . . . . . 76 124 A.5.2. clock_filter() . . . . . . . . . . . . . . . . . . . 83 125 A.5.3. fast_xmit() . . . . . . . . . . . . . . . . . . . . 87 126 A.5.4. access() . . . . . . . . . . . . . . . . . . . . . . 88 127 A.5.5. System Process . . . . . . . . . . . . . . . . . . . 88 128 A.5.6. Clock Adjust Process . . . . . . . . . . . . . . . . 103 129 A.5.7. Poll Process . . . . . . . . . . . . . . . . . . . . 104 130 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 111 132 1. Introduction 134 This document defines the Network Time Protocol Version 4 (NTPv4), 135 which is widely used to synchronize system clocks among a set of 136 distributed time servers and clients. It describes the core 137 architecture, protocol, state machines, data structures and 138 algorithms. NTPv4 introduces new functionality to NTPv3, as 139 described in [RFC1305], and functionality expanded from SNTPv4 as 140 described in [RFC4330] (SNTPv4 is a subset of NTPv4). This document 141 obsoletes [RFC1305], and [RFC4330]. While certain minor changes have 142 been made in some protocol header fields, these do not affect the 143 interoperability between NTPv4 and previous versions of NTP and SNTP. 145 The NTP subnet model includes a number of widely accessible primary 146 time servers synchronized by wire or radio to national standards. 147 The purpose of the NTP protocol is to convey timekeeping information 148 from these primary servers to secondary time servers and clients via 149 both private networks and the public Internet. Precisely tuned 150 algorithms mitigate errors that may result from network disruptions, 151 server failures and possible hostile actions. Servers and clients 152 are configured such that values flow towards clients from the primary 153 servers at the root via branching secondary servers. 155 The NTPv4 design overcomes significant shortcomings in the NTPv3 156 design, corrects certain bugs and incorporates new features. In 157 particular, expanded NTP timestamp definitions encourage the use of 158 the floating double data type throughout the implementation. As a 159 result, the time resolution is better than one nanosecond and 160 frequency resolution is less than one nanosecond per second. 161 Additional improvements include a new clock discipline algorithm 162 which is more responsive to system clock hardware frequency 163 fluctuations. Typical primary servers using modern machines are 164 precise within a few tens of microseconds. Typical secondary servers 165 and clients on fast LANs are within a few hundred microseconds with 166 poll intervals up to 1024 seconds, which was the maximum with NTPv3. 167 With NTPv4, servers and clients are precise within a few tens of 168 milliseconds with poll intervals up to 36 hours. 170 The main body of this document describes the core protocol and data 171 structures necessary to interoperate between conforming 172 implementations. Appendix A contains a full featured example in the 173 form of a skeleton program, including data structures and code 174 segments for the core algorithms as well as the mitigation algorithms 175 used to enhance reliability and accuracy. While the skeleton program 176 and other descriptions in this document apply to a particular 177 implementation, they are not intended as the only way the required 178 functions can be implemented. While the NTPv3 symmetric key 179 authentication scheme described in this document has been carried 180 over from NTPv3, the Autokey public key authentication scheme new to 181 NTPv4 is described in [I-D.ietf-ntp-autokey]. 183 The NTP protocol includes modes of operation described in Section 2 184 using data types described in Section 6 and data structures described 185 in Section 7. The implementation model described in Section 5 is 186 based on a threaded, multi-process architecture, although other 187 architectures could be used as well. The on-wire protocol described 188 in Section 8 is based on a returnable-time design which depends only 189 on measured clock offsets, but does not require reliable message 190 delivery. Reliable message delivery such as TCP[RFC0793] can 191 actually make the delivered NTP packet less reliable since retries 192 would increase the delay value and other errors. The synchronization 193 subnet is a self-organizing, hierarchical, master-slave network with 194 synchronization paths determined by a shortest-path spanning tree and 195 defined metric. While multiple masters (primary servers) may exist, 196 there is no requirement for an election protocol. 198 This document includes material from [ref9], which contains flow 199 charts and equations unsuited for RFC format. There is much 200 additional information in [ref7], including an extensive technical 201 analysis and performance assessment of the protocol and algorithms in 202 this document. The reference implementation is available at 203 www.ntp.org. 205 The remainder of this document contains numerous variables and 206 mathematical expressions. Some variables take the form of Greek 207 characters, which are spelled out by their full case-sensitive name. 208 For example DELTA refers to the uppercase Greek character, while 209 delta refers to the lowercase character. Furthermore, subscripts are 210 denoted with '_', for example theta_i refers to the lowercase Greek 211 character theta with subscript i, or phonetically theta sub i. In 212 this document all time values are in seconds (s), and all frequencies 213 will be specified as fractional frequency offsets (FFO) (pure 214 number). It is often convenient to express these FFOs in parts per 215 million (ppm). 217 1.1. Requirements Notation 219 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 220 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 221 document are to be interpreted as described in [RFC2119]. 223 2. Modes of Operation 225 An NTP implementation operates as a primary server, secondary server 226 or client. A primary server is synchronized to a reference clock 227 directly traceable to UTC (eg, GPS, Galileo, etc). A client 228 synchronizes to one or more upstream servers, but does not provide 229 synchronization to dependent clients. A secondary server has one or 230 more upstream servers and one or more downstream servers or clients. 231 All servers and clients who are fully NTPv4 compliant MUST implement 232 the entire suite of algorithms described in this document. In order 233 to maintain stability in large NTP subnets, secondary servers SHOULD 234 be fully NTPv4 compliant. Alternative algorithms MAY be used, but 235 their output MUST be identical to the algorithms described in this 236 specification. 238 3. Protocol Modes 240 There are three NTP protocol variants, symmetric, client/server and 241 broadcast. Each is associated with an association mode (a 242 description of the relationship between two NTP speakers) as shown in 243 Figure 1. In addition, persistent associations are mobilized upon 244 startup and are never demobilized. Ephemeral associations are 245 mobilized upon the arrival of a packet and are demobilized upon error 246 or timeout. 248 +-------------------+--------------+-------------+ 249 | Association Mode | Assoc. Mode | Packet Mode | 250 +-------------------+--------------+-------------+ 251 | Symmetric Active | 1 | 1 or 2 | 252 | Symmetric Passive | 2 | 1 | 253 | Client | 3 | 4 | 254 | Server | 4 | 3 | 255 | Broadcast Server | 5 | 5 | 256 | Broadcast Client | 6 | N/A | 257 +-------------------+--------------+-------------+ 259 Figure 1: Association and Packet Modes 261 In the client/server variant a persistent client sends packet mode 4 262 packets to a server, which returns packet mode 3 packets. Servers 263 provide synchronization to one or more clients, but do not accept 264 synchronization from them. A server can also be a reference clock 265 driver which obtains time directly from a standard source such as a 266 GPS receiver or telephone modem service. In this variant, clients 267 pull synchronization from servers. 269 In the symmetric variant a peer operates as both a server and client 270 using either a symmetric active or symmetric passive association. A 271 persistent symmetric active association sends symmetric active (mode 272 1) packets to a symmetric active peer association. Alternatively, an 273 ephemeral symmetric passive association can be mobilized upon arrival 274 of a symmetric active packet with no matching association. That 275 association sends symmetric passive (mode 2) packets and persists 276 until error or timeout. Peers both push and pull synchronization to 277 and from each other. For the purposes of this document, a peer 278 operates like a client, so references to client imply peer as well. 280 In the broadcast variant a persistent broadcast server association 281 sends periodic broadcast server (mode 5) packets which can be 282 received by multiple clients. Upon reception of a broadcast server 283 packet without a matching association, an ephemeral broadcast client 284 (mode 6) association is mobilized and persists until error or 285 timeout. It is useful to provide an initial volley where the client 286 operating in client mode exchanges several packets with the server, 287 so as to calibrate the propagation delay and to run the Autokey 288 security protocol, after which the client reverts to broadcast client 289 mode. A broadcast server pushes synchronization to clients and other 290 servers. 292 Following loosely the conventions established by the telephone 293 industry, the level of each server in the hierarchy is defined by a 294 stratum number. Primary servers are assigned stratum one; secondary 295 servers at each lower level are assigned stratum numbers one greater 296 than the preceding level. As the stratum number increases, its 297 accuracy degrades depending on the particular network path and system 298 clock stability. Mean errors, measured by synchronization distances, 299 increase approximately in proportion to stratum numbers and measured 300 roundtrip delay. 302 As a standard practice, timing network topology should be organized 303 to avoid timing loops and minimize the synchronization distance. In 304 NTP the subnet topology is determined using a variant of the Bellman- 305 Ford distributed routing algorithm, which computes the shortest-path 306 spanning tree rooted on the primary servers. As a result of this 307 design, the algorithm automatically reorganizes the subnet, so as to 308 produce the most accurate and reliable time, even when there are 309 failures in the timing network. 311 3.1. Dynamic Server Discovery 313 There are two special associations, manycast client and manycast 314 server, which provide a dynamic server discovery function. There are 315 two types of manycast client associations, persistent and ephemeral. 316 The persistent manycast client sends client (mode 3) packets to a 317 designated IPv4 or IPv6 broadcast or multicast group address. 318 Designated manycast servers within range of the time-to-live (TTL) 319 field in the packet header listen for packets with that address. If 320 a server is suitable for synchronization, it returns an ordinary 321 server (mode 4) packet using the client's unicast address. Upon 322 receiving this packet, the client mobilizes an ephemeral client (mode 323 3) association. The ephemeral client association persists until 324 error or timeout. 326 A manycast client continues sending packets to search for a minimum 327 number of associations. It starts with a TTL equal to one and 328 continuously adding one to it until the minimum number of 329 associations is made or when the TTL reaches a maximum value. If the 330 TTL reaches its maximum value and yet not enough associations are 331 mobilized, the client stops transmission for a time-out period to 332 clear all associations, and then repeats the search cycle. If a 333 minimum number of associations has been mobilized, then the client 334 starts transmitting one packet per time-out period to maintain the 335 associations. Field constraints limit the minimum value to 1 and the 336 maximum to 255. These limits may be tuned for individual application 337 needs. 339 The ephemeral associations compete among themselves. As new 340 ephemeral associations are mobilized, the client runs the mitigation 341 algorithms described in Section 10 and Section 11.2 for the best 342 candidates out of the population, the remaining ephemeral 343 associations are timed out and demobilized. In this way the 344 population includes only the best candidates that have most recently 345 responded with an NTP packet to discipline the system clock. 347 4. Definitions 349 A number of technical terms are defined in this section. A timescale 350 is a frame of reference where time is expressed as the value of a 351 monotonically increasing binary counter with an indefinite number of 352 bits. It counts in seconds and fractions of a second, when a decimal 353 point is employed. The Coordinated Universal Time (UTC) timescale is 354 defined by ITU-R TF.460[ITU-R_TF.460]. Under the auspices of the 355 Metre Convention of 1865, in 1975 the CGPM[CGPM] strongly endorsed 356 the use of UTC as the basis for civil time. 358 The Coordinated Universal Time (UTC) timescale represents mean solar 359 time as disseminated by national standards laboratories. The system 360 time is represented by the system clock maintained by the hardware 361 and operating system. The goal of the NTP algorithms is to minimize 362 both the time difference and frequency difference between UTC and the 363 system clock. When these differences have been reduced below nominal 364 tolerances, the system clock is said to be synchronized to UTC. 366 The date of an event is the UTC time at which the event takes place. 367 Dates are ephemeral values designated with upper case T. Running time 368 is another timescale that is coincident to the synchronization 369 function of the NTP program. 371 A timestamp T(t) represents either the UTC date or time offset from 372 UTC at running time t. Which meaning is intended should be clear 373 from the context. Let T(t) be the time offset, R(t) the frequency 374 offset, D(t) the aging rate (first derivative of R(t) with respect to 375 t). Then, if T(t_0) is the UTC time offset determined at t = t_0, 376 the UTC time offset at time t is 378 T(t) = T(t_0) + R(t_0)(t-t_0) + 1/2 * D(t_0)(t-t_0)^2 + e, 380 where e is a stochastic error term discussed later in this document. 381 While the D(t) term is important when characterizing precision 382 oscillators, it is ordinarily neglected for computer oscillators. In 383 this document all time values are in seconds (s) and all frequency 384 values are in seconds-per-second (s/s). It is sometimes convenient 385 to express frequency offsets in parts-per-million (PPM), where 1 PPM 386 is equal to 10^(-6) seconds/second. 388 It is important in computer timekeeping applications to assess the 389 performance of the timekeeping function. The NTP performance model 390 includes four statistics which are updated each time a client makes a 391 measurement with a server. The offset (theta) represents the 392 maximum-likelihood time offset of the server clock relative to the 393 system clock. The delay (delta) represents the round trip delay 394 between the client and server. The dispersion (epsilon) represents 395 the maximum error inherent in the measurement. It increases at a 396 rate equal to the maximum disciplined system clock frequency 397 tolerance (PHI), typically 15 PPM. The jitter (psi) is defined as 398 the root-mean-square (RMS) average of the most recent offset 399 differences, represents the nominal error in estimating the offset. 401 While the theta, delta, epsilon, and psi statistics represent 402 measurements of the system clock relative to each server clock 403 separately, the NTP protocol includes mechanisms to combine the 404 statistics of several servers to more accurately discipline and 405 calibrate the system clock. The system offset (THETA) represents the 406 maximum-likelihood offset estimate for the server population. The 407 system jitter (PSI) represents the nominal error in estimating the 408 system offset. The delta and epsilon statistics are accumulated at 409 each stratum level from the reference clock to produce the root delay 410 (DELTA) and root dispersion (EPSILON) statistics. The 411 synchronization distance (LAMBDA) equal to EPSILON + DELTA / 2 412 represents the maximum error due all causes. The detailed 413 formulations of these statistics are given in Section 11.2. They are 414 available to the dependent applications in order to assess the 415 performance of the synchronization function. 417 5. Implementation Model 419 Figure 2 shows the architecture of a typical, multi-threaded 420 implementation. It includes two processes dedicated to each server, 421 a peer process to receive messages from the server or reference clock 422 and a poll process to transmit messages to the server or reference 423 clock. 425 ..................................................................... 426 . Remote . Peer/Poll . System . Clock . 427 . Servers . Processes . Process .Discipline. 428 . . . . Process . 429 .+--------+. +-----------+. +------------+ . . 430 .| |->| |. | | . . 431 .|Server 1| |Peer/Poll 1|->| | . . 432 .| |<-| |. | | . . 433 .+--------+. +-----------+. | | . . 434 . . ^ . | | . . 435 . . | . | | . . 436 .+--------+. +-----------+. | | +-----------+. . 437 .| |->| |. | Selection |->| |. +------+ . 438 .|Server 2| |Peer/Poll 2|->| and | | Combine |->| Loop | . 439 .| |<-| |. | Cluster | | Algorithm |. |Filter| . 440 .+--------+. +-----------+. | Algorithms |->| |. +------+ . 441 . . ^ . | | +-----------+. | . 442 . . | . | | . | . 443 .+--------+. +-----------+. | | . | . 444 .| |->| |. | | . | . 445 .|Server 3| |Peer/Poll 3|->| | . | . 446 .| |<-| |. | | . | . 447 .+--------+. +-----------+. +------------+ . | . 448 ....................^.........................................|...... 449 | . V . 450 | . +-----+ . 451 +--------------------------------------| VFO | . 452 . +-----+ . 453 . Clock . 454 . Adjust . 455 . Process . 456 ............ 458 Figure 2: Implementation Model 460 These processes operate on a common data structure, called an 461 association, which contains the statistics described above along with 462 various other data described in Section 9. A client sends packets to 463 one or more servers and then processes returned packets when they are 464 received. The server interchanges source and destination addresses 465 and ports, overwrites certain fields in the packet and returns it 466 immediately (in the client/server mode) or at some time later (in the 467 symmetric modes). As each NTP message is received, the offset theta 468 between the peer clock and the system clock is computed along with 469 the associated statistics delta, epsilon and psi. 471 The system process includes the selection, cluster and combine 472 algorithms that mitigate among the various servers and reference 473 clocks to determine the most accurate and reliable candidates to 474 synchronize the system clock. The selection algorithm uses Byzantine 475 fault detection principles to discard the presumably incorrect 476 candidates called "falsetickers" from the incident population, 477 leaving only good candidates called "truechimers". A truechimer is a 478 clock that maintains timekeeping accuracy to a previously published 479 and trusted standard, while a falseticker is a clock that shows 480 misleading or inconsistent time. The cluster algorithm uses 481 statistical principles to find the most accurate set of truechimers. 482 The combine algorithm computes the final clock offset by 483 statistically averaging the surviving truechimers. 485 The clock discipline process is a system process that controls the 486 time and frequency of the system clock, here represented as a 487 variable frequency oscillator (VFO). Timestamps struck from the VFO 488 close the feedback loop which maintains the system clock time. 489 Associated with the clock discipline process is the clock adjust 490 process, which runs once each second to inject a computed time offset 491 and maintain constant frequency. The RMS average of past time offset 492 differences represents the nominal error or system clock jitter. The 493 RMS average of past frequency offset differences represents the 494 oscillator frequency stability or frequency wander. These terms are 495 given precise interpretation in Section 11.3. 497 A client sends messages to each server with a poll interval of 2^tau 498 seconds, as determined by the poll exponent tau. In NTPv4, tau 499 ranges from 4 (16 s) through 17 (36 h). The value of tau is 500 determined by the clock discipline algorithm to match the loop time 501 constant T_c = 2^tau. In client/server mode the server responds 502 immediately; however, in symmetric modes each of two peers manages 503 tau as a function of current system offset and system jitter, so may 504 not agree with the same value. It is important that the dynamic 505 behavior of the clock discipline algorithm be carefully controlled in 506 order to maintain stability in the NTP subnet at large. This 507 requires that the peers agree on a common tau equal to the minimum 508 poll exponent of both peers. The NTP protocol includes provisions to 509 properly negotiate this value. 511 The implementation model includes some means to set and adjust the 512 system clock. The operating system is assumed to provide two 513 functions, one to set the time directly, for example the Unix 514 settimeofday() function, and another to adjust the time in small 515 increments advancing or retarding the time by a designated amount, 516 for example the Unix adjtime() function. In this and following 517 references, parentheses following a name indicate reference to a 518 function rather than a simple variable. In the intended design the 519 clock discipline process uses the adjtime() function if the 520 adjustment is less than a designated threshold, and the 521 settimeofday() function if above the threshold. The manner in which 522 this is done and the value of the threshold as described in 523 Section 10. 525 6. Data Types 527 All NTP time values are represented in twos-complement format, with 528 bits numbered in big-endian (as described in Appendix A of [RFC0791]) 529 fashion from zero starting at the left, or high-order, position. 530 There are three NTP time formats, a 128-bit date format, a 64-bit 531 timestamp format and a 32-bit short format, as shown in Figure 3. 532 The 128-bit date format is used where sufficient storage and word 533 size are available. It includes a 64-bit signed seconds field 534 spanning 584 billion years and a 64-bit fraction field resolving .05 535 attosecond (i.e., 0.5e-18). For convenience in mapping between 536 formats, the seconds field is divided into a 32-bit Era Number field 537 and a 32-bit Era Offset field. Eras cannot be produced by NTP 538 directly, nor is there need to do so. When necessary, they can be 539 derived from external means, such as the filesystem or dedicated 540 hardware. 542 0 1 2 3 543 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 545 | Seconds | Fraction | 546 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 548 NTP Short Format 550 0 1 2 3 551 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | Seconds | 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 | Fraction | 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 558 NTP Timestamp Format 560 0 1 2 3 561 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Era Number | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Era Offset | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | | 568 | Fraction | 569 | | 570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 572 NTP Date Format 574 Figure 3: NTP Time Formats 576 The 64-bit timestamp format is used in packet headers and other 577 places with limited word size. It includes a 32-bit unsigned seconds 578 field spanning 136 years and a 32-bit fraction field resolving 232 579 picoseconds. The 32-bit short format is used in delay and dispersion 580 header fields where the full resolution and range of the other 581 formats are not justified. It includes a 16-bit unsigned seconds 582 field and a 16-bit fraction field. 584 In the date and timestamp formats the prime epoch, or base date of 585 era 0, is 0 h 1 January 1900 UTC, when all bits are zero. It should 586 be noted that strictly speaking, UTC did not exist prior to 1 January 587 1972, but it is convenient to assume it has existed for all eternity, 588 even if all knowledge of historic leap seconds has been lost. Dates 589 are relative to the prime epoch; values greater than zero represent 590 times after that date; values less than zero represent times before 591 it. Note that the Era Offset field of the date format and the 592 Seconds field of the timestamp format have the same interpretation. 594 Timestamps are unsigned values and operations on them produce a 595 result in the same or adjacent eras. Era 0 includes dates from the 596 prime epoch to some time in 2036, when the timestamp field wraps 597 around and the base date for era 1 is established. In either format 598 a value of zero is a special case representing unknown or 599 unsynchronized time. Figure 4 shows a number of historic NTP dates 600 together with their corresponding Modified Julian Day (MJD), NTP era 601 and NTP timestamp. 603 +-------------+------------+-----+---------------+------------------+ 604 | Date | MJD | NTP | NTP Timestamp | Epoch | 605 | | | Era | Era Offset | | 606 +-------------+------------+-----+---------------+------------------+ 607 | 1 Jan -4712 | -2,400,001 | -49 | 1,795,583,104 | 1st day Julian | 608 | 1 Jan -1 | -679,306 | -14 | 139,775,744 | 2 BCE | 609 | 1 Jan 0 | -678,491 | -14 | 171,311,744 | 1 BCE | 610 | 1 Jan 1 | -678,575 | -14 | 202,939,144 | 1 CE | 611 | 4 Oct 1582 | -100,851 | -3 | 2,873,647,488 | Last day Julian | 612 | 15 Oct 1582 | -100,840 | -3 | 2,874,597,888 | First day | 613 | | | | | Gregorian | 614 | 31 Dec 1899 | 15019 | -1 | 4,294,880,896 | Last day NTP Era | 615 | | | | | -1 | 616 | 1 Jan 1900 | 15020 | 0 | 0 | First day NTP | 617 | | | | | Era 0 | 618 | 1 Jan 1970 | 40,587 | 0 | 2,208,988,800 | First day UNIX | 619 | 1 Jan 1972 | 41,317 | 0 | 2,272,060,800 | First day UTC | 620 | 31 Dec 1999 | 51,543 | 0 | 3,155,587,200 | Last day 20th | 621 | | | | | Century | 622 | 8 Feb 2036 | 64,731 | 1 | 63,104 | First day NTP | 623 | | | | | Era 1 | 624 +-------------+------------+-----+---------------+------------------+ 626 Figure 4: Interesting Historic NTP Dates 628 Let p be the number of significant bits in the second fraction. The 629 clock resolution is defined 2^(-p), in seconds. In order to minimize 630 bias and help make timestamps unpredictable to an intruder, the non- 631 significant bits should be set to an unbiased random bit string. The 632 clock precision is defined as the running time to read the system 633 clock, in seconds. Note that the precision defined in this way can 634 be larger or smaller than the resolution. The term rho, representing 635 the precision used in the protocol, is the larger of the two. 637 The only arithmetic operation permitted on dates and timestamps is 638 twos-complement subtraction, yielding a 127-bit or 63-bit signed 639 result. It is critical that the first-order differences between two 640 dates preserve the full 128-bit precision and the first-order 641 differences between two timestamps preserve the full 64-bit 642 precision. However, the differences are ordinarily small compared to 643 the seconds span, so they can be converted to floating double format 644 for further processing and without compromising the precision. 646 It is important to note that twos-complement arithmetic does not 647 distinguish between signed and unsigned values (although comparisons 648 can take sign into account); only the conditional branch instructions 649 do. Thus, although the distinction is made between signed dates and 650 unsigned timestamps, they are processed the same way. A perceived 651 hazard with 64-bit timestamp calculations spanning an era, such as 652 possible in 2036, might result in over-run. In point of fact, if the 653 client is set within 68 years of the server before the protocol is 654 started, correct values are obtained even if the client and server 655 are in adjacent eras. 657 Some time values are represented in exponent format, including the 658 precision, time constant and poll interval. These are in 8-bit 659 signed integer format in log2 (log base 2) seconds. The only 660 arithmetic operations permitted on them are increment and decrement. 661 For the purpose of this document and to simplify the presentation, a 662 reference to one of these variables by name means the exponentiated 663 value, e.g., the poll interval is 1024 s, while reference by name and 664 exponent means the actual value, e.g., the poll exponent is 10. 666 To convert system time in any format to NTP date and timestamp 667 formats requires that the number of seconds s from the prime epoch to 668 the system time be determined. To determine the integer era and 669 timestamp given s, 671 era = s / 2^(32) and timestamp = s - era * 2^(32), 673 which works for positive and negative dates. To determine s given 674 the era and timestamp, 676 s = era * 2^(32) + timestamp. 678 Converting between NTP and system time can be a little messy, and 679 beyond the scope of this document. Note that the number of days in 680 era 0 is one more than the number of days in most other eras and this 681 won't happen again until the year 2400 in era 3. 683 In the description of state variables to follow, explicit reference 684 to integer type implies a 32-bit unsigned integer. This simplifies 685 bounds checks, since only the upper limit needs to be defined. 687 Without explicit reference, the default type is 64-bit floating 688 double. Exceptions will be noted as necessary. 690 7. Data Structures 692 The NTP protocol state machines are defined in the following 693 sections. State variables are separated into classes according to 694 their function in packet headers, peer and poll processes, the system 695 process and the clock discipline process. Packet variables represent 696 the NTP header values in transmitted and received packets. Peer and 697 poll variables represent the contents of the association for each 698 server separately. System variables represent the state of the 699 server as seen by its dependent clients. Clock discipline variables 700 represent the internal workings of the clock discipline algorithm. 701 An example is described in Appendix A. 703 7.1. Structure Conventions 705 In order to distinguish between different variables of the same name 706 but used in different processes, the naming convention summarized in 707 Figure 5 is adopted. A receive packet variable v is a member of the 708 packet structure r with fully qualified name r.v. In a similar 709 manner x.v is a transmit packet variable, p.v is a peer variable, s.v 710 is a system variable and c.v is a clock discipline variable. There 711 is a set of peer variables for each association; there is only one 712 set of system and clock variables. 714 +------+---------------------------------+ 715 | Name | Description | 716 +------+---------------------------------+ 717 | r. | receive packet header variable | 718 | x. | transmit packet header variable | 719 | p. | peer/poll variable | 720 | s. | system variable | 721 | c. | clock discipline variable | 722 +------+---------------------------------+ 724 Figure 5: Prefix Conventions 726 7.2. Global Parameters 728 In addition to the variable classes a number of global parameters are 729 defined in this document, including those shown with values in 730 Figure 6. 732 +-----------+-------+----------------------------------+ 733 | Name | Value | Description | 734 +-----------+-------+----------------------------------+ 735 | PORT | 123 | NTP port number | 736 | VERSION | 4 | NTP version number | 737 | TOLERANCE | 15e-6 | frequency tolerance PHI (s/s) | 738 | MINPOLL | 4 | minimum poll exponent (16 s) | 739 | MAXPOLL | 17 | maximum poll exponent (36 h) | 740 | MAXDISP | 16 | maximum dispersion (16 s) | 741 | MINDISP | .005 | minimum dispersion increment (s) | 742 | MAXDIST | 1 | distance threshold (1 s) | 743 | MAXSTRAT | 16 | maximum stratum number | 744 +-----------+-------+----------------------------------+ 746 Figure 6: Global Parameters 748 While these are the only global parameters needed for 749 interoperability, a larger collection is necessary in any 750 implementation. Appendix A.1.1 contains those used by the skeleton 751 for the mitigation algorithms, clock discipline algorithm and related 752 implementation-dependent functions. Some of these parameter values 753 are cast in stone, like the NTP port number assigned by the IANA and 754 the version number assigned NTPv4 itself. Others like the frequency 755 tolerance (also called PHI), involve an assumption about the worst 756 case behavior of a system clock once synchronized and then allowed to 757 drift when its sources have become unreachable. The minimum and 758 maximum parameters define the limits of state variables as described 759 in later sections of this document. 761 While shown with fixed values in this document, some implementations 762 may make them variables adjustable by configuration commands. For 763 instance, the reference implementation computes the value of 764 PRECISION as log2 of the minimum time in several iterations to read 765 the system clock. 767 7.3. Packet Header Variables 769 The most important state variables from an external point of view are 770 the packet header variables described in Figure 7 and below. The NTP 771 packet header consists of an integral number of 32-bit (4 octet) 772 words in network byte order. The packet format consists of three 773 components, the header itself, one or more optional extension fields 774 and an optional message authentication code (MAC). The header 775 component is identical to the NTPv3 header and previous versions. 776 The optional extension fields are used by the Autokey public key 777 cryptographic algorithms described in [I-D.ietf-ntp-autokey]. The 778 optional MAC is used by both Autokey and the symmetric key 779 cryptographic algorithm described in this RFC. 781 +-----------+------------+-----------------------+ 782 | Name | Formula | Description | 783 +-----------+------------+-----------------------+ 784 | leap | leap | leap indicator (LI) | 785 | version | version | version number (VN) | 786 | mode | mode | mode | 787 | stratum | stratum | stratum | 788 | poll | poll | poll exponent | 789 | precision | rho | precision exponent | 790 | rootdelay | delta_r | root delay | 791 | rootdisp | epsilon_r | root dispersion | 792 | refid | refid | reference ID | 793 | reftime | reftime | reference timestamp | 794 | org | T1 | origin timestamp | 795 | rec | T2 | receive timestamp | 796 | xmt | T3 | transmit timestamp | 797 | dst | T4 | destination timestamp | 798 | keyid | keyid | key ID | 799 | dgst | dgst | message digest | 800 +-----------+------------+-----------------------+ 802 Figure 7: Packet Header Variables 804 The NTP packet is a UDP datagram[RFC0768]. Some fields use multiple 805 words and others are packed in smaller fields within a word. The NTP 806 packet header shown in Figure 8 has 12 words followed by optional 807 extension fields and finally an optional message authentication code 808 (MAC) consisting of the key identifier field and message digest 809 field. 811 0 1 2 3 812 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 813 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 814 |LI | VN |Mode | Stratum | Poll | Precision | 815 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 816 | Root Delay | 817 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 818 | Root Dispersion | 819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 820 | Reference ID | 821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 822 | | 823 + Reference Timestamp (64) + 824 | | 825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 826 | | 827 + Origin Timestamp (64) + 828 | | 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | | 831 + Receive Timestamp (64) + 832 | | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 | | 835 + Transmit Timestamp (64) + 836 | | 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 838 | | 839 . . 840 . Extension Field 1 (variable) . 841 . . 842 | | 843 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 844 | | 845 . . 846 . Extension Field 2 (variable) . 847 . . 848 | | 849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 850 | Key Identifier | 851 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 852 | | 853 | dgst (128) | 854 | | 855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 857 Figure 8: Packet Header Format 859 The extension fields are used to add optional capabilities, for 860 example, the Autokey security protocol [I-D.ietf-ntp-autokey]. The 861 extension field format is presented in order that the packet can be 862 parsed without knowledge of the extension field functions. The MAC 863 is used by both Autokey and the symmetric key authentication scheme. 865 A list of the packet header variables is shown in Figure 7 and 866 described in detail below. Except for a minor variation when using 867 the IPv6 address family, these fields are backwards compatible with 868 NTPv3. The packet header fields apply to both transmitted packets (x 869 prefix) and received packets (r prefix). In Figure 8 the size of 870 some multiple-word fields is shown in bits if not the default 32 871 bits. The basic header extends from the beginning of the packet to 872 the end of the Transmit Timestamp field. 874 The fields and associated packet variables (in parentheses) are 875 interpreted as follows: 877 LI Leap Indicator (leap): 2-bit integer warning of an impending leap 878 second to be inserted or deleted in the last minute of the current 879 month with values defined in Figure 9. 881 +-------+----------------------------------------+ 882 | Value | Meaning | 883 +-------+----------------------------------------+ 884 | 0 | no warning | 885 | 1 | last minute of the day has 61 seconds | 886 | 2 | last minute of the day has 59 seconds | 887 | 3 | unknown (clock unsynchronized) | 888 +-------+----------------------------------------+ 890 Figure 9: Leap Indicator 892 VN Version Number (version): 3-bit integer representing the NTP 893 version number, currently 4. 895 Mode (mode): 3-bit integer representing the mode, with values defined 896 in Figure 10. 898 +-------+--------------------------+ 899 | Value | Meaning | 900 +-------+--------------------------+ 901 | 0 | reserved | 902 | 1 | symmetric active | 903 | 2 | symmetric passive | 904 | 3 | client | 905 | 4 | server | 906 | 5 | broadcast | 907 | 6 | NTP control message | 908 | 7 | reserved for private use | 909 +-------+--------------------------+ 911 Figure 10: Association Modes 913 Stratum (stratum): 8-bit integer representing the stratum, with 914 values defined in Figure 11. 916 +--------+-----------------------------------------------------+ 917 | Value | Meaning | 918 +--------+-----------------------------------------------------+ 919 | 0 | unspecified or invalid | 920 | 1 | primary server (e.g., equipped with a GPS receiver) | 921 | 2-15 | secondary server (via NTP) | 922 | 16 | unsynchronized | 923 | 17-255 | reserved | 924 +--------+-----------------------------------------------------+ 926 Figure 11: Packet Stratum 928 It is customary to map the stratum value 0 in received packets to 929 MAXSTRAT (16) in the peer variable p.stratum and to map p.stratum 930 values of MAXSTRAT or greater to 0 in transmitted packets. This 931 allows reference clocks, which normally appear at stratum 0, to be 932 conveniently mitigated using the same clock selection algorithms used 933 for external sources (See Appendix A.5.5.1 for an example). 935 Poll: 8-bit signed integer representing the maximum interval between 936 successive messages, in log2 seconds. Suggested default limits for 937 minimum and maximum poll intervals are 6 and 10, respectively. 939 Precision: 8-bit signed integer representing the precision of the 940 system clock, in log2 seconds. For instance a value of -18 941 corresponds to a precision of about one microsecond. The precision 942 can be determined when the service first starts up as the minimum 943 time of several iterations to read the system clock. 945 Root Delay (rootdelay): Total round trip delay to the reference 946 clock, in NTP short format. 948 Root Dispersion (rootdisp): Total dispersion to the reference clock, 949 in NTP short format. 951 Reference ID (refid): 32-bit code identifying the particular server 952 or reference clock. The interpretation depends on the value in the 953 stratum field. For packet stratum 0 (unspecified or invalid) this is 954 a four-character ASCII[RFC1345] string, called the kiss code, used 955 for debugging and monitoring purposes. For stratum 1 (reference 956 clock) this is a four-octet, left-justified, zero-padded ASCII string 957 assigned to the reference clock. The authoritative list of Reference 958 Identifiers is maintained by IANA, however any string beginning with 959 the ASCII character "X" is reserved for unregistered experimentation 960 and development. The identifiers in Figure 12 have been used as 961 ASCII identifiers: 963 +------+----------------------------------------------------------+ 964 | ID | Clock Source | 965 +------+----------------------------------------------------------+ 966 | GOES | Geosynchronous Orbit Environment Satellite | 967 | GPS | Global Position System | 968 | GAL | Galileo Positioning System | 969 | PPS | Generic pulse-per-second | 970 | IRIG | Inter-Range Instrumentation Group | 971 | WWVB | LF Radio WWVB Ft. Collins, CO 60 kHz | 972 | DCF | LF Radio DCF77 Mainflingen, DE 77.5 kHz | 973 | HBG | LF Radio HBG Prangins, HB 75 kHz | 974 | MSF | LF Radio MSF Anthorn, UK 60 kHz | 975 | JJY | LF Radio JJY Fukushima, JP 40 kHz, Saga, JP 60 kHz | 976 | LORC | MF Radio LORAN C station, 100 kHz | 977 | TDF | MF Radio Allouis, FR 162 kHz | 978 | CHU | HF Radio CHU Ottawa, Ontario | 979 | WWV | HF Radio WWV Ft. Collins, CO | 980 | WWVH | HF Radio WWVH Kauai, HI | 981 | NIST | NIST telephone modem | 982 | ACTS | NIST telephone modem | 983 | USNO | USNO telephone modem | 984 | PTB | European telephone modem | 985 +------+----------------------------------------------------------+ 987 Figure 12: Reference Identifiers 989 Above stratum 1 (secondary servers and clients) this is the reference 990 identifier of the server and can be used to detect timing loops. If 991 using the IPv4 address family, the identifier is the four-octet IPv4 992 address. If using the IPv6 address family, it is the first four 993 octets of the MD5 hash of the IPv6 address. Note that, when using 994 the IPv6 address family on an NTPv4 server with a NTPv3 client, the 995 Reference Identifier field appears to be a random value and a timing 996 loop might not be detected. 998 Reference Timestamp: Time when the system clock was last set or 999 corrected, in NTP timestamp format. 1001 Origin Timestamp (org): Time at the client when the request departed 1002 for the server, in NTP timestamp format. 1004 Receive Timestamp (rec): Time at the server when the request arrived 1005 from the client, in NTP timestamp format. 1007 Transmit Timestamp (xmt): Time at the server when the response left 1008 for the client, in NTP timestamp format. 1010 Destination Timestamp (dst): Time at the client when the reply 1011 arrived from the server, in NTP timestamp format. 1013 Note: Destination Timestamp field is not included as a header field; 1014 it is determined upon arrival of the packet and made available in the 1015 packet buffer data structure. 1017 If NTP has access to the physical layer, then the timestamps are 1018 associated with the beginning of the symbol after the start of frame. 1019 Otherwise, implementations should attempt to associate the timestamp 1020 to the earliest accessible point in the frame. 1022 The MAC consists of the Key Identifier followed by the Message 1023 Digest. The message digest, or cryptosum, is calculated as in 1024 [RFC1321] over all NTP header and optional extension fields, but not 1025 the MAC itself. 1027 Extension Field n: See Section 7.5 for a description of the format of 1028 this field. 1030 Key Identifier (keyid): 32-bit unsigned integer used by the client 1031 and server to designate a secret 128-bit MD5 key. 1033 Message Digest (digest): 128-bit MD5 hash computed over the key 1034 followed by the NTP packet header and extensions fieds (but not the 1035 Key Identifier or Message Digest fields). 1037 It should be noted that the MAC computation used here differs from 1038 those defined in [RFC1305] and [RFC4330] but is consistent with how 1039 existing implementations generate a MAC. 1041 7.4. The Kiss-o'-Death Packet 1043 If the Stratum field is 0, which implies unspecified or invalid, the 1044 Reference Identifier field can be used to convey messages useful for 1045 status reporting and access control. These are called Kiss-o'-Death 1046 (KoD) packets and the ASCII messages they convey are called kiss 1047 codes. The KoD packets got their name because an early use was to 1048 tell clients to stop sending packets that violate server access 1049 controls. The kiss codes can provide useful information for an 1050 intelligent client, either NTPv4 or SNTPv4. Kiss codes are encoded 1051 in four-character ASCII strings left justified and zero filled. The 1052 strings are designed for character displays and log files. A list of 1053 the currently-defined kiss codes is given in Figure 13. Recipients 1054 of kiss codes MUST inspect them and in the following cases take these 1055 actions: 1057 a. For kiss codes: DENY, RSTR the client MUST demobilize any 1058 associations to that server and stop sending packets to that 1059 server; 1061 b. For kiss code: RATE the client MUST immediately reduce its 1062 polling interval to that server and continue to reduce it each 1063 time it receives a RATE kiss code. 1065 c. Kiss codes beginning with the ASCII character "X" are for 1066 unregistered experimentation and development and MUST be ignored 1067 if not recognized. 1069 d. Other than the above conditions, KoD packets have no protocol 1070 significance and are discarded after inspection. 1072 +------+------------------------------------------------------------+ 1073 | Code | Meaning | 1074 +------+------------------------------------------------------------+ 1075 | ACST | The association belongs to a unicast server | 1076 | AUTH | Server authentication failed | 1077 | AUTO | Autokey sequence failed | 1078 | BCST | The association belongs to a broadcast server | 1079 | CRYP | Cryptographic authentication or identification failed | 1080 | DENY | Access denied by remote server | 1081 | DROP | Lost peer in symmetric mode | 1082 | RSTR | Access denied due to local policy | 1083 | INIT | The association has not yet synchronized for the first | 1084 | | time | 1085 | MCST | The association belongs to a dynamically discovered server | 1086 | NKEY | No key found. Either the key was never installed or is | 1087 | | not trusted | 1088 | RATE | Rate exceeded. The server has temporarily denied access | 1089 | | because the client exceeded the rate threshold | 1090 | RMOT | Alteration of association from a remote host running | 1091 | | ntpdc. | 1092 | STEP | A step change in system time has occurred, but the | 1093 | | association has not yet resynchronized | 1094 +------+------------------------------------------------------------+ 1096 Figure 13: Kiss Codes 1098 The Receive Timestamp and the Transmit Timestamp (set by the server) 1099 are undefined when in a KoD packet and MUST NOT be relied upon to 1100 have valid values and MUST be discarded. 1102 7.5. NTP Extension Field Format 1104 In NTPv4 one or more extension fields can be inserted after the 1105 header and before the MAC, which is always present when an extension 1106 field is present. Other than defining the field format, this 1107 document makes no use of the field contents. An extension field 1108 contains a request or response message in the format shown in 1109 Figure 14. 1111 0 1 2 3 1112 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1114 | Field Type | Length | 1115 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1116 . . 1117 . Value . 1118 . . 1119 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1120 | Padding (as needed) | 1121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1123 Figure 14: Extension Field Format 1125 All extension fields are zero-padded to a word (4 octets) boundary. 1126 The Field Type field is specific to the defined function and is not 1127 elaborated here. While the minimum field length containing required 1128 fields is 4 words (16 octets), a maximum field length remains to be 1129 established. 1131 The Length field is a 16-bit unsigned integer which indicates the 1132 length of the entire extension field in octets, including the Padding 1133 field. 1135 8. On Wire Protocol 1137 The heart of the NTP on-wire protocol is the core mechanism which 1138 exchanges time values between servers, peers and clients. It is 1139 inherently resistant to lost or duplicate packets. Data integrity is 1140 provided by the IP and UDP checksums. No flow control or 1141 retransmission facilities are provided or necessary. The protocol 1142 uses timestamps, either extracted from packet headers or struck from 1143 the system clock upon the arrival or departure of a packet. 1144 Timestamps are precision data and should be restruck in case of link 1145 level retransmission and corrected for the time to compute a MAC on 1146 transmit. 1148 NTP messages make use of two different communication modes, one-to- 1149 one and one-to-many, commonly referred to as unicast and broadcast. 1150 For the purposes of this document, the term broadcast is interpreted 1151 as any available one-to-many mechanism. For IPv4 this equates to 1152 either IPv4 broadcast or IPv4 multicast. For IPv6 this equates to 1153 IPv6 multicast. For this purpose, IANA has allocated the IPv4 1154 multicast address 224.0.1.1 and the IPv6 multicast address ending 1155 :101, with prefix determined by scoping rules. Any other non- 1156 allocated multicast address may also be used in addition to these 1157 allocated multicast addresses. 1159 The on-wire protocol uses four timestamps numbered t1 through t4 and 1160 three state variables org, rec and xmt, as shown in Figure 15. This 1161 figure shows the most general case where each of two peers, A and B, 1162 independently measure the offset and delay relative to the other. 1163 For purposes of illustration the packet timestamps are shown in lower 1164 case, while the state variables are shown in upper case. The state 1165 variables are copied from the packet timestamps upon arrival or 1166 departure of a packet. 1168 t2 t3 t6 t7 1169 +---------+ +---------+ +---------+ +---------+ 1170 | 0 | | t1 | | t3 | | t5 | 1171 +---------+ +---------+ +---------+ +---------+ 1172 | 0 | | t2 | | t4 | | t6 | Packet 1173 +---------+ +---------+ +---------+ +---------+ Timestamps 1174 | t1 | |t3=clock | | t5 | |t7=clock | 1175 +---------+ +---------+ +---------+ +---------+ 1176 |t2=clock | |t6=clock | 1177 +---------+ +---------+ 1178 Peer B 1179 +---------+ +---------+ +---------+ +---------+ 1180 org | T1 | | T1 | | t5<>T1? | | T5 | 1181 +---------+ +---------+ +---------+ +---------+ State 1182 rec | T2 | | T2 | | T6 | | T6 | Variables 1183 +---------+ +---------+ +---------+ +---------+ 1184 xmt | 0 | | T3 | | t3=T3? | | T7 | 1185 +---------+ +---------+ +---------+ +---------+ 1187 t2 t3 t6 t7 1188 --------------------------------------------------------- 1189 /\ \ /\ \ 1190 / \ / \ 1191 / \ / \ 1192 / \/ / \/ 1193 --------------------------------------------------------- 1194 t1 t4 t5 t8 1196 t1 t4 t5 t8 1197 +---------+ +---------+ +---------+ +---------+ 1198 | 0 | | t1 | | t3 | | t5 | 1199 +---------+ +---------+ +---------+ +---------+ 1200 | 0 | | t2 | | t4 | | t6 | Packet 1201 +---------+ +---------+ +---------+ +---------+ Timestamps 1202 |t1=clock | | t3 | |t5=clock | | t7 | 1203 +---------+ +---------+ +---------+ +---------+ 1204 |t4=clock | |t8=clock | 1205 +---------+ +---------+ 1206 Peer A 1207 +---------+ +---------+ +---------+ +---------+ 1208 org | 0 | | t3<>0? | | T3 | | t7<>T3? | 1209 +---------+ +---------+ +---------+ +---------+ State 1210 rec | 0 | | T4 | | T4 | | T8 | Variables 1211 +---------+ +---------+ +---------+ +---------+ 1212 xmt | T1 | | t1=T1? | | T5 | | t5=T5? | 1213 +---------+ +---------+ +---------+ +---------+ 1214 Figure 15: On-Wire Protocol 1216 In the figure the first packet transmitted by A contains only the 1217 origin timestamp t1, which is then copied to T1. B receives the 1218 packet at t2 and copies t1 to T1 and the receive timestamp t2 to T2. 1219 At this time or some time later at t3, B sends a packet to A 1220 containing t1 and t2 and in addition the transmit timestamp t3. All 1221 three timestamps are copied to the corresponding state variables. A 1222 receives the packet at t4 containing the three timestamps t1, t2 and 1223 t3 and in addition the destination timestamp t4. These four 1224 timestamps are used to compute the offset and delay of B relative to 1225 A, as described below. 1227 Before the xmt and org state variables are updated, two sanity checks 1228 are performed in order to protect against duplicate, bogus or 1229 replayed packets. In the exchange above, a packet is duplicate or 1230 replay if the transmit timestamp t3 in the packet matches the org 1231 state variable T3. A packet is bogus if the origin timestamp t1 in 1232 the packet does not match the xmt state variable T1. In either of 1233 these cases the state variables are updated, then the packet is 1234 discarded. To protect against replay of the last transmitted packet, 1235 the xmt state variable is set to zero immediately after a successful 1236 bogus check. 1238 The four most recent timestamps, T1 through T4, are used to compute 1239 the offset of B relative to A 1241 theta = T(B) - T(A) = 1/2 * [(T2-T1) + (T3-T4)] 1243 and the round trip delay 1245 delta = T(ABA) = (T4-T1) - (T3-T2). 1247 Note that the quantities within parentheses are computed from 64-bit 1248 unsigned timestamps and result in signed values with 63 significant 1249 bits plus sign. These values can represent dates from 68 years in 1250 the past to 68 years in the future. However, the offset and delay 1251 are computed as sums and differences of these values, which contain 1252 62 significant bits and two sign bits, so can represent unambiguous 1253 values from 34 years in the past to 34 years in the future. In other 1254 words, the time of the client must be set within 34 years of the 1255 server before the service is started. This is a fundamental 1256 limitation with 64-bit integer arithmetic. 1258 In implementations where floating double arithmetic is available, the 1259 first-order differences can be converted to floating double and the 1260 second-order sums and differences computed in that arithmetic. Since 1261 the second-order terms are typically very small relative to the 1262 timestamp magnitudes, there is no loss in significance, yet the 1263 unambiguous range is restored from 34 years to 68 years. 1265 In some scenarios where the initial frequency offset of the client is 1266 relatively large and the actual propagation time small, it is 1267 possible for the delay computation to becomes negative. For 1268 instance, if the frequency difference is 100 PPM and the interval 1269 T4-T1 is 64 s, the apparent delay is -6.4 ms. Since negative values 1270 are misleading in subsequent computations, the value of delta should 1271 be clamped not less than s.rho, where s.rho is the system precision 1272 described in Section 11.1, expressed in seconds. 1274 The discussion above assumes the most general case where two 1275 symmetric peers independently measure the offsets and delays between 1276 them. In the case of a stateless server, the protocol can be 1277 simplified. A stateless server copies T3 and T4 from the client 1278 packet to T1 and T2 of the server packet and tacks on the transmit 1279 timestamp T3 before sending it to the client. Additional details for 1280 filling in the remaining protocol fields are given in a Section 9 and 1281 following sections and in the appendix. 1283 Note that the on-wire protocol as described resists replay of a 1284 server response packet. However, it does not resist replay of the 1285 client request packet, which would result in a server reply packet 1286 with new values of T2 and T3 and result in incorrect offset and 1287 delay. This vulnerability can be avoided by setting the xmt state 1288 variable to zero after computing the offset and delay. 1290 9. Peer Process 1292 The process descriptions to follow include a listing of the important 1293 state variables followed by an overview of the process operations 1294 implemented as routines. Frequent reference is made to the skeleton 1295 in the appendix. The skeleton includes C-language fragments that 1296 describe the functions in more detail. It includes the parameters, 1297 variables and declarations necessary for a conforming NTPv4 1298 implementation. However, many additional variables and routines may 1299 be necessary in a working implementation. 1301 The peer process is called upon arrival of a server or peer packet. 1302 It runs the on-wire protocol to determine the clock offset and round 1303 trip delay and in addition computes statistics used by the system and 1304 poll processes. Peer variables are instantiated in the association 1305 data structure when the structure is initialized and updated by 1306 arriving packets. There is a peer process, poll process and 1307 association for each server. 1309 9.1. Peer Process Variables 1311 Figure 16, Figure 17, Figure 18 and Figure 19 summarize the common 1312 names, formula names and a short description of the peer variables. 1313 The common names and formula names are interchangeable; formula names 1314 are intended to increase readability of equations in this 1315 specification. Unless noted otherwise, all peer variables have 1316 assumed prefix p. 1318 +---------+----------+-----------------------+ 1319 | Name | Formula | Description | 1320 +---------+----------+-----------------------+ 1321 | srcaddr | srcaddr | source address | 1322 | srcport | srcport | source port | 1323 | dstaddr | dstaddr | destination address | 1324 | dstport | destport | destination port | 1325 | keyid | keyid | key identifier key ID | 1326 +---------+----------+-----------------------+ 1328 Figure 16: Peer Process Configuration Variables 1330 +-----------+------------+---------------------+ 1331 | Name | Formula | Description | 1332 +-----------+------------+---------------------+ 1333 | leap | leap | leap indicator | 1334 | version | version | version number | 1335 | mode | mode | mode | 1336 | stratum | stratum | stratum | 1337 | ppoll | ppoll | peer poll exponent | 1338 | rootdelay | delta_r | root delay | 1339 | rootdisp | epsilon_r | root dispersion | 1340 | refid | refid | reference ID | 1341 | reftime | reftime | reference timestamp | 1342 +-----------+------------+---------------------+ 1344 Figure 17: Peer Process Packet Variables 1346 +------+---------+--------------------+ 1347 | Name | Formula | Description | 1348 +------+---------+--------------------+ 1349 | org | T1 | origin timestamp | 1350 | rec | T2 | receive timestamp | 1351 | xmt | T3 | transmit timestamp | 1352 | t | t | packet time | 1353 +------+---------+--------------------+ 1355 Figure 18: Peer Process Timestamp Variables 1357 +--------+---------+-----------------+ 1358 | Name | Formula | Description | 1359 +--------+---------+-----------------+ 1360 | offset | theta | clock offset | 1361 | delay | delta | roundtrip delay | 1362 | disp | epsilon | dispersion | 1363 | jitter | psi | jitter | 1364 | filter | filter | clock filter | 1365 | tp | t_p | filter time | 1366 +--------+---------+-----------------+ 1368 Figure 19: Peer Process Statistics Variables 1370 The following configuration variables are normally initialized when 1371 the association is mobilized, either from a configuration file or 1372 upon the arrival of the first packet for an unknown association. 1374 srcaddr: IP address of the remote server or reference clock. This 1375 becomes the destination IP address in packets sent from this 1376 association. 1378 srcport: UDP port number of the server or reference clock. This 1379 becomes the destination port number in packets sent from this 1380 association. When operating in symmetric modes (1 and 2) this field 1381 must contain the NTP port number PORT (123) assigned by the IANA. In 1382 other modes it can contain any number consistent with local policy. 1384 dstaddr: IP address of the client. This becomes the source IP 1385 address in packets sent from this association. 1387 dstport: UDP port number of the client, ordinarily the NTP port 1388 number PORT (123) assigned by the IANA. This becomes the source port 1389 number in packets sent from this association. 1391 keyid: Symmetric key ID for the 128-bit MD5 key used to generate and 1392 verify the MAC. The client and server or peer can use different 1393 values, but they must map to the same key. 1395 The variables defined in Figure 17 are updated from the packet header 1396 as each packet arrives. They are interpreted in the same way as the 1397 packet variables of the same names. It is convenient for later 1398 processing to convert the NTP short format packet values r.rootdelay 1399 and r.rootdisp to floating doubles as peer variables. 1401 The variables defined in Figure 18 include the timestamps exchanged 1402 by the on-wire protocol in Section 8. The t variable is the seconds 1403 counter c.t associated with these values. The c.t variable is 1404 maintained by the clock adjust process described in Section 12. It 1405 counts the seconds since the service was started. The variables 1406 defined in Figure 19 include the statistics computed by the 1407 clock_filter() routine described in Section 10. The tp variable is 1408 the seconds counter associated with these values. 1410 9.2. Peer Process Operations 1412 The receive routine defines the process flow upon the arrival of a 1413 packet. An example is described by the receive() routine in 1414 Appendix A.5.1. There is no specific method required for access 1415 control, although it is recommended that implementations include such 1416 a scheme, which is similar to many others now in widespread use. The 1417 access() routine in Appendix A.5.4 describes a method of implementing 1418 access restrictions using an access control list (ACL). Format 1419 checks require correct field length and alignment, acceptable version 1420 number (1-4) and correct extension field syntax, if present. 1422 There is no specific requirement for authentication; however, if 1423 authentication is implemented, then the MD5 keyed hash algorithm 1424 described in [RFC1321] must be supported. 1426 Next, the association table is searched for matching source address 1427 and source port, for example using the find_assoc() routine in 1428 Appendix A.5.1. Figure 20 is a dispatch table where the columns 1429 correspond to the packet mode and rows correspond to the association 1430 mode. The intersection of the association and packet modes 1431 dispatches processing to one of the following steps. 1433 +------------------+---------------------------------------+ 1434 | | Packet Mode | 1435 +------------------+-------+-------+-------+-------+-------+ 1436 | Association Mode | 1 | 2 | 3 | 4 | 5 | 1437 +------------------+-------+-------+-------+-------+-------+ 1438 | No Association 0 | NEWPS | DSCRD | FXMIT | MANY | NEWBC | 1439 | Symm. Active 1 | PROC | PROC | DSCRD | DSCRD | DSCRD | 1440 | Symm. Passive 2 | PROC | ERR | DSCRD | DSCRD | DSCRD | 1441 | Client 3 | DSCRD | DSCRD | DSCRD | PROC | DSCRD | 1442 | Server 4 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | 1443 | Broadcast 5 | DSCRD | DSCRD | DSCRD | DSCRD | DSCRD | 1444 | Bcast Client 6 | DSCRD | DSCRD | DSCRD | DSCRD | PROC | 1445 +------------------+-------+-------+-------+-------+-------+ 1447 Figure 20: Peer Dispatch Table 1449 DSCRD. This indicates a nonfatal violation of protocol as the result 1450 of a programming error, long delayed packet or replayed packet. The 1451 peer process discards the packet and exits. 1453 ERR. This indicates a fatal violation of protocol as the result of a 1454 programming error, long delayed packet or replayed packet. The peer 1455 process discards the packet, demobilizes the symmetric passive 1456 association and exits. 1458 FXMIT. This indicates a client (mode 3) packet matching no 1459 association (mode 0). If the destination address is not a broadcast 1460 address, the server constructs a server (mode 4) packet and returns 1461 it to the client without retaining state. The server packet header 1462 is constructed. An example is described by the fast_xmit() routine 1463 in Appendix A.5.3. The packet header is assembled from the receive 1464 packet and system variables as shown in Figure 21. If the 1465 s.rootdelay and s.rootdisp system variables are stored in floating 1466 double, they must be converted to NTP short format first. 1468 +-----------------------------------+ 1469 | Packet Variable --> Variable | 1470 +-----------------------------------+ 1471 | r.leap --> p.leap | 1472 | r.mode --> p.mode | 1473 | r.stratum --> p.stratum | 1474 | r.poll --> p.ppoll | 1475 | r.rootdelay --> p.rootdelay | 1476 | r.rootdisp --> p.rootdisp | 1477 | r.refid --> p.refid | 1478 | r.reftime --> p.reftime | 1479 | r.keyid --> p.keyid | 1480 +-----------------------------------+ 1482 Figure 21: Receive Packet Header 1484 Note that, if authentication fails, the server returns a special 1485 message called a crypto-NAK. This message includes the normal NTP 1486 header data shown in Figure 8, but with a MAC consisting of four 1487 octets of zeros. The client MAY accept or reject the data in the 1488 message. After these actions the peer process exits. 1490 If the destination address is a multicast address, the sender is 1491 operating in manycast client mode. If the packet is valid and the 1492 server stratum is less than the client stratum, the server sends an 1493 ordinary server (mode 4) packet, but using its unicast destination 1494 address. A crypto-NAK is not sent if authentication fails. After 1495 these actions the peer process exits. 1497 MANY: This indicates a server (mode 4) packet matching no 1498 association. Ordinarily, this can happen only as the result of a 1499 manycast server reply to a previously sent multicast client packet. 1500 If the packet is valid, an ordinary client (mode 3) association is 1501 mobilized and operation continues as if the association was mobilized 1502 by the configuration file. 1504 NEWBC. This indicates a broadcast (mode 5) packet matching no 1505 association. The client mobilizes either a client (mode 3) or 1506 broadcast client (mode 6) association. Examples are shown in the 1507 mobilize() and clear() routines in Appendix A.2. Then the packet is 1508 validated and the peer variables initialized. An example is provided 1509 by the packet() routine in Appendix A.5.1.1. 1511 If the implementation supports no additional security or calibration 1512 functions, the association mode is set to broadcast client (mode 6) 1513 and the peer process exits. Implementations supporting public key 1514 authentication MAY run the Autokey or equivalent security protocol. 1515 Implementations SHOULD set the association mode to 3 and run a short 1516 client/server exchange to determine the propagation delay. Following 1517 the exchange the association mode is set to 6 and the peer process 1518 continues in listen-only mode. Note the distinction between a mode-6 1519 packet, which is reserved for the NTP monitor and control functions, 1520 and a mode-6 association. 1522 NEWPS. This indicates a symmetric active (mode 1) packet matching no 1523 association. The client mobilizes a symmetric passive (mode 2) 1524 association. An example is shown in the mobilize() and clear() 1525 routines in Appendix A.2. Processing continues in the PROC section 1526 below. 1528 PROC. This indicates a packet matching an existing association. The 1529 packet timestamps are carefully checked to avoid invalid, duplicate 1530 or bogus packets. Additional checks are summarized in Figure 22. 1531 Note that all packets, including a crypto-NAK, are considered valid 1532 only if they survive these tests. 1534 +--------------------------+----------------------------------------+ 1535 | Packet Type | Description | 1536 +--------------------------+----------------------------------------+ 1537 | 1 duplicate packet | The packet is at best an old duplicate | 1538 | | or at worst a replay by a hacker. | 1539 | | This can happen in symmetric modes if | 1540 | | the poll intervals are uneven. | 1541 | 2 bogus packet | | 1542 | 3 invalid | One or more timestamp fields are | 1543 | | invalid. This normally happens in | 1544 | | symmetric modes when one peer sends | 1545 | | the first packet to the other and | 1546 | | before the other has received its | 1547 | | first reply. | 1548 | 4 access denied | The access controls have blacklisted | 1549 | | the source. | 1550 | 5 authentication failure | The cryptographic message digest does | 1551 | | not match the MAC. | 1552 | 6 unsynchronized | The server is not synchronized to a | 1553 | | valid source. | 1554 | 7 bad header data | One or more header fields are invalid. | 1555 +--------------------------+----------------------------------------+ 1557 Figure 22: Packet Error Checks 1559 Processing continues by coping the packet variables to the peer 1560 variables as shown in Figure 21. An example is described by the 1561 packet() routine in Appendix A.5.1.1. The receive() routine 1562 implements tests 1-5 in Figure 22; the packet() routine implements 1563 tests 6-7. If errors are found the packet is discarded and the peer 1564 process exits. 1566 The on-wire protocol calculates the clock offset theta and round trip 1567 delay delta from the four most recent timestamps as described in 1568 Section 8. While it is in principle possible to do all calculations 1569 except the first-order timestamp differences in fixed-point 1570 arithmetic, it is much easier to convert the first-order differences 1571 to floating doubles and do the remaining calculations in that 1572 arithmetic, and this will be assumed in the following description. 1574 Next, the 8-bit p.reach shift register in the poll process described 1575 in Section 13 is used to determine whether the server is reachable 1576 and the data are fresh. The register is shifted left by one bit when 1577 a packet is sent and the rightmost bit is set to zero. As valid 1578 packets arrive, the rightmost bit is set to one. If the register 1579 contains any nonzero bits, the server is considered reachable; 1580 otherwise, it is unreachable. Since the peer poll interval might 1581 have changed since the last packet, the host poll interval is 1582 reviewed. An example is provided by the poll_update() routine in 1583 Appendix A.5.7.2. 1585 The dispersion statistic epsilon(t) represents the maximum error due 1586 to the frequency tolerance and time since the last packet was sent. 1587 It is initialized 1589 epsilon(t_0) = r.rho + s.rho + PHI * (T4-T1) 1591 when the measurement is made at t_0 according to the seconds counter. 1592 Here r.rho is the packet precision described in Section 7.3 and s.rho 1593 is the system precision described in Section 11.1, both expressed in 1594 seconds. These terms are necessary to account for the uncertainty in 1595 reading the system clock in both the server and the client. 1597 The dispersion then grows at constant rate PHI; in other words, at 1598 time t, epsilon(t) = epsilon(t_0) + PHI * (t-t_0). With the default 1599 value PHI = 15 PPM, this amounts to about 1.3 s per day. With this 1600 understanding, the argument t will be dropped and the dispersion 1601 represented simply as epsilon. The remaining statistics are computed 1602 by the clock filter algorithm described in the next section. 1604 10. Clock Filter Algorithm 1606 The clock filter algorithm is part of the peer process. It grooms 1607 the stream of on-wire data to select the samples most likely to 1608 represent accurate time. The algorithm produces the variables shown 1609 in Figure 19, including the offset (theta), delay (delta), dispersion 1610 (epsilon), jitter (psi) and time of arrival (t). These data are used 1611 by the mitigation algorithms to determine the best and final offset 1612 used to discipline the system clock. They are also used to determine 1613 the server health and whether it is suitable for synchronization. 1615 The clock filter algorithm saves the most recent sample tuples 1616 (theta, delta, epsilon, t) in the filter structure, which functions 1617 as an 8-stage shift register. The tuples are saved in the order that 1618 packets arrive. Here t is the packet time of arrival according to 1619 the seconds counter and should not be confused with the peer variable 1620 tp. 1622 The following scheme is used to insure sufficient samples are in the 1623 filter and that old stale data are discarded. Initially, the tuples 1624 of all stages are set to the dummy tuple (0, MAXDISP, MAXDISP, 0). 1625 As valid packets arrive, tuples are shifted into the filter causing 1626 old tuples to be discarded, so eventually only valid tuples remain. 1627 If the three low order bits of the reach register are zero, 1628 indicating three poll intervals have expired with no valid packets 1629 received, the poll process calls the clock filter algorithm with a 1630 dummy tuple just as if the tuple had arrived from the network. If 1631 this persists for eight poll intervals, the register returns to the 1632 initial condition. 1634 In the next step the shift register stages are copied to a temporary 1635 list and the list sorted by increasing delta. Let i index the stages 1636 starting with the lowest delta. If the first tuple epoch t_0 is not 1637 later than the last valid sample epoch tp, the routine exits without 1638 affecting the current peer variables. Otherwise, let epsilon_i be 1639 the dispersion of the ith entry, then 1640 i=n-1 1641 --- epsilon_i 1642 epsilon = \ ---------- 1643 / (i+1) 1644 --- 2 1645 i=0 1647 is the peer dispersion p.disp. Note the overload of epsilon, whether 1648 input to the clock filter or output, the meaning should be clear from 1649 context. 1651 The observer should note (a) if all stages contain the dummy tuple 1652 with dispersion MAXDISP, the computed dispersion is a little less 1653 than 16 s, (b) each time a valid tuple is shifted into the register, 1654 the dispersion drops by a little less than half, depending on the 1655 valid tuples dispersion, (c) after the fourth valid packet the 1656 dispersion is usually a little less than 1 s, which is the assumed 1657 value of the MAXDIST parameter used by the selection algorithm to 1658 determine whether the peer variables are acceptable or not. 1660 Let the first stage offset in the sorted list be theta_0; then, for 1661 the other stages in any order, the jitter is the RMS average 1662 +----- -----+^1/2 1663 | n-1 | 1664 | --- | 1665 1 | \ 2 | 1666 psi = -------- * | / (theta_0-theta_j) | 1667 (n-1) | --- | 1668 | j=1 | 1669 +----- -----+ 1671 where n is the number of valid tuples in the filter (n > 1). In 1672 order to insure consistency and avoid divide exceptions in other 1673 computations, the psi is bounded from below by the system precision 1674 s.rho expressed in seconds. While not in general considered a major 1675 factor in ranking server quality, jitter is a valuable indicator of 1676 fundamental timekeeping performance and network congestion state. Of 1677 particular importance to the mitigation algorithms is the peer 1678 synchronization distance, which is computed from the delay and 1679 dispersion. 1681 lambda = (delta / 2) + epsilon. 1683 Note that epsilon and therefore lambda increase at rate PHI. The 1684 lambda is not a state variable, since lambda is recalculated at each 1685 use. It is a component of the root synchronization distance used by 1686 the mitigation algorithms as a metric to evaluate the quality of time 1687 available from each server. 1689 It is important to note that, unlike NTPv3, NTPv4 associations do not 1690 show a timeout condition by setting the stratum to 16 and leap 1691 indicator to 3. The association variables retain the values 1692 determined upon arrival of the last packet. In NTPv4 lambda 1693 increases with time, so eventually the synchronization distance 1694 exceeds the distance threshold MAXDIST, in which case the association 1695 is considered unfit for synchronization. 1697 An example implementation of the clock filter algorithm is shown in 1698 the clock_filter() routine of Appendix A.5.2. 1700 11. System Process 1702 As each new sample (theta, delta, epsilon, jitter, t) is produced by 1703 the clock filter algorithm, all peer processes are scanned by the 1704 mitigation algorithms consisting of the selection, cluster, combine 1705 and clock discipline algorithms in the system process. The selection 1706 algorithm scans all associations and casts off the falsetickers, 1707 which have demonstrably incorrect time, leaving the truechimers as 1708 result. In a series of rounds the cluster algorithm discards the 1709 association statistically furthest from the centroid until a 1710 specified minimum number of survivors remain. The combine algorithm 1711 produces the best and final statistics on a weighted average basis. 1712 The final offset is passed to the clock discipline algorithm to steer 1713 the system clock to the correct time. 1715 The cluster algorithm selects one of the survivors as the system 1716 peer. The associated statistics (theta, delta, epsilon, jitter, t) 1717 are used to construct the system variables inherited by dependent 1718 servers and clients and made available to other applications running 1719 on the same machine. 1721 11.1. System Process Variables 1723 Figure 23 summarizes the common names, formula names and a short 1724 description of each system variable. Unless noted otherwise, all 1725 variables have assumed prefix s. 1727 +-----------+------------+------------------------+ 1728 | Name | Formula | Description | 1729 +-----------+------------+------------------------+ 1730 | t | t | update time | 1731 | p | p | system peer identifier | 1732 | leap | leap | leap indicator | 1733 | stratum | stratum | stratum | 1734 | precision | rho | precision | 1735 | offset | THETA | combined offset | 1736 | jitter | PSI | combined jitter | 1737 | rootdelay | DELTA | root delay | 1738 | rootdisp | EPSILON | root dispersion | 1739 | v | v | survivor list | 1740 | refid | refid | reference ID | 1741 | reftime | reftime | reference time | 1742 | NMIN | 3 | minimum survivors | 1743 | CMIN | 1 | minimum candidates | 1744 +-----------+------------+------------------------+ 1746 Figure 23: System Process Variables 1748 Except for the t, p, offset and jitter variables and the NMIN and 1749 CMIN constants, the variables have the same format and interpretation 1750 as the peer variables of the same name. The NMIN and CMIN parameters 1751 are used by the selection and cluster algorithms described in the 1752 next section. 1754 The t variable is the seconds counter at the time of the last update. 1755 An example is shown by the clock_update() routine in 1756 Appendix A.5.5.4. The p variable is the system peer identifier 1757 determined by the cluster() routine in Section 11.2.2. The precision 1758 variable has the same format as the packet variable of the same name. 1759 The precision is defined as the larger of the resolution and time to 1760 read the clock, in log2 units. For instance, the precision of a 1761 mains-frequency clock incrementing at 60 Hz is 16 ms, even when the 1762 system clock hardware representation is to the nanosecond. 1764 The offset and jitter variables are determined by the combine 1765 algorithm in Section 11.2.3. These values represent the best and 1766 final offset and jitter used to discipline the system clock. 1767 Initially, all variables are cleared to zero, then the leap is set to 1768 3 (unsynchronized) and stratum is set to MAXSTRAT (16). Remember 1769 that MAXSTRAT is mapped to zero in the transmitted packet. 1771 11.2. System Process Operations 1773 Figure 24 summarizes the system process operations performed by the 1774 clock select routine. The selection algorithm described in 1775 Section 11.2.1 produces a majority clique of presumed correct 1776 candidates (truechimers) based on agreement principles. The cluster 1777 algorithm described in Section 11.2.2 discards outlyers to produce 1778 the most accurate survivors. The combine algorithm described in 1779 Section 11.2.3 provides the best and final offset for the clock 1780 discipline algorithm. An example is described in Appendix A.5.5.6. 1781 If the selection algorithm cannot produce a majority clique, or if it 1782 cannot produce at least CMIN survivors, the system process exits 1783 without disciplining the system clock. If successful, the cluster 1784 algorithm selects the statistically best candidate as the system peer 1785 and its variables are inherited as the system variables. 1787 +-----------------+ 1788 | clock_select() | 1789 +-----------------+ 1790 ................................|........... 1791 . V . 1792 . yes +---------+ +-----------------+ . 1793 . +--| accept? | | scan candidates | . 1794 . | +---------+ | | . 1795 . V no | | | . 1796 . +---------+ | | | . 1797 . | add peer| | | | . 1798 . +---------- | | | . 1799 . | V | | . 1800 . +---------->-->| | . 1801 . | | . 1802 . Selection Algorithm +-----------------+ . 1803 .................................|.......... 1804 V 1805 no +-------------------+ 1806 +-------------| survivors? | 1807 | +-------------------+ 1808 | | yes 1809 | V 1810 | +-------------------+ 1811 | | Cluster Algorithm | 1812 | +-------------------+ 1813 | | 1814 | V 1815 V yes +-------------------+ 1816 |<------------| n < CMIN? | 1817 | +-------------------+ 1818 V | 1819 +-----------------+ V no 1820 | s.p = NULL | +-------------------+ 1821 +-----------------+ | s.p = v_0.p | 1822 | +-------------------+ 1823 V | 1824 +-----------------+ V 1825 | return (UNSYNC) | +-------------------+ 1826 +-----------------+ | return (SYNC) | 1827 +-------------------+ 1829 Figure 24: Clock Select Routine 1831 11.2.1. Selection Algorithm 1833 Note that the selection and cluster algorithms are described 1834 separately, but combined in the code skeleton. The selection 1835 algorithm operates to find an intersection interval containing a 1836 majority clique of truechimers using Byzantine agreement principles 1837 originally proposed by Marzullo [ref6], but modified to improve 1838 accuracy. An overview of the algorithm is given below and described 1839 in the first half of the clock_select() routine in Appendix A.5.5.1. 1841 First, those servers which are unusable according to the rules of the 1842 protocol are detected and discarded as shown by the accept() routine 1843 in Appendix A.5.5.3. Next, a set of tuples (p, type, edge) is 1844 generated for the remaining candidates. Here, p is the association 1845 identifier and type identifies the upper (+1), middle (0) and lower 1846 (-1) endpoints of a correctness interval centered on theta for that 1847 candidate. This results in three tuples, lowpoint (p, -1, theta - 1848 lambda), midpoint (p, 0, theta) and highpoint (p, +1, theta + 1849 lambda), where lambda is the root synchronization distance. An 1850 example of this calculation is shown by the rootdist() routine in 1851 Appendix A.5.1.1. The steps of the algorithm are: 1853 1. For each of m associations, place three tuples as defined above 1854 on the candidate list. 1856 2. Sort the tuples on the list by the edge component. Order the 1857 lowpoint, midpoint and highpoint of these intervals from lowest to 1858 highest. Set the number of falsetickers f = 0. 1860 3. Set the number of midpoints d = 0. Set c = 0. Scan from lowest 1861 endpoint to highest. Add one to c for every lowpoint, subtract one 1862 for every highpoint, add one to d for every midpoint. If c >= m - f, 1863 stop; set l = current lowpoint. 1865 4. Set c = 0. Scan from highest endpoint to lowest. Add one to c 1866 for every highpoint, subtract one for every lowpoint, add one to d 1867 for every midpoint. If c >= m - f, stop; set u = current highpoint. 1869 5. Is d = f and l < u? If yes, then follow step 5A; else, follow 1870 step 5B. 1872 5A. Success: the intersection interval is [l, u]. 1874 5B. Add one to f. Is f < (m / 2)? If yes, then go to step 3 again. 1875 If no, then go to step 6. 1877 6. Failure; a majority clique could not be found. There are no 1878 suitable candidates to discipline the system clock. 1880 The algorithm is described in detail in Appendix A.5.5.1. Note that 1881 it starts with the assumption that there are no falsetickers (f = 0) 1882 and attempts to find a nonempty intersection interval containing the 1883 midpoints of all correct servers, i.e., truechimers. If a nonempty 1884 interval cannot be found, it increases the number of assumed 1885 falsetickers by one and tries again. If a nonempty interval is found 1886 and the number of falsetickers is less than the number of 1887 truechimers, a majority clique has been found and the midpoint of 1888 each truechimer (theta) represents the candidates available to the 1889 cluster algorithm. 1891 If a majority clique is not found, or if the number of truechimers is 1892 less than CMIN, there are insufficient candidates to discipline the 1893 system clock. CMIN defines the minimum number of servers consistent 1894 with the correctness requirements. Suspicious operators would set 1895 CMIN to insure multiple redundant servers are available for the 1896 algorithms to mitigate properly. However, for historic reasons the 1897 default value for CMIN is one. 1899 11.2.2. Cluster Algorithm 1901 The candidates of the majority clique are placed on the survivor list 1902 v in the form of tuples (p, theta_p, psi_p, lambda_p), where p is an 1903 association identifier, theta_p, psi_p, and stratum_p the current 1904 offset, jitter and stratum of association p, respectively, and 1905 lambda_p is a merit factor equal to stratum_p * MAXDIST + lambda, 1906 where lambda is the root synchronization distance for association p. 1907 The list is processed by the cluster algorithm below. An example is 1908 shown by the second half of the clock_select() algorithm in 1909 Appendix A.5.5.1. 1911 1. Let (p, theta_p, psi_p, lambda_p) represent a survivor candidate. 1913 2. Sort the candidates by increasing lambda_p. Let n be the number 1914 of candidates and NMIN the minimum required number of survivors. 1916 3. For each candidate compute the selection jitter psi_s: 1918 +----- -----+^1/2 1919 | n-1 | 1920 | --- | 1921 | 1 \ 2 | 1922 psi_s = | ---- * / (theta_s - theta_j) | 1923 | n-1 --- | 1924 | j=1 | 1925 +----- -----+ 1927 4. Select psi_max as the candidate with maximum psi_s. 1929 5. Select psi_min as the candidate with minimum psi_p. 1931 6. Is psi_max < psi_min or n <= NMIN? If yes, follow step 6A; 1932 otherwise, follow step 6B. 1934 6A. Done. The remaining candidates on the survivor list are ranked 1935 in the order of preference. The first entry on the list represents 1936 the system peer; its variables are used later to update the system 1937 variables. 1939 6B. Delete the outlyer candidate with psi_max; reduce n by one and go 1940 back to step 3. 1942 The algorithm operates in a series of rounds where each round 1943 discards the statistical outlyer with maximum selection jitter psi_s. 1944 However, if psi_s is less than the minimum peer jitter psi_p, no 1945 improvement is possible by discarding outlyers. This and the minimum 1946 number of survivors represent the terminating conditions of the 1947 algorithm. Upon termination, the final value of psi_max is saved as 1948 the system selection jitter PSI_s for use later. 1950 11.2.3. Combine Algorithm 1952 The clock combine route processes the remaining survivors to produce 1953 the best and final data for the clock discipline algorithm. The 1954 routine processes peer offset and jitter statistics to produce the 1955 combined system offset THETA and system peer jitter PSI_p, where each 1956 server statistic is weighted by the reciprocal of the root 1957 synchronization distance and the result normalized. An example is 1958 shown by the clock_combine() routine in Appendix A.5.5.5 1960 The combined THETA is passed to the clock update routine. The first 1961 candidate on the survivor list is nominated as the system peer with 1962 identifier p. The system peer jitter PSI_p is a component of the 1963 system jitter PSI. It is used along with the selection jitter PSI_s 1964 to produce the system jitter: 1966 PSI = [(PSI_s)^2 + (PSI_p)^2]^1/2 1968 Each time an update is received from the system peer, the clock 1969 update routine is called. By rule, an update is discarded if its 1970 time of arrival p.t is not strictly later than the last update used 1971 s.t. The labels IGNOR, PANIC, ADJ and STEP refer to return codes 1972 from the local clock routine described in the next section. 1974 IGNORE means the update has been ignored as an outlyer. PANIC means 1975 the offset is greater than the panic threshold PANICT (1000 s) and 1976 SHOULD cause the program to exit with a diagnostic message to the 1977 system log. STEP means the offset is less than the panic threshold, 1978 but greater than the step threshold STEPT (125 ms). In this case the 1979 clock is stepped to the correct offset, but since this means all peer 1980 data have been invalidated, all associations MUST be reset and the 1981 client begins as at initial start. 1983 ADJ means the offset is less than the step threshold and thus a valid 1984 update. In this case the system variables are updated from the peer 1985 variables as shown in Figure 25. 1987 +-------------------------------------------+ 1988 | System Variable <-- System Peer Variable | | 1989 +-------------------------------------------+ 1990 | s.leap <-- p.leap | 1991 | s.stratum <-- p.stratum + 1 | 1992 | s.offset <-- THETA | 1993 | s.jitter <-- PSI | 1994 | s.rootdelay <-- p.delta_r + delta | 1995 | s.rootdisp <-- p.epsilon_r + p.epsilon + | 1996 | p.psi + PHI * (s.t - p.t) | 1997 | + |THETA| | 1998 | s.refid <-- p.refid | 1999 | s.reftime <-- p.reftime | 2000 | s.t <-- p.t | 2001 +-------------------------------------------+ 2003 Figure 25: System Variables Update 2005 There is an important detail not shown. The dispersion increment 2006 (p.epsilon + p.psi + PHI * (s.t - p.t) + |THETA|) is bounded from 2007 below by MINDISP. In subnets with very fast processors and networks 2008 and very small delay and dispersion this forces a monotone-definite 2009 increase in s.rootdisp (EPSILON), which avoids loops between peers 2010 operating at the same stratum. 2012 The system variables are available to dependent application programs 2013 as nominal performance statistics. The system offset THETA is the 2014 clock offset relative to the available synchronization sources. The 2015 system jitter PSI is an estimate of the error in determining this 2016 value, elsewhere called the expected error. The root delay DELTA is 2017 the total round trip delay relative to the primary server. The root 2018 dispersion EPSILON is the dispersion accumulated over the network 2019 from the primary server. Finally, the root synchronization distance 2020 is defined 2022 LAMBDA = EPSILON + DELTA / 2, 2024 which represents the maximum error due all causes and is designated 2025 the root synchronization distance. 2027 An example of the clock update routine is provided 2028 inAppendix A.5.5.4. 2030 11.3. Clock Discipline Algorithm 2032 The NTPv4 clock discipline algorithm, shortened to discipline in the 2033 following, functions as a combination of two philosophically quite 2034 different feedback control systems. In a phase-locked loop (PLL) 2035 design, periodic phase updates at update intervals mu seconds are 2036 used directly to minimize the time error and indirectly the frequency 2037 error. In a frequency-locked loop (FLL) design, periodic frequency 2038 updates at intervals mu are used directly to minimize the frequency 2039 error and indirectly the time error. As shown in [ref7], a PLL 2040 usually works better when network jitter dominates, while a FLL works 2041 better when oscillator wander dominates. This section contains an 2042 outline of how the NTPv4 design works. An in-depth discussion of the 2043 design principles is provided in [ref7], which also includes a 2044 performance analysis. 2046 The discipline is implemented as the feedback control system shown in 2047 Figure 26. The variable theta_r represents the combine algorithm 2048 offset (reference phase) and theta_c the VFO offset (control phase). 2049 Each update produces a signal V_d representing the instantaneous 2050 phase difference theta_r - theta_c. The clock filter for each server 2051 functions as a tapped delay line, with the output taken at the tap 2052 selected by the clock filter algorithm. The selection, cluster and 2053 combine algorithms combine the data from multiple filters to produce 2054 the signal V_s. The loop filter, with impulse response F(t), 2055 produces the signal V_c which controls the VFO frequency omega_c and 2056 thus the integral of the phase theta_c which closes the loop. The 2057 V_c signal is generated by the clock adjust process in Section 12. 2058 The detailed equations that implement these functions are best 2059 presented in the routines of Appendix A.5.5.6 and Appendix A.5.6.1. 2061 theta_r + +---------\ +----------------+ 2062 NTP --------->| Phase \ V_d | | V_s 2063 theta_c - | Detector ------>| Clock Filter |----+ 2064 +-------->| / | | | 2065 | +---------/ +----------------+ | 2066 | | 2067 ----- | 2068 / \ | 2069 | VFO | | 2070 \ / | 2071 ----- ....................................... | 2072 ^ . Loop Filter . | 2073 | . +---------+ x +-------------+ . | 2074 | V_c . | |<-----| | . | 2075 +------.-| Clock | y | Phase/Freq |<---------+ 2076 . | Adjust |<-----| Prediction | . 2077 . | | | | . 2078 . +---------+ +-------------+ . 2079 ....................................... 2081 Figure 26: Clock Discipline Feedback Loop 2083 Ordinarily, the pseudo-linear feedback loop described above operates 2084 to discipline the system clock. However, there are cases where a 2085 nonlinear algorithm offers considerable improvement. One case is 2086 when the discipline starts without knowledge of the intrinsic clock 2087 frequency. The pseudo-linear loop takes several hours to develop an 2088 accurate measurement and during most of that time the poll interval 2089 cannot be increased. The nonlinear loop described below does this in 2090 15 minutes. Another case is when occasional bursts of large jitter 2091 are present due to congested network links. The state machine 2092 described below resists error bursts lasting less than 15 minutes. 2094 Figure 27 contains a summary of the variables and parameters 2095 including the variables (lower case) or parameters (upper case) name, 2096 formula name and short description. Unless noted otherwise, all 2097 variables have assumed prefix c. The variables t, tc, state, hyster 2098 and count are integers; the remaining variables are floating doubles. 2099 The function of each will be explained in the algorithm descriptions 2100 below. 2102 +--------+------------+--------------------------+ 2103 | Name | Formula | Description | 2104 +--------+------------+--------------------------+ 2105 | t | timer | seconds counter | 2106 | offset | theta | combined offset | 2107 | resid | theta_r | residual offset | 2108 | freq | phi | clock frequency | 2109 | jitter | psi | clock offset jitter | 2110 | wander | omega | clock frequency wander | 2111 | tc | tau | time constant (log2) | 2112 | state | state | state | 2113 | adj | adj | frequency adjustment | 2114 | hyster | hyster | hysteresis counter | 2115 | STEPT | 125 | step threshold (.125 s) | 2116 | WATCH | 900 | stepout thresh(s) | 2117 | PANICT | 1000 | panic threshold (1000 s) | 2118 | LIMIT | 30 | hysteresis limit | 2119 | PGATE | 4 | hysteresis gate | 2120 | TC | 16 | time constant scale | 2121 | AVG | 8 | averaging constant | 2122 +--------+------------+--------------------------+ 2124 Figure 27: Clock Discipline Variables and Parameters 2126 The process terminates immediately if the offset is greater than the 2127 panic threshold PANICT (1000 s). The state transition function is 2128 described by the rstclock() function in Appendix A.5.5.7. Figure 28 2129 shows the state transition function used by this routine. It has 2130 four columns showing respectively the state name, predicate and 2131 action if the offset theta is less than the step threshold, the 2132 predicate and actions otherwise, and finally some comments. 2134 +-------+---------------------+-------------------+--------------+ 2135 | State | theta < STEP | theta > STEP | Comments | 2136 +-------+---------------------+-------------------+--------------+ 2137 | NSET | ->FREQ | ->FREQ | no frequency | 2138 | | adjust time | step time | file | 2139 +-------+---------------------+-------------------+--------------+ 2140 | FSET | ->SYNC | ->SYNC | frequency | 2141 | | adjust time | step time | file | 2142 +-------+---------------------+-------------------+--------------+ 2143 | SPIK | ->SYNC | if < 900 s ->SPIK | outlyer | 2144 | | adjust freq | else ->SYNC | detected | 2145 | | adjust time | step freq | | 2146 | | | step time | | 2147 +-------+---------------------+-------------------+--------------+ 2148 | FREQ | if < 900 s ->FREQ | if < 900 s ->FREQ | initial | 2149 | | else ->SYNC | else ->SYNC | frequency | 2150 | | step freq | step freq | | 2151 | | adjust time | adjust time | | 2152 +-------+---------------------+-------------------+--------------+ 2153 | SYNC | ->SYNC | if < 900 s ->SPIK | normal | 2154 | | adjust freq | else ->SYNC | operation | 2155 | | adjust time | step freq | | 2156 | | | step time | | 2157 +-------+---------------------+-------------------+--------------+ 2159 Figure 28: State Transition Function 2161 In the table entries the next state is identified by the arrow -> 2162 with the actions listed below. Actions such as adjust time and 2163 adjust frequency are implemented by the PLL/FLL feedback loop in the 2164 local_clock() routine. A step clock action is implemented by setting 2165 the clock directly, but this is done only after the stepout threshold 2166 WATCH (900 s) when the offset is more than the step threshold STEPT 2167 (.125 s). This resists clock steps under conditions of extreme 2168 network congestion. 2170 The jitter (psi) and wander (omega) statistics are computed using an 2171 exponential average with weight factor AVG. The time constant 2172 exponent (tau) is determined by comparing psi with the magnitude of 2173 the current offset theta. If the offset is greater than PGATE (4) 2174 times the clock jitter, the hysteresis counter hyster is reduced by 2175 two; otherwise, it is increased by one. If hyster increases to the 2176 upper limit LIMIT (30), tau is increased by one; if it decreases to 2177 the lower limit -LIMIT (-30), tau is decreased by one. Normally, tau 2178 hovers near MAXPOLL, but quickly decreases if a temperature spike 2179 causes a frequency surge. 2181 12. Clock Adjust Process 2183 The actual clock adjustment process runs at one-second intervals to 2184 add the frequency correction and a fixed percentage of the residual 2185 offset theta_r. The theta_r is in effect the exponential decay of 2186 the theta value produced by the loop filter at each update. The TC 2187 parameter scales the time constant to match the poll interval for 2188 convenience. Note that the dispersion EPSILON increases by PHI at 2189 each second. 2191 The clock adjust process includes a timer interrupt facility driving 2192 the seconds counter c.t. It begins at zero when the service starts 2193 and increments once each second. At each interrupt the 2194 clock_adjust() routine is called to incorporate the clock discipline 2195 time and frequency adjustments, then the associations are scanned to 2196 determine if the seconds counter equals or exceeds the p.next state 2197 variable defined in the next section. If so, the poll process is 2198 called to send a packet and compute the next p.next value. 2200 An example of the clock adjustment process is shown by the 2201 clock_adjust() routine in Appendix A.5.6.1. 2203 13. Poll Process 2205 Each association supports a poll process that runs at regular 2206 intervals to construct and send packets in symmetric, client and 2207 broadcast server associations. It runs continuously, whether or not 2208 servers are reachable in order to manage the clock filter and reach 2209 register. 2211 13.1. Poll Process Variables 2213 Figure 29 summarizes the common names, formula names and a short 2214 description of the poll process variables(lower case) and parameters 2215 (upper case). Unless noted otherwise, all variables have assumed 2216 prefix p. 2218 +---------+---------+--------------------+ 2219 | Name | Formula | Description | 2220 +---------+---------+--------------------+ 2221 | hpoll | hpoll | host poll exponent | 2222 | last | last | last poll time | 2223 | next | next | next poll time | 2224 | reach | reach | reach register | 2225 | unreach | unreach | unreach counter | 2226 | UNREACH | 24 | unreach limit | 2227 | BCOUNT | 8 | burst count | 2228 | BURST | flag | burst enable | 2229 | IBURST | flag | iburst enable | 2230 +---------+---------+--------------------+ 2232 Figure 29: Poll Process Variables and Parameters 2234 The poll process variables are allocated in the association data 2235 structure along with the peer process variables. Following is a 2236 detailed description of the variables. The parameters will be called 2237 out in the following text. 2239 hpoll: signed integer representing the poll exponent, in log2 seconds 2241 last: integer representing the seconds counter when the most recent 2242 packet was sent 2244 next: integer representing the seconds counter when the next packet 2245 is to be sent 2247 reach: 8-bit integer shift register shared by the peer and poll 2248 processes 2250 unreach: integer representing the number of seconds the server has 2251 been unreachable 2253 13.2. Poll Process Operations 2255 As described previously, once each second the clock adjust process is 2256 called. This routine calls the poll routine for each association in 2257 turn. If the time for the next poll message is greater than the 2258 seconds counter, the routine returns immediately. Symmetric (modes 2259 1, 2), client (mode 3) and broadcast server (mode 5) associations 2260 routinely send packets. A broadcast client (mode 6) association runs 2261 the routine to update the reach and unreach variables, but does not 2262 send packets. The poll process calls the transmit process to send a 2263 packet. If in a burst (burst > 0), nothing further is done except 2264 call the poll update routine to set the next poll interval. 2266 If not in a burst, the reach variable is shifted left by one bit, 2267 with zero replacing the rightmost bit. If the server has not been 2268 heard for the last three poll intervals, the clock filter routine is 2269 called to increase the dispersion. An example is shown in 2270 Appendix A.5.7.3. 2272 If the BURST flag is lit and the server is reachable and a valid 2273 source of synchronization is available, the client sends a burst of 2274 BCOUNT (8) packets at each poll interval. The interval between 2275 packets in the burst is two seconds. This is useful to accurately 2276 measure jitter with long poll intervals. If the IBURST flag is lit 2277 and this is the first packet sent when the server has been 2278 unreachable, the client sends a burst. This is useful to quickly 2279 reduce the synchronization distance below the distance threshold and 2280 synchronize the clock. 2282 If the P_MANY flag is lit in the p.flags word of the association, 2283 this is a manycast client association. Manycast client associations 2284 send client mode packets to designated multicast group addresses at 2285 MINPOLL intervals. The association starts out with a TTL of 1. If 2286 by the time of the next poll there are fewer than MINCLOCK servers 2287 have been mobilized, the ttl is increased by one. If the ttl reaches 2288 the limit TTLMAX, without finding MINCLOCK servers, the poll interval 2289 increases until reaching BEACON, when it starts over from the 2290 beginning. 2292 The poll() routine includes a feature that backs off the poll 2293 interval if the server becomes unreachable. If reach is nonzero, the 2294 server is reachable and unreach is set to zero; otherwise, unreach is 2295 incremented by one for each poll to the maximum UNREACH. Thereafter 2296 for each poll hpoll is increased by one, which doubles the poll 2297 interval up to the maximum MAXPOLL determined by the poll_update() 2298 routine. When the server again becomes reachable, unreach is set to 2299 zero, hpoll is reset to the tc system variable and operation resumes 2300 normally. 2302 A packet is sent by the transmit process. Some header values are 2303 copied from the peer variables left by a previous packet and others 2304 from the system variables. Figure 30 shows which values are copied 2305 to each header field. In those implementations using floating double 2306 data types for root delay and root dispersion, these must be 2307 converted to NTP short format. All other fields are either copied 2308 intact from peer and system variables or struck as a timestamp from 2309 the system clock. 2311 +-----------------------------------+ 2312 | Packet Variable <-- Variable | 2313 +-----------------------------------+ 2314 | x.leap <-- s.leap | 2315 | x.version <-- s.version | 2316 | x.mode <-- s.mode | 2317 | x.stratum <-- s.stratum | 2318 | x.poll <-- s.poll | 2319 | x.precision <-- s.precision | 2320 | x.rootdelay <-- s.rootdelay | 2321 | x.rootdisp <-- s.rootdisp | 2322 | x.refid <-- s.refid | 2323 | x.reftime <-- s.reftime | 2324 | x.org <-- p.xmt | 2325 | x.rec <-- p.dst | 2326 | x.xmt <-- clock | 2327 | x.keyid <-- p.keyid | 2328 | x.digest <-- md5 digest | 2329 +-----------------------------------+ 2331 Figure 30: xmit_packet Packet Header 2333 The poll update routine is called when a valid packet is received and 2334 immediately after a poll message has been sent. If in a burst, the 2335 poll interval is fixed at 2 s; otherwise, the host poll exponent 2336 hpoll is set to the minimum of ppoll from the last packet received 2337 and hpoll from the poll routine, but not less than MINPOLL nor 2338 greater than MAXPOLL. Thus the clock discipline can be oversampled, 2339 but not undersampled. This is necessary to preserve subnet dynamic 2340 behavior and protect against protocol errors. 2342 The poll exponent is converted to an interval which when added to the 2343 last poll time variable determines the value of the next poll time 2344 variable. Finally, the last poll time variable is set to the current 2345 seconds counter. 2347 14. Simple Network Time Protocol (SNTP) 2349 Primary servers and clients complying with a subset of NTP, called 2350 the Simple Network Time Protocol (SNTPv4) [RFC4330], do not need to 2351 implement the mitigation algorithms described in Section 9 and 2352 following sections. SNTP is intended for primary servers equipped 2353 with a single reference clock, as well as for clients with a single 2354 upstream server and no dependent clients. The fully developed NTPv4 2355 implementation is intended for secondary servers with multiple 2356 upstream servers and multiple downstream servers or clients. Other 2357 than these considerations, NTP and SNTP servers and clients are 2358 completely interoperable and can be intermixed in NTP subnets. 2360 An SNTP primary server implementing the on-wire protocol described in 2361 Section 8 has no upstream servers except a single reference clock. 2362 In principle, it is indistinguishable from an NTP primary server that 2363 has the mitigation algorithms and therefore capable of mitigating 2364 between multiple reference clocks. 2366 Upon receiving a client request, an SNTP primary server constructs 2367 and sends the reply packet as described in Figure 31. Note that the 2368 dispersion field in the packet header must be updated as described in 2369 Section 5. 2371 +-----------------------------------+ 2372 | Packet Variable <-- Variable | 2373 +-----------------------------------+ 2374 | x.leap <-- s.leap | 2375 | x.version <-- r.version | 2376 | x.mode <-- 4 | 2377 | x.stratum <-- s.stratum | 2378 | x.poll <-- r.poll | 2379 | x.precision <-- s.precision | 2380 | x.rootdelay <-- s.rootdelay | 2381 | x.rootdisp <-- s.rootdisp | 2382 | x.refid <-- s.refid | 2383 | x.reftime <-- s.reftime | 2384 | x.org <-- r.xmt | 2385 | x.rec <-- r.dst | 2386 | x.xmt <-- clock | 2387 | x.keyid <-- r.keyid | 2388 | x.digest <-- md5 digest | 2389 +-----------------------------------+ 2391 Figure 31: fast_xmit Packet Header 2393 A SNTP client implementing the on-wire protocol has a single server 2394 and no dependent clients. It can operate with any subset of the NTP 2395 on-wire protocol, the simplest approach using only the transmit 2396 timestamp of the server packet and ignoring all other fields. 2397 However, the additional complexity to implement the full on-wire 2398 protocol is minimal so that a full implementation is encouraged. 2400 15. Security Considerations 2402 NTP security requirements are even more stringent than most other 2403 distributed services. First, the operation of the authentication 2404 mechanism and the time synchronization mechanism are inextricably 2405 intertwined. Reliable time synchronization requires cryptographic 2406 keys which are valid only over a designated time interval; but, time 2407 intervals can be enforced only when participating servers and clients 2408 are reliably synchronized to UTC. In addition, the NTP subnet is 2409 hierarchical by nature, so time and trust flow from the primary 2410 servers at the root through secondary servers to the clients at the 2411 leaves. 2413 An NTP client can claim to have authentic time to dependent 2414 applications only if all servers on the path to the primary servers 2415 are authenticated. In NTP each server authenticates the next lower 2416 stratum servers and authenticates by induction the lowest stratum 2417 (primary) servers. It is important to note that authentication in 2418 the context of NTP does not necessarily imply the time is correct. A 2419 NTP client mobilizes a number of concurrent associations with 2420 different servers and uses a crafted agreement algorithm to pluck 2421 truechimers from the population possibly including falsetickers. 2423 The NTP specification assumes the goal of the intruder is to inject 2424 false time values, disrupt the protocol or clog the network, servers 2425 or clients with spurious packets that exhaust resources and deny 2426 service to legitimate applications. There are a number of defense 2427 mechanisms already built in the NTP architecture, protocol and 2428 algorithms. The on-wire timestamp exchange scheme is inherently 2429 resistant to spoofing, packet loss and replay attacks. The 2430 engineered clock filter, selection and clustering algorithms are 2431 designed to defend against evil cliques of Byzantine traitors. While 2432 not necessarily designed to defeat determined intruders, these 2433 algorithms and accompanying sanity checks have functioned well over 2434 the years to deflect improperly operating but presumably friendly 2435 scenarios. However, these mechanisms do not securely identify and 2436 authenticate servers to clients. Without specific further 2437 protection, an intruder can inject any or all of the following 2438 attacks: 2440 1. An intruder can intercept and archive packets forever, as well as 2441 all the public values ever generated and transmitted over the 2442 net. 2444 2. An intruder can generate packets faster than the server, network 2445 or client can process them, especially if they require expensive 2446 cryptographic computations. 2448 3. In a wiretap attack the intruder can intercept, modify and replay 2449 a packet. However, it cannot permanently prevent onward 2450 transmission of the original packet; that is, it cannot break the 2451 wire, only tell lies and congest it. Generally, the modified 2452 packet cannot arrive at the victim before the original packet, 2453 nor does it have the server private keys or identity parameters. 2455 4. In a middleman or masquerade attack the intruder is positioned 2456 between the server and client, so it can intercept, modify and 2457 replay a packet and prevent onward transmission of the original 2458 packet. However, the middleman does not have the server private 2459 keys. 2461 The NTP security model assumes the following possible limitations: 2463 1. The running times for public key algorithms are relatively long 2464 and highly variable. In general, the performance of the time 2465 synchronization function is badly degraded if these algorithms 2466 must be used for every NTP packet. 2468 2. In some modes of operation it is not feasible for a server to 2469 retain state variables for every client. It is however feasible 2470 to regenerated them for a client upon arrival of a packet from 2471 that client. 2473 3. The lifetime of cryptographic values must be enforced, which 2474 requires a reliable system clock. However, the sources that 2475 synchronize the system clock must be trusted. This circular 2476 interdependence of the timekeeping and authentication functions 2477 requires special handling. 2479 4. Client security functions must involve only public values 2480 transmitted over the net. Private values must never be disclosed 2481 beyond the machine on which they were created, except in the case 2482 of a special trusted agent (TA) assigned for this purpose. 2484 Unlike the Secure Shell (SSH) security model, where the client must 2485 be securely authenticated to the server, in NTP the server must be 2486 securely authenticated to the client. In SSH each different 2487 interface address can be bound to a different name, as returned by a 2488 reverse-DNS query. In this design separate public/private key pairs 2489 may be required for each interface address with a distinct name. A 2490 perceived advantage of this design is that the security compartment 2491 can be different for each interface. This allows a firewall, for 2492 instance, to require some interfaces to authenticate the client and 2493 others not. 2495 In the case of NTP as specified herein, NTP broadcast clients are 2496 vulnerable to disruption by misbehaving or hostile SNTP or NTP 2497 broadcast servers elsewhere in the Internet. Such disruption can be 2498 minimized by several approaches. Filtering can be employed to limit 2499 the access of NTP clients to known or trusted NTP broadcast servers. 2500 Such filtering will prevent malicious traffic from reaching the NTP 2501 clients. Cryptographic authentication at the client will only allow 2502 timing information from properly signed NTP messages to be utilized 2503 in synchronzing its clock. Higher levels of authentication may be 2504 gained by the use of the Autokey mechanism[I-D.ietf-ntp-autokey]. 2506 Section 8 describes a potential security concern with the replay of 2507 client requests. Following the recommendations in that section 2508 provides protection against such attacks. 2510 It should be noted that this specification is describing an existing 2511 implementation. While the security shortfalls of the MD5 algorithm 2512 are well-known, its use in the NTP specification is consistent with 2513 widescale deployment in the Internet community. 2515 16. IANA Considerations 2517 UDP/TCP Port 123 was previously assigned by IANA for this protocol. 2518 The IANA has assigned the IPv4 multicast group address 224.0.1.1 and 2519 the IPv6 multicast address ending :101 for NTP. This document 2520 introduces NTP extension fields allowing for the development of 2521 future extensions to the protocol, where a particular extension is to 2522 be identified by the Field Type sub-field within the extension field. 2523 IANA is requested to establish and maintain a registry for Extension 2524 Field Types associated with this protocol, populating this registry 2525 with no initial entries. As future needs arise, new Extension Field 2526 Types may be defined. Following the policies outlined in [RFC5226], 2527 new values are to be defined by IETF Review. 2529 The IANA is requested to create a new registry for NTP Reference 2530 Identifier codes. This should include the current codes defined in 2531 Section 7.3, and may be extended on a First-Come-First-Serve (FCFS) 2532 basis. The format of the registry is: 2534 +------+----------------------------------------------------------+ 2535 | ID | Clock Source | 2536 +------+----------------------------------------------------------+ 2537 | GOES | Geosynchronous Orbit Environment Satellite | 2538 | GPS | Global Position System | 2539 | ... | ... | 2540 +------+----------------------------------------------------------+ 2542 Figure 32: Reference Identifier Codes 2544 The IANA is requested to create a new registry for NTP Kiss-o'-Death 2545 codes. This should include the current codes defined in Section 7.4, 2546 and may be extended on a FCFS basis. The format of the registry is: 2548 +------+------------------------------------------------------------+ 2549 | Code | Meaning | 2550 +------+------------------------------------------------------------+ 2551 | ACST | The association belongs to a unicast server | 2552 | AUTH | Server authentication failed | 2553 | ... | ... | 2554 +------+------------------------------------------------------------+ 2556 Figure 33: Kiss Codes 2558 For both Reference Identifiers and Kiss-o'-Death codes, IANA is 2559 requested to never assign a code beginning with the character "X", as 2560 this is reserved for experimentation and development. 2562 17. Acknowledgements 2564 The editors would like to thank Karen O'Donoghue, Brian Haberman, 2565 Greg Dowd, Mark Elliot, Harlan Stenn, Yaakov Stein, Stewart Bryant, 2566 and Danny Mayer for technical reviews and specific text contributions 2567 to this document. 2569 18. References 2571 18.1. Normative References 2573 [RFC0768] Postel, J., "User Datagram Protocol", STD 6, RFC 768, 2574 August 1980. 2576 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 2577 September 1981. 2579 [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, 2580 RFC 793, September 1981. 2582 [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 2583 April 1992. 2585 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2586 Requirement Levels", BCP 14, RFC 2119, March 1997. 2588 18.2. Informative References 2590 [CGPM] Bureau International des Poids et Mesures, "Comptes Rendus 2591 de la 15e CGPM", 1976. 2593 [I-D.ietf-ntp-autokey] 2594 Haberman, B. and D. Mills, "Network Time Protocol Version 2595 4 Autokey Specification", draft-ietf-ntp-autokey-06 (work 2596 in progress), July 2009. 2598 [ITU-R_TF.460] 2599 International Telecommunications Union, "ITU-R TF.460 2600 Standard-frequency and time-signal emissions", 2601 February 2002. 2603 [RFC1305] Mills, D., "Network Time Protocol (Version 3) 2604 Specification, Implementation", RFC 1305, March 1992. 2606 [RFC1345] Simonsen, K., "Character Mnemonics and Character Sets", 2607 RFC 1345, June 1992. 2609 [RFC4330] Mills, D., "Simple Network Time Protocol (SNTP) Version 4 2610 for IPv4, IPv6 and OSI", RFC 4330, January 2006. 2612 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 2613 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 2614 May 2008. 2616 [ref6] Marzullo and S. Owicki, "Maintaining the time in a 2617 distributed system.", ACM Operating Systems Review 19 , 2618 July 1985. 2620 [ref7] Mills, D.L., "Computer Network Time Synchronization - the 2621 Network Time Protocol. CRC Press, 304pp.", 2006. 2623 [ref9] Mills, D.L., Electrical and Computer Engineering Technical 2624 Report 06-6-1, NDSS, June 2006., "Network Time Protocol 2625 Version 4 Reference and Implementation Guide.", 2006. 2627 Appendix A. Code Skeleton 2629 This appendix is intended to describe the protocol and algorithms of 2630 an implementation in a general way using what is called a code 2631 skeleton program. This consists of a set of definitions, structures 2632 and code fragments which illustrate the protocol operations without 2633 the complexities of an actual implementation of the protocol. This 2634 program is not an executable and is not designed to run in the 2635 ordinary sense. 2637 Most of the features of the reference implementation are included 2638 here, with the following exceptions: There are no provisions for 2639 reference clocks or public key (Autokey) cryptography. There is no 2640 huff-n'-puff filter, anti-clockhop hysteresis or monitoring 2641 provisions. Many of the values that can be tinkered in the reference 2642 implementation are assumed constants here. There are only minimal 2643 provisions for the kiss-o'death packet and no responding code. 2645 The program is not intended to be fast or compact, just to 2646 demonstrate the algorithms with sufficient fidelity to understand how 2647 they work. The code skeleton consists of eight segments, a header 2648 segment included by each of the other segments, plus a code segment 2649 for the main program, kernel I/O and system clock interfaces, and 2650 peer, system, clock_adjust and poll processes. These are presented 2651 in order below along with definitions and variables specific to each 2652 process. 2654 A.1. Global Definitions 2656 A.1.1. Definitions, Constants, Parameters 2658 #include /* avoids complaints about sqrt() */ 2659 #include /* for gettimeofday() and friends */ 2660 #include /* for malloc() and friends */ 2661 #include /* for memset() */ 2663 /* 2664 * Data types 2665 * 2666 * This program assumes the int data type is 32 bits and the long data 2667 * type is 64 bits. The native data type used in most calculations is 2668 * floating double. The data types used in some packet header fields 2669 * require conversion to and from this representation. Some header 2670 * fields involve partitioning an octet, here represented by individual 2671 * octets. 2672 * 2673 * The 64-bit NTP timestamp format used in timestamp calculations is 2674 * unsigned seconds and fraction with the decimal point to the left of 2675 * bit 32. The only operation permitted with these values is 2676 * subtraction, yielding a signed 31-bit difference. The 32-bit NTP 2677 * short format used in delay and dispersion calculations is seconds and 2678 * fraction with the decimal point to the left of bit 16. The only 2679 * operations permitted with these values are addition and 2680 * multiplication by a constant. 2681 * 2682 * The IPv4 address is 32 bits, while the IPv6 address is 128 bits. The 2683 * message digest field is 128 bits as constructed by the MD5 algorithm. 2684 * The precision and poll interval fields are signed log2 seconds. 2685 */ 2686 typedef unsigned long long tstamp; /* NTP timestamp format */ 2687 typedef unsigned int tdist; /* NTP short format */ 2688 typedef unsigned long ipaddr; /* IPv4 or IPv6 address */ 2689 typedef unsigned long digest; /* md5 digest */ 2690 typedef signed char s_char; /* precision and poll interval (log2) */ 2692 /* 2693 * Timestamp conversion macroni 2694 */ 2695 #define FRIC 65536. /* 2^16 as a double */ 2696 #define D2FP(r) ((tdist)((r) * FRIC)) /* NTP short */ 2697 #define FP2D(r) ((double)(r) / FRIC) 2699 #define FRAC 4294967296. /* 2^32 as a double */ 2700 #define D2LFP(a) ((tstamp)((a) * FRAC)) /* NTP timestamp */ 2701 #define LFP2D(a) ((double)(a) / FRAC) 2702 #define U2LFP(a) ((a).tv_sec + JAN_1970 << 32 + (unsigned long long) \ 2703 ((a).tv_usec / 1e6 * FRAC)) 2705 /* 2706 * Arithmetic conversions 2707 */ 2708 #define LOG2D(a) ((a) < 0 ? 1. / (1L << -(a)) : \ 2709 1L << (a)) /* poll, etc. */ 2710 #define SQUARE(x) (x * x) 2711 #define SQRT(x) (sqrt(x)) 2713 /* 2714 * Global constants. Some of these might be converted to variables 2715 * which can be tinkered by configuration or computed on-fly. For 2716 * instance, the reference implementation computes PRECISION on-fly and 2717 * provides performance tuning for the defines marked with % below. 2718 */ 2719 #define VERSION 4 /* version number */ 2720 #define MINDISP .01 /* % minimum dispersion (s) */ 2721 #define MAXDISP 16 /* maximum dispersion (s) */ 2722 #define MAXDIST 1 /* % distance threshold (s) */ 2723 #define NOSYNC 0x3 /* leap unsync */ 2724 #define MAXSTRAT 16 /* maximum stratum (infinity metric) */ 2725 #define MINPOLL 6 /* % minimum poll interval (64 s)*/ 2726 #define MAXPOLL 17 /* % maximum poll interval (36.4 h) */ 2727 #define MINCLOCK 3 /* minimum manycast survivors */ 2728 #define MAXCLOCK 10 /* maximum manycast candidates */ 2729 #define TTLMAX 8 /* max ttl manycast */ 2730 #define BEACON 15 /* max interval between beacons */ 2732 #define PHI 15e-6 /* % frequency tolerance (15 PPM) */ 2733 #define NSTAGE 8 /* clock register stages */ 2734 #define NMAX 50 /* maximum number of peers */ 2735 #define NSANE 1 /* % minimum intersection survivors */ 2736 #define NMIN 3 /* % minimum cluster survivors */ 2737 /* 2738 * Global return values 2739 */ 2740 #define TRUE 1 /* boolean true */ 2741 #define FALSE 0 /* boolean false */ 2743 /* 2744 * Local clock process return codes 2745 */ 2746 #define IGNORE 0 /* ignore */ 2747 #define SLEW 1 /* slew adjustment */ 2748 #define STEP 2 /* step adjustment */ 2749 #define PANIC 3 /* panic - no adjustment */ 2751 /* 2752 * System flags 2753 */ 2754 #define S_FLAGS 0 /* any system flags */ 2755 #define S_BCSTENAB 0x1 /* enable broadcast client */ 2757 /* 2758 * Peer flags 2759 */ 2760 #define P_FLAGS 0 /* any peer flags */ 2761 #define P_EPHEM 0x01 /* association is ephemeral */ 2762 #define P_BURST 0x02 /* burst enable */ 2763 #define P_IBURST 0x04 /* intial burst enable */ 2764 #define P_NOTRUST 0x08 /* authenticated access */ 2765 #define P_NOPEER 0x10 /* authenticated mobilization */ 2766 #define P_MANY 0x20 /* manycast client */ 2768 /* 2769 * Authentication codes 2770 */ 2771 #define A_NONE 0 /* no authentication */ 2772 #define A_OK 1 /* authentication OK */ 2773 #define A_ERROR 2 /* authentication error */ 2774 #define A_CRYPTO 3 /* crypto-NAK */ 2776 /* 2777 * Association state codes 2778 */ 2779 #define X_INIT 0 /* initialization */ 2780 #define X_STALE 1 /* timeout */ 2781 #define X_STEP 2 /* time step */ 2782 #define X_ERROR 3 /* authentication error */ 2783 #define X_CRYPTO 4 /* crypto-NAK received */ 2784 #define X_NKEY 5 /* untrusted key */ 2785 /* 2786 * Protocol mode definitionss 2787 */ 2788 #define M_RSVD 0 /* reserved */ 2789 #define M_SACT 1 /* symmetric active */ 2790 #define M_PASV 2 /* symmetric passive */ 2791 #define M_CLNT 3 /* client */ 2792 #define M_SERV 4 /* server */ 2793 #define M_BCST 5 /* broadcast server */ 2794 #define M_BCLN 6 /* broadcast client */ 2796 /* 2797 * Clock state definitions 2798 */ 2799 #define NSET 0 /* clock never set */ 2800 #define FSET 1 /* frequency set from file */ 2801 #define SPIK 2 /* spike detected */ 2802 #define FREQ 3 /* frequency mode */ 2803 #define SYNC 4 /* clock synchronized */ 2805 #define min(a, b) ((a) < (b) ? (a) : (b)) 2806 #define max(a, b) ((a) < (b) ? (b) : (a)) 2808 A.1.2. Packet Data Structures 2810 /* 2811 * The receive and transmit packets may contain an optional message 2812 * authentication code (MAC) consisting of a key identifier (keyid) and 2813 * message digest (mac). NTPv4 supports optional extension fields which 2814 * are inserted after the the header and before the MAC, but these are 2815 * not described here. 2816 * 2817 * Receive packet 2818 * 2819 * Note the dst timestamp is not part of the packet itself. It is 2820 * captured upon arrival and returned in the receive buffer along with 2821 * the buffer length and data. Note that some of the char fields are 2822 * packed in the actual header, but the details are omitted here. 2823 */ 2824 struct r { 2825 ipaddr srcaddr; /* source (remote) address */ 2826 ipaddr dstaddr; /* destination (local) address */ 2827 char version; /* version number */ 2828 char leap; /* leap indicator */ 2829 char mode; /* mode */ 2830 char stratum; /* stratum */ 2831 char poll; /* poll interval */ 2832 s_char precision; /* precision */ 2833 tdist rootdelay; /* root delay */ 2834 tdist rootdisp; /* root dispersion */ 2835 char refid; /* reference ID */ 2836 tstamp reftime; /* reference time */ 2837 tstamp org; /* origin timestamp */ 2838 tstamp rec; /* receive timestamp */ 2839 tstamp xmt; /* transmit timestamp */ 2840 int keyid; /* key ID */ 2841 digest dgst; /* message digest */ 2842 tstamp dst; /* destination timestamp */ 2843 } r; 2845 /* 2846 * Transmit packet 2847 */ 2848 struct x { 2849 ipaddr dstaddr; /* source (local) address */ 2850 ipaddr srcaddr; /* destination (remote) address */ 2851 char version; /* version number */ 2852 char leap; /* leap indicator */ 2853 char mode; /* mode */ 2854 char stratum; /* stratum */ 2855 char poll; /* poll interval */ 2856 s_char precision; /* precision */ 2857 tdist rootdelay; /* root delay */ 2858 tdist rootdisp; /* root dispersion */ 2859 char refid; /* reference ID */ 2860 tstamp reftime; /* reference time */ 2861 tstamp org; /* origin timestamp */ 2862 tstamp rec; /* receive timestamp */ 2863 tstamp xmt; /* transmit timestamp */ 2864 int keyid; /* key ID */ 2865 digest dgst; /* message digest */ 2866 } x; 2868 A.1.3. Association Data Structures 2870 /* 2871 * Filter stage structure. Note the t member in this and other 2872 * structures refers to process time, not real time. Process time 2873 * increments by one second for every elapsed second of real time. 2874 */ 2875 struct f { 2876 tstamp t; /* update time */ 2877 double offset; /* clock ofset */ 2878 double delay; /* roundtrip delay */ 2879 double disp; /* dispersion */ 2880 } f; 2881 /* 2882 * Association structure. This is shared between the peer process and 2883 * poll process. 2884 */ 2885 struct p { 2887 /* 2888 * Variables set by configuration 2889 */ 2890 ipaddr srcaddr; /* source (remote) address */ 2891 ipaddr dstaddr; /* destination (local) address */ 2892 char version; /* version number */ 2893 char hmode; /* host mode */ 2894 int keyid; /* key identifier */ 2895 int flags; /* option flags */ 2897 /* 2898 * Variables set by received packet 2899 */ 2900 char leap; /* leap indicator */ 2901 char pmode; /* peer mode */ 2902 char stratum; /* stratum */ 2903 char ppoll; /* peer poll interval */ 2904 double rootdelay; /* root delay */ 2905 double rootdisp; /* root dispersion */ 2906 char refid; /* reference ID */ 2907 tstamp reftime; /* reference time */ 2908 #define begin_clear org /* beginning of clear area */ 2909 tstamp org; /* originate timestamp */ 2910 tstamp rec; /* receive timestamp */ 2911 tstamp xmt; /* transmit timestamp */ 2913 /* 2914 * Computed data 2915 */ 2916 double t; /* update time */ 2917 struct f f[NSTAGE]; /* clock filter */ 2918 double offset; /* peer offset */ 2919 double delay; /* peer delay */ 2920 double disp; /* peer dispersion */ 2921 double jitter; /* RMS jitter */ 2923 /* 2924 * Poll process variables 2925 */ 2926 char hpoll; /* host poll interval */ 2927 int burst; /* burst counter */ 2928 int reach; /* reach register */ 2929 int ttl; /* ttl (manycast) */ 2930 #define end_clear unreach /* end of clear area */ 2931 int unreach; /* unreach counter */ 2932 int outdate; /* last poll time */ 2933 int nextdate; /* next poll time */ 2934 } p; 2936 A.1.4. System Data Structures 2938 /* 2939 * Chime list. This is used by the intersection algorithm. 2940 */ 2941 struct m { /* m is for Marzullo */ 2942 struct p *p; /* peer structure pointer */ 2943 int type; /* high +1, mid 0, low -1 */ 2944 double edge; /* correctness interval edge */ 2945 } m; 2947 /* 2948 * Survivor list. This is used by the clustering algorithm. 2949 */ 2950 struct v { 2951 struct p *p; /* peer structure pointer */ 2952 double metric; /* sort metric */ 2953 } v; 2955 /* 2956 * System structure 2957 */ 2958 struct s { 2959 tstamp t; /* update time */ 2960 char leap; /* leap indicator */ 2961 char stratum; /* stratum */ 2962 char poll; /* poll interval */ 2963 char precision; /* precision */ 2964 double rootdelay; /* root delay */ 2965 double rootdisp; /* root dispersion */ 2966 char refid; /* reference ID */ 2967 tstamp reftime; /* reference time */ 2968 struct m m[NMAX]; /* chime list */ 2969 struct v v[NMAX]; /* survivor list */ 2970 struct p *p; /* association ID */ 2971 double offset; /* combined offset */ 2972 double jitter; /* combined jitter */ 2973 int flags; /* option flags */ 2974 int n; /* number of survivors */ 2975 } s; 2977 A.1.5. Local Clock Data Structures 2979 /* 2980 * Local clock structure 2981 */ 2982 struct c { 2983 tstamp t; /* update time */ 2984 int state; /* current state */ 2985 double offset; /* current offset */ 2986 double last; /* previous offset */ 2987 int count; /* jiggle counter */ 2988 double freq; /* frequency */ 2989 double jitter; /* RMS jitter */ 2990 double wander; /* RMS wander */ 2991 } c; 2993 A.1.6. Function Prototypes 2995 /* 2996 * Peer process 2997 */ 2998 void receive(struct r *); /* receive packet */ 2999 void packet(struct p *, struct r *); /* process packet */ 3000 void clock_filter(struct p *, double, double, double); /* filter */ 3001 double root_dist(struct p *); /* calculate root distance */ 3002 int fit(struct p *); /* determine fitness of server */ 3003 void clear(struct p *, int); /* clear association */ 3004 int access(struct r *); /* determine access restrictions */ 3006 /* 3007 * System process 3008 */ 3009 int main(); /* main program */ 3010 void clock_select(); /* find the best clocks */ 3011 void clock_update(struct p *); /* update the system clock */ 3012 void clock_combine(); /* combine the offsets */ 3014 /* 3015 * Local clock process 3016 */ 3017 int local_clock(struct p *, double); /* clock discipline */ 3018 void rstclock(int, double, double); /* clock state transition */ 3020 /* 3021 * Clock adjust process 3022 */ 3023 void clock_adjust(); /* one-second timer process */ 3024 /* 3025 * Poll process 3026 */ 3027 void poll(struct p *); /* poll process */ 3028 void poll_update(struct p *, int); /* update the poll interval */ 3029 void peer_xmit(struct p *); /* transmit a packet */ 3030 void fast_xmit(struct r *, int, int); /* transmit a reply packet */ 3032 /* 3033 * Utility routines 3034 */ 3035 digest md5(int); /* generate a message digest */ 3036 struct p *mobilize(ipaddr, ipaddr, int, int, int, int); /* mobilize */ 3037 struct p *find_assoc(struct r *); /* search the association table */ 3039 /* 3040 * Kernel interface 3041 */ 3042 struct r *recv_packet(); /* wait for packet */ 3043 void xmit_packet(struct x *); /* send packet */ 3044 void step_time(double); /* step time */ 3045 void adjust_time(double); /* adjust (slew) time */ 3046 tstamp get_time(); /* read time */ 3048 A.2. Main Program and Utility Routines 3050 /* 3051 * Definitions 3052 */ 3053 #define PRECISION -18 /* precision (log2 s) */ 3054 #define IPADDR 0 /* any IP address */ 3055 #define MODE 0 /* any NTP mode */ 3056 #define KEYID 0 /* any key identifier */ 3058 /* 3059 * main() - main program 3060 */ 3061 int 3062 main() 3063 { 3064 struct p *p; /* peer structure pointer */ 3065 struct r *r; /* receive packet pointer */ 3067 /* 3068 * Read command line options and initialize system variables. 3069 * The reference implementation measures the precision specific 3070 * to each machine by measuring the clock increments to read the 3071 * system clock. 3073 */ 3074 memset(&s, sizeof(s), 0); 3075 s.leap = NOSYNC; 3076 s.stratum = MAXSTRAT; 3077 s.poll = MINPOLL; 3078 s.precision = PRECISION; 3079 s.p = NULL; 3081 /* 3082 * Initialize local clock variables 3083 */ 3084 memset(&c, sizeof(c), 0); 3085 if (/* frequency file */ 0) { 3086 c.freq = /* freq */ 0; 3087 rstclock(FSET, 0, 0); 3088 } else { 3089 rstclock(NSET, 0, 0); 3090 } 3091 c.jitter = LOG2D(s.precision); 3093 /* 3094 * Read the configuration file and mobilize persistent 3095 * associations with specified addresses, version, mode, key ID 3096 * and flags. 3097 */ 3098 while (/* mobilize configurated associations */ 0) { 3099 p = mobilize(IPADDR, IPADDR, VERSION, MODE, KEYID, 3100 P_FLAGS); 3101 } 3103 /* 3104 * Start the system timer, which ticks once per second. Then 3105 * read packets as they arrive, strike receive timestamp and 3106 * call the receive() routine. 3107 */ 3108 while (0) { 3109 r = recv_packet(); 3110 r->dst = get_time(); 3111 receive(r); 3112 } 3113 } 3115 /* 3116 * mobilize() - mobilize and initialize an association 3117 */ 3118 struct p 3119 *mobilize( 3120 ipaddr srcaddr, /* IP source address */ 3121 ipaddr dstaddr, /* IP destination address */ 3122 int version, /* version */ 3123 int mode, /* host mode */ 3124 int keyid, /* key identifier */ 3125 int flags /* peer flags */ 3126 ) 3127 { 3128 struct p *p; /* peer process pointer */ 3130 /* 3131 * Allocate and initialize association memory 3132 */ 3133 p = malloc(sizeof(struct p)); 3134 p->srcaddr = srcaddr; 3135 p->dstaddr = dstaddr; 3136 p->version = version; 3137 p->hmode = mode; 3138 p->keyid = keyid; 3139 p->hpoll = MINPOLL; 3140 clear(p, X_INIT); 3141 p->flags == flags; 3142 return (p); 3143 } 3145 /* 3146 * find_assoc() - find a matching association 3147 */ 3148 struct p /* peer structure pointer or NULL */ 3149 *find_assoc( 3150 struct r *r /* receive packet pointer */ 3151 ) 3152 { 3153 struct p *p; /* dummy peer structure pointer */ 3155 /* 3156 * Search association table for matching source 3157 * address, source port and mode. 3158 */ 3159 while (/* all associations */ 0) { 3160 if (r->srcaddr == p->srcaddr && r->mode == p->hmode) 3161 return(p); 3162 } 3163 return (NULL); 3164 } 3166 /* 3167 * md5() - compute message digest 3168 */ 3170 digest 3171 md5( 3172 int keyid /* key identifier */ 3173 ) 3174 { 3175 /* 3176 * Compute a keyed cryptographic message digest. The key 3177 * identifier is associated with a key in the local key cache. 3178 * The key is prepended to the packet header and extension fields 3179 * and the result hashed by the MD5 algorithm as described in 3180 * RFC-1321. Return a MAC consisting of the 32-bit key ID 3181 * concatenated with the 128-bit digest. 3182 */ 3183 return (/* MD5 digest */ 0); 3184 } 3186 A.3. Kernel Input/Output Interface 3188 /* 3189 * Kernel interface to transmit and receive packets. Details are 3190 * deliberately vague and depend on the operating system. 3191 * 3192 * recv_packet - receive packet from network 3193 */ 3194 struct r /* receive packet pointer*/ 3195 *recv_packet() { 3196 return (/* receive packet r */ 0); 3197 } 3199 /* 3200 * xmit_packet - transmit packet to network 3201 */ 3202 void 3203 xmit_packet( 3204 struct x *x /* transmit packet pointer */ 3205 ) 3206 { 3207 /* send packet x */ 3208 } 3210 A.4. Kernel System Clock Interface 3212 /* 3213 * System clock utility functions 3214 * 3215 * There are three time formats: native (Unix), NTP and floating double. 3216 * The get_time() routine returns the time in NTP long format. The Unix 3217 * routines expect arguments as a structure of two signed 32-bit words 3218 * in seconds and microseconds (timeval) or nanoseconds (timespec). The 3219 * step_time() and adjust_time() routines expect signed arguments in 3220 * floating double. The simplified code shown here is for illustration 3221 * only and has not been verified. 3222 */ 3223 #define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */ 3225 /* 3226 * get_time - read system time and convert to NTP format 3227 */ 3228 tstamp 3229 get_time() 3230 { 3231 struct timeval unix_time; 3233 /* 3234 * There are only two calls on this routine in the program. One 3235 * when a packet arrives from the network and the other when a 3236 * packet is placed on the send queue. Call the kernel time of 3237 * day routine (such as gettimeofday()) and convert to NTP 3238 * format. 3239 */ 3240 gettimeofday(&unix_time, NULL); 3241 return (U2LFP(unix_time)); 3242 } 3244 /* 3245 * step_time() - step system time to given offset valuet 3246 */ 3247 void 3248 step_time( 3249 double offset /* clock offset */ 3250 ) 3251 { 3252 struct timeval unix_time; 3253 tstamp ntp_time; 3255 /* 3256 * Convert from double to native format (signed) and add to the 3257 * current time. Note the addition is done in native format to 3258 * avoid overflow or loss of precision. 3259 */ 3260 gettimeofday(&unix_time, NULL); 3261 ntp_time = D2LFP(offset) + U2LFP(unix_time);; 3262 unix_time.tv_sec = ntp_time >> 32; 3263 unix_time.tv_usec = (long)((ntp_time - unix_time.tv_sec << 3264 32) / FRAC * 1e6); 3265 settimeofday(&unix_time, NULL); 3266 } 3268 /* 3269 * adjust_time() - slew system clock to given offset value 3270 */ 3271 void 3272 adjust_time( 3273 double offset /* clock offset */ 3274 ) 3275 { 3276 struct timeval unix_time; 3277 tstamp ntp_time; 3279 /* 3280 * Convert from double to native format (signed) and add to the 3281 * current time. 3282 */ 3283 ntp_time = D2LFP(offset); 3284 unix_time.tv_sec = ntp_time >> 32; 3285 unix_time.tv_usec = (long)((ntp_time - unix_time.tv_sec << 3286 32) / FRAC * 1e6); 3287 adjtime(&unix_time, NULL); 3288 } 3290 A.5. Peer Process 3292 /* 3293 * A crypto-NAK packet includes the NTP header followed by a MAC 3294 * consisting only of the key identifier with value zero. It tells the 3295 * receiver that a prior request could not be properly authenticated, 3296 * but the NTP header fields are correct. 3297 * 3298 * A kiss-o'-death packet is an NTP header with leap 0x3 (NOSYNC) and 3299 * stratum 16 (MAXSTRAT. It tells the receiver that something drastic 3300 * has happened, as revealed by the kiss code in the refid field. The 3301 * NTP header fields may or may not be correct. 3302 */ 3303 /* 3304 * Peer process parameters and constants 3305 */ 3306 #define SGATE 3 /* spike gate (clock filter */ 3307 #define BDELAY .004 /* broadcast delay (s) */ 3309 /* 3310 * Dispatch codes 3311 */ 3312 #define ERR -1 /* error */ 3313 #define DSCRD 0 /* discard packet */ 3314 #define PROC 1 /* process packet */ 3315 #define BCST 2 /* broadcast packet */ 3316 #define FXMIT 3 /* client packet */ 3317 #define MANY 4 /* manycast packet */ 3318 #define NEWPS 5 /* new symmetric passive client */ 3319 #define NEWBC 6 /* new broadcast client */ 3321 /* 3322 * Dispatch matrix 3323 * active passv client server bcast */ 3324 int table[7][5] = { 3325 /* nopeer */ { NEWPS, DSCRD, FXMIT, MANY, NEWBC }, 3326 /* active */ { PROC, PROC, DSCRD, DSCRD, DSCRD }, 3327 /* passv */ { PROC, ERR, DSCRD, DSCRD, DSCRD }, 3328 /* client */ { DSCRD, DSCRD, DSCRD, PROC, DSCRD }, 3329 /* server */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, 3330 /* bcast */ { DSCRD, DSCRD, DSCRD, DSCRD, DSCRD }, 3331 /* bclient */ { DSCRD, DSCRD, DSCRD, DSCRD, PROC} 3332 }; 3334 /* 3335 * Miscellaneous macroni 3336 * 3337 * This macro defines the authentication state. If x is 0, 3338 * authentication is optional, otherwise it is required. 3339 */ 3340 #define AUTH(x, y) ((x) ? (y) == A_OK : (y) == A_OK || \ 3341 (y) == A_NONE) 3343 /* 3344 * These are used by the clear() routine 3345 */ 3346 #define BEGIN_CLEAR(p) ((char *)&((p)->begin_clear)) 3347 #define END_CLEAR(p) ((char *)&((p)->end_clear)) 3348 #define LEN_CLEAR (END_CLEAR((struct p *)0) - \ 3349 BEGIN_CLEAR((struct p *)0)) 3351 A.5.1. receive() 3353 /* 3354 * receive() - receive packet and decode modes 3355 */ 3356 void 3357 receive( 3358 struct r *r /* receive packet pointer */ 3359 ) 3360 { 3361 struct p *p; /* peer structure pointer 3362 int auth; /* authentication code */ 3363 int has_mac; /* size of MAC */ 3364 int synch; /* synchronized switch */ 3365 int auth; /* authentication code */ 3367 /* 3368 * Check access control lists. The intent here is to implement a 3369 * whitelist of those IP addresses specifically accepted and/or 3370 * a blacklist of those IP addresses specifically rejected. 3371 * There could be different lists for authenticated clients and 3372 * unauthenticated clients. 3373 */ 3374 if (!access(r)) 3375 return; /* access denied */ 3377 /* 3378 * The version must not be in the future. Format checks include 3379 * packet length, MAC length and extension field lengths, if 3380 * present. 3381 */ 3382 if (r->version > VERSION /* or format error */) 3383 return; /* format error */ 3385 /* 3386 * Authentication is conditioned by two switches which can be 3387 * specified on a per-client basis. 3388 * 3389 * P_NOPEER do not mobilize an association unless 3390 * authenticated 3391 * P_NOTRUST do not allow access unless authenticated 3392 * (implies P_NOPEER) 3393 * 3394 * There are four outcomes: 3395 * 3396 * A_NONE the packet has no MAC 3397 * A_OK the packet has a MAC and authentication 3398 * succeeds 3399 * A_ERROR the packet has a MAC and authentication fails 3400 * A_CRYPTO crypto-NAK. The MAC has four octets only. 3401 * 3402 * Note: The AUTH(x, y) macro is used to filter outcomes. If x 3403 * is zero, acceptable outcomes of y are NONE and OK. If x is 3404 * one, the only acceptable outcome of y is OK. 3405 */ 3406 has_mac = /* length of MAC field */ 0; 3407 if (has_mac == 0) { 3408 auth = A_NONE; /* not required */ 3409 } else if (has_mac == 4) { 3410 auth == A_CRYPTO; /* crypto-NAK */ 3411 } else { 3412 if (r->mac != md5(r->keyid)) 3413 auth = A_ERROR; /* auth error */ 3414 else 3415 auth = A_OK; /* auth OK */ 3416 } 3418 /* 3419 * Find association and dispatch code. If there is no 3420 * association to match, the value of p->hmode is assumed NULL. 3421 */ 3422 p = find_assoc(r); 3423 switch(table[p->hmode][r->mode]) { 3425 /* 3426 * Client packet and no association. Send server reply without 3427 * saving state. 3428 */ 3429 case FXMIT: 3431 /* 3432 * If unicast destination address, send server packet. 3433 * If authentication fails, send a crypto-NAK packet. 3434 */ 3436 /* not multicast dstaddr */ 3437 if (!IN_MULTICAST(dstaddr)) { 3438 if (AUTH(p->flags & P_NOTRUST, auth)) 3439 fast_xmit(r, M_SERV, auth); 3440 else if (auth == A_ERROR) 3441 fast_xmit(r, M_SERV, A_CRYPTO); 3442 return; /* M_SERV packet sent */ 3443 } 3445 /* 3446 * This must be manycast. Do not respond if we are not 3447 * synchronized or if our stratum is above the 3448 * manycaster. 3449 */ 3450 if (s.leap == NOSYNC || s.stratum > r->stratum) 3451 return; 3453 /* 3454 * Respond only if authentication is ok. Note that the 3455 * unicast address is used, not the multicast. 3456 */ 3457 if (AUTH(p->flags & P_NOTRUST, auth)) 3458 fast_xmit(r, M_SERV, auth); 3459 return; 3461 /* 3462 * New manycast client ephemeral association. It is mobilized in 3463 * the same version as in the packet. If authentication fails, 3464 * ignore the packet. Verify the server packet by comparing the 3465 * r->org timestamp in the packet with the p->xmt timestamp in 3466 * the multicast client association. If they match, the server 3467 * packet is authentic. Details omitted. 3468 */ 3469 case MANY: 3470 if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth)) 3471 return; /* authentication error */ 3473 p = mobilize(r->srcaddr, r->dstaddr, r->version, M_CLNT, 3474 r->keyid, P_EPHEM); 3475 break; 3477 /* 3478 * New symmetric passive association. It is mobilized in the same 3479 * version as in the packet. If authentication fails, send a 3480 * crypto-NAK packet. If restrict no-moblize, send a symmetric 3481 * active packet instead. 3482 */ 3483 case NEWPS: 3484 if (!AUTH(p->flags & P_NOTRUST, auth)) { 3485 if (auth == A_ERROR) 3486 fast_xmit(r, M_SACT, A_CRYPTO); 3487 return; /* crypto-NAK packet sent */ 3488 } 3489 if (!AUTH(p->flags & P_NOPEER, auth)) { 3490 fast_xmit(r, M_SACT, auth); 3491 return; /* M_SACT packet sent */ 3492 } 3493 p = mobilize(r->srcaddr, r->dstaddr, r->version, M_PASV, 3494 r->keyid, P_EPHEM); 3495 break; 3497 /* 3498 * New broadcast client association. It is mobilized in the same 3499 * version as in the packet. If authentication fails, ignore the 3500 * packet. Note this code does not support the initial volley 3501 * feature in the reference implementation. 3502 */ 3504 case NEWBC: 3505 if (!AUTH(p->flags & (P_NOTRUST | P_NOPEER), auth)) 3506 return; /* authentication error */ 3508 if (!(s.flags & S_BCSTENAB)) 3509 return; /* broadcast not enabled */ 3511 p = mobilize(r->srcaddr, r->dstaddr, r->version, M_BCLN, 3512 r->keyid, P_EPHEM); 3513 break; /* processing continues */ 3515 /* 3516 * Process packet. Placeholdler only. 3517 */ 3518 case PROC: 3519 break; /* processing continues */ 3521 /* 3522 * Invalid mode combination. We get here only in case of 3523 * ephemeral associations, so the correct action is simply to 3524 * toss it. 3525 */ 3526 case ERR: 3527 clear(p, X_ERROR); 3528 return; /* invalid mode combination */ 3530 /* 3531 * No match; just discard the packet. 3532 */ 3533 case DSCRD: 3534 return; /* orphan abandoned */ 3535 } 3537 /* 3538 * Next comes a rigorous schedule of timestamp checking. If the 3539 * transmit timestamp is zero, the server is horribly broken. 3540 */ 3541 if (r->xmt == 0) 3542 return; /* invalid timestamp */ 3544 /* 3545 * If the transmit timestamp duplicates a previous one, the 3546 * packet is a replay. 3547 */ 3548 if (r->xmt == p->xmt) 3549 return; /* duplicate packet */ 3551 /* 3552 * If this is a broadcast mode packet, skip further checking. 3553 * If the origin timestamp is zero, the sender has not yet heard 3554 * from us. Otherwise, if the origin timestamp does not match 3555 * the transmit timestamp, the packet is bogus. 3556 */ 3557 synch = TRUE; 3558 if (r->mode != M_BCST) { 3559 if (r->org == 0) 3560 synch = FALSE; /* unsynchronized */ 3562 else if (r->org != p->xmt) 3563 synch = FALSE; /* bogus packet */ 3564 } 3566 /* 3567 * Update the origin and destination timestamps. If 3568 * unsynchronized or bogus, abandon ship. 3569 */ 3570 p->org = r->xmt; 3571 p->rec = r->dst; 3572 if (!synch) 3573 return; /* unsynch */ 3575 /* 3576 * The timestamps are valid and the receive packet matches the 3577 * last one sent. If the packet is a crypto-NAK, the server 3578 * might have just changed keys. We demobilize the association 3579 * and wait for better times. 3580 */ 3581 if (auth == A_CRYPTO) { 3582 clear(p, X_CRYPTO); 3583 return; /* crypto-NAK */ 3584 } 3586 /* 3587 * If the association is authenticated, the key ID is nonzero 3588 * and received packets must be authenticated. This is designed 3589 * to avoid a bait-and-switch attack, which was possible in past 3590 * versions. 3591 */ 3592 if (!AUTH(p->keyid || (p->flags & P_NOTRUST), auth)) 3593 return; /* bad auth */ 3595 /* 3596 * Everything possible has been done to validate the timestamps 3597 * and prevent bad guys from disrupting the protocol or 3598 * injecting bogus data. Earn some revenue. 3599 */ 3601 packet(p, r); 3602 } 3604 A.5.1.1. packet() 3606 /* 3607 * packet() - process packet and compute offset, delay and 3608 * dispersion. 3609 */ 3610 void 3611 packet( 3612 struct p *p, /* peer structure pointer */ 3613 struct r *r /* receive packet pointer */ 3614 ) 3615 { 3616 double offset; /* sample offsset */ 3617 double delay; /* sample delay */ 3618 double disp; /* sample dispersion */ 3620 /* 3621 * By golly the packet is valid. Light up the remaining header 3622 * fields. Note that we map stratum 0 (unspecified) to MAXSTRAT 3623 * to make stratum comparisons simpler and to provide a natural 3624 * interface for radio clock drivers that operate for 3625 * convenience at stratum 0. 3626 */ 3627 p->leap = r->leap; 3628 if (r->stratum == 0) 3629 p->stratum = MAXSTRAT; 3630 else 3631 p->stratum = r->stratum; 3632 p->pmode = r->mode; 3633 p->ppoll = r->poll; 3634 p->rootdelay = FP2D(r->rootdelay); 3635 p->rootdisp = FP2D(r->rootdisp); 3636 p->refid = r->refid; 3637 p->reftime = r->reftime; 3639 /* 3640 * Verify the server is synchronized with valid stratum and 3641 * reference time not later than the transmit time. 3642 */ 3643 if (p->leap == NOSYNC || p->stratum >= MAXSTRAT) 3644 return; /* unsynchronized */ 3646 /* 3647 * Verify valid root distance. 3648 */ 3650 if (r->rootdelay / 2 + r->rootdisp >= MAXDISP || p->reftime > 3651 r->xmt) 3652 return; /* invalid header values */ 3654 poll_update(p, p->hpoll); 3655 p->reach |= 1; 3657 /* 3658 * Calculate offset, delay and dispersion, then pass to the 3659 * clock filter. Note carefully the implied processing. The 3660 * first-order difference is done directly in 64-bit arithmetic, 3661 * then the result is converted to floating double. All further 3662 * processing is in floating double arithmetic with rounding 3663 * done by the hardware. This is necessary in order to avoid 3664 * overflow and preseve precision. 3665 * 3666 * The delay calculation is a special case. In cases where the 3667 * server and client clocks are running at different rates and 3668 * with very fast networks, the delay can appear negative. In 3669 * order to avoid violating the Principle of Least Astonishment, 3670 * the delay is clamped not less than the system precision. 3671 */ 3672 if (p->pmode == M_BCST) { 3673 offset = LFP2D(r->xmt - r->dst); 3674 delay = BDELAY; 3675 disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI * 3676 2 * BDELAY; 3677 } else { 3678 offset = (LFP2D(r->rec - r->org) + LFP2D(r->dst - 3679 r->xmt)) / 2; 3680 delay = max(LFP2D(r->dst - r->org) - LFP2D(r->rec - 3681 r->xmt), LOG2D(s.precision)); 3682 disp = LOG2D(r->precision) + LOG2D(s.precision) + PHI * 3683 LFP2D(r->dst - r->org); 3684 } 3685 clock_filter(p, offset, delay, disp); 3686 } 3688 A.5.2. clock_filter() 3690 /* 3691 * clock_filter(p, offset, delay, dispersion) - select the best from the 3692 * latest eight delay/offset samples. 3693 */ 3694 void 3695 clock_filter( 3696 struct p *p, /* peer structure pointer */ 3697 double offset, /* clock offset */ 3698 double delay, /* roundtrip delay */ 3699 double disp /* dispersion */ 3700 ) 3701 { 3702 struct f f[NSTAGE]; /* sorted list */ 3703 double dtemp; 3704 int i; 3706 /* 3707 * The clock filter contents consist of eight tuples (offset, 3708 * delay, dispersion, time). Shift each tuple to the left, 3709 * discarding the leftmost one. As each tuple is shifted, 3710 * increase the dispersion since the last filter update. At the 3711 * same time, copy each tuple to a temporary list. After this, 3712 * place the (offset, delay, disp, time) in the vacated 3713 * rightmost tuple. 3714 */ 3715 for (i = 1; i < NSTAGE; i++) { 3716 p->f[i] = p->f[i - 1]; 3717 p->f[i].disp += PHI * (c.t - p->t); 3718 f[i] = p->f[i]; 3719 } 3720 p->f[0].t = c.t; 3721 p->f[0].offset = offset; 3722 p->f[0].delay = delay; 3723 p->f[0].disp = disp; 3724 f[0] = p->f[0]; 3726 /* 3727 * Sort the temporary list of tuples by increasing f[].delay. 3728 * The first entry on the sorted list represents the best 3729 * sample, but it might be old. 3730 */ 3731 dtemp = p->offset; 3732 p->offset = f[0].offset; 3733 p->delay = f[0].delay; 3734 for (i = 0; i < NSTAGE; i++) { 3735 p->disp += f[i].disp / (2 ^ (i + 1)); 3736 p->jitter += SQUARE(f[i].offset - f[0].offset); 3737 } 3738 p->jitter = max(SQRT(p->jitter), LOG2D(s.precision)); 3740 /* 3741 * Prime directive: use a sample only once and never a sample 3742 * older than the latest one, but anything goes before first 3743 * synchronized. 3744 */ 3745 if (f[0].t - p->t <= 0 && s.leap != NOSYNC) 3746 return; 3748 /* 3749 * Popcorn spike suppressor. Compare the difference between the 3750 * last and current offsets to the current jitter. If greater 3751 * than SGATE (3) and if the interval since the last offset is 3752 * less than twice the system poll interval, dump the spike. 3753 * Otherwise, and if not in a burst, shake out the truechimers. 3754 */ 3755 if (fabs(p->offset - dtemp) > SGATE * p->jitter && (f[0].t - 3756 p->t) < 2 * s.poll) 3757 return; 3759 p->t = f[0].t; 3760 if (p->burst == 0) 3761 clock_select(); 3762 return; 3763 } 3765 /* 3766 * fit() - test if association p is acceptable for synchronization 3767 */ 3768 int 3769 fit( 3770 struct p *p /* peer structure pointer */ 3771 ) 3772 { 3773 /* 3774 * A stratum error occurs if (1) the server has never been 3775 * synchronized, (2) the server stratum is invalid. 3776 */ 3777 if (p->leap == NOSYNC || p->stratum >= MAXSTRAT) 3778 return (FALSE); 3780 /* 3781 * A distance error occurs if the root distance exceeds the 3782 * distance threshold plus an increment equal to one poll 3783 * interval. 3784 */ 3785 if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll)) 3786 return (FALSE); 3788 /* 3789 * A loop error occurs if the remote peer is synchronized to the 3790 * local peer or the remote peer is synchronized to the current 3791 * system peer. Note this is the behavior for IPv4; for IPv6 the 3792 * MD5 hash is used instead. 3793 */ 3795 if (p->refid == p->dstaddr || p->refid == s.refid) 3796 return (FALSE); 3798 /* 3799 * An unreachable error occurs if the server is unreachable. 3800 */ 3801 if (p->reach == 0) 3802 return (FALSE); 3804 return (TRUE); 3805 } 3807 /* 3808 * clear() - reinitialize for persistent association, demobilize 3809 * for ephemeral association. 3810 */ 3811 void 3812 clear( 3813 struct p *p, /* peer structure pointer */ 3814 int kiss /* kiss code */ 3815 ) 3816 { 3817 int i; 3819 /* 3820 * The first thing to do is return all resources to the bank. 3821 * Typical resources are not detailed here, but they include 3822 * dynamically allocated structures for keys, certificates, etc. 3823 * If an ephemeral association and not initialization, return 3824 * the association memory as well. 3825 */ 3826 /* return resources */ 3827 if (s.p == p) 3828 s.p = NULL; 3829 if (kiss != X_INIT && (p->flags & P_EPHEM)) { 3830 free(p); 3831 return; 3832 } 3834 /* 3835 * Initialize the association fields for general reset. 3836 */ 3837 memset(BEGIN_CLEAR(p), LEN_CLEAR, 0); 3838 p->leap = NOSYNC; 3839 p->stratum = MAXSTRAT; 3840 p->ppoll = MAXPOLL; 3841 p->hpoll = MINPOLL; 3842 p->disp = MAXDISP; 3843 p->jitter = LOG2D(s.precision); 3844 p->refid = kiss; 3845 for (i = 0; i < NSTAGE; i++) 3846 p->f[i].disp = MAXDISP; 3848 /* 3849 * Randomize the first poll just in case thousands of broadcast 3850 * clients have just been stirred up after a long absence of the 3851 * broadcast server. 3852 */ 3853 p->outdate = p->t = c.t; 3854 p->nextdate = p->outdate + (random() & ((1 << MINPOLL) - 1)); 3855 } 3857 A.5.3. fast_xmit() 3859 /* 3860 * fast_xmit() - transmit a reply packet for receive packet r 3861 */ 3862 void 3863 fast_xmit( 3864 struct r *r, /* receive packet pointer */ 3865 int mode, /* association mode */ 3866 int auth /* authentication code */ 3867 ) 3868 { 3869 struct x x; 3871 /* 3872 * Initialize header and transmit timestamp. Note that the 3873 * transmit version is copied from the receive version. This is 3874 * for backward compatibility. 3875 */ 3876 x.version = r->version; 3877 x.srcaddr = r->dstaddr; 3878 x.dstaddr = r->srcaddr; 3879 x.leap = s.leap; 3880 x.mode = mode; 3881 if (s.stratum == MAXSTRAT) 3882 x.stratum = 0; 3883 else 3884 x.stratum = s.stratum; 3885 x.poll = r->poll; 3886 x.precision = s.precision; 3887 x.rootdelay = D2FP(s.rootdelay); 3888 x.rootdisp = D2FP(s.rootdisp); 3889 x.refid = s.refid; 3890 x.reftime = s.reftime; 3891 x.org = r->xmt; 3892 x.rec = r->dst; 3893 x.xmt = get_time(); 3895 /* 3896 * If the authentication code is A.NONE, include only the 3897 * header; if A.CRYPTO, send a crypto-NAK; if A.OK, send a valid 3898 * MAC. Use the key ID in the received packet and the key in the 3899 * local key cache. 3900 */ 3901 if (auth != A_NONE) { 3902 if (auth == A_CRYPTO) { 3903 x.keyid = 0; 3904 } else { 3905 x.keyid = r->keyid; 3906 x.dgst = md5(x.keyid); 3907 } 3908 } 3909 xmit_packet(&x); 3910 } 3912 A.5.4. access() 3914 /* 3915 * access() - determine access restrictions 3916 */ 3917 int 3918 access( 3919 struct r *r /* receive packet pointer */ 3920 ) 3921 { 3922 /* 3923 * The access control list is an ordered set of tuples 3924 * consisting of an address, mask and restrict word containing 3925 * defined bits. The list is searched for the first match on the 3926 * source address (r->srcaddr) and the associated restrict word 3927 * is returned. 3928 */ 3929 return (/* access bits */ 0); 3930 } 3932 A.5.5. System Process 3934 A.5.5.1. clock_select() 3936 /* 3937 * clock_select() - find the best clocks 3938 */ 3940 void 3941 clock_select() { 3942 struct p *p, *osys; /* peer structure pointers */ 3943 double low, high; /* correctness interval extents */ 3944 int allow, found, chime; /* used by intersection algorithm */ 3945 int n, i, j; 3947 /* 3948 * We first cull the falsetickers from the server population, 3949 * leaving only the truechimers. The correctness interval for 3950 * association p is the interval from offset - root_dist() to 3951 * offset + root_dist(). The object of the game is to find a 3952 * majority clique; that is, an intersection of correctness 3953 * intervals numbering more than half the server population. 3954 * 3955 * First construct the chime list of tuples (p, type, edge) as 3956 * shown below, then sort the list by edge from lowest to 3957 * highest. 3958 */ 3959 osys = s.p; 3960 s.p = NULL; 3961 n = 0; 3962 while (fit(p)) { 3963 s.m[n].p = p; 3964 s.m[n].type = +1; 3965 s.m[n].edge = p->offset + root_dist(p); 3966 n++; 3967 s.m[n].p = p; 3968 s.m[n].type = 0; 3969 s.m[n].edge = p->offset; 3970 n++; 3971 s.m[n].p = p; 3972 s.m[n].type = -1; 3973 s.m[n].edge = p->offset - root_dist(p); 3974 n++; 3975 } 3977 /* 3978 * Find the largest contiguous intersection of correctness 3979 * intervals. Allow is the number of allowed falsetickers; found 3980 * is the number of midpoints. Note that the edge values are 3981 * limited to the range +-(2 ^ 30) < +-2e9 by the timestamp 3982 * calculations. 3983 */ 3984 low = 2e9; high = -2e9; 3985 for (allow = 0; 2 * allow < n; allow++) { 3987 /* 3988 * Scan the chime list from lowest to highest to find 3989 * the lower endpoint. 3990 */ 3991 found = 0; 3992 chime = 0; 3993 for (i = 0; i < n; i++) { 3994 chime -= s.m[i].type; 3995 if (chime >= n - found) { 3996 low = s.m[i].edge; 3997 break; 3998 } 3999 if (s.m[i].type == 0) 4000 found++; 4001 } 4003 /* 4004 * Scan the chime list from highest to lowest to find 4005 * the upper endpoint. 4006 */ 4007 chime = 0; 4008 for (i = n - 1; i >= 0; i--) { 4009 chime += s.m[i].type; 4010 if (chime >= n - found) { 4011 high = s.m[i].edge; 4012 break; 4013 } 4014 if (s.m[i].type == 0) 4015 found++; 4016 } 4018 /* 4019 * If the number of midpoints is greater than the number 4020 * of allowed falsetickers, the intersection contains at 4021 * least one truechimer with no midpoint. If so, 4022 * increment the number of allowed falsetickers and go 4023 * around again. If not and the intersection is 4024 * nonempty, declare success. 4025 */ 4026 if (found > allow) 4027 continue; 4029 if (high > low) 4030 break; 4031 } 4033 /* 4034 * Clustering algorithm. Construct a list of survivors (p, 4035 * metric) from the chime list, where metric is dominated first 4036 * by stratum and then by root distance. All other things being 4037 * equal, this is the order of preference. 4038 */ 4039 s.n = 0; 4040 for (i = 0; i < n; i++) { 4041 if (s.m[i].edge < low || s.m[i].edge > high) 4042 continue; 4044 p = s.m[i].p; 4045 s.v[n].p = p; 4046 s.v[n].metric = MAXDIST * p->stratum + root_dist(p); 4047 s.n++; 4048 } 4050 /* 4051 * There must be at least NSANE survivors to satisfy the 4052 * correctness assertions. Ordinarily, the Byzantine criteria 4053 * require four, survivors, but for the demonstration here, one 4054 * is acceptable. 4055 */ 4056 if (s.n < NSANE) 4057 return; 4059 /* 4060 * For each association p in turn, calculate the selection 4061 * jitter p->sjitter as the square root of the sum of squares 4062 * (p->offset - q->offset) over all q associations. The idea is 4063 * to repeatedly discard the survivor with maximum selection 4064 * jitter until a termination condition is met. 4065 */ 4066 while (1) { 4067 struct p *p, *q, *qmax; /* peer structure pointers */ 4068 double max, min, dtemp; 4070 max = -2e9; min = 2e9; 4071 for (i = 0; i < s.n; i++) { 4072 p = s.v[i].p; 4073 if (p->jitter < min) 4074 min = p->jitter; 4075 dtemp = 0; 4076 for (j = 0; j < n; j++) { 4077 q = s.v[j].p; 4078 dtemp += SQUARE(p->offset - q->offset); 4079 } 4080 dtemp = SQRT(dtemp); 4081 if (dtemp > max) { 4082 max = dtemp; 4083 qmax = q; 4085 } 4086 } 4088 /* 4089 * If the maximum selection jitter is less than the 4090 * minimum peer jitter, then tossing out more survivors 4091 * will not lower the minimum peer jitter, so we might 4092 * as well stop. To make sure a few survivors are left 4093 * for the clustering algorithm to chew on, we also stop 4094 * if the number of survivors is less than or equal to 4095 * NMIN (3). 4096 */ 4097 if (max < min || n <= NMIN) 4098 break; 4100 /* 4101 * Delete survivor qmax from the list and go around 4102 * again. 4103 */ 4104 s.n--; 4105 } 4107 /* 4108 * Pick the best clock. If the old system peer is on the list 4109 * and at the same stratum as the first survivor on the list, 4110 * then don't do a clock hop. Otherwise, select the first 4111 * survivor on the list as the new system peer. 4112 */ 4113 if (osys->stratum == s.v[0].p->stratum) 4114 s.p = osys; 4115 else 4116 s.p = s.v[0].p; 4117 clock_update(s.p); 4118 } 4119 A.5.5.2. root_dist() 4121 /* 4122 * root_dist() - calculate root distance 4123 */ 4124 double 4125 root_dist( 4126 struct p *p /* peer structure pointer */ 4127 ) 4128 { 4130 /* 4131 * The root synchronization distance is the maximum error due to 4132 * all causes of the local clock relative to the primary server. 4133 * It is defined as half the total delay plus total dispersion 4134 * plus peer jitter. 4135 */ 4136 return (max(MINDISP, p->rootdelay + p->delay) / 2 + 4137 p->rootdisp + p->disp + PHI * (c.t - p->t) + p->jitter); 4138 } 4139 A.5.5.3. accept() 4141 /* 4142 * accept() - test if association p is acceptable for synchronization 4143 */ 4144 int 4145 accept( 4146 struct p *p /* peer structure pointer */ 4147 ) 4148 { 4149 /* 4150 * A stratum error occurs if (1) the server has never been 4151 * synchronized, (2) the server stratum is invalid. 4152 */ 4153 if (p->leap == NOSYNC || p->stratum >= MAXSTRAT) 4154 return (FALSE); 4156 /* 4157 * A distance error occurs if the root distance exceeds the 4158 * distance threshold plus an increment equal to one poll 4159 * interval. 4160 */ 4161 if (root_dist(p) > MAXDIST + PHI * LOG2D(s.poll)) 4162 return (FALSE); 4164 /* 4165 * A loop error occurs if the remote peer is synchronized to the 4166 * local peer or the remote peer is synchronized to the current 4167 * system peer. Note this is the behavior for IPv4; for IPv6 the 4168 * MD5 hash is used instead. 4169 */ 4170 if (p->refid == p->dstaddr || p->refid == s.refid) 4171 return (FALSE); 4173 /* 4174 * An unreachable error occurs if the server is unreachable. 4175 */ 4176 if (p->reach == 0) 4177 return (FALSE); 4179 return (TRUE); 4180 } 4182 A.5.5.4. clock_update() 4184 /* 4185 * clock_update() - update the system clock 4186 */ 4188 void 4189 clock_update( 4190 struct p *p /* peer structure pointer */ 4191 ) 4192 { 4193 double dtemp; 4195 /* 4196 * If this is an old update, for instance as the result of a 4197 * system peer change, avoid it. We never use an old sample or 4198 * the same sample twice. 4199 */ 4200 if (s.t >= p->t) 4201 return; 4203 /* 4204 * Combine the survivor offsets and update the system clock; the 4205 * local_clock() routine will tell us the good or bad news. 4206 */ 4207 s.t = p->t; 4208 clock_combine(); 4209 switch (local_clock(p, s.offset)) { 4211 /* 4212 * The offset is too large and probably bogus. Complain to the 4213 * system log and order the operator to set the clock manually 4214 * within PANIC range. The reference implementation includes a 4215 * command line option to disable this check and to change the 4216 * panic threshold from the default 1000 s as required. 4217 */ 4218 case PANIC: 4219 exit (0); 4221 /* 4222 * The offset is more than the step threshold (0.125 s by 4223 * default). After a step, all associations now have 4224 * inconsistent time valurs, so they are reset and started 4225 * fresh. The step threshold can be changed in the reference 4226 * implementation in order to lessen the chance the clock might 4227 * be stepped backwards. However, there may be serious 4228 * consequences, as noted in the white papers at the NTP project 4229 * site. 4230 */ 4231 case STEP: 4232 while (/* all associations */ 0) 4233 clear(p, X_STEP); 4234 s.stratum = MAXSTRAT; 4235 s.poll = MINPOLL; 4236 break; 4238 /* 4239 * The offset was less than the step threshold, which is the 4240 * normal case. Update the system variables from the peer 4241 * variables. The lower clamp on the dispersion increase is to 4242 * avoid timing loops and clockhopping when highly precise 4243 * sources are in play. The clamp can be changed from the 4244 * default .01 s in the reference implementation. 4245 */ 4246 case SLEW: 4247 s.leap = p->leap; 4248 s.stratum = p->stratum + 1; 4249 s.refid = p->refid; 4250 s.reftime = p->reftime; 4251 s.rootdelay = p->rootdelay + p->delay; 4252 dtemp = SQRT(SQUARE(p->jitter) + SQUARE(s.jitter)); 4253 dtemp += max(p->disp + PHI * (c.t - p->t) + 4254 fabs(p->offset), MINDISP); 4255 s.rootdisp = p->rootdisp + dtemp; 4256 break; 4258 /* 4259 * Some samples are discarded while, for instance, a direct 4260 * frequency measurement is being made. 4261 */ 4262 case IGNORE: 4263 break; 4264 } 4265 } 4266 A.5.5.5. clock_combine() 4268 /* 4269 * clock_combine() - combine offsets 4270 */ 4271 void 4272 clock_combine() 4273 { 4274 struct p *p; /* peer structure pointer */ 4275 double x, y, z, w; 4276 int i; 4278 /* 4279 * Combine the offsets of the clustering algorithm survivors 4280 * using a weighted average with weight determined by the root 4281 * distance. Compute the selection jitter as the weighted RMS 4282 * difference between the first survivor and the remaining 4283 * survivors. In some cases the inherent clock jitter can be 4284 * reduced by not using this algorithm, especially when frequent 4285 * clockhopping is involved. The reference implementation can be 4286 * configured to avoid this algorithm by designating a preferred 4287 * peer. 4288 */ 4289 y = z = w = 0; 4290 for (i = 0; s.v[i].p != NULL; i++) { 4291 p = s.v[i].p; 4292 x = root_dist(p); 4293 y += 1 / x; 4294 z += p->offset / x; 4295 w += SQUARE(p->offset - s.v[0].p->offset) / x; 4296 } 4297 s.offset = z / y; 4298 s.jitter = SQRT(w / y); 4299 } 4301 A.5.5.6. local_clock() 4303 /* 4304 * Clock discipline parameters and constants 4305 */ 4306 #define STEPT .128 /* step threshold (s) */ 4307 #define WATCH 900 /* stepout threshold (s) */ 4308 #define PANICT 1000 /* panic threshold (s) */ 4309 #define PLL 65536 /* PLL loop gain */ 4310 #define FLL MAXPOLL + 1 /* FLL loop gain */ 4311 #define AVG 4 /* parameter averaging constant */ 4312 #define ALLAN 1500 /* compromise Allan intercept (s) */ 4313 #define LIMIT 30 /* poll-adjust threshold */ 4314 #define MAXFREQ 500e-6 /* frequency tolerance (500 PPM) */ 4315 #define PGATE 4 /* poll-adjust gate */ 4317 /* 4318 * local_clock() - discipline the local clock 4319 */ 4320 int /* return code */ 4321 local_clock( 4322 struct p *p, /* peer structure pointer */ 4323 double offset /* clock offset from combine() */ 4324 ) 4325 { 4326 int state; /* clock discipline state */ 4327 double freq; /* frequency */ 4328 double mu; /* interval since last update */ 4329 int rval; 4330 double etemp, dtemp; 4332 /* 4333 * If the offset is too large, give up and go home. 4334 */ 4335 if (fabs(offset) > PANICT) 4336 return (PANIC); 4338 /* 4339 * Clock state machine transition function. This is where the 4340 * action is and defines how the system reacts to large time 4341 * and frequency errors. There are two main regimes: when the 4342 * offset exceeds the step threshold and when it does not. 4343 */ 4344 rval = SLEW; 4345 mu = p->t - s.t; 4346 freq = 0; 4347 if (fabs(offset) > STEPT) { 4348 switch (c.state) { 4350 /* 4351 * In S_SYNC state we ignore the first outlyer amd 4352 * switch to S_SPIK state. 4353 */ 4354 case SYNC: 4355 state = SPIK; 4356 return (rval); 4358 /* 4359 * In S_FREQ state we ignore outlyers and inlyers. At 4360 * the first outlyer after the stepout threshold, 4361 * compute the apparent frequency correction and step 4362 * the time. 4363 */ 4364 case FREQ: 4365 if (mu < WATCH) 4366 return (IGNORE); 4368 freq = (offset - c.offset) / mu; 4369 /* fall through to S_SPIK */ 4371 /* 4372 * In S_SPIK state we ignore succeeding outlyers until 4373 * either an inlyer is found or the stepout threshold is 4374 * exceeded. 4375 */ 4376 case SPIK: 4377 if (mu < WATCH) 4378 return (IGNORE); 4380 /* fall through to default */ 4382 /* 4383 * We get here by default in S_NSET and S_FSET states 4384 * and from above in S_FREQ state. Step the time and 4385 * clamp down the poll interval. 4386 * 4387 * In S_NSET state an initial frequency correction is 4388 * not available, usually because the frequency file has 4389 * not yet been written. Since the time is outside the 4390 * capture range, the clock is stepped. The frequency 4391 * will be set directly following the stepout interval. 4392 * 4393 * In S_FSET state the initial frequency has been set 4394 * from the frequency file. Since the time is outside 4395 * the capture range, the clock is stepped immediately, 4396 * rather than after the stepout interval. Guys get 4397 * nervous if it takes 17 minutes to set the clock for 4398 * the first time. 4399 * 4400 * In S_SPIK state the stepout threshold has expired and 4401 * the phase is still above the step threshold. Note 4402 * that a single spike greater than the step threshold 4403 * is always suppressed, even at the longer poll 4404 * intervals. 4405 */ 4406 default: 4408 /* 4409 * This is the kernel set time function, usually 4410 * implemented by the Unix settimeofday() system 4411 * call. 4412 */ 4413 step_time(offset); 4414 c.count = 0; 4415 s.poll = MINPOLL; 4416 rval = STEP; 4417 if (state == NSET) { 4418 rstclock(FREQ, p->t, 0); 4419 return (rval); 4420 } 4421 break; 4422 } 4423 rstclock(SYNC, p->t, 0); 4424 } else { 4426 /* 4427 * Compute the clock jitter as the RMS of exponentially 4428 * weighted offset differences. This is used by the 4429 * poll-adjust code. 4430 */ 4431 etemp = SQUARE(c.jitter); 4432 dtemp = SQUARE(max(fabs(offset - c.last), 4433 LOG2D(s.precision))); 4434 c.jitter = SQRT(etemp + (dtemp - etemp) / AVG); 4435 switch (c.state) { 4437 /* 4438 * In S_NSET state this is the first update received and 4439 * the frequency has not been initialized. The first 4440 * thing to do is directly measure the oscillator 4441 * frequency. 4442 */ 4443 case NSET: 4444 rstclock(FREQ, p->t, offset); 4445 return (IGNORE); 4447 /* 4448 * In S_FSET state this is the first update and the 4449 * frequency has been initialized. Adjust the phase, but 4450 * don't adjust the frequency until the next update. 4451 */ 4452 case FSET: 4453 rstclock(SYNC, p->t, offset); 4454 break; 4456 /* 4457 * In S_FREQ state ignore updates until the stepout 4458 * threshold. After that, correct the phase and 4459 * frequency and switch to S_SYNC state. 4460 */ 4461 case FREQ: 4462 if (c.t - s.t < WATCH) 4463 return (IGNORE); 4465 freq = (offset - c.offset) / mu; 4466 break; 4468 /* 4469 * We get here by default in S_SYNC and S_SPIK states. 4470 * Here we compute the frequency update due to PLL and 4471 * FLL contributions. 4472 */ 4473 default: 4475 /* 4476 * The FLL and PLL frequency gain constants 4477 * depend on the poll interval and Allan 4478 * intercept. The FLL is not used below one-half 4479 * the Allan intercept. Above that the loop gain 4480 * increases in steps to 1 / AVG. 4481 */ 4482 if (LOG2D(s.poll) > ALLAN / 2) { 4483 etemp = FLL - s.poll; 4484 if (etemp < AVG) 4485 etemp = AVG; 4486 freq += (offset - c.offset) / (max(mu, 4487 ALLAN) * etemp); 4488 } 4490 /* 4491 * For the PLL the integration interval 4492 * (numerator) is the minimum of the update 4493 * interval and poll interval. This allows 4494 * oversampling, but not undersampling. 4495 */ 4496 etemp = min(mu, LOG2D(s.poll)); 4497 dtemp = 4 * PLL * LOG2D(s.poll); 4498 freq += offset * etemp / (dtemp * dtemp); 4499 rstclock(SYNC, p->t, offset); 4500 break; 4501 } 4502 } 4504 /* 4505 * Calculate the new frequency and frequency stability (wander). 4507 * Compute the clock wander as the RMS of exponentially weighted 4508 * frequency differences. This is not used directly, but can, 4509 * along with the jitter, be a highly useful monitoring and 4510 * debugging tool 4511 */ 4512 freq += c.freq; 4513 c.freq = max(min(MAXFREQ, freq), -MAXFREQ); 4514 etemp = SQUARE(c.wander); 4515 dtemp = SQUARE(freq); 4516 c.wander = SQRT(etemp + (dtemp - etemp) / AVG); 4518 /* 4519 * Here we adjust the poll interval by comparing the current 4520 * offset with the clock jitter. If the offset is less than the 4521 * clock jitter times a constant, then the averaging interval is 4522 * increased, otherwise it is decreased. A bit of hysteresis 4523 * helps calm the dance. Works best using burst mode. 4524 */ 4525 if (fabs(c.offset) < PGATE * c.jitter) { 4526 c.count += s.poll; 4527 if (c.count > LIMIT) { 4528 c.count = LIMIT; 4529 if (s.poll < MAXPOLL) { 4530 c.count = 0; 4531 s.poll++; 4532 } 4533 } 4534 } else { 4535 c.count -= s.poll << 1; 4536 if (c.count < -LIMIT) { 4537 c.count = -LIMIT; 4538 if (s.poll > MINPOLL) { 4539 c.count = 0; 4540 s.poll--; 4541 } 4542 } 4543 } 4544 return (rval); 4545 } 4546 A.5.5.7. rstclock() 4548 /* 4549 * rstclock() - clock state machine 4550 */ 4551 void 4552 rstclock( 4553 int state, /* new state */ 4554 double offset, /* new offset */ 4555 double t /* new update time */ 4556 ) 4557 { 4558 /* 4559 * Enter new state and set state variables. Note we use the time 4560 * of the last clock filter sample, which must be earlier than 4561 * the current time. 4562 */ 4563 c.state = state; 4564 c.last = c.offset = offset; 4565 s.t = t; 4566 } 4568 A.5.6. Clock Adjust Process 4570 A.5.6.1. clock_adjust() 4572 /* 4573 * clock_adjust() - runs at one-second intervals 4574 */ 4575 void 4576 clock_adjust() { 4577 double dtemp; 4579 /* 4580 * Update the process time c.t. Also increase the dispersion 4581 * since the last update. In contrast to NTPv3, NTPv4 does not 4582 * declare unsynchronized after one day, since the dispersion 4583 * threshold serves this function. When the dispersion exceeds 4584 * MAXDIST (1 s), the server is considered unfit for 4585 * synchronization. 4586 */ 4587 c.t++; 4588 s.rootdisp += PHI; 4590 /* 4591 * Implement the phase and frequency adjustments. The gain 4592 * factor (denominator) is not allowed to increase beyond the 4593 * Allan intercept. It doesn't make sense to average phase noise 4594 * beyond this point and it helps to damp residual offset at the 4595 * longer poll intervals. 4596 */ 4597 dtemp = c.offset / (PLL * min(LOG2D(s.poll), ALLAN)); 4598 c.offset -= dtemp; 4600 /* 4601 * This is the kernel adjust time function, usually implemented 4602 * by the Unix adjtime() system call. 4603 */ 4604 adjust_time(c.freq + dtemp); 4606 /* 4607 * Peer timer. Call the poll() routine when the poll timer 4608 * expires. 4609 */ 4610 while (/* all associations */ 0) { 4611 struct p *p; /* dummy peer structure pointer */ 4613 if (c.t >= p->nextdate) 4614 poll(p); 4615 } 4617 /* 4618 * Once per hour write the clock frequency to a file 4619 */ 4620 if (c.t % 3600 == 3599) 4621 /* write c.freq to file */ 0; 4622 } 4624 A.5.7. Poll Process 4626 /* 4627 * Poll process parameters and constants 4628 */ 4629 #define UNREACH 12 /* unreach counter threshold */ 4630 #define BCOUNT 8 /* packets in a burst */ 4631 #define BTIME 2 /* burst interval (s) */ 4633 A.5.7.1. poll() 4635 /* 4636 * poll() - determine when to send a packet for association p-> 4637 */ 4638 void 4639 poll( 4640 struct p *p /* peer structure pointer */ 4641 ) 4643 { 4644 int hpoll; 4645 int oreach; 4647 /* 4648 * This routine is called when the current time c.t catches up 4649 * to the next poll time p->nextdate. The value p->outdate is 4650 * the last time this routine was executed. The poll_update() 4651 * routine determines the next execution time p->nextdate. 4652 * 4653 * If broadcasting, just do it, but only if we are synchronized. 4654 */ 4655 hpoll = p->hpoll; 4656 if (p->hmode == M_BCST) { 4657 p->outdate = c.t; 4658 if (s.p != NULL) 4659 peer_xmit(p); 4660 poll_update(p, hpoll); 4661 return; 4662 } 4664 /* 4665 * If manycasting, start with ttl = 1. The ttl is increased by 4666 * one for each poll until MAXCLOCK servers have been found or 4667 * ttl reaches TTLMAX. If reaching MAXCLOCK, stop polling until 4668 * the number of servers falls below MINCLOCK, then start all 4669 * over. 4670 */ 4671 if (p->hmode == M_CLNT && p->flags & P_MANY) { 4672 p->outdate = c.t; 4673 if (p->unreach > BEACON) { 4674 p->unreach = 0; 4675 p->ttl = 1; 4676 peer_xmit(p); 4677 } else if (s.n < MINCLOCK) { 4678 if (p->ttl < TTLMAX) 4679 p->ttl++; 4680 peer_xmit(p); 4681 } 4682 p->unreach++; 4683 poll_update(p, hpoll); 4684 return; 4685 } 4686 if (p->burst == 0) { 4688 /* 4689 * We are not in a burst. Shift the reachability 4690 * register to the left. Hopefully, some time before the 4691 * next poll a packet will arrive and set the rightmost 4692 * bit. 4693 */ 4694 oreach = p->reach; 4695 p->outdate = c.t; 4696 p->reach << 1; 4697 if (!(p->reach & 0x7)) 4698 clock_filter(p, 0, 0, MAXDISP); 4699 if (!p->reach) { 4701 /* 4702 * The server is unreachable, so bump the 4703 * unreach counter. If the unreach threshold has 4704 * been reached, double the poll interval to 4705 * minimize wasted network traffic. Send a burst 4706 * only if enabled and the unreach threshold has 4707 * not been reached. 4708 */ 4709 if (p->flags & P_IBURST && p->unreach == 0) { 4710 p->burst = BCOUNT; 4711 } else if (p->unreach < UNREACH) 4712 p->unreach++; 4713 else 4714 hpoll++; 4715 p->unreach++; 4716 } else { 4718 /* 4719 * The server is reachable. Set the poll 4720 * interval to the system poll interval. Send a 4721 * burst only if enabled and the peer is fit. 4722 */ 4723 p->unreach = 0; 4724 hpoll = s.poll; 4725 if (p->flags & P_BURST && fit(p)) 4726 p->burst = BCOUNT; 4727 } 4728 } else { 4730 /* 4731 * If in a burst, count it down. When the reply comes 4732 * back the clock_filter() routine will call 4733 * clock_select() to process the results of the burst. 4734 */ 4735 p->burst--; 4736 } 4738 /* 4739 * Do not transmit if in broadcast client mode. 4740 */ 4741 if (p->hmode != M_BCLN) 4742 peer_xmit(p); 4743 poll_update(p, hpoll); 4744 } 4746 A.5.7.2. poll_update() 4747 /* 4748 * poll_update() - update the poll interval for association p 4749 * 4750 * Note: This routine is called by both the packet() and poll() routine. 4751 * Since the packet() routine is executed when a network packet arrives 4752 * and the poll() routine is executed as the result of timeout, a 4753 * potential race can occur, possibly causing an incorrect interval for 4754 * the next poll. This is considered so unlikely as to be negligible. 4755 */ 4756 void 4757 poll_update( 4758 struct p *p, /* peer structure pointer */ 4759 int poll /* poll interval (log2 s) */ 4760 ) 4761 { 4762 /* 4763 * This routine is called by both the poll() and packet() 4764 * routines to determine the next poll time. If within a burst 4765 * the poll interval is two seconds. Otherwise, it is the 4766 * minimum of the host poll interval and peer poll interval, but 4767 * not greater than MAXPOLL and not less than MINPOLL. The 4768 * design insures that a longer interval can be preempted by a 4769 * shorter one if required for rapid response. 4770 */ 4771 p->hpoll = max(min(MAXPOLL, poll), MINPOLL); 4772 if (p->burst > 0) { 4773 if (p->nextdate != c.t) 4774 return; 4775 else 4776 p->nextdate += BTIME; 4777 } else { 4779 /* 4780 * While not shown here, the reference implementation 4781 * randomizes the poll interval by a small factor. 4782 */ 4783 p->nextdate = p->outdate + (1 << max(min(p->ppoll, 4784 p->hpoll), MINPOLL)); 4785 } 4787 /* 4788 * It might happen that the due time has already passed. If so, 4789 * make it one second in the future. 4790 */ 4791 if (p->nextdate <= c.t) 4792 p->nextdate = c.t + 1; 4793 } 4794 A.5.7.3. peer_xmit() 4795 /* 4796 * transmit() - transmit a packet for association p 4797 */ 4798 void 4799 peer_xmit( 4800 struct p *p /* peer structure pointer */ 4801 ) 4802 { 4803 struct x x; /* transmit packet */ 4805 /* 4806 * Initialize header and transmit timestamp 4807 */ 4808 x.srcaddr = p->dstaddr; 4809 x.dstaddr = p->srcaddr; 4810 x.leap = s.leap; 4811 x.version = p->version; 4812 x.mode = p->hmode; 4813 if (s.stratum == MAXSTRAT) 4814 x.stratum = 0; 4815 else 4816 x.stratum = s.stratum; 4817 x.poll = p->hpoll; 4818 x.precision = s.precision; 4819 x.rootdelay = D2FP(s.rootdelay); 4820 x.rootdisp = D2FP(s.rootdisp); 4821 x.refid = s.refid; 4822 x.reftime = s.reftime; 4823 x.org = p->org; 4824 x.rec = p->rec; 4825 x.xmt = get_time(); 4826 p->xmt = x.xmt; 4828 /* 4829 * If the key ID is nonzero, send a valid MAC using the key ID 4830 * of the association and the key in the local key cache. If 4831 * something breaks, like a missing trusted key, don't send the 4832 * packet; just reset the association and stop until the problem 4833 * is fixed. 4834 */ 4835 if (p->keyid) 4836 if (/* p->keyid invalid */ 0) { 4837 clear(p, X_NKEY); 4838 return; 4839 } 4840 x.dgst = md5(p->keyid); 4841 xmit_packet(&x); 4842 } 4843 Authors' Addresses 4845 Jack Burbank 4846 The Johns Hopkins University Applied Physics Laboratory 4847 11100 Johns Hopkins Road 4848 Laurel, MD 20723-6099 4849 US 4851 Phone: +1 443 778 7127 4852 Email: jack.burbank@jhuapl.edu 4854 William Kasch 4855 The Johns Hopkins University Applied Physics Laboratory 4856 11100 Johns Hopkins Road 4857 Laurel, MD 20723-6099 4858 US 4860 Phone: +1 443 778 7463 4861 Email: william.kasch@jhuapl.edu 4863 Jim Martin (editor) 4864 Daedelus Group 4865 411 Park Avenue, Unit 118 4866 Santa Jose, CA 95110 4867 US 4869 Email: jim@daedelus.com 4871 Dr. David L. Mills 4872 University of Delaware 4873 Newark, DE 19716 4874 US 4876 Phone: +1 302 831 8247 4877 Email: mills@udel.edu